Умовне випадкове поле

Умо́вні випадко́ві поля́ (УВП, англ. conditional random fields, CRFs) — це клас методів статистичного моделювання, які часто застосовують в розпізнаванні образів та машинному навчанні, й використовують для структурового передбачування. УВП належать до родини моделювання послідовностей. На відміну від дискретного класифікатора, який передбачує мітку для окремого зразка без врахування «сусідніх» зразків, УВП може брати до уваги контекст; наприклад, лінійно-ланцюгове УВП (що є популярним в обробці природної мови) передбачує послідовності міток для послідовностей входових зразків.

УВП є одним з типів розрізнювальних неспрямованих імовірнісних графових моделей. Їх використовують для кодування відомих взаємозв'язків між спостереженнями та побудови узгоджених представлень, і часто використовують для розмічування^[en] або розбирання послідовних даних, таких як обробка природних мов та біологічні послідовності,^[1] та в комп'ютерному баченні.^[2] Зокрема, УВП, серед інших задач, знаходять застосування в розмічуванні частин мови, поверхнево-синтаксичному аналізі,^[3] розпізнаванні іменованих сутностей,^[4] пошуку генів^[en] та пошуку пептидних критичних функційних областей,^[5] будучи альтернативою спорідненим прихованим марковським моделям (ПММ). У комп'ютерному зорі УВП часто використовують для розпізнавання об'єктів^[6] та сегментування зображень.

Опис ред.

Лафферті^[en], Маккалум^[en] та Перейра^[1] визначили УВП на спостереженнях ${\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}}$ , володіють марковською властивістю по відношенню до цього графу: $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$ .

Це означає, що УВП є неспрямованою графовою моделлю, чиї вершини може бути поділено на рівно дві неперетинні множини ${\boldsymbol {X}}$ та ${\boldsymbol {Y}}$ , спостережувані та виходові змінні, відповідно; тоді моделюють умовний розподіл $p({\boldsymbol {Y}}|{\boldsymbol {X}})$ .

Висновування ред.

Для графів загального вигляду задача точного висновування в УВП є нерозв'язною. Задача висновування для УВП є по суті такою ж, як і для МВП^[en], і мають місце ті самі аргументи.^[7] Проте, існують особливі випадки, для яких висновування є здійсненним:

Якщо граф є ланцюгом або деревом, то точні розв'язки дають алгоритми передавання повідомлень. Алгоритми, що застосовують в цих випадках, є аналогічними до послідовно-зворотного алгоритму^[en] та алгоритму Вітербі для випадку ПММ.
Якщо УВП містить лише попарні потенціали, й ця енергія є субмодулярною^[en], то точні розв'язки дають комбінаторні алгоритми мінімального розрізу/максимального потоку.

Якщо точне висновування є неможливим, то можливо застосовувати декілька алгоритмів для отримування наближених розв'язків. До них належать:

Петлясте поширення переконання^[en]
Альфа-розширення (англ. alpha expansion)
Висновування середнього поля (англ. mean field inference)
Лінійне програмування з послабленням^[en]

Навчання параметрів ред.

Навчання параметрів $\theta$ зазвичай виконують навчанням максимальної правдоподібності для $p(Y_{i}|X_{i};\theta )$ . Якщо всі вузли мають розподіли експоненційного сімейства, та є спостережуваними під час тренування, то ця оптимізація є опуклою.^[7] Її можливо розв'язувати, наприклад, застосуванням алгоритмів градієнтного спуску, або квазі-ньютоновими методами, такими як алгоритм L-BFGS^[en]. З іншого боку, якщо деякі змінні є неспостережуваними, то для цих змінних має бути розв'язано задачу висновування. Для графів загального вигляду точне висновування є непіддатливим, тож мають застосовуватися наближення.

Приклади ред.

У послідовнісному моделюванні, граф, який становить інтерес, зазвичай є ланцюговим. Входова послідовність спостережуваних змінних $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}$ .

Лінійно-ланцюгові УВП мають багато таких же застосувань, як і концептуально простіші приховані марковські моделі (ПММ), але послаблюють деякі вихідні положення щодо розподілів послідовностей входу та виходу. ПММ можливо грубо розуміти як УВП з дуже особливими функціями ознак, які використовують сталі ймовірності для моделюванні переходів станів та виходів. І навпаки, УВП можливо грубо розуміти як узагальнення ПММ, яке робить сталі ймовірності переходів довільними функціями, що міняться над позиціями в послідовності прихованих станів, залежно від послідовності входу.

Примітно, що, на противагу до ПММ, УВП можуть містити будь-яке число функцій ознак, ці функції ознак можуть оглядати всю послідовність входу $X$ в будь-який момент висновування, і спектрові функцій ознак не потрібно мати ймовірнісної інтерпретації.

Варіанти ред.

УВП вищих порядків, та напівмарковські УВП ред.

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

Проте, іншому нещодавньому просуванню вдалося поліпшити ці нюанси шляхом задіювання понять та інструментів з області баєсової непараметрії. Конкретніше, УВП-нескінченний (англ. CRF-infinity) підхід^[9] становить УВП-модель, здатну навчатися нескінченно тривалої часової динаміки масштабованою манерою. Це здійснюється введенням новітньої функції потенціалу для УВП, яка ґрунтується на «запам'ятовувачі послідовностей» (ЗП, англ. Sequence Memoizer, SM), непараметричній баєсовій моделі для навчання нескінченно тривалих динамік у послідовних спостереженнях.^[10] Щоби зробити таку модель обчислювально піддатливою, УВП-нескінченність застосовує наближення середнього поля^[11] запостульованих новітніх функцій потенціалу (які веде ЗП). Це дозволяє винаходити дієві алгоритми наближеного тренування та висновування для цієї моделі, не підриваючи її здатності схоплювати та моделювати часові залежності довільної тривалості.

Існує ще одне узагальнення УВП, напівма́рковське умо́вне випадко́ве по́ле (напів-УВП, англ. semi-Markov conditional random field, semi-CRF), яке моделює сегментування довільної довжини послідовності міток $Y$ .^[12] Воно забезпечує майже таку ж потужність для моделювання довготривалих залежностей $Y_{i}$ , як і УВП вищих порядків, за помірних обчислювальних витрат.

Нарешті, як альтернативу процедурі тренування УВП можливо розглядати моделі з широким розділенням (англ. large-margin models) для структурового передбачування, такі як структурові опорно-векторні машини^[en].

Латентно-динамічне умовне випадкове поле ред.

Лате́нтно-динамі́чні умо́вні випадко́ві по́ля (ЛДУВП, англ. latent-dynamic conditional random fields, LDCRF), або розрі́знювальні імові́рнісні моде́лі з лате́нтними змі́нними (РІМЛЗ, англ. discriminative probabilistic latent variable models, DPLVM) — це один із типів УВП для задач маркування послідовностей. Вони є моделями з латентними змінними^[en], що тренують розрізнювально.

В ЛДУВП, як і в будь-якій задачі маркування послідовностей, для заданої послідовності спостережень x = $x_{1},\dots ,x_{n}$ головною задачею, яку ця модель мусить розв'язати, є як призначити послідовність міток y = $y_{1},\dots ,y_{n}$ з однієї скінченної множини міток $Y$ . Замість моделювати $P$ (y|x) безпосередньо, як робило би звичайне лінійно-ланцюгове УВП, між x та y «вставляють» множину латентних змінних h, застосовуючи ланцюгове правило ймовірності:^[13]

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

Це дозволяє схоплювати латентну структуру між спостереженнями та мітками.^[14] В той час як ЛДУВП може бути треновано з використанням квазі-ньютонових методів, для них на основі алгоритму структурового перцептрону Коллінза також було розроблено особливу версію алгоритму перцептрону, названу перцептро́ном з лате́нтними змі́нними (англ. latent-variable perceptron).^[13] Ці моделі знаходять застосування в комп'ютерному баченні, зокрема в розпізнаванні жестів^[en] для потоків відео,^[14] та в поверхнево-синтаксичному аналізі.^[13]

Програмне забезпечення ред.

Це — частковий перелік програмного забезпечення, що втілює загальні інструменти УВП.

RNNSharp УВП на основі рекурентних нейронних мереж (C#, .NET)
CRF-ADF лінійно-ланцюгові УВП зі швидким інтерактивним ADF-тренуванням (C#, .NET)
CRFSharp лінійно-ланцюгові УВП (C#, .NET)
GCO УВП з субмодулярними функціями енергії (C++, Matlab)
DGM загальні УВП (C++)
GRMM загальні УВП (Java)
factorie загальні УВП (Scala)
CRFall загальні УВП (Matlab)
Sarawagi's CRF лінійно-ланцюгові УВП (Java)
HCRF library приховано-станові УВП (C++, Matlab)
Accord.NET лінійно-ланцюгові УВП, ПУВП та ПММ (C#, .NET)
Wapiti швидкі лінійно-ланцюгові УВП (C)^[15]
CRFSuite швидкі обмежені лінійно-ланцюгові УВП (C)
CRF++ лінійно-ланцюгові УВП (C++)
FlexCRFs марковські УВП першого та другого порядків (C++)
crf-chain1 лінійно-ланцюгові УВП першого порядку (Haskell)
imageCRF УВП для сегментування зображень та томів зображень (C++)
MALLET лінійно-ланцюгові для маркування послідовностей (Java)
PyStruct структурове навчання в Python (Python)
Pycrfsuite python-обв'язка для crfsuite (Python)
Figaro ймовірнісна мова програмування, здатна визначати УВП та інші графові моделі (Scala)
CRF моделювальні та обчислювальні інструменти для УВП та інших неспрямованих графових моделей (R)
OpenGM бібліотека для дискретних розкладово-графових^[en] моделей та розподілених операцій на цих моделях (C++)
UPGMpp^[6] бібліотека для побудови, тренування неспрямованих графових моделей, та виконання висновування на них (C++)
KEG_CRF швидкі лінійні УВП (C++)

Це — частковий перелік програмного забезпечення, що втілює пов'язані з УВП інструменти.

MedaCy розпізнавач медичних іменованих сутностей (Python)
Conrad передбачувач генів на основі УВП (Java)
Stanford NER розпізнавач іменованих сутностей (Java)
BANNER розпізнавач іменованих сутностей (Java)

Див. також ред.

Примітки ред.

↑ ^а ^б Lafferty, J., McCallum, A., Pereira, F. (2001). Conditional random fields: Probabilistic models for segmenting and labeling sequence data. Proc. 18th International Conf. on Machine Learning. Morgan Kaufmann. с. 282—289. (англ.)
↑ He, X.; Zemel, R.S.; Carreira-Perpinñán, M.A. (2004). Multiscale conditional random fields for image labeling. IEEE Computer Society. CiteSeerX 10.1.1.3.7826. (англ.)
↑ Sha, F.; Pereira, F. (2003). shallow parsing with conditional random fields. (англ.)
↑ Settles, B. (2004). Biomedical named entity recognition using conditional random fields and rich feature sets (PDF). Proceedings of the International Joint Workshop on Natural Language Processing in Biomedicine and its Applications. с. 104—107. (англ.)
↑ Chang KY; Lin T-p; Shih L-Y; Wang C-K (2015). Analysis and Prediction of the Critical Regions of Antimicrobial Peptides Based on Conditional Random Fields. PLoS ONE. doi:10.1371/journal.pone.0119490. PMC 4372350.{{cite conference}}: Обслуговування CS1: Сторінки із непозначеним DOI з безкоштовним доступом (посилання) (англ.)
↑ ^а ^б J.R. Ruiz-Sarmiento; C. Galindo; J. Gonzalez-Jimenez (2015). UPGMpp: a Software Library for Contextual Object Recognition.. 3rd. Workshop on Recognition and Action for Scene Understanding (REACTS). (англ.)
↑ ^а ^б Sutton, Charles; McCallum, Andrew (2010). «An Introduction to Conditional Random Fields». arXiv:1011.4088v1 [stat.ML]. (англ.)
↑ Lavergne, Thomas; Yvon, François (7 вересня 2017). Learning the Structure of Variable-Order CRFs: a Finite-State Perspective. Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing. Copenhagen, Denmark: Association for Computational Linguistics. с. 433. (англ.)
↑ Chatzis, Sotirios; Demiris, Yiannis (2013). The Infinite-Order Conditional Random Field Model for Sequential Data Modeling. IEEE Transactions on Pattern Analysis and Machine Intelligence. 35 (6): 1523—1534. doi:10.1109/tpami.2012.208. PMID 23599063. (англ.)
↑ Gasthaus, Jan; Teh, Yee Whye (2010). Improvements to the Sequence Memoizer (PDF). Proc. NIPS. (англ.)
↑ Celeux, G.; Forbes, F.; Peyrard, N. (2003). EM Procedures Using Mean Field-Like Approximations for Markov Model-Based Image Segmentation. Pattern Recognition. 36 (1): 131—144. CiteSeerX 10.1.1.6.9064. doi:10.1016/s0031-3203(02)00027-4. (англ.)
↑ Sarawagi, Sunita; Cohen, William W. (2005). Semi-Markov conditional random fields for information extraction. У Lawrence K. Saul, Yair Weiss, Léon Bottou (eds.) (ред.). Advances in Neural Information Processing Systems 17. Cambridge, MA: MIT Press. с. 1185—1192. Архів оригіналу (PDF) за 30 листопада 2019. Процитовано 30 листопада 2019. (англ.)
↑ ^а ^б ^в Xu Sun; Takuya Matsuzaki; Daisuke Okanohara; Jun'ichi Tsujii (2009). Latent Variable Perceptron Algorithm for Structured Classification. IJCAI. с. 1236—1242. Архів оригіналу за 6 грудня 2018. Процитовано 30 листопада 2019. (англ.)
↑ ^а ^б Morency, L. P.; Quattoni, A.; Darrell, T. (2007). Latent-Dynamic Discriminative Models for Continuous Gesture Recognition (PDF). 2007 IEEE Conference on Computer Vision and Pattern Recognition. с. 1. CiteSeerX 10.1.1.420.6836. doi:10.1109/CVPR.2007.383299. ISBN 978-1-4244-1179-5. (англ.)
↑ T. Lavergne, O. Cappé and F. Yvon (2010). Practical very large scale CRFs [Архівовано 2013-07-18 у Wayback Machine.]. Proc. 48th Annual Meeting of the ACL^[en], pp. 504—513. (англ.)

Література ред.

McCallum, A.: Efficiently inducing features of conditional random fields. In: Proc. 19th Conference on Uncertainty in Artificial Intelligence. (2003) (англ.)
Wallach, H.M.: Conditional random fields: An introduction. Technical report MS-CIS-04-21, University of Pennsylvania (2004) (англ.)
Sutton, C., McCallum, A.: An Introduction to Conditional Random Fields for Relational Learning. In «Introduction to Statistical Relational Learning». Edited by Lise Getoor^[en] and Ben Taskar. MIT Press. (2006) Online PDF (англ.)
Klinger, R., Tomanek, K.: Classical Probabilistic Models and Conditional Random Fields. Algorithm Engineering Report TR07-2-013, Department of Computer Science, Dortmund University of Technology, December 2007. ISSN 1864-4503. Online PDF (англ.)

[Laf:McC:Per01-1] а ^б Lafferty, J., McCallum, A., Pereira, F. (2001). Conditional random fields: Probabilistic models for segmenting and labeling sequence data. Proc. 18th International Conf. on Machine Learning. Morgan Kaufmann. с. 282—289. (англ.)

[2] He, X.; Zemel, R.S.; Carreira-Perpinñán, M.A. (2004). Multiscale conditional random fields for image labeling. IEEE Computer Society. CiteSeerX 10.1.1.3.7826. (англ.)

[3] Sha, F.; Pereira, F. (2003). shallow parsing with conditional random fields. (англ.)

[4] Settles, B. (2004). Biomedical named entity recognition using conditional random fields and rich feature sets (PDF). Proceedings of the International Joint Workshop on Natural Language Processing in Biomedicine and its Applications. с. 104—107. (англ.)

[5] Chang KY; Lin T-p; Shih L-Y; Wang C-K (2015). Analysis and Prediction of the Critical Regions of Antimicrobial Peptides Based on Conditional Random Fields. PLoS ONE. doi:10.1371/journal.pone.0119490. PMC 4372350.{{cite conference}}: Обслуговування CS1: Сторінки із непозначеним DOI з безкоштовним доступом (посилання) (англ.)

[Rui:Gal:Gon15-6] а ^б J.R. Ruiz-Sarmiento; C. Galindo; J. Gonzalez-Jimenez (2015). UPGMpp: a Software Library for Contextual Object Recognition.. 3rd. Workshop on Recognition and Action for Scene Understanding (REACTS). (англ.)

[SuttonIntroduction-7] а ^б Sutton, Charles; McCallum, Andrew (2010). «An Introduction to Conditional Random Fields». arXiv:1011.4088v1 [stat.ML]. (англ.)

[8] Lavergne, Thomas; Yvon, François (7 вересня 2017). Learning the Structure of Variable-Order CRFs: a Finite-State Perspective. Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing. Copenhagen, Denmark: Association for Computational Linguistics. с. 433. (англ.)

[9] Chatzis, Sotirios; Demiris, Yiannis (2013). The Infinite-Order Conditional Random Field Model for Sequential Data Modeling. IEEE Transactions on Pattern Analysis and Machine Intelligence. 35 (6): 1523—1534. doi:10.1109/tpami.2012.208. PMID 23599063. (англ.)

[10] Gasthaus, Jan; Teh, Yee Whye (2010). Improvements to the Sequence Memoizer (PDF). Proc. NIPS. (англ.)

[11] Celeux, G.; Forbes, F.; Peyrard, N. (2003). EM Procedures Using Mean Field-Like Approximations for Markov Model-Based Image Segmentation. Pattern Recognition. 36 (1): 131—144. CiteSeerX 10.1.1.6.9064. doi:10.1016/s0031-3203(02)00027-4. (англ.)

[12] Sarawagi, Sunita; Cohen, William W. (2005). Semi-Markov conditional random fields for information extraction. У Lawrence K. Saul, Yair Weiss, Léon Bottou (eds.) (ред.). Advances in Neural Information Processing Systems 17. Cambridge, MA: MIT Press. с. 1185—1192. Архів оригіналу (PDF) за 30 листопада 2019. Процитовано 30 листопада 2019. (англ.)

[lvperceptron-13] а ^б ^в Xu Sun; Takuya Matsuzaki; Daisuke Okanohara; Jun'ichi Tsujii (2009). Latent Variable Perceptron Algorithm for Structured Classification. IJCAI. с. 1236—1242. Архів оригіналу за 6 грудня 2018. Процитовано 30 листопада 2019. (англ.)

[morency-14] а ^б Morency, L. P.; Quattoni, A.; Darrell, T. (2007). Latent-Dynamic Discriminative Models for Continuous Gesture Recognition (PDF). 2007 IEEE Conference on Computer Vision and Pattern Recognition. с. 1. CiteSeerX 10.1.1.420.6836. doi:10.1109/CVPR.2007.383299. ISBN 978-1-4244-1179-5. (англ.)

[15] T. Lavergne, O. Cappé and F. Yvon (2010). Practical very large scale CRFs [Архівовано 2013-07-18 у Wayback Machine.]. Proc. 48th Annual Meeting of the ACL^[en], pp. 504—513. (англ.)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]