介紹多核學習(multiple kernel learning)中的優化問題,主要是Semidefinite Program(SDP)和Quadratically Constrained Quadratic Program(QCQP)。
優化領域小學生來報道,最近在看多核學習(multiple kernel learning),本文follow封面圖中的paper[1],整理一下MKL中所涉及到的一些優化問題,主要是Semidefinite Program(SDP)和Quadratically Constrained Quadratic Program(QCQP);學藝不精,一知半(不)解,歡迎大家批評指正。
1.Kernel Method
關於kernel method和一些kernel-based learning algorithm,科普介紹有很多了,更多詳細內容也可以去仔細閱讀那本黃皮書[2],我這裡就簡單鋪一下。
1.1. Criteria Used in Kernel Method
1.1.1. Hard Margin
如果對這個優化問題感到陌生的,不明白為什麼它可以實現maximal margin的,可以去看一下黃皮書[2]的4.5 Separating Hyperplanes,這裡不再贅述了。
The hard margin solution exists only when the labeled sample is linearly separable in feature space.
1.1.2. 1-norm Soft Margin
1.1.3. 2-norm Soft Margin
可以看到,(Dual_HM)、(Dual_SM1)、(Dual_SM2)都是convex Quadratic Program(QP)問題。
Kernel Alignment不講了。。。
2. SDP和QCQP的等價關係
關於SDP的更多詳細介紹,推薦本公眾號的另一篇文章:《優化|半正定規劃(SDP)的形象理解和基本原理》。
3. Algorithms for Learning Kernels
3.1. Convex Subset of PSD matrices
3.2. Linear Combination of a Set of Kernel Matrices
3.3. Linear Combination with Non-negative Parameters
4. 寫在最後
我知道這是篇很老的paper了,而且現在大家可能更多focus在deep learning上面,但可以的話,我還是想聽聽機器學習領域做相關研究的同學來講講這個方法目前的研究和應用,先謝過了~ 最後,感謝閱讀這一堆枯燥的公式。
參考文獻
[1] G. R. G. Lanckriet, N. Cristianini, P. Bartlett, L. E. Ghaoui and M. I. Jordan, Learning the Kernel Matrix with Semidefinite Programming, Journal of Machine Learning Research, 5(Jan): 27 - 72, 2004.
[2] T. Hastie, R. Tibshirani and J. Friedman, The Elements of Statistical Learning: Data Mining, Inference, and Prediction, Springer Science & Business Media, 2009.
旨在為讀者帶來運籌學/優化理論最專業和前沿的資訊與報道,及其在供應鏈管理、人工智能等學科的交叉應用。專欄主編多為世界名校OR博士,50多位審稿人由全球高校教授、研究院科學家、企業CTO等組成。歡迎有稿費投稿,敬請加入全球最大華人運籌學社區。
閱讀更多 留德華叫獸 的文章