Скрытые цепи Маркова, алгоритм Витерби

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

    Исходный сигнал

    Интересный метод, описан в статье «A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition» L.R. Rabiner, которая вводит модель скрытой цепи Маркова и описывает три ценных алгоритма: The Forward-Backward Procedure, Viterbi Algorithm и Baum-Welch reestimation. Несмотря на то, что эти алгоритмы представляют интерес только в совокупности, для большего понимания описывать их лучше по отдельности.


    Метод скрытых цепей Маркова имеет широкое применение, например, он используется для поиска CG-островков (участков DNA, RNA с высокой плотностью связки цитозина и гуанина), в то время как сам Лоренс Рабинер использовал его для распознавания речи. Мне алгоритмы пригодились для того, чтобы отслеживать смену стадий сна/бодрствования по электроэнцефалограмме и искать эпилептические припадки.

    В модели скрытых цепей Маркова предполагается, что рассматриваемая система обладает следующими свойствами:

    1. в каждый период времени система может находится в одном из конечного набора состояний;
    2. система случайно переходит из одного состояния в другое (возможно, в то же самое) и вероятность перехода зависит только от того состояния, в котором она находилась;
    3. в каждый момент времени система выдает одно значение наблюдаемой характеристики – случайную величину, зависящую только от текущего состояния системы.


    Модель HMM можно описать как: HMM= \langle M, S, I, T, E\rangle
    • M – число состояний;
    • S=\{S_1,...,S_M\} – конечное множество состояний;
    • I=(P(q_0=S_i)=\pi_i) – вектор вероятностей, того что система находится в состоянии i в момент времени 0;
    • T=\|P(q_t=S_j|q_{t-1}=S_i)=a_{ij}\| – матрица вероятностей перехода из состояния i в состояние j для \forall t\in[1,T_m];
    • E=(E_1,...,E_M), E_i=f(o_t|q_t=S_i)– вектор распределений наблюдаемых случайных величин, соответствующих каждому из состояний, заданных как функции плотности или распределения, определенные на O (совокупности наблюдаемых значений для всех состояний).


    Время t предполагается дискретным, заданным неотрицательными целыми числами, где 0 соответствует начальному моменту времени, а Tm наибольшему значению.

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

    Более простое описание уже упоминалось в Вероятностные модели: примеры и картинки.

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


    У исследователя, обычно, есть свобода в выборе распределения наблюдаемых состояний. Чем сильнее наблюдаемые величины различают скрытые состояния тем лучше. С точки зрения программирования, перебор различных наблюдаемых характеристик означает необходимость аккуратной инкапсуляции E_i. На графике ниже приведен пример исходных данных для задачи о детекторе лжи, где распределение наблюдаемой характеристики (подрагивания рук) непрерывное, так как моделировалось как нормальное с средним 0 для обоих состояний, с дисперсией равной 1, когда человек говорит правду (фиолетовые столбцы) и 1.21, когда лжет (зеленые столбцы):


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

    Дано:

    два скрытых состояния, где честному поведению соответствует белый шум с дисперсией 1, лжи – белый шум с дисперсией 1.21;
    выборка из 10 000 последовательных наблюдений o;
    смена состояний происходит в среднем раз в 2 500 тактов.
    Требуется определить моменты смены состояний.

    Решение:

    Зададим пятерку параметров модели:
    • число состояний M=2;
    • S={1,2};
    • опыт показывает, что начальное распределение практически не имеет значения, поэтому I=(0.5,0.5);
    • T\leftarrow\left(\begin{matrix}1-1/2500&1/2500\\1/2500&1-1/2500\end{matrix}\right);
    • E=(N(0,1),N(0,1.21)).

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

    По модели скрытых цепей Маркова и выборке значений наблюдаемых характеристик найдем такую последовательность состояний, которая наилучшим образом описала бы выборку в заданной модели. Понятие наилучшим образом можно трактовать по-разному, но устоявшимся решением является алгоритм Витерби, который находит такую последовательность Q^*=(q_0,..,q_{T_m}), q_i\in S, что P(Q^*,O|HMM)=\max\limits_{Q\in\Omega}P(Q,O|HMM).

    Задача поиска Q^* решается с помощью динамического программирования, для этого рассмотрим функцию:

    \delta_t(s) = \max\limits_{I=(i_0, ..., i_{t-1})}P(q_0=S_{i_0},..,q_{t-1}=S_{i_{t-1}}, q_t=s)
    где \delta_t(s) — наибольшая вероятность оказаться в состоянии s в момент времени t. Рекурсивно, эту функцию можно определить следующим образом:

    \delta_0(s) = \pi_s f_s(o_0), \delta_t(s) = \max_{s'\in S}(\delta_{t-1}(s')a_{s's}) f_s(o_t)
    Одновременно с расчетом\delta_t(s) для каждого момента времени запоминаем наиболее вероятное состояние, из которого мы пришли, то есть q_t=\arg\max\limits_{s'\in S}(\delta_{t-1}(s')a_{s's}), на котором был достигнут максимум. При этом q_{T_m} = \arg\max\limits_{s\in S} (\delta_{T_m}(s)), и значит, можно восстановить Q^*=(q_0^*, ..., q_{T_m}^*), пройдясь по ним в обратном порядке. Можно заметить, что \max\limits_{s\in S}(\delta_{t}(s)) = P(Q^*,O|HMM)– значение искомой вероятности. Требуемая последовательность Q^* найдена. Интересным свойством алгоритма является, то что оценочная функция наблюдаемых характеристик входит в \delta_t(s) в виде сомножителя. Если считать, что image, то в случае пропусков в наблюдениях, все равно можно оценить наиболее вероятные скрытые состояния в эти моменты.

    «Псевдокод» для алгоритма Витерби набросан ниже. Необходимо учесть, что все операции с векторами и матрицами поэлементные.

    Tm<-10000 # Max time
    M<-2 # Number of states
    S<-seq(from=1, to=M) # States [1,2]
    I<-rep(1./M, each=M) # Initial distribution [0.5, 0.5]
    T<-matrix(c(1-4./Tm, 4./Tm, 4./Tm,1-4./Tm),2) #[0.9995 0.0005; 0.0005 0.9995]
    P<-c(function(o){dnorm(o)}, function(o){dnorm(o,sd=1.1)}) # Vector of density functions for each state (N(0,1), N(0,1.21))
    
    E<-function(P,s,o){P[[s]](o)} # Calculate probability of observed value o for state s.
    
    Es<-function(E,P,o) {
      # Same for all states
      probs<-c()
      for(s in S) {
        probs<-append(probs, E(P,s,o))
      }
      return(probs)
    }
    
    viterbi<-function(S,I,T,P,E,O,tm) {
      delta<-I*Es(E,P,O[1]) # initialization for t=1
      prev_states<-cbind(rep(0,length(S))) # zeros
      for(t in 2:Tm) {
        m<-matrix(rep(delta,length(S)),length(S))*T # delta(s')*T[ss'] forall s,s'
        md<-apply(m,2,max) # search for max delta(s) by s' for all s
        max_delta<-apply(m,2,which.max)
        prev_states<-cbind(prev_states,max_delta)  
        delta<-md*Es(E,P,O[t]) # prepare next step delta(s)
      }
      return(list(delta=delta,ps=prev_states)) # return delta_Tm(s) and paths
    }
    
    restoreStates<-function(d,prev_states) {
      idx<-which.max(d)
      s<-c(idx)
      sz<-length(prev_states[1,])
      for(i in sz:2) {
        idx<-prev_states[idx,i]
        s<-append(s,idx,after=0)
      }
      return (as.vector(s))
    }
    


    Кто-нибудь мог узнать в этом “псевдокоде” код на R, но это далеко не самая лучшая реализация.

    Сравним периоды постоянства состояний, которые были заданы при моделировании (верхняя часть графика), и те, которые были найдены с помощью алгоритма Витерби (нижняя часть графика):


    Вполне достойно по-моему, но каждый раз на такое не стоит надеяться.

    Описанный ранее алгоритм Витерби требует определения модели скрытой цепи Маркова (Аргументов функции viterbi). Для их задания используется простая инициализация, которая подразумевает, что кроме выборки наблюдаемых величин O так же задана соответствующая им выборка скрытых состояний Q, которые откуда-то нам известны. В таком случае формулы для оценки параметров будут выглядеть следующим образом:
    S\leftarrow \left\{s:q_t=s,t\in[0,T_m]\right\} \\
M\leftarrow \|S\| \\
I\leftarrow \left(\frac{\sum_{t\in[0,T_m]}Id(q_t=s)}{T_m+1}, s\in S\right) \\
T\leftarrow \left(\frac{\sum_{t\in[1,T_m]}Id(q_{t-1}=s',q_t=s)}{\sum_{t\in[0,T_m]}(\sum_{t\in[1,T_m]}Id(q_{t-1}=s')}, s,s'\in S\right) \\
E\leftarrow \left(f_s(o_t)=\frac{\sum_{t\in [0,T_m]}Id(q_t=s,o_t=e)}{\sum_{t\in[0,T_m]}Id(q_t=s)}, s\in S\right)
    где Id(x) – индикаторная функция, Id(x)=\begin{cases}1,\mbox{x is true},\\0, \mbox{x is false.}\end{cases}

    Для рассмотренного примера о детекторе лжи алгоритм неправильно классифицировал 413 из 10 000 состояний (~4%), что вовсе не плохо. Алгоритм Витерби способен с хорошей точностью детектировать моменты смены скрытых состояний, но только в случае, если распределения наблюдаемых характеристик точно известны. Если же известен только параметрический класс таких распределений, то существует способ выбора наиболее подходящих параметров, называемый алгоритм Баума-Велша.

    Если интересно, требуйте продолжения…

    Similar posts

    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 25

      +9
      Если интересно, требуйте продолжения…


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

          пишите!
            –3
            У одного моего хорошего знакомого прекрасный девиз в скайпе: «Делай, что должен и будь, что будет!»
            Если кто-то напишет понятнее — это прекрасно, но это не повод не писать как можешь.
              –2
              «Делай, что должен и будь, что будет!»
              Первый раз услышал это от А.А. Фурсенко, экс-минобра, в передаче Познера.
                +4
                Это Марк Аврелий сказал. Только не «должен», а «до́лжно». А вообще, мне кажется некорректным употреблять фразы без знания контекста, в котором она прозвучала изначально.
                  0
                  Возможно, что и Марк Аврелий. Я не историк. В любом случае, вряд-ли он говорил эту фразу по русски (это я про «должен» и «должно»).
              +2
              В сфере образования и вообще (само)обучения наблюдается отчетливая тенденция перехода от системного обучения к поисковому. Люди все чаще вместо использования собственных накопленных знаний ищут чужие, но профильные и используют именно их. В этом контексте ценность Ваших статей будет со временем только расти.

              Пишите конечно. Подход далеко не тривиальный. В учебниках практически не описанный. Это намного ценнее «понятности».
                0
                В смысле, как человек может использовать собственные накопленные знания в поисках чего-то нового? :)
                  0
                  Чужие знания.

                  Хотя свои, кстати, тоже помогают, я один раз присутствовал (сказать, что я как-либо помог, было бы нескромно) в ситуации, когда человек сложил вместе задачу (тоже классификация), имеющийся подход (ручное написание правил) и сложные-непонятные методы линейной регрессии, о которых он слышал в универе.
                    +1
                    На эту тему вспомнился случай. Пришлось изучать один старый алгоритм классификации данных, который был реализован, судя по коду, биологом. Человек не зная того, сам заново открыл логистическую регрессию.
            0
            Интересная тема. А есть ли промышленные решения детекторов лжи с использованием ML? В принципе, навесить датчиков и обучить nn, наверное, труда особого не составляет.
              +2
              Думаю, все программные комплексы детекторов лжи имеют те или иные алгоритмы ML.
              Начиная от простейших supervised задач и кончая умным препроцессингом.
                0
                Нейронные сети все-таки это средство для создания моделей, а не сами модели, но тема сравнения различных подходов лично меня бы очень заинтересовала.
                  +1
                  Нейронные сети — лишь одна из моделей машинного обучения.
                  Обладающая тем недостатком, что построенные модели практически неинтерпретируемы.
                    +1
                    Я бы сказал, что это всего лишь один из недостатков, и далеко не самый страшный
                +2
                Хочу добавить, что алгоритм Витерби можно еще использовать для синхронизации нотной записи и реально исполняемой музыкантом мелодии (называется Score following), в клавиатурных тренажерах (если точное посимвольное совпадение не так важно), ну и других подобных задачах.

                Надеюсь от меня будет статья на эту тему в будущем.
                  0
                  Я интересом жду.
                    0
                    Использование Витерби в анализе звука очень распространено, но описания лучше, чем у Рабинера нигде не могу найти.
                    0
                    Несколько замечаний по статье:
                    1. Возможно сначала стоило бы рассмотреть СММ с дискретными распределениями вероятностей наблюдений, а уже затем перейти к непрерывным распределениям.
                    2. У вас имеется проблема с обозначениями.
                    С начала I — вектор вероятностей, того что система находится в состоянии i в момент времени 0, а потом I(x) – индикаторная функция. Здесь лучше выбрать другую букву. Кроме того нет пояснения, что такое «индикаторная функция».
                    3. Плохо описан алгоритм оценки параметров СММ. Он итерационный вообще-то (потому что это EM-алгоритм). В статье про это не сказано ни слова. Ну и каждую формулу оценки надо бы пояснить. Я, например, не понял, почему вы написали именно такие.
                      0
                      По пунктам:
                      1. Использование в модели плотности непрерывного распределения и использование конечной дискретной функции вероятности приводит к аналогичным функциям расчёта. Согласен, что забыл это уточнить в статье. По поводу того, что использую непрерывное распределение: все мои потуги придумать живой пример с дискретным распределением оказались тщетны. Было бы здорово, если бы кто-нибудь что-нибудь предложил (подбрасывание бракованной монеты или шулерской кости не в счёт).
                      2. Согласен, сейчас подправлю. По программистской привычке пользуюсь сигнатурой, а не именем.
                      3. Это не алгоритм оценки параметров, это алгоритм обучения. На самом деле я просто хотел сразу же ответить, откуда мы можем взять начальную модель. То что Вы называете алгоритмом оценки параметров, у меня упоминается как алгоритм Баума-Велша (Он как раз EM-алгоритм, которому все равно нужна 0-ая итерация). Я надеюсь, что оформлю про него отдельную статью.
                        +1
                        Это не алгоритм оценки параметров, это алгоритм обучения. На самом деле я просто хотел сразу же ответить, откуда мы можем взять начальную модель. То что Вы называете алгоритмом оценки параметров, у меня упоминается как алгоритм Баума-Велша (Он как раз EM-алгоритм, которому все равно нужна 0-ая итерация). Я надеюсь, что оформлю про него отдельную статью.


                        Т.е. я правильно понимаю, что тот набор формул описывает процесс задания начальных параметров СММ? Если так, то здесь уместнее употреблять слово «инициализация». Все же в литературе под обучением как правило понимается поиск на основе некоторой обучающей выборки таких параметров модели, которые бы удовлетворяли заданному критерию оптимальности.
                      +4
                      Пожалуй, добавлю кое что от себя для заинтересовавшихся. Алгоритм Витерби очень хорош, но у него есть одна маленькая проблема: ему требуется обратный проход, что делает несколько проблематичным обработку данных в реальном времени. Тем не менее, иногда (для некоторых моделей никогда, для некоторых часто) оптимальные пути состояний внезапно сходятся в одной точке. Если немного поразмыслить, то становится понятно, что из этой точки можно делать обратный проход, не дожидаясь конца последовательности, без ущерба для оптимальности. Существует эффективный алгоритм отслеживания оптимальных путей, который хранит их в специальной древесной структуре данных с минимальным оверхедом, реализующий этот принцип.

                      Кроме того, алгоритм Витерби вообще говоря является частным случаем более сложного алгоритма belief propagation (max-product / max-sum), который грубо говоря делает все то же самое, но не только для цепочек, а для произвольных деревьев. Алгоритмы этого семейства довольно хорошо исследованы и имеют хорошие приближенные параллельные варианты. Может показаться, что параллельность здесь вставляется очевидно — в прямой проход во время вычисления стоимости для следующего возможного состояния (можно паралеллить по этим состояниям), но, увы, состояний обычно достаточной мало, поэтому такое распараллеливание не приносит особой выгоды. Это все, правда, заслуживает отдельной статьи
                        0
                        Об belief propagation слышу впервые. Было бы очень интересно о нем узнать больше.
                        0
                        Интересные вы привели примеры. Несомненно хочется продолжения! Спасибо за материалы!
                        Интересует: обучение CRF со скрытыми переменными, beam поиск, foward — backward и желательно с примерами и побольше :)

                        Имеется ли на русском языке литература по графическим моделям?

                        Only users with full accounts can post comments. Log in, please.