贝叶斯分类器
贝叶斯决策
贝叶斯决策理论是在概率的框架下进行决策的基本方法。假设有
N
种可能的类内标记,即
Y={c1,c2,c3,...,cn}
,而
λij
表示将
cj
类误分为
ci
的损失代价。基于后验概率
P(ci∣x)
可能将样本
x
分类为
ci
所产生的期望损失,也就是在样本
x
上的条件风险:
R(ci∣x)=∑j=1NλijP(cj∣x)(1)
如果定义损失函数为:
L(y,y^)=L(y,h(x))={0,y=h(x)1,y≠h(x)
此处的损失函数和
λij
的一种具体形式。那么式(1)可以写成:
R(ci∣x)=∑j=1NL(ci,cj)P(cj∣x)
那么问题就可以转化为寻找一个判定准则:
h:X→Y
使得最小化总体风险:
R(h)=Ex[R(h(x)∣x)]=Ex[∑j=1NL(h(x),cj)P(cj∣x)](2)
显然,对每个样本
x
若
h
能最小化条件风险,则总体风险
R(h)
也将被最小化。
y^=f(x)=argminc∈Y∑j=1NL(c,cj)P(cj∣x)=argminc∈Y∑j=1NP(c≠cj∣x)=argminc∈Y1−P(c=cj∣x)=argmaxc∈YP(c=cj∣x)=argmaxc∈YP(c∣x)
这就解释了最大化后验概率等价于最小化总体风险,也是朴素贝叶斯采用的基本原理!!!
这就是贝叶斯判定准则:为最小化总体风险,只需要在每个样本上选择那个能使条件风险最小的类别标记,即
h∗(x)=argminc∈Y R(c∣x)=argmaxc∈YP(c∣x)(3)
此时,称
h∗
为贝叶斯最优分类器,与之对应的总体风险
R(h∗)
为贝叶斯风险,
1−R(h∗)
反映了分类器能达到的最好的性能。
那么根据公式(1)就不难知道,如果需要最小化风险,就必须知道后验概率
P(c∣x)
. 从这个角度来看,所有的机器学习算法就是基于训练样本来估计后验概率。主要的策略有:
1. 给定
x
,通过直接建模
P(c∣x)
,然后预测
c
,这种得到的模型称之为“判别式模型“。
2. 先对联合概率分布
P(c,x)
进行建模,然后由此获得
P(c∣x)
,这种模型称之为 “生成模型“。
对于生成模型来说,有:
P(c∣x)=P(x,c)P(x)(4)
又结合贝叶斯定理:
P(c∣x)=P(x∣c)P(c)P(x)(5)
<1> 类先验概率
P(c)
为样本空间中各类样本所占的比例,依据大数定理,可以使用各类样本出现的频率来估计。
<2>估计类条件概率
P(x∣c)
一种方法是假设其符合某种分布,然后再利用样本对该分布的参数
θc
进行估计,常用的估计方法就是
极大似然估计。
朴素贝叶斯分类器
由公式(4),(5)可知,贝叶斯决策的难点在于:类条件概率
P(x∣c)
是所有属性上的联合概率分布。朴素贝叶斯分类器假设所有的属性是条件独立的(注意不同于独立),那么公式(5)就可以转化为:
P(c∣x)=P(c)P(x1,x2,⋯,xd|c)P(x)=P(c)P(x)∏i=1dP(xi∣c)←(根据各维度的独立性可得)(6)=P(c)∏di=1P(xi∣c)∑nj=1P(x∣cj)P(cj)←(对分母使用全概率公式可得)=P(c)∏di=1P(xi∣c)∑nj=1P(cj)∏di=1P(xi∣c)←(对分母中的对应分量的条件独立性可得)
在公式(6)中可知
P(x)
与
x
所属的类别没有关系,也就是不论它属于哪个类别,在计算不同类别的后验概率的时候其值都是相等的。那么贝叶斯分类器的问题可以描述为:
y^(i)=argmaxcjP(cj∣x)=argmaxcjP(cj)∏i=1dP(xi∣cj)
这就是我们所需要求解的贝叶斯分类器,我们通过训练数据学习获得参数
P(cj)
和
P(xi∣cj)
。参数的估计方法可以使用极大似然估计。
参数的极大似然估计
假设
Dc
表示属于类别
c
的样本个数,
D
表示所有训练样本的个数:
P(cj)=|Dcj||D|=∑mi=1I{y(i)=cj}m(7)
对于离散属性,假设属性
xi的取值可以为{xi1,xi2,⋯,xil}
:
P(xil∣cj)=|Dcj,xil||Dcj|=∑mk=1I{xi=xil,y(k)=cj}∑mk=1I{y(k)=cj}(8)
对于连续属性:
P(xi∣c)=f(xi)(9)
参数的贝叶斯估计
为了避免某些属性被未出现的属性值抹去,即可能出现某些属性取值的概率为0的情况。通常使用拉普拉斯修正来进行平滑计算,这样可以避免因训练样本的不充分而导致概率估值为零的情况发生。
P(c)=|Dc|+1|D|+N,N表示类别的数目(10)
P^(xi∣c)=|Dc,xi|+1|Dc|+Li,Li表示第i维属性能所能取值的个数(11)
半朴素贝叶斯分类器
半朴素贝叶斯分类器的基本想法是适当考虑一部分属性的依赖关系而不是认为其全部是独立的,这样虽然不需要计算所有属性的联合概率分布,但也一定程度上反映了部分属性的关联性。
贝叶斯网
贝叶斯网也称为信念网,借助有向无环图(DAG)来刻画属性之间的依赖关系,并使用条件概率表(CPT)来描述属性的联合概率分布。
EM算法
在样本中,往往会发生属性值缺失的事情,也就是并不是所有样本的属性值都是完整的。那么对于这样的情况如何去估模型的参数呢?
我们将这种缺失信息的变量成为”隐变量“,令
X
表示属性值完整的变量,
Z
表示隐变量,
Θ
表示模型参数,那么对
Θ
做参数估计,采用极大似然估计可得:
l(Θ∣X,Z)=lnP(X,Z∣Θ)](12)
Z
为隐变量,上式无法直接求解,但可以通过对
Z
计算期望,来最大化已经观测数据的对数”边际似然“
l(Θ∣X)=lnP(X∣Θ)]=ln∑zP(X,Z∣Θ)(13)
EM算法的基本思想是:若参数
Θ
已知,则可以根据训练数据推断出最优隐变量
Z
的值(E步);反之,若是
Z
的值已知,那么则可以对参数
Θ
做极大似然估计(M步);如此迭代的进行,最终算法收敛。
杰森不等式
假设
f
是一个凸函数,
X
是随机变量,那么:
E[f(X)]≥f[E[X]]
,当
f
是一个严格凸函数且
X=E[X]
时等号成立。
References:
[1]周志华:机器学习
[2]EM算法原理详解
[3]李航:统计学习方法