Условные случайные поля (CRF): краткий обзор

На этой картинке вы видите условное случайное поле.

Продолжаю выкладывать тексты, которые когда-то писал по рабочей надобности. Этот текст был составлен в конце 2014 года, но вполне актуален и сейчас.

В связи с бурным развитием глубинных нейросетей мы как-то начали забывать о простых статистических тружениках машинного обучения. Хватит это терпеть!

Здесь содержится краткий конспект по алгоритму CRF (conditional random fields, условные случайные поля), который я писал для доклада на внутренней конференции. Как обычно — минимум теории (кроме самой интересной) и совсем немного занудства. Пригодится всем, кто любит краткие конспекты. Здесь все, что вы хотели знать о CRF, но боялись спросить (но это не точно).

Добро пожаловать под кат!

Что такое CRF

Conditional Random Fields (Условные случайные поля) — дискриминативная ненаправленная вероятностная графическая модель, являющаяся разновидностью марковских случайных полей (Markov random field).
Наиболее распространенной в применении является модель линейного CRF (linear chain CRF). Данная модель чаще всего применяется для решения задач разметки и сегментации последовательностей.
CRF — алгоритм машинного обучения с учителем.

Для чего применяют CRF в обработке языка

Линейный CRF хорошо подходит для решения задач сегментации и разметки последовательности, например:

автоматическое выделение ключевых слов из текстов
автоматическое выделение (именованных) сущностей
анализ тональности
частеречное тэгирование
автоматическое распознавание речи

Сложность CRF

Сложность процесса обучения CRF:

Большая. Точнее:

(1) $\begin{equation*} O(mNTQ2nS), \end{equation*}$

где:

m — количество тренировочных итераций
N — количество обучающих последовательностей (из обучающей коллекции)
T — средняя длина обучающей последовательности
Q — количество выходных классов
n – количество признаков (которые features) в обучающей матрице
S – время работы алгоритма оптимизации на каждом шаге. Хорошим, добрым алгоритмом численной оптимизации можно считать алгоритм Бройдена — Флетчера — Гольдфарба — Шанно с ограниченным использованием памяти, который буржуи изящно называют L-BFGS.

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

Это грустно.

Сложность процесса работы уже обученной модели CRF:

Чуть меньше (в случае применения алгоритма Витерби, который считается достаточно быстрым-эффективным). Точнее:

(2) $\begin{equation*} О(T|S|^3) \end{equation*}$

, где

T — количество подаваемых на вход последовательностей данных
S — количество возможных выходных классов

CRF против похожих алгоритмов (HMM, MEMM)

Родственным методом для CRF является алгоритм MEMM (Марковские модели с максимальной энтропией), также являющийся дискриминативной вероятностной моделью. Главным положительным отличием CRF от МЕММ является отсутствие проблемы смещения метки (label bias — ситуация, когда преимущество получают состояния с меньшим количеством переходов, так как строится единое распределение вероятностей и нормализация. Про это еще можно вот тут прочитать)
Сравнивать CRF и HMM (Скрытые марковские модели) таким же образом не совсем корректно, так как они относятся к разным семействам алгоритмов (HMM – генеративная, а CRF – дискриминативная модель)

Недостатки CRF

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

Достоинства CRF

По данным некоторых исследований в автоматическом выделении сущностей и ключевых слов показывает лучшие результаты (F-мера), чем MEMM или НММ (также косвенно об этом говорит факт использования CRF товарищами из Стэнфорда для создания своего знаменитого Stanford Named Entity Recognizer)
С помощью правильного выбора признаков можно достичь высокого качества тэгирования
Метод довольно гибкий в выборе признаков для обучения, причем наличие условной независимости переменных не является обязательным условием

Реализации для питона

Их очень даже немного.

Пожалуй, наиболее нормальная – это pyStruct.

Еще можно назвать CRFsuite, которая, хоть и написана на C++, но имеет обертку на Python. CRFsuite считается быстрой и качественной.

Примеры применения CRF

Выделение ключевых слов

Так как CRF – алгоритм машинного обучения с учителем, то для его обучения требуется обучающая выборка достаточного размера. При наличии хорошего обучающего корпуса и грамотного выбора признаков качество может быть где-то 0.6-0.7 по F1-мере. Кстати, далее везде качество по умолчанию будет указываться именно по F1-мере.

