U N T E R S T Ü T Z U N G D E S R E S S O U R C E N - B A S I E RT E N L E R N E N S I N O N L I N E C O M M U N I T I E S – A U T O M AT I S C H E E R S T E L L U N G V O N G R O SS TA X O N O M I E N I N V E R S C H I E D E N E N S P R A C H E N Vom Fachbereich Elektrotechnik und Informationstechnik der Technischen Universität Darmstadt zur Erlangung des akademischen Grades eines Doktor-Ingenieurs (Dr.-Ing.) genehmigte Dissertation von dipl.-inform. renato domínguez garcía Geboren am 17. September 1982 in San José, Costa Rica Referent: Prof. Dr.-Ing. Ralf Steinmetz Korreferent: Prof. Dr.-Ing Ulrik Schroeder Tag der Einreichung: 07. Dezember 2012 Tag der Disputation: 04. Februar 2013 Hochschulkennziffer D17 Darmstadt 2013 K U R Z FA S S U N G Die sich stetig verändernden beruflichen Rahmenbedingungen und die immer kürzer werdende Gültigkeit einmal erworbenen Wissens verlangen flexible Formen des Wissens- und Kompetenzerwerbs. Das in Bildungseinrichtungen ange- eignete Wissen reicht nicht mehr ein Leben lang. Vielmehr besteht insbesondere im Arbeitsprozess zunehmend die Notwendigkeit, sich abhängig von der konkreten Pro- blemstellung situativ Wissen anzueignen. Man spricht von selbstgesteuertem Lernen, da Lernende für ihre Lern- bzw. Wissenserwerbsprozesse selbst verantwortlich sind. Gleichzeitig hat sich das World Wide Web zu einer der wichtigsten Quellen beim Wissenserwerb entwickelt. Das selbstgesteuerte Lernen mit Hilfe von Ressourcen aus dem Internet wird auch Ressourcen-basiertes Lernen bezeichnet. Eine der größten Herausforderung im Ressourcen-basierten Lernen ist es, relevante Web-Ressourcen im Web zu finden. Suchmaschinen werden sehr häufig verwen- det, liefern aber praktisch keine Hilfestellung bei der Auswahl und Beurteilung gefundener Ressourcen. Empfehlungssysteme (engl. Recommender Systems) kön- nen grundsätzlich hilfreich sein, um für die jeweilige Situation und den jeweiligen Lernenden relevanten Ressourcen zu finden. Lernende können davon profitieren, dass sie auf Wissensressourcen hingewiesen werden, die andere Lernende, die einen ähnlichen Wissensbedarf besitzen, verwendet haben. In größeren Gruppen oder in einer Community sind für die eigene Lernaufgabe relevante Ressourcen mit hoher Wahrscheinlichkeit bereits von anderen Personen gefunden worden. Ziel dieser Arbeit war es, das Ressourcen-basierte Lernen innerhalb einer Com- munity von Lernenden zu unterstützen, indem Lernende situationsbezogen auf Wissensressourcen hingewiesen werden, die andere Community-Mitglieder bereits verwendet haben. Zur Erreichung dieses Ziels wurde das Anwendungsszenario am Beispiel der CROKODIL-Plattform, eine Plattform zur Unterstützung des Ressourcen-basierten Lernens, untersucht. Die Untersuchung ergab, dass Benutzer oftmals nicht auf inter- essante Ressourcen hingewiesen werden können, wenn sie unterschiedliche Termino- logien bei der Verschlagwortung von beim Lernen genutzten Ressourcen verwenden. Basierend auf dieser Feststellung wurde ein Konzept entwickelt, welches die Lücken in den von den Benutzern verwendeten Terminologien mittels der Verwendung einer Taxonomie schließt. Die Analyse ergab weiterhin, dass das Anwendungsszenario dadurch gekennzeichnet ist, dass die Benutzer aktuelle Begriffe in mehreren Spra- chen als Schlagworte verwenden. Taxonomien, die diese Schlagworte in Beziehung zueinander setzen wollen, müssen daher dadurch charakterisiert sein, dass sie sehr aktuell sind und im mehreren Sprachen vorliegen. Diese Anforderungen können von existierenden manuell erzeugten Taxonomien nicht erfüllt werden. Daher wurden in der Arbeit mit TaxWikiHeur.KOM und TaxWikiML.KOM zwei Verfahren konzipiert und implementiert, die weitestgehend sprachunabhängig aus der Online Enzyklopädie Wikipedia Taxonomien generieren, indem sie Kategorienpaare aus der Wikipedia in Hyponymie- und Nicht-Hyponymiebeziehungen klassifizieren. Diese Verfahren zeichnen sich dadurch aus, dass sie keine externen, manuell erzeug- ten Wissensbasen verwenden. Damit besteht keine Notwendigkeit einer manuellen Pflege von Taxonomien für neue Wissensbereiche. Das Verfahren TaxWikiML.KOM erweitert das Verfahren TaxWikiHeur.KOM und behebt einige der bei der Evaluation von TaxWikiHeur.KOM erkannten Mängel. Die Evaluation der Verfahren hat insge- samt gezeigt, dass trotz des Verzichtes auf eine externe Wissensbasis die Güte der Taxonomien sehr gut ist. Die Verwendung der Verfahren erfolgte in fünf Sprachen, so dass der Nachweis der sprachunabhängigen Nutzbarkeit ebenfalls erfolgte. Das Verfahren TaxWikiML.KOM wurde in der Arbeit weiterhin verwendet, um innerhalb der CROKODIL-Lernumgebung automatisch Beziehungen zwischen von den Benutzern verwendeten Schlagworten zur Beschreibung der im Lernprozess genutzten Ressourcen zu ergänzen. Es konnte zum einen anhand dreier Korpora aus dem Anwendungsfeld der Ressourcen-basierten Lernens nachgewiesen werden, dass die Dichte des semantischen Netzes, die zur Speicherung der Daten (Ressourcen, Tags und Benutzer) benutzt wird, durch das implementierte Konzept größer wird, womit Empfehlungssysteme umfangreichere Informationen zur Generierung von Empfehlungen zur Verfügung stehen, die auch solche Ressourcen anderer Lernender empfehlen können, die mit einer unterschiedlichen Terminologie beschrieben sind. Der positive Einfluss von mittels TaxWikiML.KOM ergänzten Hyponymiebeziehun- gen zwischen Schlagworten auf die Güte von Empfehlungssystemen wurde in einer weiteren Evaluation anhand des State-of-the-Art Verfahrens FolkRank zusätzlich nachgewiesen. Schließlich wurde das FReSET-Tool zur Evaluation von Empfehlungssystemen ent- wickelt. Das Tool wurde bereits in verschiedenen Arbeiten zur Evaluation verwendet, da es einen standardisierten Vergleich von Empfehlungssystemen ermöglicht. A B S T R A C T Due to constantly changing professional environments and the decrease in the half-life of acquired knowledge, flexible forms of knowledge and skills acquisi- tion are required. Nowadays, the knowledge acquired in educational institutions no longer last a lifetime. Rather, there is an increasing need (especially in work processes) for the personal acquisition of knowledge depending on specific tasks. This is called self-directed learning, as learners are responsible for their learning processes. At the same time, the World Wide Web has become one of the most important sources for knowledge acquisition. Self-directed learning using resources from the Internet is also called resource-based learning. One of the biggest challenges in resource-based learning is finding relevant web resources on the Web. Search engines are very often used for this purpose, but they do not provide assistance in the selection of found resources. Recommender systems can be helpful to find relevant resources. Learners can benefit from resources that other learners with similar knowledge requirements have already found. In larger groups or in a community, there is a high probability that relevant resources have already been found by other people. The goal of this thesis is to support resource-based learning within a community of learners by recommending knowledge resources that other community members have already found. To achieve this objective, the application scenario and an example implementation, CROKODIL, were investigated. The investigation revealed that the recommendation of interesting resources is often impossible, if the users use different terminologies for the tagging of resources. Based on this observation, a concept was developed that fills the gaps in the terminology used by the users through the use of a taxonomy. The analysis also reveals that the application scenario is characterized by current terms in multiple languages which are used as tags. A taxonomy used for the purpose of finding relationships between tags must, therefore, be characterized by the fact that it is up-to-date and available in multiple languages. These characteristics make manually created taxonomies unsuitable. Therefore, two approaches, TaxWikiHeur.KOM and TaxWikiML.KOM, were desi- gned and implemented in order to generate large-scale taxonomies from the online encyclopedia Wikipedia in multiple languages. This is done by classifying pairs of categories from the Wikipedia in hyponymy and non-hyponymy relationships. These methods are characterized by the fact that they do not use external, manually created knowledge bases. Thus there is no need for the manual maintenance of taxonomies for new knowledge fields. TaxWikiML.KOM extends TaxWikiHeur.KOM and fixes some of the recognized shortcomings in the evaluation of TaxWikiHeur.KOM. The evaluation of the whole process has shown that even if no external knowledge base was used, the quality of the taxonomies was still very good. The approaches were evaluated in five different languages, in order to show the language-independency of the approaches. TaxWikiML.KOM was also used within CROKODIL to complement automatically generated relations between tags used by the users to describe the resources in their learning processes. Based on three corpora obtained from the application scenario, the evaluation could show that the density of the network grew using the implemen- ted concept. Therefore, recommender systems have more information available to generate recommendations and this can be used for recommendations to learners using different terminologies. Additionally, the positive effect on the quality of recom- mender systems due to hyponymy relations between tags found by TaxWikiML.KOM was demonstrated in a further evaluation based on a state-of-the-Art algorithm. Finally, the FReSET tool for the evaluation of recommender systems was developed. FReSET can be used for the evaluation of recommender systems as it allows a standardized and thus comparable evaluation of recommender systems. I N H A LT S V E R Z E I C H N I S 1 einführung 1 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Ziel, Ansatz und Beiträge der Arbeit . . . . . . . . . . . . . . . . . . . . 2 1.3 Gliederung der Arbeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 grundlagen 5 2.1 Ressourcen-basiertes Lernen und Lernressourcen . . . . . . . . . . . . 5 2.2 Information Retrieval und Maschinelles Lernen . . . . . . . . . . . . . 8 2.2.1 Information Retrieval . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.2 Maschinelles Lernen . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2.3 Evaluationsmaße . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2.4 Evaluationsverfahren . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3 Wissensrepräsentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.3.1 Begriffe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.3.2 Konzepte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.3.3 Relationen zwischen Konzepten . . . . . . . . . . . . . . . . . . 14 2.3.4 Taxonomien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.3.5 Thesauri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.3.6 Ontologien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.3.7 Semantische Netze . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.3.8 Folksonomien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.4 Wikipedia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.4.1 Das Projekt Wikipedia . . . . . . . . . . . . . . . . . . . . . . . . 20 2.4.2 Struktur der Wikipedia . . . . . . . . . . . . . . . . . . . . . . . 20 3 verwandte arbeiten 27 3.1 Verwandte Arbeiten im Bereich Empfehlungssysteme . . . . . . . . . . 27 3.1.1 Grundlagen zu Empfehlungssystemen . . . . . . . . . . . . . . 27 3.1.2 Empfehlungssysteme im E-Learning . . . . . . . . . . . . . . . . 30 3.2 Verwandte Arbeiten im Bereich Wissensextraktion . . . . . . . . . . . . 33 3.2.1 Manuell erstellte Wissensbasen . . . . . . . . . . . . . . . . . . . 33 3.2.2 Automatische Extraktion von Wissensbasen . . . . . . . . . . . 34 3.2.3 Automatische Extraktion von Wissensbasen aus Wikipedia . . 37 3.2.4 Diskussion und Einordnung dieser Arbeit . . . . . . . . . . . . 40 4 unterstützung des kollaborativen ressourcen-basierten ler- nens in online communities 43 4.1 Analyse des Anwendungsszenarios und die CROKODIL-Plattform . . 43 4.1.1 Ziele der Entwicklung der CROKDODIL-Lernumgebung . . . 43 4.1.2 Funktionalitäten der CROKODIL-Plattform . . . . . . . . . . . 44 4.1.3 Das CROKODIL-Datenmodell . . . . . . . . . . . . . . . . . . . 47 4.1.4 Analyse der Eigenschaften des Ressourcen-basierten Lernens in Online Communities . . . . . . . . . . . . . . . . . . . . . . . . . 48 vii viii inhaltsverzeichnis 4.1.5 Herausforderungen bei der Nutzung von Ressourcen der Com- munity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 4.2 Konzept zur Steigerung der Zugreifbarkeit auf Ressourcen im Ressourcen- basierten Lernen in Online Communities durch die Verwendung von Taxonomien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.2.1 Empfehlung von Ressourcen auf Basis hyponymischer Bezie- hungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.2.2 Anforderungen an eine Taxonomie zur Ergänzung hyponymi- scher Beziehungen . . . . . . . . . . . . . . . . . . . . . . . . . . 53 4.3 Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 5 erkennung von hyponymien in verschiedenen sprachen 55 5.1 Erkennung von Hyponymien auf Basis von Heuristiken . . . . . . . . 55 5.1.1 Workflow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 5.1.2 Einzelne Schritte des Algorithmus im Detail . . . . . . . . . . . 56 5.1.3 Sprachunabhängigkeit des Verfahrens . . . . . . . . . . . . . . . 65 5.1.4 Evaluation des Verfahrens . . . . . . . . . . . . . . . . . . . . . . 66 5.1.5 Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . . . . . 71 5.2 Erkennung von Hyponymien auf Basis von Entscheidungsbäumen . . 71 5.2.1 Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 5.2.2 Sprachunabhängigkeit des Verfahrens . . . . . . . . . . . . . . . 79 5.2.3 Evaluation des Verfahrens . . . . . . . . . . . . . . . . . . . . . . 79 5.3 Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 6 implementierung und proof-of-concept 89 6.1 CROKODIL-Komponenten und erweiterte Architektur . . . . . . . . . 89 6.1.1 CROKODIL-Komponenten . . . . . . . . . . . . . . . . . . . . . 90 6.1.2 Die Taxonomiedatenbank . . . . . . . . . . . . . . . . . . . . . . 92 6.2 Erweiterung des Datenmodells und Realisierung von Empfehlungen . 93 6.2.1 Erweiterung des Datenmodells . . . . . . . . . . . . . . . . . . . 93 6.2.2 Generierung von Empfehlungen . . . . . . . . . . . . . . . . . . 94 6.3 CrokTaxTools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 6.3.1 Architektur von CrokTaxTools . . . . . . . . . . . . . . . . . . . 97 6.3.2 Funktionsweise . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 6.4 Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 7 evaluation der nutzung der taxonomie im anwendungsszena- rio 101 7.1 Grundlagen der Evaluation von Empfehlungssystemen . . . . . . . . . 101 7.1.1 Evaluation mit historischen Daten . . . . . . . . . . . . . . . . . 101 7.1.2 Benutzerevaluationen . . . . . . . . . . . . . . . . . . . . . . . . 102 7.1.3 Fazit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 7.2 Ziele und Evaluationsmethodik . . . . . . . . . . . . . . . . . . . . . . . 103 7.2.1 Auswahl und Erzeugung der Korpora . . . . . . . . . . . . . . . 105 7.2.2 Verwendete Algorithmen und Tools . . . . . . . . . . . . . . . . 106 7.3 Ergebnisse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 7.3.1 Evaluation bzgl. der Dichte des semantischen Netzes . . . . . . 109 7.3.2 Empfehlungen anhand eines Empfehlungssystems . . . . . . . 110 inhaltsverzeichnis ix 7.4 Fazit und Diskussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 8 zusammenfassung und ausblick 115 8.1 Zusammenfassung und Beiträge der Arbeit . . . . . . . . . . . . . . . . 115 8.2 Ausblick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 literaturverzeichnis 119 abbildungsverzeichnis 133 tabellenverzeichnis 135 abkürzungsverzeichnis 138 a anhang 139 a.1 Details zu TaxWikiHeur.KOM . . . . . . . . . . . . . . . . . . . . . . . . 139 a.1.1 Parametrisierung der Heuristiken für die deutsche Sprache . . 139 a.1.2 Ergebnisse von TaxWikiHeur.KOM in anderen Sprachen . . . . 140 a.2 Details zu TaxWikiML.KOM . . . . . . . . . . . . . . . . . . . . . . . . . 144 a.2.1 Klassifizierungsergebnisse basierend auf der englischen Wikipedia144 a.2.2 Klassifizierungsergebnisse basierend auf der deutschen Wikipedia145 a.3 Details zur Evaluation der Nutzung der Taxonomie im Anwendungs- szenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 a.3.1 Weitere Details zu den in der Evaluation verwendeten Korpora 147 a.3.2 Weitere Details zu Ausführung von FolkRank auf die verwen- deten Korpora . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 b wissenschaftliche arbeiten des autors 159 b.1 Veröffentlichungen als Erstautor . . . . . . . . . . . . . . . . . . . . . . 159 b.2 Mitautorenschaft und sonstige Veröffentlichungen . . . . . . . . . . . . 160 c curriculum vitæ 163 d betreute studentische abschlussarbeiten 165 e erklärung laut §9 der promotionsordnung 167 1 E I N F Ü H R U N G »Ein Anfang ist kein Meisterstück, doch guter Anfang halbes Glück.« — Anastasius Grün 1.1 motivation Die sich stetig verändernden beruflichen Rahmenbedingungen und die immer ge- ringer werdende Gültigkeit einmal erworbenen Wissens [39, 56, 164] verlangen flexible Formen des Wissens- und Kompetenzerwerbs [148]. Das in Bildungsein- richtungen angeeignete Wissen reicht nicht mehr ein Leben lang. Vielmehr besteht insbesondere im Arbeitsprozess zunehmend die Notwendigkeit, sich abhängig von der konkreten Aufgabenstellung situativ Wissen anzueignen. Die Lernenden sind dann für ihre Lern- bzw. Wissenserwerbsprozesse selbst verantwortlich und können entscheiden, wann sie was, wo und wie lernen möchten. Man spricht von selbstge- steuertem Lernen. Gleichzeitig hat sich das World Wide Web (WWW) zu einer der wichtigsten Quellen beim Wissenserwerb entwickelt. Das WWW enthält verschie- denste Quellen, wie Onlineenzyklopädien, Weblogs oder Nachrichtenportale, aber auch frei verfügbare Lernressourcen (Open Educational Ressources) und wissen- schaftliche Publikationen. Teilweise sind diese Ressourcen zu Lernzwecken didaktisch aufbereitet, überwiegend aber nicht. Das WWW zeichnet sich zudem dadurch aus, dass Informationen zu aktuellen Themen vorliegen, die in Lehrbüchern noch nicht aufgenommen sind. Das selbstgesteuerte Lernen mit Hilfe von solchen Ressourcen, wie sie im In- ternet zu finden sind, wird auch Ressourcen-basiertes Lernen (RBL) genannt und wurde von Norbert Meder in [97] als „ein Sich-verfügbar-Machen von Informatio- nen und Wissensbeständen bei aktuellen Problemen“ beschrieben. Selbstgesteuertes Ressourcen-basiertes Lernen ist mit einer Vielzahl von Herausforderungen für den Lernenden verbunden [145]. Daher wurden Anwendungen entwickelt, um den Ler- nenden individuell im Ressourcen-basierten Lernen zu unterstützen [19]. Eine der größten Herausforderung im Ressourcen-basierten Lernen ist es, relevante Web-Ressourcen im Web zu finden [41]. Suchmaschinen werden sehr häufig ver- wendet, liefern aber praktisch keine Hilfestellung bei der Auswahl und Beurteilung gefundener Ressourcen. Empfehlungssysteme [131] (engl. Recommender Systems) können grundsätzlich hilfreich sein, um für die jeweilige Situation und den jeweiligen Lernenden relevanten Ressourcen zu finden [128]. Allerdings muss beachtet werden, dass an Empfehlungssysteme im E-Learning besondere Anforderungen bestehen. Während Systeme für Produktempfehlungen, wie beispielsweise in Amazon1, die Empfehlung ähnlicher Produkte zum Ziel haben, so ist das im E-Learning nicht immer sinnvoll. Es gibt zum Beispiel Lernende mit verschiedenen Kenntnisstufen. Anfänger brauchen Lernressourcen, die einen groben Überblick über ein bestimmtes 1 https://www.amazon.de/ - Zugriff am 14.11.2012 1 https://www.amazon.de/ 2 einführung Thema geben, während Experten Lernressourcen brauchen, die vertieft in das Thema eingehen [39]. 1.2 ziel, ansatz und beiträge der arbeit In vielen Lernszenarien können sich Lernende gegenseitig unterstützen. Das gilt auch für das Ressourcen-basiertes Lernen. Lernende können davon profitieren, dass sie auf Wissensressourcen hingewiesen werden, die andere Lernende, die einen ähnli- chen Wissensbedarf besitzen, verwendet haben. In größeren Gruppen oder in einer Online Community (wie z.B. Social Bookmarking Applikationen wie delicious2 oder GroupMe3) sind für die eigene Lernaufgabe relevante Ressourcen mit hoher Wahr- scheinlichkeit bereits von anderen Personen gefunden worden. Zielsetzung dieser Arbeit ist es, gerade im Ressourcen-basierten Lernen dem Lernenden die Ressourcen, die innerhalb einer Community bereits verwendet wurden, situationsabhängig zu- gänglich zu machen. Die Arbeit betrachtet zusammenfassend als generelles Szenario das kollaborative Ressourcen-basierte Lernen in Online Communities. Die Arbeit analysiert dieses Szenario am Beispiel der CROKODIL-Lernumgebung [8], die Ressourcen-basiertes Lernen unterstützt, und zeigt bestehende Schwächen der zur Verfügung stehenden Anwendung auf. So können Lernende heute, obwohl Empfehlungssysteme in der CROKODIL-Lernumgebung realisiert sind, nur teilwei- se von den Ressourcen anderer Community-Mitglieder profitieren. Dies resultiert insbesondere aus der Tatsache, dass die Lernenden verschiedene Terminologien bei der Verschlagwortung von Ressourcen verwenden. Anfänger kennen die spezifische Terminologie des Themas, für das sie sich interessieren nicht. Experten dagegen kennen und benutzen die spezifische Terminologie des Gebietes, um sich präzise auszudrücken. Der Ansatz dieser Arbeit besteht darin, eine Taxonomie dazu zu verwenden, um diese Unterschiede in der von den Benutzern verwendeten Terminologie zu über- brücken. Mittels der Taxonomie sollen Beziehungen zwischen den von den Lernenden zur Verschlagwortung von Ressourcen verwendeten Begriffen ergänzt werden. Da- mit stehen zusätzliche Informationen zur Verfügung, die verwendet werden sollen, um verbesserte Empfehlungssysteme zu realisieren und damit dem Lernenden die Ressourcen anderer Community-Mitglieder zugänglich zu machen. Das Szenario des Ressourcen-basierten Lernens in Communities stellt an die Taxo- nomie die Anforderung, dass sie einerseits aktuelle Begriffe aus nahezu beliebigen Wissensdomänen enthalten muss, um Lernenden in ihren akuten Lernaufgaben zu unterstützen, und andererseits in mehreren Sprachen vorliegen muss, da Lernende häufig Ressourcen in unterschiedlichen Sprachen verwenden und ebenso Schlagworte aus unterschiedlichen Sprachen zur Auszeichnung der Ressourcen nutzen. Zur Erstel- lung solcher aktueller, umfassender Taxonomien in mehreren Sprachen verfolgt diese Arbeit den Ansatz die Wikipedia, als umfassende mehrsprachige Onlineenzyklopädie, als Wissensbasis zu verwenden. Die vorliegende Arbeit umfasst folgende Beiträge: • Das Szenario des kollaborativen Ressourcen-basierten Lernens in Online-Com- munities wird anhand des Beispiels der CROKODIL-Lernumgebung analysiert und es werden bestehende Herausforderungen identifiziert. 2 http://delicious.com/ - Zugriff am 14.11.2012 3 http://groupme.org/GroupMe/ - Zugriff am 14.11.2012 http://delicious.com/ http://groupme.org/GroupMe/ 1.3 gliederung der arbeit 3 • Basierend auf dieser Analyse wird ein Konzept zur Bereitstellung von zusätzli- chen Relationen zwischen den von Lernenden zur Verschlagwortung verwende- ten Begriffen auf Basis von Taxonomien entwickelt. Das Ziel ist hierbei Lernen- den die Ressourcen anderer Community-Mitglieder zugänglich zu machen. Die Anforderungen an die genutzte Taxonomie werden ebenfalls bestimmt. • Es werden zwei Verfahren zur sprachunabhängigen Generierung von Taxonomi- en auf Basis der Wikipedia entworfen, die die zuvor bestimmten Anforderungen erfüllen, konzipiert, implementiert und evaluiert. • Das Konzept zur Bereitstellung von zusätzlichen Relationen wird als Erweite- rung der CROKODIL-Lernumgebung implementiert. • Die Verwendung der Taxonomien zur Ergänzung von Relationen zwischen Schlagworten in der CROKODIL-Lernumgebung wird evaluiert. • Ein Framework zur Evaluation von auf Folksonomien basierenden Empfeh- lungssystemen wird konzipiert, implementiert und verwendet, um den Nutzen der Verwendung von Relationen zwischen Schlagworten anhand eines Standar- dempfehlungssystems zu evaluieren. 1.3 gliederung der arbeit Die vorliegende Arbeit gliedert sich wie folgt: Nach dieser Einleitung erfolgt in Kapi- tel 2 die Beschreibung des Anwendungsszenarios Ressourcen-basiertes Lernen und der für das Verständnis der Arbeit notwendigen Grundlagen. Die wichtigsten Begriffe werden definiert. Kapitel 3 fasst verwandte Arbeiten zu dem in dieser Arbeit behan- delten Themen und Ansätzen zusammen. In Kapitel 4 wird das Anwendungsszenario des kollaborativen Ressourcen-basierten Lernens detailliert anhand der CROKODIL- Lernumgebungen analysiert und es werden die Herausforderungen bestimmt. Die Zielsetzung der Arbeit und das Konzept zur Bestimmung von Relationen zwischen Schlagworten auf Basis von Taxonomien und deren Verwendung in Empfehlungssys- temen werden vorgestellt. Kapitel 5 stellt zwei sprachunabhängige Methoden vor, mit deren Hilfe sich taxonomische Beziehungen aus der Wikipedia bestimmen lassen, und evaluiert sie. Kapitel 6 beschreibt die Umsetzung des zuvor vorgestellten Konzeptes in der CROKODIL-Plattform. Anschließend wird in Kapitel 7 der Nutzen der ergänzten Relationen evaluiert. Kapitel 8 fasst den Inhalt dieser Arbeit zusammen und schließt die vorliegende Arbeit mit einem Ausblick auf zukünftige Forschungsarbeiten ab. 2 G R U N D L A G E N »Man muss sicher auf festem Boden gehen können, ehe man mit dem Seiltanzen beginnt.« — Henri Matisse Dieses Kapitel führt die Terminologie ein, die im Rahmen dieser Arbeit be- nutzt wird. Im ersten Abschnitt werden grundlegende Arbeiten und Begriffe zum Thema Information Retrieval und kollaboratives Ressourcen-basiertes Lernen vorgestellt. Da sich diese Arbeit mit Taxonomien zur Unterstützung des Ressourcen- basierten Lernens beschäftigt, soll im dritten Abschnitt ein Überblick über verschie- dene Möglichkeiten der Wissensrepräsentation gegeben werden. Abschließend wird auf Wikipedia als Wissensquelle eingegangen, weil diese im Rahmen dieser Arbeit Wikipedia als Wissensquelle zur Generierung einer Taxonomie benutzt wird. 2.1 ressourcen-basiertes lernen und lernressourcen Das Internet hat sich zu einer wichtigen Quelle von im Lernprozess zu verwendenden Ressourcen entwickelt. Heutzutage ist ein großer Teil des menschlichen Wissens digital über das Internet verfügbar. Beispielsweise werden Bücher über Initiativen wie Google Books1 digitalisiert. Darüber hinaus können Bibliotheken ihre Sammlungen in die Google Buchsuche aufnehmen lassen. Ein anderes Beispiel für Institutionen, die Ressourcen im Internet zur Verfügung stellen, sind wissenschaftliche Gesellschaf- ten und Verlage wie Association for Computing Machinery (ACM)2 bzw. Springer Link3, die schon lange digitale Kopien von wissenschaftlichen Beiträgen anbieten. Aber nicht nur Bücher und wissenschaftliche Publikationen sind online verfügbar, sondern beispielsweise auch Anleitungen für Haushaltsgeräte oder Computer-Treiber. Zusätzlich sind in den letzten Jahren die sogenannten Web 2.0 Technologien, wie We- blogs (Blogs), Soziale Netzwerke oder Foren entstanden. Diese Technologien erlauben Internet-Nutzern, eigenes Wissen im Web verfügbar zu machen und mit Interessierten zu interagieren. Diese Entwicklung ist in informellen Lernsettings, insbesondere in Lernsettings, in denen Lernende die Organisation und Planung ihres Lernprozesses selbst übernehmen, relevant. Meder definiert in [97] die Art des Lernens mit Ressourcen z.B. aus dem Internet als „ein Sich-verfügbar-Machen von Informationen und Wissensbeständen bei aktuellen Problemen“. Diese Art des Lernens hat Rakes [123] als einen Lernmodus, bei dem Lernende durch eigene Interaktion mit einer großen Vielfalt an Ressourcen anstatt durch Frontalunterricht lernen, bezeichnet. Allerdings schlägt Rakes vor, dass Lehren- de eine Vorauswahl an Ressourcen vornehmen sollten und nicht die Studenten das gesamte Netz durchstöbern sollen. Tergan [157] bezog die Definition von Rakes vor 1 http://books.google.com - Zugriff am 14.11.2012 2 http://dl.acm.org - Zugriff am 14.11.2012 3 http://www.springerlink.com - Zugriff am 14.11.2012 5 http://books.google.com http://dl.acm.org http://www.springerlink.com 6 grundlagen allem auf Hypertextumgebung und Internetressourcen und erwartete von Lernenden die selbstständige Suche nach Lernressourcen im Web. Heutige Schätzungen4 gehen davon aus, dass das Web mehr als 7,9 Billionen Webseiten umfasst, und diese Anzahl wächst täglich. Auch wenn nur ein geringer Teil dieser Webseiten relevante und wertvolle Informationen, die für das Lernen verwendet werden können, enthalten, ist es immer noch eine unüberschaubare An- zahl von Ressourcen. Damit ergeben sich für das Lernen mit diesen Ressourcen Herausforderungen: Viele Ressourcen sind nicht für das Lernen aufbereitet. Relevan- te Informationen sind zum Beispiel oft über verschiedene Ressourcen verteilt. Die Unerfahrenheit von Lernenden ist ein weiteres Problem, denn sie können zumindest am Anfang einer Recherche nicht über die Vertrauenswürdigkeit und Relevanz von Ressourcen urteilen. Weitere Probleme werden von Tergan in [157] und Naumann in [107] angesprochen. Tergan spricht von struktureller und konzeptueller Desorientie- rung, die auftreten, wenn ein Lernender seine Recherche nicht strukturieren kann (z.B. wenn er nicht weiß, wie er am besten die Suche startet oder wenn er Schwierigkeiten hat beim Auffinden bereits besuchter Webseiten) bzw. wenn er neue Informationen nicht aufnehmen kann (z.B. weil Vorwissen fehlt). Naumann wiederum spricht von der kognitiven Mehrbelastung, wenn Lernende ihre Konzentration nicht nur für das Lernen, sondern für andere Aufgaben wie das Finden, Bewerten oder Speichern von Ressourcen verwenden müssen. Ressourcen-basiertes Lernen mit Ressourcen aus dem Internet findet in sehr vie- len Szenarien statt: Wenn Studenten einen Vortrag im Rahmen einer Gruppenarbeit erstellen möchten und Informationen im Netz suchen, wenn ein Schüler ein Biologie- Referat vorbereiten soll, wenn Mitarbeiter einer Firma eine Geschäftsreise nach Indien planen und sich über Land und die Kultur informieren wollen oder wenn Wissen- schaftler an einem Beitrag arbeiten und nach verwandten Arbeiten recherchieren. An diesen Beispielen werden zwei Aspekte deutlich: erstens, dass das Vorwissen der Per- sonen nicht ausreicht, um einen aktuellen Informationsbedarf zu decken, sodass sie selbstständig nach digitalen Ressourcen suchen müssen und zweitens, dass Lernende zwar die Aufgabe alleine bearbeiten, aber oft einer größeren Gruppe angehören. Bei- spielsweise gehört ein Schüler zu einer Klasse, ein Studenten besucht eine Vorlesung zusammen mit anderen Studenten, ein Mitarbeiter ist einer von vielen in einer Firma und ein Forscher einer von vielen in einer Forschergruppe. Aus diesem Grund stellte Tergan fest, dass Lehrende Lernenden Werkzeugen zur Unterstützung des Ressourcen- basierten Lernens anbieten sollten. In [19] diskutiert Böhnstedt weitere Definitionen des Ressourcen-basierten Lernens im Web und definiert Ressourcen-basiertes Ler- nen als „Form des Lernens, bei welcher der aktuelle Informationsbedarf durch die selbständige Interaktion mit einer Vielzahl verschiedener digitaler Lernressourcen gedeckt wird“. Diese Definition beschreibt sehr genau das Ressourcen-basierte Ler- nen, wie es im Rahmen dieser Arbeit benutzt wird, betrachtet allerdings nicht die oben erwähnte zweite Tatsache: Da Lernende in vielen Szenarien Mitglieder einer größeren Gruppe sind, gibt es eine hohe Wahrscheinlichkeit, dass andere Mitglieder relevante oder ähnliche Ressourcen bereits gefunden haben. Daher wird in dieser Arbeit Ressourcen-basiertes Lernen wie folgt definiert: 4 http://www.worldwidewebsize.com/ - Zugriff am 14.11.2012 http://www.worldwidewebsize.com/ 2.1 ressourcen-basiertes lernen und lernressourcen 7 Definition 1 (Ressourcen-basiertes Lernen (RBL) in Online-Communities) RBL in Online Communities wird definiert als Form des Lernens, bei welcher Lernende ihren aktuellen Informationsbedarf durch selbständige Interaktion mit einer Vielzahl verschiedener digitaler Lernressourcen decken. Lernende gehören dabei einer Community an, deren andere Mitglie- der ebenfalls durch selbständige Interaktion mit Lernressourcen lernen. Die gesammelten Lernressourcen stehen allen Mitgliedern der Community zur Verfügung. Diese Definition schließt weder die Anleitung durch einen Experten oder Lehrer noch die Kollaboration zwischen den Mitgliedern der Community aus, fokussiert aber auf das selbstgesteuerte Suchen und Lernen eines Lernenden. In dieser Definition kommt das Konzept „Lernressource“ vor. Bevor die Heraus- forderungen im Ressourcen-basierten Lernen in Communities analysiert werden, soll dieser Begriff an dieser Stelle nochmals erklärt werden. In der Literatur sind die Begriffe „Lernressourcen“ und „Lernobjekte“ eng miteinander verknüpft, oft werden sie sogar synonym benutzt. Die Tatsache, dass sich sehr viele Forscher mit Lernressourcen beschäftigt haben, hat dazu geführt, dass sich keine klare Definition des Begriffs „Lernobjekt“ gebildet hat. Die existierenden Definitionen hängen in der Regel vom Anwendungsszenario ab. Scholl hat in [145] verschiedene Definitionen diskutiert und folgerte, dass Forscher in der Vergangenheit folgende Merkmale in den Vordergrund der Definition von Lernobjekten stellen: • Granularität, also die Feinkörnigkeit der Lernobjekte, je nachdem, ob ein Lern- objekt aus vielen anderen kleinen besteht. Hier haben sich Autoren wie Wiley [165], Polsani [116], Boyle [22] oder Meyer [100] mit der Frage beschäftigt, ob Fragmente von Lernobjekten auch Lernobjekte sind und wie sich aus diesen Fragmenten neue Lernobjekte erstellen lassen. • Wiederverwendbarkeit, die lange Zeit im Fokus der Forschung war, definiert, inwieweit sich Lernobjekte für verschiedene Zwecke adaptieren lassen. Autoren wie Polsani [116], Hörmann [59], Meyer [100] und Zimmermann [174] legten einen großen Fokus auf die Wiederverwendbarkeit von Lernobjekten. • Lernabsicht, d.h. inwieweit die Absicht mit dem ein Objekt erstellt wurde, seine Eigenschaften als Lernobjekt betrifft. Beispielsweise definierte L’Allier [80] verschiedene Kriterien, die Ressourcen erfüllen müssen, um als Lernobjekte zu gelten. Eines dieser Kriterien war u.a. die Tatsache, dass ein Lernziel definiert ist. Darüber hinaus muss dieses Ziel durch Deckung eines Informationsbedarfs erreichbar sein und es muss bewertbar sein, ob und ab wann das Ziel erreicht wurde. Polsani [116] und Littlejohn [84] definierten Lernobjekte allerdings weni- ger strikt, da eine zu große Fixierung auf Lernziele die Wiederverwendbarkeit beeinträchtigen könnte. • das Beinhalten von Metadaten, um die Suche, Katalogisierung und den Nutzen von Lernobjekten zu unterstützen. Hodgins klassifizierte in [58] Lernobjekte je nach der Art der Metadaten, mit der sie versehen sind. • ihr Inhaltsmodell, je nachdem, wie der Inhalt des Lernobjekts eingebunden ist. Bekannte Inhaltsmodelle sind das Cisco-Inhaltsmodell [14] und das Inhaltsmo- dell von Hodgins [58]. 8 grundlagen • im Lebenszyklus, unterteilt in Erstellung, Wiederverwendung, Benutzung und Bereitstellung. Die Unterstützung des Lebenszyklus von Lernobjekten haben sich Autoren wie Downnes [38], Rensing et al. [126] und Lehmann [82] vorge- nommen. Allerdings stellt Polsani in [116] fest, dass diese vielen Definitionen von Lernobjek- ten nicht konsistent sind und sich zum Teil widersprechen. Darüber hinaus existie- ren Formate wie das Learning Object Metadata (LOM)5 (LOM) oder das Shareable Content Object Reference Model (SCORM)6 (SCROM), um Lernobjekte zu beschrei- ben oder auszutauschen. Im Ressourcen-basierten Lernen, wie es in dieser Arbeit betrachtet wird, spielen Web-Ressourcen eine große Rolle, insofern schränken die Definitionen von Lernobjekten aus der Literatur das Ressourcen-basierte Lernen zu sehr ein. Aus diesem Grund werden im Rahmen dieser Arbeit Lernressourcen wie folgt definiert: Definition 2 (Lernressourcen) Lernressourcen sind digitale (Web-)Ressourcen, die vom Lernenden im Ressourcen-basierten Lernen genutzt werden können. Lernressourcen können z.B. Webseiten, Videos, Bilder oder Blog-Einträge sein. Darüber hinaus deckt diese Definition die Definitionen aus vorherigen Arbeiten ab, wenn die Lernobjekte digital vorliegen und über das Web verfügbar sind. Laut Definition 2 müssen Lernressourcen weder explizit für das Lernen aufbereitet noch durch Metadaten beschrieben sein oder andere Eigenschaften besitzen. 2.2 information retrieval und maschinelles lernen Information Retrieval (IR) (auf Deutsch Informationsrückgewinnung) wird von Man- ning et al. in [91] wie folgt definiert: „Information Retrieval is finding material (usually documents) of an unstructured nature (usually text) that satisfies an information need from within large collections (usually stored on computers)“. Danach ist Information Retrie- val als das Finden von unstrukturierten Dokumenten in einer großen Menge von Dokumenten, um einen Informationsbedarf zu decken, definiert. Im Folgenden wer- den verschiedene Konzepte aus diesem Gebiet eingeführt und insbesondere auf die Evaluation von Systemen für Information Retrieval eingegangen. 2.2.1 Information Retrieval 2.2.1.1 Informationsbedarf Der Informationsbedarf eines Benutzers bezeichnet den Wunsch nach Informationen zu einem gegebenen Thema, um z.B. eine gegebene Aufgabe zu lösen [91]. Man unterscheidet zwischen Informationsbedarf und Anfrage. Eine Anfrage beschreibt den Versuch eines Benutzers, seinen Informationsbedarf mitzuteilen [91]. Dies kann in textueller Form (z.B. SQL-Anfrage7), implizit (z.B. mittels Analyse des Benutzer- 5 http://www.adlnet.gov/Technologies/scorm/SCORMSDocuments/20044thEdition/ - Zugriff am 14.11.2012 6 http://ltsc.ieee.org/wg12/files/LOM_1484_12_1_v1_Final_Draft.pdf - Zugriff am 14.11.2012 7 Standard Query Language (SQL) http://www.adlnet.gov/Technologies/scorm/SCORMSDocuments/ 20044thEdition/ http://ltsc.ieee.org/wg12/files/LOM_1484_12_1_v1_Final_Draft. pdf 2.2 information retrieval und maschinelles lernen 9 verhaltens oder seiner gespeicherten Dateien) oder auf andere Weisen geschehen(z.B. mit „Like“-Knöpfen in Facebook8) 2.2.1.2 Relevanz Eine Ressource oder ein Dokument ist relevant für einen Benutzer, wenn die Ressource wertvolle Informationen bzgl. des Informationsbedarfs eines Benutzers [91] enthält. Allerdings muss man an dieser Stelle anmerken, dass die Relevanz immer eine Portion Subjektivität hat und dass die Qualität des Retrieval von der Anfrage des Benutzers abhängt. 2.2.1.3 Ranking Informell kann ein Ranking als eine Liste von Entitäten gemäß einem Ranking- Kriterium bezeichnet werden. Beispielsweise kann ein Ranking von Ressourcen eine Liste von Ressourcen sein, in dem die Ressourcen in absteigender Reihenfolge gemäß Relevanz den Informationsbedarf eines Benutzers decken. Formell ist ein Ranking ein Tupel von Entitäten in geordneter Reihenfolge. Entitäten sind eine Menge von Dingen, die gerankt werden und die miteinander vergleichbar sein können auf der Basis eines Ranking-Kriteriums, das durch die binäre Relation / ausgedrückt wird. R = {(e0,...,en)|(e0,...,en) ∈ P(E)∧ ∀k = {0,...,n− 1}⇒ ek+1 / ek} E stellt eine Menge von Entitäten dar, die gerankt werden sollen. P(E) Menge von Permutationen von E / Totale, reflexive und transitive binäre Relation basierend auf Ranking-Kriterien 2.2.1.4 Empfehlung Eine Empfehlung von Entitäten sind Vorschläge. Üblicherweise werden diese Vor- schläge von einem Empfehlungssystem generiert. Entitäten können alle möglichen Ressourcen, Benutzer oder Dinge sein. Beispielsweise beschreibt Koren in [77] ein Film-Empfehlungssystem. In [3] stellen Adomavicious et al. verschiedene traditionelle Empfehlungssysteme dar. Das Ziel von traditionellen Empfehlungssystemen ist die Bestimmung einer Ratingfunktion R mit folgender Signatur: R : Benutzer× Entität→ Rating Die Ratingfunktion ist partiell, da kein Benutzer alle Entitäten gespeichert hat. Ein Empfehlungssystem muss die Ratingfunktion total machen, also unbekannte Ratings raten. In Folksonomie-Anwendungen 2.3.8 ist Rating ∈ {0,1}, je nachdem, ob ein Benutzer eine Ressource getaggt hat oder nicht. Die Abschätzung von unbekannten Ratings stellt ein Ranking dar. Aus diesem Grund lassen sich Empfehlungssysteme als Rankingsysteme ansehen. Ein Empfehlungssystem prognostiziert Entitäten basierend auf Informationen über sie und auf dem Profil des Benutzers [64]. In Abschnitt 3.1 wird auf die verschiedenen Empfehlungssysteme näher eingegangen. 8 http://www.facebook.com - Zugriff am 14.11.2012 http://www.facebook.com 10 grundlagen 2.2.2 Maschinelles Lernen Der Einsatz von Methoden des maschinellen Lernens für die Klassifizierung von Relationen zwischen den Konzepten stellt einen Schwerpunkt dieser Arbeit dar. Im folgenden Kapitel sollen die Prinzipien erklärt werden, wie solche Verfahren evaluiert werden. Mitchell hat in [103] maschinelles Lernen wie folgt definiert: „A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with Experiences E“. Es geht also darum, dass ein Computer-Programm von Erfah- rungen E lernt, wie eine Aufgabe (oder Menge von Aufgaben) T gelöst wird, sodass sie bzgl. einer gegebenen Metrik bzw. Maß besser abschneidet. Beispielsweise kann ein Schachspieler-Computer-Programm seine Gewinnquote (P) beim Schachspielen (T) durch Erfahrungen verbessern, wenn es immer wieder gegen sich selbst spielt (E). In dieser Arbeit wird maschinelles Lernen im Rahmen von binären Klassifikati- onsaufgaben angewendet. Eine Klassifikationsaufgabe bezeichnet die Aufgabe der Klassifizierung von Instanzen in einer gegebenen diskreten Menge von möglichen Kategorien [103]. Bei binären Klassifikationsaufgaben geht es darum, zwischen genau zwei Kategorien zu unterscheiden. Die Klassifizierungsaufgabe übernimmt ein Klas- sifikator. Der Klassifikator entscheidet anhand einer gegebenen Beispielmenge, wie eine neue Instanz klassifiziert wird. Angewendet auf die Definition von maschinellem Lernen stellt man fest, dass die Aufgabe (T) darin besteht, zwischen zwei Kategorien c1 und c2 zu unterscheiden, die Erfahrungen (E) kommen aus einer gegebenen Bei- spielmenge, genannt Trainingskorpus, und die Performanz (P) wird anhand der im nächsten Abschnitt (2.2.3) vorgestellten Metriken gemessen. Konkret entscheidet der Klassifikator basierend auf sogenannten Features, ob eine Instanz zu c1 oder c2 gehört. Ein Feature wird auf eine Instanz angewendet und liefert als Ergebnis jedes Features einen Zahlenwert zurück. Anschließend, wenn alle Features zu einer Instanz berechnet wurden, werden die Werte in einen soge- nannten Featurevektor eingetragen. Der Featurevektor wird dabei als Repräsentation der Instanz angesehen und kann benutzt werden, um ähnliche Instanzen oder wie- derkehrende Muster zwischen den Instanzen zu berechnen. Die Erstellung eines Featurevektors wird in Abbildung 1 dargestellt. KOM – Multimedia Communications Lab 5 Our Approach Feature f1 Feature f2 … Feature fn Link (c1,c2) … Featurevektor = ( v1 v2 … vn ) 2 Abbildung 1: Erstellung des Featurevektors 2.2.3 Evaluationsmaße Die im Rahmen dieser Arbeit entwickelten Verfahren werden mit Hilfe von Maßen aus dem Information Retrieval evaluiert: Precision, Recall und F-Maß. Diese Maße helfen dabei, die Güte der Verfahren aus mehreren Blickwinkeln zu beurteilen. 2.2 information retrieval und maschinelles lernen 11 Gegeben sei ein Klassifikator k, der eine (z.B. binäre) Klassifikation c1 oder c2 vornimmt. Der Klassifikator klassifiziert Entitäten e = {e1,e2,...,en} in den beiden Klassen c1 oder c2 ein. Bei diesem Prozess kann der Klassifikator allgemeine Fehler begehen, d.h. er sortiert eine Entität ei in die falsche Klasse ein. Abhängig vom Ergebnis der Klassifikation sowie von der tatsächlichen Klasse der Entität können vier Fälle unterschieden werden: 1. Richtig-positiver Fall (engl. true positive, tp): Eine Entität ei der Klasse c1 wird korrekt als c1 markiert. 2. Richtig-negativer Fall (engl. true negative, tn): Eine Entität ei der Klasse c2 wird korrekt als c2 markiert. 3. Falsch-positiver Fall (engl. false positive, fp): Eine Entität ei der Klasse c1 wird fälschlicherweise als c2 markiert. 4. Falsch-negativer Fall (engl. false negative, fn): Eine Entität ei der Klasse c2 wird fälschlicherweise als c1 markiert. Oft benutzt man eine sogenannte Konfusionsmatrix, um die Ergebnisse der Klassifi- kation darzustellen. Ein Beispiel wird in Tabelle 1 dargestellt. Tabelle 1: Beispiel einer Konfusionsmatrix Der Link gehört zur Klasse c1 Der Link gehört zur Klasse c2 Als c1 klassifiziert Richtig-positiv (tp) Falsch-positiv (fp) Als c2 klassifiziert Falsch-negativ (fn) Richtig-negativ (tn) Aus den Werten der Konfusionsmatrix lassen sich zwei zentrale Kennzahlen zur Evaluation eines Klassifikators errechnen [90]: Recall (auch Sensitivität oder Trefferquote genannt), die als Anteil der korrekt als c1 klassifizierten Entitäten an der Gesamtheit der tatsächlich existierenden c1 Entitäten definiert werden. Recall entspricht der bedingten Wahrscheinlichkeit: P(richtig als c1 erkannt|alle tatsächlichen existierenden c1-Entitäten) = tp tp+fn Precision (auch Relevanz, positiver Vorhersagewert, Genauigkeit genannt), der Anteil der korrekt als c1 klassifizierten Entitäten an der Gesamtheit der als c1 erkann- ten Entitäten. Precision entspricht der bedingten Wahrscheinlichkeit: P(richtig als c1 erkannt|alle als c1-erkannten Entitäten) = tp tp+fp Recall und Precision stehen oft in Konflikt zueinander: Ein höherer Recall eines Klassifikators bedeutet, dass der Großteil der tatsächlichen c1-Entitäten vom Klas- sifikator als c1 korrekt klassifiziert wurde. Darunter kann aber die Precision leiden, da der Klassifikator für diesen Zweck viele c2-Entitäten u.U. klassifizieren müsste. Umgekehrt kann eine hohe Precision zu einem schlechten Recall führen. Ein Klassi- fikator, der „auf Nummer sicher“ geht und nur Entitäten als c1 klassifiziert, wenn er sich sehr sicher ist, produziert hohe Precision-Werte. Dies führt aber auch dazu, 12 grundlagen dass viele „unsichere“ c1-Entitäten übersprungen werden, was wiederum zu einer niedrigeren Precision führt. Je nach Anwendungsszenario können abhängig vom Schwerpunkt der Suche Such- ergebnisse mit höherem Recall oder mit höherer Precision bevorzugt werden, indem dem Recall oder der Precision höhere Gewichtung zugeordnet wird [133]. Aus dem Precision und dem Recall kann ein sogenanntes F-Maß berechnet werden, das ein kombiniert gewichtetes harmonisches Maß für Recall und Precision darstellt. Im Rahmen dieser Arbeit wird die sogenannte F1-Maß (Precision und Recall werden jeweils mit dem Wert 1 gewichtet) wie folgt berechnet: F1 = 2∗Precision∗Recall Precision+Recall In allgemeinerer Form lautet die Formel für Fα (mit α > 0) [133]: Fα = (1+α)∗Precision∗Recall α∗Precision+Recall F2 gewichtet z.B. den Recall doppelt so stark wie die Precision, bei F0,5 hingegen nimmt die Precision eine doppelt höhere Gewichtung im Vergleich zum Recall ein. Van Rijsbergen postuliert in [133], dass F-Maß ein Maß für die Effektivität der Informationsgewinnung aus Sicht eines Benutzers ist. Ein wichtiger Unterschied zwischen Recall und Precision ist der Fakt, dass das Recall nicht vom Verhältnis zwischen den positiven und negativen Fällen in der Testmenge abhängt. Der Recall beschränkt sich nur auf die positiven Fälle (c1) und es spielt keine Rolle, ob die positiven Fälle in der Testmenge unter- oder überrepräsentiert sind. Die Berechnung der Precision dagegen bezieht sowohl die positiven als auch die negativen Fälle in die Berechnung mit ein, was dazu führt, dass die Precision durch das Verhältnis zwischen positiven und negativen in der Testmenge beeinflusst wird. 2.2.4 Evaluationsverfahren Für die Evaluation von Verfahren im Information Retrieval werden oft Varianten der sogenannten Kreuzvalidierung (engl. cross-validation) genutzt [103]. Mittlerweile hat sich die sogenannte k-fache stratifizierte Kreuzvalidierung (engl. K-Fold Cross- Validation) als aus statischer Sicht beste Wahl herauskristallisiert [16]. Im Rahmen dieser Arbeit werden die Ergebnisse des Verfahrens des maschinellen Lernens mittels einer zehnfachen stratifizierten Kreuzvalidierung überprüft. Die Vorgehensweise wird in Abbildung 2 gezeigt: Der gesamte Korpus wird in zehn Stichproben zerlegt. Davon werden neun Proben (90 % der Proben, hier in Grün dargestellt) als Trainingsdaten be- nutzt und die zehnte Probe (10% der Proben, hier in Rot dargestellt) als Testdaten. Der Evaluationsvorgang wird 10 Mal durchlaufen, wobei jede Stichprobe genau einmal als Testprobe eingesetzt wird. Abschließend werden die erhaltenen Ergebnisse über eine Mittelwertbildung bzw. über eine andere Kombinierungsmethode zusammengeführt, um ein einheitliches gesamtes Ergebnis zu erreichen. Der Vorteil dieser Methode liegt darin, dass alle Stichproben sowohl für das Training als auch für die Validierung des Verfahrens benutzt werden und jede Stichprobe genau einmal als eine Testprobe auftritt. Durch den Einsatz der zehnfachen stratifizierten Kreuzvalidierung wird der Einfluss von zufälligen Ausreißern vermindert sowie eine klare Trennung zwischen Training- und Test-Daten erreicht [76]. 2.3 wissensrepräsentation 13 . . . . 1 2 10 3 Abbildung 2: 10-fache stratifizierte Kreuzvalidierung 2.3 wissensrepräsentation In dieser Arbeit werden Fachbegriffe aus dem Gebiet der Wissensrepräsentation und der Computerlinguistik verwendet. In diesem Kapitel sollen daher die zum Verständnis der Arbeit notwendigen Fachbegriffe definiert und erklärt werden. 2.3.1 Begriffe Im Rahmen dieser Arbeit sind Begriffe Wörter oder zusammengesetzte Wörter, die eine syntaktische und semantische Einheit bilden. Beispiele von Begriffen sind „Maschine“, „Informationstechnologie“, „Trauer“, „Telefon“ und „Löwe“. 2.3.2 Konzepte Es existieren sehr viele Definitionen eines Konzepts. An dieser Stelle sollen drei Definitionen vorgestellt und diskutiert werden. Definition von Grabrilovitch and Markovitch [46]: „Concepts are the basic units of meaning that serve humans to organize and share their knowledge.“ Konzepte sind also demnach die „Grundeinheiten“ der Bedeutung, die von Men- schen benutzt werden, um ihr Wissen zu organisieren und zu teilen. Bei dieser Definition liegt der Fokus in der Bedeutung eines Wortes. Diese Definition erlaubt durch die Benutzung des Begriffes „Grundeinheit des Wissens“ einen großen Raum an Interpretationen. Es ist hier sehr schwer zu sagen, ob ein gegebener Begriff eine „Grundeinheit des Wissens“ darstellt. Das liegt daran, dass das Wissen von Menschen nicht objektiv messbar ist. Definition aus Wikipedia.org9: „Ein Konzept ist ein Ergebnis des Instruments des Prozesses kognitiver Konzeption von Begriffen mit Sprache, der gleichzeitig eine Aussage zum Begriff enthält.“ Diese Definition enthält Begriffe wie „kognitive Konzeption“, die aus der Psycholo- gie kommen. Bei dieser Definition wird ein Konzept als ein Ergebnis der Konzeption deklariert, allerdings ist es mit ihrer Hilfe sehr schwierig zu beurteilen, ob ein be- stimmter Begriff ein Konzept darstellt. 9 http://de.wikipedia.org/wiki/Konzeption - Zugriff am 14.11.2012 http://de.wikipedia.org/wiki/Konzeption 14 grundlagen Definition aus WordNet10: „A concept is an abstract or general idea inferred or derived from specific instances“ Diese Definition ist abstrakter als die zwei vorherigen Definitionen. Sie stellt weder erklärende Beschreibungen vor noch geht sie im Detail auf die spezifischen Instanzen ein. Zwar werden hier die Eigenschaften eines Konzepts definiert, sie erlaubt aber z.B. im Rahmen dieser Arbeit Kategorien in Wikipedia als Konzepte zu sehen und die darin enthaltenen Artikel als Instanzen zu sehen. Zum Schluss bleibt zu erwähnen, dass Konzepte eindeutig sind. Beispielsweise stellt jede Bedeutung des Begriffes „Bank“, das Finanzinstitut und die Sitzgelegenheit, ein einzigartiges und unabhängiges Konzept dar. 2.3.3 Relationen zwischen Konzepten Semantische Relationen: Bevor die verschiedenen Modelle zur Wissensrepräsenta- tion vorgestellt werden, sollen hier einige der in solchen Modellen vorkommenden semantischen Beziehungen zwischen Konzepten vorgestellt werden. Synonymie: Synonymie bezeichnet die inhaltliche Überstimmung zwischen zwei oder mehreren Begriffen. Synonyme Begriffe beschreiben dasselbe Konzept. Beispiele für Synonyme sind die Begriffe „Wagen“ und „Auto“. Beide beschreiben ein Fahrzeug mit vier Rädern. Antonymie: Antonymie besteht zwischen zwei Begriffen, wenn einer der beiden Begriffe das Gegenteil des anderen ist. Beispielsweise sind „Kälte“ und „Wärme“, „weiß“ und „schwarz“ Antonymien. Meronymie: Meronymie stellt eine Teil-Ganzes-Relation zwischen Begriffen dar. Meronymie-Relationen gibt es zwischen „Finger“ und „Hand“ oder ’“Tür“ und „Haus“. Hypernymie und Hyponymie: Als Hyponymie wird in der Linguistik eine Relati- on zwischen zwei Begriffen bezeichnet, bei der ein Begriff in einen anderen Begriff eingeschlossen ist. Nach Cruse [33] wird ein Konzept c1 als Hyponym von c2 be- zeichnet (und umgekehrt wird c2 als Hyperonym von c1 bezeichnet), wenn jedes Individuum von c1 auch ein Individuum von c2 ist, aber nicht umgekehrt. Beispiels- weise ist jede Katze ein Wirbeltier, aber nicht jedes Wirbeltier eine Katze. Aus diesem Grund werden Hyponymie-Beziehungen auch „ist-ein“-Beziehungen genannt. 2.3.4 Taxonomien Taxonomien entstehen, wenn Hyperonyme und Hyponyme hierarchisch strukturiert sind. Der Begriff „Taxonomie“ setzt sich aus den altgriechischen Begriffen „taxis“ (Ordnung) und „nómos“ (Gesetz) zusammen. In [78] wird eine Taxonomie als „ein einheitliches Verfahren oder Modell definiert, um Objekte eines gewissen Bereichs [...] nach bestimmten Kriterien zu klassifizieren, d.h. sie in bestimmte Kategorien oder Klassen (auch Taxa genannt) einzuordnen“. In der Biologie wird eine Taxonomie als Klassenhierarchie verstanden, wie das Beispiel der Unterteilung von Lebewe- sen in Reiche, Stämme, Klassen Ordnungen, Familien, Gattungen und Arten (siehe Abbildung 3). 10 http://wordnetweb.princeton.edu/perl/webwn/ - Zugriff am 14.11.2012 http://wordnetweb.princeton.edu/perl/webwn/ 2.3 wissensrepräsentation 15 Abbildung 3: Eine Taxonomie in der Biologie [10] In dieser Arbeit wird die Definition einer Taxonomie an die Definition der Lin- guistik angelehnt: Eine Taxonomie zeichnet sich durch zwei Eigenschaften aus: Die Hyponymie und die Inkompatibilität (vgl. [33]). Während die Hyponymie sicherstellt, dass es eine Hyponymie-Relation zwischen Ober- und Unterknoten gibt, besagt die Inkompatibilität, dass Begriffe auf der gleichen hierarchischen Ebene nicht austausch- bar sein sollen. Weiter wird in der Linguistik zwischen Klasse-Instanz-Beziehungen, wie z.B. zwischen „Frucht“ und „Apfel“, und reine Hyponymie-Beziehungen, wie z.B. zwischen „Frucht“ und „Pflanze“, unterschieden. Im Rahmen dieser Arbeit werden diese Beziehungstypen unter dem Relationstyp „ist-ein“ zusammengefasst, da diese feinere Unterscheidung für die Anwendungszwecke dieser Arbeit und viele anderer NLP-Anwendungen keine wesentliche Bedeutung hat [152]. Abbildung 4 zeigt ein Beispiel für eine Taxonomie, die verschiedene Fahrzeuge darstellt. 16 grundlagen Fahrzeug Auto Luftfahrzeug Kombi Sportauto Flugzeug Hubschrauber ist-ein ist-ein ist-ein ist-ein ist-ein ist-ein Abbildung 4: Beispiel: Taxonomie 2.3.5 Thesauri Thesauri sind Modelle, die ein Themengebiet repräsentieren. Sie unterscheiden sich von Taxonomien darin, dass neben Hypernymie und Hyponymie weitere Beziehun- gen zwischen den Konzepten enthalten sind. Die erlaubten Relationen zwischen Beziehungen sind in Normen wie ISO 25964-111 definiert. Folgende Relationstypen zwischen Konzepten sind erlaubt: • Benutzt für (Used for) • Synonym (Synonym) • Oberbegriff (Broader term) • Unterbegriff (Narrower term) • Verwandter Begriff (Related term) • Spitzenbegriff (Top term) Abbildung 5 zeigt ein Beispiel eines Thesaurus, der neben einer kleinen Taxonomie auch einen verwandten Begriff und eine „Benutzt für“-Relation enthält. Fahrzeug AutoWagen Kombi Sportauto Taxi Oberbegriff Verwandter Begriff Unterbegriff Benutzt für Unterbegriff Abbildung 5: Beispiel: Thesaurus 11 http://www.iso.org - Zugriff am 14.11.2012 http://www.iso.org 2.3 wissensrepräsentation 17 2.3.6 Ontologien Ontologien sind eine formale und explizite Spezifikation einer gemeinsamen Begriffs- bildung [151]. Sie bestehen aus Begriffen und Relationen zwischen diesen Begriffen. Darüber hinaus unterscheiden sie zwischen Begriffen und Instanzen. Instanzen stellen Individuen eines Begriffes dar. Beispielsweise sind „Deutschland“, „Spanien“ und „Italien“ Instanzen des Begriffs „Land“. Relationen zwischen Begriffen können auch auf die Instanzen übertragen werden. Abbildung 6 zeigt eine kleine Beispielontologie mit verschiedenen Relationstypen. Fahrzeug Auto Gelb Reifen Sportauto Taxi Oberbegriff Hat FarbeUnterbegriff Benutzt für Unterbegriff Michelin Reifen Teil-von Abbildung 6: Beispiel: Ontologie Des Weiteren können in einer Ontologie logische Regeln (Axiome) gelten, die die Deduktion von weiteren Regeln ermöglichen. Aus den Fakten „Alle Autos haben Räder“ und „Der VW Touran ist ein Auto“ lässt sich schließen, dass der „VW Touran Räder“ hat. Diese Eigenschaft unterscheidet Ontologien von allen anderen Modellen zur Wissensrepräsentation. Gruber verlangt in [50] außerdem die Maschinenlesbarkeit als eine weitere Eigenschaft von Ontologien. Heutzutage ist das OWL-Format12 der bekannteste Standard für die Darstellung von Ontologien. Das Beispiel in Abbildung 6 beschreibt die Begriffe „Fahrzeug“ und „Auto“. „Auto“ ist ein Unterbegriff von „Fahrzeug“ und ist definiert als ein „Fahrzeug“ mit dem Wert „car“ im Property „Typ“. 1 6 11 12 http://www.w3.org/TR/owl2-overview - Zugriff am 14.11.2012 http://www.w3.org/TR/owl2-overview 18 grundlagen 16 ... \caption{Beispiel: Ontologie-Datei} \label{fig:ontology-file} 2.3.7 Semantische Netze Semantische Netze haben, genauso wie Taxonomien, keine fest definierten Bezie- hungstypen. Im Gegensatz zu Ontologien müssen sie nicht formell definiert sein. Sowa hat in [150] ein semantisches Netz als eine graphische Notation zur Darstellung von Wissen definiert. Diese graphische Notation setzt sich aus Knoten, die Konzepte darstellen, und Kanten, die Relationen zwischen ihnen darstellen, zusammen. Jedes Konzept wird durch die Verbindung zu anderen Konzepten definiert. Begriffe und Instanzen werden in semantischen Netzen durch eine spezielle Relation („ist vom Typ“) dargestellt. Beispielsweise gilt: Ein VW Touran „ist vom Typ“ Auto. Zusätzlich dürfen Relationen Unterrelationen haben. Ein Beispiel für ein semantisches Netz wird in Abbildung 7 gezeigt. Die Relation „Haben einen europäischen Hersteller“ hat eine Unterrelation „Haben einen deutschen Hersteller“. Fahrzeug Auto VW Touran VW Golf ist Untertyp von ist vom Typ ist vom Typ Haben einen deutschen Hersteller Haben einen europäischen Hersteller ist Unterrelation von Abbildung 7: Beispiel: Semantisches Netz 2.4 wikipedia 19 2.3.8 Folksonomien Tagging ist der Prozess der Verschlagwortung von Ressourcen. Das Schlagwort wird Tag genannt. Tagging erfolgt heute in sehr vielen Online-Communities wie delicious13, Flickr14 oder YouTube15. Eine Folksonomie besteht aus allen Tags, Ressourcen und Benutzern in einer Online- Community. Hotho hat in [61] eine Folksonomie formell als ein 4-Tupel definiert: F = (U,T ,R,Y), wobei U die endliche Menge der Benutzer, T die endliche Menge der Tags, R die endliche Menge der Ressourcen in der Folksonomie darstellt. Y ist eine ternäre Relation Y ∈ U× R× T , die die Tag-Zuweisungen von Benutzern an Ressourcen repräsentiert. Abbildung 8 zeigt eine kleine Folksonomie, bestehend aus zwei Benutzern, zwei Ressourcen und drei Tags. Ressource 1 wurde mit drei Tags getaggt: „Madrid“, „Weblogs“ und „WWW 2009“. Ressource 2 wurde nur von Benutzer Bob mit dem Tag „Weblogs“ getaggt. Anna Bob 1 2 Madrid WWW 2009Weblogs Abbildung 8: Beispiel: Folksonomie Darüber hinaus wird bei einer Folksonomie die Menge der existierenden Posts, P, betrachtet. Ein Post besteht aus einem Benutzer u, einer Ressource r und allen Tags ti, mit denen u r getaggt hat. Im oben genannten Beispiel gibt es zwei Posts: P1 = (Anna,1,{„Madrid“,“Weblogs“}) und P2 = (Bob,2,{„Weblogs“,“WWW2009“}) 2.4 wikipedia Nachdem im letzten Abschnitt die verschiedenen Möglichkeiten der Wissensreprä- sentation dargestellt wurden, sollen im nachfolgenden Abschnitt Wikipedia16 und ihre Eigenschaften näher betrachtet werden. 13 http://delicious.com - Zugriff am 14.11.2012 14 http://www.flickr.com - Zugriff am 14.11.2012 15 http://www.youtube.com - Zugriff am 14.11.2012 16 http://www.wikipedia.org - Zugriff am 14.11.2012 http://delicious.com http://www.flickr.com http://www.youtube.com http://www.wikipedia.org 20 grundlagen 2.4.1 Das Projekt Wikipedia Wikipedia definiert sich selbst als eine „freely lincensed encyclopedia written by thousands of volunteers in many languages“ [160]. Es handelt sich also um eine frei- lizenzierte Enzyklopädie, die von tausenden Benutzern in vielen Sprachen verfasst wird. Das Wikipedia-Projekt ist im Januar 2001 geboren und entwickelte sich stetig zu einer der zehn populärsten Webseiten17 der Welt. Seit 2003 wird das Projekt von der Wikimedia Foundation18 geleitet. Nach dem aktuellen Stand listet die Wikipedia über 23 Millionen Artikel, verfasst von über 1,52 Millionen Autoren19 in 276 Spra- chen20, auf. Durch die große Anzahl von Freiwilligen kann Wikipedia ein sehr großes Spektrum an Wissensdomänen abdecken. Daraus ergibt sich auch die Tatsache, dass Wikipedia-Artikel sehr aktuell sind. Dieser Fakt sowie die dichte Verweisstruktur [105] machen Wikipedia zu einer attraktiven Quelle für viele Anwendungen [96]. Am Wikipedia-Projekt darf jede Person frei und unentgeltlich teilnehmen, es wird kein Unterschied zwischen Laien, Schülern, Fachleuten oder Forschern gemacht21. Inhalte der Wikipedia werden unter der GNU Free Documentation License (GFDL)22 veröffentlicht, die jedem weitgehende Nutzungsrechte am lizenzierten Werk einräumt. Dadurch lässt sie sich in vielen Projekten einsetzen. 2.4.2 Struktur der Wikipedia Traditionelle Enzyklopädien bestehen aus alphabetisch geordneten Artikeln mit Ver- weisen zu anderen Artikeln und externer akademischer Literatur. Oft gibt es ein Inhaltsverzeichnis. Wikipedia hat einige dieser Grundsätze übernommen und um wertvolle Elemente ergänzt. Der Aufbau der Wikipedia soll in diesem Abschnitt näher betrachtet werden. 2.4.2.1 Artikel Ein Wikipedia-Artikel beschreibt ein Konzept und bietet deskriptive Texte, Bilder, Listen oder andere Arten von Medien zu diesem Konzept. Ein oder mehrere Begriffe können einem Artikel zugewiesen sein und als Indizes dienen. Beispielsweise leitet die Suche nach „Auto“ in Wikipedia zum Artikel „Automobile“23 weiter. Ein Ausschnitt dieses Artikels wird in Abb. 9 gezeigt. 17 http://exploredia.com/10-most-visited-websites-2011-2012/ -Zugriff am 14.11.2012 18 http://de.wikipedia.org/wiki/Wikipedia:Sprachen - Zugriff am 14.11.2012 19 http://exploredia.com/10-most-visited-websites-2011-2012/ - Zugriff am 14.11.2012 20 http://de.wikipedia.org/wiki/Wikipedia:Sprachen - Zugriff am 14.11.2012 21 http://de.wikipedia.org/wiki/Wikipedia:Wikipedianer - Zugriff am 14.11.2012 22 http://de.wikipedia.org/wiki/Auto - Zugriff am 14.11.2012 23 http://upload.wikimedia.org/wikipedia/de/1/1d/GNU_Free_Documentation_License_Version_1.2_ dreispaltig.pdf - Zugriff am 14.11.2012 http://exploredia.com/10-most-visited-websites-2011-2012/ http://de.wikipedia.org/wiki/Wikipedia:Sprachen http://exploredia.com/10-most-visited-websites-2011-2012/ http://de.wikipedia.org/wiki/Wikipedia:Sprachen http://de.wikipedia.org/wiki/Wikipedia:Wikipedianer http://de.wikipedia.org/wiki/Auto http://upload.wikimedia.org/wikipedia/de/1/1d/GNU_Free_Documentation_License_Version_1.2_dreispaltig.pdf http://upload.wikimedia.org/wikipedia/de/1/1d/GNU_Free_Documentation_License_Version_1.2_dreispaltig.pdf 2.4 wikipedia 21 Abbildung 9: Beispiel: Ausschnitt des Wikipedia-Artikels „Automobile“ Des Weiteren verweisen Wikipedia-Artikel zu anderen verwandten Artikeln mittels sogenannter Wikilinks (siehe Abschnitt 2.4.2.2). Sie fangen in der Regel mit einer kur- zen Definition an, auch Glosse genannt (siehe 2.4.2.3). Jeder Artikel gehört mindestens einer Kategorie an (siehe 2.4.2.5). Begriffsklärungsseiten (engl. Disambiguation) dienen zur Klärung mehrdeutiger Begriffe und verweisen auf die jeweiligen Konzepte (siehe 2.4.2.6) 2.4.2.2 Wikilinks Artikel beschreiben ein Konzept. Diese Beschreibung enthält oft Verweise zu ande- ren Wikipedia-Artikeln. Beispielsweise erwähnt der Wikipedia-Artikel „Automobile“ andere Konzepte wie „Kraftfahrzeug“24, „Fuhrwerke“25 oder „Leistung“26. Um die Navigation durch die Wikipedia zu erleichtern, ermöglicht die Wikipedia es, Wikilinks zu erstellen. Wikilinks sind Verweise zu verwandten Artikeln. Zusätzlich gibt es noch Interwikilinks, die gleiche Artikel in verschiedenen Sprachen miteinander verbinden. Sie können für verschiedene Zwecke benutzt werden, wie die Erkennung von Eigennamen in verschiedenen Sprachen [163], für die Erstellung von parallele Korpora [1] oder multilingualer Wissensquellen [2, 106]. Ferner ist es möglich, einen Wikilink von einem Artikel zu einem bestimmten Abschnitt eines anderen Artikels zu erstellen. Die Verweise zwischen Artikeln lassen sich auf einer allgemeineren Ebene als Graph ansehen, in dem Artikel durch gerichtete Kanten (Wikilinks) miteinander verbunden sind. Dieser Graph wird in der Forschung als Artikelgraph bezeichnet. 24 http://de.wikipedia.org/wiki/Kraftfahrzeug - Zugriff am 14.11.2012 25 http://de.wikipedia.org/wiki/Fuhrwerk - Zugriff am 14.11.2012 26 http://de.wikipedia.org/wiki/Leistung_%28Physik%29 - Zugriff am 14.11.2012 http://de.wikipedia.org/wiki/Kraftfahrzeug http://de.wikipedia.org/wiki/Fuhrwerk http://de.wikipedia.org/wiki/Leistung_%28Physik%29 22 grundlagen 2.4.2.3 Glosse Die Glosse eines Wikipedia-Artikels wird oft als „Wörterbuch-ähnliche Definiti- on“ charakterisiert [71], die jeder Wikipedia-Artikel besitzen sollte. Laut Wikipedia- Guidelines27 sollte der erste Paragraph das Konzept definieren. Als Beispiel betrachten wir die Glosse des Wikipedia-Artikel für „Automobile“: „Ein Automobil, kurz Auto (auch Kraftwagen, früher Motorwagen), ist ein traditionell mehrspuriges Kraftfahrzeug, das von einem Motor angetrieben wird und zur Beförderung von Personen und Frachtgütern dient. Motorisierte Wagen lösten in nahezu allen Bereichen die von Zugtieren gezogenen Fahrwerke ab, da sie deutlich schneller und weiter fahren und eine höhere Leistung erbringen können. Dieser Vorteil entwickelte sich schließlich zu mehr Transporten, einem massiv gestiegenen Raumbedarf und markanten Umweltproblemen. Dies, obwohl der Verbrennungsmotor mitnichten der Antrieb der ersten Stunde war: 1900 verkehrten in den USA 40 Prozent der Automobile mit Dampf, 38 Prozent elektrisch und nur 22 Prozent fuhren mit Benzin. Der weltweite Fahrzeugbestand steigt kontinuierlich an und lag im Jahr 2007 bei rund 918 Millionen Fahrzeugen.“ Abhängig vom Interesse des Lesers kann er sich mit dieser Definition zufrieden geben oder den Artikel weiterlesen, um weitere Details zu erfahren. 2.4.2.4 Infoboxen Infoboxen sind kleine Tabellen, die die Eckpunkte von bestimmten Wikipedia-Artikeln zusammenfassen. Infoboxen gibt es für geographische Einheiten (Kontinente, Länder, Städte, Gemeinden etc), Lebewesen (Pflanzen, Tiere etc) und andere Artikeltypen (Ber- ge, Bands, chemische Elemente etc). Die Infobox des Wikipedia-Artikels „Entenvögel“ wird in Abb. 10 gezeigt. Infoboxen lassen sich aufgrund ihrer maschinenlesbaren Form gut für NLP-Applikationen nutzen, wie das Beispiel DBPedia [11] (siehe 3.2.3) zeigt. Abbildung 10: Infobox des Wikipedia-Artikels: „Entenvögel“ 27 http://en.wikipedia.org/wiki/Wikipedia:Lead_section - Zugriff am 14.11.2012 http://en.wikipedia.org/wiki/Wikipedia:Lead_section 2.4 wikipedia 23 2.4.2.5 Kategorien In Wikipedia gehört jeder Artikel mindestens einer Kategorie an. Die Zugehörigkeit zu einer oder mehreren Kategorien wird mit Hilfe eines Kategorie-Abschnitts am Ende eines Artikels dargestellt, siehe Abbildung 11. Kategorien stellen eine Gruppe von Artikeln zu einem bestimmten Thema dar. Beispielsweise entwählt die Katego- rie „Darmstadt“28 sowohl mit Darmstadt verwandte Artikel wie „Kommunalpolizei Darmstadt“29, „Luisencenter“30 oder das „Darmstädter Zentrum für IT-Sicherheit“31. Darüber hinaus enthalten sie auch mit Darmstadt verwandte Unterkategorien wie „Bauwerk in Darmstadt“32, „Stadtteil von Darmstadt“33 oder „Unternehmen (Darm- stadt)“34. Unterkategorien dürfen wiederum weitere Artikel oder Kategorien beinhal- ten. Abbildung 11: Kategorien-Abschnitt des Wikipedia-Artikels „Darmstadt“ Der Unterschied zwischen Artikeln und Kategorien in Wikipedia kann anhand des Artikels und der Kategorie „Darmstadt“ dargestellt werden. Während der Artikel Darmstadt die Stadt Darmstadt selbst darstellt, ist die Kategorie Darmstadt eine An- sammlung von Artikeln und Unterkategorien, die mit der Stadt Darmstadt verwandt sind. Kategorien und ihre Ober- und Unterkategorien lassen sich als gerichteter Graph (ähnlich wie in Abschnitt 2.4.2.2) darstellen. Der resultierende Graph wird Kategorien- graph genannt. Die Kanten im Graph werden durch Kategorienpaare dargestellt, die Links genannt werden. Verfeinerungslinks (engl. Refinement Links) werden in Wikipe- dia verwendet, um andere Kategorien zu organisieren [118]. Verfeinerungslinks haben normalerweise die Form „X nach Y“ oder „X als Y“, wobei „X“ und „Y“ beliebige Begriffe darstellen können. Ein Beispiel wäre der Verfeinerungslink „Geographie nach Epoche“. Dieser Link fasst alle Kategorien zusammen, die mit Geographie zu tun haben und strukturiert die hier sich befindenden Kategorien und Artikel nach der Epoche, in der sie stattgefunden haben. Als Beispiel sieht man in Abb. 12 einen Ausschnitt des Kategoriengraphs. Der Kategoriengraph ist keine reine Taxonomie, da nicht nur Hyponymie-Beziehungen enthalten sind, sondern weitere semantische Relationen. Voess [158] bezeichnet den Kategoriengraph als Thesaurus aufgrund der Tatsache, dass Kategorien zu mehreren Kategorien gehören können. Andere Autoren wie Hammwöhner [52] sehen den Kate- goriengraph als strukturiertes Vokabular, mit dem Wikipedia-Artikel verschlagwortet werden können. 28 http://de.wikipedia.org/wiki/Kategorie:Darmstadt - Zugriff am 14.11.2012 29 http://de.wikipedia.org/wiki/Kommunalpolizei_Darmstadt - Zugriff am 14.11.2012 30 http://de.wikipedia.org/wiki/Luisencenter - Zugriff am 14.11.2012 31 http://de.wikipedia.org/wiki/Darmst%C3%A4dter_Zentrum_f%C3%BCr_IT-Sicherheit - Zugriff am 14.11.2012 32 http://de.wikipedia.org/wiki/Kategorie:Bauwerk_in_Darmstadt - Zugriff am 14.11.2012 33 http://de.wikipedia.org/wiki/Kategorie:Stadtteil_von_Darmstadt - Zugriff am 14.11.2012 34 http://de.wikipedia.org/wiki/Kategorie:Unternehmen_%28Darmstadt%29 - Zugriff am 14.11.2012 http://de.wikipedia.org/wiki/Kategorie:Darmstadt http://de.wikipedia.org/wiki/Kommunalpolizei_Darmstadt http://de.wikipedia.org/wiki/Luisencenter http://de.wikipedia.org/wiki/Darmst%C3%A4dter_Zentrum_f%C3%BCr_IT-Sicherheit http://de.wikipedia.org/wiki/Kategorie:Bauwerk_in_Darmstadt http://de.wikipedia.org/wiki/Kategorie:Stadtteil_von_Darmstadt http://de.wikipedia.org/wiki/Kategorie:Unternehmen_%28Darmstadt%29 24 grundlagen Abbildung 12: Kategoriengraph von der Hauptkategorie zur Kategorie „Darmstadt“ 2.4 wikipedia 25 2.4.2.6 Begriffsklärungsseiten Begriffsklärungsseiten (Disambiguierung) werden dazu benutzt, mehrdeutige Begriffe voneinander zu unterscheiden. Wenn ein Benutzer nach einem Wort mit mehre- ren Bedeutungen sucht, wird er zu einer Begriffsklärungsseite weitergeleitet. Von dieser Seite aus kann der Benutzer weiter zum gewünschten Artikel navigieren. Bei- spielsweise leitet die Suche nach „Ente“ zu der Begriffsklärungsseite „Ente“35 (siehe Abb. 13) weiter. Bei Begriffen mit mehreren Bedeutungen wird ein Hinweis auf die Mehrdeutigkeit am oberen Rande des Artikels platziert. Abbildung 13: Begriffsklärungsseite: Ente 2.4.2.7 Weiterleitungsseiten Weiterleitungsseiten, wie der Name es schon andeutet, leiten von einem Wikipedia- Artikel zu einem anderen. Der Weiterleitungsartikel selbst hat keinen Inhalt, sondern besteht aus einem Wikilink, der zum Ziel-Artikel führt. Beispielsweise gibt es die Weiterleitungsseite „Enten“ (siehe Abb. 14), die zum Artikel „Entenvögel“36 führt. Weiterleitungsseiten gibt es nicht nur für Pluralseiten, sondern auch für technische Fachbegriffe, Falschschreibungen sowie alternative Schreibweisen. 35 http://de.wikipedia.org/wiki/Ente - Zugriff am 14.11.2012 36 http://de.wikipedia.org/wiki/Entenv%C3%B6gel - Zugriff am 14.11.2012 http://de.wikipedia.org/wiki/Ente http://de.wikipedia.org/wiki/Entenv%C3%B6gel 26 grundlagen Abbildung 14: Weiterleitungsseite: Ente 2.4.2.8 Andere Elemente der Wikipedia In Wikipedia gibt es außerdem folgende Seiten: • Hilfeseiten, die Informationen zur Benutzung und Bedienung der Wikipedia enthalten. • Benutzerseiten37, auf denen sich registrierte Autoren vorstellen dürfen. Auf Benutzerseiten wird außerdem angegeben, ob ein Benutzer auch Administrator- rechte hat. • Spezialseiten38, die einen Überblick über den aktuellen Zustand der Wikipedia geben. Beispielsweise definieren diese Seiten, was auf Benutzerseiten stehen darf. • Vorlageseiten, die vorgefertigte Seiten und Beispiele zur schnellen und einheitli- chen Erstellung von Artikeln und Seiten enthalten. 37 http://de.wikipedia.org/wiki/Spezial:Benutzer - Zugriff am 14.11.2012 38 http://de.wikipedia.org/wiki/Hilfe:Spezialseiten - Zugriff am 14.11.2012 http://de.wikipedia.org/wiki/Spezial:Benutzer http://de.wikipedia.org/wiki/Hilfe:Spezialseiten 3 V E RWA N D T E A R B E I T E N »Wir sind gleichsam Zwerge, die auf den Schultern von Riesen sitzen, um mehr und Entfernteres als diese sehen zu können - freilich nicht dank eigener scharfer Sehkraft oder Körpergröße, sondern weil die Größe der Riesen uns zu Hilfe kommt und uns emporhebt.« — Bernhard von Chartres Bevor in Kapitel 4 eine Analyse des Anwendungsszenarios des Ressourcen- basierten Lernens in Online Communities erfolgt, die offenen Herausforderun- gen bestimmt und ein Konzept vorgestellt werden, soll an dieser Stelle ein Überblick über verwandte Arbeiten gegeben werden. Zuerst soll auf Empfehlungssysteme und auf ihren Einsatz im E-Learning eingegangen werden. Danach werden im zweiten Teil verschiedene Ansätze zur automatischen Wissensextraktion behandelt. Dabei liegt der Schwerpunkt auf Verfahren, die Wikipedia als Korpus benutzen, da Wikipedia auch im Rahmen dieser Arbeit für die Wissensextraktion benutzt wird. 3.1 verwandte arbeiten im bereich empfehlungssysteme Empfehlungssysteme sind Werkzeuge und Techniken, die dem Benutzer eines Soft- waresystems Objekte oder Items vorschlagen [131]. Sie werden benutzt, um Benutzer bei ihren Entscheidungen zu unterstützen wie z.B. beim Kauf von Büchern, bei der Musikauswahl oder der Suche von relevanten Nachrichten im Netz. In diesem Ka- pitel werden die grundlegenden Ideen und Verfahren von Empfehlungssystemen behandelt. 3.1.1 Grundlagen zu Empfehlungssystemen Seit Mitte der neunziger Jahre [130], als die ersten Beiträge zu Empfehlungssystemen publiziert wurden, gibt es ein wachsendes Interesse an solchen Systemen, das bis heute ungebrochen ist [28]. Insbesondere werden sie in solchen Anwendungen eingesetzt, in denen sehr viele Items zur Verfügung stehen. Das gilt beispielsweise für soziale Netzwerke oder Communities. Empfehlungssysteme zielen darauf ab, Benutzern zu helfen, relevante Items aus einer großen Menge von Items zu finden [27]. Items können Ressourcen aller Art sein: Filme, Lieder, Bücher, Webseiten, Nachrichten, Restaurants, Hotels oder Mode. Heutzutage gibt es aber auch Empfehlungssysteme, die Benutzer [72, 125] oder andere anwendungsspezifische Items wie Tags [69] oder Gruppen [110] empfehlen. Um relevante Empfehlungen für einen gegebenen Benutzer zu berechnen, greifen Empfehlungssysteme zumeist auf die historischen Daten von Benutzern zurück. Typischerweise wird bei Empfehlungssystemen zwischen den folgenden vier Typen von Ansätzen unterschieden: • Kollaboratives Filtern 27 28 verwandte arbeiten • Inhaltbasiertes Filtern • Wissensbasiertes Filtern • Hybrides Filtern An dieser Stelle soll ein Überblick über die Stärken und die Schwächen der ver- schiedenen Typen gegeben werden. Anschließend wird ein Blick auf offene Heraus- forderungen im Zusammenhang mit Empfehlungssystemen geworfen und analysiert, wie sich die verschiedenen Typen für eine Verwendung im E-Learning eignen. 3.1.1.1 Kollaboratives Filtern Diese Art von Empfehlungssystemen stützt sich grundsätzlich auf die Vorlieben der Nutzer, um Listen von Empfehlungen zu generieren. Kollaboratives Filtern [48, 57, 140] erfolgt grob in drei Schritten: Im ersten Schritt werden die Vorlieben und die Präferenzen der verschiedenen Benutzer aus ihrem bisherigen Verhalten identifiziert und anschließend werden sogenannte Nachbarschaften gebildet. Eine Nachbarschaft besteht aus ähnlichen Benutzern (bei Benutzer-basierten Ansätzen) oder ähnlichen Items (bei Item-basierten Ansätzen) [27]. Der letzte Schritt besteht darin, Benutzern Items von anderen Benutzern aus seiner Nachbarschaft anzubieten, die er noch nicht kennt bzw. Items aus der Nachbarschaft der Items des Benutzers. Aufgrund ihrer Einfachheit und Effizienz ist sie eine der verbreitetsten Empfehlungstechniken. Darüber hinaus braucht kollaboratives Filtern keine Informationen über den Inhalt bzw. Bedeutung des Items. Es sind nur die Beziehungen zwischen den Nutzern und Ressourcen von Bedeutung. Nachteile des kollaborativen Filterns sind die Tatsachen, dass eine große Benutzer-Community nötig ist, das cold-start Problem [142] für neue Benutzer und Elemente besteht und das Data-Sparsity Problem [141]. Das cold-start Problem bezeichnet die Situation, wenn ein neuer Nutzer oder eine neue Ressource in die Anwendung hinzukommen. Es lassen sich nicht sofort Empfehlungen generieren, da keine oder wenige Daten über ihn/sie bekannt sind. Auf kollaborativem Filtern basierende Empfehlungssysteme neigen dazu, die beliebtesten Items zu empfehlen, was dazu führt, dass Empfehlungen Richtung Mainstream verfälscht werden. Das Data-Sparsity Problem tritt auf, wenn die vorhandenen Informationen nicht ausreichen, um eine geeignete Nachbarschaft eines Benutzers zu bilden. 3.1.1.2 Inhaltbasiertes Filtern Inhaltbasierte Empfehlungssysteme [113] berücksichtigen für die Empfehlungen nur Informationen über die Benutzer und den Inhalt der Ressourcen. Meistens liegen diese Informationen in textueller Form, wie z.B. als Stichworte oder Beschreibun- gen der Items, vor. Empfehlungssysteme, die auf inhaltbasiertem Filtern aufbauen, suchen automatisch nach Items mit ähnlichen Beschreibungen und empfehlen die- se. Diese Art von Empfehlungen hat den Vorteil, dass sie weder auf eine große Benutzer-Community noch auf eine große Profilgeschichte angewiesen ist. Darüber hinaus gibt es das cold-start Problem für neue Items nicht. Das cold-start Problem für Benutzer besteht dagegen immer noch. Nachteilig ist, dass es zusätzliche Informa- tionen über den Benutzer braucht (i.d.R. die Interessen des Benutzers) und einen Zugriff auf den Inhalt bzw. die Beschreibung der Items (Metadaten). Bei großen Datenmengen erhöht sich die Zeitkomplexität von Empfehlungssystemen aufgrund 3.1 verwandte arbeiten im bereich empfehlungssysteme 29 der notwendigen Vorverarbeitung und Bearbeitung der textuellen Informationen ent- sprechend. Beispielsweise müssen u.a. die Wörter im textuellen Inhalt der Items auf ihre Wortstämme zurückgeführt werden, bevor sie mit anderen Wörtern verglichen werden. 3.1.1.3 Wissensbasiertes Filtern Wissensbasiertes Filtern [25, 101] bezeichnet den Prozess der Generierung von Emp- fehlungen auf Basis einer externen Wissensbasis. Diese Wissensbasen umfassen oft Benutzeranforderungen, Item-Eigenschaften und zusätzliches domänenspezifisches Wissen (z.B. in Form von Taxonomien und Ontologien). Dieses externe Wissen kann vom Empfehlungssystem ausgenutzt werden, um Zusammenhänge zwischen Benut- zer oder Items zu erkennen und auf dieser Basis Benutzer oder Items zu empfehlen. Ein Beispiel für diese Art von Empfehlungssystemen ist das sogenannte Ontological Filtering [65]. Damit werden Techniken genannt, die Taxonomien und Ontologien benutzen, um Ähnlichkeiten [89] oder semantische Relationen [104] zwischen Items zu finden. In diesem Zusammenhang spricht man auch über constraint-based wis- sensbasiertes Filtern, worin vordefinierte Empfehlungsregeln bestimmt werden und case-based wissensbasiertes Filtern, wo mit Hilfe von Taxonomien und Ontologien und einer Distanzfunktion Ähnlichkeiten zwischen Items berechnet werden. Constraint- based wissensbasierte Empfehlungssysteme bestehen aus einem eindeutig definierten Satz von Empfehlungsregeln, die nacheinander angewendet werden [47] und case- based wissensbasierte Empfehlungssysteme beinhalten, wie der Name es schon sagt, fallbezogene Regeln, die aus dem vergangenen Verhalten und aus den Wissensbasen abgeleitet werden [86]. Empfehlungssysteme, die auf wissensbasierten Filtern beruhen, eignen sich be- sonders für die Empfehlung von komplexen Items mit vielen Eigenschaften (z.B. Video-Kameras oder Autos). Vorteile dieser Empfehlungssysteme sind das externe Wissen, das in die Empfehlungen einfließt, die Behebung des cold-start Problems und dass Änderungen der Präferenzen eines Nutzers sofort berücksichtigt werden können. Die Nachteile haben meistens mit der benutzten Wissensbasis zu tun: Wie gut passt die Wissensbasis zum Szenario? Was passiert, wenn kein Wissen zu einem Produkt vorhanden ist? Was passiert, wenn Item-Eigenschaften in verschiedenen Sprachen vorliegen? 3.1.1.4 Hybrides Filtern Hybrides Filtern bezeichnet die Kombination verschiedener Datenquellen und Emp- fehlungssystemansätzen. Dabei unterscheidet man zwischen parallelisiertem hybridem Filtern (Empfehlungssysteme werden parallel ausgeführt und anschließend werden die Ergebnisse zusammengeführt), pipelined hybridem Filtern (Empfehlungssyste- me werden nacheinander ausgeführt, wobei nachfolgende Empfehlungssysteme die Empfehlungsliste der vorherigen Empfehlungssysteme kennen) und monolithischem hybridem Filtern (das monolithische hybride Empfehlungssystem entsteht durch Kombination von Ansätzen und Eigenschaften von verschiedenen Empfehlungssyste- men). 30 verwandte arbeiten 3.1.2 Empfehlungssysteme im E-Learning Die ersten Empfehlungssysteme für E-Learning wurden ca. 2003 entwickelt. Es besteht in der Forschung die Übereinkunft, dass sich kommerzielle Empfehlungssysteme nicht einfach auf E-Learning-Systeme transferieren lassen. Tang und McCalla [95, 155, 156] zeigten, dass Empfehlungen, die nur auf Vorlieben der Benutzer beruhen (wie es bei kommerziellen Empfehlungssystemen der Fall ist), oft nicht die pädagogisch wertvollsten sind und dass sich das Ziel, die Rolle und der Kontext eines Benutzers während des Lernens ändern können. Drachsler zählt in [39] verschiedene Kriterien auf, die Empfehlungssysteme in E-Learning berücksichtigen sollten: • Das Lernziel der Lernenden • Das Vorwissen der Lernenden (z.B. Anfänger, Fortgeschrittene, Experten) • Die Eigenschaften der Benutzer • Erfahrungen von anderen Benutzern • Lernstrategien von Lernenden In den letzten Jahren sind aus diesem Grund verschiedene Empfehlungssysteme [39, 93] entwickelt worden, die diesen Anforderungen oder Teilen dieser Anforderungen genügen. Leider sind viele dieser Ansätze nicht über die Entwicklung von Prototypen hinausgekommen und nicht in umfassend genutzte Anwendungen integriert worden. Im Folgenden soll ein Überblick über existierende Systeme gegeben werden. 3.1.2.1 Auf kollaborativen Filtern basierende Verfahren Eines der ersten personalisierten Empfehlungssysteme für E-Learning-Systeme wurde von Recker und Walker [124, 161] entwickelt. Sie verwendeten kollaboratives Filtern und haben untersucht, wie eine Lerncommunity vom Feedback von Lernenden profi- tieren kann. Tang und McCalla [95, 155, 156] entwickelten ein E-Learning-System, das auf kollaborativen Filtern basierend in der Lage ist, Ressourcen aus dem Web und von spezifischen Anwendungen zu empfehlen. Die Autoren zielten darauf ab, sowohl das Vorwissen als auch die Eigenschaften des Lernenden auszunutzen. Rafaeli et al. [121, 122] haben sich mit der Frage beschäftigt, wie die Zusammenarbeit und die Bildung von Lerngruppen mit Hilfe von kollaborativem Filtern zu fördern ist. Dabei können Lernende entscheiden, ob sie automatisch generierte Empfehlungen oder Empfehlungen von Freunden haben wollen. In [40] hat Dron ein Empfehlungsver- fahren entwickelt, das auf kollaborativem Filtern in mehreren Dimensionen besteht. Beispielsweise wird nicht nur berücksichtigt, ob ein Lernender eine Ressource gut ge- funden hat, sondern auch andere Eigenschaften wie die Verständlichkeit, die Eignung für Anfänger oder die Art, wie sie geschrieben wurde. Verfahren, die auf kollaborativem Filtern basieren, eignen sich häufig nicht für E-Learning-Systeme, da sie auf die Verfügbarkeit von großen Datensätzen angewiesen sind. Dies ist im E-Learning meistens nicht der Fall. Einer der Gründe ist die Tatsache, dass viele Systeme für Schulklassen, Lernkurse oder Lehrveranstaltungen mit be- grenzten Teilnehmerzahlen konzipiert sind. Darüber hinaus muss ein Lernender viele eigene Ressourcen gefunden haben, bevor Empfehlungen gebildet werden können. 3.1 verwandte arbeiten im bereich empfehlungssysteme 31 Für das Lernen bedeutet dies, dass gerade beim Beginn einer Recherche bzw. eines Lernprozesses keine Empfehlungen gemacht werden können. 3.1.2.2 Auf inhaltbasiertem Filtern basierende Verfahren Die meisten auf inhaltbasierten Filtern basierende Empfehlungssysteme werden mit anderen Verfahren kombiniert (siehe 3.1.2.4). Dieser Umstand hat mehrere Gründe: Inhaltbasierte Verfahren arbeiten in der Regel daraufhin, ähnliche Ressourcen (vgl. [12, 96, 168]) zu empfehlen. In Anwendungsbereiche, wo die Ähnlichkeit von Objekten eine Rolle spielt, wie z.B. Biotechnologie [114], Geoinformatik [66] oder Linguistik [112], ist dies sehr nützlich. Im E-Learning aber hat dieser Anwendungsfall nur Sinn, wenn Lernende sich für ein spezifisches Thema interessieren, unabhängig von anderen Interessen und Präferenzen. Wenn es aber z.B. darauf ankommt, sich in ein Thema zu vertiefen, reicht die reine Suche nach ähnlichen Ressourcen nicht aus. Schließlich leidet inhaltbasiertes Filtern, genau wie beim kollaborativen Filtern, unter dem cold-start Problem. 3.1.2.3 Auf wissensbasierten Filtern basierende Verfahren Auf wissensbasierten Filtern basierende Verfahren lassen sich in drei Kategorien einordnen: Die erste Kategorie von Verfahren setzt darauf, Kompetenzen von Lernenden und Lernkursen als Ontologie zu modellieren, um auf diese Weise Empfehlungen machen zu können. Zu diesem Verfahrenstyp gehören die Ansätze von Shen et al. [149], Manouselis et al. [92] und Aehnelt [4]. Shen et al. haben basierend auf einer Ontologie und auf Ablaufregeln (engl. senquencing rules) ein Verfahren zur Empfehlung von Lernobjekten entwickelt. Das System berechnet die Kompetenz von Lernenden und schlägt Lernobjekte vor, sodass Lernende ihre Kompetenz erhöhen können. Dieses Verfahren setzt eine Modellierung von Kompetenzen voraus, was im Ressourcen- basierten Lernen aufgrund der vielen möglichen Themen und Kompetenzen nicht machbar ist. Manouselis et al. versuchen einen ähnlichen Ansatz. Sie benutzen Onto- logien von Lernkursen zu einem Thema, um Lernende durch verwandte Konzepte zu führen. Zusätzlich werden die Präferenzen der Lernenden und die Erfahrungen von ähnlichen Benutzern verwendet. Aehnelt schlägt Empfehlungssysteme für Benutzer vor, die auf eine Modellierung von Lernenden und ihren Kompetenzen beruhen. Dieses Empfehlungssystem berechnet den Bedarf an Wissen von Lernenden auf der Basis von historischen Daten von anderen Lernenden. Die zweite Kategorie umfasst Ansätze, die darauf abzielen, mögliche Lernpfade zu empfehlen. Dazu gehören die Ansätze von Janssen [68] und Huang et al. [63]. Janssen präsentierte ein Verfahren, das auf der individuellen Lernhistorie beruhend zukünftige Schritte im Lernprozess empfiehlt und Huang et al. versuchen Gruppenlernpfade mit Hilfe von Markov-Ketten zu erkennen. Diese stellen die Wahrscheinlichkeit des Übergangs von einem Lernobjekt zu einem anderen dar. Darüber hinaus wird ein weiteres statistisches Modell benutzt, um neue (unbekannte Pfade) zu erkennen. Schließlich gibt es die dritte Kategorie von Verfahren, die auf die Modellierung von Lernenden setzt. Khribi et al. [74] greifen auf die Bildung von Benutzerprofilen zurück. Zusätzlich berechnen Sie Ähnlichkeiten zwischen Präferenzen von Lernenden und ihrem Kontext, um hybride Empfehlungslisten (basierend auf kollaborativem Filtern und inhaltbasierten Verfahren) zu erstellen. Jie [70] hat ein personalisiertes 32 verwandte arbeiten Empfehlungssystem vorgeschlagen. Das System ist in der Lage, abhängig vom Lernstil, Lerntempo und Hintergrundwissen, geeignete Lernmaterialien zu empfehlen. Chen et al. [29] entwickelten ein Empfehlungssystem für Lernkurse, wofür sie Lernprofile bilden (Präferenzen, Interessen und Lernverhalten). Die Empfehlungen hängen dann von den Fähigkeiten der Lernenden ab. Wie man hier sehen kann, wurden bis heute viele wissensbasierte Verfahren für das Anwendungsszenario E-Learning entwickelt. Diese Ansätze haben gemeinsam, dass sie auf vorgefertigte Ontologien oder Wissen über das Szenario zurückgreifen wie die Modellierung von Kompetenzen oder der Benutzer. Diese Tatsache macht frühere Ansätze für das Ressourcen-basierte Lernen nicht nutzbar, da Ressourcen-basiertes Lernen für das Lernen aller möglichen Themen benutzt werden kann, sodass sich keine Kompetenzen modellieren lassen. 3.1.2.4 Auf hybridem Filtern basierende Verfahren Anderson et al. [5] kombinierten kollaboratives Filtern mit zusätzlichen festen Re- geln bzw. Heuristiken, um die Empfehlung von Audio-Lernobjekten zu unterstützen. Die Regeln wurden mit Hilfe einer Domäneontologie definiert und zielen darauf ab, Schwächen des kollaborativen Filterns auszugleichen. Beispielsweise tauchen vertraute Lernobjekte in Empfehlungslisten höher als völlig unbekannte Lernobjekte auf. Koutrika et al. [79] definierten sogenannte flexible Empfehlungen, die mit Hil- fe von Operatoren (Filter oder Empfehlungen) gebildet werden können. Abhängig vom Benutzer können inhaltbasierte oder kollaborative Empfehlungen vorgeschlagen werden. Santos [139] schlägt einen hybriden Ansatz vor, der kollaboratives Filtern mit inhaltbasierten Verfahren kombiniert. Dieses Empfehlungssystem setzt Eingaben von Lernenden (Präferenzen, Bewertungen, etc., die das Benutzerprofil bilden) und Lehrenden (Generische Empfehlungen und Annotationen von Ressourcen) voraus. Abhängig von diesen Eingaben des Kontextes (Lernkurs) werden Empfehlungen ge- neriert. Hsu [62] präsentierte ein personalisiertes Online-Empfehlungssystem für die englische Sprache. Empfehlungslisten entstehen aus Kombination von inhaltbasiertem und kollaborativem Filtern zusammen mit weiteren Data-Mining-Techniken. Ziel ist es, geeignete Englischkurse zu empfehlen, in denen Lernende je nach Verhalten in Clustern zusammengefasst werden. 3.1.2.5 Zusammenfassung Im Gegensatz zu den kommerziellen Anwendungen werden rein kollaborative oder rein inhaltbasierte Empfehlungssysteme im E-Learning nur in geringem Maße verwen- det. Im E-Learning werden eher wissensbasierte und hybride Empfehlungsverfahren benutzt. Dabei spielt je nach Anwendungsszenario die Modellierung von (Themen-, Lernkurse- oder Kompetenzen-) Ontologien eine große Rolle. Diese ist möglich, weil es sich um geschlossene Szenarien handelt. Dagegen ist das Ressourcen-basierte Lernen sehr offen und kann für die verschiedensten Themenbereiche, Kurse und Lernende benutzt werden. Somit würde eine Modellierung von Kompetenzen, Lernen- den oder Kursen nur einem kleinen Teil der Lernenden zugutekommen. Bestehende Verfahren lassen sich im Ressourcen-basierten Lernen daher eher nicht anwenden. Im nachfolgenden Kapitel 4 erfolgt daher eine genaue Analyse des Anwendungsszenari- os am Beispiel einer Plattform zur Unterstützung des Ressourcen-basierten Lernens und die in dieser Plattform integrierten Empfehlungssysteme. 3.2 verwandte arbeiten im bereich wissensextraktion 33 3.2 verwandte arbeiten im bereich wissensextraktion Das im Rahmen dieser Arbeit entwickelte Konzept zur Unterstützung des Ressourcen- basierten Lernens in Online-Communities basiert auf einem wissensbasierten Emp- fehlungssystem, das die mit Hilfe einer Taxonomie generierten zusätzlichen Infor- mationen verwendet, um weitere Items zu empfehlen. Dazu werden in dieser Arbeit zwei Verfahren vorgestellt, die die Taxonomie auf Basis der Wikipedia extrahieren. Die Extraktion von strukturiertem Wissen und dessen Bereitstellung in maschinen- lesbarer Form steht im Vordergrund bei vielen Anwendungen aus dem Gebiet des Natural Language Processing. In diesem Abschnitt soll ein Überblick über bestehende Ansätze zur Extraktion von Taxonomien und Ontologien gegeben werden. Zuerst sollen manuell erzeugte Wissensquellen behandelt werden, danach wird auf automa- tische Verfahren eingegangen. Abschließend werden Ansätze, die auf der Wikipedia basieren, diskutiert. 3.2.1 Manuell erstellte Wissensbasen Die ersten existierenden umfassenden Wissensbasen (Das Wort Wissensbasis wird aus dem Englischen knowledge base abgeleitet und bezeichnet alle maschinenlesbaren Wissensquellen wie Taxonomien, Thesauri oder Ontologien) wurden manuell erstellt. Ziel war es, möglichst große Menge an Wissen bei entsprechender hoher Qualität zur Verfügung zu stellen. Einer der populärsten manuell erzeugten Vertreter ist das Projekt WordNet [102]. WordNet ist ein semantisches Netz für die englische Sprache. Der Erfolg von WordNet hat gezeigt, dass Wissensbasen für die unterschiedlichs- ten Anwendungen benutzt werden können. Beispiele für eine Nutzung sind die Sinn-Erkennung von Wörtern [81], die Berechnung der semantischen Ähnlichkeit zwischen Begriffen [24] oder die Sentiment Detection, also die Extraktion von sub- jektiven Informationen aus Texten [6]. WordNet besteht aus sogenannten Synsets. Jedes Synset repräsentiert ein Konzept und besteht aus verschiedenen Wörtern, die die gleiche Bedeutung haben [152]. Beispiele für Synsets sind {Apfelsine,Orange} oder {öffen,aufmachen}. Wie man an diesem Beispiel sieht, können diese „Wörter“ nicht nur Substantive, sondern auch Verben, Adjektive und Adverbien sein. Weiter können polyseme Wörter, also Wörter mit mehreren Bedeutungen, wie z.B. „Bank“, in mehreren Synsets auftreten. WordNet definiert (abhängig vom Wort-Typ) verschie- dene semantische Relationen (siehe 2.3.3) für die Synsets. Ein weiteres Beispiel einer Wissensbasis für die englische Sprache ist Cyc [83]. Cyc verfolgt das Ziel eine umfas- sende Ontologie des menschlichen Wissens zu erstellen. Im Gegenteil zu WordNet wurde Cyc 1995 von einem Unternehmen (Cycorp1) erstellt. Aus diesem Grund gibt es erst seit 2002 Opencyc, eine öffentlich verfügbare leicht-abgespeckte Version und seit 2006 ResearchCyc, eine für den wissenschaftlichen Einsatz aufbereitete Version. Sie unterscheiden sich darin, dass ResearchCyc sowohl weitere semantische Beziehungen und ein umfangreicheres Lexikon als auch Schnittstellen zur Wissenserweiterung und -bearbeitung zur Verfügung stellt. Cyc besteht aus einer großen Anzahl an einfachen Regeln in Prädikatenlogik, die die verschiedenen Relationen zwischen Konzepten darstellen. 1 http://www.cyc.com/ - Zugriff am 14.11.2012 http://www.cyc.com/ 34 verwandte arbeiten Schließlich gibt es eine von einer Community manuell erstellte Wissensbasis, Free- base [20]. Freebase wurde von der Firma Metaweb2 entwickelt und später an Google3 verkauft. Bei Freebase wird das gesamte Wissen nicht durch Experten erstellt, sondern durch eine Menge von Freiwilligen, ähnlich wie bei Wikipedia. Allerdings gibt es bei Freebase zusätzlich eine strukturierte globale Wissensbasis. Aufgrund des WordNet-Erfolgs sind in den letzten Jahren ähnliche regionale Projekte zur Erstellung vergleichbarer semantischer Wissensbasen entstanden. Auf der Internet-Seite der Global WordNet Association4 findet sich ein Verzeichnis mit 69 existierenden Projekten. Viele dieser regionalen Projekte befinden sich leider immer noch in der Entwicklung oder sind nicht frei verfügbar. Für die deutsche Sprache gibt es GermaNet [53]. Dieses hat eine ähnliche Struktur wie WordNet: Neben Wörter- Synsets, die Namen, Verben oder Adjektive sein können, gibt es Relationen zwischen den Synsets. GermaNet enthält außerdem multilinguale Verweise zu EuroWordNet5. EuroWordNet ist ein Projekt für europäische Sprachen, das darauf abzielt, ähnliche Wissensbasen wie WordNet für alle europäischen Sprachen zu entwickeln. Darüber hinaus werden die einzelnen Wissensbasen mit Hilfe eines interlingualen Index miteinander verbunden [159]. 3.2.2 Automatische Extraktion von Wissensbasen Anstelle einer manuellen Erstellung von Wissensbasen versuchen viele Forscher das Wissen aus existierenden Korpora automatisch zu extrahieren [31]. Sie haben ver- schiedene Methoden entwickelt, um semantische Relationen zwischen Konzepten zu bestimmen. In der Regel bestehen diese Korpora aus einer Sammlung von Texten, die mit Hilfe verschiedener Methoden verarbeitet werden, um semantische Beziehungen zu erkennen. In diesem Abschnitt sollen diese verschiedenen Methoden und Ansätze gezeigt werden, die zur Erkennung von Hyponymien benutzt werden. Für einen Überblick, wie Ontologien automatisch erstellt und erweitert werden können, wird an dieser Stelle an Faatz [42] verwiesen. Aus der Erkennung von Hyponymien lässt sich eine Taxonomie erzeugen, die im Rahmen dieser Arbeit für das Em