Der Weg ist das Ziel - Explorative semantische Videosuche

Dr. Harald SackHasso-Plattner-Institut for IT-Systems Engineering

University of Potsdam

Der Weg ist das Ziel

Explorative Semantische Videosuche

Interaktion und Visualisierung im Datenweb (IVDW 2012)Braunschweig, 20.09.2012

Donnerstag, 20. September 12

Dr. Harald SackHasso-Plattner-Institut for IT-Systems Engineering

University of Potsdam

Der Weg ist das ZielExplorative Semantische Videosuche

•Worum gehts....•Suchen und Finden im World Wide Web•Suche in multimedialen Daten•Semantische Suche•Explorative Suche


Dr. Harald Sack, Hasso-Plattner-Institut Potsdam, Workshop: Interaktion und Visualisierung im Datenweb (IVDW 2012), Braunschweig, 20.09.2012

The Web is big. Really big. You just won't believe how vastly, hugely, mind-bogglingly big it is.(frei nach Douglas Adams)



Wie findet man etwas im WWW?



...the current solution:



The World according to Google...



Suchfacetten

Multimodale Ergebnisse


Dr. Harald Sack, Hasso-Plattner-Institut Potsdam, Workshop: Interaktion und Visualisierung im Datenweb (IVDW 2012), Braunschweig, 20.09.2012Donnerstag, 20. September 12


Welcome to the End of the World....

...according to Google...62% of internet search engine users click on a search result within the first page of results, and 90% within the first three pages.

from AOL’s search query logs 08/2006

the first 10 results received 89.71% of all click-through traffic; the following 10 results received 4.37%; the third page 2.42%; and the fifth page 1.07%.

iProspect Search Engine User Behaviour Study, 2006

from AOL’s search query logs 08/2006


Dr. Harald Sack, Hasso-Plattner-Institut Potsdam, Workshop: Interaktion und Visualisierung im Datenweb (IVDW 2012), Braunschweig, 20.09.2012Donnerstag, 20. September 12


• Steht das Wichtigste tatsächlich vorne in der Ergebnisliste?

• Was bedeutet überhaupt „wichtig“?• Ist das, was Google für wichtig hält, tatsächlich

auch für alle gleichermaßen wichtig?• ...und was ist mit dem Rest?• Kann Google meine Absicht erraten??• Sind das überhaupt tatsächlich auch alle Ergebnisse?• Kann ich überprüfen, ob die Ergebnisse

vollständig sind?

Das „Google Dilemma“

Problem: Ich muss wissen, was ich suche....



Klassisches Information Retrieval

(nach Salton,G., McGill, M.J.: Introduction to Modern Information Retrieval. McGraw-Hill, New York 1983)

Menge von Dokumenten

files of records

Menge von Anfragen

Information requests

Indexierungssprache

similarity

IndexierungAnfrage-formulierung



Klassisches Information Retrieval(vereinfachte Variante....)

Menge von Dokumenten

Suchindex

SUCHEN, vb. , in allen ger n sprachen bezeugt: got.sokjan, ags. sēcan, as. sokian, an. Soekj

[Bd. 20, Sp. 835]

sēza, ahd. suohhan. aus idg. sprachen steht am nächsten lat. sāgiospüre, air. saigim gehe

einer sache nach, suche; zur weiteren verwandtschaft vgl. Walde-Pokorny 2, 449.

der umlaut des stammvokals erscheint im nd., er wird im md. verzeichnet vonCrecelius

oberhess. wb. 827; Spiess henneb. id. 248; Hertel Thüringen240; Gerbet Vogtland 425

und auf kolonialem boden bei Schröerdeutsche mundarten des ungrischen

berglandes 225. neben eigentlichem suchen 'einer sache

nachspüren, sich bemühen, sie aufzufinden' (dann auch 'jemanden

aufsuchen, ihn bedrohen, angreifen') steht eine reich bezeugte bedeutungsgruppe mehr

Schlüsselwörter

„Suchen“Suchterm(e) ?

Suchanfrage

DokumentDonnerstag, 20. September 12


relevante Dokumente gefundene Dokumente

relevante Dokumente, die gefunden wurden

R P

Recall=| R ∩ P |

|R|

Precision=| R ∩ P |

|P|

Wie gut ist das Suchergebnis?



• World Wide Web ist ein verteiltes Hypermediasystem•multimediale Dokumente• über Hyperlinks miteinander

vernetzt

•WWW-Suchmaschinen sind Information Retrieval Systeme mit folgenden Aufgaben• Erstellung und Pflege eines Indexes

(Web Crawler + Indexing)• Verarbeitung von Suchabfragen (Retrieval + Ranking)• Aufbereitung der Ergebnisse (Visualisierung)

Suchmaschinen im WWW


Vorlesung Semantic Web, Dr. Harald Sack, Hasso-Plattner-Institut, Universität Potsdam

16

URL Liste

http://www.xxxx.de/1234...http://www.xxxx.de/2234...http://www.xxxx.de/3234...http://www.xxxx.de/4234...http://www.xxxx.de/5234...http://www.xxxx.de/6234...http://www.xxxx.de/7234......

<a href=“...“ .../>

<a href=“...“ .../>

HTMLDokumente

WWW-ServerHTTP Request

WWW-Server liefert angefragteHTML-Dokumente an denWeb-Crawler zurück

1

2

3

4

Web-Crawler (Web Robot)



17

Datennormalisierung

Web Crawler

Datenanalyseund Anlegender Index-

Datenstrukturen

Preprocessing und IndexierungSuchmaschinen im WWW

Wortidentifikation

Sprachidentifikation

Word Stemming

POS-Tagging

Deskriptorengenerierung



18

Effiziente IndexdatenstrukturenSuchmaschinen im WWW

Aachen

Altavista

Ananas

……

Zustand

Zypern

Indexdatei

AnanasDocID Pos Frequenz Gewicht

D123 1;13;77;132 4 9.4D456 22;38 2 6.7 … … … …D998 15 1 1.2

Location List D123Frequenz URL <H1> … <H6> <title> … text

4 1 1 0 1 … 1

D123 http://producers.ananas.org/index.htm

<html><head><title=“Ananas around the World“></head><body> … </body></html>

Invertierte Datei

Direkte DateiDonnerstag, 20. September 12


19

Relevanzbewertung (Ranking)Suchmaschinen im WWW

• Linkpopularität (Google PageRank)

A

1.0

D

1.0

B

1.0

C

1.0

Ausgangssituation

Nr. PR(A) PR(B) PR(C) PR(D)1 1,0 1,0 1,0 1,02 1,0 0,575 2,275 0,153 2,083 0,575 1,191

20,15

… … … … …n 1,49 0,7833 1,577 0,15

Iteration der PageRank Berechnung A

1.49

D

0,15

B

0,78

C

1.57

resultierender PageRank


Dr. Harald Sack, Hasso-Plattner-Institut Potsdam, Workshop: Interaktion und Visualisierung im Datenweb (IVDW 2012), Braunschweig, 20.09.201220Aber warum ist das Suchen im WWW so schwierig...?



The Web is big. Really big. You just won't believe how vastly, hugely, mind-bogglingly big it is.(frei nach Douglas Adams)



•ca. 25 x 109 in Suchmaschinen indizierte Dokumente (TNL Blog: Google has 24 billion items index, considers MSN search nearest competitor, September 2005)

•Web Crawler: > 1012 Dokumente(The Official Google Blog: We knew the Web was Big....., Juli 25, 2008)

