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ů)