Как он устроен и что с ним делать?

Примечание. В этой серии статей я расскажу о том, что я узнал о HMM за последние несколько дней. Я постарался сделать статьи максимально простыми для понимания. Хотя это не систематический способ, которым может предложить вам учебник, но я надеюсь, что моя статья может помочь вам преодолеть некоторые узкие места на вашем пути. Удачи!

Часть 1: Архитектура скрытой марковской модели
Часть 2: Алгоритм обучения HMM: алгоритм Баума-Велча
Часть 3: Алгоритм прогнозирования с помощью обученного алгоритма HMM: Viterbi

Введение в скрытую марковскую модель

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

Интересно? Есть много случаев, когда наблюдаемое не является истиной, и скрытая марковская модель - это один из способов, который может вернуть нам скрытую истину. Однако это не магия для всего, и чтобы ее использовать, она должна удовлетворять некоторым предположениям, на которых была основана HMM. Мой подход здесь состоит в том, чтобы обсудить HMM словами и дополнить его математикой, которую можно пропустить, если на этот раз это не ваша чашка чая. Давайте начнем!

Последовательность состояний и наблюдаемые

В любом из приведенных выше примеров мы действительно имеем дело с последовательностями данных. Например, мы можем ошибочно набрать «разное» как «miscella m eous», которые на самом деле являются последовательностями символов. И в примере с GPS, если мы остановимся на месте (22,3525 ° N 113,8475 ° E), то это следует повторить пять раз, если мы будем записывать показания один раз в секунду в течение непрерывных пяти секунд. Однако по мере того, как показания меняются, мы можем увидеть (22,3535 ° N 113,8455 ° E), (22,3585 ° N 113,8325 ° E), (22,3123 ° N 113,8600 ° E), (22,3212 ° N 113,8397 ° E), ( 22.3421 ° с.ш. 113.7989 ° в.д.).

Здесь для каждых наблюдаемых данных у нас есть связанная скрытая правда. В формальном обсуждении HMM люди называют каждую «скрытую истину» «переменной состояния», а все «наблюдаемые данные» - «наблюдаемой переменной».

Состояния и наблюдаемые в структуре HMM

Давайте посмотрим на рисунок выше. В этой архитектуре HMM у нас есть последовательность состояний (скрытых истин), «связанных» друг с другом. Стрелка здесь означает зависимость. Например, состояние в момент времени = 1 зависит от состояния в момент времени = 0. Это очень важное допущение в модели Маркова, которое делает его настолько простым - любое состояние зависит ТОЛЬКО от некоторых из его предыдущих состояний. . Я ставлю (а) после состояния, потому что это необязательно. Мы называем это простой цепью Маркова, если состояние зависит от своего первого предыдущего состояния, тогда как это цепь Маркова n-го порядка, если состояние зависит от своего первого n предыдущего состояния. состояния.

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

Переход между состояниями, излучение и начальное состояние

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

Предположим, существует M возможных состояний на выбор, а именно, состояние может быть любым из {1, 2, 3,…, m}. И мы могли бы количественно оценить вероятность перехода из состояния i в состояние j как aᵢⱼ. Поскольку переход может произойти из любого из M возможных состояний в другое из M возможных состояний, всего существует M × M возможностей. И мы могли бы расположить их в следующем матричном представлении, которое называется матрицей перехода состояний A.

Поскольку все aᵢⱼ являются значениями вероятности, все они ограничены диапазоном от 0 до 1, и каждая строка должна быть суммирована до 1. Вообще говоря, у нас может быть одна такая матрица A для каждого временного шага t. Однако мы будем рассматривать стационарную цепь Маркова, что означает, что матрица A постоянна во времени.

Точно так же мы могли бы построить матрицу выбросов B для хранения вероятностей состояния i, приводящего к наблюдаемому значению j . Здесь предполагается, что наблюдаемая имеет K возможных значений, что означает, что она может принимать любое из {1, 2,…, k}. Здесь также предполагается стационарность, поэтому мы имеем одну постоянную матрицу излучения.

Мы близки к полной картине, и теперь у нас есть архитектура, матрица переходов состояний A и матрица выбросов B. . Последнее, что нам понадобится, это распределение вероятностей π₀ начального состояния X ₀. Он нужен нам для запуска первого состояния, чтобы следующие состояния в цепи Маркова можно было оценить с помощью матрицы переходов состояний.

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

Первая строка таблицы дает нам начальное распределение состояний π₀, а остальные образуют матрицу переходов состояний A. Что касается матрицы выбросов B, давайте поспорим, что в 70% случаев пользователь вводит символ правильно, в противном случае набирается соседний символ. Например, если мы намереваемся ввести «G» (состояние), то в 70% случаев мы правильно набираем «G» (наблюдается), и 30% получают любое из {'T', 'Y', ' F ',' H ',' C ',' V ',' B '} или ~ 4,2% каждый. С помощью этого аргумента мы могли построить матрицу выбросов.

Резюме

Давайте сделаем перерыв здесь. К настоящему времени мы увидели, что модель HMM построена на основе переменных состояния и связанных наблюдаемых переменных, а для каждого состояния - от количества предыдущих состояний, от которых оно зависит. Затем модель параметризуется матрицей переходов состояний A, матрицей выбросов B и распределением начальных состояний. π₀. Обратите внимание, что HMM, о которой мы говорили, представляет собой стационарную простую скрытую марковскую модель, которая принимает дискретные переменные состояния, дискретные наблюдаемые переменные, а переменные дискретны во времени, поэтому это один частный случай в семействе HMM.

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