Podmíněné náhodné pole - Conditional random field

Podmíněná náhodná pole (CRF) jsou třídou metoda statistického modelování často se používá v rozpoznávání vzorů a strojové učení a používá se pro strukturovaná předpověď. Vzhledem k tomu, že klasifikátor předpovídá označení pro jeden vzorek bez ohledu na „sousední“ vzorky, může CRF brát v úvahu kontext. K tomu je předpověď modelována jako a grafický model, který implementuje závislosti mezi předpovědi. Jaký druh grafu se použije, závisí na aplikaci. Například v zpracování přirozeného jazyka, populární jsou CRF s lineárním řetězcem, které v předpovědích implementují sekvenční závislosti. Při zpracování obrazu graf obvykle spojuje místa s blízkými a / nebo podobnými místy, aby vynutil, že dostanou podobné předpovědi.

Další příklady použití CRF jsou: Značení nebo analýza sekvenčních dat pro zpracování přirozeného jazyka nebo biologické sekvence,^[1] Značení POS, mělká analýza,^[2] uznání pojmenované entity,^[3] nález genů, nalezení kritické funkční oblasti peptidu,^[4] a rozpoznávání objektů^[5] a segmentace obrazu v počítačové vidění.^[6]

Popis

CRF jsou typem diskriminační neorientovaný pravděpodobnostní grafický model.

Lafferty, McCallum a Pereira^[1] definovat CRF na pozorováních ${displaystyle {oldsymbol {X}}}$ a náhodné proměnné ${displaystyle {oldsymbol {Y}}}$ jak následuje:

Nechat ${displaystyle G = (V, E)}$ být takovým grafem
${displaystyle {oldsymbol {Y}} = ({oldsymbol {Y}} _ {v}) _ {vin V}}$ , aby ${displaystyle {oldsymbol {Y}}}$ je indexován vrcholy ${displaystyle G}$ . Pak ${displaystyle ({oldsymbol {X}}, {oldsymbol {Y}})}$ je podmíněné náhodné pole, když náhodné proměnné ${displaystyle {oldsymbol {Y}} _ {v}}$ , podmíněno ${displaystyle {oldsymbol {X}}}$ , poslouchejte Majetek Markov s ohledem na graf: ${displaystyle p ({oldsymbol {Y}} _ {v} | {oldsymbol {X}}, {oldsymbol {Y}} _ {w}, weq v) = p ({oldsymbol {Y}} _ {v} | {oldsymbol {X}}, {oldsymbol {Y}} _ {w}, wsim v)}$ , kde ${displaystyle {mathit {w}} sim v}$ znamená, že ${displaystyle w}$ a ${displaystyle v}$ jsou sousedé v ${displaystyle G}$ .

To znamená, že CRF je neorientovaný grafický model jejichž uzly lze rozdělit přesně na dvě disjunktní množiny ${displaystyle {oldsymbol {X}}}$ a ${displaystyle {oldsymbol {Y}}}$ pozorované a výstupní proměnné; podmíněné rozdělení ${displaystyle p ({oldsymbol {Y}} | {oldsymbol {X}})}$ je poté modelován.

Odvození

U obecných grafů je problém přesné odvození v CRF neřešitelný. Problém odvození pro CRF je v zásadě stejný jako pro MRF a stejné argumenty platí.^[7]Existují však speciální případy, u nichž je možný přesný závěr:

Pokud je grafem řetěz nebo strom, poskytují algoritmy předávání zpráv přesná řešení. Algoritmy použité v těchto případech jsou analogické s dopředu Dozadu a Viterbiho algoritmus pro případ HMM.
Pokud CRF obsahuje pouze párové potenciály a energie je submodulární, kombinatorické algoritmy min cut / max flow přinášejí přesná řešení.

Pokud není přesný závěr možný, lze k získání přibližných řešení použít několik algoritmů. Tyto zahrnují:

Loopy šíření víry
Alfa expanze
Střední odvození pole
Relaxace lineárního programování

Učení parametrů

Učení parametrů ${displaystyle heta}$ se obvykle provádí maximální pravděpodobnost učit se pro ${displaystyle p (Y_ {i} | X_ {i}; heta)}$ . Pokud mají všechny uzly exponenciální rozdělení rodiny a všechny uzly jsou pozorovány během tréninku, toto optimalizace je konvexní.^[7] Lze to vyřešit například pomocí klesání algoritmy, nebo Kvazi-Newtonovy metody tak jako L-BFGS algoritmus. Na druhou stranu, pokud některé proměnné nejsou pozorovány, je třeba u těchto proměnných vyřešit problém odvození. Přesný závěr je v obecných grafech neřešitelný, takže je třeba použít aproximace.

Příklady

Při sekvenčním modelování je grafem zájmu obvykle řetězový graf. Vstupní sled pozorovaných proměnných ${displaystyle X}$ představuje sled pozorování a ${displaystyle Y}$ představuje skrytou (nebo neznámou) proměnnou stavu, kterou je třeba odvodit na základě pozorování. The ${displaystyle Y_ {i}}$ jsou strukturovány tak, aby tvořily řetěz s hranou mezi nimi ${displaystyle Y_ {i-1}}$ a ${displaystyle Y_ {i}}$ . Stejně jako jednoduchý výklad ${displaystyle Y_ {i}}$ jako "štítky" pro každý prvek ve vstupní sekvenci toto rozložení umožňuje efektivní algoritmy pro:

Modelka výcvik, učení podmíněného rozdělení mezi ${displaystyle Y_ {i}}$ a funkce funkcí z nějakého korpusu tréninkových dat.
dekódování, určující pravděpodobnost dané sekvence návěští ${displaystyle Y}$ daný ${displaystyle X}$ .
odvození, určující pravděpodobně sekvence štítku ${displaystyle Y}$ daný ${displaystyle X}$ .

Podmíněná závislost každého z nich ${displaystyle Y_ {i}}$ na ${displaystyle X}$ je definována prostřednictvím pevné sady funkce funkcí formuláře ${displaystyle f (i, Y_ {i-1}, Y_ {i}, X)}$ , které lze považovat za měření vstupní sekvence, která částečně určují pravděpodobnost každé možné hodnoty pro ${displaystyle Y_ {i}}$ . Model přiřazuje každému prvku číselnou váhu a kombinuje je, aby určil pravděpodobnost určité hodnoty pro ${displaystyle Y_ {i}}$ .

Lineární řetězce CRF mají mnoho stejných aplikací jako koncepčně jednodušší skryté Markovovy modely (HMM), ale uvolňují určité předpoklady o distribuci vstupní a výstupní sekvence. HMM lze volně chápat jako CRF s velmi specifickými funkcemi funkcí, které používají konstantní pravděpodobnosti k modelování přechodů stavů a emisí. Naopak CRF lze volně chápat jako zobecnění HMM, díky kterému jsou pravděpodobnosti konstantního přechodu do libovolných funkcí, které se liší napříč pozicemi v posloupnosti skrytých stavů, v závislosti na vstupní posloupnosti.

Je pozoruhodné, že na rozdíl od HMM mohou CRF obsahovat libovolný počet funkcí funkcí, funkce funkcí mohou kontrolovat celou vstupní sekvenci ${displaystyle X}$ kdykoli během odvození a rozsah funkcí funkcí nemusí mít pravděpodobnostní interpretaci.

Varianty

CRF vyššího řádu a polomarkovské CRF

CRF lze rozšířit do modelů vyššího řádu jejich vyrobením ${displaystyle Y_ {i}}$ v závislosti na pevném čísle ${displaystyle k}$ předchozích proměnných ${displaystyle Y_ {i-k}, ..., Y_ {i-1}}$ . V konvenčních formulacích CRF vyššího řádu jsou školení a závěry praktické pouze pro malé hodnoty ${displaystyle k}$ (jako k ≤ 5),^[8] protože jejich výpočetní náklady exponenciálně rostou s ${displaystyle k}$ .

Dalšímu nedávnému pokroku se však podařilo vyřešit tyto problémy využitím konceptů a nástrojů z oblasti Bayesovské neparametrie. Konkrétně přístup CRF-nekonečno^[9] představuje model typu CRF, který je schopen se učit nekonečně dlouhou časovou dynamiku škálovatelným způsobem. Toho je dosaženo zavedením nové potenciální funkce pro CRF, která je založena na Sequence Memoizer (SM), neparametrickém Bayesianově modelu pro učení nekonečně dlouhé dynamiky v sekvenčních pozorováních.^[10] K vykreslení takového modelu výpočetně použitelného využívá CRF-infinity a střední aproximace pole^[11] postulovaných nových potenciálních funkcí (které jsou řízeny SM). To umožňuje navrhnout efektivní přibližné tréninkové a inferenční algoritmy pro model, aniž by to narušilo jeho schopnost zachytit a modelovat časové závislosti libovolné délky.

Existuje další zobecnění CRF, semi-Markov podmíněné náhodné pole (semi-CRF), který modeluje proměnnou délku segmentace sekvence štítku ${displaystyle Y}$ .^[12] To poskytuje velkou část síly CRF vyššího řádu k modelování závislostí dálkového dosahu ${displaystyle Y_ {i}}$ za rozumnou výpočetní cenu.

Konečně modely s velkou rezervou pro strukturovaná předpověď, tak jako strukturovaný Support Vector Machine lze považovat za alternativní výcvikový postup k CRF.

Latentně dynamické podmíněné náhodné pole

Latentní dynamická podmíněná náhodná pole (LDCRF) nebo diskriminační pravděpodobnostní latentní proměnné modely (DPLVM) jsou typem CRF pro úkoly označování sekvencí. Oni jsou latentní variabilní modely kteří jsou diskriminováni.

V LDCRF, jako v každém úkolu značení sekvence, je dána sled pozorování X = ${displaystyle x_ {1}, tečky, x_ {n}}$ , hlavním problémem, který musí model vyřešit, je způsob přiřazení posloupnosti štítků y = ${displaystyle y_ {1}, tečky, y_ {n}}$ z jedné konečné sady štítků $Y$ . Místo přímého modelování $P$ (y|X) jako by to udělal běžný CRF s lineárním řetězcem, sada latentních proměnných h je „vloženo“ mezi X a y za použití řetězové pravidlo pravděpodobnosti:^[13]

{displaystyle P (mathbf {y} | mathbf {x}) = součet _ {mathbf {h}} P (mathbf {y} | mathbf {h}, mathbf {x}) P (mathbf {h} | mathbf {x })}

To umožňuje zachytit latentní strukturu mezi pozorováním a štítky.^[14] Zatímco LDCRF lze trénovat pomocí kvazi-Newtonových metod, specializovaná verze perceptron algoritmus zvaný latentní proměnná perceptron byl vyvinut také pro ně na základě Collinsova strukturovaný perceptron algoritmus.^[13] Tyto modely nacházejí uplatnění v počítačové vidění konkrétně rozpoznávání gest z video streamů^[14] a mělká analýza.^[13]

Software

Toto je částečný seznam softwaru, který implementuje obecné nástroje CRF.

RNN Sharp CRF založené na rekurentních neuronových sítích (C#, .SÍŤ )
CRF-ADF Lineární řetězce CRF s rychlým online školením ADF (C#, .SÍŤ )
CRFSharp CRF s lineárním řetězcem (C#, .SÍŤ )
GCO CRF se submodulárními energetickými funkcemi (C ++, Matlab )
DGM Obecné CRF (C ++ )
GRMM Obecné CRF (Jáva )
továrna Obecné CRF (Scala )
CR Pád Obecné CRF (Matlab )
Sarawagiho CRF CRF s lineárním řetězcem (Jáva )
Knihovna HCRF Skryté CRF (C ++, Matlab )
Accord.NET CRF, HCRF a HMM s lineárním řetězcem (C#, .SÍŤ )
Wapiti Rychlé CRF s lineárním řetězcem (C )^[15]
CRFSuite Rychle omezené lineární řetězce CRF (C )
CRF ++ CRF s lineárním řetězcem (C ++ )
FlexCRF Markov CRF prvního a druhého řádu (C ++ )
crf-chain1 CRF prvního řádu s lineárním řetězcem (Haskell )
imageCRF CRF pro segmentaci obrazů a objemů obrazů (C ++ )
Palička Lineární řetězec pro označování sekvencí (Jáva )
PyStruct Strukturované učení v Pythonu (Krajta )
Pycrfsuite Pythonová vazba pro crfsuite (Krajta )
Figaro Pravděpodobnostní programovací jazyk schopný definovat CRF a další grafické modely (Scala )
CRF Modelovací a výpočetní nástroje pro CRF a další neorientované grafické modely (R )
OpenGM Knihovna pro diskrétní faktorový graf modely a distribuční operace na těchto modelech (C ++ )
UPGMpp^[5] Knihovna pro vytváření, školení a provádění závěrů s nepřímými grafickými modely (C ++ )
KEG_CRF Rychlé lineární CRF (C ++ )

Toto je částečný seznam softwaru, který implementuje nástroje související s CRF.

MedaCy Lékařský uznaný subjekt (Krajta )
Conrad CRF genový prediktor (Jáva )
Stanford NER Rozpoznávač pojmenovaných entit (Jáva )
PRAPOR Rozpoznávač pojmenovaných entit (Jáva )

Viz také

Reference

^ ^A ^b Lafferty, J., McCallum, A., Pereira, F. (2001). „Podmíněná náhodná pole: Pravděpodobnostní modely pro segmentaci a označování sekvenčních dat“. Proc. 18. mezinárodní konf. na strojovém učení. Morgan Kaufmann. str. 282–289.CS1 maint: používá parametr autoři (odkaz)
^ Sha, F .; Pereira, F. (2003). mělká analýza s podmíněnými náhodnými poli.
^ Settles, B. (2004). „Biomedicínské rozpoznávání pojmenovaných entit pomocí podmíněných náhodných polí a bohatých sad funkcí“ (PDF). Sborník z mezinárodního společného semináře o zpracování přirozeného jazyka v biomedicíně a jeho aplikacích. str. 104–107.
^ Chang KY; Lin T-p; Shih L-Y; Wang CK (2015). Analýza a predikce kritických oblastí antimikrobiálních peptidů na základě podmíněných náhodných polí. PLOS ONE. doi:10.1371 / journal.pone.0119490. PMC 4372350.
^ ^A ^b J.R. Ruiz-Sarmiento; C. Galindo; J. Gonzalez-Jimenez (2015). „UPGMpp: softwarová knihovna pro rozpoznávání kontextových objektů.“. 3. místo Workshop o rozpoznávání a jednání za porozumění scéně (REACTS).
^ On, X.; Zemel, R.S .; Carreira-Perpinñán, M.A. (2004). Msgstr "Podmíněná náhodná pole pro označování obrázků s více měřítky". IEEE Computer Society. CiteSeerX 10.1.1.3.7826.
^ ^A ^b Sutton, Charles; McCallum, Andrew (2010). "Úvod do podmíněných náhodných polí". arXiv:1011.4088v1 [stat.ML ].
^ Lavergne, Thomas; Yvon, François (7. září 2017). „Naučit se strukturu CRF s proměnným řádem: perspektiva konečného stavu“. Sborník konference z roku 2017 o empirických metodách ve zpracování přirozeného jazyka. Kodaň, Dánsko: Sdružení pro výpočetní lingvistiku. p. 433.
^ Chatzis, Sotirios; Demiris, Yiannis (2013). "Model podmíněného náhodného pole nekonečného řádu pro sekvenční modelování dat". Transakce IEEE na analýze vzorů a strojové inteligenci. 35 (6): 1523–1534. doi:10.1109 / tpami.2012.208. hdl:10044/1/12614. PMID 23599063.
^ Gasthaus, Jan; Teh, Yee Whye (2010). „Vylepšení Memoizeru sekvence“ (PDF). Proc. NIPS.
^ Celeux, G .; Forbes, F .; Peyrard, N. (2003). „EM postupy využívající střední segmentové aproximace pro segmentaci obrazu podle Markovova modelu“. Rozpoznávání vzorů. 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 podmíněná náhodná pole pro extrakci informací" (PDF). In Lawrence K. Saul; Yair Weiss; Léon Bottou (eds.). Pokroky v systémech zpracování neurálních informací 17. Cambridge, MA: MIT Press. str. 1185–1192.
^ ^A ^b ^C Xu Sun; Takuya Matsuzaki; Daisuke Okanohara; Jun'ichi Tsujii (2009). Latentní variabilní perceptronový algoritmus pro strukturovanou klasifikaci. IJCAI. s. 1236–1242.
^ ^A ^b Morency, L. P .; Quattoni, A .; Darrell, T. (2007). „Latentní dynamické diskriminační modely pro kontinuální rozpoznávání gest“ (PDF). Konference IEEE 2007 o počítačovém vidění a rozpoznávání vzorů. p. 1. CiteSeerX 10.1.1.420.6836. doi:10.1109 / CVPR.2007.383299. ISBN 978-1-4244-1179-5.
^ T. Lavergne, O. Cappé a F. Yvon (2010). Praktické CRF ve velkém měřítku Archivováno 2013-07-18 na Wayback Machine. Proc. 48. Výroční zasedání ACL, str. 504-513.

Další čtení

McCallum, A .: Efektivní vyvolání vlastností podmíněných náhodných polí. V: Proc. 19. konference o nejistotě v umělé inteligenci. (2003)
Wallach, H.M .: Podmíněná náhodná pole: Úvod. Technická zpráva MS-CIS-04-21, University of Pennsylvania (2004)
Sutton, C., McCallum, A .: Úvod do podmíněných náhodných polí pro relační učení. V „Úvod do statistického relačního učení“. Upraveno uživatelem Lise Getoor a Ben Taskar. MIT Stiskněte. (2006) Online PDF
Klinger, R., Tomanek, K .: Klasické pravděpodobnostní modely a podmíněná náhodná pole. 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] A ^b Lafferty, J., McCallum, A., Pereira, F. (2001). „Podmíněná náhodná pole: Pravděpodobnostní modely pro segmentaci a označování sekvenčních dat“. Proc. 18. mezinárodní konf. na strojovém učení. Morgan Kaufmann. str. 282–289.CS1 maint: používá parametr autoři (odkaz)

[2] Sha, F .; Pereira, F. (2003). mělká analýza s podmíněnými náhodnými poli.

[3] Settles, B. (2004). „Biomedicínské rozpoznávání pojmenovaných entit pomocí podmíněných náhodných polí a bohatých sad funkcí“ (PDF). Sborník z mezinárodního společného semináře o zpracování přirozeného jazyka v biomedicíně a jeho aplikacích. str. 104–107.

[4] Chang KY; Lin T-p; Shih L-Y; Wang CK (2015). Analýza a predikce kritických oblastí antimikrobiálních peptidů na základě podmíněných náhodných polí. PLOS ONE. doi:10.1371 / journal.pone.0119490. PMC 4372350.

[Rui:Gal:Gon15-5] A ^b J.R. Ruiz-Sarmiento; C. Galindo; J. Gonzalez-Jimenez (2015). „UPGMpp: softwarová knihovna pro rozpoznávání kontextových objektů.“. 3. místo Workshop o rozpoznávání a jednání za porozumění scéně (REACTS).

[6] On, X.; Zemel, R.S .; Carreira-Perpinñán, M.A. (2004). Msgstr "Podmíněná náhodná pole pro označování obrázků s více měřítky". IEEE Computer Society. CiteSeerX 10.1.1.3.7826.

[SuttonIntroduction-7] A ^b Sutton, Charles; McCallum, Andrew (2010). "Úvod do podmíněných náhodných polí". arXiv:1011.4088v1 [stat.ML ].

[8] Lavergne, Thomas; Yvon, François (7. září 2017). „Naučit se strukturu CRF s proměnným řádem: perspektiva konečného stavu“. Sborník konference z roku 2017 o empirických metodách ve zpracování přirozeného jazyka. Kodaň, Dánsko: Sdružení pro výpočetní lingvistiku. p. 433.

[9] Chatzis, Sotirios; Demiris, Yiannis (2013). "Model podmíněného náhodného pole nekonečného řádu pro sekvenční modelování dat". Transakce IEEE na analýze vzorů a strojové inteligenci. 35 (6): 1523–1534. doi:10.1109 / tpami.2012.208. hdl:10044/1/12614. PMID 23599063.

[10] Gasthaus, Jan; Teh, Yee Whye (2010). „Vylepšení Memoizeru sekvence“ (PDF). Proc. NIPS.

[11] Celeux, G .; Forbes, F .; Peyrard, N. (2003). „EM postupy využívající střední segmentové aproximace pro segmentaci obrazu podle Markovova modelu“. Rozpoznávání vzorů. 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 podmíněná náhodná pole pro extrakci informací" (PDF). In Lawrence K. Saul; Yair Weiss; Léon Bottou (eds.). Pokroky v systémech zpracování neurálních informací 17. Cambridge, MA: MIT Press. str. 1185–1192.

[lvperceptron-13] A ^b ^C Xu Sun; Takuya Matsuzaki; Daisuke Okanohara; Jun'ichi Tsujii (2009). Latentní variabilní perceptronový algoritmus pro strukturovanou klasifikaci. IJCAI. s. 1236–1242.

[morency-14] A ^b Morency, L. P .; Quattoni, A .; Darrell, T. (2007). „Latentní dynamické diskriminační modely pro kontinuální rozpoznávání gest“ (PDF). Konference IEEE 2007 o počítačovém vidění a rozpoznávání vzorů. p. 1. CiteSeerX 10.1.1.420.6836. doi:10.1109 / CVPR.2007.383299. ISBN 978-1-4244-1179-5.

[15] T. Lavergne, O. Cappé a F. Yvon (2010). Praktické CRF ve velkém měřítku Archivováno 2013-07-18 na Wayback Machine. Proc. 48. Výroční zasedání ACL, str. 504-513.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]