Exploiting Cluster-Structure to Predict the Labeling of a Graph
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.
Cite
Text
Herbster. "Exploiting Cluster-Structure to Predict the Labeling of a Graph." International Conference on Algorithmic Learning Theory, 2008. doi:10.1007/978-3-540-87987-9_9Markdown
[Herbster. "Exploiting Cluster-Structure to Predict the Labeling of a Graph." International Conference on Algorithmic Learning Theory, 2008.](https://mlanthology.org/alt/2008/herbster2008alt-exploiting/) doi:10.1007/978-3-540-87987-9_9BibTeX
@inproceedings{herbster2008alt-exploiting,
title = {{Exploiting Cluster-Structure to Predict the Labeling of a Graph}},
author = {Herbster, Mark},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {2008},
pages = {54-69},
doi = {10.1007/978-3-540-87987-9_9},
url = {https://mlanthology.org/alt/2008/herbster2008alt-exploiting/}
}