分类的线性方法

这两天看这本书，每天都要遭受不同程度的打击。读起来进度非常之慢，并且时不时会卡壳。如果有童鞋能够一块讨论，一定会受益匪浅。下面小结一下这几天看书的一些心得吧。
本书的第三章内容是线性回归，包括了很多变量选择的内容。这部分内容，我暂时先不写笔记。在我们已经拥有了线性回归的相关的基本知识之后，我们来看第四章。第四章的题目是linear methods for classification。众所周知，分类是机器学习，数据挖掘的最重要的任务之一。而线性方法则是这些方法中最为基本的，往往也是比较有效地，因此需要花费精力来学习这些基本的内容。
首先，所谓的分类问题，是一种有指导的学习，也就是说我们知道数据本身属于哪一类，我们要做的是找出数据分类的规则，以便对于新的数据进行分类。第二，我们要搞清楚什么是线性方法，线性到底意味着什么。我们举一个非常直观的例子。
上面的图中所表示的是一个线性判别分析分类的结果。数据是二维的，分成三类，分别用不同颜色的点表示。图中的黑色的直线，则是线性判别函数所得到的分类的边界。我们可以看到，分类的边界关于二维输入变量是线性的。（在二维情况下，直观看来就是直线）。推广到高维的情况，分类边界如果是超平面或者仿射集（affine set，这个东西我到现在也没搞懂是什么，但是没关系，我们就知道是超平面就行，不影响理解），那么就可以说这个分类的方法是线性的。更进一步的，如果分类的边界可以表示成输入变量的线性组合，我们就说是用线性方法进行分类的。我们不妨称这样的分类的准则为线性分类器。
事实上，线性方法有很多种。我们最常见的就是传说的线性回归模型，此外，还有logistic回归，线性判别分析，以及分隔平面法。我们下面一一介绍。
（1）线性回归模型。
要用线性回归的方法来学习分类的规则，重要的一步是对输出进行编码（code）。编码的目的是使得定性的输出变量能够定量化，然后套用线性回归，最小二乘之类的即可。编码的想法也很简单，比如说我们的输出集合一共有K个类，那么我们就产生K个指标变量($Y_k$)，($k=1,\ldots,K$)，如果输出确实属于第k类，则($Y_k=1$)，其他的($Y_l=0$)。这样对于每行观测，我们都有K个指标来表示其输出。这就把问题转化为了多元回归的问题。而且在这里，回归问题更加简单，若训练样本有N行观测，则会有一个($N \times K$)的指标矩阵($\textbf{Y}$)，这个矩阵每一行只有一个1，剩下的都是0.对于这个矩阵的每一列，我们同时用最小二乘进行回归就得到了一个拟合的模型
($\hat{\textbf{Y}}=\textbf{X}(\textbf{X}^T\textbf{X})^{-1}\textbf{X}^T\textbf{Y}$)
对于一个新的观测，我们如何通过上式进行判断呢？
我们首先将新的观测代入拟合的模型，从而得到了一个输出。这个输出肯定是一个K维的向量。然后我们找出这个向量元素中最大的值，比如第m个元素最大，我们就把这个观测分类为第m类。
这就是线性回归分类器（我们姑且这么称呼他，我才疏学浅，并不知道是否有此方法的确切称呼）。我们可以继续探究一下用这种方法进行分类的道理。它的合理性在哪。我们知道，线性回归模型得出的结果是对条件期望的估计，而对于如上编码的情况，条件期望正是分类的后验概率分布。这一点，强有力的支持了我们用线性回归做分类问题。
除此以外，我们还有另外一种利用线性回归方法解决分类问题的视角，视角不同，但是结果与上述内容完全相同。
线性回归方法简单，但是简单也有简单的问题。对于三个类别以上的分类问题，尤其是当类别数比较大的时候，由于线性回归对模型的要求过于严格，因此分类肯定会有重叠。下图是原书中的一个例子
我们看到，中间蓝色的类完全被忽略了。也就是说蓝色的这一类分类全部是错误的。
这个肯定是我们不想看到的。因此，我们需要想一些方法来解决。解决的方法，其思想核心与我们试验设计中考察交互作用，对交互项进行回归的思想很像。也就是说我们考虑变量之间的交互效应，拟合多项式回归模型，当多项式回归模型阶数合适的时候，可以减轻上述问题带来的困扰。这个就不多展开讲了。（这一部分是我的主修课程试验设计数据分析中的一个很重要的部分，实在是不想展开多讲）。
（2）线性判别分析
关于判别分析，最早是在多元统计分析这门课中学习的。当时年轻不懂事儿，多元统计分析没认真学习，课后作业也都是抄同学的。而且这些年，几乎没有什么实际的例子用判别分析，因此，对于这部分内容基本上脑袋里一片空白。还好这本书对于判别分析的介绍相对来说还是比较容易理解的。
统计决策理论告诉我们，如果我们要做一个最优的分类，我们需要知道分类的后验概率分布情况。仍然假设有K个类别，($\pi_k$)是这K个类别的先验概率，显然($\sum_{i=1}^K \pi_k=1$)，并且我们知道每一个类别内部的数据的分布情况($f_k(x)$)。我们利用贝叶斯公式就可以求得分类的后验概率分布
($p(G=k|X=x)=\frac{f_k(x)\pi_k}{\sum_{l=1}^K f_l(x)\pi_l}$)


