1 Einleitung
1.1 Motivation
1.2 Ziele
1.3 Vorgehen
2 Semantische Netze
2.1 Grundlagen der Wissensrepräsentation
2.2 Darstellungsmittel semantischer Netze
2.2.1 Einfache semantische Netze
2.2.2 Erweiterte semantische Netze
2.2.3 Mehrschichtige erweiterte semantische Netze
2.3 Funktionen und Relationen
2.3.1 Zweistellige Relationen
2.3.2 Reflexive Relationen
2.3.3 Einstellige Funktionen
2.3.4 Mehrstellige Funktionen
3 Graphen zeichnen
3.1 Grundlagen
3.1.1 Kräftebasierte Methoden
3.1.2 Energiebasierte Methoden
3.1.3 Andere Methoden
3.2 Beschriftung von Graphen
3.3 Qualitätskriterien
3.4 Lauftzeitkomplexität
4 Graphendarstellung für MultiNet
4.1 Bisherige Funktionalität
4.1.1 MWR
4.1.2 RETE
4.1.3 Vergleich von MWR-Layout und RETE_view
4.2 Erweiterung der Darstellungsmittel
5 Konzeption
5.1 Layout
5.2 Beschriftungen
5.2.1 Kantenbeschriftungen
5.2.2 Knotenbeschriftungen
5.3 Ausgabeformat
5.4 Statistikmodul
6 Technische Realisierung
6.1 Vorgaben
6.2 Design der Anwendung
6.3 Klassenstruktur
7 Evaluierung
7.1 Qualität
7.2 Laufzeiten
8 Ergebnisse
8.1 Fazit
8.2 Ausblick
Anhang
Quellenverzeichnis
Erklärung
Abbildungsverzeichnis
Abbildung 1: Semantisches Netz mit Verbesserungspotenzial für die Darstellung
Abbildung 2: Optimiertes semantisches Netz
Abbildung 3: Ein „Auto“-Frame
Abbildung 4: Semantisches Netz „Anja besitzt einen wertvollen Ring“
Abbildung 5: Faltung eines Hypergraphen
Abbildung 6: Kante mit k-types
Abbildung 7: Darstellung der Layer-Attribute
Abbildung 8: Zweistellige Relationen
Abbildung 9: Reflexive Relationen
Abbildung 10: Einstellige Funktion
Abbildung 11: Mehrstellige Funktionen
Abbildung 12: Graphentheoretische Abstände
Abbildung 13: Baryzentrisches Layout
Abbildung 14: Positionsmodelle für Beschriftungen
Abbildung 15: Graphenlayout im MWR
Abbildung 16: RETE_view Applet
Abbildung 17: Erkennung der Oszillation und Rotation
Abbildung 18: Anziehungskräfte bei mehrfachen Kanten
Abbildung 19: Ausrichtung der Kantenbeschriftungen
Abbildung 20: Beschriftung für Funktionskanten
Abbildung 21: 6-Positionen-Modell für Knoten-Beschriftungen
Abbildung 22: Beschriftung von Blatt-Knoten
Abbildung 23: Java-Modell für Kreisbögen
Abbildung 24: Konstruktion einer Schleife
Abbildung 25: Überschneidung von Kanten und Beschriftungen
Abbildung 26: Kontextmenüs im JGemPanel
Abbildung 27: Paket der Klassen für das Zeichnen von Kanten
Abbildung 28: Paket der Klassen für das Zeichnen von Beschriftungen
Abbildung 29: Semantisches Netz mit Layer-Attributen und Statistik
Tabellenverzeichnis
Tabelle 1: Vergleich der Eigenschaften von MWR-Layout und RETE_view
Tabelle 2: Vergleich der drei Darstellungsmodule
Tabelle 3: Laufzeiten des Layout-Algorithmus
Abkürzungsverzeichnis
Abbildung in dieser Leseprobe nicht enthalten
Semantische Netze haben sich als eines der erfolgreichsten Konzepte für die Darstellung und Verarbeitung von Wissen in dem Kontext der automatischen Wissensverarbeitung erwiesen. Während die textuelle Repräsentation eines semantischen Netzes sich sehr gut für die automatische Verarbeitung eignet, unterstützt die visuelle Darstellung in Form einer Grafik das Verständnis eines menschlichen Betrachters.
Einzelne Wissenselemente und die Beziehungen zwischen ihnen werden als Knoten und Kanten eines verallgemeinerten Graphen abgebildet, so dass sich das Zeichnen eines semantischen Netzes auf das Zeichnen von Graphen zurückführen lässt. Bei dem rechnergestützten Zeichnen von Graphen besteht die Aufgabe darin, zu einem gegebenen Graphen (als Menge von Knoten und Kanten) die Positionen der Knoten, Kanten und Beschriftungen so zu ermitteln, dass die Darstellung ästhetischen Anforderungen genügt.
Zur Unterstützung der praktischen Arbeit mit semantischen Netzen wurden in dem Lehrgebiet Praktische Informatik VII der FernUniversität in Hagen bereits mehrere Anwendungen entwickelt, die Module für die grafische[1] Darstellung von semantischen Netzen mit einschließen. Trotz der umfassenden Möglichkeiten dieser Anwendungen bestehen noch Lücken in der Berücksichtigung aller Darstellungsmittel von semantischen Netzen, beispielsweise bei mehrstelligen Funktionen. Insbesondere die Platzierung von Beschriftungen zeigt deutlichen Optimierungsbedarf, damit durch weniger Überschneidungen die Beschriftungen besser lesbar werden (s. Abbildung 1). Auch hinsichtlich der Berechnung der Darstellung von großen Netzen mit mehreren Hundert Knoten ist eine deutliche Verbesserung der Qualität wünschenswert und möglich.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 1: Semantisches Netz mit Verbesserungspotenzial für die Darstellung
Ausgehend von der Abbildung 1 werden die hinter der Darstellung liegenden Algorithmen analysiert sowie mit anderen in der Literatur bekannten Ansätzen für das automatische Zeichnen von Graphen verglichen. Daraus ergeben sich schrittweise Optimierungsmöglichkeiten der vorhandenen Algorithmen, so dass insgesamt ein ästhetisch besseres Layout erreicht wird.
Die Bewertung des Layouts erfolgt anhand von objektiven Kriterien, die im Verlauf der Arbeit erarbeitet werden. Die Beurteilung eines konkreten Layouts nach diesen Kriterien erfolgt innerhalb der entwickelten Anwendung durch ein implementiertes Statistikmodul.
Der Abbildung 2 liegt das gleiche semantische Netz zugrunde wie der Abbildung 1, jedoch nach Berechnung des Layouts mit Hilfe der verbesserten Algorithmen. Anhand der definierten Qualitätskriterien ermittelt das Statistikmodul eine Wertung von 97 (von 100 möglichen) Punkten für die verbesserte Darstellung, während die ursprüngliche Darstellung wegen der vielen Überschneidungen nur ca. 30 Punkte erhält.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 2: Optimiertes semantisches Netz
Zuerst werden die Grundlagen der semantischen Netze im Kontext von Wissensrepräsentationssystemen eingeführt (Kapitel 2). Hierbei werden Syntax und Semantik der mehrschichtigen erweiterten semantischen Netze sowie ihre graphische Darstellung erläutert. Besonderes Augenmerk liegt auf der Darstellung von Relationen und Funktionen, den Bindegliedern zwischen einzelnen Wissenselementen eines semantischen Netzes.
Kapitel 3 widmet sich dem Zeichnen von semantischen Netzen aus einem graphentheoretischen Blickwinkel. Es werden verschiedene Ansätze diskutiert, mit deren Hilfe ein Computerprogramm selbständig zu einem gegebenen semantischen Netz ein qualitativ hochwertiges und optisch ansprechendes Layout berechnen und zeichnen kann. Dies schließt eine Festlegung der Qualitätskriterien sowie ihre Anwendung auf die vorgestellten Ansätze mit ein.
Von den Anwendungsmodulen zur Darstellung semantischer Netze, die an der FernUniversität in Hagen entwickelt wurden, werden zwei in Kapitel 4 mit ihren jeweiligen Einsatzgebieten sowie Vor- und Nachteilen vorgestellt. Aus einem Vergleich der beiden Module ergeben sich eine Reihe von Eigenschaften bzw. Funktionen, um die die grafische Darstellung erweitert werden kann, so dass der Nutzwert gesteigert wird.
Wesentliches Element der Anforderungen ist eine möglichst überschneidungsfreie Darstellung von Beschriftungen der Knoten und Kanten eines semantischen Netzes. Die Konzeption der Algorithmen und Funktionen für die Erfüllung der zusätzlichen Anforderungen wird in Kapitel 5 vorgestellt. Zudem wird die textuelle Repräsentation von semantischen Netzen um einige syntaktische Elemente erweitert, die eine Speicherung der berechneten Darstellung erlauben.
Kapitel 6 erläutert die technische Umsetzung der Konzepte in ein Java-Applet. Hierbei wird auf die verwendeten Datenstrukturen und implementierten Funktionen eingegangen.
Eine Evaluierung der Umsetzung erfolgt in Kapitel 7 anhand der vorher festgelegten Qualitätskriterien. Für die Auswertung der Kriterien an einzelnen semantischen Netzen wird das implementierte Statistikmodul des Java-Applets verwendet.
Den Abschluss bildet Kapitel 8 mit einer Zusammenfassung der Ergebnisse sowie einem Ausblick auf weitere Entwicklungen in dem Bereich der semantischen Netze und ihrer graphischen Darstellung.
Die Repräsentation von Wissen auf dem Rechner ist eines der zentralen Anliegen der Forschung im Bereich der Künstlichen Intelligenz. Dementsprechend vielfältig sind die bisher hierfür verwendeten Modelle und realisierten Wissensrepräsentationssysteme (WRS).
Die meisten WRS basieren auf der Bildung von Modellen für geistige Inhalte des menschlichen Bewusstseins. Die Prozesse und Methoden des Denkens und des Speicherns von Informationen im Gehirn sind jedoch sehr komplex und größtenteils noch unbekannt, so dass nur Ausschnitte davon betrachtet werden können. Die Inhalte des Bewusstseins bzw. des Gedächtnisses wiederum beruhen auf einer Abbildung der realen Welt, wie sie auch von den Naturwissenschaften beobachtet wird. Das Gedächtnis kann jedoch auch abstrakte Konzepte, z. B. aus den Bereichen der Philosophie oder Theologie, darstellen, die nicht direkt in der uns umgebenden physikalischen Welt beobachtbar sind. Solche abstrakten Konzepte wie auch soziale Phänomene haben bisher noch keinen (nennenswerten) Eingang in rechnergestützte WRS gefunden.
Stark strukturierte Inhalte werden bereits seit längerem in den klassischen Datenbanken abgebildet, vor allem mit dem relationalen Datenmodell[2], aber auch dem hierarchischen Modell und dem Netzwerkmodell . Aus einem technischen Blickwinkel gehören zu den Datenbanken auch Thesauri, wegen ihres besonderen Fokus’ auf Begriffe (vor allem Synonyme und Antonyme) werden sie jedoch zu den lexikalischen WRS gezählt.[3]
Produktionsregelsysteme sind neben logikorientierten WRS die bedeutendsten Vertreter der regelorientierten WRS . Sie werden häufig in Expertensystemen eingesetzt, wenn das Wissen der Experten in Form von „Wenn..., dann...“ –Aussagen vorliegt.
Die letzte an dieser Stelle betrachtete Gruppe von Wissensrepräsentationssystemen sind die objektorientierten WRS . Diese sind insbesondere für die Darstellung von Zusammenhängen zwischen verschiedenen Objekten geeignet.
In Frame-Repräsentationen werden Objekte in einer Hierarchie als Schema von Merkmals-Wert-Paaren (auch Slots und Filler genannt) dargestellt. Ein Filler kann ein „einfacher“ Wert sein, wie z.B. eine Zeichenkette oder eine Zahl, oder auch wieder selber ein Frame. Dadurch kann eine geschachtelte Struktur entstehen.
In Abbildung 3 ist ein Frame dargestellt, der ein Auto repräsentiert. Die Slots „Modell“ und „Sitze“ enthalten einfache Werte, während „Motor“ einen eigenen Frame enthält, der weitere Eigenschaften besitzt.[4]
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 3: Ein „Auto“-Frame
Semantische Netze legen – im Vergleich zu den Frame-Repräsentationen – einen stärkeren Wert auf Verknüpfungen zwischen einzelnen Wissenselementen. Damit ähneln sie in einem gewissen Maße dem Speichermodell des Gehirns, wie es von der kognitiven Psychologie angenommen wird.[5] Das Gehirn merkt sich demnach Daten nicht in strukturierter Tabellenform, sondern eher in Form eines Netzwerkes bzw. einer „mentalen Landkarte“. Diese Landkarte wird von frühester Kindheit an gezeichnet und mit Verbindungen zwischen Wissenselementen versehen. Mit zunehmendem Alter wird sie eher statisch und unterliegt kaum noch wesentlichen Veränderungen. Bei der grafischen Darstellung semantischer Netze ist daher eine klare und verständliche Form hilfreich, um leichter in die mentale Landkarte des Betrachters integriert werden zu können.
Wegen der angenommenen Ähnlichkeit der semantischen Netze mit der Art der Wissensrepräsentation des menschlichen Gehirns werden sie oft für die Speicherung natürlichsprachlich gegebenen Wissens eingesetzt.
Semantische Netze können in zwei unterschiedlichen Formen dargestellt werden: graphisch und textuell. Die graphische Notation besteht aus einem verallgemeinerten Graphen, dessen Knoten durch gerichtete, markierte Kanten miteinander verbunden sind. Ein Knoten repräsentiert einen Begriff, der aus einem Wortetikett („Eiffelturm“, „Tomate“), einem komplexen Muster („das grüne Auto“) und einer Gesamtheit von Beziehungen zu anderen Begriffen bestehen kann.
Eine gerichtete Kante repräsentiert eine Beziehung zwischen zwei Knoten und die Kantenmarkierung beschreibt die Art der Beziehung.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 4: Semantisches Netz „Anja besitzt einen wertvollen Ring“
Das semantische Netz in Abbildung 4 verdeutlicht die eingeführten Termini. „Anja“, „Ring“ und „wertvoll“ sind Wortetikette für 3 Knoten, „POSS“ (Besitz), „PROP“ (Eigenschaft) und „SUB“ (begriffliche Unterordnung) sind die Markierungen der 3 Kanten. Der unmarkierte Knoten in der Abbildung erhält durch seine speziellen Beziehungen zu den anderen Knoten die Bedeutung „Anjas wertvoller Ring“.
An dieser Stelle muss darauf hingewiesen werden, dass in semantischen Netzen vereinbarungsgemäß die Tiefenstruktur eines Satzes abgebildet wird und nicht die Oberflächenstruktur.[6] Dies bedeutet, dass Sätze mit gleichem Bedeutungs-Inhalt trotz verschiedener Formulierungen in einem semantischen Netz gleich abgebildet werden können. „Einen wertvollen Ring hat Anja“ würde demnach ebenfalls durch das Netz aus Abbildung 4 dargestellt werden. Dementsprechend bestehen die Knotenmarkierungen jeweils aus den Grundformen der Wortetikette, bei Adjektiven wie „wertvoll“ ist dies Singular Maskulinum im Indikativ. Bei Wörtern mit gleicher Schreibweise aber unterschiedlicher Bedeutung (Polyseme und Homographen) wird zusätzlich ein Index zur Unterscheidung der verschiedenen Begriffe an die Knotenmarkierung angehangen.[7]
Der Vorteil der graphischen Notation liegt darin, dass sie für den Menschen intuitiv leicht erschließbar ist. Viele wichtige Zusammenhänge zwischen den Wissenselementen lassen sich direkt ablesen.
Für die Speicherung und Verarbeitung eines semantischen Netzes auf einem Rechner ist die bildliche Darstellung weniger geeignet. Hierfür wird üblicherweise eine textuelle Repräsentation verwendet, die einem Ausdruck der KI-Programmiersprache LISP entspricht.
Knoten, die in der graphischen Darstellung keine Markierung aufweisen, müssen für die textuelle Darstellung einen eindeutigen, künstlichen Namen erhalten, weil sie sonst nicht identifiziert werden könnten. Solche Knoten tragen im Folgenden stets das Präfix „c“ gefolgt von einer laufenden Nummer.
Dem semantischen Netz aus Abbildung 4 entspricht die folgende (verkürzte) textuelle Notation:
((poss Anja c1)
(sub c1 Ring)
(prop c1 wertvoll))
Die genaue Syntax der verwendeten Notation ist in Anhang 1 angegeben. Für die automatische Verarbeitung ist diese Notation sehr gut geeignet, weil sie einfach aufgebaut ist und sich leicht um beliebige Zusatzinformationen erweitern lässt, die während der Verarbeitung benötigt werden. Für den Menschen ist es allerdings wesentlich schwieriger, die wichtigen Informationen aus dieser Darstellung abzulesen als aus einer Grafik, insbesondere bei größeren Netzen.
Die bisher vorgestellten einfachen semantischen Netze sind jedoch in ihrer Darstellungsfähigkeit begrenzt. „Ein einfaches semantisches Netz reicht für die Repräsentation der semantischen Ebene der natürlichen Sprache nicht aus. Dazu benötigt man erweiterte semantische Netze, die durch einen orientierten markierten Hypergraphen dargestellt werden.“[8]
Ein erweitertes semantisches Netz bietet im Vergleich zu einem einfachen semantischen Netz ein größeres Repertoire an Darstellungsmitteln, um den Anforderungen der natürlichen Sprache gerecht zu werden[9] :
- Zusätzliche Sortenmarkierungen für die Knoten zur Unterscheidung von z. B. Objekten, Sachverhalten und Situationsdeskriptoren. Üblicherweise werden über 30 Sorten unterschieden.
- Verschiedene Typen von Beziehungen zwischen Knoten, nicht nur binäre Relationen (s. Abschnitt 2.3)
- Hyperknoten, die ganze Teilnetze repräsentieren und als solche Beziehungen zu anderen Knoten haben können.
- Hyperkanten, die Hyperknoten miteinander verbinden.
Die Bedeutung von Hyperkanten und Hyperknoten lässt sich anhand des Beispieles der Abbildung 4 schrittweise herleiten. Die drei markierten Knoten stellen lexikalisierte Begriffe dar und entsprechen damit den Grundbausteinen eines jeden Netzes. Der unmarkierte Knoten repräsentiert einen Begriff höherer Komplexität, der durch mehrere Worte bezeichnet wird („Anjas wertvoller Ring“), und ist damit bereits ein Hyperknoten. Dieser Knoten kann nun in einer erweiterten Wissensbasis mit anderen komplexen Begriffen in Verbindung gesetzt werden, um einen Sachverhalt als natürlichsprachlichen Satz zu beschreiben („Anjas wertvoller Ring liegt auf dem alten Tisch.“, s. Abbildung 5 oben). Dieser Sachverhalt kann durch einen Sachverhaltsknoten repräsentiert werden. Seine Kanten sind die Hyperkanten.
Die grafische Darstellung von Hyperknoten und Hyperkanten ermöglicht das Falten , ein grafischer Effekt, bei dem die untergeordneten Knoten und Kanten nicht mehr dargestellt werden, um die Übersichtlichkeit des Graphen zu erhöhen. In Abbildung 5 werden zuerst die beiden Hyperknoten „Anjas wertvoller Ring“ und „der alte Tisch“ jeweils eingefaltet, wodurch die Knoten der lexikalisierten Begriffe in der grafischen Darstellung entfallen. Im zweiten Schritt werden auch die beiden Hyperknoten zusammen mit den Hyperkanten und dem unmarkierten Knoten der Lokationsangabe[10] zu einem Sachverhaltsknoten eingefaltet.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 5: Faltung eines Hypergraphen
Der Einsatz der Faltung sollte nur bedeutungserhaltend erfolgen, d. h. die insgesamt repräsentierte Information im Netz sollte nicht verändert werden, um den Betrachter nicht zu verwirren. Dies wäre beispielsweise der Fall, wenn eine weitere PROP-Kante zwischen „Anja“ und „alt“ bestünde (s. Abbildung in Anhang 2). Nach dem ersten Faltungsschritt würde die Kante zwischen den beiden Hyperknoten verlaufen, was inkorrekt ist, weil „Anjas wertvoller Ring“ im ursprünglichen Netz nicht die Eigenschaft „alter Tisch“ besitzt.
Wie die Markierung des Sachverhaltsknotens im letzten Faltungsschritt zeigt, reicht auch die Darstellungskraft der erweiterten semantischen Netze nicht aus, um alle Feinheiten der natürlichen Sprache abzubilden. In diesem konkreten Fall fehlt eine Angabe der Bestimmtheit: handelt es sich um irgendeinen alten Tisch oder um einen bestimmten alten Tisch? Das gleiche gilt auch für den wertvollen Ring und sogar für Anja. Hier wird deutlich, dass sich die Problemstellung nicht durch die zusätzlichen Knoten „bestimmt“ und „unbestimmt“ lösen lässt, weil eine andere semantische Ebene involviert ist.
Diese Hürde überwinden die mehrschichtigen erweiterten semantischen Netze , in deren Schichten (engl. Layer) verschiedene Attribute zu den einzelnen Knoten und Kanten angegeben werden können. Zu den wichtigsten Layer-Attributen der Knoten gehören die folgenden:
- Generizität: repräsentiert der Knoten einen generischen Inhalt („Vögel können fliegen“) oder einen speziellen Inhalt?
- Faktizität: handelt es sich um eine faktische oder um eine hypothetische Entität?
- Determiniertheit: handelt es sich um eine bestimmte (determinierte) Entität oder um eine nicht näher bestimmte (indeterminiert)?
- Quantität: Singular oder Plural
- Kardinalität: Anzahl der Entitäten, die durch den Begriff repräsentiert werden
Die Layer-Attribute sind stets als optional zu verstehen und können daher entfallen, falls sie im Prozess der Wissenserfassung unbekannt sind oder falls ein bestimmtes Attribut nicht auf ein dargestelltes Konzept anwendbar ist (einer Zeitangabe kann beispielsweise keine sinnvolle Kardinalität zugewiesen werden).
Den Kanten werden verschiedene knowledge types (k-types) zugeordnet, die angeben, in wie weit die repräsentierten Beziehungen gültig sind. Die grundlegende Unterscheidung wird zwischen immanentem und situativem Wissen getroffen.[11] Immanentes Wissen (auch definitorisches Wissen genannt) gilt als charakteristisch für die betrachteten Entitäten und ihre Beziehungen („Ein Vogel ist ein Tier“) und ist unabhängig von einer bestimmten Situation. Situatives Wissen (auch assertorisches Wissen genannt) hingegen gilt nicht als charakteristisch für die beteiligten Entitäten, sondern nur für einen bestimmten Kontext („Gestern hat es in Bonn geschneit“).
In der Praxis wird eine weitere Differenzierung der k-types vorgenommen, um die Beziehungen zu präzisieren und eine automatische Verarbeitung der Informationen einer Wissensbasis zu ermöglichen:
- Immanent: die Beziehung ist untrennbar mit der Definition der beteiligten Entitäten verbunden („Ein Mensch ist ein Lebewesen“)
- Kategorisch: die Beziehung gilt immer, gehört aber nicht zur eigentlich Definition der beteiligten Entitäten („Europa liegt auf der nördlichen Hemisphäre“)
- Prototypisch: die Beziehung gilt im Normalfall, es kann aber auch Ausnahmen geben („Vögel können fliegen“)
- Restriktiv: die Beziehung gilt nur unter bestimmten Einschränkungen („Die Sonne scheint nur am Tag“)
- Situativ: die Beziehung gilt nur in einer bestimmten Situation, einem Kontext oder einem Diskursbereich
- Deskriptiv: eine Entität der Beziehung beschreibt die andere
Eine Besonderheit ist dadurch gegeben, dass jedem Kantenende einer Beziehung ein anderer k-type zugeordnet werden kann. Abbildung 6 zeigt eine ORIGM-Kante (materielle Herkunft) mit den k-types immanent (imman) und situativ (situa). Dies ist so zu interpretieren, dass eine Silbermünze definitorisch aus dem Material Silber besteht. Diese Beziehung ist in Bezug auf Silber selbst nur situativ, weil der Begriff „Silber“ im Kern nicht davon abhängt, ob man aus dem Material Münzen herstellt oder nicht. Die k‑types können in der textuellen Repräsentation wie folgt dargestellt werden:
(ORIGM Silbermünze Silber imman situa)
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 6: Kante mit k-types
Um die Layer-Attribute komplett in einem Graphen anzuzeigen, werden Knoten nicht mehr als Kreise dargestellt, sondern im Prinzip als Rechtecke, die die komplette Beschriftung und darunter in großen eckigen Klammern die Layer-Attribute in einer Kurzschreibweise enthalten (s. Abbildung 7[12] ). Die Abbildung zeigt das semantische Netz, welches bei der automatischen Analyse der Frage „Wie starb Jimi Hendrix?“ aufgebaut wurde. Auch in dieser Darstellung wurde der Übersicht halber von der Faltung gebrauch gemacht, ansonsten würden die Relationen SUB und SUBS zu eigenen Knoten („Nachname“, „Vorname“, „Mensch“, „sterben“) zeigen.[13]
Aus Platzgründen und der Verständlichkeit wegen werden die Layer-Attribute üblicherweise nur bei kleinen Netzen vollständig dargestellt.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 7: Darstellung der Layer-Attribute
Bei den einfachen semantischen Netzen wurde davon ausgegangen, dass Beziehungen zwischen Entitäten stets binär sind und sich die entsprechenden Kanten zwischen den beteiligten Knoten als gerade Linien darstellen lassen. Bei den erweiterten semantischen Netzen sind auch andere Konstruktionen möglich, die bei einer grafischen Darstellung beachtet werden müssen. Die textuelle Repräsentation der Netze bleibt hiervon größtenteils unbeeinflusst.
Eine n-stellige Relation ist eine Teilmenge des Kreuzproduktes der Definitionsmengen der beteiligten Argumente: Abbildung in dieser Leseprobe nicht enthalten
Für die Kleiner-als-Relation gilt beispielsweise: kleiner-als(3, 5) oder in Infix-Notation: 3 < 5. Die LISP-Notation hierfür ist „(kleiner-als 3 5)“.
Binäre Relationen sind die am häufigsten vorkommende Art von Beziehungen in semantischen Netzen. Sie werden üblicherweise durch gerade Linien zwischen den beteiligten Knoten dargestellt. Sollen mehrere binäre Relationen zwischen den gleichen Knoten dargestellt werden, so werden diese als Bögen gezeichnet (s. Abbildung 8).
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 8: Zweistellige Relationen
Wenn Abbildung in dieser Leseprobe nicht enthaltenfür jedes beliebige x gilt, so ist die Relation REL reflexiv. Für die textuelle Darstellung ist es unerheblich, ob die Argumente der Relation identisch sind oder nicht: „(kleiner-gleich 3 5)“ und „(kleiner-gleich 5 5)“ haben im Prinzip die gleiche Form. Die grafischen Notationen unterscheiden sich aber sehr wohl von einander, da eine gerade Kante von einem Knoten zu sich selber schwerlich darstellbar ist.
Folglich wird die entsprechende Kante in Form einer Schleife von einem Knoten zu sich selber geführt (s. Abbildung 9).
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 9: Reflexive Relationen
Eine Funktion ist eine eindeutige Abbildung von Werten aus dem Definitionsbereich der Funktion auf ihren Wertebereich. Funktionen werden im Kontext von semantischen Netzen für eine „Veränderung“ von Entitäten eingesetzt. Einstellige Funktionen dienen insbesondere einer Erzeugung von Entitäten mit unterschiedlicher Sortenzugehörigkeit.
Einzelne Sorten können als Definitionsbereiche für Funktionen und Relationen eingesetzt werden, so dass die Gültigkeit der Argumente rechentechnisch überprüft werden kann. So hat die bereits erwähnte Relation ORIGM als Argumente ein Konkretum k und eine Substanz s. Abbildung in dieser Leseprobe nicht enthaltenbesagt, dass k aus s besteht.
Die Relation LOK aus dem Beispiel „Anjas wertvoller Ring liegt auf dem alten Tisch“ hat als erstes Argument ein Objekt o oder einen Sachverhalt sv, dem eine Lokation l zugeordnet wird: Abbildung in dieser Leseprobe nicht enthaltenundAbbildung in dieser Leseprobe nicht enthalten. Der Tisch ist von der Sorte her ein Konkretum und kann daher nicht in der LOK-Relation als Lokation eingesetzt werden. Hier kommt die einstellige Funktion *AUF ins Spiel, die als Argument ein Objekt annimmt und als Rückgabewert eine Lokation liefert (s. Abbildung 10). Die erzeugte Lokation entspricht der präpositionalen Deutung „auf dem alten Tisch“.
Die graphische Darstellung einer einstelligen Funktion besteht aus einer Linie wie bei Relationen. Die Pfeilspitze der Linie zeigt auf das Funktionsargument, das andere Ende auf das Ergebnis. Zusätzlich wird auf der Linie ein Kreis mit Pfeilspitze gezeichnet.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 10: Einstellige Funktion
In der textuellen Darstellung unterscheidet sich eine Funktion prinzipiell nicht von einer Relation, daher fängt per Konvention der Name einer Funktion stets mit einem Sternchen (*) an, während dies bei einer Relation nicht der Fall ist. Das obige Netz kann daher wie folgt textuell dargestellt werden:
((LOK „Anjas wertvoller Ring“ c1)
(*AUF c1 „alter Tisch“))
Bei der Interpretation der beiden Zeilen ist jedoch zu beachten, dass nach dem Relationsnamen LOK direkt beide Argumente folgen, während nach dem Funktionsnamen *AUF zuerst der Funktionswert und danach das Argument folgen.
Eine logische Erweiterung der einstelligen Funktionen sind mehrstellige Funktionen. Die Funktion *ZWISCHEN ist analog zu *AUF aufgebaut, hat aber zwei oder mehr Objekte als Argumente und liefert als Rückgabewert eine Lokation, die präpositional interpretiert zwischen den Objekten liegt.
In einer Grafik wird eine mehrstellige Funktion so dargestellt, dass die Funktionsargumente durch Linien mit dem Funktionswert verbunden sind. Die Pfeilspitzen zeigen auch hier auf die Argumente. Zusätzlich werden die Linien der Argumente durch einen Bogen mit Pfeilspitze verbunden (s. Abbildung 11). Bei Funktionen, die ihre Argumente gleichwertig behandeln (wie *ZWISCHEN), ist die Ordnung der Knoten in der Darstellung unerheblich, falls das zugrunde liegende Wissensrepräsentationssystem entsprechende Axiome für die Symmetrie und Assoziativität der Funktionen enthält.
Die Funktion *MODP (Abk. für „modify property“) aus Abbildung 11 verhält sich jedoch anders: sie erwartet als Argumente eine Eigenschaft („reich“) und einen Spezifikator („sehr“), der die Eigenschaft verändert. Daher muss der Bogen zwischen den beiden Linien mit seiner Pfeilspitze von dem Spezifikator zu der Eigenschaft hinzeigen.
Das dargestellte Netz lässt sich mit dem Satz „Luxemburg liegt zwischen Frankreich, Deutschland und Belgien und ist sehr reich“ natürlichsprachlich formulieren.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 11: Mehrstellige Funktionen
Die textuelle Darstellung geschieht analog zu den einstelligen Funktionen. Für das obige Beispiel wäre dies:
((LOK Luxemburg c1)
(*ZWISCHEN c1 Frankreich Deutschland Belgien)
(PROP Luxemburg c2)
(*MODP c2 sehr reich))
Das Zeichnen von semantischen Netzen per Hand oder mit einem einfachen Grafikprogramm ist aufwändig und insbesondere für größere Netze ab 10 oder 20 Knoten recht schwierig. Deshalb bietet es sich geradezu an, das Zeichnen des Netzes von einem Rechner automatisch erledigen zu lassen. Das Problem besteht formal gesehen darin, zu einem (in textueller Form) gegebenen Graphen ein ästhetisch ansprechendes Layout des Graphen zu berechnen. Die Kriterien der Ästhetik werden später erläutert[14].
In den letzten Jahren sind Algorithmen zur Berechnung eines automatischen Graphen-Layouts immer beliebter geworden, weil sie viel manuelle Arbeit einsparen können. Die steigende Rechenleistung der Rechner sowie die Verfügbarkeit von guten Schnittstellen für die Grafikerzeugung in Programmiersprachen hat einige der Hürden für eine automatische Layout-Berechnung gesenkt.[15]
Dementsprechend gibt es eine ganze Reihe verschiedener Algorithmen, die sich in den jeweiligen Zielen und daher auch in den Vorgehensweisen deutlich unterscheiden. Einzelne Forschungsgebiete aus dem Bereich des Zeichnens von Graphen sind das Zeichnen von ungerichteten, geradlinigen Graphen, orthogonalen Graphen[16], hierarchischen, gerichteten Graphen, 3-dimensionalen Graphen und auch das Zeichnen von Landkarten.
Die Landkarten mögen in dieser Aufzählung ungewöhnlich erscheinen, es finden sich aber vielfach die gleichen Problemstellungen wieder wie bei den anderen Graphentypen, wie z. B. das Platzieren von Beschriftungen.
In den folgenden Abschnitten werden die Grundideen einiger Algorithmen vorgestellt sowie die Einsatzmöglichkeiten für das Zeichnen semantischer Netze diskutiert.
Viele Methoden für das Erstellen eines Graphen-Layouts basieren auf Analogien zu physikalischen Systemen. Wegen dieser Beziehung zu der uns umgebenden physikalischen Welt erscheinen die Ergebnisse intuitiv gut nachvollziehbar. Zudem ist die ästhetische Darstellung für Graphen mit unter 50 Knoten akzeptabel.[17]
Im Allgemeinen besteht eine solche Layout-Methode aus zwei Komponenten: einem Modell und einem Algorithmus.[18] Das Modell repräsentiert physikalische Objekte und die Interaktionen (bzw. Kräfte) zwischen ihnen, was in einem Graphen G=(V, E) als Knoten und Kanten abgebildet wird. Der Algorithmus ist eine Berechnungsvorschrift, die einen Gleichgewichtszustand zwischen den Kräften des Modells herzustellen versucht. Dabei wird davon ausgegangen, dass ein Zustand des Systems mit minimaler Gesamtenergie ein adäquates Layout liefert und daher erstrebenswert ist.
Wie das adäquate Layout genau aussieht, hängt entscheidend von der Ausprägung des Modells ab. Der Algorithmus dient lediglich dazu, die Eigenschaften des Modells umzusetzen bzw. zu optimieren.
Für eine ästhetisches Gestaltung des Layouts werden zwei Rahmenkriterien mitgegeben, über die ein allgemeiner Konsens besteht: 1. die Knoten sollen gleichmäßig auf der Zeichenfläche verteilt sein und 2. durch eine Kante verbundene Knoten sollen nah bei einander liegen.
Äquivalente physikalische Phänomene existieren für beide Kriterien. Eine gleichmäßige Verteilung der Knoten auf der Fläche entspricht abstoßenden Kräften zwischen den Knoten, wie sie in magnetischen oder elektrischen Feldern vorkommen. Das zweite Kriterium findet seine Umsetzung in Form von Federn, die im Modell als Kanten zwischen den Knoten eingesetzt werden. Federn besitzen mehrere Eigenschaften, die der Modellierung zugute kommen: sie besitzen ein konstante natürliche Länge, für die im Modell der gewünschte ideale Knotenabstand eingesetzt werden kann. Ferner besitzen Federn Kräfte, die sie bei einer Verformung auf ihre natürliche Länge zurückbringen wollen. Dies gilt sowohl für die Dehnung als auch für die Stauchung einer Feder, und zwar umso mehr, je stärker ihre Länge von ihrer natürlichen Länge abweicht. Die Modellierung mit elektrischen Kräften und Federn geht auf Eades zurück[19] und ist heute unter dem Namen „Spring Embedder“[20] bekannt.
Auf jeden der Knoten Abbildung in dieser Leseprobe nicht enthaltenwirken Kräfte, die sich aus den abstoßenden elektrischen Kräften Abbildung in dieser Leseprobe nicht enthaltenund den Federkräften Abbildung in dieser Leseprobe nicht enthaltenzusammensetzen: Abbildung in dieser Leseprobe nicht enthalten
Die Federkräfte zwischen zwei Knoten u und v können sowohl anziehend als auch abstoßend wirken, je nachdem, ob der Knoten-Abstand größer oder kleiner als die natürliche Länge der Feder ist. Sei Abbildung in dieser Leseprobe nicht enthaltender Abstand der Knoten, Abbildung in dieser Leseprobe nicht enthaltender Einheitsvektor von u nach v, l die natürliche Länge der Feder und cσ eine Konstante der Federstärke, so sind die erzeugten Kräfte
Abbildung in dieser Leseprobe nicht enthalten
Die abstoßenden elektrischen Kräfte betragen
Abbildung in dieser Leseprobe nicht enthalten
wobei cρ eine Konstante der Abstoßung ist.
Bei Eades wurden die abstoßenden Kräfte nur zwischen nicht-benachbarten Knoten berechnet. Dies spart zwar Rechenzeit, kann aber zu „Gedränge“ führen, wenn in einem lokalen Bereich viele Kanten zwischen den Knoten vorhanden sind.
Der eigentliche Spring Embedder Algorithmus ist recht kurz zu beschreiben:
Eingabe: Graph G =(V, E)
Ausgabe: Knotenpositionen mit minimaler Gesamtenergie
Erzeuge initiale Positionierung der Knoten vÎV
Wiederhole M Mal
Berechne die Kräfte F(v) auf jedes vÎV
Bewege jeden Knoten um Delta * F(v)
Ende Wiederholung
Das M ist eine fest vorgegebene Anzahl von Iterationen (bei Eades: 100) und das Delta eine Konstante (bei Eades: 0,1), die die Kräfte insgesamt verringert, so dass sich die Knoten durch die simultane Platzierung nicht übertrieben stark bewegen. Trotz der Einfachheit des Algorithmus erzeugt er in vielen Fällen ein zufrieden stellendes Layout.
Einige der Kritikpunkte an dem Algorithmus wurden von anderen Autoren für eine Weiterentwicklung genutzt. So wird häufig kritisiert, dass die Anzahl der Iterationen sowie die Bewegungs-Konstante Delta sehr starr sind und sich nicht an dem vorgegebenen, spezifischen Graphen orientieren. So ist es leicht vorstellbar, dass ein großer Graph mit 100.000 Knoten nach 100 Iterationen mit kleiner Bewegungs-Reichweite sein optimales Layout noch nicht erreicht hat.
Viele Erweiterungen der Spring-Methode wurden von Fruchterman und Reingold durchgeführt[21]. Sie haben sowohl neue Kräfte der Anziehung und der Abstoßung eingeführt, als auch die Konzepte von Temperatur und Abkühlung umgesetzt. Die neuen Kräfte haben eine ähnliche Wirkung wie diejenigen bei Eades, sind jedoch effizienter zu berechnen, da der rechenintensive Logarithmus und eine Wurzelberechnung entfallen.
Es werden anziehende Kräfte
Abbildung in dieser Leseprobe nicht enthalten
zwischen benachbarten Knoten und abstoßende Kräfte
Abbildung in dieser Leseprobe nicht enthalten
zwischen jedem Paar von Knoten berechnet.
Werden jeweils benachbarte Knoten betrachtet, so entsprechen die anziehenden und abstoßenden Kräfte zusammen einer federähnlichen Kraft wie bei Eades:
Abbildung in dieser Leseprobe nicht enthalten
Fruchterman und Reingold sahen auch vor, die gesamte Zeichenfläche in ein Gitter aufzuteilen und abstoßende Kräfte von Knoten nur bis zu benachbarten Gitterfeldern zu verfolgen, da sich weiter entfernte Knoten sowieso nur mit sehr schwachen Kräften abstoßen. Dies spart wiederum einiges an Berechnungsaufwand. Dieser Ansatz hat sich aber nicht durchgesetzt, weil die Berechnung bzw. Befüllung des Gitters bei jedem Iterationsschritt einen aufwändigen Prozess darstellt und der Nutzen bei ungünstig aussehenden Graphen minimal sein kann.
Das Konzept der Temperatur ersetzt die bei Eades festen Werte der Iterationen-Anzahl und der Bewegungs-Reichweite durch ein natürlicheres Modell. Ähnlich dem physikalischen Konzept können sich Teilchen (Knoten) bei einer hohen Temperatur schnell bewegen, während bei einer niedrigen Temperatur nur langsame, kleine Bewegungen möglich sind. Der Algorithmus wird anfangs mit einer hohen Temperatur gestartet, was den Knoten die Möglichkeit gibt, sich schnell in Richtung der auf sie wirkenden Kräfte zu bewegen. Später, wenn das Layout sich dem Zielzustand nähert, sind die benötigten „Korrekturen“ geringer und die Temperatur kann abgesenkt werden.
Die neue Position eines Knotens Abbildung in dieser Leseprobe nicht enthaltenergibt sich aus der alten Position Abbildung in dieser Leseprobe nicht enthaltendurch die Anwendung der Kräfte Abbildung in dieser Leseprobe nicht enthaltenunter Berücksichtigung der Temperatur Abbildung in dieser Leseprobe nicht enthalten:
Abbildung in dieser Leseprobe nicht enthalten
Fruchterman und Reingold setzen einen „Abkühlungsplan“ (engl. Cooling Schedule) ein, nach dem die Temperatur linear von dem Startwert aus abgesenkt wird. Im Allgemeinen führt dies zu akzeptablen Ergebnissen. Die Autoren merken jedoch auch an, dass ein anderer optimierter Abkühlungsplan das Ergebnis erheblich verbessern kann, während gleichzeitig die Anzahl der benötigten Iterationen des Algorithmus gesenkt wird.[22]
Eine weitere Neuerung bei Fruchterman und Reingold ist der Einsatz eines Rahmens um die Zeichenfläche. Der Rahmen begrenzt die Bewegung der Knoten auf den in ihm liegenden Bereich. Hierfür gibt es verschiedene Methoden: der Rahmen kann den Bewegungsanteil ein Knotens, der über den Rahmen hinausgeht, einfach abschneiden, was in der physikalischen Welt einem unelastischen Stoß entspricht. Es kann aber auch ein elastischer Stoß simuliert werden, der den Knoten an dem Rahmen abprallen lässt. Eine weitere vorgesehene Möglichkeit ist die Modellierung eines elektrisch geladenen Rahmens, welcher die Knoten bei zu großer Nähe abstößt.
Die meisten der heutigen Modellierungen verzichten allerdings auf solch einen Rahmen der Zeichenfläche und führen nach Abschluss der Layout-Berechnung eine Skalierung durch, die den berechneten Graphen in die zur Verfügung stehende Zeichenfläche einpasst.
Die Spring-Embedder Methode versucht, durch Federkräfte, die auf jedes Paar verbundener Knoten wirken, einen Zustand des Systems zu erzeugen, in dem die Gesamtenergie minimal ist. Kamada und Kawai verfolgten in ihrer Arbeit[23] den Ansatz, Federkräfte zwischen jedem Knotenpaar einer Zusammenhangskomponente des Graphen wirken zu lassen. Eine Zusammenhangskomponente eines Graphen besteht jeweils aus allen Knoten, die durch Kanten miteinander verbunden sind.
Eine zentrale Rolle hierbei stellt der graphentheoretische Abstand zwischen Knoten dar, der der Länge des jeweils kürzesten Pfades zwischen zwei Knoten entspricht. Zwischen jedem Paar von Knoten wird im Modell eine Feder eingesetzt, deren natürliche Länge dem graphentheoretischen Abstand multipliziert mit der idealen Länge einer einzelnen Kante entspricht. Das bedeutet im Grunde, dass jeder Pfad idealerweise durch eine gerade Linie dargestellt wird.[24] In Abbildung 12 haben die Knoten A und B einen graphentheoretischen Abstand von 2, während B und F einen Abstand von 3 haben. (Der kürzeste Pfad ist B-C-E-F.)
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 12: Graphentheoretische Abstände
Das Ziel von Kamada und Kawais Algorithmus ist es, einen entspannten Zustand des Systems zu berechnen, bei dem die Gesamtenergie am niedrigsten ist. Da es für Graphen meistens nicht möglich ist, alle Federn auf ihre natürliche Länge zu bringen, ergibt sich die Frage nach einer Gewichtung der Federn. Es erscheint für die grafische Darstellung am sinnvollsten, kurze Abstände – also direkt durch Kanten verbundene Knoten – stärker zu gewichten und weniger auf die weit entfernten Knoten zu reagieren. Aus diesem Grund werden den Federn Kräfte gegeben, die umgekehrt proportional zu ihrer natürlichen Länge sind: Abbildung in dieser Leseprobe nicht enthalten.
c ist eine Skalierungskonstante und dG ist der graphentheoretische Abstand der Knoten. Damit beträgt die Gesamtenergie des Systems
Abbildung in dieser Leseprobe nicht enthalten
wobei kuv die oben dargestellte Federkraft ist, duv der Abstand Abbildung in dieser Leseprobe nicht enthaltender Knoten und luv die natürliche Länge der Feder zwischen den Knoten.
[...]
[1] Der Begriff „graphisch“ bezieht sich in dieser Arbeit auf mathematische Graphen, während der Begriff „grafisch“ im Zusammenhang mit Grafiken bzw. grafischen Darstellungen verwendet wird.
[2] Vgl. Codd, Edgar (1970)
[3] Vgl. Helbig, Hermann (1996), S. 51
[4] Vgl. Aiteanu, Fabian (2005), S. 4
[5] Vgl. Hoffmann, Joachim (1986)
[6] Diese Vereinbarung dient der Komplexitätsreduktion und vermindert außerdem den benötigten Speicherplatz, weil Paraphrasierungen des bestehenden Wissens dieses nicht erweitern.
[7] Genau genommen kann es sich um zwei Indizes handeln: der erste Index wird zur Unterscheidung von Homographen verwendet, der zweite zur Unterscheidung von Polysemen.
[8] Helbig, Hermann (1996), S. 101
[9] Vgl. Helbig, Hermann (1996), S. 102ff
[10] Die Bedeutungen der Relation LOK sowie der Funktion *AUF werden in Abschnitt 2.3 erläutert.
[11] Helbig, Hermann (2001), S. 23ff
[12] Hartrumpf, Sven (2004)
[13] Auf die einzelnen Elemente der Darstellung soll nicht weiter eingegangen werden, da es nur um das Prinzip der Darstellung von Layer-Attributen geht.
[14] s. Abschnitt 3.3
[15] Vgl. Behzadi, Lila (1999), S. 1
[16] In einem orthogonalen Graphen verlaufen alle Kanten waagerecht oder senkrecht, niemals schräg.
[17] Vgl. Brandes, Ulrik (2001), S. 71
[18] Vgl. Di Battista et al. (1999)
[19] Vgl. Eades, Peter (1984)
[20] Auf deutsch etwa „Feder-Einbettung“.
[21] Fruchterman/Reingold (1991)
[22] Vgl. Fruchterman/Reingold (1991), S. 1138
[23] Vgl. Kamada/Kawai (1989)
[24] Vgl. Brandes, Ulrik (2001), S. 78
