Lesk-Algorithmus

Der Lesk-Algorithmus ist ein Algorithmus aus der Computerlinguistik, den Michael E. Lesk 1986 zur Begriffsklärung für sprachlich mehrdeutige Begriffe entwickelt hat (Wortsinndisambiguierung).

Wörter, die für mehrere Begriffe stehen (Homonyme), stellen ein großes Problem in vielen Bereichen der maschinellen Sprachverarbeitung dar. Die Idee des Lesk-Algorithmus besteht darin, die Wörterbuchdefinition für verschiedene mögliche Bedeutungen eines Wortes zu nutzen, um die im untersuchten Text passende Bedeutung herauszufinden. Dazu wird ein maschinenlesbares Wörterbuch benötigt, das neben den Wörtern Bedeutungserklärungen enthält.

Der von Lesk vorgeschlagene Algorithmus bildet die Basis für verschiedene Weiterentwicklungen.

Der Lesk-Algorithmus

Der Algorithmus betrachtet ein Wort M mitsamt seinem Kontext, zum Beispiel in einem Satz, der neben M selbst noch die Wörter M₁, M₂, ..., M_n enthält.

Für jede der möglichen Bedeutungen B₁(M), B₂(M), ..., B_m(M) des Wortes M wird im Wörterbuch die Bedeutungserklärung nachgeschlagen. Sei D(B_i(M)) die Menge der Wörter, die im Wörterbuch in der Bedeutungserklärung der i-ten Bedeutung des Wortes M verwendet wurden. Gleichermaßen werden die Bedeutungserklärungen der im Kontext von M stehenden Wörter M₁, M₂, ..., M_n nachgeschlagen. Die Menge der Wörter in der Bedeutungserklärung des Wortes M_i bezeichnen wir mit E(M_i). Wie zu verfahren ist, wenn M_i selbst mehrdeutig ist, wird weiter unten erklärt.

Der Grundgedanke des Lesk-Algorithmus besteht nun darin, dass unter den möglichen Bedeutungen B₁(M), B₂(M), ..., B_m(M) des Wortes M diejenige zu bevorzugen ist, für die die Mengen $D(B_{i}(M))$ und $M_{i}\cup E(M_{i})$ die größte Schnittmenge aufweisen.

Es wird daher für jede Bedeutung B_i(M) des Wortes M, also $\forall i=1,\dots ,m$ der Lesk-Score berechnet als

$LeskScore(B_{i}(M))={\Bigl |}D(B_{i}(M))\cap {\Bigl (}\bigcup _{i=1}^{n}{\bigl (}M_{i}\cup E(M_{i}){\bigr )}{\Bigr )}{\Bigr |}$

Sollte es für eines der Wörter M_i im Kontext von M selbst mehrdeutig sein, wird unter den möglichen Mengen für $E(M_{i})$ diejenige ausgewählt, die bei der Berechnung des Lesk-Scores den größten Wert liefert.

Beispiel

Der Algorithmus soll mit einem Beispiel illustriert werden (angelehnt an ):

Im Satz „Zur Eingabe von Daten an meinem Computer nutze ich lieber meine Tastatur als die Maus.“ soll die Bedeutung des Wortes „Maus“ ermittelt werden. Wikipedia (das hier als elektronisches Wörterbuch benutzt werden soll) kennt mehrere Bedeutungen für dieses Wort. Zur Vereinfachung wollen wir uns auf nur zwei Bedeutungen (das Nagetier und die Computermaus) beschränken. Die dazugehörigen Erklärungen unter dem Stichwort Maus sind:

• Maus (Computer), Eingabegerät für Computer
• speziell ein Nagetier aus der Überfamilie der Mäuseartigen, meistens aus der Familie der Langschwanzmäuse (Muridae), speziell die Hausmaus aus der Gattung der Mäuse (Mus)

Damit haben wir:

• das zu untersuchende Wort: M = Maus
• den Kontext: M₁=zur, M₂=Eingabe, M₃=von, M₄=Daten, M₅=an, M₆=meinem, M₇=Computer, M₈=nutze, M₉=ich, M₁₀=lieber, M₁₁=meine, M₁₂=Tastatur, M₁₃=als, M₁₄=die
• die beiden zu unterscheidenden Bedeutungen B₁(Maus) und B₂(Maus),
• die Wörter in den Erklärungstexten für B₁(Maus) und B₂(Maus):
  • D(B₁(Maus)) = {speziell, ein, Nagetier, ...},
  • D(B₂(Maus)) = {Eingabegerät, für, Computer},
• die Wörter in den Erklärungstexten für die Wörter des Kontexts, zum Beispiel:
  • E(M₇)=E(Computer)= {Ein, Computer, oder, Rechner, ist, ein, Gerät, das, mittels, programmierbarer, Rechenvorschriften, Daten, verarbeitet} (zu finden im Stichwort Computer),

Nachdem wir aus den Mengen D(B_i(Maus)) und E(M_i) die Stoppwörter wie „ein“ oder „der“ entfernt haben (von denen kein Informationsgewinn zu erwarten ist), arbeiten wir mit den bereinigten Mengen:

• Kontext: M₁=Eingabe, M₂=Daten, M₃=meinem, M₄=Computer, M₅=nutze, M₆=lieber, M₇=meine, M₈=Tastatur
• D(B₁(Maus)) = {speziell, Nagetier, Überfamilie, Mäuseartigen, meistens, Familie, Langschwanzmäuse, Muridae, Hausmaus, Gattung, Mäuse},
• D(B₂(Maus)) = {Eingabegerät, Computer},
• E(M₄)=E(Computer)= {Computer, Rechner, Gerät, mittels, programmierbarer, Rechenvorschriften, Daten, verarbeitet},

Bei der Berechnung der Lesk-Score stellen wir fest, dass für die Bedeutung der Maus als Nagetier keine Wörter in der Schnittmenge $D(B_{1}(Maus))\cap {\Bigl (}\bigcup _{i=1}^{n}{\bigl (}M_{i}\cup E(M_{i}){\bigr )}{\Bigr )}$ enthalten sind (der Lesk-Score ist somit 0), während für die Bedeutung der Maus als Computer-Eingabegerät die Menge $D(B_{2}(Maus))\cap {\Bigl (}\bigcup _{i=1}^{n}{\bigl (}M_{i}\cup E(M_{i}){\bigr )}{\Bigr )}$ aus den Wörtern „Computer“ und „Daten“ besteht, die sowohl im Kontext als auch in der Worterklärung E(M₄)=E(Computer) vorkommen (der Lesk-Score ist also 2). Damit ist es wahrscheinlich, dass im vorliegenden Satz das Wort „Maus“ die Bedeutung als Computer-Eingabegerät hat.

In seiner Originalarbeit nutzte Lesk das „Oxford Advanced Learner's Dictionary of Current English“ (OALDCE). Dieses umfasst ca. 21.000 Stichwörter und ca. 36.000 verschiedene Bedeutungen.

Laut Lesk ergab die Erfolgsrate seines Programms nach einigen kurzen Experimenten (Kurzproben des Romans „Stolz und Vorurteil“ und ein zugehöriger Pressebeitrag) eine Genauigkeit von 50 bis 70 %.

Kritik und andere Lesk-basierte Methoden

Lesks Ansatz ist sehr abhängig von exakten Formulierungen der betrachteten Definitionen. Schon das Fehlen eines einzelnen Wortes kann radikale Veränderungen im Ergebnis nach sich ziehen. Viele Studien über verschiedene modifizierte Versionen des Algorithmus sind bereits veröffentlicht worden, die oftmals verschiedene Ressourcen für ihre Analyse verwenden. Evaluierungen können somit Differenzen zu anderen Ergebnissen aufweisen.

Weitere Studien zu Lesks Algorithmus und dessen Erweiterungen sind unter dem Einzelnachweis zu finden.