ontologiebasierte probabilistische profilanalyse mit markov logic

Transcrição

Institut für Informatik
Fachbereich Informatik und Mathematik
ONTOLOGIEBASIERTE PROBABILISTISCHE
PROFILANALYSE MIT MARKOV LOGIC NETWORKS
Diplomarbeit
von
Pawel Kozak
April 2011
Erstgutachter: Prof. Dott. Ing. Roberto Zicari
Zweitgutachter: Prof. Dr. Heiner Stuckenschmidt
ERKLÄRUNG
Hiermit erkläre ich, dass ich diese Diplomarbeit selbständig verfasst und keine anderen
als die angegebenen Quellen und Hilfsmittel benutzt habe.
Offenbach am Main,
Pawel Kozak
DANKSAGUNG
Ich möchte Herrn Prof. Dott. Ing. Roberto Zicari, Professur für Datenbanken und Informationssysteme (DBIS), Goethe Universität Frankfurt für seine Unterstützung und
die Ermöglichung dieser Arbeit danken. Weiterhin möchte ich Herrn Prof. Dr. Heiner
Stuckenschmidt, Lehrstuhl für Künstliche Intelligenz, KM+KR Research Group, Universität Mannheim für Denkanstöße danken, die entscheidend zur Realisierung dieser
Arbeit in ihrer jetzigen Form beigetragen haben. Ebenfalls danke ich Herrn
Stuckenschmidt für seine zahlreichen Ratschläge und Anmerkungen, die mir halfen,
diese Diplomarbeit zu verbessern.
Mein besonderer Dank gilt Herrn Dr. Karsten Tolle, Professur für Datenbanken und Informationssysteme (DBIS), Goethe Universität Frankfurt für seine hervorragende Betreuung dieser Arbeit und die freundschaftliche und herzliche Arbeitsatmosphäre. Sein
stets hilfreicher fachlicher und menschlicher Rat und seine zahlreichen Verbesserungsvorschläge waren mir eine sehr große Hilfe.
Außerdem danke ich Herrn Pedro Oliveira, Clark & Parsia LLC, Washington, USA für
den angenehmen wissenschaftlichen Kontakt und den Beistand in technischen Fragen,
sowie Herrn Nicola Guarino, Laboratory for Applied Ontology, Trento, Italien für die
freundliche Erlaubnis der Nutzung seiner publizierten Abbildungen. Sina Kühne, Rainer
Häuser und Alexander Stepanovsky möchte ich für ihre Zeit und Mühe danken, die sie
sich für das Korrekturlesen dieser Arbeit nahmen.
Abschließend danke ich herzlichst meiner Mutter und meinen mittlerweile verstorbenen
Grosseltern – ohne ihre Unterstützung, ihren moralischen Beistand, ihren Glauben an
mich während meines Studiums und ihre Liebe wäre diese Arbeit nicht möglich gewesen.
INHALTSVERZEICHNIS
KAPITEL 1. EINFÜHRUNG ....................................................................................... 1
1.1 MOTIVATION ........................................................................................................... 1
1.2 ZIELSETZUNG DER ARBEIT ...................................................................................... 1
KAPITEL 2. GRUNDLAGEN UND STAND DER FORSCHUNG ......................... 7
2.1 ONTOLOGIEN UND IHRE EINSATZMÖGLICHKEITEN .................................................. 7
2.1.1
2.1.2
2.1.3
2.1.4
2.1.5
2.1.6
Begriffsdefinition ...................................................................................................................... 7
Semantische Technologien ..................................................................................................... 10
Semantic Web ......................................................................................................................... 13
Wissensrepräsentation in Künstlicher Intelligenz ................................................................... 17
Ontologien vs. Datenbank-Schemata ...................................................................................... 19
Klassifizierung und Einsatzmöglichkeiten von Ontologien .................................................... 20
2.2 WEB ONTOLOGY LANGUAGE ................................................................................ 22
2.2.1 Teilsprachen von OWL ........................................................................................................... 23
2.2.2 Unterschiede zu RDF(S) und Besonderheiten ........................................................................ 24
2.3 DIE COMMUNITY IRCLOVE................................................................................. 25
2.3.1 Einleitung ................................................................................................................................ 25
2.3.2 Struktureller Aufbau ............................................................................................................... 25
2.3.3 IRCLOVE Datenbank ............................................................................................................. 26
2.3.4 Benutzerprofile ....................................................................................................................... 29
2.3.5 Ein genauerer Blick auf „IRCLOVE Persönlichkeiten“ ......................................................... 31
2.3.6 Zusammenfassung möglicher Matching-Faktoren .................................................................. 35
KAPITEL 3. PROBABILISTISCHE ONTOLOGIEN............................................ 37
3.1 WARUM WAHRSCHEINLICHKEITEN? ..................................................................... 37
3.2 WAHRSCHEINLICHKEITEN IN BESCHREIBUNGSLOGIKEN ....................................... 38
3.2.1 Beschreibungslogiken im Allgemeinen .................................................................................. 38
3.2.2 P-SHIF(D) und P-SHOIN(D) ............................................................................................. 39
3.2.3 P-SHIQ(D) und Pronto.......................................................................................................... 41
3.2.4 P-CLASSIC ............................................................................................................................ 43
3.2.5 BayesOWL.............................................................................................................................. 45
3.3 STATISTISCHES RELATIONALES LERNEN ............................................................... 46
3.3.1 Grundlagen.............................................................................................................................. 46
3.3.1 Graphbasierte Modelle ............................................................................................................ 47
3.4 MARKOV LOGIC NETWORKS ................................................................................. 51
3.4.1 Aufbau der Markov Logic Networks ...................................................................................... 51
3.4.2 Inferenz ................................................................................................................................... 52
3.5 RESÜMEE .............................................................................................................. 53
KAPITEL 4. KONZEPT DER PPAO ONTOLOGIE ............................................. 57
4.1 KONZEPTE ............................................................................................................. 57
4.2 RELATIONEN ......................................................................................................... 58
4.2.1 Typen von Relationen in PPAO .............................................................................................. 58
4.2.2 Modellierung von Relationen .................................................................................................. 59
I
INHALTSVERZEICHNIS
4.3 INTEROPERABILITÄT ............................................................................................. 60
4.4 SCHEMATISCHE DARSTELLUNG............................................................................. 62
KAPITEL 5. IMPLEMENTIERUNG UND INFERENZ ........................................ 63
5.1 MLN REASONER ................................................................................................... 63
5.1.1 TheBeast ................................................................................................................................. 63
5.1.2 Alchemy .................................................................................................................................. 64
5.1.3 PyMLN – ein Bestandteil von ProbCog.................................................................................. 65
5.2 MODELLIERUNGSANSÄTZE .................................................................................... 67
5.3 KONSTRUKTION DER PPAO ONTOLOGIE............................................................... 68
5.3.1 Evidence-Datei ........................................................................................................................ 68
5.3.2 MLN Datei .............................................................................................................................. 69
5.3.3 Match-Prädikate als Sub-Indizes des Ähnlichkeitsindex ........................................................ 71
5.3.4 Der Ähnlichkeitsindex und die Inferenz in PPAO .................................................................. 76
5.3.5 Multiple Quellen und Regulierung ihrer Vertrauenswürdigkeit ............................................. 76
5.3.6 Segmentierung, Recommending und andere Aufgaben .......................................................... 79
5.4 VON OWL ZU MLN .............................................................................................. 79
KAPITEL 6. EXPERIMENTELLE UNTERSUCHUNG ....................................... 83
6.1 SZENARIEN ............................................................................................................ 83
6.1.1 ALL versus ALL ..................................................................................................................... 83
6.1.2 1 versus ALL........................................................................................................................... 84
6.2 METHODIK ............................................................................................................ 84
6.3 SKALIERBARKEIT BEZÜGLICH BENUTZERANZAHL................................................. 85
6.4 SKALIERBARKEIT BEZÜGLICH PRÄZISION .............................................................. 86
6.4.1 Präzision durch Aktionen und Hobbys ................................................................................... 87
6.4.2 Präzision durch Kategorien ..................................................................................................... 90
6.5 SPEICHERVERBRAUCH ........................................................................................... 92
6.6 AUSSAGEKRAFT DES ÄHNLICHKEITSINDEX ........................................................... 95
6.6.1 Wie funktioniert der Ähnlichkeitsindex? ................................................................................ 95
6.6.2 Ähnlichkeit von realen Profilen im 1 vs. ALL Szenario ......................................................... 98
6.6.3 Pseudo-Segmentierung im ALL vs. ALL Szenario............................................................... 100
6.7 DIE GRENZEN ...................................................................................................... 102
KAPITEL 7. ZUSAMMENFASSUNG .................................................................... 105
7.1 RÜCKBLICK ......................................................................................................... 105
7.2 EIN PAAR PHILOSOPHISCHE GEDANKEN .............................................................. 107
7.3 AUSBLICK ........................................................................................................... 108
LITERATURVERZEICHNIS ................................................................................... 111
ANHANG ..................................................................................................................... 115
I. KONFIGURATION DES TESTSERVERS ...................................................................... 115
II. LEVEL 1-KATEGORIEN IN IRCLOVE PERSÖNLICHKEITEN ................................... 115
III. DIE 30 HÄUFIGSTEN HOBBYS DER IRCLOVE BENUTZER ................................... 115
IV. WAHRSCHEINLICHKEITSVERTEILUNGEN FÜR EXPERIMENT IN ABSCHNITT 6.6.2 . 116
Profil A ............................................................................................................................................ 117
Profil B............................................................................................................................................. 117
II
INHALTSVERZEICHNIS
Profil C............................................................................................................................................. 118
Profil D ............................................................................................................................................ 118
III
KAPITEL 1. EINFÜHRUNG
1.1 Motivation
Was ist ein Profil? Die Persönlichkeitspsychologie besagt, dass ein Profil ein Charakterbild eines Menschen darstellt. Nicht so komplex, aber im selben Kontext, wird in der
Informatik und IT-nahen Wirtschaftszweigen der Begriff „Benutzerprofil“ für eine Ansammlung von Informationen über eine Person und möglicherweise ihre Verhaltsweise
in einem abgeschlossenen Umfeld verwendet. Benutzerprofile sind seit der Entwicklung
neuer Internettechnologien wie Web 2.0, semantischen Netzwerken, Social Networks
und Communities zu einem wichtigen und festen Bestandteil der Informationstechnologie geworden. Heutzutage werden Profile in beinahe allen Wirtschaftsbereichen verwendet, angefangen beim Marketing bis zum Maschinenbau – überall dort, wo ein Produkt oder Dienstleistung mit einem Kunden verknüpft wird.
Durch den Einsatz moderner Techniken der Disziplinen Wissensmanagement und
Künstliche Intelligenz lassen sich wertvolle Informationen aus den Daten über eine Person und die Beziehungen zwischen Personen ableiten – Informationen, die zum einen
wirtschaftliche Prozesse effizienter und kostengünstiger machen können, sowie zugleich
aus wissenschaftlicher Sicht das maschinelle Verständnis des Charakterbildes oder zumindest der Bedürfnisse und Interessen von Personen darstellen. Diese hoch interessante Erkenntnis zu demonstrieren war meine Motivation für die Erstellung dieser Diplomarbeit.
1.2 Zielsetzung der Arbeit
1
Man stelle sich vor, dass man zwei Personen in einer großen und komplexen Web
Community aufgrund ihrer gemeinsamen Interessen und Benutzerverhaltens die gegenseitige Kontaktaufnahme vorschlagen möchte – wie könnte man dies mit Hilfe von
Ontologien bewerkstelligen und wie effektiv wäre das?
Als eine Form der Wissensrepräsentation haben die Ontologien in der letzten Dekade,
insbesondere in Verbindung mit der Idee des Semantic Web, großes Forschungsinteresse
geweckt. Der entscheidende Vorteil von Ontologien gegenüber speziell für Aufgaben,
wie unter anderem auch Profilanalyse, entwickelten Lösungen liegt in ihrer Flexibilität.
Da eine Ontologie auf Standards aufbaut und eine klar definierte Semantik besitzt ist sie
viel einfacher zu erweitern und kann vielseitiger eingesetzt werden, als eine fest implementierte Lösung. Um unter anderem die oben gestellte Frage zu beantworten soll in
dieser Diplomarbeit deshalb eine relativ allgemeine Ontologie konzipiert werden, die
eine diversifizierte Analyse von Benutzerprofilen ermöglicht.
Die heutige Wissensmanagement-Forschung beschäftigt sich immer stärker mit Verarbeitung und Analyse von Daten, die nicht nur auf bloßen Tatsachen basieren. Vielmehr
beruhen viele, wenn nicht alle, Prozesse oder Ereignisse in der uns umgebenden Welt
auf Zufall oder bestimmten Mustern. In der Regel liegen Wahrscheinlichkeitsverteilungen solchen zufallsbedingten Ereignissen zugrunde, deshalb soll der Einbezug von
probabilistischen Informationen eine besondere Eigenschaft der zu entwickelnden Ontologie sein. Insbesondere ist die Wahrscheinlichkeitsgewichtung der Relationen zwischen den Profilen von großem Interesse. Heutzutage können Daten in globalen Systemen wie z.B. Facebook aus verschiedenen Quellen stammen (z.B. Facebook Apps).
Die Verwendung dieser Daten bei der Profilanalyse erfordert eine sorgfältige Bewertung der Vertrauenswürdigkeit von Quellen, da missbräuchliche Daten leicht Störungen
verursachen können. Da der Einsatz von probabilistischen Ontologien hier wegen der
einfachen Gewichtungsmöglichkeiten als vorteilhaft erscheint, soll untersucht werden,
inwieweit sich dieser Aspekt in der zu entwickelnden Ontologie umsetzen lässt.
Eine entscheidende Fragestellung für diese Aufgaben ist die Wahl eines für die Praxis
geeigneten Formalismus zur Modellierung der Ontologie. Deshalb soll ein Überblick
über die aktuelle Forschung im Bereich der Wissensrepräsentation von statischen und
probabilistischen Daten gegeben werden. Speziell Beschreibungslogiken wie P-SHIQ,
P-CLASSIC etc., aber auch Formalismen wie Bayesian Logic Networks (BLNs) und
Markov Logic Networks (MLNs) könnten für unsere Zielstellung in Frage kommen. Wir
werden die Vor- und Nachteile dieser Formalismen unter praxisbezogenen Gesichtspunkten diskutieren und anschließend begründen, warum MLNs das Werkzeug der
2
Wahl für diese Arbeit waren. Es soll ebenfalls gezeigt werden, dass die Modellierung
mit Hilfe der Web Ontology Language (OWL) grundsätzlich möglich ist und untersucht
werden, inwieweit sich der Einsatz von OWL für die Zielstellung als vorteilhaft erweisen könnte.
Auf Basis von existierenden Daten und Strukturen aus der von dem Verfasser der Diplomarbeit entwickelten Online-Community IRCLOVE soll dann auf realen Daten gezeigt werden, wie die entwickelte Ontologie aufgebaut werden kann. Mit Hilfe der Ontologie und auf Basis von MLNs soll ergründet und demonstriert werden, wie mit logischem Schlussfolgern bestimmte Aufgabenstellungen gelöst und Fragen beantwortet
werden können. Zwar sollte die Ontologie allgemein genug sein, um für mehrere Fragestellungen Antworten zu liefern. Um den Rahmen der Arbeit nicht zu sprengen soll aber
nur eine bestimmte Aufgabe intensiv untersucht werden – die Ähnlichkeitsanalyse von
Profilen. Bei der Ähnlichkeitsanalyse handelt es sich um die Fragestellung, inwieweit
sich zwei Benutzer A und B unter Beachtung statischer und dynamischer Faktoren ähneln. Diese Faktoren stellen entweder von Personen eingegebene Daten oder ihre Interaktionen mit einem System dar. So können Benutzer in IRCLOVE eine eigene multimediale Bibliothek anlegen und dort Aktionen wie Medien betrachten, kommentieren
oder erstellen ausführen. Da die Medien zudem in einer hierarchischen Kategorienstruktur organisiert sind, können A und B beispielsweise ähnliches Leseverhalten in den Kategorien aufweisen. Dies führt zu der Schlussfolgerung, dass A und B gemeinsame Interessensschwerpunkte haben und sich somit ähneln.
Beispielsweise betrachten zwei Benutzer Paul und Anna gerne Bilder von Katzen, dabei
stehen solche Bilder bei Paul für 70% und bei Anna für 80% der insgesamt betrachteten
Medien. Diese Übereinstimmung im Leseverhalten spricht dafür, dass beide Benutzer
ein gemeinsames Interesse für Katzen haben. Hierzu soll ein Index entwickelt werden,
der den Grad der Ähnlichkeit zwischen Profilen beschreibt und dazu verwendet werden
könnte, einen Vorschlag zur Kontaktaufnahme zu machen. Die technische Machbarkeit
und Grenzen für diese spezielle Aufgabe sollen dann mit Hilfe von Testreihen in einem
Experimentierteil der Arbeit untersucht werden. Auf andere Aufgabenstellungen wie
z.B. eine für das Marketing relevante Frage „Ist es möglich, Zielgruppensegmente von
Benutzern zu erstellen?“ (Segmentierung) oder ein für viele Einsatzbereiche relevantes
Problem „Wie kann man dem Benutzer auf der Basis seines Profils relevante Inhalte
vorschlagen?“ (Recommending) soll ebenfalls eingegangen werden.
Zusammenfassend soll ein allgemeines auf einer Ontologie basierendes und
probabilistisches Modell zur Analyse von Profilen konzipiert und seine Anwendung an
3
der Aufgabe der Ähnlichkeitsanalyse auf realen Daten der IRCLOVE Community demonstriert und untersucht werden. Auf der nächsten Seite zeigt Abbildung 1 schematisch die oben beschriebene Zielsetzung und den Entwicklungsverlauf dieser Arbeit.
4
Domäne
Datenbank
Mapping
OWL
Markov Logik
Ähnlichkeitsanalyse
?
Recommending
Inferenz
MLN
Reasoner
Verhaltensanalyse
Ontologie
Segmentierung
Abb. 1: Von Profilen über Markov Logik und Inferenz zur Problemlösung – das in dieser Diplomarbeit zu
entwickelnde Modell und mögliche Einsatzszenarien.
5
KAPITEL 2. GRUNDLAGEN UND STAND
DER FORSCHUNG
2.1 Ontologien und ihre Einsatzmöglichkeiten
In der Einleitung erwähnten wir bereits Ontologien als das Modell, das für die Umsetzung der Ziele dieser Arbeit benutzt werden soll. Dieses Unterkapitel soll nun neben der
Erläuterung der Bedeutung des Ontologiebegriffs auch Aufschluss darüber geben, warum Ontologien während der letzten Dekaden im Zentrum der Forschung der Wissensrepräsentation und Wissensmanagements standen und worin ihre Vorteile liegen. Dafür
werden wir auch so genannte semantische Technologien, zu denen auch Ontologien gehören, betrachten. Diese gewinnen mittlerweile nicht nur in der Forschung sondern auch
im wirtschaftlichen Umfeld immer mehr an Bedeutung. Die von uns zu entwickelnde
Ontologie sollte kein rein formales Modell sein, vielmehr ist die praktische Anwendbarkeit von großer Bedeutung. Wir werden deshalb abschließend auf die Einsatzmöglichkeiten von Ontologien in der Industrie eingehen.
2.1.1 Begriffsdefinition
Der Begriff „Ontologie“ (aus dem Griechischen „on“ für „sein“ und „logos“ für „Lehre“) wird sowohl in der Informatik als auch in der Philosophie verwendet. Wir werden
einen kurzen Blick auf seine Bedeutung in der Letzteren werfen, um die Zusammenhänge mit seiner Anwendung in der Informatik verständlicher darzustellen. Bereits
Aristoteles schrieb in seiner Abhandlungsreihe „Organon“ über Metaphysik und Ontologie. [GOS09] Im deutschensprachigen Raum wurde das Wort erstmals im 17ten Jahrhundert verwendet, unter anderem als „ontologia“ von dem deutschen Philosoph Rudolf
Gocklenius in seinem „Lexicon philosophicum“.1 Dabei bezeichnen die Philosophen die
„Ontologie“ als die Lehre von der Natur des Seins, speziell von den Grundstrukturen
1
COOMBS, Jeffrey: Goclenius, Rudolphus. Handbook of Metaphysics and Ontology, München, Philosophia Verlag. (1991) 312-313
7
KAPITEL 2. GRUNDLAGEN UND STAND DER FORSCHUNG
der Realität, deren Systematik bezüglich von Gegenständen, Prozessen oder Eigenschaften, und ihren strukturellen Beziehungen zueinander diskutiert wird. Typische Fragen
der philosophischen Ontologie sind beispielsweise „Was ist die Bedeutung des Seins?“
oder „Was für Formen der Existenz gibt es?“. Im Gegensatz zu Naturwissenschaften,
die oft empirisch nachgewiesene Dinge diskutieren, ist es für die Ontologie unbedeutend, ob ein Begriff in der Wirklichkeit existiert oder existieren kann. Daher werden
heutzutage die Begriffe „Ontologie“ und „Metaphysik“ in der Regel bedeutungsmäßig
gleichgesetzt.
Dagegen ist die Frage der Existenz für die Begriffsdefinition der „Ontologie“ in der Informatik recht pragmatisch zu beantworten: „Etwas, was repräsentiert werden kann, ist
für ein KI System auch das was existiert“ [Gru93]. Für den Begriff „Ontologie“ in der
Informatik gibt es zahlreiche Definitionen, ihnen allen ist die Nähe zur philosophischen
Ontologie-Lehre, wenn auch nur im abstrakten Sinne, anzusehen. Eine in der Literatur
weit verbreitete Definition stammt von Gruber, die er in [Gru93] formulierte: „Eine Ontologie ist eine explizite Spezifikation einer Konzeptualisierung“. Der Begriff
„Konzeptualisierung“, den Gruber in seiner Definition, benutzt bezieht sich auf eine Beschreibung, die von Genesereth und Nilsson in [GN87] formuliert wurde: „Eine
Konzeptualisierung ist eine abstrakte, vereinfachte Sicht auf die Welt, die wir für irgendeinen Zweck darstellen möchten.“ Sie definieren die Konzeptualisierung formal als
ein einfaches Tupel ( D, R ) , wobei D ein Gegenstandsbereich (auch Mini-Welt genannt) und R eine Menge von Relationen zwischen Objekten dieser Welt ist. Diese Relationen können unär (dann kann man sie auch als Eigenschaften betrachten) oder binär
sein, sowie andere Merkmale wie beispielsweise Symmetrie (Relation gilt in beide
Richtungen) oder Transitivität (Vererbungsrelation) aufweisen. Eine kleine Erweiterung
der Definition von Gruber nahm Borst vor: „Eine Ontologie ist eine formale Spezifikation einer gemeinsam benutzten Konzeptualisierung“.1,2 Hier wird postuliert, dass es verschiedene Sichten auf einen Gegenstandsbereich geben kann und dass die angesprochene Konzeptualisierung ein Konsens und keine individuelle Sichtweise sein sollte. Voraussetzung für diese Definition ist natürlich, dass Menschen, die eine Ontologie erstellen auch einen entsprechenden Konsens finden. Die „gemeinsame Nutzung“ wird von
Gómez-Pérez et al. präzisiert: „Wir können sagen, dass Ontologien … wieder verwendet
und durch Software-Applikationen und Personen gemeinsam genutzt werden können.“
1
BORST, Willem: Construction of Engineering Ontologies. PhD Thesis, Enschede, University of Twente.
(1997)
2
Die Definition lautet im Original: “An ontology is a formal specification of shared conceptualization.”
8
Wir sehen also, dass insbesondere auch Software-Agenten Ontologien nutzen sollen.1
Das wiederum führt uns zu einer weiteren Definition, in der Studer et al. die Definitionen von Gruber und Borst vereinten: „Eine Ontologie ist eine formale explizite Spezifikation einer gemeinsam benutzten Konzeptualisierung.“ [SBF98] Hier ist von einer
formalen expliziten Spezifikation die Rede, aber was bedeutet diese Aussage genau? Explizit bedeutet, dass eine (wörtliche) Beschreibung eine Situation exakt spezifiziert. Dagegen befinden sich die meisten Konzeptualisierungen „im Kopf“ – sie sind also implizit, d.h. die Situation wird eher durch die Wahl der Beschreibung (oder beschreibender
Wörter), sowie persönliche und individuelle Erfahrung spezifiziert. Es liegt also nahe,
dass man nach Studer et al. eine formelle Sprache benötigt, um Ontologien zu spezifizieren, dabei bedeutet formell, dass es sich um eine formale Sprache mit bekannter Semantik handeln muss [UG04]. Insbesondere ist eine formelle Sprache maschinenlesbar
und enthält keine natürliche Sprache. Eine typische formelle Sprache ist die Prädikatenlogik erster Stufe (PL1). Komplementär zu formellen sind die informellen Sprachen.
Diese werden oft mit der Umgangssprache gleichgesetzt. In Abb. 2 ist deutlich zu erkennen, dass die Einteilung zwischen formell und informell selten eindeutig verläuft,
vielmehr gibt es zahlreiche Abstufungen zwischen den beiden Begriffen. Bewegt man
sich entlang der Linie von links nach rechts, so steigt entsprechend die semantische
Mächtigkeit der Sprache sowie die Anzahl unterstützender Werkzeuge, beispielsweise
für Inferenz. Konträr dazu steigt die Laufzeitkomplexität dieser Werkzeuge – ein insbesondere bei Logiken oft beobachteter Effekt. Er geht so weit, dass zahlreiche sehr ausdrucksstarke Logiken nicht einmal entscheidbar sind. Für die Wahl der richtigen Repräsentationssprache für Ontologien ist es daher wichtig, einen Trade-off zwischen Ausdrucksstärke und Effizienz zu finden. Im Forschungsumfeld haben sich zwei formale
Paradigmen zur Repräsentation von Ontologien etabliert. Zum einen die Logiken, speziell Beschreibungslogiken (description logics) und zum anderen die logische Programmierung (logic programming) [GOS09]. Wir werden uns im Verlauf dieser Arbeit näher
mit den ersteren beschäftigen und auf das oben beschriebene Problem eingehen.
1
Die gemeinsame Nutzung von Ontologien erfordert Kommunikation unter Agenten, die in der Künstlichen Intelligenz auf Sprechertheorie aufbaut. Eine genauere Betrachtung würde jedoch den Rahmen dieser Arbeit sprengen.
9
Abb. 2: Der fließende Übergang von informellen zu formellen Sprachen nach [GOS09].
2.1.2 Semantische Technologien
Wir widmen uns nun kurz dem allgemeinen Umfeld der semantischen Technologien
und der Stellung von Ontologien innerhalb dieses Umfelds. „Semantische Technologien
werden als die Zukunft menschlichen Wissens gehandelt.“ [Rei10] – diese blumige Anmerkung macht deutlich, welche Erwartungen in der letzten Dekade in diesen Forschungsbereich gesetzt wurden. Zunächst sollte erklärt werden, was das ständig auftretende Wort „Semantik“ bedeutet, das in IT Kreisen schon beinahe zum Modewort aufgestiegen ist. Im klassischen Sinne ist Semantik ein Teilgebiet der Linguistik, das sich
mit dem Sinn und Bedeutung von Zeichen und sprachlichen Gebilden beschäftigt.1 Die
Verwendung des Wortes „Semantik“ in der Informatik bezieht sich öfter auf die formale
Semantik, die im Gegensatz zur „Syntax“, die eine Vorschrift zur Bildung von Ausdrücken in einer Sprache beschreibt, die exakte Bedeutung insbesondere von formalen
Sprachen spezifiziert. Der Unterschied zur Linguistik bildet lediglich die stark formalisierte Vorgehensweise. Semantische Technologien in der IT stehen für eine lose Ansammlung von Verfahren, die die Bedeutung von Information in den Mittelpunkt stellen. Auf die Softwareentwicklung bezogen werden dabei die Bedeutungsdaten getrennt
von den restlichen Daten und Programmcodes aufbewahrt und abgearbeitet. Wie die
Abbildung zeigt sind die Forschungsthemen rund um die Semantik sehr vielfältig und
interdisziplinär.
1
10
LÖBNER, Sebastian: Semantik: Eine Einführung. Gruyter Verlag. (2003)
Abb. 3: Forschungsthemen im Umfeld der semantischen Technologien.1
Typische Einsatzbereiche semantischer Technologien sind unter anderem die Erkennung von Begrifflichkeiten und Konzepten, die semantische Suche und die Kategorisierung von Information. Die Stärke semantisch angetriebener Verfahren liegt dabei in ihrer Flexibilität, die sie durch die oben erwähnte Trennung von semantischen Informationen aufweisen. Ein Kernmodell, auf dem viele semantischen Technologien aufbauen,
sind so genannte „semantische Netze“ (nicht zu verwechseln mit dem „Semantic Web“,
auf das wir später noch eingehen werden). Semantische Netze für Computer wurden
zum ersten Mal von R. H. Richens im Jahr 1956 vorgeschlagen.2 Sie sollten als eine Art
Computer-Plansprache (d.h. eine künstlich konstruierte Sprache) zur maschinellen
Übersetzung von natürlicher Sprache eingesetzt werden. Ein semantisches Netz ist ein
allgemeiner Graph in dem die Knoten gewisse Begriffe oder Konzepte darstellen. Die
Kanten stehen entsprechend für die Beziehungen zwischen den Konzepten. Ein Beispiel
für semantische Netze sind Taxonomien (Klassifizierungsschemata) - hier ist das semantische Netz ein gerichteter Graph. Ein weiteres Beispiel sind Assoziationsnetze, in
denen das semantische Netz als ungerichteter Graph auftritt. Assoziationsnetze simulieren im Grunde das menschliche Assoziativdenken.
1
DAVIS, M.: The Business Value of Semantic Technology. In Proceedings of Semantic Web Applications
for National Security SWANS, Washington. (2005)
2
RICHENS, Richard H.: Preprogramming for Mechanical Translation. Mechanical Translation Vol. 3.
(1956) 20-25
11
Abb. 4: Beispiel eines semantischen Netzes – Assoziativnetz als Modell für menschliche assoziative
Denkweise.
Hier wird deutlich, dass die Stärke semantischer Netze in der Verknüpfung von Wissen
liegt. Die Bedeutung entsteht dabei gerade durch die Relation von scheinbar statischem
Wissen. Betrachtet man nun die Definitionen von Ontologie in Abschnitt 2.1.1 so
kommt unweigerlich die Frage auf: Wo liegt eigentlich der Unterschied zwischen
Ontologien und semantischen Netzen? Diese Frage ist aufgrund einer Vielzahl von
Sichtweisen und Definitionen der Begriffe aus der semantischen Technologie in der Literatur nicht einfach zu beantworten. Eine plausible und verständliche Antwort gaben
Dirsch-Weigand und Schmidt an: „Ontologien sind im Unterschied zu semantischen
Netzen so streng axiomatisch aufgebaut und formalisiert, dass sie die Grundlage für
weit reichende logische Ableitungsregeln bilden können.“1 In Anlehnung an die oben
diskutierte „formale“ Komponente der Ontologie-Definition von Studer et al. wird nun
deutlich, dass Ontologien streng genommen eine Erweiterung der semantischen Netze
darstellen, die für Inferenzverfahren optimiert ist. Wir werden diesen Aspekt bei der Betrachtung von Beschreibungslogiken näher erläutern. Zunächst aber gehen wir noch auf
eine Vision ein, die sowohl hohes Medieninteresse anzog, als auch für die Forschung im
Bereich der semantischen Technologien eine Inspiration dargestellt hat. Insbesondere
führte diese Vision zur Entwicklung der Ontologiesprache OWL, die unter anderem für
die Realisierung der Ziele dieser Arbeit in Frage kam und später kurz erläutert werden
soll. Im Verlauf des nächsten Abschnitts stellen wir auch einige Kerntechnologien wie
XML und RDF vor, die historisch zu der Entwicklung von OWL beigetragen haben. Sie
sind insoweit wichtig, um die Syntax und Aufbau von OWL nachvollziehen zu können.
1
DIRSCH-WEIGAND, A., SCHMIDT, I.: Semantische Wissensstrukturen – Editorial. Information, Wissenschaft & Praxis Vol. 57 No. 6-7. (2006) 297
12
2.1.3 Semantic Web
Im Jahr 2001 präsentierten Tim Berners-Lee et al. in [BHL01] eine neue Zukunft für die
Weiterentwicklung des World Wide Web – das Semantic Web. Tim Berners-Lee implementierte die erste Hypertext Transfer Protocol (HTTP) Verbindung zwischen Client
und Server und entwickelte die Hypertext Markup Language (HTML). Damit wird er
als Begründer des WWW angesehen. Er gründete ebenfalls das seit 1994 bestehende so
genannte World Wide Web Consortium (W3C), das sich als Gremium für die Entwicklung neuer Standards für das WWW versteht.1 In der Tat entwickelte das W3C viele
Standards, die heutzutage unentbehrlich für das WWW geworden sind, dazu zählen außer HTML die Metasprache Extensible Markup Language (XML) und die StylesheetSprache Cascading Style Sheets (CSS). Speziell für das Semantic Web entwickelte
W3C das Resource Description Framework (RDF) sowie die Web Ontology Language
(OWL), die im nächsten Unterkapitel ausführlicher abgehandelt wird. Es ist verständlich, dass eine neue Vision des größten und wirtschaftlich wichtigsten Bereiches des
Internets seitens dieser Institution und ihres Begründers ein großes Interesse bei der Öffentlichkeit erweckte.
Das Semantic Web stellt eine Erweiterung des bestehenden WWW dar. Die grundlegende Idee ist, die Information im WWW in so einer Art und Weise zur Verfügung zu
stellen, dass eine Verarbeitung durch Computer möglich ist. In [BHL01] schreibt Berners-Lee dazu: „The Semantic Web is not a separate Web, but an extension of the current
one, in which information is given well-defined meaning, better enabling computers and
people to work in cooperation”. Obgleich in den Medien von einer eher utopischen
Sichtweise auf das Semantic Web zu lesen ist, zum Beispiel dass Computer die im Web
vorhandenen Informationen „verstehen“ würden oder dass das Internet „klüger“ werden
würde (vgl. Spiegel Online2) ist das Ziel des Semantic Web eigentlich wesentlich moderater, nämlich Methoden zu finden, die Information im Web so zu repräsentieren, dass
Computer mit Ihnen so umgehen können, wie es aus menschlicher Sicht nützlich und
sinnvoll erscheint [HKR+08]. Wie bereits oben erwähnt, hat sich das W3C dem Entwickeln neuer Standards für das Web, so auch für das Semantic Web verschrieben. Im so
genannten Semantic Web Technology Stack des W3C sind die am Semantic Web beteiligten Technologien und ihre Hierarchie zusammengefasst. Der Stack bildet auch eine
Roadmap für die Entwicklung weiterer Standards. Abb. 5 zeigt den ursprünglichen
1
http://www.w3.org/Consortium (geprüft am 6. Mai 2011)
„Das Internet soll klüger werden.“ Spiegel Online unter
http://www.spiegel.de/netzwelt/web/0,1518,561831,00.html (geprüft am 6. Mai 2011)
2
13
Stack der von Berners-Lee im Jahr 2000 konzipiert wurde im Vergleich zur einer späteren Abbildung des W3C aus dem Jahre 2007. Man erkennt, dass einige Technologien
wie OWL, RIF oder SPARQL im anfänglichen Konzept nicht namentlich gekennzeichnet wurden. Dagegen ist die allgemeine Hierarchie des Konzepts im Verlauf der Jahre
gleich geblieben. Wir werden im Rahmen dieser Arbeit nicht auf alle Technologien,
sondern nur auf zwei Kernsprachen, nämlich XML und RDF eingehen, da diese für die
spätere Betrachtung der Web Ontology Language relevant sind.
Abb. 5: Semantic Web Technology Stack aus den Jahren 2000 und 2007 – der Verlauf der konzeptionellen Entwicklung des Semantic Web.1
XML gehört zur Klasse so genannter Markup- oder Auszeichnungssprachen, mit deren
Hilfe Teile von Textdokumenten mit zusätzlicher Information versehen werden können.
Allgemein werden solche Informationen auch Metadaten genannt, d.h. Daten die Daten
beschreiben. Ein bekanntes Beispiel für eine Auszeichnungssprache ist HTML. Zusätzlich ist XML aber auch eine so genannte Metasprache – eine Sprache über eine Sprache. Dies stellt im Wesentlichen auch den Unterschied von XML zu HTML dar. Benutzt man in HTML feste Tags zur Auszeichnung von Informationen, so kann man dagegen in XML diese Tags selbst definieren – es wird also die logische Struktur anstatt
der Darstellung von Dokumenten beschrieben. Prinzipiell besteht ein XML-Dokument
aus Elementen, die durch einen XML-Namen identifiziert werden. Diese können wiederum andere Elemente, Daten, sowie Attribute beinhalten. Die auf diese Weise verschachtelte Struktur eines XML-Dokuments entspricht einem Baum. Das nächste Beispiel in Abb. 6 zeigt anschaulich, wie ein solcher Baum in Abhängigkeit der Elemente
aussehen kann. Zusätzlich können in XML Informationen über die Struktur der definier1
W3C, abrufbar unter http://www.w3.org/2000/Talks/1206-xml2k-tbl/slide10-0.html und
http://www.w3.org/2007/Talks/0130-sb-W3CTechSemWeb/#(24) (geprüft am 6. Mai 2011)
14
ten Sprache wie z.B. Restriktionen über ein so genanntes XML-Schema angegeben
werden. Wir werden auf diesen Aspekt aber nicht weiter eingehen.
15
HTML
Eine
<b>Diplomarbeit</b>
über
<i>Wissensmanagement</i>
XML
<werk>
<typ>Diplomarbeit</typ>
<thema>
Wissensmanagement
</thema>
</werk>
XML-Baum
Werk
Typ
Thema
Diplomarbeit
Wissensmanagement
Abb. 6: Grobe Unterschiede von HTML und XML anhand eines Beispiels.
XML wurde nicht speziell für das Semantic Web konzipiert, denn die Stärke dieser
Sprache liegt in der Möglichkeit einen universellen Datenaustausch von TextDokumenten zu betreiben. Sie wurde jedoch nicht dafür entwickelt, semantische Informationen zu kodieren. Dessen ungeachtet bildet XML die Grundlage für RDF (und auch
OWL) auf das wir als nächstes eingehen.
Im Grunde bildet das Resource Description Framework eine Familie von mehreren
W3C Standards und wurde zur Beschreibung allgemeiner Beziehungen zwischen Ressourcen spezifiziert. Die im Mittelpunkt von RDF stehenden Ressourcen werden dabei
durch URIs (Uniform Resource Identifiers) dargestellt. URIs spezifizieren allerlei mögliche Quellen im Internet, beispielsweise Web-Adressen, FTP-Server etc. Diese Art von
Adressierung ist neben der direkten IP-Adressierung die häufigste Adressierungsform
im Internet, vor allem im WWW. Im Gegenteil zu XML setzt RDF nicht auf Bäume,
sondern auf Graphen. Das ist durchaus nachvollziehbar, da RDF nicht für die hierarchische Strukturierung von einzelnen Dokumenten, sondern für die Repräsentation von
Beziehungen zwischen Ressourcen des Internets entwickelt wurde [HKR+08]. Die logische Struktur von RDF wird durch einen einfachen gerichteten Graphen repräsentiert,
bei dem die Knoten für die einzelnen Ressourcen stehen. Die Kanten symbolisieren entsprechend die Beziehungen zwischen je zwei Ressourcen. Ein RDF Eintrag ist also ein
Tripel (Subjekt, Prädikat, Objekt), wobei nur das Objekt ein Literal sein darf, aber nicht
muss. RDF verlangt nicht, dass die verwendeten URIs tatsächlich existieren, die URISchreibweise soll lediglich dazu beitragen, Probleme mit identischen Namen, wie sie oft
in XML vorkommen, zu vermeiden. Obwohl es für RDF mehrere Notationsformen gibt,
ist die so genannte RDF Serialisierung in Form von RDF/XML am weitesten verbreitet.
Diese beruht auf der XML-Schreibweise und kann daher von allen gängigen XMLParsern gelesen werden. Es gibt mehrere Möglichkeiten ein und denselben RDFGraphen in XML zu kodieren, Abb. 7 zeigt eine Variante, wie eine Beziehung, ähnlich
wie sie in Abb. 6 dargestellt ist, in RDF kodiert werden könnte.
RDF/XML
16
RDF-Graph
<?xml version=“1.0“?>
<rdf:RDF xmlns:rdf=“http://www.w3.org/“
xmlns:rolle=”http://example.org“>
<rdf:Description rdf:about=”http://example.org/Diplomarbeit”>
<rolle:Thema rdf:resource=”http://example.org/Wissen”/>
</rdf:Description>
</rdf:RDF>
http://.../Diplomarbeit
http://.../Thema
http://.../Wissen
Abb. 7: Beispiel eines RDF-Tripels in der RDF/XML Notation (siehe auch Bsp. aus Abb. 6). Die farbliche Hervorhebung identifiziert dieselben Elemente in der Notation- und Graphdarstellung.
Man beachte, dass in dem Beispiel XML-Namespaces (xmlns) benutzt werden, diese
definieren in XML eine Menge von Namen, die im jeweiligen Dokument benutzt werden. Hier setzt man sie unter Benutzung eines Präfix zur Abkürzung der URIs ein. Das
oben vorgestellte RDF wird durch ein so genanntes RDF-Schema, kurz RDFS, ergänzt
– zusammenfassend spricht man oft von RDF(S). RDF und RDFS stehen wie die ABox
und TBox einer Wissensbasis zueinander in Beziehung [HKR+08]. So bietet RDFS die
Möglichkeit Klassen und Klassenhierarchien (Vererbung) anzugeben, sowie die Definition von Eigenschaften und Datentypen. Anhand des in diesem Abschnitt benutzten
Beispiels könnte man exemplarisch das Objekt „Diplomarbeit“ der Klasse „Werk“ zuordnen und ihm den Datentyp „Text“ zuweisen. Man erkennt somit, dass sich mit Hilfe
von RDF(S) bereits einfache Ontologien bauen lassen und aus diesen Schlussfolgerungen gezogen werden können. Allerdings ist die Ausdrucksstärke von RDF(S) relativ beschränkt. So lassen sich Aussagen wie beispielsweise „Eine wissenschaftliche Arbeit
hat mindestens einen Autor“ nicht exakt formulieren.
2.1.4 Wissensrepräsentation in Künstlicher Intelligenz
Schon lange vor der Idee des Semantic Web wurde die Entwicklung von Formalismen
zur Repräsentation von Ontologien durch eine andere Disziplin der Informatik inspiriert
– die Künstliche Intelligenz. Wir werfen in diesem Abschnitt einen Blick auf die Wissensrepräsentation als Disziplin der Künstlichen Intelligenz und erläutern einige der
oben erwähnten Begrifflichkeiten. Der Begriff Wissensrepräsentation wird im Kontext
von Entwurf und Implementierung von Formalismen zur Beschreibung von Wissen benutzt. Gleichzeitig wird auch die Modellierung einer Domäne1 als „Wissensrepräsentation“ bezeichnet [OLN95]. Im Mittelpunkt der Wissensrepräsentation in der KI steht
stets die so genannte Wissensbasis (knowledge base). Wie die Abbildung zeigt, besteht
1
Als “Domäne” bezeichnet man einen speziellen, meistens fachspezifischen, Teil der Realität.
17
sie aus 3 Teilen: das zu beschreibende Modell wird zuerst mit Hilfe eines Formalismus
repräsentiert, um dann mit Hilfe eines so genannten Reasoners Schlussfolgerungen aus
den Daten zu ziehen. Der Reasoner ist ein Programm, das für einen speziellen Formalismus geschrieben ist und in der Regel Optimierungen enthält. Eine Wissensbasis besteht aus zwei Teilen: die TBox beschreibt terminologisches Wissen, d.h. Konzepte, Regeln etc. wogegen die ABox assertionales Wissen d.h. Axiome, Individuen etc. darstellt.
Eine Wissensbasis enthält notwendigerweise eine TBox um darüber zu schlussfolgern.
Eine ABox kann zusätzlich die in der TBox beschriebenen Konzepte mit konkreten Objekten verknüpfen.
Wissensbasis
Modell
in
Formalismus
verarbeitet durch
Reasoner
=
TBox
ABox
Abb. 8: Drei Basiselemente bilden eine Wissensbasis.
Zurückblickend auf die im Abschnitt 2.1.1 geführte Diskussion des Ontologiebegriffs
erkennt man, dass „Ontologien“ und „Wissensbasen“ sehr ähnliche Konstrukte darstellen. Allerdings werden Ontologien in der Literatur eher mit Beschreibungslogiken als
zugehörigen Formalismus in Verbindung gebracht, Wissensbasen dagegen mit Prädikatenlogik. Unter diesem Gesichtspunkt kann man eine Ontologie als eine spezielle Form
einer Wissensbasis bezeichnen, da Beschreibungslogiken eine entscheidbare Teilmenge
der Prädikatenlogik bilden.
Der Ansatz Prädikatenlogik als Formalismus für Wissensbasen zu benutzen wurde im
Laufe der Zeit immer wieder in Frage gestellt, so z.B. auch von Minsky in [Min74]:
„Traditionelle Logik kann nicht besonders gut mit realistischen, komplexen Problemen
umgehen, da sie für die Repräsentation von approximativen Lösungen schlecht geeignet
ist – diese aber unentbehrlich sind.“ Dieses Problem ist auch für diese Arbeit hoch relevant – wir werden jedoch im Kapitel 3 aktuelle Forschungsergebnisse zur Lösung dieses
Problems diskutieren. Ein ähnliches Problem besteht darin, dass Inferenz in der Prädikatenlogik monoton ist. Das bedeutet, dass die Hinzunahme von Prämissen (evidence) die
Schlussfolgerung nicht verändert, z.B. aus „Vögel können fliegen“ und „Tux ist ein Vogel“ folgt „Tux kann fliegen“, allerdings bleibt die Schlussfolgerung auch dann bestehen, wenn man „Tux ist ein Pinguin“ als Tatsache hinzunimmt. Monotone Logiken
können also bei Ausnahmen nicht richtig schlussfolgern. Aus diesen und anderen Gründen entstanden andere Repräsentationsformalismen wie die im Abschnitt 2.1.2 besprochenen semantischen Netze, Frames, Produktionsregeln, Beschreibungslogiken und
18
weitere. Im Rahmen dieser Arbeit werden wir jedoch nur auf die Beschreibungslogiken
im Kapitel 3 näher eingehen. Trotz der oben genannten Kritikpunkte wird die Logik als
das für Wissen am besten geeignete analytische Werkzeug angesehen. [OLN95]
2.1.5 Ontologien vs. Datenbank-Schemata
Heutzutage werden Daten und Wissen am häufigsten in relationalen Datenbanken gespeichert. Auch die Community IRCLOVE (Unterkapitel 2.3), die für unsere Zielsetzung als Fallbeispiel fungiert, basiert auf einer relationalen Datenbank. Die Grundlage
für das Design einer relationalen Datenbank bildet das so genannte Entity-Relationsship
(ER) Modell. Allgemein gesagt typisiert das ER-Modell Objekte und ihre Beziehungen
zueinander. Zwischen Ontologien und dem ER-Modell existieren viele Gemeinsamkeiten, die die Abbildung aus einer relationalen Datenbank in eine Ontologie erleichtern
und hier kurz umrissen werden sollen. Zum einen korrespondieren Entitäten und Relationen aus dem ER-Modell direkt mit Konzepten und Relationen der Ontologien. Dasselbe gilt für Attribute (ER-Modell) und Eigenschaften (Ontologie).
ER-Modell
Entität
Ontologie
Konzept
Relation
Relation
Attribut
Eigenschaft
Abb. 9: Äquivalente Abbildung zwischen den Kernelementen des ER-Modells und Ontologien.
Zum anderen entspricht die TBox einer Wissensbasis in gewisser Weise1 dem Datenbank-Schema. Das Datenbank-Gegenstück zur Abox bilden die Instanzen der Datenbank, sprich die Zeilen von Tabellen. Die Unterschiede der beiden Paradigmen liegen in
ihrer Spezialisierung. So werden Einschränkungen in Ontologien (auch Axiome genannt) hauptsächlich verwendet, um die Bedeutung der Konzepte im Hinblick auf die
Inferenz zu verdeutlichen. Dagegen benutzt man sie in Datenbanken, um die Integrität
1
Durch die Verwendung von Logik als Formalismus besitzt die TBox eine viel größere Ausdrucksstärke
als ein Datenbank-Schema.
19
von Daten zu gewährleisten. [UG04] Ein Beispiel sind so genannte
Kardinalitätseinschränkungen, die in Datenbanken vor allem für die Spezifikation der
Art einer Relation benutzt werden. In Ontologien werden Kardinalitäten eher zur Untermauerung der Bedeutung von Konzepten verwendet. Ontologien sind zudem für logisches Schlussfolgern ausgelegt, also insbesondere um neues Wissen herzuleiten, relationale Datenbanken dagegen nutzen optimierte Abfragesprachen wie SQL um vorhandenes Wissen schnell zu extrahieren.
2.1.6 Klassifizierung und Einsatzmöglichkeiten von
Ontologien
Seit Jahrtausenden versuchen Philosophen und heutzutage auch Informatiker
Ontologien zu formulieren, die allgemein genug sind, um die gesamte uns umgebende
Welt zu beschreiben. Platon, Aristoteles und Kant sowie berühmte moderne Theoretiker
wie Peirce oder Heidegger haben sich ausführlich mit dieser Aufgabe beschäftigt
[Sow00]. Trotz dieser bis heute nicht abgeschlossener Bemühungen ist es nicht gelungen, eine einheitliche Klassifizierung der Ontologien zu entwickeln. Es haben sich jedoch zwei grundsätzliche Ansätze herauskristallisiert. Der Erste besteht darin,
Ontologien nach dem Grad ihrer Komplexität zu kategorisieren. Dieser Ansatz wurde
von Lassila und McGuinness1, Mika2 und anderen diskutiert und verfeinert. Eine zusätzliche Unterscheidung in so genannte leicht- und schwergewichtige Ontologien (light-,
heavyweight ontology) ermöglicht eine grobe Einschätzung der Ontologiekomplexität.
Leichtgewichtige Ontologien tragen eher weniger Information über das Zusammenspiel
von Konzepten in sich. Im Vergleich dazu nutzen schwergewichtige Ontologien komplexere Werkzeuge wie Einschränkungen oder zusammengesetzte Klassen und beschreiben eine Domäne deshalb präziser. Abb. 10 zeigt zudem, dass Traktabilität einer
Ontologiesprache (bzw. ihres zugrunde liegenden Formalismus), d.h. der Grad der Verwendbarkeit in der Praxis bezogen auf algorithmische Komplexität, mit fallender
Ontologiekomplexität stets zunimmt. Dieser Trade-off zeigt auch, dass man Ontologien
ebenso gut nach der Traktabilität ihres Formalismus ordnen könnte.
1
LASSILA, O., MCGUINNESS D.: The Role of Frame-Based Representation on the Semantic Web. Technical Report KSL-01-02, California, Stanford University. (2001)
2
MIKA, Peter: Social Networks and the Semantic Web. Boston, Springer Verlag. (2007)
20
Glossare
Begriffsmengen
Lightweight Ontologien
Konzeptgraphen
[RDF(S), OWL Lite etc.]
Thesauri
Semantische Netze
Heavyweight Ontologien
[Beschreibungslogik, PL1]
Komplexität
Traktabilität
Abb. 10: Klassifizierung von Ontologien nach ihrer Komplexität.
Der zweite Ansatz besteht darin, Ontologien nach der Art des repräsentierten Wissens
zu klassifizieren. Da Ontologien, wie oben erwähnt, sehr abstrakt oder wie man später
sehen wird, sehr spezifisch sein können, ist eine präzise Klassifizierung ein äußerst
schwieriges Unterfangen. Da es viele Vorschläge zu einer solchen Klassifizierung gibt
[GFC04], sie alle vorzustellen aber den Rahmen dieser Arbeit sprengen würde, gehen
wir lediglich auf einen übersichtlichen und verständlichen Vorschlag von Guarino in
[Gua98] ein. Er schlägt die folgende Aufteilung von Ontologien vor:
Top-Level Ontologien – beschreiben sehr abstrakte Dinge wie Raum, Zeit,
Materie usw. und sind domänenunabhängig.
Domänen- und Aufgabenontologien – beschreiben eine bestimmte Domäne
(z.B. Autos oder Benutzerprofile) bzw. eine bestimmte Aufgabe (z.B. Verkauf).
Applikationenontologien – stellen eine Spezialisierung der beiden oberen
Ontologietypen dar und beschreiben eine bestimmte Aufgabe in einer bestimmten Domäne (z.B. Verkauf von Autos).
Top-Level Ontologie
Domänenontologie
Aufgabenontologie
Applikationenontologie
Usability
Re-Usability
Abb. 11: Klassifizierung von Ontologien nach ihrem Inhalt in Anlehnung an [Gua98].
Betrachtet man Ontologien von diesem Standpunkt, so offenbart sich auch hier ein Trade-off zwischen Usability und Re-Usability, je spezieller eine Ontologie, desto einfacher ist es, sie zu nutzen, aber desto schwieriger, sie für andere Aufgaben einzusetzen.
21
Aus den Klassifizierungsbetrachtungen wird bereits klar, wie vielseitig Ontologien eingesetzt werden können. Semantische Technologien fanden mit der Zeit ihren Weg aus
der reinen Forschung in diverse Unternehmensbereiche. So zählt Fensel in [Fen04] Wissensmanagement, E-Commerce (Business-to-Customer und Business-to-Business) sowie Integration von Geschäftsprozessen zu den wichtigsten Einsatzbereichen der
Ontologien. Nach Meinung von Reichenberger [Rei10] ist die semantische Suche (also
eine Suche, die auf die Bedeutung von Begriffen statt auf ihr bloßes Auftreten, wie bei
der Vollsuche eingeht) die häufigste Möglichkeit, wie semantische Technologien in Unternehmen eingesetzt werden können. Andere Aufgaben sind unter anderem Harmonisierung oder Aufbau von strukturierten Daten. Auch im Bereich E-Learning spielen semantische Technologien, insbesondere so genannte Concept Maps1 und Mind Maps eine große Rolle.
Der Einsatz von Ontologien beschränkt sich aber nicht nur auf reine Verbesserung der
Repräsentation von Daten. Ontologien bilden den Kern der Wissensrepräsentation für
Bereiche wie Maschinelles Lernen oder Expertensysteme. Auch für die Idee des
Semantic Web sind Ontologien unentbehrlich, wie die jahrelange und voranschreitende
Entwicklung der Ontologiesprache OWL zeigt. Die Fähigkeit mit formalen Ontologien
effektive Rückschlüsse über Daten zu ziehen erweitert also ihren Einsatzbereich auf
komplexe Datenstrukturen und Aufgabenstellungen.
Die in dieser Arbeit zu entwickelnde Ontologie soll nach der Klassifizierung aus Abb.
11 eindeutig eine Domänenontologie darstellen, die allgemein genug sein sollte, um in
jeder Domäne mit Profilen eine vielfältige Analyse zu ermöglichen.
2.2 Web Ontology Language
Das vorherige Unterkapitel beschäftigte sich vor allem mit Ontologien im Allgemeinen.
Obwohl die Ontologiesprache OWL in dieser Arbeit keine direkte Anwendung findet,
werden wir im weiteren Verlauf immer wieder auf Formalismen stoßen, die ihr entweder zugrunde liegen oder auf ihr basieren. Deshalb werden wir in diesem kurzen Unterkapitel sie etwas aus der Nähe betrachten und ihren Aufbau erläutern.
1
NOVAK, J. D.: Learning, Creating, and Using Knowledge: Concept Maps as Facilitative Tools in
Schools and Corporations. London, Lawrence Erlbaum Associates. (1998)
22
2.2 Web Ontology Language
2.2.1 Teilsprachen von OWL
OWL entstand als Nachfolger der Ontologiesprache DAML+OIL1, die 2001 von einem
US/EU Konsortium, dem so genannten Agent Markup Language Committee eingeführt
wurde [Fen04]. Wie schon im Abschnitt 2.1.3 erwähnt baut OWL auf RDF(S) auf. Die
erste Version von OWL (wir werden sie zukünftig OWL 1 bezeichnen) erreichte im
Jahr 2004 den Status einer W3C Recommendation. OWL 1 spaltet sich in 3 Teilsprachen, die nach ihrer Mächtigkeit angeordnet sind:
OWL Lite ⊂ OWL DL ⊂ OWL Full
Dabei sind OWL Lite und OWL DL entscheidbar, OWL Full dagegen nicht. Dafür ist es
OWL Full als einziger Teilsprache erlaubt, die volle RDF(S) Syntax zu benutzen
[OWLGD]. Von praktischer Bedeutung ist jedoch nur OWL DL und OWL Lite. Der an
der Stanford University entwickelte grafische Ontologie-Editor Protégé 3.x2 ist das am
meisten verbreitete Tool, um OWL 1 Ontologien zu konzipieren.
Im Jahr 2009 spezifizierte das W3C die Nachfolgerversion OWL 2, wobei OWL 2 DL
und OWL 2 Full so wie bei OWL 1 spezifiziert wurden. Die Teilsprache OWL Lite
wurde in 3 traktable Sprachen aufgeteilt, die allerdings keine echten Teilmengen voneinander sind. Das W3C legte die Teilsprachen, die „Profile“ heißen, in Hinsicht auf ihre
Anwendung in der Praxis fest3:
OWL EL wurde für Ontologien optimiert, die eine große Anzahl von Klassen
und Rollen haben. Die Inferenz läuft hier in polynomieller Zeit.
OWL QL wurde so konzipiert, dass eine bessere Abbildung von relationalen Datenbanken zu OWL gewährleistet ist. Insbesondere wurde dieses Profil optimiert, um Inferenz bei einer großen Anzahl von Individuen zu beschleunigen.
OWL RL wurde in Anlehnung an DLP (description logic programs) gestaltet
und ermöglicht eine vereinfachte Implementierung von regel-basierten Technologien.
Protégé 4.x ist das Gegenstück zu der 3-Serie, um mit OWL 2 Ontologien umzugehen,
leidet aber zum gegenwärtigen Zeitpunkt noch an einigen „Kinderkrankheiten“. Neben
Protégé existieren einige weitere OWL-unterstützende Editoren.
1
http://www.daml.org/2001/03/daml+oil-index.html (geprüft am 6. Mai 2011)
http://protege.stanford.edu/ (geprüft am 6. Mai 2011)
3
http://www.w3.org/TR/2009/REC-owl2-primer-20091027/#OWL_2_DL_and_OWL_2_Full (geprüft
am 6. Mai 2011)
2
23
2.2.2 Unterschiede zu RDF(S) und Besonderheiten
Wir werden im Rahmen dieser Arbeit nicht auf die konkrete OWL Syntax eingehen,
sondern lediglich auf besondere Merkmale dieser Ontologiesprache. OWL wurde in erster Linie entwickelt, um die durch RDF definierten Graphen zu erweitern. Grundsätzlich
besteht eine OWL Ontologie aus Klassen (Konzepten), Properties (Rollen) und Individuen (ABox). Um das Beispiel aus Abb. 7 in OWL abzubilden, können wir uns z.B.
zwei Klassen „Diplomarbeit“ und „Thema“ mit der Rolle „hatThema“ definieren. Im
Vergleich zu RDF(S) ist es jedoch möglich, komplexere Beziehungen zwischen Klassen
bzw. Rollen zu definieren. Dazu zählen Kardinalitätsrestriktionen, Beziehungen zwischen Individuen, abgeschlossene Klassen, Rollenvererbung und Eigenschaften wie
Transitivität sowie Datentypisierung. In dem unteren Beispiel verwenden wir die
OWL 2 Syntax um eine Kardinalitätseinschränkung für die Rolle „hatThema“ zu definieren und zwar so, dass zu jeder Diplomarbeit genau ein Thema existieren darf. Mit
einer solchen einfachen Konstruktion ließe sich nun durch das Einfügen von Individuen
in die jeweiligen Klassen eine vollwertige Wissensbasis aufbauen.
1. <owl: Class rdf:about=“Diplomarbeit“/>
2. <owl: Class rdf:about=”Thema”/>
3. <owl:ObjectProperty rdf:about=”hatThema”>
4.
<rdfs:domain rdf:resource=”Diplomarbeit”/>
5.
<rdfs:range rdf:resource=”Thema”/>
6.
<rdfs:range>
7.
<owl:Restriction>
8.
<owl:onProperty rdf:resource="hatThema"/>
9.
<owl:onClass rdf:resource="Diplomarbeit"/>
10.
<owl:qualifiedCardinality rdf:datatype="">1</owl:qualifiedCardinality>
11. </owl:Restriction>
12. </rdfs:range>
13. </owl>
Diplomarbeit
hatThema
1
Thema
Abb. 12: Eine einfache OWL 2 Ontologie analog zu dem Beispiel aus Abb. 7.
Es ist in OWL möglich, so genannte Annotationen bestimmten Objekten zuzuweisen.
Diese Annotationen können zum Beispiel verwendet werden, um Kommentare über Objekte zu schreiben. Der Unterschied zwischen OWL 1 und OWL 2 besteht darin, dass in
OWL 2 Annotation zu allen Axiomen verfasst werden können, beispielweise zu der
Kardinalitätsrestriktion im oberen Bild. Diese Tatsache erweist sich im Bezug auf die
Integration von zusätzlichen Informationen in OWL als äußerst nützlich und wird in
Hinsicht auf unsere Absicht probabilistische Informationen zu verarbeiten im Kapitel 3
näher erläutert.
24
2.3 Die Community IRCLOVE
Im Rahmen dieser Arbeit soll die Anwendung der entwickelten Ontologie an dem konkreten Szenario der Ähnlichkeitsanalyse gezeigt werden. Dabei werden wir bei unseren
Experimenten reale Daten aus der, vom Verfasser der Arbeit konzipierten und entwickelten, Online-Community IRCLOVE verwenden und ihre Struktur berücksichtigen. In
diesem Unterkapitel stellen wir IRCLOVE nun näher vor.
2.3.1 Einleitung
Die Online-Community IRCLOVE wurde entwickelt, um Menschen das gegenseitige
Kennenlernen zu ermöglichen. Dabei kann man die Webseite als eine Mischung einer
gewöhnlichen Anzeigenseite und eines Autorenportals bezeichnen. Der thematische
Schwerpunkt liegt auf dem Thema „Liebe“, das hier im abstrakten Zusammenhang betrachtet wird. Es werden zahlreiche Informationen, wie z.B. Liebesgedichte angeboten.
Somit zählen zu der Zielgruppe von IRCLOVE eher Menschen, die keine gewöhnlichen kommerziellen Webportale zur Partnersuche nutzen, sondern eher nach Gleichgesinnten Ausschau halten. Die Entwicklung und Betrieb der Webseite findet ehrenamtlich statt. Die Anmeldung sowie Mitgliedschaft in der Community sind kostenfrei.
Die technische Basis hinter IRCLOVE ist eine Kombination der WebProgrammiersprache PHP1 und der relationalen Datenbank MySQL2. Beide Technologien erlangten durch ihre Spezialisierung und Optimierung auf Internet-Applikationen
hohe Popularität und werden sehr häufig als „Engine“ für dynamische Webseiten verwendet.
2.3.2 Struktureller Aufbau
Wie jede Online-Community besteht auch IRCLOVE aus bestimmten Kernelementen.
Im Folgenden sollen sie näher vorgestellt werden, dabei bezeichnet die Schreibweise
„(N~)“ das zum Zeitpunkt der Fertigstellung dieser Arbeit vorhandene Datenvolumen.
Jedes IRCLOVE Mitglied (N~37.500) verfügt über ein Profil. Zu den Grundfunktionen,
die ein Benutzer ausführen kann, gehört die Suche nach anderen Mitgliedern in ver-
1
2
The PHP Group: http://www.php.net (geprüft am 6. Mai 2011)
Oracle Corporation: http://www.mysql.de (geprüft am 6. Mai 2011)
25
schiedenen Detailstufen, ein Nachrichtensystem mit einer In-/Outbox, eine Favoritenliste, in der ein Benutzer seine Freunde speichern kann, ein Chatsystem, sowie Möglichkeiten Profilbilder anderer Benutzer zu bewerten und diverse Rankings und Statistiken
anzuschauen.
Abb. 13: Die Hauptansicht von IRCLOVE nach dem Einloggen.
Jeder Benutzer ist in der Lage eine eigene Medienbibliothek anzulegen. Diese ist ein
Bestandteil seines Profils und ermöglicht eine kreative oder gar künstlerische Entfaltung. Alle Bibliotheken (N~780) werden in einem Bereich der Webseite namens
„IRCLOVE Persönlichkeiten“ zusammengefasst. Da dieser Bereich relativ komplex und
für das Vorhaben Profile auf Gemeinsamkeiten zu untersuchen sehr nützlich ist, wird
auf ihn weiter unten gesondert eingegangen.
2.3.3 IRCLOVE Datenbank
Die Datenbank hinter IRCLOVE ist eine relationale Datenbank auf Basis von MySQL
4. Die gesamte Datenbank besteht gegenwärtig aus 38 Tabellen und hat eine Größe von
über 6 GB und 2,9 Mio. Zeilen. Zu dem relativ großen Volumen tragen vor allem die
Inhalte der Medienbibliotheken der Benutzer bei. Die Datenbank ist so konzipiert, dass
gewisse strukturelle Suchanfragen schnell ablaufen. Betrachtet man die Gesamtheit der
26
SQL-Abfragen, so kann man die IRCLOVE Datenbank als eher READ-lastig bezeichnen, d.h. die Mehrzahl der Abfragen besteht aus SELECT Abfragen. Dieses Verhalten
ist grundsätzlich typisch für Online-Communities, weil bei ihnen Informationen oft abgerufen, aber selten hinzugefügt oder verändert werden.
In dieser Arbeit interessieren wir uns insbesondere für die verschiedenen Ausprägungen
der Benutzerprofile, sowie die Möglichkeiten der Benutzer, miteinander interagieren zu
können. Die Abb. 14 zeigt Teile des Datenbank-Schemas von IRCLOVE. Wie man
leicht erkennt, gibt es zwei Schwerpunkte: die Tabellen „users“ (N~38.000) und
„mediadb_index“ (N~15.000). Diese Tabellen enthalten Informationen über die Benutzerprofile resp. Medien in den Bibliotheken der Benutzer. Sie sind zentral, da sie Primärschlüssel definieren, die in zahlreichen anderen Tabellen verwendet werden. Diese
Referenztabellen speichern wiederum Informationen über gewisse Aktionen der Benutzer. So speichert beispielsweise die Tabelle „mediadb_viewhistory“ (N~230.000) die
eindeutigen Medienlesungen (d.h. die Tatsache, dass ein Benutzer ein Medium angeschaut hat). Die Tabelle „mediadb_itemvotehistory“ (N~45.000) speichert die Bewertungen zu den Medien, „mediadb_comments“ (N~3.500) die Kommentare und
„mediadb_hphistory“ (N~1500) die Auszeichnungen der Medien.
27
Abb. 14: Ausschnitt des IRCLOVE Datenbank-Schema – das Benutzerprofil und Medienbibliothek Subsystem.
28
2.3.4 Benutzerprofile
Wir widmen uns nun den Benutzerprofilen in IRCLOVE. Wie Abb. 15 zeigt, ist die Registrierung in der Community völlig anonym. Es werden keine persönlichen Daten über
Personen gespeichert, insbesondere auch kein Name, Adresse und Telefonnummer. Der
Benutzer wird anhand eines Benutzernamens identifiziert. Für Kommunikationszwecke
und Vermeidung gefälschter Anmeldungen wird eine Email-Adresse gespeichert und
bei der Registrierung durch eine Verifizierungsemail überprüft.
Abb. 15: Einfaches Registrierungsformular (Schnellregistrierung) bei IRCLOVE.
Der Benutzer hat die Möglichkeit, zahlreiche Informationen in sein Profil einzugeben:
•
Alter (wird aus Geburtsdatum errechnet) und Geschlecht.
•
Haarfarbe, Augenfarbe, Größe, Gewicht (optional).
•
PLZ und Wohnort (optional).
•
Weitere Angaben wie Kinderwunsch, Anzahl der Kinder usw. (optional).
•
Beruf, Musikpräferenzen (optional).
•
Hobbys und Interessen (optional).
•
Beschreibungstexte, mit denen sich der Benutzer vorstellen kann (optional).
•
So genannte Extras, mit deren Hilfe zusätzliche Merkmale definiert werden können.
Die Extras bestehen je aus einem Tupel (Eigenschaft, Wert) z.B. (Schuhgröße, 44).
Wie viele andere Dinge kann ein Profil in IRCLOVE von anderen Benutzern bewertet
werden. Obwohl aus Anonymisierungsgründen die eigentliche Note nicht gespeichert
wird, kann eine Zuordnung anhand der Tabelle „vote_history“ (N~80.000) vorgenommen werden.
29
Abb. 16: Exemplarische Darstellung eines Profils bei IRCLOVE.
Das Hauptbild des Benutzers kann in einer randomisierten Bewertung von anderen Benutzern bewertet werden. Diese Information wird in „photovote_history“ (N~1,9 Mio.)
gespeichert. Da bei dem Bewertungsverfahren einem Benutzer zufällig Bilder gezeigt
werden, kann das Bewerten nicht als eine gezielte Handlung interpretiert und im Sinne
dieser Arbeit verwertet werden.
30
2.3.5 Ein genauerer Blick auf „IRCLOVE Persönlichkeiten“
Wie bereits oben erwähnt, beinhaltet der Bereich „IRCLOVE Persönlichkeiten“1 die
Medienbibliotheken der einzelnen Benutzer. In diesem Abschnitt wird speziell auf die
Struktur dieses Bereichs eingegangen. In IRCLOVE entsprechen „Medien“ den einzelnen Einträgen der Benutzerbibliothek. Diese Medien können verschiedene Typen haben, die die Beschaffenheit der Medien definieren. Momentan erlaubt sind Medien des
Typs Bild, Text, Video, Umfrage und iHTML (das Letztere stellt eine, auf IRCLOVE
zugeschnittene, restriktive Version von HTML dar). Die Medientypen sind fest implementiert und werden nicht in Referenztabellen festgehalten. Die Bibliothek von Benutzern besteht aus Ordnern. Nach der Anmeldung steht dem Benutzer ein so genannter
Standard-Ordner zur Verfügung.
Später können weitere Ordner
erstellt werden, welche wiederum
Unterordner beinhalten können.
Diese Unterordner können wieder
neue Unterordner enthalten, so
dass die Tiefe einer solchen Verschachtelung von Ordnern ist
nicht beschränkt ist. Die Medien
werden in Ordner geladen bzw.
dort erstellt. Somit entspricht die
Struktur der Bibliothek exakt einer gewöhnlichen Dateisystem-
Abb. 17: Beispiel einer Ordner-Übersicht in einer Bibliothek.
Struktur. Man kann diese Anschauung als die erste Sicht auf den Bereich „Persönlichkeiten“ bezeichnen.
Ein Medium unterliegt einer strengen Klassifizierung. Während ein Benutzer ein neues
Medium anlegt, muss er es einer Kategorie zuordnen, die vom Medientyp abhängig ist.
Alle Kategorien sind in einem hierarchischen Baum angeordnet, wobei die Tiefe des
Kategorienbaums unbegrenzt ist. IRCLOVE unterscheidet zwischen Level-1 Kategorien
(N=10) und Subkategorien (N~550). Level-1 Kategorien sind den Medientypen recht
ähnlich, obwohl zwei verschiedene Kategorien denselben Medientyp fassen können,
beispielsweise handeln „Gedicht“ und „Geschichte“ beide von dem Medientyp „Text“.
Level-1 Kategorien bilden die Ankerpunkte der Hierarchie und können sinngemäß keine
1
Unter http://art.irclove.de erreichbar. (geprüft am 6. Mai 2011)
31
Medien aufnehmen. Die Subkategorien sind dagegen flexibel und die Administrationsoberfläche ermöglicht u. a. das Umhängen ganzer Teilbäume. Findet der Benutzer keine
passende Kategorie, kann er eine neue anlegen und sein Medium dort einsortieren. Diese „Benutzerkategorien“ sind jedoch temporär und werden erst nach einer administrativen Kontrolle zum festen Bestandteil der Hierarchie. Die Gestaltung der Kategorien geschieht somit in Zusammenarbeit der Administratoren und Benutzer der OnlineCommunity.
Das oben beschriebene Modell wird auch als Closed Topic Model (CTM) bezeichnet.1
Wir möchten näher erklären, wie CTM’s definiert sind: ein CTM ist durch ein Klassifizierungsschema gegeben und bildet im Grunde eine terminologische Ontologie, d.h. eine bei der die Konzepte bestimmte Themen (topics oder areas of interest) bezeichnen.
Solche Klassifizierungsschemata werden durch eine kleine Gruppe von Experten verwaltet und kontrolliert, wodurch eine typische Eigenschaft von CTM’s ersichtlich wird
– sie verändern sich sehr langsam. Man beachte, dass gerade diese Tatsache im Widerspruch zur realen Welt der Menschen und der Vielzahl ständig neu aufkommender Begriffe und Themen steht. Zugleich aber garantieren CTM’s durch ihre relativ starre
Struktur die Vergleichbarkeit von Klassifizierungsergebnissen und eine universelle
Möglichkeit, die Information in ähnliche Strukturen zu übertragen. Aus diesem Grund
werden Closed Topic Modelle oft in digitalen Bibliotheken genutzt.
Die nächste Abbildung zeigt, wie ein Klassifizierungsschema (speziell für IRCLOVE ist
es der Kategorienbaum) aussieht. Man beachte auch, dass die neben den Kategoriennamen stehende Benutzernamen die so genannten Kategorien-Inhaber kennzeichnen, d.h.
die Personen, die die Kategorie ursprünglich erstellt haben. Diese kann man auch als
Verwalter des Themas ansehen.
1
MEHLER, A., WALTINGER, U.: Enhancing Document Modeling by Means of Open Topic Models. Library
Hi Tech Vol. 27 Issue 4, Emerald Group Publishing. (2009) 520-539
32
Abb. 18: Darstellung eines Teils des Kategorienbaums im IRCLOVE Admin-Interface.
Die Klassifizierung ermöglicht schließlich eine zweite Sicht auf „Persönlichkeiten“ mit
deren Hilfe ein Benutzer durch die Kategorien navigieren und für ihn interessante Informationen schnell finden kann. Diese Sicht wurde verwendet, um das Autorenportal
von IRCLOVE zu konzipieren. Ein Beispiel findet sich in Abb. 19.
Abb. 19: Unterkategorie Foto→Tiere→Säugetiere→Nagetiere→Ratten im IRCLOVE Autorenportal.
Zusammenfassend kann „IRCLOVE Persönlichkeiten“ als eine klassische digitale Bibliothek mit 2 Sichten betrachtet werden, denen ein CTM zugrunde liegt. Die streng hie-
33
rarchische Struktur ermöglicht Schlussfolgerungen über Interessenschwerpunkte von
Benutzern, die wir im Rahmen der Ähnlichkeitsanalyse von Profilen benutzen möchten.
Das Verhalten von Benutzern im Bezug auf die Bibliotheken lässt sich über Wahrscheinlichkeitsverteilungen ausdrücken. Diese können wiederum verwendet werden, um
Profilinformationen anzureichern. Insofern bietet diese Plattform ein mächtiges Hilfsmittel, um Interessensschwerpunkte von realen Personen besser zu identifizieren und
verarbeiten zu können. Allerdings besteht die notwendige Voraussetzung, dass ein
IRCLOVE Benutzer die Funktionalität auch benutzt. Zum gegenwärtigen Zeitpunkt besitzen nur etwa 4.5% der Benutzer eine eigene Bibliothek.
Zum Abschluss des Abschnitts gehen wir auf die möglichen Interaktionen der Benutzer
innerhalb des Portals ein. Ein Überblick ist in Abb. 20 dargestellt. Alle Interaktionen
sind eindeutig in der Datenbank gespeichert, d.h. schaut sich z.B. ein Benutzer ein Medium doppelt an, wird für dieses Ereignis nur ein Eintrag abgelegt (unique view). Obwohl eine redundante Speicherung für die Zwecke dieser Arbeit vom Nutzen wäre, um
Schwerpunkte noch schärfer identifizieren zu können, war dies für das ursprüngliche
Design der Webseite nicht notwendig.
beobachtet
Ordner
beobachtet
kommentiert
Medium
Autor ordnet zu
liest
User
bewertet
auszeichnet
Kategobeobachtet
Abb. 20: Interaktionsströme innerhalb von IRCLOVE Persönlichkeiten.
34
2.3.6 Zusammenfassung möglicher Matching-Faktoren
Nachdem wir uns die Community angeschaut haben, können Faktoren benannt werden,
die man als Informationsquelle in unserer Ontologie verwenden könnte. Zunächst sollen
Informationen betrachtet werden, die aus dem Bereich „IRCLOVE Persönlichkeiten“
extrahieren werden können. Dabei fassen wir eine Aktion eines Benutzers zusammen
mit seinem Bezugspunkt als eine stochastische Zufallsvariable auf. Die Wahrscheinlichkeitsverteilung errechnet sich dann über alle möglichen Werte des Bezugspunktes.
Wird beispielsweise die Aktion „lesen“ zusammen mit dem Bezugspunkt „Kategorien“
betrachtet, dann wäre die folgende Verteilung der Zufallsvariable möglich: „Foto:Katzen“:0.2, „Text:Tiere“:0.1, „Zeichnung:Ratten“:0.7. In IRCLOVE werden für jede Aktion Informationen zusammen mit dem Benutzer (als Fremdschlüssel) in einer
Tabelle gespeichert (vgl. Abschnitt 2.3.3 und Abb. 14). Deshalb kann man solche
Wahrscheinlichkeitsverteilungen mit Hilfe von aggregierenden SQL Befehlen aus der
IRCLOVE Datenbank problemlos extrahieren und einem Benutzer zuordnen. Im Anhang IV finden sich einige Beispiele von Verteilungen bezüglich einiger Aktionen, die
im Rahmen der Experimente verwendet wurden. Abschließend fasst Tabelle 1 die Interaktionen des Bereichs „Persönlichkeiten“ zusammen:
Aktion
Bezugspunkt
lesen
bewerten
kommentieren
auszeichnen
beobachten (Kategorie)
beobachten (Ordner)
beobachten (Bibliothek)
beobachten (Medium)
Medien- (Kategorie, Autor)
Kategorie
Ordner-Autor
Bibliothek-Autor
Tabelle 1: Zusammenfassung möglicher Interaktionen in „Persönlichkeiten“ als Zufallsvariablen.
Kommen wir nun zu den Informationen aus Benutzerprofilen. Anders als oben betrachtet man in diesem Fall keine Handlungen von Benutzern, sondern Informationen, die sie
eingegeben haben. Ohne einen Bezugspunkt kann deshalb keine Wahrscheinlichkeitsverteilung ermittelt werden – die Profilinformationen sind fast statisch. Allerdings reicht
das völlig aus, um Anhaltspunkte zu finden, die bei der Ermittlung der Ähnlichkeit von
Benutzern oder anderen Fragestellungen helfen könnten. Beispielsweise kann ein Benutzer seine Hobbys als eine kommagetrennte Zeile eingeben. Die Angabe von gemeinsamen Hobbys ist mit Sicherheit ein Anzeichen für Ähnlichkeit. Problematisch ist jedoch die genaue Abgrenzung der Begriffe, da der Benutzer in IRCLOVE die Hobbys
nicht aus einer Liste auswählt sondern frei eingibt.
35
In Tabelle 2 sind alle relevanten Informationen aus den Benutzerprofilen zusammengefasst. Dabei bezeichnet „Struktur“ die Beschaffenheit der jeweiligen Ausprägung in
Hinsicht auf eine mögliche Analyse.
Merkmal
Struktur
Alterssegment
Geschlecht
Postleitzahl
Wohnort
Single-Status
Beruf
Hobbys
Musikvorlieben
benutzerdefinierte Eigenschaften
diskret
diskret
möglicherweise unvollständig
nicht klassifizierter Freitext
diskret
Tabelle 2: Zusammenfassung relevanter Profilmerkmale von IRCLOVE.
Zusätzlich zu den Profilmerkmalen können noch folgende Interaktionen von Benutzern
relevant sein:
36
•
Bewertung des Profils eines anderen Benutzers zeugt von Interesse an dieser Person.
•
Freundschaftsliste: fügen sich zwei Benutzer gegenseitig der Freundschaftsliste hinzu spricht das dafür, dass sich die beiden bereits kennen gelernt hatten.
KAPITEL 3. PROBABILISTISCHE
ONTOLOGIEN
In den letzten Jahren wurden seitens der Forschergemeinschaft bedeutende Anstrengungen unternommen, Formalismen zur Beschreibung von probabilistischen Ontologien zu
entwickeln. Dies ist vor allem darauf zurückführen, dass mit der Verwendung von
Wahrscheinlichkeitsinformationen reichhaltige und interessante Informationen extrahiert, Fragen beantwortet und realitätsnahe Ontologien modelliert werden können. Für
die Konzeption einer probabilistischen Ontologie, wie sie in dieser Arbeit entstehen
soll, ist die Wahl des „richtigen“ Formalismus von zentraler Bedeutung. Deshalb werden wir in diesem Kapitel auf den aktuellen Forschungsstand der Repräsentation von
probabilistischen Ontologien eingehen und die wichtigsten Formalismen beschreiben.
Dabei konzentrieren wir uns zuerst auf Formalismen, die auf Beschreibungslogiken basieren und werden danach das Statische Relationale Lernen als eine relativ neue und
viel versprechende Forschungsrichtung vorstellen. Am Ende folgt die Begründung, warum gerade die Markov Logic Networks am geeignetsten für die Realisierung der Zielsetzung dieser Arbeit erschienen.
3.1 Warum Wahrscheinlichkeiten?
Die in Unterkapitel 2.3 bereits erfolgte Betrachtung der IRCLOVE Community zeigt,
dass viele Daten in der Domäne „Social Networks“ nicht nur rein statischer Natur sind.
Auch ein Konsument oder Geschäftskunde kauft nicht immer dieselben Dinge, allerdings liegen seinen Käufen oft Wahrscheinlichkeitsverteilungen zugrunde, die auf seine
Präferenzen hindeuten. Menschliches Verhalten lässt sich also nicht mit einem einfachen Ja und Nein eindeutig beschreiben, es unterliegt stattdessen häufig bestimmten
Mustern. Die Erkenntnis lässt sich zudem stark verallgemeinern - schaut man auf andere
Bereiche, so stellt man fest, dass unsere Welt in höchstem Maße relativ ist. Selbst einfache Konzepte lassen sich oft nicht eindeutig definieren, so denkt man gewöhnlich beim
Wort „Fahrzeug“ an ein Auto, das fast immer 4 Räder hat. Es gibt aber auch Autos oder
andere Fahrzeuge, die weniger oder mehr Räder haben. Dennoch erkennen wir Menschen ein Fahrzeug mit nahezu hundertprozentiger Wahrscheinlichkeit. Es ist offen-
37
KAPITEL 3. PROBABILISTISCHE ONTOLOGIEN
sichtlich, dass zufallbedingtes Wissen für die Beschreibung von komplexen Domänen
unabdingbar ist.
In den Anfängen der Forschung im Bereich der Wissensrepräsentation beschäftigte man
sich grundsätzlich mit der Möglichkeit, präzises Wissen in einer für Maschinen verständlichen und effizienten Form darzustellen. Man entwickelte und verfeinerte Logiken
und schuf damit exakte Formalismen, die sehr mächtig sind. In der letzten Dekade gewann die Problemstellung, probabilistische Informationen in Formalismen, die
Ontologien zugrunde liegen, zu integrieren und zu verarbeiten stark an Bedeutung. Die
Verwendung probabilistischer Informationen in einer Ontologie ist ein Kernpunkt der
Zielstellung dieser Diplomarbeit. Deshalb war es außerordentlich wichtig, den „richtigen“ Formalismus zum Erreichen dieses Ziels zu finden. Da wie man oben gesehen hat,
„richtig“ und „falsch“ sehr relativ ist, werden wir neben einem Überblick über den aktuellen Stand in der probabilistischen Forschung auch die Wahl der Markov Logic Networks diskutieren und begründen.
3.2 Wahrscheinlichkeiten in Beschreibungslogiken
3.2.1 Beschreibungslogiken im Allgemeinen
Beschreibungslogiken (DL) entstanden als eine Erweiterung der Semantischen Netze
um eine formale Semantik. Das erste DL-basierte System KL-ONE [BS85] wurde bereits im Jahr 1985 entwickelt. Seitdem wurden viele weitere Beschreibungslogiken formuliert. Grundsätzlich versucht man mit Beschreibungslogiken, eine Teilmenge der
PL1 mit großer Ausdrucksstärke zu finden, die entscheidbar und traktabel ist [Fen04].
Diese zwei Eigenschaften zeichnen diesen Repräsentationsformalismus zwar aus, im
Bezug auf Traktabilität gibt es allerdings große Unterschiede. Eine DL-Wissensbasis
besteht ontologie-typisch aus Konzepten, Rollen und häufig einer ABox mit Definitionen der Fakten. Heutige Beschreibungslogiken bauen alle auf der von Schmidt-Schauß
und Smolka eingeführten Logik ALC [SS91] auf [BN03]. Diese ist durch die folgende
Grammatik gegeben:
C, D → A ¬ C C ó D
Cò D
∀R.C ∃R.C
wobei A primitives Konzept, C und D zusammengesetzte Konzepte darstellen. Die Allund Existenzquantoren spezifizieren eine so genannte universelle bzw. existenzielle
Restriktion eines Konzeptes bezüglich einer Rolle. Zum Beispiel steht
38
∃hatThema.Wissen für alle Konzepte, die bei der Rolle „hatThema“ den Endpunkt
„Wissen“ haben (z.B. Diplomarbeiten, die unter anderem das Thema „Wissen“ haben).
Analog definiert ∀hatThema.Wissen alle Konzepte, die bei der Rolle „hatThema“ ausschließlich Endpunkte „Wissen“ haben (z.B. Diplomarbeiten, die ausschließlich das
Thema „Wissen“ haben). Die Entwicklung probabilistischer Beschreibungslogiken konzentrierte sich vor allem auf die Erweiterung von Logiken, welche die Grundlage für
OWL bilden und deshalb als nächstes vorgestellt werden sollen.
3.2.2 P-SHIF(D) und P-SHOIN(D)
Die Teilsprachen OWL Lite und OWL DL von OWL können auf die Beschreibungslogiken SHIF(D) bzw. SHOIN(D) abgebildet werden [HP03]. Das bedeutet ebenfalls,
dass das Schlussfolgern in diesen Varianten von OWL genau dem Schlussfolgern in den
beiden Beschreibungslogiken entspricht. In [Luk07] werden probabilistische Versionen
dieser Logiken, nämlich P-SHIF(D) bzw. P-SHOIN(D) vorgestellt.
In den beiden Logiken werden Wahrscheinlichkeiten durch so genannte conditional
constraints repräsentiert [Luk07]. Diese Einschränkungen beschreiben Wahrscheinlichkeitsintervalle für Beziehungen innerhalb der Logik, speziell die kleinste und größte
Wahrscheinlichkeit, mit der ein Mitglied einer Klasse ebenfalls in einer anderen Klasse
ist (Subsumption). Die Wahrscheinlichkeit eines Konzeptausdrucks gilt somit unter der
Vorbedingung eines anderen Konzeptes. Ohne auf weitere Details einzugehen, die ergänzend [Luk07] entnommen werden können, zeigen wir im nächsten Beispiel, wie man
die in der Einleitung beschriebene Situation mit Benutzern Paul und Anna in
P-SHOIN(D) formulieren könnte:
I P = {Paul, Anna}
T = {User ô Person, Katze ô Bild ô Kategorie}
) [ 0.7, 0.7 ] , (User |• ) [1,1]}
= {( ∃reads.Katze |• ) [ 0.8, 0.8] , (User |• ) [1,1]}
PPaul = {( ∃reads.Katze |•
PAnna
I P bezeichnet die Menge der probabilistischen Individuen, T die TBox im klassischen
Sinne und PPaul , PAnna die eigentlichen conditional constraints. Die Wissensbasis beschreibt also, dass sich Paul und Anna zu je 70% bzw. 85% Katzenbilder anschauen.
39
Man beachte, dass für unsere Zielsetzung die Nutzung von Intervallen keinen Mehrwert
bringt.
Eines der großen Probleme vieler Beschreibungslogiken, und auch von P-SHIF(D)
bzw. P-SHOIN(D), ist die hohe Zeitkomplexität der Inferenz. Für die Komplexitätsbetrachtung einiger gängiger Probleme ist es notwendig die wesentlichen Komplexitätsklassen [AB09], [RN10] zu betrachten. Diese stehen in einer Teilmengen-Beziehung
zueinander:
P ⊆ NP ⊆ P NP ⊆ EXP ⊆ NEXP ⊆ P NEXP
Im Detail definiert man diese Klassen wie folgt:
P - alle Probleme, die von einer deterministischen Turingmaschine in
polynomieller Zeit gelöst werden können.
•
NP – Probleme, die von einer nicht-deterministischen Turingmaschine in
polynomieller Zeit berechnet werden können.
•
EXP bzw. NEXP – Probleme, die von einer deterministischen bzw. nichtdeterministischen Turingmaschine in exponentieller Zeit berechnet werden.
•
P NP bzw. P NEXP – Probleme, die von einer deterministischen Turingmaschine
in polynomieller Zeit unter Verwendung eines Orakels für NP bzw. NEXP berechnet werden.
•
Für Algorithmen, die einen Funktionswert berechnen, verwendet man analog zu
den oberen Klassen die Bezeichnungen FNP, FEXP usw.
Zu beachten ist, dass Probleme in Klassen über P in der Praxis meistens außerordentlich
schwierig zu berechnen sind.
Für die OWL 1 zugrunde liegenden Beschreibungslogiken SHIF(D) bzw. SHOIN(D)
liegt das Problem der Erfüllbarkeit (satisfiability, kurz SAT), d.h. die Prüfung, ob zu
gegebener Wissensbasis L eine Interpretation I gibt, die L erfüllt, in den Komplexitätsklassen EXP bzw. NEXP. [Tob01], [HP03]
Lukasiewicz untersuchte in [Luk07] die Komplexität gängiger Probleme für die Beschreibungslogiken P-SHIF(D) bzw. P-SHOIN(D). Die Ergebnisse sind in der folgenden Tabelle zusammengefasst:
40
SAT
TlogEnt
TlexEnt
P-SHIF(D)
EXP-vollständig
FEXP-vollständig
FEXP-vollständig
P-SHOIN(D)
NEXP-vollständig
FP NEXP –vollständig
FP NEXP –vollständig
Tabelle 3: Algorithmische Zeitkomplexität von Erfüllbarkeitsproblemen in P-SHIF(D) und
P-SHOIN(D) nach [Luk07].
Die Probleme TlogEnt und TlexEnt entsprechen logischem bzw. lexikographischem
Schlussfolgern. Lexikographisches Schlussfolgern ist eine Art des monotonen Schließens und wird von Lukasiewicz ebenfalls für probabilistische Inferenz vorgeschlagen1.
Offensichtlich verändert die Einführung von Wahrscheinlichkeiten die Komplexität des
Schließens in diesen Logiken nicht.
3.2.3 P-SHIQ(D) und Pronto
Horrocks et al. führten eine bedeutende Familie so genannter SI-Beschreibungslogiken
ein. Eine davon ist in [Hor99] vorgestellte Logik SHIQ(D), die wie alle Beschreibungslogiken dieser Familie eine Ergänzung von ALC darstellt. SHIQ(D) repräsentiert
eine Teilmenge von OWL-DL resp. SHOIN(D) ohne Datentypen und Klassen, die
durch einelementige Mengen definiert werden. Obwohl das Erfüllbarkeitsproblem für
ALC noch in der Komplexitätsklasse PSPACE (es gilt NP ⊆ PSPACE ⊆ EXP )
liegt, ist für SHIQ das SAT Problem bereits in EXP2.
P-SHIQ ist eine probilistische Erweiterung von SHIQ, die ebenso wie P-SHOIN(D)
durch so genannte conditional constraints ergänzt wird [Luk07]. Das SAT-Problem ist
für P-SHIQ
analog zu SHIQ in EXP [KP08]. Im Gegensatz zu den in 3.2.2 be-
schriebenen Logiken, für die keine Reasoner implementiert wurden, entwickelte Klinov
für P-SHIQ den Reasoner Pronto [Kli08]. Pronto basiert auf dem bekannten OWL
1
LUKASIEWICZ, Thomas: Probabilistic Default Reasoning with Conditional Constraints. Annals of Mathematics and Artificial Intelligence Vol. 34. (2002) 35-88
2
HORROCKS, Ian: Using an Expressive Description Logic: FaCT or Fiction? In Proceedings of 6th Conference on Principles of Knowledge Representation, Trento Italy. (1998) 636-649
41
Reasoner Pellet1 und benutzt lexikographisches probabilistisches Schlussfolgern nach
Lukasiewicz. Er arbeitet daher nicht auf der klassischen Syntax der Beschreibungslogiken sondern direkt auf OWL-Ontologien. Dabei kann Pronto lediglich mit OWL 1.1
Ontologien umgehen. Zu beachten ist, dass OWL 1.1 nicht den Status einer
Recommendation des W3C erreicht hat und daher nicht als offizieller Standard angesehen wird. Allerdings besteht in OWL 1.1 ebenfalls die Möglichkeit, Annotationen zu
OWL Axiomen zu verfassen (siehe auch Abschnitt 2.2.2), was wiederum der wesentliche Grund ist, warum Pronto diese Version anstatt OWL 1 nutzt. Die Annotationen erlauben, die Beziehungen zwischen Klassen, Rollen und Individuen mit Wahrscheinlichkeiten zu versehen, indem man Kommentare hinzufügt. In P-SHIQ(D) würde unser
Beispiel aus der Einleitung exakt wie in Abschnitt 3.2.2 aussehen. In OWL wäre allerdings viel mehr Notation erforderlich um die Klassen und Relationen zu definieren, so
dass unten lediglich gezeigt wird, wie man mit Pronto-Annotationen ausdrücken kann,
dass Paul sich zu 70% Fotos von Katzen anschaut:
1.
<owl11:Axiom>
2.
3.
4.
5.
6.
<rdf:subject rdf:resource="#Paul"/>
<rdf:predicate rdf:resource="#reads "/>
<rdf:object rdf:resource="#Katze"/>
<pronto:certainty>0.7;0.7</pronto:certainty>
</owl11:Axiom>
Die Relation „reads“ wird hier mit einem Wahrscheinlichkeitsintervall versehen.
Wie im Kapitel 2 bereits erwähnt, hängt die Berechnungsleistung eines Reasoners in
erster Linie von dem gewählten Formalismus, d.h. der Komplexität der jeweiligen zugrunde liegenden Beschreibungslogik, und zum anderen dem Grad der Optimierungen
innerhalb des Reasoners ab. Wir haben auf unserem Testsystem (zur Konfiguration des
Systems siehe Anhang I) die Inferenz auf der Breast Cancer Risk Assessment (BRCA)2
Ontologie getestet. Die BRCA Ontologie ist eine medizinische Ontologie für die Wahrscheinlichkeitsanalyse von Brustkrebs bei Frauen. Sie macht auch deutlich, warum in
P-SHIQ Wahrscheinlichkeitsintervalle benutzt wurden. Denn gerade im medizinischen
Bereich sind Risikoeinschätzungen meist über Unter- und Obergrenzen definiert.
1
2
42
http://clarkparsia.com/pellet/ (geprüft am 6. Mai 2011)
Enthalten in http://pellet.owldl.com/downloads/pronto-0.2.zip. (geprüft am 06.05.2011)
Der probabilistische Teil der Ontologie enthielt anfänglich 21 probabilistische Axiome
zu Klassen (rdfs: subClassOf) sowie 7 Axiome zu 3 Individuen der ABox. Wir haben
nachträglich einige Axiome zu Klassen hinzugefügt, um die Performance zu testen. Alle
Axiome besaßen stets ein Wahrscheinlichkeitsintervall von [1,1], d.h. es handelte sich
um absolut sichere Fakten. Abb. 21 zeigt wie lange die Berechnung einer Abfrage für
die Mitgliedschaft eines Individuums in einer Klasse mit zunehmender Anzahl von
Axiomen dauerte.
1200
1000
Sekunden
800
600
400
200
0
0
1
2
3
4
5
6
Abb. 21: Berechnungsdauer einer Inferenzabfrage mit Pronto und BRCA Ontologie mit zunehmender
Anzahl zusätzlicher probabilistischer Klassen-Axiome.
Nach dem Hinzufügen von 6 zusätzlichen subClassOf-Axiomen benötigte die Berechnung bereits 20 Minuten. Obwohl die BRCA Ontologie auch einige Dutzend nichtprobabilistische Klassen und Relationen enthält, lässt sich an diesem Test gut erkennen,
wie stark zusätzliche probabilistische Daten die Traktabilität beeinträchtigen. Auffallend ist der ausgeprägt exponentielle Verlauf der Kurve im Diagramm.
3.2.4 P-CLASSIC
Wie man bisher gesehen hat, leiden die verbreiteten Ansätze für probabilistische (wie
auch für gewöhnliche) Beschreibungslogiken an der hohen Komplexität der Inferenz.
Mit Blick auf dieses Problem definierten Koller et al. [KLP97] die traktable Beschreibungslogik P-CLASSIC. P-CLASSIC stellt eine probabilistische Erweiterung der Beschreibungslogik CLASSIC1,2 dar, daher ist die semantische Definition beider Logiken fast
1
BORGIDA, A. et al.: CLASSIC: A structural data model for objects. In proceedings of ACM SIGMOD
1989 International Conference on Management of Data, ACM. (1989) 59-67
2
CLASSIC steht für CLASSification of Individuals and Concepts.
43
identisch. P-CLASSIC unterstützt primitive und zusammengesetzte Konzepte, Rollen sowie so genannte Attribute. Attribute sind in P-CLASSIC Rollen, die eine 1:1 Verbindung
zwischen Konzepten darstellen – ist zum Beispiel (a R b) dann gibt es kein c mit (a R
c). Die Beschreibungslogik wird durch die folgende Grammatik definiert:
C, D → A C ó D
¬ A ∀R.C (≥ n R)
(≤ n R) (fills Q a)
wobei A ein primitives Konzept, C, D zusammengesetzte Konzepte, R eine Rolle und Q
ein Attribut bezeichnen. Ebenso wie CLASSIC unterstützt P-CLASSIC keine ABoxen. Die
Integration von stochastischem Wissen erfolgt mit Hilfe so genannter p-Klassen, die in
Form eines Bayes’schen Netzwerks (BN) gegeben sein müssen. Ein Bayes’sches Netzwerk ist ein gerichteter Graph in dem die Knoten jeweils Zufallsvariablen
Darstellen. Jeder Knoten ist zudem mit einer
Tabelle mit bedingten Wahrscheinlichkeiten
assoziiert, die die Verteilung bezüglich der jeweiligen Zufallsvariable unter der Vorbedingung der Elternknoten angibt. Mit Hilfe des
BN’s lassen sich nun alle Wahrscheinlichkeiten für alle möglichen Werte dieser Zufallsvariablen berechnen. Die p-Klassen repräsentieren somit die Wahrscheinlichkeiten des Durchschnitts und der Negation von Konzepten soAbb. 22: Beispiel eines Bayes’schen Netzwerks
wie Verteilungen über Rollenbeziehungen.
aus [KLP97].
Deutlich zu erkennen ist, dass P-CLASSIC zum
einen wenig ausdrucksstark im Vergleich zu anderen Beschreibungslogiken ist, und
zum anderen lediglich Wahrscheinlichkeiten über zusammengesetzte Konzepte und
Rollenbeziehungen abbilden kann. Trotz dieser Nachteile hat die Berechnung von solchen Wahrscheinlichkeiten in P-CLASSIC eine viel versprechende Zeitkomplexität. Das
Aufbauen von BN’s für zusammengesetzte Konzepte ist lediglich polynomiell, die
Auswertung dieser BN’s ist höchstens exponentiell, aber nur in Anzahl der Elternknoten
[PS08]. Um den Grad der Überlappung zwischen den einzelnen Konzepten zu quantifizieren, ist diese Beschreibungslogik also durchaus geeignet und traktabel.
Dem Autor dieser Arbeit ist kein Ansatz bekannt, bei dem eine Abbildung aus OWL in
P-CLASSIC oder eine Formalisierung der Semantik von P-CLASSIC innerhalb von OWL
versucht wurde. Ein Problem stellt die an sich recht unhandliche Definition von Wahrscheinlichkeiten in Form von Bayes’schen Netzwerken dar, die von Anfang an für die
gesamte Wissensbasis gegeben sein müssen. Hinzu kommt, dass kein Reasoner für
P-CLASSIC implementiert wurde [PS08].
44
3.2.5 BayesOWL
Abgesehen von einigen probilistischen Erweiterungen der verbreiteten Beschreibungslogiken gibt es Ansätze, die versuchen, die stochastische Unsicherheit direkt in den
OWL Formalismus einzufügen. Einer dieser Ansätze soll hier näher vorgestellt werden.
BayesOWL1 übersetzt stochastische Teile einer OWL Ontologie in Bayes’sche Netzwerke. Anders als in P-CLASSIC müssen in BayesOWL die Wahrscheinlichkeitsinformationen nicht von Beginn an als BN’s vorliegen. Wahrscheinlichkeitsinformationen über
Konzepte der Form P ( C ) bzw. bedingte Wahrscheinlichkeiten P ( C | D ) werden über
zusätzliche Syntaxkonstrukte in OWL eingefügt. Man beachte, dass diese nicht im
OWL Standard enthalten sind. Die Tatsache, dass sich Paul zu 70% Bilder von Katzen
anschaut könnte z.B. so dargestellt werden:
1.
2.
3.
<Variable rdf:ID="Paul">
<hasClass>liest_Kategorie_Katze</hasClass>
<hasState>True</hasState>
4.
5.
6.
7.
8.
9.
</Variable>
<PriorProb rdf:ID=P(Paul)”>
<hasVariable>Paul</hasVariable>
<hasProbValue>0.7</hasProbValue>
</PriorProb>
An diesem Beispiel erkennt man bereits eine der größten Schwächen dieses Modells –
die Wahrscheinlichkeiten können nur für Subsumption von Konzepten abgebildet werden. Wahrscheinlichkeitsinformationen über Relationen lassen sich mit BayesOWL
nicht darstellen. Deshalb muss man oben die Klasse „liest_Kategorie_Katze“ definieren,
um dieses Problem zu umgehen (siehe auch Abschnitt 4.2.2). BayesOWL erlaubt zwar
zusammengesetzte Klassen bezüglich der Mengenrelationen, z.B. Komplement, Vereinigung oder Durchschnitt, allerdings lässt sich damit wiederum nur auf die Subsumption-Beziehung zweier Konzepte schließen. Ebenso wenig ist es vorgesehen, dass eine
ABox berücksichtigt werden kann. Damit lassen sich einfache Klassenhierarchien, aber
keine stark strukturierten Informationen effektiv abbilden. [PS08]
Obwohl der Einsatz von BN’s aus komplexitätstechnischer Sicht viel versprechend ist,
wurde keine Untersuchung der Inferenzkomplexität für BayesOWL durchgeführt und
1
DING, Z. et al.: BayesOWL: Uncertainty Modeling in Semantic Web Ontologies. Soft Computing in Ontologies and Semantic Web Vol. 204, Berlin, Springer Verlag (2005)
45
kein Reasoner implementiert. Insofern ist eine praktische Anwendung dieses Modells
zum derzeitigen Zeitpunkt nicht möglich.
3.3 Statistisches relationales Lernen
3.3.1 Grundlagen
Von auf Beschreibungslogiken basierten probabilstischen Ontologieformalismen
schwenken wir nun zu einem Bereich um, in dem in der letzten Zeit erstaunlich effiziente Ergebnisse im Blick auf probabilistische Wissensrepräsentation erzielt wurden. Bereits vor Dekaden wurde in der KI-Disziplin Maschinelles Lernen (ML) intensiv Forschung betrieben. Diese konzentrierte sich auf die Verarbeitung von verrauschten Daten
und großen Datenmengen. Die ML-Forschung setzte dabei stark auf statistische Verfahren, und so entstanden Modelle wie neuronale Netze, Entscheidungsbäume und lineare
Modelle, die große Erfolge bei Problemen wie Bild- und Spracherkennung verzeichnen
konnten. Allerdings vernachlässigte man dabei den relationalen Aspekt der Daten, die
Beziehungen zwischen Objekten von Domänen wurden außer acht gelassen. Eine Ausnahme bildet die so genannte Induktive Logische Programmierung (ILP), die sich mit
dem Lernen von deterministischen Regeln aus relationalen Daten (meistens auf Grundlage von PL1) beschäftigt. In den letzten Jahren etablierte sich ein neuer Forschungsbereich mit dem Namen Statistisches Relationales Lernen (SRL) der ML und ILP Ansätze
vereint. SRL steht für den Versuch, Wissensrepräsentation, Inferenz und Lernen in Domänen mit komplexen relationalen und stark probabilistischen Strukturen effizient zu
ermöglichen [GT07]. Andere in der Literatur verwendete Synonyme sind
„probabilistisches logisches Lernen“ oder „multi-relationales Data Mining“. Obwohl die
Ziele des SRL nach einer utopischen Allround-Lösung in der KI klingen, werden wir
sehen, dass bereits heute praxisbezogene Problemlösungen mit SRL-Methoden durchaus möglich sind.
Die üblichen Repräsentationsformalismen in SRL bauen entweder auf Prädikatenlogik
oder Frames auf. Wir werden uns in dieser Arbeit nur mit den ersteren beschäftigen.
Abb. 23 zeigt, wie der Workflow eines SRL-Modells aussieht. Aus einer relationalen
Domäne wird zuerst eine probabilistische Ontologie gelernt. Dabei gibt es Verfahren,
die aus reinen Daten neue probabilistische Regeln gewinnen – das entspricht in etwa
den Methoden des Data Mining. Ist die Struktur der Domäne bereits gut bekannt, besteht eine andere Herangehensweise darin, eine vorhandene logische Wissensbasis mit
probabilistischen Informationen anzureichern. Mit Hilfe von Reasonern kann man nun
46
auf dieser Ontologie schlussfolgern. Das Besondere an der Inferenz in SRL Modellen
ist, dass die probabilistische Natur der Formalismen den Einsatz diverser approximativer Techniken der Statistik ermöglicht. Diese Techniken konnten erfolgreich integriert
werden und ermöglichen die Berechnung von derart großen Datenmengen, bei denen
der Einsatz von Prädikatenlogik schlicht unvorstellbar wäre. Diese Tatsache trägt im
Wesentlichen zur Traktabilität der Inferenz in SRL bei.
Relationale
Domäne
Statistisches Lernen
Probabilistische
Ontologie
(Approximative)
Inferenz
Abb. 23: Vollständiger SRL-Prozess – Anhand von Domänendaten wird eine probabilistische Ontologie
gelernt, die dann für Inferenz verwendet wird.
3.3.1 Graphbasierte Modelle
Konsequenterweise stellt sich an dieser Stelle die Frage: Wie werden eigentlich die
Wahrscheinlichkeitsinformationen in SRL repräsentiert? In der Forschung verfolgte
man zwei Ansätze: so genannte graphbasierte Modelle (graphical models, GMs) und
stochastische Grammatiken [GT07]. In dieser Arbeit werden wir ein bestimmtes
graphbasiertes Modell nutzen und gehen deshalb hier etwas näher darauf ein. Wie der
Name bereits anmutet, verwenden GMs Graphen zur Repräsentation von Wahrscheinlichkeiten und probabilistischen Relationen. GMs werden in zwei Gruppen unterteilt:
(azyklische) gerichtete und ungerichtete Modelle. Den Hauptvertreter der ersten Gruppe
hat man bereits im Abschnitt 3.2.4 gesehen – Bayes’sche Netzwerke. Das Ziel von
graphbasierten Modellen ist stets, die Verteilung einer Menge von Zufallsvariablen
X = { X 1 ,..., X n } darzustellen.
In BN’s werden diese Zufallsvariablen durch die Knoten eines gerichteten Graphen repräsentiert. Die bereits erwähnten Tabellen nennt man CPTs (conditional probability
tables), diese beinhalten bedingte Wahrscheinlichkeiten der Zufallsvariable X i für alle
möglichen Belegungswerte unter Vorbedingung aller Elternknoten resp. Zufallsvariablen (vgl. auch Abb. 22). Die Wahrscheinlichkeit für eine mögliche Belegung der Zufallsvariablen von X kann als Produkt von bedingten Wahrscheinlichkeiten berechnet
werden:
47
n
P ( X 1 = x1 ,..., X n = xn ) = ∏ P ( X i = xi | eltern( X i ) )
i =1
wobei eltern( X i ) die Belegung der Elternknoten mit entsprechenden Werten aus X
ist.
Zwei
Zufallsvariablen
sind
stochastisch
unabhängig
wenn
gilt:
P ( X ∩ Y ) = P ( X ) ⋅ P (Y ) . Offensichtlich sind Knoten ohne Eltern immer stochastisch
unabhängig. Zwei Zufallsvariablen nennt man stochastisch unabhängig unter Vorbedingung wenn gilt: P ( X , Y | Z ) = P( X | Z ) ⋅ P(Y | Z ) . Ohne auf mathematische Details
einzugehen sei hier erwähnt, dass jeder Knoten stochastisch unabhängig von seinen
Nicht-Nachfahren unter Vorbedingung seiner Eltern ist [KFG+07]. Bayes’sche Netzwerke tragen also dank ihrer Struktur viel Information über Abhängigkeiten zwischen
einzelnen Zufallsvariablen in sich.
Den Hauptvertreter der Gruppe der ungerichteten Graphen stellen so genannte Markow
Netzwerke (MNs). Wie in BN’s repräsentieren hier die Knoten die Zufallsvariablen. Allerdings werden die Wahrscheinlichkeitsinformationen in MN’s nicht so intuitiv und
einfach integriert. Sei X = { X 1 ,..., X n } eine Menge von (diskreten) Zufallsvariablen
und x eine konkrete Zuweisung dieser Variablen aus ihren Wertebereichen. Eine Clique ist ein Teilgraph eines ungerichteten Graphen, bei dem jeder Knoten mit allen anderen Knoten verbunden ist. Auch ein einzelner Knoten ist eine Clique. Sei nun G ein
Graph und C (G ) die Mengen aller Cliquen für G , sowie Vc die Menge der Knoten in
{
}
der Clique c . Zusätzlich sei φc (Vc ) : Vc1 = x1 ,...,Vck = xk → R + eine Funktion, die
jeder Belegung von Vc einen positiven reellen Wert zuordnet. φc (Vc ) wird Cliquenpotentialfunktion genannt. Die Menge aller solcher Funktionen sei Φ = {φc (Vc )}c∈C ( G ) .
Wir können nun das Markow Netzwerk als M = ( G, Φ ) definieren. [TAW+07] Die
Wahrscheinlichkeitsverteilung in MN’s errechnet sich als:
P ( X = x) =
1
∏ φc (vc ) mit Z = ∑∏ φc (vc′ )
Z c∈C (G )
v′ c
(1)
vc steht stets für eine Belegung der Clique c unter Berücksichtigung von X und Z
wird auch Normalisierungskonstante für das MN genannt. Die Wahrscheinlichkeit von
X berechnet sich also aus dem Produkt der Potentiale aller Cliquen. Diese Potentiale
repräsentieren keine Wahrscheinlichkeiten im klassischen Sinne. Sie können aber als
eine Art Vergleich zwischen verschiedenen Möglichkeiten der Belegung der Clique interpretiert werden. Da die Anzahl der Cliquen in einem Graphen und die Cliquen selbst
sehr groß sein können verwendet man oft eine etwas andere Notation, die so genannte
logarithmisch-lineare Repräsentation:
48
P ( X = x) =
1




exp  ∑ wi ⋅ fi (vc )  und Z = ∑ exp  ∑ wi ⋅ fi (vc′ ) 
Z
v′
 i

 i

(2)
mit wi Gewichte und fi so genannte Merkmale (features). Die einfachste Form der
Features ist eine Indikatorfunktion auf vc , d.h. f v ( c ) ( x) ≡ δ ( x = v(c) ) . Durch den Einsatz der logarithmisch-linearen Form lassen sich Features und Gewichte wieder verwenden und dadurch eine kürzere Darstellungsform als in (1) erreichen. [KFG+07] Die
nächste Abbildung zeigt ein bereits parametrisiertes Markow Netzwerk mit 3 Knoten
und 6 Cliquen.
V1
φ (V1 )
0
1
0.5
100
V1
V1 V3 φ (V1 , V3 )
V1 V2 φ (V1 , V2 )
0
0
1
1
0
1
0
1
0
0
1
1
1
100
10
0.4
V2
V2
φ (V2 )
0
1
5
100
0
1
0
1
0.3
5
2
0.1
V3
V3
φ (V3 )
0
1
100
2.2
V2 V3 φ (V2 , V3 )
0
0
1
1
0
1
0
1
50
0.1
20
2.1
Abb. 24: Beispiel eines Markow Netzwerks mit 6 Cliquen. Auch einzelne Knoten zählen als Cliquen.
Da BN’s Spezialfälle der Markow Netzwerke sind, kann ein Bayes’sches Netzwerk in
ein MN überführt werden.1 Für Bayes’sche Netzwerke wurde 2005 der SRL-Ansatz
Bayesian Logic (BLOG) vorgeschlagen.2 BLOG verknüpft BN’s und Prädikatenlogik zu
einem inferenzfähigen Modell. Im Detail werden wir jedoch auf den Ansatz mit dem
1
BISHOP, C.: Pattern Recognition and Machine Learning. New York, Springer Verlag (2006)
MILCH, B. et al.: BLOG: Probabilistic Models with Unknown Objects. In proceedings of 19th IJCAI,
UK, Edinburgh. (2005) 1352-1359
2
49
Namen Markov Logic Networks eingehen, der von Richardson und Domingos im Jahr
2004 vorgestellt wurde und Markow Netzwerke mit Prädikatenlogik verknüpft.
50
3.4 Markov Logic Networks
3.4 Markov Logic Networks
3.4.1 Aufbau der Markov Logic Networks
Ohne auf die Grundlagen der Prädikatenlogik erster Stufe näher einzugehen ([RN10]
bietet z.B. einen guten Überblick zu PL1 in Künstlicher Intelligenz) führen wir zunächst
einige Begriffe ein, die später in der Arbeit verwendet werden. Ein Grundterm beschreibt einen Term, der keine Variablen enthält, wohingegen ein Grundprädikat
(ground atom) eine atomare Formel ist, die nur aus Grundtermen besteht. Eine mögliche
Welt (possible world) oder Herbrandt Interpretation weist jedem Grundprädikat einen
Wahrheitswert zu. Demnach ist eine Formel immer dann erfüllbar, wenn es mindestens
eine Welt gibt, in der sie wahr ist. Die Idee hinter Markov Logic Networks ist, dass ein
Verstoß gegen eine Formel in einer möglichen Welt die Wissensbasis nicht gleich unmöglich sondern nur weniger wahrscheinlich macht [DR07].
Sei {Fi } eine abzählbare Menge von PL1-Formeln und wi reele Zahlen, die als Gewicht jeder Formel zugeordnet werden. Dann ist L = ( Fi , wi ) ein Markov Logic Network (MLN). Zusammen mit einer Menge von Konstanten C = {c1 ,..., cn } , die Wertebereiche für Variablen enthält, definiert L ein MN M L ,C nach den folgenden Regeln:
Zu jedem Prädikat P aus L wird für jede Belegung von P ein binärer Knoten
erstellt. Das Potential des Knotens ist 1 wenn das Grundprädikat wahr ist und
sonst 0.
Der Knoten wird mit allen anderen Knoten verbunden, deren Prädikate zusammen mit P in einer Formel vorkommen.
Für jede mögliche Belegung einer Formel Fi wird ein eindeutiges Feature fi
erzeugt, wobei fi = 1 wenn die Grundformel wahr ist, und 0 sonst. Die Gewichte für fi entsprechen den Gewichten wi aus L .
Die Wahrscheinlichkeit für eine mögliche Welt x berechnet man nun als:
P ( X = x) =
1


exp  ∑ wi ⋅ ni ( x) 
Z
 i

wobei ni ( x) die Anzahl von wahren Belegungen der Formel Fi in der möglichen Welt
x ist. In der nächsten Abbildung wird ein Beispiel eines MLNs gezeigt. Wir verwenden
eine kleine Wissensbasis mit 2 Prädikaten und 1 Formel.
51
Formel
∀ x : Fahrzeug ( x ) ⇒ hatRaeder(x)
Gewicht
3
C={Auto, Hovercraft}
Fahrzeug (Auto)
Fahrzeug
(Hovercraft)
hatRaeder (Auto)
hatRaeder
(Hovercraft)
Abb. 25: Beispiel eines MLN mit 1 Formel und 2 Prädikaten.
3.4.2 Inferenz
Die häufigste Abfrage in MLNs oder in SRL im Allgemeinen ist P (Y | E = e ) =: Q .
Diese Art von Abfrage wird auch probabilistic conditional query (PCQ) genannt
[KFG+07]. Die Zufallsvariablen in E stellen Fakten (evidence) dar, also Dinge, die bereits beobachtet und bekannt sind. Unter diesen Vorbedingungen erhält man mit der Abfrage die komplette Verteilung von Y . Die Art dieser Abfrage gibt bereits Aufschluss
darüber, wie eine MLN-Wissensbasis strukturiert ist. Sie besteht aus einer Menge von
Formeln (TBox) und einer Datenbank mit Fakten (ABox). Eine andere Gruppe von Abfragen beschäftigt sich damit, die wahrscheinlichste Belegung unter gegebenen Fakten
zu finden. Diese Gruppe kann man in zwei Mengen unterteilen: eine MPE (most probable explanation) Abfrage versucht die wahrscheinlichste Belegung für alle nonevidence Zufallsvariablen zu finden. Eine MAP (maximum a posteriori) Abfrage stellt
eine Speziellisierung der Abfrage Q dar, sie versucht die wahrscheinlichste Belegung
für eine gegebene Menge Y unter Vorbedingung E zu finden. Offensichtlich können
MPE/MAP Abfragen gelöst werden, wenn die vollständige Verteilung bekannt ist. Allerdings ist schon die Berechnung der Verteilung einer einfachen binären Zufallsvariable NP-hart [KFG+07]. Heutzutage nimmt man an, dass die beste Komplexität, die bei
NP-harten Problemen im Worst Case Szenario zu erreichen ist, gleich EXP ist. Unter
dieser Voraussetzung würde die exakte Berechnung der oben beschriebenen Abfragen
in den meisten Fällen nicht traktabel sein. Dies führte zur Implementierung vieler approximativer Inferenzmethoden für MLNs. Die Tabelle zählt die wichtigsten
Inferenzalgorithmen für die oben genannten Typen von Abfragen auf:
52
3.5 Resümee
MAP/MPE
PCQ
Komplette Aufzählung (exakt)
MaxWalkSAT1 (approximativ)
LazySAT2 (approximativ)
Cutting Plane Inference3 (CPI) (exakt)
Komplette Aufzählung (exakt)
Markov Chain Monto Carlo4 (MCMC) (approximativ)
Belief Propagation5 (BP) (approximativ)
Lifted Belief Propagation6 (lifted BP) (approximativ)
Gibbs Sampling7 (approximativ)
Simulated Tempering8 (approximativ)
Markov Chain + SampleSAT9 (MC-SAT) (approximativ)
MC-SAT-PC10 (approximativ) / IPFP-M10 (exakt)
Tabelle 4: Auflistung wichtigster Inferenzverfahren in MLNs. Genaue Beschreibung ist in den FußnotenQuellen zu finden.
3.5 Resümee
In unserem Überblick haben wir uns zuerst insbesondere auf Formalismen konzentriert,
die Beschreibungslogiken oder OWL um probabilistische Konstrukte erweitern. Der
Grund dafür liegt darin, dass OWL die einzige standardisierte Ontologiesprache ist, die
insbesondere im Blick auf das Semantic Web weiter entwickelt wird und breite Anwendung in realen Applikationen findet. Die von uns betrachteten Ansätze weisen offensichtlich Schwächen auf. So wurden viele Formalismen wie P-CLASSIC oder
1
KAUTZ, H., SELMAN, B., JIANG, Y.: A general stochastic approach to solving problems with hard and
soft constraints. In The satisfiability problem: Theory and applications. (1997) 573-586
2
DOMINGOS, P. et al.: Just Add Weights: Markov Logic for Semantic Web. ISWC International Workshops. (2008)
3
RIEDEL, Sebastian: Improving the Accuracy and Efficiency of MAP Inference for Markov Logic. In proceedings of 24th UAI, Helsinki, Finnland. (2008) 468-475
4
GILKS, W., RICHARDSON, S., SPIEGELHALTER, D.: Markov chain Monte Carlo in practice. London,
Chapman and Hall. (1995)
5
PEARL, Judea: Reverend Bayes on inference engines: A distributed hierarchical approach. In proceedings of 2nd AAAI, Pittsburgh, USA. (1982) 133-136
6
SINGLA, P., DOMINGOS, P.: Lifted First-Order Belief Propagation. In proceedings of 23rd AAAI, Chicago, USA. (2008) 1094-1099
7
GEMAN, S., GEMAN, D.: Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of
Images. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 6. (1984) 721-741
8
MARINARI, E., PARISI, G.: Simulated Tempering: a New Monto Carlo Scheme. Europhysics Letters Vol.
19. (1992) 451-458
9
WEI, W., ERENRICH, J., SELMAN, B.: Towards efficient sampling: Exploiting random walk strategies. In
proceedings of 19th AAAI, San Jose, USA. (2004) 670-676
10
JAIN, D., BEETZ, M.: Soft Evidential Update via Markov Chain Monte Carlo Inference. In proceedings
of 33rd KI 2010, Karlsruhe, Germany. (2010) 280-290
53
BayesOWL theoretisch beschrieben, sind aber in der Praxis mangels eines Reasoners
nicht anwendbar.
Der einzige uns bekannte probabilistische OWL-Reasoner Pronto stellt lediglich einen
Prototypen dar und arbeitet mit einer nicht standardisierten OWL-Version. Die auf
Pronto zugeschnittenen Ontologien sind daher nicht standard-konform und somit auch
nicht universell einsetzbar, ein Mapping aus anderen Standards scheint in der Praxis
ineffizient. Zudem stellt die Berechnungskomplexität ein weiteres Problem dar. Wir sahen, dass die Traktabilität der Inferenz mit Pronto unter der EXP-Komplexität der zugrunde liegenden Beschreibungslogik stark leidet. Leider findet auch keine Weiterentwicklung dieses Reasoners statt. Ob aus Mangel an Forschungsgeldern oder anderen
Gründen – es sei dahin gestellt, warum in diesem Bereich keine praktische Weiterentwicklung bzw. Verbesserung solcher bereits entwickelten oder auch oben genannter
theoretisch beschriebener Formalismen erfolgt.
Wir haben dann mit Statistischem Relationalem Lernen einen viel versprechenden Forschungsbereich vorgestellt, in dem bereits große Fortschritte im Bezug auf praktische
Anwendbarkeit von Formalismen gemacht wurden. Insbesondere in der Anwendung der
Markov Logic Networks haben sich zahlreiche Vorteile herauskristallisiert:
54
Die Anwendung von MLNs ist unter Einsatz von speziell optimierten Algorithmen traktabel.
Für MLNs existieren mehrere gut bis sehr gut funktionierende Software-Suiten,
die Reasoner und Lernapplikationen beinhalten und dokumentiert sind.
Die direkte Verwendung von Prädikatenlogik als Ontologiesprache ist intuitiv
und für Ontologiedesigner gut zugänglich. Eine Nutzung von komplizierten Prozeduren und einer, auf die Lösung zugeschnittener Syntax ist nicht notwendig.
Die Verwendung von Prädikatenlogik, die an sich ein Quasi-Standard ist, gewährleistet Universalität einer MLN-Ontologie im Bezug auf Mappings in andere Domänen.
Zahlreiche approximative Inferenzalgorithmen stehen zur Verfügung, zudem
wurden konstruktive Erweiterungen der MLNs entwickelt, so z.B. soft-evidence
(Hinzufügen von Gewichten zu Fakten in der ABox) im MC-SAT-PC Algorithmus (siehe Abschnitt 3.4.2). Solche Erweiterungen erleichtern zusätzlich die
Modellierung in komplexen probabilistischen Domänen.
Die MLNs zugrunde liegenden Markow Netzwerke erlauben zyklische Graphen.
Obwohl das für die Zielsetzung dieser Arbeit nicht von Relevanz war, ist die
Möglichkeit Zyklen zu modellieren für die Anwendungen des Semantic Web
durchaus von großer Bedeutung.
3.5 Resümee
Diese Vorteile waren der entscheidende Grund, warum MLNs zur Umsetzung der Zielstellung benutzt wurden. Dessen ungeachtet werden wir später zeigen, dass auch MLNs
im Bezug auf die Problemgröße recht strikte Grenzen gesetzt sind. Zunächst aber folgt
die Konstruktion unserer Profil-Ontologie.
55
KAPITEL 4. KONZEPT DER PPAO
ONTOLOGIE
Im Rahmen dieser Arbeit soll nicht nur eine konkrete Aufgabenstellung gezeigt werden.
Vielmehr soll zudem ein allgemeines „Gerüst“ in Form eines Ontologie-Modells (im
Folgenden Probabilistische Profilanalyseontologie, kurz PPAO genannt) entstehen, mit
dem man Profile unter verschiedenen Aspekten analysieren kann. Damit soll die universelle Einsetzbarkeit der Ontologie für die Profilanalyse gewährleistet werden. Wir werden daher in diesem kurzen Kapitel zuerst das abstrakte Konzept beschreiben und danach im Kapitel 5 auf Basis und mit den Begriffen des abstrakten Modells eine Implementierung von PPAO zeigen, die auf eine konkrete Aufgabenstellung ausgerichtet ist.
4.1 Konzepte
Wir werden grundsätzlich drei Typen von abstrakten Konzepten unterscheiden:
Benutzer
Statische
Bezugspunkte
Dynamische
Bezugspunkte
Abb. 26: Drei Kernelemente der PPAO Ontologie.
Im Abschnitt 2.3.6 sah man, dass Benutzerprofile innerhalb der IRCLOVE Community
bestimmte Merkmale haben können, wie z.B. Alter, Geschlecht etc. Wir nennen diese
Merkmale statische Bezugspunkte, weil die Information, die ein Benutzer in seinem
Profil angibt sich in der Regel gar nicht und nur sehr selten ändert. Auf der anderen Seite haben wir auch gesehen, dass Benutzer bestimmte Aktionen auslösen können, z.B.
Medien hoch laden, Kommentare schreiben oder Nachrichten austauschen. Solche Aktionen geschehen recht häufig und ihr Auftreten bildet gegenüber ihrem Bezugspunkt
57
KAPITEL 4. KONZEPT DER PPAO ONTOLOGIE
eine Wahrscheinlichkeitsverteilung. Deshalb werden wir solche Bezugspunkte als dynamisch bezeichnen.
Man beachte, dass diese Art von Definition keinesfalls domänenspezifisch ist. So sind
statische Profilinformationen in jeder Umgebung vorhanden, deren Teilaufgabe es ist,
Daten über Benutzer oder Personen im allgemeinen zu speichern. Es ist gar davon auszugehen, dass bestimmte statische Merkmale wie die Angaben von persönlichen Daten,
beispielsweise Namen, Pseudonyme, Adressen oder Geburtsdaten in den meisten heutigen Datenbanksystemen auf ein und dieselbe Weise gespeichert werden. Eine Abbildung dieser Daten aus einer beliebigen relationalen Datenbank in unsere Ontologie
würde deshalb keine Schwierigkeit darstellen. Dynamische Bezugspunkte sind in den
meisten komplexen Domänen, in denen die Untersuchung des Verhaltens von Menschen beabsichtigt ist, vorhanden. Sie sind im Gegensatz zu statischen Merkmalen viel
domänenspezifischer. So könnten sie bei einem Web-Commerce Unternehmen die Kategorien der gekauften Artikel eines Kunden und bei einem Verlag die Themen oder
Schlagwörter der gelesenen Zeitungsartikel oder Bücher darstellen. Die Transformation
von Verteilungen in die Ontologie ist daher wesentlich aufwendiger und abhängig von
der jeweiligen Struktur der vorhandenen Datenbank. Unser PPAO-Konzept gewährleistet dennoch, dass diese Faktoren für die Analyse zur Verfügung stehen.
4.2 Relationen
4.2.1 Typen von Relationen in PPAO
Die Konzepte einer Ontologie werden über Relationen in Beziehung zueinander gesetzt.
Man erkennt, dass es mit den oben genannten 3 Konzeptypen 6 verschiedene Relationstypen geben kann. Tabelle 5 listet alle möglichen Typen mit dazugehörigen Beispielen
von Relationen auf.
P
P
P
Relationstyp
Beispiel
Benutzer <-> Benutzer
Benutzer <-> statischer Bezugspunkt
Benutzer <-> dynamischer Bezugspunkt
statisch <-> statisch
dynamisch <-> dynamisch
statisch <-> dynamisch
Freund, Kollege
Interesse, Fachgebiet, Adresse
Aktion
Ort in Bundesland
Unterkategorie von Kategorie
Interesse bezieht sich auf Kategorie
Tabelle 5: Mögliche Relationstypen in PPAO und Beispiele, wie solche Relationen aussehen können. P
kennzeichnet probabilistische Relationstypen.
58
4.2 Relationen
Grundsätzlich erhöht die Verwendung aller Relationstypen die Präzision der Analyse,
die man mit Hilfe der Ontologie durchführen möchte. So können durch dynamisch <->
dynamisch Relationen hoch komplexe Zusammenhänge in CTMs (vgl. Abschnitt 2.3.5)
modelliert werden. Allgemein können Relationen zwischen Bezugspunkten viele neue
Erkenntnisse offenbaren. Voraussetzung für die Verwendung solcher Relationen ist,
dass entsprechende Informationen in der Domäne überhaupt bekannt sind – was häufig
nicht der Fall ist. Ein Nachteil der Nutzung vieler Relationen und Relationstypen liegt
vor allem in der resultierenden hohen Komplexität der PPAO. Obwohl sich mit
IRCLOVE-Daten alle Relationstypen modellieren ließen, werden wir lediglich zwei
Typen verwenden, nämlich Benutzer <-> statisch und Benutzer <-> dynamisch. Das
war notwendig um die Traktabilität zu gewährleisten und wird im Experimentierteil dieser Arbeit näher erläutert.
Die Wahrscheinlichkeitskomponente von PPAO wird durch die Relationen realisiert.
Jeder Relationstyp kann mit Hilfe von MLNs mit Wahrscheinlichkeitsinformationen
versehen werden – es ist aber nicht immer sinnvoll. So sind diskrete Profilmerkmale wie
Alter oder Name offensichtlich eindeutig. Wir werden deshalb davon ausgehen, dass die
Relationstypen mit statischen Bezugspunkten lediglich attributiven Charakter haben und
entweder wahr oder falsch sein können.
4.2.2 Modellierung von Relationen
Es gibt zwei Arten wie man Relationen umsetzen kann. Bei der ersten Möglichkeit verzichtet man auf die Verwendung von Rollen. Für jede Relation und ihren Endpunkt wird
eine neue Klasse angelegt. Die Mitgliedschaft eines Konzepts bzw. Individuums in solchen „Relationsklassen“ (Unterklassenbeziehung bzw. Instanzierung) repräsentiert dann
die eigentliche Relation. Die nächste Abbildung zeigt ein Beispiel für eine solche Modellierung.
0,8
Benutzer
1
2
Liest_Kategorie_Maus
0,2
0,5
Liest_Kategorie_Katze
0,5
Abb. 27: Modellierung von Relationen ohne die Verwendung von Rollen anhand eines Beispiels.
59
Diese Art der Repräsentation von Relationen hat einen gravierenden Nachteil: man benötigt für jede Relation genau so viele Klassen, wie die Anzahl der Endpunkte, die diese
Relation annehmen kann. In der Regel wird das zu einer sehr großen Anzahl von Klassen führen, bei einer Benutzer <-> Benutzer Relation entspräche das bereits quadratischem Wachstum. Deshalb ist diese Modellierungsform vor allem für probabilistische
Formalismen wie BayesOWL geeignet, in denen es nicht möglich ist, probabilistische
Informationen über Rollen anzugeben.
Die zweite Möglichkeit der Repräsentation besteht in der direkten Nutzung von Rollen
zur Beschreibung von Relationen.
Benutzer
1
liest
0,8
Maus
0,2
2
Kategorie
0,5
0,5
Katze
Abb. 28: Modellierung von Relationen mit Rollen analog dem Beispiel aus Abb. 27.
Da MLNs auf Prädikatenlogik setzen, die uns ermöglicht, sogar n-äre Prädikate zu deklarieren und damit über einfache binäre Beziehungen hinausgeht, werden wir die zweite Form der Modellierung nutzen.
4.3 Interoperabilität
In der Praxis sind oft Situationen vorstellbar, bei denen Daten aus mehreren Quellen in
eine Ontologie importiert werden müssen. Dabei besteht häufig das Problem, die Daten
in korrekter Weise aufeinander abzubilden. Durch den abstrakten und kompakten Aufbau der PPAO Ontologie ist das Hinzufügen von neuen Relationen, Konzepten und Individuen ohne große Mühe möglich. So ließe sich beispielsweise der Nutzerbestand einer zweiten Community mit zusätzlichen Profilmerkmalen einfach integrieren, denn das
Fehlen von Fakten (wir werden später zeigen, dass sich Benutzer <-> statische Bezugspunkte Relationen am einfachsten über ABox Fakten darstellen lassen) wird so interpretiert, als seien diese nicht vorhanden. Diese Vorgehensweise nennt man closed world
assumption. In MLN Reasonern ist grundsätzlich auch die dazu gegensätzliche open
world assumption möglich, die bei unbekannten Fakten eine 50%-ige Wahrscheinlichkeit für diese annimmt.
60
4.3 Interoperabilität
Ein anderes Problem besteht in der Vertrauenswürdigkeit von Quellen. Bezieht ein System Informationen von einer Vielzahl von Quellen, so könnte es passieren, dass eine
nicht vertrauenswürdige Quelle Daten verfälschen oder gar manipulieren kann. Es ist
daher wichtig, eine Vertrauenseinstufung von Quellen vornehmen und berücksichtigen
zu können. Wir werden daher im nächsten Kapitel im Abschnitt 5.3.5 eine Möglichkeit
zur Einbindung von Quelleninformationen und ihrer Vertrauenseinstufung aufzeigen.
Obwohl mit MLNs grundsätzlich jedem PPAO Element eine Quellenzugehörigkeit
zuweisbar ist, so auch Benutzern und Bezugspunkten, ist in Hinsicht der Vertrauenseinstufung nur die Herkunft von Interaktionsströmen von Interesse, die von Benutzern ausgehen. Daher ist es sinnvoll davon auszugehen, dass Benutzerbestände und Bezugspunkte von allen Quellen gemeinsam genutzt werden und nur die Relationen quellenspezifisch sind. Ein solches Szenario besteht in Bereich der sozialen Netzwerke z.B. bei
Facebook Apps1, da dort systemfremde Applikationen auf eine globale Benutzerbasis
zugreifen und danach Informationen an das System zurückliefern können.
1
http://developers.facebook.com/docs/guides/canvas (geprüft am 6. Mai 2011)
61
4.4 Schematische Darstellung
Wir schließen dieses kurze Kapitel mit einer schematischen Darstellung des oben beschriebenen Konzeptes. Berücksicht wurde dabei auch die optionale Möglichkeit der
Einbindung von Quelleninformationen für alle Elemente der Ontologie.
Quellen
P -Rollen
Binäre Rollen
Statische
Bezugspunkte
Dynamische
Bezugspunkte
Binäre Rollen
P -Rollen
Binäre Rollen
Benutzer
P -Rollen
Quellen
Abb. 29: Schematische Darstellung der PPAO Ontologie. Die gestrichelten Elemente sind Inhalte, die
zwar Bestandteil der konzeptuellen Beschreibung sind, jedoch nicht im Rahmen dieser Arbeit in der praktischen Umsetzung eingesetzt wurden. Die Kreise stellen Klassen von Konzepten, die Pfeile Klassen von
Rollen dar.
62
KAPITEL 5. IMPLEMENTIERUNG UND
INFERENZ
Wir werden nun die praktische Umsetzung des im vorherigen Kapitel entwickelten
Konzeptes beschreiben. Dabei gehen wir auf eine bisher noch unbeantwortete Frage ein:
wie können wir mit Hilfe der PPAO Ontologie für uns relevante Informationen erhalten? Um den Rahmen dieser Arbeit nicht zu sprengen konzentrieren wir uns nur auf eine
Aufgabenstellung – die Ähnlichkeitsanalyse von Profilen, werden jedoch andere Aufgabenstellungen ebenfalls kurz anreißen. Da die praktische formale Beschreibung von
PPAO reasoner-spezifisch ist, folgt als erstes ein Überblick über einige etablierte MLNReasoner.
5.1 MLN Reasoner
5.1.1 TheBeast
Der MLN-Reasoner thebeast [TBEAST] wurde von Sebastian Riedel an der University
of Edinburgh entwickelt. Zum Zeitpunkt der Fertigstellung dieser Arbeit lag diese Software in der Version 0.0.2 vor. Die Spezialität dieses Reasoners ist die beschleunigte
MAP-Inferenz mit dem CPI Verfahren [Rie08]. Thebeast ist zudem in der Lage, so genanntes
diskriminatives
Lernen
(discriminative
learning)
durchzuführen.
Diskriminatives Lernen und generatives Lernen bilden zusammen zwei wesentliche Paradigmen des probabilistischen Maschinellen Lernens.1 Da wir in dieser Arbeit keine
Lernverfahren verwenden, werden wir nicht näher auf dieses umfangreiche Feld eingehen. Thebeast erlaubt zudem, Kardinalitätseinschränkungen bei Formeln und Funktionen zu verwenden. Die Repräsentation der Daten in thebeast erinnert ein wenig an die
logische Programmierung:
1
BISHOP, C. M., LASSERRE, J.: Generative or Discriminative? Getting the best of both worlds. In Bayesian Statistics 8. Oxford University Press. (2007) 3-23
63
KAPITEL 5. IMPLEMENTIERUNG UND INFERENZ
1.
factor: for <QUANTIFICATION>
2.
if <CONDITION> add [<FORMULA>] * <WEIGHT>;
Diese Syntax definiert eine Formel mit dem dazugehörigen Gewicht. Der Reasoner
verwendet eine textuelle Shell, um Daten zu laden, Inferenz einzuleiten etc. Ein BatchBetrieb ist ebenfalls möglich.
Neben der etwas sperrigen Art der Notation ist das Fehlen von approximativen
Inferenzalgorithmen der wesentliche Nachteil von thebeast. Der Einsatz der approximativen Inferenz war für die zu verarbeitenden Datenmengen unbedingt notwendig. Aus
diesem Grund kam die Anwendung von thebeast im Rahmen der Diplomarbeit nicht in
Frage.
5.1.2 Alchemy
Alchemy [ALCHEM] ist eine umfangreiche, wenn nicht die umfangreichste, SoftwareSuite für MLNs. Sie wurde von Pedro Domingos et al. an der University of Washington
entwickelt und lag zur Fertigstellung dieser Arbeit in einer nicht näher spezifizierten
Beta-Version vor.
Für die Inferenz stehen in Alchemy zahlreiche Algorithmen zur Verfügung: neben dem
exakten MAP/MPE können MC-SAT, Gibbs Sampling, Simulated Tempering und Belief Propagation verwendet werden. Außerdem ermöglicht Alchemy den Einsatz von
integrierten und benutzerdefinierten Funktionen. Die Software-Suite besitzt keine Shell,
stattdessen besteht sie aus drei Modulen, die jeweils für das Lernen der Struktur, der
Gewichte und die Inferenz zuständig sind. Das Lernmodul reichert so genannte MLNDateien anhand von Trainingsdaten mit Gewichten an. Die daraus resultierende MLNWissensbasis kann dann zusammen mit einer ABox (die sich selbstverständlich von
Trainingsdaten unterscheiden kann) zur Inferenz verwendet werden. Der Ablauf entspricht also exakt dem in Abb. 23 geschilderten SRL-Prozess. Die Notation der Daten
gestaltet sich in Alchemy einfacher und intuitiver als bei Thebeast:
1.
2.
0.2 Smokes(x) => Cancer(x)
0.8 Friends(x,y) => (Smokes(x) <=> Smokes(y))
Beispielsweise postulieren diese zwei Formeln, dass Rauchen möglicherweise zu Krebs
führt und dass zwei Freunde oftmals beide Raucher oder Nicht-Raucher sind. Die PL1-
64
5.1 MLN Reasoner
Formeln sind hier bereits mit MLN-Gewichten versehen. Alchemy (und momentan auch
kein anderer MLN-Reasoner) ermöglicht keine direkte Angabe von Wahrscheinlichkeiten statt Gewichten. Dies ist auf die strukturelle Bauweise von Markov Logic Networks
zurückzuführen und stellt aktuell noch ein offenes Forschungsproblem dar.
Obwohl Alchemy über zahlreiche Features verfügt, ist es gänzlich nicht fehlerfrei. Tests
mit verschiedenen Modellen ergaben oftmals Fehler und berechnete Daten unterschieden sich je nach dem verwendeten Inferenzalgorithmus zum Teil gravierend. Ebenfalls
war die Performance der Inferenz zum Teil nicht zufrieden stellend. Zudem fehlt in
Alchemy die Möglichkeit, statt reinen reellwertigen Gewichtsangaben automatisch die
natürlichen Logarithmen der Gewichte zu verwenden. Diese Möglichkeit erweist sich
im Bezug auf bereits vorhandene Wahrscheinlichkeitsverteilungen als sehr nützlich.
Aus diesen Gründen entschieden wir uns nach einigen Tests für die Verwendung eines
dritten MLN-Reasoners, den wir als nächstes beschreiben.
5.1.3 PyMLN – ein Bestandteil von ProbCog
ProbCog [PCOG] ist eine von D. Jain, M. Beetz et al. an der Technischen Universität
München entwickelte Software-Suite für SRL-Techniken. ProbCog integriert Werkzeuge für Bayesian Logic Networks1 (BLNs) und MLNs. Die Software wurde während des
Verfassens dieser Arbeit stets weiterentwickelt. Die hier betrachtete und später verwendete Version ist 1573. Der für Markov Logic Networks zuständige Suite-Teil trägt den
Namen PyMLN und wurde mit der Programmiersprache Python entwickelt. PyMLN
beherrscht mehrere Lernverfahren. Es wird die MAP-Inferenz und die vollständige
exakte Aufzählung unterstützt. MC-SAT und Gibbs Sampling sowie zwei spezielle für
so genannte Soft Evidence optimierte Verfahren MC-SAT-PC und IPFP-M stehen für
approximative Inferenz zur Verfügung. Soft Evidence ist eine von Jain et al. vorgeschlagene Verbesserung von MLNs: Die ABox der Wissensbasis kann mit zusätzlichen
Gewichten angereichert werden. PyMLN kann zudem externe MLN-Reasoner, wie das
oben beschriebene Alchemy, verwenden.
Als Einziger der drei betrachteten Reasoner verfügt PyMLN über eine GUI. Die Abbildung zeigt die PPAO Ontologie innerhalb des Inferenz-Moduls.
1
JAIN, D., WALDHERR, S., BEETZ, M.: Bayesian Logic Networks. Technical Report. Technische Universität München. (2009)
65
Abb. 30: PyMLN GUI (Query Tool) mit geladener PPAO Ontologie.
Eine PyMLN-Wissensbasis besteht aus zwei Teilen. Der obere Bildteil beinhaltet die
eigentliche MLN-Datei, die stets die TBox und probabilistische Teile der ABox enthält.
Der untere Bildteil beinhaltet die Evidence-Datei, die einer reinen ABox entspricht. Sie
kann bei Verwendung von Soft Evidence ebenfalls probabilistische Elemente enthalten.
Die Evidence-Datei definiert zudem die Wertebereiche (Domänen) der verwendeten
Variablen.
PyMLN erlaubt die Verwendung von Gewichten, die als natürliche Logarithmen aus
reellen Zahlen dargestellt werden können, z.B. logx(0.8) FORMEL. Wir werden diese
Möglichkeit benutzen, um bereits bekannte Wahrscheinlichkeitsverteilungen in die
Wissensbasis zu integrieren. Die Art der Notation von Daten entspricht der AlchemyNotation: PL1-Formeln werden direkt über die GUI in die Dateien eingegeben. Im Gegensatz zu Alchemy unterstützt PyMLN keine Funktionen. Dennoch ist die Software
leicht verständlich, verfügt über eine gute Usability und erwies sich im Bezug auf die
Fehleranfälligkeit und Performance effektiver als Alchemy. Dies ist auch der Verwendung von speziellen optionalen Math-Bibliotheken zu verdanken. Um die beste Performance zu erzielen installierten wir alle empfohlenen Zusatzbibliotheken.
66
5.2 Modellierungsansätze
5.2 Modellierungsansätze
Im Laufe der Implementierung des abstrakten Konzepts aus dem Kapitel 4 haben wir
mehrere Modelle getestet. An dieser Stelle sollen nur zwei grundsätzliche Modellierungsansätze erörtert werden.
Bei dem ersten Ansatz wurden die Rollen ganz klassisch gemäß der Prädikatenlogik
modelliert, wobei beispielsweise die probabilistische Rolle „read“ zu dem dynamischen
Bezugspunkt „Kategorie“ als ein zweistelliges Prädikat read(Benutzer, Kategorie) dargestellt wurde. Ohne auf Details einzugehen (das geschieht im weiteren Verlauf dieses
Kapitels) wurden die so genannten Match-Prädikate, die die Ähnlichkeit zwischen Profilen symbolisieren, als Match(Benutzer, Benutzer) dargestellt. Es zeigte sich, dass dieser Modellierungsansatz, obwohl er klassisch und flexibel formuliert ist, und damit die
Möglichkeiten der Prädikatenlogik ausnutzt, eine relativ schlechte Performance aufweist. Die Darstellung von mehrstelligen Prädikaten impliziert stets, dass alle Belegungsmöglichkeiten dieser Prädikate aufgezählt werden. In PyMLN gibt es zwar die
Möglichkeit, 1:n – Beziehungen abzubilden, indem hinter dem Argument ein „!“ gesetzt
wird (z.B. hatMitarbeiter(Chef!,Mitarbeiter)). Dies verringert zwar die kombinatorische
Komplexität, hat aber für unsere Zwecke keine Bedeutung. Die oben beschriebene Darstellung der Match-Prädikate hat zudem weitere Nachteile: zum einen ist es überflüssig,
gleiche Profile miteinander zu vergleichen. Diese Möglichkeit wird aber immer
mitberechnet und kann nur durch zusätzliche Regeln in der Ausgabe genullt werden.
Zum anderen verursacht diese Darstellung Redundanz, da Match(1,2)=Match(2,1) ist.
Bei Verwendung von Gibbs Sampling zeigte sich aber, dass der Approximationsalgorithmus teilweise verschiedene Werte für diese Kombinationen berechnet. Um die Identität zu erzielen bedarf es weiterer zusätzlicher Regeln. Auch hier verursacht die Redundanz einen enormen Mehraufwand, da sie die Menge der Kombinationen um das zweifache vergrößert.
Das Vorhaben dieser Arbeit bestand unter Anderem auch darin zu zeigen, wie gut man
die konzipierte Ontologie in der Praxis anwenden kann. In Anbetracht der oben beschriebenen Nachteile haben wir daher einen zweiten optimierten, und im folgenden
beschriebenen, Ansatz verwendet. Dabei haben wir gänzlich auf die Verwendung von
mehrstelligen Prädikaten verzichtet und lediglich einstellige Prädikate benutzt. Die gesamte Information wurde in die Namen der Prädikate kodiert. Obwohl diese Lösung
nicht so elegant wie das klassische Vorgehen ist, und die Ontologie damit nicht so flexibel zu handhaben ist, erzielte die Inferenz bei unseren Tests eine viel bessere Performance. Ein weiterer Grund für die Verwendung der optimierten Implementierung be-
67
stand darin, dass die Berechnung mit mehrstelligen Prädikaten Fehler in PyMLN verursachte und teilweise nicht durchführbar war.
5.3 Konstruktion der PPAO Ontologie
Wir werden nun Schritt für Schritt die Konstruktion von PPAO beschreiben. Eine
PyMLN Wissensbasis besteht aus zwei Dateien und einer Abfragesequenz (vgl. auch
Abschnitt 5.1.3). Die Hauptdatei, auch MLN-Datei genannt, enthält die TBox und eine
probabilistische ABox. Die Evidence-Datei enthält reine Fakten und ist somit eine
ABox im klassischen Sinne. Wir starten mit der Evidence-Datei, da diese unsere statischen und dynamischen Bezugspunkte definiert.
5.3.1 Evidence-Datei
In dieser Datei definieren wir die Domänen für die in der MLN-Datei aufgeführten und
benutzten Prädikate. Die Domänen der Prädikate bilden die Klassen der jeweiligen statischen oder dynamischen Bezugspunkte analog Abb. 29. Die möglichen Werte dieser
Domänen sind die Instanzen dieser Klassen.
Schritt 1: Für jeden statischen und dynamischen Bezugspunkt A definiere die Domäne
mit A={ M }, wobei M eine kommaseparierte Menge aller Möglichen Instanzen von A
darstellt.
Wir möchten am Beispiel der Ähnlichkeitsermittlung in IRCLOVE die Anwendbarkeit
der PPAO Ontologie zeigen. Deshalb werden die Kategorien (vgl. Tabelle 1, Kapitel
2.3.6) als dynamische Bezugspunkte definiert:
kat={1,2,3,5,6,7,8,9,11,13}
Die Menge stellt die IDs der Level 1-Kategorien des IRCLOVE Persönlichkeiten Portals dar. Als statischen Bezugspunkt verwenden wir exemplarisch die Hobby-Angaben
der Benutzer, beispielsweise mit der Menge der 5 häufigsten Hobbys1:
1
Die Aufschlüsselung der Kategorien-IDs und die 30 häufigsten Hobbys der IRCLOVE User finden sich
im Anhang II und III.
68
hobby={musik,sport,lesen,kino,freunde}
Nun folgen die Definition der „harten“, das heißt nicht-probabilistischen, Fakten.
Schritt 2: Für jede binäre Rolle zwischen einem statischen Bezugspunkt und einem
Benutzer führe alle Fakten mit der Syntax
ROLLE+BENUTZERID (INSTANZ DES STAT. BEZUGSPUNKTES) auf.
Das „+“ Zeichen wird hier und im Folgenden ausschließlich zur Konkatenation von
Textzeilen verwendet, der Name der Rolle und die Benutzer-ID folgen unmittelbar aufeinander. Hier ist bereits die oben erwähnte Tatsache zu sehen, dass lediglich einstellige
Prädikate verwendet werden. Im konkreten Fall könnte die Definition so aussehen:
hasHobby411(kino)
hasHobby545(lesen)
….
5.3.2 MLN Datei
Den Anfang der MLN Datei bilden Definitionen der Prädikate. Zudem können auch hier
Domänen definiert werden. Da wir das jedoch schon in der Evidence-Datei getan haben,
definieren wir hier lediglich eine Platzhalter-Domäne d={0} um darauf bestimmte Prädikate anzuwenden.
Schritt 3: Für jede Rolle zwischen einem statischen Bezugspunkt und einem Benutzer
definiere Prädikate mit der Syntax
ROLLE+BENUTZERID (BEZUGSPUNKT)
Für jede Rolle zwischen einem dynamischen Bezugspunkt und einem Benutzer definiere Prädikate mit der Syntax
ROLLE+BENUTZERID (BEZUGSPUNKT!)
Analog zu oberen Ausführungen sehen die Definitionen im konkreten Fall so aus:
reads411(kat!)
comments411(kat!)
hasHobby411(hobby)
69
Der einzige Unterschied zwischen der Definition von statischen und dynamischen Rollen besteht in der Verwendung des „!“-Operators. Dieser signalisiert dem Reasoner,
dass der später angegebene Wert eindeutig ist, d.h. es nur ein solches Prädikat geben
kann und zwar mit dem angegebenen Wert. Diese Art von Definition ist notwendig um
Wahrscheinlichkeitsverteilungen korrekt zu beschreiben. Die Gewichte in MLNs entsprechen keinen Wahrscheinlichkeiten. Man kann jedoch eine feste Verteilung eines
Prädikats beschreiben, indem man für jeden möglichen Wert x dieses Prädikats die
Gewichte als ln ( p ( X = x) ) angibt und die Variablen des Prädikats als eindeutig, wie
oben beschrieben, definiert [SD10]. Für p ( X = x) = 0 funktioniert diese Transformation nicht, allerdings genügt es hier als Gewicht einen sehr großen negativen Wert anzugeben. PyMLN erlaubt beides durch die Bereitstellung der logx-Funktion, die folgendermaßen definiert ist:
ln ( z ) , für z ≠ 0
logx ( z ) = 
 −100, für z = 0
Wir können nun die probabilistischen Rollen zwischen dynamischen Bezugspunkten
und Benutzern mit Wahrscheinlichkeitsverteilungen belegen.
Schritt 4: Für jede probabilistische Rolle zwischen einem dynamischen Bezugspunkt
und einem Benutzer definiere die, ihr zugrunde liegende, Wahrscheinlichkeitsverteilung, falls diese vorhanden ist, mit der Syntax:
logx( p ( X = x ) ) ROLLE+BENUTZERID ( x )
Falls keine Wahrscheinlichkeitsverteilung für den Bezugspunkt und Benutzer vorliegt,
führe keine weiteren Daten auf.
Wir haben festgestellt, dass die Angabe von Null-Wahrscheinlichkeiten für alle Werte
eines Prädikats zu Verzerrungen in der Berechnung führten, da jeder Wert dann gleich
(niedrig) gewichtet wird. Aus diesem Grund wurde bei nicht vorhandenen Daten auch
keine Informationen in die Ontologie hinzugefügt. Die Tatsache, dass keine Verteilung
für eine Rolle vorliegt wird aber später im Inferenz-Teil der Ontologie festgehalten. Eine typische Definition könnte nun wie folgt aussehen:
logx(0.304348) reads599(1)
logx(0.521739) reads599(2)
logx(0.173913) reads599(6)
logx(0) reads599(3)
70
….
Damit sind alle Daten zu den Rollen in PPAO vorhanden, die wir in dieser Arbeit im
Rahmen des Fallbeispiels benötigen. Andere Rollen, wie beispielsweise zwischen statischen und dynamischen Bezugspunkten können analog als zweistellige Prädikate definiert werden. Probabilistische Rollen zwischen zwei Benutzern können mit der oben
beschriebenen Syntax ebenfalls ohne Umwege definiert werden.
Wir benötigen nun Konstrukte, die eine Schlussfolgerung von den roh gespeicherten
Daten auf die Beantwortung von Fragen ermöglichen.
5.3.3 Match-Prädikate als Sub-Indizes des Ähnlichkeitsindex
Grundsätzlich werden in Ontologien, die auf Beschreibungslogiken basieren, so genannte Query-Klassen oder Konzepte definiert. Diese, zumeist komplizierter zusammengesetzten, Konzepte beschreiben die jeweilige Fragestellung. Auch in MLN-basierten
probabilistischen Ontologien ist die Definition solcher Konzepte die erste Wahl. Mit
Hilfe der PPAO Ontologie wollen wir einen Ähnlichkeitsindex zwischen zwei Profilen
bestimmen und werden deshalb so genannte Match-Prädikate definieren. Diese Prädikate bestimmen den Grad der Ähnlichkeit zweier Benutzer im Bezug auf eine statische
oder dynamische Rolle in PPAO.
Schritt 5: Für jede Rolle zwischen einem statischen oder dynamischen Bezugspunkt
und einem Benutzer definiere in der MLN-Datei Match-Prädikate für jedes eindeutige
Benutzerpaar mit der Syntax
ROLLE_MATCH+BENUTZERID1_BENUTZERID2 (d)
Hier erkennt man, warum in 5.3.2 die Domäne „d“ eingeführt wurde – PyMLN erlaubt
nämlich keine nullstelligen Prädikate. Nullstellige Prädikate kann man als Analogon zu
Aussagen in der Aussagenlogik betrachten, im probabilistischen Fall der MLNs hat diese Aussage stets eine Wahrscheinlichkeit. Da wir die Match-Prädikate gerade als solche
„probabilstischen Aussagen“ modellieren wollen, benötigt man in PyMLN eine Platzhalter-Domäne. In PPAO sieht die Definition der Match-Prädikate beispielsweise so
aus:
read_Match21142_411(d)
create_Match27886_411(d)
71
award_Match27886_411(d)
….
Zu beachten ist, dass hier nur für eindeutige Benutzerpaare eine Definition erfolgt. Wir
haben die User-IDs stets so kombiniert, dass die Erste immer größer als die Zweite ist.
Diese Konvention ist nicht bindend, hat aber die Implementierung erleichtert.
Als letztes bestimmen wir nun, wie die Match-Prädikate berechnet werden. Die „Bauweise“ der Match-Prädikate unterscheidet sich dabei in Abhängigkeit davon, ob eine
statische oder dynamische Rolle betrachtet wird. Für jede auszuwertende Aktion wird
ein spezielles Gewicht spezifiziert. Damit kann man die einzelnen Bestandteile des
Ähnlichkeitsindex exakt balancieren und bestimmte Aktionen stärker bewerten als andere. Wie schon oben beschrieben muss zudem jedes Prädikat in PyMLN auf einer Domäne definiert werden. Unsere Platzhalter-Domäne d enthält deshalb lediglich nur einen
Wert 0. Alle Match-Prädikate werden dementsprechend für diesen Wert bestimmt. Wir
haben für eine bessere Sichtbarkeit die variablen Bestandteile der Formeln im folgenden
Schritt 6 farblich markiert. Das Wort EXIST beschreibt in PyMLN-Notation den logischen Existenz-Quantor.
72
Schritt 6: Für jede Rolle zwischen einem dynamischen Bezugspunkt und einem Benutzer, die Bestandteil der Ähnlichkeitsbetrachtung ist, und für die eine Wahrscheinlichkeitsverteilung für jeden der zwei verglichenen Benutzer vorliegt, füge der MLN-Datei
die folgende positive Match-Formel hinzu:
WR (EXIST c (ROLLE+ID1(c) ^ ROLLE+ID2(c))) => ROLLE_MATCH+ID1_ID2 (0)
wobei WR das spezifische Gewicht des Sub-Index im Ähnlichkeitsindex und ID1 / ID2
Benutzer-IDs sind.
Weiterhin füge im selben Schritt die folgende negative Match-Formel der MLN-Datei
hinzu:
!(EXIST c (ROLLE+ID1(c) ^ ROLLE+ID2(c))) => !ROLLE_MATCH+ID1_ID2 (0).
Die erste „positive“ Formel besagt, dass eine Übereinstimmung in einer dynamischen
Rolle (in unserem Fall also einer Aktion) zu einem Match führt. Je mehr solcher Übereinstimmungen in den jeweiligen Instanzen der Bezugspunkte (in unserem Fall also Kategorien) vorkommen, desto höher ist die Wahrscheinlichkeit für das Match-Prädikat.
Da die betrachteten Rollen an sich probabilistisch sind, ist die Wahrscheinlichkeit des
Match-Prädikats hauptsächlich nicht von der Anzahl sondern der Wahrscheinlichkeit
der jeweiligen Übereinstimmungen abhängig. Ein Match-Prädikat ist bei wenigen Übereinstimmungen, die allerdings hohe Einzelwahrscheinlichkeiten aufweisen (z.B. Benutzer A für Kategorie 1 bei 90% und Benutzer B für Kategorie 1 bei 70%) viel wahrscheinlicher, als bei einer Situation mit vielen Übereinstimmungen bei kleinen Einzelwahrscheinlichkeiten (z.B. 100 Übereinstimmungen zwischen Benutzer A und B mit
Wahrscheinlichkeiten der Größenordnung <1%). Die Konstruktion präferiert also starke
Spitzen in Verteilungen der beiden Benutzer und damit eindeutiges Verhalten. Dies ist
auf die, den Prädikaten zugrunde liegende, stochastische Funktionsweise zurückzuführen. Wir werden im Abschnitt 6.6.1 diese Funktionsweise genauer erläutern.
Die zweite „negative“ Formel stellt sicher, dass die Wahrscheinlichkeit für das MatchPrädikat bei Null bleibt, falls keine einzige Übereinstimmung in Instanzen der Bezugspunkte vorhanden ist, obwohl für beide Benutzer Aktivität vorliegt. Das ist zum Beispiel dann der Fall, wenn zwei Benutzer völlig unterschiedliche Kategorien lesen. Ohne
diese Formel wird durch die Verwendung eines approximativen Inferenzalgorithmus die
Wahrscheinlichkeit zwar klein aber nicht Null und verfälscht damit das Endergebnis.
Der Punkt am Ende dieser Formel signalisiert dem Reasoner, dass es sich dabei um eine
73
so genannte hard clause handelt. Da in MLNs alle Formeln ein Gewicht haben müssen,
sind hard clauses eine Art Workaround - die Formeln werden dabei mit einem sehr hohen Gewicht versehen. Damit sind harte Klauseln sichere, immer geltende, Formeln.
Im konkreten Fall sehen die Match-Formeln aus Schritt 6 folgendermaßen aus:
0.3 (EXIST c (comments58064(c) ^ comments411(c))) => comment_Match58064_411(0)
!(EXIST c (comments58064(c) ^ comments411(c))) => !comment_Match58064_411(0).
0.1 (EXIST c (reads11641(c) ^ reads411(c))) => read_Match11641_411(0)
!(EXIST c (comments11641(c) ^ comments411(c))) => !comment_Match11641_411(0).
Wir haben zudem beobachtet, dass die negativen Match-Formeln hohen Berechnungsaufwand verursachen. Vermutlich ist das auf die Durchiteration aller möglichen Belegungen zurückzuführen, die für die formulierte Aussage notwendig ist. Im Schritt 6 haben wir nur Match-Prädikate für Benutzer gebildet, für die eine Wahrscheinlichkeitsverteilung überhaupt vorliegt. Dies geschah, um den Berechnungsaufwand für die MatchPrädikate zu senken. Wir betrachten nun den entgegen gesetzten Fall.
Schritt 7: Für jede Rolle zwischen einem dynamischen Bezugspunkt und einem Benutzer, die Bestandteil der Ähnlichkeitsbetrachtung ist, und für die keine Wahrscheinlichkeitsverteilung für einen oder beide der zwei verglichenen Benutzer vorliegt, füge in die
MLN-Datei die folgende negative Match-Formel ein:
!ROLLE_MATCH+ID1_ID2 (0).
Ist also für mindestens einen der beiden Benutzer keine Wahrscheinlichkeitsverteilung
vorhanden, wird ein Match in der entsprechenden Aktion bereits bei der Erstellung der
Ontologie ausgeschlossen. Auch hier benutzen wir eine hard clause. Die Formeln sehen
in PPAO entsprechend aus:
!award_Match49249_411(0).
!create_Match24171_411(0).
!read_Match21233_411(0).
….
In ähnlicher Weise konstruiert man nun die Match-Prädikate für statische Rollen.
Schritt 8: Für jede Rolle zwischen einem statischen Bezugspunkt und einem Benutzer,
die Bestandteil der Ähnlichkeitsbetrachtung ist, und für die eine Wahrscheinlichkeits-
74
verteilung für jeden der zwei verglichenen Benutzer vorliegt, füge der MLN-Datei die
folgende positive Match-Formel hinzu:
WR ROLLE+ID1(x) ^ ROLLE+ID2(x) => ROLLE_MATCH+ID1_ID2 (0)
wobei WR das spezifische Gewicht des Sub-Index im Ähnlichkeitsindex und ID1 / ID2
BenutzerIDs sind.
Weiterhin füge im selben Schritt die folgende negative Match-Formel der MLN-Datei
hinzu:
!(EXIST x (ROLLE+ID1(x) ^ ROLLE+ID2(x))) => !ROLLE_MATCH+ID1_ID2 (0).
Der einzige Unterschied zu der Konstruktion von dynamischen Rollen liegt im Verzicht
auf den Existenz-Quantor in der positiven Formel. Wäre diese Formel eine harte Klausel, so würde eine einzige Übereinstimmung bereits zum eindeutigen Match führen. Da
die gesamte Formel jedoch probabilistisch ist, wächst die Wahrscheinlichkeit für das
Match-Prädikat mit steigender Anzahl von Übereinstimmungen. Allerdings ist diese
Wahrscheinlichkeit bereits bei einer einzigen Übereinstimmung sehr hoch, so dass diese Art von Konstruktion eine starke Gewichtung von Matches in statischen Rollen ermöglicht. Die oben beschriebenen Match-Prädikate können in PPAO so aussehen:
0.5 hasHobby34322(x) ^ hasHobby411(x) => hasHobby_Match34322_411(0)
!(EXIST x (hasHobby44917(x) ^ hasHobby411(x))) => !hasHobby_Match44917_411(0).
….
Schritt 9: Für jede Rolle zwischen einem statischen Bezugspunkt und einem Benutzer,
die Bestandteil der Ähnlichkeitsbetrachtung ist, und für die keine Wahrscheinlichkeitsverteilung für einen oder beide der zwei verglichenen Benutzer vorliegt, füge in die
MLN-Datei die folgende negative Match-Formel hinzu:
!ROLLE_MATCH+ID1_ID2 (0).
!hasHobby_Match45281_411(0).
!hasHobby_Match45279_411(0).
….
Nachdem die Sub-Indizes konstruiert sind kann man nun zu der eigentlichen Inferenz
übergehen.
75
5.3.4 Der Ähnlichkeitsindex und die Inferenz in PPAO
Es wäre möglich gewesen, ein weiteres Abfrage-Prädikat für den Ähnlichkeitsindex zu
definieren. Wir haben auf diese Möglichkeit jedoch bewusst verzichtet, um bei den experimentellen Untersuchungen im Kapitel 6 flexibel zu bleiben. Stattdessen haben wir
PyMLNs Feature benutzt, komplexe Klauseln in der Inferenz-Abfrage zu verwenden
(vgl. Abb. 30).
Schritt 10: Konstruiere den Ähnlichkeitsindex für zwei Benutzer als Disjunktion aller in
Schritt 5 definierten Match-Prädikate.
Die Definition ist also sehr einfach: wir fragen nach, wie hoch die Wahrscheinlichkeit
ist, dass mindestens ein Match-Prädikat vorhanden ist. Die Disjunktion war die plausibelste Form, einen aussagekräftigen Index zu erzielen. Wie wir später im Unterkapitel
6.6 demonstrieren werden, führt diese Art von Konstruktion zu einem relativ schnellen
Anstieg des Ähnlichkeitsindex. Aus diesem Grund ist eine feine Balancierung der speziellen Gewichte in der Praxis notwendig, damit der Index seine Aussagekräftigkeit
nicht verliert. Eine typische Index-Abfrage sieht folgendermaßen aus:
read_Match58598_411(0) v comment_Match58598_411(0) v
award_Match58598_411(0) v create_Match58598_411(0) v
hasHobby_Match58598_411(0)
Auf dem, dieser Diplomarbeit, beiliegenden Datenträger wurden selbstverfasste PHPProgramme angefügt, die zum Generieren der PPAO Ontologie aus IRCLOVE Daten
verwendet wurden. Diese Programme sind kommentiert und flexibel konfigurierbar,
insbesondere um Szenarien aus dem folgenden Kapitel 6 zu erzeugen. Außerdem haben
wir einige erzeugte Ontologien und Berechnungsergebnisse auf dem Datenträger zusammengefasst.
5.3.5 Multiple Quellen und Regulierung ihrer Vertrauenswürdigkeit
In diesem Abschnitt soll demonstriert werden, dass sich PPAO relativ einfach für die
Berücksichtigung mehrerer Datenquellen ergänzen lässt. Die Erweiterungen implizieren
76
allerdings, dass man zweistellige Prädikate benutzen muss. Wie schon in Unterkapitel
5.2 erwähnt verschlechtert die Verwendung solcher Prädikate die Performance der Inferenz. Aus diesem Grund und um den Rahmen der Arbeit nicht zu sprengen haben wir im
experimentellen Teil der Arbeit auf die Verwendung von mehreren Quellen verzichtet.
Im ersten Schritt müssen wir eine neue Klasse für die Quellen definieren:
Schritt Q1: Definiere in der Evidence-Datei die Domäne der Quellen mit Q={ M }, wobei M eine kommaseparierte Menge aller Möglichen Datenquellen darstellt.
Q={quelle1, quelle2}
Um die Quellenangabe in jedes Element der Ontologie einzubinden, führen wir für jedes benutzte Prädikat ein zweites Argument ein und speichern die Daten so für jede einzelne Quelle:
Schritt Q2: Ergänze in jeder Formel aus Schritten 2 bis 9 jedes dort vorkommende
Prädikat um die Quellenangabe, indem ein zweites Argument hinzugefügt wird. Bei
Match-Prädikaten aus Schritt 5 kann die Platzhalter-Domäne d durch Q ersetzt werden.
Somit werden alle Match-Prädikate einstellig.
Speichere alle vorhandenen Daten, die Schritten 2 bis 4 eingefügt werden, individuell
für jede Quelle.
Die neuen Prädikate könnten nun folgendermaßen aussehen:
reads411(kat!,Q!)
hasHobby411(hobby,Q)
.
hasHobby411(kino,quelle1)
logx(0.2) reads411(1,quelle1)
Zu beachten ist, dass die Instanzen der Benutzerklasse und der Bezugspunkte in allen
Quellen übereinstimmen müssen. Ansonsten muss man die Domänen als Vereinigung
aller möglichen Instanzen jeder Quelle definieren. Die oben beschriebene Vorgehens-
77
weise erlaubt uns sogar, die Gewichtung der einzelnen Aktionen pro Quelle unabhängig
zu definieren:
Schritt Q3: Falls für jede Quelle eine unterschiedliche Gewichtung von Matches erforderlich ist, füge die in Schritt 6 und 8 aufgeführten Formeln für jede Quelle einzeln mit
Q
expliziter Angabe der Quelle und den jeweiligen Gewichten WR ein. Ansonsten füge
die Formeln mit einer Variable als Quellenargument ein.
Konkret könnten also bei unterschiedlicher Gewichtung beispielsweise folgende Formeln entstehen:
0.3 (EXIST c (comments58064(c,q1) ^ comments411(c,q1))) => comment_Match58064_411(q1)
0.1 (EXIST c (comments58064(c,q2) ^ comments411(c,q2))) => comment_Match58064_411(q2)
Oben wurden die Quellen 1 und 2 mit q1 und q2 abgekürzt. Die Match-Prädikate sind
nun für jede Quelle formuliert. Da mit der Vertrauenswürdigkeit von Quellen eine zweite Gewichtungsschicht aufgelegt werden muss, benötigen wir „globale“ MatchPrädikate, die in Abhängigkeit der „lokalen“ quellenabhängigen Prädikate und der Vertrauensstufe der jeweiligen Quelle eine Wahrscheinlichkeit annehmen.
Schritt Q4: Definiere globale Match-Prädikate analog Schritt 5 mit
ROLLE_MATCH+ID1_ID2_GLOBAL (d)
comment_Match411_508_GLOBAL(d)
read_Match411_508_GLOBAL(d)
Schritt Q5: Für jede Quelle, Rolle und Benutzerpaar, wie in Schritten 5 und 8 beschrieben, füge die globale Match-Formel hinzu:
TQ ROLLE_MATCH+ID1_ID2 (QUELLE)=>ROLLE_MATCH+ID1_ID2_GLOBAL (0)
wobei TQ eine Zahl ist, die die Vertrauenswürdigkeit der Quelle angibt.
Die Gewichte TQ müssen nicht im Bereich zwischen 0 und 1 liegen. Allerdings sollten
sie in abgestimmter Proportion zueinander stehen und sind daher anwendungsspezifisch.
Beispielsweise könnten die Formeln so aussehen:
78
5.4 Von OWL zu MLN
1 comment_Match411_508 (quelle1) => comment_Match411_508_GLOBAL(0)
3 comment_Match411_508 (quelle2) => comment_Match411_508_GLOBAL(0)
Man bemerkt, dass die oben beschriebene Vorgehensweise zu einer deutlichen Erhöhung der Anzahl von Formeln in der Wissensbasis führt, da man für jede Kombination
eine Formel benötigt. Dies ist auf die Abkoppelung der Argumente von Prädikaten zurückzuführen. Um das Datenvolumen zu verringern ist es möglich, den in Unterkapitel
5.2 angesprochenen Modellierungsansatz zu nutzen, statt die Parameter in den Prädikatennamen zu kodieren. Auf die Inferenz hat dies jedoch keinen Einfluss, da der
Reasoner intern trotzdem alle Belegungskombinationen aufbaut.
Schritt Q6: Konstruiere den Ähnlichkeitsindex für zwei Benutzer als Disjunktion aller in
Schritt Q5 definierten globalen Match-Prädikate.
5.3.6 Segmentierung, Recommending und andere Aufgaben
In der Anleitung und Abb. 1 wurde bereits angedeutet, dass die zu entwickelnde Ontologie für mehrere Analyseaufgaben geeignet sein sollte. Zu gängigen Aufgaben der Profilanalyse gehören unter anderem die Segmentierung (Identifizierung oder Bildung von
Personengruppen), Recommending (Empfehlung von medialen Inhalten) und die Verhaltensanalyse (Erkennung von Verhaltensmustern von Benutzern). Diese Aufgaben
können im Einklang mit den abstrakten Konstrukten aus dem PPAO-Konzept durch eine Erweiterung des Inferenz-spezifischen Teiles der Ontologie integriert werden, wobei
man die bereits beschriebene Implementierung der probabilistischen Daten in der
Evidence- und MLN-Datei unverändert nutzen könnte. Die Erweiterung würde jedoch
eine Definition von zusätzlichen, auf die Aufgabe zugeschnittenen, Match-Prädikaten
erfordern, so dass die Betrachtung und Evaluation solcher Erweiterungen den Rahmen
dieser Diplomarbeit sprengen würde.
Die Aufgaben der Profilanalyse liegen recht nah beieinander. So kann die Ähnlichkeit
von Profilen als Kriterium für die Bildung von Segmenten fungieren. Wir werden deshalb im Abschnitt 6.6.3 an einem Experiment zeigen, wie man mit der bereits beschriebenen Implementierung der PPAO eine effektive Segmentierung durchführen kann.
5.4 Von OWL zu MLN
79
In Abb. 1 haben wir bereits angedeutet, dass eine Möglichkeit existiert, eine Ontologie
in OWL aufzubauen und sie nachher in eine MLN-Wissensbasis umzuwandeln. In diesem Unterkapitel wird dieser „Umweg“ näher beschrieben und begründet, warum wir
direkt eine MLN-Ontologie konzipierten und den direkten Weg nahmen.
In seiner Master Thesis entwickelte Oliveira ein Tool namens Incerto [Oli09]. Es lag
zum Zeitpunkt der Fertigstellung dieser Arbeit in einer Beta-Version 0.2 vor. Obwohl
Incerto auch zum Demonstrieren von probabilistischen Lernprozessen im Semantic
Web mit im Unterkapitel 5.1 beschriebenen Reasonern Alchemy und PyMLN konzipiert ist, liegt seine Besonderheit in der Fähigkeit, OWL Ontologien in MLNs umzuwandeln.
Die nächste Abbildung zeigt die Incerto-GUI mit einer geladenen und konvertierten
OWL-Ontologie aus einem der beiliegenden Beispiele.
Abb. 31: GUI des Tools Incerto, das auch zur Umwandlung von OWL- zu MLN-Ontologien verwendet
werden kann.
Der wesentliche Gedanke hinter der Tranformation, die Incerto durchführt, besteht darin, dass Konzepte unäre Prädikate, Rollen binäre Prädikate und OWL Individuen Konstanten entsprechen. In [Oli09] führt Oliveira Regeln zur Transformation von fast allen
80
5.4 Von OWL zu MLN
OWL Axiomen und Klassenausdrücken in Prädikatenlogik auf. Tabelle 6 zeigt einige
Beispiele solcher Umwandlungen.
OWL Ausdruck
subClassOf( CE1 , CE2 )
PL1 Formel
∀x : CE1 ( x) ⇒ CE2 ( x)
IntersectionOf( CE1 ,…, CEn )
∀x : CE1 ( x) ^ ... ^ CEn ( x)
PropertyAssertion( OPE , a, b )
OPE (a, b)
Tabelle 6: Einige Tranformationsregeln von OWL 2 zu PL1 nach [Oli09]. Dabei steht CE für einen
Klassenausdruck (class expression) und OPE für einen Rollenausdruck (object property expression).
Analog zu Pronto benutzt Incerto OWL 2 und die darin enthaltene Möglichkeit, Annotationen zu machen, um Gewichte für OWL Ausdrücke zu definieren. In Incerto lässt sich
zudem der URI der Annotation individuell konfigurieren. Wir haben das Tool installiert
und getestet, sind aber auf einige Schwierigkeiten gestoßen. Zum Einen ließ sich das
Java-Programm aus unerklärlichen Gründen nicht unter Windows ausführen. Da Incerto
OWL 2 benutzt, war die Verwendung einer mit Protégé 3 erstellten Testontologie nicht
möglich. Wir haben deshalb eine nicht stabile Protégé-Version 4.0.2 sowie die Version
4.1, die volle OWL 2 Syntax unterstützt, dazu verwendet, um Testontologien zu exportieren. Beide Ontologien konnten aber nicht in Incerto geladen werden und verursachten
Programmfehler. Der Kontakt mit Pedro Oliveira bestätigte den Verdacht, dass Incerto
eine OWL API benutzt, die nicht mehr mit den aktuellen Standards konform ist, und das
Programm in dieser Hinsicht nicht weiterentwickelt oder verbessert wird. Außerdem
benutzen die Transformationsregeln die klassische Darstellungsform von Prädikaten.
Diese hat sich aber, wie man im Unterkapitel 5.2 bereits gesehen hat, für die Zielstellung dieser Arbeit nicht als effizient genug erwiesen.
Zusammenfassend kann man also sagen, dass die meisten Elemente von OWL
Ontologien erfolgreich zu MLN Ontologien umgewandelt werden können. Im Rahmen
dieser Arbeit ergab sich aber kein Mehrwert durch ein vorheriges Aufbauen einer OWL
Ontologie und späterer Konvertierung zu MLNs. Im Gegensatz würde dies einen zusätzlichen maschinellen und konzeptionellen Aufwand verursachen, die Performance der
Ontologie verschlechtern und damit die praktische Anwendbarkeit der PPAO Ontologie
im Ganzen beeinträchtigen. Liegen allerdings bereits fertige OWL Ontologien vor, so
kann es von Vorteil sein, diese mit abgestimmtem Post-Processing und Methoden, wie
sie in Incerto angewendet werden, in das PPAO-Modell umzuwandeln.
81
KAPITEL 6. EXPERIMENTELLE
UNTERSUCHUNG
In Kapitel 5 haben wir den vollständigen Prozess beschrieben, wie die PPAO Ontologie
auf Basis von Daten einer relationalen Datenbank strukturiert und erstellt werden kann.
Insbesondere wurde beschrieben, wie die Daten aus der IRCLOVE Community in
PPAO überführt werden können, um einen Ähnlichkeitsindex zwischen Profilen zu bestimmen. Wir werden nun in diesem Kapitel unsere experimentellen Ergebnisse präsentieren und zwei wichtige Fragen beantworten: wie gut lässt sich unsere Berechnung skalieren und wo liegen die Grenzen von Markov Logic Networks im Bezug auf Profilanalyse?
6.1 Szenarien
6.1.1 ALL versus ALL
Wir werden zwei Testszenarien bei weiter folgenden Ergebnissen verwenden. Das erste
Szenario beruht auf der Berechnung des Ähnlichkeitsindex für jeden Benutzer zu jedem
anderen Benutzer und wird weiter unten als „ALL vs. ALL“ bezeichnet. Das Ergebnis
der Berechnung kann man als eine n × n Matrix auffassen, wobei die Hauptdiagonale
mit Nullen gefüllt ist. Aus Performance-Gründen werden wir, wie in Kapitel 5 beschrieben, auf die redundanten Berechnungen verzichten, d.h. die Ähnlichkeit zwischen zwei
identischen Benutzern und die Reihenfolge der Benutzer nicht berücksichtigen. Damit
n
 2
entstehen in diesem Szenario   =
n ⋅ ( n − 1)
Indizes, die berechnet werden müssen.
2
Immerhin wären es bei 1000 Benutzern bereits fast 500.000 Kombinationen, für die eine
Ähnlichkeit bestimmt werden soll.
Obwohl diese Lösung allumfassend ist und rein theoretisch die gesamte Menge der Profile in Beziehung zueinander bringt ahnt man schon an dem polynomiellen Wachstum
83
KAPITEL 6. EXPERIMENTELLE UNTERSUCHUNG
der Anzahl von Indizes, dass der Inferenz hier starke Grenzen gesetzt sind. Wir haben
daher ein weiteres Szenario in Erwägung gezogen.
6.1.2 1 versus ALL
Bei dem „1 vs. ALL“ Szenario wird ein Index nur für einen vordefinierten Benutzer zu
allen anderen Benutzern berechnet. Damit müssen nur n Indizes berechnet werden, ein
lineares Wachstum ist zumindest in der Anzahl der Benutzer gewährleistet. Die Vorgehensweise erlaubt eine zeitnahe Ermittlung der Ähnlichkeit und könnte z.B. dazu verwendet werden, um dem Benutzer auf der Webseite einige Kontaktvorschläge anzuzeigen, also Personen, die für ihn interessant wären. Hierbei könnte auch die Kombination
der Matching-Faktoren so angepasst werden, dass der Benutzer je nach seinen Präferenzen Kontaktvorschläge beispielsweise auf Interessensbasis oder auf Basis einer Partnersuche erhalten würde. Wir haben uns bei der Auswahl auf die erste Möglichkeit konzentriert. Um den Worst Case zu testen haben wir ein Administratorprofil als Vergleichsprofil genommen, das in allen getesteten Aktionen Aktivität vorzuweisen hatte.
6.2 Methodik
Das einzige approximative PyMLN-Inferenzverfahren, das für das in Kapitel 5 beschriebene Model fehlerfrei funktionierte, war Gibbs Sampling. Der Algorithmus MCSAT, der ebenfalls für die Berechnung in Frage kam, wurde bei der einfachsten Variante des Tests im nächsten Unterkapitel nach mehr als 3 Stunden abgebrochen, da die
Konvertierung der Formeln in die CNF (Konjunktive Normalform) bis dahin nicht fertig
wurde. Wir führen dies auf die noch nicht völlig ausgereifte Version von PyMLN zurück, die sich während der Fertigstellung dieser Arbeit stets in Entwicklung befand. Aus
diesen Gründen wurden alle nachfolgenden Untersuchungen mit dem Gibbs Sampling
Verfahren durchgeführt.
Das Gibbs Sampling ist ein approximativer Algorithmus, der nach einer bestimmten
Anzahl von Rechenschritten konvergiert. Die Anzahl dieser Schritte ist jedoch von Lauf
zu Lauf unterschiedlich, es kann also durchaus sein, dass der Algorithmus mit den selben Daten eine unterschiedliche Anzahl von Schritten benötigt. In der Regel befand sich
die Anzahl der benötigten Schritte bei unseren Untersuchungen zwischen 200 und 1000.
Um die Ergebnisse in einer einheitlichen Form zu präsentieren ist bei jeder nachfolgenden Diagrammdarstellung die Zeitdarstellung auf 500 Schritte normiert.
84
6.3 Skalierbarkeit bezüglich Benutzeranzahl
Für die Durchführung der im folgenden beschriebenen Experimente haben wir ein
konfigurierbares PHP-Programm entwickelt, dass die PPAO Ontologie für beide Szenarien generiert. Dabei wurden im Wesentlichen die Schritte aus Kapitel 5 umgesetzt und
die Information mit SQL Queries aus der IRCLOVE Datenbank in entsprechender Form
extrahiert und aufbereitet. Das Programm erzeugt die Evidence- und MLN- sowie eine
Query-Datei. Die Daten wurden dann innerhalb einer virtuellen Linux-Maschine in
PyMLN importiert und danach die Inferenz ausgeführt. Die technischen Daten zur Servermaschine finden sich im Anhang I.
6.3 Skalierbarkeit bezüglich Benutzeranzahl
Die erste Frage, die sich natürlicherweise aufzwang, war: Bei wie vielen Benutzern
kann die Profilähnlichkeit mit der PPAO Ontologie noch effektiv bestimmt werden? Bei
diesem Experiment haben wir lediglich eine einzige Aktion „read“ benutzt. Diese Aktion repräsentiert die Tatsache, dass ein Benutzer ein Medium aus einer bestimmten Kategorie des IRCLOVE Persönlichkeiten Portals sich angeschaut hat (vgl. Abb. 20). Obwohl die Verwendung einer einzigen Aktion relativ wenig Aussagekraft über die Ähnlichkeit zweier Benutzer hat, wurde diese Aktion so gewählt, dass sie für alle getesteten
Benutzer Wahrscheinlichkeitsverteilungen aufweist. Um eine gewisse statistische Relevanz zu erreichen, wurden zudem in diesem und allen weiteren Experimenten nur Benutzer berücksichtigt, die mindestens 10 Lesevorgänge ausgeführt hatten. Damit ist die
Befüllung dieser Aktion als ein Worst Case zu betrachten, da im Normalfall oftmals
keine Verteilungen für Aktionen vorliegen, weil Benutzer auf der IRCLOVE Webseite
nicht die volle Funktionalität ausnutzen. Die Anzahl der Kategorien, auf die sich die
Aktion „read“ bezieht, wurde auf 10 beschränkt. Es handelt sich um alle so genannte
Level 1 Kategorien, wie sie im Abschnitt 2.3.5 beschrieben und Anhang II aufgeführt
sind. Da Level 1 Kategorien in IRCLOVE keine Medien enthalten und somit keine direkten Lesungen in diesen Kategorien stattfinden können, wurden die jeweiligen Unterkategorien der Medien auf Level 1 Kategorien reduziert, beispielsweise wurde „Foto→Tiere→Säugetiere“ auf „Foto“ reduziert. Da in IRCLOVE die Level 1
Kategoriezugehörigkeit zusätzlich zu der eigentlichen Unterkategorie für jedes Medium
gespeichert wird, erforderte diese Reduktion keinen gesonderten maschinellen Aufwand. In anderen Domänen könnte jedoch ein zusätzliches „Aufrollen“ des Kategorienbaums notwendig sein. Hier wird auch deutlich, dass das Design der zugrunde liegenden
Datenbank ebenfalls von Bedeutung ist.
85
Das unten stehende Diagramm zeigt nun das Ergebnis dieses Tests für das „ALL vs.
ALL“ Szenario. Die Berechnung von 600 Benutzern musste aufgrund des enormen
Speicherverbrauchs des PyMLN-Prozesses und des daraus resultierenden starken
Swaping innerhalb des virtuellen und Host-Betriebsystems nach 7 Stunden abgebrochen
werden.
ALL vs. ALL - Benutzer
180
160
140
Minuten
120
100
80
60
40
20
0
100
200
300
400
500
Abb. 32: Berechnungsdauer des ALL vs. ALL Szenarios mit steigender Anzahl der Profile in 100-er
Schritten. Es wurden 10 Kategorien und die Aktion „read“ verwendet.
Dieses Experiment bringt keine all zu guten Nachrichten. Wie nach den Ausführungen
im Abschnitt 6.1.1 zu erwarten war, entwickelt sich die Berechnungsdauer ausgeprägt
polynomiell. Zudem haben wir einen weiteren Effekt beobachtet: bei diesem Test lag
die Zeit, die PyMLN für das Einlesen der MLN-Datei und das Erstellen des MLNs benötigte, ungefähr bei 50% der Gesamtzeit. Obwohl die MLN-Datei bei den letzten
Messpunkten mehrere Dutzend Megabyte groß war, ist dies dennoch ein Anzeichen für
Optimierungsschwäche in PyMLN. Der Effekt drehte sich im späteren Verlauf der Untersuchungen (siehe folgende Unterkapitel) um, als die Dateigröße nicht so stark anstieg, wie ihre Komplexität (z.B. mehr Aktionen).
6.4 Skalierbarkeit bezüglich Präzision
Als Nächstes schauen wir auf die Entwicklung der Performance mit steigender Anzahl
von Auswertungsfaktoren, die uns dabei helfen, die Aussagekraft des Ähnlichkeitsindex
zu verbessern.
86
6.4.1 Präzision durch Aktionen und Hobbys
Es ist klar, dass eine einzige Aktion als dynamische Rolle nicht ausreichend ist, um eine
aussagekräftige Ähnlichkeit der Profile zu ermitteln. Die Tatsache, dass zwei Benutzer
ähnliche Kategorien lesen sagt zwar durchaus etwas über gemeinsame Präferenzen aus,
die Analyse zusätzlicher Daten kann dieses Ergebnis jedoch stark verfeinern. Wir haben
daher die Aktionen „comment“ (kommentieren von Medien), „award“ (auszeichnen von
Medien) und „create“ (erstellen von Medien) hinzugenommen. Alle Aktionen bezogen
sich auf denselben dynamischen Bezugspunkt, nämlich die Level 1 Kategorien des
IRCLOVE Persönlichkeiten Portals.
Als letzten Schritt fügten wir noch einen statischen Bezugspunkt sprich Rolle hinzu und
schlossen die Hobby-Angaben der Benutzer in PPAO mit ein. Eine Menge von 30 häufigsten Hobbys (siehe Anhang III) wurde benutzt, um die Klasse der Hobbys zu
instanzieren. Für 500 Benutzer war die Auswertung von mehr als 2 Aktionen technisch
nicht möglich, da der PyMLN Prozess über 3 GB RAM benötigte und nicht von dem
Testserver bereitgestellt werden konnte. Wir werden auf dieses Problem weiter unten
genauer eingehen.
Abb. 33 zeigt nun die Ergebnisse dieses Experiments. Äußerst positiv ist zu bewerten,
dass der Anstieg der Berechnungszeit mit steigender Anzahl von auszuwertenden Aktionen recht moderat war. Eine Berechnung über 4 Aktionen gelang innerhalb 1 Stunde.
Die Verwendung von diesen Aktionen mit entsprechenden Gewichtungen lässt bereits
auf eine recht genaue Aussage über die Interessensgebiete von Benutzern schließen.
87
ALL vs. ALL - Aktionen und Hobbys
250
200
Minuten
150
100
50
0
read
read, comment read, comment, read, comment,
award
award, create
300 User
+ hobbies
(n=30)
500 User
Abb. 33: Berechnungsdauer des ALL vs. ALL Szenarios mit steigender Anzahl von Aktionen. Beim letzten Messpunkt wurden zusätzlich die Hobbys der Benutzer als statischer Bezugspunkt ausgewertet, wobei
eine Menge mit 30 häufigsten Hobbys benutzt wurde.
Logisch war eine zusätzliche Verfeinerung durch die Hobby-Angaben der Benutzer, da
ein gemeinsames Hobby eine starke Aussage über die Ähnlichkeit von Personen darstellt. Da statische Bezugspunkte von Benutzern selbst eingegeben werden, stellen sie
zudem pro-aktives Verhalten dar und sind so auf natürliche Weise aussagekräftiger als
zufallsbedingtes Verhalten. Wie man erkennt, führte diese Ergänzung zu einem signifikanten Anstieg der Berechnungszeit. Wir haben aus diesem Grund diese Tatsache genauer untersucht und im nächsten Diagramm die Ergebnisse zusammengefasst. Das
1 vs. ALL Szenario wurde mit 4 oben genannten Aktionen und 10 Kategorien generiert
und die Kardinalität der Menge von Hobbys schrittweise erhöht. Zudem haben wir für
diesen Test die komplette Menge aller Benutzer in der Community genommen, die sich
mindestens ein Medium angeschaut haben, d.h. für die in der Aktion „read“ eine Verteilung vorlag. Diese Eingrenzung war insofern sinnvoll, damit „leere“ Daten nicht analysiert werden – denn die Tatsache dass ein Benutzer ein Medium zuerst lesen muss stellt
eine notwendige Bedingung für alle weiteren Aktionen dar.
88
1 vs. ALL - Hobbys
250
200
Minuten
150
100
50
0
Hobbies
0
5
30
50
1653 User, 4 Aktionen, 10 Kategorien
Abb. 34: Berechnungsdauer des 1 vs. ALL Szenarios mit steigender Größe der Menge von Hobbys.
Ein weiteres Ziel dieses Experimentes war es herauszufinden, bei welcher Anzahl von
Hobbys eine „komfortable“ und dennoch präzise Berechnung des 1 vs. ALL Szenarios
möglich ist. Es zeigte sich, dass bereits eine kleine Anzahl von Hobbys dazu führt, dass
sich die Berechnungszeit vervielfacht. So stieg die Dauer des Laufs von 6 Minuten bei
Nichtvorhandensein der Hobbys auf das 5-fache von 30 Minuten bei lediglich 5 Hobbys. Das führt unweigerlich zu der Folgerung, dass die Klassen der statischen Bezugspunkte keine große Anzahl von Objekten beinhalten dürfen. Das ist nur dann der Fall,
wenn entweder die Domäne stark eingeschränkt oder die Relation von Benutzer und
Bezugspunkt eine 1:1 Relation ist (beispielsweise hat ein Benutzer nur eine Postleitzahl). Im zweiten Fall spielt die Kardinalität der Klasse dann keine Rolle.
Im Rahmen von IRCLOVE macht die Möglichkeit, dass ein Benutzer ein, zwei oder gar
alle Hobbys in der gewählten Menge haben kann, die Berechnung in höchstem Maße
intraktabel. Da IRCLOVE eine reale und statistisch relevante Datenbasis darstellt, führten wir eine Datenbankanalyse im Bezug auf das Auftreten von Hobbys durch. Dabei
wurden zuerst alle Benutzerpaare, die jeweils gemeinsame Hobbys, haben in eine temporäre indizierte Tabelle eingefügt. Danach wurden nur die eindeutigen Benutzerpaare
gezählt. Als Ergebnis bekamen wir die Anzahl aller Benutzerpaare, die mindestens ein
gemeinsames Hobby haben. Das folgende Diagramm zeigt diesen Sachverhalt im Verhältnis zu steigender Kardinalität der Menge von Hobbys. Die zweite Säule symbolisiert
89
100
90
80
Userpaare
70
60
50
40
30
20
10
0
1
5
10
Eindeutige Userpaare
15
Hobby-Matches
20
25
30
Polynomielle Trendapproximation
Abb. 35: Entwicklung der Anzahl von Benutzerpaaren, die mind. ein gemeinsames Hobby haben, sowie
die Anzahl der Gesamtübereinstimmungen bei Hobbys bei steigender Kardinalität der Hobbymenge.
Es sei noch angemerkt, dass die entsprechenden SQL-Abfragen auf der MySQL Datenbank im leichtesten Fall (n=1) mindestens 10 Minuten, und im schwersten Fall (n=30)
mind. 2 Stunden dauerten. Das Diagramm zeigt eindrucksvoll, welche kombinatorische
Komplexität eine solche Analyse schon für eine relativ kleine Datenbasis wie
IRCLOVE besitzt. Unter diesen Bedingungen ist die Performance der MLNBerechnung, wie sie in Abb. 34 gezeigt ist, sehr zufrieden stellend. Eine interessante
Erkenntnis ist zudem, dass die optimale Anzahl der zu analysierenden Hobbys zwischen
5 und 10 liegt. Danach stieg die Anzahl der Überstimmungen, und damit die Präzision,
nur geringfügig an.
6.4.2 Präzision durch Kategorien
Eine weitere Möglichkeit, die Präzision der Berechnung zu verbessern, ist die Erhöhung
der Anzahl von Kategorien (also unseren Bezugspunkten). In diesem Experiment untersuchten wir, wie stark sich das auf die Berechnungsdauer auswirkt. Es wurde das
1 vs. ALL Szenario, wie es im vorherigen Abschnitt beschrieben ist, verwendet, da es
leichter und dementsprechend praktischer zu ermitteln ist. Die Kardinalität der Hobbymenge wurde auf 5 gesetzt. Da es lediglich 10 Level 1-Kategorien gibt, wurden für grö-
90
Millionen
die gesamte Anzahl der Matches für Hobbys, da Benutzer mehrere Übereinstimmungen
bei Hobbys haben können. Es wurden alle verfügbaren IRCLOVE Daten benutzt, die
Anzahl der Profile lag bei 37490.
ßere Mengen die Unterkategorien verwendet. Es gab zum Zeitpunkt des Tests 520 Unterkategorien, so dass die jeweilige Testmenge per Zufall aus dieser Gesamtmenge ausgewählt wurde. Zu berücksichtigen ist, dass die Level 1 Kategorien den kompletten
möglichen Aktionsbereich eines Benutzers abdecken, n zufällig ausgewählte Unterkategorien jedoch nur eine Teilmenge dieses Aktionsbereiches darstellen. Die Wahrscheinlichkeitsverteilungen innerhalb dieser Menge mussten also entsprechend angepasst werden, was den Aufwand auf der Datenbank-Seite um die MLN-Dateien zu erzeugen erheblich erhöhte.
Wie das Ergebnis in Abb. 36 zeigt, fällt der Anstieg in diesem Szenario fast linear und
damit sehr moderat aus. Die Auslastung der Aktionen im Bezug auf Verteilungsdaten ist
von der Wahl der Kategorien abhängig. Da für jeden Lauf andere Kategorien verwendet
wurden, ist eine gewisse Toleranz für die Messpunkte zu berücksichtigen. Auch führte
die randomisierte Wahl der Kategorien dazu, dass für viele Benutzer keine Wahrscheinlichkeitsverteilungen in den jeweiligen Aktionen vorhanden waren. Die optimierte Aufbauweise der PPAO Ontologie trug hier zum guten Komplexitätsverhalten maßgeblich
bei.
1 vs. ALL - Kategorien
60
55
50
Minuten
45
40
35
30
25
20
10
20
30
40
50
1653 User, 4 Aktionen + Hobbies (n=5)
Abb. 36: Berechnungsdauer des 1 vs. ALL Szenarios mit steigender Anzahl von Kategorien.
Intuitiv führt die Erhöhung der Anzahl von Kategorien zur besseren Aussagekräftigkeit
des Ähnlichkeitsindex. Allerdings fanden wir heraus, dass in der Praxis die Streuung
innerhalb der Verteilungen bei großer Differenzierung von Kategorien massiv zunimmt.
91
Das bedeutet, dass einzelne Wahrscheinlichkeiten sehr klein ausfallen (im Zehntel- oder
Hundertstel-Prozent Bereich) und keine eindeutigen Schwerpunkte im Verhalten der
Benutzer ausgeprägt werden. Dies hat aus unserer Sicht zwei Gründe: der erste besteht
darin, dass das Verhalten der Benutzer in IRCLOVE bei großem Differenzierungsgrad
stark zufallsgeprägt ist. Der Benutzer interagiert mit dem System auf eine sporadische
Weise, die statistisch äußerst schwer greifbar ist. Diese schwerwiegende Erkenntnis
werden wir in unserer Zusammenfassung nochmals aufgreifen. Der zweite Grund besteht in der medialen Auslastung der Kategorien. Diese schwankt innerhalb des
IRCLOVE Systems sehr stark, so existieren Unterkategorien, die einige bis Dutzend
Medien beinhalten, andere dagegen können hunderte Medien beinhalten. Da wir die
Wahrscheinlichkeit einer Aktion bezüglich einer Kategorie unter Nutzung der Gesamtheit aller Aktionsereignisse messen, ist es offensichtlich, dass eine stark ausgelastete
Kategorie mehr Chancen besitzt, eine höhere Trefferquote zu erzielen, weil sie einfach
mehr Inhalte enthält. Dieser Verzerrungseffekt ist bereits bei der Nutzung von Level 1
Kategorien sichtbar, da z.B. die Kategorie Foto 10 mal mehr Medien enthält, als die Kategorie Gedicht.
Eine Lösung für dieses Problem besteht darin, die Wahrscheinlichkeit für ein Aktionsereignis lediglich anhand der Anzahl von Medien innerhalb einer Kategorie zu normieren, d.h. hat sich z.B. ein Benutzer 100 Fotos aus 7000 angeschaut, so wäre die Wahrscheinlichkeit für dieses Ereignis bei 7%. Analog dazu wäre sie bei 100 aus 100 Gedichten bei 100%. Man erkennt, dass wir bei dieser Vorgehensweise die Kategorie nicht
mehr als eine einzige Zufallsvariable betrachten. MLNs sind jedoch für den Aufbau solcher Konstruktionen nur eingeschränkt geeignet, da Wahrscheinlichkeiten nicht direkt,
sondern nur über relative Gewichte eingegeben werden können. Es ist daher schwierig
zu gewährleisten, dass diese Gewichte in richtigem Verhältnis zueinander stehen, um
die Wahrscheinlichkeiten maßgerecht abzubilden. Neue Methoden, wie die von Jain
vorgeschlagene Einführung der Soft Evidence und adaptiver MLNs, könnten hier zur
Verbesserung dieses Verhaltens beitragen (siehe auch [JB10]). Diese Techniken waren
aber zum Zeitpunkt der Erstellung dieser Arbeit noch nicht praxisgerecht ausgereift.
6.5 Speicherverbrauch
Der Grund, warum einige Tests nicht mit größeren Datenmengen fortgeführt werden
konnten, bestand im enormen Arbeitsspeicherverbrauch der Berechnung. Da das für die
praktische Anwendung der PPAO Ontologie bzw. MLNs im Allgemeinen von großer
Bedeutung ist, möchten wir auf den Speicherverbrauch etwas näher eingehen.
92
6.5 Speicherverbrauch
Die MLN-Wissensbasis bestand stets aus zwei Dateien, wobei die Evidence-Datei nur
bei statischen Bezugspunkten (also im getesteten Fall die Hobbys) eine relevante Größe
erreichte. Zusammengezählt wuchsen diese Dateien zwar mit der Anzahl der Benutzer,
Aktionen, Kategorien und Hobbys an, ihre Größe befand sich aber dennoch in einem
durchaus übersichtlichen Rahmen. Die Tabelle zeigt einige wenige Beispiele aus den
oben beschriebenen Experimenten:
93
Experiment
Größe der Wissensbasis
ALL vs. ALL
300 U / 10 C / 2 A
500 U / 10 C / 3 A
~10 MB
~ 36 MB
1653 U / 10 C / 4 A / 1 S
1653 U / 40 C / 4 A / 1 S
~ 2 MB
~ 4 MB
1 vs. ALL
Tabelle 7: Die Größe der PPAO bei einigen durchgeführten Experimenten. Dabei steht U für Anzahl der
Benutzer, C für Anzahl der Kategorien, A für Anzahl der Aktionen und S für die Berücksichtigung von
Hobbys.
4
1,2
3,5
1
3
0,8
GB
2,5
2
0,6
1,5
0,4
1
0,2
0,5
0
0
300 U / 1 A
300 U / 2 A
300 U / 3 A
RAM-Verbrauch
300 U / 4 A 300 U / 4 A / 1 S 500 U / 2 A
500 U / 3 A
# ground atoms + # ground formulas
Abb. 37: Speicherverbrauch und Anzahl von Grundprädikaten und Formeln im Experiment aus Abschnitt
6.4.1. U steht für Anzahl der Benutzer, A für Anzahl der Aktionen und S für Verwendung von Hobbys.
Die Balken stellen den Speicherverbrauch, die Linie die Anzahl der Grundelemente dar.
Die Grafik zeigt, dass eine geringere Anzahl von logischen Grundelementen bei 500
Benutzern dennoch zu einem größeren Speicherverbrauch führte. Man könnte diese Tatsache dadurch erklären, dass die Verarbeitung von festen Fakten (hard evidence), wie
94
Millionen
Der RAM-Verbrauch korrelierte hauptsächlich mit der Anzahl der Grundprädikate
(ground atoms) und Grundformeln (ground formulas). Wir werden dies exemplarisch an
dem im Abschnitt 6.4.1 und Abb. 33 beschriebenen Experiment im folgenden Diagramm zeigen:
6.6 Aussagekraft des Ähnlichkeitsindex
sie im Fall von Hobbys auftritt, sich von der probabilistischen Verarbeitung innerhalb
von PyMLN unterscheidet. Zudem ist die Anzahl der zu berechnenden Ähnlichkeitsindizes bei 500 Benutzern deutlich höher als bei 300. Folglich verursacht die Berechnung
der Match-Prädikate in PPAO den meisten Speicheraufwand. Ebenfalls haben wir beobachtet, dass die Anzahl der Grundprädikate bei dem ALL vs. ALL Szenario stets kleiner als die Anzahl der Grundformeln war. Im 1 vs. ALL Szenario gab es dagegen fast
doppelt so viele Grundformeln als Grundprädikate. Auch hier liegt der wesentliche
Grund in der Anzahl der Match-Prädikate, die bei dem ALL vs. ALL Szenario um Faktoren höher ist.
Bisher haben wir lediglich die Skalierbarkeit der PPAO Ontologie untersucht. Es blieb
jedoch die Frage unbeantwortet, ob und wie der Ähnlichkeitsindex in der Praxis wirklich funktioniert. In diesem Unterkapitel soll die Funktionsweise des Ähnlichkeitsindex
erläutert werden. Anschließend wird anhand von zwei Experimenten demonstriert, dass
der mit PPAO berechnete Ähnlichkeitsindex aussagekräftig ist und damit ein effektives
Matching von Personen ermöglicht.
6.6.1 Wie funktioniert der Ähnlichkeitsindex?
Um das Beispiel aus der Einleitung zu ergänzen nehmen wir an, dass vier Benutzer
Paul, Anna, Peter und Lena Bilder aus Kategorien „Katze“ und „Maus“ betrachten mit:
Kategorie
Benutzer
Paul
Anna
Peter
Lena
Katze
0.3
0.8
0.8
1
Maus
0.7
0.2
0.2
0
Tabelle 8: Beispiele von einfachen Wahrscheinlichkeitsverteilungen für vier Benutzer, die Medien aus
zwei Kategorien betrachten.
Paul und Anna besitzen gegensätzliches Leseverhalten, wogegen Peter eine identische
Verteilung wie Anna aufweist. Lena ist eine Benutzerin, die sich ausschließlich Bilder
von Katzen anschaut.
Ein gewöhnliches Ähnlichkeitsmaß könnte beispielsweise wie folgt aussehen:
95
Suser1,user 2 = ∑ Puser1 (c) − Puser 2 (c)
c∈C
wobei die Menge C alle Kategorien resp. Bezugspunkte enthält. Würde man dieses
Maß auf die oben beschriebene Situation anwenden, so wären Benutzer Anna und Peter
identisch und somit am ähnlichsten zueinander. Der Nachteil einer solchen Betrachtungsweise liegt darin, dass hier lediglich die proportionale Verteilung des vergangenen
Verhaltens von Benutzern als Ähnlichkeit der Interessen deklariert wird. Somit stellt ein
solches Maß zwar eine „optische“ Ähnlichkeit der Verteilungen zweifelsfrei fest, betrachtet die eigentlichen Wahrscheinlichkeiten aber eher als Gewichte und basiert nicht
auf einer statistischen Herangehensweise.
MLNs bieten uns als probabilistischer Formalismus die Möglichkeit fundierte statistische Analyse auf eine elegante Weise umzusetzen. Da der Gesamtähnlichkeitsindex eine Komposition von Sub-Indizes darstellt, ist gerade die Funktionsweise der SubIndizes ausschlaggebend für das Verständnis des Modells. Dafür stelle man sich das
folgende Gedankenspiel vor:
Es seien Verteilungen von zwei Benutzern aus der Vergangenheit bereits bekannt. Man setze diese beiden Personen vor den Computer und fordere sie
gleichzeitig auf, nun als nächstes sich ein Bild aus der Kategorie „Katze“ oder
„Maus“ anzuschauen. Mit welcher Wahrscheinlichkeit werden die beiden Benutzer ein und dieselbe Kategorie wählen?
Die im Kapitel 5 beschriebene Implementierung setzt genau diese Fragestellung um.
Was würde passieren, wenn man dieses Modell nun auf die oben beschriebene Situation
anwenden würde? In der nächsten Abbildung haben wir die Benutzer Anna mit Peter
und Lena verglichen, indem stochastische Entscheidungsbäume, die aus der Darstellung
von bedingten Wahrscheinlichkeiten bekannt sind, für jede Situation aufgestellt wurden.
96
0.2
0.8
0.8
0.2
Anna
Anna
Katze
0.8
Maus
0.2
0.8
Peter
Katze
0.2
1
Pe-
Katze
0
LeMaus
∑: 0.68
Maus
1
0
Lena
Katze
Maus
∑: 0.8
Abb. 38: Zwei stochastische Entscheidungsbäume demonstrieren, wie die Wahrscheinlichkeit für einen
Sub-Index berechnet wird. Dabei sind die Verteilungen für Anna und Peter bezüglich der Kategorien
„Katze“ und „Maus“ identisch. Lena liest dagegen ausschließlich die „Katzen“-Kategorie.
Im Gegensatz zu dem oben beschriebenen Maß erfährt man hier, dass die Wahrscheinlichkeit, dass Anna und Lena sich mehr ähneln, höher ist als bei Anna und Peter. Dies
ist darauf zurückzuführen, dass bei Peter eine Restwahrscheinlichkeit besteht, dass er
eine abweichende Kategorie wählen wird. Bei Lena dagegen ist es sicher, dass sie sich
nur Katzen anschauen wird. Statt der reinen Betrachtung der Proportionen der einzelnen
Interessensschwerpunkte, die nur auf der Vergangenheit basieren, ist diese Art von Modellierung also ein stochastischer Blick in die Zukunft. Der Index priorisiert eindeutige
Spitzen in der Verteilung und somit eindeutig ausgeprägte Interessensschwerpunkte.
Die Korrektheit des Index ist dadurch gewährleistet, dass er gegensätzliches und abweichendes Verhalten entsprechend untergewichtet. Beispielsweise würde die Wahrscheinlichkeit für Paul und Anna, die gegensätzliche Verteilungen aufweisen, lediglich bei
0.38 liegen und ist damit erheblich niedriger als für die oben erwähnten Paare. Wir betrachten nun zwei Beispiele auf realen Daten.
97
6.6.2 Ähnlichkeit von realen Profilen im 1 vs. ALL Szenario
Es wurden vier reale Personen und Benutzer der IRCLOVE Community ausgesucht, die
wir als A, B, C und D bezeichnen werden. Die Profile wurden so gewählt, dass sie bestimmten Nutzergruppen entsprechen:
Profil A – ist ein Administrator-Profil und hat eine hohe Aktivität in allen Aktionen vorzuweisen.
Profil B – ist ein Poweruser-Profil und hat ebenfalls eine hohe Aktivität vorzuweisen.
Profil C – ist ein Normalbenutzer-Profil, das Aktivität in einigen Aktionen vorzuweisen hat.
Profil D – ist ein Gelegenheitsbenutzer-Profil, das nur bezüglich einer Aktion
eine eindeutige Verteilung aufweist.
Die Wahrscheinlichkeitsverteilungen der einzelnen Aktionen für jeden Benutzer sind in
Anhang IV aufgeführt. Man kann dort leicht bildlich nachvollziehen, welche
Verhaltsmuster bei je zwei Benutzern ähnlich sind. Deshalb ist die Betrachtung der einzelnen, im Anhang aufgeführten, Verteilungen für das Nachvollziehen dieses Experiments von großem Nutzen. Erwähnenswert ist zudem, dass die Benutzer A und B sowie
A und D ein gemeinsames Hobby teilten.
Um das Beispiel übersichtlich zu halten haben wir das 1 vs. ALL Szenario und die im
Abschnitt 6.4.1 und Abb. 34 beschriebene und gezeigte Konfiguration für dieses Szenario benutzt und Profil A mit den drei oben genannten anderen Profilen verglichen. Die
Anzahl der untersuchten Hobbys wurde auf 5 gesetzt. Die Gewichtung der AktionenMatches wurde für alle Aktionen auf 0.2 gesetzt. Obwohl die Aktionen in der Praxis
unterschiedlich gewichtet werden sollten, da z.B. die Tatsache dass ein Benutzer selbst
Medien in Kategorien erstellt gewichtiger als die Tatsache ist, dass er dort Medien lediglich betrachtet. Wir haben die Gewichtung jedoch identisch gelassen, um die Aussagekraft der einzelnen Subindizes in der Demonstration nicht zu verzerren. Die Gewichtung wurde bewusst niedrig gewählt, um den Gesamtindex vergleichbar zu halten. Bei
zu großer Gewichtung der Sub-Indizes tendierte der Ähnlichkeitsindex auch bei schwächeren Matches gegen 1. Die Gewichtung eines Hobby-Matches wurde auf 0.5 gesetzt
und damit stärker als die dynamischen Rollen bewertet, da die Hobby-Angabe proaktives Benutzerverhalten darstellt.
98
Tabelle 9 zeigt die Ergebnisse des Experiments. Die einzelnen Sub-Indizes wurden zusätzlich ermittelt, um die Zusammensetzung des Gesamtähnlichkeitsindex zu verdeutlichen.
read
comment
award
create
hobby
Ähnlichkeitsindex
A ↔ B
0.266
0.330
0.324
0.466
0.613
0.923
A ↔ C
0.205
0.254
0
0.22
0
0.528
A ↔ D
0.282
0
0
0
0.64
0.737
Tabelle 9: Beispiel der Berechnung des Ähnlichkeitsindex zwischen 4 Benutzern im 1 vs. ALL Szenario.
In den Spalten werden zuerst die Sub-Indizes (also Matches in einzelnen Aktionen) aufgelistet und nachfolgend die berechnete Gesamtähnlichkeit. Die realen Wahrscheinlichkeitsverteilungen von Benutzern A
bis D sind im Anhang IV aufgeführt.
Man erkennt, dass die Anwesenheit von identischen Hobbys wie gewünscht stark gewichtet wird und die Gesamtähnlichkeit bei den entsprechenden Benutzern höher ausfällt. Deutlich wird dies aufgrund der Tatsache, dass obwohl Benutzer C zu A mehr
Matches aufweist, seine Ähnlichkeit zu A niedriger als von Benutzer D ist. Die Benutzer A und B weisen die höchste Ähnlichkeit auf, da sie außer einem Hobby-Match noch
weitere Matches in allen Kategorien aufweisen. Grundsätzlich haben wir beobachtet,
dass der Gesamtindex aufgrund seiner Beschaffenheit dazu tendiert, relativ groß zu
werden, wenn mehrere Matches vorhanden sind. Dieser Effekt ist aber durchaus erwünscht, da Übereinstimmungen in mehreren Aktionen dafür sprechen, dass Profile sich
ähnlich verhalten.
Das Experiment zeigt, dass die Berechnung plausibel ist und die resultierenden IndexZahlen im Einklang mit dem stehen, was man bei einem solchen Szenario erwarten
würde. Zusätzlich kann in PPAO stets eine Feinabstimmung durch die Anpassung der
Gewichtung der Sub-Indizes erfolgen, falls es die Applikation erfordert.
99
6.6.3 Pseudo-Segmentierung im ALL vs. ALL Szenario
Wir haben bereits erwähnt, dass man mit PPAO auch andere Fragestellungen, so z.B.
auch die Bildung von Segmenten innerhalb der Benutzerbasis untersuchen könnte.
Grundsätzlich ist dafür eine Erweiterung des Inferenz-spezifischen Teiles der Ontologie
notwendig. In diesem Experiment werden wir zeigen, dass man schon mit der beschriebenen PPAO Implementierung Benutzer-Segmente identifizieren kann. Dabei stellt gerade das Vorhandensein von gemeinsamen Interessen das entscheidende Kriterium für
die Bildung dieser Segmente dar.
Das ALL vs. ALL Szenario mit 500 Benutzern aus Unterkapitel 6.2 wurde für dieses
Experiment verwendet. Nur die Aktion „read“ wurde miteinbezogen, um das Beispiel
übersichtlich zu halten. Nach der Berechnung wurden die errechneten Indizes in eine
Datenbank importiert, um eine schnellere Verarbeitung zu ermöglichen. Nach dem Zufallsprinzip wurde einer der 500 Benutzer ausgewählt, den wir im folgenden als „Masteruser“ bezeichnen. Zu diesem wurde der erst-, fünft- und zehntähnlichste Benutzer
ausgesucht. Umgekehrt wurden auch die schlechten, d.h. unähnlichsten, Benutzer nach
demselben Prinzip ausgesucht. Der Abstand im Ranking der Benutzer wurde so gewählt, damit man besser erkennen kann, wie sich die Indizes im Verhältnis zueinander
ändern. Danach wurden die 3 „Tops“ und „Flops“ jeweils untereinander verglichen.
Das Ergebnis des Experimentes wird in Abb. 39 gezeigt. Für jeden Benutzer haben wir
seine Wahrscheinlichkeitsverteilung für „read“ aufgeführt, wobei sich die Beschreibungen der einzelnen Kategorie-IDs im Anhang II befinden. Die „Tops“ und „Flops“ stehen
im Einklang mit der, in Abschnitt 6.2.1 erklärten, Funktionsweise des Ähnlichkeitsindex. Demnach ist der, zum Masteruser am besten „passende“, Benutzer eine Person, die
hundertprozentiges Interesse für die Kategorie 2 aufweist, da der Masteruser Medien
aus dieser Kategorie am häufigsten betrachtet. Die etwas „schlechteren“ Benutzer weisen dagegen zusätzliche Interessensgebiete auf.
100
Top 10 - Index: 0.3565
80,00%
60,00%
40,00%
20,00%
0,00%
0.5904
Top 5 - Index: 0.3826
80,00%
60,00%
0.7226
40,00%
20,00%
0,00%
0.7443
Top 1 - Index: 0.3956
100,00%
80,00%
60,00%
40,00%
20,00%
0,00%
Masteruser
60,00%
40,00%
20,00%
0,00%
1
2
3
5
6
7
8
9
11 13
Flop 1 - Index: 0.0
60,00%
40,00%
20,00%
0.4773
0,00%
Flop 5 - Index: 0.0
100,00%
80,00%
60,00%
0.3722
40,00%
20,00%
0,00%
Flop 10 - Index: 0.034
0.1165
4
80,00%
60,00%
40,00%
20,00%
0,00%
Abb. 39: Segmentierung - für einen Benutzer wurden das 1,5 und 10 ähnlichste Profil berechnet und umgekehrt. Die neben Pfeilen stehenden Zahlen bezeichnen die Ähnlichkeit der Profile untereinander.
101
Interessant und besonders eindrucksvoll an diesem Beispiel ist, dass es deutlich veranschaulicht, wie Segmente gebildet werden können. Man erkennt, dass die „Tops“ allesamt eine hohe Ähnlichkeit zueinander aufweisen und damit ein Segment bilden. Zudem fällt auf, dass mit steigender Distanz zum Top 1 - Benutzer die Ähnlichkeit der Benutzer untereinander abfällt. Da wir lediglich 500 Benutzer verarbeitet haben, sehen wir
diesen Abfall schon in der Menge der besten Zehn recht deutlich. Es ist somit klar, dass
man durch die Wahl eines ausgewählten Repräsentanten, wie in unserem Fall des Masterusers, Gruppen von Personen identifizieren kann, die ähnliche Interessensgebiete haben. Solche Informationen sind unter anderem auch für Marketingzwecke von großem
Nutzen, da mit ihrer Hilfe den Benutzern entsprechende Werbeangebote gemacht werden können.
Den Effekt der abfallenden Ähnlichkeit sehen wir in diesem Experiment ebenfalls bei
den „Flop“-Benutzern. Wir führen das aber auf ein zufälliges Auftreten zurück. In der
Regel wird sich kein „Gegensegment“ herausbilden, da die Interessen der Flops völlig
unterschiedlich und dennoch gegensätzlich zum Masteruser sein können.
6.7 Die Grenzen
Unsere Experimente haben gezeigt, dass sich die PPAO Ontologie in der Anzahl von
Faktoren, die die Präzision der Berechnung verbessern, gut skalieren lässt. Dagegen sahen wir bei der Erhöhung der Benutzeranzahl, sowohl in Hinsicht auf die Verarbeitungszeit, als auch den Arbeitsspeicherverbrauch klare Grenzen. Eine Berechnung mit
500 Benutzern und mehr als 2 Aktionen scheiterte bereits an dem zu hohen Speicherverbrauch der Berechnung. Eine wichtige Erkenntnis zeigte die Untersuchung von Hobbys im Blick auf statische Bezugspunkte: zwar verursachen statische Eigenschaften, von
denen ein Benutzer eine Teilmenge besitzen kann, eine enorme kombinatorische Komplexität, und damit auch längere Berechnungszeiten. Es ist aber oftmals ausreichend,
nicht die gesamte Menge sondern eine spezielle Auswahl zu betrachten, um eine ausreichend genaue Aussage über die Ähnlichkeit von Profilen zu erhalten.
Das wesentliche Problem der Markov Logic Networks, und speziell auch der ihnen zugrunde liegenden Prädikatenlogik liegt in der „possible worlds“-Betrachtungsweise.
Diese führt insbesondere dazu, dass alle möglichen Belegungsvarianten aller Prädikate
und Formeln aufgebaut werden. In Verbindung mit dem polynomiellen Anstieg der zu
untersuchenden Benutzerpaare verursachte das eine sehr große Anzahl von möglichen
Belegungen in den Match-Formeln. Das wiederum führte zu der hohen Zeit- und Spei-
102
6.7 Die Grenzen
cherkomplexität. Diese Feststellung macht also deutlich, dass der Einsatz von MLNs für
unsere Problemstellung im kleinen Rahmen zwar durchaus praktikabel und ausreichend
präzise sein kann. Für eine vollständige mittelgroße Profilbasis, wie sie in der
IRCLOVE Community vorhanden ist, ist die Inferenz in PPAO nicht ohne Weiteres
traktabel – und das obwohl die Ontologie bereits optimiert und ein Approximationsalgorithmus für die Inferenz benutzt wurde. Man bedenke allerdings, dass für 50.000 Profile
fast 1,25 Milliarden Indizes zu berechnen wären und große Web- oder EntepriseApplikationen eine Datenbasis haben können, die IRCLOVE um zehn- oder gar hundertfache übersteigt. Somit beschränkt sich die Schwierigkeit nicht lediglich auf die
Traktabilität der Inferenz in MLNs. Die gewaltige Größe der Problemstellung an sich
spielt bei der Betrachtung von solchen, wie von uns vorgenommenen, Zielsetzungen
eine entscheidende Rolle.
Ein Versuch aus dem oben beschriebenen Dilemma herauszukommen bestand im
1 vs. ALL Szenario. Dieses Szenario würde sich anbieten, um dem Benutzer in Echtzeit
bestimmte Vorschläge zu machen, in unserem speziellen Fall also Kontaktvorschläge zu
anderen Benutzern. Die Berechnung auf unserem Testserver mit verschiedenen Präzisionsstufen war aber zu keinem Zeitpunkt schnell genug, um eine Echtzeit-Verarbeitung
zu ermöglichen, da sie zwischen einigen bis dutzenden Minuten andauerte.
Die beiden gezeigten Szenarien bergen jedoch Potenzial für eine weitere Art von Berechnung: es können bestimmte Nutzergruppen untereinander oder nur eine bestimmte
Nutzergruppe gegen alle anderen getestet werden. Diese Vorgehensweise ist in der Praxis sinnvoll, da in stark frequentierten Web-Applikationen, so auch in Communities, die
Benutzerbasis nie vollständig aktiv ist. Deshalb ist die Untersuchung der Ähnlichkeit
von Profilen oder auch anderen Fragestellungen (z.B. Verhaltensanalyse) in solchen
Domänen für die gesamte Benutzerbasis wenig sinnvoll, da man dabei viele inaktive
Profile und veraltete Daten verarbeitet. Wie unsere Untersuchungen zeigen, würde die
oben genannte Art von Berechnung innerhalb der PPAO Ontologie mit einer speziell
gewählten Profilmenge praxisgerecht anwendbar und ausreichend präzise sein. Sie kann
ohne allzu großen Zusatzaufwand und beispielsweise in nächtlichen Wartungszyklen
durchgeführt werden – und stellt somit eine reale Möglichkeit dar, die PPAO Ontologie
in der Praxis anzuwenden. Wir werden zusätzlich auf weitere Möglichkeiten zur Verbesserung der praktischen Anwendbarkeit von MLN-basierten Ontologien in der nun
folgenden Zusammenfassung dieser Diplomarbeit eingehen.
103
KAPITEL 7. ZUSAMMENFASSUNG
7.1 Rückblick
Die Zielsetzung dieser Arbeit war es, ein ontologiebasiertes probabilistisches Modell für
die Analyse von Profilen zu entwickeln und seine Anwendung an einer konkreten Aufgabe zu demonstrieren. Dabei war es wichtig, eine praxisgerechte Ontologie zu entwickeln, die über die reine Papierform hinausgehen würde und in einer realen Applikation
Anwendung finden könnte – denn nur auf diese Weise können semantische Technologien ihre Stärken unter Beweis stellen. Auch aktuelle Themen, die wiederum aus der
Praxis kommen, so auch die Berücksichtigung der Vertrauensregulierung, sollten integriert werden. Im zweiten Kapitel haben wir zuerst Grundlagen und Begriffe der aktuellen Forschung erörtert, die für diese Arbeit relevant waren - insbesondere den Begriff
der Ontologien, die ihn umgebenden Forschungsbereiche und Technologien wie OWL
oder Beschreibungslogiken, sowie die praktischen Einsatzmöglichkeiten von
Ontologien im Allgemeinen. Außerdem wurde die vom Autor der Arbeit entwickelte
und betriebene IRCLOVE Community beschrieben, deren Struktur und Daten die Basis
für den experimentellen Teil dieser Arbeit bildeten.
Eine der großen Schwierigkeiten dieser Arbeit bestand darin, den richtigen Formalismus
für die Zielsetzung der Arbeit zu finden, da er die Möglichkeit bieten sollte,
probabilistische Information in die Ontologie einzubinden. Außerdem musste dieser
Formalismus in der Praxis anwendbar sein. Das dritte Kapitel spiegelt diese Suche in
verkürzter Form wider und gibt einen, zugegebenermaßen aus Platzgründen unvollständigen, Überblick über zentrale Entwicklungen und Bemühungen der Forschung während der letzten Dekaden, probabilistische Information in Ontologien zu integrieren.
Nicht verwunderlich war es, dass hierfür zahlreiche Ansätzen und Modelle existierten.
Die Mehrzahl dieser Formalismen, insbesondere derer, die auf Beschreibungslogiken
basieren (z.B. auch OWL-Erweiterungen), liegt heutzutage lediglich in Papierform vor.
Der Hauptgrund, warum diese nie eine praktische Umsetzung widerfuhren liegt vermutlich in der hohen algorithmischen Zeitkomplexität der Inferenz. Das von uns in Kapitel
3 vorgestellte Forschungsfeld des Statischen Relationalen Lernens stellt in diesem Be-
105
zug eine Ausnahme dar, da hier approximative Techniken verwendet werden, die die
Performance erheblich steigern. Sowohl MLNs als auch BLOG stellen unserer Meinung
nach viel versprechende Technologien dar. Zum Abschluss des Kapitels haben wir deshalb begründet, warum MLNs nach einer langen und fast aussichtslosen Suche das
Werkzeug der Wahl für die Umsetzung dieser Arbeit waren.
Im Kapitel 4 wurde ein abstraktes Modell der PPAO Ontologie und Begrifflichkeiten
definiert, die später verwendet wurden. Die Ontologie wurde dabei so allgemein konzipiert, dass sie auf der abstrakten Ebene zahlreiche Analysen ermöglichen könnte. Da es
aus Platzgründen nur möglich war, lediglich eine spezielle Analyse genau zu untersuchen, ließen wir uns von der Frage inspirieren, wie man zwei Benutzern auf Basis ihrer
Angaben und Verhaltens bezogen auf gemeinsame Interessen einen Vorschlag zu Kontaktaufnahme machen könnte. Dafür musste die Ähnlichkeit der Benutzerprofile ermittelt werden.
Basierend auf diesen Überlegungen wurde die Implementierung von PPAO in Kapitel 5
beschrieben und mit zahlreichen Beispielen mit realen Daten belegt. Dabei ist für die
Analyse der Fragestellung, nämlich die Berechnung des Ähnlichkeitsindex, nur der Inferenz-Teil der Ontologie (also die Match-Prädikate) zuständig. Die Integration der
(probabilistischen) Daten kann dagegen für beliebige andere Aufgaben benutzt werden.
Zusätzlich haben wir gezeigt, wie man mit wenigen Veränderungen multiple Datenquellen in PPAO integrieren und gewichten kann, um eine effektive Regulierung der Vertrauenswürdigkeit von Quellen zu ermöglichen.
Im Kapitel 6 führten wir anschließend zahlreiche zum Teil recht aufwendige und zeitintensive Experimente durch. Sie allesamt dienten dem Zweck, die praktische Anwendbarkeit von PPAO unter verschiedenen Blickwinkeln zu untersuchen und zu demonstrieren. Dabei konzentrierten wir uns auf zwei Aspekte: zum einen die bekannte Problematik der Zeitkomplexität bei derartigen Formalismen, die sofort die Frage nach der
Skalierbarkeit der Ontologie und der Grenzen diesbezüglich aufwarf. Es stellte sich heraus, dass sich PPAO mit der Erhöhung von Faktoren, die zur Verbesserung der Aussagekraft des Ähnlichkeitsindex beitrugen viel besser skalieren ließ, als mit der Vergrößerung des zu untersuchenden Benutzerbestandes. Sowohl bei der Verarbeitungszeit als
auch dem Speicherverbrauch der Berechnung wurden feste Grenzen für die Machbarkeit
unseres Vorhabens deutlich. Wir haben diese Grenzen am Ende des Kapitels 6 im Detail
diskutiert. Der zweite Aspekt bestand in der Frage, wie plausibel der Ähnlichkeitsindex
ist. Wir haben nach der Erklärung der stochastischen Funktionsweise des Index, die
106
7.2 Ein paar philosophische Gedanken
MLNs zueigen ist, an zwei Beispielen mit realen Daten gezeigt, dass mit der PPAO
Analyse plausible, korrekte und interessante Ergebnisse erzielt werden.
7.2 Ein paar philosophische Gedanken
Im Laufe der Experimente mit einer großen Anzahl von Kategorien (500 und mehr) haben wir beobachtet, dass der Ähnlichkeitsindex zwischen Benutzern sehr klein und damit schwach unterscheidbar wurde. Die Einzelwahrscheinlichkeiten in der Verteilung
der Benutzer fielen teilweise auf Bereiche zwischen 0.1%-0.01%. Die Tatsache, dass
der Index dabei sehr klein wird liegt in der stochastischen Betrachtungsweise – bei einer
starken Streuung der Verteilung sind keine Schwerpunkte mehr identifizierbar. Damit
wird auch nicht mehr erkennbar, was der Benutzer „als Nächstes“ tun wird. Hinzu
kommt, dass unsere Stichproben aus IRCLOVE Daten oftmals Nutzerverhalten zeigten,
das absolut keine Interessensschwerpunkte aufwies. Dies ist teilweise auf die Gestaltung
der IRCLOVE Community zurückzuführen, die einfaches „Browsen“ durch die Medien
ermöglicht. Ein solches Verhalten ist aber oftmals typisch für andere InternetApplikationen – Personen surfen teilweise völlig sporadisch, ohne dass hinter ihrem
Verhalten ein ausgeprägtes Interesse besteht. In vielen Fällen wird ein Mensch nicht
durch seine Eigenart oder Charakter sondern eher durch Situationen zur Auslösung bestimmter Aktionen getrieben, beispielsweise sucht man in Google nach „Auto“ nicht
unbedingt weil man sich für Autos interessiert, sondern weil man sich gerade jetzt ein
Auto kaufen möchte. Im Licht dieser schwerwiegenden Erkenntnis, mit der wir hautnah
in dieser Arbeit konfrontiert wurden, stellt sich die Frage, inwieweit man in solch großen und unüberschaubaren Domänen wie dem Internet, überhaupt in der Lage ist, mit
maschinellen Methoden das Verhalten von Personen zu analysieren, zu „verstehen“ und
vorherzusagen. Insbesondere gilt das für das Semantic Web, bei dem Billionen von
Webseiten mit semantischer Information verknüpft werden sollen. Maschinelle Erkennung von Absichten, Interessensschwerpunkten oder das Treffen von Vorhersagen zum
Verhalten von Menschen aufgrund von Daten hat zur Zeit nur dann eine Aussicht auf
Erfolg, wenn sie auf einer kontrollierten und eingeschränkten Domäne (und in der Personen bestimmte Verhaltensmuster herausbilden müssen) angewendet wird.
Gleichzeitig entsteht dabei die ethische Grundsatzfrage, inwieweit sich der „gläserne
Benutzer“ mit dem Recht auf Privatsphäre vereinbaren lässt. Es ist umso wichtiger, diese Problematik nicht nur aus rein technischer Sicht anzugehen, wie es in den meisten
Forschungsarbeiten bis jetzt geschehen ist. Vielmehr ist hier die Zusammenarbeit mehrerer Disziplinen, wie Informatik, Kognitiver Wissenschaft, psychologischer Verhal-
107
tensforschung und ethischer Philosophie notwendig, um gesellschaftlich und wirtschaftlich vertretbare Fortschritte zu erzielen. Erste Bemühungen diese Zusammenarbeit zu
ermöglichen zeigen sich in Form einer sehr neuen transdisziplinären wissenschaftlichen
Richtung Webwissenschaft (Web Science)1, deren Ursprung auf die von Tim BernersLee ins Leben gerufene Web Science Trust Initiative2 zurückzuführen ist.
7.3 Ausblick
In dieser Arbeit wurde eine praxistaugliche ontologiebasierte Lösung für die Analyse
von Profilen entwickelt und am Problem der Ähnlichkeitsermittlung an realen Daten
demonstriert. Dabei stießen wir insbesondere im Bezug auf die Anzahl der analysierten
Profile auf technische Grenzen – und konnten auf unserem Testserver nicht mehr als
500 Profile verarbeiten. Dies hat in erster Linie mit der exorbitanten Problemgröße zu
tun, aber auch mit fehlenden Optimierungen in den existierenden MLN SoftwareSuiten. Um diese Grenzen zu bewältigen gibt es aus unserer Sicht zwei Ansätze: der
erste, bereits in Unterkapitel 6.7, erwähnte Ansatz besteht darin, nur bestimmte, fein
selektierte Benutzergruppen zu untersuchen. So könnten inaktive Profile ausgeschlossen
und eine Vorauswahl von potenziell ähnlichen Profilen getroffen werden. Neben diesem
anwendungsspezifischen Ansatz besteht aus unserer Sicht der dringende Bedarf die Skalierbarkeit von MLNs durch Parallelisierung der Berechnung zu verbessern. So fiel
während der Experimente auf, dass PyMLN immer nur eine CPU/Core verwendete.
Durch die Verteilung der Berechnung könnte man mit entsprechender Infrastruktur
leicht in der Praxis übliche Benutzervolumen von zehn- oder hunderttausenden von
Benutzern verarbeiten. Auch die Verwendung so genannter Top-K Methoden, die
„schlechte“ Ergebnisse bereits innerhalb der Berechnung verwerfen und nicht weiter
verfolgen, könnte einen viel versprechenden Ansatz insbesondere mit Hinblick auf die
Ähnlichkeitsanalyse oder andere Ranking-verwandte Aufgaben darstellen. Durch die
Einführung einer unteren Index-Schranke würde auch die oben erwähnte anwendungsspezifische Vorauswahl bereits im Algorithmus vorgenommen werden und die Berechnung dadurch erheblich beschleunigt. Forschungsergebnisse aus dieser Richtung wurden bereits vorgestellt, unter anderem in [Nie10] und [FG09].
1
2
108
BERNERS-LEE, T. et al.: Creating a Science of the Web. Science Magazine Vol. 313. (2006) 769-771
http://webscience.org/home.html (geprüft am 6. Mai 2011)
7.3 Ausblick
Schon als die Idee dieser Arbeit entstand, war es absolut klar, dass ein probabilistisches
Modell entstehen muss. Denn unsere Welt basiert nicht nur auf Logik sondern auch auf
Zufällen, auf Statistik und Vermutungen. Wir werden dem Computer nur dann ein besseres „Verständnis“ dieser Welt vermitteln können, wenn wir diese, uns Menschen angeborene Intuition des Zufalls, für die Maschine zu formulieren versuchen. Diese Diplomarbeit zeigt nur einen sehr kleinen Teil dessen, was heute mit Entwicklungen wie
MLNs machbar ist, die Logik und statistische Methoden in der Wissensrepräsentation
vereinen. Sie wurde jedoch aus der Überzeugung geschrieben, dass dieser Weg der einzig gangbare ist, um mit heutiger Technologie einen Schritt näher an dieses bessere
Verständnis des menschlichen Verhaltens und Denkens zu kommen.
109
LITERATURVERZEICHNIS
[ALCHEM]
Alchemy: Open Source AI. (2010) <http://alchemy.cs.washington.edu>
(zuletzt geprüft am 6. Mai 2011)
[AB09]
ARORA, S., BARAK, B.: Computational Complexity: A Modern Approach. Cambridge University Press. (2009)
[BHL01]
BERNERS-LEE, T., HENDLER, J., LASSILA, O.: The Semantic Web: a new
form of Web content that is meaningful to computers will unleash a revolution of new possibilities. Scientific American Magazine Vol. 284.
(2001) 34-43
[BN03]
BAADER, F., NUTT, W.: Basic Description Logics. The Description Logic Handbook – Theory, implementation, and applications. Cambridge
University Press. (2003) 47-101
[BS85]
BRACHMAN, R., SCHMOLZE, J.: An Overview of the KL-ONE Knowledge
Representation System. Cognitive Science, Vol. 9. (1985) 171-216
[DR07]
DOMINGOS, P., RICHARDSON, M.: Markov Logic: A Unifying Framework
for Statistical Relational Learning. In Introduction to Statistical Relational Learning. USA, Cambridge, MIT Press. (2007) 339-373
[Fen04]
FENSEL, Dieter: Ontologies: A Silver Bullet for Knowledge Management
and Electronic Commerce. Berlin, Springer Verlag. (2004)
[FG09]
FROMER, M., GLOBERSON, A.: An lp view of the m-best map problem. In
Advances in Neural Information Processing Systems Vol 22. (2009)
567-575
[GFC04]
GÓMEZ-PÉREZ, A., FERNÁNDEZ-LÓPEZ, M., GORCHO, O.: Ontological
Engineering. London, Springer Verlag. (2004)
[GN87]
GENESERETH, M. R., NILSSON, N. J.: Logical Foundations of Artificial
Intelligence. Los Altos, Morgan Kaufmann. (1987)
111
[GOS09]
GUARINO, N., OBERLE, D., STAAB, S.: What Is an Ontology? Handbook
on Ontologies, Berlin, Springer Verlag. (2009)
[Gru93]
GRUBER, T. R.: A Translation Approach to Portable Ontologies. Knowledge Acquisition Vol. 5. (1993) 199-220
112
[GT07]
GETOOR, L., TASKAR, B.: Introduction to Statistical Relational Learning. USA, Cambridge, MIT Press. (2007)
[Gua98]
GUARINO, Nicola: Formal Ontology in Information Systems. Proceedings of FOIS98, Italy, Trento. (1998) 3-15
[HKR+08]
HITZLER, P. et al.: Semantic Web. Berlin, Springer Verlag. (2008)
[Hor99]
HORROCKS, I. et al.: Practical Reasoning for Expressive Description
Logics. Logic for Programming and Automated Reasoning Vol. 1705,
Berlin, Springer Verlag. (1999) 161-180
[HP03]
HORROCKS, I., PATEL-SCHNEIDER, P. F.: Reducing OWL Entailment to
Description Logic Satisfiability. The Semantic Web, Proceedings of
ISWC 2003, Berlin, Springer Verlag. (2003) 17-29
[JB10]
JAIN, D., BEETZ, M.: Soft Evidential Update via Markov Chain Monte
Carlo Inference. In proceedings of 33rd KI 2010, Karlsruhe, Germany.
(2010) 280-290
[KFG+07]
KOLLER, D. et al.: Graphical Models in a Nutshell. In Introduction to
Statistical Relational Learning. USA, Cambridge, MIT Press. (2007) 1356
[Kli08]
KLINOV, Pavel: Pronto: a Non-Monotonic Probabilistic Description
Logic Reasoner. The Semantic Web: Research and Applications, Proceedings of ESWC 2008, Berlin, Springer Verlag. (2008) 822-826
[KLP97]
KOLLER, D., LEVY, A., PFEFFER, A.: P-CLASSIC: A tractable probabilistic description logic. In proceedings of AAAI. (1997) 390-397
[KP08]
KLINOV, P., PARSIA, B.: Optimization and Evaluation of Reasoning in
Probabilistic Description Logic: Towards a Systematic Approach. The
Semantic Web, Proceedings of ISWC 2008, Berlin, Springer Verlag.
(2008) 213-228
[Luk07]
LUKASIEWICZ, Thomas: Probabilistic Description Logics for the Semantic Web. INFSYS Research Report 1843-06-05, Wien, Universität Wien.
(2007)
[Min74]
MINSKY, Marvin: A Framework for Representing Knowledge. The Psychology of Computer Vision, New York, McGraw-Hill. (1974) 211-277
[Nie10]
NIEPERT, Mathias: A Delayed Column Generation Strategy for Exact kBounded MAP Inference in Markov Logic Networks. In proceedings of
26th UAI, USA, Catalina Island, AUAI Press. (2010)
[Oli09]
DE
OLIVEIRA, PEDRO: Probabilistic Reasoning in the Semantic Web us-
ing Markov Logic. MSc Thesis. Portugal, University of Coimbra. (2009)
[OLN95]
OWSNICKI-KLEWE, B., VON LUCK, K., NEBEL, B.: Wissensrepräsentation
und Logik – Eine Einführung. Einführung in die Künstliche Intelligenz,
Addison-Wesley. (1995) 15-58
[OWLGD]
OWL Web Ontology Guide Deutsche Übersetzung. W3C. (2004)
<http://semaweb.org/dokumente/w3/TR/2004/REC-owl-guide20040210-DE.html> (zuletzt geprüft am 6. Mai 2011)
[PCOG]
ProbCog: Probabilistic Cognition for Cognitive Technical Systems.
(2010)
<http://ias.cs.tum.edu/research-areas/knowledge-processing/probcog>
(zuletzt geprüft am 6. Mai 2011)
[PS08]
PREDOIU, L., STUCKENSCHMIDT, H.: Probabilistic Models for the Semantic Web – A Survey. Technical Report, Mannheim, Universität Mannheim. (2008)
[RD04]
RICHARDSON, M., DOMINGOS, P.: Markov Logic Networks. Technical
Report, University of Washington, USA. (2004)
113
[Rei10]
REICHENBERGER, Klaus: Kompendium semantische Netze. Berlin, Springer Verlag. (2010)
[Rie08]
RIEDEL, Sebastian: Improving the Accuracy and Efficiency of MAP Inference for Markov Logic. In proceedings of 24th UAI, Helsinki,
Finnland. (2008) 468-475
[RN10]
RUSSELL, S. J., NORVIG, P.: Artificial Intelligence: a modern approach.
Boston, Pearson Verlag. (2010)
[SBF98]
STUDER, R., BENJAMINS, R., FENSEL, D.: Knowledge engineering: Principles and methods. Data & Knowledge Engineering Vol. 25. (1998)
161-198
[SD10]
SUMNER,
M.,
DOMINGOS,
P.:
The
Alchemy
Tutorial.
(2010)
<http://alchemy.cs.washington.edu/tutorial/tutorial.pdf> (zuletzt geprüft
am 6. Mai 2011)
114
[Sow00]
SOWA, John F.: Knowledge Representation – Logical, Philosophical and
Computational Foundations. Pacific Grove, Brooks/Cole. (2000)
[SS91]
SCHMIDT-SCHAUß, M., SMOLKA, G.: Attributive concept descriptions
with complements. Artificial Intelligence Vol. 48. (1991) 1-26
[TAW+07]
TASKAR, B. et al.: Relational Markov Networks. In Introduction to Statistical Relational Learning. USA, Cambridge, MIT Press. (2007) 175199
[TBEAST]
Markov thebeast: Markov Logic / Statistical Relational Learning Software auf Google Code. (2010) <http://code.google.com/p/thebeast> (zuletzt geprüft am 6. Mai 2011)
[Tob01]
TOBIES, Stephan: Complexity Results and Practical Algorithms for Logics in Knowledge Representation. PhD Thesis, Aachen, RTWH Aachen.
(2001)
[UG04]
USCHOLD, M., GRUNINGER, M.: Ontologies and Semantics for Seamless
Connectivity. SIGMOD Record Vol. 33. (2004)
ANHANG
I. Konfiguration des Testservers
Für die praktischen Berechnungen innerhalb dieser Arbeit wurde die folgende Maschine
benutzt:
CPU: 2x AMD Opteron 244, 1,8 GHz
RAM: 4 GB
Festplatten: Seagate 500 GB, Durchsatz: 70 MB/sek
Primäres Betriebsystem: Microsoft Windows XP
Virtuelle Umgebung: VMWare
Sekundäres Betriebsystem: Linux, OpenSuSE 11.3
II. Level 1-Kategorien in IRCLOVE Persönlichkeiten
ID
1
2
3
5
6
7
8
9
11
13
Kategorie
Foto
Zeichnung
Gedicht
Umfrage
Freier
Text
Gedanke
Zitat
Geschichte
iHTML
Video
III. Die 30 häufigsten Hobbys der IRCLOVE Benutzer
Die Tabelle enthält die 30 häufigsten Hobbys aus realen Daten der Community sowie
die Anzahl der Benutzer, die das jeweilige Hobby angegeben haben. Bei der Ermittlung
wurden gleich bedeutende Ausdrücke automatisch zusammengefasst (z.B. „Computer“
und „PC“). Die 50 häufigsten Begriffe wurden dann verwendet, um die Benutzerangaben danach zu durchsuchen und zu normalisieren, d.h. wurde ein Begriff wie „Musik“
115
ANHANG
in einer Angabe „Musik hören“ gefunden, dann wurde diese Angabe zu „Musik“ geändert. Dieses Pre-Processing war notwendig, da in IRCLOVE die Hobby-Angabe ein
Freitext-Feld ist und damit eine eindeutige Unterscheidung schwierig ist. Trotz der Verbesserung der Datenqualität lag die Anzahl der eindeutigen Hobby-Ausdrücke bei über
9000, wobei mehr als 7000 nur ein einziges Mal vorkamen.
Hobby
Anzahl
Hobby
Anzahl
Hobby
Anzahl
1. Musik
4909
11. Tanzen
1209
21. Fitness
631
2. Sport
3. Lesen
4272
3224
12. Kochen
13. Natur
1137
1022
22. Wandern
23. Fotografie
558
530
4. Kino
5. Freunde
3176
3105
14. Ausgehen
15. Fußball
967
954
24. Kunst
25. Chatten
504
470
6. Computer
7. Reisen
2133
1978
16. Motorrad
17. Essen
862
789
26. Literatur
27. Tiere
436
415
8. Party
1738
18. Internet
748
28. Kultur
388
9. Schwimmen
10. Radfahren
1390
1273
19. Joggen
20. Auto
733
638
29. Theater
30. Tennis
367
366
IV. Wahrscheinlichkeitsverteilungen für Experiment in Abschnitt 6.6.2
In den folgenden Diagrammen ist die X-Achse mit echten Kategorien-IDs aus der
IRCLOVE Datenbank beschriftet.
116
IV. WAHRSCHEINLICHKEITSVERTEILUNGEN FÜR EXPERIMENT IN ABSCHNITT 6.6.2
Profil A
read
comment
80,00%
80,00%
60,00%
60,00%
40,00%
40,00%
20,00%
20,00%
0,00%
0,00%
1
2
3
5
6
7
8
9
11 13
1
2
3
award
5
6
7
8
9
11 13
7
8
9
11 13
7
8
9
11 13
7
8
9
11 13
create
80,00%
100,00%
80,00%
60,00%
60,00%
40,00%
40,00%
20,00%
20,00%
0,00%
0,00%
1
2
3
5
6
7
8
9
11 13
1
2
3
5
6
Profil B
read
comment
80,00%
100,00%
80,00%
60,00%
60,00%
40,00%
40,00%
20,00%
20,00%
0,00%
0,00%
1
2
3
5
6
7
8
9
11 13
1
2
3
award
100,00%
80,00%
80,00%
60,00%
60,00%
40,00%
40,00%
20,00%
20,00%
0,00%
0,00%
2
3
5
6
6
create
100,00%
1
5
7
8
9
11 13
1
2
3
5
6
117
ANHANG
Profil C
read
comment
60,00%
80,00%
60,00%
40,00%
40,00%
20,00%
20,00%
0,00%
0,00%
1
2
3
5
6
7
8
9
11 13
1
2
3
5
award
6
7
8
9
11 13
8
9
11 13
7
8
9
11 13
7
8
9
11 13
create
100,00%
60,00%
80,00%
40,00%
60,00%
40,00%
20,00%
20,00%
0,00%
0,00%
1
2
3
5
6
7
8
9
11 13
1
2
3
5
6
7
Profil D
read
comment
100,00%
100,00%
80,00%
80,00%
60,00%
60,00%
40,00%
40,00%
20,00%
20,00%
0,00%
0,00%
1
2
3
5
6
7
8
9
11 13
1
2
3
award
100,00%
80,00%
80,00%
60,00%
60,00%
40,00%
40,00%
20,00%
20,00%
0,00%
0,00%
118
2
3
5
6
6
create
100,00%
1
5
7
8
9
11 13
1
2
3
5
6

ontologiebasierte probabilistische profilanalyse mit markov logic

Transcrição

Documentos relacionados

Referenz: Generic Java Ontology API Thema: Eclipse Plug

Full Text

Strokes Arabisch Serie 20

Semantisches Web, Ontologie und künstliche Intelligenz

BIOLOGIE t - Lebendiger Unterricht

WIN-911®

¨Ubungsblatt 6 Aufgabe 1: Codebreaker (6 Punkte, B)

Entblösst unter Freunden

AGB herunterladen als PDF-Datei

Phishing und Pharming: Diebstahl im Netz