- PVSM.RU - https://www.pvsm.ru -
Статья посвящена описанию метода CRF (Conditional Random Fields), являющимся разновидностью метода Марковских случайных полей (Markov random field). Данный метод нашел широкое применение в различных областях ИИ, в частности, его успешно используют в задачах распознавания речи и образов, обработки текстовой информации, а также и в других предметных областях: биоинформатики, компьютерной графики и пр.
(кто не любит математики и боится формул, можно сразу перейти на «сравнение методов»).
Марковским случайным полем или Марковской сетью (не путать с Маковскими цепями) называют графовую модель, которая используется для представления совместных распределений набора нескольких случайных переменных. Формально Марковское случайное поле состоит из следующих компонентов:
Вершины, не являющиеся смежными, должны соответствовать условно независимым случайным величинам. Группа смежных вершин образует клику, набор состояний вершин является аргументом соответствующей потенциальной функции.
Совместное распределение набора случайных величин в Марковском случайном поле вычисляется по формуле:
(1) ,
где – потенциальная функция, описывающая состояние случайных величин в k-ой клике; Z – коэффициент нормализации вычисляется по формуле:
(2) .
Множество входных лексем и множество соответствующих им типов в совокупности образуют множество случайных переменных . Для решения задачи извлечения информации из текста достаточно определить условную вероятность P(Y | X). Потенциальная функция имеет вид:
, где вещественнозначный параметрический вектор, и
— набор признаковых функций. Тогда линейным условным случайным полем называется распределение вероятности вида:
.
Коэффициент нормализации тогда Z(x) вычисляется по формуле:
.
Метод CRF, как и метод MEMM (Maximum Entropy Markov Models), относится к дискриминативным вероятностным методам, в отличие от генеративных методов, таких как HMM (Hidden Markov Models) или метод «Наивного Баеса» (Naïve Bayes).
По аналогии с MEMM, выбор факторов-признаков для задания вероятности перехода между состояниями при наличии наблюдаемого значения зависит от специфики конкретных данных, но в отличие от того же МЕММ,
CRF может учитывать любые особенности и взаимозависимости в исходных данных. Вектор признаков рассчитывается на основе обучающей выборки и определяет вес каждой потенциальной функции. Для обучения и применения модели используются алгоритмы, аналогичные алгоритмам HMM: Витерби и его разновидность – алгоритм «вперед-назад» (forward-backward).
Скрытую Марковскую модель можно рассматривать как частный случай линейного условного случайного поля (CRF). В свою очередь, условное случайное поле можно рассматривать как разновидность Марковского случайного поля (см. рис).
Рис. Изображение в виде графов для методов HMM, MEMM и CRF. Незакрашенные окружности обозначают, что распределение случайной величины не учитывается в модели. Стрелки указывают на зависимые узлы.
В условных случайных полях отсутствует т.н. label bias problem – ситуация, когда преимущество получают состояния с меньшим количеством переходов, так как строится единое распределение вероятностей и нормализация (коэффициент Z(x) из формулы (5)) производится в целом, а не в рамках отдельного состояния. Это, безусловно, является преимуществом метода: алгоритм не требует предположения независимости наблюдаемых переменных. Кроме того, использование произвольных факторов позволяет описать различные признаки определяемых объектов, что снижает требования к полноте и объему обучающей выборки. В зависимости от решаемой задачи, на практике достаточно объема от нескольких сотен тысяч до миллионов термов. При этом точность будет определяться не только объемом выборки, но и выбранными факторами.
Недостатком подхода CRF является вычислительная сложность анализа обучающей выборки, что затрудняет постоянное обновление модели при поступлении новых обучающих данных.
Сравнение метода CRF с некоторыми другими методами, используемыми в компьютерной лингвистике можно найти в работе [3]. В работе показано, что предлагаемый метод работает лучше остальных (по мере F1) при решении различных лингвистических задач. Например, в задачах автоматического нахождения в тексте именованных сущностей CRF демонстрирует несколько меньшую точность по сравнению с методом MEMM, но при этом значительно выигрывает в полноте.
Следует добавить, что реализация алгоритма CRF имеет хорошую скорость, что очень важно при обработке больших объемов информации.
На сегодняшний день именно метод CRF является наиболее популярным и точным способом извлечения объектов из текста. Например, он был реализован в проекте Стэндфордского университета Stanford Named Entity Recognizer. Так же этот метод успешно реализован для разных видов лингвистической обработки текста [1].
Автор: elingur
Источник [5]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/data-mining/72490
Ссылки в тексте:
[1] разных видов лингвистической обработки текста: http://lingurus.net
[2] Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data: http://www.cis.upenn.edu/~pereira/papers/crf.pdf
[3] http://itas2013.iitp.ru/pdf/1569759547.pdf: http://itas2013.iitp.ru/pdf/1569759547.pdf
[4] http://www-nlp.stanford.edu/software/CRF-NER.shtml: http://www-nlp.stanford.edu/software/CRF-NER.shtml
[5] Источник: http://habrahabr.ru/post/241317/
Нажмите здесь для печати.