автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Методы и программные средства разрешения лексической многозначности терминов на основе сетей документов

Московский государственный университет имени М. В. Ломоносова

На правах рукописи ---

Турдаков Денис Юрьевич

Методы и программные средства разрешения лексической многозначности терминов на основе сетей документов

05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

1 "

Москва - 2010

003492491

Работа выполнена на кафедре системного программирования факультета вычислительной математики и кибернетики Московского государственного университета имени М. В, Ломоносова.

Научный руководитель: доктор технических наук,

профессор

Кузнецов Сергей Дмитриевич. Официальные оппоненты: доктор физико-математических наук,

профессор

Соловьев Валерий Дмитриевич;

кандидат физико-математических наук, заведующий лабораторией Доброе Борис Викторович. Ведущая организация: Санкт-Петербургский государственный

университет

Защита состоится «5» марта 2010 года в 11 часов на заседании диссертационного совета Д 501.001.Ц Московского государственного университета имени М.В. Ломоносова по адресу: 119991, ГСП-1, Москва, Ленинские горы, МГУ имени М.В.Ломоносова, 2-й учебный корпус, факультет ВМК, ауд. 685.

С диссертацией можно ознакомиться в библиотеке факультета ВМК МГУ. С текстом автореферата можно ознакомиться на официальном сайте ВМК МГУ http://cs.msu.ru в разделе «Наука» — «Работа диссертационных советов» — «Д 501.001.44»

Автореферат разослан «5» февраля 2010 г. Ученый секретарь диссертационного совета

профессор (рллК^ Н.П. Трифонов

Общая характеристика работы

Актуальность темы

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

Для решения задачи необходимо определить возможные значения слов и отношения между этими значениями и контекстом, в котором использовались слова. На данный момент основным источником значений являются словари и энциклопедии. Для установления связей между значениями лингвистами создаются тезаурусы, семантические сети и другие специализированные структуры. Однако создание таких ресурсов требует огромных трудозатрат.

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

Открытая энциклопедия Викинедия является беспрецедентным ресурсом. Она позволяет автоматически составить словарь терминов, достаточный для описания любых текстовых документов, сопоставить термины со значениями, описанными в статьях Викииедии, и на основе ссылочной структуры вывести отношения между этими значениями. Словарь Викииедии позволяет автоматически находить в документах как отдельные слова, так и составные термины. На основе разрешения лексической многозначности выделенных

терминов, возможно определить основные тематические линии, нахождение которых необходимо для большого числа практических приложений.

Цель диссертационной работы

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

Для достижения этой цели были поставлены следующие задачи:

1. разработать метод для автоматического определения отношений между значениями терминов Викинедии;

2. разработать методы разрешения лексической многозначности терминов, на основе структурной и текстовой информации Викинедии.

Научная новизна

Научной новизной обладают следующие результаты работы:

1. предложен подход к разрешению лексической многозначности терминов на основе сети документов Викинедии.

2. разработан метод разрешения лексической многозначности, основанный на Марковской модели высокого порядка, где параметры модели оценивались на основе структурной и текстовой информации Викинедии;

3. предложено обобщение Марковской модели на случай множества независимых Марковских процессов и разработан алгоритм вычисления наи-

более вероятной последовательности состояний, удовлетворяющей ограничениям модели;

4. разработан метод разрешения лексической многозначности и выделения лексических цепей, основанный на обобщенной Марковской модели.

Практическая значимость Разработанные методы разрешения лексической многозначности, основанные на Википедии, могут применяться для повышения точности реальных практических приложений, предназначенных для обработки и анализа текстовых данных.

На основе предложенных методов разработан прототип системы разрешения лексической многозначности. Этот прототип был использован в качестве основы для создания в Институте системного программирования РАН системы анализа текстов «Texterra».

Апробация работы и Публикации.

По материалам диссертации опубликовано восемь работ [1-8]. Основные положения докладывались на следующих конференциях и семинарах:

• на четвертом и пятом весеннем коллоквиуме молодых исследователей в области баз данных и информационных систем (SYRCoDIS) (2007 и 2008 гг.);

• на сто двадцать пятом и сто тридцать шестом заседаниях Московской Секции ACM SIGMOD (2008 и 2009 гг.);

• на тридцать четвертой международной конференции по очень большим базам данных (VLDB) (2008 г.);

• на международном симпозиуме по извлечению знаний из социального Веба (KASW) (2008 г.);

• на одиннадцатой Всероссийской научной конференции «Электронные библиотеки: перспективные методы и технологии, электронные коллекции» (2009 г.);

• на двадцать третей международной конференции по проблемам языка, информации и вычислений (РАСЫС) (2009 г.).

Структура и объем диссертации

Работа состоит из введения, трех глав, заключения и списка литературы. Общий объем диссертации составляет 138 страниц. Список литературы содержит 119 наименований.

Содержание работы

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

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

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

в соответствии с контекстом, в котором они использовались.

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

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

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

Для установления отношений между значениями используются статистические оценки и оценки полученные на основе лексико-семантических ресурсов, называемые в литературе семантической близостью значений.

Определение 1. семантической близостью называется отображение / : X х X —> 11, ставящее в соответствие паре слов, терминов или их значений действительное число и обладающее следующими свойствами:

1- 0 < f{x,y) < 1,

2. f{x,y) = l&x = y.

Семантическая близость часто используется методами из обоих описанных классов класса, для преодоления проблемы разреженности языка. На практике для определения таких отображений используются специализированные дексико-семантические ресурсы, создающиеся экспертами в области лингвистики, что существенно усложняет процесс разработки практических приложений.

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

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

Под сетью документов понимается случайный граф, вершинами которого являются текстовые документы, а ребрами — гипертекстовые ссылки между ними. При этом, распределение степеней узлов в таких сетях, отвечает степенному закону, то есть доля Р(к) вершин в сети, имеющих к связей с другими узлами описывается законом Р(к) ~ к~7, где 7 — константа, для большинства реальных сетей находящаяся в интервале 2 < 7 < 3. Таким образом, сети документов являются частным случаем безмасштабных графов (scale-free graph).

В первом разделе второй главы описываются свойства сетей документов и безмасштабных графов и показывается, что сети документов структурно отличаются от семантических сетей и тезаурусов, созданных экспертами. Это

накладывает отпечаток на способы их использования, в частности, на методы вычисления семантической близости.

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

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

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

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

В третьем разделе предлагается собственный метод вычисления семанти-

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

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

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

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

результаты в контексте применения к задаче устранения лексической многозначности:

агт(А,В) -——- , (1

N<En{A) И£п{В)

где п{Х) — множество узлов, непосредственно связанных с узлом X. Эксперименты проводились на алгоритмах и тестовых множествах, описанных в третьей главе данной работы.

Также в третьем разделе второй главы описан процесс извлечения информации из Википедии, приводится обзор существующих работ по этой теме и обосновывается необходимость создания собственного анализатора Википедии. Так как использование Википедии является новым направлением, существующие системы извлечения информации из этой энциклопедии являются недостаточно гибкими для использования с методами, разработанными в диссертационной работе. Описание разработанного анализатора, представленное в данном разделе, показывает процесс построения словарей и основные трудности, возникающие при обработке Википедии. После обработки Википедии был получен словарь из 5.5 млн. терминов, соответствующих 2.8 млн. значений. При этом словарь содержит 290000 многозначных слов, а среднее количество значений равно 5,4.

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

Результаты второй главы опубликованы в работах [2, 3, 7].

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

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

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

Для определения наиболее близкого к контексту значения используется семантическая близость между значениями терминов. Так как контекст может состоять из нескольких терминов, в данном разделе предлагается способ вычисления семантической близости между множествами значений. Результаты предложенного метода зависят от однозначного контекста, которого может быть недостаточно для принятия правильного решения. Этот существенный недостаток, исправляется в последующих методах, где задача устранения лексической многозначности сводится к задаче максимизации.

Также в данном разделе описываются три тестовые коллекции, которые используются для оценки качества всех методов, представленных в диссертационной работе. Первая коллекция разработана в Институте системного программирования РАН и основана на коллекции новостных документов и

научных статей. Во второй коллекции используются статьи самой Википе-дии. Оценка производится только для терминов, представленных в ссылках, а значения этих терминов описываются статьями на которые указывает соответствующая ссылка. Еще одна используемая коллекция была разработана исследователями новозеландского университета Уэйкато и размечена с помощью сервиса Amazon Mechanical Turk.

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

В третьей секции показано как решать задачу разрешения лексической многозначности с помощью скрытой модели Маркова. Имея последовательность наблюдаемых неременных г = {t\,-..,tn) (терминов текста), необходимо найти наиболее вероятную последовательность состояний модели ¡л = (mi,... ,тп) (соответствующих значений терминов). Марковская модель задает ограничения на зависимость между переменными, а задача разрешения лексической многозначности сводится к поиску наиболее вероятной последовательности значений:

где (т,-ь:-1) — сокращенная запись для последовательности переменных (т<_ь • ■ •, 1).

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

Эвристика 1. Вероятность значения rrii, при условии предыдущего контекста trii-h,..., m¡_i пропорциональна линейной комбинации (а) близости значения к контексту и (б) априорной вероятности этого значения.

Р(тгц\гщ-н, ■ ■ ■ Щ-i) = P(m¡lmi-h,. ■ ■ m¡_i) =

= a- (sOTi(m¿;m¿-h,...m¿-i) + 0 • Р(щ)) (2)

Эвристика позволяет дать экспертные оценки параметров марковских моделей любого порядка. Для задачи разрешения лексической многозначности такой результат представлен впервые.

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

Эвристика 2. для задачи устранения лексической многозначности, наиболее вероятный путь до состояния пц зависит только от п последних значений наиболее вероятного пути до состояния m¿_i .

Эта эвристика позволила существенно увеличить скорость обработки текстов, при этом потери в точности оказались несущественны.

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

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

Также как и в классической марковской модели, исследуются стационарные процессы, моделируемые марковскими цепями некоторого порядка т. Основное различие между классической марковской моделью и моделью представленной в данном разделе заключается в том, что текущее состояние может стать частью одной из существующих цепей, а может сформировать новую цепь, независимую от других цепей. Для этого в определение модели вводится дополнительная вероятность, что некоторое состояние принадлежит одной или нескольким из существующих цепей.

Д = arg max ПРЦ € A)P(mj|A)P(ii|mi) ,

" V;=i /

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

Предположение 1. Вероятность того, что текущее состояние ть принадлежит цепи L, зависит только от конечного числа предыдущих состояний mti, mt2, ..., mi(i цепи С, где U < k,Vi = 1 ,h.

В дальнейшем будем называть состояния m(l, mt2, ..., гщк, описанпые в сделанном предположении активными; цени, содержащие активные состояния, будем называть активными цепями. Количество активных состояний определяет порядок обобщенной модели.

Предположение 2. Для различных состояний m,i, nij итк, событие «mi и mk принадлежат одной цепи» (обозначаемое mimk) является независимым от события «тj и тк принадлежат одной цепи». То есть для г ^ j, i ф к и]ф к:

Р(щгпь and, гпрщ) = Р(пцтк) ■ Р(гпрпи) ■ 15

Эти ограничения позволяют выразить вероятность Р(гп; е Л) через вероятности Р(пцггц) и существенно сократить сложность вычисления наиболее вероятной последовательности состояний.

Далее в тексте представлен алгоритм для нахождения наиболее вероятной последовательности состояний обобщенной модели, являющийся модификацией алгоритма Витерби. Алгоритм линейно зависит от количества обрабатываемых терминов, однако на каждом шаге производит сравнение всех возможных цепей. Число таких цепей описывается последовательностью Белла Вп, где п — число активных состояний. Таким образом, сложность алгоритма растет в экспоненциальной зависимости от порядка обобщенной модели.

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

1. если на некотором шаге алгоритма для фиксированных значений неременных состояний вероятность объединения этих состояний в одну цепь больше вероятности создания нескольких цепей, и если переменные состояния в итоговом наиболее вероятном пути будут иметь те же значения, то они также будут принадлежать одной цени;

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

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

Теорема 1.

I. \/т, е Л, С = Сх.....£п, Уп € N. У/с = 1 ..п:

к-1 п

Р(Ш) > Р(С,т) =» Р(£т) > Др(А) х Р(2*т) х Д Р(£,) ,

1=1 )=<;+1 Л—1 п

Р(£,т) > Р(£гп) => Р(£,т) > ДР(А) х Р(2^п) X [] Р(£<) .

¿=1 {=к+1

£ УАеЛ, Л = {£ь...,£п}, Эт.-

Р{С\...Спт) > Р(АП... £нк,Щ), где г/ = ■•■

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

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

Эвристика 3. Вероятности события, что два значения принадлежат одной цепи, является функцией от семантической близости:

Р(гщтъ) = ф(з{т(гп1,тп2)) . (3)

Далее предлагается метод, для автоматической оценки параметра Р(тгцгп2), основанный на кластеризации графа значений. Оценка производилась на неразмеченной коллекции новостных статей. Каждый документ коллекции был представлен в виде взвешенного графа, где вершинами являлись значения терминов документа, а ребра между вершинами имели вес равный семантической близости этих значений. После этого к каждому полученному графу был применен алгоритм кластеризации. Два значения считались принадлежащими одной лексической цепи, если соответствующие вершины графа принадлежали одному кластеру. Таким образом был получен тренировочный корпус для оценки функции ф, где пары концепций, принадлежащих одному кластеру, являлись положительными примерами, а отрицательные примеры формировались парами концепций, принадлежащих одному документу, но разным кластерам. Было получено множество из 137,324 положительных и 859,076 отрицательных примеров, на их основе из пространства ступенчатых функций с шагом 0.01 выбиралась функция ф. Заметим, что никакая ручная обработка текста не требовалась.

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

Результаты третьей главы опубликованы в работах [2, 5, 6, 8].

В Заключении диссертационной работы перечисляются ее основные результаты.

Основные результаты работы

1. Предложен подход к разрешению лексической многозначности терминов на основе сети документов Википедии.

2. Предложен метод измерения семантической близости узлов взвешенной сети документов.

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

4. Для экспериментального подтверждения эффективности предложенных методов разработан прототип системы разрешения лексической многозначности терминов Википедии и проведены эксперименты, доказывающие эффективность предложенных методов.

5. Разработанный прототип был использован в качестве основы для создания в Институте системного программирования РАН системы анализа текстов Texterra.

Список публикаций

[1] Denis Turdakov. Recommender System Based on User-generated Content // Proceedings of the SYRCODIS 2007 Colloquium on Databases and Information Systems. — 2007.

[2] Denis Turdakov, Pavel Velikhov. Semantic Relatedness Metric for Wikipedia Concepts Based on Link Analysis and its Application to Word Sense Disam-

biguation // Proceedings of the SYRCODIS 2008 Colloquium on Databases and Information Systems. — 2008.

[3] Dmitry Lizorkin, Pavel Velikhov, Maxim Grinev, Denis Turdakov. Accuracy estimate and optimization techniques for SimRank computation // Proceedings of the 34rd International Conference on Very Large Data Bases. — 2008.- Vol. 1, no. 1,- Pp. 422-433.

[4] Maria Grineva, Maxim Grinev, Denis Turdakov et al. Harnessing Wikipedia for Smart Tags Clustering // KASW: International Workshop on «Knowledge Acquisition from the Social Web». — 2008.

[5] Д. Ю. Турдаков, С. Д. Кузнецов. Автоматическое разрешение лексической многозначности терминов на основе сетей документов // Программирование. — 2010. — Vol. 36, no. 1. — Pp. 11-18.

[6] Турдаков Денис. Устранение лексической многозначности терминов Википедии на основе скрытой модели Маркова //XI Всероссийская научная конференция «Электронные библиотеки: перспективные методы и технологии, электронные коллекции». — 2009.

[7] Dmitry Lizorkin, Pavel Velikhov, Maxim Grinev, Denis Thirdakov. Accuracy estimate and optimization techniques for SimRank computation // The VLDB Journal. - 2009. http://dx.doi. org/10.1145/1453856.1453904.

[8] Denis Turdakov, Dmitry Lizorkin. HMM Expanded to Multiple Interleaved Chains as a Model for Word Sense Disambiguation ,// Proceedings of the 23rd Pacific Asia Conference on Language, Information and Computation. — Hong Kong: City University of Hong Kong, 2009. — December. — Pp. 549-558.

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. Подписано к печати 12.01.2010 г. Формат 60x90 1/16. Усл.печ.л. 1,0. Тираж 100 экз. Заказ 002. Тел. 939-3890. Тел./факс 939-3891 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 627 к.

Введение

Глава 1. Разрешение лексической многозначности

1.1. Используемая терминология

1.1.1. Терминология классической лингвистики.

1.1.2. Терминология компьютерной лингвистики

1.2. Основные проблемы разрешения лексической многозначности

1.2.1. Значение

1.2.2. Контекст

1.2.3. Методы оценки.

1.3. Обзор работ

1.3.1. Работы 50-х — 80-х годов.

1.3.2. Методы, основанные внешних источниках знаний

1.3.3. Методы, основанные на обучении по размеченным корпусам

1.3.4. Методы, основанные на обучении по неразмеченным корпусам

1.4. Выводы к первой главе

Глава 2. Вычисление семантической близости в сетях документов

2.1. Сети документов.

2.2. Семантическая близость в сетях документов.

2.2.1. Локальные методы

2.2.2. Глобальные методы

2.3. Википедия

2.3.1. Вычисление семантической близости между статьями Ви-кипедии.

2.3.2. Обработка Википедии.

2.4. Обзор работ, использующих Википедию для устранения лексической многозначности

2.5. Выводы ко второй главе

Глава 3. Снятие лексической многозначности

3.1. Общий процесс обработки

3.2. Метод, использующий однозначный контекст

3.2.1. Описание метода.

3.2.2. Эксперименты

3.2.3. Выбор параметров и результаты.

3.2.4. Выводы.

3.3. Метод на основе специализированной марковской модели

3.3.1. Описание метода.

3.3.2. Эксперименты

3.3.3. Выводы.

3.4. Метод на основе марковской модели, обобщенной на случай нескольких независимых цепей.

3.4.1. Мотивация и примеры

3.4.2. Обобщение марковской модели.

3.4.3. Алгоритм для нахождения наиболее вероятной последовательности состояний

3.4.4. Применение модели к задаче устранения лексической многозначности

3.4.5. Эксперименты

3.4.6. Выводы.

3.5. Выводы к третей главе

Актуальность темы

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

Для решения задачи необходимо определить возможные значения слов и отношения между этими значениями и контекстом, в котором использовались слова. На данный момент основным источником значений являются словари и энциклопедии. Для установления связей между значениями лингвистами создаются тезаурусы, семантические сети и другие специализированные структуры. Однако создание таких ресурсов требует огромных трудозатрат.

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

Открытая энциклопедия Википедия является беспрецедентным ресурсом. Она позволяет автоматически составить словарь терминов, достаточный для описания любых текстовых документов, сопоставить термины со значениями, описанными в статьях Википсдии, и на основе ссылочной структуры вывести отношения между этими значениями. Словарь Википедии позволяет автоматически находить в документах как отдельные слова, так и составные термины. На основе разрешения лексической многозначности выделенных терминов, возможно определить основные тематические линии, нахождение которых необходимо для большого числа практических приложений.

Цель диссертационной работы

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

Для достижения этой цели были поставлены следующие задачи:

1. разработать метод для автоматического определения отношений между значениями терминов Википедии;

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

Научная новизна

Научной новизной обладают следующие результаты работы:

1. предложен подход к разрешению лексической многозначности терминов на основе сети документов Википедии.

2. разработан метод разрешения лексической многозначности, основанный на Марковской модели высокого порядка, где параметры модели оценивались на основе структурной и текстовой информации Википедии;

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

4. разработан метод разрешения лексической многозначности и выделения лексических цепей, основанный на обобщенной Марковской модели.

Практическая значимость Разработанные методы разрешения лексической многозначности, основанные на Википедии, могут применяться для повышения точности реальных практических приложений, предназначенных для обработки и анализа текстовых данных.

На основе предложенных методов разработан прототип системы разрешения лексической многозначности. Этот прототип был использован в качестве основы для создания в Институте системного программирования РАН системы анализа текстов «Texterra».

Апробация работы и Публикации.

По материалам диссертации опубликовано восемь работ [1-8]. Основные положения докладывались на следующих конференциях и семинарах:

• на четвертом и пятом весеннем коллоквиуме молодых исследователей в области баз данных и информационных систем (SYRCoDIS) (2007 и 2008 гг.);

• на сто двадцать пятом и сто тридцать шестом заседаниях Московской Секции ACM SIGMOD (2008 и 2009 гг.);

• на тридцать четвертой международной конференции по очень большим базам данных (VLDB) (2008 г.);

• на международном симпозиуме по извлечению знаний из социального Веба (KASW) (2008 г.);

• на одиннадцатой Всероссийской научной конференции «Электронные библиотеки: перспективные методы и технологии, электронные коллекции» (2009 г.);

• на двадцать третей международной конференции по проблемам языка, информации и вычислений (PACLIC) (2009 г.).

Структура и объем диссертации

Работа состоит из введения, трех глав, заключения и списка литературы. Общий объем диссертации составляет 138 страниц. Список литературы содержит 119 наименований.

3.5. Выводы к третей главе

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

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

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

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

Заключение

В ходе диссертационной работы получены следующие результаты:

1. Предложен подход к разрешению лексической многозначности терминов на основе сети документов Википедии.

2. Предложен метод измерения семантической близости узлов взвешенной сети документов.

3. В рамках предложенного подхода разработаны и формально обоснованы мето-ды разрешения лексической многозначности терминов на основе структурной и текстовой информации сетей документов с использованием: контекста из однозначных терминов; Марковской модели высокого порядка; обобщения Марковской модели.

4. Для экспериментального подтверждения эффективности предложенных методов разработан прототип системы разрешения лексической многозначности терминов Википедии и проведены эксперименты, доказывающие эффективность предложенных методов.

5. Разработанный прототип был использован в качестве основы для создания в Институте системного программирования РАН системы анализа текстов Textcrra.

1. Denis Turdakov. Recommender System Based on User-generated Content // Proceedings of the SYRCOD1. 2007 Colloquium on Databases and Information Systems. — 2007.

2. Denis Turdakov, Pavel Velikhov. Semantic Relatedncss Metric for Wikipedia Concepts Based on Link Analysis and its Application to Word Sense Disambiguation // Proceedings of the SYRCODIS 2008 Colloquium on Databases and Information Systems. — 2008.

3. Dmitry Lizorkin, Pavel Velikhov, Maxim Grinev, Denis Turdakov. Accuracy estimate and optimization techniques for SimRank computation // Proceedings of the 34rd International Conference on Very Large Data Bases. — 2008. — Vol. 1, no. l.-Pp. 422-433.

4. Maria Grineva, Maxim Grinev, Denis Turdakov et al. Harnessing Wikipedia for Smart Tags Clustering // KASW: International Workshop on «Knowledge Acquisition from the Social Web». — 2008.

5. Д. IO. Турдаков, С. Д. Кузнецов. Автоматическое разрешение лексической многозначности терминов на основе сетей документов // Программирование. — 2010. — Vol. 36, no. 1. — Pp. 11—18.

6. Турдаков Денис. Устранение лексической многозначности терминов Викинедии на основе скрытой модели Маркова //XI Всероссийская научная конференция «Электронные библиотеки: перспективные методы и технологии, электронные коллекции». — 2009.

7. Dmitry Lizorkin, Pavel Velikhov, Maxim Grinev, Denis Turdakov. Accuracyestimate and optimization techniques for SimRank computation // The VLDB Journal. — 2009. http: //dx. doi. org/10.1145/1453856.1453904.

8. George A. Miller, Richard Beckwith, Christiane Fellbaum et al. WordNet: An on-line lexical database // International Journal of Lexicography. — 1990. — Vol. 3. Pp. 235-244.

9. Word Sense Disambiguation: Algorithms and Applications (Text, Speech and Language Technology), Ed. by E. Agirre, P. G. Edmonds. — 1 edition. — Springer, 2007. — November.

10. Nancy Ide, Jean Veronis. Word Sense Disambiguation: The State of the Art // Computational Linguistics. — 1998. — Vol. 24. — Pp. 1-40.

11. Gerard. Salton. Automatic Information Organization and Retrieval. — Mc-Graw Hill Text, 1968.

12. Kenneth C. Litowski. Desiderata for tagging with WordNet sysnscts or MCA A categories //In Proceedings of the ACL-SIGLEX Workshop "Tagging Text with Lexical Semantics: Why, What, and How?"pages 12—17. — Washington, DC, 1997, —April.

13. Stephanie Seneff. TINA: a natural language system for spoken language applications // Comput. Linguist. — 1992. — Vol. 18, no. 1,—Pp. 61-86.

14. M. Grineva, M. Grinev, D. Lizorkin. Effective Extraction of Thematically Grouped Key Terms From Text // AAAI-SSS-09: Social Semantic Web: Where Web 2.0 Meets Web 3.0. 2009.

15. Maria Grineva, Maxim Grinev, Dmitry Lizorkin. Extracting Key Terms From Noisy and Multi-theme Documents // 18th International World Wide Web Conference. — 2009. April. - Pp. 661-661.

16. Аристотель. Категории // Аристотель. Сочинения: в 4 т. Т.2-4 / ред. З.Н.Микеладзе. — М.: Мысль, 1978-1984.

17. Розеиталъ Д.Э., Голуб И.Б., Теленкова М.А. Современный русский язык.

18. Jesus Gimenez, Lluis Marquez. SVMTool: A general POS tagger generator based on Support Vector Machines. — 2004.

19. Robert Malouf. A comparison of algorithms for maximum entropy parameter estimation // COLING-02: proceeding of the 6th conference on Natural language learning. — Morristown, NJ, USA: Association for Computational Linguistics, 2002.

20. Roger C. Schank. Conceptual Information Processing. — Amsterdam: North Holland, 1975.

21. В. В. Виноградов. Основные типы лексических значений слова // "Вопросы языкознания".— 1953.

22. Abraham Kaplan. An experimental study of ambiguity and context // Mechanical Translation. — 1955. — Vol. 2, no. 2. — Pp. 39-46.

23. David Yarowsky. One sense per collocation // HLT '93: Proceedings of the workshop on Human Language Technology. — Morristown, NJ, USA: Association for Computational Linguistics, 1993.— Pp. 266-271.

24. W. A. Gale, K. W. Church, D. Yarowsky. A method for disambiguating word senses in a large corpus. // Computers and the Humanitzes. — Vol. 26. 1993. - Pp. 415-439.

25. William A. Gale, Kenneth W. Church, David Yarowsky. One sense per discourse // HLT '91: Proceedings of the workshop on Speech and Natural Language. — Morristown, NJ, USA: Association for Computational Linguistics, 1992. Pp. 233-237.

26. Terry Winograd. Procedures as a Representation for Data in a Computer Program for Understanding Natural Language: Tech. rep.: 1971.

27. George A. Miller, Claudia Leacock, Randee Tengi, Ross T. Bunker. A semantic concordance // HLT '93: Proceedings of the workshop on Human Language Technology. — Morristown, NJ, USA: Association for Computational Linguistics, 1993. Pp. 303-308.

28. Nelson W. Francis, Henry Kucera. Frequency Analysis of English Usage: Lexicon and Grammar. — Boston: Houghton Mifflin, 1982.—April. — Vol. 18. Pp. 64-70.

29. Claudia Leacock, Geoffrey Towell, Ellen Voorhees. Corpus-based statistical sense resolution // HLT '93: Proceedings of the workshop on Human Language Technology.— Morristown, NJ, USA: Association for Computational Linguistics, 1993, — Pp. 260-265.

30. Rebecca Bruce, Janyce Wiebe. Word-Sense Disambiguation Using Decomposable Models // Proceedings of the 32nd Annual Meeting of the Association for Computational Linguistics. — 1994. — Pp. 139-146.

31. Adam Kilgarriff. SENSEVAL: An Exercise in Evaluating Word Sense Disambiguation Programs // In LREC. 1998. — Pp. 581-588.

32. Sue Atkins. Tools for computer-aided corpus lexicography: The Hector project. 1993. - Vol. 41.

33. Martha Palmer, Christiane Fellbaum, Scott Cotton et al. English tasks: Al-1-words and verb lexical sample // Proceedings of Senseval-2: Second International Workshop on Evaluating Word Sense Disambiguation Systems. — Toulouse, France: 2001,- P. 21-24.

34. Rada Mihalcea, Philip Edmonds // Proceedings of Senscval-3: Third International Workshop on the Evaluation of Systems for the Semantic Analysis of Text. — Barcelona, Spain: 2004.

35. Timothy Chklovski, Rada Mihalcea. Building a sense tagged corpus with open mind word expert // Proceedings of the ACL-02 workshop on Word sense disambiguation. — Morristown, NJ, USA: Association for Computational Linguistics, 2002. — Pp. 116-122.

36. R. V. Guha, Douglas B. LenaL CYC: a mid-term report // Appl. Artif. Intell. — 1991. — Vol. 5, no. 1. Pp. 45-86.

37. Mitchell P. Marcus, Mary Ann Marcinkiewicz, Beatrice Santorini et a,I. Building a Large Annotated Corpus of English: The Penn Treebank. — 2004.

38. Noam Chomsky. Syntactic Structures. — Mouton, The Hague, 1957.

39. Минский M. Фреймы для представления знаний. — М.: Мир, 1979.

40. Richard Н. Richens. Interlingual machine translation // Computer Journal. Vol. 3. - 1958. - Pp. 144-147.

41. Margaret Masterman. Semantic message detection for machine translation, using an interlingua // International Conference on Machine Translation of Languages and Applied Language Analysis. — London: Her Majesty's Stationery Office, 1962, — Pp. 437-475.

42. M. Ross Quillian. The teachable language comprehender: a simulation program and theory of language // Commun. ACM. — 1969. — Vol. 12, no. 8. — Pp. 459-476.

43. Philip J Hayes. A process to implement some word-sense disambiguation // Working paper 23. Institut pour les Etudes Semantiques et Cognitives. Uni-versiti de Geneve. — 1976.

44. Allan M. Collins, Elisabeth F. Loftus. A spreading activation theory ofsemantic processing // Psychological Review.— 1975.— Vol. 82, no. 6.— Pp. 407-428.

45. Claudia Leacock, George A. Miller, Martin Chodorow. Using Corpus Statistics and WordNet Relations for Sense Identification. — 1998.

46. Graeme Hirst, David St-Onge. Lexical Chains as Representations of Context for the Detection and Correction of Malapropisms. — 1997.

47. Philip Resnik Sun. Using Information Content to Evaluate Semantic Similarity in a Taxonomy //In Proceedings of the 14th International Joint Conference on Artificial Intelligence. — 1995.— Pp. 448-453.

48. J. J. Jiang, D. W. Conrath. Semantic Similarity Based on Corpus Statistics and Lexical Taxonomy // International Conference Research on Computational Linguistics (ROCLING X).— 1997. — September.

49. Dekang Lin. An Information-Theoretic Definition of Similarity // ICML '98: Proceedings of the Fifteenth International Conference on Machine Learning. — San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 1998. — Pp. 296-304.

50. Eneko Agirre, German Rigau. Word Sense Disambiguation using Conceptual Density //In Proceedings of the 16th International Conference on Computational Linguistics. — 1996. — Pp. 16-22.

51. Jiri Stetina, Sadao Kurohashi, Makoto Nagao. General Word Sense Disambiguation Method Based on a Full Sentential Context //In Usage of WordNet in Natural Language Processing, Proceedings of COLING-ACL Workshop. 1998.

52. Jane Morris, Graeme Hirst. Lexical cohesion computed by thesaural relations as an indicator of the structure of text // Comput. Linguist. — 1991. — March. Vol. 17, no. 1. — Pp. 21-48.

53. Rada Mihalcea, Dan I. Moldovan. A Highly Accurate Bootstrapping Algorithm for Word Sense Disambiguation // International Journal on Artificial Intelligence Tools. — 2001. — Vol. 10, no. 1-2. — Pp. 5-21.

54. Sergey Brin, Lawrence Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine // Computer Networks and ISDN Systems. — 1998.— Pp. 107-117.

55. R. Nelken, S.M. Shieber. Lexical chaining and word-sense-disambiguation: Technical Report TR-06-07: School of Engineering and Applied Sciences, Harvard University, 2007.

56. Доброе Б.В., Лукашевич Н.В. Разрешение лексической многозначности на основе тезауруса предметной области // Труды международной конференции «Диалог 2007». — 2007.

57. Н.В. Лукашевич, Д. С. Чуйко. Автоматическое разрешение лексической многозначности на базе тезаурусных знаний // Сборник работ участников конкурса «Интернет-математика 2007». — 2007.

58. Martin Chodorow, Claudia Leacock, George A. Miller. A topical local classifier for word sense identification // Computers and the Humanities. — 2000. —Vol. 34.-Pp. 115-120.

59. Adam L. Berger, Vincent J. Delia Pietra, Stephen A. Delia Pietra. A maximum entropy approach to natural language processing // Comput. Linguist. — 1996. — Vol. 22, no. 1. — Pp. 39-71.

60. C. Fellbaum, M. Palm,er. Manual and Automatic Semantic Annotation with WordNet // Proceedings of NAACL 2001 Workshop. — 2001.

61. Tom O'Hara et al. Selecting decomposable models for word sense disambiguation: the grling-sdm system // Computers and the Humanities. —2000. — Vol. 34. Pp. 159-164.

62. Rebecca F. Bruce, Janyce M. Wiebe. Decomposable modeling in natural language processing // Comput. Linguist. — 1999. — Vol. 25, no. 2. — Pp. 195-207.

63. Walter Daelemans, Jakub Zavrel, Ко van der Sloot, Antal van den Bosch. TiMBL: Tilburg Memory-Based Learner version 4.0 - Reference Guide. —2001.

64. Mark Stevenson, Yorick Wilks. The interaction of knowledge sources in word sense disambiguation // Comput. Linguist. — 2001. — September. — Vol. 27, no. 3. Pp. 321-349.

65. Hoa Trang Dang, Martha Palmer. Combining Contextual Features for Word Sense Disambiguation //In Proceedings of the Workshop on Word Sense Disambiguation: Recent Successes and Future Directions. — 2002.— Pp. 88-94.

66. Indrajit Bhattacharya, Lise Getoor, Yoshua Bengio. Unsupervised sense disambiguation using bilingual probabilistic models // ACL '04: Proceedings of the 42nd Annual Meeting on Association for Computational Linguistics. —

67. Morristown, NJ, USA: Association for Computational Linguistics, 2004.— P. 287.

68. Плунгян В. А., Резникова Т. И., Сичинава Д. В. Национальный корпус русского языка: общая характеристика // НТИ, сер. 2, 2005, № 3, 9-13.

69. Кобрицов Б. П. Методы снятия семантической многозначности // Научно-техническая информация, сер.2, N 2. — 2004.

70. Кобрицов Б. П., Ляшевская О. Н. Автоматическое разрешение семантической неоднозначности в Национальном корпусе русского языка // Компьютерная лингвистика и интеллектуальные технологии: Труды международной конференции «Диалог'2004». Москва, Наука, 2004.

71. Кобрицов Б. П., Ляшевская О. Н., Шеманаева О. Ю. Снятие лексико-семантической омонимии в новостных и газетно-журнальных текстах: поверхностные фильтры и статистическая оценка / / Интернет-математика — 2005. Москва, 2005.

72. Кобрицов Б. П., Ляшевская О. Н., Толдова С. 10. Снятие семантической многозначности глаголов с использованием моделей управления, извлеченных из электронных толковых словарей. —

73. Электронная публикация. http://download.yandex.ru/IMAT2007/ kobricov.pdf.

74. Filippo Menczer. Evolution of document networks // Proceedings of the National Academy of Sciences of the United States of America. — 2004. — April. —Vol. 101, no. Suppl 1,- Pp. 5261-5265.

75. Adam Kilgarriff, Gregory Grefenstette. Introduction to the Special Issue on the Web as Corpus // Computational Linguistics. — 2003. — Vol. 29. — Pp. 333-347.

76. A. L. Barabasi, R. Albert. Emergence of scaling in random networks // Science. — 1999. — October. — Vol. 286, no. 5439. Pp. 509-512.

77. P. Erdos, A. Renyi. On random graphs. I // Publ. Math. Debrecen. — 1959. — Vol. 6. Pp. 290-297.

78. Reka Albert, Hawoong Jeong, Albert-Laszlo Barabasi. Error and attack tolerance of complex networks // Nature. — 2000. — July. — Vol. 406, no. 6794. — Pp. 378-382.

79. M. E. Newman. Scientific collaboration networks. I. Network construction and fundamental results. // Phys Rev E Stat Nonlin Soft Matter Phys. — 2001, —July. —Vol. 64, no. 1 Pt 2.

80. М. Е. J. Newman. Clustering and preferential attachment in growing networks. // Phys. Rev. E. 2001. - Vol. 64.

81. Lada A. Adamic, Rajan M. Lukose, Bernardo A. Huberman. Local Search in Unstructured Networks // CoRR.— 2002.— Vol. cond-mat/0204181.— informal publication. ^

82. Reuven Cohen, Shlomo Havlin. Scale-Free Networks Are Ultrasmall // Physical Review Letters. — 2003. — Feb. — Vol. 90, no. 5.

83. V. Zlatic, M. Bozicevic, H. Stefancic, M. Domazet. Wikipedias: Collaborative web-based encyclopedias as complex networks // Physical Review E. — 2006. —Vol. 74,- P. 016115.

84. Justin Zobel, Alistair Moffat. Exploring the similarity space // SIGIR Forum. — 1998. Vol. 32, no. 1. - Pp. 18-34.

85. E. Gabrilovich, S. Markovitch. Computing Semantic Relatedness using Wikipedia-based Explicit Semantic Analysis // Proceedings of the 20th International Joint Conference on Artificial Intelligence. — 2007.— Pp. 6-12.

86. Thomas K. Landauer, Peter W. Foltz, Darrell Laham. An Introduction to Latent Semantic Analysis // Discourse Processes.— 1998.— no. 25.— Pp. 259-284.

87. Ana Gabriela Maguitman, Filippo Menczer, Fulya Erdinc et al. Algorithmic Computation and Approximation of Semantic Similarity // World Wide Web. — 2006. Vol. 9, no. 4. - Pp. 431-456.

88. W. N. Lee, N. Shah, K. Sundlass, M. Musen. Comparison of ontology-based semantic-similarity measures. // AMI A . Annual Symposium proceedings / AMIA Symposium. AMIA Symposium. — 2008. — Pp. 384-388.

89. D. Milne. Computing Semantic Relatedness using Wikipedia Link Structure // Proceedings of the New Zealand Computer Science Research Student Conference (NZCSRSC). Hamilton, New Zealand: 2007.

90. Michael Strube, Simone Paolo Ponzetto. WikiRelate! Computing Semantic Relatedness Using Wikipedia. //21. AAAI / 18. IAAI 2006. — AAAI Press, 2006. —july.

91. D. Milne, I. II. Witten. Learning to link with Wikipedia // 17th ACM Conference on Information and knowledge management. — ACM, 2008. — Pp. 509-518.

92. M. Kessler. Bibliographic coupling between scientific papers // American Documentation. — 1963. Vol. 14. — Pp. 10-25.

93. Glen Jeh, Jennifer Wiclom. SimRank: a measure of structural-context similarity // KDD '02: Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining. — ACM Press, 2002. — Pp. 538-543.

94. Torsten Zesch, Iryna Gurevych. Analysis of the Wikipedia Category Graph for NLP Applications // Proceedings of the TextGraphs-2 Workshop (NAA-CL-IiLT). — 2007.

95. Jim Giles. Internet encyclopaedias go head to head // Nature. — 2005,— December. Vol. 438. — Pp. 900-901.

96. Lotfi A. Zadeh. Fuzzy Sets // Information and Control. — 1965,— Vol. 8, no. 3. Pp. 338-353.

97. Fabian M. Suchanek, Gjergji Kasneci, Gerhard Weikum. Yago: A Large Ontology from Wikipedia and WordNet. — 2007.

98. Soren Auer, Christian Bizer, Georgi Kobilarov ei al. DBpedia: A Nucleus for a Web of Open Data. — 2008. Pp. 722-735.

99. D. Milne, I.II. Witten. An Open-Source Toolkit for Mining Wikipedia.— 2009.

100. D. Milne, I.E. Witten. An effective, low-cost measure of semantic related-ness obtained from Wikipedia // AAAI 2008 Workshop on Wikipedia and Artificial Intelligence: An Evolving Synergy (WIKI-AI '08). — 2008.

101. Rada Mihalcea. Using Wikipedia for Automatic Word Sense Disambiguation // North American Chapter of the Association for Computational Linguistics (NAACL 2007).- 2007.

102. Rada Mihalcea, Andras Csomai. Wikify!: linking documents to encyclopedic knowledge // CIKM '07: Proceedings of the sixteenth ACM conference on Conference on information and knowledge management. — New York, NY, USA: ACM, 2007,- Pp. 233-242.

103. S. Cucerzan. Large-Scale Named Entity Disambiguation Based on Wikipcdia Data // EMNLP 2007: Empirical Methods in Natural Language Processing, June 28-30, 2007, Prague, Czech Republic. — 2007.

104. A. Clauset, M. E. J. Newman, C. Moore. Finding community structure in very large networks // Physical Review E. — 2004. — Vol. 70. — P. 066111.2007.