Поиск в коллекциях текстовых документов на основе методов семантического анализа, использующих универсальные гипертекстовые энциклопедии Александр Болдаков Институт системного программирования РАН

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

Задача поиска в текстовых коллекциях Information retrieval & Semantic Web Актуальность (Web 2.0 – очередной всплеск) Разные типы документов в коллекциях – специализация систем поиска Блоги (мало связанные, актуальные,…) Новости (мало связанные, очень актуальные,…) Научные статьи (строгая терминология, мало именованных сущностей,…) Web (большое количество мусора, сильная связанность,…)

Проблемы лексического поиска по ключевым словам (1) Лексическая многозначность терминов Многозначность терминов в запросе Многозначность терминов в тексте документа Результат: ухудшение точности результатов Учет синонимов Синонимы, аббревиатуры, сленг, прозвища и т.д. Результат: ухудшение полноты результатов Оценка релевантности Основана на композиции статистических значений Результат: ухудшение ранжирования результатов

Проблемы лексического поиска по ключевым словам (2) Сложность подбора ключевых слов Неопределенность предмета поиска Недостаточная осведомленность о предметной области Результат: ухудшение полноты результатов Интерфейс Система – черный ящик Модель поиска – несвязанная последовательность запросов Нет механизмов уточнения поиска Результат: снижение эффективности поиска иощущение потерянности в данных

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

Wikipedia как основа для построения универсальной базы знаний Преимущества англоязычной Wikipedia: Универсальность (около 3 млн. статей) Актуальность Структурированность (ссылки различных типов, категории, метаданные и т.д.) Доступность для пополнения пользователями

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

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

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

Устранение лексической многозначности терминов: пример Текст: Jigsaw is W3C's open-source project that started in May It is a web server platform that provides a sample HTTP 1.1 implementation and …

Ранжирование терминов в документе Задача: отсортировать термины в документе по их семантической важности Критерий важности: центральность вершины в графе терминов в документе Вес термина: алгоритм PageRank на взвешенном графе

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

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

Формирование поискового запроса: концепции Wikipedia Использование словаря концепций Wikipedia как основы для формирования поисковых запросов Устранение лексической многозначности Учёт синонимов, аббревиатур и т.д.

Формирование поискового запроса: интеграция с поиском по терминам Использование словаря концепций Wikipedia как основы для формирования поисковых запросов Статистика Google – 40% запросов ведут к статье Wikipedia как к первому результату Соответствует исследовательскому-поиску Необходимость комбинировать поиск по концепциям и по терминамы Не все концепции есть в Wikipedia Поддержка навигационного поиска Синтаксис Electric car; Speed; fastest Electric car; fastest speed

Формирование поискового запроса: смешанный запрос

Извлечение семантики из документа при индексировании Документ D состоит из последовательности лексем L(D)=l 1,l 2,…,l k Извлечение концепций C(D) = {c i } Устранение многозначности Учет синонимов Векторная модель представления документа и запроса: концепции, термины Вектор размерности |C|+|L| Концепциям соответствует семантический вес Терминам соответствует лексический вес

Определение весов: значимость терминов и концепций Значимость терминов: значимость определяется статистическими величинами Значимость концепций: концепция в документе тем более значима, чем больше в документе сильно связанных с ней концепций Sedna (database) без связанных терминов в рекламе Sedna (database) в окружении XML, XQuery, XML database Если концепция встречается в документе без связанных с ней концепций, то её вклад в релевантность такой же, как у лексического термина

Определение весов для терминов Измерение косинуса между векторами запроса и документа f d,t – частота встречаемости термина в документе f t – число документов в которых встречается термин N – общее число документов в коллекции w q,t, w d,t – веса в векторе запроса и документа S q,d – функция близости запроса и документа

Определение весов для концепций

Если нет связанных вершин, то вес совпадает с лексическим весом концепции

Лексическое представление концепций в индексе ExtName(c) = title(c)+_(concept) LexName(c) = replace(ExtName(c),,_) Пример: c = IBM, LexName(c) = IBM_(concept)

Индексация документов Для каждой концепций с i из C(D) в индекс добавляется запись LexName( с i ) (id D,w с i ) Для каждого термина l i из L(D) в индекс добавляется запись l i (id D,w l i )

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

Учет ошибок устранения многозначности и ошибок при выделении терминов L – последовательность слов Redir(c) = {L i } – названия статей в Wikipedia, которые указывают на с Amb(c) = {L i } – названия статей для устранения многозначности в Wikipedia, содержащих c среди возможных значений Repr(c) = {L i } = name(c) U Redir(c) U Amb(c) – множество возможных текстовых представлений концепции Пример: c = IBM Redir(c) = International Business Machines, Ibm Amb(c) = IBM, Big Blue Repr(c) = IBM, International Business Machines, Big Blue

Выполнение запросов: поиск по концепции Поиск по концепции с Repr(c) = {L i } Интерпретация запроса: LexName(с i ), L 1 *w, L 2 *w, …, L N *w w = 0.01, вес понижающий вклад L i в релевантность L i – улучшают полноту выборки и не влияют на ранжирование документов, содержащих распознанную концепцию

Выполнение запросов: смешанный поиск Поиск по концепции с и лексеме l Repr(c) = {L i } Интерпретация запроса: LexName(с i ),L 1 *w,…,L N *w, l w = 0.01, вес понижающий вклад L i в релевантность L i – улучшают полноту выборки и не влияют на ранжирование документов, содержащих распознанную концепцию с и/или термин l

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

Расширение запроса концепциями, семантически близкими к искомой (2) Exp(c)={c 1,…,c k } – множество концепций: Sim(c1,c2)!=0 Exp p (c)={c 1,…,c k } – множество концепций: Sim(c1,c2)>p Расширение запроса по концепции с Q orig = c Q expanded = c;c 1* w 1 ;…;c k* w k w i = Sim(c,c i )

Расширение запроса концепциями, семантически близкими к искомой: пример 1. Cost per click {0.30} 2. Pay per click {0.24} 3. Ad serving {0.22} 4. Affiliate marketing {0.20} 5. Online advertising {0.18} 6. Compensation methods {0.18} 7. Search engine marketing {0.17} 8. Cost per action {0.17} 9. Social media optimization {0.16} 10. Audience screen {0.16} с = Internet marketing, Exp 0.13 (c): 11. Search engine optimization {0.16} 12. Cost per mille {0.15} 13. Web banner {0.15} 14. PubCon {0.15} 15. Landing page optimization {0.15} 16. Pay per play {0.15} 17. Cost per Activity (CPA) {0.13} 18. Cost per impression {0.13} 19. marketing {0.13}

Построение фасетного поискового интерфейса Комбинация навигационного и поискового интерфейсов В ответ на поисковый запрос фасетная поисковая система формирует: Список релевантных результатов на текущий запрос Набор фасетов – терминов, предназначенных для: Уточнения поискового запроса Навигации по коллекции документов Методы извлечения фасетных терминов: Использование созданной вручную метаинформации о документах Автоматическое извлечение фасетных терминов

Подзадачи Идентификация терминов-кандидатов Рекомендация конкретных фасетов на текущем шаге поиска Учет текущего запроса Учет текущего множества результатов

Построение фасетного поиска на основе методов семантического анализа текстов Идентификация фасетов: хорошие претенденты – ключевые слова в документах Рекомендация фасетов: Объединение ключевых слов для всех документов из текущего множества результатов – множество возможных фасетов Термины, семантически близкие к запросу, описывают текущий домен интересов пользователя Решение:

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

Подтверждающие концепции в поисковом интерфейсе

Реализация фасетного поискового интерфейса (2)

Накладные расходы Скорость индексирования (0.5 Mb/s) Выделение концепций Устранение многозначности Построение взвешенного графа концепций Размер индекса (+20%) Выделенные концепции дублируются своим лексическим представлением Увеличение кол-ва терминов в запросе Расширение запроса лексическим представлением концепций Расширение запроса близкими концепциями Регулярное обновление Wikipedia

Заключение Преимущества подхода Качество ранжирования результатов Полнота выборки Подтверждающие концепции Автоматическое построение фасетов Недостатки Поиск не на естественном языке (интерфейс) Время индексации документов (0.5 Mb/s) Размер индекса (+20%)

Спасибо за внимание Александр Болдаков Институт системного программирования РАН