滴滴研究院副院長葉傑平：大規模稀疏和低秩學習（上）

機器學習移動互聯網人工智能美國雷鋒網 2017-03-29

編者按：本文根據葉傑平教授在中國人工智能學會AIDL第二期人工智能前沿講習班【機器學習前沿】所作報告《大規模稀疏和低秩學習》編輯整理而來。

葉傑平滴滴研究院副院長美國密歇根大學終身教授，密歇根大學大數據研究中心管理委員會成員，美國明尼蘇達大學博士畢業，現任滴滴研究院副院長。他擔任Data Mining and Knowledge Discovery, IEEE Transactions on Knowledge and Data Engineering, IEEE Transactions on Pattern Analysis and Machine Intelligence的編委. 2004年獲得ICML最佳學生論文獎。2010年獲得NSF CAREER Award。2010，2011，2012年分別獲得KDD最佳論文提名，2013年獲得KDD最佳學生論文獎。

以下內容是本次報告的上篇，由亞萌，夏睿共同編輯。雷鋒網(公眾號：雷鋒網)AI科技評論後續會整理出本次報告的下篇。

大家好！今天下午主要是跟大家分享這兩個領域的研究：稀疏和低秩。這個報告跟滴滴的應用沒有直接的關係。本次報告主要對一些基礎的稀疏模型，以及結構的稀疏模型進行講解，並會簡單介紹低秩的模型，以及一些優化加速算法，最後會給大家講一下如何將這些算法用在大規模的數據上。

Part 1 : 稀疏學習的一些基礎概念

稀疏學習的“稀疏”是指很多模型的係數是0，這裡是模型比較稀，可以是一維的，線性迴歸，或者矩陣的模型。

先講一下正則，從簡單一個線性的擬合，有這麼多點，用一條線去擬合這些點，這裡我們簡單用多項式（Polynomial），有M+1個參數，為了優化問題而把最佳的係數選出來。這個就是用線性迴歸，每個點有一個預測，預測是多項式給定，一個ground truth，我們希望找到係數，使這個誤差最小，這是非常常用的方式。

當M=0或1的時候是一條直線，當M=3或9的時候就成了曲線。這裡兩條曲線，一個是在訓練集上，一個是在測試集上，我們發現當M的值處於中間的時候，效果最好，兩頭都不行，這是機器學習裡常見的問題。當M=9的時候，一下子出現了過擬合。

所以模型需要加一個正則項，控制係數的大小。我們希望這個曲線擬合這個數據，係數也不要太大，太大就會overfit。超參數λ用來控制係數的大小，需要通過model selection選出來。

我們利用正則項q norm來控制參數的大小，來保證參數的絕對值比較小。q 可以取任意的值，當q大於等於1時，是凸函數，其中的好處是你可以在其中找到最優解。當q小於1時，就變成了非凸問題，找到最優解就比較困難了。所以1是一個臨界點。

L1為什麼得到稀疏解？

這裡我們給出一個簡單的例子，前面是loss函數，後面是正則項，可以看到一範式為凸但不可微，會在x＝0時取到極值點，二範式在零點可微，但是不一定在零點取得極值點，另外一種對於一範式稀疏的解釋是通過等高線的方式，可以發現一範式的約束能夠使得loss函數在零點相交的可能性更大，而二範式是一個球，與loss函數在零點相交的可能性不大，從而一範式能夠使得解稀疏。一範式最經典的就是96年的LASSO問題。

A是數據矩陣，每一行代表樣本，列代表特徵，有標籤y。用一個簡單的線性模型來預測y，那麼Ax-y就是一個擬合項，一範數就是正則項，使得x的係數稀疏，有很多是0，從而去掉一些無關項。這個好處就是，你自動做了一些特徵選擇。又選了特徵、又選了模型，這樣分析、推廣都比較方便一些。

下面是一個具體的應用實例，建造一個模型，區分這些腦成像，哪些是正常的，哪些是不正常的。其中要找到一些跟疾病相關的特徵。

之前提到的y都是比較簡單的，只有一列，但是很多場景下，y可能有很多值。比如說在Imaging Genetics，特徵可以是一個或者無數個基因。比如說把腦區變成很多個區，每個區域的體積或者面積作為一個Y，這樣這個Y有幾百個。還可以圖像每個點是一維，這樣Y也可以是幾百萬，X是幾百萬的，Y也是幾百萬的，兩邊都非常大，這個模型就從100萬變成了100萬的平方。這個時候如果不加正則項，問題就沒法解。這時模型可以用稀疏，先假設這個矩陣非常低，這樣參數個數減少很多。

我的一個合作者進行了一個比較大的項目，把世界上200多個醫院所有的數據整合在一起，有兩三萬個數據，但仍然不算很多，未來的數據如果越來越大的話，模型會越來越精確，現有數據不足，所以只能對模型加入很多假設，從而保證模型的有效性。當然，數據還是第一重要的，數據量如果不夠大，這個模型無論怎麼學可能都還是有問題的。

稀疏學習在很多領域中都有很廣泛的應用，如生物醫學，圖像處理，信號處理，神經科學，機器學習等等。在實際問題裡我們需要找到一個參數，一個常用的方法是使用交叉檢驗（cross validation），在一個廣泛的超參數空間中，選擇一個最優的參數，這種方法在稀疏模型裡可能會存在缺陷，一個更好的方法是使用stability selection，相當於對每個數據進行子採樣，然後進行多次篩選，選擇最好的參數。具體的可以在文章中查閱，裡面有很強的理論保證，因為它會對問題進行很多子採樣，所以會進行成千上萬次的lasso求解，因此需要一個特別快的算法，這也是我們今天主要要講的，如何讓模型在大規模的數據上進行計算。

Part 2: 四大結構化稀疏學習模型

下面講幾個模型。Lasso模型前面講到，好處是有理論保證，模型和特徵一起建立，非常容易推廣。我們知道，很多特徵是有結構的，特徵與特徵之間並不是獨立的。

我們首先介紹一些結構Lasso，這裡給出一個例子，特徵之間會有光滑性，我們給出了一個所有腦區的特徵，我們可以發現向鄰近的點會比較類似，特徵的光滑性有時間和空間上的光滑性，比如說，相鄰時刻之間的數據以及相鄰空間的數據是具有相似性的，所以很多問題都是有光滑性的，也會有一些問題具有一些樹的結構，以及一些問題可能具有一些網的結構，得到特徵值之間的相似性。當我們獲得我們的這些特徵之間的先驗知識之後，如果對lasso進行推廣，利用我們的特徵之間的關係，結構的lasso也就應運而生。和lasso類似，損失函數可以根據問題相關設計，如邏輯迴歸或者最小二乘迴歸等等，來表示對數據的擬合程度，重點是如何設計我們的penalty，lasso是L1 norm，僅僅是稀疏，特徵之間沒有任何假設，但是如果我們有特徵直接結構的先驗知識，那麼我們可以在正則項這裡進行推廣，一般是利用一個凸的方法，來得到我們需要的結構。

下面舉幾個例子。這裡我們根據結構的先驗信息，有Fused Lasso（光滑性），Graph Lasso（圖結構）, Group Lasso（組結構）以及樹結構Lasso（樹結構）。

• Fused Lasso（光滑性）

特徵有光滑性，相鄰的特徵會比較像。那麼penalty可以加一項，第一項還是稀疏，保證很多段都是0；除此之外，在利用數據的光滑性再加一項，就是說每相鄰兩項減一下，這樣就保證相鄰的是相近的，係數是相似的。每一段都是一個常數，而且很多都是稀疏的，這樣子就能夠簡化模型，降低模型的複雜性，同時實驗發現，這種方式能夠有效的提升符合這種特點的數據的效果。

• Graph Lasso（圖結構）

第二個推廣，如果你的結構是graph，比如蛋白質，哪些蛋白質是相關的，如果兩個特徵相關，這個可以簡單認為是剛才那個Fused LASSO的推廣。我們增加一個penalty，使得相關的特徵具有相同的結構。這個可以認為就是一個簡單的graph case，就是一條線，當然這個graph case也可以很複雜。這個缺點是，它是強相關的，所以不一定是正相關，可能是負相關的，這也是有可能的。比如很多場景，你提高我就下降了，但它的比例是類似的，這個時候需要加一個絕對值。你正1，我其實也可以負1，只要值類似就好了。

• Group Lasso（組結構）

第三個推廣是很多特徵會有一種組的結構，最典型的應用就是在腦影像的分析中，很多腦區或者體素之間有一定的組約束的，同時滴滴也有很多場景，如司機，終點，天氣等等，還有categorical variable。很多特徵必須放在一組裡才有一定的意義。因此group LASSO就是用來解決這種存在組結構的問題。

比如每個腦區可以當成一個group，基因我們知道有些group。假設categorical variable的值有四種模型：ATCG，怎麼去表達呢？一種方式就是變成向量，4種可能性，如最右圖所示。這四個特徵，其實單看其中一個是沒有什麼意義的，四個在一塊才是有意義的。這麼一個特徵用四維來表示，所以把這四個值作為一個group。所以早期發明group，就是解決這個categorical variable類型的問題。

下圖最左邊是 L1，挑了一些特徵，如果是有group structure的話，比如前面四個特徵是一個group、後面三個是一個group、最後四個是一個group。那麼每個group都是一個一個四維向量，你去算它的 q norm。比如q=2,算每個向量的長度，如果這裡有100個group，算出來是100個值，然後就把100個值加起來。這個導致的結果是說，group這個係數要麼一起等於0，或者都不等於0，也就是說這四個特徵如果在同一個組裡面，要麼全部被挑出來，要麼全部不挑出來。

一個應用就是Multi－task learning。假設Y有很多列，X也有很多列，每一行作為一個group加起來。這個結果是說，任何一個特徵要麼所有的task都有用，或者所有task都沒用。如果用這個模型來挑特徵，所有task挑出來的特徵是一樣的。

