Створюємо генератор тексту на основі ланцюгів Маркова: теорія і практика


Дізнайтесь більше про нові кар'єрні можливості в EchoUA. Цікаві проекти, ринкова оплата, гарний колектив. Надсилайте резюме та приєднуйтеся до нас.

Розповідає Олександр Деджу, студент Make School’s Product College


Ця стаття дає загальне уявлення про те, як генерувати тексти за допомогою моделювання марківських процесів. Зокрема, ми ознайомимося з ланцюгами Маркова, на практиці реалізуємо невеликий генератор тексту на Python.

 

Спершу випишемо потрібні, але дотепер не дуже зрозумілі нам визначення зі сторінки у Вікіпедії, щоб хоч трохи уявляти, з чим маємо справу:

Марковський процес – випадковий процес, еволюція якого після певного заданого значення часового параметра t  не залежить від еволюції, яка передувала t, за умови, що значення процесу в цей момент було фіксованим.

Марковський ланцюг – окремий випадок марковського процесу, коли простір його станів дискретний, тобто не більше за рахунковий.

Що все це означає? Давайте розбиратися.

Засади

Перший приклад гранично простий. Використовуючи речення з дитячої книжки, ми освоїмо базову концепцію ланцюга Маркова, а також визначимо, що означають у нашому контексті корпус, ланки, розподіл ймовірностей і гістограми. Попри те, що речення наведене англійською мовою, суть теорії легко буде зрозуміти.

Це речення і є корпус, тобто база, на основі якої далі генеруватиметься текст. Воно складається з восьми слів, але при цьому унікальних слів тільки п’ять – це ланки (ми говоримо про марковський ланцюг). Для наочності забарвимо кожну ланку у свій колір:

І випишемо кількість появ кожної ланки у тексті:

На картинці вище видно, що слово “fish” з’являється в тексті у 4 рази частіше, ніж кожне з інших слів (“One”, “two”, ” red”, ” blue”), тобто ймовірність зустріти в нашому корпусі слово “fish” у 4 рази вище, ніж ймовірність зустріти кожне інше слово з наведених на рисунку. Говорячи мовою математики, ми можемо визначити закон розподілу випадкової величини і обчислити, з якою ймовірністю одне зі слів з’явиться в тексті після поточного. Ймовірність обчислюється так: треба поділити число появ потрібного нам слова в корпусі на загальне число всіх слів у ньому. Для слова “fish” ймовірність – 50 %, оскільки воно з’являється 4 рази у реченні з 8 слів. Для кожної з інших ланок ця ймовірність дорівнює 12,5 % (1/8).

Графічно показати розподіл випадкових величин можна за допомогою гістограми. В даному випадку, наочно видно частоту появи кожної ланки в реченні:

Отже, наш текст складається зі слів та унікальних ланок, а розподіл ймовірності появи кожної ланки у реченні ми показали на гістограмі. Якщо Вам здається, що мати справу зі статистикою не варто, прочитайте наш переклад, який вас переконає. І, можливо, збереже Вам життя.

Суть визначення

Тепер додамо до нашого тексту елементи, які завжди маються на увазі, але не озвучуються в повсякденній мові – початок і кінець речення:

Будь-яке речення містить ці невидимі “початок” і ” кінець”, додамо їх як ланки до нашого розподілу:

Повернемося до визначення, наведеного на початку статті:

Марковський процес – випадковий процес, еволюція якого після певного заданого значення часового параметра t  не залежить від еволюції, яка передувала t, за умови, що значення процесу в цей момент було фіксованим.

Марковський ланцюг – окремий випадок марковського процесу, коли простір його станів дискретний, тобто не більше за рахунковий.

Так що ж це означає? Відверто кажучи, ми моделюємо процес, у якому стан системи в наступний момент часу залежить тільки від її стану в нинішній момент, і ніяк не залежить від усіх попередніх станів.

Уявіть, що перед Вами вікно, яке відображає тільки поточний стан системи (у нас, це одне слово), і Вам треба визначити, яким буде наступне слово, ґрунтуючись тільки на даних, наведених у цьому вікні. У нашому корпусі слова йдуть одне за іншим за схемою:

У такий спосіб формуються пари слів (навіть у кінця речення є своя пара – порожнє значення):

Згрупуємо ці пари за першим словом. Ми побачимо, що у кожного слова є свій набір ланок, які в контексті нашого речення можуть йти за ним:

Подамо цю інформацію в інший спосіб – кожній ланці поставимо відповідний масив з усіх слів, які можуть з’явитися в тексті після цієї ланки:

Розберемо детальніше. Ми бачимо, що кожна ланка має слова, які можуть стояти після неї в реченні. Якби ми показали наведену вище схему  комусь ще, ця людина з деякою ймовірністю могла б реконструювати наше початкове речення, тобто корпус.

Приклад. Розпочнемо зі слова “Start”. Далі вибираємо слово “One”, оскільки за нашою схемою це єдине слово, яке може йти за початком речення. За словом “One” також може слідувати тільки одно слово – “fish”. Тепер нове речення в проміжному варіанті:“One fish”. Далі ситуація ускладнюється – за “fish” можуть з рівною імовірністю в 25 % йти слова “two”, ” red”, ” blue” і кінець речення “End”. Якщо ми припустимо, що наступне слово – “two”, реконструкція продовжиться, але ми можемо вибрати і ланку “End”. У такому разі на основі нашої схеми буде випадково згенеровано речення, що істотно відрізняється від корпусу, – “One fish”.

Ми щойно змоделювали марковський процес – визначили кожне наступне слово винятково на підставі знань про поточне. Давайте для повного засвоєння матеріалу побудуємо діаграми, що відображають залежності між елементами всередині нашого корпусу. Овали є ланками. Стрілки ведуть до потенційних ланок, які можуть йти за словом в овалі. Біля кожної стрілки – ймовірність, з якою наступна ланка з’явиться після поточної:

Відмінно! Ми засвоїли необхідну інформацію, щоб рухатися далі та розбирати складніші моделі.

Розширюємо словникову базу

У цій частині статті ми будуватимемо модель за тим самим принципом, що і раніше, але в описі опустимо деякі кроки. Якщо виникнуть утруднення, повертайтеся до теорії в першому блоці.

Візьмемо ще чотири цитати того ж автора (також англійською, нам це не завадить):

“Today you are you. That is truer than true. There is no one alive who is you – er than you”.

“You have brains in your head. You have feet in your shoes. You can steer yourself any direction you choose. You’re on your own”.

“The more that you read, the more things you will know. The more that you learn, the more places you’ll go”.

“Think left and think right and think low and think high. Oh, the thinks you can think up if only you try”.

Складність корпусу збільшилася, але в нашому випадку це тільки плюс – тепер генератор тексту зможе видавати більш осмислені речення. Справа в тому, що в будь-якій мові є слова, які зустрічаються частіше, порівняно з іншими (наприклад, прийменник “в” ми використовуємо набагато частіше, ніж слово “кріогенний”). Чим більше слів у нашому корпусі (отже, і залежностей між ними), тим більше у генератора інформації про те, яке слово найімовірніше має з’явитися в тексті після поточного.

Перечитайте абзац, наведений вище, кілька разів, щоб розібратися. Зверніть увагу на те, що вкладений словник у даному разі – це та сама гістограма, бо він допомагає нам відстежувати ланки і частоту їх появи в тексті відносно інших слів. Зазначимо, що навіть така словникова база дуже мала для належної генерації текстів природною мовою – вона повинна містити понад 20 000 слів, а краще більше як 100 000, найкраще – понад 500 000. Однак розглянемо ту словникову базу, яку маємо.

Ланцюг Маркова в даному випадку будується аналогічно першому прикладу – кожне наступне слово вибирається тільки на підставі знань про поточне слово, всі інші слова не враховуються. Завдяки зберіганню у словнику даних про те, які слова з’являються частіше за інші, ми можемо при виборі прийняти зважене рішення. Давайте розглянемо на прикладі:

