線性單類支持向量機與支持向量數據域描述的對偶座標下降法

Dual Coordinate-Descent Methods for Linear One-Class SVM and SVDD

周弘逸(Hung-Yi Chou)

指導教授 ： 林智仁

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2019年)

https://doi.org/10.6342/NTU201902086

摘要

單類支持向量機和支持向量數據域描述是兩種有效的孤立點檢測技術,在核設定下,雖然這些技術已被成功使用在各項應用,但對於某些高維度資料,線性的,而非核的,單類支持向量機和支持向量數據域描述可以被考慮使用。過去於核化分類問題與線性分類問題的研究指出,特別設計過的最佳化演算法可以使線性的情況訓練更快速。然而,我們指出因為某些與標準線性支持向量機的差異,現有的演算法可能無法適用於單類的情況,於是我們為了線性單類支持向量機和支持向量數據域描述開發了一些新穎的座標下降法方法,並以實驗顯示了這些方法在於收斂速度的優勢。

關鍵字

區塊座標下降法 ； 單類支持向量機 ； 支持向量數據域描述

並列摘要

One-class SVM and support vector data description (SVDD) are two effective outlier detection techniques. They have been successfully applied to many applications under the kernel settings, but for some high dimensional data, linear rather than kernel one-class SVM and SVDD may be more suitable. Past developments on kernel and linear classification have indicated that specially designed optimization algorithms can make the training for linear scenarios much faster. However, we point out that because of some differences from standard linear SVM, existing algorithms may not be suitable for one-class scenarios. We then develop some novel coordinate descent methods for linear one-class SVM and SVDD. Experiments demonstrate their superiority on the convergence speed.

並列關鍵字

block coordinate descent ； one-class SVM ； support vector data description

參考文獻

C.-C. Chang and C.-J. Lin. LIBSVM: a library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2(3):27:1–27:27, 2011. Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm.

C.-C. Chiu, P.-Y. Lin, and C.-J. Lin. Two-variable block dual coordinate descent methods for large-scale linear support vector machines. Technical report, National Taiwan University, 2018. URL https://www.csie.ntu.edu.tw/~cjlin/papers/2var_cd/twocddual.pdf.

R.-E. Fan, P.-H. Chen, and C.-J. Lin. Working set selection using second order information for training SVM. Journal of Machine Learning Research, 6:889–1918, 2005. URL http://www.csie.ntu.edu.tw/~cjlin/papers/quadworkset.pdf.

C.-J. Hsieh, K.-W. Chang, C.-J. Lin, S. S. Keerthi, and S. Sundararajan. A dual coordinate descent method for large-scale linear SVM. In Proceedings of the Twenty Fifth International Conference on Machine Learning (ICML), 2008. URL http://www.csie.ntu.edu.tw/~cjlin/papers/cddual.pdf.

T. Joachims. Making large-scale SVM learning practical. In B. Scholkopf, C. J. C. Burges, and A. J. Smola, editors, Advances in Kernel Methods – Support Vector Learning, pages 169–184, Cambridge, MA, 1998. MIT Press.