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

Вот некоторые отраслевые приложения цепей Маркова:

  • Генерация текста (для этого вы здесь).
  • Финансовое моделирование и прогнозирование (включая торговые алгоритмы).
  • Логистика: моделирование будущих поставок или поездок.
  • Поисковые системы: PageRank можно рассматривать как моделирование случайного интернет-пользователя с цепью Маркова.

Пока мы можем сказать, что этот алгоритм полезен, но что такое цепи Маркова?

Что такое цепи Маркова?

Цепь Маркова - это случайный процесс, который моделирует конечный набор состояний с фиксированными условными вероятностями перехода из одного состояния в другое.

Это означает, что у нас будет «агент», который случайным образом перескакивает между разными состояниями с определенной вероятностью перехода из одного состояния в другое.

Чтобы показать, как выглядит цепь Маркова, мы можем использовать орграф, где каждый узел является состоянием (с меткой или связанными данными), а вес ребра, идущего от узла от a до узла b - это вероятность перехода из состояния a в состояние b.

Вот пример моделирования погоды в виде цепи Маркова.

Мы можем выразить вероятность перехода из состояния a в состояние b как компонент матрицы, где вся матрица характеризует нашу цепь Маркова. , соответствующий матрице смежности орграфа.

Затем, если мы представим текущее состояние как горячее кодирование, мы можем получить условные вероятности для значений следующего состояния, взяв текущее состояние и посмотрев на соответствующую ему строку.

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

Цепи Маркова для генерации текста

Чтобы сгенерировать текст с помощью цепей Маркова, нам нужно определить несколько вещей:

  • Какими будут наши государства?
  • Какие вероятности мы присвоим переходу из одного состояния в другое?

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

Я уже подробно рассказывал об этом в своей статье LSTM for Text Generation и получил неоднозначные результаты.

В этом эксперименте я вместо этого выберу предыдущие k слов в качестве моего текущего состояния и смоделирую вероятности следующего токена.

Для этого я просто создам вектор для каждой отдельной последовательности из k слов, имеющий N компонентов, где N - общее количество различных слов в моем корпусе.

Затем я добавлю 1 к j -ому компоненту i -го вектора, где i - это индекс i -го k. -последовательность слов, а j - индекс следующего слова.

Если я нормализую вектор каждого слова, у меня будет распределение вероятностей для следующего слова с учетом предыдущих k токенов.

Сбивает с толку? Рассмотрим пример с небольшим корпусом.

Тренируем нашу цепочку: игрушечный пример.

Представим, что мой корпус - это следующее предложение.

This sentence has five words

Сначала мы выберем k: количество слов, которые наша цепочка рассмотрит перед выборкой / предсказанием следующего. В этом примере возьмем k = 1.

Итак, сколько различных последовательностей одного слова состоит в нашем предложении? В нем 5, по одному на каждое слово. Если бы в нем были повторяющиеся слова, они бы не добавляли к этому числу.

Сначала мы инициализируем матрицу нулей 5 × 5.

После этого мы добавим 1 в столбец, соответствующий «предложению» в строке «this». Затем еще 1 в строке "предложение" в столбце "имеет". Мы продолжим этот процесс, пока не закончим все предложение.

Это будет итоговая матрица:

Поскольку каждое слово появляется только один раз, эта модель будет просто генерировать одно и то же предложение снова и снова, но вы можете увидеть, как добавление большего количества слов может сделать это интересным.

Надеюсь, теперь все прояснилось. Давайте перейдем к коду!

Кодирование нашей цепи Маркова на Python

А теперь самое интересное! Мы обучим цепь Маркова всему корпусу «Песни льда и пламени» (Ха! Вы думали, я собираюсь сослаться на шоу? Жаль, что я книжный парень!).

Затем мы сгенерируем предложения с различными значениями для k.

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

Обычно в НЛП мы обрабатываем знаки препинания (например, "," или ".") Как токены. Чтобы решить эту проблему, я сначала добавлю отступ в виде двух пробелов к каждому знаку препинания.

Вот код этой небольшой предварительной обработки плюс загрузка корпуса:

Мы сразу же приступим к обучению нашей цепи Маркова, но сначала давайте посмотрим на наш набор данных:

У нас более 2 миллионов токенов, представляющих более 32000 различных слов! Это довольно большой корпус для одного писателя.

Если бы он только мог добавить еще 800 тысяч…

Обучение нашей сети

Далее, вот как мы инициализируем нашу матрицу подсчета «слово после k-последовательности» для произвольного k (в данном случае 2).

В корпусе 2185918 слов и 429582 различных последовательностей из 2 слов, за каждым из которых следует одно из 32663 слов.

Это означает, что лишь немногим более 0,015% компонентов нашей матрицы будут отличными от нуля.

Из-за этого я использовал scipy's dok_matrix (dok означает Словарь ключей), реализацию разреженной матрицы, поскольку мы знаем, что этот набор данных будет чрезвычайно разреженным.

После инициализации нашей матрицы выборка становится довольно интуитивной.

Вот код для этого:

