ИНЖЕНЕРНЫЙ ВЕСТНИК

УДК 004.62

Россия, МГТУ им. Н.Э. Баумана

mstu@sevik.ru

Открытые источники знаний.

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

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

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

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

Структура Википедии.

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

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

• Использование гипертекстовых ссылок в статьях позволяет просто и удобно организовать информацию по темам или в хронологическом порядке.
• Механизм категорий Википедии позволяет группировать статьи по темам, а сами темы-категории могут объединяться и разбиваться, образуя разветвлённую структуру.
• Списки позволяют объединять значительное количество ссылок на статьи, объединённые общим признаком, облегчают работу с единообразной информацией.

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

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

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

Предлагаемый алгоритм построения расширенного запроса.

Нахождение корневого множества понятий.

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

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

В том числе, проблема с расшифровкой аббревиатур. Например, пользователь вводит запрос ``МГТУ''. В случае простого полнотекстового поиска, при правильной работе модуля морфологии, в выдаче появятся только документы, который содержат именно эту аббревиатуру, а наличие в документе ее расшифровки, не смотря на то, что она по смыслу напрямую связана с исходным запросом, никак не будет учитываться при поиске. Для предлагаемого же подхода, в корневом множестве окажется страница ``МГТУ'', являющаяся редиректом на основную статью ``Московский государственный технический университет имени Н. Э. Баумана'', которая впоследствии, наряду с аббревиатурой, повлияет на место содержащего соответствующие слова документа в выборке.

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

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

Нахождение базового множества понятий.

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

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

Однако, как говорилось ранее, расстояния в Википедии весьма малы, вследствие чего расширенное множество даже при небольшом количестве переходов (3-4) получается чрезвычайно большим - сравнимым по порядку с размерами всего множества понятий в Википедии.

Для того, чтобы его ограничить, предлагается выбирать только наиболее важные ссылки. Были выделены следующие типы ссылок (в порядке убывания веса):

1.     Перенаправляющие - для понятий, страницы которых являются страницами перенаправления на другие - это самые весомые ссылки.

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

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

4.     Входящие и исходящие ссылки - простые гипертекстовые ссылки с или на данную страницу. Обладают наименьшим весом.

5.     Конкретное количество тех или иных ссылок выбирается экспериментально.

Определение ключевых понятий.

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

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

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

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

Составление запроса.

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

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

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

Исходные данные и результаты.

Для оценки качества поиска использовалась методика РОМИП [4]. Использовалась правовая коллекция документов РОМИП'2009.

Ниже приведены усредненные значения метрик, полученные для первых 100 найденных документов, для разных требований к релевантности [4].

Таблица 1.

Слабые требования к релевантности.

Таблица 2.

Сильные требования к релевантности.

Заключение.

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

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

Литература

1.   Sergey Brin and Lawrence Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine.  COMPUTER NETWORKS AND ISDN SYSTEMS. — Elsevier Science Publishers B. V., 1998. — с.107-117.

2.   Denis Turdakov, Pavel Velikhov. Semantic Relatedness Metric for Wikipedia Concepts Based on Link Analysis and its Application to Word Sense Disambiguation.— SYRCoDIS, 2008.

3.   Jon M. Kleinberg.  Authoritative Sources in a Hyperlinked Environment. — SODA, 1998. — с.668-677.

4.   Российский семинар по Оценке Методов Информационного Поиска. - http://romip.ru