IPN

UPIICSA

 Lic. En C. Sección de

  de la  Posgrado e

Informática Investigación.

ALGUNAS PROPIEDADES MATEMATICAS

DE LOS SISTEMAS LINGUISTICOS

Fernando Galindo Soria

  Septiembre de 1992.

ALGUNAS PROPIEDADES MATEMATICAS DE

LOS SISTEMAS LINGUISTICOS

Fernando Galindo Soria

Septiembre de 1992

UPIICSA-IPN

Calle de Te # 950

Col. Granjas México

México, D.f.

08400 México

Tel 6-49-03-66 ext 301

I) DESARROLLO HISTORICO.

I.1 De la Lingüística matemática a los Sistemas Dirigidos      por Sintáxis.

A pesar de que el área de la Lingüistica Matemática es relativamente joven, ya que, empezó a consolidarse a mediados de los 50's, su campo de aplicación en la Informática ha ido creciendo rápidamente.

Uno de sus primeros logros se presentó cuando se usó para decribir la gramática del Lenguaje Algol durante los años 60's propiciando que ya para finales de esa décadas empezaran a surgir libros donde se mostraba como construir un compilador a partir de la gramática de un lenguaje dado, y que durante los 70's se volviera cotidiana la construcción de compiladores e intérpretes bajo este enfoque.

Lo anterior ocasionó que en prácticamente todos los cursos de compiladores y de Programación de Sistemas se enseñaran una gran cantidad de métodos para analizar tanto léxica como sintácticamente las oraciones de algún lenguaje de programación

En particular en el caso del Análisis Sintáctico se desarrolló una gran variedad de métodos que permiten detectar si una oración es sintácticamente correcta, verificando si cumple o no con las reglas gramaticales del Lenguaje de Programación.

Conforme fue madurando el área, se detectó que existían muchos problemas en los cuales el usuario se comunicaba mediante algún lenguaje con la computadora, desde los problemas más complejos de reconocimiento de lenguaje natural hasta la comunicación en algún lenguaje de control con el Sistema Operativo o algún lenguaje de Descripción de Datos con un Manejador de Base de Datos

En particular se detectó que algunos de estos problemas se volvían un caso específico de la construcción de intérpretes, ya que es relativamente fácil, usando las técnicas de compiladores que se reconozca por ejemplo las instrucciones de un lenguaje de control, y se ejecuten. A todo este universo de problemas se les agrupó con el nombre genérico de Sistemas Dirigidos por Sintaxis, y es así que en la actualidad es común encontrar por ejemplo editores dirigidos por sintáxis.

I.2) Inferencia Gramatical y Programación Dirigida por      Sintáxis.

Ya para mediados de los 70's era común tratar de construir interpretes de múltiples tipos de lenguajes, sin embargo, casi desde el principio se encontró un problema que luego se volvió cotidiano, ya que, según la técnica desarrollada en la contrucción de compiladores, para poder construir el compilador o intérprete de un lenguaje dado, se requiere contar con su gramatica y en ningún libro de Compiladores decía como encontrar la gramática de un lenguaje.

En el caso específico de los lenguajes de programación y algunos otros, la gramática la daba el diseñador del lenguaje y reflejaba las características y restricciones que se querían imponer al sistema, sin embargo, en muchos otros casos no se contaba con la gramática, sino con múltiples ejemplos de oraciones del lenguaje y con criterios y reglas empíricas, por lo que encontrar la gramática de un lenguaje dado a partir de un conjunto de oraciones se volvió un gran reto.

En paralelo con lo anterior y también desde mediados de los 60's se empezó a aplicar la Lingüística Matemática al Reconocimiento de Patrones y en particular al Reconocimiento de Imágenes y ya desde esa época se empezo a desarrollar el Reconocimiento Sintáctico de Patrones, en el cual se aplica la Lingüistica Matemática para reconocer imagenes o patrones específicos viéndolos como 'oraciones' de algún 'Lenguaje de Patrones o Imágenes'.

Ahora bien, en el caso del Reconocimiento de Patrones es común contar con un gran número de oraciones que representar imágenes o patrones particulares, si embargo, por lo común no se cuenta con la gramática del lenguaje, por lo que, desde mediados de los 60's se comenzaron a desarrollar un conjunto de métodos y técnicas orientados a la obtención de la gramática de un lenguaje a partir de ejemplos de oraciones de este lenguaje. A todo este conjunto de herramientas se les englobó con el nombre genérico de Inferencia Gramatical.

