朴素贝叶斯法学习笔记

频率派和贝叶斯派

频率派认为可以通过大量实验，从样本推断总体。比如假定总体服从均值为$\mu$，方差为$\sigma$的分布。根据中心极限定理，是可以通过抽样估算总体的参数的，而且抽样次数越多，对总体的估计就越准确。需要指出的是，频率派的观点认为$\mu$和$\sigma$都是固定，就是说他们都是某个确定的值。
但实际上，实验次数越多，成本就越高，而且很多时候是没有办法进行多次试验的。这时候，频率派对总体参数的估计就会存在较大偏差。
贝叶斯派则认为，可以先对总体的参数进行粗略估计（先验概率），然后根据实验结果不断调整参数的估计值（后验概率）。而且，贝叶斯派认为参数并不是固定的，而是服从某个概率分布的值。

朴素贝叶斯法

独立同分布假设

假设训练数据集$T=(x_1,y_1),(x_2,y_2),...,(x_n,y_n)$，可以理解为每个$x$都代表了一个完整的case。比如$x_1$可以用$x_1^{(1)}$来表示第一个样本的第1个特征，而一个样本可以有多个特征，比如$x_1^{(k)}$就表示第1个样本的第$k$个特征；而$y_1$就表示这个$x_1$这个case所属的类。
书上还有一句话，训练集是独立同分布的。也就是说所使用的到的样本都是从同一个总体中拿出来的，自然就服从同一个分布；如果不服从同分布，也就意味着我们无法得到最终的模型，我们只能根据不同的case得到不同的模型。独立就是说各样本之间互不影响，得到什么样的$y$值，只要看自己有什么样的$x$就可以了，$x_1$不用去管$x_2$的$y_2$值是怎么得到的。

学习过程

朴素贝叶斯法的最终目的是通过训练集学习$x$和$y$的联合概率分布$P(X,Y)$。这样当我们知道某个测试样本的$X$，我们就可以根据联合概率分布求出$Y$的概率分布。然后我们看哪个$Y$能够让$P(X,Y)$最大，我们就把这个$Y$作为这个测试样本$X$的类别。
我们假设$Y$有$k$个不同的取值，也就是说样本一共有$k$类。而我们一共有$n$个特征，$X_i^{(1)},X_i^{(2)},...,X_i^{(n)}$。
而为了通过训练集学到联合概率分布$P(X,Y)$，我们需要分别学到先验概率分布$$P(Y=c_k)$$以及条件概率分布$$P(X^{(1)}=x^{(1)},X^{(2)}=x^{(2)},...,X^{(n)}=x^{(n)}|Y=c_k)$$
这是因为当我们拿到测试数据集的时候，我们面临的问题是求：
$$P(Y=c_k|X^{(1)}=x^{(1)},X^{(2)}=x^{(2)},...,X^{(n)}=x^{(n)})$$
这是一个条件概率求解，而根据贝叶斯公式，我们知道：
$$P(A|B)=\frac{P(A)P(B|A)}{P(B)}$$
所以上面那个条件概率就等于：
$$\frac{P(Y=c_k)P(X^{(1)}=x^{(1)},X^{(2)}=x^{(2)},...,X^{(n)}=x^{(n)}|Y=c_k)}{P(X^{(1)}=x^{(1)},X^{(2)}=x^{(2)},...,X^{(n)}=x^{(n)})}\text{， }\text{\hspace{1em}(1)}$$
而且我们知道朴素贝叶斯之所以朴素，就是因为这个算法假定各特征都是独立的。也就是说$X^{(1)}$、$X^{(2)}$……$X^{(n)}$的互不影响，没有关系。其实相当于是把问题简单化了。有了这个条件，公式1就可以进一步化简：
$$P(X^{(1)}=x^{(1)},X^{(2)}=x^{(2)},...,X^{(n)}=x^{(n)})=\prod _{i=1}^{n}P(X^{(i)}=x^{(i)})$$
$$P(X^{(1)}=x^{(1)},X^{(2)}=x^{(2)},...,X^{(n)}=x^{(n)}|Y=c_k)=\prod _{i=1}^{n}P(X^{(i)}=x^{(i)}|Y=c_k)$$
所以公式1最后就变成了：
$$f_1=\frac{P(Y=c_k){\prod }_{i=1}^{n}P(X^{(i)}=x^{(i)}|Y=c_k)}{{\prod }_{i=1}^{n}P(X^{(i)}=x^{(i)})}\text{\hspace{1em}(2)}$$
我们知道，现在有了样本$X^{(i)}=x^{(i)}$，现在要求的是当$f_1$最大的时候，$c_k$是多少？也就是说现在$c_k$是未知量，而跟$X^{(i)}$相关的都是由数据集提供的，所以求$f_1$的最大值就等价于求$f_2$的最大值，二者的最大值不一样（我们也不关心），但取得最大值时的$c_k$是相等的。
$$f_2=P(Y=c_k)\prod _{i=1}^{n}P(X^{(i)}=x^{(i)}|Y=c_k)\text{\hspace{1em}(3)}$$

参数估计

极大似然估计

朴素贝叶斯法意味着我们要估计$P(Y=c_k)$以及$P(X^{(i)}=x^{(i)}|Y=c_k)$。
先验概率$P(Y=c_k)$的极大似然估计是：
$$P(Y=c_k)=\frac{\sum _{i=1}^{n}I(y_i=c_k)}{N}\text{,}k=1,\mathrm{2...}K$$
而每个特征$X^{(i)}$都可能有很多个取值，所以假设第$i$个特征$X^{(i)}$的可能取值为结合{ai1,ai2...aiSi}\lbrace{a_{i1},a_{i2}...a_{iS_i}}\rbrace{ai1​,ai2​...aiSi​​}，也就是说我们假设第$i$个特征可能的取值$S_i$种。
条件概率的极大似然估计是：$$P(X^{(i)}=a_{il}|Y=c_k)=\frac{\sum _{i=1}^{n}I(x_j^{(i)}=a_{il},y_i=c_k)}{\sum _{i=1}^{n}I(y_i=c_k)}$$
上式小标太多，解释一下，$x_j^{(i)}$表示第$j$个样本的第$i$个特征，$a_{il}$表示第$i$个特征的取值为$a_{il}$。
$I$为指示函数，也就是说当括号中的关系成立时，$I=1$，不成立时，$I=0$。
所以从这里也可以看出来，这个参数的估计过程就是“数数”。先验概率就是数$Y=c_k$出现多少次，占比多少。条件概率就是数$Y=c_k$的时候，$x^{(i)}$这个特征取$a_{il}$出现多少次，占比多少。可想而知，这是一项庞大的“数数”工程。

贝叶斯估计

极大似然估计可能会发生一个比较尴尬的事情，比如我们就假设样本的第3个特征$X^{(3)}$在训练集中所有取值为{1,3,5}\lbrace1,3,5\rbrace{1,3,5}，但是在测试集中，出现一个新值4。这时，如果按照极大似然法，条件概率$P(X^{(i)}=4|Y=c_k)=0$（因为训练集没有这个4，所以从训练集学到的条件概率就是0）。而目标函数$f_2$是一系列条件概率的累乘，所以最后无论其他特征的条件概率是多少，$f_2$恒等于0。
也就意味着学到的这个联合分布，过拟合了，对新出现的数据预测能力极差。
为了避免这一现象，现在需要引入贝叶斯估计，其实也可以理解为正则化的手段。具体的，条件概率的贝叶斯估计是：$$P(X^{(i)}=a_{il}|Y=c_k)=\frac{\sum _{i=1}^{n}I(x_j^{(i)}=a_{il},y_i=c_k)+\lambda }{\sum _{i=1}^{n}I(y_i=c_k)+S_i\lambda }$$
上式中，$\lambda \ge 0$，显而易见，当$\lambda =0$的时候就是极大似然估计。根据习惯，经常取$\lambda =1$，此时称为拉普拉斯平滑。
同样，也为了避免先验概率等于0，同样可以引入贝叶斯估计：$$P(Y=c_k)=\frac{\sum _{i=1}^{n}I(y_i=c_k)+\lambda }{N+K\lambda }$$
由于当$\lambda =1$，并且在样本量$N$越来越大的时候，$\lambda$对先验概率和条件概率的影响就会越来越小，甚至忽略不计。这就是所谓的拉普拉斯平滑的思想。