Прихована марковська модель

Матеріал з Вікіпедії — вільної енциклопедії.
(Перенаправлено з Прихована марківська модель)
Перейти до: навігація, пошук

Прихо́вана ма́рковська моде́ль, ПММ (англ. hidden Markov model, HMM) — це статистична марковська модель[en], у якій система, що моделюється, розглядається як марковський процес із неспостережуваними (прихованими) станами. ПММ може розглядатися як найпростіша динамічна баєсова мережа[en]. Математичний апарат для ПММ було розроблено Леонардом Баумом[en] зі співробітниками.[1][2][3][4][5] Він тісно пов'язаний з більш ранньою працею про оптимальну нелінійну проблему фільтрування (стохастичні процеси)[en] Руслана Стратоновича[en],[6] який першим описав послідовно-зворотній алгоритм[en].

У простіших марковських моделях[en] (таких як ланцюги Маркова) стан є безпосередньо видимим спостерігачеві, і тому ймовірності переходу станів є єдиними параметрами. У прихованій марковській моделі стан не є видимим безпосередньо, але вихід, залежний від стану, видимим є. Кожен стан має ймовірнісний розподіл усіх можливих вихідних значень. Тому послідовність символів, згенерована ПММ, дає якусь інформацію про послідовність станів. Зауважте, що прикметник «прихований» стосується послідовності станів, якою проходить модель, а не параметрів моделі; навіть якщо параметри моделі точно відомі, модель все одно є «прихованою».

Приховані марковські моделі відомі в першу чергу завдяки їхньому застосуванню в розпізнаванні часових шаблонів, таких як розпізнавання мовлення, рукописного введення, жестів[en],[7] морфологічної розмітки[en], мелодій для акомпонуваня,[8] часткових розрядів[en][9] та в біоінформатиці.

Приховані марковські моделі можуть розглядатися як узагальнення сумішевої моделі[en], де приховані змінні[en], що контролюють, яка складова суміші обиратиметься для кожного спостереження, пов'язані марковським процесом, а не є незалежними одна від одної. Нещодавно приховані марковські моделі було узагальнено до подвійних марковських моделей (англ. pairwise Markov models) та триплетних марковських моделей (англ. triplet Markov models), що дозволяє розглядати складніші структури даних[10][11] та моделювати нестаціонарні дані.[12][13]

Опис у термінах урн[ред.ред. код]

Малюнок 1. Ймовірнісні параметри прихованої марковської моделі (приклад)
X — стани
y — можливі спостереження
a — ймовірності переходів станів
b — ймовірності виходів

У своїй дискретній формі прихований марковський процес може бути представлено як узагальнення задачі про урни[en] (де кожен елемент з урни перед наступним кроком повертається до своєї урни).[14] Розгляньмо цей приклад. У невидимій для спостерігача кімнаті знаходиться джин. Кімната містить урни X1, X2, X3, … кожна з яких містить відому суміш куль, кожну кулю позначено як y1, y2, y3, … . Джин обирає урну в цій кімнаті, та витягує випадкову кулю з цієї урни. Потім він кладе цю кулю на конвеєрну стрічку, на якій спостерігач може бачити послідовність куль, але не послідовність урн, з яких їх було витягнуто. Джин має певну процедуру для обирання урн; вибір урни для n-тої кулі залежить лише від випадкового числа та вибору урни для (n − 1)-ї кулі. Вибір урни не залежить безпосередньо від урн, обраних перед цією однією попередньою урною; отже, це називається марковським процесом. Його може бути зображено верхньою частиною малюнку 1.

Самого марковського процесу не видно, видно лише послідовність позначених куль, тому цей механізм називатися «прихованим марковським процесом». Це проілюстровано нижньою частиною діаграми, зображеної на малюнку 1, де можна бачити, що кулі y1, y2, y3, y4 може бути витягнуто у кожному стані. Навіть якщо спостерігач знає склад урн, і щойно побачив на конвеєрній стрічці послідовність трьох куль, наприклад, y1, y2 та y3, він все ще не може бути впевненим з якої урни (тобто, в якому стані) джин витягнув третю кулю. Однак, спостерігач може опрацювати іншу інформацію, таку як ймовірність того, що третю кулю було витягнуто з кожної з урн.

Архітектура[ред.ред. код]

Діаграма нижче показує загальну архітектуру прикладу ПММ. Кожен овал представляє випадкову змінну, що може приймати будь-яке число значень. Випадкова змінна x(t) є прихованим станом у момент часу t (у моделі з діаграми вище x(t) ∈ { x1x2x3 }). Випадкова змінна y(t) є спостереженням у момент часу t (де y(t) ∈ { y1y2y3y4 }). Стрілки у цій діаграмі (що часто називають ґратковою діаграмою[en]) позначають ймовірнісні залежності.

З цієї діаграми видно, що умовний розподіл прихованої змінної x(t) у момент часу t, якщо дано значення прихованої змінної x в усі моменти часу, залежить лише від значення прихованої змінної x(t − 1): значення у момент часу t − 2 та раніші не мають впливу. Це називається марковською властивістю[en]. Так само, значення спостережуваної змінної y(t) залежить лише від значення прихованої змінної x(t) (у той же момент часу t).

У стандартному типі прихованої марковської моделі, що тут розглядається, простір станів прихованих змінних є дискретним, тоді як самі спостереження можуть бути або дискретними (що зазвичай генеруються з категоричного розподілу[en]) або неперервними (зазвичай з нормального розподілу). Параметри прихованої марковської моделі належать до двох типів, ймовірності переходів та ймовірності виходів. Ймовірності переходів керують тим, яким чином прихований стан у момент часу t обирається на підставі прихованого стану в момент часу t-1.

Вважається, що простір прихованих станів складається з одного з N можливих значень, змодельований як категоричний розподіл. (Див. розділ нижче про розширення для інших можливостей.) Це означає, що для кожного з N можливих станів, у якому прихована змінна може бути в момент часу t, є ймовірність переходу з цього стану до кожного з N можливих станів прихованої змінної в момент часу t+1, загалом N^2 ймовірностей переходів. Зауважте, що набір ймовірностей переходів для переходів з будь-якого заданого стану мусить в сумі дорівнювати 1. Отже, матриця N \times N ймовірностей переходів є марковською матрицею. Оскільки будь-яку одну ймовірність переходу може бути визначено, коли відомо решту, загальна кількість параметрів переходу складає N(N-1).

До того ж, для кожного з N можливих станів є набір ймовірностей виходів, що керує розподілом спостережуваної змінної у певний момент часу для заданого стану прихованої змінної в цей момент часу. Розмір цього набору залежить від природи спостережуваної змінної. Наприклад, якщо спостережувана змінна є дискретною з M можливих значень, що регулюються категоричним розподілом[en], то буде M-1 окремих параметрів, загальним числом N(M-1) параметрів виходу для всіх прихованих станів. З іншого боку, якщо спостережувана змінна є M-мірним вектором з розподілом відповідно до довільного багатовимірного нормального розподілу, то буде M параметрів, що контролюють середні, та M(M+1)/2 параметрів, що контролюють коваріаційну матрицю, загальним числом N(M + \frac{M(M+1)}{2}) = NM(M+3)/2 = O(NM^2) параметрів виходу. (В такому випадку, якщо значення M не є малим, може бути зручніше обмежити природу коваріацій між індивідуальними елементами вектору спостережень, наприклад, припустивши, що елементи не залежать один від одного, або, менш обмежуюче, не залежать від всіх, крім фіксованого числа сусідніх елементів.)

Часова еволюція прихованої марковської моделі

Отримання висновків[ред.ред. код]

Ймовірності переходів станів та виходів ПММ на верхній частині діаграми позначено непрозорістю ліній. Маючи це, ми проспостерігали вихідну послідовність у нижній частині діаграми, нас може цікавити найбільш правдоподібна послідовність станів, що могла це виробити. На підстави представлених на діаграмі стрілок, кандидатами є наступні послідовності станів:
5 3 2 5 3 2
4 3 2 5 3 2
3 1 2 5 3 2
Ми можемо знайти найбільш правдоподібну послідовність, обчисливши спільну ймовірність послідовностей станів та спостережень для кожного випадку (просто перемноживши значення ймовірностей, що відповідають непрозорості задіяних стрілок). Загалом, цей тип задач (тобто, знаходження найбільш правдоподібного пояснення спостережуваної послідовності) може ефективно розв'язуватися алгоритмом Вітербі.

З прихованими марковськими моделями пов'язані деякі задачі отримання висновків, як окреслено нижче.

Ймовірність спостережуваної послідовності[ред.ред. код]

Задача полягає в обчисленні, при заданих параметрах моделі, ймовірності певної вихідної послідовності. Це вимагає сумування за всіма можливими послідовностями станів:

Ймовірність спостереження послідовності

Y=y(0), y(1),\dots,y(L-1)\,

довжиною L задається формулою

P(Y)=\sum_{X}P(Y\mid X)P(X),\,

де сума пробігає усіма можливими послідовностями прихованих вузлів

X=x(0), x(1), \dots, x(L-1).\,

При застосуванні принципу динамічного програмування ця задача також може розв'язуватися ефективно з використанням послідовного алгоритму[en].

Імовірність прихованих змінних[ред.ред. код]

Ряд пов'язаних задач про ймовірність однієї або більше прихованих змінних при заданих параметрах моделі та послідовності спостережень y(1),\dots,y(t).

Фільтрування[ред.ред. код]

Задача полягає в обчисленні, при заданих параметрах моделі та послідовності спостережень, розподілу над прихованими станами останньої прихованої змінної в кінці послідовності, тобто в обчисленні P(x(t)\ |\ y(1),\dots,y(t)). Ця задача зазвичай застосовується, коли послідовність прихованих змінних розглядається як базові стані, якими проходить процес у послідовності моментів часу, із відповідними спостереженнями у кожен момент часу. Тоді природно спитати про стан процесу в кінці.

Ця задача може ефективно розв'язуватися із застосуванням послідовного алгоритму[en].

Згладжування[ред.ред. код]

Ця задача схожа на фільтрування, але в ній питається про розподіл прихованої змінної десь у середині послідовності, тобто, потрібно обчислити P(x(k)\ |\ y(1), \dots, y(t)) для деякого k < t. З огляду на описане вище, це може розглядатися як розподіл ймовірностей над прихованими станами для моменту часу k у минулому, по відношенню до часу t.

Ефективним методом обчислення згладжених значень для всіх змінних прихованого стану є послідовно-зворотній алгоритм[en].

Найбільш правдоподібне пояснення[ред.ред. код]

У цій задачі, на відміну від двох попередніх, питається про спільну ймовірність[en] всієї послідовності прихованих станів, що згенерувала певну послідовність спостережень (див. ілюстрацію праворуч). Ця задача, як правило, можна застосовувати тоді, коли ПММ застосовується до різних типів проблем з тих, для яких застосовуються задачі фільтрування та згладжування. Прикладом є морфологічна розмітка[en], де приховані стани представляють гадані частини мови, що відповідають спостережуваній послідовності слів. У цьому випадку інтерес становить повна послідовність частин мови, а не просто частина мови для одного слова, що її обчислювали би фільтрування чи згладжування.

Задача вимагає знаходження максимуму над усіма можливими послідовностями станів, і може ефективно розв'язуватися алгоритмом Вітербі.

Статистична значимість[ред.ред. код]

Для деяких із наведених вище задач може бути цікаво спитати про статистичну значимість[en]. Якою є ймовірність того, що послідовність, витягнута з якогось нульового розподілу[en], матиме ПММ-ймовірність (у випадку послідовного алгоритму) або максимальну ймовірність послідовності станів (у випадку алгоритму Вітербі), не меншу за таку ймовірність певної послідовності?[15] Коли ПММ використовується для оцінювання доречності гіпотези для певної послідовності виходу, статистична значимість показує рівень похибки першого роду, пов'язаною зі слабкістю можливості спростування цієї гіпотези для цієї послідовності виходу.

Конкретний приклад[ред.ред. код]

Розгляньмо двох приятелів, Алісу та Боба, які живуть далеко один від одного, і які щодня спілкуються телефоном про те, що вони робили цього дня. Боб цікавиться лише трьома заняттями: гулянням в парку, купівлями та прибиранням своєї квартири. Вибір, чим зайнятися, визначається виключно погодою в цей день. Аліса не має чіткої інформації про погоду в місці проживання Боба, але вона знає загальні тенденції. На підставі того, що Боб каже їй про те, що він робив кожного дня, Аліса намагається вгадати, якою, швидше за все, була погода.

Аліса вважає, що погода діє, як дискретний марковський ланцюг. Є два стани, «Сонячно» та «Дощ», але вона не може спостерігати їх безпосередньо, тобто, вони приховані від неї. Кожного дня є певний шанс, що Боб займатиметься одним із наступних занять, в залежності від погоди: «гуляння», «купівлі» та «прибирання». Оскільки Боб каже Алісі про свої заняття, вони є спостереженнями. Вся система в цілому є тим же, що й прихована марковська модель (ПММ).

Аліса знає загальні тенденції погоди в тій місцевості, і що Боб любить робити в середньому. Іншими словами, параметри ПММ відомі. Їх можна представити мовою програмування Python наступним чином:

# стани
states = ('Дощ', 'Сонячно')
 
# спостереження
observations = ('гуляння', 'купівлі', 'прибирання')
 
# початкова ймовірність
start_probability = {'Дощ': 0.6, 'Сонячно': 0.4}
 
# ймовірність переходу
transition_probability = {
   'Дощ' : {'Дощ': 0.7, 'Сонячно': 0.3},
   'Сонячно' : {'Дощ': 0.4, 'Сонячно': 0.6},
   }
 
# ймовірність виходу
emission_probability = {
   'Дощ' : {'гуляння': 0.1, 'купівлі': 0.4, 'прибирання': 0.5},
   'Сонячно' : {'гуляння': 0.6, 'купівлі': 0.3, 'прибирання': 0.1},
   }

У цьому фрагменті коду start_probability представляє думку Аліси про те, в якому стані знаходиться ПММ, коли Боб телефонує їй вперше (все, що вона знає, це те, що там зазвичай дощить). Конкретний розподіл ймовірності, що тут використовується, не є рівноважним, що є (при заданих ймовірностях переходів) приблизно {'Дощ': 0.57, 'Сонячно': 0.43}. transition_probability представляє зміну погоди в основному марковському ланцюгові. У цьому прикладі є лише 30% шансів, що завтра буде сонячно, якщо сьогодні дощить. emission_probability представляє, наскільки ймовірно Боб займатиметься певною справою за кожної погоди. Якщо дощить, є ймовірність 50%, що він прибиратиме у квартирі; якщо сонячно, є ймовірність 60%, що він гуляє надворі.

Графічне представлення даної ПММ

Подібний приклад розбирається далі на сторінці Viterbi algorithm.

Математичний опис[ред.ред. код]

Загальний опис[ред.ред. код]

Базову (не баєсову) приховану марковську модель може бути описано таким чином:

    N   =   кількість станів
    T   =   кількість спостережень
    \theta_{i=1 \dots N}   =   параметр виходу для спостереження, пов'язаного зі станом i
    \phi_{i=1 \dots N, j=1 \dots N}   =   ймовірність переходу зі стану i до стану j
    \boldsymbol\phi_{i=1 \dots N}   =   N-мірний вектор, що складається з \phi_{i,1 \dots N}; в сумі має дорівнювати 1
    x_{t=1 \dots T}   =   стан спостереження в момент часу t
    y_{t=1 \dots T}   =   спостереження в момент часу t
    F(y|\theta)   =   розподіл ймовірностей спостережень, параметризований за \theta
    x_{t=2 \dots T}   \sim   \operatorname{Categorical}(\boldsymbol\phi_{x_{t-1}})
    y_{t=1 \dots T}   \sim   F(\theta_{x_t})

Зауважте що в наведеній вище моделі (а також і в наведеній нижче), апріорний розподіл початкового стану x_1 не вказано. Типові моделі навчання відповідають припусканню дискретного рівномірного розподілу можливих станів (тобто, припускається відсутність певного апріорного розподілу).

У баєсовому варіанті всі параметри пов'язано з випадковими змінними, а саме:

    N,T   =   як вище
    \theta_{i=1 \dots N}, \phi_{i=1 \dots N, j=1 \dots N}, \boldsymbol\phi_{i=1 \dots N}   =   як вище
    x_{t=1 \dots T}, y_{t=1 \dots T}, F(y|\theta)   =   як вище
    \alpha   =   спільний гіперпараметр для параметрів виходу
    \beta   =   спільний гіперпараметр для параметрів переходу
    H(\theta|\alpha)   =   апріорний розподіл ймовірності параметрів виходу, параметризований за \alpha
    \theta_{i=1 \dots N}   \sim   H(\alpha)
    \boldsymbol\phi_{i=1 \dots N}   \sim   \operatorname{Symmetric-Dirichlet}_N(\beta)
    x_{t=2 \dots T}   \sim   \operatorname{Categorical}(\boldsymbol\phi_{x_{t-1}})
    y_{t=1 \dots T}   \sim   F(\theta_{x_t})

Ці описи використовують F та H для опису довільних розподілів над спостереженнями та параметрами відповідно. Зазвичай H буде спряженим апріорним розподілом[en] F. Двома найпоширенішими варіантами F є нормальний та категоричний[en] розподіли; див. нижче.

У порівнянні з простою сумішевою моделлю[ред.ред. код]

Як зазначено вище, розподіл кожного спостереження у прихованій марковській моделі є сумішевою щільністю[en], де стани відповідають складовим суміші. Корисно порівняти наведені вище описи ПММ з відповідними характеристиками сумішевої моделі[en], використовуючи той самий запис.

Небаєсова сумішева модель:

    N   =   кількість складових суміші
    T   =   кількість спостережень
    \theta_{i=1 \dots N}   =   параметр розподілу спостереження, пов'язаний зі складовою i
    \phi_{i=1 \dots N}   =   сумішева вага, тобто, апріорна ймовірність складової i
    \boldsymbol\phi   =   N-мірний вектор, що складається з \phi_{1 \dots N}; в сумі має дорівнювати 1
    x_{t=1 \dots T}   =   складова спостереження t
    y_{t=1 \dots T}   =   спостереження t
    F(y|\theta)   =   розподіл ймовірності спостереження, параметризований за \theta
    x_{t=1 \dots T}   \sim   \operatorname{Categorical}(\boldsymbol\phi)
    y_{t=1 \dots T}   \sim   F(\theta_{x_t})

