Research Plan

 Michael T. Cox
Computer Science Department
Carnegie Mellon University
Pittsburgh, PA 15213-3891




Abstract

In the following plan, I will propose two related lines of research. The first continues the effort of treating learning as a planning task and builds directly on my dissertation work. The goal is to further formalize the computational task of strategy selection, important in multistrategy learning systems that integrate multiple learning algorithms. In association with this first research direction, I intend to modify the computational system developed during my thesis work in order to model the learning-strategy selection by humans when learning to program. The second research goal poses a novel approach to learning conceptual categories. This research will develop algorithms that compare and contrast both expected and actual categories when revising background theories used in classification tasks. Both research directions combine ideas from artificial intelligence and cognitive science and have the potential of making major contributions to the two fields.

Learning as Planning

The idea of applying the metaphor of goal-directed planning to learning tasks presents a number of interesting research issues. The planning community has investigated problems of goal interaction, uncertainty, strategy selection, error recovery (including backtracking during the planning process and rollback during plan execution), and concurrency (End Note 1). In one form or another, all of these issues reappear given the following interpretation of the learning task. Broadly construed, the technique of nonlinear planning in the pursuit of explicit goals can be directly mapped to learning. Instead of desired states in the world, learning goals represent desired states in the background knowledge of the learner. Instead of operators that result in actions performed by agents, learning operators result in actions by learning algorithms. However, at a finer level of granularity the metaphor may not map so neatly. For example, I have established that the brother-clobbers-brother goal interaction (Sussman, 1975) is present in some situations during multistrategy learning (Cox & Ram, in press); however, it is not immediately apparent whether or not all types of goal interactions from the classical planning literature will apply to operators executing in the background knowledge. Therefore, one of my research goals is to more fully determine where the planning metaphor fits a learning framework and under what conditions it does not.

To support this goal I intend to expand the number of learning algorithms contained in Meta-AQUA's strategy suite. An early candidate for inclusion is the ID3 algorithm (Quinlan, 1986) that learns through decision trees. At the current time, I have addressed strategy selection at a very large grain size. That is, I have concentrated on integrating learning algorithms that do not perform the same learning function. Therefore, to fully address strategy selection it is necessary to address the selective superiority problem. Empirical results suggest that various inductive algorithms are better at classifying specific categories or particular distributions of data than others. Each algorithm is good at some but not all learning tasks. The selective superiority problem is to choose the most appropriate inductive algorithm, given a particular set of data (Brodley, 1993). A goal-driven approach to learning is well-suited to working on this problem because the knowledge needs are specific.

Additionally, I plan to extend the current taxonomy of learning goals understood by my system. This will expand the vocabulary with which to specify changes in the background knowledge of a system. Although learning goals are explicit in the Meta-AQUA system, one should not assume that they are always deliberate goals in cognitive terms. As Barsalou (in press) notes, there is an implicit goal-orientation in all learning agents. Thus, one must be careful to distinguish between the computational benefit of expressing goals explicitly and the cognitive interpretation in which some goals are considered either implicit in the behavior (the agent behaves as if having the goal) or subconsciously pursued. I make no claim as to which stance is preferred. For example, it cannot be reasonably claimed that humans actively form a goal to compare visual images, although they constantly do make such comparisons. However, humans can form high-level goals when learning. For example, novices learning LISP exhibit the goal of trying to understand a programming error by choosing the strategy of re-reading textual instructions or reviewing an earlier example.

An interesting cognitive-science inquiry that complements my computational research is to modify Meta-AQUA in order to cover a set of human data in a LISP troubleshooting domain. I have already shown the feasibility of this direction by adapting Meta-AQUA to cover one such protocol. The protocol was chosen from data gathered in the School of Education at Berkeley concerning the behavior of novice LISP programmers. These data support the positive relationship between metacognitive reasoning and learning in novel problem-solving domains (Pirolli & Recker, 1994). These data were collected and analyzed without knowledge of my own work, and I developed the Meta-AQUA system without knowledge of the data; therefore, the experiment to model the data with Meta-XP theory represents a double-blind exercise. If significant amounts of the data can be covered with minimal modification to the theory, then this supports the claim that my theory is a reasonable and sufficient model of reflection and learning.

