Условное случайное поле

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

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

Описание

CRF — это тип дискриминационной ненаправленной вероятностной графической модели .

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

Позволять $G=(V,E)$ быть графом таким, что ${\boldsymbol {Y}}=({\boldsymbol {Y}}_{v})_{v\in V}$ , так что ${\boldsymbol {Y}}$ индексируется вершинами $G$ .
Затем $({\boldsymbol {X}},{\boldsymbol {Y}})$ – условное случайное поле, когда каждая случайная величина ${\boldsymbol {Y}}_{v}$ , обусловленный ${\boldsymbol {X}}$ , подчиняется марковскому свойству относительно графа; то есть его вероятность зависит только от его соседей в G:
$P({\boldsymbol {Y}}_{v}|{\boldsymbol {X}},\{{\boldsymbol {Y}}_{w}:w\neq v\})=P({\boldsymbol {Y}}_{v}|{\boldsymbol {X}},\{{\boldsymbol {Y}}_{w}:w\sim v\})$ , где ${\mathit {w}}\sim v$ означает что $w$ и $v$ являются соседями по $G$ .

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

Вывод

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

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

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

Изучение параметров

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

Примеры

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

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

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

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

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

Варианты

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

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

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

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

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

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

Скрытые динамические условные случайные поля ( LDCRF ) или дискриминативные вероятностные модели скрытых переменных ( DPLVM ) представляют собой тип CRF для задач маркировки последовательностей. Это модели со скрытыми переменными , которые обучаются дискриминативно.

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

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 ]}

См. также

Ссылки

^ Jump up to: ^а ^б Лафферти, Дж.; МакКаллум, А.; Перейра, Ф. (2001). «Условные случайные поля: вероятностные модели для сегментации и маркировки данных последовательности» . Учеб. 18-я Международная конференция. по машинному обучению . Морган Кауфманн. стр. 282–289.
^ Ша, Ф.; Перейра, Ф. (2003). неглубокий парсинг с условными случайными полями .
^ Сетлс, Б. (2004). «Распознавание биомедицинских именованных объектов с использованием условных случайных полей и богатых наборов функций» (PDF) . Материалы международного совместного семинара по обработке естественного языка в биомедицине и ее приложениям . стр. 104–107.
^ Чанг К.Ю.; Лин Тп; Ши ЛИ; Ван СК (2015). «Анализ и прогнозирование критических областей антимикробных пептидов на основе условных случайных полей» . ПЛОС ОДИН . 10 (3): e0119490. Бибкод : 2015PLoSO..1019490C . дои : 10.1371/journal.pone.0119490 . ПМЦ 4372350 . ПМИД 25803302 .
^ Х.Р. Руис-Сармьенто; К. Галиндо; Х. Гонсалес-Хименес (2015). «UPGMpp: библиотека программного обеспечения для контекстного распознавания объектов». . 3-й. Семинар по распознаванию и действиям для понимания сцены (РЕАКТЫ) .
^ Он, Х .; Земель, РС; Каррейра-Перпиньян, Массачусетс (2004). «Многомасштабные условные случайные поля для маркировки изображений». Компьютерное общество IEEE. CiteSeerX 10.1.1.3.7826 .
^ Jump up to: ^а ^б Саттон, Чарльз; МакКаллум, Эндрю (2010). «Введение в условные случайные поля». arXiv : 1011.4088v1 [ stat.ML ].
^ Лавернь, Томас; Ивон, Франсуа (7 сентября 2017 г.). «Изучение структуры CRF переменного порядка: перспектива конечного состояния» . Материалы конференции 2017 года по эмпирическим методам обработки естественного языка . Копенгаген, Дания: Ассоциация компьютерной лингвистики. п. 433.
^ Хацис, Сотириос; Демирис, Яннис (2013). «Модель условного случайного поля бесконечного порядка для последовательного моделирования данных». Транзакции IEEE по анализу шаблонов и машинному интеллекту . 35 (6): 1523–1534. дои : 10.1109/tpami.2012.208 . hdl : 10044/1/12614 . ПМИД 23599063 . S2CID 690627 .
^ Гастхаус, Ян; Да, Йи Почему (2010). «Усовершенствования в мемоайзере последовательностей» (PDF) . Учеб. НИПС .
^ Селё, Г.; Форбс, Ф.; Пейрар, Н. (2003). «ЭМ-процедуры, использующие аппроксимации среднего поля для сегментации изображений на основе марковской модели». Распознавание образов . 36 (1): 131–144. Бибкод : 2003PatRe..36..131C . CiteSeerX 10.1.1.6.9064 . дои : 10.1016/s0031-3203(02)00027-4 .
^ Сараваги, Сунита ; Коэн, Уильям В. (2005). «Полумарковские условные случайные поля для извлечения информации» . У Лоуренса К. Сола; Яир Вайс; Леон Ботту (ред.). Достижения в области нейронных систем обработки информации 17 . Кембридж, Массачусетс: MIT Press. стр. 1185–1192. Архивировано из оригинала (PDF) 30 ноября 2019 г. Проверено 12 ноября 2015 г.
^ Jump up to: ^а ^б ^с Сюй Сунь; Такуя Мацузаки; Дайсуке Оканохара; Дзюнъити Цудзи (2009). Алгоритм перцептрона со скрытой переменной для структурированной классификации . IJCAI. стр. 1236–1242. Архивировано из оригинала 6 декабря 2018 г. Проверено 6 декабря 2018 г.
^ Jump up to: ^а ^б Моренси, LP; Кваттони, А.; Даррелл, Т. (2007). «Скрыто-динамические дискриминационные модели для непрерывного распознавания жестов» (PDF) . Конференция IEEE 2007 г. по компьютерному зрению и распознаванию образов . п. 1. CiteSeerX 10.1.1.420.6836 . дои : 10.1109/CVPR.2007.383299 . ISBN 978-1-4244-1179-5 . S2CID 7117722 .

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

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

[Laf:McC:Per01-1] Jump up to: ^а ^б Лафферти, Дж.; МакКаллум, А.; Перейра, Ф. (2001). «Условные случайные поля: вероятностные модели для сегментации и маркировки данных последовательности» . Учеб. 18-я Международная конференция. по машинному обучению . Морган Кауфманн. стр. 282–289.

[2] Ша, Ф.; Перейра, Ф. (2003). неглубокий парсинг с условными случайными полями .

[3] Сетлс, Б. (2004). «Распознавание биомедицинских именованных объектов с использованием условных случайных полей и богатых наборов функций» (PDF) . Материалы международного совместного семинара по обработке естественного языка в биомедицине и ее приложениям . стр. 104–107.

[4] Чанг К.Ю.; Лин Тп; Ши ЛИ; Ван СК (2015). «Анализ и прогнозирование критических областей антимикробных пептидов на основе условных случайных полей» . ПЛОС ОДИН . 10 (3): e0119490. Бибкод : 2015PLoSO..1019490C . дои : 10.1371/journal.pone.0119490 . ПМЦ 4372350 . ПМИД 25803302 .

[Rui:Gal:Gon15-5] Х.Р. Руис-Сармьенто; К. Галиндо; Х. Гонсалес-Хименес (2015). «UPGMpp: библиотека программного обеспечения для контекстного распознавания объектов». . 3-й. Семинар по распознаванию и действиям для понимания сцены (РЕАКТЫ) .

[6] Он, Х .; Земель, РС; Каррейра-Перпиньян, Массачусетс (2004). «Многомасштабные условные случайные поля для маркировки изображений». Компьютерное общество IEEE. CiteSeerX 10.1.1.3.7826 .

[SuttonIntroduction-7] Jump up to: ^а ^б Саттон, Чарльз; МакКаллум, Эндрю (2010). «Введение в условные случайные поля». arXiv : 1011.4088v1 [ stat.ML ].

[8] Лавернь, Томас; Ивон, Франсуа (7 сентября 2017 г.). «Изучение структуры CRF переменного порядка: перспектива конечного состояния» . Материалы конференции 2017 года по эмпирическим методам обработки естественного языка . Копенгаген, Дания: Ассоциация компьютерной лингвистики. п. 433.

[9] Хацис, Сотириос; Демирис, Яннис (2013). «Модель условного случайного поля бесконечного порядка для последовательного моделирования данных». Транзакции IEEE по анализу шаблонов и машинному интеллекту . 35 (6): 1523–1534. дои : 10.1109/tpami.2012.208 . hdl : 10044/1/12614 . ПМИД 23599063 . S2CID 690627 .

[10] Гастхаус, Ян; Да, Йи Почему (2010). «Усовершенствования в мемоайзере последовательностей» (PDF) . Учеб. НИПС .

[11] Селё, Г.; Форбс, Ф.; Пейрар, Н. (2003). «ЭМ-процедуры, использующие аппроксимации среднего поля для сегментации изображений на основе марковской модели». Распознавание образов . 36 (1): 131–144. Бибкод : 2003PatRe..36..131C . CiteSeerX 10.1.1.6.9064 . дои : 10.1016/s0031-3203(02)00027-4 .

[12] Сараваги, Сунита ; Коэн, Уильям В. (2005). «Полумарковские условные случайные поля для извлечения информации» . У Лоуренса К. Сола; Яир Вайс; Леон Ботту (ред.). Достижения в области нейронных систем обработки информации 17 . Кембридж, Массачусетс: MIT Press. стр. 1185–1192. Архивировано из оригинала (PDF) 30 ноября 2019 г. Проверено 12 ноября 2015 г.

[lvperceptron-13] Jump up to: ^а ^б ^с Сюй Сунь; Такуя Мацузаки; Дайсуке Оканохара; Дзюнъити Цудзи (2009). Алгоритм перцептрона со скрытой переменной для структурированной классификации . IJCAI. стр. 1236–1242. Архивировано из оригинала 6 декабря 2018 г. Проверено 6 декабря 2018 г.

[morency-14] Jump up to: ^а ^б Моренси, LP; Кваттони, А.; Даррелл, Т. (2007). «Скрыто-динамические дискриминационные модели для непрерывного распознавания жестов» (PDF) . Конференция IEEE 2007 г. по компьютерному зрению и распознаванию образов . п. 1. CiteSeerX 10.1.1.420.6836 . дои : 10.1109/CVPR.2007.383299 . ISBN 978-1-4244-1179-5 . S2CID 7117722 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]