•Google Search Index Caffeine umfasst ca.100 Million Gigabytes i.e. 1017 Byte (SMX Video: Google’s Matt Cutts On Caffeine Launch, June 9, 2010,http://searchengineland.com/smx-video-googles-matt-cutts-on-caffeine-launch-43933)

•DeepWeb (Darkweb) schätzungsweise bis zu 550 mal größer als das Surface Web (Bergman, 2001)

The Web is big...


http://www.tnl.net/blog/2005/09/27/google-has-24-billion-items-index-considers-msn-search-nearest-competitor/




http://googleblog.blogspot.com/2008/07/we-knew-web-was-big.html

http://googleblog.blogspot.com/2008/07/we-knew-web-was-big.html

http://searchengineland.com/smx-video-googles-matt-cutts-on-caffeine-launch-43933





...and it‘s getting bigger every minute!



http://www.visualnews.com/2012/06/19/how-much-data-created-every-minute/



25

und damit nicht genug...



26

Problemfeld Informationssuche



27

Problemfeld Informationsextraktion


Vorlesung Semantic Web, Dr. Harald Sack, Hasso-Plattner-Institut, Universität Potsdam 28The Web does not only consist out of text data...



29

A little Semantics goes a long way...Donnerstag, 20. September 12


Automated Audiovisual Analysis

Face DetectionIdentification

TrackingClustering

overlay text

Logo Detection

VisualConcept Analysis

Classification:StudioIndoorPerson

News Show

scenetext

Audio-Mining

structuralanalysis

AutomatedSpeech

Recognitionspeaker

identification



• basiert auf semantisch annotierten Daten, i.e. (textuelle) Metadaten werden mit semantischen Entitäten (Wissensrepräsentation) verknüpft• ermöglicht durch entitätenbasiertes Information

Retrieval eine Suche mit hohem Recall und Precision• durch Ausnutzung semantischer Relationen werden

inhaltsbasierte Kategorisierungen und Filterfunktionen ermöglicht• Semantische Metadaten sind Interoperable Metadaten

durch explizite Semantik• zur inhaltlichen Beschreibung• zur struturellen/technischen Beschreibung

(Multimedia Ontologien)

Semantische Suche



Astronaut Person

Neil Armstrong

Science Occupation

Employment

is a is a

is a

is a

Entities

Ontologies

Named Entity Recognition„locating and classifying atomic elements...intopredefined categories such as names, persons, organizations, locations, expressions of time,quantities, monetary values, etc.“C.J.Rijsbergen, Information Retrieval (1979)

has an



33

Astronaut Person

Neil Armstrong

Science Occupation

Employment

is a is a

is a

is a

Entity Mapping onto the Web of Data

has an


Semantic Multimedia Analysis

Video Analysis /Metadata Extraction

metadata

metadata

metadata

metadatametadata

e.g., bibliographical data,geographical data,encyclopedic data, ..

Entity Mapping

Entity Recognition



35

...was ist eigentlich der Vorteil der semantischen Suche?Donnerstag, 20. September 12


36

Semantische Suche

(1) Präzisierung der Suchergebnisse• durch Verfeinerung der ursprünglichen Suchphrase über mögliche

Kategorisierungen/Oberbegriffe (Query Refinement)

Suchphrase: Bank

Mögliche Erweiterung: Bank ∧ Kreditanstalt oder Bank ∧ Sitzgelegenheit oder Bank ∧ Sediment



37

Semantische Suche

(2) Vervollständigung der Suchergebnisse• durch Erweiterung der ursprünglichen Suchphrase unter Einbeziehung von

Synonymen sowie und Oberbegriffen (Query Refinement)

Suchphrase: Bank

Mögliche Erweiterung: Bank ∨ Kreditanstalt ∨ Sparkasse ∨ ... Bank ∨ Konto ∨ Kredit ∨ ... Bank ∨ Santander ∨ Raiffeisen ∨ ...



38

Semantische Suche

(3) Kategorisierung der Suchergebnisse• durch inhaltsbasierte Filterung nach gemeinsamen Oberbegriffen / Kategorien

(Faceted Search)



39

Semantic SearchFaceted Search


Semantic Searchz.B. Auto-Suggestion Services



41

Semantische Suche

(3) Herstellung von Querverweisem• Bereitstellung von Suchergebnissen, die zwar den Suchbegriff nicht notwendigerweise

enthalten, aber mit diesem in inhaltlichem Zusammenhang stehen

Suchphrase: Neil Armstrongermittelter Oberbegriff: Apollo 11Ausweitung der Suche auf andere Crewmitglieder

dbpedia:Neil_Armstrong

dbpedia:Apollo_11

dbprop:mission

Neil Armstrong

NER

dbpedia:Buzz_Aldrin

dbprop:mission

dbpedia:Michael_Collinsdbprop:mission


http://www2.diego10.com.br/diego









42

Suchen ist nicht immer gleich Suchen


Harald Sack, Hasso-Plattner-Institute for IT-Systems Engineering, 63. Theorietag - Workshop für Algorithmen und Komplexität, FH Brandenburg, 18. 01. 2012

ein einfaches Beispiel:

Ich suche nach dem Buch „Brave New World“ von Aldous Huxley in der ersten in Deutschland erschienenen Ausgabe

Brave New World. - Aldous H U X L E Y.

- The Albatros Continental Library, 47

(Hamburg usw., Albatros Verlag, 1933)

257 S. 8“

II 1, 2506, 34548



44

...aber was, wenn

...mir hat das Buch „Brave New World“ gut gefallen, aber was lese ich als nächstes...?



45

Exploratory Search• What, if the user does not know, which query string to use?• What, if the user is looking for complex answers ?• What, if the user does not know the domain he/she is looking for?• What, if the user wants to know all(!) about a specific topic?

• ...,Browsing‘ instead of ,Searching‘• ...to get an overview• ...enable content based navigation



46

What facts for dbpedia:Brave_New_Worldare relevant?

http://dbpedia.org/page/Brave_New_World

...use heuristicsDonnerstag, 20. September 12

http://dbpedia.org/page/Ernest_Hemingway



47

dbpedia:Brave_New_World

dbpedia-owl:author

dbpedia:Aldous_Huxley

dbpe

dia-

owl:a

utho

r

dbpedia-owl:au

thor

dbpedia-owl:author



48

dbpedia:Brave_New_World

dbpedia-owl:author

dbpedia:Aldous_Huxley

dbpe

dia:

onto

logy

/influ

ence

s

dbpedia:H._G._Wells

dbpedia:ontology/in

fluences

dbpedia:George_Orwell

dbpedia:ontology/influences

dbpedia:Michel_Houellebecq



49

dbpedia:H._G._Wells dbpedia:George_Orwell dbpedia:Michel_Houellebecq

dbpedia-owl:notableWork

dbpedia:Les_Particules_élémentaires


dbpedia:Nineteen_Eighty-Four


dbpedia:The_Time_Machine



50

Problem: Was ist eigentlich wichtig?

http://dbpedia.org/page/Aldous_Huxley

Aldous Huxley

•z.B.., Aldous Huxley•> 400 Fakten (RDF-triples)•> 70 Eigenschaften (properties)•keine Reihenfolge•keine Relevanzbewertungen

•Linked Data beinhaltet ungewichtetes Wissen•ungewichtet = keine Unterscheidung, ob wichtig oder unwichtig

•Entwicklung von Heuristischen Verfahren zur Relevanz-Bewertung von Linked Data Fakten•semantische Graphenanalyse•statistische Verfahren

J. Waitelonis, H. Sack: Towards exploratory video search using linked data, MTAP vol.59-2, 2012, pp. 645-672.A. Thalhammer, M. Knuth, H. Sack: Evaluating Entity Summarizations Using a Game-Based Ground Truth, (ISWC 2012).




http://www.springerlink.com/content/m45r495n634m0q05/

http://www.springerlink.com/content/m45r495n634m0q05/

http://iswc2012.semanticweb.org/

http://iswc2012.semanticweb.org/


51

Explorative Suche - ein einfaches Beispiel

• Suche im Grunddatenbestand nach ,Aldous Huxley‘• Identifikation einer Entität dbpedia:Aldous Huxley• Bestimmung eines geeigneten Properties• Nutzung der gefundenen Properties zur Navigation des Suchraums

Aldous Huxley

Yago:EnglishScienceFictionWriters

rdfs:type


George Orwell

rdfs:type


H.G. Wells

rdfs:type



52

Explorative Suche - vom „glücklichen Finden“

• Finden, was man eigentlich gar nicht gesucht hat, aber schon immer einmal finden wollte....

• glückliches Finden = SerendipitySuchphrase: Ernest HemingwayAusweitung der Suche auf Personen, die etwas mit Ernest Hemingway zu tun haben

dbpedia:Ernest_Hemingway

category:Person

rdf:typedbpedia:Marlene_Dietrich

rdf:type

popstra:dated
















http://mediaglobe.yovisto.com:8080/

Explorative Searchwith yovisto

Waitelonis, Sack: Augmenting Video Search with Linked Open Data, in Proc. I-Semantics 2009.





So long,and Thanks for all the fish.(Douglas Adams)

Contact:Harald SackHasso-Plattner-Institut für SoftwaresystemtechnikUniversität PotsdamProf.-Dr.-Helmert-Str. 2-3D-14482 Potsdam

Homepage:http://www.hpi.uni-potsdam.de/meinel/team/sack.html http://www.yovisto.com/Blog: http://moresemantic.blogspot.com/E-Mail: [email protected] Twitter: lysander07 / biblionomicon / yovisto


http://www.hpi.uni-potsdam.de/meinel/team/sack.html

http://www.hpi.uni-potsdam.de/meinel/team/sack.html

http://www.yovisto.com

http://www.yovisto.com

http://moresemantic.blogspot.com

http://moresemantic.blogspot.com

mailto:[email protected]

mailto:[email protected]

Technology

Der Weg ist das Ziel - Explorative semantische Videosuche