language identification in the limit

This model is an early attempt to formally capture the notion of learnability.

Gold's journal articlep.457 introduces for contrast the stronger models

• Finite identification (where the learner has to announce correctness after a finite number of steps), and
• Fixed-time identification (where correctness has to be reached after an apriori-specified number of steps).

A weaker formal model of learnability is the Probably approximately correct learning (PAC) model, introduced by Leslie Valiant in 1984.

{{clear}}

It is instructive to look at concrete examples (in the tables) of learning sessions the definition of identification in the limit speaks about.

1. A fictitious session to learn a regular language L over the alphabet {a,b} from text presentation:
   In each step, the teacher gives a string belonging to L, and the learner answers a guess for L, encoded as a regular expression."A+B" contains all strings that are in A or in B; "AB" contains all concatenations of a string in A with a string in B; "A^*" contains all repetitions (zero or more times) of strings in A; "ε" denotes the empty string; "a" and "b" denote themselves. For example, the expression "(ab+ba)^*" in step 7 denotes the infinite set { ε, ab, ba, abab, abba, baab, baba, ababab, ababba, ... }. In step 3, the learner's guess is not consistent with the strings seen so far; in step 4, the teacher gives a string repeatedly. After step 6, the learner sticks to the regular expression (ab+ba)^*. If this happens to be a description of the language L the teacher has in mind, it is said that the learner has learned that language.
   If a computer program for the learner's role would exist that was able to successfully learn each regular language, that class of languages would be identifiable in the limit. Gold has shown that this is not the case.Theorem I.8,I.9, p.470-471
2. A particular learning algorithm always guessing L to be just the union of all strings seen so far:
   If L is a finite language, the learner will eventually guess it correctly, however, without being able to tell when. Although the guess didn't change during step 3 to 6, the learner couldn't be sure to be correct.
   Gold has shown that the class of finite languages is identifiable in the limit,Theorem I.6, p.469 however, this class is neither finitely nor fixed-time identifiable.
3. Learning from complete presentation by telling:
   In each step, the teacher gives a string and tells whether it belongs to L ({{color|green|green}}) or not ({{color|red|red, struck-out}}). Each possible string is eventually classified in this way by the teacher.
4. Learning from complete presentation by request:
   The learner gives a query string, the teacher tells whether it belongs to L ({{color|green|yes}}) or not ({{color|red|no}}); the learner then gives a guess for L, followed by the next query string. In this example, the learner happens to query in each step just the same string as given by the teacher in example 3.
   In general, Gold has shown that each language class identifiable in the request-presentation setting is also identifiable in the telling-presentation setting,Theorem I.3, p.467 since the learner, instead of querying a string, just needs to wait until it is eventually given by the teacher.

More formally,{{Cite journal |last=Johnson |first=Kent |date=October 2004 |title=Gold's Theorem and Cognitive Science |url=https://www.cambridge.org/core/journals/philosophy-of-science/article/abs/golds-theorem-and-cognitive-science/046D4E968548BBAF6059FC155AD26FDF |journal=Philosophy of Science |language=en |volume=71 |issue=4 |pages=571–592 |doi=10.1086/423752 |s2cid=5589573 |issn=0031-8248}}

• a language $L$ is a nonempty set, and its elements are called sentences.
• a language family is a set of languages.
• a language-learning environment $E$ for a language $L$ is a stream of sentences from $L$, such that each sentence in $L$ appears at least once.
• a language learner is a function $f$ that sends a list of sentences to a language.
• This is interpreted as saying that, after seeing sentences $a\_1,\; a\_2...,\; a\_n$ in that order, the language learner guesses that the language that produces the sentences should be $f(a\_1,\; ...,\; a\_n)$.
• Note that the learner is not obliged to be correct — it could very well guess a language that does not even contain $a\_1,\; ...,\; a\_n$.
• a language learner $f$ learns a language $L$ in environment $E\; =\; (a\_1,\; a\_2,\; ...)$ if the learner always guesses $L$ after seeing enough examples from the environment.
• a language learner $f$ learns a language $L$ if it learns $L$ in any environment $E$ for $L$.
• a language family is learnable if there exists a language learner that can learn all languages in the family.

Notes:

• In the context of Gold's theorem, sentences need only be distinguishable. They need not be anything in particular, such as finite strings (as usual in formal linguistics).
• Learnability is not a concept for individual languages. Any individual language $L$ could be learned by a trivial learner that always guesses $L$.
• Learnability is not a concept for individual learners. A language family is learnable iff there exists some learner that can learn the family. It does not matter how well the learner performs for learning languages outside the family.

{{Math theorem|name=Gold's theorem (1967)|note=Theorem I.8 of (Gold, 1967)|math_statement=

If a language family $C$ contains $L\_1,\; L\_2,\; ...,\; L\_\backslash infty$, such that

$$L\_1\; \backslash subsetneq\; L\_2\; \backslash subsetneq\; \backslash cdots$$

and $L\_\backslash infty\; =\; \backslash cup\_\{n=1\}^\backslash infty\; L\_n$, then it is not learnable.

}}

{{Math proof|title=Proof|proof=

Suppose $f$ is a learner that can learn $L\_1,\; L\_2,\; ...$, then we show it cannot learn $L\_\backslash infty$, by constructing an environment for $L\_\backslash infty$ that "tricks" $f$.

First, construct environments $E\_1,\; E\_2,\; ...$ for languages $L\_1,\; L\_2,\; ...$.

Next, construct environment $E$ for $L\_\backslash infty$ inductively as follows:

• Present $f$ with $E\_1$ until it outputs $L\_1$.
• Switch to presenting $f$ with alternating the rest of $E\_1$ and the entirety of $E\_2$. Since $L\_1\; \backslash subset\; L\_2$, this concatenated environment is still an environment for $L\_2$, so $f$ must eventually output $L\_2$.
• Switch to presenting the rest of $E\_1,\; E\_2$ and the entirety of $E\_3$ alternatively.
• And so on.

By construction, the resulting environment $E$ contains the entirety of $E\_1,\; E\_2,\; ...$, thus it contains $\backslash cup\_n\; E\_n\; =\; \backslash cup\_n\; L\_n\; =\; L\_\backslash infty$, so it is an environment for $L\_\backslash infty$. Since the learner always switches to $L\_n$ for some finite $n$, it never converges to $L\_\backslash infty$.

}}

Gold's theorem is easily bypassed if negative examples are allowed. In particular, the language family $\backslash \{L\_1,L\_2,\; ...,\; L\_\backslash infty\backslash \}$ can be learned by a learner that always guesses $L\_\backslash infty$ until it receives the first negative example $\backslash neg\; a\_n$, where $a\_n\backslash in\; L\_\{n+1\}\; \backslash setminus\; L\_\{n\}$, at which point it always guesses $L\_n$.

Dana Angluin gave the characterizations of learnability from text (positive information) in a 1980 paper.{{cite journal| author=Dana Angluin| title=Inductive Inference of Formal Languages from Positive Data| journal=Information and Control| year=1980| volume=45| issue=2| pages=117–135| doi=10.1016/S0019-9958(80)90285-5| url=http://www-personal.umich.edu/~yinw/papers/Angluin80.pdf| doi-access=free}}

If a learner is required to be effective, then an indexed class of recursive languages is learnable in the limit if there is an effective procedure that uniformly enumerates tell-tales for each language in the class (Condition 1).p.121 top It is not hard to see that if an ideal learner (i.e., an arbitrary function) is allowed, then an indexed class of languages is learnable in the limit if each language in the class has a tell-tale (Condition 2).p.123 top

The table shows which language classes are identifiable in the limit in which learning model. On the right-hand side, each language class is a superclass of all lower classes. Each learning model (i.e. type of presentation) can identify in the limit all classes below it. In particular, the class of finite languages is identifiable in the limit by text presentation (cf. Example 2 above), while the class of regular languages is not.

Pattern Languages, introduced by Dana Angluin in another 1980 paper,{{cite journal| author=Dana Angluin| title=Finding Patterns Common to a Set of Strings| journal=Journal of Computer and System Sciences| year=1980| volume=21| pages=46–62| doi=10.1016/0022-0000(80)90041-0| doi-access=free}} are also identifiable by normal text presentation; they are omitted in the table, since they are above the singleton and below the primitive recursive language class, but incomparable to the classes in between.incomparable to regular and to context-free language class: Theorem 3.10, p.53{{clarify|reason=I'm not quite sure about context-sensitive and primitive recursive languages; please cross-check.|date=October 2013}}

Condition 1 in Angluin's paper is not always easy to verify. Therefore, people come up with various sufficient conditions for the learnability of a language class. See also Induction of regular languages for learnable subclasses of regular languages.

A class of languages has finite thickness if every non-empty set of strings is contained in at most finitely many languages of the class. This is exactly Condition 3 in Angluin's paper.p.123 mid Angluin showed that if a class of recursive languages has finite thickness, then it is learnable in the limit.p.123 bot, Corollary 2

A class with finite thickness certainly satisfies MEF-condition and MFF-condition; in other words, finite thickness implies M-finite thickness.{{cite book|author1=Andris Ambainis |author2=Sanjay Jain |author3=Arun Sharma | chapter=Ordinal mind change complexity of language identification| title=Computational Learning Theory| year=1997| volume=1208| pages=301–315| publisher=Springer| series=LNCS| chapter-url=http://www.comp.nus.edu.sg/~sanjay/paps/efs2.pdf}}; here: Proof of Corollary 29

A class of languages is said to have finite elasticity if for every infinite sequence of strings $s\_0,\; s\_1,\; ...$ and every infinite sequence of languages in the class $L\_1,\; L\_2,\; ...$, there exists a finite number n such that $s\_n\backslash not\backslash in\; L\_n$ implies $L\_n$ is inconsistent with $\backslash \{s\_1,...,s\_\{n-1\}\backslash \}$.

It is shown that a class of recursively enumerable languages is learnable in the limit if it has finite elasticity.

A bound over the number of hypothesis changes that occur before convergence.

A language L has infinite cross property within a class of languages $\backslash mathcal\{L\}$ if there is an infinite sequence $L\_i$ of distinct languages in $\backslash mathcal\{L\}$ and a sequence of finite subset $T\_i$ such that:

• $T\_1\; \backslash sub\; T\_2\backslash sub\; ...$,
• $T\_i\; \backslash in\; L\_i$,
• $T\_\{i+1\}\backslash not\backslash in\; L\_i$, and
• $\backslash lim\_\{n=\backslash infty\}T\_i=L$.

Note that L is not necessarily a member of the class of language.

It is not hard to see that if there is a language with infinite cross property within a class of languages, then that class of languages has infinite elasticity.

• Finite thickness implies finite elasticity;{{#tag:ref|Wright, Keith (1989) "[https://www.researchgate.net/publication/221497309_Identification_of_Unions_of_Languages_Drawn_from_an_Identifiable_Class Identification of Unions of Languages Drawn from an Identifiable Class]". Proc. 2nd Workwhop on Computational Learning Theory, 328-333; with correction in:Motoki, Shinohara, and Wright (1991) [https://www.researchgate.net/profile/Takeshi_Shinohara/publication/31900621_Correct_Definition_of_Finite_Elasticity/links/541763930cf2218008bee4d6.pdf?inViewer=true&disableCoverPage=true&origin=publication_detail "The correct definition of finite elasiticity: corrigendum to identification of unions"], Proc. 4th Workshop on Computational Learning Theory, 375-375}} the converse is not true.
• Finite elasticity and conservatively learnable implies the existence of a mind change bound. [http://citeseer.ist.psu.edu/context/1042497/0]
• Finite elasticity and M-finite thickness implies the existence of a mind change bound. However, M-finite thickness alone does not imply the existence of a mind change bound; neither does the existence of a mind change bound imply M-finite thickness. [http://citeseer.ist.psu.edu/context/1042497/0]
• Existence of a mind change bound implies learnability; the converse is not true.
• If we allow for noncomputable learners, then finite elasticity implies the existence of a mind change bound; the converse is not true.
• If there is no accumulation order for a class of languages, then there is a language (not necessarily in the class) that has infinite cross property within the class, which in turn implies infinite elasticity of the class.

• If a countable class of recursive languages has a mind change bound for noncomputable learners, does the class also have a mind change bound for computable learners, or is the class unlearnable by a computable learner?

{{reflist|group=note}}

{{reflist}}

Category:Formal languages

Category:Computational learning theory