Информационный поиск в Интернете Павел Морозов

План лекции Модели информационного поиска Булевская модель Векторная модель Вероятностная модель

План лекции Модели информационного поиска Булевская модель Векторная модель Вероятностная модель Архитектура поисковой системы

План лекции Модели информационного поиска Булевская модель Векторная модель Вероятностная модель Архитектура поисковой системы PageRank

Модели информационного поиска Что такое документ ? Что такое запрос ? При каком условии документ соответствует запросу ?

Булевская модель Словарь : T = {t 1,... t n } Документ : D T, иначе говоря D {0, 1} n Запрос : t 5 OR t 7 NOT t 12

Булевская модель Словарь : T = {t 1,... t n } Документ : D T, иначе говоря D {0, 1} n Запрос : t 5 OR t 7 NOT t 12 Соответствие : Формула запроса должна быть выполнена на документе.

Булевская модель Словарь : T = {t 1,... t n } Документ : D T, иначе говоря D {0, 1} n Запрос : t 5 OR t 7 NOT t 12 Соответствие : Формула запроса должна быть выполнена на документе. Недостатки модели ?

Векторная модель Снова коллекция документов, каждый из которых теперь является мультимножеством слов. Определим матрицу M по формуле M ij = TF ij · IDF i, где : Частота терма TF ij относительная доля слова i в тексте j Обратная встречаемость в документах IDF i величина, обратная количеству документов, содержащих слово i

Векторная модель Снова коллекция документов, каждый из которых теперь является мультимножеством слов. Определим матрицу M по формуле M ij = TF ij · IDF i, где : Частота терма TF ij относительная доля слова i в тексте j Обратная встречаемость в документах IDF i величина, обратная количеству документов, содержащих слово i Физический смысл M ij степень соответствия слова i тексту j

Векторная модель Снова коллекция документов, каждый из которых теперь является мультимножеством слов. Определим матрицу M по формуле M ij = TF ij · IDF i, где : Частота терма TF ij относительная доля слова i в тексте j Обратная встречаемость в документах IDF i величина, обратная количеству документов, содержащих слово i Физический смысл M ij степень соответствия слова i тексту j Запрос : t 3 AND t 5 ( разрешаем только AND)

Релевантность в векторной модели Запишем запрос в виде вектора : Q = t 3 AND t 5 ~ {0, 0, 1, 0, 1, 0,..., 0} Мерой релевантности будет косинус между запросом и документом :

Вероятностная модель для чайников Документ : множество слов ( булевский вектор ) D = {d 1,..., d n } Запрос : Q k тоже, но храним как множество

Вероятностная модель для чайников Документ : множество слов ( булевский вектор ) D = {d 1,..., d n } Запрос : Q k тоже, но храним как множество Соответствие : Зафиксируем запрос Q k Пусть есть распределение вероятностей на всех текстах быть релевантным запросу Q k : обозначаем Пусть есть распределение вероятностей на всех текстах быть НЕрелевантным запросу Q k : обозначаем Функцией соответствия будет их отношение ( или логарифм этой дроби ):

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

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

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

Вычисляем функцию соответствия II Введем обозначения : Предположим, что для каждого слова i, не входящего в запрос,

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

Вычисляем функцию соответствия III

Второй сомножитель одинаков для всех документов. Забудем про него и возьмем логарифм от первого :

Подбор параметров Для использования полученной формулы нужно знать p ik и q ik.

Подбор параметров Для использования полученной формулы нужно знать p ik и q ik. Рецепт : пусть у нас уже есть некий набор текстов, про которые мы знаем, релевантны они запросу Q k или нет. Тогда мы можем использовать формулы :

Подбор параметров II Тут f общее число документов, r число релевантных документов, r i число релевантных документов, содержащих слово i, f i общее число документов со словом i.

Архитектура поисковой системы В каком формате запоминать интернет - страницы ? В какой структуре данных их хранить ? Как обрабатывать запрос пользователя ?

Анатомия поисковой системы Любая поисковая система содержит три базовые части : Робот ( он же краулер, спайдер или индексатор ) Базы данных Клиент ( обработка запросов )

Схема из [Brin,Page, 1998]

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

Релевантность Наличие слов на сайте Частота слов Форматирование Близость слов друг к другу Количество ссылок с других страниц на данную Качество ссылок Соответствие тематик сайта и запроса Регистрация в каталоге, связанном с поисковой системой

Как работает клиент ? Разбирает запрос на слова Переводит слова в их идентификаторы Для каждого слова находит в обратном индексе список документов, его содержащих Одновременно бежит по этим спискам, ища общий документ Для каждого найденного документа вычисляет степень релевантности Сортирует образовавшийся список по релевантности

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

PageRank Как определить ссылочную популярность страницы (PageRank)? Как быстро вычислить приближение PageRank?

PageRank: постановка задачи Хотим для каждой страницы сосчитать показатель ее качества. Идея [ Брин, 1998]: Определить рейтинг страницы через количество ведущих на нее ссылок и рейтинг ссылающихся страниц Другие методы : Учет частоты обновляемости страницы Учет посещаемости Учет регистрации в каталоге - спутнике поисковой системы

Модель случайного блуждания Сеть : Вершины Ориентированные ребра ( ссылки ) Передвижение пользователей по сети Стартуем в случайной вершине С вероятностью ε переходим в случайную вершину С вероятностью 1 ε переходим по случайному исходящему ребру Предельные вероятности Для каждого k можно определить PR k (i) как вероятность оказаться в вершине i через k шагов lim k PR k (i) = PR(i) то есть для каждой вершины есть предельная вероятность находится именно в ней

Основное уравнение PageRank Пусть T1,...,Tn вершины, из которых идут ребра в i, C(X) обозначение для исходящей степени вершины X. По определению PR k (i ) верно следующее : Нужно перейти к пределу ! Практическое решение : вместо PR(i ) используют PR 50 (i ), вычисленное по итеративной формуле.

Вопросы ?