Задачи
<<  Проблема поиска корней многочленов Методы распределённых вычислений на основе модели потока данных. Прототип системы  >>
Математические модели документального поиска
Математические модели документального поиска
Обобщенное описание модели документального поиска
Обобщенное описание модели документального поиска
Математические модели документального поиска
Математические модели документального поиска
Теоретико-множественная модель
Теоретико-множественная модель
Теоретико-множественная модель
Теоретико-множественная модель
Теоретико-множественная модель
Теоретико-множественная модель
Теоретико-множественная модель
Теоретико-множественная модель
Метрики подобия
Метрики подобия
Булевская модель
Булевская модель
Булевская модель
Булевская модель
Булевская модель
Булевская модель
Расширенная булевская модель
Расширенная булевская модель
Булевские модели: достоинства и недостатки
Булевские модели: достоинства и недостатки
Альтернативные модели
Альтернативные модели
Векторная модель
Векторная модель
Векторная модель
Векторная модель
Векторная модель
Векторная модель
Векторная модель
Векторная модель
Закон Ципфа (Zipf)
Закон Ципфа (Zipf)
Принцип Луна (Luhn)
Принцип Луна (Luhn)
Расчет весов терминов
Расчет весов терминов
Расчет tf x idf
Расчет tf x idf
Векторная модель
Векторная модель
Вероятностные модели
Вероятностные модели
Вероятностные модели: определения
Вероятностные модели: определения
Вероятностные модели: правило принятия решения
Вероятностные модели: правило принятия решения
Вероятностные модели: правило принятия решения
Вероятностные модели: правило принятия решения
Вероятностные модели: правило принятия решения
Вероятностные модели: правило принятия решения
Вероятностные модели: правило принятия решения
Вероятностные модели: правило принятия решения
Вероятностные модели: правило принятия решения
Вероятностные модели: правило принятия решения
Вероятностные модели: правило принятия решения
Вероятностные модели: правило принятия решения
Оценка вероятности на основе обратной связи по релевантности
Оценка вероятности на основе обратной связи по релевантности
Оценка вероятности на основе обратной связи по релевантности
Оценка вероятности на основе обратной связи по релевантности
Оценка вероятности на основе обратной связи по релевантности
Оценка вероятности на основе обратной связи по релевантности
Пример (1)
Пример (1)
Пример (2)
Пример (2)
Вероятностные модели: достоинства и недостатки
Вероятностные модели: достоинства и недостатки
Матричная модель
Матричная модель
Матричная модель
Матричная модель
Матричная модель
Матричная модель
Матричная модель
Матричная модель
Матричная модель
Матричная модель
Матричная модель
Матричная модель
Матричная модель
Матричная модель
Матричная модель
Матричная модель
Матричная модель
Матричная модель
Матричная модель
Матричная модель
Матричная модель
Матричная модель
Энтропийная модель
Энтропийная модель
Энтропийная модель
Энтропийная модель
Энтропийная модель
Энтропийная модель
Энтропийная модель
Энтропийная модель
Источники
Источники

Презентация: «Математические модели документального поиска». Автор: Alex. Файл: «Математические модели документального поиска.ppt». Размер zip-архива: 359 КБ.

Математические модели документального поиска

содержание презентации «Математические модели документального поиска.ppt»
СлайдТекст
1 Математические модели документального поиска

Математические модели документального поиска

Воронежский государственный университет Факультет компьютерных наук Кафедра информационных систем

Информационно-поисковые системы. Сычев А.В. 2006 г.

1

2 Обобщенное описание модели документального поиска

Обобщенное описание модели документального поиска

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

Информационно-поисковые системы. Сычев А.В. 2006 г.

2

3 Математические модели документального поиска

Математические модели документального поиска

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

Информационно-поисковые системы. Сычев А.В. 2006 г.

3

4 Теоретико-множественная модель

Теоретико-множественная модель

Множество всех документов в системе

- Подмножество нерелевантных документов

- Подмножество автоматно-релевантных документов

- Подмножество автоматно-нерелевантных документов

- Подмножество документов, соответствующих заданной информационной потребности пользователя (релевантных)

Информационно-поисковые системы. Сычев А.В. 2006 г.

4

5 Теоретико-множественная модель

Теоретико-множественная модель

- Подмножество релевантных документов, оказавшихся в выдаче

- Подмножество нерелевантных документов, оказавшихся в выдаче

- Подмножество релевантных документов, не оказавшихся в выдаче

- Подмножество нерелевантных документов, не оказавшихся в выдаче

Информационно-поисковые системы. Сычев А.В. 2006 г.

5

6 Теоретико-множественная модель

Теоретико-множественная модель

Информационно-поисковые системы. Сычев А.В. 2006 г.

6

7 Теоретико-множественная модель

Теоретико-множественная модель

B = c = 0: идеальное качество поиска

Информационно-поисковые системы. Сычев А.В. 2006 г.

7

8 Метрики подобия

Метрики подобия

- простое соответствие - коэффициент Дайса (Dice) - коэффициент Жаккарда (Jaccard) - косинусный коэффициент - коэффициент перекрытия где Q и D – множества терминов в запросе и документе соответственно

Информационно-поисковые системы. Сычев А.В. 2006 г.

8

9 Булевская модель

Булевская модель

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

Информационно-поисковые системы. Сычев А.В. 2006 г.

9

10 Булевская модель

Булевская модель

Матрица документ-термин C(d,t) показывает какие встречаются слова и в каких документах

C(d,t)

1

0

0

1

1

0

1

0

1

0

1

0

1

1

1

Запрос: q = a И (b ИЛИ (НЕ c))

Информационно-поисковые системы. Сычев А.В. 2006 г.

10

11 Булевская модель

Булевская модель

A -> 1,1,1,0,1 b -> 0,1,0,1,1 НЕ c -> 1,1,0,1,0

Запрос: q = a И (b ИЛИ (НЕ c)) Результат: d1, d2, d5

И 1,1,0,0,1

Или 1,1,0,1,1

Информационно-поисковые системы. Сычев А.В. 2006 г.

11

12 Расширенная булевская модель

Расширенная булевская модель

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

Информационно-поисковые системы. Сычев А.В. 2006 г.

12

13 Булевские модели: достоинства и недостатки

Булевские модели: достоинства и недостатки

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

Информационно-поисковые системы. Сычев А.В. 2006 г.

13

14 Альтернативные модели

Альтернативные модели

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

Информационно-поисковые системы. Сычев А.В. 2006 г.

14

15 Векторная модель

Векторная модель

Документы и запросы представляются в виде векторов в N-мерном евклидовом пространстве Компоненты вектора соответствуют N терминам, образующим пространство.

Информационно-поисковые системы. Сычев А.В. 2006 г.

15

16 Векторная модель

Векторная модель

Релевантность выражается через подобие векторов Для вычисления подобия векторов используется косинусная метрика

Информационно-поисковые системы. Сычев А.В. 2006 г.

16

17 Векторная модель

Векторная модель

Для построения пространства терминов обычно используются основы слов, отдельные слова, а также целые фразы, пары слов и т.д. Документы и запросы представляются в виде векторов, компоненты которых соответствуют весам терминов wt. Чем больше используется терминов, тем сложнее понять какие подмножества слов являются общими для подобных документов.

Информационно-поисковые системы. Сычев А.В. 2006 г.

17

18 Векторная модель

Векторная модель

Ключевые вопросы: Как выбирать размерность пространства терминов N ? Как вычислять весовые коэффициенты wt ?

Информационно-поисковые системы. Сычев А.В. 2006 г.

18

19 Закон Ципфа (Zipf)

Закон Ципфа (Zipf)

Произведение частоты термина f на его ранг r остается примерно постоянной величиной

f = C/r, C ? N/10

Информационно-поисковые системы. Сычев А.В. 2006 г.

19

20 Принцип Луна (Luhn)

Принцип Луна (Luhn)

Самые часто встречающиеся слова – не самые значимые!

Информационно-поисковые системы. Сычев А.В. 2006 г.

20

21 Расчет весов терминов

Расчет весов терминов

