廣州熱線

AI課堂開(kāi)講，就差你了！

很多人說(shuō)，看了再多的文章，可是沒(méi)有人手把手地教授，還是很難真正地入門(mén)AI。為了將AI知識(shí)體系以最簡(jiǎn)單的方式呈現(xiàn)給你，從這個(gè)星期開(kāi)始，芯君邀請(qǐng)AI專業(yè)人士開(kāi)設(shè)“周末學(xué)習(xí)課堂”——每周就AI學(xué)習(xí)中的一個(gè)重點(diǎn)問(wèn)題進(jìn)行深度分析，課程會(huì)分為理論篇和代碼篇，理論與實(shí)操，一個(gè)都不能少！

來(lái)，退出讓你廢寢忘食的游戲頁(yè)面，取消只有胡吃海塞的周末聚會(huì)吧。未來(lái)你與同齡人的差異，也許就從每周末的這堂AI課開(kāi)啟了！

讀芯術(shù)讀者交流群，請(qǐng)加小編微信號(hào)：zhizhizhuji。等你。

全文共2571字，預(yù)計(jì)學(xué)習(xí)時(shí)長(zhǎng)6分鐘

暑期將至，不知道大家都計(jì)劃好怎么度假了嗎？先提醒一下，周末的課程不要忘記哦！

我們?cè)谇皟芍艿摹毒€性降維》和《非線性降維》中提到，降維的動(dòng)機(jī)之一就是在高維空間上，如果我們感興趣的只是某個(gè)低維分布，甚至樣本只分布在某個(gè)低維流形上，數(shù)據(jù)的采樣會(huì)面臨困難。實(shí)際上，按照傳統(tǒng)的辦法，在高維空間計(jì)算數(shù)據(jù)的內(nèi)積也會(huì)變得非常困難，所以我們盡量用降維的手段將一些操作拉到低維空間。

如果我們只考慮降維的話，似乎繞開(kāi)了高維空間內(nèi)積的麻煩，但對(duì)于某些實(shí)際問(wèn)題，我們做的不再是降低維度，而是升高維度。

比如，對(duì)于一個(gè)二分類(lèi)問(wèn)題，我們的目標(biāo)是尋找一個(gè)邊界將兩類(lèi)樣本很好的區(qū)分開(kāi)，這個(gè)邊界就叫做決策邊界（decision boundary）。我們更希望得到一個(gè)線性的形式，線性的決策邊界在數(shù)學(xué)上形式簡(jiǎn)單，同時(shí)具有可加性，非常容易做推廣，而非線性不僅形式復(fù)雜，還很容易導(dǎo)致過(guò)擬合。

在二維的特征空間上，左邊的圖是線性邊界，代表著樣本線性可分，右邊的圖是非線性邊界。

但在低維空間上，樣本往往是線性不可分的，而我們又想要找到一個(gè)線性邊界。那么我們就可以在輸入變量的特征空間做一個(gè)轉(zhuǎn)換：

，使得線性不可分的樣本變得線性可分，同時(shí)也使得原本表現(xiàn)很差的線性決策邊界在高維空間成為一個(gè)表現(xiàn)良好的決策邊界：

圖為原始二維空間經(jīng)過(guò)變換為三維空間，原本的非線性邊界也變成了一個(gè)平面，這個(gè)平面就是高維空間的決策邊界。

隨之帶來(lái)的問(wèn)題則是，我們?cè)诠烙?jì)參數(shù)的時(shí)候，無(wú)論是用Logistic Regression還是SVM，都會(huì)面臨樣本內(nèi)積的計(jì)算，在低維空間我們需要算

，在高維空間我們需要算

。隨著維度的升高，這樣的內(nèi)積計(jì)算就不再容易，我們甚至需要先做一個(gè)高維變換，再做內(nèi)積，這樣的計(jì)算復(fù)雜度就會(huì)非常高。

核技巧是什么

核技巧（kernel trick）是一種方法，我們用它可以非常方便地計(jì)算

。

很多教材上把SVM和核技巧放在一起，容易讓人以為核技巧只能在SVM中使用，同時(shí)SVM的對(duì)偶問(wèn)題和幾何意義以及相應(yīng)的最大硬間隔和最小軟間隔與核技巧一起出現(xiàn)，給人一種核技巧非常難以理解的感覺(jué)。

其實(shí)呢，核技巧不只應(yīng)用于SVM，大多數(shù)情況下，只要我們做了高維變換，同時(shí)需要計(jì)算

,那么我們都可以應(yīng)用核技巧來(lái)簡(jiǎn)化運(yùn)算。另一方面，核技巧其實(shí)非常簡(jiǎn)單，它就是用低維空間的內(nèi)積來(lái)求高維空間的內(nèi)積，省去了先做變換再求內(nèi)積的痛苦。

以多項(xiàng)式核為例，我們定義某個(gè)樣本x有個(gè)d分量：

我們做的高維變換是做一個(gè)多項(xiàng)式變換（degree=2），將d維擴(kuò)展：

需要注意的是，上面的式子存在很多重復(fù)項(xiàng)，比如

和

,但這并不重要，我們會(huì)在后面它們都會(huì)寫(xiě)成統(tǒng)一的形式。我們對(duì)變換后的樣本做內(nèi)積：

我們分別疊加一次項(xiàng)，二次項(xiàng)，四次項(xiàng)，其中，四次項(xiàng)也可以拆成：

我們注意到，各元素的相應(yīng)乘積再求和，正是內(nèi)積的定義：

所以這個(gè)degree為2的多項(xiàng)式變換的內(nèi)積可以寫(xiě)成：

這樣，我們就可以不先進(jìn)行高維變換，再在高維空間做內(nèi)積，而是直接在在低維空間做內(nèi)積，經(jīng)過(guò)簡(jiǎn)單的加法就可以得到我們想要的結(jié)果。

我們把等號(hào)后邊的形式叫做核函數(shù)（kernel function）：

。同時(shí)，我們可以發(fā)現(xiàn)，核函數(shù)交換x,y應(yīng)該保持不變，所以有

,這就是核函數(shù)的對(duì)稱性。

另外，對(duì)于每一組樣本都有著相應(yīng)的核函數(shù)表示，我們就可以很方便的寫(xiě)成矩陣的形式：

這其實(shí)就是由

所構(gòu)成的內(nèi)積矩陣，而內(nèi)積矩陣是半正定的。我們也把這個(gè)矩陣叫做核矩陣(kernel matrix).一般的，如果一個(gè)二元函數(shù)滿足了對(duì)稱性，以及構(gòu)成的內(nèi)積矩陣滿足了半正定性，就可以被當(dāng)作核函數(shù)來(lái)使用。這兩個(gè)條件一起構(gòu)成了傳說(shuō)中的Mercer Condition.

核技巧的使用

大家一定覺(jué)得，如果我們遇到以下兩個(gè)條件，那么就可以用到我們的核技巧：

? 存在低維到高維的映射：

? 求解形式中只有映射的內(nèi)積項(xiàng)，沒(méi)有關(guān)于映射的奇數(shù)次項(xiàng)：

其實(shí)呢，有一個(gè)更為強(qiáng)大的定理叫做表示定理（Representer Theorem）告訴我們，只要優(yōu)化問(wèn)題中的正則化項(xiàng)是遞增的，優(yōu)化函數(shù)的解總可以表示成核函數(shù)的線性組合，換而言之，滿足表示定理的內(nèi)蘊(yùn)屬性的優(yōu)化函數(shù)就一定可以用kernel trick 來(lái)進(jìn)行非線性拓展。

SVM中的核技巧

這可能是最著名的核技巧的使用場(chǎng)景。在SVM中，我們?nèi)绻紤]最大硬間隔，優(yōu)化問(wèn)題會(huì)變成異類(lèi)支持向量到?jīng)Q策邊界的距離之和最大化，同時(shí)滿足樣本劃分正確：

