Abstract
In the late 1980s, the "Probably Approximately Correct" (PAC) learning framework, pioneered by Leslie Valiant, provided a rigorous mathematical foundation for machine learning. However, Jonathan Amsterdam’s critique, "Some Philosophical Problems with Formal Learning Theory," argues that this framework relies on assumptions that diverge significantly from the realities of human cognition and the requirements of general intelligence. By examining the distribution of data, the bivalence of categories, and the interconnected nature of knowledge, Amsterdam suggests that formal learning theory captures recognition shortcuts rather than true conceptual understanding.
Introduction
Valiant’s "Theory of the Learnable" revolutionized artificial intelligence by introducing a framework that prioritized polynomial-time efficiency and statistical confidence. While this approach has been immensely successful for specific classification tasks, it operates under a set of constraints that Amsterdam finds philosophically problematic. The PAC model assumes that concepts are binary, defined by finite feature sets, and can be learned in isolation. This paper explores the tensions between these formal requirements and the messy, "fuzzy," and interconnected nature of real-world knowledge.
The Distribution Problem: Learning vs. Recognition
A central tenet of formal learning theory is that a learner succeeds if it performs well on data drawn from the same distribution as its training set. Amsterdam argues that this focus on "naturally occurring" data conflates recognition with understanding.
Consider a robot trained to identify "bachelors." If the robot relies on a high-correlation shortcut—such as identifying unmarried men who do not wear wedding rings—it might achieve high accuracy on a standard dataset. However, if it fails to recognize a hypothetical "unmarried male wearing a wedding ring" as a bachelor, it has not truly learned the concept. True understanding requires the ability to handle rare or hypothetical cases that fall outside the typical training distribution. Formal models often prioritize extensional equivalence (getting the right answer on a specific set) over intensional understanding (grasping the underlying meaning).
The Bivalence Problem and the Ontological Critique
Formal models typically assume bivalence: an object either belongs to a category or it does not. Amsterdam challenges this by drawing on prototype theory from cognitive psychology. In human cognition, concepts are often "fuzzy." For instance, a robin is frequently viewed as a "better" or more typical example of a bird than a penguin.
Furthermore, the "Ontological Critique" suggests that many empirical concepts lack a finite set of necessary and sufficient conditions. Using the example of "seedless grapes," Amsterdam points out that factors like genetic anomalies or environmental interference mean that no static list of sensory features can perfectly define the category. Formal learning theory’s search for a fixed, binary definition clashes with the graded and dynamic nature of human categories.
The Single-Concept Trap and the Web of Belief
Most formal theories focus on the acquisition of a single concept in isolation. Amsterdam argues that this is a fundamental misunderstanding of how knowledge is structured. Following philosopher W.V.O. Quine, he posits that concepts exist within a "web of belief" where they are interdefined.
In language acquisition, for example, children do not learn nouns, verbs, and syntax in a linear, isolated fashion. Instead, they engage in "semantic bootstrapping," using partial knowledge of one category to help define another. This piecemeal, simultaneous acquisition contradicts the isolated focus of PAC learning. Learning a new concept often necessitates the revision of existing ones, suggesting that learning is a process of theory formation and holistic revision rather than a simple search through a version space.
Conclusion
While Amsterdam acknowledges that single-concept learning models serve as useful modules for simple tasks, he concludes they cannot scale up to general intelligence. The path forward requires a shift away from models seeking static, definable concepts and toward "theory-construction models" where multiple concepts interact dynamically. By incorporating statistical techniques that allow for accurate hypotheses without assuming perfect underlying definitions, AI research may move closer to capturing the flexible and interconnected nature of human thought.
Summary updated