Цепи Маркова

Наконец перед садовником стоит задача, какую стратегию нужно выбрать для максимизации среднего ожидаемого дохода. Может рассматриваться два типа задач: с конечным и бесконечным количеством этапов. В данном случае когда-нибудь деятельность садовника обязательно закончится. Кроме того, визуализаторы решают задачу принятия решений для конечного числа этапов. Пусть садовник намеревается прекратить свое занятие через N лет. Наша задача теперь состоит в том, чтобы определить оптимальную стратегию поведения садовника, то есть стратегию, при которой его доход будет максимальным. Конечность числа этапов в нашей задаче проявляется в том, что садовнику не важно, что будет с его сельскохозяйственным угодьем на N+1 год (ему важны все года до N включительно). Теперь видно, что в этом случае задача поиска стратегии превращается в задачу динамического программирования. Если через fn(i) обозначить максимальный средний ожидаемый доход, который можно получить за этапы от n до N включительно, начиная из состояния с номером i, то несложно вывести рекуррентное соотношение, связывающее fn(i) с числами fn+1(j):

fn(i) = maxk{∑j=1mpijk[rijk + fn+1(j)]}, n = 1, 2, …, N

Здесь k - номер используемой стратегии. Это уравнение основывается на том, что суммарный доход rijk + fn+1(j) получается в результате перехода из состояния i на этапе n в состояние j на этапе n+1 с вероятностью pijk.

Теперь оптимальное решение можно найти, вычисляя последовательно fn(i) в нисходящем направлении (n = N…1). При этом введение вектора начальных вероятностей в условие задачи не усложнит ее решение.

Моделирование сочетаний слов в тексте

Рассмотрим текст, состоящий из слов w. Представим процесс, в котором состояниями являются слова, так что когда он находится в состоянии (Si) система переходит в состояние (sj) согласно матрице переходных вероятностей. Прежде всего, надо «обучить» систему: подать на вход достаточно большой текст для оценки переходных вероятностей. А затем можно строить траектории марковской цепи. Увеличение смысловой нагрузки текста, построенного при помощи алгоритма цепей Маркова возможно только при увеличении порядка, где состоянием является не одно слово, а множества с большей мощностью - пары (u, v), тройки (u, v, w) и т.д. Причем что в цепях первого, что пятого порядка, смысла будет еще немного. Смысл начнет появляться при увеличении размерности порядка как минимум до среднего количества слов в типовой фразе исходного текста. Но таким путем двигаться нельзя, потому, что рост смысловой нагрузки текста в цепях Маркова высоких порядков происходит значительно медленнее, чем падение уникальности текста. А текст, построенный на марковских цепях, к примеру, тридцатого порядка, все еще будет не настолько осмысленным, чтобы представлять интерес для человека, но уже достаточно схожим с оригинальным текстом, к тому же число состояний в такой цепи будет потрясающим.

Эта технология сейчас очень широко применяется (к сожалению) в Интернете для создания контента веб-страниц. Люди, желающие увеличить трафик на свой сайт и повысить его рейтинг в поисковых системах, стремятся поместить на свои страницы как можно больше ключевых слов для поиска. Но поисковики используют алгоритмы, которые умеют отличать реальный текст от бессвязного нагромождения ключевых слов. Тогда, чтобы обмануть поисковики используют тексты, созданные генератором на основе марковской цепи. Есть, конечно, и положительные примеры использования цепей Маркова для работы с текстом, их применяют при определении авторства, анализе подлинности текстов.

Цепи Маркова и лотереи

В некоторых случаях вероятностная модель используется в прогнозе номеров в различных лотереях. По-видимому, использовать цепи Маркова для моделирования последовательности различных тиражей нет смысла. То, что происходило с шариками в тираже, никак не повлияет на результаты следующего тиража, поскольку после тиража шары собирают, а в следующем тираже их укладывают в лоток лототрона в фиксированном порядке. Связь с прошедшим тиражом при этом теряется. Другое дело последовательность выпадения шаров в пределах одного тиража. В этом случае выпадение очередного шара определяется состоянием лототрона на момент выпадения предыдущего шара. Таким образом, последовательность выпадений шаров в одном тираже является цепью Маркова, и можно использовать такую модель. При анализе числовых лотерей здесь имеется большая трудность. Состояние лототрона после выпадения очередного шара определяет дальнейшие события, но проблема в том, что это состояние нам неизвестно. Все что нам известно, что выпал некоторый шар. Но при выпадении этого шара, остальные шары могут быть расположены различным образом, так что имеется группа из очень большого числа состояний, соответствующая одному и тому же наблюдаемому событию. Поэтому мы можем построить лишь матрицу вероятностей переходов между такими группами состояний. Эти вероятности являются усреднением вероятностей переходов между различными отдельными состояниями, что конечно, снижает эффективность применения модели марковской цепи к числовым лотереям.

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

