Lab 4: Rule-based Systems

From 6.034 Wiki

(Difference between revisions)
Jump to: navigation, search
m (Goal trees)
(Some hints from production.py)
(40 intermediate revisions not shown.)
Line 13: Line 13:
Those who think recursively may also benefit from the Python function <tt>reduce</tt> (the equivalent of Scheme's "fold-left" or "accumulate"), documented in the [http://docs.python.org/lib/built-in-funcs.html#reduce Python library reference].
Those who think recursively may also benefit from the Python function <tt>reduce</tt> (the equivalent of Scheme's "fold-left" or "accumulate"), documented in the [http://docs.python.org/lib/built-in-funcs.html#reduce Python library reference].
 +
 +
A note on nomenclature: Wherever possible, we try to be consistent with our use of certain keywords. In particular, the words ''clause'', ''expression'', and ''statement'' are very vague and overloaded, but we attempt to use them mostly consistently in this document:
 +
* IF, THEN, and DELETE commands are '''clauses'''
 +
* AND, OR, and NOT commands are '''expressions'''
 +
* AND and OR expressions comprise zero or more '''statements'''; NOT expressions comprise a single statement (which is semantically negated)
 +
We will occasionally use ''expression'' or ''statement'' in a different context, but the context of usage should make their intended meaning clear.
== Forward chaining ==
== Forward chaining ==
Line 19: Line 25:
This section is an explanation of the system you'll be working with. There aren't any problems to solve, but read it carefully anyway.
This section is an explanation of the system you'll be working with. There aren't any problems to solve, but read it carefully anyway.
-
This problem set will make use of a ''production rule system''. The system is given a list of rules and a list of data. The rules look for certain things in the data -- these things are the ''antecedents'' of the rules -- and usually produce a new piece of data, called the ''consequent''. Rules can also delete existing data.
+
This problem set will make use of a ''production rule system''. The system is given a list of rules and a list of data. A '''datum''' is simply a statement (string) declaring a fact or a relation, e.g. <tt>'Jake is a person'</tt>. A '''rule''' is a combination of a predicate (''antecedent'') and a resultant action or set of actions (''consequent'').
 +
 
 +
The system compares its rules against the data, attempting to find data that "matches" the antecedents of its rules. If it finds a datum that matches a particular rule's ''antecedent'', it may activate that rule to produce a new piece of data, the ''consequent''. Rules can also delete existing data.
Importantly, rules can contain variables. This allows a rule to match more than one possible datum. The consequent can contain variables that were bound in the antecedent.
Importantly, rules can contain variables. This allows a rule to match more than one possible datum. The consequent can contain variables that were bound in the antecedent.
Line 34: Line 42:
:If ''x'' is the parent of ''y'', and ''x'' is the parent of ''z'', then ''y'' is the sibling of ''z''.
:If ''x'' is the parent of ''y'', and ''x'' is the parent of ''z'', then ''y'' is the sibling of ''z''.
-
Given data that look like <tt>'parent marge bart'</tt> and <tt>'parent marge lisa'</tt>, then, it will produce further data like <tt>'sibling bart lisa'</tt>. (It will also produce <tt>'sibling bart bart'</tt>, which is something that will need to be dealt with.)
+
Given data that look like <tt>'parent marge bart'</tt> and <tt>'parent marge lisa'</tt>, then, it will produce further data like <tt>'sibling bart lisa'</tt>. (In this particular case, it will also produce <tt>'sibling bart bart'</tt>, which is something that will need to be dealt with.)
Of course, the rule system doesn't know what these arbitrary words "parent" and "sibling" mean! It doesn't even care that they're at the beginning of the expression. The rule could also be written like this:
Of course, the rule system doesn't know what these arbitrary words "parent" and "sibling" mean! It doesn't even care that they're at the beginning of the expression. The rule could also be written like this:
Line 46: Line 54:
Then it will expect its data to look like <tt>'marge is a parent of lisa'</tt>. This gets wordy and involves some unnecessary matching of symbols like <tt>'is'</tt> and <tt>'a'</tt>, and it doesn't help anything for this problem, but we'll write some later rule systems in this English-like way for clarity.
Then it will expect its data to look like <tt>'marge is a parent of lisa'</tt>. This gets wordy and involves some unnecessary matching of symbols like <tt>'is'</tt> and <tt>'a'</tt>, and it doesn't help anything for this problem, but we'll write some later rule systems in this English-like way for clarity.
-
Just remember that the English is for you to understand, not the computer.
+
'''Just remember that''' the English is for you to understand, not the computer. The computer's only concern is to pattern match the data with the rules.
==== Rule expressions ====
==== Rule expressions ====
Line 52: Line 60:
Here's a more complete description of how the system works.
Here's a more complete description of how the system works.
-
The rules are given in a specified order, and the system will check each rule in turn: for each rule, it will go through all the data searching for matches to that rule's antecedent, before moving on to the next rule.
+
The rules are given in a specified order, and the system will check each rule in turn: for each rule, it will iterate through all of the data (also known as assertions) searching for matches to that rule's antecedent, before moving on to the next rule.
A rule is an expression that can have an IF antecedent and a THEN consequent.  Both of these parts are required.
A rule is an expression that can have an IF antecedent and a THEN consequent.  Both of these parts are required.
Optionally, a rule can also have a DELETE clause, which specifies some data to delete.
Optionally, a rule can also have a DELETE clause, which specifies some data to delete.
-
The IF antecedent can contain AND, OR, and NOT expressions. AND requires that multiple statements are matched in the dataset, OR requires that one of multiple statements are matched in the dataset, and NOT requires that a statement is ''not'' matched in the dataset. AND, OR, and NOT expressions can be nested within each other. When nested like this, these expressions form an AND/OR tree (or really an AND/OR/NOT tree). At the bottom of this tree are strings, possibly with variables in them.
+
The IF antecedent can contain AND, OR, and NOT expressions. AND requires that multiple statements are matched in the dataset; OR requires that at least one of multiple statements are matched in the dataset; and NOT requires that a statement is ''not'' matched in the dataset. AND, OR, and NOT expressions can be nested within each other. When nested like this, these expressions form an AND/OR tree (or really an AND/OR/NOT tree). At the bottom of this tree are strings, possibly with variables in them.
-
The data is searched for items that match the requirements of the antecedent. Data items that appear earlier in the data take precedence. Each pattern in an AND clause will match the data in order, so that later ones have the variables of the earlier ones.
+
As explained above, for each rule, the system searches the data, in order, for data items that match the requirements of the rule's antecedent. Data items (assertions) that appear ''earlier'' in the data take precedence over data items that appear ''later'' in the data. If an AND or OR expression comprises multiple statements, we always try to match those statements ''in the order given''. This is particularly important for AND expressions, because if one of the AND expression's statements contains variables and we match that to a datum, we must apply those same variable bindings to the subsequent statements in the AND expression.
-
If there is a NOT clause in the antecedent, the data is searched to make sure that ''no'' items in the data match the pattern. A NOT clause should not introduce new variables - the matcher won't know what to do with them. Generally, NOT clauses will appear inside an AND clause, and earlier parts of the AND clause will introduce the variables. For example, this clause will match objects that are asserted to be birds, but are not asserted to be penguins:
+
If there is a NOT expression in the antecedent, the data is searched to make sure that ''no data item'' matches the pattern. '''A NOT expression should never introduce new variables''': the matcher won't know what to do with them, and it will certainly not behave as you expect it to. Generally, NOT expressions will appear inside an AND expression, and earlier parts of the AND expression will introduce the variables. For example, the following expression will match objects that are asserted to be birds, but are not asserted to be penguins:
<code><pre>
<code><pre>
Line 68: Line 76:
</pre></code>
</pre></code>
-
The other way around won't work:
+
The other way around '''will not work''':
<code><pre>
<code><pre>
Line 75: Line 83:
</pre></code>
</pre></code>
-
The terms '''match''' and '''fire''' are important. A rule '''matches''' if its antecedent matches the existing data. A rule that matches can '''fire''' if its THEN or DELETE clauses change the data. (Otherwise, it fails to fire.)
+
This is not a valid expression, because we introduced the variable ''x'' in a NOT expression.
 +
 
 +
The terms '''match''' and '''fire''' are important. A rule '''matches''' if its antecedent matches the existing data. A rule that matches can '''fire''' if its THEN or DELETE clauses ''change'' the data. (Otherwise, it fails to fire.)
Only one rule can fire at a time. When a rule successfully fires, the system changes the data appropriately, and then starts again from the first rule. This lets earlier rules take precedence over later ones. (In other systems, the precedence order of rules can be defined differently.)
Only one rule can fire at a time. When a rule successfully fires, the system changes the data appropriately, and then starts again from the first rule. This lets earlier rules take precedence over later ones. (In other systems, the precedence order of rules can be defined differently.)
Line 81: Line 91:
==== Running the system ====
==== Running the system ====
-
If you <tt>from production import forward_chain</tt>, you get a procedure <tt>forward_chain(rules, data, verbose=False)</tt> that will make inferences as described above. It returns the final state of its input data.
+
If you call <tt>from production import forward_chain</tt>, you gain access to a procedure <tt>forward_chain(rules, data, verbose=False)</tt> that will make inferences as described above. It's important to note that in our code, <tt>rules</tt> and <tt>data</tt> may either be supplied as lists or tuples; either is acceptable. (However, it may be most appropriate semantically to represent <tt>data</tt> as a list since it's mutable, and data may be added or removed.) This method returns the final state of its input data.
Here's an example of using it with a very simple rule system:
Here's an example of using it with a very simple rule system:
Line 104: Line 114:
<code><pre>
<code><pre>
Rule: IF(you have (?x), THEN('i have (?x)'))
Rule: IF(you have (?x), THEN('i have (?x)'))
-
Added: i have pear
+
Added assertion: i have apple
Rule: IF(you have (?x), THEN('i have (?x)'))
Rule: IF(you have (?x), THEN('i have (?x)'))
-
Added: i have apple
+
Deleted assertion: you have apple
Rule: IF(you have (?x), THEN('i have (?x)'))
Rule: IF(you have (?x), THEN('i have (?x)'))
-
Added: i have orange
+
Added assertion: i have orange
 +
Rule: IF(you have (?x), THEN('i have (?x)'))
 +
Deleted assertion: you have orange
 +
Rule: IF(you have (?x), THEN('i have (?x)'))
 +
Added assertion: i have pear
 +
Rule: IF(you have (?x), THEN('i have (?x)'))
 +
Deleted assertion: you have pear
('i have apple', 'i have orange', 'i have pear')
('i have apple', 'i have orange', 'i have pear')
</pre></code>
</pre></code>
-
NOTE: The <tt>Rule:</tt> and <tt>Added:</tt> lines come from the verbose printing.
+
NOTE: The <tt>Rule:</tt>, <tt>Added assertion:</tt>, and <tt>Deleted assertion:</tt> lines come from the verbose printing.
The final output is the set of assertions after applying the forward chaining procedure.
The final output is the set of assertions after applying the forward chaining procedure.
Line 120: Line 136:
As you answer the multiple choice questions below, keep in mind:
As you answer the multiple choice questions below, keep in mind:
* that the computer doesn't know English, and anything that reads like English is for the user's benefit only
* that the computer doesn't know English, and anything that reads like English is for the user's benefit only
-
* the difference between a rule having an antecedent that matches, and a rule actually '''firing'''
+
* that there is a difference between a rule having an antecedent that '''matches''', and a rule actually '''firing'''
 +
 
 +
Indicate your answers as strings assigned to <tt>ANSWER_i</tt> in <tt>lab1.py</tt> under "Part 1".
 +
 
 +
==== Questions 1-2: New assertions ====
 +
'''Question 1:''' In forward chaining, after all the variables in a rule have been bound, which part of the rule may appear as a new assertion in the data?
 +
 
 +
1. the antecedent
 +
 
 +
2. the consequent
 +
 
 +
3. both
 +
 
 +
4. neither
-
Indicate your answers as strings in <tt>lab1.py</tt>.
+
<tt>ANSWER_1</tt> should be <tt>'1'</tt>, <tt>'2'</tt>, <tt>'3'</tt>, or <tt>'4'</tt>.
-
'''Question 1:''' Which part of a rule may change the data?
+
'''Question 2:''' In backward chaining, after all the variables in a rule have been bound, which part of the rule may appear as a new assertion in the data?
1. the antecedent
1. the antecedent
Line 133: Line 162:
3. both
3. both
-
<tt>ANSWER_1</tt> should be <tt>'1'</tt>, <tt>'2'</tt>, or <tt>'3'</tt>.
+
4. neither
 +
<tt>ANSWER_2</tt> should be <tt>'1'</tt>, <tt>'2'</tt>, <tt>'3'</tt>, or <tt>'4'</tt>.
-
'''Rules for Questions 2-3'''
+
==== Questions 3-5: Hypothetical cats ====
 +
Consider the following rules about hypothetical cats.
 +
<pre>
 +
rule1 = IF( AND( '(?x) is a hypothetical cat',
 +
                '(?x) is alive',
 +
                NOT('(?x) is alive')),
 +
            THEN( '(?x) is a paradox' ) )
 +
 
 +
rule2 = IF( AND( '(?x) is a hypothetical cat',
 +
                '(?x) is alive',
 +
                '(?x) is dead')),
 +
            THEN( '(?x) is Schrodinger's cat' ) )
 +
 
 +
rule3 = IF( AND( '(?x) is a hypothetical cat',
 +
                NOT('(?x) is alive'),
 +
                NOT('(?x) is dead'))),
 +
            THEN( '(?x) is amortal' ) )
 +
</pre>
 +
'''Question 3:'''
 +
Consider the following set of assertions about Kitty.
 +
assertions = ( 'Kitty is a hypothetical cat',
 +
                'Kitty is alive',
 +
                'Kitty is dead' )
 +
Which rules would match in the first round of forward chaining?  Answer with a string of numbers in <tt>ANSWER_3</tt>.  (For example, if the assertions match <tt>rule1</tt> and <tt>rule2</tt>, answer <tt>'12'</tt>.)  If no rules match, answer <tt>'0'</tt>.
 +
 
 +
'''Question 4:'''
 +
Consider the following set of assertions about Nyan.
 +
assertions = ( 'Nyan is a hypothetical cat',
 +
                'Nyan is alive',
 +
                'Nyan is not alive' )
 +
Which rules would match in the first round of forward chaining?  Answer with a string of numbers in <tt>ANSWER_4</tt>.  If no rules match, answer <tt>'0'</tt>.
 +
 
 +
'''Question 5:'''
 +
Consider the following set of assertions about Garfield.
 +
assertions = ( 'Garfield is a hypothetical cat',
 +
                'Garfield likes lasagna' )
 +
Which rules would match in the first round of forward chaining?  Answer with a string of numbers in <tt>ANSWER_5</tt>.  If no rules match, answer <tt>'0'</tt>.
 +
 
 +
<!--If our system runs forward-chaining on this rule and set of assertions, will it produce the datum <tt>'Kitty is Schrodinger's cat'</tt>?  Answer <tt>'yes'</tt> or <tt>'no'</tt> in <tt>ANSWER_3</tt>.
 +
'''Question 4:'''
A rule-based system about Monty Python's "Dead Parrot" sketch uses the following rules:
A rule-based system about Monty Python's "Dead Parrot" sketch uses the following rules:
Line 144: Line 213:
             THEN( '(?x) is not dead' ) )
             THEN( '(?x) is not dead' ) )
   
   
-
  rule2 = IF( NOT( '(?x) is dead' ),
+
  rule2 = IF( AND('(?x) is motionless',
 +
                NOT('(?x) is dead')),
             THEN( '(?x) is pining for the fjords' ) )
             THEN( '(?x) is pining for the fjords' ) )
Line 152: Line 222:
   'Polly is motionless' )
   'Polly is motionless' )
-
'''Question 2:''' Will this system produce the datum <tt>'Polly is pining for the fjords'</tt>?  Answer <tt>'yes'</tt> or <tt>'no'</tt> in <tt>ANSWER_2</tt>.
+
'''Question 4:''' If this system runs forward-chaining on this rule set and data, will it produce the datum <tt>'Polly is pining for the fjords'</tt>?  Answer <tt>'yes'</tt> or <tt>'no'</tt> in <tt>ANSWER_4</tt>.
-
 
+
-
'''Question 3:''' Which rule contains a programming error?  Answer <tt>'1'</tt> or <tt>'2'</tt> in <tt>ANSWER_3</tt>.
+
 +
Which rule would contain a programming error if the order of the <tt>AND()</tt> conditions were switched?  Answer <tt>'1'</tt> or <tt>'2'</tt> in <tt>ANSWER_4</tt>.
 +
-->
-
'''Rules for Questions 4-5'''
+
==== Questions 6-7: Pendergast ====
In a completely different scenario, suppose we have the following rules list:
In a completely different scenario, suppose we have the following rules list:
Line 177: Line 247:
   'Pendergast can swim' )
   'Pendergast can swim' )
-
'''Question 4:''' After we start the system running, which rule fires first?  In <tt>ANSWER_4</tt>, answer <tt>'1'</tt> or <tt>'2'</tt>, or <tt>'0'</tt> if neither rule does what is asked.
+
'''Question 6:''' After starting the system, which rule fires first?  In <tt>ANSWER_6</tt>, answer <tt>'1'</tt> or <tt>'2'</tt>, or <tt>'0'</tt> if neither rule fires.
-
'''Question 5:''' Which rule fires second?  In <tt>ANSWER_5</tt>, answer <tt>'1'</tt> or <tt>'2'</tt>, or <tt>'0'</tt> if neither rule does what is asked.
+
'''Question 7:''' Which rule fires second?  In <tt>ANSWER_7</tt>, answer <tt>'1'</tt> or <tt>'2'</tt>, or <tt>'0'</tt> if neither rule fires.
Line 187: Line 257:
==== Poker hands ====
==== Poker hands ====
-
We can use a production system to rank types of poker hands against each other. If we tell it the basic things like <tt>'three-of-a-kind beats two-pair'</tt> and <tt>'two-pair beats pair'</tt>, it should be able to deduce by transitivity that <tt>'three-of-a-kind beats pair'</tt>.
+
We can use a production system to rank types of poker hands against each other. If we tell it the basic things like <tt>'three-of-a-kind beats two-pair'</tt> and <tt>'two-pair beats pair'</tt>, it would make sense for it be able to deduce by transitivity that <tt>'three-of-a-kind beats pair'</tt>.
You're given this data about poker hands:
You're given this data about poker hands:
Line 199: Line 269:
</pre>
</pre>
-
Write a one-rule system that finds all other combinations of which poker hands beat which, transitively, given some of the rankings already.  For example, it should be able to deduce that a three-of-a-kind beats a pair, because a three-of-a-kind beats two-pair, which beats a pair.  The rankings will all be provided in the form <tt>'(?x) beats (?y)'</tt>.
+
Write a one-rule system that finds all other combinations of which poker hands beat which, transitively, given some of the rankings already.  For example, it should be able to deduce that a three-of-a-kind beats a pair, because a three-of-a-kind beats two-pair and a two-pair beats a pair.  The rankings (data) will all be provided in the form <tt>'(?x) beats (?y)'</tt>.
-
Call the one rule you write <tt>transitive_rule</tt>, so that your list of rules is <tt>[ transitive_rule ]</tt>.
+
Put your one rule in the section "Part 2" of <tt>lab1.py</tt>, and assign it to the variable <tt>transitive_rule</tt>, so that your list of rules is <tt>[transitive_rule]</tt>.
-
You can test your <tt>transitive_rule</tt> on two additional data sets by uncommenting the print statements in <tt>lab1.py</tt>:
+
You can test your <tt>transitive_rule</tt> on two additional data sets by uncommenting some or all of the print statements in <tt>lab1.py</tt>:
<pre>
<pre>
-
abc_data = [ 'a beats b', 'b beats c' ]
+
print forward_chain([transitive_rule], abc_data)
-
 
+
print forward_chain([transitive_rule], poker_data)
-
minecraft_data = [ 'diamond sword beats diamond axe',
+
print forward_chain([transitive_rule], minecraft_data)
-
                  'diamond axe beats iron axe',
+
-
                  'iron axe beats iron pick',
+
-
                  'iron pick beats stone pick',
+
-
                  'stone pick beats stone shovel',
+
-
                  'stone shovel beats fist' ]
