贝叶斯学习

贝叶斯学习的背景

• 发现两件事情之间的关系 (因果分析， 先决条件 &结论) • 在我们的日常生活中，医生的疾病诊断可以被认为是一个贝叶斯学习过程
• $A\to B$
  • e.g. 肺炎 $\to$ 肺癌?
  • 很难直接判断
• 反向思考
  • e.g. 有多少肺癌患者曾经得过肺炎?
    

贝叶斯定理

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

举例: 某项化验测试结果与癌症诊断

• P(h|D) = h的后验概率（posterior probability）
  P(h|D) : 已知测试结果=‘+’, 那么得了这种癌症的概率
• P(h) = h的先验概率（prior probability）
  P(h) : 得这种癌症的概率
• P(D)＝D的先验概率
  P(D)：测试结果 = ‘+’的概率
• P(D|h) = 给定 h 情况下 D 的概率
  P(D|h)：已知一个人得了这种癌症，那么测试结果为‘+’的概率

• P(h)
  • 假设: 互相排斥的
  • H假设空间: 完全详尽$\sum P(h_i)=1$
• P(D)
  • D：所有可能数据中的一个采样集合
  • 与h相互独立
  • 在比较不同假设时可以忽略
• P(D|h) (似然度 likelihood)
• • log likelihood log(P(D|h)

举例

• 化验测试结果: +，患有某种癌症?
  $P(cancer|+)=?$

我们已知:

• 正确的阳性样本: 98% (患有该癌症, 测试结果为 +)
• 正确的阴性样本: 97% (未患该癌症, 测试结果为 -)
• 在整个人群中，只有0.008 的人患这种癌症
  $P(cancer|+)=P(+|cancer)P(cancer)/P(+)=0.98\ast 0.008/(0.98\ast 0.008+0.03\ast 0.992)=0.21$

$P(cancer)=0.008$
$P(\neg cancer)=0.992$

概览

• 贝叶斯定理
  • 用先验概率来推断后验概率
• $MaxAPosterior,MAP,h_{MAP}，极大后验假设$
• $MaximumLikelihood,ML,h_{ML},极大似然假设$
  • • ML vs. LSE (最小二乘，Least Square Error)
• Naïve Bayes, NB, 朴素贝叶斯
  • 独立属性/特征假设
  • NB vs. MAP
• Maximum description length, MDL (最小描述长度)
  • 权衡: 假设复杂度 vs. 假设带来的错误
  • MDL vs. MAP

选择假设— MAP

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

• 一般我们需要在给定训练集上最有可能的假设
• Maximum A Posteriori (MAP): (极大后验假设) 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举例

• 实验室测试结果: +，患有某种特定癌症?

• 当我们已知：

  • 正确的阳性: 98% (患癌, 检测结果 +)
  • 正确的阴性: 97% (不患癌, 检测结果 -)
  • 在整个人群中，只有 0.008 患有癌症
    $\underset{h\in H}{\mathrm{argmax}}P(D|h)P(h)$

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

  选择假设 — 极大似然 ML

  $h_{MAP}=\underset{h\in H}{\mathrm{argmax}}P(D|h)P(h)$
  
  如果知道P(h)，聪明的人总是能最大限度地从经验中学习

• 如果我们完全不知道假设的概率分布，或者我们知道所有的假设发生的概率相同，那么MAP 等价于 Maximum Likelihood (h_ML 极大似然假设)
  $h_{ML}=\underset{h_{i}inH}{\mathrm{argmax}}P(D|h_i)$

ML 举例: 抛硬币问题

• 2 个硬币: P₁(H) = p，P₂(H) = q
• 抛1号硬币的概率是 a
• 但是 a, p, q 未知的
• 观察到一些产生序列:
  • 2HHHT，1HTHT， 2HHHT， 2HTTH
• 估计 a, p, q 最有可能的值

• “简单” 估计: ML (maximum likelihood，极大似然)
  - 抛一个(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}$$
• 求最大值，对 p 求导令导数为 0:$\frac{d(logL(D|p))}{dp}=\frac{k}{p}-\frac{m-k}{1-p}=0$
• 求解 p，得到:$p=k/m$

• 估计 a, p, q 最有可能的值
a = 1/4, p = 2/4, q = 8/12

极大似然 & 最小二乘

• 训练数据: $<x_i,d_i>$
• $d_i=f(x_i)+e_i$
  • d_i : 独立的样本.
  • f(x_i): 没有噪声的目标函数值
  • e_i: 噪声，独立随机变量，正态分布 $N(0,{\sigma }^2)$
• $\to$ d_i : 正态分布 $N(f(x_i),{\sigma }^2)$
  
  
• 独立随机变量，正态分布噪声 $N(0,{\sigma }^2),h_{ML}=h_{LSE}$

Naïve Bayesian Classifier (朴素贝叶斯分类器)

• 假设目标函数 f : $X\to V$，其中每个样本 x = (a1, a2, …, an). 那么最有可能的 f(x) 的值是:
  $v_{MAP}=\underset{v_j\in V}{\mathrm{argmax}}P(x|v_j)P(v_j)$
• 朴素贝叶斯假设:
  $$P(x|v_j)=P(a_1,a_2...a_n|v_j)=\prod _{i}P(a_i|v_j)$$
  $每个属性a_1,a_2...a_n独立$
• 朴素贝叶斯分类器:
  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​)}​
  如果满足属性之间的独立性，那么 $v_{MAP}=v_{NB}$

举例1：词义消歧 (Word Sense Disambiguation)

• e.g. fly =? bank = ?
• 对于单词 w，使用上下文 c 进行词义消歧
  • e.g. A fly flies into the kitchen while he fry the chicken. （他在炸鸡时一只苍蝇飞进了厨房）
  • 上下文 c: 在词 w 周围的一组词w_i(即：特征 / 属性)
  • si: 词 w 的第 i^th 个含义(即：输出标签)
• 朴素贝叶斯假设: $$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 发送者
• 第四季度主要垃圾邮件来源 (数据来自 Sophos)
  • 美国 (21.3% 垃圾信息来源，较28.4%有所下降)
  • 俄罗斯 (8.3%, 较 4.4% 有上升)
  • 中国 (4.2%, 较 4.9% 有下降)
  • 巴西 (4.0%, 较 3.7% 有上升)

垃圾邮件过滤问题中人们学到的经验：

• 不要武断地忽略任何信息
  • E.g. 邮件头信息
• 不同的代价: 假阳性 v.s. 假阴性
• 一个非常好的参考报告: http://www.paulgraham.com/better.html

从垃圾邮件过滤中学到的经验

(根据报告:)
早期关于贝叶斯垃圾邮件过滤的论文有两篇，于1998年发表在同一个会议

1) 作者是 Pantel 和 Lin; 2) Microsoft 研究院的一个小组

Pantel 和 Lin的过滤方法效果更好
但它只能捕捉92%的垃圾邮件，且有1.16% 假阳性错误
文章作者实现了一个贝叶斯垃圾邮件过滤器
它 能捕捉 99.5%的垃圾邮件 且 假阳性错误低于0.03%

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

• 5 处不同

1. 他们训练过滤器的数据非常少:
   • 160 垃圾邮件和466非垃圾邮件
     2.最重要的一个不同可能是他们忽略了邮件头
     3.Pantel 和 Lin 对词进行了stemming (词干化) —— 做法有些草率了
     4.计算概率的方式不同。他们使用了全部的词，但作者只用了最显著的15个词
     5.他们没有对假阳性做偏置。而作者考虑了：对非垃圾邮件中出现的词频翻倍

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

• 奥卡姆剃刀:
  • 偏向于最短的假设
• MDL：
  • 偏向假设 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解释（基于信息理论）

• 为随机发送的信息所设计的编码
  • 遇到消息 i 的概率是 p_i
• 所需的最短编码(最小期望传输位数)是什么？
  • 为可能性较大的消息赋予较短的编码
    
• 最优编码对消息i 的编码长度为 -log₂ p 比特 [Shannon & Weaver 1949]
  

MDL 和 MAP

-log₂ p (h): 假设空间H最优编码下，h 的长度
-log2 p (D|h): 最优编码下，给定h 时D 的描述长度

对MDL的另一个解释

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编码数据的代价

  • 假设实例的序列以及编码规则对发送者和接收者来说都是已知的
  • 没有分类错误: 除h外不需要传输额外的信息
  • 如果 h 错误分类了某些样本，则需要传输:
    • 1. **哪个实例出错了? **
         – 最多 log₂m (m: 实例的个数)
    • 2. **正确的分类结果是什么? **
         – 最多 log2k (k: 类别的个数)

• 权衡: 假设的复杂程度 vs. 由假设造成的错误数

  • 更偏好 一个短的且错误更少的假设
    而不是一个长的但完美分类训练数据的假设
    

总结

• 贝叶斯定理
  • 用先验概率来推断后验概率
• $MaxAPosterior,MAP,h_{MAP}，极大后验假设$
• $MaximumLikelihood,ML,h_{ML},极大似然假设$
  • • ML vs. LSE (最小二乘，Least Square Error)
• Naïve Bayes, NB, 朴素贝叶斯
  • 独立属性/特征假设
  • NB vs. MAP
• Maximum description length, MDL (最小描述长度)
  • 权衡: 假设复杂度 vs. 假设带来的错误
  • MDL vs. MAP