舉個例子，讓你去判斷寫的是什麼字母。有180個人來寫ABCD，你要去預測那個字母是什麼。因為每個人的寫法不一樣，所以有幾種做法，一種是把所有的人寫的所有的字母放塊，一個模型去預測，不管誰寫的全部放在一塊。

另外一個極端是，每個人建一個模型，因為每個人的寫法不一樣。兩種模型都有缺點。第一個模型的缺點是，它的樣本區別可能很大，用一個模型可能不能夠覆蓋所有的特徵。第二個模型的缺點是，每個人的樣本量可能不夠大，這會導致每個人的模型都不是特別精確。

而Multi-task learning就是在中間建一個模型，相當於兼顧到兩種方法。方法是：建180個模型，每個人都建立一個模型，同時每個模型是相關的，不是獨立的，所有模型一起學。

相關性怎麼建呢？我們希望所有的模型挑出的重要特徵是一樣的，所有特徵不同的模型綁在一塊，要麼都挑，要麼都不挑。這個結果比模型1、模型2都要好。

講一個滴滴應用的例子。它有一個場景是讓司機挑能跟他順路的乘客。這裡就有一個模型，看乘客是不是跟我順路的模型。那麼我就給乘客排序，把最順路的乘客放在最前面。

早期在大城市運行的時候，比如北京、上海這些訂單量比較大的城市，這個模型挺精確的，但放在小城市，這個模型就比較長，因為數據量不夠大，這個時候我們就採取了Multi-task learning。其實每個城市是一個模型，如果全部疊在一塊了，模型效果不好，因為每個城市的特徵不太一樣，交通狀況也不一樣，每個城市的生活、消費水平都不一樣。如果每個城市建一個模型也不好，因為小城市數據量不大效果不好。所以我們每個城市建一個模型，而每個模型又不是完全獨立的，有一些相關性，甚至可以遷移學習，大城市模型建好後直接可以遷移到小城市，這也是可以的。

• 樹結構Lasso（樹結構）

最後一個是樹。Group Lasso考慮的情況還是比較簡單，只是把特徵分成很多組。在很多場景下，特徵可以做更精細的劃分，比如先把它分成10個組，然後每個組的特徵又可以把它細分成10個組，有一個分層的結構，這個信息量會更大。就是說特徵的相似性是有這麼一個樹結構的，這個時候用group Lasso效果就不好，應該用樹，樹顯然是比group更加複雜一些。

我這裡舉一個例子，可能不是最恰當的例子，但能說明怎麼用。

假設我們每個樣本一個圖，這是腦成像的圖。這個樹結構，最上面表示整個圖，在這個樹的最頂端是整幅圖，如果把這個腦區每個橫縱都分四份，這樣把它分成16個小圖，第一層就16個節點；類似的往下每一個圖又分成16個，以此類推，組成一個樹結構。最後兩個節點之間的距離可以精確的表達特徵實際的相似性，這很多場景都是可以用的。

這裡可以建一個tree的Lasso，怎麼建呢？第一層，最上面是把所有特徵都放在上面。假設有8個特徵，最上面8個特徵都有。第二層有三個group，每一層把特徵劃分開，每一層都是group Lasso，再把每一層group Lasso加起來。

Part3 : 低秩模型

下面講一下低秩模型。很多問題都可以用矩陣來表示。通常，矩陣中的一些值是未知的，因此需要用觀測值去預測丟失值。比如說圖像，可能會有一些圖像被樹覆蓋，要用觀測值去預測被遮擋的部分。

或者說collaborative filtering，一種場景是行代表用戶，列代表電影，每個用戶被要求給電影打分，但不是所有的用戶都對所有的電影打分，所以我們需要去預測這些缺失的數據。

同樣滴滴有類似的問題，假設這個城市我們需要預測現在的交通狀況是順暢的還是擁堵的，我們有觀測值，只要某個區域有一輛我們平臺的車在開，就能知道它的速度，也就知道這個路段的交通狀況。但北京大部分區域我們沒有車在開，不知道交通狀況，這樣我們需要通過觀測的值去預測我們沒有觀測的值，這個非常重要，我們如果能知道北京現在所有路段的交通狀況，就能做很多事情，比如說路徑規劃，做A到B的時間預估等等，所以類似的有大部分區域是未知的問題，我們都需要去預測。

如果不做任何假設，這個問題是很難解決的。因此，我們引入低秩假設。

我們認為這個矩陣這些缺失值填進去之後得到的這個矩陣是低秩的，也就是說其實對每個問題它的主要核心的因素是少量的。數學上等價於希望最後得到的矩陣X 的秩（Rank）越小越好。Rank可以通過SVD分解，通過非零的奇異特徵數就是矩陣的rank。

低秩模型與稀疏模型比較類似，這裡我們假設紅色的是觀測點，白色為缺失點，X是我們需要預測的，該問題第一項為數據擬合項，我們需要M與X類似，同時希望我們填補之後的X能夠保持低秩特性，並用λ控制這個數量。由於rank是非奇異的，所以這會是一個NP難問題，常用的方法使用rank的上確界trace-norm來逼近它。同時trace-norm是一個連續的凸問題，這使得問題更加容易求解，且能夠使得奇異值變為零，最終獲得低秩。