Стохастические цепочки с памятью переменной длины

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

Определение

Стохастическая цепь с памятью переменной длины — это стохастическая цепь. $(X_{n})_{n\in Z}$ , принимающий значения в конечном алфавите $A$ и характеризуется вероятностным контекстным деревом $(\tau ,p)$ , так что

$\tau$ это группа всех контекстов. Контекст $X_{n-l},\ldots ,X_{n-1}$ , существование $l$ размер контекста - это конечная часть прошлого $X_{-\infty },\ldots ,X_{n-1}$ , что важно для прогнозирования следующего символа $X_{n}$ ;
$p$ представляет собой семейство вероятностей перехода, связанных с каждым контекстом.

История

Класс стохастических цепей с памятью переменной длины был введен Йормой Риссаненом в статье Универсальная система сжатия данных . ^[1] Такой класс стохастических цепей был популяризирован в статистическом и вероятностном сообществе П. Бюльманом и А. Дж. Винером в 1999 году в статье « Цепи Маркова переменной длины» . Названные Бюльманом и Винером « цепями Маркова переменной длины » (VLMC), эти цепи также известны как « модели Маркова переменного порядка » (VOM), «вероятностные суффиксные деревья ». ^[2] и « модели контекстного дерева ». ^[5] Название «стохастические цепи с памятью переменной длины», по-видимому, было введено Гальвесом и Лёхербахом в 2008 году в одноименной статье. ^[6]

Примеры

Прерывистый источник света

Рассмотрим систему с лампой, наблюдателем и дверью между ними. Лампа имеет два возможных состояния : включена, обозначается цифрой 1, или выключена, обозначается цифрой 0. Когда лампа включена, наблюдатель может видеть свет через дверь, в зависимости от того, в каком состоянии дверь находится в данный момент: открыта, 1. , или закрыто, 0. такие состояния не зависят от исходного состояния лампы.

Позволять $(X_{n})_{n\geq 0}$ цепь Маркова , которая представляет состояние лампы со значениями в $A={0,1}$ и пусть $p$ быть вероятностной матрицей перехода . Кроме того, пусть $(\xi _{n})_{n\geq 0}$ быть последовательностью независимых случайных величин , которые представляют состояния двери, также принимающие значения в $A$ , независимо от цепи $(X_{n})_{n\geq 0}$ и такое, что

\mathbb {P} (\xi _{n}=1)=1-\varepsilon

где $0<\epsilon <1$ . Определить новую последовательность $(Z_{n})_{n\geq 0}$ такой, что

Z_{n}=X_{n}\xi _{n}

для каждого

(Z_{n})_{n\geq 0}.

Чтобы определить последний момент, когда наблюдатель мог видеть включенную лампу, т. е. определить наименьший момент $k$ , с $k<n$ в котором $Z_{k}=1$ .

Используя дерево контекста, можно представить прошлые состояния последовательности, показывая, какие из них важны для идентификации следующего состояния.

Стохастическая цепочка $(Z_{n})_{n\in \mathbb {Z} }$ тогда это цепочка с памятью переменной длины, принимающая значения в $A$ и совместимо с вероятностным контекстным деревом $(\tau ,p)$ , где

\tau =\{1,10,100,\cdots \}\cup \{0^{\infty }\}.

Выводы в цепочках переменной длины

Учитывая образец $X_{l},\ldots ,X_{n}$ , можно найти соответствующее дерево контекста, используя следующие алгоритмы.

Контекстный алгоритм

В статье Универсальная система сжатия данных , ^[1] Риссанен представил последовательный алгоритм для оценки вероятностного контекстного дерева, генерирующего данные. Функцию этого алгоритма можно свести к двум этапам:

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

Быть $X_{0},\ldots ,X_{n-1}$ образец конечного вероятностного дерева $(\tau ,p)$ . Для любой последовательности $x_{-j}^{-1}$ с $j\leq n$ , можно обозначить через $N_{n}(x_{-j}^{-1})$ количество вхождений последовательности в выборку, т. е.

N_{n}(x_{-j}^{-1})=\sum _{t=0}^{n-j}\mathbf {1} \left\{X_{t}^{t+j-1}=x_{-j}^{-1}\right\}

Риссанен сначала построил кандидата контекстного максимума, заданного формулой $X_{n-K(n)}^{n-1}$ , где $K(n)=C\log {n}$ и $C$ — произвольная положительная константа. Интуитивная причина выбора $C\log {n}$ происходит из-за невозможности оценить вероятности последовательности с длиной больше, чем $\log {n}$ на основе выборки размером $n$ .

Далее Риссанен укорачивает максимального кандидата путем последовательного разрезания ветвей в соответствии с последовательностью тестов, основанных на статистическом отношении правдоподобия. В более формальном определении, если bANnxk1b0 определяет оценку вероятности перехода $p$ к

{\hat {p}}_{n}(a\mid x_{-k}^{-1})={\frac {N_{n}(x_{-k}^{-1}a)}{\sum _{b\in A}N_{n}(x_{-k}^{-1}b)}}

где $x_{-j}^{-1}a=(x_{-j},\ldots ,x_{-1},a)$ . Если $\sum _{b\in A}N_{n}(x_{-k}^{-1}b)\,=\,0$ , определять ${\hat {p}}_{n}(a\mid x_{-k}^{-1})\,=\,1/|A|$ .

К $i\geq 1$ , определять

\Lambda _{n}(x_{-i}^{-1})\,=\,2\,\sum _{y\in A}\sum _{a\in A}N_{n}(yx_{-i}^{-1}a)\log \left[{\frac {{\hat {p}}_{n}(a\mid x_{-i}^{-1}y)}{{\hat {p}}_{n}(a\mid x_{-i}^{-1})}}\right]\,

где $yx_{-i}^{-1}=(y,x_{-i},\ldots ,x_{-1})$ и

{\hat {p}}_{n}(a\mid x_{-i}^{-1}y)={\frac {N_{n}(yx_{-i}^{-1}a)}{\sum _{b\in A}N_{n}(yx_{-i}^{-1}b)}}.

Обратите внимание, что $\Lambda _{n}(x_{-i}^{-1})$ это отношение логарифмического правдоподобия для проверки согласованности выборки с вероятностным контекстным деревом. $(\tau ,p)$ против альтернативы, которая соответствует $(\tau ',p')$ , где $\tau$ и $\tau '$ отличаются только набором родственных узлов.

Длина текущего предполагаемого контекста определяется выражением

{\hat {\ell }}_{n}(X_{0}^{n-1})=\max \left\{i=1,\ldots ,K(n):\Lambda _{n}(X_{n-i}^{n-1})\,>\,C\log n\right\}\,

где $C$ — любая положительная константа. Наконец, Риссанен, ^[1] есть следующий результат. Данный $X_{0},\ldots ,X_{n-1}$ конечного вероятностного контекстного дерева $(\tau ,p)$ , затем

P\left({\hat {\ell }}_{n}(X_{0}^{n-1})\neq \ell (X_{0}^{n-1})\right)\longrightarrow 0,

когда $n\rightarrow \infty$ .

Байесовский информационный критерий (BIC)

Оценщик контекстного дерева по BIC со штрафной константой $c>0$ определяется как

{\hat {\tau }}_{\mathrm {BIC} }={\underset {\tau \in {\mathcal {T}}_{n}}{\arg \max }}\{\log L_{\tau }(X_{1}^{n})-c\,{\textrm {d}}f(\tau )\log n\}

Критерий наименьшего максимизатора (SMC)

Наименьший критерий максимизатора ^[3] рассчитывается путем выбора наименьшего дерева τ из набора деревьев-чемпионов C такого, что

\lim _{n\to \infty }{\frac {\log L_{\tau }(X_{1}^{n})-\log L_{\hat {\tau }}(X_{1}^{n})}{n}}=0

См. также

Ссылки

^ Jump up to: ^а ^б ^с ^д Риссанен, Дж (сентябрь 1983 г.). «Универсальная система сжатия данных». Транзакции IEEE по теории информации . 29 (5): 656–664. дои : 10.1109/TIT.1983.1056741 .
^ Jump up to: ^а ^б Беженаро, Дж. (2001). «Вариации вероятностных суффиксных деревьев: статистическое моделирование и прогнозирование семейств белков» . Биоинформатика . 17 (5): 23–43. дои : 10.1093/биоинформатика/17.1.23 . ПМИД 11222260 .
^ Jump up to: ^а ^б Галвес А, Галвес С, Гарсия Дж, Гарсия Н.Л., Леонарди Ф (2012). «Выбор контекстного дерева и извлечение лингвистической ритмики из письменных текстов» . Анналы прикладной статистики . 6 (5): 186–209. arXiv : 0902.3619 . дои : 10.1214/11-AOAS511 .
^ Дубнов С., Ассаяг Г., Лартильо О., Беженаро Г. (2003). «Использование методов машинного обучения для моделирования музыкальных стилей». Компьютер . 36 (10): 73–80. CiteSeerX 10.1.1.628.4614 . дои : 10.1109/MC.2003.1236474 .
^ Гальвес А., Гаривье А., Гассиат Э. (2012). «Совместная оценка пересекающихся моделей контекстного дерева». Скандинавский статистический журнал . 40 (2): 344–362. arXiv : 1102.0673 . дои : 10.1111/j.1467-9469.2012.00814.x .
^ Гальвес А, Лехербах Э (2008). «Стохастические цепочки с памятью переменной длины» . Серия ТИКСП . 38 : 117–133. arXiv : 0804.2050 .

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

[Bejenaro-2] Jump up to: ^а ^б Беженаро, Дж. (2001). «Вариации вероятностных суффиксных деревьев: статистическое моделирование и прогнозирование семейств белков» . Биоинформатика . 17 (5): 23–43. дои : 10.1093/биоинформатика/17.1.23 . ПМИД 11222260 .

[Galves-3] Jump up to: ^а ^б Галвес А, Галвес С, Гарсия Дж, Гарсия Н.Л., Леонарди Ф (2012). «Выбор контекстного дерева и извлечение лингвистической ритмики из письменных текстов» . Анналы прикладной статистики . 6 (5): 186–209. arXiv : 0902.3619 . дои : 10.1214/11-AOAS511 .

[Dubnov-4] Дубнов С., Ассаяг Г., Лартильо О., Беженаро Г. (2003). «Использование методов машинного обучения для моделирования музыкальных стилей». Компьютер . 36 (10): 73–80. CiteSeerX 10.1.1.628.4614 . дои : 10.1109/MC.2003.1236474 .

[Galves2-5] Гальвес А., Гаривье А., Гассиат Э. (2012). «Совместная оценка пересекающихся моделей контекстного дерева». Скандинавский статистический журнал . 40 (2): 344–362. arXiv : 1102.0673 . дои : 10.1111/j.1467-9469.2012.00814.x .

[Galves3-6] Гальвес А, Лехербах Э (2008). «Стохастические цепочки с памятью переменной длины» . Серия ТИКСП . 38 : 117–133. arXiv : 0804.2050 .

[1]

[2]

[3]

[4]

[5]

[6]

