Google Rephil是Google AdSense背後廣告相關性計算的頭号秘密武器。但是這個系統沒有發表過論文。隻是其作者(博士Uri Lerner和工程師Mike Yar)在2002年在灣區舉辦的幾次小規模交流中簡要介紹過。所以Kevin Murphy把這些内容寫進了他的書《Machine Learning: a Probabilitic Perspecitve》裡。在吳軍博士的《數學之美》裡也提到了Rephil。
Rephil的模型是一個全新的模型,更像一個神經元網絡。這個網絡的學習過程從Web scale的文本數據中歸納海量的語義——比如“apple”這個詞有多個意思:一個公司的名字、一種水果、以及其他。當一個網頁裡包含”apple”, “stock”, “ipad”等詞彙的時候,Rephil可以告訴我們這個網頁是關于apple這個公司的,而不是水果。
這個功能按說pLSA和LDA也都能實現。為什麼需要一個全新的模型呢?
從2007年至今,國内外很多團隊都嘗試過并行化pLSA和LDA。心靈手巧的工程師們,成功的開發出能學習數萬甚至上十萬語義(latent topics)的訓練系統。但是不管大家用什麼訓練數據,都會發現,得到的大部分語義(相關的詞的聚類)都是非常類似,或者說“重複”的。如果做一個“去重”處理,幾萬甚至十萬的語義,就隻剩下幾百幾千了。
這是怎麼回事?
如果大家嘗試着把訓練語料中的低頻詞去掉,會發現訓練得到的語義和用全量數據訓練得到的差不多。換句話說,pLSA和LDA模型的訓練算法沒有在意低頻數據。
為什麼會這樣呢?因為pLSA和LDA這類概率模型的主要構造單元都是指數分布(exponential distributions)。比如pLSA假設一個文檔中的語義的分布是multinomial的,每個語義中的詞的分布也是multinomial的。因為multinomial是一種典型的指數分布,這樣整個模型描述的海量數據的分布,不管哪個維度上的marginalization,都是指數分布。在LDA中也類似——因為LDA假設各個文檔中的語義分布的multinomial distributions的參數是符合Dirichlet分布的,并且各個語義中的詞的分布的multinomial distributions的參數也是符合Dirichlet分布的,這樣整個模型是假設數據是指數分布的。
可是Internet上的實際數據基本都不是指數分布的——而是長尾分布的。至于為什麼是這樣?可以參見2006年紐約時報排名暢銷書The Long Tail: Why the Future of Business is Selling Less of More。或者看看其作者Chris Anderson的博客The Long Tail。
長尾分布的形狀大緻如下圖所示:
其中x軸表示數據的類型,y軸是各種類型的頻率,少數類型的頻率很高(稱為大頭,圖中紅色部分),大部分很低,但是大于0(稱為長尾,圖中黃色部分)。一個典型的例子是文章中詞的分布,有個具體的名字Zipf’s law,就是典型的長尾分布。而指數分布基本就隻有大頭部分——換句話說,如果我們假設長尾數據是指數分布的,我們實際上就把尾巴給割掉了。
割掉數據的尾巴——這就是pLSA和LDA這樣的模型做的——那條長尾巴覆蓋的多種多樣的數據類型,就是Internet上的人生百态。理解這樣的百态是很重要的。比如百度和Google為什麼能如此賺錢?因為互聯網廣告收益。傳統廣告行業,隻有有錢的大企業才有财力聯系廣告代理公司,一幫西裝革履的高富帥聚在一起讨論,競争電視或者紙媒體上的廣告機會。互聯網廣告裡,任何人都可以登錄到一個網站上去投放廣告,即使每日廣告預算隻有幾十塊人民币。這樣一來,劉備這樣織席販屢的小業主,也能推銷自己做的席子和鞋子。而搜索引擎用戶的興趣也是百花齊放的——從人人愛戴的陳老師蒼老師到各種小衆需求包括“紅酒木瓜湯”(一種豐胸秘方,應該出豐胸廣告)或者“蘋果大尺度”(在搜索範冰冰主演的《蘋果》電影呢)。把各種需求和各種廣告通過智能技術匹配起來,就醞釀了互聯網廣告的革命性力量。這其中,理解各種小衆需求、長尾意圖就非常重要了。
實際上,Rephil就是這樣一個能理解百态的模型。因為它把Google AdSense的盈利能力大幅提升,最終達到Google收入的一半。兩位作者榮獲Google的多次大獎,包括Founders’ Award。
而切掉長尾是一個很糟糕的做法。大家還記得小說《1984》裡有這樣一個情節嗎?老大哥要求發布“新話”——一種新的語言,删掉自然英語中大部分詞彙,隻留下那些主流的詞彙。看看小說裡的人們生活的世界,讓人渾身發毛,咱們就能體會“割尾巴”的惡果了。沒有看過《1984》的朋友可以想象一下水木首頁上隻有“全站十大”,連“分類十大”都删掉之後的樣子。
既然如此,為什麼這類模型還要假設數據是指數分布的呢?——實在是不得已。指數分布是一種數值計算上非常方便的數學元素。拿LDA來說,它利用了Dirichlet和multinomial兩種分布的共轭性,使得其計算過程中,模型的參數都被積分給積掉了(integrated out)。這是AD-LDA這樣的ad hoc并行算法——在其他模型上都不好使的做法——在LDA上好用的原因之一。換句話說,這是為了計算方便,掩耳盜鈴地假設數據是指數分布的。
實際上,這種掩耳盜鈴在機器學習領域很普遍。比如有個兄弟聽了上面的故事後說:“那我們就别用概率模型做語義分析了,咱們還用矩陣分解吧?SVD分解怎麼樣?” 很不好意思的,當我們把SVD分解用在語義分析(稱為LSA,latent semantic analysis)上的時候,我們還是引入了指數分布假設——Gaussian assumption或者叫normality assumption。這怎麼可能呢?SVD不就是個矩陣分解方法嗎?确實傳統SVD沒有對數據分布的假設,但是當我們用EM之類的算法解決存在missing data的問題——比如LSA,還有推薦系統裡的協同過濾(collaborative filtering)——這時不僅引入了Gaussian assumption,而且引入了linearity assumption。當我們用其他很多矩陣分解方法做,都存在同樣的 問題。
掩耳盜鈴的做法怎麼能存在得如此自然呢?這是因為指數分布假設(尤其是Gaussian assumption)有過很多成功的應用,包括通信、數據壓縮、制導系統等。這些應用裡,我們關注的就是數據中的低頻部分;而高頻部分(或者說距離mean比較遠的數據)即使丢掉了,電話裡的聲音也能聽懂,壓縮還原的圖像也看得明白,導彈也還是能沿着“最可能”靠譜的路線飛行。我們當然會假設數據是指數分布的,這樣不僅省計算開銷,而且自然的忽略高頻數據,我們還鄙夷地稱之為outlier或者noise。
可是在互聯網的世界裡,正是這些五花八門的outliers和noise,蘊含了世間百态,讓數據不可壓縮,從而産生了“大數據”這麼個概念。處理好大數據的公司,賺得盆滿缽滿,塑造了一個個傳奇。這裡有一個聽起來比較極端的說法大數據裡無噪聲——很多一開始頻率很低,相當長尾,會被詞過濾系統認為是拼寫錯誤的queries,都能後來居上成為主流。比如“神馬”,“醬紫”。
Rephil系統實現的模型是一個神經元網絡模型(neural network)。它的設計的主要考慮,就是要能盡量好的描述長尾分布的文本數據和其中蘊含的語義。Rephil模型的具體技術細節因為沒有在論文中發表過,所以不便在這裡透露。但是Rephil模型描述長尾數據的能力,是下文将要介紹的Peacock系統的原動力,雖然兩者在模型上完全不同。
Rephil系統是基于Google MapReduce構建的。如上節所述,MapReduce在用來實現疊代算法的時候,效率是比較低的。這也是Peacock要設計全新框架的原動力——使其比MapReduce高效,但同時像MapReduce一樣支持fault recovery。
,更多精彩资讯请关注tft每日頭條,我们将持续为您更新最新资讯!