Wissensextraktion im Rahmen des Grids

Abstract

Zusammenfassung Moderne Netzwerke stellen immense Datensammlungen bereit, so dass oft weniger das Bescha en von Informationen, als vielmehr das Heraus ltern der relevanten Essenz, den gro ten Aufwand darstellt. Hier konnen Methoden der Wissensextraktion helfen, essentielle Inhalte aus vorliegenden Daten als hoherwertiges Wissen zu extrahieren und damit konkrete Fragestellungen einfacher beantwortbar zu machen. Grid Computing hat zum Ziel verteilte Ressourcen fur alle Beteiligten e zient nutzbar zu machen. Bisherige Umsetzungen haben sich dabei primar auf Rechenleistung als Ressource konzentriert. Um auch die im Grid vorliegenden Daten sinnvoll nutzbar zu machen, bietet es sich an, das enthaltene Wissen zu extrahieren und in eine abstrakte Form zu ubertragen. Extraktionstechnologien konnen hierbei von der Gridinfrastruktur pro tieren und so eine bessere E zienz erreichen. Innerhalb dieser Arbeit wird ein generisches Extraktionsframework vorgestellt, sich ergebende Probleme bei der U bertragung in ein Gridumfeld aufgezeigt und erste Schritte zur Anpassung dargelegt.

1. EINLEITUNG

Mit der Entstehung von Computernetzwerken entstand auch der Bedarf entfernte Ressourcen, wie z.B. Rechenleistung und Speicher, aber auch vorhandene Daten und Dienste, in den lokalen Arbeitsprozess einzubinden. Dieses Bestreben brachte das Grid Computing hervor, das darauf abzielt, die vorhandenen Ressourcen in sogenannten virtuellen Organisationen fur die jeweiligen Mitglieder zuganglich zu machen. Bisher konzentrieren sich diese Bemuhungen primar auf verschiedene Aspekte zur verteilten Berechnung von Anwendungen, wie z.B. Scheduling, Work ow Management (UNICORE[ 19 ], Condor[ 24 ]) und Zugri ssicherheit (Globus[ 13 ]). Allerdings bietet sich, zur Nutzung von Synergien, eine Zusammenarbeit auch auf Ebene der eigentlichen Inhalte an. Dazu gehort z.B. eine einheitliche globale Suche nach diesen Inhalten. Eine Schlusselwortsuche auf den Daten selbst stellt hierbei nur den kleinsten gemeinsamen Nenner dar. Die enthaltenen Informationen werden dabei vollstandig abgebildet, konnen aber auch nur dann gefunden werden, wenn explizit mit dem richtigen Schlusselwort nach ihnen gesucht wird. Beispielsweise wird eine Schlusselwortsuche nach dem Geburtsort von Albert Einstein zu der Anfrage \Einstein Geburtsort" ein Dokument das lediglich den Satz \Einstein wurde in Ulm geboren" nicht als Ergebnis liefern. Eine abstrakte Wissensreprasentation dagegen kann solche unterschiedlichen Ausdrucksweisen vereinheitlichen und die Suche nach den eigentlichen Inhalten so erleichtern. Zudem fallt die Suche nach Beziehungen uber eine Schlusselwortbasierte Suche schwer. Sind z.B. alle Naturwissenschaftler gesucht, die in Ulm geboren wurden, lasst sich diese Beziehung schwerlich als Schlusselwortsuche formulieren. Zur Beantwortuntg einer solchen Suche bedarf es Hintergrundwissen zur Identi kation von Naturwissenschaftlern und ihren Geburtsorten. Liegt solches Wissen z.B. in Ontologien vor, kann die Fragestellung dagegen recht einfach als SPARQL Anfrage formuliert werden: \?x hatTyp Naturwissenschaftler . ?x geborenIn Ulm".

Auf der anderen Seite zeigt sich zwar, dass Verfahren der Wissensextraktion auf Texten durch Einsatz komplexerer Sprachanalysemethoden deutlich verbesserte Ergebnisse erzielen konnen (z.B. Deep Syntactic Analysis in LEILA[ 21 ]), dies geht aber in der Regel auf Kosten der Laufzeit([ 20 ]), da diese Verfahren einen deutlich hoheren Aufwand erfordern als beispielsweise relativ einfache Regeln auf Basis der Zeichenabfolge (z.B. Regulare Ausdrucke).

