Multilabel-Klassifizierung bezeichnet die Aufgabe, eine Zuordnung von Objekten zu Mengen von möglicherweise sich überlappender Klassen zu lernen. Dieses Feld hat in letzter Zeit stark an Aufmerksamkeit gewonnen. Ein praktisches Anwendungsszenario wäre die Zuweisung von Schlüsselwörtern zu Dokumenten. Ein Problem, das häufig im Gebiet der Text-Klassifizierung anzutreffen ist. Durch die aufkommenden Web 2.0 Technologien wird dieses Gebiet um eine Reihe von Szenarien erweitert welche sich hauptsächlich mit dem Empfehlen von Tags und Schlagwörtern konzentrieren. Der Trend geht dabei unausweichlich zu noch mehr Datenpunkten und noch mehr Labels. Die vorliegende Arbeit bietet eine umfassende Einleitung in das Thema Multilabel-Klassifizierung mit einer detaillierten Formalisierung und einer ausführlichen Erläuterung der aktuellen Verfahren, die den Stand der Technik repräsentieren.

Ein gängiges Verfahren, um Multilabel-Probleme zu lösen, stellt die Zerlegung des Originalproblems in mehrere Teilprobleme dar. Diese Teilaufgaben sind üblicherweise leicht mit konventionellen Techniken zu lösen. Im Vergleich zu der direkten Methode, dem Lernen eines Klassifizierers pro Klasse, der dann für jede Klasse unabhängig von den anderen die Relevanz vorhersagt (Binary Relevance), legt diese Arbeit ihren Schwerpunkt auf den Ansatz der paarweisen Zerlegung. Hierbei wird eine Entscheidungsfunktion für jedes Paar von Klassen gelernt. Der Hauptvorteil dieser Methode, die Verbesserung der Qualität der Vorhersagen, steht allerdings im Gegensatz zum Hauptnachteil, nämlich der quadratischen Anzahl von Klassifizierern. Diese Anzahl berechnet sich in Abhängigkeit der Anzahl der Labels. Diese Dissertation stellt ein Framework von effizienten und skalierbaren Lösungen für die Verarbeitung von hunderten und sogar tausenden von Labels vor, die trotz der quadratischen Abhängigkeit verarbeitet werden können.

Wie sich herausstellt, kann das Trainieren eines paarweisen Ensembles von Klassifizierern in linearer Zeit geschehen. Der Unterschied zum simplen Binary Relevance (BR) Verfahren beträgt hierbei nur einen kleinen Faktor, der der durchschnittlichen Zahl von assoziierten Labels pro Objekt entspricht. Zusätzlich konnte durch die Anwendung eines intelligenten und dynamischen Auswertungsschemas, inspiriert durch das System der Sport-Ligen, die quadratische Anzahl an Auswertungen von Basis-Klassifizierern auf eine in der Praxis log-lineare Abhängigkeit reduziert werden. Die Kombination mit einem einfachen aber schnellen und mächtigen linearen Klassifizierer erlaubte die Echtzeit-Verarbeitung von Daten mit sehr vielen, hoch-dimensionalen Datenpunkten. Eine Aufgabenstellung, die davor dem paarweisen Lernen nicht zugänglich war.

Der verbleibende Flaschenhals, die explodierenden Speicheranforderungen, wurde durch die Ausnutzung einer interessanten Eigenschaft von linearen Klassifizierern überwunden, nämlich die Möglichkeit der dualen Reformulierung als Linearkombination der Trainingsbeispiele. Die Tauglichkeit dieses Verfahrens wurde auf dem neuartigen Textdatensatz EUR-Lex demonstriert, welches insbesondere die Skalierbarkeit des paarweisen Ansatzes auf die Probe stellt. Mit seinen fast 4.000 Labels und 20.000 Dokumenten stellt EUR-Lex eine der anspruchsvollsten Testdatensätze für Multilabel-Lernen dar. Die duale Formulierung ermöglicht es, ein Modell im Speicher zu halten, welches den 8 Millionen Basislernern, die bei der konventionellen Lösung für EUR-Lex nötig wären, entspricht, und das beim gleichen Speicherbedarf wie Binary Relevance. Darüber hinaus wurde BR in den Experimenten klar geschlagen.

Ein weiterer Beitrag dieser Arbeit, basierend auf einer hierarchischen Zerlegung und Anordnung der Originalaufgabenstellung, ermöglicht sogar die Reduzierung der Abhängigkeit von der Anzahl der kleiner als linear. Dieser Ansatz öffnet einer großen Auswahl an neuen Herausforderungen und Anwendungen die Türen, aber es werden dabei auch die Vorteile des paarweisen Lernens beibehalten, nämlich die exzellente Qualität der Vorhersagen. Im Vergleich mit dem konventionellen, flachen Ansatz konnte sogar gezeigt werden, daß sich bei Problemen mit vielen Labels ein besonders positiver Effekt beim Ausbalancieren von Recall und Precision einstellt.

Die verbesserte Skalierbarkeit und Effizienz ermöglichte es, den paarweisen Ansatz auf eine Menge von großen Multilabel-Problemen anzuwenden, die alle eine gemeinsame, parallele Datenbasis aber unterschiedliche Domänen von Labels besitzen. Dieses Szenario von parallelen Tasks stellt einen ersten Schritt dar, die Fähigkeiten des paarweisen Ansatzes für die Ausnutzung von Label-Abhängigkeiten zu untersuchen, mit ersten vielversprechenden Ergebnissen. Die Verwendung von Multilabel-Verfahren für die automatische Annotation von Texten stellt eine weitere offensichtliche, aber bislang verkannte Verbindung zu Multi-Task und Multi-Target-Learning dar. In der vorgeschlagenen Lösung wird das gleichzeitige Markierung von Wörtern mit unterschiedlichen aber möglicherweise überlappenden Annotationsschemata als Multilabel-Problem betrachtet. Dieser Ansatz wird voraussichtlich von Verfahren, die Label-Abhängigkeiten berücksichtigen, profitieren können. Die Fähigkeit des paarweisen Ansatzes hierfür ist klarerweise auf paarweise Relationen beschränkt. Deshalb wird in dieser Arbeit eine Technik untersucht, die Konstellationen von Labels erforscht, die nur lokal in Untergruppen der Datenpunkte zu finden sind. Zusätzlich zu dem festgestellten positiven Effekt dieser zusätzlichen Informationen bietet die experimentelle Auswertung auch interessante Erkenntnisse über das unterschiedliche Verhalten von aktuellen Verfahren bezüglich der Optimierung und besonderen Bevorzugung von Multilabel-Evaluationsmaßes, ein kontroverses Thema im Gebiet der Multilabel-Klassifizierung.