Книги, научные публикации
Pages: | 1 | 2 | 3 | -- [ Страница 1 ] --
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ ЭЛЕКТРОНИКИ И МАТЕМАТИКИ (ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)
На правах рукописи
УДК 50.10.41 САПУНОВ Григорий Владимирович СИСТЕМА АВТОМАТИЧЕСКОГО РАСПОЗНАВАНИЯ РЕЧЕВЫХ
КОМАНД ДЛЯ ПАРАЛЛЕЛЬНЫХ АРХИТЕКТУР 05.13.05 - У Элементы и устройства вычислительной техники и систем управления Ф Диссертация на соискание ученой степени кандидата технических наук
Научный консультант: проф., д.т.н. Петров Геннадий Михайлович Москва - 2005 Оглавление ОГЛАВЛЕНИЕ................................................................................................................................................... 2 АННОТАЦИЯ..................................................................................................................................................... 4 ВВЕДЕНИЕ......................................................................................................................................................... 5 ГЛАВА 1. АНАЛИЗ ОСНОВНЫХ ПРОБЛЕМ ПРИМЕНЕНИЯ СКРЫТЫХ МАРКОВСКИХ МОДЕЛЕЙ В СИСТЕМАХ РАСПОЗНАВАНИЯ РЕЧИ.............................................................................. 12 1.1 ЧТО ТАКОЕ МАРКОВСКАЯ МОДЕЛЬ.................................................................................................................. 15 1.2 СКРЫТАЯ МАРКОВСКАЯ МОДЕЛЬ (СММ)........................................................................................................ 16 1.3 ОСНОВНЫЕ ЗАДАЧИ ПРИ ПРИМЕНЕНИИ СММ К РАСПОЗНАВАНИЮ РЕЧИ......................................................... 18 1.4 ТИПЫ СММ, ПРИМЕНЯЕМЫЕ В СИСТЕМАХ РАСПОЗНАВАНИЯ РЕЧИ................................................................. 21 1.5 ПОДХОДЫ К РЕШЕНИЮ ОСНОВНЫХ ЗАДАЧ СММ............................................................................................ 24 1.5.1 Задача 1. Эффективное вычисление вероятности генерации заданной последовательности...... 24 1.5.2 Задача 2. Отыскание оптимальной последовательности состояний............................................ 27 1.5.3 Задача 3. Обучение СММ тестовыми последовательностями...................................................... 28 1.6 ВЫВОДЫ......................................................................................................................................................... 30 ГЛАВА 2. СРАВНИТЕЛЬНАЯ ОЦЕНКА МЕТОДОВ ОПТИМИЗАЦИИ В ЗАДАЧЕ ОБУЧЕНИЯ СММ.................................................................................................................................................................. 31 2.1 СХЕМА ПРОЦЕССА ПРИНЯТИЯ РЕШЕНИЯ КАК ЗАДАЧИ ПОИСКА........................................................................ 31 2.2 ТРАДИЦИОННЫЕ МЕТОДЫ ПОИСКА ОПТИМАЛЬНЫХ РЕШЕНИЙ И ИХ ПРИЛОЖЕНИЕ К ЗАДАЧЕ ОБУЧЕНИЯ СММ 33 2.2.1 Методы, основанные на математических вычислениях................................................................. 33 2.2.2 Перечислительные методы.............................................................................................................. 34 2.2.3 Методы, использующие элементы случайности............................................................................. 36 2.3 КОНЦЕПЦИЯ ЭВОЛЮЦИОННЫХ ВЫЧИСЛЕНИЙ................................................................................................. 36 2.4 ОСНОВЫ ТЕОРИИ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ (ГА)...................................................................................... 39 2.5 ПОСЛЕДОВАТЕЛЬНОСТЬ РАБОТЫ ГЕНЕТИЧЕСКОГО АЛГОРИТМА....................................................................... 41 2.6 ВЫЧИСЛИТЕЛЬНАЯ ЭФФЕКТИВНОСТЬ ПРИМЕНЕНИЯ ГА. ТЕОРЕМА СХЕМ........................................................ 45 2.7 ВЫВОДЫ......................................................................................................................................................... 52 ГЛАВА 3. РЕАЛИЗАЦИЯ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ДЛЯ РЕШЕНИЯ ЗАДАЧИ ОПТИМИЗАЦИИ СММ.................................................................................................................................. 54 3.1 СИСТЕМА РАСПОЗНАВАНИЯ РЕЧЕВЫХ КОМАНД НА ОСНОВЕ СММ.................................................................. 54 3.2 ПОСТРОЕНИЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ДЛЯ ОПТИМИЗАЦИИ ПРОЦЕССА ОБУЧЕНИЯ СММ ТРЕНИРОВОЧНЫМИ ПОСЛЕДОВАТЕЛЬНОСТЯМИ.................................................................................................... 55 3.2.1 Кодирование хромосомы.................................................................................................................. 55 3.2.2 Создание исходной популяции.......................................................................................................... 59 3.2.3 Размер популяции............................................................................................................................. 64 3.2.4 Генетические операторы: оператор отбора.................................................................................. 66 3.2.5 Генетические операторы: оператор скрещивания......................................................................... 66 3.2.6 Генетические операторы: оператор мутации............................................................................... 69 3.2.7 Генетические операторы: оператор редукции............................................................................... 73 3.2.8 Критерий останова алгоритма....................................................................................................... 74 3.3 ВЫВОДЫ......................................................................................................................................................... 78 ГЛАВА 4. ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ ОПТИМИЗАЦИИ СММ С ИСПОЛЬЗОВАНИЕМ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ............................................................................................................... 81 4.1 СРАВНЕНИЕ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ С ТРАДИЦИОННЫМИ МЕТОДАМИ................................................... 81 4.1.1 Метод Баума-Велча.......................................................................................................................... 81 4.1.2 Случайный поиск............................................................................................................................... 90 4.2 ПОКАЗАТЕЛИ ЭФФЕКТИВНОСТИ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ........................................................................ 93 4.2.1 Скорость работы генетического алгоритма................................................................................. 93 4.2.2 Средства повышения скорости работы генетических алгоритмов.............................................. 95 4.2.3 Устойчивость работы генетического алгоритма......................................................................... 96 4.2.4 Средства повышения устойчивости работы генетических алгоритмов...................................... 98 4.3 НАПРАВЛЕНИЯ РАЗВИТИЯ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ................................................................................. 4.3.1 Использование комбинированной фитнес-функции......................................................................... 99 4.3.2 Адаптивный ГА................................................................................................................................. 99 4.4 ВЫВОДЫ....................................................................................................................................................... 102 ВЫВОДЫ И ЗАКЛЮЧЕНИЕ....................................................................................................................... 105 ЛИТЕРАТУРА................................................................................................................................................ 108 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ..................................................................................................................... 114 ПРИЛОЖЕНИЕ 1. ОПИСАНИЕ ПРОГРАММНОГО КОМПЛЕКСА ДЛЯ ИЗУЧЕНИЯ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ............................................................................................................. 116 СТРУКТУРА И ФУНКЦИОНИРОВАНИЕ ПРОГРАММЫ.............................................................................................. 116 НАЗНАЧЕНИЕ МОДУЛЕЙ ПРОГРАММЫ................................................................................................................. 118 VCL.......................................................................................................................................................... 118 АЦП......................................................................................................................................................... 119 Таксоном.................................................................................................................................................. 119 DSP.......................................................................................................................................................... 119 ГА............................................................................................................................................................. 120 Настройка системы генетических алгоритмов.................................................................................... 120 ПОРЯДОК РАБОТЫ С ПРОГРАММОЙ..................................................................................................................... 123 Сохранение настроек.............................................................................................................................. 123 Загрузка настроек................................................................................................................................... 123 Диктовка слов......................................................................................................................................... 123 Чтение WAV-файла................................................................................................................................. 124 Создание новой модели........................................................................................................................... 124 ПРИЛОЖЕНИЕ 2. РЕЗУЛЬТАТЫ ЭКСПЕРИМЕНТАЛЬНОЙ ПРОВЕРКИ КОМПЛЕКСА НА ПЭВМ........................................................................................................................................................................... Аннотация Целью диссертационной работы является повышение эффективности работы современных систем управления, использующих системы автоматического распознавания речевых команд на основе скрытых марковских моделей (СММ). При фиксированной на сегодняшний день аппаратной базе подобных систем распознавания и, учитывая тенденции её развития в ближайшем будущем (переход к параллельным архитектурам), рассматривается один из наиболее важных блоков таких систем - блок обучения СММ тренировочными последовательностями. От успешного решения им задачи обучения марковской модели напрямую зависит качество работы системы распознавания. В задаче обучения СММ на данный момент есть две серьёзные проблемы: стандартные методы её решения (метод Баума-Велча или ЕМ-процедура) являются методами локальной оптимизации, (то есть, не способны выйти за пределы локальных экстремумов функции) и сильно зависимы от стартовых параметров. В поисках решения данной задачи в работе проводится исследование эффективности применения аппарата генетических алгоритмов (ГА) для оптимизации процесса обучения СММ тренировочными последовательностями. Акцент сделан на русскоязычных системах распознавания речевых команд. Для достижения поставленной цели в работе решены следующие основные задачи: Х Х Исследованы возможности применения ГА для оптимизации процесса обучения СММ тренировочными последовательностями. Разработан ГА, предназначенный для работы со скрытыми марковскими моделями речевых команд (рассмотрены альтернативы и выбрана схема кодирования хромосом, реализованы генетические операторы, определены наиболее эффективные значения параметров ГА). Х Исследована эффективность оптимизации обучения СММ с помощью ГА (произведено сравнение ГА с традиционными методами оптимизации обучения СММ и изучено влияние параметров ГА на эффективность этого процесса). Х Х Разработаны методы, направленные на дальнейшее повышение эффективности и качества работы ГА в контексте рассматриваемой задачи. Автором создан программно-аппаратный комплекс для исследования генетических алгоритмов на основе системы распознавания команд, использующей аппарат скрытого марковского моделирования и кепстральную предобработку речевого сигнала, разработанной на кафедре ЭВА МИЭМ.
Введение Работы в области систем распознавания речи имеют уже довольно долгую историю. В Советском Союзе работы по компресии речи начались в начале 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-класса на основе x86-совместимых процессоров для программных продуктов, используемых в настольных компьютерах, в некоторых серверных или мобильных решениях;
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]. Использование СММ для распознавания команд давно показало свою эффективность, а возросшие доступные вычислительные мощности открыли дорогу к использованию новых подходов к решению задач, встающих перед разработчиком подобных систем. Одной из важнейших и наиболее сложных задач, возникающих при работе с СММ, является задача обучения модели, то есть нахождения таких её параметров, при которых модель точнее описывает своё слово, т.е. генерирует для последовательности речевого сигнала, содержащего это слово, большее значение вероятности, чем другие модели слов из словаря системы. В процессе распознавания команды в системе происходит оценка и сравнение между собой вероятностей генерации наблюдаемого слова различными моделями из словаря с тем, чтобы отобрать среди них наиболее вероятного претендента. Чем лучше модель описывает тестовое (или тренировочное) слово, тем больше шансов, что оно будет верно распознано, т.е. будет выбрано среди всех остальных слов словаря. Особенно заметным становится влияние качества обучения модели на результативность работы системы распознавания в том случае, если словарь системы разрастается, и в нём оказываются похожие слова, т.е. слова, модели которых генерируют близкие значения вероятности. В таких условиях выбор правильного варианта оказывается затруднительным. Кроме того, желательно, чтобы модель могла эффективно распознавать своё слово по-возможности в более широких пределах изменяющихся условий работы системы распознавания (в различных уровнях зашумлённости или при работе по каналам различающегося качества) и вариативности произнесения слов диктором (в случае стресса или наличия дефектов речи). Отсюда следует, что задача обучения модели, причём её качественного обучения, является весьма актуальной и её решению должно уделяться повышенное внимание. Существуют и давно применяются оптимизированные методы обучения СММ (например, метод Баума-Велча или EM-метод), но они не свободны от недостатков, важнейшие среди которых - это сильная зависимость от начальных условий, порождающая задачу нахождения стартовых параметров СММ, и неспособность найти глобальный экстремум, если локальный экстремум оказывается ближе. Однозначно лучшего метода обучения СММ не известно, и для решения этой задачи могут применяться различные подходы. Одним из таких потенциально интересных методов обучения являются генетические алгоритмы (ГА). Генетические алгоритмы, относящиеся к концепции эволюционных вычислений, - это современное, перспективное и активно разрабатываемое направление методов оптимизации многокритериальных задач. Во второй главе диссертационной работы рассмотрена концепция ГА и их место среди других методов нахождения оптимальных значений, и проведена оценка их применимости к решению задачи обучения СММ. Генетические алгоритмы уже активно используются для обучения нейронных сетей, проектирования структуры механизмов и составления расписаний, для оптимизации структуры телекоммуникационных сетей и размещения электронных элементов на плате, поиска оптимальной формы детали и раскроя ткани и т.д. Так, израильская компания Schema на основе генетических алгоритмов разработала программный продукт Channeling для оптимизации работы сетей сотовой связи путём выбора оптимальной частоты, на которой будет вестись разговор [44];
компания Boeing использовала генетические алгоритмы для оптимизации турбины двигателя самолёта Boeing 777, оказавшейся по крайней мере на 1% эффективнее с точки зрения расхода топлива (что для данной отрасли считается неожиданной удачей), а фирма Texas Instruments задействовала их для оптимизации расположения компонентов на чипе, чтобы создать как можно меньший по размерам чип, и использование ГА позволило сделать его на 18% меньшим по площади [79]. За рубежом известно несколько случаев применения ГА для оптимизации СММ в системах распознавания речи, ориентированных на английский язык [54, 76, 77]. Но различия в фонематической базе русского и английского языков, уже выступавшие причиной плохой работы иностранных систем распознавания речи с русским языком, не позволяют однозначно перенести на него опыт применения ГА, а отечественных работ подобной направленности на момент написания диссертации не обнаружено. К тому же перечисленные зарубежные работы имеют обзорный и довольно поверхностный характер, не несут в себе сколь-нибудь серьёзного анализа альтернатив реализации ГА и практически не содержат обоснования выбора применяемых решений. В третьей главе диссертации предлагается разработанная автором в рамках программно-аппаратного комплекса Иволга конкретная реализация генетического алгоритма, предназначенного для оптимизации процесса обучения СММ тренировочными последовательностями. За основу взята разработанная на кафедре ЭВА МИЭМ в 1998 г. А.А.Серовым система оценки стартовых параметров непрерывных СММ в задачах распознавания команд при кепстральной предобработке речевого сигнала (система SdiApp). Основной задачей SdiApp является получение стартовых параметров СММ для изолированных слов. Результаты её работы используются в разработанной автором системе Иволга как отправная точка для работы генетического алгоритма. В этой главе также рассмотрены различные альтернативы и предложены варианты кодирования хромосом ГА, выбраны реализации генетических операторов, подходящие для работы с непрерывными СММ, определены параметры генетического алгоритма, обеспечивающие наиболее эффективное решение поставленной задачи. В четвёртой главе диссертации производится оценка эффективности генетических алгоритмов в решении задачи обучения СММ. Тестирование системы проводилось с использованием имеющейся речевой базы данных (РБД), также разработанной на кафедре ЭВА МИЭМ А.Г.Бурёй. Произведено сравнение результатов работы ГА с традиционными методами поиска оптимальных решений для СММ, рассмотрено влияние параметров генетического его работы. Исследование автора показало, что ГА успешно справляются с поставленными задачами, являясь эффективным методом обучения СММ, свободным от основных недостатков традиционно используемого метода Баума-Велча, при этом успешно сочетаясь с ним в рамках единой системы распознавания речи. Кроме того, с учётом современных тенденций развития аппаратной части систем распознавания генетические алгоритмы имеют очень хорошие перспективы по части оптимизации эффективности своей работы, так как позволяют легко распараллелить работу ГА и распределить её между разными процессорами (или процессорными ядрами) в одной машине или между разными компьютерами в сети. В приложении 1 предназначенного для приведено описание программного комплекса Иволга, исследования генетических алгоритмов в рамках задачи алгоритма на эффективность его работы, предложены варианты дальнейшего развития алгоритма, направленные на повышение скорости и устойчивости распознавания голосовых команд. В приложении 2 приведён пример работы системы генетических алгоритмов в рамках программного комплекса Иволга.
Глава 1. Анализ основных проблем применения скрытых марковских моделей в системах распознавания речи Системы распознавания речевых команд являются важным элементом современных систем управления, способных взаимодействовать с человеком посредством акустического канала. В зависимости от места применения конкретной системы управления, точность распознавания команд имеет различную важность: в одних системах допускается заметный процент ошибок (управление текстовым редактором или навигация в браузере), в других - ошибки распознавания крайне нежелательны и имеют высокую цену (управление работой станка или системой вооружения). В любом случае, разработчики подобных систем борются за уменьшение процента ошибок распознавания команд, как за наиболее значимую характеристику качества системы распознавания, отражающуюся в работе всей системы управления в целом. Структура типичной системы распознавания команд представлена на рис.1.1:
Рис. 1.1. Структура системы распознавания команд Аналоговый речевой сигнал, снятый с микрофона, поступает на вход системы, где производится его оцифровка (дискретизация по времени и квантование по амплитуде). Перед этим, как правило, сигнал дополнительно подвергается низкочастотной фильтрации так называемым фильтром ограничения спектра, чтобы избежать нарушения теоремы Котельникова о дискретизации (также известной как теорема Найквиста или Шеннона) и искажения спектра оцифрованного сигнала. Далее производится сегментация уже цифрового сигнала, во время которой определяются границы слов и входной поток разбивается на отдельные элементы, соответствующие словам. После этого производится предобработка выделенных речевых единиц, целью которой является сокращение объёма информации, с которой предстоит работать системе, с сохранением в то же время значимых информационных признаков речевого сигнала. Существует множество разных методов предобработ ки (спектральные коэффициенты, клиппирование, кепстральные коэффициенты и многие другие), имеющих свои наборы информационных признаков, обычно представляемых в виде неких коэффициентов. И далее управляющий процессор, оперируя полученными данными, производит сравнение их с памятью эталонов в системе, выбирая наиболее близкий, который и является результатом распознавания. В соответствии с этим результатом система распознавания выдаёт команду на устройство или иной блок системы управления, в рамках которой она реализована. В режиме обучения системы распознавания вместо выдачи выходной команды управляющий процессор производит сохранение нового эталона во внутренней памяти системы для последующей работы. Как видно из схемы, типичная система распознавания команд содержит несколько модулей, каждый из которых оказывает влияние на итоговый процесс распознавания и может быть подвергнут модификации в целях улучшения характеристик системы распознавания в целом. Так, при реализации модуля оцифровки выбирают требуемую частоту выборки, разрядность и число каналов АЦП, параметры фильтра ограничения спектра и оценивают возможную необходимость в дополнительных устройствах типа устройств шумоподавления или компенсации эха. Для систем, реализованных на базе персонального компьютера эта часть работы выполняется звуковой картой, выдающей на выходе цифровой сигнал с разрядностью 8 или 16 бит и частотой дискретизации до 44.1КГц (а более современные модели с разрядностью до 24 бит и частотой дискретизации до 48, 96 или 192КГц). Алгоритм сегментации также может быть реализован различными способами, определяя паузы между словами по энергии сигнала, с учётом шума или без него. Методов предобработки также известно великое множество, наиболее распространённые среди которых - это клиппирование, спектральные коэффициенты, LPC (Linear Prediction Coefficients) или ЛПК (коэффициенты линейного предсказания), кепстральная предобработка, PLP (Perceptual Linear Predictive), Rasta, ASSF и другие. Значительная часть систем работает с кепстральными коэффициентами, которые считаются достаточно хорошей моделью, соответствующей модели речеобразования человека. Далее в работу включается управляющий процессор, оперирующий моделями слов. Чаще всего для этого используются скрытые марковские модели (СММ). В настоящее время известно немалое число систем распознавания, построенных с использованием аппарата СММ. Использование СММ является на сегодняшний день наиболее популярным и успешно применяемым подходом к проблеме распознавания речи. Помимо систем распознавания речи на основе СММ существуют также системы на основе нейронных сетей (НС) и методов динамического программирования (ДП).
Аппаратная база таких систем также может быть весьма разнообразной и оказывать заметное влияние на итоговую эффективность системы распознавания в целом. Как было отмечено во введении, на данный момент есть несколько наиболее распространённых устоявшихся вариантов её реализации, весьма распространённым среди которых является персональный компьютер архитектуры x86. Аппаратная часть систем распознавания уже не является самым узким местом и способна выполнять качественную оцифровку речевого сигнала с требуемыми параметрами, а также обеспечивает требуемые вычислительные мощности для реализации необходимых алгоритмов предобработки и работы с моделями слов. Во введении была отмечена важность качественного обучения системы распознавания или создания как можно более хороших моделей слов в случае системы, основанной на СММ. Именно этой задаче будет уделено основное внимание в диссертационной работе, поскольку другие основные модули систем распознавания команд сегодня обладают довольно хорошими характеристиками. Использование СММ для распознавания речи базируется на следующих предположениях [15]: 1) Речь может быть разбита на сегменты (состояния), внутри которых речевой сигнал может рассматриваться как стационарный. Переходы между этими состояниями осуществляется мгновенно. 2) Вероятность символа наблюдения, порождаемого моделью, зависит только от текущего состояния модели и не зависит от предыдущих порождённых символов. По сути, ни одно из этих двух предположений не является справедливым для речевого сигнала, и большое количество исследований было посвящено тому, чтобы сгладить недостатки этих предположений [65]. Так в русском языке для взрывных звуков типа [п] или [б] неверно предположение 1, поскольку речевой сигнал в пределах фонемы сильно изменяется - сначала резко и быстро нарастает и затем так же быстро спадает почти к нулевому уровню, что и нашло отражение в названии таких звуков. Предположение 2 спорно, например, в силу того, что вероятность появления звука зависит от его положения в слове - так сочетание звуков [ой] более характерно для окончаний, чем для начала слова. Тем не менее, стандартные СММ являются основой для большинства современных систем распознавания речи. При использовании СММ перед разработчиком встают несколько серьёзных задач, которые будут рассмотрены далее в этой главе.
1.1 Что такое марковская модель Рассмотрим систему, которая в произвольный момент времени может находиться в одном из N различных состояний S1, S2,..., SN, как показано на рисунке 1.2.
S S S S Рис. 1.2. Марковская модель В дискретные моменты времени t = 1, 2,... система переходит из одного состояния в другое, но может оставаться и в существующем (текущее состояние в момент времени t будем описывать как q t). При этом переходы осуществляются в соответствии с некоторой матрицей вероятностей, описываемой как aij, где aij = P[ qt = Sj | qt-1 = Si ], 1i,jN aij0 (1.1) При этом aij имеет следующие свойства: (1.2) ij a j= N = (1.3) Такой стохастический процесс называется марковским процессом. Результатом наблюдения такого процесса является последовательность состояний, которые система проходит за время наблюдения. Рассмотрим для примера марковскую модель погоды с тремя состояниями. Будем считать, что наблюдаемая раз в день (например, в полдень) погода может иметь одно из следующих состояний: S1 - дождь (снег) S2 - облачно S3 - ясно Условимся, что погода в день t описывается одним из трёх указанных выше состояний, и матрица вероятностей переходов имеет вид: 0.4 0.3 0.3 A = {a ij } = 0.2 0.6 0.2 0.1 0.1 0.8 Считая, что погода в первый день (t=1) солнечная (состояние 3), мы можем задаться вопросом, какова вероятность того, что в последующие 7 дней погода будет солнечносолнечно-дождь-дождь-солнечно-облачно-солнечно? Или более формально можно определить последовательность наблюдений как O = {S3, S3, S3, S1, S1, S3, S2, S3}, соответствующую временам t = 1, 2, Е, 8, и мы хотим найти вероятность O для заданной модели. Эта вероятность может быть записана и рассчитана как: P(O|Модель) = P[S3, S3, S3, S1, S1, S3, S2, S3| Модель] = = P[S3] * P[S3|S3] * P[S3|S3] * P[S1|S3] * P[S1|S1] * P[S3|S1] * P[S2|S3] * P[S3|S2] = = П3 * a33 * a33 * a31 * a11 * a13 * a32 * a23 = = 1 * (0.8)(0.8)(0.1)(0.4)(0.3)(0.1)(0.2) = 1.536*10 -4 Здесь мы использовали запись Пi = P[ q1 = Si ], 1 i N для определения вероятностей начальных состояний. Таким образом, имея модель процесса в виде матрицы вероятностей A = aij и матрицы вероятностей начальных состояний Пi, можно вычислить вероятность любой последовательности состояний, т.е. любого наблюдения. Такая модель и называется марковской моделью. Однако для систем распознавания речи подобная модель не дает точного описания и может применяться лишь со значительными ограничениями, поскольку реальные системы распознавания речи имеют структуру вложенных стохастических систем, которые и будут рассмотрены далее.
1.2 Скрытая марковская модель (СММ) Рассмотренный выше тип марковских моделей хорошо применим там, где состоя ния модели соответствуют реально наблюдаемым событиям, однако такие модели слишком ограничены, чтобы быть применимыми к большому числу интересных задач, в том числе и к распознаванию речи. На практике наиболее распространены так называемые скрытые марковские модели (СММ). Они описывают вложенные стохастические процессы, когда реально наблюдаются только события внешнего процесса, а события некоего скрытого процесса не наблюдаются непосредственно - они могут быть определены только из наблюдений внешнего процесса. В таких моделях наблюдаемые события являются вероятностными функциями от реального состояния системы. Рассмотрим абстрактный пример стохастического процесса и на его примере покажем, что представляют собой скрытые марковские модели. Пусть в комнате имеется N урн. В каждой из урн находится большое число шариков M различных цветов. Наблюдение производится следующим образом: некто выбирает начальную урну и случайным образом извлекает из нее шарик. Цвет шарика записывается как наблюдение и шарик возвращается в ту же урну. Затем выбирается новая урна, и процесс повторяется. Результатом наблюдения является последовательность цветов. В этом примере мы записывали только цвета извлекаемых шариков и не записывали номера урн, из которых они извлекались. Т.е. стохастический процесс выбора урны остался скрытым. При этом СММ можно описать следующим набором параметров: 1) N - число состояний модели. Несмотря на то, что внутренние состояния системы скрыты, для реальных приложений число состояний N выбирается, исходя из физических свойств моделируемого процесса. Будем обозначать конкретное значение состояния как S = {S1,S2,...SN}, и состояние системы в момент времени t как qt. 2) M - число различных, наблюдаемых в каждом состоянии символов (т.е. размер алфавита). Наблюдаемые символы соответствуют физическому выходу моделируемой системы (в нашем примере символом является цвет извлекаемого шарика). Далее условимся обозначать конкретные символы как V = {v1,v2,...,vM }. 3) A = {aij} - матрица вероятностей переходов, где aij = P[qt+1=Sj|qt=Si], 1i,jN Для специального случая, когда любое состояние может быть доступно из любого другого за один шаг (полносвязный граф как на рисунке 1.2), для всех aij выполняется условие aij > 0. Для других случаев aij может быть равной 0 для одной или нескольких пар i и j. 4) B = {bj(k)} - распределение вероятностей наблюдаемых символов в состоянии j, где b j(k) = P[vk|qt=Sj], 1jN,1kM (для непрерывного случая b j ( k ) задается как функция распределения плотности вероятности). 5) П ={Пi} - вероятность каждого начального состояния, где Пi = P[q1=Si],1iN. Таким образом, задав значения N,M,A,B и П для СММ, ее можно использовать как генератор последовательностей следующим образом: 1) Руководствуясь распределением вероятностей начальных состояний П, выбирается начальное состояние q1 = Si. 2) 3) Устанавливается t = 1. Руководствуясь распределением вероятностей символов в состоянии Si (т.е., bi(k)), выбирается Ot = vk. 4) Переходим в новое состояние qt+1 = Sj, руководствуясь матрицей вероятностей переходов для состояния Si, т.е. aij. 5) 6) Устанавливаем t = t + 1 и возвращаемся к шагу 3). Повторяем процедуру, пока не наберем последовательность нужной длины. Как видно из сказанного выше материала, для полного определения СММ необходимо задать два параметра наблюдаемых символов (M и N), и три вероятностных величины A, B и П. Для компактности условимся записывать последние как: =(A,B,П). (1.4) 1.3 Основные задачи
при применении СММ к распознаванию речи Для использования СММ при распознавании речи необходимо решить три задачи [83]. Задача 1: Если заданы последовательность наблюдений O = O1, O2,... OT и модель =(A,B,П), то как эффективно вычислить P(O|) - вероятность такой последовательности при заданных параметрах модели? Задача 2: Если заданы последовательность наблюдений O = O1, O2,... OT и модель =(A,B,П), то как определить соответствующую последовательность внутренних состояний Q = q 1, q2... q T? Задача 3: Как определить параметры модели =(A,B,П), исходя из критерия максимизации P(O|)? Очевидно, что решение первой задачи позволит эффективно распознавать элементы речи из некоторого ограниченного набора, имея готовые, уже обученные модели этих элементов. В этом случае произнесенное слово оцифровывается и после сегментации на определенные элементы, например, фреймы - участки фиксированной длины, рассматривается как набор последовательностей наблюдений. Вместо непосредственно оцифрованного речевого сигнала системы распознавания речи обычно работают с неким набором признаков (меньшим по объёму), достаточно хорошо характеризующим речевой сигнал (спектральные коэффициенты, кепстральные коэффициенты, коэффициенты линейного предсказания и другие). Этот этап называется предобработкой речевого сигнала. Затем каждая последовательность наблюдений, представляющая собой неизвестное слово, проверяется на соответствие всем имеющимся в словаре моделям слов. Для этого вычисляется вероятность генерации такой последовательности наблюдений каждой из имеющихся в словаре моделей. Слово, модель которого с наибольшей вероятностью генерирует такую последовательность наблюдений, и является результатом распознавания. Решение второй задачи позволяет выявлять скрытую часть модели, т.е. находить её внутренние состояния. В действительности определить ту последовательность состояний, которая имела место, невозможно, а в случае с распознаванием речи такой последовательности просто нет, поскольку считается, что модель речеобразования человека не носит стохастический характер. Тем не менее, нахождение оптимальной последовательности дает нам дополнительный критерий сравнения при поиске оптимальной модели и позволяет выявлять статистические характеристики конкретных состояний модели. Решение третей задачи позволяет обучать модели, т.е. вычислять параметры модели так, чтобы она наилучшим образом описывала так называемые тренировочные последовательности. Задача тренировки моделей считается самой сложной при использовании СММ в системах распознавания, так как неизвестно единственного и универсального способа её решения, а от результата обучения моделей зависит качество работы системы распознавания. Поэтому решению этой задачи уделяется особое внимание. Для примера рассмотрим простой распознаватель речи для изолированных слов на основе СММ (распознаватель речевых команд, рис. 1.3):
Рис. 1.3 Схема распознавателя команд на основе СММ Для каждого слова из словаря мы хотим создать собственную СММ из N состояний. Для этого представляем речевой сигнал полученного слова как временную последовательность кодированных спектральных векторов (если в качестве метода предобработки речевого сигнала выбраны спектральные коэффициенты), считая, что кодирование проводится с использованием спектральной кодовой книги объёмом в M уникальных спектральных векторов, и каждое наблюдение записывается индексом спектрального вектора, оказавшегося наиболее близким к исходному сигналу. Эта процедура называется векторным квантованием. [92] В результате для каждого слова из словаря мы имеем тренировочную последовательность (для одного или более дикторов), состоящую из индексов кодовой книги. Первым делом надо построить модели изолированных слов. Этому посвящено решение задачи №3 для оптимального оценивания параметров модели каждого слова. Для получения понимания физического значения состояний модели используется решение задачи №2. И, наконец, когда набор СММ создан, оптимизирован и исследован, распознавание неизвест ного слова производится, используя решение задачи №1 - по данной последовательности наблюдений оцениваются все модели из словаря системы и из них отбирается та, значение вероятности генерации которой данной последовательности наблюдений максимально (рис. 1.3), то есть максимально правдоподобная. При увеличении размера словаря, с которым работает система распознавания, задача оптимизации имеющихся моделей становится особенно актуальной, так как у большего количества моделей слов есть шанс сгенерировать близкие по значению вероятности, что отрицательно скажется на точности распознавания.
1.4 Типы СММ, применяемые в системах распознавания речи До сих пор мы рассматривали только специальный случай так называемой эргодической или полносвязной СММ, в которой каждое состояние модели за один шаг может быть достигнуто из любого другого состояния. (Строго говоря, эргодическая модель обладает таким свойством, что каждое состояние может быть достигнуто из любого другого состояния за конечное число шагов). Этот тип моделей имеет то свойство, что каждый коэффициент aij матрицы вероятностей переходов положителен. Такая модель была изображена на рис.1.2. Для некоторых же приложений, в особенности связанных с распознаванием речи, находят применение другие типы СММ, лучше описывающие наблюдаемые свойства моделируемого речевого сигнала, чем стандартная эргодическая модель. Одна из таких моделей называется моделью слева-направо (left-right model) или моделью Бэйкиса (Bakis model), поскольку последовательность состояний, лежащая в основе модели имеет то свойство, что с течением времени индекс состояния (его порядковый номер) также увеличивается (или остаётся тем же). То есть состояния на оси времени идут слева-направо. Очевидно, что такая модель имеет желаемое свойство: она легко моделирует сигналы, свойства которых изменяются со временем, например, речь. Ещё более частный случай СММ - частный случай моделей слева-направо - это модели с поступательно-ограниченными переходами. Особенность поступательноограниченных переходов в том, что они могут осуществляться не более чем на заданное число состояний вперёд (часто не более чем на два, как это указано на рис.1.4).
Рис. 1.4. Модель слева-направо Основное свойство моделей слева-направо в том, что коэффициенты переходов удовлетворяют условию: Aij = 0, j < i (1.5) То есть, переходы в состояния с индексом меньше, чем у текущего состояния, недопустимы. Кроме того, вероятности начальных состояний имеют свойство: 0, i 1 Пi = 1, i = 1 ся в состоянии N). Хотя мы и особо выделили эргодические модели и модели слева-направо, существует множество других типов СММ, например модель с параллельными путями (рис.1.5). Строго говоря, это тоже модель слева-направо, поскольку она удовлетворяет тем же условиям, но у неё есть и особенность в виде наличия двух параллельных путей. По сути, это объединение двух моделей с поступательно-ограниченными переходами. (1.6) Иначе говоря, последовательность должна начинаться с состояния 1 (и оканчивать Рис. 1.5. Модель с параллельными путями Применительно к речи это означает, что такая СММ моделирует возможную вариативность речевого сигнала, которая может иметь место в случае работы, например, с диктором, находящимся в условиях стресса, из-за чего изменяются особенности произнесения им фонем, или при работе с несколькими дикторами, различающимися особенностями произнесения тренировочного слова, потому что в этом случае в модели есть несколько альтернативных путей для той части слова, которая произносится по-разному различными людьми или одним человеком от случая к случаю. Такая модель учитывает вышеперечисленные особенности произнесения и придаёт дополнительную гибкость использующим её приложениям. Выше мы рассматривали только случаи моделей, когда наблюдения характеризуются дискретными символами из конечного алфавита и потому могли использовать дискретную плотность вероятности для каждого состояния модели. Однако в реальности (по крайней мере, для некоторых приложений) наблюдения являются непрерывными сигналами (или векторами). В этом случае необходимо использовать СММ с непрерывными плотностями вероятностей. Такие СММ используются при работе в системах распознавания, использующих спектральные коэффициенты или кепстральную предобработку речевого сигнала. Общая формулировка СММ с непрерывными плотностями вероятностей применима к широкому классу задач, но существует ещё один очень интересный класс СММ, дающий хорошие результаты именно применительно к системам распознавания речи. Речь идёт об авторегрессионных СММ. Для данного типа СММ вектора наблюдений получаются из авторегрессионного процесса. То есть компоненты вектора наблюдений имеют вид: Ok = a i O k i + e k, i =1 p (1.7) где ek (k=0,1,2,Е,K-1) - гауссовская независимая равномерно распределённая случайная величина с нулевым матожиданием и дисперсией 2, а a i (i=1,2, Е, p) - коэффициенты авторегрессии или предсказания. Поскольку традиционные СММ плохо моделируют продолжительность состояния (для этого приходится последовательно включать в модель несколько одинаковых состояний или повышать вероятность перехода системы из данного состояния в само себя), то в них приходится явно вводить плотность продолжительности состояния и запрещать переходы модели из любого состояния в само себя. Такая СММ носит название СММ с длительностью состояний. На практике в системах распознавания речи это может быть полезно для того, чтобы учесть разницу в длительности произнесения различных фонем (например, в русском языке такие взрывные звуки как [п], [б] имеют значительно меньшую длительность, чем тоновые [а] или [о]). Также существуют СММ, в которых наблюдения являются дугами графа, а не узлами модели, как было во всех ранее рассмотренных случаях. Такой тип моделей активно использовался в распознавателе непрерывной речи, который разрабатывала компания IBM [83]. Для этого типа моделей оказалось полезным разрешить переходы модели, не произ водящие выходного значения (т.н. нулевой переход - переход из одного состояния в другое, не генерирующий наблюдения). Такой метод даёт простой и эффективный способ для описания особенностей произнесения и дефектов речи, выражающихся в пропуске отдельных звуков.
1.5 Подходы к решению основных задач СММ 1.5.1 Задача 1. Эффективное вычисление вероятности генерации заданной последовательности Как уже указывалось эта задача связана с необходимостью вычислить вероятность последовательности наблюдений O = O1, O2,... OT при заданных параметрах модели, т.е., P(O|). Самый прямой метод вычисления этой вероятности состоит в вычислении суммы вероятностей всех возможных последовательностей состояний. Рассмотрим одну из таких возможных последовательностей: Q = q 1 q2 q3... q T. Вероятность последовательности наблюдений O при заданной последовательности состояний вычисляется как P ( O| Q, ) = P ( O t | q t, ) ;
t =1 T (1.8) или P(O|Q, ) = bq 1 (O1 ) b q 2 (O2 ) b q T (OT ).
(1.9) Вероятность такой последовательности состояний может быть записана как P (Q | ) = П q1 a q1q 2 a q 2 q 3 a qT 1qT.
вероятностей:
(1.10) Совместная вероятность O и Q, вычисляется как произведение приведенных выше P (O, Q | ) = P ( O | Q, ) P ( Q, ) по всем возможным последовательностям состояний q (1.11) Вероятность O, таким образом, вычисляется как сумма совместных вероятностей P (O | ) = P (O | Q, ) P (Q | ) = allQ q1, q 2,, qT П q1 q b (O1 )aq1q2 bq2 (O2 ) aqT 1qT bqT (QT ) (1.12) Нетрудно подсчитать, что количество операций умножения, необходимых для вычисления этой суммы, равняется 2TNT. Т.е., если модель имеет пять состояний (N=5) и последовательность наблюдений имеет длину сто (T=100), то количество арифметических операций равно 2*100*5 1001072.
Однако существует более эффективный метод вычисления вероятности O. Он называется процедурой Forward-Backward и состоит в следующем: Вводится переменная t(i), определяемая как t (i ) = P (O 1O 2 O t, q t = S i | ).
(1.12) Назовем ее прямой переменной, которая представляет собой вероятность появления для данной модели частичной последовательности наблюдений, O1 O2... Ot, (до момента времени t и состояния Si) при заданных параметрах модели. Можно индуктивно определить эту прямую переменную как 1) инициализация:
1 (i ) = П i b i (O1 ), 1 i N ;
(1.13) 2) индукция:
N j) = t+1 ( i= t (i )a ij b j ( O t + 1 ), 1 t T 1, ;
1 j N (1.14) 3) завершение:
P( O| ) = T ( i).
i =1 N (1.15) При этом шаг 1) инициализирует прямые переменные совместными вероятностями состояний Si и начальных наблюдений O1. Индуктивный шаг 2) является сердцем процедуры, он проиллюстрирован на рис. 1. S1 S2 S a1j a2j a3j Sj ST t t(i) aNj t+1 t+1(i) Рис. 1.6. Индуктивный шаг процедуры Forward-Backward Рисунок показывает, как состояние Sj может быть достигнуто в момент времени t+1 из N возможных состояний Si, 1iN, в которых система могла находиться в момент времени t. Поскольку t(i) - это совместная вероятность того, что наблюдалась последовательность O1,O2,...Ot и в момент времени t система находилась в состоянии Si, то произведение t(i)aij - это совместная вероятность того, что наблюдалась последовательность O1,O2,...Ot и в момент времени t+1 система находится в состоянии Sj, в которое перешла из состояния Si, в котором находилась в момент времени t. Суммируя эти произведения по всем N возможным состояниям Si, 1iN, в которых система могла находиться в момент времени t, получим вероятность перехода системы в момент времени t+1 в состояние Sj с учетом всех возможных предшествующих этому частичных последовательностей наблюдений. Теперь, умножив эту сумму на вероятность bj(Ot+1), продвигаемся на один шаг, получив t+1(j). На заключительном шаге 3) вычисляется искомая вероятность P(O|) как сумма по i окончательных значений прямых переменных T(i), при этом T ( i ) = P (O 1O 2 O T, q T = S i | ) (1.16) Для вычисления вероятности P(O|) таким образом, требуется уже порядка N2T вычислительных операций, вместо 2TNT для прямого метода, так что данный метод значительно более быстрый. В нашем примере для N=5 и T=100 он требует всего около 3000 арифметических операций, вместо 1072 операций для прямого вычисления. Теперь введем лобратную переменную t(i) и определим ее как t ( i ) = P (O t+ O t+ O T,q t = S i| ), (1.17) т.е. t(i) - это вероятность частичной последовательности наблюдений от момента времени t до конца последовательности при заданном состоянии Si в момент времени t и параметрах модели. t(i) мы точно также можем индуктивно вычислить посредством следующей процедуры: 1) Инициализация T (i ) = 1, 1i N (1.18) 2) Индукция T (i) = N j= a ij b j (O ) ( j), t+1 t+ (1.19) t = T 1, T 2,,1,1 i N Очевидно, что для решения первой задачи СММ достаточно вычисления только прямой переменной, но как мы увидим дальше, лобратная переменная используется наравне с прямой при решении других задач СММ.
1.5.2 Задача 2. Отыскание оптимальной последовательности состояний В отличие от первой задачи, где мы можем получить точное решение, вторая задача имеет несколько возможных решений. Поскольку нам надо найти оптимальную последовательность состояний, исходя из имеющейся последовательности наблюдений, конкретное решение во многом будет зависеть от выбранных критериев оптимальности. Одним из таких критериев может быть выбор состояний qt, которые наиболее вероятны в конкретные моменты времени t. Для нахождения решения в соответствии с этим критерием оптимальности определим переменную t (i ) = P (q t = S i | O, ), (1.20) т.е. вероятность нахождения в состоянии Si в момент времени t при заданных параметрах модели и последовательности наблюдений O. Эту вероятность легко выразить в терминах прямой и обратной переменных, т.е.
t (i) = t ( i ) t ( i ) = P (O | ) t ( i ) t ( i ) N (1.21) i= t ( i ) t ( i ) Здесь P(O|) - нормализирующий фактор для того, чтобы ( i) = i =1 t N (1.22) Используя переменную t(i), можно легко найти наиболее вероятные конкретные состояния qt для моментов времени t как q t = arg max t ( i), 1i N [ ] (1.23) 1 t T Поскольку приведенный выше метод находит только наиболее вероятные состояния для каждого из моментов времени, для случаев, где матрица переходов aij имеет нулевые значения, такая последовательность может оказаться некорректной. Поэтому правильно в выборе оптимальной последовательности использовать и матрицу вероятностей переходов. Одним из таких методов является алгоритм Витерби [23, 93].
1.5.3 Задача 3. Обучение СММ тестовыми последовательностями Как уже отмечалось, третья задача является самой трудной при работе с СММ: она должна дать метод нахождения параметров модели, таких, чтобы максимизировать вероятность последовательностей наблюдений, соответствующих данной модели. На самом деле не известно ни одного аналитического метода решения этой задачи. То есть для любого конечного числа тренировочных последовательностей нет оптимального пути оценки параметров модели. Однако можно выбрать =(A,B,П) так, чтобы P(O|) имел локальный максимум, используя итеративную процедуру Баума-Велча (Baum-Welch) (или эквивалентный ему EM (expectation-modification)-метод), или градиентные методы [48, 49, 83]. Рассмотрим одну из итеративных процедур выбор параметров модели, основанную преимущественно на классической работе Баума и его коллег [48, 49]. Для описания процедуры итеративного уточнения параметров СММ нам потребуется определить вероятность нахождения системы в состоянии Si в момент времени t и в состоянии Sj в момент времени t+1 при заданных параметрах модели и последовательности наблюдений, т.е.
t (i, j ) = P (q t = S i, q t +1 = S j | O, ).
t (i )aij b j (Ot +1 ) t +1 ( j ) P(O | ) t (i )aij b j (Ot +1 ) t +1 ( j ) (1.24) В терминах прямой и обратной переменных эту вероятность можно записать так t (i, j ) = = t (i)aijb j (Ot +1 ) t +1 ( j ) i =1 j = N N, (1.25) где числитель - это просто P(qt=Si,qt+1=Sj,O|), а деление его на P(O|)дает искомую вероятность. Ранее мы определяли t(i) как вероятность нахождения системы в состоянии Si в момент времени t, теперь мы можем выразить t(i) через t(i,j) суммированием по j t (i ) = t (i, j ).
j = N (1.26) Если мы просуммируем t(i) по времени, то получим результат, который может быть интерпретирован как ожидаемое количество раз, которое система окажется в состоянии Si или ожидаемое количество переходов из этого состояния (если исключить из рассмотрения момент времени T). Так же сумма t(i,j) по времени (от t=1 до t=T-1) может быть интерпретирована как ожидаемое число переходов из состояния Si в Sj.
(i ) = ожидаемое число переходов из состояния S ;
t =1 t i T (1.27) (i, j ) = t t = T ожидаемое число переходов из состояния Si в Sj. (1.28) Используя приведенные выше формулы, мы можем получить набор формул для уточнения параметров СММ:
i = ожидаемая частота нахождения в состоянии Si в момент времени (t=1) = 1 (i ) ;
(1.29) a ij = ожидаемое число переходов из состояния S i в состояние S j ожидаемое число переходов из состояния S i T = = (i, j ) t =1 T 1 t =1 t (i ) t ;
(1.30) ожидаемая частота нахождения в состоянии S j b j (k ) = и наблюдения символа vk = ожидаемая частота нахождения в состоянии S j = t =1 Ot = v k T t = ( j) t T t ( j).
(1.31) Если мы имеем текущее параметры модели =(A,B,П) и посредством этих формул получили уточненные параметры модели =(A,B,П), то, как утверждает Баум и его коллеги, либо мы получим, что P(O|)=P(O|), либо что P(O|)>P(O|), т.е. мы нашли новые параметры модели, при которых она с наибольшей вероятностью будет производить данную последовательность наблюдений. Следует сразу отметить, что при этом на каждой итерации автоматически удовлетворяются следующие требования i = N N i = = 1, (1.32) a j = ij (1.33) 1i N b (k ) = 1, j k = M (1.34) 1 j N Так, рассмотренный метод производит итеративное улучшение параметров модели, но он не способен выйти из локального экстремума функции P(O|), что является довольно серьёзным ограничением, и кроме того его работа сильно зависит от начальных условий - так называемых стартовых параметров СММ - и в случае неудачного их выбора (рядом с локальным экстремумом) этот метод будет неэффективным. В данном случае мы имеем одну из задач оптимизации, для которой применимы различные методы решения.
1.6 Выводы В данной главе диссертации рассматривается теория скрытого марковского моделирования (СММ) и её применение к приложениям распознавания речи. Рассмотрены основные типы СММ, используемые в системах распознавания речи, классифицированы основные задачи теории и определены подходы к их решению. Показано, что решение каждой из перечисленных задач в лоб может быть очень ресурсоёмким, и потому существуют оптимизированные для этих целей алгоритмы, например, Forward-Backward для решения первой задачи или алгоритм Витерби для решения второй. Кроме того, важная и наиболее сложная среди трёх задача обучения скрытой марковской модели тренировочными последовательностями не имеет аналитического решения, и потому к её решению могут быть применены различные методы, например, итеративная процедура Баума-Велча (Baum-Welch) или эквивалентный ей EM-метод, которые не свободны от собственных недостатков и ограничений, важнейшие из которых - это неспособность выйти из локального экстремума и сильная зависимость от стартовых значений модели. В то же время от качественного обучения модели, то есть нахождения таких её параметров, которые описывают тренировочное слово как можно лучше, напрямую зависит эффективность работы системы распознавания речевых команд. Интерес представляет поиск альтернативных способов решения этой задачи, которые могли бы преодолеть указанные ограничения.
Глава 2. Сравнительная оценка методов оптимизации в задаче обучения СММ Как было показано в предыдущей главе диссертационной работы, наиболее трудной и актуальной задачей является задача оптимизации процесса обучения СММ в системах автоматического распознавания речи, однозначного решения которой не известно. В данной главе диссертации рассматриваются различные методы оптимизации, применимые к решению данной задачи, оцениваются их возможности и ограничения и показывается принципиальная возможность использования в этих целях генетических алгоритмов, представляющих собой перспективное и динамично развивающееся направление интеллектуальной обработки данных, связанное с решением задач поиска и оптимизации. Далее будут подробно описаны принципы их функционирования и исследована применимость к задаче обучения СММ. Область применения генетических алгоритмов достаточно обширна. Они успешно используются для решения ряда больших и экономически значимых задач в бизнесе и инженерных разработках. С их помощью были разработаны промышленные проектные решения, позволившие сэкономить многомиллионные суммы. Наряду с другими методами эволюционных вычислений генетические алгоритмы обычно используются для оценки значений непрерывных параметров моделей большой размерности, для решения комбинаторных задач, для оптимизации моделей, включающих одновременно непрерывные и дискретные параметры. Другая область применения - использование в системах извлечения новых знаний из больших баз данных, создание и обучение стохастических сетей, обучение нейронных сетей, оценка параметров в задачах многомерного статистического анализа, получение исходных данных для работы других алгоритмов поиска и оптимизации [1].
2.1 Схема процесса принятия решения как задачи поиска Рассмотрим общую схему процесса принятия решения в многокритериальных задачах. Принятие решения при этом обычно заключается в выборе лучшей из возможных альтернатив решений, при которой с учётом разнообразных и порой противоречивых требований будет оптимизирована некая общая ценность. Иными словами, решение в максимальной степени будет способствовать достижению поставленной цели. Для формализации поставленной задачи требуется описание всех факторов, оказы вающих влияние на достижение цели, ограничительных условий, а также критерий оценки качества принимаемого решения, который даст возможность осуществлять выбор между рассматриваемыми альтернативами. Обычно таким критерием является некая целевая функция, зависящая от указанных факторов, выступающих её аргументами, а решению, приводящему к наилучшему результату, соответствует экстремум этой целевой функции, то есть точка её минимума или максимума. Все возможные комбинации аргументов образуют пространство поиска задачи, а его размерность определяется количеством аргументов целевой функции. Каждая из указанных комбинаций представляется точкой в этом пространстве. Процесс принятия решения в данном случае схематично изображён на рис. 2.1:
Рис. 2.1 Формальное представление процесса принятия решений Указанная интерпретация процесса принятия решений (Рис. 2.1), несмотря на свою обобщенность и приблизительность, позволяет увидеть потенциальные возможности автоматизации, то есть применения вычислительной техники для выполнения задач принятия решений. Наиболее широко вычислительная техника используется сейчас для реализации самого трудоемкого процесса - генерации альтернатив решений и выбора наилучшей из них.
2.2 Традиционные методы поиска оптимальных решений и их приложение к задаче обучения СММ Еще задолго до появления вычислительной техники были созданы формальные методы поиска оптимальных решений, в основе которых лежали математические вычисления, позволяющие находить экстремум целевой функции. На сегодняшний день можно выделить три основных типа методов поиска оптимальных решений [19]: з з з методы, основанные на математических вычислениях, перечислительные методы, методы, использующие элемент случайности.
Рассмотрим их более подробно.
2.2.1 Методы, основанные на математических вычислениях Методы, основанные на математических вычислениях, сегодня изучены наиболее полно. Они подразделяются на направленные и ненаправленные. Суть ненаправленного метода состоит в том, что локальный экстремум ищется путем решения системы уравнений, как правило, нелинейных. Эта система составляется путем приравнивания градиента целевой функции к нулю (например, метод градиентного спуска или покоординатного спуска). К недостаткам этих методов можно отнести очень жесткие условия, накладываемые на целевую функцию: она должна быть дифференцируема на всем пространстве поиска. При формализации современных задач это условие, как правило, соблюсти не удается, и аналитического решения задачи обучения СММ не известно. Направленные методы предполагают перемещения от точки к точке в допустимой области, причем направление подобных перемещений связывается с направлением, на которое указывает градиент (например, метод касательных). Итеративная процедура Баума-Велча, предназначенная для решения задачи обучения СММ и рассмотренная в Главе 1, относится именно к этой группе методов оптимизации. Как было отмечено, эта процедура способна находить только лишь локальные экстремумы или глобальный, но только если на пути к нему по ландшафту параметров не окажется локальных экстремумов, выбраться из которых она не сможет.
Данная особенность распространяется и на всю группу этих методов - они часто находят лишь локальные экстремумы целевой функции, тогда как оптимальному решению соответствует только глобальный экстремум. Таким образом, методы поиска оптимальных решений, основанные на математических вычислениях, применимы лишь в случаях гладких, всюду дифференцируемых унимодальных (имеющих один экстремум на пространстве поиска) целевых функций.
2.2.2 Перечислительные методы Перечислительные методы, по сути, представляют собой полный перебор. Их смысл состоит в том, что пространство поиска любой задачи можно представить в виде совокупности дискретных точек, и этом случае поиск решения будет сводиться к перебору всех точек пространства поиска и вычислению в них целевой функции, в одной из которых она, несомненно, примет экстремальное значение. Даже если пространство поиска непрерывно, то конечная точность представления чисел в вычислительных машинах позволяет сделать такое допущение. Для наглядности этот метод можно сравнить с накладыванием на пространство поиска (в случае, если оно непрерывно) сети с выбранным фиксированным размером ячеек и дальнейшим прохождением по всем узлам этой сети. Недостаток этих методов очевиден. При увеличении размерности пространства поиска (числа аргументов целевой функции) количество точек пространства возрастает не линейно, а значительно стремительнее. Данная проблема известна под названием комбинаторного взрыва. Это приводит к значительным временным затратам процедуры перебора и необходимости применения все более мощной и дорогостоящей вычислительной техники. В то же время размерность решаемых сейчас задач постоянно растет, а время, доступное для принятия решений, сокращается. Таким образом, перечислительные методы также становятся применимы для решения все более сужающегося класса задач. Так, например, для поиска оптимальной матрицы для СММ, имеющей 10 состояний, пришлось бы перебрать 10*10=100 элементов матрицы, каждый из которых может принимать значения в диапазоне от 0 до 1, с шагом равным 0,00000001 = 10-8, то есть, каждый элемент может принимать 108 значений. Такое допущение относительно шага сделано ввиду того, что значения параметров СММ в системе автоматического распознавания речи (САРР) SdiApp, разработанной на кафедре ЭВА МИЭМ, хранятся в файле словаря с точностью до восьмого знака. Для строки из этих 100 элементов число возможных комбинаций оказывается равным (10 8)100=10 800 (!). Для сравнения, считается, что в нашей Вселенной есть место для 10118 субатомных частиц [91]. Даже если крайне упростить задачу перебора и рассматривать исключительно СММ с поступательно-ограниченными переходами не более чем на 2 состояния вперёд (т.н. ленточные матрицы), то и тогда останется 3*10-31=26 нуждающихся в переборе элементов (вычитание в формуле появилось из-за того, что последняя строка матрицы содержит только один элемент, да и тот единичный, а предпоследняя - два значащих элемента, вместо стандартных трёх). Для этого случая число возможных комбинаций оказывается равным 10 8*26=10208, что тоже явно превышает все разумные значения. Если в дополнение ещё и радикально пожертвовать точностью представления данных и снизить её до второго знака (практическая польза подобной модели становится крайне сомнительна, так как при перемножении закодированных таким образом элементов очень сильно пострадает точность результата, что отрицательно скажется на качестве распознавания), число комбинаций станет равным 10 2*26=1052. Если, наконец, допустить, что в нашем распоряжении есть суперкомпьютер СКИФ-1000 мощностью 2 терафлопс (на конец 2004 года - это самый быстрый суперкомпьютер на территории бывшего СССР и 98-й по мощности суперкомпьютер в мировом рейтинге Top500 [3]), то есть способный выполнять 2*10 12 операций с плавающей точкой в секунду, и предположить, что за одну его операцию обрабатывается одна комбинация параметров или одна матрица (что, вообще говоря, далеко не так, потому что на матрицу потребуется гораздо больше операций), то на обработку всех 1052 значений матриц потребуется 1052/2*1012 = 5*1039 секунд, что на 22 порядка больше времени существования Вселенной, равного приблизительно 5*1017 секунд или 14 миллиардов лет. В свете этих последних значений первоначальный вариант даже не поддаётся осмыслению, и сколь-нибудь полный перебор попросту невозможен. Следует заметить, что не все матрицы, генерируемые рассматриваемой процедурой, являются допустимыми в силу невыполнения ими для отдельных строк условия полной вероятности (ф-ла 1.3), и такие матрицы должны быть отброшены. Здесь возможна оптимизация работы переборного алгоритма посредством реализации процедуры, генерирующей только допустимые с точки зрения СММ матрицы, что сократит объём вариантов для перебора алгоритмом, но этот подход не избавит от другой проблемы метода перебора - экспоненциального роста числа вариантов при увеличении размерности модели. Также важно заметить, что при использовании перечислительных методов важным является вопрос выбора шага дискретизации или квантования модели, чтобы точка экстремума не оказалась пропущенной в результате того, что она находится между двумя соседними точками модели. Важно обратить внимание и на то, чтобы за один шаг дискретизации значение не могло значительно изменяться внутри этого шага, иначе весь трудоёмкий перебор может оказаться бессмысленным - золотую рыбку нельзя поймать сетью для акул.
2.2.3 Методы, использующие элементы случайности Методы, использующие элементы случайности, стали появляться относительно недавно, по мере того, как становились очевидными недостатки методов, рассмотренных выше. В основе первого из случайных методов лежит случайный поиск в пространстве задачи с сохранением наилучшего полученного результата. Очевидно, что применение такого метода не гарантирует получения оптимального решения, так как точка глобального экстремума может не оказаться выбранной процедурой случайного поиска среди множества всех возможных точек - вероятность этого далеко не нулевая и увеличивается с ростом числа точек пространства поиска. Кроме того, при одинаковой дискретизации моделей результат работы такого метода не может быть лучше, чем в случае работы перечислительных методов поиска, поскольку в обоих случаях рассматриваются одни и те же дискретные точки пространства поиска задачи. Вместе с тем, следует заметить, что сейчас при решении очень сложных задач основной целью является поиск уже не оптимального, а более хорошего решения по сравнению с полученным ранее или заданным в качестве начального. Здесь методы, использующие элемент случайности, получают определенное преимущество перед остальными. Однако даже с такими допущениями непосредственный случайный поиск является малоэффективным. Исследования показали [19;
а также автор в разделе 4.1.2], что внесение в такие методы элементов детерминированности дает значительное улучшение показателей. Одним из типов таких частично случайных методов являются эволюционные вычисления.
2.3 Концепция эволюционных вычислений История эволюционных вычислений характеризуется развитием ряда независимых моделей. Первыми моделями были генетические алгоритмы и классификационные системы. Эволюционные вычисления - это бионическое направление, которое использует принципы эволюции, перенятые из природы, но упрощённые до такой степени, чтобы их можно было реализовать в компьютерных моделях. Среди многочисленных эволюционных моделей выделяют собственно бионические, то есть основанные на биологических принципах, и модели, далёкие от реальной эволюции, но полезные в прикладном смысле [44]. В основном используются системы второго типа, которые успешно решают задачи структурной оптимизации. Системы же первого типа обладают сложным поведением, что не исключает их практического применения в будущем. К моделям биологической эволюции относятся системы, известные под обобщающим термином искусственная жизнь (Artificial Life) [96]. Представителями прикладных моделей являются эволюционные алгоритмы, такие как: 1. эволюционное программирование (Evolutionary Programming), в основе которого лежит идея представления альтернатив в виде универсальных конечных автоматов, способных реагировать на стимулы, поступающие из окружающей среды. Идеи эволюционного программирования были предложены в 1966 году Фогелем, Оуэнсом и Уолшем (L.J. Fogel, A.J. Owens, M.J. Walsh) в работе Построение систем искусственного интеллекта путем моделирования эволюции [64];
2. генетические алгоритмы (Genetic Algorithms), основной особенностью которых является представление любой альтернативы решения в виде строки параметров, например, битовой строки фиксированной длины, манипуляции с которой производятся в отсутствие всякой связи с ее смысловой интерпретацией. То есть применяется единое универсальное представление любой задачи. Парадигму генетических алгоритмов предложил Джон Холланд, опубликовавший в начале 60-х годов ее основные положения. А всеобщее признание она получила после выхода в свет в 1975 году его классического труда Адаптация в естественных и искусственных системах [72];
3. эволюционные стратегии (Evolution Strategies), напротив, оперируют объектами, тесно связанными с решаемой задачей. Каждая из альтернатив решения представляется единым массивом численных параметров, за каждым из которых скрывается, по сути, аргумент целевой функции. Воздействие на данные массивы осуществляется, в отличие от генетических алгоритмов, с учетом их смыслового содержания и направлено на улучшение значений входящих в них параметров. Парадигму эволюционных стратегий предложили в году Реченберг (I.Rechenberg) в своей работе Эволюционные стратегии: оптимизация технических систем на основе принципов биологической эволюции [84] и в 1977 году Шефель (Н.Р.Schwefel) в работе Численная оптимизация компьютерных моделей посредством эволюционной стратегии [87]. Эволюционные вычисления - термин, обычно используемый для общего описания алгоритмов поиска, оптимизации или обучения, основанных на некоторых формализованных принципах естественного эволюционного процесса [1]. Основное преимущество эволюционных вычислений в этой области заключается в возможности решения многомодальных (имеющих несколько локальных экстремумов) задач с большой размерностью за счет сочетания элементов случайности и детерминированности точно так, как это происходит в природной среде. Детерминированность этих методов заключается в моделировании природных процессов отбора, размножения и наследования, происходящих по строго определенным правилам. Основным правилом при этом является закон эволюции: выживает наиболее приспособленный, который обеспечивает улучшение находимого решения. Другим важным фактором эффективности эволюционных вычислений является моделирование размножения и наследования. Рассматриваемые варианты решений могут по определенному правилу порождать новые решения, которые будут наследовать лучшие черты своих предков. В качестве случайного элемента в методах эволюционных вычислений может использоваться, например, моделирование процесса мутации. В этом случае характеристики того или иного решения могут быть случайно изменены, что приведет к новому направлению в процессе эволюции решений и может ускорить процесс выработки лучшего решения. В настоящее время наблюдается взаимное проникновение указанных парадигм и их сращивание в единую концепцию эволюционных вычислений. Как и всякий метод, использующий элемент случайности, эволюционные вычисления не гарантируют обнаружения глобального экстремума целевой функции (или оптимального решения) за определенное время. Основное их преимущество в том, что они позволяют найти более хорошие решения очень трудных задач за меньшее время, чем другие методы. К числу подобных задач может быть отнесена и задача обучения СММ. Естественно, эволюционные вычисления не являются оптимальным средством для решения любых задач, поскольку было доказано, не существует метода поиска, который был бы наилучшим во всех случаях [19]. Тем не менее, методы эволюционных вычислений оказались достаточно эффективными для решения ряда реальных задач инженерного проектирования, планирования расписаний, маршрутизации в сетях и размещения объектов в ограниченном пространстве, управления портфелями ценных бумаг, прогнозирования, а также во многих других областях. Отрицательной чертой эволюционных вычислений является то, что они представляют собой скорее подход к решению задач оптимизации, чем алгоритм, и вследствие этого требуют адаптации к каждому конкретному классу задач путем выбора определенных характеристик и параметров.
2.4 Основы теории генетических алгоритмов (ГА) Являясь разновидностью методов поиска с элементами случайности, генетические алгоритмы имеют целью нахождение лучшего по сравнению с имеющимся, а не оптимального решения задачи. Это связано с тем, что для сложной системы часто требуется найти хоть какое-нибудь удовлетворительное решение, а проблема достижения оптимума отходит на второй план. Аналогичная ситуация наблюдается и с обучением СММ - достаточно найти хорошо описывающую конкретную тестовую последовательность модель, не обязательно идеальную. При этом другие методы, ориентированные на поиск именно оптимального решения, вследствие чрезвычайной сложности задачи становятся вообще неприменимыми. В этом кроется причина появления, развития и роста популярности генетических алгоритмов. Хотя, как и всякий другой метод поиска, этот подход не является оптимальным методом решения любых задач. Дополнительным свойством этих алгоритмов является невмешательство человека в развивающийся процесс поиска - он может влиять на него лишь опосредованно, задавая определенные параметры. Прежде чем рассматривать непосредственно работу генетического алгоритма, введем ряд терминов, которые широко используются в данной области. Выше было сказано, что генетический алгоритм работает с кодами безотносительно их смысловой интерпретации. Поэтому сам код и его структура описываются понятием генотип, а его интерпретация с точки зрения решаемой задачи - понятием фенотип. Каждый код представляет, по сути, точку пространства поиска. С целью максимально приблизиться к биологическим терминам, экземпляр кода называют хромосомой, особью или индивидуумом. Далее для обозначения строки кода в основном будет использоваться термин лособь. На каждом шаге работы генетический алгоритм использует несколько точек поиска одновременно. Совокупность этих точек является набором особей, который называется популяцией. Количество особей в популяции называют размером популяции. В классических генетических алгоритмах размер популяции является фиксированным и представляет одну из характеристик генетического алгоритма. На каждом шаге своей работы генетический алгоритм обновляет популяцию путем создания новых особей и уничтожения ненужных. Чтобы отличать популяции на каждом из шагов и сами эти шаги, их называют поколениями и обычно идентифицируют по номеру. Например, популяция, полученная из исходной популяции после первого шага работы алгоритма, будет первым поколением, после следующего шага - вторым и т.д. В процессе работы алгоритма генерация новых особей происходит на основе моделирования процесса размножения. При этом, естественно, порождающие особи называются родителями, а порожденные - потомками. Родительская пара, как правило, порождает пару потомков. Непосредственная генерация новых кодовых строк из двух выбранных происходит за счет работы оператора скрещивания, который также называют кроссинговером или кроссовером (от англ. crossover). При порождении новой популяции оператор скрещивания может применяться не ко всем парам родителей. Часть этих пар может переходить в популяцию следующего поколения непосредственно. Насколько часто будет возникать такая ситуация, зависит от значения вероятности применения оператора скрещивания, которая является одним из параметров генетического алгоритма. Моделирование процесса мутации новых особей осуществляется за счет работы оператора мутации. Основным параметром оператора мутации также является вероятность мутации. Поскольку размер популяции фиксирован, порождение потомков должно сопровождаться уничтожением других особей. Выбор пар родителей из популяции для порождения потомков производит оператор отбора, а выбор особей для уничтожения - оператор редукции. Основным параметром их работы является, как правило, качество особи, которое определяется значением целевой функции в точке пространства поиска, описываемой этой особью. Таким образом, можно перечислить основные понятия и термины, используемые в области генетических алгоритмов: з з з генотип и фенотип;
особь и качество особи;
популяция и размер популяции;
з з з з з з з з операторами.
поколение;
родители и потомки. размер популяции;
оператор скрещивания и вероятность его использования;
оператор мутации и вероятность мутации;
оператор отбора;
оператор редукции;
критерий останова.
К характеристикам генетического алгоритма относятся:
Операторы отбора, скрещивания, мутации и редукции называют еще генетическими Критерий останова определяет, когда работа генетического алгоритма должна быть закончена. Обычно это происходит по достижении популяцией заданного пользователем качества (например, значение качества всех особей превысило заданный порог), по достижении определённого уровня сходимости (то есть особи в популяции стали настолько подобными, что дальнейшее их улучшение происходит чрезвычайно медленно) или же когда сформировано заданное пользователем число поколений. Характеристики генетического алгоритма выбираются таким образом, чтобы обеспечить малое время работы, с одной стороны, и поиск как можно лучшего решения, с другой.
2.5 Последовательность работы генетического алгоритма Рассмотрим теперь непосредственно работу генетического алгоритма. Общая схема его работы представлена на Рис. 2.2.
Создание исходной популяции Выбор родителей для процесса размножения (работает оператор отбора) Создание потомков выбранных пар родителей (работает оператор скрещивания) Мутация новых особей (работает оператор мутации) Расширение популяции за счёт добавления новых, только что порождённых особей Сокращение расширенной популяции до исходного размера (работает оператор редукции) Нет Критерий останова работы алгоритма выполнен?
Да Поиск лучшей достигнутой особи в конечной популяции результата работы алгоритма Рис. 2.2 Процесс работы генетического алгоритма Первый шаг при построении генетических алгоритмов Ч это кодировка вектора исходных параметров, которые именуют хромосомами, а весь их набор называют популяцией хромосом. Хромосома может быть закодирована как битовой строкой, так и символьной, или же строкой вещественных чисел. Реализация генетического алгоритма предполагает задание т.н. функции приспособленности или фитнес-функции (fitness function). Данная функция предназначена для оценки качества каждого конкретного решения - она получает на вход хромосому и возвращает число, показывающее, насколько хороша эта хромосома. Формирование исходной популяции происходит, как правило, с использованием какого-либо случайного закона, на основе которого выбирается нужное количество точек поискового пространства. Исходная популяция может также быть результатом работы какого-либо другого алгоритма оптимизации. Все здесь зависит от разработчика конкретного генетического алгоритма. Применительно к системам распознавания речи на основе СММ это означает, что в первом случае будут сгенерированы произвольные случайные матрицы СММ, а во втором они будут получены после работы какого-либо иного алгоритма (например, Баума-Велча) и ГА будет пытаться их улучшить. Существуют различные варианты реализации генетических алгоритмов, как с постоянным размером популяции, так и с переменным. Вообще, генетические алгоритмы допускают большую вариативность в реализации. В основе оператора отбора, который служит для выбора родительских пар и уничтожения особей, лежит принцип выживает наиболее приспособленный (survival of the fittest). В качестве примера можно привести оператор, выбирающий особь для размножения случайно. При этом вероятность участия особи в процессе размножения вычисляется по формуле: Pi = f i / f j, j =1 n (2.1) где Pi - вероятность участия особи в процессе размножения, i - номер особи, п размер популяции, f i - значение целевой функции для i-ой особи. В данном случае целью поиска является нахождение максимума целевой функции. Очевидно, что одна особь может быть задействована в нескольких родительских парах. Аналогично может быть решён и вопрос уничтожения особей, только вероятность уничтожения, соответственно, должна быть обратно пропорциональна качеству особей. Однако обычно происходит просто уничтожение особей с наихудшим качеством. Таким образом, выбирая для размножения наиболее качественные особи и уничтожая наиболее слабые, генетический алгоритм постоянно улучшает популяцию, приводя к формированию лучших решений. Оператор скрещивания призван моделировать природный процесс наследования, то есть обеспечивать передачу свойств от родителей к потомкам. Кроссинговер смешивает генетический материал двух родителей, причем можно ожидать, что приспособленность родителей выше средней в предыдущем поколении, так как они только что прошли очередной раунд борьбы за выживание. Это аналогично соперничеству настоящих живых существ, где, как правило, сильнейшим удается передать свои (предположительно хорошие) гены следующему поколению. Важно, что кроссинговер может порождать новые хромосомы, ранее не встречавшиеся в популяции. Рассмотрим простейший оператор скрещивания. Он выполняется в два этапа. Пусть особь представляет собой строку из т элементов. На первом этапе равновероятно выбирается натуральное число к от 1 до т-1. Это число называется точкой разбиения. В соответствии с ним обе исходные строки разбиваются на две подстроки. На втором этапе строки обмениваются своими подстроками, лежащими после точки разбиения, то есть элементами с k+1-го по m-й. Так получаются две новые строки, которые унаследовали частично свойства обоих родителей. Этот процесс проиллюстрирован ниже: Строка1 X(1)X(2)ЕX(k)X(k+1)ЕX(m) Строка2 Y(1)Y(2)ЕY(k)Y(k+1)ЕY(m) Y(1)Y(2)ЕY(k)X(k+1)ЕX(m) X(1)X(2)ЕX(k)Y(k+1)ЕY(m) Вероятность применения оператора скрещивания обычно выбирается достаточно большой (в пределах от 0,9 до 1), чтобы обеспечить постоянное появление новых особей, расширяющих пространство поиска. При значении вероятности меньше 1 часто используют элитизм [94]. Это особая стратегия, которая предполагает переход в популяцию следующего поколения элиты, то есть лучших особей текущей популяции, без каких-либо изменений. Применение элитизма способствует сохранению общего качества популяции на высоком уровне. При этом элитные особи участвуют еще и в процессе отбора родителей для последующего скрещивания. Количество элитных особей определяется обычно по формуле: К = (1 - Р) * N скрещивания, N - размер популяции. В случае использования элитизма все выбранные родительские пары подвергаются скрещиванию, несмотря на то, что вероятность применения оператора скрещивания меньше 1. Это позволяет сохранять размер популяции постоянным. Следующий этап - мутация (mutation). Оператор мутации служит для моделирования природного процесса мутации. Его применение в генетических алгоритмах обусловлено следующими соображениями. Исходная популяция, какой бы большой она ни была, охватывает ограниченную область пространства поиска. Оператор скрещивания, безусловно, расширяет эту область, но все же до определенной степени, поскольку использует ограниченный набор значений, заданный исходной популяцией. Даже для (2.2) где К - количество элитных особей, Р - вероятность применения оператора больших популяций может оказаться, что не все биты генетического материала в ней представлены. Например, если первый бит у всех хромосом равен 0, то кроссинговер никогда не породит решение с 1 в первом бите. Мутация предназначена для того, чтобы избежать таких ситуаций и увеличить разнообразие популяции. Как правило, вероятность мутации, в отличие от вероятности скрещивания, выбирается достаточно малой. Сам процесс мутации заключается в замене одного из элементов строки на другое значение. Это может быть перестановка двух элементов в строке, замена элемента строки значением элемента из другой строки, в случае битовой строки может применяться инверсия одного из битов и т. д. Мутация и кроссинговер могут порождать новые решения, которые никогда не встречались в предыдущих поколениях. Для оценки качества этих решений вычисляется фитнес-функция. На этом построение нового поколения решений заканчивается. В процессе работы алгоритма все указанные выше операторы применяются многократно и ведут к постепенному изменению исходной популяции. Поскольку операторы отбора, скрещивания, мутации и редукции по своей сути направлены на улучшение каждой отдельной особи, то результатом их работы является постепенное улучшение популяции в целом. В этом и заключается основной смысл работы генетического алгоритма - улучшить популяцию решений по сравнению с исходной. После завершения работы генетического алгоритма из конечной популяции выбирается та особь, которая дает экстремальное (максимальное или минимальное) значение целевой функции и является, таким образом, результатом работы генетического алгоритма. За счет того, что конечная популяция лучше исходной, полученный результат представляет собой улучшенное решение.
2.6 Вычислительная эффективность применения ГА. Теорема схем Генетический алгоритм обрабатывает строки, представляющие хромосомы. Разнообразные строки можно описывать с помощью шаблонов строк, которые называют схемами хромосом. Схема хромосомы H Ч это строка длины L (длина любой строки популяции), состоящая из знаков алфавита V. Для бинарного случая V={0;
1;
*}, где знак * обозначает неопределенный символ, и каждая схема определяет множество всех бинарных строк длины l, имеющих в соответствующих позициях либо 0, либо 1. Например, бинарная схема 10*1 определяет собой множество из двух четырехбитовых строк {1001;
1011}. При необходимости алфавит может быть расширен. Для схем выделяют два свойства: порядок и длину. Порядок схемы O(H) Ч число закреплённых позиций (в двоичном алфавите - число определенных битов, 0 или 1). Длина схемы L(H) Ч расстояние между крайними определенными позициями (битами) в схеме. Например, вышеупомянутая схема 10*1 имеет порядок O(10*1) = 3, а определенная длина L(10*1) = 3. Строительными блоками называют схемы, обладающие высокой приспособленностью, низким порядком и короткой длиной. Приспособленность схемы определяется как среднее от приспособленностей экземпляров строк, которые ее содержат. Процедура отбора выбирает строки с более высокой приспособленностью. Следовательно, строки, которые являются примерами высокоприспособленных схем, выбираются чаще. Кроссовер реже разрушает схемы с более короткой длиной, а мутация реже разрушает схемы с низким порядком, поэтому такие схемы имеют больше шансов переходить из поколения в поколение. Дж. Холланд [72] показал, что, если ГА явным образом обрабатывает n строк в каждом поколении, то он неявно обрабатывает порядка n3 коротких схем низкого порядка и с высокой приспособленностью (useful schemata). Это явление называется неявным параллелизмом. Для решения реальных задач присутствие неявного параллелизма означает, что большая популяция имеет больше возможностей локализовать решение экспоненциально быстрее популяции с меньшим числом особей. ГА экспоненциально увеличивает число примеров полезных схем или строительных блоков. Данное утверждение известно как теорема схем. Пусть в момент времени t в популяции S(t) содержится множество хромосом S j, j=1,2,Е, n, а схема H строится на основе заданного алфавита V. Тогда схема может быть определена на хромосоме длины L. Так, для алфавита мощности M существует (M+1)L схем и n*2 L схем, содержащихся в популяции размером n двоичных хромосом. Пусть m(H, t) Ч число представителей схемы H в t-м поколении. Вычислим ожидаемое число представителей H в следующем поколении или m(H, t+1) относительно m(H, t). ГА ставит в соответствие каждой строке вероятность ее отбора для последующего размножения. В процессе репродукции вероятность попадания хромосомы Si в репродуцированное множество для случая использования пропорционального оператора отбора равна:
Pi = f (S i ) f (S j = n, ) (2.3) j где f(Sj) - значение функции приспособленности для j-ой хромосомы, а n - размер популяции. То есть, эта вероятность зависит от значения целевой функции. За время t+1 в популяции S(t) ожидается получить m(H, t+1) представителей схемы H, которое вычисляется по формуле: m( H, t + 1) = m( H, t )n f (H ) f (S j = n, ) (2.4) j где f(H) - среднее значение целевой функции хромосом, представленных схемой H за время t. Так как среднее значение целевой функции для всей популяции равно:
f cp ( S ) = то f (S j = n j ), (2.5) n m( H, t + 1) = m( H, t ) f (H ). f cp ( S ) (2.6) Из этой формулы можно сделать вывод о том, что увеличение количества частных схем определяется отношением среднего значения целевой функции схемы к среднему значению целевой функции популяции. Поэтому схема, для которой значение целевой функции f(H) выше fcp(S), имеет большую вероятность копирования. Правило Холланда: Схема со значением целевой функции выше среднего живёт и копируется, а схема со значением ниже среднего умирает. Если предположить, что схема H является жизнеспособной, то f(H)fcp(S). Тогда значение целевой функции для схемы H можно выразить через среднее значение для всей популяции, например, следующим образом: (1+c)fcp(S), где c - константа. Число представителей схемы в следующем поколении будет: m( H, t + 1) = m( H, t ) (1 + c ) f cp (S ) f cp (S ) = (1 + c)m( H, t ). (2.7) Если принять значение c постоянным во времени, то за период 0tt* можно вычислить количество представителей схемы H по формуле: m( H, t ) = (1 + c) t m( H,0), * (2.8) из которой следует, что репродукция может приводить к экспоненциальному увеличению (c > 0) или уменьшению (c < 0) числа схем. Пусть на некотором шаге генетического алгоритма P1 есть вероятность того, что хромосома A порождает потомка, и P2 есть вероятность, что A уничтожается. Вероятность выживания хромосомы A на шаге t после операции репродукции определяется по формуле PS (t ) = (1 P2 ) t 1 P1, (2.9) где t=1, 2, Е, g;
g - число шагов (генераций) генетического алгоритма. Значение вероятности выживания хромосомы изменяется после операций кроссинговера и мутации. Использование оператора кроссинговера может вызвать увеличение или уменьшение числа схем в популяции. Если кроссинговер не применяется, то обмен между хромосомами отсутствует, поэтому поисковое пространство не увеличивается, и процесс затухает. Вероятность того, что одноточечный кроссовер разрушит схему, равна вероятности того, что точка разрыва попадёт между определёнными битами. Для хромосомы длины L существует L-1 точка разреза. Если оператор кроссинговера выполняется на основе случайного выбора с вероятностью Pс, то вероятность выживания схемы определяется по формуле: PS,CO ( H ) 1 Pc L ( H ), L 1 (2.10) где L(H) - определённая длина схемы, а L - длина хромосомы. Вероятность не меньше приведённого значения, поскольку схема может выжить, если в кроссовере участвовал пример похожей схемы. Приведённое выражение свидетельствует о том, что вероятность выживания схемы уменьшается при возрастании Pс. Вычислим число схем H в новой генерации после операций репродукции и кроссинговера, допуская их взаимную независимость: m( H, t + 1) m( H, t ) f (H ) L( H ) 1 Pc L 1. f cp (S ) (2.11) Из этого выражения следует, что число схем m(H,t+1) зависит от значений целевой функции для схемы и для всей популяции, а также от длины схемы L(H). Рассмотрим влияние мутации на выживание схем. Единственная позиция хромосомы выживает с вероятностью 1-Pm, где Pm - вероятность оператора мутации. Если учесть тот факт, что частная схема выживает в случаях, когда выживает каждая из O(H) закреплённых позиций схемы, то вероятность выживания схемы равна (1- Pm)O(H). Для малых величин Pm <1 вероятность может быть представлена выражением: PS,MO = 1 O ( H ) Pm. (2.12) С учётом сказанного, для частной схемы H можно определить ожидаемое число копий в следующем поколении после реализации операторов отбора, кроссинговера и мутации по следующей формуле: m( H, t + 1) m( H, t ) f (H ) L( H ) 1 Pc L 1 [1 O( H ) Pm ] = f cp ( S ) f (H ) L( H ) L( H ) = m( H, t ) 1 Pc L 1 O( H ) Pm + Pc Pm O ( H ) L 1 f cp ( S ) (2.13) Или в более традиционном для литературы по генетическим алгоритмам виде: m( H, t + 1) m( H, t ) f (H ) L( H ) 1 Pc L 1 O( H ) Pm f cp (S ) (2.14) Данная формула отражает фундаментальную теорему генетического алгоритма, которая определяет асимптотическое число схем, выживающих при его реализации на каждой итерации. Наиболее существенное влияние на число выживающих схем оказывают значения целевых функций отдельной схемы и всей популяции, а эффективность реализации генетических алгоритмов зависит от размера строительных блоков. Теорема схем показывает, что количество строительных блоков растет по экспоненте, в то время как схемы с приспособленностью ниже средней распадаются с той же скоростью. Теорема весьма упрощенно описывает поведение ГА. Во-первых, f(H) и fcp не остаются постоянными от поколения к поколению, и приспособленности членов популяции изменяются уже после нескольких первых поколений. Во-вторых, теорема схем объясняет лишь потери схем, но не появление новых. В то же время, несмотря на простоту, теорема схем описывает несколько важных аспектов поведения ГА. Мутации с большей вероятностью разрушают схемы высокого порядка, в то время как кроссовер с большей вероятностью разрушает схемы с большей определенной длиной. Популяция сходится, то есть стабилизируется на хорошем решении, пропорционально отношению приспособленности лучшей особи к средней приспособленности в популяции;
это отношение называется мерой давления отбора (selection pressure).
Увеличение Pc, или Pm, или уменьшение давления отбора увеличивает пространство поиска, но не позволяет использовать все хорошие схемы, которыми располагает ГА. Уменьшение Pc, или Pm, или увеличение давления выбора ведет к улучшению использования найденных схем, но тормозит исследование пространства в поисках новых хороших схем. Генетический алгоритм должен отслеживать равновесие, проблему поддержания которого называют проблемой баланса исследования и использования. Генетический алгоритм не выполняет полный перебор всех точек в пространстве поиска, но он обрабатывает значительное число гиперплоскостей поискового пространства, отличающихся высокой приспособленностью. Каждая гиперплоскость соответствует множеству похожих строк с высокой приспособленностью. Преимущества генетических алгоритмов становятся еще более прозрачными, если рассмотреть основные их отличия от традиционных методов. Основных отличий четыре [19]. 1. Генетические алгоритмы работают с кодами, в которых представлен набор параметров, напрямую зависящих от аргументов целевой функции. Причем интерпретация этих кодов происходит только перед началом работы алгоритма и после завершения его работы для получения результата. В процессе работы манипуляции закодированная с кодами строка, происходят например, совершенно битовая, независимо или от их интерпретации - код рассматривается просто как соответствующим образом символьная строка вещественных чисел. 2. Для поиска генетический алгоритм использует несколько точек поискового пространства одновременно, а не переходит от точки к точке, как это делается в традиционных методах. Это позволяет преодолеть один из их недостатков - опасность попадания в локальный экстремум целевой функции, если она не является унимодальной, то есть имеет несколько таких экстремумов. Использование нескольких точек одновременно значительно снижает такую возможность. 3. Генетические алгоритмы в процессе работы не используют никакой дополнительной информации, что повышает скорость работы. Единственной используемой информацией может быть область допустимых значений параметров и целевой функции в произвольной точке. 4. Генетический алгоритм использует как вероятностные правила для порождения новых точек анализа, так и детерминированные правила для перехода от одних точек к другим. Выше уже говорилось, что одновременное использование элементов случайности и детерминированности дает значительно больший эффект, чем раздельное. Замечательная черта генетических алгоритмов состоит в том, что они выполняют множество изощренных манипуляций с решениями задачи, представленными отдельными хромосомами, но без малейшего представления о том, что же при этом происходит. Фитнес-функция - это единственная часть программы, которая должна понимать, что же на самом деле кодирует хромосома. Поэтому для каждого приложения надо писать новые фитнес-функции. Тут нужно обратить внимание, что фитнес-функция - это, пожалуй, наиболее важная (или одна из) деталь ГА. При этом необходимо выделить 3 главных момента [51]: 1. Функция оценки должна быть адекватна задаче. Это означает, что для успешного поиска лучшего решения необходимо, чтобы распределение значений фитнес-функции совпало с распределением реального качества решений (не всегда качество решения эквивалентно его оценке по фитнесфункции). 2. Фитнес-функция должна иметь рельеф, то есть ощутимо изменяться при смещении по ландшафту параметров. Мало того, рельеф должен быть разнообразным. Это означает, что ГА имеет мало шансов на успех, если на поверхности фитнес-функции есть огромные плоские участки - это приводит к тому, что многие (или, что хуже, все) решения в популяции при различии в генотипе не будут отличаться фенотипом, то есть, несмотря на то, что решения различаются, они имеют одинаковую оценку, а значит алгоритм не имеет возможности выбрать лучшее решение - выбрать направление дальнейшего развития. Эта проблема также упоминается как проблема поля для гольфа, когда всё пространство абсолютно одинаково, за исключением лишь одной точки, которая и является оптимальным решением - в этом случае алгоритм просто остановится или будет блуждать абсолютно случайно. 3. Фитнес-функция должна требовать минимума ресурсов. Так как это наиболее часто используемая деталь алгоритма, она оказывает существенное влияние на скорость его работы. Успешное решение задачи №1 при работе с СММ, описанное в Главе 1, непосредственно влияет на этот процесс.
Генетические алгоритмы имеют два слабых места. Сама постановка задачи в их терминах, во-первых, не дает возможности проанализировать статистическую значимость получаемого с их помощью решения, так как выборка производится не равномерно по всем точкам пространства параметров, а больше ориентируясь на уже известные хорошие решения, и, во-вторых, эффективно сформулировать задачу - определить критерий отбора хромосом под силу только специалисту. В силу этих факторов генетические алгоритмы сегодня надо рассматривать скорее как инструмент научного исследования, чем как средство анализа данных для практического применения. Но в двух случаях генетические алгоритмы очень хороши. Первый - когда не известен способ точного решения задачи. Если мы знаем, как оценить приспособленность хромосом, то всегда можем заставить генетический алгоритм решать эту задачу. Второй случай - когда способ для получения точного решения существует, но очень сложен в реализации (требует больших затрат времени и денег, то есть, попросту говоря, дело того не стоит).
2.7 Выводы В главе рассмотрены основные методы поиска оптимальных решений и границы их применимости. Для систем на основе СММ (в том числе и систем автоматического распознавания речи) показано, что методы, основанные на математических вычислениях, способны привести только к локальному экстремуму или неприменимы в силу чрезвычайно жёстких ограничений на целевую функцию, выполнить которые при обучении СММ не представляется возможным. Кроме того, традиционно используемый для обучения СММ метод Баума-Велча или эквивалентная ему EM-процедура сильно зависят от стартовых значений, что также является ограничением. На примере системы распознавания речи, существующей на кафедре ЭВА МИЭМ, обнаруживаются серьёзные проблемы и при попытках использовать перечислительные методы - из-за очень высокой размерности задачи и требований к точности представления данных в моделях попытка решения этой задачи ведёт к т.н. комбинаторному взрыву, то есть фактической невозможности перебрать все возможные решения и найти среди них оптимальное. Рассмотрена современная концепция эволюционных вычислений и в её контексте особенно подробно описана парадигма генетических алгоритмов, включая последователь ность работы типового генетического алгоритма, и объяснены принципы его работы. Посредством теоремы схем показана заметно лучшая вычислительная эффективность применения ГА, чем у перечислительных методов, а также способность алгоритма не зацикливаться на локальном экстремуме. Задача обучения СММ, рассмотренная в первой главе, удовлетворяет предпосылкам для успешного применения аппарата генетических алгоритмов. Поскольку точное и однозначное решение данной задачи не известно, но есть возможность оценить каждое из предлагаемых решений, есть критерий для оценки получившегося результата и, как следствие, - возможность реализовать оценочную функцию (фитнес-функцию) для использования в генетическом алгоритме. Кроме того, вычисление фитнес-функции (значение которой равно вероятности генерации наблюдаемой последовательности при заданных параметрах скрытой марковской модели) не является особенно трудоёмким, что позволяет многократно её вычислять для различных параметров, то есть создавать популяции решений. Эффективную фитнес-функцию позволяет создать решение рассмотренной в Главе 1 задачи №1. Сами параметры, подлежащие оптимизации (матрица переходов СММ), весьма хорошо соответствует понятию хромосомы - эти параметры (элементы матрицы) могут быть легко отделены друг от друга и закодированы каждый в своём гене хромосомы, так что генетический алгоритм окажется способным создавать произвольные их комбинации в поисках тех, что ведут к лучшим значениям целевой функции. Итак, налицо все предпосылки для использования генетических алгоритмов для оптимизации процесса обучения СММ.
Глава 3. Реализация генетического алгоритма для решения задачи оптимизации СММ 3.1 Система распознавания речевых команд на основе СММ Одним из этапов работ в области распознавания речи, ведущихся на кафедре ЭВА МИЭМ, была разработка в 1998 году Серовым А.А. системы оценки стартовых параметров СММ в задачах распознавания команд при кепстральной предобработке речевого сигнала [33]. Программная часть комплекса получила название SdiApp. Система реализует работу со скрытыми марковскими моделями изолированных слов в непрерывном признаковом пространстве на основе кепстральных коэффициентов. На сегодняшний день кепстральные коэффициенты довольно часто используются в системах распознавания речи для определения признакового пространства. Другие распространённые варианты - это LPC (Linear Prediction Coefficients), PLP (Perceptual Linear Predictive), Rasta, ASSF и др. Основное достоинство кепстральных коэффициентов в том, что они наиболее точно соответствуют модели речеобразования в современном ее понимании и позволяют достаточно точно характеризовать состояние речевого тракта диктора по данным наблюдения косвенного процесса изменения давления воздуха возле микрофона системы распознавания. Для систем распознавания на основе СММ использование кепстральных коэффициентов выражается в необходимости использовать непрерывные СММ, так как само признаковое пространство непрерывно. Система SdiApp ориентирована на работу с командами (изолированными словами), что подразумевает построение моделей всех подлежащих распознаванию слов. Схема работы распознавателя команд рассмотрена в главе 1. Слова, поступающие на вход системы с микрофона, из звуковых файлов или из речевой базы данных (РБД), имеющейся на кафедре ЭВА МИЭМ [5], преобразуются в последовательность векторов кепстральных коэффициентов, и в дальнейшем система может быть обучена, то есть могут быть построены скрытые марковские модели для выбранных слов. Как было отмечено в первой главе, этот процесс представляет собой одну из задач оптимизации, и поэтому именно в этом месте оправдано применение генетических алгоритмов.
Оптимизации необходимо подвергнуть матрицы вероятностей переходов СММ в поисках более хороших решений. Матрицы вероятностей начальных состояний СММ в оптимизации не нуждаются, так как решением этой задачи занимается программа SdiApp, однако при необходимости это сделать не возникнет никаких преград. Матрицы вероятностей наблюдаемых символов также не требуется модифицировать, так как они строятся исходя из статистики наблюдаемых символов в речевом сигнале, и это также задача SdiApp. Исходная популяция для генетического алгоритма может быть сформирована на основе результатов работы системы SdiApp, но, как показали эксперименты автора, и что будет рассмотрено далее, ГА хорошо работает и при старте со случайно сгенерированной популяцией.
3.2 Построение генетического алгоритма для оптимизации процесса обучения СММ тренировочными последовательностями 3.2.1 Кодирование хромосомы Первая важная задача, которую надо решить при проектировании генетического алгоритма - это задать механизм кодирования информации в хромосоме, поскольку от правильного выбора варианта кодирования зависит скорость и качество работы ГА. Существует несколько стандартных подходов к кодированию хромосом [51]: 1) Кодирование хромосомы двоичной битовой строкой. Параметры, подлежащие оптимизации, кодируются битовой строкой, в которой каждому параметру соответствует её определённая часть. Данный метод особенно эффективен, когда параметры имеют дискретный набор значений. Кодирование в этом случае получается весьма экономным, а генетические операторы - быстрыми и простыми. Так, например, работа оператора мутации часто сводится к инверсии одного или нескольких случайно выбранных бит в строке, а скрещивание - к объединению частей двух битовых строк или к их сложению с учётом предварительно наложенной битовой маски. Следует заметить, что определённые наборы параметров могут быть некорректными и недопустимыми логикой самой задачи, и правильный выбор метода способен исключить такие варианты ещё на этапе кодирования хромосомы, сделав так, что недопустимым состояниям просто не будет соответствовать ни одна реальная хромосома. Наиболее просто это реализуется именно с двоичными хромосомами.
Вариацией этого метода является кодирование с использованием кодов Грэя (Gray codes) [45, 80]. Коды Грэя - это двоичные коды, особенность которых в том, что последовательные значения отличаются лишь одним битом в строке. Такое кодирование влияет на работу оператора мутации - случайная мутация имеет больше шансов привести к последовательным малым изменениям особи, но при этом и расширяет диапазон этих возможных изменений. Эта интересная возможность может быть охарактеризована так: большая часть мутаций ведёт лишь к малым последовательным изменениям, в то время как редкая мутация способна привести к действительно серьёзным изменениям и инициировать исследование алгоритмом новой области в пространстве хромосом. 2) Кодирование хромосомы символьной строкой. Этот метод, по сути, является расширением предыдущего, и разница лишь в том, что вместо битов используются символы, принимающие больше двух возможных значений. Впрочем, есть и некоторая разница - в двоичной хромосоме для кодирования одного параметра часто используются несколько бит (как в случае кодирования целого числа), а в символьной - каждый параметр обычно кодируется своим значением символа (но можно сделать ещё один шаг и начать кодировать параметры несколькими недвоичными символами - в этом случае рассматриваемая далее аналогия с биологическими системами ещё более усилится). Это несколько, хотя и не сильно, усложняет генетические операторы и лишает разработчика алгоритма некоторых возможностей по оптимизации скорости их работы, связанных с простым представлением двоичных чисел в современных ЭВМ, зато этот метод очень гибок и легко расширяем при необходимости, если требуется увеличить число возможных значений, а сама хромосома очень наглядна. Стоит заметить, что этим методом кодирования хромосомы часто эмулируется первый метод, когда на самом деле вместо битовой строки используется и хранится в памяти машины символьная строка, но алфавит её допускает лишь два возможных значения - У0Ф и У1Ф. В случаях, когда это не вносит особых замедлений скорости работы алгоритма, такой подход оправдан большей наглядностью самой хромосомы, что в некоторых случаях может быть полезно разработчику. Дополнительным преимуществом этого метода кодирования хромосомы является в определённом смысле его аналогичность кодированию информации в биологических системах, где ипользуется алфавит из четырёх возможных нуклеотидов: аденин, тимин, гуанин и цитозин (А, Т, Г, Ц) в ДНК, или аденин, урацил, гуанин и цитозин (А, У, Г, Ц) в РНК [18]. Упоминаемое ранее кодирование параметра несколькими недвоичными символами близко по сути к наличию в ДНК кодонов - трёх следующих друг за другом нуклеотидов, кодирующих определённый аминокислотный остаток [18]. Таким образом, данный метод кодирования может быть полезен сторонникам создания систем, которые как можно более полно соответсвуют биологическим, а также в решении задач биологии. 3) Кодирование хромосомы вещественными числами. Каждый параметр описывается вещественным числом, и хромосома представляет собой вектор вещественных чисел. Минусом метода является то, что на хранение вещественных чисел требуется больше памяти, чем на хранение хромосом в одном из предыдущих вариантов. Правда, даже при размере популяции в несколько тысяч особей (например, 5000 - весьма крупная популяция) и количестве закодированных в одной хромосоме параметров в 100 (достаточно большая хромосома), при выделении на вещественное число 8 байт на хранение популяции потребуется 8*100*5000 = 4000000 байт, что при нынешнем развитии компьютерной техники не представляется значительной величиной. Зато у этого метода есть и большие плюсы. В случае, если природа параметров такова, что они описываются именно вещественными числами (например, значения вероятностей или кепстральные коэффициенты), кодирование в двоичной хромосоме потребует их дискретизации и приведёт к неизбежной потере точности, в случае если разработчиком алгоритма будет выделено недостаточно количество бит на один параметр, а в случае использования хромосомы вещественных чисел такой проблемы не будет. Кроме того, оперирование вещественными числами в таком случае избавляет от постоянных перекодировок параметров во время работы алгоритма из битовой формы в числовую, что положительно сказывается на скорости и надёжности работы программы. Возможны и комбинированные методы кодирования, например, когда часть параметров кодируется вещественными числами, а часть - общей битовой строкой. Параметры, требующие оптимизации в решаемой задаче, - это элементы матрицы вероятностей переходов (в дальнейшем просто матрицы), которые по своей природе являются вещественными числами. Кроме того, при вычислении вероятности генерации итоговой последовательности моделью происходит перемножение отдельных вероятностей, что при малой точности представления способно привести к накоплению больших ошибок и отрицательно сказаться на качестве распознавания. В силу вышеперечисленного оправданным. Итак, для данной задачи хромосома представляет собой набор строк матрицы кодирование хромосомы вещественными числами является вероятностей переходов, каждая из которых является набором вещественных чисел. На строки и элементы матрицы существуют ограничения, и их надо учитывать при работе алгоритма: как было сказано в главе 1, каждый элемент матрицы переходов должен иметь неотрицательное значение (см. 1.2) и, кроме того, сумма элементов строки должна равняться единице (см. 1.3). Подробнее реализация этих ограничений будет рассмотрена далее вкупе с оператором мутации. Значением целевой функции является вероятность генерации обучающего слова на основе конкретного экземпляра данной СММ при определённых значениях элементов матрицы вероятностей переходов, которые и определяются содержимым хромосомы. Вот примеры двух матриц переходов для модели слова линформация (СММ с поступательно ограниченными переходами, количество состояний модели N=10):
N:10 F:9,57077200489701E-215 0,96666664 0,01609195 0,01724138 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,96428573 0,01847291 0,01724138 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,96666664 0,01666667 0,01666667 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,96428573 0,01724138 0,01847291 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,96428573 0,01847291 0,01724138 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,96666664 0,01609195 0,01724138 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,96428573 0,01847291 0,01724138 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,89905173 0,08428159 0,01666667 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,96428573 0,03571429 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 1, N:10 F:8,23964039298564E-212 0,93309182 0,06690814 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,92160136 0,07839863 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,93325907 0,06674092 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,92900026 0,07099972 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,92766172 0,07233825 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,93466944 0,06533053 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,92807543 0,07192456 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,93282956 0,06717033 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,92797035 0,07202973 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 0,00000000 1, Здесь отображено генетического алгоритма, содержимое и видно, матрицы что переходов до и с после работы изначальная модель поступательно ограниченными переходами стала ещё более строгой, с переходами только в следующее состояние. В результате мы получили модель, сильно оптимизированную на конкретный экземпляр слова, вероятность генерации которой выше, чем у исходной модели, на несколько порядков: 8,239640*10 -212 против 9,570772*10 -215. Это безусловно хорошо, если требуется точно распознать именно этот образец слова, но может отрицательно сказаться на распознавании других экземпляров этого слова, в произнесении которых наблюдается некоторая вариативность, что может иметь место при работе системы с различными дикторами или же при изменении физического состояния того же самого диктора. В целях учёта такой ситуации проводить оптимизацию надо на наборе вариантов произнесения слова, а не на одном его экземпляре. В зависимости от условий работы системы распознавания речи, должна ли она работать с одним диктором в каждый момент времени или со многими, на вход системы подаются несколько образцов одного и того же слова, произнесённые одним диктором в разные моменты времени или в разном эмоциональном состоянии, или же произнесённые различными дикторами. Фитнесфункция должна учитывать этот полный набор слов и проводить оценивание особей по каждому экземпляру слова, подводя обобщённый итоговый результат. Для этого может использоваться комбинированная фитнес-функция, получающая вероятности генерации для каждого из образцов слова, входящего в набор, и составляющая их взвешенную сумму. Комбинированная фитнес-функция будет рассмотрена в главе 4. При необходимости, в хромосому можно добавить отдельной строкой и матрицу вероятностей начальных состояний, поскольку она имеет те же размеры, что и строка матрицы вероятностей переходов, и подчиняется тем же самым ограничениям. Длина хромосом для данной задачи постоянна, так как строки матрицы имеют фиксированную длину, равную числу состояний модели. Возможно построение хромосом переменной длины, но в нашем случае это не требуется, так как размерность матрицы в процессе работы строго фиксирована и не изменяется. Такой подход практикуется, к примеру, в мобильных генетических алгоритмах (МГА, messy GA), где возможны как неполные, так и избыточные хромосомы [44].
3.2.2 Создание исходной популяции Для работы генетического алгоритма требуется задать начальную популяцию - ту точку, с которой он стартует и которая подлежит улучшению. Как было сказано ранее, на вход генетического алгоритма может быть подана случайно сгенерированная популяция, но часто подаются и результаты работы какого-либо другого алгоритма. Так и в нашем случае, на выходе программы SdiApp уже имеется набор стартовых параметров СММ, отражающий общие закономерности всех экземпляров текущего слова, модель которого подвергнется оптимизации. Представляется разумным не отказываться от этой информации и построить исходную популяцию для работы генетического алгоритма, основываясь именно на этих данных. Здесь возникает вопрос, как именно сгенерировать особей стартовой популяции. Дело в том, что стартовые параметры СММ описываются только одной особью, и у нас есть выбор, либо заполнить всю исходную популяцию полностью идентичными особями и позволить затем оператору мутации начать движение по ландшафту параметров, либо же сразу внести в неё некоторое разнообразие, чтобы ускорить старт алгоритма и сдвинуть дело с мёртвой точки. Предлагается следующий вариант создания популяции: за основу её по-прежнему берутся результаты работы алгоритма оценки стартовых параметров СММ и на их основе создаются особи, часть из которых сразу же подвергается мутации для того, чтобы разнообразить эту популяцию. Кроме того, популяция может быть сразу же дополнена определённым числом случайных особей, что уменьшит изначальную возможность застревания алгоритма в локальном экстремуме, когда алгоритм остаётся в пределах локального пика ландшафта и оказывается неспособным найти более высокий пик. Для этого же предназначен и оператор мутации в основном цикле работы ГА, но нет смысла оставлять эту работу для него на потом, поскольку добавление случайных особей в популяцию по крайней мере не сделает её хуже с точки зрения максимального качества отдельных особей. Экспериментальные исследования автора показали, что существенной разницы в эффективности этих двух подходов не наблюдается - вариант со случайными мутациями на этапе создания исходной популяции действительно опережает на несколько шагов на начальных этапах вариант с полностью идентичными особями, но в дальнейшем стабилизация результата происходит примерно в одинаковых точках (см. рис. 3.1):
Pages: | 1 | 2 | 3 | Книги, научные публикации