Vinh Thanh Ho, Hoai An Le Thi, Dinh Chien Bui, Online DC optimization for Online Binary Linear Classification.

Abstract: This paper concerns online algorithms for online binary linear classification (OBLC) problems in Machine learning. In a sense of “online” classification, an instance sequence is given step by step and on each round, these problems consist in finding a linear classifier for predicting to which label a new instance belongs. In OBCL, the quality of predictions is assessed by a loss function, specifically 0–1 loss function. In fact, this loss function is nonconvex, nonsmooth and thus, such problems become intractable. In literature, Perceptron is a well-known online classification algorithm, in which one substitutes a surrogate convex loss function for the 0–1 loss function. In this paper, we investigate an efficient DC loss function which is a suitable approximation of the usual 0–1 loss function. Basing on Online DC (Difference of Convex functions) programming and Online DCA (DC Algorithms) [10], we develop an online classification algorithm. Numerical experiments on several test problems show the efficiency of our proposed algorithm with respect to Perceptron.


Keywords: Online DC optimization, Online DCA, Perceptron, Online binary classification, DC programming, DCA.


Citation: Ho Vinh Thanh, Le Thi Hoai An, Bui Dinh Chien, Online DC Optimization for Online Binary Linear Classification. In: Nguyen N.T., Trawiński B., Fujita H., Hong TP. (eds) Intelligent Information and Database Systems. ACIIDS 2016. Lecture Notes in Computer Science, vol 9622, pp. 661-670, Springer, Berlin, Heidelberg, 2016.


Download link