social network 真方便, 透過它問到不少好東西, 備忘一下。
原文出處:
線上編輯數學式子產生圖檔, 可貼圖檔連結到任何地方
若要嵌在 Blog 裡的話, 可考慮
有人問我這個問題，想說就寫在這吧。目前還學不到家，只有斷斷續續讀個一陣子，有錯還請大家指正。
一開始我讀 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 是學東西的好地方。有代表性的方法早已有系統地記錄下來，又提供詳細的參考資料可以一路讀下去。比方說想學 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。文中提的是我學習的歷程，每個人的需求不同，數學底也不同，我的經驗不見得適用於其他人。寫在這裡供大家做個參考，有錯還請告知，感謝。
這篇是舊文重貼, 寫於 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。
經祖佑 [*2] 說明，在這補充幾點：
一點個人感想
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不足
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);其中 m, n, p 為 >0 的整數, r 為非負數整數。
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)
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)
*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)
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 的風格吧。
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」。這是題外話了。