Sequentielles Lernen mit I²VM

Der Hauptbeitrag dieser Arbeit ist die Entwicklung, Analyse und Evaluierung von inkrementellen Import Vector Machines (I²VM) für sequentielles Lernen. I²VM basiert auf den nicht-inkrementellen Import Vector Machines von Zhu und Hastie (2005) und ist ein kernel-basierter, diskriminativer Klassifikator. Seine Stärke liegt in der Fähigkeit, komplexe Datenverteilungen zu handhaben. Die Spärlichkeit des Klassifikators ermöglicht effizientes Training und Testen, zusätzlich liefert er probabilistische Ausgaben. Ein Kernpunkt der Arbeit ist der Nachweis und die Analyse der diskriminativen und rekonstruktiven Modellkomponenten von IVM und I²VM. Diskriminative Klassifikatoren trennen Klassen optimal, während rekonstruktive Komponenten die Datenverteilung approximieren, indem sie möglichst viele Informationen über die Daten erhalten. Beide Eigenschaften sind für einen leistungsfähigen inkrementellen Klassifikator unerlässlich. Ein weiterer wichtiger Aspekt ist die Formulierung der inkrementellen Lernstrategie für I²VM, welche das Hinzufügen und Entfernen von Datenpunkten sowie das Update der Modellparameter beinhaltet. Neue Klassen und Merkmale können hinzugefügt werden, wobei das Modell kontinuierlich angepasst, aber stabil und effizient gehalten wird. Die Motivation hinter dieser Arbeit ist die Entwicklung eines Klassifikators, der die Herausforderungen des sequentiellen Lernens bewältigt und dabei eine hohe Klassifikationsgenauigkeit, Effizienz und aussagekräftige Ergebnisse liefert.

Sequentielles Lernen bringt spezifische Herausforderungen mit sich. Die Daten sind zu einem gegebenen Zeitpunkt nicht vollständig verfügbar, und das Warten auf eine repräsentative Datenmenge ist oft unerwünscht und unpraktisch. Eine sofortige Klassifizierung der verfügbaren Daten ist notwendig, selbst wenn nicht alle Trainingsbeispiele vorliegen. Hinzu kommt, dass die Anzahl der sequenziell ankommenden Daten sehr groß oder sogar unendlich sein kann, was die Speicherung aller Daten unmöglich macht. Die Datenverteilung kann sich im Laufe der Zeit ändern (Concept Drift), und das Klassifikationsmodell muss gegenüber irrelevanter Information stabil, aber gegenüber neuen, relevanten Daten flexibel sein. Diese Aspekte, die für Batch-Lernalgorithmen problematisch sind, werden in dieser Arbeit durch die Entwicklung eines robusten inkrementellen Lernverfahrens adressiert. Der Fokus liegt auf der Erstellung eines maschinellen Lernalgorithmus, der speziell für sequentielles Lernen konzipiert ist und die sukzessive Verarbeitung von Daten handhabt, entweder weil die Aufgabe so angelegt ist oder der Zugriff auf die Daten keine andere Möglichkeit erlaubt. Die Daten kommen zeitlich versetzt an, einzeln oder in Batches (gleichzeitig ankommende Gruppen von Samples). Ein typisches Beispiel ist eine Videosequenz, wobei jedes Bild einen Batch darstellt. Sequentielles Lernen wird auch angewendet, wenn alle Daten verfügbar sind, aber sequenziell verarbeitet werden müssen (z.B. aufgrund von Speicherbeschränkungen).

Im Vergleich zum ursprünglichen IVM-Algorithmus von Zhu und Hastie (2005) wird hier eine hybride Vorwärts-/Rückwärtsstrategie verwendet. Diese fügt sukzessive Importvektoren hinzu, prüft aber gleichzeitig, ob bereits vorhandene Vektoren entfernt werden können. Dies führt im Gegensatz zu einer reinen Vorwärtsauswahl zu einem späreren und präziseren Modell. Um Endlosschleifen zu vermeiden, werden entfernte Vektoren für einige Iterationen von der erneuten Auswahl ausgeschlossen (Tabu-Suche). Eine weitere Modifikation betrifft die Bestimmung des Kernelparameters σ und des Regularisierungsparameters λ. Anstatt der Methode von Zhu und Hastie (mit schrittweiser Reduktion von λ), wird hier Gridsearch mit Kreuzvalidierung eingesetzt. Diese Vorgehensweise liefert in Experimenten, besonders bei wenigen Trainingsbeispielen, höhere Genauigkeiten. Die Parametersuche umfasst σ ∈ {2⁻³, 2⁻²,⁵, ..., 2⁴} und λ ∈ {exp(−12), exp(−11), ..., exp(−4)} bei einer 5-fachen Kreuzvalidierung. Der revidierte Algorithmus berücksichtigt auch die Herausforderungen des Sequentiellen Lernens: Die Verfügbarkeit von beschrifteten Trainingsdaten variiert, und Active Learning-Ansätze könnten notwendig werden, um die Beschriftung von unbeschrifteten Daten zu gewährleisten.

