贝叶斯(Bayes)——算法概念梳理与实际应用
贝叶斯法是关于随机事件A和B的条件概率和边缘概率的。
其中P(A|B)是在B发生的情况下A发生的可能性。 为完备事件组，即
在贝叶斯法则中，每个名词都有约定俗成的名称：
P(A)是A的先验概率或边缘概率。之所以称为"先验"是因为它不考虑任何B方面的因素。
P(A|B)是已知B发生后A的条件概率，也由于得自B的取值而被称作A的后验概率。
P(B|A)是已知A发生后B的条件概率，也由于得自A的取值而被称作B的后验概率。
P(B)是B的先验概率或边缘概率，也作标准化常量（normalized constant）。
按这些术语，Bayes法则可表述为：
后验概率 = (似然度 * 先验概率)/标准化常量 也就是说，后验概率与先验概率和似然度的乘积成正比。
另外，比例Pr(B|A)/Pr(B)也有时被称作标准似然度（standardised likelihood），Bayes法则可表述为：
后验概率 = 标准似然度 * 先验概率。
正文引出：
1. 贝叶斯决策论
2. 极大似然估计
-
频率派 把需要推断的参数θ看做是固定的未知常数，即概率虽然是未知的，但最起码是确定的一个值，同时，样本X 是随机的，所以频率派重点研究样本空间，大部分的概率计算都是针对样本X 的分布；
-
贝叶斯派 的观点则截然相反，他们认为参数是随机变量，而样本X 是固定的，由于样本是固定的，所以他们重点研究的是参数的分布。
此处介绍源自频率主义学派的极大似然估计(Maximum Likelihood Estimation，简称MLE)，这是根据数据采样来估计概率分布参数的经典方法。 令Dc表示训练集D中第c类样本组成的集合，假设这些样本是独立同分布的，则参数 θc 对于数据集 Dc 的似然是
对 θc 进行极大似然估计，就是去寻找能最大化似然P(Dc | θc )的参数值
此时参数 θc 的极大似然估计
需注意的是，这种参数化的方法虽能使类条件概率估计变得相对简单，但估计结果的准确性严重依赖于所假设的概率分布形式是否符合潜在的真实数据分布.在现实应用中，欲做出能较好地接近潜在真实分布的假设，往往需在一定程度上利用关于应用任务本身的经验知识，否则若仅凭“猜测”来假设概率分布形式，很可能产生误导性的结果.
3. 朴素贝叶斯分类器
估计后验概率 P(c|x) 的主要困难在于：类条件概率式 P(x|c) 是所有属性上的联合概率，难以从有限的训练样本直接估计而得。 为避开这个障碍，朴素贝叶斯分类器(naive Bayes classifier)采用了“属性条件独立性假设”(attribute conditional independence assumption)：对已知类别，假设所有属性相互独立.换言之，假设每个属性独立地对分类结果发生影响. 基于属性条件独立性假设，则：
其中 d为属性数目，xi 为 x 在第 i 个属性上的取值。 由于对所有类别来说P(x)相同，因此有
“拉普拉斯修正”(Laplacian correction).
为了避免其他属性携带的信息被训练集中未出现的属性值“抹去”，在估计概率值时通常要进行“平滑”(smoothing)，常用“拉普拉斯修正”(Laplacian correction)。具体来说，令N表示训练集D中可能的类别数，从表示第i个属性可能的取值数，则式(7.16)和(7.17)分别修正为
拉普拉斯修正避免了因训练集样本不充分而导致概率估值为零的问题，并且在训练集变大时，修正过程所引入的先验(prior)的影响也会逐渐变得可忽略，使得估值渐趋向于实际概率值.
现实任务中朴素贝叶斯分类器有多种使用方式。例如，若任务对预测速度要求较高，则对给定训练集，可将朴素贝叶斯分类器涉及的所有概率估值事先计算好存储起来，这样在进行预测时只需“查表”即可进行判别；若任务数据更替频繁，则可采用“’懒惰学习”(lazy learning)方式，先不进行任何训练，待收到预测请求时再根据当前数据集进行概率估值；若数据不断增加，则可在现有估值基础上，仅对新增样本的属性值所涉及的概率估值进行计数修正即可实现增量学习.
4. 半朴素贝叶斯分类器
为了降低贝叶斯公式(7.8)中估计后验概率 P(c|x) 的困难，朴素贝叶斯分类器采用了属性条件独立性假设，但在现实任务中这个假设往往很难成立。 于是，人们尝试对属性条件独立性假设进行一定程度的放松，由此产生了一类称为“半朴素贝叶斯分类器”(semi-naive Bayes classifiers)的学习方法。 半朴素贝叶斯分类器的基本想法是适当考虑一部分属性间的相互依赖信息，从而既不需进行完全联合概率计算，又不至于彻底忽略了比较强的属性依赖关系。
“独依赖估计”(One-Dependent Estimator，简称ODE)是半朴素贝叶斯分类器最常用的一种策略.顾名思议，所谓“独依赖”就是假设每个属性在类别之外最多仅依赖于一个其他属性，即
其中pai为属性 xi 所依赖的属性，称为xi的父属性。此时，对每个属性 xi，若其父属性pai己知，则可采用类似式(7.20)的办法来估计概率值P(xi | c, pai)。于是，问题的关键就转化为如何确定每个属性的父属性，不同的做法产生不同的独依赖分类器。
SPODE (Super-Parent ODE)方法：最直接的做法是假设所有属性都依赖于同一个属性，称为“超父”(super-parent)，然后通过交叉验证等模型选择方法来确定超父属性，由此形成了.例如，在图7.1(b)中，x1 是超父属性。
TAN (Tree Augmented naive Bayes)方法：是在最大带权生成树算法的基础上，通过以下步骤将属性间依赖关系约简为如图7.1(c)所示的树形结构：
容易看出，条件互信息 I 功刻画了属性xi，和 xj 在已知类别情况下的相关性，因此，通过最大生成树算法，TAN实际上仅保留了强相关属性之间的依赖性。
AODE (Averaged One-Dependent Estimator)方法：是一种基于集成学习机制、更为强大的独依赖分类器。与SPODE通过模型选择确定超父属性不同，AODE尝试将每个属性作为超父来构建SPODE，然后将那些具有足够训练数据支撑的SPODE集成起来作为最终结果，即
其中Dxi是在第 i 个属性上取值为 xi 的样本的集合，m‘ 为阈值常数。 显然AODE需估计P(c, xi)和P(xj | c,xi)。类似式(7.20)，有
其中 Ni 是第 i 个属性可能的取值数，Dc,xi 是类别为 c 且在第 i 个属性上取值为 xi 的样本集合，Dc,xi,xj 是类别为 c 且在第 i 和第 j 个属性上取值分别为 xi 和 xj 的样本集合。
与朴素贝叶斯分类器类似，AODE的训练过程也是“计数”，即在训练数据集上对符合条件的样本进行计数的过程。
与朴素贝叶斯分类器相似，AODE无需模型选择，既能通过预计算节省预测时间，也能采取懒惰学习方式在预测时再进行计数，并且易于实现增量学习.
既然将属性条件独立性假设放松为独依赖假设可能获得泛化性能的提升，那么，能否通过考虑属性间的高阶依赖来进一步提升泛化性能呢？ 也就是说，将式(7.23)中的属性 Pai 替换为包含 k 个属性的集合 Pai ，从而将 ODE 拓展为 kDE 。需注意的是，随着k的增加，准确估计概率P(xi | y, Pai ) 所需的训练样本数量将以指数级增加。因此，若训练数据非常充分，泛化性能有可能提升;但在有限样本条件下，则又陷入估计高阶联合概率的泥沼.
5. 贝叶斯网
5.1 贝叶斯网络定义
贝叶斯网络(Bayesian network)，又称信念网络(Belief Network)，或有向无环图模型(directed acyclic graphical model)，是一种概率图模型，于1985年由Judea Pearl首先提出。它是一种模拟人类推理过程中因果关系的不确定性处理模型，其网络拓朴结构是一个有向无环图(DAG)。
贝叶斯网络的有向无环图中的节点表示随机变量，它们可以是可观察到的变量，或隐变量、未知参数等。认为有因果关系（或非条件独立）的变量或命题则用箭头来连接。若两个节点间以一个单箭头连接在一起，表示其中一个节点是“因(parents)”，另一个是“果(children)”，两节点就会产生一个条件概率值。
总而言之，连接两个节点的箭头代表此两个随机变量是具有因果关系，或非条件独立。
例如，假设节点E直接影响到节点H，即E→H，则用从E指向H的箭头建立结点E到结点H的有向弧(E,H)，权值(即连接强度)用条件概率P(H|E)来表示，如下图所示：
简言之，把某个研究系统中涉及的随机变量，根据是否条件独立绘制在一个有向图中，就形成了贝叶斯网络。其主要用来描述随机变量之间的条件依赖，用圈表示随机变量(random variables)，用箭头表示条件依赖(conditional dependencies)。
令G = (I,E)表示一个有向无环图(DAG)，其中I代表图形中所有的节点的集合，而E代表有向连接线段的集合，且令X = (Xi)i ∈ I为其有向无环图中的某一节点i所代表的随机变量，若节点X的联合概率可以表示成：
则称X为相对于一有向无环图G 的贝叶斯网络，其中，pa(i)表示节点i之“因”，或称pa(i)是i的parents（父母）。
此外，对于任意的随机变量，其联合概率可由各自的局部条件概率分布相乘而得出：
如下图所示，便是一个简单的贝叶斯网络：
因为a导致b，a和b导致c，所以有
5.2 贝叶斯网络的3种结构形式
给定如下图所示的一个贝叶斯网络：
从图上可以比较直观的看出：
-
1. x1,x2,…x7的联合分布为
-
2. x1和x2独立（对应head-to-head）；
-
3. x6和x7在x4给定的条件下独立（对应tail-to-tail）。
根据上图，第1点可能很容易理解，但第2、3点中所述的条件独立是啥意思呢？其实第2、3点是贝叶斯网络中3种结构形式中的其中二种。为了说清楚这个问题，需要引入D-Separation（D-分离）这个概念：D-Separation是一种用来判断变量是否条件独立的图形化方法。换言之，对于一个DAG(有向无环图)E，D-Separation方法可以快速的判断出两个节点之间是否是条件独立的。
5.2.1 贝叶斯网络形式1：head-to-head
所以有：P(a,b,c) = P(a)*P(b)*P(c|a,b)成立，化简后可得：
即在c未知的条件下，a、b被阻断(blocked)，是独立的，称之为head-to-head条件独立，对应本节中最开始那张图中的“x1、x2独立”。
5.2.2 贝叶斯网络形式2：tail-to-tail
考虑c未知，跟c已知这两种情况：
1、在c未知的时候，有：P(a,b,c)=P(c)*P(a|c)*P(b|c)，此时，没法得出P(a,b) = P(a)P(b)，即c未知时，a、b不独立。
2、在c已知的时候，有：P(a,b|c)=P(a,b,c)/P(c)，然后将P(a,b,c)=P(c)*P(a|c)*P(b|c)带入式子中，得到：P(a,b|c)=P(a,b,c)/P(c) = P(c)*P(a|c)*P(b|c) / P(c) = P(a|c)*P(b|c)，即c已知时，a、b独立。
所以，在c给定的条件下，a，b被阻断(blocked)，是独立的，称之为tail-to-tail条件独立，对应本节中最开始那张图中的“x6和x7在x4给定的条件下独立”。
2.2.3 贝叶斯网络形式3：head-to-tail
还是分c未知跟c已知这两种情况：
1、c未知时，有：P(a,b,c)=P(a)*P(c|a)*P(b|c)，但无法推出P(a,b) = P(a)P(b)，即c未知时，a、b不独立。
2、c已知时，有：P(a,b|c)=P(a,b,c)/P(c)，且根据P(a,c) = P(a)*P(c|a) = P(c)*P(a|c)，可化简得到：
所以，在c给定的条件下，a，b被阻断(blocked)，是独立的，称之为head-to-tail条件独立。
插一句：这个head-to-tail其实就是一个链式网络，如下图所示：
根据之前对head-to-tail的讲解，我们已经知道，在xi给定的条件下，xi+1的分布和x1,x2…xi-1条件独立。意味着啥呢？意味着：xi+1的分布状态只和xi有关，和其他变量条件独立。通俗点说，当前状态只跟上一状态有关，跟上上或上上之前的状态无关。这种顺次演变的随机过程，就叫做马尔科夫链（Markov chain）。且有：
接着，将上述结点推广到结点集，则是：对于任意的结点集A，B，C，考察所有通过A中任意结点到B中任意结点的路径，若要求A，B条件独立，则需要所有的路径都被阻断(blocked)，即满足下列两个前提之一：
A和B的“head-to-tail型”和“tail-to-tail型”路径都通过C；
A和B的“head-to-head型”路径不通过C以及C的子孙；
最后，举例说明上述D-Separation的3种情况（即贝叶斯网络的3种结构形式），则是如下图所示：
上图中左边部分是head-to-tail，给定 T 时，A 和 X 独立；右边部分的右上角是tail-to-tail，给定S时，L和B独立；右边部分的右下角是head-to-head，未给定D时，L和B独立。
附一：贝叶斯定理特别版：
附二：算法概览——拼写检查
-
import re, collections
-
-
def words(text):
return re.findall(
'[a-z]+', text.lower())
-
-
def train(features):
-
model = collections.defaultdict(
lambda:
1)
-
for f
in features:
-
model[f] +=
1
-
return model
-
-
NWORDS = train(words(open(
'big.txt').read()))
-
-
alphabet =
'abcdefghijklmnopqrstuvwxyz'
-
-
def edits1(word):
-
n = len(word)
-
return set([word[
0:i]+word[i+
1:]
for i
in range(n)] +
# deletion
-
[word[
0:i]+word[i+
1]+word[i]+word[i+
2:]
for i
in range(n
-1)] +
# transposition
-
[word[
0:i]+c+word[i+
1:]
for i
in range(n)
for c
in alphabet] +
# alteration
-
[word[
0:i]+c+word[i:]
for i
in range(n+
1)
for c
in alphabet])
# insertion
-
-
def known_edits2(word):
-
return set(e2
for e1
in edits1(word)
for e2
in edits1(e1)
if e2
in NWORDS)
-
-
def known(words):
return set(w
for w
in words
if w
in NWORDS)
-
-
def correct(word):
-
candidates = known([word])
or known(edits1(word))
or known_edits2(word)
or [word]
-
return max(candidates, key=
lambda w: NWORDS[w])
求解：argmaxc P(c|w) -> argmaxc P(w|c) P(c) / P(w)¶
- P(c), 文章中出现一个正确拼写词 c 的概率, 也就是说, 在英语文章中, c 出现的概率有多大
- P(w|c), 在用户想键入 c 的情况下敲成 w 的概率. 因为这个是代表用户会以多大的概率把 c 敲错成 w
- argmaxc, 用来枚举所有可能的 c 并且选取概率最大的
# 把语料中的单词全部抽取出来, 转成小写, 并且去除单词中间的特殊符号
def words(text): return re.findall('[a-z]+', text.lower())
def train(features):
model = collections.defaultdict(lambda: 1)
for f in features:
model[f] += 1
return model
NWORDS = train(words(open('big.txt').read()))
要是遇到我们从来没有过见过的新词怎么办. 假如说一个词拼写完全正确, 但是语料库中没有包含这个词, 从而这个词也永远不会出现在训练集中. 于是, 我们就要返回出现这个词的概率是0. 这个情况不太妙, 因为概率为0这个代表了这个事件绝对不可能发生, 而在我们的概率模型中, 我们期望用一个很小的概率来代表这种情况. lambda: 1
编辑距离:¶
两个词之间的编辑距离定义为使用了几次插入(在词中插入一个单字母), 删除(删除一个单字母), 交换(交换相邻两个字母), 替换(把一个字母换成另一个)的操作从一个词变到另一个词.
#返回所有与单词 w 编辑距离为 1 的集合
def edits1(word):
n = len(word)
return set([word[0:i]+word[i+1:] for i in range(n)] + # deletion
[word[0:i]+word[i+1]+word[i]+word[i+2:] for i in range(n-1)] + # transposition
[word[0:i]+c+word[i+1:] for i in range(n) for c in alphabet] + # alteration
[word[0:i]+c+word[i:] for i in range(n+1) for c in alphabet]) # insertion
与 something 编辑距离为2的单词居然达到了 114,324 个。优化：在这些编辑距离小于2的词中间, 只把那些正确的词作为候选词,只能返回 3 个单词: ‘smoothing’, ‘something’ 和 ‘soothing’
#返回所有与单词 w 编辑距离为 2 的集合
#在这些编辑距离小于2的词中间, 只把那些正确的词作为候选词
def edits2(word):
return set(e2 for e1 in edits1(word) for e2 in edits1(e1))
正常来说把一个元音拼成另一个的概率要大于辅音 (因为人常常把 hello 打成 hallo 这样); 把单词的第一个字母拼错的概率会相对小, 等等.但是为了简单起见, 选择了一个简单的方法: 编辑距离为1的正确单词比编辑距离为2的优先级高, 而编辑距离为0的正确单词优先级比编辑距离为1的高.
def known(words): return set(w for w in words if w in NWORDS)
#如果known(set)非空, candidate 就会选取这个集合, 而不继续计算后面的
def correct(word):
candidates = known([word]) or known(edits1(word)) or known_edits2(word) or [word]
return max(candidates, key=lambda w: NWORDS[w])
参考文献：
- 机器学习——周志华
- http://dy.163.com/v2/article/detail/CU0MJOCV05118CTM.html
- https://blog.csdn.net/t7sfokzord1jaymsfk4/article/details/81350489
- 《Python数据分析与机器学习实战》课程
投递旷视等公司10个岗位 >
拼多多集团-PDD成长空间 486人发布
