Було описано, як навчити нейтронну мережу так, щоб вона грала в Маріо або керувала роботом. Але чи може нейронна мережагенерувати текст? У цьому можуть допомогти ланцюги Маркова.

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

Якщо хтось захоче дізнатися, що таке ланцюги Маркова, то в першому перекладі він дізнається, що:
"Ланцюг Маркова - послідовність випадкових подійз кінцевим чи лічильним числом результатів, що характеризується тим властивістю, що, кажучи нестрого, при фіксованому сьогодення майбутнє незалежно від минулого. Названа на честь А. А. Маркова (старшого).

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

Ланцюги маркова - це всього лише опис ймовірностей переходу системи з одного стану в інший. Усі стани можна описати вершинами графа. Наприклад, такими вершинами можуть бути положення людини: [лежать], [сидить], [коштує], [йде]

Тут видно, що граф орієнтований, це означає, що не з будь-якого стану можна потрапити до іншого. Наприклад, якщо ви лежите, то неможливо одразу піти. Нудно спочатку сісти, потім підвестися, а тільки потім піти. Але впасти і виявитись лежачим можна з будь-якого положення))
Кожен зв'язок має певну можливість. Так, наприклад, ймовірність впасти зі стоячого становища дуже маленька, набагато вірогідніше стояти далі, піти чи сісти. Сума всіх можливостей дорівнює 1.

До того ж ланцюги Маркова дозволяють генерувати події. Так чи інакше на ланцюгах Маркова побудовано всю більшість генераторів текстів.

Спробуємо написати генератор пиріжків.

Тістечка

Пиріжки - чотиривірші без рими, розділових знаків, цифр, без великих літер. Кількість складів має бути 9-8-9-8.

Більшість генераторів текстів використовують морфологічні аналізатори. Але ми зробимо простіше. Просто розіб'ємо слова на склади і порахуємо ймовірність того, що один склад знаходиться після іншого складу. Тобто вузлами графа у нас будуть склади, ребрами, та їх вагами – частота того, що другий склад іде за першим.
Далі згодуємо програмі півсотні пиріжків.

Наприклад, після складу "при", можуть йти такі склади (ребра та їх ваги):
"чем"(1) "хо"(4) "ме"(1) "ду"(2) "чи"(4) "ятель"(4) "йшов"(5) "ку"(1) " " (9) "су"(1) "вич"(3) "мі"(1) "кіс"(1) "про"(1) "діт"(2) "їхав"(1) "учи"(1) ) "му"(1) "бі"(1) "це"(1) "ціл"(2) "том"(1) "ко"(1) "вал"(1) "ніс"(1) " дет"(1) "але"(1) "віз"(1) "мет"(1) "вет"(1) "дя"(1) "ви"(1)

Тепер все що потрібно - це взяти випадковий склад (наприклад, "при"). Сума всіх складів, що йдуть після нього, дорівнює 58. Тепер потрібно взяти наступний склад з урахуванням частоти (кількості) цих складів:

size_t nth = rand() % count;

size_t all = 0;

for (const auto &n: next) (

All + = n.count;

if (all >= nth)

return n.word;

Таким чином генеруємо рядки так, щоб у першому рядку було 9 складів, у другому - 8, далі 9 та 8, отримуємо:

Жив жартувати будильник до кого
викрадений він поки це
тобі афаначальник тут так
онегін ефекти диван

Поки що на особливо зв'язний текст не схоже. Часто зустрічаються неіснуючі слова ("поки"). Як ключ зараз лише один склад. Але на підставі одного складу складно пропозицію. Збільшимо кількість складів, на підставі яких будемо генерувати наступний склад хоча б до 3:

Асфальту для розуму досить
на годиннику сім розділити на
стіл виносять чорний ящик
він виріс помстився знайшов
Ось і перший пиріжок, який більш-менш можна прийняти за написаний людиною.
Щоб текст вийшов більш осмисленим, потрібно використовувати морфологічні аналізатори , і тоді як вузли будуть не склади, а метаопису слів (наприклад "дієслово, множини, Минулого часу ").

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

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

Ланцюг Маркова - це поширений і досить простий спосіб моделювання випадкових подій. Використовується в самих різних областяхпочинаючи генерацією тексту і закінчуючи фінансовим моделюванням. Самим відомим прикладомє SubredditSimulator . У даному випадкуЛанцюг Маркова використовується для автоматизації створення контенту у всьому subreddit.

Ланцюг Маркова зрозуміла і проста у використанні, тому що вона може бути реалізована без використання будь-яких статистичних або математичних концепцій. Ланцюг Маркова ідеально підходить для вивчення ймовірнісного моделювання та Data Science.

Сценарій

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

Тепер вам захотілося навчитися пророкувати погоду на завтрашній день. Інтуїтивно ви розумієте, що погода не може кардинально змінитись за один день. На це впливає багато факторів. Завтрашня погода безпосередньо залежить від поточної і т. д. Таким чином, для того, щоб передбачати погоду, ви протягом декількох років збираєте дані і приходите до висновку, що після похмурого дня ймовірність сонячного дорівнює 0,25. Логічно припустити, що ймовірність двох похмурих днів поспіль дорівнює 0,75, тому що ми маємо лише дві можливі погодні умови.

Тепер ви можете прогнозувати погоду на кілька днів уперед, ґрунтуючись на поточній погоді.

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

Зверніть увагу, що у прикладі розподіл ймовірностей залежить лише від переходів з поточного днянаступного. Це унікальна властивістьМарковського процесу - він робить це без використання пам'яті. Як правило, такий підхід не здатний створити послідовність, в якій спостерігалася б якась тенденція. Наприклад, у той час як ланцюг Маркова здатна зімітувати стиль листа, заснований на частоті використання якогось слова, він не здатний створити тексти з глибоким змістомоскільки вона може працювати тільки з великими текстами. Саме тому ланцюг Маркова не може виробляти контент, що залежить від контексту.

Модель

Формально ланцюг Маркова - це ймовірнісний автомат. Розподіл ймовірностей переходів зазвичай представляється як матриці. Якщо ланцюг Маркова має N можливих станів, то матриця матиме вигляд N x N, в якій запис (I, J) буде ймовірністю переходу зі стану I стан J. Крім того, така матриця повинна бути стохастичної, тобто рядки або стовпці в сумі повинні давати одиницю. У такій матриці кожен рядок матиме власний розподіл ймовірностей.

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

Зразкова матриця переходу із трьома можливими станами.

Ланцюг Маркова має початковий векторстану, представлений у вигляді матриці N x 1. Він описує розподіл ймовірностей початку в кожному з N можливих станів. Запис I визначає ймовірність початку ланцюга у стані I.

Цих двох структур цілком вистачить на уявлення ланцюга Маркова.

Ми вже обговорили, як отримати можливість переходу з одного стану в інший, але що щодо отримання цієї можливості за кілька кроків? Для цього нам необхідно визначити можливість переходу зі стану I в стан J за M кроків. Насправді, це дуже просто. Матрицю переходу P можна визначити обчисленням (I, J) за допомогою зведення P у ступінь M. Для малих значень M це можна робити вручну за допомогою повторного множення. Але для великих значень M, якщо ви знайомі з лінійною алгеброю, більше ефективним способомзведення матриці в ступінь спочатку діагоналізуватиме цю матрицю.

Ланцюг Маркова: висновок

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

Переглядав форуми у пошуках питань, які ставлять python-програмістам на співбесідах і натрапив на одне дуже чудове. Вільно його процитую: ”Попросили написати генератор марення на основі марківського ланцюга n-го порядку”. "Але ж у мене ще немає такого генератора!" - прокричав мій внутрішній голос- "Швидше відкривай sublime і пиши!" - продовжував він наполегливо. Що ж, довелося підкоритися.

А тут я розповім, як його зробив.

Відразу було вирішено, що генератор усі свої думки викладатиме у Твіттер і свій сайт. Як основні технології я вибрав Flask і PostgreSQL. Зв'язуватися один з одним вони будуть через SQLAlchemy.

структура.

І так. Наступним чиномвиглядають моделі:
class Srt(db.Model): id = db.Column(db.Integer, primary_key = True) set_of_words = db.Column(db.Text()) list_of_words = db.Column(db.Text()) class UpperWords(db .Model): word = db.Column(db.String(40), index = True, primary_key = True, unique = True) def __repr__(self): return self.word class Phrases(db.Model): id = db .Column(db.Integer, primary_key = True) created = db.Column(db.DateTime, default=datetime.datetime.now) phrase = db.Column(db.String(140), index = True) def ): return str(self.phrase)
Як вихідних текстіввирішено було взяти субтитри із популярних серіалів. Клас Srt зберігає впорядкований набір всіх слів з перероблених субтитрів до одного епізоду і унікальний набір цих самих слів (без повторень). Так боту простіше шукатиме фразу у конкретних субтитрах. Спочатку він перевірить, чи міститься безліч слів у безлічі слів субтитрів, а потім подивиться, чи лежать вони там у потрібному порядку.

