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

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