Learning Bias and Category Membership

I have argued in previous work (Cox & Ram, 1994) that failure provides a computationally efficient bias-filter for input examples in machine-learning systems. Work in cognitive science (e.g., Chinn & Brewer, 1993) has likewise demonstrated a complementary role for anomalous data in revising background knowledge in scientific and naive theories. There are two major reasons that failure is a good bias from which to learn in both machines and humans. Failure guarantees that something worth learning exists, and it also guarantees that the degrees of freedom in learning are less than those when learning from success (Cox & Ram, 1994). A novel research direction exists from which to apply this result to concept learning. I propose to investigate the interaction of failure and knowledge during categorization tasks.

Typical theory-revision systems contain a single-concept background theory. For example, a system such as EITHER (Mooney, 1993) that contains the classical cup theory assigns either "cup" or "non-cup" to all input examples and then adjusts its domain rules when errors occur. Solitary classification systems, however, do not make complete cognitive sense. People do not fail simply by classifying a cup as a non-cup. Instead there exists a false-assignment category (such as bowl) that competes with the correct category. Failures then often lead human learners to use a compare and contrast procedure by which knowledge of the categories are refined. Yet not only is it significant that people perform this procedure, and thus such algorithms are worth discovering, but since more constraints exist under which learning can take place, such algorithms may be computationally much more tractable. This dictates that category learning should take place in the context of multi-category theories (Mooney & Ourston, 1991, report related progress in this area).

Using Meta-XPs structures, I have declaratively represented a number of reasoning failures that Meta-AQUA can reason about explicitly. The typical reasoning failure in category assignment is a failing positive (Mooney, 1993) such that a theory falsely categorizes an example, x, as a member of an expected category, E. Instead, x should be categorized by some other theory as a positive member of the actual category, A. My system uses a Meta-XP called an expectation failure to reason about such situations in story-understanding tasks. During misclassification in a multi-category domain theory, it is guaranteed that the category E is overly-general and the category A is overly-specific. Thus, for propositional Horn-clause theories, an extra rule or missing rule-antecedent exists in E and an extra rule-antecedent or missing rule also exists in A. I have established some preliminary heuristics for taking advantage of these constraints. Moreover, during misclassification, an agent should consider not just the fact that it thought x was a member of E, but was not; rather, the learner should also consider why x was a member of A. The agent can then compare and contrast the concepts E and A, the reasons why x was thought to be a member of E with the reason why x was thought not to be a member of A (if that was considered at all), and if A was not considered, then why not (was a memory association incorrect?). Many theory-revision systems compare x only with the theory supporting E and cannot search for errors that may be related to an interaction between multiple categories (and furthermore, none support memory errors).

Finally, although a failing positive implicitly implies a failing negative (or perhaps a novel category), the inverse does not necessarily hold. When a successful negative occurs, the judgement may result in either a successful positive or an impasse. That is, it may know that the example is not a cup, but may or may not know what the actual category is. Meta-XPs can represent both related cases as either a forgotten category (missing-association XP) or as a novel category (novel-situation XP). Neither case has been treated by current category theory-revision systems. Although I plan to make contributions to concept revision systems based on propositional Horn-clause logic, I also intend to go beyond such formulations to include hierarchically-structured case memories. My experience with case-based reasoning and explanation-pattern theory will facilitate such further extensions of concept learning through knowledge-intensive explanation and reflection (e.g., comprehension monitoring).

Conclusion

The Meta-AQUA system that I implemented in my dissertation work is a story-understanding system that learns from reasoning failures while processing short newspaper-like stories. For example, I have demonstrated in Cox & Ram (in press) the types of learning that may take place in a system that has a poor understanding of the objects at which dogs bark. In the story below, Meta-AQUA poses the question "Why did the dog bark?" after processing the sentence S2 because the system has only experienced dogs that bark at agents that threaten it. Therefore, it incorrectly believes that dogs bark only at animate objects. However, by elaborating and explaining the sentence S4, it learns (among other things) that dogs will bark at inanimate objects, not simply animate agents. That is, it refines its conceptual definition of the dog-barking schema. I have often been asked how the system determines that the reason the dog barks is that the dog detects some amount of contraband inside the luggage, rather than the fact that it detects exactly two kilograms of the contraband. My answer is that it possesses an explanation about authorities who detect explosives in a previous smuggling story, and thus the system can adapt that explanation to constrain the inferences that occur during comprehension. It is the contraband, rather than the amount of contraband, that is the focus of the explanation. A much more difficult story for a system to fully understand would be the following: In this superficially similar case, the number of objects that the trainer holds, rather than the kind of objects, is crucial to the explanation. The role of knowledge and explanation is much more complex in understanding this story. In particular, one cannot always depend on having a past case to adapt when explaining a story. If my proposed research goals are accomplished, I will be much closer to a theory with which to account for such ad hoc categories (Barsalou, 1983) as barking based on the number of objects. This will support the overall goal of establishing a more complete theory of multistrategy learning from both cognitive science and machine learning perspectives.

End Notes

  1. The issue of concurrent execution of learning algorithms is virtually unaddressed, but potentially of great computational benefit. I raised the issue in Cox & Ram (in press), but have not fully explored it.

    2.  

     
     
     

References

  1. Barsalou, L. W. (in press). Storage side effects: Studying processing to understand learning. In A. Ram & D. B. Leake (Eds.), Goal-driven learning. Cambridge, MA: MIT Press/Bradford Books.
  2. Barsalou, L. W. (1983). Ad hoc categories. Memory & Cognition, 11, 211-227.
  3. Brodley, C. (1993). Addressing the selective superiority problem: Automatic algorithm / model class selection. Machine Learning: Proceedings of the Tenth International Conference (pp. 17-24). San Mateo, CA: Morgan Kaufmann.
  4. Chinn, C. A., & Brewer, W. F. (1993). Factors that influence how people respond to anomalous data. In Proceedings of the Fifteenth Annual Conference of the Cognitive Science Society (pp. 318-323). Hillsdale, NJ: Lawrence Erlbaum Associates.
  5. Cox, M. T., & Ram, A. (in press). Interacting learning-goals: Treating learning as a planning task. In M. Keane & J.-P. Haton (Eds.), Topics in case-based reasoning (Lecture notes in artificial intelligence series). Berlin: Springer-Verlag.
  6. Cox, M. T., & Ram, A. (1994). Failure-driven learning as input bias. In Proceedings of the Sixteenth Annual Conference of the Cognitive Science Society (pp. 231-236). Hillsdale, NJ: Lawrence Erlbaum Associates.
  7. Pirolli, P., & Recker, M. (1994). Cognition and Instruction, 12(3), 235-275.
  8. Mooney, R. (1993). Integrating theory and data in category learning. In G. Nakamura, D. Medin, & R. Taraban (Eds.), The psychology of learning and motivation (Vol. 29): Categorization by humans and machines (pp. 189-218). New York: Academic Press.
  9. Mooney, R., & Ourston, D. (1991). Improving shared rules in multiple category domain theories. In Proceedings of the Eighth International Workshop on Machine Learning (pp. 534-538). San Mateo, CA: Morgan Kaufmann.
  10. Quinlan, J. R. (1986). Induction of decision trees. Machine Learning, 1, 81-106.
  11. Sussman, G. J. (1975). A computer model of skill acquisition. New York: American Elsevier.

    12.