利用索引技術達到低於線性時間的支持向量機訓練

Abstract

多維索引已頻繁用於在各種應用中的次線性時間近鄰搜索。在本文中，我們展示這種技術如何與與次線性稀疏學習問題結合，像是Ramp損失函數的SVM。我們提出一種outlier-free的凸鬆弛來解Ramp損失函數的SVM，並利用索引達到次線性時間的最佳化演算法，該演算法能在數據不能裝入記憶體的情境下解決大規模的問題。我們分別在充足和有限記憶體的條件下，與既有的線性SVM、Ramp損失SVM比較，其中我們的演算法不僅快許多倍，在大規模嘈雜的資料上亦能達到更好的精準度。

Multidimensional indexing has been frequently used for sublinear-time nearest neighbor search in various applications. In this paper, we demonstrate how this technique can be integrated into learning problem with sublinear sparsity like ramp-loss SVM. We propose an outlier-free convex-relaxation for ramp-loss SVM and an indexed optimization algorithm which solves large-scale problem in sublinear-time even when data cannot fit into memory. We compare our algorithm with state-of-the-art linear hinge-loss solver and ramp-loss solver in both sufficient and limited memory conditions, where our algorithm not only learns several times faster but achieves more accurate result on noisy and large-scale datasets.