Краткое и практическое введение в цепи Маркова.
Цепи Маркова - это вероятностные модели, которые генерируют значения путем случайного перехода из одного состояния в другое. Следующее состояние определяется исключительно текущим состоянием и вероятностью перехода в следующее состояние. Их простота делает их отличным введением в прогнозные модели без необходимости знать какие-либо специализированные библиотеки, такие как PyTorch и TensorFlow.
Как работают цепи Маркова?
На абстрактном уровне цепь Маркова представляет собой набор конечного числа состояний и переходов, которые описывают случайные изменения из одного состояния в другое. Их можно использовать для моделирования событий, в которых изменения происходят случайным образом, но все же подчиняются некоторому распределению вероятностей.
Когда цепь Маркова записывает переход из одного состояния в другое во время обучения, она регулирует веса перехода, чтобы сделать этот переход более вероятным во время прогнозирования. Если модель обучается на данных, где переход A → B в два раза более вероятен, чем A → C, то, когда модель находится в состоянии A, следующим состоянием может быть B или C, но это будет в два раза больше вероятности быть B .
Простой пример
Допустим, мы обучаем цепь Маркова словам «BAT» и «BIT». Мы будем использовать точку (.) Для обозначения конца слова. Вот как будет выглядеть цепочка:
Когда модель используется для прогнозирования, она выполняет случайное блуждание.
При случайном блуждании мы начинаем с состояния «начало». Существует определенная вероятность изменения состояния на «B», поэтому он это делает. В «B» следующим состоянием с равной вероятностью будет «A» или «I». Изменение является случайным («случайная» часть случайного блуждания), но все же следует распределению вероятностей. Скажем, оно перешло к «Я». Затем он переходит в «T» (вероятность 1,0) и, наконец, в конечное состояние (состояние «.»). Модель собирала слово «BIT», но с такой же вероятностью собирала «BAT».
Эта конкретная цепь Маркова не может переходить в предыдущие состояния; он мог генерировать только слова, которые видел раньше.
Более сложный пример
Цепи Маркова не обязательно должны следовать линейному потоку. Давайте возьмем цепочку из предыдущего примера и обучим ее слову «БИИТАТ»:
Теперь существует вероятность того, что модель останется в состоянии «I» и перейдет из состояния «T» обратно в состояние «A». Теперь модель может генерировать слова, которых она никогда раньше не видела, например «BATATAT» и «BIIIIIIIT»! Эти слова менее вероятны, но все же возможны. Представьте, что он мог бы сделать, если бы мы скормили ему больше данных!
Пока в конце каждого слова, с которым мы его обучаем, стоит точка (конечное состояние), случайное блуждание в конечном итоге достигнет конечного состояния.
Создание фантастических имен
Забавное приложение цепей Маркова генерирует фантастические имена. Получив достаточно данных, они будут следить за общими тенденциями обучающих данных, постоянно перетасовывая шаблоны, из которых они состоят. В конце концов, сгенерированные слова просто составлены из шаблонов ранее увиденных.
Мне кажется, что торговые марки фармацевтических препаратов всегда имеют к ним интерес. У них нет словарного значения, но обычно есть узнаваемые шаблоны, из-за которых они звучат как «названия лекарств». Мы будем использовать цепь Маркова, чтобы сгенерировать эти имена.
Данные
FDA ведет Справочник национального лекарственного кодекса (NDC) для всех одобренных лекарств. После отделения собственного имени от электронной таблицы и фильтрации имен, содержащих специальные символы, числа и пробелы, у меня остался список из 3403 имен, которые затем можно было использовать для обучения.
Ссылка на репозиторий GitHub, содержащий отфильтрованные и необработанные данные, находится в конце статьи.
Реализация цепей Маркова
В предыдущих примерах я нарисовал цепи Маркова в виде графов с узлами и связями. Узлы и ссылки упрощают отслеживание и визуализацию, но их непрактично реализовать. Мы будем реализовывать цепь Маркова как вложенный словарь Python. Ключ внешнего словаря - это «текущее состояние»; значение внешнего словаря - это другой словарь, представляющий переходы, где ключ - это «следующее состояние», а значение - частота, с которой наблюдался переход.
Этот подход сложнее визуализировать, гораздо проще получить доступ к состоянию, просто выполнив chain['state'] вместо обхода графа. Вот пример того, как будет выглядеть запись для состояния «T» на рисунке 1.2:
chain['T'] = {
'A' : 1, # T -> A transition in BIITAT
'.': 3 # T -> '.' transition in BIT, BAT, BIITAT
}
Также имеет смысл сохранять частоты переходов - их нужно только увеличивать во время обучения, тогда как все вероятности необходимо пересчитывать.
Построение цепочки
Вот как мы построим цепочку в Python:
Случайная прогулка
Несмотря на то, что во время обучения мы видели тысячи имен, обычное случайное блуждание по цепочке, как описано в примерах, порождает мусор. Большинство сгенерированных имён не содержат zang (например: просто «ae»); должны быть установлены некоторые правила, чтобы имена выглядели немного фанковыми.
Хотя я сказал ранее, что следующее состояние цепи Маркова зависит исключительно от текущего состояния, для этого приложения имеет больше смысла учитывать предыдущее состояние, чтобы генерировать лучшие имена, проверяя правила.
Я также считаю конечный символ (‘.’) И пустой символ (‘’) как гласные; это предотвращает начало или окончание слова двумя гласными.
Функция pick_char(), которая производит случайный выбор следующего состояния, работает следующим образом:
- Суммируются частоты всех следующих состояний.
- Случайное значение от 0 до 1 генерируется и умножается на сумму частот. Это значение находится между 0 и суммой частот.
- В каждом «следующем состоянии» частотного словаря частота этого состояния вычитается из случайного значения. Если случайное значение меньше нуля, то это «следующее состояние» является выбранным «следующим состоянием», в противном случае мы переходим к следующему «следующему состоянию» и делаем то же самое. Это выбирает состояние случайным образом в зависимости от вероятности его появления.
Функция next_char() совершает случайное блуждание. Это рекурсивно. Он вызывает pick_char(), пока не вернет символ, удовлетворяющий правилам. Затем он повторяется с вновь созданным «следующим состоянием» в качестве нового «текущего состояния» и ранее «текущим» состоянием в качестве предыдущего состояния.
Собираем все вместе…
Теперь мы можем вызвать ранее обсужденные функции, чтобы выполнить случайное блуждание по цепи Маркова и сгенерировать несколько имен!
И вот что мы получаем, когда запускаем его:
flurimbin kenzaidel uvinaze colmix iluprarax zelare irevene enxophir trexin hysesox
Заключение
Построение цепи Маркова для генерации вымышленных имен - забавное введение в стохастические процессы. Помимо вымышленных имен, цепи Маркова и процессы Маркова в более широком смысле могут быть использованы для «прогнозов» и генерации значений, где изменения являются результатом случайности. Я надеюсь, что вы попробуете этот простой проект и, возможно, расширите его для других целей.
Вот репозиторий GitHub, содержащий код и данные для этого проекта (генератор также реализован на JavaScript!). Данные могут быть немного устаревшими.
