Информационный поиск в Интернете Павел Морозов pmorozov@bellintegrator.ru. - презентация

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

36 Вопросы ?