Monday, September 29, 2008

Animal as RDR, part III

Examples: Building, running and modifying RDR systems

The previous entries showed the implementation of the model of a simple Ripple-Down Rules (RDR) system. This entry will show how to implement the rules for such a system from scratch as well as how to run and then to modify such a system. Again, we are using the computer game Animal as the basis of these examples.

Let's start off by implementing RDR system modelled in the first entry on this topic. But first, we need a couple of improvements. The addRule I had originally implemented wasn't an example for ease of use as it was ...
] addRule :: BinDir
] → RuleTree a b c k v
] → Environment k v b c
] → Condition a (Knowledge k v)
] → Conclusion b c (Knowledge k v)
] → RuleTreeEnv a b c k v
] addRule dir (Zip hist branch) env cond concl
] = let rule = Branch (Rule cond concl) Leaf Leaf
] newbr = fromJust $ mutate dir rule branch
] newtree = return $ settle (Zip hist newbr)
] in RuleEnv newtree env
... so I changed it so that it fit more neatly into building rules in sequence:
> addRule :: BinDirRule a b c (Knowledge k v)
> → RuleTree a b c k v → RuleTree a b c k v
> addRule dir rule (Zip hist branch)
> = let ruleB = Branch rule Leaf Leaf
> in Zip hist (mutate dir ruleB branch)
This new implementation has now replaced the previous one in the implementation entry. Also, constructing Rules themselves was a bit labour-intensive, so I've added the following function to simplify building simple rules:
> type SimpleRule = Rule String String String 
> (Knowledge String String)

> mkRule :: StringStringSimpleRule
> mkRule key ans = Rule (present key) (assume ans)
Also, recall that:
(>>|) :: Monad m ⇒ m a → (a → b) → m b
This function simply reorders the arguments of liftM, so why have it? I find it useful in the flow of building monadic systems, as demonstrated below.


And with that, let us build our Animal guessing game knowledge base:
> animalTree :: Zipper BinDir (BinaryTree SimpleRule)
> → Zipper BinDir (BinaryTree SimpleRule)
> animalTree tree = fromJust
> (return tree >>|
> addRule L (mkRule "has four legs" "pony") >>=
> advance L >>|
> addRule L (mkRule "barks" "dog") >>|
> addRule R (mkRule "swims" "fish") >>=
> advance L >>|
> addRule R (mkRule "purrs" "cat") >>=
> withdraw >>=
> advance R >>|
> addRule R (mkRule "spins web" "spider") >>|
> reset)
The function reset is from the Data.Zipper module:
> reset :: (Mutable c dir c, Transitive c dir)
> ⇒ Zipper dir c → Zipper dir c
> reset z@(Zip [] _) = z
> reset (Zip ((dir, h):t) elt) = reset (Zip t $ mutate dir elt h)
Looking at animalTree above, I say with unmasked pride that I feel (>>|) shows its hidden strength: I could not imagine puzzling out the proper way to write the above definition using liftM and have it follow the natural flow that it does with its current implementation. Also note that it is vital that reset be called after a set of changes to a knowledge base occur, to reset (obviously) the focus to the top-level (default) rule, and to correct the tree containing that knowledge.


Now that we have our animalTree, we need one more function to extract the result (follow the Conclusion) of runRule:
> runConcl :: RuleTreeEnv a b c k v → c
> runConcl (RuleEnv _ (Env ks (Concl _ f))) = f ks
Now, we could set up an interactive question-answer session to tease the animal we are guessing from our hidden thoughts, but, since interactive I/O is a sin in functional languages (see the fall from grace in Lazy K), let's "pretend" our way through an interactive session, recording the results of the questions into the Environment:
> rtests :: IO ()
> rtests = let RuleEnv tree env = initKB "default" (assume "none")
> newTree = animalTree tree
> spider = updateEnv "spins web" "true" env
> chat = updateEnv "has four legs" "true" $
> updateEnv "purrs" "true" env
> spy = runConcl (answer $ RuleEnv newTree spider)
> cat = runConcl (answer $ RuleEnv newTree chat)
> in do print newTree
> print spy
> print cat
As expected, spy is "spider" (in answer to the question "Does it spin a web?"), and cat is "cat" (in answer to the questions "Does it have four legs?" followed by "Does it purr?").


All is well and good with the world, yes? Certainly, when we receive the expected answers from our knowledge base, but let's explore the world a bit beyond what we've captured. Not everything that swims is a fish:
> fishey = let RuleEnv tree env  = initKB "default" (assume "none")
> newTree = animalTree tree
> duck = updateEnv "swims" "true"
> $ updateEnv "flies" "true" env
> noDuck = runConcl (answer $ RuleEnv newTree duck)
> in print noDuck
We find that noDuck is a "fish". Perhaps it's a "flying fish", but it definitely wasn't the animal we were guessing, so we need to update our knowledge base to give us the desired answer. Fortunately, the system returns the Rule that rendered the Conclusion, so modifying the system proceeds directly:
> duckey = let RuleEnv tree env  = initKB "default" (assume "none")
> newTree = animalTree tree
> duck = updateEnv "swims" "true"
> $ updateEnv "flies" "true" env
> re@(RuleEnv noDuckTree _) = answer $ RuleEnv newTree duck
> noDuck = runConcl re
> duckTree = addRule L (mkRule "flies" "duck") noDuckTree
> ducky = runConcl (answer $ RuleEnv duckTree duck)
> in print (noDuck, ducky)
With the modification in place, that is, the addition of the new EXCEPT Rule, we find that the animal that swims and flies is, indeed, a "duck", as expected. That's Just ducky!

Knowledge in context

Of course, there is the flying fish conundrum, so a better ordering would be to have the Conclusion of that Rule actually be "flying fish" and its EXCEPT clause (with the Condition being something like "webbed feet" or "feathers") rendering the "duck" Conclusion. While we're on the topic of structuring knowledge, not everything that purrs is a cat. The knowledge base could have had a very different structure if the Condition of the first Rule was "purrs". Trekkers know the answer to that one: "tribble", obviously! The follow-on EXCEPT clause (with the Condition of "four legs") would then clarify to the feline nature.

This demonstrates knowledge in context, where in one context, the context of "having four legs", the attribute of purring leads to "cat", but in another context (the blank context, but that context could be elaborated with some Rules that put us in the context of the Star Trek, um, multiverse?), the very same attribute leads to "tribble". Under this new context, "four legs" leads back to our "chat chapeau" (that is Viennese) [I am really running rampant with my `pataphorisms, I do apologize and will work to check myself, but topic of επιστήμη λόγος does rather lend itself to such openings [which I have relentlessly pursued ... again!]] Furthermore, the quiddity of "four legs" is, itself, context-based. In one sense it leads to every little girl's dream (a "pony") and following (EXCEPTing) that, several other species, and in another context, it leads to non-tribble purring creatures. This is a rather fundamental restructuring of our presumptions from the first article on this topic. I don't have a simple function that restructures knowledge assumptions in fundamental ways; I don't see the benefit of having one, so let's simply rewrite our knowledge base from scratch with our gained experience:
> startrek tree = fromJust
> (return tree >>|
> addRule L (mkRule "purrs" "tribble") >>=
> advance L >>|
> addRule L (mkRule "has four legs" "cat") >>|
> addTree R (firstRule (animalTree tree)) >>|
> reset)
> where addTree dir (Zip _ branch) (Zip hist tree)
> = Zip hist $ mutate dir branch tree
> firstRule = fromJust . advance L
Not as painful as I thought! There are a couple of points to note, however:
  1. The path to discovering a "cat" is duplicated, redundantly. This is fine, however: real knowledge is messy and contains redundancies, and this redundancy doesn't impact the (speed) efficiency of this knowledge base in any way; and,
  2. We are back to missing our "duck". I leave that as an exercise to you to re-add.

This concludes the series of articles on the explanation, implementation and demonstration of a simple Ripple-Down Rules (RDR) system. In these articles we showed that such systems are easy to implement in Haskell and then to use. Knowledge management, in and of itself, is a rather deep and tricky topic (we have hinted at such trickiness in our "Trouble with Tribbles"), but RDR, using the concept of knowledge in context provides a method that allows modelling this knowledge more directly and allows manipulation of assumptions without adding too much difficulty to the task of knowledge engineering.

No comments: