Multiple Classifier Systems Incorporating Uncertainty

Publications / Homepage
Cover of the dissertation: Multiple Classifier Systems Incorporating Uncertainty

Cover painting: doctors by Michael S. Parker, 2003. Used with friendly permission of the artist.

Cover design: Kreativfrosch Grafik + Design.


Dissertation (PhD thesis) of Christian Thiel, accepted at the Institute of Neural Information Processing, University of Ulm, 2010.

Print: ISBN 978-3-86853-675-1
Verlag Dr. Hut, München, 2010
Amazon
Electronic (PDF) :  University repository
Author's homepage

Cite as: Christian Thiel, Multiple Classifier Systems Incorporating Uncertainty, Verlag Dr. Hut, München, 2010, ISBN 9783868536751. Dissertation University of Ulm, 2010.

Keywords: MCS; multiple classifiers systems; uncertainty; vagueness; imprecision; Dempster-Shafer; machine learning; classifier; certainty; fuzzy-input; support vector machine; remote sensing; emotion recognition; Mehrklassifikatorsystem; Unsicherheit; Unsicherheitskalkül; Emotionserkennung; Klassifikation; Klassifikator; fuzzy; Sicherheit; unsicheres Schließen; Support-Vektor-Maschine; Dempster-Shafer-Theorie; Fuzzy-Wahrscheinlichkeit; Fuzzy-Maß; Fuzzy-Integral; Wahrscheinlichkeitstheoretische Menge;

Abstract

Multiple classifier systems (MCS) unite the answers of separately-trained powerful base-classifiers to obtain the right classification for the sample at hand. In practical applications, a sample is not associated with exactly one class, but belongs fuzzily to multiple ones. How uncertain class information can be incorporated into multiple classifier systems is detailed in this work.

On the theoretical side, it is described how existing approaches to modelling uncertainty like Bayesian probability, Dempster-Shafer theory, fuzzy logic or fuzzy sets, and also unfamiliar ones like the distribution of opinions, are able to support and deal with the core notions of uncertainty in classification: vagueness, imprecision and certainty.

In the larger practical part, the use of uncertainty is detailed for every stage of the MCS. The most suitable classifiers are identified, and some well-known schemes extended to deal and answer with uncertain class information. Notably every aspect of the newly proposed and award-winning (KES 2007) fuzzy-input fuzzy-output support vector machines is explained. How the certainty of a classifier answer can be quantified is explored as well as which fusion scheme to use to come to a final classification.

The steps for applying the techniques above to real-world problems are shown exemplarily for two applications, the recognition of emotions in facial expression videos, and land cover mapping from satellite images (a winner of the IEEE DFTC Contest 2008).

Zusammenfassung

Die Berücksichtigung von Unsicherheit in Mehrklassifikatorsystemen (MKS) steht im Zentrum dieser Arbeit. Anwendungen finden sich beispielsweise in der Emotionserkennung, wenn die Stimmung einer Person automatisch in eine bestimmte Klasse wie glücklich, wütend oder überrascht eingeordnet werden soll. Mehrere Klassifikator-Programme spezialisieren sich dann jeweils auf ein Merkmal der Person, etwa die Augen, den Mund oder die Stimmhöhe. Die Entscheidungen der Programme sind mit Unsicherheit behaftet, zum Beispiel weil die Umgebung sehr laut war. Auch soll sich ein Klassifikator nicht auf eine Emotion festlegen; eine Person kann ja wütend und überrascht zugleich sein. Also wird seine Antwort in einer sogenannten vagen oder weichen Zuordnung bestehen. Um stabilere und genauere Entscheidungen zu bekommen, fasst das MKS die Einzelmeinungen der Programme per Fusion zusammen.

Klassifikatoren arbeiten traditionell mit harten Klassen, das heißt, ein Datenpunkt ist genau einer Klasse zugeordnet. Das Beispiel der Emotionserkennung zeigt deutlich, dass dies in einigen Anwendungen eine allzu einschränkende Annahme ist. Viele Forscher haben deshalb Unsicherheit bereits in zahlreiche, aber isolierte Teilbereiche von MKS integriert. Ihre Ansätze und Erkenntnisse werden im Gesamtkontext von MKS verortet. Die Arbeit schlägt darüber hinaus Lösungen für noch bestehende Lücken vor.

Es gibt formale Theorien, um Unsicherheit zu repräsentieren, unter ihnen die Bayessche Wahrscheinlichkeitstheorie, die Dempster-Shafer Evidenz-Theorie, die Fuzzy Logik sowie Fuzzy Mengen und Meinungsverteilungen. Nachdem mit Vagheit, Ungenauigkeit und Sicherheit die für MKS relevanten Arten von Unsicherheit definiert sind, nimmt sich die Arbeit die Frage vor, inwieweit diese von den jeweiligen Theorien dargestellt und - wichtiger noch - verrechnet werden können. Besonders für die Dempster-Shafer Theorie werden praktische Anwendungen aufgezeigt.

