結合Benders拆解法及分段線性近似法求解支援向量機之模型訓練問題

Integrating Bender’s Decomposition and Piecewise Linear Approximation for Solving Support Vector Machines

蘇洛民(Lo-Min Su)

指導教授 ： 陳勝一

國立交通大學/管理學院/工業工程與管理系所/碩士(2019年)

摘要

機器學習之模型訓練最佳化問題，目標在於決定最佳的模型參數以使預測誤差最小。就支援向量機而言，其目標在於找出一個超平面分隔兩組不同類別的觀察值，使組間距離最遠，且分類誤差亦為最小。模型訓練問題之目標函式為二次項次，再者問題規模依訓練資料集而定，通常需考慮非常龐大資料，為提升計算效能，本研究結合Benders拆解法及分段線性近似法進行求解，本研究進一步提出一整數支援向量機，使分數更為精確。實驗結果比較現有演算法與本研究提出方法之優劣。

關鍵字

Benders 拆解法 ； 分段線性近似法 ； 支援向量機

並列摘要

Machine learning optimization problem is to determine the parameters of a model to minimize errors based on the training data set. In the aspect of support vector machines, the problem is to obtain parameters of a linear system defined on feature space. The goal maximizes the distance between two parallel hyperplanes and minimizes classification errors. Such a model has been broadly utilized for data scientists to classify either labeled or unlabeled data. This thesis integrates Benders decomposition and linear approximation for solving the primal problem of support vector machines. For obtaining higher accuracy and lower error rate, we further proposed an integer SVM model to penalize the frequency of error. The results display computational performance and solution quality between the proposed method and existed algorithms.

並列關鍵字

Bender’s decomposition ； Support vector machines ； Piecewise linear approximation

參考文獻

Ayat, N. E., Cheriet, M., Remaki, L., & Suen, C. Y. (2001). KMOD-A new support vector machine kernel with moderate decreasing for pattern recognition. Application to digit image recognition. In Proceedings of Sixth International Conference on Document Analysis and Recognition (pp. 1215-1219). IEEE.

Ayat, N. E., Cheriet, M., & Suen, C. Y. (2005). Automatic model selection for the optimization of SVM kernels. Pattern Recognition, 38(10), 1733-1745.

Ban, G. Y., & Rudin, C. (2018). The big data newsvendor: Practical insights from machine learning. Operations Research, 67(1), 90-108.

Benders, J. F. (1962). Partitioning procedures for solving mixed-variables programming problems. Numerische mathematik, 4(1), 238-252.

Birge, J. R., & Louveaux, F. V. (1988). A multicut algorithm for two-stage stochastic linear programs. European Journal of Operational Research, 34(3), 384-392.