Sequentielles Lernen ist durch mehrere Herausforderungen gekennzeichnet. Zunächst ist die Datenverfügbarkeit nicht vollständig und zeitlich begrenzt. Das Warten auf repräsentative Datenmengen ist in der Praxis oft nicht praktikabel, insbesondere bei großen oder unendlich großen Datensätzen. Eine Klassifizierung muss daher zu jedem Zeitpunkt möglich sein, selbst wenn noch nicht alle Trainingsdaten vorliegen. Die begrenzte Speicherkapazität stellt eine weitere Herausforderung dar, da nicht alle ankommenden Daten gespeichert werden können. Schließlich ist die Datenverteilung nicht statisch und unterliegt einem Concept Drift, also einer Veränderung der zugrundeliegenden Verteilung über die Zeit. Ein robustes Klassifikationsmodell muss daher sowohl stabil gegenüber irrelevantem Rauschen als auch flexibel gegenüber relevanten Veränderungen in der Datenverteilung bleiben. Diese drei Punkte bilden die größten Hürden für die Entwicklung von effizienten und zuverlässigen Klassifikatoren im Kontext des sequentiellen Lernens. Die Notwendigkeit einer schnellen Anpassung an neue Daten, ohne dabei die Stabilität und Effizienz zu verlieren, ist für viele Anwendungen, von der Echtzeit-Bildverarbeitung bis hin zur Analyse großer Datenströme, entscheidend. Die Entwicklung eines Algorithmus, der diese Anforderungen erfüllt, ist das zentrale Ziel dieser Arbeit.

Um die Herausforderungen des sequentiellen Lernens zu bewältigen, werden inkrementelle Lernmethoden benötigt. Diese Methoden erfordern im Allgemeinen eine rekonstruktive Modellkomponente und sollten zusätzlich eine diskriminative Komponente aufweisen. Die rekonstruktive Komponente repräsentiert einen signifikanten Teilbereich der Datenverteilung und bietet Robustheit gegenüber der Sequenz der Datenpunkte, insbesondere bei vielen konkurrierenden Klassen. Sie ermöglicht die Anpassung an tatsächliche oder scheinbare Veränderungen der Datenverteilung, die als Concept Drifts wahrgenommen werden (intra- und inter-class Variabilität). Eine diskriminative Komponente ist zwar nicht zwingend erforderlich, aber empfehlenswert, um ähnliche Klassen effizient zu unterscheiden. Kernbasierte Lernmethoden haben sich zudem bei komplexen Datenverteilungen als effektiv erwiesen. Die Kombination aus diskriminativer und rekonstruktiver Komponente, in Verbindung mit einem effizienten, spärlichen Algorithmus, bildet die Grundlage des Lösungsansatzes. Diese Kombination soll gewährleisten, dass der Klassifikator sowohl die Klassen gut trennt als auch die Datenverteilung ausreichend repräsentiert, um robust gegenüber Concept Drift und unvollständigen Daten zu sein. Die Effizienz wird durch die Spärlichkeit des Modells erreicht, wodurch Speicherplatz und Rechenzeit gespart werden. Die Fähigkeit, Datenpunkte hinzuzufügen und zu entfernen, sowie Modellparameter anzupassen, ist zentral für den Umgang mit dynamischen Datenströmen.

Der vorgestellte Algorithmus basiert auf dem IVM von Zhu und Hastie (2005), wurde aber signifikant verbessert. Die wichtigste Änderung ist die Einführung einer hybriden Vorwärts-/Rückwärtsstrategie zur Auswahl der Importvektoren. Im Gegensatz zum ursprünglichen Ansatz, der nur Importvektoren hinzufügt (Vorwärtsselektion), erlaubt dieser neue Ansatz auch das Entfernen von Importvektoren, die nach Hinzufügen weiterer Vektoren irrelevant werden. Dies führt zu einem spärlicheren und damit effizienteren Modell, da unnötige Vektoren entfernt werden und somit die Komplexität reduziert wird. Um unendliche Schleifen zwischen Hinzufügen und Entfernen zu vermeiden, werden aussortierte Vektoren für einige Iterationen von der erneuten Auswahl ausgeschlossen – eine Technik, die an die Tabu-Suche angelehnt ist. Diese hybride Strategie verbessert die Genauigkeit und Effizienz des Klassifikators erheblich, da die endgültige Entscheidungsgrenze präziser und das Modell übersichtlicher wird. Eine rein sequentielle Vorwärtsselektion kann solche Optimierungen nicht leisten.

Ein weiterer wichtiger Aspekt der Verbesserungen betrifft die Bestimmung der Modellparameter. Im Gegensatz zu Zhu und Hastie (2005), die für einen gegebenen Kernelparameter (σ) die Importvektoren und den Regularisierungsparameter (λ) simultan bestimmen, wird hier eine Gridsearch-Methode mit Kreuzvalidierung verwendet. Diese Methode durchsucht systematisch verschiedene Kombinationen von σ und λ, um die optimalen Parameter zu finden. Die Kreuzvalidierung trägt dabei zur Robustheit und Generalisierbarkeit des Modells bei, indem das Risiko des Overfitting minimiert wird. Die Entscheidung für Gridsearch mit Kreuzvalidierung basiert auf experimentellen Ergebnissen, die zeigen, dass diese Methode, insbesondere bei einer geringen Anzahl von Trainingsdaten, deutlich höhere Genauigkeiten liefert als die ursprüngliche Vorgehensweise von Zhu und Hastie. Die spezifischen Suchbereiche für σ und λ werden als σ ∈ {2⁻³, 2⁻²,⁵, ..., 2⁴} und λ ∈ {exp(−12), exp(−11), ..., exp(−4)} definiert und mittels einer 5-fachen Kreuzvalidierung optimiert. Diese Modifikation steigert die Zuverlässigkeit und die Leistungsfähigkeit des I²VM-Klassifikators.

Ein zentraler Aspekt der Arbeit ist die Untersuchung und Bestätigung der Hypothese, dass der IVM-Klassifikator, und folglich auch der I²VM, neben seiner diskriminativen auch eine rekonstruktive Modellkomponente besitzt. Während diskriminative Modelle primär die Trennung von Klassen optimieren, zielen rekonstruktive Modelle darauf ab, die Datenverteilung durch möglichst viele Informationen zu approximieren. Die These besagt, dass der IVM-Algorithmus, obwohl primär auf die Optimierung der Klassifizierungsaussagen ausgerichtet, implizit auch die Datenverteilung repräsentiert. Diese rekonstruktive Eigenschaft ist für leistungsfähige inkrementelle Klassifikatoren essentiell, insbesondere im Kontext des sequentiellen Lernens mit potentiell unvollständigen und sich verändernden Daten. Generative Modelle schätzen explizit die bedingte Verteilung der Samples (P(X|Y)), was effizientes Lernen über viele Klassen ermöglicht. Diskriminative Modelle, einschließlich des IVM, schätzen hingegen P(Y|X), ohne Annahmen über die zugrundeliegende Datenverteilung zu treffen. Die Arbeit untersucht, wie der IVM, trotz seines diskriminativen Ansatzes, unter bestimmten Voraussetzungen eine rekonstruktive Komponente entwickelt, die die Datenverteilung approximiert und somit die Robustheit gegenüber Concept Drift und unvollständigen Daten verbessert. Diese rekonstruktive Eigenschaft ist essentiell für die Leistungsfähigkeit des inkrementellen Lerners.

Die Hypothese der rekonstruktiven Komponente wird empirisch untersucht, indem die Verteilung der ausgewählten Importvektoren analysiert wird. Die Ergebnisse zeigen, dass die Importvektoren (IVs) die Datenabdeckung repräsentieren, anstatt nur deren Dichte. Stationäre Kernel sind notwendig, um eine rekonstruktive Modellkomponente zu entwickeln. Die Analyse konzentriert sich auf die Verteilung der IVs in verschiedenen Szenarien: Zwei-Klassen-Szenarien mit Gauß- und gleichförmiger Verteilung der Merkmale sowie ein Vier-Klassen-Szenario mit überlappenden Klassen. In allen Fällen wird beobachtet, dass die IVs die gesamte Datenverteilung gleichmäßig abdecken, unabhängig von der Dichte. Die Importvektoren verteilen sich dabei nicht nach einer reinen Dichtefunktion, sondern versuchen sich gegenseitig abzuhalten, um eine optimale Datenabdeckung zu gewährleisten. Das heißt, es existieren auch Importvektoren außerhalb der direkten Entscheidungsgrenze, die zur Approximation der Datenverteilung und zur Robustheit des Modells beitragen. Die empirischen Ergebnisse bestätigen somit die Hypothese, dass der IVM und folglich auch der I²VM sowohl diskriminative als auch rekonstruktive Eigenschaften aufweisen und somit die Anforderungen eines robusten inkrementellen Klassifikators erfüllen. Die gleichmäßige Verteilung der Importvektoren unterstreicht die Fähigkeit des Modells, die Datenverteilung auch bei begrenzten Ressourcen präzise abzubilden.

Die Leistungsfähigkeit des entwickelten I²VM-Klassifikators wurde in verschiedenen Anwendungsbereichen evaluiert, um seine Robustheit und Effizienz unter realistischen Bedingungen zu demonstrieren. Ein Schwerpunkt lag auf der semantischen Bildsegmentierung unter Verwendung der Microsoft Research Cambridge Object Recognition Image (MSRC) Datenbank. Diese Datenbank enthält 240 manuell segmentierte und beschriftete 8-Bit RGB-Bilder mit einer Größe von 213x320 Pixeln und 9 Klassen (building, grass, tree, cow, sky, aeroplane, face, car, bicycle, void). Die Bilder wurden in überlappende 10x10 Pixel Blöcke unterteilt, wobei für jeden Block Lab-Farbmerkmale und HoG-Merkmale extrahiert und kombiniert wurden. Die Klasse jedes Patches wurde durch Mehrheitsentscheid bestimmt. In diesem Experiment wurde die Fähigkeit von I²VM getestet, mit langen Sequenzen umzugehen und irrelevante Trainingsbeispiele zu entfernen, ohne die Leistung zu beeinträchtigen. Weitere Anwendungen umfassten die Landbedeckungsklassifizierung großer Gebiete mit zusammengesetzten Fernerkundungsbildern (unter Anwendung von Self-Training) und die Objektverfolgung in Bildsequenzen. Diese Experimente zeigten die Adaptionsfähigkeit von I²VM an Veränderungen in der Datenverteilung und die Bewältigung von Concept Drifts in langen Datenströmen.

Im Kontext der semantischen Bildsegmentierung wurden verschiedene Kriterien zum Entfernen nicht-repräsentativer Trainingsbeispiele evaluiert, um die Effizienz des Algorithmus zu optimieren. Verglichen wurden der Cook-Distanz, die modifizierte Cook-Distanz, die Kreuzentropie, ein Maß für die lineare Unabhängigkeit der Samples, ein gewichtetes Sampling und eine gierige Rückwärtsselektion. Diese Kriterien basieren auf unterschiedlichen Einflussfaktoren: Cook-Distanzen berücksichtigen den Einfluss des Entfernens von Samples auf das aktuelle Modell, Kreuzentropie misst die Differenz zwischen Zielwerten und Posterior-Wahrscheinlichkeiten, lineare Unabhängigkeit bewertet die Redundanz der Samples, und das gewichtete Sampling basiert auf der Dichte der Samples. Die Ergebnisse zeigen, dass die lineare Unabhängigkeit und das gewichtete Sampling vergleichbare Genauigkeiten wie der Referenzfall (ohne Entfernen von Samples) erreichen. Andere Kriterien, wie die Kreuzentropie, erwiesen sich als instabiler. Die Evaluierung erfolgte anhand der Fehlerraten und der Anzahl der Importvektoren. Insbesondere bei der MSRC-Datenbank erwies sich das Re-Berechnen des Modells für jedes Sample als zu rechenintensiv, weshalb die gierige Rückwärtsselektion nur auf synthetischen Datensätzen getestet wurde.

Die Leistungsfähigkeit von I²VM wurde auch im Bereich der Objektverfolgung in Bildsequenzen evaluiert. Verglichen wurden die Ergebnisse mit Batch-Tracking-Methoden (Tsai et al., 2011) und einer Online-Tracking-Methode (Chockalingam et al., 2009). Die Datensätze umfassten 'Flower', 'SegTrack' und 'Adafrag'. Für 'Flower' wurden die hinzugefügten und entfernten Importvektoren analysiert, um den Update-Prozess visuell zu untersuchen. Für 'SegTrack' und 'Adafrag' wurde die durchschnittliche Anzahl falsch klassifizierter Pixel über alle Frames bestimmt. I²VM zeigte eine vergleichbare oder sogar bessere Performance als die Vergleichsmethoden, besonders bei starken Erscheinungsänderungen. Zusätzlich wurde I²VM mit einem festen Bounding-Box-Ansatz ('I²VM (BB)') im Kontext des PROST-Datensatzes evaluiert und zeigte gute Ergebnisse bei verschiedenen Erscheinungsvariationen, Okklusionen und unterschiedlichen Lichtverhältnissen. Die Ergebnisse unterstreichen die breite Anwendbarkeit von I²VM für Aufgaben mit langen Datenströmen und Concept Drift. Die Analyse der probabilistischen Ausgabe von I²VM zeigte, dass Samples mit hohen Klassenwahrscheinlichkeiten genauer klassifiziert werden als Samples mit niedrigen Wahrscheinlichkeiten.