Herbster, MJ;
(2008)
Exploiting cluster-structure to predict the labeling of a graph.
In: Freund, Y and Györfi, L and Turán, G and Zeugmann, T, (eds.)
Algorithmic Learning Theory: 19th International Conference, ALT 2008, Budapest, Hungary, October 13-16, 2008: Proceedings.
(pp. 54 - 69).
Springer-Verlag: Berlin/Heidelberg, Germany.
![[thumbnail of 135663.pdf]](https://discovery.ucl.ac.uk/style/images/fileicons/application_pdf.png) Preview |
PDF
135663.pdf Available under License : See the attached licence file. Download (276kB) |
Abstract
The nearest neighbor and the perceptron algorithms are intuitively motivated by the aims to exploit the “cluster” and “linear separation” structure of the data to be classified, respectively. We develop a new online perceptron-like algorithm, Pounce, to exploit both types of structure. We refine the usual margin-based analysis of a perceptron-like algorithm to now additionally reflect the cluster-structure of the input space. We apply our methods to study the problem of predicting the labeling of a graph. We find that when both the quantity and extent of the clusters are small we may improve arbitrarily over a purely margin-based analysis.
| Type: | Proceedings paper |
|---|---|
| Title: | Exploiting cluster-structure to predict the labeling of a graph |
| ISBN-13: | 9783540879862 |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1007/978-3-540-87987-9_9 |
| Publisher version: | http://dx.doi.org/10.1007/978-3-540-87987-9_9 |
| Additional information: | The original publication is available at www.springerlink.com |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/135663 |
Archive Staff Only
 |
View Item |
