Для проекта распознавания сканов документов были изучены существующие подходы к решению задачи NER (Named Entity Recognition). Среди огромного множества решений на основе трансформеров был обнаружен один занятный алгоритм – Conditional Random Fields (CRF). Пытаясь разузнать о нем больше, было замечено, что в русском сегменте нет простого и понятного объяснения без горы математических доказательств. В данной статье предпринята попытка исправить это и рассказать простым языком о том, как устроен алгоритм CRF и какие возможности он имеет. Зачем это надо?

Когда мы читаем какое-то предложение или текст, то интуитивно понимаем, о чем там идет речь. Заставить компьютер понять это несколько сложнее, однако в случае успеха можно было бы автоматически извлекать важную информацию из текста, производить синтаксический разбор предложения и устанавливать связи между словами. К сожалению, найти слова, на которых строится смысл предложения является довольно непростой задачей. В качестве самого простого решения мы могли просто классифицировать каждое слово (токен) и таким образом размечать последовательность, однако в естественном языке дела обстоят несколько сложнее. Рассмотрим задачу POS-тэггинга: в данной задаче нам необходимо определить, к какой части речи относится каждое слово в тексте. Во всех языках смысл слова, а следовательно, и его часть речи, зависит от контекста, в котором он употребляется. Например, в предложении «Три дня лил дождь» слово «три» имеет часть речи «числительное» и обозначает число, а в предложении «Три паркет» слово «три» имеет часть речи «глагол» и обозначает действие.

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

Что такое CRF? При чем тут HMM?

По сути, CRF (Conditional Random Fields) является более общим случаем Скрытой Марковской Модели (HMM – Hidden Markov Model) и многие принципы, используемые в CRF, унаследованы из принципов HMM. В связи с этим невозможно рассказать об устройстве CRF, не затронув скрытые марковские модели, поэтому я бы сначала хотел рассказать о них.

Для того, чтобы понять, что такое скрытая марковская модель рассмотрим небольшой пример:

Представим, что в Новый Год Дед Мороз ставит подарки под елку. С собой у него три мешка с подарками, в каждом мешке лежит некоторое количество подарков четырех цветов. Дед Мороз с некоторой вероятностью выбирает один мешок и достает из него подарок случайным образом. Затем для следующего подарка Дед Мороз выполняет ту же процедуру, оставляя тот же мешок, либо меняя его на другой. Таким образом мы выстроили систему, где вероятность встретить подарок определенного цвета на определенной позиции зависит от множества других факторов: какой мешок выбран, сколько подарков было изъято из мешка ранее и т.д.

Как устроен HMM 

В основе всего – состояния

Работа скрытых марковских моделей основана на состояниях – скрытых и наблюдаемых. Скрытые состояния – это состояния, которые, как следует из названия, скрыты от нас, мы не можем наблюдать их, в примере выше скрытые состояния – это мешки, из которых достают подарки: на утро, увидев подарки, мы не знаем из какого мешка был изъят каждый подарок. Наблюдаемые состояния – это состояния, которые мы можем наблюдать, как результат работы модели, в примере выше это цвет подарка. Ситуация из примера выше описывает скрытую марковскую модель, в которой есть 3 скрытых состояния и 4 наблюдаемых.

Немного о параметрах:

Прежде всего стоит рассказать о параметрах, которые содержит скрытая марковская модель. Пусть N – количество скрытых состояний, M – количество наблюдаемых состояний

•         π – вектор начального состояния размерности N, содержит вероятности оказаться в i-м состоянии на первом шаге.

• A – матрица переходов размерности NxN, ij-элемент этой матрицы содержит вероятность перейти из состояния i в состояние j.

• B – матрица наблюдений размерности NxM, ij-элемент этой матрицы содержит вероятность наблюдать j-ое наблюдение из i-ого состояния.

  Таким образом, вероятность некоторой последовательности будет равна произведению соответствующих вероятностей из вектора π, матрицы перехода A и матрицы наблюдений B.

Марковское свойство

Еще одна основополагающая вещь скрытой марковской модели – это марковское свойство. Заключается оно в следующем: состояние на временном шаге t зависит только от состояния на шаге t-1. Марковскому свойству подчиняются только скрытые состояния, то есть скрытое состояние на шаге t зависит только от предыдущего скрытого состояния. Наблюдаемые состояния зависят только от текущего скрытого состояния и не зависят от других наблюдаемых состояний. Ниже можно посмотреть на графическое представление скрытой марковской модели для того, чтобы лучше понять, как взаимодействуют состояния.

Результатом работы скрытой марковской модели будет такая последовательность наблюдаемых состояний, которая наиболее вероятна при заданных параметрах. Однако количество таких последовательностей экспоненциально растет с увеличением количества состояний, поэтому просто посчитать вероятность всех последовательностей и выбрать наиболее вероятную не выйдет. Нужен иной подход к оценке вероятности последовательности, к счастью, такой метод уже имеется.

Оценка вероятности последовательности

Для оценки вероятности последовательности в скрытых марковских моделях используются приемы динамического программирования. Сам алгоритм носит название «Forward-Backward». Состоит он из двух частей: forward procedure и backward procedure. Остановимся на каждой части подробнее.

Первая часть, forward procedure, содержит в себе прямой проход по модели, от начала в конец. На данном этапе мы считаем вероятность последовательности для каждого наблюдаемого состояния на каждом шаге. В тривиальном случае (длина равна 1) эти вероятности будут равны вектору π. Для остальных случаев эти вероятности будут равны вероятностям предыдущего шага, умноженным на вероятность перехода в текущее скрытое состояние и вероятность наблюдения из этого скрытого состояния. Это можно выразить в виде следующей рекуррентной формулы:

