Для машинного обучения требуется множество сложных алгоритмов, чтобы учиться на существующих данных, а затем применять полученные знания к новым данным. Динамическое программирование встречается во многих из этих алгоритмов. Это может быть связано с тем, что динамическое программирование отлично справляется с решением проблем, связанных с «нелокальной» информацией, что делает неэффективными жадные алгоритмы или алгоритмы «разделяй и властвуй».

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

Эта статья является частью продолжающейся серии по динамическому программированию. Если вам нужно освежить эту технику, см. Мое Графическое введение в динамическое программирование.

(Я выступал на эту тему на PyData Los Angeles 2019, если вы предпочитаете видеоверсию этого поста.)

Определение скрытой марковской модели

Скрытая марковская модель имеет дело с выводом состояния системы на основании некоторых ненадежных или неоднозначных наблюдений из этой системы. Одной из важных характеристик этой системы является то, что состояние системы меняется со временем, производя последовательность наблюдений на этом пути. Есть некоторые дополнительные характеристики, объясняющие марковскую часть HMM, которые будут представлены позже. Путем включения некоторых предметных знаний можно взять наблюдения и работать в обратном направлении к максимально правдоподобной основной истине.

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

Формальное определение скрытой марковской модели.

HMM состоит из нескольких частей. Во-первых, это возможные состояния s [i] и наблюдения o [k]. Они определяют саму HMM. Экземпляр HMM проходит через последовательность состояний, x [0], x [1],…, x [n − 1], где x [0] является одним из s [i], x [1] является одним из s [i] и т. д. Каждое состояние производит наблюдение, результатом которого является последовательность наблюдений y [0], y [1],…, y [n − 1], где y [0] является одним из o [k], y [1] является одним из o [k] и т. д.

Далее следуют параметры, объясняющие, как HMM ведет себя с течением времени:

  • Есть вероятности начального состояния. Какова вероятность начала работы в состоянии s [i] для каждого возможного состояния s [i]? Эти вероятности обозначаются π (s [i]).
  • Существует Матрица перехода состояний, определяющая, как состояние изменяется с течением времени. Если система в какой-то момент находится в состоянии s [i], какова вероятность того, что она окажется в состоянии s [j] после одного временного шага? Эти вероятности называются a (s [i], s [j]).
  • Есть Матрица вероятности наблюдения. Если система находится в состоянии s [i], какова вероятность наблюдения наблюдения o [k]? Эти вероятности называются b (s [i], o [k]).

Последние два параметра особенно важны для HMM. Второй параметр настроен так, что в любой момент времени вероятность следующего состояния определяется только текущим состоянием, а не полной историей системы. Это «марковская» часть HMM. Третий параметр настроен так, что в любой момент времени текущее наблюдение зависит только от текущего состояния, а не от всей истории системы.

Выявление наиболее вероятной последовательности состояний

Главный вопрос, который следует задать о скрытой марковской модели: с учетом последовательности наблюдений, какова наиболее вероятная последовательность состояний, которые привели к этим наблюдениям? Мы можем ответить на этот вопрос, посмотрев на каждую возможную последовательность наблюдений. состояний, выбирая последовательность, которая максимизирует вероятность получения данных наблюдений. Как мы увидим, динамическое программирование помогает нам эффективно рассматривать все возможные пути.

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

Алгоритм, который мы разрабатываем в этом разделе, называется алгоритм Витерби.

Определите рекуррентное отношение

Начнем с простого случая: у нас есть только одно наблюдение y. Какое государство, скорее всего, произвело это наблюдение? Для состояния s должны произойти два события:

  • Мы должны начать с состояния s, события с вероятностью π (s).
  • Это состояние должно вызвать наблюдение y, событие с вероятностью b (s, y).

Основываясь на «марковском» свойстве HMM, где вероятность наблюдений из текущего состояния не зависит от того, как мы дошли до этого состояния, эти два события независимы. Это позволяет нам умножить вероятности двух событий. Итак, вероятность наблюдения y на первом временном шаге (индекс 0) равна:

С помощью приведенного выше уравнения мы можем определить значение V (t, s), которое представляет вероятность наиболее вероятного пути, который:

  • Имеет состояния t + 1, начиная с временного шага 0 и заканчивая временным шагом t.
  • Заканчивается в состоянии s.
  • Производит первые предоставленные нам t + 1 наблюдения.

До сих пор мы определили V (0, s) для всех возможных состояний s.

Если бы у нас было только одно наблюдение, мы могли бы просто взять состояние s с максимальной вероятностью V (0, s), и это наша наиболее вероятная «последовательность» состояний. Но если у нас есть больше наблюдений, теперь мы можем использовать рекурсию.

Допустим, мы рассматриваем последовательность наблюдений t + 1. Мы не знаем, что такое последнее состояние, поэтому должны учитывать все возможные конечные состояния s. Мы также не знаем предпоследнего состояния, поэтому должны учитывать все возможные состояния r, из которых мы могли бы переходить из. Это означает, что нам нужно, чтобы произошли следующие события:

  • Нам нужно закончить в состоянии r на предпоследнем шаге в последовательности, событии с вероятностью V (t − 1, r).
  • Мы должны перейти из некоторого состояния r в конечное состояние s, событие, вероятность которого равна a (r, s).
  • В конечном состоянии должно произойти наблюдение y, событие с вероятностью b (s, y).

Все эти вероятности не зависят друг от друга. В результате мы можем умножить три вероятности вместе. Эта вероятность предполагает, что у нас есть r на предпоследнем шаге, поэтому теперь мы должны рассмотреть все возможные r и взять максимальную вероятность:

Это определяет V (t, s) для каждого возможного состояния s.

Обратите внимание, что вероятность наблюдения зависит только от последнего состояния, а не от предпоследнего состояния. Это означает, что мы можем извлечь вероятность наблюдения из операции max.

Еще одна важная характеристика, на которую следует обратить внимание, заключается в том, что мы не можем просто выбрать наиболее вероятное предпоследнее состояние, то есть мы не можем просто максимизировать V (t − 1, r). Может оказаться, что особое предпоследнее состояние весьма вероятно. Однако, если вероятность перехода из этого состояния в s очень мала, может быть более вероятен переход из предпоследнего состояния с меньшей вероятностью в s.

Напомним, что наше рекуррентное соотношение формально описывается следующими уравнениями:

Это отношение повторения немного отличается от тех, которые я представил в своих предыдущих сообщениях, но у него все еще есть свойства, которые мы хотим:

  • Рекуррентное отношение имеет целочисленные входы. Технически второй вход - это состояние, но есть фиксированный набор состояний. Мы можем присвоить целые числа каждому состоянию, хотя, как мы увидим, на самом деле нам не нужно упорядочивать возможные состояния.
  • Окончательный ответ, который мы хотим, легко извлечь из соотношения. Мы смотрим на все значения отношения на последнем временном шаге и находим конечное состояние, которое максимизирует вероятность пути.
  • Отношение зависит от самого себя.

Проверка подзадачи DAG (ориентированный ациклический граф)

Если посмотреть на рекуррентное соотношение, есть два параметра. Первый параметр t находится в диапазоне от 0 до T − 1, где T - общее количество наблюдений. Это потому, что для каждого наблюдения существует одно скрытое состояние.

Второй параметр s охватывает все возможные состояния, то есть этот параметр может быть представлен как целое число от 0 до S − 1, где S - количество возможных состояний. Каждое целое число представляет одно возможное состояние.

Это означает, что мы можем представить наши подзадачи в виде двумерной сетки размером T × S. Столбцы представляют собой набор всех возможных конечных состояний на одном временном шаге, причем каждая строка является возможным конечным состоянием.

В момент времени t = 0, то есть в самом начале, подзадачи не зависят от других подзадач. Это наши базовые случаи.

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

Этот процесс повторяется для каждого возможного конечного состояния на каждом временном шаге.

Как и в предыдущей статье, я не показываю полный граф зависимостей из-за большого количества стрелок зависимостей.

Реализация снизу вверх

Из приведенного выше анализа мы видим, что мы должны решать подзадачи в следующем порядке:

  1. Увеличьте временной шаг t = 0 до t = T − 1.
  2. На каждом временном шаге оценивайте вероятности возможных конечных состояний в любом порядке.

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

Следующая реализация во многом заимствует аналогичную реализацию вырезания швов из моего последнего поста, поэтому я пропущу использование обратных указателей.

Во-первых, нам нужно представление нашей HMM с тремя параметрами, которые мы определили в начале сообщения. Параметры следующие:

  • Словарь p, представляющий начальные вероятности π (s).
  • Вложенный словарь a, представляющий матрицу перехода состояний a (r, s).
  • Вложенный словарь b, представляющий матрицу вероятности наблюдения b (s, y).

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

class HMM:
    def __init__(self, p, a, b):
        self.possible_states = p.keys()
        self.p = p
        self.a = a
        self.b = b
# The following is an example. We'll define a more meaningful
# HMM later.
hmm = HMM(
    # initial state probabilities
    { 's0': 0.6, 's1': 0.4 },
    # state transition matrix
    {
        's0': { 's0': 0.6, 's1': 0.4 },
        's1': { 's0': 0.4, 's1': 0.6 }
    },
    # observation probability matrix
    {
        's0': { 'y0': 0.8, 'y1': 0.2 },
        's1': { 'y0': 0.2, 'y1': 0.8 }
    }
)

Как и в реализации вырезания швов, мы будем хранить элементы нашей двумерной сетки как экземпляры следующего класса. Класс просто сохраняет вероятность соответствующего пути (значение V в соотношении повторения) вместе с предыдущим состоянием, которое дало эту вероятность.

class PathProbabilityWithBackPointer:
    def __init__(self, probability, previous_state=None):
        self.probability = probability
        self.previous_state = previous_state

После того, как все это настроено, мы начнем с расчета всех базовых случаев. Это означает вычисление вероятностей одноэлементных путей, которые заканчиваются в каждом из возможных состояний. Здесь observations - это список строк, представляющих наблюдаемые нами наблюдения.

path_probabilities = []
# Initialize the first time step of path probabilities based on
# the initial state probabilities. There are no back pointers in
# the first time step.
path_probabilities.append({
    possible_state: PathProbabilityWithBackPointer(
        hmm.p[possible_state] *
        hmm.b[possible_state][observations[0]])
    for possible_state in hmm.s
})

Затем идет основной цикл, в котором мы вычисляем V (t, s) для каждого возможного состояния s в терминах V (t − 1, r) для каждого возможного предыдущего состояния r.

# Skip the first time step in the following loop.
for t in range(1, len(observations)):
    observation = observations[t]
    latest_path_probabilities = {}
    for possible_state in hmm.possible_states:
        max_previous_state = max(
            hmm.possible_states,
            key=lambda s_i: (
                path_probabilities[t - 1][s_i].probability *
                hmm.a[s_i][possible_state]
            )
        )
        max_path_probability = PathProbabilityWithBackPointer(
            hmm.b[possible_state][observation] *
            path_probabilities[t - 1][max_previous_state].probability *
            hmm.a[max_previous_state][possible_state],
            max_previous_state
        )
        latest_path_probabilities[possible_state] = \
            max_path_probability
    path_probabilities.append(latest_path_probabilities)

После завершения всех итераций T − 1 с учетом того факта, что первый временной шаг был обработан до цикла, мы можем извлечь конечное состояние для наиболее вероятного пути, максимизируя все возможные конечные состояния в последний временной шаг.

max_path_end_state = max(
    hmm.possible_states,
    key=lambda s: path_probabilities[-1][s].probability
)

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

path = []
path_step_state = max_path_end_state
for t in range(len(path_probabilities) - 1, -1, -1):
    path.append(path_step_state)
    path_step_state = \
        path_probabilities[t][path_step_state].previous_state
path.reverse()

Попробуйте протестировать эту реализацию на следующем HMM.

hmm = HMM(
    # initial state probabilities
    { 's0': 0.8, 's1': 0.1, 's2': 0.1 },
    # state transition matrix
    {
        's0': { 's0': 0.9, 's1': 0.1, 's2': 0.0 },
        's1': { 's0': 0.0, 's1': 0.0, 's2': 1.0 },
        's2': { 's0': 0.0, 's1': 0.0, 's2': 1.0 }
    },
    # observation probability matris
    {
        's0': { 'y0': 1.0, 'y1': 0.0 },
        's1': { 'y0': 1.0, 'y1': 0.0 },
        's2': { 'y0': 0.0, 'y1': 1.0 }
    }
)

В этом HMM третье состояние s2 - единственное, которое может произвести наблюдение y1. Кроме того, единственный способ попасть в состояние s2 - сначала перейти в состояние s1. Начиная с наблюдений ['y0', 'y0', 'y0'], наиболее вероятной последовательностью состояний будет просто ['s0', 's0', 's0'], потому что HMM вряд ли перейдет в состояние s1.

Однако, если вы затем наблюдаете y1 на четвертом временном шаге, наиболее вероятный путь изменится. Вы знаете, что последним состоянием должно быть s2, но поскольку перейти в это состояние напрямую из s0 невозможно, предпоследним состоянием должно быть s1. Это означает, что наиболее вероятный путь - ['s0', 's0', 's1', 's2'].

Сложность времени и пространства

Из графика зависимостей мы можем сказать, что для каждого возможного состояния на каждом временном шаге есть подзадача. Поскольку мы должны сохранять результаты всех подзадач для отслеживания обратных указателей при восстановлении наиболее вероятного пути, алгоритм Витерби требует пространства O (T × S), где T - количество наблюдений, а S - количество возможных состояний.

Мы должны решить все подзадачи один раз, и каждая подзадача требует перебора всех S возможных предыдущих состояний. Таким образом, временная сложность алгоритма Витерби составляет O (T × S ² ).

Реальные приложения

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

  • Фильтрация, при которой зашумленные данные очищаются, чтобы выявить истинное состояние мира. Пример фильтрации - определение положения робота при наличии шумного датчика.
  • Распознавание, где косвенные данные используются, чтобы сделать вывод о том, что они представляют.

Давайте посмотрим на еще несколько реальных примеров этих задач:

  • Распознавание речи. Распознавание речи, также известное как преобразование речи в текст, воспринимает серию звуков. Эти звуки затем используются для вывода основных слов, которые являются скрытыми состояниями.
  • Обнаружение лиц. Чтобы найти лица на изображении, один алгоритм обнаружения лиц на основе HMM наблюдает перекрывающиеся прямоугольные области яркости пикселей. Эти значения интенсивности используются для определения черт лица, таких как волосы, лоб, глаза и т. Д. Эти черты являются скрытыми состояниями, и когда HMM встречает такую ​​область, как лоб, он может только оставаться в этой области или перейти к следующему. Состояние, в данном случае глаза. Если все состояния присутствуют в предполагаемой последовательности состояний, то лицо было обнаружено. См. Обнаружение и распознавание лиц с использованием скрытых марковских моделей Нефиан и Хейс.
  • Вычислительная биология. HMM нашли широкое применение в вычислительной биологии. Одна из проблем - классифицировать разные участки в последовательности ДНК. Элементы последовательности, нуклеотиды ДНК, представляют собой наблюдения, а состояния могут быть областями, соответствующими генам, и областями, которые вообще не представляют гены. Для обзора различных приложений HMM в вычислительной биологии см. Скрытые марковские модели и их приложения в анализе биологической последовательности.

Использование скрытых марковских моделей для машинного обучения

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

Извлечение признаков

Реальные проблемы не появляются на пустом месте в форме HMM. Чтобы применить подход динамического программирования, нам нужно сформулировать проблему в терминах состояний и наблюдений. Это известно как извлечение признаков и широко применяется в любом приложении машинного обучения.

В вышеупомянутых приложениях извлечение признаков применяется следующим образом:

  • При распознавании речи входящая звуковая волна разбивается на небольшие фрагменты, а частоты извлекаются для формирования наблюдения. Для получения информации см. Применение скрытых марковских моделей в распознавании речи от Гейлса и Янга.
  • При обнаружении лиц просмотр прямоугольной области пикселей и прямое использование этих значений интенсивности делает наблюдения чувствительными к шуму на изображении. Более того, многие отдельные области пикселей достаточно похожи, поэтому их не следует рассматривать как отдельные наблюдения. Для борьбы с этими недостатками подход, описанный в Nefian and Hayes 1998 (ссылка на который приведена в предыдущем разделе), обеспечивает интенсивность пикселей с помощью операции, известной как преобразование Карунена – Лоэва, для извлечения только наиболее важных аспектов. пикселей в регионе.
  • В вычислительной биологии наблюдения часто являются элементами последовательности ДНК. Однако иногда входные данные могут быть элементами нескольких, возможно, выровненных последовательностей, которые рассматриваются вместе.

Обучение с использованием максимизации ожиданий

Все это время мы предполагали наиболее вероятный путь, основываясь на данных о переходах между состояниями и вероятностях наблюдения. Но как мы вообще можем найти эти вероятности? За определение параметров HMM отвечает обучение.

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

Концепция обновления параметров на основе результатов текущего набора параметров таким образом является примером алгоритма ожидания-максимизации. Применительно к HMM алгоритм известен как алгоритм Баума-Велча.

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

Последняя пара статей охватывала широкий круг тем, связанных с динамическим программированием. Дайте мне знать, что вы хотите увидеть дальше! Есть ли конкретная часть динамического программирования, о которой вы хотите получить более подробную информацию? Или вы хотите прочитать конкретно о машинном обучении? Дайте мне знать, чтобы я мог сосредоточиться на том, что было бы наиболее полезно осветить.

Если вам нравится мой контент, вы можете купить мне кофе в Ko-fi.