-lie-detector-with-Hiden-markov-models-
реализовать детектор лжи, который по подрагиванию рук человека, определяет, говорит он правду или нет. Допустим, когда человек лжет, руки трясутся чуть больше. В модели скрытых цепей Маркова предполагается, что рассматриваемая система обладает следующими свойствами:
в каждый период времени система может находится в одном из конечного набора состояний; система случайно переходит из одного состояния в другое (возможно, в то же самое) и вероятность перехода зависит только от того состояния, в котором она находилась; в каждый момент времени система выдает одно значение наблюдаемой характеристики – случайную величину, зависящую только от текущего состояния системы.
Модель 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, то в случае пропусков в наблюдениях, все равно можно оценить наиболее вероятные скрытые состояния в эти моменты.
«Псевдокод» для алгоритма Витерби набросан ниже. Необходимо учесть, что все операции с векторами и матрицами поэлементные.