条件风险最小化

朴素贝叶斯也是一种分类算法,假设有三个类别A,B,C.给定一个新的样本x,如果我们能够计算出三个类别的条件概率:

P(A|x) = 0.6
P(B|x) = 0.3
P(C|x) = 0.1

那么x应该属于哪个类别呢?答案是x肯定属于A类,因为A类的概率大啊.

在概率论中用条件风险来说明上述结论.

给定训练数据集D,其中每个样本x都包括n维特征,即x=({f_{1},f_{2},f_{3},...,f_{n}}).类标y含有k种类别.

基于后验概率P(y_i|x)可获得将样本x分类为y_i所产生的期望损失,即条件风险:

R(y_i | x) = \sum_{j=1}^n \lambda_{ij}P(y_j|x)

其中,\lambda_{ij}为将一个真实样本为y_j误分类为y_i所产生的损失:

\lambda_{ij} = \begin{cases}0,&\text{i = j}\\ 1,&\text{other}\end{cases}

显然,如果模型是最优的,那么每个样本的条件风险一定是最小的,即:

h^*(x) = arg \; min_{y \in Y} \; R(y | x)

其中,h^*为贝叶斯最优化分类器,与之对应的总体风险R(h^*)称为总体风险.1 - R(h^*)反应了分类器所能达到的最好性能,即通过机器学习所能达到的模型精度的理论上限.

因为条件风险:

R(y | x) = 1 - P(y | x)

所以条件风险最小化相当于:

h^*(x) = arg \; max_{y \in Y} \; P(y | x)

独立参数

对于P(y | x)我们很难直接获得,根据条件概率:
P(y | x) = \dfrac{P(x,y)}{P(x)}

考虑到x有多个特征所以上式写为:

p(y\vert f_{1},\dots ,f_{n})={\dfrac  {p(y, f_{1},\dots ,f_{n})}{p(f_{1},\dots ,f_{n})}}

因为分母不依赖于y而且特征f_{i}的值是给定的,于是分母可以认为是一个常数。所以我们只关心分子:

p(y,f_{1},\dots ,f_{n})

假设所有变量都属于二项分布,我们使用列表的方式把所有的概率都列出来:

概率
p(y = 0,f_{1} = 0,\dots ,f_{n} = 0)
p(y = 1,f_{1} = 0,\dots ,f_{n} = 0)
p(y = 1,f_{1} = 1,\dots ,f_{n} = 0)
p(y = 1,f_{1} = 1,\dots ,f_{n} = 1)

总共需要多少个概率呢?2^{n}+2个概率,这些概率叫做被称作参数.

有没有可能使用更少的参数,来描述这个概率分布?因为总概率是1,所以只要确定2^{n}+1个概率,那么最后一个概率也被确定下来了,所以描述一个分布最少的参数被称为独立参数.

显然,通过遍历概率分布中所有可能的情况是不可取的,因为遍历的个数与特征数乘指数形式.

特征条件独立假设

朴素贝叶斯算法对条件概率分布作出了独立性的假设,也就是说特征之间是独立的,即:

p(f_{1},\dots ,f_{n})=\prod_{i=1}^{n}P(f_{i})

结合条件概率公式,可得转化联合分布模型为:

p(y,f_{1},\dots ,f_{n})=P(y)\prod_{i=1}^{n}P(f_{i}|y)

由上式可知,朴素贝叶斯若使由贝叶斯网画出来是:

这就是朴素贝叶斯的模型,那么它需要多少个独立参数呢?

P(y),P(f|y = 0),P(f|y = 1)都是为二项分布,共2n+1个二项分布,而每个二项分布需要一个独立参数.所以朴素贝叶斯的模型需要2n+1个独立参数.

相比遍历整个概率空间,朴素贝叶斯的模型与特征数呈线性关系,显然计算量小得多.

所以朴素贝叶斯最优化分类器可以写为:

h_{nb}(x) = arg \; max_{y \in Y} \; P(y)\prod_{i=1}^{n}P(f_{i}|y)

上式用到了连乘操作,这有可能造成数值下溢,即计算结果小于浮点数可以表示的最小数字.为了防止数值下溢,对P(f_{i}|y)取对数,将连成转化为连加:

h_{nb}(x) = arg \; max_{y \in Y} \; P(y)\sum_{i=1}^{n}logP(f_{i}|y)

显然,朴素贝叶斯分类器的训练过程就是基于训练集X,来估计P(y)P(f_{i}|y)的过程.

其中P(y)只需计算样本中的比例即可:
P(y) = \frac{|D_y|}{|D|}

不过这样计算有一个小小的问题,如果有一个类别样本中没有,那么根据这个公式算出来概率为0,但是样本中没有并不代表一定不会出现.所以这里增加拉普拉斯平滑:

P(y)=\dfrac{N_{y}+\alpha}{N+k\alpha}

其中\alpha为拉普拉斯平滑值.

如果属性是离散的,P(f_{i}|y)的值也可以通过统计样本中的比例来计算,同样增加拉普拉斯平滑:

P(f_{i}|y)=\dfrac{N_{y,f_{i}}+\alpha}{N_{y}+n\alpha}

如果属性是连续的,我们可以根据高斯分布来估计P(f_{i}|y):

P(f_{i}|y)=\dfrac{1}{\sqrt{2\pi\sigma_{y,i}^{2}}}e^{-\frac{(f_{i}-\mu_{y,i})^{2}}{2  \sigma_{y,i}^{2}}}


编程实现:
https://www.kaggle.com/swimmingwhale/naive-bayes


参考:

posted @ 2018-06-07 22:39:54
评论加载中...

发表评论