Lesk-Algorithmus

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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[1] bildet die Basis für verschiedene Weiterentwicklungen.[2]

Der Lesk-Algorithmus

[Bearbeiten | Quelltext bearbeiten]

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

Für jede der möglichen Bedeutungen B1(M), B2(M), ..., Bm(M) des Wortes M wird im Wörterbuch die Bedeutungserklärung nachgeschlagen. Sei D(Bi(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 M1, M2, ..., Mn nachgeschlagen. Die Menge der Wörter in der Bedeutungserklärung des Wortes Mi bezeichnen wir mit E(Mi). Wie zu verfahren ist, wenn Mi selbst mehrdeutig ist, wird weiter unten erklärt.

Der Grundgedanke des Lesk-Algorithmus besteht nun darin, dass unter den möglichen Bedeutungen B1(M), B2(M), ..., Bm(M) des Wortes M diejenige zu bevorzugen ist, für die die Mengen und die größte Schnittmenge aufweisen.

Es wird daher für jede Bedeutung Bi(M) des Wortes M, also der Lesk-Score berechnet als

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

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

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:

Damit haben wir:

  • das zu untersuchende Wort: M = Maus
  • den Kontext: M1=zur, M2=Eingabe, M3=von, M4=Daten, M5=an, M6=meinem, M7=Computer, M8=nutze, M9=ich, M10=lieber, M11=meine, M12=Tastatur, M13=als, M14=die
  • die beiden zu unterscheidenden Bedeutungen B1(Maus) und B2(Maus),
  • die Wörter in den Erklärungstexten für B1(Maus) und B2(Maus):
    • D(B1(Maus)) = {speziell, ein, Nagetier, ...},
    • D(B2(Maus)) = {Eingabegerät, für, Computer},
  • die Wörter in den Erklärungstexten für die Wörter des Kontexts, zum Beispiel:
    • E(M7)=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(Mi) die Stoppwörter wie „ein“ oder „der“ entfernt haben (von denen kein Informationsgewinn zu erwarten ist), arbeiten wir mit den bereinigten Mengen:

  • Kontext: M1=Eingabe, M2=Daten, M3=meinem, M4=Computer, M5=nutze, M6=lieber, M7=meine, M8=Tastatur
  • D(B1(Maus)) = {speziell, Nagetier, Überfamilie, Mäuseartigen, meistens, Familie, Langschwanzmäuse, Muridae, Hausmaus, Gattung, Mäuse},
  • D(B2(Maus)) = {Eingabegerät, Computer},
  • E(M4)=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 enthalten sind (der Lesk-Score ist somit 0), während für die Bedeutung der Maus als Computer-Eingabegerät die Menge aus den Wörtern „Computer“ und „Daten“ besteht, die sowohl im Kontext als auch in der Worterklärung E(M4)=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.[1]

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 %.[1]

Kritik und andere Lesk-basierte Methoden

[Bearbeiten | Quelltext bearbeiten]

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.[4]

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

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. a b c Automatic sense disambiguation using machine readable dictionaries | Proceedings of the 5th annual international conference on Systems documentation. Abgerufen am 2. Juni 2020 (englisch).
  2. E. Agirre, P. Edmonds (Hrsg.): Word Sense Disambiguation: Algorithms and Applications (= Text, Speech and Language Technology). Springer Netherlands, 2007, ISBN 978-1-4020-4808-1 (springer.com [abgerufen am 12. Juli 2020]).
  3. K.-U. Carsensen, Ch. Ebert, C. Ebert, S. Jekat, R. Klabunde, H. Langer (Hrsg.): Computerlinguistik und Sprachtechnologie: Eine Einführung. 3. Auflage. Springer Spektrum, 2010, ISBN 978-3-8274-2023-7 (springer.com [abgerufen am 12. Juli 2020]).
  4. A. F. Gelbukh, G. O. Sidorov: Methode zur automatischen Auflösung der Mehrdeutigkeit von Wortbedeutungen. Abgerufen am 2. Juni 2020.
  5. Roberto Navigli. Word Sense Disambiguation: A Survey. ACM Computing Surveys, 41(2), 2009, pp. 1–69. Abgerufen am 2. Juni 2020 (englisch)