Production Systems

Production systems are computer languages that are widely employed for representing the processes that operate in models of cognitive systems (NEWELL and Simon 1972).

In a production system, all of the instructions (called productions) take the form:

IF <<conditions>, THEN <<actions>,

That is to say, "if certain conditions are satisfied, then take the specified actions" (abbreviated C → A). Production system languages have great generality: they can possess the full power and generality of a Turing machine (see TURING). They have an obvious affinity to the classical stimulus-response (S → R) connections in psychology, but greater complexity and flexibility, for, in production systems, both the conditions and the actions may, and generally do, contain variables that are instantiated to the appropriate values in each separate application.

The conditions of a production are propositions that state properties of, or relations among, the components of the system being modeled, in its current state. In implementing production systems the conditions are usually stored in a WORKING MEMORY, which may represent short-term memory or current sensory information, or an activated portion of semantic memory (Anderson 1993). To activate a production, all of the conditions specified in its "IF" clause must be satisfied by one or more elements in working memory. The actions that are then initiated may include actions on the system's environment (e.g., motor actions) or actions that alter its memories, including erasing and creating working memory elements.

The operation of a production system can be illustrated by a simple algebraic example that solves linear equations in one unknown:

IF the expression has the form X = N, where N is a number, THEN halt and check by substituting N in the original equation.
IF there is a term in X on the right-hand side, THEN subtract it from both sides, and collect terms.
IF there is a numerical term on the left-hand side, THEN subtract it from both sides, and collect terms.
IF the equation has the form NX = M, N - 1, THEN divide both sides by N.

If, for instance, the equation were 7X + 6 = 4X + 12, the condition of the second production would be satisfied, and 4X would be subtracted from both sides, yielding 3X + 6 = 12. Now the condition of the third production is satisfied, and 6 is subtracted from both sides, yielding 3X = 6. Next, the condition of the fourth production is satisfied and both sides are divided by 3, yielding X = 2. Finally, the condition of the first production is satisfied, and substituting 2 for X in the original equation and simplifying gives 14 + 6 = 8 + 12, or 20 = 20.

Notice that at the outset, the conditions of both productions 2 and 3 were satisfied. A production system must contain precedence rules that select which production will be executed when the conditions of more than one are satisfied (Brownston et al. 1985). One way in which the set of productions that are executable at any time can be limited is by including goals among their conditions. A goal is simply a symbol that must be present in working memory in order for a production containing that goal among its conditions to execute. Goals are set (i.e., goal symbols are placed in working memory) as part of the actions of other productions. Goals establish contexts so that only productions relevant to the current context will be executed. For example, we could add to the condition side of each production in the system for algebra described above "IF the goal is to solve an equation &." Then, even if the other conditions of these productions were satisfied, if that goal symbol were not in working memory, the productions would not execute.

Production systems were first invented by the logician Emil Post (1943) to provide a simple, clean language for the investigation of questions in the foundations of LOGIC and mathematics. They were borrowed, sometimes under the label of "Markov productions," for use in computer systems programming (languages for compiling compilers). In about the mid-1960s, they were introduced into cognitive science at Carnegie Mellon University, some of their early uses being in the General Problem Solver (GPS; Newell, Shaw, and Simon 1960), and in Tom Williams' thesis (Williams 1972) on a general game-playing program (see GAME-PLAYING SYSTEMS). They also found early use as languages for FORMAL GRAMMARS of natural language. Among production systems widely used in cognitive simulation are OPS5 (Brownston et al. 1985; Cooper and Wogrin 1988), Prolog (Clocksin and Mellish 1994), and Act-R (Anderson et al. 1993).

Adaptive production systems are production systems that contain a learning component that is capable of modifying productions already in the system and of creating new productions that can be added to the system (Neves 1978; see LEARNING SYSTEMS). Neves showed how this could be done for algebra by the method of learning from worked-out examples. Consider our earlier example:

7`X` + 6	=	4`X` + 12
3`X` + 6	=	12
3`X`	=	6
`X`	=	2

Assume that the adaptive production system had learned previously that the allowable actions include adding or subtracting the same numbers from both sides of an equation, or multiplying or dividing both sides by the same number, and simplifying by combining similar terms, but did not know when these actions should be applied to solve a problem. It would now examine the first two lines above, discovering that the unwanted 4X ("unwanted" because there is no such term in the last line) had been removed from the right-hand side, and that the action was to subtract this term. In the same way it would find that the condition "unwanted numerical term on left-hand side" characterized the second change, and "unwanted numerical coefficient of X," the third. It would create three new productions (the ones we have already seen above) and add them to its production system. Thenceforth, it would be capable of solving equations of this general kind.

This method, widely applied in adaptive production systems, of noting and eliminating from an equation expressions that are absent from the final result, is essentially the method of means-ends analysis incorporated in the General Problem Solver (Newell and Simon 1972; see also HEURISTIC SEARCH and PROBLEM SOLVING). The key steps in means-ends analysis are (1) to detect differences between the current and goal situations and (2) to find actions capable of removing these differences. The set of productions shown earlier is simply the "Table of Connections" between differences and operations in the GPS system.

Adaptive production systems, using the method of worked-out examples, today provide the theoretical foundation for a number of computer tutoring systems and mathematics textbooks and workbooks employed successfully in the United States and China (Anderson et al. 1995; Zhu et al. 1996)

References

Anderson, J. R. (1993). Rules of the Mind. Hillsdale, NJ: Erlbaum.

Anderson, J. R., A. T. Corbett, K. R. Koedinger, and R. Pelletier. (1995). Cognitive tutors: Lessons learned 94. Journal of Learning Science 4:167-207.

Brownston, L., R. Ferrell, E. Kant, and N. Martin. (1985). Programming Expert Systems in OPS5: An Introduction to Rule-based Programming. Reading, MA: Addison-Wesley.

Clocksin, W. F., and C. S. Mellish. (1994). Programming in Prolog. 4th ed. New York: Springer.

Cooper, T., and N. Wogrin. (1988). Rule-Based Programming with OPS5. San Mateo, CA: Kaufmann.

Neves, D. M. (1978). A computer program that learns algebraic procedures by examining examples and working problems in a textbook. Proceedings of the Second Conference of Computational Studies of Intelligence. Toronto: Canadian Society for Computational Studies of Intelligence, pp. 191-195.

Newell, A., and H. A. Simon. (1972). Human Problem Solving. Englewood Cliffs, NJ: Prentice-Hall.

Newell, A., J. C. Shaw, and H. A. Simon. (1960). Report on a general problem solving program for a computer. Proceedings of the International Conference on Information Processing. Paris: UNESCO, pp. 256-264.

Post, E. L. (1943). Formal reductions of the general combinatorial decision problem. American Journal of Mathematics 65:197-215.

Williams, T. (1972). Some studies in game playing with a digital computer. In H. A. Simon and L. Siklossy, Eds., Representation and Meaning: Experiments with Information Processing Systems. Englewood Cliffs, NJ: Prentice-Hall.

Zhu, X., Y. Lee, H. A. Simon, and D. Zhu. (1996). Cue recognition and cue elaboration in learning from examples. Proceedings of the National Academy of Sciences 93:1346-1351.

Production Systems

See also

References

Further Readings