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.

Capacidad de aprendizaje editar

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.

Ejemplos editar

Presentación completa por petición
	Profesor	Aprendiz
		Suposición
0.	abab
1.	yes	abab	baba
2.	yes	a(ba)b	aa
3.	no	(ab)(ba)(ab)(ba)*	bababa
4.	yes	(ab+ba)*	babb
5.	no	(ab+ba)*	baaa
...	.

Presentación completa por revelación
	Profesor	Aprendiz
1.	abab	abab
2.	baba	a(ba)b
3.	aa	(ab)(ba)(ab)(ba)*
4.	bababa	(ab+ba)*
5.	~~babb~~	(ab+ba)*
6.	~~baaa~~	(ab+ba)*
7.	ε	(ab+ba)*
...	...

Unión-suposición
	Profesor	Aprendiz
1.	abab	abab
2.	ba	abab+ba
3.	baba	abab+ba+baba
4.	ba	abab+ba+baba
5.	baba	abab+ba+baba
6.	abab	abab+ba+baba
7.	ε	abab+ba+baba+ε
...	...

Presentación por texto
	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)*
...	...

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]
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.
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.
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.

Caracterización de capacidad de aprendizaje editar

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]

Clases de lenguajes aprendibles en el límite editar

Líneas divisoras entre clases de lenguajes aprendibles y no aprendibles^[9]
Modelos de aprendizajes	Clases de lenguajes
Presentación por texto análogo^{[note 1]}
	Recursivamente enumerable
	Recursivo
Presentación completa
	Primitivo recursivo^{[note 2]}
	Sensible al contexto
	Libre de contexto
	Regular
	Super finito^{[note 3]}
Presentación por texto normal^{[note 4]}
	Finito
	Singleton^{[note 5]}

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.

Condiciones suficientes para capacidad de aprendizaje editar

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.

Espesor finito editar

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]

Elasticidad finita editar

Una clase de lenguajes se dice que tiene elasticidad finita si para cada secuencia infinita de cadenas $s_{0},s_{1},...$ y cada secuencia infinita de lenguajes en la clase $L_{1},L_{2},...$ , existe un número finito n tal que $s_{n}\not \in L_{n}$ implica que $L_{n}$ es inconsistente con $\{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.

Límite de cambio de idea editar

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

Otros conceptos editar

Propiedad de cruzamiento infinito editar

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

$T_{1}\subset T_{2}\subset ...$ ,
$T_{i}\in L_{i}$ ,
$T_{i+1}\not \in L_{i}$ , and
$\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.

Relaciones entre los conceptos editar

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.

Preguntas abiertas editar

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?

Notas editar

↑ i.e. presentación por texto, donde la cadena de caracteres dada por el profesor es una función primitiva recursiva del número de paso actual, y el aprendiz codifica una suposición de lenguaje como un programa que enumera el lenguaje
↑ i.e. la clase de lenguajes que son decidibles por una función primitiva recursiva
↑ i.e. contiene todos los lenguajes finitos y al menos un lenguaje infinito
↑ i.e. presentación por texto, excepto para la configuración presentación por texto anómalo
↑ i.e. la clase de lenguajes consistente en solo una cadena de caracteres

Referencias editar

↑ Gold, E. Mark (1967). «Language identification in the limit». Information and Control 10 (5): 447-474. doi:10.1016/S0019-9958(67)91165-5.
↑ p.457
↑ Theorem I.8,I.9, p.470-471
↑ Theorem I.6, p.469
↑ Theorem I.3, p.467
↑ Dana Angluin (1980). «Inductive Inference of Formal Languages from Positive Data». Information and Control 45: 117-135. doi:10.1016/S0019-9958(80)90285-5.
↑ ^a ^b p.121 top
↑ p.123 top
↑ Table 1, p.452, in (Gold 1967)
↑ Dana Angluin (1980). «Finding Patterns Common to a Set of Strings». Journal of Computer and System Sciences 21: 46-62. doi:10.1016/0022-0000(80)90041-0.
↑ p.123 mid
↑ p.123 bot, Corollary 2
↑ ^a ^b Andris Ambainis; Sanjay Jain; Arun Sharma (1997). «Ordinal mind change complexity of language identification». Computational Learning Theory. LNCS 1208. Springer. pp. 301-315. ; here: Proof of Corollary 29
↑ ^a ^b Motoki, Shinohara, and Wright (1991) "The correct definition of finite elasiticity: corrigendum to identification of unions", Proc. 4th Workshop on Computational Learning Theory, 375-375
↑ Wright, Keith (1989) "Identification of Unions of Languages Drawn from an Identifiable Class". Proc. 2nd Workwhop on Computational Learning Theory, 328-333; with correction in:^[14]

Datos: Q16248789

[anomalous_text-10] .e. presentación por texto, donde la cadena de caracteres dada por el profesor es una función primitiva recursiva del número de paso actual, y el aprendiz codifica una suposición de lenguaje como un programa que enumera el lenguaje

[11] .e. la clase de lenguajes que son decidibles por una función primitiva recursiva

[12] .e. contiene todos los lenguajes finitos y al menos un lenguaje infinito

[13] .e. presentación por texto, excepto para la configuración presentación por texto anómalo

[14] .e. la clase de lenguajes consistente en solo una cadena de caracteres

[1] Gold, E. Mark (1967). «Language identification in the limit». Information and Control 10 (5): 447-474. doi:10.1016/S0019-9958(67)91165-5.

[2] .457

[3] Theorem I.8,I.9, p.470-471

[4] Theorem I.6, p.469

[5] Theorem I.3, p.467

[6] Dana Angluin (1980). «Inductive Inference of Formal Languages from Positive Data». Information and Control 45: 117-135. doi:10.1016/S0019-9958(80)90285-5.

[Angluin.1980a.Cond1-7] .121 top

[8] .123 top

[9] Table 1, p.452, in (Gold 1967)

[15] Dana Angluin (1980). «Finding Patterns Common to a Set of Strings». Journal of Computer and System Sciences 21: 46-62. doi:10.1016/0022-0000(80)90041-0.

[16] .123 mid

[17] .123 bot, Corollary 2

[Ambainis.Jain.Sharma.1997.Cor29-18] Andris Ambainis; Sanjay Jain; Arun Sharma (1997). «Ordinal mind change complexity of language identification». Computational Learning Theory. LNCS 1208. Springer. pp. 301-315. ; here: Proof of Corollary 29

[Motoki.Shinohara.Wright.1991-19] Motoki, Shinohara, and Wright (1991) "The correct definition of finite elasiticity: corrigendum to identification of unions", Proc. 4th Workshop on Computational Learning Theory, 375-375

[20] Wright, Keith (1989) "Identification of Unions of Languages Drawn from an Identifiable Class". Proc. 2nd Workwhop on Computational Learning Theory, 328-333; with correction in:^[14]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[note 1]

[note 2]

[note 3]

[note 4]

[note 5]

[10]

[11]

[12]

[13]

[14]

[15]