Movatterモバイル変換

[0]ホーム
URL:





















Введение

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

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

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

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

Актуальность темы диссертации.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Спроектирована и реализована распределённая клиент-сервернаяархитектура в программном комплексеRussian POS Tagger2,позволяющая интегрировать среду 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В ходе исследований, представленных в диссертации, были полученыследующие результаты:

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

  2. Синонимы,которые имеют одинаковое значение, но отличаются стилистическойокраской, которая не позволяет заменять их в одномконтексте,например,глаза – очи – зенки,называютсястилистическими[18],[1].

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

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

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

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

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

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

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

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

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм WLVM

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

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

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

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

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

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

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

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

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

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

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

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

Этот тип задач замечателен тем, что включает и лексическую3,и семантическую4компоненты. Обзор современных работ по scheme / ontologymatching представлен в [164], критический обзор открытых (opensource) программных систем изложен в [190].

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм ESA

В работе1Оценка эффективности метода выполнена за счёт автоматическоговычисления степени семантической связи между фрагментамитекста произвольной длины на ЕЯ.

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

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

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

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

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

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




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

Метрики

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

Формула

Название

Коэффициент Дайса (dice)

Коэффициент Джаккарда (jaccard)

Косинусный коэффициент

Коэффициент перекрытия


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

Формула ​​​/ ссылка наописание алгоритма

Название

1. Учёт частотностисловв корпусе

Нормализованное расстояние Google (NGD)1

jaccard2[173]

Описание алгоритма см. на стр. 34.

ESA [103]

2. Учёт расстояния втаксономии3

Расстояниесоответствует числу ребер кратчайшего пути между концептами

Метрика применяласьдля концептов Тезауруса Роже [117]

265-283

Wu & Palmer [186]

Метрика res [151],адаптированная к таксономии категорий ВП [173]



3. Учёт частотности слов ирасстояния в таксономии

Расстояние res[151],[152]

Расстояние lin1[128]

4. Учёт пересечения текста

пересечение текста (глоссыWordNet)

Lesk, 1986 [74]

extended gloss overlap –пересечение глосс с учётом глосс соседних концептов WordNet

Banerjee & Pedersen, 2003 [75]

[173]


Расстояние 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].

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

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

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

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

,

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

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

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

,

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

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

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

  1. для

  2. для

  3. для

  4. для

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

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

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

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

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

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

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

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

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

GATE

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

екоторые темы (в силу исторических идругих причин) обсуждаются регулярно (например:cars, ibm, intel,apple). Теги, соответствующие этим новостям, занимают место изаслоняют в облаке потенциально более интересные на сегодня темы.

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

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


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

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

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

ис.

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

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

В приложенииClusterBall3визуализируется структура трёх уровней категорий Википедии. В центреграфа отображается родительская вершина. Статьи, на которые ссылаетсяродительская вершина, рисуются внутри шара. И, наконец, статьи,ссылающиеся на эти (внутренние) вершины отображаются во внешнемкольце. Полученные рисунки ничего не говорят о сути данных, то есть отом, какие статьи представлены, однако построенные кластеры позволяюткосвенно судить о способе организации информации в Википедии,позволяют сравнить структуру Википедии с системами MVblogosphere1,6Bone IPv62,и Gnom3,поскольку для них получены аналогичные рисунки.

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

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

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

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

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

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


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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



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

гдеhjиajпоказывают соответственно насколько документj(1) является хорошим указателем на релевантные документы (тоестьj-ый документрассматривается какхаб-документ) и (2) является авторитетным документом.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(2.3)

(2.4)

(2.5)

(2.6)

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

  3. .






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

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


Subgraph(s,t,d)

,.

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

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

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

Обозначим

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

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


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

For each pRs

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

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

Bs += Г+(p).

If ||<= d then

Bs +=.

Else

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

End

Return Bs

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

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



∙2

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

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


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

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

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

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

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

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


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

  2. |> 0 && ([0]<))BEGIN

  3. [0];// v1, v2 – вершины смежные ребруe

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


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

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

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

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

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

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

N)операций, второй –O(C2).Тогда предобработка в целом требуетO(CN+C2)операций.

N+ C2)+ O(C2(C+ N)) =O(C3+ N)

(2.8)

где:

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

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

Дано:

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

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

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

.

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

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

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

CalcSimilarVertices(G, )

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

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

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

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

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

Эвристики1

времени

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

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

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

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

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

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

более длинный, составленныйавтоматически. В конец спискаB добавляются отсутствующие внём элементыА. Далее применяется формула

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

В данной главе были разработаны: (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 алгоритмом при разных параметрах поиска.


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

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

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

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

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


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

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

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

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

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

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

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

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

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


Frame6


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

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

При нажатии на кнопку «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,





Задание параметров адаптированного HITS алгоритма

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

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



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

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

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

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

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

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

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


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



Frame1

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

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


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

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

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

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

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

Итак, спроектированаархитектура программной системы индексирования вики-текстов.1На рис. 19поа уровнезаписей (англ. «recordlevel inverted index»),содержащая список ссылок на документы для каждого слова (точнее —для каждой леммы).2

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



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

TF-IDFIndexDBTF-IDFПриложение

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

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

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

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

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

Число таблиц в индексной базеданных, их наполнение и связи между ними были определены исходя изрешаемой задачи: поиск текстов по заданному слову с помощью TF*IDFформулы (см. ниже). Для этого достаточно трёх4таблиц и ряда полей (Рис. 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.


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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

Разработанная система тестировалась на двух корпусах: Английская иРусская Википедия. Энциклопедии хранятся в базе данных 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 г.1

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

Нужно отметить, что поиск синонимов и семантически близких слов неявляется полностью автоматическим2.Программа 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).

Синонимы

Synarcher+Эксперт

WordNet 2.0

Android1

+


Automaton


+

Golem

+

+

Homunculus

+


Domotics

+


Replicant

+


Sentience

+


Parahumans

+


Синонимы

Synarcher+Эксперт

WordNet 2.0

Moby

Aeronaut



+

Cosmonaut

+

+

+

Pilot



+

Rocket man



+

Rocketeer



+

Space tourist

+



Spaceman


+

+

Spationaut

+



Taikonaut

+




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

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

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

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

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

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

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

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

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

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

Слово

Семантически близкие слова

Жаргон

Сленг, Просторечие, Матерщина, Диалект, Арго1,Эвфемизм

Истина

Факт, Правда, Реальность, Действительность,Знание, Бог, Вера, Авторитет, Догмат

Самолёт2

Планер, Турболёт, Автожир, Экранолёт,Экраноплан, Авиация, Транспорт, Штурмовик, Махолёт, Мускулолёт,Дельтаплан, Вертолёт, Винтокрыл, Авиапушка, Фюзеляж, Двигатель,Винт

Сюжет

Интрига, Переживание, Конфликт, Трагедия,Коллизия, Противоречие

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

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


Чёрный список категорий (blacklist) составляется экспертом исужает пространство поиска. Например, включение категории «ХХвек» в blacklist позволяет отсечь множество документов сзаголовками:1900,1901,1902 и т. д. Вэксперименте для фильтрации выбираются категории с максимальнымчислом слов, не являющихся семантически близкими заданному слову1.На рис. 22 представлены не сами категории, а только их число(здесь от 0 до 15). Число0 означает, что нет фильтрациикатегорий.



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

1. Категории. Проведено шестьопытов с разным числом категорий: 0, 1, 3, 6, 10, 17. Были выбраныкатегории с максимальным числом слов, не являющихся релевантными.Такие категории позволяют отсечь большое число статей, заведомо неотносящихся к делу. Первая фильтруемая категория (для словаСамолёт)называетсяВикипедия:Избранные_статьина неё ссылается 14 найденных слов. Три категории включают в себявышеуказанную, а также:Незавершённые_статьи_по_географии|Незавершённые_статьи.Шесть категорий включают (помимо трёх, ещё три)Химические_элементы|Государство|Википедия:Статьи_к_викификации.10 категорий включают ещё четыре категорииМеханика|Столицы_Летних_олимпиад|Мегаполисы|История_Европы.17 категорий включают ещё семьТюркские_народы|Город|Локомотивы|Города-государства|Народы_России|Википедия:Хорошие_статьи_о_технике|Дворянство.



Русской Википедии соответствуеторграф, содержащий 171 тыс. вершин, 3.4 млн дуг (на 11.05.07). Припоиске в графе AHITS алгоритм строит базовый набор с числом вершин200-800, числом дуг 800-12 000 (для словаСамолёт).Указан диапазон вершин и дуг, поскольку изменение фильтруемыхкатегорий меняет число вершин, включаемых в базовый набор. Такимобразом, рис. 23обобщает результаты шести опытов с разными размерами базовых наборов,построенных для словаСамолёт.

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

В опытах при увеличении числа категорий (при числе категорий большенуля) время поиска уменьшается. В данном опыте время снизилось с5.2 с (максимальное значение при одной категории) до 2.8 с(при 17 категориях). Это объясняется тем, что при увеличениичисла фильтруемых категорий пространство поиска сужается. Тогдамаксимальное время работы алгоритма будет при минимальном числекатегорий, то есть при фильтрации по одной категории1,см. рис. 22-25.

3. Точность поиска. На рис. 23 видно, что использованиекатегорий увеличивает точность поиска. Максимальная точность 15.2%получена при 17 категориях, минимальная точность 6% – при однойкатегориях. В среднем (по пяти опытам с числом категорий:1,3, 6, 10, 17) это превышает точность 11%, полученную в случае,когда категории не учитываются на 6.5%.



Основная разница HITS и AHITS алгоритмов – не учёт и учёткатегорий соответственно. При числе категорий ноль (первыйвертикальный ряд на рис. 22-25) можно считать, что работа AHITSалгоритма (по скорости и точности поиска) соответствует работе HITSалгоритма. Это позволяет сравнить HITS и AHITS алгоритмы в следующейтаблице 4.5.




В столбцеHITS (табл. 4.5) указано время работы алгоритмаAHITS без учёта категорий. В столбцеAHITS дано среднее времяработы алгоритма при числе категорий больше нуля. Значения столбца«Замедление работы, %» вычислялось по формуле(AHITS – HITS)/AHITS100%.Таким образом, усреднение по девяти словам показало, чтоадаптированный HITS алгоритм работает на52%медленнее HITS алгоритма.

Слово

HITS, c

AHITS, c

Замедление работы, %

Аэродром

1,19

2,29

48,03

Беспилотный летательный аппарат

0,54

1,1

50,91

Движитель

2,17

5,39

59,74

Интернационализация

0,39

0,84

53,57

Истина

1,11

4,3

74,19

Пропеллер

0,94

2,85

67,05

Самолёт

2,87

3,64

21,15

Сюжет

4,85

7,67

36,77

Турбина

1,63

3,9

58,21

Среднее:

1,74

3,55

52,18



При каждом числе категорий получено своё значениеточности (в AHITS алгоритме), поэтому можно указать минимальное(Min), среднее (Avg) и максимальное (Max)значение точности (P AHITS) для каждогослова. Изменение точности вычисляется по формуле(P AHITS  P HITS ) / P HITS , при этом было вычислено изменение точности в худшем (при минимальномзначении точности алгоритма AHITS), среднем и лучшем случаях. Такимобразом, точность поиска адаптированного HITS алгоритма выше точностипоиска HITS алгоритма в худшем на -6.3%, среднем – на33.3%и в лучшем – на 77.8%.Изменение точности поиска в зависимости от числа фильтруемыхкатегорий представлено на рис. 26.


Респонденты (13 человек обработали 153 слова, 16 человек – 200слов) присвоили значения от 0 до 10 семантической близости парамслов, где 0 указывает на то, что слова совершенно не связаны, 10 –слова почти полные синонимы. Критика данного тестового набора,приведённая в работе [117], заключается в том, что:

Достоинство данного тестового набора в том, что он

Подробное описание экспериментов по оценке результатов поиска СБС вАнглий­ской и Simple2ВП приведено в работе [35], [36]. Основные резуль­таты даннойподглавы связаны


–

–

–


–


–

–

–

–


–

–

–


–

–


–

–

–

–

–

–

–


–

IntelliZap

0.56

–

–

–


Таким образом, оценка корреляции результатовпоиска СБС с тестовым набором 353-TC показала, что алгоритм AHITSдаёт несколько лучший результат (0.38-0.39), чем адаптированнаяметрика Резника (0.33-0.36) и хуже, чем алгоритм WLVM (0.45-0.72) наданных Английской Википедии. В экспериментах с Википедией наанглийском упрощённом языке получен значительный разброс значенийкорреляции для AHITS: от 0.15 до 0.4.6

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

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

В этой таблице столбецF – это значение коэффициента.Данный коэффициент получается при сравнении списка построенногопрограммой (длина этого списка указана в столбцеN) и спискапостроенного экспертом и упорядоченного респондентами (табл. 4.3).В столбце «Набор слов» в таблице 4.7 указаны теслова, выбранные экспертом, которые вошли в список, построенныйавтоматически программой Synarcher. В конце каждого слова стоитчисло, соответствующая порядковому номеру слова в автоматическипостроенном списке. Чем меньше эти номера и чем больше слов в столбце«Набор слов», тем более похож автоматическипостроенный список на список семантически близких слов, построенныйэкспертом. В этом случае значение коэффициентабудет меньше.

Применение эвристики не изменило результат поиска для словаистина.900 – это максимальное значение коэффициентадля списков из 100 и 9 слов, то есть их пересечение пусто. Это можнообъяснить большим количеством статей, которые связаны со статьёйИстина: на неё ссылается 45 статей.

Преимущество и недостаток данной эвристики в сужении пространствапоиска. Этим объясняется тот факт, что для словаЖаргон привключённой эвристике (1) синонимДиалект был пропущен, (2)общее число полученных семантически близких слов снизилось с 48 до11 (табл. 4.7).



Без эвристики

С эвристикой

Слово

F

N

Набор слов

F

N

Набор слов

Жаргон

129

48

Арго8,Сленг11,Эвфемизм19,Диалект28,Матерщина36,Просторечие42

27

11

Арго1,Матерщина2,Эвфемизм3,Просторечие4,Сленг8

Истина

900

100

Нет

900

100

Нет

Самолёт

161

100

Планер5,Автожир9,Экранолёт12,Турболёт13,Экраноплан41,Конвертоплан96

48

78

Планер2,Автожир4,Турболёт6,Экраноплан7,Экранолёт9,Конвертоплан35

Сюжет

547

100

Трагедия50

446

95

Трагедия12,Интрига57


Данный опыт показал, что в целом применение эвристики (не учитыватьстатьи с пробелами) понижает значение коэффициента(табл. 4.7), то есть строится список, более близкий к спискуэксперта. Это был ожидаемый результат, поскольку список семантическиблизких слов, построенный экспертом (табл. 4.3), содержитоднословные понятия, то есть слова без пробелов.

Было проведено 66 опытов для каждого из четырёх слов:жаргон,истина, самолёт, сюжет. Менялись такие входные параметрыадаптированного HITS алгоритма, как: размер корневого набора страниц(от 10 до 510 с шагом 50), инкремент (от 10 до 60 с шагом 10)3.Чёрный список категорий был тот же, что и в других экспериментах:Страны|Века|Календарь|География_России|Люди. Погрешность дляостанова итераций: 0.01. Усреднённые значения выходных параметровалгоритма приведены в таблице 4.8.

Слово

F

Inter-section

Nexpert

Nauto

time (мин)

iter

vertices

edges

Scategory

Жаргон

5.6

30.2

155.4

393.4

19855.2

Истина

900.0

0

9

100

19.9

19.2

458.8

2631.0

73257

Самолёт

50.2

86.8

7.4

12.6

144.0

547.0

29252.2

Сюжет

426.2

1.9

6

90.1

32.3

14.2

849.0

4381.4

119069.2


ГрафаIntersection указывает среднее число общих слов двухсписков: (1) списка построенного экспертом и упорядоченногореспондентами, см. таблицу 4.3 (размер этого списка указан в графеN expert) и (2) списка,автоматически построенного программой (размер этого списка см. вграфеN auto).

ГрафаS category показывает число шаговпо дереву категорий, для того чтобы выяснить, какие статьи нужноудалить / добавить в зависимости от содержимого входногопараметра алгоритма:чёрный список категорий. Этот параметр,также как и параметры:time (время выполнения поиска),iter(число итераций для вычислений весовhub иauthorityстраниц), позволяет косвенно судить о временных затратах алгоритма.

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

Эксперименты показали быструю сходимость итеративных вычислений(порядка 20, 30 шагов), см. графуiter в таблице 4.8.Аналогичная скорость сходимости указана в [125] в экспериментах попоиску похожих интернет страниц.

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

В таблице 4.9 указаны минимальное (F min),максимальное (F max), среднее значение(F avg) и стандартное отклонение(F stdev) коэффициентадля той же серии опытов, что и в предыдущей таблице.

Слово

Fmin

Fmax

Favg

Fstdev

Жаргон

20

30

22.36

2.75

Самолёт

45

59

50.21

4.41

Сюжет

60

479

426.18

95.97


Из таблицы 4.9 можно сделать вывод, что для некоторых слов (жаргон,самолёт) качество результата поиска достаточно стабильно1(значение стандартного отклонения коэффициента2.75 и 4.41 соответственно). В этом случае перед пользователем нестоит такой нетривиальной2задачи, как выбор входных параметров адаптированного HITS алгоритма.

Для многозначного словасюжетвсёсложнее. Такое высокое значение стандартного отклонениякоэффициента(95.97) указывает, что наличие в автоматически построенном списке техслов, которые являются семантически близкими, в большей степенизависит от входных параметров алгоритма. Возможно, это связано сбольшей употребимостью словасюжетв текстах энциклопедических статей, с большим количествомссылок на эту статью (среднее число вершин – 849.0, рёбер –4381.4 в базовом наборе для словасюжет, см. таблицу 4.8). Длятаких слов пользователю программы, вероятно, придётся не раз менятьпараметры программы поиска, чтобы найти как можно больше семантическиблизких слов.

    1. Сессиянормализации слов на основе модуляRussian POS Tagger,как одного из этапов автоматической обработки текстов в системеGATE

Ниже приведён пример результата работы модуляLemmatizer(разработанного в проекте Диалинг [59]) для словарама.Результат включает в себя (1) лемму слова, (2) часть речи(C,Г,П,...), (3) информацию о словоформе в кодах Ancode1,(4) граммему2,(5) уникальный идентификатор, (6) список словоформ:

И результат работы для словадоброго:

Более подробно о работе морфологического модуляLemmatizer см.в работах [59], [60].


Параметры GATE модуляRussian POS Tagger



Нарис. 28показано, что приложениюpipeline_enприсвоена после­до­ва­тель­ность из четырёхобработчиков (Document Reset PR, ANNIE English Toke­nizer, ANNIESentence Splitter, Russian POS Tagger)1и каждому из обра­бот­чиков присвоен текстовый ресурсsignatures_en.txt. Нарисунке показано при­своение текстового ресурса свойствуdocumentмодуляRussian POS Taggerи отмечено, что это необходимый параметр (required).


Определение последовательности обработчиков в GATE




Результат построения аннотацийParadigmиWordform




    1. Индексированиевики-текста: инструментарий и эксперименты

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

Преобразование вики-текста с помощью регулярных выражений

Решения по парсингу вики-текста

N

Вопросы

Ответы

1

Заголовки (подписи)рисунков

Оставить (извлечь)



2

Интервики

Оставить или удалить определяетсяпользователем (параметр).

3

Название категорий

Удалить.

Регулярное выражение (RE):\[\[Категория:.+?\]\]

4

Шаблоны; цитаты1;таблицы

Удалить.

5

Курсивный шрифт и «жирное»написание.

Знаки выделения (апострофы) удаляются.

6

Внутренняя ссылка


Оставить текст, видимый пользователю, удалитьскрытый текст.


RE:внутренняя ссылка без вертикальной черты:\[\[([^:|]+?)\]\]

7

Внешняя ссылка


Оставить текст, видимый пользователю, удалитьсами гиперссылки.

RE:Имя сайта (без пробелов), содержащее точку '.' хотя бы раз, кромепоследнего символа:
(\A|\s)\S+?[.]\S+?[^.]([\s,!?]|\z)

8

Примечание.

Раскрывать, переносить в конец текста.



(i) Удаляются такие теги(вместе с текстом внутри них):

  1. HTML комментарии ();

  2. теги выключения форматирования()2;

  3. теги исходных кодови

(ii) Выполняются преобразованиявики-тегов:

  5. ;текст остаётся

  7. Из тега изображения извлекается его название,прочие элементы удаляются;

  9. Обрабатываются одинарные квадратные скобки,обрамляющие гиперссылки: ссылка удаляется, текст остаётся;

Данный преобразовательвики-текста воплощён в виде одного из Java-па­ке­товпрограммной системы Synarcher [126]. Для замены элементов тексташи­ро­ко использовались регулярные выражения [63] языкаJava. В табл. 4.11 при­ведён фрагмент статьи РусскойВикипедии «Через тернии к звёздам (фильм)». Показанрезультат комплексного преобразования текста по всем вышеуказаннымправилам.

Пример преобразования вики-текста1





















API индексной базы данных вики

Укажем существующие программныеинтерфейсы (API) для работы c данными ВП:

I.) Интерфейс верхнегоуровня позволяет:

  1. получить список терминов дляданной вики-страницы, упорядоченный по значению TF-IDF;

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

Экспериментыпо построению индексных баз данных

Разработанная программная система индексирования вики-текстовпозволила построить индексные БД для Simple English1(далее SEW) и Русской2(далее RW) википедий и провести эксперименты. Статистическаяинформация об исходных БД, о парсинге и о размерах полученных БДпредставлены в табл. 4.12.

В двух столбцах («RW / SEW 07» и «RW / SEW08») указано во сколько раз параметры русского корпусапревосходят английский по дампам от 2007 года (SEW от 9 и RW от 20сентября) и от 2008 года (SEW от 14 и RW от 20 февраля). Данными,характеризующими корпус текстов Русской Википедии, можно назватьбольшое количество лексем(1.43 млн) и общего числа слов (32.93 млн). Р9.6, всего слов 14.4 раза.

Значения следующих двухстолбцов («SEW 08/07 %» и «RW 08/07 %»)указывают, насколько выросли (по сравнению с собой же) английский ирусский корпуса за пять месяцев с сентября 2007 до февраля 2008 гг.

В последнем столбце (SEW↑ /RW↑)указано насколько быстрее шёл рост английского корпуса по сравнению срусским (отношение предыдущих двух столбцов), а именно: на 12%быстрее появлялись статьи и на 6% быстрее пополнялся лексиконВикипедии на английском упрощённом языке.

Статистика по Русской Википедии и SimpleWikipedia, парсингу

