Pattern Recognition Theory

Origin. Soviet pattern recognition school; foundational work by Bongard ("Pattern Recognition," 1967), Aizerman, Braverman, and Rozonoer (potential functions), Vapnik and Chervonenkis (VC theory, statistical learning).

Mechanism. Recognize patterns by learning from examples. The Bongard problems posed visual pattern recognition as analogy: given examples of class A and class B, identify what distinguishes them. The potential function method generalized perceptrons to nonlinear classification using kernel functions. VC theory provided the mathematical foundation for generalization: what can be learned from finite samples, and how much data is needed.

Procedure. Collect labeled examples. Choose a hypothesis class (linear classifiers, polynomials, potential functions). Train by minimizing error on the training set, with regularization to control complexity. Evaluate on held-out data. VC dimension guides the trade-off between fit and generalization: a class with high VC dimension can fit anything but generalizes poorly; low VC dimension generalizes well but may underfit.

Applies to. Classification, recognition, any domain where patterns must be learned from examples.

Limitations. The theory assumes i.i.d. data; if the test distribution differs from training, guarantees fail. High-dimensional data requires either strong assumptions (linear separability) or massive data. The Soviet theoretical work was mathematically rigorous but computation was limited; the practical implementation awaited later hardware.