UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

Prediction on a graph with a perceptron

Herbster, M; Pontil, M; (2007) Prediction on a graph with a perceptron. In: Advances in Neural Information Processing Systems. (pp. 577 - 584).

Full text not available from this repository.

Abstract

We study the problem of online prediction of a noisy labeling of a graph with the perceptron. We address both label noise and concept noise. Graph learning is framed as an instance of prediction on a finite set. To treat label noise we show that the hinge loss bounds derived by Gentile [1] for online perceptron learning can be transformed to relative mistake bounds with an optimal leading constant when applied to prediction on a finite set. These bounds depend crucially on the norm of the learned concept. Often the norm of a concept can vary dramatically with only small perturbations in a labeling. We analyze a simple transformation that stabilizes the norm under perturbations. We derive an upper bound that depends only on natural properties of the graph - the graph diameter and the cut size of a partitioning of the graph - which are only indirectly dependent on the size of the graph. The impossibility of such bounds for the graph geodesic nearest neighbors algorithm will be demonstrated.

Type:Proceedings paper
Title:Prediction on a graph with a perceptron
UCL classification:UCL > School of BEAMS > Faculty of Engineering Science > Computer Science

Archive Staff Only: edit this record