=Paper=
{{Paper
|id=None
|storemode=property
|title=Wissensextraktion im Rahmen des Grids
|pdfUrl=https://ceur-ws.org/Vol-581/gvd2010_8_2.pdf
|volume=Vol-581
|dblpUrl=https://dblp.org/rec/conf/gvd/Metzger10
}}
==Wissensextraktion im Rahmen des Grids==
https://ceur-ws.org/Vol-581/gvd2010_8_2.pdf
Wissensextraktion im Rahmen des Grids
Steffen Metzger
Max-Planck-Institut für Informatik
Campus E1 4
Saarbrücken, Deutschland
smetzger@mpi-inf.mpg.de
Zusammenfassung gebildet, können aber auch nur dann gefunden werden, wenn
Moderne Netzwerke stellen immense Datensammlungen be- explizit mit dem richtigen Schlüsselwort nach ihnen gesucht
reit, so dass oft weniger das Beschaffen von Informatio- wird. Beispielsweise wird eine Schlüsselwortsuche nach dem
nen, als vielmehr das Herausfiltern der relevanten Essenz, Geburtsort von Albert Einstein zu der Anfrage “Einstein
den größten Aufwand darstellt. Hier können Methoden der Geburtsort” ein Dokument das lediglich den Satz “Einstein
Wissensextraktion helfen, essentielle Inhalte aus vorliegen- wurde in Ulm geboren” nicht als Ergebnis liefern. Eine ab-
den Daten als höherwertiges Wissen zu extrahieren und da- strakte Wissensrepräsentation dagegen kann solche unter-
mit konkrete Fragestellungen einfacher beantwortbar zu ma- schiedlichen Ausdrucksweisen vereinheitlichen und die Suche
chen. Grid Computing hat zum Ziel verteilte Ressourcen für nach den eigentlichen Inhalten so erleichtern. Zudem fällt die
alle Beteiligten effizient nutzbar zu machen. Bisherige Um- Suche nach Beziehungen über eine Schlüsselwortbasierte Su-
setzungen haben sich dabei primär auf Rechenleistung als che schwer. Sind z.B. alle Naturwissenschaftler gesucht, die
Ressource konzentriert. Um auch die im Grid vorliegenden in Ulm geboren wurden, lässt sich diese Beziehung schwer-
Daten sinnvoll nutzbar zu machen, bietet es sich an, das ent- lich als Schlüsselwortsuche formulieren. Zur Beantwortuntg
haltene Wissen zu extrahieren und in eine abstrakte Form einer solchen Suche bedarf es Hintergrundwissen zur Iden-
zu übertragen. Extraktionstechnologien können hierbei von tifikation von Naturwissenschaftlern und ihren Geburtsor-
der Gridinfrastruktur profitieren und so eine bessere Effizi- ten. Liegt solches Wissen z.B. in Ontologien vor, kann die
enz erreichen. Innerhalb dieser Arbeit wird ein generisches Fragestellung dagegen recht einfach als SPARQL Anfrage
Extraktionsframework vorgestellt, sich ergebende Probleme formuliert werden: “?x hatTyp Naturwissenschaftler . ?x ge-
bei der Übertragung in ein Gridumfeld aufgezeigt und erste borenIn Ulm”.
Schritte zur Anpassung dargelegt. Auf der anderen Seite zeigt sich zwar, dass Verfahren der
Wissensextraktion auf Texten durch Einsatz komplexerer
1. EINLEITUNG Sprachanalysemethoden deutlich verbesserte Ergebnisse er-
Mit der Entstehung von Computernetzwerken entstand auch zielen können (z.B. Deep Syntactic Analysis in LEILA[21]),
der Bedarf entfernte Ressourcen, wie z.B. Rechenleistung dies geht aber in der Regel auf Kosten der Laufzeit([20]), da
und Speicher, aber auch vorhandene Daten und Dienste, in diese Verfahren einen deutlich höheren Aufwand erfordern
den lokalen Arbeitsprozess einzubinden. Dieses Bestreben als beispielsweise relativ einfache Regeln auf Basis der Zei-
brachte das Grid Computing hervor, das darauf abzielt, die chenabfolge (z.B. Reguläre Ausdrücke).
vorhandenen Ressourcen in sogenannten virtuellen Organi- In der Kombination beider Technologien bietet sich hier
sationen für die jeweiligen Mitglieder zugänglich zu machen. also ein Synergieeffekt an. Einerseits liegen in den Grid-
Bisher konzentrieren sich diese Bemühungen primär auf ver- Communitys große Mengen an Daten vor, deren Inhalt auf
schiedene Aspekte zur verteilten Berechnung von Anwen- einem höheren Abstraktionslevel einheitlich und effizient
dungen, wie z.B. Scheduling, Workflow Management (UNI- durchsuchbar zur Verfügung gestellt werden soll. Anderer-
CORE[19], Condor[24]) und Zugriffssicherheit (Globus[13]). seits kann die Wissensextraktion von der verteilten Rechen-
Allerdings bietet sich, zur Nutzung von Synergien, eine Zu- leistung des Grids profitieren. Für die beteiligten Communi-
sammenarbeit auch auf Ebene der eigentlichen Inhalte an. tys ergibt sich der Vorteil, dass eine existierende Infrastruk-
Dazu gehört z.B. eine einheitliche globale Suche nach die- tur genutzt wird, um ihre Daten mit effizienten Methoden
sen Inhalten. Eine Schlüsselwortsuche auf den Daten selbst aufzuwerten und Zugriff auf Wissen anderer Communitys zu
stellt hierbei nur den kleinsten gemeinsamen Nenner dar. erhalten.
Die enthaltenen Informationen werden dabei vollständig ab- 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 Wissensex-
traktion, das in einem Grid-Projekt (WisNetGrid [14]) Ver-
wendung finden soll, vorgestellt. In Abschnitt 5 besprechen
wir letztlich offene Punkte bzw. mögliche Erweiterungen.
Copyright is held by the author/owner(s).
GvD Workshop’10, 25.-28.05.2010, Bad Helmstedt, Germany.
2. VERWANDTE ARBEITEN traktion mit Abgleich gegen existierendes Wissen, z.B. zur
Zur Realisierung von Gridinfrastrukturen sind verschiedene Bestimmung von Entitäten. Ein anderer Ansatz ([16]) nutzt
Middlewarekomponenten entstanden, die sich jeweils Aspek- Markov Logik um Entitäten auf Basis von Wahrscheinlich-
ten der verteilten Berechnung von Anwendungen (Jobs) im keiten zu identifizieren. Dem Ansatz des Lifelong Learning
Grid widmen. Während UNICORE[19] primär den Zugriff folgend verwaltet ALICE[4] eine Wissensbasis in Form einer
auf große Rechencluster über ein Grid anstrebt und hierfür Ontologie, die durch extrahierte Fakten regelmäßig erwei-
auch ein Job Workflow Management zur Verfügung stellt, tert wird. Allerdings gibt es dabei keine Mechanismen, die
widmete sich Condor[24] ursprünglich mehr der Vernetzung die Konsistenz der Ontologie sicherstellen. SOFIE[23] ver-
von Desktoprechnern, was durch die größere Unbeständig- eint Muster-basierte Wissensextraktion mit einer logischen
keit der beteiligten Knoten über ein Job Workflow Mana- Konsistenzprüfung und eignet sich daher insbesondere zur
gement hinaus ein Checkpoint System zur Wiederaufnah- fortwährenden Erweiterung einer Ontologie. Das angestreb-
me unterbrochener Grid Jobs hervorbrachte. Während beide te Extraktionsverfahren für die Anwendung im Grid basiert
Systeme den Datentransfer zu einem ausführenden Knoten daher auf der SOFIE Architektur.
im Grid und zurück erlauben, bieten Globus[13] und gLite
[9] weitergehendere Kontrolle über die Daten im Grid sowie 3. EXTRAKTIONSVERFAHREN
ein z.T. detaillierteres Rechtesystem. Auf dem abstrakten Level sind Muster generische Verall-
In Deutschland koordiniert die D-Grid-Initiative[8] (D-Grid) gemeinerungen bestimmter Ausdrucksformen von Wissen.
Grid-orientierte Projekte mit dem Ziel eine nachhaltige In Texten sind Muster also beispielsweise parametrisier-
Grid-Infrastruktur zu schaffen. Über die grundlegenden Ba- te Formulierungen die jeweils einen bestimmten Sachver-
sisdienste zur Einrichtung des Grids hinaus, sollen hierbei halt auf unterschiedlichen Objekten ausdrücken. Die For-
auch höhere Dienste etabliert werden. Die beteiligten aka- mulierung “Einstein kam in Ulm zur Welt” beispielsweise
demischen Communitys setzen sich dabei aus unterschied- beschreibt den Sachverhalt, dass Albert Einstein in Ulm
lichen Disziplinen, wie z.B. Linguistik (TextGrid[15]) und geboren wurde. Die beiden Komponenten ‘Einstein’ und
Astrophysik (AstroGrid[10]) zusammen, darüberhinaus sind ‘Ulm’ können dabei einfach ausgetauscht werden, um den-
jedoch auch kommerzielle Projekte (z.B. FinGrid[12]) einge- selben Sachverhalt zwischen einer anderen Person und ei-
bunden. Durch die Vielfalt der beteiligten Communitys, liegt nem anderen Ort auszudrücken. Ersetzen wir diese Kom-
eine große Datenheterogenität vor. Methoden der Wissens- ponenten also durch Variablen, erhalten wir das allgemei-
extraktion können genutzt werden, um diese Heterogenität
ne Muster X kam in Y zur Welt , welches eine Ausdrucks-
für den Nutzer zu überwinden und eine höherwertige Suche
auf dem vorhanden Wissen anzubieten. Allerdings bestehen form der geborenIn Relation darstellt. Tritt dieses Muster
umgekehrt natürlich auch besondere Anforderungen an die nun mit einer konkreten Variablenbesetzung auf, z.B. in der
verwendeten Extraktionsverfahren, z.B. kann eine Commu- Form Einstein kam in Ulm zur Welt , bezeichnen wir dies
nity darauf bestehen, dass extrahiertes Wissen in ihrem di- als Musterinstanz. Die gleiche Musterinstanz kann in ver-
rekten Einflussbereich verbleibt. schiedenen Dokumenten auftreten. Solche Vorkommen mit
Bezug zu einer Quelle bezeichnen wir als Mustervorkommen.
Verfahren zur Wissensextraktion versuchen aus konkre-
ten Informationen in Dateien abstrakte Fakten zu generie-
ren[17]. Beispielsweise kann aus der Aussage “Einstein kam
in Ulm zur Welt” das abstrakte Wissen, dass Albert Ein-
stein in Ulm geboren wurde (als Fakt ausgedrückt gebore-
nIn(AlbertEinstein,Ulm)) hergeleitet werden. Dazu muss al-
lerdings der mehrdeutige Ausdruck “Einstein” als eine Aus-
drucksform der eindeutigen Entität 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 Bei-
spielfakten in der Lage mit statistichen Methoden automa-
tisch textuelle Muster zu finden, die wahrscheinlich die zuge-
hörige Relation ausdrücken. Dieser Ansatz kann weiter ver- Figure 1: Beispiel der Musterbasierten Extraktion
bessert werden, indem bei der Wahl der Muster auch Ge-
genbeispiele berücksichtigt werden (siehe LEILA[21]). Wäh- Dieser Zusammenhang ist in Abbildung 1 skizziert. Die
rend diese Verfahren je darauf abzielen für eine gegebene Musterinstanz Albert Einstein kam in Ulm zur Welt wur-
Relation weitere Fakten zu finden, versucht z.B. TextRun- de hierbei in Dokument D1 gefunden, während in Doku-
ner[3] Fakten aller Relationen, die im Internet auftauchen, ment D2 eine Instanz des Musters X wurde geboren in Y
zu extrahieren. Allerdings wird hierbei keine Auflösung von vorliegt. Aus beiden Mustervorkommen lässt sich der Fakt
Mehrdeutigkeiten und Umwandlung auf Relationen durch- geborenIn(AlbertEinstein,Ulm) ableiten.
geführt. Liegen die Daten teilweise strukturiert vor, kann
das durch angepasste Extraktionsverfahren ausgenutzt wer- Generell lässt sich das Extraktionsverfahren in vier Schritte
den. So konzentrieren sich einige Ansätze z.B. auf eine Ex- unterteilen. Zuerst müssen Quelldateien auf Mustervorkom-
traktion aus Wikipedia ([22],[2]). In [18] wurde ein Frame- men untersucht werden. Anschließend werden diese Vorkom-
work zur deklarativen Extraktion basierend auf Datalog ein- men ausgewertet und potentielle Fakten aus den Muster-
geführt, welches zur Erzeugung von Portalen wie DBlife[7] vorkommen generiert. Im dritten Schritt werden diese po-
genutzt wurde. Das Modell erlaubt eine regelbasierte Ex- tentiellen Fakten mit der bestehenden Wissensbasis abgegli-
chen. Daraus ergibt sich eine optimale Menge an potentiellen Umgekehrt lässt sich auch das Erlernen neuer Fakten in eine
Fakten, die mit dem bestehenden Wissen in Einklang steht. Regel„fassen: «
Diese Fakten werden dann im letzten Schritt zur Wissensba- patternOcc(P,X,Y)
R2: ⇒R(X,Y)
sis hinzugefügt. Parallel zur Extraktion von Fakten, werden ∧ expresses(P,R)
auch eigenständig neue Muster für bereits bekannte Relatio-
nen erlernt. Ist beispielsweise bereits bekannt, dass Albert Bei beiden Regeln ignorieren wir hier, dass je die Entitäten,
Einstein in Ulm geboren wurde, und in einem Dokument die X und Y entsprechen, noch eindeutig aus den konkreten
beginnt ein Satz mit “Albert Einstein erblickte das Licht Worten identifiziert werden müssten. Dies kann ebenfalls als
der Welt in Ulm ...” kann daraus abgeleitet werden, dass Teil der Regel formuliert werden. Ebenso können weitere Re-
das Muster X erblickte das Licht der Welt in Y ein guter geln domainspezifisches Wissen kodieren, z.B. dass Personen
Kandidat für eine Ausdrucksform des Fakts geborenIn(X,Y) nur an einem Ort geboren werden können.
ist. Beide Lernverfahren werden dabei einer gemeinsamen
logischen Evaluierung unterzogen. Basierend auf logischen Werden Quelldaten bearbeitet, erzeugt jedes gefundene
Regeln und einer Menge von Fakten und Hypothesen, z.B. Mustervorkommen einen entsprechenden patternOcc Fakt.
über neue Muster, wird eine Zuweisung von Wahrheitswer- Zudem können wir davon ausgehen, dass bereits einige Fak-
ten zu den Hypothesen gesucht, so dass ein Maximum der ten gesuchter Relationen in der Ontologie vorhanden sind,
logischen Regeln erfüllt ist. z.B. weil sie bereits extrahiert wurden oder weil es sich um
die anfangs gegebenen Beispiele handelt. Weiterhin könnten
auch bereits Instanzen der expresses Relation bekannt sein.
Aussagen. Eine Aussage besteht aus einer Relation und Wann immer nun die Voraussetzungen einer Regel erfüllt
einer Liste von Entitäten. Jeder Aussage wird ein binärer sind, erzeugt diese Regel eine Hypothese aus der als Folge
Wahrheitswert zugeordnet, der in eckigen Klammern ange- angegebenen Aussage.
geben wird: Ist z.B. patternOcc( X kam in Y zur Welt ,“Einstein”,“Ulm”)
geborenIn(AlbertEinstein,Ulm) [1]
und geborenIn(AlbertEinstein,Ulm) gegeben, wird die
Eine Aussage mit Wahrheitswert 1 bezeichnen wir als Fakt, Hypothese expresses( X kam in Y zur Welt ,geborenIn) [?]
während eine Aussage mit unbekanntem Wahrheitswert ei-
durch Regel R1 erzeugt.
ne Hypothese darstellt. Ist kein Wahrheitswert angegeben,
Ist die Bearbeitung der Quelldaten abgeschlossen, muss ent-
handelt es sich um einen Fakt.
schieden werden, welche Hypothesen als wahre Fakten be-
trachtet und somit in die Ontologie aufgenommen werden
Regeln. Die logischen Regeln basieren auf Literalen. Ein sollen. Hierzu wird eine Wahrheitszuweisung an die Hypo-
Literal ist eine Aussage ohne Wahrheitswert, bei der sowohl thesen ermittelt, die ein Maximum an Regelinstanzen erfüllt.
die Relation als auch die Entitäten durch Variablen ersetzt D.h. einzelne Regeln dürfen grundsätzlich gebrochen wer-
werden können. Eine Regel ist eine logische Formel erster den. Wenn z.B. bereits in der Ontologie bekannt ist, dass
Stufe basierend auf Literalen. Zur Instantiierung einer sol- eine generierte Hypothese nicht wahr sein kann, weil das
chen quantifizierten Regel, wird jede Variable an all ihren Gegenteil bereits wahr ist, muss die entsprechende Regel ge-
Vorkommen durch die gleiche Entität ersetzt. Grundsätzlich brochen werden können, ohne dass deshalb der komplette
müssen Regeln auf allen möglichen Instantiierungen gelten, Vorgang fehlschlägt.
um gültig zu sein. Üblicherweise wird eine Person beispiels- Um eine solche Wahrheitszuweisung zu finden, kann die
weise nur an einem Ort geboren. Dies lässt sich vereinfacht Problemstellung auf ein maximum satisfiability (MAX-SAT)
wie folgt als logische Regel ausdrücken: Problem ([5]) reduziert werden. Das MAX-SAT Problem ba-
geborenIn(X,Y) ⇒¬geborenIn(X,Z) siert auf Klauseln:
Basisregeln. Im folgenden wollen wir zwei stark vereinfach- Definition 3.1 (Klausel). Eine Klausel ist eine Dis-
te Basisregeln vorstellen, die dem Erlernen neuer Fakten und junktion X1 ∨ ... ∨ Xn wobei für alle Xi∈{1,...,n} gilt: Xi ist
möglicher neuer Muster entsprechen. Hierzu bedienen wir entweder eine Variable oder eine negierte Variable.
uns zweier spezieller Relationen:
Definition 3.2 (MAX-SAT Problem). Gegeben ei-
1. patternOcc(P,A,B ) besagt, dass das Muster P mit den
ne Menge von Klauseln C1 , ..., Cn über m Variablen. Fin-
Instanzen A und B (z.B. P= X wurde geboren in Y de eine Wahrheitszuweisung für die Variablen, so dass die
mit X=A=“Einstein” und X=B=“Ulm”) vorgekommen Anzahl erfüllter Klauseln maximal ist.
ist. Korrekterweise müssten wir hier noch auf das Do-
kument, in dem die Musterinstanz gefunden wurde,
eingehen. Darauf verzichten wir an dieser Stelle. Das MAX-SAT Problem ist ein bekanntes NP-vollständiges
Problem, für das exakte Algorithmen sowie Annäherungs-
2. expresses(P,R) besagt, dass das Muster P eine Aus- verfahren zur Lösung existieren ([5]). Zur Übertragung in
drucksform der Relation R (also z.B. geborenIn) ist. ein MAX-SAT Problem müssen die Regeln per Rewriting in
Klauseln umgewandelt werden und die enthaltenen Aussa-
gen bzw. ihre Wahrheitswerte bilden die Variablen.
Das Erlernen neuer Muster bzw. ihrer Bedeutung kann dann
vereinfacht wie folgt als logische «
Regel ausgedrückt werden:
Gewichtete Regeln. In dem vorgestellten Ansatz werden
„
patternOcc(P,X,Y)
R1: ⇒expresses(P,R)
∧ R(X,Y) alle Regeln gleichbehandelt. Allerdings können einige Regeln
wichtiger als andere sein. Dies spielt z.B. eine Rolle, wenn gehend sprachunabhängigen Methoden bilden, die bei Spra-
unterschiedlich wahrscheinliche Zuordnungen von Wörtern chen für die noch kein höherwertiges Analysemodul vorliegt,
zu einzelnen Entitäten über Regeln abgebildet werden. Zu- zum Einsatz kommt.
dem kann so existentes Wissen stärker gewichtet werden als
neu erlerntes. Das Problem der Zuordnung von Wahrheits- Verteilte Daten - Aufspaltung des Frameworks. Eine
werten zu den Hypothesen unter Beachtung einer Regelge- Grundeigenschaft des Grids ist die verteilte Datenlagerung.
wichtung kann nicht in ein MAX-SAT Problem überführt Extrahiertes Wissen dagegen sollte zentral in einer Ontolo-
werden. Stattdessen kann es aber in ein gewichtetes MAX- gie vorgehalten werden, um eine effiziente Suche zu erlauben
SAT Problem ([5]) überführt werden. Die Übertragung in und die Konsistenz bei (manuellen) Änderungen sicherstel-
ein gewichtetes MAX-SAT Problem, sowie ein effizienter Al- len zu können. Dabei können einzelne Communitys eigene
gorithmus zur Lösung eines solchen Problems wird in [23] Ontologien unabhängig voneinander verwalten wollen, um
diskutiert. Auf beides gehen wir hier nicht weiter ein. Im die Kontrolle über ‘ihr Wissen’ zu behalten. Es wäre nun
Grunde kann die Hypothesenbewertung mit einem beliebi- sehr ineffizient alle Daten zur Extraktion zu der jeweiligen
gen Ansatz gelöst werden, es muss lediglich eine Zuweisung zentralen Stelle, an der die entsprechende Ontologie vorge-
von Wahrheitswerten für die aufgestellten Hypothesen ge- halten wird, zu übertragen. Einerseits sollte also die Analy-
funden werden, die möglichst viele Regeln erfüllt und dabei se der vorliegenden Daten möglichst lokal am Lagerort der
eine Gewichtung erlaubt. Markov Logik böte z.B. einen an- Daten geschehen. Andererseits muss die Extraktionskompo-
deren Ansatz. nente das extrahierte Wissen in die Ontologie übertragen
und dabei sicherstellen, dass die Konsistenz gewahrt bleibt.
Hier bietet sich eine Zweiteilung des Extraktionsverfahrens
4. UMSETZUNG IM GRIDUMFELD in einen Extraktionsclient und einen Extrakionsmaster an.
Aus dem Einsatz im Grid ergeben sich besondere Anforde- Ersterer übernimmt das lokale Analysieren von Daten und
rungen an die Wissensexktraktion. Auf einige wollen wir im extrahiert Mustervorkommen, letzterer aggregiert die gefun-
folgenden kurz eingehen. denen Mustervorkommen, generiert daraus Hypothesen und
fügt letztlich neue Erkenntnisse zentral in die Ontologie ein.
Heterogene Daten und Domänen. Durch die Zielsetzung So müssen nicht die eigentlichen Daten, sondern lediglich er-
völlig unterschiedliche Communitys über eine gemeinsame kannte Mustervorkommen übertragen werden. Dabei kann
Gridarchitektur zu verknüpfen und darüber gegenseitigen die Extraktion auch über das Grid verteilt erfolgen. So kön-
Zugriff auf in vorhandenen Daten enthaltenes Wissen zu er- nen z.B. zur Textanalyse auch rechenintensivere komplexe
möglichen, ergibt sich eine heterogene Menge an Daten aus Sprachanalysemethoden eingesetzt werden.
denen abstraktes Wissen extrahiert werden soll. Das bedeu-
tet einerseits dasss unterschiedliche Formatierungen struk- Konfidenzen. Aufgrund der generischen Gestaltung sowie
turierter Inhalte, wie z.B. Tabellen, vorliegen, aber auch fehlerhafter Quelldokumente, kann es vorkommen, dass Fak-
dass ganz unterschiedliches Hintergrundwissen vonnöten ist, ten extrahiert werden, die nicht als wahr anzusehen sind.
um sinnvoll abstrakte Fakten aus den Daten verschiedener Verschiedene Muster bzw. Mustertypen können als unter-
Communitys zu generieren. Hier bietet das besprochene Ex- schiedlich sicher betrachtet werden. Beispielsweise ist ein
traktionsframework gute Anpassungsmöglichkeiten. Einer- von einer Community manuell vorgegebenes Muster für ih-
seits können Muster generisch anhand von Beispielwissen re strukturierten Daten, z.B. ein Mapping von Spalten- und
automatisch erlernt werden, so dass sich die Extraktion in- Zeilenattribut in einer Tabelle auf eine Relation, im Allge-
krementell gestalten lässt. Andererseits können Nutzer aber meinen als sicherer anzusehen als ein selbsterlerntes textu-
auch mit entsprechenden Tools direkt Muster vorgeben oder elles Muster. Da die Nutzer im D-Grid aus unterschiedli-
bei entsprechend modularer Implementierung einzelne Kom- chen Fachrichtungen kommen und daher bei Community-
ponenten des Frameworks für ihre Belange austauschen. Da- übergreifenden Nachforschungen mit Fakten aus ihnen frem-
durch kann z.B. ein alternatives Verfahren zur Verarbei- den Fachbereichen umgehen müssen, sollte der Grad der Si-
tung domainspezifischer strukturierter Daten hinzugefügt cherheit einzelner Fakten ersichtlich sein. Hierzu wird ein
werden, dessen Muster sich auf die spezielle Struktur be- Konfidenzwert für jeden Fakt berechnet, der das Vertrauen
ziehen. Ebenso können auf diese Weise gänzlich andere In- darin repräsentiert, dass der Fakt korrekt extrahiert wur-
halte, wie z.B. Audiodaten oder grafische Darstellungen, un- de. Dieser Wert basiert auf dem Vertrauen in die Qualität
tersucht werden. Unterschiedliche Mustertypen für verschie- der Quelle und in die Genauigkeit des benutzten Musters.
dene Datenanalysemodule lassen sich parallel verwalten, es D.h. es existieren Konfidenzwerte für Muster, Quellen und
muss lediglich die Information mitgeführt werden, welches Fakten. Ihre Abhängigkeiten werden in Abbildung 2 skiz-
Muster zu welchem Analysemodul gehört. Ebenso kann do- ziert. Generell basiert der Konfidenzwert eines Fakts auf al-
mainspezifisches Vorwissen in Form von logischen Regeln len Mustervorkommen, die ihn bestätigen, bzw. dem durch
übergeben werden. Alternativ kann Vorwissen in Form von sie generierten Vertrauen. Ein Mustervorkommen eines ex-
bestehenden Ontologien zur Verfügung gestellt werden, die akten und sehr wohl erprobten Musters in einer vertrauens-
dann in den Reasoningprozess eingebunden werden. Die Da- würdigen Quelle lässt den Fakt glaubwürdig erscheinen. Ist
tenheterogenität im Grid beschränkt sich zudem nicht nur der einzige Beleg für den Fakt jedoch ein als unsicher einge-
auf die Dateninhalte und Formate, sondern auch auf die stuftes Muster, das auf einer unglaubwürdigen Quelle gefun-
Sprache der Texte. D.h. das Extraktionsverfahren muss an den wurde, so wird der Fakt wenig glaubwürdig erscheinen.
verschiedene Sprachen, zum Einsatz im D-Grid insbesonde- Findet sich beispielsweise der Satz “Albert Einstein erhielt
re an Deutsch, angepasst werden bzw. einfach an weitere seinen Nobelpreis für ...” auf der Wikipediaseite über Al-
Sprachen anpassbar sein. Einen breiten Basisansatz kann bert Einstein, so ist dies ein sehr eindeutiger Beleg für den
hier eine einfache leicht anpassbare Textanalyse mit weit-
[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
Figure 2: Beispiel: Vertrauensfluß der zum Gesamt- Computational Methods in Science and Technology,
vertrauen in einen Fakt führt 2006.
[10] H. Enke, M. Steinmetz, T. Radke, A. Reiser,
T. Röblitz, and M. Högqvist. AstroGrid-D: Enhancing
Fakt hatAuszeichnungErhalten(AlbertEinstein,Nobelpreis).
Astronomic Science with Grid Technology. 2007.
Eng damit verknüpft ist das Einarbeiten von Nutzerfeed-
back. Wird ein extrahierter Fakt von einem Nutzer als feh- [11] O. Etzioni, M. Cafarella, D. Downey, S. Kok, A.-M.
lerhaft erkannt, sollte dieses Wissen genutzt werden, um Popescu, T. Shaked, S. Soderland, D. S. Weld, and
für die Zukunft hinzuzulernen. Das kann beispielsweise über A. Yates. Web-scale information extraction in
eine Anpassung der Konfidenz in das entsprechende Mus- knowitall: (preliminary results). In WWW ’04, pages
ter geschehen. Ein weiterer Schritt wäre die Konfidenzwerte 100–110, 2004.
auch direkt in das Extraktionsverfahren einzubinden, z.B. [12] FinGrid - Financial Business Grid.
zur Regelgewichtung. Hinzu kommt, dass die gegenwärtige http://www.fingrid.de/.
Modellierung der Extraktion eingeschränkt ist. So ist es bei- [13] I. Foster, C. Kesselman, and S. Tuecke. The Anatomy
spielsweise nicht ohne weiteres möglich zeitliche oder örtliche of the Grid - Enabling Scalable Virtual Organizations.
Einschränkungen zu erkennen bzw. mit einem Fakt zu ver- International Journal of Supercomputer Applications,
knüpfen. Ebenso können z.B. kausale Zusammenhänge nicht 15:2001, 2001.
erkannt werden. Die Modellierung von Meinungen und Wer- [14] gLite - Lightweight Middleware for Grid Computing.
tungen, die sich ja unter Umständen widersprechen können, http://glite.web.cern.ch/glite/.
wird ebenso noch nicht berücksichtigt. [15] M. W. Küster, C. Ludwig, and A. Aschenbrenner.
TextGrid: eScholarship und vernetzte Angebote. it -
Information Technology, 51(4):183–190, 2009.
5. ZUSAMMENFASSUNG & AUSBLICK [16] H. Poon and P. Domingos. Joint inference in
In der vorliegenden Arbeit wurde ein Überblick über aktuel-
information extraction. In AAAI’07, pages 913–918.
le Verfahren der Wissensextraktion gegeben und ein generi-
AAAI Press, 2007.
sches Framework zur Wissensextraktion vorgestellt. Darauf
[17] S. Sarawagi. Information extraction. Foundations and
aufbauend wurden einige Aspekte diskutiert, die es bei ei-
Trends in Databases, 1(3):261–377, 2008.
ner Übertragung des Extraktionsverfahrens in ein Gridum-
feld zu beachten gilt. Für einige dieser Problemstellungen [18] W. Shen, A. Doan, J. F. Naughton, and
wurden erste Lösungsansätze entlang des vorgestellten Fra- R. Ramakrishnan. Declarative information extraction
meworks aufgezeigt. Im weiteren Verlauf der Forschungsar- using datalog with embedded extraction predicates. In
beit müssen die noch offenen Problemstellungen weiterge- VLDB ’07, pages 1033–1044, 2007.
hend analysiert und vollständige Lösungen in Form eines [19] A. Streit, D. Erwin, D. Mallmann, R. Menday,
lauffähigen Systems umgesetzt werden. Dieses wird dann M. Rambadt, M. Riedel, M. Romberg, B. Schuller,
an die Bedürfnisse zweier Testcommunitys innerhalb von D- and P. Wieder. UNICORE - From Project Results to
Grid angepasst und anschließend in diesem Rahmen evalu- Production Grids. In Grid Computing and New
iert werden. Frontiers of High Performance Processing, 2005.
[20] F. M. Suchanek. Automated Construction and Growth
of a Large Ontology. PhD thesis, Saarland University,
6. LITERATUR 2009.
[1] E. Agichtein and L. Gravano. Snowball: extracting [21] F. M. Suchanek, G. Ifrim, and G. Weikum. Combining
relations from large plain-text collections. In DL ’00, linguistic and statistical analysis to extract relations
pages 85–94, 2000. from web documents. In KDD ’06, pages 712–717.
[2] S. Auer, C. Bizer, G. Kobilarov, J. Lehmann, and ACM, 2006.
Z. Ives. DBpedia: A Nucleus for a Web of Open Data. [22] F. M. Suchanek, G. Kasneci, and G. Weikum. YAGO:
In ISWC, pages 11–15. Springer, 2007. A Large Ontology from Wikipedia and WordNet. Web
[3] M. Banko, M. J. Cafarella, S. Soderland, Semant., 6(3):203–217, 2008.
M. Broadhead, and O. Etzioni. Open Information [23] F. M. Suchanek, M. Sozio, and G. Weikum. SOFIE: A
Extraction from the Web. 2007. Self-Organizing Framework for Information
[4] M. Banko and O. Etzioni. Strategies for lifelong Extraction. In WWW 2009, 2009.
knowledge extraction from the web. In K-CAP ’07, [24] D. Thain, T. Tannenbaum, and M. Livny. Distributed
pages 95–102, 2007. computing in practice: the Condor experience:
[5] B. Borchers and J. Furman. A two-phase exact Research Articles. Concurr. Comput. : Pract. Exper.,
algorithm for MAX-SAT and weighted MAX-SAT 17(2-4):323–356, 2005.
problems. Journal of Combinatorial Optimization,
2:299–306, 1997.