Man, Marriage and Machine – Adventures in Artificial Advice, part 1

Part 2   |  Part 3  |  Try Socrates PWA | Printable Version

Introduction

Athens—Greece year 460 BC; a young man contemplating wedlock, asks Socrates for his advice. The wise one replies: “By all means, marry, if you get a good wife, you'll become happy; if you get a bad one, you'll become a philosopher”.

NY—NY year 2011; a young man asks “Socrates” the same question. The wise one replies: “Based on income compatibility, age, employment status, marriage penalty tax liability and cohabitating couple economy; you have a low chance of a successful marriage. Well “Socrates” is not communicating via a paranormal medium—it is an “Expert System”.

While Ray Kurzweil’s age of spiritual machines is still a future possibility, the age of artificial advisors is already here. These expert systems based advisors operate in diverse domains like:

• Reviewing mortgage loans
• Providing regional retail recommendations
• Evaluate carcinogenic potential of chemicals
• Assessing tax returns
• Assessing environmental impact
• Business rules engine

So I set out to write my own artificial advisor. Its goal is to provide an objective assessment of one’s nuptial success, based on factors like MBTI, income compatibility, age, employment status, marriage penalty tax liability etc. To honor its wisdom I named it “Socrates”.

“Try the Socrates PWA on a mobile device” or "try the standalone C++ desktop app".

If you find it amusing then read on, I will show you how to build it.

Background

Year 1997, Deep Blue defeats chess grandmaster Gary Kasparov and this year Watson defeats jeopardy champions Ken Jennings and Brad Rutter. Deep Blue demonstrated solving extremely complex but logically well bounded problems like chess. Watson on the other hand solved the problem of meaning behind natural languages, which inherently is unbounded. Both Deep Blue and Watson are indicative of the great strides made in the field of Artificial Intelligence. AI-complete fields like natural language processing and open domain question answering are still in the realm of computer science research. It may take a while for such fields to become useful for mainstream commercial applications. One AI discipline that has matured and found applicability in diverse domains like internal medicine, accounting, finance, organic chemistry etc. is Expert Systems.

What is an Expert System?

An expert system is a computer system that emulates, or acts in all respects, with the decision-making capabilities of a human expert. An expert system is functionally equivalent to a human expert in a specific problem domain of reasonable complexity. The equivalence in qualified in terms of its capability to:

• Reason over representations of human knowledge
• Solve the problem by heuristic or approximation techniques
• Explain and justify the solution based on known facts

So why do we need to create an Expert System if a human expert can solve the same problem? Well here are a few reasons :

• Low cost of expertise
• Response without cognitive bias or logical fallacies
• 24/7 availability with high reliability
• Clone the expert
• Use in hazardous environments
• Ability to explain the reasoning without attitude.

I will delve into theoretical concepts later, for now let's get started with programming an expert.

Programming an Expert system

Download and install CLIPS. (CLIPS is an open source framework for programming expert systems, it was developed by NASA-Johnson Space Center).
Open CLIPSWin.exe. From the Window menu open the facts and agenda windows.

You are now all set to program an expert system.

Writing “Hello world” in CLIPS

In the CLIPS programming window write the following code (or just copy/paste it) and hit enter.

(defrule start-up
=>
(printout t "Hello indecisive homo sapien. The ‘wise one’ is here to help!" crlf ))

Then type (run) and hit enter.

A “Hello indecisive…” message will show up on the window. Let us take a closer look at what just happened.

Heuristic knowledge as Rules

A rule captures a set of actions to perform in response to certain stimuli. The stimuli come from the information in the working memory of an expert system. This information is called facts. Coming back to the “Hello world” app. The first thing you did was define a rule using the “defrule” construct and named it "start-up". This instructs the expert system to create a rule. A rule consists of two parts

1. Left hand side (LHS) or antecedent
2. Right hand side (RHS) or consequent

The antecedents of a rule are a collection of “conditional elements” (CEs). When all CEs are satisfied (evaluate to true) actions in the RHS of the rule are executed. Since our “start-up” rule has no conditions it executes (or fires) immediately after you issue the (run) command. The “run” command instructs the expert system engine to fire all rules whose LHS or antecedents are true (or have no antecedents).

Rules with antecedents

Now let us modify the rule and add a condition (antecedent or LHS). Say you want to print “Hello indecisive…” only when there exists a fact with a specific name in it. In order to do that we modify the rule and add an antecedent or LHS to it. The antecedent is a fact represented by symbols “name asheesh goja” . I will explain facts and symbols in more detail later, but for now modify the rule by typing the following text and hit enter

(defrule start-up
(name asheesh goja) 
=>
(printout t "Hello indecisive homo sapien. The 'wise one' is here to help!" crlf))

Type (run) and hit enter. This time there is no response from the system. It is because this rule will fire only when a fact “(name asheesh goja)” exists in its working memory or facts list.

To add this fact type the following code and hit enter

(assert (name asheesh goja))

Notice two things happen after you issue this command

1. An entry shows up in the agenda window: “start-up: f-1”
2. And another one in the facts windows: “f-1 (name asheesh goja)”.
   (Note: You will also see a fact “f0 (initial-fact)”, this ‘a priori’ fact is created by the CLIPS engine)

Creating (or “asserting” in experts system parlance) a fact triggers the “start-up” rule, as the rule's antecedents are now true. So when you run the engine it fires the rule. Type (run) and hit enter to see the “Hello indecisive…” shows up.

Ok now let us step back to take a peek under the hood.

Anatomy of an expert system

An expert system consists of the following components:

1. Explanation facility – Provides the reasoning behind a certain conclusion.
2. Knowledge acquisition facility – Provides a means for capturing and storing knowledge elicited from a human expert(s) into a knowledge base.
3. Knowledge base– Stores this knowledge in form of rules.
4. Working memory–Database of facts used by the rules.
5. Inference engine– Decides which rule to fire and in what priority.
6. Agenda – A prioritized list of rules whose conditions are satisfied by facts.
7. Pattern matcher– Compares rules and facts.

Execution of an expert system

The core facility in an expert system is its inference engine. The inference engine follows this cycle

1. Pattern matcher uses an algorithm like Rete to create a list of rules whose antecedents (or LHS) match (or are satisfied) with the facts in the working memory.
2. The agenda determines the order in which the rule fire from this list.
3. The conflict resolver selects the rule with the highest priority from the agenda.
4. The action executor executes the consequent (or RHS) of the selected rule and also removes this rule from the agenda.
5. The pattern matcher kicks in again and updates the agenda with rules whose antecedents match and also removes the rules whose don’t.

This cycle continues until there are no rules left in the agenda. A particular rule fires only once it’s LHS is satisfied. This important feature of expert systems is called Refraction. It ensures that the expert system doesn’t get caught in trivial loops.

Now that we know how an expert system works; the next thing is to find out how human expertise is converted into a format for expert systems to reason over. This is called Knowledge Engineering.

Knowledge Engineering

Knowledge engineering is the process of eliciting the domain knowledge from a human expert and then structuring, formalizing and integrating it into the knowledge base of an expert system. Domain knowledge is the logic or heuristic used by a human to arrive at a particular solution. Unlike an algorithm where you are guaranteed to get an exact solution in a finite amount of time, expert systems only guarantee the most reasonable solution in a finite time. Depending on the level of a human expert’s understanding of the causal connections of a system, a knowledge engineer can program an expert system using heuristic/empirical or structural/behavioral knowledge. The former is called shallow knowledge and latter deep knowledge. This knowledge is expressed as a collection of rules called the knowledge base. Now let us see how domain knowledge is represented as rules.

Knowledge Representation

Computer programs consist of data structures and algorithms while expert systems consist of knowledge and inference. Knowledge is part of hierarchy called the knowledge pyramid.