В результате мы получаем набор значений

 – вероятностей наблюдать последовательность

 и закончить в скрытом состоянии i.

Как уже упоминалось выше, на вероятность отдельного наблюдения может влиять не только предыдущий контекст, но и последующий, поэтому полученные нами вероятности α не точны. Для уточнения этих вероятностей и выполняется второй шаг, backward procedure. На данном этапе мы выполняем те же действия с одним лишь изменением: в этот раз мы идем из конца в начало. В тривиальном случае (длина равна 1) вероятности принимаются равными 1. В виде рекуррентной формулы это выглядит так:

В результате мы получаем набор значений

 – вероятность наблюдать последовательность

 при исходном скрытом состоянии i.

Теперь дело остается за малым, нужно лишь скомбинировать полученные вероятности α и β:

В результате мы получили распределение вероятностей всех последовательностей при заданных параметрах модели. Теперь остается лишь найти ту последовательность, которой соответствует наибольшая вероятность.

Алгоритм Витерби

Поскольку количество последовательностей очень велико, простой перебор последовательностей не приведет нас к ответу за приемлемое время. К счастью, для поиска наиболее вероятной последовательности так же имеется особый алгоритм, называемый алгоритмом Витерби.

Данный алгоритм очень похож на описанный выше «Forward-Backward» алгоритм и так же имеет Forward и Backward этапы. Первый этап представляет собой forward часть с тем лишь изменением, что мы не считаем сумму по всем скрытым состояниям предыдущего шага, а выбираем то состояние, которому соответствует наибольшая вероятность. Для тривиального случая вероятности, как и в forward-backward алгоритме, соответствуют значениям вектора π. Нововведением данного алгоритма является то, что помимо значений вероятностей мы будем хранить так же указатели, которые показывают состояние, выбранное операцией максимума. Формулы, описывающие данные действия, выглядят следующим образом:

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

Теперь рассмотрим вторую часть алгоритма Витерби. Зная конечные вероятности последовательностей, мы можем узнать, какая последовательность из итоговых имела наибольшую вероятность. Поскольку до этого момента мы сохраняли указатели, мы можем узнать, из какого состояния был совершен переход в текущее. Данная процедура повторяется пока мы не окажемся в одном из начальных состояний. Собранную последовательность состояний нужно инвертировать, тогда полученная последовательность, называемая «путем Витерби», и будет являться наиболее вероятной последовательностью наблюдений.

Теперь мы имеем базовое представление о том, как устроена скрытая марковская модель. Этих знаний достаточно, чтобы понимать концепцию, заложенную внутрь CRF. Скрытая марковская модель еще содержит в себе идеи, не изложенные в данной статье, например алгоритм расчета параметров (обучения) HMM. Обучение HMM происходит с помощью алгоритма Баума-Велша, который является модификацией уже описанного forward-backward алгоритма. Ознакомиться с ним можно по ссылке под статьей, читателю предлагается самостоятельно изучить его.

Переходим к CRF

Скрытая марковская модель долгое время показывала хорошие результаты в различных задачах, однако с ростом популярности нейронных сетей стала использоваться заметно реже. Сейчас редко где можно встретить применение скрытой марковской модели, зато большую актуальность имеет алгоритм, обобщающий принципы HMM – условные случайные поля (CRF).

Главное идейное отличие CRF от HMM: наблюдаемые состояния зависят не только от текущего скрытого состояния, а сразу от всех скрытых состояний последовательности. Данный трюк позволяет расширить захватываемый контекст наблюдаемых состояний и избавиться от локальности, присущей HMM.

По своей сути CRF представляет собой обычную нейронную сеть с двумя полносвязными слоями, исполняемыми независимо друг от друга. Один слой характеризует матрицу переходов (A в нотации HMM), другой слой характеризует матрицу наблюдений (B в нотации HMM). Ниже представлено уравнение, характеризующее CRF:

Давайте заглянем внутрь экспоненты: каждое слагаемое суммы состоит из двух частей.

 Примечательным здесь является множитель f – это так называемая featurefunction. В качестве featurefunction может использоваться любая функция, которая возвращает представление исходных данных в виде вектора чисел. Часто в качестве featurefunctionиспользуется выход какой-либо нейронной сети, что позволяет использовать CRFдля улучшения предсказаний уже готовой модели. Пусть вас не пугает нормирующая переменная. Она позволяет получить корректное распределение вероятностей.

Еще одним замечательным фактом является то, что CRF способна обучаться градиентными методами. Это означает, что CRF можно встроить в готовый пайплайн и обучать CRF совместно с моделью более низкого уровня.

Примеры применения можно найти здесь

С приходом моделей на основе архитектуры Transformer CRF уже не показывает SOTA результаты в задачах sequence labeling, однако он все еще не потерял свою актуальность. Основная причина, по которой CRF еще применяется в различных ML решениях – это возможность использовать конечные скрытые состояния рекуррентной нейронной сети в качестве входных фичей и возможность встроить CRF в готовый NLP пайплайн и обучать сети совместно. На этом я бы хотел закончить данную статью, надеюсь, она помогла читателю понять математическую идею, стоящую за таким алгоритмом, как CRF.

Автор статьи: Матвей Колтунов, исследователь R&D центра компании UDV Group

Ссылки:

• Лекция Валентина Малых на ODS.AI про HMM и CRF

• Алгоритм Баума-Велша

• Скрытая марковская модель

• Алгоритм «вперед-назад»