线性判别函数

回顾模式分类的途径

思路一：估计条件概率密度函数，然后利用贝叶斯公式求出后验概率进行决策。而概率密度函数的估计有参数估计和分参数估计两种方式。其中参数估计有最大似然估计和贝叶斯估计，非参数估计有Parzen窗估计和KNN估计。思路二：直接用KNN算出后验概率即可进行决策思路三：直接找到可用于分类的判别函数。

这篇文章，我们主要讨论思路三，直接通过数据确定线性判别函数的参数，进而分类决策。我们的基本想法是：

给定一个线性判别函数，并且函数的参数形式已知。

采用训练样本的方法来确定判别函数的参数。

通过我们的判别函数对新样本进行决策

从最简单的二分类问题入手

对于一个两类问题，已知样本空间中的n个d维数据及其对应的类别。类与类之间是线性可分的。现假设某一个别类的线性判别函数的基本形式为 $$g(x)=w^{T}x+w_0$$ 然后利用样本数据对参数$w^T$和偏置${\omega }_0$进行训练。

训练的标准是 $$\{\begin{array}{l}g(x_i)>0,x_i\in {\omega }_1\\ g(x_i)<0,x_i\in {\omega }_2\end{array}$$ 直观地理解是我们给x的每一个分量乘以一个权重系数，求和之后与阈值${\omega }_0$进行比较，进行二值分类。

几何解释

可以从几何的角度给出更形象的解释，如图所示 平面g(x)=0为两类别的决策面H，将样本空间V分割成两部分，即第一类的决策域R_1和第二类的决策域R_2

显然，w和平面H正交。证明：若$x_1,x_2\in H$，则$w^T{x}_1+{\omega }_0=w^T{x}_2+{\omega }_0$所以$w^T(x_1-x_2)=0$，即w与H面上任一个向量正交，因此，w与平面H正交

由上图可知 $$x=x_p+r\frac{w}{||w||}$$ 其中，x_p是x在H上的投影向量，r是x到H的代数距离，其正负对应两个不同的决策域。

因为x_p在H上，因此 $$g(x_p)=w^T{x}_p+{\omega }_0=0$$ 由以上两个式子可得 $$g(x)=w^{T}x+{\omega }_0=r||w||$$ 显然，g(x)可以表示x到H的某种距离。而且原点到平面的距离为 $$r_0=\frac{g(0)}{||w||}=\frac{{\omega }_0}{||w||}$$

样本的齐次化处理

对于判别函数 $$g(x)=w^{T}x+w_0$$ 通过对样本数据x的处理，可以使得上述判别函数等价于齐次形式。如果把${\omega }_0$当做一个样本数据，且其加权系数为1，即 $$g(x_{+})=w_{+}^T{x}_{+}$$ $$x_{+}=\left[\begin{array}{c}{\omega }_0\\ x\end{array}\right]$$ $$w_{+}=\left[\begin{array}{c}1\\ w^T\end{array}\right],$$ 显然，判别函数变成了齐次的，方便计算

样本的规范化处理

对于两类问题 $$\begin{gathered} g(x_i)>0when{x}_i\in {\omega }_1 \\ g(x_i)<0when{x}_i\in {\omega }_2 \end{gathered}$$ 如果将属于第二类的样本取相反数，与第一类样本一起构成新的样本y，则 $$g(y)=a^{T}y>0$$ 这个过程，成为齐次样本的规范化处理。

从上述的齐次规范化样本的判别函数可以直观地看出

每一个样本y_i都是解a的一个约束，即$a^T{y}_i>0$;任何一个样本点y_i均可以确定一个超平面H_i:$a^T{y}_i=0$，其法向量为$y_i$。如果解向量$a^{\ast }$存在，即存在，即$(a^{\ast }{)}^T{y}_i>0$，显然，两者同向。

因此，根据两个的同向关系可以确定解空间。如下图 v 从图中可以直观地看出，解向量只要在解区内就能满足只要在解区内就能满足$(a^{\ast }{)}^{T}y>0$，但是这样的，但是这样的a^*有无穷多个，因此需要引入一个标准，来衡量有无穷多个，因此需要引入一个标准，来衡量$a^{\ast }$的好坏。

很自然地，我们认为令分类的错诶率最小的$a^{\ast }$为做好。即 $$\begin{gathered} L(a)=\sum _{y\in error}(-a^{T}y) \\ a=argmi{n}_{a}L(a) \end{gathered}$$ 下面就可以用最优化的理论对a进行求解了。

梯度下降算法

这里我们提供一种梯度下降算法

先对$L(a)$求偏导，得 $$\frac{\partial L(a)}{\partial a}=-\sum _{y\in error}y$$ 因此，a的更新原则为 $$a_{k+1}=a_k+{\eta }_k\sum _{y\in error}y$$ $a_{k+1}$是当前迭代的结果，$a_k$是前一次迭代的结果，${\eta }_k$是步长因子

一种特殊情况

​ 在应用的过程中，可能会遇到这样的问题：当a的初始值为0向量时，改变步长${\eta }_k$(固定值)对收敛的速度没有影响。

​ 原因：由齐次规范化增广样本的更新规则 $$a_{k+1}=a_k+{\eta }_k\sum _{y\in error}y$$ ​ 取两个不同的${\eta }_1,{\eta }_2$进行比较 $$\begin{gathered} a_1=0;a_1^{\prime }=0 \\ {a}_2={\eta }_1\sum _{y_{{\eta }_1}\in error}y;a_2^{\prime }={\eta }_2\sum _{y_{{\eta }_2}\in error}y \\ ... \end{gathered}$$ ​ 显然，两个不同$\eta$的错分样本空间始终相等，两者的权向量始终是同向的，而这一点成立的前提是:$a_1=a_1^{\prime }=0$

MSE多类扩展

针对C类问题，如果如果存在线性不可分的样本，可以考虑MES方法进行分类 $$y_i=W_i^{T}x+b_i$$ $y_i$表示数据x在第i类得到的值 $$y=W^{T}x+b$$ 则，y是一个包含C个值的列向量。

决策的准则是 $$result=argma{x}_i(y_i)$$ 构造$y_i=[0,...,0,1,0,...,0{]}^T$即，第i个元素为1，其余元素为0。比如：$y_i=[1,0,...,0]$

目标函数为均方误差 $$L(a)=\sum _{i=1}^n||(W^{T}x+b-y_i)|{|}_2^2$$ 因为y是一个包含C数的列向量，构造的y_i也是一个包含C个数的列向量，因此$W^{T}x+b-y_i$是一个列向量，其各个元素的平方和就是该向量二范数的平方。 $$let\{\begin{array}{l}\hat{W}=[W,b^T{]}^T\in R^{(d+1)\times c}\\ \hat{x}=[x,1{]}^T\in R^{d+1}\\ \hat{X}=(\widehat{x_1},\widehat{x_2},...,\widehat{x_n})\in R^{(d+1)\times n}\\ Y=[y_1,y_2,...,y_n],n=numberofsamples\end{array}$$ 可得 $$L(a)=||{\hat{W}}^T\hat{X}-Y|{|}_F^2$$ 因为 $$||A|{|}_F=(tr(A^{H}A){)}^{\frac{1}{2}}$$ 结合矩阵的求导公式可得 $$\frac{\partial L(a)}{\partial \hat{W}}=(\hat{X}{\hat{X}}^T{)}^{-1}\hat{X}{Y}^T$$ 由于L(a)是凸函数，因此其一阶零点一定是其最优解，即使误差最小的权重系数。