线性模型.md

线性模型

线性模型既可以做回归，也可以做分类问题，由于输出目标y是一些离散的标签，而$f(x;w)$值域为实数，因此无法直接用$f(x;w)$来预测，需要引入决策函数来预测输出目标。 $$ y=g(f(x;w)) $$ 对于二分类问题，$g(\cdot)$是符号函数，定义为： $$ \begin{aligned} g(f(x;w))&=sgn(f(x;w)) \end{aligned} $$

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

1.1 二分类

• 二分类：通常标签只有两种取值，通常设为{+1,-1}或{0,1}，通常用正例和负例分别表示属于+1和-1的样本

  在二分类问题中，我们通常只需要一个线性判别函数$f(x;w)=w^Tx+b$。特征空间$R^D$中所有满足$f(x;w)=0$的点组成一个分割超平面，称为决策边界或决策平面。决策边界将特征空间一分为二，划分成两个区域，每个区域一个类别

  所谓现行分类模型就是指决策边界是线性超平面。在特征空间中，决策平面与权重向量w正交。特征空间中每个样本点到决策平面的有向距离为： $$ \gamma=\frac{f(x;w)}{||w||} $$ $\gamma$也可以看做点x在w方向上的投影。

• 多分类：指问题分类的类别数C大于2，多分类一般需要多个线性判别函数，但设计这些判别函数有多重方式

  • “一对其余”方式：把分类问题转换成C个“一对其余”的二分类问题，这种方式需要C个判别函数，其中第c个判别函数$f_c$是将类别c的样本和不属于类别c的样本分开
  • “一对一”方式：把多分类问题转换成C(C-1)/2个“一对一”的二分类问题，这种方式共需要C(C-1)/2个判别函数，其中第(i,j)判别函数是把类别i和类别j的样本分开
  • “argmax”方式：这是一种改进的“一对其余”的方式，共需C个判别函数

  $$ f_c(x;w)=w_c^Tx+b_c, c\in{1,...,C} $$

  ​ 对于样本x，如果存在一个类别c相对于其他所有类别$\hat{c}(\hat{c}\not=c)$有$f_c(x;w_c)>f_{\hat{c}(x,w_{\hat{c}})}$，那么x属于类别c，argmax方式的预测函数定义为： $$ y=\mathop {argmin}_{c_k}^Cf_c(x;w_c) $$ “一对其余”方式和“一对一”方式都存在一个缺陷：特征空间中会存在一些难以确定类别的区域，而“argmax”方式很好地解决了这个问题。

2.逻辑回归

​ 为了解决连续的线性函数不适合分类的问题，我们引入了非线性函数g：$R^D\rightarrow (0,1)$来预测后验概率$p(y=1|x)$ $$ p(y=1|x)=g(f(x;w)) $$ ​ 其中$g(\cdot)$通常被称为激活函数。

​ 在Logistic回归中通常用Logistic函数作为激活函数，标签y=1的后验概率为： $$ p(y=1|x)=\sigma(w^Tx)\triangleq\frac{1}{1+exp(-w^Tx)} $$

$$ 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)} $$ ​ 其中$\frac{p(y=1|x)}{p(y=0|x)}$为样本x正反例后验概率的比值，称为几率，几率的对数称为对数几率，因此逻辑回归也被叫做对数几率回归。

​ 逻辑回归采用交叉熵作为损失函数，并使用梯度下降算法进行优化。给定N个训练样本${x^{(n)},y^{(n)}}{n=1}^N$，用逻辑回归模型对每个样本$x^{(n)}$进行预测，输出其标签为1的后验概率，记为$\hat{y}^{(n)}$： $$ \hat{y}^{(n)}=\sigma(w^Tx^{(n)}),1\leq n\leq N $$ ​ 由于$y^{(n)}\in(0,1)$，样本的真实条件概率分布为： $$ p_r(y^{(n)}=1|x^{(n)})=y^{(n)}\ p_r(y^{(n)}=0|x^{(n)})=1-y^{(n)} $$ ​ 使用交叉熵损失函数，其风险函数为： $$ \begin{aligned} R(w)&=-\frac{1}{N}\sum{n=1}^N(p_r(y^{(n)=1}|x^{(n)})\log \hat{y}^{(n)}+p_r(y^{(n)=0}|x^{(n)})\log \hat{1-y}^{(n)})\ &=-\frac{1}{N}\sum_{n=1}^N(y^{(n)}\log \hat{y}^{(n)}+(1-y^{(n)})\log (1-\hat{y}^{(n)})) \end{aligned} $$ ​ 风险函数R(w)关于参数w的偏导数为： $$ \begin{aligned} \frac{\partial R(w)}{\partial w}&=-\frac{1}{N}\sum_{n=1}^N(y^{(n)}\frac{\hat{y}^{(n)}(1-\hat{y}^{(n)})}{\hat{y}^{(n)}}x^{(n)}-(1-y^{(n)})\frac{\hat{y}^{(n)}(1-\hat{y}^{(n)})}{1-\hat{y}^{(n)}}x^{(n)})\ &=-\frac{1}{N}\sum_{n=1}^N(y^{(n)}(1-\hat{y}^{(n)})x^{(n)}-(1-y^{(n)})\hat{y}^{(n)}x^{(n)})\ &=-\frac{1}{N}x^{(n)}(y^{(n)}-\hat{y}^{(n)}) \end{aligned} $$ ​ 通过梯度下降法可以学习到参数w，也可以用高阶的优化方法（如：牛顿法）

