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

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

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

Пример [ править ]

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

Модель VOM максимального порядка 2 может аппроксимировать указанную выше строку, используя только следующие пять компонентов условной вероятности : {Pr ( a | aa ) = 0,5, Pr ( b | aa ) = 0,5, Pr ( c | b ) = 1,0, Pr ( a | c ) = 1.0, Pr ( a | 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 | a ), Pr ( b | b ), Pr ( b | c ), Pr ( c | a ), Pr ( c | b ), Pr ( c | c))}. Чтобы построить цепь Маркова порядка 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 |}$

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

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

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

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

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

Области применения [ править ]

Были разработаны различные эффективные алгоритмы для оценки параметров модели VOM. ^[3]

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

См. Также [ править ]

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

Ссылки [ править ]

^ a b c Риссанен, Дж. (сентябрь 1983 г.). «Универсальная система сжатия данных». IEEE Transactions по теории информации . 29 (5): 656–664. DOI : 10.1109 / TIT.1983.1056741 .
^ a b c d Шмилович, А .; Бен-Гал, И. (2007). «Использование модели VOM для реконструкции потенциальных областей кодирования в последовательностях EST». Вычислительная статистика . 22 (1): 49–69. DOI : 10.1007 / s00180-007-0021-8 .
^ a b c d e Begleiter, R .; Эль-Янив, Р .; Йона, Г. (2004). «О прогнозировании с использованием марковских моделей переменного порядка» (PDF) . Журнал исследований искусственного интеллекта . 22 : 385–421. DOI : 10.1613 / jair.1491 . Архивировано из оригинального (PDF) 28 сентября 2007 года . Проверено 22 апреля 2007 .
^ a b c d Бен-Гал, I .; Morag, G .; Шмилович, А. (2003). «CSPC: Процедура мониторинга для процессов, зависящих от состояния» (PDF) . Технометрика . 45 (4): 293–311. DOI : 10.1198 / 004017003000000122 .
^ Грау J .; Бен-Гал I .; Posch S .; Гросс И. (2006). "VOMBAT: Прогнозирование сайтов связывания транскрипционных факторов с использованием байесовских деревьев переменного порядка" (PDF) . Nucleic Acids Research, vol. 34, выпуск W529 – W533. Cite journal requires |journal= (help)
^ Братко, А .; Cormack, GV; Filipic, B .; Линам, Т .; Зупан, Б. (2006). «Фильтрация спама с использованием моделей сжатия статистических данных» (PDF) . Журнал исследований в области машинного обучения . 7 : 2673–2698.
^ Браунинг, Шэрон Р. "Сопоставление мультилокусных ассоциаций с использованием цепей Маркова переменной длины". Американский журнал генетики человека 78.6 (2006): 903–913.

^[1]

^ Смит, АР; Дененберг, JN; Slack, ТБ; Тан, СС; Wohlford, R.E (август 1985 г.). «Применение системы последовательного обучения шаблонов для распознавания подключенной речи» (PDF) . Труды Международной конференции IEEE 1985 по акустике, речи и обработке сигналов : 1201–1204.

[Rissanen-1] Риссанен, Дж. (сентябрь 1983 г.). «Универсальная система сжатия данных». IEEE Transactions по теории информации . 29 (5): 656–664. DOI : 10.1109 / TIT.1983.1056741 .

[Shmilovici-2] Шмилович, А .; Бен-Гал, И. (2007). «Использование модели VOM для реконструкции потенциальных областей кодирования в последовательностях EST». Вычислительная статистика . 22 (1): 49–69. DOI : 10.1007 / s00180-007-0021-8 .

[Begleiter-3] Begleiter, R .; Эль-Янив, Р .; Йона, Г. (2004). «О прогнозировании с использованием марковских моделей переменного порядка» (PDF) . Журнал исследований искусственного интеллекта . 22 : 385–421. DOI : 10.1613 / jair.1491 . Архивировано из оригинального (PDF) 28 сентября 2007 года . Проверено 22 апреля 2007 .

[Ben-Gal-4] Бен-Гал, I .; Morag, G .; Шмилович, А. (2003). «CSPC: Процедура мониторинга для процессов, зависящих от состояния» (PDF) . Технометрика . 45 (4): 293–311. DOI : 10.1198 / 004017003000000122 .

[5] Грау J .; Бен-Гал I .; Posch S .; Гросс И. (2006). "VOMBAT: Прогнозирование сайтов связывания транскрипционных факторов с использованием байесовских деревьев переменного порядка" (PDF) . Nucleic Acids Research, vol. 34, выпуск W529 – W533. Cite journal requires |journal= (help)

[Bratko-6] Братко, А .; Cormack, GV; Filipic, B .; Линам, Т .; Зупан, Б. (2006). «Фильтрация спама с использованием моделей сжатия статистических данных» (PDF) . Журнал исследований в области машинного обучения . 7 : 2673–2698.

[7] Браунинг, Шэрон Р. "Сопоставление мультилокусных ассоциаций с использованием цепей Маркова переменной длины". Американский журнал генетики человека 78.6 (2006): 903–913.

[8] Смит, АР; Дененберг, JN; Slack, ТБ; Тан, СС; Wohlford, R.E (август 1985 г.). «Применение системы последовательного обучения шаблонов для распознавания подключенной речи» (PDF) . Труды Международной конференции IEEE 1985 по акустике, речи и обработке сигналов : 1201–1204.

[1]