Марковские случайные поля

  • Tutorial
Статья посвящена описанию метода CRF (Conditional Random Fields), являющимся разновидностью метода Марковских случайных полей (Markov random field). Данный метод нашел широкое применение в различных областях ИИ, в частности, его успешно используют в задачах распознавания речи и образов, обработки текстовой информации, а также и в других предметных областях: биоинформатики, компьютерной графики и пр.

Краткое описание метода
(кто не любит математики и боится формул, можно сразу перейти на «сравнение методов»).
Марковским случайным полем или Марковской сетью (не путать с Маковскими цепями) называют графовую модель, которая используется для представления совместных распределений набора нескольких случайных переменных. Формально Марковское случайное поле состоит из следующих компонентов:
  • неориентированный граф или фактор-граф G = (V, E), где каждая вершина является случайной переменной Х и каждое ребро представляет собой зависимость между случайными величинами u и v.
  • набор потенциальных функций (potential function) или факторов , одна для каждой клики (клика — полный подграф G неориентированного графа) в графе. Функция ставит каждому возможному состоянию элементов клики в соответствие некоторое неотрицательное вещественнозначное число.

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

Совместное распределение набора случайных величин в Марковском случайном поле вычисляется по формуле:

(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. Lafferty J., McCallum A., Pereira F. “Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data”. Proceedings of the 18th International Conference on Machine Learning. 282-289. 2001.
  2. Klinger R., Tomanek K.: Classical Probabilistic Models and Conditional Random Fields. Algorithm Engineering Report TR07-2-013. of Computer Science. Dortmund University of Technology. December 2007. ISSN 1864-4503.
  3. Антонова А.Ю., Соловьев А.Н. Метод условных случайных полей в задачах обработки русскоязычных текстов. «Информационные технологии и системы — 2013», Калининград, 2013.
    http://itas2013.iitp.ru/pdf/1569759547.pdf
  4. Stanford Named Entity Recognizer // http://www-nlp.stanford.edu/software/CRF-NER.shtml
Share post

Similar posts

AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 12

    0
    >но в отличие от того же МЕММ, CRF может учитывать любые особенности и взаимозависимости в исходных данных

    Честно говоря не совсем понял этот момент. Можете привести пример особенностей и/или взаимозависимостей в исходных данных, которые может учитывать CRF но не может учитывать MEMM?
      0
      Попробую. Например, мы решаем задачу выделения именованных сущностей в тексте (NER). В МЕММ используется, как правило, контекст, т.е. частотность окружения, по которому вычисляется максимум энтропии. В CRF помимо словесного контекста может параллельно (или одновременно) использоваться морфологические, синтаксические и пр. характеристики окружения. Иными словами: MEMM — это линейный одномерный граф (точнее просто перебор цепочек), а CRF — это многомерный граф, который учитывает целый комплекс факторов, влияющих на результат.
        0
        Расскажите подробнее про задачу NER. Удалось ли получить хорошие результаты? Какая точность, полнота? Можно где-то посмотреть, как оно работает?
          0
          Точность и полнота зависит от кол-ва определяемых сущностей. Скажем, при определении медицинских или биологических терминов (их десятки, а иногда и сотни) точность достигает 75-80%. Если стандартный набор: люди, компании, гео — то более 90%. Сравнительный анализ методов есть в работе . Хороший обзор с демо можно посмотреть тут, тут (наиболее интересный вариант) или почитать с примерами тут .
          0
          По-видимому имеется в виду, что CRF «концептуально» может содержать признаки вида F(Y,X), где X — вектор данных «на входе», Y — вся разметка «на выходе» (например, при разметке частей речи (part-of-speech, POS) — сразу все части речи для всех слов предложения), в то время как MEMM может содержать лишь признаки вида F(y[i],y[i-1],...,y[i-n],X), то есть например, для данного слова мы «видим» лишь часть речи самого этого слова и его ближайших соседей. Однако если мы хотим использовать быстрые алгоритмы Витерби и forward-backward, то это преимущество CRF уходит, так как мы вынуждены ограничить признаки тем же видом, что в MEMM. Хотя другое преимущество — отсутствие проблемы labeling bias остаётся.

          Что касается морфологических и синтаксических характеристик именно локального «окружения», то насколько я могу судить это «видит» и MEMM.
            0
            Да, МЕММ может «видеть» морфо и синт. характеристики, но не за один проход, а за несколько, в итоге решение задачи сведется к Марковской сети.
            Однако если мы хотим использовать быстрые алгоритмы Витерби и forward-backward, то это преимущество CRF уходит, так как мы вынуждены ограничить признаки тем же видом, что в MEMM.

            — не понял, почему? СRF работает не по всему тексту, а в пределах графа, который мы сами выберем соответственно выбранным признакам, последовательно проходя по тексту (если мы говорим о линейном CRF).
        0
        Если при переводе текста каждое слово переводить во все его варианты, то потом можно «схлопнуть» на основе цепей Маркова эти «вероятности» и получить более менее правильный текст.
          0
          Разница цепей Маркова от сетей Маркова заключается в том, что первые генеративны (т.е. предсказывают вероятность следующего шага), а вторые — дискриминатины, т.е. рассчитывают вероятность текущего состояния. Использовать тот или иной алгоритм зависит от решаемой задачи. А второе, и наиболее важное отличие — это то, что сети Маркова учитывают не только шаг (два и т.д.) вправо-влево по какому-либо из параметров, а по пучку взаимосвязанных параметров. Скажем, для перевода это не только все его варианты, а и тематический контекст перевода, синтаксис и пр.
            0
            Я взял лук, и, скушав лук, начал луком резать лук.
            Цепи Маркова «обученные» по двум языкам подскажут кто их них bow, а кто onion. Но подскажут именно вероятность выбора.
              0
              Аналогично и сети Макрова, только за счет многофакторности (графа) дают предсказание более точное.
          0
          А почему бы не использовать раскрашенные сети Петри?
            0
            ну почему бы и не попробовать. Правда, насколько мне известно, в обработке текстовых данных это еще не использовали. В данной статье сравниваются статистические методы, с сетями Петри я не сравнивал результат.

          Only users with full accounts can post comments. Log in, please.