朴素贝叶斯与拉普拉斯平滑简介
今天我们从极大似然估计说起，然后阐述一下朴素贝叶斯分类算法和贝叶斯估计，最后介绍M估计和拉普拉斯平滑方法，其主要解决了零概率问题。
1 极大似然法
极大似然法是一种根据样本估计模型参数的方法，通过观测样本构造似然函数，然后令似然函数的极值为0进而确定模型参数。
假设我们有一枚硬币，抛出后正面朝上的概率为p(0<p<1)。现在我们抛出了49个正面(H)，31个反面(T)。我们来求其似然函数的最大值：
$$f(\theta)=f_D(H=49,T=80-49|p)=\left(\frac{80}{49}\right)p^{49}(1-p)^{31} \tag{1.1}$$
我们对方程两边同时取微分，并使其为零。
$$
\begin{aligned}
0 &= \frac{d}{dp}\left(\left(\frac{80}{49}\right)p^{49}(1-p)^{31}\right) \\
&= 49p^{48}(1-p)^{31}-31p^{49}(1-p)^{30} \\
&= p^{48}(1-p)^{30}[49(1-p)-31p] \\
\end{aligned} \tag{1.2}
$$
其解为p=0,p=1，以及p=49/80。使可能性最大的解显然是p=49/80，p=0和p=1这两个解会使可能性为零）。因此我们说最大似然估计值为49/80。
这个结果很容易一般化。只需要用一个字母t代替49用以表达伯努利试验中的被观察数据（即样本）的“成功”次数，用另一个字母n代表伯努利试验的次数即可。使用完全同样的方法即可以得到最大似然估计值:
$$
\hat{p}=\frac{t}{n} \tag{1.3}
$$
对于任何成功次数为t，试验总数为n的伯努利试验。
以上就是用极大似然法求解离散分布，连续参数空间的情况。
2 朴素贝叶斯
朴素贝叶斯是基于贝叶斯定理与特征条件独立假设的分类方法。对于给定的训练数据集，首先基于特征条件独立假设 学习输入/输出的联合概率分布；然后基于此模型，对于给定的输入x，利用贝叶斯定理求出后验概率最大的输出y。
先验概率
在贝叶斯统计中，某一不确定量p的先验概率分布是在考虑”观测数据”前，能表达p不确定性的概率分布。
后验概率 （知道“果”，推测“因”的概率）
在贝叶斯统计中，一个随机事件的后验概率是在考虑相关证据 ( 观测数据 ) 后所得到的条件概率。换句话说，后验概率分布是一个随机变量基于试验得到的概率分布。
2.1 联合概率分布
在概率论中, 对两个随机变量X和Y，其联合分布是同时对于X和Y的概率分布。
对离散随机变量而言，联合分布概率质量函数为$P(X = x , and , Y = y)$，即
$$
P(X=x , and , Y=y)=P(Y=y|X=x)P(X=x)=p(X=x|Y=y)P(Y=y) \tag{2.1}
$$
因为是概率分布函数，所以必须有
$$\sum_{x}{\sum_{y}{f_{X,Y}(x,y)dy dx}}=1 \tag{2.2} $$
2.2 朴素贝叶斯的推导
给定训练集 $T=\{(x_1,y_1),(x_2,y_2),..,(x_N,y_N)\}$，其由 $P(X,Y)$ 独立同分布产生。朴素贝叶斯法通过训练数据集学习联合概率分布$P(X,Y)$。具体地，学习以下先验分布和条件概率分布。先验分布$P(Y=c_k),k=1,2,…,K$,条件概率分布
$$P(X=x|Y=c_k)=P(x^{(1)}=X^{(1)},…,x^{(n)}|Y=c_k),k=1,2,…,K$$
最后学习到联合概率分布$P(X,Y)$。
但是条件概率分布$P(X=x|Y=c_k)$有指数量级的参数。其估计是不可行的。假设$x^i$的取值有$S_j$个，Y的取值有$K$个，那么参数个数为$K\prod_{j=1}^n{S_j}$。
朴素贝叶斯对条件概率分布做了独立性的假设,假设分类的特征在类确定的条件下都是相互独立的。由于这是一个较强的假设，“朴素”因此得名，但是朴素贝叶斯依然有出色的性能。由条件独立性假设可以得到
$$
\begin {aligned}
P(X=x|Y=c_k)&=P(X^{(1)}=x^{(1)}, .. , X^{(n)}=x^{(n)}|Y=c_k) \\
&=\prod_{j=1}^n{P(X^{(j)}=x^{(j)}|Y=c_k)} \\
\end {aligned} \tag{2.3}
$$
朴素贝叶斯实际上学习到了生成数据的机制，所以属于生成模型。
朴素贝叶斯分类时，对给定的输入x，通过后验概率分布$P(Y=c_k|X=x)$，将后验概率最大的类作为x的类输出。后验概率的计算根据贝叶斯定理进行：
$$
P(Y=c_k|X=x)=\frac{P(X=x|Y=c_k)P(Y=c_k)}{\sum_{i}^K{P(X=x|Y=c_i)P(Y=c_i)}} \tag{2.4}
$$
将$(2.3)$代入$(2.4)$有
$$
P(Y=c_k|X=x)= \frac{P(Y=c_k) \prod_{j=1}^n P(X^{(j)}=x^{(j)}|Y=c_k)} { \sum_{i}^K{P(Y=c_i) \prod_{j=1}^n{P(X^{(j)}=x^{(j)}|Y=c_i)}}} ,, k=1,2,..,K \tag{2.5}
$$
这就是朴素贝叶斯分类的基本公式。于是，朴素贝叶斯分类器可表示为
$$
y=f(x)=\mathop{\arg\max}\limits_{c_k}\frac{P(Y=c_k)\prod_{j=1}^n{P(X^{(j)}=x^{(j)}|Y=c_k)}}{\sum_{i}^K{P(Y=c_i)\prod_{j=1}^n{P(X^{(j)}=x^{(j)}|Y=c_i)}}} \tag{2.6}
$$
在$(2.6)$中，分母对所有$C_k$都是相同的，所以可以进一步简化为
$$
y=\mathop{\arg\max}\limits_{c_k} \space P(Y=c_k) \prod_{j=1}^n{P(X^{(j)}=x^{(j)}|Y=c_k)} \tag{2.7}
$$
2.3 朴素贝叶斯算法的参数估计
在朴素贝叶斯中，学习意味着估计$P(Y=c_k)$和$P(X^{(j)}=x^{(j)}|Y=c_k)$，可以使用极大似然法估计相应的概率(思想即伯努利试验的极大似然估计的泛化，详见第一部分)，先验概率$P(y=c_k)$ 的极大似然估计是
$$P(Y=c_k)=\frac{\sum_{i=1}^N{I(y_i=c_k)}} {N}, k=1,2,…,K \tag{2.8}$$
对于条件概率，设第j个特征$x^{(j)}$可能取值的集合为${a_{j1}, a_{j2},.., a_{jS_j}}$，则条件概率 $P(X^{(j)}=a_{(jl)}|Y=c_k)$ 的极大似然估计是
$$P(X^{(j)}=a_{jl}|Y=c_k)=\frac{\sum_{i=1}^N{I(x_i^{(j)}=a_{jl},y_i=c_k)}} {\sum_{i=1}^N{I(y_i=c_k)}} \tag{2.9} $$
$$j=1,2,…,n; , l=1,2,…, S_i; , k=1,2,.., K $$
$(2.9)$中，$x_i^{(j)}$是第i个样本的第j个特征，$a_{jl}$是第j个特征可能取的第$l$个值，$I$为指示函数。
2.4 朴素贝叶斯算法的形式化描述
输入：训练数据,训练数据$T=\{(x_1,y_1),(x_2,y_2),..,(x_N,y_N)\}$，其中$x_i=(x_i^{(1)}, x_i^{(2)}, …, x_i^{(n)} ) ^T$，$x_i^{(j)}$是第i个样本的第j个特征，$x_i^{(j)} \in \{ a_{j1}, a_{j2}, … , a_{jSj}\}$, $a_{jl}$是第$j$个特征可能取得第$l$个值，$j=1,2,..,n,, l=1,2,…,S_j, y_i \in \{c_1,c_2,..,c_K\}$；实例$x$。
输出： 实例$x$的分类。
(1) 计算先验概率及条件概率
先验概率
$$
P(Y=c_k)=\frac{\sum_{i=1}^N{I(y_i=c_k)}}{N}, k=1,2,…,K \tag{2.10}
$$
条件概率
$$
P(X^{(j)}=a_{jl}|Y=c_k)=\frac{\sum_{i=1}^N{I(x_i^{(j)}=a_{jl},y_i=c_k)}}{\sum_{i=1}^N{I(y_i=c_k)}} \tag{2.11}
$$
$$j=1,2,…,n; l=1,2,..,S; k=1,2,…,K$$
(2) 对于给定的实例$x=(x^{(1)},x^{(2)},,…,x^{(n)})$，计算后验概率(该步骤通过贝叶斯公式得到)
$$P(Y=c_k|X=x)=P(Y=c_k)\prod_{j=1}^n{P(X^{(j)}=x^{(j)}|Y=c_k)}, k=1,2,…,K \tag{2.11} $$
(3) 确定实例x的类
$$
y=\mathop{\arg\max}\limits_{c_k} \space P(Y=c_k) \prod_{j=1}^n{P(X^{(j)}=x^{(j)}|Y=c_k)} \tag{2.12}
$$
用极大似然估计可能会出现所要估计的概率值为0的情况，这会影响到后验概率的计算结果，使分类产生误差。解决这一问题的方法是采用贝叶斯估计。具体地，条件概率的贝叶斯估计是
$$P_{\lambda}{(X^{(j)}=a_{jl}|Y=c_k)}=\frac{\sum_{i=1}^N{I(X_i^{(j)} = a_{jl},y_i=c_k)+\lambda}}{\sum_{i=1}^N{I(y_i=c_k)+S_i \lambda}} \tag{2.13} $$
其中$\lambda\geq 0$。等价于在随机变量各个取值的频数上赋予一个正数$\lambda>0$。当$\lambda=0$时就是极大似然估计。常取$\lambda=1$，这时就是拉普拉斯平滑。显然，对任何$l=1,2,…,S_j,k=1,2,…,K$,有
$$P_{\lambda}(X^{(j)}=a_{jl}|Y=c_k)>0 \tag{2.14} $$
$$\sum_{l=1}^{S_j}{P(X^{(j)}=a_{jl}|Y=c_k)=1} \tag{2.15} $$
这说明式$(2.13)$确是一种概率分布。同样，先验概率的贝叶斯估计是
$$P_{\lambda}(Y=c_k)=\frac{\sum_{i=1}^N{I(y_i=c_k)+\lambda}}{N+k\lambda} \tag{2.16} $$
3 M估计和拉普拉斯平滑
对于多分类问题，一般可以通过观测数据来估计类别$c_k$出现的概率 ( 极大似然法 )，即$P(Y=c_k)=\frac{n_c}{n}$。其中，$n_k$为类别$c_k$的样本数量，$n$为总样本数量。当$n_c$很大的时候，$\frac{n_c}{n}$是对类别$c_k$出现的真实概率$P_{real}(Y=c_k)$的良好估计。但是当$n_c$比较小的时候，$\frac{n_c}{n}$会产生有偏估计。当$n_c = 0$的时候，$\frac{n_c}{n}=0$会对$P_{real}(Y=c_k)$产生一个有偏的过低概率估计。由贝叶斯公式可得$P(Y=c_k|X=x)=0$，则类别$c_k$永远不会被分类到。
为了避免此问题，m估计出现了:
$$P(Y=c_k)=\frac{n_c+mp}{n+m} \tag{3.1}$$
其中$n_c$为该类别$c_k$的样本数量，$n$为总样本数量，$p$为$P(Y=c_k)$的先验估计，m为等效样本大小的常量。
4 关于CTR中拉普拉斯平滑分母值的设定
在CTR(点击率)预估中，拉普拉斯平滑是必要的。
$$ctr=\frac{click}{expos} \tag{4.1}$$
$click$是点击次数，$expos$是曝光量次数。
加了拉普拉斯平滑之后，
$$ctr=\frac{click+\lambda}{expos+k\lambda}, ,, \lambda=1 \tag{4.2}$$
$k$为类别个数，在商品推荐中$k$为item的个数。对于商品a，如果没有曝光 ( $expos=0$ ) 的话，此时点击 ( $expos$ ) 也为0。这样的话就是$ctr_a=\frac{1}{k}$，也就是将点击 item a 的先验概率赋值给$ctr_a$。换句话说，对于总数为k的商品，在没有任何观测数据的情况下，点击其中一个的概率是$p_{prior}=\frac{1}{k}$。这和LDA主题模型也有共通之处。
