机器学习06-非线性分类器

1.朴素贝叶斯

在上节朴素贝叶斯的基础上做些调整，上节中输入变量服从0-1分布，并没有用到关键词出现次数的信息，这里修正一下令\( X_i=k \)表示第\( i \)个关键词出现了\( k \)次。这样我们或许需要更多的参数，因为分布由伯努利变成多项式，回忆logistic回归到soft\max回归的过渡，一个比较简单却有点麻烦的过程。
这里主要介绍另一个模型，变量的表示方法不同。预设一个词典，事实上这个词典就是上节所说的特征向量。对每封邮件计算其长度并表示成： \[ (x_1,x_2,x_3 \ldots x_{n}) \] 其中下表n表示邮件长度，第i封邮件的长度用\( n_i \)表示，\( x_j \)表示邮件中的第\( j \)个词；向量中每个变量的取值在[0,k]之间，其中k表示字典的长度，那么应该可以猜到了，\( x_j=k \)表示邮件中的第\( j \)个词是字典中的第k个词。
记： \[ \phi_{i|y=1}=p(x_j=k|y=1) \qquad \phi_{i|y=0}=p(x_j=k|y=0) \qquad \phi_y=p(y=1) \] 那么\( \phi_{i|y=1} \)就表示在垃圾邮件中任意一个位置出现字典中第i个词的概率。 \ 联合分布概率： \[ p(x,y)= \big( \prod_{i=1}^{n} p(x_i|y) \big) p(y) \] 运用最大似然估计得到参数估计值如下： \[ \begin{aligned} \phi_{i|y=1}&= \frac{\sum_{j=1}^{m} \sum_{l=1}^{n_j} I(x_l^{(j)}=i,y^{(j)}=1) } {\sum_{j=1}^{m} y^{(j)}*n_j } \\ \phi_{i|y=0}&= \frac{\sum_{j=1}^{m} \sum_{l=1}^{n_j} I(x_l^{(j)}=i,y^{(j)}=0) } {\sum_{j=1}^{m} (1-y^{(j)})*n_j } \\ \phi_y &= \frac{\sum_{j=1}^{m} y^{(j)}}{m} \end{aligned} \] 不难发现，上式仍然是平均的概念。上节介绍过拉普拉斯平滑，运用在这里便是： \[ \phi_{i|y=1}= \frac{1+ \sum_{j=1}^{m} \sum_{l=1}^{n_j} I(x_l^{(j)}=i,y^{(j)}=1) } {k + \sum_{j=1}^{m} y^{(j)}*n_j } \\ \] 另两个式子省略，一样的道理。
最后的预测与上节一样，仍然是使用贝叶斯公式，略过。
这节的模型与上节的模型不同之处在于，每封邮件的变量个数不同，取决与邮件长度；对于上一节的模型，设置 好特征向量之后，每封邮件都有相同的变量个数，当关键词很多通常也确实是很多，此节的模型应该会比较高效。

2.非线性分类器(non-linear classification)

前边所讲的模型都是线性分类器，在二维空间中可以得到一条直线作为分界线(如果只有两个变量的话)，现在开始介绍两个非线性分类器：神经网络(natural network)和支持向量机(support vector machine)，重点是支持向量机，简称SVM，被很多人奉为最精确高效的分类器。

神经网络(natural network)

神经网络是模拟生物的信号传输系统，由某些神经元接收外部刺激后产生信号并传递到其他神经元，经过若干次传递后到达最底层使生物作出相应的反应。适合变量间关系复杂相关性较强的情况，参考维基百科的介绍。在传递过程中不同的神经元有不同的作用，因此运用神经网络需要深入研究项目，自定义神经元，是比较麻烦的东西。相比之下，SVM无须定制，而且据说效率堪比最高效的神经网络模型(只是据说- -！)。

支持向量机(support vector machine)

假设输入变量有两个，输出变量只有两个类别，支持向量机的想法是寻找二维空间的一条直线把两类样本分开并使得两类样本到该直线的距离最长。样本到直线的距离定义为样本中的所有点到直线距离的最小值。 在多元中，直线变成超平面，比如三元变量就是寻找一个平面。
用数学语言描述更清晰些，在此之前先对某些参数重新定义一下： \[ \begin{aligned} y &\in \{-1,1\} \qquad \textrm{not} \qquad \{0,1\} \\ g(z) &= \left\{ \begin{array}{} 1 &\textrm{z$\ge$0} \\ -1 &\textrm{z<0} \end{array} \right. \\ h_{w,b}(x) &= g(z) = g(w^Tx+b) \end{aligned} \] 目前变化只是把分类标记变成-1和1，理论上是怎么定义都无所谓的，不过这样定义有利于计算；另外在\( h_{w,b}(x) = g(w^Tx+b) \)中\( x \)不含常数项1，后边有常数项b。不过看起来还是线性函数线性边界，别急~
估计参数\( w \)和\( b \)是一个比较复杂的最优化问题。在上述数学定义下一条直线如果能够分割两类样本(如果样本是线性可分的话)，那么下式一定成立： \[ y(w^Tx+b) \ge 0 \] 很明显： \[ y=1 \to z=w^Tx+b\ge 0 \to y(w^Tx+b) \ge 0 \\ y=-1 \to z=w^Tx+b < 0 \to y(w^Tx+b) \ge 0 \] 相反的，如果存在这样的\( w \)和\( b \)使得上式恒成立，那么便说样本是线性可分的。到这里应该发现改变标记方式成{-1, 1}的目的了。
接下来看样本到直线的距离：

如图所示，假设只有两个样本。样本到直线的距离就是每个点到直线的距离，对于直线上的点均有\( w^Tx+b=0 \)。记点到直线的距离为\( l \)，把样本点移动到直线上，用数学语言表示就是\( x- l*\frac{w}{\Vert w \Vert} \)(注意\( x \)和\( w \)都是向量，\( \Vert w \Vert = \sqrt{w^Tw} \)即\( w \)的模，\( \frac{w}{\Vert w \Vert} \)是一个单位向量且与分割线垂直)，故\( w^T(x- l*\frac{w}{\Vert w \Vert})+b=0 \)，那么\( l=\frac{w^Tx+b}{\Vert w \Vert} \)。这是对于正样本(即\( w^Tx+b \ge 0 \)的样本)到直线的距离公式，更一般的距离公式是： \( l=\frac{y(w^Tx+b)}{\Vert w \Vert} \)，给这个实际距离一个专业术语叫做几何距离。
定义样本的函数距离为\( \hat l^{(i)}=y^{(i)}(w^Tx^{(i)}+b) \),明显的\( \hat l=l*\Vert w \Vert \)。 在多样本情况下，\( l = \min\{ l^{(1)},l^{(2)},l^{(3)} \ldots \ \} \)，使样本到直线的距离最大就是\( \max l=\max \min\{ l^{(1)},l^{(2)},l^{(3)} \ldots \} \)。其中满足\( \max l=l^{(i)} \)的样本点被称为支持向量(support vector)。
现在问题转化为一个数学模型： \[ \max l \\ l = \min\{ l^{(1)},l^{(2)},l^{(3)} \ldots \} \\ \textrm{st.} \qquad y^{(i)}(w^Tx^{(i)}+b) \ge 0 \qquad \textrm{i=1,2...m} \] 为了求\( \max l^{(i)} \)，其实可以放大\( w \)和\( b \)使得结果无限大，而\( y^{(i)}(w^Tx^{(i)}+b) \)的符号不变，在不影响约束条件的情况下使样本之间的距离无限放大。所以人为添加一个约束条件:\( \Vert w \Vert=1 \)，在这个条件下\( \hat l=l*\Vert w \Vert=l \)，使得问题简化，转化为： \[ \max \hat l \\ \hat l=\min\{ \hat{l}^{(1)},\hat{l}^{(2)},\hat{l}^{(3)} \ldots \} \\ \textrm{st.} \qquad y^{(i)}(w^Tx^{(i)}+b) \ge 0 \qquad \textrm{i=1,2...m} \\ \Vert w \Vert =1 \] 其中约束条件\( y^{(i)}(w^Tx^{(i)}+b) \ge 0 \)是为了保证样本线性可分，在线性不可分的情况下无解，我们可以把这个约束条件去掉，得到最终的优化结果如果\( \max{\hat l} >0 \)就表示线性可分。故问题可以简化为： \[ \max \hat l \\ \textrm{st.} \qquad y^{(i)}(w^Tx^{(i)}+b) \ge \hat l \qquad \textrm{i=1,2...m} \\ \Vert w \Vert =1 \]