Low-degree Polynomial Mapping of Data for SVM

支持向量機常使用非線性映射函數將資料點映到高維度空間，以便於將非線性分布的資料點分類。核心函數則可以解決映射到高維度空間之後的資料向量有過多特徵而難以訓練的問題。然而，在大規模資料上訓練支持向量機所需的時間相當長。本論文根據最近在訓練大規模線性支持向量機(不使用非線性核心的支持向量機)上的研究，提出一個在所需訓練時間與測試準確度之間取得平衡的方法。本研究將線性支持向量機的快速訓練方法應用於以低階多項式映射函數展開的資料上。此方法有快速訓練的好處，同時可以達到與使用高度非線性核心函數相近的測試準確度。實驗顯示在特定大規模資料集上，所提方法確實可以以較少的時間得出相近的準確度。Non-linear mapping functions have long been used in SVM to transform data into a higher dimensional space, allowing the classifier to separate non-linearly distributed data instances. Kernel tricks are used to avoid the problem of a huge number of features of the mapped data point. However, the training/testing for large data is often time consuming. Following the recent advances in training large linear SVM (i.e., SVM without using nonlinear kernels), this work proposes a method that strikes a balance between the training/testing speed and the testing accuracy. We apply the fast training method for linear SVM to the expanded form of data under low-degree polynomial mappings. The method enjoys the fast training/testing, but may achieve testing accuracy close to that of using highly nonlinear kernels. Empirical experiments show that the proposed method is useful for certain large-scale data sets.TABLE OF CONTENTS試委員審定書 . .. . . . . . . . . . . . . . . . . . . . i文摘要 . . . . . . . . . . . . . . . . . . . .. .. . . iiBSTRACT . . . . . . . . . . . . . . . . . . . . . . .. iiiIST OF TABLES . . . . . . . . . . . . . . . . . . . . . viHAPTER. Introduction . . . . . . . . . . . . . . . . . . . . . 1I. Support Vector Machines . . . . . . . . . . . . . . . 4.1 Linear Support Vector Machines . . . . . . . . . . . 4.2 Nonlinear Support Vector Machines . . . . . . . . . . 5II. Decomposition Methods. . . . . . . . . . . . . . . . 7.1 Decomposition Methods for Nonlinear SVM . . . . . . . 7.2 Decomposition Methods for Linear SVM. . . . . . . . . 9V. Training/Testing Low-degree Polynomial Mappings of Datasing Linear SVM . . . . . . . . . . . . . . . . . . . . 12.1 Low-degree Polynomial Mappings . . . . . . . . . . . 12.2 Number of Nonzero Features per Instance. . . . . . . 13.3 Training by Decomposition Methods. . . . . . . . . . 14.4 Training by Other Methods for Linear SVM . . . . . . 16.5 Relations with the RBF kernel. . . . . . . . . . . . 16.6 Parameter Selection. . . . . . . . . . . . . . . . . 17.7 Prediction . . . . . . . . . . . . . . . . . . . . . 17.8 Multi-class Classification. . . . . . . . . . . . . . 18. Experiments . . . . . . . . . . . . . . . . . . . . . 19.1 Data Sets and Implementations. . . . . . . . . . . . 19.2 Analysis of φ(x) and w. . . . . . . . . . . . . . . 21.3 Calculating or Storing φ(xi) . . . . . . . . . . . 22.4 Accuracy and Time of Using Linear, Degree-2 Polynomial, and RBF . . . . . . . . . . . . . . . . . . . . . . . . 23I. Discussions and Conclusions . . . . . . . . . . . . 27PPENDICES . . . . . . . . . . . . . . . . . . . . . . . 29IBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . . 3