Першим словом фрази з тексту вибирається випадкове слово, що починається з великої літери. Для зберігання таких слів служить UpperWords. Слова туди записуються так само без повторень.

Ну і клас Phrases потрібний для зберігання вже згенерованих твітів.
Структура відчайдушно проста.

Парсер субтитрів формату srt виведений в окремий модуль add_srt.py. Там немає нічого екстраординарного, але якщо комусь цікаво, всі вихідники є на GitHub.

Генератор.

Для початку потрібно вибрати перше слово для твіту. Як говорилося раніше, це буде будь-яке слово із моделі UpperWords. Його вибір реалізований у функції:
def add_word(word_list, n): якщо немає word_list: word = db.session.query(models.UpperWords).order_by(func.random()).first().word #postgre elif len(word_list)<= n: word = get_word(word_list, len(word_list)) else: word = get_word(word_list, n) if word: word_list.append(word) return True else: return False
Вибір цього слова реалізується безпосередньо рядком:

Word = db.session.query(models.UpperWords).order_by(func.random()).first().word

Якщо Ви використовуєте MySQL, потрібно використовувати func.rand() замість func.random(). Це єдина відмінність у цій реалізації, решта працюватиме повністю ідентично.

Якщо перше слово вже є, функція дивиться на довжину ланцюга, і залежно від цього вибирає з якою кількістю слів у тексті потрібно порівняти наш список (ланцюг n-го порядку) та отримати наступне слово.

А наступне слово ми отримуємо у функції get_word:
def get_word(word_list, n): queries = models.Srt.query.all()<= set(query.set_of_words.split()): query_list.append(query.list_of_words.split()) if query_list: text = list() for lst in query_list: text.extend(lst) indexies = ) if text == word_list] word = text return word else: return False
Насамперед скрипт пробігає по всіх завантажених субтитрах і перевіряє, чи входить наше безліч слів у безліч слів конкретних субтитрів. Потім тексти відсіяних субтитрів складаються в один список і в ньому шукаються збіги фраз цілком і повертаються позиції слів, що йдуть за цими фразами. Все закінчується сліпим вибором (random) слова. Все як у житті.
Так додаються слова до списку. Сам же твіт збирається у функції:
def get_twit(): word_list = list() n = N while len(" ".join(word_list))<140: if not add_word(word_list, n): break if len(" ".join(word_list))>140: word_list.pop() break while word_list[-1][-1] not in ".?!": word_list.pop() return " ".join(word_list)
Все дуже просто - необхідно, щоб твіт не перевищував 140 символів і закінчувався завершальною розділовою ознакою. Все. Генератор виконав свою роботу.

Відображення на сайті.

Відображенням сайту займається модуль views.py.
@app.route("/") def index(): return render_template("main/index.html")
Просто відображає шаблон. Усі твіти підтягуватимуться з нього за допомогою js.
@app.route("/page") def page(): page = int(request.args.get("page")) diff = int(request.args.get("difference")) limit = 20 phrases = models.Phrases.query.order_by(-models.Phrases.id).all() pages = math.ceil(len(phrases)/float(limit)) count = len(phrases) phrases = phrases return json.dumps(( "phrases":phrases, "pages":pages, "count":count), cls=controllers.AlchemyEncoder)
Повертає твіт певної сторінки. Це потрібно для нескінченного скрола. Все досить буденно. diff – кількість твітів, доданих після завантаження сайту під час апдейту. На цю кількість потрібно зміщувати вибірку твітів для сторінки.

І безпосередньо сам апдейт:
@app.route("/update") def update(): last_count = int(request.args.get("count")) phrases = models.Phrases.query.order_by(-models.Phrases.id).all( ) count = len (phrases) if count > last_count: phrases = phrases .dumps(("count":count))
На стороні клієнта він викликається кожні n секунд і довантажує в реальному часі знову додані твіти. Так працює відображення нашого твіту. (Якщо комусь цікаво, то можна подивитися клас AlchemyEncoder у controllers.py, за його допомогою проводиться серіалізація твітів, отриманих від SQLAlchemy)

Додавання твітів у базу та постінг у Твіттер.

Для постінгу в Твіттер я використав tweepy. Дуже зручна батарея, заводиться відразу.

