• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Мовні технології

Опрацювання мовних сигналів

Багато напрямків мовних технологій (опрацювання мовних сигналів з певною метою: стиск мовних сигналів, cинтез мови, зміна темпу мовлення, розпізнавання або визначення емоційного стану людини за голосом, діагностика степені певних захворювань, розпізнавання мови) на сьогодні інтенсивно розвиваються та знаходять усе більше застосування в різноманітних сферах.

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

Важливим моментом при опрацюванні мовних сигналів у цифровому вигляді є вибір частоти дискретизації та розрядності відліків у бітах при переході за допомогою аналого-цифрового перетворювача від неперервного до дискретного мовного сигналу.

Загалом вважається, що для звукових сигналів (спів людини, музика, мова, інші звукові сигнали, скажімо дзенькіт кришталю) гранична частота не перевищує 22 КГц. Тому для дискретизації звукових сигналів беруть стандартні частоти 44,1 КГц або 48 КГц. Розрядність відліків цифрового звукового сигналу – 16 біт.

Проте мовні сигнали зокрема мають звужений діапазон частот – від 0 до 8 КГц. І при опрацюванні мови досить дискретизувати неперервні сигнали з частотою дискретизації 16 КГц та брати 16-бітові відліки.

У деяких часткових випадках основні спектральні складові сигналів знаходяться в ще вужчому діапазоні, і замість частоти дискретизації 16 КГц можна взяти частоту дискретизації 8КГц.

Виділяють такі напрямки мовних технологій.

1. Стиск (кодування) мови.

Високого степеня стиску досягаємо використанням дискретних косинусних перетворень.

2. Синтез мови

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

а) компілятивний синтез

Виділяються певні одиниці мови, наприклад звуки мови, після цього з них утворюють слова, речення.

б) формантний синтез

Будують математичну модель голосового тракту людини, щоб мати змогу утворювати різні одиниці мови.

3. Розпізнавання диктора за голосом.

Є два варіанти цієї задачі. Перший варіант, так звана верифікація, полягає в з’ясуванні факту: належить записаний мовний зразок заданій особі чи ні. Інший ускладнений варіант ідентифікації полягає у визначенні якій із наперед заданих осіб належить записаний мовний зразок.

4. Визначення емоційного стану людини за голосом.

5. Визначення стану хворого за голосом (наприклад, при лікуванні мовних розладів).

6. Зміна темпу мовлення.

7. Розпізнавання мови.

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

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

- на фазі навчання попередньо записати певну множину мовних образів-еталонів;

- під час розпізнавання порівнювати невідомий образ (мовний сигнал), який хочемо розпізнати, з кожним із із записаних мовних образів-еталонів;

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

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

У якому вигляді готувати і тримати мовні сигнали-еталони ?

Використовувати часове, спектральне чи якесь комбіноване зображення сигналів ?

Якою міркою порівнювати відстань між двома мовними сигналами ?

Розглянемо найпростіший алгоритм розпізнавання окремих слів із обмеженого словника з навчанням на одного диктора.

Найпростіший розпізнавач мови

Спочатку опишемо як виконують спрощене попереднє опрацювання мовного сигналу х(n). Пропускаємо його через набір смугопропускних цифрових фільтрів (кількість фільтрів для прикладу взята рівною 16). Тобто частотний діапазон сигналу від 0 до 8 кГц (для мовних сигналів) розбиваємо на 16 рівних смуг. Частотні характеристики фільтрів наведені на рис.9.1.

Рис.9.1.

В результаті на виходах цифрових фільтрів ЦФ₁, ЦФ₂,...,ЦФ₁₆ отримуємо 16 цифрових сигналів х₁(n), х₂(n),.... х₁₆(n).

Ділимо число N відліків кожного з цих сигналів на 16 рівних відрізків, доповнюючи сигнал при потребі нульовими відліками, щоб N було кратне 16. Для відліків кожного із шістнадцяти відрізків знаходимо середнє значення. Тобто, перше значення – це середнє відліків сигналу від першого до N/16-го; друге значення – це середнє відліків сигналу від (N/16+1)-го до 2N/16-го;...; шістнадцяте значення – це середнє відліків сигналу від (15N/16+1)-го до N-го. Отже, для кожного з шістнадцяти сигналів х₁(n), х₂(n),.... х₁₆(n) отримуємо 16 середніх значень.

У результаті для сигналу х(n) маємо загалом вектор із 16·16=256 значень.

На фазі навчання диктор проводить навчання системи розпізнавання, повторюючи по три рази (для надійності) слова із вибраного невеликого словника.

Наприклад, це можуть бути назви десяткових цифр, тобто словник складається з таких 10 слів: нуль, один, два, три, чотири, п’ять, шість, сім, вісім, дев’ять.

Виконуючи описане попереднє опрацювання цих мовних сигналів, отримуємо тридцять векторів довжиною 256 значень кожен. Це мовні еталони системи розпізнавання.

На фазі розпізнавання диктор вимовляє будь-яке невідоме слово з обумовленого словника і записуємо відповідний мовний сигнал. Після його попереднього опрацювання отримуємо вектор довжиною 256 значень. Підраховуємо по черзі відстань між цим вектором і кожним із 30 еталонних векторів.

Відстань між двома векторами та задають як евклідову відстань: .

Мінімальна із отриманих відстаней визначає відповідь системи розпізнавання.

Точність (якість) розпізнавання оцінюємо процентом правильно розпізнаних слів.

Експерименти показують, що описаний найпростіший розпізнавач мови має точність розпізнавання приблизно 85%. Це не можна вважати задовільним показником.

Що потрібно вдосконалити в розглянутому алгоритмі розпізнавання, щоб покращити точність розпізнавання ?

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

Тому вдосконалений алгоритм розпізнавання слів із невеликого словника повинен задовільняти таким вимогам:

- порівнювати мовні сигнали з урахуванням часових (темпоральних) відмінностей, при потребі вирівнюючи тривалості мовних сигналів;

- враховувати спектральні зміни в мовному сигналі при зміні цього сигналу в часі. Для цього слід, зокрема, виконувати точне попереднє опрацювання мовних сигналів.

Таким вимогам задовольняє алгоритм розпізнавання мовних команд (ізольованих слів), який називають алгоритмом DTW (dynamic time warping - динамічного часового вирівнювання).

Попереднє опрацювання мовних сигналів

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

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

Типова величина одного інтервалу - 25,6 мс. Сусідні інтервали беруться зі зсувом відносно попереднього інтервалу. Вживана величина перекриття інтервалів рівна 10 мс.У результаті попереднього опрацювання кожного з вказаних інтервалів отримуємо вектор з кількох десятків спектральних значень. Блок-схема алгоритму попереднього опрацювання мовного сигналу наведена на рис.. Кроки, які слід виконати для попереднього опрацювання кожного інтервалу мовного сигналу, детально описані далі.

Як приклад розглядаємо мовні зразки, дискретизовані з частотою 16 КГц та з розрядністю 16 біт. Дискретизований мовний сигнал розбиваємо на інтервали тривалістю 25,6 мс, тобто 409 відліків. Інтервали перекриваються зі зсувом на 10 мс (160 відліків).

Рис.9.2. Блок-схема алгоритму попереднього опрацювання мовного сигналу

Далі даються етапи попереднього опрацювання мовних сигналів.

1. Оцифрований (дискретизований у часі та квантований за рівнем) мовний сигнал розбиваємо на блоки по 25.6 мс із зсувом кожні 10 мс , тобто, блоки по 409 відліків кожен блок, із зсувом на 160 відліків.

2. Як правило, застосовують високочастотне підсилення, щоб компенсувати послаблення, спричинене розсіюванням від губ. Для цього блоки сигналу пропускають через фільтр першого порядку

S(1)=0; S(n)=y(n)-y(n-1), n=2…409,

де y_n – n-і відлік у блоці.

3. Для опрацювань такого типу до кожного блоку застосовують функцію вікна. У даному випадку береться вікно Гемінга згідно з таким виразом

D(n)=(0,54-0,46·cos(2p·(n-1)/408))·S(n) для n =1,...,409.

4. Щоб отримати спектральні оцінки використовується дискретне перетворення Фур’є. У цьому разі збільшуємо довжину блоку до 512 елементів за рахунок доповнення його справа потрібною кількістю нулів. Після цього застосовуємо швидке перетворення Фур’є довжиною 512 точок і отримуємо 512 спектральних комплексних значень. Оскільки 512 значень, до яких застосовуємо перетворення Фур’є, є дійсними, то отримані спектральні комплексні значення попарно спряжені: друге значення з 512-м, третє – з 511-м і т.д. Тому останні 256 комплексних значень перетворення ігноруємо, бо вони комплексно спряжені з попередніми і не несуть нової інформації.

5. Для перших 256 комплексних спектральних значень знаходимо їх амплітуди. Амплітудний спектр Фур’є згладжується (усереднюється) додаванням амплітуд спектральних коефіцієнтів у межах “трикутних” частотних смуг розташованих на нелінійній (подібній до логарифмічної) Mel-шкалі. Для граничної частоти мови рівної 16 КГц беруть 24 таких частотних смуги. Mel-шкала введена для наближення частотного розділення людського вуха, яке є лінійним до 1000 Гц та логарифмічним понад 1000 Гц.

Фур’є спектр згладжувався додаванням 255 останніх спектральних коефіцієнтів ( перший коефіцієнт – постійна складова спектру ігнорувався) у межах “трикутних” частотних смуг розташованих на нелінійній (подібній до логарифмічної) Mel-шкалі.

Перший амплітудний коефіцієнт – постійну складову спектру – ігноруємо, , а амплітуди решти 255 спектральних значень усереднюємо. Усереднення реалізуємо як 24 трикутні смугопропускні фільтри. Нижня, середня та верхня частоти таких смуг подані в табл.

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

256 амплітудам відповідають частоти від 0 Гц до 8000 Гц, тобто крок пересування дорівнює 8000/256=31,25 Гц. Це означає, що першій амплітуді відповідає частота 0 Гц, другій – 31,25 Гц, третій – 62,5 Гц і т.д.

Наприклад, для першої смуги частот Mel-шкали: нижня частота – 0 Гц, середня частота – 74,24 Гц, верхня частота – 156,4 Гц.

Отже, в першу смугу частот потрапляють перша (0 Гц), друга (31,25 Гц), третя (62,5 Гц), четверта (93,75 Гц), п’ята (125 Гц) та шоста (156,25 Гц) амплітуди.

Згідно з рис. третій амплітуді відповідає коефіцієнт рівний 62,5/74,24≈0,84; а п’ятій амплітуді – коефіцієнт рівний (156,4-125)/(156,4-74,24) ≈0,38.

Таблиця 9.1. Mel-шкала частот

У результаті описаних дій отримуємо 24-елементний спектральний (акустичний) вектор.

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

Для моделювання алгоритму попереднього опрацювання мовних сигналів вибрано середовище MATLAB.

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

Графічне вікно середовища MATLAB 6.5, у якому ілюструються етапи 1-5 попереднього опрацювання мовного сигналу показано на рис.9.3.

На першій ілюстрації показано мовний сигнал example.wav, дискретизований з частотою 16 КГц та розрядністю 16 розрядів.

На другій ілюстрації маємо один блок (інтервал) вказаного мовного сигналу тривалістю 25,6 мс. Такому блоку відповідає 409 відліків.

На третій ілюстрації бачимо один блок мовного сигналу після опрацювання його фільтром першого порядку.

Четверта ілюстрація показує нам один блок після застосування вікна Гемінга.

П’ята ілюстрація дає нам 512 амплітудних значень швидкого перетворення Фур’є цього одного блоку.

Оскільки ці амплітудні значення швидкого перетворення Фур’є попарно співпадають (бо відповідні комплексні значення швидкого перетворення Фур’є є попарно комплексно спряжені), то можна взяти лише 256 перших амплітудних значень. Ці 256 амплітудних значень відображені на шостій ілюстрації.

Сьома ілюстрація дає значення 24-елементного вектора, компоненти якого отримані після усереднення 256 амплітудних значень у межах 24 “трикутних” частотних смуг.

9.2. Алгоритм динамічного часового вирівнювання для розпізнавання слів з невеликого словника

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

Сигнал, який розпізнаємо, та сигнали-еталони параметризуємо – перетворюємо в послідовність спектральних векторів. Для цього розбиваємо сигнал на послідовні інтервали по 25,6 мс з перекриттям на 10 мс.У результаті попереднього опрацювання кожного з інтервалів отримуємо вектор з 24 спектральних значень. Кроки, які слід виконати для попереднього опрацювання кожного інтервалу мовного сигналу, детально описані раніше.

Рис. 9.3. Етапи попереднього опрацювання мовного сигналу

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

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

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

Рис. 9.4. Матриця відстаней для сигналу і одного еталону

Наведені в матриці відстані d_ij між векторами сигналу і векторами еталону – це евклідові відстані між відповідними векторами. Їх значення задаються таким виразом:

, i=1,2,….,I; j=1,2,…,J

Базуючись на отриманій матриці відстаней, будуємо матрицю (граф) шляхів. Побудова матриці шляхів для сигналу і одного еталону наведена на рис.9.5.

Рис. 9.5.Матриця шляхів для сигналу і одного еталону

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

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

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

Рис.9.6. Модель утворення слова

- вектору сигналу а₁ ставимо у відповідність вектор b₁ еталону (відстань між цими векторами дорівнює d₁₁, її беремо з раніше підготовленої матриці відстаней);

- вектору сигналу а₂ ставимо у відповідність вектор b₁ еталону;

- вектору сигналу а₃ ставимо у відповідність вектор b₂ еталону;

- вектору сигналу а₄ ставимо у відповідність вектор b₃ еталону;

- вектору сигналу а₅ ставимо у відповідність вектор b₃ еталону;

- вектору сигналу а₆ ставимо у відповідність вектор b₄ еталону;

- вектору сигналу а₇ ставимо у відповідність вектор b₅ еталону;

- вектору сигналу а₈ ставимо у відповідність вектор b₅ еталону;

- вектору сигналу а₉ ставимо у відповідність вектор b₆ еталону;

- вектору сигналу а₁₀ ставимо у відповідність вектор b₆ еталону;

- вектору сигналу а₁₁ ставимо у відповідність вектор b₆ еталону.

За такими правилами будуємо всі можливі шляхи. Для кожного шляху підраховуємо сумарну відстань як суму евклідових відстаней між парами векторів, пов’язаних з відрізками шляху.

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

Формально рух по матриці шляхів описуємо наступним чином (далі наведено первинний фрагмент матриці):

Найменша сумарна відстань S(i,j) від точки (0,0) до точки (i,j) дорівнює

,

де S(i-1,j-1) – найменша сумарна відстань від точки (0,0) до точки (i-1,j-1);

S(i-2,j-1) – найменша сумарна відстань від точки (0,0) до точки (i-2,j-1);

d₁ - відстань між векторами, які відповідають відрізку, що з’єднує точки (i-1,j-1) та (i,j);

d₂ - відстань між векторами, які відповідають відрізку, що з’єднує точки (i-2,j-1) та (i-1,j);

d₃ - відстань між векторами, які відповідають відрізку, що з’єднує точки (i-1,j) та (i,j);

Для отримання наведеного виразу застосовуємо так званий принцип оптимальності Белмана. Згідно із цим принципом (основним принципом динамічного програмування) будь-який підшлях оптимального шляху має бути оптимальним.

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

Модель утворення слова можна ускладнити: деякі вектори еталону дозволяється перестрибувати (пропускати), як показано на рис.

Рис.9.7. Ускладнена модель утворення слова

Тоді шляхи складатимуться з діагональних, вертикальних або горизонтальних відрізків. Горизонтальний відрізок означає пропускання вектора еталону. Перевага такого варіанту: при записування мовних сигналів-еталонів немає необхідності вимовляти їх якнайкоротше.

Блок-схема алгоритму розпізнавання слів з використанням динамічного часового вирівнювання наведена на рис.9.8.

Отримавши матриці відстаней, будуємо матрицю (граф) шляхів користуючись викладеними далі практичними прийомами.

Спочатку значення всіх елементів матриці шляхів покладаємо рівними

S(u,v)=10000, u =1,.., time; v =1,…, time(k),

де time – кількість спектральних векторів у мовному сигналі, що розпізнаємо,

time(k) - кількість спектральних векторів у k –му мовному сигналі-еталоні (k =1, 2, …, chyslo);

chyslo – число еталонів.

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

Далі обраховуємо tdelta=time-time(k). Обчислене значення є більшим від нуля, бо всі еталони вимовляються коротко, і тому їх довжина завжди менша за довжину сигналу: time>time(k) для k =1, 2, …, chyslo.

Значення відстані S(1,1) в точці (1,1) матриці шляхів береться рівним відстані між першим вектором сигналу і першим вектором зразка:

S(1,1)=d(1,1).

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

Для j=2,…,time(k) беремо значення діагональних елементів матриці шляхів рівними

S(j,j)= S(j-1,j-1)+d(j,j).

Дійсно, оскільки рух по горизонталі заборонений, то дістатися до діагонального елемента (j,j) можна лише від діагонального елемента на місці (j-1,j-1).

Для j=2,…,tdelta+1 беремо значення елементів першого стовпця матриці шляхів рівними

S(i,1)= S(i-1,1)+d(i,1).

Справді, оскільки перед першим стовпцем немає стовпців (бо він перший), дійти до елемента (i,1) першого стовпці можна лише з елемента (i-1,1) першого стовпця. Як бачимо, у першому стовпці не забороняється повторення першого вектора еталону більше, ніж один раз. Зрозуміло чому так. Адже перший вектор еталону – це вектор паузи.

Від другого до передостаннього стовпця (j=2,…,time(k)-1) матриці шляхів виконуємо такі дії.

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

Перший можливий шлях – від елемента (i-1,j-1) по діагоналі до елемента (i,j).У цьому разі до сумарної відстані S(i-1,j-1) в точці (i-1,j-1) додаємо відстань d(i,j) і отримуємо число c₁.

Другий можливий шлях розбивається на два кроки. Спочатку від елемента (i-2,j-1) рухаємось по діагоналі до елемента (i-1,j). Потім від елемента (i-1,j) рухаємось по вертикалі до елемента (i,j).

Під час першого кроку до сумарної відстані S(i-2,j-1) в точці (i-2,j-1) додаємо відстань d(i-1,j). Під час другого кроку до отриманої на попередньому кроці відстані додаємо d(i,j). У результаті отримуємо:

c₂= S(i-2,j-1)+ d(i-1,j)+ d(i,j).

Значення матриці шляхів у точці (i,j) беремо рівним меншому з чисел c₁, c₂:

s(i,j)=min(c₁, c₂).

Вектор еталону від третього до передостаннього стовпця не можна повторювати більше одного разу підряд.

Рух по останньому стовпцю матриці шляхів є специфічним. Дозволяється прийти до елемента в цьому стовпці по діагоналі або по вертикалі. Тобто, в кінці матриці шляхів дозволяється багатократно повторювати останній вектор еталону, який є вектором паузи.

Алгоритм розпізнавання включає в себе такі блоки:

Введення диктором мовних зразків із вибраного словника. У цьому блоці диктор вводить мовні зразки тих слів української мови, які потім система розпізнавання зможе розпізнати. Тобто тут задаються можливі варіанти слів, з яких система буде вибирати при розпізнаванні.

Попереднє опрацювання к-го сигналу-еталону. Виконується згідно з описом, наведеним раніше.

Рис. 9.8. Блок-схема алгоритму DTW розпізнавання слів

Рис. 9.8. Блок-схема алгоритму DTW розпізнавання слів (закінчення)

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

Запис мовного сигналу в звуковому редакторі. Використовуємо вікно звукового редактора Cool Edit для запису мовного сигналу, що потім повинен розпізнаватися. Для цього використовується мікрофон, підключений до звукової плати. Після запису мовного сигналу з відповідною частотою дискретизації та розрядністю без усякого редактування він дається на розпізнавання.

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

Побудова матриці відстаней між векторами сигналу та k-го зразка. Обчислюються евклідові відстані між усеможливими парами векторів, де перший елемент пари – це довільний вектор сигналу, що розпізнається, а другий елемент пари – це довільний вектор к-го сигналу-еталона. Розмір матриці відстаней дорівнює time x time(k), де time – кількість векторів мовної команди, що розпізнається, а time(k) – кількість векторів k -го мовного сигналу-еталона.

Задання початкових умов для матриці шляхів. Усі елементи матриці шляхів на початку покладаються рівними достатньо великому числу 10000. Оскільки подальші кроки пов’язані із знаходженням мінімумів, то такі присвоєння не вплинуть на отримання правильного результату.

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

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

Обчислення решти стовпців матриці шляхів. Елементи від третього до передостаннього включно стовпців матриці шляхів обчислюються з урахуванням двох можливих підшляхів на матриці і вибору коротшого (в сенсі евклідової відстані) з них. Такі варіанти описані на початку цього підрозділу.

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

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

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

Для моделювання цього алгоритму (його реалізації та виконання експериментів для з’ясування точності розпізнавання) вибрано середовище MATLAB.

Для роботи із звуками (у даному випадку для запису та редактування мовних сигналів-еталонів та довільних мовних сигналів) використовувалися професійний звуковий редактор COOL EDIT фірми Sintrillium Software Corporation, навушники і мікрофон.

Cool Edit є цифровим аудіо редактором для операційної системи Windows. Його, зокрема, можна використати щоб записати та програти файли з широкого набору аудіо форматів, відредактувати файли і змішати їх докупи, а також конвертувати файли з одного формату в інший.

Таким чином, робоче середовище, яке використовувалось при виконанні експериментів складалось із головного вікна програми MATLAB 6.5 та вікна професійного звукового редактора Cool Edit. Вигляд цього робочого середовища наведений на рис.9.9.

Рис. 9.9. Робоче середовище для розпізнавання слів із невеликого словника

Виконувалися експерименти з розпізнавання з використанням алгоритму динамічного часового вирівнювання 10 ізольованих слів (назви цифр від 0 до 9: ноль, один, два, три, чотири, п’ять, шість, сім, вісім, дев’ять). Коротко (як тільки можливо) вимовлені ці слова слугували еталонами для розпізнавання. Приклади отриманих після навчання на конкретного диктора сигналів-еталонів наведені на рис. Для цих еталонів виконано попереднє опрацювання. Кількість акустичних векторів у цих еталонах наведена в табл.9.2.

Таблиця 9.2. Кількість звукових векторів для еталонів слів

Далі вимовлялися вказані слова в довільному порядку. Кількість акустичних векторів у мовних сигналах, які фігурували в експериментах, наведена в табл.9.3.

Таблиця 9.4. Кількість звукових векторів для мовних сигналів слів

Зауважимо, що слова вимовлялися в різному темпі та з різною гучністю.

Отримано практично 100% точність розпізнавання.

Потім був змінений диктор: також отримано практично 100% точність розпізнавання.

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

Якщо брати зразки від одного диктора, а потім намагатися розпізнавати слова іншого диктора, то система починає робити помилки. Точність розпізнавання падає до 75-85%. Така точність уже є неприйнятною для більшості практичних застосувань. Щоб покращити точність розпізнавання у цьому разі треба було записувати зразки від кількох дикторів і потім всі отримані зразки використовувати при розпізнаванні.

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

