5.5 Mind-Change Complexity
Gold’s impossibility theorem tells us that certain classes cannot be identified at all. For classes that can be identified, a natural quantitative question arises: how many times must the learner change its mind before converging?
Lean: EXLearnable
A mind change occurs at time \(n\) if the learner’s output satisfies \(M(t_0, \ldots , t_n) \neq M(t_0, \ldots , t_{n-1})\). The mind-change count of \(M\) on text \(t\) is the number of times \(M\) changes its hypothesis.
For finite mind-change bounds, the theory is straightforward: we say that \(M\) identifies \(\mathcal{L}\) with at most \(k\) mind changes if, on every text for every \(L \in \mathcal{L}\), the mind-change count is at most \(k\). The class of all finite languages is identifiable with 0 mind changes after the first hypothesis (the learner in Example 5.3 changes its mind every time a new element appears, but a more careful learner can be designed with bounded mind changes for restricted subclasses).
The surprise, genuinely unexpected for readers coming from PAC theory, is that integer-valued bounds are not sufficient to characterize the full landscape.
Lean: mind_change_characterization
The mind-change complexity of \(\mathbf{Ex}\)-identification is naturally measured by countable ordinals. Specifically:
For every countable ordinal \(\alpha \), one can define what it means for a learner to identify a class with mind-change bound \(\alpha \).
There exist classes identifiable with mind-change bound \(\omega \) (the first infinite ordinal) that cannot be identified with any finite mind-change bound.
More generally, for every ordinal \(\alpha {\lt} \omega _1\), there exist classes identifiable with mind-change bound \(\alpha \) but not with any bound \(\beta {\lt} \alpha \).
The idea behind ordinal mind-change bounds is as follows. A learner with mind-change bound \(\omega \) begins with an ordinal counter set to \(\omega \). At each mind change, the counter must decrease, but it may decrease to any smaller ordinal. Since there is no infinite descending sequence of ordinals (ordinals are well-ordered), the learner must eventually stop changing its mind. The counter \(\omega \) allows finitely many mind changes, but the number of mind changes need not be bounded in advance by any fixed integer, it may depend on the input.
This is fundamentally different from an integer bound. With a bound of \(k \in \mathbb {N}\), the learner may change its mind at most \(k\) times on every input. With a bound of \(\omega \), the learner may change its mind \(k\) times for input-dependent \(k\), with no uniform finite upper bound. The ordinal hierarchy continues: \(\omega \cdot 2\) allows the learner to “reset” its finite counter once; \(\omega ^2\) allows nested levels of resetting; and so on up through the constructive ordinals.
The appearance of transfinite ordinals in learning theory is a genuine structural surprise. PAC learning theory uses real-valued parameters (\(\varepsilon , \delta , m(\varepsilon , \delta )\)). Online learning uses integer-valued dimensions (\(\mathrm{Ldim}\)). Gold-style learning requires ordinal-valued complexity measures. Each proof technique brings its own number system. The full development of ordinal mind-change complexity is deferred to the companion textbook’s Chapter 13 (Mind-Change Ordinals), 1 where it interacts with the constructive ordinal notation systems of Kleene.
Path: \(\textsf{\small mind\_ change\_ characterization} \xrightarrow {\texttt{\small measures}} \textsf{\small ex\_ learning}\).
The mind-change ordinal is a complexity measure on \(\mathbf{Ex}\)-identifiable classes, analogous to the VC dimension for PAC-learnable classes. But where VC dimension is a single integer, mind-change complexity is an ordinal, potentially transfinite. This is a measures edge of a qualitatively different kind than \(\textsf{\small vc\_ dimension} \xrightarrow {\texttt{\small measures}} \textsf{\small concept\_ class}\).