Decodificación de Secuencias con el Algoritmo de Viterbi

Clase 9 de 26 • Curso de Algoritmos de Clasificación de Texto

Contenido del curso

Desambiguación y etiquetado de palabras

Modelos Markovianos Latentes (HMM)

Algoritmo de Viterbi

Modelos Markovianos de máxima entropía (MEMM)

Clasificación de texto con NLTK

Implementación de un modelo de clasificación de texto

Tomar examen

Resumen

¿Qué son las predicciones del modelo marcobiano latente?

Los modelos marcobianos latentes son herramientas poderosas en el análisis del lenguaje. No solo nos permiten entrenar modelos con probabilidades de transición y emisión, sino que también nos ayudan a realizar predicciones precisas sobre secuencias de etiquetas gramaticales. El proceso clave para lograr esto es conocido como decodificación, que consiste en identificar la secuencia de etiquetas gramaticales más probable para una serie de palabras dadas. Para ello, utilizamos un algoritmo llamado Viterbi. Nos centraremos en entender cómo funciona este algoritmo para facilitar su aprendizaje y aplicación en otros métodos de decodificación.

¿Cómo se construye el proceso de decodificación?

La decodificación es la segunda fase del uso de modelos marcobianos latentes, tras el entrenamiento. Consiste en los siguientes pasos:

Calculo de matrices y probabilidades iniciales:
- Primero, se calcula la matriz de transición con coeficientes 'c'.
- Luego, se determinan las probabilidades de emisión 'b', que describen la probabilidad condicional de una etiqueta dada una palabra.
Aplicación del algoritmo de Viterbi:
- Este algoritmo asigna una probabilidad a cada posible secuencia de etiquetas para las palabras de entrada.
- Se exploran distintas combinaciones de etiquetas conectando posibles decisiones en cada palabra de la secuencia.
- Se evalúa cada camino desde la primera hasta la última palabra, seleccionando finalmente el que tiene la mayor probabilidad asignada.
Retorno de la mejor secuencia:
- De entre todas las secuencias posibles, se selecciona y retorna la más probable como la secuencia de etiquetas correctas.

¿Cómo funciona el algoritmo de Viterbi?

Vamos a detallar el funcionamiento de este algoritmo con el fin de entender cómo encuentra la secuencia más plausible.

Preparación de la matriz de nodos y cálculo inicial

Primero, tomamos una oración como "Castillo el noble trabajador" y generamos matrices de nodos donde cada columna representa una palabra, y cada fila sus posibles etiquetas gramaticales. Aquí cada nodo representa una posibilidad y comenzamos calculando la probabilidad inicial para cada nodo de la primera palabra. Por ejemplo:

# Probabilidad inicial para sustantivo propio (prop) de 'Castillo'
nu_1_prop = P_inicial(prop) * P_condicional(Castillo | prop)

Cálculo recursivo de probabilidades

Para las siguientes palabras, calculamos la probabilidad en cada nodo considerando las probabilidades de los nodos anteriores. Tomamos como ejemplo el nodo para la palabra "el":

# Ejemplo de cálculo de probabilidad para el nodo "el"
nu_2_det = max(
    nu_1_prop * P_transicion(det | prop) * P_emision(el | det),
    nu_1_non * P_transicion(det | non) * P_emision(el | det)
)

Aquí, calculamos la probabilidad desde dos caminos posibles: pasando desde un sustantivo propio o desde un sustantivo no propio ('non'), y escogemos la mayor.

Finalización del proceso

Repetimos este proceso para cada palabra y cada posible etiqueta en la secuencia. Una vez calculadas todas las probabilidades, seleccionamos la secuencia con la probabilidad más alta como la secuencia de etiquetas correctas.

Factores clave para el éxito del algoritmo Viterbi

Precisión de probabilidades iniciales y condicionales: La exactitud de las probabilidades marcobianas es crucial para la fidelidad del modelo.
Eficiencia computacional: Viterbi es conocido por su eficiencia en reducir el número de caminos calculados al descartar caminos menos probables en cada paso.
Adaptabilidad: Una vez entendido, el algoritmo de Viterbi puede aplicarse fácilmente a diversos problemas de procesamiento de lenguaje natural.

Con el enfoque correcto y la comprensión adecuada del algoritmo, la decodificación de secuencias complejas se convierte en una tarea alcanzable y eficiente. Continúa explorando este fascinante mundo de la lingüística computacional donde cada palabra cuenta una historia matemática.

Bryan Castano

student•

Un modelo oculto de Markov (HMM) se especifica formalmente mediante los siguientes componentes, los cuales permiten relacionar una secuencia de eventos observados con eventos "ocultos" que se consideran factores causales:

