Identificación del lenguaje en el límite

La identificación de lenguajes en el límite es un modelo formal para la inferencia inductiva de lenguajes formales , principalmente por computadoras (ver aprendizaje automático e inducción de lenguajes regulares ). Fue presentado por E. Mark Gold en un informe técnico ^[1] y un artículo de revista ^[2] con el mismo título.

En este modelo, un profesor proporciona a un alumno una presentación (es decir, una secuencia de cadenas ) de un lenguaje formal. El aprendizaje se considera un proceso infinito. Cada vez que el alumno lee un elemento de la presentación, debe proporcionar una representación (por ejemplo, una gramática formal ) del lenguaje.

Gold define que un alumno puede identificar en el límite una clase de lenguas si, dada cualquier presentación de cualquier lengua de la clase, el alumno produce sólo un número finito de representaciones erróneas y luego se queda con la representación correcta. Sin embargo, el alumno no necesita poder anunciar su corrección; y el profesor puede presentar un contraejemplo a cualquier representación arbitrariamente mucho tiempo después.

Gold definió dos tipos de presentaciones:

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

Capacidad de aprendizaje

Este modelo es un intento temprano de capturar formalmente la noción de capacidad de aprendizaje . El artículo de revista de Gold ^[3] presenta, para contrastar, los modelos más fuertes

• Identificación finita (donde el alumno tiene que anunciar la corrección después de un número finito de pasos), y
• Identificación en tiempo fijo (donde la corrección debe alcanzarse después de un número de pasos especificado a priori).

Un modelo formal más débil de capacidad de aprendizaje es el modelo de aprendizaje probablemente aproximadamente correcto (PAC) , introducido por Leslie Valiant en 1984.

Ejemplos

Es instructivo observar ejemplos concretos (en las tablas) de sesiones de aprendizaje de las que habla la definición de identificación en el límite.

1. Una sesión ficticia para aprender un lenguaje regular L sobre el alfabeto { a , b } a partir de una presentación de texto :
   En cada paso, el profesor da una cadena que pertenece a L , y el alumno responde una suposición para L , codificada como una expresión regular . ^{[nota 1]} En el paso 3 , la suposición del alumno no es consistente con las cadenas vistas hasta ahora; en el paso 4 , el profesor da una cadena repetidamente. Después del paso 6 , el alumno se apega a la expresión regular ( ab + ba ) ^* . Si resulta ser una descripción del lenguaje L que el profesor tiene en mente, se dice que el alumno ha aprendido ese lenguaje.
   Si existiera un programa de computadora para el rol del alumno que fuera capaz de 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. ^[4]
2. Un algoritmo de aprendizaje particular siempre supone que L es simplemente la unión de todas las cadenas vistas hasta ahora :
   si L es un lenguaje finito, el alumno eventualmente lo adivinará correctamente, sin embargo, sin poder decir cuándo. Aunque la suposición no cambió durante los pasos 3 a 6 , el alumno no podía estar seguro de estar en lo correcto.
   Gold ha demostrado que la clase de lenguajes finitos es identificable en el límite, ^[5] sin embargo, esta clase no es identificable de manera finita ni en tiempo fijo.
3. Aprendizaje a partir de una presentación completa mediante la narración :
   en cada paso, el profesor da una cadena y dice si pertenece a L ( verde ) o no ( roja, tachada ). Cada cadena posible es finalmente clasificada de esta manera por el profesor.
4. Aprendizaje a partir de una presentación completa por solicitud :
   el alumno proporciona una cadena de consulta, el profesor le dice si pertenece a L ( sí ) o no ( no ); el alumno luego proporciona una suposición para L , seguida por la siguiente cadena de consulta. En este ejemplo, resulta que el alumno consulta en cada paso exactamente la misma cadena que le proporcionó el profesor en el ejemplo 3. En general, Gold ha demostrado que cada clase de lenguaje identificable en el entorno de presentación por solicitud también es identificable en el entorno de presentación por indicación, ^[6] ya que el alumno, en lugar de consultar una cadena, solo necesita esperar hasta que finalmente la proporcione el profesor.
   

Teorema de Gold

Más formalmente, ^[7]

