TU Darmstadt / ULB / TUprints

Efficient Pairwise Multilabel Classification

Loza Mencía, Eneldo (2013)
Efficient Pairwise Multilabel Classification.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

[img]
Preview
Dissertation - Eneldo Loza Mencia: Efficient Pairwise Multilabel Classification - Text (Druckbares Online-PDF)
loza12diss.pdf - Published Version
Copyright Information: CC BY-NC-ND 2.5 Generic - Creative Commons, Attribution, NonCommercial, NoDerivs .

Download (2MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Efficient Pairwise Multilabel Classification
Language: English
Referees: Fürnkranz, Prof. Dr. Johannes ; Eyke, Prof. Dr. Hüllermeier
Date: 2013
Place of Publication: Darmstadt
Date of oral examination: 24 July 2012
Corresponding Links:
Abstract:

Multilabel classification learning is the task of learning a mapping between objects and sets of possibly overlapping classes and has gained increasing attention in recent times. A prototypical application scenario for multilabel classification is the assignment of a set of keywords to a document, a frequently encountered problem in the text classification domain. With upcoming Web 2.0 technologies, this domain is extended by a wide range of tag suggestion tasks and the trend definitely is moving towards more data points and more labels. This work provides an extended introduction into the topic of multilabel classification, a detailed formalization and a comprehensive overview of the present state-of-the-art approaches.

A commonly used solution for solving multilabel tasks is to decompose the original problem into several subproblems. These subtasks are usually easy to solve with conventional techniques. In contrast to the straightforward approach of training one classifier for independently predicting the relevance of each class (binary relevance), this work focuses particularly on the pairwise decomposition of the original problem in which a decision function is learned for each possible pair of classes. The main advantage of this approach, the improvement of the predictive quality, comes at the cost of its main disadvantage, the quadratic number of classifiers needed (with respect to the number of labels). This thesis presents a framework of efficient and scalable solutions for handling hundreds or thousands of labels despite the quadratic dependency.

As it turns out, training such a pairwise ensemble of classifiers can be accomplished in linear time and only differs from the straightforward binary relevance approach (BR) by a factor relative to the average number of labels associated to an object, which is usually small. Furthermore, the integration of a smart scheduling technique inspired from sports tournaments safely reduces the quadratic number of base classifier evaluations to log-linear in practice. Combined with a simple yet fast and powerful learning algorithm for linear classifiers, data with a huge number of high dimensional points, which was not amenable to pairwise learning before, can be processed even under real-time conditions.

The remaining bottleneck, the exploding memory requirements, is coped by taking advantage of an interesting property of linear classifiers, namely the possibility of dual reformulation as a linear combination of the training examples. The suitability is demonstrated on the novel EUR-Lex text collection, which particularly puts the main scalability issue of pairwise learning to test. With its almost 4,000 labels and 20,000 documents it is one of the most challenging test beds in multilabel learning to date. The dual formulation allows to maintain the mathematical equivalent to 8 million base learners needed for conventionally solving EUR-Lex in almost the same amount of space as binary relevance. Moreover, BR was clearly beaten in the experiments.

A further contribution based on hierarchical decomposition and arrangement of the original problem allows to reduce the dependency on the number of labels to even sub-linearity. This approach opens the door to a wide range of new challenges and applications but simultaneously maintains the advantages of pairwise learning, namely the excellent predictive quality. It was even shown in comparison to the flat variant that it has a particularly positive effect on balancing recall and precision on datasets with a large number of labels.

The improved scalability and efficiency allowed to apply pairwise classification to a set of large multilabel problems with a parallel base of data points but different domains of labels. A first attempt was made in this parallel tasks setting in order to investigate the exploitation of label dependencies by pairwise learning, with first encouraging results. The usage of multilabel learning techniques for the automatic annotation of texts constitutes a further obvious but so far missing connection to multi-task and multi-target learning. The presented solution considers the simultaneous tagging of words with different but possibly overlapping annotation schemes as a multilabel problem. This solution is expected to particularly benefit from approaches which exploit label dependencies. The ability of pairwise learning for this purpose is obviously restricted to pairwise relations, therefore a technique is investigated which explores label constellations that only exist locally for a subgroup of data points. In addition to the positive effect of the supplemental information, the experimental evaluation demonstrates an interesting insight with regards to the different behavior of several state-of-the-art approaches with respect to the optimization of particular multilabel measures, a controversial topic in multilabel classification.

Alternative Abstract:
Alternative AbstractLanguage

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.

German
Uncontrolled Keywords: multilabel classification, pairwise classification, efficiency, scalability, machine learning
Alternative keywords:
Alternative keywordsLanguage
Multilabel-Klassifizierung, Paarweise Klassifizierung, Effizienz, Skalierbarkeit, Maschinelles LernenGerman
URN: urn:nbn:de:tuda-tuprints-32260
Classification DDC: 000 Generalities, computers, information > 004 Computer science
Divisions: 20 Department of Computer Science
20 Department of Computer Science > Knowl­edge En­gi­neer­ing
Date Deposited: 04 Jul 2013 12:56
Last Modified: 09 Jul 2020 00:15
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/3226
PPN: 325491364
Export:
Actions (login required)
View Item View Item