ИНТЕГРАЦИЯ ЛИНГВИСТИЧЕСКИХ И СТАТИСТИЧЕСКИХ МЕТОДОВ ПОИСКА В ПОИСКОВОЙ МАШИНЕ «EXACTUS»

Состояние дел в области поисковых алгоритмов
Статистические алгоритмы поиска (с учетом морфологии).
Лингвистические алгоритмы поиска (без учета статистики).
Цель разработчиков Exactus:
объединение статистических и лингвистических методов поиска.

Особенности алгоритма поиска Exactus (1)
Учет статистических характеристик текста:
TF*IDF веса термов (с некоторой модификацией).
Значимость фрагментов текстов (заголовки, разметка, удаленность от начала документа и т.д.).

Особенности алгоритма поиска Exactus (2)
Учет лингвистических характеристик текста:
Значения синтаксем (Золотова Г.А.).
Семантические связи (Осипов Г.С.).

Особенности алгоритма поиска Exactus (3)

Что у других?

Что у других? (2)

Как Exactus нашел ответ

Как Exactus нашел ответ(2)
На этапе индексации производится преобразование документов к внутреннему формату Exactus, обсчет TF*IDF весов.
Производится синтаксический и семантический анализ текстов (выявление синтаксем и их значений).
Полученные в результате анализа данные укладываются в линейные упорядоченные списки вхождений слов в документы с весами и значениями
Поиск представляет собой слияние линейных упорядоченных списков.

Особенности архитектуры Exactus
Модули расположены на узлах кластерной установки.
Управление задачами осуществляется посредством PVM-машины (Parallel Virtual Machine).
Модули разделены на два типа: основные (лингвистические процессоры, индексаторы и т.д.) и вспомогательные (агрегаторы, синхронизаторы и т.д.).
Система является кросс-платформенной, код написан на С и C++.
Экспериментальная установка состоит из 8-и узлов кластера пиковой производительностью 100 Gigaflops.
В качестве вычислительных узлов используются обычные персональные компьютеры, объединенные в стойку.
Для взаимодействия узлов используется Gigabit Ethernet.

Exactus – вид сбоку

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

Экспериментальная проверка алгоритма Exactus (2)
Для выставления оценки результата используются два способа:
Строгая оценка AND – документ получает оценку релевантен или нерелевантен, если все оценщики выставили соответствующую оценку.
Нестрогая оценка OR - результат получает оценку релевантен, если хотя бы один оценщик выставил соответствующую оценку.

График TREC

Краткий анализ результатов участия в РОМИП-2007 (1)
Exactus принимал участие в поиске по коллекции белорусского Интернета.
Наилучшие результаты достигнуты системой в AND-оценке по точности.
Хорошие оценки достигнуты по другим показателям.
Отсутствие Page Rank в алгоритме Exactus не привело к отставанию от других систем в точности и полноте поиска.

Краткий анализ результатов участия в РОМИП-2007 (2)
Полученные на РОМИП результаты показывают перспективность симбиоза лингвистических и статистических алгоритмов поиска и возможность их применения в реальных условиях.
Скорость поиска Exactus сравнима с современными поисковыми машинами на больших объемах данных (не более 2х секунд на любой запрос по коллекции РОМИП).
Индексация и лингвистический анализ, по-прежнему, остаются узким местом Exactus. Единственный путь преодоления барьеров скорости анализа - использование современных вычислительных систем и параллельных вычислений.