Г. С. Осипов 1, И. А. Тихомиров 1, И. В. Смирнов 1 Доклад

Вид материала

Доклад

Содержание 1. Поиск и классические метрики точности и полноты поиска 2. Полнота поиска в системе Exactus 3. Точность поиска в Exactus 4. Дополнительные возможности Exactus 5. Принципиальный алгоритм работы Exactus 6. Результаты работ Список литературы

Подобный материал:

• Г. С. Осипов 1, И. А. Тихомиров 2, И. В. Смирнов 3 Доклад, 73.81kb.
• А. Ю. Поляков, И. В. Тихомиров материальное стимулирование персонала и качество сборки, 90.09kb.
• Iii международная научная конференция компаративистские чтения, 114.21kb.
• Ю. А. Тихомиров автор многих фундаментальных исследований в области теории государства, 6630.96kb.
• Смирнов Б. М., Смирнов, 64.61kb.
• Доклад секретного осведомителя, профессора протоиерея А. Осипова [ Осипов Александр, 500.09kb.
• Ю. А. Тихомиров тихомиров Юрий Александрович Первый заместитель директора Института, 1104.37kb.
• Тихомиров О. К. Психология мышления: Учебное посо­бие, 4461.4kb.
• Королев Олег Петрович Заместитель главы администрации Липецкой области Салогубов Сергей, 16.62kb.
• Ф. М. Достоевский и христианство, 165.2kb.

УДК 004.78:025.4.036

EXACTUS - СИСТЕМА ИНТЕЛЛЕКТУАЛЬНОГО МЕТАПОИСКА В СЕТИ ИНТЕРНЕТ^*

Г.С. Осипов¹, И.А. Тихомиров¹, И.В. Смирнов¹


Доклад посвящен методам и инструментальным средствам семантически релевантного метапоиска. Рассматривается применение описываемых методов для поиска в сети Интернет.

Введение

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

Полнота поиска увеличивается, главным образом, за счет непрерывного мониторинга сети Интернет с целью выявления новых ресурсов. Однако поисковые алгоритмы современных поисковых машин устроены таким образом, что полнотой фактически жертвуют в пользу точности поиска (концепция высокой точности поиска на первых n-документах при малых значениях полноты). Кроме того, для сокращения объема индекса и повышения скорости поиска часть документов с наименьшими весами просто отсекается (концепция быстрого индекса) и в результате невозможно получить все документы из индекса поисковой машины даже по однословному запросу. Иной путь - создание метапоисковых систем [Осипов и др., 2004], позволяющих объединять результаты поиска из различных источников.

Настоящая работа посвящена изложению подходов и описанию программных средств поиска информации, в которых проблема полноты решается с привлечением методов метапоиска [Тихомиров, 2003], проблема точности – благодаря использованию семантического анализа запроса и текстов найденных документов [Осипов, 1990; Золотова, 2001; Золотова и др., 2004].

^ 1. Поиск и классические метрики точности и полноты поиска

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

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



где:

a – количество правильно найденных документов;

c – количество правильных документов, которые система не смогла обнаружить.


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




где:

a – количество правильно найденных документов;

b – количество неверно найденных документов.


На практике оказывается, что нетрудно построить систему, обладающую высокой точностью поиска при низкой полноте или высокой полнотой при низкой точности. Поэтому для адекватной оценки используют комбинированную меру, которая учитывала бы одновременно и полноту и точность. В качестве такой меры традиционно используется F-мера:





где:

β – параметр, задающий приоритет точности над полнотой.


Для оценки качества поиска существует еще ряд критериев, например, так называемый 11-и точечный график полноты/точности, показывающий зависимость точности от полноты при шаге полноты в 10%. Чем выше проходит данный график, тем выше качество информационного поиска, демонстрируемого системой.

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

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



где:

n – количество первых возвращаемых документов;

a – количество релевантных среди первых возвращаемых документов.


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

Немаловажным фактором являются так называемые технические критерии качества поисковой системы. Среди них можно выделить: скорость поиска по запросу, объём проиндексированной базы документов, насколько правильно учтено ссылочное ранжирование документов и т.д.


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

^ 2. Полнота поиска в системе Exactus

Полнота поиска в системе Exactus растет за счет за счет:

1. Модулей метапоиска, позволяющих настраиваться на интерфейсы поисковых машин Интернет и при поиске средствами Exactus отправлять преобразованные запросы пользователя сразу на несколько поисковых ресурсов.Иначе говоря, полнота поиска метапоисковой системы равна суммарной полноте поиска ВСЕХ поисковых ресурсов, к которым она обращается.
   

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

Запрос: В районе станции Московского метрополитена Выхино обнаружили бомбу


Запрос после предобработки в автоматическом режиме:

В & (районе | области | зоне) & (станции | перегона) & Московского & (метрополитена | метро) & Выхино & обнаружили & (бомбу | взрывное устройство)


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

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

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

В системе Exactus имеется 4 профиля:


профиль Ситуация


Ситуация описывается объектами предметной области – участниками ситуации, и сложившимися отношениями между ними. С точки зрения профиля Ситуация, интерес представляют именно типы отношений между участниками, сами же участники не фиксированы. Например, если пользователь задал запрос «Птицы летят на Юг» и выбрал профиль Ситуация, то релевантными будут документы, в которых говорится, что что-то куда-то передвигается (не обязательно летит). Релевантными будут, помимо совпадающих с запросом, документы с текстами «Птицы перелетают на Запад», «Утки улетают на зимовье» и т.п;


профиль Факт

Факт - ситуация с фиксированными участниками. Для поиска фактов важны и участники и отношения на них. Для запроса «Птицы летят на Юг» релевантными будут те документы, в которых в точности говорится, что именно птицы летят в точности на Юг (а не на север или на озеро).


профиль Объект

Объекты – это участники ситуации. С точки зрения поиска объектов, отношения между участниками менее важны, чем характеристики участников. Для запроса «птицы летят на Юг» релевантными будут и «Птицы живут на Юге», «Эти птицы обитают к Югу от России» и т.п.


профиль Автоматический

В случае выбора автоматического профиля Exactus пытается понять, что имел в виду пользователь, когда вводил запрос и подобрать профиль автоматически (ситуация, факт или объект).


^ 3. Точность поиска в Exactus

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

Методы семантического поиска, реализованные в системе, основаны на теории коммуникативной грамматики русского языка [Золотова и др., 2004] и теории экстралингвистических семантических отношений [ Осипов, 1997].

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

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

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

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

^ 4. Дополнительные возможности Exactus

К дополнительным возможностям Exactus относятся:


4.1.Построение персональной онтологии пользователя.

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

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


4.2.Предварительная нарезка найденных документов

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


4.3.Контекстно-зависимое аннотирование найденных документов.

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


4.4.Возможность поиска на английском языке.

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


^ 5. Принципиальный алгоритм работы Exactus

Опишем принципиальный алгоритм работы Exactus:

1. Пользователь вводит запрос на естественном языке.
   
2. Запрос подвергается лингвистическому анализу.
   
3. Производится преобразование запроса в набор ключевых слов. При этом используется расширение синонимами, из запроса выбрасываются стоп-слова и т.д.
   
4. Преобразованный запрос отправляется сразу на несколько информационных источников (поисковых машин Интернет).
   
5. Отклики источников обрабатываются, из них выделяются тексты найденных документов.
   
6. Найденные документы подвергаются лингвистическому анализу, включающему морфологический, синтаксический и семантический анализ.
   
7. По результатам обработки проводится сравнение образов запроса и найденных документов и вычисление семантической релевантности.
   
8. Найденные документы фильтруются и сортируются в соответствие с вычисленной на предыдущем этапе релевантностью. Низкорелевантные документы отбрасываются.
   
9. Результаты поиска предоставляются пользователю.
   

Сказанное можно продемонстрировать на рис. 1.




Рис. 1. Диаграмма потоков данных при поиске.


^ 6. Результаты работ

В настоящее время реализован прототип системы, позволяющий осуществлять семантический поиск в сети Интернет (www.exactus.ru).

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

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

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

Дальнейшие направления работ:

1. Разработка кроулера для создания собственного семантического индекса документов сети Интернет.
   
2. Объединение статистических и семантических методов поиска для повышения скорости и качества поиска.
   
3. Разработка методов и средств семантического анализа для основных европейских языков.
   

^ Список литературы

[Осипов и др., 2004] Осипов Г.С., Тихомиров И.А., Смирнов И.В. Интеллектуальный поиск в глобальных и локальный вычислительных сетях и базах данных.// Труды международной конференции "Программные системы: теория и приложения". - ИПС РАН, Переславль-Залесский 2004. т2.

[Тихомиров, 2003] Тихомиров И.А. Полуавтоматическое распознавание интерфейсов Интернет-ресурсов. // Материалы первой международной дистанционной научно-практической конференции "Инновации и инвестиции: региональный опыт". – Рыбинск: РГАТА, 2003.

[Осипов, 1990] Осипов Г.С. Построение модели предметных областей. Неоднородные семантические сети. – Известия АН СССР. Техническая Кибернетика, 1990. №5.

[Золотова, 2001] Золотова Г.А. Синтаксический словарь. Репертуар элементарных единиц русского синтаксиса. – М., Эдиториал УРСС, 2001.

[Золотова и др., 2004] Золотова Г.А., Онипенко Н.К., Сидорова М.Ю. Коммуникативная грамматика русского языка. – М., 2004.

[Осипов, 1997] Осипов Г.С. Приобретение знаний интеллектуальными системами. Основы теории и технологии - М.: НАУКА ФИЗМАТЛИТ, 1997