NER, Métodos supervisados I: cadenas de Markov y máxima entropía
En el artículo Reconocimiento de entidades nombradas: Una breve introducción se abarcó la definición de NER, su trascendencia y evolución. De igual forma se mencionaron algunos casos de uso, aplicaciones y problemas al momento de implementarlo. Se listaron los enfoques más relevantes siendo cuatro los más importantes: aprendizaje supervisado, no supervisado, basado en reglas y aprendizaje profundo. A continuación se abordarán dos métodos principales (modelos ocultos de Markov y modelos basados en máxima entropía), así como los sistemas desarrollados basándose en cada modelo.
Los métodos supervisados son aquellos algoritmos en los que un modelo es aprendido a través de un conjunto de datos de entrenamiento previamente etiquetados. Por lo general, los métodos supervisados aprenden reglas de desambiguación basadas en características discriminatorias o intentan aprender el parámetro de la distribución hipotética que maximiza la probabilidad de datos de entrenamiento.
Entre los algoritmos de aprendizaje supervisado usados para el reconocimiento de entidades nombradas se encuentran, el modelo oculto de Markov (HMM), modelos de máxima entropía (ME), máquinas de soporte vectorial (SVM) y campos aleatorios condicionales (CRF).
Modelo oculto de Markov
De los métodos de aprendizaje supervisado mencionados con anterioridad, el modelo oculto de Markov es el más reciente aplicado para la resolución del problema de reconocimiento de entidades nombradas. En 1999 Bikel introdujo un sistema llamado IdentiFinder para la detección del NER.
De a cuerdo a la formulación de Bikel del problema en el sistema IdentiFinder, solo una etiqueta puede ser asignada a una palabra en el contexto. Por lo que el modelo asigna a cada palabra una de las clases deseadas o la etiqueta NOT-A-NAME para la representación de ninguna de las clases deseadas. Para realizar el tag de una oración, la principal tarea es encontrar la secuencia de clase nombre (NC) más probable dado una secuencia de palabras (W):
El modelo oculto de Markov es un modelo generativo: trata de generar los datos, secuencias de palabras W y etiquetas NC a partir de una distribución de parámetros:
El algoritmo Viterbi Forney (1973) es usado para maximizar la probabilidad (W,NC) a través del espacio entero de todas las asignaciones posibles de clase-nombre. En el artículo de Bikel, la generación es modelada en tres pasos:
- Se selecciona una clase-nombre condicionada a previas clases-nombre y palabras previas.
- Se genera la primera palabra dentro de la clase-nombre condicionando en la actual y las clases-nombre previas
- Generar todas las palabras subsecuentes dentro de la clase-nombre actual, donde cada palabra subsecuente es condicionada por su predecesor inmediato.
También hay un marcador de finalización distinto “+end+”, de modo que se puede calcular la probabilidad de que cualquier palabra actual sea la última palabra de su clase nombre.
IdentiFinder reporta una exactitud de NE de 94.9% y 90 % para un caso mezclado de Inglés (datos de MUC-6 y una colección de documentos del diario de Wall Street) y un caso mezclado de Español (datos MET-1 y artículos de nuevas agencias AFP) respectivamente.
Para el 2002 Zhou y Su se encargaron de modificar el modelo IdentiFinder usando información mutua, esto es, dado una secuencia de tokens :
El objetivo del algoritmo de aprendizaje es encontrar una secuencia de etiquetas estocásticas óptimas :
Que maximice la siguiente probabilidad :
A diferencia de IdentiFinder, el modelo de Zhou y Su genera directamente etiquetas NE originales a partir de las palabras de salida del canal ruidoso. Dicho modelo asume independencia de información mutua, mientras que el modelo oculto de Markov asume independencia de probabilidad condicional.
Ejemplo de utilización
Existen tres problemas principales asociados con el modelo oculto de Markov:
- Calcular la probabilidad de una secuencia de salida en particular.
- Encontrar la secuencia más probable de estados ocultos que puedan generar una secuencia de salida dada.
- Dada una secuencia de salida o un conjunto de tales secuencias, encontrar el conjunto de estados de transición y probabilidades de salida más probables. Es decir, entrenar los parámetros del modelo dada una secuencia de datos.
A partir de las siguientes 3 oraciones, “Bill Gates nos habla sobre teorías conspiranoicas”, “Los contagios en Francia vuelven a subir” y “La meta de Tesla y Elon Musk: fabricar 50 veces más autos”.
El etiquetado del texto queda de la siguiente forma:
- Bill Gates/PER nos/OTR habla/OTR sobre/OTR teorías/OTR conspiranoicas/OTR
- Los/OTR contagios/OTR en/OTR Francia/UBI vuelven/OTR a/OTR subir/OTR
- La/OTR meta/OTR de/OTR Tesla/ORG y Elon Musk/PER :/OTR fabricar/OTR 50/NUM veces/OTR más/OTR autos/OTR
Los estados fueron obtenidos como el conjunto sin repetir de las etiquetas en las 3 oraciones:
Estados = {PERSONA, OTROS, NUMERO, ORGANIZACION, UBICACION}
La probabilidad inicial es expresada de la siguiente forma:
prob_inicial =
La probabilidad de transición se compone de la siguiente manera:
prob_transicion =
Mientras que la probabilidad de emisión es la siguiente:
Calculando la probabilidad de emisión para las palabras de la primera oración se tiene.
prob_emision =
La prob_inicial representa la probabilidad de que la oración inicie con una etiqueta en particular.
La prob_transicion representa la probabilidad de que ocurra una etiqueta A seguido de una etiqueta B.
La prob_emision representa la probabilidad de que una palabra tenga asignada una etiqueta particular en un corpus o documento.
Modelo basado en entropía máxima
El modelo de entropía máxima a diferencia del modelo oculto de Markov, es un modelo discriminativo. Dado un conjunto de características y datos de entrenamiento, el modelo aprende directamente los pesos para características discriminatorias para clasificación. En los modelos de entropía máxima, el objetivo es maximizar la entropía de los datos para generalizar lo más posible los datos de entrenamiento. En los modelos de entropía máxima cada característica es asociada con un parámetro λᵢ. Donde la probabilidad condicional se obtiene de la siguiente manera:
Maximizando la entropía se asegura que para cada característica gᵢ el valor esperado de gᵢ será igual a la expectativa empírica de gᵢ en el cuerpo de entrenamiento. Finalmente, el algoritmo de Viterbi es usado para encontrar la ruta de probabilidad más alta a través del enrejado de probabilidades condicionales que produce las secuencias de etiquetas válidas requeridas.
Entre los sistemas basados en este modelo podemos encontrar el sistema MENE y el etiquetador ME de Curran.
El sistema MENE fue desarrollado por Borthwick en 1999, usa un conjunto extraordinariamente diverso de fuentes de conocimiento para tomar sus decisiones de etiquetado, una amplia gama de diccionarios geográficos y diccionarios de términos de una o varias palabras como nombre, nombre de la empresa, sufijos corporativos. Al igual una amplia variedad de características como las binarias, léxicas, de sección, salida de sistemas externos, consistencia y resolución de referencia. Las 29 etiquetas de MUC-7 forman el espacio de futuros para la formulación de entropía máxima de detección de NE. Una solución de entropía máxima para esto permite el cálculo de p( f|h) para cualquier f desde el espacio de futuros posibles, F, por cada h desde el espacio de historias posibles, H. Una historia de todos los datos condicionales que ayudan al modelo de máxima entropía para tomar decisiones sobre el futuro posible. La precisión reportada para el sistema MENE en los datos de las conferencias MUC-7 es de 88.80%.
El etiquetador ME de Curran fue implementado por Curran y Clark en 2003 aplicando el modelo de entropía máxima al problema de entidades nombradas. Usaron el enfoque softmax para formular la probabilidad P(y|x) . El etiquetador usa el modelo de la forma:
En donde y es la etiqueta, x es el contexto y fᵢ( x, y ) es la característica con su peso asociado λᵢ . Por lo tanto la probabilidad general para la secuencia completa de y₁ · · · yₙ y la secuencia de palabras w₁ · · · wₙ es aproximada como:
En donde xᵢ es un vector de contexto para cada palabra wᵢ . El etiquetador usa beamer search para encontrar la secuencia más probable dada la sentencia. Curran reportó precisiones de 84.89% para los datos de prueba en inglés y 68.48% para los datos de prueba en alemán CoNLL-2003.
Conclusiones
En la entrega de este artículo se abordaron dos métodos reconocidos del aprendizaje supervisado, como son cadenas ocultas de Markov y entropía máxima y para cada uno se explicaron los sistemas enfocados en el reconocimiento de entidades nombradas así como los resultados de precisión registrados en cada lenguaje probado. Para el siguiente artículo se expondrán los algoritmos de campos condicionales aleatorios y máquina de soporte vectorial con sus respectivos sistemas desarrollados para la detección y reconocimiento de entidades nombradas.
