目录
[toc]

1. 朴素贝叶斯法简介

朴素贝叶斯法是基于贝叶斯定理的分类方法。
给定训练数据集 $T=\lbrace(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\rbrace$ ，其中 $x_i\in \mathcal{X} \subseteq \R^n$ 为输入特征， $y_i\in \mathcal{Y}=\lbrace c_1,c_2,\cdots,c_K\rbrace$ 为输出类别。令 $X,Y$ 为输入空间 $\mathcal{X}$ 和输出空间 $\mathcal{Y}$ 上的随机变量，朴素贝叶斯法通过训练数据集学习联合概率分布 $P(X,Y)$ 。具体地，通过学习先验概率：
$P(Y=c_k),\quad k=1,2,\cdots,K$
和条件概率：
$P(X=x|Y=c_k)=P(X^{(1)}=x^{(1)},\cdots,X^{(n)}=x^{(n)}|Y=c_k)$
进而得到联合概率分布。
设 $x^{(j)}$ 的可能取值有 $S_j$ 个， $Y$ 的可能取值为 $K$ 个，则待学习的条件概率 $P(X=x|Y=c_k)$ 的个数为 $K\prod_{j=1}^n S_j$ ，规模随着样本维度呈指数级增长，在实际问题中不可行。
朴素贝叶斯法对条件概率分布作了条件独立性假设，这正是朴素这一定语的来源。具体地，条件独立性假设为：
$\begin{split} P(X=x|Y=c_k) &= P(X^{(1)}=x^{(1)},\cdots, X^{(n)}=x^{(n)}|Y=c_k) \\ &= \prod_{j=1}^n P(X^{(j)}=x^{(j)}|Y=c_k) \end{split}$
朴素贝叶斯法分类时，给定输入x，通过学习到联合概率分布和贝叶斯定理，可计算后验概率分布：
$\begin{split} P(Y=c_k|X=x) &= \frac{P(X=x|Y=c_k)P(Y=c_k)}{P(X=x)} \\ &= \frac{P(Y=c_k)\prod_{j=1}^n P(X^{(j)}=x^{(j)}|Y=c_k)}{P(X=x)} \end{split}$
所有后验概率中最大的类即为x的类，由于给定输入样本x后，分母是不变的，因此朴素贝叶斯分类器可表示为：
$y=\argmax_{c_k}{P(Y=c_k)\prod_{j=1}^n P(X^{(j)}=x^{(j)}|Y=c_k)}$
通过以上分析可知，朴素贝叶斯法需要先求得先验概率 $P(Y=c_k)$ 和条件概率 $P(X^{(j)}=x^{(j)}|Y=c_k),j=1,2,\cdots,n$ 。从直觉出发，可以用样本中出现的频率直接代替先验概率和条件概率，实际上这正是极大似然估计的结果，证明过程见后文，先给出结果。

先验概率的估计：
$P(Y=c_k)=\frac{\sum_{i=1}^{N}{I(y_i=c_k)}}{N},\quad k=1,2,\cdots,K$
其中， $I$ 为指示函数。
条件概率的估计：
$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)}$
其中，设第j个特征 $x^{(j)}$ 可能的取值集合为 $\lbrace a_{j1},a_{j2},\cdots,a_{jS_j}\rbrace$ ； $j=1,2,\cdots,n$ ； $l=1,2,\cdots,S_j$ ； $k=1,2,\cdots,K$

2. 参数的极大似然估计

2.1 预备数学知识

2.1.1 带约束条件的优化-拉格朗日乘法项

