Есть забавная штука под названием цепь Маркова. Говоря научным языком, это последовательность случайных событий, где вероятность появления следующего события зависит только от определенного количества предыдущих событий. Цепи Маркова выполняют множество различных задач, от предсказания курсов акций на бирже до предсказания того, какое слово вы собираетесь набрать на виртуальной клавиатуре своего смартфона. И работают они также при анализе цепочек ДНК, сжатии данных, картографии, проверке текстовой орфографии. Они занимаются распознаванием и созданием голосовых сообщений, музыки и текстов на компьютере.
Цепь Маркова — это своего рода алгоритм искусственного интеллекта и машинного обучения, но его идея очень проста.
Возьмем, к примеру, текст книги. Все слова в тексте идут одно за другим. Можно сказать, что появление каждого следующего слова в тексте — это событие. Каждое определенное слово появляется в тексте с определенной вероятностью, и эта вероятность зависит от предыдущих слов. Например, в книге Гарри Поттер и философский каменьвероятность появления слова Поттер после слова Гарри намного выше, чем любого другого слова. Мы можем проанализировать текст книги и подсчитать, как часто каждое слово появляется друг за другом для всех слов в книге. Затем мы можем записать эти данные в таблицу и использовать эту таблицу для создания нового текста в стиле оригинальной книги, которая использовалась для создания таблицы.
Например, если мы сделаем это для текста выше, мы получим такую таблицу:
Это небольшая часть таблицы. Вся таблица имеет 241 строку.
Если мы построим таблицу для всей книги Гарри Поттер и философский камень, то она будет выглядеть так:
Это часть, где первое слово «Гарри». Вся таблица имеет 42708 строк.
Чтобы сгенерировать новый текст, мы берем случайное первое слово из таблицы. Затем мы находим наиболее вероятное второе слово на основе количества повторений. Затем мы используем это второе слово как первое слово и находим наиболее вероятное следующее слово для этого слова. Мы можем повторять этот цикл, пока не получим предложение нужной длины.
Конечно, такой текст не будет иметь общего смысла. Каждое предложение не будет связано с другим, но стиль текста будет аналогичен стилю автора оригинального текста. Каждое отдельное предложение может иметь даже само значение.
Этот алгоритм является основой для компьютерных программ, которые находят плагиат или просто похожие тексты или музыку. Когда YouTube блокирует ваше видео, потому что находит там контент, защищенный авторским правом, он использует аналогичный алгоритм, но вместо слов использует звуки и видеокадры.
Виртуальные клавиатуры смартфонов, которые подсказывают вам наиболее вероятные слова, которые вы, возможно, захотите набрать, делают это на основе тех же таблиц вероятностей слов для выбранного языка и текстов, которые вы набирали ранее. Например, после анализа текста, который вы набрали ранее, ваш телефон может подсказать вам слово «я» после текста «я», потому что в прошлом вы чаще всего набирали «я», а после текста «я». подсказывает слова «а», «будет» или «так», потому что они тоже наиболее вероятны. Но он никогда не запрашивает «яблоко» после текста «Я», потому что вы никогда его не вводили. Но попробуйте много раз набрать «Я яблоко», и если ваша виртуальная клавиатура будет достаточно умной, когда-нибудь она начнет предлагать вам «яблоко» после вашего «Я».
Чем больше предыдущих слов мы используем для предсказания, тем лучше результат. Последовательности предыдущих слов, используемые для прогнозирования, вызывают N-граммы. Если мы считаем вероятности только между двумя словами, пары этих слов называются биграммами. Если мы подсчитываем вероятности между тремя словами, то их последовательности называются триграммами. Как правило, чем больше число N, тем лучше результат прогноза. Если мы используем его для генерации текста, то это означает, что чем больше N, тем красивее текст мы получим и тем больше этот текст будет похож на исходный текст, который использовался для обучения программы.
В общем, если эта компьютерная программа анализирует книгу о Гарри Поттере, она сгенерирует текст в стиле Джоан Роулинг, если анализирует книги Дж.Р.Р. Толкин будет генерировать тексты о Фродо Бэггинсе, если анализировать Библию, то будет генерировать эпические тексты об Иисусе Христе и евреях. Но если мы учим эту программу по всем этим книгам вместе взятым, то она будет давать тексты об обучении Фродо в Хоггвардсе под руководством Иисуса Христа и битвах Гарри Поттера против армии Саурона на еврейской земле. :)
С тех пор, как я читал о цепях Маркова, мне хотелось посмотреть, какой текст я получу, если буду использовать 6-граммы или больше и буду учить программу по своим любимым книгам. В Интернете можно найти множество компьютерных программ, которые генерируют тексты на основе биграмм, потому что алгоритм очень прост и написать такую программу несложно. Но если вы хотите поиграть с N-граммами, где N значительно больше 2, то очень сложно найти бесплатные удобные программы с открытым исходным кодом в Интернете. По крайней мере, я не смог найти ни одного.
Основной проблемой программ, которые могут работать с большими N-граммами, является нехватка компьютерной памяти для хранения всех возможных вероятностей между всеми словами в тексте. Например, в Библии около 52000 уникальных слов. Для хранения в памяти вероятностей для всех этих слов нужно 52000*52000*8=21632000000 байт, то есть примерно 21 гигабайт, для триграмм нужно 52000*52000*52000*8=1124864 гигабайт! Очевидно, что нет персонального компьютера с таким большим объемом памяти.
В итоге вчера сделал вот такую программу. Он хранит только вероятности, которые больше нуля, поэтому ему требуется гораздо меньше памяти и он позволяет работать с N-граммами, где N значительно больше 2 или даже 6.
Сегодня немного поигрался с программой.
Сначала я поставил N = 2 и скормил программе книгу Гарри Поттер и философский камень.
Вот несколько предложений, которые я получил:
«Гарри доволен добавлением немного бренди, чтобы создать цели, и я не понимаю, как вы думаете».
«Тетя Петуния чуть не держала руку почти в Хогвартсе, прежде чем проткнуть его плащ, быстро все выяснила, вплоть до большого шоколадного торта, и Рон сошел с Камня, прежде чем он направился к Рону, и сказал, что Гермиона не спит».
«То, что вышло из его плеча, должно было произойти в их умах, работа чего-то вроде Хагрида, усмехнувшегося и беззащитного, чтобы одолжить нам ни одного из красных фурункулов, начала волноваться, хотя папа был на три головы в Хогвартс-Экспрессе одиннадцать».
Выглядит не слишком красиво, но для такого небольшого количества N нормально.
Затем я установил N = 6 и скормил программе ту же книгу. Этот умник полностью выучил книгу наизусть и цитировал целые фразы, но не хотел придумывать что-то оригинальное.
Я соединил «Сильмариллион» и Библию и получил следующие предложения:
«Там, где Эсгалдуин стекал вниз и отделял Нелдорет от Региона, поднимались среди учителей, которые слушали их и задавали им вопросы».
«Все, что было в городе, и мужчины и женщины, и молодые, и старые, и вола, и овцу, и осла, острия меча погубят его совершенно, и все, что в нем, и скот его возьмете себе в добычу, себя.”
«Только будьте сильными и очень мужественными, чтобы соблюдать все, чему они будут учить вас, в соответствии с содержанием закона, которому они будут учить вас, и в соответствии с суждением, которое они скажут вам, что вы должны делать». /эм>
«Слушай мой голос по милости Твоей, и я буду повиноваться уставам уст Твоих».
«Когда он вошел в дом, вот, ребенок был мертв и лежал на своей постели».
Эти предложения выглядят лучше, но содержат большие цитаты из оригинальных текстов. Это означает, что программа не извлекает общего представления, не обобщает свои знания, а просто полностью запоминает заданные тексты. С точки зрения искусственного интеллекта это называется «переоснащением», у искусственных нейронных сетей та же проблема. Если их «мозг» слишком велик, они предпочитают не обобщать входящую информацию и находить новые знания, а запоминать всю входящую информацию.
Но последние два предложения превосходны. Они выглядят очень естественно. Они имеют смысл. Они полностью оригинально сгенерированы и не имеют цитирования оригинальных текстов. Это означает, что нам нужно увеличить количество текстов для обучения программе или уменьшить N, чтобы сделать программу более глупой, что делает ее неспособной запомнить все учебные тексты. Но уменьшение N делает сгенерированные предложения уродливыми, как мы видели выше для биграмм.
Наконец, я собрал вместе все семь книг о Гарри Поттере, Хоббите, Сильмариллионе, Властелине колец и Библии и попытался провести программу с N=6. Вот результат:
«С этими словами он взмахнул палочкой, исчезнув кольца, и вышел из комнаты, не замеченный ни Гермионой, ни Батильдой. Он сунул фотографию неизвестного вора в серебряной рамке себе под куртку».
"Но на следующее утро они встали рано, так как погода все еще была дождливой, они хотели добраться до Шира до ночи, и прошло много времени после того, как храп Чарли наполнил палатку, когда Гарри наконец задремал." >
"Джордж хотел закрыть дверь, чтобы заглушить шум, но прежде чем он успел что-либо сделать, Живоглот исчез одним взмахом своего длинного рыжего хвоста".
"Они ехали около четырех часов от развилки дорог, когда они приблизились к злому региону Нан Дунгортеб, всадники запутались в тенях, а Аредэль отклонилась от своих спутников и заблудилась."
«Почитай отца твоего и мать, что является первой заповедью, с обещанием, что тебе будет хорошо, и прояви милость ко мне, и упомяни обо мне фараону, и выведи меня из этого дома».
«Тогда было железо, глина, медь, серебро, золото, пряности и драгоценный елей, и весь дом Израилев, все те, которым жители Иерусалима сказали: «Удалитесь от Яхве».
Значительно увеличилось количество полностью оригинально сгенерированных предложений без больших цитат из учебных текстов, они стали лучше выглядеть и иметь более глубокий смысл. Все предложения выше не содержат цитат длиннее нескольких слов. Но все же есть много предложений, полностью процитированных из учебных текстов. Думаю, если подготовить несколько гигабайт качественных обучающих текстов, то все предложения будут полностью оригинальными и имеет смысл увеличить порядок N-грамм для улучшения качества этих предложений.
Похоже, это будет хорошая игрушка для дальнейших экспериментов. :)
Вы тоже можете поиграть с этой программой или помочь добавить туда что-то новое.
Репозиторий с исходным кодом находится здесь: https://github.com/jolly-fellow/n-gram-text-gen
Бинарные исполняемые файлы с программой вы можете скачать здесь: для Linux, для Windows
Не требует установки и настроек.
Для использования программы просто введите название программы и ключи в командной строке. Например
./textgen –N 6 –введите my_learning.txt –сгенерируйте 50
будет использовать текст из файла my_learning.txt для обучения и сгенерирует 50 предложений на основе 6 граммов.
Все возможные ключи здесь:
— help показать справочное сообщение
— N arg устанавливает порядок N-грамм (по умолчанию 2)
— generate arg устанавливает, сколько предложений генерировать (по умолчанию 10)
— input arg установить входной файл для обучения
— matrix arg задает выходной файл для сохранения матрицы
— print_stats распечатать данные статистики
— print_chains распечатать цепочки N-грамм
— print_dictionary распечатать словарь
