'

Информационный поиск: модели и методы

Понравилась презентация – покажи это...





Слайд 0

Информационный поиск: модели и методы Игорь Некрестьянов Санкт-Петербургский Университет igor@meta.math.spbu.ru


Слайд 1

Информационный поиск (ИП) Цель: удовлетворить информационные потребности пользователя Обсуждаемые темы: Модели ИП Критерии оценки качества поиска Поиск в Интернет Поиск по значимости


Слайд 2

Модель ИП: Логическое представление документов Логическое представление запросов Framework моделирования представлений документов и запросов, их взаимосвязей Ранжирующая функция


Слайд 3

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


Слайд 4

Булевы модели Модель на нечетких множествах (с термом запроса ассоциировано нечеткое множество документов) Расширенная булева модель Расширяет булеву модель для использования весов термов Обобщает модель на нечетких множествах и векторную модель (выбирая метрику)


Слайд 5

Векторные модели Обобщенная векторная модель (учет корреляции между термами) Латентно-семантический анализ (отображение документов и запросов в пространство концепций) Нейронные сети (нейроны —термы документов и документы, многошаговое распространение сигнала)


Слайд 6

Вычисление весов термов Частота терма в документе Обратная частота термов в коллекции Вычисление весов


Слайд 7

Нормализация весов Преимущества длинных документов: Больше различных термов Выше частоты термов Методы нормализации: по максимальной частоте по длине вектора весов всех термов в данном документе по длине в байтах


Слайд 8

Вероятностные модели Вероятностный принцип Оценить вероятность того, что документ будет интересен пользователю Модель сетей вывода (inference networks) На основе сети Байеса Могут имитировать булеву модель, некоторые векторные модели, обратную связь Реализована в Inquery


Слайд 9

Моделирование языка Zipf’s Law Heaps’ Law Слова F V Размер текста


Слайд 10

Предварительная обработка текста Лексический анализ Исключение стоп-слов Выделение основ слов (stemming) Выбор термов для индексирования (например только существительных) Тезаурусы (выделение категорий термов)


Слайд 11

Языки запросов Запросы по ключевым словам однословные контекстные логические на естественном языке Запросы по шаблонам Протоколы запросов (Z39.50, WAIS)


Слайд 12

Уточнение запросов: Изменение весов термов запроса Добавление новых термов в запрос Основные подходы: Обратная связь (Relevance feedback) Автоматический локальный анализ Автоматический глобальный анализ


Слайд 13

Критерии оценки Точность Полнота Процент мусора A R S


Слайд 14

Критерии оценки (2) Средняя точность Интерполяция По числу документов P@20, P@50, p@100


Слайд 15

Критерии оценки (3) Точность на уровне обнаружения заданного числа релевантных документов Точность среди первых R возвращенных, где R – число реально релевантных (R-precision) Гистограммы точности (сравнение эффективности двух алгоритмов на каждом запросе)


Слайд 16

Критерии оценки (4) Среднее гармоническое (b = 1) (компромисс между точностью и полнотой) E-мера (учет предпочтений пользователя)


Слайд 17

Критерии оценки (5) Пользовательские критерии: Коэффициент покрытия (процент уже известного среди найденного) Коэффициент новизны (отношение нового к уже известному) Относительная полнота (отношение нового к ожидаемому)


Слайд 18

Особенности поиска в Интернет Огромный размер > 1 миллиарда документов (февраль 2000) > 75 миллионов узлов Короткие запросы ( < 2 слов) Почти не используются продвинутые возможности языка запросов Много изменений в данных (40% в месяц)


Слайд 19

Размер поисковых систем


Слайд 20

Оценка качества индекса Не все страницы одинаково важны Метрики Суммарная значимость всех страниц Средняя значимость страниц Метод случайной прогулки Как проверить наличие страницы в индексе? Как оценить значимость страницы?


Слайд 21

TREC и Web Коллекция VLC2: 100Гб, 18.5 миллионов документов Короткие запросы из TREC (2.5 слова) 5 поисковых систем


Слайд 22

Задачи ИП в Интернет Обнаружение дубликатов Интеллектуальные сетевые роботы Борьба с опечатками Levenshtein(survey, surgery) = 2 LCS(survey, surgery) = surey Метапоиск Как делать слияние результатов (data fusion)?


Слайд 23

Классификация типов копий Повторение содержания (1) и структуры (2)


Слайд 24

Оценка повторения структуры Построение описаний URL yahoo.com/ref/art/news.htm (yahoo,com) (ref, art, 0) (art, news, 1) (news, htm, 2) Сокращение числа кандидатов (стоп-слова, нехарактерные пары) Вычисление весов (IDF) Вычисление оценки похожести узлов Уровни похожести: 100%, 50%, 0%


Слайд 25

Оценка повторения содержания Выбор страниц для проверки Проверка на полную идентичность Вычисление оценки близости: S(A) — множество k-грамм документа A


Слайд 26

Сетевые роботы Области применения: Построение индексов Сбор статистики Поиск ресурсов Исследование структуры Интернет Проверка целостности ссылок Стратегии обхода: Простые Учет структуры URL (уровень вложенности) Учет структуры графа (PageRank) Учет содержимого страницы (OASIS Crawler)


Слайд 27

Поиск по значимости Дополнение к оценкам близости Значимость не зависит от запроса Значимость бывает не только у текстовых ресурсов Более значимые ресурсы имеют приоритет при прочих равных


Слайд 28

Значимость из содержимого Анализ документа (PHOAKS, определение жанра текста) Анализ коллекции (Google, SCAM, PHOAKS) Информационный контекст (Referral Web) Внутренние метки в документе (PICS, RDF)


Слайд 29

Значимость из действий Явные указания: Обратная связь (групповая) Триггеры на данные (почтовые фильтры) Синтезированные фильтры (пользователь задает высокоуровневое описание)


Слайд 30

Значимость из действий (2) Неявные указания: Коллективное поведение пользователей (WebWatcher, Hotbot) Индивидуальное поведение пользователя Какие документы/коллекции он посещает? Что он делает с документом? (время просмотра, новая закладка, запись на диск, ответ на письмо)


Слайд 31

Основные конференции SIGIR (http://www.acm.org/sigir/) Digital Libraries Text Retrieval Conference (TREC) (http://trec.nist.gov) WWW Conference (http://www9.org) Электронные Библиотеки (http://www.protvino.ru/dl2000)


×

HTML:





Ссылка: