DOI 10.1007/s00450-007-0031-3

R E G U L Ä R E B E I T R Ä G E

Informatik Forsch. Entw. (2008) 22: 71–84

Strategien zur webbasierten Multilingualen Fragebeantwortung

Wie Suchmaschinen zu Antwortmaschinen werden

Gunter Neumann

Eingegangen: 20 Oktober 2006 / Angenommen: 12 Juli 2007 / Online veroffentlicht: 4 August 2007© Springer-Verlag 2007

Zusammenfassung Wir stellen eine Reihe von innovativenMethoden zur webbasierten multilingualen Fragebeantwor-tung in offenen Domanen vor. Insbesondere werden neuar-tige Strategien zur Bestimmung optimaler Antwortkontexteund zur Extraktion von exakten Antworten auf Basis vonsprachunabhangigen, datengetriebenen maschinellen Lern-verfahren beschrieben. Es werden zwei alternative Metho-den fur die crosslinguale Frageanalyse skizziert mit derenHilfe fur eine Anfrage in einer naturlichen Sprache Antwor-ten in Dokumenten einer anderen naturlichen Sprache be-stimmt werden konnen. Alle Methoden sind detailliert eva-luiert und weisen eine vielversprechende Performanz auf.

Schlusselworter Fragebeantwortung · domanenoffen ·crosslingual · datengesteuerte Methoden

Abstract We present a series of innovative methods fora webbased multilingual question answering in open do-mains. In particular, we present novel strategies for the de-termination of optimal answer contexts and for the extrac-tion of exact answers on the basis of language-independent,data-driven Machine Learning algorithms. Two alternativemethods for the crosslingual question analysis are presentedthat are used for finding answers in documents of one nat-ural language using a query formulated in another naturallanguage. All methods are evaluated in detail and demon-strate a promising performance.

G. Neumann (�)LT–lab, DFKI,66123 Saarbrucken, Deutschlande-mail: neumann@dfki.de

Keywords Question answering · Open–domain ·Crosslingual · Data-driven methods

CR subject classification I.2.6 · I.2.7 · J.1 · K.3.2 · D.3.3 ·D.2.2

1 Einfuhrung

Textbasierte Systeme zur automatischen Fragebeantwor-tung (textQA) empfangen frei formulierte, geschriebeneFragen in naturlicher Sprache (natural language, NL) undextrahieren die entsprechenden Antworten aus sehr großenBestanden von unstrukturierten Dokumenten. Sie liefernprazise Antworten, also Textausschnitte, die genau der Ant-wort entsprechen (z.B. ein Personenname, ein Zeitausdruckoder eine definitorische Textpassage) und nicht nur Ver-weise auf Dokumente oder Paragraphen, die die Antworten(moglicherweise) enthalten, wie dies bei gangigen Such-maschinen zur Zeit der Fall ist. Der aktuelle Erfolg in derForschung von textQA-Systemen liegt zentral in der inno-vativen Kombination von Technologien aus verschiedenenBereichen der Informatik, wie z.B. Information Retrieval,Informationsextraktion, Sprachtechnologie und KunstlicheIntelligenz (cf. [13]). Bedeutsam fur den aktuellen Erfolg istsicher auch die Tatsache, dass textQA-Systeme und Techno-logien seit 1999 im Rahmen der nordamerikanischen TRECKonferenzreihe (http://trec.nist.gov/), sowie seit 2003 imRahmen der europaischen CLEF Initiative (http://www.clef-campaign.org/) systematisch evaluiert werden.

Allerdings stellt die Adaption und Skalierung dieserneuen textQA-Technologien fur das Web und damit fur dieWeiterentwicklung aktueller Suchmaschinentechnologienenorme Herausforderungen bereit, insbesondere auch unterder Vorgabe, dass die Systemreaktionszeit nicht signifikant

1 3

72 Neumann

steigen darf (cf. [16]). Man betrachte beispielsweise dieriesige Menge an Webinhalten, die die gegenwartig bestenSuchmaschinen zu indizieren in der Lage sind (Milliardenvon Webseiten). Wahrend sich eine automatische linguis-tische und semantische Indizierung von TREC ahnlichenDatenmengen (ca. 1 GB Nachrichtentext) zur Beantwortungeiner eingeschrankten Menge von Fragen mittels sprach-technologischer Vorverarbeitung als sehr fruchtbar fur dieEntwicklung der textQA-Technologien erwiesen hat (wo-bei Aspekte der Systemreaktionszeit meist noch keine Rollespielen), erscheint die gleiche Vorgehensweise fur das Webzumindest gegenwartig außer Reichweite. Zudem sind dieTREC und CLEF Korpora statisch, da sie auf eine kurzeund fixe Zeitspanne beschrankt sind. Im Web werden neueDokumente permanent hinzugefugt und bereits existie-rende Dokumente konnen jederzeit verandert oder geloschtwerden. Systeme zur webbasierten Fragebeantwortung(webQA) sind damit verstarkt mit Problemen wie Redun-danz, Aktualitat und Zuverlassigkeit konfrontiert. Es mussdabei auch bedacht werden, dass ein Text in der Regeleinen hohen Interpretationsspielraum umfasst, so dass einestatische, situationsunabhangige Analyse des Textes nureingeschrankt moglich ist. Hinzu kommt die wachsendeMehrsprachigkeit der Webinhalte und der damit steigendeBedarf an einer crosslingualen Fragebeantwortung.

Es existieren bereits erste webQA-Systeme, die erfolg-reich zeigen, wie durch Einsatz moderner Sprachtechnolo-gie gepaart mit einer systematischen Ausnutzung der Red-undanz der Webinhalte fortgeschrittene Technologien furzukunftige Antwortmaschinen erreichbar sind, vgl. [1, 4, 5,10, 18]. Diese Systeme verfugen uber eine vergleichbare Ar-chitektur und fuhren im Wesentlichen die folgenden dreiSchritte durch:

1. Transformation einer NL-Frage in eine Anfrage der spe-zifischen Suchmaschine.

2. Bestimmung von relevanten Webseiten durch eine stan-dardisierte Suchmaschine, z.B. Google, Live Search, Ya-hoo.

3. Extraktion der Antworten aus den Webinhalten.

Der erste Schritt ist notwendig, um optimal die Anfra-gesyntax der jeweiligen Suchmaschine zu bedienen undum die Zugriffswahrscheinlichkeit auf relevante Doku-mente zu erhohen. Dieser letzte Aspekt kann auch alsdie Bestimmung einer ,,Antwortkontext-Voraussage“ in-terpretiert werden. Beispielsweise wird hiermit eine NL-Frage Wie heißt der deutsche Bundesprasident? uberfuhrtin der deutsche Bundesprasident heißt oder DeutschlandsBundesprasident ist. Ohne Berucksichtigung einer vor-herigen Korpusanalyse entspricht diese Art der Trans-formation prinzipiell einer Versuch-und-Irrtum Strategie.Daher verwenden fortgeschrittene webQA-Systeme einestatistische Datenanalyse zur Bestimmung einer optima-

len Gewichtung der einzelnen Antwortkontexte (cf. [5]und [18]).

Was den zweiten Schritt betrifft, so liefern Suchma-schinen in der Regel nur Verweise auf relevante Doku-mente zusammen mit automatisch erstellten Textausschnit-ten (Snippets genannt). Sie bestehen aus kleinsten Textfrag-menten, in denen Terme der Suchanfrage vorkommen. Da-her werden in der Regel fur den dritten Schritt zuerst dieN-besten Dokumente auf den lokalen Rechner geladen, be-vor die eigentliche Antwortextraktion stattfindet (cf. [10]und [18]). Die Antwortextraktion wird dann analog dertextQA-Technologie mit Hilfe von kombinierten Sprach-und Wissenstechnologie-Komponenten durchgefuhrt. DieNotwendigkeit, relevante Dokumente dynamisch zu laden,hat allerdings einen negativen Effekt auf die Reaktions-zeit des gesamten webQA-Systems. Dumais et al. zeigen,dass fur die Beantwortung von faktenbasierten Fragen dieSnippets als Antwortquellen ausreichen konnen, wenn zumeinen eine Vielzahl von Antwortkontexten systematisch be-rechnet und zum anderen eine große Menge von Snip-pets (einige hundert bis tausend) fur die Antwortextraktionberucksichtigt wird (cf. [5]).

Aktuelle webQA-Systeme haben zur Zeit erheblicheBeschrankungen. Zum einen betrifft das die Anfrage-gesteuerte Berechnung potentieller Antwortkontexte. Zumanderen sind die Systeme in der Regel nur fur die Verar-beitung bestimmter Arten von NL-Fragen (meist einfachefaktenbasierte Fragen der Art ,,Wer/Wann/Wo“) optimiert.Hinzu kommt, dass die aktuell relevanten Systeme monolin-guale (uberwiegend englischsprachige) Systeme sind.

2 Innovative QA-Technologien am DFKI

Am DFKI haben wir einige dieser kritischen Punkte aufge-griffen1 und unsere Losungen durch folgende innovativewebQA-Technologien umgesetzt:

• Datengesteuerte Berechnung von Antwortkontexten:Antwortkontexte zu einer NL-Frage Q werden dyna-misch aus den Snippets berechnet, die die Suchmaschineunter direkter Verwendung von Q (also ohne vorherigeAnalyse und Transformation von Q) bestimmte.

• Multilinguale webQA-Technologien: Die Extraktion vonAntworten wird mit Hilfe von sprachunabhangigen, da-tengetriebenen maschinellen Lernverfahren realisiert.

• Crosslinguale Fragebeantwortung: Methoden der ma-schinellen Ubersetzung werden eingesetzt, um fur dieNL-Frage in einer Sprache (z.B. Deutsch) Antworten in

1 Und selbstverstandlich eine Menge anderer Aspekte wie Multime-dia, Personalisierung, Semantic Web, Answer Credibility etc., auf dieich in diesem Artikel aus Platzgrunden nicht eingehen kann.

1 3

Webbasierte Fragebeantwortung 73

Dokumenten einer anderer Sprache (z.B. Englisch) extra-hieren zu konnen.

Diese neuen Technologien wurden von uns systema-tisch mit Hilfe der QA-Korpora (sie bestehen aus manu-ell uberpruften Paaren von Fragen und deren Antworten)durchgefuhrt, die die Organisatoren von TREC und CLEFzur Verfugung stellen. Insbesondere im Bereich der cross-lingualen Fragebeantwortung haben wir in den letzten Jah-ren aktiv mit dem Sprachpaar Deutsch/Englisch im Rahmender CLEF teilgenommen und dort im internationalen Ver-gleich sehr gut abgeschnitten. So erzielten wir die bestenErgebnisse im monolingualen Fall – deutsche Fragen unddeutsche Dokumente – mit einer Akkuratheit von 42,32%bei 200 Testfragen zu beliebigen Themen. Im crosslingua-len Bereich erzielten wir mit einer Akkuratheit von 32,8%bei der Beantwortung von englischen Fragen in deutschenDokumenten ebenfalls die besten Ergebnisse. In beiden Sze-narien wird jeweils nur die beste von einem System be-rechnete Antwort berucksichtigt, wobei bei der manuellenAuswertung durch die Evaluatoren auch die Plausibilitat desKontextes (also der Satz, in dem die Antwort vorkommt)uberpruft wird.

Man beachte, dass die erzielte Akkuratheit z.B. im mo-nolingualen Fall bedeutet, dass fur ca. 85 von 200 demSystem bis dahin unbekannte Fragen zu beliebigen Themen,die beste von unserem System berechnete Antwort auch dierichtige ist. Ein weiteres haufig benutztes Maß ist der MeanReciprocal Rank (MRR). Der MRR weist jeder Frage einenWert zu, der gleich dem Kehrwert des Ranges der erstenkorrekten Antwort der N besten Kandidaten ist, vgl. auchAbschn. 4.

Im Gegensatz zur Akkuratheit betrachtet der MRRalso mehrere Antwortkandidaten des Systems, wobei be-

Abb. 1 Webbasierte Fragebeantwortung:Komponentensicht und Informationsfluss.Genaue Erlauterungen finden sich im Text

rucksichtigt wird, ob die richtige Antwort an erster, zweiteroder anderer Stelle steht. Wenn N = 1 gewahlt wird, ent-spricht das Ergebnis demnach der Akkuratheit des Systems.Der MRR ist zwar ein weicheres, allerdings aus Anwen-dungsperspektive praktikableres Maß als die Akkuratheit,z.B. in Fallen, wo ein Benutzer selbst die passende Antwortaus einer Menge von Kandidaten wahlen kann.

Wir haben dieses Maß im Bereich der datengetriebenenmaschinellen Lernverfahren eingesetzt und einen MRR von0.5167 bei dem Vergleich der von unserem webQA-Systemberechneten besten drei Antworten mit den Antworten desCLEF Korpus aus dem Jahre 2004 erzielt. Einen MRR von0.497 fur die jeweils besten funf Antworten erzielen wirmit einem genetischen Algorithmus (vgl. Abschn. 5). Wie esauch fur die crosslinguale Fragebeantwortung der Fall ist,werden dabei nur sehr wenige externe sprachspezifische undwissensbasierte Ressourcen benotigt.

Ziel dieses Artikels ist es einen Uberblick uber diesevon uns entwickelten innovativen webQA-Technologienzu geben. Ich werde zuerst die zugrundeliegende webQA-Systemarchitektur vorstellen, der sich detaillierte Beschrei-bungen der relevanten Komponenten anschließen.

3 Systemuberblick

Die Grafik in Abb. 1 gibt eine schematische Zusammen-fassung uber die Hauptkomponenten der webbasierten Fra-gebeantwortung und deren Interaktion untereinander. DieseSystemarchitektur dient als gemeinsame Grundlage fur diein den nachsten Abschnitten im Detail beschriebenen inno-vativen QA-Strategien.

Die Komponente zur Frageanalyse empfangt als Ein-gabe eine Frage in naturlicher Sprache und analysiert sie

1 3

74 Neumann

nach syntaktischen und semantischen Kriterien. Im Fall ei-ner crosslingualen QA wird zusatzlich eine maschinelleUbersetzung der Frage durchgefuhrt. Als Ergebnis liefertdie Frageanalyse ein NL-Query Datenobjekt, das u.a. denFragetyp (z.B. Faktenfrage oder Definitionsfrage), den er-warteten Antworttyp (z.B. Person oder Lokation), einesemantische Reprasentation, die Wortkette der Frage undeventuell deren Ubersetzung beinhaltet.

Die NL-Query dient gleichzeitig als Eingabe fur dieAntwortextraktion und die Komponente zur Generie-rung der spezifischen IR-Query (die dann ihrerseits alsEingabe fur die Suchmaschine dient). Wie wir im nachstenAbschn. 4 erlautern werden, besteht die IR-Query in der Re-gel gerade aus der textuellen Reprasentation der NL-Frage,wogegen fur die Antwortextraktion der gesamte Inhalt derNL-Query herangezogen wird, vgl. Abschn. 5. Die Kompo-nente zur Antwortextraktion besteht dabei in der Regel auseiner Menge von speziellen Strategien, die mit Hilfe desbestimmten Fragetyps und des Antwortyps gezielt angesteu-ert werden kann. Damit ist es moglich, in Abhangigkeit derFrage unterschiedliche Antwortstrategien auszuwahlen (vgl.auch Abschn. 6).

Das Ergebnis der Suchmaschine besteht im Wesentli-chen aus einer Menge von Suchtreffern. Jeder Treffer be-steht mindestens aus einem Verweis auf die Webseite undeinem aus ihr dynamisch erzeugten Snippet. Des wei-teren definiert die Reihenfolge der Suchtreffer eine Rang-ordnung, wobei in der Regel das wichtigste Dokument anerster Stelle steht, das unwichtigste an letzter. Welche Kri-terien zur Bestimmung der Relevanz tatsachlich eingesetztwurden, bleibt dem Benutzer bzw. Fragesteller in der Regelverborgen.

Zwar ist es so, dass die Snippets zumindest einen Teilder Schlusselworter aus der Suchanfrage enthalten und dieseentsprechend markiert hervorheben. Fur die Antwortextrak-tion ist dies von Vorteil, da es oft der Fall ist, dass einemogliche Antwort in unmittelbarer Nahe der Fragetermeauftritt. Daraus kann aber nicht unmittelbar geschlossenwerden, dass die im Kontext solcher Schlusselworter vor-kommenden Terme automatisch sinnvolle Antwortkandida-ten waren. Insbesondere kann daraus nicht abgeleitet wer-den, dass die Snippets der ranghochsten Dokumente aucham wahrscheinlichsten die richtige Antwort enthalten.

Es ist ein zentrales Ziel der aktuellen Suchmaschi-nen, den besten Dokumenten einen hohen Rang zuzuord-nen und nicht Dokumente zu praferieren, deren Snippetsmoglicherweise einen exakten Antwortstring enthalten. Da-her kann die Rangordnung, wie sie durch aktuelle Suchma-schinen vorgegeben wird, nicht unmittelbar fur die Bestim-mung der Antwortkandidaten herangezogen werden. Dennes besteht ein relevanter Unterschied darin, ob die Such-maschine aktuelle Webseiten oder Webseiten mit moglichsthoher Zugriffszahl praferiert. Dies ist z.B. fur die Beant-

wortung von Fragen nach Personen des offentlichen In-teresses kritisch. Wurde beispielsweise gerade ein neuerBundesprasident (oder Bundesligatrainer) gewahlt, so istdie Zugriffszahl auf Webseiten mit diesem Inhalt zumin-dest vorubergehend niedrig im Vergleich zu Seiten, dieauf vorherige Bundesprasidenten verweisen. Aus diesemGrunde betrachten wir in der Antwortextraktion zwar dieN-ersten Snippets, ignorieren danach aber deren Rangord-nung. Das heißt wir betrachten sie als Menge. Es ist dannein Teilziel, wahrend der Antwortextraktion eine antworts-pezifische Rangordnung von relevanten Textausschnitten zubestimmen.

Die zentrale Aufgabe der Komponente zur Analyse desAntwortkontextes ist daher die Bestimmung derjeni-gen Wortketten aus den N-besten Snippets, die entweder 1)die exakte Antwort enthalten oder 2) eine Paraphrase fureine Teilsequenz der NL-Frage reprasentieren. Im Fall 1)werden diese als AP-Phrasen bezeichneten Wortkettenentweder direkt an die Komponente zur Antwortextraktionweitergeleitet, oder es werden die mit den AP-Phrasen as-soziierten Webseiten zuerst zur Dokumentenanalyse wei-tergereicht. Dieser Fall impliziert in der Regel, dass eineNeuberechnung der ursprunglichen Rangordnung in Rich-tung der Dokumente erfolgte, die am wahrscheinlichstendie richtige Antwort enthalten werden. Der Fall 2) bedeu-tet, dass die semantische Umformulierung einer Teilketteder NL-Frage identifiziert wurde und damit eine erneuteSuche durchgefuhrt werden kann, diesmal mit der Aus-sicht, einen relevanten anderen Ausschnitt des Webs zubesuchen.

Wir werden nun auf einige der genannten Komponen-ten und Methoden genauer eingehen, wobei wir jeweils amEnde der entsprechenden Abschnitte auch auf die durch-gefuhrten Experimente und Evaluationen eingehen werden.Dies ist moglich, da die einzelnen Komponenten aus funk-tionaler Perspektive einen hohen Grad an Modularitat undEigenstandigkeit besitzen.

4 Antwortkontexte

Nach der Frageanalyse ist der nachste plausible Schrittdie Bestimmung der relevanten Menge von Webseiten, diedie Antwort zu einer Frage enthalten. Unter der allgemeinakzeptierten Annahme, dass fur webQA-Systeme Redun-danz eine sehr gute Approximation fur die Bestimmung derGlaubwurdigkeit einer Antwort ist, sollte eine moglichstgroße Menge an relevanten Dokumenten bestimmt werden,das heißt das Rauschen durch Zugriff auf irrelevante Doku-mente (also solche, die die Antwort nicht enthalten) sollteminimiert werden. Es handelt sich hierbei also um denklassischen Trade-off zwischen Vollstandigkeit (Recall) undPrazision (Precision).

1 3

Webbasierte Fragebeantwortung 75

Einstiegspunkt fur die initiale Bestimmung sind die In-haltsworter (oder Terme) der NL-Frage. Um den Trade-offzu meistern, werden in der Regel Reformulierungen derNL-Frage erzeugt, also Paraphrasen von Teilen der Frage.Bisher wird dieser Schritt jedoch vor dem eigentlichen Zu-griff auf das Web durchgefuhrt, z.B. durch Einsatz vondomanenneutralen Thesauri (z.B. [13]) oder durch Gene-rierung potentieller Antwortkontexte (z.B. [5]). Ein gravie-render Nachteil hierbei ist, dass im Prinzip nur geschatztwerden kann, ob die entsprechenden Paraphrasen den Recalltatsachlich erhohen werden.

Um diesen Nachteil zu umgehen, haben wir eine da-tengesteuerte Methode entwickelt, die relevante Antwort-kontexte unmittelbar aus den Snippets extrahiert. ZentraleEigenschaften dieser Methode sind: datengesteuert, sprach-unabhangig (keine Sprachtechnologie-Komponenten, keinoffline-bestimmtes Sprachmodell) und unuberwacht, d.h.keine externe Parameteroptimierung, keine Beschrankungauf Langen von Teilketten und auch keine Verwendung ei-ner festen Fenstergroße.

Verfahren Die zentrale Idee dieser von uns als Antwort-kontextanalyse bezeichneten Methode ist einfach. Aus-gangspunkt ist die textuelle Reprasentation einer Frage Q,z.B. der String Welche Elemente wirken bei Photosynthesemit? Die wesentlichen Schritte sind dann:2

1. Websuche: Q wird direkt als Eingabe fur die Suchma-schine verwendet und die N-besten Snippets werden be-stimmt.

2. Snippetdokument: Jeder Snippet wird in eine Mengevon Satzen uberfuhrt und alle Satze (auch Mehrfach-vorkommen) zu einem Dokument zusammengefasst. Ab-schließend wird auch Q (quasi als nullter Snippet) die-sem Dokument hinzugefugt.

3. Wortpaarstatistik: Hier wird uber alle Satze im Snip-petdokument hinaus bestimmt, wie haufig jedes Wortpaarmit welcher Distanz vorkommt. Beispielsweise bedeu-tet 〈(Radio, Tesla), 2, 3〉, dass das Wortpaar (Radio,Tesla) drei mal mit einem Abstand von zwei in demSnippetdokument auftritt (etwa in einem Satz wie ,,DasRadio wurde von Tesla erfunden.“) Wortpaare mit den-selben Wortern, aber unterschiedlicher Distanz, werdendabei als unterschiedliche Elemente betrachtet.

4. Gewichtung: Eine Rangordnung der Satze wird be-stimmt. Fur jeden Satz der Lange N wird eine N × NMatrix konstruiert und jede Zelle mit den im Schritt 3.bestimmten Werten fur die Wortpaarstatistik gefullt.Von uns durchgefuhrte empirische Tests haben ge-zeigt, dass Wortpaare mit einer bestimmten Distanz zum

2 Eine detaillierte formale Beschreibung dieser Methode, als auch eineausfuhrliche Evaluation ihrer Performanz fur verschiedene Sprachenfindet sich in [8].

uberwiegenden Teil mit einer Frequenz von ≤ 2 vorkom-men (ca. 99%). Wir schließen daraus, dass Wortpaaremit einer hoheren Frequenz seltener auftreten und damitstarker zum Inhalt eines Dokumentes beitragen als ge-ringer frequente Paare. Daher werden nur die Wortpaareberucksichtigt, deren Frequenz oberhalb eines Schwell-wertes ζ liegen. (ζ = 2 in allen unseren Tests). Damitsoll in spateren Schritten eine Tendenz zur Bevorzugunglanger Sequenzen von geringfrequenten Wortpaaren ver-mieden werden.Danach bestimmen wir den Rang eines jeden Satzesdurch Berechnung des maximalen Eigenwertes seinerMatrix, vgl. auch [3].

5. Extraktion von AP-Phrasen: AP-Phrasen sind Kettenvon Wortpaaren von hochfrequenten Elementen in derSatzmatrix. Worter, die keine hochfrequente Beziehungzu allen anderen Wortern haben, definieren Schnittstel-len in den Satzen und werden durch * substituiert. Seiz.B. der Satz ,,The president of France went on Ho-lidays yesterday“ und ergab die Wortpaarstatistik, dass,,went“ und ,,yesterday“ keine hohe Beziehungen zu an-deren Wortern in der aktuellen Menge von Snippets hat,dann folgt daraus ,,The president of France * on Holidays* ,,und als gultige AP-Phrasen ,,The president of France“und ,,on Holidays“.

6. Gewichtung der AP-Phrasen: Es wird eine Rangord-nung fur die AP-Phrasen bestimmt, wobei diese durchKombination einer standardisierten bi-gram Statistik furdie AP-Phrase und des Ranges des Satzes aus dem dieAP-Phrase extrahiert wurde, gebildet wird.

Durch die Berechnung eines individuellen Eigenwer-tes pro Satz werden solche Satze hoch bewertet, die einengroßen Anteil von Wortpaaren mit hoher lexikalischerRedundanz und syntaktischer Bindungskraft innerhalb derdurch die NL-Frage ausgewahlten Snippets haben. Rang-hohe AP-Phrasen sind dann langstmogliche Ketten vonWortern, deren einzelne Glieder eine hohe syntaktischeRegelmaßigkeit aufweisen und einen hohen Grad an ge-meinsamen Kontext besitzen.

Wie bereits oben erwahnt, entspricht eine AP-Phraseentweder einer Paraphrase eines Teilstrings der NL-Frageoder enthalt einen exakten Antwortstring. Beispielsweisesind fur die Frage ,,Who is the Prime Minister of GreatBritain? “, ,,United Kingdom“ und ,,Tony Blair“ moglicheAP-Phrasen. Im ersten Fall handelt es sich dabei um eine Pa-raphrase fur ,,Great Britain“ und im anderen Fall fur einenAntwortstring. Die Bestimmung der AP-Phrasen ist spra-chunabhangig, da weder spezifische NL-Verarbeitungskom-ponenten noch Sprachmodelle eingesetzt werden. Die Be-stimmung ist ebenfalls vollkommen datengesteuert undunuberwacht.

1 3

76 Neumann

Damit stellt sich die Frage nach der Plausibilitat undGute der AP-Phrasen. Eine Moglichkeit ware es, den Be-nutzer die relevanten AP-Phrasen manuell aus den durch dieNL-Frage bestimmten Snippets extrahieren zu lassen unddiesen Benutzer-unterstutzten Auswahlprozess mit unseremvorgeschlagenen datengesteuerten Prozess zu vergleichen.Eine andere Moglichkeit bestunde darin, automatisch ausden AP-Phrasen exakte Antworten zu extrahieren und diesemit den Antworten aus TREC/CLEF Korpora zu verglei-chen. Die Gute der Antworten ergabe dann eine realistischeKenngroße fur die Gute der AP-Phrasen.

Evaluation Wir haben uns bei der Evaluation unseres Ver-fahrens fur den zweiten Ansatz entschieden, da zum einenein Vergleich mit standardisierten Korpora ermoglicht wird.Zum anderen wollten wir ein Maß dafur erhalten, wie oftdie AP-Phrasen fur bestimmte Fragetypen exakte Antwortenenthalten.

Zur Realisierung dieses Ansatzes wird eine Komponentezur Extraktion von exakten Antworten aus den AP-Phrasenbenotigt. Zusammen mit dieser Komponente realisiert derInformationsfluss ein vollstandiges QA-System, dass wirauch als WQA bezeichnen.

Um unsere angestrebte Sprachunabhangigkeit und dieaktuelle Effizienz des gesamten Informationsflusses nichtnegativ zu beeinflussen, werden fur die Antwortextraktionsehr einfache Methoden auf Basis von sehr kleinen sprach-spezifischen Wortlisten verwendet (zur rudimentaren Abbil-dung von Fragewortern (z.B. ,,Wo“) auf entsprechende Ant-worttypen (z.B. Ort)) und eine kleine Menge von einfachen,sprachunabhangigen Regularen Ausdrucken. Diese dienendazu, Teilausdrucke aus den AP-Phrasen in Abhangigkeitdes Antworttyps der Frage zu filtern. Beispielsweise wer-den alle Worter, die auch in der NL-Frage vorkommen oderalle Worter der geschlossenen Wortarten ignoriert. Bei per-sonenbezogenen Fragen werden alle Worter in einer AP-Phrase entfernt, die nicht-alphabetische Zeichen enthalten.

Ausgangspunkt fur unsere Experimente war der multilin-guale Korpus der CLEF-2004 Evaluation (cf. [12]). Darauswurden insgesamt 889 Fragen (228 Wann-Fragen, 232 Wo-Fragen und 439 Wer-Fragen) aus vier Sprachen (Englisch,Deutsch, Portugiesisch, Spanisch) fur unsere Tests aus-gewahlt. Fur jede Frage wurde von unserem webQA-Systemdie N = 3 besten exakten Antwortstrings aus M = 30 er-sten von der Suchmaschine gelieferten Snippets berech-net und mit dem entsprechenden Frage/Antwortpaar imCLEF Korpus verglichen. Das Gesamtergebnis fur alleSprachen findet sich in Tabelle 1. MRR steht fur den inAbschn. 2 bereits eingefuhrten Mean Reciprocal Rank.Die Tabelle zeigt auch die Resultate fur korrekt erkannteAntworten auf dem ersten, zweiten, dritten und nulltenPlatz (= NAF, was zu lesen ist als ,,keine Antwort gefun-den, obwohl eine Antwort in den Snippets vorkommt“).

Tabelle 1 Die Resultate jeden Fragetypen QT (alle Sprachen)

QT Total MRR NAG(%) WAG(%)

when 218 0.60 25.11 10.96. . . NAF(%) 1(%) 2(%) 3(%)

21.46 35.16 5.02 1.8where 232 0.57 10.77 24.14. . . NAF(%) 1(%) 2(%) 3(%)

20.68 30.60 9.91 3.87who 439 0.38 11.39 27.56. . . NAF(%) 1(%) 2(%) 3(%)

32.57 18.90 6.83 2.73

Tabelle 2 Die Verteilung der Antwortkandidaten (alle Sprachen)

CA NAF(%) 1(%) 2(%) 3(%)

when 33.82 55.42 7.91 2.84where 31.86 47.00 15.23 5.95who 53.37 30.97 11.19 4.47

Des Weiteren bedeutet NAG, dass sich keine Antwort inden Snippets befindet und das System dies als NIL an-zeigt. WAG bedeutet, dass die Snippets keine Antwortenthalten, das System aber drei falsche Antwortkandida-ten liefert. Tabelle 2 zeigt zusatzlich die Verteilung derextrahierten Antworten fur die Falle, in denen die Snip-pets tatsachlich die Antworten enthalten. Die durchschnitt-liche Verarbeitungszeit pro Frage/Antwortpaar betragt jenach der Belastung des Servers ca. zwischen 10 und15 s.3

5 Datengesteuerte Antwortextraktion

Die manuell implementierten einfachen Heuristiken zurAntwortextraktion im WQA-System haben den zentralenNachteil, dass sie vorgefertigten Mustern von moglichenAntwortkandidaten entsprechen und auf Grund ihrer Sta-tik sehr inflexibel und fehleranfallig sind, sowie in derRegel einen geringen Recall aufweisen. Um auch fur denFall der Antwortextraktion in hohem Maße datengesteu-ert operieren zu konnen, stellen wir nun ein maschinellesLernverfahren fur die Antwortextraktion vor. Ausgangs-punkt ist ein Speicher aus bereits erfolgreich bestimmtenAntworten und ihren textuellen Kontexten, den wir auchals QA-Store bezeichnen. Unter Bezugnahme auf diesenSpeicher haben wir einen speziellen genetischen Algorith-mus implementiert und evaluiert, der selbststandig in derLage ist, in den Satzen von Snippets Teilstrings als exakteAntworten eines bestimmten Typs zu identifizieren und zuextrahieren.

3 Die Zeiten wurden auf einem leistungsstarken Linux-Rechnerermittelt.

1 3

Webbasierte Fragebeantwortung 77

Motivation Ausgangspunkt ist hierbei die Idee, die Antwort-extraktion als eine spezielle Suchaufgabe aufzufassen,4 wo-bei die Menge aller eindeutigen Teilstrings (zusammen mitder Frequenz), die sich prinzipiell aus den N-besten Snip-pets konstruieren lasst, den potentiellen Suchraum definiert.Ziel ist es nun, die Teilstrings zu bestimmen, deren Kontext(linker und rechter Teilstring in einem Satz) den bereits inder Vergangenheit erfolgreich berechneten Antwortstringsam ahnlichsten ist und deren Kontextelemente eine maxi-male Uberlappung mit Termen aus der aktuellen NL-Fragehaben.

Eine naive Suchstrategie konnte nun sein, in einem ers-ten Schritt alle moglichen Teilstrings zu berechnen, sie derReihe nach zu untersuchen und abschließend die N-bestenTeilstrings zu liefern. Allerdings ist die Strategie auf Grundder Große des Suchraums nicht gangbar. Eine Moglichkeit,die Performanz zu verbessern, ist es, den Suchraum vonvornherein zu beschranken, indem man die Menge der Teil-strings beschrankt. Die oben erwahnten bisher implemen-tierten einfachen Heuristiken haben genau diese Aufgabe.Diese, mittels regularer Ausdrucke, formulierten Heuristi-ken definieren quasi einen off–line Filter fur die Menge derpotentiellen Teilstrings.

Eine andere mogliche Suchstrategie konnte sein, zuerstrein zufallig eine kleine Menge von Teilstrings auszuwahlen(quasi als Startpunkt der Suche), diese entsprechend mitKontextinformation zu bewerten und die besten Teilstringszu benutzen, um eine neue Teilmenge zu bestimmen (quasidie Nachfolgezustande). Dieser Prozess iteriert solange, biskeine neuen, besseren Teilstrings gefunden werden konnenoder der Prozess von außen abgebrochen wird, z.B. indemvorgegeben wird, wie oft der Prozess wiederholt werdendarf.

Diese Art der Suchstrategie wird auch als ,,Lokaler-Strahl-Suchalgorithmus“ bezeichnet (cf. [19], Abschnitt4.3.3, Seite 156). Ein genetischer Algorithmus (oder GA)ist eine Variante einer solchen lokalen Suchstrategie, beider Nachfolgezustande (in unserem Fall neue Teilstrings)erzeugt werden, indem zwei ubergeordnete Zustande kom-biniert werden (cf. [19], Abschnitt 4.3.4). Diesen Prozessnennt man auch Crossover. Auf unser Problem ubertragenbedeutet dies, die Informationen von Teilstrings werdenkombiniert, um damit neue Teilstrings zu bestimmen. Wei-ter unten wird man sehen, dass wir hierzu z.B. die Positions-information der zwei Teilstrings benutzen, um einen neuenTeilstring zu erhalten, der z.B. um eine Position kurzer oderlanger ist.

Wichtig fur das Konvergieren eines GA ist es, dassstets die aktuell besten Kandidaten betrachtet werden. Da-her wird zur Bewertung eines Teilstrings eine sogenannte

4 Ein sehr guter Uberblick uber Suchstrategien, wie sie in derKunstlichen Intelligenz entwickelt wurden, findet sich in [19].

Fitness-Funktion benotigt. Die Fitness-Funktion, die wirvorschlagen, basiert im Wesentlichen auf dem gleichen,oben eingefuhrten Vergleich der Kontextelemente einesaktuellen Teilstrings mit solchen Teilstrings, die dem Sys-tem schon als richtige Antworten bekannt sind und diein einem als QA-Store bezeichneten Datenspeicher ge-halten werden. Da ein GA eine lokale Suche in Richtungder besten Losungen anstrebt, ist bekannt, dass die besteLosung moglicherweise ebenfalls nur lokal optimal seinkann. Um dieses Problem zu behandeln, verfugen GA ubereine als Mutation bekannte Operation, die zufallig zu ei-ner Veranderung eines Zustandes fuhrt. Annahme ist hier,dass solche Operationen helfen, eine zu fruhe Optimierungin Richtung bestimmter lokaler Zustande zu verhindern.

Wir werden im Folgenden den QA-spezifischen geneti-schen Algorithmus genauer vorstellen, konnen aber im Rah-men dieses Uberblicksartikels nur informell und kurz aufdie einzelnen Schritte eingehen (cf. aber [7]).

Datengesteuerte Antwortextraktion Der QA-Store bestehtaus einer Menge von Tupeln der Form 〈 AType, Ans, SAns〉,wobei AType der Antworttyp ist (z.B. Person), Ans der ex-akte Antwortstring (z.B. ,,Tony Blair“) und SAns der mit Ansannotierte Satz, z.B. ,,Der Regierungschef Englands heißtTony Blair“.

Die aktuellen Elemente im QA-Store werden durch dasWQA-System bestimmt und sind manuell auf Korrektheituberpruft. Dies bedeutet insbesondere, dass die Satzkon-texte eine durch die Antwortkontextanalyse bestimmteUberlappung mit den Termen aus der NL-Frage haben.Die NL-Frage ist damit implizit auch in einem QA-Store-Element enthalten.

Der genetische Algorithmus zur Antwortextraktion AEGA

ist nun in der Lage, fur einen zufallig bestimmten TeilstringA eines Satzes S durch Vergleich des linken und rechtenKontextes von A in S mit relevanten Elementen aus demQA-Store zu berechnen, wie gut A eine mogliche Antwortfur die NL-Frage Q darstellt. Dabei werden die gleichenMethoden zur Bestimmung der Wortpaarstatistik herange-zogen, wie im Verfahren zur Antwortkontextanalyseim WQA-System. Zur Erzeugung neuer Antwortkandidatenhaben wir problemspezifische Operatoren fur das Crossoverund die Mutation implementiert, die solange angewendetwerden, bis eine vorgegebene Anzahl von Iterationen durch-laufen ist. Die am hochsten bewerteten Antwortkandidatenwerden dann als exakte Antworten von Q geliefert.

Die Struktur des auf dem genetischen Algorithmus ba-sierenden Fragebeantwortungssystems (das wir auch alsGAQA-System bezeichnen) unterteilt sich dabei in zweiPhasen: a) Vorverarbeitung und b) genetischer Algorithmus.

Vorverarbeitung In der Vorverarbeitungsphase wird dieNL-Frage Q benutzt, um die N-ersten Snippets im Web

1 3

78 Neumann

zu bestimmen und den Antworttyp ATypeQ der Frage zubestimmen. Die Snippets werden dem Verfahren in WQAfolgend in ein Snippetdokument D uberfuhrt, also in eineMenge von Satzen. ATypeQ wird ebenfalls analog zu WQAsehr einfach uber die Analyse der Frageworter bestimmt.Mittels ATypeQ werden nun alle Elemente mit gleichemAntworttyp aus QA-Store extrahiert. Danach wird in je-dem Satz eines Tupels der exakte Antwortstring durch einDummywort ersetzt. Auf diese Weise wird von der kon-kreten Antwort abstrahiert und nur noch deren linker undrechter Kontext im weiteren Verlauf der Verarbeitung be-trachtet. Um sicherzustellen, dass nur solche Satze aus demQA-Store betrachtet werden, die einen lexikalischen Be-zug zu Elementen in D haben, werden diejenigen Satzeentfernt, deren Terme hochstens einmal in D vorkommenoder deren Terme nur aus Stoppwortern bestehen.5 Da vonden eigentlichen Antworten abstrahiert wird, reprasentiertdie Menge dieser so veranderten Satze die dynamisch be-obachteten Kontexte fur einen Antworttyp. Daher wird ana-log dem Verfahren zur Bestimmung der Wortpaarstatistikaus Abschn. 4 fur diese Kontexte durch Berechnung derrelativen Haufigkeit, die Wahrscheinlichkeit Pl(wi, ε) furalle Worter wi , die links von w0 mit Abstand ε auftre-ten, naherungsweise bestimmt und analog Pr(wi, ε) fur alleWorter rechts von w0.

Fitness-Funktion Damit reprasentieren Pl und Pr das syn-taktische Verhalten von Wortern im linken und rechten Kon-text von bekannten Antworten relativ zur aktuellen NL-Frage Q und aktuellem Snippetdokument D. Sie sind damitgeeigneter Ausgangspunkt zur Spezifikation der Fitness-Funktion F von AEGA. F bewertet einen Teilstring AnsS ei-nes Satzes S derart, dass alle Worter links (rechts) von AnsS

mittels Pl (Pr ) gewichtet und deren Werte summiert wer-den (0 fur Worter die nicht in den Matrizen vorkommen).Dabei erhalten die Worter, die mit Termen in der Frage Qubereinstimmen, einen Bonus. F bewertet Antwortkandida-ten in Satzen demnach relativ zur lexikalischen und syn-taktischen Ahnlichkeit mit relevanten Elementen aus demQA-Store und zur NL-Frage. Die Gesamtbewertung einesAnwortkandidaten Ans ergibt sich dann aus der Summe derEinzelbewertungen aller Vorkommen von Ans in D.

Lernalgorithmus Die zentrale Idee im genetischen Algo-rithmus AEGA ist es, beginnend mit einem Teilstring AnsS,der zufallig in einem Satz S aus D identifiziert wurde, durchAnwendung der GA-Operatoren zu einem Teilstring Ansmit bester durch F bestimmter Bewertung zu konvergieren.Dazu wird ein Chromosom als ein Tupel 〈s, k1, k2〉 definiert,

5 Ein Stoppwort ist ein sehr haufig auftretenes Wort, das gewohnlichkeine (statistische) Relevanz in einem Dokument hat. In der Regelgehoren Worter der geschlossenen Wortarten (z.B. Prapositionen, Ar-tikel) zu den Stoppwortern. Oft werden auch spezielle Listen vonStoppwortern verwaltet, z.B. in bestimmten Domanen.

wobei s der Index eines Satzes Ss aus D ist und k1 und k2 diePositionen von AnsS in S reprasentieren. Instanzen von Tu-peln nennen wir Individuen. Damit kann AEGA spezifiziertwerden:

1. Initiale Population: Es werden I (= 20) initiale Indi-viduen kreiert. Dabei wird fur jeden Kandidaten zu-erst zufallig ein Satz Ss aus D gewahlt. In Ss wird einTeilstring AnsS als Antwortkandidat ausgewahlt, in demzufallig dessen Start- und Endpunkt in Ss bestimmt wer-den. Falls AnsS Terme aus der NL-Frage Q enthalt odernur aus Stoppwortern besteht, wird ein neuer Teilstringals Antwortkandidat bestimmt.

2. Evaluation der Kandidaten: Mittels der Fitness-Funk-tion F (siehe oben) werden die Individuen bewertet.

3. Crossover: Aus zwei zufallig bestimmten Individuen derForm I1 = 〈s1, k11, k21〉 und I2 = 〈s2, k12, k22〉 werdenzwei neue Individuen I3 und I4 erzeugt, indem I1 und I2

die Start- und Endpunkte ihrer Antwortkandidaten aus-tauschen. Konkret:I3 = 〈s1, min(k11, k21), min(max(k12, k22), len(Ss1))〉I4 = 〈s2, x := max(k11, k21), min(max (k12, k22), x)〉.Dies hat zur Folge, dass I3 zu einer Streckung eines Ant-wortkandidaten fuhrt und I4 zu einer Verkurzung.

4. Mutation: Zweck dieser Operation ist es, zufallig Werteder Attribute (oder Gene) eines Individuums zu andern.Zuerst wird zufallig das Attribut bestimmt, dessen Wertverandert werden soll. Falls s gewahlt wird, so wirdzufallig ein neuer Index (im Bereich des durch D ge-gebenen Intervalls) bestimmt, wobei die Positionen desAntwortstrings beibehalten werden, ansonsten werdensie leicht angepasst (cf. [7]). Falls k1 (k2) gewahlt wird,so wird der Start (das Ende) um ein Wort nach linksoder rechts verschoben, was ebenfalls zufallig bestimmtwird. Mutationen fuhren also dazu, dass neue Satze mitneuen Antwortkandidaten gleicher Lange betrachtet wer-den konnen oder dass sich das Prafix (Suffix) des Ant-wortkandidaten um ein Wort verlangert oder verkurzt.

5. Evaluation der Kandidaten: siehe Schritt 2.6. Nachste Population: Individuen fur die nachste Popu-

lation werden nach dem Prinzip der proportional selec-tion [9] bestimmt. Im Prinzip bedeutet dies, dass die bes-ten Individuen aus der aktuellen und der vorherigen Po-pulation, sowie die durch die Operationen neu gewonnenIndividuen eine hohere Uberlebenswahrscheinlichkeit inder nachsten Population haben werden.

7. Goto 3. falls maximale Anzahl von Iterationen T (= 25)

noch nicht erreicht.

Beispiel Das folgende Beispiel soll die Funktionsweise vonAEGA verdeutlichen. Wir nehmen an, dass das Snippetdo-kument aus m Satzen der Form wi,1wi,2 . . . w1,n−1 wi,n , mit0 ≤ i ≤ m besteht. Die Snippets sind mit Hilfe der NL-Frage

1 3

Webbasierte Fragebeantwortung 79

bestimmt worden. Demnach ist der aktuelle Antworttypebenfalls bekannt, z.B. Person. Des Weiteren nehmen wiran, dass der QA-Store aus folgenden drei Elementen be-steht (jedes Element speichert den Antworttyp, die Antwortund den Satz, in dem die Antwort gefunden wurde; wi seidas i-te Wort in einem Satz):

{〈Person, w3w4, w1w2w3w4w5w6〉,〈Person, w1, w1w2w3w4〉,〈Location, w3, w1w2w3w4〉}Aus dem Snippetdokument wahlt AEGA zufallig einen

Satz aus, z.B. w3,1w3,2w3,3w3,4w3,5w3,6 und von diesemzufallig den Teilstring w3,4w3,5 als Antwortkandidat. Derlinke Kontext ergibt sich damit als w3,1w3,2w3,3 und derrechte Kontext als w3,6. Da der aktuelle Antworttyp Per-son lautet, werden die ersten zwei Elemente des QA-Storeausgewahlt. Zur Bestimmung der Fitness des aktuellen Ant-wortkandidaten werden die jeweiligen Kontexte der aus demQA-Store gewahlten Elemente mit den Kontexten des ak-tuellen Antwortkandidaten verglichen.

Danach wird zufallig ein Element aus dem QA-Storeherangezogen, um neue Antwortkandidaten zu bestimmen.Nehmen wir an, dass dies fur das erste Element aus demQA-Store gilt, also 〈Person, w3w4, w1w2w3w4w5w6〉. DieAnwendung der Crossover-Operation liefert daher zweineue Antwortkandidaten:

w3w4w5 fur w1w2w3w4w5w6 undw3,4 fur w3,1w3,2w3,3w3,4w3,5w3,6

Die Mutationsoperation zufallig angewendet auf dasneue zweite Element verandert dieses z.B. wie folgt:

w3,3w3,4 fur w3,1w3,2w3,3w3,4w3,5w3,6

Alle Elemente werden mittels der Fitness-Funktion be-wertet und die nachste Population berechnet.

AEGA realisiert demnach eine Suche nach Teilstringsin einem Snippetdokument, die exakten Antworten ent-sprechen, wobei der Suchraum implizit durch die Mengealler moglichen Teilstrings im Snippetdokument definiertist. Dieser Suchraum ist zwar endlich, aber im Allgemei-nen sehr groß. AEGA konvergiert jedoch rasch zu Teil-strings als Antworten, die eine hohe Redundanz besitzenund in Kontexten vorkommen, die eine hohe syntagmatischeAhnlichkeit mit Kontexten von bereits als erfolgreich beant-wortete Fragen gleichen ATypes aufweisen.

Der Vorteil von evolutionaren Strategien hierbei istder, dass wir keine vorprogrammierten Annahmen ubermogliche Strukturen der Antwortstrings insbesondere ih-rer syntagmatischen Beziehungen machen mussen, sondernAEGA dies selbststandig mit Hilfe der implizit vorliegen-den syntaktischen Strukturierung (via der Wortpaarstatistik)in den QA-Store-Elementen leistet. Damit erreichen wirein hoheres Maß an Sprachunabhangigkeit als dies mit den

Tabelle 3 Resultate per Strategie (611 = 713-89-13 Fragen mitBLQA und 610 = 713-89-14 Fragen mit GAQA) . . .

MRR Total 1 2 3 4 5BLQA 0.373 400 137 92 78 42 41GAQA 0.497 401 242 78 38 31 12

. . . und bzgl. der einzelnen QA–Korpora:

Korpus Fragen NAS BLQA GAQAClef-2004 75 24 0.309 0.387Erfindungen 185 28 0.421 0.502Prasidenten 89 1 0.524 0.571Minister 76 5 0.473 0.706Symphonien 100 23 0.315 0.500Orte 43 1 0.568 0.638Datum 145 7 0.173 0.365

Methoden zur Antwortextraktion aus Abschn. 4 der Fallist.

Evaluation Dem Vorschlag von [11] folgend, betrachtenwir Fragen als eine Sammlung von Entitaten und Rela-tionen zwischen ihnen. Die fehlende Information (alsodie erforderte Antwort) entspricht demnach einer unbe-kannten Relation oder Entitat. Fur die Evaluation vonGAQA betrachteten wir Entitaten-bezogene Antworten vonWer-, Wann- und Wo-Fragen. Dabei unterscheiden wirRelationen-offene Fragen (also Fragen, die sich auf belie-bige Relationen beziehen, insbesondere die der CLEF-2004Fragen) und Relationen-geschlossene Fragen, also Fragender Art ,,Wer entdeckte X? “ oder ,,Wann wurde Y gebo-ren? “. Die entsprechenden QA-Korpora wurden aus allge-mein zuganglichen Enzyklopadien generiert, u.a. BritannicaEncylopedia (cf. [7]).

Um einen Vergleich der Ergebnisse des GAQA ziehenzu konnen, verwenden wir als Referenz ein QA-System(als BLQA bezeichnet), das zur Antwortextraktion nur ein-zelne Worter betrachtet, die aus den Snippets extrahiertund mittels des aus dem Information Retrieval her bekann-ten Maßes tfidf (term frequency and inverse document fre-quency) geordnet wurden. tfidf berechnet fur jedes Wort indem Snippetdokument dessen Frequenz und Verteilung uberden Snippets und zieht damit ebenfalls Redundanz als we-sentliches Kriterium zur Bewertung von Antwortkandidatenheran.

Die obere Teiltabelle in Tabelle 3 zeigt fur BLQA undGAQA die erzielten MRR-Werte fur N = 5. Die Teiltabelledarunter zeigt die Ergebnisse pro Korpus, wobei die erstenfunf Korpora 525 Wer-Fragen umfaßt, die anderen Korpora43 Wo-Fragen bzw. 145 Wann-Fragen. Insgesamt wurden713 Fragen analysiert.

Eine manuelle Analyse der Ergebnisse zeigte, dass in13 Fallen bei BLQA und 14 Fallen bei GAQA zwar kor-rekte Antworten gefunden wurden, diese aber vom Test-

1 3

80 Neumann

korpus nicht abgedeckt waren.6 Diese Fragen wurden beider Berechnung des MRR ignoriert. Desweiteren wurdenfur insgesamt 89 Fragen keine Antworten in den ersten30 Snippets gefunden, die von den Suchmaschinen in-itial bestimmt wurden (dies wird in der unteren Tabelleals NAS bezeichnet). Auch diese Fragen wurden bei derBerechnung des MRR ignoriert, da wir im Wesentlichenan der Evaluation unserer Methode zur Antwortextraktioninteressiert sind und nicht an einer Evaluation der Per-formanz der zugrundeliegenden Suchmaschine. Die erziel-ten Resultate zeigen, dass GAQA das Baseline-VerfahrenBLQA deutlich uberbietet, wobei die korpusspezifischeAnalyse es plausibel erscheinen laßt, dass GAQA mit re-lationenspezifischen Fragen besser funktioniert, als mit re-lationenunspezifischen. Dies liegt zum einen daran, dassin solchen Fallen die einfache Frageanalyse sehr akkuratdurchgefuhrt werden kann und zum anderen daran, dasseine großere Vielfalt an Kontexten pro Relation akquiriertwird.

6 Frageanalyse

Die bisherige Analyse von Fragen ist absichtlich sehr ein-fach gehalten, da wir nur eine beschrankte Art von Fra-gen betrachtet haben (Wer/Wann/Wo-Fragen und relatio-nenspezifische Fragen), fur die wir im Wesentlichen nurden Antworttypen mittels einfacher Schlusselwortsuchebestimmten (z.B. Wer am Anfang einer Frage bestimmtden Antworttyp Person). Der hauptsachliche Vorteil die-ser sehr einfachen Frageanalyse liegt darin, dass sie furviele Sprachen einfach zu implementieren ist und trotzdemfur die genannten Fragen eine ansprechende Performanzliefert.

Zur Analyse einer großeren Vielfalt von Fragetypen (z.B.Was/Wie/Wozu/Wodurch-Fragen mit teilweise beliebigenAntworttypen) und fur die crosslinguale Fragebeantwor-tung (vgl. Abschn. 7) wird eine detailliertere Frageanalysebenotigt. Wir haben hierfur eine zweistufige Strategie ent-wickelt, die wir nun kurz prasentieren wollen (Details findensich in [15]). In der ersten Phase dieser Frageanalyse wirdeine vollstandige syntaktische Dependenzanalyse der Fragedurchgefuhrt, wobei wir auf dem IE-Kernsystem SMESaufbauen, cf. [14]. In der zweiten Stufe schließt sich einesemantische Analyse an. Die Dependenzanalyse bestimmtfur jedes Wort wi einer Frage, von welchem anderen Wortwj es regiert wird. Man sagt: wi ist der Dependent vonwj . Das Wurzelelement eines Dependenzbaumes wird inder Regel vom finiten Verb des Satzes gebildet und hatselbst keinen Regenten. Im System SMES wahlen wir eine

6 . . . weil z.B. die Clef-2004 Frage sich auf den Namen einesPrasidenten aus dem Jahre 1994 bezog.

Reprasentation, in der die Knoten eines Dependenzbaumes(also die Worter) und deren Verbindungen explizit darge-stellt sind. Beispielsweise ist die Dependenzstruktur fur dieFrage Wo lebte Marlene Dietrich?:

〈{x1(lebt,y1),x2(wo,y2),x3(,Marlene Dietrich‘, y3)},{e1(x1,x2,y4),e2(x1,x3,y5)} 〉,

wobei xi Knoten bezeichnen, ei gerichtete Kanten (vonden Regenten zu den Dependenten) und yi zusatzlichesyntaktische und semantische Constraints beinhalten, wiez.B. Kongruenz oder Antworttyp. Diese Darstellung hatden Vorteil, dass wir auf ganz einfache Weise flache undtiefe Baumstrukturen uniform darstellen und bearbeitenkonnen.

Die semantische Frageanalyse bestimmt die zentralenWerte fur den Antworttyp (a-type), den Fragetyp (q-type) und den Fragefokus (q-focus), wobei dies zumeinen durch Traversierung relevanter Ausschnitte der De-pendenzstruktur geleistet wird und zum anderen durchZugriff auf linguistische Ontologien. Diese Wissensquel-len reprasentieren im Wesentlichen eine Abbildung lin-guistischer Entitaten auf bestimmte Fragetypen, wie z. B.Trigger-Phrasen name_von, typ_von, abkurzung_vonoder sie definieren eine Abbildung von lexikalischen Ele-menten auf bestimmte Antworttypen, z.B. wird das Wort,,Stadt“ direkt auf LOCATION abgebildet. Dies erlaubtes dann fur die Frage ,,In welcher Stadt wurde ThomasMann geboren? “ LOCATION als Antworttyp zu bestim-men. Dieser lexikalische Zugriff wird durch eine Soft-Retrieval Methode realisiert, die unter anderem auch dasErgebnis der Zerlegung von komplexen Wortern expli-zit in Betracht zieht. So werden z.B. die Worter ,,Stadt“,,,Kleinstadt“ und ,,Großstadt“ alle auf den a-type LOCA-TION abgebildet. In der Regel reicht ein einfacher lexika-lischer Look-up nicht aus. Zum Beispiel sind Wer-Fragenoft ambig bzgl. der Antworttypen LOCATION und OR-GANISATION. Daher wird ein analoger lexikalischer Zu-griff auch fur das relevante Verb im Satz durchgefuhrt undalle so bestimmten Antworttypen auf Typenkonsistenz hinuberpruft (dabei wird die Zuordnung von Verb und rele-vanten Argumenten durch die erkannte Dependenzstrukturunterstutzt).

Mit Hilfe dieser Informationen konnen wir recht einfachfragetypspezifische Antwortstrategien auswahlen bzw. dieFormulierung von spezifischen Anfragen an eine Suchma-schine formulieren. Diese Methode wurde unter anderemauch in Smartweb verwendet (cf. [1]). Beispielsweise hatder Fragetyp fur die Außerung Zeige mir ein Bild, wo ChiracBlatter ehrt! den Wert C-Image. Damit kann dann expliziteine Suche nach Bildern im Web angestoßen werden, in-dem z.B. die entsprechenden Parameter fur die Suche mitGoogle gesetzt werden (u.a., dass der Dateityp GIF seinsollte).

1 3

Webbasierte Fragebeantwortung 81

Das Laufzeitverhalten der Frageanalyse ist sehr gut, daSMES im Wesentlichen auf der Verarbeitung mit kaskadier-ten kompilierten endlichen Automaten basiert (cf. [14]).7

7 Crosslinguale Fragebeantwortung

Bisher wurde angenommen, dass Fragen und Antwortender jeweils gleichen Sprache angehoren. In diesem Ab-schnitt wollen wir daher kurz auf unsere innovativen Arbei-ten im Bereich der sprachubergreifenden (crosslingualen)Fragebeantwortung eingehen. Die von uns entwickeltenStrategien verwenden hierbei uber das Internet verfugbaremaschinelle Ubersetzungs (MU)-Dienste (z.B. Altavista,FreeTranslation), um die Sprachbarrieren zu uberwinden.Dies erfolgt in verschiedenen Verarbeitungsstufen: bevordie Komponente zur Frageanalyse angesteuert wird undnachdem die Frageanalyse angesteuert wurde. Diese Stra-tegien sind im Rahmen unserer aktiven CLEF-Teilnahmenausfuhrlich evaluiert worden, worauf am Ende dieses Ab-schnittes eingegangen wird.

Bevor-Methode In der bevor-Methode wird eine NL-FrageQx einer NL-Sprache x zuerst mit N (= 3 in unseren Ex-perimenten) verschiedenen online MU-Diensten ubersetzt,was eine Menge von Ubersetzungen Qy = {Qyi | 1 ≤i ≤ N} in einer Sprache y liefert, die wir im weiterenVerlauf auch als Paraphrasen von Qx auffassen. In einemnachsten Schritt wird dann jedes Element aus Qy mit derentsprechenden Komponente zur Frageanalyse der Zielspra-che y analysiert, was eine entsprechende Menge QOy ={QOyi | 1 ≤ i ≤ N} von NL-Query Datenobjekten generiert.Dabei wird jedes NL-Query Objekt in QOy gemaß lin-guistischer Wohlgeformtheit und Vollstandigkeit bezuglichder relevanten Frageinformation (Fragetyp, Anworttyp, Fra-gefokus) gewichtet und nur das am hochsten bewerteteFrageobjekt wird dann zur weiteren Verarbeitung (Doku-mentensuche, Antwortextraktion) herangezogen. Die Stra-tegie ist motiviert aus der Annahme, dass eine ubersetzteFrage eine großere Glaubwurdigkeit oder Nutzlichkeit hatals eine andere, wenn ihre linguistische Analyse zu einergroßeren Wohlgeformtheit und semantischen Spezifikationfuhrt.8

In unserem CLEF-System haben wir diese Strategie furdas Sprachpaar x = Englisch und y = Deutsch realisiert. DieBestimmung der linguistischen Wohlgeformtheit wird da-bei direkt von SMES realisiert: SMES verfugt uber meh-rere Module zur Analyse der Dependenzstruktur (u.a. mor-

7 Es wurden hierbei Laufzeittests auf Standard PCs mit 2 GB RAMund mehreren tausend Fragen und Satzen durchgefuhrt. Die Laufzeitbetragt auch bei langen Satzen ca. 0,5 s.8 Eine vergleichbare Argumentation liegt auch der Multi-Engine Stra-tegie im System Verbmobil zugrunde, cf. [21].

phologische Analyse, topologische Satzstruktur, Gramma-tiken fur Phrasen, Kongruenzuberprufung, cf. [14]), diejeweils durch entsprechende Symbole mitteilen, ob ihreAnalysen erfolgreich waren oder nicht. Zum Beispiel istes moglich, dass die morphologische Analyse eines Wor-tes daran scheitert, dass es im Lexikon nicht bekannt ist.Fur diesen Fall verfugt z.B. die Grammatik zur Erken-nung von Nominalphrasen uber robuste Regeln, die z.B.uberprufen, ob das unbekannte Wort in der Position ei-nes Nomens vorkommt. Ist dieses der Fall (und das Worterfullt weitere Bedingungen) dann wird zwar eine Analysefur die Nominalphrase geliefert, aber mit einer Gewich-tung, die ausdruckt, dass nicht alle Elemente erkannt wer-den konnten und die Analyse der gesamten Außerung da-mit unterspezifiziert ist. Fur den Fall, dass z.B. das finiteVerb eines Satzes lexikalisch unbekannt ist (oder eventuellgar nicht formuliert wurde), kann zwar keine vollstandigeSatzstruktur bestimmt werden, aber zumindest die Struk-tur der einzelnen Satzteile. Ahnliche Aussagen konnen auchuber die relevanten Ausdrucke der Frageinformation (alsoFragetyp, Antworttyp, etc.) gemacht werden. Zum Bei-spiel ist es moglich, dass auf Grund einer fehlerhaftenUbersetzung der Antworttyp nicht genau bestimmt werdenkann, was dann ebenfalls zu einer Unterspezifikation imNL-Query Datenobjekt fuhrt. Mit Hilfe eines (z.Zt. nochmanuell erstellten) Entscheidungsbaumes kann dann die-jenige Ubersetzung mit geringster Fehlerquote in der Fra-geanalyse bestimmt werden.

Nachdem-Methode Die nachdem-Methode fuhrt dagegenzuerst eine Frageanalyse von Qx durch. Danach wird dasdurch die Analyse einer Frage resultierende Frageobjektubersetzt unter Verwendung einer Ubersetzung der Frage,eines Sprachmodells und einer wortbasierten Zuordnung dersemantischen Frageinformation von Quellfrage und Ziel-frage, also einer Abbildung von Fragetyp, Fragefokus undAntworttyp. Hierbei sind keine zielsprachenspezifischenKomponenten zur Frageanalyse notig. Mit anderen Wortenwird der ubersetzten Frage Qy die strukturelle Informationder Frage Qx ,,draufgesattelt“.

Diese Strategie verwenden wir in unserem CLEF-Systemfur das Sprachpaar Deutsch-Englisch. Im Wesentlichen wer-den zwei Verarbeitungsschritte durchgefuhrt, die mittels derBeispielfrage In welchem Jahrzehnt investierten japanischeAutohersteller sehr stark? im Folgenden genauer verdeut-licht werden:

1. Die, von online MT-Diensten berechneten Ubersetzun-gen werden mittels eines Sprachmodells bewertet:

In which decade did Japanese automakers investvery strongly? (0.7)In which decade did Japanese car manufacturers in-vest very strongly? (0.8)

1 3

82 Neumann

2. Die Ubersetzungen, die eine akzeptable Bewertung er-halten haben, werden nun mit der deutschen Frage aufder Wortebene miteinander verknupft. Hierbei werdenverschiedene Filter eingesetzt: Worterbuch, Wortarten,Wortformenahnlichkeit.

In: [in:1] true 1.0welchem: [which:0.5] true 0.5Jahrzehnt: [decade:1] true 1.0investierten: [invest:1] true 1.0japanische: [japanese:0.5] true 0.5Autohersteller: [car manufacturers:0.8, automakers:0.1] true 0.8sehr: [very:1] true 1.0stark: [strongly:0.5] true 0.5

Evaluation Mit beiden Methoden haben wir an den CLEFEvaluationen 2005 und 2006 teilgenommen, mit der nach-dem-Methode ebenfalls im Jahr 2004. Tabelle 4 fasst dieErgebnisse fur das Sprachpaar ENDE (bevor-Methode)und DEEN (nachdem-Methode) zusammen, sowie ver-gleichend unsere erzielten Ergebnisse fur die monolingualeAufgabe DEDE (man beachte, dass in allen drei Aufga-ben dasselbe System eingesetzt wurde!). Bewertet wurdedie Akkuratheit der ersten gelieferten exakten Antworten fur200 Testfragen (das entspricht demnach einem MRR mitN = 1). Fur ENDE und DEDE wurden daruberhinaus beider CLEF-2006 fur die 3 ersten Antworten ein MRR von0.3536 bzw. 0.4567 erreicht.

Bei der Analyse der Ergebnisse muß man berucksich-tigen, dass von Jahr zu Jahr die Anforderungen an die Auf-gaben gestiegen sind. Zum Beispiel wurden 2005 erstmalsDefinitionsfragen und temporalrestringierende Fragen ein-gefuhrt. Im Jahr 2006 wurden zusatzlich listenbasierte Fra-gen eingefuhrt und es wurde erstmals nicht der Typ derFrage bereits vorgegeben, was die Anforderungen an dieFrageanalyse erheblich erhoht. Fur die Aufgaben DEDEund ENDE konnten wir jeweils die besten Ergebnisse erzie-len. Fur die Aufgabe DEEN haben wir die besten Ergebnissein den Jahren 2004 und 2005 erreicht.

Da die Schwierigkeiten der Aufgaben in jedem Jahrerhoht wurden, konnen die Ergebnisse aus verschiedenenJahren zwar nicht unmittelbar verglichen werden, gebenaber sehr gute Hinweise uber das Performanzpotential ein-zelner Strategien wieder. Die sehr gute Verbesserung unse-

Tabelle 4 Unsere CLEF-Ergebnisse fur monolingual Deutsch unddas Sprachpaar Deutsch/Englisch (n.t. steht fur nicht teilgenommen)

2004 2005 2006

DEEN 23,5% 25,5% 17,89%ENDE n.t. 23% 32,8%DEDE 25,4% 43,5% 42,32%

res Ergebnisses in der Aufgabe ENDE erklaren wir damit,dass in der bevor-Methode die sprachspezifische Frageana-lyse von SMES eingesetzt wird, die u.a. explizit den Fra-getyp bestimmen kann, vgl. Abschn. 6. In der nachdem-Methode muss jedoch die Information des Fragetyps ausder deutschen Analyse auf die englische Ubersetzung derFrage automatisch ubertragen werden (man beachte, dassdies im Jahr 2005 nicht notig war, da dort der Fragetyp be-reits vorgegeben war). Fur die Bestimmung des Fragetypssind jedoch teilweise sprachspezifische Informationen not-wendig, was zumindest unserer aktuellen Implementationder nachdem-Methode erhebliche Schwierigkeiten zu verur-sachen scheint.

8 Verwandte Arbeiten

Gegenwartig existieren nur wenige datengesteuerte Me-thoden fur end-to-end QA-Systeme. Ramakrishnan et al.prasentieren einen Ansatz zur automatischen Bestimmungvon oberflachennahen Textmustern, die die Methode desMaximum Entropy Modellings zum Ranking von Snippetsheranzieht (cf. [17]). Sie erreichen einen MRR von 0.2993auf 500 TREC-10 Fragen, die auf entsprechende TRECQA-Dokumenten angewendet werden. Das sind in der Re-gel kurze Nachrichtentexte. Sie verwenden wissensintensiveMethoden zur Merkmalsextraktion, u.a. volles Parsing undWordNet zur Desambiguierung.

Ein instanzenbasierter Ansatz fur QA ist von [11] ent-wickelt worden. Sie betrachten insbesondere temporalre-stringierende Fragen aus dem TREC-9 bis TREC-12 Kor-pora und erreichen einen durchschnittlichen MRR von0.447, allerdings unter Verwendung eines sehr viel großerenFragekorpus. Sie stellen einen sehr interessanten Ansatz furdas Clustern von Fragen vor, der auf dem strukturellen Ver-gleich von Fragen unter Verwendung von POS-Tagging undvollem Parsing basiert. Bei der Evaluation fokussieren sieauf webbasierte Snippets, die die korrekte Antwort enthal-ten, nicht jedoch auf die Extraktion der exakten Antworten.

Sasaki stellt ein multilinguales Verfahren fur QA vor,das ebenfalls auf dem Maximum Entropy Modelling ba-siert (cf. [20]). Ahnlich wie in unsere Methode, werdenneue Antworten durch Vergleich der Kontexte von bereitsbekannten Antworten bestimmt, die ebenfalls auf einemSprachmodell basieren, das aus einem Trainingskorpus vonFrage-Antwortpaaren abgeleitet wurde. Allerdings wirddieser Korpus nicht dynamisch bestimmt, wie dies in un-serem Ansatz der Fall ist, sondern basiert auf den ma-nuell erstellten TREC-Korpora. Das Verfahren basiert imWesentlichen auf Part-of-Speech-Tagging und einer spe-ziellen Morphologiekomponente, die uber eine Vielzahlan feinkornigen Wortarten verfugt, die auch semantischeMerkmale umfaßt.

1 3

Webbasierte Fragebeantwortung 83

