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

Эта статья поднимает множество проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалить эти сообщения-шаблоны )

Эта статья предоставляет недостаточный контекст для тех, кто не знаком с предметом . Пожалуйста, помогите улучшить статью , предоставив читателю больше контекста . ( Январь 2013 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

Эта статья может быть слишком технической для понимания большинства читателей . Пожалуйста, помогите улучшить его, чтобы он был понятен неспециалистам , не удаляя технических деталей. ( Июнь 2012 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

( Узнайте, как и когда удалить этот шаблон сообщения )

Машинное обучение и интеллектуальный анализ данных
Часть серии по

Проблемы Классификация Кластеризация Регресс Обнаружение аномалий AutoML Правила ассоциации Обучение с подкреплением Структурированный прогноз Разработка функций Особенности обучения Онлайн обучение Полу-контролируемое обучение Обучение без учителя Учимся ранжировать Введение в грамматику
Обучение с учителем ( классификация • регрессия ) Деревья решений Ансамбли Упаковка Повышение Случайный лес k -NN Линейная регрессия Наивный байесовский Искусственные нейронные сети Логистическая регрессия Перцептрон Вектор релевантности (RVM) Машина опорных векторов (SVM)
Кластеризация БЕРЕЗА ИЗЛЕЧИВАТЬ Иерархический k- означает Ожидание – максимизация (EM) DBSCAN ОПТИКА Средний сдвиг
Снижение размерности Факторный анализ CCA ICA LDA NMF PCA PGD t-SNE
Структурированный прогноз Графические модели Сеть Байеса Условное случайное поле Скрытый Марков
Обнаружение аномалий k -NN Фактор локального выброса
Искусственная нейронная сеть Автоэнкодер Когнитивные вычисления Глубокое обучение DeepDream Многослойный перцептрон RNN LSTM ГРУ ESN Ограниченная машина Больцмана GAN SOM Сверточная нейронная сеть U-Net Трансформатор Пиковая нейронная сеть Мемтранзистор Электрохимическая RAM (ECRAM)
Обучение с подкреплением Q-обучение SARSA Временная разница (TD)
Теория Компромисс смещения и дисперсии Теория вычислительного обучения Минимизация эмпирического риска Обучение Оккама PAC обучение Статистическое обучение Теория ВК
Площадки для машинного обучения NeurIPS ICML ML JMLR ArXiv: cs.LG
Глоссарий искусственного интеллекта Глоссарий искусственного интеллекта
Статьи по Теме Список наборов данных для исследований в области машинного обучения Схема машинного обучения
v т е

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

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

Описание [ править ]

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

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

Позвольте быть граф, такой что ${\ Displaystyle G = (V, E)}$
${\ displaystyle {\ boldsymbol {Y}} = ({\ boldsymbol {Y}} _ {v}) _ {v \ in V}}$ , так что индексируется вершинами . Тогда является условным случайным полем, когда случайные величины , обусловленные условием , подчиняются свойству Маркова по отношению к графу:, где означает, что и являются соседями в . ${\ displaystyle {\ boldsymbol {Y}}}$ ${\ displaystyle G}$ ${\ displaystyle ({\ boldsymbol {X}}, {\ boldsymbol {Y}})}$ ${\ displaystyle {\ boldsymbol {Y}} _ {v}}$ ${\ displaystyle {\ boldsymbol {X}}}$ $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 содержит только парные потенциалы, а энергия является субмодульной , комбинаторные алгоритмы минимального отсечения / максимального расхода дают точные решения.

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

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

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

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

Примеры [ править ]

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

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

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

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

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

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

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

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.

CRF RNNSharp на основе рекуррентных нейронных сетей ( C # , .NET )
CRF-ADF CRF с линейной цепочкой и быстрым онлайн-обучением ADF ( C # , .NET )
CRFSharp CRF с линейной цепочкой ( C # , .NET )
GCO CRF с субмодульными энергетическими функциями ( C ++ , Matlab )
Общие CRF DGM ( C ++ )
GRMM Общие CRF ( Java )
фабрика General CRFs ( Scala )
CRFall Общие CRF ( Matlab )
CRF Сараваги CRF с линейной цепью ( Java )
Библиотека HCRF CRF со скрытым состоянием ( C ++ , Matlab )
Accord.NET CRF, HCRF и HMM с линейной цепочкой ( C # , .NET )
Линейно-цепные CRF Wapiti Fast ( C ) ^[15]
CRFSuite Быстрые ограниченные линейно-цепные CRF ( C )
CRF ++ CRF с линейной цепью ( C ++ )
FlexCRF Марковские CRF первого и второго порядка ( C ++ )
crf-chain1 CRF первого порядка с линейной цепочкой ( Haskell )
imageCRF CRF для сегментации изображений и объемов изображений ( C ++ )
МОЛЛЕТ Линейная цепочка для маркировки последовательностей ( Java )
Структурированное обучение PyStruct на Python ( Python )
Pycrfsuite Связывание Python для crfsuite ( Python )
Figaro Вероятностный язык программирования, способный определять CRF и другие графические модели ( Scala )
CRF Моделирование и вычислительные инструменты для CRF и других неориентированных графических моделей ( R )
Библиотека OpenGM для моделей дискретных факторных графов и распределительных операций над этими моделями ( C ++ )
UPGMpp ^[5] Библиотека для построения, обучения и выполнения логического вывода с помощью неориентированных графических моделей ( C ++ )
KEG_CRF Быстрые линейные CRF ( C ++ )

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

MedaCy Medical Named Entity Recognizer ( Python )
Предиктор генов на основе CRF Конрада ( Java )
Stanford NER Named Entity Recognizer ( Java )
Распознаватель именованных объектов BANNER ( Java )

См. Также [ править ]

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

Ссылки [ править ]

^ a b Лафферти, Дж., МакКаллум, А., Перейра, Ф. (2001). «Условные случайные поля: вероятностные модели для сегментации и маркировки данных последовательности» . Proc. 18-я международная конф. по машинному обучению . Морган Кауфманн. С. 282–289.CS1 maint: uses authors parameter (link)
^ Sha, F .; Перейра, Ф. (2003). неглубокий парсинг с условными случайными полями .
^ Оседает, B. (2004). «Распознавание биомедицинских названных сущностей с использованием условных случайных полей и богатого набора функций» (PDF) . Труды международного совместного семинара по обработке естественного языка в биомедицине и ее приложениях . С. 104–107.
^ Чанг KY; Lin Tp; Shih LY; Ван СК (2015). Анализ и прогнозирование критических областей антимикробных пептидов на основе условных случайных полей . PLoS ONE. DOI : 10.1371 / journal.pone.0119490 . PMC 4372350 .
^ а б Дж. Р. Руис-Сармьенто; К. Галиндо; Х. Гонсалес-Хименес (2015). «UPGMpp: программная библиотека для распознавания контекстных объектов». . 3-й. Семинар по распознаванию и действию для понимания сцены (REACTS) .
^ Он, X .; Zemel, RS; Каррейра-Перпиннан, Массачусетс (2004). «Мультимасштабные условные случайные поля для маркировки изображений». Компьютерное общество IEEE. CiteSeerX 10.1.1.3.7826 .
^ a b Саттон, Чарльз; Маккаллум, Эндрю (2010). «Введение в условные случайные поля». arXiv : 1011.4088v1 [ stat.ML ].
^ Лавернь, Томас; Ивон, Франсуа (7 сентября 2017 г.). «Изучение структуры с переменной-Order ИРК: а конечно-Perspective» . Труды конференции по 2017 г. Эмпирические методы в задачах обработки естественного языка . Копенгаген, Дания: Ассоциация компьютерной лингвистики. п. 433.
^ Хатзис, Сотириос; Демирис, Яннис (2013). "Модель условного случайного поля бесконечного порядка для последовательного моделирования данных". IEEE Transactions по анализу шаблонов и машинному анализу . 35 (6): 1523–1534. DOI : 10.1109 / tpami.2012.208 . hdl : 10044/1/12614 . PMID 23599063 .
^ Gasthaus, Ян; Тех, Йи Уай (2010). «Улучшения Sequence Memoizer» (PDF) . Proc. НИПС .
^ Celeux, G .; Forbes, F .; Пейрард, Н. (2003). «EM процедуры, использующие приближения типа среднего поля для сегментации изображений на основе марковских моделей». Распознавание образов . 36 (1): 131–144. CiteSeerX 10.1.1.6.9064 . DOI : 10.1016 / s0031-3203 (02) 00027-4 .
^ Сараваги, Сунита; Коэн, Уильям В. (2005). «Полумарковские условные случайные поля для извлечения информации» (PDF) . В Лоуренсе К. Сауле; Яир Вайс; Леон Ботту (ред.). Достижения в системах обработки нейронной информации 17 . Кембридж, Массачусетс: MIT Press. С. 1185–1192.
^ a b c Сюй Сунь; Такуя Мацудзаки; Дайсуке Окоанохара; Дзюнъити Цудзи (2009). Алгоритм латентного перцептрона для структурированной классификации . IJCAI. С. 1236–1242.
^ a b Моренси, LP; Quattoni, A .; Даррелл, Т. (2007). «Латентно-динамические дискриминационные модели для распознавания непрерывных жестов» (PDF) . Конференция IEEE 2007 года по компьютерному зрению и распознаванию образов . п. 1. CiteSeerX 10.1.1.420.6836 . DOI : 10,1109 / CVPR.2007.383299 . ISBN 978-1-4244-1179-5.
^ Т. Лавернь, О. Cappe и Ф. Ивон (2010). Практические очень крупномасштабные CRF, заархивированные 18 июля 2013 г. в Wayback Machine . Proc. 48-е ежегодное собрание ACL , стр. 504-513.

Дальнейшее чтение [ править ]

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

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

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

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

[4] Чанг KY; Lin Tp; Shih LY; Ван СК (2015). Анализ и прогнозирование критических областей антимикробных пептидов на основе условных случайных полей . PLoS ONE. DOI : 10.1371 / journal.pone.0119490 . PMC 4372350 .

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

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

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

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

[9] Хатзис, Сотириос; Демирис, Яннис (2013). "Модель условного случайного поля бесконечного порядка для последовательного моделирования данных". IEEE Transactions по анализу шаблонов и машинному анализу . 35 (6): 1523–1534. DOI : 10.1109 / tpami.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 . DOI : 10.1016 / s0031-3203 (02) 00027-4 .

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

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

[morency-14] Моренси, LP; Quattoni, A .; Даррелл, Т. (2007). «Латентно-динамические дискриминационные модели для распознавания непрерывных жестов» (PDF) . Конференция IEEE 2007 года по компьютерному зрению и распознаванию образов . п. 1. CiteSeerX 10.1.1.420.6836 . DOI : 10,1109 / CVPR.2007.383299 . ISBN 978-1-4244-1179-5.

[15] Т. Лавернь, О. Cappe и Ф. Ивон (2010). Практические очень крупномасштабные CRF, заархивированные 18 июля 2013 г. в Wayback Machine . Proc. 48-е ежегодное собрание ACL , стр. 504-513.