2011年8月19日 星期五

我學 Machine Learning 的方法

這篇是舊文重貼, 寫於 2010-03-01。文章搬到另一個站後, 原本的舊文就遺失在資訊海裡了。挑幾篇和學術相關的重貼過來。

-------------------------------------------------------

有人問我這個問題,想說就寫在這吧。目前還學不到家,只有斷斷續續讀個一陣子,有錯還請大家指正。

讀 Data mining 的書

一開始我讀 data mining 之類的課本、講義,發現內容講得滿概念的。但若只是想拿 ML 來用,那看這類文件會比較容易上手。比方 Introduction to Data Mining 寫得挺不錯的,可謂深入淺出!官網附的投影片挺棒的,可以先「快速」 (相對於看書來說……) 看一遍,再挑有興趣的部份閱讀課本。若有耐性慢慢讀完課本,會較有系統性地認識相關內容。由於碩論做 clustering 的緣故,我有好好地讀書本 clustering 部份。不過 clustering 論文種類多到爆炸,看完這本的內容也只是苦痛的開始而已……。

讀國外大學的授課講義

若想進一步了解 model 的原理,那就需要讀 ML 課程用的課本和講義。這類文件滿多的,其中我強力推薦 Andrew Ng 教的 Stanford CS229 Machine Learning。大部份教材在講解 model 最關鍵的數學時,只會從天空掉下來一句「套用 gradient ascending 求最大值」、「運用 EM 求最佳值」之類的話,接著結果就神奇地飛出來。這份講義卻從最基礎的數學開始講,包含需要用到的微分、線性代數、機率等,讓讀者有能力自己從頭推導數學算式,算是 ML 文件裡最親切的教材。當然,讀者也要有興趣慢慢地啃才行。我大概啃了一半多一點內容,收獲良多。可惜久一沒用也只記得概念了。有機會想再從頭自己推導一次。我覺得 Andrew Ng 數學寫得相當漂亮,這是我第一次察覺寫數學式和寫程式一樣,也有美醜、易懂難懂之分。附帶一提,當初會看這份教材是看 Mr. Saturday 推薦才讀的,感謝 Mr. Saturday 推薦。

後來我陸續看了一些不同國外大學的 ML 課程講義,發覺大家的切入點差很多,各有不同考量。像 MIT OCR 6.867 Machine Learning 有教 HMM,Stanford CS229 沒教。A Fundamentalist Organization of Machine Learning 提到由 Learning theory 的方式切入 ML,而不要走馬看花講一堆 model (作者稱為 “zoo approach”,挺傳神的譬喻)。我只有從 Andrew Ng 的講義裡讀了一點 learning theory,懂些基本觀念 (bias 和 variance),感覺挺有用的。若對 learning to theory 有興趣,印象中該文作者有推薦 15-859(B) Machine Learning Theory,Spring 2009。我看了一晚講義,內容是從簡單的假設環境中推導出明確的性質,還挺有趣的。但看到後來就看不懂了,也不明白能做什麼,就沒繼續看了。

讀 Wikipedia

此外,我發覺 Wikipedia 是學東西的好地方。有代表性的方法早已有系統地記錄下來,又提供詳細的參考資料可以一路讀下去。比方說想學 Linear classifier ,比起查書,查 Wikipedia 更有效率。我常拿 Wikipedia 內容和其它文件交叉對照,弄明白看不懂的部份。讀這些東西需要的是耐心以及不傷眼的 Wikipedia CSS 樣版

讀經典課本

後來又看到 Mr. Saturday 提到 Elements of Statistical Learning: data mining,inference,and prediction. 2nd Edition.,而且官網還有附完整電子書,就載來看看。不得不說這本書數學超硬,但內容超級紮實,相當值得一讀。我挑有興趣且讀得下去的部份加減看,學到 bagging、random forest 等東西,讓我擴展眼界,明白許多原理。除數學太硬之外,這本書另一問題是實驗資料太小了,令人懷疑實驗結果是否適用於真實世界的情況。只好先暫時相信大師,之後再從實驗中確認。

有興趣的話可以在 Amazon 查一下其它書,或以這本書為底看相關書籍。ML 有不少經典書籍,也有針對影像處理或文字處理的。

其它

O’Reilly 出的 Programming Collective Intelligence - O’Reilly Media 也是不錯的書,適合初學者閱讀。配合使用情境,作者簡單地解釋 model 的概念並用 Python 說明如何實作。最令人讚賞的是,作者還有比較各個模型的優缺點。雖然分析的內容不見得正確,對初學者來說挺受用的。

總結

讀這些理論時,我發覺有許多文件提供不同的講解方式,可以多比較一番,找自己看得懂的。不用刻意從某個地方學會某種 model。文中提的是我學習的歷程,每個人的需求不同,數學底也不同,我的經驗不見得適用於其他人。寫在這裡供大家做個參考,有錯還請告知,感謝。

2011年8月6日 星期六

Naive Bayes Classifier 的原理

這篇是舊文重貼, 寫於 2009-02-19。文章搬到另一個站後, 原本的舊文就遺失在資訊海裡了。挑幾篇和學術相關的重貼過來。

-------------------------------------------------------