и сгенерированным индексным базам данных

БД Википедии

Simple English (SEW 08)

Russian (RW 08)


RW/SEW 07

RW/SEW 08


SEW 08/07

%

RW 08/07

%

SEW

База данных Википедии


Исходный дамп, дата

14 фев. 2008

20 фев. 2008


–

–


–

–

–

Исходный дамп, размер, МБ1

21.11

240.38


15.9

14.4


40

26

10

Статей, тыс.

25.22

239.29


10.7

9.5


31

17

12

Парсинг

Парсинг всего, ч

3.63

69.26


15.1

19.1


4

32

-21

Парсинг одной страницы, сек

0.52

1.04


1.42

2.01


-20

13

-30

Индексная база данных Википедии

Лексемв корпусе, млн

0.149

1.43


10.2

9.6


23

16

6

Лексема-страница (<=1000 дляслова)2,млн

1.65

15.71


10.1

9.5


24

16

6

Слов в корпусе, млн

2.28

32.93


15.1

14.4


29

23

5

Размер сжатого файла дампаиндексной БД, МБ

7.15

77.5


11.5

10.8


25

17

6


Чтобы время парсинга,приведённое в табл. 4.12, имело смысл, укажем параметры рабочегокомпьютера и версии двух основных программ: ОС Debian 4.0 etch, ядроLinux 2.6.22.4, процессор AMD 2.6 ГГц, 1 ГБ RAM, Java SE 1.6.0_03,MySQL 5.0.51a-3.

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

Проверка выполнения закона Ципфа длявики-текстов

Эмпирический закон Ципфаговорит о том, что частота употребления слова в корпусе обратнопропорциональна его рангу в списке упорядоченных по частоте словэтого корпуса[131](стр. 23), то есть второе по частоте слово будет употребляться втекстах в два раза реже чем первое, третье — в три раза и такдалее.

Другая формулировка законаЦипфа гласит: если построить список слов, отранжировав слова поуменьшению их частоты встречаемости в некоторомдостаточнобольшом тексте, инарисовать график логарифма частот слов в зависимости от логарифмапорядкового номера в списке, то получится прямая[155].См. также построение аппроксимирующих расчётных ранговыхраспределений частот появления слов (РРЧС) в тексте А. С. Пушкина“Медный всадник” в работе[4].

На рис. 30слова упорядочены (по убыванию частоты) вдоль оси абсцисс, вдоль осиординат отложена частота слов. Кривая, составленная из знаков «+»,построена по данным корпуса текстов Русской Википедии «RW 08».С помощью метода наименьших квадратов пакета Scilab [91]были построены и нарисованыаппроксимирующие кривыепо первым ста наиболее частотным словам корпуса (см. рис. 30,криваярозового цвета, длинный пунктир) ипо первым 10 тыс. слов (голубая линия, пунктир с точкой):


;

(4.1)


Знакам «»на рис. 30 соответствуют данные Википедии «SEW 08».Аналогично нарисованы аппроксимирующие кривые:(зелёного цвета, точечный пунктир) и(красного цвета, пунктир с двумя точками):


;

(4.2)



Рис. 30показывает, что закон Ципфа в целом выполняется для текстоввикипедий, то есть кривую на рисунке с логарифмическим масштабомвполне можно аппроксимировать прямой. При этом данные SimpleWikipedia(0.20)1соответствуют данному закону немного лучше корпуса русских текстов(0.23). Что довольно-таки странно, поскольку размер Русской Википедиина порядок больше (табл. 4.12).Такое пристрастие выполнения закона к текстам на английскомупрощённом языке, по сравнению с русским, можно объяснить либоособенностью упрощённого языка, либо разницей между русским ианглийским языками. Для окончательного выяснения вопроса нужно решитьзадачу промышленного масштаба, а именно: построить индексную БД дляEnglish Wikipedia.




На рис. 31представлено распределение частоты слов в текстах двух википедийвдва момента времени,то есть на рисунке приведены данные для тех же четырёх корпусов(индексных БД), что представлены в табл. 4.12.Перечислим значения пяти кривых (сверху вниз) на рис. 31:

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

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

а) взять первую 1000 слов по частоте в корпусе, упорядочить почислу документов, построить график;

б) найти число слов с частотой 1, 2, 3.. 10..1000 слов в корпусе(привести в таблице и построить гистограмму);

в) найти число слов длиной 1 буква, 2, 3.. 30 (таблица игистограмма);

г) сравнить изменение ранга слов (по популярности, то естьчастоте употребления) в корпусе со временем (слово, ранг,повышение/понижение — на сколько), (подсказка: нужно построитьдве индексных БД для разных по времени дампов википедий); указатьчасто употребимые слова, ранг которых изменился максимально;

д) найти число различныхлексем в документе; среднее и максимальное число по всем документам;то же, но нормированное на число слов в документе; вычислить списокпервых десяти самых «пёстрых» документов, то есть богатыхсвоим лексиконом, а именно: содержащих максимальное значениеотношения числа уникальных лексем к числу слов в документе; обратнаязадача: построить упорядоченный список самых «нудных»,т.е. длинных, но бедных лексиконом документов.

    1. Экспериментыв проекте «Контекстно-зависимый поиск документов впроблемно-ориентированных корпусах»

В проекте «Контекстно-зависимый поиск документов впроблемно-ориентированных корпусах» предлагается решение задачапоиска похожих документов на основе онтологий1.

Задача поиска похожих документов решается в два этапа: индексированиеи поиск на основе индекса.

  1. Индексирование документов относительно онтологии заключаетсяв (i) определении фрагмента онтологии, соответствующегодокументу (классы, атрибуты, отношения между ними, см. рис. 34),(ii) вычислении сходства (similarity) между документом иданным фрагментом онтологии. В базе данных сохраняется тройка<A'',Doc ID, Sim>,гдеA''–фрагмент онтологии,Doc ID–идентификатор документа,Sim– степень сходства. Предложено два варианта индексирования: наоснове категорий(рис. 32)и полнотекстовое (рис. 33).При полнотекстовом индексировании используется модульRussianPOS Tagger (см., раздел3.2на стр. 106).



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




Для решения данных задач автором были спроектированы и реализованы:(i) алгоритм индексирования на основе категорий Википедии,(ii) алгоритм сравнения графов, (iii) алгоритм выбораминимального связного набора вершин в графе (рис. 35).




Алгоритм сравнения графов и алгоритм выбора минимального связногонабора вершин реализованы в виде модулей библиотеки Java UniversalNetwork / Graph Framework (JUNG) [144].JUNG – это программная библиотека с открытымисходным кодом, обеспечивающая средства для управления, анализа ивизуализации таких данных, которые можно представить в виде графа.

Для демонстрации алгоритма сравнения графов автором созданоприложение Java WebStart, позволяющее сравнивать графы1.Данное приложение можно также рассматривать как пример интеграциибиблиотеки JUNG и технологии WebStart2.

Для визуального отображения графов в целях отладки (см., например,рис. 34, 35) использовался формат и программаPajek,разработанные словенскими учёными [78].


В этой главе (1) описаны эксперименты поискасинонимов в Английской и Русской Википедии с помощью адаптированногоHITS алгоритма, (2) дано описание (с точки зрения пользователя)сессии поиска синонимов в программы Synarcher (реализующейадаптированный HITS алгоритм), (3) численно проверена пользапредложенных поисковых эвристик, (4) проведены эксперименты попостроению индексных баз данных вики-текстов, (5) полученоподтверждение выполнения закона Ципфа для текстов двух Википедий.

Экспериментыпозволяют сделать вывод, что программа Synarcher позволяет находитьсинонимы и семантически близкие слова в Английской Википедии,отсутствующие в современных тезаурусах WordNet, Moby (например,найден синонимSpationaut для словаAstronaut). Тем неменее некоторые синонимы, представленные в тезаурусах, не былинайдены. Таким образом, можно улучшить алгоритм, используя данныетезаурусов.

Экспериментыпоказывают, что работа AHITS алгоритма медленнее HITS алгоритма всреднем на 52%, а точность поиска AHITS алгоритма вышена33%.

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

Предложеннаямодификация коэффициента Спирмена позволила провести эксперименты дляоценки чувствительности результатов адаптированного HITS алгоритма кпараметрам поиска. Для ряда слов из Русской Википедии (Жаргон,Cамолёт) качество результата поиска1было достаточно стабильным (значение стандартного отклонениякоэффициента Спирмена 2.75 и 4.41 соответственно), что избавляетпользователя от необходимости тщательно подбирать параметры поиска.Для более часто употребимого (в данном корпусе текстов) словаСюжеткачество результата оказалось в большей степени зависимым от входныхпараметров алгоритма (значение стандартного отклонения коэффициентаСпирмена 95.97).

Описаны данныеморфологического анализа Lemmatizer, доступные в модуле Russian POSTagger. Представлен пример инициализации модуля Russian POS Tagger,указаны параметры для его подключения к XML-RPC серверу LemServer.Показан способ подключения и результаты работы модуля Russian POSTagger в составе системы GATE.

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

Проведеныэксперименты, подтверждающие выполнение эмпирического закона Ципфадля текстов Русской Википедии и Википедии на английском упрощённомязыке.


    Заключение

Одной из важных современных задач является задача поиска информации.Подзадачей является п

Анализ методов поиска синонимов и методов поиска похожих интернетстраниц показал, что HITS алгоритм наиболее подходит для поискапохожих документов в корпусах текстов специальной структуры (сгиперссылками и категориями). HITS алгоритма, изначальнопредназначенный для поиска похожих страниц в Интернете, быладаптирован для поиска наиболее похожих документов в корпусе текстовспециальной структуры с использованием алгоритма кластеризации.Данный алгоритм был реализован в программном продуктеSynarcherс визуализацией результатов поиска и с возможностями интерактивногопоиска. Эксперименты показали возможность находить синонимы исемантически близкие слова в Английской Википедии, отсутствующие всовременных тезаурусах WordNet, Moby.

В работе предложен итеративный алгоритм поиска похожих вершин графа.Предложены эвристики и проведена оценка временной сложностиалгоритма.

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

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

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

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

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






    Приложение 1

ИПС










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

Жаргон

Слово|Арго|Матерщина|Эвфемизм|Просторечие|ЗЫ|Ака|Диалектология|Сленг|Франц.|Аниме

Истина2

Философия|Религия|Математика|Христианство|Искусство|Физика|Логика|Теология|Химия|Биология|История|Медицина|Натурфилософия|Мифология|Идеология|Экономика|Механика|Теория|Психология|Филология|Мировоззрение|Современность|Постмодерн|Мистицизм|Вселенная|Викиновости|США|Диалектика|Астрономия|Космология|Гипотеза|Право|Демокрит|Социология|Информатика|Магия|Гносеология|Астрофизика|Космогония|Богословие|Космос|Эмпиризм|Атом|Экология|Абстракция|Агностицизм|Алгебра|Лингвистика|Схоластика|Мораль|Дедукция|Образование|Эксперимент|Антропология|Средневековье|Каббала|Материаловедение|Техника|Язык|Гравитация|Хаос|Геометрия|Криптография|Геология|СССР|Звезда|Оптика|Алхимия|Лженаука|Кибернетика|Архитектура|Электрон|Астрология|Иммунология|Фрактал|Пространство-время|Псевдонаука|Возрождение|Марксизм-ленинизм|Индукция|Космонавтика|Робототехника|Галактика|Нейтрон|Бионика|Парапсихология|Политология|Радиоактивность|Технология|ДНК|Электротехника|Компьютер|Полупроводник|Нумерология|Электроника|Портал:Наука|Культурология|Нанотехнология|Шизофрения|Свет

Самолёт

Вертолёт|Аэростат|Планер|Мускулолёт|Автожир|Винтокрыл|Турболёт|Экраноплан|Махолёт|Экранолёт|Викисклад|Авиация|Атмосфера|Воздух|Водород|Винт|СССР|Гелий|США|Газ|Аэропорт|Фарнборо|Пулемёт|DARPA|Давление|Сибирь|Радио|Киловатт|Движитель|А-50|Дирижабль|Шарльер|Монгольфьер|Велосипед|Двигатель|Конвертоплан|Педаль|ОКБ|Вектор|Тангаж|Крен|Пожар|Артиллерия|Эверест|Фенестрон|Спецназ|Разведка|Медицина|Ка-50|Москва|ИКАО|Феодосия|Boeing|Ан-225|Мореходность|Каспийск|ИМО|Амфибия|Дельтаплан|Параплан|Катапульта|Ива|Шёлк|Фюзеляж|Ла-Манш|Икар|Бензин|Инфраструктура|Скорость|Самолет|ПВО|Космонавтика|Керосин|Судно|Энергия|Гироскоп|Корабль|Техника

Сюжет

Философия|Наука|Искусство|Религия|История|Идеология|Бог|Христианство|Литература|Культура|Поэзия|Античность|Трагедия|Эпос|Илиада|Поэт|Одиссея|Символизм|Аллегория|Ирония|Общество|Мировоззрение|Драма|Католицизм|Фольклор|Романтизм|Личность|Грех|Гёте|Мистика|Символ|Человечество|Персонаж|Евангелие|Имя|Катастрофа|Фантастика|Пролетариат|Притча|Бессмертие|Эстетика|Познание|Абстракция|Викицитатник|Эмоция|Семиотика|Скульптура|Абстракционизм|Документ|Художник|Письменность|Цвет|Мифология|Натурфилософия|Образ|Реализм|Мотив|Интрига|Шекспир|Сатира|Сказка|Агиография|Проза|Антропоморфизм|Жанр|Метод|Автор|Текст|Знак|XVII|Миф|Событие|Атеизм|Аноним|Неоязычество|Викисклад|Живопись|Фотография|Кинематограф|Метафора|Реклама|Изображение|Орнамент|Герой|Ритм|Комедия|Кино|Драматургия|Шиллер|Трилогия|Басня|Компьютер|Минерал|Саундтрек|Баба-Яга



Приложение 

Задача упорядочения списка семантически близких слов была решена с помощью привлечения респондентов, носителей русского языка. Им былпредставлен список слов (графа «Слова» в табл. 1)и поставлена задача «упорядочить список слов с тем, чтобынаиболее близкие по значению слова были в начале списка». Такоеранжирование позволяет соотнести каждому слову в списке –некоторое целое число – его ранг, порядковый номер в списке.Чем меньше ранг у слова, тем оно ближе по значению к исходному.

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

Эксперт N

Слово

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

Среднее

3

7

8

9

8

7

7

8

5

9

6

6

9

5

6

7

6,88

9

6

1

9

1

8

8

1

1

9

6

2

9

5

6

8

5,56

7

8

3

9

9

3

9

9

5

9

6

2

9

6

6

9

6,81

5

1

6

3

5

5

2

7

1

5

1

5

3

2

2

4

3,56

8

9

9

9

7

9

6

5

2

9

2

2

9

5

6

5

6,38

6

5

4

9

6

1

4

4

2

9

2

3

4

3

6

6

4,63

2

3

2

9

2

2

5

2

1

1

6

1

1

2

1

1

2,56

4

4

7

2

3

4

1

6

1

3

1

6

2

2

2

3

3,19

1

2

5

1

4

6

3

3

1

3

1

6

5

2

2

2

2,94


Наличие такой численной оценки положения слов всписке, позволяет их усреднить (графа «Среднее»),то есть упорядочить на основе оценок экспертов. Таким образом,упорядоченный список семантически близких слов для словаИстинабудет такой:Правда, Факт, Реальность, Действительность, Знание,Бог, Догмат, Вера, Авторитет.

Результат упорядочения списков (тем же способом)для словЖаргон,Самолёт,Сюжет представлен втаблице 4.3.

Три базовых принципа формирования Википедии:

  1. NPOV (Neutral Point Of View) – представление содержаниястатей с нейтральной точки зрения. На спорные и конфликтные темыпредставляются все значимые точки зрения без навязывания своегомнения. Прения по некоторому вопросу обсуждаются, оцениваются, ноавторы статей в них не вовлекаются. Необходимо холодное, честное,аналитическое описание вопроса.

  2. Verifiability – возможность проверить материал, наличиессылок на достоверные источники, на опубликованные материалы.

  3. No original research – Википедия – это непервоисточник информации. Цитирование источников позволяет проверитьнадёжность информации.

Отношения в Википедии

