Linear Models for Classification

  与回归模型的是它的预测结果是一个离散变量。
  我们讨论的大多数分类问题类别都是不相交的，即一个样本只有一个类别。输入空间可以被划分成若干个决策区域，其边界称为决策边界(decision boundaries or decision surfaces)。标题中所谓的线性模型就是指决策边界是输入变量的线性函数。可以被线性的决策边界成功分类的问题称为线性可分的。
  在分类问题中，目标变量$t$t的表示形式有多种。例如二分类问题$t\in\{0,1\}$t∈{0,1}，0代表类别$C_1$C1​，1代表类别$C_2$C2​。概率模型中，t可以被解释为该样本属于$C_1$C1​的概率。多分类问题，t往往被表示为形式如$\mathbf{t}=(0,0,1)^T$t=(0,0,1)T的向量，其中只有一个分量为1，表示样本属于$C_k$Ck​

判别函数 Discriminant Functions

讨论线性判别式模型，解决分类问题。几何上等价于，找一个决策平面（超平面）将不同类别的样本分开。从易到难，首先讨论二分类问题。

二分类问题

$y(\mathbf{x})=\mathbf{w}^T\mathbf{x}+w_0$y(x)=wTx+w0​
若$y(x)\ge 0$y(x)≥0则样本分类成$C_1$C1​类，否则为$C_2$C2​类，决策边界为$\mathbf{w}^T\mathbf{x}+w_0=0$wTx+w0​=0

可以看出向量$\mathbf{w}$w垂直于决策平面，样本到决策平面的距离
$r=\frac{y(x)}{\rVert \mathbf{w}\lVert}$r=∥w∥y(x)​

这里留一个疑问，如何利用训练集去估计参数

多分类问题

刚刚学习了二分类问题，一个直接的想法是使用$k-1$k−1个二分类分离器解决K分类问题，这个分类器被称为one-versus-the-rest classifier，他会有模糊区域如图

另一个简单的想法是使用$\frac{K(K-1)}{2}$2K(K−1)​个二分类器，用两条线为每一个类划分一个区域，这个分类器被称为one-versus-one classifier

第三种想法是K个线性分类器，如下
$y_k(\mathbf{x})=w^{T}_{k}x+w_{k0}$yk​(x)=wkT​x+wk0​
x被预测为$C_{k}$Ck​如果$y_{k}(x)>y_{j}(x)$yk​(x)>yj​(x)对于任意的$j\ne k$j​=k
可以证明被如此方法划分出来的决策区间是凸的。
假设$x_{1},x_{2}\in \mathcal R_{k}$x1​,x2​∈Rk​,则
$\hat{x} = \lambda x_{1}+(1-\lambda)x_{2} w_{k}^{T}\hat{x}+w_{k0}\le w_{k}^{T}(\lambda x_{1}+(1-\lambda)x_{2})+w_{k0}\\ \le \lambda (w_{j}^{T}x_{1}+w_{j0}) + (1-\lambda) (w_{j}^{T}x_{2}+w_{j0}),\forall j\ne k$x^=λx1​+(1−λ)x2​wkT​x^+wk0​≤wkT​(λx1​+(1−λ)x2​)+wk0​≤λ(wjT​x1​+wj0​)+(1−λ)(wjT​x2​+wj0​),∀j​=k

之后讲三种训练模型的方法，分别基于最小二乘，Fisher和感知机

Least Square for Classification

在这里，我们陈述使用最小二乘法解决多酚类问题的方法。在上所说的三种分类策略中，第三种用于实际的分类问题，但需要换一种更为简洁的表达方式
$\mathbf{y}(\mathbf{x})=\tilde{W}^{T}\tilde{x}\\$y(x)=W~Tx~
其中$\tilde{W}$W~的列向量$\tilde{w_k}=(w_{k0},w_{k}^{T})^{T}$wk​~​=(wk0​,wkT​)T，$\tilde{x}=(1,x^{T})^{T}$x~=(1,xT)T。x的最终类别就是$\tilde{w_k}^{T}\tilde{x}$wk​~​Tx~最大的那一类

那么现在我们需要找到一个参数矩阵$\tilde{W}$W~使得二次损失函数最小
$E_D(\tilde{W})=\frac{1}{2}Tr((\tilde{X}\tilde{W}-T)^{T}(\tilde{X}\tilde{W}-T))$ED​(W~)=21​Tr((X~W~−T)T(X~W~−T))
可以求得
$\tilde{W}=(\tilde{X}^{T}\tilde{X})^{-1}\tilde{X}^{T}T=\tilde{X}^{\dagger}T$W~=(X~TX~)−1X~TT=X~†T
就这样，我们容易的求出判别模型的解析解
$\mathbf{y}(\mathbf{x})=\widetilde{\mathbf{W}}^{\mathrm{T}} \widetilde{\mathbf{x}}=\mathbf{T}^{\mathrm{T}}\left(\widetilde{\mathbf{X}}^{\dagger}\right)^{\mathrm{T}} \widetilde{\mathbf{x}}$y(x)=WTx=TT(X†)Tx