A principios de los 80's se empezaron a combinar la Inferencia Gramatical y la construcción de Compiladores con el fin de resolver problemas de tratamiento de diferentes tipos de lenguajes y gracias a esa interrelación ya se contaba con un conjunto de herramientas con las cuales:

a) a partir de un conjunto de ejemplos de un lenguaje se puede encontrar la gramática que describe el lenguaje.

b) a partir de la gramática se puede construir un compilador o intérprete capaz de reconocer las oraciones del lenguaje.

Ya para 1983 se tenían integradas estas herramientas en un método conocido como Programación Dirigida por Sintaxis, en el cual, se muestra un proceso para desarrollar sistemas a partir de ejemplos del lenguaje con el que se quieren dar órdenes al sistema.

I.3) Enfoque Lingüístico de la Informática.

En un principio estas herramientas se aplicaban para encontrar la gramática y construir el compilador de lenguajes muy concretos, tipo PASCAL, FORTRAN, lenguajes de consultas y por otro lado se siguieron aplicando al Reconocimiento de Patrones.

Sin embargo, conforme avanzó el área se detectó que existían muchos otros problemas donde se podía aplicar este método, únicamente con la condición de que los problemas a atacar fueran susceptibles de representarse mediante oraciones de algún lenguaje.

Pero por otro lado, el mismo concepto de lenguaje se fue ampliando, ya que, si en un principio se utilizaron estas herramientas para manejar lenguajes como FORTRAN y PASCAL, al mismo tiempo se utilizaban para representar imágenes y patrones en general.

Actualmente el campo de aplicación de estas herramientas ha crecido enormemente y se postula que cualquier problema susceptible de ser atacado por medios automatizados es susceptible de representarse mediante oraciones de algún Lenguaje, llegándose a plantear así el Enfoque Lingüístico de la Informática, en el cual se considera que cualquier 'objeto' se puede ver como una oración de algún lenguaje X.

Ahora bien, si se tuviera que tener la lista de todas las oraciones de un lenguaje no terminaríamos, por lo que, comúnmente en lugar de la lista se utiliza una Gramática o conjunto de reglas que representan la estructura del lenguaje.

Por lo que, el principal problema cuando se tiene que manejar objetos de los cuales no se tiene la gramática es precisamente encontrar ésta.

I.4) Operaciones Lingüísticas,

En la actualidad ya existen una gran cantidad de herramientas de Inferencia Gramatical orientadas a encontrar la gramática de múltiples tipos de lenguaje (visuales, auditivos, de trayectorias, etc.).

Sin embargo, los primeros métodos presentados, tendían a ser complejos, particulares y difíciles de programar, por lo que, se empezaron a desarrollar nuevos métodos, para diferentes tipos de problemas.

A través de esta búsqueda de métodos y herramientas, ya para principios de los 80's se empezó a detectar que muchos métodos eran parecidos y solo eran un caso particular de métodos más generales.

En la actualidad se ha llegado a que existe un grupo de operaciones lingüísticas que al combinarse entre sí cubren la gran mayoría de los problemas de Inferencia Gramatical y por otro lado se ha detectado que estas operaciones son similares a ciertos procesos algebráicos y analíticos.

En particular se cuenta con una gran cantidad de herramientas basadas en las operaciones linguísticas de:

.Factorización

.Conmutatividad

.Distribución

.Recursividad

La Factorización y Distribución Linguísticas son equivalentes a las algebráicas con la diferencia de que en este caso se factorizan o distribuyen componentes de una oración.

La Recursividad es, tal vez, la herramienta linguística más poderosa ya que permite encontrar reglas generales o patrones a partir de casos particulares.

Estas herramientas de la Inferencia Gramatical se utilizan cotidianamente desde hace varios años, tanto para desarrollo de sistemas en forma manual mediante la Programación Dirigida por Sintáxis, como en la construcción de Sistemas Evolutivos.

Es precisamente durante el desarrollo de estas aplicaciones que se ha detectado un conjunto de propiedades de tipo matemático, presentes en la Factorización, Distribución y Recursividad Linguística.

2) FACTORIZACION LINGUISTICA.

2.1) Introducción.

Las herramientas de la Inferencia Gramatical trabajan con la estructura de las oraciones buscando encontrar una estructura general (o regla sintáctica) a partir de estructuras particulares (u oración canónica).

Así, si por ejemplo, se tienen las siguientes oraciones:

Juan es hermano de Pedro y

Juan estudia en UPIICSA

se puede detectar que en las dos oraciones se encuentra presente la palabra Juan y que un párrafo equivalente sería:

Juan es hermano de Pedro y estudia en UPIICSA.

Si se observa lo que se ha hecho es detectar que la palabra Juan era común a las dos oraciones por lo que se factorizó (o sea que se sacó como factor común) y se obtuvo un párrafo donde sólo aparece una sóla vez.

Para que se pueda visualizar el proceso sustituiremos fragmentos de la oración por etiquetas de acuerdo a la siguiente tabla:

Fragmento Etiqueta

Juan o1

es hermano de r1

Pedro o2

  y  +

estudia en r2

 UPIICSA o3

Con lo que el párrafo Juan es hermano de Pedro y

Juan estudia en UPIICSA

quedarían como:

o1 r1 o2 +

o1 r2 o3

Donde se observa que o1 es común a las 2 oraciones.

A las oraciones

o1 r1 o1 y

o1 r2 o3

se les conoce como oraciones canónicas y en general cuando se sustituyen los elementos de una oración por una representación que permita visualizar la estructura de la oración se obtiene una oración canónica.

Recordemos que la factorización algebráica consiste en encontrar los factores comunes en una expresión algebráica y sacarlos de la expresión, como se ve a continuación:

. ab + ac = a(b+c)

.3x + 3y = 3(x + y)

.a(b * c) + a(e/f) = a(b*c+e/f)

Aplicando lo anterior a las oraciones canónicas entonces tenemos que:

o1r1o2+o1r2o3 = o1(r1o2+r2o3)

o sea que el párrafo

o1r1o2 + o1r2o3

es equivalente al párrafo

o1(r1o2+r2o3)

si sustituimos las etiquetas por los fragmentos que representan tenemos entonces que:

Juan es hermano de Pedro y estudia en UPIICSA

 o1 r1 o2 + r2 o3

2.2) Generación de Gramáticas.

La factorización Lingüística es una herramienta muy poderosa ya que permite encontrar los factores comunes dentro de un conjunto de oraciones, por lo que, si por ejemplo tengo un conjunto de ejemplos de algún lenguaje, aplicando la factorización se pueden encontrar algunos de los factores comunes o reglas generales del lenguaje.

Lo anterior se puede aplicar para encontrar entonces una Gramática de un lenguaje a partir de ejemplos de las oraciones del lenguaje, ya que si por ejemplo, se tienen las siguientes oraciones canónicas (que se obtuvieron sustituyendo los elementos de las oraciones del lenguaje por etiquetas)

a b c d e

a b m e x y z

a b m g

lo primero que se hace es que como esas oraciones canónicas representan la estructura de las oraciones del lenguaje, entonces las integramos para formar una primera gramática del lenguaje

S --> a b c d e |

a b m e x y z |

a b m g

conocida como Gramática Canónica donde 'S -->' se puede ver como el nombre de una rutina y el símbolo '|' como un separador entre los diferentes casos de un programa.

Por lo que, la Gramática Canónica se puede leer como:

La Rutina S genera tres posibles tipos de oraciones:

Oraciones del tipo abcde

  del tipo abmexyz

y del tipo abmg

Lo cual es congruente con el hecho de que cada uno de los tipos anteriores corresponde a cada una de las oraciones canónicas que se dieron como ejemplo, por lo que podemos afirmar que la Gramática Canónica genera al menos las oraciones que se tenían como ejemplo originalmente.

Como siguiente paso se toman las oraciones de la gramática canónica y se les aplica la factorización lingüística, para lo que se considera al símbolo '|' equivalente al '+' del Algebra tradicional

S --> abcde |

   abmexyz|

abmg

    factorizando ab queda:

S --> ab( cde |

mexyz |

mg )

    Factorizando m queda:

s --> ab( cde |

m( exyz|

g ) )

Dado que no es común el uso de paréntesis dentro de una Gramática se introducen una serie de variables auxiliares (conocidas como Variables no Terminales) en lugar de los parténtesis, quedando

      Introduciendo la variable no terminal X

S --> abX

X --> cde|

m( exyz|

g )

Introduciendo la variable no terminal Y

S --> abX

X --> cde|

mY

Y --> exyz|

g

Que se lee:

El programa S genera ab y llama a la rutina X

La rutina X genera las cadenas

cde o

my

La rutina Y genera las cadenas

exyz o

g

si analizamos este programa podemos ver que:

abcde

S ==> abX ==> abmY==> abmexyz

abmg

Donde '==>' significa 'se sustituye por' de donde S se sustituye por abX y así sucesivamente de donde llegamos que al final

S genera abcde

abmexyz

abmg

