2011年3月13日 星期日
The YouTube Video Recommendation System
身為一名 YouTube 重度使用者, 有機會了解 YouTube 的運作機制, 自然要來了解一下啊。
一開始是在 YouTube转向Amazon的推荐算法 看到別人提到 YouTube uses Amazon's recommendation algorithm。前篇說明後篇作者的背景, 並提了些相關看法, 值得一讀。後篇的作者是當年寫 Amazon item-based collaborative filtering 專利和論文的主要作者 (Greg Linden), 他在自己的 blog 多年來寫了一系列關於 CF、YouTube、他之前的產品 Findory 的看法, 滿有意思的。
另外, YouTube uses Amazon's recommendation algorithm 的這則留言值得一看, 作者用簡短的文字清楚地說明 CF 的核心概念, 以及相關方法 (clustering) 的差異、優勢。在這摘錄部份內容:
該則留言的作者自己開家公司做 YouTube 推薦影片。看起來似乎是設定後可以在自己網站放 YouTube 影片, 由他們公司的產品幫忙找關聯影片。賣點大概是高度客製化和提供介面人工管理影片品質。
今天讀完 YouTube 的論文後, 發覺沒太重的 item-based CF 味道, 只是很單純的概念。不過也如同 Greg Linden 在留言提到, PageRank 的想法也沒有很新穎, 但它在業界獲得成效, 造成一個里程碑。Amazon 那篇論文也該獲得類似的對待。由於他自己是該論文的第一作者, 加上他在 Blog 三不五時提到該篇論文的代表性, 很難認同他說的話。只能說, 和名利扯上關係後, 很多事情都無法單純看待, YouTube 那篇論文不 cite Amazon 那篇, 也許是沒看過, 或認為無關聯, 也可能有專利考量吧。
YouTube 這篇論文只有四頁, 但寫得相當漂亮, 先說明 YouTube 各種使用情境, 再指出本篇針對 recommendation, 接著分析資料特性和 Netflix、Amazon 的差異, 分析自家資料分為 content data (如 title) 和 user activity data。其中 user activity data 又分 explicit (如 like, subscription) 和 implicit 的資料 (如 click through rate, long CTR)。說明使用者需求為即時且讓使用者明白的推薦。說明系統需求要讓各元件獨立簡單, 方便理解和除錯。前言的部份, 讀起來滿過癮的。
接著說明演算法時, 只有提到概念, 實際上效果的好壞, 取決於細節特徵和參數怎麼設, 這些應該都是長期間實測的經驗談。不過光是概念部份就有些幫助, 大概知道 YouTube 做了什麼取捨, 和在這樣取捨下, 大方向的優缺點。
首先是定義兩部影片的關聯性為何, 這是整篇的重點。設影片為 vertex、關聯強弱為 edge weight, 就能用 edge weight 排序找出一般性的 top-n 推薦。在使用者登入的情況下, 再用使用者明確喜歡的片子做為 seed set S (vertices 的子集), 由此找出它們 k 步內的點, 而形成發散且具一定準度的推薦候選清單。然後再配合細項資料排序結果。
至於 graph 的建法, 則是先定一個期間 (如 24h), 計算這個期間內任何部影片被同樣人觀看的次數, 於是能用 Cij / Cj 表示影片 j 對影片 i 的關聯度 (Cij 表示多少人看過影片 i 和 j)。這只是一個示意的概念, 關鍵是用一段時間內各使用者觀看影片的相對次數表示關聯程度。Greg Linden 應該就是針對運用這個概念卻沒 cite Amazon 的論文而不滿吧。看完關聯性的找法後, 我好像明白為何可以這麼準地找出《康熙來了》不同段的影片了。呃.....這是個人使用 YouTube 的經驗談。
2.5 User interface 另外提到 UI 設計, 也滿有意思的, 對照自己的使用經驗, 才明白 YouTube 的用心。2.6 System implementation 提到系統架構設計, 如何兼顧線上服務速率和即時更新資料。內容很短, 不過有些相關經驗的話, 應該會有些收獲。最後驗證的方式也很威, 長時間調整 A/B test, 做了頗為嚴謹的對照, 證明推薦方式確實有效, 但也只有 Google 的人力和 infrastructure 才做得起這種程度的測試吧。
總結來說, 花個一兩小時就能讀完這篇論文, 滿有趣的。
備註: Apache Mahout 有提供 Collaborative Filtering / User and Item based recommenders, 需要用時再來看看。
一開始是在 YouTube转向Amazon的推荐算法 看到別人提到 YouTube uses Amazon's recommendation algorithm。前篇說明後篇作者的背景, 並提了些相關看法, 值得一讀。後篇的作者是當年寫 Amazon item-based collaborative filtering 專利和論文的主要作者 (Greg Linden), 他在自己的 blog 多年來寫了一系列關於 CF、YouTube、他之前的產品 Findory 的看法, 滿有意思的。
另外, YouTube uses Amazon's recommendation algorithm 的這則留言值得一看, 作者用簡短的文字清楚地說明 CF 的核心概念, 以及相關方法 (clustering) 的差異、優勢。在這摘錄部份內容:
In general though, all collaborative filtering methods suffer from typical problems listed in many academic papers, like the cold start problem, popular item dominance, etc. They really work best in massive scale systems [both # of users and # if items]. This is why it did not work that well at Netflix, which has a small number of items [in the 100Ks rather than 100s of millions at Amazon and YouTube], so they needed better methods like the ensemble approach that won the Netflix prize.這有點像 naive bayes classification, 在資料量不足的情況下, 得用些技巧從訓練資料中撈出更多資訊 (例如 NBC 假設 conditional independence, 詳見這篇解釋), 但用得不好就會搞砸。有道是, 「No pain, no gain; no assumption, no gain; wrong assumption, a lot of pain」。這是題外話了。
該則留言的作者自己開家公司做 YouTube 推薦影片。看起來似乎是設定後可以在自己網站放 YouTube 影片, 由他們公司的產品幫忙找關聯影片。賣點大概是高度客製化和提供介面人工管理影片品質。
今天讀完 YouTube 的論文後, 發覺沒太重的 item-based CF 味道, 只是很單純的概念。不過也如同 Greg Linden 在留言提到, PageRank 的想法也沒有很新穎, 但它在業界獲得成效, 造成一個里程碑。Amazon 那篇論文也該獲得類似的對待。由於他自己是該論文的第一作者, 加上他在 Blog 三不五時提到該篇論文的代表性, 很難認同他說的話。只能說, 和名利扯上關係後, 很多事情都無法單純看待, YouTube 那篇論文不 cite Amazon 那篇, 也許是沒看過, 或認為無關聯, 也可能有專利考量吧。
YouTube 這篇論文只有四頁, 但寫得相當漂亮, 先說明 YouTube 各種使用情境, 再指出本篇針對 recommendation, 接著分析資料特性和 Netflix、Amazon 的差異, 分析自家資料分為 content data (如 title) 和 user activity data。其中 user activity data 又分 explicit (如 like, subscription) 和 implicit 的資料 (如 click through rate, long CTR)。說明使用者需求為即時且讓使用者明白的推薦。說明系統需求要讓各元件獨立簡單, 方便理解和除錯。前言的部份, 讀起來滿過癮的。
接著說明演算法時, 只有提到概念, 實際上效果的好壞, 取決於細節特徵和參數怎麼設, 這些應該都是長期間實測的經驗談。不過光是概念部份就有些幫助, 大概知道 YouTube 做了什麼取捨, 和在這樣取捨下, 大方向的優缺點。
首先是定義兩部影片的關聯性為何, 這是整篇的重點。設影片為 vertex、關聯強弱為 edge weight, 就能用 edge weight 排序找出一般性的 top-n 推薦。在使用者登入的情況下, 再用使用者明確喜歡的片子做為 seed set S (vertices 的子集), 由此找出它們 k 步內的點, 而形成發散且具一定準度的推薦候選清單。然後再配合細項資料排序結果。
至於 graph 的建法, 則是先定一個期間 (如 24h), 計算這個期間內任何部影片被同樣人觀看的次數, 於是能用 Cij / Cj 表示影片 j 對影片 i 的關聯度 (Cij 表示多少人看過影片 i 和 j)。這只是一個示意的概念, 關鍵是用一段時間內各使用者觀看影片的相對次數表示關聯程度。Greg Linden 應該就是針對運用這個概念卻沒 cite Amazon 的論文而不滿吧。看完關聯性的找法後, 我好像明白為何可以這麼準地找出《康熙來了》不同段的影片了。呃.....這是個人使用 YouTube 的經驗談。
2.5 User interface 另外提到 UI 設計, 也滿有意思的, 對照自己的使用經驗, 才明白 YouTube 的用心。2.6 System implementation 提到系統架構設計, 如何兼顧線上服務速率和即時更新資料。內容很短, 不過有些相關經驗的話, 應該會有些收獲。最後驗證的方式也很威, 長時間調整 A/B test, 做了頗為嚴謹的對照, 證明推薦方式確實有效, 但也只有 Google 的人力和 infrastructure 才做得起這種程度的測試吧。
總結來說, 花個一兩小時就能讀完這篇論文, 滿有趣的。
備註: Apache Mahout 有提供 Collaborative Filtering / User and Item based recommenders, 需要用時再來看看。
訂閱：
文章 (Atom)