Условное случайное поле - Conditional random field

Условные случайные поля (CRF) являются классом метод статистического моделирования часто применяется в распознавание образов и машинное обучение и используется для структурированный прогноз. В то время как классификатор предсказывает метку для одного образца без учета «соседних» образцов, CRF может учитывать контекст. Для этого прогноз моделируется как графическая модель, который реализует зависимости между прогнозами. Какой вид графика используется, зависит от приложения. Например, в обработка естественного языка популярны линейные цепные CRF, которые реализуют последовательные зависимости в предсказаниях. При обработке изображений граф обычно связывает местоположения с соседними и / или аналогичными местоположениями, чтобы обеспечить получение аналогичных прогнозов.

Другие примеры использования CRF: маркировка или же разбор последовательных данных для обработка естественного языка или же биологические последовательности,^[1] POS-теги, неглубокий разбор,^[2] признание названного лица,^[3] поиск генов, поиск критических функциональных областей пептидов,^[4] и распознавание объектов^[5] и сегментация изображения в компьютерное зрение.^[6]

Описание

CRF являются разновидностью отличительный ненаправленный вероятностный графическая модель.

Лафферти, Маккаллум и Перейра^[1] определить CRF по наблюдениям ${displaystyle {oldsymbol {X}}}$ и случайные переменные ${displaystyle {oldsymbol {Y}}}$ следующее:

Позволять ${displaystyle G=(V,E)}$ граф такой, что

${displaystyle {oldsymbol {Y}}=({oldsymbol {Y}}_{v})_{vin V}}$, так что ${displaystyle {oldsymbol {Y}}}$ индексируется вершинами ${displaystyle G}$. потом ${displaystyle ({oldsymbol {X}},{oldsymbol {Y}})}$ является условным случайным полем, когда случайные величины ${displaystyle {oldsymbol {Y}}_{v}}$, при условии ${displaystyle {oldsymbol {X}}}$, подчиняться Марковская собственность относительно графика: ${displaystyle p({oldsymbol {Y}}_{v}|{oldsymbol {X}},{oldsymbol {Y}}_{w},weq v)=p({oldsymbol {Y}}_{v}|{oldsymbol {X}},{oldsymbol {Y}}_{w},wsim v)}$, куда ${displaystyle {mathit {w}}sim v}$ Значит это ${displaystyle w}$ и ${displaystyle v}$ находятся соседи в ${displaystyle G}$.

Это означает, что CRF - это неориентированная графическая модель узлы которого можно разделить ровно на два непересекающихся множества ${displaystyle {oldsymbol {X}}}$ и ${displaystyle {oldsymbol {Y}}}$, наблюдаемые и выходные переменные соответственно; условное распределение ${displaystyle p({oldsymbol {Y}}|{oldsymbol {X}})}$ затем моделируется.

Вывод

Для общих графов проблема точного вывода в CRF неразрешима. Проблема вывода для CRF в основном такая же, как для MRF и те же аргументы верны.^[7]Однако существуют особые случаи, для которых возможен точный вывод:

• Если граф представляет собой цепочку или дерево, алгоритмы передачи сообщений дают точные решения. Используемые в этих случаях алгоритмы аналогичны вперед назад и Алгоритм Витерби для случая HMM.
• Если CRF содержит только парные потенциалы и энергия равна субмодульный комбинаторные алгоритмы минимального отсечения / максимального расхода дают точные решения.

Если точный вывод невозможен, можно использовать несколько алгоритмов для получения приближенных решений. К ним относятся:

• Путевое распространение убеждений
• Альфа-расширение
• Вывод среднего поля
• Расслабления в линейном программировании

Параметр обучения

Изучение параметров ${displaystyle heta }$ обычно делается максимальная вероятность обучение для ${displaystyle p(Y_{i}|X_{i}; heta )}$. Если все узлы имеют экспоненциальное распределение семейств и все узлы наблюдаются во время обучения, это оптимизация выпуклый.^[7] Это можно решить, например, используя градиентный спуск алгоритмы, или Квазиньютоновские методы такой как L-BFGS алгоритм. С другой стороны, если некоторые переменные не наблюдаются, проблема вывода должна быть решена для этих переменных. Точный вывод на обычных графиках невозможен, поэтому необходимо использовать приближения.

Примеры

При моделировании последовательности интересующий граф обычно представляет собой цепной граф. Входная последовательность наблюдаемых переменных ${displaystyle X}$ представляет собой последовательность наблюдений и ${displaystyle Y}$ представляет скрытую (или неизвестную) переменную состояния, которая должна быть выведена с учетом наблюдений. В ${displaystyle Y_{i}}$ структурированы так, чтобы образовать цепочку, с ребром между каждым ${displaystyle Y_{i-1}}$ и ${displaystyle Y_{i}}$. Помимо простой интерпретации ${displaystyle Y_{i}}$ в качестве «меток» для каждого элемента входной последовательности этот макет допускает эффективные алгоритмы для:

• модель обучение персонала, изучая условные распределения между ${displaystyle Y_{i}}$ и функции функций из некоторого корпуса обучающих данных.
• расшифровка, определяя вероятность данной последовательности меток ${displaystyle Y}$ данный ${displaystyle X}$.
• вывод, определяя скорее всего последовательность этикеток ${displaystyle Y}$ данный ${displaystyle X}$.

Условная зависимость каждого ${displaystyle Y_{i}}$ на ${displaystyle X}$ определяется через фиксированный набор функции функции формы ${displaystyle f(i,Y_{i-1},Y_{i},X)}$, которые можно рассматривать как измерения входной последовательности, частично определяющие вероятность каждого возможного значения для ${displaystyle Y_{i}}$. Модель присваивает каждой характеристике числовой вес и объединяет их, чтобы определить вероятность определенного значения для ${displaystyle Y_{i}}$.

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

Примечательно, что в отличие от HMM, CRF могут содержать любое количество функций функций, функции функций могут проверять всю входную последовательность. ${displaystyle X}$ в любой момент во время вывода, и диапазон функций признаков не обязательно должен иметь вероятностную интерпретацию.

Варианты

CRF высшего порядка и полумарковские CRF

CRF можно расширить до моделей более высокого порядка, сделав каждый ${displaystyle Y_{i}}$ зависит от фиксированного числа ${displaystyle k}$ предыдущих переменных ${displaystyle Y_{i-k},...,Y_{i-1}}$. В обычных формулировках CRF более высокого порядка обучение и логический вывод практичны только для небольших значений ${displaystyle k}$ (Такие как k ≤ 5),^[8] поскольку их вычислительные затраты растут экспоненциально с увеличением ${displaystyle k}$.

Однако еще одно недавнее достижение помогло решить эти проблемы за счет использования концепций и инструментов из области байесовской непараметрии. В частности, подход CRF-бесконечности^[9] представляет собой модель CRF-типа, которая способна изучать бесконечно длительную временную динамику масштабируемым образом. Это достигается за счет введения новой потенциальной функции для CRF, которая основана на Sequence Memoizer (SM), непараметрической байесовской модели для изучения бесконечно длинной динамики в последовательных наблюдениях.^[10] Чтобы сделать такую ​​модель доступной для вычислений, CRF-infinity использует приближение среднего поля^[11] постулируемых новых потенциальных функций (которыми управляет СМ). Это позволяет разрабатывать эффективные алгоритмы приближенного обучения и вывода для модели, не подрывая ее способность фиксировать и моделировать временные зависимости произвольной длины.

Существует еще одно обобщение CRF: полумарковское условное случайное поле (полу-CRF), который моделирует переменную длину сегментации последовательности меток ${displaystyle Y}$.^[12] Это обеспечивает большую часть возможностей CRF более высокого порядка для моделирования дальнодействующих зависимостей ${displaystyle Y_{i}}$, по разумной вычислительной стоимости.

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

Латентно-динамическое условное случайное поле

Латентно-динамические условные случайные поля (LDCRF) или же дискриминативные вероятностные модели со скрытыми переменными (DPLVM) являются типом CRF для задач маркировки последовательностей. Они есть скрытые переменные модели которые обучаются разборчиво.

