Марковская модель переменного порядка

Марковские процессы с переменной «памятью»

В математической теории случайных процессов модели Маркова переменного порядка (VOM) представляют собой важный класс моделей, расширяющих хорошо известные модели цепей Маркова . В отличие от моделей цепей Маркова, где каждая случайная величина в последовательности с марковским свойством зависит от фиксированного числа случайных величин, в моделях VOM это количество обусловливающих случайных величин может варьироваться в зависимости от конкретной наблюдаемой реализации.

Эту последовательность реализации часто называют контекстом ; поэтому модели VOM также называются контекстными деревьями . ^[1] Модели VOM хорошо визуализируются с помощью раскрашенных вероятностных суффиксных деревьев (PST). ^[2] Гибкость количества обуславливающих случайных величин оказывается реальным преимуществом для многих приложений, таких как статистический анализ , классификация и прогнозирование . ^{[3] [4] [5]}

Пример

Рассмотрим, например, последовательность случайных величин , каждая из которых принимает значение из троичного алфавита { a , b , c } . В частности, рассмотрим строку, созданную из бесконечных конкатенаций подстроки aaabc : aaabcaaabcaaabcaaabc…aaabc .

Модель VOM максимального порядка 2 может аппроксимировать приведенную выше строку, используя только следующие пять компонентов условной вероятности : Pr( a | aa ) = 0,5 , Pr( b | aa ) = 0,5 , Pr( c | b ) = 1,0 , Pr( а | с ) = 1,0 , Пр( а | ca ) знак равно 1,0 .

В этом примере Pr( c | ab ) = Pr( c | b ) = 1,0 ; следовательно, более короткого контекста b достаточно для определения следующего символа. Аналогично, модель VOM максимального порядка 3 может генерировать строку точно, используя только пять компонентов условной вероятности, все из которых равны 1,0.

Чтобы построить цепь Маркова порядка 1 для следующего символа в этой строке, необходимо оценить следующие 9 компонентов условной вероятности: Pr( a | a ) , Pr( a | b ) , Pr( a | c ) , Pr( b а ) , Пр( б | б ) , Пр ( б | с ) , Пр ( с | а ) , Пр ( с | б ) , Пр ( с | с ) . Чтобы построить цепь Маркова порядка 2 для следующего символа, необходимо оценить 27 компонент условной вероятности: Pr( a | aa ) , Pr( a | ab ) , … , Pr( c | cc ) . А чтобы построить цепь Маркова третьего порядка для следующего символа, необходимо оценить следующую 81 компоненту условной вероятности: Pr( a | aaa ) , Pr( a | aab ) , … , Pr( c | ccc ) .

В практических условиях редко бывает достаточно данных для точной оценки экспоненциально растущего числа компонентов условной вероятности по мере увеличения порядка цепи Маркова.

Модель Маркова переменного порядка предполагает, что в реалистичных условиях существуют определенные реализации состояний (представленные контекстами), в которых некоторые прошлые состояния независимы от будущих состояний; соответственно, «можно добиться значительного сокращения количества параметров модели». ^[1]

Определение

Пусть A — пространство состояний (конечный алфавит ) размера . ${\displaystyle |A|}$

Рассмотрим последовательность с марковским свойством n реализаций случайных величин , где – состояние (символ) в позиции i , а конкатенация состояний и обозначается . ${\displaystyle x_{1}^{n}=x_{1}x_{2}\dots x_{n}}$ ${\displaystyle x_{i}\in A}$ ${\displaystyle \scriptstyle (1\leq i\leq n)}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{i+1}}$ ${\displaystyle x_{i}x_{i+1}}$

Учитывая обучающий набор наблюдаемых состояний, алгоритм построения моделей VOM ^{[3] [4] [5]} изучает модель P , которая обеспечивает назначение вероятности для каждого состояния в последовательности с учетом его прошлого (ранее наблюдаемые символы) или будущего. состояния. ${\displaystyle x_{1}^{n}}$

В частности, учащийся генерирует условное распределение вероятностей для символа с заданным контекстом , где знак * представляет собой последовательность состояний любой длины, включая пустой контекст. ${\displaystyle P(x_{i}\mid s)}$ ${\displaystyle x_{i}\in A}$ ${\displaystyle s\in A^{*}}$

Модели VOM пытаются оценить условные распределения формы , в которой длина контекста варьируется в зависимости от доступной статистики. Напротив, традиционные модели Маркова пытаются оценить эти условные распределения, предполагая фиксированную длину контекстов и, следовательно, могут рассматриваться как частные случаи моделей VOM. ${\displaystyle P(x_{i}\mid s)}$ ${\displaystyle |s|\leq D}$ ${\displaystyle |s|=D}$

Фактически, для данной обучающей последовательности обнаружено, что модели VOM обеспечивают лучшую параметризацию модели, чем модели Маркова фиксированного порядка , что приводит к лучшему компромиссу между дисперсией и смещением изученных моделей. ^{[3] [4] [5]}

Области применения

Разработаны различные эффективные алгоритмы оценки параметров модели ВОМ. ^[4]

Модели VOM успешно применяются в таких областях, как машинное обучение , теория информации и биоинформатика , включая конкретные приложения, такие как кодирование и сжатие данных , ^[1] сжатие документов, ^[4] классификация и идентификация последовательностей ДНК и белков , ^[6] [ 1] ^[3] статистический контроль процессов , ^[5] фильтрация спама , ^[7] гаплотипирование , ^[8] распознавание речи, ^[9] анализ последовательностей в социальных науках , ^[2] и другие.

Смотрите также

• Стохастические цепочки с памятью переменной длины
• Примеры цепей Маркова
• Байесовская сеть переменного порядка
• Марковский процесс
• Цепь Маркова Монте-Карло
• Полумарковский процесс
• Искусственный интеллект

Рекомендации

1. Риссанен, Дж. (сентябрь 1983 г.). «Универсальная система сжатия данных». Транзакции IEEE по теории информации . 29 (5): 656–664. дои : 10.1109/TIT.1983.1056741.
2. Габадиньо, Алексис; Ритчард, Гилберт (2016). «Анализ последовательностей состояний с помощью вероятностных суффиксных деревьев: пакет PST R». Журнал статистического программного обеспечения . 72 (3). дои : 10.18637/jss.v072.i03 . ISSN  1548-7660. S2CID  63681202.
3. Шмиловичи, А.; Бен-Гал, И. (2007). «Использование модели VOM для реконструкции потенциальных областей кодирования в последовательностях EST». Вычислительная статистика . 22 (1): 49–69. дои : 10.1007/s00180-007-0021-8. S2CID  2737235.
4. Begleiter, Р.; Эль-Янив, Р.; Йона, Г. (2004). «О прогнозировании с использованием марковских моделей переменного порядка». Журнал исследований искусственного интеллекта . 22 : 385–421. arXiv : 1107.0051 . дои : 10.1613/jair.1491 .
5. Бен-Гал, И.; Мораг, Г.; Шмилович, А. (2003). «Контекстное статистическое управление процессами: процедура мониторинга процессов, зависящих от состояния» (PDF) . Технометрика . 45 (4): 293–311. дои : 10.1198/004017003000000122. ISSN  0040-1706. S2CID  5227793.
6. Грау Дж.; Бен-Гал И.; Пош С.; Гросс И. (2006). «VOMBAT: прогнозирование сайтов связывания факторов транскрипции с использованием байесовских деревьев переменного порядка» (PDF) . Исследования нуклеиновых кислот . 34 (проблема с веб-сервером). Исследования нуклеиновых кислот, том. 34, выпуск W529–W533.: W529-33. дои : 10.1093/nar/gkl212. ПМЦ 1538886 . ПМИД  16845064. 
7. Братко, А.; Кормак, Г.В.; Филипич, Б.; Линам, Т.; Зупан, Б. (2006). «Фильтрация спама с использованием статистических моделей сжатия данных» (PDF) . Журнал исследований машинного обучения . 7 : 2673–2698.
8. Браунинг, Шэрон Р. «Отображение мультилокусных ассоциаций с использованием цепей Маркова переменной длины». Американский журнал генетики человека 78.6 (2006): 903–913.
9. Смит, А.; Дененберг, Дж.; Слэк, Т.; Тан, К.; Уолфорд, Р. (1985). «Применение системы последовательного обучения шаблонам для распознавания связанной речи». ИКАССП '85. Международная конференция IEEE по акустике, речи и обработке сигналов . Том. 10. Тампа, Флорида, США: Институт инженеров по электротехнике и электронике. стр. 1201–1204. дои : 10.1109/ICASSP.1985.1168282. S2CID  60991068.