1 / 12
Petr Chmelař
UIFS FIT VUT
PDB
IR & MM Apps
Teorie!
Modely
Taxonomie
Experiment.
Realita?
Vyhledávání informací
a multimediální aplikaceInformation Retrieval
and Multimedia Applications
[ http://www.fit.vutbr.cz/~chmelarp/pdb/ ]
[ http://www.dcs.gla.ac.uk/ssms07/material.html ]
2
Vědecké paradigma
Teorie
Experiment
Realita
Top-down approach
Bottom-up approach
Věda
čtení
myš
lení
psaní
3
Konceptuální úroveň
Geometrická
logická úroveň
Obraz
fyzická úroveň
Reprezentace
Vnímání
Semantic
Gap
Vidění
Binární reprezentace
4 / 12
Petr Chmelař
UIFS FIT VUT
PDB
IR & MM Apps
Teorie!
Modely
Taxonomie
Experiment.
Realita?
Teorie!
Vyhledávání informací je činnost, jejímž cílem je
identifikace relevantních dokumentů nebo informací v
informačních zdrojích (např. fulltextových databázích),
souvisí s reprezentací, skladováním, organizací a
přístupem k informacím.
IR je vyhledávání v nestrukturovaných datech.
[ TDKIV, Keith, RBY-MIR ]
5
Objekt IR
Vstupy / výstupy
Dokument
Novinové články, web…
Fotografie
Řeč a zvuk
Video
Dotaz
Cokoliv ▲
Relevance?
za následující odbočkou …
Database
DocumentsQue
ries Output
Fee
dba
ck
6
Pozadí
Data
Strukturovaná
Čísla
Písmena
Slova
Informace
Rozdíl? ▲
Relevance?
…
Dotazování IR
potřeba
data
shodná
informace
relevantní
dotaz
strukturovaný
kompletní
přirozený
nekompletní
odvození
dedukce indukce
shoda
přesná nejlepší možná
model
deterministický pravděpodobnostní
…
přisoudíme významsmysl v daný okamžik
7
Modely
Modely IR odpovídají na otázky relevance dotazu k dokumentům v DB:
Jaké dokumenty mají být výsledkem dotazu?
Jaké bude jejich uspořádání pro prezentaci uživateli?
Klasické modely
Booleovský model
Pravděpodobnostní modely
Vektorové modely
Alternativní modely… Fuzzy set, neural network, belief network, SVM, latent
semantic indexing, hypertext model, …
QueryDocumentEvaluation
Model
8
Klasický booleovský model
Klasický model předpokládá, že dokument d je popsán množinou
reprezentativních klíčových slov – indexační termíny k.
Termy jsou obvykle podstatná jména (bez některých vybraných).
Binární rozhodovací kritérium je založené na přítomnosti, resp. absenci daného
klíčového slova a neuvažuje jeho váhu (pravdivost, dokazatelnost).
Dotazy jsou tvořeny termy a logickými spojkami and, or, not a závorkami.
Striktní formalizmus, efektivní (index „invertovaný soubor“), používá se pro
dotazování; výsledkem příliš (málo) dokumentů, neřeší uspořádání…
Binární porovnávání
Jednoduché
Jaccardovo
)(notand)and( 321 kkkq
21 ddM Diceovo
Kosinové
21
21
dd
ddM
21
21
dd
ddM
21
21
dd
ddM
9
Teorie informace
Term frequency
četnost výskytu klíčového slova
nebo jiné lingvistické jednotky
v … dokumentu
váha termínu - důležitost
Inverse document frequency
inverzní log četnosti
dokumentů, ve kterých
se tem vyskytuje
informační hodnota termínu
[ Shannon, Keith ]
t
iii kkkH
12 )p(log)p()(
ijiji D
ndkw 2, log),f(
10
Vektorový model
Váhový vektor přiřazen dotazu q i dokumentům dj …
pak vzdálenost (kosinová) je
ale může být i Eukleidovská, nebo dokonce Manhattan.
O vzdálenosti platí:
dist(x, y) ≥ 0
dist(x, x) = 0
dist(x, y) = dist(y, x)
dist(x, y) ≤ dist(x, z) + dist(z, y)
→ navazující přednáška
qtq wwq ,,1 ,, jtjj wwd ,,1 ,,
t
iji
t
iqi
t
i jiqi
j
jj
ww
ww
dq
dqdq
1,
2
1,
2
1 ,,,dist
q
dj
11
Pravděpodobnostní model
Relevance v IR nejistá → pravděpodobnost a teorie rozhodování!
Idea: Pokud se na daný dotaz podaří vrátit dokumenty v pořadí s klesající
pravděpodobností relevance, bude efektivita systému nejlepší možná.
Řešení: Bayesem
)()|P()P()()|P( apabbabpba )P(
)P()|P(
b
baba
)P(
)P()|P()|P(
b
aabba marginal probability
AP(B | ai)P(ai)
likehood prior informationposterior probability
12
Probability ranking principlePrincip ohodnocení dle pravděpodobnosti
Potřebujeme zjistit relevanci (True / False) daného dokumentu P(T | d):
Základem je, že minimalizujeme průměrnou (celkovou) chybu:
)P(
)P()|P()|P(
d
TTddT
)P(
)P()|P()|P(
d
FFddF
pravď. že při získání nerelevantního
dokumentu to bude d.
je relevantní
)P()|P(maxarg)|P(maxarg)(* TTddTddd
Tdecideweif
Fdecideweif
dFp
dTpderror
)|(
)|()|P(
D
dderrorerror )P()|P()P(
13
Taxonomie
Úplnost
Přesnost
)|P( PTP
TPPrecision
round ruthRelevant (g t )
True False
Info
rmat
ion
Req
uest
Po
sitiv
e
Ne
ga
tive
Data Collection
TruePositive
TrueNegative
FalsePositive
FalseNegative
)|P( TPT
TPRecall
)|P( FPF
FPFallout
14 / 12
Petr Chmelař
UIFS FIT VUT
PDB
IR & MM Apps
Teorie!
Modely
Taxonomie
Experiment.
Realita?
Experiment.
Funguje teorie?
Text
TREC evaluace a porovnání … relevance systémů
WWW
Google, Yahoo, Altavista, Jyxo, Seznam, …
Multimedia?
TRECvid…
PETS Performance Evaluation of Tracking and Surveillance
CLEAR, VACE, ETISEO, … http://pets2007.net/
http://www.clear-evaluation.org/
http://trec.nist.gov/tracks.html
15
Fulltextové databáze
Fulltextové vyhledávací funkce v databázích
Oracle
create index docs_index on docs(text) indextype is ctxsys.context;
select id, title, text, ctxsys.score(1) score from docs
where ctxsys.contains(text, ‘inrmation retrieval’, 1) > 0
order by ctxsys.score(1) desc;
MySQL
ALTER TABLE Clanky ADD FULLTEXT (nazev, anotace, text);
SELECT * FROM Clanky WHERE MATCH(nazev, anotace, text)
AGAINST (‘vyhledávání informací’ IN BOOLEAN MODE);
http://en.wikipedia.org/wiki/Special:Search?search=information+retrieval&fulltext=Search
16
TRECVid
Video data
100h (2007) + 156h (2006) + 140h (2005) + 150 (předtím)
Shot detection, ASR, MT, … Annotations
Tasks
Shot boundary detection
Detecting semantic concepts / features (39) [ Alan Smeaton ]
Searching based on topics
Automatic
Manual
Interactive
Automatic summarization
LSCOM Large Scale Concept Ontology for Mm http://www.lscom.org/
http://www-nlpir.nist.gov/projects/tv2007/tv2007.html#2.3
17
Koncepty [ Cees Noek ]
18
MultimodalitaKombinace více způsobů…
[ Alex Hauptmann ]
19
Demonstrace
Přísně tajné, neveřejné, …
CuVid Columbia Video Search System
http://apollo.ee.columbia.edu/cuvidsearch/
MediaMillhttp://mediamill.nl/
Informedia (dočasně nefunkční demo)
http://www.informedia.cs.cmu.edu/
ESP Gamehttp://www.espgame.org/
Flickr & Tiltomo http://flickr.com/ & http://www.tiltomo.com/
MultimediaN N9C Eculture projecthttp://e-culture.multimedian.nl/
LTU Visual Search on Royalty-Free imageshttp://corbis.ltutech.com/
20
Software
Finding Out Abouthttp://www.cse.ucsd.edu/~rik/foa/
BRISC Image Retrieval System
http://sourceforge.net/projects/brisc
Octagon - content based image retrieval softwarehttp://octagon.viitala.eu/
Chuckwalla (MediaWay)http://www.chuckwallainc.com/
IBM DB2 AIV Extenders
http://www-306.ibm.com/software/data/db2/extenders/aiv/
interMediahttp://www.oracle.com/technology/
Váš projekt :)
21 / 12
Petr Chmelař
UIFS FIT VUT
PDB
IR & MM Apps
Teorie!
Modely
Taxonomie
Experiment.
Realita?
Praxe?
Experimenty prokázaly, že teorie nefunguje
a že nic lepšího neexistuje.
[ Churchill ]
Multimodální?
Sémantické?
22
Literatura
CHMELAŘ, Petr. Multimediální databáze. 2006. http://
www.fit.vutbr.cz/~chmelarp/pdb/
Teaching Material @ SSMS 2007
http://www.dcs.gla.ac.uk/ssms07/material.html
Rijsbergen, van C.J., Keith. Information Retrieval. 1999.
http://www.dcs.gla.ac.uk/ssms07/teaching-material/ir/index.htm
Baeza-Yates, R. - Ribeiro-Neto, B. Modern information retrieval. New
York : ACM Press, 1999. 513 s. ISBN 978-0-201-39829-8.
TDKIV - Česká terminologická databáze z oblasti knihovnictví a informační vědy
http://www.nkp.cz/o_knihovnach/Slovnik/index.htm
23 / 12
Petr Chmelař
UIFS FIT VUT
PDB
IR & MM Apps
Teorie!
Modely
Taxonomie
Experiment.
Realita?
Díky
Otázky?