Что такое цепи Маркова и как они работают
Что такое цепи Маркова и как они работают
Простейший генератор текста на цепях Маркова Пишем Чехова на цепях Маркова: готовая библиотека Генератор статей для Кода

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ехал — 1

гре­ка — 3

через — 1

реку — 2

видит — 1

в — 2

реке — 1

рак — 2

сунул — 1

руку — 2

за — 1

гре­ку — 1

цап — 1

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

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

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

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

Ехал → грека

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

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

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

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

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

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

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

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

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

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

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

через → реку

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

видит → грека

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

реке → рак

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

сунул → грека

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

за → руку

гре­ку → цап

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

НАЧАЛО → Ехал

цап → КОНЕЦ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Что дальше

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

Текст:

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

Редак­ту­ра:

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

Худож­ник:

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

Кор­рек­тор:

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

Вёрст­ка:

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

Соц­се­ти:

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