37

朴素贝叶斯

 3 years ago
source link: https://mp.weixin.qq.com/s/N42KsWkmGWi0f-LgbKGePg?amp%3Butm_medium=referral
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

引言

你在新加坡国立大学里面徜徉,见到一个人 (斯蒂文) 问他的性格是内向还是外向,得到的答案是内向,那么斯蒂文是数学博士还是商科学生? (假设斯蒂文只可能是这两者之一,即斯蒂文不可能是艺术院学生)

告诉我你的直觉,斯蒂文更有可能是数学博士对吗?因为一般数学博士比商科学生 更容易 内向些 (没有歧视)。你的直觉可以用数学这样表示出来

P( 内向 |数学博士) > P( 内向 |商科学生)

P(A|B) 代表在 B 的条件下 A 的概率,因此你的直觉是 当一个人是数学博士他内向的概率比这个人是商科学生他内向的概率大 (陈述 1) 。但是问题是比较以下两个概率

P(数学博士| 内向 ) ? P(商科学生| 内向

在知道这个人是内向性格后,问他是数学博士和商科学生的概率哪个大(陈述 2)

即便你不懂高深的概率,你至少可以分清这两种陈述的区别吧。根据调查结果,假设数学博士内向的概率是 75%,而商科学生内向的概率是 15%,下面我们用一种非常直观的方法来解决问题 (见以下三幅图):

例一

RbyUNzy.png!web

根据调查,假设数学博士和商科学生的人数比例是 1:10,上下两个长方形框的面积分别代表数学博士和商科学生的人数。数学博士内向的概率是 75% 指的这 1 份数学博士中有 0.75 份是内向的;而商科学生内向的概率是 15% 指的这 10 份商科学生中有 1.5 份是内向的。忽略百分号,我们计算出 当斯蒂文性格内向,他是数学博士和商科学生的比例是 75:150 也就是 1:2。 因此斯蒂文更可能是商科学生 。这很违背直觉对吗?原因就是商科学生比数学博士人数多太多了。

例二

IvIbe2v.png!web

假设数学博士和商科学生的人数比例变成是 1:5,根据以上的算法,我们计算出当一个人性格内向,斯蒂文是数学博士和商科学生的比例是 75:75 也就是 1:1。 因此斯蒂文是数学博士和商科学生的可能性一样

例三

qMzm63z.png!web

假设数学博士和商科学生的人数比例变成是 1:3,根据以上的算法,我们计算出当一个人性格内向,斯蒂文是数学博士和商科学生的比例是 75:45 也就是 5:3。 因此斯蒂文更可能是数学博士

上面三个例子都用以下公式

后验比例 = 先验比例 × 可能性比例

其中

  • 类别 – 在本例就是“内向”

  • 先验比例  – 没做试验之前的比例,在本例就是两类人的人数比例,和“内向”类别无关

  • 可能性比例 – 人的直觉在评估这一点最强,在本例就是两类人内向的比例

  • 后验比例 – 做过实验之后的比例,在本例就是如果内向而两类人的比例

判断斯蒂文是数学博士还是商科学生和 先验比例可能性比例 有关。即便我们认为数学博士比起商科学生更容易内向 ( 可能性比例 ),但是在例一里商科学生人数比例太大 10 比 1 ( 先验比例 ),因此还是认为斯蒂文是商科学生。在例三中商科学生人数比例已下降到 3 比 1,这是 可能性比例 开始起作用了,因此认为斯蒂文是数学博士。例二是 先验比例 和可能性比例达到一个临界点,商科学生人数的较大 先验比例 和较小 可能性比例 ,和数学博士人数的较小 先验比例 和较大 可能性比例 ,打了个平手。

此外,试想你目的是为了快速对判断斯蒂文是数学博士还是商科学生,而你的方法是提问题。

  1. 在本例中,你问斯蒂文内向还是外向,答案是内向,这时根据调查可以知道两类人的 可能性比例 ,再加上两类人的 先验比例 可以算出 后验比例

  2. 假如你问斯蒂文早上吃过早餐吗,答案不管是什么,对后验比例都没什么影响,因为这两类人早上吃早餐的 可能性比例 相同。 先验比例 决定了 后验比例 。因此这个提问没有任何价值

  3. 假如你问斯蒂文是不是数学博士,答案不管是什么,你都能马上确定斯蒂文是不是数学博士因为他已经正面回答了你。 先验比例 不起任何作用。这次这个提问太一针见血但是有作弊嫌疑

根据上面比例关系式,我们类比出概率关系式

后验比例 = 先验比例 × 可能性比例

后验概率 = c × 先验概率 × 可能性

其中 c 是一个正规范常数,它使得后验概率是一个真正的概率值。而这个公式就是大名鼎鼎的贝叶斯公式。用该公式加上特征相互条件独立 (conditional independent) 的假设,就可得到朴素贝叶斯 (naïve Bayes) 分类器。它的核心思想真的很简单很朴素,大家跟我走一遭吧。

本贴目录如下:

第一章 - 前戏王

1.1 频率学派和贝叶斯学派

1.2 独立和条件独立

1.3 贝叶斯公式

1.4 生成学习算法和判别学习算法

1.5 最大似然估计和最大后验估计

1.6 概率分布

第二章 - 理论皇

2.1 数学符号

2.2 问题剖析

2.3 邮件分类

2.4 朴素贝叶斯算法

2.5 多元伯努利事件模型

2.6 多项事件模型

2.7 高斯判别分析模型

第三章 - 实践狼

3.1 拉普拉斯校正

3.2 多分类问题

3.3 高斯判别分析模型和对率模型

3.4 最大似然估计和最大后验估计

总结和下帖预告

第一章 - 前戏王

1.1 频率学派和贝叶斯学派

在概率学上有两大学派, 频率学派 (frequentist) 和 贝叶斯学派 (Bayesian)。

什么是概率?即使没学过概率论的人都知道概率就是事情发生的可能性。但是,这个所谓的“可能性”,到底是客观存在于这个世界里的 ( 频率学派 ),还是存在于我们主观的想法之中 ( 贝叶斯学派 )?

频率学派 只相信客观的、能测量的东西,而认为概率是频率在无限多次重复试验时的极限值 。比如丢硬币,丢 N 次 (N 是个很大的数) 而记录下来正面朝上的次数 n,因此硬币正面朝上的概率为 n/N。

贝叶斯学派 认为概率只不过是我们思想中对事情发生可能性的一种猜测与信念 。我觉得一件事情八九不离十,那么对于我来说它的概率就大,我觉得一件事情希望渺茫,它的概率就小。当然,我的看法也不一定对,看到了新的现象,我就修正我的信念,这不是所有人应该做的事吗?

频率学派贝叶斯学派 的个人猜测太过于主观而且很可能是错的。对于某个事件发生的概率 q 是客观存在的,是一个老天知道的确定的数值。比如丢硬币,只要你选定了硬币,q 就是个确凿的数,在冥冥中掌控着抛出的结果。任何不确定性都只存在于数据之中。所以, 贝叶斯学派 说的那些主观猜测,在 频率学派 看来都是不存在的事情。如果人人都按自己的意愿、甚至按自己想要什么结果来设定先验概率,那岂不是乱套了?

贝叶斯学派 说我们既非上帝,也没有长生不老之躯能在千百万个平行空间中做无限多次重复试验。某个事件发生的概率 q 我不知道有没有一个真实确定的数值,即使有我也没法知道,不过我会收集信息来形成一个看法。比如丢硬币,我看看它的样子不太奇怪,我就觉得它应该挺均匀的,所以 q 应该和 0.5 挺接近的。我再把它拿到手抛几次,根据正反面出现的次数的多少,修正我对于 q 等于 0.5 的概率的看法。我相信随着收集信息的增多,我的估计会越来越精确。

两种学派都有自己的道理,谁也很难说服谁,但是在机器学习中我们比较倾向于 贝叶斯学派 。一开始在计算条件概率时 (先直接给出贝叶斯公式)

P(假想|数据) = P(数据|假想) /  P(数据)  × P(假想)

当假想太多时, P(数据) 是非常难计算的,因此 贝叶斯学派 的思想只能用于非常简单的应用上。现在计算机的发展日新月异,同时 贝叶斯学派 练就了一个新利器叫做马尔可夫链蒙特卡洛 (Markov Chain Monte Carlo, MCMC),未来将会是 贝叶斯学派 收复失地的时代。

1.2 独立和条件独立

这两个概念很重要但又容易混淆,条件独立 (conditionally independent) 是朴素贝叶斯的一个重要假设,让我们来看看两个例子:

例1:事件A和B独立但在条件C下不独立

假如你扔两个正常硬币 (正反面的概率都是 50%)

  • 事件A:第一个硬币是正面

  • 事件B:第二个硬币是正面

  • 事件C:二次扔的结果一样

很显然 A 和 B 独立,数学上证明

P(A)P(B) = 1/2 ∙ 1/2 = 1/4

P(AB) = 1/4

P(AB) = P(A)P(B)

但是在 C 条件下 A 和 B 不独立,因为当你知道 C 和 A 后,你可以确定 B 的概率是 1。数学上证明

P(A|C)P(B|C) = 1/2 ∙ 1/2 = 1/4

P(AB|C) = P(B|C)P(B|AC) = 1/2 ∙ 1 = 1/2

P(AB|C) ≠ P(A|C)P(B|C)

例2:事件A和B不独立但在条件C下独立

假如盒子里有一个正常硬币和一个两面都是正面的硬币,你 随机 选一个扔

  • 事件A:第一个硬币是正面

  • 事件B:第二个硬币是正面

  • 事件C:正常硬币被选了

A 和 B 不独立,数学上证明

P(A) = 0.5 ∙ 1/2 + 0.5 ∙ 1 = 3/4

P(B) = 0.5 ∙ 1/2 + 0.5 ∙ 1 = 3/4

P(AB) = 0.5 ∙ 1/2 ∙ 1/2 + 0.5 ∙ 1 ∙ 1 = 5/8

P(AB) ≠ P(A)P(B)

但是在 C 条件下 A 和 B 独立,因为当你知道 C 后就知道正常硬币被选了。数学上证明

P(A|C)P(B|C) = 1/2 ∙ 1/2 = 1/4

P(AB|C) = 1/4

P(AB|C) = P(A|C)P(B|C) 

1.3 贝叶斯公式

根据概率的乘法规则和对称性,我们有

QfqeueF.png!web

和机器学习息息相关的贝叶斯公式为

z6fiAjB.png!web

其中假想 (hypothesis) 也可称为模型 (model),或监督学习里面的标记 (label),而数据 (data) 也可称为信息 (information),是监督学习里面的特征 (feature),再者

  • P( 假想 ) 是假想的先验概率 (prior probability), 可以是基于历史数据的统计,可以由背景常识得出,也可以是人的主观观点给出

  • P( 数据 | 假想 ) 是给定假想后数据的可能性 (likelihood) 或条件概率,一般是通过历史数据统计得到,或者人为主观给出

  • P( 假想 | 数据 ) 是假想的后验概率 (posteriori probability),是需要求的目标

  • P( 数据 ) 是数据的先验概率,如果仅仅是通过后验概率大小来分类那么都不用计算它,只有在算出后验概率具体数值时才需要计算它

贝叶斯公式其实就是告诉我们,怎样根据观察到的数据来更新我们的先验概率,从而获得对假说的新看法– 后验概率。

再进一步将贝叶斯公式变形可得

UZNJJnz.png!web

这就是贝叶斯推断的含义。我们先预估一个“先验概率”,然后加入实验结果,看这个实验到底是增强还是削弱了“先验概率”,由此得到更接近事实的"后验概率"。在这里,如果“调整因子” P( 数据 | 假想 ) / P( 数据 )

  • 大于 1,意味着"先验概率"被增强,假想发生的可能性变大

  • 等于 1,意味着数据无助于判断假想的可能性

  • 小于 1,意味着"先验概率"被削弱,假想发生的可能性变小

1.4 生成学习算法和判别学习算法

回顾贝叶斯公式

P(y|x) = P(x|y)P(y) / P(x)

假设 y 是类别,x 是数据,再分类问题上我们可以采用两套方法

  1. 判别学习算法 (discriminative learning algorithm): 直接 对 P(y|x)  建模,比如

  • P(y|x) = θ T x,线性回归

  • P(y|x) = 1/[1+exp(- θ T x)],对率分类

生成学习算法 (generative learning algorithm): 直接对 p(x|y) 和 p(y) 建模,比如在二分类问题中

  • P(y) 是伯努利分布,正类概率为 p,反类概率为 1-p

  • P(x|y) 可以是任何合理的概率分布,比如正态、伯努利或多项分布

或者在多分类问题中

  • P(y) 是分类分布,类 k 的概率为 p k

  • P(x|y) 可以是任何合理的概率分布,比如正态、伯努利或多项分布

最后再根据贝叶斯公式计算 p(y|x) = P(x|y)P(y)/P(x),因此生成学习算法是 间接 对 p(y|x) 建模。

1.5 最大似然估计和最大后验 估计

让我们用一个简单的例子开始讨论如何估计概率,并探索两种直观的算法。这将会证明这两个直观算法涵盖了机器学习中用到的所有概率算法。

你有一个硬币,由随机变量 X 表示扔硬币的结果,正面向上 X = 1,反面向上 X = 0。现在的学习任务是估计它正面向上的概率。我们用 q 来表示它真实的但未知的概率。

现在你开始做实验,扔了硬币 n 次,观察到正面 n 1 次,反面  n 2   次,那么这枚硬币正面向上的概率是多少?大多数人都是立即给出一个非常直观的答案,用观察正面的次数除以总次数。这就是我们要讨论的第一个算法。

算法 1:给定观察正面 n 1   次,反面  n 2   次,正面朝上的概率

q = n 1   / ( n 1  n 2 )

举例说明,你扔了 50 次,24 正面 26 反面,那么 q = 24/50 = 0.48。

这种方法是合理的,但前提是有大量的数据。如果数据非常稀少,它会产生不可靠的概率估计。例如,如果我们只扔 3 次,有可能观察到的是 1 正 2 反,那么估计出来的概率分别为 0.33。这时候如果你有先验知识,比如你知道这个硬币是政府铸造的正常硬币 (正反面的概率都是 50%)。那么你根据你的观察结果还会回答这个硬币正面向上的概率是 0.33 吗?应该不会吧,那问题到底出在哪了呢?这就引出了第二个算法,一种使我们能够结合先前知识以及观察的数据,以产生最终概率估计。

算法 2 允许我们表达之前对硬币的假设或知识,通过添加任何数量的虚拟正面和反面的次数,正面记为 a 1   次,反面记为  a 次。

算法 2 :给定观察正面 n 1   次,反面  n 次,利用先前知识添加正面  a 1 次,反面  a 次,正面朝上的概率

q = ( n 1   + a 1 ) / ( n 1   + a 1 + n 2   + a 2 )

算法 2 比起 算法 1 有几个吸引点:

  1. 通过调整 a 1 和  a 的值,很容易反映我们关于真实概率值的先验知识。比如我们认为 q = 0.7,那么将  a 1 = 7 和  a 2 = 3

  2. 通过调整 a 和  a 的强度,很容易表达我们对自己的先验知识的确定程度。比如我们非常确信 q = 0.7,那么将  a 1 = 700 和  a 2 = 300

  3. 如果我们设置 a 1 = 0 和  a 2 = 0,则 算法 2 化简成 算法 1

  4. 当观察数据很多时,虚拟数据影响很小。但是当观察数据稀缺时,先验知识影响很大,但其影响随着丰富的观察而逐渐失色

算法 1 算法 2 都很直观。事实上,这两个算法例示了两种最广泛使用的机器方法。它们分别从两个不同的基本原则推出来的。

  • 算法 1 遵循的原理是最大似然估计 (maximum likelihood estimation, MLE),其中我们来寻求 q 的估计最大化观察数据的概率。事实上,我们可以证明 算法 1  生成的参数 q 使得观测数据比其他任何参数 q 都更有可能发生

  • 算法 2  遵循不同的原理,称为最大后验 估计 (maximum a posteriori estimation, MAPE) ,其中我们给定观察数据并加上背景知识,来寻找最可能的 q 的估计

因此,这两个原则之间的区别在于, 算法 2 可以用背景知识,而 算法 1  不可用。

1.6 概率分布

概率分布可分为 离散 概率分布和 连续 概率分布,对于前者本节需要了解的是伯努利分布、分类分布、二项分布和多类分布;对于后者本节需要了解的是正态分布。首先先了解伯努利实验。

伯努利试验 (Bernoulli trial) 是只有 两种 可能结果的 单次 随机试验。关键词是“ 结果只有两种 ”而且“ 只能试验一次 ”。

伯努利分布 (离散)

伯努利分布 (Bernoulli distribution),又名两点分布或者 0-1 分布。

  • 若伯努利试验成功,则伯努利随机变量取值为 1

  • 若伯努利试验失败,则伯努利随机变量取值为 0

记其成功概率为 p,失败概率为 q = 1 – p,其中 0 < p < 1。

伯努利分布的典型例子是扔一次硬币的概率分布,硬币正面朝上概率为 p 而硬币正面朝上概率为 q。

伯努利随机变量 x ~ Bernoulli(p),只能取值 0 或 1,它的概率函数是

EVJBVfm.png!web

分类分布 (离散)

分类分布 (categorical distribution) 就是互斥事件的发生次数 (大于 2) 的“伯努利分布”。

分类分布的典型例子是扔一次骰子。不同于扔硬币,骰子有6个面对应6个不同的点数,对应的概率分别为 p 1 , p 2 , p 3 , p 4 , p 5 p 6 (注意骰子不一定每个点数的概率为 1/6)。

分类随机变量 x ~ Categorical( p ),有 p k 的概率取值 k (k = 1,2, …,K)。它的概率函数是

nIzM3im.png!web

二项分布 (离散)

二项分布 (binomial distribution) 是 n 个独立的“是/非”试验中成功的次数的离散概率分布,其中每次试验的成功概率为 p。这样的单次成功/失败试验又称为伯努利试验。

也就是说,单次抛硬币是伯努利分布,多次抛硬币是二项分布。当 n = 1 时,二项分布就是伯努利分布。

二项随机变量 x ~ Binomial(p, n),描述 n 次伯努利试验成功了 x 次,因此可取值 x = 0,1, …, n。它的概率函数是

uM3i6fI.png!web

多项分布 (离散)

与二项分布之于伯努利分布相同,多项分布 (multinomial distribution) 相当于进行 n 次分类试验。

单次扔骰子是分类分布,多次扔骰子是多项分布。假设用 D(K, n) 代表一个通用的分布函数,K 是每次试验结果的个数,而 n 是做试验的个数,那么

  • 当 n = 1, K = 2,D(2, 1) 是伯努利分布

  • 当 n > 1, K = 2,D(n, 1) 是二项分布

  • 当 n = 1, K > 2,D(2, K) 是分类分布

  • 当 n > 1, K > 2,D(n, K) 是多项分布

多项随机变量 x ~ Multinomial(p, n),描述 n 次分类试验有 K 个结局,其中 x k 结局 (概率为  p k ) 出现了  n k 次 (k = 1,2, …, K)。它的概率函数是

3ma22eN.png!web

因为多项分布是最通用的,我们看看选择不同的参数 n 和 K,它是否能够化简成二项分布、分类分布和伯努利分布

当 n > 1 和 K = 2 时

BjUVNfb.png!web

从概率函数上看 x 是个 二项随机变量

  • K = 2 意味类别只有 2 类,所以我们可以定义这两类为“成功”和“失败”

  • x k  = n k 指的是成功和失败的次数,因为只有两类,知道一类的次数同时也就知道另一类的次数

当 n = 1 和 K > 2 时

AfmEjqy.png!web

从概率函数上看 x 是个 分类随机变量

  • K > 2 意味着类别超过 2 类

  • n = 1 而且所有  n k  加起来和也为 1,这意味着  n k  中间只有一个为 1 而其他 K-1 个都为 0,类似于指标函数

当 n = 1 和 K = 2 时

MBbAziE.png!web

从概率函数上看 x 是个 伯努利随机变量

  • K = 2 意味着类别只有 2 类,所以我们可以定义这两类为“成功”和“失败”

  • n = 1 而且  n + n 2  也为 1,这意味着  n 1  和  n 2 中间只有一个为 1,类似于指标函数

正态分布 (连续)

一维正态分布是具有两个参数 μ 和 s 2 的连续型随机变量的分布,正态随机变量 x ~ N(μ, s 2 ),它的概率分布函数为

yQvMJjq.png!web

n 维正态分布是具有向量参数 μ 和矩阵参数  Σ 的连续型随机变量的分布,正态随机变量  x ~ N n ( μ , Σ ),它的概率分布函数为

vQbA3i7.png!web

贝塔分布 (连续)

贝塔分布是描述概率的概率分布,它有两个形状参数 和  b ,贝塔随机变量 x ~ Beta( a , b ), 0 ≤ x ≤ 1,它的概率分布函数为

a22qamI.png!web

第二章 - 理论皇

2.1 数学符号

下个给出本章用到的所有符号

2qmammA.png!web

2.2 问题剖析

前面帖子已讲过 线性回归 对率分类 ,这两种都属于判别学习算法,而本贴主要关注的是用生成学习算法来解决二分类问题 (多分类问题也可用类似的解法)。首先回顾生成学习算法的步骤

7rmYRzU.png!web

首先对 P(y) 建模,因为是二分类问题 (y = 0,1),y 最常见就是服从伯努利分布 p(y) = ϕ y (1- ϕ ) (1-y) ,接下来对 P( x |y) 建模 (注: x 通常是向量而不是纯量)

  • 如果向量 x 里的元素只取 0 和 1 的离散值,则 P( x |y) 可服从伯努利分布,这个模型叫做多元伯努利事件 (multivariate Bernoulli event, MBE) 模型。MBE 可用来过滤垃圾邮件

  • 如果向量 x 里的元素取 k 个的离散值,则 P( x |y) 可服从多项分布,这个模型叫做多项事件 (multinomial event, ME) 模型。ME也可用来过滤垃圾邮件

  • 如果向量 x 里的元素取连续值,则 P( x |y) 可服从多维正态分布,这个模型叫做高斯判别分析 (Gaussian discriminant analysis, GDA) 模型。这个名字起的非常奇怪,明明是地道的生成学习算法 (不是判别学习算法),可名字偏偏还有“判别”二字。GDA 模型和对率模型有着深厚的关系

以上模型都有自己的模型参数,这些参数是由训练集决定的。对于一个新数据  x new ,我们用贝叶斯公式我们只需找到一个类别 y,使得其后验概率最大:

ANFJ7ny.png!web

其中  argmax  函数就是使得  P(y| x ) 取得最大值所对应的  值,而最后一步推导是因为分母  P( x new ) 和  无关,因此不影响最大值所对应的  y

在细讲 MBE, ME 和 GDA 模型之前,让我们来看看一个实际的邮件分类问题。

2.3 邮件分类

邮件预处理

在任何机器学习任务之前,略看一下数据的样例是极其必要的。以分类垃圾邮件为例,一篇样例邮件可能是这样的

Anyone knows how much it costs to host a web portal ?

Well, it depends on how many visitors youre expecting.This can be  anywhere from less than 10 bucks a month to a coupleof $100. You  should checkout http://www.rackspace.com/ or perhapsAmazon EC2 if  youre running something big..

To unsubscribe yourself from this mailing list, sendan email to:

[email protected]

在上面邮件内容中,我们看到它包含

  • 网址(URL):http://www.rackspace.com/

  • 邮件地址(email address):groupname-unsubs[email protected]

  • 数字:10, 100, 2

  • 货币符号:$

你可以想象其他邮件也有可能包含网址,邮件地址,数字和货币符号,但是它们具体得内容肯定千奇百怪。因此我们需要正规化这些元素,具体的处理过程如下:

  • 小写:将邮件所有内容变为小写 (BiG和big是一个词)

  • 删掉超文本标记语言 (HTML) 格式:很多邮件有HTML标签,去除它们只留下其中内容

  • 正规化 URL:所有URL都用“httaddr”来替代

  • 正规化 email address:所有email address都用“emailaddr”来替代

  • 正规化数字:所有数字都用“number”来替代

  • 正规化货币符号:所有 $ 标志都用“dollar”来替代

  • 词根检索(word stemming):单词就精简成其词根形式,比如 discount, discounts, discounted, discounting 都用“discount”代替,再比如include,includes, included, including都用“includ”代替,即使它不是一个英文单词

  • 删除非单词:所有非单词和标点符号都被删除,所有空白处 (tabs, newlines, spaces) 都被“单间距空白”代替

预处理之后的邮件如下:

anyon know how much it cost to host a web portal wellit depend on how mani visitor your expect thi can be anywher from less than number buck a month to a coupl of dollarnumb you should checkout httpaddr or perhap amazon ecnumb if your run someth big to unsubscrib yourself from thi mail list send an email to emailaddr

文本字符到数值向量

预处理之后的邮件内容看起来比较正规化了,接下来我们需要把邮件里所有的词一一从“字典”里面找出来,记为一个数值向量。这个字典不是那种标准的英文字典,而是专门用来分类邮件而建的字典。下图展示了一个字典的缩影。

uARJJ3Y.png!web

给了字典之后,上面邮件可以用两种数值表达方式:

第一种 :用一个长度为 字典词数 (本例为 50000 个) 的向量 x,如果向量第 j 个词出现在邮件里,那么  x j = 1;如果没有出现,那么  x j = 0。其向量形式为

UvYf6bv.png!web

该邮件含有 a, anyon 和 know 等词,因此向量对应位置的元素为 1;而邮件不含有 aa, ab 和 zip 等词,因此向量对应位置的元素为 0。总结:该向量是一个只含 0 和 1 的长度为字典词数 n 的向量,因此每封邮件的长度都一样,而且其表达形式没有记录“一个词重复出现多次”的情况。

第二种 :用一个长度为 邮件词数 (本例为 61 个) 的向量  x x j 储存着对应位置的词在字典里的索引位置。其向量形式为

BJrmeyr.png!web

该邮件里 anyon, know, how, it, checkout 和 emailaddr 分别对应着字典里第

886,16916,15053,15621,3498 和  5980  号位置。总结:该向量是一个长度为邮件字数的向量,因此每封邮件的长度都不一样,但是其表达形式可以记录 一个词重复出现多次 的情况。

对比两种方法,我们发现第二种向量的长度明显比第一种向量小很多,因此计算起来也会高效一些。

2.4 朴素贝叶斯算法

朴素贝叶斯算法是基于应用贝叶斯公式与特征之间独立的假设产生的一组算法。给定类变量 y 和特征向量 x 到  x n ,我们有条件独立假设 (对所有 i)

yQJjUzQ.png!web

注意特征  之间是 条件独立 而不是独立。

因此贝叶斯公式简化成朴素贝叶斯公式

3Qfiyqq.png!web

朴素贝叶斯的核心作用就把 n 维联合概率 p( x 1 , x 2 ,…, x n |y) 简化成 n 个 1 维概率 p( x i |y) 的乘积。

用最大后验概率估计 (MAPE) 找到相对应的类 y*

eaeIniR.png!web

朴素贝叶斯的优点有

  • 分类容易且快速,而且在多类预测中表现良好

  • 当条件独立假设成立时分类比其他模型比如对率分类性能更好,而且也需要更少的训练数据

最后一个优点也是它的缺点,就是独立的预测变量的假设。因为在现实生活中几乎不可能获得一组完全独立的预测变量。

在 scikit-learn 里面有现成的朴素贝叶斯分类器 naive_bayes,里面支持正态、伯努利和多项类的模型,代码如下:

yyqMF3U.png!web

2.5 多元伯努利事件模型

在邮件分类问题,一旦将文本字符转化成第一种向量形式 (见 2.3),我们便可用多元伯努利事件 (MBE) 模型来描述

aIreM37.png!web

其中 ϕ j,1 ( ϕ j,0 ) 表示字典里第 j 个词在邮件里而邮件被分为正类 (分类) 的概率,这个概率对于任何一封邮件都是一样的(MBE 模型的假设)。

由此可写出MBE模型一般形式:

fuuieyR.png!web

这里是 ϕ , ϕ j,0  和  ϕ j,1  是模型参数且都是纯量,总共有 2n+1 个参数。

给定训练集 ( x (i) , y (i) ), i = 1, 2, …, m,其中  x (i) 是 1×n 的列向量, y (i) 是纯量。最大化 MBE 模型对应的 对数后验概率 可得到最优参数:

NRziEzj.png!web

感兴趣的同学可看证明

证明

为了简化证明过程,介绍以下变量 (a = 0, 1)

AZjmyim.png!web

MBE 模型的对数后验概率为

yYzeUfI.png!web

对 l 求 ϕ 的偏导数可得

vUjea2b.png!web

对 l 求 ϕ j,a 的偏导数可得 (a = 0, 1)

IJj6Vni.png!web

证毕

2.6 多项事件模型

在邮件分类问题,一旦将文本字符转化成第二种向量形式 (见 2.3),我们便可用多项事件 (ME) 模型来描述

F3Ujyuz.png!web

其中 ϕ k,1 ( ϕ k,0 ) 表示邮件里第 j 个词在字典里的索引位置为 k 而该邮件被分为正类 (分类) 的概率,这个概率只跟索引位置 k 有关而和词在邮件位置 j 无关 (ME 模型的假设)。

由此可写出 ME 模型一般形式:

EzieIzv.png!web

这里是 ϕϕ k,0  和  ϕ k,1  是模型参数且都是纯量,总共有 2n+1 个参数。

给定训练集 ( x (i) , y (i) ), i = 1, 2, …, m,其中  x (i) 是 1× n i 的列向量, y (i) 是纯量。最大化 ME 模型对应的 对数后验概率 可得到最优参数:

U3U7vmf.png!web

感兴趣的同学可看证明

证明

为了简化证明过程,介绍以下变量  (a = 0, 1)

rMN3Ab2.png!web

ME  模型的 对数后验概率

VrUv2uy.png!web

对  求  ϕ   的偏导数可得

6NNJ7vQ.png!web

对  求  ϕ k,a   的偏导数可得  (a = 0, 1)

BNRnYbB.png!web

对于 p =1, 2,…, k-1, k+1, …, n,依次用

因此上式等于

7vAFRvB.png!web

将上面 n-1 式加总得到

zUzeYzF.png!web

证毕

2.7 高斯判别分析模型

GDA 模型表达如下

mUBZVfq.png!web

这里是 ϕ , μ 0 μ 1 , Σ 是模型参数,其中  ϕ 是纯量, μ 0 和  μ 都是1×n 的列向量, Σ  而是 n×n 的矩阵,总共有 (n+1 ) 个参数。为了简化,我们假设 x 在不同的 y 条件下均值不同但方差相同。

给定训练集 ( x (i) , y (i) ), i = 1, 2, …, m,其中  x (i)  是 1×n 的列向量, y (i)  是纯量。最大化 GDA 模型对应的 对数后验概率 可得到最优参数:

MjI7ryz.png!web

感兴趣的同学可看证明

证明

为了简化证明过程,介绍以下变量  (a = 0, 1)

jaYniyI.png!web

GDA  模型的 对数后验概率

MbaYrea.png!web

对  求  ϕ   的偏导数可得

VNBBnaf.png!web

对 l 求 μ 的梯度可得(a = 0, 1)

ii6Rfei.png!web

S = Σ -1 ,因此 | S | = 1/| Σ |,对 l 求  Σ  的梯度可得

NnMvaqE.png!web

证毕

第三章 - 实践狼

3.1 拉普拉斯校正

你给女生发邮件夸她 adorkable,这个词是由 dork(呆子) 来替代 adorable (可爱) 里的 dor,这个词的意思是呆萌。由于这个词太新,它根本不在你原来训练集的邮件里面。假设 adorkable 是字典第 800 个单词,根据上节讲的朴素贝叶斯分类,我们用多元伯努利事件模型可以计算参数

VNJNny2.png!web

因为正类 (垃圾) 和反类 (正常) 邮件都没有见过 adorkable 这个词,因此该分类器认为两类邮件包含这个词的概率都为零。现在计算后验概率

732ueeM.png!web

推出上式第三行是因为在连乘项里有一项 ϕ 800,1   = 0 或  ϕ 800,0 = 0,概率等于 0/0 而不知道如何预测该分类。

更一般的说,一旦模型参数为零,朴素贝叶斯分类就会出问题,这时候拉普拉斯校正 (Laplace correction) 就排上用场了,它的核心思想就是将模型参数校正成

  1. 各自不为 0 的数

  2. 总体和为 1,因为这些参数都是概率

对于多元伯努利事件模型,校正后的参数 ( 红色数字 ) 为

3MnAJjM.png!web

对于多项事件模型,校正后的参数 ( 红色数字 ) 为

iaY3i2j.png!web

3.2 多分类问题

在上一章讨论的全部都是二分类问题,应用到的实例是如何分类垃圾邮件和正常邮件。现在如果任务是分类垃圾邮件、工作邮件和个人邮件这三类 (实际类别可能更多),那么以上讨论的模型还适用吗?

本节用类比方式来推出 MBE, ME 和 GDA 模型的多分类版本。它们最主要区别就是 y 从原来的伯努利分布变成了分类分布。二类和多类条件下的 y 的先验概率如下

Ij2QzmU.png!web

每个模型的模型参数对比如下:

ryqqMnY.jpg!web

3.3 高斯判别分析模型和对率模型

回忆高斯判别分析模型表达如下

quUVfaI.png!web

从高斯判别分析模型中的后验概率开始

veAFrma.png!web

其中 x 0 = 1 是常数项,而参数  w

VnqIjyZ.png!web

我们发现给定适当的参数 w ,高斯判别分析模型可以写成对率模型。实际上当 P(x|y=0) 和 P(x|y=1) 是两个泊松分布式,P(y=1|x) 也能化简成对率模型的表达式。现在问题来了,哪个模型更好?

高斯判别分析模型 (GDA) 比起对率 (L) 模型对需要更强的模型假设。

  • 在不知道数据分布时,用 L 更好,因为它有更强的鲁棒性 (robustness)。试想万一数据是泊松分布,用 GDA 的话一开始连假设都错了,那么性能也可想而知了

  • 在知道数据是正态分布时,用 GDA 更好,因为它的假设更精准,也利用了更多信息来构建模型。同时需要比L更少的数据来进行分类

一句话,你掌握的信息越少,就应该选择模型独立性 (model independent) 强的通用泛化模型,比如对率模型;你掌握的信息越多,就应该选择模型相关性 (model dependent) 强的特定细化模型,比如高斯判别分析模型或泊松判别分析模型。信息掌握的多 不用白不用 ,信息掌握的少 宁可用少而对,也不用多而错

3.4 最大似然估计和最大后验 估计

顾名思义,最大似然估计 (MLE) 是找到可以最大化可能性的参数,而最大后验估计 (MAPE) 是找到可以最大化后验概率的参数。

RFze2yF.png!web

其中 D 代表数据,w 代表模型参数。由上式可知,MLE 和 MAPE 最大化的函数都包含着“可能性函数”,但 MAPE 还要考虑“参数先验概率函数”,一般都会 根据主观经验或者背景知识给一个概率分布

本节用两个例子继续深挖 MLE 和 MAPE 的区别,第一个例子接着小节 1.5 的扔硬币估计概率,第二个例子重新回顾线性回归模型。

例一:扔硬币

扔 n 次硬币观察正面朝上的次数是一个二次分布,给定硬币正面的概率为 w,那么观察正面 n 1 次,反面  n 2 次的概率为

MLE 做法是最大化 lnP([ n 1 , n 2 ]|w)

3M7ZbeA.png!web

对以上表达式求 w 的导数,使之等于零可得到

w =  n 1   / (n 1  +  n 2 )

MAPE 做法是最大化 lnP([ n 1 , n 2 ]|w)P(w),通常用一个贝塔分布来描述参数 w 的先验概率 (因为贝塔分布是对概率建模,而 w 就是个概率)

fAZz2iI.png!web

对以上表达式求 w 的导数,使之等于零可得到

w = (n 1  + a 1 ) / (n 1  + a 1  + n 2  + a 2 )

其中 a 1 = b – 1, a 2 = b – 1。 这不就是我们在  1.5  小节推出的结果 吗? 其中  a 1   和  a 2   可以看作是通过对 硬币的假设而添加任何数量的虚拟正面和反面的次数

例二:线形回归

首先回忆房价面积的线性模型

y (i) w x (i)  +  e (i) e (i)  ~ N( 0,  σ 2 )

当给定参数  w  和  x (i)  时,目标值  y (i)  也服从正态分布:

M3uAV3Q.png!web

由于数据之间是独立同分布的 (independent and identically distributed,iid),

ZrYNZ3Q.png!web

MLE 做法是最大化 lnP( y | x w )

jYNBnmj.png!web

因此 MLE 最小化

nMRF3u7.png!web

MAPE 做法是最大化 lnP( y | x ; w )P( w ),通常用均值为 0 方差为 c -1 I 的正态分布来描述参数 w 的先验概率 (我们假设这样一个分布就是希望参数的绝对值不要离 0 太远,也就是不要有太大的绝对值)

FfEbaqe.png!web

因此 MAPE 最小化

Jryue2Z.png!web

这表达式正是岭回归 (ridge regression) 需要最小化的代价函数。根据我们对参数做的正态分布的假设,就是不希望参数绝对值太大,而岭回归就是控制这一点而避免模型过拟合的。这样看,MAPE 还是比 MLE 看起来高级些啊。MLE 只是客观的最大化数据发生的可能性来求出那个冥冥之中的参数 w ,而 MAPE 主观加入了参数的正态分布的假设,这假设不一定对,如果不对的化再换一个咯,总能碰上一个。

总结:贝叶斯学派与频率学派其本质区别在于, 前者认为参数是 随机变量  (绝对不知道其取值也不 care 知道,给个流行的概率分布即可),而后者认为参数是 确定变量 (只不过不知道其取值而已)

总结和下贴预告

贝叶斯学派重先验,频率学派重似然。

假如你今天很不幸点进这个帖子,假设你又很不幸的看到我的帖子有很多赞,排除朋友圈那些点赞狂人的存在,我们就假设这些赞都是正常人点的好了。那么现在的问题是“这个帖子写的好吗?”

很多人就会觉得,卧槽好牛比,这么多赞帖子绝比好啊,这就是频率学派的观点。频率学派重视数据,而不会对数据带有任何有色眼镜来看待。

但假如机器学习大牛吴恩达也很不幸地点进这个帖子,看了之后轻拍我的肩膀说“ 今天我作为一位长者告诉你一些人生经验,我觉得你啊,还需要学习,搞深度学习的 Hinton, LeCun 和 Goodfellow 那些人,不知道比你高到哪里去了,我和他们谈笑风生! ” 为什么会这样呢?用贝叶斯的看法就是,因为吴恩达的知识比我丰富,所以他的先验告诉他,这篇文章对他就是 too simple sometime naïve,所以他对点赞的数量就不再完全相信了。贝叶斯学派对待数据,是带有感情色彩的。

我交朋友从来不看他有没有钱,反正都没有我有钱” — 王思聪,他这是典型的先验,不注重数据 (钱),带有色眼睛看任何人,典型的贝叶斯流派。

好了,笑话讲完,我觉得贝叶斯公式是最伟大的公式之一!为了避免在贝叶斯分类面临的极高计算成本,我们引入了特征条件独立性假设而将“贝叶斯分类”简化成“朴素贝叶斯分类”。尽管这个假设在现实应用中很难成立,但是朴素贝叶斯在很多分类问题上性能很好。该算法是一种生成学习算法,也入选过“数据挖掘十大算法”。

下一贴讲决策树 (decision tree),该方法是人类在作决定时一种很自然的处理机制。以二分类任务为例,在分类过程通常问一系列“是/非”问题来对新样例进行分类。 Stay Tuned!

fyQjEnE.jpg!web


About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK