nips nips2006 nips2006-163 nips2006-163-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Mark Herbster, Massimiliano Pontil
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. 1
[1] C. Gentile. The robustness of the p-norm algorithms. Machine Learning, 53(3):265–299, 2003.
[2] A. Blum and S. Chawla. Learning from labeled and unlabeled data using graph mincuts. In ICML 2002, pages 19–26. Morgan Kaufmann, San Francisco, CA, 2002.
[3] R. I. Kondor and J. Lafferty. Diffusion kernels on graphs and other discrete input spaces. In ICML 2002, pages 315–322. Morgan Kaufmann, San Francisco, CA, 2002.
[4] X. Zhu, Z. Ghahramani, and J. Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In ICML 2003, pages 912–919, 2003.
[5] A. Smola and R.I. Kondor. Kernels and regularization on graphs. In COLT 2003, pages 144–158, 2003.
[6] M. Belkin, I. Matveeva, and P. Niyogi. Regularization and semi-supervised learning on large graphs. In COLT 2004, pages 624 – 638, Banff, Alberta, 2004. Springer.
[7] T. Zhang and R. Ando. Analysis of spectral kernel design based semi-supervised learning. In Y. Weiss, B. Sch¨ lkopf, and J. Platt, editors, NIPS 18, pages 1601–1608. MIT Press, Cambridge, MA, 2006. o
[8] M. Herbster, M. Pontil, and L. Wainer. Online learning over graphs. In ICML 2005, pages 305–312, New York, NY, USA, 2005. ACM Press.
[9] Y. Freund and R. E. Schapire. Large margin classification using the perceptron algorithm. Machine Learning, 37(3):277–296, 1999.
[10] D. Klein and M. Randi´ . Resistance distance. Journal of Mathematical Chemistry, 12(1):81–95, 1993. c
[11] J. M. Barzdin and R. V. Frievald. On the prediction of general recursive functions. Soviet Math. Doklady, 13:1224–1228, 1972.
[12] N. Aronszajn. Theory of reproducing kernels. Trans. Amer. Math. Soc., 68:337–404, 1950.
[13] D. Karger and C. Stein. A new approach to the minimum cut problem. JACM, 43(4):601–640, 1996.