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?