more :[things: 1, places: 1, that: 2]

Якщо поточним словом є слово “more”, то після нього можуть з рівною ймовірністю у 25 % йти слова “things” і “places”, і з ймовірністю у 50 % – слово “that”. Проте ймовірність може бути й такою: всі рівні між собою.

think :[high: 1, up: 1, right: 1, low: 1, left: 1]

Робота з вікнами

Дотепер ми розглядали тільки вікна розміром в одне слово. Можна збільшити розмір вікна, щоб генератор тексту видавав краще “вивірені” речення. Це означає, що чим більше вікна, тим менше буде відхилень від корпусу при генерації. Збільшення розміру вікна відповідає переходу ланцюга Маркова до вищого порядку. Раніше ми будували ланцюг першого порядку, для вікна з двох слів вийде ланцюг другого порядку, з трьох – третього, і так далі.

Вікно – це ті дані в поточному стані системи, які використовуються для прийняття рішень. Якщо ми поєднаємо велике вікно і маленький набір даних, то, швидше за все, щоразу отримуватимемо те саме речення. Давайте візьмемо словникову базу з нашого першого прикладу і розширимо вікно до розміру 2:

Розширення привело до того, що біля кожного вікна тепер тільки один варіант наступного стану системи, і що б ми не робили, то завжди отримуватимемо те саме речення, ідентичне нашому корпусу. Отже, щоб експериментувати з вікнами, і щоб генератор тексту повертав унікальний контент, запасіться словниковою базою від 500 000 слів.

Реалізація на Python

Структура даних Dictogram

Dictogram (dict – вбудований тип даних словник в Python), який відображатиме залежність між ланками та їх частотою появи в тексті, тобто їх розподіл. При цьому структура даних матиме потрібну нам властивість словника – час виконання програми не залежатиме від об’єму вхідних даних, а це означає, що ми створюємо ефективний алгоритм.

import randomclass Dictogram (dict): def __init__ (self, iterable=None): # Ініціалізували наш розподіл як новий об'єкт класу, # додаємо наявні елементи super (Dictogram, self).__init__() self.types = 0 # число унікальних ключів в розподілі self.tokens = 0 # загальна кількість усіх слів в розподілі if iterable: self.update (iterable) def update (self, iterable): # Оновлюємо розподіл елементами з наявного # итерируемого набору даних for item in iterable: if item in self: self[item] += 1 self.tokens += 1 else: self[item] = 1 self.types += 1 self.tokens += 1 def count (self, item): # Повертаємо значення лічильника елементу, або 0
if item in self: return self[item] return 0 def return_random_word (self): random_key = random.sample (self, 1)  # Інший спосіб: # random.choice (histogram.keys()) return random_key[0] def return_weighted_random_word (self): # Згенерувати псевдовипадкове число між 0 і (n - 1), # де n - загальне число слів random_int = random.randint (0, self.tokens - 1) index = 0 list_of_keys = self.keys () # вивести 'випадковий індекс:', random_int for i in range (0, self.types): index += self[list_of_keys[i]] # вивести індекс if (index > random_int): # вивести list_of_keys[i] return list_of_keys[i]

У конструктор структурі Dictogram можна передати будь-який об’єкт, за яким можна ітеріруватися. Елементами цього об’єкта будуть слова для ініціалізації Dictogram, наприклад, усі слова певної книги. В даному випадку ми ведемо підрахунок елементів, щоб для звернення до одного з них не було потреби щоразу перевіряти весь набір даних.

Ми також зробили дві функції для повернення випадкового слова. Одна функція вибирає випадковий ключ у словнику, а інша, зважаючи на число появ кожного слова в тексті, повертає потрібне нам слово.

Структура ланцюга Маркова

from histograms import Dictogramdef make_markov_model (data): markov_model = dict () for i in range (0, len (data) - 1): if data[i] in markov _model: # Просто приєднуємо до вже існуючого розподілу
markov_model[data[i]].update ([data[i+1]])  else: markov_model[data[i]] = Dictogram ([data[i+1]]) return markov_model

Отже, ми маємо словник, який зберігає вікна як ключ у парі “(ключ, значення)” і розподіли як значення в цій парі.

Структура ланцюга Маркова N-го порядку

from histograms import Dictogramdef make_higher_order_markov_model (order, data): markov_model = dict () for i in range (0, len (data) - order): # Створюємо вікно window = tuple (data[i: i+order])  # Додаємо в словник if window in markov _model: # Приєднуємо до вже існуючого розподілу markov_model[window].update ([data[i+order]])  else: markov_model[window] = Dictogram ([data[i+order]])
return markov_model

Дуже схожа на ланцюг Маркова першого порядку, але в даному випадку ми зберігаємо кортеж як ключ у парі “(ключ, значення)” в словнику. Ми використовуємо його замість списку, оскільки кортеж захищений від будь-яких змін, а для нас це важливо, бо ключі в словнику мінятися не повинні.

Парсинг моделі

Відмінно, ми реалізували словник. Як тепер здійснити генерацію контенту, ґрунтуючись на поточному стані й кроці до наступного стану? Пройдімося нашою моделлю:

from histograms import Dictogramimport randomfrom collections import dequeimport redef generate_random_start (model): # Щоб згенерувати будь-яке початкове слово, раскомментируйте рядок: # return random.choice (model.keys())  # Щоб згенерувати " правильне" початкове слово, використайте код нижче:
# Правильні початкові слова - це ті, що були початком пропозицій в корпусі if 'END' in model: seed_word = 'END' while seed_word == 'END': seed_word = model['END'].return_weighted_random_word () return seed_word return random.choice (model.keys()) def generate_random_sentence (length, markov_model): current_word = generate_random_start (markov_model) sentence =[current_word] for i in range (0, length): current_dictogram = markov_model[current_word] random_weighted_word = current_dictogram.return_weighted_random_word () current_word = random_weighted_word sentence.append (current_word) sentence[0] = sentence[0].capitalize () return ' '.join (sentence)  + '.' return sentence

Краще генерувати “правильні” початкові слова – ті, які у вихідному тексті стояли на початку речення. Для цього ми в словнику знаходимо всі ключі “END” і вибираємо слово, що йде за одним з них. Після генерації початкового слова ми шукаємо, яке слово може йти далі, звертаючись до того ж словника, і вибираємо потрібне на підставі комбінації ймовірності та випадковості. Продовжуємо це робити, поки речення не досягне встановленої нами довжини, і наприкінці повертаємо його. Якщо Ви хочете дізнатися більше  про парсинг, подивіться наш переклад про історію синтаксичного аналізу.

Що далі?

Спробуйте придумати, де Ви самі можете використати генератор тексту на основі марківських ланцюгів. Тільки не забувайте, що головне – це те, як Ви парсите модель і які особливі обмеження встановлюєте на генерацію. Автор цієї статті, наприклад, при створенні генератора твітів використав велике вікно, обмежив генерований контент до 140 символів і використав для початку речень тільки “правильні” слова, тобто ті, які були на початку речення в корпусі.

Ви також можете продовжити далі вивчати марківські процеси і, наприклад, спробувати розібратися в тому, що являють собою приховані марківські моделі.

Переклад статті “From “What is a Markov Model” to “Here is how Markov Models Work””

Київ, Харків, Одеса, Дніпро, Запоріжжя, Кривий Ріг, Вінниця, Херсон, Черкаси, Житомир, Хмельницький, Чернівці, Рівне, Івано-Франківськ, Кременчук, Тернопіль, Луцьк, Ужгород, Кам'янець-Подільський, Стрий - за статистикою саме з цих міст програмісти найбільше переїжджають працювати до Львова. А Ви розглядаєте relocate?


Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *