Effiziente Informationssuche im Web der Zukunft

Im Zeitalter der Informationsexplosion sind der intelligente Umgang mit Information und vor allem das Suchen relevanter Daten entscheidende Aspekte für den Fortschritt in Industrie und Wirtschaft (Beispiel Marktanalysen), Alltag und Gesellschaft (Beispiel Gesundheitswesen) und in nahezu allen - immer mehr auf Datenanalysen angewiesenen - Wissenschaften (Beispiel Genexpressionsdaten). Die Gesamtheit der über das World Wide Web zugänglichen Informationen, einschließlich der darüber erreichbaren digitalen Bibliotheken, haben das Potenzial zu einer allumfassenden Enzyklopädie und Wissensbank, die vom Schüler bis zum Nobelpreisträger genutzt werden könnte.

Datenbank- und Suchmaschinentechnologien bieten vielfältige Unterstützung zur Informationsorganisation und -suche, doch leider allzu oft nur mit mittelmäßigen Resultaten. Ziel muss es sein, die maschinelle Informationssuche so zu verbesseren, dass die Güte der Antworten der der besten menschlichen Experten entspricht, gleichzeitig aber kaum noch manuelle Schritte anfallen und Ergebnisse schnell gefunden werden. Beispielsweise sollte ein Wissenschaftler in die Lage versetzt werden, eine Suche nach den für eine bestimmte Vermutung relevanten mathematischen Theoremen mit wenigen Minuten Arbeitsaufwand zu formulieren und ein befriedigendes Resultat über Nacht zu erhalten. Einige konkrete Suchbeispiele, bei denen heutige Suchmaschinen mehr oder weniger versagen, sind:

Für S1 qualifiziert sich keine einzelne Web-Seite; vielmehr muss man mehrere Web-Seiten im Zusammenhang sehen: die Homepage eines Saarbrücker Informatikprofessors, eine Seite über eine bestimmte Vorlesung und eine dritte Seite mit Projekten. S2 wäre einfach, wenn man genau wüsste, in welchem Bioinformatik-Web-Portal oder welcher digitalen Bibliothek man wie zu suchen hat; die Situation ist jedoch viel komplexer, weil es unzählige solcher Portale mit uneinheitlichen Terminologien und Taxonomien und stark streuender Informationsqualität gibt. Für S3 wäre offensichtlich Macbeth ein guter Treffer, doch würde eine Stichwortsuche nach Frau, Edelmann und Mord nicht ohne weiteres fündig, weil im Text stattdessen von "Lady Macbeth", "Than von Cawdor" und "Bist du zu feige, derselbe Mann zu sein in Tat und Mut, der du in Wünschen bist?" die Rede ist. Bei S4 schließlich muss man verschiedene Informationsbruchstücke aus Email-Archiven, Konferenzankündigungen im Web und Homepages zusammensetzen, und man muss wissen, dass etwa Sophie Cluet aus Paris eine gute Kandidatin ist, weil Sophie fast immer ein weiblicher Vorname ist und mit Paris mit sehr hoher Wahrscheinlichkeit die französische Hauptstadt und nicht das aus einem Film bekannte 500-Seelen-Dorf Paris, Texas, gemeint ist.

Für den Menschen ist keine dieser Anfragen wirklich schwierig - wenn man die Treffer nur aus einer kleinen Datenmenge herausfischen muss oder beliebig viel Zeit hat. Die maschinelle Suche dagegen steht vor dem Problem, einerseits mit gigantischen Datenmengen - mehrere Milliarden Web-Seiten plus etliche Petabytes in Datenbanken hinter Web-Portalen - und hoher Varianz der Datenqualität umzugehen und andererseits die menschliche Intelligenz bei der Verknüpfung und Interpretation von Informationsbruchstücken geeignet zu simulieren. Wir arbeiten am "Web der Zukunft", indem wir Methoden verschiedener Teilgebiete der Informatik kombinieren, insbesondere effiziente Suchalgorithmen aus dem Datenbankbereich, Techniken zur Textähnlichkeitssuche aus dem Information Retrieval, Methoden des statistischen Lernens, etwa zur automatischen Klassifikation von Dokumenten, und Wissensrepräsentationsformen aus der Künstlichen Intelligenz.

Wie können wir in eine Suchmaschine das - für den Menschen banale, für den Rechner aber a priori unzugängliche - Wissen einbauen, dass Lady Macbeth eine Frau ist und damit der Antwort der Beispielsuche S3 näher kommen? Dazu muss man zunächst entsprechende Wissensbanken oder Thesauri aufbauen, die im Web-Kontext häufig als Ontologien bezeichnet werden. Eine Ontologie ist eine Sammlung von Konzepten, zwischen denen semantische Beziehungen expliziert modelliert sind. Die wichtigsten Beziehungstypen sind Synonymie, Hypernomie (Verallgemeinerung) und Hyponomie (Spezialisierung); beispielsweise ist "Lady" ein Hyponym von "Woman". Eines der bekanntesten Unterfangen, ein umfassendes Konzeptgeflecht dieser Art aufzubauen, ist WordNet, das von Kognitionswissenschaftlern in Princeton entwickelt wurde. Allerdings ist WordNet, obwohl maschinell verarbeitbar, nicht direkt für die Verwendung in einer Suchmaschine geeignet, da Beziehungen nur qualitativ modelliert sind, aber ihre "Stärke" nicht quantifiziert wird. Abbildung 1 zeigt einige Hyponyme von "Woman", von denen etliche für die Suche kaum relevant sind. Wir haben daher mit statistischen Methoden auf großen Korpora Beziehungen zwischen Konzepten quantifiziert und daraus einen gewichteten Konzeptgraphen aufgebaut, mit dessen Hilfe man zu jedem Konzept die am nächsten verwandten Konzepte bestimmen kann.

Die statistischen Ähnlichkeiten zwischen Konzepten können bei der Informationssuche ausgenutzt werden. Abbildung 2 zeigt die graphische Formulierung der Beispielsuche S1 mit einem unserer Softwarewerkzeuge. Jede der drei Boxen spezifiziert die Suchbedingungen, die eine Web-Seite jeweils erfüllen muss. Neben Schlüsselwörtern wie "Information Retrieval" können auch Konzept-Wert-Paare wie "Location = Saarbrücken" und relaxierbare Konzepte wie "~Professor" formuliert werden; letzteres besagt, dass eine Seite, in der ein ontologisch eng verwandter Begriff wie z.B. "Hochschuldozent" oder "Wissenschaftlicher Direktor" auftritt, ebenfalls als Treffer interpretiert werden soll. Die Pfeile zwischen den drei Boxen verlangen, dass es entsprechende explizite oder assoziative Links zwischen Trefferseiten geben muss. Die Ausführung dieser recht komplexen Anfrage ist mit der von uns entwickelten Software vollständig automatisiert. Wie in Suchmaschinen üblich werden Treffer in ihrer Relevanz quantitativ bewertet und in einer Rangliste nach diesen "Scores" absteigend sortiert geliefert.

Nun sind die meisten Daten im Web und in digitalen Bibliotheken einfache Texte oder bestenfalls HTML- oder XML-Dokumente. Um konzeptorientiert oder sogar strukturiert darauf arbeiten zu können, müssen die Daten selbst mit semantischen Annotationen angereichert und in einen Konzeptraum abgebildet werden. Für die Abbildung von Wörtern auf Konzepte und die Klassifikation ganzer Dokumente in eine Themenhierarchie verwenden wir eine Kombination aus statistischen Lernverfahren und einfachen Techniken der Computerlinguistik. Insbesondere Personen- und Firmennamen, Ortsbezeichnungen, Zeitangaben u.ä. können so aus Texten extrahiert werden. Außerdem ist es möglich, Querbeziehungen zwischen verschiedenen Web-Seiten als "assoziative Links" zu etablieren und in der Informationssuche zu berücksichtigen. Dies gibt uns eine Chance, die Antwort zur Beispielsuche S4 zu finden. Für breite Informationsbedürfnisse wie Beispiel S2 schließlich haben wir einen thematisch fokussierten Crawler entwickelt, der ausgehend von wenigen guten Startseiten automatische Klassifikationsverfahren verwendet, um bei seinem Web-Crawl inhaltlich passende Seiten zu finden.

So wünschenswert derartige Intelligenz in einer Suchmaschine ist, so sehr muss man aber auch darauf achten, dass Anfragen effizient ausgeführt werden können. Suchmaschinen arbeiten generell mit vorausberechneten Indexstrukturen, wie in Abbildung 3 illustriert. Hier sind "algorithm", "optimum", "performance" und "z-transform" Schlüsselwörter einer Anfrage oder allgemeiner sog. Terme, die im Index über einen Suchbaum schnell gefunden werden. Zu jedem Term gibt es eine Indexliste mit den Seiten, die den Term enthalten, und zwar in absteigender Reihenfolge eines Relevanz-Scores, der - basierend auf statistischen Maßen - die Signifikanz des Terms in der jeweiligen Seite widerspiegelt. In Abbildung 3 bezeichnen die Großbuchstaben in den Indexlisten Web-Seiten, und die Zahlen dahinter sind die Scores. Der Gesamt-Score einer Seite und damit ihr Rang für eine Anfrage ergibt sich durch (evtl. gewichtetes) Aufsummieren der Scores aus den einzelnen Indexlisten der in der Anfrage vorkommenden Terme. Im Beispiel hat die Seite B den Gesamt-Score 1.85 (= 0.9 + 0.7 + 0.125 + 0.125) und wäre damit der beste Treffer für eine Suche nach den vier angegebenen Wörtern.

Allgemeiner betrachten wir im folgenden die Frage, wie man zu einer gegebenen Anfrage mit m Termen die Top-k-Treffer mit den höchsten Gesamt-Scores effizient bestimmen kann. Der Wert von k ist typischerweise 10 bis 100. Der Wert von m wäre 1 bis 10 bei konventioneller Web-Suche; mit den skizzierten Techniken ontologiegestützter konzeptbasierter Suche werden jedoch intern komplexere Anfragen generiert, die 20 bis 100 elementare Suchbedingungen umfassen können. Da eine einzelne Indexliste ohne weiteres einige Hunderttausend Web-Seiten enthalten kann und der Gesamtindex mit einer Größe von mehreren Terabytes nicht im Hauptspeicher gehalten werden kann, ist die Berechnung der Top-k-Treffer bereits bei heutigen Suchmaschinen ein kritischer Aspekt und sie wird bei der verfolgten intelligenteren Suche noch wichtiger.

Ein Standardalgorithmus für das Problem besteht darin, einfach alle Indexlisten zu Termen der Anfrage komplett von der Magnetplatte in den Hauptspeicher zu lesen, dort zunächst alle Listen nach Seitennummern zu sortieren, dann mit linearem Rechenaufwand die Gesamt-Scores pro Dokument zu berechnen, dieses Ergebnis nach Gesamt-Scores absteigend zu sortieren und davon schließlich die Top-k-Treffer auszugeben. Dieses Verfahren ist auf kleinen Datenmengen akzeptabel, skaliert aber nicht mit der Größe des Index. In der Literatur finden sich Heuristiken zur Beschleunigung, die vermutlich auch von großen Web-Suchmaschinen verwendet werden; sie sind jedoch unbefriedigend, weil sie keinerlei Aussagen über den potenziellen Fehler des zurückgelieferten Top-k-Ergebnisses erlauben.

Erst in jüngster Zeit wurde unter dem Namen Schwellwertverfahren (englisch: Threshold Algorithms) eine auf Branch-and-Bound-Optimierungsprinzipien beruhende Familie von Algorithmen vorgeschlagen, die ein genaues Top-k-Ergebnis berechnen und dabei nur einen Bruchteil der Indexlisten anschauen müssen. Dazu wird jede Indexliste nach ihren jeweiligen Scores absteigend sortiert gespeichert, so wie in Abbildung 1. Die Algorithmen arbeiten alle für die Anfragen relevanten Indexlisten mit sequentiell verschränkt ab, also erst Rang 1 in allen Listen, dann Rang 2 in allen Listen, usw. Die Verbesserung gegenüber dem Lesen der kompletten Listen beruht auf dynamisch berechneten oberen und unteren Schranken für den Gesamt-Score möglicher Top-k-Resultate und einem geeignet gewählten Abbruchkriterium.

Wie sehen diese Schranken genau aus? Für jede in einer Liste auftauchende Seite legt man einen Eintrag in einer Prioritätswarteschlange an (z.B. einem sog. Fibonacci-Heap). Dort speichert man die Summe aller für die Seite bereits bekannter Scores aus den Indexlisten; dies ist eine untere Schranke für den Gesamt-Score der Seite. Zusätzlich merkt man sich für jede der traversierten Indexlisten den zuletzt gesehenen Score, der wegen der sortierten Speicherung die möglichen Scores dieser Liste für alle Seiten nach oben beschränkt. Für jede Seite ist damit die Summe ihres bisher bekannten Partial-Scores und der bestmöglichen Scores aller Listen, in denen die Seite noch nicht gesehen wurde, eine obere Schranke für den Gesamt-Score der Seite. Nehmen wir an, wir seien im Beispiel von Abbildung 1 in der Abarbeitung der Listen bis zur durchgezogenen blauen Linie gekommen. Wir wissen an dieser Stelle, dass der Gesamt-Score von Seite A mindestens 1.5 (= 0.9 + 0.6) ist und höchstens 1.75 (= 1.5 + 0.125 + 0.125). Analog können wir für die Seiten B und C feststellen, dass ihre Gesamt-Scores zwischen 1.725 und 1.85 bzw. zwischen 1.6 und 1.85 liegen müssen, und für Seite E etwa sind die entsprechenden Schranken 0.95 und 1.475.

Man kann nun leicht zu jedem Zeitpunkt die bzgl. ihrer unteren Schranken bisher besten Top-k-Treffer bestimmen. An der durchgezogenen blauen Linie wären das für k=3 die Seiten B, C und A; das sind in der Tat die drei besten Treffer insgesamt. Doch dürfen wir an dieser Stelle das Abarbeiten der Indexlisten bereits abbrechen, oder könnte sich weiter unten in den Listen noch ein Score finden, der eine andere Seite, beispielsweise G, in die Top-k-Ränge bringt? Der Schlüssel zum korrekten Abbruchkriterium liegt darin, die schlechteste untere Schranke der aktuellen Top-k-Treffer mit der besten oberen Schranke aller anderen Kandidaten zu vergleichen. Wenn keiner der noch im Rennen befindlichen Kandidaten eine Chance hat, einen Gesamt-Score zu erreichen, der über dem garantiert erreichten Score des aktuellen Rang-k-Treffers liegt, darf der Algorithmus stoppen. Im Beispiel haben D, E, F, G und H an der durchgezogenen blauen Linie die oberen Schranken 1.465, 1.475, 1.435, 1.45 und 1.475, andere Seiten erreichen auch keine höheren Werte, und der bestmögliche Gesamt-Score einer bislang in keiner Liste angetroffenen Seite wäre auch nur 1.25. Die schlechteste untere Schranke der aktuellen Top-k-Treffer ist 1.5 und die beste obere Schranke der Alternativkandidaten 1.475; das Abbruchkriterium ist erfüllt. Einen Schritt früher, also nachdem die ersten 6 Ränge aller Listen bekannt sind, dürfte der Algorithmus noch nicht stoppen.

Das Schwellwertverfahren ist beweisbar optimal unter allen Verfahren, die die Indexlisten sequentiell abarbeiten, und zwar für alle nur denkbaren Werte in den Indexlisten. In Experimenten auf realen Web-Daten, z.B. dem TREC-Benchmark, und anderen Korpora zeigt sich, dass man für den Standardfall k=10 häufig nur zehn Prozent der Indexeinträge abarbeiten muss. Das Verfahren kann jedoch nochmals um eine Zehnerpotenz beschleunigt werden, indem man die statistische Verteilung der Scores in den einzelnen Indexlisten berücksichtigt und sich damit zufrieden gibt, dass das berechnete Top-k-Resultat mit hoher Wahrscheinlichkeit die wirklichen Top-k-Treffer enthält. Wir haben ein solches Verfahren entwickelt und damit die Laufzeiten des einfachen Schwellwertalgorithmus in Benchmark-Tests um eine Größenordnung und teilweise bis zu einem Faktor 30 verbessert. Dabei können wir gleichzeitig eine mathematisch fundierte, probabilistische Garantie für die Güte des Top-k-Resultats, relativ zu dem des exakten Algorithmus, geben.

Das probabilistische Verfahren profitiert von der Beobachtung, dass die Verteilung der Scores in einer Indexliste oft extrem ungleichmäßig ist: es gibt wenige hohe Werte und sehr viele niedrige Werte. In Abbildung 1 zeigen die ersten beiden Listen eine Gleichverteilung (zumindest in dem gezeigten Teil), während in der dritten und vierten Liste die Scores sehr schnell fallen, wie etwa in einer sog. Zipf-Verteilung. Solche Verteilungen können vorab analysiert und in kompakter Form durch Histogramme oder parametrisierte Funktionen (z.B. Poisson-Mix-Verteilungen) gut approximiert werden. Im Schwellwertverfahren können wir nun die - unnötig konservative - obere Schranke des Gesamt-Scores einer Seite durch eine probabilistische Schranke ersetzen, nämlich durch ein Quantil der Score-Verteilung. Das heißt, wir berechnen einen Wert für den bislang unbekannten Teil des Gesamt-Scores, der mit einer nahe bei Eins liegenden Wahrscheinlichkeit p, zum Beispiel 90 Prozent, nicht überschritten wird.

Dieser Effekt ist bei typischen Score-Verteilungen realer Daten stark ausgeprägt und hilft uns, den Algorithmus sehr frühzeitig zu beenden, und zwar mit garantiert kleinem Risiko, dabei einen Fehler zu machen. Im Beispiel könnte man schon an der gestrichelten blauen Linie, also nach dem 3. Schritt, stoppen. Zu diesem Zeitpunkt kennt man die untere Schranke 1.5 für die Gesamt-Scores der bisherigen Top-3, und die Wahrscheinlichkeit, dass eine der anderen Seiten diesen Wert überschreitet, ist hinreichend klein. Betrachten wir etwa Seite Z als Alternativkandidat, von der wir wissen, dass ihr Gesamt-Score mindestens 0.5 beträgt. Über die 4. Liste wissen wir, dass die Scores dort extrem schnell fallen. In der 1. und 2. Liste ist die Situation anders, denn deren Score-Verteilungen sehen eher nach einer Gleichverteilung aus. Die Wahrscheinlichkeit, in der Summe der Scores in diesen beiden Listen einen Wert über 1.0 zu erreichen, ist aber selbst bei Gleichverteilungen nicht sonderlich hoch. Analog müssten wir die Wahrscheinlichkeit schätzen, dass eine bislang in keiner Liste gesehene Seite in der Summe der Scores aus allen vier Listen einen Wert über 1.5 erreicht. Wir sehen, dass wir Summen von (unterschiedlich verteilten) Zufallsvariablen betrachten müssen und - da sich zwar Erwartungswerte addieren, nicht aber ganze Verteilungen und deren Quantile - zur Analyse die Faltung der Score-Verteilungen berechnen müssen. Dazu gibt es eine Reihe möglicher Wege: der eleganteste ist wohl die analytische Faltung der Laplace-Transformierten der zugrundeliegenden Verteilungen und die Abschätzung der resultierenden Quantile mit Chernoff-Hoeffding-Schranken, der praxistauglichste ist die numerische Faltung von Histogrammen, die die Verteilungen in den jeweiligen Listen approximieren. Eine Annahme dabei ist, dass die Scores verschiedener Listen stochastisch voneinander unabhängig sind. In Experimenten zeigt sich, dass diese Annahme unkritisch ist; es gibt aber auch Wege, Korrelationen zwischen Listen zu berücksichtigen.

Die Umsetzung dieses probabilistischen Schwellwertverfahrens in ein Softwarewerkzeug erfordert Geschick. Ein subtiler, aber leistungsentscheidender Punkt ist die Verwaltung der Prioritätswarteschlange. Da sich in jedem Schritt die bestmöglichen Scores der einzelnen Listen ändern, müsste man eigentlich ständig die oberen Schranken der Kandidaten aktualisieren und die Prioritätswarteschlange entsprechend umsortieren. Letzteres geht zwar sehr effizient, aber die schiere Anzahl etlicher Tausender solcher Operationen würde das Verfahren stark belasten. Unsere Software arbeitet daher mit beschränkten Prioritätswarteschlangen, in denen nur einige Hundert der aussichtsreichsten Kandidaten verwaltet werden, verzichtet auf ständiges Aktualisieren der Prioritätswerte und baut stattdessen die gesamte Datenstruktur periodisch neu auf. Bei jedem erneuten Aufbau eliminieren wir Kandidaten, deren Erfolgswahrscheinlichkeit zu gering ist. Auf diese Weise kann man eine extrem effiziente Suchmaschine bauen, die mehr als zehnmal schneller ist als das konservative Schwellwertverfahren und sogar mehrere Zehnerpotenzen schneller als die Standardverfahren aus Lehrbüchern.

Unser Arbeitsprogramm, Methoden und Softwarewerkzeuge für die intelligente und effiziente Informationssuche in digitalen Bibliotheken, wissenschaftlichen Datensammlungen, Intranets und im Web zu entwickeln, hat vielfältige Unterthemen. Ein Langzeitziel ist es, eine Suchmaschine völlig dezentralisiert und selbstorganisierend in einer sog. Peer-to-Peer-Architektur zu realisieren. Wir stellen uns vor, dass jeder Benutzer eine vollständige Suchmaschine mit einem kleinen Index von z.B. 100 Gigabytes auf seinem persönlichen Rechner hat. Der Index ist für das jeweilige Interessensprofil spezialisiert, indem etwa unsere fokussierte Crawling-Technologie verwendet wird. Anfragen des Benutzers werden zunächst lokal ausgewertet, wenn das Resultat aber das Informationsbedürfnis nicht voll befriedigt, werden andere "Peers" automatisch kontaktiert und um Mithilfe bei der Suche gebeten. Die Art und Weise, wie Dutzende von Peers für eine einzelne Anfrage zusammenarbeiten und wie sich Millionen von Peers langfristig untereinander verbinden, sollte völlig selbstorganisiert sein, also ohne menschliche Eingriffe (durch Systemadministratoren) auskommen. Eine solche Architektur ist nicht nur aus Informatiksicht interessant, sondern hat auch das Potenzial, die Suchresultatsgüte global für alle Benutzer zu verbessern, indem sie den impliziten intellektuellen Input (die Historie der Anfragen, Clicks, etc.) aller Benutzer berücksichtigt. Alleine die Kenntnis der Bookmarks von Millionen von Peers könnte mit geeigneten statistischen Analysen und Lernverfahren zu einem Quantensprung in der Suchresultatsgüte führen. Darüber hinaus würde dieser Ansatz die Gefahr des De-Facto-Monopols einer einzigen, zentralisierten Web-Suchmaschine bannen.