Palmer, Nicholas James (2008) Pattern classification via unsupervised learners. PhD thesis, University of Warwick.

Preview

PDF WRAP_THESIS_Palmer_2008.pdf - Requires a PDF viewer. Download (10Mb)

Request Changes to record.

Abstract

We consider classification problems in a variant of the Probably Approximately Correct (PAC)-learning framework, in which an unsupervised learner creates a discriminant function over each class and observations are labeled by the learner returning the highest value associated with that observation. Consideration is given to whether this approach gains significant advantage over traditional discriminant techniques.
It is shown that PAC-learning distributions over class labels under Ll distance or KL-divergence implies PAC classification in this framework. We give bounds on the regret associated with the resulting classifier, taking into account the possibility of variable misclassification penalties. We demonstrate the advantage of estimating the a posteriori probability distributions over class labels in the setting of Optical Character Recognition.
We show that unsupervised learners can be used to learn a class of probabilistic concepts (stochastic rules denoting the probability that an observation has a positive label in a 2-class setting). This demonstrates a situation where unsupervised learners can be used even when it is hard to learn distributions over class labels - in this case the discriminant functions do not estimate the class probability densities.
We use a standard state-merging technique to PAC-learn a class of probabilistic automata and show that by learning the distribution over outputs under the weaker L1 distance rather than KL-divergence we are able to learn without knowledge of the expected length of an output. It is also shown that for a restricted class of these automata learning under L1 distance is equivalent to learning under KL-divergence.

Item Type:	Thesis (PhD)
Subjects:	L Education > LB Theory and practice of education Q Science > QA Mathematics
Library of Congress Subject Headings (LCSH):	Pattern perception, Learning classifier systems, Pattern recognition systems, Probability learning, Learning, Psychology of
Official Date:	March 2008
Dates:	Date Event March 2008 Submitted
Institution:	University of Warwick
Theses Department:	Department of Computer Science
Thesis Type:	PhD
Publication Status:	Unpublished
Supervisor(s)/Advisor:	Goldberg, P. W. (Paul W.)
Sponsors:	Engineering and Physical Sciences Research Council (Great Britain) (EPSRC) (GR/R86188/01)
Format of File:	pdf
Extent:	151 leaves : charts
Language:	eng

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads