ontologiebasierte probabilistische profilanalyse mit markov logic
Transcrição
ontologiebasierte probabilistische profilanalyse mit markov logic
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 KAPITEL 1. EINFÜHRUNG 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 1.2 Zielsetzung der Arbeit 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 KAPITEL 1. EINFÜHRUNG 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 1.2 Zielsetzung der Arbeit 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 2.1 Ontologien und ihre Einsatzmöglichkeiten 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 KAPITEL 2. GRUNDLAGEN UND STAND DER FORSCHUNG 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) 2.1 Ontologien und ihre Einsatzmöglichkeiten 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 KAPITEL 2. GRUNDLAGEN UND STAND DER FORSCHUNG 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 Ontologien und ihre Einsatzmöglichkeiten 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 KAPITEL 2. GRUNDLAGEN UND STAND DER FORSCHUNG 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 2.1 Ontologien und ihre Einsatzmöglichkeiten ten Sprache wie z.B. Restriktionen über ein so genanntes XML-Schema angegeben werden. Wir werden auf diesen Aspekt aber nicht weiter eingehen. 15 KAPITEL 2. GRUNDLAGEN UND STAND DER FORSCHUNG 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 2.1 Ontologien und ihre Einsatzmöglichkeiten <?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 KAPITEL 2. GRUNDLAGEN UND STAND DER FORSCHUNG 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 2.1 Ontologien und ihre Einsatzmöglichkeiten 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 KAPITEL 2. GRUNDLAGEN UND STAND DER FORSCHUNG 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 2.1 Ontologien und ihre Einsatzmöglichkeiten 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 KAPITEL 2. GRUNDLAGEN UND STAND DER FORSCHUNG 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 KAPITEL 2. GRUNDLAGEN UND STAND DER FORSCHUNG 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 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 KAPITEL 2. GRUNDLAGEN UND STAND DER FORSCHUNG 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 2.3 Die Community IRCLOVE 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. KAPITEL 2. GRUNDLAGEN UND STAND DER FORSCHUNG 28 2.3 Die Community IRCLOVE 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 KAPITEL 2. GRUNDLAGEN UND STAND DER FORSCHUNG 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 Die Community IRCLOVE 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 KAPITEL 2. GRUNDLAGEN UND STAND DER FORSCHUNG 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 2.3 Die Community IRCLOVE 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 KAPITEL 2. GRUNDLAGEN UND STAND DER FORSCHUNG 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 Die Community IRCLOVE 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) Medien- (Kategorie, Autor) Medien- (Kategorie, Autor) Medien- (Kategorie, Autor) Kategorie Ordner-Autor Bibliothek-Autor Medien- (Kategorie, 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 KAPITEL 2. GRUNDLAGEN UND STAND DER FORSCHUNG 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 nicht klassifizierter Freitext nicht klassifizierter Freitext nicht klassifizierter Freitext nicht klassifizierter Freitext 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 3.2 Wahrscheinlichkeiten in Beschreibungslogiken ∃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 KAPITEL 3. PROBABILISTISCHE ONTOLOGIEN 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 3.2 Wahrscheinlichkeiten in Beschreibungslogiken 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 KAPITEL 3. PROBABILISTISCHE ONTOLOGIEN 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) 3.2 Wahrscheinlichkeiten in Beschreibungslogiken 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 KAPITEL 3. PROBABILISTISCHE ONTOLOGIEN 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 Wahrscheinlichkeiten in Beschreibungslogiken 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 KAPITEL 3. PROBABILISTISCHE ONTOLOGIEN 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 3.3 Statistisches relationales Lernen 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 KAPITEL 3. PROBABILISTISCHE ONTOLOGIEN 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 3.3 Statistisches relationales Lernen 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 KAPITEL 3. PROBABILISTISCHE ONTOLOGIEN 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 KAPITEL 3. PROBABILISTISCHE ONTOLOGIEN 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 KAPITEL 3. PROBABILISTISCHE ONTOLOGIEN 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 KAPITEL 4. KONZEPT DER PPAO ONTOLOGIE 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 KAPITEL 4. KONZEPT DER PPAO ONTOLOGIE 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 KAPITEL 5. IMPLEMENTIERUNG UND INFERENZ 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 KAPITEL 5. IMPLEMENTIERUNG UND INFERENZ 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 5.3 Konstruktion der PPAO Ontologie 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 KAPITEL 5. IMPLEMENTIERUNG UND INFERENZ 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 5.3 Konstruktion der PPAO Ontologie …. 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 KAPITEL 5. IMPLEMENTIERUNG UND INFERENZ 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 5.3 Konstruktion der PPAO Ontologie 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 KAPITEL 5. IMPLEMENTIERUNG UND INFERENZ 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 5.3 Konstruktion der PPAO Ontologie 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 KAPITEL 5. IMPLEMENTIERUNG UND INFERENZ 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 5.3 Konstruktion der PPAO Ontologie 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) logx(0.8) reads411(2,quelle1) logx(0.5) reads411(1,quelle2) logx(0.5) reads411(2,quelle2) 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 KAPITEL 5. IMPLEMENTIERUNG UND INFERENZ 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 KAPITEL 5. IMPLEMENTIERUNG UND INFERENZ 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 KAPITEL 6. EXPERIMENTELLE UNTERSUCHUNG 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 Skalierbarkeit bezüglich Präzision 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 KAPITEL 6. EXPERIMENTELLE UNTERSUCHUNG 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 6.4 Skalierbarkeit bezüglich Präzision 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 KAPITEL 6. EXPERIMENTELLE UNTERSUCHUNG 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. 6.4 Skalierbarkeit bezüglich Präzision ß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 KAPITEL 6. EXPERIMENTELLE UNTERSUCHUNG 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 KAPITEL 6. EXPERIMENTELLE UNTERSUCHUNG 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. 6.6 Aussagekraft des Ähnlichkeitsindex 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 KAPITEL 6. EXPERIMENTELLE UNTERSUCHUNG 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 6.6 Aussagekraft des Ähnlichkeitsindex 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 KAPITEL 6. EXPERIMENTELLE UNTERSUCHUNG 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 6.6 Aussagekraft des Ähnlichkeitsindex 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 KAPITEL 6. EXPERIMENTELLE UNTERSUCHUNG 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 6.6 Aussagekraft des Ähnlichkeitsindex 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 KAPITEL 6. EXPERIMENTELLE UNTERSUCHUNG 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 KAPITEL 7. ZUSAMMENFASSUNG 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 KAPITEL 7. ZUSAMMENFASSUNG 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 LITERATURVERZEICHNIS [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 LITERATURVERZEICHNIS [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 LITERATURVERZEICHNIS [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