Representing knowledge so that valid inferences can be made from it is called knowledge representation. Before we represent knowledge we first need to define:

• What is knowledge?
• How is knowledge acquired?
• How do we know what we know?

A study of such questions is called epistemology.

Epistemology

Epistemology is the study of the nature, structure and origins of knowledge. Categories of epistemology are:

• A priori - This is the universally true knowledge.
• A posteriori – This is knowledge acquired from senses and can be invalidated on basis of new knowledge
• Procedural - This is the knowledge of how to do something.
• Declarative – This is the knowledge that something is true or false.
• Tacit – This is unconscious knowledge.

Epistemic categories are represented in expert systems as productions.

Productions

Productions consists of two parts: A precondition (an IF) and a post condition (a THEN). If the production’s precondition is verified as true based on the current state of the system, then the production is triggered. You saw one such production called rules in the “Heuristic knowledge as Rules” section. Additional techniques used to define productions are:

• Semantic nets
• Frames
• Logic

Logic

Logic is the study of making valid inferences. It has two primary branches:

• Informal Logic – Here the meaning of statement is used to make valid inferences. Semantics is of the essence.
• Formal Logic – Here the form of statement is used to make valid inferences. Syntax is of the essence.

Formal Logic

Expert systems need to make inferences without knowing the meaning of words, hence they use formal logic. The most fundamental formal logic is based on syllogism. Consider the following statements

1. all programmers are smart.
2. asheesh is a programmer.
3. therefore asheesh is smart.

Using the law of syllogism , the 3rd statement was inferred from the hypothesis of the 1st statement and the conclusion of 2nd. This syllogism is represented in an expert system as a rule that takes the form

IF all programmers are smart AND
asheesh is as programmer
THEN asheesh is smart

Methods of inference or reasoning

Key to knowledge representation is to separate the actual meaning of words from the reasoning process itself. What may appear as reasoning may be knowledge. Once that is accomplished then inferences can be represented as mathematical rules that change one set of symbols to another. Various methods of making inferences are:

1. Deduction – a premise, a conclusion and a rule that the former implies the latter
2. Induction – inference is from the specific case to the general
3. Intuition – no proven theory
4. Heuristics – rules of thumb based on experience
5. Generate and test – trial and error
6. Abduction – reasoning back from a true condition to the premises that may have caused the condition
7. Default – absence of specific knowledge
8. Autoepistemic – self-knowledge
9. Nonmonotonic – previous knowledge
10. Analogy – inferring conclusions based on similarities with other situations

The process of grouping multiple inferences that connects a problem with a solution is called chaining.

Chaining

A chain that is traversed from a problem to its solution is called a forward chain. A chain traversed from a hypothesis back to the facts that support the hypothesis is a backward chain. Consider the following rules chain

• IF A then B
• IF B then C
• IF C then D

If fact A is asserted then the inference engine matches the facts against the antecedents resulting in assertion of intermediate facts B and C. This in-turn leads to conclusion D. This is forward chaining.

In backward chaining if fact (or hypothesis) D is asserted then the inference engine matches the facts against the consequents. Thus C and B now become sub-goals or intermediate hypotheses that must be satisfied to satisfy the hypotheses D. The evidence as fact A ends the backward chain of sub-goals hence validating D. If no A is found then hypothesis D is unsupported. The chain now becomes

• IF D then C
• IF C then B
• IF B then A

We will use this technique to create a backward chaining algorithm in part-2 of this article. For now let see how these concepts apply to our “Hello world” program.

Knowledge representation in CLIPS

In the “Hello world“ app the “start-up” rule has an antecedent (or LHS) expressed as a set of three symbols “name asheesh goja”. This rule creates the causal connection between the precondition (LHS) and the conclusion (RHS/antecedent). The CLIPS engine doesn’t know the meaning of these symbols. All it does is to see if a fact (a set of symbols in the working memory) matches the LHS of the rule. So when you entered symbols “name asheesh goja” in the facts list, it resulted into a complete pattern match (between LHS and fact), hence activation of “start-up” rule. This in-turn triggers the rule's consequent, hence executing the command in its RHS viz. “(printout t "Hello indecisive homo sapien. The 'wise one' is here to help!"))”. Additional constructs used by a knowledge engineer to represent domain expertise are:

1. Ordered Facts
2. Unordered Facts
3. Rules

Let me explain them in more detail.

Ordered Facts

The fact “(name asheesh goja)” is example of an ordered fact. The first field of an ordered fact specifies a “relation” that applied to the remaining fields in the ordered fact. Ordered facts don’t have an associated fact template. The ones that have are called unordered facts.

Unordered facts

These are structured fact representations created using the “deftemplate” construct. We can use this construct to create a new fact called “homo-sapien” and add name and age attributes/slots to it. Type or copy/paste the following code blocks in CLIPS ( hit enter after you type them)

(clear)

(deftemplate homo-sapien
    (multislot name (type SYMBOL) (default none) )
    (slot age (type INTEGER) (default 0) ))

I issued a (clear) command to remove any existing facts and rules. You can constraint attributes of an unordered fact with following restrictions:

1. type
2. default
3. cardinality
4. range
5. allowed-[symbols, strings, lexemes, floats, numbers, instance-names, values].

Rules

Rules in CLIPS are created using the “defrule” construct. Let us rewrite the “start-up” rule to use the unordered fact created above. Type or copy/paste the following code in CLIPS and press enter

(defrule start-up
    (homo-sapien (age 37) (name asheesh goja)) 
     =>
    (printout t "Hello indecisive homo sapien. The 'wise one' is here to help!"))

Notice that in the LHS of this rule the order of the fact’s slots doesn’t matter. I specified the age before name. This is the reason why such facts are called unordered facts.

Now that you know the fundamental constructs required to create the knowledge base and working memory, let us see how to create a non-trivial program using some more advanced concepts. CLIPS allows you to control the pattern matching (matching facts with LHS) using

1. Literal constraints
2. Variable constraints
3. Conditional Elements (CE)

Literal constraints

The “start-up” rule’s LHS is constrained by the literals 37 and “asheesh goja”. This means that this rule will fire only when facts match these constraints. To see that add the following facts (one at a time, followed by pressing the enter key)

(assert (homo-sapien (name huan goja) (age 38)))

(assert (homo-sapien (name thomas goja) (age 41)))

Notice that no activations show up in the agenda window. This means that none of these facts match the LHS of the “start-up” rule; reason being the literal constrain. Now add a fact that matches the constraints

(assert (homo-sapien (name asheesh goja) (age 37)))

You will now see three facts in the facts window and the following activation in the agenda window:

“0 start-up: f-3”.

This means that the rule “start-up” LHS matches the fact “f-3”. The fact “f-3” corresponds to “(name (value asheesh goja) (age 37))”

Variable constraints

What if you want to constraint age attribute within a range of values. Say you want the rule to fire the rule only when age of a person is more than 30 but less than 40. Additionally you want to print out the name of the person(s) that fall in this age category. For that you need variable constraints.

Modify the “start-up” rule’s LHS and add the following variable constraints. Type this code and press enter

(defrule start-up
    (homo-sapien (age ?a&:(> ?a 30)&:(< ?a 40)) (name $?n) ) 
     =>
    (printout t "Hello indecisive homo sapien named " ?n ". The 'wise one' is here to help!" crlf))

Notice two activations show up in the agenda window:

1. “0 start-up: f-3”.
2. “0 start-up: f-1”.

The syntax may take some time getting used to, but it perfectly complements the functional programming style of CLIPS. CLIPS uses the prefix notation as opposed to the infix which is common in procedural languages like C++, .net, Java etc. Read this article for more information on such notations.

Now let us take a closer look at LHS to see it individual elements along the variable constraints

