Estudio de la Mezcla de Estados Determinista y No Determinista en el Dise˜no de Algoritmos para Inferencia Gramatical de Lenguajes Regulares

Gloria In´es Alvarez Vargas Director: Dr. D. Pedro Garc´ıa G´omez

Tesis Doctoral.

Programa Doctoral en Reconocimiento de Formas e Inteligencia Artificial Departamento de Sistemas Inform´aticos y Computaci´on, DSIC Universidad Polit´ecnica de Valencia

Valencia, Mayo de 2007

2

´Indice general 1. El Problema de la Inferencia Gramatical. 1.1. Definiciones B´ asicas . . . . . . . . . . . . . . . . . . . . . . . . . 1.2. Modelo de Aprendizaje . . . . . . . . . . . . . . . . . . . . . . . . 1.3. Aut´ omatas Finitos Residuales . . . . . . . . . . . . . . . . . . . .

3 5 9 10

2. Antecedentes 19 2.1. Antecedentes en Inferencia Gramatical de Lenguajes Regulares . 19 2.1.1. Variaciones del Orden en la Mezcla de Estados . . . . . . 22 2.1.2. La Inferencia Gramatical como Problema de B´ usqueda . . 23 2.2. Modelos de Aprendizaje . . . . . . . . . . . . . . . . . . . . . . . 26 2.3. Antecedentes en cuanto a Evaluaci´ on de Algoritmos de Inferencia Gramatical . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.3.1. T´ecnicas de Generaci´ on de Aut´ omatas Aleatorios . . . . . 30 2.3.2. Criterios de Evaluaci´ on para Algoritmos de Inferencia Gramatical . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3. La Mezcla de Estados 32 3.1. Relaciones de Inclusi´ on . . . . . . . . . . . . . . . . . . . . . . . . 32 ´ 3.1.1. El Arbol de Mezcla . . . . . . . . . . . . . . . . . . . . . . 33 3.1.2. Duplicaci´ on de Transiciones . . . . . . . . . . . . . . . . . 34 3.1.3. Definici´ on de Valores de Salida . . . . . . . . . . . . . . . 35 3.2. El Mecanismo B´ asico de Mezcla de Estados . . . . . . . . . . . . 38 3.3. La Mezcla No-Determinista de Estados . . . . . . . . . . . . . . . 40 3.4. Importancia del Orden de Mezcla . . . . . . . . . . . . . . . . . . 42 3.5. Convergencia de la Mezcla de Estados . . . . . . . . . . . . . . . 44 3.5.1. Convergencia de la Mezcla de Estados en M´ aquinas Deterministas . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.5.2. Convergencia de la Mezcla de Estados en M´ aquinas No Deterministas . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.6. Sumario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 4. Algoritmos Propuestos 4.1. Algoritmos B´ asicos . . . . . . . . . . . 4.1.1. Algoritmo RPNI . . . . . . . . 4.1.2. Algoritmos de Gold y DeLeTe2 4.1.3. Programa DeLeTe2 . . . . . . 4.2. Mezcla Determinista . . . . . . . . . . 4.2.1. Algoritmo IRPNI1 . . . . . . . i

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

59 59 59 61 65 72 72

4.2.2. Algoritmo IRPNI2 4.2.3. Algoritmo RBIR . 4.2.4. Algoritmo RRB . 4.3. Mezcla No Determinista . 4.3.1. Algoritmo NRPNI 4.3.2. Algoritmo MRIA . 4.4. Sumario . . . . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

75 80 83 84 84 88 94

5. Resultados Experimentales 96 5.1. Datos de Entrenamiento y Prueba . . . . . . . . . . . . . . . . . 96 5.1.1. Corpus Utilizado para Evaluar el Algoritmo DeLeTe2 . . 97 5.1.2. Corpus Utilizado para Evaluar Unambiguous Finite Automata (UFAs) . . . . . . . . . . . . . . . . . . . . . . . . 99 5.1.3. Primer Corpus Extendido . . . . . . . . . . . . . . . . . . 100 5.1.4. Segundo Corpus Extendido . . . . . . . . . . . . . . . . . 100 5.1.5. Corpus de DFAs Aleatorios . . . . . . . . . . . . . . . . . 101 5.2. Resultados Experimentales . . . . . . . . . . . . . . . . . . . . . 102 5.2.1. Mezcla Determinista, Experimentos con Algoritmos IRPNI1 e IRPNI2 . . . . . . . . . . . . . . . . . . . . . . . . 103 5.2.2. Mezcla Determinista, Experimentos con el Algoritmo RBIR113 5.2.3. Mezcla Determinista, Experimentos con el Algoritmo RRB 117 5.2.4. Mezcla No Determinista, Experimentos con el Algoritmo NRPNI . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 5.2.5. Mezcla No Determinista, Experimentos con el Algoritmo MRIA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 5.3. Sumario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 6. Conclusiones

136

ii

´Indice de figuras 1.1. 1.2. 1.3. 1.4.

Ejemplo de la Notaci´ on Usada para Dibujar M´ aquinas de Moore Ejemplo de Aut´ omatas RFSA . . . . . . . . . . . . . . . . . . . . Ejemplo de Construcci´ on del RFSA Can´ onico, Aut´ omata Inicial . ´ Ejemplo de Construcci´ on del RFSA Can´ onico, Arbol de Inclusiones entre Estados . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5. Ejemplo de Construcci´ on del RFSA Can´ onico, Aut´ omata Despu´es de Eliminar el Estado Compuesto 8 . . . . . . . . . . . . . . 1.6. Ejemplo de Construcci´ on del RFSA Can´ onico, Aut´ omata Final .

8 12 14

´ 3.1. Ejemplo de Arbol de Mezcla, M´ aquina de Moore Inicial . . . . . ´ 3.2. Ejemplo de Arbol de Mezcla . . . . . . . . . . . . . . . . . . . . . 3.3. Esquema de Inclusi´ on entre Estados 1 . . . . . . . . . . . . . . . ´ 3.4. Ejemplo de Detecci´ on de Relaciones de Inclusi´ on, Arbol de Mezcla 3.5. Esquema de Inclusi´ on entre Estados 2 . . . . . . . . . . . . . . . 3.6. Ejemplo de Definici´ on de Valores de Salida, Aut´ omata Inicial . . ´ 3.7. Ejemplo de Definici´ on de Valores de Salida, Arbol de Mezcla . . 3.8. Ejemplo de Definici´ on de Valores de Salida, Aut´ omata Final . . . 3.9. Ejemplo de Mezcla de Estados, Aut´ omata Inicial . . . . . . . . . 3.10. Ejemplo de Mezcla de Estados, Aut´ omata resultante . . . . . . . 3.11. Ejemplo de Mezcla de Estados, Aut´ omata Resultante con Propagaci´ on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.12. Ejemplo de Mezcla de Estados No Determinista, Aut´ omata Inicial 3.13. Ejemplo de Mezcla de Estados No Determinista, Aut´ omata Resultante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.14. Ejemplo Convergencia de la Mezcla en DFAs, DFA M´ınimo del Lenguaje Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . ´ 3.15. Ejemplo Convergencia de la Mezcla en DFAs, Arbol de Prefijos de Moore de la Muestra de Entrada . . . . . . . . . . . . . . . . ´ 3.16. Ejemplo Convergencia de la Mezcla en DFAs, Arbol de Prefijos de Moore Extendido . . . . . . . . . . . . . . . . . . . . . . . . . ´ 3.17. Ejemplo Convergencia de la Mezcla en DFAs, Arbol de Prefijos de Moore que Entra al Algoritmo de Mezcla . . . . . . . . . . . . 3.18. Ejemplo Convergencia de la Mezcla en DFAs, Aut´ omata Intermedio 3.19. Ejemplo Convergencia de la Mezcla en DFAs, Resultado del Algoritmo de Mezcla . . . . . . . . . . . . . . . . . . . . . . . . . . ´ 3.20. Ejemplo Convergencia de la Mezcla en DFAs, Otro Arbol de Prefijos de Moore Extendido . . . . . . . . . . . . . . . . . . . . . . 3.21. Ejemplo Convergencia de la Mezcla en DFAs, Aut´ omata Intermedio 3.22. Convergencia de la Mezcla en NFAs, DFA y Aut´ omata Universal

33 34 34 35 36 37 37 38 39 39

iii

16 17 17

39 42 42 47 47 47 48 48 48 49 49 51

3.23. Ejemplo Convergencia de la Mezcla en NFAs, Trellis de Caminos de Aceptaci´ on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.24. Ejemplo Convergencia de la Mezcla en NFAs, Subaut´ omata Inducido . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.25. Ejemplo Convergencia de la Mezcla en NFAs, AM (aaa). . . . . . 3.26. Ejemplo Convergencia de la Mezcla en NFAs, Resultado de Aplicar una Partici´ on que Acepta L . . . . . . . . . . . . . . . . . . . 3.27. Ejemplo Convergencia de la Mezcla en NFAs, Resultado de una Partici´ on Luego de Adicionar la Muestra Positiva bbbb . . . . . . 3.28. Ejemplo Algoritmo OIL, Aut´ omata Determinista M´ınimo y Aut´ omata Universal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.29. Ejemplo Algoritmo OIL, Tres Posibles Salidas . . . . . . . . . . . 4.1. Ejemplo Algoritmo RPNI . . . . . . . . . . . . . . . . . . . . . . ´ 4.2. Ejemplo DeLeTe2, Arbol Aceptor de Prefijos de la Muestra de Entrada D+ ∪ D− . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3. Ejemplo DeLeTe2, Aut´ omata luego de Mezclar los Estados Equivalentes 2 w 3, 4 w 6 y 5 w 7 . . . . . . . . . . . . . . . . . . . . 4.4. Ejemplo DeLeTe2, Aut´ omata luego de Mezclar los Estados Equivalentes 1 w 4 y 2 w 8 . . . . . . . . . . . . . . . . . . . . . . . . 4.5. Ejemplo DeLeTe2, Respuesta Final . . . . . . . . . . . . . . . . . ´ 4.6. Ejemplo del Algoritmo IRPNI1, Arbol de Prefijos de Moore Inicial 4.7. Ejemplo IRPNI1, M´ aquina de Moore Intermedia . . . . . . . . . 4.8. Ejemplo IRPNI1, M´ aquina de Moore Final . . . . . . . . . . . . 4.9. Ejemplo de la Subrutina definirEstados, M´ aquina de Moore Inicial ´ 4.10. Ejemplo de la Subrutina definirEstados, Arbol de Mezcla . . . . ´ 4.11. Ejemplo del Algoritmo IRPNI2, Arbol de Prefijos de Moore Inicial 4.12. Ejemplo del Algoritmo IRPNI2, M´ aquina de Moore Intermedia . ´ 4.13. Ejemplo del Algoritmo IRPNI2, Arbol de Mezcla de los Estados 0y3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.14. Ejemplo del Algoritmo IRPNI2, M´ aquina de Moore Intermedia . 4.15. Ejemplo del Algoritmo IRPNI2, M´ aquina de Moore Intermedia . 4.16. Ejemplo del Algoritmo IRPNI2, M´ aquina de Moore Intermedia . 4.17. Ejemplo del Algoritmo IRPNI2, M´ aquina de Moore Final . . . . 4.18. Ejemplo Algoritmo NRPNI, Paso Inicial . . . . . . . . . . . . . . 4.19. Ejemplo Algoritmo NRPNI, Caminos de Longitud M´ınima . . . . ´ 4.20. Ejemplo Algoritmo NRPNI, Arbol de Prefijos de Moore . . . . . 4.21. Ejemplo Algoritmo NRPNI, Hip´ otesis Generadas . . . . . . . . . ´ 4.22. Ejemplo Algoritmo MRIA, Arbol de Prefijos de Moore de D+ . . 4.23. Ejemplo Algoritmo MRIA, Comparaciones Entre los Estados 0 y 1 4.24. Ejemplo Algoritmo MRIA, M´ aquinas de Moore Intermedias . . . 4.25. Ejemplo Algoritmo MRIA, Hip´ otesis Emitidas por MRIA . . . .

52 52 52 53 54 57 58 61 68 70 70 72 74 74 74 77 77 78 78 78 79 79 79 79 84 84 88 88 92 93 93 93

5.1. Formato de los Archivos de Muestras . . . . . . . . . . . . . . . . 96 5.2. Formato de los Archivos de Aut´ omatas . . . . . . . . . . . . . . . 97 5.3. Comparaci´ on de Tasas de Reconocimiento Promedio entre RPNI, IRPNI2 IRPNI1 y DeLeTe2 en el Corpus de DeLeTe2 . . . . . . 105 5.4. Comparaci´ on de Tama˜ no Promedio de Hip´ otesis entre RPNI, IRPNI2 IRPNI1 y DeLeTe2 en el Corpus de DeLeTe2 . . . . . . 106 iv

5.5. Comparaci´ on de Tasas de Reconocimiento Promedio entre RPNI, IRPNI2 y DeLeTe2 en el Corpus Extendido1 . . . . . . . . . . . 5.6. Comparaci´ on de Tama˜ no Promedio de Hip´ otesis entre RPNI, IRPNI2 y DeLeTe2 en el Corpus Extendido1 . . . . . . . . . . . 5.7. Comparaci´ on de Tasas de Reconocimiento Promedio entre RPNI, IRPNI2 y DeLeTe2 en el Corpus Extendido2 . . . . . . . . . . . 5.8. Comparaci´ on de Tama˜ no Promedio de Hip´ otesis entre RPNI, IRPNI2 y DeLeTe2 en el Corpus Extendido2 . . . . . . . . . . . 5.9. Comparaci´ on de Tasas de Reconocimiento Promedio entre redBlue, RBIRX, RBIRZ e IRPNI2 en el Corpus Extendido2 . . . . 5.10. Comparaci´ on de Tama˜ no Promedio de Hip´ otesis entre redBlue, RBIRX, RBIRZ e IRPNI2 en el Corpus Extendido2 . . . . . . . 5.11. Comparaci´ on de Tasas de Reconocimiento Promedio entre redBlue, RRB e IRPNI2 en el Corpus Extendido2 . . . . . . . . . . 5.12. Comparaci´ on de Tama˜ no Promedio de Hip´ otesis entre redBlue, RRB e IRPNI2 en el Corpus Extendido2 . . . . . . . . . . . . . 5.13. Comparaci´ on de Tasas de Reconocimiento Promedio entre NRPNI, NRPNI2, NRPNI1 y IRPNI2 en el Corpus de DeLeTe2 . . . 5.14. Comparaci´ on de Tama˜ no Promedio de Hip´ otesis entre NRPNI, NRPNI2, NRPNI1 y IRPNI2 en el Corpus de DeLeTe2 . . . . . 5.15. Comparaci´ on de Tasas de Reconocimiento Promedio entre NRPNI, NRPNI2 y IRPNI2 en el Corpus Extendido2 . . . . . . . . . 5.16. Comparaci´ on de Tama˜ no Promedio de Hip´ otesis entre NRPNI, NRPNI2 y IRPNI2 en el Corpus Extendido2 . . . . . . . . . . . 5.17. Comparaci´ on de Tasas de Reconocimiento Promedio entre MRIA y DeLeTe2 en el Corpus de DeLeTe2 . . . . . . . . . . . . . . . . 5.18. Comparaci´ on de Tama˜ no Promedio de Hip´ otesis entre MRIA y DeLeTe2 en el Corpus de DeLeTe2 . . . . . . . . . . . . . . . . . 5.19. Comparaci´ on de Tasas de Reconocimiento Promedio entre MRIA, IRPNI2 y DeLeTe2 en el Corpus Extendido2 . . . . . . . . . . . 5.20. Comparaci´ on de Tama˜ no Promedio de Hip´ otesis entre MRIA, IRPNI2 y DeLeTe2 en el Corpus Extendido2 . . . . . . . . . . .

v

108 109 111 112 115 116 118 119 121 122 124 125 127 128 132 133

vi

´Indice de cuadros 1.1. Ejemplo de Construcci´ on del RFSA Can´ onico, Aut´ omata Inicial . 1.2. Ejemplo de Construcci´ on del RFSA Can´ onico, R(A) en Representaci´ on de Tabla . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3. Ejemplo de Construcci´ on del RFSA Can´ onico, D(R(A)) en Representaci´ on de Tabla . . . . . . . . . . . . . . . . . . . . . . . . 1.4. Ejemplo de Construcci´ on del RFSA Can´ onico, Matriz B´ asica . .

15 15 15 16

3.1. Trellis de una Mezcla no Determinista . . . . . . . . . . . . . . . 3.2. Ejemplo Convergencia de la Mezcla en DFAs, Enumeraci´ on E de Σ∗ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3. Ejemplo Convergencia de la Mezcla en DFAs, Otra Enumeraci´ on E de Σ∗ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

4.1. 4.2. 4.3. 4.4.

68 68 69

Algoritmo DeLeTe2, Transitividad de las Relaciones de Inclusi´ on 1 Algoritmo DeLeTe2, Transitividad de las Relaciones de Inclusi´ on 2 Ejemplo Algoritmo DeLeTe2, Relaciones de Inclusi´ on Iniciales . . Ejemplo Algoritmo DeLeTe2, Tabla de Relaciones de Inclusi´ on en Estado Intermedio 1 . . . . . . . . . . . . . . . . . . . . . . . 4.5. Ejemplo Algoritmo DeLeTe2, Tabla de Relaciones de Inclusi´ on en Estado Intermedio 2 . . . . . . . . . . . . . . . . . . . . . . . 4.6. Ejemplo Algoritmo DeLeTe2, Tabla de Relaciones de Inclusi´ on en Estado Intermedio 3 . . . . . . . . . . . . . . . . . . . . . . .

5.1. Comparaci´ on de Tasas de Reconocimiento Promedio entre MAYOR´ IA, RPNI y DeLeTe2 en el Corpus de DeLeTe2 . . . . . . . 5.2. Comparaci´ on de Tasas de Reconocimiento Promedio entre MAYOR´ IA, RPNI y DeLeTe2 en el Corpus Extendido2. . . . . . . . 5.3. Comparaci´ on de Tasas de Reconocimiento y Tama˜ no Promedio de las Hip´ otesis entre RPNI, IRPNI2, IRPNI1 y DeLeTe2 en el Corpus de DeLeTe2 . . . . . . . . . . . . . . . . . . . . . . . . . 5.4. Comparaci´ on de Tasas de Reconocimiento y Tama˜ no Promedio de las Hip´ otesis entre RPNI, IRPNI2 y DeLeTe2 en el Corpus Extendido1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5. Comparaci´ on de Tasas de Reconocimiento y Tama˜ no Promedio de las Hip´ otesis entre RPNI, IRPNI2 y DeLeTe2 en el Corpus Extendido2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.6. Comparaci´ on de Tasas de Reconocimiento y Tama˜ no Promedio de las Hip´ otesis entre redBlue, IRPNI2, RBIRX y RBIRZ en el Corpus Extendido2 . . . . . . . . . . . . . . . . . . . . . . . . . . vii

47 49

70 71 71 99 101

103

107

110

113

5.7. Comparaci´ on de Tasas de Reconocimiento y Tama˜ no Promedio de las Hip´ otesis entre redBlue, RRB y IRPNI2 en el Corpus Extendido2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 5.8. Comparaci´ on de Tasas de Reconocimiento y Tama˜ no Promedio de las Hip´ otesis entre NRPNI, NRPNI2, NRPNI1 y IRPNI2 en el Corpus de DeLeTe2 . . . . . . . . . . . . . . . . . . . . . . . . 120 5.9. Comparaci´ on de Tasas de Reconocimiento y Tama˜ no Promedio de las Hip´ otesis entre NRPNI, NRPNI2 y IRPNI2 en el Corpus Extendido2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 5.10. Comparaci´ on de Tasas de Reconocimiento y Tama˜ no Promedio de las Hip´ otesis entre MRIA y DeLeTe2 en el Corpus de DeLeTe2 126 5.11. Comparaci´ on de Tasas de Reconocimiento Promedio entre MRIA y DeLeTe2 con Probabilidades PI y PF Menores o Iguales a 0,1 en los Experimentos NFA del Corpus de DeLeTe2 . . . . . . . . . 129 5.12. Comparaci´ on de Tasas de Reconocimiento Promedio entre MRIA y DeLeTe2 con Probabilidades PI y PF Superiores a 0,1 en los Experimentos NFA del Corpus de DeLeTe2 . . . . . . . . . . . . 130 5.13. Comparaci´ on de Tasas de Reconocimiento y Tama˜ no Promedio de las Hip´ otesis entre MRIA, IRPNI2 y DeLeTe2 en el Corpus Extendido2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130

viii

´Indice de algoritmos 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31.

Algoritmo para construir el RFSA Can´ onico . Algoritmo EDSM . . . . . . . . . . . . . . . . Algoritmo redBlue . . . . . . . . . . . . . . . Algoritmo exbar . . . . . . . . . . . . . . . . Subrutina exhSearch . . . . . . . . . . . . . . ´ Subrutina para Construir un Arbol de Mezcla Subrutina incluido . . . . . . . . . . . . . . . Subrutina definirValoresSalida . . . . . . . . Subrutina merge . . . . . . . . . . . . . . . . Subrutina detmerge . . . . . . . . . . . . . . . Subrutina nodetmerge . . . . . . . . . . . . . Subrutina muestraCaracteristica . . . . . . . Subrutina mergeDfas . . . . . . . . . . . . . . Algoritmo OIL . . . . . . . . . . . . . . . . . Subrutina mergeNfas . . . . . . . . . . . . . . Algoritmo RPNI . . . . . . . . . . . . . . . . Algoritmo de Gold . . . . . . . . . . . . . . . Algoritmo DeLeTe2 . . . . . . . . . . . . . . Algoritmo del Programa DeLeTe2 . . . . . . Algoritmo IRPNI1 . . . . . . . . . . . . . . . Algoritmo IRPNI2 . . . . . . . . . . . . . . . Subrutina tryInclusion . . . . . . . . . . . . . Subrutina definirEstados . . . . . . . . . . . . Algoritmo RBIR . . . . . . . . . . . . . . . . Modificaci´ on al Algoritmo 24 . . . . . . . . . Algoritmo RRB . . . . . . . . . . . . . . . . . Algoritmo NRPNI . . . . . . . . . . . . . . . Subrutina podar . . . . . . . . . . . . . . . . Algoritmo MRIA . . . . . . . . . . . . . . . . Subrutina compare . . . . . . . . . . . . . . . Subrutina nmerge . . . . . . . . . . . . . . .

ix

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14 23 23 24 25 33 35 37 38 40 41 45 46 55 56 60 62 63 67 73 75 76 76 81 82 83 85 86 89 90 91

x

Introducci´ on El problema de la inferencia gramatical consiste en recibir como entrada cadenas de s´ımbolos etiquetadas como pertenecientes (positivas) o no (negativas) a un lenguaje formal y producir como salida una representaci´ on del lenguaje formal que etiquet´ o dichas cadenas. El dise˜ no de algoritmos de inferencia gramatical, que es el tema fundamental en esta investigaci´ on, pretende desarrollar m´etodos eficaces y eficientes para realizar dicho proceso. La caracter´ıstica m´ as importante de un algoritmo de inferencia es su convergencia en el l´ımite; es decir, su capacidad para identificar, luego de un n´ umero finito de intentos, en forma correcta y definitiva el lenguaje representado por las muestras. En la medida que el algoritmo recibe mayor cantidad de cadenas de entrada es m´ as factible que realice la identificaci´ on exacta, cuando no lo logra el algoritmo propone una respuesta aproximada. La inferencia gramatical es un problema que ha venido despertando mucho inter´es en la comunidad acad´emica, debido no s´ olo a sus caracter´ısticas te´ oricas sino a la amplia gama de posibles aplicaciones que tiene, de la Higuera [dlH05] menciona entre otras: la rob´ otica, los sistemas de control, el reconocimiento estructural de patrones, la lig¨ u´ıstica computacional, el modelamiento del habla, la traducci´ on autom´ atica, la biolog´ıa computacional, el manejo de documentos, la compresi´ on de datos y la b´ usqueda de conocimiento en bases de datos (en ingl´es data mining). Aunque ya existe mucho terreno adelantado gracias a a˜ nos de estudio, todav´ıa queda trabajo por hacer, sobre todo si se tiene en cuenta que el problema de encontrar el DFA m´ as peque˜ no que reconoce un conjunto de muestras positivas y negativas es un problema NP-Completo y que en la pr´ actica es necesario realizar la inferencia en el menor tiempo posible, necesitando la menor cantidad de datos posible y generando hip´ otesis tan peque˜ nas y exactas como sea posible. Existen varias aproximaciones a la soluci´ on del problema de la inferencia gramatical; por ejemplo, se hace inferencia mediante mezcla de estados [OG92, LPP98]; se usan aut´ omatas deterministas estoc´ asticos [CO94]; se aplica aprendizaje activo, es decir, aquel que aporta informaci´ on adicional al proceso de inferencia en la forma de un or´ aculo o maestro informado que participa en el proceso cuando el algoritmo as´ı lo requiere [PH97, PH00, Ang87, Ang90, Ang92]; se incorpora informaci´ on sobre el contexto del que provienen las muestras [CFKdlH04]; y tambi´en se usan t´ecnicas de inteligencia computacional como redes neuronales, algoritmos gen´eticos [DMV94] o programaci´ on evoluti1

va [LR05]. Este trabajo centra su inter´es en el estudio de la mezcla de estados como elemento principal de los algoritmos de inferencia gramatical, considerando tanto la inferencia de modelos deterministas como no deterministas, buscando proponer algoritmos con el mejor desempe˜ no sobre muestras de prueba y que produzcan hip´ otesis lo m´ as peque˜ nas posible. En el Cap´ıtulo 1 se describe en m´ as detalle el problema y la hip´ otesis de investigaci´ on, se proponen definiciones b´ asicas y la notaci´ on a utilizar, se presenta el modelo de aprendizaje y se describen los RFSA (Residual Finite State Automata) que son una clase de aut´ omata no determinista que ser´ a utilizada intensivamente en esta investigaci´ on. Luego, en el Cap´ıtulo 2, se hace un recuento de los trabajos m´ as importantes que se conocen en el a ´mbito de la inferencia gramatical de lenguajes regulares haciendo ´enfasis en los trabajos relacionados con algoritmos de mezcla de estados, tambi´en se reportan antecedentes en cuanto a modelos de aprendizaje y a la evaluaci´ on emp´ırica de algoritmos de inferencia gramatical. A continuaci´ on, en el Cap´ıtulo 3 se describen los diferentes tipos de mezcla de estados que se han considerado en este trabajo y tambi´en se presenta la demostraci´ on de que la convergencia de un proceso de mezcla de estados es independiente del orden en que ellas se realizan, tanto en el caso determinista como no determinista. En el Cap´ıtulo 4 se describen algoritmos de inferencia gramatical, en la primera secci´ on se presentan los algoritmos de referencia, ellos no s´ olo han servido como base para algunos de los nuevos algoritmos propuestos, sino que tambi´en se utilizan en la parte experimental como punto de referencia para evaluarlos; en las secciones posteriores se describen los algoritmos de inferencia gramatical que han surgido de este estudio. En el siguiente Cap´ıtulo, el 5, se describen los c´ orpora utilizados para evaluar dichos algoritmos, los resultados de las experimentaciones y se analizan dichos resultados. Finalmente, en el Cap´ıtulo 6 se concluye y se proponen l´ıneas de trabajo futuro.

2

Cap´ıtulo 1

El Problema de la Inferencia Gramatical. El problema de la inferencia gramatical se puede plantear como el de aprender una funci´ on desconocida a partir de algunos de los valores que produce. M´ as exactamente, consiste en construir, ojal´ a en forma eficiente, una representaci´ on de un lenguaje objetivo a partir de un conjunto muestras de entrada. El lenguaje objetivo es un lenguaje formal, definido sobre un alfabeto finito, que en este estudio ser´ a siempre un lenguaje regular. La entrada del problema est´ a formada por un conjunto no vac´ıo de muestras positivas y un conjunto, que puede ser vac´ıo, de muestras negativas. Las muestras positivas son cadenas de s´ımbolos del alfabeto del lenguaje, que pertenecen al lenguaje objetivo y las negativas cadenas que pertenecen al complemento de dicho lenguaje objetivo. La representaci´ on resultante de la inferencia puede expresarse de diversas maneras, en este estudio dicha representaci´ on ser´ a un aut´ omata finito. Este estudio asume el modelo de aprendizaje de Gold (ver Secci´ on 1.2) y lo aplica al dise˜ no de algoritmos de inferencia gramatical para lenguajes regulares, con el objetivo de lograr mejores tasas de acierto en muestras de prueba y menores tama˜ nos de las hip´ otesis que los obtenidos con los mejores algoritmos actuales. Se procede bajo la hip´ otesis de que utilizar NFAs como modelo de representaci´ on, puede mejorar la velocidad de convergencia, la tasa de acierto y/o disminuir el tama˜ no de las hip´ otesis obtenidas durante el proceso de inferencia gramatical de algunas subclases de lenguajes regulares. La hip´ otesis surge de un estudio inicial en el que se implementa una versi´ on del algoritmo RPNI con mezcla no determinista, all´ı se logra constatar que la generaci´ on de hip´ otesis no deterministas abre nuevas posibilidades con respecto a la inferencia de aut´ omatas deterministas. Algunos antecedentes cercanos, como los trabajos de Denis et. al. [DLT04], que muestran resultados exitosos, refuerzan el inter´es inicial. Esta investigaci´ on se interesa en particular por el estudio de los aut´ omatas residuales y las relaciones de inclusi´ on entre estados; esta teor´ıa se aprovecha tanto para construir algoritmos de inferencia que obtienen aut´ omatas deterministas como algoritmos que obtienen aut´ omatas no deterministas. A partir de estos algoritmos y de manera fundamentalmente ex3

perimental se busca validar o refutar la hip´ otesis. Existen importantes resultados te´ oricos que establecen la dificultad de la tarea de la inferencia gramatical: Gold demostr´ o que es posible identificar en el l´ımite lenguajes regulares a partir de muestras positivas y negativas [Gol67]; en cambio si s´ olo se dispone de muestras positivas la identificaci´ on es imposible para cualquier clase super-finita de lenguajes [Gol67]. Para lenguajes en categor´ıas m´ as altas de la jerarqu´ıa de Chomsky no se garantiza la identificaci´ on [Gol67]. En cuanto a la complejidad de las soluciones para el problema de la inferencia gramatical, tambi´en se conocen resultados importantes: se puede encontrar un aut´ omata determinista consistente con un conjunto de muestras positivas y negativas dadas en tiempo polinomial, pero encontrar el aut´ omata determinista m´ as peque˜ no posible es un problema NP-Completo [Gol67]. Buscar un aut´ omata no determinista consistente con un conjunto de muestras positivas y negativas es un problema tratable, pero encontrar un aut´ omata no determinista con el menor n´ umero de estados posible es de nuevo un problema NP-Completo [Gol67]. Aunque en la u ´ltima d´ecada han aparecido algunos trabajos sobre la inferencia de lenguajes regulares mediante aut´ omatas no deterministas (NFAs), este no es un tema en el que abunden las aportaciones. La escasez de trabajos se puede explicar en la mayor complejidad de este enfoque con respecto a la inferencia de aut´ omatas deterministas (DFAs); y el hecho que a pesar de ello est´en surgiendo propuestas se puede explicar en que los NFAs son un modelo de representaci´ on que puede llegar a ser exponencialmente m´ as peque˜ no que los DFAs. A continuaci´ on se profundiza en los problemas que surgen en la inferencia de NFAs y en la importancia de buscarles una soluci´ on. Se sabe que inferir una representaci´ on m´ınima de un lenguaje regular es NP-Completo, y tambi´en se sabe que existen algoritmos que, provistas ciertas condiciones en cuanto a la cantidad y calidad de las muestras de entrenamiento, pueden resolver dicho problema en tiempo polinomial, obteniendo como representaci´ on un DFA. Dichos algoritmos proceden iterativamente, parten de una hip´ otesis muy particular y la van generalizando en tanto las muestras de entrenamiento lo permitan. Este proceso se realiza de manera convergente, es decir, garantizando que despu´es de un n´ umero finito de hip´ otesis equivocadas, se llega a la hip´ otesis correcta. Para que la convergencia tenga sentido, debe existir una representaci´ on “ideal” del lenguaje objetivo, hacia la cual debe fluir el proceso. En el caso de los DFAs, esta representaci´ on es el DFA m´ınimo, es decir, aquel aut´ omata determinista que identifica el lenguaje objetivo y que tiene el menor n´ umero de estados; la teor´ıa dice que cada lenguaje regular tiene asociado un u ´nico DFA m´ınimo. Al pasar a la inferencia de NFAs, y procediendo tambi´en de forma iterativa, se observa que no existe un u ´nico NFA m´ınimo asociado a cada lenguaje regular sino varios NFAs minimales diferentes entre s´ı, esto hace que no haya un u ´nico punto hacia el cual enfocar el proceso de convergencia. En resumen, se tiene que a la dificultad ya conocida de la inferencia en s´ı misma, se suma la dificultad de trabajar con un modelo que no facilita la convergencia. Conocidas las dificultades, alguien podr´ıa preguntarse si vale la pena insistir en la inferencia de NFAs, y efectivamente hay razones para hacerlo: se sabe que 4

un mismo lenguaje puede ser representado mediante muchos DFAs (o NFAs); de todos ellos, normalmente interesa el m´ as peque˜ no, el que tiene menor n´ umero de estados. El hecho que se obtenga la representaci´ on de tama˜ no m´ınimo no significa que dicha representaci´ on sea peque˜ na, y cuando estos tama˜ nos crecen mucho, hacen que la inferencia no sea viable en la pr´ actica, lo cual ocurre desafortunadamente en la mayor´ıa de los problemas reales en los que te´ oricamente ser´ıa de utilidad aplicar inferencia. Dado un lenguaje regular, se sabe que el tama˜ no de los NFAs minimales que lo representan es menor o igual que el tama˜ no del DFA m´ınimo que lo representa; en ocasiones, el n´ umero de estados de un NFA minimal puede ser exponencialmente menor que el del mencionando DFA m´ınimo. Obtener representaciones precisas y a la vez peque˜ nas es una condici´ on necesaria para poder aplicar la inferencia en problemas de tama˜ no real. Una estrategia que se viene siguiendo en los u ´ltimos a˜ nos para realizar inferencia de NFAs, consiste en proponer subclases de NFAs que posean propiedades que faciliten la inferencia. Por ejemplo, en los trabajos de Coste [CF00, CF03b, CF03a], se propone la subclase de los UFAs (Unambiguous Finite Automata) y Denis propone la subclase de los RFSAs (Residual Finite State Automata) [DLT02, DLT04, AGR06]. Estas aproximaciones han sido evaluadas experimentalmente y reportan mejor comportamiento que la inferencia de DFAs para ciertos tipos de lenguajes regulares. El mejor comportamiento puede significar: mayor precisi´ on en la aproximaci´ on al lenguaje objetivo o ´ menor tama˜ no en las hip´ otesis obtenidas. Estas estrategias proponen algoritmos polinomiales, pero de mayor complejidad temporal que los ya existentes para la inferencia de DFAs. Se sabe que existen lenguajes regulares cuya inferencia con NFAs no mejora los resultados obtenidos con DFAs, pero tambi´en se sabe que hay otros lenguajes regulares para los cuales es posible hacer mejoras importantes [DLT04, CF03a]. Durante el resto de este cap´ıtulo se presentan elementos te´ oricos b´ asicos a los que se har´ a referencia en el resto del documento. En la secci´ on 1.1 se presentan las definiciones fundamentales y algunos aspectos de notaci´ on; en la secci´ on 1.2 se hace expl´ıcito el modelo de aprendizaje que sirve de base a este trabajo y en la secci´ on 1.3 se presenta la teor´ıa fundamental acerca de los aut´ omatas finitos residuales (RFSA).

