Метод Леска (Bymk; Lyvtg)

Алгоритм Леска — классический алгоритм разрешения лексической многозначности, основанный на знаниях, предложенный Майклом Леском в 1986 году.

Описание

Майкл Леск попытался самостоятельно решить задачу сопоставления слова и его смысла в английском языке с помощью машиночитаемых словарей. Идея метода заключалась в поиске значения слова в списке словарных определений с учетом контекста, где это слово использовано. Основным критерием для выбора значения послужило следующее правило: заложенный в этом определении смысл должен был частично совпадать со смыслом значений соседних слов в контексте.

Принцип работы алгоритма

Наглядное представление работы алгоритма Леска

1. Отделение контекста для рассматриваемого слова — не более 10 ближайших по расположению слов.
2. Поиск всех определений в словаре (любом другом подобном источнике знаний) для рассматриваемого слова.
3. Поиск слов из контекста в каждом найденном определении. Если какое-либо слово из контекста присутствует в определении, тогда этому определению дается балл (повышается процент верности определения для данного контекста).
4. В качестве наиболее вероятного значения выбирается то, для которого такое пересечение оказалось больше.

Пример работы алгоритма

В качестве примера можно рассмотреть задачу — определить значение слова «кошка» в тексте «в Китае выведены новые породы кошек». Предположим, что словарь выдаст два определения для слова «кошка»:

1. «кошка»₁ — домашнее животное из породы кошачьих;
2. «кошка»₂ — предмет альпинистского снаряжения.

Алгоритм покажет, что с определением (1) у этого текста одно общее слово — «породы», а с определением (2) ни одного. Следовательно, алгоритм Леска выберет значение «кошка»₁.

Примечания автора метода

• В качестве слов Леск рассматривал цепочки из букв английского алфавита.
• При выборе 4, 6 и 8 слов для контекста результаты работы алгоритма мало отличались.
• Автор в своей работе в качестве источника знаний использовал Оксфордские словари английского языка.

Преимущества алгоритма

• Независимость алгоритма от синтаксиса. Это позволяет применять алгоритм в качестве дополнения к методам, основанным на синтаксическом анализе.
• Независимость алгоритма от лексического значения слова. Опираясь на контекст, алгоритм может сопоставлять слову его переносные значения.

Недостатки алгоритма

В алгоритме Леска для поиска значений новых слов не используются уже найденные определения. Алгоритм смотрит на каждое слово в отдельности, ищет для него значение, при выяснении корректного смысла одного слова, алгоритм проделывал те же действия со следующим словом.

Модификации алгоритма

Существует большое количество работ, предлагающих использование модификации алгоритма Леска. Эти исследования основаны на идее использования различных словарей (тезаурусы, словари синонимов и т. д.) или моделей (морфологические, синтаксические и т. д.) совместно. Все эти работы ориентированы на обработку различных не словарных текстов, и ни одна не использует в качестве материала для обработки именно толковый словарь. Кроме того, практически всегда процесс ограничивается небольшим количеством экспериментов и не производится обработка достаточно больших массивов данных.

Улучшение метода

В качестве возможных путей улучшения исходного алгоритма Леска используется привлечение дополнительной информации о сходстве слов и учет значимости совпадений для различных слов.

В качестве первого примера модифицированного метода Леска можно привести вариант алгоритма, где в качестве дополнительной информации используется словарь синонимов, словообразовательная морфологическая модель, а также привлекаются толкования слов, входящих в исходное толкование.

Важным моментом является то, что алгоритм разрешения неоднозначности значений слов применяется к толкованиям, берущимся из словаря, что существенно упрощает задачу по сравнению с применением алгоритма к обычным текстам, по следующим причинам:

• все слова толкования заведомо связаны с заглавным словом, поскольку входят в его определение;
• следовательно, не возникает проблема выбора размера окна контекста, в котором надо рассматривать слова, а используется все определение целиком;
• разрешение неоднозначности частей речи (что обычно является первым шагом подобных алгоритмов) упрощено, поскольку толкования являются структурированными и, следовательно, части речи слов на определенных местах предсказуемы; кроме того, помогает информация о грамматическом классе заглавного слова.

В качестве второго примера модифицированного метода Леска можно привести вариант алгоритма, основанный на двух гипотезах. Первая гипотеза заключается в том, что со слов, встречающихся в предложении, можно снять неоднозначность, присвоив им смысл, который наиболее близок к соседним словам. Это следует из интуитивного понятия того, что слова, встречающиеся вместе в одном предложении, обязательно каким-то образом связаны между собой, так как, согласуясь друг с другом, они передают некоторый смысл. Вторая гипотеза состоит в том, что связанные между собой смыслы можно идентифицировать, находя в их определениях слова, которые встречаются в толкованиях обоих слов. Эту гипотезу также можно обосновать с помощью интуитивного понятия, а именно того, что слова, которые связаны по смыслу, могут быть определены с одними и теми же терминов, а также могут ссылаться друг на друга в своих определениях.

В качестве примера можно рассмотреть два значения слова «калейдоскоп»:

1. оптический прибор — трубка с зеркальными пластинками и цветными стеклышками, при поворачивании складывающимися в разнообразные узоры;
2. быстрая смена разнообразных явлений.

И текст «Красивые цветные узоры калейдоскопа завораживают и взрослых, и детей». С первым определением у этого текста два общих слова, а со вторым — ни одного. Следовательно, алгоритм Леска выберет первое значение.

Критика алгоритма и другие схожие методы

К сожалению, подход Леска очень чувствителен к точной формулировке определений, таким образом, отсутствие определенного слова может радикально изменить результаты. Ещё одним минусом является то, что алгоритм определяет перекрытия только среди толкований смыслов, которые рассматриваются. Это существенное ограничение, которое состоит в том, что толкования словаря имеют тенденцию быть довольно короткими и не обеспечивают достаточный словарь, чтобы показывать разницу между схожими по смыслу определениями.

В последнее время появилось большое количество работ, предлагающих использовать модификации алгоритма Леска. В этих работах выдвигаются идеи, связанные с дополнительным использованием различных словарей (тезаурусы, словари синонимов) или моделей (морфологические, синтаксические и т. п.), см., например:

Относительно алгоритма Леска есть много исследований и расширений:

• Квонг (Kwong), 2001 ;
• Нэстасе и Шпакович (Nastase and Szpakowicz), 2001 ;
• Уилкс и Стивенсон (Wilks and Stevenson), 1998, 1999 ;
• Махеш и др, (Mahesh), 1997;
• Коуи и др., (Cowie), 1992 ;
• Яровски (Yarowsky), 1992 ;
• Пук и Катлет (Pook and Catlett), 1988 ;
• Калгриф и Розенцвейг (Kilgarriff & Rosensweig), 2000 ;
• Александр Гельбух, Григорий Сидоров, 2004 .

Точность метода

Относительно больших экспериментов на проверку этого метода не проводилось, кроме как на корпусе книги «Гордость и предубеждение» и газеты Associated Press. Результат варьировался от 50 % до 70 %.

Литература

• Lesk, Michael. Automatic Sense Disambiguation Using Machine Readable Dictionaries: How to Tell a Pine Cone from an Ice Cream Cone // Proceedings of the 5th Annual International Conference on Systems Documentation. — 1986. — С. 24—26.
• Agirre, E. and Edmonds, P.G. Word Sense Disambiguation: Algorithms and Applications. — Springer, 2007. — ISBN 9781402048098.
• Гельбух А. Ф., Сидоров Г. О. Метод автоматического разрешения неоднозначности значений слов в словарных толкованиях // Научно-техническая информация (НТИ),серия 2, Информационные процессы и системы : журнал. — М.: ВИНИТИ РАН, 2004. — № 3. — С. 10—15. — ISSN 0548-0027.

• Kwong O.I. Forming an Integrated Lexical Resource for Word Sense Disambiguation (англ.). — 2001.

• Nastase V. and Szpakowicz S. Unifying Semantic Relations Across Syntactic Levels (англ.). — Ottawa, Canada: School of Information Technology and Engineering University of Ottawa, 2001.

• Wilks, Y., Stevenson M. Word sense disambiguation using optimised combinations of knowledge sources (англ.) // Proceedings of ACL 36/Coling 17, Volume 2. — 1998. — P. 1398—1402.

• Wilks, Y., Stevenson M. Combining weak knowledge sources for sense disambiguation (англ.) // Proceedings of IJCAI-99. — 1999. — P. 884—889.

• Cowie J., Guthrie L., Guthrie G. Lexical disambiguation using simulated annealing (англ.) // COLING '92 Proceedings of the 14th conference on Computational linguistics - Volume 1. — 1992. — P. 359—365.

• Yarowksy D. Word-sense disambiguation using statistical models of Roget's categories trained on large corpora (англ.) // Proceeding Coling'92 Proceedings of the 14th conference on Computational linguistics, Volume 2. — Nante, France, 1992. — P. 454—460.

• Pook S. L., Catlett J. Making sense out of searching (англ.). — Sydney, 1988.

• Kilgarriff A., Rosenzweig J. Framework and Results for English SENSEVAL (англ.) // Computers and the Humanities : журнал. — Kluwer Academic Publishers, 2000. — No. 34. — P. 15—48. — ISSN 1572-8412.