+
</pre>
</pre>
Line 225: Line 290:
Your task is to deduce, wherever you can, the following relations:
Your task is to deduce, wherever you can, the following relations:
-
* <tt>'sibling x y'</tt>: ''x'' is the sibling of ''y'' (sharing at least one parent)
+
* <tt>'sibling x y'</tt>: ''x'' is the sibling of ''y'' (''x'' and ''y'' are different people, but share at least one parent)
* <tt>'child x y'</tt>: ''x'' is the child of ''y''
* <tt>'child x y'</tt>: ''x'' is the child of ''y''
-
* <tt>'cousin x y'</tt>: ''x'' and ''y'' are cousins (a parent of ''x'' and a parent of ''y'' are siblings)
+
* <tt>'cousin x y'</tt>: ''x'' and ''y'' are cousins (a parent of ''x'' and a parent of ''y'' are siblings, but ''x'' and ''y'' are not siblings)
* <tt>'grandparent x y'</tt>: ''x'' is the grandparent of ''y''
* <tt>'grandparent x y'</tt>: ''x'' is the grandparent of ''y''
* <tt>'grandchild x y'</tt>: ''x'' is the grandchild of ''y''
* <tt>'grandchild x y'</tt>: ''x'' is the grandchild of ''y''
-
You will probably run into the problem that the system wants to conclude that everyone is their own sibling. To avoid this, you may want to write a rule that adds <tt>'self (?x) (?x)'</tt> for every person, and make sure that potential siblings don't have <tt>self</tt>. (Hint: The order of the rules will matter.) Note that it's fine to include statements that are not any of the specified relations, such as <tt>self</tt>. (You're also welcome to implement additional relations such as <tt>great-grandparent</tt> or <tt>nibling</tt> (which is a gender-neutral form of niece/nephew), if you feel so inclined.)
+
You will probably run into a problem where the system wants to conclude that everyone is their own sibling. To avoid this, you may want to write a rule that adds the relation <tt>'self (?x) (?x)'</tt> for every person, and make sure that potential siblings don't have <tt>self</tt>. (Hint: The order of the rules will matter.)
 +
 
 +
Note that for this problem, you are '''not''' limited to only defining rules that generate one of the five familial relations enumerated above. You are welcome to include rules that inform other relations (such as <tt>self</tt>, as described above). You're also welcome to implement additional familial relations such as <tt>great-grandparent</tt> or <tt>nibling</tt> (which is a gender-neutral form of niece/nephew), if you feel so inclined.
-
Some relations are symmetric, and you need to include them both ways. For example, if ''a'' is a cousin of ''b'', then ''b'' is a cousin of ''a''.
+
Keep in mind that some relations are symmetric, so you need to include them both ways. For example, if ''a'' is a cousin of ''b'', then ''b'' is a cousin of ''a''.
-
First, define all your rules individually -- that is, give them names by assigning them to variables.  This will enable you to refer to the rules by name and easily rearrange them if you need to.  Then, put them together into a list in order, and call it <tt>family_rules</tt>, so that the rules can be plugged into the forward chainer.
+
First, define all your rules individually -- that is, give them names by assigning them to variables.  This will enable you to refer to the rules by name and easily rearrange them if you need to.  Then, put them together into a list in order, and call it <tt>family_rules</tt>, so that the rules can be plugged into the forward-chaining system.
-
We've given you two larger sets of test data -- one for the Simpsons family, and one for the Black family from Harry Potter -- as well as a couple smaller data sets to help with debugging.  To debug what happened in your rules, you can set verbose=True.
+
We've given you two larger sets of test data -- one for the Simpsons family, and one for the Black family from Harry Potter -- as well as a couple smaller data sets to help with debugging.  To debug what happened in your rules, you can set <tt>verbose=True</tt>.
-
<tt>lab1.py</tt> will automatically define <tt>black_family_cousins</tt> to include all the <tt>'cousin x y'</tt> relations you find in the Black family. There should be 14 of them.
+
You will write your solution in <tt>lab1.py</tt> in the section labeled "Part 3". Note that <tt>lab1.py</tt> will automatically define a variable called <tt>black_family_cousins</tt> which will include all the <tt>'cousin x y'</tt> relations you find in the Black family, per your rule set. There should be 14 of them.
-
NOTE: Make sure you implement all five relations defined above.  In this lab, the online tester will be stricter, and may test some relations not tested offline.
+
IMPORTANT: Make sure you implement all five relations defined above.  In this lab, the online tester will be stricter, and may test some relations not tested offline.
== Backward chaining and goal trees ==
== Backward chaining and goal trees ==
Line 247: Line 314:
=== Goal trees ===
=== Goal trees ===
-
For the next problem, we're going to need a representation of goal trees. Specifically, we want to make trees out of AND and OR nodes, much like the ones that can be in the antecedents of rules. (There won't be any NOT nodes.) They will be represented as AND() and OR() objects. Note that both 'AND' and 'OR' inherit from the built-in Python type 'list', so you can treat them just like lists.
+
For the next problem, we're going to need a representation of goal trees. Specifically, we want to make trees out of AND and OR nodes, much like the ones that can be in the antecedents of rules. (There won't be any NOT nodes.) They will be represented as <tt>AND(...)</tt> and <tt>OR(...)</tt> objects. In our production code, <tt>AND</tt> and <tt>OR</tt> are subclasses of <tt>RuleExpression</tt>, which itself is a subclass of the Python built-in type <tt>list</tt>. Hence, you may iterate, slice, index into, and otherwise do any other standard list-like operation on <tt>AND</tt> and <tt>OR</tt> objects.
Strings will be the leaves of the goal tree. For this problem, the leaf goals will simply be arbitrary symbols or numbers like <tt>g1</tt> or <tt>3</tt>.
Strings will be the leaves of the goal tree. For this problem, the leaf goals will simply be arbitrary symbols or numbers like <tt>g1</tt> or <tt>3</tt>.
-
An '''AND node''' represents a list of subgoals that are required to complete a particular goal. If all the branches of an AND node succeed, the AND node succeeds. <tt>AND(g1, g2, g3)</tt> describes a goal that is completed by completing g1, g2, and g3 in order.
+
An '''AND node''' represents a list of sub-goals that are required to complete a particular goal. If all the branches of an AND node succeed, the AND node succeeds. <tt>AND(g1, g2, g3)</tt> describes a goal that is completed by completing g1, g2, and g3 in order. Similarly, <tt>AND</tt> can take in an iterable of arguments, so e.g. <tt>AND([g1, g2, g3])</tt> is equivalent to <tt>AND(g1, g2, g3)</tt>.
-
An '''OR node''' is a list of options for how to complete a goal. If any one of the branches of an OR node succeeds, the OR node succeeds. <tt>OR(g1, g2, g3)</tt> is a goal that you complete by first trying g1, then g2, then g3.
+
An '''OR node''' is a list of options for how to complete a goal. If any one of the branches of an OR node succeeds, the OR node succeeds. <tt>OR(g1, g2, g3)</tt> is a goal that you complete by first trying g1, then g2, then g3. Similarly, <tt>OR</tt> can take in an iterable of arguments, so e.g. <tt>OR([g1, g2, g3])</tt> is equivalent to <tt>OR(g1, g2, g3)</tt>.
'''Unconditional success''' is represented by an AND node with no requirements: <tt>AND()</tt>. '''Unconditional failure''' is represented by an OR node with no options: <tt>OR()</tt>.
'''Unconditional success''' is represented by an AND node with no requirements: <tt>AND()</tt>. '''Unconditional failure''' is represented by an OR node with no options: <tt>OR()</tt>.
Line 263: Line 330:
This is how we simplify goal trees:
This is how we simplify goal trees:
# If a node contains another node of the same type, absorb it into the parent node. So <tt>OR(g1, OR(g2, g3), g4)</tt> becomes <tt>OR(g1 g2 g3 g4)</tt>.
# If a node contains another node of the same type, absorb it into the parent node. So <tt>OR(g1, OR(g2, g3), g4)</tt> becomes <tt>OR(g1 g2 g3 g4)</tt>.
-
# Any AND node that contains an unconditional failure (OR) has no way to succeed, so replace it with unconditional failure.
+
# Any AND node that contains an unconditional failure (<tt>OR()</tt>) has no way to succeed, so replace it with unconditional failure.
-
# Any OR node that contains an unconditional success (AND) will always succeed, so replace it with unconditional success.
+
# Any OR node that contains an unconditional success (<tt>AND()</tt>) will always succeed, so replace it with unconditional success.
# If a node has only one branch, replace it with that branch. <tt>AND(g1)</tt>, <tt>OR(g1)</tt>, and <tt>g1</tt> all represent the same goal.
# If a node has only one branch, replace it with that branch. <tt>AND(g1)</tt>, <tt>OR(g1)</tt>, and <tt>g1</tt> all represent the same goal.
# If a node has multiple instances of a variable, replace these with only one instance. <tt>AND(g1, g1, g2)</tt> is the same as <tt>AND(g1, g2)</tt>.
# If a node has multiple instances of a variable, replace these with only one instance. <tt>AND(g1, g1, g2)</tt> is the same as <tt>AND(g1, g2)</tt>.
-
We've provided an abstraction for AND and OR nodes, and a function that simplifies them, in <tt>production.py</tt>. Everything you need to know about <tt>production.py</tt> is [#Some_hints_from_production.py described below], so you shouldn't need to read the source code. There is nothing for you to code in this section, but please make sure to understand this representation, because you're going to be building goal trees in the next section.
+
We've provided an abstraction for AND and OR nodes, and a function that simplifies them, in <tt>production.py</tt>. Everything you need to know about <tt>production.py</tt> is [[#Some_hints_from_production.py | described below]], so you shouldn't need to read the source code. There is nothing for you to code in this section, but please make sure to understand this representation, because you're going to be building goal trees in the next section.
Some examples:
Some examples:
<code><pre>
<code><pre>
Line 279: Line 346:
=== Backward chaining ===
=== Backward chaining ===
-
''Backward chaining'' is running a production rule system in reverse. You start with a conclusion, and then you see what statements would lead to it, and test to see if those statements are true.
+
''Backward chaining'' is running a production rule system in reverse. We start with a conclusion (the hypothesis), and then we find which rules, when fired, would yield that hypothesis; then, we test those rules' antecedents to figure out how we can successfully match them.
-
In this problem, we will do backward chaining by starting from a conclusion, and generating a goal tree of ''all'' the statements we may need to test.  The leaves of the goal tree will be statements like <tt>'opus swims'</tt>, meaning that at that point we would need to find out whether we know that Opus swims or not.
+
In this problem, we will do backward chaining by starting from a conclusion, and generating a goal tree of ''all'' of the statements we may need to test.  The leaves of the goal tree will be sentences (strings) like <tt>'opus swims'</tt>, meaning that at that point we would need to find out whether we know that Opus swims or not.
We'll run this backward chainer on the <tt>zookeeper</tt> system of rules, a simple set of production rules for classifying animals, which you will find in <tt>data.py</tt>. As an example, here is the goal tree generated for the hypothesis <tt>'opus is a penguin'</tt>:
We'll run this backward chainer on the <tt>zookeeper</tt> system of rules, a simple set of production rules for classifying animals, which you will find in <tt>data.py</tt>. As an example, here is the goal tree generated for the hypothesis <tt>'opus is a penguin'</tt>:
Line 295: Line 362:
</pre></code>
</pre></code>
-
You will write a procedure, <tt>backchain_to_goal_tree(rules, hypothesis)</tt>, which outputs the goal tree containing the statements you would need to test to prove the hypothesis.  Note that this function is supposed to be a general backchainer, so you should not hard-code anything that is specific to a particular rule set.  The backchainer will be tested on rule sets other than zookeeper_rules.
+
You will write a procedure, <tt>backchain_to_goal_tree(rules, hypothesis)</tt> (in "Part 4" of <tt>lab1.py</tt>), which outputs the goal tree containing the statements you would need to test to prove the hypothesis.  Note that this function is supposed to be a general backchainer, so you should not hard-code anything that is specific to a particular rule set.  The backchainer will be tested on rule sets other than <tt>zookeeper_rules</tt>.
-
The rules you work with will be limited in scope, because general-purpose backward chainers are difficult to write. In particular:
+
The rules you work with will be limited in scope, because general-purpose backward chainers are difficult to write. In particular, for this problem, make the following assumptions:
-
* You will never have to test a hypothesis with unknown variables. All variables that appear in the antecedent will also appear in the consequent.
+
* All variables that appear in a rule's antecedent also appear in its consequent (so there are no "unknown" variables in the antecedent). In other words, you will not need to do backtracking.
* All assertions are positive: no rules will have DELETE parts or NOT clauses.
* All assertions are positive: no rules will have DELETE parts or NOT clauses.
-
* Antecedents are not nested. Something like <tt>(OR (AND x y) (AND z w))</tt> will not appear in the antecedent parts of rules.
+
* Rule antecedents never have nested <tt>RuleExpression</tt> nodes. For example, something like <tt>(OR (AND x y) (AND z w))</tt> will never appear within an antecedent, since that comprises an AND expression nested under an OR expression.
Note that an antecedent can be a single hypothesis (a string) or a <tt>RuleExpression</tt>.
Note that an antecedent can be a single hypothesis (a string) or a <tt>RuleExpression</tt>.
Line 307: Line 374:
==== The backward chaining process ====
==== The backward chaining process ====
Here's the general idea of backward chaining:
Here's the general idea of backward chaining:
-
* Given a hypothesis, you want to see what rules can produce it, by matching the consequents of those rules against your hypothesis. All the consequents that match are possible options, so you'll collect their results together in an OR node. If there are no matches, this statement is a leaf, so output it as a leaf of the goal tree.
+
* Given a hypothesis, you want to see what rules can produce it, by matching the consequents of those rules against your hypothesis. All the consequents that match are possible options, so you'll collect their results together in an OR node. If there are no matches, this hypothesis is a leaf, so output it as a leaf of the goal tree.
* If a consequent matches, keep track of the variables that are bound. Look up the antecedent of that rule, and instantiate those same variables in the antecedent (that is, replace the variables with their values). This instantiated antecedent is a new hypothesis.
* If a consequent matches, keep track of the variables that are bound. Look up the antecedent of that rule, and instantiate those same variables in the antecedent (that is, replace the variables with their values). This instantiated antecedent is a new hypothesis.
* The antecedent may have AND or OR expressions. This means that the goal tree for the antecedent is already partially formed. But you need to check the leaves of that AND-OR tree, and recursively backward chain on them.
* The antecedent may have AND or OR expressions. This means that the goal tree for the antecedent is already partially formed. But you need to check the leaves of that AND-OR tree, and recursively backward chain on them.
Line 327: Line 394:
Both arguments to <tt>match</tt> must be strings; you cannot pass a consequent (an object of type THEN) to <tt>match</tt>, but you can index into the THEN (because it's a type of list) and pass each element to <tt>match</tt>.
Both arguments to <tt>match</tt> must be strings; you cannot pass a consequent (an object of type THEN) to <tt>match</tt>, but you can index into the THEN (because it's a type of list) and pass each element to <tt>match</tt>.
-
Note: <tt>{}</tt> and <tt>None</tt> are both <tt>False</tt> expressions in python, so you should explicitly check if match's return value is <tt>None</tt>.  If <tt>match</tt> returns <tt>{}</tt>, that means that the expressions match but there are no variables that need to be bound; this does not need to be treated as a special case.
+
Note: <tt>{}</tt> and <tt>None</tt> are both <tt>False</tt>-like values in Python, so you should explicitly check if <tt>match</tt>'s return value is <tt>None</tt>.  If <tt>match</tt> returns <tt>{}</tt>, that means that the statements match but there are no variables that need to be bound; this does not need to be treated as a special case.
-
<tt>populate(exp, bindings)</tt> - given an expression with variables in it, look up the values of those variables in ''bindings'' and replace the variables with their values. You can use the bindings from <tt>match(leaf_a, leaf_b)</tt> with <tt>populate(leaf, bindings)</tt>, which will fill in any free variables using the bindings.
+
<tt>populate(exp, bindings)</tt> - given an expression with variables in it, look up the values of those variables in ''bindings'' and replace the variables with their values. You can use the bindings from <tt>match(leaf_a, leaf_b)</tt> with <tt>populate(leaf, bindings)</tt>, which will fill in any free variables using the bindings. Note that the expression input to <tt>populate</tt> may either be a string or a more complicated tree:
* Example:  <tt>populate("(?x) is a (?y)", { x: "John", y: "student" }) => "John is a student"</tt>
* Example:  <tt>populate("(?x) is a (?y)", { x: "John", y: "student" }) => "John is a student"</tt>
 +
* Example:  <tt>populate(AND("(?x) is a (?y)", "(?x) loves (?z)"), { x: "John", y: "student" }) => AND("John is a student", "John loves (?z)")</tt>
 +
 +
<tt>rule.antecedent()</tt>: returns the IF part of a rule, which is either a leaf or a <tt>RuleExpression</tt>. Recall that <tt>RuleExpression</tt> objects act like lists, so you can iterate over them.
-
<tt>rule.antecedent()</tt>: returns the IF part of a rule, which is either a leaf or a RuleExpression. RuleExpressions act like lists, so you'll need to iterate over them.
+
<tt>rule.consequent()</tt>: returns the THEN part of a rule, which is either a leaf or a <tt>RuleExpression</tt>.
-
<tt>rule.consequent()</tt>: returns the THEN part of a rule, which is either a leaf or a RuleExpression.
+
By the way, if you need to know to what class an antecedent belongs, you may find the <tt>isinstance</tt> function helpful. For example, <tt>isinstance(my_antecedent, OR)</tt> returns <tt>True</tt> if <tt>my_antecedent</tt> is an <tt>OR</tt> object, otherwise it returns <tt>False</tt>.
== Survey ==
== Survey ==
Line 344: Line 414:
* <tt>COLLABORATORS</tt>: Other than 6.034 staff, whom did you work with on this lab? (string, or empty string if you worked alone)
* <tt>COLLABORATORS</tt>: Other than 6.034 staff, whom did you work with on this lab? (string, or empty string if you worked alone)
-
* <tt>HOW_MANY_HOURS_THIS_LAB_TOOK</tt>: Approximately how many hours did you spend on this lab? (number)
+
* <tt>HOW_MANY_HOURS_THIS_LAB_TOOK</tt>: Approximately how many hours did you spend on this lab? (number or string)
* <tt>WHAT_I_FOUND_INTERESTING</tt>: Which parts of this lab, if any, did you find interesting? (string)
* <tt>WHAT_I_FOUND_INTERESTING</tt>: Which parts of this lab, if any, did you find interesting? (string)
Line 375: Line 445:
'''Q:''' When I submit to the online tester, it hangs for a while and eventually prints a stack trace ending in httplib.BadStatusLine: ' '
'''Q:''' When I submit to the online tester, it hangs for a while and eventually prints a stack trace ending in httplib.BadStatusLine: ' '
-
'''A:''' '''(UPDATE)''' When run on Windows, Python versions 2.6.5 through 2.7.3 seem to be incompatible with our server.  The recommended solution is to install a version of Python >= 2.7.4 or <= 2.6.4; we recommend the latest stable release, Python 2.7.10.
+
'''A:''' When run on Windows, Python versions 2.6.5 through 2.7.3 seem to be incompatible with our server.  The recommended solution is to install a version of Python >= 2.7.4 or <= 2.6.4; we recommend the latest stable release, Python 2.7.10.
<!--We're investigating this; for now the best workaround is to ssh into Athena (or physically transfer your files over to an Athena computer if that's easier for you) and submit from there. If you encounter this problem, please email jmn@ and include your OS, your Python version, and what program you're using to run Python (IDLE, Spyder, Linux terminal, etc).
<!--We're investigating this; for now the best workaround is to ssh into Athena (or physically transfer your files over to an Athena computer if that's easier for you) and submit from there. If you encounter this problem, please email jmn@ and include your OS, your Python version, and what program you're using to run Python (IDLE, Spyder, Linux terminal, etc).
-->
-->

Revision as of 18:27, 14 September 2016

Contents


This lab is due by Tuesday, September 20 at 10:00pm.

To work on this lab, you will need to get the code, much like you did for Lab 0. You can:

All of your answers belong in the main file lab1.py.

You will probably want to use the Python feature called "list comprehensions" at some point in this lab, to apply a function to everything in a list. You can read about them in the official Python tutorial.

Those who think recursively may also benefit from the Python function reduce (the equivalent of Scheme's "fold-left" or "accumulate"), documented in the Python library reference.

A note on nomenclature: Wherever possible, we try to be consistent with our use of certain keywords. In particular, the words clause, expression, and statement are very vague and overloaded, but we attempt to use them mostly consistently in this document:

  • IF, THEN, and DELETE commands are clauses
  • AND, OR, and NOT commands are expressions
  • AND and OR expressions comprise zero or more statements; NOT expressions comprise a single statement (which is semantically negated)

We will occasionally use expression or statement in a different context, but the context of usage should make their intended meaning clear.

Forward chaining

Explanation

This section is an explanation of the system you'll be working with. There aren't any problems to solve, but read it carefully anyway.

This problem set will make use of a production rule system. The system is given a list of rules and a list of data. A datum is simply a statement (string) declaring a fact or a relation, e.g. 'Jake is a person'. A rule is a combination of a predicate (antecedent) and a resultant action or set of actions (consequent).

The system compares its rules against the data, attempting to find data that "matches" the antecedents of its rules. If it finds a datum that matches a particular rule's antecedent, it may activate that rule to produce a new piece of data, the consequent. Rules can also delete existing data.

Importantly, rules can contain variables. This allows a rule to match more than one possible datum. The consequent can contain variables that were bound in the antecedent.

A rule is an expression that contains certain keywords, like IF, THEN, AND, OR, and NOT. An example of a rule looks like this:

 IF( AND( 'parent (?x) (?y)',
          'parent (?x) (?z)' ),
     THEN( 'sibling (?y) (?z)' ))

This could be taken to mean:

If x is the parent of y, and x is the parent of z, then y is the sibling of z.

Given data that look like 'parent marge bart' and 'parent marge lisa', then, it will produce further data like 'sibling bart lisa'. (In this particular case, it will also produce 'sibling bart bart', which is something that will need to be dealt with.)

Of course, the rule system doesn't know what these arbitrary words "parent" and "sibling" mean! It doesn't even care that they're at the beginning of the expression. The rule could also be written like this:

 IF (AND( '(?x) is a parent of (?y)',
          '(?x) is a parent of (?z)' ),
     THEN( '(?y) is a sibling of (?z)' ))

Then it will expect its data to look like 'marge is a parent of lisa'. This gets wordy and involves some unnecessary matching of symbols like 'is' and 'a', and it doesn't help anything for this problem, but we'll write some later rule systems in this English-like way for clarity.

Just remember that the English is for you to understand, not the computer. The computer's only concern is to pattern match the data with the rules.

Rule expressions

Here's a more complete description of how the system works.

The rules are given in a specified order, and the system will check each rule in turn: for each rule, it will iterate through all of the data (also known as assertions) searching for matches to that rule's antecedent, before moving on to the next rule.

A rule is an expression that can have an IF antecedent and a THEN consequent. Both of these parts are required. Optionally, a rule can also have a DELETE clause, which specifies some data to delete.

The IF antecedent can contain AND, OR, and NOT expressions. AND requires that multiple statements are matched in the dataset; OR requires that at least one of multiple statements are matched in the dataset; and NOT requires that a statement is not matched in the dataset. AND, OR, and NOT expressions can be nested within each other. When nested like this, these expressions form an AND/OR tree (or really an AND/OR/NOT tree). At the bottom of this tree are strings, possibly with variables in them.

As explained above, for each rule, the system searches the data, in order, for data items that match the requirements of the rule's antecedent. Data items (assertions) that appear earlier in the data take precedence over data items that appear later in the data. If an AND or OR expression comprises multiple statements, we always try to match those statements in the order given. This is particularly important for AND expressions, because if one of the AND expression's statements contains variables and we match that to a datum, we must apply those same variable bindings to the subsequent statements in the AND expression.

If there is a NOT expression in the antecedent, the data is searched to make sure that no data item matches the pattern. A NOT expression should never introduce new variables: the matcher won't know what to do with them, and it will certainly not behave as you expect it to. Generally, NOT expressions will appear inside an AND expression, and earlier parts of the AND expression will introduce the variables. For example, the following expression will match objects that are asserted to be birds, but are not asserted to be penguins:

 AND( '(?x) is a bird',
      NOT( '(?x) is a penguin' ))

The other way around will not work:

 AND( NOT( '(?x) is a penguin' ),  # don't do this!
      '(?x) is a bird' )

This is not a valid expression, because we introduced the variable x in a NOT expression.

The terms match and fire are important. A rule matches if its antecedent matches the existing data. A rule that matches can fire if its THEN or DELETE clauses change the data. (Otherwise, it fails to fire.)

Only one rule can fire at a time. When a rule successfully fires, the system changes the data appropriately, and then starts again from the first rule. This lets earlier rules take precedence over later ones. (In other systems, the precedence order of rules can be defined differently.)

Running the system

If you call from production import forward_chain, you gain access to a procedure forward_chain(rules, data, verbose=False) that will make inferences as described above. It's important to note that in our code, rules and data may either be supplied as lists or tuples; either is acceptable. (However, it may be most appropriate semantically to represent data as a list since it's mutable, and data may be added or removed.) This method returns the final state of its input data.

