Что такое цепи Маркова? 5 изящных применений реального мира

Возможно, вы слышали термин «цепь Маркова» раньше, но если вы не взяли несколько уроков по теории вероятностей или компьютерным алгоритмам

вы, вероятно, не знаете, кто они, как они работают и почему они так важны.

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

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

Марковские цепи 101

Допустим, вы хотите предсказать, какой будет погода завтра. Истинный прогноз — вид, выполненный опытными метеорологами

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

Представьте, что у вас был доступ к тридцати годам данных о погоде. Вы начинаете с самого начала, отмечая, что День 1 был солнечным. Вы продолжаете идти, отмечая, что День 2 также был солнечным, но День 3 был облачным, затем День 4 был дождливым, что привело к грозе в День 5, за которым последовало солнечное и ясное небо в День 6.

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

Вы делаете это по всему 30-летнему набору данных (который будет стоить всего 11 000 дней) и рассчитываете вероятности того, какой будет погода завтрашнего дня, исходя из сегодняшней погоды. Например, если сегодня солнечно, то:

50-процентная вероятность, что завтра снова будет солнечно.
30-процентная вероятность, что завтра будет облачно.
20-процентная вероятность, что завтра будет дождливо.

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

Переходные состояния

Это суть цепи Маркова. У вас есть отдельные состояния (в данном случае погодные условия), где каждое состояние может переходить в другие состояния (например, солнечные дни могут переходить в облачные дни), и эти переходы основаны на вероятностях. Если вы хотите предсказать, какой может быть погода через одну неделю, вы можете изучить различные вероятности в течение следующих семи дней и посмотреть, какие из них наиболее вероятны. Таким образом, марковская «цепь».

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

Как цепи Маркова используются в реальном мире

Изложив объяснение, давайте рассмотрим некоторые из реальных приложений, где они пригодятся. Вы можете быть удивлены, обнаружив, что вы использовали цепи Маркова все это время, не зная об этом!

Генерация имени

Вы когда-нибудь участвовали в настольных играх, MMORPG играх или даже в художественной литературе? Возможно, вы мучаетесь с именами своих персонажей (по крайней мере, в тот или иной момент) — и когда вы просто не можете придумать, какое имя вам нравится, вы, вероятно, прибегаете к онлайн-генератору имен

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

Все, что вам нужно, это набор писем, в котором у каждого письма есть список возможных последующих писем с вероятностями. Так, например, буква «М» имеет 60-процентный шанс привести к букве «А» и 40-процентный шанс привести к букве «Я». Сделайте это для целого ряда других букв, затем запустите алгоритм. Бум, у тебя есть имя, которое имеет смысл! (Во всяком случае, в большинстве случаев.)

Google PageRank

Одно из интересных следствий теории цепей Маркова состоит в том, что с увеличением длины цепочки (т. Е. Увеличением числа переходов состояний) вероятность того, что вы попадете в определенное состояние, сходится к фиксированному числу, и эта вероятность не зависит от того, где вы начинаете в системе.

Это чрезвычайно интересно, когда вы думаете о всей всемирной паутине как о системе Маркова, где каждая веб-страница является состоянием, а ссылки между веб-страницами представляют собой переходы с вероятностями. Эта теорема в основном говорит, что Независимо от того, с какой веб-страницы вы начинаете, вероятность того, что вы попадете на определенную веб-страницу X, будет фиксированной, предполагая «длительное время» серфинга..

Изображение предоставлено: 345Kai через Викимедиа

И это основа того, как Google ранжирует веб-страницы. Действительно, алгоритм PageRank является модифицированной (читай: более продвинутой) формой алгоритма цепей Маркова.

Чем выше «фиксированная вероятность» попадания на определенную веб-страницу, тем выше ее PageRank. Это связано с тем, что более высокая фиксированная вероятность подразумевает, что на веб-странице есть много входящих ссылок с других веб-страниц — и Google предполагает, что если на веб-странице есть много входящих ссылок, то она должна быть ценной. Чем больше входящих ссылок, тем они ценнее.

Конечно, это сложнее, но это имеет смысл. Почему такой сайт, как About.com, получает более высокий приоритет на страницах результатов поиска? Потому что оказывается, что пользователи, как правило, приходят туда, когда они выходят в Интернет. Интересно, не правда ли?

Ввод слова Предсказание

На мобильных телефонах уже десятилетиями ведется интеллектуальная типизация, но можете ли вы догадаться, как эти прогнозы делаются? Используете ли вы Android (альтернативные варианты клавиатуры

) или iOS (альтернативные варианты клавиатуры

), есть большая вероятность, что ваше приложение использует цепочки Маркова.

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

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

Subreddit Simulation

Если вы никогда не использовали Reddit, мы рекомендуем вам хотя бы проверить этот увлекательный эксперимент под названием / r / SubredditSimulator.

Проще говоря, Subreddit Simulator берет большую часть ВСЕХ комментариев и названий, сделанных в многочисленных сообществах Reddit, а затем анализирует пословную структуру каждого предложения. Используя эти данные, он генерирует вероятности из слова в слово, а затем использует эти вероятности для создания заголовков и комментариев с нуля.

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

И самая забавная — или, возможно, самая тревожная — часть всего этого состоит в том, что сгенерированные комментарии и заголовки часто могут быть неотличимы от тех, которые сделаны реальными людьми. Это абсолютно увлекательно.

Знаете ли вы какие-либо другие интересные варианты использования цепей Маркова? Есть вопросы, на которые еще нужно ответить? Дайте нам знать в комментарии ниже!