Автоматные методы распознавания речи тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ВВЕДЕНИЕ.

ГЛАВА 1. ФОРМАЛЬНАЯ МОДЕЛЬ РЕЧИ.

1.1 Речь как математический объект. Основные определения.

1.2 Дискретизация.

1.3 Формализация задачи распознавания речи. Функция качества словаря команд.

ГЛАВА 2. ДЕТЕРМИНИРОВАННЫЕ АВТОМАТНЫЕ МОДЕЛИ.

2.1 Метод решения задачи локального распознавания речи.

2.2 Модель распознавания последовательного кода команды с помощью детерминированных автоматов.

2.3 Модель и алгоритм распознавания кода команды для случая классов звуков. Нижняя оценка качества словаря команд.

ГЛАВА 3. ВЕРОЯТНОСТНЫЕ АВТОМАТНЫЕ МОДЕЛИ.

3.1 Понятие монотонного автономного вероятностного автомата. Модель распознавания речи с помощью вероятностных автоматов.

3.2 Метрика pi на множестве стохастических словарных функций.

3.3 Метрика р2 на множестве стохастических словарных функций. Функция качества словаря команд.

3.4 Метрика р3 на множестве стохастических словарных функций.

3.5 Связь между метрикой и вероятностью.

Образное восприятие - одно из свойств мозга, позволяющее правильно воспринимать информацию о внешнем мире. При этом происходит классификация воспринимаемых ощущений, т.е. разделение их на группы похожих образов. Образы обладают тем свойством, что ознакомление с некоторым конечным числом их реализаций дает возможность узнавать все остальные представители образа. Более того, разные люди, обучающиеся на различном материале наблюдений, одинаково распознают одни и те же объекты.

Процессу распознавания образов всегда предшествует процесс обучения, во время которого мы знакомимся с некоторым числом примеров, зная наперед об их принадлежности к каким-то образам. У человека процесс обучения заканчивается успешно. Следовательно, образы - это объективные характеристики внешнего мира, а не произвольные наборы изображений. Эту объективную характеристику образов и стремятся выявлять с помощью математических методов. Создаются аппаратные и программные распознающие системы, на вход которых подается информация о предъявляемых объектах, а на выходе отображается информация о классах, к которым отнесены распознаваемые объекты.

Две фундаментальные гипотезы, лежащие в основе работы большинства систем автоматического распознавания речи (АРР), заключаются в следующем ([1, 6]):

1) информация в речевом сигнале переносится в виде изменений во времени его амплитудного спектра

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

Все это позволяет эффективно использовать автоматные методы[34] для описания речевых сигналов.

При этом решаются задачи синтеза порождающих образ автоматов (детерминированных и вероятностных), распознавания объектов, оценки сложности этих алгоритмов. Заметим, что участвующие в задании объектов массивы чисел хотя и конечные, но необозримые, и не представляется возможным хранение достаточного запаса примеров этих объектов. К примеру, одна секунда речевой записи занимает около 10000 байт, а сами примеры этих записей, как бы мы их не накапливали, не только не повторяются и не обладают близостью в 10000-мерном пространстве, но даже имеют принципиально разную длину.

Практически все известные методы распознавания речи обладают рядом основных общих свойств:

- для распознавания используется метод сравнения с эталонами;

- сигнал может быть представлен либо в виде непрерывной функции времени, либо в виде слова в некотором конечном алфавите;

- для сокращения объема вычислений используются методы динамического программирования.

Методы распознавания речи можно условно разделить на две большие группы — непараметрические — с использованием непараметрических мер близости к эталонам (к ним можно отнести методы на основе формальных грамматик и методы на основе метрик на множестве речевых сигналов) и параметрические (вероятностные - на основе скрытых марковских моделей, нейросетевые).

Первые разработки в области создания устройств автоматического распознавания речи можно отнести к концу 40-х годов прошлого столетия. Первые устройства ([2, 3, 4]) были аналоговыми и использовали пороговую логику. Исследователи сразу же столкнулись с тем, что распознавание речи — достаточно сложная задача в силу неравномерности растяжения речевых сигналов во времени и сложной связи сигнала с фонемной структурой произносимой речи. В силу этого первые системы распознавания речи не обладали высокой надежностью и были узкоспециализированными.

Ситуация резко изменилась к началу 70-х годов в результате послевоенного развития электроники и вычислительной техники и появления лингвистической теории речи, представляющей устную речь как производную фонетической транскрипции произносимого текста. К числу первых проектов такого рода можно отнести проект Агентства перспективных исследовательских работ ARPA ([5]). В этих системах сигнал разбивался на сегменты, которые обозначались фонемоподобными символами, а затем получившийся код сигнала распознавался с помощью формальных грамматик. Узким местом такого подхода оказалось то, что сегментация и локальное распознавание является задачей, трудно поддающейся точному автоматическому решению, несмотря на то, что человек с этой задачей вполне справляется ([7]).

Следующим этапом в развитии теории распознавания речи стало развитие непараметрических систем, основанных на мерах близости на множестве речевых сигналов как функций времени. Революционный вклад в развитие этого направления оказал подход Винцюка (1960-е г.г., [8]), предложившего использовать новый для того времени метод динамического программирования (Беллман, 1950-е г.г. [9]) для быстрого вычисления меры близости между двумя функциями, задающими изменение во времени параметров речевых сигналов. Подход Винцюка, развитый Итакурой ([10]) и другими исследователями, позволил сократить время вычисления значений функции близости к эталонам с экспоненциального (от длины сигнала) до квадратичного. В силу того, что основной спецификой метода являлось нелинейное искажение временной оси одной из сравниваемых функций, метод получил название «динамической деформации времени» (ДДВ).

Метод ДДВ обладает рядом достоинств и недостатков. К очевидным достоинствам метода относятся простота его реализации и обучения -для работы метода достаточно в качестве эталона команды использовать одно из ее произнесений. Основным недостатком метода является сложность вычисления меры близости (пропорционально квадрату длины сигнала) и большой объем памяти, необходимый для хранения эталонов команд (пропорционально длине сигнала и количеству команд в словаре).

Ряд исследователей (Бейкер — CMU — система «Драгон» [И] и, независимо, Йелинек — IBM [12], 1970-е годы) для распознавания речи применили теорию скрытых марковских моделей (СММ, скрытых марковских процессов, вероятностных функций цепей Маркова), созданную Баумом и коллегами в конце 60-х - начале 70-х г.г ([13]). Скрытые марковские процессы представляют из себя дважды стохастические процессы — марковские цепи ([14]) по переходам между состояниями и множества стационарных процессов в каждом состоянии цепи. Основы теории СММ были опубликованы в ряде научных журналов ([13,19]), однако получили развитие среди разработчиков систем распознавания речи лишь после выхода серии обзоров, посвященных популярному изложению теории СММ ([15-18]). Для обучения моделей и вычисления функции близости к эталону (здесь — вероятности наблюдения слова на выходе СММ) был также применен метод динамического программирования (алгоритмы прямого-обратного хода [19], Баума-Уэлча, или ЕМ-алгоритм [20], Виттерби [21-22]).

Достоинствами метода СММ являются достаточно быстрый способ вычисления значений функции расстояния (вероятности) и существенно меньший объем памяти, необходимый для хранения эталонов (пропорционально количеству фонем, Трифонов и т.п. в языке), а основными недостатками — достаточно большая сложность его реализации, а также необходимость использования больших фонетически сбалансированных речевых корпусов (баз данных) для обучения параметров СММ. Последнее обстоятельство привело к тому, что вплоть до начала 90-х годов методы ДДВ были более эффективными и точными при решении практических задач, чем методы СММ.

В настоящее время распознавание речи на основе СММ переживает период бурного роста. Десятки крупных коммерческих компаний (IBM, Dragon, L&H, Philips, Microsoft, Intel.) создали и активно развивают коммерческие системы распознавания речи. Эксперты в области компьютерных технологий называют распознавание речи одной из важнейших задач XXI века.

Основными характеристиками современных систем АРР являются следующие: словари размером в десятки тысяч слов; распознавание слитной речи; возможность работы как с предварительной настройкой на голос диктора, так и без настройки; надежность работы 95-98%.

СММ, возникшие как обобщение цепей Маркова, тесно связаны с понятием вероятностного автомата. Вероятностные автоматы, впервые введенные в общей форме Дж Карлайлом (1963, [23]) и, независимо от него, Р.Бухараевым (1964, [24]) и П.Штарке (1965, [25]), представляют из себя в практическом плане устройства с конечной памятью, перерабатывающие информацию с входных каналов в выходные, переходы и выходы которых происходят на основе вероятностных законов ([26]). Скрытые марковские модели являются частным случаем вероятностных автоматов, а именно, вероятностными автоматами без входа. СММ, используемые в системах распознавания речи, обладают дополнительно тем свойством, что на каждом такте работы автомата переход осуществляется в состояние с тем же или большим номером. Такие модели, предложенные впервые Бакисом ([27, 12]), называются лево-правыми (left-right), или моделями Бакиса. Автор предложил при изложении на автоматном языке называть соответствующие этим моделям вероятностные автоматы монотонными.

Распознавание речи с помощью автономных монотонных вероятностных автоматов сводится к следующему. Каждой речевой команде сопоставляется эталон в виде вероятностного автомата. Вычисляется вероятность наблюдения распознаваемого кодового слова на выходе каждого из таких автоматов, и выбирается автомат, максимизирующий эту вероятность. Соответствующая найденному автомату команда считается результатом распознавания.

Метод СММ на уровне распознавания отдельных команд (т.е. без учета контекстной зависимости слов внутри предложения на естественном языке) дает надежность распознавания, близкую к надежности распознавания речевых команд человеком. Это позволяет сделать вывод о том, что общая задача распознавания отдельно произносимых команд решается методом СММ почти с максимально возможной точностью. Тем не менее, в практических приложениях возникает необходимость построения систем распознавания речи с ограниченным словарем, которые должны обладать сравнительно более высокой надежностью работы.

Традиционно эта задача решается методом подбора словаря команд. Подбор словаря может осуществляться путем проведения экспериментов с распознаванием команд из различных словарей и сравнения результатов этих экспериментов, что является «дорогим» решением. Поэтому представляет интерес задача автоматического подбора словаря команд без проведения экспериментов для обеспечения требуемой надежности распознавания.

Для решения этой задачи автор предложил использовать функцию качества словаря команд, связанную со средней вероятностью ошибки при распознавании и вычисляемую непосредственно по эталонам команд без проведения экспериментов с помощью введеннной метрики на множестве монотонных вероятностных автоматов.

В статистике традиционно задача нахождения расстояния между случайными величинами решается на основе статистических мер близости типа расстояний Махаланобиса, Кульбака-Лейбнера, Бхатачария и др. ([30]). Однако, данные метрики не имеют эффективного обобщения на случай вероятностных автоматов. В настоящей работе предлагается новая адекватная метрика, которая вычисляется эффективно.

Целью настоящей работы является построение формальной математической модели для распознавания речи с целью исследования вопроса оценки качества работы различных автоматных алгоритмов распознавания речи для различных словарей команд.

В работе имеются следующие достижения:

1. Предложена формальная математическая модель для задачи распознавания речи, в которой выделены множества (алфавиты букв, звуков, сигналов и кодов) и действующие на них функции (транскрибирования, произнесения, описания, кодирования и распознавания). Данная модель охватывает все случаи распознавания речевых сигналов в произвольных внешних условиях. В эту модель укладывается, в частности, задача распознавания речи при наличии дополнительных неакустических источников речевой информации в условиях шумов.

2. Сформулирована постановка задачи распознавания речи в данной модели и предложена функция для оценки качества словаря команд для фиксированного алгоритма распознавания.

3. Предложен универсальный детерминированно-автоматный алгоритм распознавания в рамках введенной модели, для которого найдена нижняя оценка функции качества словаря команд.

4. Известный метод распознавания речи на основе скрытых марковских моделей переведен на язык вероятностных автоматов.

5. Введено новое понятие автономного монотонного вероятностного автомата. На множестве таких автоматов введены операции декартового и скалярного произведений автоматов и на их основе построена метрика, эффективно вычислимая по автоматам.

6. Введено понятие качества словаря команд для вероятностного случая, получена точная формула для вычисления качества произвольного словаря команд через метрику на множестве монотонных автономных вероятностных автоматов.

В первой главе вводится формальное определение речевой модели как математического объекта. Основой ее является понятие звукового сигнала, под которым понимается функция s : R —> R, непрерывная на некотором отрезке [to,t{\ £ R и принимающая вне этого отрезка нулевые значения. Переходя к дискретному времени, дискретным звуковым сигналом называется любое отображение s' : Z —у R , такое что G Z : s'(z) = 0 \/z ^ [20,21]. Дискретные звуковые сигналы получаются из непрерывных с помощью операции дискретизации: s'(z) = s(z • (5), где 5 называется периодом дискретизации. Для простоты далее будем опускать штрих при обозначении звукового сигнала.

Носителем сигнала s : Z R, s ф 0 назовем отрезок [inf{z|s(z) т^ 0},sup{z|s(2:) ф 0}], вне которого он принимает нулевые значения. Границы носителя назовем началом и концом сигнала s соответственно. Определим операцию конкатенации S1S2 сигналов si,s2 с непересекающимися носителями как (s^X^) = max(si(z),s2(z)).

Далее дается понятие речевой модели, отдельно для случая непрерывного и для случая дискретного времени.

Понятие речевой модели в дискретном случае формулируется в определении 1.15. Упрощенно это определение выглядит так:

Речевой моделью называется восьмерка (Б, В, 5, С, d, Г, П, г), где

• В — конечный алфавит звуков;

• В £ В* — конечный словарь команд;

• S — множество дискретных звуковых сигналов — произнесений команд;

• С — конечный алфавит — кодовая книга описаний сигналов;

• П : В —> 2s - функция произнесения (здесь 2s - множество всех подмножеств множества S); П(/3) — множество всех произнесений команды /3;

• d : S —> (RM)* — функция описания речевых сигналов, сопоставляющая речевому сигналу s матрицу М х п, где М - некоторая константа (размерность пространства описаний), а п линейно зависит от длины речевого сигнала. Каждый столбец матрицы описания задает точку в пространстве описаний RM;

• Г : К —> С — кодирующее отображение, сопоставляющее каждому столбцу матрицы описания элемент кодовой книги С. Г естественно обобщается на слова как Г : (Шм)* —У С*;

• г : С* —>■ 2В — функция распознавания, определяемая как г(7) = {/3 € В|7 е r(d(n(/3)))}.

Обозначим через П(&о) множество сигналов, не являющихся произнесениями никаких звуков:

II(bo) = S\|Jn(ft),

Ъев

Будем считать, что функция произнесения П удовлетворяет следующим свойствам:

1. V/ЗеВ П(/3) ф 0;

2. V/3b ft G В А ^ & =» П(&) П П(&) = 0;

3. V/3 G В Vs G П(/3) s ^ 0;

4. У/3 е В : (3 = 6i62.6„ и n > 1 Vs G П(/3)

3s0l, Sl, Sl2, S2j Sn-lnSnSnO € Si s = S0lSlSi2S2.Sn-.inSnSn0, где Sj G n(6i) для г = 1,2, .,тг,

G П(Ь{) U П(bj) U П(Ь0) для i,j = 1,2,n, Sio, «оi G П() U П(bi) U П(Ьо) Для г = 1,2,., п, — специальный символ алфавита (символ паузы) и все сигналы Sj, имеют непересекающие носители.

Как правило, функция описания d строится в виде композиции оконного отображения, вырезающего с постоянным шагом L из сигнала временное окно в общем случае переменной длины, и функции локального описания сигнала, сопоставляющей каждому окну сигнала точку в пространстве описаний Шм.

Образом V(b) С фонемы 6 G В как в непрерывном, так и в дискретном случае называется совокупность всех точек описания всех ее произнесений. Для дискретного случая

V(b) = {ре ЕМ|3</ G d(U(b)) : у = \\у1\у2\.\р\.\уп1\уп\\}, где | j 2/112/21 - - - j 2/тт. |! обозначает матрицу, состоящую из столбцов yi, у2,., уп.

В утверждении 1.6. показано, что для любых допустимых значений периода дискретизации S и шага описания L дискретный и непрерывный образы одной и той же фонемы совпадают. Это, по сути, означает эквивалентность понятий образа фонемы в непрерывном и дискретном случае, что позволяет, ничего не теряя в точности решения задачи, использовать для распознавания речевую модель с дискретным временем.

При этом можно считать, что мы рассматриваем описания сигналов с шагом 1.

Задача распознавания речи во введенной речевой модели состоит в восстановлении функции распознавания г. Содержательно, распознавание речи сводится к тому, чтобы по заданному кодовому слову 7 е С*, про которое известно, что оно является кодом описания произнесения одной из команд словаря В, найти в словаре эту команду.

Задачу распознавания можно решать методом сравнения с эталонами. Пусть каждой команде € В сопоставлен эталон е* - элемент некоторого множества Е = {ei, 62,., едг}. Содержательно эталон команды является компактным способом представления множества кодовых слов всех ее произнесений.

Пусть также на декартовом произведении С* X Е введена функция расстояния р : С* X Е R между кодовыми словами и эталонами. Алгоритм (Е, р) распознавания речи методом сравнения с эталонами восстанавливает функцию распознавания г с помощью формулы Г(Е,Р)Ь) = ArgminpeB(p(7,ei),i = 1,2, .,N). Если г ф г(Е)/э), будем говорить, что имеют место ошибки распознавания.

Качество q(E,p)(B) словаря команд В для данного алгоритма распознавания (Е1, р) естественно определить, как 1 — 2рош.> где рош. - среднее число ошибок распознавания команд из В алгоритмом (Е,р).

Важно заметить, что каждой команде /3 соответствует множество кодовых слов описаний всех ее произнесений Г(с?(П(/3))), которое является конечным подъязыком языка С* всех кодовых слов. Автоматный подход к распознаванию речи состоит в том, чтобы представить язык кодовых слов каждой команды некоторым автоматом. В случае конечно-детерминированных автоматов мы погружаем язык кодовых слов команды в некоторый известный нам бесконечный регулярный язык, а в случае вероятностных автоматов каждому слову языка кодовых слов приписываем некоторое действительное число — его вероятность, что дает нам возможность рассматривать случай пересекающихся языков кодовых слов.

Во второй главе эталоны команд задаюся конечно-детерминированными автоматами. Построен алгоритм распознавания речи на основе конечных детерминированных автоматов, где множество произнесений команды представляется некоторым бесконечным регулярным языком, приведена конструкция автоматического порождения указанных регулярных язкыков, введена функция качества словаря команд и получена нижня оценка значения функции качества в детерминированно-автоматном случае.

Предложен следующий способ построения автоматов.

Пусть пространство описаний сигналов RM разбито на m непересекающихся подмножеств U i=l,m л л

С = {ci, С2,., ст}. Сопоставим каждому элементу с; разбиения С символ q, и выберем алфавит С = {ci, С2,ст} в качестве кодовой книги нашей речевой модели.

Кодирующее отображение будем строить на основе разбиения С. А именно, для каждой точки р £ RM определим Г(р) как Г(р) = с £ С : р £ с. Предположим, что при распознавании мы не умеем вычислять Т(р) для всех точек р £ Шм. Пусть, тем не менее, для А каждой пары элементов разбиения С мы умеем "отличать их друг от друга". Более строго, Л

Отделяющей функцией для двух множеств с;, dj £ С назовем фун-цию TpCiCj : Шм —» С U {?}, такую что Vp £ RM

0° фсс{р) = с;

1° фсъ(р) = Фс^Ар) (симметричность);

2° ^(pjefe.c,-,?};

3° р G Q Фъч(р) G fe, ?};

С помощью функции ф можно построить функцию локального распознавания кода описания сигнала:

Функцией локального распознавания Ф будем называть функцию Ф : Ем —>• 2е7, определенную для каждой точки р G Мм следующим образом: Ф(р) = {с G С : Vc' G С, с' ф с G {с, ?}}.

Множество значений функции Ф порождает регулярный язык "близких "гипотез распознавания кода описания сигнала, описываемый регулярным выражением f(j/) = #(Ф(г/1))Я(Ф(з/2)). Л(Ф(угг)), где матрица у = 112/i 12/21 - - -12/гг)| > а регулярное выражение R определено как R({ai, а2, • •., ато}) = {ai\a2\. \ат).

Обозначим через {%) регулярный язык, описываемый регулярным выражением TZ.

Справедливо Утверждение 2.2. о том, что множество Ф(р) "близ-ких"гипотез локального распознавания содержит всегда "правильную "гипотезу Г(р):

Vpe rm г(р)еФ(р).

Как следствие получаем, что для описания у = d(s) любого сигнала s справедливо Г(з/) G (Г(у))

Говорим, что с G С и с' G С отделимы с помощью отделяющей функции ф, если Vp Е cU с' ф(р) G {с,с'}.

Окрестностью О(С') некоторого подалфавита С' С С кодовой книги С будем называть множество всех букв с из С, не являющихся отделимыми хотя бы от одной буквы алфавита С'.

Обозначим через с{Ь) множество с{Ь) = {с' G С : с' C\V(b) ф 0}.

Свойство 4 функции произнесения П позволяет нам ввести эталоны команд в виде регулярных языков, порождаемых регулярными выражениями специального вида, которые строятся непосредственно по текстам команд.

А именно, эталонным кодом команды /3 = &1&2. Ьп назовем регулярное выражение

Г03) = Л(0(с() U с(6о) U c(bi)))R(0(c(bi)))R(0(c(bi) U с(Ь0) U с(Ь2)))Л(0(с(62))). • ■ • Д(0(с(Ьпх)))Д(0(с(Ьп1) U с (bo) U c(bn)))R(0{c(bn)))R{0(c(bn) U с(Ь0) U с(Ь»))).

Код Г(d(s)) любого произнесения s £ П(/3) команды /3 лежит в эталоне этой команды - регулярном языке (Г(/3)).

Справедлива более сильная теорема 2.1:

В речевой модели, в которой функция произнесения обладает свойствами 1-4, для любой звуковой команды /3 = bfa. .Ъп и описания у = d(s) ее произвольного произнесения s Е П(/3) имеет место вложе-ние (Г(у)) С (Г(f3)}.

Далее во второй главе показано, что если звуки объединить в классы эквивалентности с помощью отношения отделимости, и в качестве разбиения С пространства описаний рассмотреть образы этих класов при отображении d о Г, то каждый язык гипотез распознавания (Г(у)) будет состоять ровно из одного элемента - кодового слова Г (у).

Теперь автоматный алгоритм (Е, р) распознавания речи в модели (В, В, S, С, d, Г, П, г) можно задать множеством эталонов Е = {е\, еч, •. •, е ег- = (Г(Д)), и функцией расстояния р, определяемой для кодового слова 7 = Г(ф)),веП(А) как:

10, если 7 е ei 7) = <

I 1, иначе

Результат распознавания кодового слова 7 алгоритмом (J51, /э) есть множество команд г^р) (7) = {/3 G B\j Е (Г(/3))}.

Справедливо утверждение 2.4 о том, что в условиях модели для любого кодового слова 7 имеет место вложение г (7) С r^E,p)(l)

Функцию качества словаря для введенного детерминированно-авто-матного алгоритма распознавания (Е, р) определим следующим образом. Если словарь В состоит из одного слова (3, то положим, что его качество равно 1 (естественно предположить, что в словаре из одной команды распознаватель не делает ошибок). Для каждого словаря В = {/3,(3'}, состоящего из двух команд, определим функцию качества как

Е 1гомМ1

Q я'\ О 7€Г(<*(П(/3)иП(/3'))) Я{Е,р){Р,Р) = 2 тщр)ищ/з>т

Пусть S — некоторое конечное множество, / : S х S ~> R. Обозначим через Qs(f) среднее значение функции / на S х S:

Е fM

5(/) =

S\i\S\~l) 2

Теперь для произвольного словаря команд В определим его качество как среднее качество по всем парам слов из В\

Я{Е,Р)(В) = ®в{Я{Е,р))

Введем расстояние р(е, е') между регулярными языками е и е' как . J 0, если е П е' ф 0 P\ei е ) — \

I 1, иначе

Справедлива Теорема 2.2 о нижней оценке качества словаря команд при распознавании детерминированно-автоматным алгоритмом (Е,р):

В третьей главе эталоны задаются в виде автономных монотонных вероятностных автоматов.

Этот подход не является новым. В современных системах распознавания речи распознавание производится с помощью метода скрытых марковских моделей [18]. В основе этого метода лежит алгоритм, который можно перевести на язык вероятностных автоматов.

Формально, автономный вероятностный автомат — это тройка (C,Q,v), где С - алфавит выходных символов; Q - конечный алфавит состояний автомата, v - функция, определенная на множестве состояний автомата Q и принимающая в качестве своих значений вероятностные меры на множестве С х Q, такая, что она разлагается в произведение v = 7Г • Р, где 7г действует на множестве Q и имеет значениями вероятностные меры на множестве Q, а Р действует на том же множестве Q и имеет значениями вероятностные меры на множестве С [26]. Содержательно v(c,q'/q) интерпретируется как условная вероятность перейти в состояние д' и выдать символ с при условии, что в предыдущий момент времени автомат находился в состоянии q. Функцию и можно задать двумя матрицами - квадратной т х m-матрицей 7г = ||7Гу ||: TTij = 7Г{qj/qi),i,j = l,m и прямоугольной т X n-матрицей Р = Pik = P(ci/qi),i = 1, т, I = 1, к, к — \С\. Матрицы 7Г и Р являются стохастическими (по строкам). Далее для вероятностных автоматов вида (С, Q, 7г • Р) будем использовать обозначение (С, Q, 7г, Р).

В каждый момент времени состояние автомата характеризуется вектором распределения вероятностей вида (Р1,Р2»РЗ, • • • где т = |Q|, Pi — вероятность находиться в состоянии ^^ рг = 1. Будем называть i=l,т вероятностный автомат инициальным, если заданы распределения и0 и vF для его начального и финального состояний соответственно (обозначение (С, Q, 7г, Р,

Можно рассмотреть обобщение понятия вероятностного автомата, положив, что матрицы 7г и Р не являются стохастическими, но состоят из неотрицательных элементов и сумма элементов в каждой их строке не превосходит 1 (такие матрицы будем называть слабостохастическими). Далее автоматы со слабостахостическими матрицами 7г и Р также будем называть вероятностными.

Функционирование инициального автомата определяется следующим образом. Начальное состояние определяется распределением г/°. На каждом шаге, находясь в некотором состоянии q, автомат сначала выдает некоторую букву с алфавита С, исходя из распределения вероятностей P(q), а затем переходит в следующее состояние, исходя из распределения вероятностей тг(q). Поскольку матрицы 7г и Р не явлюятся в общем случае стохастическими, будем считать, что на каждом шаге существует вероятность того, что автомат не выдал никакой буквы или не осуществил перехода. Если на некотором шаге автомат перешел в состояние qi, для которого ntj = 0, считаем, что автомат завершил работу. В i=Vn этом случае буквы, которые автомат начиная с начального состояния последовательно выдавал на выход в процессе своей работы, образуют некоторое слово 7 над алфавитом С. Говорим в таком случае, что автомат "выдал"слово 7.

Если некоторое слово 7 = С\С2.СП выдано автоматом (С, Q, 7г, Р, г/°, uF), вероятностью этого слова назовем величину

Pa{i) — V°P(ci)P(c2) • . • P(cn)(l/F)T, где т означает транспонирование матрицы, а для каждого q 6 С F(q) -квадратная m X m матрица и P(q)ij = • Рц — вероятность того, что находясь в состоянии qi, автомат выдал букву с/ и перешел в состояние Чу

Инициальный автономный вероятностный автомат Л = (С, Q, 7г, Р, z/°, v \Q\ = m будем называть монотонным, если выполнены условия:

1. 7Tij = 0 при г > j]

2. и0 = (1, 0,0,., 0);

3. uF = (0,0,.,0,1);

4. тгтт — 0.

Теорема 3.1. утверждает, что для любого монотонного автономного вероятностного автомата Л = (С, Q, 7г, Р, uF), для которого выполен-но условие тгц < 1 для всех i = 1, m, события, связанные с выдачей автоматом различных слов из С*, являются несовместными.

Это позволяет сопоставить каждому автономному монотонному вероятностному автомату Л стохастическую (слабостохастическую) словарную функцию рд : С* —[0,1], вычисляющую вероятность выдачи слов из С* автоматом Л и обладающую свойством

Ы < 1, где сумма берется по всем словам 7j из С*, занумерованным в лексикографическом порядке. Каждую такую словарную функцию можно задать бесконечным вектором

РЪ• • • )Pni • • •) G h с /ь оо где р,- = я4(7»)> = \Р* I < °°}> 1

00 a h = {(PhP2, • • • • • •) : l^l2 < i=l

Методу скрытых марковских моделей соответствует в нашей формализации алгоритм (Е, р) распознавания речи, в котором эталоны Е = {ei, ., едг} команд {/?], ., Д/v} задаются в виде некоторых автономных монотонных вероятностных автоматов, синтезированных по примерам кодовых слов одним из известных методов[19-22], а расстояние между эталонами и кодовыми словами вводится как 7) = 1 — PeXl)

Содержательно метод сравнения с эталонами в вероятностно-автоматном случае сводится к поиску команды, на которой достигается максимум вероятности выдачи распознаваемого кодового слова соответствующим этой команде эталонным вероятностным автоматом.

Качество словаря команд для алгоритма (Е, р) будем также вводить следующим образом. Для В вида {/3} положим Я(Е,р){{@}) = 1- Для словаря из двух команд определим его качество как единица минус удвоенная вероятность ошибки распознавания в этом словаре при условии, что распознаваемые кодовые слова выдаются автоматами, соответствующими каждой из команд, и автоматы включаются по очереди с одинаковой вероятностью 1/2. Для словаря, состоящего из более чем двух команд, определим его качество как среднее качество всех его подсловарей из двух команд.

Далее в третьей главе решается задача оценки качества словарей команд для алгоритма (Е, р). С этой целью на множестве эталонов команд (автономных монотонных вероятностных автоматов) вводится метрика.

Если на множестве стохастических словарных функций метрика каким-либо образом введена, расстоянием между автономными монотонными вероятностными автоматами определяем как расстояние между соответствующими им словарными функциями.

Определения 3.8, 3.9, 3.11 задают три способа введения метрики на множестве стохастических словарных функций: где || • || — норма в ^

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

Связь метрики р2 и вероятности ошибки при распознавании иллюстрирует Лемма 3.4., утверждающая, что p2(pei,Pe2) = 1 - 2р0ш., где р0ш. — вероятность ошибки распознавания в словаре {/З^/Зг}.

Это позволяет выразить функцию качества словаря команд через расстояние между соответствующими командам эталонными вероятностны

7 г£С* р2(рър2) = 1 - Е min(pib)>p2(7i)); лес*

1 и Pi Р2 vT'lNI INI ми автоматами. Теорема 3.2 утверждает, что

ЯШ(В) = вв(р2).

Далее доказывается, что метрика /?з эффективно вычисляется по автоматам.

Для этого в определении 3.12 вводится понятие декартова произведения автономных автоматов:

Декартовым произведением Л = Л\ х автономных вероятностных автоматов Л\ = (С, Q1,71*1, Pi, г/Д v\f) и j\2 = (С, фг? я"2> Ль ^2°) V2F) называем вероятностный автомат = (cf,g2xg2,7r,2,i/°,i/F>, где 7Г — т х m-матрица, т = mim2, mi = \Qi\, г — 1,2, (ЛО^ ' (Лг),*!

Atj) = Mi ■ h°h; Ли) = ■ ("A

Приведенной матрицей переходов тг вероятностного автомата (С, тг, Р, назовем m х m-матрицу, (г, элемент которой определен как к

Kij = Щ XI 1=1

Теорема 3-3 показывает связь между понятием декартова произведения Л = Л\ х Л2 автоматов А\ и Л2 и скалярным произведением соответствующих этим автоматам словарных функций в /2: здесь Е - единичная матрица).

Используя известную связь между нормой и скалярным произведением (||v|| = yj(v, г>)), получаем, как следствие, формулу для вычисления расстояния рз между автономными монотонными вероятностными автоматами Л\ = {С, Qi, 7гь Ph z/Д щр) иЛ2 = {С, Q2, ^2, ^2°, V2F)здесь mi = |Qi|, rri2 = IQ2I, ?hx2 — приведенная матрица переходов автомата Л\ х.4.2, TTixi — приведенная матрица переходов автомата Л1 х А\, ^"2x2 — приведенная матрица переходов автомата Ач х Л2)

Окончательно, качество словаря команд Б с помощью метрики рз определяется как

Приложения.

На основе изложенных в работе подходов написаны прикладные программы распознавания речи. Система распознавания речи с ограниченным словарем ([а2]) работает в операционной системе Windows и позволяет в реальном времени распознавать речевые команды из словаря объемом до 100 команд. Система позволяет вводить команды на любом естественном языке, поскольку для обучения эталонов используется поэлементный метод [33]. В качестве моделей эталонов система позволяет одинаково эффективно работать как с методом ДДВ, так и с методом СММ. Система использует алгоритм распознавания речи, основанный на конечно-автоматном подходе, изложенном во второй главе. В качестве алфавита классов звуков выбран алфавит {Л, О, /, , X} ((см. приложение 2, [al]), где класс X включает шипящие согласные, — символы паузы и глухие смычки, а классы А, 0,1 соответствуют низкочастотным, среднечастотным и высокочастотным гласным звукам соответственно.

Конструктор систем распознавания речи в условиях сильных акустических шумов ([а4]) также работает с раздельно произносимыми командами и фразами из ограниченного словаря. В качестве устройства ввода я\е,Р)(Щ = е*(рз). для конструктора могут подключаться как обычные микрофоны, так и системы из различных датчиков: акустических, фотодатчиков слежения за губами говорящего, датчиков дыхания и т.п. В отличие от описанной выше системы распознавания, конструктор позволяет динамически строить функции описания сигналов на основе сигналов с датчиков с помощью богатого семейства унарных и бинарных операций. Конструктор позволяет строить также устойчиво работающие модули выделения границ речевых сообщений на фоне шума, что повышает в сотни раз надежность распознавания речи в шуме по сравнению с традиционно используемыми методами распознавания. Работа конструктора основана на описанной в первой главе формальной речевой модели.

Система автоматического подравнивания произношения является дополнением к мультимедийным системам обучения иностранным языкам. После настройки на голос ученика электронный учитель позволяет определить количество, место и тип ошибок при произнесении учеником фраз на иностранном языке. При построении системы использовалась оригинальная методика построения модели «правильного произношения» для ученика в виде монотонного вероятностного автомата.

Метрика на множестве автономных вероятностных автоматов, введенная в третьей главе настоящей работы, была эффективно использована при решении задачи оптимального выбора фонетического алфавита при разработке системы распознавания русской речи в рамках гранта с фирмой Intel Corp., США ([35]). С помощью метрики была построена матрица попарных расстояний между фонемами русского языка (см. приложение 3), представленных в виде автономных вероятностных автоматов с 4 состояниями, которые были синтезированы на основе русской речевой базы данных. На основе проведенного эксперимента удалось показать, что алфавит из 150 фонемных символов для русского языка можно сократить без потенциальной потери точности при распознавании до

120 символов, что может значительно увеличить эффективность системы распознавания речи на русском языке.

Введенная в настоящей работе метрика на множестве автономных монотонных вероятностных автоматов имеет широкие возможности практического применения. Она может быть использована в тех областях, где в настоящее время требуется уметь эффективно вычислять расстояние между марковскими автоматами: при решении задач подбора фонетического алфавита ([36]) и словаря команд ([38]), распознавания и идентификации диктора, конверсии и синтеза речи ([37] - здесь метрика используется для решения задачи интерполяции голоса диктора), при программировании стратегических компьютерных игр ([40]) и моделировании стратегий поведения человека в реальных условиях ([39]). Во всех этих практических примерах в настоящее время используются статистические меры близости типа расстояний Махаланобиса, Кульбака-Лейбнера, метод Монте-Карло и им подобные. Поскольку эти меры близости зачастую не обладают всеми свойствами метрики (не выполняется неравенство треугольника), введение метрики на множестве скрытых марковских моделей может дать более эффективные результаты при решении данных практических задач.

Автор выражает благодарность своему научному руководителю доктору физико-математических наук, профессору Бабину Дмитрию Николаевичу за постановку задачи и помощь в работе над диссертацией.

1. С.Е. Левинсон. Структурные методы автоматического распознавания речи. ТИИЭР, т.73, №11, ноябрь 1985 г., с. 100-128.

2. К.Н. Davis, R.Biddulph, and S.Balashek, "Automatic recognition of spoken digits", J.Acoust. Soc. Amer., Vol. 24, pp.637-642, 1952.

3. P.B. Denes and M. V. Mathews, "Spoken digit recognition using time frequency pattern matching", J.acoust. Soc. Amer., vol. 32, pp. 1450-1455, 1960.

4. H. Dudley and S.Balashek, "Automatic recognition of phonetic patterns in speech", J. Acoust. Soc. Amer., vol. 30, pp. 721-7439, 1958.

5. D. H. Klatt, "Review of the ARPA Speech Understanding Project", J. Acoust. Soc. Amer., vol.62, no.6, pp. 1345-1366, Dec. 1977.

6. Г. Фант. Акустическая теория речеобразования / Пер. под ред. B.C. Григорьева. М.: Наука, 1964.

7. V. W. Zue and R. A. Cole, "Experiments on spectrogram reading" in Proc. ICASSP-79, pp. 116-119, 1979.

8. Т.К. Винцюк. Распознавание слов устной речи методами динамического программирования. Кибернетика. 1968. - №1, с. 81-88.

9. Р. Беллман, Динамическое программирование. М.: ИЛ, 1960.

10. F. Itakura, "Minimum prediction residual principle applied to speech recognition", IEEE Trans. Acoust., Speech, Signal Processing, vol. ASSP-23, pp. 67-72, 1975.

11. J.K.Baker, "Stochastic modeling for automatic speech understanding", in Speech Recognition, D.R. Reddy, Ed. New York: Academic Press, 1975, pp. 521-542.

12. Ф. Джелинек Елинек]. Распознавание непрерывной речи с помощью статистических методов. ТИИЭР, 1976, т. 64, №4, с. 131-160.

13. L.E. Baum and T. Petrie, "Statistical inference for probabilistic functions of finite state Markov chains", Ann. Math. Stat., vol. 37, pp. 1554-1563, 1966.

14. А.А. Марков. Пример статистического исследования над текстом "Евгения Онегина", иллюстрирующий связь испытаний в цепь. Известия Академии наук, СПб., VI, т.7, 1913, №3, с. 153-162.

15. S. Е. Levinson, L.R. Rabiner, and М.М. Sondhi, "An introduction to the application of the theory of probabilistic functions of a Markov process to automatic speech recognition". Bell Syst. Tech. J., vol 62, no.4, pp. 1035-1074, Apr. 1983.

16. B.H. Juang, "On the hidden Markov model and dynamic time warping for speech recognition A unified view", AT&T Tech. J., vol. 63, no.7, pp.1213-1243, Sept. 1984.

17. L.E. Baum and J.A.Egon, "An inequality with applications to statistical estimation for probabilistic functions of a Markov process and to a model for ecology", Bull. Amer. Meteorol. Soc., vol.73, pp.360-363, 1967.

18. A. P. Dempster, N.M. Laird, and D.B. Rubin, "Maximum likelihood from incomplete data via the EM algorithm", J.Roy. Stat. Soc., vol. 39, no.l, pp.l-38, 1077.

19. A.J. Yiterbi, "Error bounds for convolutional codes and an asymptotically optimal decodin algorithm", IEEE Trans. Informat. Theory, vol. IT-13, pp. 260-269, Apr. 1967.

20. Дж. Д. Форни-мл. "Алгоритм Витерби". ТИИЭР, 1973, т.61, №3, с.12-25.

21. J.W. Carlyle. Reduced forms for stochastic sequencial machines. J. Math. Analysis and Applic., 1963, 7, p. 167-175.

22. Р.Г. Бухараев. Некоторые эквивалентности в теории вероятностных автоматов. Уч. записки Казан, университета, 1964. 124, №2, с. 45-65.

23. Р.Н. Starke. Theorie Stochastischen Automaten. I, II. Elektron Informationsverarb. und Kybern., 1965, 1, №2.

24. Р.Г. Бухараев. Основы теории вероятностных автоматов. М.: "Наука", 1985.

25. R. Bakis, "Continuous speech word recognition via senti-second acoustic states" in Proc. ASA Meeting (Washington, DC), Apr. 1976.

26. D. Kanevsky, M. Monkowsky, J. Sedivy. Large Vocabulary Speaker-Independent Continuous Speech Recognition in Russian Language. Proc. SPECOM'96, St.-Petersburg, October 28-31, 1996.

27. A. H. Колмогоров, С. В. Фомин. Элементы теории функций и функционального анализа. М.: Наука, 1989.

28. Дж.Бендат, А.Пирсол. Измерение и анализ случайных процессов. М.: "Мир", 1974 г., стр. 372, 342, 368.

29. Ипатов Я.В., Коваль C.JL, Лапшина А.В., Сапожкова И.Ф. Компилятивный синтезатор речи по правилам. Параметрическое представление. Лингвистическое обеспечение.: АРСО-15, стр. 156-157.

30. Л.Р.Рабинер, Р.В.Шафер, Цифровая обработка речевых сигналов. Пер. с английского. М., "Радио и связь", 1981 г.

31. Т.К. Винтцюк. Анализ, распознавание и интерпретация речевых сигналов. Киев, Наукова думка, 1987.

32. В.Б. Кудрявцев, С.В. Алешин, А.С. Подколзин. Введение в теорию автоматов. М.: Наука, 1985.

33. Академическая программа Intel. http://www.intel.ru/education/Grants/grants .htm

34. R. Singh, Bh. Raj, R. M. Stern. Structured definition of sound units by merging and splitting for improved speech recognition. 1999.

35. T. Yoshimura, T. Masuko, K. Tokuda, T. Kobayashi, T. Kitamura. Speaker interpolation in HMM-based speech synthesis system. 1999.

36. B.T. Tan, Y. Gu, T.Thomas. Word confusability measures for vocabulary selection in speech recognition. 1999.

37. M. C. Nechyba, Y. Xu. Stochastic similarity for validating human control strategy models. 1999.

38. S. Siruguri. Modelling a navigation task. 1999.

39. H. В. Зиновьева, JI. M. Захаров, О. Ф. Кривнова, А. Ю. Фролов, И. Г. Фролова. Автоматический транскриптор. АРСО-92.