极大似然估计、最小二乘法及朴素贝叶斯

1. 问题定义

样本集 $D$ 中的样本都是独立同分布，且样本数为 $m$
$D=\{(X_1, Y_1), (X_2, Y_2), ...\ ,(X_m,Y_m)\}$
其中， $X_k=\{x_1, x_2, ...\ ,x_n\}$ 是第 $k$ 个样本的 $n$ 个特征项， $X_k\in\mathbb{R}^n$ 。 $Y_k$ 是第 $k$ 个样本的类别， $Y_k\in\mathbb{R}^1$ 。 $Y_k\in Y=\{y_1, y_2, ...\ ,y_v\}$ ，其中 $Y$ 是类别的空间， $Y\in\mathbb{R}^v$ 。

要解决的问题为，在已知样本和其所属的类别的条件下，求得某个样本是某一类别的概率。

2. 贝叶斯决策

首先看经典的贝叶斯公式：

$P(y|x) = \frac{P(x|y)P(y)}{P(x)}\tag{1}$

按照上述问题定义，可将贝叶斯公式写为：
$P(y|X) = \frac{P(X|y)P(y)}{P(X)}\tag{2}$
由于每个类别都是独立的，则：
$P(y|X) = \frac{P(X|y)P(y)}{\sum_{i=1}^{v}P(X|y_i)P(y_i)}\tag{3}$

在这里，我们称：
$P(y)$ 为先验概率

$P(X|y)$ 为条件概率

$P(y|X)$ 为后验概率

$P(X)$ 为先验概率

3. 朴素贝叶斯

根据上式（3）我们能够看到，在某一个样本所具有的的特征 $X$ 条件下，该样本属于某一种类别的概率 $P(y|X)$ 的相对大小与分母无关（在各个条件概率计算过程中，分母的值都相同，而且等于各个条件概率中分子值的和，因此，在计算得到各个分子后求和，也就得到了分母的值）。

因此，在构建朴素贝叶斯时，我们可以先忽略分母 $P(X)$ ，着重求解分子。

对于分子中的先验概率 $P(y)$ ，我们可以通过样本数据集 $D$ 来统计得到。

而对于分子中的条件概率 $P(X|y)$ ，我们也可以根据样本数据集中出现的样本来估计条件概率。但是，在实际中， $X$ 往往包含多个特征，在样本中往往不能包含属性值的所有可能组合（假设每个属性都是二值属性，那么就有 $2^n$ 中属性之间的组合），那么在样本集中，很多的 $P(X|y)$ 都会为0。然而，这些样本仅仅可能是我们的数据集中并没有观察到而并非真的不存在。

这时，朴素贝叶斯的条件独立性假设就发挥作用了。

通过条件独立性假设，我们可以将公式（3）改写为：

$P(y|X) = \frac{P(X|y)P(y)}{\sum_{i=1}^{v}P(X|y_i)P(y_i)} = \frac{P(x_1,x_2,... \ ,x_n|y)P(y)}{\sum_{i=1}^{v}P(X|y_i)P(y_i)} = \frac{\prod_{j=1}^{n}P(x_j|y)P(y)}{\sum_{i=1}^{v}P(X|y_i)P(y_i)}\tag{4}$

上式将每个样本的属性集合 $X$ 中的每一个属性看做是相互独立的，所以可以将 $P(x_1,x_2,... \ ,x_n|y)$ 拆分成 $\prod_{j=1}^{n}P(x_j|y)P(y)$ ，在该假设下，就基本解决了样本集中属性组合不能覆盖所有可能性的问题。

根据公式（4），我们就可以求得在已知的属性下，该样本属于各个类别的概率值，那判断的结果为：
$h(X) = \mathop{\arg\min}_{y\in Y} \prod_{j=1}^{n}P(x_j|y)P(y)\tag{5}$

离散属性与连续属性的处理

在估计条件概率的时候，若 $x_i$ 为离散属性，那么我们计算每个属性占该类样本的比例记好了：
$P(x_i|y) = \frac{|D_{y,x_i}|}{|D_y|}\tag{6}$

如果 $x_i$ 是连续值，就需要用概率密度函数来计算其概率，即假定对于某一类别中样本的属性 $x_i$ 满足如下正态分布： $p(x_i|y) \sim N(\mu_{y,i},\sigma_{y,i}^2)$ ，其中 $\mu_{y,i},\sigma_{y,i}^2$ 分别表示第 $y$ 类样本在第 $i$ 个属性上的均值和方差。则：
$P(x_i|y) = \frac{1}{\sqrt{2\pi}\sigma_{y,i}}exp(-\frac{(x_i-\mu_{y,i})^2}{2\sigma_{y,i}^2})\tag{7}$

拉普拉斯修正(Laplacian correction)

朴素贝叶斯分类器在实际使用中还需要注意的一个问题是：若某个离散类型的属性值在训练集中没有与某个类同时出现过，那么当我们使用 $P(x_i|y) = \frac{|D_{y,x_i}|}{|D_y|}$ 对齐进行估计是， $P(x_i|y)$ 会等于0。但如果这时有个测试集样本，在该属性 $x_i$ 的取值正好是训练集中所没有出现的，但其他的属性都非常符合该类的特征，但是由于计算公式是各个条件概率相乘计算得到，则不管其他属性取值如何，计算得到该测试集样本属于该类的概率 $P(x_i|y)$ 始终为0，这显然是不合常理的。

这一问题本质上是我们的训练集不够完整，没有足够的样本。为了避免该问题，我们通常在估计概率值时，对其进行“平滑”（smoothing）操作，通常使用“拉普拉斯修正”（Laplacian correction）。

具体的方法为：
$\hat{P}(y) = \frac{|D_y| + 1}{|D|+v}\tag{8}$
其中， $v$ 表示可能的类别数。
$\hat{P}(x_i|y) = \frac{|D_{y,x_i}| + 1}{|D|+w_i}\tag{9}$
其中， $w_i$ 表示第 $i$ 个属性的可能取值数（针对离散值来说，连续值由于使用服从正态分布的概率密度函数来计算条件概率，因此不会出现概率为零的情况）
通过公式（8）和（9），在分子中加1，就避免了计算针对每个属性时的条件概率为零的情况出现。

4. 极大似然估计

通过上面的朴素贝叶斯算法我们能够看到，很多情况下都需要我们对类别或特征进行估计得到其概率密度函数。

简单来说，极大似然估计就是在已知样本的情况下，假定该样本服从某项分布，但是该分布的参数未知。目标就是当参数取什么值时使得出现数据集中样本的概率最大，这时我们就估计假定样本服从的分布的参数为使得概率最大的参数。

极大似然估计

5. 最小二乘法

最小二乘法是为了拟合样本的实际值与模型的输出值。当假设极大似然估计中似然概率函数为正态分布时，最小二乘法和极大似然估计得到统一。

梯度下降（不做赘述）

代数求解

$J(\theta) = \frac{1}{2}\sum_{i=1}^{n}(y_i-h(x_i))^2 = \frac{1}{2}\sum_{i=1}^{n}(y_i-\theta_1x_i-\theta_0)^2$

分别求关于参数 $\theta_1$ $\theta_0$ 的偏导：
$\frac{\partial J(\theta)}{\partial \theta_1} = \sum_{i=1}^n(y_i-\theta_1x_i-\theta_0)\cdot-x_i=-\sum_{i=1}^nx_iy_i +\theta_1\sum_{i=1}^nx_i^2+\theta_0\sum_{i=1}^nx_i$

$\frac{\partial J(\theta)}{\partial \theta_0} = \sum_{i=1}^n(y_i-\theta_1x_i-\theta_0)\cdot-1=-\sum_{i=1}^ny_i +\theta_1\sum_{i=1}^nx_i+\theta_0\cdot n$

根据上述的两个多项式在等于0的时候， $J(\theta)$ 取得最小值，可以分别求解 $\theta_1$ ， $\theta_0$ 。

假设 $A=\sum_{i=1}^nx_iy_i$ ， $B=\sum_{i=1}^nx_i^2$ ， $C=\sum_{i=1}^nx_i$ ， $D=\sum_{i=1}^ny_i$
则上述两个偏导方程可以表示为
$-A+\theta_1 \cdot B + \theta_0 \cdot C = 0$
$-D + \theta_1 \cdot C + \theta_0 \cdot n = 0$

求解得到：
$\theta_1 = \frac{An-CD}{B-C^2}= \frac{n \cdot \sum_{i=1}^nx_iy_i - \sum_{i=1}^nx_i\sum_{i=1}^ny_i}{\sum_{i=1}^nx_i^2 - (\sum_{i=1}^nx_i)^2}$

$\theta_0 = \frac{AC-BD}{C^2-nB}=\frac{\sum_{i=1}^nx_iy_i\sum_{i=1}^nx_i-\sum_{i=1}^nx_i^2\sum_{i=1}^ny_i}{(\sum_{i=1}^nx_i)^2-n \cdot \sum_{i=1}^nx_i^2}$