Главная
Коллекция "Otherreferats"
Программирование, компьютеры и кибернетика
Скрытые марковские модели
Скрытые марковские модели
Применение скрытых марковских моделей для распознавания текстов, основные вопросы их проектирования. Переход к скрытым марковским моделям, пример шариков в вазах. Математическое описание скрытой марковской модели. Алгоритмы прямого и обратного хода.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 07.04.2011 |
| Размер файла | 1,6 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
“ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ”
Факультет компьютерных наук
Кафедра информационных систем
Курсовая работа
Скрытые Марковские процессы
230201 Информационные системы и технологии
Студент Е.В. Голова, 4 курс, д/о
Руководитель А.А. Жижелев, к. э. н., ассистент
Воронеж 2011
Содержание
- Введение
- Марковские процессы
- Переход к скрытым марковским моделям
- Пример шариков в вазах
- Математическое описание скрытой марковской модели
- Три основных задачи СММ
- Решение трех задач СММ
- Алгоритмы прямого и обратного хода
- Решение второй задачи
- Заключение
- Список литературы
Введение
При наблюдении за каким-либо процессом, первоначально регистрируется его проявление, с помощью датчиков воспринимаются сигналы, порождаемые этим процессом. Проявления процесса обычно подвержены шумам и искажениям, не позволяющим получить информацию об источнике сигнала и описать процесс, породивший этот сигнал. Для описания подобных систем создаются стохастические модели. В настоящей работе рассмотрен один из типов стохастических моделей сигнала - скрытые марковские модели.
В основе построения такой модели лежит допущение о том, что сигнал может быть описан случайным процессом, параметры которого могут быть определены конкретным способом. Основы этой теории были опубликованы в статьях Баума и его коллег в конце 60-х - начале 70-х годов, а в 70-х годах ее результаты были применены для распознавания данных. До середины 80-х годов теория широко не была известна, поскольку была опубликована в математических журналах, которые не читались инженерами, работающими в области распознавания. Популярность теории значительно возросла лишь после выхода ряда статей, содержащих вводно-методический материал и советы по правильному применению теории в задачах распознавания. Особую популярность имели статьи Рабинера [1], на которую ссылаются практически все публикации о СММ.
В 90-х годах СММ начинают применяться для распознавания печатного и рукописного текстов. Теория получила развитие для случая, когда необходимо описать двумерный сигнал - изображение, такой вид моделей называют псевдодвумерные скрытые марковские модели и применяются для инвариантного распознавания символов различных шрифтов, отличающихся нелинейным искажением формы, а также для поиска лиц на фотографиях.
скрытая марковская модель алгоритм
Рассмотрим скрытые марковские модели и их применение в отдельных аспектах распознавания речи.
Происходящие явления можно описывать как сигналы. Сигналы могут быть дискретными, как письменная речь, или непрерывными, как фонограмма или кардиограмма. Сигналы с постоянными статистическими свойствами называются стабильными (стационарными), а с меняющимися - нестабильными (нестационарными). Сигнал может быть чистым, а может и искаженным, с помехами или посторонними сигналами.
Для описания сигналов часто нужны математические модели. В модели сигнала на основе его характеристик может быть предусмотрен определенный механизм обработки, который позволяет получить желаемый выход при анализе сигнала. Например, если надо облагородить сигнал, искаженный и зашумлённый при передаче, мы можем смоделировать его и рассмотреть эту модель отвлечённо от искажений и шумов в сигнале.
Модели позволяют также генерировать и исследовать сигнал без его источника. В этом случае, имея под рукой хорошую модель, мы можем имитировать сигнал и изучить его по этой имитации.
Модели очень успешно применяются на практике, позволяя создавать эффективные рабочие системы: системы прогноза, распознавания, идентификации. Грубо все модели можно разделить на детерминистические и статистические. Детерминистические используются, если известны фундаментальные характеристики сигнала: что сигнал - это синусоидальная волна или, например, сумма экспонент. В таком случае достаточно просто описать подобную модель сигнала - для этого нужно всего лишь подобрать (вычислить) параметры этой модели: для синусоидальной волны - это амплитуда, частота, фаза. Второй класс - это статистические модели, которые, в соответствии со своим названием, используют в качестве основы статистические характеристики сигнала. Эти модели описывают гауссовы, пуассоновские, марковские процессы, а также подобные им процессы. В общем, статистические модели описывают сигнал как определенный случайный процесс, параметры которого могут быть качественно определены.
В области распознавания речи используются оба типа моделей, но рассмотрим мы только одну статистическую модель, а именно - скрытую марковскую модель (СММ).
Для успешного понимания СММ необходимо для начала рассмотреть скрытые марковские цепи. Далее от марковских цепей перейдем к скрытым марковским моделям и к трем главным вопросам проектирования СММ. Покажем, что эти три главных вопроса решаемы. А спроектированную СММ мы сможем применить в области распознавания речи.
Марковские процессы
Рассмотрим систему, которую в любой момент времени можно описать одним из состояний, , для примера .
Через определенный промежуток времени система может изменить свое состояние или остаться в прежнем состоянии согласно вероятностям, указанным для данных состояний. Моменты времени, когда мы регистрируем состояние системы, обозначим как а состояние в момент времени мы обозначим . Полное описание рассмотренной выше системы должно содержать текущее состояние (в момент времени ) и последовательность всех предыдущих состояний, через которые прошла система. В отдельных случаях описание системы сводится к указанию текущего и предыдущего состояния, т.е.
(1.1)
Кроме того, мы также полагаем что процессы, протекающие в системе, не зависят от времени, о чем нам говорит правая часть формулы (1.1). Таким образом, систему можно описать матрицей вероятностей в виде
(1.2)
где - это вероятность перехода из состояния в состояние в данный момент времени. Поскольку эти вероятности характеризуют случайный процесс, они имеют обычные свойства, т.е.
(1.3)
Описанный выше случайный процесс можно назвать открытой марковской моделью, поскольку выходной сигнал модели - это последовательность состояний регистрируемых во времени. Каждое состояние соответствует определенному (наблюдаемому) событию.
Теперь рассмотрим простую марковскую модель погоды, у которой будет всего три состояния. Предполагается, что мы один раз в день (например, в полдень), смотрим в окно и регистрируем в журнале текущее состояние погоды. Мы условились, что лишь одно из трех ниженазванных состояний в день мы записываем в журнал:
· Состояние №1: дождь (или снег)
· Состояние №2: пасмурно
· Состояние №3: ясно
Матрица вероятностей изменения погоды имеет вид
(1.4)
Так как погода в первый день () ясная (состояние 3), мы можем задать себе вопрос: какова вероятность (согласно нашей модели), что следующие 7 дней будет именно "ясно - ясно - ясно - дождь - дождь - ясно - пасмурно - ясно"? Точнее сказать, для данной последовательности состояний , где соответствует, мы хотим на основе данной модели определить вероятность наблюдения последовательности . Эта вероятность может быть выражена (и вычислена) следующим образом
(1.5)
где - это вероятность того, что начальное состояние системы будет .
Есть и другой интересный вопрос, ответ на который нам даст эта модель: какова вероятность того, что модель сохранит свое состояние в течение ровно дней? Эта вероятность может быть вычислена как вероятность наблюдения следующей последовательности
дает модель, в которой
(1.6)
Величина - это вероятность того, что система будет находиться в состоянии ровно раз подряд. Соответственно, есть функция распределения вероятности для продолжительности пребывания системы в одном состоянии, которая является характеристикой сохранения состояния для марковской цепи. Зная величины мы можем вычислить среднее время, в течение которого система сохранит свое состояние (используем формулу математического ожидания):
(1.7)
(1.8)
Ожидается, что солнечная погода вероятнее всего простоит дней, пасмурная - 2.5 дня, а вот дождливая погода, согласно нашей модели, вероятнее всего продержится 1.67 дня.
Переход к скрытым марковским моделям
В вышеописанной марковской модели каждому физическому явлению соответствовало определенное состояние модели. Эта модель несколько ограничена и ей не под силу решение многих актуальных проблем. Рассмотрим в этом разделе марковские модели. В данном случае модель (скрытая марковская модель) - это результат двух случайных процессов. Первый - скрытый процесс - его никак нельзя зарегистрировать, но его можно охарактеризовать с помощью другого случайного процесса, который предоставляет нам набор сигналов - наблюдаемую последовательность. Проиллюстрируем это описание на примере работы супервайзера в рекламном агентстве.
Пример работы супервайзера
Допустим, что в некотором рекламном агентстве разработана система наблюдения за промоутерами. Полагаем, что руководителю группы промоутеров - супервайзеру требуется объехать промоутеров и убедиться, что они на рабочих местах. Свой отчет супервайзер передает в отдел кадров.
Супервайзер не указывает, в каком порядке он посещал промоутеров, неизвестно также, проверял ли он их вообще. Он представляет отчет, содержащий следующую информацию:
1. Промоутер на работе.
2. Промоутер не на работе.
Физически представим это так. Супервайзер каким либо случайным образом выбирает промоутера для проверки. Результат проверки (наличие промоутера на рабочем месте) записывает в отчет. Потом супервайзер выбирает следующего промоутера, едет к нему, и так далее. В результате мы получаем последовательность проверок - результат работы СММ - наблюдаемую последовательность.
В этом и заключается суть скрытого процесса (вы не знаете, что происходит с супервайзером и промоутерами), когда о процессе вы можете судить лишь по наблюдаемой последовательности
(2.1)
где - это номер проверяемого промоутера, - это промоутер на работе, - это промоутер не на работе.
Как же построить скрытую марковскую модель, соответствующую этой ситуации? Первый вопрос: сколько состояний будет у модели и что означает каждое состояние такой модели?
Предположим, что супервайзер наблюдает только за одним промоутером , обозначим этого промоутера как , и других у него нет. Тогда выбор мы остановим на модели с двумя возможными состояниями , где состояние означает, что промоутер на работе, - что не на работе.
В этом случае марковская модель является открытой и единственное, что мы можем сделать с этой моделью - это оптимизировать вероятность смены состояния.
Следует заметить, что скрытая марковская модель в данном случае будет представлять собой модель одного состояния, которое соответствует единственному промоутеру. Неизвестным параметром здесь будет факт его присутствия на работе, выраженный через вероятность его присутствия в наблюдаемой последовательности супервайзера.
Таким образом, для случая наблюдения супервайзера за одним промоутером можно сказать, что СММ (именно скрытая, а не открытая) имеет одно состояние (один промоутер). Выходной алфавит содержит 2 элемента (множество наблюдаемых значений) - промоутер на работе и промоутер не на работе. Взаимно-однозначного соответствия между промоутером (например, его порядковым номером) и выходным алфавитом - нет, значит, модель является скрытой.
Далее рассмотрим модель двух состояний. Пусть супервайзер в течение дня наблюдает за двумя промоутерами, т.е. Обозначим первого и второго промоутера как и соответственно (в этом случае модель имеет два состояния, которые соответствуют двум различным промоутерам N = 2).
Каждому состоянию соответствует распределение вероятностей между состояниями на работе и не на работе, а также матрицей вероятностей переходов (матрицей переходов) - , указывающей вероятность перехода из одного состояния в другое. Переход из состояния в состояние согласно заданным вероятностям из матрицы переходов осуществляется на основе той же проверки промоутеров или на основе любого другого случайного события.
Предположим, что результатом работы супервайзера с двумя промоутерами за неделю стала последовательность , которую супервайзер в виде отчета сдает в отдел кадров.
Таким образом, выходной алфавит также содержит 2 значения ( и ). Взаимно однозначного соответствия между выходным алфавитом и состоянием нет, поэтому модель является скрытой. Это объясняется тем, что по результатам отчета, представленного супервайзером (последовательность ), нельзя говорить о том, какой именно промоутер на работе или не на работе.
В данном случае , .
Пример шариков в вазах
Сейчас мы дополним СММ новыми структурными элементами, для того чтобы она могла решать ряд более сложных задач. Поможет нам в этом пример с шариками в вазах (рис.1).
Рис.1. Модель с N состояниями (вазами) и шариками, цвета которых обозначают элементы наблюдаемой последовательности.
Покажем, как модель может порождать последовательность на примере выбора шариков из ваз. На первом шаге выбираем исходное состояние в соответствии с распределением вероятностей р и выбираем объект (это будет шарик цвета с вероятностью .
Далее переходим в какое-то состояние в соответствии с вероятностью (переходим к вазе номер ). В этом состоянии выбираем объект (выбираем - шарик цвета с вероятностью . Выполнив Т шагов описанного процесса, построим последовательность , которая и есть наблюдаемая последовательность.
Рис.2 Марковская модель, которая может быть использована для моделирования результатов экспериментов для примера ваз с шариками.
При этом последовательность состояний S, в которых производился выбор объектов, нас не интересует. Этим и объясняется название "скрытая" модель Маркова - последовательность состояний от нас "скрыта". Модель является "черным ящиком" - после выполнения заданного количества шагов она выдает некую последовательность .
Таким образом, множество состояний в данном примере - это номера ваз, из которых мы выбираем шарик. Соответственно общее количество состояний равно количеству ваз.
Математическое описание скрытой марковской модели
Приведенные выше примеры дают представление о СММ, и о возможных сферах их применения. Далее определим СММ следующими элементами:
- общее количество состояний в модели. Несмотря на то, что состояния в СММ являются скрытыми, во многих случаях есть соответствие между состоянием модели и реальным состоянием процесса. В примере с работой супервайзера состояние системы соответствовало выбранному для проверки промоутеру, а в примере с шариками в вазах состояние модели соответствовало выбранной вазе. В общем, переход в любое выбранное состояние возможен из любого состояния всей системы (в том числе и само в себя); с другой стороны, и это мы увидим впоследствии, лишь определенные пути переходов представляют интерес в каждой конкретной модели. Обозначим совокупность состояний модели множеством
, а текущее состояние в момент времени как .
1. , количество возможных символов в наблюдаемой последовательности, размер алфавита наблюдаемой последовательности. В случае с промоутером - это 2 символа: на работе и не на работе; в случае с шариками - это количество цветов шариков. Алфавит наблюдаемой последовательности мы обозначим как .
2. Матрица вероятностей переходов (или матрица переходов)
, где , (2.4)
т.е. это вероятность того, что система, находящаяся в состоянии , перейдет в состояние . Если для любых двух состояний в модели возможен переход из одного состояние в другое, то > 0 для любых . В остальных СММ для некоторых у нас вероятность перехода = 0.
3. Распределение вероятностей появления символов в - том состоянии,
, где ,, (2.5)
- вероятность того, что в момент времени t, система, находящаяся в -ом состоянии (состояние ), выдаст -тый символ (символ ) в наблюдаемую последовательность.
4. Распределение вероятностей начального состояния , где , (2.6)
т.е. вероятность того, - это начальное состояние модели.
Совокупность значений ,, и р - это скрытая марковская модель, которая может сгенерировать наблюдаемую последовательность
(2.7)
где - один из символов алфавита , а - это количество элементов в наблюдаемой последовательности.
СММ строит наблюдаемую последовательность по следующему алгоритму:
Выбираем начальное состояние в соответствии с распределением р. Устанавливаем .
Выбираем в соответствии с распределением в состоянии ().
Переводим модель в новое состояние в соответствии с матрицей переходов с учетом текущего состояния .
Устанавливаем время ; возвращаемся к шагу 3, если ; иначе - заканчиваем выполнение. Подводя итог, заметим, что полное описание СММ состоит из двух параметров модели (), описания символов наблюдаемой последовательности и трех массивов вероятностей - , и р. Для удобства мы используем следующую запись для обозначения достаточного описания параметров модели
. (2.8)
Три основных задачи СММ
Согласно описанию скрытой марковской модели, изложенному в предыдущем разделе, существует три основных задачи, которые должны быть решены для того, чтобы модель могла успешно решать поставленные перед ней задачи. В книге [7] дается следующее определение трем задачам.
Задача 1
Дано: наблюдаемая последовательность и модель
Необходимо вычислить вероятность | л) - вероятность того, что данная наблюдаемая последовательность построена именно для данной модели.
Задача 1 - это задача оценки модели, которая заключается в вычислении вероятности того, что модель соответствует заданной наблюдаемой последовательности. К сути этой задачи можно подойти и с другой стороны: насколько выбранная СММ соответствует заданной наблюдаемой последовательности. Такой подход имеет большую практическую ценность. Например, если у нас стоит вопрос выбора наилучшей модели из набора уже существующих, то решение первой задачи дает нам ответ на этот вопрос.
Задача 2
Дано: наблюдаемая последовательность и модель Необходимо подобрать последовательность состояний системы , которая лучше всего соответствует наблюдаемой последовательности, т.е. "объясняет" наблюдаемую последовательность.
Задача 2 - это задача, в которой мы пытаемся понять, что же происходит в скрытой части модели, т.е. найти "правильную" последовательность, которую проходит модель. Совершенно ясно, что абсолютно точно нельзя определить эту последовательность. Здесь можно говорить лишь о предположениях с соответственной степенью достоверности. Тем не менее, для приближенного решения этой проблемы мы обычно будем пользоваться некоторыми оптимальными показателями, критериями. Далее мы увидим, что, к сожалению, не существует единого критерия оценки для определения последовательности состояний. При решении второй задачи необходимо каждый раз принимать решение о том, какие показатели использовать. Данные, полученные при решении этой задачи, используются для изучения поведения построенной модели, нахождения оптимальной последовательности её состояний, для статистики и т.п.
Задача 3
Подобрать параметры моделитаким образом, чтобы максимизировать
Решение задачи 3 состоит в оптимизации модели таким образом, чтобы она как можно лучше описывала реальную наблюдаемую последовательность. Наблюдаемая последовательность, по которой оптимизируется СММ, принято называть обучающей последовательностью, поскольку с помощью нее мы "обучаем" модель. Задача обучения СММ - это важнейшая задача для большинства проектируемых СММ, поскольку она заключается в оптимизации параметров СММ на основе обучающей наблюдаемой последовательности, т.е. создается модель, наилучшим образом описывающая реальные процессы.
Система, предназначенная для распознавания речи
Для лучшего понимания рассмотрим все вышесказанное на примере системы, предназначенной для распознавания речи, приведенном в [6]. Для каждого слова из словаря мы спроектируем СММ с состояниями. Каждое слово, в частности, мы представим как последовательность спектральных векторов. Обучение мы будем считать завершенным, когда модель с высокой точностью будет воспроизводить ту самую последовательность спектральных векторов, которая использовалась для обучения модели.
Таким образом, каждая отдельная СММ будет обучаться воспроизводить какое-либо одно слово, но обучать эту модель следует на нескольких вариантах произнесения этого слова. Т.е. например три человека (каждый по-своему) проговаривают слово "собака", а затем каждое сказанное слово конвертируется в упорядоченный по времени набор спектральных векторов, и модель обучается на основе этих трех наборов. Для каждого отдельного слова проектируются соответствующие модели.
В начале, решается 3-я задача СММ: каждая модель настраивается на "произнесение" определенного слова из словаря , согласно заданной точности. Для того чтобы интепретировать каждое состояние спроектированных моделей мы решаем 2-ую задачу, а затем выделяем те свойства спектральных векторов, которые имеют наибольший вес для определенного состояния. Это момент тонкой настройки модели. А уже после того, как набор моделей будет спроектирован, оптимизирован и обучен, следует оценить модель на предмет ее способности распознавать слова в реальной жизни. Здесь мы уже решаем 1-ую задачу СММ. Нам дается тестовое слово, представленное, разумеется, в виде наблюдаемой последовательности спектральных векторов. Далее мы вычисляем функцию соответствия этого тестового слова для каждой модели. Модель, для которой эта функция будет иметь наибольшее значение, будет считаться моделью названного слова.
В следующем разделе мы дадим четкое формальное решение трем задачам СММ.
Решение трех задач СММ
Решение первой задачи
Нам необходимо вычислить вероятность того, что последовательность наблюдений принадлежит модели л, т.е. вычислить . В первую очередь в голову приходит решение подсчитать вероятность появления последовательности наблюдений для каждой возможной последовательности состояний модели. Рассмотрим такой способ на примере одной последовательности состояний
(3.1)
где - это начальное состояние модели. Вероятность появления последовательности наблюдений для последовательности состояний (3.1) равна
(3.2)
где мы подразумеваем статистическую независимость наблюдений. Отсюда получаем
(3.3)
Вероятность, что в модели состояния пройдут последовательность , равна
(3.4)
Вероятность совмещения и , т.е. вероятность одновременного их проявления, выражается произведением
(3.5)
Вероятность появления - это сумма вероятностей совмещения (3.5) по всем возможным комбинациям состояний системы:
(3.6)
Объяснить это можно так. В момент времени мы выбираем начальное состояние в соответствии с вероятностью, и генерируем символ (в этом состоянии) с вероятностью . Далее переходим к следующему моменту времени и выполняем переход в состояние с вероятностью ; после чего генерируем символ с вероятностью . Этот процесс повторяется, пока мы не достигнем времени . В итоге мы переведем систему из состояния в с вероятностью и сгенерируем символ с вероятностью .
Следует отметить, что прямое вычисление по формуле (3.6) требует произвести порядка вычислений, поскольку для каждого времени существует возможных состояний системы, т.е. возможных вариантов последовательности состояний; и для каждого варианта около вычислений - для каждого слагаемого суммы в формуле (3.6). Скажем, что нам необходимо произвести умножений и сложений. Подобные вычисления невыполнимы даже для малых значений и ; т.е. для (состояний), (наблюдений) количество вычислений будет порядка !
Ясно, что для решения 1-ой задачи СММ требуется гораздо более эффективный алгоритм. Существуют даже два таких алгоритма и называются они алгоритм прямого хода и алгоритм обратного хода. Рассмотрим алгоритм, описанный в статье [5].
Алгоритмы прямого и обратного хода
Введем прямую переменную и определим ее как
(3.7)
т.е. вероятность того что для заданной модели л к моменту времени наблюдалась последовательность , и в момент система находится в состоянии . Значение мы можем найти методом индукции по следующему алгоритму:
1) Инициализируем:
(3.8)
2) Определяем шаг индукции:
(3.9)
3) Когда дойдем до шага , подсчитаем то, что нам нужно:
(3.10)
Рис.3. (a) Пример последовательности операций, необходимых для вычисления прямой переменной ; (b) реализация вычислений с помощью решетки наблюдений и состояний .
На шаге 1 подсчитываются вероятности совмещения состояния и первого наблюдения . Индукция является центральной частью вычисления; её схема показана на рис.3 (а). На этой схеме видно, каким путем система в момент времени приходит в состояние из возможных состояний предыдущего момента времени. Поскольку - совмещенная вероятность проявления наблюдений и нахождения системы в состоянии в момент времени .
Вычисление прямой вероятности в действительности основано на использовании решетчатой структуры, показанной на рис.3 (b). Основная идея состоит здесь в том, что поскольку существует только возможных различных состояний модели, то все возможные последовательности состояний (независимо от длины последовательности наблюдений) должны сливаться в этих узлах. Для начального момента времени (первая метка времени на решетке) необходимо вычислить , . Для момента времени необходимо вычислить , , причем при каждом таком вычислении используются только предыдущих значений , так как в каждый из узлов решетки можно попасть из каждого такого же узла, но относящегося к предыдущему моменту времени.
Решение второй задачи
Алгоритм Витерби
Вторая задача СММ требует найти "оптимальную" последовательность состояний при условии данной модели и данной последовательности наблюдений. Наиболее эффективным способом решения данной задачи является алгоритм Витерби [3].
Допустим, у нас есть последовательность наблюдений
= , и мы хотим проверить ее правильность.
Идея состоит в нахождении последовательности которая максимально точно соответствовала бы .
, где - может принимать любые допустимые значения в данной модели.
Кроме того, пусть - распределение априорной вероятности всех последовательностей наблюдений. Вероятность корректного сопоставления последовательности наблюдений и максимизируется, выбирая ту последовательность наблюдений, у которой есть максимальная апостериорная вероятность или так называемое MAP (maximum a posteri)
Необходимо учесть, что использование алгоритма Витерби для марковских процессов предполагает наличие процесса со следующими характеристиками:
конечное состояние, т.е. число должно быть конечно,
дискретное время,
последовательность наблюдений зависит только от вероятности предыдущей последовательности переходов.
Из правила Байеса [8]:
. (3.11)
Теперь, когда не зависит от последовательности , мы должны только максимизировать дискриминантную функцию
. (3.12)
Сделаем следующие предположения:
Размер последовательности наблюдений не является очень большим. Пусть будет равным размеру слова, тогда - частота возникновения слова.
Форма символа, которая генерирует данный характеристический вектор, не зависит от формы соседних символов и, поэтому, зависит только от рассматриваемого символа.
(3.13)
Для случая алгоритма Витерби, если мы предполагаем, что процесс - цепь Маркова 1-го порядка, тогда (3.13) уменьшается до:
(3.14)
Чтобы понять, как алгоритм Витерби находит кратчайший путь, представим процесс маркова в виде диаграммы состояний - рис.4. В этой диаграмме узлы представляют собой состояния, а стрелки переходы, и со временем процесс проделывает некоторый путь из состояния в состояние в диаграмме состояний.
Рис.4. Диаграмма состояний
Теперь представим тот же процесс в виде решетчатой диаграммы - треллиса (рис.5).
В треллисе каждому узлу соответствует состояние в установленный момент времени, а каждая стрелка представляет собой переход к некоторому новому состоянию в следующий момент времени. Треллис начинается и заканчивается состояниями и .
Его важнейшее свойство заключается в том, что к каждой возможной последовательности состояний соответствует уникальный путь через треллис и наоборот.
Рис.5. Решетчатая диаграмма - треллис
Теперь предположим, что мы присваиваем каждому пути длину пропорциональную
Так как является монотонной функцией и есть взаимно-однозначное соответствие между путями последовательности, мы должны найти путь, чей минимален. Это даст нам последовательность состояний, для которых максимален, другими словами мы вернулись к проблеме, которую хотели решить. Полная длина пути, соответствующего некоторой последовательности состояний ,
(3.15)
где является связанной длиной каждого перехода от до .
Самый короткий отрезок пути вызывает уцелевший, соответствующий узлу , и обозначается Для времени , есть всех уцелевших, по одному для каждого . Значит, самый короткий путь должен начинаться с одного из этих уцелевших. Таким образом, в течение всего времени мы должны помнить только уцелевших и соответствующие им длины. Чтобы получить время , мы должны расширить все время на одну единицу измерения времени, вычислить длины расширенных отрезков пути для каждого узла в соответствующее время Рекурсия продолжается до тех пор, пока число уцелевших не превысит . Этот алгоритм представляет собой простую версию прямого динамического программирования.
Проиллюстрируем это примером, который включает треллис с четырьмя состояниями, покрывающий пять единиц измерения времени.
Рис.6 Треллис с четырьмя состояниями, покрывающий пять единиц измерения времени.
5 рекурсивных шагов, которыми алгоритм определяет кратчайший путь от начального до заключительного узла, показывает следующий рисунок. На каждом шаге запоминаются только 4 (или меньше) уцелевших, вместе с их длинами.
В общем виде алгоритм Витерби выглядит следующим образом:
1) Инициализация:
- индекс времени
2) Рекурсия:
На всех переходах
Вычислить:
для всех .
Найти
Для каждого
Запоминать и аналогично для
Повторять до
Для конечной последовательности алгоритм завершится в момент времени с кратчайшим решением для
Обобщенный алгоритм Витерби для оценивания скрытых марковских процессов характеризуется высокой точностью оценивания и хорошим быстродействием.
Решение третьей задачи
Алгоритм Баума - Велша
Алгоритм Баума - Велша, приведенный в статье [4] используется для нахождения неизвестных параметров скрытой марковской модели. В рамках CMM есть два независимых утверждения, обеспечивающих сходимость данного алгоритма:
1. -я скрытая переменная при известной () - ой переменной, независима от всех предыдущих переменных, то есть
2. е известное наблюдение зависит только от t-го состояния, то есть не зависит от времени,
Далее будет предложен алгоритм "максимальной правдоподобности" для поиска максимальной вероятностной оценки параметров скрытой модели маркова при заданном наборе наблюдений. Этот алгоритм так же известен как алгоритм Баума - Велша.
- это дискретная случайная переменная, принимающая одно из значений (). Будем полагать, что данная модель Маркова, определенная как , однородна по времени, то есть независима от . Тогда можно задать как независящую от времени стохастическую матрицу перемещений . Особый случай для времени определяется начальным распределением .
Будем считать, что мы в состоянии в момент времени , если . Последовательность заданных состояний определяется как , где является состоянием в момент .
Наблюдение может иметь одно из возможных значений,
. Вероятность заданного вектора наблюдений в момент времени для состояния определяется как
( - это матрица на ). Заданная последовательность наблюдений выражается как .
Следовательно, мы можем описать скрытую модель Маркова с помощью
. При заданном векторе наблюдений алгоритм Баума - Велша находит . л максимизирует вероятность наблюдений .
Вот так работает алгоритм Баума - Велша:
Исходные данные: со случайными начальными условиями.
Алгоритм итеративно обновляет параметр до схождения в одной точке.
Прямая процедура
Определим , что является вероятностью получения заданной последовательности для состояния в момент времени .
можно вычислить рекурсивно:
1. ; (3.16)
2. . (3.17)
Обратная процедура:
Данная процедура позволяет вычислить вероятность конечной заданной последовательности при условии, что мы начали из исходного состояния , в момент времени
Можно вычислить :
1. ;
2. .
Используя и можно вычислить следующие значения:
(3.18)
(3.19)
Имея и , можно определить:
(3.20)
Заключение
В данной работе приведены сведения о скрытых марковских моделях, основных задачах, их решениях и алгоритмов их реализации, а именно:
Скрытая марковская модель (СММ) - статистическая модель, имитирующая работу процесса, похожего на марковский процесс с неизвестными параметрами, и задачей ставится нахождение неизвестных параметров на основе наблюдаемых. Полученные параметры могут быть использованы в дальнейшем анализе, например, для распознавания образов.
В обычной марковской модели состояние видимо наблюдателю, поэтому вероятности переходов - единственный параметр. В скрытой марковской модели мы можем следить лишь за переменными, на которые оказывает влияние данное состояние. Каждое состояние имеет вероятностное распределение среди всех возможных выходных значений. Поэтому последовательность символов, сгенерированная СММ, даёт информацию о последовательности состояний.
Основное применение СММ получили в области распознавания речи, письма, движений и биоинформатике.
Существуют три основных задачи, связанные с СММ:
1. Даны параметры модели и последовательность, требуется вычислить вероятность появления данной последовательности (задача решается с помощью алгоритма вперёд - назад),
2. Даны параметры модели, требуется определить наиболее подходящую последовательность скрытых узлов, наиболее точно описывающую данную модель (алгоритм Витерби помогает при решении данной задачи),
3. Дана выходная последовательность (или несколько), требуется "потренировать" СММ на данном выходе (в этом помогает алгоритм Баума-Велша).
Список литературы
1. Рабинер Л.Р. Скрытые Марковские модели и их применение в избранных приложения при распознавании речи. М.: ТИИЭР, т.77, №2, февраль 1989 - с. 20-86.
2. Елинек Ф., 1976. Распознавание непрерывной речи статическими методами. М.: ТИИЭР 64, №4, с.131-160.
3. Форней Г.Д., Алгоритм Витерби. М.: IEEE, т.61, №3, с.268-276, 1973
4. Мосс Л., Алгоритм Баума - Вейша. М.: Q520, Rawles Hall, 2008
5. Марков А.А., Об одном применении статистического метода. М.: Известия АН, сер.6, Х, №4, 239, 1916
6. Чесебиев И.А., Компьютерное распознавание и порождение речи. М.: Спорт и культура - 2000, 2008 г.
7. Николенко С., Машинное обучение. М.: ИТМО, 2006
8. Гмурман В.Е., Теория вероятностей и математическая статистика, М.: Высшее образование. 2005
Размещено на Allbest.ru
Подобные документы
Разработка программной базы для исследований в области распознавания речи и поиска ключевых слов в ней. Расчет mel-фильтров. Скрытые марковские модели. Применение в алгоритме сверточного декодирования Витерби. Методы визуализации и обработки аудиоданных.
курсовая работа [1,1 M], добавлен 01.06.2015Сущность обратного проектирования, принцип работы лазерных сканеров. Этапы обратного проектирования модели существующего объекта. Построение модели по фотографиям, обработка полигональной сетки и построение параметрических поверхностей в Geomagic Wrap.
курсовая работа [4,8 M], добавлен 19.11.2017Транскрипционные факторы. Представление регуляторных элементов. Алгоритмы поиска мотивов. Скрытые Марковские модели и вспомогательные алгоритмы. Тестирование на сгенерированных и реальных данных, отличия в показателях. Сравнение с другими алгоритмами.
дипломная работа [5,0 M], добавлен 24.05.2012Математическое моделирование технических объектов. Понятие математических моделей, классификация и свойства. Численные методы, система MathCAD и её основные функции. Алгоритмический анализ задачи, анализ реализации базовой модели электрической цепи.
дипломная работа [755,4 K], добавлен 25.07.2012Математическое описание имитационной модели. Описание блок-схемы алгоритма. Анализ полученных результатов имитационного моделирования. Сопоставление полученных результатов для разработанных моделей. Математическое описание аналитического моделирования.
курсовая работа [306,5 K], добавлен 25.03.2015Описание структурной схемы искусственного нейрона. Характеристика искусственной нейронной сети как математической модели и устройств параллельных вычислений на основе микропроцессоров. Применение нейронной сети для распознавания образов и сжатия данных.
презентация [387,5 K], добавлен 11.12.2015Описание процесса экстракции. Математическое описание модели. Алгоритм решения системы уравнений математического описания. Этапы имитационного исследования модели. Анализ результатов. Зависимость неудовлетворительной работы аппарата от расхода бензола.
контрольная работа [116,4 K], добавлен 16.11.2012Применение, функции и элементы контроллеров. Функциональная структура системы управления движением поездов. Этапы проектирования контроллера для модели железной дороги на основе микропроцессора. Реализация машинной модели, блок-схема и листинг программы.
курсовая работа [744,6 K], добавлен 08.11.2009Программное обеспечение и инструменты, применяемые для создания трехмерной модели автомобиля. Основные приемы и методы, применяемые при создании модели. Описание технической части и хода работы над проектом, примеры практического применения инструментов.
курсовая работа [5,6 M], добавлен 09.04.2014Значение вербальных и знаковых информационных моделей для исследования объектов, процессов, явлений. Роль метода формализации в процессе создания компьютерной модели. Использование программы AutoCAD для трехмерного моделирования и визуализации объекта.
курсовая работа [866,5 K], добавлен 08.01.2015
