Contrastive learners identify languages from positive data alone

A Reverse-Gold Theorem: Positive-Data Identification by Substrate-Bounded Contrastive Learners

Computation and LanguageMachine Learning

Summary

This paper tackles a known challenge in language learning: how to figure out the rules of a language by only looking at correct examples. The authors present a method where a learning tool creates subtle changes to these examples itself and uses these to teach a ranking system to tell real examples from altered ones. This approach, under certain conditions, lets the system reliably identify languages using only positive samples, without needing examples of mistakes or complex calculations. They prove this works for specific language types and discuss potential extensions.

What this means in practice

  • For natural language processing engineers: Design language models that learn grammar patterns using only correct sentence examples without requiring negative samples or labeled errors.
  • For computational linguists: Develop algorithms to classify languages or grammatical structures based solely on positive data and internally generated perturbations.

A theory result. No direct application yet.

Authors

Rakesh Sengupta

Abstract

Gold's theorem shows that no learner can identify an arbitrary language in a superfinite class from positive presentations alone. We prove a positive result of a different shape. Fix an innate \emph{recursive contrast operator} $R$ mapping any string to a finite set of structurally bounded perturbations of it, and a discriminative scorer of bounded capacity trained by InfoNCE-style contrastive estimation \citep{vandenoord2018,macollins2018} on self-generated perturbations. Under a faithfulness condition relating operator, scorer, and target, the trained scorer achieves \emph{PAC conditional identification} from positive data alone: with high probability it ranks all but an $\varepsilon$-fraction of positives above every out-of-language perturbation in their own orbit, with sample complexity polynomial in the capacity, the orbit size, the score bound, and $1/\varepsilon$. The negatives are constructed by the learner, not supplied by an oracle, and no global normalizing constant over strings is ever computed. The misranking bound follows from the geometry of the contrastive loss---per-example loss floors plus a definite loss increment under misranking---yielding an $\varepsilon^{-2}$ rate, together with an explicit approximation gap that quantifies the cost of in-language (``colliding'') perturbations and vanishes for orbit-pure operators. The ranking guarantee lifts to a global membership classifier under a margin condition, and the same operator composed with the learned scorer is a normalization-free Metropolis--Hastings generator. We instantiate the hypotheses for substitutable context-free languages \citep{clarkeyraud2007} and the subregular classes \citep{heinz2010,hayashikamigaito2025}, and state an open conjecture locating the construction in the mildly context-sensitive hierarchy.