Generalized Notions of Mind Change Complexity

Arun Sharma, Frank Stephan, Yuri VentsovCOLT 1997 · DOI

TL;DR

This paper introduces a more generalized framework for understanding the "mind change complexity" of learning algorithms, moving beyond fixed bounds to more flexible ordinal and partially ordered sets. This work offers a richer understanding of learning efficiency and provides new characterizations for when learning is possible, particularly for computable functions.

What Problem Does This Paper Address?

In machine learning, a fundamental question is how efficiently a learner can identify a concept (like a pattern or a function). A common model, "identification in the limit" (Ex-identification), focuses on whether a learner eventually converges to the correct concept. However, this model doesn't account for how fast it converges. To address this, researchers introduced "mind change complexity," which bounds the number of times a learner has to revise its hypothesis before it settles on the correct one.

Early approaches used simple constant bounds (e.g., "at most 5 mind changes"). While intuitive, this is too rigid: complex concepts might naturally require more revisions than simple ones. To overcome this, constructive ordinals were introduced, allowing for more dynamic bounds (e.g., "at most ω + 2w mind changes"). This paper asks: can we generalize even further? They propose moving beyond well-ordered sets (like ordinals) to linearly and partially ordered sets, creating a hierarchy of learning complexity.

Methods

The core of this paper is the introduction of four generalized notions of mind change bounds, defined by the set of values a "mind change counter" can take:

  1. Type 1: Constant Bound: The counter takes values from a finite set (e.g., {0, 1, ..., c}). This is the traditional approach.
  2. Type 2: Ordinal Bound: The counter takes values from a well-ordered set (no infinite descending chains). This is the established ordinal-based approach.
  3. Type 3: Linear Bound: The counter takes values from a linearly ordered set that does not contain any infinite descending recursive sequences. This is a new, more flexible notion.
  4. Type 4: General Bound: The counter takes values from a partially ordered set that does not contain any infinite descending recursive sequences. This is the most general notion introduced.

The authors then investigate the relationships between these types, showing they form a hierarchy (Type 1 < Type 2 < Type 3 < Type 4). They also explore characterizations of these bounds, particularly for Type 2 and Type 4, linking them to the ability of a learner to converge on all computable functions, or even all recursive or non-recursive functions. They also extend these notions to "behaviorally correct" (BC) learning, which is a more semantic version of convergence.

Datasets

Not discussed in the paper. The paper focuses on theoretical concepts and learning algorithms rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • A Hierarchy of Learning Complexity: The paper establishes a clear hierarchy: constant bounds are the most restrictive, followed by ordinal bounds, then linear bounds, and finally partially ordered bounds are the most general. This means a class learnable with a Type 1 bound is also learnable with Types 2, 3, and 4, but not necessarily vice-versa.
  • Generalization Matters: The introduction of linear and partially ordered sets for mind change counters significantly expands the theoretical landscape of learnability. This allows for more nuanced analysis of learning efficiency.
  • Computability is Key: A striking result is that a class of functions can be learned with a Type 4 (most general) mind change bound if and only if it can be learned by a learner that converges on every computable function. This connects the abstract notion of mind change complexity directly to the fundamental concept of computability.
  • Hypothesis Space Trade-offs: The choice of hypothesis space (the set of possible concepts a learner can output) can influence mind change complexity. A richer hypothesis space can sometimes reduce the number of mind changes required, offering a practical insight for designing learning systems.
  • BC Learning Equivalence: The paper shows that for BC learning, the characterizations for Type 2 and Type 4 bounds are surprisingly similar to those for Ex-identification, highlighting the robustness of these generalized notions.

Key Results

  • Hierarchy Established: Type 1 ⊂ Type 2 ⊂ Type 3 ⊂ Type 4 (where ⊂ denotes "is strictly more restrictive than").
  • Type 4 Equivalence: A class S is learnable with a Type 4 mind change bound iff it can be learned by a learner that converges on every computable function.
  • Type 2 Equivalence: A class S is learnable with a Type 2 mind change bound iff it can be learned by a learner that converges on every recursive or non-recursive function.
  • Type 3 Characterization (Partial): A sufficient condition for Type 3 learnability is that the learner converges on every function computable relative to the halting problem (K). A necessary condition is that the learner converges on every function of hyperimmune-free Turing degree.

Limitations and Future Work

  • Type 3 Characterization Incomplete: The paper notes that a "nice" characterization for Type 3 bounds (linear bounds) is missing, though sufficient and necessary conditions are provided. This suggests further theoretical work could refine our understanding of this intermediate complexity class.
  • Language Learning: While the paper mentions extending the framework to language learning, the detailed results are primarily focused on function learning due to space constraints. Further exploration of language learning with these generalized bounds would be valuable.
  • Empirical Validation: The paper is theoretical. Future work could explore how these generalized mind change bounds manifest in practical learning algorithms and whether they offer tangible benefits in real-world applications.

Summary updated

BibTeX
@inproceedings{sharma1997generalized,
  author = {Arun Sharma and Frank Stephan and Yuri Ventsov},
  title = {{Generalized Notions of Mind Change Complexity}},
  booktitle = {Conference on Learning Theory},
  year = {1997},
  doi = {10.1145/267460.267485},
}

Loading related content...

Figure