1.引文

SVM是機器學習里面最強大最好用的工具之一，它試圖在特征空間里尋找一個超平面，以最小的錯分率把正負樣本分開。它的強大之處還在于，當樣本在原特征空間中線性不可分，即找不到一個足夠好的超平面時，可以利用核（kernel）函數，將特征映射到希爾伯特（Hilbert）空間。后者一般維度更高，通過這樣的映射之后，樣本在新的特征空間中便是線性可分的了。

記得剛剛學習SVM的時候，對“核”這個詞很恐懼，一直理解不了它究竟是什么。在看MKL的時候，又經常會遇到“核矩陣”（kernel matrices）這個詞。現在說一下我的理解。

剛才說過，我們通過核把特征從低維空間映射到高維空間。舉例來說，我們看下面的多項式核函數：

其中x,y是兩個樣本，他們的特征分別是(x1,x2)，(y1,y2)，通過這個核函數，可以看到二維特征被映射到了六維特征。而且我們也可以理解，這個映射其實就是用一個矩陣A乘以原來的特征(x1,x2)得到的。矩陣A也就是核矩陣了。一個核函數對應一個核矩陣。

2.基本概念闡述

????特征融合：主要用來描述各種不同的特征融合方式，常見的方式有前期融合，就是前面所描述的將各個特征拼接在一起，后期融合本文后面會提到

????核函數：SVM遇到線性不可分問題時，可以通過核函數將向量映射到高維空間，在高維空間線性可分

????多核學習：在利用SVM進行訓練時，會涉及核函數的選擇問題，譬如線性核，rbf核等等，多核即為融合幾種不同的核來訓練。

3.應用背景

????在圖片搜索中，會出現這樣的一類badcase，圖像的內容和描述圖像的文本不一致，經常會有文本高相關，而圖像完全不一致的情況。解決這類問題的一個思路就是綜合利用圖像的內容分類屬性和文本的query分類屬性，看兩者的匹配程度做相應策略。

4.分類方法的選取

對分類熟悉的同學，馬上可能要說出，這還不easy，抽取各種特征，然后一拼接，隨便找個分類器，設定幾個參數，馬上分類模型文件就出來啦，80%準確率沒問題。

????圖像的分類問題跟一般的分類問題方法本質上沒太大差異，主要差異體現在特征的抽取上以及特征的計算時間上。

????圖像特征的抽取分為兩部分，一部分是針對通用圖像的特征，還有一部分則是針對特定類別抽取的特征。這些特征與普通的文本特征不一致的地方在于，一個圖像特征由于存在分塊、采樣、小波變換等，可能維度就已經很高。譬如常見的MPEG-7標準中提到的一些特征，邊緣直方圖150維，顏色自相關特征512維等。在分類過程中，如果將這些特征拼接在一起直接就可能過千維，但是實際在標注樣本時，人工標注的正負樣本也才幾千張，所以在選擇分類器時，挑選svm，該分類器由于可以在眾多分類面中選擇出最優分界面，以及在小樣本的學習中加入懲罰因子產生一定軟邊界，可以有效規避overfitting。

????在特征的計算時間上，由于圖像處理涉及的矩陣計算過多，一個特征的計算時間慢的可以達到0.3秒，所以如何挑選出既有效又快速的特征也非常重要。

5.兩種特征融合方式的比較

????那剛才的方法有什么問題呢？

仔細想想，大致存在以下幾點問題：

???? 1. 你所提取的所有特征，全部串在一起，一定合適么？如果我想知道哪些特征組合在一起效果很好，該怎么辦？

???? 2. 用svm進行學習時，不同的特征最適合的核函數可能不一樣，那我全部特征向量串在一起，我該如何選擇核函數呢？

???? 3. 參數的選取。不同的特征即使使用相同的核，可能最適合的參數也不一樣，那么如何解決呢？

???? 4. 全部特征都計算，計算時間的花銷也是挺大的

對于剛才的問題，如果用前期融合，可能是用下面方式來解決：

???? 1. 根據經驗，覺得在樣本中可能表現不錯的特征加進來，至于組合么，全部串在一起，或者選幾個靠譜的串一起，慢慢試驗，慢慢調，看哪些特征有改進就融合在一起

???? 2. 也是根據經驗，選取普遍表現不錯的RBF核，總之結果應該不會差

???? 3. 交叉驗證是用來干嘛的？驗證調優參數唄，全部特征融合在一起，再來調，盡管驗證時間長，不要緊，反正模型是離線訓練的，多調會也沒關系。

????那是否有更好的選擇方案呢？

? ??我們學過的SVM都是單核（single kernel）的，在使用的時候，需要我們根據經驗或試驗來選擇用哪種核函數、怎樣指定它的參數，這樣很不方便。另一方面，實際應用當中，特征往往不是single domain的，而是異構的。拿圖像分類來說，我們可能用到顏色相關的特征、紋理相關的特征、空間相關的特征，這幾類特征對應的最佳的核函數未必相同，讓他們共用同一個核函數，未必能得到最優的映射。對這些問題的思考，就引出了MKL。

簡單地說，我們給定一些basekernels，比如linear,Polynomial,RBF,Sigmoid，對于每一個，可以指定多組參數，也就是一共有M個base kernels，我們想用它們的線性組合來作為最終的核函數。通過training，得到這個線性組合中每個kernel的權重d（weight）。由于融合了各種kernel，可以照顧到異構的特征；由于自動學習權重，我們就不需要費腦子想究竟用哪一個核哪一種參數，把可能的核、參數都拿過來，組合著來用就可以了。

多核學習(MKL)可能是個不錯的選擇，該方法屬于后期融合的一種，通過對不同的特征采取不同的核，對不同的參數組成多個核，然后訓練每個核的權重，選出最佳核函數組合來進行分類。

與傳統的單核SVM的不同，就是除了要學習w、b之外，還要學習上面提到的權重d。這樣的話，decision function, cost function都會有些變化，棘手的是，cost function 的求解不再是一個convex problem，傳統的優化方法就不適用了。近年來MKL比較熱，很多論文都是在優化方法上面下功夫，企圖達到更快的收斂速度、更好的解。具體的優化方法就比較復雜了，略去。

????先看下簡單的理論描述：

????普通SVM的分類函數可表示為：

????

????其中為待優化參數，物理意義即為支持向量樣本權重，用來表示訓練樣本屬性，正樣本或者負樣本，為計算內積的核函數，為待優化參數。

????其優化目標函數為：

????

???? 其中用來描述分界面到支持向量的寬度，越大，則分界面寬度越小。C用來描述懲罰因子，而則是用來解決不可分問題而引入的松弛項。

???? 在優化該類問題時，引入拉格朗日算子，該類優化問題變為：

?????

???? 其中待優化參數在數學意義上即為每個約束條件的拉格朗日系數。

???? 而MKL則可認為是針對SVM的改進版，其分類函數可描述為：

?????

???? 其中，表示第K個核函數，則為對應的核函數權重。

???? 其對應的優化函數可以描述為：

?????

???? 在優化該類問題時，會兩次引入拉格朗日系數，參數與之前相同，可以理解為樣本權重，而則可理解為核函數的權重，其數學意義即為對每個核函數引入的拉格朗日系數。具體的優化過程就不描述了，不然就成翻譯論文啦~，大家感興趣的可以看后面的參考文檔。

???? 通過對比可知，MKL的優化參數多了一層其物理意義即為在該約束條件下每個核的權重。

???? Svm的分類函數形似上是類似于一個神經網絡，輸出由中間若干節點的線性組合構成，而多核學習的分類函數則類似于一個比svm更高一級的神經網絡，其輸出即為中間一層核函數的輸出的線性組合。其示意圖如下：

?????

???? 在上圖中，左圖為普通SVM示例，而全圖則為MKL示例。其中為訓練樣本，而為不同的核函數，為支持向量權重(假設三個訓練樣本均為支持向量)，為核權重，y為最終輸出分類結果。

6.實驗過程與相關應用

????以實際對地圖類別的分類為例，目前用于分類的特征有A，B，C，D，E，F，G(分別用字母代表某特征)，這些特征每個的維數平均幾百維。

???? 準備工作：

???? 1. 人工標注地圖類別正負樣本，本次標注正樣本176張，負樣本296張

???? 2. 提取正負訓練樣本圖片的A~G各個特征

???? 3. 歸一化特征

???? 4. 為每個特征配置對應的核函數，以及參數

???? 工具：

????Shogun工具盒：http://www.shogun-toolbox.org/，其中關于該工具的下載，安裝，使用實例都有詳細說明。該工具除了提供多核學習接口之外，幾乎包含所有機器學習的工具，而且有多種語言源碼，非常方便使用。

????結果測試：

????經過大約5分鐘左右的訓練，輸出訓練模型文件，以及包含的核函數權重、準確率。

????在該實例中，7個特征分別用七個核，其權重算出來為：

????0.048739 0.085657 0.00003 0.331335 0.119006 0.00000 0.415232，

????最終在測試樣本上準確率為：91.6%

????為了節省特征抽取的時間，考慮去掉權重較小的特征A、C、F，

????拿剩下4個核訓練，幾分鐘后，得到核函數權重如下：

????0.098070 0.362655 0.169014 0.370261，

????最終在測試樣本上準確率為：91.4%

????在這次訓練中，就可以節約抽取A、C、F特征的訓練時間，并且很快知道哪些特征組合在一起會有較好的結果。

????實驗的幾點說明：

???? 1. 該類別的分類，因為樣本在幾百的時候就已經達到不錯效果，所以選取數目較少。

???? 2. 該實驗是針對每個特征選擇一個核，且每個核配置固定參數，實際中如果時間允許，可以考慮每個特征選不同核，同一核可以選取不同參數，這樣可以得到稍微更好的結果。

???? 參考文章：

????Large Scale Multiple Kernel Learning

????SimpleMKL

????Representing shape with a spatial pyramid kernel

????參考代碼：http://www.shogun-toolbox.org/doc/cn/current/libshogun_examples.html

多核線性組合，最經典的是simpleMKL，也被作為MKL的具體實現，應用在了計算機各領域。為了使MKL應用地更廣，應對各種特征組合、各種樣本量級，后來又有人提出了GMKL，G即Generalized，最優化方法用的是PGD（Projected Gradient Descend）。為了改進收斂效果，Vishwanathan又提出SPG-GMKL(Spectral Projected Gradient)，同時提出了多核的product組合。SPG-GMKL也被后來者視作state-of-art。

除了MKL，還有一個MKB(Multiple Kernel Boosting)，大連理工大學的盧湖川有幾篇論文就是用MKB做跟蹤。論文生成MKB是基于MKL的，我覺得不然。請看MKB的框架圖：

這里的確用到多核，但每一個SVM都是單核的，根本沒有用到多核訓練的東西。本質上就是訓練出M * N個single-kernel SVM，然后用boosting的方法，把這些弱分類器ensemble為一個強分類器。用到的就是傳統的SVM加傳統的boosting，只是名字新，實質并無新意。

TKDE12 有一篇 MKBoost論文，這應該是正宗的MKB，它提出了一個框架，并提供了幾個formulation，然后與MKL做了比較。論文中全是公式，沒有看，以后需要的時候再研究吧。

MKL的經典實現有SimpleMKL，Shogun，SPG-GMKL，SMO-MKL。

如果只是要使用MKL，可以不看論文中的推導，更多的是看看上述幾種實現附帶的例子；可以看看MKL在跟蹤、圖像分類中的使用，輸入輸出是什么；可以看看這個和這個教程。

7.個人經驗與總結：

????1. 多核學習在解釋性上比傳統svm要強。多核學習可以明顯的看到各個子核中哪些核在起作用，哪些核在一起合作效果比較好。

???? 2. 關于參數優化。曾經做過實驗，關于同一特征選用同一核，但是不同參數，組合成多個核，也可以提升分類準確率。

???? 3. 多核學習相比前期特征融合在性能上會有3%~5%左右的提升。

???? 4. 通過特征選擇，可以節約特征計算時間。