Как работает алгоритм Viterbi?

Алгоритм Витерби — это динамический программный метод для поиска наиболее вероятной последовательности скрытых состояний в модели скрытой марковской модели (HMM), которая могла бы породить наблюдаемые данные.

Основная идея:

• Для каждого момента времени алгоритм вычисляет наиболее вероятный путь, ведущий к каждому состоянию.
• Использует рекуррентные вычисления, чтобы избежать перебора всех возможных путей.

Применение — распознавание речи, биоинформатика, обработка естественного языка.

Кратко:

1. Инициализация вероятностей для начальных состояний.
2. Для каждого следующего наблюдения вычисляется максимальная вероятность перехода из предыдущих состояний с учетом вероятности наблюдения.
3. Запоминается путь, который дал максимальную вероятность.
4. По окончании выбирается путь с максимальной общей вероятностью.

Пример псевдокода:

for state in states:
    V[0][state] = start_prob[state] * emit_prob[state][obs[0]]

for t in range(1, len(obs)):
    for state in states:
        V[t][state], path[state] = max(
            (V[t-1][prev_state] * trans_prob[prev_state][state] * emit_prob[state][obs[t]], prev_state)
            for prev_state in states
        )

# Выбираем конечное состояние с максимальной вероятностью
max_prob, last_state = max((V[len(obs)-1][state], state) for state in states)

# Восстанавливаем путь
best_path = []
while last_state:
    best_path.append(last_state)
    last_state = path[last_state]
best_path.reverse()