ПРОГРАММИРОВАНИЕ, 2010, No 1, с. 16-28
ТЕОРЕТИЧЕСКИЕ ВОПРОСЫ ПРОГРАММИРОВАНИЯ
УДК 004.92+004.94
АВТОМАТИЧЕСКОЕ РАЗРЕШЕНИЕ ЛЕКСИЧЕСКОЙ МНОГОЗНАЧНОСТИ ТЕРМИНОВ НА ОСНОВЕ СЕТЕЙ ДОКУМЕНТОВ*
© 2010 г. Д. Ю. Турдаков**, С. Д. Кузнецов***
** Факультет вычислительной математики и кибернетики МГУ им. М.В. Ломоносова 119992 Москва, Воробьевы горы ***Институт системного программирования РАН 109004 Москва, ул. Солженицына, 25 E-mail: turdakov@ispras.ru, kuzloc@ispras.ru Поступила в редакцию 17.02.2009 г.
В данной статье приводится обзор работ по разрешению лексической многозначности и описывается метод, используемый в системе Texterra [1] и основанный на вычислении семантической близости концепций Википедии. Также дается сравнение существующих и предложенного методов устранения лексической многозначности в различных коллекциях документов.
1. ВВЕДЕНИЕ
1.1. Задача устранения лексической многозначности
В связи с ростом Интернета и объемов информации, которую приходится воспринимать человеку, особую актуальность приобрели системы автоматической обработки и анализа текстов. При создании такой системы разработчик сталкивается с проблемами из области компьютерной лингвистики1. И хотя активные разработки в этой области ведутся уже более 50 лет, некоторые задачи все еще остаются нерешенными. Одна из таких задач - разрешение лексической многозначности.
Задача разрешения лексической многозначности (word sense disambiguation) возникла в 50-х годах прошлого века в качестве подзадачи машинного перевода. С тех пор исследователи
* Эта работа частично поддержана грантами РФФИ 08-07-00195 и 08-07-12010.
1В специальной литературе иногда делают различие между терминами "компьютерная лингвистика" и "обработка естественного языка", здесь имеется в виду наиболее широкое понятие, включающее оба термина.
предложили огромное количество методов решения этой задачи, однако она остается более чем актуальной и по сей день. Условно можно выделить три этапа развития методов устранения лексической многозначности. С 50-х по 80-е года были разработаны основные подходы, однако из-за отсутствия хороших машинных словарей и баз знаний в этот период были созданы только "игрушечные" системы, покрывающие лишь крошечную часть языка. Следующий этап, пик которого пришелся на 90-е годы, был обусловлен вручную созданными крупномасштабными базами знаний, такими как WordNet [2] и CyC [3], и сбалансированными корпусами документов (Brown [4], Penn TreeBank [5]). Алгоритмы, разработанные в этот период, использовали структуру баз знаний или обучались на общепризнанных корпусах. Исследователи получили хорошие результаты, однако сложность ручного создания и поддержки в актуальном состоянии больших структур ограничила область применения этих алгоритмов. В начале 21-го века исследователей в области обработки естественного языка заинтересовала возможность использования сетей документов, таких, как WWW и Wikipedia, связан-
АВТОМАТИЧЕСКОЕ РАЗРЕШЕНИЕ ЛЕКСИЧЕСКОЙ МНОГОЗНАЧНОСТИ ТЕРМИНОВ
17
ных гиперссылками и созданных огромным числом независимых пользователей. Большим преимуществом таких сетей является то, что пользователи Интернета поддерживают их всегда в актуальном состоянии, а их документы описывают детально все области человеческой жизнедеятельности. Структура таких сетей отличается от созданных экспертами в 90-х годах баз знаний, что влечет за собой необходимость разработки новых моделей и алгоритмов.
Разрешение многозначности - это задача выбора значения многозначного слова или фразы из множества его значений. Исследователи разделили эту задачу на две различающихся подзадачи: морфосинтаксическую многозначность (значения относятся к разным частям речи, например, "look" - существительное "взгляд" или глагол "смотреть"), которая дополняет лексико-семантическую многозначность (значения относятся к одной части речи и различаются только смыслу, например "platform" -железнодорожная или компьютерная платформа). В отличие от задачи определения части речи, для которой существуют методы, показывающие высокую точность 98%) [6], автоматическое устранение лексико-семантической многозначности представляет собой намного более сложную задачу, поиски решения которой ведутся до сих пор.
Из названия задачи разрешения лексико-се-мантической многозначности следует, что в ней можно выделить подзадачи разрешения лексической и семантической многозначности. Под семантической многозначностью понимается возможность использования слова в переносном значении (лиса как обозначение хитрого человека). Большая часть методов разрешения лексической многозначности может применяться и для разрешения семантической многозначности, поэтому в литературе часто используют термин "лексическая многозначность" для обозначения обоих явлений.
Задача разрешения лексической многозначности включает в себя два аспекта:
1) фиксирование всех различных значений для каждого слова, относящегося к тексту;
2) определение способа выбора подходящего значения для каждого экземпляра слова.
Существуют два основных подхода к определению списка значений слов [7]. Большинство ранних работ опирается на предопределенные значения: списки слов, найденные в словарях, переводы на иностранные языки и т. п. Вторым подходом является анализ способов употребления слов в различных источниках и выделение значений на основе этого анализа. Однако до сих пор ведутся споры о том, что является значением слова.
Алгоритмы для выбора подходящего значения используют два источника информации: контекст слова - информацию, содержащуюся в тексте, в котором данное слово встретилось, -и внешние источники, такие, как словари и базы знаний. Современные методы можно разделить на два класса: методы, основанные на обучении по размеченным корпусам, и методы, основанные на внешних источниках знаний (тезаурусы, машинно-ориентированные словари, лексиконы). Хороший обзор алгоритмов можно найти в [7, 8], краткий обзор современных методов приведен во втором разделе статьи.
Еще одной важной проблемой является оценка методов и их сравнение. Так как разрешение многозначности является промежуточной задачей, существуют два способа оценки: in vitro -насколько хорошо работают методы сами по себе - и in vivo - как разрешение многозначности улучшает работу системы в целом. Для оценивания самих методов обычно используют два коэффициента: точность и полноту. Точность - это число слов, размеченных правильно, по отношению к числу всех слов, обработанных системой. Полнота - число слов, размеченных правильно, по отношению к числу слов в тестовом множестве. Также часто вводят F-меру, значением которой является среднее гармоническое между полнотой и точностью.
Для сравнения методов разрешения многозначности английских слов были разработаны тестовые коллекции и проводятся конференции Senseval-1,2,3 и Semeval [9]. В тестовых коллекциях используются заранее определенные наборы значений многозначных слов, которые бе-
рутся из словаря WordNet [2], что накладывает ограничение на возможность использования этих коллекций. Так, методы, использующие словарь Википедии, нельзя напрямую сравнить с методами, использующими словарь WordNet, так как количество значений слов в Википе-дии намного превосходит аналогичное число в WordNet (таблица 1). В работе [10] авторы смогли отобразить используемые значения на словарь WordNet, однако в дальнейшем (в работе [11]) отказались от такой процедуры. Это связано с тем, что Википедия растет и изменяется очень быстро, а объем ее словаря на порядок превосходит словарь WordNet. Кроме того, если значения слов находятся путем анализа употребления слов в текстах, то для оценки методов можно использовать только тестовые коллекции, созданные специально для оценки этого метода.
В данной статье описывается метод разрешения многозначности, основанный на вычислении семантической близости концепций Википедии. В следующем подразделе будет введено понятие сети документов, далее будет приведен обзор структуры Википедии, который необходим для описания разработанного метода. Во втором разделе будет дан обзор наиболее близких методов устранения многозначности. Далее будет описан разработанный метод, и будут приведены оценки его работы. Все эксперименты проводились на снимке англоязычной Википедии, полученном в июле 2008 года.
1.2. Сети документов
Прежде чем перейти к обзору структуры Ви-кипедии, мы введем понятие сети документов. Сеть документов (document network [12]) - это частный случай безмасштабного графа (scale-free graph [13]), обладающий дополнительными свойствами. Так же, как и у безмасштабных графов, распределение степеней вершин подчинено степенному закону, что означает присутствие узлов с очень большой степенью по сравнению со средним значением степеней и длинного "хвоста" из вершин с малой степенью. Другие не менее важные свойства сетей документов - высокий коэффициент кластеризации (вероятность
того, что между двумя документами существует прямая ссылка, при условии, что они соединены цепью длиной 2) и малый диаметр [14]. Эти свойства возникают из-за того, что документы с похожим содержимым имеют тенденцию ссылаться друг на друга [12], образуя, тем самым, структуру с высоким коэффициентом кластеризации. Примерами сетей документов могут служить Веб и Википедия. Основываясь на этих свойствах, мы разработали эффективный метод вычисления семантической близости концепций Википедии [15], который будет вкратце описан в третьем разделе.
1.3. Википедия
Узким местом методов статистических алгоритмов всегда была нехватка данных для тренировки. Не удивительно, что исследователи обратили внимание на такие коллекции документов, как Web и Wikipedia. Было предложено несколько подходов по использованию Web как корпуса для методов компьютерной лингвистики [16]. Однако в данное время большей популярностью пользуется Википедия, так как она обладает более четкой структурой и проще поддается машинной обработке.
Википедия - это открытая энциклопедия, создающаяся пользователями Веба. Сейчас Ви-кипедия содержит более 3 млн. статей, не считая специальных страниц. Граф Ви
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.