Warunkowe pole losowe - Conditional random field

Część serii na
Uczenie maszynowe i eksploracja danych
Problemy Klasyfikacja Grupowanie Regresja Wykrywanie anomalii Czyszczenie danych AutoML Zasady stowarzyszenia Nauka wzmacniania Prognoza strukturalna Inżynieria funkcji Nauka funkcji Nauka online Nauka częściowo nadzorowana Nauka nienadzorowana Nauka rangi Indukcja gramatyczna
Uczenie nadzorowane ( klasyfikacja  • regresja ) Drzewa decyzyjne Zespoły Parcianka Wzmacnianie Losowy las k -NN Regresja liniowa Naiwny Bayes Sztuczne sieci neuronowe Regresja logistyczna Perceptron Maszyna wektorów trafności (RVM) Maszyna wektorów pomocniczych (SVM)
Grupowanie BRZOZOWY LECZYĆ Hierarchiczny k -oznacza Oczekiwanie – maksymalizacja (EM) DBSCAN OPTYKA Średnia zmiana
Redukcja wymiarowości Analiza czynników CCA ICA LDA NMF PCA PGD t-SNE
Prognoza strukturalna Modele graficzne Sieć Bayesa Warunkowe pole losowe Ukryty Markow
Wykrywanie anomalii k -NN Lokalny czynnik odstający
Sztuczna sieć neuronowa Autokoder Obliczenia kognitywne Głęboka nauka DeepDream Perceptron wielowarstwowy RNN LSTM GRU ESN Ograniczona maszyna Boltzmanna GAN SOM Konwolucyjna sieć neuronowa U-Net Transformator Wzrastająca sieć neuronowa Memtranzystor Elektrochemiczna pamięć RAM (ECRAM)
Nauka wzmacniania Q-learning SARSA Różnica czasowa (TD)
Teoria Kompromis między odchyleniami a wariancją Teoria uczenia się komputerowego Minimalizacja ryzyka empirycznego Nauka Occam Nauka PAC Nauka statystyczna Teoria VC
Miejsca uczenia maszynowego NeuroIPS ICML ML JMLR ArXiv:cs.LG
Powiązane artykuły Słowniczek sztucznej inteligencji Lista zbiorów danych do badań nad uczeniem maszynowym Zarys uczenia maszynowego
v T mi

Warunkowe pola losowe ( CRF ) to klasa metod modelowania statystycznego często stosowana w rozpoznawaniu wzorców i uczeniu maszynowym oraz wykorzystywana do przewidywania strukturalnego . Podczas gdy klasyfikator przewiduje etykietę dla pojedynczej próbki bez uwzględniania „sąsiadujących” próbek, CRF może uwzględniać kontekst. W tym celu predykcja jest modelowana jako model graficzny , który implementuje zależności między predykcjami. Rodzaj używanego wykresu zależy od aplikacji. Na przykład w przetwarzaniu języka naturalnego popularne są liniowe CRF, które implementują sekwencyjne zależności w predykcjach. Podczas przetwarzania obrazu wykres zazwyczaj łączy lokalizacje z pobliskimi i/lub podobnymi lokalizacjami, aby wymusić otrzymanie podobnych prognoz.

Inne przykłady zastosowania CRF to: znakowanie lub parsowanie danych sekwencyjnych do przetwarzania języka naturalnego lub sekwencji biologicznych , znakowanie POS , płytkie parsowanie , rozpoznawanie nazwanych jednostek , znajdowanie genów, znajdowanie obszarów funkcjonalnych krytycznych dla peptydów oraz rozpoznawanie obiektów i segmentacja obrazu w wizji komputerowej .

Opis

CRF są rodzajem dyskryminacyjnego, nieskierowanego probabilistycznego modelu graficznego .

Lafferty , McCallum i Pereira definiują CRF dla obserwacji i zmiennych losowych w następujący sposób: ${\displaystyle {\boldsymbol {X}}}$ ${\displaystyle {\boldsymbol {Y}}}$

Niech będzie wykresem takim, że ${\ Displaystyle G = (V, E)}$

