🗊Методы поиска в структурированных файлах функции ранжирования

Категория: Авто/мото
Нажмите для полного просмотра!
Методы поиска в структурированных файлах  функции ранжирования, слайд №1Методы поиска в структурированных файлах  функции ранжирования, слайд №2Методы поиска в структурированных файлах  функции ранжирования, слайд №3Методы поиска в структурированных файлах  функции ранжирования, слайд №4Методы поиска в структурированных файлах  функции ранжирования, слайд №5Методы поиска в структурированных файлах  функции ранжирования, слайд №6Методы поиска в структурированных файлах  функции ранжирования, слайд №7Методы поиска в структурированных файлах  функции ранжирования, слайд №8Методы поиска в структурированных файлах  функции ранжирования, слайд №9Методы поиска в структурированных файлах  функции ранжирования, слайд №10Методы поиска в структурированных файлах  функции ранжирования, слайд №11Методы поиска в структурированных файлах  функции ранжирования, слайд №12Методы поиска в структурированных файлах  функции ранжирования, слайд №13Методы поиска в структурированных файлах  функции ранжирования, слайд №14Методы поиска в структурированных файлах  функции ранжирования, слайд №15Методы поиска в структурированных файлах  функции ранжирования, слайд №16Методы поиска в структурированных файлах  функции ранжирования, слайд №17Методы поиска в структурированных файлах  функции ранжирования, слайд №18Методы поиска в структурированных файлах  функции ранжирования, слайд №19Методы поиска в структурированных файлах  функции ранжирования, слайд №20Методы поиска в структурированных файлах  функции ранжирования, слайд №21Методы поиска в структурированных файлах  функции ранжирования, слайд №22Методы поиска в структурированных файлах  функции ранжирования, слайд №23Методы поиска в структурированных файлах  функции ранжирования, слайд №24Методы поиска в структурированных файлах  функции ранжирования, слайд №25Методы поиска в структурированных файлах  функции ранжирования, слайд №26Методы поиска в структурированных файлах  функции ранжирования, слайд №27Методы поиска в структурированных файлах  функции ранжирования, слайд №28Методы поиска в структурированных файлах  функции ранжирования, слайд №29Методы поиска в структурированных файлах  функции ранжирования, слайд №30Методы поиска в структурированных файлах  функции ранжирования, слайд №31Методы поиска в структурированных файлах  функции ранжирования, слайд №32Методы поиска в структурированных файлах  функции ранжирования, слайд №33Методы поиска в структурированных файлах  функции ранжирования, слайд №34Методы поиска в структурированных файлах  функции ранжирования, слайд №35Методы поиска в структурированных файлах  функции ранжирования, слайд №36

Содержание

Вы можете ознакомиться и скачать Методы поиска в структурированных файлах функции ранжирования. Презентация содержит 36 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации


Слайд 1





Методы поиска в структурированных файлах
функции ранжирования
Описание слайда:
Методы поиска в структурированных файлах функции ранжирования

Слайд 2





Содержание
Векторная модель
TF-IDF
Косинусная мера
Структурированный файл
на примере XML
Лексические поддеревья
Структурные термы
Расширение векторной модели на случай структурированных файлов
Схожесть контекстов
Okapi BM25
BM25F
BM25Е
Описание слайда:
Содержание Векторная модель TF-IDF Косинусная мера Структурированный файл на примере XML Лексические поддеревья Структурные термы Расширение векторной модели на случай структурированных файлов Схожесть контекстов Okapi BM25 BM25F BM25Е

Слайд 3





Векторная модель
Векторная модель (англ. vector space model) — представление коллекции документов векторами из одного общего для всей коллекции векторного пространства.
Коллекция - неупорядоченное множество документов.

Документ - неупорядоченное множество термов. 
Термы (словарные термы) - слова, из которых состоит текст (определение терма зависит от приложения)
В векторной модели термы – это измерения. 
	Вес терма – координата в данном измерении.
Описание слайда:
Векторная модель Векторная модель (англ. vector space model) — представление коллекции документов векторами из одного общего для всей коллекции векторного пространства. Коллекция - неупорядоченное множество документов. Документ - неупорядоченное множество термов. Термы (словарные термы) - слова, из которых состоит текст (определение терма зависит от приложения) В векторной модели термы – это измерения. Вес терма – координата в данном измерении.

Слайд 4





Векторная модель
Более формально
dj = (w1j, w2j, …, wnj), где 
	dj — векторное представление j-го документа, 
	wij — вес i-го терма в j-м документе, 
	n — общее количество различных термов во всех документах коллекции.
Запросы представляются в той же форме, что и документы. Т.е.
q = (w1q,w2q,...,wtq), где
	q – векторное представление запроса,
	wiq - вес i-го терма в запросе
Описание слайда:
Векторная модель Более формально dj = (w1j, w2j, …, wnj), где dj — векторное представление j-го документа, wij — вес i-го терма в j-м документе, n — общее количество различных термов во всех документах коллекции. Запросы представляются в той же форме, что и документы. Т.е. q = (w1q,w2q,...,wtq), где q – векторное представление запроса, wiq - вес i-го терма в запросе

Слайд 5





TF-IDF
TF-IDF (от англ. TF — term frequency, IDF — inverse document frequency) — статистическая мера, используемая для оценки важности слова в контексте документа, являющегося частью коллекции документов. TF-IDF = TF*IDF
	ni - число вхождений терма в документ
	k – общее число термов в документе
	|D| — количество документов в коллекции
	    — количество документов, в которых встречается терм ti 						(когда ni≠0)
Описание слайда:
TF-IDF TF-IDF (от англ. TF — term frequency, IDF — inverse document frequency) — статистическая мера, используемая для оценки важности слова в контексте документа, являющегося частью коллекции документов. TF-IDF = TF*IDF ni - число вхождений терма в документ k – общее число термов в документе |D| — количество документов в коллекции — количество документов, в которых встречается терм ti (когда ni≠0)

Слайд 6





Косинусная мера
Описание слайда:
Косинусная мера

Слайд 7





Косинусная мера




ρ(Q,D) – соответствие запроса Q документу D

ti – терм (измерение) 

wQ(ti) – вес терма ti в запросе Q

wD(ti) – вес терма ti в документе D
Описание слайда:
Косинусная мера ρ(Q,D) – соответствие запроса Q документу D ti – терм (измерение) wQ(ti) – вес терма ti в запросе Q wD(ti) – вес терма ti в документе D

Слайд 8





Структурированный файл
на примере XML*
<play>
<author>Shakespeare</author>
<title>Macbeth</title>
<act number="I">
<scene number="vii">
<title>Macbeth’s castle</title>
<verse>Will I with wine and wassail ...</verse>
</scene>
</act>
</play>
* Здесь и далее под структурированным
файлом подразумевается XML-файл
Описание слайда:
Структурированный файл на примере XML* <play> <author>Shakespeare</author> <title>Macbeth</title> <act number="I"> <scene number="vii"> <title>Macbeth’s castle</title> <verse>Will I with wine and wassail ...</verse> </scene> </act> </play> * Здесь и далее под структурированным файлом подразумевается XML-файл

Слайд 9





Лексические поддеревья
Деревья, содержащие хотя бы один словарный терм
Описание слайда:
Лексические поддеревья Деревья, содержащие хотя бы один словарный терм

Слайд 10





Лексические поддеревья
С увеличением количества узлов в дереве
растет число лексических поддеревьев.
Описание слайда:
Лексические поддеревья С увеличением количества узлов в дереве растет число лексических поддеревьев.

Слайд 11





Структурные термы
Будем рассматривать только такие лексические поддеревья, которые оканчиваются единственным словарным термом
Такие поддеревья называются структурными термами и обозначаются парой (t,c), где t – это терм, c - его XML-контекст.
Описание слайда:
Структурные термы Будем рассматривать только такие лексические поддеревья, которые оканчиваются единственным словарным термом Такие поддеревья называются структурными термами и обозначаются парой (t,c), где t – это терм, c - его XML-контекст.

Слайд 12





Расширение векторной модели на случай структурированных файлов
ρ(Q,D) – соответствие запроса Q документу D

(ti,c i) – структурный терм (измерение) 

wQ(ti,c i) – вес структурного терма (ti,c i) в запросе Q

wD(ti,c i) – вес структурного терма (ti,c i) в документе D
cr(ci,ck) – схожесть контекстов (context resemblance) ci и ck,  0≤cr(ci,ck) ≤1
Описание слайда:
Расширение векторной модели на случай структурированных файлов ρ(Q,D) – соответствие запроса Q документу D (ti,c i) – структурный терм (измерение) wQ(ti,c i) – вес структурного терма (ti,c i) в запросе Q wD(ti,c i) – вес структурного терма (ti,c i) в документе D cr(ci,ck) – схожесть контекстов (context resemblance) ci и ck, 0≤cr(ci,ck) ≤1

Слайд 13





Схожесть контекстов	 
1 способ
	|cq| -  число узлов в контексте, соответствующем терму из запроса
	|cd| -  то же, но для документа
Описание слайда:
Схожесть контекстов 1 способ |cq| - число узлов в контексте, соответствующем терму из запроса |cd| - то же, но для документа

Слайд 14





Схожесть контекстов	
2 способ
Рассмотрим запрос в форме <q1><q2><q3>T</q3></q2></q1>

Q = q1q2q3 – контекст появления Т в запросе
А = а1а2…а8 – контекст появления Т в произвольном XML документе

Пример:
Q = language/book/title
A = language/media/book/chapter/section/subsection/title/number
Описание слайда:
Схожесть контекстов 2 способ Рассмотрим запрос в форме <q1><q2><q3>T</q3></q2></q1> Q = q1q2q3 – контекст появления Т в запросе А = а1а2…а8 – контекст появления Т в произвольном XML документе Пример: Q = language/book/title A = language/media/book/chapter/section/subsection/title/number

Слайд 15





Схожесть контекстов	
LCS(Q,A)
Longest Common Subsequence
 
LCS(Q,A) =  lcs(Q,A)/|Q|, где

lcs(Q,A) – длина наибольшей общей подпоследовательности  Q и А 
0 ≤ LCS(Q,A) ≤ 1
Описание слайда:
Схожесть контекстов LCS(Q,A) Longest Common Subsequence LCS(Q,A) = lcs(Q,A)/|Q|, где lcs(Q,A) – длина наибольшей общей подпоследовательности Q и А 0 ≤ LCS(Q,A) ≤ 1

Слайд 16





Критерии оценки
Критерии оценки
Контекст А включает больше элементов qi в правильном порядке. (В примере - 3)
Элементы qi появляются ближе к началу А, чем к концу. (В примере – совпадение q1q2q3 с а1а3а7 предпочтительнее, чем с а1а3а8)
Элементы qi появляются в А ближе друг к другу. (В примере – совпадение q1q2q3 с а2а3а4 предпочтительнее, чем с а1а3а5)
Из двух контекстов документа, одинаково совпадающих с контекстом запроса, выше оценивается тот, который имеет меньшую длину.
Описание слайда:
Критерии оценки Критерии оценки Контекст А включает больше элементов qi в правильном порядке. (В примере - 3) Элементы qi появляются ближе к началу А, чем к концу. (В примере – совпадение q1q2q3 с а1а3а7 предпочтительнее, чем с а1а3а8) Элементы qi появляются в А ближе друг к другу. (В примере – совпадение q1q2q3 с а2а3а4 предпочтительнее, чем с а1а3а5) Из двух контекстов документа, одинаково совпадающих с контекстом запроса, выше оценивается тот, который имеет меньшую длину.

Слайд 17





Схожесть контекстов	
POS(Q,A) 

	POS(Q,A) = 1-((AP-AverOptimalPosition)/(|A|-2*AverOptimalPosition+1))
	AverOptimalPosition - среднее положение оптимального совпадения Q и А (если совпадение начинается с первого элемента и продолжается без пробелов)
	
	АР -  фактическое среднее положение совпадения Q и А 
	
	0 ≤ POS(Q,A) ≤ 1
	(0 – в случае полного несовпадения, 1 – в случае «самого левого» 
	совпадения)
Описание слайда:
Схожесть контекстов POS(Q,A) POS(Q,A) = 1-((AP-AverOptimalPosition)/(|A|-2*AverOptimalPosition+1)) AverOptimalPosition - среднее положение оптимального совпадения Q и А (если совпадение начинается с первого элемента и продолжается без пробелов) АР - фактическое среднее положение совпадения Q и А 0 ≤ POS(Q,A) ≤ 1 (0 – в случае полного несовпадения, 1 – в случае «самого левого» совпадения)

Слайд 18





Схожесть контекстов	
GAPS(Q,A)


GAPS(Q,A) =  gaps/(gaps + lcs(Q,A))

	
	gaps - число «пробелов» (в примере gaps = 4)
	
	0 ≤ GAPS ≤ 1 
	( 0 – полное совпадение)
Описание слайда:
Схожесть контекстов GAPS(Q,A) GAPS(Q,A) = gaps/(gaps + lcs(Q,A)) gaps - число «пробелов» (в примере gaps = 4) 0 ≤ GAPS ≤ 1 ( 0 – полное совпадение)

Слайд 19





Схожесть контекстов	
LD(Q,A)


LD(Q,A)=  (|A|- lcs(Q,A))/|A|
Описание слайда:
Схожесть контекстов LD(Q,A) LD(Q,A)= (|A|- lcs(Q,A))/|A|

Слайд 20





Схожесть контекстов	

cr(Q,A) = αLCS(Q,A) + βPOS(Q,A) – γGAPS(Q,A) – δLD(Q,A) 
0 ≤ α ≤ 1, 0 ≤ β ≤ 1, 0 ≤ γ ≤ 1, 0 ≤ δ ≤ 1
α + β = 1 (т.к. cr(Q,A) = 1 в случае полного совпадения)
Описание слайда:
Схожесть контекстов cr(Q,A) = αLCS(Q,A) + βPOS(Q,A) – γGAPS(Q,A) – δLD(Q,A) 0 ≤ α ≤ 1, 0 ≤ β ≤ 1, 0 ≤ γ ≤ 1, 0 ≤ δ ≤ 1 α + β = 1 (т.к. cr(Q,A) = 1 в случае полного совпадения)

Слайд 21





Примеры
	Показывают, как влияют оценки LCS(Q,A) , POS(Q,A), GAPS(Q,A), LD(Q,A) на cr(Q,A) 

	Q = q1q2q3 = book/chapter/title

	Положим α = 0.75, β = 0.25, γ = 0.25, δ = 0.2 	

	Для простоты будем рассматривать lcs(Q,A) вместо LCS(Q,A), 
	АР вместо POS, gaps	вместо GAPS, ld вместо LD
Описание слайда:
Примеры Показывают, как влияют оценки LCS(Q,A) , POS(Q,A), GAPS(Q,A), LD(Q,A) на cr(Q,A) Q = q1q2q3 = book/chapter/title Положим α = 0.75, β = 0.25, γ = 0.25, δ = 0.2 Для простоты будем рассматривать lcs(Q,A) вместо LCS(Q,A), АР вместо POS, gaps вместо GAPS, ld вместо LD

Слайд 22





Пример A1. Влияние lcs(Q,A) на cr(Q,A)
Описание слайда:
Пример A1. Влияние lcs(Q,A) на cr(Q,A)

Слайд 23





Пример A3. Влияние gaps(Q,A) на cr(Q,A)
Описание слайда:
Пример A3. Влияние gaps(Q,A) на cr(Q,A)

Слайд 24


Методы поиска в структурированных файлах  функции ранжирования, слайд №24
Описание слайда:

Слайд 25





Okapi BM25
	d - документ

	C – коллекция документов

	W(d,q,C) – релевантность документа d из коллекции С запросу q

	wj(d,C) – вес j-го терма в документе d коллекции С
	qj – совпадание терма j из документа с термом запроса
Описание слайда:
Okapi BM25 d - документ C – коллекция документов W(d,q,C) – релевантность документа d из коллекции С запросу q wj(d,C) – вес j-го терма в документе d коллекции С qj – совпадание терма j из документа с термом запроса

Слайд 26





Okapi BM25
	

	d - документ
	C – коллекция документов
	wj(d,C) – вес j-го терма в документе d коллекции С
	tfj – частота  j-го терма в документе d коллекции С (TF)
	dfj – количество документов коллекции, содержащих j-й терм 
	dl – длина документа
	avdl – средняя длина документов в коллекции
	k1, b – коэффициенты (обычно k1 = 2, b = 0.75)
Описание слайда:
Okapi BM25 d - документ C – коллекция документов wj(d,C) – вес j-го терма в документе d коллекции С tfj – частота j-го терма в документе d коллекции С (TF) dfj – количество документов коллекции, содержащих j-й терм dl – длина документа avdl – средняя длина документов в коллекции k1, b – коэффициенты (обычно k1 = 2, b = 0.75)

Слайд 27





BM25F
модификация BM25, в которой документ рассматривается как совокупность нескольких полей (таких как, например, заголовки, основной текст, ссылочный текст), длины которых независимо нормализуются, и каждому из которых может быть назначена своя степень значимости в итоговой функции ранжирования.
	
	
	tf’j – взвешенная частота  j-го терма в документе d
	dl’ – взвешенная длина документа
	avdl’ – взвешенная средняя длина документа
	 k’1 – взвешенный параметр
Описание слайда:
BM25F модификация BM25, в которой документ рассматривается как совокупность нескольких полей (таких как, например, заголовки, основной текст, ссылочный текст), длины которых независимо нормализуются, и каждому из которых может быть назначена своя степень значимости в итоговой функции ранжирования. tf’j – взвешенная частота j-го терма в документе d dl’ – взвешенная длина документа avdl’ – взвешенная средняя длина документа k’1 – взвешенный параметр

Слайд 28





BM25F
	Пусть имеется nF полей f = 1, …, nF
	В данном поле f документа d терм t имеет частоту tfd,t,f
	Пусть V – это словарь (набор термов). Тогда
	
	Длина поля f в документе d
	
	Частота терма t в документе d
Описание слайда:
BM25F Пусть имеется nF полей f = 1, …, nF В данном поле f документа d терм t имеет частоту tfd,t,f Пусть V – это словарь (набор термов). Тогда Длина поля f в документе d Частота терма t в документе d

Слайд 29





BM25F
	Пусть имеется nF полей f = 1, …, nF
	В данном поле f документа d терм t имеет частоту tfd,t,f
	Пусть V – это словарь (набор термов). Тогда
	
	Длина документа d
	Средняя длина документа
Описание слайда:
BM25F Пусть имеется nF полей f = 1, …, nF В данном поле f документа d терм t имеет частоту tfd,t,f Пусть V – это словарь (набор термов). Тогда Длина документа d Средняя длина документа

Слайд 30





BM25F
	Если считать, что полю f присвоен вес wf , получим:
	N – мощность коллекции
	atf – средняя частота терма
Описание слайда:
BM25F Если считать, что полю f присвоен вес wf , получим: N – мощность коллекции atf – средняя частота терма

Слайд 31





BM25E
В BM25F вместо частоты терма в документе используется линейная комбинация взвешенных частот терма в полях
Этот метод можно применить к поиску элементов.
Элементы можно обрабатывать так же, как и документы. Но каждый элемент может иметь ещё и дополнительные, унаследованные поля
Описание слайда:
BM25E В BM25F вместо частоты терма в документе используется линейная комбинация взвешенных частот терма в полях Этот метод можно применить к поиску элементов. Элементы можно обрабатывать так же, как и документы. Но каждый элемент может иметь ещё и дополнительные, унаследованные поля

Слайд 32





BM25E
	Пусть имеется nЕ элементов е = 1, …, nЕ в коллекции С
	В элементе е терм t  имеет частоту tfd,t,e 
	el – длина элемента
	avel – средняя длина элемента
	Тогда расширение ВМ25 на случай поиска элементов:
Описание слайда:
BM25E Пусть имеется nЕ элементов е = 1, …, nЕ в коллекции С В элементе е терм t имеет частоту tfd,t,e el – длина элемента avel – средняя длина элемента Тогда расширение ВМ25 на случай поиска элементов:

Слайд 33





ВМ25Е
	Соответственно, функция ВМ25Е:
	
	tf’e,j – взвешенная частота  j-го терма в элементе е
	еl’ – взвешенная длина элемента
	avеl’ – взвешенная средняя длина элемента в коллекции
	 k’1 – взвешенный параметр
Описание слайда:
ВМ25Е Соответственно, функция ВМ25Е: tf’e,j – взвешенная частота j-го терма в элементе е еl’ – взвешенная длина элемента avеl’ – взвешенная средняя длина элемента в коллекции k’1 – взвешенный параметр

Слайд 34





BM25E
	Соответственно,
M – мощность коллекции
atf – средняя частота терма
Описание слайда:
BM25E Соответственно, M – мощность коллекции atf – средняя частота терма

Слайд 35





Литература
Christopher D. Manning, Prabhakar Raghavan and Hinrich Schütze, Introduction to Information Retrieval, Cambridge University Press. 2008.
David Carmel, Nadav Efraty, Gad M. Landau, Yoelle S. Maarek, Yosi Mass, An Extension of the Vector Space Model for Querying XML Documents via XML Fragments, ACM SIGIR'2002 Workshop on XML and IR, Tampere, Finland , Aug 2002
Wei Lu, Stephen Robertson, Andrew Macfarlane, Advances in XML Information Retrieval and Evaluation (INEX 2005).  LNCS 3977, Springer 2006 (pp 161-171).
Описание слайда:
Литература Christopher D. Manning, Prabhakar Raghavan and Hinrich Schütze, Introduction to Information Retrieval, Cambridge University Press. 2008. David Carmel, Nadav Efraty, Gad M. Landau, Yoelle S. Maarek, Yosi Mass, An Extension of the Vector Space Model for Querying XML Documents via XML Fragments, ACM SIGIR'2002 Workshop on XML and IR, Tampere, Finland , Aug 2002 Wei Lu, Stephen Robertson, Andrew Macfarlane, Advances in XML Information Retrieval and Evaluation (INEX 2005). LNCS 3977, Springer 2006 (pp 161-171).

Слайд 36





Спасибо за внимание!
Описание слайда:
Спасибо за внимание!



Похожие презентации
Mypresentation.ru
Загрузить презентацию