Информационно-поисковые системы. Сычев А.В г.1 Математические модели документального поиска Воронежский государственный университет Факультет компьютерных наук Кафедра информационных систем

Информационно-поисковые системы. Сычев А.В г.2 Обобщенное описание модели документального поиска Задается в виде кортежа, где D – множество представлений документа Q – множество представлений информационной потребности (запроса) F – средства моделирования представлений документа, запросов и их отношений R(d,q) – функция ранжирования Ставит в соответствие d из D и q из Q вещественные числа Определяет порядок на множестве документов относительно запроса q

Информационно-поисковые системы. Сычев А.В г.3 Математические модели документального поиска Теоретико-множественные (булевская, нечеткие множества, расширенная булевская) Вероятностные (сети вывода, энтропийная и др.) Алгебраические (векторная, матричная и др.)

Информационно-поисковые системы. Сычев А.В г.4 Теоретико-множественная модель - Множество всех документов в системе - Подмножество документов, соответствующих заданной информационной потребности пользователя (релевантных) - Подмножество нерелевантных документов - Подмножество автоматно-релевантных документов - Подмножество автоматно-нерелевантных документов

Информационно-поисковые системы. Сычев А.В г.5 Теоретико-множественная модель - Подмножество релевантных документов, оказавшихся в выдаче - Подмножество нерелевантных документов, оказавшихся в выдаче - Подмножество релевантных документов, не оказавшихся в выдаче - Подмножество нерелевантных документов, не оказавшихся в выдаче

Информационно-поисковые системы. Сычев А.В г.6 Теоретико-множественная модель

Информационно-поисковые системы. Сычев А.В г.7 Теоретико-множественная модель b = c = 0: идеальное качество поиска

Информационно-поисковые системы. Сычев А.В г.8 - простое соответствие - коэффициент Дайса (Dice) - коэффициент Жаккарда (Jaccard) - косинусный коэффициент - коэффициент перекрытия где Q и D – множества терминов в запросе и документе соответственно Метрики подобия

Информационно-поисковые системы. Сычев А.В г.9 Самая простая модель, основанная на теории множеств Запросы представляются в виде булевских выражений из слов и логических операторов И, ИЛИ, НЕ. Релевантными считаются документы, которые удовлетворяют булевскому выражению в запросе. Булевская модель

Информационно-поисковые системы. Сычев А.В г.10 Булевская модель Матрица документ-термин C(d,t) показывает какие встречаются слова и в каких документах C(d,t) Запрос : q = a И (b ИЛИ (НЕ c))

Информационно-поисковые системы. Сычев А.В г.11 a-> 1,1,1,0,1 b-> 0,1,0,1,1 НЕ c-> 1,1,0,1,0 Булевская модель ИЛИ 1,1,0,1,1 И 1,1,0,0,1 Запрос :q = a И (b ИЛИ (НЕ c)) Результат: d1, d2, d5

Информационно-поисковые системы. Сычев А.В г.12 Взамен бинарных величин термины в документах и запросах описываются весовыми коэффициентами (значимость или статистическая оценка) Используется аппарат нечетких множеств, т.е. степень принадлежности элемента к множеству задается величиной из интервала [0,1]. Степень принадлежности элементов может использоваться для ранжирования результатов запроса Расширенная булевская модель

Информационно-поисковые системы. Сычев А.В г.13 Булевские модели: достоинства и недостатки Достоинства: простая, легко понимаемая структура запроса простота реализации Недостатки: недостаточно возможностей для описания сложных запросов результатов запроса либо слишком много либо слишком мало проблематичность при ранжирования результатов Пока еще распространены в коммерческих ИПС

Информационно-поисковые системы. Сычев А.В г.14 Требуется метрика для описания подобия между запросом и документом. Для этого необходимо привлекать характеристики документов и запроса. Можно предположить, что лингвистическое подобие документа и запроса подразумевает тематическое подобие, т.е. выражает фактически релевантность документа. Альтернативные модели

Информационно-поисковые системы. Сычев А.В г.15 Векторная модель Документы и запросы представляются в виде векторов в N-мерном евклидовом пространстве Компоненты вектора соответствуют N терминам, образующим пространство.

Информационно-поисковые системы. Сычев А.В г.16 Релевантность выражается через подобие векторов Для вычисления подобия векторов используется косинусная метрика Векторная модель

Информационно-поисковые системы. Сычев А.В г.17 Для построения пространства терминов обычно используются основы слов, отдельные слова, а также целые фразы, пары слов и т.д. Документы и запросы представляются в виде векторов, компоненты которых соответствуют весам терминов w t. Чем больше используется терминов, тем сложнее понять какие подмножества слов являются общими для подобных документов. Векторная модель

Информационно-поисковые системы. Сычев А.В г.18 Ключевые вопросы : Как выбирать размерность пространства терминов N ? Как вычислять весовые коэффициенты w t ? Векторная модель

Информационно-поисковые системы. Сычев А.В г.19 Закон Ципфа (Zipf) Произведение частоты термина f на его ранг r остается примерно постоянной величиной f = C/r, C N/10

Информационно-поисковые системы. Сычев А.В г.20 Принцип Луна (Luhn) Самые часто встречающиеся слова – не самые значимые!

Информационно-поисковые системы. Сычев А.В г.21 Бинарные веса: W ij =1 если документ d i содержит термин t j, иначе 0. Частота термина tf ij, т.е. сколько раз встретился термин t j в документе d i tf x idf: чем выше частота термина в документе – тем выше его вес, но термин должен не часто встречаться во всей коллекции документов Расчет весов терминов

Информационно-поисковые системы. Сычев А.В г.22 Расчет tf x idf t f ik – частота термина T k в документе D i idf k – обратная документальная частота для термина T k в коллекции С N – общее число документов в коллекции N k - количество документов в коллекции C, содержащих термин T k

Информационно-поисковые системы. Сычев А.В г.23 Векторная модель Достоинства: Учет весов повышает эффективность поиска Позволяет оценить степень соответствия документа запросу Косинусная метрика удобна при ранжировании Проблемы: Нет достаточного теоретического обоснования для построения пространства терминов Поскольку термины не являются независимыми друг от друга, то они не могут быть полностью ортогональными Имеет преимущество перед другими моделями ввиду простоты и изящества

Информационно-поисковые системы. Сычев А.В г.24 Вероятностные модели Заключаются в оценке вероятности того, что документ d является релевантным по отношению к запросу q: Pr(R|d,q). При ранжировании документов в выборке ключевым являет Принцип Ранжирования Вероятностей, согласно которому если каждый ответ поисковой системы представляет собой ранжированный по убыванию вероятности полезности для пользователя список документов, то общая эффективность системы для пользователей будет наилучшей.

Информационно-поисковые системы. Сычев А.В г.25 Вероятностные модели: определения Релевантность R определяется как отношение: – вероятности того, что d – релевантный и не релевантный соответственно Допущения: Структура документа описывается бинарным вектором в пространстве терминов Релевантность документа запросу оценивается независимо от других документов.

Информационно-поисковые системы. Сычев А.В г.26 Вероятность вычисляется на основе теоремы Байеса: P(R) – вероятность того, что случайно выбранный из коллекции документ D является релевантным P(d|R) – вероятность случайного выбора документа d из множества релевантных документов P(d) – вероятность случайного выбора документа d из коллекции D Вероятностные модели: правило принятия решения

Информационно-поисковые системы. Сычев А.В г.27 Вероятностные модели: правило принятия решения Решающее правило заключается в максимизации следующей функции:

Информационно-поисковые системы. Сычев А.В г.28 В предположении о независимости терминов друг от друга: d i – бинарная величина, указывающая на наличие либо отсутствие термина t i в документе d Вероятностные модели: правило принятия решения

Информационно-поисковые системы. Сычев А.В г.29 Вводя обозначения: получим: Вероятностные модели: правило принятия решения

Информационно-поисковые системы. Сычев А.В г.30 В итоге: или после логарифмирования: Вероятностные модели: правило принятия решения

Информационно-поисковые системы. Сычев А.В г.31 C – константа, не зависящая от документов c i – вес релевантности термина, показывающий дискриминантную способность между релевантными и нерелевантными документами термина t i. Проблема: оценка вероятностей p t и q t Вероятностные модели: правило принятия решения

Информационно-поисковые системы. Сычев А.В г.32 Оценка вероятности на основе обратной связи по релевантности (Robertson&Jones) Если пользователь предоставляет информацию об оценке релевантности полученных им документов (обратная связь) в виде R – числа релевантных документов и r – число релевантных документов, содержащих термин t N – общее число документов выданных пользователю n - число документов, содержащих термин t, то можно получить следующие оценки: p t = r/R q t = (n-r)/(N-r)

Информационно-поисковые системы. Сычев А.В г.33 Оценка вероятности на основе обратной связи по релевантности (Robertson & Spark Jones) РелевантныеНерелевантныеВсего Содержат t rn-rn Не содержат t R-rN-n-R+rN-n Всего RN-RN

Информационно-поисковые системы. Сычев А.В г.34 Оценка веса релевантности термина: Проблема: высокая затратность оценки Большинство систем используют формулу Okapi BM25, учитывающую веса Робертсона-Спарка Джонса. Логистическая регрессия Оценка вероятности на основе обратной связи по релевантности (Robertson & Spark Jones)

Информационно-поисковые системы. Сычев А.В г.35 Пример (1) Имеется 20 документов оцениваемых по 2 терминам: D = (d 1, d 2 ) Отсюда: N = 20; R = 12; r 1 = 8; r 2 = 7; n 1 = 11; n 2 = 11

Информационно-поисковые системы. Сычев А.В г.36 Пример (2) p 1 = 8/12; p 2 = 7/12; q 1 = 3/8; q 2 = 4/8; c 1 = 1.2; c 2 = 0.34; S(D) = 1.2*d *d 2

Информационно-поисковые системы. Сычев А.В г.37 Вероятностные модели: достоинства и недостатки Достоинства: Хорошее теоретическое обоснование При имеющейся информации дают наилучшие предсказания релевантности Могут быть реализованы аналогично векторным моделям Недостатки: Требуется информация о релевантности или ее приближенные оценки Структура документа описывается только терминами Оптимальные результаты получаются только в процессе обучения на основе информации о релевантности

Информационно-поисковые системы. Сычев А.В г.38 Рассматривает множество из n документов. На его основе можно построить множество из m терминов, которые хоть раз встречались в каком- либо или более документах. Можно ввести матрицы сопряженности трех типов: документ-документ термин-термин документ-термин Матричная модель

Информационно-поисковые системы. Сычев А.В г.39 Матричная модель

Информационно-поисковые системы. Сычев А.В г.40 Матричная модель Матрица сопряженности документ-документ размерностью (n x n) Элемент d [i,j] указывает на наличие терминов содержащихся одновременно в j-м и i-м документах (бинарный случай), либо равен количеству общих терминов в этих документах

Информационно-поисковые системы. Сычев А.В г.41 Матричная модель Матрица сопряженности термин-термин размерностью (m x m) Элемент t [i,j] указывает на наличие документов содержащих одновременно j-й и i-й термины (бинарный случай), либо равен количеству таких документов

Информационно-поисковые системы. Сычев А.В г.42 Матричная модель Запрос пользователя можно представить в виде: n-мерного вектора-строки Q[q i ], i-ая координата которого не равна нулю в том случае, если i-ый документ включен пользователем в список документов, представляющих его запрос m-мерного вектора-столбца Q[q i ], i-ая координата которого равна единице, если i-ый термин включен пользователем в список терминов, представляющий его запрос.

Информационно-поисковые системы. Сычев А.В г.43 Реакция системы (вектор релевантностей) на запрос пользователя Q вычисляется как: A = C * Q Значение i-ой координаты n-мерного вектора A[a i ] при этом оказывается равным числу терминов запроса (бинарный случай), оказавшихся в i-ом документе. Матричная модель

Информационно-поисковые системы. Сычев А.В г.44 Информационный поиск описывается в виде итерационного процесса: A (0) = C * Q (0) Q (1) = C T * A (0) A (1) = C * Q (1) …………………….. A (t) = C * Q (t) Q (t+1) = C T * A (t) Элементы Q (i), i>0, рассматриваются как уточненные величины значимостей терминов в запросе. Матричная модель

Информационно-поисковые системы. Сычев А.В г.45 Можно заметить, что Q (t) = (C T С) t Q (0) A (t) = (CC T ) t * A (0) Из теоремы Сильвестра при достаточно больших t можно получить приближение: Q (t+1) = λ 0 Q (t) A (t+1) = λ 0 A (t) где λ 0 – собственное значение матрицы C T С. Матричная модель

Информационно-поисковые системы. Сычев А.В г.46 Видно, что с увеличением t векторы Q (t) и A (t) стремятся принимать направления собственных векторов матриц C T С и СC T, соответствующих собственным значениям этих матриц. Т.е. если вектор Q (0) не учитывает фактор поисковой среды, то уже начиная с Q (1) этот фактор учитывается. При больших значениях t вектор Q (t) выражает только свойства самой среды. Вывод: на первых тактах (при небольших t) итерационный процесс улучшает качество поиска, но при дальнейших итерациях качество поиска ухудшается, поскольку результаты перестают зависеть от запроса пользователя. Матричная модель

Информационно-поисковые системы. Сычев А.В г.47 Корректировка модели: A (0) = C * Q (0) Q (1) = C T * A (0) +Q (0) A (1) = C * Q (1) …………………….. A (t) = C * Q (t) Q (t+1) = C T * A (t) +Q (0) Матричная модель

Информационно-поисковые системы. Сычев А.В г.48 Можно показать, что при достаточно больших значениях t матрицы Q и A являются решением системы уравнений: A = CQ Q = C T A+Q (0) или в матричном виде: Матричная модель

Информационно-поисковые системы. Сычев А.В г.49 Энтропийная модель - Коэффициент релевантности запросу - Коэффициент полноты поиска - Коэффициент выдачи

Информационно-поисковые системы. Сычев А.В г.50 - Коэффициент специфичности - Коэффициент точности Энтропийная модель

Информационно-поисковые системы. Сычев А.В г.51 Энтропийная модель

Информационно-поисковые системы. Сычев А.В г.52 Энтропийная модель Коэфф. относит. уменьшения исходной неопределенности

Информационно-поисковые системы. Сычев А.В г.53 Аветисян Р.Д., Аветисян Д.О. Теоретические основы информатики. М.: РГГУ, S.E.Robertson, K.S.Jones Simple, proven approaches to text retrieval. Cambridge Technical Report, S.E.Robertson, K.S.Jones Simple, proven approaches to text retrieval. Cambridge Technical Report, 1997 Ray Larson Principles of Information Retrieval. Слайды ( / ) / D.Carmel, A.Soffer Information Retrieval. Слайды. ( Источники