Generalization versus classification

ABSTRACT

Generalization is a learning problem that has received considerable attention. The generalization problem is to take a finite sample of some concept and produce an algorithm that can produce all other (perhaps infinitely many) samples of the same concept. Inductive inference is the study of this problem in a most general framework [1]. The classification problem is to take a finite sample of some concept and decide which type of concept the sample is from. The choice of type is usually finite. If the mechanism performing the classification is limiting, e.g., it makes more and more conjectures as to a classification as time goes on, then the process can also be considered as a type of learning. Roughly, we will say that some suitable mechanism has learned an appropriate classification if its sequence of conjectures stabilizes at some point. In this paper we formalize, at a suitable level of abstraction, the classification problem and rigorously compare it to the generalization problem. Despite some obvious similarities, the two notions are shown to be distinct. The new formalism of classification is investigated further.

REFERENCES

• 1: Dana Angluin , Carl H. Smith, Inductive Inference: Theory and Methods, ACM Computing Surveys (CSUR), v.15 n.3, p.237-269, Sept. 1983 [doi>10.1145/356914.356918]
• 2: BLUM, L. AND BLUM, M. Toward a mathematical theory of inductive inference. Information and Control 28 (1975), 125-155.
• 3: CASE, J. AND SMtTH, C. Comparison of identification criteria for machine inductive inference. Theoretical Computer Science 25, 2 (1983), 193- 220.
• 4: Erwin Engeler, Introduction to the Theory of Computation, Academic Press, Inc., Orlando, FL, 1973
• 5: Fm~IVALDS, R. V. AND WIU, HAGEN, R. Inductive inference with additional information. Elektronische Informationsverabeitung und Kybernetik 15,4 (1979), 179-184.
• 6: GOLD, E. M. Language identification in the limit. Information and Control 10 (1967), 447- 474.
• 7: Michael Machtey , Paul Young, An Introduction to the General Theory of Algorithms, Elsevier Science Inc., New York, NY, 1978
• 8: MINICOZZI, E. Some natural properties of strongidentification in inductive inference. Theoretical Computer Science 2 (1976), 345-360.
• 9: RtCE, H. On completely recursively enumerable classes and their key arrays. Journal of Symbolic Logic 21 (1956), 304-308.
• 10: Hartley Rogers, Jr., Theory of recursive functions and effective computability, MIT Press, Cambridge, MA, 1987
• 11: ROSE, G. AND ULLIAN, J. Approximations of functions on the integers. Pacific Journal of Mathematics 13 (1963), 693-701.
• 12: Robert I. Soare, Recursively enumerable sets and degrees, Springer-Verlag New York, Inc., New York, NY, 1987

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

General Terms:
Theory, Verification