Identificación del idioma en el límite

La identificación del lenguaje 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 en un artículo de revista ^[2] con el mismo título.

En este modelo, un profesor proporciona al alumno alguna presentación (es decir, una secuencia de cadenas ) de algún lenguaje formal. El aprendizaje es visto como 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 idioma.

Gold define que un alumno puede identificar en el límite una clase de idiomas si, dada cualquier presentación de cualquier idioma en la clase, el alumno producirá solo un número finito de representaciones incorrectas y luego se quedará con la representación correcta. Sin embargo, no es necesario que el alumno pueda anunciar que es correcto; y el profesor podría 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 idioma.
• 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 idioma o no.

Capacidad de aprendizaje

Este modelo es un primer intento de capturar formalmente la noción de capacidad de aprendizaje . El artículo de la revista 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 proporciona una cadena que pertenece a L y el alumno responde una suposición de 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 cuerda repetidamente. Después del paso 6 , el alumno se ciñe a la expresión regular ( ab + ba ) ^* . Si esto resulta ser una descripción del idioma L que el profesor tiene en mente, se dice que el alumno ha aprendido ese idioma.
   Si existiera un programa informático para el rol de alumno que fuera capaz de aprender con éxito cada idioma regular, esa clase de idiomas 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 cierto.
   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 un tiempo fijo.
3. Aprender de la presentación completa contando :
   En cada paso, el profesor da una cuerda y dice si pertenece a L ( verde ) o no ( rojo, tachado ). 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 indica si pertenece a L ( sí ) o no ( no ); Luego, el alumno adivina L , seguido de la siguiente cadena de consulta. En este ejemplo, el alumno consulta en cada paso la misma cadena proporcionada por el profesor en el ejemplo 3. En general, Gold ha demostrado que cada clase de idioma identificable en la configuración de presentación de solicitud también es identificable en la presentación de narración. configuración, ^[6] ya que el alumno, en lugar de consultar una cadena, solo necesita esperar hasta que finalmente se la proporcione el maestro.
   

teorema de oro

Más formalmente, ^[7]

• un lenguaje es un conjunto no vacío y sus elementos se llaman oraciones . ${\displaystyle L}$
• una familia de lenguas es un conjunto de lenguas.
• Un entorno de aprendizaje de idiomas para un idioma es un flujo de oraciones de , de modo que cada oración aparece al menos una vez. ${\displaystyle E}$ ${\displaystyle L}$ ${\displaystyle L}$ ${\displaystyle L}$
• un estudiante de idiomas es una función que envía una lista de oraciones a un idioma. ${\displaystyle f}$
  • Esto se interpreta en el sentido de que, después de ver oraciones en ese orden , el estudiante de la lengua adivina que la lengua que produce las oraciones debería serlo . ${\displaystyle a_{1},a_{2}...,a_{n}}$ ${\displaystyle f(a_{1},...,a_{n})}$
  • Tenga en cuenta que el alumno no está obligado a acertar: bien podría adivinar un idioma que ni siquiera contiene . ${\displaystyle a_{1},...,a_{n}}$
• un estudiante de idiomas aprende un idioma en el 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 idiomas aprende un idioma si lo aprende en cualquier entorno . ${\displaystyle f}$ ${\displaystyle L}$ ${\displaystyle L}$ ${\displaystyle E}$ ${\displaystyle L}$
• una familia de idiomas se puede aprender si existe un estudiante de idiomas que pueda aprender todos los idiomas de la familia.

Notas:

• En el contexto del teorema de Gold, las oraciones sólo necesitan ser distinguibles. No es necesario que sean nada en particular, como cadenas finitas (como es habitual en la lingüística formal).
• La capacidad de aprendizaje no es un concepto para idiomas individuales. Cualquier idioma individual podría ser aprendido por un alumno trivial que siempre adivina . ${\displaystyle L}$ ${\displaystyle L}$
• La capacidad de aprendizaje no es un concepto para estudiantes individuales. Una familia de lenguas se puede aprender si existe algún alumno que pueda aprender la familia. No importa qué tan bien 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 , tal que ${\displaystyle C}$ ${\displaystyle L_{1},L_{2},...,L_{\infty }}$

$${\displaystyle L_{1}\subsetneq L_{2}\subsetneq \cdots }$$

y entonces no se puede aprender. ${\displaystyle L_{\infty }=\cup _{n=1}^{\infty }L_{n}}$

Prueba

Supongamos que un alumno 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}$

Primero, construya entornos para idiomas . ${\displaystyle E_{1},E_{2},...}$ ${\displaystyle L_{1},L_{2},...}$

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

• Presente con hasta que salga . ${\displaystyle f}$ ${\displaystyle E_{1}}$ ${\displaystyle L_{1}}$
• Cambie a presentar alternando el resto y la totalidad de . Dado que este entorno concatenado sigue siendo un entorno para , eventualmente debe generarse . ${\displaystyle f}$ ${\displaystyle E_{1}}$ ${\displaystyle E_{2}}$ ${\displaystyle L_{1}\subset L_{2}}$ ${\displaystyle L_{2}}$ ${\displaystyle f}$ ${\displaystyle L_{2}}$
• Cambie 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 algo 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 eludir fácilmente si se permiten ejemplos negativos . En particular, la familia de lenguas puede ser aprendida por un alumno que siempre adivina hasta que recibe el primer ejemplo negativo , donde , momento en el que 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 de texto (información positiva) en un artículo de 1980. ^[8] Si se requiere que un alumno sea efectivo , entonces una clase indexada de lenguajes recursivos se puede aprender en el límite si existe un procedimiento efectivo que enumere uniformemente los indicadores para cada lenguaje en la clase (Condición 1). ^[9] No es difícil ver que si se permite un alumno ideal (es decir, una función arbitraria), entonces una clase indexada de idiomas se puede aprender en el límite si cada idioma de la clase tiene un indicador (Condición 2). . ^[10]

Clases de idiomas que se pueden aprender al límite.

La tabla muestra qué clases de idiomas son identificables en el límite en qué modelo de aprendizaje. En el lado derecho, cada clase de idioma 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 inferiores a él. En particular, la clase de lenguas finitas es identificable en el límite por la presentación del texto (cf. Ejemplo 2 anterior), mientras que la clase de lenguas regulares no lo es.

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

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, a la gente se le ocurren varias condiciones suficientes para que una clase de idioma sea fácil de aprender. Consulte también Inducción de lenguajes regulares para subclases de lenguajes regulares que se pueden aprender.

Espesor finito

Una clase de idiomas tiene un grosor finito si cada conjunto de cadenas no vacías está contenido como máximo en un número finito de idiomas 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 grosor finito, entonces se puede aprender en el límite. ^[14]

Una clase con espesor finito ciertamente satisface las condiciones MEF y MFF ; en otras palabras, espesor finito implica espesor M-finito . ^[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 que es inconsistente con . ^[dieciséis] ${\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 muestra que una clase de lenguajes recursivamente enumerables se puede aprender en el límite si tiene una elasticidad finita.

cambio de mente obligado

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

Otros conceptos

Propiedad cruzada infinita

Un lenguaje L tiene una propiedad cruzada infinita dentro de una clase de lenguajes si hay una secuencia infinita de lenguajes distintos 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 miembro de la clase de lenguaje.

No es difícil ver que si hay una lengua con propiedad cruzada infinita dentro de una clase de lenguas, entonces esa clase de lenguas tiene una elasticidad infinita.

Relaciones entre conceptos

• El espesor finito implica elasticidad finita; ^{[15] [17]} lo contrario no es cierto.
• La elasticidad finita y el aprendizaje conservador implican la existencia de un cambio de mentalidad limitado. [1]
• La elasticidad finita y el espesor M-finito implican la existencia de un límite de cambio de mente. Sin embargo, el espesor M-finito por sí solo no implica la existencia de un límite de cambio de mente; Tampoco la existencia de un límite de cambio de mente implica un espesor M-finito . [2]
• La existencia de un límite de cambio de mentalidad implica capacidad de aprendizaje; lo contrario no es cierto.
• Si tenemos en cuenta a los alumnos no computables, entonces la elasticidad finita implica la existencia de un límite de cambio de mente; lo contrario no es cierto.
• Si no existe un orden de acumulación para una clase de lenguas, entonces hay una lengua (no necesariamente en la clase) que tiene una propiedad cruzada infinita 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 cambio de mentalidad destinado a los estudiantes no computables, ¿la clase también tiene un cambio de mentalidad limitado a los estudiantes computables, o la clase no puede ser aprendida por 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 ; "ε" indica la cadena vacía; "a" y "b" se indican 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. es decir, presentación de texto, donde la cadena proporcionada por el profesor es una función recursiva primitiva del número de paso actual, y el alumno codifica una suposición del idioma como un programa que enumera el idioma.
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. es decir, presentación de texto, excepto la configuración de presentación de texto anómala
6. es decir, la clase de lenguajes que consta de 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 una clase de idioma regular y sin contexto: Teorema 3.10, p.53

Referencias

1. Oro, E. Mark (1964). Identificación de idioma en el límite (Memorando de Investigación RAND RM-4136-PR). Corporación RAND.
2. Gold, E. Mark (mayo de 1967). «Identificación del idioma en el límite» (PDF) . Información y Control . 10 (5): 447–474. doi : 10.1016/S0019-9958(67)91165-5 .
3. p.457
4. Teorema I.8, I.9, páginas 470-471
5. Teorema I.6, p.469
6. Teorema I.3, p.467
7. Johnson, Kent (octubre de 2004). "El teorema del oro 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 cuerdas". Revista de Ciencias de la Computación y de Sistemas . 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 mente ordinal cambia la complejidad de la identificación del lenguaje" (PDF) . Teoría del aprendizaje computacional . LNCS. vol. 1208. Saltador. 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. 4to Taller sobre Teoría del Aprendizaje Computacional, 375-375
17. Wright, Keith (1989) "Identificación de uniones de lenguas extraídas de una clase identificable". Proc. Segundo taller sobre teoría del aprendizaje computacional, 328-333; con corrección en: ^[16]