Другое

Цепи Маркова для чайников — это просто: примеры решения задач

Lorem ipsum dolor

Цепи Маркова применяются во многих компаниях и организациях. С их помощью можно:

  • предсказать погоду,

  • разработать маркетинговую стратегию,

  • предугадать результат каких-то действий,

  • разработать программное обеспечение, прогнозирующее случайное событие,

  • генерировать случайные числа,

  • генерировать случайный текст,

  • и др.

По сути, «марковские цепи» — это последовательность событий, при которой каждое последующее событие косвенно зависит от предыдущего. Таким образом, цепь Маркова формирует последовательность псевдослучайных событий. Именно для этой цели ее чаще всего и применяют.

Цепь Маркова

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

Цепи Маркова на словах для чайников

Представим, что вы хотите спрогнозировать погоду на завтра. Вы точно понимаете, что за один день кардинально погода не меняется. На ее изменение влияет много факторов, например:

  • скорость и направление ветра,

  • движение атмосферных масс,

  • положение Луны относительно Земли,

  • атмосферное давление,

  • и др.

Факторов, определяющих погоду, очень много, но они вам пока и не нужны, чтобы предсказать погоду на завтра. Вы понимаете, что, раз кардинально погода за один день не меняется, значит, она каким-то образом связана с сегодняшней погодой. Например, если сегодня дождь и температура около +10, тогда вероятность, что завтра будет солнечно и +30, очень низкая. Скорее всего, завтра температура будет «больше или меньше», а также будет идти или не идти дождь. Чтобы качественней прогнозировать погоду, вам нужно понаблюдать за ее зависимостями в течение нескольких лет. 

Например, после наблюдений вы знаете, что если сегодня идет дождь, то вероятность солнечного дня составляет 1 из 4-х случаев, а вероятность пасмурного дня — 3 из 4-х. Поэтому на сегодня мы можем предположить, что завтра будет солнечно или пасмурно, но, скорее всего, пасмурно, так как так было в 3-х из 4-х случаев. По такому принципу можно прогнозировать погоду на несколько дней вперед. Это простой пример, в котором мы взяли только два вероятных события: солнечно либо пасмурно. На деле вероятных событий будет куда больше, например:

  • может быть опять дождь, а не просто пасмурно,

  • может быть снег,

  • может полдня лить дождь, а полдня будет солнечно,

  • и др.

Чтобы прогнозировать погоду на несколько дней, нужно учесть еще несколько факторов. Например, если будет переход из дождливого дня в солнечный, тогда меняется система вероятностей. Когда будет солнечный день, тогда вероятность, что завтра опять будет солнце, будет 3 из 4-х, а вероятность дождливого дня будет 1 из 4-х.

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

Из всего сказанного получается, что цепь Маркова не создает точных долгосрочных стратегий, а напрямую зависит от «сегодняшнего» состояния объекта, для которого нужно вычислить вероятность. То есть в случае с погодой для более точного результата цепь Маркова лучше использовать каждый день при прогнозе на следующий день.

Цепь Маркова: модель

С формальной точки зрения цепь Маркова представляет собой «автомат», который генерирует вероятности, в зависимости от входных данных. По факту цепь Маркова будет иметь вид матрицы, где будет прописана вероятность наступления следующего события, отталкиваясь от нынешнего.

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

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

Вправо вероятность состояний. Вниз нынешнее состояние погоды

Идет дождь

Пасмурно

Солнечно

Идет дождь

0,65

0,25

0,10

Пасмурно

0,25

0,55

0,20

Солнечно

0,10

0,25

0,65

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

Заключение

Мы простыми словами рассказали и объяснили, что такое цепи Маркова. Марковские цепи — это череда вероятных событий, которые зависят друг от друга. Цепи Маркова можно реализовать на разных языках, но наиболее распространенный — это Python. Как они реализуются на языке программирования — мы расскажем в следующих статьях.

Кстати, самое известное применение цепи Маркова — это генерация текста. Каждый пользователь сталкивался в разных приложениях с такой функцией, как автодополнение слов и предложений. Это алгоритм цепи Маркова предсказывает вероятность использования того или иного слова.

Схожие статьи

Синтаксический анализатор методом рекурсивного спуска. Что это такое?
Другое

Синтаксический анализатор методом рекурсивного спуска. Что это такое?

С чего начать путь программиста: какой язык подойдет на начальном этапе
Другое

С чего начать путь программиста: какой язык подойдет на начальном этапе

Среда для резервного копирования в Mac OS X
Другое

Среда для резервного копирования в Mac OS X

Музыка из кейгенов и кряков, как работает эта программа
Другое

Музыка из кейгенов и кряков, как работает эта программа