貝葉斯學(xué)習(xí)的背景

• 發(fā)現(xiàn)兩件事情之間的關(guān)系 (因果分析， 先決條件 &結(jié)論) ? 在我們的日常生活中，醫(yī)生的疾病診斷可以被認(rèn)為是一個(gè)貝葉斯學(xué)習(xí)過程
• $A\to B$
  • e.g. 肺炎 $\to$ 肺癌?
  • 很難直接判斷
• 反向思考
  • e.g. 有多少肺癌患者曾經(jīng)得過肺炎?
    

貝葉斯定理

$P(h|D)=\frac{P(D|h)P(h)}{P(D)}$

舉例: 某項(xiàng)化驗(yàn)測(cè)試結(jié)果與癌癥診斷

• P(h|D) = h的后驗(yàn)概率（posterior probability）
  P(h|D) : 已知測(cè)試結(jié)果=‘+’, 那么得了這種癌癥的概率
• P(h) = h的先驗(yàn)概率（prior probability）
  P(h) : 得這種癌癥的概率
• P(D)＝D的先驗(yàn)概率
  P(D)：測(cè)試結(jié)果 = ‘+’的概率
• P(D|h) = 給定 h 情況下 D 的概率
  P(D|h)：已知一個(gè)人得了這種癌癥，那么測(cè)試結(jié)果為‘+’的概率

• P(h)
  • 假設(shè): 互相排斥的
  • H假設(shè)空間: 完全詳盡$\sum P(h_i)=1$
• P(D)
  • D：所有可能數(shù)據(jù)中的一個(gè)采樣集合
  • 與h相互獨(dú)立
  • 在比較不同假設(shè)時(shí)可以忽略