3.Softmax回归

​ softmax回归是Logistic回归在多分类问题下的推广，对于多分类问题，类别标签$y\in {1,2,...,C}$可以有C个取值，给定一个样本x，softmax回归预测属于类别c的条件概率为： $$ p(y=c|x)=\frac{exp(w_c^Tx)}{\sum_{c'=1}^{C}exp(w_{c'}^Tx)} $$ ​ 其中$w_c$是第c类的权重。

​ Softmax回归的决策函数可以表示为： $$ \begin{aligned} \hat{y}&=\mathop {argmin}{c=1}^C p(y=c|x)\ &=\mathop {argmin}{c=1}^Cw_c^Tx \end{aligned} $$ ​ 与Logistic回归的关系：当类别C=2时u，softmax回归的决策为： $$ \begin{aligned} \hat{y}&=\mathop {argmin}{y\in (0,1)}w_y^Tx\ &=I(w_1^Tx-w_0^Tx>0)\ &=I((w_1^T-w_0^T)x>0) \end{aligned} $$ ​ 参数学习：给定N个训练样本${x^{(n)}, y^{(n)}}{n=1}^N$，为了方便起见，用C维的one-hot向量$y\in{0,1}^C$表示来表示类别标签，对于类别c其向量为： $$ y=[I(1=c), I(2=c), ..., I(C=c)] $$ ​ 采用交叉熵损失函数，softmax回归的风险函数为： $$ \begin{aligned} R(W)&=-\frac{1}{N}\sum_{n=1}^N\sum_{c=1}^Cy_c^{(n)}\log \hat{y}c^{(n)}\ &=-\frac{1}{N}\sum{n=1}^N(y^{(n)})^T\log \hat{y}^{(n)} \end{aligned} $$ ​ 其中$\hat{y}^{(n)}=softmax(W^Tx^{(n)})$为样本$x^{(n)}$在每个类别的后验概率：

​ 风险函数$R(W)$关于W的梯度为： $$ \begin{aligned} \frac{\partial R(W)}{\partial W}&=-\frac{1}{N}\sum_{n=1}^Nx^{(n)}(y^{(n)}-\hat{y}^{(n)})^T \end{aligned} $$ ​ 证明：

​ 先引入两个结论： $$ \begin{aligned} &(1).若y=softmax(z)，则\frac{\partial y}{\partial z}=diag(y)-yy^T\ &(2).若z=W^Tx=[w_1^Tx, w_2^Tx, ..., w_C^Tx]^T，则\frac{\partial z}{\partial w_c}为第c列为x，其余为0的矩阵\ \end{aligned} $$

$$ \begin{aligned} \frac{\partial z}{\partial w_c}&=[\frac{\partial w_1^Tx}{\partial w_c}, \frac{\partial w_2^Tx}{\partial w_c},...,\frac{\partial w_C^Tx}{\partial w_c}]\\ &=[0,0,...,x,...,0]\\ &\triangleq M_c(x) \end{aligned} $$

​ 根据链式法则，$L^{(n)}(W)=-(y^{(n)})^T\log \hat{y}^{(n)}$关于$w_c$的偏导数为： $$ \begin{aligned} \frac{\partial L^{(n)}(W)}{\partial w_c}&=-\frac{\partial ((y^{(n)})^T\log \hat{y}^{(n)})}{\partial w_c}\ &=-\frac{\partial z^{(n)}}{\partial w_c}\frac{\partial y^{(n)}}{\partial z^{(n)}}\frac{\partial \log \hat{y}^{(n)}}{\partial \hat{y}^{(n)}}y^{(n)}\ &=-M_c(x^{(n)})(diag(\hat{y}^{(n)}-\hat{y}^{(n)}(\hat{y}^{(n)})^T)(diag(\hat{y}^{(n)})^{-1}y^{(n)})\ &=-M_c(x^{(n)})(I-\hat{y}^{(n)}1^T_C)y^{(n)}\ &=-M_c(x^{(n)})(y^{(n)}-\hat{y}^{(n)}1^T_Cy^{(n)})(1^T_Cy^{(n)}=1)\ &=-M_c(x^{(n)})(y^{(n)}-\hat{y}^{(n)})\ &=-x^{n}[y^{(n)}-\hat{y}^{(n)}]_c \end{aligned} $$ ​ 证毕.。

​ 计算技巧：softmax需要计算指数exp，而指数稍大一点或者稍小一点时很容易溢出，因此需要一些计算技巧来避免计算溢出。

4.支持向量机

• 给定一个二分类数据集$D={(x^{(n)}, y^{(n)}}_{n=1}^N$，其中$y^{(n)}\in {+1,-1}$，如果两类样本是线性可分的，即存在一个超平面： $$ w^Tx+b=0 $$ 将两类样本分开，那么对于每个样本都有$y^{(n)}(w^Tx^{(n)}+b)>0$

  数据集中每个样本$X^{(n)}$到分割超平面的距离为： $$ y^{(n)}=\frac{|w^Tx+b|}{||w||}=\frac{y^{(n)}(w^Tx^{(n)}+b)}{||w||} $$ 我们定义间隔$\gamma$为整个数据集D中所有样本到分割超平面最短的距离： $$ \gamma = \min_n \gamma^{(n)} $$ 如果间隔$\gamma$越大，其分割超平面对两个数据集的划分越稳定，不容易受噪声等因素影响，支持向量机的目标是寻找一个超平面$(w^,b^)$使得$\gamma$最大，即： $$ \max_{w,b} \qquad \gamma\ s.t. \qquad\frac{y^{(n)}(w^Tx^{(n)}+b)}{||w||}\geq \gamma $$ 超平面：$w^Tx+b=0$

  • 超平面的参数等比例放缩不会改变超平面，如：$[1, 2]^Tx+2=0$和$[2,4]^Tx+4=0$表示的是同一条直线x+2y+2=0

  函数间隔：$\hat{\gamma}^{(n}) = y^{(n)}(w^Tx^{(n)}+b)$

  几何间隔：$\frac{|w^Tx^{(n)}+b|}{||w||}=\frac{y^{(n)}(w^Tx^{(n)}+b)}{||w||}$

  • 在给定的超平面下，前面提到，同等比例改变超平面参数仍是原来的超平面，那么同比例改变参数可以使得函数间隔为$\frac{1}{||w||}$不会影响这个超平面 $$ \gamma =\frac{1}{||w'||^2} $$

  • $\frac{1}{||w||}^2$还是不好优化，那么我们的目标是最大化最小的几何间隔，等价于最小化$||w||^2$

  原问题等价于： $$ \min_{w,b}\qquad \frac{1}{2}||w||^2\ s.t.\qquad y^{(n)}(w^Tx^{(n)}+b)\geq 1 $$

• 求解方式： $$ \min_{w,b}\qquad \frac{1}{2}||w||^2\ s.t.\qquad y^{(n)}(w^Tx^{(n)}+b)\geq 1 $$ 使用拉格朗日乘数法： $$ \nu(w,b,\lambda)=\frac{1}{2}||w||^2+\sum_{n=1}^N\lambda_n(1-y^{(n)}(w^Tx^{(n)}+b))\ \begin{aligned} \frac{\partial \nu}{\partial w}&=w+\sum_{n=1}^N\lambda_n(-y^{(n)}x^{(n)})\ \frac{\partial \nu}{\partial b}&=\sum_{n=1}^N\lambda_n(-y^{(n)})\ \end{aligned} $$ 这里利用拉格朗日对偶求解，分别令两个偏导为0得： $$ \begin{aligned} w&=\sum_{n=1}^N\lambda_ny^{(n)}x^{(n)}\ 0&=\sum_{n=1}^N\lambda_ny^{(n)} \end{aligned} $$ 将上面的参数代入到原方程中得，也就是求$\min_{w,b}\nu(w,b,\lambda)$： $$ \begin{aligned} \nu(w, b, \lambda)&=\frac{1}{2}\sum_{n=1}^N\sum_{m=1}^N\lambda_n\lambda_my^{(n)}y^{(m)}(x^{(n)})^Tx^{(m)}+\sum_{n=1}^N\lambda_n-\sum_{n=1}^N\sum_{m=1}^N\lambda_n\lambda_my^{(n)}y^{(m)}(x^{(n)})^Tx^{(m)}+b\sum_{n=1}^N\lambda_ny^{(n)}\ &=-\frac{1}{2}\sum_{n=1}^N\sum_{m=1}^N\lambda_n\lambda_my^{(n)}y^{(m)}(x^{(n)})^Tx^{(m)}+\sum_{n=1}^N\lambda_n \end{aligned} $$

  根据对偶问题，然后再求解最大值问题即与原问题等价： $$ \begin{aligned} &\max_\lambda \qquad -\frac{1}{2}\sum_{n=1}^N\sum_{m=1}^N\lambda_n\lambda_my^{(n)}y^{(m)}(x^{(n)})^Tx^{(m)}+\sum_{n=1}^N\lambda_n\ &s.t.\qquad \sum_{n=1}^N\lambda_ny^{(n)}=0,\lambda_i\geq0 \end{aligned} $$ 把最大化问题转化成最小化问题： $$ \begin{aligned} &\min_\lambda \qquad \frac{1}{2}\sum_{n=1}^N\sum_{m=1}^N\lambda_n\lambda_my^{(n)}y^{(m)}(x^{(n)})^Tx^{(m)}-\sum_{n=1}^N\lambda_n\ &s.t.\qquad \sum_{n=1}^N\lambda_ny^{(n)}=0,\lambda_i\geq0 \end{aligned} $$ 根据KKT条件中的互补松弛条件，最优解满足：$\lambda_n^(1-y^{(n)}((w^T)^x^{(n)}+b^))$，如果样本不在约束边界上，$\lambda_n^=0$；如果在边界上，$\lambda_n^*\geq0$，这些样本点称为支持向量，即里决策平面最近的点。在决定分离超平面时只有支持向量在起作用，其他实例点不起作用，与训练样本总数无关，分类速度较快。

• 核函数： $$ K(x, z) = (1+x^Tz)^2=\Phi(x)^T\Phi(z) $$ 其中$\Phi(x)$的作用是将m维的向量x映射到更高维n，上面的核函数对应的$\Phi(x)$为：$\Phi(x)=[1, \sqrt{2}x_1, \sqrt{2}x_2, \sqrt{2}x_1x_2, x_1^2, x_2^2]$

• 软间隔：假设数据是线性不可分的，训练数据中有一些特异点，去除这些点之后剩下的点都是线性可分的。我们可以在原有最小间隔的情况下，增加一个松弛变量，扩宽一下间隔使得少部分点可以不满足限制条件，所以优化目标成了：

  $$ \min_{w}\qquad \frac{1}{2}||w||^2+C\sum_{n=1}^N\epsilon_n\ s.t.\qquad 1-y^{(n)}(w^Tx^{(n)}+b)-\epsilon_n\leq0\ \epsilon_n\geq0 $$ 上面的公式也可以写成风险+正则化的形式： $$ \min_{w,b}\sum_{n=1}^N\max (0, 1-y^{(n)}(w^Tx^{(n)}+b))+\lambda||w||^2 $$ 证明：

  定义取正值函数为： $$ [z]+=\left{\begin{aligned}&z,\qquad z>0\&0,\qquad z\leq 0\end{aligned}\right. $$ 将$1-y^{(n)}(w^Tx^{(n)}+b)-\epsilon_n\leq0$改写：令$[1-y^{(n)}(w^Tx^{(n)}+b)]+=\epsilon_n$

  首先这里的$\epsilon_n\geq0$，其次当$1-y^{(n)}(w^Tx^{(n)}+b)>0$时有：$1-y^{(n)}(w^Tx^{(n)}+b)>\epsilon_n$，即$y^{(n)}(w^Tx^{(n)}+b)=1-\epsilon_n$；而当$1-y^{(n)}(w^Tx^{(n)}+b)\leq0$时，有：$\epsilon_n=0$，即$y^{(n)}(w^Tx^{(n)}+b)\geq 1-\epsilon_n$

  故式子的改写成立。代入到上面风险+正则化的式子中： $$ \min_{w,b}\sum_{n=1}^N\epsilon_n+\lambda||w||^2 $$ 取$\lambda=\frac{1}{C}$，那么上面的式子为： $$ \min_{w,b}\frac{1}{C}(\frac{1}{2}||w||^2+C\sum_{n=1}^N\epsilon_n) $$ 其中$\max (0, 1-y^{(n)}(w^Tx^{(n)}+b))$就是支持向量机的损失函数