На этой картинке вы видите условное случайное поле.
Продолжаю выкладывать тексты, которые когда-то писал по рабочей надобности. Этот текст был составлен в конце 2014 года, но вполне актуален и сейчас.
В связи с бурным развитием глубинных нейросетей мы как-то начали забывать о простых статистических тружениках машинного обучения. Хватит это терпеть!
Здесь содержится краткий конспект по алгоритму CRF (conditional random fields, условные случайные поля), который я писал для доклада на внутренней конференции. Как обычно — минимум теории (кроме самой интересной) и совсем немного занудства. Пригодится всем, кто любит краткие конспекты. Здесь все, что вы хотели знать о CRF, но боялись спросить (но это не точно).
Добро пожаловать под кат!
Что такое CRF
- Conditional Random Fields (Условные случайные поля) — дискриминативная ненаправленная вероятностная графическая модель, являющаяся разновидностью марковских случайных полей (Markov random field).
- Наиболее распространенной в применении является модель линейного CRF (linear chain CRF). Данная модель чаще всего применяется для решения задач разметки и сегментации последовательностей.
- CRF — алгоритм машинного обучения с учителем.
Для чего применяют CRF в обработке языка
Линейный CRF хорошо подходит для решения задач сегментации и разметки последовательности, например:
- автоматическое выделение ключевых слов из текстов
- автоматическое выделение (именованных) сущностей
- анализ тональности
- частеречное тэгирование
- автоматическое распознавание речи
Сложность CRF
Сложность процесса обучения CRF:
Большая. Точнее:
(1)
где:
- m — количество тренировочных итераций
- N — количество обучающих последовательностей (из обучающей коллекции)
- T — средняя длина обучающей последовательности
- Q — количество выходных классов
- n – количество признаков (которые features) в обучающей матрице
- S – время работы алгоритма оптимизации на каждом шаге. Хорошим, добрым алгоритмом численной оптимизации можно считать алгоритм Бройдена — Флетчера — Гольдфарба — Шанно с ограниченным использованием памяти, который буржуи изящно называют L-BFGS.
На практике, кстати, вычислительная/временная сложность обучения CRF даже выше за счет всяких дополнительных операций, вроде сглаживания, преобразования данных из формата в формат и т.д.
Это грустно.
Сложность процесса работы уже обученной модели CRF:
Чуть меньше (в случае применения алгоритма Витерби, который считается достаточно быстрым-эффективным). Точнее:
(2)
, где
- 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 vs. HMM в задачах выделения сущностей (англ.)
Древняя публикация про выделение ключевых слов в научных текстах (англ.)
Древняя публикация про новый подход — гибкий CRF (англ.)
23,594 просмотров всего, 2 просмотров сегодня
Leave a Reply