A. Prüfungsfragen zu Einführende Fragen Flashcards
Wie funktioniert eine ISM (Internet-Suchmaschien)?
Eine ISM besteht aus Komponenten:
- Crawler:sammelt Dokumente
- Parser: Dokument in Wörter zerlegen,
- Indexer: dann ling. Alg angewenden und gewichten.
- Datenbank: Ergebnisse von Parser speichern
- Searcher: über Browser an Such-Interface zugreifen.
Eine ISM ist eine Art von Information Retrieval System IRS. In dem Fall die ISM crawlt, parst, und indexiert den Inhalt von Webseiten. Die Dokumente, die gesucht werden können sind Webseiten.
In dem Searcher:
Der Benutzer erkennt dass ihm Wissen fehlt (Anomalous State of Knowledge) und versucht eine Anfrage zu formulieren. Die Anfrage enthält Vagtheit, weil der Benutzer nicht genau spezifieren kann, was er möchte.
Seine Anfrage hat eine Repräsentation (welche die IRSystem/Suchmaschine mit linguistischen Funktionen und Stoppworteliminieren aufbereitet hat) und eine Beschreibung. Die Dokumente im IR-System die vom Parse/Indexer aufbereitet wurde haben auch eine Repräsentation und Beschreibung. Diese Beschreibung ist unsicher weil das Wissen über die Objekte unzureichend sind.
Das IR-System vergleicht die Beschreibung von Dokumente mit Beschreibung von Anfrage und wendet Algorithmen an (probabilistische (Bsp VRM, boolsche), nicht-probabilistische (BIR, BM25, neuere-probabilisitische Modelle (LTR, IPRP) um eine Ergebnisliste für den Benutzer zu erstellen. Ausser bei dem booleschen Retrieval gibt es immer eine Rangordnung and geordnete best-matches werden dem Benutzer gezeigt.
Das IR-System kann hier auf die Ergebnisliste eine Evaluierung durchführen. Wichtig hier ist eine gute Suchqualität (Precision und Recall).
Die Suchmaschine präsentiert die Ergebnisse (gerankte relevante Webseiten) dem Benutzer. Wenn die ISM/IR-System statisch ist, dann wird höchsten Relevanz Feedback (z.B. bei Vektor-Raum-Modell) benutzt, um aktuelle Ergebnisse zur aktuellen Anfrage zu optimieren. Wenn es aber ein Iteraktives Retrieval ISM/IR-System ist, dann wird dem Benutzer durch die Graphische Benutzeroberfläche Optionen Angeboten, um die Suchergebnisse zu verbessern (Strategische Unterstützung /Bates) z.B. durch Reformulierungen, durch Browsing von Areas of Interest, durch Auswahl von Synonymen bei der Reformulieren der Anfrage, Link-Verfolgungen, … Anzeige Verwandter Suchbegriffe, Rechtsschreibkorrektur, Kombination von Anfragen, Speicherung von Sitzungen oder andere proaktiven Taktiken
Wissensrepäsentation für Textinhalte
Die Repräsentationsform der Dokumente und Anfragen ist ein grosses Problem in IR-Systeme. Das liegt daran, dass IR-Systeme durch ihre Vagtheit der Anfragen und Unzureichendes Wissen über die Dokumente charaktierisiert werden. Mit einer klaren Repräsentationsform für Textinhalte kann man Precision und Recall verbessern.
Die Ansätze hierzu sind entweder Ansätze der Freitextsuche oder der semantischer Ansatz.
Bei dem semantischen Ansatz wird eine zweite Repräsentationsform erstellt, die unabhängig von einer Formulierung des Textes ist. Dafür benötigt man eine Dokumentationssprache. Zuordnung von Deskriptionen zu Texten →
Dokumentationssprachen.
Beispielle:
1. Klassifikationen- Strukturierung nach einem vorgegeben formalen Schema
-Facettenklassifikation (bottom up: beginnt mit Beschreibungen z.B. Fellart, Lebensraum, …) Findet man bei Online Shops, ISM Yahoo
-monohierarchische Klassifikation (top-down: beginnt mit Oberbegriffe: Bsp:
Tiere-> ( Saugetiere, Fische, Vogel)
Saugetiere -> (Landsäuger, Meeresäuger)
Bsp: Computing Classification System (CCS)
2. Thesauri - Kontrolle der Terminologien (USE, UsedFor, RelatedTerm, NarrowTerm, BroaderTerm… Bsp Inspec Thesaurus
Bsp Softwareentwicklung
BS -Softwaretechnik
VB Softwaretechnologie
VB Software Engineering
UB (narrower term) Agile-Softwareentwicklung
3. Ontologien - Konstrukte Klasse, Vererbung, Slots. Bsp: YAGO- Retrieval von Wikipedia Artikeln
4. Tagging- Benutzer definiert und gewartet. Tags manchmal chaotisch Bsp Flickr, LibraryThing
Bei der Freitextsuche (die Suche mit Formular wie bei Google und Daffodil) wird keine zusätzliche Repräsentation erstellt, sondern es werden nur bestimmte Funktionen zur Verbesserung der Suche im Text der Dokumente angeboten. Es gibt zwei Unteilungen von Ansätze für die Freitextsuche: computerlinguistische Ansätze und informatische Ansätze.
Der informatischer Ansatz behandelt den Text als Zeichenkette. z.B. Mittel-Maskierung von Buchstaben ($), Trunkierung am Ende des Wortes (#) und Kontextoperatoren (genauer Wortabstand ($), maximaler Wortabstand (#), Wortreihenfolge (,), gleicher Satz (.)), der Benutzer muss die Funktionen aber kennen. Erreicht wird dadurch, dass verschiedene passende Formulierungen eines Wortes/Phrasen erkannt werden.
Bei dem Computerlinguistischer Ansatz wird mit Hilfe von morphologischen und teilweise auch syntaktischen Verfahren eine **Normalisierung von Wortformen angestrebt, so dass sich die Suche auf W¨orter bezieht. Lexikalische Verfahren benutzen ein Wörterbuch (Dekomposition von Wörter: Haustür - Haus’ tür, Flexionsform: Hauses - Haus) und graphematische Verfahren basieren auf die linguistische (graphematische) Analyse Text in einer bestimmten Sprache (Bsp applies -> apply). Graphem. Verfahrne nur gut bei wenig-flektierten Sprachen wie Englisch.
Syntaktische Verfahren werden benutzt, um Nominalphrasen zu bestimmen. Ziel Wortklassenbestimmung und Parsing. Funktionen: Head-Modifier-Strukturen erkennen, partielles Parsing (nominalphrasen erkennen NN+IN JJ NN+ = ‘retrieval of new documents’), Wortklassenbestimmung mit Vollformenwörterbuch…
Evaluierung im IR
Eine Evaluierung soll helfen, die Qualität eines IR-Systems beurzuteilen.
Die wissenschaftlichen Maßstäben für eine Evaluierung für ein IR-System sind die Reliabilität (Wiederholbarkeit) und Validität (ob Evaluierung repräsentativ ist, z.B. ob Benutzer in der Studie der Benutzer repräsentativ sind.)
Es gibt weiterhin zwei wesentliche Arten von Evaluierungen: Systemorientierte Evaluierungen und Benutzerorientierte Evaluierung.
- Systemorientierte Evaluierung fokussieren auf System-Effizien z.B. Zeit und Speciherplatz Nutzung des Systems.
- Benutzerorientierte Evaluierung stellt Benutzer im Zentrum und misst BenutzerEffizienz (schnelligkeit Aufgabe zu lösen), Effektivität (wie gut/genau Ziel erreicht wird), und Zufriedenheit.
Die Effektivitätsevaluierung (gerade erwähnt) kann auch in zwei Sorten unterteilt werden:.
Bei der Systemorientierte Evaluierung der Effektivität sind Relevanz-Beurteilung schon vorhanden und das System wird evaluiert.
(Bestimmung von REL (Recall Abschätzen)
-> Pooling, Frageerweiterung, ..
-> Assessoren, evtl. Mehrfachbewertung
)
Bei der Benutzerorientierte Evaluierungen der Effektivität werdenInteraktion zwischen Benutzer und System evaluiert.
(Wichtig hier ist: 1. mehrere TN bearbeiten dieselbe Aufgabe
2. Aufgabenreihenfolge permutieren (“randomisieren”)
3. “Große” Stichproben, Replikation von Versuchen.)
Maße für Ergebnismengen:
Recall: wie Anteil der Relevanten Dokumente habe ich für meine Anfrage gefunden (schwer zu berechnen)
Precision: Wie viele von meinen gefundenen Dokumente waren Relevant?
Fallout: Was ist der Anteil von nicht-relevanten die ich falscherweise gefunden habe an der Gesamtzahl der nicht-relevanten Dokumente.
Da Recall schwer abzuschätzen ist, gibt es folgende Methoden für die Abschätzung:
Pooling: Verschiedene Systeme mit gleicher Kollektion, gleicher Anfrage -> Relevanten aus allen Systemen sollten alle Relevanten annähern.
Source-Document-Method: Wähle beliebiges Dokument und formuliere eine Anfrage die das Dokument zurückgeben sollte. Wurde Dokument zurückgegeben? Wiederhole mit mehreren Dokumente und das ist eine Schätzung für Recall.
Frageerweiterung: erweitere eine beliebige Anfrage um mehr ähnliche Dokumente zu bekommen. Recall-Schätzung zu hoch.
usw….
Recall und Precision werden benutzt um die Ergebnissmengen und Systeme im Bezug auf eine Anfrage zu evaluieren. Aber was ist wichtiger, preicsion oder Recall? Beide Werte werden in als (r,p)-Paar in die F-Maß-Funktion eingebenen um einen F-Maß zu berechnen. Mit diesem Wert hat meine eine numerische Bewertung des Systems. Mit dem Parameter beta gibt man an, ob Precision oder REcall wichtiger ist. Der F-Maß kann graphisch mit Recall-Precision-Kurve dargestellt werden. Werte oberhalb der Kurve indiziert ein ‘gutes” System.
Abbruchverhalten von Nutzern:
Wenn der Retrievalwert für viele Dokumente gleich ist, erhält man mehrere Dokumente in einem ‘Rang’. Das ist wichtig, der Precision nach jedem Relevanten Dokumenten /nach dem Rang mit diesem Element berechnet wird. Es wird hier neu berechnet wird, weil Benutzer nach jedem relevanten Dokumenten die Suche abbrechen könnte.
Das Cumulated Gain Modell versucht dieses Verhalten zu berücksichtigen. Der Cumulated Gain ist weniger nach jedem gefundenen angesehen relevanten Dokument. Der Gain für ein relevantes Dokument ist der cumulativer Gain + der Gain bei Dokument d /log b(Rang k). b ist frei wählbar. Der cum gain vector entspricht diese Vektor von Gain-Zahlen.
Diversity Ranking:
Bei Diversity-Ranking berücksichtig man, dass ein Retrievalsystem am besten alle Aspekte der Anfrage mit den ersten dokumente (in der Ergebnisslist). z.B. wenn man ein Popstar sucht, will man einen Twitterartikel, wikipedia artikel, klatsch Artikel, Ticket-Verkauf, … etc.
Für diversity Ranking Evaluierung berechnet man Subtopic Recall, Subtopic Precision. Man berechnet hier wie viele Subtopics bis zum Rang k abgedeckt sind/alle Subtopics z.B. für Subtopic Recall.
Wenn man nur eine Anfrage evaluiert, heisst es Batch-Retrieval. Wenn man viele Anfragen die von dem gleichen Informationsbedürfnis stammen evaluiert heisst es interaktives Retrieval.
IR-Modelle
Das IR-Modell entspricht die logische Ebene im konzeptionellem Modell des IR-Syteme.
Es gibt zwei Arten von IR-Modelle: Nicht-probabilistische Modelle und Probabilistische Modelle.
Nicht-Probabilistische Modelle:
Boolesches Model - Diese Anfrage ist ein boolischer Ausdruck bestehend aus Terme und booleschen Operatoren. Es gibt keine Term-Gewichtung, keine Rangordnung und weniger gut Recall, aber sehr mächtig, wenn Benutzer weiss, wie er die Anfrage formulieren soll. Gefundene Dokumente sind exakt-Matches. (Jeder nicht-negierte Term in query kommt in Dokument vor)
Fuzzy Retrieval- Ist Verbessung im VErgleich zu Booleschem Retrieval weil man die Terme Gewichten kann und somit bekommt man einen Retrievalwert zwischen 0 und 1 zuordnet. Man bekommt eine Rangordnung von Dokumente die besser gepasst haben. Bsp: Bsp query q = t1 UND T2,
Dokumente
d1 = (0.6, 0.6), (Gewichtung von t1 und t2 respecktiv)
d2 = (1.0, 0.59)
=> d1 bekommt einen besseren Retrievalwert. Das ist Nachteilhaft weil d1 wahrscheinlich relevanter ist. (Verundung heisst, schlechtester Termwert ist RetrievalwertK)
Vektor-Raum Modell- Verbesserung zum Fuzzy-Retrieval-Modell weil der Retrievalwert -einen **Ähnlichkeitsmaß zwischen der Query und Dokument ist. Die Terme werden auch gewichtet (tdf-Formel) und Retrievalwert ist z.B. Skalarprodukt von query und Dokument (das heisst, dass die gewichtete Werte* 1 oder 0 aufsummiert werden). Das ist eine Verbesserung zum Beispiel oben:
RSV d1 = 1* 0.6 +1* 0.6= 1.2 RSW d2 = 11.0 + 10.59 = 1.59
Gewichtung **tdf-Formel: Inverse Dokument-höher, wenn Term seltener in Kollektion vorkommt und höher, wenn Term öfter in kürzeren Dokument vorkommt.
**Ein Vorteil bei dem VRM ist dass man (mit der gleichen Anfrage) iteratives Relevance Feedback in der Berechnung Fragevektor benutzen kann. Für weitere Dokumente wird der Fragevektor mit dem optimalen Fragevektor berechnet, um Precision und Recall zu erhöhen.
Relevance Feedback = Optimaler Fragevektor = Mittelpunkt der rel Dok - Mittelpunkt der nicht-relevanten Dokumenten.
=> eine trennung der relevanten und nicht-relevanten Dokumente fließt ein in die Modifikation der ursprünglichen Fragevektors.
Rocchios Vorschlag, der Optimaler Fragevektor sollte relevante Dokumente positiv und mehr gewichten als nicht-relevanten.
Nachteil aller Nicht-Prob. Modelle: Kein Bezug auf Retrievalqualität = “nicht zu begründen, warum Dok. relevant seins soll.”
Probabilisitsche Modelle:
Relevanz-orientierte Modelle versuchen, die Wahrscheinlichkeit zu schätzen, dass ein gegebenes Dokument bezüglich der aktuellen Anfrage q als relevant beurteilt wird. Vorteil über nicht-prob. Modelle: Durch den Probability Ranking Principle wird begründet, was die Relevanzwahrscheinlichkeit ein optimales Retrieval entspricht.
Binary-Independence Retrieval Modell (BIR)
-ein Dokument wird als Vektor von Terme repäsentiert.(berücksichtigt die Häufigkeit der Terme NICHT)
-Man berechnet die Wahrscheinlichkeit, dass ein Dokument relevant ist. D. h. man berechnet die Odds, dass ein beliebiges Dokument relevant ist und die Wahrscheinlichkeit pro Term, dass Term vor kommt (pi) oder nicht vorkommt (si)
-man betrachtet die Terme im Dokument und multipliziert Odds Dok rel * produkt alle pi-Werte * product aller si-Werte
-Parameterschätzung: pi: bezeichnet die Wahrscheinlichkeit, dass ti
in einem arbitr¨aren relevanten Dokument vorkommt. si: bezeichnet die Wahrscheinlichkeit, dass ti
in einem arbitr¨aren nicht- relevanten Dokument vorkommt. si schätz man als ni/N, pi typischerweise als 0.5 oder beide durch relative Häufigkeiten.
Nachteil: Häufigkit der Term im Dokumentvektor wird nicht gewichtet, Dokumente mit gleichen Vektor gleiche Wahrscheinlichkeit.
BM25 ist eine Verbesserung zu BIR weil die Häufigkeit der Terme im Dokument berücksichtigt wird.
- Die Gewichtung von einem Term in einem Dokument liegt zwischen 0 und 1.
- Es benutzt eine ähnliche Gewichtungsformel als Vektorraummodell (Nicht-Prob Modelle) mit ntf*idf-Formel.
statische Sprachmodelle:
Die Idee ist, dass Frage und Dokument von demselben Sprachmodell generiert wurden (gleicher Sprache). Man berechnet die Wahrscheinlichkeit, dass ein gegebenes Text d = t2t2t3..tm von dieser Sprache/diesem Sprachmodell generiert wurde.
Neuere Probabilistische Modelle:
Learning to Rank-“Beim Learning to Rank (LTR) wird mit Hilfe von maschinellen Lernverfahren die Relevanz bzw. der retrieval Wert (RSV) oder Ranking vorhergesagt. “
- Punktweise LTR will Klassifikation (Relevanz/Nicht-Relevanz) oder Retrievalwert vorhersagen.
- Paarweise LTR- vergleicht (d,d) Paare (alle möglichen) und berechnet den besten Ranking, so dass Umtauschungen der Paare minimiert werden.
- Listenweise LTR - Trainingsdaten besteht aus Liste, die ideale Rangordnungen vorgeben. Lernalgorithmus optimiert Evaluierungsmaß für die Listen.
- Training/Lernen auf Anteil der Daten, wo Relevance Feedback existiert.
Interactive Probability Ranking Principle (IPRP)
-Sagt Informationsbedürfnis DOCH nicht statisch.. ändert sich während der Suche.
-IPRP versucht vollständige Interaktion zwischen Mensch und Computer zu berücksichtigen.
-macht Annahme, dass Relevanz von Dokumenten nicht unabhängig (zweites Duplikat hat weniger Relevanz)
Modell: Benutzer beurteilz angezeigte Reihenfolge von “Choices”, Feedback (positive Entscheidungen) führt zu einer potentiell neuen Auswahlliste ->neue Situation. Jedes Choice ist assoziert mit Kosten und Wahrscheinlichkeits Parameter * Nutzen = Expected Value of Choice
Diversity Ranking
Bsp: Anfrage: Popstar xyz
Erbenisse:
Twitter Seite, Wikipedia, neuerster Album, Ticket-Verkauf zum Konzert, Neuester Klatsch zu xyz
-Man versucht, m¨oglichst
viele verschiedene (DIVERSE) Aspekte einer Anfrage durch die obersten Antworten abzudecken
-Man berechnet ungefähr die Wahrscheinlichkeit der Ähnlichkeit zwischen das aktuelle Dokument und Query q + Wahrscheinlichkeit dass es KEINE Ähnlichkeit gibt zw. Dokument d und bisher gesehene Dokumente.
Letzeres multipliziert man mal eine Gewichtung für die Neuigkeit des Dokumentes.
Information Seeking and Searching
Information Seeking and Searching entspricht die Ebene Functional Level (Funktionen zur Informationsbeschaffung) in der Ebenen-Architektur von IR-Systemen.
Im Vergleich zu dem klassischen Information Retrieval wird das Informationsbedürfnis bei Interaktives Information Retrieval als dynamisch gesehen. Das heisst, dass der Benutzer eine Sequenz von Anfragen ausführen kann bis er sein Informationsbedürfnis befriedigt hat.
-Interaktion des Benutzer mit IR-System steht im Vordergrund (nicht statisch)
Zwei Betrachtungsweisen zum interaktiven IR
1. information Seeking Behavior - Modelle zum Verhalten, Motivation und Vorgehen des Benutzers zur Befriedigung einer Aufgabe
Bsp: Meho/Tibbo Modell: Information Seeking Behavior beinhaltet viele Unterschiedliche Phasen:Accessing, Searching und Processing.
“Searching” beinhaltet, “Starting, Chaining, Browsing, Monitoring, Differentiating, Extracting, Networking” (Phasen von Ellis), Processing behaltet VEifying, Infomration Managing, Synthesis, analyzing, writing…
- Information Searching - Sicht auf Interaktion des Benutzers, stellt Modelle für den Suchprozess dar und hat Bedeutungen für die Unterstützung, die eine Suchmaschine anbieten sollte.
- Klassisches Model: Beginn, Wähle System, Anfrage, Abfrage abschicken, erhalte Ergebnisse, Durchschauen, Stopp oder Remuliere Anfrage.
- Belkins Episodic Interaction Model- basiert auf ASK-hypothesis: Anomalous State of Knowledge = Wissenzustand mit Lücken. Benutzer will diesen Lücken beseitigen. Bsp: Buch Suchen und am Ende neue Suchbegriffe finden und andere Bücher ausleihen.
- Berrypicking Model: Die Suche besteht aus einer Folge von Seltionen und dem Aufsammeln von INformationsbrocken
- Ingwersen’s Cognitive Modell: beinflussender Faktoren mit denen der Benutzer integriert ist. (soziales Umfeld, Benutzerschnittstelle, IR-System) -> Strategie zur Unterstützung des Modells ist Prinzip der Polyrepräsentation (Dokument soll unterschiedlich dargestellt werden.) Bsp Amazon Buch - miniaturbild, Titel, Inhaltsangaben, reviews, …
Strategische Unterstützung:
Verfahren die dem Benutzer helfen sollen, Suche voran zu treiben:
Move: einfach: Suchbegriff eingeben, Treffer anschauen, Link-verfolgen.
Taktik: Bsp Auswahl von Synonymen,
Strategem: Bsp Browsing Area of Interest
Strategie (all of the above)
Proaktivität in IR-Systeme wichtig: Rechtsschreibkorrektur, Anzeige der verwandter Suchbegriffe Suggestions anzeigen Bsp: Daffodil Studie zeigt, dass ohne praktiven Taktiken sind Benutzer verunsichert.
Gestaltung von Benutzerschnittstellen für IR-Systeme
Design Prinizipien sind:
Interface solte fast verschwinden um dass Benutzer sie nicht merken und unverhinert weiterarbeiten
-gebe informatives Feedback -Frageformulierung zusammen mit Ergebnissmenge
-erlaube einfaches zurücknehmen von Aktionen
- reduziere Belastung des Kurzzeitgedächnisses.
Die Klassischen Eingabe-Schnittstellen sind: 1. Kommandosprachen – schwierig zu erlernen – fehleranf¨allig – un¨ubersichtlich \+ m¨achtiger Formalismus \+ effiziente Interaktion m¨oglich Bsp: => S (PAPER# OR PULP# OR FIBER#) 236096 PAPER# 106940 PULP# 73040 FIBER# (????) 2. Formulare Bsp Google (ein Feld) , Daffodil (Formular mit Felder ausfüllen
- Menüs - checkboxes
Beispiel: Produktauswahl bei Amazon, Mail-Suche bei Thunderbird
Die Benutzerschnittstele kann auch vieles visualisieren für den Benutzer:
VISUALISIERUNG VON KOLLEKTIONEN:
Browsen von Hierarchien: Indented Tree Layout, Treemap
GRAPHISCHE ANS¨ATZE ZUR FRAGEFORMULIERUNG
Magic-Lens-Interface zur Frageformulierung
Boolesche Anfragen: Blockdiagramme (black and white boxes für die Anfrage ???), Flussdiagramm mit Filtern,
ERGEBNISLISTEN:
Liste mit Titeln und info. (uni due primo),
Liste mit Dokumentzusammenfassung (google),
STRUKTURIERUNG VON ERGEBNISMENGEN:
Ergebnismengen im Termraum (visueller Raum von Terme),
Zeige zeitlicher Bezug Ergebnisse: Bsp Google Timeline
Zeige geographisher Bezug: Google Maps
Ergebnisse mit TileBars - Gewicht und Ort von Frageterms
Highlighting im Ergebnis: Google highlighting search terms
DER MEDIOVIS-ANSATZ: ???
-explore Kollektion with semantic zooming approach, uses visual spacial orientation and ability to remember visual landmarks. or table based visualization in grid form. (Hypergrid)
Interessant sind auch Agentenbasiertes : IR-System macht Vorschläge direkt durch einen Agenten in der Benutzeroberfläche
- Bsp Karl Klammar
- beobachtet Benutzer
- macht Vorschläge
- unterbricht die Aktionen des Nutzers = kein soziales Verhalten!!!
- ist immer animiert
- nervt den Benutzer
Mixed-Initiative-Interfaces (sozialer Agenten)
-Timing wichtig
-Soziale Verhaltensweisen,
Korrekturmöglichkeiten, Verbesserung
-Dialoggestaltung mit Rückfragen
-Kosten und Nutzen Abwägung vor einer Empfehlung/Unterbrechung.
Beispiel: Daffodil
-macht Korrekturvorschlag mit Verzögerung,-
-Markiert Wort in Rot falls potenzielle fehlerfhaft (syntax)