• P(D|h) (似然度 likelihood)
• • log likelihood log(P(D|h)

舉例

• 化驗(yàn)測(cè)試結(jié)果: +，患有某種癌癥?
  $P(cancer|+)=?$

我們已知:

• 正確的陽性樣本: 98% (患有該癌癥, 測(cè)試結(jié)果為 +)
• 正確的陰性樣本: 97% (未患該癌癥, 測(cè)試結(jié)果為 -)
• 在整個(gè)人群中，只有0.008 的人患這種癌癥
  $P(cancer|+)=P(+|cancer)P(cancer)/P(+)=0.98?0.008/(0.98?0.008+0.03?0.992)=0.21$

$P(cancer)=0.008$
$P(?cancer)=0.992$

概覽

• 貝葉斯定理
  • 用先驗(yàn)概率來推斷后驗(yàn)概率
• $MaxAPosterior,MAP,h_{MAP}，極大后驗(yàn)假設(shè)$
• $MaximumLikelihood,ML,h_{ML},極大似然假設(shè)$
  • ? ML vs. LSE (最小二乘，Least Square Error)
• Na?ve Bayes, NB, 樸素貝葉斯
  • 獨(dú)立屬性/特征假設(shè)
  • NB vs. MAP
• Maximum description length, MDL (最小描述長度)
  • 權(quán)衡: 假設(shè)復(fù)雜度 vs. 假設(shè)帶來的錯(cuò)誤
  • MDL vs. MAP

選擇假設(shè)— MAP

$P(h|D)=\frac{P(D|h)P(h)}{P(D)}$

• 一般我們需要在給定訓(xùn)練集上最有可能的假設(shè)
• Maximum A Posteriori (MAP): (極大后驗(yàn)假設(shè)) hMA
  $$\begin{array}{rl}{h}_{MAP}& =\underset{h\in H}{\mathrm{argmax}}P(h|D)P(h)\\ & =\underset{h\in H}{\mathrm{argmax}}\frac{P(D|h)P(h)}{P(D)}\\ & =\underset{h\in H}{\mathrm{argmax}}P(D|h)P(h)\end{array}$$

MAP舉例

• 實(shí)驗(yàn)室測(cè)試結(jié)果: +，患有某種特定癌癥?

• 當(dāng)我們已知：

  • 正確的陽性: 98% (患癌, 檢測(cè)結(jié)果 +)
  • 正確的陰性: 97% (不患癌, 檢測(cè)結(jié)果 -)
  • 在整個(gè)人群中，只有 0.008 患有癌癥
    $\underset{h\in H}{\mathrm{argmax}}P(D|h)P(h)$

  $P(+|cancer)P(cancer)=0.0078,P(+|?cancer)P(?cancer)=0.0298$
  $h_{MAP}=?cancer$
  $$\begin{array}{rl}P(cancer)=0.008& P(?cancer)=0.992\\ P(+|cancer)=0.98& P(?|cancer)=0.02\\ P(+|?cancer)=0.03& P(?|?cancer)=0.97\end{array}$$

  選擇假設(shè) — 極大似然 ML

  $h_{MAP}=\underset{h\in H}{\mathrm{argmax}}P(D|h)P(h)$
  
  如果知道P(h)，聰明的人總是能最大限度地從經(jīng)驗(yàn)中學(xué)習(xí)

• 如果我們完全不知道假設(shè)的概率分布，或者我們知道所有的假設(shè)發(fā)生的概率相同，那么MAP 等價(jià)于 Maximum Likelihood (h_ML 極大似然假設(shè))
  $h_{ML}=\underset{h_{i}inH}{\mathrm{argmax}}P(D|h_i)$

ML 舉例: 拋硬幣問題

• 2 個(gè)硬幣: P₁(H) = p，P₂(H) = q
• 拋1號(hào)硬幣的概率是 a
• 但是 a, p, q 未知的
• 觀察到一些產(chǎn)生序列:
  • 2HHHT，1HTHT， 2HHHT， 2HTTH
• 估計(jì) a, p, q 最有可能的值

• “簡單” 估計(jì): ML (maximum likelihood，極大似然)
  - 拋一個(gè)(p,1-p)硬幣 m 次，得到k 次 H 和 m-k 次 T
  $$\begin{array}{rl}logL(D|p)& =logP(D|p)\\ & =log(p^k(1?p{)}^{m?k})\\ & =klogp+(m?k)log(1?p)\end{array}$$
• 求最大值，對(duì) p 求導(dǎo)令導(dǎo)數(shù)為 0:$\frac{d(logL(D|p))}{dp}=\frac{k}{p}?\frac{m?k}{1?p}=0$
• 求解 p，得到:$p=k/m$

? 估計(jì) a, p, q 最有可能的值
a = 1/4, p = 2/4, q = 8/12

極大似然 & 最小二乘

• 訓(xùn)練數(shù)據(jù): $<x_i,d_i>$
• $d_i=f(x_i)+e_i$
  • d_i : 獨(dú)立的樣本.
  • f(x_i): 沒有噪聲的目標(biāo)函數(shù)值
  • e_i: 噪聲，獨(dú)立隨機(jī)變量，正態(tài)分布 $N(0,{\sigma }^2)$
• $\to$ d_i : 正態(tài)分布 $N(f(x_i),{\sigma }^2)$
  
  
• 獨(dú)立隨機(jī)變量，正態(tài)分布噪聲 $N(0,{\sigma }^2),h_{ML}=h_{LSE}$

Na?ve Bayesian Classifier (樸素貝葉斯分類器)

• 假設(shè)目標(biāo)函數(shù) f : $X\to V$，其中每個(gè)樣本 x = (a1, a2, …, an). 那么最有可能的 f(x) 的值是:
  $v_{MAP}=\underset{v_j\in V}{\mathrm{argmax}}P(x|v_j)P(v_j)$
• 樸素貝葉斯假設(shè):
  $$P(x|v_j)=P(a_1,a_2...a_n|v_j)=\prod _{i}P(a_i|v_j)$$
  $每個(gè)屬性a_1,a_2...a_n獨(dú)立$
• 樸素貝葉斯分類器:
  v N B = P v j ∈ V ( v j ) ∏ i P ( a i ∣ v j ) = a r g m a x v j ∈ V { l o g P ( v j ) + ∑ i l o g P ( a i ∣ v j ) } \begin{align*} v_{NB} &= \underset{v_j \in V}P(v_j)\prod_iP(a_i|v_j) \\ &=\underset{v_j \in V}{argmax}\{logP(v_j) + \sum_ilogP(a_i|v_j)\} \\ \end{align*} vNB??=vj?∈VP?(vj?)i∏?P(ai?∣vj?)=vj?∈Vargmax?{logP(vj?)+i∑?logP(ai?∣vj?)}?
  如果滿足屬性之間的獨(dú)立性，那么 $v_{MAP}=v_{NB}$

舉例1：詞義消歧 (Word Sense Disambiguation)

• e.g. fly =? bank = ?
• 對(duì)于單詞 w，使用上下文 c 進(jìn)行詞義消歧
  • e.g. A fly flies into the kitchen while he fry the chicken. （他在炸雞時(shí)一只蒼蠅飛進(jìn)了廚房）
  • 上下文 c: 在詞 w 周圍的一組詞w_i(即：特征 / 屬性)
  • si: 詞 w 的第 i^th 個(gè)含義(即：輸出標(biāo)簽)
• 樸素貝葉斯假設(shè): $$P(c|s_k)=\prod _{w_i\in c}P(w_i|s_k)$$
• 樸素貝葉斯選擇: s = a r g m a x s k { l o g P ( s k ) + ∑ w i ∈ c l o g P ( w i ∣ s k ) } s=\underset{s_k}{argmax}\{logP(s_k) + \sum_{w_i \in c}logP(w_i|s_k)\} s=sk?argmax?{logP(sk?)+wi?∈c∑?logP(wi?∣sk?)}
  其中:$P(s_k)=\frac{C(s_k)}{C(w)}P(w_i|s_k)=\frac{C(w_i,s_k)}{C(s_k)}$

舉例 2: 垃圾郵件過濾

• 垃圾郵件量: 900億/天，80% 來自 <200 發(fā)送者
• 第四季度主要垃圾郵件來源 (數(shù)據(jù)來自 Sophos)
  • 美國 (21.3% 垃圾信息來源，較28.4%有所下降)
  • 俄羅斯 (8.3%, 較 4.4% 有上升)
  • 中國 (4.2%, 較 4.9% 有下降)
  • 巴西 (4.0%, 較 3.7% 有上升)

垃圾郵件過濾問題中人們學(xué)到的經(jīng)驗(yàn)：

• 不要武斷地忽略任何信息
  • E.g. 郵件頭信息
• 不同的代價(jià): 假陽性 v.s. 假陰性
• 一個(gè)非常好的參考報(bào)告: http://www.paulgraham.com/better.html

從垃圾郵件過濾中學(xué)到的經(jīng)驗(yàn)

(根據(jù)報(bào)告:)
早期關(guān)于貝葉斯垃圾郵件過濾的論文有兩篇，于1998年發(fā)表在同一個(gè)會(huì)議

1) 作者是 Pantel 和 Lin; 2) Microsoft 研究院的一個(gè)小組

