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

Semi-supervised learning with committees [Elektronische Ressource] : exploiting unlabeled data using ensemble learning algorithms / vorgelegt von Mohamed Farouk Abdel Hady

313 pages
Universitat Ulmj 89069 Ulmj DeutschlandFakultat fur Ingenieurwissenschaften und InformatikInstitut fur NeuroinformatikDirektor: Prof. Dr. Gunther PalmSemi-Supervised Learning with Committees:Exploiting Unlabeled Data Using EnsembleLearning AlgorithmsDissertation zur Erlangung des DoktorgradesDoktor der Naturwissenschaften (Dr. rer. nat.)der Fakultat fur Ingenieurwissenschaften und Informatik der Universitat Ulmvorgelegt vonMohamed Farouk Abdel Hadyaus Kairo, AgyptenUlm, Deutschland2010Amtierender Dekan der Fakultat fur Ingenieurwissenschaften und Informatik:Prof. Dr. Klaus DietmayerVorsitzender des Promotionsausschusses: Prof. Dr. Uwe SchoningMitglieder des Promotionsausschusses:Prof. Dr. Michael WeberProf. Dr. Heiko NeumannDie Gutachter der Dissertation:Prof. Dr. Gun ther PalmProf. Dr. Wolfgang MinkerProf. Dr. Barbara HammerTag der Promotion: 8. Februar 2011University of Ulmj 89069 Ulmj GermanyFaculty of Engineering and Computer ScienceInstitute of Neural Information ProcessingDirector: Prof. Dr. Gunther PalmSemi-Supervised Learning with Committees:Exploiting Unlabeled Data Using EnsembleLearning AlgorithmsA thesis submitted toFaculty of Engineering and Computer Scienceat University of Ulmin ful llment of the requirements for the degree ofDoctor of Philosophy in Science (Dr. rer. nat.)byMohamed Farouk Abdel Hadyfrom Cairo, EgyptUlm, Germany2010Dean of the Faculty of Engineering and Computer Science:Prof. Dr.
Voir plus Voir moins

Universitat Ulmj 89069 Ulmj Deutschland
Fakultat fur Ingenieurwissenschaften und Informatik
Institut fur Neuroinformatik
Direktor: Prof. Dr. Gunther Palm
Semi-Supervised Learning with Committees:
Exploiting Unlabeled Data Using Ensemble
Learning Algorithms
Dissertation zur Erlangung des Doktorgrades
Doktor der Naturwissenschaften (Dr. rer. nat.)
der Fakultat fur Ingenieurwissenschaften und Informatik
der Universitat Ulm
vorgelegt von
Mohamed Farouk Abdel Hady
aus Kairo, Agypten
Ulm, Deutschland
2010Amtierender Dekan der Fakultat fur Ingenieurwissenschaften und Informatik:
Prof. Dr. Klaus Dietmayer
Vorsitzender des Promotionsausschusses: Prof. Dr. Uwe Schoning
Mitglieder des Promotionsausschusses:
Prof. Dr. Michael Weber
Prof. Dr. Heiko Neumann
Die Gutachter der Dissertation:
Prof. Dr. Gun ther Palm
Prof. Dr. Wolfgang Minker
Prof. Dr. Barbara Hammer
Tag der Promotion: 8. Februar 2011University of Ulmj 89069 Ulmj Germany
Faculty of Engineering and Computer Science
Institute of Neural Information Processing
Director: Prof. Dr. Gunther Palm
Semi-Supervised Learning with Committees:
Exploiting Unlabeled Data Using Ensemble
Learning Algorithms
A thesis submitted to
Faculty of Engineering and Computer Science
at University of Ulm
in ful llment of the requirements for the degree of
Doctor of Philosophy in Science (Dr. rer. nat.)
by
Mohamed Farouk Abdel Hady
from Cairo, Egypt
Ulm, Germany
2010Dean of the Faculty of Engineering and Computer Science:
Prof. Dr. Klaus Dietmayer
Chairman of the doctoral committee: Prof. Dr. Uwe Schoning
Members of the doctoral committee:
Prof. Dr. Michael Weber
Prof. Dr. Heiko Neumann
Reviewers of the dissertation:
Prof. Dr. Gun ther Palm
Prof. Dr. Wolfgang Minker
Prof. Dr. Barbara Hammer
Day of Conferral of Doctorate: February 8, 2011Zusammenfassung
Uberwachtes maschinelles Lernen ist ein Teilgebiet der Kunstlic hen Intelligenz,
das sich mit dem automatischen Lernen von Vorhersagemodellen aus gelabelten
Daten befasst. Solche Lernansatze sind nutzlic h fur viele interessante reale An-
wendungen, insbesondere fur Aufgaben bei der automatischen Klassi kation, dem
Information-Retrieval oder dem Data Mining aus gro en Datensammlungen von
Texten, Bildern und Videos.
Im traditionellen ub erwachten Lernen, benutzt man gelabelte Daten um das
Vorhersagemodell zu bestimmen. Allerdings ist die Annotation der Trainingsda-
ten mit Lehrersignalen fur reale Anwendungen oft schwierig, kosten- und auch zei-
tintensiv, da ein menschlicher Experte mit Erfahrung und der notwendigen Aus-
bildung in der Anwendungsdomane gebraucht wird. Dies gilt vor allem fur Anwen-
dungen mit einer gro en Klassenzahl, besonders dann wenn starke Ahnlichkeiten
zwischen den Klassen vorhanden sind.
Semi-uberwachtes Lernen (SSL) lost diesen inharenten Engpass, durch die In-
tegration von ungelabelten Daten in den ub erwachten Lernprozess. Das Ziel ist
es, die Klassi kationsleistung des Modells durch diese bisher nicht annotierten
Datenpunkte zu steigern, bei gleichzeitiger Reduzierung des Labeling-Aufwandes
durch menschliche Experten. Die Forschungen im Bereich des semi-uberwachten
Lernens lassen sich in vier Hauptrichtungen unterteilen: SSL mit Graphen, SSL
mit generativen Modellen, Semi-ub erwachte Support-Vektor-Maschinen und SSL
mit Ensembles. Semi-uberwachtes Lernen und Ensemble-Lernen sind zwei wich-
tige Paradigmen des maschinellen Lernens, die sich fast parallel, aber mit unter-
schiedlichen Philosophien entwickelt haben. Semi-uberwachtes Lernen versucht
die Klassi kationsleistung durch die Nutzung ungelabelter Daten zu steigern, da-
gegen wird im Ensemble-Lernen versucht, das gleiche Ziel durch die Verwendung
mehrerer Pradiktoren zu erreichen.
In dieser Dissertation fokussiere ich auf SSL mit Ensembles (SSL durch Disa-
greement) und vor allem auf "Co-Training" Algorithmen. "Co-Training" ist ein
oft angewendeter SSL-Algorithmus der von Blum und Mitchell im Jahr 1998 in die
iLiteratur eingefuhrt wurde. Er setzt voraus, dass jede Instanz durch zwei oder
mehrere Merkmalsmengen reprasentiert ist, die auch "Views" genannt werden.
Jeder "View" muss hinreichend zum Lernen des Modells sein und alle "views"
sollen unabhangig sein. In diesem Zusammenhang habe ich einige zentrale Pro-
blemstellungen bei der Kombination von Ensemble-Lernen und semi-ub erwachten
Lernen identi ziert, die ich in der vorliegenden Dissertation bearbeitet habe. Hier-
bei diskutiert ich insbesondere Aufgabenstellungen mit gro er Anzahl von Klassen
und mit vielen Instanzen, die multimodal reprasentiert sind. Kann "Co-Training"
angewendt werden, wenn keine naturliche Merkmalsaufspaltung vorliegt? Wie
kann man mehrere Klassi katoren f ur das "Co-Training" e ektiv konstruktie-
ren? Wie berechnet man einen Kon denzwert zur Klassi kation bzw. Vorhersa-
ge? Fur den Fall, das es Beziehungen und Ahnlichkeiten zwischen den Klassen
gibt, konnen diese Beziehungen im SSL gelernt oder ausgenutzt werden? Wie
kann die Dempster-Shafer-Kombinationsmethode zur Kon denz-Bestimmung ein-
gesetzt werden? Konnen hierarchische neuronale Netze als Klassi katoren unge-
labelter Daten verwendet werden? Kann durch aktives Lernen die Performanz
semi-ub erwachter Lernverfahren verbessert werden? Kann SSL mit Ensembles
auf Regressionsaufgaben ubertragen werden?
Ich habe ferner Fragen im Bereich des Ensemble-Lernens diskutiert, die in
einem engen Zusammenhang mit den von mir studierten SSL Verfahren stehen.
Fuhren trainierbare Kombinierer gegenub er festen Kombinationsabbildungen in
hierarchischen Ensembles yu verbesserten Klassi kationsraten? L asst sich die Per-
formanz hierarchischer Klassi katoren durch Ensembles steigern? Lassen sich in-
formationstheoretische Betrachtungen nutzen um die Gro e eines Ensembles zu
reduzieren? Die Diskussion dieser Fragestellungen zeigt unmittelbar den Nutzen
der semi-ub erwachten Lernverfahren in komplexen realen maschinellen Lernver-
fahren.Abstract
Supervised machine learning is a branch of arti cial intelligence concerned with
learning computer programs to automatically improve with experience through
knowledge extraction from examples. It builds predictive models from labeled
data. Such learning approaches are useful for many interesting real-world appli-
cations, but are particularly useful for tasks involving the automatic categoriza-
tion, retrieval and extraction of knowledge from large collections of data such as
text, images and videos.
In traditional supervised learning, one uses "labeled" data to build a model.
However, labeling the training data for real-world applications is di cult, expen-
sive, or time consuming, as it requires the e ort of human annotators sometimes
with speci c domain experience and training. There are implicit costs associated
with obtaining these labels from domain experts, such as limited time and nan-
cial resources. This is especially true for applications that involve learning with
large number of class labels and sometimes with similarities among them.
Semi-supervised learning (SSL) addresses this inherent bottleneck by allowing
the model to integrate part or all of the available unlabeled data in its supervised
learning. The goal is to maximize the learning performance of the model through
such newly-labeled examples while minimizing the work required of human anno-
tators. Exploiting unlabeled data to help improve the learning performance has
become a hot topic during the last decade and it is divided into four main di-
rections: SSL with graphs, SSL with generative models, semi-supervised support
vector machines and SSL by disagreement (SSL with committees). It is interest-
ing to see that semi-supervised learning and ensemble learning are two important
paradigms that were developed almost in parallel and with di erent philosophies.
Semi-supervised learning tries to improve generalization performance by exploit-
ing unlabeled data, while ensemble learning tries to achieve the same objective
by using multiple predictors.
In this thesis, I concentrate on SSL by disagreement and especially on Co-
Training style algorithms. Co-Training is a popular SSL algorithm introduced by
iiiBlum and Mitchell in 1998. It requires that each instance is represented by two
or more sets of features that are called views. Each view must be su cient for
learning and all views must be independent. I explore several important ques-
tions regarding how to exploit di erent ensemble learning algorithms in SSL for
tasks involving large number of classes and instances that has either single or
multiple representations. How can Co-Training algorithm be applied if there is
not a natural feature splitting? How to construct multiple classi ers to be co-
trained e ectively? How to measure con dence in class label prediction? If there
is relationships and similarities among classes, can these relationships be learned
and exploited during SSL? How can the Dempster-Shafer evidence-theoretic com-
biner be appropriate for con dence measure? How can hierarchical neural network
classi ers exploit unlabeled data to improve the accuracy of image classi cation?
How can active learning improve the performance of semi-supervised learning with
committees? How can SSL with committees be extended to regression tasks? I
investigate other questions that are indirectly related to SSL. How can a train-
able combiner be designed for hierarchical ensembles? Can an ensemble of class
hierarchies outperform a single class hierarchy? How can information theory be
used to prune ensembles? The answers to the questions illustrate the utility and
promise of semi-supervised learning algorithms in complex real-world machine
learning systems.Acknowledgments
First of all, I would like to express my thanks to my advisor Prof. Dr. Gun ther
Palm, the director of the Institute of Neural Information Processing, for accepting
me as a doctoral student at his institute, for giving me the right advice at the
right time and for carefully reviewing this thesis.
Especially, my deepest gratitude goes to my mentor Dr. Friedhelm Schwenker
for supporting me with his valuable suggestions, fruitful discussions and construc-
tive criticisms and for carefully reading this thesis. Despite his workload and tight
schedule, he has cooperated with me in writing many papers.
Many thanks to the German Academic Exchange Service (DAAD) whose
doctoral scholarship nanced my thesis. I would like to thank all the DAAD
co-workers both in Cairo and in Bonn for the excellent organization of the schol-
arship. They have done a lot of e ort to prepare me, through German courses,
seminars and consultation. After the arrival and during my residence in Germany,
they support me in all aspects. Especially I would like to express my gratitude to
Frau Margret Leopold as she is always reachable and solves any faced problem.
Also, I would like to express my thanks to the German Science Foundation
(DFG) for supporting the publication of my papers and conferences attendance
through the funding of both the project \Learning with Fuzzy Teacher Signals in
Neural Multiple Classi er Systems" (under grant SCHW623/4-3) and the Tran-
sregional Collaborative Research Centre SFB/TRR 62 \Companion-Technology
for Cognitive Technical Systems".
Last, but not least, I am grateful to my family for all their patience, support
and loving. My mother for her unlimited support and guidance throughout my
life. She has never stopped believing in me and encouraging me to nish my
studies. My son Ahmed and my daughter Heba who make the nights shorter but
my days much brighter. My marvelous wife Marwa for her encouragement and
never-ending love. To them is all my love and prayers.
Ulm, February 2011 Mohamed F. Abdel Hady
v