新演算法將電影偏好推薦的效率提升了20倍

credit:銳景創意

新演算法大大縮短了電影偏好推薦或計程車最優化調度的時間。

高級研究員，哈佛大學的Yaron Singer說，他們減少了以往演算法所需的步驟，以更快的速度完成優化分析。令人驚訝的是，該方法「不會犧牲結果的質量」。

優化問題是從所有可能的解決方案中找到效率最高的一個，例如找出最快路線從A點前往B點。許多優化問題的演算法自20世紀70年代被發明以來就沒有變動過。

先前的優化演算法通常採取逐步調整的方式，運算步驟與所分析的數據量成正比。例如，你喜歡文藝片，那麼電影推薦演算法需要依次查看獲得你較高評價的電影，再為這些電影中的每一部尋找相似度高的同類影片，最後依據某種機制——大數據信息——將它們進行優先度排序。

然而，這種演算法具有收益遞減的特性：隨著程序運行，每個步驟的相對增益變得越來越小。這意味著對於涉及大量數據的優化問題，找到最佳解決方案可能會付出極其昂貴的運算成本。

在實驗中，Singer和合作者Eric Balkanski發現他們的演算法可以對數據集進行分析，其中包含來自6000名用戶的4000部電影的100萬個評分，並得到了與目前最優演算法類似的推薦結果，同時效率提高了20倍。此外，使用來自紐約市計程車和豪華轎車委員會的200萬次計程車呼叫相應的數據集，新演算法可以為計程車選擇最佳等待位置，以覆蓋最大數量的潛在客戶，比以前的演算法快六倍。

先前的優化演算法通過在單一方向上逐步調整來解決問題，新演算法可以並行地從多個數據維度採樣來完成工作。它會過濾掉不太理想的方向，並選擇最有價值的方向來推進對結果運算。對數據自適應的演化演算法有助於解決收益遞減的問題。

自適應策略針對演算法目標的兩個不同方面。研究人員稱之為曲率和同質性。

在為你推薦電影的時候，具有高曲率的對象是與你喜歡看的電影非常相似的其他影片——每個人都經過這樣的事情吧，如果您喜歡Die Hard，評分頁面的底部就自動地展現其續集的超鏈接。對於計程車調度問題，高曲率的目標是特定的停車地點，那裡可以在30秒內響應新的叫車信息。曲率更溫和——例如，計程車響應時間為五分鐘而不是30秒——的演算法的運算時間更加寬綽。

還是電影推薦問題，同質性描述的對象是同類型的影片——果你依舊喜歡《虎膽龍威》，根據同質性假設，你也會喜歡《致命武器》。對計程車調度公司，同質性假設是客戶在不同地點的分布相對均勻。同質性越高，演算法的速度也越快。

新演算法也可以解決其他問題，包括識別新葯，從公共衛生論壇獲取藥物相互作用的影響後果，以及設計用於醫學成像的感測器陣列。

「事實上，我們可以獲得指數級的效率提升，這為醫療保健、計算生物學、機器學習和數據挖掘等領域提供了嶄新的應用前景。它們以前消耗的運算成本實在太高。」Singer說。

Balkanski和Singer正在進一步發掘可以應用其策略的優化問題。他們還計劃為GPU編寫代碼，以便其他人可以重現他們的工作成果。「一般來說，這些演算法非常簡單，只需要幾行代碼就能實現。」Singer說。

6月28日洛杉磯計算機協會計算機理論研討會(STOC)上，他們做了詳細的報告，介紹了自己的成果；7月12日在斯德哥爾摩的國際機器學習大會(ICML)上對外展示了他們的演算法。

本文譯自 spectrum，由譯者 majer 基於創作共用協議(BY-NC)發布。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！