Pantel 和 Lin的過濾方法效果更好
但它只能捕捉92%的垃圾郵件，且有1.16% 假陽性錯(cuò)誤
文章作者實(shí)現(xiàn)了一個(gè)貝葉斯垃圾郵件過濾器
它 能捕捉 99.5%的垃圾郵件 且 假陽性錯(cuò)誤低于0.03%

Subject*FREE 0.9999
Subject*free 0.9782, 
free 0.6546 
free!! 0.9999

• 5 處不同

1. 他們訓(xùn)練過濾器的數(shù)據(jù)非常少:
   • 160 垃圾郵件和466非垃圾郵件
     2.最重要的一個(gè)不同可能是他們忽略了郵件頭
     3.Pantel 和 Lin 對(duì)詞進(jìn)行了stemming (詞干化) —— 做法有些草率了
     4.計(jì)算概率的方式不同。他們使用了全部的詞，但作者只用了最顯著的15個(gè)詞
     5.他們沒有對(duì)假陽性做偏置。而作者考慮了：對(duì)非垃圾郵件中出現(xiàn)的詞頻翻倍

MDL (最小描述長度，Minimum Description Length)

• 奧卡姆剃刀:
  • 偏向于最短的假設(shè)
• MDL：
  • 偏向假設(shè) h 使得最小化： h M D L = a r g m i n h ∈ H { L C 1 ( h ) + L C 2 ( D ∣ h ) } h_{MDL}=\underset{h \in H}{argmin}\{L_{C_1}(h) + L_{C_2}(D|h)\} hMDL?=h∈Hargmin?{LC1??(h)+LC2??(D∣h)}
    其中 $L_C(x)$是 x在編碼C下的 描述長度

