Что такое цепи Маркова и как они работают

Что такое цепи Маркова и как они работают

Простой способ сгенерировать много текста, который будет похож на настоящий.

В «Коде» уже вышло несколько проектов, где мы генерировали какой-то случайный текст, чтобы показать его пользователю:

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

Главный минус такого подхода — вы делаете всю работу за компьютер. Вы сами жёстко задаёте структуру каждого предложения. Такой текст вас ничем не удивит, потому что вы чётко знаете, сколько предложений у вас в шаблоне и из каких частей состоит каждое.

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

Что такое цепь Маркова

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

Допустим, у нас есть событие «Взять зонт», которое всегда идёт только после события «Идёт дождь». Даже если сейчас середина декабря, кругом снег, но внезапно случилась оттепель и пошёл дождь — следом за ним по этой логике будет событие «Взять зонт». 

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

Чтобы было понятнее, разберём на тексте.

Текст и цепи Маркова

Возьмём такую скороговорку:

Ехал грека через реку, видит грека — в реке рак, сунул грека руку в реку, рак за руку греку цап.

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

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

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

Считаем слова

Посчитаем, сколько раз встречается каждое слово в нашем тексте:

Ехал — 1

грека — 3

через — 1

реку — 2

видит — 1

в — 2

реке — 1

рак — 2

сунул — 1

руку — 2

за — 1

греку — 1

цап — 1

Ещё нам нужно пометить, что после «цап» ничего нет, просто ставим точку. 

👉 Такие отдельные элементы в цепи Маркова называют звеньями. А цепь как раз и состоит из звеньев :-)

Составляем пары

Теперь составим пары связанных событий. Связные — это когда одно событие идёт только после конкретного другого события. В нашем тексте первая пара будет такая:

Ехал → грека

Так как в исходном тексте слово «Ехал» только одно и после него идёт «грека», то алгоритм запомнит, что после «Ехал» нужно обязательно поставить только «грека», без вариантов. 

А вот со второй парой уже поинтереснее:

грека → (через, в, руку)

Чтобы было понятно, откуда появились три слова, выделим жирным все слова сразу после греки:

Ехал грека через реку, видит грека — в реке рак, сунул грека руку в реку, рак за руку греку цап.

Получается, что наш алгоритм, когда дойдёт до «грека», с какой-то долей вероятности выберет одно из трёх следующих слов.

Сразу разберёмся, как считать доли вероятности — это пригодится нам на следующем этапе. У нас есть пара грека → (через, в, руку), при этом «через» у нас встречается 1 раз, «в» — 2 раза, и «руку» — 2 раза, а всего эти слова вместе в тексте встречаются 5 раз. Получается, что после «грека» вероятность продолжения текста:

  • словом «через» — ⅕, 
  • словом «в» — ⅖ 
  • словом «реку» — ⅖.

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

Значения этих вероятностей пригодятся нам при составлении схемы связей.

Составим точно так же остальные пары:

через → реку

реку → (видит, рак)

видит → грека

в → (реке, реку)

реке → рак

рак → (сунул, за)

сунул → грека

руку → (в, греку)

за → руку

греку → цап

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

НАЧАЛО → Ехал

цап → КОНЕЦ

Составим схему связей

Это необязательный этап, но с ним может быть понятнее, как работает алгоритм в целом. 

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

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

Что такое цепи Маркова и как они работают

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

Ехал грека руку греку цап.

Ехал грека через реку видит грека через реку видит грека руку греку цап.

Ехал грека через реку видит грека руку в реке рак сунул грека руку греку цап.

Всё, что делает алгоритм, — идёт по схеме и переходит по стрелочкам. Это и есть цепи Маркова. 

Как сделать текст более осмысленным

У нас в примере про греку алгоритм всегда выдаёт чушь, потому что исходный текст (корпус) слишком маленький для составления связей и в нём мало слов. Если мы возьмём текст побольше, например, Конституцию или «Войну и мир», то алгоритм сможет составлять текст, похожий на язык оригинала, как будто его написал человек.

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

Понимает ли сам алгоритм смысл сказанного?

Нет. Всё, что делает алгоритм, — выдаёт следующее слово на основе вероятностей. Ему неважно, что получается в итоге, потому что алгоритм не умеет думать.

Что дальше

Следующий шаг — написать свой алгоритм для цепей Маркова и нагенерировать какой-то текст про компьютеры. Некоторые редакции так уже делают, пора и нам.

Текст:

Михаил Полянин

Редактура:

Максим Ильяхов

Художник:

Даня Берковский

Корректор:

Ирина Михеева

Вёрстка:

Мария Дронова

Соцсети:

Олег Вешкурцев

Алгоритмы — основа разработки
Изучите алгоритмы, чтобы легко проходить ИТ-собеседования и делать более совершенный софт. Старт — бесплатно. После обучения — помощь с трудоустройством.
Новый уровень тут
Алгоритмы — основа разработки Алгоритмы — основа разработки Алгоритмы — основа разработки Алгоритмы — основа разработки
Получите ИТ-профессию
В «Яндекс Практикуме» можно стать разработчиком, тестировщиком, аналитиком и менеджером цифровых продуктов. Первая часть обучения всегда бесплатная, чтобы попробовать и найти то, что вам по душе. Дальше — программы трудоустройства.
Начать карьеру в ИТ
Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию
Еще по теме
NFT — новые модные токены. Зачем они нужны и не развод ли это?
NFT — новые модные токены. Зачем они нужны и не развод ли это?

Объясняем на Аллегровой.

easy
Гид: что изучать, чтобы получить ИТ-профессию

Планы на будущий год.

easy
Markdown: что это и кому нужно
Markdown: что это и кому нужно

Для всех, кто пишет контент, сайты и программы.

easy
TypeScript — как JavaScript, но может больше
TypeScript — как JavaScript, но может больше

Способ избежать проблем JavaScript в больших проектах.

easy
Зарплата 180 000. Что нужно уметь разработчику
Зарплата 180 000. Что нужно уметь разработчику

Кто готов платить эти деньги и за что.

easy
Как работают алгоритмы кодирования в радиосвязи
Как работают алгоритмы кодирования в радиосвязи

Как вообще это возможно — что по воздуху к нам прилетает видео?

medium
С чего начать в IT

Даже если вы абсолютный гуманитарий — выход есть.

easy
Как запустить операционку внутри операционки внутри операционки
Что такое виртуализация

Как запустить операционку внутри операционки внутри операционки

hard
Как это работает: вход на сайты через соцсети
Как это работает: вход на сайты через соцсети

Всё дело в единой авторизации.

easy
Объясни мне: как устроен интернет
Объясни мне: как устроен интернет

Часть 1: Компьютеры и сеть.

easy
Если у вас ребёнок: об информатике
easy
Как устроен и зачем нужен квантовый компьютер

Это прорыв в технологиях или очередной биткоин?

medium
Как автомобильный навигатор находит самый быстрый путь
Как автомобильный навигатор находит самый быстрый путь

Или самый короткий

medium
easy