Як це виглядає:
def twit(): phrase = get_twit() twited = models.Phrases(phrase=phrase) db.session.add(twited) db.session.commit() auth = tweepy. , ACCESS_TOKEN_SECRET) api = tweepy.API(auth) api.update_status(status=phrase)
Виклик цієї функції я виніс у cron.py в корені проекту і, як можна здогадатися, воно запускається по крону. Кожні півгодини додається новий твіт у базу та Твіттер.


Все запрацювало!

На закінчення.

На даний момент я підвантажив усі субтитри для серіалу "Друзі" та "Теорія великого вибуху". Ступінь марківського ланцюга поки що вибрав рівним двом (при збільшенні бази субтитрів ступінь буде збільшуватися). Як це працює можна подивитися в

У web-будівництві та SEO ланцюга Маркова використовуються для генерації псевдоосмислених текстів на основі вихідних текстів. Це використовується для штампування дорвеїв із заданими ключовими словами, для набору контентної текстової маси тощо "чорним" трюкам. На щастя, пошукові системи навчилися ефективно визначати контент, створений на основі ланцюгів Маркова та відправляє таких розумників у бан. Вчити вас подібним технологіям я не збираюся, для цього є спеціальні гівносайти, мене цікавить лише програмна реалізація алгоритму.

Ланцюгом Маркова називається послідовність випробувань, у кожному з яких з'являється лише одна з k несумісних подій Ai з повної групи. При цьому умовна ймовірність pij(s) того, що в s-му випробуванні настане подія Aj за умови, що в (s - 1) - му випробуванні настала подія Ai, не залежить від результатів попередніх випробувань.

Бажаючі подивитись свій головний мозок можуть почитати про математичну модель. На людській мові всі ці формули зводяться до наступного. У вихідному тексті визначаються слова та зберігається послідовність, які слова йдуть за якими. Потім виходячи з цих даних створюється новий текст, у якому самі слова обрані випадково, але збережено зв'язок між ними. Для прикладу візьмемо дитячий віршик:

З-за лісу, з-за гір
їде дідусь Єгор:
сам на коні,
дружина на корівці,
діти на телятках,
онуки на козенятах.

Розберемо текст на ланки та зв'язки

Через [ліси, гір]
ліси [через]
гір [їде]
їде [дідусь]
дідусь [Єгор]
Єгор [сам]
сам [на]
на [конячку, корівці, телятках, козенятках]
коняці [дружина]
дружина [на]
корівці [діти]
діти [на]
телятках [онуки]
онуки [на]

Ланки в цьому списку є унікальними словами з тексту, а в квадратних дужках перераховані зв'язки - список слів, які можуть розташовуватися після цього слова.

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

Єгор сам на телятках онуки на коні дружина на корівці діти на корівці
У цьому прикладі отриманий текст мало відрізняється від вихідного, оскільки текст дуже короткий. Якщо взяти вихідний словник у кілька кілобайт або навіть мегабайт, то на виході вийде цілком зв'язний текст, хоч і не має сенсу.

1. // Прочитати вихідний текст, на основі якого генеруватиметься новий
2. $str = file_get_contents ("markov.txt");
3. // Встановити кодування системи
4. setlocale (LC_ALL, "ru_RU.CP1251");
5. // Прибрати з тексту символи крім цифр, літер і деяких розділових знаків
6. $str = eregi_replace ("[^-a-zа-я0-9 !\?\.\,]" , " " , $str );
7. // Підчистити прогалини перед закінченнями речень
8. $str = eregi_replace (" (1,)([!\?\.\,])" , "\\1" , $str );
9. // Розділити текст на слова
10. $tmp = preg_split ("/[[:space:]]+/is" , $str );
11. // Масив "ланок"
12. $words = Array();
13. // Заповнити ланки
14. for($i = 0 ; $i< count ($tmp ); $i ++) {
15. if ($tmp [$i + 1]! = "") (
16. $words [ $tmp [ $i ]]= $tmp [ $i + 1 ];
17. $words = array_map ("array_unique", $words);
18. // Масив початкових слів у реченнях
19. $start =Array();
20. foreach($words as $word => $links ) (
21. if (ereg ("^[А-Я][а-я]+" , $word )) (
22. $start = $word;
23. // Сгененувати 100 речень на основі вихідного тексту
24. for ($i = 0; $i< 100 ; $i ++) {
25. while (true) (
26. $w = $start [ rand (0, (count ($start)-1))];
27. if (ereg ("[\.!\?]$" , $w )) ( continue; )
28. $sentence = $w . "";
29. // Кількість слів у реченні
30. $ cnt = 1;
31. // Згенерувати пропозицію
32. while(true) (
33. $links = $words [$w];
34. // Переключити ланцюжок
35. $w = $words [ $w ][ rand (0 ,(count ($words [ $w ])- 1 ))]];
36. $sentence .= $w . "";
37. // Якщо слово було наприкінці речення
38. if (ereg ("[\.!\?]$" , $w )) ( break; )
39. $ cnt ++;
40. // Якщо генератор зациклився, то примусово вийти
41. if ($cnt > 19) (break;)
42. // Вдалим вважати пропозицію довжиною 5-20 слів
43. if ($cnt > 5 && $cnt< 20 ) { break; }
44. // Згенерована пропозиція
45. echo $sentence;

Невеликі пояснення, як це все працює. Спочатку завантажується файл "markov.txt", він має бути в кодуванні win-1251. Потім з нього видаляються всі символи, крім літер і деяких розділових знаків, потім вирізаються зайві прогалини. Виходить чистий текст, який потім поділяється на окремі слова. Все, у нас є окремі ланки ланцюга. Тепер треба визначити зв'язки слів, тобто якісь слова і за якими можуть розташовуватися. Це найбільш ресурсомісткий процес, так що на великих файлах доведеться запастися терпінням. Якщо генерація потрібна часто, то, напевно, є сенс зберігати масив ланок і зв'язок у якійсь базі, щоб мати до нього швидкий доступ. Наступний крок- Визначення слів, з яких починаються пропозиції. Я прийняв умову, що у таких слів перша літера має бути великою, ви можете зробити більше точне визначення. Генерація тексту виконується за описаним вище алгоритмом, тільки додав до нього кілька перевірок від зациклювання.

Робочий приклад генератора текстів на основі ланцюгів Маркова та наведеного вище скрипту, можете переглянути

Ця стаття дає загальне уявленняпро те, як генерувати тексти за допомогою моделювання марківських процесів. Зокрема, ми познайомимося з ланцюгами Маркова, а як практика реалізуємо невеликий генератор тексту на 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. Ви можете стерти будь-який напрямок ви 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.»

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

Найпростіше це пояснюється з погляду програми. Ми знаємо, що для кожної ланки існує набір слів, які можуть слідувати за ним. А також кожне слово характеризується числом його появ у тексті. Нам потрібно якось зафіксувати всю цю інформацію в одному місці; для цієї мети найкраще підійде словник, що зберігає пари "(ключ, значення)". У ключі словника буде записано поточний стан системи, тобто одна з ланок корпусу (наприклад, "the"на зображенні нижче); а в значенні словника зберігатиметься ще один словник. У вкладеному словнику ключами будуть слова, які можуть йти в тексті після поточної ланки корпусу ( "thinks"і «more»можуть йти в тексті після "the"), а значеннями - кількість появ цих слів у тексті після нашої ланки (слово "thinks"з'являється у тексті після слова "the" 1 раз, слово «more»після слова "the"- 4 рази):

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

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

Більше:

Тобто, якщо поточним словом є слово «more»після нього можуть з рівною ймовірністю в 25% йти слова "things"і «places», І з ймовірністю 50% - слово "that". Але ймовірності можуть бути й усі рівні між собою:

Think:

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

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

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

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

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

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

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

Import random class 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 += 1 self.tokens += 1 else: self = 1 self.types += 1 self.tokens += 1 def count(self, item): # Повертаємо значення лічильника елемента, або 0 if item in self: return self return 0 def return_random_word(self): random_key = random.sample(self, 1) # Інший спосіб: # random .choice(histogram.keys()) return random_key def return_weighted_random_word(self): # Згенерувати псевдовипадкове число між 0 і (n-1), # де n - загальна кількість слів random_int = random.randint(0, self.tok ) index = 0 list_of_keys = self.keys() # вивести "випадковий індекс:", random_int for i in range(0, self.types): index += self] # вивести індекс if(index > random_int): # вивести list_of_keys [i] return list_of_keys[i]

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

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

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

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

У реалізації вище у нас є словник, який зберігає вікна як ключ у парі «(ключ, значення)» та розподіл як значення в цій парі.

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

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

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

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

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

З histograms import Dictogram import random from collections import deque import re def 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 = for i in range(0, length): current_dictogram = markov_model random_weighted_word = current_dictogram. weighted_word sentence.append(current_word) sentence = sentence.capitalize() return " ".join(sentence) + "." return sentence

Що далі?

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