• Un conjunto de estados (Q): Consiste en N estados individuales, representados como q1,q2,…,qN.

• Una matriz de probabilidades de transición (A): Cada valor aij representa la probabilidad de pasar de un estado i a un estado j. Esta matriz debe cumplir que, para cualquier estado, la suma de las probabilidades de todas las transiciones que salen de él sea igual a 1.

• Probabilidades de emisión o verosimilitudes de observación (B): Se define como una secuencia de probabilidades bi(ot), donde cada una expresa la probabilidad de que se genere una observación específica (ot) desde un estado determinado (qi).

• Una distribución de probabilidad inicial (π): Es un conjunto de probabilidades π=π1,π2,…,πN, donde cada πi indica la probabilidad de que el modelo comience en el estado i. Al igual que con las transiciones, la suma de estas probabilidades iniciales debe ser 1.

• Un vocabulario de observaciones (V): Es el conjunto de todos los símbolos o eventos posibles que pueden ser observados, denotados como v1,v2,…,vV.

Además de estos componentes estructurales, el modelo opera bajo dos supuestos simplificadores fundamentales:

1. Supuesto de Markov: La probabilidad de un estado particular depende únicamente del estado inmediatamente anterior.

2. Independencia de salida: La probabilidad de que aparezca una observación determinada (oi) depende exclusivamente del estado que la produjo (qi) y no de otros estados u observaciones previas.

En la práctica, el modelo recibe como entrada una secuencia de observaciones (O) de longitud T, donde cada elemento pertenece al vocabulario V, con el fin de inferir la secuencia de estados ocultos más probable que la general.

Las diferencias fundamentales entre los procesos de Markov (específicamente las cadenas de Markov) y los modelos ocultos de Markov (HMM) se centran en la visibilidad de los estados, los componentes del modelo y la forma en que se calculan las probabilidades:

• Visibilidad de los estados: En una cadena de Markov, los eventos o estados que nos interesan son directamente observables. Es decir, las observaciones superficiales son las mismas que los estados. Por el contrario, en un HMM, los eventos de interés son "ocultos" y no se pueden observar directamente; en su lugar, observamos una secuencia de eventos diferentes que resultan de esos estados ocultos y debemos inferirlos.

• Componentes adicionales del modelo: Un HMM se basa en el aumento de una cadena de Markov. Mientras que una cadena de Markov se define por un conjunto de estados (Q), una matriz de probabilidades de transición (A) y una distribución de probabilidad inicial (π), un HMM añade un componente crucial: una secuencia de probabilidades de emisión o verosimilitudes de observación (B). Estas probabilidades (B) expresan la probabilidad de que se genere una observación específica desde un estado oculto determinado.

• Complejidad en el cálculo de probabilidades: En una cadena de Markov, la probabilidad de una secuencia se calcula simplemente multiplicando las probabilidades de las transiciones entre los estados observados. En un HMM, el proceso es más complejo porque no se conoce la secuencia de estados ocultos; para determinar la probabilidad de una secuencia de observaciones, es necesario sumar las probabilidades de todas las posibles secuencias de estados ocultos que podrían haberla generado, lo cual se resuelve eficientemente mediante el algoritmo Forward.

• Relación causal: Los HMM permiten modelar tanto eventos observados como eventos ocultos, tratando a estos últimos como factores causales en el modelo probabilístico. Por ejemplo, en el etiquetado de partes del discurso, las palabras son observadas, pero las etiquetas (los estados ocultos) son los factores causales que el modelo busca descubrir.

En resumen, mientras que las cadenas de Markov son útiles para calcular probabilidades de secuencias de eventos que podemos ver, los HMM son herramientas diseñadas para situaciones donde los procesos subyacentes más importantes no son directamente accesibles.

Decodificación de Secuencias con el Algoritmo de Viterbi

Desambiguación y etiquetado de palabras

Clasificación de Texto con Machine Learning

Etiquetado de Palabras en Python con NLTK y Stanza

Uso de Stanza para Procesamiento de Lenguaje Natural en Español

Modelos Markovianos Latentes (HMM)

Modelos Marcovianos Latentes en PLN: Fundamentos y Aplicaciones

Matemáticas de Cadenas de Markov y su Aplicación en Modelos Latentes

Modelos Marcovianos Latentes: Etiquetado Gramatical Automático

Implementación de Modelos Marcovianos Latentes en Python con Google Colab

Entrenamiento de Modelos Marcobianos Latentes en Python

Algoritmo de Viterbi