Баєсова сумішева модель:

    N,T   =   як вище
    \theta_{i=1 \dots N}, \phi_{i=1 \dots N}, \boldsymbol\phi   =   як вище
    x_{t=1 \dots T}, y_{t=1 \dots T}, F(y|\theta)   =   як вище
    \alpha   =   спільний гіперпараметр для параметрів складових
    \beta   =   спільний гіперпараметр для сумішевих ваг
    H(\theta|\alpha)   =   апріорний розподіл ймовірності параметрів складових, параметризований за \alpha
    \theta_{i=1 \dots N}   \sim   H(\alpha)
    \boldsymbol\phi   \sim   \operatorname{Symmetric-Dirichlet}_N(\beta)
    x_{t=1 \dots T}   \sim   \operatorname{Categorical}(\boldsymbol\phi)
    y_{t=1 \dots T}   \sim   F(\theta_{x_t})

Приклади[ред.ред. код]

Наступні математичні описи повністю розписано та пояснено для полегшення втілення.

Типова небаєсова ПММ з нормальним розподілом спостережень виглядає так:

    N   =   кількість станів
    T   =   кількість спостережень
    \phi_{i=1 \dots N, j=1 \dots N}   =   ймовірність переходу зі стану i до стану j
    \boldsymbol\phi_{i=1 \dots N}   =   N-мірний вектор, що складається з \phi_{i,1 \dots N}; в сумі має дорівнювати 1
    \mu_{i=1 \dots N}   =   середнє спостережень, пов'язане зі станом i
    \sigma^2_{i=1 \dots N}   =   дисперсія спостережень, пов'язана зі станом i
    x_{t=1 \dots T}   =   стан спостереження у момент часу t
    y_{t=1 \dots T}   =   спостереження у момент часу t
    x_{t=2 \dots T}   \sim   \operatorname{Categorical}(\boldsymbol\phi_{x_{t-1}})
    y_{t=1 \dots T}   \sim   \mathcal{N}(\mu_{x_t}, \sigma_{x_t}^2)

Типова баєсова ПММ з нормальним розподілом спостережень виглядає так:

    N   =   кількість станів
    T   =   кількість спостережень
    \phi_{i=1 \dots N, j=1 \dots N}   =   ймовірність переходу зі стану i до стану j
    \boldsymbol\phi_{i=1 \dots N}   =   N-мірний вектор, що складається з \phi_{i,1 \dots N}; в сумі має дорівнювати 1
    \mu_{i=1 \dots N}   =   середнє спостережень, пов'язане зі станом i
    \sigma^2_{i=1 \dots N}   =   дисперсія спостережень, пов'язана зі станом i
    x_{t=1 \dots T}   =   стан спостереження у момент часу t
    y_{t=1 \dots T}   =   спостереження у момент часу t
    \beta   =   гіперпараметр концентрації, що контролює щільність матриці переходу
    \mu_0, \lambda   =   спільні гіперпараметри для середніх для кожного стану
    \nu, \sigma_0^2   =   спільні гіперпараметри для дисперсій для кожного стану
    \boldsymbol\phi_{i=1 \dots N}   \sim   \operatorname{Symmetric-Dirichlet}_N(\beta)
    x_{t=2 \dots T}   \sim   \operatorname{Categorical}(\boldsymbol\phi_{x_{t-1}})
    \mu_{i=1 \dots N}   \sim   \mathcal{N}(\mu_0, \lambda\sigma_i^2)
    \sigma_{i=1 \dots N}^2   \sim   \operatorname{Inverse-Gamma}(\nu, \sigma_0^2)
    y_{t=1  \dots T}   \sim   \mathcal{N}(\mu_{x_t}, \sigma_{x_t}^2)

Типова небаєсова ПММ з категоричними спостереженнями виглядає так:

    N   =   кількість станів
    T   =   кількість спостережень
    \phi_{i=1 \dots N, j=1 \dots N}   =   ймовірність переходу зі стану i до стану j
    \boldsymbol\phi_{i=1 \dots N}   =   N-мірний вектор, що складається з \phi_{i,1 \dots N}; в сумі має дорівнювати 1
    V   =   розмірність категоричних спостережень, наприклад, розмір словника
    \theta_{i=1 \dots N, j=1 \dots V}   =   ймовірність спостереження j-того елементу в стані i
    \boldsymbol\theta_{i=1 \dots N}   =   V-мірний вектор, що складається з \theta_{i,1 \dots V}; в сумі має дорівнювати 1
    x_{t=1 \dots T}   =   стан спостереження у момент часу t
    y_{t=1 \dots T}   =   спостереження у момент часу t
    x_{t=2 \dots T}   \sim   \operatorname{Categorical}(\boldsymbol\phi_{x_{t-1}})
    y_{t=1 \dots T}   \sim   \text{Categorical}(\boldsymbol\theta_{x_t})

Типова баєсова ПММ з категоричними спостереженнями виглядає так:

    N   =   кількість станів
    T   =   кількість спостережень
    \phi_{i=1 \dots N, j=1 \dots N}   =   ймовірність переходу зі стану i до стану j
    \boldsymbol\phi_{i=1 \dots N}   =   N-мірний вектор, що складається з \phi_{i,1 \dots N}; в сумі має дорівнювати 1
    V   =   розмірність категоричних спостережень, наприклад, розмір словника
    \theta_{i=1 \dots N, j=1 \dots V}   =   ймовірність спостереження j-того елементу в стані i
    \boldsymbol\theta_{i=1 \dots N}   =   V-мірний вектор, що складається з \theta_{i,1 \dots V}; в сумі має дорівнювати 1
    x_{t=1 \dots T}   =   стан спостереження у момент часу t
    y_{t=1 \dots T}   =   спостереження у момент часу t
    \alpha   =   спільний гіперпараметр концентрації \boldsymbol\theta для кожного стану
    \beta   =   гіперпараметр концентрації, що контролює щільність матриці переходу
    \boldsymbol\phi_{i=1 \dots N}   \sim   \operatorname{Symmetric-Dirichlet}_N(\beta)
    \boldsymbol\theta_{1 \dots V}   \sim   \text{Symmetric-Dirichlet}_V(\alpha)
    x_{t=2 \dots T}   \sim   \operatorname{Categorical}(\boldsymbol\phi_{x_{t-1}})
    y_{t=1 \dots T}   \sim   \operatorname{Categorical}(\boldsymbol\theta_{x_t})

Зауважте, що в наведених вище баєсових описах \beta (параметр концентрації[en]) контролює щільність матриці переходу. Тобто, при високому значенні \beta (значно більше 1) ймовірності, що контролюють перехід з певного конкретного стану, будуть схожими між собою, що означає, що буде суттєва ймовірність переходу до будь-якого іншого стану. Іншими словами, шлях, пройдений ланцюгом Маркова прихованими станами, буде сильно випадковим. При низькому значенні \beta (значно менше 1) лише мала кількість можливих переходів з певного заданого стану матиме значну ймовірність, що означає, що шлях, пройдений прихованими станами, буде до деякої міри передбачуваним.

Дворівнева баєсова ПММ[ред.ред. код]

Альтернативою двох до наведених вище баєсових прикладів буде додавання до матриці переходу додаткового рівня апріорних параметрів. Тобто, замінити рядки

    \beta   =   гіперпараметр концентрації, що контролює щільність матриці переходу
    \boldsymbol\phi_{i=1 \dots N}   \sim   \operatorname{Symmetric-Dirichlet}_N(\beta)

наступними:

    \gamma   =   гіперпараметр концентрації, що контролює, як багато станів є притаманно ймовірними
    \beta   =   гіперпараметр концентрації, що контролює щільність матриці переходу
    \boldsymbol\eta   =   N-мірний вектор ймовірностей, що визначає притаманну ймовірність заданого стану
    \boldsymbol\eta   \sim   \operatorname{Symmetric-Dirichlet}_N(\gamma)
    \boldsymbol\phi_{i=1 \dots N}   \sim   \operatorname{Dirichlet}_N(\beta N \boldsymbol\eta)

Це означає наступне:

  1. \boldsymbol\eta є розподілом ймовірностей станів, що визначає, які стани є притаманно ймовірними. Що більшою є ймовірність заданого стану в цьому векторі, то більшою є ймовірність переходу до цього стану (незалежно від початкового стану).
  2. \gamma контролює щільність \boldsymbol\eta. Значення, значно більші за 1, призводять до такого вектору щільності, в якому всі стани мають схожі апріорні ймовірності[en]. Значення, значно менші за 1, призводять до розрідженого вектору, де лише деякі стани притаманно ймовірні (мають апріорні ймовірності значно більше 0).
  3. \beta контролює щільність матриці переходу, або, конкретніше, щільність N різних векторів ймовірності \boldsymbol\phi_{i=1 \dots N}, що визначають ймовірність переходів зі стану i до будь-якого іншого стану.

Уявіть, що значення \beta є значно більшим за 1. Тоді різні вектори \boldsymbol\phi будуть щільними, тобто, масу ймовірності буде розкидано досить порівну між всіма станами. Однак, в тій мірі, в якій цю масу розкидано нерівномірно, \boldsymbol\eta контролює, які стани ймовірніше отримають більше маси за інші.

Тепер замість цього уявіть, що \beta є значно меншим за 1. Це зробить вектори \boldsymbol\phi розрідженими, тобто, майже всю масу ймовірності розподілено між невеликою кількістю станів, а щодо решти, то перехід до таких станів буде вельми малоймовірним. Зверніть увагу, що є різні вектори \boldsymbol\phi для кожного з початкових станів, і отже, навіть якщо всі вектори є розрідженими, різні вектори можуть перерозподіляти масу до різних кінцевих станів. Однак, для всіх векторів \boldsymbol\eta контролює, які кінцеві стани ймовірніше отримають призначення маси собі. Наприклад, якщо \beta дорівнює 0.1, то кожен \boldsymbol\phi буде розрідженим, і, для будь-якого заданого початкового стану i множина станів \mathbf{J}_i, переходи до яких будуть ймовірними, буде дуже маленькою, зазвичай з одним або двома елементами. Тепер, якщо ймовірності в \boldsymbol\eta є всі однаковими (або, рівноцінно, використовується одна з наведених вище моделей без \boldsymbol\eta), то для різних i будуть різні стани у відповідних \mathbf{J}_i, так що всі стани матимуть однакову ймовірність опинитися у довільно взятому \mathbf{J}_i. З іншого боку, якщо значення у \boldsymbol\eta є незбалансованими, так що один стан має значно більшу ймовірність за інші, то майже всі \mathbf{J}_i міститимуть цей стан; отже, незалежно від початкового стану, переходи майже завжди вестимуть до цього заданого стану.

Отже, така дворівнева модель, якщо щойно описано, дає можливість незалежного контролю над (1) загальною щільністю матриці переходів та (2) щільністю станів, переходи до яких є ймовірними (тобто, щільністю апріорного розподілу станів у будь-якій окремій прихованій змінній x_i). В обох випадках це робиться із збереженням припущення про невідомість того, які конкретні стани є ймовірнішими за інші. Якщо є бажання ввести цю інформацію до моделі, то можна безпосередньо задати вектор ймовірності \boldsymbol\eta; або, якщо немає такої впевненості про ці відносні ймовірності, в якості апріорного розподілу над \boldsymbol\eta може бути використано несиметричний розподіл Діріхле. Тобто, замість використання симетричного розподілу Діріхле з єдиним параметром \gamma (або, рівноцінно, звичайного Діріхле з вектором, чиї значення всі дорівнюють \gamma), використовувати звичайний Діріхле зі значеннями, що є по-різному більшими або меншими за \gamma, відповідно до того, якому станові віддається більше або менше переваги.

Застосування[ред.ред. код]

