Введение

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

История

Алгоритм Баума — Уэлча был назван в честь его изобретателей Леонарда Э. Баума и Ллойда Р. Уэлча. Алгоритм и скрытые марковские модели были впервые описаны в серии статей Баума и его коллег из Центра исследований связи IDA в Принстоне в конце 1960-х и начале 1970-х годов. Одним из первых значительных применений скрытых марковских моделей стала область обработки речи. В 1980-х годах скрытые марковские модели стали полезным инструментом в анализе биологических систем и информации, в особенности генетической информации. С тех пор они стали важным инструментом в вероятностном моделировании геномных последовательностей.

Описание

Скрытая модель Маркова описывает совместную вероятность набора "скрытых" и наблюдаемых дискретных случайных переменных. Она основана на предположении, что i-я скрытая переменная, при заданном значении (i − 1)-й скрытой переменной, независима от предыдущих скрытых переменных, а текущие наблюдаемые переменные зависят только от текущего скрытого состояния. Алгоритм Баума — Уэлша использует хорошо известный алгоритм EM для нахождения оценки максимального правдоподобия параметров скрытой модели Маркова, основываясь на наборе наблюдаемых векторов признаков. Пусть — дискретная скрытая случайная переменная с возможными значениями (то есть мы предполагаем, что всего существует состояний). Мы предполагаем, что не зависит от времени , что приводит к определению стационарной стохастической матрицы переходов.

Распределение начального состояния (то есть при ) задается как

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

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

Алгоритм

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

Процедура продления

Пусть , вероятность наблюдения и нахождения в состоянии в момент времени . Это вычисляется рекурсивно:

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

Процедура обратного отсчета

Пусть это вероятность завершения частичной последовательности, учитывая начальное состояние в момент времени t. Мы вычисляем её как,

Распознавание речи

Скрытые модели Маркова впервые были применены к распознаванию речи Джеймсом К. Бейкером в 1975 году. Непрерывное распознавание речи осуществляется следующими шагами, моделируемыми с помощью HMM. Сначала проводится анализ признаков временных и/или спектральных характеристик речевого сигнала. Это приводит к созданию вектора наблюдения. Затем полученный признак сравнивается со всеми последовательностями единиц распознавания речи. Этими единицами могут быть фонемы, слоги или целые слова. Для ограничения исследуемых путей используется система декодирования лексикона, поэтому рассматриваются только слова, содержащиеся в лексиконе системы (словаре слов). Аналогично декодированию лексикона, путь системы дополнительно ограничивается правилами грамматики и синтаксиса. В заключение применяется семантический анализ, и система выдает распознанное высказывание. Ограничением многих применений HMM в распознавании речи является то, что текущее состояние зависит только от состояния на предыдущем временном шаге, что нереалистично для речи, поскольку зависимости часто охватывают несколько временных шагов. Алгоритм Баума — Уэлша также широко используется для решения HMM, применяемых в области синтеза речи.

Криптоанализ

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

Прокариотические

Программное обеспечение GLIMMER (Gene Locator and Interpolated Markov ModelER) было одной из первых программ для поиска генов, использовавшихся для идентификации кодирующих областей в прокариотической ДНК. GLIMMER использует интерполированные марковские модели (IMM) для выявления кодирующих областей и их отличия от некодирующей ДНК. Последняя версия (GLIMMER3) продемонстрировала повышенную специфичность и точность по сравнению с предыдущими версиями в отношении предсказания сайтов инициации трансляции, показывая среднюю точность 99% в определении 3'-концов по сравнению с подтвержденными генами у прокариот.

Эукариотические

GENSCAN – это веб-сервер, способный анализировать последовательности эукариот длиной до одного миллиона пар оснований (1 Мбп). GENSCAN использует общую неоднородную, трипериодическую, марковскую модель пятого порядка для кодирующих областей ДНК. Кроме того, эта модель учитывает различия в плотности и структуре генов (таких как длина интронов), которые наблюдаются в разных изохорах. В то время как большинство интегрированных программ для поиска генов (на момент выпуска GENSCAN) предполагали, что входные последовательности содержат ровно один ген, GENSCAN решает общий случай, когда присутствуют частичные, полные или множественные гены (или даже вообще ни одного гена). Показано, что GENSCAN точно предсказывает местоположение экзонов с точностью 90% и специфичностью 80% по сравнению с аннотированной базой данных.

Обнаружение изменения количества копий

Вариации числа копий (CNV) — широко распространенная форма вариаций структуры генома человека. Для анализа использовалась дискретная бивариантная скрытая марковская модель (dbHMM), которая относила хромосомные области к семи различным состояниям: не измененные области, делеции, дупликации и четыре переходных состояния. Решение этой модели с помощью алгоритма Баума — Уэлша показало возможность предсказания местоположения границы CNV с точностью до 300 пар оснований на основе данных микроматриц. Такая степень разрешения позволяет устанавливать более точные корреляции между различными CNV и между популяциями, чем это было возможно ранее, что открывает возможности для изучения частот CNV в популяциях. Также была продемонстрирована прямая схема наследования для конкретного CNV.