В LDCRF, как и в любой задаче маркировки последовательностей, задана последовательность наблюдений. Икс = ${displaystyle x_{1},dots ,x_{n}}$, основная проблема, которую должна решить модель, - как назначить последовательность меток у = ${displaystyle y_{1},dots ,y_{n}}$ из одного конечного набора этикеток Y. Вместо прямого моделирования п(у|Икс), как это сделала бы обычная линейно-цепная CRF, набор скрытых переменных час "вставлен" между Икс и у с использованием цепное правило вероятности:^[13]

${displaystyle P(mathbf {y} |mathbf {x} )=sum _{mathbf {h} }P(mathbf {y} |mathbf {h} ,mathbf {x} )P(mathbf {h} |mathbf {x} )}$

Это позволяет уловить скрытую структуру между наблюдениями и метками.^[14] Хотя LDCRF можно обучать с помощью квазиньютоновских методов, специализированная версия перцептрон алгоритм называется перцептрон со скрытой переменной был разработан для них также на основе Коллинза структурированный перцептрон алгоритм.^[13] Эти модели находят применение в компьютерное зрение, конкретно распознавание жеста из видеопотоков^[14] и неглубокий разбор.^[13]

Программного обеспечения

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

• RNNSharp CRF на основе рекуррентных нейронных сетей (C #, .СЕТЬ )
• CRF-ADF CRF с линейной цепью с быстрым онлайн-обучением ADF (C #, .СЕТЬ )
• CRFSharp Линейно-цепные CRF (C #, .СЕТЬ )
• GCO CRF с субмодульными энергетическими функциями (C ++, Matlab )
• DGM Общие CRF (C ++ )
• ГРММ Общие CRF (Ява )
• фабрика Общие CRF (Scala )
• CRFall Общие CRF (Matlab )
• CRF Сараваги Линейно-цепные CRF (Ява )
• Библиотека HCRF CRF со скрытым состоянием (C ++, Matlab )
• Accord.NET Линейно-цепные CRF, HCRF и HMMs (C #, .СЕТЬ )
• Wapiti Быстрые линейно-цепные CRF (C )^[15]
• CRFSuite Быстрые ограниченные CRF с линейной цепью (C )
• CRF ++ Линейно-цепные CRF (C ++ )
• FlexCRFs Марковские CRF первого и второго порядков (C ++ )
• crf-chain1 Линейно-цепные CRF первого порядка (Haskell )
• imageCRF CRF для сегментации изображений и объемов изображений (C ++ )
• МОЛОТОК Линейная цепочка для маркировки последовательностей (Ява )
• PyStruct Структурированное обучение на Python (Python )
• Pycrfsuite Привязка python для crfsuite (Python )
• Фигаро Вероятностный язык программирования, способный определять CRF и другие графические модели (Scala )
• CRF Инструменты моделирования и вычислений для CRF и других неориентированных графических моделей (р )
• OpenGM Библиотека для дискретных факторный график модели и распределительные операции над этими моделями (C ++ )
• UPGMpp^[5] Библиотека для построения, обучения и выполнения логического вывода с неориентированными графическими моделями (C ++ )
• KEG_CRF Быстрые линейные CRF (C ++ )

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

• МедаСи Распознаватель медицинских именованных сущностей (Python )
• Конрад Предиктор генов на основе CRF (Ява )
• Stanford NER Распознаватель именованных сущностей (Ява )
• БАННЕР Распознаватель именованных сущностей (Ява )

Смотрите также

• Теорема Хаммерсли – Клиффорда
• Графическая модель
• Марковское случайное поле
• Марковская модель максимальной энтропии (MEMM)

Рекомендации

1. Лафферти, Дж., Маккаллум, А., Перейра, Ф. (2001). «Условные случайные поля: вероятностные модели для сегментации и маркировки данных последовательности». Proc. 18-я международная конф. по машинному обучению. Морган Кауфманн. С. 282–289.
2. Sha, F .; Перейра, Ф. (2003). неглубокий анализ с условными случайными полями.
3. Settles, B. (2004). «Распознавание названных биомедицинских объектов с использованием условных случайных полей и богатых наборов функций» (PDF). Труды Международного совместного семинара по обработке естественного языка в биомедицине и ее приложениях. С. 104–107.
4. Chang KY; Лин Т-п; Ши Л-Й; Ван Си-К (2015). Анализ и прогнозирование критических областей антимикробных пептидов на основе условных случайных полей. PLoS ONE. Дои:10.1371 / journal.pone.0119490. ЧВК  4372350.
5. Дж. Р. Руис-Сармьенто; К. Галиндо; Х. Гонсалес-Хименес (2015). «UPGMpp: программная библиотека для распознавания контекстных объектов».. 3-й. Семинар по распознаванию и действию для понимания сцены (REACTS).
6. Он, X.; Zemel, R.S .; Каррейра-Перпиннан, M.A. (2004). «Мультимасштабные условные случайные поля для маркировки изображений». Компьютерное общество IEEE. CiteSeerX  10.1.1.3.7826.
7. Саттон, Чарльз; Маккаллум, Эндрю (2010). «Введение в условные случайные поля». arXiv:1011.4088v1 [stat.ML ].
8. Лавернь, Томас; Ивон, Франсуа (7 сентября 2017 г.). "Изучение структуры CRF переменного порядка: перспектива конечного состояния". Материалы конференции 2017 г. по эмпирическим методам обработки естественного языка. Копенгаген, Дания: Ассоциация компьютерной лингвистики. п. 433.
9. Хатзис, Сотириос; Демирис, Яннис (2013). "Модель условного случайного поля бесконечного порядка для последовательного моделирования данных". IEEE Transactions по анализу шаблонов и машинному анализу. 35 (6): 1523–1534. Дои:10.1109 / тпами.2012.208. HDL:10044/1/12614. PMID  23599063.
10. Gasthaus, Ян; Тех, Йи Уай (2010). «Улучшения в Sequence Memoizer» (PDF). Proc. НИПС.
11. Celeux, G .; Forbes, F .; Пейрард, Н. (2003). «EM процедуры, использующие приближения типа среднего поля для сегментации изображений на основе марковских моделей». Распознавание образов. 36 (1): 131–144. CiteSeerX  10.1.1.6.9064. Дои:10.1016 / с0031-3203 (02) 00027-4.
12. Сараваги, Сунита; Коэн, Уильям В. (2005). «Полумарковские условные случайные поля для извлечения информации» (PDF). В Лоуренс К. Саул; Яир Вайс; Леон Ботту (ред.). Достижения в системах обработки нейронной информации 17. Кембридж, Массачусетс: MIT Press. С. 1185–1192.
13. Сюй Сунь; Такуя Мацудзаки; Дайсуке Окоанохара; Дзюнъити Цудзи (2009). Алгоритм латентного перцептрона для структурированной классификации. IJCAI. С. 1236–1242.
14. Morency, L.P .; Quattoni, A .; Даррелл, Т. (2007). «Латентно-динамические дискриминационные модели для непрерывного распознавания жестов» (PDF). Конференция IEEE 2007 года по компьютерному зрению и распознаванию образов. п. 1. CiteSeerX  10.1.1.420.6836. Дои:10.1109 / CVPR.2007.383299. ISBN  978-1-4244-1179-5.
15. Т. Лаверн, О. Каппе и Ф. Ивон (2010). Практические очень крупномасштабные CRF В архиве 2013-07-18 в Wayback Machine. Proc. 48-е ежегодное собрание ACL, стр. 504-513.

дальнейшее чтение

• МакКаллум, А .: Эффективное наведение свойств условных случайных полей. В: Proc. 19-я конференция по неопределенности в искусственном интеллекте. (2003)
• Валлах, Х.М.: Условные случайные поля: введение. Технический отчет MS-CIS-04-21, Пенсильванский университет (2004 г.)
• Саттон, К., МакКаллум, А .: Введение в условные случайные поля для реляционного обучения. В «Введение в статистическое реляционное обучение». Отредактировано Лиз Гетур и Бен Таскар. MIT Press. (2006) Онлайн PDF
• Клингер, Р., Томанек, К .: Классические вероятностные модели и условные случайные поля. Отчет по разработке алгоритмов TR07-2-013, Департамент компьютерных наук, Технологический университет Дортмунда, декабрь 2007 г. ISSN 1864-4503. Онлайн PDF