Language Identification In The Limit Article Index for
Language 		Website Links For
Language 		 

Information About

Language Identification In The Limit
  CATEGORIES ABOUT LANGUAGE IDENTIFICATION IN THE LIMIT
   
formal languages
   
APPAREL
BABY
BEAUTY
BOOKS
CAR TOYS
CELL PHONES
DVD'S
ELECTRONICS
GOURMET FOOD
GROCERIES
HEALTH & PERSONAL
HOME & GARDEN
JEWELRY
MUSIC
MUSIC INSTRUMENTS
OFFICE PRODUCTS
SOFTWARE
SPORTING GOODS
TOOLS & HARDWARE
TOYS
VIDEO GAMES
SHOPPING HOME
MORE SHOPPING...




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 in her paper {Link without Title} .

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-tale s 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



LANGUAGE CLASSES NOT LEARNABLE IN THE LIMIT



SUFFICIENT 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
ot\in L_n implies L_n is inconsistent with \{s_1,...,s_{n-1}\}. {Link without Title}

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_2\sub ...,

  • T_i \in L_i,

  • T_{i+1}

    • ot\in 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. {Link without Title}

  • 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 . {Link without Title}

  • 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