Solving Support Vector Machine with Many Examples

• Autorzy: Białoń P.
• Języki publikacji: EN

Abstrakty

EN

Various methods of dealing with linear support vector machine (SVM) problems with a large number of examples are presented and compared. The author believes that some interesting conclusions from this critical analysis applies to many new optimization problems and indicates in which direction the science of optimization will branch in the future. This direction is driven by the automatic collection of large data to be analyzed, and is most visible in telecommunications. A stream SVM approach is proposed, in which the data substantially exceeds the available fast random access memory (RAM) due to a large number of examples. Formally, the use of RAM is constant in the number of examples (though usually it depends on the dimensionality of the examples space). It builds an inexact polynomial model of the problem. Another author's approach is exact. It also uses a constant amount of RAM but also auxiliary disk files, that can be long but are smartly accessed. This approach bases on the cutting plane method, similarly as Joachims' method (which, however, relies on early finishing the optimization).

Słowa kluczowe

EN

concept drift; convex optimization; data mining; network failure detection; stream processing; support vector machine

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2010
• Tom: nr 3
• Strony: 65--70
• Opis fizyczny: Bibliogr. 8 poz., rys., tab.

Twórcy

autor

Białoń P.

• National Institute of Telecommunications, Szachowa st 1, 04-894 Warsaw, Poland,

Bibliografia

• [1] E. Ikonomovska, D. Gorgevik, and S. Loskovska, “A survey of stream data mining”, in Proc. 8th Nat. Conf. Int. Particip. ETAI 2007, Ohrid, Republic of Macedonia, 2007, pp. I6-2.
• [2] T. Joachims, “Training linear SVMs in linear time”, in Proc. ACM Conf. KDD 2006, Philadelphia, USA, 2006, pp. 217–226.
• [3] P. Białoń, “A linear Support Vector Machine solver for a huge number of training examples”, Control Cybern. (to appear).
• [4] D. R. Musicant, “Data mining via mathematical programing and machine learning”. Ph.D. thesis, University of Wisconsin, Madison, 2000.
• [5] V. N. Vapnik, The Nature of Statistical Learning Theory. New York: Springer, 1995.
• [6] Yu. Nesterov, “Complexity estimates of some cutting plane methods based on the analytic barrier”, Math. Program., vol. 69, 149–176, 1995.
• [7] J. Kelley, “The cutting plane method for solving convex programs”, J. Soc. Ind. Appl. Mathem., vol. 8, pp. 703–712, 1960.
• [8] A. Bordes and L. Bottou, “The Huller: a simple and efficient online SVM”, in Machine Learning: ECML-2005, Lect. Notes Artif. Int. Springer, pp. 505–512.