Задачи
<<  Проблема поиска корней многочленов Методы распределённых вычислений на основе модели потока данных. Прототип системы  >>
Теоретико-множественная модель
Теоретико-множественная модель
Векторная модель
Векторная модель
Векторная модель
Векторная модель
Принцип Луна (Luhn)
Принцип Луна (Luhn)
Картинки из презентации «Математические модели документального поиска» к уроку математики на тему «Задачи»

Автор: Alex. Чтобы познакомиться с картинкой полного размера, нажмите на её эскиз. Чтобы можно было использовать все картинки для урока математики, скачайте бесплатно презентацию «Математические модели документального поиска.ppt» со всеми картинками в zip-архиве размером 359 КБ.

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

содержание презентации «Математические модели документального поиска.ppt»
Сл Текст Сл Текст
1Математические модели документального 26Вероятностные модели: правило принятия
поиска. Воронежский государственный решения. Вероятность вычисляется на основе
университет Факультет компьютерных наук теоремы Байеса: P(R) – вероятность того,
Кафедра информационных систем. что случайно выбранный из коллекции
Информационно-поисковые системы. Сычев документ D является релевантным P(d|R) –
А.В. 2006 г. 1. вероятность случайного выбора документа d
2Обобщенное описание модели из множества релевантных документов P(d) –
документального поиска. Задается в виде вероятность случайного выбора документа d
кортежа <D, Q, F, R(d,q)>, где D – из коллекции D. Информационно-поисковые
множество представлений документа Q – системы. Сычев А.В. 2006 г. 26.
множество представлений информационной 27Вероятностные модели: правило принятия
потребности (запроса) F – средства решения. Решающее правило заключается в
моделирования представлений документа, максимизации следующей функции:
запросов и их отношений R(d,q) – функция Информационно-поисковые системы. Сычев
ранжирования Ставит в соответствие d из D А.В. 2006 г. 27.
и q из Q вещественные числа Определяет 28Вероятностные модели: правило принятия
порядок на множестве документов решения. В предположении о независимости
относительно запроса q. терминов друг от друга: di – бинарная
Информационно-поисковые системы. Сычев величина, указывающая на наличие либо
А.В. 2006 г. 2. отсутствие термина ti в документе d.
3Математические модели документального Информационно-поисковые системы. Сычев
поиска. Теоретико-множественные А.В. 2006 г. 28.
(булевская, нечеткие множества, 29Вероятностные модели: правило принятия
расширенная булевская) Вероятностные (сети решения. Вводя обозначения: получим:
вывода, энтропийная и др.) Алгебраические Информационно-поисковые системы. Сычев
(векторная, матричная и др.). А.В. 2006 г. 29.
Информационно-поисковые системы. Сычев 30Вероятностные модели: правило принятия
А.В. 2006 г. 3. решения. В итоге: или после
4Теоретико-множественная модель. логарифмирования: Информационно-поисковые
Множество всех документов в системе. - системы. Сычев А.В. 2006 г. 30.
Подмножество нерелевантных документов. - 31Вероятностные модели: правило принятия
Подмножество автоматно-релевантных решения. C – константа, не зависящая от
документов. - Подмножество документов ci – вес релевантности термина,
автоматно-нерелевантных документов. - показывающий дискриминантную способность
Подмножество документов, соответствующих между релевантными и нерелевантными
заданной информационной потребности документами термина ti. Проблема: оценка
пользователя (релевантных). вероятностей pt и qt.
Информационно-поисковые системы. Сычев Информационно-поисковые системы. Сычев
А.В. 2006 г. 4. А.В. 2006 г. 31.
5Теоретико-множественная модель. - 32Оценка вероятности на основе обратной
Подмножество релевантных документов, связи по релевантности
оказавшихся в выдаче. - Подмножество (Robertson&Jones). Если пользователь
нерелевантных документов, оказавшихся в предоставляет информацию об оценке
выдаче. - Подмножество релевантных релевантности полученных им документов
документов, не оказавшихся в выдаче. - (обратная связь) в виде R – числа
Подмножество нерелевантных документов, не релевантных документов и r – число
оказавшихся в выдаче. релевантных документов, содержащих термин
Информационно-поисковые системы. Сычев t N – общее число документов выданных
А.В. 2006 г. 5. пользователю n - число документов,
6Теоретико-множественная модель. содержащих термин t , то можно получить
Информационно-поисковые системы. Сычев следующие оценки: pt = r/R qt =
А.В. 2006 г. 6. (n-r)/(N-r). Информационно-поисковые
7Теоретико-множественная модель. B = c системы. Сычев А.В. 2006 г. 32.
= 0: идеальное качество поиска. 33Оценка вероятности на основе обратной
Информационно-поисковые системы. Сычев связи по релевантности (Robertson &
А.В. 2006 г. 7. Spark Jones). r. n-r. n. R-r. N-n-R+r.
8Метрики подобия. - простое N-n. R. N-R. N. Релевантные.
соответствие - коэффициент Дайса (Dice) - Нерелевантные. Всего. Содержат t. Не
коэффициент Жаккарда (Jaccard) - содержат t. Всего. Информационно-поисковые
косинусный коэффициент - коэффициент системы. Сычев А.В. 2006 г. 33.
перекрытия где Q и D – множества терминов 34Оценка вероятности на основе обратной
в запросе и документе соответственно. связи по релевантности (Robertson &
Информационно-поисковые системы. Сычев Spark Jones). Оценка веса релевантности
А.В. 2006 г. 8. термина: Проблема: высокая затратность
9Булевская модель. Самая простая оценки Большинство систем используют
модель, основанная на теории множеств формулу “Okapi BM25”, учитывающую веса
Запросы представляются в виде булевских Робертсона-Спарка Джонса. Логистическая
выражений из слов и логических операторов регрессия. Информационно-поисковые
И, ИЛИ, НЕ. Релевантными считаются системы. Сычев А.В. 2006 г. 34.
документы, которые удовлетворяют 35Пример (1). Имеется 20 документов
булевскому выражению в запросе. оцениваемых по 2 терминам: D = (d1, d2).
Информационно-поисковые системы. Сычев Отсюда: N = 20; R = 12; r1 = 8; r2 = 7; n1
А.В. 2006 г. 9. = 11; n2 = 11. Информационно-поисковые
10Булевская модель. Матрица системы. Сычев А.В. 2006 г. 35.
документ-термин C(d,t) показывает какие 36Пример (2). p1 = 8/12; p2 = 7/12; q1 =
встречаются слова и в каких документах. 3/8; q2 = 4/8; c1 = 1.2; c2 = 0.34; S(D) =
C(d,t). 1. 0. 0. 1. 1. 0. 1. 0. 1. 0. 1. 1.2*d1+0.34*d2. Информационно-поисковые
0. 1. 1. 1. Запрос: q = a И (b ИЛИ (НЕ системы. Сычев А.В. 2006 г. 36.
c)). Информационно-поисковые системы. 37Вероятностные модели: достоинства и
Сычев А.В. 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Расширенная булевская модель. Взамен описывается только терминами Оптимальные
бинарных величин термины в документах и результаты получаются только в процессе
запросах описываются весовыми обучения на основе информации о
коэффициентами (значимость или релевантности. Информационно-поисковые
статистическая оценка) Используется системы. Сычев А.В. 2006 г. 37.
аппарат нечетких множеств, т.е. степень 38Матричная модель. Рассматривает
принадлежности элемента к множеству множество из n документов. На его основе
задается величиной из интервала [0,1]. можно построить множество из m терминов,
Степень принадлежности элементов может которые хоть раз встречались в каком-либо
использоваться для ранжирования или более документах. Можно ввести матрицы
результатов запроса. сопряженности трех типов:
Информационно-поисковые системы. Сычев “документ-документ” “термин-термин”
А.В. 2006 г. 12. “документ-термин”. Информационно-поисковые
13Булевские модели: достоинства и системы. Сычев А.В. 2006 г. 38.
недостатки. Достоинства: простая, легко 39Матричная модель.
понимаемая структура запроса простота Информационно-поисковые системы. Сычев
реализации Недостатки: недостаточно А.В. 2006 г. 39.
возможностей для описания сложных запросов 40Матричная модель. Матрица
результатов запроса либо слишком много сопряженности “документ-документ”
либо слишком мало проблематичность при размерностью (n x n) Элемент d[i,j]
ранжирования результатов Пока еще указывает на наличие терминов содержащихся
распространены в коммерческих ИПС. одновременно в j-м и i-м документах
Информационно-поисковые системы. Сычев (бинарный случай), либо равен количеству
А.В. 2006 г. 13. общих терминов в этих документах.
14Альтернативные модели. Требуется Информационно-поисковые системы. Сычев
метрика для описания подобия между А.В. 2006 г. 40.
запросом и документом. Для этого 41Матричная модель. Матрица
необходимо привлекать характеристики сопряженности “термин-термин” размерностью
документов и запроса. Можно предположить, (m x m) Элемент t[i,j] указывает на
что лингвистическое подобие документа и наличие документов содержащих одновременно
запроса подразумевает тематическое j-й и i-й термины (бинарный случай), либо
подобие, т.е. выражает фактически равен количеству таких документов.
релевантность документа. Информационно-поисковые системы. Сычев
Информационно-поисковые системы. Сычев А.В. 2006 г. 41.
А.В. 2006 г. 14. 42Матричная модель. Запрос пользователя
15Векторная модель. Документы и запросы можно представить в виде: n-мерного
представляются в виде векторов в N-мерном вектора-строки Q[qi] , i-ая координата
евклидовом пространстве Компоненты вектора которого не равна нулю в том случае, если
соответствуют N терминам, образующим i-ый документ включен пользователем в
пространство. Информационно-поисковые список документов, представляющих его
системы. Сычев А.В. 2006 г. 15. запрос m-мерного вектора-столбца Q[qi],
16Векторная модель. Релевантность i-ая координата которого равна единице,
выражается через подобие векторов Для если i-ый термин включен пользователем в
вычисления подобия векторов используется список терминов, представляющий его
косинусная метрика. запрос. Информационно-поисковые системы.
Информационно-поисковые системы. Сычев Сычев А.В. 2006 г. 42.
А.В. 2006 г. 16. 43Матричная модель. Реакция системы
17Векторная модель. Для построения (вектор релевантностей) на запрос
пространства терминов обычно используются пользователя Q вычисляется как: A = C*Q
основы слов, отдельные слова, а также Значение i-ой координаты n-мерного вектора
целые фразы, пары слов и т.д. Документы и A[ai] при этом оказывается равным числу
запросы представляются в виде векторов, терминов запроса (бинарный случай),
компоненты которых соответствуют весам оказавшихся в i-ом документе.
терминов wt. Чем больше используется Информационно-поисковые системы. Сычев
терминов, тем сложнее понять какие А.В. 2006 г. 43.
подмножества слов являются общими для 44Матричная модель. Информационный поиск
подобных документов. описывается в виде итерационного процесса:
Информационно-поисковые системы. Сычев A(0) = C*Q(0) Q(1) = CT*A(0) A(1) = C*Q(1)
А.В. 2006 г. 17. …………………….. A(t) = C*Q(t) Q(t+1) = CT*A(t)
18Векторная модель. Ключевые вопросы: Элементы Q(i), i>0, рассматриваются как
Как выбирать размерность пространства уточненные величины значимостей терминов в
терминов N ? Как вычислять весовые запросе. Информационно-поисковые системы.
коэффициенты wt ? Информационно-поисковые Сычев А.В. 2006 г. 44.
системы. Сычев А.В. 2006 г. 18. 45Матричная модель. Можно заметить, что
19Закон Ципфа (Zipf). Произведение Q(t) = (CTС)tQ(0) A(t) = (CCT)t*A(0) Из
частоты термина f на его ранг r остается теоремы Сильвестра при достаточно больших
примерно постоянной величиной. f = C/r, C t можно получить приближение: Q(t+1) =
? N/10. Информационно-поисковые системы. ?0Q(t) A(t+1) = ?0A(t) где ?0 –
Сычев А.В. 2006 г. 19. собственное значение матрицы CTС.
20Принцип Луна (Luhn). Самые часто Информационно-поисковые системы. Сычев
встречающиеся слова – не самые значимые! А.В. 2006 г. 45.
Информационно-поисковые системы. Сычев 46Матричная модель. Видно, что с
А.В. 2006 г. 20. увеличением t векторы Q(t) и A(t)
21Расчет весов терминов. Бинарные веса: стремятся принимать направления
Wij=1 если документ di содержит термин tj, собственных векторов матриц CTС и СCT,
иначе 0. Частота термина tfij , т.е. соответствующих собственным значениям этих
сколько раз встретился термин tj в матриц. Т.е. если вектор Q(0) не учитывает
документе di tf x idf: чем выше частота фактор поисковой среды, то уже начиная с
термина в документе – тем выше его вес, но Q(1) этот фактор учитывается. При больших
термин должен не часто встречаться во всей значениях t вектор Q(t) выражает только
коллекции документов. свойства самой среды. Вывод: на первых
Информационно-поисковые системы. Сычев тактах (при небольших t) итерационный
А.В. 2006 г. 21. процесс улучшает качество поиска, но при
22Расчет tf x idf. tfik – частота дальнейших итерациях качество поиска
термина Tk в документе Di idfk – обратная ухудшается, поскольку результаты перестают
документальная частота для термина Tk в зависеть от запроса пользователя.
коллекции С N – общее число документов в Информационно-поисковые системы. Сычев
коллекции Nk - количество документов в А.В. 2006 г. 46.
коллекции C, содержащих термин Tk. 47Матричная модель. Корректировка
Информационно-поисковые системы. Сычев модели: A(0) = C*Q(0) Q(1) = CT*A(0)+Q(0)
А.В. 2006 г. 22. A(1) = C*Q(1) …………………….. A(t) = C*Q(t)
23Векторная модель. Достоинства: Учет Q(t+1) = CT*A(t) +Q(0).
весов повышает эффективность поиска Информационно-поисковые системы. Сычев
Позволяет оценить степень соответствия А.В. 2006 г. 47.
документа запросу Косинусная метрика 48Матричная модель. Можно показать, что
удобна при ранжировании Проблемы: Нет при достаточно больших значениях t матрицы
достаточного теоретического обоснования Q и A являются решением системы уравнений:
для построения пространства терминов A = CQ Q = CTA+Q(0) или в матричном виде:
Поскольку термины не являются независимыми Информационно-поисковые системы. Сычев
друг от друга, то они не могут быть А.В. 2006 г. 48.
полностью ортогональными Имеет 49Энтропийная модель. Коэффициент
преимущество перед другими моделями ввиду релевантности запросу. - Коэффициент
простоты и изящества. выдачи. - Коэффициент полноты поиска.
Информационно-поисковые системы. Сычев Информационно-поисковые системы. Сычев
А.В. 2006 г. 23. А.В. 2006 г. 49.
24Вероятностные модели. Заключаются в 50Энтропийная модель. - Коэффициент
оценке вероятности того, что документ d специфичности. - Коэффициент точности.
является релевантным по отношению к Информационно-поисковые системы. Сычев
запросу q: Pr(R|d,q). При ранжировании А.В. 2006 г. 50.
документов в выборке ключевым являет 51Энтропийная модель.
Принцип Ранжирования Вероятностей, Информационно-поисковые системы. Сычев
согласно которому если каждый ответ А.В. 2006 г. 51.
поисковой системы представляет собой 52Энтропийная модель. - Коэфф. относит.
ранжированный по убыванию вероятности уменьшения исходной неопределенности. 1.
полезности для пользователя список 2. 3. Информационно-поисковые системы.
документов, то общая эффективность системы Сычев А.В. 2006 г. 52.
для пользователей будет наилучшей. 53Источники. Аветисян Р.Д., Аветисян
Информационно-поисковые системы. Сычев Д.О. Теоретические основы информатики. М.:
А.В. 2006 г. 24. РГГУ, 1997. S.E.Robertson, K.S.Jones
25Вероятностные модели: определения. Simple, proven approaches to text
Релевантность R определяется как retrieval. Cambridge Technical Report,
отношение: – вероятности того, что d – 1997. Ray Larson “Principles of
релевантный и не релевантный Information Retrieval”. Слайды
соответственно Допущения: Структура (http://www.sims.berkeley.edu/academics/co
документа описывается бинарным вектором в rses/is240/s06/) D.Carmel, A.Soffer
пространстве терминов Релевантность “Information Retrieval”. Слайды.
документа запросу оценивается независимо (http://cs.haifa.ac.il/courses/infor/).
от других документов. Информационно-поисковые системы. Сычев
Информационно-поисковые системы. Сычев А.В. 2006 г. 53.
А.В. 2006 г. 25.
Математические модели документального поиска.ppt
http://900igr.net/kartinka/matematika/matematicheskie-modeli-dokumentalnogo-poiska-119969.html
cсылка на страницу

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

другие презентации на тему «Математические модели документального поиска»

«Математические загадки» - Только стружки белели. Не поставишь комарят наших в ряд. Сколько было сестренок? Посадила бабка в печь Пирожки с капустой печь. Математические загадки. Отгадка. Помогали мне братья. Пять первых связок изучи — Найдешь к решению ключи! Да в печи четыре штуки, Пироги считают внуки. Насчитала Комариха сорок пар, А продолжил счет сам Комар.

«Математический парадокс» - Вы верите в Бога, в судьбу? Математические парадоксы. Парадокс №5 «Разность квадратов». Есть возражения? «То, что я утверждаю сейчас — ложно», или «Данное высказывание — ложь». Как по-вашему, темнота существует? Парадокс №3 «Закономерность». Свет можно измерить, а темноту нет. И цепочка рассуждений возвращается в начало.

«Математический турнир» - Результаты игры. Луч 1. Задание 5 луч 2. Задание 4 луч 3. Задание 4 луч 1. Задание 2 луч 2. Задание 5 луч 3. Луч 3. Задание 1 луч 1. Дидактическая игра. Луч 2. Задание 3 луч 3. Задание 1 луч 2. "Математический турнир".

«Математические ребусы» - Последний ребус. Конус. Вектор. Касательная. Пирамида. Медиана. Назад. Хорда. Апофема. Аксиома. Гипотенуза. Математические ребусы.

«Математическое образование» - Развить существующую систему математического образования. Я думаю, что реформаторы пойдут дальше и сделают тест единым с 1 по 11 класс. Формализация прекрасно настраивает детей на решение определенного класса задач. Ушел устный счет. Сам материал дает возможность научить ребенка интеллектуально работать.

«Математическая модель» - Тест. Проведение математического исследования. Сбор данных. Математическая модель Исходные данные Приближенный метод Погрешности вычислений. Прогноз. Систематизация. При решении научно-технических задач в основном используются вещественные числа. Понятие погрешности. Источники погрешности решения. Предельная погрешность.

Задачи

45 презентаций о задачах
Урок

Математика

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