Echihabi et al. prasentieren eine Methode, die auf demprobabilistischen Noisy-Channel Model zur Bestimmungder Ahnlichkeit zwischen Fragen und Antwortsatzen basiert(cf. [6]). Ihr bestes Ergebnis von MRR = 0.812 wird fur 24Fragen von der TREC-11 auf Basis einer Trainingsmengevon ca. 100.000 Frage-Fakten-Antwortpaaren erzielt. Un-ter Verwendung eines Korpus von ca. 90.000 allgemeinerenFrage-Antwortpaaren erreichen sie einen MRR zwischen0.343 und 0.365 fur 500 TREC-11 Fragen. Im Unterschiedzu unserem Ansatz verwenden sie sehr wissensintensiveVerarbeitungskomponenten und eine sehr viel großere Trai-ningsmenge.

Basierend auf ihren eigenen Arbeiten an AskMSR, er-forschen [2] die Verwendung von statistischen Modellenim Kontext von webbasierten QA-Systemen. Ihre Motiva-tion ist dabei vergleichbar mit der unsrigen, insofern dasssie ebenfalls eine strenge datengesteuerte Perspektive vor-ziehen, die nur uber sehr einfache sprachspezifische Wis-sensquellen verfugt. Im Wesentlichen fuhren sie einfacheReformulierungen und Mustervergleiche basierend auf N-gram Technologien durch. Damit generieren sie sehr elegant(sehr viele) Paraphrasen zur aktuellen Frage, die unmittelbarzur Suche mit einer IR-Suchmaschine verwendet werden.Um zu optimalen Reformulierungsstrategien zu gelangen,wird anschließend eine Kostenanalyse auf Basis von er-lernten Entscheidungsbaumen fur alle erfolgreichen Frage-Antwortpaare durchgefuhrt.

9 Zusammenfassung und Ausblick

In diesem Artikel haben wir einen Uberblick uber die amDFKI entwickelten innovativen Strategien zur crosslingua-len, webbasierten Fragebeantwortung in offenen Domanengegeben. Die Methoden verwenden dabei nur sehr wenige,einfache sprachspezifische Wissensquellen, deren Bereit-stellung und Verarbeitung im Wesentlichen die Frageana-lyse betrifft.

Die ausfuhrliche Evaluation unserer neuartigen daten-getriebenen QA-Methoden liefert bereits sehr vielverspre-chende Ergebnisse, die nicht nur konkurrenzfahig mitder internationalen Spitzenklasse sind, sondern diese garuberbieten (siehe unsere CLEF Ergebnisse). Unsere Er-gebnisse zeigen, dass der breite Einsatz von maschinel-len Lernverfahren auch fur komplexe Aufgaben, wie diedomanenoffene, webbasierte Fragebeantwortung, sehr viel-versprechend ist und fur einfache faktoide Fragetypen be-reits die noch dominierenden manuell formulierten QA-Strategien uberbietet.

Neben der Erforschung und Entwicklung weiterer inno-vativer Konzepte in dem Bereich der webbasierten Frage-beantwortung (z.B. Strategien zur Behandlung komplexe-rer Fragen und Antworten), gilt unser Augenmerk auch der

Verbesserung der aktuellen Systemperformanz bzgl. Akku-ratheit, aber auch Geschwindigkeit. Obwohl aus wissen-schaftlicher Perspektive die aktuellen Ergebnisse vielver-sprechend sind, ist die bisherige Performanz noch nicht aus-reichend genug fur eine Integration in Anwendungen außer-halb der Forschungslabore. Daher ist es ein erstes nahelie-gendes Ziel, die Performanz der bestehenden Technologienwesentlich zu erhohen.

Die Steigerung der Systemperformanz allein ist aber fureine erfolgreiche Integration dieser neuen Technologien inzukunftige Anwendungen nicht ausreichend. Ein weiterer,gleichermaßen aus Forschungs- und Anwendungsperspek-tive relevanter Aspekt, betrifft die Glaubwurdigkeit der voneinem System bestimmten Antworten. Im Allgemeinen wirdes einem webbasierten QA-System nicht moglich sein, dieKorrektheit von Antworten vollstandig zu beweisen, zumin-dest was den gegenwartigen Stand der Kunst betrifft. Wahr-scheinlicher ist, dass ein System bestimmen kann, wie ,,si-cher“ es ist, dass die Antworten fur den Fragenden die ,,be-sten“ sind, die das System gefunden hat. Ahnlich zu beste-henden Konzepten der Glaubwurdigkeit von Webseiten (cf.http://credibility.stanford.edu/), sollte ein QA-System einemBenutzer die Zuverlassigkeit der vorgeschlagenen Antwor-ten vermitteln konnen.

Aktuell ist dieser Bereich im Kontext von webbasiertenQA-Systemen noch Neuland. Allerdings gehen wir davonaus, dass sich in absehbarer Zeit auf Grund der Dringlichkeitdieses Problems, ein verstarktes Forschungsinteresse ent-wickeln wird. Wir haben hierbei mit der Entwicklung vonersten Konzepten fur eine ,,Answer Credibility“ bereits erstewichtige Erkenntnisse erworben, an deren Umsetzung wiraktiv arbeiten.

Danksagung Die in diesem Papier beschriebenen Arbeiten wurdenfinanziell unterstutzt von den BMBF-Projekten Quetal (FKZ 01 IWC02), HyLap (FKZ 01 IW F02) und Smartweb (FKZ 01 IMD01A). Ich bedanke mich sehr herzlich bei meinen Kollegen AlejandroFigueroa und Bogdan Sacaleanu fur die Unterstutzung bei der Um-setzung der Methoden. Ich bedanke mich auch sehr gerne bei denanonymen Gutachtern und bei meinem Kollegen Norbert Reithin-ger fur die hilfreichen Tipps und Hinweise bei der Erstellung desManuskripts.

Literatur

1. Ankolekar A, Buitelaar P, Cimiano P, Hitzler P, Kiesel M,Krotzsch M, Lewen H, Neumann G, Sintek M, Tserendorj T, Stu-der R (2006) Smartweb: Mobile access to the semantic web. In:Proc of the Demo Session at the International Semantic Web Con-ference, Athens GA, USA, Nov

2. Azari D, Horvitz E, Dumais S, Brill E (2003) A decision makingperspective on web question answering. In: UAI

3. Belkin M, Goldsmith J (2002) Using eigenvectors of the bigramgraph to infer morpheme identity. In: Proceedings of the ACL-02 workshop on Morphological and phonological learning, As-sociation for Computational Linguistics, Morristown, NJ, USA,pp. 41–47

1 3

84 Neumann

4. Clarke CLA, Cormack GV, Lynam TR, Li CM, McLearn GL(2001) Web reinforced question answering (multitest experimentsfor trec 2001). In: TREC

5. Dumais ST, Banko M, Brill E, Lin JJ, Ng AY (2002) Web que-stion answering: is more always better? In: SIGIR, pp. 291–298

6. Echihabi A, Marcu D (2003) A noisy-channel approach to que-stion answering. In: ACL

7. Figueroa A, Neumann G (2006) Genetic algorithms for data-driven web question answering. Evol Comput, accepted, to appear

8. Figueroa A, Neumann G (2006) Language independent answerprediction from the web. In: FinTAL, pp. 423–434

9. Holland JH (1992) Adaptation in Natural and Artificial Sys-tems. A Bradford Book. The MIT Press, Cambridge,Massachusetts

10. Kwok CCT, Etzioni O, Weld DS (2001) Scaling question answe-ring to the web. In: WWW

11. Lita L, Carbonell J (2004) Instance-based question answe-ring: A data-driven approach. In: EMNLP 2004, Barcelona,Spain

12. Magnini B, Vallin A, Ayache C, Erbach G, Penas A, de RijkeM, Rocha P, Simov K, Sutcliffe R (2005) Overview of the clef2004 multilingual question answering track. In: Peters C, CloughPD, Jones GJF, Gonzalo J, Kluck M, Magnini B (Eds), "Multilin-gual Information Access for Text, Speech and Images: Results ofthe Fifth CLEF Evaluation Campaign. Lecture Notes in ComputerScience, p. Vol. 3491

13. Moldovan D, Harabagui S, Clark C, Bowden M, Lehmann J, Wil-liams J (2004) Experiments and analysis of lcc’s two qa systemsover trec 2004. In: Proceedings of The Thirteenth Text RetrievalConference (TREC 2004), Gaithersburg, USA

14. Neumann G, Piskorksi J (2002) A shallow text processing coreengine. J Comput Intell 18(3):451–476

15. Neumann G, Sacaleanu B (2006) Experiments on cross-lingualityand question-type driven strategy selection for open-domainquestion answering. In: CLEF 2005, Springer-Verlag LNCS,vol 4022

16. Radev D (2003) Panel on web-based question answering. In:AAAI Spring Symposium on New Directions in Question Answe-ring, AAAI press

17. Ramakrishnan G, Paranjape D, Chakrabarti S, Bhattacharyya P(2004) Is question answering an acquired skill? In: WWW04

18. Ravichandran D, Hovy EH (2002) Learning surface text patternsfor a question answering system. In: ACL, pp 41–47

19. Russell SJ, Norvig P (2004) Kunstliche Intelligenz. Ein modernerAnsatz. Pearson Studium

20. Sasaki Y (2005) Question answering as question-biased term ex-traction: a new approach toward multilingual QA. In: Proceedingsof ACL’05, URL http://www.aclweb.org/anthology/P05-1027

21. Wahlster W (2000) Mobile speech-to-speech translation of spon-taneous dialogs: An overview of the final verbmobil system.In: Wahlster (Ed.) Verbmobil: Foundations of Speech-to-SpeechTranslation, Springer, pp. 3–21

Gunter Neumann ist ResearchFellow und Principal Researcheram Deutschen Forschungszentrumfur Kunstliche Intelligenz (DFKIGmbH). Er studierte Informa-tik, Kunstliche Intelligenz undComputerlinguistik an den Uni-versitaten Koblenz-Landau undSaarbrucken. Von der Universitatdes Saarlandes erhielt er seinePromotion und Habilitation. SeinForschungsinteresse betrifft alleAspekte der naturlichsprachlichenVerarbeitung mit einem aktuellenSchwerpunkt auf der Erforschungund Entwicklung von webba-sierten lernfahigen Systemenzur Informationsextraktion undFragebeantwortung.

1 3