Pattern classification via unsupervised learners
Palmer, Nicholas James (2008) Pattern classification via unsupervised learners. PhD thesis, University of Warwick.
WRAP_THESIS_Palmer_2008.pdf - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Official URL: http://webcat.warwick.ac.uk/record=b2244164~S9
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 or Dissertation (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|
|Institution:||University of Warwick|
|Theses Department:||Department of Computer Science|
|Supervisor(s)/Advisor:||Goldberg, P. W. (Paul W.)|
|Sponsors:||Engineering and Physical Sciences Research Council (Great Britain) (EPSRC) (GR/R86188/01)|
|Format of File:|
|Extent:||151 leaves : charts|
Actions (login required)
Downloads per month over past year