Приховані марківські процеси

Міністерство освіти та науки України

Національний університет «Львівська політехніка»

Курсова робота

з дисципліни

Інформаційні інтелектуальні системи

на тему

«Приховані марківські процеси»

Львів - 2009

Зміст

1. Постановка проблеми, якій присвячується тема курсової роботи

2. Огляд літератури за тематикою курсової роботи

3. Постановка завдання яке буде виконане у курсовій роботі

4. Існуючі шляхи вирішення задачі

5. Основні результати, які отримані в результаті вирішення задачі

6. Місце і спосіб застосування отриманих результатів

7. Програмна реалізація завдання, виконаного у курсовій роботі

7.1 Алгоритм ELVIRS для окремо вимовлених слів

7.2 Алгоритм ELVIRCOS для розпізнавання злитого мовлення

8. Експериментальні результати

9. Список використаної літератури

1. Постановка проблеми, якій присвячується тема курсової роботи

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

Явища, що відбуваються, можна описувати як сигнали. Сигнали можуть бути дискретними, як письмова мова, або безперервними, як фонограма або кардіограма. Сигнали з постійними статистичними властивостями, називаються стабільними (стаціонарними), а з мінливими - нестабільними (нестаціонарними). Сигнал, може бути чистим, а може й не чистим, з телефонів або зі сторонніми сигналами.

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

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

В області розпізнавання мовлення використовуються обидва типи моделей, але ми розглянемо тільки одну, статистичну модель, а саме - приховану Марківську модель (ПММ).[3]

Теорія прихованих Марківських моделей не нова. Її основи опублікував Баум і його колеги в кінці 60-х, початку 70-х років. Тоді ж, на початку 70-х Бейкер і Джелінек з колегами застосували ПММ в розпізнаванні мови.

2. Огляд літератури за тематикою курсової роботи

Виконуючи підготовку до курсової роботи я використовувала такі матеріали

Із матеріалів Вікіпедії (uk.wikipedia.org)- визначення марківського процесу.

Марківський процес -- це випадковий процес, конкретні значення якого для будь-якого заданого часового параметру t+1 залежать від значення у момент часу t, але не залежать від його значень у моменти часу t-1, t-2 і т. д.[6]

На сайті www.nbuv.gov.ua-сутність поняття марківського процесу. Прикладом марківського процесу може бути відома дитяча гра, у якій фішки учасників повинні переміститися з початкового пункту А0 ("старт") у кінцевий Ak ("фініш"). Потрапивши в той або інший проміжний пункт AJ, фішка може або наблизитися до фінішу (за рахунок "пільги", передбаченої умовами гри), або видалитися від нього (за рахунок "штрафу").

Статтю Т.В. Грищука «Отримання характеристичної обсервації прихованої марківської моделі». В статті розглядається процес отримання на основі натренованої прихованої моделі характеристичної обсервації голосової команди. Ця інформація може використовуватися для підвищення ефективності процесу розпізнання мови. Введено поняття оціночної функції, знаходження максимуму якої дає характеристичну обсервацію.

Вісник НАН України. -- 2003. -- N 1. Стаття І. Сергієнко, А. Гупал. Стаття в якій описується ланцюг Маркова -- проста та економна модель дослідження поведінки об'єктів із залежними ознаками.

Стаття «Алгоритм Витерби для моделей скрытых марковских процессов с неизвестным моментом появления скачка». В цій статті показані результати математичного моделювання для алгоритма Вітербі, за допомогою прихованих марківських процесів.[3]

http://teormin.ifmo.ru/education/machine-learning/notes-06-hmm.pdf Стаття «Приховані марківські моделі». В ній є поняття прихованих марківських процесів, конкретні приклади та пояснюються елементи прихованих марківських моделей. Також пояснюється зміст та вирішення задач прихованих марківських моделей.[5]

http://www.lib.ua-ru.net/diss/cont/9307.html Стаття «Скрытые марковские модели», в якій описується марківські ланцюги та процеси, а також розв`язок задач прихованих марківських моделей.[2]

http://www.genetics.wustl.edu/eddy В цій статті наведений приклад застосування Прихованих марківських моделей як програмного забезпечення для аналізу послідовності білка. HMMER є програмною реалізацією. HMMER1 широко використовується для аналізу ДНК, на додаток до аналізу білків.[1]

3. Постановка завдання яке буде виконане у курсовій роботі

Розглянемо систему, яку можна в будь-який момент часу можна описати одним з N станів, S1, S2,...SN, (мал. 1), де для простоти N = 5. Через певний проміжок часу система може змінити свій стан або залишитися в колишньому стані відповідно до ймовірностям, зазначеним для цих станів. Моменти часу, коли ми реєструємо стан системи ми позначимо як t=1,2,... , а стан в момент часу t - ми позначимо q t. Повний опис розглянутої вище системи, повинно містити поточний стан (в момент часу t) і послідовність всіх попередніх станів, через які пройшла система. В окремих випадках опис системи зводиться до вказівкою поточного та попереднього стану.

