Implementación del Algoritmo Viterbi para Modelos Ocultos de Markov

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

Cursos Empresas Blog Live Conf Eventos Precios

0:0017:50

Implementación del Algoritmo Viterbi para Modelos Ocultos de Markov

Curso de Algoritmos de Clasificación de Texto

Clase 12 de 26

Clase 12 / 26

Comentarios (9)9 comentarios

David Pinchao

Hace 6 años

Asi podemos sumar las probabilidades de una manera mas facil.

sum() recibe una lista como argumento

sum(initTagStateProb.values())

Francisco Garcia [C6]

Hace 6 años

Me apareciendo el siguiente error

![](

Lo corregí de la siguiente manera.

viterbiProb[tag_row, col] = max(possible_probs) if possible_probs else 0

Francisco Garcia [C6]

Hace 6 años

Pero igual es un problema, ya que posssible_probs, esta llegando vacío.

Demian Arenas

Hace 6 años

Hola garciafran, puedes compartir tu código completo?

Omar Larasa

Hace 6 años

Hola, Aquí abajo dejo un buscador para palabras en el diccionario de emisión, y que se pueda comprobar con que categorías da coincidencia y cuál es que es su índice, este lo use para guiarme en la interpretación de la matriz de Viterbi.

w = 'mundo' # palabra a buscar, solo eso hay que cambiar
# iteramos las probabilidades de emision, palabras|tags
for key in emissionProbdict.keys():
  # buscamos la palabra entre las keys del dic
  if key[:len(w)+1].lower() == f'{w}|':
    print(key, '>', tagStateDict[key.split('|')[1]], '>', emissionProbdict[key])

Increíble clase, creo que al poner directamente las formulas de probabilidad no se llega a entender tanto, pero con la aplicación en el código ya se aclaro bastante el funcionamiento del algoritmo y la interpretación de la matriz. :)

Jhon Freddy Tavera Blandon

Hace 2 años

Definir Funciones para el Algoritmo de Viterbi

El algoritmo de Viterbi se basa en una programación dinámica que toma como entrada:

La secuencia de observaciones (palabras).
La matriz de transición entre estados ocultos.
La matriz de emisión de los estados ocultos a las observaciones.

Sergio Rubiano

Hace 6 años

Muy bien explicado y entendible Pacho. :D

Francisco Garcia [C6]

Hace 6 años

El ejercicio es muy bueno

Bryan Castano

Hace 9 meses

Algoritmo de Viterbi para HMM:

La implementación del algoritmo de Viterbi es el método estándar para resolver la tarea de decodificación en un Modelo Oculto de Markov (HMM),. Su objetivo es encontrar la secuencia de estados ocultos más probable (Q) que ha generado una secuencia de observaciones (O),.

A continuación, se detalla su funcionamiento y pasos de implementación según las fuentes:

1. Estructura de Datos: La Rejilla (Trellis)

El algoritmo utiliza una técnica de programación dinámica basada en una rejilla,. Cada celda de esta rejilla, denotada como vt(j), representa la probabilidad de que el modelo se encuentre en el estado j en el tiempo t, habiendo procesado las primeras t observaciones y habiendo seguido la ruta de estados más probable hasta ese momento,.

2. Pasos de la Implementación

La ejecución formal del algoritmo se divide en tres fases principales,:

• Fase de Inicialización (t=1): Para cada estado j, se calcula el valor inicial de la celda multiplicando la probabilidad inicial del estado (πj) por la probabilidad de que ese estado genere la primera observación (bj(o1)),. Se inicializa un puntero de retroceso (backpointer) en cero para este primer paso,.

• Fase de Recursión (t de 2 a T): Para cada estado s en cada paso de tiempo, el algoritmo busca el camino más probable que llega a él desde el paso anterior,. Para calcular vt(j), se multiplican tres factores y se selecciona el máximo resultado,:

1. vt−1(i): La probabilidad de Viterbi del estado previo i.

2. aij: La probabilidad de transición del estado i al estado j.

3. bj(ot): La verosimilitud de la observación actual ot dado el estado j.

• Punteros de retroceso: Es crucial que, en cada celda, se almacene el argumento que maximiza la probabilidad (el estado previo i que resultó ganador),. Esto permite saber qué camino se eligió como el mejor para llegar a ese punto.

• Fase de Terminación: Al llegar al final de la secuencia de observaciones (T), se identifica cuál de los estados finales tiene el valor de probabilidad más alto,. Este valor representa la probabilidad de la ruta completa más probable.

3. Reconstrucción de la Secuencia (Backtrace)

A diferencia del algoritmo Forward, que solo produce un número (la probabilidad total), Viterbi debe devolver la secuencia de estados,. Para esto, se realiza un rastreo hacia atrás (backtrace) siguiendo los punteros de retroceso desde el estado final con mayor probabilidad hasta el inicio,. Este proceso reconstruye la secuencia óptima de variables ocultas,.

Diferencia Matemática Clave

La implementación de Viterbi es casi idéntica a la del algoritmo Forward, con la diferencia fundamental de que Viterbi utiliza la operación de maximización (max) en lugar de la suma (∑) para combinar las rutas previas, y añade el componente de los punteros de retroceso para la recuperación de la ruta.

Gabriel Obregón

Hace un año

🧠ALGORITMO DE VITERBI

🔍 ¿Qué es?

El algoritmo de Viterbi busca la secuencia más probable de estados ocultos dentro de un Modelo Oculto de Markov (HMM), a partir de una serie de observaciones.

⚙️ Ingredientes esenciales

🧩 1. Matrices de probabilidad

🔸 Transición: probabilidad de pasar de un estado a otro → Ejemplo: "VERB|NOUN"

🔸 Emisión: probabilidad de que un estado produzca una palabra → Ejemplo: "casa|NOUN"

🌐 2. Distribución inicial

Indica con qué probabilidad comienza la secuencia en cada estado.
Ejemplo: {"NOUN": 0.4, "VERB": 0.6}

✂️ 3. Tokenizador

Divide el texto en palabras individuales.
En Python: from nltk.tokenize import word_tokenize

🧮 Estructura de la matriz de Viterbi

📊 Filas: posibles estados (etiquetas gramaticales)

📊 Columnas: posiciones de palabras en la oración

🔢 Cada celda: probabilidad máxima de llegar a ese estado en esa posición

🧱 Etapas del cálculo

1️⃣ Inicialización: Solo la primera palabra → P(inicio) × P(emisión)

2️⃣ Recurrencia: Para cada palabra siguiente → máximo sobre todos los estados previos de P(previo) × P(transición) × P(emisión)

3️⃣ Terminación: Se elige el camino con la probabilidad total más alta

Ranlly Peguero

Hace 3 años

¿Ustedes creen que es recomendable escribir todo el codigo en un cuaderno?

Juan Baquero

Hace 2 años

Como método de aprendizaje es fenomenal. Te permite practicar y retener mejor la información. En todo caso, tienes a disposición los Notebooks con los ejercicios disponibles en los repositorios de clase y puedes consultarlos en cualquier momento. Es decir, que podrías complementar con notas en cuaderno.

Recursos

¿Qué es el algoritmo de Viterbi y cómo se implementa?

El algoritmo de Viterbi es un método probado y eficiente para encontrar la secuencia más probable de estados ocultos, dados un conjunto de observaciones y un modelo oculto de Markov. Es una herramienta esencial en el procesamiento del lenguaje natural, especialmente cuando se trata de tareas como el etiquetado gramatical. En esta clase, exploraremos cómo implementar este algoritmo paso a paso utilizando Python.

¿Cuáles son los ingredientes esenciales para crear el algoritmo de Viterbi?

Antes de implementar el algoritmo, necesitamos preparar ciertos componentes clave:

Matrices de probabilidad:
- Transición: Probabilidad de cambiar de un estado a otro.
- Emisión: Probabilidad de observar una cierta salida desde un estado específico.
Distribución inicial de estados: Esta distribución representa las probabilidades iniciales para cada estado al comienzo de la secuencia.
Tokenizador: Utilizando la biblioteca NLTK y su tokenizador de palabras word_tokenize, podemos dividir una secuencia de texto en palabras individuales. Esto es esencial para que el algoritmo procese correctamente las entradas textuales.

¿Cómo configurar la función de matriz de Viterbi en Python?

La implementación de la función comienza con la creación de la estructura de la matriz y continúa con el llenado de sus elementos:

import nltk
from nltk.tokenize import word_tokenize

def viterbi_matrix(sequence, prob_dict_trans, prob_dict_emis, tag_state_dict, init_tag_state_prov):
    # Tokenizar la secuencia
    tokens = word_tokenize(sequence.lower())

    # Crear matriz de Viterbi llena de ceros
    viterbi_pro = [[0] * len(tokens) for _ in range(len(tag_state_dict))]

    # Inicializar la primera columna
    for key in tag_state_dict.keys():
        tag_row = tag_state_dict[key]
        word_tag = f"{tokens[0]}|{key}"
        
        if word_tag in prob_dict_emis:
            viterbi_pro[tag_row][0] = init_tag_state_prov[key] * prob_dict_emis[word_tag]
    
    # Calcular probabilidades para siguientes columnas
    for col in range(1, len(tokens)):
        for key in tag_state_dict.keys():
            tag_row = tag_state_dict[key]
            word_tag = f"{tokens[col]}|{key}"
            
            if word_tag in prob_dict_emis:
                possible_props = []
                for key2 in tag_state_dict.keys():
                    tag_row2 = tag_state_dict[key2]
                    tag_pre_tag = f"{key2}|{key}"
                    
                    if tag_pre_tag in prob_dict_trans:
                        previous_prob = viterbi_pro[tag_row2][col - 1]
                        if previous_prob > 0:
                            possible_props.append(previous_prob * prob_dict_trans[tag_pre_tag] * prob_dict_emis[word_tag])
                
                viterbi_pro[tag_row][col] = max(possible_props, default=0)  # Valor por defecto para evitar errores
    
    return viterbi_pro

# Ejemplo de uso
sequence = "El mundo es pequeño"
viterbi_matrix = viterbi_matrix(sequence, prob_dict_trans, prob_dict_emis, tag_state_dict, init_tag_state_prov)

Esta función procesa una secuencia de palabras y devuelve una matriz de Viterbi completa con las probabilidades más relevantes para cada etiqueta gramatical y posición de palabra.

¿Cómo continuar con el desarrollo del algoritmo de Viterbi?

Una vez establecida la matriz inicial, podemos proceder a:

Completar el cálculo de las probabilidades de las siguientes columnas basándonos en las transiciones previas.
Verificar y ajustar dónde se encuentran los valores más altos para determinar la secuencia de etiquetas más probable.
Identificar cualquier otro componente o herramienta en librerías como NLTK que puedan optimizar o simplificar el proceso.

A través de este proceso, hemos logrado una comprensión más profunda de cómo implementar un modelo basado en Markov oculto en Python de manera intuitiva, conectando la teoría matemática con el código. Esto no solo nos proporciona una base sólida para construir modelos de procesamiento del lenguaje natural, sino que también nos prepara para adaptarnos a prácticas de desarrollo más avanzadas en el futuro.

¡Continúa explorando y desarrollando tus habilidades en algoritmos y modelos de lenguaje natural! Cada paso que tomes te acercará más a convertirte en un experto en el campo.

w = 'mundo' # palabra a buscar, solo eso hay que cambiar
# iteramos las probabilidades de emision, palabras|tags
for key in emissionProbdict.keys():
  # buscamos la palabra entre las keys del dic
  if key[:len(w)+1].lower() == f'{w}|':
    print(key, '>', tagStateDict[key.split('|')[1]], '>', emissionProbdict[key])

Resumen

¿Qué es el algoritmo de Viterbi y cómo se implementa?

¿Cuáles son los ingredientes esenciales para crear el algoritmo de Viterbi?

Antes de implementar el algoritmo, necesitamos preparar ciertos componentes clave:

Matrices de probabilidad:
- Transición: Probabilidad de cambiar de un estado a otro.
- Emisión: Probabilidad de observar una cierta salida desde un estado específico.
Distribución inicial de estados: Esta distribución representa las probabilidades iniciales para cada estado al comienzo de la secuencia.
Tokenizador: Utilizando la biblioteca NLTK y su tokenizador de palabras word_tokenize, podemos dividir una secuencia de texto en palabras individuales. Esto es esencial para que el algoritmo procese correctamente las entradas textuales.

¿Cómo configurar la función de matriz de Viterbi en Python?

La implementación de la función comienza con la creación de la estructura de la matriz y continúa con el llenado de sus elementos:

import nltk
from nltk.tokenize import word_tokenize

def viterbi_matrix(sequence, prob_dict_trans, prob_dict_emis, tag_state_dict, init_tag_state_prov):
    # Tokenizar la secuencia
    tokens = word_tokenize(sequence.lower())

    # Crear matriz de Viterbi llena de ceros
    viterbi_pro = [[0] * len(tokens) for _ in range(len(tag_state_dict))]

    # Inicializar la primera columna
    for key in tag_state_dict.keys():
        tag_row = tag_state_dict[key]
        word_tag = f"{tokens[0]}|{key}"
        
        if word_tag in prob_dict_emis:
            viterbi_pro[tag_row][0] = init_tag_state_prov[key] * prob_dict_emis[word_tag]
    
    # Calcular probabilidades para siguientes columnas
    for col in range(1, len(tokens)):
        for key in tag_state_dict.keys():
            tag_row = tag_state_dict[key]
            word_tag = f"{tokens[col]}|{key}"
            
            if word_tag in prob_dict_emis:
                possible_props = []
                for key2 in tag_state_dict.keys():
                    tag_row2 = tag_state_dict[key2]
                    tag_pre_tag = f"{key2}|{key}"
                    
                    if tag_pre_tag in prob_dict_trans:
                        previous_prob = viterbi_pro[tag_row2][col - 1]
                        if previous_prob > 0:
                            possible_props.append(previous_prob * prob_dict_trans[tag_pre_tag] * prob_dict_emis[word_tag])
                
                viterbi_pro[tag_row][col] = max(possible_props, default=0)  # Valor por defecto para evitar errores
    
    return viterbi_pro

# Ejemplo de uso
sequence = "El mundo es pequeño"
viterbi_matrix = viterbi_matrix(sequence, prob_dict_trans, prob_dict_emis, tag_state_dict, init_tag_state_prov)

Esta función procesa una secuencia de palabras y devuelve una matriz de Viterbi completa con las probabilidades más relevantes para cada etiqueta gramatical y posición de palabra.

¿Cómo continuar con el desarrollo del algoritmo de Viterbi?

Una vez establecida la matriz inicial, podemos proceder a:

Completar el cálculo de las probabilidades de las siguientes columnas basándonos en las transiciones previas.
Verificar y ajustar dónde se encuentran los valores más altos para determinar la secuencia de etiquetas más probable.
Identificar cualquier otro componente o herramienta en librerías como NLTK que puedan optimizar o simplificar el proceso.

¡Continúa explorando y desarrollando tus habilidades en algoritmos y modelos de lenguaje natural! Cada paso que tomes te acercará más a convertirte en un experto en el campo.

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

Decodificación de Secuencias con el Algoritmo de Viterbi

Cálculo de Probabilidades en el Algoritmo de Viterbi

Implementación del Algoritmo de Viterbi en Python con NumPy

Implementación del Algoritmo Viterbi para Modelos Ocultos de Markov

Implementación de Modelos Ocultos de Markov en NLTK y Python

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

Modelos Marcovianos de Máxima Entropía en Clasificación de Etiquetas

Algoritmo BiTerbi en Modelos de Máxima Entropía

Entrenamiento y Decodificación de Modelos Marcobianos en Bitterbi

Clasificación de texto con NLTK

Clasificación de Texto en Machine Learning: Teorías y Aplicaciones

Clasificación de Nombres por Género con NLTK en Python

Clasificación de Nombres con Naive Bayes en Python

Clasificación de correos: Filtrado de spam con Naive Bayes

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

Funcionamiento Matemático del Clasificador Naive Bayes

Preparación de Datos para Modelo Naive Bayes en Python

Implementación del Algoritmo Naive Bayes en Python con spaCy

Implementación del Método Predict en Naive Bayes Clasificador

Métricas de Evaluación en Modelos de Clasificación: Accuracy, Precision y Recall

Clasificación de Sentimientos con Reviews de Amazon

Implementación del Algoritmo Viterbi para Modelos Ocultos de Markov