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 ocultos de Markov (HMM) y los modelos de máxima entropía (MaxEnt). Un MEMM es un modelo discriminativo que extiende un clasificador estándar de máxima entropía al asumir 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 habla ^{[ 1 ]} y la extracción de información ^{[ 2 ]} .

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

${\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.${\displaystyle P(s\mid s',o)}$. Para cada posible valor de etiqueta de la etiqueta anterior${\displaystyle s'}$, la probabilidad de una etiqueta determinada${\displaystyle s}$se modela de la misma manera que un clasificador de entropía máxima : ^{[ 3 ]}

${\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í, el${\displaystyle f_{a}(o,s)}$son funciones de características de valor real o categóricas, y${\displaystyle Z(o,s')}$es un término de normalización que asegura que la distribución sume uno. Esta forma para la distribución corresponde a la distribución de probabilidad de máxima entropía que satisface la restricción de que la esperanza empírica para la característica sea igual a la esperanza dado el modelo:

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

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

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

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

Una ventaja de los MEMM sobre los HMM para el etiquetado de secuencias es que ofrecen mayor libertad en la elección de características para representar las observaciones. En situaciones de etiquetado de secuencias, es útil utilizar el conocimiento del dominio para diseñar características de propósito especial. En el artículo original que introduce los MEMM, los autores escriben que "al intentar extraer nombres de empresas previamente no vistos de un artículo de agencia 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 usa en una aposición y que aparece cerca del principio del artículo sería bastante predictivo (junto con el contexto proporcionado por la estructura de transición de estado)". ^{[ 2 ]} Las características útiles para el etiquetado de secuencias, como estas, a menudo no son independientes. Los modelos de entropía máxima no asumen independencia entre características, pero los modelos de observación generativos utilizados en los HMM sí. ^{[ 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 bucle interno en el entrenamiento . 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 puede realizarse de forma aislada para cada distribución de transición.

Una desventaja de los MEMM es que potencialmente sufren del "problema del sesgo de etiquetas", 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 etiquetas es que el entrenamiento siempre se realiza con respecto a etiquetas previas conocidas, por lo que el modelo tiene dificultades en el momento de la prueba cuando hay incertidumbre en la etiqueta previa.