1.1.

Definiciones B´ asicas

A continuaci´ on se proponen algunas definiciones importantes y tambi´en algunas explicaciones sobre la notaci´ on utilizada, para mayor detalle sobre definiciones b´ asicas se puede ver [HMU01]. Sea Σ un alfabeto finito y sea Σ∗ el monoide libre generado por Σ con la concatenaci´ on como operaci´ on interna y ε como elemento neutro. Un lenguaje L sobre Σ es un subconjunto de Σ∗ . Los elementos de L se llaman palabras. La longitud de una palabra w ∈ Σ∗ se denota |w|. Dado x ∈ Σ∗ , si x = uv con u, v ∈ Σ∗ , entonces u (resp. v) se denomina prefijo (resp. sufijo) de x. Pr(L) (resp. Suf(L)) denota el conjunto de prefijos (resp. sufijos) de L. El producto de 5

dos lenguajes L1 , L2 ⊆ Σ∗ se define como: L1 · L2 = {u1 u2 |u1 ∈ L1 ∧ u2 ∈ L2 }. Algunas veces, L1 · L2 se denotar´ a simplemente como L1 L2 . A lo largo de este documento, el orden lexicogr´ afico en Σ∗ se denotar´ a como . Suponiendo que Σ est´ a totalmente ordenado por < y dados u, v ∈ Σ∗ con u = u1 . . . um y v = v1 . . . vn , u  v si y s´ olo si (|u| < |v|) o ´ (|u| = |v| y ∃j, 0 ≤ j < n, m tal que u1 . . . uj = v1 . . . vj y uj+1 < vj+1 ). Un Aut´ omata No Determinista (NFA por su sigla en ingl´es) es una 5-tupla A = (Q, Σ, δ, I, F ) donde Q es el conjunto (finito) de estados, Σ es un alfabeto finito, I ⊆ Q es el conjunto de estados iniciales, F ⊆ Q es el conjunto de estados finales y δ es una funci´ on parcial que va de Q × Σ en 2Q . La extensi´ on de esta funci´ on a palabras tambi´en se denota δ, va de 2Q × Σ∗ en 2Q y se define en la Ecuaci´ on 1.1.

δ({q}, ε) = {q} δ({q}, a) = δ(q, a) δ(Q0 , u) = ∪{δ({q}, u) | q ∈ Q0 } δ({q}, ua) = δ(δ({q}, u), a)

(1.1)

Donde Q0 ⊆ Q, a ∈ Σ, q ∈ Q, u ∈ Σ∗ . Una palabra x es aceptada por A si δ(I, x) ∩ F 6= ∅. El conjunto de palabras aceptadas por A se denota L(A). Un Aut´ omata Determinista (DFA por su sigla en ingl´es) es un NFA tal que |I| = 1 y |δ(q, a)| ≤ 1, ∀q ∈ Q, ∀a ∈ Σ. Un DFA se denota entonces como la tupla A = (Q, Σ, δ, q0, F ), donde Q es el conjunto (finito) de estados, Σ es un alfabeto finito, δ es una funci´ on de Q × Σ en Q, q0 es el u ´nico estado inicial y F ⊆ Q es el conjunto de estados finales. Se dice que un NFA est´ a recortado si y s´ olo si ∀q ∈ Q, ∃w1 ∈ Σ∗ tal que ∗ q ∈ δ(q0 , w1 ) y ∃w2 ∈ Σ tal que δ(q, w2 ) ∩ F 6= ∅. Un estado q es alcanzable mediante una palabra u si q ∈ δ(q0 , u). Dos aut´ omatas son equivalentes si ellos reconocen el mismo lenguaje. Dado un aut´ omata A = (Q, Σ, δ, I, F ) y un conjunto P ⊆ Q, la restricci´ on de A a P es el aut´ omata AP = (P, Σ, δ 0 , I 0 , F 0 ), donde I 0 = I ∩ P , F 0 = F ∩ P y δ 0 es la restricci´ on de δ que va de P × Σ en 2P . Dado un conjunto finito de palabras D+ , el a ´rbol aceptor de prefijos de D+ se define como el aut´ omata A = (Q, Σ, δ, q0 , F ) donde Q = P r(D+ ), q0 = ε, F = D+ y δ(u, a) = ua, ∀u, ua ∈ Q. La derivada de un lenguaje L por una palabra u, tambi´en llamada lenguaje residual de L con respecto a u, o ´ lenguaje por la derecha de L con respecto a u se denota u−1 L y se define como u−1 L = {v ∈ Σ∗ |uv ∈ L}. Un lenguaje residual u−1 L es compuesto si u−1 L = ∪(v−1 L u−1 L) v −1 L. Un lenguaje residual es primo si no es compuesto, es decir, si no puede construirse a partir de la uni´ on de los lenguajes residuales de otros estados.

6

Si A = (Q, Σ, δ, I, F ) es un N F A y q ∈ Q, se define el lenguaje aceptado por A desde el estado q como L(A, q) = {v ∈ Σ∗ |δ(q, v) ∩ F 6= ∅}. El conjunto de los Prefijos m´ as cortos de un lenguaje [OG92] P c(L) = {w|w ∈ P r(L), @v : w −1 L = v −1 L, v  w}. El n´ ucleo de un lenguaje N (L) = {ua|ua ∈ P r(L), u ∈ P c(L)} ∪ {ε}. Sea D ⊂ Σ∗ finito. El aut´ omata maximal para D es el NFA AM (D) = (Q, Σ, δ, I, F ) donde Q = ∪x∈D {(u, v) ∈ Σ∗ × Σ∗ |uv = x}, I = {(λ, x)|x ∈ D}, F = {(x, λ)|x ∈ D} y para (u, av) ∈ Q, δ((u, av), a) = (ua, v). De modo que L(AM (D)) = D. Sea A = (Q, Σ, δ, I, F ) un aut´ omata, sea π una partici´ on de Q y sea B(q, π) el bloque de π que contiene q. El aut´ omata cociente es A/π = (Q0 , Σ, δ 0 , I 0 , F 0 ), donde Q0 = Q/π = {B(q, π)|q ∈ Q}, I 0 = {B ∈ Q0 |B ∩ I 6= ∅}, F 0 = {B ∈ Q0 |B ∩ F 6= ∅} y la funci´ on de transici´ on es B 0 ∈ δ 0 (B, a) si y s´ olo si 0 0 0 ∃q ∈ B, ∃q ∈ B con q ∈ δ(q, a). −1 ∗ Dado un lenguaje L, sea U = {u−1 1 L ∩ ... ∩ uk L|k ≥ 0, u1 , ..., uk ∈ Σ }. El aut´ omata universal [ADN70, Car70, Lom01, Pol05] para L se define como U = (U, Σ, δ, I, F ) con:

I = {q ∈ U|q ⊆ L}. F = {q ∈ U|ε ∈ q}. La funci´ on de transici´ on es tal que q ∈ δ(p, a) si y s´ olo si q ⊆ a−1 p. Seg´ un Carrez [Car70], el aut´ omata universal U = (U, Σ, δ, I, F ) para L ⊆ Σ ∗ tiene las siguientes caracter´ısticas: 1. L(U) = L. 2. Para un aut´ omata A = (Q, Σ,T δA , IA , FA ) tal que L(A) ⊆ L, la funci´ on ϕ : omata homomorfismo. Q → U definida como ϕ(q) = u∈Lq u−1 L es un aut´ Una m´ aquina de Moore es una 6-tupla M = (Q, Σ, B, δ, q0 , Φ), donde Q es el conjunto de estados, Σ (resp. B) es el alfabeto de entrada (resp. salida), δ es una funci´ on parcial que va de Q × Σ en Q, q0 es el estado inicial y Φ es una funci´ on que va de Q en B llamada funci´ on de salida. Una m´ aquina de Moore no determinista, se define de manera similar, excepto que δ va de Q × Σ en 2Q y puede tener m´ as de un estado inicial, siendo I el conjunto de ellos. El aut´ omata asociado a una m´ aquina de Moore M = (Q, Σ, {0, 1}, δ, I, Φ) es A = (Q, Σ, δ, I, F ) donde F = {q ∈ Q|Φ(q) = 1}. La restricci´ on de M a P ⊆ Q es la m´ aquina MP definida an´ alogamente al caso de los aut´ omatas. El comportamiento de M est´ a dado por la funci´ on parcial tM |Σ∗ → B definida como tM (x) = Φ(δ(q0 , x)), para todo x ∈ Σ∗ tal que δ(q0 , x) est´ a definida. Al mostrar en forma gr´ afica una m´ aquina de Moore, el valor de la funci´ on de salida asociada a cada estado, se representa variando el grosor y la forma del borde del c´ırculo que dibuja un estado x: una l´ınea continua gruesa significa que el estado es de aceptaci´ on (Φ(x) = 1), si la l´ınea es continua pero delgada, el 7

estado es de rechazo (Φ(x) = 0), si la l´ınea no es continua, significa que el valor de salida est´ a indefinido (Φ(x) =?). La Figura 1.1 ilustra esta convenci´ on de dibujo: los estados 1,4,6,7,9 tienen valor de salida 1, los estados 2, 3 y 8 tienen valor de salida 0 y el estado 5 tiene valor de salida indefinido.

4

1

8

0 2

1

0

5

0

9

1 1

6

0 3 1

7

Figura 1.1: Ejemplo de la Notaci´ on Usada para Dibujar M´ aquinas de Moore Dados dos conjuntos disjuntos de palabras D+ y D− , se define el (D+ , D− )a ´rbol de Prefijos de Moore, denotado (AP M (D+ , D− )), como la m´ aquina de Moore que tiene B = {0, 1, ?}, Q = Pr(D+ ∪ D− ), q0 = ε y δ(u, a) = ua si u, ua ∈ Q y a ∈ Σ. Para todo estado u, el valor de la funci´ on de salida asociado a u es 1, 0 o ´ ? dependiendo si u pertenece a D+ , a D−Po a Σ∗ − (D+ ∪ D− ) respectivamente. El tama˜ no de la muestra (D+ , D− ) es w∈D+ ∪D− |w|. Una m´ aquina de Moore M = (Q, Σ, {0, 1, ?}, δ, q0, Φ) es consistente con (D+ , D− ) si ∀x ∈ D+ se tiene que Φ(x) = 1 y ∀x ∈ D− se tiene que Φ(x) = 0. Se entiende por tama˜ no de un aut´ omata finito o ´ de una m´ aquina de Moore, el n´ umero de estados |Q| que posee. Se dice que una muestra positiva (D+ ) de un lenguaje regular L es estructuralmente completa con respecto a un aut´ omata A que reconoce L, si existe una partici´ on π sobre los estados del a ´rbol aceptor de prefijos de D+ tal que el aut´ omata cociente AAP (D+ )/π acepta L (AAP significa a ´rbol aceptor de prefijos). En otras palabras, una muestra positiva es estructuralmente completa con respecto a un aut´ omata si el aut´ omata utiliza todas sus transiciones y todos sus estados finales para aceptar dicha muestra. Una muestra caracter´ıstica (D+ , D− ) [OG92] con respecto a un lenguaje regular L es aquella que cumple las siguientes dos condiciones: ∀u ∈ N (L) si u ∈ L entonces u ∈ D+ , si no ∃v ∈ Σ∗ |uv ∈ D+ ∀u ∈ P c(L), ∀v ∈ N (L)|δ(q0 , u) 6= delta(q0 , v) y ocurre una de dos cosas, o ´ ∃uu0 ∈ D+ |∃vu0 ∈ D− o ´ ∃vv 0 ∈ D+ |∃uv 0 ∈ D− 8

La primera condici´ on garantiza que la muestra positiva sea estructuralmente completa y la segunda asegura que si se intenta mezclar dos estados distintos, existir´ a al menos una muestras negativa que lo impida.

1.2.

Modelo de Aprendizaje

La inferencia gramatical se puede considerar una t´ecnica inductiva para realizar aprendizaje autom´ atico, por eso es fundamental dejar claro qu´e se entiende por aprendizaje. Existen varios modelos de aprendizaje que vienen siendo utilizado en este a ´mbito: el modelo de Gold, el aprendizaje activo, el modelo PAC y el modelo basado en la teor´ıa de Bayes, a continuaci´ on se presentan brevemente los elementos que componen el modelo de Gold, en tanto que los otros modelos mencionados son comentados en la Secci´ on 2.2. Se hace mayor ´enfasis en el modelo de Gold, ya que esta investigaci´ on se interesa especialmente por esta forma de definir el aprendizaje autom´ atico. Un modelo de aprendizaje, seg´ un Gold [Gol67], consta de tres elementos: Una definici´ on de aprendizaje Un m´etodo de presentaci´ on de informaci´ on Una relaci´ on de nombramiento, es decir, que asigna nombres (posiblemente m´ as de uno) a lenguajes. El aprendiz identifica un lenguaje indicando uno de sus nombres Con el fin de proponer un modelo de aprendizaje, Gold [Gol67] procede a definir cada uno de estos tres elementos: Definici´ on de aprendizaje. Recibe el nombre de identificaci´ on en el l´ımite y funciona de la siguiente forma: se tiene un aprendiz, que se encarga de formular una hip´ otesis qt de un nombre del lenguaje L bas´ andose en la informaci´ on que ha recibido hasta el momento. El aprendiz es una funci´ on G que va de cadenas de unidades de informaci´ on en nombres de lenguajes. qt = G(i1 , . . . , it ). Se dice que el aprendiz ha identificado L en el l´ımite si pasado un tiempo finito, las hip´ otesis que produce son todas la misma y son un nombre de L. Una clase de lenguajes es identificable en el l´ımite con respecto a un modelo de aprendizaje, si existe un aprendiz efectivo; es decir, un algoritmo que genere hip´ otesis y que cumpla la siguiente propiedad: dado cualquier lenguaje de la clase y dada cualquier secuencia de entrenamiento permitida para dicho lenguaje, el lenguaje va a ser identificado en el l´ımite [Gol67]. M´etodo de presentaci´ on de informaci´ on. Se refiere al esquema con el cual se presenta la informaci´ on de entrada al aprendiz, puede ser en forma de texto: en donde la entrada se compone u ´nicamente cadenas que pertenecen al lenguaje objetivo; tambi´en puede ser en forma de informante: donde se proporcionan cadenas de s´ımbolos indicando si ellas pertenecen al lenguaje objetivo o ´ a su complemento. 9

Relaci´ on de nombramiento. Gold considera dos maneras de asignar nombres a lenguajes, las llama el probador y el generador, ambas son m´ aquinas de Turing. El probador es un procedimiento de decisi´ on para el lenguaje L, es decir, es una funci´ on que va de cadenas de s´ımbolos al rango de enteros [0,1] devolviendo cero cuando la cadena de entrada no pertenece al lenguaje y uno cuando s´ı pertenece. El generador es una funci´ on de enteros en cadenas de s´ımbolos, es decir, para cada entero retorna una palabra que pertenece al lenguaje L, en otras palabras el rango de esta funci´ on es exactamente L. Gold defini´ o varios modelos de aprendizaje de lenguajes, para ello propuso una definici´ on de aprendizaje, dos m´etodos de presentaci´ on de informaci´ on y seis m´etodos de asignaci´ on de nombres a lenguajes. El modelo es iterativo y funciona presentando unidades de informaci´ on a un aprendiz que genera hip´ otesis a partir de ellas. Al escoger un m´etodo de presentaci´ on de informaci´ on y un m´etodo de asignaci´ on de nombres concretos, se instancia un modelo de aprendizaje particular. En el caso de esta investigaci´ on, se adopta la identificaci´ on en el l´ımite como definici´ on de aprendizaje, el informante como m´etodo de presentaci´ on de la informaci´ on y los aut´ omatas finitos como relaci´ on de nombramiento. Todos los modelos de aprendizaje que se mencionan al comienzo de la secci´ on est´ an en desarrollo y cada uno de ellos tiene ventajas y desventajas: el modelo de Gold es te´ oricamente s´ olido y da or´ıgen a algoritmos convergentes, pero requiere datos abundantes y correctos, lo cual no siempre es viable en problemas reales. El modelo de aprendizaje activo logra resolver en tiempo polinomial algunos problemas que son intratables en el modelo de Gold, pero tiene el problema de la interactividad y de que en algunas tareas espec´ıficas no es posible construir el or´ aculo necesario para el buen funcionamiento del modelo, por ejemplo: si no se conoce el lenguaje objetivo como ocurre en muchas tareas reales. Los algoritmos probabil´ısticos se comportan mejor con informaci´ on incompleta o ruidosa, aunque pierden su car´ acter exacto y hasta cierto punto son cajas negras cuyo funcionamiento interno es desconocido. Por su parte, el modelo PAC brinda un soporte te´ orico al desarrollo de modelos inductivos aproximados; los resultados conocidos son m´ as te´ oricos que pr´ acticos y apuntan a determinar qu´e clases de problemas son solucionables en tiempo polinomial y cu´ ales no lo son. Conociendo las ventajas y desventajas de los diferentes modelos y siguiendo tambi´en la l´ınea marcada por los trabajos que preceden y dan or´ıgen a esta investigaci´ on, se ha adoptado el modelo de aprendizaje de Gold, que permite obtener algoritmos con propiedades te´ oricas demostrables tales como la convergencia.

1.3.

Aut´ omatas Finitos Residuales

Un aut´ omata de estado finito residual [DLT02] o ´ RFSA (por su sigla en ingl´es) es un aut´ omata A = (Q, Σ, δ, I, F ) tal que, para cada q ∈ Q, L(A, q) es un lenguaje residual del lenguaje L reconocido por A. As´ı ∀q ∈ Q, ∃u ∈ Σ∗ tal que L(A, q) = u−1 L. En otras palabras, un Aut´ omata de Estado Finito Residual 10

