When we did the General Problem Solver, GPS, you saw that it is often seen as marking the end of the let's-find-a-generally-intelligent-algorithm approach to AI. Proponents of this approach believed that we would eventually be able to find a powerful and intelligent algorithm capable of solving any problem, whether in chess-playing, algebra, or translation. All it would need to know about the problem would be a statement of the goal to be achieved and the ``rules of the game''. (In GPS, this information is conveyed in ``operator tables'' which specify the allowable ``moves'' or operations.)
Although GPS was called a General Problem Solver, it turned out not to be one. Its failure, some writers say, helped cause a shift in AI research: a shift from looking for generally intelligent algorithms (where all the intelligence is in the algorithm, and only a small amount of knowledge is added about each new problem), to devising problem-specific methods (where the ``intelligence'' is provided by large quantities of problem-specific knowledge).
The histories of AI generally agree that this was the motivation behind Dendral, one of the first expert systems. Instead of trying to construct grand methods which would solve any problem, Dendral's creators took a highly specific problem, that of interpreting mass spectra. They tried to answer the question: what knowledge do we need to do this, how should it be represented, and how can we acquire it? This is of interest to many chemists, and the Dendral project was set up as a collaboration between a group of chemists who needed to interpret mass spectra, and a group of Artificial Intelligentsia who saw this as a good test of the new approach. For an excellent account of this change of view, see Feigenbaum's article On generality and problem solving --- a case study using the Dendral project, in Machine intelligence 6 (1971) (RSL, probably the stack).
The approach chosen was to represent much of the knowledge as IF-THEN rules:
IF you know this
THEN you can deduce this
Systems which use rules in this way are often called rule-based
systems.
The same kind of shift took place in the thinking of Newell and Simon, the originators of GPS. They had devised GPS as a cognitive model --- a program which embodies a theory about how we perform certain types of cognitive task. GPS, however, is only a partial theory --- it does not, for example, say anything about the structure of memory, and it makes very specific assumptions about how control passes from one sub-task to the next.
Their successor to GPS for cognitive modelling was production systems --- a special class of rule-based system whose architecture is restricted to fit assumptions about low-level mental structure. In production systems, attention focuses much more than with GPS on what information is represented in memory, and what strategies are used to process it.
So this week's tutorial is on rule-based systems, on how they work, and on production systems and their use as cognitive models. I said above that production systems are deliberately restricted so they model various assumptions about mental structure --- such as the capacity of working memory. For engineering purposes, when you just want a rule-based system to do a certain job, these constraints are counter-productive. It's therefore important to understand how the internal mechanism of production systems differs from that of rule-based systems in general.
One difference is that whereas rule-based systems can be either forward-chaining or backward-chaining, production systems are always forward-chaining. These names, forward-chaining and backward-chaining, name two methods of inference. They are not differences in the rules themselves, but in the way one reasons with the rules: it's possible to reason both forward and back with the same set of rules.
The difference between forward-chaining and backward-chaining is, like the difference between depth-first and breadth-first strategies, one that appears in many places; you should know it for the exam, and you should be able to work examples of either direction of chaining, given a set of rules.
In the readings, you will often come across the name expert system. Most, but not all expert systems are rule-based systems. There is no exact definition of an expert system, but it's generally agreed that expert systems: