Forschungsbericht 2011 - Max-Planck-Institut für Informatik

Antworten auf komplexe Fragen – Der nächste Schritt für eine effektivere Suche im Internet

Answering complex queries – The next step in searching the internet more effectively

Autoren
Wischnewski, Patrick
Abteilungen
Max-Planck-Forschungsgruppe Automation of Logic (Christoph Weidenbach)
Zusammenfassung
In der heutigen Zeit, insbesondere mit Blick auf das Internet, gibt es eine Unmenge an verfügbarem Wissen. Um mit diesem Wissen, komplexe Anfragen präzise zu beantworten, muss ein Computer in der Lage sein, dieses Wissen so zu verarbeiten, dass er daraus logische Schlussfolgerungen ziehen kann. Am Max-Planck-Institut für Informatik werden entsprechende Methoden entwickelt, die komplexe Anfragen mithilfe von großen Wissenssammlungen, die aus mehreren Millionen Einträgen bestehen, in wenigen Sekunden beantworten können.
Summary
Today, there is a vast quantity of knowledge available, in particular on the Internet. In order to precisely answer complex queries in terms of this knowledge, a computer has to be able to perform reasoning on this knowledge. At the Max Planck Institute for Informatics methods are developed that allow a computer to efficiently reason about knowledge bases consisting of several million entries. These methods answer complex queries with respect to such a knowledge base in less than one second.

Einleitung

In der heutigen Zeit nimmt die Anzahl an verfügbaren Informationen insbesondere durch das Internet stetig zu. Es wird damit immer schwieriger in dieser immensen Menge an Informationen die richtigen Antworten auf unsere Fragen zu finden. Mithilfe von Suchmaschinen lassen sich bereits Antworten auf viele Fragen im Internet finden. Allerdings erlauben diese Suchmaschinen eine Suche nur rein syntaktisch anhand von Schlüsselwörtern. Aus der Anfrage "Welcher Physiker ist dort geboren, wo alle seine Kinder geboren sind?" extrahiert ein Suchdienst die Schlüsselwörter "Physiker", "Kind", "alle" und "geboren" und liefert als Ergebnis Dokumente, die diese Schlüsselwörter enthalten. Die Wörter der Anfrage müssen in den gefundenen Dokumenten exakt vorkommen. Auf die obige Anfrage bekommt man eine Fülle von Dokumenten, die die extrahierten Schlüsselwörter enthalten, aber typischerweise nicht das gesuchte Ergebnis. Eine Umformulierung der Frage kann zum gewünschten Ergebnis führen. Das Problem liegt darin, dass die Suchmaschine die Bedeutung der Informationen in den Dokumenten und der Anfrage nicht kennt, sondern nur rein syntaktisch mit den Wörtern, also den Zeichenketten, arbeitet. Im Folgenden werden Methoden aufgezeigt, die am Max-Planck-Institut für Informatik entwickelt wurden und die es einem Computer ermöglichen aus vorhandenem Wissen effizient Schlussfolgerungen zu ziehen und somit komplexe Anfragen zu beantworten.

Ontologien

Damit ein Computer eine präzise Antwort auf eine gestellte Frage geben kann, muss er in der Lage sein, die Bedeutung von Wörtern und Sätzen und das damit transportierte Wissen zu verarbeiten und zu verstehen. Deshalb muss dieses Wissen explizit und für einen Computer nutzbar gemacht werden. Für obige Anfrage handelt es sich bei solchem Wissen um die Tatsache, dass Physiker und Kinder Menschen sind und man nur an einem Ort geboren sein kann. Die Aggregation allgemeinen Wissens dieser Art heißt Ontologie. Bestimmte Ontologien können automatisch erstellt werden. Ein Beispiel für eine automatisch generierte Ontologie ist die am Max-Planck-Institut für Informatik entwickelte Ontologie YAGO [1]. Die YAGO Ontologie enthält große Teile des Wissens der online Enzyklopädie Wikipedia [L1]. Abbildung 1 zeigt ein Beispiel für Wissen aus einer Ontologie.

Automatisches Schließen in Ontologien

Eine Herausforderung besteht aktuell darin, all die Fragen in kurzer Zeit zu beantworten, die sich mithilfe des in einer Ontologie verankerten Wissens beantworten lassen. Dazu ist es zunächst notwendig, die Ontologie in eine geeignete Sprache, eine sogenannte beschreibende Logik, zu überführen. Eine in Logik übersetzte Ontologie hat die Eigenschaft, dass der Computer, mithilfe geeigneter Methoden, prinzipiell alles herleiten kann, was aus der Ontologie folgt.

Mit solchen Methoden kann man zum Beispiel aus den Information "Alle weiblichen Kinder sind Töchter", und "Ève ist ein Kind von Pierre Curie und weiblich" automatisch folgern, dass Ève Curie eine Tochter von Pierre Curie ist. Diese Art des automatischen Schließens ist notwendig, wenn Fragen mithilfe einer Ontologie beantwortet werden sollen, deren Antwort aber nicht explizit in der Ontologie vorhanden ist; aber daraus gefolgert werden kann.

Um auf diese Weise effektiv Fragen beantworten zu können, wird die Ontologie zunächst kompiliert; sie wird in eine kompakte Darstellung aller notwendigen logischen Konsequenzen überführt, die frei von Widersprüchen ist. Allerdings sind die zur Kompilation notwendigen Operationen auf der Logik sehr rechenintensiv, was die bisher bekannten Verfahren auf Ontologien mit mehreren 10 Millionen Einträgen nicht in akzeptabler Zeit leisten. Die Operationen auf die Struktur von Ontologien so abzustimmen, dass eine effiziente Kompilation möglich ist, ist die Herausforderung, die es zu bewältigen gilt, um effektiv Antworten auf Fragen auch in solch großen Ontologien zu berechnen. Aktuell kompilieren die am Max-Planck-Institut für Informatik entwickelten Methoden Ontologien von bis zu 10 Millionen Einträgen in etwa einer Stunde [2]. Diese Methoden kompilieren insbesondere die in Logik übersetzte YAGO Ontologie.

Beantwortung von komplexen Fragen

Mithilfe der durch das Kompilieren erreichten Darstellung kann der Computer effizient Antworten auf Fragen finden, die aus der ursprünglichen Ontologie folgen. Diese Darstellung erlaubt es auch Fragen zu beantworten, die eine komplexe Struktur haben. Die Anfrage aus der Einleitung ist ein Beispiel für eine Anfrage mit einer komplexen Struktur, einer sogenannten Quantorenalternierung: "es gibt (Physiker) - für alle (Kinder)". Bei der Frage "Hat jeder deutsche Physiker mindestens einen Vorfahren, der auch Naturwissenschaftler war?" handelt es sich zum Beispiel um eine "für alle - es gibt" Anfrage. Anfragen, die Quantorenalternierung enthalten, sind besonders schwierig zu beantworten. Daher gilt es auch hier effiziente Verfahren zu entwickeln, die Anfragen mit beliebigen Verschachtelungen solcher Quantorenalternierungen beantworten.

Um Anfragen in einer Ontologie mit mehreren Millionen Einträgen effizient zu beantworten, sollten möglichst nur die Einträge betrachtet werden, die notwendig sind um die Anfrage zu beantworten. Aufgrund der Eigenschaften der durch Kompilierung erreichten Darstellung der Ontologie, ist es möglich, die zur Beantwortung einer Anfrage relevanten Einträge aus der Ontologie zu filtern. Für das Beispiel aus der Einleitung gilt: Wenn Pierre Curie als Physiker identifiziert wurde, müssen nur noch dessen Kinder betrachtet werden, um zu verifizieren, ob Pierre Currie die Antwort auf die Anfrage ist. Mithilfe geeigneter Indextechniken lassen sich die Kinder von Pierre Curie effizient aus der Ontologie extrahieren. Ein solcher Index funktioniert ähnlich dem alphabetischen Index eines Buches. Effizienz ist hier von entscheidender Bedeutung, da auf diese Index Datenstrukturen mehrere zehntausendmal während der Bearbeitung einer einzigen Anfrage zugegriffen wird. Abbildung 2 zeigt einen vereinfachten Auszug aus einem solchen Index, mit dessen Hilfe auf Pierre Curies Kinder in nur zwei Schritten zugegriffen werden kann, obwohl der Index noch Millionen anderer Einträge enthält. Die am Max-Planck-Institut für Informatik entwickelten Verfahren beantworten bereits heute Anfragen mit Quantorenalternierungen in der kompilierten YAGO Ontologie mit 10 Millionen Einträgen in wenigen Sekunden.

Die Software SPASS YAGO

Die entwickelten Methoden wurden auf Basis des automatischen Beweisers SPASS [3] implementiert. Die daraus resultierende Version heißt SPASS YAGO. Unter der Internetadresse http://spassyago.spass-prover.org gibt es ein experimentelles Webinterface, das es erlaubt das System zu testen. Abbildung 3 gibt einen Überblick über dessen Architektur. Die YAGO Ontologie wurde dafür in Logik übersetzt, mit dem Kompilierungsmodul kompiliert und in den Index geladen. Damit steht das System bereit um online Anfragen zu bearbeiten. Das System SPASS YAGO läuft als Serverprozess auf einem Server im Max-Planck-Institut für Informatik. Mithilfe des Webinterfaces können Anfragen an das System gesendet werden, die vom Antwortberechnungsmodul bearbeitet werden. Im Anschluss werden die berechneten Antworten wieder an das Webinterface gesendet und dort angezeigt.

Zukunftsperspektiven

Wie die aktuellen Ergebnisse des Max-Planck-Instituts für Informatik zeigen, können Computer heute schon präzise Antworten auf komplexe Anfragen geben und dabei auch neues Wissen aus bereits Vorhandenem durch Schlussfolgern herleiten. Die dabei verwendeten Wissensbasen können aus mehreren Millionen Einträgen bestehen.

Gegenwärtig müssen die Anfragen allerdings in Logik formuliert sein, damit der Computer diese auch versteht. Die Entwicklung eines Interfaces, das natürlich sprachliche Anfragen in die entsprechende Formulierung in Logik übersetzt, ist Gegenstand aktueller Forschung.

Ebenso wird erforscht, wie man zeitliche Aspekte in die hier beschriebenen Verfahren integrieren kann, damit auch zeitliche Beziehungen zwischen Einträgen in der Wissenssammlung bei der Beantwortung von Fragen berücksichtigt werden. Dies würde es beispielsweise ermöglichen Anfragen wie "Welcher Physiker überlebte alle seine Kinder" automatisch zu beantworten.

Suchanek, F. M.; Kasneci, G.; Weikum, G.
Yago - A Core of Semantic Knowledge
16th international World Wide Web conference (WWW 2007)
Suda, M.; Weidenbach, C.; Wischnewski, P.
On the Saturation of YAGO
5th International Joint Conference on Automated Reasoning, IJCAR 2010, LNCS 6173, 441-456 (2010)
Weidenbach C.; Dimova D.; Fietzke A.; Kumar R.; Suda M.; Wischnewski P.
SPASS Version 3.5
22nd International Conference on Automated Deduction, CADE 2009, LNCS 5663, 140-145 (2009)
Zur Redakteursansicht