Здесь есть две вещи, которые могли привлечь ваше внимание. Первый - гиперпараметр альфа.

Это креативность нашей цепочки: шанс (обычно небольшой или нулевой), что она выберет совершенно случайное слово вместо тех, которые предлагает корпус.

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

Во всех примерах, которые я покажу, я использовал значение alpha, равное 0.

Второе - это функция weighted_choice. Мне пришлось реализовать это, поскольку случайный пакет Python не поддерживает взвешенный выбор по списку с более чем 32 элементами, не говоря уже о 32000.

Результаты: сгенерированные предложения

Прежде всего, в качестве основы я попробовал детерминированный подход: что произойдет, если мы выберем слово, используем k = 1 и всегда перейдем к наиболее вероятному слову после текущего?

Результаты, мягко говоря, неутешительны.

I am not have been a man , and the Wall . " " " "
he was a man , and the Wall . " " " " " " "
she had been a man , and the Wall . " " " " " "

Поскольку мы детерминированы, за «a» всегда следует «человек», за «the» всегда следует «Wall» (хе-хе) и так далее.

Это означает, что наши предложения будут скучными, предсказуемыми и бессмысленными.

Теперь для некоторого реального поколения я попытался использовать стохастическую цепь Маркова из 1 слова и значение 0 для альфы.

Результаты 1-word цепи Маркова

Вот некоторые из полученных предложений из 15 слов, где исходное слово выделено жирным шрифтом.

'the Seven in front of whitefish in a huge blazes burning flesh . I had been' 
'a squire , slain , they thought . " He bathed in his head . The' 
'Bran said Melisandre had been in fear I've done . " It must needs you will' 
'Melisandre would have feared he'd squired for something else I put his place of Ser Meryn' 
'Daenerys is dead cat - TOOTH , AT THE GREAT , Asha , which fills our' 
'Daenerys Targaryen after Melara had worn rich grey sheep to encircle Stannis . " The deep'

Как видите, полученные предложения совершенно бессмысленны, хотя и намного интереснее предыдущих.

Каждая отдельная пара слов имеет какой-то смысл, но вся последовательность не имеет смысла.

Модель действительно узнала некоторые интересные вещи, например, как Дейенерис обычно следует за Таргариеном, и «боялся бы» - довольно хорошая конструкция для знания только предыдущего слова.

Однако в целом я бы сказал, что это далеко не так хорошо, как могло бы быть.

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

Результаты с цепями Маркова из 2 слов

Цепочка из 2 слов произвела еще несколько интересных предложений.

Несмотря на то, что это тоже обычно заканчивается звучанием совершенно случайным образом, большая часть его вывода может на самом деле немного обмануть вас в начале (выделено мной).

'the world . And Ramsay loved the feel of grass welcomed them warmly , the axehead flew' 
'Jon Snow . You are to strike at him . The bold ones have had no sense' 
'Eddard Stark had done his best to give her the promise was broken . By tradition the' 
'The game of thrones , so you must tell her the next buyer who comes running ,' 
'The game trail brought her messages , strange spices . The Frey stronghold was not large enough' 
'heard the scream of fear . I want to undress properly . Shae was there , fettered'

Предложения сохраняют локальную связность (Вы должны ударить его, или Рамзи любил ощущение травы), но затем объедините очень последовательные последовательности слов в полный беспорядок.

Никакого смысла синтаксиса, грамматики или семантики явно отсутствует.

Между прочим, я вообще не выбирал эти предложения, это первые результаты, которые я выбрал.

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

В качестве последнего эксперимента давайте посмотрим, что мы получим с цепью Маркова из 3 слов.

Результаты цепочки из 3 слов

Вот некоторые предложения, которые модель сгенерировала при обучении последовательностям из 3 слов.

'I am a master armorer , lords of Westeros , sawing out each bay and peninsula until the' 
'Jon Snow is with the Night's Watch . I did not survive a broken hip , a leathern' 
'Jon Snow is with the Hound in the woods . He won't do it . " Please don't' 
'Where are the chains , and the Knight of Flowers to treat with you , Imp . "' 
'Those were the same . Arianne demurred . " So the fishwives say , " It was Tyrion's' 
'He thought that would be good or bad for their escape . If they can truly give us' 
'I thought that she was like to remember a young crow he'd met briefly years before . "'

Ладно, некоторые из них мне очень понравились, особенно последний. Это звучит как настоящая фраза, которую можно найти в книгах.

Заключение

Реализовать цепь Маркова намного проще, чем может показаться, и обучение ее на реальном корпусе было забавным.

Результаты были откровенно лучше, чем я ожидал, хотя, возможно, я поставил планку слишком низко после моего небольшого фиаско с LSTM.

В будущем я могу попробовать тренировать эту модель с еще более длинными цепями или с совершенно другим корпусом.

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

Как вы думаете, какой корпус даст более интересные результаты, особенно для более длинной цепочки? Дай мне знать в комментариях!

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

Первоначально опубликовано на http://www.datastuff.tech 25 октября 2019 г.