que es la lista de oraciones originales

De donde se tiene que la gramática canónica

S --> abcde

abmexyz

abmg

y la gramática

S --> abX

X --> cde|

mY

Y --> exyz|

g

obtenida a partir de la primera mediante la Factorización Lingüística generan las mismas oraciones.

Sin embargo, estructuralmente estas dos gramáticas no son iguales ya que en el primer caso se tiene sólo un nivel y en el segundo la gramática incluye tres niveles.

Cuando dos gramáticas general el mismo lenguaje pero con diferente estructura se dice que son débilmente equivalentes

2.3) De la Gramática al Programa.

Ahora bien si analizamos un poco a fondo las dos gramáticas y las vemos como dos programas podemos observar que la gramática canónica se comporta como un programa con tres opciones en la primera opción el programa ejecuta las instrucciones:

abc ...

en la segunda opción ejecuta

abme ...

y en la tercera

abmg

Por lo que existe una repetición de instrucciones comunes y lo más lógico es que el programa ejecute al principio

ab

y después las opciones

c...

me...

mg...

que si observamos es precisamente la idea de la segunda gramática.

Por lo que la primera gramática se comporta como el programa:

Program S

1) a b c d e

2) a b m e x y z

3) a b m g

fin programa

y la segunda gramática se comporta como:

Program S

ab

1)cde

2)m

1)exyz

2)g

fin programa

O sea que las instrucciones repetitivas sólo se ejecutan una sóla vez.

2.4) Aplicaciones.

Una de las aplicaciones de la factorización lingüística se encuentra precisamente en la depuración de programas con el fin de quitar código redundante.

Sin embargo no es la única ya que una gran cantidad de métodos de inferencia gramatical se reducen a la aplicación de la factorización.

Una aplicación que se desarrolló en 1988 en colaboración con Javier Ortiz (en esa época Coordinador de la Maestría en Computación del CENIDET en Cuernavaca, Mor.) consistió en la aplicación de la factorización a la construcción de un Sistema Evolutivo generador de Sistemas Expertos, en el cual, la idea consistió básicamente en tomar una gran cantidad de oraciones en las cuales un experto explica como resuelve un problema y transformar cada oración en una oración canónica incluyendo por ejemplo síntomas (s), diagnósticos (d) y tratamientos (t) e ignorando todo lo demás.

A partir de ahi integrar todas las oraciones canónicas en una Gramática Canónica, mediante factorización agrupar los síntomas comunes y proponerlos como reglas generales hasta construir una cascada de reglas de las más generales a las más específicas que caracterizan un problema o diagnóstico particular.

Por ejemplo si se tiene la oración:

Paciente femenino de 15 años con 38 grados de temperatura y

S1 S2 S3

dolor en el pecho, se le diagnosticó faringitis y se le

      S4                                d1

recetó antibióticos, antistamínicos y reposo

t1              t2           t3

la oración canónica equivalente sería:

S1S2S3S4d1dt1t2t3

Por otro lado si en lugar de tener una sola oración se tiene la información de todos los pacientes del hospital entonces se pueden obtener cientos o miles de reglas canónicas, las cuales mediante factorización pueden proporcionar las reglas generales de un problema y su tratamiento.

Por ejemplo si se tienen las reglas.

S --- S1S2S3S4d1t1t2t3

S1S2S5d2t1t4

S1S4S6S7d3t5

Factorizando S1

S --> S1X

X --> S2S3S4D1T1T2T3

S2S5D2T1T4

S4S6S7D3T5

Factorizando S2

S --> S1X

X --> S2Y

S4S6S7D3T5

Y --> S3S4D1T1T2T3

S5D2T1T4

Analizando la última gramática se observa que S1 es la característica general de los pacientes y después se tiene a los pacientes con S2 o con S4.

Obtener un sistema experto a partir de las reglas es directo.

3) CONMUTATIVIDAD LINGUISTICA.

En el anterior ejemplo los síntomas, tratamientos y diagnósticos no necesariamente están ordenados o aparecen en el mismo orden en todas las oraciones, por lo que, ya que se encontraron las oraciones canónicas el siguiente paso consiste en ordenar los elementos de la oración, Por ejemplo, si se tiene:

S5S1d2t1S2t4

al ordenarla queda:

S1S2S5d2t1t4

Lo anterior no necesariamente es aplicable a cualquier oración ya que es mucho más común que se trabaje con oraciones en las cuales no se permite la conmutatividad con lo que tenemos dos tipos de oraciones

Las oraciones conmutables como en el caso de los sistemas