In der Kombination beider Technologien bietet sich hier also ein Synergiee ekt an. Einerseits liegen in den GridCommunitys gro e Mengen an Daten vor, deren Inhalt auf einem hoheren Abstraktionslevel einheitlich und e zient durchsuchbar zur Verfugung gestellt werden soll. Andererseits kann die Wissensextraktion von der verteilten Rechenleistung des Grids pro tieren. Fur die beteiligten Communitys ergibt sich der Vorteil, dass eine existierende Infrastruktur genutzt wird, um ihre Daten mit e zienten Methoden aufzuwerten und Zugri auf Wissen anderer Communitys zu erhalten.

Im folgenden wollen wir einen kurzen Einblick in den Stand der Forschung im Bereich der Wissensextraktion und des Grid Computing geben. Anschlie end wird in Abschnitt 3 ein generisches Musterbasiertes Verfahren zur Wissensextraktion, das in einem Grid-Projekt (WisNetGrid [ 14 ]) Verwendung nden soll, vorgestellt. In Abschnitt 5 besprechen wir letztlich o ene Punkte bzw. mogliche Erweiterungen.

2. VERWANDTE ARBEITEN

Zur Realisierung von Gridinfrastrukturen sind verschiedene Middlewarekomponenten entstanden, die sich jeweils Aspekten der verteilten Berechnung von Anwendungen (Jobs) im Grid widmen. Wahrend UNICORE[ 19 ] primar den Zugri auf gro e Rechencluster uber ein Grid anstrebt und hierfur auch ein Job Work ow Management zur Verfugung stellt, widmete sich Condor[ 24 ] ursprunglich mehr der Vernetzung von Desktoprechnern, was durch die gro ere Unbestandigkeit der beteiligten Knoten uber ein Job Work ow Management hinaus ein Checkpoint System zur Wiederaufnahme unterbrochener Grid Jobs hervorbrachte. Wahrend beide Systeme den Datentransfer zu einem ausfuhrenden Knoten im Grid und zuruck erlauben, bieten Globus[ 13 ] und gLite [ 9 ] weitergehendere Kontrolle uber die Daten im Grid sowie ein z.T. detaillierteres Rechtesystem.

In Deutschland koordiniert die D-Grid-Initiative[ 8 ] (D-Grid) Grid-orientierte Projekte mit dem Ziel eine nachhaltige Grid-Infrastruktur zu scha en. U ber die grundlegenden Basisdienste zur Einrichtung des Grids hinaus, sollen hierbei auch hohere Dienste etabliert werden. Die beteiligten akademischen Communitys setzen sich dabei aus unterschiedlichen Disziplinen, wie z.B. Linguistik (TextGrid[ 15 ]) und Astrophysik (AstroGrid[ 10 ]) zusammen, daruberhinaus sind jedoch auch kommerzielle Projekte (z.B. FinGrid[ 12 ]) eingebunden. Durch die Vielfalt der beteiligten Communitys, liegt eine gro e Datenheterogenitat vor. Methoden der Wissensextraktion konnen genutzt werden, um diese Heterogenitat fur den Nutzer zu uberwinden und eine hoherwertige Suche auf dem vorhanden Wissen anzubieten. Allerdings bestehen umgekehrt naturlich auch besondere Anforderungen an die verwendeten Extraktionsverfahren, z.B. kann eine Community darauf bestehen, dass extrahiertes Wissen in ihrem direkten Ein ussbereich verbleibt.

Verfahren zur Wissensextraktion versuchen aus konkreten Informationen in Dateien abstrakte Fakten zu generieren[ 17 ]. Beispielsweise kann aus der Aussage \Einstein kam in Ulm zur Welt" das abstrakte Wissen, dass Albert Einstein in Ulm geboren wurde (als Fakt ausgedruckt geborenIn(AlbertEinstein,Ulm)) hergeleitet werden. Dazu muss allerdings der mehrdeutige Ausdruck \Einstein" als eine Ausdrucksform der eindeutigen Entitat AlbertEinstein erkannt werden. Es existiert ein breites Spektrum an Verfahren zur Wissensextraktion, drei der bekanntesten sind Snowball[ 1 ], KnowItAll[ 11 ] and DIPRE[ 6 ]. Sie sind anhand einiger Beispielfakten in der Lage mit statistichen Methoden automatisch textuelle Muster zu nden, die wahrscheinlich die zugehorige Relation ausdrucken. Dieser Ansatz kann weiter verbessert werden, indem bei der Wahl der Muster auch Gegenbeispiele berucksichtigt werden (siehe LEILA[ 21 ]). Wahrend diese Verfahren je darauf abzielen fur eine gegebene Relation weitere Fakten zu nden, versucht z.B. TextRunner[ 3 ] Fakten aller Relationen, die im Internet auftauchen, zu extrahieren. Allerdings wird hierbei keine Au osung von Mehrdeutigkeiten und Umwandlung auf Relationen durchgefuhrt. Liegen die Daten teilweise strukturiert vor, kann das durch angepasste Extraktionsverfahren ausgenutzt werden. So konzentrieren sich einige Ansatze z.B. auf eine Extraktion aus Wikipedia ([ 22 ],[ 2 ]). In [ 18 ] wurde ein Framework zur deklarativen Extraktion basierend auf Datalog eingefuhrt, welches zur Erzeugung von Portalen wie DBlife[ 7 ] genutzt wurde. Das Modell erlaubt eine regelbasierte Extraktion mit Abgleich gegen existierendes Wissen, z.B. zur Bestimmung von Entitaten. Ein anderer Ansatz ([ 16 ]) nutzt Markov Logik um Entitaten auf Basis von Wahrscheinlichkeiten zu identi zieren. Dem Ansatz des Lifelong Learning folgend verwaltet ALICE[ 4 ] eine Wissensbasis in Form einer Ontologie, die durch extrahierte Fakten regelma ig erweitert wird. Allerdings gibt es dabei keine Mechanismen, die die Konsistenz der Ontologie sicherstellen. SOFIE[ 23 ] vereint Muster-basierte Wissensextraktion mit einer logischen Konsistenzprufung und eignet sich daher insbesondere zur fortwahrenden Erweiterung einer Ontologie. Das angestrebte Extraktionsverfahren fur die Anwendung im Grid basiert daher auf der SOFIE Architektur.

3. EXTRAKTIONSVERFAHREN

Auf dem abstrakten Level sind Muster generische Verallgemeinerungen bestimmter Ausdrucksformen von Wissen. In Texten sind Muster also beispielsweise parametrisierte Formulierungen die jeweils einen bestimmten Sachverhalt auf unterschiedlichen Objekten ausdrucken. Die Formulierung \Einstein kam in Ulm zur Welt" beispielsweise beschreibt den Sachverhalt, dass Albert Einstein in Ulm geboren wurde. Die beiden Komponenten `Einstein' und `Ulm' konnen dabei einfach ausgetauscht werden, um denselben Sachverhalt zwischen einer anderen Person und einem anderen Ort auszudrucken. Ersetzen wir diese Komponenten also durch Variablen, erhalten wir das allgemeine Muster X kam in Y zur Welt , welches eine Ausdrucksform der geborenIn Relation darstellt. Tritt dieses Muster nun mit einer konkreten Variablenbesetzung auf, z.B. in der Form Einstein kam in Ulm zur Welt , bezeichnen wir dies als Musterinstanz. Die gleiche Musterinstanz kann in verschiedenen Dokumenten auftreten. Solche Vorkommen mit Bezug zu einer Quelle bezeichnen wir als Mustervorkommen. Dieser Zusammenhang ist in Abbildung 1 skizziert. Die Musterinstanz Albert Einstein kam in Ulm zur Welt wurde hierbei in Dokument D1 gefunden, wahrend in Dokument D2 eine Instanz des Musters X wurde geboren in Y vorliegt. Aus beiden Mustervorkommen lasst sich der Fakt geborenIn(AlbertEinstein,Ulm) ableiten.

Generell lasst sich das Extraktionsverfahren in vier Schritte unterteilen. Zuerst mussen Quelldateien auf Mustervorkommen untersucht werden. Anschlie end werden diese Vorkommen ausgewertet und potentielle Fakten aus den Mustervorkommen generiert. Im dritten Schritt werden diese potentiellen Fakten mit der bestehenden Wissensbasis abgeglichen. Daraus ergibt sich eine optimale Menge an potentiellen Fakten, die mit dem bestehenden Wissen in Einklang steht. Diese Fakten werden dann im letzten Schritt zur Wissensbasis hinzugefugt. Parallel zur Extraktion von Fakten, werden auch eigenstandig neue Muster fur bereits bekannte Relationen erlernt. Ist beispielsweise bereits bekannt, dass Albert Einstein in Ulm geboren wurde, und in einem Dokument beginnt ein Satz mit \Albert Einstein erblickte das Licht der Welt in Ulm ..." kann daraus abgeleitet werden, dass das Muster X erblickte das Licht der Welt in Y ein guter Kandidat fur eine Ausdrucksform des Fakts geborenIn(X,Y) ist. Beide Lernverfahren werden dabei einer gemeinsamen logischen Evaluierung unterzogen. Basierend auf logischen Regeln und einer Menge von Fakten und Hypothesen, z.B. uber neue Muster, wird eine Zuweisung von Wahrheitswerten zu den Hypothesen gesucht, so dass ein Maximum der logischen Regeln erfullt ist.

Aussagen. Eine Aussage besteht aus einer Relation und einer Liste von Entitaten. Jeder Aussage wird ein binarer Wahrheitswert zugeordnet, der in eckigen Klammern angegeben wird:

geborenIn(AlbertEinstein,Ulm) [ 1 ] Eine Aussage mit Wahrheitswert 1 bezeichnen wir als Fakt, wahrend eine Aussage mit unbekanntem Wahrheitswert eine Hypothese darstellt. Ist kein Wahrheitswert angegeben, handelt es sich um einen Fakt.

Regeln. Die logischen Regeln basieren auf Literalen. Ein Literal ist eine Aussage ohne Wahrheitswert, bei der sowohl die Relation als auch die Entitaten durch Variablen ersetzt werden konnen. Eine Regel ist eine logische Formel erster Stufe basierend auf Literalen. Zur Instantiierung einer solchen quanti zierten Regel, wird jede Variable an all ihren Vorkommen durch die gleiche Entitat ersetzt. Grundsatzlich mussen Regeln auf allen moglichen Instantiierungen gelten, um gultig zu sein. U blicherweise wird eine Person beispielsweise nur an einem Ort geboren. Dies lasst sich vereinfacht wie folgt als logische Regel ausdrucken:

geborenIn(X,Y) ):geborenIn(X,Z) Basisregeln. Im folgenden wollen wir zwei stark vereinfachte Basisregeln vorstellen, die dem Erlernen neuer Fakten und moglicher neuer Muster entsprechen. Hierzu bedienen wir uns zweier spezieller Relationen: 1. patternOcc(P,A,B ) besagt, dass das Muster P mit den Instanzen A und B (z.B. P= X wurde geboren in Y mit X=A=\Einstein" und X=B=\Ulm") vorgekommen ist. Korrekterweise mussten wir hier noch auf das Dokument, in dem die Musterinstanz gefunden wurde, eingehen. Darauf verzichten wir an dieser Stelle. 2. expresses(P,R) besagt, dass das Muster P eine Ausdrucksform der Relation R (also z.B. geborenIn) ist.

^ Das Erlernen neuer Muster bzw. ihrer Bedeutung kann dann vereinfacht wie folgt als logische Regel ausgedruckt werden: patternOcc(P,X,Y) R1: R(X,Y) )expresses(P,R) Umgekehrt lasst sich auch das Erlernen neuer Fakten in eine Regel fassen: R2: ^ patternOcc(P,X,Y) expresses(P,R) )R(X,Y) Bei beiden Regeln ignorieren wir hier, dass je die Entitaten, die X und Y entsprechen, noch eindeutig aus den konkreten Worten identi ziert werden mussten. Dies kann ebenfalls als Teil der Regel formuliert werden. Ebenso konnen weitere Regeln domainspezi sches Wissen kodieren, z.B. dass Personen nur an einem Ort geboren werden konnen.

Werden Quelldaten bearbeitet, erzeugt jedes gefundene Mustervorkommen einen entsprechenden patternOcc Fakt. Zudem konnen wir davon ausgehen, dass bereits einige Fakten gesuchter Relationen in der Ontologie vorhanden sind, z.B. weil sie bereits extrahiert wurden oder weil es sich um die anfangs gegebenen Beispiele handelt. Weiterhin konnten auch bereits Instanzen der expresses Relation bekannt sein. Wann immer nun die Voraussetzungen einer Regel erfullt sind, erzeugt diese Regel eine Hypothese aus der als Folge angegebenen Aussage.

Ist z.B. patternOcc( X kam in Y zur Welt ,\Einstein",\Ulm") und geborenIn(AlbertEinstein,Ulm) gegeben, wird die Hypothese expresses( X kam in Y zur Welt ,geborenIn) [?] durch Regel R1 erzeugt.

Ist die Bearbeitung der Quelldaten abgeschlossen, muss entschieden werden, welche Hypothesen als wahre Fakten betrachtet und somit in die Ontologie aufgenommen werden sollen. Hierzu wird eine Wahrheitszuweisung an die Hypothesen ermittelt, die ein Maximum an Regelinstanzen erfullt. D.h. einzelne Regeln durfen grundsatzlich gebrochen werden. Wenn z.B. bereits in der Ontologie bekannt ist, dass eine generierte Hypothese nicht wahr sein kann, weil das Gegenteil bereits wahr ist, muss die entsprechende Regel gebrochen werden konnen, ohne dass deshalb der komplette Vorgang fehlschlagt.

Um eine solche Wahrheitszuweisung zu nden, kann die Problemstellung auf ein maximum satis ability (MAX-SAT) Problem ([ 5 ]) reduziert werden. Das MAX-SAT Problem basiert auf Klauseln:

Definition 3.1 (Klausel). Eine Klausel ist eine Disjunktion X1 _ ::: _ Xn wobei fur alle Xi2f1;:::;ng gilt: Xi ist entweder eine Variable oder eine negierte Variable.

Definition 3.2 (MAX-SAT Problem). Gegeben eine Menge von Klauseln C1; :::; Cn uber m Variablen. Finde eine Wahrheitszuweisung fur die Variablen, so dass die Anzahl erfullter Klauseln maximal ist.

Das MAX-SAT Problem ist ein bekanntes NP-vollstandiges Problem, fur das exakte Algorithmen sowie Annaherungsverfahren zur Losung existieren ([ 5 ]). Zur U bertragung in ein MAX-SAT Problem mussen die Regeln per Rewriting in Klauseln umgewandelt werden und die enthaltenen Aussagen bzw. ihre Wahrheitswerte bilden die Variablen. Gewichtete Regeln. In dem vorgestellten Ansatz werden alle Regeln gleichbehandelt. Allerdings konnen einige Regeln wichtiger als andere sein. Dies spielt z.B. eine Rolle, wenn unterschiedlich wahrscheinliche Zuordnungen von Wortern zu einzelnen Entitaten uber Regeln abgebildet werden. Zudem kann so existentes Wissen starker gewichtet werden als neu erlerntes. Das Problem der Zuordnung von Wahrheitswerten zu den Hypothesen unter Beachtung einer Regelgewichtung kann nicht in ein MAX-SAT Problem uberfuhrt werden. Stattdessen kann es aber in ein gewichtetes MAXSAT Problem ([ 5 ]) uberfuhrt werden. Die U bertragung in ein gewichtetes MAX-SAT Problem, sowie ein e zienter Algorithmus zur Losung eines solchen Problems wird in [ 23 ] diskutiert. Auf beides gehen wir hier nicht weiter ein. Im Grunde kann die Hypothesenbewertung mit einem beliebigen Ansatz gelost werden, es muss lediglich eine Zuweisung von Wahrheitswerten fur die aufgestellten Hypothesen gefunden werden, die moglichst viele Regeln erfullt und dabei eine Gewichtung erlaubt. Markov Logik bote z.B. einen anderen Ansatz.

4. UMSETZUNG IM GRIDUMFELD

Aus dem Einsatz im Grid ergeben sich besondere Anforderungen an die Wissensexktraktion. Auf einige wollen wir im folgenden kurz eingehen.