Here's an example of using it with a very simple rule system:

from production import IF, AND, OR, NOT, THEN, DELETE, forward_chain

theft_rule = IF( 'you have (?x)',
                  THEN( 'i have (?x)' ),
                  DELETE( 'you have (?x)' ))

data = ( 'you have apple',
         'you have orange',
         'you have pear' )

print forward_chain([theft_rule], data, verbose=True)

We provide the system with a list containing a single rule, called theft_rule, which replaces a datum like 'you have apple' with 'i have apple'. Given the three items of data, it will replace each of them in turn.

Here is the output if you copy-and-pasted the code above and ran it as a python script:

Rule: IF(you have (?x), THEN('i have (?x)'))
Added assertion: i have apple
Rule: IF(you have (?x), THEN('i have (?x)'))
Deleted assertion: you have apple
Rule: IF(you have (?x), THEN('i have (?x)'))
Added assertion: i have orange
Rule: IF(you have (?x), THEN('i have (?x)'))
Deleted assertion: you have orange
Rule: IF(you have (?x), THEN('i have (?x)'))
Added assertion: i have pear
Rule: IF(you have (?x), THEN('i have (?x)'))
Deleted assertion: you have pear
('i have apple', 'i have orange', 'i have pear')

NOTE: The Rule:, Added assertion:, and Deleted assertion: lines come from the verbose printing. The final output is the set of assertions after applying the forward chaining procedure.

You can look at a much larger example in the zookeeper data in data.py, which classifies animals based on their characteristics.

