PAC-Bayesian Pattern Classification with Kernels - Theory, Algorithms, and an Application to the Game of Go (dissetation 2002 239s)_Thore Graepel.pdf

PAC-Bavesian Pattern
Classification with Kernels
Theory, Algorithms,
and an Application to the Game of Go
vorgelegt von
Diplom-Physiker (Dip1.-Phys.)
Thore Graepel
Fakultat IV - Elektrotechnik und Informatik
der Technischen Universitat Berlin
zur Erlangung des akademischen Grades
Doktor der Naturwissenschaften
- Dr. rer. nat. -
genehmigte Dissertation
Promotionsausschuss:
Vorsitzender: Prof. Dr. Heinrich Klar
Berichter: Prof. Dr. Ulrich Kockelkorn
Berichter: Prof. Dr. Fritz Wysotzki
Tag der wissenschaftlichen Aussprache: 12. Juli 2002
Berlin 2002
D 83
Fiir rneine Eltern
Abstract
The thesis deals with problems of pattern classification in the framework of machine
learning. The focus of the work is on kernel methods for the supervised classification
of objects. The thesis gives a detailed introduction into the field of kernel algorithms
and learning theory. New contributions include learning theoretical results in the PAC-
Bayesian framework, efficient sampling algorithms for Bayesian classification in kernel
space, and an application of kernel methods to pattern analysis in the game of Go.
Learning Theory In the PAC-Bayesian framework we derive new bounds on the predic-
tion error of linear classifiers (in kernel space) in terms of the normalised margin achieved
on the training sample, taking into account both the concentration of the training data
and the margin distribution. Assuming sparseness of the dual variables we extend the
PAC-Bayesian framework to data-dependent hypotheses. Finally, we prove "egalitarian"
bounds on the probability of finding classifiers with high prediction error in subsets of hy-
pothesis space with low empirical risk-results that emphasise the importance of model
selection.
Learning Algorithms We discuss Bayesian classification in kernel space and identify
Bayesian transduction and the Bayes point machine as optimal procedures for classifica-
tion in a Ba