Міністерствоосвіти та науки України
Національнийуніверситет «Львівська політехніка»
Курсоваробота
здисципліни
Інформаційніінтелектуальні системи
натему
«Прихованімарківські процеси»
Львів– 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]
teormin.ifmo.ru/education/machine-learning/notes-06-hmm.pdf
Стаття «Приховані марківські моделі». В ній є поняття прихованих марківськихпроцесів, конкретні приклади та пояснюються елементи прихованих марківськихмоделей. Також пояснюється зміст та вирішення задач прихованих марківськихмоделей.[5]
www.lib.ua-ru.net/diss/cont/9307.html
Стаття «Скрытые марковские модели», в якій описується марківські ланцюги тапроцеси, а також розв`язок задач прихованих марківських моделей.[2]
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 ij — це ймовірність переходу з стану 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 невідомих параметрів. Таким чином, ПММ з великою кількістю ступенівсвободи по суті більш дієздатна, ніж її менші аналоги. Також теоретичнодоведено (і це ми побачимо далі), що в сучасних умовах існують обмеження нарозмір моделей. Більш того, може виявитися, що у випадку, коли людина за стіноюпідкидає одну єдину монету, ми виберемо модель трьох станів. У такому випадкуз'ясовується, що стану системи не відповідають реальним станів за стіною, і,отже, ми використовуємо надлишкову модель.
Приклад кульок увазах. Зараз мидоповнимо ПММ новими структурними елементами, для того, щоб вона моглавирішувати ряд більш складних завдань. Допоможе нам в цьому приклад з кулькамиу вазах (мал. 3).
/>
мал. 3. Модель зN станами (вазами) та кульками, кольори яких позначають елементи щоспостерігається послідовності.
Припустимо, у насє N скляних прозорих ваз. У кожній вазі — велике число кульок різногокольоруВважаємо, що у нас в кошику лежать кульки M різних кольорів. Фізично цеможна представити наступним чином. Людина знаходиться в кімнаті з вазами.Яким-небудь випадковим чином він вибирає будь-яку вазу, простягає руку глибше,і витягує м'яч. Колір кулі записується в журнал показань — спостерігаєтьсяпослідовність, і людина кладе шар назад в цю вазу. Потім наша людина вибираєнову вазу, і йде до неї, і витягує звідти новий шар, і так далі. В результаті миотримуємо послідовність кольорів — результат роботи ПММ — спостерігаєтьсяпослідовність.
Очевидно, щоприклад кульок у вазах відповідає прихованої марківській моделі, де кожне станмоделі — це обрана ваза, причому в різних ваз різну ймовірність витягти кулькучервоного (або іншого) кольору, що відповідає різного розподілу ймовірностейдля кожного стану. Те, яка ваза буде обрана наступної, залежить від матриціпереходів ПММ, т. е. залежить і від того, у якої вази ми зараз знаходимося.[1]
/>
Елементиприхованої марківської моделі
Наведені вищеприклади дають непогане уявлення про ПММ, і про можливі сферах їх застосування.Зараз ми дамо формальне визначення елементів ПММ і зрозумілий, як модельгенерує спостережувану послідовність. ПММ визначається наступними елементами:
1. N — загальнакількість станів в моделі. Незважаючи на те, що стану в ПММ є прихованими, убагатьох випадках є відповідність між станом моделі і реальним станом процесу. Уприкладі з підкиданням монети кожне стан відповідно до обраної монеті, а вприкладі з кульками у вазах стан моделі відповідно до обраної вазі. Взагальному, перехід у будь-який обраний стан можливий з будь-якого стану всієїсистеми (в тому числі й сама в себе); з іншого боку, і це ми побачимо згодом,лише певні шляхи переходів представляють інтерес у кожної конкретної моделі. Мипозначимо сукупність станів моделі безліччю />,,a поточний стан в момент часу t як q.
2. M, кількістьможливих символів у що спостерігається послідовності, розмір алфавітупослідовності. У випадку з підкиданням монети — це 2 символу: орел і решка; увипадку з кульками — це кількість кольорів цих самих кульок. Алфавіт щоспостерігається в послідовності ми позначимо як />.
3. Матрицяймовірностей переходів (або матриця переходів) />, де
/> , /> (7)
ттобто це ймовірність того, щосистема, що перебуває в стані Si, перейде в стан Sj. Якщо для будь-яких двохстанів в моделі можливий перехід з одного стану в інше, то a i j>0 для будь-яких i, j. В інших ПММ для деяких i, j у нас ймовірність переходу ai j = 0.
4. Розподілймовірностей появи символів у j-тому стані, />, где, де
/> /> /> (8)
b j (k) — імовірність того, що в момент часу t, система, яка знаходиться в j-му стані(стан Sj), видасть k-тий символ (символ k) в спостережувану послідовність.
5. Розподілймовірностей початкового стану />, где, де
/>, />, (9)
тобто ймовірністьтого, Si — це початковий стан моделі.
Сукупністьзначень N, M, A, B і π — це прихована марківська модель, яка можезгенерувати послідовність
/> (10)
(де O t— один з символів алфавіту V, а T — це кількість елементів в послідовності.
ПММ будуєспостережувану послідовність по наступному алгоритмі
1. Вибираємопочатковий стан q 1 = S i відповідно до розподілу π
2. Встановлюємоt = 1.
3. ВибираємоO t = v k відповідно до розподілу b j ( k ) устані ( S i ).
4. Переводимомодель у новий стан q t + 1 = S j відповідно до матриціпереходів a i j з урахуванням поточного стану S i.
5. Встановлюємочас t = t + 1; вертаємося до кроку 3, якщо t
Підбиваючипідсумок, можливо помітити, що повний опис ПММ складається із двох параметрівмоделі ( N і M ), опису символів спостережуваної послідовності й трьох масивів ймовірностей— A, B, і π. Для зручності ми використаємо наступний запис
/> (11)
для позначення достатньогоопису параметрів моделі.
5.Основні результати, які отримані в результаті вирішення задачі
Відповідно доопису схованої марківської моделі, викладеному в попередньому розділі, існуєтри основних задачі, які повинні бути вирішені для того, щоб модель моглауспішно вирішувати поставлені перед нею задачі.
Задача 1
Дано:спостережувана послідовність і модель λ = ( A, B ,π). Необхіднообчислити ймовірність P ( O | λ) — імовірність того, що данаспостережувана послідовність побудована саме для даної моделі.
Задача 2
Дано:спостережувана послідовність і модель λ = ( A, B ,π). Необхіднопідібрати послідовність станів системи, що найкраще відповідає спостережуванійпослідовності, тобто «пояснює» спостережувану послідовність.
Задача 3
Підібратипараметри моделі λ = ( A, B ,π) таким чином, щоб максимізувати P ( O| λ).
Задача 1 — цезадача оцінки моделі, що полягає в обчисленні ймовірності того, що модельвідповідає заданій спостережуваній послідовності. До суті цієї задачі можнапідійти й з іншої сторони: наскільки обрана ПММ відповідає заданійспостережуваній послідовності. Такий підхід має більшу практичну цінність.Наприклад, якщо в нас коштує питання вибору найкращої моделі з набору вжеіснуючих, то рішення першої задачі дає нам відповідь на це питання.
Задача 2 — цезадача, у якій ми намагаємося зрозуміти, що ж відбувається в прихованій частинімоделі, тобто знайти «правильну» послідовність, що проходить модель. Зовсімясно, що абсолютно точно не можна визначити цю послідовність. Тут можнаговорити лише про припущення з відповідним ступенем вірогідності. Проте длянаближеного рішення цієї проблеми ми звичайно будемо користуватися деякимиоптимальними показниками, критеріями. Далі ми побачимо, що, на жаль, не існуєєдиного критерію оцінки для визначення послідовності станів. При рішенні другоїзадачі необхідно кожний раз ухвалювати рішення щодо того, які показникивикористати. Дані, отримані при рішенні цієї задачі використаються для вивченняповодження побудованої моделі, знаходження оптимальної послідовності її станів,для статистики й т.п. [6]
Рішення задачі 3складається в оптимізації моделі таким чином, щоб вона якнайкраще описувалареальну спостережувану послідовність. Спостережувана послідовність, по якійоптимізується ПММ, прийнято називати навчальною послідовністю, оскільки за допомогоюїї ми «навчаємо» модель. Задача навчання ПММ — це найважливіша задача длябільшості проектованих ПММ, оскільки вона полягає в оптимізації параметрів ПММна основі навчальної спостережуваної послідовності, тобто створюється модель,що щонайкраще описує реальні процеси.
Для кращогорозуміння розглянемо все вищесказане на прикладі системи, призначеної длярозпізнавання мови. Для кожного слова зі словника W ми спроектуємо ПММ із Nстанами. Кожне слово зокрема ми представимо як послідовність спектральнихвекторів. Навчання ми будемо вважати завершеним, коли модель із високоюточністю буде відтворювати ту саму послідовність спектральних векторів, щовикористалася для навчання моделі. У такий спосіб кожна окрема ПММ буденавчатися відтворювати яке-небудь одне слово, але навчати цю модель треба надекількох варіантах проголошення цього слова; тобто наприклад три чоловіки(кожний по-своєму) проговорюють слово «собака», а потім кожне сказане словоконвертується в упорядкований за часом набір спектральних векторів, і модельнавчається на основі цих трьох наборів. Для кожного окремого слова проектуютьсявідповідні моделі. Спершу вирішується 3-я задача ПММ: кожна модель настроюєтьсяна «проголошення» певного слова зі словника W, відповідно до заданої точності.Для того щоб інтерпретувати кожний стан спроектованих моделей ми вирішуємо 2-уюзадачу, а потім виділяємо ті властивості спектральних векторів, які маютьнайбільша вага для певного стану. Це момент тонкого настроювання моделі. А вжепісля того, як набір моделей буде спроектований, оптимізований і навчений,варто оцінити модель на предмет її здатності розпізнавати слова в реальномужитті. Тут ми вже вирішуємо 1-ую задачу ПММ. Нам дається тестове слово,представлене, зрозуміло, у вигляді спостережуваної послідовності спектральнихвекторів. Далі ми обчислюємо функцію відповідності цього тестового слова длякожної моделі. Модель, для якої ця функція буде мати найбільше значення, будевважатися моделлю названого слова.
6.Місце і спосіб застосування отриманих результатів
Для розпізнаваннямовлення із великих словників для ізольовано (або дискретно) вимовлених слів напочатку 90-х років було розроблено декілька систем з достатньо гарнимипоказниками. Потім увага дослідників перенеслася на розпізнавання злитого мовлення,де використовувалися статистичні залежності в порядку слів, що дозволялопередбачити поточне розпізнаване слово на основі кількох попередніх слів.Розроблені статистичні методи прогнозу дозволили значно зменшити кількістьальтернатив при розпізнаванні, що у свою чергу дозволило розробляти системирозпізнавання з сумарним обсягом у десятки тисяч слів, хоча на кожному кроцірозпізнавання розглядалося декілька сотень альтернатив.
Проте, існуєнеобхідність побудови систем розпізнавання мови з великою кількістю альтернативі за умови, що немає яких-небудь обмежень на порядок розпізнаваних слів.
Наприклад, прикеруванні комп'ютера голосом неможливо передбачити наступне слово на основідекількох попередніх, оскільки це визначається логікою керування комп'ютера, ане властивостями тексту. З іншого боку існує необхідність значного збільшенняобсягу словника для того, щоб охопити всі синоніми однієї і тієї ж команди,оскільки користувачу, звичайно, важко запам'ятати тільки один варіант назвикоманди.
Другий прикладпов'язаний з диктуванням текстів. Використання таких систем, звичайно, обмеженотакими текстами, що аналогічні тим текстам, для яких накопичувалися статистики.Крім іншого, додаткове редагування набраного тексту вимагає наявності всіх слівв активному словнику.
Таким чином,існують додатки, де бажано мати словник максимально великого розміру, щоб умайбутньому охопити всі слова даної мови.
Додатковаінформація для обмеження числа альтернатив може бути одержана безпосередньо змовного сигналу. Для цього пропонується виконати пробне розпізнавання задопомогою фонетичного стенографа. Одержана послідовність фонем формує потікзапитів до бази даних для отримання невеликої кількості слів, які могли бвходити в словник розпізнавання, що дозволяє значно скоротити кількістьальтернатив для розпізнавання.[3]
Наступні розділиописують новий двопрохідний алгоритм. Спочатку представлена базова система дляпорівняння із запропонованою системою розпізнавання мови. Потім описані дваваріанти алгоритму для ізольованих слів та злитого мовлення. Виконаніексперименти показують ефективність запропонованих методів.
Запропонованийметод можна застосувати в будь-якій системі розпізнавання мовлення, депредставлені фонеми, і можна сформувати процедуру фонетичного стенографа. У данійроботі як базова система використовується інструментарій на основі прихованихМарківських моделей (Hidden Markov Model — HMM)
Попередня обробкамовленнєвого сигналу
Мовний сигналперетвориться в послідовність векторів ознак з інтервалом аналізу 25 мс і крокоманалізу 10 мс. Спочатку мовний сигнал фільтрується фільтром високих частот зхарактеристикою P(z) =1-0.97z-1 та застосовується вікно Хемінга. Швидкеперетворення Фурьє переводити часовий сигнал у спектральний вигляд. Спектральнікоефіцієнти усереднюються з використанням 26 трикутних вікон, розташованими вмел-шкалі. 12 кепстральних коефіцієнтів обчислюються за допомогою зворотногокосинусного перетворення.
Логарифм енергіїдодається як 13-й коефіцієнт. Ці 13 коефіцієнтів розширюються до 39-мірного векторапараметрів шляхом дописування першої та другої різниць від коефіцієнтівсусідніх за часом. Для обліку впливу каналу застосовується відніманнясереднього кепстра.
Акустична модель
Акустичні моделівідображають характеристики основних одиниць розпізнавання. Для акустичнихмоделей використовуються приховані Марківські моделі з 64 сумішами Гауссівськихфункцій щільності імовірності. 47 російських контекстно-незалежних фонеммоделюються трьома станами Марківського ланцюга з пропусками. Словниктранскрипцій створюється автоматично з орфографічного словника з використанняммножини контекстно-залежних правил.[3]
Показники базовоїсистеми
Акустичні моделінавчалися на вибірці з 12 тис. звукових записів із словника в 2037 слів,вимовлених одним диктором. Розпізнавання проводилося на комп'ютері P-IV 2.4ГГц.
Для перевіркинадійності розпізнавання мови було накопичено 1000 окремо вимовлених слів тимже диктором. Послівна надійність розпізнавання і середній час розпізнаванняоднієї секунди мови для різних розмірів словника приведені в таблиці 1.Оскільки час розпізнавання лінійно залежить від розміру словника, то длясловника в 1987 тис. слів його можна оцінити приблизно в 2300 секунд.
Таблиця 1:Результати розпізнавання окремо вимовлених слів базовою системоюОб'єм словника, тис. 1 15 95 Надійність, % 99.9 97.9 94.7 Час, сек. 1 16 115
Для перевіркинадійності розпізнавання злитого мовлення було додатково накопичено 1000 фраз зчислами від 0 до 999. Послівна надійність розпізнавання і середній часрозпізнавання однієї секунди мови для різних розмірів словника приведені втаблиці 2.
Таблиця 2:Результати розпізнавання злитого мовлення базовою системоюОб'єм словника, тис. 1 15 95 Надійність, % 98.0 96.5 92.6 Час, сек. 2.1 36 205
7.Програмна реалізація завдання, виконаного у курсовій роботі
7.1Алгоритм ELVIRS для окремо вимовлених слів
Архітектура
Архітектурасистеми розпізнавання ELVIRS (Extra Large Vocabulary Speech recognition basedon the Information Retrieval) показана на мал. 4. Такі блоки з базової системи якобчислення ознак і акустичних моделей використовуються перед першим проходомалгоритму.
/>
Також на другомупроході використовується звичайне порівняння образів в умовах обмеженогословника
Зміни торкаютьсявведення першого проходу алгоритму, де фонетичний стенограф використовуєтьсядля отримання послідовності фонем. Потім процедура вибірки інформації створюєобмежений словник (підсловник) для другого проходу алгоритму.
Фонетичнийстенограф
Алгоритмфонетичного стенографа[2] створює фонетичну послідовність для мовного сигналунезалежно від словника. Для цього будується деякий автомат породження фонем,який може синтезувати всі можливі моделі мовних сигналів для послідовностіфонем. Потім використовується пофонемне розпізнавання для невідомого мовногосигналу.
Використовуютьсяті ж контекстно-незалежні моделі фонем, що і в базовій системі розпізнавання.
Процедураотримання підсловника з бази даних
Заздалегідь впроцесі навчання із словника транскрипцій створюється індекс від трійок фонемдо транскрипцій. Ключем індексу є трійка фонем. Таким чином, таблиця індексускладається з M3 входжень, де M є число фонем в системі. Кожне входження втаблицю містить список транскрипцій, в які входить трійка фонем ключавходження.
Процес отриманняпідсловника ілюструється. Вихід фонетичного стенографа ділиться на трійки фонеміз зрушенням на одну фонему. Трійка фонем стає запитом до бази даних. Заразвикористовується простий запит, коли він в точності співпадає з трійкою фонем.В майбутньому пропонується використовувати відстань Levensteine для врахуваннявставок, видалень та замін в послідовності фонем. Таким чином, послідовністьфонем продукує потік запитів до бази даних.
Відповідь на одинзапит складається із списку транскрипцій, в які дана трійка фонем входить. Цейсписок копіюється в підсловник для другого проходу алгоритму. Наступний запит зпотоку додає нову порцію транскрипцій, при цьому підраховується кількістьповторень для того, щоб можна було обчислити ранг слова в підсловнику.
Всі транскрипціїв одержаному підсловнику упорядковуються згідно рангу слова (лічильникуповторень). Перші N транскрипцій заносяться в остаточний підсловник для другогопроходу алгоритму. Таким чином, підсловник для розпізнавання міститьтранскрипції з найвищими рангами і число транскрипцій не перевищує фіксованогочисла N.
АлгоритмELVIRS
Алгоритм ELVIRSскладається з двох частин. Підготовчий етап:
• Підготуватисловник для розпізнавання.
• Вибратимножину фонем і створити транскрипції слів із словника за допомогою правил.
• Створитиіндекс бази даних від трійок фонем до транскрипцій.
• Навчитиакустичні моделі по накопичених мовних сигналах.
Етапрозпізнавання:
• Застосуватифонетичний стенограф до вхідного сигналу для отримання послідовності фонем.
• Поділитипослідовність фонем на трійки фонем із зрушенням в одну фонему.
• Створитизапити до БД з трійок фонем
• Одержатисписки транскрипцій за допомогою запитів до індексу бази даних.
• Упорядкуватитранскрипції до їх рангу.
• Вибрати першіN транскрипцій з найвищими рангами як підсловник для розпізнавання.
• Розпізнативхідний мовний сигнал в умовах обмеженого підсловника.[5]
Інформаційнаоцінка імовірності правильного формування підсловника
Відповідьрозпізнавання фонетичного стенографа може розглядатися як правильнапослідовність фонем, пропущена через канал з шумом. Позначимо у відповідіфонетичного стенографа правильну фонему як 1, а зіпсовану шумом як 0. Нехайімовірність появи 1 в двійковому наборі дорівнює u. Імовірність P знайти вдвійковому наборі довжини n підряд k одиниць і більше можна обчислити задопомогою наступного рекурентного виразу:
/> (12)
В таблиці показанаімовірність P знайти в двійкових наборах підряд три і більше 1 при деякихдовжинах n та імовірності u. Середня довжина транскрипцій дорівнює приблизно 8і імовірність правильного знаходження фонеми у відомих реалізацій приблизнодорівнює 85%. При таких значеннях імовірність знайти правильне слово впідсловнику дорівнює 0.953.
Таблиця 3:Імовірність знайти підряд три і більше 1 в двійковому наборі довжини n 0.75 0.8 0.85 0.9 6 0.738 0.819 0.890 0.948 7 0.799 0.869 0.926 0.967 8 0.849 0.908 0.953 0.982 9 0.887 0.937 0.971 0.991 10 0.915 0.956 0.981 0.995
7.2Алгоритм ELVIRCOS для розпізнавання злитого мовлення
Архітектура
Після отриманнясписків транскрипцій використовується додаткова процедура формування графа слівдля злитого мовлення, яка створює мережу слів для другого проходу алгоритму.
Формуванняграфа слів
Процес створенняграфа слів показаний на мал. 5. Мережа слів починається з вершини S ізакінчується у вершині F. Кожна трійка фонем з відповіді фонетичного стенографапороджує проміжну вершину з номером синхронним до часу появи цієї трійки фонем.З іншого боку кожна трійка фонем стає запитом до індексу бази даних, якийповертає список транскрипцій. Транскрипції вставляються між проміжнимивершинами так, щоб трійки фонем опинилися в одній колонці по вертикалі.
У випадку, коливідбувається перетин транскрипцій одного слова, породженими різними трійкамифонем, тоді ранги цих транскрипцій збільшуються на одиницю. Для кожного моментучасу можна підрахувати число транскрипцій тих, що входять у цей проміжок часу.
Для зменшенняскладності графа слів використовується обмеження N для кількості слів в коженмомент часу. При цьому віддаляються слова з малими рангами.
Оскільки графслів формується зліва направо можна проводити його формування у реальному часііз затримкою, яка дорівнює максимальній довжині транскрипції.
Відповідьфонетичного стенографа
# с г в а + с н, ъ й е #
/>
мал. 5.Формування графа слів для злитого мовлення
АлгоритмELVIRCOS
Алгоритм ELVIRCOSскладається з двох частин. Підготовчий етап такої ж, як і в алгоритмі ELVIRS.Етап розпізнавання:
• Застосуватифонетичний стенограф до вхідного сигналу для отримання послідовності фонем.
• Поділитипослідовність фонем на трійки фонем із зрушенням в одну фонему.
• Створитизапити до БД з трійок фонем
• Одержатисписки транскрипцій за допомогою запитів до індексу бази даних.
• Створитиграф слів для злитого мовлення.
• Упорядкуватитранскрипції до їх рангу.
• Вибрати першіN транскрипцій з найвищими рангами як підсловник для розпізнавання.
• Розпізнативхідний мовний сигнал для графа злитої мови в умовах обмеженого підсловника.[5]
8.Експериментальні результати
Для того, щобввести перший прохід алгоритму ELVIRCOS в базову систему розпізнавання мовибули зроблені необхідні зміни в інструментарії і проведені декількаекспериментів.
Для окремовимовлених слів досліджувався вплив обмеження N на середній час і надійністьрозпізнавання мовлення для словників різного об'єму, що наведені в таблиці 4.Результати показують корисність обмеження N для словників великих об'ємів, щодозволяє додатково скоротити час розпізнавання при незначному погіршеннінадійності.
В цілому одержанозначне скорочення часу розпізнавання в сотні разів при відносно невеликому(близько 5%) погіршенні надійності в порівнянні з базовою системоюрозпізнавання. Погіршення надійності має хороший збіг з оцінкою імовірності правильногоформування підсловника.
Таблиця 4:Результати алгоритму ELVIRS
Об'єм словника, тис
Обмеження N на розмір підсловника 15 95 1987 Надійн. % Час, сек. Надійн. % Час, сек. Надійн. % Час, сек. 50 92.2 1.4 81.0 1.4 69.2 1.6 200 94.6 1.6 87.6 2.1 76.0 1.9 500 95.5 1.9 90.1 2.5 80.0 3.3 1000 96.0 2.1 90.7 3.1 82.7 4.4 2000 96.0 4.4 92.0 4.5 84.8 6.8 5000 96.0 4.6 92.9 8.3 86.4 12.0
Для злитогомовлення були проведені попередні експерименти, в яких розглядався випадок,коли обмеження N співпадало з розміром словника. У таблиці 5 наведені показникинадійності для різних розмірів словника.
Таблиця 5:Результати алгоритму ELVIRCOSОб'єм словника, тис 15 95 1987 Надійність, % 85.3 84.9 83 Час, сек 2.3 9.4 160
Зменшеннясереднього часу розпізнавання не настільки значне, як у випадку окремовимовлених слів, оскільки деякі послідовності фонем від фонетичного стенографапороджують графи слів дуже великої розмірності. Сподіваємося, що введенняобмеження N істотно зменшить час розпізнавання.[5]
Слід підкреслитиважливість підходів вибірки інформації з баз даних для процесу розпізнаваннямови. Показано, що додаткове джерело інформації, одержане з аналізупослідовності фонем від фонетичного стенографа, дозволило значно скоротитипростір пошуку в алгоритмі розпізнавання мови. Це дозволило створити системирозпізнавання мови, що охоплюють практично всі слова мови.
Списоквикористаної літератури
1. www.genetics.wustl.edu/eddy
2. www.lib.ua-ru.net/diss/cont/9307.html
3. www.nbuv.gov.ua/e-journals/VNTU/2007-1/ukr/07gtvmco.pdf
4. www.ru.wikibooks.org/wiki/
5.www.teormin.ifmo.ru/education/machine-learning/notes-06-hmm.pdf
6. www.uk.wikipedia.org