Ein Conditional Random Field (CRF) ist eine Klasse statistischer Modellierungsmethoden, die für strukturierte Vorhersagen in der Mustererkennung und im maschinellen Lernen verwendet werden. Im Gegensatz zu einem Klassifikator, der ein Label für eine einzelne Stichprobe ohne Berücksichtigung benachbarter Stichproben vorhersagt, kann ein CRF den Kontext berücksichtigen, indem es Vorhersagen als grafisches Modell modelliert, das Abhängigkeiten zwischen ihnen darstellt. Die Graphstruktur hängt von der Anwendung ab: Beispielsweise sind in der Verarbeitung natürlicher Sprache lineare Ketten-CRFs beliebt, bei denen jede Vorhersage nur von ihren unmittelbaren Nachbarn abhängt; in der Bildverarbeitung verbindet der Graph typischerweise Orte mit nahegelegenen oder ähnlichen Orten, um konsistente Vorhersagen zu erzwingen.
CRFs sind diskriminative ungerichtete probabilistische grafische Modelle. Formal gilt: Gegeben Beobachtungen \(\boldsymbol{X}\) und Zufallsvariablen \(\boldsymbol{Y}\), die durch Knoten \(V\) eines Graphen \(G=(V,E)\) indiziert sind, ist das Paar \((\boldsymbol{X},\boldsymbol{Y})\) ein Conditional Random Field, wenn jede Variable \(\boldsymbol{Y}_v\), konditioniert auf \(\boldsymbol{X}\), die Markov-Eigenschaft bezüglich des Graphen erfüllt: Ihre Wahrscheinlichkeit hängt nur von ihren Nachbarn in \(G\) ab, nicht von anderen Variablen. Dies bedeutet, dass die Knoten in zwei disjunkte Mengen unterteilt sind, beobachtete Variablen \(\boldsymbol{X}\) und Ausgabevariablen \(\boldsymbol{Y}\), und die bedingte Verteilung \(p(\boldsymbol{Y}|\boldsymbol{X})\) modelliert wird.
Anwendungen
CRFs werden häufig für die Kennzeichnung oder das Parsing sequenzieller Daten in der Verarbeitung natürlicher Sprache und biologischen Sequenzen verwendet. Häufige Aufgaben umfassen Part-of-Speech-Tagging, flaches Parsing, Erkennung benannter Entitäten, Genfindung und die Identifizierung kritischer funktioneller Regionen in Peptiden. In der Computer Vision werden CRFs für die Objekterkennung und Bildsegmentierung eingesetzt, wobei räumlicher Kontext hilft, kohärente Labels zu erzeugen. Beispielsweise kann ein CRF bei der Bildsegmentierung erzwingen, dass benachbarte Pixel mit ähnlichen Farben dasselbe Label erhalten.
Inferenz
Für allgemeine Graphen ist exakte Inferenz in CRFs nicht handhabbar, ähnlich wie bei Markov Random Fields. Spezialfälle ermöglichen jedoch exakte Lösungen. Wenn der Graph eine Kette oder ein Baum ist, liefern Message-Passing-Algorithmen exakte Ergebnisse, analog zu den Forward-Backward- und Viterbi-Algorithmen, die für Hidden Markov Models verwendet werden. Wenn das CRF nur paarweise Potenziale enthält und die Energie submodular ist, liefern kombinatorische Max-Flow-Min-Cut-Algorithmen exakte Lösungen. Wenn exakte Inferenz unmöglich ist, umfassen approximative Methoden Loopy Belief Propagation, Alpha-Expansion, Mean-Field-Inferenz und Relaxationen der linearen Programmierung.
Parameterlernen
Das Lernen der Parameter \(\theta\) erfolgt typischerweise durch Maximum-Likelihood-Schätzung von \(p(Y_i|X_i;\theta)\). Wenn alle Knoten Exponentialfamilien-Verteilungen haben und alle Knoten während des Trainings beobachtet werden, ist das Optimierungsproblem konvex und kann mit Gradientenabstieg oder Quasi-Newton-Methoden wie L-BFGS gelöst werden. Wenn einige Variablen unbeobachtet sind, muss für diese Variablen Inferenz durchgeführt werden, und da exakte Inferenz in allgemeinen Graphen nicht handhabbar ist, werden Näherungen verwendet.
Beziehung zu anderen Modellen
CRFs sind mit Hidden Markov Models (HMMs) verwandt, aber diskriminativ, da sie die bedingte Verteilung direkt modellieren, anstatt die gemeinsame Verteilung. Dies ermöglicht es CRFs, beliebige, überlappende Merkmale der Beobachtungen ohne Unabhängigkeitsannahmen zu integrieren. Bei der Sequenzmodellierung ist ein lineares Ketten-CRF ein Spezialfall, bei dem der Graph eine Kette ist, was die Inferenz effizient macht. CRFs haben Einfluss auf die Verarbeitung natürlicher Sprache und Computer Vision gehabt und bleiben in modernen Maschinenlern-Pipelines relevant, obwohl Deep-Learning-Methoden sie in vielen Anwendungen weitgehend ersetzt haben. Allerdings werden CRFs manchmal mit Neuronalen Netzwerk-Modellen kombiniert, wie etwa in neuronalen CRFs für Sequenzkennzeichnung, bei denen ein neuronales Netzwerk Merkmale berechnet und eine CRF-Schicht Abhängigkeiten modelliert.