Vyhledávání v multimediálních databázích

Tomáš SkopalKSI MFF UK

2. Modelování a podobnost

manažer dokumentů

robot

databázedokumentů

extraktor indexer

index(y)

„example“ dotaz

„sketch“ dotaz

web

LAN, intranet, ...

relevance feedback

podobnost

relevantní dokumenty

Modelová struktura multimedia retrieval systému

Extrakce vlastností

které vlastnosti extrahovat? používané mírou podobnosti deskriptivní (rozlišující) relativně malý počet kompaktní (malé prostorové náklady)

geometrický přístup model vektorového prostoru metrického prostoru obecně „dissimilarity space“

single-reprezentace vs. multi-reprezentace single-reprezentace – jediný komplexní objekt, složen z více podobjektů

problém: jak měřit komplexní podobnost? multi-reprezentace – dokument je rozdroben na více jednoduchých objektů

problém: jak při extrakci rozpoznat izolované části v dokumentu?

Vektor

homogenní histogram na jedné sémantické doméně

např. šedotónový histogram k obrázku

heterogenní kombinace nezávislých vlastností (domén) např. u notové partitury (takt, tempo, žánr, délka)

kombinovaný homogenní části vektoru např. 3 histogramy pro barvy

Geometrie

polygon

síť polygonů

Množina

otisky identifikační body (více druhů)

komplexní objekty, single-reprezentace např. řetězce (množina slov/vět v textu) tvary (polygony) cokoliv jiného

Posloupnost

diskrétní signál v čase, extrakce vzorkováním akcie trajektorie

řetězec vektor proměnné délky

DCT, DFT, DWT koeficienty

obecně lineární uspořádání na množině čehokoliv

Řetězec

DNA

termyslovník

AATAGCAGCATA...

Graf

XML XML dokument reprezentován

stromem (obecně grafem) sada grafů

topologie webu identifikace zajímavých podgrafů

např. k-souvislé komponenty modelování topologií webových komunit

podgrafy tvoří objeky sady

Míry podobnosti

vlastnosti metriky, nemetriky kvalita (teorie podobnosti vs. restrikce)

učení, adaptace, relevance feedback uživatelské profilování

robustní míry většinou nemetrické snížená citlivost na tzv. „outliers“, anomální objekty, kde

vlastnost objektu je výrazně jiná než tato vlastnost u ostatních objektů

typicky šum nebo chyba v signálu důraz na efektivní spočitatelnost

Metriky vs. nemetriky

argumenty proti axiomům metriky

(a) reflexivita

(b) pozitivita

(c) symetrie

(d) trojúhelníková nerovnost

Vektorové metriky

L1 L2 L5 L∞

vážená L2

kvadratická forma

tzv. Minkowského vzdálenosti

Vektorové nemetrické míry (1)

kosinová míra SIMcos kosinus úhlové odchylky dvou vektorů

normovaný skalární součin úhel (tj. arccos(SIMcos)) je metrika

(L2 vzdálenost po povrchu jednotkové koule v radiánech)

robustní vůči velikostem vektorů

fractional Lp distances zobecnění Minkowského vzdáleností

použitím p<1 robustní vůči extrémním rozdílům

hodnot souřadnic

L0.5

Vektorové nemetrické míry (2)

Vektorové nemetrické míry (3)

COSIMIR třívrstvá neuronová síť vstup – dva vektory výstup – hodnota podobnosti učení pomocí back-propagation

uživatelem ohodnocené vektory nebezpečí lokálních extrémů,

tj. při učení nemusí konvergovat

Konvexní vs. nekonvexní regiony

na tvaru regionu nezáleží „hustota“ regionů se liší

metrika nemetrika metrika nemetrika

Míry pro posloupnosti

lze aplikovat i vektorové míry (např. Euklidovskou) nevhodné pro porovnávání různě

dlouhých posloupností omezeno na číselné posloupnosti

(dynamic) time warping distance (DTW) zohledňuje časově lokální „frekvenci vzorkování“ tím, že lokálně

„natahuje/zkracuje“ posloupnost s cílem najít nejmenší cenu součtu parciálních vzdáleností

tzv. zarovnání posloupností (sequence alignment) i nečíselné posloupnosti (prvkem může být cokoliv „měřitelné“) není to metrika (porušena trojúhelníková nerovnost)

DTW, princip (1)

matice M řádu m x n, kde m = |s1|, n = |s2|, kde s1 a s2 jsou porovnávané posloupnosti

buňka matice M(i,j) odpovídá parciální vzdálenosti (s1(i),s2(j)) DTW(s1,s2) je nejkratší cesta v matici (ve smyslu součtu hodnot

buněk na cestě) definice cesty – buňky na cestě mají jisté vlastnosti

monotónnost – buňky uspořádány monotónně spojitost – buňka „sousedí“ s buňkou hraniční podmínka – první buňka je v matici na souřadnicích (0,0),

poslední na souřadnicích (m-1, n-1)

DTW, princip (2)

exponenciální počet možných cest, nicméně DTW lze spočítat v čase O(m*n) pomocí dynamického programování

parametr ≥0 (tzv. Sakoe-Chibův pás) umožňuje snížit počet přípustných cest, čímž se zamezuje „patologickým cestám“ snižuje složitost výpočtu na O((m+n)* )

pro =0, m=n a (x,y) = |x-y| dostanemeEuklidovskou vzdálenost (L2)(pouze jedna cesta, zarovnává se 1:1)

Řetězcové (ne)metriky (1)

editační vzdálenost (Levenshteinova metrika) je nejmenší počet operací potřebných ke konverzi jednoho řetězce do druhého operace vložení, vymazání, substituce znaku

substituce se může chápat jako dvojice vložení, vymazání), tzv. indel vzdálenost (insert-delete), tj. lze se omezit pouze na indel

různé váhy pro operace podobná filosofie jako u DTW

koncept cest v matici, resp. alignment, dynamické programování šikmá hrana v cestě je match znaků, vertikální/horizontální je vložení/smazání

Hammingova vzdálenost editační, kde je povolena pouze substituce řetězce stejné délky, v podstatě vektorová metrika

indel(ATGTTAT ATCGTAC) = 4

hamming(ABCDEF BCDEFA) = 6

Řetězcové (ne)metriky (2)

LCSS (longest common subsequence) hledání nejdelšího společného podřetězce (podposloupnosti)

myslí se podposloupnost, která může být „prokládaná“, tj. LCSS(ABCD, ACBD) = 3 (buď ABD nebo ACD)

opět podobná filosofie jako u DTW rovněž koncept cest v matici, resp. alignment, dynamické

programování pouze binární ohodnocení vztahu prvků v posloupnostech

(match / mismatch) šikmá hrana je match, rovná hrana mismatch

využití zejména v DNA databázích nemetrika

Množinové metriky (1)

Jaccard distance (normed overlap distance) normovaná velikost průniku dvou množin

Hausdorffova metrika měří „nejvzdálenějšího nejbližšího souseda“

pro všechny prvky A se spočítají vzdálenosti k nejbližšímu sousedu v B a vezme se maximum

dNO({kočka, pes, myš}, {klávesnice, myš}) = 0.75

Množinové metriky (2)

source: Michael Leventon's pages

Hausdorffova metrika a shape retrieval

- multi-reprezentace (sada objektů příslušející jednomu dokumentu)

- je vzdálenost dvou úseček (obecně kusů polygonu)

dotaz

sada objektů příslušející jednomu dokumentu

výsledek – nejbližší objekt, resp. odpovídající dokument

Množinové metriky (2)

Hausdorffova metrika a otisky prstů

- single-reprezentace

- je Euklidova vzdálenost dvou bodů (identifikační body)

Grafové metriky

měření strukturální podobnosti stromová editační vzdálenost

novější obdoba řetězcové editační vzdálenostije nejmenší počet operací potřebných ke konverzi jednoho stromu do druhého

operace přejmenování uzlu, vymazání uzlu, vložení uzlu

Robustní míry

k-median distances uvažuje (k-té) nejpodobnější části v objektu operátor k-med (výběr k-té nejmenší hodnoty) se aplikuje na

setříděnou posloupnost parciálních vzdáleností

fractional Lp distances redukuje se vliv „outlier dimenzí“

k-median Hausdorff distance

single-reprezentace je Hausdorffova metrika (jako u multi-reprezentace) k = 3 (vrací vzdálenost třetího nejpodobnějšího objektu)

outliers

Black-box míry

zcela neznámá analytická definice black-box

algoritmusHW zařízení