作者：Preetha Appan

Indeed.com?每個月有兩億不同的訪客，有每天處理數(shù)億次請求的推薦引擎。在這篇文章里，我們將描述我們的推薦引擎是如何演化的，如何從最初的基于Apache Mahout建立的最簡化可用行產(chǎn)品，到一個在線離線混合的成熟產(chǎn)品管道。我們將探索這些變化對產(chǎn)品性能指標(biāo)的影響，以及我們是如何通過使用算法、架構(gòu)和模型格式的增量修改來解決這些挑戰(zhàn)的。進(jìn)一步，我們將回顧在系統(tǒng)設(shè)計(jì)中的一些相關(guān)經(jīng)驗(yàn)，相信可以適用于任何高流量的機(jī)器學(xué)習(xí)應(yīng)用中。

從搜索引擎到推薦

Indeed的產(chǎn)品運(yùn)行在世界各地的許多數(shù)據(jù)中心上。來自每個數(shù)據(jù)中心的點(diǎn)擊流數(shù)據(jù)以及其他應(yīng)用事件被復(fù)制到我們在奧斯丁數(shù)據(jù)中心的一個中心化的HDFS數(shù)據(jù)倉庫中。我們在這個數(shù)據(jù)倉庫上進(jìn)行計(jì)算分析并且構(gòu)建我們的機(jī)器學(xué)習(xí)模型。
我們的職位搜索引擎是簡單而直觀的，只有兩個輸入：關(guān)鍵字和地點(diǎn)。搜索結(jié)果頁面展示了一個匹配的職位列表，并基于相關(guān)性進(jìn)行了排序。搜索引擎是我們的用戶發(fā)現(xiàn)職位的主要方式。
我們決定在搜索引擎之上加入職位推薦作為一個新的交互模式是基于以下幾個關(guān)鍵原因：

• Indeed上所有搜索的25%只指定了一個區(qū)域，并沒有搜索關(guān)鍵字。有許多的求職者并不確定在他們的搜索中應(yīng)該用什么關(guān)鍵字
• 當(dāng)我們發(fā)送有針對性的推薦時，求職者的體驗(yàn)是個性化的
• 推薦可以幫助甚至最復(fù)雜的用戶來發(fā)現(xiàn)額外的未被搜索所涵蓋的職位
• 推薦為亞馬遜帶來了額外35%的銷量為Netflix75%的內(nèi)容閱覽。很顯然，推薦能提供額外的價值

推薦職位與推薦產(chǎn)品或者是電影有很顯著的區(qū)別。這里列舉了一些我們在構(gòu)建推薦引擎時仔細(xì)考慮過的因素：

• （職位）庫存快速增長：我們每天要聚合計(jì)算幾百萬新的職位?？梢酝扑]的職位的集合在不斷變化
• 新用戶：每天有幾百萬新的求職者訪問我們的網(wǎng)站并開始他們的職位搜索。我們想要能夠根據(jù)有限的用戶數(shù)據(jù)生成推薦。
• 流動性：在indeed上一個職位的平均生命周期是30天左右。內(nèi)容的更新十分重要，因?yàn)槔系穆毼坏男枰浅？赡芤呀?jīng)被滿足了
• 有限的供給關(guān)系：一個發(fā)布的職位通常只招一個的應(yīng)聘者。這和書籍或者電影很不一樣，并不是只要有庫存就可以同時推薦給很多用戶。如果我們過度推薦一個職位，我們可能會讓雇主收到到上千個應(yīng)聘申請的轟炸。

如何理解推薦算法

推薦是一個匹配問題。給定一個用戶集合和一個物品集合，我們想要將用戶匹配到他們喜歡的物品上。有兩種高層次的方法可以達(dá)成這類匹配：基于內(nèi)容的和基于行為的。它們各有優(yōu)缺點(diǎn)，此外也有將兩者結(jié)合起來從而發(fā)揮各自優(yōu)勢的方法。

基于內(nèi)容的方法使用比如用戶偏好設(shè)置、被推薦物品的特性之類的數(shù)據(jù)來決定最佳匹配。對于職位推薦來說，通過職位的描述中的關(guān)鍵字來匹配用戶上傳的簡歷中的關(guān)鍵字是一種基于內(nèi)容的推薦方法。通過一個職位的關(guān)鍵字來找到其他看上去相似的職位是另外一種基于內(nèi)容的推薦的實(shí)現(xiàn)方法。

基于行為的方法利用了用戶的行為來生成推薦。這類方法是領(lǐng)域無關(guān)的，這意味著同樣的算法如果對于音樂或者電影有效的話，也可以被應(yīng)用在求職領(lǐng)域。基于行為的方法會遇到所謂的冷啟動問題。如果你只有很少的用戶活動數(shù)據(jù)，就很難去生成高質(zhì)量的推薦。

Mahout協(xié)同過濾

我們從建立一個基于行為的推薦引擎開始，因?yàn)槲覀兿胍梦覀円延械那舐氂脩艉退麄兊狞c(diǎn)擊數(shù)據(jù)，我們的首次個性化推薦嘗試是基于Apache Mahout提供的基于用戶間的協(xié)同過濾算法的實(shí)現(xiàn)。我們將點(diǎn)擊流數(shù)據(jù)喂給一個運(yùn)行在Hadoop集群上的Mahout構(gòu)建器并產(chǎn)生一個用戶到推薦職位的映射。我們建立一個新的服務(wù)使得可以運(yùn)行時訪問這個模型，且多個客戶端應(yīng)用可以同時訪問這個服務(wù)來獲取推薦的職位。

產(chǎn)品原型的結(jié)果和障礙

作為一個產(chǎn)品原型，基于行為的推薦引擎向我們展示了一步步迭代前進(jìn)的重要性。通過快速建立起這個系統(tǒng)并將其展示給用戶，我們發(fā)現(xiàn)這種推薦對于求職者來說是有用的。然而，我們很快就遇到了一些在我們的數(shù)據(jù)流上使用Mahout的問題：

• 模型構(gòu)建器需要花大約18個小時的時間來處理Indeed網(wǎng)站2013年的點(diǎn)擊流數(shù)據(jù)，這個數(shù)據(jù)量要比今日的數(shù)據(jù)小了三倍。
• 我們只能一天執(zhí)行一個模型構(gòu)造器，這意味著每天新加入的用戶直到第二天為止看不到任何推薦。
• 幾百萬新匯總的職位在模型構(gòu)造器再次運(yùn)行之前是不能作為可見的推薦的。
• 我們產(chǎn)生的模型是一個很大的映射，大約占了50吉字節(jié)的空間，需要花費(fèi)數(shù)個小時將其通過廣域網(wǎng)從其生成的數(shù)據(jù)中心拷貝到全球各地的數(shù)據(jù)中心。
• Mahout的實(shí)現(xiàn)的提供露了一些可配置參數(shù)，比如相似度閾值。我們可以調(diào)節(jié)算法的參數(shù)，但是我們想要測試整個不同的算法這樣的靈活性。

為推薦實(shí)現(xiàn)最小哈希

我們先解決最重要的問題：構(gòu)建器太慢了。我們發(fā)現(xiàn)在Mahout中的用戶間相似度是通過在n^2復(fù)雜度下的用戶間兩兩比較的來實(shí)現(xiàn)的。僅對于美國的網(wǎng)站用戶來說（五千萬的訪問量），這個比較的數(shù)量將達(dá)到15 * 10^15次，這是難以接受的。而且這一計(jì)算本身也是批量處理的，新加一個用戶或者一個新的點(diǎn)擊事件就要求重新計(jì)算所有的相似度。

我們意識到推薦是一個非精確匹配問題。我們是在尋求方法來發(fā)現(xiàn)給定用戶最相近的用戶們，但是我們并不需要100%準(zhǔn)確。我們找了一些估算相似度的方法，不需要準(zhǔn)確的計(jì)算。

主要貢獻(xiàn)者戴夫格里菲思從一篇谷歌新聞學(xué)術(shù)論文上看到了最小哈希方法。最小哈希（或者最小獨(dú)立序列）允許近似計(jì)算杰卡德相似度。將這一方法應(yīng)用到兩個用戶都點(diǎn)擊過的職位上，我們發(fā)現(xiàn)兩個用戶有更多共同的職位點(diǎn)擊，那么他們的杰卡徳相似度就越高。為所有的用戶對計(jì)算杰卡徳相似度的復(fù)雜度是O(n^2)，而有了最小哈希后，我們可以將復(fù)雜度降到O(n)。

給定一個哈希函數(shù)h1, 一個項(xiàng)目集合的最小哈希被定義為將集合中所有項(xiàng)用該哈希函數(shù)分別哈希，然后取其中最小的值。由于方差太大，單個哈希函數(shù)不足以計(jì)算近似杰卡徳相似度。我們必須使用一個哈希函數(shù)族來合理地計(jì)算近似的杰卡徳距離。通過使用一個哈希函數(shù)族，最小哈?？杀挥脕韺?shí)現(xiàn)可調(diào)節(jié)杰卡徳相似度閾值的個性化推薦。

“挖掘海量數(shù)據(jù)集”，一個最近的由斯坦福大學(xué)教授萊斯科維克、拉賈羅曼和厄爾曼講解的Coursera課程，非常詳細(xì)的解釋了最小哈希。他們書的第三章——“挖掘海量數(shù)據(jù)集”，解釋了最小哈希背后的數(shù)學(xué)證明原理。

我們針對推薦的最小哈希的實(shí)現(xiàn)涉及到以下三個階段：

1. 簽名計(jì)算和集群分配

每一個求職者被映射到一個h個集群的集合，對應(yīng)了一個哈希函數(shù)族H（下面的偽代碼展示了這一過程）：

				H = {H1, H2, ..H20}
				for user in Users
				???????for hash in H
				?????????????minhash[hash] = min{x∈Itemsi| hash(x)}
			

這里H是一個包含h個哈希函數(shù)的族。這一步的最后，每一個用戶被一個簽名集合所代表，也即一個由h個值組成的集群。

2. 集群擴(kuò)展

共享相同簽名的用戶被認(rèn)為是相似的，他們的職位將為被互相推薦。因此我們從每一個在集群中的用戶開始，用其所有的職位來擴(kuò)展每個集群。

3.生成推薦

為了給一個用戶生成推薦，我們將h個用戶所在的集群中的職位并起來。然后我們除去任何用戶已經(jīng)訪問過的職位，從而得到最后的職位推薦。

為新用戶推薦職位

最小哈希的數(shù)學(xué)屬性使得我們可以解決為新用戶推薦職位的問題，并且可以向所有的用戶推薦新的職位。當(dāng)新的點(diǎn)擊數(shù)據(jù)到來的時候，我們增量地更新最小哈希簽名。我們也在內(nèi)存中維護(hù)新職位和他們的最小哈希族的映射。通過在內(nèi)存中保留這兩部分?jǐn)?shù)據(jù)，我們就可以在新用戶點(diǎn)擊了一些職位后為他們推薦職位。只要任何新發(fā)布的職位被點(diǎn)擊訪問過，它就可以被推薦給用戶。

在轉(zhuǎn)移到最小哈希方法后，我們有了一個混合的推薦模型，由一個在Hadoop上的構(gòu)建的離線每日被更新的組件和一個由當(dāng)日的點(diǎn)擊數(shù)據(jù)組成、在內(nèi)存緩存中實(shí)現(xiàn)的在線組件。這兩個模型被整合起來用以計(jì)算每一個用戶的最終推薦集合。在我們做了這些改變之后，每一個用戶的推薦變得更加得動態(tài)，因?yàn)樗鼈儗㈦S著用戶點(diǎn)擊感興趣的職位的同時發(fā)生變化。

這些改變中我們認(rèn)識到，我們可以在性能和準(zhǔn)確度上做出權(quán)衡，用小的誤差增加來換大的性能提升。我們也認(rèn)識到可以將較慢的離線模型通過在線的模型進(jìn)行補(bǔ)充，從而得到更新的推薦結(jié)果。

工程基礎(chǔ)設(shè)施的影響

包含每一個用戶到他們的推薦的映射的推薦模型是一個相當(dāng)龐大的文件。由于職位對于每個國家來說都是本地的，我們首先嘗試將我們的數(shù)據(jù)基于大約的地理邊界進(jìn)行分片。我們在每一塊區(qū)域運(yùn)行模型構(gòu)造器，而不是在整個世界運(yùn)行一個。每一個地區(qū)都有多個國家組成。舉個例子，東亞地區(qū)包括為中國、日本、韓國、香港、臺灣以及印度的推薦。

但是在分片之后，一些區(qū)域產(chǎn)生的數(shù)據(jù)仍然十分龐大，需要花好幾個小時才能通過廣域網(wǎng)從歐洲數(shù)據(jù)中心拷貝到奧斯丁的Hadoop集群。為了解決這個問題，我們決定增量的傳輸推薦數(shù)據(jù)，而不是一天一次。我們重用了連續(xù)先寫日志(sequential write ahead logs)的方法，通過日志結(jié)構(gòu)合并樹來實(shí)現(xiàn)。這一方法已經(jīng)在Indeed的其他大型產(chǎn)品應(yīng)用中得到驗(yàn)證，比如我們的文檔服務(wù)。

我們修改了我們的模型構(gòu)建器，將推薦數(shù)據(jù)存儲成小的分段，而不是產(chǎn)生一個單獨(dú)龐大的模型文件。每一個段文件使用順序輸入輸出，并且為快速復(fù)制做了優(yōu)化。這些分段在遠(yuǎn)程數(shù)據(jù)中心運(yùn)行推薦服務(wù)時將被重新組裝成一個日志結(jié)構(gòu)合并樹。

這一基礎(chǔ)架構(gòu)的改變使得用戶可以比之前快數(shù)個小時在遠(yuǎn)程的數(shù)據(jù)中心上看到他們新的推薦。從我們的A/B測試的結(jié)果來看，由用戶更快的得到新職位推薦帶來了30%的點(diǎn)擊量提升。

這一改進(jìn)展示了工程基礎(chǔ)設(shè)施的改進(jìn)與算法的改進(jìn)帶來的影響不相上下。

改進(jìn)A/B測試的速度

建立起計(jì)算和更新推薦的管道只是一個開始。為了改進(jìn)覆蓋率和推薦質(zhì)量，我們需要加快我們的A/B測試的速度。我們?yōu)榱苏{(diào)整最后的推薦集合做了很多決策。這些決策包括，相似度閾值，每一個用戶的推薦包含的職位數(shù)量，以及各種不同的用來過濾掉低質(zhì)量推薦的方法。我們想要調(diào)節(jié)和優(yōu)化計(jì)算推薦的各個方面，但是這需要逐個對算法的每個改進(jìn)都構(gòu)建新的模型。測試多個改進(jìn)想法意味著處理用戶請求的服務(wù)器上多倍的磁盤以內(nèi)存占用。

我們開始通過傳輸計(jì)算推薦的單獨(dú)組件而不是最終的結(jié)果來改進(jìn)我們的A/B測試。我們改變了推薦服務(wù)來執(zhí)行最后的計(jì)算，即通過將碎片整合起來，而不是簡單的讀取模型返回結(jié)果。重要的推薦子組件是每個用戶的集群分配，從每一個集群到這個集群中的職位的映射以及一個對于每個用戶來說包含不應(yīng)該推薦給他們的職位的黑名單。我們修改了我們的構(gòu)建器，來產(chǎn)生這些組件，并且修改了我們的服務(wù)，將他們在收到請求時組合起來從而返回最終的推薦列表。

通過實(shí)現(xiàn)這種架構(gòu)上的改變，我們只傳輸那些在每一個A/B測試中改變的子組件。比如說，如果測試只調(diào)節(jié)了什么樣的職位會從一個用戶的推薦中除去，那么我們只需要傳輸這個測試組的黑名單。

這一改變改進(jìn)了A/B測試的速度的數(shù)量級。我們能夠在很短的時間內(nèi)測試并驗(yàn)證多個可以改進(jìn)推薦質(zhì)量和覆蓋率的想法。之前，由于設(shè)置環(huán)境的開銷較大，我們平均每個季度只能測試一個模型中的改進(jìn)，

我們的經(jīng)驗(yàn)表明A/B測試的速度應(yīng)該在設(shè)計(jì)大型機(jī)器學(xué)習(xí)系統(tǒng)時就被考慮進(jìn)去。你能越快地將你的想法放在用戶面前，那么你就能越快地在上面迭代。

這篇文章總結(jié)了我們在構(gòu)建我們的推薦引擎時做出的一系列算法和架構(gòu)上的改變。我們迭代地構(gòu)建軟件，我們從一個最簡單原型開始，從中獲取經(jīng)驗(yàn)，并不斷改進(jìn)。這些改變帶來的成果是職位推薦的點(diǎn)擊增加從2014年初最簡原型時的3%增長到了14%。

我們將繼續(xù)精煉我們的推薦引擎。我們正在使用Apache Spark建立一個原型模型，建立一個模型集成組合，并精煉我們的優(yōu)化參數(shù)來應(yīng)對流行偏見問題。

End.

轉(zhuǎn)載請注明來自36大數(shù)據(jù)（36dsj.com)： 36大數(shù)據(jù) ? 工作職位推薦系統(tǒng)的算法與架構(gòu)