Mit Support-Vektor-Maschinen (SVM), lernender Vektor-Quantisierung und selbstorganisierenden Karten werden einige Basis-Klassifikatoren so erweitert, dass sie auch aus unsicheren Klassenzuordnungen lernen können und in der Lage sind, unsichere Antworten zu geben. Hervorzuheben ist dabei die Erweiterung der an sich schon mächtigen binären SVM. Sie beruht auf der Verdoppelung der Trainingspunkte und erfordert Änderungen am darunterliegenden Optimierungsproblem. Wie hier vage Antworten errechnet werden können, wird für zwei wichtige Mehrklassenarchitekturen (Eine-gegen-den-Rest und Jede-gegen-Jede) detailliert dargestellt. Experimente bestätigen, dass die mit unsicheren Zuordnungen trainierte Klassifikatoren genauere Antworten geben als die mit harten Zuordnungen trainierten. Eine Untersuchung zum (überraschend geringen) Einfluss von Klassenzuordnungsfehlern in den Trainingsdaten rundet die Behandlung der Klassifikatoren ab.

Für die Klassifikator-Fusion ist es wichtig zu wissen, wie sicher die Antworten der einzelnen Algorithmen sind. Ein Indikator dafür ist die Struktur der vagen Ausgaben, die etwa mit der Gini-Funktion oder dem Fuzzy-Index charakterisiert werden kann. Eine mächtigere Alternative ist, jeden Klassifikator selbst einen Sicherheitswert ausgeben zu lassen, schließlich kann er abschätzen, ob ihm beispielsweise passend zur Anfrage Trainingsdaten in ausreichender Menge zur Verfügung stehen. Um den Nutzen von Sicherheitsindikatoren und vagen Klassifikatoren abwägen zu können, reicht es nicht aus, die Genauigkeit auf Basis der Erkennungsrate zu bestimmen. Abhilfe schaffen hier Maße wie die Fuzzy Fehlermatrix von Binaghi. Durch Zurückweisungs-Experimente, bei denen das System mit zu großer Unsicherheit beurteilte Datenpunkte ablehnt, werden weitere Erkenntnisse gewonnen.

Eine sogenannte Fusionsfunktion fasst die Antworten mehrerer Klassifikatoren zusammen. Bestehende Funktionen, die unter anderem auf den verschiedenen Unsicherheitstheorien fußen, werden vorgestellt und kategorisiert. Für vier auf den ersten Blick unterschiedliche Verfahren (Entscheidungs-Schablonen, lineare Assoziativspeicher, naive Bayes-Fusion und Pseudoinversen-Lösung) kann gezeigt werden, dass sie im Kern auf der in der Trainingsphase gewonnenen Verwechslungsmatrix beruhen. Experimente bestätigen erneut, dass MKS einzelnen Klassifikatoren überlegen sind, und geben Hinweise zur Auswahl geeigneter Fusionsfunktionen.

Allgemein wurden zahlreiche Experimente durchgeführt, um die genannten Problemstellungen besser verstehen und beurteilen zu können. Von den vier dazu verwendeten Anwendungsszenarien verdienen zwei besondere Erwähnung:

Das System zur Emotionserkennung in Videos von Gesichtsausdrücken besteht aus 14 Einzelklassifikatoren, die auf verschiedenen Regionen des Gesichts und auf unterschiedlichen Merkmalen arbeiten. Letztere stützen sich auf Bewegungsschätzer, Kantendetektoren und Hauptachsentransformation. Die endgültige Erkennungsrate nach der Fusion ist sogar etwas höher als die eines Menschen und braucht den Vergleich mit anderen in der Literatur vorgestellten Systemen nicht zu scheuen.

Im Szenario der Fernerkundung besteht das Problem darin, aufgrund von Satellitendaten sagen zu können, zu welcher Klasse ein bestimmtes Gebiet auf der Erde gehört, beispielsweise ob es bebaut ist oder ob hier ein Feld brach liegt. Bei dieser Anwendung zeigt sich, dass die vorgeschlagenen halbüberwachten selbstorganisierenden Karten viel gleichmäßigere vage Antworten geben als bisherige Ansätze. Die inzwischen preisgekrönten* erweiterten SVM produzieren Landkarten mit sehr kompakten, gut zu interpretierenden Regionen, und haben von allen getesteten Klassifikatoren die höchste Genauigkeit.

*Auf der Konferenz KES 2007 gewann meine Veröffentlichung zu Fuzzy-Input Fuzzy-Output Support-Vektor-Maschinen (Fuzzy-Input Fuzzy-Output One-Against-All Support Vector Machines) bei einer Konkurrenz von 410 Beiträgen den Preis für den besten Artikel. In Zusammenarbeit mit Ferdinando Giacco konnte ich die SVM so erfolgreich auf das Fernerkundungs-Szenario anwenden, dass das System zu den Gewinnern des DFTC Fusion Contest 2008 der IEEE Geoscience and Remote Sensing Society zählt.