La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
Télécharger Lire

Multiple classifier systems incorporating uncertainty [Elektronische Ressource] / vorgelegt von Christian André Thiel

205 pages
Christian ThielMultipleClassifierSystemsIncorporatingUncertaintyThe title page and cover show the painting doctors by Michael S. Parker(www.michaelsparker.com), 2003. Used with friendly permission of the artist.Cover layout by Kreativfrosch Grafik + Design (www.kreativfrosch.eu),Wegscheid bei Passau, Germany.Universit¨at Ulm| 89069 Ulm| GermanyDissertation zur Erlangung des DoktorgradesDoktor der Naturwissenschaften (Dr. rer. nat.)der Fakult¨ at fur¨ Ingenieurwissenschaften und Informatikder Universit¨ at Ulmvorgelegt vonChristian Andr´e ThielAngefertigt am Institut fur¨ NeuroinformatikEinreichung der Dissertation: Dezember 2009Tag der Promotion: 10. Juni 2010Gutachter: Prof. Dr. Gun¨ ther Palmhter: Prof. Dr. Heiko NeumannGutachter: Prof. Dr. Barbara HammerAmtierender Dekan der Fakult¨ at:Prof. Dr.-Ing. Michael Weberwww.ChristianThiel.comAbstractThe inclusion of uncertain class information into multi classifier systems (MCS)is the central theme in this thesis. A multi classifier system relies on multiplebase classifiers, each of which is trained on a separate view of the problem athand. Combining their answers will lead to a more accurate final decision. Anexample would be emotion recognition, with decisions based on observations ofthe mouth, the eyes or the pitch of the voice.Traditionally in classification one sample is associated with exactly one class,for example anger.
Voir plus Voir moins

