03.07.2024 07:17
badcasedaily1 0 540 Источник

Привет, Хабр!

Алгоритм был предложен Эндрю Витерби в 1967 году для декодирования сигналов с кодировкой, используемой в системах связи.

Алгоритм Витерби предназначен для поиска наиболее вероятной последовательности скрытых состояний в моделях с наблюдаемыми переменными, таких как скрытые марковские модели. Основное применение заключается в декодировании, где нужно определить скрытую последовательность состояний, вызвавших наблюдаемую последовательность событий.

Основные концепции алгоритма:

  • Начальные вероятности: определяют, с какой вероятностью процесс начинается в каждом возможном состоянии. В контексте скрытых марковских моделей, начальные вероятности (или начальные распределения) дают нам понимание того, каковы шансы нахождения системы в каждом из возможных начальных состояний. Например, если есть три возможных состояния S1, S2 и S3, начальные вероятности могут быть представлены как , P(S2) и P(S3), где сумма всех вероятностей равна 1.

  • Матрица переходов: матрица, в которой каждая ячейка a_{ij} представляет собой вероятность перехода из состояния S_i в состояние S_j. Матрица переходов отображает динамику системы, показывая, как вероятности изменения состояний зависят от текущего состояния. В скрытых марковских моделей если система находится в состоянии S_i в момент времени t , то a_{ij} показывает вероятность перехода в состояние S_j в момент времени t+1.

  • Матрица эмиссий: матрица определяет вероятность наблюдения каждого возможного события в каждом состоянии. Эмиссионные вероятности описывают, как наблюдаемые данные зависят от скрытых состояний. Например, если O_k представляет наблюдаемое событие, то вероятность того, что это событие произойдет, когда система находится в состоянии S_i, обозначается как b_i(O_k). В каждой строке этой матрицы указаны вероятности наблюдения различных событий для конкретного состояния, и сумма всех вероятностей в строке равна 1.

Допустим, мы наблюдаем последовательность погодных условий, и есть скрытые состояния солнечно и дождливо. Начальные вероятности могут быть такими: P(\text{солнечно}) = 0.6 ) и P(\text{дождливо}) = 0.4. Матрица переходов может показывать, что если сегодня солнечно, то завтра также будет солнечно с вероятностью 0.7, а дождливо с вероятностью 0.3, и наоборот. Матрица эмиссий может указывать, что если сегодня солнечно, то с вероятностью 0.9 мы наблюдаем солнце, а с вероятностью 0.1 — дождь, и наоборот.

Реализация функции декодирования Витерби в TF

Установим сам TensorFlow:

pip install tensorflow

Также понадобится numpy.

На старте создадим кэш, который будет использоваться для хранения промежуточных значений вероятностей:

import tensorflow as tf

class HMM:
    def __init__(self, initial_prob, trans_prob, obs_prob):
        self.initial_prob = tf.constant(initial_prob, dtype=tf.float64)
        self.trans_prob = tf.constant(trans_prob, dtype=tf.float64)
        self.obs_prob = tf.constant(obs_prob, dtype=tf.float64)
        self.viterbi = tf.Variable(initial_value=tf.zeros([self.initial_prob.shape[0], None], dtype=tf.float64), trainable=False)

    def get_emission(self, obs_idx):
        return tf.gather(self.obs_prob, obs_idx)

Далее, объявим оператор для обновления кэша Витерби на каждом временном шаге:

class HMM:
    # предыдущий код инициализации

    def decode_op(self, obs_idx):
        emissions = self.get_emission(obs_idx)
        transitions = tf.matmul(self.viterbi, tf.transpose(emissions))
        weighted_transitions = transitions * self.trans_prob
        viterbi_update = tf.reduce_max(weighted_transitions, axis=1)
        return tf.reshape(viterbi_update, tf.shape(self.viterbi))

Обратные указатели необходимы для отслеживания наиболее вероятных путей переходов между состояниями:

class HMM:
    # предыдущий код инициализации и decode_op

    def backpt_op(self):
        back_transitions = tf.matmul(self.viterbi, tf.ones([self.viterbi.shape[1], self.trans_prob.shape[0]], dtype=tf.float64))
        weighted_back_transitions = back_transitions * self.trans_prob
        return tf.argmax(weighted_back_transitions, axis=1)

Объединяем все части для реализации полной функции:

import numpy as np

# пример данных HMM
initial_prob = np.array([0.6, 0.4])
trans_prob = np.array([[0.7, 0.3], [0.4, 0.6]])
obs_prob = np.array([[0.5, 0.5], [0.1, 0.9]])

# пример наблюдений
observations = np.array([0, 1, 1])

# инициализация модели
hmm = HMM(initial_prob, trans_prob, obs_prob)

# создание сессии TensorFlow
with tf.Session() as sess:
    sess.run(tf.global_variables_initializer())
    
    # инициализация кэша Витерби начальными вероятностями
    viterbi_init = sess.run(hmm.initial_prob)
    
    backpts = np.ones((hmm.trans_prob.shape[0], len(observations)), dtype='int32') * -1
    
    for t in range(1, len(observations)):
        feed_dict = {hmm.viterbi: viterbi_init}
        viterbi, backpt = sess.run([hmm.decode_op(observations[t]), hmm.backpt_op()], feed_dict=feed_dict)
        backpts[:, t] = backpt
    
    # вычисление наиболее вероятной последовательности состояний
    tokens = [np.argmax(viterbi)]
    for i in range(len(observations) - 1, 0, -1):
        tokens.append(backpts[tokens[-1], i])
    tokens.reverse()

    print('Most likely hidden states are', tokens)

Алгоритм Витерби не ограничивается только теоретическими задачам и применяется в телекоммуникациях, биоинформатики, обработки естественного языка и т.д.

Все актуальные методы и инструменты DS и ML можно освоить на онлайн-курсах OTUS: в каталоге можно посмотреть список всех программ, а в календаре — записаться на открытые уроки.

Комментарии (0)