v т и Случайные процессы
Дискретное время	Процесс Бернулли Процесс ветвления процесс в китайском ресторане Процесс Гальтона – Ватсона Независимые и одинаково распределенные случайные величины Цепь Маркова Процесс Морана Случайное блуждание Петля стерта Самоизбегание Пристрастный Максимальная энтропия
Непрерывное время	Аддитивный процесс Бессельский процесс Процесс рождения-смерти чистое рождение Броуновское движение Мост Экскурсия Дробный Геометрический Меандр Процесс Коши Контактный процесс Случайное блуждание в непрерывном времени Процесс Кокса Процесс диффузии Броуновское движение Дайсона Эмпирический процесс Валочный процесс Процесс Флеминга-Вио Гамма-процесс Геометрический процесс Процесс Хоукса Процесс охоты Взаимодействующие системы частиц Диффузия Ито Ито-процесс Прыжковая диффузия Процесс перехода Процесс Леви Местное время Марковский аддитивный процесс Процесс Маккина – Власова Процесс Орнштейна – Уленбека Пуассоновский процесс Сложный Неоднородный Эволюция Шрамма – Лёвнера Семимартингалы Сигма-мартингейл Стабильный процесс Суперпроцесс Телеграфный процесс Дисперсионный гамма-процесс Винеровский процесс Венская колбаса
Оба	Процесс ветвления Гауссов процесс Скрытая модель Маркова (HMM) Марковский процесс Мартингейл Различия Местный Суб- Супер- Случайная динамическая система Регенеративный процесс Процесс продления Стохастические цепочки с памятью переменной длины Белый шум
Поля и прочее	Процесс Дирихле Гауссово случайное поле Мера Гиббса Модель Хопфилда Модель Изинга Модель Поттса Логическая сеть Марковское случайное поле перколяция Процесс Питмана-Йора Точечный процесс Кокс Пуассон Случайное поле Случайный график
Модели временных рядов	Модель авторегрессионной условной гетероскедастичности (ARCH) Модель авторегрессионного интегрированного скользящего среднего (ARIMA) Авторегрессионная (AR) модель Модель авторегрессии – скользящего среднего (ARMA) Модель обобщенной авторегрессии условной гетероскедастичности (GARCH) Модель скользящего среднего (MA)
Финансовые модели	Модель ценообразования биномиальных опционов Черный–Дерман–Игрушка Блэк – Карасински Блэк – Скоулз Чан – Каройи – Лонгстафф – Сандерс (CKLS) Чен Постоянная эластичность отклонения (CEV) Кокс – Ингерсолл – Росс (CIR) Гарман-Кольхаген Хит – Джарроу – Мортон (HJM) Хестон Хо-Ли Корпус – Белый Корн-Креер-Ленссен рынок ЛИБОР Рендлман-Барттер Волатильность SABR Ваш Уилки
Актуарные модели	Бюльманн Крамер-Лундберг Процесс риска Спарре-Андерсон
Модели массового обслуживания	Масса Жидкость Обобщенная сеть массового обслуживания М/Г/1 М/М/1 М/М/с
Характеристики	Тропы Кадлага Непрерывный Непрерывные пути Эргодический Сменный Феллер-непрерывный Гаусс–Марков Марков Смешивание Кусочно-детерминированный Предсказуемый Постепенно измеримый Самоподобный Стационарный обратимый во времени
Предельные теоремы	Центральная предельная теорема Теорема Донскера Теоремы о мартингальной сходимости Дуба Эргодическая теорема Теорема Фишера – Типпетта – Гнеденко. Принцип большого отклонения Закон больших чисел (слабый/сильный) Закон повторного логарифма Максимальная эргодическая теорема Теорема Санова Законы нуля–единицы ( Блюменталь , Борель–Кантелли , Энгельберт–Шмидт , Хьюитт–Сэвидж , Колмогоров , Леви )
Неравенства	Беркхолдер – Дэвис – Ганди Мартингейл Дуба Апкросс Дуба Кунита – Ватанабэ Марцинкевич–Зигмунд
Инструменты	Формула Кэмерона-Мартина Сходимость случайных величин Экспонента Долеана-Дада Теорема Дуба о разложении Теорема Дуба – Мейера о разложении Необязательная теорема Дуба об остановке Формула Дынкина Формула Фейнмана – Каца Фильтрация Теорема Гирсанова Бесконечно-малый генератор Ито интеграл Лемма Ито Теорема Карунена – Лёва Теорема Колмогорова о непрерывности Теорема Колмогорова о продолжении Метрика Леви – Прохорова Исчисление Маллявена Теорема о мартингальном представлении Необязательная теорема об остановке Prokhorov's theorem Квадратичная вариация Принцип отражения Skorokhod integral Теорема о представлении Скорохода Скороход пространство Снелл конверт Стохастическое дифференциальное уравнение Танака Остановка времени Интеграл Стратоновича Равномерная интегрируемость Обычные гипотезы Винерское пространство Классический Абстрактный
Дисциплины	Актуарная математика Теория управления Эконометрика Эргодическая теория Теория экстремальных ценностей (EVT) Теория больших отклонений Математические финансы Математическая статистика Теория вероятностей Теория массового обслуживания Теория обновления Теория руин Обработка сигналов Статистика Стохастический анализ Анализ временных рядов Машинное обучение
Список тем Категория