Algorytm Leska - Lesk algorithm

Algorytm Lesk to klasyczny algorytm sens wyrazu dezambiguacji wprowadzonym przez Michaela E. Lesku w 1986 roku.

Przegląd

Algorytm Leska opiera się na założeniu, że słowa w danym „sąsiedztwie” (fragmencie tekstu) będą miały wspólny temat. Uproszczona wersja algorytmu Leska polega na porównaniu słownikowej definicji słowa niejednoznacznego z terminami zawartymi w jego sąsiedztwie. Wersje zostały przystosowane do korzystania z WordNet . Implementacja może wyglądać tak:

  1. dla każdego sensu ujednoznacznionego słowa należy policzyć liczbę słów, które znajdują się zarówno w sąsiedztwie tego słowa, jak i w słownikowej definicji tego sensu
  2. zmysł, który ma być wybrany, to ten, który ma największą liczbę z tej liczby.

Często używanym przykładem ilustrującym ten algorytm jest kontekst „szyszka”. Stosowane są następujące definicje słownikowe: 

PINE 
1. kinds of evergreen tree with needle-shaped leaves
2. waste away through sorrow or illness

CONE 
1. solid body which narrows to a point
2. something of this shape whether solid or hollow
3. fruit of certain evergreen trees

Jak widać, najlepszym skrzyżowaniem jest Sosna #1 ⋂ Stożek #3 = 2.

Uproszczony algorytm Leska

W algorytmie uproszczonym Lesk poprawne znaczenie każdego słowa w danym kontekście ustalane jest indywidualnie poprzez zlokalizowanie sensu, który najbardziej pokrywa się między jego słownikową definicją a danym kontekstem. Zamiast równoczesnego określania znaczeń wszystkich słów w danym kontekście, podejście to traktuje każde słowo indywidualnie, niezależnie od znaczenia innych słów występujących w tym samym kontekście.

„Ocena porównawcza przeprowadzona przez Vasilescu i in. (2004) wykazała, że ​​uproszczony algorytm Leska może znacznie przewyższać oryginalną definicję algorytmu, zarówno pod względem precyzji, jak i wydajności. dane słów, mierzą precyzję 58% przy użyciu uproszczonego algorytmu Leska w porównaniu z zaledwie 42% w ramach oryginalnego algorytmu.

Uwaga: Vasilescu i in. implementacja uwzględnia strategię back-off dla słów nieobjętych algorytmem, składającą się z najczęstszego sensu zdefiniowanego w WordNet. Oznacza to, że słowa, dla których wszystkie możliwe znaczenia prowadzą do zera, pokrywają się z bieżącym kontekstem lub innymi definicjami słów, są domyślnie przypisane sensu numer jeden w WordNet”.

Uproszczony algorytm LESK z inteligentnym domyślnym znaczeniem słów (Vasilescu i in., 2004)

funkcja UPROSZCZONE LESK( słowo, zdanie ) zwraca najlepsze znaczenie słowa
najlepszy sens <- najczęstszy sens słowa
max-nakładanie <- 0
kontekst <- zestaw słów w zdaniu
za każdym sensie w znaczeniach słowa zrobienia
podpis <- zbiór wyrazów w glosie i przykłady sensu
nakładanie się <- COMPUTEOVERLAP ( podpis,kontekst )
jeśli nakładają się > max-nakładanie wtedy
max-nakładanie <- nakładanie
najlepszy sens <- sens

koniec zwrotu ( najlepszy sens )

Funkcja COMPUTEOVERLAP zwraca liczbę słów wspólnych dla dwóch zestawów, ignorując słowa funkcyjne lub inne słowa z listy zatrzymania. Oryginalny algorytm Leska definiuje kontekst w bardziej złożony sposób.

Krytyka i inne metody Leska

Niestety podejście Leska jest bardzo wrażliwe na dokładne sformułowanie definicji, więc brak określonego słowa może radykalnie zmienić wyniki. Co więcej, algorytm określa nakładanie się tylko między glosami rozważanych zmysłów. Jest to istotne ograniczenie, ponieważ glosy słownikowe są zwykle dość krótkie i nie zawierają wystarczającego słownictwa, aby odnieść się do subtelnych rozróżnień sensu.

Pojawiło się wiele pracy, oferując różne modyfikacje tego algorytmu. Prace te wykorzystują do analizy inne zasoby (tezaurusy, słowniki synonimów czy modele morfologiczno-syntaktyczne): np. mogą wykorzystywać takie informacje jak synonimy, różne pochodne, czy słowa z definicji słów z definicji.

Istnieje wiele opracowań dotyczących Leska i jego rozszerzeń:

  • Wilks i Stevenson, 1998, 1999;
  • Mahesh i in., 1997;
  • Cowie i wsp., 1992;
  • Yarowsky, 1992;
  • Pook i Catlett, 1988;
  • Kilgarriff i Rosensweig, 2000;
  • Kwong, 2001;
  • Nastase i Szpakowicz, 2001;
  • Gelbuch i Sidorow, 2004.

Warianty Leska

  • Oryginał Lesk (Lesk, 1986)
  • Adapted/Extended Lesk (Banerjee i Pederson, 2002/2003): W algorytmie adaptive lesk tworzony jest wektor słowa odpowiadający każdemu słowu treści w słowniku wordnet. Łączenie glos pokrewnych pojęć w WordNet może być wykorzystane do rozszerzenia tego wektora. Wektor zawiera liczniki współwystępowania słów współwystępujących z w w dużym korpusie. Dodanie wszystkich wektorów słów dla wszystkich słów treści w jego połysku tworzy wektor połysku g dla pojęcia. Pokrewieństwo określa się przez porównanie wektora połysku przy użyciu miary podobieństwa kosinusowego .

Zobacz też

Bibliografia