大數(shù)據(jù)的挑戰(zhàn)與隨機(jī)機(jī)器學(xué)習(xí)算法

　數(shù)據(jù)規(guī)模的重要性
　　數(shù)據(jù)在不斷地增長(zhǎng)，數(shù)據(jù)量很大的時(shí)候是非常重要的一件事情，因?yàn)閿?shù)據(jù)只有到了一定的程度的量才會(huì)發(fā)生質(zhì)的變化，有一個(gè)例子是Matrix Completion（矩陣補(bǔ)全），就是給你一個(gè)表，有一部分的數(shù)據(jù)你知道，有一部分?jǐn)?shù)據(jù)你不知道，沒有辦法拆出來，這個(gè)東西就是矩陣補(bǔ)全。矩陣補(bǔ)全非常重要，幾乎所有的機(jī)器學(xué)習(xí)的問題都可以表示成矩陣補(bǔ)全的問題，這里顯示的聚類，也可以看成矩陣補(bǔ)全。
　　矩陣補(bǔ)全非常有意思的結(jié)果是怎樣的？我們這邊的橫軸是數(shù)據(jù)量，考慮在矩陣?yán)锬軌蚩吹降臄?shù)據(jù)量，縱軸是恢復(fù)誤差，拆出來的結(jié)果和真實(shí)結(jié)果的誤差，肯定是數(shù)據(jù)量越多拆的誤差越高，當(dāng)數(shù)據(jù)低于一定程度的時(shí)候，這可以是非常顯示的刻劃出來，在數(shù)據(jù)小于一定量的時(shí)候，不管怎么做總是拆的很糟糕，幾乎沒有太大的區(qū)別。只有當(dāng)你的數(shù)據(jù)大于一定量的時(shí)候，突然你可以拆的非常準(zhǔn)，如果按原來的說法，在一個(gè)的情況下，你可以拆的很完美，沒有任何的錯(cuò)誤。所以我們說大數(shù)據(jù)，只有當(dāng)數(shù)據(jù)到一定的程度的時(shí)候，有些事情才是可能的，當(dāng)你的數(shù)據(jù)小于這個(gè)的時(shí)候，不管你怎么做都永遠(yuǎn)不可能。
　　大數(shù)據(jù)帶來的困難我們大家一直在談大數(shù)據(jù)的挑戰(zhàn)，來到阿里之前我沒有意識(shí)到，來了之后覺得這個(gè)事情真的是big deal。做任何統(tǒng)計(jì)是最重要的一件事情，比如這里非?；A(chǔ)、簡(jiǎn)單的任務(wù)——矩陣平均，即便只是簡(jiǎn)簡(jiǎn)單單地做大數(shù)據(jù)下的平均，也是一個(gè)big deal，每一個(gè)矩陣都是很大（1Bx1M）。在應(yīng)用里頭，這個(gè)矩陣記錄了每個(gè)人對(duì)每個(gè)商品行為的矩陣，這個(gè)矩陣是非常大的，但每天記錄下的矩陣是很稀疏的，雖然說你有幾百萬幾千萬的商品，但通常每個(gè)人只有在很少量的商品上的行為，你希望把這些矩陣加起來，平均表達(dá)出在一個(gè)人在很長(zhǎng)的周期內(nèi)的行為是什么樣的，但是一個(gè)disaster就發(fā)生了，如果矩陣做一個(gè)平均、求和，這個(gè)矩陣會(huì)變成一個(gè)death的矩陣，如果不做任何smart commutation，這個(gè)事情實(shí)際上是非常昂貴的，而且存儲(chǔ)也是昂貴的。我在阿里的第一件事情，就是我能不能做一個(gè)這樣的平均，我雖然不能算出確切結(jié)果，但有沒有辦法說我可以算出大概結(jié)果？最后一個(gè)很簡(jiǎn)單的辦法，就是用一個(gè)隨機(jī)算法做這個(gè)事情。
　　隨機(jī)算法的好處所謂的機(jī)器學(xué)習(xí)問題（Learning Problem），一般的機(jī)器學(xué)習(xí)問題會(huì)寫成這樣的形式，考慮有一堆訓(xùn)練樣本，有一個(gè)叫Lost Function，用來比較預(yù)測(cè)和現(xiàn)實(shí)的差別，并分析這些差別。通常，Learning Problem就是找到一個(gè)解，確認(rèn)這個(gè)解能夠給出正確的預(yù)測(cè)和訓(xùn)練樣本，通?？梢园阉兂梢粋€(gè)優(yōu)化問題來做。
　　
　　解決該問題的主要挑戰(zhàn)在于兩個(gè)方面：一個(gè)方面是樣本數(shù)量很大（1Bx1M），還有一個(gè)問題是維度非常高，通常來講都是億級(jí)，要解決的不會(huì)是一個(gè)簡(jiǎn)單的問題。一個(gè)成熟的解決方案就是隨機(jī)算法。相信很多人都有意無意地使用到隨機(jī)算法，比如用LR、SGD。
　　隨機(jī)算法有兩個(gè)好處：
　　隨機(jī)算法的Efficient，包括兩個(gè)方面，第一個(gè)方面是即使針對(duì)大規(guī)模樣本也不需要多次掃描數(shù)據(jù)，另一個(gè)方面，如果是非常高維的數(shù)據(jù)，一個(gè)簡(jiǎn)單的辦法是可以使用隨機(jī)投影（Random Projection）來降低維度，這樣可以不用直接解決高維問題；隨機(jī)算法的Effective，就是它通常有最小化泛化誤差 （Generalization Error） ，不僅僅是計(jì)算簡(jiǎn)化，同時(shí)也可以提供很強(qiáng)的保證。
　　隨機(jī)算法的挑戰(zhàn)（以隨機(jī)投影為例）
　　隨機(jī)算法很好，但是總體來講，隨機(jī)算法還是有很多的局限的，我的演講用一個(gè)很簡(jiǎn)單的隨機(jī)投影問題來討論，來看一下隨機(jī)算法的問題在哪里。
　　隨機(jī)投影是一種非常簡(jiǎn)單的方法，而且應(yīng)用廣泛。一個(gè)高維矩陣X，long long vector，處理起來很麻煩，計(jì)算量很大，而且可以證明優(yōu)化收斂速度跟維度是有關(guān)系的。一個(gè)簡(jiǎn)單的做法，針對(duì)非常長(zhǎng)的vector，乘上一個(gè)非常fat的隨機(jī)矩陣S，乘完以后得到一個(gè)很短vector的X point，很低維度的表示，就把這個(gè)X point變成我的數(shù)據(jù)，用低維的數(shù)據(jù)來優(yōu)化問題，在低維空間學(xué)習(xí)。這個(gè)好的解是一個(gè)很矮的vector，我還要回到原來的空間上去，把原來的矩陣轉(zhuǎn)置一下，又變成一個(gè)很長(zhǎng)的vector，就變成最后的解。幾乎所有的random projection都可以這么做：把一個(gè)（很長(zhǎng)的）vector用一個(gè)隨機(jī)矩陣變成一個(gè)很短很短的vector，算出一個(gè)解來，再把矩陣轉(zhuǎn)置，把最優(yōu)解一乘就可以了。這是一個(gè)非常簡(jiǎn)單的算法，是使用廣泛，而且有無限多的paper分析這個(gè)東西有沒有效。幾乎所有的paper都告訴你這個(gè)東西很有效，也可以證明它很有效，但是我覺得所有的paper都很理想化，通常會(huì)假設(shè)原來的問題是一個(gè)很容易解的問題，可以證明所有的東西都是對(duì)的，但不幸的是，如果你的問題是比較難分類的問題，它告訴你的所有story都是假的。所以這其中隱藏了一個(gè)非常有趣的幾何泛函的問題，一百多年前就已經(jīng)被well study。也就是說，這個(gè)W star是真正的最優(yōu)解，把所有的高維數(shù)據(jù)放進(jìn)去讓機(jī)器run獲得的最優(yōu)解，而所有W star cute就是剛才說的用隨機(jī)投影的算法降維得到的解，你可以證明這兩個(gè)解通常會(huì)有非常大的差別，這個(gè)差別跟原來的vector應(yīng)該是一個(gè)數(shù)量級(jí)的。
　　
　　所以說run隨機(jī)投影的算法拿到的解，跟原來的解有很大的差別。這是不是因?yàn)槲颐枋隽艘粋€(gè)非常特定的過程，這個(gè)中間的過程造成這個(gè)解不好，所以是不是嘗試一下變化一個(gè)問題就有機(jī)會(huì)拿到更好的解呢？非常不幸地告訴你，這是不可能的，這也就是我說的Impossibility Theorem，可以證明這個(gè)事情不管怎么玩，只要做隨機(jī)投影，不管你怎么去解這個(gè)w star cute，這兩個(gè)解永遠(yuǎn)是差別很大，這和怎么解的問題都沒有半毛錢關(guān)系。而且非常奇怪這個(gè)東西一百多年前都知道了，不知道為什么沒有人提出來。但是對(duì)我來說這個(gè)事情很有意思，我能不能做其他的事情，稍微加一點(diǎn)限制，就能讓我這個(gè)疏密的問題解掉？
　　對(duì)偶隨機(jī)投影的優(yōu)化
　　這是五年前讓我很感興趣的一個(gè)問題，我們創(chuàng)造了一個(gè)對(duì)偶隨機(jī)投影 （Dual Random Projection），非常簡(jiǎn)單、非常神奇，把隨機(jī)投影得到的w star cute這個(gè)解塞到每一個(gè)Lost Function里去，然后去求一個(gè)導(dǎo)數(shù)，這里稱為alpha i，最后的解是用每一個(gè)training instance和alpha i對(duì)應(yīng)，所以你需要做的，不是直接采用隨機(jī)投影得到的解，而是用隨機(jī)投影的解去算它的對(duì)偶變量，用對(duì)偶變量去win每一個(gè)training instance。