Christian Thiel
IncorporatingUncertaintyThe title page and cover show the painting doctors by Michael S. Parker
(www.michaelsparker.com), 2003. Used with friendly permission of the artist.
Cover layout by Kreativfrosch Grafik + Design (www.kreativfrosch.eu),
Wegscheid bei Passau, Germany.Universit¨at Ulm| 89069 Ulm| Germany
Dissertation zur Erlangung des Doktorgrades
Doktor der Naturwissenschaften (Dr. rer. nat.)
der Fakult¨ at fur¨ Ingenieurwissenschaften und Informatik
der Universit¨ at Ulm
vorgelegt von
Christian Andr´e Thiel
Angefertigt am Institut fur¨ Neuroinformatik
Einreichung der Dissertation: Dezember 2009
Tag der Promotion: 10. Juni 2010
Gutachter: Prof. Dr. Gun¨ ther Palmhter: Prof. Dr. Heiko Neumann
Gutachter: Prof. Dr. Barbara Hammer
Amtierender Dekan der Fakult¨ at:
Prof. Dr.-Ing. Michael Weberwww.ChristianThiel.comAbstract
The inclusion of uncertain class information into multi classifier systems (MCS)
is the central theme in this thesis. A multi classifier system relies on multiple
base classifiers, each of which is trained on a separate view of the problem at
hand. Combining their answers will lead to a more accurate final decision. An
example would be emotion recognition, with decisions based on observations of
the mouth, the eyes or the pitch of the voice.
Traditionally in classification one sample is associated with exactly one class,
for example anger. But, in practical applications, such a hard distinction is
not warranted; instead a sample should have soft class memberships, thus being
associated fuzzily with multiple classes at the same time. The inclusion of this
uncertain information into various, but isolated building blocks of a MCS has
been tackled by a great many researchers. This thesis places these approaches
in the greater MCS context and assesses their utility. Remaining problems are
identified and in many cases a solution is proposed.
Bayesian probability is the most obvious tool for modelling class uncertainty, but
perhaps the Dempster-Shafer theory of evidence, fuzzy logic or fuzzy sets, or even
a distribution of opinions are much more viable in a classification context. These
formal uncertainty theories, as well as some others, are assessed regarding their
aptitude to support the core flavours of uncertainty in MCS, as identified in this
work: vagueness, imprecision, and certainty. For the very fitting Dempster-Shafer
theory, practical applications are reported.
Some base classifiers have been extended to be trained on and answer with uncer-
tain labels: learning vector quantisation, self-organizing maps, and most notably
support vector machines (SVMs). The latter are an already very powerful breed
of classifiers, and based on the idea of duplication, the underlying optimisation
problem could be altered to accept fuzzy labels. Obtaining soft outputs from
the binary SVMs is not trivial, but complete solutions are provided for the One-
vs-Rest and One-vs-One multiclass decomposition architectures. Experiments do
confirm the effectiveness of the fuzzy trained machines over their hard trained
icounterparts, and yield answers as to which variants and parameter settings are
to be preferred. Ideas on including certainty weighted information into many
classifiers, and a study on the (surprisingly low) impact of label noise complete
the classifier chapter.
Once all classifiers have provided their answers, the following fusion stage requires
an assessment of how certain these opinions are. This can be accomplished by
looking at the structure of the answer, for example using the Gini function or an
index of fuzziness. A rating of certainty can also be provided by the classifiers
themselves. Both approaches are closely related to measuring the fuzzy accuracy
of an algorithm, with Binaghi’s fuzzy error matrix being one option. Rejection
experiments provide further insight in this regard.
Existing fuzzy classifier fusion schemes are presented and categorised, among
them those derived from uncertainty theories. For four fusion functions (decision
templates, linear associative memory, naive Bayes and pseudoinverse solution) it
can be shown that they all share the confusion matrix as the core element. Exper-
iments again confirm the superiority of MCS architectures over single classifiers,
and give pointers as to which fusion scheme to use in which situations.
Numerous experiments were conducted to assess each mentioned aspect. Of the
four real-world applications that served as test cases, two are especially note-
worthy. The setup for the recognition of emotions in video sequences of facial
expressions includes 14 base classifiers, operating on four different areas of the
face and utilising PCA, edge orientation, and motion based features. The accu-
racy of the system is slightly higher than for the average human, and apparently
competitive with approaches described in the literature. Applied to land cover
mapping, the fuzzy semi-supervised SOMs provide much smoother soft answers
1than hitherto proposed techniques, and the award-winning fuzzy SVMs produce
a rendering of the satellite images that exhibits very compact regions, perfect for
easy expert interpretation, and the highest accuracy of all tested classifiers.
1My initial publication on fuzzy-input fuzzy-output support vector machines [260] won the
“BestPaper”awardattheKES2007conference,outof411contributions. Incollaborationwith
Ferdinando Giacco, applying the SVMs in a land cover mapping scenario placed us among the
winners [156] of the 2008 DFTC Fusion Contest of the IEEE Geoscience and Remote Sensing
Die Berucksichtigung von Unsicherheit in Mehrklassifikatorsystemen (MKS) steht¨
im Zentrum dieser Arbeit. Anwendungen finden sich beispielsweise in der Emo-
tionserkennung, wenn die Stimmung einer Person automatisch in eine bestimmte
Klasse wie gluc¨ klich, wutend¨ oder ub¨ errascht eingeordnet werden soll. Mehre-
re Klassifikator-Programme spezialisieren sich dann jeweils auf ein Merkmal der
Person, etwa die Augen, den Mund oder die Stimmhohe. 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 wutend¨ und ub¨ errascht 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 Daten-
punkt ist genau einer Klasse zugeordnet. Das Beispiel der Emotionserkennung
zeigt deutlich, dass dies in einigen Anwendungen eine allzu einschrank¨ ende An-
nahme ist. Viele Forscher haben deshalb Unsicherheit bereits in zahlreiche, aber
isolierte Teilbereiche von MKS integriert. Ihre Ansatze und Erkenntnisse wer-¨
den im Gesamtkontext von MKS verortet. Die Arbeit schlag¨ t darub¨ er hinaus
Losungen fur noch bestehende Lucken vor.¨ ¨ ¨
Es gibt formale Theorien, um Unsicherheit zu repr¨asentieren, unter ihnen die
Bayessche Wahrscheinlichkeitstheorie, die Dempster-Shafer Evidenz-Theorie, die
Fuzzy Logik sowie Fuzzy Mengen und Meinungsverteilungen. Nachdem mit Vag-
heit, Ungenauigkeit und Sicherheit die fur MKS relevanten Arten von Unsicher-¨
heit definiert sind, nimmt sich die Arbeit die Frage vor, inwieweit diese von den
jeweiligen Theorien dargestellt und - wichtiger noch - verrechnet werden konnen.¨
Besonders fur¨ die Dempster-Shafer Theorie werden praktische Anwendungen auf-
Mit Support-Vektor-Maschinen (SVM), lernender Vektor-Quantisierung und selbst-
organisierenden Karten werden einige Basis-Klassifikatoren so erweitert, dass sie
iiiauch aus unsicheren Klassenzuordnungen lernen k¨onnen und in der Lage sind,
unsichere Antworten zu geben. Hervorzuheben ist dabei die Erweiterung der an
sich schon m¨achtigen bin¨aren SVM. Sie beruht auf der Verdoppelung der Trai-
¨ningspunkte und erfordert Anderungen am darunterliegenden Optimierungspro-
blem. Wie hier vage Antworten errechnet werden k¨onnen, wird fur¨ zwei wichtige
Mehrklassenarchitekturen (Eine-gegen-den-Rest und Jede-gegen-Jede) detailliert
dargestellt. Experimente bestat¨ igen, dass die mit unsicheren Zuordnungen trai-
nierte Klassifikatoren genauere Antworten geben als die mit harten Zuordnungen
trainierten. Eine Untersuchung zum (uberraschend geringen) Einfluss von Klas-¨
senzuordnungsfehlern in den Trainingsdaten rundet die Behandlung der Klassifi-
katoren ab.
Fur¨ die Klassifikator-Fusion ist es wichtig zu wissen, wie sicher die Antworten der
einzelnen Algorithmen sind. Ein Indikator dafur ist die Struktur der vagen Ausga-¨
ben, die etwa mit der Gini-Funktion oder dem Fuzzy-Index charakterisiert werden
kann. Eine machtigere Alternative ist, jeden Klassifikator selbst einen Sicherheits-¨
wert ausgeben zu lassen, schließlich kann er abschat¨ zen, ob ihm beispielsweise pas-
send zur Anfrage Trainingsdaten in ausreichender Menge zur Verfugung stehen.¨
Um den Nutzen von Sicherheitsindikatoren und vagen Klassifikatoren abw¨agen
zu konnen,¨ reicht es nicht aus, die Genauigkeit auf Basis der Erkennungsrate zu
bestimmen. Abhilfe schaffen hier Maße wie die Fuzzy Fehlermatrix von Binaghi.
Durch Zuruc¨ kweisungs-Experimente, bei denen das System mit zu großer Unsi-
cherheit beurteilte Datenpunkte ablehnt, werden weitere Erkenntnisse gewonnen.
Eine sogenannte Fusionsfunktion fasst die Antworten mehrerer Klassifikatoren
zusammen. Bestehende Funktionen, die unter anderem auf den verschiedenen Un-
sicherheitstheorien fußen, werden vorgestellt und kategorisiert. Fur¨ vier auf den
ersten Blick unterschiedliche Verfahren (Entscheidungs-Schablonen, lineare As-
soziativspeicher, naive Bayes-Fusion und Pseudoinversen-L¨osung) kann gezeigt
werden, dass sie im Kern auf der in der Trainingsphase gewonnenen Verwechs-
lungsmatrix beruhen. Experimente best¨atigen erneut, dass MKS einzelnen Klas-
sifikatoren uberlegen sind, und geben Hinweise zur Auswahl geeigneter Fusions-¨
Allgemein wurden zahlreiche Experimente durchgefuhrt, um die genannten Pro-¨
blemstellungen besser verstehen und beurteilen zu konnen.¨ Von den vier dazu
verwendeten Anwendungsszenarien verdienen zwei besondere Erw¨ahnung:
Das System zur Emotionserkennung in Videos von Gesichtsausdruc¨ ken besteht
aus 14 Einzelklassifikatoren, die auf verschiedenen Regionen des Gesichts und
auf unterschiedlichen Merkmalen arbeiten. Letztere stutzen sich auf Bewegungs-¨
sch¨atzer, Kantendetektoren und Hauptachsentransformation. Die endgultig¨ e Er-
kennungsrate nach der Fusion ist sogar etwas hoher als die eines Menschen und¨
braucht den Vergleich mit anderen in der Literatur vorgestellten Systemen nicht
zu scheuen.
ivIm Szenario der Fernerkundung besteht das Problem darin, aufgrund von Sa-
tellitendaten sagen zu konnen, zu welcher Klasse ein bestimmtes Gebiet auf der¨
Erde gehor¨ t, beispielsweise ob es bebaut ist oder ob hier ein Feld brach liegt. Bei
dieser Anwendung zeigt sich, dass die vorgeschlagenen halbuberwachten selbst-¨
organisierenden Karten viel gleichmaߨ igere vage Antworten geben als bisherige
2Ansatze. Die inzwischen preisgekronten erweiterten SVM produzieren Landkar-¨ ¨
ten mit sehr kompakten, gut zu interpretierenden Regionen, und haben von allen
getesteten Klassifikatoren die h¨ochste Genauigkeit.
2AufderKonferenz KES2007gewannmeineVeroffentlichungzuFuzzy-InputFuzzy-Output¨
Support-Vektor-Maschinen [260] bei einer Konkurrenz von 410 Beitragen den Preis fur 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 zahlt.¨