Language identification in the limit


Language identification in the limit

Language identification in the limit is a formal model for inductive inference. It was introduced by E. Mark Gold in his paper with the same title [http://www.isrl.uiuc.edu/~amag/langev/paper/gold67limit.html] . In this model, a learner is provided with presentation of some language. The learning is seen as an infinite process. Each time an element of the presentation is read the learner should provide a representation for the language. We say that a learner can identify in the limit a class of languages if given any presentation of any language in the class the learner will produce a finite number of wrong representations, and therefore converge on the correct representation in a finite number of steps, without however necessarily being able to announce its correctness since a counterexample to that representation could appear as an element arbitrarily long after.

Gold defined two types of presentations:
* Text (positive information): an enumeration of the language.
* Complete presentation (positive and negative information): an enumeration of all the possible strings with a label indicating if the string belongs to the language or not.

Learnability

This model is the first known attempt to capture the notion of learnability; another learnability model is the so-called Probably approximately correct learning (PAC) model.

Learnability characterization

Dana Angluin gave the characterizations of learnability from text (positive information) in her paper [http://citeseer.ist.psu.edu/context/14508/0] .

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). It is not hard to see that if we allow an ideal learner (i.e., an arbitrary function), then an indexed class of languages is learnable in the limit if each language in the class has a tell-tale (Condition 2).

Language classes learnable in the limit from text

*Finite cardinality languages
*Pattern languages

Language classes not learnable in the limit from text

*Regular languages

ufficient conditions for learnability

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.

Finite thickness

A class of languages has finite thickness if for every string s, there are only a finite number of languages in the class that are consistent with s. This is exactly Condition 3 in Angluin's paper. Angluin showed that if a class of recursive languages has finite thickness, then it is learnable in the limit.

A class with finite thickness certainly satisfies MEF-condition and MFF-condition; in other words, finite thickness implies M-finite thickness.

Finite elasticity

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 otin L_n implies L_n is inconsistent with {s_1,...,s_{n-1}}. [http://www.acm.org/pubs/citations/proceedings/colt/114836/p375-motoki/]

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

Mind change bound

Other concepts

Infinite cross property

A language L has infinite cross property within a class of languages mathcal{L} if there is an infinite sequence L_i of distinct languages in mathcal{L} and a sequence of finite subset T_i such that:
*T_1 sub T_2sub ...,
*T_i in L_i,
*T_{i+1} otin L_i, and
*lim_{n=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.

Relations between concepts

*Finite thickness implies finite elasticity; 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.

Open questions

*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?

External links

* http://www.isrl.uiuc.edu/~amag/langev/paper/gold67limit.html


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • The Price Is Right (U.S. game show) — The Price Is Right Format Game show Created by Mark Goodson Bill Todman Directed b …   Wikipedia

  • The Birth of Tragedy — Out of the Spirit of Music   …   Wikipedia

  • The Joker's Wild — infobox television show name = The Joker s Wild caption = Show logo, 1972 1975 format = Game show rating = TV G runtime = 30 minutes with commercials creator = Jack Barry starring = Jack Barry (host, 1972 84) Bill Cullen (host, 1984 86) Jim Peck… …   Wikipedia

  • The Rain God — Infobox Book | name = The Rain God: A Desert Tale title orig = translator = image caption = author = Arturo Islas illustrator = cover artist = country = language = series = genre = publisher = Alexandrian pub date = 1984 english pub date = media… …   Wikipedia

  • The Israel Lobby and U.S. Foreign Policy — infobox Book | name = The Israel Lobby and U.S. Foreign Policy orig title = translator = author = John Mearsheimer and Stephen Walt cover artist = country = United States language = English series = classification = Non fiction genre = Politics… …   Wikipedia

  • Poverty of the stimulus — The poverty of the stimulus (POTS) argument is a variant of the epistemological problem of the indeterminacy of data to theory that claims that grammar is unlearnable given the linguistic data available to children. As such, the argument strikes… …   Wikipedia

  • Society of the People's Republic of China — The People s Republic of China, the world s largest society, is united by a set of values and institutions that cut across extensive linguistic, environmental, and subcultural differences. Chinese society, since the second decade of the twentieth …   Wikipedia

  • Ionians (The) — The Ionians Malcolm Schofield THALES AND OTHERS The Greeks agreed that philosophy had begun with Thales. However they did not know much about his views.1 What survives is mostly a potent legend. Herodotus tells stories of his practical ingenuity …   History of philosophy

  • Society of the United States — The society or culture of the United States is a Western culture, and has been developing since long before the United States became a country with its own unique characteristics and developments such as dialect, music, arts, cuisine, etc. Today… …   Wikipedia

  • Dacian language — Dacian Spoken in Romania, northern Bulgaria, eastern Serbia; also (possibly): Moldova, SW Ukraine, eastern Hungary, southern Bulgaria, northern Greece, European Turkey, NW Anatolia (Turkey) Extinct probably by the 6th century AD …   Wikipedia