Сигнал записаний в звуковому професійному редакторі Cool Edit. У цьому разі слово “чотири” вимовлялося диктором якомога коротше (у швидкому темпі). Частота дискретизації сигналу-еталона – 16 КГц. Розрядність сигналу-еталона – 16 розрядів. Після того, як сигнал був записаний, у ньому вручну на початку і вкінці викинуто паузи. Ці паузи обов’язково присутні в мові людини. З точки зору проведення подальшого розпізнавання їх слід викинути.

Кількість відліків для наведеного на рис.4.5 сигналу-еталона дорівнює 7139 відліків.

Рис.9.5. Сигнал-еталон слова “ноль”

Сигнал записаний в звуковому професійному редакторі Cool Edit. У цьому разі слово “ноль” вимовлялося диктором якомога коротше (у швидкому темпі). Частота дискретизації сигналу-еталона – 16 КГц. Розрядність сигналу-еталона – 16 розрядів. Після того, як сигнал був записаний, у ньому вручну на початку і вкінці викинуто паузи. Ці паузи обов’язково присутні в мові людини. З точки зору проведення подальшого розпізнавання їх слід викинути.

Кількість відліків для наведеного на рис. сигналу-еталона дорівнює 3725 відліків.

Сигнал записаний в звуковому професійному редакторі Cool Edit. У цьому разі слово “вісім” вимовлялося диктором якомога коротше (у швидкому темпі). Частота дискретизації сигналу-еталона – 16 КГц. Розрядність сигналу-еталона – 16 розрядів. Після того, як сигнал був записаний, у ньому вручну на початку і вкінці викинуто паузи. Ці паузи обов’язково присутні в мові людини. З точки зору проведення подальшого розпізнавання їх слід викинути.

Кількість відліків для наведеного на рис. сигналу-еталона дорівнює 6292 відліків.

Як бачимо з рисунку, на початку і вкінці реального сигналу, який розпізнається, є паузи. Пауза на початку сигналу рівна приблизно 0,3 с, а пауза вкінці сигналу рівна наближено 0,25 с. Система розпізнавання дала відповідь, що сигнал, який розпізнавався, це слово “вісім”. Можна порівняти рис. з рис. (сигнал-еталон слова “вісім”). Кількість відліків у сигналі суттєво більша порівняно з сигналами-еталонами і дорівнює 19538 відліків.

Рис.9.6. Сигнал-еталон слова “чотири”

Рис.9.7. Сигнал-еталон слова “вісім”

Приклад, сигналу для якого виконувалося розпізнавання, наведений на рис.9.8.

Рис.9.8. Сигнал, що розпізнавався

9.3. Розпізнавання злитної мови з великим словником

Сучасні системи для розпізнавання злитної мови з великим словником ґрунтуються на принципах статистичного розпізнавання образів.

На першому етапі мовний сигнал перетворюється звуковий препроцесором на послідовність спектральних векторів Y=y₁,y₂,…,y_T, як описано раніше. Кожен вектор є стислим поданням короткочасного мовного спектру на інтервалі, як правило, близько 25 мс зі зсувом інтервалів на 10 мс. Типова фраза з десяти слів по 6-7 звуків у кожному може мати тривалість біля 3 с і зображатися послідовністю з T=300 спектральних векторів.

У загальному, фраза складається з послідовності слів . Робота системи розпізнавання полягає у визначенні найбільш імовірної послідовності слів , маючи мовний сигнал Y. Для цього використовується правило Байєса:

.

Ця рівність показує, що для знаходження найбільш правдоподібної послідовності слів W, повинна бути знайдена послідовність, що робить максимальним добуток P(W) та P(Y|W).Так як знаменник P(Y) не залежить від W, то його при розпізнаванні ігнорують.

Перший із співмножників представляє апріорну ймовірність спостереження W незалежно від спостереження мовного сигналу. Ця ймовірність визначається моделлю мови.

Другий співмножник представляє ймовірність спостереження послідовності векторів Y при заданій послідовності слів W. Ця ймовірність визначається звуковою моделлю.

На рис.9.9 наведена структура типової системи статистичного розпізнавання. Вона включає чотири складових.

Рис.9.9. Структура системи розпізнавання мови

Розглянемо кожну з цих чотирьох складових більш детально.

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

Звукова модель. Мета звукової моделі – дати метод обчислення правдоподібності P(Y|W) будь-якої послідовності звукових векторів Y при заданій послідовності слів W.

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

Замість цього послідовності слів розбиваються на базові “будівельні” блоки (звуки), які називаються фонемами.

Кожна фонема зображається прихованою моделлю за Марківим (англійська назва – hidden Markov model (HMM)). HMM-модель складається з низки станів, з’єднаних дугами. HMM-модель фонеми, як правило, має три породжуючих стани (рис.). Формальні вхідний і вихідний стани дозволяють об’єднувати моделі фонем, щоб утворювати слова і об’єднувати слова з метою отримати фрази.

Рис.9.10. HMM-модель фонеми

HMM простіше зрозуміти як генератор послідовностей спектральних векторів. Це автомат зі скінченним числом станів, який змінює свій стан у кожний дискретний момент часу. Коли в момент часу t він переходить у стан j , утворюється спектральний вектор y_t з щільністю ймовірності b_j(y_t). Більш того, перехід із стану i в стан j також імовірнісний і задається дискретною ймовірністю a_ij. Рис. дає приклад цього процесу, коли модель проходить послідовність станів X=1,2,2,3,4,4,5 і утворює послідовність векторів Y=y₁,y₂, y₃, y₄, y₅.

Сумісна ймовірність послідовності векторів Y та послідовності станів X при певній заданій моделі M обчислюється просто як добуток ймовірностей переходів та ймовірностей виходів. Тобто, для послідовності станів X на рис.

P(Y,X|M)=a₁₂·b₂(y₁)·a₂₂·b₂(y₂)·a₂₃·b₃(y₃)·a₃₄·b₄(y₄)·a₄₄·b₄(y₅)·a₄₅

Більш загально, сумісна ймовірність послідовності векторів Y та деякої послідовності станів X=x(0),x(1),x(2),…,x(T),x(T+1) дорівнює

де x(0) вхідний, а x(T+1) вихідний стан моделі.

На практиці, звичайно, відома лише послідовність Y, а послідовність X невідома. Ось звідки взялася назва прихована за Марківим модель. Проте, потрібну ймовірність P(Y|M) легко знаходимо додаючи величини P(Y,X|M) для всіх можливих послідовностей станів X. Розроблено ефективний рекурсивний метод виконання цих обчислень, який називається алгоритмом руху вперед-назад. Суттєвою особливістю цього алгоритму є те, що він дозволяє обчислити ймовірність перебування в заданому стані моделі в заданий момент часу. З нього випливає дуже проста і ефективна процедура Баума-Велча знаходження за критерієм максимальної правдоподібності оцінок параметрів a та b моделі. Слід зауважити, що поява процедури Баума-Велча стала ключовим фактором домінування HMM в звуковій моделі.

Вважається, що наведене рівняння треба переписати в логарифмічній формі та розділити члени a і b

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

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

,

де c_jv - вага v–го доданка для j–го стану; G(y_t,μ_jv,Σ_jv) позначає багатовимірний розподіл Гауса з середнім вектором μ_jv та коваріаційною матрицею Σ_jv рівний

n означає розмірність спектральних векторів, | | - визначник матриці, T – транспонування вектора.

Приблизно 10 компонент лінійної комбінації дають добрі показники для системи розпізнавання.

На ранній стадії досліджень вважалося, що вимагається лише одна HMM для кожної фонеми.

Число фонем в українській мові рівне 38. Здавалось би, потрібно здійснити навчання лише 38 HMM-моделей. На практиці, проте, контекстні ефекти спричиняють значні зміни у способі утворення звуків (так зване явище коартикуляції). Тому, щоб досягти доброго фонетичного розрізнення, треба навчати різні HMM для різних контекстів.

Найбільш загальним є підхід з використанням трифонів, коли кожна фонема має окрему HMM-модель для кожної індивідуальної пари сусідів зліва та справа. В останніх публікаціях згадується і про використання квінфонів (сукупностей 5 сусідніх звуків: два сусіди зліва і два сусіди справа).

Наприклад, нехай позначення x-y+z представляє фонему y, що трапилась після x і перед z. Тоді фраза “Цей комп’ютер” подається послідовністю фонем È ц е і к о м п і у т е р È, де È позначає паузу. Якщо використовуються HMM-моделі трифонів, то фраза буде описуватися так:

È-ц+е ц-е+і е-і+к і-к+о к-о+м о-м+п м-п+і п-і+у і-у+т у-т+е т-е+р е-р+È

При 38 фонемах є 38³=54872 можливих трифони, проте не всі трапляються через обмеження української мови.

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

Перед тим, як HMM може бути застосована, повинні бути визначені її параметри. Цей процес називають навчанням. Він вимагає три елементи.

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

Для англійської мови існує багато загальнодоступних баз даних мовних зразків (ISOLET, CONNEX,Resource Management Database, Wall Street Journal Database та інші). Створення таких баз даних для української мови є завданням на часі.

Як для української, так і для англійської мов, завданням є якнайкраще розбиття мовного запису на фонеми відповідно до тексту.

2 Цільову функцію, яка разом з навчальною базою даних може бути використана, щоб поміряти “відповідність” HMM. Найбільш широко вживаною є цільова функція максимальної правдоподібності:

O - повна множина спектральних векторів усіх навчальних речень;

