IEEE Trans Neural Netw Learn Syst. 2013 Apr;24(4):593-609. doi: 10.1109/TNNLS.2013.2238556.
The support vector machine (SVM) method, as a promising classification technique, has been widely used in various fields due to its high efficiency. However, SVM cannot effectively solve online classification problems since, when a new sample is misclassified, the classifier has to be retrained with all training samples plus the new sample, which is time consuming. According to the geometric characteristics of SVM, in this paper we propose an online SVM classifier called VS-OSVM, which is based on convex hull vertices selection within each class. The VS-OSVM algorithm has two steps: 1) the samples selection process, in which a small number of skeleton samples constituting an approximate convex hull in each class of the current training samples are selected and 2) the online updating process, in which the classifier is updated with newly arriving samples and the selected skeleton samples. From the theoretical point of view, the first d+1 (d is the dimension of the input samples) selected samples are proved to be vertices of the convex hull. This guarantees that the selected samples in our approach keep the greatest amount of information of the convex hull. From the application point of view, the new algorithm can update the classifier without reducing its classification performance. Experimental results on benchmark data sets have shown the validity and effectiveness of the VS-OSVM algorithm.
支持向量机（SVM）方法作为一种有前途的分类技术，由于其高效率而在各个领域得到了广泛应用。然而，SVM 不能有效地解决在线分类问题，因为当新样本被错误分类时，分类器必须使用所有训练样本加上新样本进行重新训练，这很耗时。根据 SVM 的几何特性，本文提出了一种称为 VS-OSVM 的在线 SVM 分类器，它基于每个类内凸壳顶点的选择。VS-OSVM 算法有两个步骤：1）样本选择过程，其中选择构成当前训练样本中每个类的近似凸壳的少量骨架样本；2）在线更新过程，其中用新到达的样本和选择的骨架样本更新分类器。从理论角度来看，前 d+1 个（d 是输入样本的维度）选择的样本被证明是凸壳的顶点。这保证了我们方法中选择的样本保持了凸壳的最大信息量。从应用角度来看，新算法可以在不降低分类性能的情况下更新分类器。在基准数据集上的实验结果表明了 VS-OSVM 算法的有效性和有效性。