8

Управляемые цепи Маркова. Выбор стратегии.

Завод по изготовлению телевизоров, находясь в состоянии 1, может увеличить спрос путем организации рекламы. Это требует добавочных затрат и уменьшает доход. В состоянии 2 завод может увеличить вероятность перехода в состояние 1 путем увеличения затрат на исследования. Выделим две стратегии. Первая состоит в отказе от затрат на рекламу и исследования, а вторая - в согласии на них. Пусть матрицы переходных вероят­ностей и матрицы доходов для данных стратегий имеют вид:

В рассмотренной ситуации имеет место управляемая цепь Мар­кова. Управление соответствует выбору стратегии.

Пусть каждому состоянию соответствует ко­нечное множество решений (или альтернатив), элементы которого обозначим номерами . Пространством стратегий К назы­вается прямое произведение множеств решений .

Пусть в i-м состоянии имеется не одно, а  множеств пере­ходных вероятностей . При имеем случай неуправляемой цепи Маркова. Если система находится в состоянии и принимается ре­шение то:

- она получает доход ;

- ее состояние в следующий момент времени определяется вероят­ностью , где - вероятность того, что система из состояния при выборе решения перейдет в состояние .

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

Кроме того,

,       при всех и .

Управляемой цепью Маркова называется конструкция, зада­ваемая параметрами , где К-решения,  Р-вероятности переходов, r-доходы. Доход, полученный за несколько шагов, является случайной величиной, зависящей от начального состоя­ния и принимаемых в каждый момент времени решений.

Назовем решение, принимаемое в конкретный момент, частным управлением. Тогда управление есть последовательность решений в моменты n = 1, 2, ... Качество управления можно оценить сред­ним суммарным доходом (при конечном времени) или среднем дохо­дом в единицу времени (при бесконечном времени).

Пусть  (2)

Стратегией называется последовательность решений , где - вектор вида (2), i-я компонента которого, обозначаемая через , является решением, принимаемым в состоянии в момент п. Другими словами, задание стратегии означает пол­ное описание в каждый момент времени t =1, 2, ..., п, ... конкретных решений, которые должны были бы приниматься в i-м состоянии , если бы система находилась в нем в рассматриваемый момент.

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

Обозначим произвольную конечную часть стратегии через . Пусть зафиксированы произвольная стратегия некоторый момент времени п. Если в этот момент система находилась в состоянии , то в следующий (п+1)-й момент времени она будет находиться в состоянии с вероятностью , где . Тогда матрица переходных ве­роятностей в момент п имеет вид

Таким образом, при фиксированной стратегии получаем цепь Маркова с матрицами перехода

Обозначим - вектор суммарных средних доходов, полученных до любого момента n включительно,  для некоторой стратегии . Стратегия максимизирующая , т.е. удовлетворяющая неравенству ≥ при любых   называется оптимальной.

Верны следующее утверждения:

Утверждение 1. Для бесконечного времени существует опти­мальная стационарная стратегия.

Утверждение 2. Для конечного времени существует оп­тимальная марковская стратегия.

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

Список используемой литературы

1.            http://rain.ifmo.ru/cat/view.php/theory/processes-automata/markov-2008

2.            http://ru.wikipedia.org/wiki/Цепь_Маркова

3.            http://www.statsoft.ru/home/portal/taskboards/mark.htm

4.            Айвазян С. А. Прикладная статистика и основы эконометрики: Учебник для вузов / С.А. Айвазян, В.С. Мхитарян; ГУ-ВШЭ. М.: ЮНИТИ, 1998.

5.            «Теория выбора и принятия решений»: учебное пособие. И.М. Макаров, Т.М. Виноградская, А.А. Рубчинский, В.Б. Соколов. Москва, изд. «Наука».

6.            Соколов Г.А., Чистякова Е.А. "Теория вероятностей. Управляемые цепи Маркова в экономике" 248 стр. 2005г.

21