MediaWiki (оболочка Wikipedia)предоставляет механизм категорий, позволяющий классифицировать статьии другие страницы в проектах Wikimedia. Категории выбираются иприсваиваются статьям в ходе совместной работы пользователей (такназываемый процесс collaborative tagging, другое название –folksonomy1.Страница категории представляет из себя (i) заголовок –название категории, (ii) краткое описание назначениякатегории(аналог глоссы в тезаурусе)1,(iii) список названий статей, имеющих данную категорию.Закономерно поэтому, что систему категорий называют тезаурусом сиерархическими отношениями между категориями[184].Иерархические отношения между категориями возможны, посколькукатегории могут быть присвоены не только статьям, но и самимкатегориям в Википедии. Категории используются в поисковых алгоритмах[176],[182].

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

Отношение

Обозначение

В терминах MediaWiki

Эквивалентность (синонимия)

USE

USE FOR

Перенаправление (redirect)

Иерархия

Broader Term

Narrow Term

Категории данной категории

Подкатегории данной категории

Ассоциативность

Related Term

Ссылки между категориями


В Википедии активноиспользуется механизм перенаправлений, или иначе отношениеэквивалентности2.Механизм перенаправлений позволяет решить такие проблемы, какзаглавные/сточные буквы в заголовке статьи, разные варианты написаниязаглавного слова, аббревиатуры, синонимы3,разговорные выражения, научная терминология[135].

Пример иерархической цепочкикатегорий (Broader Term) для категории «Шифр» –«Криптография» – «Защита информации» –«Информатика»и т.д. Пример иерархической цепочки подкатегорий (Narrow Term) длякатегории «Криптография» – «Аутентификация»– «Биометрия».

Гиперссылки – этоосновной способ навигации в Веб, они же связывают как страницы, так икатегории в Википедии. Ассоциативные отношения между категориямиопределяются наличием обычных ссылок между страницами-категориями[184].В работе[103]различают понятияrelatedterms (семантическисвязанные, близкие по значению слова) иsimilarterms –семантически сходные, сходные по значению слова (в основномсинонимы). Таким образом, понятиеSemanticrelatedness шире,чемSemanticsimilarity, так каксюда включаются (кроме синонимии) ещё отношения: меронимии, антонимиии др.[103].

К какому виду отношений отнестиссылки между статьями энциклопедии? Поскольку между собой могут бытьсвязаны самые разные статьи1,а наличие связи определяется общностью контекста статей, постолькууказать жёстко какой-то один тип отношений, связывающий статьи, былобы не верно. Следующим шагом в развитии Википедии, как технологиисемантической паутины2,является: (i) указаниетипассылок междустатьями, (ii) указаниетипаданных внутристатей. Результаты разработки такого семантического расширения,встраиваемое в ВП (Semantic Wikipedia), представлены в работе[183]и доступны в интернет3.

Замечания о категориях и ссылках Википедии

Названия страниц в формате вики состоят из двух частей: пространствоимён (необязательная часть) и собственно название. Например, статья«Шифр» имеет страницу обсуждения с заголовком[[Обсуждение:Шифр]]1,в которой пространству имён соответствует «Обсуждение:».

Страница – это любой документ энциклопедии, которыйимеет заголовок. И статьи, и категории являются страницами.

Статьи – это страницы в пустом пространстве имён.Это основные страницы энциклопедии. Например, статья Шифр имеетзаголовок [[Шифр]]

Категории – это страницы в пространстве имён«Категория:». Они служатдля группирования сходных по тематике страниц.

Присвоить странице категорию можно, добавив странице тег категории соссылкой на страницу категорию. Например, редактируемый текст статьи[[Рукопись Войнича]]2содержит:

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

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

Сообщество Википедиирекомендует придерживаться следующих правил3:

В работе [135] отмечают, что одним из основных источников информациив программных проектах, связанных с Википедией, являются категории.Но даже этот источник данных не является однозначно определённым,поскольку категории могут представлять не только родовидовыеотношения (гиперонимия, is-a), но также отношения часть-целое(меронимия), наличие свойств (has-property) [173].

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

Группировать статьи вэнциклопедии можно с помощью категорий, списков, и навигационныешаблоны (article series box, navigational templates).последовательности. У каждого способа есть свои достоинства инедостатки3.

Общий недостаток категорий и списков вики – это дублированиеинформации, то есть параллельное существование списков (например,List of astronomers) и категорий (Astronomers). К сожалению,дублирование информации не полное: не все статьи из списка могут бытьпомечены соответствующей категорией (например, не у всех страницастрономов со страницыhttp://en.wikipedia.org/wiki/List_of_astronomersуказана категорияAstronomers).



1Определение,функции и примеры тезаурусов см. на стр. 45.

2«Вотличие от понятия тезауруса глоссарий – этопонятийно-терминологические определения слов, используемых втезаурусе конкретной предметной области» [2].

3«Релевантность(relevance, relevancy) – соответствие документа запросу»[52].

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

5Другаязадача, получившая названиеsemantic associations,заключается в поиске и ранжировании сложных отношений в данных RDF.Две сущности в RDF графесемантически связаны (semanticassociations), если существует связывающий их путь (или несколькопутей). В работе [71] представлен поиск в семантической сети [17]интересных пользователю отношений между двумя сущностями иранжирование отношений, основанное на статистических исемантических (например, учёт типа ссылок) критериях. См. прототипсистемы:http://lsdis.cs.uga.edu/projects/semdis/index.php?page=3

2См.определения авторитетных и хаб-страниц в главе 1 в подразделе «Алгоритм HITS»на стр. 27, см. также подраздел «Поиск синонимов с помощью HITS алгоритма»на стр. 74. Заметим, что слов хаб встречается в отечественнойнаучной литературе, например, «термин-хаб»в работе [11].

3«Семантическимипринято считать системы, в которых в процессе анализа содержаниятекста делаются попытки учесть не только лингвосемантические, но илогико-семантические отношения между языковыми объектами. Крометого, контекст, определяющий лингвосемантические отношения и вобычных системах синтаксического анализа не выходящий за пределыпредложения, в семантических системах распространяется на уровнидискурса и текста. Наконец, предполагается, что системасемантического анализа должна учитывать как сведения о даннойпредметной области, так и её связи с внешним миром в целом» [30].

1Этопозволяет не решать отдельную сложную задачу классификации –соотнесения документа заданным категориям. См., например, работу [137],в которой описано автоматическое отображение веб-страниц вYahoo!онтологию с помощью классификатора Байеса, или статью [106] опоиске похожих документов в библиографическом корпусе на основеалгоритмапоиска ближайшего соседа (k-NN). Забегая вперёд,укажем, что задача классификации в вики-текстах решена за счётналичия категорий, указанных авторами текстов.

2Осложности выбора амортизирующего коэффициента можно судить по работе[73].

1«Вначале 50-х годов XX века группа американских исследователей подруководством Ч. Осгуда опубликовала сенсационную книгу «Измерениезначения». Для языковедов само сочетание этих слов былобессмыслицей: каждому ясно, чтозначение слова, его смыслневозможно как-то там измерить(курсив наш – А.К.). Но Ч. Осгуд действительно открыл дляязыкознания нечто новое. Он доказал, что в области семантикивозможны измерения <...> Ч. Осгуд впервые выделил и измерилкачественно-признаковый аспект значения слова» [48].

2Лемматизация– приведение слова к неопределённой (словарной) форме,например, для глаголов – это получение инфинитива (бежал–бежать), для существительных – это 1-ое лицо,ед.ч. (яблоки –яблоко).В работе [67] используется терминлексикографический контроль.«Он заключается в приведении используемых ключевых слов кединой морфологической форме и к единому написанию, в учётесинонимии и многозначности ключевых слов» ([67], стр. 75).

1«Кластер-анализ– это способ группировки многомерных объектов, основанный напредставлении результатов отдельных наблюдений точками подходящегогеометрического пространства с последующим выделением групп как“сгустков” этих точек.» [43]. Кластер в англ. это«сгусток», «гроздь (винограда)», «скопление(звёзд)» и т.п. Неформально, кластер – это связныйподграф с большим числом внутренних и небольшим числом внешних рёбер[165].

2Вработе [79] указан вариант объединения двух задач: (1) уточнениепоискового запроса и (2) определение сходства запросов междусобой. Подход заключается в том, чтобы на основе сходстварезультатов (множеств найденных документов) находить похожиезапросы. Тогда поисковая система сможет предложить пользователюальтернативные формулировки запроса.

3Вработе [116] представлена схема извлечения концептов и отношений изтекста с помощью эксперта (система T-Rex – The TrainableRelation Extraction framework).

4Достоинствотезаурусов, построенных с помощью Википедии, как отмечают в работе [135]– это стоимость, постоянное расширение, то есть адекватностьсовременному лексикону, многоязычность (то есть привязка к концептуслов на разных языках).

1Задачаопределения значения многозначных слов (Word sense disambiguationили WSD) состоит в приписывании каждому экземпляру слова одного изизвестных (например из словаря) значений. Эта задача отличается отзадачи вывода значения слова (sense induction).

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

3Вработе [123] предложен метод построения таксономии по наборудокументов (система TaxaMiner).

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

2Числостатей Английской Википедии превысило размер энциклопедииБританника.

1Болееподробно о фильтрации статей при поиске и чёрном списке категорийсм. на стр. 86.

1Программас открытым исходным кодом, доступна по адресуhttp://synarcher.sourceforge.net

2Программас открытым исходным кодом, доступна по адресуhttp://rupostagger.sourceforge.net

1См.«Требования к корпусу проблемно-ориентированных текстов»на стр. 24.

1Списоктребований, на основе которых был выбран алгоритм HITS, приведёнвыше.

2Понятиепохожесть документов основано на концепциях авторитетных ихаб-страниц [125]. В общих чертах, два документа будут считатьсяпохожими, если существует достаточное число документов, которыессылаются на эти два документа в одном контексте. Более подробноеопределение авторитетных и хаб-страниц см. в гл.1 в подразделе «Алгоритм HITS»,стр. 27. Было формализовано понятие «похожие вершины»графа, см. стр. 76, формул

1Обратимвнимание на более жёсткую позицию в работе [51], где утверждается,что «... только слова имеют значения. Текст же имеет смысл, ане значение.»

1Неменее интересная типизация присуща и антонимам, в работе [65] (стр.9) (вслед за Л.А. Новиковым) выделяют классы: контрарные,комплементарные и векторные антонимы (семантическая классификацияантонимии). Там же определены точные / неточные,производные и отражённые антонимы.

2«Фразеологизм– это воспроизводимый в речи оборот, построенный по образцусочинительных и подчинительных словосочетаний, обладающий целостным(реже – частично целостным) значением и сочетающийся сословами свободного употребления.» [27]. Примерыфразеологических синонимов:как свои пять пальцев (разг.);вдоль и поперёк (разг.);до последней запятой(разг.),до <последней> точки (разг.),до тонкости(разг.),до точности(прост.).

1Примерантонимов:доверие правительству – вотум недоверияправительству, правовое обеспечение – правовой вакуум.

2Примерродовидовых синонимов:здравоохранение – укреплениездоровья, каракулево-смушковое сырьё – каракуль –каракульча – смушка.

3Например,спортсмен – спортсменка, владелец – владелица.

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

5Например,встреча на высшем уровне – встреча в верхах.

6Примердополнительной модальности:артиллерийский обстрел –артиллерийская канонада – артиллерийская подготовка –артиллерийский удар.

7Например,безопасность судоходства – безопасность кораблей –безопасность на море.

1Обэтой и других проблемах Википедии см. в подразделе «Корпус текстов вики-ресурса Википедия».

1См.http://wikipedia.org

2ФЦП«Электронная Россия». Информационное сопровождениеПрограммы. Организация коммуникации по вопросам административногообеспечения государства и использования ИКТ в практикеадминистрирования.http://projects.economy.gov.ru/pms/DownloadFile.aspx/tt_eg2006v3_nov05.doc?workproductid=70a5c8fa-5e73-463f-9233-15db250b80ba.

3Департаментобразования г. Москвы: Методические рекомендации для школ,подключаемых к сети Интернет.http://web.archive.org/web/20070828105815/http://www.educom.ru/ru/projects/link-up/package/.

4См.http://ru.wikipedia.org/wiki/Википедия:Пресс-релиз/В_десятке!.

5Всоответствии с классификацией, предложенной в работе [15].«Гипертекстовые ИПС – характеризуются наличием не толькосодержания, но и некоторой унифицированной структуры сведений одокументах. Такие сведения являются метаданными относительноисходных документов» [15].

1Практическаяреализация может объединять возможности разных подходов.

2См.также обзор и классификацию методов и приложений вычисления сходствакоротких текстов в [147].

3Дляопределения силы связи между словами по совместной встречаемости вдокументах либо в общем контексте — могут использоватьсяспециальные алгоритмы [40].

4Насегодняшний момент, автору не встретились работы, посвящённые поискусемантически близких слов с помощью систем автоматического пониманиятекстов (АПТ). О системах АПТ см. в [41].

5Вработе [129] предложена мера вычисления семантического сходстваинтернет страниц на основе учёта и ссылок, и текста. Сходство текставычисляется с помощью TF (формула косинусного коэффициента).Сходство ссылок вычисляется с помощью формулы «частота ссылок– обратная частота документов» (то есть в формуле TF-IDFдокументы оставили, а слова заменили на ссылки).

6Возможностьпоиска похожих документов реализована в современных поисковыхсистемах [52], например, Яндекс («похожи на страницу»),Google («Find pages similar to the page»).Достоинство такого вида поиска для пользователя – нужно нажатьодну кнопку, для системы – документ содержит большеинформации, чем запрос пользователя.

2Детальныйанализ алгоритма, постановка задачи, дополнительные замечания, атакже поиск синонимов с помощью HITS алгоритма представлены в гл. 2,стр. 69.

3Ещёодно название HITS алгоритма – «Сonnectivity analysisalgorithm for hyperlinked environment» – предложено вработе [81].

4Оригинальноерасширение HITS алгоритма предложено в работе [136]. Авторыпостроили и проанализировали граф Темы-Системы для поиска наиболееуспешных тем, выявляющих слабые и сильные поисковые системы, наоснове данных TREC. Поскольку результаты работы поисковиков могутбыть неудачными, постольку веса могут быть отрицательными, поэтомуавторы вводят понятиенеавторитетности (unauthority) ивыделяют тип вершин, ссылающихся на неавторитетные вершины(unhubness). Тогда «хаб-документ – это документ,содержащий много ссылок на неавторитетные вершины, причём ссылкиимеют большой отрицательный вес» [136].

1Овыборе амортизирующего коэффициента в алгоритме PageRank см. вработе [73].

2Вработе [89] авторы используют в Байесовой сети доверия веса,рассчитанные с помощью HITS, для поиска релевантных документов. Спомощью HITS посчитали четыре веса для каждого документа:hubиauthority, локальные (по запросу), глобальные (по всемдокументам).

1Подмножествоопределяется благодарю наличию категорий у страниц. Например статьяв русской Википедии: «Куинджи, Архип Иванович» содержиттакие категории, как: «Художники России», «Передвижники»и др., см.http://ru.wikipedia.org/wiki/Куинджи,_Архип_Иванович

2Вработе [145] указан недостаток LocalPageRank, присущий и HITS: всильно связанном графе (например ВП), соседние вершины (для данной)– это значительная часть всего графа.

3Нетвходящих дуг, то есть слова не упоминаются ни в одной словарнойстатье.

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

1«Редирект»– это страница-перенаправление; «разрешитьредирект» означает подменить ссылки xyzна xz, спрямляяпуть до целевой статьи.

2«Дизамбиги»– статьи Википедии, содержащие перечисление значений.Создаются для многозначных терминов, см., например, статью «Лемма».

3Тестовыйнабор подробно описан на стр. 127. Сравнение результатов работыалгоритма WLVM с другими см. в табл. 4.6 на стр. 130.

1ПрограммаWikipedia Miner Toolkit, см.http://sourceforge.net/projects/wikipedia-miner.

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

3Примеромиспользования лексической компоненты в задачах scheme / ontologyalignment может быть задача сравнения графов (graph matching),задача сравнение строк (например, сравнение имён) и др. [164].

4Примерсемантической компоненты – использование формальной онтологииверхнего уровня SUMO, DOLCE (там же, стр. 9).

5Семантическийграф – это граф, который содержит вершины разных типов иотношения между ними, также разных типов [77]. Семантическая сеть(semantic network) – это направленный граф с вершинами,соответствующими концептам, и рёбрам, представляющим семантическиеотношения между концептами (см.http://en.wikipedia.org/wiki/Semantic_network).

1Втаком графе концептам соответствуют вершины, отношениям –дуги.

2См.http://en.wikipedia.org/wiki/Expectation-maximization_algorithm.

1Обобщение,поскольку Блондел вводит понятиеструктурный граф и получает,что в алгоритме Клейнберга

2Вокабула– заголовок словарной статьи (лексикографическийтермин).

1ESA– это аббревиатура от «Explicit Semantic Analysis»(явный семантический анализ). Название выбрано в противовес«скрытому семантическому анализу» (LSA), поскольку в ESAконцепт – это название статьи. То есть концепты явные,формулируются человеком, легко объяснить их значение.

2Причёмсвязь слова и концепта не указывается, если концепты получилинебольшой вес для данного слова. Для вычисления взвешенного вектораиспользуется параметрk – запись в инвертированноминдексе, указывающая на степень связи слова и концепта. Из статьи [103]не ясно, как вычисляется эта степень связи слова и концепта,возможно, как (1) относительное число повторов слова в статье,(2) позиция в тексте (чем ближе к началу статьи, тем большевес).

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

1NGDрасшифровывается какnormalized Google distance,http://en.wikipedia.org/wiki/Semantic_relatedness

2Формулавычисления сходства слов с помощью коэффициента Джаккарда (см.предыдущую таблицу) предложена в работе [173], гдеHits(x) –определяется как число страниц, которые возвращает Google для словаx.

3Ванглоязычной литературе такие метрики называют:path basedmeasures,edge counting methods [173].

1Даннаяметрика получила развитие в работе [146], см. метод извлеченияконтекстно связанных слов, стр. 35.

1Заметим,что в ВП у слова обычно несколько категорий, то есть может бытьнесколько ближайших общих категорий.

2Вэкспериментах Резник оценивал сходство существительных, учитывалотношение WordNetIS-A (гипонимия).

3Возможно,это одна из причин, почему мераres hypoпоказала в экспериментах [173] относительно слабый результат.

4ГипонимыкатегорииK в Википедии – это все подкатегорииК,а также все статьи, принадлежащие этим подкатегориям и категории К.

1ЗаконЦипфа утверждает, что чем длиннее фраза, тем реже она встречается вкорпусе. На основании этого, было предложено наличие общих фраздлиной вn слов (в глоссах сравниваемых слов) оценивать какn2 [75].

2Любаяфункция оценкистепени различия между документамиDможет быть преобразована в функцию, определяющуюстепеньсоответствияS следующим образом:.

1Видысетей, их топологические свойства и приложения см. в обзорныхработах [70], [96], [142].

2Вработе [77] эта метрика называетсякоэффициент кластеризациивершины и вычисляется по формуле,гдеki – степень вершиныi,Ei– число ссылок междуki соседями.УсреднениеC(i)по всем вершинам даёт коэффициенткластеризации графа.

1Насегодняшний день существует огромное количество программных системдля поиска и обработки текста, см. например, каталог программ DataMining (http://www.togaware.com/datamining/catalogue.htmlиhttp://www.togaware.com/datamining/gdatamine/index.html

2Этоограниченная форма лицензии GNU, позволяющая, в случаенеобходимости, встраивать GATE в коммерческие продукты

1Впроекте ALVIS предложен иной формат лингвистической аннотации(платформа Ogmios) для индексирования документов определённойтематики [109], [141]. Лингвистическая аннотация, добавляемая ктекстовым единицам (словам, фразам, и т.д.) включает морфологическиеи синтаксическая теги, синтаксические отношения и семантическиеотношения (анафорические и специфичные для данной проблемнойобласти).

2Эти,а также ещё десяток других мер для оценки работы ранжирующих методикпредставлены в работе [156].

1Каждаясловоформа представляется множеством морфологических омонимов [47].

1ПрограммаLemmatizer (http://www.aot.ru)распространяется на условиях LGPL лицензии.

2«Парадигматическиеотношения обусловлены наличием логических связей междупредметами и явлениями, обозначаемыми словами. Такие отношения носятвнеязыковой характер и не зависят от ситуации, для описания которойиспользуются слова» [66]. Примерами парадигматическихотношений являются отношения синонимии, антонимии.

3См.http://wordnet.princeton.edu

1Сточки зрения теории графов системе WordNet соответствуетнаправленный граф, вершины которого представлены концептами (наборысинонимов, синсеты), дуги представлены семантическими отношениями.

2См.описание меры Leacock-Chodorow и других в табл. 1.2, стр. 37.

1Сдругой стороны глоссы WordNet критикуют за отсутствие единого стиляв их написании, считают также, что некоторые из них не оченьинформативны [158].

2Всвою очередь WSD (word sense disambiguation) методики успешноприменяются в машинном переводе, основанном на статистическомподходе [88].

3Вработе [138] категориям (в классификации новостных тем) ищетсясоответствующий синсет WordNet. При этом категория может состоять изнескольких слов, то есть нет точно соответствующего слова в WordNet.Проблема была решена поиском подстроки среди слов WordNet (функция«Find Keywords by Substring»). Эту идею (поискподстроки) можно применить при интеграции данных ВП и WordNet припоиске соответствия между словом из WordNet и названием статьи ВП,состоящей из нескольких слов.

4Вработе [154] под «родовым термином» (англ. genusterm) подразумевается гипероним. Отношение гипонимии важно, так какявляется «основой таксономии и главным механизмомнаследования, помогая в установлении других семантических отношенийи свойств, обеспечивая строгую структуру, не обременённуюмногословием» [154]. Заметим также, что «в словарномопределении заголовок статьи и “родовой термин” должныпринадлежать одной части речи» [154].

1Такоеавтоматическое установление соответствия является подзадачейавтоматического построения онтологий, как верно замечают авторы [158].

2Непутать с Википедией на английском упрощённом языке (SimpleWikipedia).

3Этимобъясняется небольшое количество статей в упрощённой Википедии (1841статья на 15.11.2004)

1Y=ВЫШЕ(X),если можно утверждать, что X – это вид Y, например«государственная собственность» = ВЫШЕ(«государственноепредприятие») [41]. Связь ВЫШЕ-НИЖЕ соответствуют отношениюгипонимии в Викисловаре: X – это гипоним, Y – этогипероним.

2СвязиЦЕЛОЕ-ЧАСТЬ соответствуют меронимы и холонимы в Викисловаре.

3АббревиатураGEMET (швед.gem – скрепка, игра) расшифровывается какGEneral Multilingual Environmental Thesaurus, см.http://www.eionet.europa.eu/gemet/about?langcode=enиhttp://en.wikipedia.org/wiki/GEMET

4EnglishWiktionary, см.http://en.wiktionary.org.

5См.http://ru.wiktionary.org,http://ru.wikipedia.org/wiki/Викисловарь.

1См.http://ru.wiktionary.org/wiki/самолёт.

2См.http://ru.wiktionary.org/wiki/сжимать.

3См.http://ru.wiktionary.org/wiki/канифоль.

4См.http://ru.wiktionary.org/wiki/бор.

5См.http://en.wikipedia.org/wiki/Wiki

6См.http://wiki.org/wiki.cgi?WhatIsWiki

7См.http://en.wikipedia.org/wiki/Wiki

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

2Надёжностьстатьи в Википедии можно оценить визуально с помощью специальнойпрограммы численной оценки степени доверия к тексту [69].

3Появилсяновый формат электронных документов – вики, см. стр. 51.Особенности корпуса вики-текстов, позволяющие говорить окачественном изменении по сравнению с html страницами, перечисленына стр. 24.

4См.http://s23.org/wikistats/largest_html.php?th=10000&lines=500,данные от 17.08.2007.

5Этоконкретный вики-ресурс, используемый в работе. См.http://en.wikipedia.org

6См.список википедийhttp://meta.wikimedia.org/wiki/List_of_Wikipedias,данные от 17.08.2007.

1Болееподробно об авторском праве, интеллектуальной собственности ипатентах, лицензировании в целом и лицензии GPL в частности см. в [62].

2Наличиеинтереса к вики ресурсам и Википедии в научной общественностихарактеризуется появлением значительного количества публикаций поданной тематике, см.Wiki Research Bibliography(1) http://meta.wikimedia.org/wiki/Wiki_Research_Bibliography,(2)http://bibliography.wikimedia.de,а такжеWikipedia in academic studieshttp://en.wikipedia.org/wiki/Wikipedia:Wikipedia_in_academic_studies.

3См.http://www.mediawiki.org.

4«Википедиясодержит огромное количество тщательно организованных человеческийзнаний» [103].

5Русскаяверсия Википедии содержит 171 тыс. статей по данным на 11 мая 2007г. (http://ru.wikipedia.org/wiki/Служебная:Statistics).На 23 октября 2006 г. тексты содержали 22,5 млн слов и 650 тыс.лексем (http://ru.wikipedia.org/wiki/ВП:ЧС).

6АнглийскаяВикипедии содержит 1,8 млн статей (11 мая 2007 г). В мае 2005Английская Википедия включала 512 млн. слов [157]. См.http://en.wikipedia.org/wikistats/EN/TablesDatabaseWords.htm,а такжеhttp://en.wikipedia.org/wiki/Wikipedia:Statistics

1Базуданных Википедии можно скачать по адресуhttp://download.wikimedia.org,одно из описаний по установке Википедии см. на сайтеhttp://synarcher.sourceforge.net

2Сетевойанализ (часть теории графов) – это количественная оценкасвязности и расстояний в графах.

3Болеепоздние работы отечественных исследователей показывают, чтоВикипедия содержит изолированные статьи, не связанные с другимистатьями внутренними ссылками. См.http://ru.wikipedia.org/wiki/Википедия:Проект:Связность.

1Подстатистическими свойствами вершин имеются в виду: средняя степень(числа входящих ссылок), максимальная степень, стандартноеотклонение, параметр разнородности, максимальное сходство [162].

2См.выдержки из диссертации немецкого учёного: Daniel Kinzler. “Outlineof a method for building a multilingual thesaurus from Wikipedia”,2008.http://brightbyte.de/page/WikiWord/Excerpt

3См.http://www.opencyc.org.

4См.http://www.cyc.com/cycdoc/ref/dict-assist.html.

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

1MSRрасшифровывается как мера семантической близости, см. сайт MSRhttp://cwl-projects.cogsci.rpi.edu/msr

2CGI(Common Gateway Interface) интерфейс обеспечивает связь внешнейпрограммы с веб-сервером.

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

4См.http://www.visualthesaurus.com

5См.http://www.ug.it.usyd.edu.au/~smer3502/assignment3/form.html

6См.http://vslovar.org.ru

1«Similaritymeasure» в [185] – это и есть «figure of merit»(число совместных совпадений слов в списках).

1См.http://ru.wikipedia.org/wiki/AJAX

2См.http://www.cs.umd.edu/hcil/piccolo/index.shtml

3Визуальныйпоисковик, использует Flash технологию.http://kartoo.com

4См.http://newzingo.com

1См.замечание с описанием folksonomy на стр.183.

2Сайт«Перекрестный каталог» предлагает несколько осей (схем)категоризации, выбирая значения которых, пользователь сужаетпространство поиска. См.http://4kg.ru

3Авторысистем, использующих закладки, предлагают различные способыорганизации закладок, что сближает подход тегов с подходомкатегоризации страниц. Например, на del.icio.us предлагаетсямеханизм «bundle tags» для организации иерархиизакладок.

4См.http://www.marumushi.com/apps/flickrgraph

5См.http://en.wikipedia.org/wiki/Force-based_algorithms

1«Многиестатьи Википедии содержат один рисунок (ознакомительный),иллюстрирующий главную мысль статьи. В этом качестве длябиографической статьи используется портрет, для статьи о бытовойтехнике — фотография предмета статьи, для статьи обобщественном движении — его символ или флаг, и так далее.Рекомендуется именно этим изображением и начинать статью. Такоеизображение должно обязательно иметь атрибутthumb»(http://ru.wikipedia.org/wiki/Википедия:Изображения).

2См.http://www.metaportaldermedienpolemik.net/wiki/Blog/2006-04-18/RhNav3D

1ПрограммаPathway с открытым исходным кодом написана на языке Cocoa длякомпьютеров Макинтош. См.http://pathway.screenager.be

2См.http://www.chrisharrison.net/projects/wikiviz/index.html

3См.видеофильмы и рисунки на странице проектаhttp://www.chrisharrison.net/projects/clusterball

1См.http://www.mvblogs.org/visuals/visual_08.php

2См.http://www.visualcomplexity.com/vc/project_details.cfm?id=142&index=142&domain=

3См.http://www.visualcomplexity.com/vc/project_details.cfm?id=55&index=55&domain=

1Изкорпуса выбирается документ, заголовок которого совпадает с исходнымсловом, заданным пользователем. Таким образом, в данной схемеприняты следующие допущения: (1) разные документы в корпусеимеют разные заголовки, (2) заголовки состоят из одного слова.Заметим, что можно расширить эти ограничения, если (1) вместозаголовков выполнять поиск по ключевым слова документов,(2) выполнять поиск подстроки в заголовке (тогда заголовокможет состоять из нескольких слов). Заметим также, если слово заданоне в неопределённой форме, то его можно привести к ней с помощьюмодуля морфологической обработки русского языка Lemmatizer,описанного на стр. 106. Прочие ограничения для заголовков словарныхстатей указаны на стр. 74.

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

1См.Требования к корпусу проблемно-ориентированных текстов, гл. 1, стр.24.

2См.«Виды отношений в Википедии» в табл. 1 на стр. 184.

3Cм.определения авторитетных и хаб-страниц далее в главе 1 в подразделе«Алгоритм HITS».

1ИсходныйHITS алгоритм представлен в главе 1 в подразделе «Алгоритм HITS»(стр. 27). Отметим работу [125], в которой предлагается искатьпохожие Интернет страницы на основе структуры ссылок.

2Предлагаемыйадаптированный HITS алгоритм применим только к корпусам текстам,удовлетворяющим ряду требований, см. «Требования к корпусу проблемно-ориентированных текстов»в главе 1 на стр. 24.

3Здесьи далее подстатьёй,страницей,документом,вики-текстом подразумевается текстовый документ корпуса. Разницамежду страницей, статьёй и категорией объясняется в подразделе «Замечания о категориях и ссылках Википедии»на стр. 186.

4Подособенностями корпуса подразумевается (1) наличие категорий(категории классифицируют документы, то есть определяют ихтематическую принадлежность; сами категории в идеале образуютиерархическую структуру) и (2) наличие двух списков страниц длякаждой статьи (кто ссылается на данную статью Г¯(v), на когоссылается данная статья Г+(v)).

1Цит.поhttp://ru.wikipedia.org/wiki/Википедия:Категории.

1См.подраздел 2.3 «Адаптированный HITS алгоритм, включающий алгоритм иерархической кластеризации»на стр. 76.

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

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

3Наэту же проблему указывает Hearst М. [112] (цит. по [81]), аименно: HITS алгоритм не находит часть документов, соответствующуюменее популярной интерпретации запроса. Hearst предлагает возможныерешения: (1) кластеризация документов на подтемы и анализ каждогоподграфа с помощью HITS отдельно; (2) модификация HITS алгоритма,присваивающая рёбрам внутри кластера больший вес по сравнению свесом рёбер между кластерами.

4«IDF(обратная частота термина в документах, обратная документнаячастота) – показатель поисковой ценности слова (егоразличительной силы)» [52]. В 1972 г. Karen Sparck Jonesпредложил эвристику: «терм запроса, встречающийся в большомколичестве документов, обладает слабой различительной силой (широкийтермин), ему должен быть присвоен меньший вес, по сравнению стермином, редко встречающимся в документах коллекции (узкийтермин)». Данная эвристика показала свою пользу на практике ив работе [155] представлено её теоретическое обоснование.

1Поисквыполнялся в словаре «Online Plain Text English Dictionary»(http://msowww.anu.edu.au/~ralph/OPTED),построенный на основе словаря «Project Gutenberg Etext ofWebster’s Unabridged Dictionary»(http://www.gutenberg.net),который, в свою очередь, использует словарь «1913 USWebster’s Unabridged Dictionary»[84].

2Определенияавторитетных и хаб-страниц см. выше в подразделе «Алгоритм HITS».

1См.формулы (2.3)-(2.6) выше.

2Однаиз задач будущих исследований – настроить локальный поисковик(например, Google Desktop или Beagle) на корпус текстов, с которымработают в адаптированном HITS алгоритме. Тогда, можно будетсравнить два способа построения базового набора: (1) построениекорневого набора с помощью поисковика и (2) построение корневогонабора от исходной вершины (текущий вариант).

1Асимптотическийанализ и, в частности, О-оценивание см. в [20], стр. 49-50.

1Укаждой страницы (категории или статьи) Википедии есть уникальныйидентификатор.

1Изчисла статей и категорий в Английской (659 358, 113 483) иНемецкой (305 099, 27 981) Википедиях (на 01.2006 г. по [94])следует, что три слагаемых оценки отличаются друг от друга менее чемв 104.

2Полагаем,что категорияc1 страницы – это первый уровень,надкатегорияc2 категорииc1 – это второйуровень, надкатегорияc3 категорииc2 – этотретий уровень и т.д.

1Такимобразом, получили рекуррентную формулу вычисления меры сходствамежду вершинами одного гра­фа алгоритма SimRank [119] (стр.5,формула (5)). Разница заключается в наличии первого слагаемого вформуле (2.9), определяющего число общих соседей. Очевидно, что обобщих соседях можно говорить в случае поиска похожих вершин дляодного графа, а не в общем случае сравнения вершин разных графов.

1Другойвариант инициализации – начальное значение весов вершин можетбыть вычислено, например, с помощью HITS алгоритма (вес authorityберётся за начальный).

1Валгоритме SimRank [119] предлагается следующая эвристика: отсекатьвершины (pruning), находящиеся на значительном расстоянии от вершиныv, и поэтому, вероятно, имеющей мало общих вершин сотсекаемыми. Таким образом, в SimRank рассматриваются (какпотенциально похожие) вершины, удалённые не более чем на радиусrдруг от друга (где радиус – это один из параметров алгоритма).

1PesericoE., Pretto L. The rank convergence of HITS can be slow. 2008.http://arxiv.org/abs/0807.3006.

1MobyThesaurus List by Grady Ward, см.http://www.dcs.shef.ac.uk/research/ilash/Moby

1Данныйспособ использовался в экспериментах, см. графуIntersectionв таблице 4.8.

2Встатистике коэффициент корреляции Spearman – этонепараметрическая мера корреляции, оценивающая насколько хорошопроизвольная монотонная функция может описать отношение между двумяпеременными в случае, когда неизвестен характер зависимостипеременных (линейный или какой-либо др.). См.http://en.wikipedia.org/wiki/Spearman's_rank_correlation_coefficient

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

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

1Посколькузадачу программы можно сформулировать так: SYNonym seARCH.

2Данныйпакет представляет собой модификацию программыTouchGraph WikiBrowser (см.http://www.touchgraph.com).Можно отметить популярность данной программы, например онаиспользовалась в прототипе американских учёных [71] для визуальногопредставления отношений RDF. Недостаток программы в том, чторазработчики больше не поддерживают данную программу, а также в том,что программа работает не устойчиво при отображении большого числавершин и рёбер (например, если вершин больше сотни).

1Наиюнь 2007 проект kleinberg программы Synarcher содержал 119 тестов,на июнь 2008 – 241 тест.

1Дополнительнаяинформация по Dict серверам и протоколу RFC-2229 на сайтеhttp://www.dict.org

2См.http://www.graphviz.org

1http://www.touchgraph.com

2См.http://ru.wikipedia.org/wiki/Вкладка

1«Кодировкапеременной длины, предназначенная для отображения всех символовстандарта Unicode, при этом совместимая со стандартом ASCII»(http://en.wikipedia.org/wiki/UTF-8)

2http://synarcher.sourceforge.net

1Cм.подраздел «Эвристика: фильтрация на основе категорий статей»во второй главе.

1Впрограмме разные группы вершин выделены разным цветом.

1WikIDF– аббревиатура, отражающая применение подхода TF-IDF [155], [52]к индексированию вики-текстов.

2См.http://en.wikipedia.org/wiki/Wikitext.

1Фантазиипо поводу применения данной архитектуры для (1) тематическойвики-индексации и (2) фильтрации потоков текстов см. вработе [167].

2Обинвертированном файле см. в [52], а такжеhttp://en.wikipedia.org/wiki/Inverted_index.

3Болееподробно о преобразование текста см. на стр. 138.

4Например,ограничение числа связокслово-страница. В экспериментахограничение 1000, см. табл. 4.12.

1Болееподробно о программахLemmatizer иRussian POS Taggerсм.:http://rupostagger.sourceforge.net.

2Точнее— суммарной частоты всех словоформ данной лексемы в заданнойстатье (и во всём корпусе) для каждой леммы. Лемма строится пословоформе с помощью программы Lemmatizer. Определение словоформы,леммы и лексемы см. в Русском Викисловаре.

3Построенныетаким способом индексные БД Русской Википедии и SimpleWikipediaдоступны поадресу:http://rupostagger.sourceforge.net,см., соответственно, пакетыidfruwiki иidfsimplewiki.

1Этафункциональность доступна начиная с версииSynarcher 0.12.5,см.http://synarcher.sourceforge.net

2WikIDF— это консольное приложение на языке Java. Оно зависит отбиблиотек программы Synarcher и поставляется в комплекте споследней.

3См. принципы проектирования индексов поисковых систем:http://en.wikipedia.org/wiki/Index_(search_engine).

4Четвёртаятаблицаrelated_page нужнадля вспомогательной функции — кэширования похожих страниц,найденных с помощью AHITS алгоритма[126].Она использовалась при экспериментальной оценке работы AHITS,поскольку слова в тестовом наборе многократно повторялись[35].

1Дляпроектирования и визуализации таблиц БД использовалась системавизуального проектирования баз данных [17] DBDesigner 4, см.http://www.fabforce.net/dbdesigner4.

2Точнее:возможно меньше число, чем все леммы. Поскольку для слов,встречающихся больше чем в N документах (здесь тысяча), N+1 связка«слово-документ» не будет записана в таблицуterm_page.

3Тоже ограничение, до 1000 документов здесь.

4См.замечание об IDF на стр. 72.

1Цифры26-38% получены как отношение значения поля «Исходный дамп,размер» к «Размер сжатого файла дампа индексной БД»в табл. 4.12 на стр. 144.

1Вкладка– элемент графического интерфейса для переключения междуприложения, в данном случае между разными группами входныхпараметров и результатами. См.http://ru.wikipedia.org/wiki/Вкладка.

1Lemmatizerразработан москвичами (в проекте Диалинг), см.http://www.aot.ru

1Отметим,что для работы адаптированного HITS алгоритма (реализованного впрограмме Synarcher) необходимо, чтобы таблицаpagelinks БДВикипедия была заполнена. Таблицаpagelinks хранит информациюо том, какая страница на какую ссылается. Авторы оболочкиэнциклопедии MediaWiki предлагают несколько способов её заполнения.До 2006 г. эту таблицу вполне успешно заполнял инструмент mwdumper(http://download.wikimedia.org/tools/),написанный на Java. После изменения формата БД Википедии осталосьдва способа заполнения: с помощью php-скриптаrefreshLinks.phpи (более быстрый способ) с помощью программы Xml2sql(http://meta.wikimedia.org/wiki/Xml2sql).

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

1Значениеданного слова см. в энциклопедической статьеhttp://en.wikipedia.org/wiki/Android.Значение прочих слов таблицы можно найти в энциклопедии аналогичнымобразом.

1См.http://en.wikipedia.org/wiki/Automaton

2Словарьсинонимов системы АSIS, ссылка(http://www.lingvoda.ru/dictionaries/)

3Второезначение словажаргон(дорогой камень красно-желтого цвета, циркон, минерал[24])на данный момент (18 июля 2006 г.) в русской Википедии непредставлено

4Толковыйсловарь русского языка (1935-1940 гг.) под редакцией Д.Н.Ушакова.Компьютерное издание, ссылка (http://www.lingvoda.ru/dictionaries/)

1Определениеданного слова даётся в энциклопедической статьеhttp://ru.wikipedia.org/wiki/Арго.Определения прочих слов данной таблицы см. аналогичным образом.

2Викисловарьсодержал (на 19.07.2007) такие семантически близкие слова для словасамолёт (включая синонимы, гипонимы, гиперонимы, меронимы,холонимы):аэроплан, авиация, транспорт, штурмовик, экранолёт,экраноплан, моноплан, биплан, планер, махолёт, мускулолёт,дельтаплан, параплан, турболёт, вертолёт, автожир, винтокрыл,эскадрилья, авиапушка, фюзеляж, крыло, двигатель, винт.Примеры СБС для словосочетания «Беспилотный летательныйаппарат» представлены в табл. 4.1.

1Экспериментпроводился на данных, соответствующих онлайн версии РусскойВикипедии от 20 сентября 2007 г. Данная версия энциклопедии содержитоколо двухсот тыс. энциклопедических статей, 10.4 млн. внутреннихперекрёстных ссылок, 49.8 тыс. категорий, 1.1 млн. ссылок накатегории.

2ДлясловаЖаргон эксперимент не проводился, так как набор слов,найденный программой, слишком мал (11 слов) для того, чтобыприменять какую-либо дополнительную фильтрацию. Для словаАвтопилотточность поиска была низкой (2%) и не менялась при изменении числафильтруемых категорий. Возможно, это объясняется недостаточным (посравнению, например, со статьёйСамолёт) числом ссылок,связывающих статьюАвтопилот с другими. Результаты поиска СБСдля словаАвтопилот учитывались для оценки времени поиска ине учитывались для оценки суммарной точности поиска.

1Выбираетсякатегория, которой принадлежит больше всего найденных слов. Этовозможно узнать с помощью вкладки «Категории С», см.рис. 17 на стр. 106.

1Времяпоиска зависит и от того, какая именно категория выбрана.

1Эксперимент(по оценке работы AHITS алгоритма и адаптированной метрики Резника(res hypo) проводился на данных, соответствующихонлайн версии English Wikipedia от 27 мая 2007 и 2 мая 2006г., атакже Simple Wikipedia от 11 августа 2007 и 9 сенября 2007,подробности см. в [35].

2

3Тестына синонимию: 80 вопросов теста TOEFL, 50 вопросов ESL [177] и 300вопросов Reader's Digest Word Power Game [117].

1Разницапонятий semantic similarity и semantic relatedness описана на стр.185. AHITS алгоритм позволяет находить семантически близкие слова(semantic relatedness).

2ПростаяАнглийская Википедия, см.http://simple.wikipedia.org

3Ещёодна классификация метрик семантической близости представлена вработе [148] (стр. 5).

1АнглийскаяВикипедия, см.http://en.wikipedia.org

20.33-0.36– о получении этих данных см. [35], [36], 0.37 взято из [173].

3Коэффициенткорреляции Спирмена с эталонным набором равен 0.45 приавтоматическом разрешении многозначных статей и 0.72 — приручном. Подробнее об WLVM см. на стр. 30.

4

5

6Подробноеописание экспериментов см. в работе [35], (10 стр.), краткое в [36](4 стр.).

7См.http://ru.wikipedia.org/wiki/Участник:AKA_MBG/Wordsim

1Экспериментпроводился на данных, соответствующих онлайн версии РусскойВикипедии от 18 июля 2006 г.

1Тоесть заголовки статей состоят из одного слова.

2Экспериментпроводился на данных, соответствующих онлайн версии РусскойВикипедии от 18 июля 2006 г.

3Дляэтого была написана подпрограмма с вложенным циклом, в теле циклакоторой вызывался адаптированный HITS алгоритм.

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

2Тоесть неформализованной на данный момент.

1Всевозможные морфологические интерпретации хранятся в таблице Ancodes вLemmatizer. Ключом является поле Ancode («аношкинский код»)[60].

2«Граммема– это элементарный морфологический описатель, относящийсловоформу к какому-то морфологическому классу» [59].Например, словоформерама с леммой РАМ будет приписанследующий набор граммем: «мр,рд,ед».

1Болееподробно эти модули GATE описаны в гл. 3 на стр. 106.

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

1Имеютсяв виду короткие цитаты:{{цитата|текст}},см.http://ru.wikipedia.org/wiki/Википедия:Шаблоны/Форматирование.

1См.код функцииwikipedia.text.WikiParser.convertWikiToText впрограмме Synarcher.

2Посколькутеги <pre> обычно «оборачивают» исходный кодпрограмм, не содержащий текстов на ЕЯ, см.http://en.wikipedia.org/wiki/Wikipedia:How_to_edit_a_page#Character_formatting.

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

4Имеетсяв виду парсер протокола XML-RPC системы RuPOSTagger.

1См.http://ru.wikipedia.org/wiki/Через_тернии_к_звёздам_(фильм).

1См.http://api.futef.com/apidocs.html.

2См.http://json.org/json-ru.html.

3См.http://modis.ispras.ru/sedna/иhttp://wikixmldb.dyndns.org/help/use-cases/.

11000наиболее частотных слов, полученных по текстам Википедии наупрощённом английском языке, см.http://simple.wiktionary.org/wiki/User:AKA_MBG/English_Simple_Wikipedia_20080214_freq_wordlist.(14.02.2008)

21000наиболее частотных слов, полученных по текстам Русской Википедии (20февраля 2008), см.http://ru.wiktionary.org/wiki/Конкорданс:Русскоязычная_Википедия/20080220.

1Размерфайла «...-pages-articles.xml.bz2», содержащего текстыстатей.

2Числосвязок «слово-статья» в корпусе, учёт не более 1000 дляодного слова. Число1000 здесь — это один из входныхпараметров программного комплекса построения индексной БД, см.«TF-IDF contraints» на рис. 1.

3Следуетпризнать, что к данному вопросу авторов привлёк рисунок сраспределением частот слов в Английской Википедии за 2006 г., см.http://en.wikipedia.org/wiki/Zipf%27s_law#Related_laws.

10.20— разница между степенью наклона аппроксимирующих прямых поста (0.974) и тысяче (1.174) слов.

1Можнопостроить аналогичный график, если отсортировать слова не по частотеслов в корпусе, а по числу документов, содержащих слова. В этомслучае взаимно поменяется характер кривых «07 corpus» и«ruwiki 07 doc».

1Поклассификации, предложенной в работе [118], приложение,разработаннное в данном проекте, относится к классу «ontology-basedsearch». Определение онтологии см. в [107], [181]. Введение иобзор онтологий также представлены в отечественной монографии [61].

1Приложениеи код программы доступны по адресу:http://whinger.narod.ru/soft/edoc.jung/index.html.

2См.http://java.sun.com/products/javawebstart,http://mindprod.com/jgloss/javawebstart.html.

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

1Методикапостроения индексной базы. 23.10.2006.http://ru.wikipedia.org/wiki/Википедия:Частотный_словник

1Визуальныйинтерфейс GATE позволяет: (1) связывать модули друг с другом, (2)задавать параметры, (3) представлять результаты работы модулей.

1Полныйсписок, тоестьбезфильтрации экспертом

2Использоваласьпрограмма Synarcher версии 0.12.1

1«Folksonomy– это создаваемая совместными усилиями, открытая длярасширения система меток, позволяющая пользователям Интернеткатегоризовать информационные ресурсы, такие как Интернет страницы,онлайн фотографии, интернет ссылки. Использование меток (другоеназвание – теги, аналог ключевых слов), свободно выбираемыхпользователем, позволяет улучшить работу поисковых систем, посколькудля категоризации применяется знакомый, понятный, используемыйпользователем лексикон»(http://en.wikipedia.org/wiki/Folksonomy).Подход folksonomy преследует цели: создание личной коллекции[ссылок] и общественной коллекции [108] (цит. по[184]).В работе [160] представлена формальная модель folksonomy, как наборатроек (пользователь, тег, ресурс) или трёхдольного графа.Особенность Википедии в том, что некоторая категория присваиваетсястатье раз и навсегда для всех пользователей[184].Примерами folksonomy систем могут служит del.icio.us (открытоехранилище закладок), в которой пользователи придумывают иприсваивают теги интернет страницам, и flickr – гдепользователи-фотографы присваивают теги фотографиям [127]. Такимобразом, теги нужны для того, чтобы пользователи могли быстроповторно найти некоторую информацию, помеченную тегами.

1ПравилаВикипедии рекомендуют, чтобы у категорий не было аннотаций, то естьназвания категорий должны быть ясными и не требующими пояснений.Возразим, что в редких случаях (особенно, когда нет основной статьи,описывающей понятия категории) аннотации нужны, например, когдакатегории имеют научное название, см. например,http://ru.wiktionary.org/wiki/Категория:Эпистемические_глаголы

2Врусской Википедии есть такие примеры эквивалентности, как:перенаправление со статьи «Броузер» на статью«Браузер», «Астронавт» –«Космонавт», «Космодром Байконур» –«Байконур», «Космос (астрономия)» –«Вселенная», «Linux» – «GNU/Linux».

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

1Вработе [135] указывают на проблему гиперссылок, на то, что часто вэнциклопедической статье указаны ссылки на статьи, которыенезначительно, слабо связаны с исходной статьёй. Это проблема дляпоисковых систем, которые выполняют поиск на основе анализагиперссылок. Учёные из Новой Зеландии [135] предлагают рассматриватьтолько взаимные ссылки. Я бы предложил следующее: рассматривать и невзаимные, но взаимным давать приоритет. Какой приоритет? Это ужебудет зависеть от алгоритма. Например в HITS – включать вкорневой набор только вершины, взаимносвязанные с исходной вершиной,в базовый – включать вершины с не только взаимными ссылками.

2«SemanticWeb – это расширения Веб, позволяющие выполнять автоматическую(и ручную) обработку данных вычислительным системам (и человеку).Расширения обеспечат: (i) представление данных вмашинно-читаемой форме, описывающих содержание веб-страниц,(ii) возможность пользователям указывать отношения (например,семантические) между различными типами данных».http://www.w3.org/2001/sw/SW-FAQ

3См.программу (http://ontoworld.org)и описание (http://ru.wikipedia.org/wiki/Семантическая_вики).

1Двойныескобки в формате вики являются аналогом гиперссылки в Веб.

2См.http://ru.wikipedia.org/wiki/Рукопись_Войнича

3См.http://ru.wikipedia.org/wiki/Википедия:Категории

1См.http://en.wikipedia.org/wiki/Wikipedia:Categorization

2См.http://ru.wikipedia.org/wiki/Википедия:Правила_отнесения_в_категории

3См.http://en.wikipedia.org/wiki/Wikipedia:Categories,_lists,_and_series_boxes

4См.http://en.wikipedia.org/wiki/Wikipedia_talk:Categorization/Archive_1#Lists_v._categories

5См.http://meta.wikimedia.org/wiki/Category_talk:Demo

6См.замечание о folksonomy на стр. 183.

1См.Блогосфера российского интернета. Информационный бюллетень Яндекс.Осень 2006 года.http://company.yandex.ru/articles/yandex_on_blogosphere_autumn_2006.pdf

2Подсилой кластера понимается число тегов, часто употребляемых разнымипользователями. Таким образом, авторы работы [111] выделяют сильныеи слабые кластеры.

[8]ページ先頭
©2009-2025 Movatter.jp