Information Extraction in der Koch-Domäne

Folgend werden Algorithmen zum Extrahieren von Zutaten aus semi-strukturiertem Text vorgestellt, die wir im Kontext der Koch-Domäne gefunden haben. Sind die Zutaten erst einmal von einem Programm extrahiert, kann das Programm diese leicht mit cueML auszeichnen und zurückschreiben. Das automatische Auszeichnen ist wünschenswert, da das manuelle Auszeichnen...

• zeitaufwendig ist. Die Erfahrung hat gezeigt, dass ich selber im Schnitt ca. 5 Minuten pro Rezept zum Auszeichnen brauche. Eine SHK, welche nicht im Umgang mit XML geübt war, hat freundlicherweise ebenfalls ein paar Rezepte ausgezeichnet. Sie hat im Schnitt sogar 15 Minuten für ein Rezept gebraucht.
• fehleranfällig ist. Diese Feststellung bei mir selbst, wie auch bei der SHK werden u.A. durch und bestätigt.
• Domänen-spezifisches Wissen benötigt. Wir sind z. B. über die Zutat Scorzonerwurzel gestolpert. Das Nachfragen bei einer Ernährungswissenschaftlerin der Kieler Uni ergab, dass damit wahrscheinlich Scorzone, bzw. Sommer-Trüffel gemeint ist. Später ist uns jedoch aufgefallen, dass Frau Davidis in viele Suppen Scorzonerwurzeln hineingibt. Dies hat bei uns die Frage aufgeworfen, ob sie wirklich oft empfiehlt, teure Sommer-Trüffel in Suppen zu zerkochen. Nach einer weiteren Recherche glauben wir nun, dass sie mit Scorzonerwurzel Scorzonera hispanica bzw. Schwarzwurzel meint, welche sicherlich in einer Suppe angebrachter sind als Sommer-Trüffel.

Regular Expression-based

Conditional Random Field-based

Die New York Times (NYT) betreibt eine eigene Kochseite. Greene behauptet, dass sie mittels Linear-chain Conditional Random Fields (CRF) in der Lage sind „automatisch den unstrukturierten Text von Rezepten in strukturierte Daten umzuwandeln“ . Dies beinhaltet insbesondere das Extrahieren der Zutaten mit ihren Mengenangaben und Einheiten. Da diese Behauptung genau unserer Problemstellung entspricht, stellen wir zunächst die Idee von CRF vor und gehen anschließend auf die Implementierung von Greene ein.

CRF erklärt

CRF orakelt zu einem Vektor von Wörtern ein Vektor von Labels. Im Folgenden bezeichnen wir daher CRF auch als ein Orakel. Wenn wir dem Orakel z. B. den Vektor [Man, süße, mit, 2, EL, Zucker, .] geben, orakelt es uns idealerweise die Labels [OTHER, OTHER, OTHER, QUANTITY, UNIT, INGREDIENT, OTHER]. Wenn wir so ein Orakel hätten, würden wir unsere Rezepte in solche Wort-Vektoren aufspalten und dem Orakel übergeben. Aus der Antwort des Orakels könnten wir dann sofort die Zutaten mit Mengenangaben und Einheiten ablesen.

Jetzt stellt sich nur noch die Frage, woher man so ein Orakel bekommt. Folgend erläutern wir die Idee, wie so ein Orakel antrainiert werden kann. Eine detaillierte Einführung ist in zu finden. Wir fangen damit an, dass wir dem Orakel eine Reihe von Wort-Vektoren geben und ihm für diese bereits die passenden Antworten von Label-Vektoren mitgeben. Solch eine Menge von Wort- und zugehörenden Label-Vektoren werden auch Trainingsdaten genannt. Fragen wir es nun nach den Labels von einen dieser Wort-Vektoren, könnte es uns einfach den zugehörenden Label-Vektor orakeln.

Spannend ist die Frage, wie das Orakel Labels für Wort-Vektoren rät, von denen es die Lösung nicht kennt. Dafür leitet es zunächst aus den Trainingsdaten eine multivariate Wahrscheinlichkeits­verteilung \( p(X,Y) \) ab, die angibt, wie wahrscheinlich zu einem Wort-Vektor \( X \) ein Label-Vektor \( Y \) gehört. Das Orakel geht dabei von dem vereinfachten Modell aus, dass jedes Label \( y_i \in Y \) nur vom vorherigen Label \( y_{i-1} \in Y \) und dem entsprechenden Wort \( x_i \in X \) abhängt. Ist dies der Fall, kann \( p(X,Y) \) durch eine Formel der Form von Formel (1) beschrieben werden.

\begin{equation} \boldsymbol{ p(X,Y) = \prod_{t=1}^{\#X} p(y_t|y_{t-1}) * p(y_t|x_t) } \end{equation}

Wahrscheinlichkeiten der Form von (1) können immer in die Form von Formel (2) überführt werden.

\begin{align} mit\ \Theta_{i,j} \in \mathbb{R}^+,\ L = alle\ moeglichen\ Labels, \ W = alle\ moeglichen\ Woerter, \nonumber \\ X^*=alle\ moeglichen\ Woerter\mbox{-}Vektoren,\ Y^*=alle\ moeglichen\ Label\mbox{-}Vektoren, \nonumber \\ und\ Z = \sum_{X \in X^*}^{}\sum_{Y \in Y^*}^{}\prod_{t=1}^{\#X} exp(\sum_{i,j\in L}^{} \Theta_{i,j} * 1_{y_t=i} * 1_{y_{t-1}=j} + \sum_{i \in L}^{} \sum_{o \in W}^{} \mu_{i,o} * 1_{y_t=i} * 1_{x_t=o}), \nonumber \\ \boldsymbol{ p(X,Y) = \frac{1}{Z}\prod_{t=1}^{\#X} exp(\sum_{i,j \in L}^{} \Theta_{i,j} * 1_{y_t=i} * 1_{y_{t-1}=j} + \sum_{i \in L}^{} \sum_{o \in W}^{} \mu_{i,o} * 1_{y_t=i} * 1_{x_t=o}) } \end{align}

\( 1_{Bedingung} \) ist dabei eine Funktion, die genau dann Eins ist, wenn die Bedingung erfüllt ist und ansonsten Null. Je öfter \( y_t=i \) und \( y_{t-1}=j \) gemeinsam in der Verteilung vorkommen, desto größer wird \( \Theta_ {i,j} \) sein. Kommen \( y_t=i \) und \( y_{t-1}=j \) gar nicht gemeinsam vor, gilt \( \Theta_{i,j} * 1_{y_t=i} * 1_{y_{t-1}=j} = 0 \). Gleiches gilt für \( y_t=i \), \( x_t=o \) und \( \mu_{i,o} \). Die Thetas werden auch als Gewichte bezeichnet. \( Z \) bildet die Summe der Werte für alle möglichen Vorkommen von \( X \) und \( Y \). Nach der Division durch \( Z \) ist somit sichergestellt, dass Formel (2) zwischen \( 0 \) und \( 1 \) liegt, sowie dass die Summe über alle möglichen Wahrscheinlichkeiten \( 1 \) ist, wie es für eine Wahrscheinlichkeitsverteilung der Fall sein muss.

Durch eine Abbildung der Indizies \( i \), \( j \) und \( o \) auf \( k \) kann dies wiederum zu Formel (3) vereinfacht werden.

\begin{align} \boldsymbol{ p(X,Y) = \frac{1}{Z}\prod_{t=1}^{\#X} exp(\sum_{k=1}^{K} \Theta_{k} * f_k(y_t, y_{t-1}, x_t)) }, \\ mit\ Z = \sum_{X \in X^*}^{}\sum_{Y \in Y^*}^{}\prod_{t=1}^{\#X} exp(\sum_{k=1}^{K} \Theta_{k} * f_k(y_t, y_{t-1}, x_t)) \nonumber \end{align}

Wie in Formel (4) zu sehen ist, kann jede multivariate Wahrscheinlichkeit in eine bedingte Wahrscheinlichkeit umgerechnet werden.

\begin{equation} \boldsymbol{ p(Y|X) = \frac{p(X,Y)}{\sum_{Y'\in Y^*}^{}p(Y', X)} } \end{equation}

Eine nahe liegende Art zu Orakeln ist nun Formel (5). Nebenbei sei erwähnt, dass ein so antrainiertes Orkal als ein Hidden Markov Model (HMM) bezeichnet wird.

\begin{equation} \boldsymbol{ orakel(X)=argmax_Y(p(Y|X)) } \end{equation}

Aufgrund des vereinfachten Modells, dass jedes Label \( y_i \) nur vom vorherigen Label \( y_{i-1} \) und dem entsprechenden Wort \( x_i \) abhängt, ist Formel (1) nur eine Annäherung an \( p(X,Y) \) und somit sind auch alle weiteren Umformungen nur eine Annäherung. Ein CRF vereinfacht das Modell nun weiter, in dem es einige \( \Theta_{k} \) und entsprechende \( f_{k} \) im Model weglässt. Durch das Weglassen von vielen kleinen \( \Theta_{k} \) kann ein CRF die Berechnungszeit beschleunigen, wobei die berechnete Verteilung und somit das spätere Orakeln nur marginal verändert werden. Auch erlaubt ein CRF negative Werte für \( \Theta_{k} \). Der Intuition nach sagen diese aus, dass ein gemeinsames Vorkommen von \( X \) und \( Y \) sehr unwahrscheinlich ist und geben somit Strafpunkte für die \( argmax_Y \)-Orakel-Funktion. Des Weiteren können in einem CRF sogenannte custom feature functions \( f_{k'}(y_t, y_{t-1}, X) \) angegeben werden, die nicht nur vom entsprechenden Wort \( x_i \) sondern vom ganzen Wort-Vektor \( X \) abhängig sein können. Die \( \Theta_{k'} \) zu diesen custom feature functions werden so berechnet, dass beim Orakeln der Trainings-Vektoren \( X \) die entsprechenden Label-Vektoren \( Y \) möglichst genau geraten werden, unter der Annahme, dass das Ergebnis berechnet werden muss und nicht einfach nachgeschaut werden darf. Die Praxis zeigt, dass ein CRF mit guten custom feature functions besser orakelt als ein HMM. Typische custom feature functions wären z. B.:

• \( f_{k'_1}(y_t, y_{t-1}, X) = 1_{x_t\ ist\ ein\ Nomen} \)
• \( f_{k'_2}(y_t, y_{t-1}, X) = 1_{x_t\ ist\ in\ einem\ Domaenen-spezifischen\ Woerterbuch} \)
• \( f_{k'_3}(y_t, y_{t-1}, X) = 1_{x_t\ ist\ in\ einem\ Domaenen-spezifischen\ Woerterbuch\ und\ x_{t-1}\ ist\ ein\ Nomen} \)

Abschließend seien zu CRF noch eine überraschende und eine gute Bemerkung erwähnt. Die Überraschende ist folgende: Aufgrund der Vereinfachung des Models wie auch den custom feature functions ist es möglich, dass ein CRF ein Wort-Vektor, der in den Trainingsdaten enthalten war, falsch orakelt. Die gute Bemerkung ist, dass sich die erste Befürchtung eines Informatikers nicht bestätigt, dass die Funktion \( orakel(X)=argmax_Y(p(Y|X) \) in Laufzeit von \( O({\#L}^{\#X}) \) berechnet werden muss. Stattdessen kann sie durch dynamisches Programmieren in \( O({\#L}^2*{\#X}) \) berechnet werden.

Implementierung der NYT

Die Rezepte der Kochseite der NYT haben alle eine Zutatenliste. Jede Zeile der Zutatenliste ist in einer Datenbank abgespeichert, aufgespalten nach der Zutat, einer Mengenangabe, der Mengeneinheit und Anderem. In dieser Datenbank sind mehr als 130.000 solcher Einträge, welche alle als Trainingsdaten für das CRF genutzt werden können. Die Zutat erhält dabei das Label NAME, die Mengenangabe QTY und die Einheit UNIT. Nach dem IOB2-Format erhält das erste Wort eines Labels den Prefix B-. Folgende Wörter erhalten den Prefix I-. Als CRF-Bibliothek verwendet die NYT CRF++. Abb. 2 bis 4 zeigen alle von Greene in CRF++-Format angegebenen custom feature functions.

Diese CRF Implementierung berücksichtigt für ihre custom feature functions also nur die Position im Satz, die Länge des Satzes, ob ein Wort groß geschrieben wird und ob es eingeklammert ist. Bei einem Test mit 481 Rezepten orakelt dieses CRF 89% aller Zeilen einer Zutatenliste korrekt. testet nur 481 Rezepte, obwohl er über 130.000 zur Verfügung hat, da er keine Möglichkeit zur automatischen Auswertung gefunden hat. Wenn das CRF was anderes orakelt hat, als in der Datenbank stand, dann war manchmal das Orakelelte falsch, manchmal aber auch die manuell aufgebaute Datenbank und manchmal waren sogar beide falsch.

Dictionary- and rule-based

Die beiden unabhängigen Arbeiten von und kategorisieren wir als dictionary- and rule-based. Die Grundidee ist in Abb. 6 zu sehen.

möchte aus Rezepten die Zutaten extrahieren und herausfinden, wie diese verarbeitet werden. Zum Beispiel ob sie gekocht, oder gebacken werden. Nachdem er mit einem Wörterbuch von Zutaten und einem von Verarbeitungs-Verben die gesuchten Entities gefunden hat, muss er noch verbinden, welche Verarbeitungs-Verben zu welchen Zutaten gehören. Er hat dafür zwei unterschiedliche Ansätze:

sind an folgenden vier Fragen interessiert: Welche Lebensmittel passen zu welchem Anlass?, Welche Lebensmittel werden oft kombiniert?, Welche Lebensmittel können untereinander ausgetauscht werden? und Welche Lebensmittel sind Teil eines Gerichts. Um diese Fragen zu beantworten, extrahieren sie Informationen aus Wikipedia und dem Forum von Chefkoch.de. Sie arbeiten also mit rein textuellen Daten und können beispielsweise nicht auf der Struktur eines Rezeptes mit Zutatenliste aufbauen. Für uns relevant sind ihre Methoden Surface Patterns und Statistical Co-occurrence.

Das Ergebnis der Extraktion ist je eine Liste von Lebensmittel für jede der vier Fragen. Da eine Liste von Ergebnissen nicht passend mit Percision und Recall ausgewertet werden kann und die Evaluierung keine weiteren Erkenntnisse für diese Arbeit bringt, sei für die Evaluierung auf die originale Ausarbeitung verwiesen.