An Analytic Center Machine
Tóm tắt
Support vector machines have recently attracted much attention in the machine learning and optimization communities for their remarkable generalization ability. The support vector machine solution corresponds to the center of the largest hypersphere inscribed in the version space. Recently, however, alternative approaches (Herbrich, Graepel, & Campbell, In Proceedings of ESANN 2000) have suggested that the generalization performance can be further enhanced by considering other possible centers of the version space like the center of gravity. However, efficient methods for calculating the center of gravity of a polyhedron are lacking. A center that can be computed efficiently using Newton's method is the analytic center of a convex polytope. We propose an algorithm, that finds the hypothesis that corresponds to the analytic center of the version space. We refer to this type of classifier as the analytic center machine (ACM). Preliminary experimental results are presented for which ACMs outperform support vector machines.
Tài liệu tham khảo
Bazaraa, M. Z., Sherali, H. D., & Shetty C. M. (1993). Nonlinear Programming: Theory and Algorithms, New York, NY: John Wiley & Sons.
Blake, C. L. & Merz, C. J. (1998). UCI Repository of machine learning databases, http://www.ics.uci.edu/~mlearn/MLRepository.html.
Bouten, M., Schietse, J., & van den Broeck, C. (1995). Gradient descent learning in perceptrons: A review of its possibilities, Physical Review, E, 52:2, 1958-1967.
Herbrich, R., Graepel, T., & Campbell, C. (2000). Robust bayes point machines. In Proceedings of ESANN 2000. pp. 49-54.
Kaiser, M. J., Morin, T. L., & Trafalis, T. B. (1991). Centers and invariant points of convex bodies. In P. Gritzmann & B. Sturmfels (Eds), Applied geometry and discrete mathematics: The victor klee festschrift. AMS DIMACS Series in Discrete Mathematics and Theoretical Computer Science (pp. 367-385). American Mathematical Society, Providence, RI.
Mitchell, T. M. (1997). Machine Learning. McGraw-Hill.
Nesterov, Y. E. & Nemirovskii, A. S. (1994). Interior point polynomial methods in convex programming, Philadelphia: SIAM Publications.
Péton, O. & Vial, J.-Ph. (2000). A tutorialon ACCPM. Technical report, HEC/Logilab, University of Geneva. http://ecolu-info.unige.ch/logibab/software/accpm/index.html.
Rätsch G., Onoda, T., & Müller, K.-R. (2001). Soft margins for AdaBoost. Machine Learning, 42:2, 287-320. In press.
Ruján, P. (1997). Playing billard in version space. Neural Computation, 9, 99-122.
Schölkopf, B., Burges, C. J. C., & Smola, A. J. (1999). Advances in kernel methods: Support vector learning. Cambridge, Massachusetts: The MIT Press.
Smola, A. J. (1998). Learning with kernels, Ph.D. Thesis, Technical University, Berlin.
Smola, A., Bartlett, P., Schölkopf B., & Schuurmans, D. (2000). Advances in large margin classifiers. Cambridge, Massachusetts: The MIT Press.
Sonnevend, G. (1985). An analytical center for polyhedrons and then new classes of global algorithms for linear (smooth, convex) programming. Lectures Notes in Control Information Sciences (pp. 866-876). New York: Springer-Verlag.
Vapnik, V. (1995). The nature of statistical learning theory. Berlin: Springer Verlag.
Wright, M. H. (1995). Why a pure primal newton barrier step may be infeasible. SIAM Journal on Optimization, 5:1, 1-12.