Слайд 2Информационный поиск (ИП)
Цель: удовлетворить информационные потребности пользователя
Обсуждаемые темы:
Модели ИП
Критерии оценки качества поиска
Поиск
![Информационный поиск (ИП) Цель: удовлетворить информационные потребности пользователя Обсуждаемые темы: Модели ИП](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/410663/slide-1.jpg)
в Интернет
Поиск по значимости
Слайд 3Модель ИП:
Логическое представление документов
Логическое представление запросов
Framework моделирования представлений документов и запросов, их
![Модель ИП: Логическое представление документов Логическое представление запросов Framework моделирования представлений документов](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/410663/slide-2.jpg)
взаимосвязей
Ранжирующая функция
Слайд 4Классификация моделей
Булева модель
(теория множеств и булева алгебра)
Векторная модель
(векторные пространства и
![Классификация моделей Булева модель (теория множеств и булева алгебра) Векторная модель (векторные](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/410663/slide-3.jpg)
линейная алгебра)
Вероятностная модель
(множества, теория вероятностей)
Классические модели подразумевают независимость слов (термов)
Слайд 5Булевы модели
Модель на нечетких множествах
(с термом запроса ассоциировано нечеткое множество документов)
Расширенная булева
![Булевы модели Модель на нечетких множествах (с термом запроса ассоциировано нечеткое множество](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/410663/slide-4.jpg)
модель
Расширяет булеву модель для использования весов термов
Обобщает модель на нечетких множествах и векторную модель (выбирая метрику)
Слайд 6Векторные модели
Обобщенная векторная модель
(учет корреляции между термами)
Латентно-семантический анализ
(отображение документов и запросов
![Векторные модели Обобщенная векторная модель (учет корреляции между термами) Латентно-семантический анализ (отображение](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/410663/slide-5.jpg)
в пространство концепций)
Нейронные сети
(нейроны —термы документов и документы,
многошаговое распространение сигнала)
Слайд 7Вычисление весов термов
Частота терма в документе
Обратная частота термов в коллекции
Вычисление весов
![Вычисление весов термов Частота терма в документе Обратная частота термов в коллекции Вычисление весов](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/410663/slide-6.jpg)
Слайд 8Нормализация весов
Преимущества длинных документов:
Больше различных термов
Выше частоты термов
Методы нормализации:
по максимальной частоте
по длине
![Нормализация весов Преимущества длинных документов: Больше различных термов Выше частоты термов Методы](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/410663/slide-7.jpg)
вектора весов всех термов в данном документе
по длине в байтах
Слайд 9Вероятностные модели
Вероятностный принцип
Оценить вероятность того, что документ будет интересен пользователю
Модель сетей
![Вероятностные модели Вероятностный принцип Оценить вероятность того, что документ будет интересен пользователю](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/410663/slide-8.jpg)
вывода (inference networks)
На основе сети Байеса
Могут имитировать булеву модель, некоторые векторные модели, обратную связь
Реализована в Inquery
Слайд 10Моделирование языка
Zipf’s Law
Heaps’ Law
Слова
F
V
Размер текста
![Моделирование языка Zipf’s Law Heaps’ Law Слова F V Размер текста](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/410663/slide-9.jpg)
Слайд 11Предварительная обработка текста
Лексический анализ
Исключение стоп-слов
Выделение основ слов (stemming)
Выбор термов для индексирования
(например
![Предварительная обработка текста Лексический анализ Исключение стоп-слов Выделение основ слов (stemming) Выбор](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/410663/slide-10.jpg)
только существительных)
Тезаурусы
(выделение категорий термов)
Слайд 12Языки запросов
Запросы по ключевым словам
однословные
контекстные
логические
на естественном языке
Запросы по шаблонам
Протоколы запросов (Z39.50, WAIS)
![Языки запросов Запросы по ключевым словам однословные контекстные логические на естественном языке](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/410663/slide-11.jpg)
Слайд 13Уточнение запросов:
Изменение весов термов запроса
Добавление новых термов в запрос
Основные подходы:
Обратная связь (Relevance
![Уточнение запросов: Изменение весов термов запроса Добавление новых термов в запрос Основные](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/410663/slide-12.jpg)
feedback)
Автоматический локальный анализ
Автоматический глобальный анализ
Слайд 14Критерии оценки
Точность
Полнота
Процент мусора
A
R
S
![Критерии оценки Точность Полнота Процент мусора A R S](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/410663/slide-13.jpg)
Слайд 15Критерии оценки (2)
Средняя точность
Интерполяция
По числу документов
P@20, P@50, p@100
![Критерии оценки (2) Средняя точность Интерполяция По числу документов P@20, P@50, p@100](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/410663/slide-14.jpg)
Слайд 16Критерии оценки (3)
Точность на уровне обнаружения заданного числа релевантных документов
Точность среди первых
![Критерии оценки (3) Точность на уровне обнаружения заданного числа релевантных документов Точность](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/410663/slide-15.jpg)
R возвращенных, где R – число реально релевантных
(R-precision)
Гистограммы точности
(сравнение эффективности двух алгоритмов на каждом запросе)
Слайд 17Критерии оценки (4)
Среднее гармоническое (b = 1)
(компромисс между точностью и полнотой)
E-мера
(учет
![Критерии оценки (4) Среднее гармоническое (b = 1) (компромисс между точностью и](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/410663/slide-16.jpg)
предпочтений пользователя)
Слайд 18Критерии оценки (5)
Пользовательские критерии:
Коэффициент покрытия
(процент уже известного среди найденного)
Коэффициент новизны
(отношение нового к
![Критерии оценки (5) Пользовательские критерии: Коэффициент покрытия (процент уже известного среди найденного)](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/410663/slide-17.jpg)
уже известному)
Относительная полнота
(отношение нового к ожидаемому)
Слайд 19Особенности поиска в Интернет
Огромный размер
> 1 миллиарда документов (февраль 2000)
> 75 миллионов
![Особенности поиска в Интернет Огромный размер > 1 миллиарда документов (февраль 2000)](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/410663/slide-18.jpg)
узлов
Короткие запросы ( < 2 слов)
Почти не используются продвинутые возможности языка запросов
Много изменений в данных (40% в месяц)
Слайд 21Оценка качества индекса
Не все страницы одинаково важны
Метрики
Суммарная значимость всех страниц
Средняя значимость страниц
![Оценка качества индекса Не все страницы одинаково важны Метрики Суммарная значимость всех](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/410663/slide-20.jpg)
Метод случайной прогулки
Как проверить наличие страницы в индексе?
Как оценить значимость страницы?
Слайд 22TREC и Web
Коллекция VLC2:
100Гб, 18.5 миллионов документов
Короткие запросы из TREC (2.5
![TREC и Web Коллекция VLC2: 100Гб, 18.5 миллионов документов Короткие запросы из](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/410663/slide-21.jpg)
слова)
5 поисковых систем
Слайд 23Задачи ИП в Интернет
Обнаружение дубликатов
Интеллектуальные сетевые роботы
Борьба с опечатками
Levenshtein(survey, surgery) = 2
LCS(survey,
![Задачи ИП в Интернет Обнаружение дубликатов Интеллектуальные сетевые роботы Борьба с опечатками](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/410663/slide-22.jpg)
surgery) = surey
Метапоиск
Как делать слияние результатов (data fusion)?
Слайд 24Классификация типов копий
Повторение содержания (1) и структуры (2)
![Классификация типов копий Повторение содержания (1) и структуры (2)](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/410663/slide-23.jpg)
Слайд 25Оценка повторения структуры
Построение описаний URL
yahoo.com/ref/art/news.htm
(yahoo,com) (ref, art, 0) (art, news, 1) (news,
![Оценка повторения структуры Построение описаний URL yahoo.com/ref/art/news.htm (yahoo,com) (ref, art, 0) (art,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/410663/slide-24.jpg)
htm, 2)
Сокращение числа кандидатов
(стоп-слова, нехарактерные пары)
Вычисление весов (IDF)
Вычисление оценки похожести узлов
Уровни похожести: 100%, 50%, 0%
Слайд 26Оценка повторения содержания
Выбор страниц для проверки
Проверка на полную идентичность
Вычисление оценки близости:
S(A) —
![Оценка повторения содержания Выбор страниц для проверки Проверка на полную идентичность Вычисление](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/410663/slide-25.jpg)
множество k-грамм документа A
Слайд 27Сетевые роботы
Области применения:
Построение индексов
Сбор статистики
Поиск ресурсов
Исследование структуры Интернет
Проверка целостности ссылок
Стратегии обхода:
Простые
Учет структуры
![Сетевые роботы Области применения: Построение индексов Сбор статистики Поиск ресурсов Исследование структуры](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/410663/slide-26.jpg)
URL
(уровень вложенности)
Учет структуры графа
(PageRank)
Учет содержимого страницы
(OASIS Crawler)
Слайд 28Поиск по значимости
Дополнение к оценкам близости
Значимость не зависит от запроса
Значимость бывает не
![Поиск по значимости Дополнение к оценкам близости Значимость не зависит от запроса](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/410663/slide-27.jpg)
только у текстовых ресурсов
Более значимые ресурсы имеют приоритет при прочих равных
Слайд 29Значимость из содержимого
Анализ документа
(PHOAKS, определение жанра текста)
Анализ коллекции
(Google, SCAM, PHOAKS)
Информационный контекст
(Referral Web)
Внутренние
![Значимость из содержимого Анализ документа (PHOAKS, определение жанра текста) Анализ коллекции (Google,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/410663/slide-28.jpg)
метки в документе
(PICS, RDF)
Слайд 30Значимость из действий
Явные указания:
Обратная связь
(групповая)
Триггеры на данные
(почтовые фильтры)
Синтезированные фильтры
(пользователь задает
![Значимость из действий Явные указания: Обратная связь (групповая) Триггеры на данные (почтовые](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/410663/slide-29.jpg)
высокоуровневое описание)
Слайд 31Значимость из действий (2)
Неявные указания:
Коллективное поведение пользователей
(WebWatcher, Hotbot)
Индивидуальное поведение пользователя
Какие документы/коллекции
![Значимость из действий (2) Неявные указания: Коллективное поведение пользователей (WebWatcher, Hotbot) Индивидуальное](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/410663/slide-30.jpg)
он посещает?
Что он делает с документом?
(время просмотра, новая закладка, запись на диск, ответ на письмо)