SISTEMAS EVOLUTIVOS DE REESCRITURA
Fernando Galindo Soria
IPN - ESCOM
fgalindo@vmredipn.ipn.mx
RESUMEN
Tal vez una de las herramientas más poderosas y desconocidas de la
Matemática actual sean la reglas de reescritura, su fuerza es tan grande que
valdría la pena que su uso se introdujera sin mucho formalismo desde el nivel
de educación primaria y secundaria, sin
embargo y a pesar de que su campo de aplicación es enorme, la potencia
de esta herramienta se ha diluido dentro del concepto de gramática generativa.
Por lo que en este documento se presentaran las reglas de reescritura como una
herramienta independiente de las gramáticas y se mostrara su campo de
aplicación
Como primer punto se dará una breve
introducción al tema y se vera como un sistema de reescritura se puede
representar fácilmente mediante un sistema de información integrado por un
programa de control y un archivo donde se almacenan las reglas de reescritura.
Con esta arquitectura el conocimiento queda independiente del programa y el
proceso de mantenimiento y actualización del sistema se vuelve simple, ya que
si surgen nuevas reglas solo se requiere almacenarlas en el archivo y el
programa no se modifica. Aun más el sistema puede empezar a construir la base
de conocimiento desde cero, ya que el archivo puede estar vacío y el sistema en
forma interativa lo puede empezar ha llenar, con lo que se tiene la base de un
Sistema Evolutivo.
A continuación se mostrara que problemas aparentemente diferentes como
el reconocimiento de imágenes, señales, sistemas experto, tutores, traductores,
lenguaje natural elemental, y prácticamente cualquier problema que se pueda
representar como una cadena de bits o caracteres, son casos particulares de un
problema mas general atacable con reglas de reescritura.
Finalmente se vera que cualquier programa o algoritmo X se puede
representar como un conjunto de reglas de reescritura, que demostrar un
teorema y hacer un programa son actividades equivalentes y que las reglas de
reescritura permiten representar
directamente a las gramáticas tipo cero.
PALABRAS CLAVES
Reglas de Reescritura, Sistemas Evolutivos, Gramáticas y Autómatas,
Sistemas expertos, Lenguaje Natural, Reconocimiento de Imágenes, Voz y Señales.
INTRODUCCIÓN
Una de las herramientas más poderosas y desconocidas de la matemática actual son las reglas de reescritura, descubiertas dentro de la lingüística matemática y aplicadas inicialmente en esta área y más adelante para la construcción de compiladores y en general de sistemas dirigidos por sintaxis.
La fuerza de esta herramienta se ha diluido, porque normalmente solo se aplica como parte de las gramáticas generativas y en particular como reglas de producción, a pesar de que cualquier sistema, sistema formal o sistema evolutivo puede manejar como herramienta de representación a estas reglas. En general cualquier problema de Informática, Computación o Inteligencia Artificial se puede representar en término de reglas de reescritura (es como si el operador de suma sólo se usara para sumar números naturales, hasta que se libera del entorno de los números naturales adquiere toda su importancia ).
Su fuerza es tan grande que
valdría la pena que el uso de estas reglas
se introdujera sin mucho formalismo desde el nivel de primaria y
secundaria, como una herramienta mas de la Matemática, tan importante como la
suma y la resta, ya que abre a los alumnos todo un nuevo universo.
1.) CONCEPTOS GENERALES
Como primer punto partiremos de que un sistema de reescritura <A,B,R> esta formado por un conjunto de elementos de entrada A, un conjunto de elementos de salida B y un conjunto de reglas de reescritura R. (Donde A y B pueden ser iguales o diferentes).
Una regla de reescritura es de la forma:
X--> Y
Donde XeA*, YeB* (A* y B*
representan respectivamente las cerradura de A y B ). Y lo anterior se lee
como: X se puede reescribir como Y y
significa que X se puede sustituir
por Y.
Es relativamente fácil construir un sistema de información que representa a los sistemas de reescritura, por ejemplo el siguiente sistema formado por un programa y un archivo con dos columnas :
|
A1 A2 "" An |
B1 B2 "" Bn |
Programa()
{i=1
lee Ax
mientras ((Ax != Ai) y (no fin de archivo))i++
si (no fin de archivo) escribe Bi
sino escribe "no reconozco Ax"
}
El archivo representa al conjunto de reglas de reescritura:
A1 --> B1
A2 --> B2
"""
An --> Bn
Y el programa representa a un proceso que reescribe Ai como Bi.
2.) PRESENTACIÓN DE LA HERRAMIENTA
GENERAL.
Esta idea se puede aplicar por ejemplo para hacer un traductor automático, donde se puede tener una tabla que contiene en la primera columna el texto en un idioma y en la segunda su traducción a otro idioma.
|
texto este es un perro el perro blanco """ el perro negro |
traducción this is a dog the white dog """ the black dog |
Y un pequeño programa que realiza la sustitución de reglas.
Programa()
{
i=1
lee Textox
mientras ((Textox != Textoi) y (no fin de archivo))i++
si (no fin de archivo) escribe Traduccióni
sino escribe "no conozco el texto"
}
Como se podrá ver el sistema es pequeño y en general trivial de modificar, ya que el conocimiento queda separado del programa, al estar almacenado en registros, por lo que, si se encuentra una nueva regla lo único que se requiere es aumentar un registro en el archivo y el programa no se toca.
Aun mas, se puede hacer que el mismo programa actualice el archivo, de tal manera que si entra un texto desconocido, el programa pueda preguntar (al usuario o a un experto) la traducción asociada, con lo que se tendría un pequeño sistema evolutivo.
|
texto este es un perro el perro blanco """ el perro negro |
traducción this is a dog the white dog """ the black dog |
Programa()
{
i=1
lee Textox
mientras ((Textox != Textoi) y (no fin de archivo))i++
si (no fin de archivo) escribe Traduccióni
sino //entra al dialogo
escribe "desconozco Textox dame su traducción"
lee Traducciónx
almacena en el archivo Textox , Traducciónx
}
Como se podrá ver este programa
es muy simple de hacer y tiene la ventaja de que no requiere tener almacenado
el conocimiento previamente, ya que si el archivo estuviera vacío y se
preguntara por Textox el programa pediría Traducciónx y ya tendría la regla Textox
-> Traducciónx con lo que, el sistema evolutivo puede empezar ha construir la base de
conocimiento y 'aprender' desde cero,
en tiempo real y fácilmente.
Aunque se tienen que tomar en cuenta algunas consideraciones prácticas, por ejemplo que sólo se permita 'enseñar' al sistema a personas con clave de autorización, estos motivos no afectan ni la idea ni la estructura del sistema.
Si seguimos con la misma idea el programa se puede generalizar aun mas y aplicar para atacar otros problemas aparentemente diferentes, como es la construcción de sistemas experto, tutores automatizados y en general al tratamiento restringido de lenguaje natural.
Por ejemplo si se analizan algunos sistemas experto se observa que es común que los programas en su forma más simple tengan una estructura de cascadas de IF's de la forma:
Programa()
{
lee Sx
si Sx = S1 entonces D1 sino
si Sx = S2 entonces D2 sino
''' '''
si Sx = Sn entonces Dn sino
escribe "no reconoce los síntomas"
}
Donde el programa lee los síntomas Sx que da el usuario y los compara con los primeros síntomas almacenados S1, si corresponden entonces envía el diagnóstico D1, sino los compara con los síntomas S2 y así sucesivamente.
El problema de este enfoque es que si se quieren aumentar las reglas o modificar al sistema se tiene que reestructurar el programa. Ahora bien, usando prácticamente el mismo sistema evolutivo desarrollado para la traducción es relativamente fácil construir un programa que generaliza al anterior.
Para lo cual sustituiremos la cascada de IF's por un sistema formado por un archivo de reglas de reescritura de la forma Si --> Di, donde se almacenan los síntomas y diagnósticos.
|
Síntomas S1 S2 "" Sn |
Diagnostico D1 D2 "" Dn |
Y por un pequeño programa que realiza la sustitución de reglas.
Programa()
{
i=1
lee Sx
mientras ((Sx != Si) y (no fin de archivo))i++
si (no fin de archivo) escribe Di
sino //entra al dialogo
escribe "desconozco Sx, dame su diagnostico"
lee Dx
almacena en el archivo Sx , Dx
}
Nuevamente con este sistema se puede tener el archivo vacío y conforme se realiza el proceso de dialogo las reglas del sistema experto se van integrando en forma natural, con lo que se tiene un sistema evolutivo que genera las reglas de inferencia de un sistemas expertos. Lo único que cambia entre el traductor y el sistema experto es que en lugar de escribir:
desconozco texto, dame su traducción
escribe
desconozco Sx, dame su diagnostico
Aun mas, si se cambian las reglas, con el mismo programa se puede tener un sistema de reconocimiento de lenguaje natural elemental. Por ejemplo, en lugar de poner los síntomas y diagnósticos de un sistema experto se pueden poner las preguntas y respuestas de un sistema tutor. En este caso se puede tener una lista de preguntas y respuestas como las siguientes:
|
¿quien descubrió América? ¿cual es la capital de Francia? """ ¿en que continente esta Rusia? |
Colon París """ en Europa |
Entonces el mismo programa funciona como un sistema tutor, donde el alumno pregunta y el sistema responde, y en lugar de síntomas y diagnósticos el sistema tiene preguntas y respuestas, lo cual es interesante ya que el mismo sistema se puede ver como un sistema experto o como un tutor automatizado. Y lo único que cambia es que en lugar de escribir
desconozco Sx, dame su diagnostico
escribiría
no conozco la respuesta, dámela
3.) GENERALIZACIÓN PARA MANEJO DE
SEÑALES
Como se puede ver una gran cantidad de problemas aparentemente diferentes se pueden reducir en primera instancia al mismo sistema, sin embargo no son los únicos casos que se pueden manejar con esta herramienta, ya que prácticamente se puede atacar cualquier problema que se pueda representar como una cadena de bits o caracteres.
Para poder ver lo anterior se trabajara primero con algo muy simple, ya que lo importante no es resolver el problema en toda su complejidad, sino mostrar una de las cosas mas hermosas de la Informática, que el reconocimiento de imágenes, texto, traductores, sistemas experto, señales biofísica, voz, etc., que normalmente se ven como cuestiones completamente diferentes son en realidad casos particulares de un problema general.
Como primer ejemplo se vera un sistema que entrega una imagen a partir de su nombre. Este sistema consta de un archivo con dos columnas, en la primera columna se encuentra el nombre de la imagen y en la segunda su imagen correspondiente -almacenada por ejemplo como cadena de bits-, ademas se cuenta con un programa construido de tal manera que si alguien da el nombre de la imagen Nx regresa su imagen correspondiente Ix y si no la tiene entra en un proceso de dialogo donde la pide y almacena.
|
Nombre N1 N2 "" Nn |
Imagen I1 I2 "" In |
Programa()
{
i=1
lee Nx
mientras ((Nx != Ni) y (no fin de nombres))i++
si (no fin de nombres) escribe Ii
sino //entra al dialogo
escribe "no conozco la imagen dámela"
lee Ix
almacena Ix y Nx
}
Como se puede ver este sistema es prácticamente idéntico al que se ha estado manejando desde el principio para texto con la diferencia de que ahora un lado de la regla de reescritura no es texto.
Ha partir de una idea tan simple es fácil construir un programa que pronuncie palabras ha partir de texto escrito, en este caso en la primera columna se tiene el texto y en la segunda el sonido asociado, en caso de que la computadora no encontrara la cadena escrita puede entrar en un proceso de dialogo donde se grabaría el texto y su sonido.
A continuación se puede guardar
en la primera columna una serie de imágenes y en la segunda sus nombres,
entonces si se presenta una nueva imagen, el sistema puede compararla con las
que ya tiene, si la encuentra regresa su nombre, sino lo pide y almacena la
imagen y el nombre.
|
Imagen I1 I2 "" In |
Nombre N1 N2 "" Nn |
Programa()
{
i=1
lee Ix
mientras ((Ix != Ii) y (no fin de imágenes))i++
si (no fin de imágenes) escribe Ni
sino //entra al dialogo
escribe "no conozco la imagen dame su nombre"
lee Nx
almacena Ix y Nx
}
Con lo que se tiene un sistema elemental de reconocimiento de imágenes usando el mismo que se utilizo para tratamiento de texto, donde en lugar de manejar cadenas de caracteres, se manejan imágenes, con lo que la programación especifica se puede complicar, porque no es lo mismo manejar registros de unos cuantos caracteres a manejar arreglos de miles de palabras, sin embargo la estructura general se conserva.
Aunque buscar imágenes idénticas se podría considerar como una "trampa", este sistema es un buen ejemplo para empezar con el tratamiento de imágenes, ya que el manejo de cadenas idénticas es común en computación, por ejemplo en un compilador las palabras claves son iguales ha palabras ya almacenadas.
A partir de lo anterior se pueden atacar problemas de mayor complejidad, por ejemplo modificando el sistema para que encuentre la distancia entre la imagen de entrada y la almacenada y en su caso nos indique si son idénticas o su grado de semejanza o diferencia, con lo que se tiene las bases de un sistema de reconocimiento de formas.
El tratamiento de señales en general, se vuelve prácticamente idéntico, ya que en principio, lo que se tiene son archivos donde se guardan las señales y se comparan unas con otras.
Al almacenar la información se ha construido una mina de información sobre la cual se pueden aplicar una gran cantidad de técnicas y métodos de reconocimiento de formas, sistemas evolutivos, lingüística matemática e inferencia gramatical, redes neuronales y otras herramientas para el manejo de información.
4.)GENERALIZACIÓN A CUALQUIER SISTEMA
Al proceso de sustituir Ai por Bi se le conoce como derivación directa y se denota como:
Ai => Bi
Si A = B
o A => B1 => B2 => B3 =>...=> B
entonces se dice que A deriva B y se denota como A =>* B
En general cualquier sistema informático se puede ver como un proceso de derivación, ya que sí se tiene:
El sistema sustituye la entrada por la salida (a la mejor realizando millones de operaciones ), o sea
Entrada => * Salida
Y la secuencia de pasos que llevan de la entrada a la salida se puede visualizar como:
Entrada =>a1=>a2 =>...=> Salida
Donde para cada paso de la forma ai => aj existe una regla de reescritura de la forma ai --> aj , por lo que el algoritmo o programa se puede ver como un sistema de reescritura.
De la misma forma un teorema se puede ver como
A =>* B
Y la demostración del teorema se puede ver como:
A => a1 => a2 =>...=> B
O sea que, desde el punto de vista de los sistemas de reescritura demostrar un teorema y hacer un programa son equivalentes, lo cual es interesante, ya que normalmente se considera que es más fácil programar que demostrar teoremas, por lo que, si se adquiere conciencia de que son procesos equivalentes, se podría facilitar el desarrollo de la capacidad de demostración de teoremas ha partir de la capacidad de programar.
Aun mas esta herramienta se puede aplicar dentro del entorno de los sistemas axiomáticos (gramáticas, autómatas, sistemas de Post, etc. ). Por ejemplo si se tiene el siguiente diagrama de estados.
|
La gramática regular equivalente tiene reglas de reescritura de la forma |
El autómata finito equivalente se representa con las herramientas tradicionales como |
El autómata finito equivalente tiene reglas de reescritura de la forma |
|
A --> 1B A --> 2C B --> 3C B --> 5D C --> 4B |
d(A,1) = B d(A,2) = C d(B,3) = C d(B,5) = D d(C,4) = B |
A1 --> B A2 --> C B3 --> C B5 --> D C4 --> B |
En este ejemplo se ve la fuerza de las reglas de reescritura, ya que, con un cambio notacional se reduce drásticamente la complejidad del manejo de los autómatas.
Por ejemplo, si se quiere demostrar que A245 =>* D -o sea que ha partir de A se llega a D con las señales 2, 4 y 5- con la notación tradicional quedaría:
d(A,245) = d(d(A,24),5)
= d(d(d(A,2),4),5)
= d(d(C,4),5)
= d(B,5)
= D
Que desde el "punto de vista matemático" es poesía, pero desde el punto de vista aplicativo complica la vida (como un numero romano se puede ver más elegante que uno arábigo, pero es menos práctico ).
Usando reglas de reescritura queda:
A245 => C45=> B5=> D
que como se puede ver es mucho más simple. Por lo que sin entrar en mas detalle quiero comentar que, los teoremas de equivalencia entre gramáticas y autómatas se vuelven más simples usando reglas de reescritura en lugar de la notación tradicional.
Las reglas de reescritura tienen un rango de aplicación enorme y están en el núcleo de solución de muchos problemas aparentemente complejos. Lo anterior no es gratis, ya que si se recuerda la jerarquía de Chomsky, las gramáticas generativas tipo cero son las más generales y equivalen a las máquinas de Turing que pueden representar el algoritmo de solución de cualquier problema computable.
Ahora bien ha pesar de su fuerza la máquina de Turing normalmente no se aplica a la solución de problemas reales por la dificultad notacional y operativa que presenta.
Sin embargo las gramáticas tipo 0 tienen reglas de la forma a --> b donde a y b son cadenas de elementos de algún conjunto. O sea que las gramáticas tipo cero están formadas por reglas de reescritura.
Por lo que no es raro que un sistema de
reescritura sea tan fuerte ya que representa a una gramática tipo cero y por
equivalencia a una máquina de Turing.
CONCLUSIÓN
En este trabajo se mostró la fuerza de las reglas de reescritura, como se pueden manejar en forma independiente de las gramáticas y aplicar a áreas tan diferentes como el reconocimiento de imágenes, tratamiento de voz, traducción de lenguajes, sistemas experto, reconocimiento de señales y muchas otras.
Se vio a estas áreas como casos particulares del mismo problema, por lo que se esta perdiendo una cantidad enorme de energía al atacarlos como problemas independientes, ya que, muchas de las herramientas que se han encontrado para atacar un tipo de problema se podrían usar para atacar los otros y en su momento se deben desarrollar herramientas generales a las que les sean indistintas las aplicaciones particulares y aun mas que llegue un momento en el que ya no se vea cada problema en forma particular sino que se ataque el problema general.
Finalmente se vio que las gramáticas tipo cero se representan
mediante reglas de reescritura, de donde se concluyo que se puede construir un sistema
con la fuerza de una máquina de Turing y la facilidad de un programa de unas cuantas líneas.
BIBLIOGRAFÍA
1.- Estructuras Sintácticas. Noam Chomsky. Ed. Siglo XXI
2.- Teoría Sintáctica. Emmon Bach. Ed. Anagrama.
3.- Formal Languages. Salomaa.
Ed. Academic Press.
4.- Sistemas Evolutivos. Fernando Galindo Soria.
Boletín de Política Informática. México, Septiembre de 1986.
5.- Sistemas Evolutivos: Nuevo Paradigma de
la Informática. Fernando Galindo Soria.
Memorias XVII Conf. Latinoamericana de Informática. Caracas Ven., julio
de 1991.
6.-
Sintactic Pattern Recognition. Rafael C. Gonzalez y Michael C. Thomason.
Ed. Addison-Wesley.