Learnability and Positive Equivalence Relations

David Belanger, Ziyuan Gao, Sanjay Jain, Wei Li, Frank Stephan

TL;DR

This paper explores how the "rules of equality"—mathematically defined as positive equivalence relations—shape the limits of what an algorithm can learn from data. The authors demonstrate that while some learning hierarchies are universal, specific equivalence relations can cause different learning models to collapse into one another or even become impossible.

What Problem Does This Paper Address?

In the classic "learning in the limit" framework (introduced by E. Mark Gold), a learner receives a stream of positive examples and must eventually converge on a correct hypothesis. Usually, we assume a standard world where numbers are just numbers. However, in many algebraic and logical structures, "equality" is more complex. For example, in provable equivalence (like in Peano Arithmetic), two different formulas might represent the same underlying truth.

The authors ask: How does the underlying equivalence relation ($\eta$) of a domain affect the hierarchy of learnability?

In a standard world, there is a strict hierarchy of learning criteria:

  1. Finite (Fin): Learn it in one shot.
  2. Confident (Conf): Always converge to a hypothesis, even if the data is "garbage" (not in the class).
  3. Explanatory (Ex): Eventually settle on a single correct hypothesis.
  4. Vacillatory (Vac): Eventually oscillate between a finite set of correct hypotheses.
  5. Behaviourally Correct (BC): Eventually, every hypothesis is correct, but they might all be different "names" for the same thing.

The paper investigates whether these gaps ($Fin \subset Conf \subset Ex \subset Vac \subset BC$) hold up when the data is grouped by different types of positive (recursively enumerable) equivalence relations.

Methods

The paper is a theoretical study using tools from recursion theory and formal learning theory. The authors construct specific families of sets (called $\eta$-families) and use diagonalisation arguments to prove the existence or non-existence of learners.

Key techniques include:

  • The Ascending Family: A construction used to show that for any positive equivalence relation, there are things that can be learned in the limit but cannot be learned "confidently."
  • Pathological Relations: The authors construct two special equivalence relations, $\vartheta$ and $\zeta$, to test the boundaries of the hierarchy.
  • Kummer’s Theorem: Used to ensure that the complex families they construct can be indexed in a "one-one" fashion (where every set has exactly one unique index).

Datasets

Not discussed in the paper. As a theoretical computer science paper, it relies on formal mathematical proofs rather than empirical benchmarks or datasets.

Key Insights and Ideas

  • Universal Gaps: Some things never change. Regardless of the equivalence relation chosen, there will always be families that are "Behaviourally Correct" learnable but not "Vacillatorily" learnable. The jump from settling on one answer to eventually being "always right but changing your mind on the name" is a fundamental gap.
  • The Collapse of Vacillation: The authors discovered a specific equivalence relation ($\vartheta$) where the power of "vacillating" disappears. In this world, if you can learn something by oscillating between a few correct answers, you could have just as easily settled on one. Here, $Vac = Ex$.
  • The Death of Confidence: Under that same relation $\vartheta$, "Confident" learning becomes impossible (void). No non-trivial family can be learned if the learner is required to converge on every possible input string.
  • The Non-Union Property: Learning is sensitive to how classes are combined. The authors prove that for any equivalence relation, you can find two learnable families whose union is impossible to learn. This extends a famous result by Gold to these more complex "worlds."

Key Results

  • Universal Separations: For every positive equivalence relation $\eta$, the authors proved the existence of families that satisfy:
  • (a) $BC$ learnable but not $Vac$ learnable.
  • (b) $Ex$ learnable but not $Conf$ learnable.
  • (c) Not $BC$ learnable at all.
  • The $\vartheta$ Case: They proved there exists a relation $\vartheta$ where every $Vac$ learnable family is also $Ex$ learnable, and no family is $Conf$ learnable.
  • The $\zeta$ Case: They proved there exists a relation $\zeta$ where $Conf$ learning is possible, but $Fin$ (one-shot) learning is not.
  • Union Closure: They characterized exactly when $BC$ learning is closed under union: it only happens if the world is "simple" enough to have only one infinite r.e. set (the set of all natural numbers).

Limitations and Future Work

The authors acknowledge that their results primarily focus on one-one numbered families (where each set has a unique ID). They suggest that future research should investigate:

  • Arbitrary r.e. families: Does the collapse of Vacillatory to Explanatory learning still hold if sets can have multiple IDs?
  • $\eta$-singletons: Exploring a new level of the hierarchy where the learner only needs to identify a single equivalence class.
  • Structural Generalization: Moving beyond natural numbers to more general algebraic structures.

Summary updated

Abstract

Prior work of Gavryushkin, Khoussainov, Jain and Stephan investigated what algebraic structures can be realised in worlds given by a positive (= recursively enumerable) equivalence relation which partitions the natural numbers into infinitely many equivalence classes. The present work investigates the infinite one-one numbered recursively enumerable (r.e.) families realised by such relations and asks how the choice of the equivalence relation impacts the learnability properties of these classes when studying learnability in the limit from positive examples, also known as learning from text. For all choices of such positive equivalence relations, for each of the following entries, there are one-one numbered r.e. families which satisfy it: (a) they are behaviourally correctly learnable but not vacillatorily learnable; (b) they are explanatorily learnable but not confidently learnable; (c) they are not behaviourally correctly learnable. Furthermore, there is a positive equivalence relation which enforces that (d) every vacillatorily learnable one-one numbered family of languages closed under this equivalence relation is already explanatorily learnable and cannot be confidently learnable.
BibTeX
@inproceedings{belanger2021learnability,
  author = {David Belanger and Ziyuan Gao and Sanjay Jain and Wei Li and Frank Stephan},
  title = {{Learnability and Positive Equivalence Relations}},
  booktitle = {LATA},
  year = {2021},
  url = {https://openreview.net/forum?id=aMFBDC9hz7c},
}
Figure