UNIVERSIDAD POLITÉCNICA DE VALENCIADEPARTAMENTO DE SISTEMAS INFORMÁTICOS Y COMPUTACIÓN

Estimación de gramáticas incontextuales probabilísticasy su aplicación en modelización del lenguaje

Tesis Doctoralpresentada por Joan Andreu Sánchez Peiró

dirigida por el Doctor José Miguel Benedí Ruiz

Estimación de gramáticas incontextuales probabilísticasy su aplicación en modelización del lenguaje

Joan Andreu Sánchez Peiró

Trabajo realizado bajo la dirección del DoctorD. José Miguel Benedí Ruiz

y presentado en la Universidad Politécnica de Valenciapara optar al grado de Doctor en Informática

Valencia, 1999

Este trabajo ha sido desarrollado, principalmente, en el marco de los proyectos TIC95/0884-C04 y

TIC97-0745-C01, subvencionados por la Comisión Interministerial de Ciencia y Tecnología.

IV

Resumen

En esta tesis se estudian las Gramáticas Incontextuales Probabilísticas y su aplica-ción en problemas de Modelización del Lenguaje. Dos son los grandes problemasque se va a considerar en este tipo de modelos: el aprendizaje de las funciones deprobabilidad asociadas a las reglas, y su integración como modelo de interpretaciónen tareas complejas de Modelización del Lenguaje.

En primer lugar, se plantea el interés de aplicar las Gramáticas IncontextualesProbabilísticas en problemas complejos de Reconocimiento Sintáctico de Formas,y se concretan los problemas que se van a estudiar en esta tesis.

A continuación se presentan algunas definiciones sobre lenguajes y gramáticasprobabilísticas en el marco de la Teoría de Lenguajes Formales, poniendo énfasisen las principales ventajas y restricciones de las Gramáticas Incontextuales Proba-bilísticas para los problemas que se pretende abordar.

El primero de los problemas que se estudia es la estimación de las funcionesde probabilidad asociadas a las reglas. Se presentan dos de los algoritmos clásicosde estimación de las GIP, el algoritmo Inside-Outside y el algoritmo basado en lascuentas de Viterbi, y se estudian las relaciones entre las funciones que optimizanambos algoritmos. A continuación, se demuestran propiedades fundamentales delos modelos obtenidos por ambos algoritmos que ponen de manifiesto la validez delos algoritmos de estimación y de los propios modelos.

Después se proponen nuevos algoritmos de estimación en los cuales se utilizaun subconjunto específico de derivaciones de cada cadena. Este subconjunto dederivaciones puede formarse a partir de las k mejores derivaciones de cada cadena,o bien, a partir de información estructural definida sobre la muestra. Se estudianlas características de los métodos de estimación así como las propiedades de losmodelos obtenidos. Finalmente, los algoritmos propuestos se aplican al conjuntode datos del Penn Treebank para ilustrar su comportamiento en la práctica.

Por último se aborda el problema de la interpretación e integración de las Gra-máticas Incontextuales Probabilísticas en problemas de Modelización del Lengua-je. Se propone un nuevo algoritmo para computar la probabilidad de la mejor de-rivación que genera una subcadena inicial. A continuación se hace una propuestade integración que combina modelos de n-gramas a nivel de palabras con una Gra-mática Incontextual Probabilística a nivel de categorías léxicas. La propuesta esestudiada de nuevo sobre el conjunto de datos delPenn Treebank.

VI

Índice general

1. Introducción 11.1. Estimación de las probabilidades de una GIP . . . . . . . . . . . . 31.2. Las GIP como modelo de interpretación en ML . . . . . . . . . . 51.3. Organización general de esta tesis . . . . . . . . . . . . . . . . . 6

2. Revisión de conceptos de lenguajes y gramáticas formales 92.1. Lenguajes y gramáticas formales . . . . . . . . . . . . . . . . . . 92.2. Análisis sintáctico de una cadena . . . . . . . . . . . . . . . . . . 132.3. Lenguajes y gramáticas formales probabilísticos . . . . . . . . . . 142.4. Análisis sintáctico probabilístico de una cadena . . . . . . . . . . 19

3. Estimación de las GIP 233.1. Estimación probabilística de las GIP . . . . . . . . . . . . . . . . 233.2. Los algoritmos IO y VS . . . . . . . . . . . . . . . . . . . . . . . 26

3.2.1. El algoritmo IO . . . . . . . . . . . . . . . . . . . . . . . 263.2.2. El algoritmo VS . . . . . . . . . . . . . . . . . . . . . . 293.2.3. Estudio empírico del comportamiento de los algoritmos IO

y VS . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303.3. Relación entre las funciones maximizadas por los algoritmos IO y

VS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343.4. Propiedades de las GIP estimadas con los algoritmos IO y VS: con-

sistencia de los modelos . . . . . . . . . . . . . . . . . . . . . . . 403.5. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

4. Estimación de las GIP a partir de un conjunto de derivaciones 494.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494.2. Estimación de las GIP a partir de un subconjunto de derivaciones . 51

4.2.1. Propiedades de las GIP estimadas a partir de un subcon-junto de derivaciones: consistencia de los modelos . . . . 51

4.3. El algoritmo kVS . . . . . . . . . . . . . . . . . . . . . . . . . . 534.3.1. Costes del algoritmo kVS . . . . . . . . . . . . . . . . . 544.3.2. Relación entre los modelos estimados en función de k . . 554.3.3. Estudio empírico del comportamiento del algoritmo kVS . 56

VII

VIII

4.4. Relación entre las funciones maximizadas por los algoritmos IO,VS y kVS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

4.5. Estimación de las GIP a partir de información estructural . . . . . 654.5.1. Estudio empírico del comportamiento de los algoritmos

IOp y VSp . . . . . . . . . . . . . . . . . . . . . . . . . 684.6. Experimentos con el corpus Penn Treebank . . . . . . . . . . . . 70

4.6.1. Experimentos realizados con el algoritmo kVS . . . . . . 724.6.2. Experimentos realizados con los algoritmos IOp y VSp . . 74

4.7. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

5. Aplicación de las GIP en ML 795.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 795.2. Análisis sintáctico probabilístico del prefijo de una cadena . . . . 81

5.2.1. Probabilidad de una subcadena inicial: el algoritmo LRI . 825.2.2. Probabilidad de la mejor derivación que genera una subca-

dena inicial: el algoritmo VLRI . . . . . . . . . . . . . . 835.3. Combinación de n-gramas y GIP para ML . . . . . . . . . . . . . 86

5.3.1. Experimentos realizados sobre el Penn Treebank . . . . . 885.4. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

6. Conclusiones y trabajos futuros 93

Bibliografía 97

Apéndices 104

A. Experimentos complementarios con los algoritmos IO y VS 105A.1. Experimentos con la semilla 1 . . . . . . . . . . . . . . . . . . . 105A.2. Experimentos con la semilla 2 . . . . . . . . . . . . . . . . . . . 113

B. Demostraciones de teoremas y corolarios 119B.1. Demostración del Teorema 3.4.2 . . . . . . . . . . . . . . . . . . 119B.2. Demostración del Corolario 3.4.2 . . . . . . . . . . . . . . . . . . 122B.3. Demostración del Teorema 4.2.1 . . . . . . . . . . . . . . . . . . 123B.4. Demostración del Corolario 4.2.1 . . . . . . . . . . . . . . . . . . 126B.5. Cálculo de la matriz T . . . . . . . . . . . . . . . . . . . . . . . 128

C. Resultados complementarios de los experimentos con el corpus PennTreebank 129C.1. Resultados con la semilla 1 . . . . . . . . . . . . . . . . . . . . . 129C.2. Resultados con la semilla 2 . . . . . . . . . . . . . . . . . . . . . 135

Capítulo 1

Introducción

En esta tesis se estudian las Gramáticas Incontextuales Probabilísticas y su apli-cación en tareas complejas de Modelización del Lenguaje. El Reconocimiento Sin-táctico de Formas (RSF) constituye una marco formal en el que se pueden abordarproblemas complejos de Reconocimiento Automático del Habla (RAH) [RJ93], deLenguaje Natural [Che96], de Traducción Automática [BPPM93], de Análisis deSecuencias Biológicas [SJK83, DEKM98], y de Modelización del Lenguaje (ML)[BJM83], entre otros. En este marco es necesario definir algún mecanismo capaz derepresentar adecuadamente los objetos del problema. Las gramáticas formales sonuna herramienta potente de especificación para representar de manera eficiente res-tricciones sintácticas entre las primitivas que constituyen los objetos [GT78, Fu82].Las Gramáticas Incontextuales (GI) constituyen un tipo importante de modelos yaque permiten representar dependencias a largo término entre estas primitivas. Elproblema de ML se aborda habitualmente mediante modelos basados en n-gramas.Estos modelos consideran una cantidad de información limitada por n, por lo querepresentan, básicamente, relaciones locales entre las palabras del lenguaje. LasGI, por su parte, son capaces de representar de una forma compacta las relacionessintácticas que a largo plazo se establecen entre las palabras del lenguaje. En losúltimos años se ha propuesto el uso de las GI para tratar este problema [JL91]. Enesta tesis se van a estudiar los problemas que se presentan al aplicar las GI en tareascomplejas de ML.

Una Gramática Incontextual Probabilística1 (GIP) es una extensión natural deuna GI que se compone básicamente de dos partes: un conjunto de reglas (gramáti-ca característica) que conforman la parte estructural de la misma y unas funcionesde distribución de probabilidad (o simplemente probabilidades) asociadas a las re-glas que constituyen su parte estocástica. Dos son los grandes problemas que se vaa considerar en las GIP: de un lado, su aprendizaje, esto es, la obtención de unaGIP que represente un lenguaje; y de otro lado, su integración como modelo de

1El término probabilístico no existe en castellano, aunque actualmente es aceptado como sinó-nimo de estocástico. A lo largo de esta tesis utilizaremos el término probabilístico como términoequivalente de estocástico.

1

2

interpretación en tareas complejas de ML.Para abordar el problema del aprendizaje existen, en general, dos aproximacio-

nes: la deductiva y la inductiva. En la aproximación deductiva la información paraconstruir la GIP se obtiene a partir del conocimiento que posee un experto humanosobre el lenguaje a representar. En la aproximación inductiva la GIP se construyeautomáticamente a partir de un conjunto de ejemplos (muestra de aprendizaje). Elconjunto de ejemplos puede pertenecer al lenguaje que se pretende representar opuede estar compuesto por ejemplos convenientemente etiquetados pertenecientes,o no, al lenguaje [FB75]. El aprendizaje de modelos mediante la aproximación de-ductiva es una labor tediosa y compleja, siendo inabordable en tareas reales dondese da una gran variabilidad. La aproximación inductiva, por el contrario, puedeser apropiada si se dispone de algoritmos robustos y eficientes, y de muestras querecojan la variabilidad. Precisamente, una restricción de esta aproximación es lanecesidad de disponer de grandes volúmenes de datos. Los buenos resultados al-canzados por algunas técnicas basadas en el aprendizaje inductivo en Reconoci-miento Automático del Habla [HAJ90], en Traducción Automática [BPPM93] yen modelización de secuencias de ARN [Sak90, DEKM98], entre otros, han con-firmado la validez de esta aproximación. En esta tesis seguiremos la aproximacióninductiva para abordar el problema del aprendizaje de las GIP.

EL proceso de aprendizaje de las GIP puede descomponerse en el aprendizajede la gramática característica y/o el aprendizaje de las probabilidades asociadasa las reglas [Vid94]. Con el aprendizaje de la gramática característica se preten-de recoger la información estructural presente en la muestra, mientras que con elaprendizaje de las probabilidades se pretende recoger básicamente la informaciónestocástica.

En referencia al aprendizaje de la gramática característica, se han propuestodiversas técnicas de Inferencia Gramatical [FB75, Sak90] que hacen uso funda-mentalmente de información estructural representada en la muestra. Existen otrastécnicas que combinan el aprendizaje de la gramática característica con el apren-dizaje de las probabilidades de las reglas y que hacen uso tanto de la informa-ción estructural como de la estocástica para el proceso de aprendizaje: unas in-corporan conceptos propios de la Teoría de la Información y de la Codificación[CRA76, Che96], y otras lo hacen de la inferencia estadística [Mar74, Sto94].

En cuanto al aprendizaje de las probabilidades de una GIP, en primer lugar cabedefinir alguna función criterio a optimizar dependiente de la muestra. Esta muestrapuede estar formada por ejemplos pertenecientes al lenguaje, o por cadenas per-tenecientes y no pertenecientes al lenguaje. Una vez definida la función objetivo,se elige un marco en el que optimizarla. Una posibilidad es definir alguna técnicade descenso por gradiente [HAJ90]. En esta tesis se va a estudiar el problema delaprendizaje de la probabilidades de una GIP a partir de la definición de una fun-ción dependiente de una muestra, compuesta por cadenas del lenguaje que se desearepresentar.

La aplicación de las GIP en tareas complejas de RSF para procesos de inter-pretación es un aspecto fundamental que ha cobrado interés en los últimos años

3

[Ney92, JLM92]. En ML, se han propuesto las GIP para calcular la probabilidadde la siguiente palabra a partir de una secuencia de palabras vistas con anteriori-dad [JL91, Dup93, JWS+95, Sto95]. Estas propuestas presentan severas restric-ciones como consecuencia del coste temporal, tanto en el proceso de aprendizajecomo en el proceso de análisis. Los resultados alcanzados son competitivos conlos resultados alcanzados con modelos clásicos de n-gramas para tareas sencillas.Sin embargo, en tareas complejas resulta inviable el uso de este tipo de mode-los. Recientemente se han propuesto técnicas que tratan de integrar modelos den-gramas a nivel de palabras con modelos sintácticos a nivel de categorías gra-maticales [CJ98, Bel98]. Esto facilita el aprendizaje de los modelos sintácticos ypermite reducir el coste del proceso de análisis. Estas aplicaciones han propiciadoun creciente interés por definir métodos eficaces y robustos de análisis mediantelas GIP, y por definir métodos eficientes de integración. En esta tesis se van a estu-diar problemas de interpretación utilizando las GIP, y problemas de integración demodelos híbridos de n-gramas y GIP.

1.1. Estimación de las probabilidades de una GIP

El problema de la Estimación Probabilística de una GIP consiste en aprenderlas probabilidades de sus reglas a partir de una muestra. Para abordar este pro-blema se define alguna función criterio dependiente de la muestra, y un marcopara optimizarla. Como se ha mencionado anteriormente, la muestra puede estarcompuesta únicamente por cadenas perteneciente al lenguaje, o bien por cade-nas pertenecientes y no pertenecientes al lenguaje. En la primera aproximación,las funciones a optimizar que habitualmente se definen son la verosimilitud de lamuestra [Bak79, LY90, Ney92, Cas96], la verosimilitud de la mejor derivación dela muestra [Ney92, Cas96], o la verosimilitud de un conjunto específico de de-rivaciones de la muestra [PS92, SB98a]. En la segunda aproximación cabe citarel Aprendizaje Correctivo en el que la función a optimizar es la tasa de error so-bre un conjunto de prueba, y que fue desarrollado para modelos ocultos de Mar-kov [BBdSM93] y extendido para las GIP en [BS95], o el aprendizaje para opti-mizar la Información Mutua [GKNN91], también desarrollado básicamente paramodelos regulares. Esta segunda aproximación presenta el inconveniente de queen ocasiones resulta difícil disponer de muestras que no pertenecen al lenguaje.En esta tesis vamos a centrarnos en la estimación de las GIP utilizando cadenaspertenecientes al lenguaje.

La verosimilitud de una muestra puede ser maximizada mediante el algoritmoInside-Outside (IO) [Bak79, LY90, Ney92, Cas96], mientras que la verosimilitudde la mejor derivación de la muestra puede ser maximizada mediante el algoritmobasado en las cuentas de Viterbi (VS) [Ney92, Cas96]. Cada uno de ellos procedeiterativamente incrementando el valor de la función hasta alcanzar un óptimo local.Ambos algoritmos son un caso particular del algoritmo EM [Moo96] y su conver-gencia puede ser convenientemente descrita en el marco de las Transformaciones

4

Crecientes [Bau72]. El algoritmo IO considera para el proceso de estimación todaslas posibles derivaciones de cada cadena de la muestra. Por su parte, el algoritmoVS considera únicamente una derivación de cada cadena. Ambos algoritmos tienenel mismo coste temporal asintótico en cada iteración, pero el algoritmo IO necesitaun elevado número de iteraciones para converger, por lo que es el algoritmo VS elque se utiliza en la mayoría de las aplicaciones prácticas. Sin embargo, los modelosobtenidos por el algoritmo IO ofrecen, en general, mejores resultados que los obte-nidos con el algoritmo VS. Las anteriores consideraciones introducen la necesidadde estudiar la relación entre ambos algoritmos y las funciones que estos optimizan.

Dado que en tareas reales complejas resulta inviable aplicar el algoritmo IOpara el proceso de estimación, una alternativa que se explora en esta tesis consisteen utilizar un número de derivaciones intermedio entre los algoritmos IO y VS. Deesta forma se pretende evitar los inconvenientes de ambos y aprovechar las ven-tajas de los dos algoritmos. Este subconjunto de derivaciones puede definirse concriterios básicamente estructurales o con criterios fundamentalmente estocásticos.

En esta línea, en [PS92] se propuso un algoritmo de estimación basado en elalgoritmo IO que sólo consideraba para el aprendizaje aquellas derivaciones de ca-da cadena que eran compatibles con una parentización2 definida sobre la muestra.Una restricción de esta propuesta es la necesidad de disponer de grandes volúmenesde datos parentizados. Los experimentos reportados en [PS92] mostraban como elalgoritmo tardaba menos iteraciones en converger que el algoritmo IO y como labondad de los modelos era satisfactoria. En esta tesis se explora esta aproxima-ción, y basándonos en esta idea, se propone otra alternativa para la estimación delas probabilidades, utilizando la mejor derivación de la muestra compatible con laparentización definida sobre la misma.

Otra posibilidad para definir el subconjunto de derivaciones, que estudiaremosen esta tesis, consiste en seleccionar las k mejores derivaciones de cada cadena, demanera análoga a como procede el algoritmo VS. Puesto que se utiliza más infor-mación que en el algoritmo VS, es de esperar que las gramáticas obtenidas esténmejor estimadas. Esta propuesta tiene la ventaja de que no es necesario incorporarinformación deductiva en la muestra, lo que facilita su aplicación en tareas reales.Uno de los inconvenientes es el coste temporal de obtener las k mejores derivacio-nes de cada cadena [Mar94].

Los métodos de estimación mencionados proporcionan un modelo que reco-ge información estocástica contenida en la muestra. Un aspecto fundamental decualquier algoritmo de estimación consiste en garantizar que los modelos obte-nidos son capaces de representar correctamente esta información. La consisten-cia [BT73] es una propiedad importante que debe cumplir cualquier modelo pararepresentar adecuadamente la información estocástica contenida en la muestra. En

2Los términos parentizado/a y parentización no existen en castellano. Sin embargo, por como-didad y abusando del lenguaje llamaremos cadena parentizada a una cadena en la que algunas desus partes han sido marcadas con paréntesis de acuerdo con algún criterio (principalmente sintácti-co y/o semántico). Así mismo, llamaremos parentización al conjunto de paréntesis de una cadenaparentizada.

5

[Mar74, CPG83] se demostró que dada una GIP no ambigua cuyas probabilidadeshan sido obtenidas con el algoritmo VS a partir de una muestra dada, da lugar auna GIP consistente. En esta tesis demostramos este resultado para una GIP sinrestricciones, cuando las probabilidades se calculan definiendo una Transforma-ción Creciente. El cumplimiento de esta importante propiedad permite derivar unaserie de interesantes propiedades estocásticas que relacionan la muestra con el len-guaje generado por la gramática.

1.2. Las GIP como modelo de interpretación en ML

Un problema fundamental en ML es determinar la probabilidad de una palabraa partir de la historia anterior, y puede plantearse como la evaluación de la siguienteexpresión [BJM83, Jel98]:

Pr(wk+1 | w1w2 . . . wk).

Una posibilidad para abordar este problema consiste en utilizar los modelos de n-gramas [BJM83]. Se basan en el supuesto de que la probabilidad de una palabraestá condicionada por las n − 1 palabras anteriores. Las ventajas de este tipo demodelos es que la estimación de los parámetros es sencilla y robusta, y la integra-ción en los sistemas de reconocimiento puede realizarse de forma eficiente. Losexcelentes resultados proporcionados por estos modelos los han convertido en laaproximación más extendida. Su utilización comporta también diversos inconve-nientes. El primero de ellos es que el número de parámetros a estimar aumentaexponencialmente con el valor de n, por lo que sólo es posible considerar valoresrelativamente pequeños de n. Como consecuencia de esto último, estos modelosúnicamente contemplan dependencias locales, y no capturan la estructura comple-ta de las frases del lenguaje [JLM92].

Actualmente las GIP son aceptadas como un modelo razonable para la MLy sus ventajas respecto a los n-gramas han sido estudiadas en diferentes trabajos[JWS+95, Che96]. Una característica que las hace atractivas es que permiten repre-sentar relaciones a largo término entre las palabras de una cadena, proporcionandouna interpretación de la estructura de la cadena completa. Sin embargo, su utiliza-ción comporta problemas graves de aprendizaje de los modelos, de interpretacióny de integración.

El aprendizaje de estos modelos para abordar problemas complejos es un serioinconveniente debido en primer lugar, a su elevado coste computacional, y en se-gundo lugar, debido al gran volumen de datos que son necesarios para su correctaestimación. En trabajos recientes se han estudiado alternativas para atenuar esteproblema utilizando modelos sintácticos de categorías de palabras [CJ98, Bel98].

En cuanto a problemas de interpretación, una cuestión de especial interés es elcálculo de la probabilidad de una subcadena inicial a partir de una GIP, para la quese han propuesto diferentes soluciones [JL91, Sto95]. Estas destacan especialmentepor su elevado coste computacional, por lo que únicamente cabe considerar su

6

aplicación en situaciones en las que el conjunto de parámetros del modelo seareducido. En esta tesis se va a estudiar una de estas soluciones y se van a explorarotras posibilidades para aproximar la probabilidad de una subcadena inicial a partirde una GIP.

La integración eficiente de las GIP en ML es una cuestión importante parael cual se han presentado diferentes propuestas. En [Dup93] se hace uso de unaGIP como modelo de lenguaje en una tarea de RAH, cuyos terminales representanel vocabulario de la tarea. Durante el proceso de análisis se genera una red quese va expandiendo dinámicamente para dar cuenta de la secuencia de entrada. En[JWS+95] se propone la combinación de un modelo de n-gramas con una GIP.El primer modelo da cuenta fundamentalmente de la información local mientrasque el segundo recoge la información a más largo término. Estas propuestas tienenen común, por un lado, que los terminales de la GIP representan el vocabulariode la tarea, y por otros, que los modelos incontextuales utilizados se obtuvieronmediante métodos deductivos.

En [CJ98] se propone una idea similar a la anterior en la que se combina unmodelo de n-gramas con un modelo sintáctico. En esta propuesta el modelo de n-gramas da cuenta de información a nivel léxico mientras que el modelo sintácticolo hace a nivel de categorías léxicas [Jel98]. Una de las justificaciones de esta pro-puesta es que la relaciones que se establecen a largo término entre las diferentespartes de una cadena quedan mejor representadas en un nivel “superior” al nivelléxico. En [Bel98] se propone una idea análoga a la propuesta mencionada ante-riormente en la que un modelo de n-gramas que representa información local secombina con un modelo capaz de representar información global.

Esta idea resulta especialmente atractiva dado que las relaciones a largo tér-mino están recogidas en el modelo sintáctico mientras que las relaciones a cortotérmino están representadas en el modelo de n-gramas. Un modelo sintáctico conun pequeño número de categorías necesita menos parámetros que un modelo a ni-vel de palabras, dado que el número de relaciones es notablemente menor. Estofacilita su obtención mediante alguno de los métodos de estimación mencionados.En esta tesis se va a explorar un modelo de lenguaje en esta línea, en el que elmodelo sintáctico es un GIP, y se combina con modelo de n-gramas a nivel depalabras.

1.3. Organización general de esta tesis

De acuerdo con lo que se ha expuesto anteriormente, en esta tesis se va a estu-diar el problema de la estimación de las probabilidades de las GIP, y la aplicaciónde estos modelos en tareas complejas de ML. En concreto, en este trabajo:

se estudian los algoritmos clásicos IO y VS de Estimación Probabilística delas GIP y las funciones que optimizan,

se proponen nuevos algoritmos de estimación de las GIP a partir de un sub-

7

conjunto de derivaciones elegidas con criterios estocásticos,

se exploran algoritmos de estimación a partir de un subconjunto de deriva-ciones elegidas con criterios estructurales contenidos en una muestra paren-tizada y se proponen otros nuevos,

se estudia la consistencia de las GIP obtenidas con los diferentes métodos deestimación, y las características estocásticas de las gramáticas,

se propone un método para el cálculo de la probabilidad de la mejor inter-pretación de una subcadena inicial,

se propone un modelo para la ML que combina una GIP con un modelo den-gramas.

Por todo ello, esta memoria se organiza de la siguiente forma. En el segundocapítulo se introducen los principales conceptos y la notación utilizada a lo largodel texto. En el tercer capítulo se estudian los algoritmo IO y VS y la relaciónentre las funciones que éstos optimizan. Así mismo, se estudian las propiedadesestocásticas de los modelos obtenidos. En el cuarto capítulo se exploran diferen-tes algoritmos de estimación que hacen uso de un subconjunto de derivaciones enel proceso de estimación. En el quinto capítulo se estudian algunos problemas re-lacionados con la aplicación de las GIP como mecanismo de interpretación y suintegración en problemas de ML. En el último capítulo se detallan los resultadosalcanzados y los trabajos futuros.

8

Capítulo 2

Revisión de conceptos delenguajes y gramáticas formales

En este capítulo presentamos algunas definiciones sobre lenguajes y gramáti-cas en el marco de la Teoría de Lenguajes Formales. Se introducen las nocionesnecesarias que permite relacionar ambos conceptos y se plantean los problemasque supone su aplicación a tareas complejas de Reconocimiento Sintáctico de For-mas. A continuación se generalizan los conceptos vistos en un marco estocástico,y se estudian los problemas que introduce esta generalización.

2.1. Lenguajes y gramáticas formales

En esta revisión se van a presentar aquellos conceptos relacionados con el temade la tesis. Una revisión más completa se puede encontrar, entre otros, en [GT78,HU79, Fu82].

Definición 2.1. Se define un alfabeto Σ como un conjunto finito de símbolos.

Los elementos de un alfabeto constituyen las unidades básicas o primitivas deun lenguaje. Estos, a su vez, se agrupan en cadenas.

Definición 2.2. Se denomina cadena o palabra sobre un alfabeto Σ a una secuenciafinita de elementos de Σ.

La longitud de una cadena x es el número de símbolos que tiene, y lo escri-biremos como |x|. La cadena vacía es aquella que no posee ningún elemento yla denotaremos como ε (|ε| = 0). Denotaremos como Σ∗ el conjunto de todas lascadenas de longitud mayor o igual que 0 que se pueden formar con símbolos deΣ. Así mismo Σ+ denotará el conjunto de todas las cadenas de longitud mayor oigual que 1 que se pueden formar con elementos de Σ, es decir, Σ+ = Σ∗ − ε.

Definición 2.3. Se define un lenguaje L sobre Σ como un subconjunto del conjuntoΣ∗.

9

10

Un lenguaje se puede definir mediante un autómata formal que tiene un ca-rácter de aceptor de cadenas, o con una gramática formal que tiene un carácter degenerador de cadenas. La relación entre ambos tipos de formalismos ha sido am-pliamente estudiada y aparece recogida en diversos textos [GT78, HU79, Fu82]. Enesta tesis utilizaremos las gramáticas formales como mecanismo de especificaciónde lenguajes formales.

Definición 2.4. Se define una gramática formal como un tupla (N,Σ, S, P ) donde:

N es un conjunto finito de símbolos llamados no terminales,

Σ un conjunto finito de símbolos llamados terminales que cumple que N ∩Σ = ∅,

P es un conjunto finito de reglas o producciones. Cada regla es un par (α, β)que se representa de la forma α → β donde α, β ∈ (N∪Σ)∗. A α se le llamaantecedente y a β consecuente,

S ∈ N es el símbolo inicial o axioma de la gramática.

Las definiciones que introducimos a continuación establecen cómo se formanlas cadenas que genera una gramática formal.

Definición 2.5. Si r = (α → β) es una regla que pertenece a P , y γ, ϕ ∈ (N ∪Σ)∗, entonces hay una derivación directa de γαϕ a γβϕ, y lo expresaremos comoγαϕ

r⇒ γβϕ.

También suele decirse que γαϕ se reescribe en γβϕ, o que la regla r reescribea α. Tanto γαϕ como γβϕ se les llama forma sentencial.

Definición 2.6. Se dice que hay una derivación de α1 a α2, donde α1, α2 ∈(N ∪ Σ)∗, y lo expresaremos como α1

∗⇒ α2, si existe una secuencia de formassentenciales α1 = µ0, µ1, . . . , µm = α2, m ≥ 0, con µ1, . . . , µm−1 ∈ (N ∪ Σ)∗,y una secuencia de reglas (r1, r2, . . . , rm) ∈ P tal que:

α1 = µ0r1⇒ µ1

r2⇒ . . .rm⇒ µm = α2.

Si la secuencia de reglas es no vacía, es decir, m ≥ 1, entonces la expresión

anterior se escribe como α1+⇒ α2.

Definición 2.7. Se define la longitud de la derivación, |dx|, como el número dereglas de la secuencia (r1, r2, . . . , rm).

Definición 2.8. Se define el lenguaje generado por una gramática G, como L(G) =

x ∈ Σ∗ | S∗⇒ x.

Atendiendo a la forma de sus reglas, las gramáticas se clasifican en 4 tipos quedefinimos a continuación [GT78, Fu82].

11

Definición 2.9. En la jerarquía de Chomsky, los cuatro tipos de gramáticas forma-les son:

Una gramática es regular o de tipo 3 si todas sus reglas son de la formaA → aB ó A → a donde A,B ∈ N y a ∈ Σ.

Una gramática es incontextual o de tipo 2 si todas sus reglas son de la formaA → α donde A ∈ N y α ∈ (N ∪ Σ)∗.

Una gramática es sensible al contexto o de tipo 1 si todas sus reglas son dela forma α → β tal que |α| ≤ |β|.

Una gramática es no restringida o de tipo 0 si no se establece ninguna res-tricción sobre sus reglas.

La jerarquía entre las gramáticas se extiende de forma natural a los lenguajesformales. Se dice que un lenguaje es regular si es generado por una gramáticaregular, es incontextual si es generado por una gramática incontextual, es sensibleal contexto si es generado por una gramática de tipo 1 y de tipo 0 en el último caso.

La complejidad de los problemas que pueden ser abordados con cada tipo delenguaje crece de acuerdo con la jerarquía: los lenguajes regulares permiten tra-tar problemas más simples, mientras que los lenguajes de tipo 0 permiten tratarproblemas más complejos. Paralelamente, la dificultad de los algoritmos que per-mite la manipulación eficiente de las gramáticas también crece con su capacidadexpresiva. De esta forma, ciertos problemas que pueden ser resueltos en las gra-máticas regulares en un tiempo razonable, son inabordables con las gramáticas norestringidas.

Las gramáticas y lenguajes incontextuales son un compromiso razonable entrela complejidad de los problemas que permiten abordar y el coste de los algoritmosque permiten su adecuada manipulación. De un lado, las gramáticas incontextualestiene suficiente capacidad expresiva como para establecer relaciones a largo térmi-no entre las primitivas del lenguaje, lo que las convierte en una herramienta potentepara representar problemas complejos. De otro lado, existen algoritmo robustos yeficientes que permiten su adecuada manipulación. En esta tesis vamos a trabajarcon las gramáticas incontextuales (GI), por lo que las definiciones que siguen estánreferidas básicamente a este tipo de gramáticas.

A continuación se presentan algunas definiciones y propiedades relacionadascon las GI. Dado un lenguaje incontextual, éste puede representarse por más deuna GI.

Definición 2.10. Dos GI G1 y G2 son equivalentes si L(G1) = L(G2).

Se dice que una gramática incontextual está en Forma Normal de Chomsky(FNC) si todas sus reglas son de la forma A → BC o A → a donde A,B,C ∈ Ny a ∈ Σ. Existen diferentes formas normales de las GI [GT78, Fu82], aunque a lolargo de esta tesis vamos a trabajar, en general, con GI en FNC. Esto no implica

12

ninguna pérdida de generalidad, puesto que dada una GI G1, existe una GI G2

en FNC tal que L(G1) = L(G2) [GT78]. Esto significa que cualquier lenguajeincontextual puede ser definido con una GI en FNC.

Definición 2.11. Una derivación a izquierdas de una cadena x ∈ L(G), dx, es unaderivación tal que µ0 = S y µm = x y ri, 1 ≤ i ≤ m, reescribe el no terminal mása la izquierda de µi−1.

De esta forma la derivación a izquierdas dx queda definida por la secuencia dereglas utilizadas. De forma análoga puede definirse la derivación a derechas. Eneste trabajo únicamente consideraremos derivaciones a izquierdas, por lo que nosreferiremos a ellas simplemente como derivación.

Un concepto estrechamente relacionado con el de derivación es el de árbolde derivación o de análisis. Un árbol de derivación o de análisis permite ponerde manifiesto de una forma relativamente sencilla las relaciones que se establecenentre las diferentes partes de una cadena.

Definición 2.12. Un árbol etiquetado y ordenado t es un árbol de derivación o deanálisis en una GI G si [Fu82]:

cada nodo del árbol tiene una etiqueta, que es un símbolo de (N ∪ Σ),

la raíz del árbol tiene la etiqueta S,

si un nodo cuya etiqueta es A tiene un descendiente directo diferente de élmismo, entonces A ∈ N ,

si los nodos n1, n2, . . . , nm son descendientes directos del nodo n (cuyaetiqueta es A) en orden de izquierda a derecha, con etiquetas A1, A2, . . . Am

respectivamente, entonces A → A1A2 . . . Am es una regla de P .

Un árbol de análisis puede asociarse a una única derivación, de forma que lasecuencia de reglas utilizada es la que se obtiene haciendo un recorrido en preordendel árbol y haciendo uso de la última característica de la definición anterior (verejemplo en Figura 2.1).

Dada una cadena x y una GI G tal que x ∈ L(G), es posible que exista másde un árbol de análisis que permita derivar x a partir del símbolo inicial. Así porejemplo, dada la GI definida en la Figura 2.1 y la cadena 1010, ésta puede ser ge-nerada con la derivación de la figura o con la derivación (S → SS, S → AS,A →1, S → 0, S → AS,A → 1, S → 0).

Definición 2.13. Una GI se dice que es no ambigua si para cada x ∈ L(G) exis-te una única derivación que permite generar x; en caso contrario se dice que esambigua.

Dada una cadena x ∈ L(G), denotaremos como Dx el conjunto de todas lasderivaciones diferentes que tiene la cadena x y |Dx| representará su talla.

13

1

S

0

S

JJ

S

1

A

0

S

JJ

S

##

cc

S

Figura 2.1: Dada la GI G = (S,A, 0, 1, S, S → SS, S → AS, S → 0, S →1, A → 1) y el árbol de derivación t, la derivación asociada es d = (S →SS, S → SS, S → 1, S → 0, S → AS,A → 1, S → 0).

2.2. Análisis sintáctico de una cadena

Una cuestión esencial relacionada con las GI es cómo podemos identificar lascadenas que pertenecen al lenguaje generado por una gramática. Este problema,consiste en evaluar la relación x ∈ L(G), dada una cadena x y una GI G. El aná-lisis sintáctico de una cadena consiste en determinar esta relación. La solución alproblema consiste en encontrar una secuencia de derivaciones que permitan derivarx a partir del símbolo inicial de G utilizando reglas de la gramática.

Se puede solucionar el problema con un coste lineal con la longitud de la cade-na, pero restringiendo severamente la clase de gramáticas, y por tanto la capacidadexpresiva de las mismas [HU79]. Otro forma de solucionarlo es con un coste cú-bico con la longitud de la cadena utilizando gramáticas sin restricciones. Estasgramáticas permiten representar adecuadamente los fenómenos de ruido y variabi-lidad presentes en los problemas que se pretende abordar, por lo que en esta tesisseguiremos esta última propuesta.

Una solución eficiente para abordar el análisis sintáctico consiste en utilizaralgún método tabular basado en Programación Dinámica [HU79]. Estos métodosse basan en la construcción de una tabla de análisis tal que cada celda representala solución a un determinado subproblema. Los métodos tabulares más conocidosson el algoritmo de Cocke-Younger-Kasami [HU79] que opera con GI en FNC, yel algoritmo de Earley [Ear70] que permite trabajar con una GI cuyas reglas noes necesario que tengan ninguna particularidad. En esencia, ambos algoritmos sonsimilares [Ney91]. En esta tesis haremos uso sólo del primero de ellos, por lo quenos limitaremos a describir únicamente éste.

El algoritmo de Cocke-Younger-Kasami se basa en la construcción de una tablade análisis V de dimensión |x| × |x|, tal que si A ∈ Vi,j , entonces A

∗⇒ xi . . . xj .De esta forma x ∈ L(G) si S pertenece a V1,|x| (ver el algoritmo en la Figura 2.2).

El algoritmo opera analizando partes de la cadena cada vez de mayor longitudhasta incluir finalmente toda cadena. Este tipo de análisis se conoce como análisisascendente puesto que va considerando subárboles de análisis desde las hojas hacia

14

1: Algoritmo de Cocke-Younger-Kasami2: Entrada3: GI G = (N,Σ, S, P ) en FNC y una cadena x de talla n > 0.4: Salida5: Tabla de análisis V .6: Método7: para i = 1 hasta n hacer8: Vi,i = A | A → xi ∈ P9: fin para

10: para i = 1 hasta n − 1 hacer11: para j = i + 1 hasta n hacer12: Vi,j = ∅13: para k = i hasta j − 1 hacer14: Vi,j = Vi,j ∪ A | A → BC,B ∈ Vi,k y C ∈ Vk+1,j15: fin para16: fin para17: fin para

Figura 2.2: Algoritmo de Cocke-Younger-Kasami para computar la tabla de análi-sis.

la raíz. El coste temporal del algoritmo de Cocke-Younger-Kasami es O(|x|3|P |)mientras que el coste espacial es O(|x|2|N |).

2.3. Lenguajes y gramáticas formales probabilísticos

En diferentes aplicaciones de RSF se presentan habitualmente fenómenos deruido y variabilidad junto con aspectos de incertidumbre que requieren un tratoadecuado. Estas consideraciones introducen la necesidad de generalizar los mo-delos vistos para contemplar tales fenómenos. En Teoría de Lenguajes Formalespuede abordarse este hecho asociando una medida de probabilidad a algunos delos conceptos vistos. Las GIP son modelos apropiados que introducen una nociónde uso a la teoría ordinaria de los lenguajes formales. Son herramientas simplespara las cuales existen algoritmos eficientes que permiten su adecuada utilización;permiten representar de manera compacta y sencilla los fenómenos de ruido y va-riabilidad mencionados; además, tienen la ventaja de que existen algoritmos robus-tos que permiten su aprendizaje automático a partir de ejemplos. Esto las convierteen una potente herramienta para abordar problemas reales complejos de RSF.

A continuación introducimos una serie de definiciones que van precisamente enesta dirección, y siguen básicamente las definiciones que pueden verse en [BT73]y [Wet80]. Puesto que la mayoría de los conceptos que vamos a comentar sonsimilares a los vistos, pero extendiéndolos con un marco estocásticos, trataremosde seguir el orden de presentación del apartado anterior.

15

Definición 2.14. Se define un lenguaje probabilístico sobre un alfabeto Σ comoun par (L,Φ), donde L es un lenguaje formal y Φ : Σ∗ →

es un función realsobre las cadenas de Σ∗. La función de probabilidad Φ satisface las siguientescondiciones:

1. x /∈ L ⇒ Φ(x) = 0 para todo x ∈ Σ∗,

2. x ∈ L ⇒ 0 < Φ(x) ≤ 1 para todo x ∈ Σ∗,

3.∑

x∈L Φ(x) = 1.

Anteriormente hemos visto como la gramáticas formales constituyen una he-rramienta apropiada para definir lenguajes formales. Así pues, parece razonableque extendamos los conceptos anteriores sobre gramáticas formales para introdu-cir algún mecanismo que permita tratar los lenguajes formales probabilísticos. Es-te nuevo formalismo serán las gramáticas probabilísticas. En este trabajo estamosinteresados en modelos incontextuales, por lo que las definiciones que damos acontinuación están referidas básicamente a las GI, aunque se pueden extender fá-cilmente a otros tipos de gramáticas [Mar74].

Definición 2.15. Se define una Gramática Incontextual Probabilística (GIP) Gp

como un par (G, p) tal que G es una GI, denominada en este caso gramática ca-racterística, y p es una función p : P →]0, 1] que observa la siguiente propiedad:

∀A ∈ N,∑

(A→α)∈ΓA

p(A → α) = 1,

donde ΓA representa el conjunto de reglas de la gramática cuyo antecedente es A.

Definición 2.16. Definimos la probabilidad de la derivación dx de la cadena xcomo:

Pr(x, dx | Gp) =∏

(A→α)∈P

p(A → α)N(A→α,dx),

donde N(A → α, dx) representa el número de veces que la regla A → α haaparecido en la derivación dx.

Definición 2.17. Definimos la probabilidad de la cadena x como:

Pr(x | Gp) =∑

dx∈Dx

Pr(x, dx | Gp),

donde Dx denota el conjunto de todas las derivaciones diferentes de la cadena x.

Dada una GIP Gp = (G, p), se puede definir una GIP G′

p cuya gramáticacaracterística está en FNC y además para todo x ∈ L(G) se cumple que Pr(x |Gp) = Pr(x | G

′

p) [Cas94].

16

Definición 2.18. Llamaremos probabilidad de la mejor derivación de la cade-na x a:

Pr(x | Gp) = maxdx∈Dx

Pr(x, dx | Gp).

Definición 2.19. Llamaremos derivación más probable o mejor derivación a:

dx = arg maxdx∈Dx

Pr(x, dx | Gp).

De esta forma la probabilidad de la mejor derivación podemos expresarla tam-bién como Pr(x, dx | Gp).

Las definiciones 2.17 y 2.18 pueden extenderse a un número arbitrario de deri-vaciones tal como se contempla en la siguiente definición.

Definición 2.20. Dada la cadena x y un conjunto de derivaciones de la misma∆x ⊆ Dx, se define la probabilidad de la cadena con el conjunto ∆x como:

Pr(x,∆x | Gp) =∑

dx∈∆x

Pr(x, dx | Gp).

Observemos que la expresión de la definición anterior coincide con la expresiónde la definición 2.17 cuando el conjunto de derivaciones considerado coincide conel máximo posible. También coincide con la expresión de la definición 2.18 cuandola derivación considerada es aquella que tiene máxima probabilidad de entre todaslas posibles derivaciones de una cadena.

Definición 2.21. Se define el lenguaje generado por una GIP Gp como, L(Gp) =x ∈ L(G)|Pr(x | Gp) > 0.

Dado un lenguaje probabilístico (L,Φ) cualquiera, donde L es un lenguajeincontextual, podría pensarse que siempre es posible encontrar una GIP Gp =(G, p) tal que L = L(G) y Φ es computada en términos de la definición 2.17. Sinembargo, no todo lenguaje probabilístico en el cual L es un lenguaje incontextualpuede ser representado por una GIP tal como establece el siguiente teorema.

Teorema 2.3.1 ([BT73]). Dado el lenguaje incontextual L = anbn | n ≥ 0 yla función Φ(anbn) = 1

en! y Φ(x) = 0 si x /∈ L, no existe ninguna GIP Gp querepresente el lenguaje probabilístico (L,Φ).

Obsérvese que (L,Φ) cumple las condiciones de la definición 2.14 [Wet80].La intuición para la demostración de este teorema es sencilla. Si examinamos lafunción de la definición 2.17 podemos observar que ésta crece de forma inversa auna función polinómica dependiente de la longitud de la cadena. Mientras que lafunción Φ del teorema anterior crece de forma inversa a una función exponencialdependiente de la longitud de la cadena. Puesto que ningún polinomio puede apro-ximar una función que crece exponencialmente, Φ no puede ser computada porninguna GIP.

17

De forma inversa podría pensarse que cualquier GIP Gp es capaz de generarun lenguaje probabilístico (L,Φ) donde L = L(G) y Φ(x) = Pr(x | Gp). Sinembargo esto tampoco es necesariamente cierto ya que la función de probabilidaddefinida debe cumplir la condición 3 de la definición 2.14.

Definición 2.22. Una GIP Gp es consistente si y solo si:∑

x∈L(G)

Pr(x | Gp) = 1.

En cualquier otro caso la gramática no es consistente.

Definición 2.23. Dada una GIP Gp consistente, el par (L(G),P) es un lenguajeincontextual probabilístico, donde P es una función de probabilidad computada entérminos de la expresión de la definición 2.17.

El problema de la consistencia de un GIP es por tanto un problema crucial parautilizar este formalismo como método de representación de lenguajes incontextua-les probabilísticos, y a lo largo de este trabajo pondremos especial énfasis en esteaspecto.

En lo que sigue, vamos a introducir una serie de conceptos que nos permitiránestudiar el problema de la consistencia de una GIP. Cuando una GIP es consistente,se pueden derivar una serie de importantes características del lenguaje que genera.A continuación describimos también estas propiedades.

Definición 2.24. Dada una GIP Gp, se define su matriz de esperanzas de no termi-nales E = (eij), 1 ≤ i, j ≤ |N |, como1:

eij =∑

(A→α)∈ΓAi

p(A → α)N(Aj , α),

donde el valor N(Aj , α) representa el número de veces que el no terminal Aj apa-rece en el consecuente α.

Observemos que el valor eij representa el número esperado de no terminalesAj que se pueden generar directamente a partir de Ai.

Definición 2.25. Se define la matriz de esperanzas de terminales Z = (zij), 1 ≤i ≤ |N |, 1 ≤ j ≤ |Σ| como:

zij =∑

(A→α)∈ΓAi

p(A → α)N(aj , α),

donde el valor N(aj , α) representa el número de veces que el terminal aj apareceen el consecuente α.

1En diferentes partes de este trabajo supondremos que los no terminales se numeran de 1 a |N |como S = A1, A2, . . . , A|N|. Algo similar supondremos para los terminales pero numerados de 1 a|Σ|.

18

Similarmente a la definición anterior, el valor zij representa el número esperadode terminales aj que se pueden generar directamente a partir de Ai.

El siguiente teorema basado en las definiciones anteriores establece qué condi-ciones deben darse para que una GIP sea consistente.

Teorema 2.3.2 ([BT73]). Una GIP Gp es consistente, si ρ(E) < 1, donde ρ(E) oradio espectral es el valor absoluto del mayor valor propio de la matriz E.

Este teorema proporciona una manera sencilla y directa de comprobar la con-sistencia de una GIP únicamente estudiando las características de E. Existen di-ferentes formas de calcular los valores propios de una matriz. Sin embargo obser-vemos que sólo estamos interesado en el valor absoluto del mayor de ellos. Lossiguientes teoremas tratan de resolver este problema de manera sencilla.

Teorema 2.3.3 ([Wet80]). Para cualquier matriz cuadrada M de dimensión m,ρ(M) < 1 si y sólo si existe un n ≥ 1, tal que para todo i, 1 ≤ i ≤ m:

m∑

j=1

|(Mn)ij | < 1.

Corolario 2.3.1 ([Wet80]). Si se cumple el teorema anterior para un valor n,entonces también se cumple para cualquier n′ > n.

Un método para determinar si el radio espectral de una matriz es menor queuno consiste en evaluar la expresión del Teorema 2.3.3. Si no se cumple entoncesse multiplica la matriz por si misma y se vuelva a aplicar. Este proceso se repitehasta comprobar si el radio espectral es menor que uno o hasta repetir el proceso unnúmero suficiente de veces. Si este proceso termina sin saber si el radio espectrales menor que uno habría que recurrir a algún método que permita calcular el radioespectral.

Cuando una GIP Gp es consistente se pueden derivar interesantes propiedadesestocásticas acerca de las derivaciones y el lenguaje que se puede generar. Hemosvisto que el valor eij se interpreta como el número esperado de no terminales Aj

que se pueden generar directamente a partir del no terminal Ai. Si deseamos cono-cer el número esperado de no terminales Aj que se pueden generar a partir de Ai endos derivaciones directas consecutivas, deberemos considerar cualquier no termi-nal Ak intermedio que pueda generarse desde Ai y que a su vez genere Aj , esto es,∑|N |

k=1 eikekj . Observemos que este valor representa el valor ij-ésimo de la matrizE2. De forma análoga se pueden obtener e interpretar las matrices E3, E4, . . ., y unrazonamiento similar puede aplicarse a la matriz identidad I = E0. Consideremosahora la siguiente suma infinita:

Q =∞∑

i=0

Ei.

19

El valor ij-ésimo de la matriz Q representa el número esperado de veces que seha generado el no terminal Aj a partir del Ai en un proceso generativo infinito.La suma anterior únicamente se puede calcular cuando es convergente y esto úni-camente sucede cuando el radio espectral de E es menor que uno [Wet80], y portanto cuando la gramática es consistente, en cuyo caso [Wet80, JL91]:

Q =∞∑

i=0

Ei =I

I − E= (I − E)−1.

Cuando se cumple la condición anterior, en [Wet80] se demuestra que la lon-gitud esperada de las derivaciones en un GIP Gp, LED(Gp), y la longitud esperadade las cadenas generadas por Gp, LEC(Gp), son respectivamente [Wet80]:

LED(Gp) =

|N |∑

i=1

Q1i,

LEC(Gp) =

|Σ|∑

i=1

(QZ)1i.

Otra propiedad interesante acerca de las GIP consistentes está referida a lafrecuencia con que los diferentes terminales aparecen en el lenguaje que genera.

Definición 2.26. Dada una GIP Gp, se define la densidad del terminal ai ∈ Σ,d(ai, L(Gp)), como el número relativo de veces que el terminal ai aparece en ca-denas de L(Gp).

Teorema 2.3.4 ([BT73]). Dado el lenguaje L(Gp) generado por una GIP Gp con-sistente, se cumple que:

∀ai ∈ Σ, d(ai, L(Gp)) =(100 . . . 0) Q Zi

LEC(Gp),

donde Zi representa la columna i-ésima de la matriz Z y (100 . . . 0) es un vectorfila de |N | dimensiones.

Así pues, vemos que la propiedad de consistencia de una GIP es un proble-ma importante ya que determina la validez de este formalismo para especificarlenguajes probabilísticos. Además, su cumplimiento permite derivar interesantespropiedades estocásticas del lenguaje que genera. Puesto que estamos interesadosen estudiar métodos de estimación de las GIP, la consistencia será un aspecto queestudiaremos extensamente en esta tesis.

2.4. Análisis sintáctico probabilístico de una cadena

El análisis sintáctico probabilístico consiste en determinar si Pr(x | Gp) > 0.Para solucionar este problema hay que encontrar al menos una derivación cuya pro-babilidad sea mayor que cero y que permita derivar la cadena a partir del símboloinicial de la gramática.

20

A continuación describimos tres algoritmos que resuelven por ProgramaciónDinámica este problema en un tiempo polinómico. Para ello consideraremos quela GIP Gp está en FNC, que como ya vimos, no supone ninguna pérdida de gene-ralidad. Existen otras propuestas para resolver este problema que no requieren quela gramática esté en ninguna forma normal especial [Sto95].

Algoritmo Inside

El algoritmo Inside permite determinar si Pr(x | Gp) > 0 calculando la pro-babilidad de la cadena a partir de todas las posibles derivaciones. El algoritmoInside [Bak79, LY90, Ney92, Cas96] es una algoritmo basado en un esquema deProgramación Dinámica análogo al algoritmo de Cocke-Younger-Kasami (ver Fi-gura 2.2). Se basa en la definición de e(A < i, j >) = Pr(A

∗⇒ xi . . . xj|Gp),como la probabilidad de que la subcadena xi . . . xj sea generada a partir de A. Estaprobabilidad puede ser evaluada eficientemente, para todo A ∈ N , como:

e(A < i, i >) = p(A → xi) 1 ≤ i ≤ |x|,

e(A < i, j >) =∑

B,C∈N

p(A → BC)

j−1∑

k=i

e(B < i, k >)e(C < k + 1, j >)

1 ≤ i < j ≤ |x|.De esta forma, Pr(x|Gp) = e(S < 1, |x| >).

El coste temporal de esta algoritmo es O(|x|3|P |) y el coste espacial es O(|x|2|N |).

Algoritmo Outside

De manera análoga al algoritmo Inside, el algoritmo Outside permite determi-nar si una cadena x es generada por una GIP calculando la probabilidad de la mismaa partir de todas las posibles derivaciones. En el algoritmo Outside [Bak79, LY90,Ney92, Cas96] se define f(A < i, j >) = Pr(S

∗⇒ x1 . . . xi−1Axj+1 . . . x|x| |Gp) como la probabilidad de que a partir del axioma inicial se genere la subca-dena x1 . . . xi−1, a continuación el no terminal A y a continuación la subcadenaxj+1 . . . x|x|. De esta forma, al no terminal A le corresponde generar la subcadenaxi . . . xj . Esta expresión puede ser calculada eficientemente mediante el siguienteesquema. Para todo A ∈ N :

f(A < 1, |x| >) =

1 si A = S0 si A 6= S

f(A < i, j >) =∑

B,C∈N

(p(B → CA)

i−1∑

k=1

f(B < k, j >)e(C < k, i − 1 >)

+ p(B → AC)

|x|∑

k=j+1

f(B < i, k >)e(C < j + 1, k >)

1 ≤ i ≤ j ≤ |x|.

21

De esta forma Pr(x|Gp) =∑

A∈N f(A < i, i >)p(A → xi), 1 ≤ i ≤ |x|.Análogamente al algoritmo Inside, el cómputo de las expresiones anteriores

requiere un coste temporal O(|x|3|P |) y un coste espacial es O(|x|2|N |).

Algoritmo de Viterbi

Otra posibilidad para determinar si Pr(x | Gp) > 0 consiste en encontrar almenos una derivación cuya probabilidad sea mayor que cero. El siguiente algo-ritmo permite calcular la derivación de la cadena cuya probabilidad es máxima.El cálculo de esta probabilidad está basado en la definición de e(A < i, j >) =

Pr(A∗⇒ xi . . . xj|Gp) como la probabilidad de la mejor derivación que genera la

subcadena xi . . . xj a partir de A. Para todo A ∈ N :

e(A < i, i >) = p(A → xi),

e(A < i, j >) = maxB,C∈N

p(A → BC) maxk=i,...,j−1

e(B < i, k >)e(C < k + 1, j >)

1 ≤ i < j ≤ |x|. (2.1)

Por tanto, Pr(x|Gp) = e(S < 1, |x| >).Similarmente a los algoritmos anteriores, el coste temporal de este algoritmo

es O(|x|3|P |), mientras que el coste espacial es O(|x|2|P |).Nótese que este algoritmo es similar al algoritmo de Cocke-Younger-Kasami.

Además, procede de forma análoga al algoritmo de Viterbi definido para modelosregulares [For73], por lo que le llamaremos igualmente algoritmo de Viterbi.

La mejor derivación de la cadena x, dx, puede obtenerse fácilmente a partirdel algoritmo anterior guardando los argumentos que maximizan cada uno de lossubproblemas. Esta información es sumamente importante en determinados pro-blemas de RSF en los que se desea conocer las relaciones más probables entre lasdiferentes partes de una cadena.

22

Capítulo 3

Estimación de las GIP

En este capítulo se presentan dos de los algoritmos clásicos de estimación delas GIP. Uno de ellos optimiza la función de verosimilitud de la muestra, y el otrooptimiza la verosimilitud de la mejor derivación de la muestra. Así mismo, se estu-dian las relaciones entre las funciones que optimizan ambos algoritmos. El cumpli-miento de la propiedad de consistencia es fundamental en los modelos obtenidospor cualquier método de estimación. En este capítulo demostramos esta propie-dad para los algoritmos que se va a presentar. Por último, se estudian una seriede importantes propiedades estocásticas acerca del lenguaje generado por la GIPestimada.

3.1. Estimación probabilística de las GIP

El problema de la estimación de una GIP puede enunciarse en los siguien-tes términos: sea (L,Φ) un lenguaje probabilístico sobre un alfabeto Σ, tal queL ⊆ L(G) para una GI G dada, y sea Φ una función de probabilidad, en general,desconocida. Dada una muestra Ω del lenguaje, que asumimos que refleja la distri-bución (desconocida) de Φ, el problema consiste en determinar las probabilidadesde una GIP a partir de dicha muestra para representar dicha función. Tal comovimos en el Capítulo 2, para abordar este problema es necesario asumir que la fun-ción Φ puede representarse por medio de una GIP. Por tanto, dada Gp = (G, p) yΩ, se desea encontrar el conjunto de parámetros de la GIP que hacen que la dis-tribución de probabilidad que ésta define sobre L se ajuste lo máximo posible a ladistribución desconocida Φ y representada por Ω. Se pretende obtener el conjuntode parámetros tal que:

p′ = arg maxp

fp(Ω), (3.1)

donde p es el conjunto de probabilidades de la GIP, y fp() es una función criterioa optimizar dependiente de la muestra, y definida en términos del conjunto de pro-babilidades. Así pues, para abordar el problema de la estimación debemos definirdicha función criterio, y algún método de optimización que nos permita obtener p ′.

23

24

Respecto al método de optimización, en esta tesis se van a considerar algorit-mos de maximización en el marco de las Transformaciones Crecientes [Bau72].Una Transformación Creciente es una función de un espacio paramétrico que tieneciertas restricciones, en sí mismo. El siguiente teorema nos permite introducir esteconcepto, así como algunas de sus propiedades más importantes:

Teorema 3.1.1 ([BE67]). Sea P (Θ) un polinomio homogéneo con coeficientes nonegativos de grado d en sus variables Θ = Θij. Sea θ = θij un punto deldominio D = θij | θij ≥ 0,

∑qi

j=1 θij = 1, i = 1, . . . , p i j = 1, . . . , qi, y sea

Q(Θ) un punto de D definido como1:

Q(Θ)ij =θij(∂P/∂Θij)θ∑qi

k=1 θik(∂P/∂Θik)θ,

tal que ∀i∑qi

k=1 θik(∂P/∂Θik)θ 6= 0. Entonces, P (Q(θ)) > P (θ) excepto siQ(θ) = θ.

La aplicación del teorema anterior permite obtener un máximo local del poli-nomio P en el espacio de búsqueda definido por D haciendo uso del algoritmo dedescenso por gradiente de la Figura 3.1.

1: Algoritmo de estimación2: Entrada3: P (Θ)4: Salida5: θ6: Método7: θ = valores iniciales8: repetir9: calcular Q(Θ) utilizando P (Θ)

10: θ = Q(θ)11: hasta converger

Figura 3.1: Esquema general de los algoritmos de estimación derivados a partir deuna Transformación Creciente [Cas96].

Dado un polinomio que cumple las condiciones del Teorema 3.1.1, y un puntoinicial θ del dominio definido en el teorema, el problema de la estimación se planteacomo la aplicación repetida de la transformación hasta alcanzar un máximo localdel polinomio definido2.

Un punto crucial en este algoritmo es la elección del valor inicial del paráme-tro θ, ya que condiciona la localidad del máximo alcanzado [Mer93]. Este es un

1Por comodidad y siguiendo otros trabajos [Cas96], en lo que sigue escribiremos (∂P/∂Θij)θ

como ∂P/∂θij .2En ocasiones lo que suele hacerse es estimar hasta que la diferencia entre dos iteraciones conse-

cutivas está por debajo de un umbral.

25

problema que aparece en algoritmos de esta naturaleza y cuyo estudio está más alládel propósito de esta tesis.

Nótese como las probabilidades de una GIP (definición 2.15) son un punto deldominio definido en el Teorema 3.1.1. Para una GIP Gp:

p(Ai → αj) = θij i = 1, . . . , |N |; j = 1, . . . , |ΓAi|,

donde ΓAirepresenta el conjunto de reglas de la gramática cuyo antecedente es

Ai. Por tanto, una función criterio definida en términos de estas probabilidades(el polinomio P () en el Teorema 3.1.1) puede ser convenientemente maximizadahaciendo uso del Teorema 3.1.1 y del algoritmo 3.1.

En el Capítulo 1 se ha hecho mención a funciones criterio utilizadas habitual-mente. En esta tesis la función criterio fp() (ver expresión 3.1) a optimizar serála función de verosimilitud. Para ello se van a hacer una serie de asunciones bas-tante restrictivas que facilitan el proceso de estimación [Bro87]: en primer lugar,se va a considerar que Φ pertenece a la familia de distribuciones de probabilidadsusceptibles de ser representadas por una GIP; en segundo lugar, la familia de dis-tribuciones bajo consideración están bien definidas; y en tercer lugar, la muestra Ωes representativa de la distribución definida por Φ y suficientemente grande. Ba-jo estas asunciones la estimación por máxima verosimilitud funciona mejor quecualquier otro método de estimación [Bro87].

La estimación por máxima verosimilitud puede interpretarse como la minimi-zación de la distancia de Kullback-Liebler [ER90] entre dos distribuciones. Éstaes una medida de distancia entre dos distribuciones parametrizadas por π y πo,definida como [CT91]:

D(πo||π) =∑

x∈X

Pr(x | πo) lnPr(x | πo)

Pr(x | π).

En realidad la distancia de Kullback-Liebler no es una verdadera distancia ya queno necesariamente cumple la desigualdad triangular, pero si cumple algunas im-portantes propiedades. En particular este valor es mayor o igual que cero, y es nulocuando π = πo [CT91]. En nuestro caso estamos considerando dos distribucionesrepresentadas por la muestra Ω y la GIP a estimar Gp. De esta forma, abusando dellenguaje, el proceso de optimización se puede reescribir como:

mınp

D(Φ||Gp) = mınp

∑

x∈L(G)

Pr(x | Φ) lnPr(x | Φ)

Pr(x | Gp)

=∑

x∈L(G)

Pr(x | Φ)maxp

ln Pr(x | Gp).

Bajo las asunciones realizadas, la muestra Ω es representativa de la distribuciónde Φ y suficientemente grande, por lo que la frecuencia con la que aparece cada

26

cadena en Ω se aproxima al valor definido por Φ [CT91], por lo que:

mınp

DG(Φ||Gp) =

∑x∈Ω maxp ln Pr(x | Gp)

|Ω| =1

|Ω| maxp

ln∏

x∈Ω

Pr(x | Gp).

Por tanto, nuestro problema consiste en obtener un parámetro p′ tal que:

p′ = arg maxp

ln∏

x∈Ω

Pr(x | Gp).

El logaritmo de la función de verosimilitud de la muestra, ln∏

x∈Ω Pr(x | Gp),es la función fp() de la expresión 3.1. El Teorema 3.1.1, junto con el algoritmo 3.1,nos proporciona el mecanimo apropiado para optimizar la función elegida, y de estaforma obtener p′. De esta forma ya tenemos todos los mecanismos necesarios parael proceso de estimación

Un método para obtener p′ consiste en utilizar el algoritmo Inside-Outside (IO)[Bak79, LY90, Ney92, Cas96]. Este algoritmo procede de forma iterativa, maximi-zando en cada etapa la verosimilitud de la muestra hasta alcanzar un máximo local.La obtención de este algoritmo, y la demostración de su convergencia puede ha-cerse desde diferentes perspectivas, como considerarlo como un caso particular delalgoritmo EM [Moo96] o como un método de optimización por gradiente [HAJ90].En este trabajo vamos a derivar este algoritmo en el marco de las TransformacionesCrecientes [BE67]. Éste es un marco suficientemente general que permite estudiarel algoritmo IO, además de otros algoritmos que veremos más adelante.

3.2. Los algoritmos IO y VS

La función de verosimilitud de una muestra es un polinomio definido en los tér-minos de Teorema 3.1.1, por lo que puede definirse una Transformación Crecientepara optimizarla en la que se basa el algoritmo IO. La convergencia del algoritmoestá garantizada por el teorema. A continuación describimos este algoritmo.

3.2.1. El algoritmo IO

Sea Gp = (G, p) una GIP, y sea Ω una muestra de L(G), es decir, un conjuntode cadenas de L(G) en el cual puede haber cadenas repetidas. El logaritmo de lafunción de verosimilitud de la muestra Ω dada la GIP Gp se define como:

ln Pr(Ω | Gp) = ln∏

x∈Ω

Pr(x | Gp). (3.2)

Puesto que esta función es un polinomio que cumple las condiciones del Teore-ma 3.1.1, se puede definir una transformación ∀(A → α) ∈ P como:

p(A → α) =p(A → α)

(∂ lnPr(Ω|Gp)

∂p(A→α)

)

∑(A→α)∈ΓA

p(A → α)(

∂ lnPr(Ω|Gp)∂p(A→α)

) .

27

Por el Teorema 3.1.1 esta transformación permite obtener una GIP Gp = (G, p) talque Pr(Ω | Gp) > Pr(Ω | Gp) a no ser que p = p.

Resolviendo parcialmente la expresión anterior la transformación que obtene-mos ∀(A → α) ∈ P es:

p(A → α) =

∑x∈Ω

1Pr(x|Gp)p(A → α)

(∂ Pr(x|Gp)∂p(A→α)

)

∑x∈Ω

1Pr(x|Gp)

∑(A→α)∈ΓA

p(A → α)(

∂ Pr(x|Gp)∂ Pr(A→α)

) . (3.3)

Para resolver la expresión anterior vamos a resolver previamente parte de sunumerador haciendo uso de las expresiones de las definiciones 2.16 y 2.17:

p(A → α)

(∂ Pr(x | Gp)

∂p(A → α)

)= p(A → α)

∑

dx∈Dx

(∂ Pr(x, dx | Gp)

∂p(A → α)

)

=∑

dx∈Dx

N(A → α, dx) Pr(x, dx | Gp).

Resolvemos a continuación parte del denominador de (3.3) haciendo uso de laexpresión anterior y teniendo en cuenta que el número de veces que el no terminalA ha sido derivado en dx es N(A, dx) =

∑(A→α)∈ΓA

N(A → α, dx) :

∑

(A→α)∈ΓA

p(A → α)

(∂ Pr(x | Gp)

∂p(A → α)

)

=∑

(A→α)∈ΓA

∑

dx∈Dx

N(A → α, dx) Pr(x, dx | Gp)

=∑

dx∈Dx

N(A, dx) Pr(x, dx | Gp).

Finalmente, la expresión (3.3) queda ∀(A → α) ∈ P como:

p(A → α) =

∑x∈Ω

1Pr(x|Gp)

∑dx∈Dx

N(A → α, dx) Pr(x, dx | Gp)∑

x∈Ω1

Pr(x|Gp)

∑dx∈Dx

N(A, dx) Pr(x, dx | Gp). (3.4)

El algoritmo IO consiste en la aplicación iterativa de esta transformación si-guiendo el esquema del algoritmo de la Figura 3.1 sobre las probabilidades de lagramática Gp, obteniendo en cada paso una Gp hasta maximizar localmente la fun-ción (3.2). Es importante destacar nuevamente en este algoritmo como las probabi-lidades iniciales de la gramática condicionan completamente el óptimo alcanzado.La convergencia del algoritmo está garantizada por el Teorema 3.1.1, y se producecuando las probabilidades de la gramática no varían de una iteración a la siguiente.

En la expresión (3.4), es necesario realizar los cómputos de manera eficiente,ya que, como comentamos, el número de derivaciones de una cadena puede llegara ser exponencial con la longitud de la cadena.

28

Supongamos que la gramática está en FNC y consideremos una regla A → BC ,con A,B,C ∈ N . Sea dx una derivación de la cadena x y tx el árbol de análisisasociado. Supongamos que esta regla aparece en tx en una posición delimitada porlos valores enteros i, j, k, 1 ≤ i ≤ k < j ≤ |x| (ver Figura 3.2). Si sumamosPSfrag replacements

S

A

B C

x1 xi−1 xi xk xk+1 · · ·xj xj+1 x|x|· · · · · ·· · ·

Figura 3.2: Esquema general de los árboles de análisis en los cuales la regla A →BC aparece delimitada por las posiciones i, j, k de la cadena x. S genera la formasentencial x1 . . . xi−1Axj+1 . . . x|x|, A genera BC , B genera la forma sentencialxi . . . xk y C genera la forma sentencial xk+1 . . . xj .

la probabilidad de todas las derivaciones en las cuales la regla A → BC apare-ce justamente delimitada por las posiciones i, j, k, entonces tenemos el valor (verSección 2.4):

Pr(S∗⇒ x1 . . . xi−1Axj+1 . . . x|x| | Gp)·p(A → BC) · Pr(B

∗⇒ xi . . . xk|Gp) · Pr(C∗⇒ xk+1 . . . xj|Gp)

= f(A < i, j >)p(A → BC)e(B < i, k >)e(C < k + 1, j >)

Considerando todos los posibles valores de estos límites y siguiendo un razona-miento similar para el denominador y para las reglas A → a, con A ∈ N y a ∈ Σ,la expresión (3.4) puede reescribirse como sigue, para toda (A → BC) ∈ P :

p(A → BC)

=

∑x∈Ω

p(A→BC)Pr(x|Gp)

∑1≤i≤k<j≤|x| f(A < i, j >)e(B < i, k >)e(C < k + 1, j >)

∑x∈Ω

1Pr(x|Gp)

∑|x|i=1

∑|x|j=i f(A < i, j >)e(A < i, j >)

,

(3.5)

29

y para toda (A → a) ∈ P :

p(A → a)

=

∑x∈Ω

1Pr(x|Gp)

∑|x|i=1, a=xi

f(A < i, i >)p(A → xi)∑

x∈Ω1

Pr(x|Gp)

∑|x|i=1

∑|x|j=i f(A < i, j >)e(A < i, j >)

. (3.6)

El algoritmo IO consiste en la aplicación de esta expresión según el esquemade la Figura 3.1. Esta es la formulación habitual para presentar el algoritmo IO[Bak79, LY90, Ney92, Cas96]. Observemos como en estas expresiones aparecenlos valores que se calculan con los algoritmos Inside y Outside. A partir de unosvalores iniciales de las probabilidades de la GIP, se aplica la expresión anterior re-petidamente sobre las probabilidades hasta que finalmente éstas no cambian entredos iteraciones consecutivas.

Cada iteración del algoritmo requiere aplicar el algoritmo Inside, a continua-ción el Outside y después la transformación, por lo que el coste temporal asintóticoen cada iteración es O(3|Ω|l3m|P |), con lm = maxx∈Ω |x|, o sea, O(|Ω|l3m|P |). Enel peor de los casos |P | ∈ O(|N |3). El coste espacial del algoritmo es O(l2m|N |).

3.2.2. El algoritmo VS

La probabilidad de la mejor derivación de una muestra es también un polinomiodefinido en los términos del Teorema 3.1.1. El algoritmo VS se basa en la defini-ción de una Transformación Creciente para optimizar esta función. Este algoritmopuede utilizarse para aproximar la verosimilitud de la muestra considerando única-mente la información contenida en la mejor derivación. La función que se defineen este caso es:

ln Pr(Ω | Gp) = ln∏

x∈Ω

Pr(x, dx | Gp). (3.7)

Puesto que esta función es un polinomio que cumple las condiciones del Teo-rema 3.1.1 se puede definir una transformación para maximizar dicha función.Siguiendo unos pasos similares a los que se han visto en el apartado anterior seobtiene la siguiente transformación ∀(A → α) ∈ P :

p(A → α) =

∑x∈Ω N(A → α, dx)∑

x∈Ω N(A, dx). (3.8)

Al igual que antes, aplicando iterativamente esta transformación siguiendo el es-quema de la Figura 3.1 sobre la gramática Gp permite obtener una Gp en cada pasohasta maximizar localmente la función (3.7). La convergencia del algoritmo estágarantizada por el Teorema 3.1.1. Cabe observar que la expresiones (3.4) y (3.8)son idénticas cuando la gramática es no ambigua, ya que en tal caso sólo existe unaderivación para cada cadena. Además, en tal situación, tanto el algoritmo IO comoel algoritmo VS alcanzan un máximo absoluto de la función objetivo puesto quelas cuentas de la expresión (3.8) no dependen de las probabilidades de la gramática

30

y sólo de la única derivación de cada cadena; únicamente es necesaria una iteraciónpara alcanzar dicho máximo.

Como vimos la Sección 2.4, la obtención de la mejor derivación puede hacersecon el algoritmo de Viterbi. Esto nos proporciona las cuentas que aparecen en laexpresión anterior. Por ello, nos referiremos a este método de estimación comoalgoritmo VS (del inglés Viterbi Score).

El coste temporal asintótico de esta transformación en cada iteración es O(|Ω|l3m|P |)para el algoritmo de Viterbi y O(|P |) para la transformación, mientras que el costeespacial es O(l2m|N |). Es importante destacar que aunque el algoritmo VS tiene uncoste temporal asintótico en cada iteración equivalente al algoritmo IO, el coste delprimero es tres veces menor que el del segundo.

3.2.3. Estudio empírico del comportamiento de los algoritmos IO yVS

En los apartados anteriores hemos presentado los algoritmos IO y VS en elmarco de las Transformaciones Crecientes, lo que nos ha permitido poner de ma-nifiesto la naturaleza similar de ambos algoritmos. Sin embargo este marco aportapoca información acerca del comportamiento del proceso iterativo de estimación.En un plano teórico apenas se puede decir nada de los algoritmo IO y VS, exceptosu convergencia y la localidad de la solución alcanzada. Sin embargo en la prácticasí se observan ciertas tendencias y similitudes en el comportamiento de los algorit-mos en las que nos basaremos para hacer otras propuestas en el capítulo siguiente.

Con el objetivo de ilustrar el comportamiento comentado vamos a presentarun experimento sintético de estimación con ambos algoritmos. Para ello se eligióel lenguaje de los palíndromos de dos terminales, previamente utilizado en otrostrabajos [LY90, PS92]. Con la GIP que puede verse en la Figura 3.3 se generóuna muestra de 100 cadenas de manera aleatoria. Esta gramática es consistente ygenera el lenguaje L = wwR | w ∈ a, b+ [PS92]. La muestra de aprendizajecontenía 58 cadenas diferentes y la masa de probabilidad de éstas era 0.55.

S → AC 0,4 C → SA 1,0S → BD 0,4 D → SB 1,0S → AA 0,1 A → a 1,0S → BB 0,1 B → b 1,0

Figura 3.3: GIP utilizada para generar la muestra de aprendizaje.

Se creó una gramática inicial a estimar de forma análoga a como se describeen [LY90, PS92], que estaba compuesta por todas las reglas que se pueden formarcon 5 no terminales y los terminales a y b, es decir, 135 reglas (53 + 5 × 2). Lasprobabilidades iniciales fueron generadas de forma aleatoria. Se probaron 3 inicia-lizaciones, aunque sólo se reporta una de ellas, dado que los resultados obtenidos

31

fueron similares. En el Apéndice A pueden verse los experimentos con las otrasdos inicializaciones.

A partir de esta GIP inicial, se estimó otra GIP tanto con el algoritmo IO comocon el VS. Después de cada iteración se evaluó la función que maximizaba cadauno de los algoritmos, esto es, la expresión (3.2) y (3.7), respectivamente. El pro-ceso de estimación continuó hasta que el valor de la función no cambió entre dositeraciones consecutivas. En la Figura 3.43 puede verse como evolucionaban lasfunciones maximizadas por cada algoritmo.

De este experimento (y de los que pueden verse en el Apéndice A y en otrostrabajos [SBC96, SB98a]) nos interesa destacar tres aspectos: el número de itera-ciones que cada algoritmo necesita hasta converger, la acumulación de la masa deprobabilidad de cada cadena en un número relativamente pequeño de derivaciones,y la bondad de los modelos obtenidos. A continuación comentamos detalladamentecada uno de estos aspectos.

PSfrag replacements

ln Pr(Ω | Gp)

ln Pr(Ω | Gp)

Iteraciones180160140120100806040200

-1400

-1300

-1200

-1100

-1000

-900

-800

-700

-600

Figura 3.4: Evolución de las funciones maximizadas con cada algoritmo cuando seestimó con el IO (línea continua) y cuando se estimó con el VS (línea discontinua).

Aunque los algoritmos IO y VS son algoritmos iterativos cuyo coste asintóticopor iteración es el mismo, estimar un modelo con uno u otro algoritmo no “cues-ta” lo mismo, ya que ambos no convergen igual de rápido en la práctica. En elproceso de estimación, el algoritmo VS considera únicamente la derivación másprobable, por lo que sólo se tiene en cuenta la información estructural contenida enésta; las reglas que no aparecen en una de las mejores derivaciones pasan a tenerprobabilidad nula y no se tienen en cuenta para la siguiente iteración. Esto puede

3De las 3 inicializaciones de las probabilidades, sólo se reporta aquella en la que el algoritmo IOalcanzó un mejor óptimo.

32

suponer una reducción severa en el factor |P | del coste y el algoritmo tarda pocasiteraciones en converger. En la Figura 3.4 puede verse la diferencia entre el nú-mero de iteraciones que necesita el algoritmo IO para converger frente a las pocasiteraciones del algoritmo VS.

El algoritmo IO procede esencialmente de forma similar al algoritmo VS, peroel primero considera todas las posibles derivaciones en el proceso de aprendizaje.Si una regla aparece en al menos una derivación no nula, entonces nunca tendráprobabilidad nula. En este caso el algoritmo converge más lentamente (ver Figu-ra 3.4). La aplicación de este algoritmo en experimentos reales está muy condicio-nada por este comportamiento.

Otro aspecto a destacar que se da en ambos algoritmos, es la tendencia a acu-mular la masa de probabilidad en las mejores derivaciones de cada cadena. Véaseen la Tabla 3.1 la masa de probabilidad acumulada en la muestra, frente a la ma-sa acumulada en las cinco mejores derivaciones, antes de empezar el proceso deestimación y al terminar. Puede observarse como la masa de probabilidad quedarecogida en un pequeño conjunto de derivaciones. Esta tendencia que se observa eneste experimento también puede verse en los que se presentan en el Apéndice A yen otros trabajos [SBC96, SB98a]. En la Figura 3.5 se ilustra este comportamientopara una cadena de la muestra durante el proceso de estimación. Puede observarseque en las iteraciones en las que la función optimizada tiende a “estabilizarse” laacumulación de probabilidad en las mejores derivaciones es más notable. Al finaldel proceso de estimación la masa de probabilidad de la cadena se acumula en unconjunto relativamente pequeño de las mejores derivaciones. Este comportamientosugiere que las derivaciones más probables condicionan mayormente la evolucióndel proceso de aprendizaje, y esto se acentúa en las últimas iteraciones.

Cuadro 3.1: Masa de probabilidad acumulada en el conjunto de cadenas no repeti-das de la muestra (columna mdp) y porcentaje de la masa de probabilidad acumu-lada en las 5 mejores derivaciones (columna 5md).

IOiteración mdp 5md

0 0.002347 50 %190 0.662 98.3 %

VSiteración mdp 5md

0 0.002347 50 %10 0.032136 97.2 %

Otro aspecto importante a notar en ambos algoritmos está referido a la “bon-dad” de los modelos obtenidos. Cada uno de ellos optimiza una función diferente,aunque en ocasiones, por cuestiones prácticas, cabe considerar el uso del algorit-mo VS para aproximar la verosimilitud de la muestra. Véase en la Figura 3.4 elmáximo alcanzado por cada función. La verosimilitud de la muestra con el mode-lo estimado con el algoritmo VS coincide prácticamente con el valor de la funciónmaximizada por éste. En todos los experimentos realizados, el valor de la verosimi-

33

litud obtenido por modelos estimados con el algoritmo VS fue significativamentemenor que el valor de la verosimilitud obtenido con modelos estimados con elalgoritmo IO.

010

2030

4050

6070

80

02

46

810

1214

1618

20

-70-60-50-40-30-20-10

0

PSfrag replacements

Iteración (×10)

Derivación

02

46

810

1214

1618

0

2

4

6

8

10

-20

-18

-16

-14

-12

-10

-8

PSfrag replacements

Iteración (×10)

Derivación

Figura 3.5: Evolución del logaritmo de la probabilidad de las mejores derivacionespara la cadena abaaba de la muestra cuando se estimó con el algoritmo IO (gráficasuperior) y cuando se estimó con el algoritmo VS (gráfica inferior). La derivación0 corresponde a la mejor.

Las consideraciones anteriores introducen interesante problemas que concier-nen de un lado a los propios algoritmos de estimación, y de otro, a los modelos esti-mados. Por una parte, es importante estudiar las características de los algoritmos deestimación IO y VS para poner de manifiesto las relación que existe entre ambos,

34

y la motivación e importancia de elegir uno u otro. Por otra parte, resulta crucialel estudio de las propiedades de los modelos obtenidos, ya que el cumplimiento dealgunas de las mismas condiciona la validez de los modelos y su aplicabilidad acierto problemas.

En la siguiente sección estudiaremos la relación que existe entre los algoritmosIO y VS, y entre las funciones que estos maximizan. A continuación estudiaremoslas principales propiedades de las GIP estimadas con los algoritmos anteriores.

3.3. Relación entre las funciones maximizadas por los al-goritmos IO y VS

Hemos comentado que la aplicación del algoritmo IO para estimar las pro-babilidades de las GIP está restringida a situaciones en las cuales lo permita lavelocidad de convergencia. El algoritmo VS puede utilizarse en tal caso para es-timar las probabilidades y aproximar la verosimilitud de una muestra. Es por elloque resulta importante estudiar el comportamiento de la función que maximiza elalgoritmo IO cuando se utiliza el algoritmo VS para estimar las probabilidades delas reglas de una GIP. Resulta igualmente importante conocer como evolucionala función que maximiza el algoritmo VS cuando se utiliza el algoritmo IO parala estimación. Algunos trabajos han sido realizados en este sentido para modelosocultos de Markov [ME91a, ME91b], que muestran que se puede establecer unacota superior entre la diferencia de las dos funciones para un modelo dado. En elcaso de las GIP puede establecerse una cota teórica similar, pero bajo asuncionesmuy pesimistas. Algunos experimentos que aparecen más adelante así lo muestran.

Vamos a estudiar la diferencia entre los logaritmos de las expresiones de lasdefiniciones 2.17 y 2.18, y también la diferencia entre las expresiones (3.2) y (3.7).Para ello hay que tener en cuenta que el máximo número de derivaciones que tieneuna cadena x de Gp cuando la gramática característica de Gp está en FNC, esa|x|−1|N |2|x|−2 con |x| > 1, donde [SBC96]:

am =1

m + 1

(2m)!

m!m!≤ 1

m + 1

4m

√πm

.

De acuerdo con esto, podemos definir la relación entre los logaritmos de las

35

expresiones de las definiciones 2.17 y 2.18 para una cadena x de Gp con |x| > 1:

ln maxdx∈Dx

Pr(x, dx | Gp) ≤ ln∑

dx∈Dx

Pr(x, dx | Gp)

≤ ln1

|x|4|x|−1

√π(|x| − 1)

|N |2|x|−2 maxdx∈Dx

Pr(x, dx | Gp)

≤ ln22|x|−2

|x|√|x| − 1

|N |2|x|−2 + ln maxdx∈Dx

Pr(x, dx | Gp)

≤ 2|x| ln 2|N | − ln |x|√

|x| − 1 + ln maxdx∈Dx

Pr(x, dx | Gp)

≤ 2|x| ln 2|N | + ln maxdx∈Dx

Pr(x, dx | Gp).

Finalmente se obtiene el siguiente resultado:

ln Pr(x|Gp) − ln Pr(x|Gp) ≤ 2|x| ln 2|N |. (3.9)

El significado de esta cota puede entenderse intuitivamente en los siguiente tér-minos: la diferencia entre el logaritmo de las dos funciones está acotado por ellogaritmo de una cota superior del número de derivaciones que tiene una cadena(que es (2|N |)2|x|), ya que la máxima probabilidad de una derivación es uno.

Esta expresión puede extenderse fácilmente a una muestra Ω de L(G), de formaque pueda establecerse una cota para la diferencia de las funciones (3.2) y (3.7):

ln∏

x∈Ω

Pr(x | Gp) =∑

x∈Ω

ln Pr(x | Gp)

≤∑

x∈Ω

(2|x| ln 2|N | + ln Pr(x|Gp))

=∑

x∈Ω

2|x| ln 2|N | + ln∏

x∈Ω

Pr(x|Gp),

con lo que finalmente tenemos el siguiente resultado:

ln Pr(Ω | Gp) − ln Pr(Ω|Gp) ≤ 2∑

x∈Ω

|x| ln 2|N |. (3.10)

Esta cota superior puede utilizarse para estimar las diferencias de verosimilituden la estimación probabilística en caso de que exista un algoritmo eficiente paraobtener máximos globales de las correspondientes funciones objetivos.

Para una muestra Ω proponemos las siguientes definiciones:

p∗ = arg maxp

Pr(Ω | Gp), (3.11)

p ∗ = arg maxp

Pr(Ω | Gp), (3.12)

36

y las correspondientes gramáticas G∗p = (G, p∗) y G∗

p = (G, p ∗). A partir de estasdefiniciones y haciendo uso de (3.10) podemos derivar los siguientes resultados:

ln Pr(Ω | G∗p) ≤ ln Pr(Ω | G∗

p) ≤ ln Pr(Ω | G∗p)

≤ ln Pr(Ω | G∗p) + 2

∑

x∈Ω

|x| ln 2|N |

≤ ln Pr(Ω | G∗p) + 2

∑

x∈Ω

|x| ln 2|N |

≤ ln Pr(Ω | G∗p) + 2

∑

x∈Ω

|x| ln 2|N |.

Consecuentemente tendremos que:

0 ≤ ln Pr(Ω | G∗p) − ln Pr(Ω | G∗

p) ≤ 2∑

x∈Ω

|x| ln 2|N |,

0 ≤ ln Pr(Ω | G∗p) − ln Pr(Ω | G∗

p) ≤ 2∑

x∈Ω

|x| ln 2|N |.

Por tanto, para un algoritmo ideal que pueda calcular el máximo global de lasdos funciones, la diferencia entre ellas está acotado superiormente por una funciónlineal de la muestra y una función logarítmica del número de símbolos no termi-nales. Obviamente, esta es una cota muy pesimista ya que estamos considerandoque todas las derivaciones son posibles para cada cadena x y una gramática dadas,sin considerar las restricciones sintácticas de ésta última. Además, hay que teneren cuenta que tanto el algoritmo IO como el VS no garantizan que se alcanza unmáximo global de la función que están maximizando.

En realidad la diferencia real entre las dos funciones es bastante menor que lacota propuesta, y además, en la práctica esta diferencia tiende a decrecer cuando seestima con cualquiera de los dos algoritmos. Así por ejemplo, para el experimentode los palíndromos descrito en la sección anterior, la Figura 3.6 ilustra cómo evolu-cionaban las funciones para los dos algoritmos de estimación, y la diferencia entrelas dos funciones y la cota teórica puede verse en la Figura 3.7 (puede observarse lamisma tendencia en los experimentos con otras inicializaciones en el Apéndice A).

En la Figura 3.6 vemos que cuando se utilizó el algoritmo IO para la estima-ción, el valor de la expresión (3.7) tendía a crecer en cada iteración, puesto quecomo hemos comentado, la masa de probabilidad de cada cadena tiende a acumu-larse en una pocas derivaciones. Como consecuencia de esto, la diferencia entre lasexpresiones (3.2) y (3.7) tendía a decrecer. Así, en el ejemplo que presentamos enla Figura 3.7, esta diferencia se reduce en un 91,5% entre la primera y la últimaiteración, y el valor de la diferencia supone un 5,12% respecto al valor de la cotateórica. En la Figura 3.6 vemos que en alguna iteración, el valor de (3.7) descendióligeramente. Esto pudo deberse a que alguna regla perteneciente a la mejor deriva-ción desapareciese por problemas de precisión y a partir de ese momento pasase aconsiderarse alguna otra derivación.

37

PSfrag replacements

ln Pr(Ω | Gp)

ln Pr(Ω | Gp)

Iteraciones18016014012010080604020

108642

0-3500

-3000

-2500

-2000

-1500

-1000

-500

PSfrag replacements

ln Pr(Ω | Gp)

ln Pr(Ω | Gp)

Iteraciones

18016014012010080604020

1086420-3500

-3000

-2500

-2000

-1500

-1000

-500

Figura 3.6: Evolución de las funciones optimizadas con los algoritmos IO y VScuando se estimó la GIP empleando el algoritmo IO (gráfica superior) y el algorit-mo VS (gráfica inferior).

Cuando se utilizó el algoritmo VS en la estimación, el valor de la expresión(3.2) también tendía a crecer. Sin embargo es importante destacar que el valor de laverosimilitud de la muestra cuando se estimó con el VS nunca superó al valor de laverosimilitud cuando se estimó con el IO (pueden otros ejemplos en [SBC96] y enel Apéndice A). Además, la diferencia entre las expresiones (3.2) y (3.7) tambiéntendía a decrecer, aunque con un porcentaje de decrecimiento entre la primera y laúltima iteración significativamente menor que cuando se estimó con el algoritmoIO. En el ejemplo que presentamos en la Figura 3.7, la diferencia se reduce en un

38

PSfrag replacements

Iteraciones18016014012010080604020

108642

00

4500

4000

3500

3000

2500

2000

1500

1000

500

PSfrag replacements

Iteraciones

180160140120100

80604020

10864200

4500

4000

3500

3000

2500

2000

1500

1000

500

Figura 3.7: En línea continua aparece la diferencia entre las dos funciones cuandose estimó la GIP empleando el algoritmo IO (gráfica superior) y el algoritmo VS(gráfica inferior). En línea discontinua aparece el valor de la cota teórica.

41,7% entre la primera y la última iteración, y el valor de la diferencia supone un3,8% respecto al valor de la cota teórica.

Vemos por tanto como ambos algoritmos proceden de manera similar acumu-lando la masa de probabilidad de las cadenas en las mejores derivaciones. Además,podemos observar como, efectivamente, la cota teórica propuesta resulta ser de-masiado pesimista: estamos suponiendo que la gramática es capaz de generar cadacadena con el máximo número posible de derivaciones.

Una cota más realista sería aquella que considerase únicamente el verdadero

39

número de derivaciones que tiene cada cadena, esto es, basada en criterios estruc-turales, en cuyo caso:

ln Pr(Ω | Gp) ≤ ln Pr(Ω | Gp)

≤∑

x∈Dx

ln(|Dx| Pr(x | Gp))

=∑

x∈Ω

ln |Dx| + ln Pr(x | Gp).

De esta forma tenemos que:

ln Pr(Ω | Gp) − ln Pr(Ω | Gp) ≤∑

x∈Ω

ln |Dx|.

Esta cota tiene el inconveniente de que su cómputo no es inmediato a partir de losparámetros de la gramática y la muestra como lo era la cota anterior, puesto quehay que calcular el número de derivaciones de cada cadena.

Este valor puede calcularse con un algoritmo similar al algoritmo Inside. Estacota fue calculada para los experimentos comentados anteriormente y los resulta-dos obtenidos pueden verse en la Figura 3.8. Los saltos que aparecen en la nuevacota corresponden al momento en que algunas reglas desaparecen por problemasde precisión. Vemos como efectivamente esta cota es más ajustada que la cota an-terior ya que en cada instante únicamente se considera el número de derivacionesque realmente tiene cada cadena. Este fenómeno es más destacable en el caso delalgoritmo VS.

Como conclusión de este punto cabe destacar que se ha presentado una cotateórica para la diferencia entre las funciones maximizadas por los algoritmos IOy VS. Se ha visto como en la práctica esta diferencia tiende a decrecer cuando seestima con cualquiera de ellos y es bastante menor que la cota teórica propues-ta. Se ha visto como ambos algoritmos tienden a acumular la probabilidad de lasderivaciones en unas pocas cadenas.

Conviene notar que el comportamiento comentado justifica, en parte, el usoque se hace de algoritmos similares en modelos regulares en RAH. En este camporesulta habitual utilizar el algoritmo de Baum-Welch [HAJ90] (equivalente al algo-ritmo IO pero para modelos regulares) en la etapa de aprendizaje para estimar lasprobabilidades de un modelo. En la etapa de reconocimiento se utiliza el algoritmode Viterbi [For73] (la versión para modelos regulares) para obtener el mejor cami-no, y por tanto, la mejor interpretación que da cuenta de una secuencia acústica deentrada. El algoritmo de Baum-Welch tiende a acumular la masa de probabilidaden las mejores derivaciones. En la etapa de reconocimiento, el algoritmo de Viterbisaca provecho de esta característica y recupera el camino más probable, es decir,aquel camino que mayor información estocástica ha concentrado.

Cuando finaliza el proceso de estimación, utilizando el algoritmo IO o el algo-ritmo VS, se obtiene un modelo que ha recogido una gran cantidad de informaciónestocástica de la muestra. A continuación estudiamos este aspecto de proceso deestimación.

40

PSfrag replacements

Iteraciones18016014012010080604020

108642

00

4500

4000

3500

3000

2500

2000

1500

1000

500

PSfrag replacements

Iteraciones

180160140120100

80604020

10864200

4500

4000

3500

3000

2500

2000

1500

1000

500

Figura 3.8: En línea continua aparece la diferencia entre las dos funciones cuandose estimó la GIP empleando el algoritmo IO (gráfica superior) y el algoritmo VS(gráfica inferior). En línea discontinua aparece el valor de la cota basada en criteriosestructurales.

3.4. Propiedades de las GIP estimadas con los algoritmosIO y VS: consistencia de los modelos

Una cuestión fundamental relacionada con cualquier mecanismo de aprendiza-je de las GIP y en particular con los algoritmos de estimación vistos en la secciónanterior consiste en garantizar que los modelos obtenidos generan un lenguaje in-contextual probabilístico, esto es, que las GIP son consistentes. El cumplimiento

41

de esta propiedad es esencial ya que no sólo confirma la validez de los modelosestimados, sino también la de los propios algoritmos de estimación.

En [Mar74, CPG83] se demostró el cumplimiento de esta propiedad en condi-ciones muy restrictivas, esto es, para gramáticas no ambiguas cuyas probabilidadeseran estimadas a partir de las frecuencias relativas obtenidas a partir de una mues-tra. Esta propiedad se ha venido asumiendo como cierta para las GIP sin restriccio-nes estimadas con los algoritmos IO y VS. Sin embargo, resulta crucial demostrarformalmente que esto es cierto.

En esta sección vamos a demostrar que las GIP cuyas probabilidades han sidoestimadas con los algoritmos IO y VS satisfacen la propiedad de consistencia. Elcumplimiento de esta propiedad permite derivar otras interesantes propiedades es-tocásticas que relacionan el lenguaje generado por la GIP con la muestra a partirde la cual han sido estimadas las probabilidades. Algunas de estas propiedades yafueron conjeturadas en [Wet80].

En primer lugar, vamos a demostrar en el siguiente teorema como la aplicaciónde la expresión (3.4) sobre una GIP Gp da lugar a una gramática consistente. Paraello seguiremos la línea argumental que se sigue en [CPG83].

Teorema 3.4.1. Sea Gp = (G, p) una GIP y sea Ω una muestra de L(G). SiGp = (G, p) es una GIP obtenida a partir de Gp aplicando la transformacióndescrita en (3.4), entonces Gp es consistente.

DemostraciónLa matriz de esperanzas de no terminales E asociada a la GIP Gp es:

eij =∑

(A→α)∈ΓAi

p(A → α)N(Aj , α)

=

∑x∈Ω

1Pr(x|Gp)

∑dx∈Dx

Pr(x, dx | Gp)∑

(A→α)∈ΓAiN(A → α, dx)N(Aj , α)

∑x∈Ω

1Pr(x|Gp)

∑dx∈Dx

N(Ai, dx) Pr(x, dx | Gp).

Recordemos del Capítulo 2 que eij representa el número esperado de no termi-nales Aj que se pueden generar directamente a partir de Ai en la GIP Gp. La ideasubyacente para demostrar la consistencia se basa en probar que el número de noterminales que son introducidos en un proceso generativo infinito tiende a ser cero.

Vamos a continuación a simplificar la notación:

ei =∑

x∈Ω

1

Pr(x | Gp)

∑

dx∈Dx

N(Ai, dx) Pr(x, dx | Gp), (3.13)

hij =∑

x∈Ω

1

Pr(x | Gp)

∑

dx∈Dx

Pr(x, dx | Gp)∑

(A→α)∈ΓAi

N(A → α, dx)N(Aj , α).

De esta forma eij = hij/ei.

42

A continuación conjeturamos que se cumplen las siguientes ecuaciones:

e1 = λ + h11 + h21 + . . . + h|N |1 (3.14.1)

e2 = h12 + h22 + . . . + h|N |2 (3.14.2)

...

e|N | = h1|N | + h2|N | + . . . + h|N ||N | (3.14.|N|)

donde λ es el número de cadenas en Ω.Vamos a demostrar que la conjetura se cumple para (3.14.1). La parte derecha

de la ecuación es:

λ +

|N |∑

i=1

hi1 =∑

x∈Ω

1

Pr(x | Gp)

∑

dx∈Dx

Pr(x, dx | Gp)

+

|N |∑

i=1

∑

x∈Ω

1

Pr(x | Gp)

∑

dx∈Dx

Pr(x, dx | Gp)∑

(A→α)∈ΓAi

N(A → α, dx)N(A1, α)

=∑

x∈Ω

1

Pr(x | Gp)

∑

dx∈Dx

Pr(x, dx | Gp)

+∑

x∈Ω

1

Pr(x | Gp)

∑

dx∈Dx

Pr(x, dx | Gp)

N(A1,dx)−1︷ ︸︸ ︷|N |∑

i=1

∑

(A→α)∈ΓAi

N(A → α, dx)N(A1, α) .

(3.15)

Observemos que N(A1, dx) representa el número de no terminales A1 (= S) quehan aparecido en la parte derecha de las reglas que participan en la derivación dx.No se considera el símbolo inicial, y por ello la expresión anterior es igual a:

∑

x∈Ω

1

Pr(x | Gp)

∑

dx∈Dx

Pr(x, dx | Gp)

+∑

x∈Ω

1

Pr(x | Gp)

∑

dx∈Dx

Pr(x, dx | Gp)(N(A1, dx) − 1) =

∑

x∈Ω

1

Pr(x | Gp)

∑

dx∈Dx

Pr(x, dx | Gp)N(A1, dx) = e1.

Algo similar se puede demostrar para (3.14.2), . . . , (3.14.|N |), con lo que quedademostrada la conjetura.

Demostraremos a continuación que Gp es consistente haciendo uso del Teore-

ma 2.3.2. Demostraremos que la suma infinita Q = I + E + E2+ . . . converge y

que por ello el radio espectral de E es menor que uno. Primero demostramos quelos elementos de la primera fila de Q (la fila asociada al símbolo inicial A1 = S)

43

están acotados. Para demostrar esto definimos la suma parcial de n + 1 términos

W(n)

= I +E +E2+ . . .+E

n. Nos referiremos como w

(n)ij al elemento ij-ésimo

de la matriz W(n)

. Dado que En+1

= EnE, tenemos que:

e(n+1)ij = e

(n)i1 e1j + e

(n)i2 e2j + . . . + e

(n)i|N |e|N |j

= e(n)i1

h1j

e1+ e

(n)i2

h2j

e2+ . . . + e

(n)i|N |

h|N |j

e|N |.

A partir de la expresión anterior tenemos que:

e(0)11 = 1,

e(1)11 =

h11

e1,

e(2)11 = e

(1)11

h11

e1+ e

(1)12

h21

e2+ . . . + e

(1)1|N |

h|N |1

e|N |,

...

e(n+1)11 = e

(n)11

h11

e1+ e

(n)12

h21

e2+ . . . + e

(n)1|N |

h|N |1

e|N |.

Sumando la serie de ecuaciones anteriores:

w(n+1)11 = 1 + (1 + e

(1)11 + e

(2)11 + . . . + e

(n)11 )

h11

e1+ . . .

+(e(1)1|N | + e

(2)1|N | + . . . + e

(n)1|N |)

h|N |1

e|N |

= 1 + w(n)11

h11

e1+ . . . + w

(n)1|N |

h|N |1

e|N |.

De forma similar:

w(n+1)12 = w

(n)11

h12

e1+ . . . + w

(n)1|N |

h|N |2

e|N |,

...

w(n+1)1|N | = w

(n)11

h1|N |

e1+ . . . + w

(n)1|N |

h|N ||N |

e|N |.

Supongamos por hipótesis de inducción que:

w(n)11 ≤ e1

λ,w

(n)12 ≤ e2

λ, . . . , w

(n)1|N | ≤

e|N |

λ. (3.16)

Entonces, haciendo uso de (3.14.1), . . . , (3.14.|N|) y dividiendo por λ, tenemos

44

que:

w(n+1)11 ≤ 1 +

e1

λ

h11

e1+ . . . +

e|N |

λ

h|N |1

e|N |=

e1

λ

w(n+1)12 ≤ e1

λ

h12

e1+ . . . +

e|N |

λ

h|N |1

e|N |=

e2

λ

...

w(n+1)1|N | ≤ e1

λ

h1|N |

e1+ . . . +

e|N |

λ

h|N ||N |

e|N |=

e|N |

λ

Para n = 0 y n = 1, la demostración de (3.16) es inmediata, y por ello se cumpleque w

(n)1i ≤ ei/λ para i = 1, 2, . . . , |N | y para todo n. Observemos que w

(n)1i ≤

w(n+1)1i , y por ello w

(n)1i es una secuencia creciente acotada superiormente. Por tanto

existe el límite lımn→∞ w(n)1i = w1i para cada i y w1i ≤ ei/λ.

En segundo lugar hay que demostrar que los elementos del resto de filas de Q

están también acotados. Esto lo haremos demostrando que existe el límite lımn→∞ w(n)ji

para j = 2, 3, . . . , |N | y i = 1, 2, . . . , |N |. Para demostrar esto, observemos que

existe un entero d ≥ 1 que puede ser diferente para cada i, tal que e(d)1i > 0. Tal

como se comenta en [CPG83], este d existe claramente puesto que si para algún i,e(k)1i = 0 para todo k, entonces el no terminal Ai no es alcanzable desde el sím-

bolo inicial y por tanto las reglas Ai → α (∀α) son innecesarias y L(G) se puedegenerar sin utilizar esas producciones. Observemos que:

0 ≤ e(d)1j w

(n)ji = e

(d)1j eji + e

(d)1j e

(2)ji + . . . + e

(d)1j e

(n)ji

≤|N |∑

l=1

e(d)1l eli +

|N |∑

l=1

e(d)1l e

(2)li + . . . +

|N |∑

l=1

e(d)1l e

(n)li

= e(d+1)1i + e

(d+2)1i + . . . + e

(d+n)1i ≤ w

(d+n)1i ≤ w1i,

y por ello existe el límite lımn→∞ w(n)ji = wji (j = 2, 3, . . . , |N |; i = 1, 2, . . . , |N |).

Observemos que hemos supuesto que i 6= j, pero el mismo razonamiento se puedeaplicar cuando i = j. Así pues, la suma infinita I + E + E

2+ . . . es convergente.

Por tanto, por el Teorema 2.3.2, el radio espectral de E es menor que uno y Gp esconsistente.

Del teorema anterior cabe destacar, en primer lugar, que su cumplimiento esefectivo independientemente de que la gramática esté en FNC o no, lo que permi-te demostrar la corrección de otros métodos de estimación como el propuesto en[Sto95].

45

En segundo lugar, cabe destacar que para algoritmos iterativos como el IO, lapropiedad de consistencia se cumple desde la primera iteración, con lo que cual-quier GIP estimada con este algoritmo genera un lenguaje probabilístico.

A partir del resultado anterior vamos a demostrar una serie de interesantes pro-piedades que relacionan una muestra Ω con la gramática Gp cuyas probabilidadeshan sido estimadas haciendo uso de Ω. Para ello vamos a introducir previamentealgunas definiciones.

Definición 3.1. Dada una GIP Gp y una muestra Ω de L(G), se define la longitudmedia de las derivaciones de Ω, LMDGp(Ω), como:

LMDGp(Ω) =

∑x∈Ω

1Pr(x|Gp)

∑dx∈Dx

Pr(x, dx | Gp)|dx|λ

donde λ es el número de cadenas de Ω.

Definición 3.2. Se define la longitud media de las cadenas de Ω, LMC(Ω), como:

LMC(Ω) =

∑x∈Ω |x|

λ.

Definición 3.3. Se define la densidad relativa de un símbolo terminal ai ∈ Σ,1 ≤ i ≤ |Σ|, en la muestra Ω como:

δ(ai,Ω) =

∑x∈Ω N(ai, x)∑

x∈Ω |x|

donde N(ai, x) representa el número de veces que el terminal ai aparece en lacadena x.

Corolario 3.4.1. Sea una GIP Gp = (G, p) y sea Ω una muestra de L(G). Si Gp =(G, p) es una GIP que ha sido obtenida a partir de Gp aplicando la transformacióndescrita en (3.4), entonces se cumplen las siguiente ecuaciones:

LED(Gp) = LMDGp(Ω),

LEC(Gp) = LMC(Ω),

d(ai, L(Gp)) = δ(ai,Ω) ∀ai ∈ Σ.

DemostraciónPara demostrar la primera ecuación, sabemos por el Teorema 3.4.1 que w1i =

(Q)1i = ei/λ para i = 1, 2, . . . , |N |. Haciendo uso de (3.13), y dado que |dx| =∑|N |i=1 N(Ai, dx):

LED(Gp) =

|N |∑

i=1

(Q)1i =

∑|N |i=1 ei

λ=

∑x∈Ω

1Pr(x|Gp)

∑dx∈Dx

Pr(x, dx | Gp) |dx|λ

.

46

Por tanto se cumple la primera de las ecuaciones.Vamos a demostrar a continuación la segunda de las ecuaciones. Sea Z = (z ij),

1 ≤ i ≤ |N |, 1 ≤ j ≤ |Σ|, la matriz de esperanzas de terminales de Gp. Entonces:

zij =∑

(A→α)∈ΓAi

p(A → α)N(aj , α)

=

∑x∈Ω

1Pr(x|Gp)

∑dx∈Dx

Pr(x, dx | Gp)∑

(A→α)∈ΓAiN(A → α, dx)N(aj , α)

∑x∈Ω

1Pr(x|Gp)

∑dx∈Dx

N(Ai, dx) Pr(x, dx | Gp).

(3.17)

Observemos que el denominador de la expresión anterior es ei definido en (3.13).Por tanto:

LEC(Gp) =

|Σ|∑

j=1

|N |∑

i=1

(Q)1i(Z)ij =

|Σ|∑

j=1

|N |∑

i=1

ei

λzij

=

∑x∈Ω

1Pr(x|Gp)

∑dx∈Dx

Pr(x, dx | Gp)

|x|︷ ︸︸ ︷|Σ|∑

j=1

|N |∑

i=1

∑

(A→α)∈ΓAi

N(A → α, dx)N(aj , α)

λ

=

∑x∈Ω |x|λ

.

Por tanto se cumple la ecuación LEC(Gp) = LMC(Ω).Para demostrar la última ecuación seguiremos el razonamiento de [CR83]. A

partir del Teorema 2.3.4, el Teorema 3.4.1 y la expresión (3.17) tenemos que paratodo ai ∈ Σ:

d(ai, L(Gp) =(1 0 0 . . . 0)Q Zi

LEC(Gp)=

∑|N |j=1 q1jzji∑x∈Ω |x|/λ

=

∑x∈Ω

1Pr(x|Gp)

∑dx∈Dx

Pr(x, dx | Gp)

N(ai,x)︷ ︸︸ ︷|N |∑

j=1

∑

(A→α)∈ΓAj

N(A → α, dx)N(ai, α)

∑x∈Ω |x|

=

∑x∈Ω N(ai, x)∑

x∈Ω |x| .

De nuevo cabe destacar que el corolario anterior pone de manifiesto como unaGIP estimada con un algoritmo basado en la expresión (3.2) captura desde el primermomento la mayor parte de la información estocástica presente en la muestra.

47

Tanto el Teorema 3.4.1, como el Corolario 3.4.1 pueden extenderse sin dema-siadas dificultades para una GIP Gp cuyas probabilidades han sido estimadas apartir de una muestra Ω de L(G) utilizando el algoritmo VS mediante la transfor-mación (3.8). Los siguientes teorema y corolario los enunciamos sin demostración(ver la demostración en el Apéndice B).

Teorema 3.4.2. Sea Gp = (G, p) una GIP y sea Ω una muestra de L(G). SiGp = (G, p) es una GIP obtenida a partir de Gp aplicando la transformacióndescrita en (3.8), entonces Gp es consistente.

En la definición 3.1 es importante destacar que la longitud media de las deri-vaciones es dependiente del conjunto de ellas utilizado en la estimación. Por ello,para demostrar la relación entre las propiedades estocásticas de la muestra y aque-llas que finalmente quedan capturadas en la gramática estimada, es convenienteredefinir 3.1 de manera que sólo se considere la información contenida en las deri-vaciones utilizadas en el aprendizaje.

Definición 3.4. Dada una GIP Gp y una muestra Ω de L(G), se define la longitud

media de la mejor derivación de Ω, LMDGp(Ω), como:

LMDGp(Ω) =

∑x∈Ω |dx|

λ.

Corolario 3.4.2. Sea una GIP Gp = (G, p) y sea Ω una muestra de L(G). Si Gp =(G, p) es una GIP que ha sido obtenida a partir de Gp aplicando la transformacióndescrita en (3.8), entonces se cumplen las siguiente ecuaciones:

LED(Gp) = LMDGp(Ω),

LEC(Gp) = LMC(Ω),

d(ai, L(Gp)) = δ(ai,Ω) ∀ai ∈ Σ.

3.5. Conclusiones

En este capítulo se han revisado dos algoritmos de estimación de las GIP: elalgoritmo IO, que permite maximizar localmente la verosimilitud de la muestra, yel algoritmo VS, que maximiza localmente la verosimilitud de la mejor derivaciónde la muestra. El primero tiene el inconveniente de necesitar un elevado número deiteraciones para converger. En el segundo, el número de iteraciones que necesita

48

hasta converger es significativamente menor que el que necesita el algoritmo IO.El algoritmo VS puede utilizarse para aproximar la verosimilitud de una muestra.Sin embargo, en la práctica, el valor de la función de verosimilitud alcanzado coneste algoritmo es, en general, bastante menor que el alcanzado con el algoritmo IO.

Se han estudiado algunas características propias del proceso de estimación deambos algoritmos, y se ha visto cómo la diferencia entre los logaritmos de lasfunciones maximizadas por ambos algoritmos puede ser acotada por una funciónlineal de la muestra y logarítmica del número de no terminales. Se ha comprobadoempíricamente como esta diferencia disminuye significativamente en ambos algo-ritmos durante el proceso de estimación. Otros experimentos y resultados similaresa los presentados aquí pueden encontrarse en [SBC96].

Así mismo se ha estudiado el problema de la consistencia de los modelos es-timados con ambos algoritmos y se ha demostrado que ambos dan lugar a unagramática consistente. El cumplimiento de la propiedad de consistencia nos ha per-mitido, además, estudiar una serie de características estocásticas, que relacionan ellenguaje generado por una GIP, con la muestra a partir de la cual se han estimadosus probabilidades.

Es importante destacar el resultado obtenido en este capítulo acerca de la con-sistencia de los modelos estimados con los algoritmo IO y VS. El cumplimiento deesta propiedad es especialmente importante ya que permite hacer uso de estos mo-delos para representar lenguajes incontextuales probabilísticos. Otra consecuencia,incluso más importante de este resultado, es que permite confirmar la correcciónde los propios algoritmos de estimación. La resultados comentados aquí, aparecendetallados en otros trabajos presentados por el autor en [SB96, SB97b]

La propiedad de consistencia demostrada aquí también aparece demostrada deotra forma en [CG98], donde se hace mención al trabajo [SB97b]. Así mismo,trabajos recientes estudian el cumplimiento de esta propiedad para otro tipo demodelos [Sar98], poniendo de manifiesto la importancia de la misma.

Capítulo 4

Estimación de las GIP a partir deun conjunto de derivaciones

En este capítulo se presentan y estudian nuevas propuestas para la estimaciónde las GIP, que hacen uso de un conjunto específico de derivaciones de cada ca-dena de la muestra para el proceso de aprendizaje. Este conjunto de derivacionespuede formarse a partir de las k mejores derivaciones de cada cadena, o bien, a par-tir de cierta información estructural presente en la muestra. Se demostrará que lasgramáticas estimadas con estos algoritmos cumplen la propiedad de consistencia,tal como sucedía con los algoritmos que vimos en el capítulo anterior. Por último,se presenta un experimento completo sobre una base de datos real, el conjunto dedatos Penn Treebank. Los resultados obtenidos ilustran como estos algoritmos pue-den ser de gran interés práctico frente a los algoritmos clásicos en tareas complejas.

4.1. Introducción

En el Capítulo 3 se ha visto como la utilización del algoritmo IO para maxi-mizar la verosimilitud de la muestra se caracteriza porque hace uso de todas lasderivaciones presentes en la misma, por lo que, en la estimación de los modelos, seconsidera toda la información de la que es posible disponer. Este algoritmo permiteobtener unos modelos que ofrecen, en general, buenos resultados. Sin embargo, suuso presenta un importante inconveniente, que se acentúa especialmente en pro-blemas reales: el elevado número de iteraciones que son necesarias para converger.Alternativamente, puede utilizarse el algoritmo VS como una forma de aproximardicha verosimilitud. Este algoritmo considera únicamente la información obtenidade la mejor derivación, y tiene la ventaja de necesitar en la práctica menos iteracio-nes para converger. Sin embargo, las GIP estimadas con el algoritmo VS ofrecen,en general, peores resultados. Se ha visto como estos algoritmos proceden de for-ma análoga, acumulando la masa de probabilidad de las cadenas en un reducidonúmero de derivaciones. Estas consideraciones nos llevan a plantear algoritmos deestimación más eficientes para aproximar la verosimilitud de la muestra.

49

50

La idea general de los algoritmos que se van a proponer es utilizar un com-promiso intermedio entre los algoritmos IO y VS, considerando para ello un sub-conjunto reducido de derivaciones entre los dos extremos. De esta forma, se pre-tende obtener una rápida convergencia, pero incorporando más información que laque utiliza el algoritmo VS. En esta tesis se van a estudiar dos métodos para se-leccionar el subconjunto de derivaciones: elegir las derivaciones a partir de ciertainformación estructural definida sobre la muestra, o bien, eligiendo las k mejoresderivaciones de cada cadena de la muestra.

Respecto a la propuesta de elegir las derivaciones a partir de cierta informaciónestructural definida sobre la muestra, en [PS92] se propuso una versión modifica-da del algoritmo IO que hace uso de muestras analizadas, etiquetadas y conve-nientemente parentizadas para el proceso de aprendizaje. Este algoritmo consideraúnicamente las derivaciones compatibles con el análisis que subyace en la parenti-zación. El objetivo de esta propuesta es doble: mejorar la velocidad de convergen-cia del algoritmo, y obtener modelos mejor entrenados. La parentización definidasobre la muestra pretende restringir la estimación utilizando únicamente las deri-vaciones relevantes, evitando la redundancia excesiva que se da en el algoritmo IO.Los resultados reportados en [PS92] muestran como efectivamente la convergen-cia de este algoritmo es significativamente más rápida que el algoritmo IO, y quelos modelos obtenidos están estructuralmente mejor aprendidos. Dos restriccionesimportantes de esta propuesta son la necesidad de disponer de grandes conjuntosde datos parentizados, y que el número de derivaciones hasta la convergencia con-tinua siendo elevado. En este capítulo se va a presentar un método alternativo deestimación basado en la propuesta de [PS92]. Este nuevo método consiste en utili-zar únicamente la mejor derivación compatible con la parentización definida sobrela muestra. La motivación de esta propuesta es tratar de mejorar la velocidad deconvergencia de la propuesta de [PS92], tal como se hace con el algoritmo VS res-pecto al algoritmo IO, y obtener unos modelos mejor estimados que los obtenidoscon el algoritmo VS.

En cuanto a la alternativa de elegir las k mejores derivaciones de cada cadena,vamos a presentar un algoritmo para la estimación que considera únicamente estesubconjunto de derivaciones [SB98a]. La motivación de esta propuesta es conse-cuencia, principalmente, de la forma en que procede en la práctica el algoritmoIO. Vimos empíricamente como este algoritmo tiende a acumular progresivamen-te la probabilidad de cada cadena en un reducido número de derivaciones. Estonos lleva a plantear la hipótesis de que las derivaciones más probables son las quecondicionan en mayor medida el comportamiento del algoritmo y la bondad delos modelos. El inconveniente de esta propuesta respecto al algoritmo IO es quese considera menos información en el proceso de aprendizaje. La ventaja es quela convergencia puede ser más rápida. Observemos que un algoritmo basado enlas k mejores derivaciones considera más información para el aprendizaje que elalgoritmo VS y, consecuentemente, es de esperar que las GIP estén mejor apren-didas. Con esta propuesta no es necesario incorporar información deductiva en lamuestra, a diferencia de como sucedía en [PS92], lo que facilita su aplicación en

51

tareas reales. Sin embargo, el no utilizar información estructural puede dar lugar amodelos peor entrenados.

Puesto que ambas propuesta consideran un subconjunto de derivaciones en elproceso de estimación, en la siguiente sección, siguiendo un desarrollo similar alde la Sección 3.2, vamos a estudiar, en el marco de las Transformaciones Cre-cientes, el problema de la estimación de las GIP cuando se utiliza un subconjuntoespecífico de derivaciones. A continuación, se estudiará el problema de la consis-tencia para los métodos de estimación basados en la transformación presentada,y las características estocásticas del lenguaje generado por la GIP obtenida. Final-mente se presentará una experimentación completa sobre el conjunto de datos PennTreebank para ilustrar las posibilidades de las diferentes propuestas.

4.2. Estimación de las GIP a partir de un subconjunto dederivaciones

Sea Gp = (G, p) una GIP, Ω una muestra de L(G) y ∆x ⊆ Dx un conjunto dederivaciones para cada cadena x ∈ L(G). Definimos la siguiente función:

Pr(Ω,∆Ω | Gp) =∏

x∈Ω

Pr(x,∆x | Gp), (4.1)

como la probabilidad de generar la muestra con el conjunto de derivaciones ∆x

de cada cadena x ∈ Ω. Esta función es un polinomio definido en los términos delTeorema 3.1.1, y por tanto podemos definir una transformación ∀(A → α) ∈ Psimilar a la descrita para el algoritmo IO. Desarrollando de forma análoga se llegaa la siguiente expresión:

p(A → α) =

∑x∈Ω

1Pr(x,∆x|Gp)

∑dx∈∆x

N(A → α, dx)Pr(x, dx | Gp)∑

x∈Ω1

Pr(x,∆x|Gp)

∑dx∈∆x

N(A, dx) Pr(x, dx | Gp). (4.2)

Esta transformación permite obtener una GIP Gp = (G, p) tal que Pr(Ω,∆Ω |Gp) > Pr(Ω,∆Ω | Gp) excepto si p = p. Puede verse que la trasformación (4.2)coincide con la (3.4) cuando ∆x tiene el máximo número de derivaciones de x,mientras que coincide con (3.8) cuando ∆x tiene sólo la mejor derivación de entretodas las posibles de la cadena x.

Es importante destacar en esta expresión que cada valor de k define una fun-ción, por lo que más que una transformación, se puede decir que es una familia detransformaciones.

4.2.1. Propiedades de las GIP estimadas a partir de un subconjuntode derivaciones: consistencia de los modelos

En esta sección vamos a demostrar que las GIP estimadas con cualquier al-goritmo basado en la transformación (4.2) son consistentes. El cumplimiento de

52

la propiedad de consistencia por parte de estos modelos nos permitirá derivar unaserie de propiedades estocásticas similares a las que ya vimos en el capítulo ante-rior. Estas propiedades relacionan el lenguaje que es capaz de generar la gramáticacon la muestra a partir de la cual se han estimado sus probabilidades. El siguienteteorema establece la propiedad de consistencia para las GIP estimadas a partir deun subconjunto de derivaciones.

Teorema 4.2.1. Sea Gp = (G, p) una GIP, Ω una muestra de L(G) y ∆x ⊆ Dx unconjunto de derivaciones para cada cadena x ∈ L(G). Si Gp = (G, p) es una GIPobtenida a partir de Gp aplicando la transformación descrita en (4.2), entoncesGp es consistente.

La demostración de este teorema es similar a la del Teorema 3.4.1 y se basa en de-mostrar que el número de no terminales que se introducen en un proceso generativoinfinito tiende a ser cero (puede verse la demostración completa en el Apéndice B).Así pues, cualquier GIP estimada con un algoritmo basado en esta transformaciónes capaz de representar un lenguaje probabilístico, y por tanto, podemos utilizardicha transformación en los problemas reales que se pretende abordar.

Así mismo, cualquier GIP estimada con la transformación (4.2) captura granparte de la información estocástica presente en la muestra, al igual que sucedía conlos algoritmos IO y VS. A continuación comentamos las propiedades estocásticasrecogidas por la GIP durante el proceso de estimación.

La primera de las propiedades que vamos a mencionar está referida a la longi-tud media de las derivaciones. Para ello, es necesario redefinir la expresión de ladefinición 3.1 de forma que se consideren un conjunto arbitrario de derivacionesde cada cadena.

Sea una GIP Gp, una muestra Ω de L(G), y ∆x ⊆ Dx un subconjunto dederivaciones para cada cadena x ∈ L(G). La longitud media de las derivacionesdel conjunto ∆x de las cadenas de la muestra, LMDGp(Ω), se define como:

LMDGp(Ω) =

∑x∈Ω

1Pr(x,∆x|Gp)

∑dx∈∆x

Pr(x, dx | Gp)|dx|λ

,

donde λ es el número de cadenas de Ω.El siguiente corolario relaciona una GIP estimada con la transformación (4.2)

con algunas características estocásticas de la muestra.

Corolario 4.2.1. Sea una GIP Gp = (G, p), Ω una muestra de L(G) y ∆x ⊆ Dx

un conjunto de derivaciones para cada cadena x ∈ L(G). Si Gp = (G, p) es unaGIP que ha sido obtenida a partir de Gp aplicando la transformación descrita en

53

(4.2), entonces se cumplen las siguiente ecuaciones:

LED(Gp) = LMDGp(Ω),

LEC(Gp) = LMC(Ω),

d(ai, L(Gp)) = δ(ai,Ω) ∀ai ∈ Σ.

La demostración de este corolario es similar a la del Corolario 3.4.1 y puedeverse en el Apéndice B.

Este corolario permite evidenciar que tanto este algoritmo, como los algorit-mos IO y VS, capturan la información estocástica que aparece únicamente en lasderivaciones que se utilizan en el proceso de estimación.

Como ya sucedía con las transformaciones definidas para los algoritmos IOy VS, cabe destacar, en primer lugar, que los propiedades anteriores se cumplenpara cualquier GIP independientemente de que la gramática esté en FNC o no.Y en segundo lugar, que la propiedad de consistencia se cumple desde la primeraiteración, con lo que cualquier GIP estimada con este algoritmo genera un lenguajeprobabilístico.

Como conclusión, el Teorema 4.2.1 nos garantiza que los modelos estimadoscon la Transformación (4.2) son correctos. Basada en dicha transformación, en lassiguientes secciones vamos a presentar diferentes algoritmos de estimación queconsideran un subconjunto de derivaciones para el proceso de aprendizaje.

4.3. El algoritmo kVS

Siguiendo el esquema de la Figura 3.1 y a partir de la transformación (4.2), sepuede definir un algoritmo tal que ∆x se obtiene por medio de las k mejores deri-vaciones de cada cadena. Ésta es la misma estrategia seguida por el algoritmo VS,por lo que le denominaremos algoritmo kVS. Este algoritmo parte de una gramáti-ca inicial y siguiendo un proceso iterativo, se calculan en cada paso las k mejoresderivaciones de cada cadena de la muestra. Para las reglas que aparecen en estasderivaciones se acumulan los valores que aparecen en el numerador y denomina-dor de la expresión (4.2). Al final de cada iteración se aplica la transformación.Este proceso iterativo continua hasta alcanzar un óptimo local de la función queestá siendo optimizada. Observemos que de forma análoga a lo que sucedía conel algoritmo VS, aquellas reglas que no aparecen en alguna de las k mejores de-rivaciones pasan a tener probabilidad nula, por lo que no son consideradas en lassiguientes iteraciones. Esto provoca una severa reducción del espacio de búsquedaque facilita la rápida convergencia del algoritmo.

En este algoritmo cabe destacar dos aspectos: en primer lugar, nótese que laconsistencia de los modelos obtenidos está garantizada desde la primera iteración,

54

como se ha demostrado en la sección anterior. En segundo lugar, como ya hemoscomentado, cada valor de k define una función diferente. En particular, hay quetener en cuenta, que pueden existir cadenas con menos de k derivaciones, por loque k es en realidad un cota superior del número de derivaciones utilizado.

El algoritmo kVS introduce dos problemas que merecen especial atención. Unode ellos es el cómputo de las k mejores derivaciones de cada cadena x. Este cálculorequiere un cuidadoso estudio puesto que afecta directamente al coste del algorit-mo. Otro problema que introduce es el estudio del comportamiento del algoritmoen función del valor de k elegido. Este aspecto es importante para determinar unvalor de k adecuado. En los siguientes apartados tratamos estos temas con detalle.

4.3.1. Costes del algoritmo kVS

Una cuestión fundamental de este algoritmo es el cálculo de las k mejoresderivaciones de una cadena. En este punto se describe su cálculo y sus costes parasu aplicación en el algoritmo kVS. Un estudio general en profundidad del cómputode las k mejores soluciones a problemas de Programación Dinámica pueden verseen [Mar94].

La idea básica para computar las k mejores derivaciones de una cadena consisteen calcular en cada celda de la tabla de análisis (esto es, para cada subproblema)un conjunto de k mejores soluciones, que se organizan habitualmente como unacola de prioridad. Cada solución representa un análisis diferente de una subcadena.Inicialmente sólo se incluye la mejor solución que se obtiene mediante el algoritmode Viterbi. Las siguientes soluciones se obtienen bajo demanda. Para obtener lasiguiente mejor derivación deberemos volver a visitar las celdas de la tabla deanálisis que han proporcionado la mejor derivación anterior (si la GIP está en FNCel número de celdas que se visitan es O(|x|)), desestimar la solución utilizada yobtener una nueva. Para realizar esto de manera eficiente, en la segunda visita acada celda se crea un conjunto con las k mejores soluciones del siguiente modo:

si el conjunto asociado a la celda tiene sólo la mejor solución, entonces segeneran todas las posibles soluciones repitiendo la maximización que apa-rece en la expresión (2.1) y sólo se guardan las k mejores soluciones. Estosignifica que en cada celda tendremos un coste O(|x||P |

|N | log k). La mejorsolución (que ya ha sido considerada con anterioridad) se sustituye por lasiguiente mejor solución consultando recursivamente las celdas de las cualesdependía.

Si el conjunto asociado a la celda tiene más de una solución, se sustituye lamejor solución por una nueva combinando mejores soluciones de las celdasde las cuales dependía. Esto supone un coste en cada celda O(log k).

Puesto que el número de celdas de la tabla es |x|2

2 |N |, entonces, si se llegan avisitar todas las celdas para obtener las k mejores derivaciones, tendríamos un costeO(|x|3|P | log k) para el primer punto. Puesto que obtener cada nueva solución

55

significa visitar 2|x| − 1 celdas (que es el número de reglas de una derivación de lacadena), entonces obtener las k mejores soluciones en el peor de los casos puedesignificar un coste de O(|x|3|P | + k|x| log k + |x|3|P | log k). En el mejor de loscasos el coste temporal del algoritmo es O(|x|3|P | + k + |x||P |

|N | ).

El coste espacial en el peor de los casos es O(k|x|2(|N | + |Σ|)). La constantek en este coste corresponde al número de soluciones a guardar como mucho encada celda de la tabla de análisis. En el mejor de los casos, el coste espacial delalgoritmo es O(k + |x|2(|N | + |Σ|)).

Es importante destacar que en la práctica la obtención de las k mejores solucio-nes está más cerca de su caso mejor que de su caso peor como ilustraremos en losexperimentos que se presentan al final del capítulo. Esto es debido a que la diferen-cia entre una derivación y la siguiente está habitualmente en una pocas reglas, porlo que las celdas diferentes que se visitan de una derivación a la siguiente son real-mente pocas. En tal caso, los valores que puede tomar k sin superar excesivamenteel coste del algoritmo VS pueden ser bastante elevados, lo que da bastante flexibi-lidad al algoritmo kVS. Nuestra hipótesis a la hora de plantear el algoritmo kVSes que, teniendo en cuenta el comportamiento del algoritmo IO, sólo es necesarioconsiderar valores pequeños de k.

4.3.2. Relación entre los modelos estimados en función de k

En la expresión (4.2), cada valor de k supone definir una transformación dife-rente, por lo que cabe plantearse qué relación existe entre los modelos estimadoscon el algoritmo kVS para diferentes valores de k. Intuitivamente podría pensarseque el valor de la función a optimizar crece a medida que crece k, y que en conse-cuencia los modelos están mejor estimados. Sin embargo esto no es necesariamentecierto tal como vamos a mostrar con un contraejemplo.

Sea la GIP Gp = (S,A, 0, 1, S, S 0,25−→ SS, S0,25−→ AS, S

0,25−→ 0, S0,25−→

1, A1−→ 1) y sean las derivaciones de la Figura 4.1 las tres mejores derivaciones

de la cadena 100. Sean ∆′

x, ∆′′

x y ∆′′′

x los conjuntos formados por la mejor deriva-ción, las dos mejores derivaciones y las tres mejores derivaciones, respectivamente,por lo que se cumple que Pr(x,∆

′

x | Gp) < Pr(x,∆′′

x | Gp) < Pr(x,∆′′′

x | Gp).

1

A

0

S

0

S JJ

S

## JJ

S

1

A

0

S JJ

S

0

Sc

c

S

1

S

0

S

0

S JJ

S

## JJ

S

Figura 4.1: De izquierda a derecha tenemos los tres mejores árboles de análisis dela cadena 100. El primero tiene una probabilidad 0,00391, el segundo 0,00391 y eltercero 0,00098.

56

Supongamos que utilizamos ∆′

x, ∆′′

x y ∆′′′

x para estimar separadamente la GIPGp con la expresión (4.2), de manera que obtenemos respectivamente G

′

p, G′′

p y

G′′′

p . A partir de estos nuevos modelos, calculamos Pr(x,∆′

x | G′

p) = 0,0156,

Pr(x,∆′′

x | G′′

p) = 0,03125 y Pr(x,∆′′′

x | G′′′

p ) = 0,02802 que coincide con elvalor de la función a optimizar. Como se puede observar aumentando k no implicanecesariamente que el valor de la función (4.1) aumenta.

La razón por la que sucede esto es que al considerar más derivaciones en elproceso de estimación, pueden introducirse derivaciones con baja probabilidad,que afectan negativamente (decrementando su probabilidad) a reglas importantesde las mejores derivaciones, cuya probabilidad era más alta utilizando menos deri-vaciones. Así, en el ejemplo, la regla S −→ AS, que es un regla importante (conalta probabilidad) en las dos mejores derivaciones, pasa a tener probabilidad 0,25cuando se utilizan dos derivaciones en la estimación, mientras que pasa a tenerprobabilidad 0,216 cuando se utilizan tres derivaciones.

Este resultado tiene consecuencias negativas ya que impide fijar un valor de ka priori. Sin embargo, en la práctica se observa que los modelos tienden a mejorara medida que se utiliza una mayor número de derivaciones en el proceso de estima-ción. A continuación se van a presentar diferentes ejemplos en los cuales podremosobservar esta tendencia.

4.3.3. Estudio empírico del comportamiento del algoritmo kVS

En esta sección presentamos dos experimentos que pretenden ilustrar algunascaracterísticas del comportamiento en la práctica del algoritmo kVS. En primerlugar, presentamos experimentos sintéticos realizados con la tarea de los palíndro-mos, tal como hemos venido realizando a lo largo de la tesis. En estos experimentoscompararemos los diferentes algoritmos descritos hasta ahora. A continuación pre-sentamos la experimentación realizada con una tarea pseudo-natural más compleja.En esta tarea, la aplicación del algoritmo IO es inviable dado el elevado coste com-putacional del proceso de estimación, por lo que el algoritmo kVS sólo se contrastacon el algoritmo VS.

Experimentos con la tarea de los palíndromos

Como ya sucediera con los algoritmos IO y VS, la Transformación Crecienteen la cual se basa el algoritmo kVS aporta poca información acerca del compor-tamiento del proceso iterativo de estimación, salvo su convergencia y la localidadde la solución alcanzada. En este apartado vamos ilustrar con un ejemplo como secomporta este algoritmo durante el proceso de estimación. Esto nos permitirá, porun lado, poner de manifiesto la similitud con los algoritmos IO y VS, y por otro,mostrar como el algoritmo kVS ofrece en la práctica buenos resultados inclusopara valores pequeños de k.

El experimento sintético utilizado es el de los palíndromos, que ya describimosen la Sección 3.2.3. A partir de la misma gramática inicial de aquel experimento, y

57

con la muestra de 100 cadenas, se estimó una GIP con diferentes valores de k, estoes, con diferente número de derivaciones. Con esta experimentación pretendemosestudiar varios aspectos del algoritmo kVS: la velocidad de convergencia, la bon-dad de los modelos estimados, y la acumulación de la probabilidad de las cadenasen las mejores derivaciones.

Respecto a los dos primeros aspectos, en la Figura 4.2 puede verse la evoluciónde la función a optimizar para diferentes valores de k y su relación con los algorit-mo IO y VS. En las Figuras A.6 y A.16 del Apéndice A pueden consultarse otrosejemplos con las otras dos semillas.

PSfrag replacements

IO

V S

k = 5

k = 10

k = 15

Iteraciones180160140120100806040200

-1400

-1300

-1200

-1100

-1000

-900

-800

-700

-600

Figura 4.2: Evolución de las funciones optimizadas por el algoritmo kVS en fun-ción de k, y su relación con las funciones optimizadas por los algoritmos IO yVS.

En esta figura puede observarse como, en general, la función (4.1) mejora amedida que crece el valor de k; así mismo, podemos apreciar como el algoritmoconverge más lentamente a medida que aumenta k, aunque siempre más rápida-mente que el algoritmo IO. Algo similar puede observarse en los experimentosreportados en las figuras mencionadas del Apéndice A y en [SB98b, SB98a]. Estoconfirma que el algoritmo kVS puede ser una buena alternativa al algoritmo VSpara aproximar la verosimilitud de la muestra.

Por otro lado, cabe destacar como este algoritmo se comporta de forma similara los algoritmos IO y VS durante el proceso iterativo, acumulando la probabilidadde las cadenas en las mejores derivaciones. Tal como se puede ver en la Tabla 4.1,para el experimento comentado, estos valores estaban próximos al 100 % para losdiferentes valores de k. Resultados análogos pueden consultarse en el Apéndice A(Tablas A.2 y A.4) para las otras semillas. Esto viene a confirmar nuestra hipóte-sis de que un pequeño conjunto de derivaciones recogen, prácticamente, toda la

58

información estocástica de cada cadena.

Cuadro 4.1: Relación entre la masa de probabilidad acumulada en el conjunto decadenas no repetidas de la muestra (columna mdp) y el porcentaje de la masa deprobabilidad acumulada en la 5 mejores derivaciones (columna 5md) cuando seutilizan diferente número de derivaciones en la estimación. Los resultados que semuestran son después de la convergencia.

núm. de derivaciones mdp 5md ( %)

VS 0.032136 97.2 %k = 5 0.069506 99.3 %k = 10 0.139859 99.7 %k = 15 0.138838 99.7 %

IO 0.662 98.3 %

Experimentos con la tarea de Feldman

En los experimentos anteriores se ha visto como el algoritmo kVS muestraalgunas características atractivas para su utilización como método de estimación:una rápida convergencia y unos modelos adecuadamente estimados. Estas carac-terísticas nos sugieren la posibilidad de aplicar dicho algoritmo en tareas realescomplejas en las cuales es inviable aplicar el algoritmo IO. Sin embargo, antes deestudiar su aplicación en una tarea real, vamos a estudiar si mantiene estas pro-piedades en una tarea más compleja. Para poder mantener los parámetros de laexperimentación bajo control, se optó por trabajar con una tarea sintética pseudo-natural. La tarea elegida fue la tarea de Feldman [FLSW90], utilizada en diferentestrabajos [Dup96], y que describimos a continuación.

La tarea de Feldman consiste en frases que describen escenas en dos dimensio-nes que implican diferentes objetos geométricos de diferente forma, color y tama-ño, y localizados en diferentes posiciones relativas. En la tarea original, se utilizan19 símbolos terminales, aunque para esta experimentación se agruparon en 9 cate-gorías gramaticales. Esta modificación permitía reducir el esfuerzo computacionaly mantenía la mayor parte de la información estructural. En la Figura 4.3. puedeverse la gramática utilizada para la generación de las cadenas. La gramática origi-nal fue modificada para que generase un lenguaje infinito.

Para este experimento se generó un conjunto de entrenamiento (Tr) y uno detest (Ts) cuyas características se describen en la Tabla 4.2. La perplejidad1 delconjunto de test con un modelo de trigramas era 1.69.

1Para el cómputo de esta expresión y otras que aparecen más adelante se utilizó la herramienta desoftware descrita en [Ros95] (la versión 2.04 del mismo está accesible públicamente en la direcciónhttp://svr-www.eng.cam.ac.uk/∼prc14/toolkit.html).

59

S → NP VP 0,35 NP1 → size shade obj 0,4S → det NP1 0,39 NP1 → obj 0,1S → det NP1 and NP 0,26 VP → vi REL NP 0,7NP → det NP1 0,6 VP → vt NP 0,3NP1 → det NP1 and NP 0,4 REL → far rel1 0,2NP1 → shade obj 0,2 REL → rel1 0,8NP1 → size obj 0,3

Figura 4.3: GIP en FNC utilizada en la tarea de Feldman para generar el conjuntode datos. Esta gramática es consistente.

Cuadro 4.2: Características del los conjuntos de entrenamiento (Tr) y de test (Ts)utilizados en el experimento con la tarea de Feldman.

Conjunto Núm. de Núm. de cad. Long. Desv. Cadena Cadenacadenas sin repetir media típica más corta más larga

Tr 20,000 2,730 8.84 6.29 2 40Ts 10,000 1,723 8.92 6.39 2 39

Para la experimentación se construyó una GIP inicial que tenía el máximo nú-mero de reglas que pueden construirse con 9 terminales y 19 no terminales. Lasprobabilidades iniciales se asignaron de forma aleatoria. A partir de esta GIP ini-cial se estimó una GIP con el algoritmo kVS, para diferentes valores de k.

Un problema presente en cualquier proceso de estimación es la evaluación delos modelos obtenidos. En los problemas que vamos abordar de ML, es habitualutilizar la perplejidad por palabra (PP) [BJM83, Jel98] para evaluar la bondad delas gramáticas. Una interpretación intuitiva de esta medida es considerarla como lacapacidad del modelo para tratar los eventos que se van produciendo en el procesode análisis. Valores próximos a cero indican que el modelo tiene mayor capacidady por tanto es mejor. Esta medida se evalúa sobre un conjunto de datos que no hansido utilizados en el proceso de entrenamiento denominado conjunto de test (Ts).Cuando el modelo es una GIP esta medida se define como [Dup96]:

PP (Ts,Gp) = e−∑

x∈Ts log Pr(x|Gp)∑x∈Ts |x| .

Observemos que cuando Ts es exactamente el conjunto de entrenamiento, la ma-ximización de la verosimilitud de la muestra hace decrecer esta medida. Por tanto,si el conjunto Ts sigue una distribución similar a la del conjunto de entrenamiento,entonces es de esperar que esta medida tienda a decrecer.

En los experimentos realizados sobre la tarea de Feldman se estudiaron dosaspectos a los que se hecho mención al presentar el algoritmo kVS: el coste delalgoritmo, y la dependencia del mismo respecto a k.

60

Al hablar del coste del algoritmo kVS, hemos comentado que en la práctica elcoste de obtener las k mejores derivaciones de cada cadena se aproxima más a sucaso mejor que a su caso peor. En tal caso el coste en cada iteración es poco más queel coste del algoritmo VS. En la Figura 4.4 puede verse el tiempo de cada iteraciónen el experimento comentado para el algoritmo VS y kVS (k = 7). Puede apreciar-se que el tiempo disminuye drásticamente a partir de la primera iteración cuandodesaparecen muchas reglas por tener probabilidad nula. Nótese como el tiempo deambos algoritmos es bastante similar. Este hecho favorece nuestras expectativasacerca del algoritmo kVS, ya indica que pueden utilizarse mayores valores de ksin sobrepasar excesivamente el coste del algoritmo VS. Destacar en estos experi-mentos que no se estimó con el algoritmo IO dado el elevado esfuerzo de cómputoque requería.

PSfrag replacements

Iteraciones

Seg

undo

s

VSk = 7

201816141210864200

35000

30000

25000

20000

15000

10000

5000

Figura 4.4: Tiempo consumido en la 20 primeras iteraciones para el algoritmo VSy el algoritmo kVS (k = 7). Los experimentos se realizaron en una máquina HP9000-735 con el sistema operativo Unix Versión B.10.01.

Asimismo, hemos comentado que la elección de valores de k mayores no ga-rantiza necesariamente la obtención de modelos mejor estimados. Sin embargo, enla práctica si se observa esta tendencia. En la Tabla 4.3 puede verse la perplejidadsobre el conjunto de test. Nótese que para valores relativamente pequeños de k losporcentajes de mejora de la perplejidad son bastantes significativos. Esto viene aconstatar que valores de k progresivamente mayores puede permitir la obtención demodelos mejor entrenados. Puede apreciarse también, que el porcentaje de mejoratiende a decrecer a medida que crece el valor de k.

De forma similar a como sucedía con los algoritmo VS y IO, el algoritmo kVSintroduce interesantes problemas relacionados con el proceso de estimación. En

61

Algoritmo Perplejidad Mejora ( %)

VS 4.22kVS (k = 3) 3.93 6.87 %kVS (k = 5) 3.83 9.24 %kVS (k = 7) 3.76 10.90 %

Cuadro 4.3: Perplejidad del conjunto de test para los modelos obtenidos con losdiferentes algoritmos. La tercera columna representa el porcentaje de mejora conrespecto al algoritmo VS.

la sección que sigue vamos a estudiar la relación que existe entre las diferentesfunciones maximizadas por los algoritmos IO, VS y kVS para un modelo dado.

4.4. Relación entre las funciones maximizadas por los al-goritmos IO, VS y kVS

Similarmente al algoritmo VS, el algoritmo kVS puede considerarse como unapropuesta para aproximar la verosimilitud de una muestra cuando no es posibleaplicar el algoritmo IO. La utilización de este algoritmo introduce la necesidad deestudiar la relación entre los algoritmos IO, VS y kVS, y más concretamente, lasfunciones que maximizan, de manera similar a como se hizo en el Capítulo 3.

Primeramente vamos estudiar la diferencia entre los logaritmos de las funcio-nes optimizadas con el algoritmo VS y kVS (definiciones 2.18 y 2.20). De estaforma trataremos de estudiar el interés de utilizar el algoritmo kVS frente al al-goritmo VS. A continuación estudiaremos la diferencia entre los logaritmos de lasfunciones que optimizan los algoritmos IO y kVS (definiciones 2.17 y 2.20). Es-to nos permitirá estudiar el inconveniente de utilizar el algoritmo kVS frente alalgoritmo IO.

Relación entre las funciones maximizadas por los algoritmos VS y kVS

Como en los algoritmo IO y VS, la diferencia entre las funciones maximizadascon los algoritmos VS y kVS puede acotarse en función del número de derivacionesutilizado en cada función, es decir, en función de k. Sea ∆x el conjunto de las kmejores derivaciones de la cadena x. Entonces tenemos que:

ln maxdx∈Dx

Pr(x, dx | Gp) ≤ ln∑

dx∈∆x

Pr(x, dx | Gp)

≤ ln k + ln maxdx∈∆x

Pr(x, dx | Gp).

De esta forma tenemos que:

ln Pr(x,∆x | Gp) − ln Pr(x | Gp) ≤ ln k.

62

Si extendemos esto para una muestra, y suponemos que k es igual para todas lascadenas, entonces el resultado que obtenemos es:

ln Pr(Ω,∆Ω | Gp) − ln Pr(Ω | Gp) ≤ |Ω| ln k. (4.3)

Como ya hicimos en la sección 3.3, esta cota superior puede utilizarse para esti-mar las diferencias de verosimilitud en la estimación probabilística, en caso de queexista un algoritmo eficiente para obtener máximos globales de las correspondien-tes funciones objetivos. Para ello, hacemos la siguiente definición:

p ∗ = arg maxp

Pr(Ω,∆Ω | Gp), (4.4)

y la correspondiente gramática G∗p = (G, p ∗). De esta forma, haciendo uso de

(3.12) y de (4.3) podemos obtener los siguientes resultados:

0 ≤ ln Pr(Ω,∆Ω | G∗p) − ln Pr(Ω | G∗

p) ≤ |Ω| ln k,

0 ≤ ln Pr(Ω,∆Ω | G∗p) − ln Pr(Ω,∆Ω | G∗

p) ≤ |Ω| ln k.

Por tanto, para un algoritmo ideal que permitiese calcular el máximo global de lasdos funciones, la diferencia entre ellas está acotado superiormente por una funciónlineal de la muestra y una función logarítmica de k. Sin embargo, hay que teneren cuenta que tanto el algoritmo VS como el kVS no garantizan que alcanzan unmáximo global de las respectivas funciones objetivo. Por tanto, el comportamientode los algoritmo y las diferencias entre las funciones únicamente podrían estudiarsede forma empírica para comprobar qué sucede en la práctica.

A continuación vamos a reproducir unos experimentos similares a los presenta-dos en el capítulo anterior, con el ejemplo de los palíndromos. Sobre este conjuntode datos se calcularon las funciones descritas, y la diferencia entre ambas cuandose estimó la gramática con el algoritmo kVS. En la Figura 4.5 puede observarseque la función maximizada por el algoritmo VS crece durante el proceso iterativo.

En la Figura 4.6 puede verse como la diferencia entre la dos funciones es bas-tante menor que la cota teórica. Esta diferencia, sin embargo, no es tan grandecomo sucedía entre los algoritmos IO y VS, puesto que aquí la diferencia del nú-mero de derivaciones entre una transformación y otra es exactamente k, y no unacota superior. Para el ejemplo que se presenta, la diferencia en la práctica suponíaun 26% respecto a la cota teórica después de la última iteración.

Relación entre las funciones maximizadas por los algoritmos IO y kVS

Las funciones maximizadas por los algoritmos IO y kVS también puede seracotada en similares términos:

lnPr(x | Gp) − ln Pr(x,∆x | Gp)

= ln(1 +

∑x∈(Dx−∆x) Pr(x, dx | Gp)∑

x∈∆xPr(x, dx | Gp)

) ≤ ln|Dx|k

≤ 2|x| ln 2|N | − ln k.

63

PSfrag replacements

ln Pr(Ω | Gp)

ln Pr(Ω | Gp)

lnPr(Ω,∆Ω | Gp)

Iteraciones20181614121086420

-3500

-3000

-2500

-2000

-1500

-1000

-500

Figura 4.5: Evolución de las funciones optimizadas cuando se utiliza el algoritmokVS (k = 10) en el proceso de estimación.

12 14 16 18

PSfrag replacements

Iteraciones

180160140120100806040

2010864200

4500

4000

3500

3000

2500

2000

1500

1000

500

Figura 4.6: En línea continua aparece la diferencia entre las dos funciones cuandose utilizó el algoritmo kVS (k = 10) en la estimación. En línea discontinua apareceel valor teórico de la cota.

La anterior expresión pone de manifiesto que la diferencia de los logaritmos delas funciones optimizadas por los algoritmo IO y kVS de las (definiciones 2.20 y2.17) está acotada por la diferencia de los logaritmos del número de derivaciones

64

utilizado en cada una de ellas, ya que la probabilidad de una derivación es comomucho 1. La expresión anterior puede extenderse para una muestra suponiendo quek es igual para todas las cadenas de forma que obtenemos el siguiente resultado:

ln Pr(Ω | Gp) − ln Pr(Ω,∆Ω | Gp) ≤ 2∑

x∈Ω

|x| ln 2|N | − |Ω| ln k. (4.5)

De igual modo a como hemos visto antes, esta cota superior puede utilizarse paraestimar las diferencias de verosimilitud en la estimación probabilística en caso deque exista un algoritmo eficiente para obtener máximos globales de las correspon-dientes funciones objetivos. Haciendo uso de (3.11), de (4.4) y de (4.5) podemos,obtener los siguientes resultados:

0 ≤ ln Pr(Ω | G∗p) − lnPr(Ω,∆Ω | G∗

p) ≤ 2∑

x∈Ω

|x| ln 2|N | − |Ω| ln k,

0 ≤ ln Pr(Ω | G∗p) − lnPr(Ω | G∗

p) ≤ 2∑

x∈Ω

|x| ln 2|N | − |Ω| ln k.

Así pues, para un algoritmo ideal que permitiese calcular el máximo global de lasdos funciones, la diferencia de los logaritmos de las dos funciones está acotadosuperiormente por una función lineal de la muestra y una función logarítmica dek. De nuevo hay que tener en cuenta que tanto el algoritmo kVS como el IO nogarantizan que se alcanza un máximo global, por lo que la diferencia entre lasfunciones maximizadas por ambos algoritmos puede ser bastante menor que lacota definida.

Para el ejemplo de los palíndromo, se calcularon las funciones descritas cuandose estimaba una gramática con el algoritmo kVS (k = 10) y la evolución de lasmisma puede consultarse en la Figura 4.5. En este caso la función maximizada conel algoritmo IO también tendía a crecer. En la Figura 4.7 puede verse la diferenciaentre las dos funciones y la cota teórica. En este caso la diferencia entre la cotateórica y la diferencia de las dos funciones es notable puesto que la cota teóricadepende de la diferencia entre el máximo número de derivaciones de la cadena y k.Para el ejemplo que se presenta la diferencia entre las dos funciones representabael 1,38% de la cota teórica al terminar el proceso de estimación.

Para concluir, destacar que la cota teórica para la diferencia entre las funcionesmaximizadas con los algoritmos VS y kVS es más ajustada que la cota teórica parala diferencia entre las funciones maximizadas con los algoritmos IO y kVS, puestoque la primera cota se expresa en un número exacto de derivaciones, mientras queen la segunda se utiliza una cota superior del número de derivaciones. Como yasucedía en los algoritmo IO y VS, la diferencia en la práctica entre las funcionesen un proceso de estimación tiende a decrecer y es significativamente menor quela cota teórica.

65

12 14 16 18

PSfrag replacements

Iteraciones

180160140120100806040

2010864200

4500

4000

3500

3000

2500

2000

1500

1000

500

Figura 4.7: En línea continua aparece la diferencia entre las dos funciones cuandose utilizó el algoritmo kVS (k = 10) en la estimación. En línea discontinua apareceel valor teórico de la cota.

4.5. Estimación de las GIP a partir de información estruc-tural

Una forma alternativa de seleccionar un subconjunto específico de derivacio-nes para estimar una GIP es haciendo uso de información estructural contenida enla muestra de aprendizaje. Una forma posible de incorporar información estructu-ral en una muestra es realizando un análisis de las cadenas (manual o automático)de acuerdo con algún criterio (principalmente sintáctico y/o semántico), y poste-riormente marcando (por ejemplo, con paréntesis) la información relevante de lascadenas. En esta sección se exploran dos algoritmos de estimación en los que elconjunto de derivaciones se elige a partir de una muestra parentizada. En primerlugar, se estudia una versión modificada del algoritmo IO propuesta inicialmenteen [PS92]. Este algoritmo considera en el proceso de estimación todas las deriva-ciones compatibles con el análisis que subyace en la parentización de la muestrade aprendizaje. Basándonos en esta idea, vamos a presentar una nueva propuestaderivada del algoritmo VS. En esta propuesta, la mejor derivación seleccionada escompatible con la parentización definida sobre la cadena. De esta forma, se pre-tende combinar las ventajas del algoritmo VS con información estructural definidasobre la muestra.

A continuación vamos presentar la notación apropiada para representar la in-formación estructural en forma de paréntesis definida sobra la muestra. Despuésdescribiremos nuevas versiones de los algoritmos IO y VS que permiten trabajarcon muestras parentizadas. Finalmente se ilustrará con un ejemplo sintético algu-

66

nas características acerca del comportamiento de estos nuevos algoritmos.

Notación con muestras parentizadas

En primer lugar, vamos introducir la notación precisa que nos permitirá tra-bajar con muestras parentizadas. La idea intuitiva consiste en definir una serie deíndices sobre la cadena, que se corresponden dos a dos, y que agrupan partes de lacadena que están relacionadas. Sobre estos índices se impone ciertas restriccionesque eviten solapamientos no deseados.

Una muestra parentizada Ω es un conjunto de pares c = (x,B) donde x esuna cadena y B es una parentización de la cadena. Dada una cadena x, llamaremosexpansión de x a un par (i, j) con 1 ≤ i ≤ j ≤ |x|, que delimita la subcadenaxi . . . xj . Una parentización B de una cadena x es un conjunto finito de expansio-nes de la cadena x tal que cualquier par de expansiones (i, j) y (k, l) cumple lacondición i ≤ k ≤ l ≤ j, o bien, k ≤ i ≤ j ≤ l. En tal caso se dice que ambasexpansiones son coherentes.

Dada una cadena parentizada, cualquier análisis que se realice sobre la cade-na debe respetar los límites definidos por los paréntesis. Los siguientes conceptosestablecen las condiciones para que una derivación de una cadena x sea compa-tible con una parentización definida sobre la misma. Para ello vamos a definir laparentización que proporciona una derivación.

Sea (x,B) una cadena parentizada y dx una derivación de x con la GIP Gp.Si la GIP no contiene símbolos inútiles entonces cada no terminal que aparece encada forma sentencial de la derivación da cuenta de una subcadena xi . . . xj de x,1 ≤ i ≤ j ≤ |x|, y define una expansión (i, j). Una derivación de x es compatiblecon B si todas las expansiones que define son coherentes en las expansiones de B.

Para adaptar los algoritmo IO y VS con muestras parentizadas se define lasiguiente función auxiliar para cada par (x,B) de la muestra:

c(i, j) =

1 si (i, j) es coherente con cualquier b ∈ B,0 en cualquier otro caso.

(4.6)

Esta función nos permitirá filtrar aquellas derivaciones, o partes de derivaciones,cuyo análisis no sea compatible con la parentización definida sobre la muestra.

El algoritmo IO con muestras parentizadas: el algoritmo IOp

A partir de la función descrita, las expresiones del algoritmo IO pueden rees-cribirse para que se ignoren las derivaciones que no son compatibles con el paren-

67

tizado [PS92]. El algoritmo Inside (ver Sección 2.4) puede reescribirse como:

ec(A < i, i >) = p(A → xi) 1 ≤ i ≤ |x|,ec(A < i, j >) =

c(i, j)∑

B,C∈N

p(A → BC)

j−1∑

k=i

ec(B < i, k >)ec(C < k + 1, j >)

1 ≤ i < j ≤ |x|.

De esta forma, Pr(x|Gp) = ec(S < 1, |x| >).Los costes de este algoritmo son los mismos que la versión sin parentizar del

algoritmo Inside, por lo que el coste temporal es O(|x|3|P |) y el coste espacial esO(|x|2|N |).

El algoritmo Outside (ver Sección 2.4) puede reescribirse de manera análoga.

f c(A < 1, |x| >) =

1 si A = S0 si A 6= S

f c(A < i, j >) =

c(i, j)∑

B,C∈N

(p(B → CA)

i−1∑

k=1

f c(B < k, j >)ec(C < k, i − 1 >)

+ p(B → AC)

|x|∑

k=j+1

f c(B < i, k >)ec(C < j + 1, k >)

1 ≤ i ≤ j ≤ |x|.

Con lo que, Pr(x|Gp) =∑

A∈N f c(A < i, i >)p(A → xi), 1 ≤ i ≤ |x|.El cálculo de las expresiones anteriores requiere un coste temporal O(|x|3|P |)

y un coste espacial es O(|x|2|N |).La información estructural presente en la muestra queda registrada en la expre-

siones anteriores de manera que únicamente se consideran aquellas derivacionesque con compatibles con la parentización. El algoritmo IO con muestras parenti-zadas, al que llamaremos algoritmo IOp, puede reescribirse haciendo uso de lasdefiniciones anteriores y su formulación es similar a las expresiones (3.5) y (3.6)[PS92].

Los costes de esta versión del algoritmo en cada iteración son asintóticamentelos mismos que el algoritmo original.

La ventaja de esta propuesta es que al imponer restricciones sintácticas en laselección de las derivaciones que se consideran para el aprendizaje, algunas reglaspueden pasar a tener probabilidad nula, lo cual puede provocar una severa reduc-ción en el espacio de búsqueda y acelerar la convergencia del algoritmo respecto alalgoritmo IO. Además, las restricciones sintácticas permiten focalizar la informa-ción estocástica en derivaciones relevantes, lo que puede facilitar la obtención de

68

mejores modelos. Los inconvenientes son, por un lado, la necesidad de disponer dedatos parentizados, y por otro, que el número de iteraciones hasta converger puedeser elevado.

El algoritmo VS con muestras parentizadas: el algoritmo VSp

A partir de la propuesta anterior, vamos a presentar un algoritmo en el que laselección de la mejor derivación se hace considerando únicamente las derivacionesque son compatibles con la parentización definida sobre la muestra. La idea esaplicar un esquema de Viterbi con muestras parentizadas. Este algoritmo pretendereunir las ventajas del algoritmo VS y el uso de información estructural

Para ello, hay que adaptar el algoritmo de Viterbi (ver Sección 2.4) pero res-tringiendo las derivaciones a considerar con la función c(·, ·) definida anteriormen-te (4.6):

ec(A < i, i >) = p(A → xi),

ec(A < i, j >) =

c(i, j) maxB,C∈N

p(A → BC) maxk=i,...,j−1

ec(B < i, k >)ec(C < k + 1, j >)

1 ≤ i < j ≤ |x|.

De esta forma, Pr(x|Gp) = ec(S < 1, |x| >).Los costes de esta nueva versión del algoritmo de Viterbi son iguales a la

de la versión original, esto es, un coste temporal O(|x|3|P |) y un coste espacialO(|x|2|P |).

Por lo demás, el algoritmo VS con muestras parentizadas, al que llamaremosalgoritmo VSp, es igual al presentado en el apartado 3.2.2. Nótese que en estealgoritmo la mejor derivación que se selecciona tiene que ser compatible con laparentización, lo que supone imponer más restricciones en el proceso de estimacióna las que impone el algoritmo VS.

4.5.1. Estudio empírico del comportamiento de los algoritmos IOp yVSp

De forma análoga a lo que sucede con los algoritmo IO y VS, la transformaciónen la que se basan los algoritmos IOp y VSp únicamente informa sobre la localidadde la solución alcanzada y sobre su convergencia. Por ello, en este apartado vamosilustrar con un ejemplo sintético como se comportan estos algoritmos en la práctica.Esto nos permitirá, además, relacionarlo con los algoritmo IO y VS.

El experimento realizado es el de los palíndromos que hemos venido utilizandoa lo largo de esta tesis. Las condiciones de la experimentación son las mismas quelas descritas en la Sección 3.2.3, pero en esta ocasión las cadenas estaban parenti-zadas. A partir de la misma GIP inicial utilizada en aquel experimento, se estimóuna nueva GIP tanto con el algoritmo IOp como con el algoritmo VSp. En cada

69

iteración se calculó la función que optimiza cada algoritmo. En la Figura 4.8 pue-den verse los resultados obtenidos, y en el Apéndice A pueden verse los resultadosobtenidos con otras semillas.

PSfrag replacements

IO

V S

IOp

V Sp

Iteraciones180160140120100806040200

-1800

-1600

-1400

-1200

-1000

-800

-600

-400

Figura 4.8: Evolución de las funciones maximizadas con cada algoritmo cuandose estimó con el IO, cuando se estimó con el VS, cuando se estimó con el IOp ycuando se estimó con el VSp.

En la misma puede verse como efectivamente el algoritmo IOp converge másrápidamente. Sin embargo, en este experimento podemos observar que la conver-gencia no fue tan rápida como era de esperar. En los experimentos con otras se-millas que se reportan en el Apéndice A si se observa una mayor velocidad deconvergencia (se ha dejado este experimento puesto que utilizaba la misma semillaque hemos venido utilizando a lo largo de la tesis). El óptimo alcanzado con el al-goritmo IOp es significativamente mejor que el óptimo alcanzado con el algoritmoIO, lo cual coincide con las expectativas que se tenía sobre este algoritmo.

Con el algoritmo VSp, la convergencia también fue muy rápida (ver los resulta-dos con otras semillas en el Apéndice A). Sin embargo, el óptimo alcanzado no estan bueno como el alcanzado con el algoritmo VS. Esto es debido a que las restric-ciones sintácticas impuestas por el parentizado pueden resultar demasiado severas,y pueden obligar a seleccionar una derivación de muy baja probabilidad. Esto haceque este algoritmo sea especialmente sensible a los valores iniciales de las probabi-lidades. Más adelante veremos algún experimento que nos permitirá constatar estehecho.

70

4.6. Experimentos con el corpus Penn Treebank

En apartados anteriores hemos visto mediante una experimentación sintética,como la estimación a partir de un subconjunto de derivaciones puede ser una al-ternativa apropiada frente al algoritmo VS para aproximar la verosimilitud de unamuestra. Sin embargo resulta necesario evaluar las posibilidades de los algoritmoscomentados, y estudiar sus problemas en una aplicación real compleja.

La tarea utilizada es la parte del corpus del Wall Street Journal procesada enel proyecto Penn Treebank2 [MSM93]. Se decidió trabajar con esta base de datospor ser ampliamente utilizada, por la gran cantidad de datos que contiene, y porqueestá analizada y etiquetada de acuerdo con las características de la experimentaciónque se deseaba realizar.

Estos datos son una colección de textos de ediciones de finales de la década delos 80 del periódico Wall Street Journal. El conjunto de datos comprende un millónde palabras. Este corpus está analizado y etiquetado automáticamente, y revisadode forma manual tal como se describe en [MSM93] (ver frases de ejemplo en laFigura 4.9). El etiquetado es dos tipos: un etiquetado de partes del habla que lla-maremos etiquetado léxico (en ingles POStag) y un etiquetado sintáctico3 . La talladel vocabulario es de más de 25,000 palabras, el vocabulario léxico está compuestopor 45 etiquetas, y el vocabulario sintáctico está compuesto por 14 etiquetas4 .

( (S(NP-SBJ

(NP (NNP Pierre) (NNP Vinken) )(, ,)(ADJP

(NP (CD 61) (NNS years) )(JJ old) )

(, ,) )(VP (MD will)

(VP (VB join)(NP (DT the) (NN board) )(PP-CLR (IN as)(NP (DT a) (JJ nonexecutive) (NN director) ))

(NP-TMP (NNP Nov.) (CD 29) )))(. .) ))

Figura 4.9: La frase “Pierre Vinken, 61 years old, will join the board as a nonexe-cutive director Nov. 29.” analizada y etiquetadas en el proyecto Penn Treebank.

2La versión 2 de este conjunto de datos puede obtenerse a través del Linguistic Data Consortiumcon número de catálogo LDC94T4B (http://www.ldc.upenn.edu/ldc/noframe.html).

3Cada etiquetado se guarda en un directorio diferente: el etiquetado léxico en el directorio “tag-ged” y el etiquetado sintáctico en el directorio “parsed”. Adicionalmente existe el directorio “com-bined” que combina ambos tipos de etiquetado.

4Algunas etiquetas sintácticas está acompañadas de otra información que indica la función de laparte sintáctica.

71

Puesto que la talla del vocabulario del corpus original resultaba demasiadogrande para los experimentos que se pretendía realizar se decidió trabajar única-mente con las etiquetas léxicas. A partir del directorio “tagged” proporcionado enla base de datos, el conjunto de datos se dividió en frases, considerando para ellouna frase como una secuencia de etiquetas que terminaban con la etiqueta “.”, confinal de párrafo (marcado con una secuencia de signos “=” en el corpus original),o con final de fichero. Esto daba lugar a un corpus de datos cuyas característicasprincipales pueden consultarse en la Tabla 4.4.

Cuadro 4.4: Características del corpus Penn Treebank después de la división enfrases.

Número de Longitud Desviación Longitud Longitudcadenas media típica mínima máxima

54,393 23.75 11.31 1 249

Dado el número de experimentos que se deseaba realizar, se decidió no con-siderar las cadenas que tenían un longitud superior a 15 terminales. Esto permitíareducir el esfuerzo computacional en la experimentación. Algo análogo se hace enotros trabajos [Che96].

El corpus de datos está organizado en 25 directorios (del 00 al 24) y se agrupa-ron en 5 particiones cuyas características pueden verse en la Tabla 4.5.

Cuadro 4.5: Características de las 5 particiones definidas para los experimentos unavez se han eliminado las cadenas con una longitud superior a 15 terminales.

Partición Directorios Número de Longitud Desviacióncadenas media típica

P1 del 00 al 04 2,462 10.35 3.69P2 del 05 al 09 2,561 10.55 3.56P3 del 10 al 14 2,900 10.52 3.58P4 del 15 al 19 2,708 10.61 3.59P5 del 20 al 24 2,788 10.29 3.63

Total todos 13,419 10.48 3.61

Conjunto de entrenamiento, conjunto de test y gramática inicial

El conjunto de datos descrito se dividió en un conjunto de entrenamiento (quellamamos Tr) y un conjunto de test (que denominamos Ts). Dado el volumen deexperimentos que se deseaba realizar se definieron tres experimentos con las parti-ciones comentadas, cuyos conjuntos Tr y Ts aparecen descritos en la Tabla 4.6.

72

Cuadro 4.6: Particiones utilizadas en los conjuntos Tr y Ts de los tres experimentos.Entre paréntesis aparece el número de frases de cada conjunto.

Tr TsExperimento 1 P2 P3 P4 P5 (10,957) P1 (2,462)Experimento 2 P1 P2 P4 P5 (10,519) P3 (2,900)Experimento 3 P1 P2 P3 P4 (10,631) P5 (2,788)

Las perplejidades de los conjuntos de test utilizando un modelo de trigramas 5

entrenado con los respectivos conjuntos de entrenamiento pueden verse en la Ta-bla 4.7. Obsérvese como la perplejidad es bastante similar para las tres particionesescogidas.

Cuadro 4.7: Perplejidad de cada uno de los conjuntos de test, empleando el con-junto de entrenamiento para estimar un modelo de trigramas.

Partición P1 P3 P5

Perplejidad 9.17 9.16 9.63

Cada uno de los conjuntos de entrenamiento descritos se utilizó para estimaruna GIP a partir de una GIP inicial. Esta GIP inicial tenía el máximo número dereglas que pueden formarse con 45 terminales y 14 no terminales, o sea, 3, 374reglas (143 + 14 ∗ 45). El número de no terminales se eligió para que coincidiesecon el número de etiquetas sintácticas, de forma similar a como se hace en [PS92].Las probabilidades se asignaron de forma aleatoria. Para evitar una mala elecciónde las probabilidades de la gramática inicial, todos los experimentos se repitieroncon tres gramáticas iniciales diferentes.

A continuación se describen los experimentos realizados con los datos descri-tos para estimar las GIP, tanto con el algoritmo kVS como con los algoritmos IOpy VSp. Únicamente se comentan los resultados obtenidos con una de las gramáti-cas iniciales. Los resultados con las otras dos gramáticas son similares y puedenconsultarse en el Apéndice C.

4.6.1. Experimentos realizados con el algoritmo kVS

En la experimentación realizada con el algoritmo kVS se pretendían estudiartres aspectos de este algoritmo: la evolución en función de k, el comportamiento

5En los cálculos de perplejidad con trigramas que aparecen en este capítulo y el que sigue, seutilizó interpolación lineal, y las palabras fuera del vocabulario se agruparon en una misma clase yse incluyeron en el cómputo de la perplejidad.

73

temporal, y la dependencia respecto a la talla del conjunto de entrenamiento. Acontinuación detallamos cada uno de ellos.

Como se vio al presentar el algoritmo kVS, la elección de k no podía hacersesimplemente en función del coste del algoritmo, y demostramos que utilizar valo-res progresivamente mayores de este valor no garantizaba la obtención de modelosmejor estimados. Sin embargo, en la experimentación preliminar si se observabaesta tendencia. Este comportamiento fue evaluado en los experimentos descritos.Los resultados obtenidos pueden verse en la Tabla 4.8. En los experimentos repor-tados cabe notar que se utilizaron valores pequeños de k, puesto que hicimos lahipótesis de que un pequeño conjunto de las derivaciones más probables eran lasque condicionaban en mayor medida la bondad de los modelos obtenidos (véase laSección 3.2.3). Podemos observar como la perplejidad tiende a decrecer a medidaque aumenta el número de derivaciones utilizado en la estimación. Sin embargo,obsérvese que para la partición P3, la perplejidad al pasar de k = 3 a k = 5creció ligeramente. Como comentamos, esta situación podía darse, puesto que uti-lizar mayores valores de k no implicaba siempre modelos mejor estimados (véasela Sección 4.3.2). Los porcentajes de mejora entre el algoritmo VS y el kVS conk = 7 están alrededor de un 7 %. Esto confirma que la utilización de más derivacio-nes en el proceso de estimación permite, en general, obtener mejores modelos. Elnúmero de derivaciones necesarias para converger era alrededor de cien iteracionesen todos los casos.

Cuadro 4.8: Perplejidad de los conjuntos de test para diferentes valores de k. Lacolumna Ts indica la partición utilizada para el test. El conjunto de entrenamientoestaba compuesto por las otras cuatro particiones que no aparecen en este columna.Las tallas de cada partición pueden consultarse en la Tabla 4.6.

Ts VS k = 3 k = 5 k = 7

P5 22.87 22.67 21.45 20.80P3 22.65 22.60 22.81 21.25P1 22.37 21.31 20.67 20.60

Respecto al comportamiento temporal del algoritmo kVS, es importante notarque el tiempo requerido en cada iteración era muy similar al tiempo requeridopor el algoritmo VS. En la Figura 4.10 puede verse el tiempo requerido por elalgoritmo para diferentes valores de k durante las primera iteraciones. Obsérveseque es bastante similar en todos los casos, lo cual confirma que el coste temporal delalgoritmo de cálculo de las k mejores derivaciones está más cerca de su caso mejorque de su caso peor. Este comportamiento es especialmente atractivo puesto queconfirma que se pueden utilizar valores de k mayores sin sobrepasar excesivamenteel coste del algoritmo VS.

Finalmente cabe comentar el comportamiento del algoritmo en función de la

74

PSfrag replacements

Iteraciones

18000

16000

14000

12000

10000

8000

6000

4000

2000

Seg

undo

s

201816141210864200

VSk = 3k = 5k = 7

Figura 4.10: Tiempo consumido en la 20 primeras iteraciones para diferentes va-lores de k cuando el conjunto de test era P5 y el de entrenamiento estaba formadopor el resto de particiones. Los experimentos se realizaron en una máquina HP9000-735 con el sistema operativo Unix Versión B.10.01.

talla del conjunto de entrenamiento. El algoritmo kVS fue evaluado utilizando úni-camente k = 7 y variando la talla del corpus de entrenamiento. Los resultadosobtenidos se contrastaron con los obtenidos por el algoritmo VS y se reportan en laTabla 4.9. Obsérvese como, en general, la tendencia de la perplejidad es a disminuira medida que aumenta el conjunto de entrenamiento.

Para concluir, hemos visto como el algoritmo kVS es una alternativa razonableal algoritmo VS para estimar las GIP. Se ha confirmado nuestra hipótesis de queúnicamente son necesarias unas pocas derivaciones para obtener mejoras frente alalgoritmo VS. Valores mayores de k permitirían obtener modelos mejor estimadossin sobrepasar excesivamente el coste del algoritmo VS.

4.6.2. Experimentos realizados con los algoritmos IOp y VSp

A continuación se describen los experimentos realizados con los algoritmosIOp y VSp. Para esta experimentación se utilizó el corpus de datos parentizados.A partir del directorio “combined” de la base de datos, el conjunto de datos sedividió en frases de acuerdo con la información proporcionada por la parentización.Dado que en la experimentación anterior no se apreciaron diferencias significativasentre los tres experimentos descritos en la Tabla 4.6, y dado el elevado número deiteraciones que el algoritmo IOp necesita para converger, los algoritmos IOp yVSp sólo se probaron con el experimento 3 (ver en la Tabla 4.6 las particionesutilizadas para el entrenamiento y para el test). Esto daba lugar a unos conjuntos de

75

Cuadro 4.9: Perplejidad del conjunto de test para diferentes tallas del conjunto deentrenamiento. La columna Ts indica la partición utilizada para el test. La colum-na Tr indica las particiones utilizadas para el entrenamiento. Las tallas de cadapartición pueden consultarse en la Tabla 4.5.

Ts Tr VS k = 7

P5 P1 23.89 22.06P1 P2 23.54 22.00

P1 P2 P3 22.56 21.55P1 P2 P3 P4 22.87 20.80

P3 P1 23.95 22.24P1 P2 23.71 22.09

P1 P2 P4 22.80 22.60P1 P2 P4 P5 22.65 21.25

P1 P2 23.01 21.57P2 P3 22.55 21.82

P2 P3 P4 22.27 21.83P2 P3 P4 P5 22.37 20.60

datos cuyas características pueden verse en la Tabla 4.106. Con estos algoritmos ylos datos comentados, se estimó una GIP a partir de la GIP inicial utilizada en losexperimentos anteriores.

Cuadro 4.10: Características del conjunto de entrenamiento y de conjunto de test.Las diferencias respecto a los datos de la Tabla 4.6 son debidos fundamentalmenteal mencionado directorio.

Conjunto Directorios Número de Longitud Desviacióncadenas media típica

Tr del 00 al 19 9,933 10.67 3.46Ts del 20 al 24 2,295 10.51 3.55

La perplejidad del conjunto Ts con los modelos estimados con los algoritmosIOp y VSp utilizando Tr pueden verse en la Tabla 4.11. Resultados similares conlas otras semillas pueden consultarse en las Tablas C.3 y C.7 del Apéndice C. Laperplejidad de Ts con un modelo de trigramas estimado con Tr era 9.63.

Pueden verse los buenos resultados obtenidos por el algoritmo IOp frente alalgoritmo VSp. La información estructural permite al algoritmo focalizar la proba-

6Cabe notar que en la base de datos mencionada, el directorio “combined” tiene uno de los sub-directorios incompletos (el directorio 08).

76

Cuadro 4.11: Perplejidad del conjunto de test cuando se estimó con los algoritmosIOp y VSp.

Algoritmo IOp VSp

Perplejidad 13.14 21.82

bilidad en un subconjunto de derivaciones compatibles con la parentización. Estaforma de proceder del algoritmo facilita la obtención de mejores modelos. Sin em-bargo, un severo inconveniente del algoritmo IOp es el número de iteraciones quenecesita para converger. Además, su aplicabilidad está restringida a tareas donde elconjunto de terminales es bastante pequeño.

Los resultados obtenidos con el algoritmo VSp no fueron tan buenos como losobtenidos por el algoritmo IOp. Como ya comentamos en la experimentación sinté-tica esto es debido a que la parentización puede introducir condiciones demasiadoseveras sobre las derivaciones a considerar, obligando a elegir una compatible conla parentización pero con baja probabilidad. Este algoritmo es especialmente sen-sible a las probabilidades de la GIP inicial, como ya sucedía con el algoritmo VSrespecto al IO.

Nótese como los resultados obtenidos por ambos algoritmos son peores que losobtenidos por un modelo de n-gramas, incluso en este experimento en el cual elconjunto de terminales es bastante pequeño. Un experimento de estimación de lasGIP similar en el que los terminales fueran palabras y no categorías sería impensa-ble, tanto por el coste en cada iteración como por la cantidad de datos necesariospara estimar tal volumen de parámetros. Por ello resulta impensable el uso de lasGIP para competir con los modelos de n-gramas en tareas de ML. Una alterna-tiva más razonable consiste en utilizar un modelo mixto en el cual las n-gramasrepresenten información local entre palabras y las GIP representen información dela frase completa a nivel de categorías. En el siguiente capítulo detallaremos másextensamente esta propuesta.

Por último, en la Tabla 4.12 se resumen los resultados más significativos alcan-zados por los diferentes algoritmos presentados en este capítulo a excepción delalgoritmo IO, para el experimento 3. Resultados similares con las otras semillaspueden consultarse en las Tablas C.4 y C.8 del Apéndice C.

Cuadro 4.12: Perplejidad de Ts en el experimento 3 con diferentes algoritmos.

Algoritmo VS kVS (k = 7) IOp VSp

Perplejidad 21.56 20.65 13.14 21.82

Nótese en esta tabla los buenos resultados alcanzados por la versión parentiza-

77

da del algoritmo frente al resto de algoritmos. Sin embargo es importante destacarque este algoritmo sólo se puede aplicar en condiciones muy restrictivas, como yase ha comentado.

4.7. Conclusiones

En este capítulo se han estudiado diferentes algoritmos para la estimación delas GIP que hacen uso de un subconjunto específico de derivaciones de cada ca-dena. Por una parte se ha propuesto y estudiado el algoritmo kVS en el que elconjunto de derivaciones se elige con criterios estadísticos [SB98a]. Este algorit-mo tiene la ventaja de que su coste en la práctica es similar al algoritmo VS tantoen número de iteraciones como en coste por iteración. En la práctica se observaque los modelos estimados con esta técnica tienden a mejorar a medida que seutiliza un mayor número de derivaciones. Así mismo se ha estudiado la relaciónentre la función maximizada entre este algoritmo y los algoritmo IO y VS, y se hanestudiado las características estocásticas de los modelos obtenidos demostrando laconsistencia de los mismos.

Por otra parte se ha estudiado el algoritmo IOp que hace uso de cadenas paren-tizadas, con lo que el conjunto de derivaciones se elige con criterios básicamenteestructurales. Basándonos en esta idea se ha propuesto el algoritmo VSp que se-lecciona la mejor derivación que es compatible con la muestra parentizada. Unaexperimentación con ambos algoritmo revela los buenos resultados que es capazde obtener el algoritmo IOp frente a la nueva propuesta. El inconveniente del algo-ritmo IOp para su aplicación en problemas reales es, de una parte, la dificultad dedisponer de grandes volúmenes de datos parentizados, y de otra, el elevado núme-ro de iteraciones que son necesarias para converger. Los resultado obtenidos porel algoritmo VSp muestran por el contrario que las condiciones estructurales im-puestas por la muestra parentizadas pueden resultar bastante severas, obligando aelegir una derivación con baja probabilidad y obteniendo en consecuencia mode-los peor entrenados. Este algoritmo, al igual que sucede con el algoritmo VS, sonespecialmente sensibles a los valores iniciales de las probabilidades, por lo que elproblema de la inicialización se convierte en un problema crucial.

78

Capítulo 5

Aplicación de las GIP en ML

La aplicación de las GIP para modelizar el lenguaje introduce una serie deproblemas que requieren soluciones eficientes. En primer lugar, se plantean pro-blemas de interpretación; es decir, cómo determinar la relación entre las palabrasdel lenguaje. En segundo lugar, se introducen problemas de integración; es decir,cómo realizar la interpretación de forma eficiente. Para abordar el problema de lainterpretación se han realizado propuestas basadas en el cálculo de la probabilidaddel prefijo de una cadena, mientras que para tratar el problema de la integración sehan propuesto modelos híbridos que combinan modelos de n-gramas con modelosestructurales. En este capítulo se van a estudiar y realizar propuestas relacionadascon ambos problemas.

5.1. Introducción

Un problema importante asociado con la Modelización del Lenguaje consisteen evaluar la siguiente expresión [BJM83]:

Pr(wk+1 | w1w2 . . . wk), (5.1)

es decir, determinar la probabilidad de que en el instante k + 1 se observe la pala-bra wk+1 suponiendo que previamente hemos observado la secuencia de palabrasw1w2 . . . wk. La evaluación de esta expresión se realiza haciendo uso de algún mo-delo, y de esta forma se introducen dos problemas: el aprendizaje del modelo, y elcómputo de la propia expresión.

Para calcular la expresión 5.1 es habitual simplificarla imponiendo restriccio-nes sobre la historia, esto es, sobre w1w2 . . . wk. La restricción más común parapredecir la palabra en el instante k + 1 es limitar la historia anterior a un pequeñoconjunto de palabras. Los modelos de n-gramas [BJM83, Jel98] permiten aproxi-mar la expresión (5.1) calculando la probabilidad de la siguiente palabra a observar,considerando únicamente las n − 1 palabras anteriores:

Pr(wk+1 | wk−n+2 . . . wk). (5.2)

79

80

Esta propuesta presenta importantes ventajas: en primer lugar, la estimación de losparámetros del modelo se puede realizar de manera sencilla y eficiente [Jel98]; ensegundo lugar, la evaluación de la expresión anterior puede hacerse con un cos-te temporal constante, puesto que únicamente hay que consultar una tabla. Sinembargo, estos modelos tienen algunos inconvenientes. El número de parámetrosa estimar crece exponencialmente con el valor de n, por lo que sólo es posibleconsiderar valores pequeños de n; en consecuencia, sólo son capaces de recogerdependencias locales, en función del valor de n.

Otra forma de aproximar la expresión (5.1) consiste en imponer restriccionessintácticas sobre la historia anterior para limitar las posibles relaciones entre laspalabras. Las GIP son una alternativa adecuada para representar relaciones sintác-ticas entre las palabras. Con este tipo de modelos, la expresión (5.1) se aproximacomo [JL91]:

Pr(wk+1 | w1w2 . . . wk, Gp). (5.3)

La probabilidad de la palabra que se observa en el instante k + 1, wk+1, se deter-mina a partir de la relación que define una GIP Gp, entre la subcadena w1w2 . . . wk

y dicha palabra. Esta aproximación presenta varias ventajas: en primer lugar, estetipo de modelos permite representar de forma compacta y eficiente, relaciones alargo término entre las palabras de la cadena; en segundo lugar, como se ha vistoen capítulos anteriores, existen algoritmos potentes que permiten la estimación delos modelos a partir de una muestra de aprendizaje; y en tercer lugar, existen al-goritmos robustos que permiten la evaluación de la expresión (5.3) [JL91, Sto95],y posibilitan una integración eficiente de este tipo de modelos. Sin embargo, elcoste de los algoritmos hace que la utilización se vea enormemente limitada. Ade-más, para tareas reales complejas es necesario un elevado número de parámetros,y consecuentemente, una gran cantidad de datos para estimarlos adecuadamente.Estos problemas se acentúan en tareas reales con grandes vocabularios, por lo quela aplicación de las GIP en ML sin apoyo de algún otro mecanismo resulta pocoadecuado.

En los Capítulos 3 y 4 se ha estudiado ampliamente el problema de la estima-ción de estos modelos. En este capítulo vamos a presentar propuestas tanto para elproblema de la interpretación como para el problema de la integración de este tipode modelos.

En cuanto al problema de interpretación, en [JL91] se plantea el problema delcálculo de la expresión (5.3), y presentan el algoritmo Left-to-Right Inside (LRI)que permite calcular la probabilidad de una subcadena inicial a partir de una GIPGp. En este capítulo se va a estudiar una forma de aproximar la expresión (5.3)a partir de la mejor derivación que genera una subcadena inicial. La motivaciónde esta propuesta es consecuencia, principalmente, de la forma de proceder delos algoritmos de estimación estudiados. Si la GIP es estimada con alguno de losalgoritmos vistos, entonces la mejor derivación de una subcadena es la que registramayor cantidad de información acerca de la siguiente palabra a analizar, y por tantola que posee mayor capacidad discriminativa.

81

Para la integración de estos modelos, trabajos recientes han propuesto el usode modelos híbridos de n-gramas y modelos estructurales [CJ98, Bel98] para apro-ximar de forma eficiente la expresión (5.1). Los modelos de n-gramas tratan derepresentar la información local a nivel de palabras, mientras que los modelos es-tructurales tratan de representar información sintáctica de toda la frase a nivel decategorías. En este capítulo vamos a presentar un modelo híbrido en el que el mo-delo estructural es una GIP. Como se vio en el Capítulo 2, este tipo de modelospermiten representar de forma eficiente y compacta, relaciones sintácticas entre lasdiferentes partes de una cadena.

En la sección que sigue vamos a estudiar como computar la expresión (5.3)mediante el algoritmo LRI propuesto en [JL91], y a continuación haremos unanueva propuesta para aproximar este valor siguiendo un esquema de Viterbi. Acontinuación estudiaremos un modelo de lenguaje híbrido de n-gramas y GIP comoel comentado.

5.2. Análisis sintáctico probabilístico del prefijo de unacadena

Jelinek y Lafferty, en [JL91], plantean el problema del cálculo de (5.3) como:

Pr(wk+1 | w1w2 . . . wk, Gp) =Pr(S

∗⇒ w1 . . . wkwk+1 . . . | Gp)

Pr(S∗⇒ w1 . . . wk . . . | Gp)

. (5.4)

Esta aproximación se caracteriza porque el cómputo de la siguiente palabra con-sidera toda la historia anterior, aportando de esta forma la mayor cantidad posiblede información. Para computar la expresión (5.4) se presenta el algoritmo LRI quepermite calcular Pr(S

∗⇒ x1 . . . xk . . . | Gp), esto es, la probabilidad de generar elprefijo w1 . . . wk . . ..

En esta sección vamos a presentar una forma de aproximar la expresión (5.3) apartir de la probabilidad de la mejor derivación que genera una subcadena inicial.Tal como se ha mencionado en la introducción, si la GIP utilizada en el cómputode dicha expresión es estimada con alguno de los métodos que estudiamos en capí-tulos anteriores, entonces la mejor derivación de la cadena acumula gran parte dela probabilidad de la cadena, por lo que esta derivación será la que influirá princi-palmente en la predicción de la siguiente palabra que puede seguir a un prefijo.

La idea es similar a la que se aplica en RAH. En este campo se utiliza el algorit-mo de Baum-Welch [HAJ90] (equivalente al algoritmo IO para modelos regulares)en la etapa de aprendizaje. En la etapa de reconocimiento, el algoritmo de Viterbi[For73] (la versión para modelos regulares) obtiene la interpretación que da cuen-ta de una secuencia acústica de entrada. El algoritmo de Baum-Welch tiende aacumular la masa de probabilidad en las mejores derivaciones. En la etapa de reco-nocimiento, el algoritmo de Viterbi saca provecho de esta característica y recuperala interpretación más probable, es decir, aquella que mayor información estocásticaha concentrado.

82

El problema del cálculo de la probabilidad de la mejor derivación que generauna subcadena inicial está fuertemente relacionado con el algoritmo LRI, por loque vamos a definir previamente algunos conceptos que serán de utilidad en estasección. Para ello seguiremos básicamente la notación propuesta en [JL91].

5.2.1. Probabilidad de una subcadena inicial: el algoritmo LRI

Sea Gp una GIP y x una cadena de L(Gp). Se define la probabilidad de que elno terminal A ∈ N derive directamente el no terminal B ∈ N , como no terminalmás a la izquierda en una de sus reglas, como:

R(A → B) =∑

C∈N

p(A → BC). (5.5)

Se define la probabilidad de que B sea el no terminal más a la izquierda, encualquier forma sentencial que se pueda derivar a partir de A, como:

T (A ⇒ B) = R(A → B) +∑

C1∈N

R(A → C1)R(C1 → B) + · · ·

+∑

C1,...,Ck∈N

R(A → C1)R(C1 → C2) · · ·R(Ck → B) + · · ·

=∑

α∈(N∪Σ)+

Pr(A∗⇒ Bα | Gp). (5.6)

Se define la probabilidad de que BC , C ∈ N , pueda ser la subcadena inicialde todas las formas sentenciales derivadas de A como:

T (A ⇒ BC) = p(A → BC) +∑

D∈N

T (A ⇒ D)p(D → BC).

Finalmente se define la probabilidad de generación de cadenas a partir de Acuya subcadena inicial sea xi . . . xj como:

e(A << i, j) = Pr(A∗⇒ xi . . . xj . . . | Gp).

Con todo ello, el algoritmo LRI se define como:

e(A << i, i) = p(A → xi) +∑

B∈N

T (A ⇒ B)p(B → xi), (5.7)

e(A << i, j) =∑

B,C∈N

T (A ⇒ BC)

j−1∑

k=i

e(B < i, k >)e(C << k + 1, j).

1 ≤ i < j

Con lo que Pr(x1 . . . xk . . . | Gp) = e(S << 1, k).El coste del algoritmo LRI es dos veces el coste del algoritmo Inside y por

tanto O(|x|3|P |).

83

Comparando las expresiones de los algoritmos Inside y LRI se puede apreciarinteresantes similitudes; sin embargo, también se observan notables diferencias,sobre todo en la aparición de las expresiones T (A ⇒ B) y T (A ⇒ BC). Como sepuede ver, el cálculo de ambas se basa en la expresión (5.6) y ésta se evalúa en tér-minos de la expresión (5.5). En [JL91] se plantea la utilización de álgebra matricialpara la evaluación de la expresión (5.6). Para ello se considera que R y T denotanmatrices cuadradas (con dimensión igual al número de no terminales) cuyos ele-mentos en la A-ésima fila y la B-ésima columna son R(A → B) y T (A ⇒ B)respectivamente. Así pues:

T = R + RR∗R = R + R2 + R3 + . . . , (5.8)

y de ésta se puede obtener la expresión [Wet80]:

T = R[I − R]−1.

La expresión (5.8) representa una suma infinita cuya convergencia se puede de-mostrar cuando la GIP no contiene símbolos inútiles. En el Apéndice B se puedever una propiedad acerca de la convergencia de esta suma.

Como Jelinek y Lafferty comentan en [JL91], el cálculo de Pr(x1 . . . xk . . . |Gp) a partir del algoritmo LRI, se limita a aquellas gramáticas con un númeroreducido de no terminales, de forma que el cálculo de la matriz inversa sea posible.

5.2.2. Probabilidad de la mejor derivación que genera una subcadenainicial: el algoritmo VLRI

A continuación vamos a presentar un algoritmo para calcular la probabilidad dela mejor derivación que genera un prefijo. Este algoritmo se basa en la aplicaciónde un esquema de Viterbi al algoritmo LRI, por lo que le denominamos algoritmoVLRI.

Considerando la analogía que existe entre el algoritmo Inside y el algoritmode Viterbi, se va a proponer frente a la probabilidad de generación de la sub-cadena inicial Pr(x1 . . . xk . . . | Gp), evaluada con el algoritmo LRI, el cálcu-lo de la probabilidad de la mejor derivación que genera una subcadena inicialPr(x1 . . . xk . . . | Gp).

Para la evaluación eficiente de esta probabilidad, Pr(x1 . . . xk . . . | Gp), vamosa proponer un algoritmo similar al algoritmo LRI pero basado en un esquema deViterbi. Por tanto, vamos a realizar una presentación similar a la sección anterior,redefiniendo los conceptos más importantes.

Se define la máxima probabilidad de que B ∈ N sea inicial de A ∈ N , a partirde una de sus reglas, como:

R(A → B) = maxC∈N

p(A → BC). (5.9)

84

Análogamente, se define la probabilidad de la mejor derivación en la que par-tiendo de A, B es el símbolo de más a la izquierda como:

T (A ⇒ B) = max(R(A → B), maxC1∈N

(R(A → C1)R(C1 → B)), . . . ,

maxC1,...,Ck∈N

(R(A → C1) · · · R(Ck → B)), . . .)

= maxα∈(N∪Σ)+

Pr(A∗⇒ Bα | Gp). (5.10)

Se define la probabilidad de la mejor derivación en la que partiendo de A, BC(C ∈ N ), sea subcadena inicial como:

T (A ⇒ BC) = max(p(A → BC),maxD∈N

(T (A ⇒ D)p(D → BC))). (5.11)

Finalmente, se define la probabilidad de la mejor derivación que genera la sub-cadena inicial xi . . . xj a partir de A dado Gp como:

e(A << i, j) = Pr(xi . . . xj . . . | Gp).

Con todo ello, el algoritmo VLRI propuesto será:

e(A << i, i) = max(p(A → xi),maxB∈N

T (A ⇒ B)p(B → xi)),

e(A << i, j) = maxB,C∈N

(T (A ⇒ BC) (5.12)

maxk=i,...,j−1

e(B < i, k >)e(C << k + 1, j)) 1 ≤ i < j.

Con lo que Pr(x1 . . . xk . . . | Gp) = e(S << 1, k).Como se puede apreciar existen grandes similitudes entre el algoritmo pro-

puesto y el algoritmo LRI. Como en este último, la clave está en el cálculo de lasexpresiones T (A ⇒ B) y T (A ⇒ BC). El cálculo de ambas depende de la ade-cuada evaluación de la expresión (5.10) en términos de la expresión R(A → B).

Para ilustrar este cálculo se va a considerar un grafo, en el cual los vérticesserán los no terminales de la gramática, los arcos representarán la relación inicialy las etiquetas de los arcos representarán la probabilidad R(A → B) (obtenidaséstas a partir de las probabilidades de las reglas de la gramática). La función deetiquetado cumple las propiedades de un semianillo cerrado ([0, 1],max, ∗, 0, 1) ypor tanto se puede plantear como el problema de la evaluación de la probabilidaddel mejor camino (de probabilidad máxima) entre dos vértices [AHU74, BS96].Evidentemente este problema es equivalente al cálculo de T entre los no termi-nales asociados a dichos vértices (ver algoritmo de la Figura 5.1). Los cómputosrealizados en este algoritmo no dependen de la cadena analizada y sólo de la GIPutilizada, por lo que su aplicación se realiza una única vez en el algoritmo VLRI.

El problema del cálculo de la expresión (5.6) se podría plantear de modo si-milar, sólo que T representará la suma de las probabilidades de todos los posiblescaminos entre dos vértices [AHU74].

85

1: Algoritmo de cálculo de T .2: Entrada3: R(Ai → Aj) para todo i, j / 1 ≤ i, j ≤ |N |.4: Salida5: T (Ai → Aj) para todo i, j / 1 ≤ i, j ≤ |N |.6: Variables7: C , matriz de |N | × |N |.8: Método9: para todo i, j / 1 ≤ i, j ≤ |N | hacer C0

ij = R(Ai → Aj)10: para todo k / 1 ≤ k ≤ |N | hacer11: para todo i, j / 1 ≤ i, j ≤ |N | hacer12: Ck

ij = max(Ck−1ij , Ck−1

ik Ck−1kj )

13: fin para14: fin para15: para todo i, j / 1 ≤ i, j ≤ |N | hacer T (Ai ⇒ Aj) = Ck

ij

16: FIN

Figura 5.1: Algoritmo para el cálculo de la T . Los no terminales se han numeradocomo S = A1, A2, . . . , A|N |.

El coste temporal de este algoritmo es O(|N |3) mientras que su coste espaciales O(|N |2).

Siguiendo [JL91], para computar e(S << 1, k) se pueden realizar los siguien-tes pasos:

1. Calcular e(A < i, j >) para todo A ∈ N , para i = 1, 2, . . . , k − 1 y paraj = i, i + 1, . . . , k − 1.

2. Calcular e(A << i, k) para todo A ∈ N y para i = k, k − 1, . . . , 1.

El coste temporal del paso 1 es O(k3|P |) que corresponde al algoritmo de Viterbi.El coste temporal del paso 2 es O(k2|P |), por lo que el coste de ambos pasos esO(k3|P |). El coste espacial es O(k2|N |). Como en [JL91], una vez se ha compu-tado e(S << 1, k), para calcular e(S << 1, k + 1), los pasos a seguir son:

1. Calcular e(A < i, k >) para todo A ∈ N , para i = 1, 2, . . . , k.

2. Calcular e(A << i, k + 1) para todo A ∈ N y para i = k + 1, k, . . . , 1.

El coste del primer paso es O(k2|P |) puesto que podemos aprovechar todos loscálculos realizados sobre el prefijo anterior. Igualmente, el coste del segundo pasoes O(k2|P |), por lo que el coste de analizar cada nuevo símbolo es O(k2|P |).

El algoritmo VLRI puede utilizarse para aproximar (5.3) según la expresión:

Pr(wk+1 | w1 . . . wk, Gp) =Pr(S ⇒ w1 . . . wkwk+1 . . .)

Pr(S ⇒ w1 . . . wk . . .). (5.13)

86

El uso de esta expresión para ML comparte algunos de los inconvenientes de laexpresión (5.4). En concreto, su coste computacional limita su aplicación a aque-llas gramáticas con un numero reducido de parámetros. Nótese que la informaciónque aporta la expresión (5.13) está contenida en la expresión (5.4). Si la GIP hasido estimada con alguno de los métodos comentados en los capítulos anterioresentonces la mayor parte de la información estocástica queda recogida en las mejo-res derivaciones, por que lo que el valor de ambas expresiones no debería diferirsustancialmente. Nuestra hipótesis es que la mejor derivación es la que mayor ca-pacidad discriminativa posee, y por tanto, la que tiene mayor capacidad predictivaacerca de la siguiente palabra a observar. En la siguiente sección se reportará unaexperimentación para estudiar esta hipótesis.

Una característica que diferencia al algoritmo VLRI del LRI es que permite ob-tener los argumentos que dan lugar a la maximización, y por tanto permite obtenerla mejor interpretación de la cadena de entrada en cualquier momento del procesode análisis.

5.3. Combinación de n-gramas y GIP para ML

La aplicación de las expresiones (5.4) y (5.13) en tareas complejas de ML pre-senta diversos problemas que han sido mencionados en las secciones anteriores. Enprimer lugar, son necesarios una gran cantidad de datos para estimar adecuadamen-te los parámetros del modelo. En segundo lugar, el proceso de aprendizaje de losmodelos presenta un elevado coste computacional. Y en tercer lugar, el coste delproceso de análisis tiene un coste excesivo. Por ello, las GIP no son una verdaderaalternativa a los modelos de n-gramas en ML.

En trabajos recientes de ML, se han propuesto modelos híbridos que combinanmodelos de n-gramas con modelos estructurales para aproximar la expresión (5.1)[CJ98, Bel98]. Ambos tipos de modelos se combinan para representar relacionesentre partes de la cadena en diferentes niveles de conocimiento. El modelo de n-gramas da cuenta de las relaciones entre las palabras del léxico, donde quedanmejor representadas las restricciones locales. Por su lado, el modelo estructuralda cuenta de las restricciones entre categorías de palabras, donde quedan mejorrepresentadas las restricciones a más largo término [CJ98].

Esta idea resulta muy atractiva, dado que trabajar con un modelo estructural anivel de categorías comporta varias ventajas. Al agrupar las palabras en un con-junto relativamente pequeño de categorías, se reduce notablemente el conjunto deparámetros necesarios para representar las relaciones sintácticas. De esta forma sereduce la talla del modelo y es posible estimarlo mejor. Además, al reducir el con-junto de terminales se atenúa el coste de los algoritmos de manipulación en la líneasugerida en [JL91]. Un serio inconveniente de esta propuesta es la necesidad dedisponer de un corpus de datos etiquetado con categorías para estimar los paráme-tros del modelo. Sin embargo, en años recientes han aparecido conjuntos de datosconvenientemente etiquetados [MSM93], que han propiciado un creciente interés

87

por esta propuesta.A continuación vamos a presentar una nueva propuesta en la cual la probabi-

lidad de la siguiente palabra se calcula con un modelo híbrido que combina unmodelo de n-gramas a nivel de palabras con una GIP a nivel de categorías. Des-pués veremos una experimentación realizada con esta propuesta sobre el corpus dedatos Penn Treebank.

Modelo híbrido de n-gramas y GIP

En el modelo que vamos a plantear, la probabilidad de la siguiente palabra quese observa (5.1) la aproximaremos como:

Pr(wk+1 | w1 . . . wk)

= γ Pr(wk+1 | wk−n+2wk) + (1 − γ) Pr(wk+1 | g(w1) . . . g(wk)). (5.14)

El primer sumando de esta expresión es un modelo de n-gramas que recoge lasdependencias locales a nivel de palabras. Tanto la estimación de los parámetros delmodelo, como el cómputo de Pr(wk+1 | wk−n+2wk) están ampliamente descritosen la bibliografía [Jel98], por lo que no se va a hacer mención a ellos.

En el segundo sumando, g() es una función de etiquetado que asocia una ca-tegoría a cada palabra. El problema de agrupar las palabras en categorías es unproblema que aparece ampliamente estudiado en la literatura [Jel98] y que no seva a tratar aquí. La expresión Pr(wk+1 | g(w1) . . . g(wk)) pretende recoger lasrelaciones estructurales a largo término entre las categorías de la frase.

En la expresión (5.14), γ, 0 ≤ γ ≤ 1, es un factor de peso que pondera ambaspartes de la expresión. Este factor expresa, en cierta forma, nuestra confianza encada uno de los modelos. Este parámetro puede ser estimado a partir del conjuntode datos como se describe en [Jel98].

Para una primera propuesta, vamos a simplificar el cálculo de la expresión (5.14),y para ello vamos a suponer que disponemos de un método para etiquetar laspalabras. Esto nos permite separar el problema del etiquetado del cómputo dePr(wk+1 | g(w1) . . . g(wk)). De esta forma el segundo sumando de (5.14) lo apro-ximaremos como:

Pr(wk+1 | g(w1) . . . g(wk)) = Pr(wk+1 | g1 . . . gk)

= Pr(wk+1 | gk+1) Pr(gk+1 | g1 . . . gk),

(5.15)

donde a partir de ahora gi, 1 ≤ i ≤ k, denotará la etiqueta asociada a la i-ésimapalabra. La expresión anterior se interpreta en los siguientes términos: la probabili-dad de que se dé una palabra se aproxima a partir de la probabilidad de la categoríaa la que pertenece (considerando un modelo gramatical de categorías) multiplicadopor la probabilidad de que en esa categoría se dé esa palabra. Las simplificacionesintroducidas permiten evaluar todas las expresiones como describimos a continua-ción.

88

El valor Pr(wk+1 | gk+1) corresponde a la probabilidad de clasificación de lapalabra wk+1 en la categoría gk+1. Para la estimación de los parámetros de los co-rrespondientes modelos es necesario disponer de un conjunto de datos etiquetadosen términos de categorías. De esta forma, el valor Pr(wk+1 | gk+1) se estima apartir de las frecuencias absolutas del corpus. Para una palabra w del vocabulario,la probabilidad de que esa palabra se clasifique en la categoría g, será:

Pr(w | g) =N(w, g)∑w′ N(w′, g)

,

donde N(w, g) es el número de veces que la palabra w ha sido etiquetada con laetiqueta g.

La evaluación de la expresión Pr(gk+1 | g1 . . . gk) puede realizarse con elalgoritmo LRI:

Pr(gk+1 | g1 . . . gk) = Pr(gk+1 | g1 . . . gk, Gp),

o bien, puede aproximarse con el algoritmo VLRI:

Pr(gk+1 | g1 . . . gk) = Pr(gk+1 | g1 . . . gk, Gp).

En las expresiones anteriores, la GIP Gp puede estimarse con alguno de losmétodos estudiados en los capítulos anteriores. El uso de categorías permite re-ducir considerablemente el número de parámetros de la GIP, lo cual posibilita laaplicación de los algoritmo LRI y VLRI con un coste razonable.

Con todo ello, la expresión (5.14) se aproxima como:

Pr(wk+1 | w1 . . . wk)

= γ Pr(wk+1 | wk−n+2wk) + (1 − γ) Pr(wk+1 | gk+1) Pr(gk+1 | g1 . . . gk, Gp).

(5.16)

Para estudiar las posibilidades de esta propuesta, se realizó una experimenta-ción con un corpus de datos real. A continuación detallamos estos experimentos ylos resultados obtenidos.

5.3.1. Experimentos realizados sobre el Penn Treebank

La propuesta descrita se estudió con el corpus de datos del Penn Treebank,puesto que reunía todas las características necesarias para la estimación de los pa-rámetros del modelo y para la evaluación de la propuesta. Se realizó un experi-mento a partir de los datos descritos en la Sección 4.6.2 del capítulo anterior, estoes, utilizando la partición P5 como corpus de test y el resto de particiones parael entrenamiento. El conjunto de test estaba compuesto por 2,295 cadenas y el deentrenamiento por 9,933. Al conjunto de datos descrito se le añadió la parte noetiquetada del mismo, que estaba formado por 6,333 palabras diferentes.

89

Con la parte no etiquetada del corpus se estimó un modelo de trigramas1 . Laperplejidad del conjunto de test con este modelo era 180.4. Para obtener este valorse utilizó interpolación lineal. Las palabras fuera del vocabulario se agruparon enuna misma clase y se incluyeron en el cómputo de la perplejidad [Ros95].

Con la parte etiquetada del corpus se estimó una GIP con los diferentes méto-dos de estimación estudiados en el Capítulo 4. Las GIP obtenidas con los diferentesmétodos, y utilizadas en el cómputo de la expresión (5.16), son las que se deta-llan en la Tabla 4.12. Esto nos permitía además analizar las posibilidades en unaaplicación real de los diferentes algoritmos de estimación descritos en capítulosanteriores.

Los experimentos se realizaron haciendo uso tanto de la expresión (5.4), comode la expresión (5.13). De esta forma se pretendía comparar los algoritmo LRI yVLRI para tareas de ML. Se probaron diferentes valores de γ y los resultados obte-nidos pueden verse en las Figuras 5.2, 5.3, 5.4, y 5.5. Resultado similares con otrasGIP estimadas a partir de semillas diferentes pueden consultarse en el Apéndice C.

PSfrag replacements

Per

plej

idad

γ

LRI

VLRI

160

165

170

175

180

185

0.7 0.75 0.8 0.85 0.9 0.95 1

Figura 5.2: Perplejidad del conjunto de test en función de γ. La linea continuacorresponde a la perplejidad con el modelo de trigramas. La GIP utilizada se estimócon el algoritmo VS.

De estas figuras cabe destacar los siguientes aspectos. En primer lugar, puedeobservarse como la combinación de modelos de n-gramas con las GIP permite me-jorar los resultados que se obtienen con modelos simples de n-gramas. En segundolugar, nótese como el valor de γ que permite obtener el mínimo en cada gráfica estárelacionado con la confianza que se tiene en cada modelo, y que esta confianza está

1Como en el capítulo anterior, este modelo se estimó con la herramienta de software descrita en[Ros95].

90

PSfrag replacements

Per

plej

idad

γ

LRI

VLRI

160

165

170

175

180

185

0.7 0.75 0.8 0.85 0.9 0.95 1

Figura 5.3: Perplejidad del conjunto de test en función de γ. La linea continuacorresponde a la perplejidad con el modelo de trigramas. La GIP utilizada se estimócon el algoritmo kVS (k = 7).

PSfrag replacements

Per

plej

idad

γ

LRI

VLRI

160

165

170

175

180

185

0.7 0.75 0.8 0.85 0.9 0.95 1

Figura 5.4: Perplejidad del conjunto de test en función de γ. La linea continuacorresponde a la perplejidad con el modelo de trigramas. La GIP utilizada se estimócon el algoritmo VSp.

en relación con el método de estimación empleado para obtener la GIP. Así, puedeobservarse que los menores valores de γ se obtienen con la GIP estimada con el

91

PSfrag replacements

Per

plej

idad

γ

LRI

VLRI

160

165

170

175

180

185

0.7 0.75 0.8 0.85 0.9 0.95 1

Figura 5.5: Perplejidad del conjunto de test en función de γ. La linea continuacorresponde a la perplejidad con el modelo de trigramas. La GIP utilizada se estimócon el algoritmo IOp.

algoritmo IOp. Y en tercer lugar, puede verse que los valores de la perplejidad ob-tenidos con el algoritmo VLRI son, en todos los casos, mejores que los obtenidoscon el algoritmo LRI. Como ya se ha comentado, esto puede deberse a una mayorcapacidad discriminativa del algoritmo VLRI frente al algoritmo LRI a la hora depredecir la siguiente palabra a observar.

Para concluir, destacar en primer lugar, que se ha presentado una propuestasencilla para ML que combina modelos de n-gramas con una GIP. Se ha visto queesta propuesta permite obtener mejores resultados que un modelo de n-gramas.En segundo lugar comentar que esta propuesta nos ha permitido evaluar las GIPobtenidas con los diferentes métodos de estimación estudiados en el Capítulo 4.Se ha visto como los resultados obtenidos están en sintonía con los resultados ob-tenidos en aquel capítulo. Y en tercer lugar, se ha visto como el algoritmo VLRIpermite obtener mejores resultados que el algoritmo LRI. Esto confirma la hipóte-sis que hicimos acerca del algoritmo VLRI, cuando comentamos que poseía mayorcapacidad para predecir la siguiente palabra a observar que el algoritmo LRI.

Esta propuesta abre interesantes vías de trabajo, fundamentalmente en dos di-recciones: por un lado estudiar la posibilidad de reducir el coste del proceso deanálisis, y por otro lado, estudiar cómo se puede introducir un etiquetador en lapropuesta, bien basado en los propios algoritmo LRI y VLRI, bien basado en otrasestrategias.

92

5.4. Conclusiones

En este capítulo se han estudiado diferentes aspectos de interpretación e inte-gración de las GIP para problemas de ML. Se ha estudiado el algoritmo LRI paracalcular la probabilidad de un prefijo. A partir de este algoritmo y del esquema deViterbi, se ha propuesto el algoritmo VLRI para el cálculo de la probabilidad de lamejor derivación que genera una subcadena inicial. Este algoritmo se ha formuladoen términos del problema de la búsqueda del mejor camino entre dos nodos en ungrafo ponderado [SB97a]. Este tipo de algoritmos tiene un gran interés en proble-mas de Reconocimiento del Habla Continua ya que permite procesar la secuenciade entrada de “izquierda a derecha”.

También se ha estudiado una propuesta para utilizar las GIP en problemas deML, combinándolas con modelos de n-gramas. El modelo de n-gramas represen-ta restricciones entre las palabras del vocabulario, mientras que la GIP representarestricciones sintácticas a nivel de categorías de palabras. Se ha visto en unos ex-perimentos, como esta propuesta mejora los resultados obtenidos por un modelobasado únicamente en n-gramas. En estos experimentos también se ha podido ob-servar que el algoritmo VLRI puede ser incluso más competitivo que el algoritmoLRI para esta labor cuando la GIP es estimada con alguno de los métodos de esti-mación estudiados en los Capítulos 3 y 4. Parte de este trabajo ha sido remitido en[BS99].

Capítulo 6

Conclusiones y trabajos futuros

Conclusiones

En esta tesis nos planteamos el problema de la estimación de las probabilidadesde una GIP, y de las propiedades de los modelos obtenidos. Así mismo, nos plan-teamos los problemas de interpretación e integración de las GIP para el problemade la Modelización del Lenguaje (ML).

En el Capítulo 2 se han introducido las GIP, se han descrito sus propiedades yse han presentado las principales ventajas e inconvenientes que comporta su utili-zación en problemas de análisis sintáctico.

Uno de los objetivos de la tesis era estudiar los dos algoritmos clásicos deestimación de las GIP: el algoritmo IO y el algoritmo VS. Se pretendía estudiartanto los propios métodos de estimación como las propiedades de los modelosobtenidos.

En el Capítulo 3 se ha estudiado la relación entre las funciones optimizadas porambos algoritmos y se ha visto que la diferencia entre ambas está acotada superior-mente por una función lineal de la muestra y una función logarítmica del númerode símbolos no terminales de la GIP. Se ha visto que en la práctica esta diferen-cia es notablemente menor que la cota propuesta, y cuando se estima una GIP conalguno de estos métodos, esta diferencia tiende a decrecer considerablemente. Asímismo, se ha visto que durante el proceso iterativo de estimación ambos algoritmosproceden en la práctica de forma análoga, acumulando la masa de probabilidad delas cadenas en las mejores derivaciones [SBC96].

Respecto a las características de los modelos obtenidos, también en el Capítu-lo 3 se ha estudiado el problema de la consistencia de las GIP estimadas con estosalgoritmos. Se ha demostrado que los modelos aprendidos por cualquiera de losdos métodos obtiene una gramática consistente [SB96, SB97b]. Este resultado essumamente importante puesto que valida la corrección de los métodos de estima-ción. El cumplimiento de esta propiedad nos ha permitido derivar igualmente unaserie de importantes propiedades estocásticas que relacionan la muestra utilizadaen el proceso de estimación con el lenguaje generado por la GIP obtenida.

93

94

Otro objetivo de esta tesis era estudiar métodos alternativos de estimación.En el Capítulo 4 se han estudiado y propuesto diferentes algoritmos de estima-ción que hacen uso de un subconjunto específico de derivaciones en el procesode aprendizaje. En uno de ellos las derivaciones escogidas eran las k mejores[SB98b, SB98a, SB99b, SB99a]. En los otros dos algoritmos, el conjunto de de-rivaciones se escogía a partir de información estructural definida sobre la muestra[ABS99]. Como en el caso de los algoritmo IO y VS, también se ha demostra-do que los modelos obtenidos con estos métodos de estimación eran consistentes.Asimismo, se han derivado una serie de importantes propiedades estocásticas querelacionan la muestra de aprendizaje con el lenguaje generado por la GIP obtenida.

Para el algoritmo kVS se ha estudiado la relación entre la función optimizadapor este algoritmo y las optimizadas por los algoritmo IO y VS. Se ha visto quela diferencia entre la funciones puede ser acotada superiormente por una funciónlineal de la muestra, y que, en la práctica, esta cota tiende a decrecer cuando seestima una GIP con cualquiera de los tres algoritmos. Se ha estudiado una versiónmodificada del algoritmo IO que hace uso de muestras parentizadas y se ha pro-puesto un nuevo algoritmo basado en el algoritmo VS que hace uso, igualmente,de cadenas parentizadas.

Todos los algoritmos mencionados han sido probados sobre un conjunto dedatos datos real, obteniendo en todos los casos unos resultados satisfactorios.

Otro propósito importante de esta tesis era estudiar la aplicación de las GIPpara tareas de ML. En el Capítulo 5 se han estudiado los problemas de interpreta-ción subyacentes en ML mediante una GIP. Para ello se ha estudiado un algoritmoque permite calcular la probabilidad de una palabra a partir de la historia anteriorcuando el modelo generador era una GIP. Se ha propuesto un nuevo algoritmo quepermite calcular la probabilidad de la mejor derivación de un prefijo, y que permiteaproximar la probabilidad de una palabra a partir de la historia anterior [SB97a].Se ha estudiado el problema de la integración de las GIP en ML. Se ha hecho unapropuesta en la que una GIP se combina con un modelo de n-gramas para compu-tar la probabilidad de la siguiente palabra [BS99]. El modelo de n-gramas recogeinformación local a nivel del léxico, mientras que la GIP recoge información amás largo término a nivel de categorías. Los modelos estimados en el Capítulo 4se probaron con la propuesta presentada. Los resultados preliminares son satisfac-torios cuando se aplicaba el nuevo algoritmo de análisis propuesto. Los mejoresresultados se han obtenido cuando la GIP utilizada era estimada con el algoritmoIOp.

Desarrollos futuros

Los trabajos futuros que proponemos van en la línea de los problemas que sehan estudiado en la tesis.

En cuanto a estimación de las GIP, existen algunas cuestiones que no se hanconsiderado en esta tesis y que se pretende explorar en el futuro:

95

Un aspecto básico que se debería estudiar es el problema de la inicialización,tanto de las probabilidades como de la gramática característica. En esta línease podría explorar la propuesta presentada para modelos regulares en [SB94],en la que la gramática inicial es obtenida mediante métodos de InferenciaGramatical. Existen diferentes métodos de Inferencia Gramatical que puedenser considerados para tal fin, como [Mar74, Sto94, Che96], y sobre todo[Sak90].

A partir de los métodos de estimación estudiados en esta tesis, cabe plantear-se nuevos métodos de estimación que combinen algunas de las estrategiascomentadas. En particular, una posibilidad que resultaría interesante explo-rar es la estimación de las GIP a partir de las k mejores derivaciones quesean compatibles con la información estructural definida en la muestra.

Otra posibilidad para estimar una GIP se basa en la definición de otras fun-ciones criterio a optimizar. En [BS95] se ha estudiado una propuesta de es-timación en la que la función criterio a optimizar era la minimización de loserrores de clasificación sobre un conjunto de datos. Existen otras propuestaspresentadas para modelos regulares que podrían ser extendidas para incon-textuales en la misma línea de los métodos considerados en esta memoria[Bro87, BBdSM88].

En cuanto a aspectos de interpretación e integración, las líneas que se proponeseguir son:

Estudiar métodos de interpretación basados en el algoritmo de Earley [Ear70,Sto95].

Estudiar métodos de interpretación basado en modelos más simples, comolas gramáticas LR, que permitan la reducción temporal del cálculo de la pro-babilidad de un prefijo.

Continuar explorando la propuesta de modelos híbridos de n-gramas y GIPpresentada en el Capítulo 5.

En la línea del punto anterior, estudiar el algoritmo VLRI como método deetiquetado automático [FJ90, Kne93, Jel98].

Publicaciones relacionadas con la tesis

Algunas de las principales aportaciones realizada en esta tesis han sido ya pu-blicadas. Respecto a la parte de estimación se han publicado resultados relaciona-dos con los siguiente tópicos:

la relación entre las funciones optimizadas por los algoritmo de IO y VS ysu comportamiento en la práctica [SBC96, SB98a],

96

la demostración de la propiedad de consistencia para las GIP obtenidas conlos algoritmo IO y VS [SB97b],

y la estimación mediante los algoritmos kVS [SB98a, SB99b, SB99a] (elúltimo en proceso de revisión), IOp y VSp [ABS99].

Otros aspectos relacionados con la estimación que han sido estudiados y presenta-dos son:

el problema de la inicialización [SB94],

y la estimación con otros criterios [BS95].

Respecto a la parte de interpretación e integración, se ha presentado:

el problema del cálculo de probabilidad de la mejor derivación que genera elprefijo de una cadena [SB97a],

la propuesta de integración de modelos híbridos de n-gramas y GIP (remitidoen [BS99]).

Bibliografía

[ABS99] F. Amaya, J.M. Benedí, and J.A. Sánchez. Learning of stochasticcontext-free grammars from bracketed corpora by means of reesti-mation algorithms. 1999. Aceptado en VIII Spanish Symposium onPattern Recognition and Image Analysis.

[AHU74] A.V. Aho, J.E. Hopcroft, and J.D. Ullman. The Design and Analysisof Computer Algorithms. Addison-Wesley, 1974.

[Bak79] J.K. Baker. Trainable grammars for speech recognition. In Klatt andWolf, editors, Speech Communications for the 97th Meeting of theAcoustical Society of America, pages 31–35. Acoustical Society ofAmerica, June 1979.

[Bau72] L.E. Baum. An inequality and associated maximization technique instatistical estimation for probabilistic functions of markov processes.Inequalities, 3:1–8, 1972.

[BBdSM88] L.R. Bahl, P.E. Brown, P.V. de Souza, and R.L. Mercer. A new al-gorithm for the estimation of hidden markov models parameters. InProc. of ICASSP’88, pages 493–496, 1988.

[BBdSM93] L.R. Bahl, P.E. Brown, P.V. de Souza, and R.L. Mercer. Estimatinghidden markov model parameters so as to maximize speech recogni-tion accuracy. IEEE Trans. Speech and Audio Processing, 1(1):77–83, 1993.

[BE67] L.E. Baum and J.A. Eagon. An inequality with applications to sta-tistical prediction for functions of markov chains. Bull. Amer. Math.Soc., 73:360–363, 1967.

[Bel98] J.R. Bellegarda. A multispan language modeling framework for lar-ge vocabulary speech recognition. IEEE Trans. Speech and AudioProcessing, 6(5):456–476, 1998.

[BJM83] L.R. Bahl, F. Jelinek, and R.L. Mercer. A maximum likelihood ap-proach to continuous speech recognition. IEEE Trans. Pattern Analy-sis and Machine Intelligence, PAMI-5(2):179–190, 1983.

97

98

[BPPM93] P.F. Brown, S.A. Della Pietra, V.J. Della Pietra, and R.L. Mercer. Themathematics of statistical machine translation: parameter estimation.Computational Linguistics, 19(2):263–311, 1993.

[Bro87] P.F. Brown. The acoustic-Modeling Problem in Automatic SpeechRecognition. Ph. d. dissertation, Carnegie-Mellon University, 1987.

[BS95] J.M Benedí and J.A. Sánchez. Corrective training for the estimationof stochastic context-free grammars. In A. Calvo and R. Medina, edi-tors, Proc. VI Spanish Symposium on Pattern Recognition and ImageAnalysis, pages 442–450. AERFAI, April 1995.

[BS96] J.M. Benedí and J.A. Sánchez. Probabilidad de la mejor derivaciónque genera una subcadena inicial a partir de una gramática incontex-tual probabilística. Technical Report DSIC-II/29/96, Departamentode Sistemas Informáticos y Computación. Universidad Politécnica deValencia., 1996.

[BS99] J.M. Benedí and J.A. Sánchez. Combination of n-grams and stochas-tic context-free grammars for language modeling. 1999. Remitido aEUROSPEECH’99.

[BT73] T.L. Booth and R.A. Thompson. Applying probability measures toabstract languages. IEEE Transactions on Computers, C-22(5):442–450, May 1973.

[Cas94] F. Casacuberta. Statistical estimation of stochastic context-free gram-mar using the inside-outside algorithm and a transformation on gram-mars. In R.C. Carrasco and J. Oncina, editors, Grammatical Inferenceand Applications, LNAI 862, pages 119–129. Springer-Verlag, 1994.

[Cas96] F. Casacuberta. Growth transformations for probabilistic functionsof stochastic grammars. IJPRAI, 10(3):183–201, 1996.

[CG98] Z. Chi and S. Geman. Estimation of probabilistic context-free gram-mars. Computational Linguistics, 24(2):299–305, 1998.

[Che96] S.F. Chen. Bayesian Grammar Induction for Language Modeling.Ph. d. dissertation, Harvard University, 1996.

[CJ98] C. Chelba and F. Jelinek. Exploiting syntactic structure for languagemodeling. In Proc. COLING, Montreal, Canada, 1998. University ofMontreal.

[CPG83] R. Chaudhuri, S. Pham, and O.N. Garcia. Solution of an open pro-blem on probabilistic grammars. IEEE Transactions on Computers,C-32(8):748–750, August 1983.

99

[CR83] R. Chaudhuri and A.N.V. Rao. On a property of probabilistic context-free grammars. International Journal of Mathematics and Mathema-tical Science, 6(2):403–406, 1983.

[CRA76] C.M. Cook, A. Rosenfeld, and A.R. Aronson. Grammatical inferenceby hill climbing. Informational Sciences, 10:59–80, 1976.

[CT91] T.M. Cover and J.A. Thomas. Elements of Information Theory. JohnWiley and Sons, 1991.

[DEKM98] R. Durbin, S. Eddy, A. Krogh, and G. Mitchison. Biological sequen-ce analysis: probabilistic models of proteins and nucleic acids. Cam-bridge University Press, 1998.

[Dup93] P. Dupont. Efficient integration of context-free grammars based lan-guage models in continuous speech recognition. In New Advancesand Trends in Speech Recognition and Coding, pages 179–182. NA-TO ASI, 1993.

[Dup96] P. Dupont. Utilisation et apprentissage de modèle de langage pourla reconnaissance de la parole continue. Ph. d. dissertation, ?, 1996.

[Ear70] J. Earley. An efficient context-free parsing algorithm. Communica-tions of the ACM, 8(6):451–455, 1970.

[ER90] Y. Ephraim and L.R. Rabiner. On the relation between modelingapproaches for speech recognition. IEEE on Trans. on InformationTheory, 36(2):372–380, 1990.

[FB75] K.S. Fu and T.L. Booth. Grammatical inference: Introduction andsurvey–part i. IEEE Trans. on System, Man and Cybernetics, SMC-5(1):95–111, January 1975.

[FJ90] S. Roukos F. Jelinek, R. Mercer. Classifying words for improvedstatistical language model. In Proc. ICASSP-90, pages 621–624, De-troit, Michigan, USA, 1990.

[FLSW90] J.A. Feldman, G. Lakoff, A. Stolcke, and S.H. Weber. Miniature lan-guage acquisition: A touchstone for cognitive science. Technical Re-port TR-90-009, International Computer Science Institute, Berkeley,CA, USA, 1990.

[For73] G.D. Forney. The viterbi algorithm. In Proceedings of the IEEE,volume 61(3), pages 268–278, 1973.

[Fu82] K.S. Fu. Syntactic Pattern Recognition and Applications. Prentice-Hall, 1982.

100

[GKNN91] P.S. Gopalakrishnan, D. Kanevsky, A. Nadas, and D. Nahamoo. Aninequality for rational functions with applications to some statisti-cal estimation problems. IEEE Transactions on Information Theory,37(1):107–113, 1991.

[GT78] R.C. González and M.G. Thomason. Syntactic Pattern Recognition:an Introduction. Addisson-Wesley, 1978.

[HAJ90] X.D. Huang, Y. Ariki, and M.A. Jack. Hidden Markov Models forSpeech Recognition. Edinburgh University Press, third edition edi-tion, 1990.

[HU79] J.E. Hopcroft and J.D. Ullman. Introduction to Automata Theory,Languages and Computation. Addison-Wesley, 1979.

[Jel98] F. Jelinek. Statistical Methods for Speech Recognition. MIT Press,1998.

[JL91] F. Jelinek and J.D. Lafferty. Computation of the probability of initialsubstring generation by stochastic context-free grammars. Computa-tional Linguistics, 17(3):315–323, 1991.

[JLM92] F. Jelinek, J.D. Lafferty, and R.L. Mercer. Basic methods of proba-bilistic context-free grammars. In P. Laface and R. De Mori, edi-tors, Speech Recognition and Understanding. Recent Advances, pa-ges 345–360. Springer-Verlag, 1992.

[JWS+95] D. Jurafsky, C. Wooters, J. Segal, A. Stolcke, E. Fosler, G. Tajch-man, and N. Morgan. Using a stochastic context-free grammar as alanguage model for speech recognition. In Proc. ICASSP-95, pages189–192, 1995.

[Kne93] R. Knesser. Improved clustering techniques for class-based statisticallanguage model. In Proc. EUROSPEECH’93, pages 973–976, Berlín,Alemania, 1993.

[LY90] K. Lari and S.J. Young. The estimation of stochastic context-freegrammars using the inside-outside algorithm. Computer, Speech andLanguage, 4:35–56, 1990.

[Mar74] F. J. Maryanski. Inference of Probabilistic Grammars. Ph. d. disser-tation, Dep. Elec. Eng. and Comput. Sci. Univ. Connecticut Storrs,Ct, July 1974.

[Mar94] A. Marzal. Cálculo de las k mejores soluciones a problemas de pro-gramación dinámica. Ph. d. dissertation, Universidad Politécnica deValencia, 1994.

101

[ME91a] N. Merhav and Y. Ephraim. Hidden markov modeling using a domi-nant state sequence with application to speech recognition. ComputerSpeech and Language, 5:327–339, 1991.

[ME91b] N. Merhav and Y. Ephraim. Maximum likelihood hidden markovmodeling using a dominant sequence of states. IEEE. Transactionson Signal Processing, 39(9):2111–2115, 1991.

[Mer93] B. Merialdo. On the locality of the forward-backward algorithm.IEEE Trans. on Speech and Audio Processing, 1(2):255–257, 1993.

[Moo96] T.K. Moon. The expectation-maximization algorithm. IEEE SignalProcessing Magazine, pages 47–60, November 1996.

[MSM93] M.P. Marcus, B. Santorini, and M.A. Marcinkiewicz. Building a lar-ge annotated corpus of english: the penn treebank. ComputationalLinguistics, 19(2):313–330, 1993.

[Ney91] H. Ney. Dynamic programing parsing for context-free grammarsin continous speech recognition. IEEE Trans. Signal Processing,39(2):336–340, February 1991.

[Ney92] H. Ney. Stochastic grammars and pattern recognition. In P. Lafa-ce and R. De Mori, editors, Speech Recognition and Understanding.Recent Advances, pages 319–344. Springer-Verlag, 1992.

[PS92] F. Pereira and Y. Schabes. Inside-outside reestimation from partiallybracketed corpora. In Proceedings of the 30th Annual Meeting of theAssociation for Computational Linguistics, pages 128–135. Univer-sity of Delaware, 1992.

[RJ93] L. Rabiner and B.H. Juang. Fundamentals of speech recognition.Prentice-Hall, 1993.

[Ros95] R. Rosenfeld. The cmu statistical language modeling toolkit and itsuse in the 1994 arpa csr evaluation. In ARPA Spoken Language Tech-nology Workshop, Austin, Texas, USA, 1995.

[Sak90] Y. Sakakibara. Learning context-free grammars from structural da-ta in polynomial time. Theoretical Computer Science, 76:223–242,1990.

[Sar98] A. Sarkar. Conditions on consistency of probabilistic tree adjoininggrammars. In Proc. of COLING98. University of Montreal, 1998.

[SB94] J.A. Sánchez and J.M. Benedí. Statistical inductive learning of regu-lar formal language. In R.C. Carrasco and J. Oncina, editors, Gram-matical Inference and Applications, pages 130–138. Springer-Verlag,1994.

102

[SB96] J.A. Sánchez and J.M. Benedí. Gramáticas incontextuales probabi-lísticas consistentes. Technical Report DSIC-II/20/96, Departamentode Sistemas Informáticos y Computación. Universidad Politécnica deValencia., 1996.

[SB97a] J.A. Sánchez and J.M. Benedí. Computation of the probability of thebest derivation of an initial substring from a stochastic context-freegrammar. In A. Sanfeliu, J.J. Villanueva, and J. Vitrià, editors, Proc.VII Spanish Symposium on Pattern Recognition and Image Analysis,pages 181–186, Barcelon, España, April 1997. AERFAI.

[SB97b] J.A. Sánchez and J.M. Benedí. Consistency of stochastic context-free grammmars from probabilistic estimation based on growth trans-formation. IEEE Trans. Pattern Analysis and Machine Intelligence,19(9):1052–1055, 1997.

[SB98a] J.A. Sánchez and J.M. Benedí. Estimation of the probability distribu-tions of stochastic context-free grammars from the k-best derivations.In In 5th International Conference on Spoken Language Processing,pages 2495–2498, Sidney, Australia, 1998.

[SB98b] J.A. Sánchez and J.M. Benedí. Study of different algorithms for esti-mating the probability distributions of stochastic context-free gram-mars: a new proposal based on the k-best derivations. Technical Re-port DSIC-II/05/98, Departamento de Sistemas Informáticos y Com-putación. Universidad Politécnica de Valencia., 1998.

[SB99a] J.A. Sánchez and J.M. Benedí. Learning of stochastic context-freegrammars by means of estimation algorithms. 1999. Remitido aEUROSPEECH’99.

[SB99b] J.A. Sánchez and J.M. Benedí. Probabilistic estimation of stochasticcontext-free grammar from the k-best derivations. 1999. Acepta-do en VIII Spanish Symposium on Pattern Recognition and ImageAnalysis.

[SBC96] J.A. Sánchez, J.M. Benedí, and F. Casacuberta. Comparison betweenthe inside-outside algorithm and the viterbi algorithm for stochasticcontext-free grammars. In P. Perner, P. Wang, and A. Rosenfeld,editors, Advances in Structural and Syntactical Pattern Recognition,pages 50–59. Springer-Verlag, 1996.

[SJK83] D. Sankoff and (eds.) J.B. Kruskal. Time warps, string edits andmacromolecules. Addison-Wesley, 1983.

[Sto94] A. Stolcke. Bayesian Learning of Probabilistic Language Models.PhD thesis, University of California, Berkeley, CA., 1994.

103

[Sto95] A. Stolcke. An efficient probabilistic context-free parsing algorit-hm that computes prefix probabilities. Computational Linguistics,21(2):165–200, 1995.

[Vid94] E. Vidal. Grammatical inference: an introductory survey. In R.C.Carrasco and J. Oncina, editors, Grammatical Inference and Appli-cations, LNAI 862, pages 1–4. Springer-Verlag, 1994.

[Wet80] C.S. Wetherell. Probabilistic languages: A review and some openquestions. Computing Surveys, 12(4):361–379, 1980.

104

Apéndice A

Experimentos complementarioscon los algoritmos IO y VS

Los siguientes apartados ilustran los resultados obtenidos en los experimentossintéticos con la tarea de los palíndromos (descrita en la Sección 3.2.3 de la memo-ria) con los algoritmos IO y VS, utilizando dos semillas diferentes para generar lasprobabilidades de la gramática inicial. Se comentan brevemente los experimentos ylos resultados. Comentarios más extensos pueden encontrarse a lo largo de la tesis.En cada uno de los pies de las figuras y tablas se indica entre paréntesis a qué figurao tabla corresponde en los capítulos de la tesis, y por tanto a qué experimento. Entodas las gráficas se ha tratado de mantener la escala de ejes igual a la escala de losejes de los experimentos reportados en los diferentes capítulos.

A.1. Experimentos con la semilla 1

Tal como se comentó en la Sección 3.2.3, el comportamiento en la práctica delos algoritmos IO y VS permite poner de manifiesto algunos aspectos que marcandiferencias entre ellos y otros que marcan similitudes. Las diferencias son el nú-mero de derivaciones que los algoritmos necesitan para converger, y la bondad delos modelos; una similitud es la tendencia a acumular la masa de probabilidad delas cadenas en un pequeño número de derivaciones. Para ilustrar estos aspectos, serealizó una experimentación con una tarea sintética descrita en la Sección 3.2.3.La Figura A.1 muestra los resultados obtenidos al estimar una GIP con los algorit-mo IO y VS. Puede verse el número de derivaciones que cada algoritmo necesitapara converger. Nótese como este número es significativamente mayor para el al-goritmo IO que para el algoritmo VS. Respecto a la bondad de los modelos, laverosimilitud de la muestra con el modelo estimado con el algoritmo VS coincideprácticamente con el valor de la función maximizada, y puede verse que es bastan-te menor que la obtenida con el modelo estimado con el algoritmo IO. Por último,respecto a la acumulación de masa de probabilidad en las mejores derivaciones,podemos observar en la Tabla A.1 como ambos algoritmo tienden a acumular la

105

106

masa de probabilidad en un subconjunto reducido de derivaciones. Obsérvese en laFigura A.2 este comportamiento para dos cadenas de la muestra. Puede apreciarsecomo la acumulación es mucho más significativa con el algoritmo VS.

PSfrag replacements

ln Pr(Ω | Gp)

ln Pr(Ω | Gp)

Iteraciones180160140120100806040200

-1400

-1300

-1200

-1100

-1000

-900

-800

-700

-600

Figura A.1: (Figura 3.4) Evolución de las funciones maximizadas con cada algo-ritmo cuando se estimó con el IO (línea continua) y cuando se estimó con el VS(línea discontinua).

Cuadro A.1: (Tabla 3.1) Masa de probabilidad acumulada en el conjunto de cadenasno repetidas de la muestra (columna mdp) y porcentaje de la masa de probabilidadacumulada en las 5 mejores derivaciones (columna 5md).

IOiteración mdp 5md

0 0.003315 52.10 %180 0.174976 82.56 %

VSiteración mdp 5md

0 0.003315 52.10 %11 0.444453 99.98 %

En la Sección 3.3 se estudió la relación entre los algoritmo IO y VS y lasfunciones que maximizaban cada uno de ellos. Se vio que la diferencia entre lasfunciones podía ser acotada por una función lineal de la muestra y logarítmica delnúmero de no terminales de la GIP estimada. Sin embargo, vimos que esta dife-rencia disminuía significativamente en la práctica, en ambos algoritmos, durante elproceso de estimación. En la Figura A.3 puede apreciarse esta circunstancia paraambos algoritmos, mientras que en la Figura A.4 puede verse como la diferencia

107

010

2030

4050

6070

80

02

46

810

1214

1618

-22

-20

-18

-16

-14

-12

-10

PSfrag replacementsIteración (×10)

Derivación

00.5

11.5

22.5

33.5

4

0

2

4

6

8

10

02e-054e-056e-058e-05

0.00010.000120.000140.000160.00018

PSfrag replacementsIteración (×10)

Derivación

Figura A.2: (Figura 3.5) Evolución del logaritmo de la probabilidad de las me-jores derivaciones para la cadena abaaba de la muestra cuando se estimó con elalgoritmo IO (gráfica izquierda) y cuando se estimó con el algoritmo VS (gráficaderecha). La derivación 0 corresponde a la mejor.

entre las dos funciones es bastante menor que la cota teórica planteada. Este hechoaparece más acentuado cuando se estimó con el algoritmo VS.

PSfrag replacements

ln Pr(Ω | Gp)

ln Pr(Ω | Gp)

Iteraciones18016014012010080604020

108642

0-3500

-3000

-2500

-2000

-1500

-1000

-500

PSfrag replacements

ln Pr(Ω | Gp)

ln Pr(Ω | Gp)

Iteraciones

180160140120100

80604020

1086420-3500

-3000

-2500

-2000

-1500

-1000

-500

Figura A.3: (Figura 3.6) Evolución de las funciones optimizadas con los algoritmosIO y VS cuando se estimó la GIP empleando el algoritmo IO (gráfica izquierda) yel algoritmo VS (gráfica derecha).

Puesto que la cota propuesta resultaba bastante pesimista, se propuso otra cotabasada en criterios estructurales. Esta nueva cota consideraba únicamente el núme-ro derivaciones que tenía cada cadena. En la Figura A.5 puede verse la diferenciaentre las funciones optimizadas y su relación con la nueva cota. Nótese como estanueva cota resultó especialmente ajustada cuando se estimó con el algoritmo VS.

En el Capítulo 4 se propuso el algoritmo kVS para estimar las probabilidadesde una GIP y aproximar la verosimilitud de la muestra. Este algoritmo se plan-tea como un compromiso intermedio entre los algoritmo IO y VS, en el cual seconsideran un subconjunto de derivaciones de cada cadena para el proceso de es-timación. Un aspecto importante de este algoritmo es que la elección de valores

108

PSfrag replacements

Iteraciones18016014012010080604020

108642

00

4500

4000

3500

3000

2500

2000

1500

1000

500

PSfrag replacements

Iteraciones

18016014012010080604020

10864200

4500

4000

3500

3000

2500

2000

1500

1000

500

Figura A.4: (Figura 3.7) En línea continua aparece la diferencia entre las dos fun-ciones cuando se estimó la GIP empleando el algoritmo IO (gráfica izquierda) yel algoritmo VS (gráfica derecha). En línea discontinua aparece el valor de la cotateórica.

PSfrag replacements

Iteraciones18016014012010080604020

108642

00

4500

4000

3500

3000

2500

2000

1500

1000

500

PSfrag replacements

Iteraciones

18016014012010080604020

10864200

4500

4000

3500

3000

2500

2000

1500

1000

500

Figura A.5: (Figura 3.8) En línea continua aparece la diferencia entre las dos fun-ciones cuando se estimó la GIP empleando el algoritmo IO (gráfica izquierda) yalgoritmo VS (gráfica derecha). En línea discontinua aparece el valor de la cotabasada en criterios estructurales.

progresivamente mayores de k no implica necesariamente la obtención de modelosmejor estimados. Sin embargo en la práctica si se observa esta tendencia. En laFigura A.6 puede verse este comportamiento para el experimento de los palíndro-mos. Puede observarse como utilizando valores progresivamente mayores de k sepuede obtener modelos mejor estimados. Nótese como en este caso los resultadosalcanzados con k = 5 eran mejores que los resultados alcanzados con k = 10 yk = 15. También es importante destacar el reducido número de iteraciones respec-to al algoritmo IO hasta alcanzar la convergencia.

El algoritmo kVS, al igual que los algoritmos IO y VS, tiende a acumular lamasa de probabilidad de las cadenas en un reducido número de derivaciones decada cadena. Véase en la Tabla A.2 la masa de probabilidad de la muestra sin con-siderar muestras repetidas, y el porcentaje de esta masa que está acumulado en las

109

PSfrag replacements

IO

V S

k = 5

k = 10k = 15

Iteraciones180160140120100806040200

-1400

-1300

-1200

-1100

-1000

-900

-800

-700

-600

Figura A.6: (Figura 4.2) Evolución de las funciones optimizadas por el algoritmokVS en función de k, y su relación con las funciones optimizadas por los algorit-mos IO y VS.

cinco mejores derivaciones. Se puede apreciar que para los valores de k elegidos,la acumulación de masa de probabilidad en las cinco mejores derivaciones es casidel 100 %.

Cuadro A.2: (Tabla 4.1) Relación entre la masa de probabilidad acumulada en elconjunto de cadenas no repetidas de la muestra (columna mdp) y el porcentaje dela masa de probabilidad acumulada en la 5 mejores derivaciones (columna 5md)cuando se utilizan diferente número de derivaciones en la estimación. Los resulta-dos que se muestran son después de la convergencia.

núm. de derivaciones mdp 5md

VS 0.45 97.8 %k = 5 0.26 100 %k = 10 0.19 100 %k = 15 0.20 100 %

IO 0.18 77.8 %

En la Sección 4.4 se estudió la relación entre las funciones optimizadas por losalgoritmos IO y VS cuando se estimaba con el algoritmo kVS. En la Figura A.7puede observarse el comportamiento en la práctica de las diferentes funciones. Pue-de verse que las funciones optimizadas por los algoritmos IO y VS tienden a crecer.

110

Se propuso una cota teórica para la diferencia entre las funciones optimizadas porlos algoritmos VS y kVS (ver Figura A.8) y kVS y IO (ver Figura A.9). Esta cotaera más ajustada con el algoritmo VS que con el algoritmo IO. Cuando se estimacon el algoritmo kVS, las diferencias entre las funciones tienden a decrecer talcomo se observa en las Figuras A.8 y A.9.

5 15

PSfrag replacements

ln Pr(Ω | Gp)

ln Pr(Ω | Gp)

lnPr(Ω,∆Ω | Gp)

Iteraciones20

18161412

10

8642

0-3500

-3000

-2500

-2000

-1500

-1000

-500

Figura A.7: (Figura 4.5) Evolución de las funciones optimizadas cuando se utilizael algoritmo kVS (k = 10) en el proceso de estimación.

En la Sección 4.5 se estudiaron dos propuestas de estimación utilizando mues-tras parentizadas: una de ellas se basaba en el algoritmo IO (algoritmo IOp), mien-tras que la otra se basaba en el algoritmo VS (algoritmo VSp). La motivación deesta propuesta era estudiar si seleccionando un subconjunto de derivaciones paraestimar una GIP de acuerdo con criterios estructurales, permitía obtener mejoresmodelos y con una convergencia más rápida. Estas nuevas versiones de los algorit-mos fueron probadas con la tarea de los palíndromos. En la Figura A.10 puede ver-se como evolucionaban las funciones maximizadas con cada algoritmo. Obsérvesecomo la convergencia es significativamente más rápida con los nuevos algoritmoque con al algoritmo IO. En este experimento puede observarse que el máximo al-canzado con el algoritmo IOp es mayor el máximo alcanzado con el algoritmo IO.En el caso del algoritmo VS y VSp sucedió lo contrario. Como ya comentamos,esto es debido a la sensibilidad del algoritmo VSp al proceso de inicialización.

111

5 15

PSfrag replacements

Iteraciones

180160140120100806040

2010

8642

00

4500

4000

3500

3000

2500

2000

1500

1000

500

Figura A.8: (Figura 4.6) En línea continua aparece la diferencia entre las funcionesoptimizadas por los algoritmo IO y VS cuando se estimó la GIP empleando elalgoritmo kVS (k = 10). En línea discontinua aparece el valor teórico de la cota.

5 15

PSfrag replacements

Iteraciones

180160140120100806040

2010

8642

00

4500

4000

3500

3000

2500

2000

1500

1000

500

Figura A.9: (Figura 4.7) En línea continua aparece la diferencia entre las funcionesoptimizadas por los algoritmos kVS y IO cuando se utilizó el algoritmo kVS (k =10) en la estimación. En línea discontinua aparece el valor teórico de la cota.

112PSfrag replacements

IO

V S

IOp

V Sp

Iteraciones180160140120100806040200

-1800

-1700

-1600

-1500

-1400

-1300

-1200

-1100

-1000

-900

-800

-700

Figura A.10: (Figura 4.8) Evolución de las funciones maximizadas con cada algo-ritmo cuando se estimó con el IO, cuando se estimó con el VS, cuando se estimócon el IOp y cuando se estimó con el VS con muestras parentizadas VSp.

113

A.2. Experimentos con la semilla 2

En esta sección se reproducen los experimentos de las sección anterior y dela tesis con la tarea de los palíndromos, pero con otra semilla para generar lasprobabilidades de iniciales de la GIP a partir de la cual estimar un nuevo modelo.

La Figura A.11 ilustra los óptimos alcanzados con los algoritmos IO y VS. Ob-sérvese como el número de iteraciones que necesita el algoritmo VS para convergeres notablemente menor que el número de iteraciones que necesita el algoritmo IO.

PSfrag replacements

ln Pr(Ω | Gp)

ln Pr(Ω | Gp)

Iteraciones200150100500

-1400

-1300

-1200

-1100

-1000

-900

-800

-700

-600

Figura A.11: (Figura 3.4) Evolución de las funciones maximizadas con cada algo-ritmo cuando se estimó con el IO (línea continua) y cuando se estimó con el VS(línea discontinua).

La Tabla A.3 muestra la masa de probabilidad acumulada en las mejores deri-vaciones cuando se estimó con el algoritmo IO y cuando se estimó con el algoritmoVS. En la Figura A.12 puede apreciarse esta circunstancia para dos cadenas de lamuestra.

Cuadro A.3: (Tabla 3.1) Masa de probabilidad acumulada en el conjunto de cadenasno repetidas de la muestra (columna mdp) y porcentaje de la masa de probabilidadacumulada en las 5 mejores derivaciones (columna 5md).

IOiteración mdp 5md

0 0.002949 42.12 %215 0.174563 73.85 %

VSiteración mdp 5md

0 0.002949 42.12 %7 0.048673 91.89 %

114

010

2030

4050

6070

80

02

46

810

12

-22

-20

-18

-16

-14

-12

-10

PSfrag replacementsIteración (×10)

Derivación

02

46

810

1214

1618

01

23

45

6

-17-16-15-14-13-12-11-10-9-8

PSfrag replacementsIteración (×10)

Derivación

Figura A.12: (Figura 3.5) Evolución del logaritmo de la probabilidad de las me-jores derivaciones para la cadena abaaba de la muestra cuando se estimó con elalgoritmo IO (gráfica izquierda) y cuando se estimó con el algoritmo VS (gráficaderecha). La derivación 0 corresponde a la mejor.

La Figura A.13 muestra como evolucionan las funciones optimizadas con losalgoritmos IO y VS dependiendo de qué algoritmo se utilice en proceso de estima-ción. En la Figura A.14 puede verse como la diferencia entre las funciones tiendea decrecer durante el proceso de estimación para los dos algoritmos, y que estadiferencia es notablemente menor que la cota teórica propuesta al final del procesode estimación. Esto es más apreciable cuando se estima con el algoritmo VS.

PSfrag replacements

ln Pr(Ω | Gp)

ln Pr(Ω | Gp)

Iteraciones20015010050

7654321

0-3500

-3000

-2500

-2000

-1500

-1000

-500

PSfrag replacements

ln Pr(Ω | Gp)

ln Pr(Ω | Gp)

Iteraciones

20015010050

76543210-3500

-3000

-2500

-2000

-1500

-1000

-500

Figura A.13: (Figura 3.6) Evolución de las funciones optimizadas con los algorit-mos IO y VS cuando se estimó la GIP empleando el algoritmo IO (gráfica izquier-da) y el algoritmo VS (gráfica derecha).

La Figura A.15 muestra la diferencia entre las funciones y su relación con lacota teórica basada en criterios estructurales. Nótese como en el caso del algoritmoVS esta cota es más ajustada ya que el proceso de estimación asigna probabilidadnula a muchas reglas, con lo que el número de derivaciones de cada cadena decrecesignificativamente durante el proceso de estimación.

Respecto al algoritmo kVS, la Figura A.16 ilustra los máximos alcanzados

115

PSfrag replacements

Iteraciones20015010050

7654321

0

4500

4000

3500

3000

2500

2000

1500

1000

500

PSfrag replacements

Iteraciones

200150100

50

765432100

4500

4000

3500

3000

2500

2000

1500

1000

500

Figura A.14: (Figura 3.7) En línea continua aparece la diferencia entre las dosfunciones cuando se estimó la GIP empleando el algoritmo IO (gráfica izquierda)y el algoritmo VS (gráfica derecha). En línea discontinua aparece el valor de la cotateórica.

PSfrag replacements

Iteraciones20015010050

7654321

00

4500

4000

3500

3000

2500

2000

1500

1000

500

PSfrag replacements

Iteraciones

200150100

50

765432100

4500

4000

3500

3000

2500

2000

1500

1000

500

Figura A.15: (Figura 3.8) En línea continua aparece la diferencia entre las dosfunciones cuando se estimó la GIP empleando el algoritmo IO (gráfica izquierda)y el algoritmo VS (gráfica derecha). En línea discontinua aparece el valor de la cotabasada en criterios estructurales.

para diferentes valores de k y su relación respecto a los algoritmo IO y VS. Cabedestacar de una lado, los óptimos alcanzados para valores relativamente pequeñosde k, y de otro lado, el reducido número de iteraciones hasta converger respectoal algoritmo IO. La Tabla A.4 muestra la acumulación de masa de probabilidadque se produce en las mejores derivaciones, y su relación con los algoritmos IO yVS. Puede observarse como para el algoritmo kVS, prácticamente la totalidad dela masa de probabilidad queda recogida en las cinco mejores derivaciones.

La Figura A.17 muestra el comportamiento de las funciones optimizadas porlos algoritmo IO y VS cuando se estimó con el algoritmo kVS (k = 10). En ge-neral, las dos funciones tienden a crecer. La Figura A.18 representa la diferenciateórica entre las funciones optimizadas por los algoritmo VS y kVS, y el comporta-miento de esta diferencia en la práctica cuando se estimó con este último algoritmo.

116

PSfrag replacements

IO

V S

k = 5k = 10

k = 15

Iteraciones200150100500

-1400

-1300

-1200

-1100

-1000

-900

-800

-700

-600

Figura A.16: (Figura 4.2) Evolución de las funciones optimizadas por el algoritmokVS en función de k, y su relación con las funciones optimizadas por los algorit-mos IO y VS.

Cuadro A.4: (Tabla 4.1) Relación entre la masa de probabilidad acumulada en elconjunto de cadenas no repetidas de la muestra (columna mdp) y el porcentaje dela masa de probabilidad acumulada en la 5 mejores derivaciones (columna 5md)cuando se utilizan diferente número de derivaciones en la estimación. Los resulta-dos que se muestran son después de la convergencia.

núm. de derivaciones mdp 5md

VS 0.049 91.8 %k = 5 0.16 100 %k = 10 0.16 100 %k = 15 0.16 100 %

IO 0.18 72.2 %

La Figura A.19 muestra algo similar, pero respecto al algoritmo IO. Destacar quela cota teórica es mucho más ajustada respecto a la función optimizada con el al-goritmo VS que respecto a la función optimizada con el algoritmo IO.

Por último, la Figura A.20 refleja el comportamiento de las funciones optimi-zadas con los algoritmo IO, VS, IOp y VSp. Nótese como la convergencia es másrápida con las versiones parentizadas de los algoritmos. También puede observarseque el máximo alcanzado con el algoritmo IOp es mayor que el máximo alcanzadocon el algoritmo IO. En el caso del algoritmo VS y VSp sucedió lo contrario.

117

5 15

PSfrag replacements

ln Pr(Ω | Gp)

ln Pr(Ω | Gp)

lnPr(Ω,∆Ω | Gp)

Iteraciones20

18161412

10

8642

0-3500

-3000

-2500

-2000

-1500

-1000

-500

Figura A.17: (Figura 4.5) Evolución de las funciones optimizadas cuando se utilizael algoritmo kVS (k = 10) en el proceso de estimación.

5 15

PSfrag replacements

Iteraciones

180160140120100806040

2010

8642

00

4500

4000

3500

3000

2500

2000

1500

1000

500

Figura A.18: (Figura 4.6) En línea continua aparece la diferencia entre las funcio-nes optimizadas por los algoritmo VS y kVS cuando se utilizó el algoritmo kVS(k = 10) en la estimación. En línea discontinua aparece el valor teórico de la cota.

118

5 15

PSfrag replacements

Iteraciones

180160140120100

806040

2010

8642

00

4500

4000

3500

3000

2500

2000

1500

1000

500

Figura A.19: (Figura 4.7) En línea continua aparece la diferencia entre las funcio-nes optimizadas por los algoritmos kVS y IO cuando se utilizó el algoritmo kVS(k = 10) en la estimación. En línea discontinua aparece el valor teórico de la cota.

PSfrag replacements

IO

V S

IOp

V Sp

Iteraciones180160140120100806040200

-1800

-1600

-1400

-1200

-1000

-800

-600

-400

Figura A.20: (Figura 4.8) Evolución de las funciones maximizadas con cada algo-ritmo cuando se estimó con el IO, cuando se estimó con el VS, cuando se estimócon el IOp y cuando se estimó con el VSp.

Apéndice B

Demostraciones de teoremas ycorolarios

En este apéndice se demuestran los teoremas y corolarios que no fueron demos-trados en el desarrollo de la memoria. En primer lugar demostramos el cumplimien-to de la propiedad de consistencia para los modelos estimados con el algoritmo VS.A continuación demostramos como el algoritmo VS permite obtener unos modelosque recogen gran parte de la información estocástica presente en la muestra, deforma análoga a como sucedía con el algoritmo IO. Estas mismas propiedades sondemostradas a continuación para los algoritmos de estimación que consideran unsubconjunto de derivaciones en el proceso de aprendizaje. Por último se demuestrauna propiedad que permite garantizar el cómputo de la probabilidad de una subca-dena inicial con el algoritmo LRI.

B.1. Demostración del Teorema 3.4.2

La demostración del Teorema 3.4.2 que presentamos a continuación es similara la del Teorema 3.4.1 pero considerando únicamente la mejor derivación de cadacadena de la muestra.

La matriz de esperanzas de no terminales E asociada a la GIP Gp es:

eij =∑

(A→α)∈ΓAi

p(A → α)N(Aj , α) =

∑x∈Ω

∑(A→α)∈ΓAi

N(A → α, dx)N(Aj , α)∑

x∈Ω N(Ai, dx).

Simplificando notación tenemos:

ei =∑

x∈Ω

N(Ai, dx), (B.1)

hij =∑

x∈Ω

∑

(A→α)∈ΓAi

N(A → α, dx)N(Aj , α).

119

120

Con lo cual eij = hij/ei.Conjeturamos a continuación que se cumplen las siguiente ecuaciones:

e1 = λ + h11 + h21 + . . . + h|N |1 (B.2.1)

e2 = h12 + h22 + . . . + h|N |2 (B.2.2)

...

e|N | = h1|N | + h2|N | + . . . + h|N ||N | (B.2.|N|)

donde λ es el número de cadenas en Ω.Vamos a demostrar que se cumple para (B.2.1). La parte derecha de la ecuación

es:

λ +

|N |∑

i=1

hi1 =∑

x∈Ω

1 +

|N |∑

i=1

∑

x∈Ω

∑

(A→α)∈ΓAi

N(A → α, dx)N(A1, α)

=∑

x∈Ω

1 +∑

x∈Ω

N(A1,dx)−1︷ ︸︸ ︷|N |∑

i=1

∑

(A→α)∈ΓAi

N(A → α, dx)N(A1, α) .

(B.3)

Observemos que N(A1, dx) representa el número de no terminales A1 (= S) quehan aparecido en la parte derecha de las reglas que participan en la derivación dx.No se considera el axioma inicial, y por ello la expresión anterior es igual a:

∑

x∈Ω

1 +∑

x∈Ω

(N(A1, dx) − 1) =∑

x∈Ω

N(A1, dx) = e1.

Algo similar se puede demostrar para (B.2.2), . . . , (B.2.|N |), con lo que quedademostrada la conjetura.

Demostraremos a continuación que Gp es consistente haciendo uso del Teore-ma 2.3.2. Demostraremos que la suma infinitaQ = I + E + E2 + . . . converge yque por ello el radio espectral de E es menor que uno. Primero demostramos quelos elementos de la primera fila de Q (la fila asociada al axioma inicial A1 = S)están acotados. Para demostrar esto definimos la suma parcial de n + 1 términosW (n) = I + E + E2 + . . .+ En. Nos referiremos como w

(n)ij al elemento ij-ésimo

de la matriz W (n). Dado que En+1 = EnE, tenemos que:

e(n+1)ij = e

(n)i1 e1j + e

(n)i2 e2j + . . . + e

(n)i|N |e|N |j

= e(n)i1

h1j

e1+ e

(n)i2

h2j

e2+ . . . + e

(n)i|N |

h|N |j

e|N |.

121

A partir de la expresión anterior tenemos que:

e(0)11 = 1,

e(1)11 =

h11

e1,

e(2)11 = e

(1)11

h11

e1+ e

(1)12

h21

e2+ . . . + e

(1)1|N |

h|N |1

e|N |,

...

e(n+1)11 = e

(n)11

h11

e1+ e

(n)12

h21

e2+ . . . + e

(n)1|N |

h|N |1

e|N |.

Sumando la serie de ecuaciones anteriores:

w(n+1)11 = 1 + (1 + e

(1)11 + e

(2)11 + . . . + e

(n)11 )

h11

e1+ . . .

+(e(1)1|N | + e

(2)1|N | + . . . + e

(n)1|N |)

h|N |1

e|N |

= 1 + w(n)11

h11

e1+ . . . + w

(n)1|N |

h|N |1

e|N |.

De forma similar:

w(n+1)12 = w

(n)11

h12

e1+ . . . + w

(n)1|N |

h|N |2

e|N |,

...

w(n+1)1|N | = w

(n)11

h1|N |

e1+ . . . + w

(n)1|N |

h|N ||N |

e|N |.

Supongamos por hipótesis de inducción que:

w(n)11 ≤ e1

λ, w

(n)12 ≤ e2

λ, . . . , w

(n)1|N | ≤

e|N |

λ. (B.4)

Entonces, haciendo uso de (B.2.1), . . . , (B.2.|N|) y dividiendo por λ, tenemos que:

w(n+1)11 ≤ 1 +

e1

λ

h11

e1+ . . . +

e|N |

λ

h|N |1

e|N |=

e1

λ

w(n+1)12 ≤ e1

λ

h12

e1+ . . . +

e|N |

λ

h|N |1

e|N |=

e2

λ

...

w(n+1)1|N | ≤ e1

λ

h1|N |

e1+ . . . +

e|N |

λ

h|N ||N |

e|N |=

e|N |

λ

Para n = 0 y n = 1, la demostración de (B.4) es inmediata, y por ello se cumpleque w

(n)1i ≤ ei/λ para i = 1, 2, . . . , |N | y para todo n. Observemos que w

(n)1i ≤

122

w(n+1)1i y por ello w

(n)1i es una secuencia creciente acotada superiormente. Por tanto

existe el límite lımn→∞ w(n)1i = w1i para cada i y w1i ≤ ei/λ.

En segundo lugar hay que demostrar que los elementos del resto de filas de Q

están también acotados. Esto lo haremos demostrando que existe el límite lımn→∞ w(n)ji

para j = 2, 3, . . . , |N | y i = 1, 2, . . . , |N |. Para demostrar esto, observemos que

existe un entero d ≥ 1 que puede ser diferente para cada i, tal que e(d)1i > 0. Tal

como se comenta en [CPG83], este d existe claramente puesto que si para algún i,e(k)1i = 0 para todo k, entonces el no terminal Ai no es alcanzable desde el sím-

bolo inicial y por tanto las reglas Ai → α (∀α) son innecesarias y L(G) se puedegenerar sin utilizar esas producciones. Observemos que:

0 ≤ e(d)1j w

(n)ji = e

(d)1j eji + e

(d)1j e

(2)ji + . . . + e

(d)1j e

(n)ji

≤|N |∑

l=1

e(d)1l eli +

|N |∑

l=1

e(d)1l e

(2)li + . . . +

|N |∑

l=1

e(d)1l e

(n)li

= e(d+1)1i + e

(d+2)1i + . . . + e

(d+n)1i ≤ w

(d+n)1i ≤ w1i,

y por ello existe el límite lımn→∞ w(n)ji = wji (j = 2, 3, . . . , |N |; i = 1, 2, . . . , |N |).

Observemos que hemos supuesto que i 6= j, pero el mismo razonamiento se puedeaplicar cuando i = j. Así pues, la suma infinita I +E + E2 + . . . es convergente.Por tanto, por el Teorema 2.3.2, el radio espectral de E es menor que uno y Gp esconsistente.

B.2. Demostración del Corolario 3.4.2

La demostración del Corolario 3.4.2 es similar a la del Corolario 3.4.1.Para demostrar la primera ecuación, sabemos por el Teorema 3.4.2 que w1i =

(Q)1i = ei/λ para i = 1, 2, . . . , |N |. Haciendo uso de (B.1) y dado que |dx| =∑|N |i=1 N(Ai, dx):

LED(Gp) =

|N |∑

i=1

(Q)1i =

∑|N |i=1 ei

λ=

∑|N |i=1

∑x∈Ω N(Ai, dx)

λ=

∑x∈Ω |dx|

λ.

Por tanto se cumple la primera de la ecuaciones.Vamos a demostrar la segunda de las ecuaciones. Sea Z = (zij), 1 ≤ i ≤ |N |,

1 ≤ j ≤ |Σ|, la matriz de esperanzas de terminales de Gp. Entonces:

zij =∑

(A→α)∈ΓAi

p(A → α)N(aj , α)

=

∑x∈Ω

∑(A→α)∈ΓAi

N(A → α, dx)N(aj , α)∑

x∈Ω N(Ai, dx). (B.5)

123

Observemos que el denominador de la expresión anterior es ei definido en (B.1).Por tanto:

LEC(Gp) =

|Σ|∑

j=1

|N |∑

i=1

(Q)1i(Z)ij =

|Σ|∑

j=1

|N |∑

i=1

ei

λzij

=

∑x∈Ω

|x|︷ ︸︸ ︷|Σ|∑

j=1

|N |∑

i=1

∑

(A→α)∈ΓAi

N(A → α, dx)N(aj , α)

λ

=

∑x∈Ω |x|λ

.

Por tanto se cumple la segunda de las ecuaciones.Para la demostración de la tercera ecuación observemos que a partir del Teore-

ma 2.3.4, el Teorema 3.4.2 y la expresión (B.5) tenemos que para todo ai ∈ Σ:

d(ai, L(Gp) =(1 0 0 . . . 0)Q Zi

LEC(Gp)=

∑|N |j=1 q1j zji∑x∈Ω |x|/λ

=

∑x∈Ω

N(ai,x)︷ ︸︸ ︷|N |∑

j=1

∑

(A→α)∈ΓAj

N(A → α, dx)N(ai, α)

∑x∈Ω |x|

=

∑x∈Ω N(ai, x)∑

x∈Ω |x| .

B.3. Demostración del Teorema 4.2.1

La demostración del Teorema 4.2.1 que presentamos a continuación es similara la del Teorema 3.4.1 pero considerando un subconjunto específico de derivacio-nes de cada cadena de la muestra.

La matriz de esperanzas de no terminales E asociada a la GIP Gp es:

eij =∑

(A→α)∈ΓAi

p(A → α)N(Aj , α)

=

∑x∈Ω

1Pr(x,∆x|Gp)

∑dx∈∆x

Pr(x, dx | Gp)∑

(A→α)∈ΓAiN(A → α, dx)N(Aj , α)

∑x∈Ω

1Pr(x,∆x|Gp)

∑dx∈∆x

N(Ai, dx) Pr(x, dx | Gp).

124

Vamos a continuación a simplificar la notación:

ei =∑

x∈Ω

1

Pr(x,∆x | Gp)

∑

dx∈∆x

N(Ai, dx) Pr(x, dx | Gp), (B.6)

hij =∑

x∈Ω

1

Pr(x,∆x | Gp)

∑

dx∈∆x

Pr(x, dx | Gp)∑

(A→α)∈ΓAi

N(A → α, dx)N(Aj , α).

De esta forma eij = hij/ei.A continuación conjeturamos que se cumplen las siguiente ecuaciones:

e1 = λ + h11 + h21 + . . . + h|N |1 (B.7.1)

e2 = h12 + h22 + . . . + h|N |2 (B.7.2)

...

e|N | = h1|N | + h2|N | + . . . + h|N ||N | (B.7.|N|)

donde λ es el número de cadenas en Ω.Vamos a demostrar que la conjetura se cumple para (B.7.1). La parte derecha

de la ecuación es:

λ +

|N |∑

i=1

hi1 =∑

x∈Ω

1

Pr(x,∆x | Gp)

∑

dx∈∆x

Pr(x, dx | Gp)

+

|N |∑

i=1

∑

x∈Ω

1

Pr(x,∆x | Gp)

∑

dx∈∆x

Pr(x, dx | Gp)∑

(A→α)∈ΓAi

N(A → α, dx)N(A1, α)

=∑

x∈Ω

1

Pr(x,∆x | Gp)

∑

dx∈∆x

Pr(x, dx | Gp)

+∑

x∈Ω

1

Pr(x,∆x | Gp)

∑

dx∈∆x

Pr(x, dx | Gp)

N(A1,dx)−1︷ ︸︸ ︷|N |∑

i=1

∑

(A→α)∈ΓAi

N(A → α, dx)N(A1, α) .

(B.8)

Observemos que N(A1, dx) representa el número de no terminales A1 (= S) quehan aparecido en la parte derecha de las reglas que participan en la derivación dx.No se considera el axioma inicial, y por ello la expresión anterior es igual a:

∑

x,∆x∈Ω

1

Pr(x,∆x | Gp)

∑

dx∈∆x

Pr(x, dx | Gp)

+∑

x∈Ω

1

Pr(x,∆x | Gp)

∑

dx∈∆x

Pr(x, dx | Gp)(N(A1, dx) − 1) =

∑

x∈Ω

1

Pr(x,∆x | Gp)

∑

dx∈∆x

Pr(x, dx | Gp)N(A1, dx) = e1.

125

Algo similar se puede demostrar para (B.7.2), . . . , (B.7.|N |), con lo que quedademostrada la conjetura.

Demostraremos a continuación que Gp es consistente haciendo uso del Teore-ma 2.3.2. Demostraremos que la suma infinitaQ = I + E + E2 + . . . converge yque por ello el radio espectral de E es menor que uno. Primero demostramos quelos elementos de la primera fila de Q (la fila asociada al axioma inicial A1 = S)están acotados. Para demostrar esto definimos la suma parcial de n + 1 términosW (n) = I + E + E2 + . . .+ En. Nos referiremos como w

(n)ij al elemento ij-ésimo

de la matriz W (n). Dado que En+1 = EnE, tenemos que:

e(n+1)ij = e

(n)i1 e1j + e

(n)i2 e2j + . . . + e

(n)i|N |e|N |j

= e(n)i1

h1j

e1+ e

(n)i2

h2j

e2+ . . . + e

(n)i|N |

h|N |j

e|N |.

A partir de la expresión anterior tenemos que:

e(0)11 = 1,

e(1)11 =

h11

e1,

e(2)11 = e

(1)11

h11

e1+ e

(1)12

h21

e2+ . . . + e

(1)1|N |

h|N |1

e|N |,

...

e(n+1)11 = e

(n)11

h11

e1+ e

(n)12

h21

e2+ . . . + e

(n)1|N |

h|N |1

e|N |.

Sumando la serie de ecuaciones anteriores:

w(n+1)11 = 1 + (1 + e

(1)11 + e

(2)11 + . . . + e

(n)11 )

h11

e1+ . . .

+(e(1)1|N | + e

(2)1|N | + . . . + e

(n)1|N |)

h|N |1

e|N |

= 1 + w(n)11

h11

e1+ . . . + w

(n)1|N |

h|N |1

e|N |.

De forma similar:

w(n+1)12 = w

(n)11

h12

e1+ . . . + w

(n)1|N |

h|N |2

e|N |,

...

w(n+1)1|N | = w

(n)11

h1|N |

e1+ . . . + w

(n)1|N |

h|N ||N |

e|N |.

Supongamos por hipótesis de inducción que:

w(n)11 ≤ e1

λ, w

(n)12 ≤ e2

λ, . . . , w

(n)1|N | ≤

e|N |

λ. (B.9)

126

Entonces, haciendo uso de (B.7.1), . . . , (B.7.|N|) y dividiendo por λ, tenemos que:

w(n+1)11 ≤ 1 +

e1

λ

h11

e1+ . . . +

e|N |

λ

h|N |1

e|N |=

e1

λ

w(n+1)12 ≤ e1

λ

h12

e1+ . . . +

e|N |

λ

h|N |1

e|N |=

e2

λ

...

w(n+1)1|N | ≤ e1

λ

h1|N |

e1+ . . . +

e|N |

λ

h|N ||N |

e|N |=

e|N |

λ

Para n = 0 y n = 1, la demostración de (B.9) es inmediata, y por ello se cumpleque w

(n)1i ≤ ei/λ para i = 1, 2, . . . , |N | y para todo n. Observemos que w

(n)1i ≤

w(n+1)1i y por ello w

(n)1i es una secuencia creciente acotada superiormente. Por tanto

existe el límite lımn→∞ w(n)1i = w1i para cada i y w1i ≤ ei/λ.

En segundo lugar hay que demostrar que los elementos del resto de filas de Q

están también acotados. Esto lo haremos demostrando que existe el límite lımn→∞ w(n)ji

para j = 2, 3, . . . , |N | y i = 1, 2, . . . , |N |. Para demostrar esto, observemos que

existe un entero d ≥ 1 que puede ser diferente para cada i, tal que e(d)1i > 0. Tal

como se comenta en [CPG83], este d existe claramente puesto que si para algún i,e(k)1i = 0 para todo k, entonces el no terminal Ai no es alcanzable desde el sím-

bolo inicial y por tanto las reglas Ai → α (∀α) son innecesarias y L(G) se puedegenerar sin utilizar esas producciones. Observemos que:

0 ≤ e(d)1j w

(n)ji = e

(d)1j eji + e

(d)1j e

(2)ji + . . . + e

(d)1j e

(n)ji

≤|N |∑

l=1

e(d)1l eli +

|N |∑

l=1

e(d)1l e

(2)li + . . . +

|N |∑

l=1

e(d)1l e

(n)li

= e(d+1)1i + e

(d+2)1i + . . . + e

(d+n)1i ≤ w

(d+n)1i ≤ w1i,

y por ello existe el límite lımn→∞ w(n)ji = wji (j = 2, 3, . . . , |N |; i = 1, 2, . . . , |N |).

Observemos que hemos supuesto que i 6= j, pero el mismo razonamiento se puedeaplicar cuando i = j. Así pues, la suma infinita I +E + E2 + . . . es convergente.Por tanto, por el Teorema 2.3.2, el radio espectral de E es menor que uno y Gp esconsistente.

B.4. Demostración del Corolario 4.2.1

La demostración del Corolario 4.2.1 es similar a la del Corolario 3.4.1.Para demostrar la primera ecuación, sabemos por el Teorema 4.2.1 que w1i =

(Q)1i = ei/λ para i = 1, 2, . . . , |N |. Haciendo uso de (B.6), y dado que |dx| =

127

∑|N |i=1 N(Ai, dx):

LED(Gp) =

|N |∑

i=1

(Q)1i =

∑|N |i=1 ei

λ=

∑x∈Ω

1Pr(x,∆x|Gp)

∑dx∈∆x

Pr(x, dx | Gp) |dx|λ

.

Por tanto se cumple la primera de las ecuaciones.Vamos a demostrar a continuación la segunda de las ecuaciones. Sea Z = (zij),

1 ≤ i ≤ |N |, 1 ≤ j ≤ |Σ|, la matriz de esperanzas de terminales de Gp. Entonces:

zij =∑

(A→α)∈ΓAi

p(A → α)N(aj , α)

=

∑x∈Ω

1Pr(x,∆x|Gp)

∑dx∈∆x

Pr(x, dx | Gp)∑

(A→α)∈ΓAiN(A → α, dx)N(aj , α)

∑x∈Ω

1Pr(x,∆x|Gp)

∑dx∈∆x

N(Ai, dx) Pr(x, dx | Gp).

(B.10)

Observemos que el denominador de la expresión anterior es ei definido en (B.6).Por tanto:

LEC(Gp) =

|Σ|∑

j=1

|N |∑

i=1

(Q)1i(Z)ij =

|Σ|∑

j=1

|N |∑

i=1

ei

λzij

=

∑x∈Ω

1Pr(x,∆x|Gp)

∑dx∈∆x

Pr(x, dx | Gp)

|x|︷ ︸︸ ︷|Σ|∑

j=1

|N |∑

i=1

∑

(A→α)∈ΓAi

N(A → α, dx)N(aj , α)

λ

=

∑x∈Ω |x|λ

.

Por tanto se cumple la ecuación LEC(Gp) = LMC(Ω).Para demostrar la última ecuación observemos que a partir del Teorema 2.3.4,

el Teorema 4.2.1 y la expresión (B.10) tenemos que para todo ai ∈ Σ:

d(ai, L(Gp) =(1 0 0 . . . 0)Q Zi

LEC(Gp)=

∑|N |j=1 q1j zji∑x∈Ω |x|/λ

=

∑x∈Ω

1Pr(x,∆x|Gp)

∑dx∈∆x

Pr(x, dx | Gp)

N(ai,x)︷ ︸︸ ︷|N |∑

j=1

∑

(A→α)∈ΓAj

N(A → α, dx)N(ai, α)

∑x∈Ω |x|

=

∑x∈Ω N(ai, x)∑

x∈Ω |x| .

128

B.5. Cálculo de la matriz T

A continuación vamos a demostrar que el cálculo de la expresión (5.8):

T = R + R2 + R3 + · · ·

es posible si la GIP no tiene símbolo inútiles. La demostración que presentamosaquí es similar a la que se presenta en [Sto95].

Propiedad B.5.1. Si G es una GIP sin símbolo inútiles, entonces los valores de lamatriz Rn tienden a cero cuando n tiende a infinito.

DemostraciónDada la matriz R = (rij), 1 ≤ i, j ≤ |N |, rij representa la probabilidad de que

el no terminal Ai derive directamente el no terminal Aj como no terminal más a la

izquierda en una de sus reglas. De forma análoga, en la matriz Rn = (r(n)ij ), n ≥ 1,

r(n)ij representa la probabilidad de que el no terminal Ai derive el no terminal Aj

como no terminal más a la izquierda con n − 1 no terminales intermedios. Si laGIP no contiene símbolo inútiles r

(n)ij tiende a cero cuando n tiende a infinito, por

lo que la suma R + R2 + R3 + · · · es convergente.

Apéndice C

Resultados complementarios delos experimentos con el corpusPenn Treebank

Los siguientes apartados muestran los resultados obtenidos en los experimentosdescritos en la tesis sobre el corpus Penn Treebank, pero utilizando dos semillasdiferentes para generar las probabilidades de la gramática inicial.

El conjunto de datos se organizó en cinco particiones de aproximadamente lamisma talla. A partir de estas particiones se definieron tres experimentos cuyasprincipales características aparecen recogidas en la Tabla 4.6. En la Sección 4.6puede verse una descripción más detallada del conjunto de datos.

En este apéndice se describen brevemente los experimentos y se comentan losresultados obtenidos. En el desarrollo de la tesis se pueden encontrar comentariosmás extensos. En cada uno de los pies de las figuras y tablas se indica entre parén-tesis a qué figura o tabla corresponde en los capítulos de la tesis y por tanto a quéexperimento.

C.1. Resultados con la semilla 1

En la experimentación realizada con el algoritmo kVS se pretendía estudiardos importantes aspectos del mismo: la evolución del algoritmo en función de k, yla dependencia respecto a la talla del conjunto de entrenamiento. En la Tabla C.1puede verse la perplejidad del conjunto de test cuando se utilizaron diferentes va-lores de k (la Tabla 4.7 muestra la perplejidad de este conjunto con un modelo detrigramas). Nótese como la perplejidad tiende, en general, a decrecer a medida queaumenta k. Sin embargo, en alguna ocasión puede suceder lo contrario, como seexplicó en la Sección 4.3.1. La Tabla C.2 muestra como se comporta el algoritmoa medida que varía la talla del conjunto de entrenamiento. En este experimento,el comportamiento del algoritmo kVS fue contrario al deseado, no apreciándosemejoras significativas a medida que aumentaba la talla de conjunto de datos.

129

130

Cuadro C.1: (Tabla 4.8) Perplejidad del conjunto de test para diferentes valores dek. La columna Ts indica la partición utilizada para el test. El conjunto de entrena-miento estaba compuesto por las otras cuatro particiones que no aparecen en estacolumna. Las tallas de cada partición pueden consultarse en la Tabla 4.6.

Ts VS k = 3 k = 5 k = 7

P5 26.38 25.38 25.70 26.08P3 26.72 24.92 25.10 24.50P1 25.25 24.87 24.50 24.65

Cuadro C.2: (Tabla 4.9) Perplejidad del conjunto de test para diferentes tallas delconjunto de entrenamiento. La columna Ts indica la partición utilizada para el test.La columna Tr indica las particiones utilizadas para el entrenamiento. Las tallas decada partición pueden consultarse en la Tabla 4.5.

Ts Tr VS k = 7

P5 P1 29.58 25.78P1 P2 27.47 24.37

P1 P2 P3 26.47 25.44P1 P2 P3 P4 26.38 26.08

P3 P1 28.07 24.80P1 P2 27.17 24.23

P1 P2 P4 26.76 24.25P1 P2 P4 P5 26.72 24.50

P1 P2 25.42 22.64P2 P3 25.14 23.76

P2 P3 P4 25.30 23.70P2 P3 P4 P5 25.25 24.65

En la Sección 4.5 se estudiaron dos algoritmos de estimación, basados en los al-goritmo IO y VS, que hacían uso de muestras parentizadas. Estos algoritmos fueronprobados con una de las particiones de test (ver Tabla 4.10). La Tabla C.3, muestralos resultados de este experimento. Notar en este experimento el buen resultadoalcanzado por la nueva versión del algoritmo IO. Sin embargo es importante des-tacar que la aplicación de este algoritmo sólo es posible si la talla del vocabularioes reducida, como sucede en este caso. La Tabla C.4 resume los mejores resulta-dos alcanzados con los diferentes algoritmos estudiados en la tesis, exceptuando elalgoritmo IO. Puede observarse que las nuevas propuestas estudiadas mejoran losresultados obtenidos por el algoritmo VS.

131

Cuadro C.3: (Tabla 4.11) Perplejidad de Ts en el experimento 3 cuando se estimócon los algoritmos IOp y VSp.

Algoritmo IOp VSp

Perplejidad 15.12 21.30

Cuadro C.4: (Tabla 4.12) Perplejidad de Ts en el experimento 3 con diferentesalgoritmos.

Algoritmo VS kVS (k = 7) IOp VSp

Perplejidad 24.99 21.64 15.12 21.30

En la Sección 5.3 se propuso un modelo de lenguaje que combinaba un modelode n-gramas a nivel de palabras con una GIP a nivel de categorías léxicas. Estapropuesta se evaluó en el conjunto de datos del Penn Treebank. En las Figuras C.1,C.2, C.3, y C.4 puede verse la perplejidad del conjunto de test en función de γcuando se utilizó el algoritmo LRI y el algoritmo VLRI. La perplejidad con unmodelo de trigramas era 180.4. Destacar en primer lugar los buenos resultadosobtenidos por la GIP estimada con el algoritmo IOp, y en segundo lugar, el buencomportamiento del algoritmo VLRI frente al algoritmo LRI.

PSfrag replacements

Per

plej

idad

γ

LRI

VLRI

160

165

170

175

180

185

0.7 0.75 0.8 0.85 0.9 0.95 1

Figura C.1: (Figura 5.2) Perplejidad del conjunto de test en función de γ. La lineacontinua corresponde a la perplejidad con el modelo de trigramas. La GIP utilizadase estimó con el algoritmo VS.

132

PSfrag replacements

Per

plej

idad

γ

LRI

VLRI

160

165

170

175

180

185

0.7 0.75 0.8 0.85 0.9 0.95 1

Figura C.2: (Figura 5.3) Perplejidad del conjunto de test en función de γ. La lineacontinua corresponde a la perplejidad con el modelo de trigramas. La GIP utilizadase estimó con el algoritmo kVS (k = 7).

PSfrag replacements

Per

plej

idad

γ

LRI

VLRI

160

165

170

175

180

185

0.7 0.75 0.8 0.85 0.9 0.95 1

Figura C.3: (Figura 5.4) Perplejidad del conjunto de test en función de γ. La lineacontinua corresponde a la perplejidad con el modelo de trigramas. La GIP utilizadase estimó con el algoritmo VSp.

133

PSfrag replacements

Per

plej

idad

γ

LRI

VLRI

160

165

170

175

180

185

0.7 0.75 0.8 0.85 0.9 0.95 1

Figura C.4: (Figura 5.5) Perplejidad del conjunto de test en función de γ. La lineacontinua corresponde a la perplejidad con el modelo de trigramas. La GIP utilizadase estimó con el algoritmo IOp.

134

135

C.2. Resultados con la semilla 2

A continuación se presentan los experimentos comentados en la sección ante-rior, pero utilizando otra semilla para generar las probabilidades iniciales de la GIPa partir de la cual estimar un nuevo modelo.

La Tabla C.5 muestra la perplejidad obtenida sobre los diferentes conjuntos detest cuando se utilizaron diferentes valores de k. Puede observarse que el progresivoaumento de k permite obtener modelos mejor estimados. La Tabla C.6 muestracomo también el progresivo aumento de la talla del conjunto de entrenamientopermite mejorar la bondad de los modelos.

Cuadro C.5: (Tabla 4.8) Perplejidad del conjunto de test para diferentes valores dek. La columna Ts indica la partición utilizada para el test. El conjunto de entrena-miento estaba compuesto por las otras cuatro particiones que no aparecen en estacolumna. Las tallas de cada partición pueden consultarse en la Tabla 4.6.

Ts VS k = 3 k = 5 k = 7

P5 23.62 22.46 21.18 21.09P3 23.91 22.75 21.54 21.96P1 23.06 21.55 20.90 20.16

Cuadro C.6: (Tabla 4.9) Perplejidad del conjunto de test para diferentes tallas delconjunto de entrenamiento. La columna Ts indica la partición utilizada para el test.La columna Tr indica las particiones utilizadas para el entrenamiento. Las tallas decada partición pueden consultarse en la Tabla 4.5.

Ts Tr VS k = 7

P5 P1 25.08 22.67P1 P2 24.01 21.77

P1 P2 P3 23.93 21.90P1 P2 P3 P4 23.62 21.09

P3 P1 25.30 23.17P1 P2 24.18 21.89

P1 P2 P4 24.39 21.52P1 P2 P4 P5 23.91 21.96

P1 P2 23.34 20.96P2 P3 23.38 20.53

P2 P3 P4 22.97 21.23P2 P3 P4 P5 23.06 20.16

La Tabla C.7 muestra la perplejidad de una de las particiones de test cuando

136

se estimó una GIP con los algoritmo IOp y VSp. Mientras que la Tabla C.8 ilus-tra los mejores resultados alcanzados con los diferentes algoritmos de estimaciónestudiados en la tesis. Destacar los buenos resultados alcanzados por el algoritmoIOp.

Cuadro C.7: (Tabla 4.11) Perplejidad de Ts en el experimento 3 cuando se estimócon los algoritmos IOp y VSp.

Algoritmo IOp VSp

Perplejidad 13.52 21.73

Cuadro C.8: (Tabla 4.12) Perplejidad de Ts en el experimento 3 con diferentesalgoritmos.

Algoritmo VS kVS (k = 7) IOp VSp

Perplejidad 23.07 23.08 13.52 21.73

Por último, las Figuras C.5, C.6, C.7, y C.8 muestran la perplejidad obtenidapor el modelo de lenguaje que combina un modelo de trigramas con una GIP. Igualque en los experimentos con la semilla 1, destacar los buenos resultados obtenidospor la GIP estimada con la versión parentizada con el algoritmo IO, y el buencomportamiento del algoritmo VLRI frente al algoritmo LRI.

137PSfrag replacements

Per

plej

idad

γ

LRI

VLRI

160

165

170

175

180

185

0.7 0.75 0.8 0.85 0.9 0.95 1

Figura C.5: (Figura 5.2) Perplejidad del conjunto de test en función de γ. La lineacontinua corresponde a la perplejidad con el modelo de trigramas. La GIP utilizadase estimó con el algoritmo VS.PSfrag replacements

Per

plej

idad

γ

LRI

VLRI

160

165

170

175

180

185

0.7 0.75 0.8 0.85 0.9 0.95 1

Figura C.6: (Figura 5.3) Perplejidad del conjunto de test en función de γ. La lineacontinua corresponde a la perplejidad con el modelo de trigramas. La GIP utilizadase estimó con el algoritmo kVS (k = 7).

138PSfrag replacements

Per

plej

idad

γ

LRI

VLRI

160

165

170

175

180

185

0.7 0.75 0.8 0.85 0.9 0.95 1

Figura C.7: (Figura 5.4) Perplejidad del conjunto de test en función de γ. La lineacontinua corresponde a la perplejidad con el modelo de trigramas. La GIP utilizadase estimó con el algoritmo VSp.PSfrag replacements

Per

plej

idad

γ

LRI

VLRI

160

165

170

175

180

185

0.7 0.75 0.8 0.85 0.9 0.95 1

Figura C.8: (Figura 5.5) Perplejidad del conjunto de test en función de γ. La lineacontinua corresponde a la perplejidad con el modelo de trigramas. La GIP utilizadase estimó con el algoritmo IOp.

139

140