La identificación del lenguaje en el límite es un modelo formal para la inferencia inductiva de lenguajes formales , principalmente por computadora (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 alguna presentación (es decir, una secuencia de cadenas ) de algún lenguaje formal. El aprendizaje se ve 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, el alumno no necesita poder anunciar su corrección; y el maestro podría presentar un contraejemplo a cualquier representación arbitrariamente mucho tiempo después.
Gold definió dos tipos de presentaciones:
- Texto (información positiva): enumeración de todas las cadenas de caracteres 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 intento temprano de capturar formalmente la noción de capacidad de aprendizaje . Gold's paper [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 de 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 de
Profesor | Del alumno | ||
---|---|---|---|
Adivinar | Consulta | ||
0. | abab | ||
1. | sí | abab | baba |
2. | sí | a * ( ba ) * b * | Automóvil club británico |
3. | No | ( ab ) * ( ba ) * ( ab ) * ( ba ) * | bababa |
4. | sí | ( ab + ba ) * | babb |
5. | No | ( ab + ba ) * | baaa |
... | ... |
Profesor | Aprendiz | |
---|---|---|
1. | abab | abab |
2. | baba | a * ( ba ) * b * |
3. | ( ab ) * ( ba ) * ( ab ) * ( ba ) * | |
4. | bababa | ( ab + ba ) * |
5. | ( ab + ba ) * | |
6. | ( ab + ba ) * | |
7. | ε | ( ab + ba ) * |
... | ... |
Profesor | Aprendiz | |
---|---|---|
1. | abab | abab |
2. | licenciado en Letras | abab + ba |
3. | baba | abab + ba + baba |
4. | licenciado en Letras | abab + ba + baba |
5. | baba | abab + ba + baba |
6. | abab | abab + ba + baba |
7. | ε | abab + ba + baba + ε |
... | ... |
Profesor | Aprendiz | |
---|---|---|
1. | abab | abab |
2. | baba | abab + baba |
3. | baabab | ( b + ε) ( ab ) * |
4. | baabab | ( b + ε) ( ab ) * + baabab |
5. | abbaabba | ( ab ) * ( ba ) * ( ab ) * ( ba ) * |
6. | baabbaab | ( ab + ba ) * |
7. | bababa | ( ab + ba ) * |
... | ... |
Es instructivo mirar ejemplos concretos (en las tablas) de sesiones de aprendizaje de las que habla la definición de identificación en el límite.
- Una sesión ficticia para aprender un idioma normal L sobre el alfabeto { a , b } de la presentación del texto . En cada paso, el maestro da 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 maestro da una cuerda repetidamente. Después del paso 6 , el alumno se apega a la expresión regular ( ab + ba ) * . Si se trata de una descripción de la lengua L que el profesor tiene en mente, se dice que el alumno ha aprendido esa lengua. Si existiera un programa de computadora para el rol del alumno que pudiera aprender exitosamente cada idioma regular, esa clase de idiomas sería identificable en el límite . Gold ha demostrado que este no es el caso. [4]
- Un algoritmo de aprendizaje particular siempre adivina que L es solo 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 puede 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 ni finita ni identificable en un tiempo fijo.
- Aprendiendo 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. - Aprendiendo de la presentación completa a pedido . El alumno da una cadena de consulta, el profesor dice si pertenece a L ( sí ) o no ( no ); el alumno luego da una suposición de L , seguida de la siguiente cadena de consulta. En este ejemplo, el alumno consulta en cada paso la misma cadena dada por el profesor en el ejemplo 3. En general, Gold ha demostrado que cada clase de idioma identificable en la configuración de solicitud-presentación también es identificable en la presentación-reveladora configuración, [6] ya que el alumno, en lugar de consultar una cadena, solo necesita esperar hasta que finalmente la proporcione el profesor.
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. [7] Si se requiere que un alumno sea efectivo , entonces una clase indexada de idiomas recursivos se puede aprender en el límite si existe un procedimiento efectivo que enumere de manera uniforme los indicadores de cada idioma en la clase (Condición 1). [8] 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) . [9]
Clases de idiomas aptas para el límite
Modelo de capacidad de aprendizaje | Clase de idiomas |
---|---|
Presentación de texto anómala [nota 2] | |
Recursivamente enumerable | |
Recursivo | |
Presentación completa | |
Primitivo recursivo [nota 3] | |
Sensible al contexto | |
Libre de contexto | |
Regular | |
Superfinito [nota 4] | |
Presentación de texto normal [nota 5] | |
Finito | |
Singleton [nota 6] |
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 por debajo de él. En particular, la clase de lenguajes finitos es identificable en el límite por presentación de texto (véase el ejemplo 2 anterior ), mientras que la clase de lenguajes regulares no lo es.
Los lenguajes de patrones , presentados por Dana Angluin en otro artículo de 1980, [11] 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] [ aclaración necesaria ]
Condiciones suficientes para la capacidad de aprendizaje
La condición 1 del artículo de Angluin [8] no siempre es fácil de verificar. Por lo tanto, las personas plantean varias condiciones suficientes para el aprendizaje de una clase de idiomas. Consulte también Inducción de lenguajes regulares para subclases de idiomas regulares que se pueden aprender.
Espesor finito
Una clase de lenguajes tiene un grosor finito si cada conjunto de cadenas no vacías está contenido en un número finito de lenguajes de la clase como máximo. Ésta es exactamente la Condición 3 del artículo de Angluin. [12] Angluin demostró que si una clase de lenguajes recursivos tiene un grosor finito, entonces se puede aprender en el límite. [13]
Una clase con espesor finito ciertamente satisface MEF-condición y MFF-condición ; en otras palabras, el espesor finito implica M-espesor finito . [14]
Elasticidad finita
Se dice que una clase de lenguajes tiene elasticidad finita si por cada secuencia infinita de cadenas y cada secuencia infinita de idiomas en la clase , existe un número finito n tal que implica es inconsistente con . [15]
Se muestra que una clase de lenguajes enumerables de forma recursiva se puede aprender en el límite si tiene una elasticidad finita.
Mente atado al cambio
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 lenguaje L tiene una propiedad cruzada infinita dentro de una clase de lenguajes si hay una secuencia infinita de distintos idiomas en y una secuencia de subconjunto finito tal que:
- ,
- ,
- , y
- .
Tenga en cuenta que L no es necesariamente un miembro de la clase de idioma.
No es difícil ver que si hay un lenguaje con propiedad cruzada infinita dentro de una clase de lenguajes, entonces esa clase de lenguajes tiene una elasticidad infinita.
Relaciones entre conceptos
- El espesor finito implica elasticidad finita; [14] [16] lo contrario no es cierto.
- La elasticidad finita y el aprendizaje conservador implica la existencia de un límite de cambio mental. [1]
- La elasticidad finita y el espesor M-finito implican la existencia de un límite de cambio mental. Sin embargo, M-espesor finito por sí solo no implica la existencia de un límite de cambio mental; tampoco la existencia de un límite de cambio mental implica M-espesor finito . [2]
- La existencia de un límite de cambio mental implica capacidad de aprendizaje; lo contrario no es cierto.
- Si damos cabida a aprendices no computables, entonces la elasticidad finita implica la existencia de un límite de cambio mental; lo contrario no es cierto.
- Si no hay un orden de acumulación para una clase de lenguajes, entonces hay un lenguaje (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 mente destinado a estudiantes que no pueden computar, ¿la clase también tiene un cambio de mente destinado a estudiantes computables, o es la clase inaprendible por un estudiante computable?
Notas
- ^ " 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, ...}.
- ^ es decir, presentación de texto, donde la cadena dada por el maestro es una función recursiva primitiva del número de paso actual, y el alumno codifica una conjetura de idioma como un programa que enumera el idioma
- ^ es decir, la clase de lenguajes que son decidibles porfunciones recursivas primitivas
- ^ es decir, que contiene todos los lenguajes finitos y al menos uno infinito
- ^ es decir, presentación de texto, excepto para la configuración de presentación de texto anómala
- ^ es decir, la clase de lenguajes que consta de una sola cadena (se mencionan aquí solo como un límite inferior común para lenguajes finitos y lenguajes de patrones)
- ^ incomparable a la clase de lenguaje regular y sin contexto: Teorema 3.10, p.53
Referencias
- ^ Oro, E. Mark (1964). Identificación del idioma en el límite (Memorando de investigación RAND RM-4136-PR). Corporación RAND.
- ^ 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 .
- ^ p.457
- ^ Teorema I.8, I.9, p.470-471
- ^ Teorema I.6, p.469
- ↑ Teorema I.3, p.467
- ^ 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 .
- ^ a b p.121 arriba
- ^ p.123 arriba
- ^ Tabla 1, p.452, en (Gold 1967)
- ^ Dana Angluin (1980). "Encontrar patrones comunes a un conjunto de cadenas". Revista de Ciencias de la Computación y Sistemas . 21 : 46–62. doi : 10.1016 / 0022-0000 (80) 90041-0 .
- ^ p.123 mediados
- ^ p.123 bot, Corolario 2
- ^ a b Andris Ambainis; Sanjay Jain; Arun Sharma (1997). "Complejidad del cambio de mente ordinal de la identificación del idioma" (PDF) . Teoría del aprendizaje computacional . LNCS. 1208 . Saltador. págs. 301–315.; aquí: Prueba del corolario 29
- ^ a b Motoki, Shinohara y Wright (1991) "La definición correcta de elasiticidad finita: corrección de errores para la identificación de uniones" , Proc. Cuarto Taller de Teoría del Aprendizaje Computacional, 375-375
- ^ Wright, Keith (1989) " Identificación de uniones de lenguas extraídas de una clase identificable ". Proc. 2º Taller de Teoría del Aprendizaje Computacional, 328-333; con corrección en: [15]