автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.05, диссертация на тему:Система автоматического распознавания речевых команд для параллельных архитектур

На правах рукописи УДК 50 1041

САПУНОВ Григорий Владимирович

СИСТЕМА АВТОМАТИЧЕСКОГО РАСПОЗНАВАНИЯ РЕЧЕВЫХ КОМАНД ДЛЯ ПАРАЛЛЕЛЬНЫХ АРХИТЕКТУР

05 13.05 - " Элементы и устройства вычислительной техники и систем управления "

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Москва - 2006

Работа выполнена на кафедре «Электронно-вычислительная аппаратура» Московского государственного института электроники и математики (технический университет)

Научный руководитель: доктор технических наук, профессор Петров Геннадий Михайлович

Официальные оппоненты: доктор технических наук, профессор Солодовников Игорь Владимирович кандидат технических наук Аврин Сергей Борисович

Ведущая организация: Московский государственный институт электронной техники (технический университет)

Защита состоится «28» февраля 2006 г. в 14 00 на заседании диссертационного совета Д 212 133.03 в Московском государственном институте электроники и математики (техническом университете) по адресу: 109028, Москва, Б Трёхсвятителъский пер 3/12

С диссертацией можно ознакомиться в библиотеке МИЭМ.

Автореферат диссертации разослан «2У» ЛИ 2006 г

Учйный секретарь диссертационного Совета Д 212 133 03 к т н , доцент

Леохин Ю Л

-ftâj^

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Объектом исследования является речевой сигнал, представленный в системе распознавания речи в определённом признаковом пространстве.

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

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

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

Достаточно хорошо развита ниша программ распознавания речи для персональных компьютеров. Уже довольно давно существуют такие продукты, как IBM ViaVoice, DragonDictate или «Горыныч» (являющийся локализованной версией системы DragonDictaie, изначально ориентированной на английский язык), а также отечественные разработки Сакрамснт и SPIRIT На ПК такие программы обычно выполняют функции навигации и управления другими программами или операционной системой Другое серьёзно проработанное направление использование подобных продуктов - голосовой интерфейс в са11-центрах

Отечественные системы обладают тем преимуществом перед зарубежными, что они изначально ориентированы на русские фонемы В отсутствии такой базы иностранные

PU С. НАЦИОНАЛЬНА)! БИБЛИОТЕКА

системы вынуждены работать с русским языком на основе английских фонем или некоторого общего и универсального их набора, что отрицательно сказывается на качестве распознавания Так, по сообщениям прессы, первый зарубежный коммерческий продукт распознавания русской речи для телефонных приложений, включающий поддержку русских фонем, появился лишь в 2003 году - набор программных модулей, библиотек и утилит для разработки систем такого класса - SpeechPear! компании Philips Speech Processing

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

Аппаратная база современных систем распознавания команд устоялась на нескольких основных вариантах:

1) Системы PC-класса на основе х86-совмесгимых процессоров для программных продуктов, используемых в настольных компьютерах в некоторых серверных или мобильных решениях;

2) Мобильные устройства (телефоны, коммуникаторы, бытовая техника и т п) на процессорах архитектуры ARM (более 75% всех интегрированных процессоров, выпускаемых в мире);

3) Специализированные аппаратные решения на оспове DSP-процессоров с тенденцией замены их массовыми решениями из предыдущих двух классов, так как возросшая производительность универсальных процессоров позволяет решать задачи, прежде бывшие для них весьма тяжёлыми

Тенденция экстенсивного наращивания производительносш процессоров за счёт увеличения их рабочих частот, имевшая место в предыдущие годы, уступает место новой тенденции, нацеленной на активное использование параллелизма в различных его проявлениях В ближайшие годы это выльется в создание многоядерных архитектур процессоров (от уже существующей технологии Intel HyperThreading к созданию двух- и

более ядерных процессоров на одном кристалле, появления которых можно ожидать уже в 2006 году, крайне интересная технология Cell от альянса Sony, Toshiba и IBM, которая чатронет не только компьютеры и игровые консоли, но, потенциально, и бытовую технику в доме), создание недорогих кластерных решений на основе стандартных компонентов (начиная с проекта BeoWulf для ОС Linux) и массовое использование распределенных вычислений (от уже реализовавшихся одиночных проектов типа distributed net для взлома шифров или SETI@Home для поиска внеземных цивилизаций к технологии GRID и виртуализации вычислений, активно продвигаемых корпорацией IBM).

По мнению многих аналитиков и представителей различных компаний, грядёт эра параллельного программирования Одним из первых сё предвестников можно назвать уже существующую технологию EPIC (Explicitly Parallel Instruction Computer) компании Intel, реализованную в коммерческих процессорах Itanium Переход на новые параллельные архитектуры требует создания чрезвычайно сложных оптимизирующих компиляторов, изменения образа мышления программистов и приложения ими специальных усилий для разработки и реализации соответствующих алгоритмов В таких условиях особую ценность представляют алгоритмы, учитывающие возможный параллелизм своей работы.

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

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

Одной из важнейших и наиболее сложных задач, возникающих при работе с СММ, является задача обучения модели, то есть нахождения таких ее параметров, при которых модель точнее описывает «свой» слово, те генерирует для последовательности речевого сигнала, содержащего это слово, большее значение вероятности, чем другие модели слов из словаря системы В процессе распознавания команды происходит оценка и сравнение между собой вероятностей генерации наблюдаемого слова различными моделями из словаря системы с тем, чтобы отобрать среди них наиболее вероятного претендента Чем лучше

модель описывает тестовое (или тренировочное) слово, тем больше шансов, что оно будет верно распознано, те будет выбрано среди всех остальных слов словаря Особенно заметным становится влияние качества обучения модели на результативность работы системы распознавания в том случае, если словарь системы разрастается, и в нём оказываются похожие слова, те слова, модели которых генерируют близкие значения вероятности В таких условиях выбор правильного варианта оказывается затруднительным Кроме того, желательно, чтобы модель могла эффективно распознавать «свое» слово невозможности в более широких пределах изменяющихся условий работы системы распознавания (в различных уровнях зашумлённости или при работе по каналам различающегося качества) и вариативности произнесения слов диктором (в случае стресса или наличия дефеетов речи).

Отсюда следует, что задача обучения модели, причём её качественного обучения, является весьма актуальной и её решению должно уделяться повышенное внимание Существуют и давно применяются оптимизированные методы обучения СММ (например, метод Баума-Велча или ЕМ-процедура), но они не свободны от недостатков, важнейшие среди которых - это сильная зависимость от начальных условий, порождающая задачу нахождения стартовых параметров СММ, и неспособность найти глобальный экстремум, если локальный экстремум оказывается ближе Однозначно лучше1 о метода обучения СММ не известно, и для решения этой задачи могут применяться различные подходы

Одним из таких потенциально интересных методов обучения являются генетические алгоритмы (ГА) Генетические алгоритмы, относящиеся к концепции эволюционных вычислений, - это современное, перспективное и активно разрабатываемое направление методов оптимизации многокритериальных задач Большим плюсом их является организация работы, позволяющая легко распараллелить выполнение алгоритма по нескольким процессорным элементам или компьютерам

За рубежом известно несколько работ о применении ГА для оптимизации СММ в системах распознавания речи, ориентированных на английский язык, но аспект возможности параллельной работы в них не затрагивается Также различия в фонематической базе русского и английского языков, уже выступавшие причиной плохой работы иностранных систем распознавания речи с русским языком, не позволяют однозначно перенести на него опыт применения ГА, а отечественных работ подобной направленности на момент написания диссертации не обнаружено К гаму же обнаруженные зарубежные работы имеют обзорный и довольно поверхностный характер, не несут в себе сколь-нибудь серьёзного анализа альтернатив реализации ГА и практически не содержат обоснования выбора

применяемых решений.

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

Для достижения поставленной цели в работе решены следующие основные задачи

• Исследованы возможности применения генетических алгоритмов (ГА) для оптимизации процесса обучения СММ тренировочными последовательностями с учётом современных тенденций развития аппаратных средств

• Разработан ГА, предназначенный для работы со скрытыми марковскими моделями речевых команд (рассмотрены альтернативы и выбрана схема кодирования решений, реализованы генетические операторы, определены наиболее эффективные значения параметров ГА)

• Исследована эффективность оптимизации обучения СММ с помощью ГА (произведено сравнение ГА с традиционными методами оптимизации обучения СММ и изучено влияние параметров ГА на эффективность этого процесса)

• Разработаны методы, направленные на дальнейшее повышение эффективности и качества работы ГА в контексте рассматриваемой задачи

• Автором создан программно-аппаратный комплекс для исследования генетических алгоритмов на основе системы распознавания команд, использующей аппарат скрытого марковского моделирования и кепстральную предобработку речевого сигнала, разработанной на кафедре ЭВА МИЭМ

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

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

В рамках решения этой задачи автором получены следующие результаты 1 При фиксированной аппаратной базе современных систем распознавания речевых

команд и существующих тенденциях её развития в ближайшем будущем исследованы проблемы применения СММ в задачах распознавания речи и применимость аппарата генетических алгоритмов для оптимизации обучения СММ тренировочными последовательностями. Показана возможность и оправданность использования генетических алгоритмов для решения поставленной задачи

2 Разработан и практически реализован генетический алгоритм, предназначенный для оптимизации обучения СММ, реализованы различные варианты генетических операторов, выбраны наиболее эффективные реализации операторов и определены наиболее эффективные значения параметров ГА с точки зрения поставленной задачи.

3 Проведено исследование эффективности применения реализованного ГА для оптимизации обучения СММ в сравнении с традиционными методами их оптимизации, исследовано влияние параметров ГА на эффективность решения задачи, показано отсутствие ограничений, характерных для традиционных методов Данный метод обладает очень хорошими перспективами при реализации на параллельных архитектурах

4 Предложена схема организации процесса обучения в системе распознавания речевых команд на основе СММ, способная улучшить процесс обучения СММ тренировочными последовательностями и повысить надёжность работы систем распознавания речевых команд, использующих в своей работе марковские модели

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

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

Практическая ценность результатов работы состоит в том, что программно-аппаратный комплекс «Иволга», разработашшй автором на кафедре ЭВА МИЭМ, способен эффективно обучать СММ как традиционными методами, так и с использованием генетических алгоритмов, и находить лучшие параметры моделей, чем используя только лишь традиционные методы обучения СММ Тем самым он позволяет проводить более качественное обучение моделей, а успешное решение этих задач способно повысить

точность и надежность работы систем распознавания речи.

Апробация работы. Основные положения работы докладывались на Научно-технических конференциях студентов, аспирантов и молодых специалистов МИЭМ в 2003, 2004 и 2005 гг.

Публикации. По теме диссертации опубликованы 9 работ.

Структура и объём работы. Диссертационная работа состоит из введения, четырех глав, заключения, предметного указателя и приложений. Список литературы включает 96 наименований.

СОДЕРЖАНИЕ РАБОТЫ Во введении обоснована актуальность работы, сформулированы цели и задачи исследований, раскрываются основные положения работы и практическая значимость полученных результатов.

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

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

С этой целью рассмотрены основные проблемы применения скрытых марковских моделей в задачах распознавания речи. Рассмотрены 3 основные задачи, связанные с использованием СММ в распознавании речи:

Задача 1" Если заданы последовательность наблюдений О = 0|, Ог, От, и модель А.=(А,В,П), где А - матрица вероятностей переходов, В - матрица вероятностей наблюдаемых символов, и П - вектор вероятностей начальных состояний; то как эффективно вычислить Р(0[Х), вероятность такой последовательности при заданных параметрах модели' Решение этой задачи позволит эффективно распознавать элементы речи, имея готовые, обученные модели этих элементов

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

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

Задача 2" Если заданы последовательность наблюдений О = 01; 02, От, и модель Х=(А,В,П), то как выбрать соответствующую оптимальную последовательность состояний Q = qi, q2 qr? Решение этой задачи позволяет выявлять «скрытую» часть модели, т.е находить реальную последовательность состояний

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

Задача 3: Как определить параметры модели Х=(А,В,П), исходя из критерия максимизации Р(0|Я.)' Решение этой задачи позволяет обучать модели, те вычислять параметры модели так, чтобы модель наилучшим образом описывала, так называемые, «тренировочные» последовательности.

Проблема тренировки моделей считается самой сложной при использовании СММ в системах распознавания, и ее решению уделяется особое внимание Она должна дать метод нахождения параметров модели, таких, чтобы максимизировать вероятность последовательностей наблюдений, соответствующих данной модели На самом деле, не известно ни одного аналитического метода решения этой задачи. То есть для любого конечного числа «тренировочных» последовательностей нет оптимального пути оценки параметров модели Однако, используя итеративную процедуру Баума-Велча (Baum-Welch) (или эквивалентный ей ЕМ (expectation-modification) метод) или градиентные методы, можно выбрать А.=(А,В,П) так, чюбы Р(О|?0 имел локальный максимум Здесь мы имеем одну из задач оптимизации, для которой применимы различные методы решения

У описанных традиционных методов решения задачи №3 есть два серьёзных ограничения: уже упонянутая способность находить лишь локальные максимумы, а также сильная зависимость от стартовых параметров.

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

Во второй главе диссертации рассматриваются методы оптимизации, применимые к обучению СММ.

На сегодняшний день можно выделить три основных типа методов поиска оптимальных решений, применимых к данной задаче.

• методы, основанные на математических вычислениях,

• перечислительные методы,

• методы, использующие элемент случайности

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

Направленные методы строятся на перемещении от точки к точке в допустимой области, причем направление подобных перемещений связывается с тем направлением, на которое указывает градиент (например, метод касательных) Итеративная процедура Баума-Велча, предназначенная для решения задачи обучения СММ и рассмотренная в первой главе, относится именно к этой группе методов оптимизации Как было отмечено для этой процедуры, она способна находить лишь локальные экстремумы или глобальный, но только если на пути к нему по ландшафту параметров не окажется локальных экстремумов, выбраться из которых она не сможет Данная особенность распространяется и на всю группу методов - они часто находят лишь локальные экстремумы целевой функции, тогда как оптимальному решению соответствует только глобальный экстремум

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

Так, например, для поиска оптимальной матрицы для СММ, имеющей 10 состояний, пришлось бы перебрать 10*10=100 элементов матрицы вероятностей переходов, каждый из которых может принимать значения в диапазоне от 0 до 1, с шагом равным 0,00000001 = 10'8 (такова точность хранения параметров СММ в системе распознавания речи, разрабатываемой на кафедре ЭВА МИЭМ), то есть, каждый элемент может принимать 108 значений Для строки из этих 100 элементов число возможных комбинаций оказывается равным (108),оо=108<х>, что значительно больше числа субатомных частиц во Вселенной Даже, если крайне упростить залачу перебора наложив серьезные ограничения на структуру матрицы переходов СММ, а также на точность представления ее элементов, число вариашов для перебора все равно останемся огромным и превышающим все разумные значения

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

Вместе с тем следует заметить, что сейчас при решении очень сложных задач основной целью является поиск уже не оптимального, а более «хорошего» решения по сравнению с полученным ранее или заданным в качестве начальною Здесь методы,

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

Эволюционные вычисления - термин, обычно используемый для общего описания алгоритмов поиска, оптимизации или обучения, основанных на некоторых формализованных принципах естественного эволюционного процесса Одним их основных направлений в рамках этого подхода являются генетические алгоритмы Детерминированность этих методов заключается в моделировании природных процессов отбора, размножения и наследования, происходящих по строго определённым правилам Основным правилом при этом является закон эволюции «выживает наиболее приспособленный», который обеспечивает улучшение находимого решения Другим важным фактором эффективности эволюционных вычислений является моделирование размножения и наследования Рассматриваемые варианты решений могут по определенному правилу порождать новые решения, которые будут наследовать лучшие черты своих «предков» В качестве случайного элемента в методах эволюционных вычислений может использоваться, например, моделирование процесса мутации В этом случае характеристики того или иного решения могут бьпъ изменены случайным образом, что приведет к новому направлению в процессе эволюции решений и может ускорить процесс выработки лучшего решения

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

Суть генетических алгоритмов заключается в представлении любой альтернативы решения в виде строки параметров (например, битовой строки фиксированной длины), манипуляции с которой производятся в отсутствие всякой связи с ее смысловой интерпретацией То есть в данном случае применяется единое универсальное представление любой задачи Каждый код при этом представляет, по сути, точку пространства поиска. С целью максимально приблизиться к биологическим терминам, экземпляр кода называют хромосомой, особью или индивидуумом На каждом шше работы генетический алгоритм использует несколько точек поиска параллельно Совокупность этих точен является набором особей, который называется популяцией Формирование исходной популяции происходит, как правило, с использованием какого-либо случайного закона, на основе которого выбирается

нужное количество точек поисково! о пространства. Исходная попуошщя может также бьпь результатом работы какого-либо другого алгоритма оптимизации

В процессе работы алгоритма генерация новых особей происходит на основе моделирования процесса размножения При этом порождающие особи называются родителями, а порожденные - потомками Родительская пара, как правило, порождает пару потомков Непосредственная генерация новых кодовых строк из двух выбранных происходит за счет работы оператора скрещивания, который также называют кроссинтовером или кроссовером Моделирование процесса мутации новых особей осуществляется за счет работы оператора мутации Основным параметром оператора мутации является вероятность мутации Поскольку размер популяции не может быть неограниченным, порождение потомков должно сопровождаться уничтожением других особей Выбор пар родителей из популяции для порождения потомков производит оператор отбора, а выбор особей для уничтожения - оператор редукции Основным параметром их работы является, как правило, качество особи или приспособленность, которое определяется значением целевой функции (или фитнес-функции) в точке пространства поиска, описываемой этой особью

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

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

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

Создание исходной популяции

Выбор родителей для процесса размножения (работает оператор отбора)

Создание потомков выбранных пар родителей (работает оператор скрещивания)

Мутация новых особей

(работает оператор мутации)

Расширение популяции за счёт добавления новых, только что порожденных особей

Сокращение расширенной популяции до исходного размера (работает оператор редукции)

Критерий останова работы алгоритма выполнен''

Да

Поиск лучшей достигнутой особи в конечной популяции -результата работы алгоритма

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

Теорема схем (1) отражает фундаментальную теорему генетического алгоритма, которая определяет асимптотическое число схем т(Н, I) (подстрок хромосомы, Я), выживающих при его реализации на каждой итерации г

ДЮ

где ДН) - приспособленность схемы Н,

Лр($) - средняя приспособленность популяции, Рс - вероятность кроссовера, Рт - вероятность мутации,

ЦН) -длина схемы (расстояние между крайними определенными позициями), £ - длина хромосомы,

О(Н) - порядок схемы (число определенных позиций)

Наиболее существенное влияние на число выживающих схем оказывают значения целевых функций отдельной схемы /(И) и всей популяции а эффективность реализации генетических операторов связана с их параметрами (Рс, 1'т) и зависит от размера схем (ЦН), 0(Н)) Теорема схем показывает, что количество схем с высокой приспособленностью (строительных блоков) растет по экспоненте, в то время как схемы с приспособленностью ниже средней распадаются с той же скоростью

Задача обучения СММ, рассмогренная в первой главе, удовлетворяет предпосылкам для успешного применения аппарата генетических алгоритмов Поскольку точное и однозначное решение дшшой задачи не известно, но есть возможность оценить каждое из предлагаемых решений, есть критерий для оценки получившегося результата и, как следствие, - возможность реализовать оценочную функцию (фитнес-функцию) для использования в генетическом алгоритме Кроме того, вычисление фиггнес-функции (значение которой равно вероятности генерации наблюдаемой последовательности при заданных параметрах скрытой марковской модели) не является особенно трудоёмким, что позволяет многократно её вычислять для различных параметров, то есть создавать популяции решений Эффективную фитнес-функцию позволяет создать решение рассмотренной в Главе 1 задачи №1

Сами параметры, подлежащие оптимизации (матрица переходов СММ), весьма хорошо соответствует поюггию хромосомы - эти параметры (элементы матрицы) могут быть легко отделены друг от друга и закодированы каждый в своём «]ене» хромосомы, так что генетический алгоритм окажется способным создавать произвольные их комбинации в поисках тех, что ведут к лучшим значениям целевой функции

В третьей главе предлагается реализация генетического алгоритма, предназначенного для оптимизации процесса обучения СММ тренировочными последовательностями или образцами команд За основу взята разработанная на кафедре ЭВА МИЭМ система оценки стартовых параметров СММ в задачах распознавания команд при кепегральной предобработке речевого сш нала ($сЬЛрр) Основной задачей БсЪАрр является получение стартовых параметров СММ для изолированных слов Результаты ее

работы и используются в данной работе как отправная точка для деятельности генетическою алгоритма. В целях повышения разнообразия исходной популяции часть решений сразу подвергается мутации Другим вариантом создания начальной популяции является ее заполнение случайными особями Автором экспериментально установлено, что алгоритм успешно работает и при такой начальной популяции Это свидетельствует о том, что он свободен от ограничения в виде сильной зависимости результата от стартовых параметров, присущего традиционным методам оптимизации СММ, например, методу Баума-Велча

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

Автором экспериментально определён размер популяции решений, обеспечивающий наиболее эффективную работу реализованного генетического алгоритма (рис 2)-

9 оое 212---

1 48 95 142 189 236 283 330 3/7 424 471 518 565 812 659 706 753 800 847 894 941 Пошл сни*

Ряс. 2. Влияние размера популяции на сходимость алгоритма Слишком малое выбранное значепие размера популяции (Ю особей) приводит к очень медленному движению алгоритма в сторону лучших решений, и кроме того на фафике часто наблюдаются горизонтальные участки, которые свидетельствуют о «застревании» алгоритма в точках локальных экстремумов При увеличении размера популяции алгоричм быстро набирает скорость и доходит до определённой точки, после которой дальнейшее увеличение

популяции не оказывается особо эффективным, поскольку не даёт заметного улучшения

работы Так, популяция размером в 500 особей оказывается всего лишь незначительно

эффективнее популяции размером 200 особей, при том, что на её обработку требуется более

чем в два раза больше времени В итоге, по результатам этих экспериментов был сделан »

вывод о том, что оптимальный размер популяции для данной задачи находится в районе 200

особей }

В работе был осуществлён выбор операторов ГА

В алгоритме реализован пропорциональный оператор отбора, эффективность которого подтверждена экспериментально в соответствии с теоремой схем Вероятность отбора особи для последующего размножения, Р/0-. прямо пропорциональна её приспособленности (значению целевой функции) Эта вероятность равна отношению приспособленности особи (Л) к суммарной приспособленности популяции

Генетический оператор скрещивания должен учитывать ограничения на матрицу вероятностей переходов СММ - строка матрицы должна рассматриваться как единое целое То есть, точка разбиения не должна находиться внутри строки, а может лежать только на границе строк Это условие возникает из рассмотренных в первой главе ограничений на строки матрицы вероятностей переходов, главное из которых условие полной вероятности, то есть сумма всех элементов строки (а^) должна быть равна единице:

Были реализовацы различные варианты оператора скрещивания одноточечный, двухточечный и равномерный, учитывающие условие (3) и проведено сравнение их работы Резу.штаты их работы оказались достаточно близкими, и peí улярных серьёзных расхождений в работе различных операторов скрещивания не наблюдалось

Оператор мутации также должен соблюдать условие (3), для чего во время мутации подвергаются корректировке соседние с мутировавшим элементы строки Для однострочною оператора мутации, действие которого затрагивает только одну строку матрицы, автором получена оптимальная вероятность мутации, которая составила порядка 0 9-0 95 Это нехарактерное для генетических алгоритмов значение говорит о том, что мутации недостаточно эффективны при большом размере хромосомы (так, для СММ с числом состояний, равным 10, в хромосоме закодированы 100 естественных чисел).

(2)

N

(3)

Во многих задачах изменение одного гена не позволяет выйти решению из локального оптимума Если принять во внимание, что в случае сходимости популяции в локальном оптимуме мутация остаётся единственным механизмом, способным вывести популяцию из него, то проблема становится весьма значимой Альтернативой этому варианту является использование операторов мутации, затрагивающих несколько элементов или несколько строк сразу

Автором реализован модифицированный многострочный оператор мутации, работающий несколько иначе В случае его использования вероятность мутации трактуется как вероятность мутации каждой из строк матрицы, а не единичной произвольно выбранной строки В этом случае мутация может затронуть сразу несколько строк матрицы Последующие эксперименты показали, что эффективность работы однострочного оператора мутации при высокой вероятности самой мутации сравнима с эффективностью работы многострочного оператора мутации при традиционно низких вероятностях мутации порядка О 05-0 1, что подтверждает выдвинутое ранее предположение Кроме того, высокие значения вероятности мутации в сочетании с многосгрочным оператором мутации наоборот сильно снижают эффективность работы алгоритма, что, в соответствии с теоремой схем, выражается в разрушении строительных блоков хромосом и уничтожении хороших особей в популяции

Оператор редукции поддерживает постоянный размер популяции, не давая ей неограниченно увеличиваться, в простейшем случае просто приводя ей к фиксированному размеру в конце каждого шага основного цикла ГА Работа оператора редукции сводятся к уничтожению в популяции худших её особей Эта процедура проводится для расширенной популяции, то есть той популяции, что получается после добавления вновь получившихся после скрещивания и мутации особей к исходной, и заключается в последовательном удалении из популяции особей с наименьшим значением функции приспособленности

Все выбранные операторы ГЛ были реализованы в ра}работанном авюром программном комплексе «Иволга», используемом па кафедре ЭВЛ МИЭМ для работ в области распознавания речи

Рассмотрены различные варианты реализации критерия остапова ГЛ фиксированное число поколений работы, фиксированное время работы, достижение заданного значения целевой функции, достижение всеми особями популяции задашюго порога и достижение определённой сходимости работы ГА К выбору критерия останова предлагается использовать следующий подход на этапе исследования моделей критерием является заданная сходимость алгоритма, когда же проведено достаточное количество испытаний, система может быть перенастроена на исполыование в качестве критерия фиксированного

числа поколений генетического алгоритма Эксперименты автора показывают, что для большинства моделей за 250-300 поколений достигается такое значение целевой функции, дальнейшее улучшение которого идет крайне незначительно и варьируется в лучшем случае в пределах единиц процентов от этого значения, поэтому становится оправданным использование в качестве критерия останова фиксированного значения числа поколений работы генетического алгоритма в районе 250-300

В четвёртой главе производится исследование способности ГА решать поставленную задачу обучения СММ Ориентиром при оценке является традиционный метод обучения СММ - метод Баума-Велча Отобраны примеры, наглядно иллюстрирующие наиболее важные моменты в работе ГА.

Тестирование проводилось на речевой базе данных (РБД) кафедры ЭВА МИОМ, использовались словари «Русский фонетический алфавит» (36 слов), «Связь и коммуникации» (46 слов), «Графический» (19 слов), «Управление в коммуникации» (15 слов), «Числовой» (21 слово), «Новый» (24 слова), «Латинский фонетический алфавит» (26 слов) и «Stv» (18 английских слов), а также отдельные слова из других словарей и слова, поступающие в систему распознавания непосредственно с микрофона, подключенного к компьютеру

При сравнении использовалась реализация метода Баума-Велча из библиотеки Intel Recognition Primitives Library Это хорошо оптимизированная по скорости работы библиотека, созданная специалистами компании Intel, которая предоставляет разработчику набор функций, часто исполыуемых при разработке приложений распознавания речи или зрительных образов.

Проводилось сравнение результатов работы ГА с результатами обучения марковской модели методом Баума-Велча, и оно показало, что ГА дает сравнимые с последним результаты, порой превосходя его В цифрах, однократный запуск генетического алгоритма с числом поколений равным 300, и количеством особей в популяции равным 200, (эти значения по результатам множества хестов признаны автором оптимальными для данной задачи) для слов одного словаря («Числовой») в сравнении с результатами обучения методом Баума-Велча показывает результат от -15% (на 15% худший результат) до +70% (на 70% лучший) Повторные запуски ГА способны найти еще более хорошие решения (то есть, более качественно обученные модели слов) Так, для обученной с помощью генетического алгоритма модели слова «гуманист» вероятность i еиерации тестового слова оказалась на 68% выше, чем у модели, обученной с помощью метода Баума-Велча

Весьма показательно то, что генетический алгоритм при старте с совершенно

случайной точки способен обнаружить хорошее решение, в то время как для метода Баума-Велча является важным выбор стартовых параметров

В части случаев матрица решения получается менее строгой, чем в других случаях, -некоторые состояния допускают переходы-скачки в другие состояния, порой далеко ♦ отстоящие от исходного Такая ситуация может иметь место при работе со словами,

записанными разными дикторами, где часть звуков у одного из дикторов может оказаться 4. пропущена (или, как говорят, «проглочена») или при наличии особенностей произнесения

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

В некоторых случая ГА находит решения, несколько худшие, нежели метод Баума-Велча, хотя и сравнимые с ним Это свидетельствует о вероятностном характере работы алгоритма, и порой надо совершить серию запусков, чтобы по результатам выбрать среди них лучшее решение На основании этих данных предлагается следующая схема организации процесса обучения в системе распознавания речевых команд на основе СММ система содержит модуль, реализующий обучение традиционным методом Баума-Велча и параллельно несёт в себе модуль ГА Первоначальное обучение марковской модели слова производится с помощью метода Баума-Велча, а в дальнейшем (например, во время простоя системы, когда вычислительные ресурсы компьютера свободны) производя ¡ся запуски системы ГА как со случайной стартовой популяцией, так и с популяцией, построенной на основе уже обученных моделей При нахождении генетическим алгоритмом модели слова лучшей, чем имеющаяся в словаре системы, производится её замена на новую Данный подход позволяет произвести быстрое начальное обучение системы и затем последовательно работать над улучшением моделей слов в словаре

Иными словами, генетические алгоритмы и метод Баума-Велча хорошо согласуются между собой и ни в косм случае не противостоят друг другу и не являются взаимоисключающими Хотя они и предназначены для решения одной задачи, они могут действовать в её решении согласованно Так, исходной точкой для работы ГА могут быть значения, полученные с помощью метода Баума-Велча, тогда ГА будет работать в направлении улучшения имеющегося решения Или же, наоборот, методом Баума-Велча может быть улучшено решение, полученное генетическим алгоритмом особенно, когда число шагов его работы было заметно ограничено Возможность согласованной работы ГА и метода Баума-Велча проиллюстрирована примерами

Экспериментально показана низкая эффективность случайного поиска при решении

чадачи обучения СММ и значительное повышение его эффективности при введении в него элементов детерминированности

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

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

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

Еще одним важным фактором, влияющим на скорость работы генетического алгоритма, является вычисление фитнес-функции (или функции приспособленности) Фитнес-функция численно равна вероятности генерации заданного слова моделью и расчитывается для всех особей на каждом шаге работы алгоритма Это то место в программе,

где задача обучения СММ (Задача №3 - из классификации в первой главе среди основных задач, встающих перед разработчиком при работе с СММ) вплотную соприкасается с Задачей №1 - задачей эффективного вычисления вероятности генерации заданной последовательности, и от успешного решения задачи №1 зависит эффективное решение задачи №3 Ввиду того, что вычисление фигнес-функции требуется регулярно, так как это наиболее часто используемая деталь алгоритма, она должна требовать минимум ресурсов, и потому важно, чтобы сама процедура её вычисления была достаточно эффективна Поэтому оптимизация самой фитнес-функции также является методом повышения скорости работы генетического алгоритма. В разработанной автором программе используется высокоэффективная реализация функции для вычисления вероятности генерации последовательности из библиотеки Intel Signal Processing Library

Крайне хорошим средством увеличения скорости работы генетического алгоритма является его распараллеливание как на уровне организации работы генетического алгоритма, так и на уровне его непосредственной реализации на вычислительной машине На уровне непосредственной реализации ГА - это реализация на параллельных системах или процессорах вычисления значений целевой функции для различных особей, осуществление преобразования оператора скрещивания и мутации для нескольких пар родителей и т д, что пропорционально повысит скорость работы алгоритма На уровне организации работы ГЛ применяется структурирование популяции решений на основе концепции островов или концепции скрещивания в локальной области Оба подхода могут эффективно реализовываться на параллельных вычислительных машинах

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

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

Автором предложены дальнейшие усовершенствования реализованного

генетического алгоритма, направленные на повышение эффективности его работы

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

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

Поскольку эффективность работы алгоритма нижнего уровня подтверждена экспериментально автором в этой работе, можно автоматизировать настройку параметров ГА введением 1А второго уровня.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

I перспективное направление повышения эффективности обучения СММ посредством

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

2 Для решения задачи оптимизации обучения СММ разработан наиболее приспособленный для этой цели ГА, выбран и реализован механизм кодирования решений вещественным числами, создана фитнес-функция, вычисляющая вероятность генерации тестовой последовательности моделью наиболее эффективным способом Разработанные генетические операторы ориентированы на работу с СММ и учитывают характерные для них ограничения На основании теоремы схем показано, что выбранный оператор отбора ведёт к эффективному нахождению более хороших решений задачи Определены условия эффективного применения различных вариантов реализации критерия останова ГА Экспериментально определены наиболее эффективные зпачения параметров алгоритма (размер популяции, вероятность мутации) для использования в задаче обучения СММ

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

4 Экспериментально определены параметры, оказывающие влияние на эффективность решения алгоритмом поставленной задачи Предложены методы, направленные на дальнейшее повышение эффективности и качества работы ГА в контексте

рассматриваемой задачи' возможность оптимизации выбора параметров с испольчованнем 2-уровневого ГА и использование комбинированной фитнес-функции Это открывает путь к созданию самообучающихся систем распознавания и позволяет повысить качество распознавания команд при работе с разными дикторами, дикторами в условиях стресса, с дикторами, речь которых имеет особенности в виде «проглатывания» части звуков, а также в телекоммуникационных системах при работе по каналам связи низкого качества, где часть голосовой информации может быть потеряна, в том числе и в сетях сотовой связи или IP-телефонии

5 В рамках работы создан программно-аппаратный комплекс «Иволга» для исследования генетических алгоритмов Программная его часть является дополнением системы SdlApp, решающей задачу оценки стартовых параметров СММ и функционирующей на кафедре ЭВА МИЭМ с 1998 г, и написала в среде Borland С++ Builder 6 Необходимая для работы аппаратная часть - ПК с процессором класса Pentium-З 500МГц и 256Мб оперативной памяти, а также звуковая карта, поддерживающая при записи звука частоты дискретизации до 44КГц

6 Автором предлагается следующая схема организации процесса обучения в системе распознавания речевых команд на основе СММ- система содержит модуль, реализующий обучение традиционным методом Баума-Велча и параллельно несёт в себе модуль ГА Первоначальное обучение марковской модели слова производится с помощью метода Баума-Велча, а в дальнейшем (например, во время простоя системы, когда вычислительные ресурсы компьютера свободны) производятся запуски системы ГА как со случайной стартовой популяцией, так и с популяцией, построенной на основе уже обученных моделей При нахождении гепетическим алгоритмом модели слова лучшей, чем имеющаяся в словаре системы, производится её замена на новую Данпый подход позволяет произвести быстрое начальное обучение системы и затем работать над улучшением моделей слов в словаре (в том числе и имея возможность распределить вычисления между различными компьютерами в сети) Предложенное в данной работе решение задачи оптимизации обучения СММ способно улучшить процесс обучения СММ тренировочными последовательностями и повысить надёжность работы систем распознавания речевых команд, использующих в своей работе марковские модели

СПИСОК ОСНОВНЫХ РАБОТ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

1) Сапунов Г В , Труфанов Ф А «Метол предварительной классификации фонем русского языка на основе элементарных параметров речевого сигнала», Информационные технологии в системах вычислительной техники Сборник научных трудов кафедры ЭВА 2 выпуск Москва, МИЭМ 2002 ISBN 5-9456-002-X, стр 37-40

2) Сапунов Г В «Формирование массивов данных для качественного статистического анализа фонематического состава русского языка», Научно-техническая конференция студентов, аспирантов и молодых специалистов института, посвященная 40-летию МИЭМ Тезисы докладов - М МИЭМ, 2002 - 395с ISBN 5-230-16362-3, стр 121122.

3) Сапунов Г.В «Задача предварительной классификации звуков русского языка в двухуровневой системе автоматического распознавания речи», "Новые информационные технологии" Тезисы докладов X Юбилейной международной студенческой школы-семинара в 2-х томах. - М МИЭМ, 2002 - 63 lc ISBN 5-94506005-4, стр 138

4) Сапунов Г В «Применение метода кластерного анализа к задаче классификации фонем русского языка», Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ Тезисы докладов - М ■ МИЭМ, 2003 - 536с ISBN 594506-017-8, стр 104-105.

5) Сапунов Г В «Генетические алгоритмы и оптимизация скрытых марковских моделей в задачах распознавания речи», Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ Тезисы докладов - М ~ МИЭМ, 2004. -617с ISBN 5-94506-039-9, стр. 245-246

6) Сапунов Г.В, Труфанов Ф А «Генетические алгоритмы как метод оптимизации скрытых марковских моделей в задачах распознавания речи», Информационные технологии в системах вычисти тельной техники Сборник научных трудов кафедры ЭВА 3 выпуск Москва, МИЭМ 2004

7) Труфанов Ф А, Сапунов Г В «Применение нечеткой логики в алгоритме предварительной классификации в двухступенчатой системе распознавания фоием русского языка», Информационные технологии в системах вычислительной техники Сборник научных трудов кафедры ЭВА 3 выпуск Москва, МИЭМ 2004

8) Сапунов Г В «Выбор базовых параметров генетического алгоритма для решения задачи оптимизации обучения скрытых марковских моделей», Научно-техническая

конференция студентов, аспирантов и молодых специалистов МИЭМ Тезисы докладов -М МИЭМ, 2005 -429с ISBN 5-94506-106-9, стр 200-202 9) Сапунов Г В «Исследование эффективности гснсгическ01 о алгоритма в зависимости от выбора его базовых параметров в задачах автоматического распознавания речи», "Новые информационные технологии" Тезисы докладов XIII международной студенческой школы-семинара, - М МИЭМ, 2005 - 361с, стр 111

Подписано в печать 19.01.2006. Формат 60x84/16. Бумага типографская № 2. Печать - ризография. Усл. печ. л. 1,8 Тираж 100 экз. Заказ &2.Í

Московский государственный институт электроники и математики 109028, Москва, Б.Трехсеятительский пер., 3/12.

Центр оперативной полиграфии (095) 916-88-04, 916-89-25

t

)

í

f !

I

jfl - f p n

ОГЛАВЛЕНИЕ.

АННОТАЦИЯ.

ВВЕДЕНИЕ.

ГЛАВА 1. АНАЛИЗ ОСНОВНЫХ ПРОБЛЕМ ПРИМЕНЕНИЯ СКРЫТЫХ МАРКОВСКИХ МОДЕЛЕЙ В СИСТЕМАХ РАСПОЗНАВАНИЯ РЕЧИ.л.

1.1 что такое марковская модель.

1.2 Скрытая марковская модель (СММ).

1.3 Основные задачи при применении СММ к распознаванию речи.

1.4 Типы СММ, применяемые в системах распознавания речи.

1.5 Подходы к решению основных задач СММ.

1.5.1 Задача 1. Эффективное вычисление вероятности генерации заданной последовательности.

1.5.2 Задача 2. Отыскание оптимальной последовательности состояний.

1.5.3 Задача 3. Обучение СММ тестовыми последовательностями.

1.6 выводы.

ГЛАВА 2. СРАВНИТЕЛЬНАЯ ОЦЕНКА МЕТОДОВ ОПТИМИЗАЦИИ В ЗАДАЧЕ ОБУЧЕНИЯ СММ.

2.1 Схема процесса принятия решения как задачи поиска.

2.2 Традиционные методы поиска оптимальных решений и их приложение к задаче обучения СММ.ЗЗ

2.2.1 Методы, основанные на математических вы числениях.

2.2.2 Перечислительные методы.

2.2.3 Методы, использующие элементы случайности.

2.3 Концепция эволюционных вычислений.

2.4 OCI ювы теории генетических алгоритмов (ГА).

2.5 Последовательность работы генетического алгоритма.

2.6 Вычислительная эффективность применения ГА. Теорема схем.

2.7 Выводы.!.

ГЛАВА 3. РЕАЛИЗАЦИЯ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ДЛЯ РЕШЕНИЯ ЗАДАЧИ ОПТИМИЗАЦИИ СММ.

3.1 Система распознавания речевых команд на основе СММ.

3.2 Построение генетического алгоритма для оптимизации процесса обучения СММ тренировочными последовательностями.

3.2.1 Кодирование хромосомы.

3.2.2 Создание исходной популяции.

3.2.3 Размер популяции.

3.2.4 Генетические операторы: оператор отбора.

3.2.5 Генетические операторы: оператор скрещивания.

3.2.6 Генетические операторы: оператор мутации.

3.2.7 Генетические операторы: оператор редукции.

3.2.8 Критерий останова алгоритма.

3.3 Выводы.

ГЛАВА 4. ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ ОПТИМИЗАЦИИ СММ С ИСПОЛЬЗОВАНИЕМ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ.

4.1 Сравнение генетических алгоритмов с традициош 1ыми методами.

4.1.1 Метод Баума-Велча.:.

4.1.2 Случайный поиск.

4.2 Показатели эффективности ш штических алгоритмов.

4.2.1 Скорость работы генетического алгоритма.

4.2.2 Средства повышения скорости работы генетических алгоритмов.

4.2.3 Устойчивость работы генетического алгоритма.

4.2.4 Средства повышения устойчивости работы генетических алгоритмов.

4.3 Направления развития генетических алгоритмов.

4.3.1 Использование комбинированной фитнес-функции.

4.3.2 Адаптивный ГА.

4.4 выводы.

Работы в области систем распознавания речи имеют уже довольно долгую историю. В Советском Союзе работы по компресии речи начались в начале 50-х годов, а по автоматическому распознаванию - в конце 50-х годов. При этом следует отметить, что первая в мире система автоматического распознавания речи была продемонстрирована в 1939 году в Ленинградском Государственном Университете Л.Л.Мясниковым. В 70-х годах в разработке речевых систем начали активно выходить вперёд США, тем не менее уровень теоретических и приладных разработок в СССР и США до середины 80-х годов оставался приблизительно одинаковый: С середины 80-х годов значительная часть речевых разработок в нашей стране была прекращена, и в настоящее время помимо США в области речевых технологий активно и очень успешно работает ещё ряд стран (ЕС, Япония, Канада, Австралия). [10] Но в нынешний момент происходит процесс восстановления интереса к этой области и в нашей стране, и на рынке появляются отечественные разработки, например, системы SPIRIT [89] и Sakrament [85].

В настоящее время работы по распознаванию речи не только не потеряли актуальности, но и развиваются широким фронтом, находя для себя множество областей для практического применения. Сейчас можно выделить 4 сравнительно изолированных направления в области развития речевых технологий [9]:

1. Распознавание речи - т.е. преобразование речевого акустического сигнала в цепочку символов, слов. Эти системы могут быть охарактеризованы по ряду параметров. Прежде всего это объём словаря: малые объёмы до 20 слов, большие - тысячи и десятки тысяч. Количество дикторов: от одного до произвольного. Стиль произнесения: от изолированных команд до слитной речи и от чтения до спонтанной речи. Коэффициент ветвления, т.е. величина, определяющая количество гипотез на каждом шаге распознавания: от малых величин (<10-15) до больших (-100-200). Отношение сигнал/шум от больших (>30 дб) до низких (<10 дб). Качество каналов связи: от высококачественного микрофона до телефонного канала. Качество работы систем распознавания речи обычно характеризуется надёжностью распознавания слов, или, что то же самое, процентом ошибок.

2. Определение индивидуальности говорящего. Эти системы прежде всего делятся на 2 класса: верификация говорящего (т.е. подтверждение его личности) и идентификация. говорящего (т.е. определение его личности из заранее ограниченного числа людей). Оба эти класса далее могут быть разделены на тексто-зависимые и тексто-независимые. Следующий характеристический параметр - объём парольной фразы. Два других (как и в распознавании речи): отношение сигнал/шум и качество канала связи. Качество работы систем верификации/идентификации говорящего характеризуется двумя величинами: вероятностью не опознания «своего» диктора и вероятностью принятия «чужого» диктора за своего.

3. Синтез речи. Практически существует 2 класса:

1) Воспроизведение записанного в той или иной форме ограниченного числа сообщений;

2) Синтез речи по тексту.

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

4. Компрессия речи. Основной (и единственный) классификационный признак этих систем - степень компрессии: от низкой (32-16 кбит/сек) до высокой (1200-2400 кбит/сек и ниже). Качество работы систем компрессии речи характеризуется прежде всего разборчивостью компрессированной речи. Дополнительными характеристиками очень важными в ряде приложений являются узнаваемость голоса говорящего и возможность определения уровня стрессованности говорящего.

В диссертационной работе рассматриваются системы первой группы - системы распознавания речи и их частный случай - системы распознавания речевых команд, т.е. распознавание изолированных слов, а не слитной речи. Такие системы весьма полезны па практике, и возросшая необходимость в них связана в первую очередь с появлением большого количества доступных человеку разнообразных устройств (персональные, мобильные и карманные компьютеры, коммуникаторы и мобильные телефоны, игровые и многофункциональные мультимедийные устройства с достаточной вычислительной мощностью) в сочетании с бурным развитием телекоммуникаций в современном мире. Растёт важность массового внедрения новых интерфейсов взаимодействия человека с техническими системами, поскольку традиционные интерфейсы во многом уже достигли своего совершенства, а вместе с ним и своих пределов. При традиционно высокой значимости информации, поступающей к нам через органы зрения, и её высокой доли среди всей сенсорной информации, считающейся равной порядка 85% [11], этот канал восприятия человека становится в значительной степени перегружен. И первоочередной альтернативой здесь видится коммуникация именно по акустическому каналу.

Кроме того, системы распознавания (а также синтеза) речи также крайне важны для людей с ограниченным зрением, и эта ниша для их применения активно развивается прежде всего в области мобильной телефонии (малые размеры экранов телефонных аппаратов не дают таким людям возможности пользоваться ими с достаточной степенью комфорта), а также в бытовой технике (для управления разнообразными домашними устройствами). Для помощи таким людям производители вводят в свои устройства возможности управления посредством голосовых команд (при наборе номера в телефоне или во время навигации по пунктам меню), а также дублирования экранной информации голосом. И в первую очередь от таких продуктов требуется распознавание ограниченного набора команд пользователя, а не слитной речи с большим или неограниченным словарём. Благодаря стандартизации платформ и операционных систем телефонов расширяется круг сторонних разработчиков программных продуктов с данной функциональностью [22].

Значительно более развита ниша программ распознавания речи для персональных компьютеров, где уже достаточно давно существуют такие продукты как IBM ViaVoice, DragonDictate или «Горыпыч» (являющийся локализованной версией системы DragonDictate, изначально ориентированной на английский язык), а также уже упоминавшиеся отечественные разработки Сакрамепт и SPIRIT.

Отечественные разработки обладают тем преимуществом перед зарубежными, что они изначально ориентированы на русские фонемы. В отсутствии такой базы иностранные системы вынуждены работать с русским языком на основе английских фонем или некоторого общего и универсального их набора, что отрицательно сказывается на качестве распознавания. Так, по сообщениям прессы, первый зарубежный коммерческий продукт распознавания русской речи для телефонных приложений, включающий поддержку русских фонем, появился лишь в 2003 году - набор программных модулей, библиотек и утилит для разработки систем такого класса - SpeechPearl компании Philips Speech Processing [56].

Аппаратная база подобных систем на сегодняшний момент устоялась на нескольких основных вариантах:

1) Системы PC-класса на основе х86-совместимых процессоров для программных продуктов, используемых в настольных компьютерах, в некоторых серверных или мобильных решениях;

2) Мобильные устройства (телефоны, коммуникаторы и т.п.) на основе процессорной архитектуры ARM (более 75% всех интегрированных процессоров, выпускаемых в мире) [24];

3) Специализированные аппаратные решения на основе DSP-процессоров с тенденцией замены их массовыми решениями из предыдущих двух классов, так как возросшая производительность универсальных процессоров позволяет решать задачи, прежде бывшие для них весьма тяжёлыми.

Тенденция экстенсивного наращивания производительности процессоров за счёт увеличения их рабочих частот, имевшая место в предыдущие годы, уступает место новой тенденции, нацеленной на активное использование параллелизма в различных его проявлениях. В ближайшие годы это выльется в создание многоядерных архитектур процессоров (от уже существующей технологии Intel HyperThreading к созданию двух- и более ядерных процессоров на одном кристалле, появления которых можно ожидать уже в 2006 году; крайне интересная технология Cell от альянса Sony, Toshiba и IBM, которая затронет не только компьютеры, но,.потенциально, и бытовую технику в доме), создание недорогих кластерных решений на основе стандартных компонент (начиная с проекта BeoWulf для ОС Linux) и массовое использование распределённых вычислений (от уже реализовавшихся одиночных проектов типа distributed.net для взлома шифров или SETI@Home для поиска внеземных цивилизаций к технологии GRID и виртуализации вычислений, активно продвигаемых корпорацией IBM).

По мнению многих аналитиков и представителей различных компаний, грядёт эра параллельного программирования [25]. Одним из первых её предвестников можно назвать уже существующую технологию EPIC (Explicitly Parallel Instruction Computer) компании Intel, реализованную в коммерческих процессорах Itanium. Переход на новые параллельные архитектуры требует создания чрезвычайно сложных оптимизирующих компиляторов, изменения образа мышления программистов и приложения ими специальных усилий для разработки и реализации соответствующих алгоритмов. В таких условиях особую ценность представляют алгоритмы, учитывающие возможный параллелизм своей работы.

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

СММ - это довольно мощный (хотя и громоздкий) и весьма эффективный математический аппарат для решения задач распознавания речи [8]. Использование СММ для распознавания команд давно показало свою эффективность, а возросшие доступные вычислительные мощности открыли дорогу к использованию новых подходов к решению задач, встающих перед разработчиком подобных систем.

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

Отсюда следует, что задача обучения модели, причём её качественного обучения, является весьма актуальной и её решению должно уделяться повышенное внимание.

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

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

Генетические алгоритмы уже активно используются для обучения нейронных сетей, проектирования структуры механизмов и составления расписаний, для оптимизации структуры телекоммуникационных сетей и размещения электронных элементов на плате, поиска оптимальной формы детали и раскроя ткани и т.д. Так, израильская компания «Schema» на основе генетических алгоритмов разработала программный продукт Channeling для оптимизации работы сетей сотовой связи путём выбора оптимальной частоты, на которой будет вестись разговор [44]; компания Boeing использовала генетические алгоритмы для оптимизации турбины двигателя самолёта Boeing 777, оказавшейся по крайней мере на 1% эффективнее с точки зрения расхода топлива (что для данной отрасли считается неожиданной удачей), а фирма Texas Instruments задействовала их для оптимизации расположения компонентов на чипе, чтобы создать как можно меньший по размерам чип, и использование ГА позволило сделать его на 18% меньшим по площади [79].

За рубежом известно несколько случаев применения ГА для оптимизации СММ в системах распознавания речи, ориентированных на английский язык [54, 76, 77]. Но различия в фонематической базе русского и английского языков, уже выступавшие причиной плохой работы иностранных систем распознавания речи с русским языком, не позволяют однозначно перенести на него опыт применения ГА, а отечественных работ подобной направленности на момент написания диссертации не обнаружено. К тому же перечисленные зарубежные работы имеют обзорный и довольно поверхностный характер, не несут в себе сколь-нибудь серьёзного анализа альтернатив реализации ГА и практически не содержат обоснования выбора применяемых решений.

В третьей главе диссертации предлагается разработанная автором в рамках программно-аппаратного комплекса «Иволга» конкретная реализация генетического алгоритма, предназначенного для оптимизации процесса обучения СММ тренировочными последовательностями. За основу взята разработанная на кафедре ЭВА МИЭМ в 1998 г. А.А.Серовым система оценки стартовых параметров непрерывных СММ в задачах распознавания команд при кепстральной предобработке речевого сигнала (система

SdiApp). Основной задачей SdiApp является получение стартовых параметров СММ для изолированных слов. Результаты её работы используются в разработанной автором системе «Иволга» как отправная точка для работы генетического алгоритма. В этой главе также рассмотрены различные альтернативы и предложены варианты кодирования хромосом ГА, выбраны реализации генетических операторов, подходящие для работы с непрерывными СММ, определены параметры генетического алгоритма, обеспечивающие наиболее эффективное решение поставленной задачи.

В четвёртой главе диссертации производится оценка эффективности генетических алгоритмов в решении задачи обучения СММ. Тестирование системы проводилось с использованием имеющейся речевой базы данных (РБД), также разработанной на кафедре ЭВА МИЭМ А.Г.Бурёй. Произведено сравнение результатов работы ГА с традиционными методами поиска оптимальных решений для СММ, рассмотрено влияние параметров генетического алгоритма на эффективность его работы, предложены варианты дальнейшего развития алгоритма, направленные на повышение скорости и устойчивости его работы.

Исследование автора показало, что ГА успешно справляются с поставленными задачами, являясь эффективным методом обучения СММ, свободным от основных недостатков традиционно используемого метода Баума-Велча, при этом успешно сочетаясь с ним в рамках единой системы распознавания речи. Кроме того, с учётом современных тенденций развития аппаратной части систем распознавания генетические алгоритмы имеют очень хорошие перспективы по части оптимизации эффективности своей работы, так как позволяют легко распараллелить работу ГА и распределить её между разными процессорами (или процессорными ядрами) в одной машине или между разными компьютерами в сети.

В приложении 1 приведено описание программного комплекса «Иволга», предназначенного для исследования генетических алгоритмов в рамках задачи распознавания голосовых команд.

В приложении 2 приведён пример работы системы генетических алгоритмов в рамках программного комплекса «Иволга».

Выводы и заключение

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

2. Для решения задачи оптимизации обучения СММ разработан наиболее приспособленный для этой цели ГА, выбран и реализован механизм кодирования хромосом вещественным числами, создана фитнес-функция, вычисляющая вероятность генерации тестовой последовательности моделью наиболее эффективным способом. Разработанные генетические операторы ориентированы на работу с СММ и учитывают характерные для них ограничения. На основании теоремы схем показано, что выбранный оператор отбора ведёт к эффективному нахождению более хороших решений задачи. Определены условия эффективного применения различных вариантов реализации критерия останова ГА. Экспериментально определены наиболее эффективные значения параметров алгоритма (размер популяции, вероятность мутации) для использования в задаче обучения СММ.

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

4. Экспериментально определены параметры, оказывающие влияние на эффективность решения алгоритмом поставленной задачи. Предложены методы, направленные на дальнейшее повышение эффективности и качества работы ГА в контексте рассматриваемой задачи: возможность оптимизации выбора параметров с использованием 2-уровневого ГА и использование комбинированной фитнес-фупкции. Это открывает путь к созданию самообучающихся систем распознавания и позволяет повысить качество распознавания команд при работе с разными дикторами, дикторами в условиях стресса, с дикторами, речь которых имеет особенности в виде «проглатывания» части звуков, а также в телекоммуникационных системах при работе по каналам связи низкого качества, где часть голосовой информации может быть потеряна, в том числе и в сетях сотовой связи или 1Р-телефонии.

5. В рамках работы создан -программно-аппаратный комплекс «Иволга» для исследования генетических алгоритмов. Программная его часть является дополнением системы SdiApp, решающей задачу оценки стартовых параметров СММ и функционирующей на кафедре ЭВА МИЭМ с 1998 г., и написана в среде Borland С++ Builder 6. Необходимая для работы аппаратная часть - ПК с процессором класса Pentium-З 500МГц и 256Мб оперативной памяти, а также звуковая карта, поддерживающая при записи звука частоты дискретизации до 44КГц.

6. Автором предлагается следующая схема организации процесса обучения в системе распознавания речевых команд на основе СММ: система содержит модуль, реализующий обучение традиционным методом Баума-Велча и параллельно несёт в себе модуль ГА. Первоначальное обучение марковской модели слова производится с помощью метода Баума-Велча, а в дальнейшем (например, во время простоя системы, когда вычислительные ресурсы компьютера свободны) производятся запуски системы ГА как со случайной стартовой популяцией, так и с популяцией, построенной на основе уже обученных моделей. При нахождении генетическим алгоритмом модели слова лучшей, чем имеющаяся в словаре системы, производится её замена на новую. Данный подход позволяет произвести быстрое начальное обучение системы и затем работать над улучшением моделей слов в словаре (в том числе и имея возможность распределить вычисления между различными компьютерами в сети). Предложенное в данной работе решение задачи оптимизации обучения СММ способно улучшить процесс обучения СММ тренировочными последовательностями и повысить надёжность работы систем распознавания речевых команд, использующих в своей работе марковские модели.

1. Апдрейчиков А.В., Апдрейчикова О.Н. Интеллектуальные информационные системы: Учебник. - М.: Финансы и статистика, 2004. - 424 е.: ил.

2. Анохин П.К. «Философский смысл проблемы естественного и искусственного интеллекта», Вопросы философии (1973, № 6, с.83-97).

3. Баричев С. «Нас мало, но мы супер!», Компьютерра, #47 (571), 2004, стр.19.

4. Белянин В.П. «Психолингвистика: учебник». М.:Флинта: Московский психолого-социальный институт, 2003. - 232 с.

5. Буря А.Г. «Фонетическая база данных для речевых исследований», Диплом, Москва, МИЭМ, 2000

6. Витяев Е.Е. «Вероятностное прогнозирование и предсказание как принцип работы мозга» // Измерение и Модели Когнитивных Процессов, Труды ИМ СО РАН (Выч. системы, 162), Новосибирск, 1998, Стр. 14-40.

7. Галунов В.И. «Актуальные проблемы речевой акустики», Акустика речи. Медицинская и биологическая акустика. Сборник трудов XIII сессии Российского акустического общества. Т.З. М.: ГЕОС, 2003. - 274 с. Стр.16-19.

8. Галунов В.И. «Современные речевые технологии (обзорная статья)», 1999, http://www.auditech.ru/article/cntrid/click.php?action=download&id=5.

9. Галунов В.И., Кутуков Г.П., Матюнин С.Н. «Состояние исследований в области речевых технологий и задачи, выдвигаемые государственными заказчиками», Секция по автоматическому распознаванию и синтезу речи РАН, 1999.

10. Галяшипа Е.И. «Основы судебного речеведения», изд-во СТЭНСИ, 2003.

11. Годфруа Ж. «Что такое психология»: В 2-х т. Изд 2-е, стереотипное. Т.1: Пер. с франц. М.: «Мир», 1999.-496 е., ил.

12. Дубров A.M., Мхитарян B.C., Трошин Л.И. «Многомерные статистические методы» -Финансы и статистика, Москва, 1998.

13. Дьяконов В. «MATLAB. Обработка сигналов и изображений. Специальный справочник». СПб.: Питер, 2002. - 608 с.:ил.

14. Златоустова JI.B., Потапова Р.К., Потопов В.В., Трунин-Допской В.Н. «Общая и прикладная фонетика». М.: МГУ, 1997.

15. Иконин С.Ю., Сарана Д.В. «Система автоматического распознавания речи SPIRIT ASP Engine», Цифровая обработка сигналов, #3,2003.

16. Капра Ф. «Паутина жизни. Новое'научное понимание живых систем», К.: София; 2002.

17. Клемент Р. «Генетические алгоритмы: почему они работают? Когда их применять?», Компьютерра, №289, 1999, стр. 20-23.

18. Кольман Я., Рём К.-Г. «Наглядная биохимия»: Пер. с нем. М.: Мир, 2000. - 469 с.

19. Корнеев В.В., Гареев А.Ф., Васютин С.В., Райх В.В. «Базы данных. Интеллектуальная обработка информации». М.: «Нолидж», 2000. - 352 е., ил.

20. Короткое А.В. «Послесловие к матрице: виртуальные миры или искусственная жизнь». М.: МПБ «Деловая культура»; Альпина Бизнес Букс, 2005. - 308 с.

21. Косарев Ю.А. «Естественная форма диалога с ЭВМ». — Л.Машиностроение, 1989.

22. Кочетков А. «Умные телефоны заговорили», Компьютерра #16 (588), 2005, стр.50-51.

23. Люгер Дж. «Искусственный интеллект: стратегии и методы решения сложных проблем», 4-е издание.: пер.с англ. М.:Издательский дом «Вильяме», 2003, - 864 с.

24. Озеров С. «Архитектура CPU», Компьютерра #37 (609), 2005, стр.24-39.

25. Озеров С. «Ячейка. Она же клетка, она же. Cell», Компьютерра #38 (610), 2005, стр.3 8-41.

26. Петере Э. «Хаос и порядок на рынках капитала. Новый аналитический взгляд на циклы, цены и изменчивость рынка»гПер. с англ. М.: Мир, 2000, - 333 с.

27. Пиотровский Р.Г. и др. «Математическая лингвистика. Учеб. пособие для пед. ин-тов». М., «Высшая школа», 1977.

28. Попов Э.В. «Общение с ЭВМ на естественном языке». Изд. 2-е, стереотипное. М.: Едиториал УРСС, 2004. - 360 с. (Науки об искусственном.)

29. Потёмкин В.Г. «MATLAB 6: среда проектирования инженерных приложений». М.: Диалог-МИФИ, 2003. - 448 с.

30. Саймон Г. «Науки об искусственном». Пер с англ. Изд. 2-е. М.: Едиториал УРСС, 2004. 144 с. (Науки об искусственном.)

31. Самойленко А.П., Дюк В.А. Data Mining. Учебный курс, изд-во Питер, 2001

32. Серов А.А. «Оценка стартовых параметров СММ в задачах распознавания команд при кепстральной предобработке речевого сигнала», диссертация, УДК 534.78, Москва, МИЭМ, 2001.

33. Скляр Б. «Цифровая связь. Теоретические основы и практическое применение». Изд. 2-е, испр.: Пер. с англ. М.:Издательский дом «Вильяме», 2003. - 1104 е.: ил.

34. Солонина А.И., Улахович Д.А., Яковлев JI.A. «Алгоритмы и процессоры цифровой обработки сигналов». СПб.: БХВ-Петербург, 2002. - 464 е.: ил.

35. Солсо Р. «Когнитивная психология». СПб.:Питер, 2002. - 592 с.

36. Сусов И.П. «Введение в теоретическое языкознание. Основы общей фонетики и фонологии». (http://www.tversu.ru/~ips')

37. Таран О., Мирошниченко С., Гуриев В. «Ничего никому не скажу?», Компьютерра, #36 (608), 2005, стр.25-33.

38. Тейлор Д., Грин Н., Стаут У. «Биология»: в 3-х т. Т.1: Пер. с англ./Под ред. Р.Сопера -3-е изд.,-М.: Мир, 2001.-454 с. "

39. Тьюринг А. «Может ли машина мыслить?» (С приложением статьи Дж. фон Неймана «Общая и логическая теория автоматов». Пер. и примечания Ю.В. Данилова). М.: ГИФМЛ, 1960.

40. Уитби Б. «Искусственный интеллект: реальна ли Матрица». М.: Фаир-пресс, 2004, 210 с.

41. Хофштадтер Д., Деннетт Д. «Глаз разума». Самара: Издательский дом «Бахрах-М», 2003.-432 с.

42. Цой Ю. «Модели ГА», http://qai.narod.ru/GA/gamodels.html

43. Ярушкина Н.Г. «Основы теории нечётких и гибридных систем»: Учеб. пособие. М.: Финансы и статистика, 2004, - 320 с.

44. Artificial Intelligence FAQ «What are Gray codes, and why are they used?», http://www.faqs.org/faqs/ai-faq/genetic/part6/section-l.html

45. Back Th., «Evolutionary Algorithms in theory and practice», Oxford University Press, 1996.

46. Back Th., «Self-Adaptation in Genetic Algorithms», University of Dortmund, Department of Computer Science, Dortmund, Germany, 1992.

47. Baum L.E., Petrie Т., «Statistical inference for probabilistic functions of finite state Markov chains», Ann. Math. Stat., vol.37, pp.1554-1563, 1966.

48. Baum L.E. «An inequality and associated maximization technique in statistical estimation for probabilistic functions of Markov processes», Inequalities, vol.3, pp. 1-8, 1972.

49. Blickle Т., Thiele L., «А Comparison of Selection Schemes used in Genetic Algorithms», Computer Engineering and Communication Networks Lab, Swiss Federal Institute of Technology, Zurich, Switzerland, 1995.

50. Burger Y. «Мягкие вычисления», http://www.getinfo.ru/print28 O.html

51. Carnegie Mellon Engineering Researchers To Create Speech Recognition in Silicon, 13 September 2004, http://www.cmu.edu/PR/releases04/040913 speech.html

52. Capra F. «The Hidden Connections», Harper Collins Publishers, 2002, ISBN 0-00-257047-5.

53. Chau C.W., Kwong S., Diu C.K., Fahrner W.R. «Optimization of HMM by a Genetic Algorithm», Proceedings of the 1997 International Conference on Acoustics, Speech and Signal Processing, 1997, pp. 1727-1730.

54. Clement R.P., Wren A. «Genetic Algorithms and Bus-Driver Scheduling», Presented at the 6th International Conference for Computer-Aided Transport Scheduling, Lisbon, Portugal, 1993.

55. CompTek, «В России появился первый коммерческий продукт распознавания русской речи для телефонных приложений», http://news.telecominfo.ru/print.phtml?nid=::26076.

56. Daridi F., Kharma N., Salik J.F.N. «Parameterless Genetic Algorithms: Review and Innovation», IEEE Canadian Review, Summer 2004, No. 47.

57. Deb K., Agrawal S. «Understanding Interactions Among Genetic Algorithm Parameters», Kanpur Genetic Algorithms Laboratory, Kanpur, India, 1998.

58. De Jong, K.A. «An analysis of the behavior of a class of genetic adaptive systems». Doctoral dissertation, University of Michigan, Ann-Arbor, MI (University Microfilms No. 76-9381), 1975.

59. Eiben A.E., Marchiori E., Valko. «Evolutionary Algorithms with on-the-fly Population Size Adjustment», Department of Artificial Intelligence, Vrije Universiteit Amsterdam, 2004.

60. Eiben A.E., Hinterding R., Michalewicz Z. «Parameter control in evolutionary algorithms», IEEE Transactions on Evolutionary Computation, Vol.3, No.2, 1999, pp.124-141.

61. Elliott L., Ingham D., Kyne A., Mera N., Pourkashanian M., Whittaker S. «Efficient Clustering-Based Genetic Algorithms in Chemical Kinetic Modelling», GECCO 2004 Proceedings, Springer-Verlag Berlin Heidelberg, 2004, pp.932-944.

62. Fogarty Т., Terence C. «Varying the probability of mutation in the genetic algorithm», Proceeding of the Third International Conference on Genetic algorithms, Morgan Kufmann, 1989, pp.104-109.

63. Fogel L.J., Owens A.J., Walsh M.J. «Artificial Intelligence Through Simulated Evolution», John Wiley, 1966.

64. Gales M. «The Theory of Segmental Hidden Markov Models», Cambridge University, 1993.

65. Galunov V.I., Soloviev A.N. «Black Patches in the Field of Automatic Speech Recognition», Proceedings of XV Session of the Russian Acoustic Society, Nizhny Novgorod, November 15-18, 2004. pp.412-415.

66. Goldberg D.E. «Genetic Algorithms in Search, Optimization and Machine Learning». Reading, MA: Addison-Wesley, 1989.

67. Goldberg D.E., Deb К., Clark J.H. «Genetic algorithms, noise, and the sizing of populations», Complex systems, 6(4), 1992, August, pp.333-362.

68. Gorges-Schleuter M. «Explicit Parallelism of Genetic Algorithms through Population Structures». Paralles Problem Solving from Nature, Springer Verlag, 1991, pp. 150-159.

69. Grefenstette J.J. «Optimization of Control Parameters for Genetic Algorithms». IEEE Trans. Systems, Man, and Cybernetics, 16(1), 1986, pp.122-128.

70. Hand D., Mannila H., Smyth P. «Principles of Data Mining», Massachusetts Institute of Technology, 2001, ISBN 0-262-08290-X.

71. Holland J.H. «Adaptation in Natural and Artificial Systems: 2nd edition», MIT Press, 1992.

72. Holland J.H. «Building Blocks, Cohort Genetic Algorithms, and Hyperplane-Defined Functions», MIT Press, Evolutionary Computation #8(4), 2000, pp.373-391.

73. Jelinek F. «Statistical Methods for Speech Recognition», Massachusetts Institute of Technology, 1998, ISBN 0262100665.

74. Kaiser J. «Training of HMM with Genetic Algorithms», University of Maribor, Faculty of Electrical Engineering and Computer Science, Slovenia.

75. Kaiser J., KafiiC Z. «UCenje prikritih modelov Markova z genetskimi algoritmi», Fakulteta za elektrotehniko, ra£unalni§tvo in informatiko, Univerza v Mariboru, Slovenija.

76. Koutras A., Dermatas E., Kokkinakis G. «Recognizing simultaneous speech: a genetic algorithm approach», WCL, Electrical and-Computer Engineering Dept., University of Patras, Greece.

77. Luke S. «When Short Runs Beat Long Runs», George Mason University. In GECCO-2001: Proceedings of the Genetic and Evolutionary Computation Conference. Lee Spector et al, eds. Morgan Kaufmann, 2001, pp. 74-80.

78. Marczyk A. «Genetic Algorithms and Evolutionary Computation», 2004, http://www.talkorigins.org/faqs/genalg/genalg.html.

79. Mathias K., Whitley D. «Transforming the Search Space with Gray Coding», Department of Computer Science, Colorado State University, 1994.

80. Penrose R. «Shadows of the Mind», Vintage Science, 1995, ISBN 0-09-958211-2.

81. Popovici E., De Jong K. «Understanding EA Dynamics via Population Fitness Distributions», Department of Computer Science, George Mason University, Fairfax, USA, 2003.

82. Rabiner L.R., «А tutorial on Hidden Markov Models and Selected Applications in Speech Recognition», Proceedings of the IEEE, vol, 77. no.2, February 1989, pp. 257-284.

83. Rechenberg I. «Evolutions strategic: Optimierung technischer systeme nach prinzipien der biologischen evolution», Frommann, 1973.

84. Sakrament ASR Engine, http://www.sakrament.com

85. Sastry K., O'Reilly U.M., Goldberg D.E. «Population Sizing for Genetic Programming Based Upon Decision Making», IlliGAL Report No. 2004028, April, 2004.

86. Schwefel H-P. «Numerische optimierung von computer-modellen mittels der evolutionsstrategie», Volume 26 of Interdisciplinary systems research. Birkhauser, Basel, 1997.

87. Smith W.S. «The Scientist and Engineer's Guide to Digital Signal Processing», Second Edition, California Technical Publishing, San Diego, California, 1999, ISBN 0-9660176-6-8

88. SPIRIT Corp., http://www.spirit.ru90. «StatSoft's Electronic Statistics Textbook», 1999

89. Tegmark M. «Parallel Universes», Scientific American, May, 2003.

90. Vector Quantization, http://www.data-compression.com/vq.shtml

91. Viterbi A.J., «Error bounds for convolutional codes and an asymptotically optimal decoding algorithm». IEEE Trans. Informat. Theory, vol. IT-13, pp. 260-269, Apr. 1967.

92. Whitley D. «А Genetic Algorithm Tutorial», Computer Science Department, Colorado State University, USA, 1993.

93. Wikipedia. «Genetic algorithm», http://en.wikipedia.org/wiki/Genetic algorithm.

94. Wikipedia. «Artificial life», http://en.wikipedia.org/wiki/Artificial life.1. Предметный указатель

95. ЕМ (expectation-modification) метод.28

96. Forward-Backward процедура.25nGA.102pGA, parameterless GA.100