Websemantik

Query --> erzeuge Queryrepräsentation --> in suche einfließen

Corpus (mehr. Dok) --> erzeuge Dokumentenrepräsentation --> Index --> in Suche einfließen

Suchergebnis -->Dokumente nach Rang sortierte and Benutzer zurückgeben

• ermittelt die Struktur  der Dokumente/Abfragen,
• wie kann man feststellen welche Dokumente der Abfrage am ehesten entsprechen
• --> Suchmatrix (Ähnlichkeit/Matchingfunktion) nötig
• Ähnlichkeitsfunktion wird durch Suchbegriffe beeinflußt

Bedeutung:

• wird durch Ähnlichkeitsfunktion bestimmt
• soll das Userbedürfnis (richtiges thema, Neuheit) stillen
• kein Objektives Mß (alter d. Dokuments, vertrauenswürdigkeit des Dokuments?

Qualität:

dadurch bestimmt, wie gut wurde das Userbedürfnis abgedeckt wurde

Vergleich SQL:

• SQL kann benutzt werden um Retrieval-Model zu implementierten
• Korrek. Evaluierung einer Query Language Expresseion

1. QUERY
   • Repräsentation was Benutzer sucht (Liste von Wörtern od. Phrase)
   • nicht mit SQL verwechseln!
2. DOCUMENT
   • Informationsobjekt, welches Benutzer abrufen will
3. CORPUS/COLLECTION
   • Menge von Dokumenten
4. INDEX
   • Informationsobjekt, welches Abfragen erleichtert
5. TERM
   • Wort od. Begriff welches im DOKUMENT od. QUERY vorkommt
6. DICTIONARY
   • eine sortierte Liste aller TERME im CORPUS, vom INDEX benutzt

• abschneiden unerwünschter Zeichen/Markups (Htmltags zb.)
• Tokenization
• Stopwörter-Entfernung
• Stemming
• Synonym-Matching
• Indizierung

Prozess des Herausbrechens von Wörtern/Phrasen/Symbolen aus Textstrom

• passiert nicht auf Wortebene
• nicht-trivial f. bestimmte domänen (zB Biomedizin)
• Tokens: kleinste Einheit von aussagekräftigen Text
• Tokenizer beruht auf simplen Heuristiken
  • z.B. Alle benachbarten Strings des Alphabets sind Teil eines Tokens
  • Whitespaceentferung im Token oder auch nicht

heuristischer Prozess der die Wortenden abschneidet

verschiedene Wortformen haben selbe Bedeutung

• z.b. search, searching

Token werden zu Wurzelwörtern reduziert

• zb. computational -> compute

=StemmingAlgorithmus

speziell f. engl. Sprache, basierta auf suffix Entfernung

5 Phasen der Wortreduktion (in jeder Phase existieren unterschiedliche Konventionen um Regeln zu selektieren)

• z.b. selektiere die Regel von jeder Regelgruppe welche das längste Suffix des Worts zutrifft
  • sses-> ss (bosses->boss)
  • ies --> i (bodies->bodi)
  • ss->ss (caress->caress)
  • s-> NULL (cats->cat)
• Wortlängensensitiv!
  • cement->cement (ce wäre zu kurz)

komplexer als Stemming, benutzt morphologische Analyse, benötigt Vokabular um zur Basisform (Lemma) zu finden.

reduziert "gebeugte" bzw. abgeleitete Wörter zu einer Basisform

• am, are, is -> be
• car, cars, car's, cars -> car
• destruction->destroy

Entfernung häufiger (Stop)-wörter: a, the, it

Stoppwörter: Wörter die zu oft vorkommen in dokumenten (daher wenig Semantik) haben.

• zb. Artikel, Präpositionen, Konjunktionen, Verben, Adverben, Adjektive

Entfernung nötig um Indexgröße nich zu groß werden zu lassen.

manchmal gefährlich:

"to be or not to be"

=Datenstruktur, welche Abfragen schneller in Dokumenten findet.

• Indextyp: hängt von Benutzerabfrage ab
• Index-Erstellung:
  • Manuelle Indizierung (von Menschen)
    • Vorteil: Beziehungen/Konzepte zwischen scheinbar unterschiedlichen Themen herstellbar
  • Automatische Indizierung
    • invertierter Index:
      • Mappt Terme zu Dokumenten
      • erlaubt Benutzer dokumente die deren abfrage entsprechen, aufzufinden
    • erweiterter invertierter Index enthält auch die Häufigkeit und auch die Positionen des Terms im Dictionary (siehe Grafik) inner halb Postingliste

mappt Dokumente zu Termen

benutzer kann nicht nur Dokumente, die der Abfrage entsprechen, finden sondern erhält auch eine "Ranking" der zutreffensten Dokumente

Zeilen: spaltennummern, Spalten: Begriffe

da viele Begriffe nicht oft Vorkommen --> eigene Datenstruktur entwickeln

Annahme: t eindeutige Terme bleiben nach Preprocessing über

diese orthogonalen Terme formen einen mehrdimensionalen Vektorraum (Dimension=V=|Vokabular|)

jedem Term (i) innerhalb eines Dokuments/einer Abfrage wird ein reelwertiges Gewicht (w_ij) zu gewiesen.

Dokumente u. Abfragen werden als t-dimensionale Vektoren dargestellt.

Grafik:

• Terme sind die Achsen des Raums
• Dokumente sind Punkte od. Vektoren innerhalb dieses Raums
• die meisten vektoren sind 0

Als Maß wird sowohl der lokale (tf) als auch der globale Worthäufigkeit (idf) herangezogen

1) für jedes Dokument und Abfrage die Vektorlängen berechnen

2) alle innerprodukte berechnen

3) die Ähnlichkeitswerte berechnen

4) Absteigend sortieren 

Beobachtungen:

simpler mathematischer Ansatz -berücksichtigt (tf) lokale als auch globale (idf) Worthäufigkeiten

bietet partielles matching und rang im ergebnis

häufige Terme (a, in,of) tendieren dazu niedriges Gewicht zu bekommen --> d.h. Modell sagt korrekt voraus, dass sehr gebräuchliche Terme keine Relevanz haben

Nachteile:

VSM ist rechenintensiv

keine semantische Wortinfos

"Bag of Words" Modell

• fehlende syntaktische Info (Satzstruktur, Wortreihenfolge, Nachbarinfos)

Annahme der Term-Unabhängigkeite (Synonyme werden ignoriert)

Fehlende Kontrolle der Boolschen Abfrage

• zB Erzwingen des Vorkommens eines terms in einem Dokument
• Bei einer zwei Term Abfrage A B würde das Dokument welches A öfter beinhaltet welches A + B beinhaltet bevorzugt werden

Konvertierte alle dokumente in corpus D zu tf-idf gewichteten Vektoren d_j

Konvertiere Abfrage zu tf-idf gewichteten Vektor

for each d_j in D do
compute score s_j = cosSim(d_j,q)

Sortiere Dokumente abnehmend nach Score

Präsentiere die top gerankten Dokumente dem Benutzer

dem Indextermen (df_i) werden Postingg lists hinzugefügt

in einem zweiten Schritt werden log(N/df_i)  und die Vektorlänge der Dokumente gespeichert

die TermFrequenz  tf_t,d des Terms t im Dokument d ist definiert als Anzahl von t in d.

Wir wollen tf benutzen um query Dokument Scores zu ermitteln.

Problem: ein Term der 10x vorkommt ist nicht 10x so relevant.

Häufigere Terme innerhalb eines dokuments sind wichtiger (indikativer)

Normalisierung der Termfrequenz (tf) durch Division des am häufig vorkommenden Wertes im Dokument:

tf_ij = f_ij/max,{f_ij}

rare Terme sind informativer als häufige Terme (vgl. Stoppwörter)

ein Dokument welches einen raren Term (der in der Abfrage vorkommt) enhält, ist relevanter für diese Abfrage

für häufige terme wollen wir pos. Gewichte, diese sollen aber niedriger gewichtet sein als für rare Terme

--> DocumentFrequency(df) wird benutzt um dies im Score zu berücksichtigen

df(<=N) ist die Anzahl der Dokumente welche den Termn beinhalten

Terme die in  vilen verschiedenen Dokumenten vorkommen sind weniger indikativ

Df_i = Dokument Frequenz des Term i (Anzahl der Dok. wo i enthalten ist)

Idf_{i = Inverse dok. Frequenz des  Term i; Indikator der Diskriminanz (Unterscheidung); log dämpft den Relativeffekt von tf.}

Idf_i = log₂(N/df_i)    .... N... totale Anzahl der dokumente

=typischer kombinierter Term -Wichtigkeitsfaktor tf-idf-Gewichtung

w_ij = tf_ij

idf_i = tf_ijlog₂(N/df_i)

--> Ein Term der häufiger vorkommt innerhalb eines Dokuments aber kaum in den anderen, bekommt mehr Gewicht

--> tf-idf hat deterministisch bewiesene hohe Aussagekraft, ist der am meisten benutzte Gewichtungsansatz für Vector Space Modelle.

3 Dokumente

wird auch tf-idf gewichtet (wie Dokumente)

Berechnung der Gewichte des Abfrage Vektors:

w_iq = tf_iq * log₂(N/df_i)

tf_iq hat häufig den Wert 1 da terme kaum mehr als einmal pro Abfrage benutzt werden

Funktion, die den Grad der Ähnlichkeit zweier Vektoren berechnet, wird in IR benutzt um die Ähnlichkeit zw. Abfrage und Dokument festzustellen.

• Euklidsche Distanz
• Inner-Product
• Cosinus-Ähnlichkeit

Euklidsche Distanz:

funktioniert nicht so gut da trotz Vektorenähnlichkeit oft große Distanzwerte rauskommen (siehe Grafik).

misst den winkel zwischen zwei Vektoren (normalisiert von der Vektorlänge)

warum normalisiert:

cosinus-Normalisierung reduziert den Einfluß von großen Dokumenten, aber favorisiert kleine.

jedes Element des Dokumentvektors wird mit jedem Element des Abfragevektors verglichen und dann summiert (siehe Grafik).

Probleme:

favorisiert große dokumente mit großen anzahl an termen

misst nur wieviele Terme matchen, aber NICHT wieviel NICHT matchen.

Vordefinierte Liste von Termen

Nur anerkannte Terme werden indiziert

entfernt inhärente Mehrdeutigkeit

erhöht Geschwindigkeit eines IR

eingeschränkte Vokabularien div. Domänen ermöglicht

es gibt 4 Typen eingeschränkter Vokabularien

• Listen
• Synonym Ringe
• Taxonomien
• Thesaurus

eingeschränkte Menge von termine in simpler alphabetischer Reihenfolge

zur kleinen anzahl verwendbar z.B. Bundesstaaten

Menge von Symbolen für jeden Term

keiner ist ein präferierter Term

gebräuchlich in suchmaschinen

oft in Umgebungen mit eingeschränkten Vokabular verwendet

Hierarchisches Klassifikationssystem

jeder Term mit jedem verbunden  solange dies kein höherer Term ist

Supertyp-Subtyp Beziehungen möglich: Generalisierung-Spezialisierung

Alle Terme sind in einer einzigen großen hierarchischen Struktur organisiert

enthält Merkmal einer Taxonomie plus folgende mögliche Beziehungsarten:

hierarchisch (schmaler/breiter Term)

Assoziativ (zugehöriger Term)

Equivalenz

Nichtpräferierter Term der zu einem akzeptierten umgeleitet wird

ermöglicht es eine Frage zu stellen, welcher ein Boolscher ausdruck (e) ist.

Schlüsselwörter:

OR (e1 oder e2) = Vereinigungsmenge

AND (e1 und e2) = Schnittmenge

BUT (e1 aber e2) = Unterschied: e1 erfüllt aber e2 nicht

Negation nur mittels BUT

Nachteile: naive Benutzer haben Probleme mit der 

bei AND mit n Termen:

für jeden der n Terme ermittle Posting, dann ANDE sie zusammen

Prozessierung anhand der Reihenfolge der Häufigkeit (aus Dictionary)- Beginn mit kleinster Menge (siehe Grafik)

sehr rigide AND (alles) OR irgendein

boolsche Logik für Benutzer nicht immer verständlich

Anzahl der ermittelten Dokumente nur schwer einschränkbar

Ranking des Outputs schwierig zu erstellen, dazu gibt es verschiedene Ansätze

1. einfacher Ansatz:
   • Jaccard coeffizient
2. Statistische Modelle:

• Vektorspacemodell
• Wahrscheinlichkeitsmodell

Anzahl der Elemente der Durchschnittsmenge / Anzahl der Menge der Vereinigungsmenge.

z.B:

Query: "The sky is blue"

Document: "sky hack download"

Jacard (q,d) = 1/6

Probleme:

Berücksichtigt nicht die Häufigkeit des Vorkommens eines Terms. (weniger oft vorkommende sind häufig informativer)

Prodzuiert als Output eine Liste von Dokumenten gereiht nach der ermittelten Relevanz

Zwei Modelle: Vektorspacemodell, Probilistisches Retrieval Modell (Wahrscheinlichkeit)

Auffindung basiert auf der Ähnlichkeit zwischen Abfrage und Dokumenten (Häufigkeit des Vorkommens von schlüsselwörtern in abfrage und Dokument)

Dokument ist "Bag of words": ungeordnet, Wörter inkl. deren Häufigkeiten, mehrfaches Vorkommen desselben Elements erlaubt

Keine Boolsche Bedingung in Abfrage  (ungewichtete Abfrageterme)

Ausführen des Relevanzfeedback schwierig (Wie soll einBenutzer Abfrage modifizieren  wenn ein Dokument als relevant/irrelvant identifiziert wurde?)