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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ехал — 1

грека — 3

через — 1

реку — 2

видит — 1

в — 2

реке — 1

рак — 2

сунул — 1

руку — 2

за — 1

греку — 1

цап — 1

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

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

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

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

Ехал → грека

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

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

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

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

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

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

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

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

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

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

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

через → реку

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

видит → грека

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

реке → рак

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

сунул → грека

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

за → руку

греку → цап

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

НАЧАЛО → Ехал

цап → КОНЕЦ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Что дальше

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

Текст:

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

Редактура:

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

Художник:

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

Корректор:

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

Вёрстка:

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

Соцсети:

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

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

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

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

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

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

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

Растровая и векторная графика: это как?
Растровая и векторная графика: это как?

Как-нибудь так…

Карьерный путь: руководитель группы в лаборатории ИИ Сбера
Карьерный путь: руководитель группы в лаборатории ИИ Сбера

Разговор с Алексеем Васильевым: управление проектами, учёба в ШАД и разработка систем ИИ.

Начинающим программистам: что такое фреймворки и библиотеки
Что такое порт в программировании
Что такое порт в программировании

С ними компьютер не путает, что и куда отправлять

Чем занимаются андроид-разработчики
Чем занимаются андроид-разработчики

И за что получают 103 тысячи рублей.

Как устроены онлайн-кинотеатры: техническая сторона
Как устроены онлайн-кинотеатры: техническая сторона

Главное из подкаста «Запуск завтра».

Объяснение асимметричного шифрования без математики
Объяснение асимметричного шифрования без математики

Чтобы лучше понять принцип работы.

Какой софт нужен, чтобы стать тестировщиком
Какой софт нужен, чтобы стать тестировщиком

Можно и без него, но с ним удобнее

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

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

Как установить Python на компьютер и начать на нём писать

Это занимает всего 10 минут.

easy