Multiple Choice

As you answer the multiple choice questions below, keep in mind:

  • that the computer doesn't know English, and anything that reads like English is for the user's benefit only
  • that there is a difference between a rule having an antecedent that matches, and a rule actually firing

Indicate your answers as strings assigned to ANSWER_i in lab1.py under "Part 1".

Questions 1-2: New assertions

Question 1: In forward chaining, after all the variables in a rule have been bound, which part of the rule may appear as a new assertion in the data?

1. the antecedent

2. the consequent

3. both

4. neither

ANSWER_1 should be '1', '2', '3', or '4'.


Question 2: In backward chaining, after all the variables in a rule have been bound, which part of the rule may appear as a new assertion in the data?

1. the antecedent

2. the consequent

3. both

4. neither

ANSWER_2 should be '1', '2', '3', or '4'.

Questions 3-5: Hypothetical cats

Consider the following rules about hypothetical cats.

rule1 = IF( AND( '(?x) is a hypothetical cat',
                 '(?x) is alive',
                 NOT('(?x) is alive')),
            THEN( '(?x) is a paradox' ) )

rule2 = IF( AND( '(?x) is a hypothetical cat',
                 '(?x) is alive',
                 '(?x) is dead')),
            THEN( '(?x) is Schrodinger's cat' ) )

rule3 = IF( AND( '(?x) is a hypothetical cat',
                 NOT('(?x) is alive'),
                 NOT('(?x) is dead'))),
            THEN( '(?x) is amortal' ) )

Question 3: Consider the following set of assertions about Kitty.

assertions = ( 'Kitty is a hypothetical cat',
               'Kitty is alive',
               'Kitty is dead' )

Which rules would match in the first round of forward chaining? Answer with a string of numbers in ANSWER_3. (For example, if the assertions match rule1 and rule2, answer '12'.) If no rules match, answer '0'.

Question 4: Consider the following set of assertions about Nyan.

assertions = ( 'Nyan is a hypothetical cat',
               'Nyan is alive',
               'Nyan is not alive' )

Which rules would match in the first round of forward chaining? Answer with a string of numbers in ANSWER_4. If no rules match, answer '0'.

Question 5: Consider the following set of assertions about Garfield.

assertions = ( 'Garfield is a hypothetical cat',
               'Garfield likes lasagna' )

Which rules would match in the first round of forward chaining? Answer with a string of numbers in ANSWER_5. If no rules match, answer '0'.


Questions 6-7: Pendergast

In a completely different scenario, suppose we have the following rules list:

( IF( AND( '(?x) has feathers',  # rule 1
           '(?x) has a beak' ),
      THEN( '(?x) is a bird' )),
  IF( AND( '(?y) is a bird',     # rule 2
           '(?y) cannot fly',
           '(?y) can swim' ),
      THEN( '(?y) is a penguin' ) ) )

and the following list of initial data:

( 'Pendergast is a penguin',
  'Pendergast has feathers',
  'Pendergast has a beak',
  'Pendergast cannot fly',
  'Pendergast can swim' )

Question 6: After starting the system, which rule fires first? In ANSWER_6, answer '1' or '2', or '0' if neither rule fires.

Question 7: Which rule fires second? In ANSWER_7, answer '1' or '2', or '0' if neither rule fires.


If you're confused about any of the answers, look in tests.py for an explanation.

Rule systems

Poker hands

We can use a production system to rank types of poker hands against each other. If we tell it the basic things like 'three-of-a-kind beats two-pair' and 'two-pair beats pair', it would make sense for it be able to deduce by transitivity that 'three-of-a-kind beats pair'.

You're given this data about poker hands:

poker_data = ( 'two-pair beats pair',
               'three-of-a-kind beats two-pair',
               'straight beats three-of-a-kind',
               'flush beats straight',
               'full-house beats flush',
               'straight-flush beats full-house' )

Write a one-rule system that finds all other combinations of which poker hands beat which, transitively, given some of the rankings already. For example, it should be able to deduce that a three-of-a-kind beats a pair, because a three-of-a-kind beats two-pair and a two-pair beats a pair. The rankings (data) will all be provided in the form '(?x) beats (?y)'.

Put your one rule in the section "Part 2" of lab1.py, and assign it to the variable transitive_rule, so that your list of rules is [transitive_rule].

You can test your transitive_rule on two additional data sets by uncommenting some or all of the print statements in lab1.py:

print forward_chain([transitive_rule], abc_data)
print forward_chain([transitive_rule], poker_data)
print forward_chain([transitive_rule], minecraft_data)

Family relations

You will be given data that includes two kinds of statements:

  • 'person x': x is a person
  • 'parent x y': x is a parent of y

Every person in the data set will be explicitly defined as a person.

Your task is to deduce, wherever you can, the following relations:

  • 'sibling x y': x is the sibling of y (x and y are different people, but share at least one parent)
  • 'child x y': x is the child of y
  • 'cousin x y': x and y are cousins (a parent of x and a parent of y are siblings, but x and y are not siblings)
  • 'grandparent x y': x is the grandparent of y
  • 'grandchild x y': x is the grandchild of y

You will probably run into a problem where the system wants to conclude that everyone is their own sibling. To avoid this, you may want to write a rule that adds the relation 'self (?x) (?x)' for every person, and make sure that potential siblings don't have self. (Hint: The order of the rules will matter.)

Note that for this problem, you are not limited to only defining rules that generate one of the five familial relations enumerated above. You are welcome to include rules that inform other relations (such as self, as described above). You're also welcome to implement additional familial relations such as great-grandparent or nibling (which is a gender-neutral form of niece/nephew), if you feel so inclined.

Keep in mind that some relations are symmetric, so you need to include them both ways. For example, if a is a cousin of b, then b is a cousin of a.

First, define all your rules individually -- that is, give them names by assigning them to variables. This will enable you to refer to the rules by name and easily rearrange them if you need to. Then, put them together into a list in order, and call it family_rules, so that the rules can be plugged into the forward-chaining system.

We've given you two larger sets of test data -- one for the Simpsons family, and one for the Black family from Harry Potter -- as well as a couple smaller data sets to help with debugging. To debug what happened in your rules, you can set verbose=True.

You will write your solution in lab1.py in the section labeled "Part 3". Note that lab1.py will automatically define a variable called black_family_cousins which will include all the 'cousin x y' relations you find in the Black family, per your rule set. There should be 14 of them.

IMPORTANT: Make sure you implement all five relations defined above. In this lab, the online tester will be stricter, and may test some relations not tested offline.

Backward chaining and goal trees

Goal trees

For the next problem, we're going to need a representation of goal trees. Specifically, we want to make trees out of AND and OR nodes, much like the ones that can be in the antecedents of rules. (There won't be any NOT nodes.) They will be represented as AND(...) and OR(...) objects. In our production code, AND and OR are subclasses of RuleExpression, which itself is a subclass of the Python built-in type list. Hence, you may iterate, slice, index into, and otherwise do any other standard list-like operation on AND and OR objects.

Strings will be the leaves of the goal tree. For this problem, the leaf goals will simply be arbitrary symbols or numbers like g1 or 3.

An AND node represents a list of sub-goals that are required to complete a particular goal. If all the branches of an AND node succeed, the AND node succeeds. AND(g1, g2, g3) describes a goal that is completed by completing g1, g2, and g3 in order. Similarly, AND can take in an iterable of arguments, so e.g. AND([g1, g2, g3]) is equivalent to AND(g1, g2, g3).

An OR node is a list of options for how to complete a goal. If any one of the branches of an OR node succeeds, the OR node succeeds. OR(g1, g2, g3) is a goal that you complete by first trying g1, then g2, then g3. Similarly, OR can take in an iterable of arguments, so e.g. OR([g1, g2, g3]) is equivalent to OR(g1, g2, g3).

Unconditional success is represented by an AND node with no requirements: AND(). Unconditional failure is represented by an OR node with no options: OR().

A problem with goal trees is that you can end up with trees that are described differently but mean exactly the same thing. For example, AND(g1, AND(g2, AND(AND(), g3, g4))) is more reasonably expressed as AND(g1, g2, g3, g4). So, we've provided you a function that reduces some of these cases to the same tree. We won't change the order of any nodes, but we will prune some nodes that it is fruitless to check.

We have provided this code for you. You should still understand what it's doing, because you can benefit from its effects. You may want to write code that produces "messy", unsimplified goal trees, because it's easier, and then simplify them with the simplify function.

This is how we simplify goal trees:

  1. If a node contains another node of the same type, absorb it into the parent node. So OR(g1, OR(g2, g3), g4) becomes OR(g1 g2 g3 g4).
  2. Any AND node that contains an unconditional failure (OR()) has no way to succeed, so replace it with unconditional failure.
  3. Any OR node that contains an unconditional success (AND()) will always succeed, so replace it with unconditional success.
  4. If a node has only one branch, replace it with that branch. AND(g1), OR(g1), and g1 all represent the same goal.
  5. If a node has multiple instances of a variable, replace these with only one instance. AND(g1, g1, g2) is the same as AND(g1, g2).

We've provided an abstraction for AND and OR nodes, and a function that simplifies them, in production.py. Everything you need to know about production.py is described below, so you shouldn't need to read the source code. There is nothing for you to code in this section, but please make sure to understand this representation, because you're going to be building goal trees in the next section. Some examples:

 simplify(OR(1, 2, AND()))                                     => AND()
 simplify(OR(1, 2, AND(3, AND(4)), AND(5)))                    => OR(1, 2, AND(3, 4), 5)
 simplify(AND('g1', AND('g2', AND('g3', AND('g4', AND())))))   => AND('g1', 'g2', 'g3', 'g4')
 simplify(AND('g'))                                            => 'g'
 simplify(AND('g1', 'g1', 'g2'))                               => AND('g1', 'g2')

Backward chaining

Backward chaining is running a production rule system in reverse. We start with a conclusion (the hypothesis), and then we find which rules, when fired, would yield that hypothesis; then, we test those rules' antecedents to figure out how we can successfully match them.

In this problem, we will do backward chaining by starting from a conclusion, and generating a goal tree of all of the statements we may need to test. The leaves of the goal tree will be sentences (strings) like 'opus swims', meaning that at that point we would need to find out whether we know that Opus swims or not.

We'll run this backward chainer on the zookeeper system of rules, a simple set of production rules for classifying animals, which you will find in data.py. As an example, here is the goal tree generated for the hypothesis 'opus is a penguin':

OR(
  'opus is a penguin',
  AND(
    OR('opus is a bird', 'opus has feathers', AND('opus flies', 'opus lays eggs'))
    'opus does not fly',
    'opus swims',
    'opus has black and white color' ))

You will write a procedure, backchain_to_goal_tree(rules, hypothesis) (in "Part 4" of lab1.py), which outputs the goal tree containing the statements you would need to test to prove the hypothesis. Note that this function is supposed to be a general backchainer, so you should not hard-code anything that is specific to a particular rule set. The backchainer will be tested on rule sets other than zookeeper_rules.


The rules you work with will be limited in scope, because general-purpose backward chainers are difficult to write. In particular, for this problem, make the following assumptions:

  • All variables that appear in a rule's antecedent also appear in its consequent (so there are no "unknown" variables in the antecedent). In other words, you will not need to do backtracking.
  • All assertions are positive: no rules will have DELETE parts or NOT clauses.
  • Rule antecedents never have nested RuleExpression nodes. For example, something like (OR (AND x y) (AND z w)) will never appear within an antecedent, since that comprises an AND expression nested under an OR expression.

Note that an antecedent can be a single hypothesis (a string) or a RuleExpression.

The backward chaining process

Here's the general idea of backward chaining:

  • Given a hypothesis, you want to see what rules can produce it, by matching the consequents of those rules against your hypothesis. All the consequents that match are possible options, so you'll collect their results together in an OR node. If there are no matches, this hypothesis is a leaf, so output it as a leaf of the goal tree.
  • If a consequent matches, keep track of the variables that are bound. Look up the antecedent of that rule, and instantiate those same variables in the antecedent (that is, replace the variables with their values). This instantiated antecedent is a new hypothesis.
  • The antecedent may have AND or OR expressions. This means that the goal tree for the antecedent is already partially formed. But you need to check the leaves of that AND-OR tree, and recursively backward chain on them.

Other requirements:

  • The branches of the goal tree should be in order: the goal trees for earlier rules should appear before (to the left of) the goal trees for later rules. Intermediate nodes should appear before their expansions.
  • The output should be simplified as in the previous problem (you can use the simplify function). This way, you can create the goal trees using an unnecessary number of OR nodes, and they will be conglomerated together nicely in the end.
  • If two different rules tell you to check the same hypothesis, the goal tree for that hypothesis should be included both times, even though it seems a bit redundant.

Some hints from production.py

match(pattern, datum) - This attempts to assign values to variables so that pattern and datum are the same. You can match(leaf_a, leaf_b), and that returns either None if leaf_a didn't match leaf_b, or a set of bindings if it did (even empty bindings: {}).

Examples:

  • match("(?x) is a (?y)", "John is a student") => { x: "John", y: "student" }
  • match("foo", "bar") => None
  • match("foo", "foo") => {}

Both arguments to match must be strings; you cannot pass a consequent (an object of type THEN) to match, but you can index into the THEN (because it's a type of list) and pass each element to match.

Note: {} and None are both False-like values in Python, so you should explicitly check if match's return value is None. If match returns {}, that means that the statements match but there are no variables that need to be bound; this does not need to be treated as a special case.

populate(exp, bindings) - given an expression with variables in it, look up the values of those variables in bindings and replace the variables with their values. You can use the bindings from match(leaf_a, leaf_b) with populate(leaf, bindings), which will fill in any free variables using the bindings. Note that the expression input to populate may either be a string or a more complicated tree:

  • Example: populate("(?x) is a (?y)", { x: "John", y: "student" }) => "John is a student"
  • Example: populate(AND("(?x) is a (?y)", "(?x) loves (?z)"), { x: "John", y: "student" }) => AND("John is a student", "John loves (?z)")

rule.antecedent(): returns the IF part of a rule, which is either a leaf or a RuleExpression. Recall that RuleExpression objects act like lists, so you can iterate over them.

rule.consequent(): returns the THEN part of a rule, which is either a leaf or a RuleExpression.

By the way, if you need to know to what class an antecedent belongs, you may find the isinstance function helpful. For example, isinstance(my_antecedent, OR) returns True if my_antecedent is an OR object, otherwise it returns False.

Survey

Please answer these questions at the bottom of your lab1.py file:

  • NAME: What is your name? (string)
  • COLLABORATORS: Other than 6.034 staff, whom did you work with on this lab? (string, or empty string if you worked alone)
  • HOW_MANY_HOURS_THIS_LAB_TOOK: Approximately how many hours did you spend on this lab? (number or string)
  • WHAT_I_FOUND_INTERESTING: Which parts of this lab, if any, did you find interesting? (string)
  • WHAT_I_FOUND_BORING: Which parts of this lab, if any, did you find boring or tedious? (string)
  • (optional) SUGGESTIONS: What specific changes would you recommend, if any, to improve this lab for future years? (string)


(We'd ask which parts you find confusing, but if you're confused you should really ask a TA.)

When you're done, run the online tester to submit your code.

FAQ

Q: I'm getting a somewhat baffling "unhashable type: list" error when working on the family rules part.

A: This probably means your syntax for THENs is incorrect. A THEN with multiple consequents should look like THEN('consequent 1', 'consequent 2', 'consequent 3').


Q: When I submit to the online tester, it hangs for a while and eventually prints a stack trace ending in httplib.BadStatusLine: ' '

A: When run on Windows, Python versions 2.6.5 through 2.7.3 seem to be incompatible with our server. The recommended solution is to install a version of Python >= 2.7.4 or <= 2.6.4; we recommend the latest stable release, Python 2.7.10.


Personal tools