Содержание к диссертации
Введение
ГЛАВА 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 Направления развития генетических алгоритмов 99
4.3.1 Использование комбинированной фитнес-функции 99
4.3.2 Адаптивный ГА 99
4.4 Выводы 102
Выводы и заключение 105
Литература
- Основные задачи при применении смм к распознаванию речи
- Методы, основанные на математических вычислениях
- Построение генетического алгоритма для оптимизации процесса обучения смм тренировочными последовательностями
- Показатели эффективности генетических алгоритмов
Введение к работе
Работы в области систем распознавания речи имеют уже довольно долгую историю. В Советском Союзе работы по компресии речи начались в начале 50-х годов, а по автоматическому распознаванию - в конце 50-х годов. При этом следует отметить, что первая в мире система автоматического распознавания речи была продемонстрирована в 1939 году в Ленинградском Государственном Университете Л.Л.Мясниковым. В 70-х годах в разработке речевых систем начали активно выходить вперёд США, тем не менее уровень теоретических и приладных разработок в СССР и США до середины 80-х годов оставался приблизительно одинаковыми С середины 80-х годов значительная часть речевых разработок в нашей стране была прекращена, и в настоящее время помимо США в области речевых технологий активно и очень успешно работает ещё ряд стран (ЕС, Япония, Канада, Австралия). [10] Но в нынешний момент происходит процесс восстановления интереса к этой области и в нашей стране, и на рынке появляются отечественные разработки, например, системы SPIRIT [89] и Sakrament [85].
В настоящее время работы по распознаванию речи не только не потеряли актуальности, но и развиваются широким фронтом, находя для себя множество областей для практического применения. Сейчас можно выделить 4 сравнительно изолированных направления в области развития речевых технологий [9]:
Распознавание речи - т.е. преобразование речевого акустического сигнала в цепочку символов, слов. Эти системы могут быть охарактеризованы по ряду параметров. Прежде всего это объём словаря: малые объёмы до 20 слов, большие - тысячи и десятки тысяч. Количество дикторов: от одного до произвольного. Стиль произнесения: от изолированных команд до слитной речи и от чтения до спонтанной речи. Коэффициент ветвления, т.е. величина, определяющая количество гипотез на каждом шаге распознавания: от малых величин (<10-15) до больших (-100-200). Отношение сигнал/шум от больших (>30 дб) до низких (<10 дб). Качество каналов связи: от высококачественного микрофона до телефонного канала. Качество работы систем распознавания речи обычно характеризуется надёжностью распознавания слов, или, что то же самое, процентом ошибок.
Определение индивидуальности говорящего. Эти системы прежде всего делятся на 2 класса: верификация говорящего (т.е. подтверждение его личности) и идентификация.говорящего (т.е. определение его личности из
заранее ограниченного числа людей). Оба эти класса далее могут быть разделены на тексто-зависимые и тексто-независимые. Следующий характеристический параметр - объём парольной фразы. Два других (как и в распознавании речи): отношение сигнал/шум и качество канала связи. Качество работы систем верификации/идентификации говорящего характеризуется двумя величинами: вероятностью не опознания «своего» диктора и вероятностью принятия «чужого» диктора за своего.
3. Синтез речи. Практически существует 2 класса:
Воспроизведение записанного в той или иной форме ограниченного числа сообщений;
Синтез речи по тексту.
Синтезаторы характеризуются по следующим параметрам: разборчивость (словесная или слоговая), естественность звучания, помехоустойчивость.
4. Компрессия речи. Основной (и единственный) классификационный признак
этих систем - степень компрессии: от низкой (32-16 кбит/сек) до высокой
(1200-2400 кбит/сек и ниже). Качество работы систем компрессии речи
характеризуется прежде всего разборчивостью компрессированной речи.
Дополнительными характеристиками очень важными в ряде приложений
являются узнаваемость голоса говорящего и возможность определения уровня
стрессованности говорящего.
В диссертационной работе рассматриваются системы первой группы - системы распознавания речи и их частный случай - системы распознавания речевых команд, т.е. распознавание изолированных слов, а не слитной речи. Такие системы весьма полезны на практике, и возросшая необходимость в них связана в первую очередь с появлением большого количества доступных человеку разнообразных устройств (персональные, мобильные и карманные компьютеры, коммуникаторы и мобильные телефоны, игровые и многофункциональные мультимедийные устройства с достаточной вычислительной мощностью) в сочетании с бурным развитием телекоммуникаций в современном мире. Растёт важность массового внедрения новых интерфейсов взаимодействия человека с техническими системами, поскольку традиционные интерфейсы во многом уже достигли своего совершенства, а вместе с ним и своих пределов. При традиционно высокой значимости информации, поступающей к нам через органы зрения, и её высокой доли среди всей сенсорной информации, считающейся равной порядка 85% [11], этот канал восприятия человека становится в значительной степени перегружен. И первоочередной
альтернативой здесь видится коммуникация именно по акустическому каналу.
Кроме того, системы распознавания (а также синтеза) речи также крайне важны для людей с ограниченным зрением, и эта ниша для их применения активно развивается прежде всего в области мобильной телефонии (малые размеры экранов телефонных аппаратов не дают таким людям возможности пользоваться ими с достаточной степенью комфорта), а также в бытовой технике (для управления разнообразными домашними устройствами). Для помощи таким людям производители вводят в свои устройства возможности управления посредством голосовых команд (при наборе номера в телефоне или во время навигации по пунктам меню), а также дублирования экранной информации голосом. И в первую очередь от таких продуктов требуется распознавание ограниченного набора команд пользователя, а не слитной речи с большим или неограниченным словарём. Благодаря стандартизации платформ и операционных систем телефонов расширяется круг сторонних разработчиков программных продуктов с данной функциональностью [22].
Значительно более развита ниша программ распознавания речи для персональных компьютеров, где уже достаточно давно существуют такие продукты как IBM ViaVoice, DragonDictate или «Горыныч» (являющийся локализованной версией системы DragonDictate, изначально ориентированной на английский язык), а также уже упоминавшиеся отечественные разработки Сакрамент и SPIRIT.
Отечественные разработки обладают тем преимуществом перед зарубежными, что они изначально ориентированы на русские фонемы. В отсутствии такой базы иностранные системы вынуждены работать с русским языком на основе английских фонем или некоторого общего и универсального их набора, что отрицательно сказывается на качестве распознавания. Так, по сообщениям прессы, первый зарубежный коммерческий продукт распознавания русской речи для телефонных приложений, включающий поддержку русских фонем, появился лишь в 2003 году - набор программных модулей, библиотек и утилит для разработки систем такого класса - SpeechPearl компании Philips Speech Processing [56].
Аппаратная база подобных систем на сегодняшний момент устоялась на нескольких основных вариантах:
Системы PC-класса на основе х8б-совместимых процессоров для программных продуктов, используемых в настольных компьютерах, в некоторых серверных или мобильных решениях;
Мобильные устройства (телефоны, коммуникаторы и т.п.) на основе процессорной архитектуры ARM (более 75% всех интегрированных
процессоров, выпускаемых в мире) [24];
3) Специализированные аппаратные решения на основе DSP-процессоров с
тенденцией замены их массовыми решениями из предыдущих двух классов, так как возросшая производительность универсальных процессоров позволяет решать задачи, прежде бывшие для них весьма тяжёлыми.
Тенденция экстенсивного наращивания производительности процессоров за счёт увеличения их рабочих частот, имевшая место в предыдущие годы, уступает место новой тенденции, нацеленной на активное использование параллелизма в различных его проявлениях. В ближайшие годы это выльется в создание многоядерных архитектур процессоров (от уже существующей технологии Intel HyperThreading к созданию двух- и более ядерных процессоров на одном кристалле, появления которых можно ожидать уже в 2006 году; крайне интересная технология Cell от альянса Sony, Toshiba и IBM, которая затронет не только компьютеры, но,.потенциально, и бытовую технику в доме), создание недорогих кластерных решений на основе стандартных компонент (начиная с проекта BeoWulf для ОС Linux) и массовое использование распределённых вычислений (от уже реализовавшихся одиночных проектов типа для взлома шифров или SETI@Home для поиска внеземных цивилизаций к технологии GRID и виртуализации вычислений, активно продвигаемых корпорацией IBM).
По мнению многих аналитиков и представителей различных компаний, грядёт эра параллельного программирования [25]. Одним из первых её предвестников можно назвать уже существующую технологию EPIC (Explicitly Parallel Instruction Computer) компании Intel, реализованную в коммерческих процессорах Itanium. Переход на новые параллельные архитектуры требует создания чрезвычайно сложных оптимизирующих компиляторов, изменения образа мышления программистов и приложения ими специальных усилий для разработки и реализации соответствующих алгоритмов. В таких условиях особую ценность представляют алгоритмы, учитывающие возможный параллелизм своей работы.
Далеко не все производители систем работы с голосом раскрывают особенности внутренней реализации своих систем, но тем не менее можно сказать, что одними из самых популярных систем распознавания на сегодняшний день являются системы, использующие теорию скрытого марковского моделирования (СММ) [38]. Помимо них в системах распознавания речи также используются нейронные сети (НС) и методы динамического программирования (ДП). В первой главе диссертации рассматривается
аппарат СММ применительно к задачам распознавания речи.
СММ - это довольно мощный (хотя и громоздкий) и весьма эффективный математический аппарат для решения задач распознавания речи [8]. Использование СММ для распознавания команд давно показало свою эффективность, а возросшие доступные вычислительные мощности открыли дорогу к использованию новых подходов к решению задач, встающих перед разработчиком подобных систем.
Одной из важнейших и наиболее сложных задач, возникающих при работе с СММ, является задача обучения модели, то есть нахождения таких её параметров, при которых модель точнее описывает «своё» слово, т.е. генерирует для последовательности речевого сигнала, содержащего это слово, большее значение вероятности, чем другие модели слов из словаря системы. В процессе распознавания команды в системе происходит оценка и сравнение между собой вероятностей генерации наблюдаемого слова различными моделями из словаря с тем, чтобы отобрать среди них наиболее вероятного претендента. Чем лучше модель описывает тестовое (или тренировочное) слово, тем больше шансов, что оно будет верно распознано, т.е. будет выбрано среди всех остальных слов словаря. Особенно заметным становится влияние качества обучения модели на результативность работы системы распознавания в том случае, если словарь системы разрастается, и в нём оказываются похожие слова, т.е. слова, модели которых генерируют близкие значения вероятности. В таких условиях выбор правильного варианта оказывается затруднительным. Кроме того, желательно, чтобы модель могла эффективно распознавать «своё» слово по-возможности в более широких пределах изменяющихся условий работы системы распознавания (в различных уровнях зашумлённости или при работе по каналам различающегося качества) и вариативности произнесения слов диктором (в случае стресса или наличия дефектов речи).
Отсюда следует, что задача обучения модели, причём её качественного обучения, является весьма актуальной и её решению должно уделяться повышенное внимание.
Существуют и давно применяются оптимизированные методы обучения СММ (например, метод Баума-Велча или ЕМ-метод), но они не свободны от недостатков, важнейшие среди которых - это сильная зависимость от начальных условий, порождающая задачу нахождения стартовых параметров СММ, и неспособность найти глобальный экстремум, если локальный экстремум оказывается ближе. Однозначно лучшего метода обучения СММ не известно, и для решения этой задачи могут применяться различные подходы.
Одним из таких потенциально интересных методов обучения являются
генетические алгоритмы (ГА). Генетические алгоритмы, относящиеся к концепции эволюционных вычислений, - это современное, перспективное и активно разрабатываемое направление методов оптимизации многокритериальных задач. Во второй главе диссертационной работы рассмотрена концепция ГА и их место среди других методов нахождения оптимальных значений, и проведена оценка их применимости к решению задачи обучения СММ.
Генетические алгоритмы уже активно используются для обучения нейронных сетей, проектирования структуры механизмов и составления расписаний, для оптимизации структуры телекоммуникационных сетей и размещения электронных элементов на плате, поиска оптимальной формы детали и раскроя ткани и т.д. Так, израильская компания «Schema» на основе генетических алгоритмов разработала программный продукт Channeling для оптимизации работы сетей сотовой связи путём выбора оптимальной частоты, на которой будет вестись разговор [44]; компания Boeing использовала генетические алгоритмы для оптимизации турбины двигателя самолёта Boeing 777, оказавшейся по крайней мере на 1% эффективнее с точки зрения расхода топлива (что для данной отрасли считается неожиданной удачей), а фирма Texas Instruments задействовала их для оптимизации расположения компонентов на чипе, чтобы создать как можно меньший по размерам чип, и использование ГА позволило сделать его на 18% меньшим по площади [79].
За рубежом известно несколько случаев применения ГА для оптимизации СММ в системах распознавания речи, ориентированных на английский язык [54, 76, 77]. Но различия в фонематической базе русского и английского языков, уже выступавшие причиной плохой работы иностранных систем распознавания речи с русским языком, не позволяют однозначно перенести на него опыт применения ГА, а отечественных работ подобной направленности на момент написания диссертации не обнаружено. К тому же перечисленные зарубежные работы имеют обзорный и довольно поверхностный характер, не несут в себе сколь-нибудь серьёзного анализа альтернатив реализации ГА и практически не содержат обоснования выбора применяемых решений.
В третьей главе диссертации предлагается разработанная автором в рамках программно-аппаратного комплекса «Иволга» конкретная реализация генетического алгоритма, предназначенного для оптимизации процесса обучения СММ тренировочными последовательностями. За основу взята разработанная на кафедре ЭВА МИЭМ в 1998 г. А.А.Серовым система оценки стартовых параметров непрерывных СММ в задачах распознавания команд при кепстральной предобработке речевого сигнала (система
SdiApp). Основной задачей SdiApp является получение стартовых параметров СММ для изолированных слов. Результаты её работы используются в разработанной автором системе «Иволга» как отправная точка для работы генетического алгоритма. В этой главе также рассмотрены различные альтернативы и предложены варианты кодирования хромосом ГА, выбраны реализации генетических операторов, подходящие для работы с непрерывными СММ, определены параметры генетического алгоритма, обеспечивающие наиболее эффективное решение поставленной задачи.
В четвёртой главе диссертации производится оценка эффективности генетических алгоритмов в решении задачи обучения СММ. Тестирование системы проводилось с использованием имеющейся речевой базы данных (РБД), также разработанной на кафедре ЭВА МИЭМ А.Г.Бурёй. Произведено сравнение результатов работы ГА с традиционными методами поиска оптимальных решений для СММ, рассмотрено влияние параметров генетического алгоритма на эффективность его работы, предложены варианты дальнейшего развития алгоритма, направленные на повышение скорости и устойчивости его работы.
Исследование автора показало, что ГА успешно справляются с поставленными задачами, являясь эффективным методом обучения СММ, свободным от основных недостатков традиционно используемого метода Баума-Велча, при этом успешно сочетаясь с ним в рамках единой системы распознавания речи. Кроме того, с учётом современных тенденций развития аппаратной части систем распознавания генетические алгоритмы имеют очень хорошие перспективы по части оптимизации эффективности своей работы, так как позволяют легко распараллелить работу ГА и распределить её между разными процессорами (или процессорными ядрами) в одной машине или между разными компьютерами в сети.
В приложении 1 приведено описание программного комплекса «Иволга», предназначенного для исследования генетических алгоритмов в рамках задачи распознавания голосовых команд.
В приложении 2 приведён пример работы системы генетических алгоритмов в рамках программного комплекса «Иволга».
Основные задачи при применении смм к распознаванию речи
Для использования СММ при распознавании речи необходимо решить три задачи [83].
Задача 1: Если заданы последовательность наблюдений О = Oi, О2,... От и модель X =(А,В,П), то как эффективно вычислить Р(0Х.) - вероятность такой последовательности при заданных параметрах модели? Задача 2: Если заданы последовательность наблюдений О = Oj, О2,... От и модель X =(А,В,П), то как определить соответствующую последовательность внутренних состояний Q = qb q2 ... qT?
Задача 3: Как определить параметры модели Х=(А,В,П), исходя из критерия максимизации Р(0Х)?
Очевидно, что решение перво й задачи позволит эффективно распознавать элементы речи из некоторого ограниченного набора, имея готовые, уже обученные модели этих элементов. В этом случае произнесенное слово оцифровывается и после сегментации на определенные элементы, например, фреймы - участки фиксированной длины, рассматривается как набор последовательностей наблюдений. Вместо непосредственно оцифрованного речевого сигнала системы распознавания речи обычно работают с неким набором признаков (меньшим по объёму), достаточно хорошо характеризующим речевой сигнал (спектральные коэффициенты, кепстральные коэффициенты, коэффициенты линейного предсказания и другие). Этот этап называется предобработкой речевого сигнала. Затем каждая последовательность наблюдений, представляющая собой неизвестное слово, проверяется на соответствие всем имеющимся в словаре моделям слов. Для этого вычисляется вероятность генерации такой последовательности наблюдений каждой из имеющихся в словаре моделей. Слово, модель которого с наибольшей вероятностью генерирует такую последовательность наблюдений, и является результатом распознавания.
Решение второй задачи позволяет выявлять «скрытую» часть модели, т.е. находить её внутренние состояния. В действительности определить ту последовательность состояний, которая имела место, невозможно, а в случае с распознаванием речи такой последовательности просто нет, поскольку считается, что модель речеобразования человека не носит стохастический характер. Тем не менее, нахождение оптимальной последовательности дает нам дополнительный критерий сравнения при поиске оптимальной модели и позволяет выявлять статистические характеристики конкретных состояний модели.
Решение третей задачи позволяет обучать модели, т.е. вычислять параметры модели так, чтобы она наилучшим образом описывала так называемые «тренировочные» последовательности. Задача тренировки моделей считается самой сложной при использовании СММ в системах распознавания, так как неизвестно единственного и универсального способа её решения, а от результата обучения моделей зависит качество работы системы распознавания. Поэтому решению этой задачи уделяется особое внимание.
До сих пор мы рассматривали только специальный случай так называемой эргоди-ческой или полносвязной СММ, в которой каждое состояние модели за один шаг может быть достигнуто из любого другого состояния. (Строго говоря, эргодическая модель обладает таким свойством, что каждое состояние может быть достигнуто из любого другого состояния за конечное число шагов). Этот тип моделей имеет то свойство, что каждый коэффициент ау матрицы вероятностей переходов положителен. Такая модель была изображена на рис. 1.2.
Для некоторых же приложений, в особенности связанных с распознаванием речи, находят применение другие типы СММ, лучше описывающие наблюдаемые свойства моделируемого речевого сигнала, чем стандартная эргодическая модель. Одна из таких моделей называется моделью слева-направо (left-right model) или моделью Бэйкиса (Bakis model), поскольку последовательность состояний, лежащая в основе модели имеет то свойство, что с течением времени индекс состояния (его порядковый номер) также увеличивается (или остаётся тем же). То есть состояния на оси времени идут слева-направо. Очевидно, что такая модель имеет желаемое свойство: она легко моделирует сигналы, свойства которых изменяются со временем, например, речь.
Ещё более частный случай СММ - частный случай моделей «слева-направо» - это модели с поступательно-ограниченными переходами. Особенность поступательно-ограниченных переходов в том, что лни могут осуществляться не более чем на заданное число состояний вперёд (часто не более чем на два, как это указано на рис. 1.4).
Основное свойство моделей «слева-направо» в том, что коэффициенты переходов удовлетворяют условию: Aij = 0,j i (1.5) То есть, переходы в состояния с индексом меньше, чем у текущего состояния, недопустимы. Кроме того, вероятности начальных состояний имеют свойство: Иначе говоря, последовательность должна начинаться с состояния 1 (и оканчиваться в состоянии N).
Хотя мы и особо выделили эргодические модели и модели «слева-направо», существует множество других типов СММ, например модель с параллельными путями (рис. 1.5). Строго говоря, это тоже модель «слева-направо», поскольку она удовлетворяет тем же условиям, но у неё есть и особенность в виде наличия двух параллельных путей. По сути, это объединение двух моделей с поступательно-ограниченными переходами.
Применительно к речи это означает, что такая СММ моделирует возможную вариативность речевого сигнала, которая может иметь место в случае работы, например, с диктором, находящимся в условиях стресса, из-за чего изменяются особенности произнесения им фонем, или при работе с несколькими дикторами, различающимися особенностями произнесения тренировочного слова, потому что в этом случае в модели есть несколько альтернативных путей для той части слова, которая произносится по-разному различными людьми или одним человеком от случая к случаю. Такая модель учитывает вышеперечисленные особенности произнесения и придаёт дополнительную гибкость использующим её приложениям.
Выше мы рассматривали только случаи моделей, когда наблюдения характеризуются дискретными символами из конечного алфавита и потому могли использовать дискретную плотность вероятности для каждого состояния модели. Однако в реальности (по крайней мере, для некоторых приложений) наблюдения являются непрерывными сигналами (или векторами). В этом случае необходимо использовать СММ с непрерывными плотностями вероятностей. Такие СММ используются при работе в системах распознавания, использующих спектральные коэффициенты или кепстральную предобработку речевого сигнала.
Общая формулировка СММ с непрерывными плотностями вероятностей применима к широкому классу задач, но существует ещё один очень интересный класс СММ, дающий хорошие результаты именно применительно к системам распознавания речи. Речь идёт об авторегрессионных СММ. Для данного типа СММ вектора наблюдений получаются из авторегрессионного процесса
Методы, основанные на математических вычислениях
Методы, основанные на математических вычислениях, сегодня изучены наиболее полно. Они подразделяются на направленные и ненаправленные.
Суть ненаправленного метода состоит в том, что локальный экстремум ищется путем решения системы уравнений, как правило, нелинейных. Эта система составляется путем приравнивания градиента целевой функции к нулю (например, метод градиентного спуска или покоординатного спуска). К недостаткам этих методов можно отнести очень жесткие условия, накладываемые на целевую функцию: она должна быть дифференцируема на всем пространстве поиска. При формализации современных задач это условие, как правило, соблюсти не удается, и аналитического решения задачи обучения СММ не известно.
Направленные методы предполагают перемещения от точки к точке в допустимой области, причем направление подобных перемещений связывается с направлением, на которое указывает градиент (например, метод касательных). Итеративная процедура Баума-Велча, предназначенная для решения задачи обучения СММ и рассмотренная в Главе 1, относится именно к этой группе методов оптимизации. Как было отмечено, эта процедура способна находить только лишь локальные экстремумы или глобальный, но только если на пути к нему по ландшафту параметров не окажется локальных экстремумов, выбраться из которых она не сможет.
Данная особенность распространяется и на всю группу этих методов - они часто находят лишь локальные экстремумы целевой функции, тогда как оптимальному решению соответствует только глобальный экстремум. Таким образом, методы поиска оптимальных решений, основанные на математических вычислениях, применимы лишь в случаях гладких, всюду дифференцируемых унимодальных (имеющих один экстремум на пространстве поиска) целевых функций.
Перечислительные методы, по сути, представляют собой полный перебор. Их смысл состоит в том, что пространство поиска любой задачи можно представить в виде совокупности дискретных точек, и этом случае поиск решения будет сводиться к перебору всех точек пространства поиска и вычислению в них целевой функции, в одной из которых она, несомненно, примет экстремальное значение. Даже если пространство поиска непрерывно, то конечная точность представления чисел в вычислительных машинах позволяет сделать такое допущение. Для наглядности этот метод можно сравнить с накладыванием на пространство поиска (в случае, если оно непрерывно) сети с выбранным фиксированным размером ячеек и дальнейшим прохождением по всем узлам этой сети.
Недостаток этих методов очевиден. При увеличении размерности пространства поиска (числа аргументов целевой функции) количество точек пространства возрастает не линейно, а значительно стремительнее. Данная проблема известна под названием «комбинаторного взрыва». Это приводит к значительным временным затратам процедуры перебора и необходимости применения все более мощной и дорогостоящей вычислительной техники. В то же время размерность решаемых сейчас задач постоянно растет, а время, доступное для принятия решений, сокращается. Таким образом, перечислительные методы также становятся применимы для решения все более сужающегося класса задач.
Так, например, для поиска оптимальной матрицы для СММ, имеющей 10 состояний, пришлось бы перебрать 10 10=100 элементов матрицы, каждый из которых может принимать значения в диапазоне от 0 до 1, с шагом равным 0,00000001 = 10"8, то есть, каждый элемент может принимать 10 значений. Такое допущение относительно шага сделано ввиду того, что значения параметров СММ в системе автоматического распознавания речи (САРР) SdiApp, разработанной на кафедре ЭВА МИЭМ, хранятся в файле словаря с точностью до восьмого знака. Для строки из этих 100 элементов число возможных комбинаций оказывается равным (10 )-10 (!). Для сравнения, считается, что в нашей Вселенной есть место для 10118 субатомных частиц [91]. Даже если крайне упростить задачу перебора и рассматривать исключительно СММ с поступательно-ограниченными переходами не более чем на 2 состояния вперёд (т.н. ленточные матрицы), то и тогда останется 3 10-3-1=26 нуждающихся в переборе элементов (вычитание в формуле появилось из-за того, что последняя строка матрицы содержит только один элемент, да и тот единичный, а предпоследняя - два значащих элемента, вместо стандартных трёх). Для этого случая число возможных комбинаций оказывается равным 108 2б=10208, что тоже явно превышает все разумные значения.
Если в дополнение ещё и радикально пожертвовать точностью представления данных и снизить её до второго знака (практическая польза подобной модели становится крайне сомнительна, так как при перемножении закодированных таким образом элементов очень сильно пострадает точность результата, что отрицательно скажется на качестве распознавания), число комбинаций станет равным 102 26=1052. Если, наконец, допустить, что в нашем распоряжении есть суперкомпьютер СКИФ-1000 мощностью 2 терафлопс (на конец 2004 года - это самый быстрый суперкомпьютер на территории бывшего СССР и 98-й по мощности суперкомпьютер в мировом рейтинге Тор500 [3]), то есть способный выполнять 2 1012 операций с плавающей точкой в секунду, и предположить, что за одну его операцию обрабатывается одна комбинация параметров или одна матрица (что, вообще говоря, далеко не так, потому что на матрицу потребуется гораздо больше операций), то на обработку всех 1052 значений матриц потребуется 1052/2 1012=5 1039 секунд, что на 22 порядка больше времени существования Вселенной, равного приблизительно 5 10 секунд или 14 миллиардов лет. В свете этих последних значений первоначальный вариант даже не поддаётся осмыслению, и сколь-нибудь полный перебор попросту невозможен.
Следует заметить, что не все матрицы, генерируемые рассматриваемой процедурой, являются допустимыми в силу невыполнения ими для отдельных строк условия полной вероятности (ф-ла 1.3), и такие матрицы должны быть отброшены. Здесь возможна оптимизация работы переборного алгоритма посредством реализации процедуры, генерирующей только допустимые с точки зрения СММ матрицы, что сократит объём вариантов для перебора алгоритмом, но этот подход не избавит от другой проблемы метода перебора - экспоненциального роста числа вариантов при увеличении размерности модели.
Построение генетического алгоритма для оптимизации процесса обучения смм тренировочными последовательностями
Первая важная задача, которую надо решить при проектировании генетического алгоритма - это задать механизм кодирования информации в хромосоме, поскольку от правильного выбора варианта кодирования зависит скорость и качество работы ГА.
Существует несколько стандартных подходов к кодированию хромосом [51]: 1) Кодирование хромосомы двоичной битовой строкой.
Параметры, подлежащие оптимизации, кодируются битовой строкой, в которой каждому параметру соответствует её определённая часть. Данный метод особенно эффективен, когда параметры имеют дискретный набор значений. Кодирование в этом случае получается весьма экономным, а генетические операторы - быстрыми и простыми. Так, например, работа оператора мутации часто сводится к инверсии одного или нескольких случайно выбранных бит в строке, а скрещивание - к объединению частей двух битовых строк или к их сложению с учётом предварительно наложенной битовой маски.
Следует заметить, что определённые наборы параметров могут быть некорректными и недопустимыми логикой самой задачи, и правильный выбор метода способен исключить такие варианты ещё на этапе кодирования хромосомы, сделав так, что недопустимым состояниям просто не будет соответствовать ни одна реальная хромосома. Наиболее просто это реализуется именно с двоичными хромосомами.
Вариацией этого метода является кодирование с использованием кодов Грэя (Gray codes) [45, 80]. Коды Грэя - это двоичные коды, особенность которых в том, что последовательные значения отличаются лишь одним битом в строке. Такое кодирование влияет на работу оператора мутации - случайная мутация имеет больше шансов привести к последовательным малым изменениям особи, но при этом и расширяет диапазон этих возможных изменений. Эта интересная возможность может быть охарактеризована так: большая часть мутаций ведёт лишь к малым последовательным изменениям, в то время как редкая мутация способна привести к действительно серьёзным изменениям и инициировать исследование алгоритмом новой области в пространстве хромосом. 2) Кодирование хромосомы символьной строкой.
Этот метод, по сути, является расширением предыдущего, и разница лишь в том, что вместо битов используются символы, принимающие больше двух возможных значений. Впрочем, есть и некоторая разница - в двоичной хромосоме для кодирования одного параметра часто используются несколько бит (как в случае кодирования целого числа), а в символьной - каждый параметр обычно кодируется своим значением символа (но можно сделать ещё один шаг и начать кодировать параметры несколькими недвоичными символами - в этом случае рассматриваемая далее аналогия с биологическими системами ещё более усилится). Это несколько, хотя и не сильно, усложняет генетические операторы и лишает разработчика алгоритма некоторых возможностей по оптимизации скорости их работы, связанных с простым представлением двоичных чисел в современных ЭВМ, зато этот метод очень гибок и легко расширяем при необходимости, если требуется увеличить число возможных значений, а сама хромосома очень наглядна.
Стоит заметить, что этим методом кодирования хромосомы часто эмулируется первый метод, когда на самом деле вместо битовой строки используется и хранится в памяти машины символьная строка, но алфавит её допускает лишь два возможных значения - "0" и "1". В случаях, когда это не вносит особых замедлений скорости работы алгоритма, такой подход оправдан большей наглядностью самой хромосомы, что в некоторых случаях может быть полезно разработчику.
Дополнительным преимуществом этого метода кодирования хромосомы является в определённом смысле его аналогичность кодированию информации в биологических системах, где ипользуется алфавит из четырёх возможных нуклеотидов: аденин, тимин, гуанин и цитозин (А, Т, Г, Ц) в ДНК, или аденин, урацил, гуанин и цитозин (А, У, Г, Ц) в РНК [18]. Упоминаемое ранее кодирование параметра несколькими недвоичными
символами близко по сути к наличию в ДНК кодонов - трёх следующих друг за другом нуклеотидов, кодирующих определённый аминокислотный остаток [18]. Таким образом, данный метод кодирования может быть полезен сторонникам создания систем, которые как можно более полно соответсвуют биологическим, а также в решении задач биологии. 3) Кодирование хромосомы вещественными числами.
Каждый параметр описывается вещественным числом, и хромосома представляет собой вектор вещественных чисел.
Минусом метода является то, что на хранение вещественных чисел требуется больше памяти, чем на хранение хромосом в одном из предыдущих вариантов. Правда, даже при размере популяции в несколько тысяч особей (например, 5000 - весьма крупная популяция) и количестве закодированных в одной хромосоме параметров в 100 (достаточно большая хромосома), при выделении на вещественное число 8 байт на хранение популяции потребуется 8 100 5000 = 4000000 байт, что при нынешнем развитии компьютерной техники не представляется значительной величиной.
Зато у этого метода есть и большие плюсы. В случае, если природа параметров такова, что они описываются именно вещественными числами (например, значения вероятностей или кепстральные коэффициенты), кодирование в двоичной хромосоме потребует их дискретизации и приведёт к неизбежной потере точности, в случае если разработчиком алгоритма будет выделено недостаточно количество бит на один параметр, а в случае использования хромосомы вещественных чисел такой проблемы не будет.
Кроме того, оперирование вещественными числами в таком случае избавляет от постоянных перекодировок параметров во время работы алгоритма из битовой формы в числовую, что положительно сказывается на скорости и надёжности работы программы.
Возможны и комбинированные методы кодирования, например, когда часть параметров кодируется вещественными числами, а часть - общей битовой строкой.
Параметры, требующие оптимизации в решаемой задаче, - это элементы матрицы вероятностей переходов (в дальнейшем просто матрицы), которые по своей природе являются вещественными числами. Кроме того, при вычислении вероятности генерации итоговой последовательности моделью происходит перемножение отдельных вероятностей, что при малой точности представления способно привести к накоплению больших ошибок и отрицательно сказаться на качестве распознавания. В силу вышеперечисленного кодирование хромосомы вещественными числами является оправданным.
Показатели эффективности генетических алгоритмов
Основным способом повышения скорости работы генетических алгоритмов является распараллеливание [95]. Причем этот процесс можно рассматривать с двух позиций. Распараллеливание может осуществляться на уровне организации работы генетического алгоритма и на уровне его непосредственной реализации на вычислительной машине.
На уровне непосредственной реализации ГА используется следующая особенность генетических алгоритмов. В процессе работы многократно приходится вычислять значения целевой функции для каждой особи, осуществлять преобразования оператора скрещивания и мутации для нескольких пар родителей и т. д. Все эти процессы могут быть реализованы одновременно на нескольких параллельных системах или процессорах, что пропорционально повысит скорость работы алгоритма.
Алгоритм требует достаточно большого количества вычислений, но в то же время не требуется его работа в реальном времени, поскольку процесс оптимизации моделей слов в системе может быть запущен во времена её простоя или проводиться отдельным процессом в фоновом режиме параллельно основной работе системы распознавания. Кроме того, работа генетического алгоритма может быть распараллелена, в том числе между различными машинами в сети, что является весьма интересным дальнейшим шагом в развитии системы в перспективе.
На уровне организации работы ГА применяется структурирование популяции решений на основе одного из двух подходов:
1) Популяция разделяется на несколько различных подпопуляций (демосов), которые впоследствии развиваются параллельно и независимо. То есть скрещивание происходит только между членами одного демоса. На каком-то этапе работы происходит обмен частью особей между подпопуляциями на основе случайной выборки. И так может продолжаться до завершения работы алгоритма. Данный подход получил название концепции островов (island model) [43,94].
2) Для каждой особи устанавливается ее пространственное положение в популяции. Скрещивание в процессе работы происходит между ближайшими особями. Такой подход получил название концепции скрещивания в локальной области (cellular genetic algorithms) [94]. Оба подхода, очевидно, также могут эффективно реализовываться на параллельных вычислительных машинах, что даёт хорошие перспективы использованию ГА в контексте современных тенденций развития аппаратных средств систем распознавания. Кроме того, практика показала, что структурирование популяции приводит к повышению эффективности генетического алгоритма даже при использовании традиционных вычислительных средств [19].
Еще одним средством повышения скорости работы является кластеризация [62]. Суть ее состоит, как правило в двухэтапной работе генетического алгоритма. На первом этапе генетический алгоритм работает традиционным образом с целью получения популяции более «хороших» решений. После завершения работы алгоритма из итоговой популяции выбираются группы наиболее близких решений. Эти группы в качестве единого целого образуют исходную популяцию для работы генетического алгоритма на втором этапе. Размер такой популяции будет, естественно, значительно меньше, и, соответственно, алгоритм будет далее осуществлять поиск значительно быстрее. Сужения пространства поиска в данном случае не происходит, поскольку применяется исключение из рассмотрения только ряда очень похожих особей, существенно не влияющих на получение новых видов решений.
Устойчивость или способность генетического алгоритма эффективно формировать лучшие решения зависит в основном от принципов работы генетических операторов (операторов отбора, скрещивания, мутации и редукции). Вычислительная эффективность этого процесса была рассмотрена при обсуждении теоремы схем в разделе 2.6. Рассмотрим механизм этого воздействия подробнее.
Как правило, диапазон влияния можно оценить, рассматривая вырожденные случаи генетических операторов.
Вырожденными формами операторов скрещивания являются, с одной стороны, точное копирование потомками своих родителей, а с другой, порождение потомков, в наибольшей степени отличающихся от них.
Преимуществом первого варианта является скорейшее нахождение лучшего решения, а недостатком, в свою очередь, тот факт, что алгоритм не сможет найти решения лучше, чем уже содержится в исходной популяции, поскольку в данном случае алгоритм не порождает принципиально новых особей, а лишь копирует уже имеющиеся. Чтобы все-таки использовать достоинства этой предельной формы операторов скрещивания в реальных генетических алгоритмах, применяют элитизм, речь о котором шла в главе 2.
Во втором случае алгоритм рассматривает наибольшее число различных особей, расширяя область поиска, что, естественно, приводит к получению более качественного результата. Недостатком в данном случае является значительное замедление поиска. Одной из причин этого, в частности, является то, что потомки, значительно отличаясь от родителей, не наследуют их полезных свойств.
В качестве реальных операторов скрещивания используются промежуточные варианты. В частности, родительское воспроизводство с мутацией и родительское воспроизводство с рекомбинацией и мутацией. Родительское воспроизводство означает копирование строк родительских особей в строки потомков. В первом случае после этого потомки подвергаются воздействию мутации. Во втором случае после копирования особи-потомки обмениваются подстроками (то есть происходит кроссовер или рекомбинация). После рекомбинации потомки также подвергаются воздействию мутации. Последний подход получил наибольшее распространение в области генетических алгоритмов. Наиболее распространенными при этом являются одноточечный, двухточечный и равномерный операторы скрещивания.
Основным параметром оператора мутации является вероятность его воздействия. Обычно она выбирается достаточно малой, чтобы, с одной стороны, обеспечивать расширение области поиска, а с другой, не привести к чересчур серьезным изменениям потомков, нарушающим наследование полезных параметров родителей. Сама же суть воздействия мутации обычно определяется фенотипом и на эффективность алгоритма особого воздействия не оказывает.
Эксперименты на разработанном автором программно-аппаратном комплексе «Иволга» показали, что для решения задачи оптимизации СММ одиночные мутации с низкой вероятностью малоэффективны. Это обусловлено большим размером хромосомы, кодирующей матрицу вероятностей переходов скрытой марковской модели, и тем, что
такие мутации затрагивают лишь малую часть модели. Иначе говоря, работа случайной составляющей в генетическом алгоритме недостаточна и является ограничивающим фактором для всего алгоритма в целом. Устранение этого узкого места способно привести к общему повышению эффективности алгоритма.
Выполненное автором сравнение результатов для одноточечного оператора мутации и для многострочного в третьей главе (рис, 3.7) показало, что многоточечный оператор при малой вероятности мутации (порядка 0.05-0.1) эквивалентен одноточечному оператору при высокой вероятности его применения (0.9-0.95). При увеличении вероятности его применения ГА становится неустойчивым, поскольку значительная часть хороших решений разрушаются этим оператором в соответствии с теоремой схем.
