TextRank como motor de aprendizaje en tareas de etiquetado

TextRank como motor de aprendizaje en tareas de etiquetado ∗ Ferm´ın Cruz, Jos´e A. Troyano, Fernando Enr´ıquez yF. Javier Ortega Dep. de Lenguajes y Sistemas Inform´aticos Universidad de Sevilla Avda. Reina Mercedes s/n 41012 Sevilla [email protected] Resumen: Este trabajo trata de c´omo adaptar el m´etodo TextRank para que funcione de manera supervisada. TextRank es un m´etodo basado en grafos que aplica las ideas de PageRang al PLN. Nuestra principal aportaci´on es la definici´on de un m´etodo que permite crear un grafo que incluye informaci´on extra´ıda de un corpus de entrenamiento. Hemos comparado los resultados de nuestro m´etodo en distintas tareas PLN con los obtenidos por herramientas especializadas en el etiquetado. El rendimiento de nuestro sistema se acerca bastante al de estas herramientas llegando incluso a superar a algunas de ellas en varias tareas. Palabras clave: Ordenaci´on de Grafos, Corpus anotado, Aprendizaje Supervisado Abstract: In this paper we investigate how to adapt the TextRank method to make it work in a supervised way. TextRank is a graph based method that applies the ideas of PageRank to NLP tasks. Our main contribution is the definition of a method that allows to apply TextRank to a graph that includes information generated from a training tagged corpus. We have compared the results that our method achieves in several NLP tasks with those obtained with specialized tagging tools. The performance of our system is quite near to these tools, improving the results of some of them in several tasks. Keywords: Graph Ranking, Tagged corpus, Supervised Learning 1. Introducci´on En muchas aplicaciones relacionadas con el Procesamiento del Lenguaje Natural los grafos se revelan como la representaci´on m´as adecuada. De hecho, desde el momento en el que un texto es fragmentado en palabras y se establece alg´un tipo de relaci´on entre dichas palabras, disponemos de una representaci´on en forma de grafo. Sin embargo, esta conexi´on entre PLN y grafos no siempre est´a presente en los modelos que se utilizan para resolver muchos de los problemas relacionados con el tratamiento de textos. As´ı, en las visiones generativas (basadas en gram´aticas) del PLN el modelo de representaci´on dominante suele ser el ´arbol, como consecuencia directa del concepto de ´arbol de derivaci´on. En las propuestas estad´ısticas (basadas en corpus) hay m´as variedad de modelos, pero no son muchos los que explotan la conexi´on entre grafo y lenguaje. En este sentido, t´ecni- ∗Parcialmente financiado por el Ministerio de Ciencia y Tecnolog´ıa (TIN2004-07246-C03-03). cas como los ´arboles de decisi´on, el modelado de m´axima entrop´ıa, el aprendizaje basado en ejemplos o el aprendizaje basado en transformaciones descansan sobre representaciones bastante alejadas de los grafos. Por otro lado, t´ecnicas como los modelos de Markov y las redes neuronales s´ı se basan en representaciones en forma de grafo, aunque en estos modelos no se utilizan directamente algoritmos relacionados con la teor´ıa de grafos. Recientemente est´an apareciendo propuestas que dan m´as protagonismo a los grafos en el proceso de entrenamiento, e incluso empiezan a surgir workshops (como (Radev, 2006)) que incluyen como tema principal la aplicaci´on de algoritmos basados en grafos al PLN. Una propuesta interesante es la de TextRank (Mihalcea, 2004), un algoritmo basado en la misma idea que originalmente us´o Google para establecer un ranking de p´aginas (Brin, 1998). El algoritmo TextRank ha sido aplicado con bastante ´exito a diver33 sas tareas del PLN como son la extracci´on de res´umenes, la extracci´on de palabras clave o la desambiguaci´on de significados. A pesar de ser un algoritmo no supervisado alcanza en dichas tareas resultados similares a los obtenidos en la literatura por sistemas supervisados. El objetivo principal de este trabajo es investigar c´omo se puede utilizar el algoritmo TextRank de una manera supervisada. Para ello hay que introducir informaci´on recopilada desde un corpus de entrenamiento (que al ser el aprendizaje supervisado estar´ıa etiquetado) en el grafo que represente un determinado problema que posteriormente ser´ıa procesado por el algoritmo TextRank. La intuici´on nos dice que dada la flexibilidad que ha mostrado dicho algoritmo en su versi´on no supervisada, el hecho de introducir la informaci´on proveniente del corpus anotado no tendr´ıa que estropear la bondad del algoritmo. La clave est´a en encontrar una representaci´on para cada problema que saque el m´aximo rendimiento a la potencia del algoritmo TextRank. La organizaci´on del resto del art´ıculo es como sigue, en la siguiente secci´on se explicar´a el algoritmo TextRank, en la secci´on tercera mostraremos c´omo hemos construido el grafo a partir de un corpus etiquetado, la secci´on cuarta incluir´a el dise˜no experimental, la quinta los resultados, y por ´ultimo la secci´on sexta estar´a dedicada a las conclusiones y l´ıneas de trabajo futuro. 2. El algoritmo TextRank La idea principal de TextRank es aplicar un algoritmo de ordenaci´on basado en grafos a problemas relacionados con el PLN. En concreto, hace uso del famoso algoritmo PageRank (Brin, 1998), una de las claves que llevaron a Google a la posici´on de privilegio de la que actualmente disfruta en Internet. PageRank es utilizado para medir la importancia de cualquier p´agina web en Internet en funci´on de los enlaces que dicha p´agina recibe, aunque tambi´en se han utilizado ideas similares en otros contextos como el an´alisis de redes sociales o de redes de referencias bibliogr´aficas. La formalizaci´on del algoritmo PageRank es bastante simple, dado un grafo G=(V,E) donde Ves un conjunto de v´ertices y Eun conjunto de arcos dirigidos entre dos v´ertices, se definen en primer lugar dos operaciones E(Vi)yS(Vi) que calculan, respectivamente, el n´umero de arcos que entran o salen del v´ertice Vi. A partir de estas dos operaciones b´asicas, se define la puntuaci´on (o PageRank) de un determinado v´ertice con la siguiente f´ormula: P(Vi)=(1−d)+ d j∈E(Vi) 1 |S(Vj)|P(Vj) donde des un factor de amortiguaci´on que tiene como objetivo incluir en el modelo la probabilidad de que haya un salto aleatorio de un v´ertice del grafo a cualquier otro. En el contexto de la navegaci´on en Internet, dicho factor representa la probabilidad de que un usuario acceda a una p´agina a trav´es de un enlace situado en la p´agina actual, siendo por tanto (1 −d) la probabilidad de que dicho usuario salte a una p´agina aleatoria no enlazada con la p´agina actual. En la definici´on original de PageRank se recomienda un valor de 0.85 para el factor d. Partiendo de valores arbitrarios para las puntuaciones de los nodos de un grafo, se alcanza un punto de convergencia aplicando iterativamente la f´ormula hasta que la mayor diferencia de las puntuaciones obtenidas para cada nodo, entre dos iteraciones, es menor que un determinado umbral. Una vez finalizado el algoritmo, la puntuaci´on alcanzada por cada nodo representa la importancia del mismo, y puede ser utilizada como criterio para la toma de decisiones. Esta f´ormula se puede generalizar con facilidad para ser aplicada a grafos cuyos arcos tengan pesos. En este caso la puntuaci´on de cada nodo se calcular´ıa de la siguiente forma, donde pji es el peso del arco que va del v´ertice Vjal Vi: P(Vi)=(1−d)+ d : j∈E(Vi) pji 2 k∈S(Vj)pjk P(Vj) Para poder aplicar TextRank s´olo es necesario obtener un grafo a partir de un texto, calcular a partir del grafo la puntuaci´on de PageRank y utilizar dicha puntuaci´on de los nodos para resolver cuestiones sobre las unidades textuales a las que se refieren dichos nodos. Este algoritmo se ha aplicado a tareas como la extracci´on de palabras clave y la generaci´on de res´umenes (Mihalcea, 2004) o desambiguaci´on de significados (Mihalcea, 34 Fermín Cruz, José Antonio Troyano, Fernando Enríquez y F. Javier Ortega 2004b) con muy buenos resultados. En cada caso la forma de construcci´on del grafo es distinta. Por ejemplo, en la extracci´on de palabras clave los v´ertices son palabras y se establecen arcos entre v´ertices si hay coocurrencia entre las palabras que representan. Se entiende que hay coocurrencia si est´an juntas o a una distancia menor que un l´ımite Nestablecido. 3. Obtenci´on del grafo a partir de un corpus anotado Las aplicaciones desarrolladas alrededor de TextRank han sido siempre no supervisadas. Es decir, construyen el grafo directamente a partir del texto de evaluaci´on sin hacer uso de ning´un corpus de entrenamiento anotado. A pesar de esto, TextRank consigue en las tres tareas antes mencionadas resultados similares a los obtenidos por sistemas que s´ı usan corpus anotados, y que por tanto realizan un aprendizaje supervisado. Quiz´ala raz´on de tan sorprendente hecho (se alcanzan los mismos resultados con menos informaci´on) haya que buscarla en la naturaleza de los tres problemas a los que se ha aplicado, que se ajustan muy bien al modelo de grafo. Parece por tanto que la cercan´ıa de la tarea al modelo de grafo es una condici´on indispensable para que TextRank se pueda utilizar como motor de aprendizaje. En este punto la pregunta es, ¿ser´a posible aplicar este algoritmo a otras tareas? Nosotros no hemos encontrado aproximaciones a otras tareas cl´asicas en el PLN como el etiquetado POS, el an´alisis sint´actico o la extracci´on de informaci´on. Precisamente el objetivo inicial de este trabajo era explorar otras v´ıas de aplicaci´on de este algoritmo al mismo tiempo que intentar encajar su utilizaci´on en un marco supervisado que aproveche la informaci´on disponible en un corpus de entrenamiento anotado. No tiene porqu´e haber una ´unica manera de representar una tarea PLN en forma de grafo para poder aplicar un algoritmo de ranking como TextRank. Nosotros hemos elegido una lo suficientemente general como para que pueda ser utilizada en cualquier tarea en la que se asocien etiquetas a palabras. Los v´ertices de nuestros grafos estar´an compuestos por dos informaciones V=(w, t), wes una palabra y tuna etiqueta. Si una palabra es ambigua (puede tener varias etiquetas) se crear´an tantos v´ertices como posibles etiquetas pueda tener. La idea principal de nuestra aproximaci´on es construir un grafo con este tipo de v´ertices para cada frase, aplicar TextRank a dicho grafo y asociar a cada palabra de la frase la etiqueta correspondiente a su v´ertice mejor puntuado. Si una palabra aparece m´as de una vez en una frase, se crean v´ertices diferenciados para que estas m´ultiples instancias no interfieran entre s´ı. Para los arcos del grafo hemos optado por la coocurrencia, de manera que habr´a un arco desde un v´ertice Vi=(wi,t i) a otro v´ertice Vj=(wj,t j) si la palabra wjaparece en la frase despu´es de la palabra wi. El grafo ser´a por tanto dirigido. Por ´ultimo, la informaci´on del corpus de entrenamiento aparecer´a en el grafo mediante pesos en los arcos. Hemos experimentado con distintas medidas y la que mejor resultado nos ha dado ha sido una combinaci´on de las probabilidades de emisi´on P(w|t) y transici´on P(t|t) utilizadas en los modelos ocultos de Markov basados en bigramas. Dichas probabilidades son estimadas a partir de la frecuencia de aparici´on de etiquetas y palabras en el corpus de entrenamiento: P(w|t)=C(w, t) C(t)P(t|t)=C(t,t) C(t) donde C(t)eseln´umero de veces que aparece la etiqueta ten el corpus de entrenamiento, C(w, t)eln´umero de veces que la palabra waparece etiquetada con tyC(t,t) el n´umero de ocasiones en las que la etiqueta taparece antes de la etiqueta t. En el modelo de Markov estas probabilidades se utilizan para calcular el mejor etiquetado para una frase maximizando la siguiente probabilidad: P(t1,n|w1,n)= n  i=1 P(wi|ti)P(ti|ti−1) Nosotros utilizaremos la probabilidad P(wi|ti)P(ti|ti−1) como peso del arco que va del v´ertice Vi−1=(wi−1,t i−1)alv´ertice Vi=(wi,t i) del grafo, y dejaremos a TextRank que calcule la importancia de cada v´ertice. A diferencia del modelo de Markov en el que se consideran los distintos caminos como competidores y se busca el que maximice la anterior expresi´on, la aproximaci´on 35 TextRank como motor de aprendizaje en tareas de etiquetado de TextRank es m´as colaborativa ya que se combinan las probabilidades desde distintos arcos para determinar el ranking de un determinado v´ertice. 3.1. Extensiones al modelo inicial Muchas de las extensiones cl´asicas de los modelos de Markov pueden ser incluidas en nuestro grafo de una u otra forma. Por ejemplo, podemos redefinir la expresi´on con la que se calcula el peso de un arco para que incluya en la medida la probabilidad de trigramas y unigramas, adem´as de bigramas, o podemos generar nuevos arcos adicionales a los explicados en nuestro dise˜no base. A partir del modelo b´asico anteriormente expuesto, hemos realizado una serie de pruebas para encontrar variantes con mejor comportamiento. El camino que ha seguido nuestra investigaci´on en este sentido ha sido el siguiente: En los primeros experimentos, us´abamos la probabilidad de bigramas y de emisi´on de palabras para ponderar los arcos. Posteriormente, a˜nadimos aristas que un´ıan los nodos representantes de una palabra con los nodos de las palabras dos posiciones a la izquierda y derecha. De esta forma, trat´abamos de a˜nadir un conocimiento menos local a la red. Con este esquema conseguimos peores resultados que con el anterior. La tercera evoluci´on supuso el uso de trigramas en lugar de bigramas. Para ello fue necesario cambiar la construcci´on del grafo, de forma que para cada palabra se crease un nodo por cada posible etiqueta de la palabra anterior y cada posible etiqueta de la palabra en cuesti´on. El problema de usar s´olo la probabilidad de trigramas es que la frecuencia de aparici´on de los trigramas en un corpus es mucho menor, encontr´andonos con muchas combinaciones de etiquetas no observadas en el corpus. Se necesita por tanto suavizar estos resultados mediante la inclusi´on de las probabilidades de bigramas y unigramas. Investigamos si el proceso de combinaci´on de bigramas y trigramas se podr´ıa llevar a cabo simplemente mediante la inclusi´on de aristas distintas para cada probabilidad, y dejando que el algoritmo de TextRank calculara una puntuaci´on para cada nodo en funci´on de dichas probabilidades. Pero tras distintos experimentos, llegamos a la conclusi´on de que la mejor soluci´on era usar una sola arista ponderada con una interpolaci´on lineal de los tres tipos de probabilidad. Para el c´alculo de los coeficientes de correlaci´on de las probabilidades hemos usado el mismo algoritmo que TnT. El modelo que mejor se ha comportado y que hemos utilizado por tanto en nuestros experimentos ha sido este ´ultimo. Para el tratamiento de las palabras desconocidas hemos optado por una estrategia muy simple: las etiquetas m´as usuales en el corpus son asignadas como candidatas a las palabras desconocidas, y la probabilidad de emisi´on es calculada en base a la terminaci´on de dichas palabras. En el proceso de extracci´on de estad´ısticas del corpus de entrenamiento, se calculan las probabilidades de emisi´on de las palabras con terminaciones m´as comunes, y dichas probabilidades son usadas para el c´alculo de las probabilidades de emisi´on de palabras desconocidas en el proceso de etiquetado. Este tratamiento puede ser todav´ıa muy refinado para llegar al nivel de herramientas como TnT, y es de esperar que la inclusi´on de dichas t´ecnicas mejore sensiblemente los resultados obtenidos en nuestro trabajo, sobre todo ante corpus de entrenamiento peque˜nos. 4. Dise˜no experimental En esta secci´on presentaremos el dise˜no experimental que hemos seguido para aplicar nuestras ideas a dos corpus anotados con etiquetas POS (Part Of Speech). Para esta tarea se pueden encontrar recursos suficientes y numerosas aproximaciones con las que comparar los resultados. El conjunto de etiquetas suele ser mediano (entre 50 y 100), hay palabras que s´olo pueden ser etiquetadas con una etiqueta y otras para las que hay varias posibilidades. Los dos corpus utilizados est´an escritos en ingl´es, uno es el corpus Susanne y otro un extracto del corpus Penn compuesto por sus cuatro primeras secciones, en la tabla 1 se pueden ver los tama˜nos de las respectivas particiones de entrenamiento y test para ambos corpus. La diferencia m´as significativa entre los 36 Fermín Cruz, José Antonio Troyano, Fernando Enríquez y F. Javier Ortega Entren. Test Etiquetas Susanne 141140 15482 131 Penn 198550 46461 37 Tabla 1: Tama˜nos de los corpus. dos corpus utilizados es el n´umero de etiquetas. El corpus Penn tiene un conjunto de etiquetas bastante peque˜no de s´olo 37 etiquetas, mientras que el corpus Susanne casi triplica esa cifra con 131. En la pr´actica esto se traduce en que la tarea de etiquetar a partir del corpus Susanne es mucho m´as dif´ıcil que con el Penn, tal y como se podr´a comprobar en los resultados. 4.1. Otros sistemas Para comparar los resultados obtenidos con nuestra versi´on supervisada de TextRank hemos entrenado los dos corpus con herramientas especializadas en tarea del etiquetado POS. En concreto hemos utilizado los siguientes sistemas: TnT (Brants, 2000), es uno de los m´as utilizados, est´a basado en modelos de Markov, es muy r´apido y suele obtener muy buenos resultados. TreeTagger (Schmid, 1994), est´a basado en ´arboles de decisi´on, para cada palabra genera un registro de una base de datos que es posteriormente utilizada para la obtenci´on del ´arbol de decisi´on. MBT (Daelemans, 2004), realiza el entrenamiento mediante aprendizaje basado en ejemplos, una implementaci´on eficiente de la t´ecnica de los vecinos m´as cercanos. fnTBL (Ngai, 2001), es una implementaci´on eficiente del m´etodo TBL (Brill, 1995) basado en la generaci´on de reglas de transformaci´on guiada por el descubrimiento de errores. MaxEnt (Baldridge, 2005), que emplea modelado de m´axima entrop´ıa para integrar, en forma de restricciones, el conocimiento del problema que proporciona el corpus de entrenamiento. Adem´as, disponemos de un etiquetador simple que nos servir´adel´ınea base para nuestros experimentos. En ´el, se asocia a cada palabra la etiqueta m´as repetida para ella en el corpus de entrenamiento. 4.2. TextRank inverso Adem´as del m´etodo supervisado para TextRank presentado en la secci´on 3 de este art´ıculo, hemos incluido en nuestro grupo de experimentos dos variantes sobre la idea original. La primera variante, que denominaremos TextRank inverso (TextRankI), consiste en calcular las probabilidades de transici´on en sentido contrario, procesando el texto de derecha a izquierda. De esta forma, P(t|t) refleja la probabilidad de que la etiqueta t aparezca despu´es de la etiqueta t, y se estima con la siguiente f´ormula a partir de los ejemplos del corpus de entrenamiento: P(t|t)=C(t, t) C(t) En general, los resultados de esta variante son peores que el tratamiento natural (de izquierda a derecha), pero aportan una visi´on alternativa del problema que aprovecharemos en la siguiente variante. 4.3. TextRank combinado La segunda variante (TextRankC) consiste en la combinaci´on de los resultados de TextRank y TextRank inverso. Hemos aplicado la t´ecnica de stacking, que consiste en utilizar los resultados de una primera etapa de aprendizaje para entrenar un clasificador de segundo nivel. Con ello se consigue combinar las opiniones producidas por los etiquetadores de la primera etapa de aprendizaje de una manera muy flexible. La t´ecnica de stacking suele dar muy buenos resultados cuando se combinan opiniones complementarias. Esto se suele conseguir o bien utilizando distinto material de entrenamiento, o bien utilizando distintos clasificadores sobre un ´unico conjunto de datos de entrenamiento. Este esquema ha sido aplicado con ´exito en diversas tareas, en concreto en el ´ambito del Procesamiento del Lenguaje Natural existen trabajos que aplican una doble etapa de decisi´on para el etiquetado POS (Halteren, 2001), la desambiguaci´on de significados (Florian, 2002), el an´alisis sint´actico (Henderson, 1999) o el reconocimiento de entidades con nombre (Florian, 2003). En nuestro caso, para cada palabra del corpus de entrenamiento hemos creado un registro que contiene las tres etiquetas mejor situadas seg´un TextRank y TextRank inverso 37 TextRank como motor de aprendizaje en tareas de etiquetado para dicha palabra, as´ı como las puntuaciones obtenidas por cada una de las propuestas. El registro se completa con la etiqueta real que es extra´ıda directamente del corpus de entrenamiento. Con todos los registros obtenidos del corpus de entrenamiento, entrenamos un ´arbol de decisi´on que determinar´a la etiqueta a asignar a una palabra en funci´on de las propuestas de TextRank y TextRank inverso. La figura 1 muestra todos los elementos que participan en el esquema, dentro del recuadro en trazo discontinuo se incluye el proceso que permite convertir el corpus de entrenamiento en base de datos de entrenamiento gracias a la aplicaci´on de los modelos previamente entrenados para TextRank. Un proceso similar se aplica al corpus de test, aunque no se ha detallado en el gr´afico para no complicarlo en exceso. Una vez que se dispone de ambas bases de datos, se sigue el esquema cl´asico de entrenamiento/aplicaci´on de cualquier proceso de aprendizaje autom´atico cuya salida es utilizada para componer el corpus de test anotado. Figura 1: Proceso de Stacking 5. Resultados Antes de empezar con estos experimentos sab´ıamos que iba a ser dif´ıcil obtener mejores resultados que las herramientas con las que nos comparar´ıamos. La raz´on: estas herramientas est´an muy especializadas en la tarea del etiquetado POS e incluyen heur´ısticas especiales para resolver de la mejor manera posible este problema. Los resultados no nos han sorprendido, aunque nuestra aproximaci´on ha dado muestras de saber adaptarse bien a este problema. La tabla 2 muestra los resultados de todos los sistemas descritos en este art´ıculo. Se muestra la medida accuracy que calcula el porcentaje de palabras del corpus de test que han sido etiquetadas correctamente. Con respecto la l´ınea base, TextRank supera con creces las establecidas para los dos corpus. En cuanto a la comparativa con otras herramientas, nuestro m´etodo (la versi´on TextRankC) s´olo supera a TreeTagger y MBT con el corpus Susanne, se queda bastante cerca del resto de etiquetadores para dicho corpus y un poco m´as alejado cuando utilizamos el corpus Penn. Susanne Penn L´ınea base 79.15 % 80.01 % TnT 93.61 % 95.48 % TreeTagger 91.27 % 94.28 % fnTBL 93.01 % 95.04 % MBT 91.16 % 94.40 % MaxEnt 93.09 % 95.47 % TextRank 90.32 % 92.14 % TextRankI 89.84 % 91.70 % TextRankC 91.51 % 93.28 % Tabla 2: Resultados de los experimentos. Pese a obtener peores resultados que la mayor´ıa de las herramientas, hay que destacar que nuestro m´etodo est´aa´un en una fase muy preliminar. Por ejemplo, no se incluye ninguna heur´ıstica especial para las palabras desconocidas. Es de esperar que los resultados se acerquen m´as a medida que se incluya en la construcci´on del grafo este tipo de informaci´on, con la que cuenta la mayor´ıa de las herramientas con las que lo hemos comparado. Tambi´en hay que destacar que el m´etodo se ha comportado mejor en una tarea m´as dura (corpus Susanne con m´as etiquetas) que en una m´as sencilla (corpus Penn con menos etiquetas entre las que decidir). 5.1. Otras tareas PLN Nuestro m´etodo puede ser aplicado a cualquier tarea siempre que el corpus que la describa sea de dos columnas (palabraetiqueta). Gracias a la notaci´on IOB es posible especificar tareas en las que se etiquetan grupos de palabras con corpus de dos columnas. De esta forma hemos podido aplicar TextRank supervisado a las siguientes tareas: Reconocimiento de entidades con nombre para el espa˜nol (NER-E), usando el 38 Fermín Cruz, José Antonio Troyano, Fernando Enríquez y F. Javier Ortega corpus distribuido para la tarea propuesta en CoNLL 2002. Reconocimiento de entidades biom´edicas (NER-B), usando el corpus distribuido para la tarea propuesta en COLING 2004. An´alisis sint´actico superficial (Chunk), usando el corpus distribuido para la tarea propuesta en CoNLL 2000. En la tabla 3 se pueden ver los tama˜nos de las respectivas particiones de entrenamiento y test para estas tareas. A pesar de que el conjunto de etiquetas es en todos los casos muy peque˜no y que los corpus de entrenamiento son grandes, son tareas tan, o m´as complejas que las que plantearon los corpus Penn y Susanne ya que presentan un mayor grado de dependencia contextual. Entren. Test Etiquetas NER-E 529413 105842 9 NER-B 985102 202078 11 Chunk 423454 94754 23 Tabla 3: Tama˜nos de los corpus de las tareas NER-E, NER-B y Chunk. El dise˜no experimental es el mismo que el que empleamos para los corpus Susanne y Penn. En la tabla 4 se pueden ver los resultados de los distintos sistemas usando la medida accuracy. NER-E NER-B Chunk L´ınea base 71.90 % 72.64 % 63.08 % TnT 94.78 % 88.97 % 89.62 % TreeTagger 90.58 % 84.79 % 84.40 % fnTBL 94.30 % 90.49 % 89.54 % MBT 94.38 % 88.71 % 90.61 % MaxEnt 95.03 % 87.52 % 92.83 % TextRank 92.72 % 86.75 % 87.34 % TextRankI 90.85 % 87.78 % 78.84 % TextRankC 92.93 % 89.71 % 89.24 % Tabla 4: Resultados para las tareas NER-E, NER-B y Chunk. Al igual que para los experimentos POS, la versi´on combinada de TextRank sigue superando a las otras dos. En cuanto a la comparativa con los otros sistemas, es claramente favorable en la tarea NER-B (donde supera a todos los sistemas salvo a fnTBL), est´a igualada en Chunk (supera a TreeTagger y est´a muy cerca de TnT y fnTBL) y m´as desfavorable para NER-E (supera a TreeTagger y del resto queda a una distancia entre 1.4 y 2.1 puntos). En general podemos decir que el m´etodo se adapta bien a estas tareas m´as contextuales, acerc´andose m´as al resto de sistemas que en los experimentos POS. 6. Conclusiones y trabajo futuro En este trabajo hemos estudiado de qu´e manera se pueden aplicar las ideas del m´etodo no supervisado TextRank para que aproveche la informaci´on disponible en un corpus de entrenamiento anotado. Hemos definido un m´etodo de construcci´on de grafos basado en la coocurrencia de palabras, que incluye el conocimiento acumulado en el corpus de entrenamiento mediante probabilidades de emisi´on y transici´on similares a las utilizadas en un modelo de Markov. Hemos realizado un estudio experimental para la tarea POS y hemos comparado los resultados con los obtenidos con herramientas especializadas en este tipo de etiquetado. Los resultados demuestran que el m´etodo obtiene un etiquetado satisfactorio, y aunque la comparativa es desfavorable con la mayor´ıa de los casos, llegamos incluso a superar a una de esta herramientas especializadas cuando entrenamos con el corpus Susanne. Hemos reproducido los experimentos para otras tareas PLN como NER o Chunking obteniendo mejores resultados que en el POS en la comparativa con los otros sistemas. Nuestro trabajo futuro pasa por estudiar formas alternativas de creaci´on del grafo que exploten otras caracter´ısticas adem´as de la coocurrencia, e incluir en el m´etodo heur´ısticas que nos permitan presentar resultados m´as competitivos. Bibliograf´ıa Baldridge, J., Morton, T., Bierner, G.: Maxent, Mature Java package for training and using maximum entropy models. An OpenNLP project. (2005) Brants, T.: TnT. A statistical part-of-speech tagger. In Proceedings of the 6th Applied NLP Conference (ANLP00). USA (2000) Brill, E.: Transformation-based error-driven learning and natural language processing: 39 TextRank como motor de aprendizaje en tareas de etiquetado A case study in part of speech tagging. In Computational Linguistics 21(4), (1995) Brin, S., Page, L.: The anatomy of a largescale hypertextual Web search engine. In Computer Networks and ISDN Systems. (1998) Daelemans, W., Zavrel, J., van der Sloot, K., van den Bosch, A.: TiMBL Memory Based Learner, version 5.1, Reference Guide. ILK Research Group Technical Report Series no. 04-02. The Netherlands (2004) Florian, R., Yarowsky, D., 2002. Modeling Consensus: Classifier Combination for Word Sense Disambiguation. In Proceedings of EMNLP’02, Philadelphia, pp 25– 32. Florian, R., Ittycheriah, A., Jing, H., Zhang, T., 2003. Named Entity Recognition through Classifier Combination. In Proceedings of CoNLL-2003, Canada, pp 168– 171. Halteren, v.H., Zavrel, J., Daelemans, W., 2001. Improving accuracy in word class tagging through the combination of machine learning systems. Computational Linguistics 27, pp 199–230. Henderson, J.C., Brill, E., 1999. Exploiting diversity in natural language processing. Combining parsers. In 1999 Joint Sigdat Conference on Empirical Methods in Natural Language Processing and Very Large Corpora, ACL, USA, pp 187–194. Mihalcea, R., Tarau, P.: TextRank. Bringing Order into Texts. In Proceedings of the Conference on Empirical Methods in Natural Language Processing. Barcelona, Spain (2004) Mihalcea, R., Tarau, P. Figa, E.: PageRank on Semantic Networks, with application to Word Sense Disambiguation. In Proceedings of The 20st International Conference on Computational Linguistics . Switzerland, Geneva (2004) Ngai, G., Florian, R.: Transformation-based learning in the fast lane. In Proceedings of North Americal ACL 2001, (2001) Radev, D., Mihalcea, R. (organizers): Graphbased Algorithms for Natural Language Processing. Workshop at HLT/NAACL. New York, USA (2006) Schmid, H.: Probabilistic Part-of-Speech Tagging Using Decision Trees. In International Conference on New Methods in Language Processing. Manchester, UK (1994) 40 Fermín Cruz, José Antonio Troyano, Fernando Enríquez y F. Javier Ortega