Бинарные веса: Wij=1 если документ di содержит термин tj, иначе 0. Частота термина tfij , т.е. сколько раз встретился термин tj в документе di tf x idf: чем выше частота термина в документе – тем выше его вес, но термин должен не часто встречаться во всей коллекции документов

Информационно-поисковые системы. Сычев А.В. 2006 г.

21

22 Расчет tf x idf

Расчет tf x idf

tfik – частота термина Tk в документе Di idfk – обратная документальная частота для термина Tk в коллекции С N – общее число документов в коллекции Nk - количество документов в коллекции C, содержащих термин Tk

Информационно-поисковые системы. Сычев А.В. 2006 г.

22

23 Векторная модель

Векторная модель

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

Информационно-поисковые системы. Сычев А.В. 2006 г.

23

24 Вероятностные модели

Вероятностные модели

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

Информационно-поисковые системы. Сычев А.В. 2006 г.

24

25 Вероятностные модели: определения

Вероятностные модели: определения

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

Информационно-поисковые системы. Сычев А.В. 2006 г.

25

26 Вероятностные модели: правило принятия решения

Вероятностные модели: правило принятия решения

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

Информационно-поисковые системы. Сычев А.В. 2006 г.

26

27 Вероятностные модели: правило принятия решения

Вероятностные модели: правило принятия решения

Решающее правило заключается в максимизации следующей функции:

Информационно-поисковые системы. Сычев А.В. 2006 г.

27

28 Вероятностные модели: правило принятия решения

Вероятностные модели: правило принятия решения

В предположении о независимости терминов друг от друга: di – бинарная величина, указывающая на наличие либо отсутствие термина ti в документе d

Информационно-поисковые системы. Сычев А.В. 2006 г.

28

29 Вероятностные модели: правило принятия решения

Вероятностные модели: правило принятия решения

Вводя обозначения: получим:

Информационно-поисковые системы. Сычев А.В. 2006 г.

29

30 Вероятностные модели: правило принятия решения

Вероятностные модели: правило принятия решения

В итоге: или после логарифмирования:

Информационно-поисковые системы. Сычев А.В. 2006 г.

30

31 Вероятностные модели: правило принятия решения

Вероятностные модели: правило принятия решения

C – константа, не зависящая от документов ci – вес релевантности термина, показывающий дискриминантную способность между релевантными и нерелевантными документами термина ti. Проблема: оценка вероятностей pt и qt

Информационно-поисковые системы. Сычев А.В. 2006 г.

31

32 Оценка вероятности на основе обратной связи по релевантности

Оценка вероятности на основе обратной связи по релевантности

(Robertson&Jones)

Если пользователь предоставляет информацию об оценке релевантности полученных им документов (обратная связь) в виде R – числа релевантных документов и r – число релевантных документов, содержащих термин t N – общее число документов выданных пользователю n - число документов, содержащих термин t , то можно получить следующие оценки: pt = r/R qt = (n-r)/(N-r)

Информационно-поисковые системы. Сычев А.В. 2006 г.

32

33 Оценка вероятности на основе обратной связи по релевантности

Оценка вероятности на основе обратной связи по релевантности

(Robertson & Spark Jones)

r

n-r

n

R-r

N-n-R+r

N-n

R

N-R

N

Релевантные

Нерелевантные

Всего

Содержат t

Не содержат t

Всего

Информационно-поисковые системы. Сычев А.В. 2006 г.

33

34 Оценка вероятности на основе обратной связи по релевантности

Оценка вероятности на основе обратной связи по релевантности

(Robertson & Spark Jones)

Оценка веса релевантности термина: Проблема: высокая затратность оценки Большинство систем используют формулу “Okapi BM25”, учитывающую веса Робертсона-Спарка Джонса. Логистическая регрессия

Информационно-поисковые системы. Сычев А.В. 2006 г.

34

35 Пример (1)

Пример (1)

Имеется 20 документов оцениваемых по 2 терминам: D = (d1, d2)

Отсюда: N = 20; R = 12; r1 = 8; r2 = 7; n1 = 11; n2 = 11

Информационно-поисковые системы. Сычев А.В. 2006 г.

35

36 Пример (2)

Пример (2)

p1 = 8/12; p2 = 7/12; q1 = 3/8; q2 = 4/8; c1 = 1.2; c2 = 0.34; S(D) = 1.2*d1+0.34*d2

Информационно-поисковые системы. Сычев А.В. 2006 г.

36

37 Вероятностные модели: достоинства и недостатки

Вероятностные модели: достоинства и недостатки

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

Информационно-поисковые системы. Сычев А.В. 2006 г.

37

38 Матричная модель

Матричная модель

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

Информационно-поисковые системы. Сычев А.В. 2006 г.

38

39 Матричная модель

Матричная модель

Информационно-поисковые системы. Сычев А.В. 2006 г.

39

40 Матричная модель

Матричная модель

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

Информационно-поисковые системы. Сычев А.В. 2006 г.

40

41 Матричная модель

Матричная модель

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

Информационно-поисковые системы. Сычев А.В. 2006 г.

41

42 Матричная модель

Матричная модель

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

Информационно-поисковые системы. Сычев А.В. 2006 г.

42

43 Матричная модель

Матричная модель

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

Информационно-поисковые системы. Сычев А.В. 2006 г.

43

44 Матричная модель

Матричная модель

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

Информационно-поисковые системы. Сычев А.В. 2006 г.

44

45 Матричная модель

Матричная модель

Можно заметить, что Q(t) = (CTС)tQ(0) A(t) = (CCT)t*A(0) Из теоремы Сильвестра при достаточно больших t можно получить приближение: Q(t+1) = ?0Q(t) A(t+1) = ?0A(t) где ?0 – собственное значение матрицы CTС.

Информационно-поисковые системы. Сычев А.В. 2006 г.

45

46 Матричная модель

Матричная модель

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

Информационно-поисковые системы. Сычев А.В. 2006 г.

46

47 Матричная модель

Матричная модель

Корректировка модели: A(0) = C*Q(0) Q(1) = CT*A(0)+Q(0) A(1) = C*Q(1) …………………….. A(t) = C*Q(t) Q(t+1) = CT*A(t) +Q(0)

Информационно-поисковые системы. Сычев А.В. 2006 г.

47

48 Матричная модель

Матричная модель

Можно показать, что при достаточно больших значениях t матрицы Q и A являются решением системы уравнений: A = CQ Q = CTA+Q(0) или в матричном виде:

Информационно-поисковые системы. Сычев А.В. 2006 г.

48

49 Энтропийная модель

Энтропийная модель

Коэффициент релевантности запросу

- Коэффициент выдачи

- Коэффициент полноты поиска

Информационно-поисковые системы. Сычев А.В. 2006 г.

49

50 Энтропийная модель

Энтропийная модель

- Коэффициент специфичности

- Коэффициент точности

Информационно-поисковые системы. Сычев А.В. 2006 г.

50

51 Энтропийная модель

Энтропийная модель

Информационно-поисковые системы. Сычев А.В. 2006 г.

51

52 Энтропийная модель

Энтропийная модель

- Коэфф. относит. уменьшения исходной неопределенности

1.

2.

3.

Информационно-поисковые системы. Сычев А.В. 2006 г.

52

53 Источники

Источники

Аветисян Р.Д., Аветисян Д.О. Теоретические основы информатики. М.: РГГУ, 1997. S.E.Robertson, K.S.Jones Simple, proven approaches to text retrieval. Cambridge Technical Report, 1997. Ray Larson “Principles of Information Retrieval”. Слайды (http://www.sims.berkeley.edu/academics/courses/is240/s06/) D.Carmel, A.Soffer “Information Retrieval”. Слайды. (http://cs.haifa.ac.il/courses/infor/)

Информационно-поисковые системы. Сычев А.В. 2006 г.

53

«Математические модели документального поиска»
http://900igr.net/prezentacija/matematika/matematicheskie-modeli-dokumentalnogo-poiska-119969.html
cсылка на страницу
Урок

Математика

71 тема
Слайды
900igr.net > Презентации по математике > Задачи > Математические модели документального поиска