(1)

Крім того, ми також вважаємо що процеси, що протікають у системі, не залежать від часу, про що нам говорить права частина формули (1). Таким чином, систему можна описати безліччю ймовірностей a i j у вигляді

(2)

де a i j - це ймовірність переходу з стану S i в стан S j в даний момент часу. Оскільки ці ймовірності характеризують випадковий процес, вони мають звичайні властивості, т. е.

(3.1)

(3.2)

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

§ Стан № 1: дощ (або сніг)

§ Стан № 2: хмарно, можливий дощ

§ Стан № 3: ясно

Матриця ймовірностей зміни погоди A має вигляд

Виходячи з того, що погода в перший день (t = 1) ясна (стан 3), ми можемо задати собі питання: яка вірогідність (згідно з нашою моделі), що наступні 7 днів буде саме «зрозуміло - ясно - дощ - дощ - ясно - Хмарно, можливий дощ - ясно »? Точніше сказати, для цієї послідовності станів O, де відповідає, t=1,2,...,8, Ми хочемо на основі даної моделі визначити ймовірність спостереження послідовності O. Ця ймовірність може бути виражена (і обчислено) наступним чином

(4)

це ймовірність того, що початковий стан системи буде Si.

Є й інший цікаве питання, відповідь на яке нам дасть ця модель: яка вірогідність того, що модель збереже свій стан протягом рівно d днів? Ця ймовірність може бути обчислено як ймовірність спостереження такій послідовності

дає модель, в якій

(5)

Величина pi (d) - це ймовірність того, що система буде перебувати в стані i рівно d раз поспіль. Відповідно є функція розподілу ймовірності для тривалості перебування системи в одному стані, яка є характеристикою збереження стану для марківських ланцюга. Знаючи величини pi (d) ми можемо обчислити середній час, протягом якого система збереже свій стан (використовуємо формулу математичного очікування):

(6.1)

(6.2)

Очікується, що сонячна погода швидше за все простоїть 5 днів, похмура - 2,5 дні, а от дощова погода, згідно з нашою моделі, імовірніше за все протримається 1,67 дня.

4. Існуючі шляхи вирішення задачі

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

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

,

де Н - це орел, а Т - це решка.

Як же побудувати приховану марківську модель, що відповідає цій ситуації? Перше питання: скільки станів буде у моделі і що означає кожне стан такої моделі? Припустимо, що ми підкидаємо одну єдину монету, а інших у нас немає. Тоді вибір ми зупинимо на моделі з двома станами, де одне стан означає випадання орла, інше - решка. [1]

мал. 2.

Три марківські моделі, які можуть описати експеримент з монетою, що підкидається. (а) 1 монета бере участь у підкиданні, (2) 2 - монети, (3) - три монети.

Ця модель зображена на малюнку 2 (а). У цьому випадку марківських модель є відкритою і єдине, що ми можемо зробити з цією моделлю - це оптимізувати ймовірність зміни стану. Слід зауважити, що прихована марківських модель, що є аналогом моделі, зображеної на рис. 2 (а), буде представляти собою модель одного стану. В цій моделі єдине стан означає, що підкидана всього лише одна монета.

На наступному малюнку 2 (б) зображена ПММ двох станів. У цьому випадку кожне стан відповідає різним монетам, які підкидають в ході експерименту (наприклад, 1 копійка і 5 рублів). Кожному станом відповідає розподіл ймовірностей між випаданням орла і решка, а також матрицею ймовірностей переходів (матрицею переходів), що вказує ймовірність переходу з одного стану в інше. Перехід зі стану в стан згідно з заданим ймовірностям з матриці переходів може здійснюється на основі того ж підкидання монети або на основі будь-якої іншої випадкової події.

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

Тут, як і кожен раз при проектуванні ми задаємося питанням: яка з трьох моделей найкращим чином підходить для опису, що спостерігається послідовності? Добре видно, що перша модель (мал. 2 (а)) має всього лише 1 невідомий параметрМодель для двох монет (мал. 2 (б)) має 4 невідомих параметра І нарешті, модель для трьох монет (мал. 3 (в)) має 9 невідомих параметрів. Таким чином, ПММ з великою кількістю ступенів свободи по суті більш дієздатна, ніж її менші аналоги. Також теоретично доведено (і це ми побачимо далі), що в сучасних умовах існують обмеження на розмір моделей. Більш того, може виявитися, що у випадку, коли людина за стіною підкидає одну єдину монету, ми виберемо модель трьох станів. У такому випадку з'ясовується, що стану системи не відповідають реальним станів за стіною, і, отже, ми використовуємо надлишкову модель.

Страницы: 1, 2, 3