La Combinación de Sistemas y el PLN

La Combinaci´on de Sistemas y el PLN ∗ System Combination and NLP Fernando Enr´ıquez, Jos´e A. Troyano, Ferm´ın Cruz yF. Javier Ortega Dep. de Lenguajes y Sistemas Inform´aticos Universidad de Sevilla Avda. Reina Mercedes s/n 41012 Sevilla [email protected] Resumen: La combinaci´on de sistemas constituye un ´area de investigaci´on ampliamente estudiada en el ´ambito del Reconocimiento de Patrones, en donde se han desarrollado m´ultiples t´ecnicas para aprovechar la diversidad de m´etodos de clasificaci´on de los que se dispone actualmente gracias al Aprendizaje Autom´atico. Tras un an´alisis de los trabajos que emplean alguna de estas t´ecnicas para resolver tareas del PLN, vemos que aunque se le haya prestado atenci´on en m´ultiples trabajos a esta l´ınea de investigaci´on, se suelen emplear los m´etodos m´as populares debido quiz´as al desconocimiento general sobre la existencia de un gran n´umero de opciones disponibles para llevar a cabo la combinaci´on. En este trabajo pretendemos dar a conocer los aspectos te´oricos en los que se apoya el uso de estas t´ecnicas, as´ı como mostrar el amplio abanico de opciones existentes hoy en d´ıa, adem´as de repasar los trabajos m´as importantes de PLN que han hecho uso de alguna de ellas. Palabras clave: Aprendizaje Autom´atico, combinaci´on de sistemas Abstract: The combination of systems is an area of widely studied research in the field of Recognition Patterns, where there have been developed many techniques for taking advantage of the diversity of classification methods that are currently available thanks to Machine Learning. After an analysis of the works that employ some of these techniques to solve NLP tasks, we see that although this research has been considered in many cases, only the most popular methods are often used perhaps due to widespread ignorance about the existence of a large number of options available for carrying out the combination. In this paper we intend to present the theoretical aspects that support the use of these techniques, to show the wide range of options existing today, and review the most important NLP works where any of them has been used. Keywords: Machine Learning, system combination 1. Introducci´on Durante muchos a˜nos han ido surgiendo un n´umero considerable de m´etodos de clasificaci´on, y aunque en algunos casos podamos reconocer uno de ellos como el mejor dotado para la tarea que pretendemos afrontar, no es lo habitual disponer de un clasificador perfecto que alcance una precisi´on del 100 %. En otros muchos casos no podemos ni tan siquiera disponer de una lista ordenada que nos facilite el nombre del mejor sistema de clasificaci´on. En el primer caso, donde te- ∗Parcialmente financiado por el proyecto I+D HUM2007-66607-C04-04. nemos un candidato destacado del resto, no podemos asegurar que ´este no carezca de alguna caracter´ıstica deseable que s´ı se encuentra presente en el resto de clasificadores. En el segundo caso expuesto, parece l´ogico pensar que ser´ıa mejor poder trabajar con todos los clasificadores, combinando sus resultados para extraer lo mejor de cada uno, en lugar de decantarnos por uno de ellos, descartando al resto. Un gran n´umero de tareas del Procesamiento del Lenguaje Natural (PLN) pueden considerarse tareas de clasificaci´on, donde debemos resolver alg´un tipo de ambig¨uedad relacionada con el contenido tex- Procesamiento del Lenguaje Natural, Revista nº 45, septiembre 2010, pp 67-75 recibido 28-04-10 revisado 18-05-10 aceptado 20-05-10 ISSN 1135-5948 © 2010 Sociedad Española para el Procesamiento del Lenguaje Natural tual de una colecci´on de documentos, pudiendo aplicarse m´ultiples algoritmos de clasificaci´on, as´ı como t´ecnicas y estrategias de combinaci´on de sistemas. En la siguiente secci´on comentaremos las razones que justifican la combinaci´on y los diferentes puntos de vista desde los que podemos aplicarla. A continuaci´on comentaremos las familias m´as influyentes de t´ecnicas y algoritmos. En la secci´on 4 abordaremos la combinaci´on de sistemas desde el punto de vista de su aplicaci´on al PLN para pasar finalmente a exponer las conclusiones. 2. La Combinaci´on de Sistemas En Hansen y Salamon (Hansen y Salamon, 1990) se establecen la precisi´on y la diversidad como requisitos necesarios y suficientes para llevar a cabo con ´exito la combinaci´on de dos o m´as sistemas de clasificaci´on. Por su parte Dietterich (Dietterich, 2000) justifica la combinaci´on desde tres puntos de vista. Considerando el punto de vista estad´ıstico, escoger un clasificador para resolver nuestro problema entra˜na un riesgo, ya que ´este puede no ser el m´as capacitado para el caso particular que estamos tratando. Debido a esto, puede que la combinaci´on no nos proporcione mejores resultados que el mejor clasificador individual de que disponemos, pero s´ı que elimina o mitiga el riesgo de equivocarnos en la selecci´on. Desde el pun- to de vista computacional, a´un teniendo un volumen de datos tal que haga desaparecer el problema estad´ıstico mencionado anteriormente, existe el problema de los m´aximos locales, en los que pueden incurrir muchos algoritmos en su b´usqueda del objetivo. Una vez m´as, la combinaci´on de los clasificadores puede realizar la b´usqueda partiendo de muchos puntos diferentes del espacio de hip´otesis y acercarse m´as a la soluci´on ideal de lo que consiguen acercarse estos clasificadores individualmente. Por ´ultimo, desde el punto de vista de la representaci´on hay que considerar la posibilidad de que el espacio de b´usqueda de los clasificadores no contenga la soluci´on que estamos buscando, mientras que la combinaci´on puede darnos la oportunidad de expandir dicho espacio con la posibilidad que esto acarrea de que consigamos incluir el objetivo en dicho espacio y tengamos opciones de aproximarnos m´as a ´el. Apoy´andose en estas afirmaciones se han desarrollado m´ultiples m´etodos de combi- Figura 1: Justificaci´on para la combinaci´on seg´un Dietterich. naci´on, muchos de ellos aportando enfoques muy dispares que en (Kuncheva y Whitaker, 2003) son organizados en base a cuatro niveles como se aprecia en la figura 2. Figura 2: Enfoques para la combinaci´on de clasificadores. Estos niveles representan el punto del proceso donde recae el peso de la combinaci´on, pudiendo hacer uso de diferentes colecciones de datos (data level), diferentes subconjuntos de caracter´ısticas empleadas para representar los ejemplos (feature level), diferentes clasificadores (classifier level) o distintas t´ecnicas de combinaci´on (combiner level). Pr´acticamente la totalidad de m´etodos existentes puede categorizarse en funci´on del nivel en el que se ejerce mayor ´enfasis. Existen otros criterios para agrupar los m´etodos de combinaci´on, como puede ser la distinci´on entre m´etodos de fusi´on y m´etodos de selecci´on. En la fusi´on todas las opiniones Fernando Enríquez, José A. Troyano, Fermín Cruz, F. Javier Ortega 68 gozan de la misma consideraci´on y se busca una opini´on com´un, mientras que en la selecci´on se elige un participante responsable de clasificar un determinado grupo de ejemplos. No todos los m´etodos de combinaci´on existentes son aplicables a cualquier conjunto de clasificadores. Es importante considerar el tipo de informaci´on que estos producen como salida. En (Xu, Krzyzak, y Suen, 1992) se describen tres posibilidades: el abstract level (la salida es una ´unica etiqueta o un subconjunto de las etiquetas posibles), el rank level (se devuelven las etiquetas o un subconjunto de ellas ordenadas seg´un el orden de preferencia) y el measurement level (el clasificador atribuye a cada etiqueta un valor indicativo de la confianza que se tiene en ella). 3. M´etodos de Combinaci´on Algunos de los m´etodos de combinaci´on m´as importantes son los que pasamos a comentar a continuaci´on. Votaci´on Uno de los m´etodos de combinaci´on m´as populares es el basado en la llamada Teor´ıa de Elecci´on Social, que relaciona el concepto de elecciones con el problema de clasificaci´on, el de votantes con los clasificadores implicados y el de votos con las etiquetas propuestas por cada uno de ellos. La t´ecnica de votaci´on por mayor´ıa decreta como vencedor a aquel que consiga superar en votos a todos sus rivales, y aunque el criterio m´as popular es el de mayor´ıa plural (el candidato con m´as votos gana), existen otros como el de mayor´ıa simple (el candidato que supera el 50 % de los votos gana) o por unanimidad (el candida- to debe recibir todos los votos para ganar). Estos m´etodos tienen la ventaja de ser independientes de los datos ya que no requieren entrenamiento previo para su posterior ejecuci´on sobre los ejemplos a clasificar. Tambi´en existe la posibilidad de ponderar los votos para darle m´as importancia a unos clasificadores que a otros bas´andonos en criterios subjetivos o en las respectivas tasas de acier- to. Estos m´etodos tambi´en pueden agruparse en mayoritarios y posicionales en funci´on de como se valoran los votos. En el primer caso se realizan comparaciones por pares, y en el segundo la valoraci´on de los candidatos se cuantifica en base a su posici´on relativa al resto. Los m´etodos Condorcet yBorda Count son los m´etodos m´as representativos de estos dos grupos respectivamente. Operaciones sobre valores cont´ınuos Probablemente el m´etodo m´as sencillo es el que podemos aplicar siempre que obtengamos salidas catalogadas en el measurement level, a trav´es de la aplicaci´on de una funci´on combinatoria (i.e. media, m´aximo, media arm´onica o producto). Son m´etodos sencillos que no requieren entrenamiento previo, aunque tambi´en podemos hacer uso de otras funciones que s´ı lo requieran como puede ser la media ponderada. Teorema de Bayes La aplicaci´on del Teorema de Bayes ha dado muy buenos resultados en m´ultiples tareas, incluso superando a m´etodos m´as complejos. En este caso, se trata de calcular la probabilidad a posteriori de que dadas cetiquetas posibles y dada una serie de observaciones s=s1, . . . , sL, la etiqueta real sea ωk. Las observaciones se corresponden con las etiquetas propuestas por los Lclasificadores, representando los valores µobtenidos para k= 1, . . . , c el grado de apoyo que recibe cada etiqueta: µk(x)∝P(ωk) L Y i=1 P(si|ωk) Basados en la memorizaci´on Podemos encontrar diversos algoritmos que comparten una idea fundamental, que consiste en memorizar el comportamiento demostrado por los clasificadores en los ejemplos de entrenamiento, para luego tomar decisiones sobre los nuevos elementos bas´andose en el pasado. Es el caso del Behavior Knowledge Space (BKS) (Huang y Suen, 1995), perteneciente a la familia de m´etodos multinomiales y que se basa en estimar la probabilidad P(ωk|s) para todo k= 1, . . . , c y para toda combinaci´on de votos posible s. Estas probabilidades se almacenan en una tabla indexada junto a los contadores donde se van acumulando las veces en que cada combinaci´on dio lugar a cada una de las etiquetas posibles. Para clasificar un nuevo elemento, se accede a la tabla indexada, recuper´andose la etiqueta m´as utilizada entre los ejemplos que ocasionaron la misma combinaci´on de salidas de los clasificadores participantes. La misma filosof´ıa comparte el m´etodo Decision Template (Kuncheva, Bezdek, y Duin, 2001), que genera una plantilla DT (j) para cada clase ωj, que representa la matriz de salidas m´as representativas de los clasificadores para La Combinación de Sistemas y el PLN 69 dicha categor´ıa. Posteriormente se busca la m´ınima distancia entre las salidas asociadas al ejemplo que se desea clasificar respecto a cada DT(j). Basados en caracter´ısticas Las caracter´ısticas utilizadas para describir los ejemplos a clasificar suponen otro foco de atenci´on en el que podemos aplicar la combinaci´on. El an´alisis de caracter´ısticas puede dividirse en dos aproximaciones basadas en la selecci´on y la extracci´on. En el primer caso se aplican algoritmos para obtener subconjuntos de caracter´ısticas de forma que se maximice la diversidad, pudiendo tratarse de algoritmos denominados wrappers,filters oembedded. Los wrappers utilizan t´ecnicas de aprendizaje para valorar los posibles subconjuntos de caracter´ısticas pudiendo aplicar diferentes algoritmos de b´usqueda para hallar el subconjunto deseado. Los filters son m´etodos gen´ericos y suelen formar parte del preprocesado mientras que los embedded son m´etodos incrustados en el propio proceso de entrenamiento del clasificador. La combinaci´on se puede aplicar sobre diferentes subconjuntos obtenidos mediante alguna de estas t´ecnicas, aunque otros m´etodos como el Random Subspace Method (Ho, 1998) directamente combinan subconjuntos obtenidos de forma aleatoria. En cuanto a la extracci´on, puede llevarse a cabo mediante m´etodos que se encargan de la construcci´on de nuevas caracter´ısticas a partir de las ya existentes, as´ı como de la reducci´on de la dimensi´on del espacio original. Este es el caso del Singular Value Decomposition, m´etodo por el cu´al se obtiene una aproximaci´on de la matriz original utilizando los autovalores y autovectores en un proceso de factorizaci´on. Explorando agrupaciones de clasificadores Los m´etodos que exploran diversos subconjuntos de clasificadores buscan el “equipo” de participantes mejor dotado para resolver la tarea. Uno de ellos es el basado en las integrales difusas, que proviene del an´alisis de decisiones multicriterio, y consiste en valorar la “bondad” de cada subconjunto de clasificadores atendiendo al concepto de medida difusa. Seg´un la descripci´on, si tomamos Xcomo el conjunto de criterios y℘(X) como el conjunto de las partes de X, podemos definir como medida difusa la funci´on que cumple: g:℘(X)→[0,1], g(∅) = 0, g(X) = 1, A⊂B⇒g(A)≤g(B)A, B ∈℘(X) En este caso, los criterios se corresponder´ıan a las salidas aportadas por los diferentes clasificadores, y una vez obtenidas las medidas difusas para los subconjuntos se aplicar´a la integral, cuyas versiones m´as populares son las de Sugeno, que puede verse como una media ponderada, y la de Choquet, que se asemeja m´as a una generalizaci´on del concepto de mediana. El algoritmo adaptado a la combinaci´on de clasificadores se muestra en (Pal, 2001). Otro algoritmo que explora los subconjuntos de clasificadores posibles es el basado en la Teor´ıa de Dempster-Shafer, en el que se eval´ua el grado de creencia (belief) en una hip´otesis cuando disponemos de varias fuentes de evidencia (Rogova, 1994). Bagging y Boosting Centrados en el Data level seg´un los enfoques mostrados en 2 nos encontramos las t´ecnicas de Bagging yBoosting (Witten y Frank, 2000). La primera genera la variabilidad necesaria para la combinaci´on creando diferentes versiones de los datos de entrenamiento mediante un remuestreo con reemplazamiento, procediendo finalmente a un proceso de votaci´on para combinar los clasificadores obtenidos a trav´es de los distintos conjuntos de datos. Boosting por su parte asigna pesos a los ejemplos, reflejando en ellos la dificultad que entra˜na su clasificaci´on y creando versiones progresivas del corpus dotando de mayor relevancia a los ejemplos m´as dif´ıciles de clasificar. ECOC El m´etodo denominado Error Correcting Output Codes (ECOC) (Dietterich y Bakiri, 1991) representa un caso particular de combinaci´on de sistemas, ya que no encaja en la mayor´ıa de las taxonom´ıas empleadas habitualmente para agrupar los m´etodos existentes. Se trata de un m´etodo que realiza la combinaci´on en base a las salidas o clases asignadas a los ejemplos, generando la variabilidad en el propio conjunto de etiquetas C=ω1, . . . , ωc, creando particiones binarias de este conjunto, a las que se le asigna un clasificador binario especializado. Para c clases podemos representar cada una de estas particiones a trav´es de un vector binario de Fernando Enríquez, José A. Troyano, Fermín Cruz, F. Javier Ortega 70 celementos, donde se indica para cada etiqueta en qu´e lado de la partici´on ha ca´ıdo. Si colocamos todas las particiones formando las columnas de una matriz de c´odigos, las filas resultantes representar´an a cada etiqueta en todas las particiones consideradas, recibiendo el nombre de codeword, mientras que a cada columna se le asignar´a un clasificador. Al recibir un nuevo ejemplo se ejecutar´an los clasificadores generando un codeword, al que se le aplicar´a alguna medida de similitud sobre la matriz de c´odigos para determinar la etiqueta m´as probable. Meta-aprendizaje El Meta-aprendizaje es otra de las v´ıas que m´as se han explorado a la hora de combinar clasificadores, entendiendo como tal la utilizaci´on de las salidas proporcionadas por un m´etodo de aprendizaje autom´atico como entrada para otro. A estos m´etodos se les suele denominar Stacking ya que se puede interpretar este proceso como una pila, en la que un algoritmo se nutre de los resultados del algoritmo en el que se apoya (sean uno o varios). Hay que distinguir algunas variantes entre las que destaca el Cascading y el bautizado como Stacked Generalization por (Wolpert, 1992). En el primero un clasificador es entrenado con la totalidad del conjunto de datos de entrenamiento, y su salida es empleada como entrada para otro clasificador, que a su vez puede enlazarse con otro y as´ı sucesivamente, mientras que el segundo queda reflejado en la figura 3, donde Zes el corpus de entrenamiento, Dison los clasificadores y rilas etiquetas que proponen. Figura 3: Esquema general del Stacking 4. La Combinaci´on y el PLN Para valorar el grado de presencia de estas t´ecnicas en el ´area del PLN, hemos analizado un gran n´umero de trabajos en los que se aplica alguna de ellas, extrayendo los de mayor relevancia, principalmente en base al n´umero de citas recibidas. Un primer an´alisis de estos trabajos nos muestra la linea temporal que comenz´o en los a˜nos noventa y tuvo su punto ´algido a principios de la pasada d´ecada como vemos en la figura 4. Figura 4: Referencias seleccionadas por a˜no. 4.1. Algunas propuestas En las pr´oximas secciones pasamos a presentar algunos de los trabajos m´as representativos en cuanto a la aplicaci´on de la combinaci´on de sistemas al PLN. Origenes En (Belkin y Callan, 1993) se afrontaba la tarea de la Recuperaci´on de Informaci´on (IR) combinando diferentes formulaciones booleanas de querys sobre una base de datos de documentos. Un a˜no m´as tarde, en (Frederking y Nirenburg, 1994) tambi´en se combin´o un sistema basado en conocimiento con otro basado en ejemplos y un sistema de transferencia l´exica para resolver la tarea de la Traducci´on Autom´atica. A partir de 1998, con la publicaci´on de los trabajos (Halteren, Zavrel, y Daelemans, 1998) y (Brill y Wu, 1998), fue cuando un mayor n´umero de investigadores desarrollaron sus trabajos aplicando las t´ecnicas de combinaci´on a tareas del PLN. Ambos art´ıculos se dedicaban al etiquetado POS, aunque les sucedieron trabajos centrados en otras tareas. Part-Of-Speech Tagging (POS) En los trabajos de Halteren y Brill se utilizaron clasificadores basados en modelos de Markov, reglas de transformaci´on y en el algoritmo de m´axima entrop´ıa, a˜nadiendo el primero un etiquetador basado en ejemplos mientras que el segundo agrega un sencillo algoritmo basado en unigramas a la lista de clasificadores empleados. Ambos muestran mejoras sobre todos los clasi- La Combinación de Sistemas y el PLN 71 ficadores base mediante votaci´on y Stacking aunque este ´ultimo m´etodo obtiene los mejores resultados. En (Borin, 2000) el problema se afronta desde otra perspectiva, mediante la utilizaci´on de un sistema de combinaci´on basado en reglas motivadas ling¨u´ısticamente. Esto hace de ´el un sistema pionero al ser un sistema de combinaci´on basado en conocimiento, intentando profundizar en c´omo deben utilizarse las diferencias existentes entre los diferentes clasificadores para conseguir mejores resultados en la asignaci´on final de las etiquetas. En (Kuta et al., 2008) se afronta la tarea una vez m´as con un idioma menos prol´ıfico que el ingl´es en cuanto a disponibilidad de recursos como es el polaco. Aqu´ı de nuevo se emplean m´etodos de votaci´on sobre diversos etiquetadores conocidos. Word Sense Disambiguation (WSD) En la tarea de WSD sorprenden las mejoras obtenidas por (Pedersen, 2000) con un sistema de combinaci´on bastante sencillo, en el que b´asicamente se var´ıa el tama˜no de las ventanas de contexto para obtener la variabilidad necesaria partiendo de un clasificador basado en el algoritmo Na¨ıve Bayes. Los experimentos se llevaron a cabo con los sustantivos line einterest y con un sencillo sistema de votaci´on por mayor´ıa aplicado sobre nueve versiones del clasificador bayesiano lograron sobrepasar a otros sistemas anteriores. En (Florian et al., 2002) se completa el trabajo que los autores presentaron con ´exito al certamen SENSEVAL-2 combinando cuatro clasificadores mediante t´ecnicas de votaci´on. Concretamente se agregan nuevos clasificadores consiguiendo un conjunto diverso de m´etodos muy populares y otros m´as novedosos, adem´as de realizarse nuevos experimentos basados en t´ecnicas de stacking, con los que se obtuvieron resultados por encima de las mejores cifras conocidas hasta la fecha. En otro trabajo interesante, (Klein et al., 2002) muestra como la combinaci´on de sistemas que alcanzan resultados mediocres puede alcanzar medidas de precisi´on a la altura de los mejores sistemas publicados para esta tarea. En este caso se recopilaron 23 trabajos de alumnos matriculados en el curso de PLN ofrecido por la Universidad de Stanford, generando un conjunto de clasificadores muy heterog´eneo. M´as recientemente vemos como Cuong introduce en su Tesis Doctoral (Cuong, 2007) dedicada al WSD el concepto de Meta-Stacking, que se diferencia del modelo de stacking habitual por utilizar como entradas para el segundo nivel de aprendizaje los resultados obtenidos por diferentes m´etodos de combinaci´on aplicados sobre los clasificadores base, en lugar de usar directamente las etiquetas proporcionadas por ´estos. Named Entity Recognition (NER) El grupo de Florian vuelve a dedicar esfuerzos a la combinaci´on, en este caso sobre la tarea del NER en (Florian, 2002), empleando Cascading sobre los clasificadores fnTBL y Snow. M´as tarde en (Jing et al., 2003) y (Florian et al., 2003) estudian el impacto que tiene en los resultados de la combinaci´on la inclusi´on de recursos adicionales como gazetteers y las salidas de otros clasificadores en el proceso. Otro experimento interesante es el realizado por (Wu, Ngai, y Carpuat, 2003), en el que se combinan fases de votaci´on y stacking para dar lugar a un esquema stacked-voted-stacked, con el que se consigui´o un valor Fβ=1 = 89,51 que supera en casi 5 puntos al mejor sistema del CoNLL-2002 y supone una reducci´on del error del 19.7 %. En (Kozareva et al., 2007) por otro lado se muestran, adem´as de la aplicaci´on de diversos m´etodos de votaci´on a un conjunto heterog´eneo de clasificadores, la aportaci´on del sistema resultante a diversas tareas finales, como la recuperaci´on de informaci´on geogr´afica o el modelado conceptual. Utilizando modelos de Markov, m´axima entrop´ıa y algoritmos basados en ejemplos, se obtiene un reconocedor de entidades, que tras ser evaluado sobre los datos de las competiciones CoNLL-2002 (espa˜nol y holand´es) y HAREM-2005 (portugu´es) se situar´ıa en tercera posici´on (de 15 participantes) y quinta (de 13 participantes) respectivamente. El reconocimiento de entidades en textos biom´edicos es otra ´area en la que se ha experimentado con t´ecnicas de combinaci´on. Una muestra es el trabajo (Dimililer, Varoˇglu, y Altin¸cay, 2007), donde se mezclan clasificadores con buena precisi´on con otros que alcanzan buenos porcentajes de cobertura. En este ´ultimo se hace uso de los algoritmos gen´eticos para medir la diversidad en base al rendimiento combinado obtenido con los datos de entrenamiento. Otras tareas Existen otras tareas que se llevan beneficiando de las virtudes de la combinaci´on des- Fernando Enríquez, José A. Troyano, Fermín Cruz, F. Javier Ortega 72 de hace tiempo, como demuestran los trabajos (Henderson y Brill, 1999) para el Parsing (PAR) o (Hull, Pedersen, y Schutze, 1996) y (Larkey y Croft, 1996) para la clasificaci´on de documentos (DC). Otros contin´uan aprovech´andolas actualmente gracias por ejemplo a la aparici´on de nuevos algoritmos de clasificaci´on, como ocurre en (Silva y Ribeiro, 2007) con el uso de los RVM (Relevance Vector Machine) en donde se aprovechan las ventajas que aportan frente a los habituales SVM. 4.2. An´alisis de la bibliograf´ıa Tras recopilar un gran n´umero de trabajos en los que se aplican t´ecnicas de combinaci´on a alguna tarea del PLN, seleccionamos los 70 trabajos m´as relevantes bas´andonos en el n´umero de citas o el lugar de publicaci´on entre otros factores. En la figura 5 se aprecia el reparto en cuanto a las tareas que han recibido m´as atenci´on en los trabajos seleccionados. En cuanto a las t´ecnicas de clasificaci´on y de combinaci´on apreciamos un uso dispar, ya que en lo referente a los algoritmos de clasificaci´on, si bien hay algunos m´etodos que destacan ligeramente del resto, existe un mayor equilibrio en cuanto a la frecuencia de uso. En los m´etodos de combinaci´on sin embargo, los m´etodos de votaci´on y Stacking acaparan la mayor parte de los trabajos, dejando entrever una posible falta de experimentaci´on con el resto de m´etodos que hemos comentado y que podr´ıan ofrecer mejoras en m´ultiples tareas de inter´es para el ´ambito del PLN. Figura 5: Clasificadores empleados, tareas afrontadas y m´etodos de combinaci´on aplicados en las referencias seleccionadas. En cuanto a los resultados presentados en los trabajos, resulta dif´ıcil establecer comparaciones debido a la gran variedad de m´etodos de clasificaci´on y combinaci´on, adem´as de las tareas y los datos, contabiliz´andose cerca de 50 corpus distintos. A´un as´ı hemos confeccionado una tabla donde se reflejan las mejoras m´ınima, m´axima y media alcanzadas en los trabajos que aplican combinaci´on de sistemas a alguna tarea del PLN. Adem´as, mostramos estos mismos valores para los casos en los que se ha aplicado un m´etodo de votaci´on o Stacking (las t´ecnicas de combinaci´on m´as utilizadas seg´un se aprecia en la figura 5) as´ı como para el grupo formado por el resto de t´ecnicas aqu´ı comentadas. Lejos de querer darle importancia a los valores concretos, pretendemos interpretar estos resultados como claros indicios sobre las capacidades de mejora que pueden lograrse en muchas tareas del PLN, as´ı como mostrar la val´ıa de muchos m´etodos ya existentes que gozan de mucha menos popularidad que los m´etodos de votaci´on y Stacking. Respecto a las tareas, podemos apreciar diferencias significativas entre los valores de mejora, lo cual es fruto, desde nuestro punto de vista, de la dificultad de la tarea y del margen de mejora de los clasificadores individuales. Resulta m´as dif´ıcil mejorar resultados en tareas como el etiquetado POS, donde partimos de resultados muy buenos antes de aplicar la combinaci´on. m´ ınimo m´ aximo media DC 0,01 8,10 2,02 NER 1,30 6,41 3,52 PAR 0,03 2,30 1,12 POS -0,58 1,75 0,75 WSD 1,70 7,00 3,34 Voting -0,58 6,20 1,53 Stacking 0,03 9,02 2,45 Otros 0,02 8,10 2,62 Cuadro 1: Resumen de los resultados de las referencias seleccionadas. 5. Conclusiones Las t´ecnicas de combinaci´on intentan aprovechar los puntos fuertes de los sistemas individuales minimizando los efectos negativos de sus puntos d´ebiles y obteniendo clasificadores m´as robustos y precisos. Si bien existen bastantes trabajos que usan algunas de estas t´ecnicas, existen t´ecnicas desarro- La Combinación de Sistemas y el PLN 73 lladas fundamentalmente en el ´area del Reconocimiento de Patrones con muy buenos resultados que apenas tienen cobertura en el PLN. Hemos mostrado los aspectos principales de las t´ecnicas m´as importantes, no sin antes recuperar los principios te´oricos en los que se sustenta esta l´ınea de investigaci´on que desde la pasada d´ecada ha ido ganando protagonismo. Como resultado del estudio aqu´ı realizado, concluimos en primer lugar que el margen de mejora depende en gran parte de la precision de los clasificadores individuales, siendo m´as dif´ıcil mejorarlos cuando parten de valores altos. Adem´as, apreciamos una mayor diversificaci´on en cuanto a los algoritmos de clasificaci´on que utilizamos habitualmente, frente a las t´ecnicas de combinaci´on, entre las que destacan claramente los algoritmos de Votaci´on y Stacking, quiz´as por el desconocimiento en lo referente a la existencia de otras muchas t´ecnicas como las expuestas en la secci´on 3. Dadas las capacidades de mejora que muestran los resultados de este estudio, creemos en la necesidad de contemplar el uso de estas t´ecnicas para la mejora de cualquier m´odulo que lleve a cabo una labor de clasificaci´on. Bibliograf´ıa Belkin, N.J. y J.P. Callan. 1993. The effect of multiple query representations on information retrieval system performance. Proceedings of the ACM SIGIR, p´aginas 339–346. Borin, L. 2000. Something borrowed, something blue: Rule-based combination of pos taggers. Proceedings of the 2nd International Conference on Language Resources and Evaluation. Brill, E. y J. Wu. 1998. Classifier combination for improved lexical disambiguation. Proceedings of the ACL Conference, p´aginas 191–195. Cuong, Le Anh. 2007. A Study of Classifier Combination and Semi-Supervised Learning for Word Sense Disambiguation. Ph.D. tesis, Japan Advanced Institute of Science and Technology. Dietterich, T. G. 2000. Ensemble methods in machine learning. Multiple Classifier Systems, LNCS, 1857:1–15. Dietterich, T.G. y G. Bakiri. 1991. Error-correcting output codes: A general method for improving multiclass inductive learning programs. In Proceedings of AAAI-91, p´aginas 572–577. Dimililer, N., E. Varoˇglu, y H. Altin¸cay. 2007. Vote-based classifier selection for biomedical ner using genetic algorithms. IbPRIA 2007, Part II, LNCS, 4478:202– 209. Florian, R. 2002. Named entity recognition as a house of cards: classifier stacking. COLING-02: proceedings of the 6th conference on Natural language learning, p´aginas 1–4. Florian, R., S. Cucerzan, C. Schafer, y D. Yarowsky. 2002. Combining classifiers for word sense disambiguation. Natural Language Engineering, 4(8):327–341. Florian, R., A. Ittycheriah, H. Jing, y T. Zhang. 2003. Named entity recognition through classifier combination. Proceedings of HLT-NAACL, p´aginas 168– 171. Frederking, R. y S.˜ Nirenburg. 1994. Three heads are better than one. In Proceedings of ANLP, p´aginas 95–100. Halteren, H.V., J. Zavrel, y W. Daelemans. 1998. Improving data driven wordclass tagging by system combination. Proceedings of the ACL Conference, 1:491–497. Hansen, L. y P. Salamon. 1990. Neural network ensembles. IEEE Transactions on Pattern Analysis and Machine Intelligence, 12(10):993–1001. Henderson, J.C. y E. Brill. 1999. Exploiting diversity in natural language processing: Combining parsers. In Joint Sigdat Conference on EMNLP and VLC (ACL), p´aginas 187–194. Ho, T.K. 1998. The random subspace method for constructing decision forests. IEEE Transactions on Pattern Analysis and Machine Intelligence, 20(8):832–844. Huang, Y. S. y C. Y. Suen. 1995. A method of combining multiple experts for the recognition of unconstrained handwritten numerals. IEEE Transactions on Pattern Analysis and Machine Intelligence, 17:90– 93. Hull, D.A., J.O. Pedersen, y H. Schutze. 1996. Method combination for document filtering. SIGIR Forum, p´aginas 279–288. Fernando Enríquez, José A. Troyano, Fermín Cruz, F. Javier Ortega 74 Jing, H., R. Florian, X. Luo, T. Zhang, y A. Ittycheriah. 2003. Howtogetachinesename(entity): segmentation and combination issues. Proceedings of EMNLP, p´aginas 200–207. Klein, D., K. Toutanova, H.T. Ilhan, S.D. Kamvar, y C.D. Manning. 2002. Combining heterogeneous classifiers for wordsense disambiguation. Proceedings of the ACL-02 workshop on Word sense disambiguation, p´aginas 74–80. Kozareva, Z., O. Ferr´andez, A. Montoyo, R. Mu˜noz, A. Su´arez, y J. G´omez. 2007. Combining data-driven systems for improving named entity recognition. Data & Knowledge Engineering, 61(3):449–466. Kuncheva, L.I., J.C. Bezdek, y R.P.W. Duin. 2001. Decision templates for multiple classifier fusion: An experimental comparison. Pattern Recognition, 34(2):299–314. Kuncheva, L.I. y C.J. Whitaker. 2003. Measures of diversity in classifier ensembles and their relationship with the ensemble accuracy. Machine Learning, 51:181–207. Kuta, M., M. Wrzeszcz, P. Chrz¸aszcz, y J. Kitowski. 2008. Accuracy of baseline and complex methods applied to morphosyntactic tagging of polish. ICCS ’08: Proceedings of the 8th international conference on Computational Science, Part I, p´aginas 903–912. Larkey, L.S. y W.B. Croft. 1996. Combining classifiers in text categorization. SIGIR Forum, p´aginas 289–297. Pal, Sankar K. 2001. Pattern recognition: from classical to modern approaches. World Scientific. Pedersen, T. 2000. A simple approach to building ensembles of naive bayesian classifiers for word sense disambiguation. Proceedings of the ACL Conference, p´aginas 63–69. Rogova, G. 1994. Combining the results of several neural network classifiers. Neural Networks, 7:777–781. Silva, C. y B. Ribeiro. 2007. Rvm ensemble for text classification. International Journal of Computational Intelligence Research, 3(1):31–35. Witten, Ian H. y Eibe Frank. 2000. Data Mining: Practical Machine Learning Tools and Techniques. Morgan Kaufmann. Wolpert, D.H. 1992. Stacked generalization. Neural Networks, 5:241–259. Wu, D., G.˜ Ngai, y M. Carpuat. 2003. A stacked, voted, stacked model for named entity recognition. Proceedings of HLTNAACL, p´aginas 200–203. Xu, L., A. Krzyzak, y C. Y. Suen. 1992. Methods of combining multiple classifiers and their application to handwriting recognition. IEEE Transactions on Systems, Man, and Cybernetics, 22:418–435. La Combinación de Sistemas y el PLN 75