14 Semantische Suche - Semantic Web Technologien WS2010/11

Die nichtkommerzielle Vervielfältigung, Verbreitung und Bearbeitung dieser Folien ist zulässig (Lizenzbestimmungen CC-BY-NC).

VorlesungDr. Harald Sack

Hasso-Plattner-Institut für SoftwaresystemtechnikUniversität Potsdam

Wintersemester 2010/11

Semantic Web Technologien

Blog zur Vorlesung: http://web-flakes.blogspot.com/

http://web-flakes.blogspot.com


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

2

Joseph Wright of Derby:The Alchymist, In Search of the Philosopher’s Stone, 1771

Linked

Data

&

Semant

ic Web

Applic

ations


3

Semantic Web Technologien


4 1. Einführung

2. Semantic Web BasisarchitekturDie Sprachen des Semantic Web - Teil 1

3. Wissensrepräsentation und LogikDie Sprachen des Semantic Web - Teil 2

4. Ontology Engineering

5. Linked Data und Semantic Web Anwendungen

Semantic Web Technologien Vorlesungsinhalt


5

Semant

ic

Search

Albrecht Dürer: Melancholia I, 1514

5.Linked Data und Semantic Web Anwendungen

5.1.Linked Data Engineering

5.2.Semantische Suche

5.2.1.Klassisches Information Retrieval und Multimedia Retrieval

5.2.2.Semantisch unterstütztes Information Retrieval

5.2.3.Explorative Suche


6



7

5. Linked Data und Semantic Web Anwendungen5.2 Semantische Suche / 5.2.1 traditionelles IR

Wie findet man etwas im WWW?


8


Das ,Google-Dilemma‘

• Eingabe einer Suchphrase

• Boolesche Verknüpfung einzelner Suchbegriffe

• Volltextsuche

• Normalisierung (Stemming)


9




10



• Erzeugung einer linearen (nach Relevanz

gewichteten) Ergebnisliste

• TFIDF / PageRank

• Personalisierung (Logdatenanalyse)


11


“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

Klassisches Information Retrieval


12


Klassisches Information RetrievalInformationRetrieval

Bereitstellenvon

Informationen

Suchfunktionenund

Navigationsformen

Interne Wissens-repräsentationen

Verfahren derWissensrekonstruktion

Analyse/Modellierungder im Objektbereich

festgelegtenWissensobjekte

mit dem Zielberuht auf

durch Anwendung von durch Anwendung von

operieren überErgebnisse abgelegt alsAllgemeines Modell des Information Retrievalnach [Kuhlen 1995]

Informations-aufbereitung

Retrieval


13


Information Retrieval Modelle

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=





14



• Boolean Retrieval

• Vector Space Model

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


15





• Probabilistic Model

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)


16





• Probabilistic Model

• Dokumente werden gemäß der Wahrscheinlichkeit ihrer Relevanz bzgl. der Anfrage gewichtet

• IR-System schätzt die Wahrscheinlichkeit der Relevanz bzgl. einer Anfrage ab

Robertson, S. E., Sparck Jones, K.: Relevance weighting of search terms. In Document Retrieval Systems, P. Willett, Ed. Taylor Graham Series In Foundations Of Information Science, vol. 3. Taylor Graham Publishing, London, UK, 143-160, 1988.


17


Evaluation von Information Retrieval Systemen

relevante Dokumente gefundene Dokumente

relevante Dokumente, die gefunden wurden

R P

Recall=| R ∩ P |

|R|

Precision=| R ∩ P |

|P|

Text REtrieval Conference (TREC, seit 1992)veröffentlicht jährlich Challenges in unterschiedlichen Gebieten des Information Retrievals mit zugehörigen Testdaten

Suchmaschinen im WWW


18


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


19


Web-Crawler (Web Robot)

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

Preprocessing und Indexierung


20


Datennormalisierung

Wortidentifikation

Sprachidentifikation

Word Stemming

POS-Tagging

Deskriptorengenerierung

Web Crawler

Datenanalyseund Anlegender Index-

Datenstrukturen


21


Effiziente Indexdatenstrukturen

Aachen

Altavista

Ananas

……

Zustand

Zypern

Indexdatei

AnanasDocID Pos Frequenz GewichtD123 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 Datei


22


Relevanzbewertung (Ranking)

• Ranking erfolgt nach 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,0

2 1,0 0,575 2,275 0,15

3 2,083 0,575 1,1912 0,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


23


Das WWW ist ,ziemlich groß`•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)

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

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


24


Multimedia, Real-Time Data, Sensor Data, ....

in 06/2010: 7 TB/day

in 05/2010: •24 h of video upload / minute•2 Milliarden streamed videos per day


25


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“


26


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• Weltwissen• um Informationen aus der

Text-/Bilddarstellung zu lösen

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

bild.de








27



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

5. Linked Data und Semantic Web Anwendungen5.2 Semantische Suche / 5.2.2 semantisch unterstütztes IR




Diego Ribas da Cunha

Fußballspieler

ist ein

Person

ist eine

Entity Mapping / Named Entity Recognition

Wo finde ich die passende Entität ?






Fußballspieler

ist ein

Person

ist eine

Entity Mapping / Named Entity Recognition


Wo finde ich die passende Ontologie ?


31 Linked Data

http://dbpedia.org/


http://linkeddata.org

http://linkeddata.org


32 Entity Mapping



Fußballspieler

ist ein

Person

ist eine

Entity Mapping

rdf:type dbpedia-owl:SoccerPlayer

rdfs:label Diego Ribas da Cunha

rdf:type dbpedia-owl:Person



33 Entity Mapping



Entity Mapping


http://dbpedia.org/resource/Diego_Ribas_da_Cunha

Aber wie finde ich die passende Entität ?




34 Entity Mapping



Determine possible Entity Mapping Candidates

5. Linked Data und Semantic Web Anwendungen5.2 Semantische Suche / 5.2.2 semantisch unterstütztes IRAber wie finde ich die passende Entität ?

Diego Kolumbus (Vizekönig)

Diego Kolumbus (Seefahrer)

Diego Alberto Milito

Diego von Österreich

Diego Giacometti

Diego Carlone

Diego Baldenweg

Diego Galeri

Diego Barreto

Diego Hypolito

Diego Morais Parcheco

Diego Hostettler

San Diego

Diego Maradonna

San Diego Mariners

USS San Diego

+ 200 mehr...


35 Entity Mapping


Determine possible Entity Mapping Candidates


We have to examine the Context...


36 Entity Mapping


Der Kontext (lat. contextus = verflochten) wird durch das Umfeld eines Wortes (Begriffes) bzw. dessen Zusammenhang mit umgebenden Worten (Begriffen) gebildet.


37 Entity Mapping


Context Analysis

Diego zu Bayern?Ich will nicht den gleichen Fehler wie Klose machen!

Extract Text Data


38 Entity Mapping


Diego zu Bayern?Ich will nicht den gleichen Fehler wie Klose machen!

Determine Named Entities from Text

Diego

Bayern

Fehler

Klose

Create all possible Sets of Mapping Candidates


39Entity Mapping


Diego Bayern Fehler Klose

Create all possible Sets of Mapping Candidates




Diego Alberto Milito


Diego Giacometti

Diego Carlone

Diego Baldenweg

Diego Galeri

Diego Barreto

Diego Hypolito

Diego Morais Parcheco

Diego Hostettler

San Diego

Diego Maradonna

San Diego Mariners

USS San Diego

BayernKönigreich Bayern

Herzogtum Bayern

F.C. Bayern München

FDP Bayern

SPD Bayern

Landtag Bayern

Maximilian I. von BayernAltbayern

Albrecht V. von BayernBayern (Volk)

Bayernliga

Fehler

Sytematischer Fehler

Menschlicher FehlerProgrammfehler

Messfehler

Erratum

Ausnahmebehandlung

Absoluter Fehler

Fehler 1. ArtRelativerFehler

Byzantinischer Fehler

Adolf Fehler

Logischer Fehler

Mittlerer Fehler

Adolf Klose

Miroslav Klose

Hans Helmut Klose

Sepp Klose

MargareteKlose

Bob Klose

Hans Klose

Oscar Klose

Josef Klose

Peter Klose

Walter Klose (Maler)

Senat Klose

Dennie Klose

Alfred Klose

Carl Klose

Hans-Ulrich Klose (CDU)

Wilhelm Klose

Kai Klose

Alfred Klose (Politologe)

Entity Mapping


40



(1) Co-occurence Analysis(2) Semantic Analysis(3) Machine Learning

Diego Kolumbus (Vizekönig) FDP Bayern Programmfehler Hans Helmut Klose

‣For all possible Combinations do:‣Determine the probability of the co-occurence of a

term combination in an arbitrary text document corpus‣Select the combination with the maximum probability

Entity Mapping


41



(1) Co-occurence Analysis(2) Semantic Analysis(3) Machine Learning

‣For all Candidat Entities do:‣Determine semantic network graph‣Select largest connected components





Diego Barreto

Bayern

Königreich Bayern

Herzogtum Bayern

F.C. Bayern München

FDP Bayern

SPD Bayern

Fehler

Sytematischer Fehler

Menschlicher Fehler

Programmfehler Logischer Fehler

Adolf Klose

Miroslav Klose

Hans Helmut Klose Hans-Ulrich Klose (CDU)

Alfred Klose (Politologe)


42 Entity Mapping



Entity Mapping






43


Wie kann ich semantische Annotationen im Information Retrieval nutzen?


44• Semantische Annotationen ermöglichen eine Verbesserung der

traditionellen Schlüsselwort-basierten Suche durch

(1) Erweiterung / Präzisierung der Suchergebnisse(Query String Refinement)

(2) Herstellung von Querverweisen(Cross Referencing)

(3) Nutzung von semantischen Beziehungen zur

• Visualisierung und

• Navigation durch den Suchraum (Explorative Suche)

(4) Herleitung von impliziten Informationen (Reasoning)



45 (1) 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

Suchphrase: Bank

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



46 (1) 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

• Nutzung von Domain Ontologien

• Meronyme, Holonyme

Suchphrase: Bank

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



47 (3) 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: Miroslav Kloseermittelter Oberbegriff: FC Bayern Munich PlayersAusweitung der Suche auf andere Teammitglieder

dbpedia:Miroslav_Klose

category:FC_Bayern_Munich_Players

rdf:type

Miroslav Klose

Entity Mapping

dbpedia:Luiz_Gustavo

rdf:type


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













48


3. Semantik Web Meetup, Berlin, 15.09.2009, Dr. Harald Sack

49 Suchen ist nicht gleich Suchen•Ein einfaches Beispiel:

Ich suche das Buch „Brave New World“ von Aldous Huxleyin der ersten in Deutschland erschienenen Ausgabe...

5. Linked Data und Semantic Web Anwendungen5.2 Semantische Suche / 5.2.3 Explorative Suche


50 Suchen ist nicht gleich Suchen•Wenn man genau weiß, was man sucht, ist es einfach.....

Ich suche das Buch „Brave New World“ von Aldous Huxleyin 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



51 Suchen ist nicht gleich Suchen•...aber was, wenn man nicht genau weiß, was man sucht?

Mir hat das Buch „Brave New World“ von Aldous Huxley gefallen und ich weiß nicht genau, was ich als nächstes lesen sollte....



52 • Was, wenn der Benutzer nicht weiß, welchen Suchbegriff er/sie benutzen soll?

• Was, wenn der Benutzer komplexere Antworten sucht?

• Was, wenn er/sie das Wissensgebiet, über das er sich informieren will, nicht (gut) kennt?

• Was, wenn er/sie wissen möchte, welche Dokumente es insgesamt zu einem speziellen Thema in einem Repository gibt?

• Explorative Suche

• ...,Stöbern‘ statt ,Suchen‘

• ...etwas ,zufällig‘ finden

• ...Serendipity

• ...einen Überblick gewinnen



53 ■How to Explore the Web of Data?

dbpedia:Aldous_Huxley

Wie soll das semantischeNetzwerk um dbpedia:Aldous_Huxleyherum durchsucht werden?

http://dbpedia.org/page/Aldous_Huxley


http://dbpedia.org/page/Ernest_Hemingway



54 ■How to Explore the Web of Data?

Aldous Huxley

Yago:EnglishScienceFictionWriters

rdfs:type

dbpedia:ontology/influences

George Orwell

rdfs:type


H.G. Wells

rdfs:type



55

Aldous Huxley


George Orwell


Kurt Vonnegut

dbpedia:notableWorks dbpedia:notableWorks


■Problem: Was ist eigentlich wichtig?


56

http://dbpedia.org/page/Aldous_Huxley

Aldous Huxley

• z.B.., Aldous Huxley• > 600 Fakten (RDF-triples)• > 80 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





Explorative Suche - ein einfaches Beispiel• Suche im Grunddatenbestand nach ,Aldous Huxley‘

• Identifikation einer Entität dbpedia:Aldous Huxley

• Bestimmung eines geeigneten Properties

57


dbpedia:Aldous_Huxley foaf:name “Aldous Huxley“ .dbpedia:Aldous_Huxleyy rdfs:type yago:EnglishScienceFictionWriters ....dbpedia:Aldous_Huxley dbpedia:ontology/influences dbpedia:H._G._Wells .dbpedia:H._G._Wells rdfs:type yago:EnglishScienceFictionWriters ....dbpedia:George_Orwell dbpedia:ontology/influences dbpedia:Ernest_Hemingway .dbpedia:George_Orwell rdfs:type yago:EnglishScienceFictionWriters .


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

58


Aldous Huxley

Yago:EnglishScienceFictionWriters

rdfs:type


George Orwell

rdfs:type


H.G. Wells

rdfs:type


59

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

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










60



61 1. Einführung

2. Semantic Web BasisarchitekturDie Sprachen des Semantic Web - Teil 1

3. Wissensrepräsentation und LogikDie Sprachen des Semantic Web - Teil 2

4. Ontology Engineering

5. Linked Data und Semantic Web Anwendungen



62


63

Materialien

□Bloghttp://web-flakes.blogspot.com/

□Materialien-Webseitehttp://www.hpi.uni-potsdam.de/meinel/lehre/lectures_classes/semanticweb_ws1011.html

□bibsonomy - Bookmarkshttp://www.bibsonomy.org/user/lysander07/swt1011_14

5. Linked Data und Semantic Web Anwendungen5.2 Semantische Suche



http://www.hpi.uni-potsdam.de/meinel/lehre/lectures_classes/semanticweb_ws1011.html




http://www.bibsonomy.org/user/lysander07/swt1011_12

http://www.bibsonomy.org/user/lysander07/swt1011_12

Technology

14 Semantische Suche - Semantic Web Technologien WS2010/11