The idea of reasoning by following simple rules provides an attractively straightforward characterization of cognition. However, production systems can be very difficult to design in ways that are guaranteed to always work. In this problem, you will write some functions to help you work with production systems, and then you will use those functions to reason about several different sets of rules.
We will represent a set of beliefs using Python sets: each element in the set corresponds to a true proposition. For example, the following belief states that 'a' and 'b' are true propositions:
In [ ]:
example_belief = {'a', 'b'}
As a quick refresher, Python sets are unique, unordered collections of objects. You can check if an item is in a set with the in keyword:
In [ ]:
'a' in example_belief
In [ ]:
'c' in example_belief
You can add new things to the set using the .add() method, for example:
In [ ]:
example_belief.add('c')
example_belief
So, our beliefs will be represented using sets, and we will represent the rules of our production system using a list of 2-tuples. Each tuple contains a condition and a result. The rule can be applied if the condition is present in the set of beliefs; if the rule is applied, then the result should be added to the set of beliefs. For example, the following belief again consists of 'a' and 'b', and the rules state that "if a, then b" and that "if c, then d":
In [ ]:
example_belief = {'a', 'b'}
example_rules = [('a', 'b'), ('c', 'd')]
To help visualize the rules a bit better, here is a function called print_rules that will print out each rule on a separate line:
In [ ]:
def print_rules(rules):
for rule in rules:
print(str(rule[0]) + " --> " + str(rule[1]))
In [ ]:
print_rules(example_rules)
match that searches through a given list of rules to find a rule that is triggered by the given set of beliefs.
In [ ]:
def match(belief, rules):
"""Determine whether a rule is triggered by the given set of beliefs.
The *first* rule in the list of rules that is triggered should be
returned (and you should only ever return one rule, even if multiple are
triggered). If no rule is triggered, None should be returned.
A rule should only be triggered if it adds something new to the set of
beliefs: for example, if the beliefs are `{'a', 'b'}`, and there is only
one rule, `('a', 'b')`, then it should not be triggered because it
doesn't add anything new. If the beliefs were just `{'a'}`, however, then
the rule *should* be triggered because it would add `b` to the set of
beliefs.
Hint: you should be able to do this in four lines of code (or less),
including the return statement.
Parameters
----------
belief : set
A set of true propositions.
rules : list of tuples
A list of tuples, such that for each tuple, the first element implies
the second (but not vice versa).
Returns
-------
The first rule (tuple) that was triggered, or None if no rules were triggered.
"""
### BEGIN SOLUTION
for rule in rules:
if (rule[0] in belief) and (rule[1] not in belief):
return rule
return None
### END SOLUTION
Check that your function behaves as expected, based on the example given above:
In [ ]:
print(match({'a'}, [('a', 'b')])) # should print ('a', 'b')
In [ ]:
print(match({'a', 'b'}, [('a', 'b')])) # should print None
In [ ]:
# add your own test cases here!
In [ ]:
from nose.tools import assert_equal
# check that a --> b is triggered
assert_equal(match({'a'}, [('a', 'b')]), ('a', 'b'))
# check that nothing is triggered, because 'b' does not trigger any rules
assert_equal(match({'b'}, [('a', 'b')]), None)
# check that nothing is triggered, because 'a' and 'b' are already in the belief
assert_equal(match({'a', 'b'}, [('a', 'b')]), None)
# check that a --> b is triggered
assert_equal(match({'a'}, [('a', 'b'), ('b', 'c')]), ('a', 'b'))
# check that b --> c is triggered
assert_equal(match({'a', 'b'}, [('a', 'b'), ('b', 'c')]), ('b', 'c'))
# check that nothing is triggered, because 'a', 'b', and 'c' are already in the belief
assert_equal(match({'a', 'b', 'c'}, [('a', 'b'), ('b', 'c')]), None)
print("Success!")
Now that we have a way to trigger rules based on a set of beliefs, we want to engage in a process called forward chaining. The idea behind forward chaining is that we want to execute rules that are triggered by our beliefs, and to continue triggering rules until no more can be triggered. For example, if we have:
rules = [("belief1", "belief2"), ("belief2", "belief3")]
belief = {"belief1"}
To start out, we have belief_1, but we also have a rule "if belief_1, then belief_2". So, we should update our belief with belief_2.
Then, we have another rule that says "if belief_2, then belief_3". Because our belief now consists of both belief_1 and belief_2 (due to triggering the first rule), this second rule should also be triggered, and should add belief_3 to our total set of beliefs.
forward_chain, to automatically perform forward chaining using a given set of initial beliefs and rules.Make sure your function does in fact perform full forward chaining -- if there are two matching rules, but only one matches at the beginning, they should still both be triggered:
In [ ]:
def forward_chain(belief, rules):
"""Fully execute a set of given rules that match a given belief, until
no more new rules are triggered. That is, this function should:
(i) Scan through the rules until it finds rule(s) which are applicable,
(ii) trigger such rules and update beliefs,
(iii) repeat (i) and (ii) until no further rules can be triggered.
Returns a new set of beliefs (without changing the original set of beliefs)
based on which rules were triggered.
Note: this function should employ a `while` loop and should call the `match`
function you implemented in the first part of this problem.
Hint: you should be able to do this in 8 lines of code, including the
return statement.
Parameters
----------
belief : set
A set of true propositions.
rules : list of tuples
A list of tuples, such that for each tuple, the first element implies
the second (but not vice versa).
Returns
-------
tuple of (new_belief, triggered_rules):
new_belief is an updated set of true propositions, and triggered_rules
is the list of rules that were triggered, in order.
"""
### BEGIN SOLUTION
new_belief = belief.copy()
rule = match(new_belief, rules)
triggered_rules = []
while rule:
triggered_rules.append(rule)
new_belief.add(rule[1])
rule = match(new_belief, rules)
return new_belief, triggered_rules
### END SOLUTION
In [ ]:
b, r = forward_chain({'a'}, [('a', 'b'), ('b', 'c')])
print_rules(r) # should print both 'a --> b' and 'b --> c'
b # should be {'a', 'b', 'c'}
In [ ]:
# add your own test cases here!
In [ ]:
"""Check that `forward_chain` uses the `match` function."""
from nose.tools import assert_raises
orig_match = match
del match
try:
assert_raises(NameError, forward_chain, {'a'}, [('a', 'b')])
finally:
match = orig_match
print("Success!")
In [ ]:
"""Ensure that the new belief is a different object from the original belief."""
b1 = {'a'}
b2 = forward_chain(b1, [('a', 'b')])
assert_equal(b1, {'a'})
assert_equal(b2, ({'a', 'b'}, [('a', 'b')]))
print("Success!")
In [ ]:
"""Check that full forward chaining works."""
b, r = forward_chain({'a'}, [('a', 'b'), ('b', 'c'), ('c', 'd')])
assert_equal(b, {'a', 'b', 'c', 'd'})
assert_equal(r, [('a', 'b'), ('b', 'c'), ('c', 'd')])
b, r = forward_chain({'a'}, [('b', 'c'), ('c', 'd'), ('a', 'b')])
assert_equal(b, {'a', 'b', 'c', 'd'})
assert_equal(r, [('a', 'b'), ('b', 'c'), ('c', 'd')])
b, r = forward_chain({'a'}, [('a', 'c'), ('a', 'b')])
assert_equal(b, {'a', 'b', 'c'})
assert_equal(r, [('a', 'c'), ('a', 'b')])
b, r = forward_chain({'b'}, [('a', 'b'), ('b', 'c')])
assert_equal(b, {'b', 'c'})
assert_equal(r, [('b', 'c')])
b, r = forward_chain({'a', 'b', 'c'}, [('b', 'c'), ('b', 'a'), ('a', 'b')])
assert_equal(b, {'a', 'b', 'c'})
assert_equal(r, [])
b, r = forward_chain(set(), [('b', 'c'), ('b', 'a'), ('a', 'b')])
assert_equal(b, set())
assert_equal(r, [])
print("Success!")
Imagine you have a small sprinkler that can water your grass, but does not reach the path you walk on, or your car. However, if it rains, then the car and the path both get wet. The sprinkler definitely comes on if the appropriate switch is flipped. We might try to capture this information in a production system as follows:
IF switch is flipped THEN sprinkler was on
IF sprinkler was on THEN grass is wet
IF it rained THEN car is wet
IF it rained THEN path is slippery
IF it rained THEN grass is wet
Or, in Python:
In [ ]:
rules_1 = [
('switch is flipped', 'sprinkler was on'),
('sprinkler was on', 'grass is wet'),
('it rained', 'car is wet'),
('it rained', 'path is slippery'),
('it rained', 'grass is wet')
]
If you now observed switch is flipped but nothing else, what would the above production system lead you to conclude? Use your forward_chain function to find out:
In [ ]:
# perform forward chaining on the belief that 'switch is flipped'
belief_1, triggered_rules_1 = forward_chain({'switch is flipped'}, rules_1)
# print which rules were triggered
print_rules(triggered_rules_1)
# show the final belief
belief_1
If your code was correct, the triggered rules would be:
switch is flipped --> sprinkler was on
sprinkler was on --> grass is wetWhich would lead to the beliefs that the switch is flipped, the sprinkler was on, and the grass is wet and nothing else. Students needed to say that they had no belief about the state of the path, not that the path was/was not slippery.
For this next section, let's imagine a different production system that is similar but ultimately unrelated to the one we defined in Part C:
IF sprinkler was on THEN switch is flipped
IF car is wet THEN it rained
IF path is slippery THEN it rained
IF grass is wet THEN it rained
Or, in Python:
In [ ]:
rules_2 = [
('sprinkler was on', 'switch is flipped'),
('car is wet', 'it rained'),
('path is slippery', 'it rained'),
('grass is wet', 'it rained')
]
In this new production system, if you knew only that the grass is wet what would you conclude? Again, you can use your forward_chain function to find out:
In [ ]:
# perform forward chaining on the belief that 'grass is wet'
belief_2, triggered_rules_2 = forward_chain({'grass is wet'}, rules_2)
# print which rules were triggered
print_rules(triggered_rules_2)
# show the final belief
belief_2
If your code was correct, the triggered rule would be:
grass is wet --> it rainedWhich would lead to the belief that the grass is wet and that it rained, but nothing else. Common sense tells us that the fact that it rained should also imply that the car is wet and the path is slippery, although this inference is not supported by the production rules in our new system. Other answers were accepted if they were well-justified.
Finally, we can imagine a third production system where the rules apply in both directions:
IF switch is flipped THEN sprinkler was on
IF sprinkler was on THEN grass is wet
IF it is raining THEN car is wet
IF it is raining THEN path is slippery
IF it is raining THEN grass is wet
IF sprinkler was on THEN switch is flipped
IF car is wet THEN it is raining
IF path is slippery THEN it is raining
IF grass is wet THEN it is raining
If you observed sprinkler was on, what would you conclude? You can again use forward_chain:
In [ ]:
# perform forward chaining on the belief that 'sprinkler was on'
belief_3, triggered_rules_3 = forward_chain({'sprinkler was on'}, rules_1 + rules_2)
# print which rules were triggered
print_rules(triggered_rules_3)
# show the final belief
belief_3
Despite only knowing that the sprinkler was on, we somehow managed to conclude that it also rained! This seems like an invalid inference to draw, because there is no causal mechanism by which the sprinkler affects the likelihood of rain.
Ideally, we would like to be able to make inverse inferences (concluding something about a cause from an effect) like "the grass it wet, so it probably rained" without fully committing to the belief that it rained and all further implications of that belief. In production systems, this is not possible, and simple workarounds don't work. For example, if one wants a rule to infer a cause from an effect (rain from wet grass) then in order to avoid spurious inferences it's necessary to include conditions involving all of the other causes of wet grass:
IF grass is wet AND NOT switch is flipped AND NOT there was a water balloon fight
AND NOT temperature is below the dew point AND ...