Vorlesung 8 - Websuche

Question 1

Herausforderungen bei der Websuche

Answer 1

• Skalierbarkeit für parallele Indexierung und Suche (Map Reduce)
• Vollständige Abdeckung des gesamten Webs sicherstellen
• Zugriffszeit vieler Anfragen müssen schnell und ggf. gleichzeitig beantwortet werden
• Robustes Ranking für Informationen geringerer Qualität und Spam-Erkennung
• Dynamik durch kontinuierlich wachsendes, sterbendes und/oder sich aktualisierendes Webs
• Möglichkeiten:
  -> Heuristiken, um Suchgenauigkeit zu verbessern, z. B. Link-Analyse, Multi-Feature-Ranking

Question 2

Komponenten einer Websuchmaschine

Answer 2

• Crawler
• Indexer
• Retriever

Question 3

Funktionsweise von Crawlern

Answer 3

• Funktionsweise (einfach):
  1. Crawler bekommt SeedPages in priorisierter Reihenfolge in einer Queue
  2. Crawler ruft Websiten ab und analysiert diese
  3. Crwaler sucht Hyperlinks und fügt diese zur Queue hinzu
  4. Crawler folgt Hyperlinks in der Queue und beginnt wieder beim ersten Schritt
• „Ein richtiger Crawler ist komplizierter:
  -> Robustheit (Serverfehler, trap, etc.)
  -> Crawler-Freundlichkeit (Server-Load-Balance, Robot Exclusion, etc.)
  -> Umgang mit unterschiedlichen Dateitypen (Bilder, PDF-Dateien usw.)
  -> URL extensions (cgi script, internal references, etc.)
  -> Erkennen redundanter Seiten (identische und Duplikate)
  -> Entdecken versteckter URLs (z. B. kürzen langer URLs )“

Question 4

Strategien von Crawlern

Answer 4

• Breadth-First: es wird zuerst in die Breite und dann in die Tiefe gesucht
• Paralleles Crawling: mehrere Spider suchen mit unterschiedlichen Seeds gleichzeitig
• Fokussiertes Crawling: beschränkt sich auf Teilmenge der Seiten
  -> z. B. über ein bestimmtes Thema (Query)
• Neue Seiten finden:
  -> Neue Seiten können nicht auf alten Seiten verlinkt sein
  -> Inkrementelles/Wiederholtes Crawling: Finden neuer Seiten
  –> „Benötigt um Ressourcen-Overhead zu minimieren“
  –> „Kann aus Erfahrungen lernen (Aktualisierung täglich vs. monatlich“
  –> „Häufig aktualisierte oder zugegriffene Seiten“

Question 5

Funktionsweise und Bedeutung des GFS

Answer 5

• „Standard Information Retrieval (IR)-Techniken bilden die Basis, sind aber nicht ausreichend im Hinblick auf Skalierbarkeit und Effizienz”
• Googles Beitrag:
  -> Google File System (GFS): verteiltes Dateisystem
  -> MapReduce: Software-Framework zur Parallelverarbeitung
  -> Hadoop: Open-Source-Implementierung von MapReduce
• Funktionsweise:
  -> Besteht aus einem Master-Server und mehreren Chunk-Servern
  -> Client stellt Anfrage an Master-Server, welcher ihm die Metadaten zu einer Datei zurückgibt,
  inklusive dem entsprechendem Chunk Server, wo sich die Datei befindet
  -> Datenübertragung der Datei findet direkt zwischen Client und Chunk-Server statt
  > Master-Server verwaltet Chunk-Server, sorgt für Load-Balancing und einer Redundanz
• Bedeutung:
  -> Kann zur Speicherung des Index einer Websuchmaschine genutzt werden, u. A. damit dieser redundant vorhanden ist

Question 6

Prinzip und Bedeutung des Map-Reduce-Frameworks

Answer 6

• Prinzip:
  -> Eingabewerte werden mittels Partitionierung der Daten in (Key, Value)-Paare zerlegt
  -> (Key, Value)-Paare werden aus verschiedenen Strängen gesammelt und sortiert
  -> Map()-Funktion bildet (Key, Values)-Paare auf andere (Key, Values)-Paare ab
  -> Values mit gleichen Key werden gruppiert
• Bedeutung:
  -> Parallelverarbeitung durch Minimierung von Aufwand für Programmierende

Question 7

Bedeutung der Linkanalyse von Webseiten

Answer 7

• Um Popularität/Nutzen einer Seite messen und somit das Scoring optimieren zu können
• Dies kann realisiert werden, indem verschiedene Features bzw. Ergebnisse verschiedener Scorer kombiniert werden

Question 8

PageRank-Algorithmus

Answer 8

• Intuition:
  -> „Links sind wie Zitierungen in der Literatur“
  -> „Erwartungsgemäß ist eine oft zitierte Seite im Allgemeinen nützlicher“
  -> PageRank ist prinzipiell „Zählen von Zitierungen“, geht aber über einfaches Zählen hinaus
  -> Indirekte Zitierungen (von häufig zitierten Paper zitiert zu werden ist viel Wert)
  -> Zitierungs-Glättung (wird angenommen, jede Seite hätte eine Pseudo-Zitierungsanzahl > 0)
  -> PageRank kann auch als Random-Surfing interpretiert werden (reflektiert die Seitenpopularität)
• Beschreibung:
  ->Menge verlinkter Dokumente (z. B. WWW) wird anhand ihrer Struktur bewertet/gewichtet
  -> Jede Seite besitzt ein Gewicht (PageRank), das umso größer ist, je mehr Seiten (mit möglichst hohem Eigengewicht) auf diese Seite verweisen
  -> Gewicht PRi einer Seite i berechnet sich aus PRj der auf verlinkenden Seiten j
  -> Verlinkt j auf insgesamt c j verschiedene Seiten, so wird das Gewicht PRj anteilig
  auf diese Seiten aufgeteilt
• Rekursive Formel als Definition des PageRank-Algorithmus:
  PRi = (1−d)/n+d∑(unten:j=i, oben:n) PRj/c j
  -> n:Gesamtanzahl der Seiten
  -> d :Dämpfungsfaktor ∈[0,1]
  -> „Dämpfungsfaktor zieht einen kleinen Anteil des Gewichts (1-d) einer jeden Seite ab und verteilt diesen gleichmäßig auf alle vom Algorithmus erfassten Seiten. Dies ist notwendig, damit das Gewicht nicht zu Seiten „abfließt“, die auf keine anderen Seiten verweisen.“

Question 9

HITS-Algorithmus beschreiben (Adjaszenz Matrix)

Answer 9

• HITS (Hypertext-Induced Topic Search) dient dem Finden von Authorities und Hubs
  -> Anchor-Texte: Beschreibung der Seite auf die sie verlinken
  -> Hub: eine Website verweis auf viele andere
  -> Authority: auf eine Website wird oft verwiesen
• Intuition:
  ->„Häufig zitierte Seiten sind gute Authorities“
  -> „Seiten, die viele andere Seiten zitieren, sind gute Hubs“
• Grundgedanke: (Grundannahmen HITS) Wichtig!
  -> Gute Authorities werden von guten Hubs zitiert
  -> Gute Hubs verweisen auf gute Authorities
  -> Verstärkung durch Iteration
• Anwendungen: Graph- und Netzwerkanalyse
• Scores:
  -> Hub Score eines Dokuments berechnet sich aus der Summe der Authority Scores der Dokumente, auf die durch diesen Hub verwiesen wird
  -> Authority Score eines Dokumentes berechnet sich aus der Summe der Hub Scores der Seiten, die auf diese Authority verweisen.
• Adjazenz-Matrix (Nachbarschaftsmatrix) (von sich auf sich selbst immer 0)
  -> Initialisierung:
  a(di)=h(di)=1
  ->h=A->a
  ⃗a=A^T ⃗h
  ⃗h=A A^Th
  ⃗a=A^T ->a
• Normalisierung: ∑(unten:i) a(di)^2=∑(unten:i) h (di)^2=1

Question 10

Kombination diverser Feature -Learning to Rank

Answer 10

Sei (Q,D) eine Query-Dokument-Paar
− Definiere verschiedene Arten von Features Xi(Q,D)
− z.B.: Anzahl überlappender Terme, BM25-Score 𝐩(Q,D), PageRank von D,p(Q,Di), wobei Di
Anchor-Text oder groß dargestellter Text ist, “beinhaltet die URL ein ‘~’?”….
− Hypothese: : p (R=1 | Q,D) = s(X1(Q,D),…,Xn(Q,D), λ)
− λ Menge von Parametern
− Lernen von λ mit Hilfe der Fitting-Funktion λ mit Trainingsdaten, d.h. 3-Tuples wie z.B.
− (D,Q, 1) → D ist relevant für Q
− (D,Q, 0) → D ist irrelevant Q

Question 11

Weitere fortgeschrittene
Lernalgorithmen

Answer 11

• Direkte Optimierung des Retrieval-Maßes (z.B. MAP, nDCG)
  − hohe Wahrscheinlichkeit der Relevanz heißt nicht unbedingt gutes Ranking
  − schwieriger als bisheriges Optimierungsproblem
  − Viele Lösungen werden in [Liu 09] diskutiert
• Allgemein einsetzbar für viele Ranking-Probleme jenseits der Suche
  − Empfehlungsmaschinen
  − Computergestützte Werbung
  − Zusammenfassungen von texten