將數(shù)據(jù)從低維映射到高維：

繼續(xù)可以得到參數(shù)化的對(duì)偶問(wèn)題（這個(gè)足夠經(jīng)典，就不展開(kāi)講了）：

那么我們?cè)谟?jì)算

時(shí)就可以采用核技巧。如果你也是這樣理解SVM中的核技巧，那么這里面其實(shí)還隱藏另外一種更深刻的理解方法，有興趣的同學(xué)可以想一想：在對(duì)約束添加拉格朗日乘子后，對(duì)參數(shù)求導(dǎo)的過(guò)程，其實(shí)就是將參數(shù)表示為

的線性組合，而后續(xù)我們要做參數(shù)與

嶺回歸（ridge regression）中的核技巧

嶺回歸就是添加了

正則化的最小二乘估計(jì)，優(yōu)化函數(shù)為：

將數(shù)據(jù)從低維映射到高維:

因?yàn)檎齽t化項(xiàng)

明顯滿足單調(diào)遞增，所以根據(jù)表示定理，優(yōu)化函數(shù)的解可以表示為核函數(shù)的線性組合，即：

所以我們把優(yōu)化函數(shù)解的核函數(shù)形式代入到優(yōu)化函數(shù)中，可得：

所以，我們就可以把傳統(tǒng)的嶺回歸拓展為非線性學(xué)習(xí)方法。

值得注意的是，使用kernel trick時(shí)，往往會(huì)有過(guò)擬合的風(fēng)險(xiǎn)，因?yàn)榫S數(shù)變高，意味著在原始空間中的決策邊界會(huì)變的非常復(fù)雜。但SVM最大間隔劃分樣本下，卻在一定程度上減弱了這樣的過(guò)擬合風(fēng)險(xiǎn)。這也是為什么我們要在SVM中頻繁使用kernel trick，而在其他地方卻很少使用的原因之一。

讀芯君開(kāi)扒

課堂TIPS

? 正是因?yàn)楸硎径ɡ硖^(guò)強(qiáng)大，才使得我們將kernel trick用到各類(lèi)學(xué)習(xí)器上成為可能。事實(shí)上，我們可以同樣可以在Logistic Regression上使用kernel trick，推導(dǎo)方式與嶺回歸類(lèi)似。

? 不同的核函數(shù)會(huì)將原始的低維空間映射到不同維數(shù)的高維空間，例如，多項(xiàng)式核函數(shù)對(duì)應(yīng)的仍然是有限維，但是高斯核函數(shù)會(huì)對(duì)應(yīng)著的卻是無(wú)限維，因?yàn)樵谕茖?dǎo)過(guò)程中我們會(huì)發(fā)現(xiàn)高斯核函數(shù)的指數(shù)項(xiàng)對(duì)應(yīng)著一個(gè)無(wú)限維的泰勒展開(kāi)。

? 文中提到的Mercer Condition只是核函數(shù)的充分條件，而非必要條件。

? 大部分的書(shū)中都會(huì)寫(xiě)著多項(xiàng)式核函數(shù)：

,而有的書(shū)中還會(huì)添加兩個(gè)參數(shù)：

,而這兩個(gè)參數(shù)只是對(duì)數(shù)據(jù)進(jìn)行了放縮。比如，在d=2時(shí)，其實(shí)就是在做多項(xiàng)式變換時(shí)，常數(shù)項(xiàng)變?yōu)?/p>

,一次項(xiàng)乘以

，二次項(xiàng)乘以

。

? 在上一節(jié)中，我們提到了kernel PCA，它就是先把樣本映射到高維空間，然后在高維空間中做PCA，在具體的操作中，就是把原本的協(xié)方差矩陣的特征值分解換為核矩陣的特征值分解。

留言 點(diǎn)贊 發(fā)個(gè)朋友圈

我們一起探討AI落地的最后一公里