Sparsity 的最重要的客戶
大概要屬 high dimensional data 了吧。現(xiàn)在的機(jī)器學(xué)習(xí)問(wèn)題中，具有非常高維度的數(shù)據(jù)隨處可見(jiàn)。例如，在文檔或圖片分類(lèi)中常用的 bag of words 模型里，如果詞典的大小是一百萬(wàn)，那么每個(gè)文檔將由一百萬(wàn)維的向量來(lái)表示。高維度帶來(lái)的的一個(gè)問(wèn)題就是計(jì)算量：在一百萬(wàn)維的空間中，即使計(jì)算向量的內(nèi)積這樣的基本操作也會(huì)是非常費(fèi)力的。不過(guò)，如果向量是稀疏的的話（事實(shí)上在
bag of words 模型中文檔向量通常都是非常稀疏的），例如兩個(gè)向量分別只有 L1 和 L2 個(gè)非零元素，那么計(jì)算內(nèi)積可以只使用 min(L1,L2)次乘法完成。因此稀疏性對(duì)于解決高維度數(shù)據(jù)的計(jì)算量問(wèn)題是非常有效的。
當(dāng)然高維度帶來(lái)的問(wèn)題不止是在計(jì)算量上。例如在許多生物相關(guān)的問(wèn)題中，數(shù)據(jù)的維度非常高，但是由于收集數(shù)據(jù)需要昂貴的實(shí)驗(yàn)，因此可用的訓(xùn)練數(shù)據(jù)卻相當(dāng)少，這樣的問(wèn)題通常稱(chēng)為small n,
large p problem
——我們一般用 n 表示數(shù)據(jù)點(diǎn)的個(gè)數(shù)，用 p 表示變量的個(gè)數(shù)，即數(shù)據(jù)維度。當(dāng) p?n 的時(shí)候，不做任何其他假設(shè)或者限制的話，學(xué)習(xí)問(wèn)題基本上是沒(méi)法進(jìn)行的。因?yàn)槿绻蒙纤凶兞康脑挘?nobr>p 越大，通常會(huì)導(dǎo)致模型越復(fù)雜，但是反過(guò)來(lái) n 有很小，于是就會(huì)出現(xiàn)很?chē)?yán)重的
overfitting 問(wèn)題。例如，最簡(jiǎn)單的線性回歸模型：
f(x)=∑j=1pwjxj=wTx
使用 square loss 來(lái)進(jìn)行學(xué)習(xí)的話，就變成最小化如下的問(wèn)題
J(w)=1n∑i=1n(yi?f(xi))2=1n∥y?Xw∥2
這里 X=(x1,…,xn)T∈Rn×p 是數(shù)據(jù)矩陣，而 y=(y1,…,yn)T
eq:
1 ?
w?=(XTX)?1XTy
然而，如果 p>n 的話，矩陣 XTX 將會(huì)不是滿秩的，而這個(gè)解也沒(méi)法算出來(lái)?；蛘吒_切地說(shuō)，將會(huì)有無(wú)窮多個(gè)解。也就是說(shuō)，我們的數(shù)據(jù)不足以確定一個(gè)解，如果我們從所有可行解里隨機(jī)選一個(gè)的話，很可能并不是真正好的解，總而言之，我們
overfitting 了。
解決 overfitting 最常用的辦法就是 regularization ，例如著名的 ridge regression 就是添加一個(gè) ?2 regularizer
：
JR(w)=1n∥y?Xw∥2+λ∥w∥2
直觀地來(lái)看，添加這個(gè) regularizer 會(huì)使得模型的解偏向于 norm 較小的 w 。從凸優(yōu)化的角度來(lái)說(shuō)，最小化上面這個(gè) J(w) 等價(jià)于如下問(wèn)題：
minw1n∥y?Xw∥2,s.t.∥w∥≤C
其中 C 是和 λ 一一對(duì)應(yīng)的是個(gè)常數(shù)。也就是說(shuō)，我們通過(guò)限制 w 的
norm 的大小實(shí)現(xiàn)了對(duì)模型空間的限制，從而在一定程度上（取決于 λ 的大?。┍苊饬? overfitting 。不過(guò) ridge regression 并不具有產(chǎn)生稀疏解的能力，得到的系數(shù) w 仍然需要數(shù)據(jù)中的所有特征才能計(jì)算預(yù)測(cè)結(jié)果，從計(jì)算量上來(lái)說(shuō)并沒(méi)有得到改觀。
不過(guò)，特別是在像生物或者醫(yī)學(xué)等通常需要和人交互的領(lǐng)域，稀疏的解除了計(jì)算量上的好處之外，更重要的是更具有可解釋性
。比如說(shuō)，一個(gè)病如果依賴(lài)于 5 個(gè)變量的話，將會(huì)更易于醫(yī)生理解、描述和總結(jié)規(guī)律，但是如果依賴(lài)于 5000 個(gè)變量的話，基本上就超出人肉可處理的范圍了。
在這里引入稀疏性的方法是用 ?1 regularization
代替 ?2 regularization，得到如下的目標(biāo)函數(shù)
eq:
2 ?
JL(w)=1n∥y?Xw∥2+λ∥w∥1
該問(wèn)題通常被稱(chēng)為 LASSO (least absolute shrinkage and selection operator) 。LASSO 仍然是一個(gè) convex optimization 問(wèn)題，不過(guò)不再具有解解析解。它的優(yōu)良性質(zhì)是能產(chǎn)生稀疏性，導(dǎo)致 w中許多項(xiàng)變成零。
可是，為什么它能產(chǎn)生稀疏性呢？這也是一直讓我挺感興趣的一個(gè)問(wèn)題，事實(shí)上在之前申請(qǐng)學(xué)校的時(shí)候一次電話面試中我也被問(wèn)到了這個(gè)問(wèn)題。我當(dāng)時(shí)的回答是背后的理論我并不是很清楚，但是我知道一個(gè)直觀上的理解。下面我們就先來(lái)看一下這個(gè)直觀上的理解。
首先，很 ridge regression 類(lèi)似，上面形式的 LASSO 問(wèn)題也等價(jià)于如下形式：
minw1n∥y?Xw∥2,s.t.∥w∥1≤C
也就是說(shuō)，我們將模型空間限制在 w 的一個(gè) ?1-ball
中。為了便于可視化，我們考慮兩維的情況，在 (w1,w2) 平面上可以畫(huà)出目標(biāo)函數(shù)的等高線，而約束條件則成為平面上半徑為 C 的一個(gè)
norm ball 。等高線與 norm ball 首次相交的地方就是最優(yōu)解。如圖 (fig:
1) 所示：
fig:
1 ?
?1-ball
meets quadratic function. ?1-ball
has corners. It’s very likely that the meet-point is at one of the corners.
?2-ball
meets quadratic function. ?2-ball
has no corner. It is very unlikely that the meet-point is on any of axes."
可以看到，?1-ball
與 ?2-ball
的不同就在于他在和每個(gè)坐標(biāo)軸相交的地方都有角
出現(xiàn)，而目標(biāo)函數(shù)的測(cè)地線除非位置擺得非常好，大部分時(shí)候都會(huì)在角的地方相交。注意到在角的位置為產(chǎn)生稀疏性，例如圖中的相交點(diǎn)就有 w1=0 ，而更高維的時(shí)候（想象一下三維的 ?1-ball
是什么樣的？）除了角點(diǎn)以外，還有很多邊的輪廓也是既有很大的概率成為第一次相交的地方，又會(huì)產(chǎn)生稀疏性。
相比之下，?2-ball
就沒(méi)有這樣的性質(zhì)，因?yàn)闆](méi)有角，所以第一次相交的地方出現(xiàn)在具有稀疏性的位置的概率就變得非常小了。這就從直觀上來(lái)解釋了為什么 ?1 regularization
能產(chǎn)生稀疏性，而 ?2 regularization
不行的原因了。
不過(guò)，如果只限于 intuitive 的解釋的話，就不那么好玩了，但是背后完整的理論又不是那么容易能夠搞清楚的，既然這次的標(biāo)題是 Basics ，我們就先來(lái)看一個(gè)簡(jiǎn)單的特殊情況好了。
接下來(lái)我們考慮 orthonormal design 的情況：(1/n)XTX=I 。然后看看
LASSO 的解具體是什么樣子。注意 orthonormal design 實(shí)際上是要求特征之間相互正交。這可以通過(guò)對(duì)數(shù)據(jù)進(jìn)行 PCA 以及模長(zhǎng) normalize 來(lái)實(shí)現(xiàn)。
注意到 LASSO 的目標(biāo)函數(shù) (eq:
2) 是 convex 的，根據(jù) KKT 條件，在最優(yōu)解的地方要求 gradient?JL(w)=0 。不過(guò)這里有一點(diǎn)小問(wèn)題： ?1-norm
不是光滑的，不存在 gradient ，所以我們需要用一點(diǎn) subgradient 的東西。
def:
1 ?
定義 subgradient;
subdifferential
對(duì)于在 p 維歐氏空間中的凸開(kāi)子集 U 上定義的實(shí)值函數(shù) f:U→R ，一個(gè)向量 p 維向量 v 稱(chēng)為 f 在一點(diǎn) x0∈U 處的
subgradient ，如果對(duì)于任意 x∈U ，滿足
f(x)?f(x0)≥v?(x?x0)
由在點(diǎn)
x0 處的所有
subgradient 所組成的集合稱(chēng)為
x0 處的
subdifferential ，記為
?f(x0) 。
注意 subgradient 和 subdifferential 只是對(duì)凸函數(shù)定義的。例如一維的情況， f(x)=|x| ，在 x=0 處的
subdifferential 就是 [?1,+1] 這個(gè)區(qū)間（集合）。注意在 f 的
gradient 存在的點(diǎn)，subdifferential 將是由 gradient 構(gòu)成的一個(gè)單點(diǎn)集合。這樣就將 gradient 的概念加以推廣了。這個(gè)推廣有一個(gè)很好的性質(zhì)。
性質(zhì) condition
for global minimizer
點(diǎn)
x0 是凸函數(shù)
f 的一個(gè)全局最小值點(diǎn)，當(dāng)且僅當(dāng)
0∈?f(x0) 。
證明很簡(jiǎn)單，將 0∈?f(x0) 帶入定義 (def:
1) 中的那個(gè)式子立即就可以得到。有了這個(gè)工具之后，就可以對(duì) LASSO 的最優(yōu)解進(jìn)行分析了。在此之前，我們先看一下原始的 least square 問(wèn)題的最優(yōu)解 (eq:
1) 現(xiàn)在變成了什么樣子，由于 orthonormal design ，我們有
eq:
3 ?
w?=1nXTy
然后我們?cè)賮?lái)看 LASSO ，假設(shè) wˉ=(wˉ1,…,wˉp)T 是 JL(w) 的全局最優(yōu)值點(diǎn)。考慮第 j個(gè)變量 wˉj ，有兩種情況。
gradient 存在，此時(shí) wˉj≠0
由于 gradient 在最小值點(diǎn)必須要等于零，我們有
?JL(w)?wj∣∣∣wˉj=0
亦即
?2n(XTy?XTXwˉ)j+λsign(wˉj)=0
根據(jù) orthonormal design 性質(zhì)以及 least square 問(wèn)題在 orthonormal design 時(shí)的解 (eq:
3) 化簡(jiǎn)得到
wˉj=w?j?λ2sign(wˉj)
從這個(gè)式子也可以明顯看出 wˉj 和 w?j 是同號(hào)的，于是 sign(wˉj) 等于 sign(w?j) ，所以上面的式子變?yōu)?/p>
wˉj=w?j?λ2sign(w?j)=sign(w?j)(∣∣w?j∣∣?λ2)
再用一次 sign(w?j)=sign(wˉj) ，兩邊同時(shí)乘以 sign(wˉj) ，可以得到
∣∣w?j∣∣?λ2=∣∣wˉj∣∣≥0
于是剛才的式子可以進(jìn)一步寫(xiě)為
eq:
4 ?
wˉj=sign(w?j)(∣∣w?j∣∣?λ2)+
這里 (x)+=max{x,0} 表示 x 的正部。
gradient 不存在，此時(shí) wˉj=0
根據(jù) subgradient 在最小值點(diǎn)處的性質(zhì)的性質(zhì)，此時(shí)比有
0=wˉj∈?JL(wˉ)={?2n(XTy?XTXwˉ)j+λe:e∈[?1,1]}={2wˉj?2w?j+λe:e∈[?1,1]}
亦即存在 e0∈[?1,1] 使得
0=2wˉj?2w?j+λe0=2w?j+λe0
于是
|w?j|=λ2|e0|≤λ2
又因?yàn)?wˉj=0 ，所以這個(gè)時(shí)候式子也可以統(tǒng)一為 (eq:
4) 的形式。 如此一來(lái)，在 orthonormal design 的情況下，LASSO 的最優(yōu)解就可以寫(xiě)為 (eq:
4) ，可以用圖 (fig:
2) 形象地表達(dá)出來(lái)。
fig:
2 ?
圖上畫(huà)了原始的 least square 解，LASSO 的解以及 ridge regression 的解，用上面同樣的方法（不過(guò)由于 ridge regularizer 是 smooth 的，所以過(guò)程卻簡(jiǎn)單得多）可以得知 ridge regression 的解是如下形式
21+2λw?j
可以 ridge regression 只是做了一個(gè)全局縮放，而 LASSO 則是做了一個(gè) soft thresholding ：將絕對(duì)值小于 λ/2 的那些系數(shù)直接變成零了，這也就更加令人信服地解釋了
LASSO 為何能夠產(chǎn)生稀疏解了。
上面的文字，前半段看懂了，后半段功力不夠，還沒(méi)有看懂
下面就講下個(gè)人的直觀理解：
l2正則可以防止參數(shù)估計(jì)的過(guò)擬合，但是選擇合適lambda比較困難，需要交叉驗(yàn)證。如果有個(gè)特征與輸出結(jié)果不相關(guān)，則L2會(huì)給一個(gè)特別小的值，但是不會(huì)為0.
l1正則會(huì)產(chǎn)生稀疏解，即不相關(guān)的的特征對(duì)應(yīng)的權(quán)重為0，就相當(dāng)于降低了維度。但是l1的求解復(fù)雜度要高于l2,并且l1更為流行
聲明：本網(wǎng)頁(yè)內(nèi)容旨在傳播知識(shí)，若有侵權(quán)等問(wèn)題請(qǐng)及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com
