Цепь Маркова с частичными связями и переменным шаблоном

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ФАКУЛЬТЕТ ПРИКЛАДНОЙ МАТЕМАТИКИ И ИНФОРМАТИКИ

Кафедра математического моделирования и анализа данных

ЦЕПЬ МАРКОВА С ЧАСТИЧНЫМИ СВЯЗЯМИ И ПЕРЕМЕННЫМ ШАБЛОНОМ

Курсовая работа

Батуры Олега Владимировича

студента 4 курса,

специальность

«Компьютерная безопасность»

Научный руководитель:

доктор физ.-мат. наук,

заведующий кафедрой ММАД

Ю. С. Харин

Минск, 2016

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ФАКУЛЬТЕТ ПРИКЛАДНОЙ математики и информатики

Кафедра математического моделирования и анализа данных

ЗАДАНИЕ НА КУРСОВУЮ РАБОТУ

Студент Батура Олег Владимирович, 4 курс, 9 группа

1. Тема работы Цепь Маркова с частичными связями и переменным шаблоном

2. Срок сдачи студентом законченной работы________ 2016 г.

3.Перечень вопросов, подлежащих разработке

· Исследовать вероятностные характеристики модели цепи Маркова с частичными связями и переменным шаблоном. Найти -мерное распределение вероятностей .

· Построить компьютерную модель ЦМ с переменным шаблоном.

· Построить статистические оценки параметров модели при известной функции шаблона , исследовать свойства оценок.

· Построить оценки параметров модели при периодически изменяющемся, но неизвестном шаблоне.

Руководитель курсовой работы____________ / Ю. С. Харин/ ______ 2016 г.

Задание принял к исполнению____________ 2016 г.

СОДЕРЖАНИЕ

Введение. 4

1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ.. 5

1.1 Цепь Маркова с частичными связями и переменным шаблоном.. 5

1.2 Статистическое оценивание параметров ЦМ с переменным шаблоном.. 6

1.3 Алгоритмы вычисления оценки шаблона . 10

1.4 Алгоритмы вычисления оценки функции . 12

2.ПРАКТИЧЕСКАЯ ЧАСТЬ.. 13

2.1.Описание программы.. 13

2.2.Моделирование временного ряда длительности .. 14

2.3.Построение оценок максимального правдоподобия и . 15

2.4.Результаты экспериментов. 18

2.5.Вывод. 21

Заключение. 22

Список использованной литературы.. 23

Введение

При математическом моделировании сложных систем и процессов в различных научных сферах часто возникает необходимость построения вероятностно-статистических моделей дискретных временных рядов , где пространство состояний — конечное множество мощности с длинной памятью [1]. Известной моделью таких дискретных временных рядов является цепь Маркова достаточно высокого порядка , определяющего длину памяти; если , то цепь Маркова называется простой, если — сложной. Однако для такой модели число параметров растет экспоненциально при увеличении порядка : , и для статистического оценивания параметров требуется иметь реализацию не всегда доступной на практике длительности . В связи с этим актуальна проблема построения малопараметрических моделей цепей Маркова высокого порядка. В данной работе исследуется малопараметрическая модель цепи Маркова порядка с частичными связями ЦМ , рассмотренная в [2], для которой шаблон связей зависит от функции, определяющей его изменение во времени, исследуются ее вероятностные характеристики, строятся статистические оценки параметров модели.

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

Цепь Маркова с частичными связями и переменным шаблоном

По аналогии с [2] построим модель цепи Маркова с частичными связями и переменным шаблоном.

Пусть – однородная ЦМ( ), заданная на вероятностном пространстве ( ). Рассмотрим обобщение данной модели, когда шаблон зависит от времени :

причем:

В общем случае шаблон зависит от некоторой функции , определяющей его изменение. Простейшая модель такой зависимости – периодическая функция с некоторым периодом :

.

При произвольной модели зависимости шаблона от времени -мерное распределение вероятностей имеет вид:

Лемма 1.Случайная последовательность является неоднородной ЦМ порядка с частичными связями и -мерной матрицей вероятностей одношаговых переходов в момент времени

1.2 Статистическое оценивание параметров ЦМ с переменным шаблоном

Для статистического оценивания параметров ЦМ( ) с переменным шаблоном будем пользоваться методом максимального правдоподобия.

Рассмотрим задачу построения оценок максимального правдоподобия (ОМП) для параметров шаблона и стохастической матрицы по наблюдаемой реализации длительности .

Введем обозначения, пусть – мультииндекс -го порядка; – функция, которую условимся называть селектором -го порядка с параметрами и – индикатор события ; – начальное -мерное распределение вероятностей ЦМ ;

– частота -граммы для шаблона , удовлетворяющая условию нормировки:

Лемма 2.Для модели ЦМ с переменным шаблоном логарифмическая функция правдоподобия имеет вид:

В частности, когда имеется лишь 2 возможных шаблона связей , а закон изменения шаблона во времени задается некоторой функцией , то есть , логарифмическая функция правдоподобия запишется в виде

Для того, чтобы найти ОМП для матрицы при известной функции шаблона , необходимо решить задачу на условный экстремум:

В результате получаем условную ОМП для матрицы ( ):

Далее рассмотрим задачу построения ОМП для шаблона при известной функции смены шаблона такой, что .

Пусть существует стационарное распределение вероятностей ЦМ с переменным шаблоном . Допустим, что модель стационарна ( ), тогда распределение вероятностей -граммы в момент времени для шаблона будет иметь следующий вид:

Соответствующая частотная оценка вероятностей :

.

Энтропия -мерного распределения вероятностей запишется в виде:

Количество информации по Шеннону, содержащейся в -грамме о будущем символе :

С учетом принятых обозначений логарифмическая функция правдоподобия для оценки имеет следующий вид:

где – подстановочная оценка энтропии, получающаяся при подстановке вместо истинных значений их оценок { }.

Учитывая, что не зависит от , добавляя также не зависящее от слагаемое , а также используя тот факт, что:

приходим к следующей ОМП шаблона :

где – подстановочная оценка количества информации по Шеннону, получающаяся при подстановке вместо истинных значений их оценок { }.

Пусть – некоторый класс функций, которому принадлежит функция изменения шаблона во времени. Предположим, что все возможные значения шаблона известны. Тогда ОМП функции выглядит следующим образом:

1.3 Алгоритмы вычисления оценки шаблона

Для вычисления оценки шаблона при известном истинном значении числа связей и функции изменения шаблона во времени аналогично [2] предлагаются два алгоритма: алгоритм А1 полного перебора значений целевой функции ОМП шаблона и алгоритм А2 наращивания шаблона, обеспечивающий сокращение перебора. В случае, когда известно с точностью до числового промежутка: , для совместного оценивания , предлагается алгоритм А3 сокращения шаблона.

При описании алгоритмов А2, А3 мы используем вспомогательные обозначения. Для некоторого шаблона -го порядка , обозначим через подмножество всевозможных шаблонов -го порядка, получающихся вставкой в строку одного из новых символов ; символ вставляется так, чтобы новая строка символов обладала свойством шаблона: . Аналогично, через обозначим подмножество всевозможных шаблонов -го порядка, которые получаются вычеркиванием одного из символов за исключением первого.

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

Наибольшее быстродействие алгоритма А2, очевидно, достигается при . Этот подход аналогичен алгоритму расширения пространства признаков в задачах распознавания образов, который, как известно, может приводить к потере истинной гипотезы.

Алгоритм А3 базируется на очевидном свойстве вложенности моделей цепей Маркова:

в силу которого шаблон связей содержит . Вначале при алгоритмом А1 вычисляется начальный шаблон порядка ; затем

осуществляется сокращение этого шаблона по рекуррентной формуле

Затем на основе { } строится искомая оценка , где

1.4 Алгоритмы вычисления оценки функции

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

1. Если принадлежит некоторому конечному классу , а также известно, что данная функция – периодическая с заранее известным периодом , предлагается алгоритм полного перебора значений целевой функции ОМП функции изменения шаблона.

2. Если принадлежит некоторому конечному классу , периодическая, и ее период не превосходит некоторого наперед заданного порогового значения , предлагается алгоритм полного перебора , значений целевой функции.

3. Дискретная функция известна с точностью до параметра:

где – некоторый неизвестный -вектор параметров, . Предлагается алгоритм полного перебора всех возможных значений данного вектора, которые принадлежат .

ПРАКТИЧЕСКАЯ ЧАСТЬ

Описание программы

Построена компьютерная модель цепи Маркова с частичными связями и переменным шаблоном со следующими входными параметрами:

· глубина предыстории однородной цепи Маркова ЦМ .

· длина временного ряда с пространством состояний .

· Шаблоны и , которые повторяются с периодом

· Стохастическая матрица вероятностей одношаговых переходов для шаблонов:

В частном случае, при данная матрица имеет следующий вид:

Реализовано моделирование цепи Маркова с частичными связями и переменным шаблоном, построение оценок максимального правдоподобия матрицы вероятностей одношаговых переходов и переменного шаблона на основе смоделированного временного ряда. Далее более подробно рассматривается алгоритм работы программы.

2.2. Моделирование временного ряда длительности

Пользователем задаются первые элементов последовательности. Для моделирования элементов с нечетными номерами выбирается шаблон . Рассматривается -предыстория элемента. Распределениями вероятностей исхода для данных элементов являются строки матрицы , соответствующие состояниям предыдущих элементов

В частности, если предыстория элемента имеет вид

,

то, например, при

Элементы с четными номерами моделируются аналогичным образом с использованием шаблона

На каждом шаге моделирование происходит с помощью генератора псевдослучайных чисел [3], работающего по следующему алгоритму:

1. Генерируется число в диапазоне .

2.

В результате имеется временной ряд , где пространство состояний – конечное множество мощности .

2.3. Построение оценок максимального правдоподобия и

Логарифмическая функция правдоподобия имеет вид:

Задача на условный экстремум:

Поиск условной оценки максимального правдоподобия матрицы одношаговых переходов осуществляется путем приравнивания к нулю компонент градиента логарифмической функции правдоподобия:

Используя факт, что матрица стохастическая,

, условная оценка полностью определяется шаблоном

Для вычисления оценки шаблона при известном истинном значении числа связей можно воспользоваться алгоритмом полного перебора значений логарифмической функции правдоподобия.

В частности, при имеется следующая система уравнений:

где частота выпадения при предыстории .

Условной оценкой максимального правдоподобия является решение данной системы:

.

Логарифмическая функция правдоподобия перепишется в следующей форме:

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

Оценка максимального правдоподобия матрицы имеет вид: