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

От марковских моделей к скрытым марковским моделям

Здравствуйте и вновь добро пожаловать на занятия по теме «Машинное обучение без учителя: скрытые марковские модели на языке Python».

В этой лекции мы расширим основную идею марковской модели до скрытой марковской модели.

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

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

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

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

Итак, как же перейти от обычной марковской модели к скрытой? Лучше всего сделать это с помощью примера. Предположим, мы находимся на карнавале и видим фокусника с двумя фальшивыми монетами, которые он прячет за спиной. Он случайным образом выбирает монету и подбрасывает её, а мы видим результат подбрасывания – выпадение орла или решки.

Что тут является скрытыми состояниями, а что – наблюдаемыми переменными? Поскольку мы видим результат подбрасывания монеты, то орёл и решка являются наблюдаемыми переменными. Их можно рассматривать как словарь, или пространство, возможных наблюдаемых значений. Скрытым же состоянием, разумеется, будет то, какую из монет фокусник решил подбросить. Мы не можем этого видеть, это скрыто для нас. Это и называется стохастическим, или случайным, процессом, поскольку это последовательность случайных переменных.

Как же определяется скрытая марковская модель? Скрытая марковская модель имеет три части: π, A и B. Этим она отличается от обычной марковской, которая имеет лишь π и A. π – это начальное распределение состояний, или вероятность пребывания в определённом состоянии в начале последовательности. В нашем примере с монетами допустим, что фокусник очень любит первую монету, поэтому вероятность, что он начнёт именно с неё, равна 0,9. A – матрица переходов состояний, показывающая вероятность перехода от одного состояния к другому. В скрытых марковских моделях состояния сами по себе являются скрытыми, так что это соответствует переходу из одного скрытого состояния в другое скрытое состояние. В примере с монетами предположим, что наш фокусник очень беспокойный, так что вероятность перехода от первой монеты ко второй равна 0,9, а вероятность обратного перехода от второй монеты к первой также равна 0,9. Тогда вероятность того, что фокусник не будет менять монету, составит 0,1 для каждой из них.

Новой переменной здесь является, конечно же, B. Это вероятность наблюдения некоторого результата с учётом того, в каком состоянии вы пребываете. Обратите внимание, что это тоже матрица, поскольку имеет две входных переменных – состояние, в котором вы пребываете (это j), и то, что вы при этом наблюдаете (это k). Таким образом, запись B(j, k) означает вероятность наблюдения k, находясь в состоянии j.

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

Что же мы можем сделать, уже имея скрытую марковскую модель? Напомним, это π, A и B. Почти то же, что и с обычными марковскими моделями, но с некоторыми дополнениями. Имея марковскую модель, мы могли сделать две основные вещи: во-первых, могли получить вероятность последовательности, равную произведению вероятностей переходов каждого состояния и вероятности начального состояния, а во-вторых, могли также обучить модель, используя максимум правдоподобия и подсчёт количества переходов.

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

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

Итого – три задачи скрытых марковских моделей, и мы рассмотрим каждую из них в последующих лекциях.

Двойная вложенность скрытых марковских моделей

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

А что, если применить гауссовы смеси распределений к скрытым состояниям? С этим мы разберёмся в следующей части, когда используем скрытые марковские модели для реальных наблюдений. При этом мы должны выбрать скрытое состояние, являющееся скрытой переменной, а после этого выбрать наблюдение, но сначала для этого надо выбрать гауссово распределение – ведь это тоже скрытая переменная. Таким образом, при использовании гауссовых смесей распределений появляется ещё один слой скрытых переменных.

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

Как выбрать количество скрытых состояний

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

Представим, что у нас есть N обучающих образцов и мы обучаем модель с N параметров. Мы получим идеальный результат без каких-либо ошибок. Но всё это ничего не скажет нам, насколько хорошо будет работать наша модель с новыми, ещё неизвестными данными. К примеру, возьмём биржевые котировки. Разумеется, мы хотим, чтобы модель давала хорошую точность в прогнозах прошлогодних тенденций, но вот что нам на самом деле нужно – это чтобы она была в состоянии предсказать с хорошей точностью тренды следующего года.

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

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

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

Обычно для этого используется K-блочная перекрёстная проверка. Работает она следующим образом. Мы делим данные на K частей; предположим, K = 5. Тогда на первом этапе мы обучаем модель на частях со 2-й по 5-ю, а точность модели проверяем на первой части наших данных. На втором этапе обучаем модель на 1-й, 3-й, 4-й и 5-й частях, а точность проверяем на 2-й части. На третьем этапе обучаем модель на 1-й, 2-й, 4-й и 5-й частях, а точность проверяем на 3-й. Это повторяется до пятого этапа. В этот момент у нас будет пять разных значений точности, и мы можем вычислить статистические показатели, такие как среднее значение и дисперсия, и просто выбрать лучшую модель с точки зрения этих величин.

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

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

Ещё один пример из биологии. Кодон – это последовательность трёх нуклеотид в ДНК или РНК. Они отвечают за создание определённых аминокислот, которые затем преобразуются белки. В этом случае скрытая марковская модель будет иметь три скрытых состояния.

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

Алгоритм прямого-обратного хода

Первый же вопрос, который возникает при работе со скрытыми марковскими моделями, является и простейшим: какова вероятность последовательности?

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

p(x(1), x(2), \;...\;, x(T) = \sum_{z(1)={1..M},...,z(T)={1,M}} \pi(z(1))p(x(1)|z(1)) \prod^{T}_{t=2} p(z(t)|z(t-1))p(x(t)|z(t)).

Обратите внимание, что оно включает в себя все переменные скрытой марковской модели. π даёт вероятность начального состояния, A даёт вероятность перехода в состояние j из состояния i:

A = (i,j) = p (z(t) = j|z(t-1) = i),

а B даёт вероятность наблюдать k из состояния j:

B = (j,k) = p (x(t) = k|z(t-1) = j).

Сколько же времени понадобится для вычисления всего этого? Во внутренней части у нас идёт произведение – всего 2T-1 умножений, проверьте сами. А сколько раз нам нужно вычислить это произведение? Ответ равен числу возможных последовательностей состояний, то есть MT. Таким образом, сложность алгоритма равна O(TMT). Это экспоненциальный рост, что весьма плохо, и вряд ли у кого возникнет желание этим заниматься.

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

Итак, как работает алгоритм прямого-обратного хода. Как правило, он описывается тремя этапами. Сначала мы должны определить переменную α – это переменная прямого хода и представляет совместную вероятность наблюдения имеющейся последовательности до текущего момента, пребывая в определённом состоянии в данный момент, поэтому у неё два индекса – время t и состояние i. Итак, первым этапом, этапом инициации, является вычисление начального значения α:

\alpha = (t,i) = \pi_iB(i,x(t)),

где t = 1.

\alpha(t+1,j) = \sum_{i=1}^{M} \alpha (t,i) A(i,j) B(j,x(t+1)).

Второй этап – индукция. Он вычисляется для каждого состояния и для каждого момента до момента T:

p(x) = \sum_{i=1}^{M} \alpha (T,i) = \sum_{i=1}^{M} p(x(1), \;...\;, x(T), z(T) = i).

И последний этап – завершающий, в котором мы исключаем скрытые состояния в момент T:

Обратите внимание, что у нас уже есть ответ – мы знаем вероятность последовательности даже после прохождения одного только прямого хода алгоритма. Но мы также можем убедиться, что сложность этого алгоритма составляет O(N2T). Попробуйте самостоятельно доказать, что это так.

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

\beta(t,i) = p(x(t+1), \;...\;, x(T)|z(t)=i).

Остальной процесс похож на алгоритм прямого хода.  Этап инициации состоит в определении β в момент T равной единице для каждого состояния:

\beta(T,i) = 1.

Этап индукции состоит в вычислении предыдущего значения β для каждого состояния, подобно тому, как мы это делали в алгоритме прямого хода. Вычисления проводятся для всех моментов времени до 1 или 0 (в зависимости от индекса) и для каждого состояния:

\beta(t,i) = \sum_{j=1}^{M} A(i,j) B(j,x(t+1))\beta(t+1),j).

Теперь посмотрим, как это реализуется в коде.

                alpha = np.zeros((T, self.M))

                alpha[0] = self.pi*self.B[:,x[0]]

                for t in xrange(1, T):

                    alpha[t] = alpha[t-1].dot(self.A) * self.B[:, x[t]]

                P[n] = alpha[-1].sum()

                beta = np.zeros((T, self.M))

                beta[-1] = 1

                for t in xrange(T – 2, -1, -1):

                    beta[t] = self.A.dot(self.B[:, x[t+1]] * beta[t+1])

Как вы можете видеть, α и β являются массивами размерностью TxM. Обратите внимание, как операции переводятся в векторную форму, стараясь по возможности избегать цикла for. При этом, заметьте, что мы можем вычислить вероятность даже до вычисления β.

Наглядное представление алгоритма прямого хода

Теперь, когда вы уже видели уравнение и реализацию алгоритма прямого хода, надеюсь, у вас было время обдумать его математический аспект и почему он работает. Но если нет, то эта лекция призвана помочь вам увидеть материал более наглядно. Ключевым тут будет «развёртывание» скрытой марковской модели во времени.

Сначала обсудим, что происходит в случае, если длина последовательности равна 1. Не забывайте, что наша цель – определить вероятность последовательности. Это простая задача нахождения вероятности. У нас есть π, которое задаёт вероятность первого состояния, и B, задающее вероятность наблюдения чего-либо, находясь в определённом состоянии. В этом случае мы просто исключаем состояния:

p(x(1)) = p(z(1) = 1)p(x(1)|z(1) = 1) +...+ p(z(1) = M)p(x(1)|z(1)=M)=

\pi_1B(1,x(1)) + \pi_2B(2,x(1)) + \pi_MB(M, (x(1)).

Этот первый этап можно показать в виде рисунка, как показано на слайде:

Мы начинаем с нулевой, или стартовой, позиции и двигаемся к одному из состояний – это π. Предположим, в данном примере количество состояний равно 3. В этом состоянии мы переходим к созданию наблюдаемой переменной. Она равна произведению π и B. Так, для трёх состояний:

\alpha(t=1, i=1) = p(x(1), z(1) = 1), = \pi_1 B (1,x(1)),

\alpha(t=1, i=2) = p(x(1), z(1) = 2), = \pi_2 B (2,x(1)),

\alpha(t=1, i=3) = p(x(1), z(1) = 3), = \pi_3 B (3,x(1)).

Обратите внимание, что это и есть определение начального значения α.

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

Найдём вероятность наблюдения номер 2, находясь в состоянии 1.

Может возникнуть вопрос: как можно достичь состояния 1, находясь в момент t = 2 и видя запись x(2)? Ответ в том, что мы можем прийти к нему из любого возможного предыдущего состояния. Поскольку каждый из переходов независим, мы можем сложить каждую из этих различных возможностей:

\pi_1A(1,1) B(1,x(2)) + \pi_2A(2,1) B(1(x(2)) + ...,

где π1 – вероятность, что мы начинаем с состояния 1, A(1, 1) – вероятность перехода из состояния 1 в состояние 1, B(1, x(2)) – вероятность наблюдения x(2), находясь в состоянии 1. Затем мы добавляем возможности того, что переходим из состояний 2 и 3.

Обратите внимание, что если мы добавим B для момента t = 1, то получается просто α, поэтому мы можем переписать предыдущую вероятность с использованием предыдущего значения α:

\pi_1B(1,x(1))A(1,1)B(1,x(2))+\pi_2 B(2,x(1)) A(2,1) B(1(x(2)) + ... =

=\alpha(t=0, j = 1) A(1,1) B(1,x(2)) + \alpha (t=0, i=2) A(2,1) B(1,x(2)) +...

И заметьте, что это – следующая α:

\alpha(t=1, j = 1) A(1,1) B(1,x(2)) + \alpha (t=1, i=2) A(2,1) B(1,x(2)) +...=

=\alpha(t=2, i=1).

Таким образом, α определяется рекурсивно.

Это конкретное значение α для момента времени t = 2 и состояния 1, является вероятностью наблюдения x(1) и x(2), пребывая в состоянии 1 в момент t = 2.

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

Продолжая этот процесс, мы в конечном итоге получим α для момента времени T, являющейся вероятностью всей последовательности, заканчивающейся в состоянии i.

Не забывайте, что наша цель – только найти вероятность последовательности. Что для этого нужно сделать? Да то же самое, что мы делали вначале. Исключаем z, то есть, другими словами, суммируем последнее α по всем i:

p(x(1)), ... , x(T)) = \sum_{i=1..M} \alpha(T,i).

Понравилась статья? Поделить с друзьями:
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: