线性分类器

1 线性判别函数

判别函数：表示分类界面的函数 g(x)g(x)，Discriminant Function。

分类：不同的样本点散落在样本空间的不同位置。运用学习方法产生判别函数，定义若干个分类界面g(x)=0g(x)=0 ，将样本空间划分为一些互不重叠的区域。

线性可分：对于一组数据（样本点的集合），如果能用一个线性的判别函数正确分类，则称他们是线性可分的。反过来，如果一个样本集是线性可分的，则一定有一个线性分类器能正确分类该样本集。

1.1 通过样本直接确定判别函数

通过样本直接确定判别函数（分类器）的三要素为：

  • 确定判别函数的类型（线性？）
  • 确定判别函数设计的目标，准则
  • 设计算法，基于样本计算最优的判别函数参数。

即，有准则函数 L(α)L(\alpha)，求解一个特定的 α∗\alpha^* 使得

L(α∗)=argmin L(α),where α⊂ω，α是待定参数L(\alpha^*)=argmin\ L(\alpha), where\ \alpha\subset\omega，\alpha是待定参数

因此，设计判别函数的问题被转换为寻找准则函数极值的问题。对于任意的一个适合特定任务的准则函数，“尽可能好”的判别函数对应于准则函数取最优值时的情况。而准则函数的设计，应根据不同的具体情况设计。

综上，可以用最优化技术优化准则函数的取值，来解决分类问题。

1.2 线性判别函数的一般形式

g(x)=ωTx+w0, whereω∈Rd, ω=(ω1,ω2,...,ωd)为权值向量x∈Rd, x=(x1,x2,...,xd)为特征向量ω0 is bias, and d indicates dimensiong(x)=\omega^Tx+w_0,\ where\\ \omega\in R^d,\ \omega=(\omega_1,\omega_2,...,\omega_d) 为权值向量\\ x\in R^d,\ x=(x_1,x_2,...,x_d)为特征向量\\ \omega_0\ is\ bias,\ and\ d\ indicates\ dimension

增广形式（改造为齐次表达式）

g(x)=ωTx, whereω∈Rd+1, ω=(ω0,ω1,ω2,...,ωd)为增广的权值向量x∈Rd+1, x=(1,x1,x2,...,xd)为增广的特征向量g(x)=\omega^Tx,\ where\\ \omega\in R^{d+1},\ \omega=(\omega_0,\omega_1,\omega_2,...,\omega_d) 为增广的权值向量\\ x\in R^{d+1},\ x=(1,x_1,x_2,...,x_d)为增广的特征向量\\

1.3 线性判别函数的决策

g(x)={>0,if x∈ category 1<0,if x∈ category 2=0,otherwise (refuse)g(x) = \begin{cases} >0, & \text{if } x \in \text{ category 1} \\ <0, & \text{if } x \in \text{ category 2} \\ =0, & \text{otherwise (refuse)} \end{cases}

g(x)=0g(x)=0 定义了一个超平面方程，称为决策面。决策面将样本空间分为两个半平面。在上面的公式中，category 1category\ 1 位于决策面的正侧，category 2category\ 2 位于决策面的负侧。决策面的方向由法向量 ω\omega 确定，位置由 ω0\omega_0 确定。

线性判别函数可看作是样本到决策面距离的函数。

  • g(x)g(x) 正比于样本 xx 到超平面的有向距离。
  • ω0\omega_0 正比于原点到超平面的有向距离。

1.4 线性判别函数的多类决策问题

假设样本集是线性可分的，且有 m (m>2)m\ (m>2) 类，则需要定义多个线性判别函数，通常有三种方案：一对其余（One vs Rest, OvR），一对一（One vs One, OvO），多对多（Many vs Many, MvM）

1.4.1 一对其余 OvR

线性判别函数将属于 category icategory\ i 的样本与其余不属于该类的样本分开。判别规则数学表示为：

{gi(x)>0,then x∈category igi(x)<0,then x∉category iwhere i∈[1,m], gi(x) is the classification function of category i\begin{cases} g_i(x)>0,then\ x\in category\ i\\ g_i(x)<0,then\ x\notin category\ i\\ \end{cases} \\ where\ i\in[1,m],\ g_i(x)\ is\ the\ classification\ function\ of\ category\ i

在该判别方式下，若有多于一个的判别函数显示为大于0，或者所有判别函数都显示为小于0，则无法对样本进行正确的分类。

1.4.2 一对一 OvO

对任意两类都建立一个判别函数，用于将样本在这两类之间区分开。此函数对其他分类不提供信息，当有 mm 类需要分类时，共需要建立 m(m−1)2\frac{m(m-1)}{2} 个分类函数。判别规则数学表示为：

gij(x)>0, then x∈category iwhere j vary from 1 to m gij(x) indicates the classification function between category i and category ji, j∈[1,m], i≠jg_{ij}(x)>0,\ then\ x\in category \ i\\ where\ j\ vary\ from\ 1\ to\ m\\ \ g_{ij}(x)\ indicates \ the\ classification\ function\ between\ category\ i\ and\ category\ j\\ i,\ j\in[1,m],\ i≠j

在该判别方式下，判别空间中同样可能存在不确定区域。

1.4.3 多对多 MvM

对 mm 类问题定义 mm 个判别函数 gi, i∈[1,m]g_i,\ i\in[1,m]

判别规则为：

gi(x)>gj(x), then x∈category iwhere j vary from 1 to m, j≠ig_i(x)>g_j(x),\ then\ x\in category\ i\\ where\ j\ vary\ from\ 1\ to\ m,\ j≠i

对任意的两个分类，之间的一对一分类平面为 gi(x)=gj(x)g_i(x)=g_j(x)

在该判别方式下，决策空间中不存在不确定区域。

2 最小距离准则

2.1 最小欧氏距离准则

在 nn 维空间中，两个向量之间的欧氏距离 dd 定义为:

d2=(x−y)T(x−y), wherex=(x1,x2,...,xn)T, y=(y1,y2,...,yn)Td^2=(x-y)^T(x-y),\ where\\ x=(x_1,x_2,...,x_n)^T,\ y=(y_1,y_2,...,y_n)^T

断言：同类样本在样本空间中应该互相靠近（降低类内距离），不同类样本在样本空间中应该相互远离（提高类间距离），因此可以用距离最小准则来设计分类器。

定义样本 xx 到 category icategory\ i 的距离为：

Di(x)=(x−μi)T(x−μi), where μi is the average of samples of category iD_i(x)=(x-\mu_i)^T(x-\mu_i),\ where\ \mu_i\ is\ the\ average\ of\ samples\ of\ category\ i

按距离最小准则，定义决策规则为：

Di(x)<Dj(x), then x∈category i, where j vary from 1 to m, j≠iD_i(x)<D_j(x),\ then\ x\in category\ i,\ where\ j\ vary\ from\ 1\ to\ m,\ j≠i

对样本到类 ii 的表达式进行展开：

Di(x)=(x−μi)T(x−μi)=xTx−2μiTx+μiTμilet gi(x)=2μiTx−μiTμiD_i(x)=(x-\mu_i)^T(x-\mu_i)=x^Tx-2\mu_i^Tx+\mu_i^T\mu_i\\ let\ g_i(x)=2\mu_i^Tx-\mu_i^T\mu_i

显然，gi(x)g_i(x) 是一个线性判别函数。最小距离分类器实质上是线性分类器。

3 感知器准则

建立感知器准则的目的，是寻找一个通用的训练方法，以求解线性分类器的权重向量，使其逐渐收敛于最优解区域。

3.1 几个基本概念

定义增广的样本集为 yi{y_i}，如果样本集线性可分，则一定存在一个权值向量 ω\omega 能正确分类该样本集，称为解向量。

如果样本集是线性可分的，对判别结果小于0（属于 category 2category\ 2）的样本向量取反，使所有的规范后样本 yi′y_i^{'} 的判别函数结果均大于0，称为样本的规范化，称这样的样本 yi′y_i^{'} 为规范化增广样本向量。

在线性可分的情况下，方程 ωTyi=0\omega^Ty_i=0 确定了一个以 yiy_i 为法向量的超平面。解向量若存在，必在所有样本确定的正半空间的交叠区，称为解区

为使解区更加可靠，引入余量 bb，寻找满足 ωTyi>b\omega^Ty_i>b 的解向量。引入余量的目的是使解向量不在解区的边界点上，使解向量能更好的对未见样本进行正确分类。

3.2 感知器准则函数

考虑线性可分问题的算法。

设 YeY_e 表示（在一次分类中）被权值向量错误分类的样本集。根据上文的定于，对任意错误分类的样本 yy，应有 ωTyi<0\omega^Ty_i<0。构造准则函数如下：

J(ω)=∑y∈Ye(−ωTyi)J(\omega)=\sum\limits_{y\in Y^e}(-\omega^Ty_i)

可知，准则函数 J(ω)J(\omega) 总是大于等于 0，当且仅当权值向量落在解区边界上时，ωTyi\omega^Ty_i 等于0。因此，寻找解向量的问题转化为寻找准则函数 ωTyi\omega^Ty_i 最小值的问题。

考虑使用梯度下降方法求解，求解准则函数的梯度如下：

∇J(ω)=∂J(ω)∂ω=∑y∈Ye(−y)\nabla J(\omega)=\frac{\partial J(\omega)}{\partial\omega}=\sum\limits_{y\in Y^e}(-y)

可得梯度下降法的迭代公式为：

ωstep+1=ωstep+αstep∑y∈Ye(−y)\omega^{step+1}=\omega^{step}+\alpha_{step}\sum\limits_{y\in Y^e}(-y)

在实际执行该梯度下降方法时，有如下若干方法：

  • 批修正法：在每次迭代中，用所有错分样本更新权值。
  • 单样本修正法：在每次迭代中，考虑一个样本。如果该样本被错分，更新一次权值。
  • 固定增量发：固定每个step中的 αstep\alpha_{step} 不变。

4 最小平方误差准则

用于解决感知器准则不能解决的线性不可分问题。

设 yiy_i 为规范化增广样本，ω\omega 为增广权值向量。

写成向量形式，有：

Yω=b, where Y=[y1Ty2T⋮ynT], b=[b1b2⋮bn]Y\omega=b,\ where\ Y= \left[ \begin{array}{c} y_1^T \\ y_2^T \\ \vdots \\ y_n^T \end{array} \right],\ b= \left[ \begin{array}{c} b_1 \\ b_2 \\ \vdots \\ b_n \end{array} \right]

定义一个误差向量 e=Yω−be=Y\omega-b ，因此有平方误差准则函数：

J(ω)=∣∣e∣∣2=∑k=1n(ωTyk−bk)2J(\omega)=||e||^2=\sum\limits^{n}_{k=1}(\omega^Ty_k-b_k)^2

得梯度：

∇J(ω)=∑k=1n2(ωTyk−bk)yk=2YT(Yω−b)\nabla J(\omega)=\sum\limits^{n}_{k=1}2(\omega^Ty_k-b_k)y_k=2Y^T(Y\omega-b)

Widrow-Hoff 算法

梯度算法可以写成：

{ω1=任意值ωk+1=ωk−αkYT(Yω−b)\begin{cases} \omega^1=任意值\\ \omega^{k+1}=\omega^k-\alpha_k Y^T(Y\omega-b) \end{cases}

可以证明，如果选择 αk=α1/k, α1\alpha_k=\alpha_1/k,\ \alpha_1 取任意值，则该算法得到的权向量序列收敛于解向量。