Must the learner make no mistakes?

No. It may revise incorrect hypotheses before stabilization.

Does the criterion guarantee a known sample size?

No. A separate bound would need to be established.

Is this the same as high prediction accuracy?

No. The criterion concerns eventual stable identification of the target, not an accuracy percentage on a finite test set.

AI Glossary / Graphs and symbolic AI / Advanced

Identification in the limit

Definition

Identification in the limit is a criterion for learning success in which a learner eventually settles on a correct hypothesis and never changes it afterward. Stabilization must occur after finitely many observations, although the learner need not know when it has happened. The criterion is associated with E. Mark Gold's work on language learning.

What it means

A learner receives evidence over time and repeatedly proposes an explanation. Early guesses may be wrong, and revisions are allowed. Success means that there is a point beyond which every guess is the same correct hypothesis.
This is stronger than merely producing a correct guess once. It also differs from announcing, with a certificate, that learning is finished. A system can meet the convergence criterion without possessing a reliable stopping test.
The claim depends on a specified class of possible targets and a specified method of presenting information.

How it works

The learning problem defines the permitted hypotheses, the evidence available at each step, and the presentations on which the learner must succeed. After each finite prefix of the evidence, the learner outputs a hypothesis. A class-level guarantee requires eventual correct stabilization for every target in the class and every presentation allowed by the model.
Correctness is about the target itself, not just agreement with examples already seen. Many hypotheses may explain the same finite prefix.
The definition alone gives no practical deadline for convergence. It does not supply a runtime bound, a required sample size, or a probability that the present hypothesis is correct.

Three practical examples

Grammar-learning analysis: A researcher studies whether a learner can eventually recover a grammar describing a target language from the permitted example stream. The conclusion depends on the language class and on whether the stream provides enough distinguishing information.
Rule-discovery prototypes: A team investigates a simplified family of operational rules before deploying a learning system. An eventual-learning argument can reveal the role of its assumptions, but cannot replace finite-data evaluation on real records.
Test design: An evaluator deliberately delays a distinguishing example while repeating familiar ones. This exposes the difference between a hypothesis that has remained unchanged for a long time and a hypothesis known to be correct.

Think of it this way

Imagine repeatedly updating a guest list as invitations arrive. Eventually every guest may have been revealed and the list may stop changing forever. Yet, without a notice saying the list is complete, a long quiet period does not prove another name will never arrive.

Worked example

Use a deliberately simple target class: all nonempty finite sets of positive integers, with a fixed target. The data stream contains only members of the target set, repeats are allowed, and every target member must eventually appear.
Let the learner's hypothesis after each observation be exactly the set of distinct integers seen so far, written in increasing order. Suppose the target is {2, 5, 9} and the stream begins 5, 2, 5, 9, 2, 9, 5, followed by further repetitions of those values.
After observation 1, the hypothesis is {5}. After observation 2, it becomes {2, 5}. Observation 3 leaves it unchanged. Observation 4 produces {2, 5, 9}, and all subsequent observations leave it unchanged.
Why does the rule work for every permitted target and stream in this class? Each target member has a finite first-appearance position. There are only finitely many members, so the largest of those positions is finite. After that position, every member has been seen and no outside member can appear. The observed set is therefore correct forever.
But the learner cannot certify completion from the displayed prefix alone. The same prefix could begin a permitted stream for {2, 5, 9, 12}, with 12 appearing much later. Any finite run of repetitions can be followed by that new member.
There is also no uniform observation deadline over these permitted streams. Even for target {2, 5, 9}, the first appearance of 9 can be delayed arbitrarily long. If the target were an infinite set, the same observed-set learner would keep acquiring new elements and would not stabilize. That case lies outside the chosen class.

Illustrative case study

Fictional Maple Rules experiments with a learner for a restricted collection of accepted message codes. A demonstration stops changing its proposed code set after a few hundred records, and an early report describes the rule as “fully learned.”
A reviewer separates two questions: whether the learner eventually converges under the toy model, and whether the present operational data justify a completion claim. Historical records may omit rare codes, include errors, or reflect changes to the accepted set.
The team revises the report to state the model assumptions and evaluates held-out and deliberately delayed examples. It treats eventual convergence as a theoretical property of the specified setting, while reporting current performance and unresolved coverage separately.

Common misconceptions and mistakes

“Convergence means the learner knows it is finished.” A reliable stopping signal is not required.
“A long period without revisions proves correctness.” New distinguishing evidence may still arrive.
“One successful stream proves the class is learnable.” The guarantee must cover all presentations required by the model.
“Eventually correct means quickly useful.” No practical speed bound follows from the criterion alone.
“The proof survives noisy or changing targets automatically.” Those conditions require a different or extended analysis.

Business use

Use the concept to examine what information a learning approach needs and what its theoretical guarantee actually says. Ask which target family is covered, what evidence can appear, whether important cases must eventually be observed, and whether the target is assumed to remain fixed.
Keep deployment decisions tied to finite evidence, operational requirements, and the consequences of errors. A convergence theorem does not state that a particular production model has already reached the correct hypothesis.

Check your understanding

When does the example stabilize?

Answer: At observation 4, when 9 first appears.

Why can the learner not certify completion there?

Answer: A larger finite target could produce the same prefix.

Which assumption makes eventual coverage possible?

Answer: Every member of the fixed finite target eventually appears.

Related terms

Hypothesis
Formal language
Convergence
Sample complexity
Concept drift
Inductive inference
grammar learning
learnability

Learn next

Delay the final unseen member in the example and track the learner's guesses. Then remove the eventual-coverage assumption and identify exactly which step of the convergence argument no longer holds.

Convergence

Sources

AIMA glossary, identification in the limit: https://github.com/aimacode/aima-glossary/blob/master/glossary.md E. Mark Gold, Language identification in the limit, original publication abstract: https://www.sciencedirect.com/science/article/pii/S0019995867911655

Previous: Identifiability analysis Next: Identification (information)