CMSC5724-数据挖掘之线性分类问题与感知机

这章主要探讨了线性分类问题这个大问题及其理论。

线性分类问题和线性可分的定义

可以将线性分类问题定义如下，有一个线性分类器（Linear classifier）为$h$，输入样本$X$，我们可以通过分类器预测其标签$h(x)$。其分类规则就是$x\cdot w\ge 0$（这里在定义的时候取到了$=$号），$h$输出其预测标签$h(x)=1$；否则$x\cdot w<0$，$h$输出其预测标签$h(x)=-1$。

PPT中可以认为$h^{\ast }$是那个「上帝」掌控的完美分类器，它在分布$D$上不会分类错误。

当存在一个训练集$S$的时候，如何题表示$S$是线性可分（Linearly separable）的？相当于我们分类器$h$分类出来的结果，和训练样本$p$的标签是一致的，如下所示，其中$w\cdot p=0$的地方是划分出来的超平面（这里需要严格划分超平面，因此不存在点在超平面上，取不到$=$号）。

其中让我疑惑的点是，线性分类问题找到的分类器都是过原点的嘛？是否有点缺乏普遍性？答案为是，参考知乎@李诗旸在机器学习中的超平面为什么不过原点？上的回答，“线性子空间”需要过原点，“超平面”可以指任意线性子空间在任意仿射下的象，言外之意不需要过原点。至于是否缺乏普适性，其实在${\mathbb{R}}^d$上不过原点的超平面，可以通过法向量${\omega }^{d+1}$的构造，转换为${\mathbb{R}}^{d+1}$上过原点的超平面，参考相关题目中的题目5。

感知机算法Perceptron

执行过程

在定义了线性分类问题后，我们就是想找到那个分类器$h$所表示的分割的超平面，找到了该超平面就能让训练样本$S$上的误差为0，即$er{r}_S(h)=0$。

为了找到合适的分类器$h$，其实就是要找到它的参数$w$，感知机算法先初始化$w=(0,0,...,0)$，然后在迭代中找到那些异常点violation point $p$，根据这些异常点调整$w$，直到不出现异常点。其中异常点的判断是和它们的label直接相关的，当label $p=1$，正常的点需要分类器算出来的$w\cdot p>0$（这里就是严格取不到$=$），否则就是异常，异常调整的规则就是$w=w+p$；对于label $p=-1$，正常的点需要分类器算出来的$w\cdot p<0$，否则就是异常，异常调整的规则就是$w=w-p$。

老师推导了一个完整的例子，两步确实找到了分割平面，实在是small and sweet。在图中我们需要记住的是，一个线性分割超平面的决定参数$\omega$，对应着就是垂直于该超平面的法向量（图中的红色箭头）。

最大调整次数通理

其中涉及到几个概念：

• $R$：radius, the farthest distance from the origin to a point.
• margin of classifier: distance from the boundary line to the closest point.
• $\gamma$: the largest margin of all seperating plane.

通理就是：感知机最大的调整次数为${\left(\frac{R}{r}\right)}^2$，或者可以认为从$w_0=(0,0...,0)$开始最多找到${\left(\frac{R}{r}\right)}^2$个violation point.

为了证明这个Theorem，需要了解一些矩阵分析vector analysis的知识：

最重要的一个分析就是将某条直线$l^{\ast }$的margin，和其单位法向量${\vec{u}}^{\ast }$联系起来，如下图所示，通过矩形的对边相等，我们可以看出，训练集$S$中任意一点$\vec{p}$到直线$l^{\ast }$的距离为$|\overrightarrow{u^{\ast }}\cdot \overrightarrow{p^{\ast }}|$， 也可以这样理解，点到直线的距离$|\frac{\vec{p}\cdot \vec{w}}{|\vec{w}|}|=|\overrightarrow{u^{\ast }}\cdot \overrightarrow{p^{\ast }}|$.

因为margin是点到直线的最短距离，训练集$S$中任意一点$\vec{p}$到直线$l^{\ast }$的距离，必定是大于等于$margin(l^{\ast })$的。

为了证明这个通理，需要证明两个引理：

1. $w_{i+1}\ast u^{\ast }\ge w_i\ast u^{\ast }+\gamma$ 这表明了在迭代过程中，我们修正的参数$w^i$在不断往正确的方向调整，且每次调整的幅度，体现在与我们最终要找的超平面$l^{\ast }$的法向量$u^{\ast }$点乘之后，大于等于$\gamma$。
2. $|w_{i+1}{|}^2\le |w_i{|}^2+R^2$ 这表明在迭代过程中，我们修正的参数的模的上限是在不断缩小的，体现在幅度上，就是小于等于$R^2$。

Lemma1证明，其中$w_0=(0,0,...0)$：

Lemma2证明：

将上面的两个引理证明的结论一夹逼，就得到了通理的证明，主要是记住两个引理的最后一步。
$$|w_k|\ge k\gamma$$
$$|w_k{|}^2\le k{R}^2$$

进一步思考

感知机算法能够找到分类器$h$让训练样本$S$上的emprical error为0，即$er{r}_S(h)=0$，进一步地，我们能否用它来约束达到一个较小的泛化误差$er{r}_D(h)$? 用第一节课学过的泛化误差和训练误差的通理是不能够进行约束了。因为其中有一项$ln(\left|H\right|)$和可能的分类器数目有关，然而在线性分类的空间中这个值无限大，不能够像决策树那样根据parameter数目进行合理估计。这就为下一章引入VC-dim埋下了伏笔，将训练误差和泛化误差的关系用VC-dim联系起来。

相关题目

1. 应用感知机算法迭代，掌握其迭代过程
   

2. 考察通理的应用，超过最大迭代次数${\left(\frac{R}{\gamma }\right)}^2$，则没有超平面。
   

3. 直接带入通理计算，对于找到的任意点来说一定都是上限。
   
   

4. 通理的推导过程，系数$\lambda$可以在不等式中消去。
   

5. 线性分类问题的推广，从${\mathbb{R}}^d$空间出发，构造法向量${\omega }^{{}^{\prime }}$到${\mathbb{R}}^{d+1}$。