Декодирование Витерби с 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: в каталоге можно посмотреть список всех программ, а в календаре — записаться на открытые уроки.