Language identification in the limit #
A learner sees the strings of an unknown language one at a time, in any order, with repetitions and pauses, and after each presentation conjectures a language. It identifies the language in the limit if on every such presentation its conjectures are eventually the language itself. A class of languages over a countable set of strings is identifiable exactly when it is countable and its languages have telltales, a telltale of a language being a finite subset that no member of the class properly inside the language contains. Hence no class containing an infinite language and all its finite subsets is identifiable, nor any class containing a strictly increasing chain of languages and its union.
Implementation notes #
The characterization is the ineffective one: a learner is any function on finite sequences, computable or not, and conjectures a language rather than a name for one, the two coming to the same when effectiveness is not required. Effective inference of an indexed family of recursive languages further needs the telltales to be uniformly enumerable, which is not formalized. A pause lets the empty language have a text; on nonempty languages pauses change nothing, since a learner can treat a pause as a repetition of the previous string. The strings form an arbitrary countable type, the words over an alphabet being one instance.
References #
A text presents strings one at a time, none being a pause in which nothing is
presented.
Equations
- InductiveInference.Text α = Stream' (Option α)
Instances For
The strings occurring in a finite sequence of presentations.
Equations
- InductiveInference.content σ = {x : α | some x ∈ σ}
Instances For
The strings occurring in a text. A text for L is one whose content is L.
Equations
- t.content = {x : α | some x ∈ t}
Instances For
A learner conjectures a language from each finite sequence of presentations.
Equations
- InductiveInference.Learner α = (List (Option α) → Set α)
Instances For
φ identifies L in the limit when on every text for L its conjectures are
eventually L.
Equations
- InductiveInference.Identifies φ L = ∀ (t : InductiveInference.Text α), t.content = L → ∀ᶠ (n : ℕ) in Filter.atTop, φ (Stream'.take n t) = L
Instances For
A class of languages is identifiable in the limit when one learner identifies each of its languages.
Equations
- InductiveInference.Identifiable 𝓛 = ∃ (φ : InductiveInference.Learner α), ∀ L ∈ 𝓛, InductiveInference.Identifies φ L
Instances For
T is a telltale of L in 𝓛: a finite subset of L that no language of 𝓛 properly
inside L contains. Once T has been presented, conjecturing L cannot overgeneralize.
Equations
- InductiveInference.IsTelltale 𝓛 L T = (T.Finite ∧ T ⊆ L ∧ ∀ L' ∈ 𝓛, T ⊆ L' → ¬L' ⊂ L)
Instances For
Content #
Every finite set is the content of a finite sequence.
Every finite part of a text has been presented after finitely many steps.
Every language over a countable set of strings has a text.
If a property of finite sequences can always be reached by extending within L, some text for
L meets it infinitely often: the text the proofs of Gold and of Angluin build.
The characterization #
A learner identifying each language of 𝓛 gives each of them a telltale, the content of a
finite sequence after which it can no longer be moved off L.
A countable class whose languages have telltales is identifiable, by conjecturing the first language in an enumeration whose telltale has appeared and which contains the data.
A class of languages over a countable set of strings is identifiable in the limit exactly when it is countable and each of its languages has a telltale. Angluin's condition without its effectiveness requirement, and Gold's observation that only countably many conjectures exist.
Every finite class is identifiable.
Gold's theorem: a class containing an infinite language and all its finite subsets is not identifiable from text. In particular no class containing every finite language and an infinite one is.
A class containing a strictly increasing chain of languages and its union is not identifiable from text, since the finite telltale of the union would already lie in a member of the chain.