贝叶斯决策论是概率框架下实施决策的基本方法,对于分类任务,在所有相关概率都已知的理想情形下,该方法考虑如何基于这些概率和误判损失来选择最优的类别标记。 假设有 N 中可能的类别标记,即
y
=
(
c
1
,
c
2
,
.
.
.
,
c
N
)
,
λ
i
j
y=(c_1,c_2,...,c_N),\lambda_{ij}
y=(c1,c2,...,cN),λij是将一个真实标记为
c
j
c_{j}
cj的样本误分类为
c
i
c_i
ci所产生的损失。基于后验概率
P
(
c
i
∣
x
)
P(c_i|x)
P(ci∣x)可获得将样本
x
x
x分类为
c
i
c_i
ci所产生的期望损失,即在样本
x
x
x上的“条件风险”
R
(
c
i
∣
x
)
=
∑
j
=
1
N
λ
i
j
P
(
c
j
∣
x
)
R(c_i|x)=\sum^{N}_{j=1}\lambda_{ij}P(c_j|x)
R(ci∣x)=j=1∑NλijP(cj∣x) 在一次分类过程中我们希望分类结果尽可能接近真实值,即要求总体的期望损失最小,这就产生了贝叶斯判别准则:为最小化总体风险,只需在每个样本上选择那个能使条件风险
R
(
c
∣
x
)
R(c|x)
R(c∣x)最小的类别标记,即
h
∗
(
x
)
=
a
r
g
c
∈
y
m
i
n
R
(
c
∣
x
)
h^*(x)=arg_{c\in y}minR(c|x)
h∗(x)=argc∈yminR(c∣x) 此时,
h
∗
h^*
h∗称为贝叶斯最优分类器,与之对应的总体风险
R
(
h
∗
)
R(h^*)
R(h∗)称为贝叶斯风险。
1
−
R
(
h
∗
)
1-R(h^*)
1−R(h∗)反映了分类器所能达到的最好性能,即通过机器学习所能产生的模型精度的理论上限。其中,贝叶斯风险
R
(
h
)
R(h)
R(h)为
R
(
h
∗
)
=
E
x
[
R
(
h
∗
(
x
)
∣
x
)
]
R(h^*)=E_x[R(h^*(x)|x)]
R(h∗)=Ex[R(h∗(x)∣x)]若目标是最小化分类错误率,则误判损失
λ
i
j
\lambda_{ij}
λij可写为
λ
i
j
=
{
0
,
i
=
j
;
1
,
o
t
h
e
r
w
i
s
e
\lambda_{ij} = \{ \begin{array}{rcl} 0, & i=j;\\ 1, &otherwise\end{array}
λij={0,1,i=j;otherwise此时的条件风险
R
(
c
∣
x
)
=
∑
j
=
1
N
λ
i
j
P
(
c
j
∣
x
)
=
∑
j
≠
i
N
λ
i
j
P
(
c
j
∣
x
)
+
0
=
1
−
P
(
c
∣
x
)
R(c|x)=\sum^N_{j=1}\lambda_{ij}P(c_j|x)\\ =\sum^N_{j\neq i}\lambda_{ij}P(c_j|x)+0=1-P(c|x)
R(c∣x)=j=1∑NλijP(cj∣x)=j=i∑NλijP(cj∣x)+0=1−P(c∣x)于是,最小化分类错误率的贝叶斯最优分类器为
h
∗
(
x
)
=
a
r
g
c
∈
y
m
a
x
P
(
c
∣
x
)
h^*(x)=arg_{c\in y}maxP(c|x)
h∗(x)=argc∈ymaxP(c∣x) 对于分类器的构建关键在于对当前样本后验概率的确定。即对每个样本
x
x
x,选择能使后验概率
P
(
c
∣
x
)
P(c|x)
P(c∣x)最大的类别标记。对生成式模型来说,必然考虑联合概率分布
P
(
x
,
c
)
P(x,c)
P(x,c):
P
(
c
∣
x
)
=
P
(
x
,
c
)
P
(
x
)
P(c|x)=\frac{P(x,c)}{P(x)}
P(c∣x)=P(x)P(x,c) 基于贝叶斯定理,
P
(
c
∣
x
)
P(c|x)
P(c∣x)可写为
P
(
c
∣
x
)
=
P
(
c
)
P
(
x
∣
c
)
P
(
x
)
P(c|x)=\frac{P(c)P(x|c)}{P(x)}
P(c∣x)=P(x)P(c)P(x∣c) 对给定的样本
x
x
x,证据因子
P
(
x
)
P(x)
P(x)与类标记无关,因此估计
P
(
c
∣
x
)
P(c|x)
P(c∣x)的问题就转化为如何基于训练数据
D
D
D来估计先验
P
(
c
)
P(c)
P(c)和类条件(似然)
P
(
x
∣
c
)
P(x|c)
P(x∣c) 类先验概率
P
(
c
)
P(c)
P(c)代表了样本空间中各类样本所占的比例,根据大数定律,当训练集包含充足的独立同分布样本时,
P
(
c
)
P(c)
P(c)可通过各类样本出现的频率来进行估计。 对于类条件概率
P
(
x
∣
c
)
P(x|c)
P(x∣c)来说,由于它涉及关于
x
x
x所有属性的联合概率,直接根据样本出现的概率来估计将会遇到严重的困难。即
P
(
x
∣
c
)
=
x
,
c
同时发生次数
c
发生次数
=
x
1
,
x
2
,
.
.
.
,
x
d
,
c
同时发生的次数
c
发生的次数
P(x|c)=\frac{x,c同时发生次数}{c发生次数}=\frac{x_1,x_2,...,x_d,c同时发生的次数}{c发生的次数}
P(x∣c)=c发生次数x,c同时发生次数=c发生的次数x1,x2,...,xd,c同时发生的次数分子很多情况下在训练集中根本没有出现,直接使用频率来估计
P
(
x
∣
c
)
P(x|c)
P(x∣c)显然不可行,因为“未被观测到”与“出现概率为零”通常不同。
二、极大似然估计
估计类条件概率的一种常用策略是先假定其具有某种确定的概率分布形式,再基于训练样本对概率分布的参数估计。具体地,记关于类别
c
c
c的类条件概率为
P
(
x
∣
c
)
P(x|c)
P(x∣c),假设
P
(
x
∣
c
)
P(x|c)
P(x∣c)具有确定的形式并且被参数向量
θ
c
\theta_c
θc唯一确定,则我们的任务就是利用训练集
D
D
D估计参数
θ
c
\theta_c
θc.为明确起见,将
P
(
x
∣
c
)
P(x|c)
P(x∣c)记为
P
(
x
∣
θ
c
)
P(x|\theta_c)
P(x∣θc). 令
D
c
D_c
Dc表示训练集
D
D
D中第
c
c
c样本组成的集合,假设这些样本是独立同分布的,则参数
θ
c
\theta_c
θc对于数据集
D
c
D_c
Dc的似然是
P
(
D
c
∣
θ
c
)
=
∏
x
∈
D
c
P
(
x
∣
θ
c
)
P(D_c|\theta_c) = \prod_{x\in D_c}P(x|\theta_c)
P(Dc∣θc)=x∈Dc∏P(x∣θc) 对
θ
c
\theta_c
θc进行极大似然估计,就是去寻找能最大化似然
P
(
D
c
∣
θ
c
)
P(D_c|\theta_c)
P(Dc∣θc)的参数值
θ
^
c
.
\widehat\theta_c.
θc.直观上看,极大似然估计是试图在
θ
c
\theta_c
θc所有可能的取值中,找到一个能使数据出现的“可能性”最大的值。
三、朴素贝叶斯
基于贝叶斯公式来估计后验概率
P
(
c
∣
x
)
P(c|x)
P(c∣x)的主要困难在于:类条件概率
P
(
x
∣
c
)
P(x|c)
P(x∣c)是所有属性上的联合概率,难以从有限的训练样本直接估计而得。为避开这个障碍,朴素贝叶斯分类器采用了“属性条件独立性假设”:对已知类别,假设所有属性相互独立。换言之,假设每个属性独立地对分类结果产生影响。 基于属性条件独立性假设,后验概率
P
(
c
∣
x
)
P(c|x)
P(c∣x)可重写为:
P
(
c
∣
x
)
=
P
(
c
)
P
(
x
∣
c
)
P
(
x
)
=
P
(
c
)
P
(
x
)
∏
i
=
1
d
P
(
x
i
∣
c
)
P(c|x)=\frac{P(c)P(x|c)}{P(x)}=\frac{P(c)}{P(x)}\prod^d_{i=1}P(x_i|c)
P(c∣x)=P(x)P(c)P(x∣c)=P(x)P(c)i=1∏dP(xi∣c)其中
d
d
d为属性数目,
x
i
x_i
xi为
x
x
x在第
i
i
i个属性上的取值。 由于对所有类别来说
P
(
x
)
P(x)
P(x)相同,因此基于贝叶斯判定准则有
h
n
b
(
x
)
=
a
r
g
c
∈
y
m
a
x
P
(
c
)
∏
i
=
1
d
P
(
x
i
∣
c
)
h_{nb}(x)=arg_{c\in y}maxP(c)\prod_{i=1}^dP(x_i|c)
hnb(x)=argc∈ymaxP(c)i=1∏dP(xi∣c)这就是朴素贝叶斯分类器的表达式。 显然,朴素贝叶斯分类器的训练过程就是基于训练集
D
D
D来估计类先验概率
P
(
c
)
P(c)
P(c),并为每个属性来估计条件概率
P
(
x
i
∣
c
)
P(x_i|c)
P(xi∣c). 令
D
c
D_c
Dc表示训练集
D
D
D中第
c
c
c类样本组成的集合,若有充足的独立同分布样本,则可容易地估计出类先验概率
P
(
c
)
=
D
c
D
P(c)=\frac{D_c}{D}
P(c)=DDc对离散属性而言,令
D
c
,
x
i
D_{c,x_i}
Dc,xi表示
D
c
D_c
Dc中在第
i
i
i各属性上取值为
x
i
x_i
xi的样本组成的集合,则条件概率
P
(
x
i
∣
c
)
P(x_i|c)
P(xi∣c)可估计为
P
(
x
i
∣
c
)
=
∣
D
c
,
x
i
∣
D
c
P(x_i|c)=\frac{|D_{c,x_i}|}{D_c}
P(xi∣c)=Dc∣Dc,xi∣对连续属性可考虑概率密度函数,假定
p
(
x
i
∣
c
)
∼
N
(
μ
c
,
i
,
σ
c
,
i
2
)
p(x_i|c) \sim N(\mu_{c,i},\sigma^2_{c,i})
p(xi∣c)∼N(μc,i,σc,i2),其中
μ
c
,
i
\mu_{c,i}
μc,i和
σ
c
,
i
2
\sigma^2_{c,i}
σc,i2分别是第
c
c
c类样本在第
i
i
i各属性上取值的均值和方差,则有
P
(
x
i
∣
c
)
=
1
2
π
σ
c
,
i
exp
(
−
(
x
i
−
μ
c
,
i
)
2
2
σ
c
,
i
2
)
P(x_i|c) = \frac{1}{\sqrt{2\pi}\sigma_{c,i}}\exp(-\frac{(x_i-\mu_{c,i})^2}{2\sigma^2_{c,i}})
P(xi∣c)=2πσc,i1exp(−2σc,i2(xi−μc,i)2)
四、拉普拉斯修正
在计算条件概率
∏
i
=
1
d
P
(
x
i
∣
c
)
\prod_{i=1}^dP(x_i|c)
∏i=1dP(xi∣c)时,会出现样本的属性值在训练集中未出现,导致条件概率相乘时最终值为0,为避免其他属性携带的信息被训练集中出现的属性值“抹去”,在估计概率值时通常要进行“平滑”,常用“拉普拉斯修正”,即令
N
N
N表示训练集
D
D
D中可能的类别数,
N
i
N_i
Ni表示第
i
i
i个属性可能的取值数,则其修正为:
P
^
(
c
)
=
∣
D
c
∣
+
1
∣
D
∣
+
N
,
P
^
(
x
i
∣
c
)
=
∣
D
c
,
x
i
∣
+
1
∣
D
c
∣
+
N
i
.
\widehat P(c)=\frac{|D_c|+1}{|D|+N},\\ \\ \widehat P(x_i|c)=\frac{|D_{c,x_i}|+1}{|D_c|+N_i}.
P(c)=∣D∣+N∣Dc∣+1,P(xi∣c)=∣Dc∣+Ni∣Dc,xi∣+1.