第三章 线性模型（part1）

线性模型（LinearModel）是机器学习中应用最广泛的模型，指通过样本特征的线性组合来进行预测的模型:
$$f(\boldsymbol{x};\boldsymbol{\omega})=\boldsymbol{\omega}^{T}\boldsymbol{x}+b$$上一章中介绍的线性回归就是典型的线性模型，直接使用模型来预测输出结果。
而在分类问题中，输出目标是离散的标签，而模型的输出值域为实数，因此需要一个非线性的决策函数（Decision Function）$g(\cdot)$来预测输出目标:
$$y=g(f(\boldsymbol{x};\boldsymbol{\omega}))$$其中$y=g(f(\boldsymbol{x};\boldsymbol{\omega}))$也成为判别函数（DiscriminantFunction）。
对于二分类问题，$g(\cdot)$可以是符号函数（SignFunction），定义为：
$$g(f(\boldsymbol{x};\boldsymbol{\omega}))=sgn(f(\boldsymbol{x};\boldsymbol{\omega}))$$ $$=\begin{cases}+1&\text{ if } f(\boldsymbol{x};\boldsymbol{\omega})>0\\-1&\text{ if } f(\boldsymbol{x};\boldsymbol{\omega})<0\end{cases}$$当$f(\boldsymbol{x};\boldsymbol{\omega})=0$时不进行预测，这就是一个典型的二分类问题的决策函数，其结构如图所示：

3.1线性判别函数和决策边界

一个线性分类模型（Linear Classification Model）或线性分类器（Linear Classifier），是由一个（或多个）线性的判别函数和非线性的决策函数组成。

3.1.1二分类（Binary Classification）

该问题中类别标签𝑦只有两种取值，通常可以设为{+1,−1}或{0,1}．在二分类问题中，常用正例（PositiveSample）和负例（Negative Sample）来分别表示属于类别+1和−1的样本。在二分类问题中，我们只需要一个线性判别函数$f(\boldsymbol{x};\boldsymbol{\omega})=\boldsymbol{\omega}^{T}\boldsymbol{x}+b$使所有满足$f(\boldsymbol{x};\boldsymbol{\omega})=0$的点组成一个分割超平面（Hyperplane），称为决策边界（Decision Boundary）或决策平面（Decision Surface）。决策边界将特征空间一分为二，划分成两个区域，每个区域对应一个类别。
在特征空间中，决策平面与权重向量$\boldsymbol{\omega}$正交．特征空间中每个样本点到决策平面的有向距离（Signed Distance）为：
$$\gamma=\frac{f(\boldsymbol{x};\boldsymbol{\omega})}{\|\boldsymbol{\omega}\|} $$ 𝛾也可以看作点𝒙在𝒘方向上的投影。下图给出了一个二分类问题的线性决策边界示例，其中样本特征向量$\boldsymbol{x}=[x_{1},x_{2}] $，权重向量$\boldsymbol{\omega}=[\omega_{1},\omega_{2}]$:

因此，线性模型试图学习到参数$\omega^{*}$，使得决策平面尽量将不同类分到不同的区域如上图所示。（两类线性可分：如果对于训练集，存在一个权重向量，使得所有的样本都能分到正确的类别中，则称训练集是线性可分的）
为了学习参数$\boldsymbol{\omega}$，我们需要定义合适的损失函数以及优化方法．对于二分类问题，最直接的损失函数为0-1损失函数。但0-1损失函数的数学性质不好，其关于$\boldsymbol{\omega}$的导数为0，从而导致无法优化$\boldsymbol{\omega}$.

3.1.2多分类（Multi-class Classification）

该问题是指分类的类别数𝐶大于2．多分类一般需要多个线性判别函数，但设计这些判别函数有很多种方式，常用的方式有以下三种：
（1）“一对其余”方式：把多分类问题转换为$C$个“一对其余”的二分类问题．这种方式共需要$C$个判别函数，其中第$c$个判别函数$f_{c}$是将类别$c$的样本和不属于类别$c$的样本分开.
（2）“一对一”方式：把多分类问题转换为$C(C−1)/2$个“一对一”的二分类问题．这种方式共需要$C(C−1)/2$个判别函数，其中第$(i,j)$个判别函数是把类别$i$和类别$j$的样本分开.
（3）“argmax”方式：这是一种改进的“一对其余”方式，共需要$C$个判别函数:
$$f_{c}(\boldsymbol{x};\boldsymbol{\omega}_{c})=\boldsymbol{\omega}_{c}^{T}\boldsymbol{x}+b_{c}$$对于样本$\boldsymbol{x}$，如果存在一个类别$c$，相对于所有的其他类别$\tilde{c}(\tilde{c}\ne c)$使得$f_{c}(\boldsymbol{x};\boldsymbol{\omega}_{c})>f_{\tilde{c}}(\boldsymbol{x};\boldsymbol{\omega}_{\tilde{c}})$,那么$\boldsymbol{x}$属于类别$c$,该方式的预测函数定义为：
$$y=\text{arg}_{c=1}^{C}\max f_{c}(\boldsymbol{x};\boldsymbol{\omega}_{c})$$“一对其余”方式和“一对一”方式都存在一个缺陷：特征空间中会存在一些难以确定类别的区域，而“argmax”方式很好地解决了这个问题,如下图所示：

（多类线性可分：如果对于训练集，存在$C$个权重向量，使得所有的样本都能分到正确的类别中，则称训练集是线性可分的，根据上图，显然如果数据集是多类线性可分的，那么一定存在一个“argmax”方式的线性分类器可以将它们正确分开）