${\ Displaystyle {\ boldsymbol {y}} = ({\ boldsymbol {y}} _ {v}) _ {v \ w V}}$, tak że jest indeksowany przez wierzchołki . Wtedy jest warunkowym polem losowym, gdy zmienne losowe uwarunkowane na , są zgodne z właściwością Markowa względem grafu: , gdzie oznacza, że i są sąsiadami w . ${\displaystyle {\boldsymbol {Y}}}$${\ Displaystyle G}$${\ Displaystyle ({\ pogrubienie {X}}, {\ pogrubienie {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}$

Oznacza to, że CRF jest nieskierowanym modelem graficznym, którego węzły można podzielić na dokładnie dwa rozłączne zbiory i odpowiednio zmienne obserwowane i wyjściowe; następnie modelowany jest rozkład warunkowy . ${\displaystyle {\boldsymbol {X}}}$${\displaystyle {\boldsymbol {Y}}}$${\ Displaystyle p ({\ pogrubienie {Y}} | {\ pogrubienie {X}})}$

Wnioskowanie

W przypadku wykresów ogólnych problem dokładnego wnioskowania w CRF jest trudny do rozwiązania. Problem wnioskowania dla CRF jest zasadniczo taki sam jak dla MRF i obowiązują te same argumenty. Istnieją jednak przypadki szczególne, dla których możliwe jest dokładne wnioskowanie:

• Jeśli graf jest łańcuchem lub drzewem, algorytmy przekazywania wiadomości dostarczają dokładnych rozwiązań. Algorytmy stosowane w tych przypadkach są analogiczne do algorytmu przód-tył i algorytmu Viterbiego w przypadku HMM.
• Jeśli CRF zawiera tylko potencjały parzyste , a energia jest submodularna , algorytmy kombinatoryczne minimalnego/maksymalnego przepływu dają dokładne rozwiązania.

Jeśli dokładne wnioskowanie jest niemożliwe, do uzyskania przybliżonych rozwiązań można zastosować kilka algorytmów. Obejmują one:

• Zapętlona propagacja przekonań
• Rozszerzenie alfa
• Wnioskowanie średniego pola
• Złagodzenia programowania liniowego

Nauka parametrów

Uczenie się parametrów jest zwykle wykonywane przez uczenie o maksymalnym prawdopodobieństwie dla . Jeśli wszystkie węzły mają rozkłady rodzin wykładniczych i wszystkie węzły są obserwowane podczas uczenia, optymalizacja ta jest wypukła. Można go rozwiązać na przykład za pomocą algorytmów gradientu lub metod Quasi-Newtona, takich jak algorytm L-BFGS . Z drugiej strony, jeśli niektóre zmienne nie są obserwowane, problem wnioskowania musi zostać rozwiązany dla tych zmiennych. Dokładne wnioskowanie jest niewykonalne na ogólnych wykresach, dlatego należy używać przybliżeń. ${\displaystyle \theta}$${\ Displaystyle p (Y_ {i} | X_ {i}; \ theta)}$

Przykłady

W modelowaniu sekwencji interesującym grafem jest zwykle graf łańcuchowy. Sekwencja wejściowa obserwowanych zmiennych reprezentuje sekwencję obserwacji i reprezentuje ukrytą (lub nieznaną) zmienną stanu, którą należy wywnioskować na podstawie obserwacji. Są tak skonstruowane, aby tworzyć łańcuch, z krawędzi między sobą i . Oprócz prostej interpretacji jako „etykiety” dla każdego elementu w sekwencji wejściowej, ten układ umożliwia wydajne algorytmy: ${\ Displaystyle X}$${\ Displaystyle Y}$${\ Displaystyle Y_ {i}}$${\ Displaystyle Y_ {i-1}}$${\ Displaystyle Y_ {i}}$${\ Displaystyle Y_ {i}}$

• Model szkolenia , nauka warunkowych rozkładów pomiędzy i funkcji fabularnych z jakiegoś corpus danych treningowych.${\ Displaystyle Y_ {i}}$
• dekodowania , wyznaczania prawdopodobieństwa danej sekwencji etykiet danym .${\ Displaystyle Y}$${\ Displaystyle X}$
• wnioskowanie , określając najbardziej prawdopodobną podaną sekwencję etykiet .${\ Displaystyle Y}$${\ Displaystyle X}$

Warunkowa zależność każdej z wartości jest definiowana przez ustalony zestaw funkcji charakterystycznych postaci , które można traktować jako pomiary sekwencji wejściowej, które częściowo określają prawdopodobieństwo każdej możliwej wartości dla . Model przypisuje każdej funkcji wagę liczbową i łączy je w celu określenia prawdopodobieństwa wystąpienia określonej wartości dla . ${\ Displaystyle Y_ {i}}$${\ Displaystyle X}$${\ Displaystyle f (i, Y_ {i-1}, Y_ {i}, X)}$${\ Displaystyle Y_ {i}}$${\ Displaystyle Y_ {i}}$

Liniowe modele CRF mają wiele takich samych zastosowań jak koncepcyjnie prostsze ukryte modele Markowa (HMM), ale rozluźniają pewne założenia dotyczące rozkładu sekwencji wejściowych i wyjściowych. HMM może być luźno rozumiany jako CRF z bardzo specyficznymi funkcjami, które wykorzystują stałe prawdopodobieństwa do modelowania przejść stanów i emisji. Odwrotnie, CRF można luźno rozumieć jako uogólnienie HMM, które powoduje, że stałe prawdopodobieństwa przejścia w dowolne funkcje różnią się w zależności od pozycji w sekwencji stanów ukrytych, w zależności od sekwencji wejściowej.

Warto zauważyć, że w przeciwieństwie do HMM, CRF mogą zawierać dowolną liczbę funkcji funkcji, funkcje funkcji mogą sprawdzać całą sekwencję wejściową w dowolnym momencie podczas wnioskowania, a zakres funkcji funkcji nie musi mieć interpretacji probabilistycznej. ${\ Displaystyle X}$

Warianty

CRF wyższego rzędu i CRF semi-Markowa

CRF można rozszerzyć na modele wyższego rzędu, uzależniając każdy z nich od stałej liczby poprzednich zmiennych . W konwencjonalnych formułach CRF wyższego rzędu szkolenie i wnioskowanie są praktyczne tylko dla małych wartości (takich jak k ≤ 5), ponieważ ich koszt obliczeniowy rośnie wykładniczo wraz z . ${\ Displaystyle Y_ {i}}$${\displaystyle k}$${\ Displaystyle Y_ {ik}, ..., Y_ {i-1}}$${\displaystyle k}$${\displaystyle k}$

Jednak kolejny niedawny postęp zdołał złagodzić te problemy, wykorzystując koncepcje i narzędzia z dziedziny nieparametrycznych bayesowskich. W szczególności podejście CRF-nieskończoności stanowi model typu CRF, który jest zdolny do uczenia się nieskończenie długiej dynamiki czasowej w sposób skalowalny. W tym celu wprowadzono nową potencjalną funkcję dla CRF, opartą na Sequence Memoizer (SM), nieparametrycznym modelu bayesowskim do uczenia się nieskończenie długiej dynamiki w obserwacjach sekwencyjnych. Aby uczynić taki model wykonalnym obliczeniowo, CRF-nieskończoność wykorzystuje aproksymację średniego pola postulowanych nowych funkcji potencjalnych (które są sterowane przez SM). Pozwala to na opracowanie wydajnych algorytmów przybliżonego uczenia i wnioskowania dla modelu, bez podważania jego zdolności do wychwytywania i modelowania zależności czasowych o dowolnej długości.

Istnieje inne uogólnienie CRF, warunkowe pole losowe semi-Markowa (semi-CRF) , które modeluje segmentacje sekwencji etykiet o zmiennej długości . Zapewnia to znaczną część mocy CRF wyższego rzędu do modelowania długozasięgowych zależności , przy rozsądnych kosztach obliczeniowych. ${\ Displaystyle Y}$${\ Displaystyle Y_ {i}}$

Wreszcie modele z dużymi marżami do ustrukturyzowanego przewidywania , takie jak ustrukturyzowana maszyna wektorów nośnych, mogą być postrzegane jako alternatywna procedura szkoleniowa dla CRF.

Utajone dynamiczne warunkowe pole losowe

Utajone dynamiczne warunkowe zmienne losowe ( LDCRF ) lub dyskryminacyjne probabilistyczne modele zmiennych latentnych ( DPLVM ) są rodzajem CRF dla zadań znakowania sekwencji. Są to modele zmiennych utajonych, które są szkolone w sposób dyskryminacyjny.

W LDCRF, jak w każdym zadaniu znakowania sekwencji, przy danej sekwencji obserwacji x = , głównym problemem, który musi rozwiązać model, jest przypisanie sekwencji etykiet y = z jednego skończonego zbioru etykiet Y . Zamiast bezpośredniego modelowania P ( y | x ) tak, jak zrobiłby to zwykły CRF z łańcuchem liniowym, zestaw zmiennych latentnych h jest „wstawiany” między x i y przy użyciu łańcuchowej reguły prawdopodobieństwa : ${\displaystyle x_{1},\kropki,x_{n}}$${\ Displaystyle y_ {1}, \ kropki , y_ {n}}$

${\ Displaystyle P (\ mathbf {y} | \ mathbf {x} ) = \ suma _ {\ mathbf {h}} P (\ mathbf {y} | \ mathbf {h}, \ mathbf {x}) P ( \mathbf {h} |\mathbf {x} )}$

Pozwala to na uchwycenie ukrytej struktury między obserwacjami a etykietami. Chociaż LDCRF można trenować za pomocą metod quasi-Newtona, opracowano dla nich specjalną wersję algorytmu perceptronowego zwaną perceptronem o zmiennej latentnej , opartą na algorytmie strukturalnym perceptronu Collinsa . Modele te znajdują zastosowanie w wizji komputerowej , w szczególności w rozpoznawaniu gestów ze strumieni wideo i płytkim analizowaniu .

Oprogramowanie

To jest częściowa lista oprogramowania, które implementuje ogólne narzędzia CRF.

• RNNSharp CRFs oparte na rekurencyjnych sieciach neuronowych ( C# , .NET )
• CRF-ADF Liniowy łańcuch CRF z szybkim szkoleniem online ADF ( C# , .NET )
• CRFSharp z łańcuchem liniowym CRF ( C# , .NET )
• GCO CRF z submodularnymi funkcjami energii ( C++ , Matlab )
• Ogólne CRF DGM ( C++ )
• Ogólne CRF GRMM ( Java )
• fabryka Ogólne CRFs ( Scala )
• CRFall Ogólne CRF ( Matlab )
• CRF CRF z łańcuchem liniowym Sarawagi ( Java )
• Biblioteka HCRF Ukryte kody CRF ( C++ , Matlab )
• Accord.NET Linear-chain CRF, HCRF i HMM ( C# , .NET )
• CRF z łańcuchem liniowym Wapiti Fast ( C )
• CRFSuite Fast z ograniczonym łańcuchem liniowym CRF ( C )
• CRF++ z łańcuchem liniowym CRF ( C++ )
• FlexCRFs 1. i 2. rzędu CRFs Markowa ( C++ )
• crf-chain1 CRF pierwszego rzędu, liniowy łańcuch ( Haskell )
• imageCRF CRF do segmentacji obrazów i woluminów obrazów ( C++ )
• MALLET Łańcuch liniowy do znakowania sekwencji ( Java )
• Uczenie strukturalne PyStruct w Pythonie ( Python )
• Pycrfsuite Wiązanie Pythona dla crfsuite ( Python )
• Probabilistyczny język programowania Figaro zdolny do definiowania CRF i innych modeli graficznych ( Scala )
• Modelowanie CRF i narzędzia obliczeniowe dla CRF i innych nieukierunkowanych modeli graficznych ( R )
• Biblioteka OpenGM dla modeli dyskretnych grafów czynnikowych i operacji dystrybucyjnych na tych modelach ( C++ )
• Biblioteka UPGMpp do budowania, trenowania i przeprowadzania wnioskowania z nieukierunkowanymi modelami graficznymi ( C++ )
• KEG_CRF Szybkie liniowe CRF ( C++ )

To jest częściowa lista oprogramowania, które implementuje narzędzia związane z CRF.

• MedaCy Medical Named Entity Recognizer ( Python )
• Predyktor genów oparty na Conrada CRF ( Java )
• Rozpoznawanie nazwanych jednostek Stanford NER ( Java )
• BANNER Rozpoznawanie nazwanych jednostek ( Java )
• SparkNLP SparkNLP NerCrfApproach ( Java , Scala , Python )

Zobacz też

• Twierdzenie Hammersleya-Clifforda
• Model graficzny
• Losowe pole Markowa
• Model Markowa maksymalnej entropii (MEMM)

Bibliografia

Dalsza lektura

• McCallum, A.: Efektywne indukowanie cech warunkowych pól losowych . W: proc. XIX Konferencja Niepewność w Sztucznej Inteligencji . (2003)
• Wallach, HM : Warunkowe pola losowe: Wprowadzenie . Raport techniczny MS-CIS-04-21, University of Pennsylvania (2004)
• Sutton, C., McCallum, A.: Wprowadzenie do warunkowych pól losowych do relacyjnego uczenia się. W „Wstępie do statystycznego uczenia relacyjnego”. Edytowany przez Lise Getoor i Bena Taskara. MIT Naciśnij. (2006) PDF online
• Klinger R., Tomanek K.: Klasyczne modele probabilistyczne i warunkowe pola losowe. Raport Inżynierii Algorytmów TR07-2-013, Wydział Informatyki, Uniwersytet Technologiczny w Dortmundzie, grudzień 2007. ISSN 1864-4503. PDF online