(RFSA) A es un aut´ omata no determinista tal que todos sus estados definen lenguajes residuales de L(A). Todo DFA es un RFSA ya que cumple con la definici´ on. Dos relaciones definidas sobre el conjunto de estados de un aut´ omata relacionan los RFSAs con la inferencia gramatical. Sea D = (D+ , D− ) un conjunto de muestras, sea u, v ∈ P r(D+ ). Se dice que u ≺ v si no existe una palabra w tal que uw ∈ D+ y vw ∈ D− . Se dice que u ' v 1 si u ≺ v y v ≺ u. Se sabe que todo lenguaje regular tiene un conjunto finito de lenguajes residuales distintos [Myh57, Ner58], tambi´en se sabe que todo lenguaje regular puede representarse mediante DFAs y dado que todo DFA recortado es un RFSA, se tiene que todo lenguaje regular puede ser descrito mediante RFSAs [DLT02]. De los RFSA que representan un lenguaje regular, tiene particular inter´es el m´ as peque˜ no de ellos, el que tiene el menor n´ umero de estados, este es el llamado RFSA can´ onico. Formalmente, dado un lenguaje L ⊆ Σ∗ el RFSA can´ onico de L es el aut´ omata A = (Q, Σ, δ, I, F ) donde: Q = {u−1 L|u−1 L es primo, u ∈ Σ∗ } Σ es el alfabeto de L δ(u−1 L, a) = {v −1 L ∈ Q|v −1 L ⊆ (ua)−1 L} I = {u−1 L ∈ Q|u−1 L ⊆ L} F = {u−1 L ∈ Q|ε ∈ u−1 L} Si L(A, q) = u−1 L se dice que u es una palabra caracter´ıstica del estado q. El tama˜ no del RFSA can´ onico de un lenguaje regular tiene como cota superior al tama˜ no del DFA m´ınimo equivalente y como cota inferior el tama˜ no de los NFA minimales equivalentes [DLT02]. En estas condiciones, puede ocurrir que el RFSA can´ onico sea exponencialmente m´ as peque˜ no que el DFA m´ınimo equivalente, o tambi´en puede ocurrir que ambos sean del mismo tama˜ no y que exista un NFA minimal exponencialmente m´ as peque˜ no. Tambi´en puede ocurrir que exista un NFA con el mismo n´ umero de estados que el RFSA can´ onico, pero con menos transiciones. Por otra parte, en algunos casos la palabra caracter´ıstica m´ as corta asociada con un estado, puede tener una longitud exponencial con respecto al n´ umero de estados del RFSA can´ onico. Esto significa que encontrar un algoritmo que converja al RFSA can´ onico del lenguaje objetivo, no asegura que el resultado de la inferencia sea m´ınimo; aun as´ı, existe la posibilidad de mejorar los resultados obtenidos con inferencia de DFAs para aquellos lenguajes regulares que se caractericen por ser representados con aut´ omatas que tienen gran cantidad de lenguajes residuales compuestos. Qu´e tan comunes son en la pr´ actica este tipo de lenguajes es una pregunta para la que aun no se conoce respuesta y de ello depender´ a el inter´es pr´ actico de las aplicaciones de la teor´ıa de los RFSAs. 1 Esta relaci´ on es conocida en la terminolog´ıa de Gold como estados no obviamente distinguibles.

11

El siguiente ejemplo, tomado de [DLT02], muestra gr´ aficamente varios aut´ omatas que reconocen un lenguaje regular L; entre ellos un NFA, un DFA y el RFSA can´ onico. Sea Σ = {0, 1} y sea L = Σ∗ 0Σ. Los tres aut´ omatas de la Figura 1.2 reconocen L. Los estados finales (resp. no finales) se han dibujado con l´ıneas gruesas (resp. delgadas). 0,1

1

2 0

1

0

2

0,1

0

0,1

3

1

0

0 0,1

0 3

1

0

1

2 0,1

1

A1

0

3 0

1 4

0,1

A2

A3

Figura 1.2: A1 es un aut´ omata que reconoce L = Σ∗ 0Σ pero que no es ni DFA ni RFSA. A2 es un DFA que reconoce L y tambi´en es un RFSA. A3 es el RFSA can´ onico para L.

El primer aut´ omata, A1 no es ni DFA ni RFSA. Los lenguajes por la derecha asociados a los estados son: L(A1 , 1) = Σ∗ 0Σ, L(A1 , 2) = Σ y L(A1 , 3) = ε. Se puede ver que L(A1 , 3) = ε y @u ∈ Σ∗ tal que L(A1 , 3) = u−1 L. El aut´ omata A2 reconoce L y es el DFA m´ınimo de L, por lo tanto es un RFSA. En este caso L(A2 , 1) = Σ∗ 0Σ, L(A2 , 2) = Σ∗ 0Σ + Σ, L(A2 , 3) = Σ∗ 0Σ + Σ + ε, L(A2 , 4) = Σ∗ 0Σ + ε. Sin embargo no es can´ onico, ya que, por ejemplo, L(A2 , 3) = L(A2 , 2) ∪ L(A2 , 4) El aut´ omata A3 es el RFSA can´ onico de L, el cual no es un DFA. Los lenguajes residuales asociados con los estados de A3 son: L(A3 , 1) = ε−1 L, L(A3 , 2) = 0−1 L y L(A3 , 3) = 01−1 L. Notar que a pesar de ser un ejemplo bastante peque˜ no, no es trivial representar los lenguajes residuales del modo que se hizo en los aut´ omatas anteriores A1 y A2 . Denis [DLT02] define dos operadores sobre RFSAs que preservan la propiedad de equivalencia: saturaci´ on y reducci´ on, el primero permite adicionar arcos y estados iniciales al aut´ omata conservando el lenguaje que reconoce; el operador de reducci´ on permite eliminar estados al aut´ omata conservando tambi´en el lenguaje que reconoce. Dado A = (Q, Σ, δ, I, F ) el aut´ omata saturado de A es el aut´ omata As = (Q, Σ, δ s , I s , F ), donde I s = {q ∈ Q|L(A, q) ⊆ L(A)} y la funci´ on de transici´ on se define como ∀q ∈ Q, ∀a ∈ Σ, δ s (q, a) = {q 0 ∈ Q|aL(A, q 0 ) ⊆ L(A, q)}. Se puede observar que L(A) = L(As ), ya que el lenguaje por la derecha de cada estado es el mismo tanto en el aut´ omata original como en el saturado, de ello se desprende que si A es un RFSA, entonces As tambi´en lo es.

12

El operador de reducci´ on se define con base en la noci´ on de estado eliminable [DLT02]. Sea A = (Q, Σ, δ, I, F ) un NFA y q un estado S de Q. Se denota R(q) = {q 0 ∈ Q − {q}|L(A, q 0 ) ⊆ L(A, q)}. Si L(A, q) = {L(A, q 0 ) − {q 0 } ∈ R(q)} se dice que q es eliminable en A. Si q es eliminable se define el operador de reducci´ on φ(A, q) = A0 tal que A0 = (Q0 , Σ, δ 0 , I 0 , F 0 ) donde: Q0 = Q − {q}. 0 I = I si q 6∈ I o ´ I 0 = (I − {q}) ∪ R(q). F 0 = F ∩ Q0 . δ 0 se define para to0 0 do q ∈ Q , a ∈ Σ como: δ 0 (q 0 , a) = δ(q 0 , a) si q 6∈ δ(q 0 , a), en caso contrario δ 0 (q 0 , a) = (δ(q 0 , a) − {q}) ∪ R(q). Si q no es eliminable, φ(A, q) = A. Se puede ver que L(A) = L(A0 ) siendo A0 = φ(A, q). Los operadores de saturaci´ on y reducci´ on son permutables: φ(A, q)s = φ(As , q). Estos operadores se pueden utilizar para construir el RFSA can´ onico ya que se sabe que si A es un RFSA saturado, el operador de reducci´ on converge y el aut´ omata resultante es el RFSA can´ onico del lenguaje L(A) [DLT02]; sin embargo, este m´etodo es computacionalmente muy costoso, ya que determinar si un lenguaje residual es primo es una tarea de coste exponencial. Existe otro algoritmo para construir el RFSA can´ onico a partir de un NFA cualquiera, que teniendo complejidad exponencial, puede ser m´ as simple de implementar y se describe a continuaci´ on. Este m´etodo de Garc´ıa [Gar06], guarda relaci´ on con el algoritmo de Pol´ ak para minimizaci´ on de NFAs [Pol05]. El Algoritmo 1 recibe como entrada un NFA, en primer t´ermino lo convierte a su DFA m´ınimo equivalente que ser´ a la base de los pasos siguientes: calcular su reverso y el determinista de su reverso. Con la informaci´ on de los bloques de estados que se forman en el determinista, se construye la matriz b´ asica siguiendo el mismo procedimiento que usa Pol´ ak en [Pol05], pero sin agregar nuevos estados. Posteriormente se compara cada par de columnas, detectando si una est´ a contenida en la otra, si todos los unos que hay en c1, tambi´en est´ an en c2, se dice que la columna c1 est´ a contenida en c2. El hecho que una columna est´e contenida en otra, refleja una relaci´ on de inclusi´ on entre los estados correspondientes a dichas columnas. De otra parte, cuando una columna puede reconstruirse como la uni´ on de otras, el estado asociado a ella es compuesto. Con la informaci´ on de estas comparaciones se construye una estructura arborescente en la que un estado es padre de aquellos otros estados cuyos lenguajes por la derecha contiene. Finalmente se recorre el a ´rbol de inclusiones por niveles y se eliminan los estados compuestos; al hacerlo, se tiene cuidado de redireccionar todos los arcos que llegan a un estado compuesto hacia cada uno de los estados incluidos en ´el.

Ejemplo 1 Con el fin de ilustrar el funcionamiento de este m´etodo para construir el RFSA Can´ onico correspondiente a un DFA m´ınimo, se va a utilizar un aut´ omata tomado del art´ıculo Minimalizations of NFA Using the Universal Automaton de Pol´ ak [Pol05], all´ı se propone un m´etodo de minimizaci´ on que guarda cierta similitud con esta estrategia para encontrar el RFSA Can´ onico, ya que ambos m´etodos usan la matriz b´ asica asociada a un aut´ omata. La Figura 1.3 muestra el aut´ omata de partida, que es un DFA m´ınimo. El Cuadro 1.1 muestra el mismo aut´ omata representado en forma de tabla. El primer paso consiste en calcular el reverso del aut´ omata A, (R(A)) que 13

Algoritmo 1 ConstruirRFSACanonico(A) 1: Convertir el NFA de entrada A en su DFA m´ınimo equivalente A 0 2: Calcular el reverso de A0 , llamado R(A0 ) 3: Calcular el determinista de R(A0 ), llamado D(R(A0 )) 4: M = Matriz b´ asica de D(R(A0 )) 5: inclusiones = {} 6: for c1 en Columnas(M ) do 7: for c2 en Columnas(M ) do 8: if c2 contiene a c1 then 9: inclusiones = inclusiones ∪ {(Estado(c1), Estado(c2))} 10: end if 11: end for 12: end for 13: Organizar las relaciones de inclusi´ on en forma arborescente 14: for s en el a ´rbol de S inclusiones, recorrido por niveles a partir de la ra´ız do 15: if Columna[s] = i∈Hijos(s) Columna[i] then 16: A0 = eliminarEstado(s, A0 ) 17: end if 18: end for 19: Return A0

a

4

a b

2 a

a

b

1

5

b

b

a

b 7

b a

3

b

9 a

b

6

a

8

a,b

Figura 1.3: Ejemplo de Construcci´ on del RFSA Can´ onico, Aut´ omata Inicial

se aprecia en el Cuadro 1.2. A continuaci´ on se calcula el determinista del reverso D(R(A)), el resultado se presenta en el Cuadro 1.3. Con esta informaci´ on se construye la matriz b´ asica, ella tiene en las filas los estados de D(R(A)) y en las columnas los estados del DFA m´ınimo inicial, la posici´ on M [i, j] de la matriz b´ asica puede valer 1 o 0, vale 1 en caso que el estado j del DFA m´ınimo, forme parte del estado i de D(R(A)) y 0 en otro caso. El Cuadro 1.4 muestra 14

la matriz b´ asica correspondiente al ejemplo.

Cuadro 1.1: Aut´ omata Inicial A en a → 1 2 2 4 ← 3 6 4 4 5 7 ← 6 8 7 4 ← 8 8 9 7

Representaci´ on de Tabla b 3 5 5 2 3 3 9 8 8

Cuadro 1.2: R(A) en Representaci´ on de Tabla a b ← 1 2 1 4 → 3 {1,5,6} 4 {2,4,7} 5 {2,3} → 6 3 7 {5,9} → 8 {6,8} {8,9} 9 7

→  →  → 

Cuadro 1.3: D(R(A)) en Representaci´ on de Tabla a b {3,6,8} {3,6,8} {1,5,6,8,9} {1,5,6,8,9} {3,6,8} {2,3,7,8,9} {2,3,7,8,9} {1,5,6,8,9} {1,4,5,6,7,8,9} {1,4,5,6,7,8,9} {2,3,4,5,6,7,8,9} {2,3,7,8,9} {1,2,3,4,5,6,7,8,9} {1,2,3,4,5,6,7,8,9} {2,3,4,5,6,7,8,9} {1,2,3,4,5,6,7,8,9} {1,2,3,4,5,6,7,8,9} {1,2,3,4,5,6,7,8,9}

Comparando las columnas de la matriz b´ asica, se pueden detectar las relaciones de inclusi´ on entre los lenguajes residuales asociados a los diferentes estados del aut´ omata inicial A. Se considera que hay inclusi´ on si los unos de una columna est´ an contenidos en los unos de otra, por ejemplo, se puede observar en el Cuadro 1.4 que 2 ≺ 3. Con esta informaci´ on tambi´en se pueden encontrar los estados compuestos, por ejemplo, la columna correspondiente al estado 9, se puede construir uniendo las columnas correspondientes a los estados 5 y 7, 15

Cuadro 1.4: Matriz B´ asica Obtenida 1 2 3 → {3,6,8} 0 0 1  {1,5,6,8,9} 1 0 0 0 1 1 → {2,3,7,8,9}  {1,4,5,6,7,8,9} 1 0 0 → {2,3,4,5,6,7,8,9} 0 1 1  {1,2,3,4,5,6,7,8,9} 1 1 1

a Partir de 4 5 6 0 0 1 0 1 1 0 0 0 1 1 1 1 1 1 1 1 1

D(R(A)) 7 8 9 0 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1

por lo tanto 9 es un estado compuesto. Realizando sistem´ aticamente todas las comparaciones, se obtienen todas las inclusiones y esto produce el a ´rbol que se presenta en la Figura 1.4. Tambi´en se deduce que los estados compuestos del aut´ omata son: 8, 9, 5, 7 por lo tanto estos estados no forman parte del RFSA can´ onico. Expresando de otra manera las inclusiones obtenidas, se puede afirmar que: 1, 2, 3, 4, 5, 6, 7, 9 ≺ 8; 1, 2, 4, 5, 7 ≺ 9; 2, 4 ≺ 7; 1, 4, 5 ≺ 6; 1, 4 ≺ 5 y 2 ≺ 3, esta informaci´ on se utilizar´ a en el paso siguiente para eliminar correctamente los estados compuestos. 8 9 5 1

6 7

4

3 2

´ Figura 1.4: Ejemplo de Construcci´ on del RFSA Can´ onico, Arbol de Inclusiones entre Estados Una vez se elimina un estado compuesto x, los arcos que llegaban a ´el deben redireccionarse a cada estado incluido en x. En el ejemplo, el primer estado que se elimina es el 8, por encontrarse en la ra´ız del a ´rbol de inclusiones, por lo tanto, los arcos que llegan a 8, deben llegar a 1, 2, 3, 4, 5, 6, 7, 9. Una vez realizada la eliminaci´ on y redireccionados los arcos, el aut´ omata queda como se ilustra en la Figura 1.5. Posteriormente se eliminan siguiendo el mismo procedimiento los estados compuestos: 9, 7 y 5, obteni´endose el aut´ omata de la Figura 1.6 que es final y corresponde al RFSA can´ onico del DFA m´ınimo de partida.

Vale la pena finalizar recopilando algunos resultados referentes a la complejidad de los problemas que se han mencionado en esta secci´ on [DLT02]: decidir si un DFA es saturado pertenece a P ; decidir si un NFA es saturado pertenece a P SP ACE − Completo; construir el saturado de un NFA tambi´en pertenece 16

b

a

b

4

a

b b

2 a

a

b

b

1

b

b

5

b 7

9

b

a

a b a

3

a a

a

b

a

a

6

a a

b b b

Figura 1.5: Ejemplo de Construcci´ on del RFSA Can´ onico, Aut´ omata Despu´es de Eliminar el Estado Compuesto 8 a a,b 2

a

4 b

b b

1

b

a

a a

b

3

6 a,b

a

Figura 1.6: Ejemplo de Construcci´ on del RFSA Can´ onico, Aut´ omata Final

a P SP ACE − Completo al igual que decidir si un NFA es RFSA y decidir si el saturado de un DFA es RFSA can´ onico; finalmente, construir el RFSA can´ onico equivalente a un DFA es P SP ACE − Completo. Estos resultados muestran que al usar RFSAs como modelo de representaci´ on para la inferencia no se escapa a la dificultad intr´ınseca del problema de inferir NFAs. Inferir RFSAs puede ser beneficioso si se logra obtener hip´ otesis de tama˜ no cercano al RFSA can´ onico, ya que ´este en algunos casos puede ser mucho m´ as peque˜ no que el DFA m´ınimo correspondiente; aun en esta circunstancia habr´ a casos en que el RFSA can´ onico tenga el mismo tama˜ no del DFA 17

m´ınimo y all´ı no se obtendr´ a mejora.

18

Cap´ıtulo 2

Antecedentes El campo de la inferencia gramatical de lenguajes regulares ha evolucionado mucho en los u ´ltimos 40 a˜ nos, tanto en cuanto a resultados te´ oricos como en el desarrollo de algoritmos de uso pr´ actico. En este Cap´ıtulo se propone una relaci´ on comentada de trabajos que se consideran importantes dentro de este campo de estudio. En primer lugar, se hace un recuento de la evoluci´ on de la inferencia gramatical de lenguajes regulares, en la que se considera con mayor detalle la estrategia de variar el orden de mezcla de los estados que dio origen a los algoritmos conocidos como EDSM (Evidence Driven States Merging) y el planteamiento del problema de inferencia gramatical de lenguajes regulares como problema de b´ usqueda. Tambi´en se presentan algunos antecedentes en cuanto a modelos de aprendizaje, c´ orpora de prueba y estrategias para evaluaci´ on de algoritmos de inferencia gramatical.

2.1.

Antecedentes en Inferencia Gramatical de Lenguajes Regulares

En las d´ecadas de 1960 y 1970 E. Mark Gold realiz´ o varios aportes importantes en cuanto a la inferencia gramatical de lenguajes regulares: en primer lugar, demostr´ o que encontrar el aut´ omata determinista (DFA) m´ as peque˜ no, consistente con un conjunto dado de muestras positivas y negativas D+ ∪ D− , es un problema NP-Completo [Gol78]. Tambi´en propuso el modelo de identificaci´ on en el l´ımite [Gol67], que es una valiosa herramienta para demostrar la correcci´ on de algoritmos de inferencia gramatical. Adem´ as, Gold propuso un algoritmo de inferencia [Gol78] que dado un conjunto de ejemplos suficientemente representativo, puede construir en tiempo polinomial dicho aut´ omata determinista m´ınimo. Este algoritmo es particularmente interesante, ya que varios algoritmos posteriores pueden entenderse como modificaciones suyas [GRC04a]. En la misma ´epoca, Trakhtenbrot y Barzdin propusieron su algoritmo de inferencia [TB73], que utiliza todas las cadenas de longitud menor o igual a un valor dado para realizar correctamente el proceso de inferencia; adem´ as mostraron que si esta informaci´ on est´ a disponible, el problema de inferencia es tratable. Se sabe que los algoritmos de Gold y Trakhtenbrot funcionan de forma simi19

lar, aunque utilizan representaciones muy diferentes de la informaci´ on [GCR00]. En la d´ecada de 1980 aparecieron nuevos resultados negativos que confirmaron la dificultad te´ orica del problema de inferencia gramatical de lenguajes regulares. Angluin demostr´ o que el problema de encontrar el aut´ omata determinista m´ as peque˜ no dado un conjunto de muestras es NP-Completo a´ un si el aut´ omata objetivo tiene s´ olo dos estados o si faltan unas pocas muestras en el conjunto de entrenamiento, que debe ser completo hasta una longitud dada [Ang78]. Angluin tambi´en demostr´ o que la tarea sigue siendo dif´ıcil a´ un si se supone que el algoritmo puede formular preguntas de pertenencia [Ang87] o de equivalencia [Ang90] a un or´ aculo; es decir, si dada una cadena puede preguntar si ella pertenece al lenguaje objetivo o no, o si la hip´ otesis actual es equivalente al aut´ omata objetivo. Los resultados te´ oricos negativos causaron un comprensible pesimismo en cuanto a las posibilidades de encontrar algoritmos pr´ acticos de inferencia gramatical, lo cual llev´ o a la exploraci´ on de otros caminos alternativos que continuaron desarroll´ andose durante la d´ecada del 90 y hasta el presente. Por ejemplo, la inferencia mediante aut´ omatas deterministas estoc´ asticos [CO94]; el aprendizaje activo, es decir, aquel que aporta informaci´ on adicional al proceso de inferencia en la forma de un or´ aculo o maestro informado que participa en el proceso cuando el algoritmo as´ı lo requiere [PH97, PH00], [Ang87, Ang90, Ang92]; otras formas de involucrar informaci´ on del entorno en el proceso de inferencia [CFKdlH04]; el uso de t´ecnicas de inteligencia computacional como redes neuronales [OS01], algoritmos gen´eticos [DMV94, PN02] o programaci´ on evolutiva [LR05, BL05]. A comienzos de la d´ecada de 1990 apareci´ o el algoritmo RPNI [OG92] y Lang propuso una modificaci´ on al algoritmo de Trakhtenbrot y Brazdin [TB73] llamada Traxbar al cual se hace referencia en [Lan92, CK03]. Estos algoritmos, gracias a su capacidad de generalizaci´ on pueden inferir aut´ omatas deterministas m´ınimos en tiempo polinomial; en el caso de RPNI la precisi´ on de la aproximaci´ on depende de la calidad de la informaci´ on en el entrenamiento y en caso que el conjunto de entrenamiento sea caracter´ıstico, se demuestra que el algoritmo converge al DFA m´ınimo del lenguaje objetivo [OG92]. Adem´ as de los esfuerzos por generar nuevos algoritmos, algunos investigadores han estudiado el espacio de b´ usqueda del problema de inferencia gramatical [DMV94, CF03b] y su relaci´ on con el espacio de b´ usqueda de otros problemas NP-Completos [PCS05]. Otra alternativa que se ha explorado es reducir el problema de la inferencia gramatical a otros problemas, por ejemplo: al problema de satisfacci´ on de restricciones [PCS05, OS01] a un problema de cubrimiento de grafos [Cho03, PO99] o al problema algebraico de caracterizar un lenguaje como la preimagen de un hiperplano en un espacio de Hilbert, que es lo que recientemente se ha llamado lenguajes planares [CFW06, CFWS06]. En los a˜ nos siguientes continuaron apareciendo mejoras a estos algoritmos, por ejemplo: Dupont propuso RPNI2, que es una versi´ on incremental de RPNI [Dup96], Cano, Ruiz y Garc´ıa desarrollaron FCRPNI, que incluye el uso de configuraciones prohibidas como informaci´ on adicional de entrada [CRG02], 20

Sebban y Janodet dise˜ naron una versi´ on probabil´ıstica que funcione a partir de muestras con ruido [SJ03]. En el a˜ no 1998 Lang propuso el concurso Abbadingo One [LPP98] en el cual compitieron diferentes tipos de algoritmos de inferencia gramatical sobre un conjunto de problemas de inferencia de lenguajes regulares. Ganaron dos algoritmos, uno basado en mezcla de estados y el otro un algoritmo paralelo que hace b´ usqueda no determinista. El triunfo de un algoritmo basado en mezcla de estados, renov´ o el inter´es por la b´ usqueda de algoritmos exactos. De hecho, el propio Lang, basado en los resultados del concurso propuso su algoritmo RedBlue descrito en [LPP98, CK03]. El algoritmo EDSM (Evidence Driven State Merging) de Rodney Price, que fue uno de los ganadores, tambi´en ha dado origen a posteriores estudios y mejoras [CK03, ACS04]. Una posibilidad que eventualmente ha sido considerada, es la de inferir aut´ omatas no deterministas (NFA) en lugar de deterministas; en el a˜ no 1994 Yokomori public´ o un trabajo en este tema cuyo m´etodo utilizaba consultas a un or´ aculo y contraejemplos [Yok94, dlH05], tambi´en lo hicieron Coste y Fredouille [CF00, CF03a, CFKdlH04] quienes partiendo del estudio de los aut´ omatas finitos no ambiguos obtuvieron un m´etodo de inferencia de NFAs. A partir del a˜ no 2000, Denis et. al. [DLT00, DLT02] han enfocado el tema de la inferencia de NFAs desde la parte te´ orica, al centrarse en un subconjunto de los NFAs, llamado RFSA (Residual Finite State Automata). Para esta subclase se demuestra la existencia de un RFSA can´ onico u ´nico para cada lenguaje regular. Denis propone un algoritmo que converge a ´el, llamado algoritmo DeLeTe2 [DLT00]; desafortunadamente, pruebas experimentales muestran que sus hip´ otesis con frecuencia son inconsistentes con las muestras de entrenamiento. Posteriormente, presenta el programa DeLeTe2 [DLT04] (n´ otese que se reportan los resultados de ejecutar dicho programa, pero no se explica el algoritmo que utiliza), cuyos resultados preliminares son prometedores para un subconjunto de lenguajes regulares en los que los m´etodos ya conocidos, como RPNI o Red-Blue no se comportan particularmente bien; esto es, cuando los lenguajes objetivo son expresiones regulares o NFAs generados aleatoriamente. En la actualidad, se conocen pocos grupos trabajando en el tema de la inferencia de NFAs: de un lado se buscan m´etodos de minimizaci´ on de NFAs que conduzcan a una forma can´ onica [Pol05]; otros trabajos han experimentado con algoritmos que converjan a RFSAs [GRC04a, GRC04b]; con algoritmos que infieren UFAs (Unambiguous Finite Automata) [ACS04, CF03b, CF03a], con extensiones a la estrategia RPNI que realizan mezcla no determinista de estados [GRCA05] y tambi´en se est´ a trabajando en la inferencia de NFAs por yuxtaposici´ on de subaut´ omatas [dPGR06]. Otra estrategia que se sigue aplicando hasta el presente, consiste en adaptar los m´etodos de inferencia a tipos particulares de aut´ omatas con miras a su aplicaci´ on a una tarea espec´ıfica, por ejemplo: la inferencia de aut´ omatas con par´ ametros permite trabajar en tareas con un alfabeto de tama˜ no grande, como ocurre en la construcci´ on de modelos de hardware y software [BJR06], este trabajo extiende el algoritmo de Angluin que hace inferencia activa. Hacer 21

inferencia activa de ERAs (Event-Recording Automata) [GJP06] sirve para inferir modelos que necesitan representar el tiempo, como los que se utilizan para modelar sistemas reactivos; la inferencia de este tipo de aut´ omatas se requiere, por ejemplo, en la verificaci´ on autom´ atica y en la generaci´ on de casos de pruebas para sistemas de telecomunicaciones. La inferencia de aut´ omatas de a ´rboles k-testables [KBBdB06] se est´ a utilizando para la extracci´ on de informaci´ on en documentos estructurados. Coste y Kerbellec [CK05, CK06] han propuesto un algoritmo de inferencia de NFAs para la identificaci´ on de proteinas, este algoritmo realiza un alineamiento m´ ultiple parcial en las cadenas de entrenamiento que le permite establecer segmentos de cadena que son similares, cada grupo de segmentos similares se convierte en una unidad gracias al proceso de mezcla y la realizaci´ on sistem´ atica de todas las mezclas posibles da origen a un aut´ omata no determinista que representa una sucesi´ on compleja de consensos locales.

2.1.1.

Variaciones del Orden en la Mezcla de Estados

Todos los algoritmos que se consideran en este trabajo tienen como caracter´ıstica com´ un el hecho de basarse en la mezcla de estados. Este concepto se describir´ a con m´ as detalle en el Cap´ıtulo 3, por el momento basta con decir que dos estados se mezclan cuando se considera que ambos tienen asociado el mismo lenguaje y por lo tanto uno de ellos es redundante. La mezcla disminuye el tama˜ no del aut´ omata y generaliza el lenguaje que ´este reconoce. Se considera que dos estados tienen el mismo lenguaje asociado si no existe ninguna muestra de entrenamiento que contradiga dicha suposici´ on, esto implica que eventualmente se terminen mezclando estados que, ante una mayor cantidad de informaci´ on disponible no lo habr´ıan sido. Realizar mezclas equivocadas tiene un impacto negativo en el proceso de inferencia, que se traduce en un aumento del tama˜ no de la hip´ otesis construida y en una disminuci´ on en la tasa de reconocimiento del aut´ omata resultante. Con el fin de evitar hasta donde sea posible la realizaci´ on de mezclas equivocadas, de la Higuera [dlHOV96] propuso modificar el orden de mezcla lexicogr´ afico para favorecer las parejas de estados que tuvieran menor posibilidad de ser equivocadas; con este fin propuso asociar a cada pareja un puntaje y proceder a mezclar aquella pareja que tenga m´ aximo puntaje; se pueden elegir muchos criterios para asignar el puntaje, en general se espera que dicho valor sea alto si hay abundante evidencia entre las muestras disponibles de que los dos estados tienen el mismo lenguaje asociado y valor bajo en caso contrario. Aunque los resultados iniciales no fueron concluyentes, la idea fue retomada posteriormente por Price [LPP98] quien propuso el algoritmo EDSM (Evidence Driven State Merging) que mostr´ o muy buen desempe˜ no en el concurso Abbadingo, llegando a ser uno de los ganadores. La estrategia de EDSM [CK03], se resume en el Algoritmo 2. La estrategia EDSM fue posteriormente refinada, porque su principal inconveniente es la necesidad de realizar una gran cantidad de procesamiento para asociar un puntaje a cada posible pareja de estados; una opci´ on fue considerar u ´nicamente las parejas formadas por estados que se encuentren a una distancia W del estado inicial, lo que se conoce como algoritmo W-EDSM [CK03]. Sin embargo, una estrategia mejor para calcular las parejas candidatas llamada blue-fringe [LPP98, CK03], dio origen al algoritmo que se conoce como redBlue, 22

Algoritmo 2 EDSM(D+ ∪ D− ) 1: Evaluar todos los posibles pares de estados del a ´rbol aceptor de prefijos de la muestra de entrenamiento 2: Mezclar la pareja de nodos que tenga m´ aximo puntaje. El puntaje se calcula asignando un punto por cada coincidencia de signos entre estados de los correspondientes sub´ arboles de mezcla 3: Repetir los pasos anteriores hasta que no haya m´ as nodos a mezclar

el cual se muestra en el Algoritmo 3. Este algoritmo es considerado el estado del arte en cuanto a inferencia de DFAs por mezcla de estados. Algoritmo 3 redBlue(D+ ∪ D− ) 1: Colorear de rojo la raiz del a ´rbol de prefijos de Moore 2: Colorear en azul los hijos de los estados rojos que no sean rojos 3: Asignar puntaje a todas las posibles parejas formadas por un estado rojo y uno azul 4: Promover el nodo azul m´ as superficial que sea distinguible de todos los nodos rojos. Resolver los empates en forma aleatoria 5: Si no es posible promover ning´ un estado, mezclar el par de nodos que tenga m´ as alto puntaje y resolver los empates en forma aleatoria 6: Terminar cuando no haya nodos azules que promover ni sea posible realizar ninguna mezcla

2.1.2.

La Inferencia Gramatical como Problema de B´ usqueda

El problema de la inferencia gramatical se puede plantear en forma de problema de b´ usqueda de la siguiente manera: dado un conjunto de muestras positivas D+ y un conjunto de muestras negativas D− , encontrar el aut´ omata determinista m´ as peque˜ no que sea consistente con dichas muestras. Esto significa que el espacio de b´ usqueda est´ a formado por todos los aut´ omatas deterministas posibles y que de alguna forma hay que recorrer este inmenso espacio hasta encontrar el aut´ omata m´ as peque˜ no que sea consistente con las muestras. Trabajos previos han estudiado este espacio de b´ usqueda [DMV94, CF03b] que puede pensarse como un a ´rbol de aut´ omatas que tiene en la raiz el a ´rbol aceptor de prefijos de las muestras de entrada y cuyos hijos corresponden a cada una de las posibles transformaciones que puede sufrir este a ´rbol. En este enfoque, se pueden construir algoritmos exactos, siguiendo estrategias como backtracking o beam search, las cuales tienen como desventaja su complejidad exponencial, o construir algoritmos de aproximaci´ on m´ as veloces, pero que no garantizan llegar a encontrar el aut´ omata m´ as peque˜ no. Entre los algoritmos de b´ usqueda exacta, vale la pena mencionar los algoritmos MMM (Mealy Machine Minimizer) [BO05], BICA [BO05] y Exbar [Lan99, BO05] siendo Exbar el m´ as eficiente de ellos [BO05]. Por su parte, entre los algoritmos que hacen b´ usqueda aproximada, vale la pena destacar a SAGE [JP98] 23

y a las versiones de EDSM para b´ usqueda ed-beam y ed-ss [Lan99, BO05]. El algoritmo MMM [BO05, CK03] parte de un aut´ omata vac´ıo que va creciendo a medida que se modifica para obtener consistencia con las muestras positivas y negativas, para ello construye el a ´rbol aceptor de prefijos aumentado de dichas muestras y lo recorre por amplitud; luego realiza una b´ usqueda por backtracking en la que al considerar cada estado del a ´rbol, el algoritmo decide si es posible identificar dicho nodo con alguno de la hip´ otesis actual o si la hip´ otesis debe ser modificada. El algoritmo BICA [OS01, CK03, BO05] sigue la misma estrategia general, pero mejora el mecanismo de b´ usqueda utilizando una base de restricciones que sirve para, ante un conflicto en el punto actual, detectar cu´ al de las decisiones anteriores puede estar causando ese conflicto y retroceder directamente a ese punto. El algoritmo exbar es el estado del arte en cuanto a m´etodos exactos [BO05] de inferencia de DFAs m´ınimos, por ese motivo ser´ a explicado con m´ as de detalle. El algoritmo exbar utiliza la t´ecnica de recorrido blue-fringe, que ha sido explicada en el algoritmo redBlue, para establecer las parejas de estados que eventualmente se pueden mezclar: considera un conjunto de estados rojos y un conjunto de estados azules, asigna un puntaje a cada elemento del conjunto azul y con ese puntaje determina cu´ al ser´ a el estado azul a procesar en cada iteraci´ on, el criterio de selecci´ on consiste en contar el n´ umero de elementos rojos con los cuales el elemento azul podr´ıa ser mezclado y actuar en orden inverso. El Algoritmo 4 muestra la subrutina principal, en la que se construye el a ´rbol aceptor de prefijos de las muestras y posteriormente se itera controlando el tama˜ no de las hip´ otesis que se van a generar, empezando en 1 e increment´ andolo indefinidamente. Es claro que el algoritmo podr´ıa modificarse para que se detenga en cuanto encuentre el primer aut´ omata consistente con las muestres, el cual por la forma de construcci´ on ser´ a necesariamente de tama˜ no m´ınimo.

Algoritmo 4 exbar(D+ ∪ D− ) 1: maxRed = 1 2: root = APM((D+ ∪ D− )) 3: while true do 4: exhSearch(list(root),maxRed) 5: maxRed = maxRed + 1 6: end while El Algoritmo 5 contiene el backtracking que funciona en la forma habitual. Recordar que la subrutina pickBlueNode prefiere el nodo azul para el cual existan menos alternativas posibles, es decir, que se prefiere un nodo azul que no sea mezclable con ning´ un nodo rojo, ya que para el la u ´nica posibilidad es ser promovido, en siguiente t´ermino se prefiere un nodo azul que s´ olo sea mezclable con uno de los nodos rojos porque para ´el s´ olo hay dos posibilidades: mezclarlo con el u ´nico estado rojo compatible o promoverlo a rojo y as´ı sucesivamente incrementando el n´ umero de alternativas posibles. La subrutina tryMerging(R,B) se encarga de realizar la mezcla de estados, 24

Algoritmo 5 exhSearch(redList,maxRed) 1: if length(redList) ≤ maxRed then 2: blueList = calculateBlueList() 3: if length(blueList) == 0 then 4: foundASolution() 5: else 6: B = pickBlueNode() 7: for R in redList do 8: if tryMerging(R,B) != ERROR then 9: exhSearch(redList,maxRed) 10: end if 11: undoMerge() 12: end for 13: exhSearch(extendList(redList,B),maxRed) 14: end if 15: end if para ello redirecciona los arcos que llegan y parten de B para que lleguen y partan de R. Adicionalmente, la subrutina propaga la mezcla para mantener el determinismo del aut´ omata actual y tambi´en ajusta la funci´ on de salida del estado R cuando ello sea necesario. La mezcla puede fallar en caso que exista inconsistencia entre los valores de salida de los estados R y B en ese caso la subrutina retorna ERROR. Notar que la mezcla se propaga inmediatamente para garantizar el determinismo del aut´ omata resultante, esta es una de las diferencias m´ as importantes entre Exbar y el algoritmo MMM. La subrutina tryMerging(R,B) es id´entica a detmerge, que se presenta en el Algoritmo 10 de la Secci´ on 3.2, all´ı se puede observar un ejemplo de su funcionamiento. Pasando a los algoritmos de b´ usqueda aproximada, el algorimo SAGE (SelfAdaptative Greedy Estimate) [JP98, CK03, BO05] es una estrategia de b´ usqueda en a ´rboles que es no determinista y paralela, ella muestrea el espacio de b´ usqueda para obtener informaci´ on sobre regularidades en la distribuci´ on de las soluciones, luego la b´ usqueda se enfoca manteniendo en el siguiente nivel los estados m´ as prometedores de acuerdo a una funci´ on objetivo. El algoritmo parte de la raiz del a ´rbol de b´ usqueda seleccionando en cada nivel un n´ umero limitado de alternativas prometedoras, las cuales se procesan paralelamente. El procesamiento consta de dos etapas: Construcci´ on: en esta etapa se establece una lista de alternativas de mezcla ubicadas en un mismo nivel del a ´rbol; se asigna un procesador a cada alternativa, el cual se encarga de calcular un puntaje asociado a la misma. El puntaje se calcula en funci´ on de un camino aleatorio desde ese punto de la b´ usqueda hasta llegar a una hoja del a ´rbol. Competici´ on: cada procesador elige entre los hijos de su nodo actual, aquel con m´ aximo puntaje y en el momento indicado todos los procesadores comienzan a trabajar en el siguiente nivel del a ´rbol. El algoritmo termina cuando no hay m´ as nodos para procesar. El algoritmo ed-beam (Evidence Driven Beam search) [Lan99, BO05] com25

bina la idea de beam search del algoritmo SAGE con el heur´ıstico de EDSM, que se usa para dar puntaje a cada una de las parejas candidatas a mezclarse y elegir la m´ as prometedora. Por su parte, el algoritmo ed-ss (Evidence Driven Stochastic Search) [BO05] procura detectar la mezcla con mayor probabilidad de ser equivocada, para eso se utiliza una medida que estima el impacto de cada mezcla realizada sobre todas las dem´ as, teniendo en cuenta: los puntajes de las mezclas que ya no ser´ıan posibles, el incremento en los puntajes de las mezclas que se vean favorecidas y el decremento en los puntajes de las mezclas que se perjudican. La idea es que la mezcla que tenga mayor puntaje debe deshacerse primero y esto cambia el procedimiento habitual del backtracking de deshacer la u ´ltima decisi´ on que se haya tomado.

2.2.

Modelos de Aprendizaje

La definici´ on de un modelo de aprendizaje est´ a en la base de cualquier investigaci´ on sobre aprendizaje en m´ aquinas y en particular sobre inferencia gramatical. Existen varios modelos de aprendizaje que se han desarrollado a trav´es de los a˜ nos. En esta secci´ on se presentan brevemente algunos de ellos. En la Secci´ on 1.1 se ha presentado ya el modelo de Gold, que sirve de base para esta investigaci´ on. El Aprendizaje Activo. Se caracteriza por ser interactivo, esto quiere decir que adem´ as de la informaci´ on que recibe de las muestras de entrenamiento, el aprendiz puede interrogar a un interlocutor plante´ andole una pregunta concreta; normalmente el interlocutor es un programa al que suele llamarse or´ aculo. Angluin [Ang87, Ang90] propone el modelo MAT (Minimally Adecuate Teacher) en el cual el interlocutor s´ olo es capaz de responder a dos tipos de preguntas concretas: preguntas de pertenencia o de equivalencia, es decir, se puede preguntar si una cadena en particular pertenece al lenguaje objetivo o no, o si la hip´ otesis actual es equivalente al aut´ omata objetivo. Aprendizaje Basado en la Teor´ıa de Bayes. Los clasificadores de Bayes son una forma muy consolidada de realizar aprendizaje inductivo. Este modelo se caracteriza por el uso intensivo de probabilidades. Los aut´ omatas estoc´ asticos y los algoritmos que hacen inferencia sobre ellos son un buen ejemplo de aplicaci´ on de esta teor´ıa como modelo de aprendizaje [CO94]. La aplicaci´ on de Modelos Ocultos de Markov tambi´en forman parte de este modelo y se sabe que tienen un buen desempe˜ no en una variedad de situaciones como el reconocimiento de habla entre otras. El Modelo PAC (Probably Aproximately Correct). En este modelo, que fue propuesto por Valiant [Val84], se parte del supuesto que el aprendiz no va a lograr aprender exactamente el lenguaje objetivo, si no que va a construir una aproximaci´ on cuya correcci´ on respeta un nivel predefinido de error con una probabilidad tambi´en predefinida. Se ha encontrado que algunos problemas que no es posible resolver polinomialmente en el Modelo de Gold, o en el Modelo de Aprendizaje Activo, 26

pueden ser aproximados en tiempo polinomial en este modelo [PH97]. De la Higuera lo define en [dlH05] como un modelo para estimar el grado de dificultad de un problema. En el caso de la inferencia gramatical, estima la dificultad del aprendizaje de una clase de lenguaje; la mayor´ıa de los resultados conocidos son negativos [dlH05]. Por su parte Angluin [Ang92] lo define como un nuevo criterio de correcci´ on para el aprendizaje de conceptos mediante ejemplos, en el que se enfatiza la importancia del aprendizaje en tiempo polinomial. Angluin [Ang92] dice que un algoritmo de aprendizaje A identifica con el modelo PAC un concepto de C en t´erminos de un espacio de hip´ otesis H con respecto a una clase de distribuciones de probabilidad D si y s´ olo si para toda distribuci´ on D en D y todo concepto c ∈ C, para todo n´ umero positivo ε, δ, cuando A se ejecuta con entradas ε, δ y accede al or´ aculo para D y c, ´el eventualmente termina y produce como salida una hip´ otesis h ∈ H tal que con probabilidad al menos (1−δ), la distancia entre c y h es menor que ε. En resumen, se conoce que el modelo de Gold permite establecer en forma s´ olida la convergencia de un algoritmo de inferencia, aunque requiere informaci´ on abundante y veraz. El aprendizaje activo funciona en forma similar, salvo que permite la interacci´ on de aprendiz con una fuente externa de informaci´ on lo cual es positivo porque aumenta la eficacia del modelo en algunos casos, pero requiere la existencia de un or´ aculo capaz de responder verazmente a las preguntas que formule el aprendiz. El modelo de Bayes tiene mayor flexibilidad para adaptarse al ruido en la informaci´ on de entrada, pero los resultados son siempre aproximaciones.

2.3.

Antecedentes en cuanto a Evaluaci´ on de Algoritmos de Inferencia Gramatical

El uso de datos sint´eticos ha sido la forma m´ as extendida en la comunidad acad´emica para evaluar nuevos algoritmos de inferencia gramatical. Esto se debe por una parte a la necesidad de proveer un ambiente controlado para la efectiva evaluaci´ on de los mismos y por otra a que el tama˜ no de los problemas del mundo real en ocasiones supera las posibilidades de los algoritmos en dise˜ no. Seg´ un Lang [LPP98], los aut´ omatas aleatorios tienen una complejidad de Kolmogorov alta y se pueden generar f´ acilmente para el tama˜ no que se desee, cualidades estas que los hacen u ´tiles como aut´ omatas objetivo para la construcci´ on de c´ orpora de entrenamiento y prueba. A medida que los algoritmos de inferencia gramatical han ido mejorando su desempe˜ no, han ido surgiendo tambi´en c´ orpora m´ as complejos para realizar las pruebas. Sin embargo, debe se˜ nalarse que hacer p´ ublicas estas bases de datos no ha sido una costumbre general y por lo tanto es mucho m´ as frecuente que cada grupo construya y utilice sus propios datos de entrenamiento y prueba. Haciendo un seguimiento a los c´ orpora que han estado disponibles de manera p´ ublica y que por lo tanto han permitido hacer comparaciones objetivas entre algoritmos de inferencia gramatical de lenguajes regulares, se conocen los siguientes: 27

Los lenguajes de Tomita [Tom82]. Estos son lenguajes sobre el alfabeto Σ = {a, b} que pueden representarse con cuatro estados o menos. Son siete lenguajes: • L1: a∗ • L2: (ab)∗ • L3: Cualquier secuencia que no tenga un n´ umero impar de a’s consecutivas despu´es de un n´ umero impar de b’s consecutivas • L4: Cualquier secuencia que no tenga m´ as de dos a’s consecutivas. • L5: Cualquier secuencia con un n´ umero par de a’s y un n´ umero par de b’s. • L6: Cualquier secuencia cuyo n´ umero de a’s difiera de su n´ umero de b’s en 0 m´ odulo 3. • L7: a∗ b∗ a∗ b∗ Estos lenguajes fueron extendidos posteriormente por Miclet y Gentile y tambi´en por Dupont [Dup94], aumentando 8 lenguajes objetivo m´ as y extendiendo en algunos casos el alfabeto a tres s´ımbolos Σ = {a, b, c}: • L8: a∗ b • L9: (a∗ + c∗ )b • L10: (aa)∗ (bbb)∗ • L11: Cualquier secuencia con un n´ umero par de a’s y un n´ umero impar de b’s. • L12: a(aa)∗ b • L13: Cualquier secuencia con un n´ umero par de a’s. • L14: (aa)∗ ba∗ • L15: bc∗ b + ac∗ a Muestras de entrenamiento para estos lenguajes, utilizadas por Dupont en [Dup94], pueden ser descargadas de la p´ agina de Internet GIB, cuya direcci´ on se provee m´ as adelante en esta secci´ on. Estos datos est´ an orientados a la inferencia de DFAs y han sido utilizados tambi´en en [dlHOV96, PN02]. Los datos generados para el concurso Abbadingo One [LPP98, JP98] siguen estando disponibles en el presente1 , as´ı como el or´ aculo de prueba. En la misma p´ agina se pueden descargar implementaciones del algoritmo traxbar y de tres versiones de EDSM, siendo redBlue una de ellas. Estos c´ orpora comprenden cuatro problemas sencillos de afinamiento y 16 problemas para la competici´ on propiamente dicha. Los problemas de competici´ on corresponden a cuatro tama˜ nos de lenguaje objetivo: 64, 128, 256 y 512 estados y para cada grupo a cuatro grados de densidad de los datos de entrenamiento. El m´etodo para generar los lenguajes objetivo ha sido reutilizado en varios trabajos posteriores [CK02, CK03, BL05] y el formato en que se almacenan las muestras se ha convertido casi en un estandar 1 abbadingo.cs.unm.edu

28

dentro del a ´rea. Estos problemas est´ an orientados a la inferencia de DFAs y tienen una dificultad creciente de modo que algunos de los problemas aun no han sido resueltos. Generador de aut´ omatas Gowachin. Utiliza el mismo m´etodo de generaci´ on de aut´ omatas de Abbadingo One, pero se pueden fijar valores concretos a los par´ ametros de generaci´ on, tambi´en se puede introducir ruido en los datos. Los experimentos reportados por [SJ03, ACS04, CFKdlH04, BO05, LR05] se han realizado utilizando este generador de DFAs que sigue funcionando en la actualidad2 . Los aut´ omatas usados por Oliveira y Silva [OS01] tambi´en est´ an disponibles en Internet3 . Son 115 m´ aquinas de Mealy generadas aleatoriamente, con entradas y salidas en el alfabeto Σ = {0, 1}, su tama˜ no var´ıa entre 3 y 19 estados. Hay 575 conjuntos de entrenamiento, cada uno contiene 20 cadenas de longitud 30. Estos experimentos tambi´en fueron usados por Lang [Lan99] en los experimentos del algoritmo exbar. Los datos de prueba del algoritmo DeLeTe2 [DLT02, DLT04]. Estos datos de entrenamiento y prueba han sido dise˜ nados para probar algoritmos de inferencia de NFAs y est´ an disponibles en Internet4 . Los lenguajes objetivo se han construido a partir de expresiones regulares y NFAs. Son 120 aut´ omatas objetivo, agrupados en cuatro grupos de 30 lenguajes cada uno. Hay cuatro conjuntos de entrenamiento de 50, 100, 150 y 200 muestras respectivamente y 1000 muestras de prueba para cada conjunto. Estos datos tambi´en se han usado tambi´en en [CF03a] y en la investigaci´ on que aqu´ı se reporta. Los datos de prueba del algoritmo de inferencia de UFAs [CF03a] se etiquetan a partir de aut´ omatas no ambiguos, pero tambi´en a partir de DFAs generados aleatoriamente. En la actualidad existen algunas p´ aginas en Internet que procuran recopilar datos y/o algoritmos de inferencia gramatical. Algunos sitios son: GIB (Grammatical Inference Benchmarks Repository and Links)5 . Este sitio pertenece al proyecto Symbiose, que explora la aplicaci´ on de la inferencia gramatical a la bioinform´ atica. Este repositorio contiene datos sint´eticos principalmente, aunque tambi´en contiene otros datos sacados de problemas reales. Los c´ orpora aqu´ı recopilados no s´ olo se refieren a lenguajes regulares sino tambi´en a gram´ aticas incontextuales y a transductores. Existe un sitio web dedicado a la inferencia gramatical6 en el cual se pueden encontrar enlaces a algunas aplicaciones concretas, el repositorio GIB y algunos congresos en el a ´rea. 2 abbadingo.cs.unm.edu/gowachin 3 enbedded/eecs.berkeley.edu/Alumni/aml 4 http://www.grappa.univ-lille3.fr/∼lemay/ seleccionar Recherche y luego seleccionar Annexes 5 www.irisa.fr/symbiose/people/coste/gi benchs.html 6 eurise.univ-st-etienne.fr/gi/

29

LearnLib7 es una biblioteca de funciones orientadas a la inferencia gramatical de lenguajes regulares a trav´es de aprendizaje activo.

2.3.1.

T´ ecnicas de Generaci´ on de Aut´ omatas Aleatorios

Dado el inter´es que para esta investigaci´ on tiene el generar datos de entrenamiento y prueba, se presentan con m´ as detalle dos maneras de realizar esta tarea que han sido exitosamente aplicadas en varias experimentaciones anteriormente. Generaci´ on de aut´ omatas para Abbadingo One [LPP98]. El procedimiento utilizado para generar los aut´ omatas objetivo de n estados consta de los siguientes pasos: primero se construye un digrafo de grado 2 con 45 n nodos, luego se escoge aleatoriamente un estado inicial y se extrae el subgrafo alcanzable desde ´el, finalmente se etiquetan aleatoriamente los estados del grafo como estados de aceptaci´ on o rechazo. Este procedimiento produce grafos con una distribuci´ on de probabilidad centrada en n y una distribuci´ on de profundidades de los estados centrada cerca de 2log2 n − 2. La variaci´ on en el tama˜ no no tiene mayor incidencia, pero la variaci´ on en la profundidad complica la construcci´ on del conjunto de muestras de entrenamiento, as´ı que una vez se genera el grafo, este es desechado si su profundidad no es exactamente 2log2 n − 2. Generaci´ on de DFAs aleatorios [CP05]. Este m´etodo se caracteriza por producir DFAs aleatorios uniformemente distribuidos entre todos los DFA con el mismo n´ umero de estados. Para generar los aut´ omatas se parte de tuplas extendidas, que posteriormente dan origen a a ´rboles extendidos y los a ´rboles extendidos a aut´ omatas deterministas. La uniformidad en la distribuci´ on se garantiza ya que se muestra una forma de obtener tuplas extendidas aleatorias uniformemente distribuidas. Dado que a cada tupla corresponde un s´ olo a ´rbol extendido, el a ´rbol tambi´en est´ a uniformemente distribuido en su dominio y de cada a ´rbol se elige aleatoriamente uno de los aut´ omatas que puede producir, con lo cual el aut´ omata tambi´en resulta estar uniformemente distribuido en su propio dominio. Como detalle matem´ atico vale la pena comentar que el n´ umero de tuplas extendidas y a ´rboles extendidos crece siguiendo los N´ umeros de Catal´ an. Las experimentaciones en [CF03b, DLT04] han utilizado este m´etodo para la generaci´ on de DFAs. En este proyecto se utiliz´ o este m´etodo de generaci´ on para desarrollar el denominado Corpus de DFAs aleatorios.

2.3.2.

Criterios de Evaluaci´ on para Algoritmos de Inferencia Gramatical

Los criterios de evaluaci´ on pueden variar de acuerdo a los objetivos de la evaluaci´ on; sin embargo, en general el criterio de evaluaci´ on m´ as com´ un es la tasa de acierto sobre muestras de prueba, algunas veces se le llama exactitud (en ingl´es accuracy). Otro criterio muy importante es el tama˜ no de las hip´ otesis producidas por el algoritmo. 7 jabc.cs.uni-dortmund.de/opencms/jabc/pugins/learnLib

30

En los experimentos estilo Abbadingo One [LPP98], se eval´ ua el criterio de exactitud, ya que el or´ aculo s´ olo acepta la entrada cuando ella corresponde a una exactitud mayor o igual al 99 %; sin embargo en este caso se involucra otra variable que es la densidad de la muestra de entrenamiento, a menor densidad es m´ as dif´ıcil lograr una exactitud elevada. En los experimentos del algoritmo DeLeTe2 [DLT04] se mide la exactitud. Adicionalmente se usa un criterio para comparar dos algoritmos, por ejemplo, A y B. Para cada bloque del corpus, se cuenta cuantas veces la exactitud de A fue mayor que la de B, cuantas veces B fue mejor que A y cuantas veces empataron (se maneja un peque˜ na holgura para considerar que ha habido empate). Se reportan los tres valores obtenidos.

31

Cap´ıtulo 3

La Mezcla de Estados La mezcla de estados es una caracter´ıstica com´ un a una variedad de algoritmos de inferencia gramatical como: RPNI, traxbar, redBlue, exbar, DeLeTe2 y todos los algoritmos que se proponen en esta investigaci´ on. La mezcla permite disminuir el tama˜ no de la hip´ otesis de inferencia y generalizar el lenguaje que acepta; si se hace correctamente, de manera que mantenga la consistencia con las muestras de entrenamiento, es un mecanismo que puede llevar a la convergencia en el l´ımite. En este cap´ıtulo se presentan las relaciones de inclusi´ on en cuanto a su relaci´ on con la mezcla de estados y sus posibles aplicaciones en el dise˜ no de algoritmos de inferencia gramatical. Tambi´en se explica el mecanismo b´ asico de mezcla de estados y algunas variaciones que se han evaluado durante del desarrollo de este trabajo; estas variaciones ser´ an mencionadas m´ as adelante cuando se describan los algoritmos que las han utilizado. Igualmente se presentan las reflexiones que se han realizado sobre la convergencia en el l´ımite de la mezcla de estados y el principal resultado te´ orico obtenido, que consiste en demostrar que el orden de las mezclas de estados no afecta la convergencia en el l´ımite, tanto si se trabaja con modelos deterministas como no deterministas.

3.1.

Relaciones de Inclusi´ on

La relaci´ on de inclusi´ on se relaciona directamente con la mezcla de estados, ya que dados dos estados p y q, (p ≺ q ∧ q ≺ p) ⇔ p ' q, dicho en palabras: p est´ a incluido en q y q est´ a incluido en p si y s´ olo si p y q son no obviamente distinguibles y por lo tanto pueden mezclarse. Sin embargo, la relaci´ on de inclusi´ on es menos estricta que la relaci´ on de no-distinguibilidad, es decir, siempre que hay no-distinguibilidad hay inclusi´ on, pero no siempre que hay inclusi´ on hay no-distinguibilidad. Esto lleva a considerar que las relaciones de inclusi´ on entre estados pueden aportar informaci´ on u ´til en el proceso de inferencia gramatical. En esta secci´ on se destacan dos maneras concretas de aprovechar esa informaci´ on que son la duplicaci´ on de transiciones y la definici´ on de valores de salida, pero antes de entrar en materia, se define el a ´rbol de mezcla, que es una construcci´ on importante para expresar el procedimiento de la mezcla de estados.

32

3.1.1.

´ El Arbol de Mezcla

Sea M = (Q, Σ, {0, 1, ?}, δ, Φ, q0) una m´ aquina de Moore determinista. El a ´rbol de mezcla asociado a p, q ∈ Q es una lista de parejas (x, y) formada por los estados alcanzables desde p y q, cuando se avanza simult´ aneamente a partir de ellos con el mismo sufijo en orden lexicogr´ afico. El Algoritmo 6 explica con detalle el procedimiento de construcci´ on. El a ´rbol de mezcla se usa en este trabajo en la detecci´ on de relaciones de inclusi´ on y en la implementaci´ on de la mezcla determinista. Algoritmo 6 arbolMezcla(M, p, q) Require: M = (Q, Σ, {0, 1, ?}δ, Φ, q0) Require: p, q ∈ Q 1: list1 := {} 2: list2 := {(p, q)} 3: while list2 6= {} do 4: (x, y) := f irst(list2) 5: list2 := list2 − {(x, y)} 6: list1 := list1 ∪ {(x, y)} 7: for a ∈ Σ do 8: if δ(x, a) ∧ δ(y, a) est´ an definidos then 9: list2 := list2 ∪ {(δ(x, a), δ(y, a))} 10: end if 11: end for 12: end while 13: Return list1 La Figura 3.1 muestra una m´ aquina de Moore a partir de la cual, considerando la pareja de estados (1, 2) se obtiene el a ´rbol de mezcla que presenta la Figura 3.2. En el a ´rbol cada nodo corresponde a una pareja de estados de la m´ aquina, se avanza en el a ´rbol movi´endose en la m´ aquina hacia el sucesor de ambos estados con un mismo s´ımbolo. Si alguno de los estados no tiene sucesor, no se avanza en esa direcci´ on. El s´ımbolo que permite el avance se muestra asociado a cada arco del a ´rbol. Recordar que, en el esquema del a ´rbol +x significa Φ(x) = 1, −x significa Φ(x) = 0. y si no hay ning´ un s´ımbolo significa Φ(x) =?. Aunque gr´ aficamente siempre se va a presentar el a ´rbol de mezcla en forma arborescente, la informaci´ on se representa en una lista, para el ejemplo tal lista es: {(+1, +2), (+1, 4), (+2, +3), (+2, 6), (+1, 5), (4, 8), (+1, 7), (6, 10), (+1, 9), (8, +12), (+2, 11), (4, −13)} 0

4 0

1

1

2

0

5

0

7

0

9

1

11

0

13

1 1

3

6

0

8

1

10

0

12

´ Figura 3.1: M´ aquina de Moore Inicial Usada para Ilustrar qu´e es un Arbol de Mezcla

33

0 0

(+1,+2)

(+1,4)

(+2,6)

0

(4,8)

1

(6,10)

0

(8,+12)

(+1,5)

0

(+1,7)

0

(+1,9)

1

(+2,11)

1

1

0

(4,-13)

(+2,+3)

´ Figura 3.2: Arbol de mezcla para los estados 1 y 2

3.1.2.

Duplicaci´ on de Transiciones

Cuando se habla de inclusi´ on entre estados de un aut´ omata, se hace referencia a la inclusi´ on entre los lenguajes por la derecha asociados a dichos estados (como se ha mencionado en la Secci´ on 1.3). La relaci´ on de inclusi´ on, definida por Denis et. al. [DLT02] juega un papel muy importante en la teor´ıa de los RFSAs y tambi´en es de utilidad en el dise˜ no de algoritmos que infieren RFSAs. El hecho que dos estados p y q est´en relacionados mediante inclusi´ on (p ≺ q) en un aut´ omata A, significa que L(A, p) ⊆ L(A, q) lo que se ilustra en la Figura 3.3, donde se representa el lenguaje por la derecha de p como un a ´rea triangular con un relleno a rayas a partir de dicho estado, el lenguaje por la derecha de q es un a ´rea m´ as grande de fondo blanco, en la cual se distingue como subconjunto el mismo lenguaje por la derecha de p. Conocer que dos estados guardan entre s´ı una relaci´ on de inclusi´ on permite ajustar el aut´ omata para que en caso de eliminar el estado incluyente, el estado incluido reconozca correctamente la porci´ on de lenguaje por la derecha que comparten.

p





 

 

 

 

 

 

 

   



  

  

  

  

  

  

  

   
 
 
 
 
 
 
 
  


 


 


 


 


 


 


















































 























 








q

Figura 3.3: Ilustraci´ on de los lenguajes residuales asociados a los estados p y q, dado que p ≺ q. Se representa el lenguaje por la derecha de p como un a ´rea triangular con relleno a rayas a partir de dicho estado, el lenguaje por la derecha de q es un a ´rea m´ as grande de fondo blanco, en la cual se distingue como subconjunto el mismo lenguaje por la derecha de p

Cuando la informaci´ on de las muestras es suficiente, se puede establecer la relaci´ on de inclusi´ on entre dos estados p y q revisando su a ´rbol de mezcla. Si existe en el a ´rbol una o m´ as parejas cuyos valores de salida sean de la forma (−x, +y), se puede concluir que p ≺ q, ya que existe al menos una cadena que pertenece al lenguaje residual de y que no pertenece al lenguaje residual de x. Si por el contrario, se encuentra una o m´ as parejas con valores de salida de la forma (+x, −y), se concluye la relaci´ on contraria p  q. En el ejemplo de la Figura 3.4 al considerar la pareja (+0, −11) se establece que la relaci´ on entre 0 y 3 es 0  3. Si se encuentran ambos tipos de parejas en el mismo a ´rbol 34

los estados no guardan entre s´ı relaci´ on de inclusi´ on (otros autores se refieren a esta condici´ on como estados no-comparables o tambi´en como estados obviamente distinguibles) y si no hay ninguna de las dos combinaciones de valores, la relaci´ on entre los estados no puede establecerse con la informaci´ on disponible. (+0,8)

0

0

(+0,-11)

0

(+0,14)

1

(+0,6)

(6,-18)

(+3,16) 1

0

(+0,+3)

0

(+3,9)

0

(6,12)

1

0

(12,+17)

(9,15)

1

(+3,+13) ´ Figura 3.4: Arbol de Mezcla a partir de los estados 0 y 3 Una manera de actuar sobre el aut´ omata, cuando se conoce la relaci´ on de inclusi´ on entre dos estados, consiste en redireccionar los arcos que llegan al estado incluyente, para que lleguen tambi´en al estado incluido. Esto garantiza que en caso que el estado incluyente desaparezca, el estado incluido aceptar´ a adecuadamente la porci´ on de lenguaje residual que comparten; si igual cosa ocurre en todos los estados incluidos por un estado compuesto, ´el podr´ a ser eliminado sin afectar el lenguaje aceptado por el aut´ omata. La Figura 3.5 muestra gr´ aficamente en qu´e consiste la redirecci´ on de los arcos: en la parte izquierda de la Figura (ANTES), los prefijos del estado q se representan con una regi´ on triangular que llega al estado y que tiene un relleno en zigzag y los prefijos del estado p como una regi´ on triangular que llega al estado y tiene un relleno en c´ırculos; una vez se realiza la redirecci´ on de los arcos, es decir, en la parte derecha de la Figura (DESPUES), en el esquema del estado p se aprecian sus propios prefijos y tambi´en los prefijos de q que ahora tambi´en llegan a p. En ese mismo diagrama del estado p se aprecia claramente que en esta situaci´ on el estado p es capaz de reconocer las mismas cadenas que el estado q en el a ´mbito del lenguaje residual que comparten. El Algoritmo 7 realiza este procedimiento. Debe destacarse que la introducci´ on de estos arcos, que en principio son redundantes, puede convertir el aut´ omata en no determinista. Algoritmo 7 incluido(M, p, q) Require: M = (Q, Σ, {0, 1, ?}δ, Φ, q0) Require: p, q ∈ Q, p ≺ q 1: for r : r ∈ Q, a ∈ Σ, δ(r, a) = q do 2: δ = δ ∪ {δ(r, a) = p} 3: end for 4: Return M

3.1.3.

Definici´ on de Valores de Salida

Considerar las relaciones de inclusi´ on entre estados tiene otro aspecto que puede aprovecharse en el dise˜ no de algoritmos de inferencia gramatical: una 35










   







   










         















       







 
 
 
 
 
 
 


 












             







          






 

 

 
            







 

 

 
      
  






 







      

 
 
 
 
 
 
 
   

  
  
  
  
  
  
  
   






 

  

 
 
 
 
 
 
 
 












            
       
 
      





             


 
 
 
 
 
 
 
   
 
 
 
 
 
 
 
   









  
 
 
 
  

 
 
 
 
  
 
 
 
 
  







  
  
  
  
     
      



             
 
 
 
 
 



q

q

 
 
 
 
 









 
 
 
 
 
























































p

p

ANTES

DESPUES

Figura 3.5: Ilustraci´ on de los Lenguajes Residuales Asociados a los Estados p ≺ q Despues de Redireccionar las Transiciones. Los prefijos del estado q se representan con una regi´ on triangular que llega al estado y que tiene un relleno en zigzag, en el esquema del estado p se aprecian sus propios prefijos, como una regi´ on con relleno en c´ırculos y tambi´en los prefijos de q que ahora tambi´en llegan a p. En el diagrama se aprecia claramente que en esta situaci´ on el estado p es capaz de reconocer las mismas cadenas que el estado q en el a ´mbito del lenguaje residual que comparten.

vez se establece una relaci´ on de inclusi´ on entre dos estados y se concluye que ellos no son equivalentes (es decir, que no existe inclusi´ on en ambos sentidos) esta informaci´ on puede servir para dar valor de salida a estados que hasta el momento tienen valor indefinido. Para ello se toma en cuenta una pareja de estados cuya relaci´ on de inclusi´ on se conoce (o se supone) y su correspondiente a ´rbol de mezcla. El razonamiento es el siguiente: si p ≺ q, y las muestras de entrenamiento son consistentes, ninguna pareja de estados descendientes de (p, q) en el a ´rbol de mezcla podr´ an tener relaciones del estilo (+r, −s), ya que ello llevar´ıa a una inconsistencia. Eso significa que si p ≺ q y en el a ´rbol de mezcla se tiene la pareja (r, s) tal que r es descendiente de p, s es descendiente de q, Φ(r) = 1 y Φ(s) =? se puede afirmar que Φ(s) = 1 porque en caso que su valor fuera 0 causar´ıa una inconsistencia; an´ alogamente, si Φ(r) =? y Φ(s) = 0, se puede afirmar que Φ(r) = 0 porque otra opci´ on introduce inconsistencia. Si la relaci´ on conocida es p  q y en el a ´rbol de mezcla existe una pareja (r, s) con Φ(r) = 0 y Φ(s) =? se puede afirmar que Φ(s) = 0 y si Φ(r) =? y Φ(s) = 1, entonces Φ(s) = 1, por las mismar razones ya expuestas. Los nuevos valores de salida que se van adicionando al aut´ omata a medida que se detectan relaciones de inclusi´ on y se dan las condiciones aqu´ı descritas, aumentan la informaci´ on disponible como si se ampliaran las muestras de entrenamiento a medida que avanza la inferencia [GRCA05]. El Algoritmo 8 presenta m´ as exactamente la manera de proceder dados dos estados p y q tales que p ≺ q. Ejemplo 2 La Figura 3.6 ilustra un aut´ omata que puede encontrarse en medio de un proceso de inferencia, notar que existen bastantes estados cuyo valor de salida se ignora. La Figura 3.7 muestra el a ´rbol de mezcla correspondiente a la pareja de estados (+1, +2) del aut´ omata de la Figura 3.6 con los respectivos valores de salida de los estados. Suponiendo que la relaci´ on entre 1 y 2 es 2 ≺ 1, la pareja (8, +12) permite asignar Φ(8) = 1 y a trav´es de la pareja (4, +8) se 36

Algoritmo 8 definirValoresSalida(M, p, q) Require: M = (Q, Σ, {0, 1, ?}, δ, Φ, q0) Require: p, q ∈ Q, p ≺ q 1: M 0 := M // M 0 = (Q, Σ, {0, 1, ?}, δ, Φ0, q0 ) 2: while p y q no son no-comparables do 3: arbol := arbolM ezcla(M 0, p, q) 4: for (u, v) ∈ arbol do 5: if Φ(u) = 1 ∧ Φ(v) =? then 6: Φ(v) := 1 7: end if 8: if Φ(u) =? ∧ Φ(v) = 0 then 9: Φ(u) := 0 10: end if 11: end for 12: end while 13: if p y q son no-comparables then 14: Return M 15: else 16: Return M’ 17: end if

asigna Φ(4) = 1. El nuevo estado del aut´ omata se observa en la Figura 3.8.

0

4 0 1

1

2

0

5

0

7

0

9

1

11

0

13

1 1

3

6

0

8

1

10

0

12

Figura 3.6: Aut´ omata Ejemplo donde 1  2

0 0

(+1,+2)

(+1,4)

1

(+2,6)

0

(4,8)

1

(6,10)

0

(8,+12)

(+1,5)

0

(+1,7)

0

(+1,9)

1

(+2,11)

1 0

(4,-13)

(+2,+3)

´ Figura 3.7: Arbol de mezcla a partir de los estados 1 y 2

En resumen, si se dise˜ na un algoritmo enfocado a la detecci´ on y eliminaci´ on de estados compuestos, las relaciones de inclusi´ on permiten transformar la m´ aquina manteniendo el lenguaje que reconoce; si el algoritmo se enfoca a la mezcla de estados, el aumentar la informaci´ on sobre los valores de salida de los estados permite tomar decisiones m´ as informadas. 37

0

5

0 4

0 1

1

2

7

0

9

1

11

0

13

1 6

1

0

0

8

1

10

0

12

3

Figura 3.8: Aut´ omata Despu´es de Haber Definido Algunos Valores de Salida

3.2.

El Mecanismo B´ asico de Mezcla de Estados

Algoritmo 9 merge(M, p, q) Require: M = (Q, Σ, {0, 1, ?}δ, Φ, q0) Require: p, q ∈ Q, p  q en orden lexicogr´ afico 1: if Φ(p) 6=? ∧ Φ(q) 6=? ∧ Φ(p) 6= Φ(q) then 2: Return M 3: end if 4: if Φ(p) =? then 5: Φ(p) := Φ(q) 6: end if 7: for s ∈ Σ do 8: for r : δ(r, s) = q do 9: δ := δ ∪ {δ(r, s) = p} 10: δ := δ \ {δ(r, s) = q} 11: end for 12: end for 13: for s ∈ Σ do 14: for x : δ(q, s) = x do 15: δ := δ ∪ {δ(p, s) = x} 16: δ := δ \ {δ(q, s) = x} 17: end for 18: end for 19: Q := Q \ {q} 20: Return M La mezcla de estados, en el sentido que aqu´ı se aplica, es una operaci´ on que se realiza sobre un modelo que puede ser determinista o no y que se centra en dos estados espec´ıficos que se fusionan en uno s´ olo. El Algoritmo 9 realiza la mezcla de dos estados p y q en una M´ aquina de Moore determinista M . Es condici´ on necesaria para poder realizar la mezcla que los dos estados tengan valores de salida compatibles, esto es que tengan el mismo valor o que al menos uno de los dos tenga valor indefinido (ver l´ınea 1 del Algoritmo 9). Si el estado que permanece ten´ıa valor de salida indefinido antes de la mezcla, toma el valor de salida del estado eliminado (l´ıneas 3 y 4). Como efecto de la mezcla el aut´ omata se modifica para que el estado p reciba todos los arcos que llegaban al estado q (l´ıneas 7-12) y emita todos los arcos que sal´ıan de ´el (l´ıneas 13-18). Finalmente, el estado q desaparece. La Figura 3.9 muestra un aut´ omata intermedio en un proceso de inferencia, observar los estados 1 y 4 con sus respectivos predecesores 38

y sucesores, la Figura 3.10 muestra las modificaciones que causa la mezcla de dichos estados. 4

0 1

0,1

2

1

8

1 5

0

9

Figura 3.9: Aut´ omata Antes de la Mezcla de los Estados 1 y 4 1

8

0,1

1

2

0

1

5

0

9

Figura 3.10: Aut´ omata despu´es de haber mezclado los estados 1 y 4 sin propagaci´ on La modificaci´ on que sufren las transiciones al realizar la mezcla de dos estados puede causar no determinismo, lo cual es una caracter´ıstica indeseable en algoritmos que infieren m´ aquinas deterministas, esto suele resolverse propagando la mezcla. El Algoritmo 10 realiza la mezcla con propagaci´ on, para ello utiliza una cola en la que va adicionando las parejas de estados que, por efecto de la mezcla ya realizada, y para evitar el no determinismo, deben ser mezcladas tambi´en. La propagaci´ on debe extenderse hasta que desaparezca el no determinismo, pero fallar´ a en el caso que trate de mezclar dos estados con valores de salida inconsistentes, en ese caso la subrutina retorna la m´ aquina que entr´ o sin efectuarle ning´ un cambio (l´ıneas 6 y 7). En la Figura 3.10, el no determinismo se aprecia en el estado 1 del cual parten dos arcos con el s´ımbolo 0, en este caso la propagaci´ on consiste en mezclar los estados 2 y 8, cuyo resultado se aprecia en la Figura 3.11. 1

0,1

2

1

5

0

9

0

Figura 3.11: Aut´ omata despu´es de haber mezclado los estados 1 y 4 con propagaci´ on La mezcla de estados causa generalizaci´ on en el lenguaje aceptado, porque el redireccionamiento de arcos genera bucles y nuevos caminos que permiten aceptar otras cadenas adem´ as de las muestras de entrada. Por ejemplo, observar que la cadena 0011 es rechazada antes de la mezcla (ver Figura 3.9), en cambio despu´es de la mezcla es aceptada (ver Figuras 3.10 y 3.11). Desde el punto de vista de la inferencia gramatical, no se puede afirmar que esta generalizaci´ on acerque el modelo actual a una representaci´ on del lenguaje objetivo. Ello depende de estrategias externas a la mezcla misma como pueden ser evaluar la consistencia del nuevo modelo con las muestras de entrenamiento.

39

Algoritmo 10 detmerge(M, p, q) Require: M = (Q, Σ, {0, 1, ?}δ, Φ, q0) Require: p, q ∈ Q, p  q en orden lexicogr´ afico 1: M 0 := M 2: list := {(p, q)} 3: while list 6= ∅ do 4: (r, s) := F irst(list) 5: M1 := merge(M 0 , r, s) 6: if M1 = M 0 then 7: Return M 8: else 9: M 0 := M1 10: for a ∈ Σ do 11: if δ(p, a) y δ(q, a) est´ an definidos then 12: list := append(list, (δ(p, a), δ(q, a))) 13: end if 14: end for 15: end if 16: end while 17: Return M 0

3.3.

La Mezcla No-Determinista de Estados

Al estudiar la mezcla de estados en la inferencia de m´ aquinas no deterministas, surge la necesidad de adaptar el modo de proceder, ya que en este caso lo que hasta ahora se ha llamado a ´rbol de mezcla se convierte en una estructura m´ as compleja debido a la existencia de varios sucesores de un estado con un mismo s´ımbolo. Para que la mezcla sea completa debe considerar todas las opciones del no determinismo. El contexto en el que se propone realizar esta mezcla es el conocido como blue-fringe, en el cual se parte del a ´rbol de prefijos de Moore de las muestras de entrada y se definen dos conjuntos de estados: el conjunto rojo formado por los estados que ya han sido procesados y forman parte de la hip´ otesis actual y el conjunto azul formado por los estados hijos de los estados rojos que a su vez no son rojos, es decir los estados que est´ an en la frontera entre la porci´ on del modelo que ya se ha procesado y el resto. Se mezcla siempre un estado rojo con un estado azul, esto limita el n´ umero de parejas candidatas para la mezcla, ya que a falta de este criterio se deber´ıa intentar mezclar todas las parejas de estados posibles, tal como ocurre en el algoritmo EDSM. Mezclar un estado del conjunto rojo con un estado del conjunto azul garantiza que aunque el estado rojo puede verse como la ra´ız de un subgrafo que puede ser no determinista, el nodo azul es siempre la ra´ız de un sub´ arbol que es una porci´ on determinista de la m´ aquina actual, por ese motivo la mezcla de una pareja rojo, azul es siempre finita, ya que no hay posibilidad de encontrar ciclos en el a ´rbol de mezcla; de hecho, se ver´ a m´ as adelante que el m´etodo tiene coste polinomial. El sub´ arbol con ra´ız en el estado azul establece la forma del a ´rbol de mezcla, en tanto que los sufijos que lo forman proporcionan una manera ordenanda de recorrerlo; a medida que se avanza por cada rama, se avanza simult´ aneamente por el subgrafo con ra´ız en el estado rojo, abarcando todos los 40

caminos que permita el no determinismo. El Algoritmo 11 muestra esta manera de proceder.

Algoritmo 11 nodetmerge(M, p, q) Require: M = (Q, Σ, {0, 1, ?}δ, Φ, q0) Require: p ∈ conjunto rojo y q ∈ conjunto azul 1: M 0 := M 2: for cadena ∈ Suf (q) do 3: rojos := {p} 4: azul := q 5: for simbolo ∈ cadena do 6: for r ∈ rojos do 7: M1 := merge(M 0 , r, q) 8: if M1 = M 0 then 9: Return M 10: else 11: M 0 := M1 12: end if 13: end for 14: rojos0 := {} 15: for r ∈ rojos do 16: if δ(r, simbolo) esta definido then 17: rojos0 := rojos0 ∪ δ(r, simbolo)) 18: end if 19: end for 20: rojos := rojos0 21: q := δ(q, simbolo) 22: end for 23: end for 24: Return M 0

Ejemplo 3 La m´ aquina de Moore de la Figura 3.12 presenta un hipot´etico estado intermedio en un proceso de inferencia que requiere mezcla no determinista, se van a mezclar los estados 2 y 3. El estado 2 pertenece al conjunto rojo, es decir a la porci´ on de la m´ aquina que puede ser no determinista, en tanto que el estado 3 pertenece a la porci´ on arborescente y determinista. El primer paso consiste en extraer los sufijos del estado 3, en este caso hay un u ´nico sufijo que es la cadena 010. La mezcla que se va a realizar, se representa claramente mediante el trellis del Cuadro 3.1, en el cual cada columna est´ a asociada a un s´ımbolo del sufijo y hay dos filas principales asociadas con los estados que se van a mezclar. La fila superior, correspondiente al estado 2, ubica bajo cada s´ımbolo el conjunto de estados alcanzables desde los estados de la columna anterior con dicho s´ımbolo. Por ejemplo, la primera columna contiene los estados 2 y 4 porque ellos son alcanzables desde 2 con el s´ımbolo 0 y el estado 6 que es alcanzable desde 3 con dicho s´ımbolo. Esta columna indica que los estados (2, 4, 6) deben mezclarse para convertirse en uno s´ olo. La segunda columna, correspondiente al s´ımbolo 1, indica la mezcla de los estados (5, 7). Una vez realizada la mezcla, la 41

m´ aquina de Moore tiene el aspecto que se muestra en la Figura 3.13. 0 4 0 2 0

1

1

5 1 3

0

6

1

7

0

8

Figura 3.12: Aut´ omata donde se va a realizar la mezcla no determinista de los estados 2 y 3

Cuadro 3.1: Trellis que ilustra la mezcla no determinista de los estados 2 y 3 siguiendo el prefijo 010 0 1 0 2 2 5 4 3 6 7 8

0

1

0,1

2

1

5

0

8

Figura 3.13: Aut´ omata despu´es de realizar la mezcla no determinista de los estados 2 y 3

Teniendo en cuenta que la mezcla no determinista necesita recorrer el sub´ arbol que pende del estado azul, lo que en peor caso puede costar O(n), donde n es el tama˜ no de la muestra de entrada y que internamiente realiza una mezcla determinista de coste O(n), el coste de la mezcla no determinista tiene como cota superior O(n2 ).

3.4.

Importancia del Orden de Mezcla

Dado un a ´rbol aceptor de prefijos correspondiente a una muestra dada, existen muchas maneras de proceder a la mezcla de estados, desde tiempo atr´ as se conoce que existen ordenamientos que permiten obtener m´ as r´ apidamente la convergencia que otros. Hay que recordar que en la pr´ actica los algoritmos de mezcla funcionan sobre una muestra incompleta del lenguaje objetivo cuyas propiedades no se conocen, no se sabe si es una muestra caracter´ıstica o si es una muestra universal, por ejemplo; esto implica que cuando se agrupan dos estados y se verifica que el nuevo modelo sea consistente con las muestras, la consistencia se puede obtener o ´ bien porque efectivamente se ha detectado un estado 42

redundante y se ha eliminado o ´ bien porque las muestras negativas disponibles fueron insuficientes para detectar la inconsistencia. En consecuencia, entre menos informaci´ on de entrenamiento se tenga hay una mayor posibilidad de que el algoritmo mezcle estados que no deber´ıa. Realizar una mezcla equivocada se puede reflejar en un tama˜ no m´ as grande de lo necesario en la hip´ otesis final y tambi´en en una menor tasa de reconocimiento de dicha hip´ otesis. Ambas cosas debidas a que dicha mezcla aleja la hip´ otesis del verdadero aut´ omata objetivo. Una mezcla equivocada que se realiza al principio del proceso de inferencia es mucho m´ as perjudicial que una que se realiza al final, porque una vez que se lleva a cabo una mezcla, todas las decisiones posteriores est´ an determinadas por ella. Con estas ideas en mente, un criterio importante al elegir un ordenamiento de los estados a mezclar ser´ a aquel que ayude a minimizar las mezclas incorrectas, siempre limitados por la informaci´ on que proporcionen las muestras disponibles. Tal vez el primer criterio de ordenamiento que se utiliz´ o fue el orden lexicogr´ afico, que aplica el algoritmo RPNI [OG92]. Se sabe que la mezcla determinista s´ olo se hace efectiva si no encuentra ninguna inconsistencia al visitar todo el a ´rbol de mezcla. Si el a ´rbol de mezcla es grande hay mayor informaci´ on a contrastar antes de dar por v´ alida la mezcla, en cambio si el a ´rbol es muy peque˜ no la mezcla se puede aceptar con muy poca informaci´ on al respecto. Por eso, empezar en orden lexicogr´ afico puede ser una buena idea, ya que los primeros estados en ser considerados son aquellos de los que penden los a ´rboles de mezcla m´ as grandes y a medida que la inferencia avanza se van considerando parejas con a ´rboles de mezcla cada vez m´ as peque˜ nos. En principio, este m´etodo podr´ıa evitar mezclas equivocadas en los primeros niveles, donde son m´ as perjudiciales. Observando el comportamiento de la inferencia en orden lexicogr´ afico, se not´ o que el hecho que el a ´rbol de mezcla sea grande no implica necesariamente que contenga m´ as informaci´ on, ya que la informaci´ on se encuentra en los valores de salida de los estados y puede ocurrir que dichos valores sean indefinidos, haciendo que aunque el a ´rbol de mezcla conste de muchos nodos no sea posible detectar inconsistencias. Esto llev´ o a considerar un orden en las mezclas que dependa directamente de la informaci´ on contenida en las muestras, dando prioridad a la mezcla mejor soportada por ellas. El esquema general lo propuso De la Higuera [dlHOV96] y consiste en establecer un conjunto de parejas candidatas a mezclarse, asociar a cada una de ellas un puntaje calculado con respecto al a ´rbol de mezcla y a las muestras de entrenamiento y finalmente mezclar la pareja que obtenga el mayor puntaje. Se pueden proponer diversos criterios para asignar el puntaje, inicialmente se contaba el n´ umero de estados con valor de salida diferente de indefinido en el a ´rbol de mezcla. Sin embargo, un criterio m´ as apropiado fue el propuesto por Lang y Price [LPP98] de contar las coincidencias entre los valores de salida de las parejas que forman el a ´rbol de mezcla; es decir, cada pareja de la forma (+x, +y) o ´ (−x, −y) incrementa en uno el puntaje. Este valor base, se complementa con otro t´ermino que privilegia la pareja de estados que se encuentre a menor profundidad en el modelo (es decir, m´ as cerca del estado inicial). Aunque en la siguiente secci´ on se muestra que cualquier orden que se elija para realizar las mezclas de estados converge en el l´ımite, desde el punto de vista pr´ actico elegir un orden adecuado para realizar las mezclas es una l´ınea muy 43

importante de trabajo, porque aporta velocidad en el proceso de convergencia.

3.5.

Convergencia de la Mezcla de Estados

3.5.1.

Convergencia de la Mezcla de Estados en M´ aquinas Deterministas

En este apartado se va a demostrar que la inferencia gramatical de lenguajes regulares mediante mezcla de estados es una estrategia que converge en el l´ımite, independientemente del orden en el cual se realicen las mezclas. La experimentaci´ on muestra que el tiempo de convergencia se puede reducir significativamente al elegir un orden de mezcla concreto, el orden lexicogr´ afico o la estrategia blue-fringe son alternativas que convergen r´ apidamente. Sin embargo, cualquier otro orden que se elija tambi´en termina por converger. El argumento de la demostraci´ on es el siguiente: dada una enumeraci´ on cualquiera de Σ∗ y una muestra caracter´ıstica, por construcci´ on de la muestra, un algoritmo de mezcla de estados que proceda en el orden de la enumeraci´ on de Σ∗ converge en el l´ımite al DFA m´ınimo del lenguaje objetivo. El primer paso consiste en, dada una muestra positiva cualquiera, convertirla en una muestra caracter´ıstica. Definici´ on 4 Dada una enumeraci´ on de Σ∗ , sea D+ una muestra estructuralmente completa y sea n el estado con m´ as alto valor en la enumeraci´ on de AP M (D+ ). Si se amplia D+ de modo que aparezcan todos los prefijos de palabras del lenguaje con valor menor que n en la enumeraci´ on y para cada par de estados de AP M (D+ ) que correspondan a estados diferentes en el aut´ omata objetivo, se a˜ naden las muestras positivas o negativas que sean necesarias para 0 0 0 0 distinguirlos (D+ , D− ). El conjunto (D+ ∪ D+ , D− ) constituye una muestra caracter´ıstica. El Algoritmo 12 ilustra m´ as detalladamente el procedimiento descrito en la definici´ on anterior. La subrutina detmerge(M, i, j) se ha presentado previamente en el Algoritmo 10. La subrutina consistente(M, D) verifica si la m´ aquina M es consistente con el conjunto de muestras D, si la muestra es positiva y la m´ aquina la acepta, o si es negativa y la m´ aquina la rechaza, retorna true; en otro caso retorna f alse. El coste del algoritmo est´ a dado por tres bloques principales: el primer ciclo (l´ıneas 5-9) se realiza n veces, siendo n el m´ aximo valor de la enumeraci´ on asociado con una cadena de D+ ; dependiendo de la enumeraci´ on, este valor puede ser polinomial o exponencial en funci´ on del n´ umero de estados 0 0 de AP M (D+ ∪ D+ ). El segundo ciclo (l´ıneas 10-12) tiene un coste m´ aximo |D+ | y el bloque final (l´ıneas 13-24) tiene un coste cuadr´ atico con respecto al n´ umero 0 de estados dePAP M (D+ ∪ D+ ) y lineal con respecto a n y a la longitud de las muestras O( x:E(x)