对于某些求极值问题，函数通常带有一些约束条件。如下面的例子：
$\begin{split} \max &\quad f(x,y)=x+y \\ s.t. &\quad x^2+y^2=1 \end{split}$
拉格朗日乘法项可用来解决这类问题。我们可以把约束条件作为拉格朗日乘法项加到目标函数中，问题可转化为：
$\max \quad L=x+y+\lambda(x^2+y^2-1)$
令导数为0，可得到以下三个方程：
$\left\{ \begin{split} f'_x(x,y,\lambda) &=1+2\lambda x=0 \\ f'_y(x,y,\lambda) &=1+2\lambda y=0 \\ f'_\lambda(x,y,\lambda) &=x^2+y^2-1=0 \end{split} \right.$
解之得：
$\left\{ \begin{split} \lambda &=\frac{\sqrt{2}}{2} \\ x &=\frac{\sqrt{2}}{2} \\ y &=\frac{\sqrt{2}}{2} \end{split} \right. \quad or \quad \left\{ \begin{split} \lambda &=-\frac{\sqrt{2}}{2} \\ x &=-\frac{\sqrt{2}}{2} \\ y &=-\frac{\sqrt{2}}{2} \end{split} \right.$
代入到原方程 $f(x,y)$ 可确定最优解。

2.1.2 极大似然估计

极大似然估计是机器学习领域最为常见的用来构建目标函数的方法。它的核心思想是根据观测到的结果来预测未知参数。举一个投掷硬币的例子。
假设有一枚硬币，它是不均匀的，即出现正面和反面的概率是不同的。假设我们设定这枚硬币出现正面的概率为 $P(正)=\theta$ , 出现反面的概率则为 $P(反)=1-\theta$ 。假设我们投掷6次之后得到以下结果，且假定每次投掷是相互独立的事件：
$D=\lbrace 正反反正正正 \rbrace$
其中D表示所观测到的所有样本。直观上通过该样本集可以估计 $\theta=4/6$ ，其实我们在无意识中已经使用了极大似然估计法。所谓极大似然估计，即最大化观测到样本的概率，也即 $\max P(D)$ ，进一步可写成：
$\max L=P(D)=\theta*(1-\theta)*(1-\theta)*\theta*\theta*\theta$
其中， $L(\theta)$ 称为似然函数。令似然函数的导数为0求极值：
$L'(\theta)=4\theta^3(1-\theta)^2-2\theta^4(1-\theta)=0$
可解得 $\theta=2/3$ ，与前面的直观估计一致。

2.2 朴素贝叶斯法参数的极大似然估计

在本文第一节对朴素贝叶斯法的简介中，我们知道朴素贝叶斯法需要估计的参数为：先验概率 $P(Y=c_k)$ 和条件概率 $P(X^{(j)}=a_{jl}|Y=c_k)$ ，为了方便叙述，不妨将所有这些参数记作 $\phi$ 。
我们可以写出 $\phi$ 的似然函数，由于似然函数中有很多乘法项（与训练样本集容量相同），会导致数据上溢出或下溢出，所以实际常使用对数似然函数，将乘法变为加法：
$\begin{split} L(\phi) &=\log\prod_{i=1}^N P(x_i,y_i;\phi) \\ &=\log\prod_{i=1}^N (P(x_i|y_i;\phi)P(y_i;\phi)) \\ &=\log\prod_{i=1}^N ((\prod_{j=1}^n P(x_i^{(j)}|y_i;\phi))P(y_i;\phi)) \\ &=\sum_{i=1}^{N}\sum_{j=1}^{n}\log P(x_i^{(j)}|y_i;\phi)+\sum_{i=1}^{N}\log P(y_i;\phi) \end{split}$
将对数似然函数以待估参数的形式来表示，其中：
$\begin{split} P(y_i;\phi) &=\prod_{k=1}^{K}P(Y=c_k)^{I(y_i=c_k)} \\ P(x_i^{(j)}|y_i;\phi) &=\prod_{l=1}^{S_j}P(X^{(j)}=a_{jl}|Y=c_k)^{I(x_i^{(j)}=a_{jl},y_i=c_k)} \end{split}$
代入对数似然函数，可得：
$\begin{split} L(\phi) &= \sum_{i=1}^{N}\sum_{j=1}^{n}\sum_{l=1}^{S_j}\log P(X^{(j)}=a_{jl}|Y=c_k)^{I(x_i^{(j)}=a_{jl},y_i=c_k)} \\ &+\sum_{i=1}^{N}\sum_{k=1}^{K}\log P(Y=c_k)^{I(y_i=c_k)} \\ &= \sum_{i=1}^{N}\sum_{j=1}^{n}\sum_{l=1}^{S_j}I(x_i^{(j)}=a_{jl},y_i=c_k)\log P(X^{(j)}=a_{jl}|Y=c_k) \\ &+\sum_{i=1}^{N}\sum_{k=1}^{K}I(y_i=c_k)\log P(Y=c_k) \end{split}$
由于概率的归一性，存在约束条件：
$\sum_{k=1}^{K}P(Y=c_k)=1 \\ \sum_{l=1}^{S_j}P(X^{(j)}=a_{jl}|Y=c_k)=1$
则带拉格朗日乘法项的对数似然函数函数为：
$\begin{split} L(\phi,\alpha,\beta) &= \sum_{i=1}^{N}\sum_{j=1}^{n}\sum_{l=1}^{S_j}I(x_i^{(j)}=a_{jl},y_i=c_k)\log P(X^{(j)}=a_{jl}|Y=c_k) \\ &+\sum_{i=1}^{N}\sum_{k=1}^{K}I(y_i=c_k)\log P(Y=c_k) \\ &+ \alpha(\sum_{k=1}^{K}P(Y=c_k)-1) \\ &+ \sum_{j=1}^{n}\beta_j(\sum_{l=1}^{S_j}P(X^{(j)}=a_{jl}|Y=c_k)-1) \end{split} \tag{1}$
对参数 $P(Y=c_k)$ 求偏导：
$\frac{\partial L(\phi,\alpha,\beta)}{\partial P(Y=c_k)} = \sum_{i=1}^{N}\frac{I(y_i=c_k)}{P(Y=c_k)} +\alpha=0 \tag{2}$
对参数 $\alpha$ 求偏导：
$\frac{\partial L(\phi,\alpha,\beta)}{\partial\alpha} = \sum_{k=1}^{K}P(Y=c_k)-1=0 \tag{3}$
对 $P(X^{(j)}=a_{jl}|Y=c_k)$ 求偏导：
$\begin{split} \frac{\partial L(\phi,\alpha,\beta)}{\partial P(X^{(j)}=a_{jl}|Y=c_k)} &=\sum_{i=1}^{N} \frac{I(x_i^{(j)}=a_{jl},y_i=c_k)}{P(X^{(j)}=a_{jl}|Y=c_k)} +\beta_j \\ &=0 \end{split} \tag{4}$
对 $\beta_j$ 求偏导：
$\frac{\partial L(\phi,\alpha,\beta)}{\partial\beta_j} = \sum_{l=1}^{S_j}P(X^{(j)}=a_{jl}|Y=c_k)-1=0 \tag{5}$
联立(2)(3)式，可解得：
$\begin{split} \alpha &=-N \\ P(Y=c_k) &= \frac{\sum_{i=1}^{N}I(y_i=c_k)}{N} \end{split}$
联立(4)(5)式，可解得：
$\begin{split} \beta_j &=-\sum_{l=1}^{S_j}\sum_{i=1}^{N} I(x_i^{(j)}=a_{jl},y_i=c_k) \\ &= -\sum_{i=1}^{N} I(y_i=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)} \end{split}$
至此，先验概率和条件概率的极大似然估计与本文第一节中给出的直觉公式一致。