Учреждение Российской академии наук
Санкт-Петербургский институт информатики и автоматизации РАН

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

Крижановский Андрей Анатольевич

Математическое и программное обеспечение
построения списков семантически близких слов
на основе рейтинга вики-текстов

Специальность: 05.13.11: «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей»

Диссертация на соискание учёной степени

кандидата технических наук

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

д.т.н. проф. А.В. Смирнов

Санкт-Петербург

2008

Оглавление

Введение

Некоторые определения. Для более ясного понимания материала и во избежание недоразумений целесообразно привести следующие определения.

Тезаурус – это словарь, в котором слова, относящиеся к каким-либо областям знания, расположены по тематическому принципу и показаны семантические отношения (родо-видовые, синонимические и др.) между лексическими единицами.¹

Глоссарий – это собрание глосс (толкований) непонятных слов или выражений с толкованием (толковый глоссарий) или переводом на другой язык (переводной глоссарий).²

Информационные поисковые системы (ИПС) – системы поиска релевантных³ документов (текст, изображение, аудио, видео файлы и др.) в сети Интернет или на локальном компьютере, где задача формулируется пользователем в виде набора ключевых слов с возможностью их объединения логическими правилами (И, ИЛИ и др.).

Актуальность темы диссертации. Увеличение числа и изменение качества⁴ электронных документов на локальных компьютерах и в сети Интернет требуют новых алгоритмов для более точного и быстрого поиска.

Выделяют два вида сходства [179]: сходство между объектами (рассматривается в данной работе) и сходство между отношениями (relational similarity, см. [178], [177], [180])⁵. Является ли сущность свойством объекта или отношением – определяется контекстом [105]. Поиск похожих объектов (similarity search) включает такие (на первый взгляд разные, но общие по способам решения) задачи, как поиск похожих текстовых документов, поиск семантически близких слов, поиск похожих вершин графа. Анализ работ в области вычислительной лингвистики показал большое разнообразие алгоритмов, предлагающих решение этих задач (алгоритм HITS [125], алгоритм PageRank [85] (и его модификация Green [145]), алгоритм распределения рангов ArcRank [174], ESA [103], алгоритм извлечения синонимов из толкового словаря [174], метод извлечения контекстно связанных слов [122], [146] и др.). Поиск похожих документов также может являться подэтапом алгоритма поиска документов по запросу [22].

Объектом исследования является синонимия и семантическая близость слов. Два текста связаны гиперссылкой, если один документ упоминает ( то есть ссылается на) другой текст. Тематическая направленность каждого текста определена экспертом, который присваивает одну или несколько категорий тексту¹.

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

Современные алгоритмы поиска синонимов (например, алгоритм извлечения синонимов из толкового словаря [174], алгоритм SimRank [119], алгоритм Similarity Flooding [132]) изначально предназначены для вычисления меры сходства между вершинами графов. Поэтому алгоритмы не учитывают такую дополнительную информацию, как тематическая направленность и метаданные текста [143], [93], [113]. Данная работа призвана восполнить этот пробел.

Требованием к выбору алгоритма (для поиска семантически близких слов) является возможность использования (в рамках алгоритма) тех дополнительных возможностей, которые предоставляет рассматриваемый корпус документов. Это (1) наличие категорий (классифицирующих документы по их тематической принадлежности)¹, (2) наличие метаинформации в виде ключевых слов (в простейшем случае – это заголовок документа). Таким требованиям удовлетворяют алгоритмы HITS [125] и PageRank [85]. Для поиска семантически близких слов был выбран алгоритм HITS, а не PageRank по следующим причинам:

1) формулы вычисления в PageRank требуют экспериментального выбора коэффициента (damping factor)², а в HITS нет никакого коэффициента за счёт использования двух типов документов (авторитетные и хаб).

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

Поиск документов на основе алгоритма HITS тесно связан с вычислением сходства вершин в графе. Автором предложены два способа вычисления меры сходства вершин графа на основе формализации понятия «похожие вершины» графа. Первый вариант использует понятия авторитетных и хаб-страниц и позволяет формализовать задачу поиска похожих страниц в HITS алгоритме. Во втором варианте получена формула сходства двух вершин a и b, основанная на поиске общих вершин среди соседей вершин a и b.

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

При выборе программных инструментальных средств разработки и проектирования архитектуры программы автор придерживался следующих требований: открытость исходного кода (open source), кроссплатформенность (возможность работы на разных платформах: Linux, Windows и др.), модульность архитектуры (возможность использовать предыдущие наработки и интегрировать решения разных подзадач). Важными требованиями были: использование достаточно широко распространённых и хорошо себя зарекомендовавших программных систем для обработки текста на естественном языке и представление результатов работы в виде текста и графики (визуализация). Использование общепринятого стандарта и модульность архитектуры позволяют решить задачу большой сложности (например, машинный перевод), разбив её на ряд подзадач. В качестве программной среды для обработки текстов на естественном языке была выбрана модульная система GATE [92], [98].

Сложность организации поиска семантически близких слов и, в частности, синонимов определяется рядом причин. Во-первых, автору не известно общепринятой количественной меры для определения степени синонимичности значений слов. Можно утверждать, что одна пара слов более синонимична чем другая, но не ясен способ, позволяющий однозначно указывать – во сколько раз.¹ Во-вторых, понятие синонимии определено не для слов, а для значений слов, то есть синонимия неразрывно связана с контекстом. В-третьих, язык – это вечноизменяемая субстанция, открытая система. Слова могут устаревать или получать новые значения. Особенно активное словообразование и присвоение новых значений словам наблюдается в науке, в её молодых, активно развивающихся направлениях. Решение задачи поиска синонимов в частности (а также современных задач автоматизированной обработки текстов на естественном языке в целом) требуют предварительной морфологической обработки текста.

Отсутствуют (по крайней мере, неизвестны автору) доступные модули в системе GATE для морфологической обработки русского языка. Возможно, поэтому система GATE редко упоминается в системах обработки текстов на русском языке. Таким образом, существует насущная необходимость в наличии модуля морфологической обработки русского языка в системе GATE, позволяющая нормализовать слова (лемматизация²), получать морфологические признаки слова (например, род, падеж) и т. д. При этом существует общедоступная программа морфологической обработки русского Lemmatizer (разработанная в проекте Диалинг московскими учёными). Сложность в том, что GATE написан на языке программирования Java, а Lemmatizer написан на C++. Таким образом, решением данной задачи будет разработка архитектуры позволяющей интегрировать эти системы.

К задачам автоматической обработки текста (АОТ) относятся такие задачи, как: машинный перевод, поиск и хранение текста [52], кластеризация текстов¹ [43], [70], определение тематически однородных частей текста и приписывание этим частям документа тематических тегов [72], [104], реферирование текстов, и многие др. Автоматический поиск синонимов и семантически близких слов является одной из задач АОТ.

Актуальность работы определяется возможными областями приложений результатов диссертации. Во-первых, это поиск похожих вершин графа в рамках задачи Ontology Matching [132], [164], [190]. Во-вторых, предложенное решение задачи автоматического поиска синонимов и семантически близких слов может использоваться в поисковых системах для расширения запроса (на основе вычисления сходства запроса и документа [86], сходства запросов между собой² [101], с помощью тезаурусов [10], [95], [163]), для автоматизированного построения онтологии по тексту³, для расширения существующих и создания новых тезаурусов⁴ [135]. В-третьих, разработанная программа поиска семантически близких слов, вероятно, будет востребована лингвистами-лексикографами при составлении словарей синонимов [7], [56], [161]. В работе [79] перечислены ещё два приложения, требующих решения задачи «similarity search»:

• «collaborative filtering» – определение пользователей, имеющих одинаковый вкус, предпочтения;

• поиск / исключение документов почти-копий (англ. «near duplicate»), которое требуется при индексировании документов.

Ещё одна актуальная область связана с задачей определения значения многозначного слова¹. Основа алгоритма представленного в [153], [187] – анализ контекста слова. При этом начальные слова² в обучающем наборе (в алгоритме, предложенном в [187]) должны точно различать возможные значения. Выбор начальных слов (для заданного слова) можно выполнять с помощью предложенного в диссертации алгоритма поиска семантически близких слов. Другие актуальные направления новых информационных технологий, в которых могут использоваться результаты данной диссертационной работы – это направление запросно-ответных систем (question-answering system) и автоматическое создание проблемно-ориентированных тезаурусов³.

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

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

1. Проанализировать методы поиска семантически близких слов, обосновать выбор текстовых ресурсов, алгоритма (с возможной адаптацией) и программных систем для автоматической обработки текстов на естественном языке (ЕЯ).

2. Разработать подход к поиску семантически близких слов (в корпусе текстовых документов с гиперссылками и категориями).

3. Разработать алгоритмы поиска семантически близких слов в корпусе текстовых документов с гиперссылками и категориями.

4. Спроектировать и реализовать программный комплекс поиска семантически близких слов; разработать способы численной оценки наборов синонимов.

Методы исследования. Для решения поставленных задач в работе используются методы кластерного анализа [43], [70], методы теории графов [19], [28], [29], [38], [45], [46], [49], элементы теории сложности алгоритмов [5], [23], [32], [42], стандарты открытых информационных сред. При разработке программного обеспечения использовалась технология объектно-ориентированного программирования (Java, C++) [13], язык структурированных запросов (SQL) управления данными в реляционных базах данных [26], программная среда для обработки текстов на естественном языке (GATE) [92], [98].

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

1. Новизна предложенного подхода к поиску семантически близких слов в проблемно-ориентированном корпусе заключается в том, что кроме гиперссылок дополнительно учитывается метаинформация документов (ключевые слова, категории).

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

3. Новый способ построения корневого набора документов в адапти­рованном HITS алгоритме заключается в выборе документов, связанных гиперссылками с исходным документом (заданным пользователем), что позволяет отказаться от шага «предварительный веб-поиск документов».

4. Коэффициент Спирмена модифицирован для численного сравнения списков семантически близких слов; отличие заключается в возможности сравнивать списки разной длины.

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

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

7. Эксперименты подтвердили выполнение закона Ципфа для текстов Русской Википедии и Википедии на английском упро­щён­ном языке на основе построенных индексных баз данных.

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

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

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

Разработана архитектура программного модуля RuPOSTagger системы GATE для удалённого доступа к программе морфологического анализа русского языка (использован модуль морфологического анализа русского языка проекта Диалинг). Модуль RuPOSTagger может использоваться как внутри GATE (с другими модулями), так и быть интегрирован в отдельный (standalone) программный продукт. Спроектирована архитектура и реализована система индексирования вики-текстов.

Реализация результатов работы.

Исследования, отражённые в диссертации, были поддержаны грантами РФФИ (проект № 02-01-00284 «Методологические и математические основы построения компьютерных систем быстрой интеграции знаний из распределённых источников» 2002-2004 гг.; № 06-07-89242 "Методология и модели интеллектуального управления конфигурациями распределенных информационных систем с динамически изменяющимися структурами", 2006-2008 гг.; № 05-01-00151 "Методологические и математические основы построения контекстно-управляемых систем интеллектуальной поддержки принятия решений в открытой информационной среде", 2005-2007 гг.), грантами Президиума РАН (проект № 2.44 «Многоагентный подход к построению компьютерной среды для быстрой интеграции знаний из распределённых источников» 2001-2003 гг. и проект № 2.35 «Контекстно-управляемая методология построения распределённых систем интеллектуальной поддержки принятия решений в открытой информационной среде» 2003-2008 гг.), а также грантом ОИТВС РАН (проект № 1.9 «Разработка теоретических основ и многоагентной технологии управления контекстом в распределённой информационной среде» 2003-2005 гг.).

Разработан программный комплекс Synarcher на языке Java для поиска семантически близких слов в энциклопедии Википедия с динамической визуализацией результатов поиска¹. Результаты поиска представлены в виде текста (список семантически близких слов), в виде таблицы (с возможностью упорядочения и редактирования) и в виде графического представления набора вершин и рёбер с возможностью показать/спрятать соседние вершины для текущей вершины. Настройка параметров поиска позволяет (i) указать размер пространства поиска, что определяет время поиска и результат, (ii) разрешить поиск статей определённой тематики (то есть сузить область поиска) за счёт выбора категорий статей.

Спроектирована и реализована распределённая клиент-серверная архитектура в программном комплексе Russian POS Tagger², позволяющая интегрировать среду GATE и модуль морфологической обработки русского языка Lemmatizer (фирма Диалинг). Комплекс RuPOSTagger предоставляет веб-сервис на основе XML-RPC протокола. Веб-сервис обеспечивает вызов функций модуля Lemmatizer из системы GATE или из отдельного Java приложения.

Часть результатов была использована при выполнении контракта «Интеллектуальный доступ к каталогам и документам» на создание системы поддержки клиентов, реализованной для немецкой промышленной компании Фесто, 2003–2004 гг. Разработан и реализован алгоритм кластеризация запросов (на естественном языке) и пользователей на основе использования онтологий в данном проекте [172].

Разработана архитектура программной системы поиска семантически близких слов в исследовательском проекте CRDF № RUM2-1554-ST-05 «Онтолого-управляемая интеграция информации из разнородных источников для принятия решений», 2005-2006 гг.

Апробация результатов работы. Основные положения и результаты диссертационной работы представлялись на международном семинаре «Автономные интеллектуальные системы: агенты и извлечение данных» (Санкт-Петербург 2005), международной конференции «Диалог» (Бекасово 2006), 11^ой международной конференции «Речь и Компьютер» (Санкт-Петербург 2006), международной конференции «Корпусная лингвистика» (Санкт-Петербург 2006) и первой конференции в России «Вики-конференции 2007» (Санкт-Петербург 2007). Часть результатов работы представлена в публикациях [33], [36], [35], [57], [58], [168], [169], [170], [171], [172].

Публикации. Основные результаты по материалам диссертационной работы опубликованы в 8 печатных работах, в том числе в 2 журналах из списка ВАК («Труды Института системного анализа РАН», 2004, «Автоматизация в промышленности», 2008).

Структура и объём работы. Диссертационная работа состоит из введения, четырёх глав, заключения, списка литературы и пяти приложений. Работа изложена на 156 страницах и включает 35 рисунков, 14 таблиц, а также список литературы из 190 наименований; приложения на 14 страницах. Общий объём работы составляет 188 страниц.

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

1. HITS алгоритм адаптирован к поиску наиболее похожих документов (в корпусе текстов с гиперссылками и категориями) на основе алгоритма иерархической кластеризации;

2. Разработано прикладное программное обеспечение для поиска семантически близких слов в проблемно ориентированном корпусе текстов с динамической визуализацией результатов поиска;

3. Предложена (1) архитектура распределённой программной системы оценивания результатов поиска на основе тезаурусов (WordNet, Moby) и (2) сами методы численной оценки (адаптация метода Спирмена для сравнения ранжирования в списках разной длины);

4. Разработана и реализована архитектура подсистемы GATE для удалённого доступа к программе морфологического анализа русского языка (на основе XML-PRC протокола).

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

В первой главе приводится анализ основных проблем автоматической обработки текста и поиска семантически близких слов. В качестве текстового ресурса выбрана энциклопедия Википедия, рассмотрен ряд алгоритмов и выбран алгоритм HITS¹, определён список задач (необходима адаптация алгоритма HITS к корпусу текстов с категориями, необходимо разработать способ оценки работы алгоритма, необходим способ визуализации результатов поиска). Была выбрана система обработки текста на естественном языке – модульная система GATE, позволяющая унифицировать программные компоненты. Указан недостаток системы, который необходимо исправить – это отсутствие доступного модуля в системе GATE для морфологической обработки русского языка.

Во второй главе представлена адаптация алгоритма HITS (с использованием алгоритма кластеризации) к поиску похожих документов² в корпусе с ссылками и категориями. Приведена оценка временной сложности адаптированного HITS алгоритма. Также предложен алгоритм алгоритм вычисления меры сходства вершин графа. Выполнена оценка временной сложности данного алгоритма и предложены две эвристики, позволяющие уменьшить временную сложность алгоритма. В конце главы предложены методы численной оценки наборов синонимов, полученных на выходе адаптированного HITS алгоритма (это адаптация метода Spearman's footrule и оценка на основе тезаурусов WordNet и Moby).

Третья главе посвящена архитектуре и моделям программ, реализующих разработанные алгоритмы. В главе описана архитектура программы Synarcher, реализующей адаптированный HITS алгоритм, детально описан модуль визуализации программы: интерфейс и функциональность. Описана архитектура программного модуля системы GATE для удалённого доступа к программе морфологического анализа русского языка Lemmatizer (предлагается использовать разработанные автором XML-RPC клиент и сервер). В главе представлена архитектура программной системы, позволяющей оценить построенные списки семантически близких слов. Оценка основана на данных тезаурусов (например WordNet, Moby). Разработана архитектура системы индексирования вики-текстов, включающая программные модули GATE и Lemmatizer. Реализован программный комплекс индексации текстов Википедии на трёх языках: русский, английский, немецкий.

В четвёртой главе описаны эксперименты поиска синонимов в Английской и Русской Википедии с помощью адаптированного HITS алгоритма. Представлен пример работы разработанного автором программного модуля Russian POS Tagger в составе системы GATE. Описаны эксперименты по построению индексных баз данных Русской Википедии и Википедии на английском упрощённом языке.

1. Положения, выносимые на защиту.

1. Подход к поиску семантически близких слов на основе метаинформации в проблемно-ориентированном корпусе, содержащем два типа текстовых документов (статья и категория) и два типа отношений: иерархические отношения (родо-видовые и часть – целое) и гиперссылки.

2. Адаптированный HITS алгоритм поиска семантически близких слов в корпусе текстовых документов с гиперссылками и категориями. Модификация алгоритма включает: (1) новый способ построения корневого набора (релевантных документов), позволяющий отказаться от предварительного поиска документов, а также (2) использование механизма иерархической кластеризации для объединения слов в смысловые группы.

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

4. Программный комплекс поиска семантически близких слов в проблемно-ориентированном корпусе текстов с динамической визуализацией результатов поиска.

5. Архитектура системы индексирования вики-текстов и её программная реализация.

1. Анализ проблемы автоматической обработки текста и поиска семантически близких слов

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

Проблема синонимии

Данная работа тесно связана с понятиями значение, смысл, семантическая близость слов. По Выготскому Л.С. [16] следует различать «смысл» слова и его «значение». «Смысл, не являясь в отличие от значения, неразрывно связанным с определённой знаковой формой, отличим от знака. Всегда существует возможность выражения одного и того же смысла через различные наборы знаков (курсив наш. – А.К.). Иначе говоря, смысл никогда не связан какой-либо жёсткой знаковой формой. Количество степеней семантической свободы знака обусловлено, в свою очередь, его положением в контексте. <...> Смысл слова неисчерпаем.¹ <...> Смысл никогда не является полным.» [16] (цит. по [48]). Таким образом, многовариантность знакового выражения одной и той же вещи (явления) определяет явление синонимии.

«В языке нет полных синонимов. Нет точных соответствий между схожими по значению словами в разных языках» [2]. Это определяется явлениями полисемии (многозначность) [50], омонимии (два или более слова с совершенно разными исконными значениями, одинаковые по форме), синонимии, энантиосемии (одна и та же форма слова может вмещать прямо противоположные значения – просмотрели означает «видели, увидели» и «не увидели» [39].

«Синонимом в полном смысле следует считать такое слово, которое определилось по отношению к своему эквиваленту (к другому слову с тождественным или предельно близким значением) и может быть противопоставлено ему по какой-либо линии: по тонкому оттенку в значении, по выражаемой экспрессии, по эмоциональной окраске, по стилистической принадлежности, по сочетаемости...» [56]. В [56] выделяют две функции синонимов — «уточнительная» (акцентирование того или иного оттенка понятия) и стилистическая.

Однако в работе [18] не делается различия между этими двумя функциями, а утверждается, что важнейшая стилистическая функция синонимов – это наиболее точное выражение мысли. Учитывая смысловые и стилистические отличия синонимов, их разделяют на несколько групп¹:

1. Синонимы, различающиеся оттенками в значениях, называются семантическими (от гр. semantikos – обозначающий), другое название – «идеографические» (гр. idea – понятие, grapho – пишу), или понятийные (молодость – юность, красный – багровый – алый) [18]. Под фразеологическими синонимами понимают “фразеологизмы² с близким значением, обозначающие одно и то же понятие, как правило, соотносительные с одной и той же частью речи, обладающие частично совпадающей или (реже) одинаковой лексико-фразеологической сочетаемостью, но отличающиеся друг от друга оттенками значения, стилистической окраской, а иногда и тем и другим одновременно” [27].

2. Синонимы, которые имеют одинаковое значение, но отличаются стилистической окраской, которая не позволяет заменять их в одном контексте, например, глаза – очи – зенки, называются стилистическими [18], [1]. Фразеологические синонимы отличаются большей стилистической однородностью, чем лексические синонимы (состоящие из слов свободного употребления), так как фразеологизмам в основном присуща эмоциональна экспрессивная окрашенность [27].

3. Синонимы, которые отличаются и по значению, и своей стилистической окраской, называются семантико-стилистическими [18].

4. Синонимы, представляющие для нейтрального слова его экспрессивные, эмоционально окрашенные дериваты, называются деривационными, например, старик – старикан, старик – старичок [1].

Стоит отметить, что деление синонимов на стилистические и «идеографические» достаточно условное. Поскольку «... материал показывает, что невозможно провести границу между теми и другими, зачислив одни в стилистические, а другие только в идеографические. Основная, подавляющая масса синонимов служит и стилистическим и смысловым (оттеночным, уточнительным) целям, часто выполняя и ту и другую функции одновременно» [56].

Способы определения синонимии в современных системах

В проектах WordNet и EuroWordNet синонимия определяется через понятие взаимозаменяемости. «Два слова (выражения) считаются синонимами, если существует хотя бы один контекст С, в котором замена одного слова другим не приводит к изменению истинностного значения» [99] (цит. по [1]).

Поскольку, во-первых, взаимозаменяемость в контексте не всегда связана с общностью значений, во-вторых, некоторые синонимы не являются взаимозаменяемыми в контексте из-за особенностей синтаксической или же лексической сочетаемости, постольку авторы тезауруса RussNet используют критерий взаимозаменяемости только как дополнительный критерий. Основными критериями семантической близости в RussNet являются идентичность словарных определений или взаимная отсылка в синонимических определениях, что проверяется при дефиниционном анализе [1]. Таким образом, в RussNet отношение синонимии устанавливается между лексико-семантическими вариантами слов, которые (i) принадлежат одной части речи, (ii) имеют сходные значения, (iii) могут быть взаимозаменяемы в контексте.

Следующие типы синонимов определены в тезаурусе РуТез [41]:

1. Лексические синонимы (полные синонимы; синонимы, отражающие различные языковые стили; синтаксические синонимы; словообразовательные синонимы);

2. Условные синонимы (сокращения; сложные и сложносокращённые слова; некоторые антонимы¹; некоторые родовидовые синонимы²; существительные, обозначающие лиц мужского и женского пола³);

3. Другие типы (дериваты; образные наименования; фрагменты толкования; энциклопедические синонимы⁴; исторические синонимы; словосочетания с исключением внутреннего члена; словосочетания с различными реализациями одного из актантов главного слова термина⁵; термины, тесно связанные отношениям причина-следствие и др.; термины, несущие в себе дополнительную модальность по отношению к основному термину⁶; термины, совпадающие в одной своей части, а в другой – состоящие из ситуационно связанных терминов⁷; термины, в которых словосочетание с неоднозначным термином становится однозначным).

1. Проблема текстовых ресурсов.

К задачам лингвистики относят, с одной стороны, идентификацию структурных единиц (например, морфемы, слова, фразы) и описание того, как одни структурные единицы формируют другие, более крупные (например, по каким правилам можно строить из слов фразы). С другой стороны, благодаря наличию текстов и аудио записей, изучают речь в том виде, как мы её слышим. В этом случае необходимо наличие корпуса – набора текстов с грамматической, синтаксической разметкой или без таковых. Среди множества проблем создания корпуса, можно выделить общую проблему отсутствия единого стандарта и сложности практического характера: опечатки, сохранение переносов в тексте [55]. Данная работа непосредственно связана с корпусной лингвистикой. Проблемы корпусной лингвистики раскрываются в работах [82], [133], [174]. В диссертации в качестве корпуса текстов предлагается использовать коллективную онлайн энциклопедию Википедия. Это позволяет решить в какой-то мере проблему стандарта (все статьи унифицированы, а именно: есть стандартные метаданные – заголовок статьи, категории, определяющие тематику статьи), но появляются новые сложности (например, проблема неравномерности количества и качества статей в зависимости от тематики)¹.

Одной из первых работ в области компьютерного семантического анализа можно считать построение «Русского семантического словаря» компьютером в 1982 (группа под руководством чл.-корр. АН СССР Ю. Караулова). Программа сравнивала описание значений слов в разных словарях. При наличии сходства в описании, программа относила слово к одной группе, то есть считала слова сходными по значению. Таким образом, программа является является автоматическим понятийным классификатором слов [48].

2. Требования к корпусу проблемно-ориентированных текстов

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

1. Каждому текстовому документу (далее «статья») соответствует одно или несколько ключевых слов, отражающих содержание статьи. Например, в случае энциклопедии – энциклопедической статье соответствует одно слово – название статьи.

2. Статьи связаны ссылками. Для каждой статьи определены: набор исходящих ссылок (на статьи, которые упоминаются в данной статье) и входящих ссылок (на статьи, которые сами ссылаются на данную статью).

3. Каждая статья соотнесена одной или нескольким категориям (тематика статьи). Категории образуют дерево таким образом, что для каждой категории есть родитель-категория (кроме корня) и один или несколько детей-категорий (кроме листьев).

Данная структура является не абстрактным измышлением. Она имеет конкретное воплощение в структурах типа вики (wiki), получивших широкое распространение в последнее время в сети Интернет, например, в виде электронной онлайн энциклопедии Википедии¹; “вики используется российскими органами власти² и Департаментом образования Москвы³ при создании административных интернет-сайтов.”⁴

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

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

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

1. поиск на основе анализа ссылок (вычисления на графах)

1. ссылки заданы явно гиперссылками (HITS [125], PageRank [85], [102], ArcRank [174], Green [145], WLVM [134]);

2. ссылки нужно построить³ (Similarity Flooding [132], алгоритм извлечения синонимов из толкового словаря [84], [83], [174]);

2. поиск на основе анализа текста:

1.  статистические алгоритмы (ESA [103], сходство коротких текстов [159], извлечение контекстно связанных слов на основе частотности словосочетаний [146]);

2.  автоматическое понимание текстов⁴;

3. поиск на основе анализа и ссылок и текста [81], [129]⁵.

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

Входными данными могут быть [106]:

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

2. идентификатор документа, будут искаться документы, похожие на заданный.⁶

Алгоритмы анализа гиперссылок: HITS, PageRank, ArcRank, WLVM

1. Алгоритм HITS²

Алгоритм HITS (Hyperlink-Induced Topic Selection)³ позволяет находить Интернет страницы, соответствующие запросу пользователя, на основе информации, заложенной в гиперссылки [125]. Демократическая природа Интернет позволяет использовать структуру ссылок как указатель значимости страниц (эта идея есть и в алгоритме PageRank [85], встроенном в поисковик Google). Страница p, ссылаясь на страницу q, полагает q авторитетной, стоящей ссылки. Для поиска существенно, что страница q соответствует тематике страницы p.

Поиск в Интернет (Web search) – это нахождение релевантных страниц, соответствующих запросу. Можно выделить два крайних типа запросов: конкретный (проблема недостатка страниц) и чрезмерно общий (проблема избытка страниц). При наличии общего запроса ставится задача дистилляции широких поисковых тем с помощью авторитетных источников по этим темам.

HITS алгоритм использует такие понятия, как: авторитетный документ и хаб-документа (или авторитетная и хаб-страница). Авторитетный документ – это документ, соответствующий запросу пользователя, имеющий больший удельный вес среди документов данной тематики, то есть большее число документов ссылаются на данный документ. Хаб-документ – это документ, содержащий много ссылок на авторитетные документы.⁴

2. Алгоритм PageRank (отличия от алгоритма HITS)

Параметр PageRank страницы p(i) (её авторитетность) определяется так [102]:

где N – общее число страниц; j→i обозначает гиперссылку от страницы j к странице i; K_out(j) – это число исходящих ссылок страницы j; (1-q) – амортизирующий коэффициент (damping factor)¹. Набор уравнений (1.1) решается итеративно.

Оба алгоритма: PageRank и HITS предлагают общую идею итеративного вычисления авторитетных страниц, где авторитетность определяется наличием (количеством) и характером (степень авторитетности источника) ссылок. Однако есть и разница. Отличие алгоритма PageRank от алгоритма HITS в том, что у каждой страницы только один параметр, который соответствует её популярности, это вес PageRank. В алгоритме HITS каждой странице сопоставлено два параметра, которые определяют авторитетность и наличие ссылок на авторитетные страницы. Это соответственно параметры authority и hub. Отметим, что PageRank не требует дополнительных вычислительных затрат во время обработки запроса, HITS более дорогой с вычислительной точки зрения алгоритм.

В работе [89] указывают на сходство результатов работы HITS и PageRank². Большинство документов, полученных как авторитетные в HITS, были представлены в результатах PageRank, но упорядочены были по другому. Однако в другой работе [80] при поиске авторитетных страниц с помощью алгоритмов HITS и PageRank по всей Английской Википедии и по некоторым подмножествам страниц (например: People, Historical Events, Countries and Cities)¹ были получены в общем разные классы концептов. Также в работе [145] приводятся эксперименты по сравнению различных методов поиска похожих статей в ВП, в том числе сравнивают работу алгоритмов LocalPageRank² и PageRankOfLinks (аналог PageRank) в пользу последнего. Авторы [145] делают вывод, метод HITS ищет хуже похожие статьи в ВП, чем PageRank, поскольку считают метод LocalPageRank аналогичным методу HITS. Скорее всего, это не верный вывод, поскольку LocalPageRank и HITS – разные алгоритмы – они используют разное число весов для каждой страницы. Таким образом, требуются дополнительные исследования по сравнению алгоритмов с помощью экспериментов.

О популярности алгоритма PageRank говорит наличие нескольких его модификаций. В работе [145] предложены методы Green, SymGreen для поиска «вершин, семантически связанных с исходной». Эти методы являются модификациями алгоритма PageRank на основе Марковских цепей.

3. Алгоритм распределения рангов (ArcRank)

Алгоритм предназначен для поиска семантически близких слов, а не синонимов. ArcRank вычисляет рейтинг вершин аналогично алгоритму PageRank. Небольшая модификация в том, что вершинам источникам³ и висячим вершинам⁴ не присваиваются предельные значения.

В ArcRank дугам назначаются веса на основе весов вершин. Если |a_s| – число исходящих дуг из вершины s, p_t – вес вершины t, тогда важность (relevance) дуги (s,t) определяется так [174]:

При выборе слов, связанных с w, первыми выбираются те рёбра, инцидентные w, которые имеют больший вес.

Алгоритм WLVM

Алгоритм векторной модели ссылок Википедии (англ. Wikipedia Link Vector Model или WLVM) вычисляет сходство двух статей ВП на основе содержащихся в них ссылок [134]. Алгоритм включает шаги:

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

2. обработать ссылки (разрешить «редиректы»¹; для ссылок на страницы «дизамбиги»² взять все ссылки, перечисленные на «дизамбигах»);

3. подсчитать вес ссылок (см. ниже);

4. построить вектор (исходящих) ссылок для каждой страницы;

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

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

Вес ссылки с исходного документа на целевой определяется по правилам:

• 1 или 0, если есть или нет такая ссылка в исходном документе;

• обратно пропорционально общему числу ссылок на целевой документ.

А именно, вес ссылки w со страницы a на страницу b рассчитывается по формуле: , где t — общее число страниц в ВП.

Для оценки алгоритма использовался тестовый набор 353-TC.³ Была предпринята малоуспешная попытка автоматически выбирать верное значение для ссылок на многозначные статьи: коэффициент корреляции Спирмена с эталонным набором оказался равным 0.45, при разрешении многозначных статей вручную — 0.72. Доступна реализация WLVM алгоритма.¹

Алгоритмы построения и анализа ссылок: Similarity Flooding, алгоритм извлечения синонимов из толкового словаря и другие

Одна из задач, рассматриваемых в диссертации², относится к типу задач scheme / ontology alignment (другое название – scheme / ontology matching). Суть этой более общей задачи в том, что «на входе есть две схемы / онтологии, каждая из которых состоит из дискретных сущностей (например, таблицы, XML элементы, классы, свойства, правила, предикаты), на выходе должны быть получены отношения (например отношение эквивалентности, отнесение к некоторой категории), связывающие эти сущности» [164].

Этот тип задач замечателен тем, что включает и лексическую³, и семантическую⁴ компоненты. Обзор современных работ по scheme / ontology matching представлен в [164], критический обзор открытых (open source) программных систем изложен в [190].

Кратко опишем несколько работ, посвящённых данной теме. Затем более подробно осветим алгоритм Similarity Flooding и алгоритм извлечения синонимов из толкового словаря.

Итак, в работе [77] для обнаружения неявных (latent) связей между вершинами считают число общих соседей двух вершин. Сходство двух вершин (relevance measure) вычисляется как отношение числа общих вершин к числу всех соседних вершин ([77], стр. 3). Авторы поставили себе общую задачу – обнаружение отношений в семантическом графе⁵. Эксперименты заключались в предсказании возможных атак и уязвимостей служб безопасности на основе видеофильмов и данных терактов.

Поиск похожих вершин в графах возможен с помощью поиска соответствий между вершинами (отображений). Во-первых, точное соответствие, одна вершина к одной (рассматривается в данной работе, стр. 86). Во-вторых, неточное – многие к одной или многие к многим, то есть кластер концептов отображается в один концепт. В работе [97] предложен алгоритм неточного сравнения графов онтологий¹ на основе максимизации ожидания². Онтология представлена в виде направленного графа с метками.

1. Алгоритм Similarity Flooding

Кратко опишем один из алгоритмов, решающих описанную выше задачу scheme / ontology alignment, – алгоритм Similarity Flooding, ключевая идея которого в том, что «два элемента считаются сходными, если сходны их соседи. Сходство двух элементов распространяется на их соседей» [132]. На первом шаге в соответствии с входными схемами, которые нужно сравнить (например SQL таблицы или запросы), строятся два графа. На втором шаге задаются начальные значения сходства между вершинами двух графов, путём сравнивая имён вершин. На третьем шаге итеративно вычисляется сходство вершин до тех пор, пока суммарное изменение степени сходства по всём вершинам больше наперёд заданного ε. Значение сходства между вершинами учитывается для вычисления сходства соседних вершин. На четвёртом шаге выбираются наиболее похожие пары вершин.

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

4. Алгоритм извлечения синонимов из толкового словаря

В работах [84], [83], [174] французские учёные, под руководством Винсента Блондела (Vincent Blondel), предлагают обобщение HITS алгоритма для поиска синонимов в толковом словаре.¹

Предположим, что (1) синонимы имеют много общих слов в определениях (в статьях толкового словаря); (2) синонимы часто употребляются в определении одних и тех же вокабул². Построим граф G, в котором вершины соответствуют вокабулам словаря. Строится дуга от вершины u к v, если слово, соответствующее v, встречается в определении вокабулы u.

Пусть ищем синонимы для слова w. Для этого строим G_w (подграф графа G), включающий (1) все вершины из G, ссылающиеся на w и (2) все вершины, на которые ссылается w. Считаем сходство слов относительно слова w, чтобы выбрать лучшие слова как синонимы.

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

• 
  Вес равен сумме весов всех вершин j, на которые указывает вершина i;

• Значение равно сумме весов (вершин, на которые указывает вершина i) и (вершин, указывающих на i).

• Значение равно сумме весов вершин, указывающих на i.

На каждом шаге веса одновременно обновляются и нормализуются. Синонимами считаются слова с максимальным значением (центральный вес). Вычисления проводились на английском словаре Вебстера. Построенный граф содержал 112 169 вершин, 1 398 424 рёбер.

Алгоритмы статистического анализа текста: ESA, поиск контекстно-связанных слов

Алгоритм ESA

В работе [103] авторы описали алгоритм ESA, позволяющий представить значение любого текста в терминах концептов ВП.¹ Оценка эффективности метода выполнена за счёт автоматического вычисления степени семантической связи между фрагментами текста произвольной длины на ЕЯ.

Для ускорения работы построили инвертированный индекс: слову соответствует список концептов, в статьях которых оно появляется. Была выполнена предобработка концептов ВП:

• удалили концепты, которым соответствуют небольшие статьи (меньше 100 слов, меньше 5 исходящих и входящих ссылок);

• удалили стоп-слова и редкие слова;

• получили леммы слов (тексты на английском языке).

В алгоритме ESA на вход подаются два текста. По ним строятся два вектора из концептов ВП следующим образом. По фрагменту текста (1) строится вектор по TF-IDF схеме, (2) из инвертированного индекса выбираются концепты и объединяются во взвешенный вектор². Произведение этих векторов и даёт вектор концептов ВП релевантных фрагменту текста. Для сравнения текстов сравнивают два вектора, например, с помощью косинусного коэффициента.

Эксперименты в работе [103] показали преимущество ESA в точности поиска семантически близких слов в ВП по сравнению с алгоритмами поиска LSA [100], WikiRelate! [173] и других, выполняющими поиск на основе данных WordNet, Роже и ВП. Достоинство метода также в том, что он позволяет определять значение многозначного слова.

Метод извлечения контекстно связанных слов

Метод извлечения контекстно связанных слов на основе частотности слово­сочетаний предлагается в [146] для поиска контекстно похожих слов (КПС) и для машинного перевода. Данными для поиска КПС служат (1) семантически близкие слова из тезауруса, (2) словосочетания из базы данных (БД) с указанием типа связи между словами. Для слова w формируется cohort w, то есть группа слов, связанных одинаковыми отношениями со словом w, из базы словосочетаний. КПС слова w – это пересечение множества похожих слов (из тезауруса) с cohort w. Работа [146] интересна формулами, предлагаемыми для вычисления сходства между группами слов.

Обычно вычисляется сходство между отдельными парами слов. В работе [146] вычисляется сходство между группами слов G₁ и G₂ на основе формул, предложенных в [122]. Вершины графа – слова, взвешенные рёбра указывают степень сходства между словами (таким образом, матрица инциденций – sim – матрица сходства, хранит сходство между отдельными элементами). Вычисляются:

AI – absolute interconnectivity (абсолютная связность), как суммарная сходство между всеми парами в группах: .

AC – absolute closeness (абсолютная близость или плотность) определяется как среднее сходство между парами элементов:

Разница между AI и AC в том, что в AC учитывается пары имеющие нулевое сходство (рис. 1).

В [122] предлагает нормализовать абсолютную связность и близость за счёт вычисления внутренней связности и близости отдельных групп. Внутренняя связность и близость определяются на основе вычисления разбиения каждой группы (поиск за O(N) минимального числа рёбер, удаление которых приведёт к разбиению графа на две части).

Рис. 1. Пример, иллюстрирующий разницу между мерами AI и AC. Значение AI в случаях (a) и (b) остаётся постоянным, но значение AC в случае (a) больше, поскольку в (b) больше вершин, не имеющих похожих вершин [146]

Можно упомянуть ещё ряд статистических алгоритмов для вычисления семантической близости слов: LSA [100], PMI-IR [180].

Метрики

Выделяют несколько способов определения похожих документов¹ [53]. Полагаем, что документы и запросы представляются с помощью индексных терминов или ключевых слов. Обозначим посредством символа |.| – размер множества ключевых слов, представляющих рассматриваемый документ. Простой коэффициент соответствия показывает количество общих индексных терминов. При вычислении коэффициента не берутся в рассмотрение размеры множеств X и Y.

Таблица 1.1

Коэффициенты сходства для документов, для ключевых слов [53]

Формула	Название
	Коэффициент Дайса (dice)
	Коэффициент Джаккарда (jaccard)
	Косинусный коэффициент
	Коэффициент перекрытия

В таблице 1.2 показаны способы вычисления степени сходства, основанные на учёте:

• частотности слов в корпусе;

• расстояния в таксономии;

• одновременно и частотности слов, и расстояния в таксономии.

Таблица 1.2

Классификация метрик и алгоритмов вычисления степени сходства слов

Расстояние Google – это мера семантической связности, вычисленная на основе числа страниц, полученных с помощью поисковика Google для заданного набора ключевых слов. В таблице приведена формула вычисления нормализованного расстояния Google (NGD) для двух слов: x и y, где М – это общее число веб-страниц, проиндексированных Google; f(x) и f(y) – число страниц, содержащих ключевые слова x и y, соответственно; f(x, y) – число страниц, содержащих сразу и x, и y. Если x и y на всех страницах встречаются вместе, то полагают NGD=0, если только по отдельности, то NGD=∞.

Выделим класс метрик, вычисляющих сходство на основе данных таксономии (табл. 1.2). Данные метрики используются для вычисления сходства концептов WordNet [74], [99], [128], [151], [152], [186], GermaNet [139], ВП [173].

В книге [99] Leacock и Chodorov предложили вычислять близость концептов как расстояние между концептами в таксономии, нормализованное за счёт учёта глубины таксономии. В формуле , функция length(c₁, c₂) – это число вершин вдоль кратчайшего пути между вершинами c₁ и c₂; D – максимальная глубина таксономии. В работе [99] авторы рассмотрели только одно отношение is-a и только между существительными.

В работе [186] предложена формула, учитывающая как глубину концептов в иерархии, так и глубину ближайшего общего родителя lcs (least common subsumer): .

Резник [151] предложил считать, что два слова тем более похожи, чем более информативен концепт, к которому соотнесены оба слова, то есть чем ниже в таксономии находится общий верхний концепт (синсет в WordNet).¹ При построении вероятностной функции P(C), потребуем, чтобы вероятность концепта не уменьшалась при движении вверх по иерархии: . Тогда более абстрактные концепты будут менее информативны. Резник предложил оценивать вероятность через частоту синонимов концепта в корпусе таким образом: ,, где words(C) – это существительные², имеющие значение C; при этом N – общее число существительных в корпусе. Пусть, если для двух концептов ближайшим общим концептом является корневая категория, то сходство равно нулю.

В работе [173] метрика Резника res была адаптирована к ВП и информативность категории P(C) вычислялась как функция от числа гипонимов (категорий в ВП), а не статистически³ (то есть не посчитали частотность термов в ВП):

,

где lcs — ближайший общий родитель концептов с₁ и с₂, hypo — число гипонимов⁴ этого родителя, а С — общее число концептов в иерархии.

Lin [128] определил сходство объектов А и B как отношение количества информации, необходимой для описания сходства А и B, к количеству информации, полностью описывающей А и B. Для измерения сходства между словами Lin учитывает частотное распределение слов в корпусе текстов (аналогично мере Резника): , где c₀ – ближайший общий супер-класс в иерархии для обоих концептов c₁ и c₂. P – вероятность концепта, вычисляемая на основе частоты появления концепта в корпусе. Отличается от формулы res способом нормализации, корректным вычислением lin (x, x) (не зависит от положения концепта х в иерархии), учитывает наличие и общих, и различающихся свойств у объектов [152].

В работе [173] мера lesk, основанная на вычислении степени пересечения глосс концептов WordNet, была адаптирована к ВП (за глоссу авторы взяли первый абзац в статье ВП). Итак, сходство двух текстов t₁, t₂ вычисляется с двойной нормализацией (по длине текста и с помощью гиперболического тангенса) так:

,

, где пересекаются n фраз, m слов¹.

В работе [139] (стр. 4) приведённая в таблице 1.2 формула lin была адаптирована к поиску в структуре GermaNet. В данной работе приведены две TF-IDF схемы для вычисления сходства между запросом и текстом документа.

Глава о метриках была бы неполной без упоминания того, что кроме сходства, метрики позволяют вычислять степень различия объектов. Так например, в задачах кластеризации используются функции, определяющие степень различия² между документами. Если P – множество объектов, предназначенных для кластеризации, то функция D определения степени различия документов удовлетворяет следующим условиям [53]:

1. для

2. для

3. для

4. для

При анализе свойств Интернет сетей¹, при оценке свойств графов, созданных с помощью генератора случайных чисел, используют такие метрики [130]:

1. Распределение расстояний d(x) – число пар вершин на расстоянии х, делённое на общее число пар n² (включая пары типа (a,a));

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

3. вероятностное распределение вершин P(k) – число вершин степени k в графе;

4. правдоподобие (likelihood) – сумма произведений степеней смежных вершин;

5. кластеризация² С(k) – отношение среднего числа ссылок между соседями вершины степени k к максимально возможному числу таких ссылок .

2. Системы и ресурсы для обработки текста

Автоматическая обработка текстов (АОТ) на естественном языке (ЕЯ) подразумевает наличие как программных систем¹, обрабатывающих тексты, так и корпусов, содержащих эти тексты. Общие проблемы создания программных систем рассматриваются в работе [12].

В данной работе под корпусом текстов понимают «набор текстов доступных для машинной обработки, на основе которых можно проводить какие-либо лингвистические исследования» [133].

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

GATE

3. Система GATE (General Architecture for Text Engineering) предлагает инфраструктуру для разработки и внедрения программных компонент с целью обработки текста на ЕЯ. Эта система (i) определяет архитектуру, то есть способ организации данных и программных компонент, обрабатывающих текст, (ii) предлагает реализацию архитектуры (набор классов, который может встраиваться в программные приложения независимо от GATE), (iii) помогает разрабатывать и использовать компоненты с помощью графического инструментария [92].

Система GATE написана на языке Java [8], [25], [68], [115], имеет модульную структуру, предоставляется на правах лицензии GNU library licence². С научной точки зрения достоинство GATE заключается в возможности проводить численные измерения текста, которые можно повторить. В работе [109] критикуют систему GATE за плохую масштабируемость и за то, что она плохо справляется с большими коллекциями документов. Однако отмечают «большой потенциал GATE как инструмента для планирования и разработки приложений АОТ в области Information Extraction».

Модульность архитектуры позволяет (i) включать только необходимые компоненты, (ii) использовать имеющиеся наработки, (iii) начать работу с уже существующими компонентами, по мере необходимости, создавая новые.

В системе GATE можно выделить компоненты, не зависящие от языка текста (например Doc Reset) и зависящие (например, English POS Tagger). Система GATE позволяет обрабатывать документы на таких языках, как: английский, французский, немецкий, арабский, китайский и др. Это определяется наличием соответствующего модуля.

В системе GATE предложен следующий способ автоматической аннотации текстовых документов.¹ GATE позволяет связать подстроку текста документа (слово, фраза, предложение) с аннотацией. Аннотации описывают иерархическое разбиение текста, простой пример – это разбиение текста на слова (tokens). Более сложный пример (при полном синтаксическом анализе) – это декомпозиция предложения на именную, глагольную группы слов с выделением главного слова и т. п.

Отсутствуют (по крайней мере, неизвестны автору) доступные модули в системе GATE для морфологической обработки русского языка. Возможно, поэтому система GATE редко упоминается в системах обработки текстов на русском языке. Отрадное исключение представляют работы [64], [98], где представлены архитектура и реализация системы OntosMiner.

Для оценки качества функционирования систем Information Extraction (IE) используются такие метрики, как: точность (Precision), полнота (Recall) и качество (F-measure)². В работе [64] предлагается новая система метрик, в которой «аннотация представляется в формате, где явно специфицированы тип выделенного объекта (отношения) и его атрибуты, а также расположение аннотации в тексте относительно его начала (Offsets)». С одной стороны, указание типа объекта и положения подстроки в тексте (Offsets) сужает понятие объекта (именно объектами оперируют метрики точность, полнота и качество). С другой стороны, новые метрики подходят для оценки качества функционирования IE систем, построенных на основе GATE, поскольку тип объекта и положения подстроки в тексте включены в аннотации GATE.

Небольшой обзор систем, подобных GATE, а именно: KIM, TEXTRACT, Textpresso, Ogmios, представлен в работе [109].

Проект Диалинг

В данном подразделе дано краткое описание модулей автоматической обработки текста и морфологических словарей, разработанных рабочей группой Aot.ru [60]. Изначальный проект, посвящённый разработке русско-английского машинного перевода, назывался Диалинг. Разработанный процессор Диалинг включает графематический, морфологический и синтаксическим модули. Программная реализация процессора выполнена на языке C++. «Неоспоримым достоинством процессора Диалинг является его завершённость: программная реализация доведена до уровня промышленного использования, – система характеризуется приемлемой скоростью анализа и устойчивостью на открытом пространстве реальных текстов» (цит. по [47]).

Морфологический словарь, или лексикон, содержит все словоформы одного из языков: английский, немецкий или русский. Словарь предоставляется в двух вариантах: с возможностью редактирования и в бинарном варианте. Оболочка редактирования словаря позволяет выполнять: (i) поиск в словаре по лемме, словоформе, морфологической интерпретации, (ii) редактирование словаря. Словарь в бинарном формате предоставляет возможность выполнять: (1) морфологический анализ (получение по словоформе леммы, её свойств, уникального ID леммы, морфологических характеристик входной словоформы¹ и (2) морфологический синтез (получение по уникальному ID леммы всей парадигмы слова со всеми словоформами и их морфологическими характеристиками). Бинарное представление словаря оптимизировано для проведения морфологического анализа. Основу этого представления составляет конечный автомат. Работает морфологическое предсказание слов, отсутствующих в словаре [60].

В прикладной части данной диссертационной работы для нормализации слов используется программа морфологического анализа (Lemmatizer)¹. Например, для текста «смерч обрушился на южные селенья» нормализованным вариантом будет – «смерч обрушиться на южный селение» [31].

Тезаурусы WordNet, РуТез, Викисловарь

Тезаурус – это сложный компонент словарного типа, отражающий основные соотношения понятий в описываемой области знаний [41]. Тезаурусы включают всю терминологию, специфическую для предметной области (ПО), а также парадигматические отношения² между понятиями ПО. Тезаурус может выполнять разные функции в разных системах [41]:

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

• является инструментом поиска в ИПС [17];

• является инструментом ручного индексирования документов в ИПС (так называемый контролирующий словарь);

• является инструментом автоматического индексирования текстов.

Одним из наиболее успешных проектов, связанных с тезаурусами, является WordNet³ [99] – тезаурус английского языка, представляющий состав и структуру лексического языка в целом, а не отдельных тематических областей [1]. WordNet группирует наборы слов со схожим значением в синсеты¹ (от англ. synonym set, synset). WordNet содержит синсеты, краткие общие определения к синсетам (глоссы), примеры употреблений и несколько типов семантических отношений между синсетами. Авторы преследовали двоякую цель: объединить возможности тезауруса и наглядность словаря, а также создать ресурс для автоматической обработки текстов на естественном языке. База данных и программа выпущены на условиях BSD лицензии. Возможен онлайн доступ к содержимому базы данных.

WordNet был разработан в 1985 г. Работа над ним ведётся сотрудниками Лаборатории когнитологии Принстонского Университета (США) под руководством профессора психологии Дж. Миллера. К 2005 г. WordNet содержал около 150 тыс. слов, организованных в более чем 115 тыс. синсетов, всего 203 тыс. пар слово-значение. Словарь состоит из 4 файлов, соответствующих таким частям речи, как: существительное, глагол, прилагательное и наречие.

Семантические отношения связывают большинство синсетов. Представлены такие семантические отношения, как: гипонимия (родовидовое), меронимия (часть-целое), лексический вывод (каузация, пре-суппозиция) и др.

Гипонимия позволяет организовывать синсеты в иерархические структуры (деревья). Гипонимия связывает слова, «между содержанием понятий которых существует отношение семантического включения, то есть значение гиперонима полностью включено в значение гипонима» [1]. Например, значение слова бояться включено в значение слов опасаться, остерегаться.

Разработаны способы вычисления семантического расстояния между концептами либо словами с помощью тезауруса WordNet, например: мера Leacock-Chodorow [99],² меры на основе частотности концептов в корпусе (мера Резника [151], [152], мера Jiang-Conrath [120], мера Lin [128]), мера Hirst-St.Onge, мера пересечения расширенных глосс¹. В работе [87] проведены эксперименты по сравнению пяти мер, вычисляющих семантическое расстояние между терминами WordNet. Эксперименты показали, что лучшие результаты даёт мера JiangConrath. Также обзор нескольких мер и эксперименты с ними представлены в диссертации итальянского учёного Calderan M. [90].

Данные WordNet используются для решения таких задач, как определение значения слова (WSD²) [138]³, [153], [187], вычисление логичности и связности предложений в тексте [110], [175], построение баз знаний [17] и тезаурусов.

В работе [154] авторы задались целью показать, что комбинация эвристик позволяет построить полную таксономию современного словаря на любом языке. В результаты были разработаны: (1) метрика расстояния между двумя словами (в двуязычном словаре) на основе таксономии гипонимов / гипернимов WordNet, (2) эвристики (и методика их интеграции) для определения значения (WSD) родовых терминов⁴ двух словарей, (3) построена таксономия для испанского и французского языков на основе машинных словарей DGILE (испанский) и LPPL (французский).

Работа [121] интересна критикой WordNet. Авторы предложили итеративный способ решения задачи WSD на основе корпуса и словаря. Слова считаются похожими, если встречаются в похожих предложениях. Предложения похожи, если содержат похожие слова. Авторы разработали меры сходства сходства слов и предложений, обладающие особенностями: ассиметричность, транзитивность, сходимость. Благодаря транзитивности данный метод позволяет оценивать сходство редких фраз, отсутствующих в корпусе. Были использованы данные словарей Webster, Oxford и WordNet. В экспериментах WordNet показал слабые результаты. Возможные причины таковы [121]:

• архитектура WordNet не предназначена для хранения данных о контекстном сходстве;

• расстояние в дереве WordNet (длина пути между концептами) не всегда соответствует интуитивным представлениям сходства слов, так как разные концепты находятся на разном уровне абстракции, имеют разное число гиперонимов.

Система WordNet используется во многих современных проектах, что, в свою очередь, приводит к появлению научно-исследовательских проектов, направленных на улучшение самой базы WordNet. В работе испанских учёных [158] предлагается использовать данные энциклопедии Википедия для расширения сети концептов WordNet. Авторы предлагают способ автоматического установления соответствия между статьями энциклопедии и концептами онтологии (здесь – семантической сети WordNet).¹ Для решения задачи авторы строят упрощённую версию Английской Википедии² таким способом, что из всех статей оригинальной Википедии были выбраны только те, заголовкам которых был найден соответствующий концепт в WordNet.³ Для вычисления метрики сходства между статьёй Википедии и концептом WordNet использовалась модель VSM (Vector Space Model).

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

«Каталог семантических переходов» – база данных регулярно воспроизводимых лексико-семантических изменений, засвидетельствованных в различных языках мира [21]. В этой БД выделено шесть типов семантических переходов (смысловых связей между словами), интересных с точки зрения изучения этимологии слов и создания этимологических словарей:

• полисемия;

• семантическая эволюция – изменение значения слова на разных временных срезах одного и того же языка;

• когнаты – «лексемы с двумя значениями, находящимися в отношении семантической производности, в родственных языках восходят к одной лексеме праязыка, в которой предположительно отсутствует соответствующая полисемия» [21];

• заимствование – семантическая адаптация иноязычных слов, в ходе которой может измениться значение слова;

• морфологическая деривация – образование новых значений при добавлении аффиксов (например «любить» – «любой»);

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

Особенностью другой системы – тезауруса РуТез [41] является автоматическое индексирование. Термины тезауруса делятся на дескрипторы и варианты (синонимы) дескрипторов. Дескрипторы представлены отдельными существительными и именными группами. Синонимами могут быть две упомянутые грамматические группы, а также отдельные прилагательные, глаголы и глагольные группы. Применяются следующие правила включения дескрипторов в тезаурус:

1. Наличие связи с другими дескрипторами;

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

В РуТез включаются термины, не упоминавшиеся в текстах, если они: (а) нужны для объединения разрозненных дескрипторов, (б) пополняют ряд нижестоящих дескрипторов для уже существующего дескриптора. Предусмотрено включение многозначных терминов, а именно: несколько значений одного термина представляются разными дескрипторами. Если только одно значение многозначного термина включено в тезаурус, то дескриптор снабжается пометой «М». В тезаурус включены фразеологизмы, в состав которых входят термины тезауруса: например, как с гуся вода, водой не разольёшь и др. Отношения в тезаурусе (ВЫШЕ-НИЖЕ¹, ЦЕЛОЕ-ЧАСТЬ², АССОЦИАЦИЯ) позволяют представить тезаурус в виде связной иерархической сети (разрешена только одна компонента связности).

Достоин упоминания тезаурус GEMET³. Интересными особенностями тезауруса является привязка концептов ко многим языкам (в том числе к русскому), предоставление данных с помощью веб-сервиса (RDF). Авторы GEMET планируют улучшить данные тезауруса за счёт включения его в Английский Викисловарь⁴ и отдачи со стороны пользователей Викисловаря.

Викисловарь является с одной стороны вики-ресурсом, поэтому в его пополнении может участвовать каждый, с другой – это толковый, грамматический, фразеологический, этимологический и многоязычный словарь, в том числе и тезаурус.⁵ Русский Викисловарь содержит следующие семантические отношения: синонимы¹, антонимы², гиперонимы, гипонимы, согипонимы, холонимы, меронимы, паронимы³, омонимы⁴.

Разработка словарей требует огромных вложений времени и сил. Поэтому тезаурусы WordNet, Роже покрывают небольшую часть лексикона, и содержат мало имён собственных, неологизмов, жаргонных слов, специальной терминологии [103]. Можно надеяться, что благодаря вики-технологии такая ситуация не грозит Викисловарю. На 10.11.2007 Викисловарь содержал 130 тыс. слов и словосочетаний более чем на 180 языках.

4. Вики-ресурсы

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

Ward Cunningham, разработчик первого вики-сайта WikiWikiWeb, первоначально описал вики как «простейшую онлайн базу данных, которая, возможно, работает».⁶ Также вики – это часть программного обеспечения на стороне сервера, позволяющая пользователям коллективно создавать и редактировать содержания интернет страниц с помощью любого интернет браузера. Язык вики поддерживает гиперссылки (для создания ссылок между вики-страницами) и является более наглядным чем HTML и безопасным (использование JavaScript и Cascading Style Sheets ограничено).⁷

Концепция «свободного редактирования» имеет свои достоинства и недостатки. Открытость в редактировании текстов привлекает технически не подкованных пользователей, что позволяет развивать уже существующие вики ресурсы. К проблемам стоит отнести борьбу с вандализмом. Эта проблема решается благодаря возможности отката.¹ Другой вопрос – надёжность и достоверность информации – может быть решён либо с помощью внешних признаков (число правок, число авторов статьи, число внутренних ссылок), либо с помощью специальных программ.²

Таким образом, появился новый формат электронных документов – вики.³ Причём в Интернете насчитывается уже 25 тыс. вики-ресурсов, из них 203 состоят из более чем 10 тыс. вики-статей.⁴

Одним из наиболее успешных вики проектов считается Википедия⁵. Если на конец 2005 г. существовало более 200 Википедий на разных языках с более чем 2.8 млн статей [184], то к августу 2007 г. более 253 Википедий содержало 8.1 млн статей, а к июню 2008 г. уже более 10 млн.⁶

Цель Wikimedia Foundation (организация, ответственная за работу Википедии) – обеспечение свободного доступа ко всем знаниям, накопленным человечеством. Кроме Википедии Wikimedia Foundation поддерживает и другие проекты: открытый медиа архив (Wikicommons), открытое хранилище электронных книг (Wikibooks), база новостей (Wikinews), многоязыковой словарь и тезаурус (Wiktionary) и другие. Стоит отметить тесную интеграцию данных проектов, например, рисунки, видео или аудио файлы (неотъемлимая часть современных энциклопедий) должны быть предварительно загружены в Wikicommons, эти файлы получают уникальный идентификатор (URL), используя который можно иллюстрировать энциклопедическую статью, поставив ссылку на данный медиа ресурс. Вышеперечисленные проекты разрабатываются совместными усилиями пользователей с помощью программного обеспечения MediaWiki. Данные этих проектов распространяются по открытой лицензии GNU Free Documentation License.¹

1. Корпус текстов вики-ресурса Википедия

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

• заранее определён способ хранения документов энциклопедии в базе данных MySQL [26] (заданы таблицы, поля таблиц, связи между полями);

• существует программа MediaWiki (набор php-файлов) для просмотра и редактирования содержимого Википедии;³

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

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

• энциклопедия общедоступна¹.

Временным недостатком Википедии можно считать неравномерное распределение качества (т.е. степень проработки и глубину изложения, формально определяемые по таким признакам, как: размер страницы, число авторов, число модификаций у страницы) и количества статей по разным тематическим направлениям. В частности, указывается перевес статей технического характера (в отличии, например, от филологического), что, возможно, объясняется составом авторов энциклопедии [114].

В исследовании исторического раздела Английской Википедии [157] указано, что из 52 исторических деятелей, представленных в специализированной энциклопедии «American National Biography Online» (18 тыс. статей) в Википедии содержится только половина, в энциклопедии Encarta – одна пятая.

Более интересные (популярные) темы проработаны лучше. Общее наблюдение таково, что новые (недавно созданные) статьи – небольшие по размеру и плохо написаны, однако статьи на популярные темы, имеющие сотни и тысячи правок, приближаются по размеру и качеству к статьям профессиональных энциклопедий [157].

Сетевой анализ² Английской Википедии как графа (вершины – это статьи, рёбра – ссылки) представлен в работе [80], в которой авторы показали, что Википедия – это единый связный граф.³ Следующие эвристики, предложенные в [80], предлагается использовать для развития системы поиска синонимов Synarcher [34], [126]:

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

• удалять все статьи, начинающиеся со слов: «List of...» (так как это просто наборы ссылок), в Русской Википедии такие статьи начинаются так: «Список...».

В [162] выделяют три вида компонент в сетевой структуре: IN, OUT и компонента сильной связности (КСС). «Если пользователь начинает просмотр интернет страницы IN-компоненты, то затем он попадает в узел КСС и, возможно, в OUT-компоненту. Попав в OUT-компоненту, пользователь уже не сможет вернуться в исходную вершину. Однако пока пользователь находится внутри КСС, все вершины – достижимы и могут быть просмотрены повторно» [162]. Открытой задачей является практическая оценка статистических свойств входящих и исходящих ссылок¹, КСС и других компонент Википедии.

Кроме своей прямой энциклопедической функции Википедия, благодаря открытому доступу к её данным, служит для определения значения многозначных слов [166], может помочь в автоматическом поиске информации в запросно-ответных систем (question-answering service) и др. [157], является основой для автоматического построения многоязыкового тезауруса.²

Другие системы

Несмотря на своё название, система OpenCyc³ не является полностью открытой: данные доступны для редактирования пользователям, но код программы недоступен для расширения разработчикам [183].

С точки зрения АОТ интерес может представлять такой модуль OpenCyc, как Dictionary Assistant (DA).⁴ С помощью DA пользователи: (i) добавляют лексическую информацию, используемую системой CYC для обработки и генерации текстов на ЕЯ, (ii) выполняют привязку слов к концептам CYC.⁵ Также DA позволяет строить отношения между концептами с помощью предикатов, например для перевода фразы «Fred fancies Sally» используется предикат likesAsFriend.

Авторы MSR веб-сервера¹ предлагают, наконец, объединить реализации различных подходов по вычислению семантической близости слов с целью обеспечить доступность к результатам работы и возможность сравнить их работу на одинаковых данных. Для стандартизации доступа к приложениям предлагается CGI² интерфейс.

3. Системы и способы графического представления тезаурусов и результатов поиска

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

Система Visual Thesaurus⁴ предоставляет визуальный интерфейс к лексикону WordNet. Данная «программная адаптация интерфейса в динамическую структуру визуальных понятий в корне меняет и значительно интенсифицирует процесс обучения, освоения и применения данного продукта» [3]. Эстетически приятно оформлен ещё один визуальный онлайн WordNet интерфейс,⁵ в котором слова равномерно распределены по кругу, а множество отношений рисуется в виде дуг окружностей.

В работах [3], [39], представлен метод формирования графовой структуры данных по текстовой информации и тезаурус предметной области в виде визуальной интерактивной среды⁶. Достоинством визуального представления является «возможность воспринимать содержимое текста не последовательно, а одномоментно. Это позволяет воспринимать структуру связей предметной области в комплексе, притом именно в том, который соответствует связям, сформированным специалистом..., а не формировать его самостоятельно при прочтении груды технической документации» [39]. Плюс интерактивной среды «Визуальный словарь» (СПИИРАН) в том, что данное приложение представлено в виде HTML страницы и для работы не требует от пользователя установки дополнительных приложений.

В [185] представлен алгоритм Roark и Charniak (и реализация с визуализацией результатов) для получения упорядоченного списка слов, принадлежащих указанной категории. Алгоритм включает шаги:

1. Для данной категории выбрать примеры (так называемые «seed words», то есть начальные слова, «затравка» для алгоритма);

2. Подсчитать число сочетаний seed слов с другими словами корпуса;

3. Выбрать новые seed слова с помощью «figure of merit»¹;

4. Перейти к шагу 2, n итераций;

5. Упорядочить слова по степени принадлежности к категории (на основе «figure of merit») и выдать упорядоченный список.

Слабое место алгоритма в выборе начальных слов экспертом. Существует опасность «инфекции» – одно неправильно предложенное слово (не относящееся к категории) повлечёт за собой другие. Система, реализующая алгоритм, предназначена для автоматического создания словарей из текста на естественном языке. К достоинствам визуализации результатов можно отнести:

• Web-интерфейс. Следовательно, минимальные требования к клиенту – достаточно наличия интернет браузера;

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

Главный недостаток – это статическая картинка в качестве результата. Значит, для постановки новой задачи необходимо возвращаться на предыдущую страницу, перезагружать страницу (современные технологии, например, AJAX¹, Piccollo², Flash позволяют решить эту проблему, см. пример визуального поисковика Kartoo³).

Облако тегов (tag cloud) – это ещё один способ формирования результатов поиска для одномоментного восприятия пользователем. В поисковой системе Ontos Semantic Web [124] используется подобное облако тегов. Другой пример – система Newzingo⁴, автоматически сканирующая новости Google и представляющая их в виде облака новостей (Рис. 2).

В облаке тегов больший размер кегля (font-size) указывает на большую важность (популярность) слова. Чем больше найдено новостей, содержащих некоторое слово, тем слово будет больше. В данном случае (Рис. 2) популярными словами среди новостей технической тематики являются такие слова, как: apple, google.

Достоинство метода в том, что одним взглядом можно охватить все существенные события, все новостные сообщения. У облака новостей есть недостатки. Один из них – нет информации о динамике новостей, неясно какая тема набирает обороты, а к какой интерес угасает. В Newzingo новостная динамика представлена в виде списка новых тегов (recent tags). Другой недостаток облака новостей проявляется из-за того, некоторые темы (в силу исторических и других причин) обсуждаются регулярно (например: cars, ibm, intel, apple). Теги, соответствующие этим новостям, занимают место и заслоняют в облаке потенциально более интересные на сегодня темы.

Рис. 2. Указание на важность слова за счёт большего размера кегля (Newzingo)

Альтернативой механизму тегов (folksonomy¹) является поиск на основе пересечения данных, соотнесённых разным категориям, что представлено на отечественном сайте «Перекрестный каталог».² Категории, с одной стороны, являются альтернативой тегам, поскольку ресурс (интернет-страница, вики-страница, сайт, фотография) может иметь несколько тегов, несколько категорий (в Википедии). Можно выполнить операцию пересечения множеств и найти ресурсы, соответствующие нескольким тегам или категориям. С другой стороны, преимущество категорий в том, что они образуют иерархию. Пользователь может, отталкиваясь от данной категории, пойти к более общей либо к более частной категории.³

Действительно визуальным можно назвать приложение Flickr Graph⁴ – визуализация социальной сети, поскольку для представления вершин графа используются картинки, а именно: фотографии участников проекта flickr (рис. 3). Приложение вычисляет положение вершин графа на основе классического алгоритма притяжения-отталкивания⁵. Идею вершин-картинок можно было бы использовать для визуализации отношений между страницами Википедии. В этом случае вершины графа, соответствующие страницам Википедии, будут представлены с помощью thumb картинок¹. За пользователем можно оставить право выбора графического или текстового представления вершин графа, например, как на сайте Функциональной Визуализации (http://www.visualcomplexity.com/vc).

Рис. 3. Визуализация социальной сети в приложении Flickr Graph

Для анализа социальных сетей, получившихся в ходе работы в Википедии предназначено Java-приложение Sonivis [140].

Два следующих приложения не выполняют никакого поиска. Их задача – это анализ и графическое представление истории работы пользователя c вики сайтом.

В приложении Rhizome Navigation² анализируется история работы пользователя с вики страницами. На рис. 4 представлены вики страницы (закрашенные прямоугольники), которые посетил пользователь, и ссылки между страницами (линии). Чем дольше пользователь оставался на странице, тем больше будет по размеру соответствующий прямоугольник. Часто используемые ссылки отображаются более толстыми и короткими линиями.

Р
ис. 4. Визуальное представление просмотренных пользователем
вики страниц в приложении Rhizome Navigation

Приложение Pathway позволяет «не потеряться в бесчисленных перекрёстных ссылках Википедии»¹. Приложение визуально представляет вики страницы, посещённые пользователем, в виде сети: вершина сети – это статья, ребро – это ссылка, по которой пользователь перешёл от одной страницы к другой (рис. 5). Эту сеть можно сохранять на диск и загружать.

Ещё два приложения: WikiViz и ClusterBall, написанные одним автором, Крисом Харрисоном, позволяют визуально представлять данные Википедии. В программе WikiViz² одновременно отображается значительная часть Википедии (десятки тысяч страниц и связей между ними), однако за счёт потери интерактивности. Первоначальный учёт ссылок между статьями и категориями приводил к тому, что все вершины сливались в единое целое, в один кластер, поэтому в WikiViz учитываются только ссылки, указанные в тексте страниц.

В приложении ClusterBall³ визуализируется структура трёх уровней категорий Википедии. В центре графа отображается родительская вершина. Статьи, на которые ссылается родительская вершина, рисуются внутри шара. И, наконец, статьи, ссылающиеся на эти (внутренние) вершины отображаются во внешнем кольце. Полученные рисунки ничего не говорят о сути данных, то есть о том, какие статьи представлены, однако построенные кластеры позволяют косвенно судить о способе организации информации в Википедии, позволяют сравнить структуру Википедии с системами MVblogosphere¹, 6Bone IPv6², и Gnom³, поскольку для них получены аналогичные рисунки.

Рис. 5. История просмотра страниц Википедии в приложении Pathway

4. Постановка задачи исследования

На первом этапе исследований проведён анализ методов поиска синонимов и методов поиска похожих документов (интернет страниц, статей энциклопедии с гиперссылками и т.п.). Необходимо выполнить ряд подзадач для решения общей задачи автоматизации построения списков семантически близких слов. Был обоснован выбор HITS алгоритма для поиска. Далее необходимо, во-первых, адаптировать HITS алгоритм к поиску наиболее похожих документов в проблемно-ориентированном корпусе текстов с гиперссылками и категориями.

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

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

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

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

Выводы по главе 1

Проведённый анализ проблемы автоматизированного построения списков семантически близких слов показал, что здесь можно выделить такие основные подзадачи, как: (1) выбор текстового ресурса для поиска слов; (2) выбор и адаптация одного из перечисленных выше алгоритмов для данного текстового ресурса; (3) решение задачи оценки алгоритма и выбор текстового ресурса для оценки результатов работы алгоритма; (4) метод визуализации результатов поиска.

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

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

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

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

2. Методологическое и математическое обеспечение для построения списков семантически близких слов в корпусе текстовых документов с гиперссылками и категориями

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

1. Подход к поиску семантически близких слов

Предлагаемый подход к поиску семантически близких слов (СБС) представлен на рис. 6. Входными данными для поиска семантически близких слов являются исходное слово, корпус документов¹ и список слов, уточнённый пользователем². Последовательность взаимодействия частей системы указана на рис. 6 числами (1-7). Входными данными для поискового алгоритма являются слово, заданное пользователем (1-2), и корпус текстов (2). Алгоритм строит упорядоченный список СБС (3), а пользователь получает возможность работать с ним благодаря визуализации (4-5). В ходе работы пользователь уточняет список СБС и может запустить алгоритм повторно (6-7). Достоинствами данного подхода являются (1) визуализация результатов поиска, (2) возможность уточнения запроса в ходе работы пользователя с программой.

Рис. 6. Подход к поиску семантически близких слов

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

Авторы алгоритма извлечения синонимов из толкового словаря [84], [83] предложили гипотезу, по которой два слова считаются «почти синонимами» (near synonyms), если слова:

1. употребляются в определении одного и того же слова;

2. имеют общие слова в определениях.

Таким образом, в работах [84], [83] полагают, что если статьи толко­во­го словаря оказались семантически близкими (то есть выполняются два пунк­та, указанных выше), то и заголовки статей (слова, словосочетания) будут семан­ти­чески близкими. Назовём это гипотезой 1.

Обобщение этой гипотезы на документы с гиперссылками предложил Kleinberg [125], используя понятия авторитетных и хаб-страниц³. Обобщение таково: пусть на страницу p ссылаются хаб страницы, которые могут иметь ссылки на авторитетные страницы.

На страницу p будут похожими (similar у Kleinberg'a, семантически близкие в нашей терминологии) те из авторитетных страниц, на которые ссылаются те же хаб-страницы, которые, в свою очередь, ссылаются на страницу p. Назовём это гипотезой 2.

Использование этих двух гипотез позволит нам (1) использовать гиперссылки для поиска похожих документов, (2) считать ключевые слова (например, заголовки документа) семантически близкими для похожих документов.

Таким образом исходными данными для поисковых алгоритмов будут направленный граф (вершины – это статьи, дуги – это ссылки) и дерево категорий (вершины – категории, дуги связывают категории-родителей и категории-детей). Направленный граф и дерево связаны, поскольку вершины направленного графа (статьи) связаны с одной или несколькими вершинами дерева категорий.

Общая идея адаптированного алгоритма¹ заключается в следующем. Документы корпуса связаны друг с другом ссылками² наподобие Интернет страниц. У каждого документа есть ключевые слова, его характеризующие и ему соответствующие; в простейшем случае – это заголовок документа. Если, таким образом, для документа найдены (с помощью HITS алгоритма) похожие документы, то можно утверждать, что найдены похожие заголовки, являющиеся семантическими близкими словами для заголовка исходного документа³. Остаётся улучшить HITS алгоритм за счёт особенностей рассматриваемого корпуса текстов⁴.

Причиной использования категорий для установления связи между страницами (относительно оригинального алгоритма HITS, который оперирует только ссылками) является следующее: «входящие ссылки» (in-links), то есть ссылки на данную страницу, «содержат ссылки, связь которых с основной страницей может быть весьма слаба, в то время как в одну категорию обычно помещают страницы сходной тематики»¹.

2. HITS алгоритм (формализация, анализ, поиск синонимов)

Формализация задачи

Дан направленный граф G=(V, E), где V – вершины (Интернет страницы), E – дуги (ссылки). Для каждой страницы v известны два списка: Г⁺(v) – это страницы, на которые ссылается данная статья, и Г¯(v) – это страницы, ссылающиеся на данную статью. Необходимо найти набор страниц, соответствующих запросу s (релевантность), на которые при этом ссылаются многие страницы (авторитетность).

Обработка всех страниц, содержащих текст запроса, является вычислительно дорогой процедурой и общее число таких страниц, вероятно, избыточно (если представить их пользователю, сформулировавшему запрос). Требуется идеальная коллекция (множество страниц) S_σ: такая, что она небольшая (подходит для вычислительно «тяжёлых» алгоритмов), содержит много релевантных страниц, большинство страниц являются авторитетными (в идеале — все).

Клейнберг [125] предлагает следующий алгоритм для поиска M страниц максимально похожих (подразумевается максимальное значение веса страницы – authority) на заданную страницу v:

1. Поиск с помощью общедоступного интернет поисковика (например, AltaVista) релевантных страниц – это корневой набор S_σ (root set).

2. Расширение корневого набора (с целью включения авторитетных страниц в набор) страницами, которые связаны ссылками с корневым набором – это базовый (base) набор страниц (рис. 7).

3. Итеративное вычисление весов (authority и hub) у вершин базового набора для поиска авторитетных и хаб-страниц. Завершение итераций, когда суммарное изменение весов меньше наперёд заданного ε.

4. Выбрать M страниц с максимальным значением веса authority) из базового набора.

Рис. 7. Расширение корневого набора страниц (root) до базового (base) [125]

Каждому документу в HITS алгоритме сопоставляются веса a (authority) и h (hub), которые показывают, соответственно, насколько документ является авторитетным и насколько он является хорошим хаб-документом. Формулы алгоритма HITS для итеративного вычисления весов таковы:

где h_j и a_j показывают соответственно насколько документ j (1) является хорошим указателем на релевантные документы (то есть j-ый документ рассматривается как хаб-документ) и (2) является авторитетным документом. Доказательство сходимости итеративного процесса вычисления весов h_j и a_j, использующее собственные значения матрицы смежности графа G, представлено в [125] и [81].

Детальное описание HITS алгоритма представлено в [125]. Описание изменений в алгоритме для адаптации к поиску в вики ресурсах представлено ниже¹.

5. Дополнительные замечания

Приведём положения Клейнберга [125] и свои замечания к ним:

1) Авторитетные страницы должны быть авторитетными именно для данного запроса.

Изменение авторитетности (веса страницы) в зависимости от запроса приводит к тому, что вычисления выполняются в режиме онлайн, то есть после формулирования запроса. Остаётся открытым вопрос о возможности предварительной предобработки, позволяющей ускорить поиск авторитетных и хаб-страниц.

2) Нет такого (внутреннего) свойства страницы, по которому можно было бы определить её авторитетность.

Иначе любая страница (усилиями авторов) стала бы авторитетной. Поскольку быть авторитетной страницей значит привлекать бóльшее число пользователей, и значит быть более доходной для коммерческих сайтов.

3) Проблема: страница может не содержать слова, которым соответствует её содержание. Например страница поисковика может не содержать слова “search”.

Анализ структуры ссылок (HITS алгоритм) решает эту проблему, поскольку (например, для данного примера со словом “search”) найдутся страницы, которые содержат искомое слово и ссылаются на релевантную страницу (в данном случае на поисковик).

Глобальность HITS алгоритма в том, что ставится задача поиска лучших авторитетных страниц во всём Интернете. Отметим, что анализ ссылок (здесь) отличается от кластерного анализа, так как элементы/кластеры образуют единое целое, чего не скажешь о страницах Интернет в целом.

Проблемы HITS алгоритма [81], [89]:

• учитываются «только ссылки», что приводит к взаимному усилению веса страниц, ссылающихся друг на друга;¹

• существуют «автоматически создаваемые ссылки», то есть ссылки, созданные программой, не выражают мнение человека о значимости страницы;²

• «не релевантные документы», граф содержит документы, не соответствующие теме запроса. Возникает проблема смещения темы (topic drift) из-за того, что большой вес имеют вершины-документы о популярных предметах (то есть имеющих много входящих ссылок), но таких, что уводят в сторону от исходной темы;³

• связность, если веб-граф представляет несколько несвязанных компонент, то HITS присвоит нулевые веса hub и authority всем страницам, кроме главной компоненты.

В [81] предложено расширение HITS алгоритма за счёт анализа текста документов, что в результате повысило точность поиска, особенно для редких запросов. Вес вершины вычисляется с помощью TF-IDF схемы⁴ (сравниваются первые 1000 слов документа и слова запроса). Перемножаются значение веса authority и вес вершины (вычисленный по схеме TF-IDF), – теперь это будет новое значение authority, аналогично пересчитывается вес hub. При построении по запросу подграфа, используется вес вершины, чтобы решить – оставить вершину в подграфе или удалить в том случае, когда значение веса ниже некоторой границы (приводится 3 способа вычисления границы).

Тематическая связность авторитетных страниц

Задача – извлечь тематически связанные авторитетные страницы из коллекции страниц S_σ (см. выше). Простейший подход: упорядочить страницы по степени захода (число ссылок на страницу). Проблема такой простой схемы ранжирования в том, что могут быть найдены страницы с большой степенью захода, но тематически несвязанные.

Возможны следующие решения задачи:

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

2) Оригинальное решение (на основе решения Клейнберга). В Википедии каждой странице эксперты приписывают несколько категорий. Категории образуют дерево, то есть у каждой категории есть категория-родитель и несколько детей. Такая тематическая определённость страниц позволяет:

1. найденный список синонимов (с помощью адаптированного HITS алгоритма) разбить на кластеры, каждый из которых соответствует одному из значений исходного слова либо

2. применить кластеризацию коллекции страниц для последующего применения HITS алгоритма к каждому кластеру отдельно.

Применение способов оценки результатов поиска в Интернет к HITS алгоритму

Поиск в Интернет (Web search) – это нахождение релевантных страниц, соответствующих запросу. Оценка качества поиска основана на оценке, сделанной человеком, так как релевантность – субъективное свойство. Не хватает объективной (численной) функции для определения качества поиска.

В классических информационно-поисковых системах (ИПС) результаты ранжируются (i) пропорционально частоте термов в документе, (ii) обратно пропорционально частоте терма по всем документам (относительно ключевых слов запроса) (TF-IDF схема).

При Веб поиске дополнительно учитывается множество параметров [76]: число ссылок, которые ссылаются на страницу; текст ссылки; положение искомого слова (наличие его в заголовке даёт больший вес странице); расстояние между искомыми термами на странице; популярность страницы (число посещений); содержание текста в метаданных (metatags) [143], [93], [113]; принадлежность страницы определённой тематике; новизна ресурса; степень точности соответствия запросу.

В HITS алгоритме вес страницы распределяется равномерно между страницами, на которые она ссылается (см. формулы (2.1) и (2.2) для вычисления весов hub и authority). Предлагается учитывать положение ссылки на странице таким образом: чем выше на странице упоминается ссылка, тем больший вес она получит.

Поиск синонимов с помощью HITS алгоритма

В работах [84], [83] предложена адаптация HITS алгоритма к поиску синонимов в словаре Webster¹. Словарная статья состоит из заголовка и текста статьи. Словарные статьи ссылаются друг на друга (образуют граф) посредством упоминания слов, которые являются заголовками других статей. С помощью алгоритма HITS можно найти авторитетные² словарные статьи для исходной статьи. Авторы предполагают, что заголовки этих словарных статей будут содержать синонимы относительно заголовка исходной статьи. При построении графа словаря часть статей словаря была отфильтрована, поскольку:

• не учитываются составные слова, то есть из нескольких термов (например, All Saints', Surinam toad);

• многозначные слова рассматриваются как однозначные;

• исключили статьи, состоящие из чисел и формул (мат., хим.);

• исключили часто встречаемые слова, которые встречаются чаще чем в 1000 определений;

• рассматривались слова только той же части речи, что искомое.

Далее вычислялись авторитетные и хаб-вершины. Проводилась оценка полученных синонимов для четырёх слов разных типов [83]:

1. Слово, имеющее несколько синонимов (Dissappear);

2. Терминологическое, узкоспециальное слово (Parallelogram), в действительности не имеющее синонимов, однако существуют слова для названий предметов близких по сути (quadrilateral, square, rectangle, rhomb).

3. Многозначное слово (Sugar);

4. Общеупотребительное слово, обозначающее понятие, не имеющее однозначного определения (Science).

Авторы [83] сравнили свой метод (адаптация HITS к поиску слов в словарных статьях) с методом расстояний и методом PageRank, вычисляя синонимы для вышеуказанных четырёх слов. Их метод показал показал более хорошие результаты, чем эти два метода.

Суть метода расстояний (distance method) заключается в том, что два слова считаются синонимами, если:

• употребляются в определении одного и того же слова;

• имеют общие слова в своих определениях.

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

3. Адаптированный HITS алгоритм, включающий алгоритм иерархической кластеризации

Постановка задачи. Дан направленный граф G=(V, E), где V – вершины (текстовые документы), E – дуги (ссылки между документами). Для каждой вершины определены значения двух весовых коэффициентов authority и hub: . Для каждой страницы v известны два списка: Г⁺(v) – это страницы, на которые ссылается данная статья, и Г¯(v) – это страницы, ссылающиеся на данную статью. Задана исходная страница s. Нужно найти похожие страницы.

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

Формализация понятия «похожие вершины» графа

Необходимо найти множество вершин A, которые являются (i) авторитетными вершинами для исходной вершины s (то есть значение (2.3) больше относительно других подмножеств вершин той же мощности), (ii) похожими на исходную вершину s, то есть существует множество хаб-вершин H, ссылающихся одновременно и на исходную вершину s и на вершины из А (2.4), (iii) где H – это хаб-вершины (то есть значение (2.5) относительно других подмножеств вершин той же мощности). Задача выбрать множество A авторитетных вершин и множество H хаб-вершин в значении (2.6), где k — весовой параметр.

Адаптированный HITS алгоритм

Входные параметры алгоритма: ; ; , где

• s – исходная вершина графа (исходный документ), требуется найти вершину похожую на исходную;

• t – размер корневого набора R_s (число страниц, включаемых в корневой набор);

• d – инкремент, параметр определяет размер базового набора B_s (d входящих ссылок для каждого документа в корневом наборе будет добавлено в базовый набор, более подробно см. [125]);

• N – число похожих вершин (документов, или семантически близких слов), которые необходимо найти;

• C _max – максимально допустимый вес кластера (число статей и категорий в кластере), где под кластером понимается набор статей, связанный ссылками с другими статьями и с категориями;

• ε – допустимая погрешность для останова итераций.

Шаги адаптированного HITS алгоритма представлены в виде блок-схемы на рис. 8. Шаги, предложенные автором, выделены пунктиром. Опишем более подробно шаги 2-6 адаптированного HITS алгоритма:

2. В корневой набор (root) включаются те страницы, на которые ссылается исходная страница; может быть включено не более t страниц (вместо поиска с помощью поискового сервера – в HITS алгоритме).

3. Для каждого страницы в корневом наборе: включаем все страницы, связанные исходящими ссылками и не более d страниц, связанных входящими ссылками. Так строим базовый набор страниц (Рис. 9).

4. Итеративно вычисляются веса с помощью формул Клейнберга (2.1) и (2.2) для поиска авторитетных и хаб-страниц среди страниц базового набора. Итеративные вычисления завершаются, когда суммарное изменение весов по всем вершинам a_v и h_v за одну итерацию меньше ε.

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

Рис. 8. Адаптированный HITS алгоритм

2. Для каждого кластера базового набора выбирается множество страниц A, содержащих N статей. Причём страницы множества А являются (i) авторитетными для исходной страницы s (то есть суммарное значение весов authority страниц из A велико относительно других подмножеств страниц той же мощности), (ii) похожими на исходную вершину s в смысле наличия множества хаб-страниц H, ссылающихся одновременно и на исходную вершину s и на вершины из А¹.

Рис. 9. Построение базового набора страниц (а) в HITS и
(b) в адаптированном HITS алгоритме

Априори трудно сказать, чем лучше способ (a) или (b) при построении базового набора страниц (рис. 9). Основная задача при построении базового набора – включить как можно больше как можно более авторитетных страниц из пространства Интернет (в случае (a)), из пространства корпуса (в случае b). Оба этих подхода не могут гарантировать, что такое включение произойдёт².

6. Построение базового набора страниц

Адаптированный алгоритм построения базового набора страниц (шаги 1 и 2 адаптированного HITS алгоритма):

Subgraph(s,t,d)

, .

s: исходная страница.

t: число страниц в корневом наборе R_s.

d: инкремент – число страниц, добавляемых в базовый набор B_s.

Обозначим

R_s – корневой набор из t страниц для страницы s;

B_s – базовый набор страниц.

R_s := первые t ссылок страницы s.

For each p Rs

Г⁺(p) – это набор всех страниц, на которые указывает p.

Г¯(p) – это набор всех страниц, которые ссылаются на p.

B_s += Г⁺(p).

If |Г¯(p)| <= d then

Bs += Г¯(p).

Else

Bs += (d любых страниц из Г¯(p)).

End

Return B_s

Число добавляемых страниц из Г¯(p) ограничено параметром d, так как на некоторые страницы могут указывать сотни и тысячи страниц.

7. Вычисление весов authority и hub

После построения базового набора страниц применяется итеративный метод вычисления весов, также как и в HITS алгоритме. Каждой странице присваивается две величины: authority и hub, которые вычисляются методом Iterate(ε) (шаг 3 алгоритма).

Iterate(ε, N):

, , где

ε – допустимая погрешность для останова итераций.

N – число похожих страниц (авторитетных), которые необходимо найти

while (E > ε) {

Для каждой страницы из базового набора B_s :

обновить значения: authority, hub (см. формулы (2.1) и (2.2))

Нормализовать authority и hub так, что и

Вычислить суммарное изменение веса по всем страницам:

}

Return N страниц с максимальным значением веса authority.

Временная сложность¹ вычисления весов (в зависимости от N – числа страниц в базовом наборе) составляет O(I∙N²), где I – число итераций. Поскольку для каждой страницы нужно обойти всех её соседей (в худшем случае их N).

Кластеризация на основе категорий статей

Предлагается следующий алгоритм иерархической кластеризации, позволяет объединить документы в смысловые группы. Определим структуры данных, используемые в алгоритме, представим блок-схему (Рис. 10) и псевдокод алгоритма.

Структуры данных и параметры алгоритма:

• G=(V, E) – направленный граф, где V – вершины (статьи и категории, то есть два типа страниц, два типа вершин), E – дуги (три типа дуг: между статьями, между категориями, между статьями и категориями).

• E _sorted – массив рёбер, упорядоченный по весу (E _sorted [0] – ребро с минимальным весом).

• Clusters – список кластеров, которые нужно построить.

• C _max – максимально допустимый вес кластера (число статей и категорий в кластере).

Для каждого ребра e определены следующие поля:

• е _c1 и е _c2 – это указатели на два соединяемых кластера;

• e _weight – вес ребра (пересчитывается), равный суммарному весу объединяемых кластеров с₁ и с₂.

Рис. 10. Иерархическая кластеризация

Для кластера-вершины c определены такие поля:

• |с _edges| – число объединённых рёбер кластера (рёбер между вершинами-категориями кластера);

• |с _articles| – число статей, которые ссылаются на категории в кластере (знак мощности множества |.| используется в силу его наглядности, однако, поскольку |с _articles| – это переменная, то ей можно присваивать значение (см. напр. строку 5b в алгоритме);

• c _weight – вес кластера;

• Г(c) – массив рёбер, связывающих кластер с другими кластерами.

При вычислении веса кластера учитываются: число статей в кластере, веса объединяемых кластеров (см. формулу (2.7) ниже).

Процесс кластеризации состоит из двух шагов: предобработка (инициализация массива кластеров, присвоение начальных значений полям вершин и рёбер) и сам алгоритм кластеризации.

Предобработка

(две косые черты '//' отделяют комментарий от псевдокода)

1. Построить кластеры (массив Clusters) по категориям: изначально каждый кластер соответствует отдельной вершине (категории). Приписать каждому кластеру (за счёт содержащихся в кластере категорий):

1. |с _articles| = число статей, которые ссылаются на категории в кластере,

2. c _weight = 1 + |с _articles| // изначально вес кластера – это число категорий в кластере (изначально одна) и число статей, которые ссылаются на эту одну категорию;

3. c _{category_id}[0] = category _id // присваиваем кластеру уникальный идентификатор id первой (и единственной пока) категории, добавленной в кластер¹.

2. Для каждого ребра между категориями создать ребро между кластерами. Каждому ребру e, соединяющему два кластера c1 и c2 определить вес так:

e _weight = c1 _weight + c2 _weight

Алгоритм

1. E _sorted = sort(e _weight); // сортировка рёбер по весу

2. while(|E _sorted| > 0 && (E _sorted[0] < C _max)) BEGIN

3. e = E _sorted [0]; // v₁, v₂ – вершины смежные ребру e

4. E _sorted = E _sorted \ Г(v₂); // удалить из упорядоченного массива рёбер рёбра смежные v₂

5. merge(e); // объединить вершины-кластеры v₁ и v₂ в кластер v₁, то есть добавить вершину v₂ в кластер v₁, изменив свойства v₁ так:

   1. v_{1 weight} += v_{2 weight}; // увеличить размер кластера (число категорий и статей)

   2. |v_{1 articles}| += |v_{2 articles}|; // увеличить число статей

   3. |v_{1 edges}| += |v_{2 edges}|; // увеличить число рёбер

   4. v_{1 category_id}[] += addUnique(v_{2 category_id}[]); // добавить категории без повторов (на основе уникальности идентификаторов)

6. passEdges(); // все рёбра смежные вершине v2 передать вершине v1 (рёбра без повторений, это не мультиграф).

7. E _sorted = E _sorted \ edge (v₁, v₂); // удалить ребро (v₁, v₂);

8. updateEdgesOfMergedCluster; // обновить указатели на вершины, удалить ребра (вершины и рёбра, смежные удаляемой вершине)

9. updateEdgeWeight(v₁); // пересчитать значения весов для всех рёбер смежных v1

10. remove(Clusters, v₂); // удалить кластер v₂ из массива кластеров

11. E _sorted = sort(e _weight) // пересортировка рёбер, сложность O(N), т. к. нужно обновить порядок только тех рёбер, которые смежны вершине v₁

12. END

13. Return Clusters

Результат работы алгоритма – это кластеры категорий (Clusters). По кластеру категорий получаем кластер статей, поскольку для каждого кластера c определено значение с _articles (список статей, ссылающиеся на категории в кластере).

Заметим, что одна статья может ссылаться на несколько категорий. Поэтому одна статья может принадлежать нескольким кластерам. Но категория принадлежит ровно одному кластеру.

Варианты объединения результатов АHITS алгоритма и алгоритма кластеризации

Могут быть реализованы следующие варианты:

1) Использовать информацию о каждой вершине (hub, authority) (в алгоритме кластеризации) для вычисления начального веса кластера на этапе предобработки, в шаге 1б:

Здесь h _v и a _v вычислены с помощью адаптированного HITS алгоритма, k – весовой коэффициент (параметр), наличие единицы объясняется тем, что на этапе предобработки кластер содержит только категорию. Суммирование проводится по всем статьям, которые ссылаются на категории кластер.

2) Выбрать (после кластеризации) из каждого кластера подмножество hub, authority статей с максимальным весом и представить пользователю как на­бо­ры синонимов и близких по значению слов (для исходного слова), сгруп­пи­ро­ванные по значению. Открытым остаётся вопрос – как определить число зна­чений (здесь – кластеров) у слова? На данный момент число кластеров опре­деляется максимально разрешённым весом кластера (параметр алгоритма кластеризации C _max).

Временная сложность алгоритма

Обозначим C – число категорий, N – число статей (число страниц в базовом наборе). Первый шаг предобработки требует O(C∙N) операций, второй – O(C²). Тогда предобработка в целом требует O(C∙N+C²) операций.

В алгоритме первый шаг (сортировка рёбер) требует не более O(C²) опе­раций. Циклов (шаг 2) должно быть не больше числа рёбер, то есть O(C²), так как на каждом витке цикла удаляется одно ребро. Наиболее вы­чи­сли­тель­но затратным будет пятый шаг, так как для объединения вершин необходимо O(C+N) операций, поскольку нужно обойти категории и статьи, соседние для объе­диняемых кластеров. Тогда предобработка и алгоритм кластеризации в целом требуют

O(C∙N + C²) + O(C²∙(C + N)) = O(C³ + N∙C²)

Временная сложность [20] вычисления весов (hub, authority) в HITS алго­ритме составляет , где I_k – число итераций в адаптированном HITS алгоритме. Тогда общая сложность адаптированного HITS алгоритма будет:

где: I_k – число итераций на шаге 3 в адаптированном HITS алгоритме;

C – число категорий;

N – число статей (число страниц в базовом наборе).¹

Эвристика: фильтрация на основе категорий статей

Предлагается следующий способ сужения поиска похожих документов в корпусе документов с категориями.

Дано: (глубина поиска) и Category _Blacklist – чёрный список ка­те­го­рий, про которые заранее известно, что документы с такими категориями не подходят, то есть не являются похожими на исходный документ.

Для использования этих данных нужно выполнить фильтрацию стра­ниц при построении корневого и базового набора страниц (первые два шага адапти­рованного HITS алгоритма), состоящую в следующем. Если категории страницы, или их надкатегории (не более N уровней относительно исходной страницы²) принадлежат списку Category _Blacklist, то страница пропускается и не добавляется в корневой / базовый набор, иначе – добавляется.

Данная эвристика была реализована в программе Synarcher, см. подраздел «Модуль визуализации: интерфейс и функции» на стр. 99.

4. Вычисление меры сходства вершин графа. Оценка временной сложности. Эвристики

Дано: направленный граф G=(V, E), где V – вершины (страницы), E – дуги (ссылки), . Для каждой страницы v известны два списка: Г⁺(v) – это страницы, на которые ссылается данная статья, и Г¯(v) – это страницы, ссылающиеся на данную статью. Для каждой вершины определены значения двух весовых коэффициентов authority и hub: .

Необходимо найти набор вершин A, похожих на вершину w. Определение похожести вершин графа приведено ниже и оно отличается от приведённого в подразделе «Формализация понятия «похожие вершины» графа» на стр. 76 тем, что (i) в результате работы алгоритма строится массив сходства вершин, (ii) не используются понятия авторитетных и хаб-страниц.

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

Задача поиска похожих вершин графа.

Дано: направленный граф G=(V, E), где V – вершины, E – дуги, .

Найти: n вершин графа G максимально похожие на w, упорядоченные по степени сходства. Степень сходства между двумя вершинами а и b определим рекуррентно:

Первое слагаемое¹ в числителе (2.9) – это число общих вершин среди соседей вер­шин a и b, второе слагаемое – это суммарное сходство соседей вершин a и b. В знаменателе – суммарное сходство по всем парам графа G. Весовой коэф­фициент k позволяет выбрать компонент, который оказывает большее влия­ние на суммарное сходство: число общих соседей или степень сходства между соседними вершинами.

Таким образом, , если (1) у вершин a и b нет общих соседей и (2) среди вершин соседних a и b степень сходства равна нулю:

где – это множество соседних вершин для вершин a и b соответственно. Такая постановка задачи определяет следующий алгоритм поиска похожих вершин графа.

Алгоритм поиска похожих вершин графа

CalcSimilarVertices(G, ε, k)

G=(V,E) – граф c N вершинами

, где

ε – погрешность вычислений

k – весовой коэффициент

Y[][] – сходство между вершинами графа

1. // инициализация Y¹

2. for(i=0; i<N;i++) {

3. for(j=0; j<N;j++) {

4. Yold[i][j] = Y[i][j] = / N²

5. }

6. }

7. // итеративное вычисление Y

8. error = 1 + ε

9. while (error > ε) {

10. norma = 0

11. for(i=0; i<N;i++) {

12. for(j=0; j<N;j++) {

13. 

14. norma += Y[i][j]

15. }

16. }

17. for(i=0; i<N;i++) {

18. for(j=0; j<N;j++) {

19. 

20. Ydelta[i][j] = |Y[i][j] – Yold[i][j]|

21. Yold[i][j] = Y[i][j]

22. }

23. }

24. 

25. }

В шагах 13, 14, 19 реализуется формула (2.9) вычисления сходства между i-ой и j-ой вершинами графа. Шаги 20, 21 и 24 вычисляют суммарное изменение (error) на данном шаге итерации (цикл while).

В результате работы алгоритма получаем симметричный массив сход­ства вершин Y[][]. Теперь для поиска упорядоченного списка макси­маль­но по­хожих вершин, например на j-ую, достаточно отсортировать одномерный массив Y[j][].

Остаются открытыми следующие вопросы:

• доказательство сходимости итеративного алгоритма;

• скорость сходимости в реальных экспериментах.

Оценка временной сложности

Шаги вложенных циклов 9, 11, 12 и 9, 17, 18 дают сложность O(I∙N²), где I – число итераций, N – число вершин в графе.

Шаг 13 требует поиска пересечений всех соседей двух вершин. Поиск пересечения двух множеств размерности N требует O(N) операций (например с помощью меток). Тогда временная сложность алгоритма O(I∙N³). Постараемся уменьшить временную сложность [20] алгоритма с помощью эвристик.

Эвристики¹

1) В первой эвристике предлагается рассматривать не все пары вершин (как кандидаты на «похожие» вершины), а только те, у которых совпадают не менее L соседей.

При этом циклы на шагах 11, 12 и 17, 18 потребуют не O(N²) операций, а O(M²), где M – число вершин, которые имеют не менее L общих вершин.

Число M можно определить (сравнив попарно вершины на наличие не менее L соседей) до выполнения алгоритма за время O(N³), где N – число вершин графа. Вычислив M, можно принять решение: будет ли эвристика давать значительный выигрыш в скорости при данном L либо нужно увеличить L и повторить вычисления.

Таким образом, вычисление степени сходства между M вершинами с помощью функции CalcSimilarVertices потребует времени O(I∙M³). После этого один раз выполняется тело цикла while (шаги 10-23) для вычисления степени сходства между всеми N вершинами за O(N²) операций. Таким образом, суммарная временная сложность составит O(I∙M³+N³).

2) Предлагается эвристика (для алгоритма поиска похожих вершин графа), использующая результаты работы HITS алгоритма.

После применения HITS алгоритма к графу G=(V, E) с N вершинами получено M особых вершин (а именно: авторитетные и хаб-страницы), причём M – это параметр алгоритма.

Временная сложность вычисления весов (hub, authority) в HITS алгоритме составляет , где I_k – число итераций в HITS алгоритме, N_k – число страниц в базовом наборе.

Число итераций I (вслед за работой¹) можно оценить, как: , где h – это число правильно найденных авторитетных вершин, всего найдено k авторитетных вершин. Необходимое условие: .

Далее аналогично первой эвристике: (1) выполнение функции CalcSimilarVertices потребует O(I∙M³) операций для вычисления значения степени сходства между M вершинами и (2) O(N²) для вычисления степени сходства между всеми N вершинами. Суммарная временная сложность будет .

Преимущество перед первой эвристикой второй эвристики (вычисляемой соответственно за O(I∙M³+N³) и операций) в том, что число обрабатываемых вершин M задаётся напрямую, а не вычисляется (за O(N³)) через параметр L (число общих соседей).

5. Показатели численной оценки семантической близости списка слов

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

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

Таким образом, разработано несколько показателей численной оценки полученного набора синонимов: SER, ER и коэффициент Спирмена.

SER (Strong Error Rate) – число слов (в процентах от общего числа найденных слов), которые не имеют отношения к исходному слову (определяется либо вручную – экспертом, либо автоматически – по наличию/отсутствию в тезаурусе, например WordNet, Moby¹).

ER (Error Rate) – число слов (в процентах), не являются синонимами (определяется вручную экспертом либо автоматически – по наличию/отсутствию в тезаурусе WordNet).

Где – множество слов, найденных с помощью адаптированного HITS алгоритма для слова w, – список синонимов из тезауруса WordNet для слова w, – список слов близких по значению из тезауруса Moby. Очевидно, что ER ≥ SER, поскольку в SER вычитаются слова из обоих тезаурусов: WordNet и Moby.

Открытые вопросы:

1. Сильно ли изменятся значения SER и ER, если в знаменателе будет стоять только ? Вероятно, это сильно связано с числом найденных синонимов адаптированным HITS алгоритмом.

2. Первый вопрос определяет второй: как для упорядоченной последовательности синонимов, возвращаемой алгоритмом (теоретически неограниченной, например, несколько тысяч), определить: где оборвать эту последовательность, обеспечивая некоторое приемлемое качество? Возможный ответ таков. После работы алгоритма у каждой вершины графа определён вес authority, который говорит о степени авторитетности (в нашем случае – синонимичности). Выбрав эмпирически некоторое вещественное d, 0≤d≤1, можно отсекать множество синонимов, выбирая только те, у которых authority≥d. Либо, вычислив последовательность SER и ER (где например SER_i соответствует первым i-ым словам результата), оборвать последовательность на N-том члене при SER_N≥d.

Коэффициент Спирмена

Самый простой способ сравнить два набора данных в том, чтобы найти количество общих элементов¹.

В [76] метрика Спирмена (Spearman, другое название – Spearman's footrule) используется как для сравнения ранжирования одного и того же набора Интернет страниц разными поисковиками, так и для оценки изменения ранжирования рассматриваемого набора страниц во времени.

Метрика Спирмена² позволяет сравнить две ранжировки одного и того же набора из N элементов. Каждому элементу назначается ранг от 1 до N (мера основана на перестановках). Метрика Spearman равна сумме модулей расстояний между i-ми элементами набора.

Предположим, при поиске синонимов для данного слова и для двух вариантов начальных параметров адаптированного HITS алгоритма I₁ и I₂ (размер корневого набора, число добавляемых страниц и др.) получили два набора слов S₁ и S₂. Задача заключается в том, чтобы выяснить, какие параметры алгоритма дают лучший результат. Это можно сделать, сравнивая множества слов S₁ и S₂ с эталонным множеством синонимов и близких по значению слов для данного слова (выбранных экспертом или найденных с помощью тезауруса). Для сравнения предлагается использовать метрику Спирмена.

Предлагается расширить метрику Спирмена для сравнения списков разной длины¹ следующим способом, отличающимся² от расширения предложенного в [76]. Дано два списка: (1) A – более короткий, эталонный, составленный экспертом, (2) B – более длинный, составленный автоматически. В конец списка B добавляются отсутствующие в нём элементы А. Далее применяется формула (2.13), где сравниваются положения в списках общих элементов, S – число общих элементов, а также длина более короткого списка.

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

Таким образом, с помощью коэффициента Спирмена можно сравнить ранжирование одного и того же набора слов адаптированным HITS алгоритмом при разных параметрах поиска с эталонным списком.

Выводы по главе 2

В данной главе были разработаны: (1) подход поиска СБС, (2) формализация понятия похожие вершины, (3) адаптированный алгоритм HITS с использованием алгоритма кластеризации, (4) предложенный автором алгоритм поиска похожих вершин графа и (5) предложенные автором методы численной оценки наборов синонимов (модификация коэффициента Спирмена (Spearman's footrule) и оценка на основе тезаурусов WordNet и Moby).

HITS алгоритм был адаптирован автором к тем дополнительным возможностям, которые предоставляет рассматриваемый корпус документов, относительно обычных Интернет страниц. Это (1) наличие категорий (классифицирующих документы по их тематической принадлежности), (2) наличие метаинформации в виде ключевых слов (в простейшем случае - это заголовок документа).

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

Автором предложены два варианта формализации понятия «похожие вершины» графа. Первый вариант использует понятия авторитетных и хаб-страниц и позволяет формализовать задачу поиска похожих страниц в HITS алгоритме. Во втором варианте получена формула сходства двух вершин a и b, основанная на поиске общих вершин среди соседей вершин a и b.

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

Предложены методы численной оценки наборов синонимов, полученных на выходе адаптированного HITS алгоритма. Оценка позволит выбрать входные параметры алгоритма. Для оценки работы алгоритма с английским корпусом текстов предлагается использовать тезаурусы WordNet и Moby.

Метрика Spearman's footrule (коэффициент Спирмена) обычно используется как для сравнения ранжирования одного и того же набора данных. Коэффициент Спирмена модифицирован для численного сравнения списков слов, отличие от оригинального метода заключается в возможности сравнивать списки разной длины. Предлагается с помощью метрики Spearman's footrule сравнить ранжирование одного и того же набора слов, полученных адаптированным HITS алгоритмом при разных параметрах поиска.

3. Организация программного обеспечения поиска семантически близких слов, автоматической оценки поиска и морфологического анализа слов

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

В этой главе представлена архитектура и реализация программного модуля системы GATE для удалённого доступа к программе морфологического анализа русского языка (aot.ru) на основе XML-PRC протокола. Данная архитектура представляет способ интеграции приложений написанных на разных языках программирования (например, С++ и Java) посредством XML-RPC протокола. Спроектирована архитектура системы индексирования вики-текстов, включающая GATE и Lemmatizer.

В главе представлена архитектура программной системы оценивания синонимов, позволяющей реализовать метод численной оценки списков семантически близких слов (адаптация метода Spearman's footrule и оценка на основе тезаурусов WordNet и Moby). Данный метод численный оценки описан в подразделе 2.5.

1. Архитектура программной системы Synarcher

Достоинствами поискового комплекса Synarcher являются (1) визуализация результатов поиска, (2) возможность уточнения запроса в ходе работы пользователя с программой.

В архитектуру программного комплекса Synarcher (рис. 11) включены такие модули, как: модуль kleinberg, предоставляющий доступ к данным Википедии и реализующий алгоритм AHITS, модуль визуализации TGWikiBrowser². Последовательность взаимодействия частей системы указаны на рис. 11 числами (1-7). Входными данными для AHITS алгоритма являются слово, заданное пользователем (1-2), и данные Википедии (2). Алгоритм строит список СБС, упорядоченных по весу authority (3), а пользователь получает возможность работать с ними благодаря модулю визуализации TGWikiBrowser (4-5). В ходе работы пользователь уточняет список СБС и запускает алгоритм повторно (6-7).

Рис. 11. Архитектура программного комплекса Synarcher

Программа написана на языке Java [68], [8], [115]. Для неусыпного контроля работоспособности разных частей программы использовалась методика экстремального программирования – автоматические тесты модулей¹ [6], [9], [188].

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

Модуль алгоритмов

Основные наборы файлов (package) первого проекта – это rfc2229, wikipedia.clustering, wikipedia.kleinberg, wikipedia.sql, wikipedia.util. Их назначение состоит в следующем:

• rfc2229 – клиент к Dict серверам¹, основанный на библиотеке JavaClientForDict (jcfd), разработанной Davor Cengija; расширение данного клиента для удалённого вызова тезаурусов WordNet и Moby;

• wikipedia.clustering – реализация алгоритма кластеризации, описанного в главе 2;

• wikipedia.kleinberg – реализация адаптированного HITS алгоритма и основные структуры данных, используемые в работе этого алгоритма (Article, Category, Node). Также этот пакет содержит вспомогательный класс DumpToGraphViz, позволяющий текущее состояние графа сохранять в специальном формате, который может быть преобразован в форматы PNG, JPEG или SVG программой GraphViz²;

• wikipedia.sql – это программный интерфейс доступа к Википедии. Пакет позволяет читать данные Википедия, хранимой в базе данных MySQL. Названия классов соответствуют таблицам, с которыми они работают: PageTage, Links, Category. Класс Statistics выдаёт статистическую информацию (число статей, категорий, ссылок) о подключенной Википедии.

• wikipedia.util – пакет содержит вспомогательные классы. Encoding – содержит функции преобразования кодировок, FileWriter – работа с файлами, RandShuffle – обеспечивает случайную перестановку данных в исходном массиве, StringUtil – вспомогательные функции по обработке строковых данных, StringUtilRegular – вспомогательные функции по обработке строковых данных с использованием регулярных выражений [63].

Модуль визуализации: интерфейс и функции

Представление в виде графа результатов поиска синонимов и семантически близких слов основывается на программе TouchGraph WikiBrowser V1.02¹. Данная программа предназначена для визуализации Wiki страниц. Программа TouchGraph WikiBrowser была существенно модифицирована для того, чтобы обеспечить следующую функциональность:

• подключение к базе данных Википедия, поскольку клиент-серверная архитектура базы данных MySQL позволяет программе Synarcher обращаться к базе данных Википедия, установленной на удалённом компьютере (рис. 13);

• задание параметров адаптированного HITS алгоритма (рис. 14);

• хранение слов, помеченных пользователем, как синонимы, и параметров поиска на компьютере пользователя. Причём запоминаемые параметры делятся на (1) параметры программы в целом (класс BrowserParameters), например, название базы данных с которой работали, последнее искомое слово и (2) параметры поиска отдельного слова (класс ArticleParameters);

• расширение контекстного меню (рис. 15) для более удобной навигации командами, позволяющими спрятать все вершины (Hide all except node), пометить вершину как синоним (Rate synonym), показать категории (Expand Categories).

Экран программы делится на две части вертикальной полосой, с левой стороны три вкладки² (англ. tab): Article, Database и Synonyms.

Первая вкладка Article позволяет просмотреть энциклопедическую статью, соответствующую выбранному слову (рис. 12). Адрес статьи (URL) можно увидеть внизу экрана в строке статуса. Представление статьи Википедии в этом мини браузере (то есть во вкладке Article) и, вообще, в Интернет браузере возможен благодаря слаженной работе на стороне сервера таких программ, как: MySQL, Apache, PHP и MediaWiki.

Вкладка Database позволяет: (1) указать кодировку, (2) указать параметры для подключения к базе данных, (3) проверить подключение и получить статистику по базе данных (рис. 13). В верхней части экрана находится выпадающее меню (поле Wikipedia), позволяющее выбрать одну из баз данных Википедия. На данный момент это английская и русская версии энциклопедии.

Возможность указать кодировку (по умолчанию UTF8¹) призвана решить возможные проблемы, связанные с хранением текстовых данных на стороне пользователя (например, название последней просмотренной статьи). Дополнительная информация по настройке кодировки в программе представлена на странице проекта².

На рис. 13 показаны параметры подключение к БД Русской Википедии, установленной локально (группа параметров «MySQL database connection parameters»):

• Database host – адрес компьютера на который установлена энциклопедия, в данном случае (рис. 13) она установлена на том же компьютере, что и запущенная программа Synarcher, поэтому указано значение: localhost;

• Database name – указывается имя базы данных в MySQL и параметры подключения к базе. Здесь база данных названа ruwiki, параметры подключения представлены в нижней части экрана в окне Output (в круглых скобках);

• User, Password – имя пользователя и пароль под которыми программа подключается к базе данных. Значения определяются настройками MySQL и MediaWiki. Здесь указан пользователь javawiki, пароль отсутствует.

• Wiki url – URL-адрес, используемый веб браузером для поиска статьи Википедии. Необязательный параметр для работы алгоритмов поиска, нужен для отображения страниц во вкладке Article (рис. 12). Значение определяется настройками Apache и MediaWiki.

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

Во вкладке Synonyms (рис. 14) задаются параметры адаптированного HITS алгоритма (дополнительная вкладка Parameters), выводятся результаты в табличной и текстовой форме (вкладка Results). Слово для поиска задаётся в поле Word. Кнопка Load позволяет загрузить параметры предыдущего поиска, кнопка «Search Synonyms» запускает алгоритм поиска, а кнопка Draw отображает (в правой части экрана в виде сетевой структуры) страницы, на которые ссылается заданное слово.

В поле Log пользователь (с помощью кнопки «Browse...») указывает директорию в которой будут храниться результаты поиска.

Поля «Root set size», increment, «N synonyms», «Eps error» соответствуют параметрам адаптированного HITS алгоритма: t, d, N, ε (см. подраздел 2.1 на стр. 68).

Рис. 13. Вкладка Database

Рис. 14. Задание параметров адаптированного HITS алгоритма

В нижней части экрана (рис. 14) задаётся группа параметров, озаглавленных «Category blacklist parameters». Данные параметры определяют такие параметры эвристики¹, как: глубина поиска (поле «Maximum search depth») и чёрный список категорий, разделённых вертикальной чертой (на рисунке в этом поле введены категории «Страны|Века|Календарь|География_Россия»). После редактирования категорий для сохранения изменений достаточно нажать кнопку Set.

На рис. 15 показан пример результатов поиска семантически близких слов для слова Локализация. Итак, пользователь вводит слово и параметры алгоритма, нажимает кнопку «Synonym Search», после чего система выполняет поиск.

Экран программы разделён на две части вертикальной полосой, с левой стороны (вкладка: Synonyms, Results) представлены результаты поиска в виде таблицы и текста, с правой стороны – в виде графа. Вершины графа соответствуют названиям статей энциклопедии (статья – это гипертекстовая страница), рёбра указывают наличие гиперссылок между статьями. Пользователь может пометить найденные слова как синонимы либо с помощью галочки в таблице (графа «Rate it»), либо с помощью контекстного меню, нажав правую клавишу мышки на интересующей вершине и выбрав команду «Rate synonym». Другие команды контекстного меню позволяют:

• раскрыть вершину, то есть отобразить соседние вершины (команда «Expand Node», см. (рис. 15);

• спрятать соседей, которые связаны только с этой вершиной (команда «Collapse Node»);

• спрятать вершину и тех соседей, которые связаны только с этой вершиной (команда «Hide Node»);

• спрятать всех соседей, кроме данной вершины (команда «Hide All Except Node»).

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

На рис. 15 можно выделить следующие группы вершин¹ (по именам статей, выделенных курсивом, им соответствующим):

1. Локализация – исходная вершина, заданная пользователем; с неё начинался поиск в адаптированном HITS алгоритме;

2. Русификация, L10N – вершины, помеченные пользователем, как синонимы исходного слова Локализация;

3. Глобализация – хаб-вершина, то есть вершина, ссылающаяся на многие авторитетные вершины (см. понятие авторитетных и хаб-страниц в разделе «Алгоритм HITS» (стр. 27) и разделе «Вычисление весов authority и hub» стр. 80);

4. Авторитетные страницы (отсутствуют на данном рисунке);

5. Сортировка, Дата – все остальные вершины (в адаптированном HITS алгоритме они соответствуют вершинам из базового набора).

Аналогичный скриншот, но уже с интерфейсом на русском языке, с ре­зуль­татами поиска для слова «Интернационализация» представлен на рис. 16.

Рис. 16. Результаты поиска семантически близких слов для слова Интернационали-зация в виде таблицы, текста и графа. Пример контекстного меню справа-внизу

Одним из результатов поиска является список категорий, см. вкладку «Категория C» на рис. 17. Таблица (слева в центре) содержит список категорий (столбец Категория), упорядоченных по числу слов (столбец Статей), статьи которых принадлежат этим категориям. При выборе какой-либо категории в таблице обновляется текст – список статей – в окне Output (слева внизу). На рис. 17 выделена категория «Воздушные суда» и перечислены названия однословных статей с такой категорией.

2. Архитектура подсистемы GATE для удалённого доступа (на основе XML-RPC протокола) к программе морфологического анализа Lemmatizer

8. Сформулируем задачу, исходя из доступных ресурсов. Система GATE¹ на­писана на языке Java, поэтому может работать в среде Linux и Windows. Мо­дуль морфологического анализа Lemmatizer написан на языке C++ и может работать либо в среде Linux, либо в CygWin (эмуляция Linux в среде Windows).

9. Связать эти разнородные системы целесообразно с помощью протокола XML-RPC (рис. 18). Данный протокол позволяет взаимодействовать программным компонентам, (1) написанным на разных языках, (2) расположенным на разных компьютерах.

Таким образом, необходимо расширить модуль морфологического анализа Lemmatizer функциональностью XML-RPC сервера, написанного на С++, назовём его LemServer, для вызова функций которого нужно указать:

• имя компьютера (указывается, как параметр модуля GATE – hostLemServer, см. рис. 27);

• порт сервера (portLemServer);

• словарь – русский, английский или немецкий (dictLemServer).

10. Со стороны GATE необходим модуль, назовём его Russian POS Tagger, на­пи­сан­ный на языке Java, который с одной стороны обеспечивает стандартную функцио­нальность модулей GATE (что даёт, в частности, возможность со­би­рать модули GATE в последовательные цепочки обработчиков, по англ. pipe). С другой стороны Russian POS Tagger может вызывать функции Lemmatizer с по­мощью XML-RPC клиента, написанного на языке Java, назовём его aotClient (программные компоненты, разработанные автором диссертации, выделены чёрной линией на рис. 18).

Рис. 18. Архитектура интеграции системы GATE и
модуля морфологического анализа Lemmatizer

Таким образом, Russian POS Tagger взаимодействует с Lemmatizer, вызывая Java-функции aotClient, который выполняет XML-RPC запросы к LemServer, кото­рый, в свою очередь, вызывает C++ функции Lemmatizer. LemServer – это интерфейс на C++ для вызова функций модуля Lemmatizer.

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

• Document Reset PR – инициализация параметров текстов;

• ANNIE English Tokenizer – выделение элементов текста (токенизация)

• ANNIE Sentence Splitter – выделение предложений;

• Russian POS Tagger – морфологическая обработка слов.

Морфологическая обработка включает в себя (1) определение части речи, (2) при­ведение слова к начальной форме, (3) построение списка парадигм сло­ва. Параметры модуля Russian POS Tagger, необходимые для под­клю­че­ния и вызова функций XML-RPC сервера LemServer включают: хост (portLemServer), порт (hostLemServer) сервера, который может быть запущен на другом компьютере. Поиск может выполняться для русского, английского или немецкого языков, для выбора языка нужно указать параметр dictLemServer модуля Russian POS Tagger.

3. Индексирование вики-текстов: архитектура системы и структура индексной базы данных

11. Разработанный адаптированный HITS алгоритм (AHITS) [37], [126] выполняет поиск на основе анализа внутренних ссылок Википедии. Многие алгоритмы поиска семантически близких слов (СБС) в Википедии обходятся без полнотекстового поиска (см. табл. 4.6 на стр. 130). Однако экспериментальное сравнение алгоритмов в работах [103], [35] показало, что наилучшие результаты поиска семантически близких слов даёт алгоритм Explicit Semantic Analysis (ESA) [103], использующий именно полнотекстовый поиск.

Это подвигнуло к созданию общедоступной индексной базы данных Вики­педии (далее WikIDF¹) и программных средств для генерации БД, что в целом обеспечит полнотекстовый поиск в энциклопедии и в вики-текстах вообще. Вики-текст — это упрощённый язык разметки HTML.² Для индекси­ро­вания требуется преобразовать его в текст на естественном языке. Поиск по ключевым словам не будет использовать символы и теги HTML- и вики-разметки, поэтому они будут удалены в ходе преобразования вики-текста в текст на естественном языке на предварительном этапе индексирования.

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

Архитектура системы построения индексной БД вики-текстов

Итак, спроектирована архитектура программной системы индексирования вики-текстов.¹ На рис. 19 показана организация взаимодействия программ GATE [92], Lemmatizer [60] и Synarcher [37], [126]. Полезным результатом ра­боты системы будет индексная БД на уровне записей (англ. «record level inverted index»), содержащая список ссылок на документы для каждого слова (точнее — для каждой леммы).²

Программной системе требуется задать три группы входных параметров. Во-первых, язык текстов Википедии (один из 254 на 16/01/2008) и один из трёх языков (русский, английский, немецкий) для лемматизации, что опре­де­ля­ется наличием трёх баз данных, доступных лемматизатору [60]. Указание язы­ка Википедии необходимо для правильного преобразования текстов в вики-формате в тексты на ЕЯ (рис. 19, функция «Преобразование вики в текст» модуля «Обработчик Википедии»)³. Во-вторых, адрес вики и индекс­ной баз данных, а именно обычные параметры для подключения к удалённой БД: IP-адрес, имя БД, имя и пароль пользователя. В-третьих, параметры инде­кси­рования, связанные с ограничениями, накладываемыми поль­зо­ва­те­лем на размер индексной БД, предназначенной для последующего поиска по TF-IDF схеме.⁴

Рис. 19. Архитектура системы индексирования вики-текстов (POS — Part Of Speech)

«Управляющее приложение» выполняет последовательно три шага для каждой статьи (вики-документ), извлекаемой из БД Википедии и преобразуемой в текст на ЕЯ, что и составляет первый шаг. На втором шаге привлекается такой мощный инструмент как GATE [92] вкупе с отечественной разработкой Lemmatizer [60] и объединяющей их программной «прослойкой» RussianPOSTagger¹, конечная цель которых – получение списка лемм и их частоты встречаемости в данной статье.² На третьем шаге полученные данные сохраняются в индексную БД³: (1) полученные леммы, (2) частота их встречаемости в тексте, (3) указывается, что данные леммы принадлежат данному вики-тексту, (4) увеличивается значение частоты данных лемм в корпусе.

Следует отметить, что две функции модуля «Обработчик Википедии», указанные на рис. 19, а также API доступа к индексной БД («TF-IDF Index DB» из модуля «TF-IDF Приложение») реализованы в программе Synarcher¹. Указание входных параметров и запуск индексации осуществляются с помощью модуля Synarcher: WikIDF².

Таблицы и отношения в индексной БД

Принципы построения индексной БД:³

1. данные наполняются единожды и далее используются только для чтения (поэтому не рассматриваются такие вопросы, как: обновление индекса, добавление записи, поддержка целостности);

2. из викитекста удаляется вики- и HTML- разметка; выполняется лемматизация, леммы слов сохраняются в базу;

3. данные хранятся в несжатом виде.

Число таблиц в индексной базе данных, их наполнение и связи между ними были определены исходя из решаемой задачи: поиск текстов по заданному слову с помощью TF*IDF формулы (см. ниже). Для этого достаточно трёх⁴ таблиц и ряда полей (Рис. 20):

1. term — таблица содержит леммы слов (поле lemma); число документов, содержащих словоформы данной лексемы (doc_freq); суммарная частота словоформ данной лексемы по всему корпусу (corpus_freq);

2. page — список названий проиндексированных документов (поле page_title в точности соответствует полю одноимённой таблицы в БД MediaWiki); число слов в документе (word_count);

3. term_page — таблица, связывающая леммы словоформ, найденных в документах с этими документами.

Постфикс «_id» в названии полей таблиц обозначает уникальный идентификатор. Ниже горизонтальной полосы в рамке каждой таблицы перечислены поля, проиндексированные для ускорения поиска. Между полями таблиц задано отношение один ко многим — между таблицами term и term_page, а также page и term_page.

Рис. 20. Таблицы и отношения в индексной базе данных WikIDF¹

Данная схема БД позволяет получить:

• список лемм слов заданного документа;²

• список документов, содержащих словоформы лексемы, заданной своей леммой.³

Напомним читателю формулу TF-IDF (3.1), с прицелом на которую и была спроектирована вышеуказанная схема БД (рис. 20). Всего в корпусе D документов, термин (лексема) t _i встречается в DF _i документах (поле индексной базы данных term.doc_freq). Для заданного термина t _i вес документа w(t _i) определяется как [155]:

где TF _i — число вхождений термина t _i в документ (поле term_page.term_freq), idf ⁴ служит для уменьшения веса высоко частотных слов. Можно нормализовать TF _i, учтя длину документа, то есть разделив на число слов в документе (поле page.word_count). Таким образом, значения полей БД позволяют вычислить обратную частоту термин t_i в корпусе.

Отметим, что в результате построения индексной БД оказалось, что размер индекса составляет 26-38% от размера файла с текстами индексируемого вики-проекта.¹

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

Разработана и далее описана архитектура программной системы для автоматической численной оценки набора списков семантически близких слов на основе тезаурусов английского языка (WordNet и Moby), доступным с помощью Dict cерверов. Эти сервера предоставляют программный интерфейс для получения данных о конкретных словарных статьях. Достоинства Dict cерверов для пользователя:

• это низкие требования к клиенту (не нужно устанавливать словарь локально, словари хранятся на сервере, клиенту нужен только выход в Интернет и программа клиент);

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

Для оценки работы адаптированного HITS алгоритма используются формулы, разработанные во второй главе (см. раздел 2.5, стр. 91). Предложена следующая программная архитектура для автоматической оценки (рис. 21).

Рис. 21. Архитектура программной системы для автоматической оценки
списков семантически близких слов

На основе протокола rfc2229 система запрашивает список синонимов (из тезауруса WordNet) и список семантически близких слов (тезаурус Moby) и после этого сравнивает списки, построенные программой поиска семантически близких слов, с эталонными (на основе разработанных формул). Данная архитектура была реализована в качестве прототипа как один из модулей программной системы Synarcher. Связь этого модуля с пользователем через графический интерфейс на данный момент не реализована.

Выводы по главе 3

В данной главе были представлены: (1) архитектура программы Synarcher, реализующей адаптированный HITS алгоритм, (2) модель интеграции системы GATE и модуля морфологического анализа Lemmatizer (на основе разработанных автором XML-RPC клиента и сервера), (3) архитектура системы построения индексной базы данных (БД) вики-текстов вместе со структурой таблиц индексной БД и (4) архитектура программной системы оценивания списков семантически близких слов с помощью удалённого доступа к тезаурусам посредством Dict сервера.

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

В рамкам описания архитектуры программы Synarcher представлены основные классы программы и их методы, программный интерфейс доступа к Википедии и особенности реализации модуля визуализации. Программа (1) предоставляет доступ к Википедии, хранимой в базе данных MySQL, размещённой локально или удалённо, (2) позволяет задать параметры адаптированного HITS алгоритма, (3) обеспечивает хранение параметров поиска и слов, помеченных пользователем, как синонимы, на компьютере пользователя.

Модуль визуализации написан на основе кода программы визуализации вики-страниц – TouchGraph WikiBrowser. Для более удобной навигации код программы был существенно модифицирован, в контекстное меню были добавлены команды: спрятать все вершины (Hide all except node), пометить вершину как синоним (Rate synonym), показать категории (Expand Categories).

Описаны основные экраны программы, точнее вкладки¹: (1) вкладка Article, позволяющая просмотреть энциклопедическую статью, соответствующую выбранному слову, (2) вкладка Database, позволяющая подключиться к базе данных и получить статистику по базе данных, (3) вкладке Synonyms, на которой задаются параметры адаптированного HITS алгоритма, выводятся результаты поиска в табличной и текстовой форме.

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

В этой главе описана модель, позволяющая интегрировать модуль морфологического анализа Lemmatizer¹ в систему GATE. Данная модель представляет способ интеграции приложений написанных на разных языках программирования (например, С++ и Java) посредством XML-RPC протокола.

Описано назначение модулей разработанных автором: (1) GATE модуль – Russian POS Tagger, (2) XML-RPC клиент на Java – aotClient и (3) XML-RPC сервер на C++ – LemServer.

Приведён один их возможных списков модулей системы GATE, включающий модуль Russian POS Tagger. Описаны параметры модуля Russian POS Tagger для его включения в систему GATE.

В главе спроектирована архитектура системы построения индексной БД вики-текстов. Описаны таблицы и отношения в индексной БД, строимой данной системой.

В данной главе представлена архитектура программной системы оценивания синонимов, позволяющей реализовать метод численной оценки списков семантически близких слов на основе тезаурусов английского языка (WordNet и Moby). Данная система для доступа к тезаурусам использует Dict cервера. Указаны достоинства Dict cерверов для конечного пользователя

4. Эксперименты и практическое использование разработанных в диссертации алгоритмов

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

Показана работа модуля Russian POS Tagger в составе системы GATE. В качестве проверки работоспособности программного комплекса индексирования вики-текстов построен ряд индексных баз данных, приводится сравнение построенных баз данных по ряду параметров.

Работоспособность и функциональность разработанных программных комплексов (Synarcher и WikIDF) обосновывается успешно работающими unit-модулями (о методике экстремального программирования, а именно автоматических тестовых модулях см. в [6], [9], [188]).

1. Экспериментальная оценка работы адаптированного HITS алгоритма

12. Оценка тестируемого корпуса текстов

Разработанная система тестировалась на двух корпусах: Английская и Русская Википедия. Энциклопедии хранятся в базе данных MySQL. На скорости работы реализованной системы Synarcher сказываются такие параметры энциклопедии, как: число статей, число ссылок, число категорий.

Сервер Википедия (http://en.wikipedia.org) не использовался, поскольку данная реализация поиска синонимов требует значительной вычислительной нагрузки на базу данных (БД). Поэтому обрабатывалась локально установленная БД MySQL Википедия.

Параметры компьютера на котором выполнялись эксперименты: процессор – AMD Athlon XP 2700+, оперативная память – 1 Гб, винчестер – 80 Гб, операционная система – Debian Sarge 3.1.

Английская версия содержит 901 861 энциклопедических статей, 18.3 млн. внутренних перекрёстных ссылок и 1.2 млн. ссылок на категории. Тестируемая Английская Википедия соответствует онлайн версии от 8 марта 2005 г.¹

Указание версий дампов Русской Википедии и Simple Wikipedia, использованных для построения индексных БД, даётся в разделе, посвящённом индексированию на стр. 143.

13. Эксперименты с Английской Википедией

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

Поиск СБС с помощью программы Synarcher выглядит следующим образом. Пользователь задаёт исходное слово, задаёт параметры адаптированного HITS алгоритма. Программа строит список слов, который может содержать семантически близкие слова, и представляет список в виде таблицы и графа пользователю. Используя команды навигации (см. раздел 3.1), пользователь исследует граф и помечает слова (на графе и в таблице), которые, по его мнению, являются семантически близкими исходному слову. Эта информация сохраняется на компьютере пользователя. При повторном поиске эти данные будут учитываться (см описание подхода на стр. 66).

Таким способом автором, с помощью программы Synarcher, были найдены синонимы для слов Robot и Astronaut (колонка Synarcher+Эксперт в таблицах 4.1 и 4.2 соответственно). Итого было найдено 6 синонимов для слова Robot, отсутствующих в WordNet: Android, Homunculus, Domotics, Replicant, Sentience, Parahumans. Здесь тезаурус Moby не рассматривается, так как он не содержит слово Robot.

Для слова Astronaut с помощью программы Synarcher было найдено 4 синонима, из которых три отсутствуют в тезаурусах Moby и WordNet: «Space tourist», «Spationaut» и «Taikonaut» (табл. 4.2).

Таблица 4.1

Синонимы для слова Robot

Таблица 4.2

Синонимы для слова Astronaut

Синонимы	Synarcher+Эксперт	WordNet 2.0	Moby
Aeronaut			+
Cosmonaut	+	+	+
Pilot			+
Rocket man			+
Rocketeer			+
Space tourist	+
Spaceman		+	+
Spationaut	+
Taikonaut	+

Результаты экспериментов показывают, что с помощью программы Synarcher можно найти синонимы и семантически близкие слова, отсутствующие в современных тезаурусах (например, найден синоним Spationaut для слова Astronaut). Тем не менее, некоторые синонимы,представленные в тезаурусах, не были найдены. Например, синоним Automaton для слова Robot не был найден, хотя такая статья¹ в Википедии существует. Это можно объяснить несовершенством алгоритма и большим количеством статей (901.8 тыс.) среди которых выполнялся поиск.

14. Эксперименты с Русской Википедией

Русская версия энциклопедии содержит 94 632 энциклопедических статей, 3.4 млн. внутренних перекрёстных ссылок, 29.9 тыс. категорий, 390.1 тыс. ссылок на категории. Тестируемая русская Википедия в данном эксперименте соответствует онлайн версии от 18 июля 2006 г.

Для оценки работы адаптированного HITS алгоритма были выбраны четыре слова, имеющие статьи в Русской Википедии:

1. Слово жаргон, имеющее несколько синонимов² (сленг, арго, радиожаргон, феня)³;

2. Слово самолёт, для которого существуют слова для названий предметов близких по сути (планер, турболёт).

3. Многозначное слово сюжет. Слово может обозначать⁴ (1) содержание, суть случая, происшествия, фильма, рассказа о чём-нибудь, тогда синонимами будут содержание, киносюжет, (2) совокупность действий, событий, в которых раскрывается основное содержание художественного произведения, тогда синонимами будут фабула, интрига.

4. Слово истина, обозначающее понятие, не имеющее однозначного определения.

Для этих слов был выполнен поиск семантически близких слов с помощью программы Synarcher. Полный список слов, выданный программой см. в приложении (табл. 1). С помощью эксперта были отобран ряд слов наиболее близких по значению к искомому слову (табл. 4.3). Порядок слов в графе «Семантически близкие слова» в этой таблице является существенным для вычисления коэффициента Спирмена. Данный порядок был получен после опроса 16 респондентов (носителей русского языка) и представляет собой ряд упорядоченный на основе усреднённой оценки экспертов (см. об усреднении в приложении в табл. 1).

Если не указано особо, то здесь и далее поиск выполнялся при следующих параметрах адаптированного HITS алгоритма:

• размер корневого набора:200;

• инкремент: 17;

• чёрный список категорий:Страны|Века|Календарь|География_России|Люди;

• глубина поиска категорий: 10;

• ограничение сверху длины строящегося списка слов:100;

• погрешность для останова итераций: 0.01.

Идея выбора нескольких типов слов (для оценки алгоритма) и привлечения респондентов для упорядочения списков семантически близких слов взята из работы [83].

Таблица 4.3

Семантически близкие слова, полученные экспертом с помощью программы Synarcher и упорядоченные респондентами

15. Экспериментальное сравнение адаптированного с исходным HITS алгоритмом¹

Для десяти слов и словосочетаний, для которых есть энциклопедические статьи в Русской Википедии (Автопилот, Аэродром, Беспилотный летательный аппарат, Движитель, Интернационализация, Истина, Пропеллер, Самолёт, Сюжет, Турбина)², проведена серия экспериментов (рис. 22-25) для оценки времени работы и точности поиска адаптированного HITS алгоритма (AHITS) в зависимости от числа категорий (ось абсцисс).

Точность (англ. precision) – это отношение числа семантически близких слов, найденных программой, к общему числу найденных программой слов. Семантически близкие слова выбираются экспертом из общего числа слов, найденных программой. Примеры СБС для словосочетания «Беспилотный летательный аппарат» представлены в табл. 4.1.

Таблица 4.4

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