Identificación de lenguaje en el límite

La identificación de lenguaje en el límite es un modelo formal para la inferencia inductiva. Fue presentado por E. Mark Gold en su artículo "Language identification in the limit".^[1]​ En este modelo, a un aprendiz se le proporciona una presentación (es decir, cadenas de caracteres) de algún lenguaje formal. El aprendizaje se ve como un proceso infinito. Cada vez que se lee un elemento de la presentación, el aprendiz debe proporcionar una representación (por ejemplo, una gramática formal) para el lenguaje. Se dice que un aprendiz puede identificar en el límite una clase de lenguajes si, dada cualquier presentación de cualquier lenguaje en la clase, el aprendiz producirá solo un número finito de representaciones erróneas y, por lo tanto, convergerá a la representación correcta en un número finito de pasos, sin embargo, sin poder necesariamente anunciar su correctitud ya que, posteriormente, un contraejemplo de esa representación podría aparecer como un elemento.

Gold definió dos tipos de presentaciones:

• Presentación por texto (información positiva): una enumeración de todas las cadenas de caracteres en que consiste el lenguaje. 
• Presentación completa (información positiva y negativa): una enumeración de todas las cadenas de caracteres posibles, cada una con una etiqueta que indica si la cadena pertenece al lenguaje o no.

Este modelo es un intento temprano por capturar formalmente la noción de capacidad de aprendizaje. En su artículo,^[2]​ Gold introduce para contrastar los modelos más fuertes:

• Identificación finita (dónde el aprendiz tiene que anunciar la correctitud después de un número finito de pasos), y
• Identificación en tiempo fijo (dónde la correctitud tiene que alcanzarse en un número de pasos fijado a priori).

Un modelo formal más débil es el Aprendizaje PAC, introducido por Leslie Valiant en 1984.

1. Una sesión ficticia para aprender un lenguaje regular L sobre el alfabeto {a, b} a partir de presentación por texto. En cada paso, el profesor da una cadena que pertenece a L, y el aprendiz responde una suposición para L, en forma de expresión regular. En el paso 3, la suposición del aprendiz no es consistente con las cadenas vistas hasta el momento; en el paso 4, el maestro da una cadena repetidamente. Después del paso 6, el aprendiz se mantiene dando como expresión regular (ab+ba)*. Si esto resulta ser una descripción del lenguaje L que el maestro tiene en mente, se dice que el aprendiz ha aprendido ese lenguaje. Si existiera un programa de computadora para el rol del aprendiz que pudiera aprender con éxito cada lenguaje regular, esa clase de lenguajes sería identificable en el límite. Gold ha demostrado que este no es el caso.^[3]​
2. Un algoritmo de aprendizaje particular que siempre supone que L es la unión de todas las cadenas de caracteres vistas hasta el momento. Si L es un lenguaje finito, el aprendiz eventualmente lo adivinará correctamente, sin embargo, sin poder decir cuándo. Aunque la suposición no cambió durante los pasos del 3 al 6, el aprendiz no podría estar seguro de estar en lo correcto. Gold ha demostrado que la clase de lenguajes finitos es identificable en el límite;^[4]​ sin embargo, esta clase no es ni finita ni identificable en tiempo fijo.
3. Aprendizaje a través de presentación completa por revelación. En cada paso, el profesor da una cadena de caracteres y dice si pertenece a L o no. Cada cadena posible es finalmente clasificada de este modo por el profesor.
4. Aprendizaje a través de presentación completa por petición. El aprendiz da una cadena de consulta, el maestro dice si pertenece a L o no; el alumno entonces da una suposición para L, seguido de la siguiente cadena de consulta. En este ejemplo, el alumno consulta en cada paso la misma cadena que da el profesor en el ejemplo 3. En general, Gold ha demostrado que cada clase de lenguaje identificable en la configuración de presentación por petición también es identificable en el límite en la configuración de presentación por revelación,^[5]​ ya que el alumno, en lugar de consultar una cadena, sólo tiene que esperar hasta que sea eventualmente el profesor se la proporcione.

Dana Angluin dio las caracterizaciones de aprendizaje a través de presentación por texto (información positiva) en un artículo^[6]​ de 1980. Si se requiere que un alumno sea eficaz, entonces se puede aprender una clase indizada de lenguajes recursivos en el límite si hay un procedimiento efectivo que enumere uniformemente las cadenas que caracteres que ocurren solo en un lenguaje para cada lenguaje de la clase (condición 1).^[7]​ No es difícil ver que si permitimos a un aprendiz ideal (es decir, una función arbitraria), entonces una clase indexada de lenguajes es aprendible en el límite si cada lenguaje en la clase tiene una cadena que caracteres que solo ocurre en ese lenguaje (condición 2).^[8]​

La tabla muestra qué clases de lenguajes son identificables en el límite en qué modelo de aprendizaje. En el lado derecho, cada clase de lenguaje es un superclase de todas las clases más bajas. Cada modelo de aprendizaje (i.e. tipo de presentación) puede identificar en el límite todas las clases de abajo. En particular, la clase de lenguajes finitos es identificable en el límite por presentación por texto (cf. Ejemplo 2 encima), mientras que la clase de los lenguajes regulares no lo es.

La condición 1 en el artículo de Angluin^[7]​ no siempre es fácil de verificar. Por lo tanto, han surgido varias condiciones suficientes para la aprendibilidad de una clase de lenguaje.

Una clase de lenguajes tiene espesor finito si cada conjunto no vacío de cadenas de caracteres está contenido en, a lo sumo, un número finito de lenguajes de la clase. Esta es exactamente la Condición 3 en artículo de Angluin.^[10]​^[11]​ Angluin mostró que si una clase de lenguajes recursivos tiene espesor finito, entonces es aprendible en el límite.^[12]​

Una clase con espesor finito sin duda satisface la MEF-condición y  la MFP-condición; en otras palabras, espesor finito implica M-espesor finito.^[13]​

Una clase de lenguajes se dice que tiene elasticidad finita si para cada secuencia infinita de cadenas ${\displaystyle s_{0},s_{1},...}$ y cada secuencia infinita de lenguajes en la clase ${\displaystyle L_{1},L_{2},...}$, existe un número finito n tal que ${\displaystyle s_{n}\not \in L_{n}}$ implica que ${\displaystyle L_{n}}$ es inconsistente con ${\displaystyle \{s_{1},...,s_{n-1}\}}$.^[14]​

Está demostrado que una clase de lenguajes recursivamente enumerable se puede aprender en el límite si tiene elasticidad finita.

Un límite sobre el número de cambios de hipótesis que se producen antes de la convergencia.

Un lenguaje L tiene propiedad de cruzamiento finito dentro de una clase de lenguajes ${\displaystyle {\mathcal {L}}}$ si hay una secuencia infinita ${\displaystyle L_{i}}$ lenguajes distintos en ${\displaystyle {\mathcal {L}}}$ y una secuencia de subconjunto finito ${\displaystyle T_{i}}$ tal que:

• ${\displaystyle T_{1}\subset T_{2}\subset ...}$,
• ${\displaystyle T_{i}\in L_{i}}$,
• ${\displaystyle T_{i+1}\not \in L_{i}}$, and
• ${\displaystyle \lim _{n=\infty }T_{i}=L}$.

Tenga en cuenta que L no es necesariamente un miembro de la clase de lenguaje.

No es difícil ver que si hay un lenguaje que cumple propiedad de cruzamiento infinito dentro de una clase de lenguajes, entonces esa clase de lenguajes tiene elasticidad infinita.

• Espesor finito implica elasticidad finita;^[13]​^[15]​ el recíproco no es cierto.
• Elasticidad finita y aprendizaje de manera conservadora implica la existencia de un límite de cambio de idea.
• Elasticidad finita y espesor M-finito implica la existencia de un límite de cambio de idea. Sin embargo, espesura M-finita solamente no implica la existencia de un límite de cambio de idea; tampoco la existencia de un límite de cambio de idea implica espesura M-finita.
• La existencia de límite de cambio de idea implica capacidad de aprendizaje; el recíproco no es cierto.
• Si permitimos aprendices no computables, entonces elasticidad finita implica la existencia de un límite de cambio de idea; el recíproco no es cierto.
• Si no hay orden de acumulación para una clase de lenguajes, entonces hay un lenguaje (no necesariamente en la clase) que tiene propiedad de cruzamiento infinito dentro de la clase, que a su vez implica elasticidad infinita de la clase.

• Si una clase contable de los lenguajes recursivos tiene un límite de cambio de idea para aprendices no computables, ¿la clase también tiene un límite de cambio de idea para aprendices computables, o la clase no puede ser aprendida por un aprendiz computable?