ПММ можуть застосовуватися у багатьох сферах, де метою є виявлення послідовності даних, що не є безпосередньо спостережуваною (але інші дані, що залежить від цієї послідовності, є). До застосування входять:

Історія[ред.ред. код]

Послідовну та зворотню рекурсії, що використовуються у ПММ, так само як і розрахунки маргінальних згладжувальних ймовірностей, було описано вперше Русланом Стратоновичем[en] у 1960 році[6] (сторінки 160–162) та у пізніх 1950-х у його працях російською. Приховані марковські моделі було пізніше описано в низці статистичних робіт Леонарда Баума та інших авторів у другій половині 1960-х. Одним з перших застосувань ПММ було розпізнавання мовлення, починаючи з середини 1970-х.[20][21][22][23]

У другій половині 1980-х ПММ почали застосовуватися до аналізу біологічних послідовностей,[24] зокрема, ДНК. Відтоді у сфері біоінформатики вони стали всюдисущими.[25]

Типи[ред.ред. код]

Приховані марковські моделі можуть моделювати складні марковські процеси, де стани видають спостереження відповідно до якогось розподілу ймовірностей. Одним з прикладів такого розподілу є нормальний розподіл, у такій прихованій марковській моделі вихід станів представлено нормальним розподілом.

Крім того, вони можуть представляти ще складнішу поведінку, коли вихід станів представлено сумішшю двох або більше нормальних розподілів, у такому випадку ймовірність генерації спостереження є добутком ймовірності спочатку вибору одного з нормальних розподілів, і ймовірності генерації цього спостереження з цього нормального розподілу.

Розширення[ред.ред. код]

У розглянутих вище прихованих марковських моделям простір станів прихованих змінних є дискретним, тоді як самі спостереження можуть бути або дискретними (зазвичай згенерованими з категоричного розподілу[en]), або неперервним (зазвичай з нормального розподілу). Приховані марковські моделі також бути узагальнено, щоби дозволяти неперервні простори станів. Прикладами таких моделей є ті, де марковський процес над прихованими змінними є лінійною динамічною системою[en] з лінійним зв'язком між пов'язаними змінними, і де всі приховані й спостережувані змінні слідують нормальному розподілу. У простих випадках, таких як щойно зазначені лінійні динамічні системи, точне виведення є легкорозв'язним (у цьому випадку з використанням фільтру Калмана); однак, у загальному випадку точне виведення в ПММ з неперервними прихованими змінними є нездійсненним, і можуть застосовуватися наближені методи, такі як розширений фільтр Калмана, або частинковий фільтр[en].

Приховані марковські моделі є генеративними моделями[en], у яких моделюється спільний розподіл[en] спостережень та прихованих станів, або, еквівалентно, як апріорний розподіл[en] прихованих станів (ймовірності переходу), так і умовний розподіл спостережень для заданих станів (ймовірності виходу). Наведені вище алгоритми неявно припускають рівномірний апріорний розподіл ймовірностей переходу. Однак, також можливо створити приховані марковські моделі з іншими типами апріорних розподілів. Очевидним кандидатом, при категоричному розподілі ймовірностей переходу, є розподіл Діріхле, що є спряженим апріорним[en] розподілом категоричного розподілу. Зазвичай обирається симетричний розподіл Діріхле, що відображає незнання того, які стани є притаманно ймовірнішими за інші. Єдиний параметр цього розподілу (що називається параметром концентрації) контролює відносну щільність або розрідженість отримуваної матриці переходу. Вибір 1 породжує рівномірний розподіл. Значення, більші за 1, породжують щільну матрицю, в якій імовірності переходів між парами станів, ймовірно, будуть майже рівними. Значення, менші за 1, породжують розріджену матрицю, в якій для кожного заданого початкового стану лише невелика кількість кінцевих станів має не незначні ймовірності переходу. Також можливе використання дворівневого апріорного розподілу Діріхле, в якому один розподіл Діріхле (верхній розподіл) керує параметрами іншого розподілу Діріхле (нижнього розподілу), який, у свою чергу, керує ймовірностями переходу. Верхній розподіл керує загальним розподілом станів, визначаючи, наскільки ймовірно для кожного стану, що він трапиться; його концентраційний параметр визначає щільність або розрідженість станів. Такий дворівневий апріорний розподіл, де обидва концентраційні параметри встановлено на породження розріджених розподілів, можуть бути корисними, наприклад, у морфологічній розмітці[en] без вчителя[ru], де деякі частини мови трапляються значно частіше за інші; алгоритми навчання, що припускають рівномірний апріорний розподіл, загалом погано працюють з цією задачею. Параметри моделей такого роду, з нерівномірними апріорними розподілами, можуть отримуватися семплуванням за Ґіббсом[en] або розширеними версіями алгоритму очікування-максимізації[en].

Розширення описаних вище прихованих марковських моделей з апріорними Діріхле використовує процес Діріхле[en] замість розподілу Діріхле. Цей тип моделей дозволяє невідому, і потенційно нескінченну кількість станів. Загальноприйнято використовувати дворівневий процес Діріхле, подібно до описаної вище моделі з двома рівнями розподілів Діріхле. Така модель називається прихованою марковською моделлю з ієрархічним процесом Діріхле (англ. hierarchical Dirichlet process hidden Markov model, HDP-HMM). Початково її було описано під назвою «Нескінченна прихована марковська модель»[26] і було формалізовано далі у [27].

Інший тип розширень використовує дискримінативну модель[en] замість генеративної моделі[en] стандартної ПММ. Цей тип моделі моделює безпосередньо умовний розподіл прихованих станів при заданих спостереженнях, замість моделювання спільного розподілу. Прикладом цієї моделі є так звана марковська модель максимальної ентропії[en] (англ. maximum entropy Markov model, MEMM), що моделює умовний розподіл станів за допомогою логістичної регресії (відома також як «модель максимальної ентропії[en]»). Перевагою цього типу моделі є те, що вона дозволяє моделювати довільні властивості (тобто, функції) спостережень, що дозволяє введення до моделі предметно-орієнтованого знання задачі, що є під руками. Моделі цього роду не обмежені моделюванням прямих залежностей між прихованими станами та пов'язаними з ними спостереженнями; швидше, для визначення значення прихованого стану до процесу можуть включатися властивості близьких спостережень, комбінацій пов'язаного спостереження і близьких спостережень, або факти довільних спостережень на будь-якій відстані від заданого прихованого стану. До того ж, не потрібно, щоби ці властивості були статистично незалежними одна від одної, як було би у випадку, якби такі властивості використовувалися у генеративній моделі. Насамкінець, можуть використовуватися довільні властивості над парами суміжних прихованих станів, а не лише ймовірності переходів. Недоліками таких моделей є: (1) Типи апріорних розподілів, що може бути встановлено над прихованими станами, суворо обмежено; (2) Неможливо передрікти ймовірність побачити певне спостереження. Це друге обмеження часто не є проблемою на практиці, оскільки багато звичайних застосувань ПММ не вимагають таких передбачувальних можливостей.

Варіантом описаної вище дискримінативної моделі є нерозгалужена умовна мережа[en] (англ. linear-chain conditional random field). Вона використовує неспрямовану графічну модель (відому як марковська мережа[en]) замість спрямованих графічних моделей марковської моделі максимальної ентропії, та подібних моделей. Перевагою цього типу моделей є те, що він не страждає від так званої проблеми міткової схильності (англ. label bias) марковських моделей максимальної ентропії, і тому може робити точніші передбачення. Недоліком є те, що навчання може бути повільнішим, ніж в марковських моделях максимальної ентропії.

Ще одним варіантом є факторіальна прихована марковська модель (англ. factorial hidden Markov model), що дозволяє єдиному спостереженню бути обумовленим відповідними прихованими змінними набору K незалежних марковських ланцюгів, а не єдиного марковського ланцюга. Це еквівалентно єдиній ПММ з N^K станів (за припущення, що кожен ланцюг має N станів), і тому навчання такої моделі є складним: для послідовності довжиною T прямолінійний алгоритм Вітербі має складність O(N^{2K} \, T). Для знаходження точного розв'язку може використовуватися алгоритм дерева з'єднань (англ. junction tree algorithm), але це призводить до складності O(N^{K+1} \, K \, T). На практиці можуть застосовуватися приблизні методи, такі як варіаційні підходи.[28]

Всі наведені вище моделі може бути розширено, щоби дозволити віддаленіші залежності серед прихованих станів, наприклад, дозволяючи заданому станові бути залежним від двох або трьох станів, а не від єдиного попереднього стану; тобто, ймовірності переходу розширюються для охоплення наборів трьох або чотирьох суміжних станів (або, в загальному випадку, K суміжних станів). Недоліком таких моделей є те, що алгоритми динамічного програмування для їх навчання мають час виконання O(N^K \, T) для K суміжних станів та T спостережень (тобто, маркового ланцюга довжиною T).

Іншим недавнім розширенням є трійкова маркова модель (англ. triplet Markov model),[29] у якій для моделювання деяких специфічностей даних додається допоміжний базовий процес. Було запропоновано багато варіантів цієї моделі. Варто також мати на увазі цікавий зв'язок, що встановився між теорією очевидності (англ. theory of evidence) та трійковими марковськими моделями,[10] який дозволяє вплавляти дані до марковського контексту[11] та моделювати нестаціонарні дані.[12][13]

Див. також[ред.ред. код]

Примітки[ред.ред. код]

  1. Baum L. E., Petrie T. Statistical Inference for Probabilistic Functions of Finite State Markov Chains // The Annals of Mathematical Statistics. — 37 (1966) (6) С. 1554–1563. DOI:10.1214/aoms/1177699147. Процитовано 28 November 2011. (англ.)
  2. Baum L. E., Eagon J. A. An inequality with applications to statistical estimation for probabilistic functions of Markov processes and to a model for ecology // Bulletin of the American Mathematical Society. — 73 (1967) (3) С. 360. DOI:10.1090/S0002-9904-1967-11751-8. (англ.)
  3. Baum L. E., Sell G. R. Growth transformations for functions on manifolds // Pacific Journal of Mathematics. — 27 (1968) (2) С. 211–227. Процитовано 28 November 2011. (англ.)
  4. Baum L. E., Petrie T., Soules G., Weiss N. A Maximization Technique Occurring in the Statistical Analysis of Probabilistic Functions of Markov Chains // The Annals of Mathematical Statistics. — 41 (1970) С. 164. DOI:10.1214/aoms/1177697196. (англ.)
  5. Baum L.E. An Inequality and Associated Maximization Technique in Statistical Estimation of Probabilistic Functions of a Markov Process // Inequalities. — 3 (1972) С. 1–8. (англ.)
  6. а б Stratonovich, R.L. Conditional Markov Processes // Theory of Probability and its Applications. — 5 (1960) С. 156–178. (англ.)
  7. Thad Starner, Alex Pentland. Real-Time American Sign Language Visual Recognition From Video Using Hidden Markov Models. Master's Thesis, MIT, Feb 1995, Program in Media Arts (англ.)
  8. B. Pardo and W. Birmingham. Modeling Form for On-line Following of Musical Performances. AAAI-05 Proc., July 2005. (англ.)
  9. Satish L, Gururaj BI (April 2003). «Use of hidden Markov models for partial discharge pattern classification». IEEE Transactions on Dielectrics and Electrical Insulation. (англ.)
  10. а б Pr. Pieczynski, W. Pieczynski, Multisensor triplet Markov chains and theory of evidence, International Journal of Approximate Reasoning, Vol. 45, No. 1, pp. 1-16, 2007. (англ.)
  11. а б Boudaren et al., M. Y. Boudaren, E. Monfrini, W. Pieczynski, and A. Aissani, Dempster-Shafer fusion of multisensor signals in nonstationary Markovian context, EURASIP Journal on Advances in Signal Processing, No. 134, 2012. (англ.)
  12. а б Lanchantin et al., P. Lanchantin and W. Pieczynski, Unsupervised restoration of hidden non stationary Markov chain using evidential priors, IEEE Trans. on Signal Processing, Vol. 53, No. 8, pp. 3091-3098, 2005. (англ.)
  13. а б Boudaren et al., M. Y. Boudaren, E. Monfrini, and W. Pieczynski, Unsupervised segmentation of random discrete data hidden with switching noise distributions, IEEE Signal Processing Letters, Vol. 19, No. 10, pp. 619-622, October 2012. (англ.)
  14. Lawrence Rabiner[en] A tutorial on Hidden Markov Models and selected applications in speech recognition // Proceedings of the IEEE. — 77 (лютий 1989) (2) С. 257-286. DOI:10.1109/5.18626. [1] (англ.)
  15. Newberg L. Error statistics of hidden Markov model and hidden Boltzmann model results // BMC Bioinformatics. — 10 (2009) С. 212. DOI:10.1186/1471-2105-10-212. PMID 19589158. (англ.)
  16. Piyathilaka, L.; Kodagoda, S., "Gaussian mixture based HMM for human daily activity recognition using 3D skeleton features, " Industrial Electronics and Applications (ICIEA), 2013 8th IEEE Conference on, vol., no., pp.567,572, 19-21 June 2013.doi: 10.1109/ICIEA.2013.6566433 (англ.)
  17. Stigler J., Ziegler F., Gieseke A., Gebhardt J. C. M., Rief M. The Complex Folding Network of Single Calmodulin Molecules // Science. — 334 (2011) (6055) С. 512–516. DOI:10.1126/science.1207598. PMID 22034433. (англ.)
  18. Wong W., Stamp M. Hunting for metamorphic engines // Journal in Computer Virology. — 2 (2006) (3) С. 211-229. DOI:10.1007/s11416-006-0028-7. (англ.)
  19. Wong K. -C., Chan T. -M., Peng C., Li Y., Zhang Z. DNA motif elucidation using belief propagation // Nucleic Acids Research. — 41 (2013) (16) С. e153. DOI:10.1093/nar/gkt574. PMID 23814189. (англ.)
  20. Baker J. The DRAGON system--An overview // IEEE Transactions on Acoustics, Speech, and Signal Processing. — 23 (1975) С. 24–29. DOI:10.1109/TASSP.1975.1162650. (англ.)
  21. Jelinek F., Bahl L., Mercer R. Design of a linguistic statistical decoder for the recognition of continuous speech // IEEE Transactions on Information Theory. — 21 (1975) (3) С. 250. DOI:10.1109/TIT.1975.1055384. (англ.)
  22. Xuedong Huang[en], M. Jack, and Y. Ariki (1990). Hidden Markov Models for Speech Recognition. Edinburgh University Press. ISBN 0-7486-0162-7.  (англ.)
  23. Xuedong Huang[en], Alex Acero, and Hsiao-Wuen Hon (2001). Spoken Language Processing. Prentice Hall. ISBN 0-13-022616-5.  (англ.)
  24. M. Bishop and E. Thompson Maximum Likelihood Alignment of DNA Sequences // Journal of Molecular Biology. — 190 (1986) (2) С. 159–165. DOI:10.1016/0022-2836(86)90289-5. PMID 3641921. (англ.)
  25. Richard Durbin, Sean R. Eddy, Anders Krogh[en], Graeme Mitchison (1999). Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press[en]. ISBN 0-521-62971-3.  (англ.)
  26. Beal, Matthew J., Zoubin Ghahramani, and Carl Edward Rasmussen. «The infinite hidden Markov model.» Advances in neural information processing systems 14 (2002): 577–584. (англ.)
  27. Teh, Yee Whye, et al. «Hierarchical dirichlet processes.» Journal of the American Statistical Association 101.476 (2006). (англ.)
  28. Ghahramani Zoubin, Jordan, Michael I. Factorial Hidden Markov Models // Machine Learning. — 29 (1997) (2/3) С. 245–273. DOI:10.1023/A:1007425814087. (англ.)
  29. Triplet Markov Chain, W. Pieczynski,Chaînes de Markov Triplet, Triplet Markov Chains, Comptes Rendus de l'Académie des Sciences — Mathématique, Série I, Vol. 335, No. 3, pp. 275–278, 2002. (англ.)

Посилання[ред.ред. код]

Концепції[ред.ред. код]

Програмне забезпечення[ред.ред. код]

  • HMMdotEM (інструментарій для звичайних ПММ з дискретними станами, випущений під 3-пунктовою ліцензією BSD, наразі лише для Matlab)
  • Hidden Markov Model (HMM) Toolbox for Matlab (інструментарій для Matlab від Кевіна Мерфі)
  • Hidden Markov Model Toolkit (HTK) (переносний інструментарій для побудови й маніпулювання прихованими марковськими моделями)
  • Hidden Markov Models (пакет для R для налаштування, застосування та отримання висновків за допомогою прихованих марковських моделей з дискретним часом і дискретним простором)
  • HMMlib (оптимізована бібліотека для роботи зі звичайними (дискретними) прихованими марковськими моделями)
  • parredHMMlib (паралельна реалізація послідовного алгоритму та алгоритму Вітербі. Надзвичайно швидка для ПММ з малими просторами станів)
  • zipHMMlib (бібліотека для звичайних (дискретних) прихованих марковських моделей, що використовує повторення у вхідній послідовності для значного прискорення послідовного алгоритму. Також реалізовано алгоритм апостеріорного декодування та алгоритм Вітербі.)
  • GHMM Library (домашня сторінка проекту GHMM Library)
  • CL-HMM Library (бібліотека ПММ для Common Lisp)
  • Jahmm Java Library (Java-бібліотека загального призначення)
  • ПММ та інші статистичні програми (Реалізація Тапаса Канунго для C)
  • The hmm package (бібліотека для Haskell для роботи з прихованими марковськими моделями)
  • GT2K (Georgia Tech Gesture Toolkit — пакет для розпізнавання жестів)
  • Hidden Markov Models — Online Calculations (інтерактивний калькулятор для ПММ — шлях Вітербі та ймовірності. Приклади із сирцевим кодом на perl)
  • CvHMM (клас дискретних прихованих марковських моделей, на базі OpenCV)
  • depmixS4: Dependent Mixture Models — Hidden Markov Models of GLMs and Other Distributions in S4 (пакет для R)
  • MLPACK[en] (містить реалізацію ПММ для C++)