MDL解釋（基于信息理論）

• 為隨機(jī)發(fā)送的信息所設(shè)計(jì)的編碼
  • 遇到消息 i 的概率是 p_i
• 所需的最短編碼(最小期望傳輸位數(shù))是什么？
  • 為可能性較大的消息賦予較短的編碼
    
• 最優(yōu)編碼對(duì)消息i 的編碼長度為 -log₂ p 比特 [Shannon & Weaver 1949]
  

MDL 和 MAP

-log₂ p (h): 假設(shè)空間H最優(yōu)編碼下，h 的長度
-log2 p (D|h): 最優(yōu)編碼下，給定h 時(shí)D 的描述長度

對(duì)MDL的另一個(gè)解釋

h M D L = a r g m i n h ∈ H { L C 1 ( h ) + L C 2 ( D ∣ h ) } h_{MDL} = \underset {h \in H}{argmin}\{L_{C_1}(h) + L_{C_2}(D|h)\} hMDL?=h∈Hargmin?{LC1??(h)+LC2??(D∣h)}

• h的長度 和 給定h編碼數(shù)據(jù)的代價(jià)

  • 假設(shè)實(shí)例的序列以及編碼規(guī)則對(duì)發(fā)送者和接收者來說都是已知的
  • 沒有分類錯(cuò)誤: 除h外不需要傳輸額外的信息
  • 如果 h 錯(cuò)誤分類了某些樣本，則需要傳輸:
    • 1. **哪個(gè)實(shí)例出錯(cuò)了? **
         – 最多 log₂m (m: 實(shí)例的個(gè)數(shù))
    • 2. **正確的分類結(jié)果是什么? **
         – 最多 log2k (k: 類別的個(gè)數(shù))

• 權(quán)衡: 假設(shè)的復(fù)雜程度 vs. 由假設(shè)造成的錯(cuò)誤數(shù)

  • 更偏好 一個(gè)短的且錯(cuò)誤更少的假設(shè)
    而不是一個(gè)長的但完美分類訓(xùn)練數(shù)據(jù)的假設(shè)
    

總結(jié)

• 貝葉斯定理
  • 用先驗(yàn)概率來推斷后驗(yàn)概率
• $MaxAPosterior,MAP,h_{MAP}，極大后驗(yàn)假設(shè)$
• $MaximumLikelihood,ML,h_{ML},極大似然假設(shè)$
  • ? ML vs. LSE (最小二乘，Least Square Error)
• Na?ve Bayes, NB, 樸素貝葉斯
  • 獨(dú)立屬性/特征假設(shè)
  • NB vs. MAP
• Maximum description length, MDL (最小描述長度)
  • 權(quán)衡: 假設(shè)復(fù)雜度 vs. 假設(shè)帶來的錯(cuò)誤
  • MDL vs. MAP