hi 各位，今天我們來深入了解一下Seurat做多樣本整合的深入算法窒篱，CCA算法以及FindIntegrationAnchors函數(shù)中的的參數(shù)l2.norm

先來知道一下CCA

典型關(guān)聯(lián)分析(Canonical Correlation Analysis贡避，以下簡(jiǎn)稱CCA)是最常用的挖掘數(shù)據(jù)關(guān)聯(lián)關(guān)系的算法之一。比如我們拿到兩組數(shù)據(jù)，第一組是人身高和體重的數(shù)據(jù)奏夫，第二組是對(duì)應(yīng)的跑步能力和跳遠(yuǎn)能力的數(shù)據(jù)。那么我們能不能說這兩組數(shù)據(jù)是相關(guān)的呢历筝？CCA可以幫助我們分析這個(gè)問題酗昼。

1. CCA概述

在數(shù)理統(tǒng)計(jì)里面，我們都知道相關(guān)系數(shù)這個(gè)概念漫谷。假設(shè)有兩組一維的數(shù)據(jù)集X和Y仔雷，則相關(guān)系數(shù)ρ
的定義為:

圖片.png

其中cov(X,Y)是X和Y的協(xié)方差，而D(X),D(Y)分別是X和Y的方差舔示。相關(guān)系數(shù)ρ的取值為[-1,1],　ρ的絕對(duì)值越接近于1碟婆，則X和Y的線性相關(guān)性越高。越接近于0惕稻，則X和Y的線性相關(guān)性越低竖共。
雖然相關(guān)系數(shù)可以很好的幫我們分析一維數(shù)據(jù)的相關(guān)性，但是對(duì)于高維數(shù)據(jù)就不能直接使用了俺祠。拿上面我們提到的公给，如果X是包括人身高和體重兩個(gè)維度的數(shù)據(jù)，而Y是包括跑步能力和跳遠(yuǎn)能力兩個(gè)維度的數(shù)據(jù)蜘渣，就不能直接使用相關(guān)系數(shù)的方法淌铐。那我們能不能變通一下呢？CCA給了我們變通的方法蔫缸。
CCA使用的方法是將多維的X和Y都用線性變換為1維的X'和Y'腿准，然后再使用相關(guān)系數(shù)來看X'和Y'的相關(guān)性。將數(shù)據(jù)從多維變到1位拾碌，也可以理解為CCA是在進(jìn)行降維吐葱，將高維數(shù)據(jù)降到1維，然后再用相關(guān)系數(shù)進(jìn)行相關(guān)性的分析校翔。下面我們看看CCA的算法思想弟跑。

2. CCA的算法思想

上面我們提到CCA是將高維的兩組數(shù)據(jù)分別降維到1維，然后用相關(guān)系數(shù)分析相關(guān)性防症。但是有一個(gè)問題是孟辑，降維的標(biāo)準(zhǔn)是如何選擇的呢哎甲？回想下主成分分析PCA（參考文章單細(xì)胞PCA分析的降維原理），降維的原則是投影方差最大扑浸；再回想下線性判別分析LDA烧给，降維的原則是同類的投影方差小，異類間的投影方差大喝噪。對(duì)于我們的CCA础嫡，它選擇的投影標(biāo)準(zhǔn)是降維到1維后，兩組數(shù)據(jù)的相關(guān)系數(shù)最大酝惧。
現(xiàn)在我們具體來討論下CCA的算法思想榴鼎。假設(shè)我們的數(shù)據(jù)集是X和Y，X為n1×m的樣本矩陣晚唇。Y為n2×m的樣本矩陣.其中m為樣本個(gè)數(shù)巫财，而n1,n2分別為X和Y的特征維度。
對(duì)于X矩陣哩陕，我們將其投影到1維平项，或者說進(jìn)行線性表示，對(duì)應(yīng)的投影向量或者說線性系數(shù)向量為a, 對(duì)于Y矩陣悍及，我們將其投影到1維闽瓢，或者說進(jìn)行線性表示，對(duì)應(yīng)的投影向量或者說線性系數(shù)向量為b, 這樣X ,Y投影后得到的一維向量分別為X',Y'心赶。我們有

圖片.png

圖片.png

圖片.png

圖片.png

圖片.png

圖片.png

3. CCA算法的SVD求解
   對(duì)于上面的優(yōu)化目標(biāo)埂材，我們可以做一次矩陣標(biāo)準(zhǔn)化塑顺，就可以用SVD來求解了。

   
   
   圖片.png
   
   

   也就是說俏险，我們的優(yōu)化目標(biāo)變成下式：

   
   
   圖片.png
   
   仔細(xì)一看严拒，如果將u和v看做矩陣
   圖片.png
   的某一個(gè)奇異值對(duì)應(yīng)的左右奇異向量。那么利用奇異值分解竖独，我們可以得到M=UΣVT,其中U,V分別為M的左奇異向量和右奇異向量組成的矩陣裤唠，而Σ為M的奇異值組成的對(duì)角矩陣。由于U,V所有的列都為標(biāo)準(zhǔn)正交基莹痢，則uTU和VTv得到一個(gè)只有一個(gè)標(biāo)量值為1种蘸，其余標(biāo)量值為0的向量。此時(shí)我們有
   
   圖片.png
   
   
   也就是說我們最大化
   圖片.png
   ,其實(shí)對(duì)應(yīng)的最大值就是某一組左右奇異向量所對(duì)應(yīng)的奇異值的最大值竞膳。也就是將M做了奇異值分解后航瞭，最大的奇異值就是我們優(yōu)化目標(biāo)的最大值，或者說我們的X和Y之間的最大相關(guān)系數(shù)顶猜。利用對(duì)應(yīng)的左右奇異向量u,v我們也可以求出我們?cè)嫉腦和Y的線性系數(shù)
   圖片.png
   沧奴。
   可以看出，SVD的求解方式非常簡(jiǎn)潔方便长窄。但是如果你不熟悉SVD的話滔吠，我們也可以用傳統(tǒng)的拉格朗日函數(shù)加上特征分解來完成這個(gè)函數(shù)的優(yōu)化。
4. CCA算法的特征分解求解　　
   特征分解方式就比較傳統(tǒng)了挠日，利用拉格朗日函數(shù)疮绷，優(yōu)化目標(biāo)轉(zhuǎn)化為最大化下式：
   
   圖片.png
   
   分別對(duì)a,b求導(dǎo)并令結(jié)果為0，我們得到：
   
   圖片.png
   
   將上面第一個(gè)式子左乘a^T,第二個(gè)式子左乘b^T嚣潜，并利用
   圖片.png
   冬骚，我們得到
   
   圖片.png
   
   其實(shí)也就是說我們的拉格朗日系數(shù)就是我們要優(yōu)化的目標(biāo)。我們繼續(xù)將上面的兩個(gè)式子做整理懂算，第一個(gè)式子左乘S^?1_XX,第二個(gè)式子左乘S^?1_YY只冻，我們得到：
   
   圖片.png
   
   將上面第二個(gè)式子帶入第一個(gè)式子，我們得到
   
   圖片.png
   
   這個(gè)式子我們就熟悉了计技，這不就是特征分解嗎喜德！要求最大的相關(guān)系數(shù)λ,我們只需要對(duì)矩陣
   圖片.png
   
   做特征分解，找出最大的特征值取平方根即可垮媒，此時(shí)最大特征值對(duì)應(yīng)的特征向量即為X的線性系數(shù)a舍悯。
   同樣的辦法航棱，我們將上面第一個(gè)式子帶入第二個(gè)式子，我們得到
   
   圖片.png
   , 我們只需要對(duì)矩陣
   圖片.png
   
   做特征分解萌衬，找出最大的特征值取平方根即可饮醇，此時(shí)最大特征值對(duì)應(yīng)的特征向量即為Y的線性系數(shù)b。
   可以看出特征分解的方法要比SVD復(fù)雜秕豫，但是兩者求得的結(jié)果其實(shí)是等價(jià)的朴艰，只要利用SVD和特征分解之間的關(guān)系就很容易發(fā)現(xiàn)兩者最后的結(jié)果相同。
5. CCA算法流程

圖片.png

6. CCA算法小結(jié)
   CCA算法廣泛的應(yīng)用于數(shù)據(jù)相關(guān)度的分析馁蒂，同時(shí)還是偏最小二乘法的基礎(chǔ)呵晚。但是由于它依賴于數(shù)據(jù)的線性表示，當(dāng)我們的數(shù)據(jù)無法線性表示時(shí)沫屡，CCA就無法使用饵隙，此時(shí)我們可以利用核函數(shù)的思想，將數(shù)據(jù)映射到高維后沮脖，再利用CCA的思想降維到1維金矛，求對(duì)應(yīng)的相關(guān)系數(shù)和線性關(guān)系，這個(gè)算法一般稱為KCCA勺届。
   此外驶俊，我們?cè)谒惴ɡ镏徽伊讼嚓P(guān)度最大的奇異值或者特征值，作為數(shù)據(jù)的相關(guān)系數(shù)免姿，實(shí)際上我們也可以像PCA一樣找出第二大奇異值饼酿，第三大奇異值，胚膊。故俐。。得到第二相關(guān)系數(shù)和第三相關(guān)系數(shù)紊婉。然后對(duì)數(shù)據(jù)做進(jìn)一步的相關(guān)性分析药版。但是一般的應(yīng)用來說，找出第一相關(guān)系數(shù)就可以了喻犁。
   有時(shí)候我們的矩陣S_XX,S_YY不可逆槽片，此時(shí)我們得不到對(duì)應(yīng)的逆矩陣，一般遇到這種情況可以對(duì)S_XX,S_YY進(jìn)行正則化肢础，將S_XX,S_YY變化為
   圖片.png
   ,然后繼續(xù)求逆还栓。其中γ為正則化系數(shù)。

深入理解L1传轰、L2正則化

我們?cè)谟肧eurat做多樣本整合的過程中蝙云，不僅僅用到了CCA的算法，其中還有一個(gè)參數(shù)l2.norm路召，那L2正則化是什么勃刨，為什么我們分析的時(shí)候一般添加這個(gè)參數(shù)、

1. L2 正則化直觀解釋

L2 正則化公式非常簡(jiǎn)單股淡，直接在原來的損失函數(shù)基礎(chǔ)上加上權(quán)重參數(shù)的平方和：

圖片.png

其中身隐，Ein 是未包含正則化項(xiàng)的訓(xùn)練樣本誤差，λ 是正則化參數(shù)唯灵，可調(diào)贾铝。但是正則化項(xiàng)是如何推導(dǎo)的？接下來埠帕，我將詳細(xì)介紹其中的物理意義垢揩。

我們知道，正則化的目的是限制參數(shù)過多或者過大敛瓷，避免模型更加復(fù)雜叁巨。例如，使用多項(xiàng)式模型呐籽，如果使用 10 階多項(xiàng)式锋勺，模型可能過于復(fù)雜，容易發(fā)生過擬合狡蝶。所以庶橱，為了防止過擬合，我們可以將其高階部分的權(quán)重 w 限制為 0贪惹，這樣苏章，就相當(dāng)于從高階的形式轉(zhuǎn)換為低階。

為了達(dá)到這一目的奏瞬，最直觀的方法就是限制 w 的個(gè)數(shù)枫绅，但是這類條件屬于 NP-hard 問題，求解非常困難丝格。所以撑瞧，一般的做法是尋找更寬松的限定條件：

圖片.png

上式是對(duì) w 的平方和做數(shù)值上界限定，即所有w 的平方和不超過參數(shù) C显蝌。這時(shí)候预伺，我們的目標(biāo)就轉(zhuǎn)換為：最小化訓(xùn)練樣本誤差 Ein，但是要遵循 w 平方和小于 C 的條件曼尊。

下面酬诀，我用一張圖來說明如何在限定條件下，對(duì) Ein 進(jìn)行最小化的優(yōu)化骆撇。

這里寫圖片描述

如上圖所示瞒御，藍(lán)色橢圓區(qū)域是最小化 Ein 區(qū)域，紅色圓圈是 w 的限定條件區(qū)域神郊。在沒有限定條件的情況下肴裙，一般使用梯度下降算法趾唱，在藍(lán)色橢圓區(qū)域內(nèi)會(huì)一直沿著 w 梯度的反方向前進(jìn)，直到找到全局最優(yōu)值 wlin蜻懦。例如空間中有一點(diǎn) w（圖中紫色點(diǎn)）甜癞，此時(shí) w 會(huì)沿著 -?Ein 的方向移動(dòng)，如圖中藍(lán)色箭頭所示宛乃。但是悠咱，由于存在限定條件，w 不能離開紅色圓形區(qū)域征炼，最多只能位于圓上邊緣位置析既，沿著切線方向。w 的方向如圖中紅色箭頭所示谆奥。

那么問題來了眼坏，存在限定條件，w 最終會(huì)在什么位置取得最優(yōu)解呢雄右？也就是說在滿足限定條件的基礎(chǔ)上空骚，盡量讓 Ein 最小。

我們來看擂仍，w 是沿著圓的切線方向運(yùn)動(dòng)囤屹，如上圖綠色箭頭所示。運(yùn)動(dòng)方向與 w 的方向（紅色箭頭方向）垂直逢渔。運(yùn)動(dòng)過程中肋坚，根據(jù)向量知識(shí)，只要 -?Ein 與運(yùn)行方向有夾角肃廓，不垂直智厌，則表明 -?Ein 仍會(huì)在 w 切線方向上產(chǎn)生分量，那么 w 就會(huì)繼續(xù)運(yùn)動(dòng)盲赊，尋找下一步最優(yōu)解铣鹏。只有當(dāng) -?Ein 與 w 的切線方向垂直時(shí)，-?Ein在 w 的切線方向才沒有分量哀蘑，這時(shí)候 w 才會(huì)停止更新诚卸，到達(dá)最接近 wlin 的位置，且同時(shí)滿足限定條件绘迁。

這里寫圖片描述

-?Ein 與 w 的切線方向垂直合溺，即 -?Ein 與 w 的方向平行。如上圖所示缀台，藍(lán)色箭頭和紅色箭頭互相平行棠赛。這樣，根據(jù)平行關(guān)系得到：

圖片.png

移項(xiàng)，得：

圖片.png

這樣睛约，我們就把優(yōu)化目標(biāo)和限定條件整合在一個(gè)式子中了鼎俘。也就是說只要在優(yōu)化 Ein 的過程中滿足上式，就能實(shí)現(xiàn)正則化目標(biāo)痰腮。

接下來而芥，重點(diǎn)來了！根據(jù)最優(yōu)化算法的思想：梯度為 0 的時(shí)候膀值，函數(shù)取得最優(yōu)值。已知 ?Ein 是 Ein 的梯度误辑，觀察上式沧踏，λw 是否也能看成是某個(gè)表達(dá)式的梯度呢？

當(dāng)然可以巾钉！λw 可以看成是 1/2λw*w 的梯度：

圖片.png

這樣翘狱，我們根據(jù)平行關(guān)系求得的公式，構(gòu)造一個(gè)新的損失函數(shù)：

圖片.png

之所以這樣定義砰苍，是因?yàn)閷?duì) Eaug 求導(dǎo)潦匈，正好得到上面所求的平行關(guān)系式。上式中等式右邊第二項(xiàng)就是 L2 正則化項(xiàng)赚导。

這樣茬缩， 我們從圖像化的角度，分析了 L2 正則化的物理意義吼旧，解釋了帶 L2 正則化項(xiàng)的損失函數(shù)是如何推導(dǎo)而來的凰锡。

2. L1 正則化直觀解釋

L1 正則化公式也很簡(jiǎn)單，直接在原來的損失函數(shù)基礎(chǔ)上加上權(quán)重參數(shù)的絕對(duì)值：

圖片.png

我仍然用一張圖來說明如何在 L1 正則化下圈暗，對(duì) Ein 進(jìn)行最小化的優(yōu)化掂为。

這里寫圖片描述

Ein 優(yōu)化算法不變还最，L1 正則化限定了 w 的有效區(qū)域是一個(gè)正方形脱篙，且滿足 |w| < C杰扫⊙镀眩空間中的點(diǎn) w 沿著 -?Ein 的方向移動(dòng)溢十。但是氓侧，w 不能離開紅色正方形區(qū)域瓢喉，最多只能位于正方形邊緣位置楣富。其推導(dǎo)過程與 L2 類似访忿，此處不再贅述瞧栗。

3. L1 與 L2 解的稀疏性

介紹完 L1 和 L2 正則化的物理解釋和數(shù)學(xué)推導(dǎo)之后，我們?cè)賮砜纯此鼈兘獾姆植夹浴?/p>

這里寫圖片描述

以二維情況討論海铆，上圖左邊是 L2 正則化迹恐，右邊是 L1 正則化。從另一個(gè)方面來看卧斟，滿足正則化條件殴边，實(shí)際上是求解藍(lán)色區(qū)域與黃色區(qū)域的交點(diǎn)憎茂，即同時(shí)滿足限定條件和 Ein 最小化。對(duì)于 L2 來說锤岸，限定區(qū)域是圓竖幔，這樣，得到的解 w1 或 w2 為 0 的概率很小是偷，很大概率是非零的拳氢。

對(duì)于 L1 來說，限定區(qū)域是正方形蛋铆，方形與藍(lán)色區(qū)域相交的交點(diǎn)是頂點(diǎn)的概率很大馋评，這從視覺和常識(shí)上來看是很容易理解的。也就是說刺啦，方形的凸點(diǎn)會(huì)更接近 Ein 最優(yōu)解對(duì)應(yīng)的 wlin 位置留特，而凸點(diǎn)處必有 w1 或 w2 為 0。這樣玛瘸，得到的解 w1 或 w2 為零的概率就很大了蜕青。所以，L1 正則化的解具有稀疏性糊渊。

擴(kuò)展到高維右核，同樣的道理，L2 的限定區(qū)域是平滑的再来，與中心點(diǎn)等距蒙兰；而 L1 的限定區(qū)域是包含凸點(diǎn)的，尖銳的芒篷。這些凸點(diǎn)更接近 Ein 的最優(yōu)解位置搜变，而在這些凸點(diǎn)上，很多 wj 為 0针炉。

關(guān)于 L1 更容易得到稀疏解的原因挠他，有一個(gè)很棒的解釋，請(qǐng)見下面的鏈接：

https://www.zhihu.com/question/37096933/answer/70507353

4. 正則化參數(shù) λ

正則化是結(jié)構(gòu)風(fēng)險(xiǎn)最小化的一種策略實(shí)現(xiàn)篡帕，能夠有效降低過擬合殖侵。損失函數(shù)實(shí)際上包含了兩個(gè)方面：一個(gè)是訓(xùn)練樣本誤差。一個(gè)是正則化項(xiàng)镰烧。其中拢军，參數(shù) λ 起到了權(quán)衡的作用。

這里寫圖片描述

以 L2 為例怔鳖，若 λ 很小茉唉，對(duì)應(yīng)上文中的 C 值就很大。這時(shí)候，圓形區(qū)域很大度陆，能夠讓 w 更接近 Ein 最優(yōu)解的位置艾凯。若 λ 近似為 0，相當(dāng)于圓形區(qū)域覆蓋了最優(yōu)解位置懂傀，這時(shí)候趾诗，正則化失效，容易造成過擬合蹬蚁。相反恃泪，若 λ 很大，對(duì)應(yīng)上文中的 C 值就很小犀斋。這時(shí)候悟泵，圓形區(qū)域很小，w 離 Ein 最優(yōu)解的位置較遠(yuǎn)闪水。w 被限制在一個(gè)很小的區(qū)域內(nèi)變化，w 普遍較小且接近 0蒙具，起到了正則化的效果球榆。但是，λ 過大容易造成欠擬合禁筏。欠擬合和過擬合是兩種對(duì)立的狀態(tài)持钉。

數(shù)學(xué)太難了，真的要吐了

生活很好篱昔，有你更好