indeed.com 每個月有兩億不同的訪客，有每天處理數億次請求的推薦引擎。在這篇文章裡，我們将描述我們的推薦引擎是如何演化的，如何從最初的基于apache mahout建立的最簡化可用行産品，到一個線上離線混合的成熟産品管道。我們将探索這些變化對産品性能名額的影響，以及我們是如何通過使用算法、架構和模型格式的增量修改來解決這些挑戰的。進一步，我們将回顧在系統設計中的一些相關經驗，相信可以适用于任何高流量的機器學習應用中。
從搜尋引擎到推薦
▼
indeed的産品運作在世界各地的許多資料中心上。來自每個資料中心的點選流資料以及其他應用事件被複制到我們在奧斯丁資料中心的一個中心化的hdfs資料倉庫中。我們在這個資料倉庫上進行計算分析并且建構我們的機器學習模型。
我們的職位搜尋引擎是簡單而直覺的，隻有兩個輸入：關鍵字和地點。搜尋結果頁面展示了一個比對的職位清單，并基于相關性進行了排序。搜尋引擎是我們的使用者發現職位的主要方式。
我們決定在搜尋引擎之上加入職位推薦作為一個新的互動模式是基于以下幾個關鍵原因：
indeed上所有搜尋的25%隻指定了一個區域，并沒有搜尋關鍵字。有許多的求職者并不确定在他們的搜尋中應該用什麼關鍵字
當我們發送有針對性的推薦時，求職者的體驗是個性化的
推薦可以幫助甚至最複雜的使用者來發現額外的未被搜尋所涵蓋的職位
推薦為亞馬遜帶來了額外35%的銷量為netflix75%的内容閱覽。很顯然，推薦能提供額外的價值
推薦職位與推薦産品或者是電影有很顯著的差別。這裡列舉了一些我們在建構推薦引擎時仔細考慮過的因素：
（職位）庫存快速增長：我們每天要聚合計算幾百萬新的職位。可以推薦的職位的集合在不斷變化
新使用者：每天有幾百萬新的求職者通路我們的網站并開始他們的職位搜尋。我們想要能夠根據有限的使用者資料生成推薦。
流動性：在indeed上一個職位的平均生命周期是30天左右。内容的更新十分重要，因為老的職位的需要非常可能已經被滿足了
有限的供給關系：一個釋出的職位通常隻招一個的應聘者。這和書籍或者電影很不一樣，并不是隻要有庫存就可以同時推薦給很多使用者。如果我們過度推薦一個職位，我們可能會讓雇主收到到上千個應聘申請的轟炸。
如何了解推薦算法
推薦是一個比對問題。給定一個使用者集合和一個物品集合，我們想要将使用者比對到他們喜歡的物品上。有兩種高層次的方法可以達成這類比對：基于内容的和基于行為的。它們各有優缺點，此外也有将兩者結合起來進而發揮各自優勢的方法。
基于内容的方法使用比如使用者偏好設定、被推薦物品的特性之類的資料來決定最佳比對。對于職位推薦來說，通過職位的描述中的關鍵字來比對使用者上傳的履歷中的關鍵字是一種基于内容的推薦方法。通過一個職位的關鍵字來找到其他看上去相似的職位是另外一種基于内容的推薦的實作方法。
基于行為的方法利用了使用者的行為來生成推薦。這類方法是領域無關的，這意味着同樣的算法如果對于音樂或者電影有效的話，也可以被應用在求職領域。基于行為的方法會遇到所謂的冷啟動問題。如果你隻有很少的使用者活動資料，就很難去生成高品質的推薦。
mahout協同過濾
我們從建立一個基于行為的推薦引擎開始，因為我們想要利用我們已有的求職使用者和他們的點選資料，我們的首次個性化推薦嘗試是基于apache mahout提供的基于使用者間的協同過濾算法的實作。我們将點選流資料喂給一個運作在hadoop叢集上的mahout建構器并産生一個使用者到推薦職位的映射。我們建立一個新的服務使得可以運作時通路這個模型，且多個用戶端應用可以同時通路這個服務來擷取推薦的職位。
産品原型的結果和障礙
作為一個産品原型，基于行為的推薦引擎向我們展示了一步步疊代前進的重要性。通過快速建立起這個系統并将其展示給使用者，我們發現這種推薦對于求職者來說是有用的。然而，我們很快就遇到了一些在我們的資料流上使用mahout的問題：
模型建構器需要花大約18個小時的時間來處理indeed網站2013年的點選流資料，這個資料量要比今日的資料小了三倍。
我們隻能一天執行一個模型構造器，這意味着每天新加入的使用者直到第二天為止看不到任何推薦。
幾百萬新彙總的職位在模型構造器再次運作之前是不能作為可見的推薦的。
我們産生的模型是一個很大的映射，大約占了50吉位元組的空間，需要花費數個小時将其通過廣域網從其生成的資料中心拷貝到全球各地的資料中心。
mahout的實作的提供露了一些可配置參數，比如相似度門檻值。我們可以調節算法的參數，但是我們想要測試整個不同的算法這樣的靈活性。
為推薦實作最小哈希
我們先解決最重要的問題：建構器太慢了。我們發現在mahout中的使用者間相似度是通過在n^2複雜度下的使用者間兩兩比較的來實作的。僅對于美國的網站使用者來說（五千萬的通路量），這個比較的數量将達到15 * 10^15次，這是難以接受的。而且這一計算本身也是批量處理的，新加一個使用者或者一個新的點選事件就要求重新計算所有的相似度。
我們意識到推薦是一個非精确比對問題。我們是在尋求方法來發現給定使用者最相近的使用者們，但是我們并不需要100%準确。我們找了一些估算相似度的方法，不需要準确的計算。
主要貢獻者戴夫格裡菲思從一篇谷歌新聞學術論文上看到了最小哈希方法。最小哈希（或者最小獨立序列）允許近似計算傑卡德相似度。将這一方法應用到兩個使用者都點選過的職位上，我們發現兩個使用者有更多共同的職位點選，那麼他們的傑卡徳相似度就越高。為所有的使用者對計算傑卡徳相似度的複雜度是o(n^2)，而有了最小哈希後，我們可以将複雜度降到o(n)。
給定一個哈希函數h1, 一個項目集合的最小哈希被定義為将集合中所有項用該哈希函數分别哈希，然後取其中最小的值。由于方差太大，單個哈希函數不足以計算近似傑卡徳相似度。我們必須使用一個哈希函數族來合理地計算近似的傑卡徳距離。通過使用一個哈希函數族，最小哈希可被用來實作可調節傑卡徳相似度門檻值的個性化推薦。
“挖掘海量資料集”，一個最近的由斯坦福大學教授萊斯科維克、拉賈羅曼和厄爾曼講解的coursera課程，非常詳細的解釋了最小哈希。他們書的第三章——“挖掘海量資料集”，解釋了最小哈希背後的數學證明原理。
我們針對推薦的最小哈希的實作涉及到以下三個階段：
1. 簽名計算和叢集配置設定
每一個求職者被映射到一個h個叢集的集合，對應了一個哈希函數族h（下面的僞代碼展示了這一過程）：
h = {h1, h2, ..h20}
for user in users
for hash in h
minhash[hash] = min{x∈itemsi| hash(x)}
這裡h是一個包含h個哈希函數的族。這一步的最後，每一個使用者被一個簽名集合所代表，也即一個由h個值組成的叢集。
2. 叢集擴充
共享相同簽名的使用者被認為是相似的，他們的職位将為被互相推薦。是以我們從每一個在叢集中的使用者開始，用其所有的職位來擴充每個叢集。
3.生成推薦
為了給一個使用者生成推薦，我們将h個使用者所在的叢集中的職位并起來。然後我們除去任何使用者已經通路過的職位，進而得到最後的職位推薦。
為新使用者推薦職位
最小哈希的數學屬性使得我們可以解決為新使用者推薦職位的問題，并且可以向所有的使用者推薦新的職位。當新的點選資料到來的時候，我們增量地更新最小哈希簽名。我們也在記憶體中維護新職位和他們的最小哈希族的映射。通過在記憶體中保留這兩部分資料，我們就可以在新使用者點選了一些職位後為他們推薦職位。隻要任何新釋出的職位被點選通路過，它就可以被推薦給使用者。
在轉移到最小哈希方法後，我們有了一個混合的推薦模型，由一個在hadoop上的建構的離線每日被更新的元件和一個由當日的點選資料組成、在記憶體緩存中實作的線上元件。這兩個模型被整合起來用以計算每一個使用者的最終推薦集合。在我們做了這些改變之後，每一個使用者的推薦變得更加得動态，因為它們将随着使用者點選感興趣的職位的同時發生變化。
這些改變中我們認識到，我們可以在性能和準确度上做出權衡，用小的誤差增加來換大的性能提升。我們也認識到可以将較慢的離線模型通過線上的模型進行補充，進而得到更新的推薦結果。
工程基礎設施的影響
包含每一個使用者到他們的推薦的映射的推薦模型是一個相當龐大的檔案。由于職位對于每個國家來說都是本地的，我們首先嘗試将我們的資料基于大約的地理邊界進行分片。我們在每一塊區域運作模型構造器，而不是在整個世界運作一個。每一個地區都有多個國家組成。舉個例子，東亞地區包括為中國、日本、南韓、香港、台灣以及印度的推薦。
但是在分片之後，一些區域産生的資料仍然十分龐大，需要花好幾個小時才能通過廣域網從歐洲資料中心拷貝到奧斯丁的hadoop叢集。為了解決這個問題，我們決定增量的傳輸推薦資料，而不是一天一次。我們重用了連續先寫日志(sequential write ahead logs)的方法，通過日志結構合并樹來實作。這一方法已經在indeed的其他大型産品應用中得到驗證，比如我們的文檔服務。
我們修改了我們的模型建構器，将推薦資料存儲成小的分段，而不是産生一個單獨龐大的模型檔案。每一個段檔案使用順序輸入輸出，并且為快速複制做了優化。這些分段在遠端資料中心運作推薦服務時将被重新組裝成一個日志結構合并樹。
這一基礎架構的改變使得使用者可以比之前快數個小時在遠端的資料中心上看到他們新的推薦。從我們的a/b測試的結果來看，由使用者更快的得到新職位推薦帶來了30%的點選量提升。
這一改進展示了工程基礎設施的改進與算法的改進帶來的影響不相上下。
改進a/b測試的速度
建立起計算和更新推薦的管道隻是一個開始。為了改進覆寫率和推薦品質，我們需要加快我們的a/b測試的速度。我們為了調整最後的推薦集合做了很多決策。這些決策包括，相似度門檻值，每一個使用者的推薦包含的職位數量，以及各種不同的用來過濾掉低品質推薦的方法。我們想要調節和優化計算推薦的各個方面，但是這需要逐個對算法的每個改進都建構新的模型。測試多個改進想法意味着處理使用者請求的伺服器上多倍的磁盤以記憶體占用。
我們開始通過傳輸計算推薦的單獨元件而不是最終的結果來改進我們的a/b測試。我們改變了推薦服務來執行最後的計算，即通過将碎片整合起來，而不是簡單的讀取模型傳回結果。重要的推薦子元件是每個使用者的叢集配置設定，從每一個叢集到這個叢集中的職位的映射以及一個對于每個使用者來說包含不應該推薦給他們的職位的黑名單。我們修改了我們的建構器，來産生這些元件，并且修改了我們的服務，将他們在收到請求時組合起來進而傳回最終的推薦清單。
通過實作這種架構上的改變，我們隻傳輸那些在每一個a/b測試中改變的子元件。比如說，如果測試隻調節了什麼樣的職位會從一個使用者的推薦中除去，那麼我們隻需要傳輸這個測試組的黑名單。
這一改變改進了a/b測試的速度的數量級。我們能夠在很短的時間内測試并驗證多個可以改進推薦品質和覆寫率的想法。之前，由于設定環境的開銷較大，我們平均每個季度隻能測試一個模型中的改進，
我們的經驗表明a/b測試的速度應該在設計大型機器學習系統時就被考慮進去。你能越快地将你的想法放在使用者面前，那麼你就能越快地在上面疊代。
這篇文章總結了我們在建構我們的推薦引擎時做出的一系列算法和架構上的改變。我們疊代地建構軟體，我們從一個最簡單原型開始，從中擷取經驗，并不斷改進。這些改變帶來的成果是職位推薦的點選增加從2014年初最簡原型時的3%增長到了14%。
我們将繼續精煉我們的推薦引擎。我們正在使用apache spark建立一個原型模型，建立一個模型內建組合，并精煉我們的優化參數來應對流行偏見問題。
原文釋出時間為：2016-12-21
本文來自雲栖社群合作夥伴“大資料文摘”，了解相關資訊可以關注“bigdatadigest”微信公衆号