Декодирование Витерби с TensorFlow
Привет, Хабр!
Алгоритм был предложен Эндрю Витерби в 1967 году для декодирования сигналов с кодировкой, используемой в системах связи.
Алгоритм Витерби предназначен для поиска наиболее вероятной последовательности скрытых состояний в моделях с наблюдаемыми переменными, таких как скрытые марковские модели. Основное применение заключается в декодировании, где нужно определить скрытую последовательность состояний, вызвавших наблюдаемую последовательность событий.
Основные концепции алгоритма:
Начальные вероятности: определяют, с какой вероятностью процесс начинается в каждом возможном состоянии. В контексте скрытых марковских моделей, начальные вероятности (или начальные распределения) дают нам понимание того, каковы шансы нахождения системы в каждом из возможных начальных состояний. Например, если есть три возможных состояния
,
и
, начальные вероятности могут быть представлены как,
и
, где сумма всех вероятностей равна
.
Матрица переходов: матрица, в которой каждая ячейка
представляет собой вероятность перехода из состояния
в состояние
. Матрица переходов отображает динамику системы, показывая, как вероятности изменения состояний зависят от текущего состояния. В скрытых марковских моделей если система находится в состоянии
в момент времени
, то
показывает вероятность перехода в состояние
в момент времени
.
Матрица эмиссий: матрица определяет вероятность наблюдения каждого возможного события в каждом состоянии. Эмиссионные вероятности описывают, как наблюдаемые данные зависят от скрытых состояний. Например, если
представляет наблюдаемое событие, то вероятность того, что это событие произойдет, когда система находится в состоянии
, обозначается как
. В каждой строке этой матрицы указаны вероятности наблюдения различных событий для конкретного состояния, и сумма всех вероятностей в строке равна
.
Допустим, мы наблюдаем последовательность погодных условий, и есть скрытые состояния солнечно и дождливо. Начальные вероятности могут быть такими: ) и
. Матрица переходов может показывать, что если сегодня солнечно, то завтра также будет солнечно с вероятностью
, а дождливо с вероятностью
, и наоборот. Матрица эмиссий может указывать, что если сегодня солнечно, то с вероятностью
мы наблюдаем солнце, а с вероятностью
— дождь, и наоборот.
Реализация функции декодирования Витерби в 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: в каталоге можно посмотреть список всех программ, а в календаре — записаться на открытые уроки.