2.10 Rule-based Programming

(Reference: Science, 20 June 1980, Vol. 208. no. 4450, pp. 1335 - 1342 "Expert and Novice Performance in Solving Physics Problems", Jill Larkin, John McDermott, Dorothea P. Simon, and Herbert A. Simon. )

Much of the early AI research was informed by a cognitive psychology model of human expertise. The model has two parts:

• LTM: A large long term memory (100,000s of patterns)
• STM: A (much) smaller short term memory (seven, plus/minus two)

Reasoning was, according to this mode: a match-act cycle:

• Content of the STM matches patterns in the LTM
• LTM patterns have actions when, when they fire, rewrites the STM contents
• Goto 1.

In this model

• experts and experts because of the "power" patterns they have laboriously learned and added to their long term memory.
• novices are novices because they clog short term memory with irrelevant goals
• experts dodge that since their LTM patters tell them

Q: How to experts know what is relevant?

A: feature extractors- gizmos that experts learn to let them glance at a situation and extract the salient details. E.g. chess experts can reproduce form memory all the positions on a chess board But if you show the same experts a gibberish game (one where all the rules are broken- e.g white pawns on white’s back row) then they can’t reproduce the board. Why? Well, when they glance at a board, their feature extractors fire to offer them a succinct summary. Gibberish boards baffle the feature extractors, so no summary

Enter rule-based programming

Much, much work on mapping this cognitive psychological insight into AI programs

Success story #1: PIGE (not well known)

(Reference: "An Expert System for Raising Pigs" by T.J. Menzies and J. Black and J. Fleming and M. Dean. The first Conference on Practical Applications of Prolog 1992 . Available from http://menzies.us/pdf/ukapril92.pdf )

PIGE: Australia’s first exported rule-based expert systems

Written by me, 1987 who trapped the expertise of pig nutritionists in a few hundred rules.

PIGE would find factors to control, try them on a simulator of a farm, then adjust its factors accordingly.

Here’s PIGE out-performing the experts:

Why did PIGE success so well? Limits to short-term-memory. PIGE had none. The humans, on the other hand, had the standard human limitations

Success story #2: MYCIN (famous)

( V.L. Yu and L.M. Fagan and S.M. Wraith and W.J. Clancey and A.C. Scott and J.F. Hanigan and R.L. Blum and B.G. Buchanan and S.N. Cohen, 1979, Antimicrobial Selection by a Computer: a Blinded Evaluation by Infectious Disease Experts, Journal of American Medical Association, vo. 242, pages 1279-1282)

Given patient symptoms, what antibiotics should be prescribed?

Approx 500 rules.

Extensively studied:

Compared to humans, performed very well:

Why did it perform so well?

• Not because of the power of its algorithm (recursive descent through the rules- backward chaining)
• But only because of the knowledge in its rules
• In this case, algorithms, not knowledge, is power.

Success story #3: XCON and VT (very famous)

John McDermott, DEC, 1980s. Two systems:

• XCON, early 1980s, auto-configured DEC computers for customers. At its peak, 8,000 to 12,000 rules. Maintained by a team of 20 developers. Saving DEC (approx) $20M/year. (Reference: J. McDermott, 1993, R1 ("XCON") at age 12: lessons from an elementary school achiever, Artificial Intelligence, 59, 241-247)
• VT, mid to late 1980s, designer of elevators, 7000 rules. (Reference: ". Marcus and J. McDermott, 1989, (SALT): A Knowledge Acquisition Language for Propose-and-Revise Systems, Artificial Intelligence, 39, 1, pages1-37.)

The First AI Bubble

With strong theoretical support and excellent industrial case studies, the future for AI seemed bright.

Begin the AI summer (mid-1980s). Just like the Internet bubble of 2000: fledgling technology, over-hyped, immature tool kits.

And after the summer, came the fall. Enough said.

Happily, then came the 1990s, data mining, and results from real-time AI planners, and stochastic theorem provers.

By 2003, I could say I was an AI-nerd and people would not run away.

Inside Rule-based programming

Here’s a good introduction on rule-based programming. Read it (only pages 1,2,3,4,5,6,7) carefully to learn the meaning of:

• Conditions,
• Actions
• Backward chaining
• Forward chaining
• Working memory

Backward chaining supports how and why queries:

• How did you prove this goal?
• Why are you trying to prove this goal?

Forward chaining supports only how not why.

• Explain.

Define match, resolve, act

• With respect to the BAGGER system, define with examples conflict resolution using:
  • Rule ordering
  • Data ordering
  • Size ordering
  • Specificity ordering

  (Note: BAGGER is a toy example of how XCON configured computers.)

Rules: the Real Story

Rules- the good news

Some nice advantages for software engineering:

• Uniform representation simplified tool construction:
  • Rules are rules;
  • Feature extractors could be written as rules that run before anything else runs;
  • Conflict resolution operators could be written as rules.
  • For example, CMU’s SOAR language added a whole meta-layer called TAQL to handle: Within each problem space: problem space proposal, problem space initialization;
  • For each state in a problem space: state initialization, state elaboration, state evaluation
  • For each operator that can jump you between states: operator proposal, operator selection, operator implementation, how to handle operator failure, operator evaluation

  And guess what- all this was code with rules!

But Rules Have Problems

As rule-based programs became more elaborate, their support tools more intricate, the likelihood that they had any human psychological connection became less and less.

As we built larger and larger rule bases, other non-cognitive issues became apparent:

• Speed: within match-resolve-act, 80% of the time is spend in match.
• Maintenance: any rule can change the working memory to effect any other rule. XCON was the commercial AI success story of the early 1980s and the maintenance nightmare of the mid-1980s.
  • What works for 400 rules does not work for 8000
  • At its peak, DEC was claiming it saved the, $20M/year (which, in 1984, was real money!) but if any of XCON’s 20 developer’s left, ouch!

Note that both these problems come from the global nature of match: all rules over all working memory.

• A search by all rules through all possible working memory contents is slowwww.
• When humans maintain rules, understanding the connections between rules is difficult.

Improving Rule-based Programming

Solution #1: throw away rules.

Go to simpler representations. e.g. state machines (used in gaming, next lecture)

Solution #2: the RETE network

As used in many rule-based tools including OPS5, ART, JESS. Compile all the rules into a big network wiring all the conditions together.

• If 10 rules make the same test, represent the test once in the network.
• New facts get dropped into the top, bubble over the network, and matched actions pop out at the bottom.
• A little complex to implement (to say the least):

• Alpha nodes; matching within one test (e.g. a ≤ 7);
• Beta nodes: matching between tests (joins across tables)
• But what is Type? select?dummy?

RETE supports standard resolution operators: e.g.:

• Specificity: number of links in the network;
• Data ordering: when advancing over the net, work left to right, most recent to oldest

Note: RETE changes some constant time factors in the search but does not tame the fundamental problem of all rules looking in all places all the time.

Solution #3: divide the global space

If searching/understanding all is too much, find ways to built the whole from local parts. Have separate rule bases for each part.

Q: How to divide the system?

A1: Using domain knowledge; e.g. from [Tambe91]:

A2: using background knowledge of problem solving types. Add tiny little specialized rule bases to the implement knowledge-level operators.

E.g. here’s Clancy’s abstraction of MYCIN:

And here’s his abstraction of an electrical fault localization expert system:

Note that the same abstract problem solving method occurs in both

A whole mini-industry arose in the late 1980s, early 1990s defining libraries of supposedly reusable problem solving methods.

e.g. Here’s "diagnosis"

Here’s "monitoring":

Note that you could write and reuse rules based to handle select, compare, specify.

And there’s some evidence that this is useful. Marcus and McDermott built rule bases containing 7000+ rules via role-limiting methods. That is, once they knew their problem solving methods, they write specialized editors that only let users enter in the control facts needed to just run those methods.

• If you can’t use it...
• ... don’t ask for it.

For a catalog of problem solving methods, see Cognitive Patterns By Karen M. Gardner (contributors James Odell, Barry McGibbon), 1998, Cambridge University Press

This document was generated on March 1, 2011 using texi2html 5.0.