Vyhledávání v multimediálních databázích
Tomáš SkopalKSI MFF UK
3. Modality a kvalita vyhledávání
Osnova
Modality vyhledávání Dotazy - rozsahový dotaz, (reverzních) k nejbližších
sousedů, closest pair, similarity join Relevance feedback Browsing, navigace pomocí výsledku dotazu
Kvalita výsledku (retrieval effectiveness) úspěšnost MDBR systému vzhledem k obsahu
výsledku dotazu (obecně celého retrieval procesu)
Dotazování, předpoklady
míra odlišnosti (např. metrika) d(*,*) definovaná na univerzu U
datová sada S U všechny objekty universa tvoří prostor
např. klasický vektorový Rn
všechny řetězce na abecedě
Podobnostní uspořádání
uspořádání objektů datové sady S vzhledem k vzdálenostem k Or (Or je referenční objekt), tj. SimOrder: U 2UxU, kde <Oi, Oj> SimOrder(Or) d(Or,Oi) < d(Or,Qj)
pouze abstrakce pro potřeby definic dotazů, tj. ve skutečnosti se uspořádání „nematerializuje“ celé
různé typy dotazů specifikují odpověď rozsahem na podobnostním uspořádání
Rozsahový dotaz (range query) zadán objektem Q (example) a poloměrem dotazu rQ
(resp. prahovou hodnotou) notace (Q, rQ)
relevantní k dotazu (Q, rQ) jsou všechny objekty Oi S univerza, které splňují podmínku d(Q,Oi) rQ výběr z uspořádání SimOrder(Q)
geometrická interpretace: „hyper-koule“ v prostoru U označuje oblast v U (a tím také v S), která je relevantní k dotazu pro zjednodušení budeme
znázorňovat regionem v R2, vnitřek regionu (včetně hranice) označuje relevantní objekty
L1 L2
Rozsahový dotaz (2)
vyžaduje se „expertní“ znalost významu poloměru, velikost výsledku dotazu je proměnlivá vhodnější použití jako mezidotaz, kdy je potřeba úplná odpověď,
která se dále zpracovává vykonání rozsahového dotazu
sekvenční průchod S a porovnání všech objektů z S vůči (Q, rQ) použití nějakého metrického indexu (pokud d je metrika)
struktura metrických datových regionů – různé tvary filtrování těch datových regionů, které nemají průnik s regionem
dotazu více na pozdějších přednáškách
Příklad - rozsahový dotaz
dist = 0.0
dotaz (Q, 1200)
dist = 1031.3 dist = 1166.2
dist = 998.7 dist = 1018.8 dist = 1040.4
1) 2) 3)
4) 5)
Q:
Bodový dotaz (point query)
rozsahový dotaz, kde rQ = 0 jednoduchá a rychlá implementace u metrik
exact-match dotaz (stačí ukládat reprezentace objektů do B-stromu a vyhlevávání je potom prosté nalezení klíče – umožňuje reflexivita)
velmi omezené použití např. identifikace duplicit
u robustních měr porušujících reflexivitu může bodový dotaz poskytovat funkcionalitu binární relevance tolerance (poloměr) se přenese „dovnitř“ míry
Dotaz na k nejbližších sousedů (k nearest neighbors – kNN dotaz) zadán objektem dotazu Q a přirozeným číslem k, které specifikuje
kolik nejbližších (nejpodobnějších) objektů se má vrátit jako výsledek notace (Q, k)
výběr prvních k objektů z uspořádání SimOrder(Q) relevantní k dotazu jsou objekty Oi A S, že |A| = k a platí Oj
S – A, d(Q,Oi) d(Q,Qj) geometrická interpretace: stejná jako u rozsahového dotazu, tj.
hyperkoule rozdíl je v tom, že poloměr rQ neznáme předem, je určen právě
vzdáleností ke k-tému sousedů tj. lze převést na problém rozsahového dotazu s dynamickým
poloměrem (v průběhu zpracování se poloměr upřesňuje)
Dotaz na k nejbližších sousedů (2)
vhodnější pro konečného uživatele, který už výsledek musí „probrat“ sám, tj. specifikuje se únosná velikost výsledku dotazu
vykonání dotazu sekvenčně
vyrobíme uspořádání (pamatujeme si průběžně nejbližších k objektů, které na konci průchodu tvoří výsledek dotazu)
pomocí metrického indexu - rozdíl oproti rozsahovému dotazu dynamický poloměr dotazu
rostoucí od nuly (heuristika odhadu poloměru) klesající od nekonečna (resp. od maximální vzdálenosti)
heuristické algoritmy prioritní fronta, ...
Dotaz na k nejbližších sousedů (3)
sekvenčně, k=3, klesající poloměr
Dotaz na k nejbližších sousedů (4)
s metrickým indexem, k=3 (detaily v pozdějších přednáškách), klesající poloměr
Příklad – kNN dotaz
dist = 0.0
dotaz (Q, 3)
dist = 998.7 dist = 1018.8 dist = 1040.4
1) 2) 3)
Q:
Dotaz na reverzních k nejbližších sousedů zadán objektem dotazu Q a přirozeným číslem k vrací ty objekty z S, pro které je Q mezi k nejbližšími
sousedy lze modelovat |S| kNN dotazy, kde Q’ proběhne přes všechny
objekty v S – výsledek původního dotazu se skládá z objektů Oi, takových, že Q’S a Oi(Q’, k)
příklad, k=3
Možná integrace do SQL
podobnostní uspořádání funkce SIMorder(obj, DB) =
< DB.obj1, DB.obj2, ..., DB.objn>, kde d(obj, DB.obji) ≤ d(obj, DB.obji+1) obji DB
podobnostní predikáty range(example.MMattribute, table.MMattribute, )
vrátí prvních x takových objektů ze SIMorder(example.MMattribute, table.MMattribute), kde SIMorder[x+1] >
kNN(example.MMattribute, table.MMattribute, k)vrátí prvních k objektů ze SIMorder(example.MMattribute, table.MMattribute)
Rozsahový a kNN dotaz v SQL
SELECT Id FROM BioData WHERE range(FrantisekNovak.Otisk, BioData.Otisk, 0.01)
SELECT Id FROM DNAData WHEREkNN(VcelkaMaja.DNA, DNAData.DNA, 1)
Similarity join
dvojice objektů ze dvou množin takových, že objekty dvojice jsou si dostatečně podobné
range similarity join – spojení přes range query predikát
kNN similarity join – spojení přes kNN predikát
Similarity join
SELECT Zločinec.Id, Občan.Id FROM Zločinec SIMILARITY JOIN Občan ON range(Zločinec.Otisk, Občan.Otisk, 0.01)
SELECT Savec.Id, Hmyz.Id FROM Savec SIMILARITY JOIN Hmyz ON kNN(Savec.DNA, Hmyz.DNA, 2)
Closest pairs
SELECT Savec.Id, Hmyz.Id FROM Savec SIMILARITY JOIN Hmyz ON kNN(Savec.DNA, Hmyz.DNA, 1)
Dynamické dotazy
podobnost závislá na dotazu
Komplexní dotazy (1)
použitá primitiva – kNN a range query primitiva lze začlenit jako speciální predikáty do
boolského modelu (takto lze rozšířit např. SQL), lze použít single-reprezentace i multi-reprezentace dokumentů
dotaz:
výsledek dotazu:
Komplexní dotazy (2)
jednodušší varianta – množinové operace na výsledcích dotazů
Relevance feedback (uživatelská zpětná vazba) zpravidla tři kroky
provede se „předdotaz“ s počátečním nastavením (např. kNN) uživatel subjektivně ohodnotí relevanci (některých) objektů z
výsledku dotazu pokud míra kombinuje „lidsky uchopitelné“ vlastnosti, může uživatel
přímo upravit jejich proporci (např. barva vs. textura vs. tvar) pozitivní a negativní příklady
učení nebo reformulace dotazu uživatelská nebo automatická (re)parametrizace míry (metriky)
např. lze u vážené euklidovské metriky, kvadratické formy, ... zjemnění dotazu (kombinovaný dotaz) učení míry, resp. uživatelské profilování
neuronové sítě více iterací
Ukázka 1 – systémy Surfimage, WebSEEK
Ukázka 2 (zdroj: kniha Image Databases, Castelli & Bergman, Wiley)
předdotaz:
Ukázka 2 (zdroj: kniha Image Databases, Castelli & Bergman, Wiley)
úprava vah
uživatelem:
Ukázka 2 (zdroj: kniha Image Databases, Castelli & Bergman, Wiley)
vizualizace
výsledku:
Browsing a navigace základní princip: nevíme přesně, co hledáme katalogizované prohlížení databáze
vyžaduje anotaci, klasifikaci, tvorbu ontologií, atd. navigace pomocí výsledku dotazu
opakovaně pokládáme dotazy pomocí výsledků jiných dotazů (např. kNN), postupně se můžeme dostat zcela mimo původní dotaz
„traverzování“ databáze po cestách „podobnostním grafu“
kvalita vyhledávání (retrieval effectiveness) je úspěšnost vyhledání dokumentů vzhledem k očekávání uživatele vždy subjektivní, obecně nelze dosáhnout dokonalosti měření kvality systému/metody na základě subjektivně ohodnocené kolekce nejčastěji přesnost (precision) P = |RelOdp|/|Odp|
a úplnost (recall) R = |RelOdp|/|Rel| kvantifikace pro jeden dotaz (ať rozsahový nebo kNN) přesnost ukazuje proporci irelevantních objektů v odpovědi úplnost ukazuje proporci relevantních objektů v odpovědi
Kvalita vyhledávání (retrieval effectiveness)
kolekce
objekty v odpovědi = Odp
relevantníobjekty = Rel
relevantní objekty v odpovědi = RelOdp
Kvalita vyhledávání (2)
nechť QRref je referenční výsledek dotazu (např. ohodnocený uživatelem nebo získaný jinou metodou) a QRsys je výsledek dotazu vytvořený systémem/metodou, potom
objekt Oi QRsys a zároveň Oi QRref se nazývá false hit (false alarm)
čím více false hitů, tím nižší přesnost
objekt Oi QRsys a zároveň Oi QRref se nazývá false drop (false dismissal)
čím více false dropů, tím nižší úplnost
u hodnot přesnosti a úplnosti obecně vztaženým k referenčnímu výsledku dotazu (tj. ne k výsledku subjektivně vytvořenému uživatelem) hovoříme někdy o relativní přesnosti a relativní úplnosti (vzhledem k dané referenční metodě)
Kvalita vyhledávání (3)
křivka precision/recall přesnosti pro 11 standardních úrovní úplnosti (R=0..1 po 0.1 krocích) ke konstrukci křivky využíváme uspořádání k dotazu – SimOrder(Q)
tj. neuvažuje se konkrétní typ a rozsah dotazu, pouze dotazový objekt Q např. pro úroveň 0.1 se přesnost spočítá tak, že se uvažuje takový „začátek“
uspořádání SimOrder(Q), který obsahuje 10% relevantních objektů (resp. nejbližší hodnotu k 10%)
křivka typicky ukazuje na kompromis – dosáhneme vyšší přesnosti za cenu nižší úplnosti – a naopak
Kvalita vyhledávání (4)
Alternativní míry:
Průměrná přesnost (mean precision) počítá se z přesností, které obdržíme při „posunování konce uspořádání“
SimOrder(Q) po všech relevantních dokumentech – přibližně odpovídá obsahu plochy pod precision/recall křivkou
Mean average precision agregovaná veličina – střední hodnota průměrných přesností přes více
dotazových objektů Q
F-score = 2*P*R/(P+R) harmonický průměr přesnosti a úplnosti výhoda: jedna veličina místo dvou
R-precision přesnost, když bereme v úvahu prvních |Rel| objektů v SimOrder(Q)
Bull-Eye percentage úplnost, když bereme v úvahu prvních |Rel|/2 objektů v SimOrder(Q)
Kvalita vyhledávání (5)
Harmonic mean a E-measure F(j) = 2/(1/r(j) + 1/P(j)) E(j) = 1 – ((1+b2)/(b2/r(j) + 1/P(j)))
r(j) je úplnost na j-tém objektu v uspořádání P(j) je přesnost na j-tém objektu v uspořádání b je zvolený parametr
Coverage a Novelty Coverage = |Rk|/|U|
pokrytí známých objektů v odpovědi
Novelty = |Ru|/(Ru + Rk) proporce neznámých
objektů v odpovědi
kolekce
relevantníobjekty = Rel
známé relevantníobjekty = U
známé relevantníobjekty v odpovědi = Rk
neznámé relevantníobjekty v odpovědi = Ru
objekty v odpovědi = Odp
Benchmarking & evaluation (1)
Návrh kolekcí a metodik pro testování úspěšnosti MDB systémů a jejich srovnávání. K tomuto účelu je zpravidla potřeba mít:
- kolekci(e) objektů- sadu dotazů- sadu relevantních objektů k dotazu (problémy s ohodnocováním dotazů)
TREC trec.nist.gov (od r. 1992) texty video (TRECVID) www-nlpir.nist.gov/projects/trecvid genomické databáze ir.ohsu.edu/genomics
Benchathlon www.benchathlon.net image retrieval
Benchmarking & evaluation (2)
Cystic Fibrosis Database www.sims.berkeley.edu/~hearst/irbook/cfc.html 1239 dokumentů o cystické fibróze 100 ohodnocených dotazů skóre relevance 0..9 přiřazeno experty
Princeton Shape Benchmark shape.cs.princeton.edu/benchmark/index.cgi databáze a nástroje 3D retrieval 1814 3D modelů trénovací a testovací klasifikace 3D objektů (2x 90 tříd a 907
modelů)