Incremental and Decremental Proximal Support
Vector Classification using Decay Coefficients
Amund Tveit, Magnus Lie Hetland and H°
Department of Computer and Information Science,
Norwegian University of Science and Technology,
N-7491 Trondheim, Norway
Abstract. This paper presents an efficient approach for supporting decre-
mental learning for incremental proximal support vector machines (SVM).
The presented decremental algorithm based on decay coefficients is com-
pared with an existing window-based decremental algorithm, and is shown
to perform at a similar level in accuracy, but providing significantly bet-
ter computational performance.
Support Vector Machines (SVMs) is an exceptionally efficient data mining ap-
proach for classification, clustering and time series analysis [5, 12, 4]. This is
primarily due to SVMs highly accurate results that are competitive with other
data mining approaches, e.g. artificial neural networks (ANNs) and evolution-
ary algorithms (EAs). In recent years tremendous growth in the amount of data
gathered (e.g. user clickstreams on the web, in e-commerce and in intrusion de-
tection systems), has changed the focus of SVM classifier algorithms to not only
provide accurate results, but to also enable online learning, i.e. incremental and
decremental learning, in order to handle concept drift of classes [2, 13].
Fung and Mangasarian introduced the Incremental and Decremental Linear
Proximal Support Vector Machine (PSVM) for binary classification , and
showed that it was able to be trained extremely fast, i.e. with 1 billion examples
(500 increments of 2 million) in 2 hours and 26 minutes on relatively low-end
hardware (400 MHz Pentium II). This has later been extended to support effi-
cient support of incremental multicategorical classification . Proximal SVMs
has also been shown to perform at a similar level of accuracy as regular SVMs
and at the same time being significantly faster .
In this paper we propose a computationally efficient algorithm that enables
decremental support for Incremental PSVMs using a weight decay coefficient.
The suggested approach is compared the current time-window based approach
proposed by Fung and Mangasarian .
Incremental and Decremental PSVM Classifiers