Zum ersten Mal in der Geschichte haben Millionen von Menschen von zu Hause oder vom Büro aus augenblicklichen Zugriff auf die kreativen Ergüsse eines bedeutenden – und wachsenden – Teils der Menschheit. Jeden Tag kommen zu den Hunderten von Millionen Dateien (web pages, "Webseiten") im weltumspannenden Informationsnetz World Wide Web (WWW) etwa eine Million neu hinzu. Zusammengehalten wird diese enorme Menge von Informationen mehr oder weniger fest von einigen Milliarden automatischer Verbindungen, sogenannter Hyperlinks: Innerhalb einer Webseite sind, für den Benutzer unsichtbar, die Adressen anderer Webseiten gespeichert, die der Autor für erwähnenswert hält; ein Klick mit der Computermaus, und schon holt das verwaltende Programm (der Browser) die Seite, auf die verwiesen wird, herbei – von irgendeinem Computer in der Welt.

Wegen seines rasanten und chaotischen Wachstums ist das Web aber so gut wie organisations- und strukturlos: ein globales Spaghettiknäuel von bislang unvorstellbarem Ausmaß. Jeder darf eine Webseite schreiben, unabhängig von Herkunft, Bildung, Kultur, Interesse oder Motivation; Sprache, Dialekt und Stil sind nicht festgelegt. Eine Seite kann ein paar oder ein paar hunderttausend Zeichen lang sein; sie kann Wahrheit, Lüge, Weisheit, Propaganda oder schlichten Unsinn enthalten. Wie findet man in diesem riesigen Misthaufen die eine Perle, die man sucht?

Mit Suchmaschinen, war bisher die Antwort. Das sind spezielle, über das Web aufrufbare Programme, die alle erreichbaren Webseiten nach bestimmten Stichwörtern oder Wortkombinationen absuchen. Ein solche Textsuche liefert jedoch häufig Zehntausende von Seiten, von denen die meisten unbrauchbar sind. Wie soll man die Information finden, die man wirklich haben will, und wie kann man sich vergewissern, daß sie auch glaubwürdig ist?

Wir haben ein neues Suchprogramm entwickelt, das sich einen der wertvollsten Teile des Webs zunutze macht: die Hyperlinks. Durch deren Analyse kann unser Programm zwischen zwei Typen von Webseiten unterscheiden: Quellen (authorities) und Knotenpunkte (hubs). Quellen sind Seiten, die als beste Informationsressource für den jeweiligen Suchbegriff eingeschätzt wurden, während Knotenpunkte hauptsächlich aus Links zu diesen Seiten bestehen.



Suchmaschinen sollen die besten Seiten finden – aber was ist eine gute Seite?



Speicherplatz ist so billig geworden, daß ein einzelner Computer – der, auf dem eine Suchmaschine läuft – große Teile des Webs in Kopie vorrätig halten kann. In der einfachsten Ausführung hält eine Suchmaschine zu jedem Wort eine Liste aller bekannten Seiten, in denen dieses Wort vorkommt. Wer sich also über Akupunktur informieren will, fragt eine Suchmaschine nach diesem Begriff und erhält Verweise auf alle Seiten, die das Wort "Akupunktur" (in dieser Schreibweise) enthalten. Eine solche Sammlung von Listen wird Index genannt.

Einen Index zu erstellen und aktuell zu halten ist keine leichte Aufgabe (vergleiche "Strategien der Informationssuche" von Clifford Lynch, Spektrum der Wissenschaft, Mai 1997, S. 90). Das Schwierigste ist, unter den vielen Stellen, an denen ein Wort vorkommt, die interessanten zu finden. Nehmen wir eine auf den ersten Blick unproblematische Suche: nach der Fluggesellschaft "Air Nepal". Als dieser Artikel geschrieben wurde, lieferte eine Suchmaschine etwa 100 Seiten. Welche davon sind die 20 besten? Dabei ist nicht objektiv mathematisch beschreibbar, was eine gute Seite ist; vielmehr hat jeder Benutzer seine eigenen Qualitätskriterien.

Suchmaschinen wie Yahoo!, AltaVista, HotBot, Lycos, Infoseek und Excite ordnen Webseiten nach Wichtigkeit mit Hilfe von sogenannten Rangfunktionen, die auf Faustregeln ("Heuristiken") beruhen. Sie müssen nicht nur bei einem simplen Suchkriterium wie "Air Nepal" brauchbare Ergebnisse liefern, sondern auch bei allgemeineren Begriffen wie "Flugzeug", die in mehr als einer Million Webseiten vorkommen. Woran erkennt man daraus die 20 wichtigsten?

Einfache Heuristiken zählen aus, wie oft der Suchbegriff in der Seite vorkommt, und werten ein Auftreten am Anfang der Seite höher als in der Mitte oder am Ende. Das führt zu spektakulären Fehlschlägen, wenn der Text in irgendeinem Sinne ungewöhnlich ist. Das Buch "The Kandy-Kolored Tangerine-Flake Streamline Baby" von Tom Wolfe etwa enthält gleich zu Anfang mehrere Dutzend mal das Wort hernia (Leistenbruch) und würde damit als sehr relevant für dieses Thema eingeschätzt. Verfeinerte Versionen dieser Heuristik geben Wörtern im Titel, in Überschriften oder in Großdruck größeres Gewicht.

Solche Strategien werden regelmäßig von kommerziellen Anbietern unterlaufen, mit der Absicht, die eigene Webseite möglichst weit oben in der Rangordnung der Suchmaschinen zu plazieren. So findet man beispielsweise Webseiten mit Titeln wie "Billige Flüge Billige Flüge Billige Flüge", oder Seiten, in denen sorgfältig gewählte Phrasen etliche Male in unsichtbaren Schriftgrößen und Farben wiederholt werden. Dieses sogenannte spamming ist inzwischen das Haupthindernis für die Unterhaltung einer effektiven Suchmaschine.

Aber selbst ohne Spamming bleiben die grundlegenden Annahmen, auf denen herkömmliche Textsuche beruht, fragwürdig. Paradoxerweise steht in relevanten Seiten nicht immer der entscheidende Suchbegriff, während andere, die ihn enthalten, vollkommen irrelevant sind. Die Umgangssprache ist nämlich reich an Synonymen (verschiedenen Wörtern mit gleicher Bedeutung) und Polysemen (verschiedenen Bedeutungen für dasselbe Wort). Wer nach "Kraftfahrzeug" sucht, findet all jene Seiten nicht, in denen ausschließlich das Synonym "Auto" verwendet wird. Die Polysemie ist dafür verantwortlich, daß eine Suche nach "Jaguar" einem Tausende von Seiten über – unter anderem – Wildkatzen, Autos und eine Football-Mannschaft beschert.

Wir wollen Suchverfahren dadurch verbessern, daß wir Informationen über semantische Beziehungen (Bedeutungsverwandtschaften) von Wörtern mit einbringen. Typischerweise sind es Linguisten, die solche semantischen Netze knüpfen; George Miller und seine Mitarbeiter an der Universität Princeton (New Jersey) haben mit ihrem Projekt "WordNet" wegweisende Arbeit geleistet. Ein Indexsuchprogramm mit Zugriff auf ein semantisches Netzwerk könnte etwa zum Stichwort "Kraftfahrzeug" das Synonym "Auto" finden und daraufhin nach allen Webseiten suchen, in denen mindestens eines dieser Wörter vorkommt. Dieses Verfahren ist jedoch ein zweischneidiges Schwert: Es hilft bei Synonymen, kann aber gleichzeitig das Polysemproblem verschärfen.

Selbst die Lösung des Synonymproblems ist unbefriedigend. Da das Web keine Sprachgrenzen kennt, sind Aufbau und Unterhaltung eines vollständigen und kulturübergreifenden semantischen Netzes gewaltige Aufgaben. Hinzu kommt, daß gerade für das Internet zahlreiche Wörter neu entstehen und alte mit neuen Bedeutungen belegt werden.

Unsere Arbeit am Projekt Clever der IBM wurde durch diese verwirrende Vielzahl von Problemen motiviert. Uns wurde bald klar, daß die üblichen, nur mit dem Text arbeitenden Suchverfahren die Milliarden von sorgfältig installierten Hyperlinks zwischen Webseiten schlicht außer acht lassen. Wie aber könnte man diese Information ausnutzen?

Wer mit einer Suchmaschine nach "Harvard" fragt, will in der Regel etwas über die Universität dieses Namens wissen und wäre dementsprechend angemessen bedient mit der Begrüßungsseite ("Homepage") der Universität, von der aus sie ihre Web-Besucher auf weitere Seiten verweist. Das Wort "Harvard" kommt jedoch auf mehr als einer Million Webseiten vor, und die Homepage der Harvard-Universität enthält es weder besonders häufig noch besonders nah am Anfang oder in einer anderen für herkömmliche Suchverfahren hervorstechenden Art und Weise. Nichts in der Homepage scheint einen Hinweis auf ihre Bedeutung zu geben.

Webseiten werden mit den verschiedensten Absichten gestaltet. Große Unternehmen wollen damit vor allem ein gewisses Bild, ein feel, von sich vermitteln, und das kann sehr verschieden von dem sein, was das Unternehmen eigentlich tut. So enthält die Homepage der Firma IBM nirgends das Wort "Computer". In solchen Situationen sind herkömmliche Suchverfahren zum Scheitern verurteilt.

Betreiber von Suchmaschinen neigen bislang dazu, das Problem durch Eingriffe im Einzelfall zu lösen. Schließlich glauben sie zu wissen, was die richtige Antwort auf gewisse Suchanfragen ist, und wenn eine Rangfunktion diese trotz sorgfältiger Programmierung nicht anbringt, setzen sie lieber von Hand an die Spitze einer Liste zu einem Wort wie "Harvard" die "richtige" Antwort.

Eine ganze Reihe von Suchmaschinen arbeitet nach diesem Prinzip. Manche, wie zum Beispiel Yahoo!, enthalten ausschließlich handverlesene Seiten. Aber wie soll eine begrenzte Anzahl menschlicher Experten alle Antworten auf eine unbegrenzte Anzahl von Fragen einigermaßen vollständig und aktuell halten, während das Netz um eine Million Seiten pro Tag wächst?



Das Wissen nutzen, das in den Hyperlinks steckt



Wir haben uns für einen anderen Ansatz entschieden. Im Zentrum stehen bei uns die Hyperlinks. Wir gehen davon aus, daß jeder dieser Verweise eine implizite Empfehlung für die Seite ist, auf die er zeigt. Das ist offensichtlich der Fall, wenn eine Menschenrechtsorganisation in ihrer Homepage einen Link auf Amnesty International hat.

Natürlich gibt es auch Links, die lediglich das Surfen erleichtern ("Zurück zur Homepage"), bezahlte Reklame für ein Unternehmen sind ("Mit einem Mausklick zu Ihrem Traumurlaubsziel") oder Ablehnung ausdrücken ("Klicken Sie hier, wenn Sie sehen möchten, was dieser Narr zu sagen hat!"). Wir glauben jedoch, daß bei Betrachtung einer ausreichend großen Anzahl von Links der Zustimmungsaspekt dominiert.

Neben Webseiten, die in diesem Sinne viel Zustimmung ernten, gibt es andere, die vorrangig als Wegweiser zu diesen fungieren. Solche Knotenpunkte im Web können in einer ganzen Reihe von Varianten auftreten, von professionell erstellten Listen in kommerziellen Webseiten hin zu privaten Sammlungen mit dem Titel "Meine Lieblingslinks". Es ist zwar sehr schwierig, "Quelle" und "Knotenpunkt" unabhängig voneinander zu definieren; aber wir können zumindest so viel sagen: Eine renommierte Quelle ist eine Seite, auf die von einer großen Anzahl von Knotenpunkten verwiesen wird, und ein Knotenpunkt ist gut, wenn er auf eine große Anzahl von respektablen Quellen verweist.

Wenn auf diese Weise "Quelle" durch "Knotenpunkt" erklärt wird und "Knotenpunkt" durch "Quelle", scheint sich die Definition hoffnungslos im Kreise zu drehen. Aber es gelingt, sie sinnvoll zu machen, und zwar mit folgendem Verfahren. Wir stellen zunächst – zum Beispiel mit herkömmlicher Textsuche – eine Liste mit Kandidaten-Seiten zusammen, also solchen, die möglicherweise für ein bestimmtes Thema geeignet sind, und geben eine grobe Einschätzung ihrer Qualität als Quelle oder Knotenpunkt zum Thema ab. Diese Zahlen – man denke an Schulnoten oder Punktzahlen auf einer Qualitätsskala – dienen uns als Startwerte eines Algorithmus, dessen zwei Teilschritte mehrfach ("iterativ") zu durchlaufen sind.

Wir berechnen zunächst die Schulnoten der Knotenpunkte neu. Und zwar ist die neue Note eines Knotenpunktes um so besser, je besser die – bisherigen – Noten der Quellen sind, auf die er verweist. Im zweiten Teilschritt bewerten wir auf entsprechende Weise die Quellen neu: Eine Quelle gilt als "gut", wenn viele "gute" Knotenpunkte auf sie verweisen. Nach einigen Iterationsschritten ändern sich die Bewertungen kaum noch.

Wir haben diesen Algorithmus in unserem Prototyp einer Suchmaschine namens "Clever" installiert. Für jeden Suchbegriff, sagen wir "Akupunktur", holt sich Clever zuerst etwa 200 Webseiten über einen herkömmlichen Index und ergänzt diese Liste dann durch all die Seiten, die auf eine dieser Seiten verweisen oder auf die von einer dieser Seiten verwiesen wird. Erfahrungsgemäß enthält diese Primärliste 1000 bis 5000 Seiten.

Am Anfang weist Clever jeder dieser Seiten vorläufige Qualitätswerte für ihre Eignung als Quelle oder Knotenpunkt zu. Dann bessert es diese Werte in der beschriebenen Weise nach: Die neue Quellennote einer Seite ist gleich der Summe aller Knotenpunktnoten der Seiten, die auf sie verweisen, und die neue Knotenpunktnote einer Seite ist die Summe aller Quellennoten der Seiten, auf die sie verweist.

Clever wiederholt dieses Verfahren, bis sich die Noten mehr oder weniger eingependelt haben. Die besten Seiten in jeder Kategorie sind dann leicht abzulesen. Es ist nicht ausgeschlossen – und kommt gelegentlich vor –, daß eine Seite gute Noten in beiden Kategorien erhält.

Anschaulich kann man sich das Ergebnis des Algorithmus etwa so vorstellen: Das Web ist ein riesiges Netz mit einer ungeheuren Anzahl von Knoten, die untereinander durch scheinbar zufällige Verbindungen verknüpft sind. Clever sucht dann für eine gegebene Menge von Seiten zu einem gewissen Suchbegriff eine Teilmenge von Knoten heraus, die untereinander am dichtesten verbunden sind.

Es stellt sich heraus, daß die Aktivität von Clever präzise mit Begriffen der Mathematik, genauer: der linearen Algebra, beschreibbar ist. Die Hyperlinkstruktur der Primärliste ist durch eine Matrix (die sogenannte Inzidenzmatrix) darstellbar, die Liste aller Knotenpunkt- beziehungsweise Quellennoten ist ein Vektor, und ein Schritt des Algorithmus besteht darin, die Inzidenzmatrix mit einem Notenvektor zu multiplizieren; das Ergebnis ist ein – nachgebesserter – Notenvektor der jeweils anderen Kategorie. Daß sich die (geeignet normierten) Notenwerte mit zunehmender Anzahl an Iterationen stabilisieren, wird in der Sprache der linearen Algebra so ausgedrückt: Das Verfahren konvergiert, und zwar gegen einen Eigenvektor. In einem gewissen Sinne ist dieser Vektor die Lösung eines durch die Inzidenzmatrix bestimmten Gleichungssystems.

Mit Hilfe der linearen Algebra können wir nicht nur beweisen, daß das Verfahren konvergiert, sondern auch, daß es schnell geht: Bei 3000 Primärseiten erhalten wir bereits nach fünf Nachbesserungsschritten durchaus akzeptable Ergebnisse. Darüber hinaus sind die Endergebnisse im wesentlichen unabhängig von den anfänglichen Schätzwerten; man könnte sogar am Anfang alle Werte auf 1 setzen. Die endgültigen Knotenpunkt- und Quellnoten sind demnach nicht Ergebnis eines Vorurteils unsererseits, sondern ein echtes Wesensmerkmal der Primärliste.

Ein angenehmer Nebeneffekt des Verfahrens ist die Separierung von Webseiten in Gruppen. So lassen sich in einer Suche nach Informationen über Abtreibung mit etwas zusätzlicher Analyse die Webseiten von Abtreibungsgegnern und -befürwortern automatisch trennen, weil Angehörige jeder Fraktion eher auf Seiten der eigenen als auf solche der gegnerischen Gruppe verweisen.

So chaotisch und unsystematisch das Web gewachsen ist, es hat dennoch eine innere – wenn auch unvollkommene – Struktur in Gestalt seiner Hyperlinks. Und genau diese ist es, die das Programm Clever aufspürt.

Es gibt zahlreiche Parallelen zwischen unserem Algorithmus und der herkömmlichen Analyse von Quellenverweisen in wissenschaftlichen Veröffentlichungen. Die wohl bekannteste Maßzahl für die Bedeutung einer wissenschaftlichen Arbeit (und der Zeitschrift, in der sie erscheint) ist ihr "Einflußfaktor" (impact factor). Der Begriff stammt von dem renommierten Informationswissenschaftler Eugene Garfield, dem Gründer des "Science Citation Index". Diese Zeitschrift führt zu – fast – jeder in der wissenschaftlichen Literatur erschienenen Arbeit die Artikel auf, in denen sie zitiert wird. Der impact factor ist im wesentlichen die Anzahl dieser Zitate.

Demnach wäre der Einflußfaktor einer Webseite gleich der Anzahl der Links, die auf sie verweisen. Dieses Maß wäre jedoch irreführend, denn es würde etwa die Homepage der "New York Times" extrem hoch bewerten, ohne Rücksicht auf das Thema, das den Anfrager interessiert.

Auch Garfields klassischer impact factor, der jedem Quellennachweis das gleiche Gewicht zuteilt, ist als verbesserungsbedürftig erkannt worden. Müßte man nicht ein Zitat in einer wichtigen Zeitschrift höher bewerten als eines in einem obskuren Blatt? Schon, aber wie definiert man eine wichtige Zeitschrift? Dadurch, daß ihre Artikel in wichtigen Zeitschriften zitiert werden – und damit ist man bei demselben Zirkelschlußproblem wie wir bei der Bewertung von Quellen und Knotenpunkten. Bereits 1976 lösten Gabriel Pinski und Francis Narin von CHI Research in Haddon Heights (New Jersey) das Problem auf im wesentlichen dieselbe Weise wie wir: durch Iteration, nur ohne die Unterscheidung zwischen Quellen und Knotenpunkten. Mehrere gute Quellen verstärken sich gewissermaßen gegenseitig in ihrem Einflußgewicht (impact weight).



Zitatenanalyse unter den Bedingungen des WWW



Das funktioniert in der herkömmlichen wissenschaftlichen Literatur, aber nicht im Web. Im Cyberspace kommt es nämlich häufig vor, daß konkurrierende Institutionen, wie zum Beispiel Netscape und Microsoft auf dem Gebiet der Web-Browser, einander ignorieren und somit nur indirekt über Knotenpunkte verknüpft sind. Dagegen ist es in wissenschaftlichen Artikeln gang und gäbe, eine Arbeit zu zitieren, die in einer konkurrierenden Zeitschrift veröffentlicht wurde, so daß der Bedarf nach Knotenpunkten viel weniger dringlich ist.

Wir sind nicht die einzigen, die das Potential von Hyperlinks zur Navigierung des Webs erkunden. Sergey Brin und Lawrence Page von der Universität Stanford (Kalifornien) haben eine Suchmaschine namens "Google" entwickelt, die Webseiten anhand ihrer Links nach dem Vorbild der Einflußgewichte von Pinski und Narin bewertet. Ihr Programm hüpft von Webseite zu Webseite – mit welchem Link, wird vom Zufall bestimmt. Dabei gerät es auf manche Seiten häufiger als auf andere. Die Anzahl der Male, die Google auf eine bestimmte Seite gerät, dient als vorläufige Punktzahl für ihre Bedeutung. Die endgültige Bewertung einer Seite ist die Summe der vorläufigen Punktzahlen der Seiten, die auf sie verweisen. Auf eine spezifische Frage hin bestimmt Google auf klassische Weise alle Seiten, die den Suchtext enthalten, und präsentiert sie dem Anfrager geordnet nach diesen vorab bestimmten Bewertungen.

Insbesondere hat Google Webseiten bereits bewertet, bevor die erste Frage kommt; dadurch ist es schneller als Clever, das für jede Frage eine neue Primärliste zusammenstellt und erst daraufhin seine Bewertungen berechnet. Außerdem folgt Google allen Links nur in eine Richtung – vorwärts –, während Clever auch nachsieht, welche Seiten auf eine bestimmte Quelle verweisen. Damit macht es sich die Neigung mancher Menschen zunutze, knotenpunktähnliche Strukturen zu schaffen, die ihr eigenes Fachwissen widerspiegeln.

Wir sind dabei, Clever mit einer Reihe von Verbesserungen zu versehen. Ein wesentliches Prinzip ist es, Text und Hyperlinks zu integrieren. So denken wir daran, gewissen Links abhängig von der Stelle, an der sie im Text stehen, mehr Bedeutung zuzumessen als anderen, etwa wenn der Suchbegriff häufig und in der Nähe eines Links erscheint.

Erste Experimente lassen den Schluß zu, daß sich mit dieser Verfeinerung die Trennschärfe erheblich verbessert. (Bislang neigt Clever dazu, bei eng gestellten Fragen – zum Beispiel nach einem speziellen Gedicht von Goethe – mit viel zu allgemeinen Informationen – etwa über die Rolle der klassischen Literatur im 18. und 19. Jahrhundert – aufzuwarten.) Entsprechend den zahlreichen im Web gebräuchlichen Stilvarianten sehen wir noch Möglichkeiten, aus dem Inhalt einer Seite weitere automatische Schlüsse zu ziehen.

Wir haben außerdem damit begonnen, vorgefertigte Listen von Quellen zu breiteren Themen zusammenzutragen. Erste Ergebnisse zeigen, daß unsere automatisch erstellten Listen durchaus mit den handverlesenen von Yahoo! und Infoseek konkurrieren können. Weiter stellte sich heraus, daß das Web eine Reihe von eng verknüpften Interessengruppen zu mehr oder weniger exotischen Themen beherbergt, wie zum Beispiel Fans des Sumo-Ringkampfs, die wochenends mit massigen Plastikrüstungen angetan Schaukämpfe gegeneinander austragen. Wir suchen nach effektiven und automatischen Methoden, um diese versteckten Gemeinschaften zugänglich zu machen.

Das Web hat sich in den letzten fünf Jahren dramatisch gewandelt. Wie es in fünf Jahren aussehen wird, kann heute noch niemand vorhersagen. Wird selbst das Erstellen eines schlichten Index für das Web ein hoffnungsloses Unterfangen werden? Wenn ja, was heißt dann Suchen im Web? Eins können wir heute schon sagen: Die schiere Menge an Information wird die Verfasser von Suchprogrammen weiter gut beschäftigen.

Literaturhinweise


Die neuesten Informationen über Suchmaschinen findet man über www.searchenginewatch.com. Das Projekt WordNet ist beschrieben in "WordNet: An Electronic Lexical Database", herausgegeben von Christiane Fellbaum (MIT Press, 1998). Das iterative Verfahren zur Ermittlung von Quellen und Knotenpunkten ist erstmalig dargestellt in "Authoritative Sources in a Hyperlinked Environment" von Jon M. Kleinberg in "Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms", herausgegeben von Howard Karloff (SIAM/ACM-SIGACT, 1998). Neuere Entwicklungen finden sich auf der Webseite des Almaden-Forschungszentrums: www.almaden.ibm.com/cs/k53/clever.html. Ein guter Überblick über die Zitatenanalyse ist "Introduction to Informetrics" von Leo Egghe und Ronald Rousseau (Elsevier Science Publishers, 1990). Näheres über das Projekt Google findet man unter www.google.com


Aus: Spektrum der Wissenschaft 8 / 1999, Seite 44
© Spektrum der Wissenschaft Verlagsgesellschaft mbH