nips nips2002 nips2002-140 nips2002-140-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Koby Crammer, Ran Gilad-bachrach, Amir Navot, Naftali Tishby
Abstract: Prototypes based algorithms are commonly used to reduce the computational complexity of Nearest-Neighbour (NN) classifiers. In this paper we discuss theoretical and algorithmical aspects of such algorithms. On the theory side, we present margin based generalization bounds that suggest that these kinds of classifiers can be more accurate then the 1-NN rule. Furthermore, we derived a training algorithm that selects a good set of prototypes using large margin principles. We also show that the 20 years old Learning Vector Quantization (LVQ) algorithm emerges naturally from our framework. 1
[1] E. Fix and j. Hodges. Discriminatory analysis. nonparametric discrimination: Consistency properties. Technical Report 4, USAF school of Aviation Medicine, 1951.
[2] P. Y. Simard, Y. A. Le Cun, and J. Denker. Efficient pattern recognition using a new transformation distance. In Advances in Neural Information Processing Systems, volume 5, pages 50–58. 1993.
[3] P. Indyk and R. Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the 30th ACM Symposium on the Theory of Computing, pages 604–613, 1998.
[4] V. Vapnik. The Nature Of Statistical Learning Theory. Springer-Verlag, 1995.
[5] Y. Freund and R. E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119–139, 1997.
[6] R. E. Schapire, Y. Freund, P. Bartlett, and W. S. Lee. Boosting the margin : A new explanation for the effectiveness of voting methods. Annals of Statistics, 1998.
[7] Llew Mason, P. Bartlett, and J. Baxter. Direct optimization of margins improves generalization in combined classifier. Advances in Neural Information Processing Systems, 11:288–294, 1999.
[8] C. Campbell, N. Cristianini, and A. Smola. Query learning with large margin classifiers. In International Conference on Machine Learning, 2000.
[9] T. Kohonen. Self-Organizing Maps. Springer-Verlag, 1995.
[10] L. Buckingham and S. Geva. Lvq is a maximum margin algorithm. In Pacific Knowledge Acquisition Workshop PKAW’2000, 2000.
[11] L. Devroye, L. Gyorfi, and G. Lugosi. A Probabilistic Theory of Pattern Recognition. Springer, New York, 1996.
[12] Y. Singer and D. D. Lewis. Machine learning for information retrieval: Advanced techniques. presented at ACM SIGIR 2000, 2000.
[13] T. Kohonen, J. Hynninen, J. Kangas, and K. Laaksonen, J. Torkkola. Lvq pak, the learning vector quantization program package. http://www.cis.hut.fi/research/lvq pak, 1995.
[14] Y. Freund. Boosting a weak learning algorithm by majority. Information and Computation, 121(2):256–285, 1995.