An interference matching technique for inducing abstractions

ABSTRACT

A method for inducing knowledge by abstraction from a sequence of training examples is described. The proposed method, interference matching, induces abstractions by finding relational properties common to two or more exemplars. Three tasks solved by a program that uses an interference-matching algorithm are presented. Several problems concerning the description of the training examples and the adequacy of interference matching are discussed, and directions for future research are considered.

REFERENCES

• 1: Bobrow, D., and Winograd, T. A knowledge representation language. Cognitive Science, in press.
• 2: Burge, J., and Hayes-Roth, F. A novel pattern learning and classification procedure applied to the learning of vowels. Proc. 1976 I.E.E.E. Int. Conf. Acoustics, Speech, and Signal Processing, Philadelphia, Pa., 1976, pp. 154-157.
• 3: Ernst, G.W., and Newell, A. GPS: A Case Study in Generality and Problem Solving. Academic Press, New York, 1969.
• 4: Evans, T.G. A program for the solution of geometric-analogy test questions. In Semantic Information Processing, M. Minsky, Ed., M.I.T. Press, Cambridge, Mass., 1968.
• 5: Hayes-Roth, F. The role of partial and best matches in knowledge systems. In Pattern-Directed Inference Systems, F. Hayes- Roth and D.A. Waterman, Eds., Academic Press, New York, in press.
• 6: Hayes-Roth, F., and Mostow, D.J. An automatically compilable recognition network for structured patterns. Proc. Fourth Int. Joint Conf. Artif. lntell., 1975, pp. 246-251.
• 7: Hayes-Roth, F. A structural approach to pattern learning and the acquisition of classificatory power. Proc. First Int. Joint Conf. Pattern Recognition, 1973, pp. 343-355.
• 8: Hayes-Roth, F. An optimal network representation and other mechanisms for the recognition of structured events. Proc. Second Int. Joint Conf. Pattern Recognition, 1974, pp. 95-101.
• 9: Hayes-Roth, F. Representation of structured events and efficient procedures for their recognition. Pattern Recognition, 8 (1976), 141-150.
• 10: Hayes-Roth, F. Fundamental mechanisms of intelligent behavior: The representation, organization, acquisition, and use of structural knowledge in perception and cognition. Doct. Diss. U. of Michigan, Ann Arbor, Mich., 1974.
• 11: Hayes-Roth, F. Uniform representations of structured patterns and an algorithm for the induction of contingency-response rules. Inform. and Control, 33 (1977), 87-116.
• 12: Hayes-Roth, F. Patterns of induction and associated knowledge acquisition algorithms. In Pattern Recognition and Artificial Intelligence, C. Chen, Ed., Academic Press, New York, 1976.
• 13: Hayes-Roth, F., and Burge, J. Characterizing syllables as sequences of machine-generated labelled segments of connected speech: A study in symbolic pattern learning using a conjunctive feature learning and classification system. Proc. Third Int. Joint Conf. Pattern Recognition, 1976, pp. 431-435.
• 14: Hayes-Roth, F., Erman, L.D., Fox, M., and Mostow, D.J. Syntactic processing in Hearsay-II. In Speech Understanding Systems: Summary of Results of the Five-Year Research Effort. Dept. of Comptr. Sci., Carnegie-Mellon U., Pittsburgh, Pa., 1976.
• 15: Hayes-Roth, F., and McDermott, J. Knowledge acquisition from structural descriptions. P-5910, Rand Corp., Santa Monica, Calif., 1976.
• 16: Hirschman, L., Grishman, R., and Sager, N. Gramatically-based automatic word class formation. Inform. Proc. and Manage., 11 (1975), 39-57.
• 17: Minskey, M. A framework for representing knowledge. In The Psychology of Computer Vision, P.H. Winston, Ed., McGraw-Hill, New York, 1975.
• 18: Moore, J., and NeweU, A. How can Merlin understand? In Knowledge and Cognition, L.W. Gregg, Ed., Erlbaum, New York, 1974.
• 19: Plotkin, G.D. A note on inductive generalization. In Machine Intelligence 5, B. Meltzer and D. Michie, Eds., American Elsevier, New York, 1970.
• 20: Plotkin, G.D. A further note on inductive generalization. In Machine Intelligence 6, B. Meltzer and D. Michie, Eds., American Elsevier, New York, 1971.
• 21: Reed, S.K., Ernst, G.W., and Banerji, R. The role of analogy in transfer between problem states. Cognitive Psychology 6 (1974), 436-450.
• 22: Tretiakoff, A. Computer-generated word classes and sentence structures. Information Processing 74, Proc. IFIP Congress 1974, North-Holland Pub. Co., Amsterdam, pp.
• 23: Vere, S.A. Induction of concepts in the predicate calculus. Proc. Fourth Int. Joint Conf. Artif. Intell., 1975, pp. 281-287.
• 24: Winston, P.H. Learning structural descriptions from examples. In The Psychology of Computer Vision, P.H. Winston, Ed., McGraw-Hill, New York, 1975.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Induction

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Knowledge acquisition

General Terms:
Algorithms, Design, Management, Performance, Theory

Keywords:
abstraction, complexity, generalization, graph matching, induction, informal retrieval, interference, knowledge acquisition, knowledge representation, language learning, learning, partial matching, predicate discovery, rule induction