TAOCP閱讀心得: Euclid's algorithm

讀到 TAOCP 1.1 尾聲, Knuth 用數學的形式表示 Euclid's algorithm, 也就是用輾轉相除法求最大公因數。覺得書上的表示方式很妙。原本的英文描述如下:

E1. [Find remainder.] Divide m by n and let r be the remainder. (We will have 0 <= r < n.)

E2. [Is it zero?] If r = 0, the algorithm terminates; n is the answer.

E3. [Reduce.] Set m <-n, n <- r, and go back to step E1.

數學定義摘錄函式定義部份如下:

f((m, n) = (m, n, 0, 1); f((n)) = (n);

f((m, n, r, 1)) = (m, n, remainder of m divided by n, 2);

f((m, n, r, 2)) = (n) if r = 0,      (m, n, r, 3) otherwise;

f((m, n, p, 3)) = (n, p, p, 1)

其中 m, n, p 為 >0 的整數, r 為非負數整數。

在上廁所的時候忽然想通 (廁所真是靈感湧現的好地方), 這和以前讀 Haskell 時看到的東西很像, 將狀態編碼到輸出入裡, 於是可以使用函數定義來達到迴圈的效果。以上例來說, 就是隱藏 while 迴圈, 將 while 內的每個操作拆成連續的數個算式, 用輸入的最後一個數字 (即 1, 2, 3) 來表示和銜接算式的順序。若需要用到 for-loop 的 i 的話 (其實大多數情況用不到它), 可用同樣的方式, 將 i 表現在函數的輸出入上。

於是回頭翻一下 Haskell 的語法, 用生澀的寫法練習表示上面的數學式子, 結果如下:

f(m, n, x, 1) = (m, n, mod m n, 2)
f(m, n, r, 2) | r == 0 = (n, n, n, 4)
f(m, n, r, 2) | r /= 0 = (m, n, r, 3)
f(m, n, p, 3) = (n, p, p, 1)
f(a, b, c, 4) = (a, b, c, 4)

印象中 Haskell 的函數輸出入必須為同一型別, 所以我改寫了一下, 讓程式符合 Haskell 的語法。應該是有其它簡單的寫法, 可以完全表示上面的數學定義, 比方輸入用 list, 自己切參數看數量再決定行為。以後有動力重頭學 Haskell 的話, 再來改寫。

下面是執行 gcd(18, 15) 的過程:

*Main> f(18, 15, 0, 1)
(18,15,3,2)
*Main> f(18, 15, 3, 2)
(18,15,3,3)
*Main> f(18, 15, 3, 3)
(15,3,3,1)
*Main> f(15, 3, 3, 1)
(15,3,0,2)
*Main> f(15, 3, 0, 2)
(3,3,3,4)

一開始我很納悶為什麼 Knuth 要多一步 f((m, n, p, 3)) = (n, p, p 1), 而不是在 r != 0 時就表示成 (n, p, p, 1)。對照原本的數學描述, 才明白這樣才能精確的表示執行成本, 讓每個步驟都是明確且有效的, 這樣寫更符合 algorithm 的定義。

那麼, 以上這串體悟對現實開發軟體有何幫助呢? 我覺得這是一個精簡表示數學和演算法的好例子。過去, 我從學習 imperative programming 到學習 OOP, 還有後來稍微學習 functional programming (相關介紹), 發覺兩者有很大的差異。有些在 imperative programming / OOP 裡很難做的事, 在 FP 裡卻不是什麼困難的事。基本論點不同, 表現想法的方式不同, 帶來的優缺點也不同。一直想找機會從頭練習 FP 的思維。附帶一提, 最近 CMU 決定要用 ML 教大一 FP。FP 似乎愈來愈紅了。

2011-04-10 更新

經曾出國深造的 command 說明, 查了一下定義 data type 的方法, 改寫 Haskell 程式如下:

data I = V1 (Integer)
         | V2 (Integer, Integer)
         | V4 (Integer, Integer, Integer, Integer) deriving Show

g :: I -> I
g(V1 (x)) = V1 (x)
g(V2 (m, n)) = V4 (m, n, 0, 1)
g(V4 (m, n, x, 1)) = V4 (m, n, mod m n, 2)
g(V4 (m, n, r, 2)) | r == 0 = V1 (n)
g(V4 (m, n, r, 2)) | r /= 0 = V4 (m, n, r, 3)
g(V4 (m, n, p, 3)) = V4 (n, p, p, 1)

感覺上好像沒有比較清楚, 或是我沒抓到或不習慣 Haskell 的風格吧。

新 blog 開張

有鑑於若等心得慢慢磨好再發表, 大概十篇有九篇半會胎死腹中, 決定仿效成果不錯的技術隨手記, 來個學術隨手記。不過看學術相關的頻率應該比技術低, 要做最低限度查證的時間也比較久。這裡發文頻率應該不會高吧。目前尚有先前看 IBM Watson 的心得可以寫個一兩篇文章, Plurk 上好像也有幾則碎碎念可以轉成文章, 之後再找時間補寫。

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) 的差異、優勢。在這摘錄部份內容:

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, 需要用時再來看看。