Modelo de Markov de máxima entropía

En estadística , un modelo de Markov de máxima entropía ( MEMM ), o modelo de Markov condicional ( CMM ), es un modelo gráfico para el etiquetado de secuencias que combina características de los modelos de Markov ocultos (HMM) y los modelos de máxima entropía (MaxEnt). Un MEMM es un modelo discriminativo que extiende un clasificador de máxima entropía estándar al suponer que los valores desconocidos que se van a aprender están conectados en una cadena de Markov en lugar de ser condicionalmente independientes entre sí. Los MEMM encuentran aplicaciones en el procesamiento del lenguaje natural , específicamente en el etiquetado de partes del discurso ^[1] y la extracción de información . ^[2]

Modelo

Supongamos que tenemos una secuencia de observaciones que buscamos etiquetar con las etiquetas que maximizan la probabilidad condicional . En un MEMM, esta probabilidad se incluye en las probabilidades de transición de Markov, donde la probabilidad de transición a una etiqueta particular depende solo de la observación en esa posición y la etiqueta de la posición anterior ^{[ cita requerida ]} : ${\displaystyle O_{1},\dots ,O_{n}}$ ${\displaystyle S_{1},\dots ,S_{n}}$ ${\displaystyle P(S_{1},\dots ,S_{n}\mid O_{1},\dots ,O_{n})}$

${\displaystyle P(S_{1},\dots ,S_{n}\mid O_{1},\dots ,O_{n})=\prod _{t=1}^{n}P(S_{t}\mid S_{t-1},O_{t}).}$

Cada una de estas probabilidades de transición proviene de la misma distribución general . Para cada valor de etiqueta posible de la etiqueta anterior , la probabilidad de una determinada etiqueta se modela de la misma manera que un clasificador de entropía máxima : ^[3] ${\displaystyle P(s\mid s',o)}$ ${\displaystyle s'}$ ${\displaystyle s}$

${\displaystyle P(s\mid s',o)=P_{s'}(s\mid o)={\frac {1}{Z(o,s')}}\exp \left(\sum _{a}\lambda _{a}f_{a}(o,s)\right).}$

Aquí, son funciones de características categóricas o de valor real, y es un término de normalización que garantiza que la distribución sume uno. Esta forma de distribución corresponde a la distribución de probabilidad de entropía máxima que satisface la restricción de que la expectativa empírica para la característica es igual a la expectativa dada en el modelo: ${\displaystyle f_{a}(o,s)}$ ${\displaystyle Z(o,s')}$

${\displaystyle \operatorname {E} _{e}\left[f_{a}(o,s)\right]=\operatorname {E} _{p}\left[f_{a}(o,s)\right]\quad {\text{ for all }}a.}$

Los parámetros se pueden estimar utilizando escalamiento iterativo generalizado . ^[4] Además, se puede utilizar una variante del algoritmo Baum–Welch , que se utiliza para entrenar HMM, para estimar parámetros cuando los datos de entrenamiento tienen etiquetas incompletas o faltantes . ^[2] ${\displaystyle \lambda _{a}}$

La secuencia de estados óptima se puede encontrar utilizando un algoritmo de Viterbi muy similar al que se utiliza para los HMM. El programa dinámico utiliza la probabilidad hacia adelante: ${\displaystyle S_{1},\dots ,S_{n}}$

${\displaystyle \alpha _{t+1}(s)=\sum _{s'\in S}\alpha _{t}(s')P_{s'}(s\mid o_{t+1}).}$

Fortalezas y debilidades

Una ventaja de los MEMM en comparación con los HMM para el etiquetado de secuencias es que ofrecen una mayor libertad a la hora de elegir las características que representan las observaciones. En situaciones de etiquetado de secuencias, resulta útil utilizar el conocimiento del dominio para diseñar características con un propósito específico. En el artículo original que presenta los MEMM, los autores escriben que "al intentar extraer nombres de empresas nunca antes vistos de un artículo de noticias, la identidad de una palabra por sí sola no es muy predictiva; sin embargo, saber que la palabra está en mayúscula, que es un sustantivo, que se utiliza en un apositivo y que aparece cerca de la parte superior del artículo sería bastante predictivo (en conjunción con el contexto proporcionado por la estructura de transición de estado)". ^[2] Las características útiles de etiquetado de secuencias, como estas, a menudo no son independientes. Los modelos de máxima entropía no suponen independencia entre características, pero los modelos de observación generativos utilizados en los HMM sí lo hacen. ^[2] Por lo tanto, los MEMM permiten al usuario especificar muchas características correlacionadas, pero informativas.

Otra ventaja de los MEMM frente a los HMM y los campos aleatorios condicionales (CRF) es que el entrenamiento puede ser considerablemente más eficiente. En los HMM y los CRF, es necesario utilizar alguna versión del algoritmo de avance-retroceso como un bucle interno en el entrenamiento ^{[ cita requerida ]} . Sin embargo, en los MEMM, la estimación de los parámetros de las distribuciones de máxima entropía utilizadas para las probabilidades de transición se puede realizar para cada distribución de transición de forma aislada.

Una desventaja de los MEMM es que potencialmente sufren del "problema del sesgo de etiqueta", donde los estados con distribuciones de transición de baja entropía "ignoran efectivamente sus observaciones". Los campos aleatorios condicionales fueron diseñados para superar esta debilidad, ^[5] que ya había sido reconocida en el contexto de los modelos de Markov basados ​​en redes neuronales a principios de la década de 1990. ^{[5] [6]} Otra fuente de sesgo de etiqueta es que el entrenamiento siempre se realiza con respecto a etiquetas anteriores conocidas, por lo que el modelo tiene dificultades en el momento de la prueba cuando hay incertidumbre en la etiqueta anterior.

Referencias

1. Toutanova, Kristina; Manning, Christopher D. (2000). "Enriquecimiento de las fuentes de conocimiento utilizadas en un etiquetador de categorías gramaticales de máxima entropía". Proc. J. SIGDAT Conf. on Empirical Methods in NLP and Very Large Corpora (EMNLP/VLC-2000) . págs. 63–70.
2. McCallum, Andrew; Freitag, Dayne; Pereira, Fernando (2000). "Modelos de Markov de máxima entropía para la extracción y segmentación de información" (PDF) . Proc. ICML 2000. págs. 591–598.
3. Berger, AL y Pietra, VJD y Pietra, SAD (1996). "Un enfoque de máxima entropía para el procesamiento del lenguaje natural". Computational Linguistics . 22 (1). MIT Press: 39–71.{{cite journal}}: CS1 maint: multiple names: authors list (link)
4. Darroch, JN y Ratcliff, D. (1972). "Escalamiento iterativo generalizado para modelos log-lineales". Anales de estadística matemática . 43 (5). Instituto de estadística matemática: 1470–1480. doi : 10.1214/aoms/1177692379 .
5. Lafferty, John; McCallum, Andrew; Pereira, Fernando (2001). "Campos aleatorios condicionales: modelos probabilísticos para segmentar y etiquetar datos de secuencias". Proc. ICML 2001 .
6. León Bottou (1991). Une Approche théorique de l'Apprentissage Connexionniste: Aplicaciones al reconocimiento de la libertad condicional (Ph.D.). Universidad de París XI.