Modelo de Markov de máxima entropía

Ahora volvemos a la tarea de etiquetado de secuencias e introducimos un modelo de Markov de máxima entropía que utiliza directamente un modelo log-lineal. Los modelos de Markov de máxima entropía son una alternativa útil a los modelos de Markov ocultos.

Nuestro objetivo es modelar las siguientes probabilidades condicionales.

Aquí está el primer símbolo de entrada (por ejemplo, la primera palabra de una frase) y el primer estado. Se utiliza para representar el conjunto de todos los estados, suponiendo que el conjunto es finito.

Por ejemplo, en la anotación de parte de la oración en inglés, es la colección de todas las partes de la oración en inglés (sustantivos, verbos, preposiciones, etc.). Dada una oración que contiene una palabra, hay una lista de posibles partes del discurso, donde está el número de todas las partes del discurso. Deseamos estimar la distribución de estas posibles secuencias.

En el primer paso, el modelo de Markov de máxima entropía utiliza la siguiente descomposición probabilística:

El primer signo igual es estrictamente válido, el segundo signo igual El El número debe satisfacer la condición de independencia condicional, lo que significa que es válido para todos los estados.

Nuestro supuesto es similar al supuesto de Markov en HMM, por ejemplo, el estado solo depende del estado, y el estado es independiente de otros estatus.

Bajo este supuesto de independencia, modelamos cada elemento usando un modelo log-lineal:

Aquí hay un vector de características donde:

Una vez que definimos los vectores de características , podemos entrenar los parámetros como lo haríamos con un modelo log-lineal. Las muestras de entrenamiento constan de oraciones y estados correspondientes, y una vez que hemos entrenado los parámetros, tenemos un modelo

del modelo

. La siguiente pregunta es cómo decodificar el modelo.

Decodificar el problema de decodificación del modelo de Markov de máxima entropía es el siguiente: dada una secuencia de prueba, nuestro objetivo es calcular la secuencia de estados más probable.

Hay muchos tipos de secuencias de estados. Por lo tanto, no es práctico utilizar una búsqueda de fuerza bruta en oraciones de una longitud razonable.

Afortunadamente, podemos usar el algoritmo de Viterbi: esto es muy similar a cómo usamos el algoritmo de Viterbi en los HMM. La estructura de datos básica requerida por el algoritmo es una tabla de programación dinámica que contiene entradas

donde, es la secuencia máxima posible de estados que terminan en un determinado estado en una determinada posición. Más formalmente, el algoritmo calcula

donde

El algoritmo es el siguiente:

Una comparación de los modelos de Markov de máxima entropía y los modelos de Markov ocultos que utilizan el máximo ¿Qué es? ¿Cuál es el motivo de los modelos entrópicos de Markov en lugar de los modelos ocultos de Markov? Tenga en cuenta que utilizando el proceso de decodificación de Viterbi, los dos modelos son muy similares. En un modelo de Markov de máxima entropía, la probabilidad de una transición de estado de

es

En un modelo de Markov oculto, la probabilidad de transición es

Máxima Entropía de Markov El La mayor ventaja de los modelos de Kov es que los vectores propios son más expresivos que los utilizados en los modelos ocultos de Markov. Por ejemplo, se podría asociar una probabilidad de transición con cada palabra de la oración de entrada.