3.3.线性模型

    线性模型（Linear Model）是机器学习中最广泛的模型：

1. 给定一个$D$维样本$x = [x_1,...,x_D]^T$

2. 它的线性组合为$f(x;w) = w_1x_1 + w_2x_2 + ... + w_Dx_D + b = w^T x + b$

   1. $w = [w_1,...,w_D]^T$为$D$维的权重向量

   2. $b$为偏置项

    分类问题中，由于输出目标$y$是一些离散标签，而$f(x;w)$值域是实数，所以无法直接预测，需引入一个非线性决策函数（Decision Function）$g(\cdot)$来预测输出：

$y = g(f(x;w))$

    此处$f(x;w)$就称为判别函数（Discriminant Function），在二分类问题中，$g(\cdot)$可以是符号函数（Sign Function），定义为：

$g(f(x;w)) = sgn(f(x;w))$

$$\triangleq = \left\{ \begin{aligned} & +1, f(x;w) > 0 \\ & -1, f(x;w) < 0 \end{aligned} \right.$$

    二分类的线性模型如下：

    常用线性分类判别函数（损失函数不同）：

• Logistic回归

• Softmax回归

• 感知器

• 支持向量机

1.线性判别函数/决策边界

    一个线性分类模型（Linear Classification Model）或线性分类器（Linear Classifiter），是由一个（或多个）线性判别函数$f(x;w) = w^Tx + b$和非线性决策函数$g(\cdot)$组成。

1.1.二分类

    二分类（Binary Classification）问题的标签$y$只有两种值，通常设置为{+1,-1}或{1,0}，二分类中，常用正例（Positive Sample）和负例（Negative Sample）来表示两种样本。二分类问题中，我们只需要一个线性判别函数$f(x;w) = w^T x + b$，特征控件$R^D$中满足$f(x;w) = 0$组成一个分割超平面（Hyperplane），它称为决策边界（Decision Boundary）或决策平面（Decision Surface）。

    线性分类模型是指决策边界是线性超平面，在特征空间中，决策平面和权重向量$w$正交，特征空间中每个样本点到决策平面的有向距离（Signed Distance）为：

$\gamma = \frac{f(x;w)}{||w||}$

    给定$N$个样本训练集$D = \{(x_n,y_n)\}_{n=1}^N$，之中$y_n \in \{+1,-1\}$，线性模型视图学习到参数$w^?$，使得每个样本满足下边两个条件：

1. $f(x_n;w^?) > 0, y_n = 1$

2. $f(x_n;w^?) < 0, y_n = -1$

定义3.1——两类线性可分：对于训练集$D = \{(x_n,y_n)\}_{n=1}^N$，如果存在权重向量$w^?$，对所有样本都满足$yf(x;w^?) > 0$，那么训练集$D$是线性可分的。

    二分类问题，直接损失函数为0-1损失函数，其中$I(\cdot)$为指示函数，但0-1损失函数数学性质不好：

$L_{01}(y, f(x;w)) = I(y f(x;w) < 0)$

1.2.多分类

    多分类（Multi-class Classification）问题是指分类的类别数C大于2，多份类一般需要多个线性判别函数，但设计这样的函数有多种方式：

1. “一对其余”方式（OneVsRest）：把多分类问题转换为C个“一对其余”的二分类问题，这种情况需要C个判别函数，其中第c个判别函数$f_c$是将类别c的样本把类别i和类别j的样本分开。

2. “一对一”方式（OneVsOne）：把多份类问题转换为C(C -1)/2个“一对一”的二分类问题，这种方式需要C(C -1)/2个判别函数，其中第$(i,j)$个判别函数是把类别i和类别j的样本分开。

3. “argmax”方式：这是一种改进的“一对其余”的方式，共需要C个判别函数

   $f_c(x;w_c) = w_c^Tx + b_c, c \in \{1,...,C\}$ 对于样本$x$，如果存在一个类别c，相对于所有的其他类别$\widehat{c}(\widehat{c} \neq c)$有$f_c(x;w_c) > f_{\widehat{c}}(x,w_{\widehat{c}})$，那么此时$x$属于类别c，该方式的预测函数定义为： $y = arg \max\limits_{c=1}^C f_c(x; w_c)$

    前边两种都存在一个缺陷：特征空间中会存在一些难以确定类别的区域，而argmax方式很好解决了该问题。

定义3.2——多类线性可分：对于训练集$D = \{(x_n,y_n)\}_{n=1}^N$，如果存在$C$个权重向量$w_1^?,...,w_C^?$，使得第$c( 1 \le c \le C )$类的所有样本都满足$f_c(x;w_c^?) > f_{\widehat{c}}(x;w_{\widehat{c}}^?), \forall \widehat{c} \neq c$，那么训练集$D$是线性可分的。

2.Logistic回归

    Logistic回归（Logistic Regression, LR）是一种常用的二分类问题线性模型，为解决线性函数无法做分类的问题，引入非线性函数$g: R^D \rightarrow (0,1)$来预测类别标签的后验概率$p(y = 1|x)$.

$p(y = 1|x) = g(f(x;w))$

    其中$g(\cdot)$通常称为激活函数（Activation Function），其作用是把线性函数的值域从实数挤压到了$(0,1)$之间，可以用来表示概率，而$g(\cdot)$的逆函数$g^{-1}(\cdot)$称为链接函数（Link Function）

    Logistic回归中，使用Logistic作激活函数：

$p(y = 1|x) = \sigma(w^Tx) \triangleq \frac{1}{1 + \exp(-w^Tx)}$

• $x = [x_1,...,x_D,1]^T$为$D+1$维的增广特征向量。

• $w = [w_1,...,w_D,b]^T$为$D+1$维的增广权重向量。

    标签$y=0$的后验概率为

$p(y=0|x) = 1 - p(y = 1|x) = \frac{\exp(-w^Tx)}{1 + \exp(-w^Tx)}$

    上述公式变换之后得到：

$w^Tx = \log{\frac{p(y=1|x)}{1 - p(y=1|x)}} = \log{\frac{p(y=1|x)}{p(y=0|x)}}$

    该值为样本$x$为正反例的后验概率比值，称为几率（Odds），几率的对数称为对数几率（Log Odds，Logit），由于等号左边是线性函数，这样Logistic回归可以看做预测值为“标签的对数几率”的线性回归模型，因此Logistic回归也称为对数几率回归（Logit Regression）。

参数学习

    Logistic回归采用交叉熵作为损失函数，并使用梯度下降法来对参数进行优化。

    风险函数

$R(w) = -\frac{1}{N}\sum\limits_{n=1}^N(y_n \log{\hat(y_n)} + ( 1 - y_n)\log{(1 - \hat{y_n})})$

    Logistic回归训练过程：$w_0 \rightarrow 0$，然后通过下边方式迭代更新参数：

$w_{t+1} \leftarrow w_t + \alpha \frac{1}{N} \sum\limits_{n=1}^N x_n (y_n - \hat{y_n}_{w_t})$

• $\alpha$是学习率

• $\hat{y_n}_{w_t}$是当参数为$w_t$时，Logistic回归模型的输出

    风险函数$R(w)$是关于参数$w$的连续可导的凸函数，因此除了梯度下降法之外，Logistic回归还可使用高阶的优化方法（牛顿法）来进行优化。

3.Softmax回归

    Softmax回归（Softmax Regression），也称为多项（Multinomial）或多类（Multi-Class）的Logistic回归，是Logistic回归在多分类问题上的推广。对于多类问题，类别标签$y \in \{1,2,...,C\}$可以有C个取值，给定一个样本$x$。

• Softmax回归预测的属于类别c的条件概率为

  $p(y = c|x) = softmax(w_c^T x) = \frac{\exp(w_c^Tx)}{\sum_{c^{'} = 1}^C \exp(w_c^Tx)}$ 其中$w_c$是第c类的权重向量

• Softmax回归的决策函数可以表示为

  $\hat{y} = arg\max\limits_{c=1}^C p(y = c|x) = arg\max\limits_{c=1}^C w_c^T x$

    Logistic回归的关系：当类别C=2时，Softmax回归的决策函数为

$\hat{y} = arg\max\limits_{c=1}^C w_c^T x = I(w_1^Tx - w_0^Tx > 0) = I(w_1 - w_0)^T x > 0$

• 之中$I(\cdot)$是指示函数，二分类中的权重向量$w = w_1 - w_0$

    向量表示

$\hat{y} = softmax(W^T x) = \frac{\exp(W^Tx)}{1_C^T\exp(W^Tx)}$

参数学习

    给定$N$个训练样本$\{(x_n, y_n)\}_{n=1}^N$，Softmax回归使用交叉熵损失函数来学习最优的参数矩阵$W$。

    风险函数

$R(W) = -\frac{1}{N} \sum\limits_{n-1}^N (y_n)^T \log{\hat{y_n}}$

    风险函数关于$W$的梯度

$\frac{\partial R(W)}{\partial W} = - \frac{1}{N} \sum\limits_{n=1}^N x_n (y_n - \hat{y_n})^T$

略去证明过程。

    使用梯度下降法，Softmax回归的训练过程为：$w_0 \rightarrow 0$，然后通过下边式子迭代更新：

$W_{t+1} \rightarrow W_t + \alpha (\frac{1}{N}\sum\limits_{n=1}^N x_n (y_n - \hat{y_n}_{W_t})^T)$

• $\alpha$是学习率

• $\hat{y_n}_{w_t}$是当参数为$W_t$时，Softmax回归模型的输出

Softmax回归中使用的C个权重向量是冗余的，即对所有权重向量都减去一个同样的向量$v$，不改变其输出结果，因此，Softmax回归往往需要使用正规化来约束其参数，此外，我们还可利用这个特性来避免计算Softmax函数时在数值计算上溢出问题。

4.感知器

    感知器（Perceptron）是一种广泛的线性分类器，感知器是最简单的神经网络，只有一个神经元，感知器是对生物神经元的数学模拟

生物	神经网络
突触	权重
阈值	偏置
细胞体	激活函数

    感知机分类准则如下：

$\hat{y} = sgn(w^Tx)$

4.1.参数学习

    感知器学习算法也是一个经典的线性分类器的参数学习算法，给定$N$个样本训练集$\{(x_n,y_n)\}_{n=1}^N$，其中$y_n \in \{+1, -1\}$，感知机算法视图找到一组参数$w^?$，使得对于每个样本$(x_n, y_n)$有：

$y_n w^{?T}x_n > 0, \forall n \in \{1,...,N\}$

    感知器的学习算法是一种错误驱动的在线学习算法，先初始化一个权重$w \rightarrow 0$（通常是全零向量），然后每次分错一个样本$(x,y)$时，$y w^Tx < 0$，就用这个样本更新权重：

$w \rightarrow w + yx$

    损失函数

$L(w;x,y) = max(0, -yw^Tx)$

    更新梯度：

$$\frac{\partial L(w;x,y)}{\partial w} = \left\{ \begin{aligned} & 0, yw^T x > 0 \\ & -yx, yw^T x < 0 \end{aligned} \right.$$

4.2.感知器的收敛性

    收敛：

• 如果训练集是线性可分的，那么感知器算法可以在有限迭代后收敛。

• 如果训练集是线性不可分的，那么感知器算法则不能确保会收敛。

定理3.1——感知器收敛性：给定训练集$D = \{(x_n, y_n)\}_{n=1}^N$，令$R$是训练集中最大的特征向量的模，即$R = \underset{n}{max} || x_n ||$，如果训练集$D$线性可分，两类感知器的参数学习算法的权重更新次数不超过$\frac{R^2}{\gamma^2}$（证明方式略）。

    感知器的缺点：

1. 在数据集线性可分时，感知器虽然可以找到一个超平面把两类数据分开，但并不能保证其泛化能力。

2. 感知器对样本顺序比较敏感，每次迭代的顺序不一致时，找到的分割超平面也往往不一致。

3. 如果训练集不是线性可分的，就永远不会收敛。

4.3.参数平均感知器

    为了提高感知器的鲁棒性和泛化能力，我们可以将在感知器学习过程中的所有$K$个权重向量保存起来，并赋予每个权重向量$w_k$一个置信系数$c_k, (1 \le k \le K)$，最终的分类结果通过这$K$个不同权重的感知器投票觉得，这个模型称为投票感知器（Voted Perceptron）。

    投票感知器为:

$\hat{y} = sgn(\sum\limits_{k=1}^N c_k sgn(w_k^Tx))$

    其中$sgn(\cdot)$为符号函数，投票感知器虽然提高了感知器泛化能力，但需要保存$K$个权重向量，在实际操作中会带来额外开销，所以人们经常会使用一个简化版本，通过使用“参数平均”策略来减少投票感知器的参数数量，也称为平均感知器（Averaged Perceptron）。

4.4.扩展到多分类

    原始的感知器是一种二分类模型，但也很容易扩展到多分类问题；为了使感知器可处理更复杂的输出，此处引入一个构建在输入输出联合空间上的特征函数$\phi(x,y)$，将样本对$(x,y)$映射到一个特征空间向量。在联合特征空间中，可建立一个广义感知器模型：

$\hat{y} = arg \underset{y \in Gen(x)}{max} w^T \phi(x,y)$

• $w$为权重向量

• $Gen(x)$表示输入$x$所有的输出目标集合

4.4.1.广义感知器的收敛性

定义 3.3——广义线性可分：对于训练集$D = \{(x_n, y_n)\}_{n=1}^N$，如果存在一个正的常数$\gamma(\gamma > 0)$和权重向量$w^?$，并且$||w^?|| = 1$，对所有$n$都满足$(w^?, \phi(x_n,y_n)) - (w^?, \phi(x_n, y)) \ge \gamma, y \neq y_n(\phi(x_n,y_n) \in R^D$为样本$x_n, y_n$的联合特征向量），那么训练集$D$在联合特征向量空间中是线性可分的。

定理 3.2——广义感知器收敛性：如果训练集$D = \{(x_n, y_n)\}_{n=1}^N$是广义线性可分的，并令$R$是所有样本中真实标签和错误标签在特征空间$\phi(x,y)$最远的距离，即$R = \underset{n}{max} \underset{z \neq y_n}{max} ||\phi(x_n, y_n) - \phi(x_n, z)||$，那么广义感知器参数学习算法的权重更新次数不超过$\frac{R^2}{\gamma^2}$。

5.支持向量机

    支持向量机（Support Vector Machine, SVM）是一个经典二分类算法，其找到的分割超平面具有更好鲁棒性，因此广泛使用在很多任务上，表现很好的优势。给定一个二分类器数据集$D = \{(x_n, y_n)\}_{n=1}^N$，其中$y_n \in \{+1,-1\}$，如果两类样本是线性可分，则存在一个超平面：

$w^Tx + b = 0$

    将两类样本分开，那么对于每个样本都有$y_n(w^Tx_n + b) > 0$，那么每个样本到超平面的距离如：

$\gamma_n = \frac{w^Tx_n + b}{||w||} = \frac{y_n(w^T x_n + b)}{||w||}$

    如果定义间隔（Margin）$\gamma$为整个数据集$D$中所有样本到分割超平面的最短距离：$\gamma = \underset{n}{min} \gamma_n$，间隔越大，分割超平面对两个数据的划分越不稳定，不容易受到噪声等因素影响。支持向量机就是寻找一个超平面$(w^?,b^?)$使得$\gamma$最大，对于一个线性可分的数据集，其分割超平面有多个，但是间隔最大的超平面是唯一的。

4.1.参数学习

    为了找到最大分割超平面，目标函数如：

$\underset{w,b}{min} = \frac{1}{2}||w||^2$ $s.t. = 1 - y_n(w^Tx_n + b) \le 0, \forall n \in \{1,...,N\}$

    使用拉格朗日乘数法，上边公式的拉格朗日函数为：

$\land(w,b,\lambda) = \frac{1}{2}||w||^2 + \sum\limits_{n=1}^N \lambda_n(1 - y_n(w^Tx_n + b))$

    其中$\lambda_1 \ge 0, ..., \lambda_n \ge 0$为拉格朗日乘数，计算$\land(w,b,\lambda)$关于$w$和$b$的导数，令其为0，最终计算得到拉格朗日对偶函数：

$\Gamma(\lambda) = - \frac{1}{2}\sum\limits_{n=1}^N\sum\limits_{m=1}^N\lambda_m \lambda_n y_m y_n (x_m)^T x_n + \sum\limits_{n=1}^N \lambda_n$

    优化方法：序列最小优化（Sequential Minimal Optimization, SMO），支持向量集可通过SMO优化得到全局最优解，支持向量机的决策函数只依赖支持向量，与训练样本综合无关，分类速度比较快。

4.2.核函数

    支持向量机还有一个重要优点是可使用核函数（Kernel Function）隐式地将样本从原始特征空间映射到更高维的空间，并解决原始特征空间中的线性不可分的问题。支持向量机的决策函数如：

$f(x) = sng((w^?)^T \phi(x) - b^?) = sgn(\sum\limits_{n=1}^N \lambda_n^? y_n k(x_n, x) + b^?)$

    之中的$k(x,z) = \phi(x)^T \phi(z)$就是核函数，通常不需显示给出$\phi(x)$的具体形式，所以可构造一个核函数$k(x,z) = (1 + x^T z)^2 = \phi(x)^T \phi(z)$来隐式计算$x,z$在特征空间$\phi$中的内积，其中：

$\phi(x) = [1, \sqrt{2}x_1, \sqrt{2}x_2, \sqrt{2}x_1x_2, x_1^2, x_2^2]$

4.3.软间隔

    为了能容忍部分不满足约束的样本，可引入松弛变量（Slack Variable），将优化问题转换为：

$\underset{w,b}{min} = \frac{1}{n}||w||^2 + C \sum\limits_{n-1}^N \xi_n$

$s.t. = 1 - y_n (w^T x_n + b) - \xi_n \le 0, \forall n \in \{1,...,N\}$

$\xi_n \ge 0, \forall n \in \{1,...,N\}$

    参数$C > 0$用来控制间隔和松弛变量惩罚的平衡，引入松弛变量的间隔称为软间隔（Soft Margin），最终计算为：

$\underset{w,b}{min} = \sum\limits_{n=1}^N max(0, 1 - y_n(w^T x_n + b)) + \frac{1}{2C}||w||^2$

• $max(0, 1 - y_n(w^T x_n + b))$就是损失函数，称为Hinge损失函数（Hinge Loss Function）

• $\frac{1}{2C}||w||^2$是正则化项

• $\frac{1}{C}$是正则化系数

下边是对比结果

6.损失函数对比

• Logistic回归损失函数：

  $L_{LR} = \log(1 + \exp(-yf(x;w)))$

• 感知机损失函数：

  $L_p = \max(0, -yf(x;w))$

• 软间隔支持向量机的损失函数

  $L_{hinge} = \max(0, 1-yf(x;w))$

• 平均损失可重写为：

  $L_{squared} = (1 - yf(x;w))^2$

    对比表格

线性模型	激活函数	损失函数	优化方法
线性回归	-	$(y - w^Tx)^2$	最小二乘，梯度下降
Logistic回归	$\sigma(w^Tx)$	$y \log \sigma(w^Tx)$	梯度下降
Softmax回归	$softmax(W^Tx)$	$y \log softmax(W^Tx)$	梯度下降
感知器	$sgn(w^Tx)$	$\max(0, -yw^Tx)$	随机梯度下降
支持向量机	$sgn(w^Tx)$	$\max(0, 1-yw^Tx)$	二次规划，SMO等

一个或多个线性判别函数加上一个非线性激活函数，线性是指决策边界由一个或多个超平面组成。