O_u - спектральні вектори u-го навчального речення;

W_u - синтезована HMM-модель для u -го навчального речення

λ – множина параметрів HMM-моделей усіх навчальних речень;

λ_u - множина параметрів HMM-моделі для u -го навчального речення.

3. Процедуру оптимізації, яку можемо використати, щоб максимізувати цільову функцію.

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

Таким чином, навчання звукової моделі зводиться до послідовним ітерацій, на кожній з яких перераховуємо всі параметри HMM-моделей усіх навчальних речень. Ітерації припиняємо, коли різниця двох послідовних значень цільової функції стає меншою від наперед заданої величини.

Звідки взяти початкові значення (до початку навчання) параметрів моделей усіх навчальних речень?

Один можливий варіант: вручну розбити невелику кількість навчальних речень на окремі фонеми та їх стани, і за рахунок цього отримати певні початкові оцінки параметрів (виходячи з 38 різних звуків).

Інший, ширше вживаний сьогодні варіант, так званого плоского старту: взяти як початкові значення парметрів будь-які теоретично можливі їх значення.

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

Ця проблема настільки серйозна, що використовуються додаткові еврістичні обмеження:

1.Розподіли ймовірностей появи звукових векторів для різних станів моделей можуть бути зв’язані, тобто користуватися тими самими параметрами. Звичайно це корисно лише тоді, коли вони представляють подібні звукові ситуації.

2.Коваріаційна матриця розподілів припускається діагональною.

3.Число розподілів Гаусса, сума яких моделює розподіл імовірностей для стану, може змінюватися, щоб досягти найкращого балансу між гнучкістю моделювання і складністю.

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

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

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

У результаті такого зв’язування замість 38³=54872 трифонів отримуємо 2000–8000 зв’язаних трифонів.

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

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

Простий, але ефективний шлях зробити це – використати N-ки слів, у яких приймається, що дане слово w_k залежить лише від попередніх N-1 слів, тобто

.

N-ки слів одночасно мають у собі граматику, смисл і предметну область та зосереджуються на локальних залежностях. Більш того, розподіли ймовірностей для N-ок можна обчислити прямо з текстових навчальних даних. Тому не потрібно мати такі точні лінгвістичні правила, як формальна граматика мови.

У принципі, N-ки можна оцінити простим підрахунком частоти повторюваності слова в навчальних текстах і зберігати ці дані в таблицях. Наприклад, для випадку трійок слів (N=3)

де t(w_k,w_k-1,w_k-2) число появ трійок w_k,w_k-1,w_k-2 в навчальних даних та b(w_k-1,w_k-2) число появ двійок слів w_k-1,w_k-2.

Проблема полягає в тому, що при словнику V слів є V³ можливих трійок. Навіть для помірного словника в 10000 слів це дуже велике число. Тому багато трійок не з’явиться в навчальних даних, а багато інших з’явиться лише раз чи двічі. Внаслідок цього отримані для них згідно з наведеним виразом оцінки будуть нереальними.

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

Класифікатор (декодер). Ця складова системи зводить воєдино дані від трьох раніше описаних компонент і знаходить найбільш імовірний текст (транскрипцію).

Як правило, усі можливі гіпотези відслідковуються паралельно. Цей підхід спирається на принцип оптимальності Белмана (динамічного програмування) і його часто називають алгоритмом Вітербі.

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

а)

б)

в)

Рис.9.11.

Замінимо кожне слово в цьому дереві послідовністю моделей згідно з його вимовою. Якщо є кілька можливих вимов, то можна дати паралельне з’єднання моделей в межах слова. Рис. б) показує фрагмент дерева, деталізованого введенням моделей. Нарешті, зіллємо моделі однакових фонем або фонем, які за рахунок зв’язування потрапили в одну групу. Це проілюстровано на рис. в).

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

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

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

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

Ескіз програмної реалізації системи розпізнавання злитної мови з великим словником можна, зокрема, знайти за адресою www.isip.msstste.edu.

Читайте також:

1. D і 3D технології креслення в AutoCAD
2. OLAP-Технології
3. PR-ІНСТРУМЕНТАРІЙ І МАНІПУЛЯТИВНІ ТЕХНОЛОГІЇ
4. PR-технології у виборчій кампанії.
5. PR-технології.
6. Web-технології
7. Абсолютні синоніми (наприклад, власне мовні й запозичені) в одному тексті ділового стилю вживати не рекомендується.
8. Алгоритмічна конструкція повторення та її різновиди: безумовні цикли, цикли з після умовою та з передумовою.
9. Багатомовні бібліотеки
10. Варіантне проектування технології зведення будівель та споруд.
11. Вартість Internetу для підприємств-користувачів. Internet-технології та формування бізнес-фокусу споживача.
12. Виборчі технології як найважливіша складова ПР

Переглядів: 2347