Gbv09 Keynote Wie Sie schon immer finden wollten, was Sie noch nie gesucht haben - Paradigmenwechsel in der (Web)Suche

Dr. Harald SackHasso-Plattner-Institut für SoftwaresystemtechnikUniversität Potsdam13. Verbundkonferenz des GBVHamburg, 09. September 2009

„Wie Sie schon immer finden wollten, was Sie noch nie gesucht haben“Paradigmenwechsel in der (Web)Suche

13. Verbundkonferenz des GBV, Hamburg, 09.-10.09.2009, Dr. Harald Sack, HPI Potsdam

■ Promotion Uni Trier, 2002: formale Verifikation

■ 2002-2008: PostDoc FSU Jena

■ 2007-2009: Gastwissenschaftler am HPI

■ 2009- : Senior Researcher am HPI

■ Forschungsschwerpunkte:

□ Semantic Web Technologien

□ Multimedia Retrieval

■ Videosuchmaschine yovisto.com

■ Projekt MEDIAGLOBE/THESEUS

2

Dr. Harald Sack


3

Wie Sie schon immer finden wollten, was Sie noch nie gesucht haben

•Das Dilemma der Schlüsselwort-basierten Suche

• klassisches Information Retrieval

• Suchmaschinen im World Wide Web

• Suche in Audiovisuellen Daten

•Semantische Suchtechnologien

• Semantic Web Technologie

• Semantisch unterstütztes Information Retrieval

• Explorative Suche in Audiovisuellen Daten


Das „Google Paradigma“4

• Eingabe einer Suchphrase

• Boolesche Verknüpfung einzelner Suchbegriffe• Volltextsuche

• Normalisierung (Stemming)

Das Dilemma der Schlüsselwort-basierten SucheDas „Google-Paradigma“



Das Dilemma der Schlüsselwort-basierten SucheDas „Google Paradigma“






• Erzeugung einer linearen (nach Relevanz gewichteten) Ergebnisliste

• TFIDF / PageRank

• Personalisierung (Logdatenanalyse)




• Erzeugung einer linearen (nach Relevanz gewichteten) Ergebnisliste

• TFIDF / PageRank

• Personalisierung (Logdatenanalyse)



7



•klassisches Information Retrieval








8

Das Dilemma der Schlüsselwort-basierten Sucheklassisches Information Retrieval

“Information-Retrieval Systeme • verarbeiten Dateien mit Informationsressourcen und

Informationsanfragen, • identifizieren und liefern aus diesen Dateien bestimmte

Informationsressourcen als Antwort auf eine Informationsanfrage. • Das Finden (Retrieval) bestimmter Ressourcen hängt von der

Ähnlichkeit der Ressourcen und den Anfragen ab, gemessen am Vergleich bestimmter Attributwerte.”

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

Menge von Anfragen

informationrequests

Menge von Dokumenten

files of records

Indexierungs-sprache

similarityIndexierungAnfrage-

formulierung


Information Retrieval Modelle9

Dominik Kuropka: Modelle zur Repräsentation natürlichsprachlicher Dokumente. Ontologie-basiertes Information-Filtering und -Retrieval mit relationalen Datenbanken, Advances in Information Systems and Management Science, Bd. 10, Logos Verlag, Berlin, 2004.


http://www.logos-verlag.de/cgi-local/engtransid?page=/Buchreihen/amsis.html&lng=eng&id=





Information Retrieval Modelle

• Boolean Retrieval

• Vector Space Model

• Probabilistic Model

10

A B

C(A ∧ ¬B) ∧ C

• verwendet Aussagenlogik als Retrievalsprache• erlaubt Selektion und Verknüpfung beliebiger

Dokumentenmengen aus einer einer Dokumentenkollektion• mit Hilfe Boolescher Junktoren (Suchoperatoren) • einfache Implementierung• keine differenzierte Termgewichtung möglich• keine Rangreihenfolge der Ergebnisse (Ranking)



Information Retrieval Modelle

• Boolean Retrieval

• Vector Space Model

• Probabilistic Model

11

Deskriptor1

Deskriptor2

Deskriptor3

Dokument = (2,4,2)Suchabfrage = (1,0,0)

Dokument

Suchanfrage

2

2

4

Bsp.: n = 3

ρ

• Dokumente und Anfragen werden als Punkte in einem hochdimensionalen, metrischen Vektorraum repräsentiert

• Zum Retrieval wird die Distanz zwischen Suchanfrage- und Dokumentenvektor verwendet

• Relevanzbewertung (Ranking) erfolgt nach der ermittelten Distanz

• Differenzierte Termgewichtung möglich• lineare Termanordnung im Dokument geht

verloren • mangelnde semantische Sensitivität

(Vokabularabhängigkeit)G. Salton, A. Wong, C. S. Yang: "A Vector Space Model for Automatic Indexing," Communications of the ACM, vol. 18, nr. 11, pp. 613–620, 1975.


http://en.wikipedia.org/wiki/Gerard_Salton

http://en.wikipedia.org/wiki/Gerard_Salton

http://www.cs.uiuc.edu/class/fa05/cs511/Spring05/other_papers/p613-salton.pdf

http://www.cs.uiuc.edu/class/fa05/cs511/Spring05/other_papers/p613-salton.pdf


Evaluation von Information Retrieval Systemen12

relevante Dokumente gefundene Dokumente

relevante Dokumente, die gefunden wurden

R P

Recall=| R ∩ P |

|R|

Precision=| R ∩ P |

|P|



13




•Suchmaschinen im World Wide Web






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


14

Das Dilemma der Schlüsselwort-basierten SucheSuchmaschinen im WWW


15 Das WWW ist „ziemlich groß“•ca. 25 x 109 in Suchmaschinenindizierte 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)

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

Probleme:• Aktualität des Suchmaschinenindex• syntaktische / semantische Inkonsistenzen im Suchmaschinenindex• Skalierbarkeit der Suchmaschinenanwendung• kann man der Information auch trauen...?


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


16 Problemfeld 1: Informationssuche

•Keyword-Suche führt zu vielen nicht relevanten Ergebnissen•Bedeutungsunterschiede•Homonyme•unterschiedlicher Kontext

•Keyword-Suche findet nichtalle relevanten Ergebnisse•Synonyme• fehlende Kontextpräzisierung

Suchbegriff: „Golf“



16 Problemfeld 1: Informationssuche

•Keyword-Suche führt zu vielen nicht relevanten Ergebnissen•Bedeutungsunterschiede•Homonyme•unterschiedlicher Kontext

•Keyword-Suche findet nichtalle relevanten Ergebnisse•Synonyme• fehlende Kontextpräzisierung

Suchbegriff: „Golf“



17 Problemfeld 2: Informationsextraktion• kann nur von menschlichem

“Agenten“ korrekt durchgeführt und bewertet werden

•heterogene Anordnung von Information

•Software-Agent verfügt nicht über• Kontextwissen• Weltwissenum Informationen aus der Text-/Bilddarstellung zu lösen

• implizites Wissen, muss durch logische Schlussfolgerungenaus der Kombination vorhandener Informationen ermittelt werden

bild.de



18





•Suche in Audiovisuellen Daten






19 Wie findet man etwas in einem audiovisuellen Archiv?

Das Dilemma der Schlüsselwort-basierten SucheSuche in audiovisuellen Daten

• Damit audiovisuelle Daten einer computergestützten gezielten Suche zugänglich werden, müssen Beschreibungen, Schlüsselwörter, etc. üblicherweise Textform vorliegen.


19 Wie findet man etwas in einem audiovisuellen Archiv?


• Damit audiovisuelle Daten einer computergestützten gezielten Suche zugänglich werden, müssen Beschreibungen, Schlüsselwörter, etc. üblicherweise Textform vorliegen.

Manuelle Analyse und Annotation


20 Retrieval in Audiovisuellen (zeitabhängigen) Daten

•

automatische inhaltliche Analyse ist • schwierig und• berechnungs-/speicheraufwändig

© Friedrich Wilhelm Murnau Stiftung, DFI




•






•






•


Marlene Dietrich





•


Marlene Dietrich ????





•


Marlene Dietrich ????????





•


Marlene Dietrich ????????

„...ich bin von Kopf bis Fuß...“

{



yovisto.com• Videosuchmaschine mit dem Schwer-

Punkt akademischer Lehrveranstaltungen

• aktuell mehr als 5.000 Vorlesungen undwissenschaftliche Vorträge aus der ganzen Welt

• automatische Segmentierung und Videoanalyse

• benutzergenerierte Co-Annotation

• Social Tagging

• Diskussionen

• Rezensionen

• Wikis

• Lernmaterialien

• Zielgenauer Zugriff auf gesuchte Videoinhalte


21

Das Dilemma der Schlüsselwort-basierten SucheYovisto.com - Akademische Videosuche

www.yovisto.com

http://www.yovisto.com



Inhaltsbezogene Videoanalyse■ Ergebnis: Videosegmente mit zugeordneten, zeitbezogenen

Metadaten

■ Metadaten setzen sich zusammen aus kombinierten Low Level/ High Level Deskriptoren

■ Metadaten als Basis für traditionelles Information Retrieval

22

ZeitMetadaten

Metadaten

Metadaten

Metadaten Metadaten

Metadaten



23 Automatische Metadatenextraktion



23

ICR / OCR

Automatische Metadatenextraktion



23

ICR / OCR

ASR




23

ICR / OCR

ASR

Dic

tiona

ry

Keyterm Spotting




24 Benutzergenerierte Metadaten□ automatische Analyse nur begrenzt leistungsfähig

□mangelnde Genauigkeit / Vollständigkeit

□ Benutzergenerierte Metadaten können qualitativ zuverlässiger sein

□ autoritative Metadaten

□ strukturierte Daten

□ unstrukturierte (textuelle) Daten

□ nicht-autoritative Metadaten

□ Tags

□ Kommentare

□ Diskussionen

□ Rezensionen

□ Feedback



25











26 Die ursprüngliche Vision des World Wide Web

„The Web was designed as an information space, with the goal that it should be useful not only for human-human communication, but also that machines would be able to participate and help… “

Voraussetzung:• Inhalte können maschinell gelesen und korrekt

interpretiert (= verstanden) werden

Tim Berners-Lee, Semantic Web Roadmap, Sept 1998

Wie kann das funktionieren?

Semantische SuchtechnologienSemantik Web Technologien


27 Inhalte im Web maschinell „verstehen“•um Inhalte im Web maschinell „verstehen“ zu können werden zwei unterschiedliche Ansätze verfolgt

Natural Language Processing• Natürliche Sprache soll mit

Techniken der Linguistik und Statistik analysiert werden

• Die Bedeutung (Semantik) soll implizit (oder auch explizit) daraus erschlossen werden

• Techniken kommen im klassischen Information Retrieval (WWW-Such-maschinen) zum Einsatz

Semantic Web• (Natürlichsprachliche) Web-

Inhalte werden explizit mit Hilfe von semantischen Metadaten annotiert

• semantische Metadaten tragen die Bedeutung (Semantik) der Web-Inhalte und lassen sich maschinell lesen und korrekt interpretieren



28 Inhalte im Web maschinell „verstehen“

Text: „Diego zu Bayern?“

Diego Ribas da Cunha (Instanz)

Fußballspieler

ist ein

(Klasse)

Person

ist eine

(Klasse)

Superklasse

Subklasse

ist eine

Klassen-zugehörigkeit

Entitäten-zuweisung

• Die Bedeutung (Semantik) der Klassenmuss ebenfalls explizit definiert werden.

• Bedeutung wird über geeignete Wissens-repräsentationen (Ontologien) kodiert



29 Ontologien als Wissensrepräsentation

Symbol Gegenstandsteht für

„Golf“Ogden, Richards, semiotisches Dreieck, 1923

Konzept

ruft hervor referenziert

verwendengemeinsames Konzept



30 Ontologien als Wissensrepräsentation

„Philosophische Disziplin, die sich primär mit dem Sein, dem Seienden als solchem und mit den fundamentalen Typen von Entitäten beschäftigt…“ (wikipedia)

"An ontology is an explicit, formal specification of a shared conceptualization. The term is borrowed from philosophy, where an Ontology is a systematic account of Existence. For AI systems, what ‘exists’ is that which can be represented.“

(Thomas R. Gruber, 1993)

Konzeptualisierung: abstraktes Modell (Domäne, identifizierte relevante Begriffe, Beziehungen)Explizit: Bedeutungen aller Begriffe definiertFormal: maschinenverstehbarGemeinsam: Konsens bzgl. Ontologie



Das Semantic Web - Datenzentrierte Verarbeitung •Die Bedeutung der Informationen (Semantik) wird durch standardisierte Wissensrepräsentationen (Ontologien) explizit formalisiert (strukturiert)

• Damit wird es möglich,

•die Bedeutung der Informationen maschinell zu verarbeiten

•unterschiedliche (heterogene) Daten miteinander in Beziehung zu setzen

•implizite (nicht offensichtliche) Information aus der vorhandenen (offensichtlichen) Information automatisch zu folgern

31

Das Semantic Web ist eine Art globaler Datenbank, dieein universales Netz semantischer Aussagen bereit hält



Das Semantic Web - Architektur32

URI / IRI

XML / XSDData Interchange: RDF

RDFS

Ontology: OWL Rule: RIF

Query:SPARQL

Proof

Unifying Logic

Cry

pto

Trust

Interface & Application



Das Semantic Web - Architektur32

URI / IRI

XML / XSDData Interchange: RDF

RDFS

Ontology: OWL Rule: RIF

Query:SPARQL

Proof

Unifying Logic

Cry

pto

Trust

Interface & Application

Current Research



Linked Data - Datenzentrierte Verarbeitung •Ziel des Semantic Web: ...to create a ,Web of Data‘

33



Linked Data - Datenzentrierte Verarbeitung •Ziel des Semantic Web: ...to create a ,Web of Data‘

33



34






• yovisto.com - Akademische Videosuche



•Semantisch unterstütztes Information Retrieval


35 Semantisch unterstütztes Information Retrieval• Semantische Annotationen ermöglichen eine Verbesserung der

traditionellen Schlüsselwort-basierten Suche durch

• Erweiterung / Präzisierung der Suchergebnisse

• Herleitung von impliziten Informationen

• Herstellung von Querverweisen

• Nutzung von semantischen Beziehungen zur

• Visualisierung und

• Navigation durch den Suchraum (Explorative Suche)

Semantische SuchtechnologienSemantisch unterstütztes Information Retrieval


36 Erweiterung der Suchergebnisse• Keyword-basierte Suche liefert nicht alle inhaltlich relevanten

Suchergebnisse zu einer Suchphrase, da Synonyme, Metaphern und Umschreibungen den gesuchten Inhalt mit anderen Termen beschreiben.

• Erweiterung der ursprünglichen Suchphrase (Query Refinement)• Nutzung von Wörterbüchern und Thesauri

• Synonyme, Ober- und Unterbegriffe

• Nutzung von Domain Ontologien

• Meronyme, Holonyme, Assoziationen



36 Erweiterung der Suchergebnisse• Keyword-basierte Suche liefert nicht alle inhaltlich relevanten

Suchergebnisse zu einer Suchphrase, da Synonyme, Metaphern und Umschreibungen den gesuchten Inhalt mit anderen Termen beschreiben.

• Erweiterung der ursprünglichen Suchphrase (Query Refinement)• Nutzung von Wörterbüchern und Thesauri

• Synonyme, Ober- und Unterbegriffe


• Meronyme, Holonyme, Assoziationen

Suchphrase: Bank

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



37 Präzisierung der Suchergebnisse• Keyword-basierte Suche liefert zu viele inhaltlich nicht relevante

Suchergebnisse zu einer Suchphrase, da Suchbegriffe mehrere Bedeutung und in unterschiedlichem Kontext/Pragmatik genutzt werden.

• Verfeinerung der ursprünglichen Suchphrase (Query Refinement)• Nutzung von Wörterbüchern und Thesauri

• Homonyme mit Hilfe von Ober- und Unterbegriffen disambiguieren


• Meronyme, Holonyme



37 Präzisierung der Suchergebnisse• Keyword-basierte Suche liefert zu viele inhaltlich nicht relevante

Suchergebnisse zu einer Suchphrase, da Suchbegriffe mehrere Bedeutung und in unterschiedlichem Kontext/Pragmatik genutzt werden.

• Verfeinerung der ursprünglichen Suchphrase (Query Refinement)• Nutzung von Wörterbüchern und Thesauri

• Homonyme mit Hilfe von Ober- und Unterbegriffen disambiguieren


• Meronyme, Holonyme

Suchphrase: Bank

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



38 Herstellung von Querverweisen□ Bereitstellung von Suchergebnissen, die zwar den Suchbegriff nicht

notwendigerweise enthalten, aber mit diesem in inhaltlichem Zusammenhang stehen

□ Nutzung von Domain Ontologien

□ Nutzung von Thesauri und Kookurrenzanalysen repräsentativer Dokumentenkorpora

Suchphrase: Hemingwayermittelter Oberbegriff zu Hemingway: amerikanischer AutorAusweitung der Suche auf andere amerikanische Autoren

dbpedia:Ernest_Hemingway

dbpedia:AmericanNovelists

rdf:type

Hemingway

Instanzerkennung

dbpedia:Edgar_Allen_Poe

rdf:type


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









Explorative Suche• Abkehr vom „Google Paradigma“

• Visualisierung von Querverbindungen zwischen

• Suchbegriffen (Ontologieebene)

• Suchergebnissen (Instanzebene)

• Ermöglicht es dem Benutzer

• Suchergebnisse „zufällig“ zu entdecken, die er eigentlich gar nicht gesucht hat (Serendipity)

• einen besseren Überblick über den Suchraum / Ergebnisraumzu gewinnen

39



Explorative Suche - ein einfaches Beispiel• Suche im Grunddatenbestand nach ,Ernest Hemingway‘

• Identifikation einer Entität dbpedia:Ernest_Hemingway

• Bestimmung gleichartiger Entitäten

40

dbpedia:Ernest_Hemingway foaf:name “Ernest Hemingway“ .dbpedia:Ernest_Hemingway rdfs:type dbpedia:class/yago/AmericanNovelist .





• Bestimmung gleichartiger Entitäten

40

dbpedia:Ernest_Hemingway foaf:name “Ernest Hemingway“ .dbpedia:Ernest_Hemingway rdfs:type dbpedia:class/yago/AmericanNovelist .

Finde weitere Ressourcen vom selben Typ, d.h.(1) finde weitere amerikanische Autoren(2) finde Ressourcen (z.B. Videos) mit weiteren amerikanischen Autoren





• Bestimmung eines geeigneten ,Properties‘

41

dbpedia:Ernest_Hemingway foaf:name “Ernest Hemingway“ .dbpedia:Ernest_Hemingway rdfs:type dbpedia:class/yago/AmericanNovelist ....dbpedia:Ernest_Hemingway dbpedia:ontology/influences dbpedia:Ezra_Pound .dbpedia:Ezra_Pound rdfs:type dbpedia:class/yago/AmericanNovelist ....dbpedia:J._D._Salinger dbpedia:ontology/influences dbpedia:Ernest_Hemingway .dbpedia:J._D._Salinger rdfs:type dbpedia:class/yago/AmericanNovelist .






41







42







43






• Bestimmung eines geeigneten „Properties“

•Nutzung des Properties zur Navigation/Visualisierung

• Erweitere Suche mit asoziierten Entitäten

44

dbpedia:ontology/influences dbpedia:ontology/influences

Ezra Pound Ernest Hemingway J.D. Salinger



45

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


29


45



29


45



29

history


45



29

history

search term


45



29

history

search term

related resources with properties





• yovisto.com - Akademische Videosuche



• semantantisch unterstütztes Information Retrieval


46

Vielen Dank für Ihre Aufmerksamkeit !Fragen....?

Links:• HPI Homepage: http://www.hpi.uni-potsdam.de/meinel/sack.html• Yovisto: www.yovisto.com• Blogs: http://moresemantic.blogspot.com/ http://yovisto.blogspot.com/




http://moresemantic.blogspot.com

http://moresemantic.blogspot.com

http://yovisto.blogspot.com

http://yovisto.blogspot.com

Education

Gbv09 Keynote Wie Sie schon immer finden wollten, was Sie noch nie gesucht haben - Paradigmenwechsel in der (Web)Suche