美國最大婚戀交友網站eHarmony的機器學習實踐
原文 http://www.csdn.net/article/2015-03-19/2824267
?上周，我去洛杉磯參加了一個機器學習的meetup，一位主講是eHarmony公司（美國最大的婚戀交友網站之一，通過性格測試來進行婚戀匹配的模式 ——百度百科）的Jon Morra，他著重分享了機器學習（machine learning）在他們的在線交友平臺中的應用。 機器學習技術應用的深度和廣度給我留下了深刻的印象，他們居然能夠應用到大多數人都能遇到的問題——尋找愛情上！
核心問題
在線約會的核心問題有太多的可挑選對象。 為了防止用戶無所適從，我們需要提供智能匹配。 簡單來說，你需要評估一下不同人們之間的“約會相容性（dating compatibility）”矩陣，從而建立一些匹配，這些匹配能夠最大可能的使得約會成功。
如果這個愛情距離矩陣很小，你可以輕松的算出匹配，然后就能夠給每一個人一個最佳匹配。比如，你可以用匈牙利算法來解決這一分配問題。 然而，當我們處理數以百萬計的用戶量的時候，計算愛情距離矩陣就不現實了，并且我們的匹配也不是完美的，所以我們需要提供多個匹配。
John提供了一個“三級跳”的方法來解決這些問題：
- 根據相容性分級來減少潛在匹配池。相容性分級由用戶提交的心理自測結果以及性取向、年齡、所在地等構成。
- 基于統計數據、文本功能、視覺功能等來計算潛在匹配之間的相似性（affinity）。
- 基于相似性，就可以找到最佳的匹配，然后通過日常電子郵件 發送給用戶。 </ol>
相容性分級
第一部分是最簡單的： 根據一些調查和從心理學的角度來看，人與人之間或多或少是具有相容性的。 相容性分級既包括單人的人格特質也包含了人與人之間的二元特質——也就是相似性（similarity）。
相容性結果也使用了性別偏好、年齡段和所在地等因素進行了過濾。第一步通過硬閾值消除了大量的不兼容的匹配。這樣就把愛情距離矩陣轉換成了更加易于處理的不含0元素的矩陣。 我私下揣摩，這樣也可能導致創建一些小分組，比如基于所在地的分組等，這些分組可以為后續的并行運算做準備。
相似性計算
相似性分值是兩個用戶愿意交流的概率。這個分值是基于邏輯回歸模型訓練得到的。 訓練數據包括了一些日志，這里面記載了兩個用戶是否曾經給對方傳遞過個人資料。 訓練通過Vowpal Wabbit來完成，這是一個聽起來挺可怕，但是功能強大的機器學習包，可以在TB級別上做線性和邏輯回歸模型的在線訓練。
你的特征關系到你的生死； eHarmony公司采用經典的特征，如網站使用率統計數據、文本特征（我猜測是bag-of-words模型）和照片數量等，這些數據從成對的用戶中提取得到。 我認為訓練矩陣也包括了相似的特征，比如相容性等級。 有趣的是，最近eHarmony公司也涉足了照片分析。
John首先展示了使用Viola-Jones探測器提取圖像特征（比如臉部區/圖片區）的例子。 無處不在的Viola-Jones檢測器采用級聯分類器存根來檢測一副圖像中是否包含了人臉，它在OpenCV中有具體實現。 這個分類器使用了類Haar特征，這種特征可以使用積分圖像進行高效的計算，同時，分類器使用AdaBoost算法進行訓練。
Face Parts檢測器
然后，John展示了使用Face Parts檢測器進行檢測的一些結果，這部分內容我不懂，但是效果還是相當驚人的。 Face Parts 包含的思想是，一個人臉可以看出是由多個部件構成的，這些部件可以放置到一個樹形結構中。 部分匹配（可以看成一個圖形的一部分如果識別成眉毛，那么這種識別可以用一個分值來表示）通過計算模板和特征集的高斯直方圖（HOG）的點積得到。
Face Parts
各個部分通過一些“彈簧”連接起來，所有彈簧的彈性決定了這種連接方式的能量——能量越低，配置就越好。 外觀和結構分數的加權和確定了一個特定的連接的“良好”程度。
由于彈簧模型使用了特殊的樹形結構，所以所有連接的良好程度可以使用消息傳遞算法來進行評估和最大化。 由于允許使用一些額外的樹形結構——比如，一個用于前臉，一個用于輪廓——所以姿勢估計、檢測以及標志性的檢測都可以使用相同的步驟來完成。 相當不錯。
訓練是用結構化SVM學習方法的最大邊界的設置來完成的。 一旦模型訓練完成，它就會使用eHarmony的臉部數據集進行評估，各種特征會從圖像中提取出來： 像臉的寬度和高度的比率，是否展示了乳溝等。 Jon實現了一個高效的版本，并且將它開源， 放置在GitHub上 。
我的理解是，這些特征沒有在相似性模型中進行雙向性的編碼： 比如，它沒有嘗試把有胡子的家伙跟展示乳溝的女士進行匹配。 相反，這些單向性的特征都是決定了你吸引別人進行交往的能力。
那么，下一步，你有多讓人喜歡從而收到交流邀請就是很重要的了。這時候，匹配就用來使得每個人都開心了。
潛在相似性匹配
最后，我們必須給用戶最佳匹配。 系統設置了每個人有6到10個匹配對象，它使用了 CS2算法 來最大化有向無環圖中的流——相匹配的人的相似性分數總和。
一個非常有趣的發展前沿——不是現在在用的——是根據人們的個人資料來給他們提供恰當的匹配數量。 有些人喜歡更多的選擇，而有些人，比如內向的人，或許更喜歡少一點的。
如果事先不知道一個人是喜歡多的還是少的，那么怎么給他提供一個更合適的匹配數量呢？一種解決方法是：一個月內，每天都給他一些隨機數量的匹配，然后挑出他最常用的交往數量作為他的最佳匹配數字。 但是使用這種策略，我們會不會浪費了太多的時間呢？
其實這個問題是變相的經典 多臂匪徒問題 （multi-armed bandit problem）。 你面對許多個單臂匪徒——數學理想化的老虎機，每個機器具有一定的但是未知的概率能中獎。 每次試驗中，你挑一個賭博機，并得到了回報。 問題是，怎樣在一定時間周期內獲取最大化的收益， 也就是說，最小化遺憾。 這就需要深度和廣度的一種平衡。
一種不太理想，但仍然非常快速和有效的策略稱為UCB策略，它說的是你應該挑選那個上限信心索引最大的機器。 所以在這種情況下部署UCB策略，可以迅速找到一個用戶的最佳匹配的數目。
在這里，我們還有更多的數據可以利用——我們知道用 戶的基本信息。 這個問題就可以在具有上下文的匪徒問題框架下處理——經典匪徒問題+特征回歸。 在Yahoo!上有一篇非常不錯的文章， 它通過實驗演示了如何使用UCB策略來生成帶上下文的匪徒問題 ，強烈建議感興趣的讀者參閱。
總結
這一天的參與值得嗎？John特別提到了發表在PNAS的一篇文章，文章提到，通過網上交友而完成的婚姻比線下的婚姻具有更高的滿意度；在交友網站中，eHarmony公司擁有最好的婚姻滿意度。
盡管該文件所依據的調查由eHarmony公司自己來完成的，但是統計結果看起來是可信的，并且PNAS是一本相當好的雜志。
當然，我們不能排除自我選擇的偏見，也就是說如果有人想通過選擇某個特定網站來進行約會，那么，如Aziz Ansari所指出的： 視頻下載 。
原文鏈接： MACHINE LEARNING IN ONLINE DATING （編譯/Fashionxu 審校/happytofly 責編/周建丁）
</div> </div>