Heterogene Daten und Domänen. Durch die Zielsetzung vollig unterschiedliche Communitys uber eine gemeinsame Gridarchitektur zu verknupfen und daruber gegenseitigen Zugri auf in vorhandenen Daten enthaltenes Wissen zu ermoglichen, ergibt sich eine heterogene Menge an Daten aus denen abstraktes Wissen extrahiert werden soll. Das bedeutet einerseits dasss unterschiedliche Formatierungen strukturierter Inhalte, wie z.B. Tabellen, vorliegen, aber auch dass ganz unterschiedliches Hintergrundwissen vonnoten ist, um sinnvoll abstrakte Fakten aus den Daten verschiedener Communitys zu generieren. Hier bietet das besprochene Extraktionsframework gute Anpassungsmoglichkeiten. Einerseits konnen Muster generisch anhand von Beispielwissen automatisch erlernt werden, so dass sich die Extraktion inkrementell gestalten lasst. Andererseits konnen Nutzer aber auch mit entsprechenden Tools direkt Muster vorgeben oder bei entsprechend modularer Implementierung einzelne Komponenten des Frameworks fur ihre Belange austauschen. Dadurch kann z.B. ein alternatives Verfahren zur Verarbeitung domainspezi scher strukturierter Daten hinzugefugt werden, dessen Muster sich auf die spezielle Struktur beziehen. Ebenso konnen auf diese Weise ganzlich andere Inhalte, wie z.B. Audiodaten oder gra sche Darstellungen, untersucht werden. Unterschiedliche Mustertypen fur verschiedene Datenanalysemodule lassen sich parallel verwalten, es muss lediglich die Information mitgefuhrt werden, welches Muster zu welchem Analysemodul gehort. Ebenso kann domainspezi sches Vorwissen in Form von logischen Regeln ubergeben werden. Alternativ kann Vorwissen in Form von bestehenden Ontologien zur Verfugung gestellt werden, die dann in den Reasoningprozess eingebunden werden. Die Datenheterogenitat im Grid beschrankt sich zudem nicht nur auf die Dateninhalte und Formate, sondern auch auf die Sprache der Texte. D.h. das Extraktionsverfahren muss an verschiedene Sprachen, zum Einsatz im D-Grid insbesondere an Deutsch, angepasst werden bzw. einfach an weitere Sprachen anpassbar sein. Einen breiten Basisansatz kann hier eine einfache leicht anpassbare Textanalyse mit weitgehend sprachunabhangigen Methoden bilden, die bei Sprachen fur die noch kein hoherwertiges Analysemodul vorliegt, zum Einsatz kommt.

Verteilte Daten - Aufspaltung des Frameworks. Eine Grundeigenschaft des Grids ist die verteilte Datenlagerung. Extrahiertes Wissen dagegen sollte zentral in einer Ontologie vorgehalten werden, um eine e ziente Suche zu erlauben und die Konsistenz bei (manuellen) A nderungen sicherstellen zu konnen. Dabei konnen einzelne Communitys eigene Ontologien unabhangig voneinander verwalten wollen, um die Kontrolle uber `ihr Wissen' zu behalten. Es ware nun sehr ine zient alle Daten zur Extraktion zu der jeweiligen zentralen Stelle, an der die entsprechende Ontologie vorgehalten wird, zu ubertragen. Einerseits sollte also die Analyse der vorliegenden Daten moglichst lokal am Lagerort der Daten geschehen. Andererseits muss die Extraktionskomponente das extrahierte Wissen in die Ontologie ubertragen und dabei sicherstellen, dass die Konsistenz gewahrt bleibt. Hier bietet sich eine Zweiteilung des Extraktionsverfahrens in einen Extraktionsclient und einen Extrakionsmaster an. Ersterer ubernimmt das lokale Analysieren von Daten und extrahiert Mustervorkommen, letzterer aggregiert die gefundenen Mustervorkommen, generiert daraus Hypothesen und fugt letztlich neue Erkenntnisse zentral in die Ontologie ein. So mussen nicht die eigentlichen Daten, sondern lediglich erkannte Mustervorkommen ubertragen werden. Dabei kann die Extraktion auch uber das Grid verteilt erfolgen. So konnen z.B. zur Textanalyse auch rechenintensivere komplexe Sprachanalysemethoden eingesetzt werden.

Konfidenzen. Aufgrund der generischen Gestaltung sowie fehlerhafter Quelldokumente, kann es vorkommen, dass Fakten extrahiert werden, die nicht als wahr anzusehen sind. Verschiedene Muster bzw. Mustertypen konnen als unterschiedlich sicher betrachtet werden. Beispielsweise ist ein von einer Community manuell vorgegebenes Muster fur ihre strukturierten Daten, z.B. ein Mapping von Spalten- und Zeilenattribut in einer Tabelle auf eine Relation, im Allgemeinen als sicherer anzusehen als ein selbsterlerntes textuelles Muster. Da die Nutzer im D-Grid aus unterschiedlichen Fachrichtungen kommen und daher bei Communityubergreifenden Nachforschungen mit Fakten aus ihnen fremden Fachbereichen umgehen mussen, sollte der Grad der Sicherheit einzelner Fakten ersichtlich sein. Hierzu wird ein Kon denzwert fur jeden Fakt berechnet, der das Vertrauen darin reprasentiert, dass der Fakt korrekt extrahiert wurde. Dieser Wert basiert auf dem Vertrauen in die Qualitat der Quelle und in die Genauigkeit des benutzten Musters. D.h. es existieren Kon denzwerte fur Muster, Quellen und Fakten. Ihre Abhangigkeiten werden in Abbildung 2 skizziert. Generell basiert der Kon denzwert eines Fakts auf allen Mustervorkommen, die ihn bestatigen, bzw. dem durch sie generierten Vertrauen. Ein Mustervorkommen eines exakten und sehr wohl erprobten Musters in einer vertrauenswurdigen Quelle lasst den Fakt glaubwurdig erscheinen. Ist der einzige Beleg fur den Fakt jedoch ein als unsicher eingestuftes Muster, das auf einer unglaubwurdigen Quelle gefunden wurde, so wird der Fakt wenig glaubwurdig erscheinen. Findet sich beispielsweise der Satz \Albert Einstein erhielt seinen Nobelpreis fur ..." auf der Wikipediaseite uber Albert Einstein, so ist dies ein sehr eindeutiger Beleg fur den Fakt hatAuszeichnungErhalten(AlbertEinstein,Nobelpreis). Eng damit verknupft ist das Einarbeiten von Nutzerfeedback. Wird ein extrahierter Fakt von einem Nutzer als fehlerhaft erkannt, sollte dieses Wissen genutzt werden, um fur die Zukunft hinzuzulernen. Das kann beispielsweise uber eine Anpassung der Kon denz in das entsprechende Muster geschehen. Ein weiterer Schritt ware die Kon denzwerte auch direkt in das Extraktionsverfahren einzubinden, z.B. zur Regelgewichtung. Hinzu kommt, dass die gegenwartige Modellierung der Extraktion eingeschrankt ist. So ist es beispielsweise nicht ohne weiteres moglich zeitliche oder ortliche Einschrankungen zu erkennen bzw. mit einem Fakt zu verknupfen. Ebenso konnen z.B. kausale Zusammenhange nicht erkannt werden. Die Modellierung von Meinungen und Wertungen, die sich ja unter Umstanden widersprechen konnen, wird ebenso noch nicht berucksichtigt.

5. ZUSAMMENFASSUNG & AUSBLICK

In der vorliegenden Arbeit wurde ein U berblick uber aktuelle Verfahren der Wissensextraktion gegeben und ein generisches Framework zur Wissensextraktion vorgestellt. Darauf aufbauend wurden einige Aspekte diskutiert, die es bei einer U bertragung des Extraktionsverfahrens in ein Gridumfeld zu beachten gilt. Fur einige dieser Problemstellungen wurden erste Losungsansatze entlang des vorgestellten Frameworks aufgezeigt. Im weiteren Verlauf der Forschungsarbeit mussen die noch o enen Problemstellungen weitergehend analysiert und vollstandige Losungen in Form eines lau ahigen Systems umgesetzt werden. Dieses wird dann an die Bedurfnisse zweier Testcommunitys innerhalb von DGrid angepasst und anschlie end in diesem Rahmen evaluiert werden.

References

6. LITERATUR

[1] E. Agichtein and L. Gravano . Snowball: extracting relations from large plain-text collections . In DL '00 , pages 85 { 94 , 2000 .

[2] S. Auer , C. Bizer , G. Kobilarov, J. Lehmann , and Z. Ives. DBpedia: A Nucleus for a Web of Open Data . In ISWC , pages 11 { 15 . Springer, 2007 .

[3] M. Banko , M. J. Cafarella , S. Soderland , M. Broadhead , and O. Etzioni . Open Information Extraction from the Web . 2007 .

[4] M. Banko and O. Etzioni . Strategies for lifelong knowledge extraction from the web . In K-CAP '07 , pages 95 { 102 , 2007 .

[5] B. Borchers and J. Furman . A two-phase exact algorithm for MAX-SAT and weighted MAX-SAT problems . Journal of Combinatorial Optimization , 2 : 299 { 306 , 1997 .

[6] S. Brin . Extracting patterns and relations from the world wide web . In WebDB '98 , pages 172 { 183 , 1999 .

[7] P. DeRose , W. Shen , F. Chen , A. Doan , and R. Ramakrishnan . Building structured web community portals: a top-down, compositional, and incremental approach . In VLDB '07 , pages 399 { 410 , 2007 .

[8] D -Grid Initiative . http://www.d-grid.de/.

[9] E. Laure et al. Programming the Grid with gLite . In Computational Methods in Science and Technology , 2006 .

[10] H. Enke , M. Steinmetz , T. Radke , A. Reiser , T. Roblitz, and M. Hogqvist . AstroGrid-D: Enhancing Astronomic Science with Grid Technology . 2007 .

[11] O. Etzioni , M. Cafarella , D. Downey , S. Kok , A.-M. Popescu , T. Shaked , S. Soderland , D. S. Weld , and A. Yates . Web-scale information extraction in knowitall: (preliminary results) . In WWW '04 , pages 100 { 110 , 2004 .

[12] FinGrid - Financial Business Grid. http://www.fingrid.de/.

[13] I. Foster , C. Kesselman , and S. Tuecke . The Anatomy of the Grid - Enabling Scalable Virtual Organizations . International Journal of Supercomputer Applications , 15 : 2001 , 2001 .

[14] gLite - Lightweight Middleware for Grid Computing . http://glite.web.cern.ch/glite/.

[15] M. W. Ku ster, C. Ludwig, and A. Aschenbrenner. TextGrid: eScholarship und vernetzte Angebote . it - Information Technology, 51 ( 4 ): 183 { 190 , 2009 .

[16] H. Poon and P. Domingos . Joint inference in information extraction . In AAAI'07 , pages 913 { 918 . AAAI Press, 2007 .

[17] S. Sarawagi . Information extraction. Foundations and Trends in Databases , 1 ( 3 ): 261 { 377 , 2008 .

[18] W. Shen , A. Doan , J. F. Naughton , and R. Ramakrishnan . Declarative information extraction using datalog with embedded extraction predicates . In VLDB '07 , pages 1033 { 1044 , 2007 .

[19] A. Streit , D. Erwin , D. Mallmann , R. Menday , M. Rambadt , M. Riedel , M. Romberg , B. Schuller , and P. Wieder. UNICORE - From Project Results to Production Grids . In Grid Computing and New Frontiers of High Performance Processing , 2005 .

[20] F. M. Suchanek . Automated Construction and Growth of a Large Ontology . PhD thesis , Saarland University, 2009 .

[21] F. M. Suchanek , G. Ifrim, and G. Weikum. Combining linguistic and statistical analysis to extract relations from web documents . In KDD '06 , pages 712 { 717 . ACM, 2006 .

[22] F. M. Suchanek , G. Kasneci, and G. Weikum. YAGO : A Large Ontology from Wikipedia and WordNet . Web Semant., 6 ( 3 ): 203 { 217 , 2008 .

[23] F. M. Suchanek , M. Sozio , and G. Weikum. SOFIE : A Self-Organizing Framework for Information Extraction . In WWW 2009 , 2009 .

[24] D. Thain , T. Tannenbaum , and M. Livny . Distributed computing in practice: the Condor experience: Research Articles . Concurr. Comput. : Pract . Exper., 17 ( 2-4 ): 323 { 356 , 2005 .