Однако, как показывают исследования, качество работы подобных схем не поднимается выше 0.5-0.6. Например, исследователи из Индии тренировали CRF на корпусе медицинских текстов для выделения ключевых научных терминов (и вроде бы даже признаки неплохо выбрали) и все равно получили качество меньше 0.4 на реальных текстах. Вот такая грусть.

Выделение сущностей

Значительно лучше CRF ведет себя при выполнении задачи выделения сущностей.

Например, товарищи из ВШЭ и СПбГУ утверждают, что если обучить CRF на хорошем большом корпусе (не менее 70 000 предложений, в каждом из которых не менее одной именованной сущности + нелингвистические признаки), то можно получить качество около 0.9. Сомнительно, потому как, например, знаменитый Стэнфордский NER выдает среднее реальное качество выделения сущностей для английского в 0.81 (это при том, что обучался на нескольких далеко не маленьких корпусах именованных сущностей CoNLL, MUC-6, MUC-7 и ACE, а признаки выделяли такие весёлые товарищи, как, например, Кристофер Мэннинг).

Еще исследователи из Испании и России сравнивали HMM и CRF при выделении именованных сущностей в медицинских текстах. На большом корпусе (JNLPBA – 18546 предложений, 109 588 именованных сущностей) натренировали оба алгоритма. В итоге у НММ была выше полнота (на 4-7% для различных типов сущностей), а у CRF – точность (на 4-13% для различных типов сущностей). Среднее значение F-меры при проверке на реальных текстах составило ~0.65 для HMM и ~0.69 для CRF. В качестве вывода авторы предположили, что, совместив НММ и CRF, можно повысить качество выделения именованных сущностей на 5-10%.

Выделение временных выражений

Это тоже сущности, да, но несколько особенный их подвид, поэтому выделил в отдельный пункт 🙂

В одной из магистерских диссертаций говорится, что с задачей выделения временных выражений для русского языка линейный CRF справился хорошо — 0.93 при кросс-валидации. Но это при:

качественном отборе признаков
тренировке на вручную размеченных 2000 предложений из OpenCorpora (где было около 500 временных выражений),
итеративном подходе к обучению (типа натренировали – проверили — посмотрели, что не понравилось – добавили новых признаков – повторили процесс).

При реальной работе, полагаю, было бы не больше 0.7-0.75. Но тоже вполне неплохо.

Анализ тональности

По словам исследователей из ВШЭ, при анализе тональности коротких сообщений из Твиттера были достигнуты результаты в среднем 0.7-0.8 на реальных текстах. Обучение производилось на вручную размеченном корпусе из 20 000 твитов, где было выделено около 21 000 объектов, индицирующих тональность. Тональность определялась трех типов – нейтральная (0.91 при кросс-валидации), положительная (0.84 при кросс-валидации), отрицательная (0.84 при кросс-валидации). При проверке на реальных текстах качество работы алгоритма было 0.74.

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

Выводы

Для выделения ключевых слов годится не то, чтобы очень, так как он не работает с неизвестными ему словами, а для добавления новых данных в обучающую коллекцию надо заново полностью переобучать модель, а это обычно не быстро. Качество работы алгоритма даже с известными словами при самых лучших условиях не выше 0.6-0.7, а обычно около 0.5 и ниже. Плюс проблема разметки обучающей коллекции — для повышения качества это надо делать вручную.
Для выделения сущностей (именованных, временных, числовых и т.д.) годится хорошо, так как есть возможность кроме непосредственно лингвистических учитывать еще и нелингвистические признаки (регистр, пунктуацию, пробелы и т.д.). Качество при хорошем выделении признаков и настолько же хорошей обучающей коллекции — в среднем районе 0.7-0.85 на реальных текстах, что приятно.
Интересная идея собрать гибридный алгоритм из НММ+CRF для выделения сущностей. В теории этот овцебык мог бы улучшить общее качество по F-мере на 5-10% и составить 0.85-0.9. Возможно, такой уже есть, просто я не все знаю.
Ссылки на статьи из этого текста могут вам пригодиться 😉