以前讀 Bayesian probability 時一直有個疑問,為什麼要這樣繞彎來計算?這疑問在讀 Naive Bayes Classifier 時更大了。

假設輸入為屬性 A1、A2、A3 和類別 C1, C2,為什麼不從 training data 裡直接計算出 P(C1 | A1, A2, A3) ?如下所示:

P(C1 | A1, A2, A3) = P(A1, A2, A3, C1) / P(A1, A2, A3) — (1)
P(A1, A2, A3, C1) = N(A1, A2, A3, C1) / N(U)
P(A1, A2, A3) = N(A1, A2, A3) / N(U)

其中 N(.) 表示計算出現次數,U 是宇集。或是更直接一點,直接算數量:

P(C1 | A1, A2, A3) = N(A1, A2, A3, C1) / N(A1, A2, A3) — (2)

可是 Naive Bayes Classifier 卻採用下面這種繞彎的方式子計算:

P(C1 | A1, A2, A3) = P(A1, A2, A3 | C1) * P(C1) / P(A1, A2, A3) — (3)

顯然 (2) 看來直接易懂,為什麼 Naive Bayes Classifier 要用 (3) 的算法呢?畢竟等式右邊各項,也是用 N(.) / N(U) 組出來的。

今天想了許久,終於想通了!關鍵在於 training data 不見得能完整涵蓋所有可能。比方從來沒出現過 (A1, A2, C1) 或 (A1, A2, C2) ,在這種情況下,無法從 training data 裡直接用計數的方式求出 P(C1 | A1, A2) 和 P(C2 | A1, A2) 。於是疑問轉成:「為何 Naive Bayes Classifier 可以計算沒出現過的組合?」

先從定義來看:

P(C1 | A1, A2) = P(A1, A2 | C1) * P(C1) / P(A1, A2)

由於 P(C1 | A1, A2) 和 P(C2 | A1, A2) 的分母一樣,分母可以忽略不算(事實上也算不出來),所以問題簡化為計算上式分子的值。P(C1) 或 P(C2) 可從 training data 裡算估出,但在沒有 P(A1, A2) 的情況下,難道 P(A1, A2 | C1) 可以估的出來?

答案是:「在 conditional independence 的假設下可以!」

假設 A1, A2 在 C1 發生的情況下為 conditional independence,則可得到如下的結果:

P(A1, A2 | C1) = P(A1 | C1) * P(A2 | C1)

原本要求 A1, A2 在 C1 條件下同時出現的機率,成功地轉換為計算各別在 C1 條件下的機率!於是在 A1, …, Ak 對 Ci 都具有 conditional independence 的假設下,只要 training data 內可估出全部的 P(Aj | Ci),就能計算各種 Aj 組合的條件機率!

結論

相較於直接在 training data 內算次數猜類別,Naive Bayes Classifier 的特色是用極少的機率函數 [*1] 表示出所有屬性組合的機率。但是前提是 conditional independence 的假設要成立。若 Ai 和 Aj 有關聯性 ( Ai and Aj are correlate ),會算出錯誤的數據,這時可能得用 Bayesian network

更新 (2009-02-21)

經祖佑 [*2] 說明,在這補充幾點:

  • 我誤用 missing value 一詞,文中已改正為「training data 不完備」。
  • 修改結論,將 Naive Bayes Classifier 的特色寫得更明確。

備註

  1. 若有 k 個屬性和 c 個類別,只要從 training data 裡估出 k * c 個機率函數,就能估計出所有組合((2^k - 1) * c)的機率。
  2. 祖佑回覆的原文如下(從 BBS 複製過來的,排版有點亂):

    一點個人感想

    NBC假設conditional independence的優勢是
    把很大的機率表拆成許多小的機率表相乘,所以減少了機率參數
    因此減少了training data的需求量,或反過來說讓同一筆training data資料意義變大
    而文中所提的”missing value”只是這個優勢下的一個特例而已
    事實上就算完全沒有”missing value”的情況,NBC還是可能有他的優勢存在

    因為自己說要舉例,所以只好舉例
    假設要判斷一部動畫camel喜不喜歡
    觀察的attribute是有沒有蘿莉跟有沒有身材好的女角
    同樣一筆training data [(有蘿莉,沒身材好的女角) => camel喜歡]
    在沒有假設conditional independence的情況下
    就只代表(有,無)這樣的組合camel可能會喜歡
    但是在假設conditional independence的情況下
    代表的是”有蘿莉=>camel可能會喜歡”以及”沒身材好的女角=>camel可能會喜歡”
    所以說同一筆資料的information變大

    但是很明顯的這樣假設的危險就在於也許camel只是不喜歡蘿莉身材好XD
    所以(無蘿莉,無身材好的女角)可能在NBC會被誤判成camel喜歡
    這就是有denpendency的情況下,錯誤假設造成的謬誤
    順帶一提的是我覺得missing value這個詞很怪XD
    因為有另一類問題是在處理某input attribute不存在的情況
    例如training data出現(有蘿莉,”不知道”) => camel喜歡這樣的情況

    前文所說的missing value與其說是missing value
    不如說是training data不足

2011年4月10日 星期日

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 的風格吧。

2011年3月13日 星期日

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