• Un lenguaje es un conjunto no vacío y sus elementos se llaman oraciones . ${\displaystyle L}$
• Una familia lingüística es un conjunto de lenguas.
• Un entorno de aprendizaje de un idioma es un flujo de oraciones de , tal que cada oración en aparece al menos una vez. ${\displaystyle E}$ ${\displaystyle L}$ ${\displaystyle L}$ ${\displaystyle L}$
• Un aprendiz de idiomas es una función que envía una lista de oraciones a un idioma. ${\displaystyle f}$
  • Esto se interpreta como que, después de ver oraciones en ese orden , el estudiante de lenguas adivina que el idioma que produce las oraciones debería ser . ${\displaystyle a_{1},a_{2}...,a_{n}}$ ${\displaystyle f(a_{1},...,a_{n})}$
  • Tenga en cuenta que el alumno no está obligado a acertar: podría perfectamente adivinar un idioma que ni siquiera contiene . ${\displaystyle a_{1},...,a_{n}}$
• Un estudiante de una lengua aprende una lengua en un entorno si siempre adivina después de ver suficientes ejemplos del entorno. ${\displaystyle f}$ ${\displaystyle L}$ ${\displaystyle E=(a_{1},a_{2},...)}$ ${\displaystyle L}$
• Un estudiante de una lengua aprende una lengua si la aprende en cualquier entorno . ${\displaystyle f}$ ${\displaystyle L}$ ${\displaystyle L}$ ${\displaystyle E}$ ${\displaystyle L}$
• Una familia lingüística se puede aprender si existe un estudiante de lenguas que puede aprender todas las lenguas de la familia.

Notas:

• En el contexto del teorema de Gold, las oraciones sólo necesitan ser distinguibles, no necesitan ser nada en particular, como cadenas finitas (como es habitual en la lingüística formal).
• La facilidad de aprendizaje no es un concepto que se aplique a los idiomas individuales. Cualquier idioma individual puede ser aprendido por un estudiante trivial que siempre adivina . ${\displaystyle L}$ ${\displaystyle L}$
• La capacidad de aprendizaje no es un concepto que se aplique a estudiantes individuales. Una familia lingüística es aprendible si existe algún alumno que pueda aprender la familia. No importa lo bien que se desempeñe el alumno en el aprendizaje de idiomas fuera de la familia.

Teorema de Gold (1967)  (Teorema I.8 de (Gold, 1967))  —  Si una familia de lenguas contiene , tales que y , entonces no se puede aprender. ${\displaystyle C}$ ${\displaystyle L_{1},L_{2},...,L_{\infty }}$ $${\displaystyle L_{1}\subsetneq L_{2}\subsetneq \cdots }$$ ${\displaystyle L_{\infty }=\cup _{n=1}^{\infty }L_{n}}$

Prueba

Supongamos que hay un alumno que puede aprender , entonces demostramos que no puede aprender , construyendo un entorno para esos "trucos" . ${\displaystyle f}$ ${\displaystyle L_{1},L_{2},...}$ ${\displaystyle L_{\infty }}$ ${\displaystyle L_{\infty }}$ ${\displaystyle f}$

En primer lugar, construir entornos para los idiomas . ${\displaystyle E_{1},E_{2},...}$ ${\displaystyle L_{1},L_{2},...}$

A continuación, construya el entorno de forma inductiva de la siguiente manera: ${\displaystyle E}$ ${\displaystyle L_{\infty }}$

• Presente con hasta que salga . ${\displaystyle f}$ ${\displaystyle E_{1}}$ ${\displaystyle L_{1}}$
• Pasar a la presentación alternando el resto de y la totalidad de . Dado que , este entorno concatenado sigue siendo un entorno para , por lo que eventualmente debe generar . ${\displaystyle f}$ ${\displaystyle E_{1}}$ ${\displaystyle E_{2}}$ ${\displaystyle L_{1}\subset L_{2}}$ ${\displaystyle L_{2}}$ ${\displaystyle f}$ ${\displaystyle L_{2}}$
• Pasar a presentar el resto y la totalidad de forma alternativa. ${\displaystyle E_{1},E_{2}}$ ${\displaystyle E_{3}}$
• Etcétera.

Por construcción, el entorno resultante contiene la totalidad de , por lo tanto, contiene , por lo que es un entorno para . Dado que el alumno siempre cambia a para algún finito , nunca converge a . ${\displaystyle E}$ ${\displaystyle E_{1},E_{2},...}$ ${\displaystyle \cup _{n}E_{n}=\cup _{n}L_{n}=L_{\infty }}$ ${\displaystyle L_{\infty }}$ ${\displaystyle L_{n}}$ ${\displaystyle n}$ ${\displaystyle L_{\infty }}$

El teorema de Gold se puede obviar fácilmente si se permiten ejemplos negativos . En particular, la familia de lenguajes puede ser aprendida por un alumno que siempre adivina hasta que recibe el primer ejemplo negativo , donde , en cuyo punto siempre adivina . ${\displaystyle \{L_{1},L_{2},...,L_{\infty }\}}$ ${\displaystyle L_{\infty }}$ ${\displaystyle \neg a_{n}}$ ${\displaystyle a_{n}\in L_{n+1}\setminus L_{n}}$ ${\displaystyle L_{n}}$

Caracterización de la capacidad de aprendizaje

Dana Angluin dio las caracterizaciones de la capacidad de aprendizaje a partir del texto (información positiva) en un artículo de 1980. ^[8] Si se requiere que un aprendiz sea efectivo , entonces una clase indexada de lenguajes recursivos es aprendible en el límite si hay un procedimiento efectivo que enumera uniformemente los indicadores para cada lenguaje en la clase (Condición 1). ^[9] No es difícil ver que si se permite 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 un indicador (Condición 2). ^[10]

Clases de idiomas que se pueden aprender en el límite

La tabla muestra qué clases de lenguaje son identificables en el límite en qué modelo de aprendizaje. En el lado derecho, cada clase de lenguaje es una superclase de todas las clases inferiores. Cada modelo de aprendizaje (es decir, tipo de presentación) puede identificar en el límite todas las clases por debajo de él. En particular, la clase de lenguajes finitos es identificable en el límite por la presentación de texto (cf. Ejemplo 2 arriba), mientras que la clase de lenguajes regulares no lo es.

Los lenguajes de patrones , introducidos por Dana Angluin en otro artículo de 1980, ^[12] también se pueden identificar por su presentación de texto normal; se omiten en la tabla, ya que están por encima del singleton y por debajo de la clase de lenguaje recursivo primitivo, pero no son comparables con las clases intermedias. ^{[nota 7] [ aclaración necesaria ]}

Condiciones suficientes para la capacidad de aprendizaje

La condición 1 del artículo de Angluin ^[9] no siempre es fácil de verificar. Por lo tanto, la gente propone varias condiciones suficientes para la capacidad de aprendizaje de una clase de lenguaje. Véase también Inducción de lenguajes regulares para subclases de lenguajes regulares que se puedan aprender.

Espesor finito

Una clase de lenguajes tiene un espesor finito si cada conjunto de cadenas no vacías está contenido en, como máximo, un número finito de lenguajes de la clase. Esta es exactamente la condición 3 del artículo de Angluin. ^[13] Angluin demostró que si una clase de lenguajes recursivos tiene un espesor finito, entonces es aprendible en el límite. ^[14]

Una clase con un espesor finito ciertamente satisface la condición MEF y la condición MFF ; en otras palabras, el espesor finito implica un espesor finito M. ^[15]

Elasticidad finita

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

Se demuestra que una clase de lenguajes recursivamente enumerables se puede aprender en el límite si tiene elasticidad finita.

Cambio de mentalidad obligado

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

Otros conceptos

Propiedad de cruz infinita

Un idioma L tiene propiedad cruzada infinita dentro de una clase de idiomas si existe una secuencia infinita de idiomas distintos en y una secuencia de subconjuntos finitos tales que: ${\displaystyle {\mathcal {L}}}$ ${\displaystyle L_{i}}$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle T_{i}}$

• ${\displaystyle T_{1}\subset T_{2}\subset ...}$,
• ${\displaystyle T_{i}\in L_{i}}$,
• ${\displaystyle T_{i+1}\not \in L_{i}}$, y
• ${\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 con propiedades cruzadas infinitas dentro de una clase de lenguajes, entonces esa clase de lenguajes tiene elasticidad infinita.

Relaciones entre conceptos

• Un espesor finito implica una elasticidad finita; ^{[15] [17]} lo inverso no es cierto.
• La elasticidad finita y el aprendizaje conservador implican la existencia de un límite para el cambio de mentalidad. [1]
• La elasticidad finita y el espesor M-finito implican la existencia de un límite de cambio de mentalidad. Sin embargo, el espesor M-finito por sí solo no implica la existencia de un límite de cambio de mentalidad; tampoco la existencia de un límite de cambio de mentalidad implica un espesor M-finito . [2]
• La existencia de un límite para el cambio de mentalidad implica capacidad de aprendizaje; lo inverso no es cierto.
• Si permitimos que haya aprendices no computables, entonces la elasticidad finita implica la existencia de un límite de cambio de mentalidad; lo inverso no es cierto.
• Si no existe un orden de acumulación para una clase de lenguajes, entonces hay un lenguaje (no necesariamente en la clase) que tiene propiedades cruzadas infinitas dentro de la clase, lo que a su vez implica una elasticidad infinita de la clase.

Preguntas abiertas

• Si una clase contable de lenguajes recursivos tiene un límite de cambio de mentalidad para estudiantes no computables, ¿la clase también tiene un límite de cambio de mentalidad para estudiantes computables, o la clase es inaprendible para un estudiante computable?

Notas

1. " A + B " contiene todas las cadenas que están en A o en B ; " AB " contiene todas las concatenaciones de una cadena en A con una cadena en B ; " A ^* " contiene todas las repeticiones (cero o más veces) de cadenas en A ; "ε" denota la cadena vacía; "a" y "b" se denotan a sí mismos. Por ejemplo, la expresión "( ab + ba ) ^* " en el paso 7 denota el conjunto infinito {ε, ab, ba, abab, abba, baab, baba, ababab, ababba, ...}.
2. ie presentación de texto, donde la cadena dada por el profesor es una función recursiva primitiva del número de paso actual, y el alumno codifica una suposición de lenguaje como un programa que enumera el lenguaje
3. es decir, la clase de lenguajes que son decidibles mediante funciones recursivas primitivas
4. es decir que contiene todos los lenguajes finitos y al menos uno infinito
5. Presentación de texto, excepto por la configuración de presentación de texto anómala
6. es decir, la clase de lenguajes que consisten en una sola cadena (se mencionan aquí solo como un límite inferior común a los lenguajes finitos y los lenguajes de patrones)
7. incomparable con la clase de lenguaje regular y libre de contexto: Teorema 3.10, p.53

Referencias

1. Gold, E. Mark (1964). Identificación de lenguaje en el límite (Memorando de investigación RAND RM-4136-PR). RAND Corporation.
2. Gold, E. Mark (mayo de 1967). "Identificación del lenguaje en el límite" (PDF) . Información y Control . 10 (5): 447–474. doi : 10.1016/S0019-9958(67)91165-5 .
3. pág. 457
4. Teorema I.8, I.9, pág. 470-471
5. Teorema I.6, pág. 469
6. Teorema I.3, p.467
7. Johnson, Kent (octubre de 2004). "El teorema de Gold y la ciencia cognitiva". Filosofía de la ciencia . 71 (4): 571–592. doi :10.1086/423752. ISSN  0031-8248. S2CID  5589573.
8. Dana Angluin (1980). "Inferencia inductiva de lenguajes formales a partir de datos positivos" (PDF) . Información y control . 45 (2): 117–135. doi : 10.1016/S0019-9958(80)90285-5 .
9. p.121 arriba
10. p.123 arriba
11. Tabla 1, p.452, en (Gold 1967)
12. Dana Angluin (1980). "Encontrar patrones comunes a un conjunto de cadenas". Journal of Computer and System Sciences . 21 : 46–62. doi : 10.1016/0022-0000(80)90041-0 .
13. p.123 mediados
14. p.123 bot, Corolario 2
15. Andris Ambainis; Sanjay Jain; Arun Sharma (1997). "La complejidad del cambio de mentalidad ordinal en la identificación del lenguaje" (PDF) . Teoría del aprendizaje computacional . LNCS. Vol. 1208. Springer. págs. 301–315.; aquí: Prueba del corolario 29
16. Motoki, Shinohara y Wright (1991) "La definición correcta de elasticidad finita: corrección de errores para la identificación de uniones", Proc. 4.º Taller sobre teoría del aprendizaje computacional, 375-375
17. Wright, Keith (1989) "Identificación de uniones de lenguajes extraídas de una clase identificable". Proc. 2nd Workwhop on Computational Learning Theory, 328-333; con corrección en: ^[16]