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

Класс методов статистического моделирования

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

Другими примерами использования CRF являются: маркировка или анализ последовательных данных для обработки естественного языка или биологических последовательностей , ^[1] маркировка частей речи , поверхностный анализ , ^[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}$

Тогда – условное случайное поле, когда каждая случайная величина , обусловленная , подчиняется марковскому свойству относительно графика; то есть его вероятность зависит только от его соседей в G: ${\displaystyle ({\boldsymbol {X}},{\boldsymbol {Y}})}$ ${\displaystyle {\boldsymbol {Y}}_{v}}$ ${\displaystyle {\boldsymbol {X}}}$

${\displaystyle P({\boldsymbol {Y}}_{v}|{\boldsymbol {X}},\{{\boldsymbol {Y}}_{w}:w\neq v\})=P({\boldsymbol {Y}}_{v}|{\boldsymbol {X}},\{{\boldsymbol {Y}}_{w}:w\sim v\})}$, где означает, что и являются соседями в . ${\displaystyle {\mathit {w}}\sim v}$ ${\displaystyle w}$ ${\displaystyle v}$ ${\displaystyle G}$

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

Вывод

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

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

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

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

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

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

Примеры

При моделировании последовательностей интересующий граф обычно представляет собой цепной граф. Входная последовательность наблюдаемых переменных представляет собой последовательность наблюдений и представляет скрытую (или неизвестную) переменную состояния, которую необходимо вывести с учетом наблюдений. Они структурированы так, чтобы образовывать цепочку с ребром между каждым и . Помимо простой интерпретации как «меток» для каждого элемента входной последовательности, этот макет допускает эффективные алгоритмы для: ${\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}$

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

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

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

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

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

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

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

${\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]

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

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

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

1. Лафферти, Дж.; МакКаллум, А.; Перейра, Ф. (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. 
5. Дж. Р. Руис-Сармьенто; К. Галиндо; Х. Гонсалес-Хименес (2015). «UPGMpp: библиотека программного обеспечения для контекстного распознавания объектов». 3-й. Семинар по распознаванию и действиям для понимания сцены (РЕАКТС) .
6. Он, X .; Земель, РС; Каррейра-Перпиньян, Массачусетс (2004). «Многомасштабные условные случайные поля для маркировки изображений». Компьютерное общество IEEE. CiteSeerX 10.1.1.3.7826 . 
7. Саттон, Чарльз; МакКаллум, Эндрю (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 . PMID  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 г.
13. Сюй Сунь; Такуя Мацузаки; Дайсуке Оканохара; Дзюнъити Цудзи (2009). Алгоритм перцептрона со скрытой переменной для структурированной классификации. IJCAI. стр. 1236–1242. Архивировано из оригинала 6 декабря 2018 г. Проверено 6 декабря 2018 г.
14. Моренси, 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