_______________________
而线性判别分析，则是假设类别内部数据是服从正态分布的。当然还有其他分布的假设，本书后续的内容也会涉及到。）
下面我们来看一看什么是线性判别分析。
我们假设每一个类内部的数据密度是多元正态的，并且协方差矩阵相同。即如下：
($f_k(x)=\frac{1}{(2\pi)^{\frac{p}{2}}\|\Sigma\|^{\frac{1}{2}}}exp\{-\frac{1}{2}(x-\mu_k)^T\Sigma^{-1}(x-\mu_k)\}$)


并且我们可以简单的推到，看到两个类别的后验概率之比再取对数得到的结果关于输入($x$)是线性的。也就是说分类边界对输入($X$)是线性的。因此这个分类器叫做线性判别分析。
以上就是线性判别分析的基本的想法。而从这个想法中再提炼，我们得到所谓的线性判别函数：
($\delta=x^T\Sigma^{-1}\mu_k-\frac{1}{2}\mu_k^T\Sigma^{-1}\mu_k+log\pi_k$)
分类的规则也是对于一个新的输入($x$)，我们找到是的($\delta_k(x)$)最大的k，然后就把($x$)归类为类别k。
对于上述判别函数，有三个参数需要利用训练样本进行估计，先验分布，正态分布的均值以及协方差阵。这些都可以利用最简单的点估计来估计。这里也不多提了。
本书的后续部分介绍了一点二次判别分析的内容，这部分内容在我的笔记里也不体现了。回头有时间，会把这些内容做一个整合，写点笔记。
对于线性判别分析，当类别比较多的时候，降秩成为了一个有趣的话题。降秩问题源于当类别比较多的时候，理论上证明了一个原空间的低维子空间可以很好的代表原空间，并且在分类问题上没有任何的信息损失。这就涉及到如何找到这个低维的子空间。Fisher运用特征分解的方法，很好的解决了这个问题。关于这个问题，原书的内容讲的很清楚，此外，宾夕法尼亚州立大学统计系的网页上有一个相关问题的课件，对此问题也讲的很清晰。关于这个问题我昨天看了整整一个上午，大致的推导过程不会太难。
在R里，MASS包中的lda()函数可以做线性判别分析。
上面的图片是原书里的一个模拟的例子，我们可以看到线性判别分析的分类效果是挺不错的。
（3）logistic回归
logistic回归可以视作是广义线性回归模型的一种。陈希孺先生在国内的某个杂志上有连载10篇论文，介绍广义线性模型。内容相对来说比较理论，比较艰深。现在广义线性模型的应用比较广泛。在我看来，如果单纯要应用logistic回归做分类问题，我们只要把它看成是线性回归的简单推广即可。具体的学理的部分，有能力者可以去学习下，如要应用起来，或许不一定需要那么多理论的知识。
首先，我们需要分类的边界是线性的。
($log\frac{p(G=1|X=x)}{p(G=K|X=x)}=\beta_{10}+\beta_1^Tx$)
($log\frac{p(G=2|X=x)}{p(G=K|X=x)}=\beta_{20}+\beta_2^Tx$)
($\cdots$)
($log\frac{p(G=K-1|X=x)}{p(G=K|X=x)}=\beta_{(K-1)0}+\beta_{K-1}^Tx$)
然后呢，我们需要后验概率加起来肯定是1.因此我们选择logistic变换
($p(G=k|X=x)=\frac{exp(\beta_{k0}+\beta_k^Tx)}{1+\sum_{l=1}^{K-1}exp(\beta_{l0}+\beta_l^Tx)}$)，($k=1,\ldots,K-1$)

($p(G=k|X=x)=\frac{1}{1+\sum_{l=1}^{K-1}exp(\beta_{l0}+\beta_l^Tx)}$)

显然，这个变换是符合了上述的条件的。
通常情况下，logistic模型并不是由最小二乘法拟合得到的，而是利用了极大似然方法。关于这个模型的求解，用到了Newton-Raphson算法，到目前为止我还没太搞明白这个最优化算法（下一步应该学点最优化方面的东西了）。总之，这个算法是一个迭代的过程，通过迭代，得到参数的估计，满足目标函数。（btw，从某种角度来讲，所有的参数回归模型，包括线性回归，广义线性回归，非线性回归，都是最优化问题）。

logistic回归在R中的函数glm。

到目前为止，我们应该可以发现一个比较有趣的问题，就是线性判别分析和logistic回归的分类边界的模型事实上是一样的。都是x的线性函数。二者的差别在于线性判别分析估计参数的方法是最小二乘，而且对模型的约束很多，包括正态性假设以及等协方差函数的假设，而logistic回归则限制少了很多，参数的估计方法也用了更为一般化的极大似然估计。更为理论的内容书中也有所介绍。感兴趣的读者可以去推导一下那部分的公式，也是挺有意思的。
下面进入本次读书笔记的最后一部分
（4）seperating hyperplanes
这个我不太清楚怎么翻译，翻译成”分隔超平面“？事实上，正是这部分内容令我感到非常的郁闷，看了很久也不是很明白。我们直接看看书上是怎么说的吧。
书上首先举了一个例子
这个图中一共有20个点，来自于二维欧式空间，这些点属于两个不同的类，分别用不同的颜色来区分。我们可以看到图中有几条分隔的直线，而事实上，这样的分隔的直线是有无穷多条的。我们的目的，是从这无穷多的超平面中搜索出一个分类效果最好的。用到的算法是Rosenblatt's perceptron learning algorithem,具体的算法，我实在也是没心思看了，每次不管看书还是看文章，看到最后部分都是匆忙略过。妈的。
总之，如果点没有被分隔开的话，这个算法是不会收敛的。之后的部分属于作者标出来的难点
所以我直接就没看……
今儿就到这了。继续努力吧，先至少把这本书从头到尾过一遍。