History: DanielKinzler Chapter 4: Ablauf

Source of version: 1 (current)

4. Ablauf Wiki-Text Analyse Ressourcen Verarbeitung Lok. Konzepte Zusammenf. Glob. Konzepte Export Thesaurus Abb. 4.1: Transformationen Das Vorgehen von WikiWord lässt sich als eine Folge von Datentransformationen betrachten: In Abb. 4.1 ist eine Aneinanderreihung von Datenmodellen und Verarbeitungsschritten dargestellt, in der jeweils ein Transformationsschritt die Daten von einem Modell in ein anderes überführt1. Die Implementation von WikiWord folgt grob dieser Struktur (.7.1), in der konkreten Umsetzung wurden allerdings einige der Schritte verschachtelt und parallelisiert (.7.2). Die einzelnen Transformationen sowie die resultierenden Datenmodelle sind im Folgenden beschrieben. 4.1. Analyse von Wiki-Text Die erste Transformation ist die Analyse des Wiki-Textes (.1.2) aus dem XML-Dump (vergleiche [WM:DOWNLOAD, MW:XML]). Hierbei werden die relevanten Informationen aus dem Wiki-Text extrahiert und in das Ressourcenmodell überführt, das die Wiki-Seite repräsentiert und direkten Zugriff auf Eigenschaften dieser Seite bietet. Dabei entfällt ein Großteil des textlichen Inhalts, die Seite wird als eine ungeordnete Sammlung von Features wie Wiki-Links, Kategorien, Vorlagen und so weiter betrachtet. Das Ressourcenmodell bietet insbesondere Zugang zu folgenden Eigenschaften der Wiki-Seite: • der Titel der Seite, sowie der Namensraum, zu dem die Seite gehört. 1die grafische Aufteilung in mehrere Spalten erfolgt lediglich aus Platzgründen. 4. Ablauf 26 • der Text der Seite, in verschiedenen Verarbeitungsstufen, vom unveränderten Wiki-Text bis zu reinem Fließtext ohne Markup, siehe .8.3. • alleWiki-Links, also alleWiki-Seiten, auf die diese Seite verweist, mitsamt dem Link-Text jedes Verweises. Der Mechanismus zur Extraktion der Wiki-Links ist in .8.7 beschrieben. MancheWiki-Links haben eine spezielle Semantik (siehe .A.3) und werden daher auch von WikiWord gesondert interpretiert. Solche besonderen Wiki-Links definieren: – die Kategorien, denen die Seite zugeordnet ist. – die Language-Links, die auf der Seite definiert sind. • alle Abschnitte (Überschriften) der Seite. • die Vorlagen, die auf der Seite verwendet werden, samt den Parametern ihrer Verwendung (.A.5). Das Verfahren, mit dem die Vorlagen extrahiert werden, ist in .8.4 beschrieben. Diese Informationen werden größtenteils durch einfaches Pattern-Matching auf Basis des Wiki- Textes gewonnen. Auf Grund dieser Basisinformationen werden (ebenfalls imWesentlichen durch Pattern-Matching) weitere, speziellere Eigenschaften bestimmt: • der Typ der Seite. Diese Eigenschaft bestimmt, wie die Seite weiter verarbeitet wird. Mögliche Typen von Seiten sind: Artikel, Weiterleitung, Begriffsklärung, Liste sowie Kategorie. Details dieser Klassifikation sind in .8.5 beschrieben. • der Typ des Konzeptes, das die Seite beschreibt, falls sie ein Artikel ist. Diese Klassifikation hat keinen Einfluss auf die weitere Verarbeitung der Daten, kann aber bei der Verwendung des Thesaurus nützlich sein, insbesondere für die Aufgabe der Named Entity Recognition. Mögliche Typen von Konzepten sind: Ort, Person, Organisation, Name, Zeitpunkt, Zahl, Lebensform und sonstige. Details der Konzeptklassifikation sind in .8.6 beschrieben. • eine Menge von Termen, die als Bezeichnung für das Konzept direkt aus der Seite selbst, insbesondere aus ihrem Titel, abgeleitet werden können (für Details, siehe .8.9). • der erste Satz des Textes der Seite, zur Verwendung als Definition (Glosse) für das Konzept, das der Artikel beschreibt. Für das Verfahren zur Extraktion des ersten Satzes, siehe .8.8. • Bedeutungslinks, also Wiki-Links auf einer Begriffsklärungsseite, die auf eine der möglichen Bedeutungen des zu klärenden Begriffs zeigen. Der Algorithmus zur Extraktion von Bedeutungslinks ist in .8.10 beschrieben. • das Ziel der Weiterleitung, falls die Seite eine Weiterleitung ist. Die verwendeten Muster zur Erkennung bestimmter Informationen im Wiki-Text sind zum Teil Wiki-spezifisch. Zu beachten ist, dass sie zum größten Teil nicht ad hoc bestimmt wurden, sondern die vorgegebene Syntax des Wiki-Markups (.A) oder explizite Konventionen und Richtlinien der einzelnen Wiki-Projekte nachbilden (vergleiche [WP:ARTIKEL, WP:KAT, WP:BKL]). Die Verfahren, die verwendet werden werden, um die einzelnen Eigenschaften der Wiki-Seite zu bestimmten, wird in .8 beschrieben. Das Ressourcenmodell selbst ist in .D.1 definiert. 4. Ablauf 27 4.2. Aufbau des lokalen Datenmodells Concept Term meaning broader (a) Relationen A B C D a b c d e f g h (b) Struktur Abb. 4.2: Datenmodell Die zweite Transformation ist die Verarbeitung der Informationen aus dem Ressourcenmodell, also der Import in das lokale Datenmodell (das Konzeptmodell). In diesem Schritt werden die Informationen aus der Wikipedia als Elemente eines Thesaurus interpretiert (.9.1). Das lokale Datenmodell definiert die Struktur eines monolingualen, konzeptorientierten Thesaurus. Konkrete lokale Datensätze, also konkrete monolinguale Thesauri, werden in dieser Struktur gespeichert. Das Datenmodell ist ein Term-Konzept-Netzwerk (Abb. 4.2), es enthält Beziehungen zwischen Termen und Konzepten (die Bedeutungsrelation) und zwischen verschiedenen Konzepten (zum Beispiel Subsumtion oder Verwandtheit), wie in Abb. 4.2(a) dargestellt. Beziehungen zwischen Termen ergeben sich implizit. Dieses Modell ähnelt den Strukturen, die in der Literatur für ähnliche Zwecke vorgeschlagen wurden, insbesondere z. B. in [GREGOROWICZ UND KRAMER (2006)] und anderen Arbeiten, die in .2.4 vorgestellt wurden. Die Umsetzung dieses Modells als Schema für ein relationales Datenbanksystem ist in .C.1 beschrieben. Im Einzelnen besteht das Modell aus den folgenden Elementen: Terme: Terme (in Abb. 4.2(b) als Kreise dargestellt) sind lexikalische Einheiten: Wörter, Wortformen, Wortgruppen, Phrasen, Namen und so weiter. Jeder Term existiert nur einmal in einem Datensatz (also höchstens einmal pro Sprache). Terme sind Bezeichnungen für Konzepte. Konzepte: Konzepte (in Abb. 4.2(b) eckige Kästchen) sind logische Einheiten: sie repräsentieren (abstrakte oder konkrete) Dinge. Konzepte sind Bedeutungen von Termen. Zu jedem Konzept werden neben seiner Identität weitere Eigenschaften gespeichert, unter anderem ein Name zur Anzeige in einer Benutzerschnittstelle und der Typ des Konzeptes (wie oben im Abschnitt über das Ressourcenmodell beschrieben), sowie weitere sekundäre Eigenschaften wie ein IDF-Wert (.9.3). Bedeutungsrelation: Die Bedeutungsrelation (in Abb. 4.2(b) als durchgezogene Linien dargestellt) verbindet Terme und Konzepte, zum Beispiel die Terme a, b und c mit Konzept A. Dabei können beliebig viele Terme einem Konzept und beliebig viele Konzepte einem 4. Ablauf 28 Term zugeordnet sein. Die Bedeutungsrelation dient der Überbrückung der Semantic Gap zwischen dem Text als Folge von Wörtern und demWissen über Konzepte (siehe dazu auch [SUCHANEK U. A. (2007)] und wieder [GREGOROWICZ UND KRAMER (2006)]). Die Bedeutungsrelation ist gewichtet, konkret wird angegeben, wie oft welche Bezeichnung für welches Konzept verwendet wurde. Die gepunkteten Verbindungen in der Abbildung ergeben sich implizit aus der Bedeutungsrelation: Sie zeigt Synonymie zwischen zwei Termen, die beide über die Bedeutungsrelation mit demselben Konzept verbunden sind (zum Beispiel a und b wegen ihrer Verbindung zu A) und Homonymie zwischen Konzepten, die über die Bedeutungsrelation mit demselben Term verbunden sind (zum Beispiel zwischen A und C wegen ihrer Verbindung zu b und c)2. Subsumtionsrelation: Die Subsumtionsrelation (in Abb. 4.2(b) als Pfeil dargestellt) verbindet allgemeinere mit spezielleren Konzepten. Sie ist irreflexiv und antisymmetrisch, sowie konzeptionell transitiv, und bildet auf der Menge der Konzepte einen gerichteten azyklischen Graphen. Idealerweise (aber nicht notwendigerweise) sind alle Konzepte von einer einzigen „Wurzel“ aus erreichbar. Die konkrete Semantik der Subsumtion bleibt unbestimmt, die Relation beinhaltet so unterschiedliche Beziehungen wie Abstraktion (subtype), Instanziierung (is-a), Aggregation (part-of ) und gelegentlich auch Attribution (property-of ); siehe dazu [VOSS (2006), PONZETTO UND STRUBE (2007B), HAMMW¨OHNER (2007)] sowie weitere Arbeiten, die in .2.4 erwähnt wurden. Diese Relation entspricht der Hyponymiebeziehung zwischen Termen, also der BT/NT-Beziehung nach ISO [ISO:2788 (1986)]. Verwandtheit und Ähnlichkeit: Die semantische Verwandtheit und Ähnlichkeit von Konzepten (in Abb. 4.2(b) eine gestrichelte Linie) ist eine symmetrische Beziehung. Sie ist unter anderem für die automatische Disambiguierung von Termen sowie für die Aufgabe der Query Expansion nützlich (vergleiche dazu die Arbeiten, die in .2.3 vorgestellt wurden, insbesondere [ZESCH U. A. (2007B)] und [STRUBE UND PONZETTO (2006)]). Lokale Datensätze werden in einer relationalen Datenbank abgelegt (siehe .C.1), für die programmatische Verwendung einzelner Konzepte gibt es aber auch eine objektorientierte Repräsentation als Transferobjekte der Datenzugriffsschicht (siehe .C.3). Jedes Konzept wird als Objekt dargestellt, das Zugriff auf die Eigenschaften des Konzeptes bietet, unter anderem auf alle Bezeichnungen für das Konzept sowie auf verwandte und untergeordnete Konzepte (.D.2). Die Beziehungen des lokalen Datenmodells werden aus dem Ressourcenmodell aufgebaut, das heißt, die in den einzelnen Ressourcen (Wiki-Seiten) enthaltenen Informationen werden als Beziehungen im lokalen Datenmodell (also im Thesaurus) interpretiert und dann als solche gespeichert. Insbesondere werden folgende Interpretationen vorgenommen: • Seiten, die keineWeiterleitungen, Begriffsklärungen, Listen, Kategorien oder andere besondere Seiten sind, werden als Artikel betrachtet, das heißt, es wird angenommen, dass sie genau ein Konzept beschreiben. Entsprechend wird für jeden Artikel ein Konzept im lokalen Datensatz angelegt, mit dem Konzepttyp, den das Ressourcenmodell für diese Seite 2Der Übersichtlichkeit halber wurden nicht alle Beziehungen, die sich so ergeben, in der Abbildung dargestellt. 4. Ablauf 29 bestimmt hat; das entspricht dem Vorgehen in der Literatur, wie in den Arbeiten in .2.3 und .2.4 beschrieben. • die Subsumtionsrelation wird direkt aus den Kategorien abgeleitet, denen eine Seite zugeordnet ist. Dabei wird nicht zwischen Kategorieseiten und Artikeln unterschieden, das heißt, Kategorien sind ebenfalls einfach Konzepte (.9.1). Auch das entspricht im Wesentlichen dem, was laut .2.4 das übliche Vorgehen ist. • die Verwandtheit von Konzepten wird aufgrund von Querverweisen (Wiki-Links) zwischen Artikeln bestimmt: wenn zwei Artikel sich gegenseitig über Wiki-Links referenzieren, wird davon ausgegangen, dass die Konzepte, die diese Artikel beschreiben, miteinander verwandt sind [GREGOROWICZ UND KRAMER (2006)], siehe .9.1.3. • die Ähnlichkeit von Konzepten wird über die Language-Links bestimmt: wenn zwei Artikel über Language-Links denselben Artikel in einer anderen Sprache referenzieren, so werden die Konzepte, die diese beiden Artikel beschreiben, als ähnlich angesehen. Der Grund ist, dass Language-Links immer auf ähnliche (oder, idealerweise, äquivalente) Artikel verweisen [WP:INTERLANG], und die Ähnlichkeitsbeziehung als transitiv und symmetrisch betrachtet wird. Language-Links wurden in [HAMMW¨OHNER (2007B)] untersucht, der Ansatz, sie zur Bestimmung von semantischer Ähnlichkeit zu verwenden, scheint jedoch noch nicht verfolgt worden zu sein. • die Bezeichnungen (Terme) für ein Konzept werden aus einer Vielzahl von Quellen bestimmt, unter anderem: – aus dem Titel des Artikels, sowie der Verwendung des Magic Words DISPLAYTITLE. Letzteres wurde in der Literatur bislang nicht betrachtet. – aus den Titeln von Weiterleitungen, die auf den Artikel verweisen. Weiterleitungsseiten werden von so gut wie allen Arbeiten zur Struktur von Wikipedia betrachtet, vergleiche .2.3 und .2.4. – aus den Titeln von Begriffsklärungsseiten, die auf den Artikel verweisen. Begriffsklärungsseiten werden in der Literatur ebenfalls häufig berücksichtigt, vergleiche z. B. [PONZETTO UND STRUBE (2007C)]. – aus dem Link-Text von Wiki-Links, die auf den Artikel verweisen. Diese Information wurde bei der Analyse der Wikipedia bislang kaum genutzt (mit der Ausnahme von [MIHALCEA (2007)] sowie einigen Arbeiten zur Named Entity Recognition, siehe .2.6), obwohl sie für das Information Retrieval sehr wertvoll sein kann (vergleiche [EIRON UND MCCURLEY (2003), KRAFT UND ZIEN (2004)]). – aus Sort-Keys, die bei der Kategorisierung des Artikels angegeben wurden, sowie der Verwendung des Magic Words DEFAULTSORT. Diese Quellen für alternative Bezeichnungen wurden in der Literatur bisher nicht untersucht. Die Interpretation von Informationen aus dem Wiki-Text ist in .9.1 näher beschrieben. Nach dem Import der Daten aus den einzelnen Seiten der Wikipedia findet eine Nachbereitung statt (.9.1.3). Dabei werden insbesondere Weiterleitungen und Kategorisierungs-Aliase aufgelöst (siehe .9.1.3 und .9.1.2) sowie die Verwandtheit und Ähnlichkeit von Konzepten berechnet (.9.1.3). Das Ergebnis ist ein lokaler Datensatz, der einen monolingualen Thesaurus repräsentiert. 4. Ablauf 30 4.3. Zusammenführen Die dritte Transformation ist das Zusammenführen der einzelnen lokalen Datensätze zu einem globalen Datensatz: Gruppen von untereinander ähnlichen Konzepten aus unterschiedlichen Sprachen werden zu jeweils einem sprachunabhängigen Konzept vereinigt. Eine solche Methode zum Aufbau eines multilingualen Thesaurus wurde in den eingangs erwähnten Arbeiten nicht beschrieben. Das globale Datenmodell enthält vor allem Informationen darüber, welche Konzepte aus den einzelnen sprachspezifischen Datensätzen zu einem sprachunabhängigen Konzept zusammengefasst wurden und wie die Beziehungen zwischen den lokalen Konzepten auf die globalen Konzepte abgebildet wurden (siehe .C.1). Zusammen mit den lokalen Datensätzen, auf die er sich bezieht, bildet der globale Datensatz eine Kollektion, die einen multilingualen Thesaurus repräsentiert. Jedes Konzept im globalen Datensatz ist eine Menge von lokalen Konzepten, die aus jeder Sprache (höchstens) ein Konzept enthält. Sprachspezifische Eigenschaften (insbesondere Terme und Glossen) werden in dem globalen Datensatz nicht noch einmal abgelegt — statt dessen werden sie bei Bedarf dem betreffenden lokalen Datensatz entnommen. Die Hauptaufgabe beim Aufbau des globalen Datensatzes ist es also, Gruppen von Konzepten aus unterschiedlichen Sprachen (also lokalen Datensätzen) zu finden, die sich möglichst ähnlich sind, bzw. idealerweise zueinander äquivalent. Dabei ist die unter Umständen sehr unterschiedliche Granularität und Abdeckung der Wikipedias in den einzelnen Sprachen zu berücksichtigen. Der hierfür verwendete Algorithmus lässt sich wie folgt zusammenfassen: 1. Nimm alle Konzepte aus allen Sprachen der Kollektion vorläufig in den multilingualen Thesaurus auf. 2. Bestimme, welche Konzepte über einen Language-Link direkt auf ein anderes Konzept in dem multilingualen Thesaurus, der ja Konzepte aus unterschiedlichen Sprachen enthält, verweisen. Auf diese Weise werden Paare von ähnlichen Konzepten im multilingualen Thesaurus markiert. 3. Bestimme, welche Paare von Konzepten sich auf diese Weise gegenseitig referenzieren. Da die über einen Language-Link referenzierten Konzepte im Allgemeinen entweder äquivalent oder allgemeiner sind als das betreffende Konzept selbst, ist davon auszugehen, dass zwei Konzepte, die sich gegenseitig auf dieseWeise referenzieren, äquivalent sind oder sich zumindest stark ähneln. Dieses Vorgehen ist analog zu der Methode, die [GREGOROWICZ UND KRAMER (2006)] folgend zur Bestimmung verwandter Konzepte innerhalb einer Sprache verwendet wurde. 4. Vereinige Paare solcher Konzepte, wobei alle Eigenschaften und Relationen der beiden Konzepte zusammengefasst werden. Dabei wird mitgeführt, welche Sprachen das vereinigte Konzept abdeckt. Jede Sprache darf in dem resultierenden sprachübergreifenden Konzept höchstens einmal vorkommen. 4. Ablauf 31 5. Vereinige so lange, bis kein solches Paare von Konzepten mehr vorhanden ist, das vereinigt werden kann. Sind zwei Konzepte zwar durch gegenseitige Language-Links verbunden, aber die Mengen der von ihnen bereits abgedeckten Sprachen überlappen sich, so stehen diese beiden Konzepte in Konflikt zueinander und können nicht vereinigt werden. Solche Konzepte sind sich in der Regel sehr ähnlich (siehe auch .11.3). Dieses Verfahren ist in .9.2 genauer beschrieben. Auf das eigentliche Zusammenführen folgt auch hier eine Nachbereitungsphase zur Konsolidierung der Daten (.9.2.3). Dabei werden aufgrund der neu bestimmten Beziehungen zwischen den sprachübergreifenden Konzepten die Verwandtheit und Ähnlichkeit der Konzepte neu berechnet. 4.4. Export Die vierte und letzte Transformation ist der Export der lokalen und globalen Datensätze in eine extern weiterverwendbare Form, nämlich das Thesaurus-Modell (siehe .10). Es repräsentiert die aus der Wikipedia extrahierten Beziehungen in einer standardisierten, für andere Softwaresysteme nützlichen Form, nämlich RDF/SKOS (.10.3). Die Modellierung der Thesaurusdaten in RDF/SKOS folgt insbesondere [GREGOROWICZ UND KRAMER (2006), VAN ASSEM U. A. (2006), W3C (2005)]. Teil III. Implementation