This is how you read it in plain English:

Any homo sapien (homo-sapien) whose (age) stored in variable named ‘a’ (?a) and (&) constrained by (:) a value greater that 30 (> ?a 30) and (&) constrained by (:) a value less that 40 (< ?a 40) and (name) stored in multi-field variable named ‘n’ ($?n)

In additional to the '&' connective constraint CLIPS supports:

1. ~ (not connective)
2. | (or connective)

And conditional element (CE)

We looked at controlling the pattern matching using variable constrains within a fact, but what if we want to express relations between groups of facts. Say we want to trigger “start-up” rule with a constrained “homo -sapien” fact and only if he/she is a millionaire. To do that we add another condition in the LHS of the rule and constraint it with the value stored in variable ?n. Type this rule in CLIPS

(defrule start-up
    (and (homo-sapien (age ?a&:(> ?a 30)&:(< ?a 40)) (name $?n) ) 
    (millionaire $?n)) 
     =>
    (printout t "Hello indecisive millionaire homo sapien named " ?n ". The 'wise one' is here to help!" crlf))

The rule will fire when following facts exist:
Any homo-sapien whose age is within 30-40 and whose name stored in variable ?n matches any millionaire whose name is the name stored in variable ?n.

Notice after you write this modified rule the agenda window becomes empty. Now enter a “millionaire” fact

(assert (millionaire asheesh goja))

The agenda now shows:
“0 start-up: f-3,f-4”.

The conditional element used in this rule was “and”. Using it is optional as it is assumed by default. So you can rewrite the rule and omit “and” CE.

(defrule start-up
     (homo-sapien (age ?a&:(> ?a 30)&:(< ?a 40)) (name $?n) ) 
     (millionaire $?n) 
   =>
     (printout t "Hello indecisive millionaire homo sapien named " ?n ". The 'wise one' is here to help!" crlf))

Or conditional Element

Say you want to trigger this rule with either of the conditions: homo-sapien or millionaire. This is done using the “or” CE

(defrule start-up
   (or (homo-sapien (age ?a&:(> ?a 30)&:(< ?a 40)) (name $?n) ) 
   (millionaire $?n)) 
=>
   (printout t "Hello indecisive millionaire homo sapien named " ?n ". The 'wise one' is here to help!" crlf))

The rule will now fire only when the following facts exist:
Any homo-sapien whose age is within 30-40 and whose name stored in variable $?n, OR any millionaire whose name is stored in variable $?n.

Notice three activations show up in the agenda window:

• “0 start-up: f-4”.
• “0 start-up: f-3”.
• “0 start-up: f-1”.

This means that this rule will fire three times.

Enter (run) and to see the following:

• Hello indecisive millionaire homo sapien named (asheesh goja). The 'wise one' is here to help!
• Hello indecisive millionaire homo sapien named (asheesh goja). The 'wise one' is here to help!
• Hello indecisive millionaire homo sapien named (huan goja). The 'wise one' is here to help!

Additional CEs supported in CLIPS are

1. not
2. exists
3. test
4. forall
5. logical.

Limitations of Expert Systems

While expert systems provide consistent answers for repetitive decisions and can process large quantities of information; it is important to know its limitations though. Here are a few:

• Expert systems work best in a narrow domain of reasonable complexity. Generalizing them for a broader domain is usually counterproductive.
• An expert system cannot completely replace human common sense.
• It is not always possible for a human expert to explain how he/she reasons. This can make developing an expert system completely unfeasible.
• Expert systems don’t guarantee the quality of its rules. Garbage in = Garbage out.
• Given the ease of adding new rules, a novice knowledge engineer can easy add rules that conflict with existing rules, potentially compromising the accuracy/reliability of the expert system.

Part 2

I will introduce you to more advanced expert system concepts as and when needed. For now grab a cup of joe and get ready for a deep dive into coding a real expert system.

Man, Marriage and Machine – Adventures in Artificial Advice, part2

.