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

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

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

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

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

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

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

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

До того ж, для кожного з N можливих станів є набір ймовірностей виходів, що керує розподілом спостережуваної змінної у певний момент часу для заданого стану прихованої змінної в цей момент часу. Розмір цього набору залежить від природи спостережуваної змінної. Наприклад, якщо спостережувана змінна є дискретною з M можливих значень, що регулюються категорійним розподілом, то буде ${\displaystyle M-1}$ окремих параметрів, загальним числом ${\displaystyle N(M-1)}$ параметрів виходу для всіх прихованих станів. З іншого боку, якщо спостережувана змінна є M-мірним вектором з розподілом відповідно до довільного багатовимірного нормального розподілу, то буде M параметрів, що контролюють середні, та ${\displaystyle {\frac {M(M+1)}{2}}}$ параметрів, що контролюють коваріаційну матрицю, загальним числом ${\displaystyle N\left(M+{\frac {M(M+1)}{2}}\right)={\frac {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
Ми можемо знайти найбільш правдоподібну послідовність, обчисливши спільну ймовірність послідовностей станів та спостережень для кожного випадку (просто перемноживши значення ймовірностей, що відповідають непрозорості задіяних стрілок). Загалом, цей тип задач (тобто, знаходження найбільш правдоподібного пояснення спостережуваної послідовності) може ефективно розв'язуватися алгоритмом Вітербі.

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

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

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

Аліса знає загальні тенденції погоди в тій місцевості, і що Боб любить робити в середньому. Іншими словами, параметри ПММ відомі. Їх можна представити мовою програмування 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.

Задача навчання параметрів у ПММ полягає в знаходженні для заданої послідовності виходів або набору таких послідовностей найкращого набору ймовірностей переходів станів та виходів. Ця задача зазвичай полягає у виведенні оцінки максимальної правдоподібності цих параметрів ПММ для заданого набору послідовностей виходів. Не відомо жодного легкорозв'язного алгоритму для точного розв'язання цієї задачі, але локальну максимальну правдоподібність може бути дієво виведено із застосуванням Алгоритма Баума — Велша або алгоритму Бальді — Шовена. Алгоритм Баума — Велша є окремим випадком алгоритму очікування-максимізації.

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

• Кінетичний аналіз однієї молекули[17]
• Криптоаналіз
• Розпізнавання мовлення
• Синтез мовлення
• Розмічування частин мови
• Розділення документів у рішеннях для сканування
• Машинний переклад
• Часткові розряди
• Передбачення генів
• Вирівнювання біопослідовностей
• Аналіз часових рядів
• Розпізнавання діяльності
• Згортання білків[18]
• Виявлення метаморфних вірусів[19]
• Виявлення консервативних мотивів ДНК[20]

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

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

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

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

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

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

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

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

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

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

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

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

Вікісховище має мультимедійні дані за темою: Прихована марковська модель