NLPx

Tales of Data Science

Условные случайные поля (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. Возможно, такой уже есть, просто я не все знаю.
  • Ссылки на статьи из этого текста могут вам пригодиться 😉

Материалы

Общее:

Педивикия про CRF (англ.)

Краткое описание с Хабра

Про CRF с большим количеством формул, для любителей (англ.)

Про label bias, для солидности (англ.)

Публикации:

Магистерская диссертация про CRF и временные выражения

Выделение ключевых слов с CRF (англ.)

Еще немного про выделение ключевых слов из текста (англ.)

CRF для русского языка

CRF vs. HMM в задачах выделения сущностей  (англ.)

Древняя публикация про выделение ключевых слов в научных текстах (англ.)

Древняя публикация про новый подход — гибкий CRF (англ.)

4,187 просмотров всего, 4 просмотров сегодня

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

Leave a Reply

Be the First to Comment!

avatar
wpDiscuz