В электротехнике , статистические вычисления и биоинформатики , то Baum-Welch алгоритм является частным случаем алгоритма EM используется для нахождения неизвестных параметров скрытой марковской модели (HMM). Он использует алгоритм вперед-назад для вычисления статистики для шага ожидания.
История
Алгоритм Баума – Велча был назван в честь его изобретателей Леонарда Э. Баума и Ллойда Р. Велча . Алгоритм и скрытые модели Маркова были впервые описаны в серии статей Баума и его коллег из Института оборонного анализа в конце 1960-х - начале 1970-х годов. [1] Одним из первых крупных приложений HMM была область обработки речи . [2] В 1980-х годах ТММ становились полезным инструментом в анализе биологических систем и информации, в частности генетической информации . [3] С тех пор они стали важным инструментом вероятностного моделирования геномных последовательностей. [4]
Описание
Скрытые модели Маркова описывает совместную вероятность коллекции « скрытые » и наблюдаемые дискретных случайных величин. Он основан на предположении, что i-я скрытая переменная с учетом ( i - 1) -й скрытой переменной не зависит от предыдущих скрытых переменных, а текущие переменные наблюдения зависят только от текущего скрытого состояния.
Алгоритм Баума – Велча использует хорошо известный алгоритм EM для нахождения оценки максимального правдоподобия параметров скрытой марковской модели с учетом набора наблюдаемых векторов признаков.
Позволять дискретная скрытая случайная величина с возможные значения (т.е. мы предполагаем, что есть штатов всего). Мы предполагаем не зависит от времени , что приводит к определению не зависящей от времени матрицы стохастических переходов
Распределение начального состояния (т.е. когда ) дан кем-то
Переменные наблюдения может взять один из возможные значения. Мы также предполагаем, что наблюдение в «скрытом» состоянии не зависит от времени. Вероятность определенного наблюдения вовремя для государства дан кем-то
Принимая во внимание все возможные значения а также , получаем матрица где принадлежит всем возможным состояниям и принадлежит всем наблюдениям.
Последовательность наблюдений задается формулой .
Таким образом, мы можем описать скрытую цепь Маркова с помощью . Алгоритм Баума – Велча находит локальный максимум для (т.е. параметры HMM которые увеличивают вероятность наблюдения). [5]
Алгоритм
Набор со случайными начальными условиями. Их также можно установить с использованием предварительной информации о параметрах, если она доступна; это может ускорить алгоритм, а также направить его к желаемому локальному максимуму.
Форвардная процедура
Позволять , вероятность увидеть наблюдения и находясь в состоянии вовремя . Это находится рекурсивно:
Поскольку этот ряд экспоненциально сходится к нулю, алгоритм будет численно истощать для более длинных последовательностей. [6] Однако этого можно избежать в слегка измененном алгоритме путем масштабирования в форварде и в обратной процедуре ниже.
Обратная процедура
Позволять это вероятность окончания частичной последовательности данное начальное состояние вовремя . Мы рассчитываем в виде,
Обновлять
Теперь мы можем вычислить временные переменные согласно теореме Байеса:
что вероятность нахождения в состоянии вовремя учитывая наблюдаемую последовательность и параметры
что вероятность нахождения в состоянии а также во время а также соответственно, учитывая наблюдаемую последовательность и параметры .
Знаменатели а также одинаковы ; они представляют собой вероятность проведения наблюдения учитывая параметры .
Параметры скрытой марковской модели теперь можно обновлять:
что является ожидаемой частотой нахождения в состоянии вовремя .
который представляет собой ожидаемое количество переходов из состояния i в состояние j по сравнению с ожидаемым общим числом переходов из состояния i . Чтобы уточнить, количество переходов из состояния i не означает переходы в другое состояние j , а в любое состояние, включая его самого. Это эквивалентно количеству раз, когда состояние i наблюдается в последовательности от t = 1 до t = T - 1.
где
- индикаторная функция, а ожидаемое количество раз, когда выходные наблюдения были равны в то время как в состоянии больше ожидаемого общего количества раз в состоянии .
Эти шаги теперь повторяются итеративно до желаемого уровня сходимости.
Примечание. Возможен перебор определенного набора данных. Это,. Алгоритм также не гарантирует глобального максимума.
Несколько последовательностей
Алгоритм, описанный до сих пор, предполагает одну наблюдаемую последовательность . Однако во многих ситуациях наблюдается несколько последовательностей:. В этом случае информация из всех наблюдаемых последовательностей должна использоваться при обновлении параметров., , а также . Предполагая, что вы вычислили а также для каждой последовательности , теперь можно обновить параметры:
где
индикаторная функция
Пример
Предположим, у нас есть курица, из которой мы собираем яйца каждый день в полдень. Теперь, отложила ли курица яйца для сбора, зависит от некоторых скрытых неизвестных факторов. Однако мы можем (для простоты) предположить, что есть только два состояния, которые определяют, откладывает ли курица яйца. Теперь мы не знаем состояние в начальной начальной точке, мы не знаем вероятностей перехода между двумя состояниями и мы не знаем вероятность того, что курица снесет яйцо в конкретном состоянии. [7] [8] Для начала предположим матрицы перехода и излучения.
|
|
|
Затем мы берем набор наблюдений (E = яйца, N = нет яиц): N, N, N, N, N, E, E, N, N, N
Это дает нам набор наблюдаемых переходов между днями: NN, NN, NN, NN, NE, EE, EN, NN, NN.
Следующим шагом является оценка новой матрицы перехода. Например, вероятность того, что последовательность NN и состояние будут тогда дается следующим образом,
Наблюдаемая последовательность | Наибольшая вероятность наблюдения этой последовательности, если состояние тогда | Наивысшая вероятность наблюдения этой последовательности | |
---|---|---|---|
NN | 0,024 = 0,2 * 0,3 * 0,5 * 0,8 | 0,3584 | , |
NN | 0,024 = 0,2 * 0,3 * 0,5 * 0,8 | 0,3584 | , |
NN | 0,024 = 0,2 * 0,3 * 0,5 * 0,8 | 0,3584 | , |
NN | 0,024 = 0,2 * 0,3 * 0,5 * 0,8 | 0,3584 | , |
NE | 0,006 = 0,2 * 0,3 * 0,5 * 0,2 | 0,1344 | , |
EE | 0,014 = 0,2 * 0,7 * 0,5 * 0,2 | 0,0490 | , |
EN | 0,056 = 0,2 * 0,7 * 0,5 * 0,8 | 0,0896 | , |
NN | 0,024 = 0,2 * 0,3 * 0,5 * 0,8 | 0,3584 | , |
NN | 0,024 = 0,2 * 0,3 * 0,5 * 0,8 | 0,3584 | , |
Общее | 0,22 | 2,4234 |
Таким образом, новая оценка к переход сейчас (в следующих таблицах именуются «псевдовероятностями»). Затем мы вычисляем к , к а также к вероятности перехода и нормализуются, поэтому они прибавляются к 1. Это дает нам обновленную матрицу перехода:
|
|
|
Затем мы хотим оценить новую матрицу выбросов,
Наблюдаемая последовательность | Наивысшая вероятность наблюдения этой последовательности, если предполагается, что E происходит из | Наивысшая вероятность наблюдения этой последовательности | ||
---|---|---|---|---|
NE | 0,1344 | , | 0,1344 | , |
EE | 0,0490 | , | 0,0490 | , |
EN | 0,0560 | , | 0,0896 | , |
Общее | 0,2394 | 0,2730 |
Новая оценка E, полученная от эмиссия сейчас .
Это позволяет нам рассчитать матрицу выбросов, как описано выше в алгоритме, путем сложения вероятностей для соответствующих наблюдаемых последовательностей. Затем мы повторяем, если N пришло из и если N и E пришли из и нормализовать.
|
|
|
Чтобы оценить начальные вероятности, мы предполагаем, что все последовательности начинаются со скрытого состояния и вычислите наибольшую вероятность, а затем повторите для . Затем мы снова нормализуем, чтобы получить обновленный начальный вектор.
Наконец, мы повторяем эти шаги до тех пор, пока результирующие вероятности не сойдутся удовлетворительно.
Приложения
Распознавание речи
Скрытые марковские модели были впервые применены к распознаванию речи Джеймсом К. Бейкером в 1975 году. [9] Распознавание непрерывной речи происходит с помощью следующих шагов, смоделированных с помощью HMM. Анализ характеристик сначала проводится на временных и / или спектральных характеристиках речевого сигнала. Это создает вектор наблюдения. Затем функция сравнивается со всеми последовательностями блоков распознавания речи. Этими единицами могут быть фонемы , слоги или целые слова. Система декодирования лексики применяется для ограничения исследуемых путей, поэтому исследуются только слова в лексиконе системы (словарном словаре). Подобно декодированию словаря, системный путь дополнительно ограничен правилами грамматики и синтаксиса. Наконец, применяется семантический анализ, и система выводит распознанное высказывание. Ограничение многих приложений HMM на распознавание речи состоит в том, что текущее состояние зависит только от состояния на предыдущем временном шаге, что нереально для речи, поскольку зависимости часто имеют продолжительность в несколько временных шагов. [10] Алгоритм Баума-Велча также имеет обширные приложения для решения HMM, используемых в области синтеза речи. [11]
Криптоанализ
Алгоритм Баума – Велча часто используется для оценки параметров HMM при расшифровке скрытой или зашумленной информации и, следовательно, часто используется в криптоанализе . В области безопасности данных наблюдатель хотел бы извлечь информацию из потока данных, не зная всех параметров передачи. Это может включать обратное проектирование кодировщика каналов . [12] HMM и, как следствие, алгоритм Баума – Велча также использовались для идентификации произносимых фраз в зашифрованных вызовах VoIP. [13] Кроме того, криптоанализ HMM является важным инструментом для автоматизированного исследования данных о времени кэширования. Это позволяет автоматически обнаруживать критическое состояние алгоритма, например ключевые значения. [14]
Приложения в биоинформатике
Поиск генов
Прокариотический
Программа GLIMMER (Gene Locator and Interpolated Markov ModelER) была ранней программой поиска генов, используемой для идентификации кодирующих областей в прокариотической ДНК. [15] [16] GLIMMER использует интерполированные марковские модели (IMM), чтобы идентифицировать кодирующие области и отличать их от некодирующей ДНК . Последняя версия (GLIMMER3) продемонстрировала повышенную специфичность и точность по сравнению с ее предшественниками в отношении прогнозирования сайтов инициации трансляции, демонстрируя в среднем 99% точность определения местоположения 3 'по сравнению с подтвержденными генами у прокариот. [17]
Эукариотический
GENSCAN веб - сервер представляет собой ген локатор , способный анализировать эукариотические последовательности до одного миллиона пар оснований (1 МВР) в длину. [18] GENSCAN использует общую неоднородную трехпериодическую марковскую модель пятого порядка кодирующих областей ДНК. Кроме того, эта модель учитывает различия в плотности и структуре генов (например, в длине интронов), которые встречаются в разных изохорах . В то время как большинство интегрированных программ для поиска генов (на момент выпуска GENSCAN) предполагали, что входные последовательности содержат ровно один ген, GENSCAN решает общий случай, когда присутствуют частичные, полные или множественные гены (или даже нет гена вообще). [19] Было показано, что GENSCAN точно предсказывает местоположение экзона с точностью 90% и специфичностью 80% по сравнению с аннотированной базой данных. [20]
Обнаружение изменения номера копии
Вариации числа копий (CNV) - распространенная форма вариаций структуры генома у людей. Использовалась двумерная HMM с дискретными значениями (dbHMM), приписывающая хромосомные области семи различным состояниям: незатронутым областям, делециям, дупликациям и четырем переходным состояниям. Решение этой модели с использованием Баума-Велча продемонстрировало способность предсказывать местоположение точки останова CNV примерно до 300 п.н. на основе экспериментов с микромассивом . [21] Эта величина разрешения позволяет более точную корреляцию между различными CNV и между популяциями, чем это было возможно ранее, что позволяет изучать частоты популяций CNV. Он также продемонстрировал образец прямого наследования для конкретной CNV .
Реализации
- Accord.NET на C #
- ghmm C-библиотека с привязками Python, которая поддерживает как дискретные, так и непрерывные выбросы.
- Пакет HMMBase для Юлии .
- Функция HMMFit в RHmm пакет для R .
- hmmtrain в MATLAB
Смотрите также
- Алгоритм Витерби
- Скрытая марковская модель
- EM алгоритм
- Максимальная вероятность
- Распознавание речи
- Биоинформатика
- Криптоанализ
Рекомендации
- ^ Рабинер, Лоуренс. «Из первых рук: скрытая марковская модель» . Сеть глобальной истории IEEE . Проверено 2 октября 2013 года .
- ^ Елинек, Фредерик; Bahl, Lalit R .; Мерсер, Роберт Л. (май 1975 г.). «Разработка лингвистического статистического декодера для распознавания слитной речи». IEEE Transactions по теории информации . 21 (3): 250–6. DOI : 10,1109 / tit.1975.1055384 .
- ^ Бишоп, Мартин Дж .; Томпсон, Элизабет А. (20 июля 1986 г.). «Максимальное правдоподобие выравнивания последовательностей ДНК». Журнал молекулярной биологии . 190 (2): 159–65. DOI : 10.1016 / 0022-2836 (86) 90289-5 . PMID 3641921 .
- ^ Дурбин, Ричард (23 апреля 1998 г.). Анализ биологической последовательности: вероятностные модели белков и нуклеиновых кислот . Издательство Кембриджского университета. ISBN 978-0-521-62041-3.
- ^ Билмес, Джефф А. (1998). Мягкое руководство по алгоритму EM и его применению для оценки параметров для гауссовской смеси и скрытых марковских моделей . Беркли, Калифорния: Международный институт компьютерных наук. С. 7–13.
- ^ Рабинер, Лоуренс (февраль 1989 г.). «Учебное пособие по скрытым марковским моделям и избранным приложениям в распознавании речи» (PDF) . Труды IEEE . Проверено 29 ноября 2019 .
- ^ «Приложения Баума-Велча и HMM» (PDF) . Школа общественного здравоохранения Bloomberg Джонса Хопкинса . Проверено 11 октября 2019 года .
- ^ Фраццоли, Эмилио. «Введение в скрытые марковские модели: алгоритм Баума-Велча» (PDF) . Аэронавтика и астронавтика, Массачусетский технологический институт . Проверено 2 октября 2013 года .
- ^ Бейкер, Джеймс К. (1975). «Система ДРАКОН - Обзор». Транзакции IEEE по акустике, речи и обработке сигналов . 23 : 24–29. DOI : 10,1109 / TASSP.1975.1162650 .
- ^ Рабинер, Лоуренс (февраль 1989 г.). "Учебное пособие по скрытым марковским моделям и избранным приложениям в распознавании речи". Труды IEEE . 77 (2): 257–286. CiteSeerX 10.1.1.381.3454 . DOI : 10.1109 / 5.18626 .
- ^ Токуда, Кейчи; Ёсимура, Такаяоши; Масуко, Такаши; Кобаяси, Такао; Китамура, Тадаши (2000). «Алгоритмы генерации параметров речи для синтеза речи на основе HMM». Международная конференция IEEE по акустике, речи и обработке сигналов . 3 .
- ^ Дингель, Янис; Хагенауэр, Иоахим (24 июня 2007 г.). "Оценка параметров сверточного кодировщика по зашумленным наблюдениям". Международный симпозиум IEEE по теории информации .
- ^ Райт, Чарльз; Баллард, Лукас; Коулл, Скотт; Монроуз, Фабиан; Массон, Джеральд (2008). «Найди меня, если сможешь: раскрытие разговорных фраз в зашифрованных разговорах по протоколу VoIP». Международный симпозиум IEEE по безопасности и конфиденциальности .
- ^ Брамли, Боб; Хакала, Ристо (2009). Атаки по шаблону времени кэширования . Достижения в криптографии . Конспект лекций по информатике. 5912 . С. 667–684. DOI : 10.1007 / 978-3-642-10366-7_39 . ISBN 978-3-642-10365-0.
- ^ Зальцберг, Стивен; Делчер, Артур Л .; Касиф, Саймон; Белый, Оуэн (1998). «Идентификация микробных генов с использованием интерполированных моделей Маркова» . Исследования нуклеиновых кислот . 26 (2): 544–548. DOI : 10.1093 / NAR / 26.2.544 . PMC 147303 . PMID 9421513 .
- ^ "Glimmer: Система обнаружения микробных генов" . Университет Джона Хопкинса - Центр вычислительной биологии.
- ^ Делчер, Артур; Братке, Кирстен А .; Пауэрс, Эдвин С .; Зальцберг, Стивен Л. (2007). «Идентификация бактериальных генов и ДНК эндосимбионтов с помощью Glimmer» . Биоинформатика . 23 (6): 673–679. DOI : 10.1093 / биоинформатики / btm009 . PMC 2387122 . PMID 17237039 .
- ^ Бердж, Кристофер. «Веб-сервер GENSCAN в Массачусетском технологическом институте» . Архивировано из оригинального 6 -го сентября 2013 года . Проверено 2 октября 2013 года .
- ^ Бердж, Крис; Карлин, Самуэль (1997). «Прогнозирование полных генных структур в геномной ДНК человека». Журнал молекулярной биологии . 268 (1): 78–94. CiteSeerX 10.1.1.115.3107 . DOI : 10.1006 / jmbi.1997.0951 . PMID 9149143 .
- ^ Бердж, Кристофер; Карлин, Самуэль (1998). «Обнаружение генов в геномной ДНК». Текущее мнение в структурной биологии . 8 (3): 346–354. DOI : 10.1016 / s0959-440x (98) 80069-9 . PMID 9666331 .
- ^ Корбель, Ян ; Урбан, Александр; Груберт, Фабьен; Ду, Цзян; Ройс, Томас; Старр, Питер; Чжун, Гуонэн; Эмануэль, Беверли; Вайсман, Шерман; Снайдер, Майкл; Герштейн, Марг (12 июня 2007 г.). «Систематическое предсказание и проверка точек останова, связанных с вариациями числа копий в геноме человека» . Труды Национальной академии наук Соединенных Штатов Америки . 104 (24): 10110–5. Bibcode : 2007PNAS..10410110K . DOI : 10.1073 / pnas.0703834104 . PMC 1891248 . PMID 17551006 .
Внешние ссылки
- Комплексный обзор методов и программного обеспечения HMM в биоинформатике - Profile Hidden Markov Models
- Ранние публикации HMM Баума:
- Техника максимизации, встречающаяся в статистическом анализе вероятностных функций марковских цепей
- Неравенство с приложениями к статистическому оцениванию вероятностных функций марковских процессов и к модели для экологии
- Статистический вывод для вероятностных функций конечных марковских цепей
- Лекция Шеннона Уэлча, в которой рассказывается, как можно эффективно реализовать алгоритм:
- Скрытые марковские модели и алгоритм Баума – Велча , Информационный бюллетень Общества теории информации IEEE, декабрь 2003 г.
- Альтернатива алгоритму Баума – Велча, алгоритм подсчета путей Витерби:
- Дэвис, Ричард ИА; Ловелл, Брайан Ч .; «Сравнение и оценка алгоритмов обучения ансамбля HMM с использованием критериев обучающих и тестовых и условных чисел» , Pattern Analysis and Applications, vol. 6, вып. 4. С. 327–336, 2003.
- Интерактивная таблица для обучения алгоритму вперед-назад (таблица и статья с пошаговым руководством)
- Формальный вывод алгоритма Баума – Велча.
- Реализация алгоритма Баума – Велча.