Adaptación del Método de Etiquetado No Supervisado TBL

Adaptaci´on del M´etodo de Etiquetado No Supervisado TBL Jes´us Gonz´alez Mart´ı Intelligent Dialogue Systems Sevilla [email protected] David Gonz´alez Maline G. Investigaci´on Julietta Universidad de Sevilla [email protected] Jos´eAntonioTroyano Departamento LSI Universidad de Sevilla troy[email protected] Resumen: Se presenta una mejora al m´etodo de etiquetado de Brill basado en reglas y transformaciones. Se disminuye considerablemente los tiempos de entrenamiento sin sacrificar de ninguna manera la eficicacia del m´etodo. Palabras clave: Brill, TBL, regla, transformaci´on, etiquetado morfosint´actico, categoria Abstract: This paper proposes an improvement of the Brill’s “Transformation- Rule Based” POS-Tagger Algorithm. Our improvement decreases training times considerably without affecting the accuracy of the algorithm. Keywords: Brill, TBL, rule, transformation, Part-of-OS tagging, category 1. Introducci´on Desobraesconocidalanecesidadde realizar el etiquetado morfosint´actico dentro de los procesos de tratamiento del lenguaje natural. Para llevar a cabo esta tarea se pueden utilizar diversos tipos de algoritmos, entre los cuales podemos encontrar el propuesto por Brill(Brill, 1992)(Brill, 1994) y en concreto la versi´on no supervisada de su etiquetador basado en transformaciones(Brill, 1995). La gran ventaja de este m´etodo es que permite una mayor implicaci´on por parte de los ling¨uistas a la hora de mejorarlo y adaptarlo a los diferentes ´ambitos de aplicaci´on del mismo. Sin embargo, y a pesar de la efectividad del m´etodo, los tiempos de entrenamiento que requiere un algoritmo de este tipo son considerablemente superiores a los tiempos que emplean los etiquetadores basados en los modelos de Markov. Existengrancantidaddetrabajosque intentan mejorar de alguna forma este problema: (Roche y Schabes, 1995), (Ramshaw y Marcus, 1996), (Aone y Hausman, 1996), (Ngai y Florian, 2001), etc... Pero la mayor´ıa de los mismos sacrifican la eficacia del etiquetado por velocidad de ejecuci´on; por consiguiente el m´etodo cae en desventaja con respecto a otros que proporcionan un mejor resultado en tiempos semejantes. Todos los trabajos mencionados se centran en estudiar las probabilidades de las reglas para evitar generar aquellas que a posteriori sean innecesarias. Sin embargo, esto no se cumple siempre y a veces se pierden reglas que podr´ıan ser muy provechosas para aumentar el n´umero de palabras correctamente etiquetadas. En este art´ıculo se presenta una adaptaci´on del m´etododeBrillquenodesecha ninguna regla, pero que realiza una mejora temporal muy interesante ya que permite competir con los ya mencionados algoritmos basados en modelos de Markov. En definitiva, aumenta en proporci´on la calidad de los resultados respecto a los tiempos de entrenamiento, sin sacrificar el grado de precisi´on y cobertura de las raglas obtenidas. 2. Algoritmo de Brill No Supervisado El algoritmo de Brill parte de un texto sin etiquetar y de un diccionario que contiene las diferentes categor´ıas gramaticales a las que puede optar una palabra. A continuaci´on realiza los siguientes pasos: 1. En primer lugar, etiqueta cada palabra consuconjuntodeetiquetascorrespon- diente. 2. Genera todas las reglas posibles bas´andose en un conjunto determinado de plantillas (PREVWORD, NEXTWORD, PREVTAG, NEXTTAG, ...).1 3. Punt´ua cada regla en funci´on de una serie de par´ametros, como por ejemplo la frecuencia de aparici´on de las mismas. 4. Si no existe ninguna regla que haya sido puntuada por encima de un cierto umbral termina el entrenamiento del etiquetador. Si existe, la aplica a todas las palabras del texto que concuerden con el contexto de la regla y la a˜nade al conjunto de reglas aprendidas por el etiquetador. 5. Volver al paso 2. Veamos un breve ejemplo. Supongamos el siguiente estado en el proceso de entrenamiento del etiquetador: ... elevaba(VERB) a(PREP-NOMB) la(DETNOMB) orilla(NOMB-VERB) misma(ADJ) del(DET) r´ıo(NOMB-VERB) y(CONJ) ... ... ... habitaba(VERB) un(DET) pueblo(NOMB) de(PREP) hombres(NOMB) vigorosos(ADJ) ... Para la palabra ambigua “orilla” de la primera frase y tomando como referencia la palabra no ambigua “pueblo” de la seguda frase, tenemos la siguiente coincidencia de contex- to: PREVTAG(DET): NOMB-VERB →NOMB Como se ve, para las dos palabras “orilla” y “pueblo”, existe una posible etiqueta com´un que les precede: “DET”. Dado que tenemos un caso no ambiguo (“pueblo”) en el cual una palabra posee la categor´ıa gramatical de “NOMB”, en el caso de “orilla”, generamos la regla anteriormente citada. Si esta regla obtiene la mayor puntuaci´on se aplicar´a y en el siguiente paso del algoritmo el texto se habr´a transformado en: ... elevaba(VERB) a(PREP-NOMB) la(DETNOMB) orilla(NOMB) misma(ADJ) del(DET) r´ıo(NOMB-VERB) y(CONJ) ... 1La versi´on implementada por los autores s´olo contempla los citados tipos de plantillas. 3. Variaci´on de Estados La mejora del algoritmo se basa en un estudio de los estados por los que pasa el proceso de entrenamiento. En cada iteraci´on, se genera un conjunto de reglas posibles entre las que elegir aquella que obtenga la mayor puntuaci´on, que normalmente coincide con aquella que m´as palabras desambigua. Podemos definir un estado del algoritmo mediante los siguientes elementos: el texto de entrada, el conjunto de reglas candidatas, la regla de mayor puntuaci´on y el conjunto de reglas aprendido durante los anteriores estados del algoritmo. Para conseguir una mejoraquenocomprometalaeficacia debemos conseguir un algoritmo diferente, m´as eficiente pero que mantenga el mismo n´umero de estados as´ı como la secuencia de los mismos. Por tanto, la idea clave de esta propuesta consiste en encontrar cu´ales son los factores que implican un cambio de un estado a otro, trabajar con dichos elementos y generar un nuevo algoritmo que no necesite el esfuerzo computacional del original. Para proponer una nueva soluci´on se estudi´o previamente el algoritmo original para encontrar su parte cr´ıtica, esto es, la que mayor carga computacional soporta. ´ Esta recae sobre la tarea de generar el conjunto de reglas candidatas y puede llegar a consumir el 85 % del tiempo del algoritmo. Esto es debido a que el algoritmo original no tiene m´as remedio que volver a generarlas a cada paso o estado. La puntuaci´on de reglas tambi´en consumeunaparteimportantedeltiempo pero no es significativa en comparaci´on al tiempo necesario para generar las miles (o incluso millones) de reglas que pueden llegar a generarse. El problema de la generaci´on de dichas reglas consume mucho tiempo porque requiere recorrer el texto de entrada un n´umero muy elevado de veces en cada iteraci´on: node recorridos noiteraciones =(palabras ambiguas)2 4. Generaci´on R´apida de Reglas Una vez se estudian los diferentes estados por los que pasa el algoritmo durante sus ejecuciones, se puede observar que el estado de reglas candidatas var´ıa en funci´on de una serie de patrones que presentamos a Jesús González Martí, David González Maline y José Antonio Troyano continuaci´on: Aparici´on en nuevos contextos La aparici´on de nuevas reglas en el conjunto de reglas candidatas cuando se cambia de un estado a otro en una iteraci´on,sedebeexlusivamenteala aparici´on de nuevos contextos que cuadren con las palabras que a´un siguen siendo ambiguas en el texto. Esto quiere decir que, cuando desambiguamos una palabra en una iteraci´on, en la siguiente pueden aparecer nuevas reglas originadas por las palabras ambiguas que ahora tienen en com´un su contexto con el contexto no ambiguo. Por ejemplo, dado el siguiente fragmento de un texto sobre el que est´a trabajando el sistema de entrenamiento: ... elevaba(VERB) a(PREP-NOMB) la(DET-NOMB) orilla(NOMB-VERB) misma(ADJ) del(DET) r´ıo(NOMB-VERB) y(CONJ) ... ... la(NOMB)2mayor(NOMB-ADJ) parte(NOMB-VERB) de(PREP) la(DETNOMB) gente(NOMB) ... ... habitaba(VERB) un(DET) pueblo(NOMB) de(PREP) hombres(NOMB) vigorosos(ADJ) ... Si tenemos en cuenta el reducido conjunto de reglas que se generar´ıan a partir de la palabra ambigua “orilla” de la primera frase, vemos que s´olo existe una palabra no ambigua que concuerda con su contexto para la plantilla PREVTAG: “pueblo”, pues tantolapalabraquelaprecede,comola que precede a “orilla” pertenecen a la categor´ıa gramatical de determinante. Por lo tanto la ´unica regla que se genera ser´ıa: •PREVTAG(DET): NOMB-VERB →NOMB Esta regla significa que si estamos ante una palabra que puede ser o bien un 2La categor´ıa NOMB viene del nombre de la nota musical “LA”. Considerese el ejemplo como un caso en el que se ha desambiguado incorrectamente. nombreobienunverboylapalabra que le precede contiene en sus posibles etiquetas DET, entonces debemos elegir para ella la categor´ıa de NOMB. En este mismo estado, la regla que obtiene mayor puntuaci´on sirve para desambiguar la palabra “mayor” a NOMB. Si ahora tuvieramos que volver a generar todas las reglas del conjunto para la palabra “orilla”, ya no es “pueblo” quien concuerda en contexto, sino tambi´en la palabra “mayor” generando estas dos nuevas reglas en el conjunto de reglas posibles: •PREVTAG(NOMB): NOMB-VERB → NOMB •PREVWORD(“la”): NOMB-VERB → NOMB Desaparici´on por la palabra desambiguada En cuanto a la desaparici´on de reglas, se pueden dar dos casos. El m´as evidente es el caso en el que una palabra ambigua que generaba reglas, pasa a ser no ambigua. En este caso, desaparecen todas las reglas que se generaban utiliz´andose dicha palabra como referencia. En el ejemplo anterior, ten´ıamos un total de tres reglas generadas a partir de la palabra “orilla” como palabra ambigua de referencia. Si en una de las iteraciones se eligiera una regla que la desambiguase, las tres reglas que se generaron en el caso anterior desaparecer´ıan. Desaparici´on por contextos propios y ajenos Existe un segundo caso de desaparici´on de reglas que se produce al desambiguar palabras que cuadran con los contextos de alguna palabra potencialmente utilizable para la generaci´on. Por ejemplo, presentando el siguiente estado an´alogo al anterior pero con la palabra “mayor” desambiguada: ... elevaba(VERB) a(PREP-NOMB) la(DET-NOMB) orilla(NOMB-VERB) misma(ADJ) del(DET) r´ıo(NOMB-VERB) y(CONJ) ... A daptación del Método de Etiquetado No Supervisado TBL ... la(NOMB) mayor(NOMB) parte(NOMBVERB) de(PREP) la(DET-NOMB) gente(NOMB) ... ... habitaba(VERB) un(DET) pueblo(NOMB) de(PREP) hombres(NOMB) vigorosos(ADJ) ... Las reglas que se generan son las siguientes: •PREVTAG(DET): NOMB-VERB →NOMB •PREVTAG(NOMB): NOMB-VERB → NOMB •PREVWORD(“la”): NOMB-VERB → NOMB Sin embargo, se puede observar que el “la” que precede a la palabra “orilla” es tambi´en una palabra ambigua, lo cual da lugar a dos contextos diferentes a tener en cuenta a la hora de generar reglas. Si dicha palabra fuera desambiguada en una de las iteraciones del algoritmo, tendr´ıamos que tener en cuenta cu´ales son las reglas que desaparecen por esta causa. En este caso concreto, si desambiguamos “la” a determinante,laregla que desaparecer´ıa ser´ıa: •PREVTAG(NOMB): NOMB-VERB → NOMB 5. Resultados Para la realizaci´on de las pruebas de medici´on de tiempos y comparaci´on entre algoritmos, se utiliz´o una m´aquina con procesador Intel Pentium III a 800 Mhz, 256 MBytes de memoria RAM y ejecutando un sistema operativo Windows 2000. La implementaci´on del algoritmo original utilizada fue creada a partir del art´ıculo publicado por Brill sobre el entrenamiento no supervisado. Primero se realiz´ouna implementaci´on “al pie de la letra” y a continuaci´on se implement´ounaversi´on queusabaestructurasdedatosindexadas. Finalmente se realiz´ounaterceraimplementaci´on que sacaba provecho de los principios mencionados en la secci´on anterior. Cada versi´on se fue construyendo en base a la anterior por lo que todo el c´odigo com´un es compartido haciendo de este modo m´as fiable los resultados y comparativas. El siguiente cuadro muestra los diferentes tiempos de ejecuci´on (en segundos) del algoritmo en sus tres variantes utilizadas en las pruebas: Tam a ˜no del Texto 1Kb 5Kb 10 Kb 20 Kb Original 1.14 160.97 640.87 5329.37 Indexada 0.53 103.95 408.24 2834.84 R´apida 0.34 48.31 138.13 807.09 Cuadro 1: Tiempos de ejecuci´on El mismo resultado puede apreciarse gr´aficamente en la figura 1. Se observa el crecimiento exponencial del tiempo de ejecuci´on en las tres versiones. El n´umero de reglas que se puede llegar a generar en un texto depende exponencialmente del tama˜no del mismo. Se observa que la diferencia de tiemposamedidaqueeltama˜no crece es muy considerable. Figura 1: Tiempos de ejecuci´on Como se cit´o anteriormente, la mejora se ha realizado ´unicamente en la generaci´on de reglas y no en otra parte del algoritmo. Esta caracter´ıstica puede apreciarse mejor si medimos la diferencia de tiempos que existe entre cada iteraci´on. Ya que lastresimplementacionessecomportan exactamente de la misma forma, incluso a la hora de conservar el estado entre las iteraciones, realizamos la medici´on entre la versi´on indexada y la versi´on mejorada, obteniendo una gr´afica como la de la figura 2. Jesús González Martí, David González Maline y José Antonio Troyano Figura 2: Tiempos de iteraci´on Se observa que la ejecuci´on del algoritmo mejorado parece mucho m´as constante en su tiempo de iteraci´on que el algoritmo original. Esto se debe a que el algoritmo original genera la totalidad del conjunto de reglas posibles en cada iteraci´on, mientras que el algoritmo propuesto tan s´olo realiza dicha operaci´on al comienzo de la ejecuci´on misma. De este modo, realiza en cada iteraci´on ´unicamente los c´alculos necesarios para averiguar las modificaciones delconjuntodereglasdelaiteraci´on anterior. La figura 3 muestra la diferencia de tiempos en cada iteraci´on de los dos algoritmos comparados. Ya que el tiempo de puntuaci´on delasreglasesid´enticamente igual en ambos algoritmos, se observa que la disminuci´on en la diferencia se debe a c´omo progresivamente decrece el n´umero de reglas candidatas que se pueden calcular, consecuencia l´ogica de c´omo se van desambiguando las palabras en el texto. Figura 3: Diferencia de Tiempos 6. Conclusi´on En este art´ıculo se ha buscado una soluci´on a la lentitud de ejecuci´on del algoritmo de entrenamiento para el etiquetado no supervisado propuesto por Brill. Para ello se han estudiado los diferentes estados por los que pasa el algoritmo, as´ı como los factores que hacen variar de un estado a otro, de una iteraci´onalasiguiente.Apartir de esa informaci´on, se dise˜na un nuevo algoritmo capaz de evitar tener que regenerar la informaci´on obtenida del texto sino quesegenerabas´andose en el estado anterior. Es importante hacer hincapi´eenelhecho de que los conjuntos de reglas soluci´on de la versi´on de Brill y la nueva versi´on propuesta son exactamente id´enticos. Esta soluci´on por tanto puede definirse como una adaptaci´on que mejora la eficiencia temporal del algoritmo original. El resultado es un nuevo etiquetador no supervisado que se ejecuta en unos m´argenes de tiempo considerablemente inferiores a losdelaversi´on original de Brill, con la ventaja a˜nadida de que el comportamiento y los resultados del algoritmo con respecto al original se mantienen intactos. 7. Trabajo Futuro Al igual que se ha conseguido reducir el tiempo de generaci´on de las reglas candidatas en cada iteraci´on del algoritmo, de un modo semejantesepodr´ıa mejorar la eficiencia en el tiempo necesario para la puntuaci´on de las mismas. Este enfoque saca partido de que la variaci´on en las puntuaciones de las reglas siguen tambi´en ciertos patrones de modificaci´on semejantes a los del conjunto de reglas candidatas. Dado que en la versi´on mejorada aqu´ı propuesta la generaci´on de reglas ha sido reducida a un segundo plano en cuanto a consumo de recursos, el nuevo cuello debotellaeslapuntuaci´on. La posible reducci´on del tiempo de puntuaci´on dar´ıa lugar a un algoritmo mucho m´as r´apido que el actual, aunque en proporci´on, no se conseguir´a una mejora comparable a la descrita en el presente trabajo. A daptación del Método de Etiquetado No Supervisado TBL Puesto que las mejoras presentadas se han realizado sobre el etiquetador original de Brill, ser´ıa interesante relizar comparativas con otros etiquetadores (por ejemplo: fnTBL), incluso etiquetadores basados en modelosdeMarkov(comoTNT). Por otro lado, ser´ıa muy interesante comparar el grado de eficacia del algoritmo cuando se aumenta el n´umero de plantillas posibles. En nuestro estudio s´olo se han implementado PREVWORD, NEXTWORD, NEXTTAG, y PREVTAG. Algunas plantillas posibles ser´ıan: PREVPREVWORD (palabra anterior a la anterior), PREVPREVTAG (etiqueta de la palabra anterior a la anterior), ..., 2-PREVWORD (las dos palabras anteriores), 2-NEXTTAG (las etiquetas de las dos palabras posteriores), etc... Bibliograf´ıa Aone, Chinatsu y Kevin Hausman, 1996. Unsupervised learning of a rule-based Spanish Part of Speech tagger. Brill, Eric. 1992. A simple rule-based part os speech tagger. En 3rd Conference on Applied Natural Language Processing. Tren- to, Italia. Brill, Eric. 1994. Some advances in rule-based part of speech tagging. En 12th Conference on Artificial Intelligence (AAAI-94). Seattle, Wa. Brill, Eric. 1995. Unsupervised learning of disambiguation rules for part of speech tagging. En 3rd Workshop on Very Large Corpora. Ngai, Grace y Radu Florian, 2001. Transformation-based learning in the fast lane. Ramshaw,LanceA.yMitchellP.Marcus, 1996. Exploring the statistical derivation of transformation rule sequences for part- of-speech tagging. Roche, Emmanuel y Yves Schabes, 1995. Deterministic Part-of-Speech tagging with finite state transducers. Jesús González Martí, David González Maline y José Antonio Troyano