机器学习——线性模型（内附详细公式推导）
机器学习——线性模型（内附详细公式推导）
一、基本形式
给定由d个属性描述的示例$\bm x=(x_1;x_2;…;x_d)$，其中$x_i$是$\bm x$在第i个属性上的取值，线性模型（linear model）是一个通过属性的线性组合来进行预测的函数，即
$$f( \bm x)=w_1x_1+w_2x_2+……+w_dx_d+b$$
一般用向量形式写成
$$f( \bm x)=\bm {W^TX} +b$$
其中，$\bm w=(w_1;w_2;…;w_d)$。$\bm w$和$b$学得之后，模型就得以确定。
线性模型的优点
- 简单
- 基本
- 可理解性好（$\bm w$直观表达了各属性在预测中的重要性）
二、线性回归
给定数据集$D= \left{ \begin{matrix} (\bm x_1,y_1),(\bm x_2,y_2),…,(\bm x_m,y_m)\end{matrix} \right}$，线性回归试图学得一个线性模型以尽可能准确地预测实值输出标记。
$$f(\bm x_i)=\bm w\bm x_i+b \qquad 使得f(\bm xi) \approx y_i$$
若属性值间存在“序”关系，可通过连续化将其转化为连续值，例如二值属性“身高”的取值“高” “矮”可转化为{1.0,0.0}，三值属性“高度”的取值“高” “中” “低”可转化为{1.0,0.5,0.0}；若属性值间不存在序关系。假定有k个属性值，则通常转化为k维向量，例如属性“瓜类”的取值“西瓜” “南瓜” “黄瓜”可转化为(0,0,1),(0,1,0),(1,0,0)
离散属性的处理
- 有序$\Rightarrow$连续化
- 无序$\Rightarrow$转为k维向量
若将无序属性连续化，则会不恰当地引入序关系，对后续处理如距离计算等造成误导.
如何确定$\bm w$和$b$，关键在于衡量$f(x)$与$y$之间的差别。均方误差是回归任务中最常用的性能度量，因此尽量让均方误差最小化。
$$(w^*,b^ *)= \arg \mathop{\min}\limits_{(w,b)} \sum_{i=1}^m(f(x_i)-y_i)^2 \ =\arg \mathop{\min} \limits_{(w,b)} \sum_{i=1}^m(y_i-wx_i-b)^2$$
均方误差具有非常好的几何意义，它对应了欧几里得距离。基于均方误差最小化来进行模型求解的方法称为“最小二乘法”（least square method）。在线性回归中，最小二乘法就是试图找到一条直线，使得所有样本到直线上的欧几里得距离之和最小。
求解$\bm w$和$b$使$E_{(w,b)}=\sum_{i=1}^m(y_i-wx_i-b)^2$最小化的过程，称为线性回归模型的最小二乘“参数估计”。对$\bm w$和$b$分别求导，得到
$$\frac{\partial E_{(w,b)} } {\partial {w}}=2 \sum_{i=1}^m(y_i-wx_i-b) \cdot \sum_{i=1}^m(-x_i) \ =2 \Bigl( w \sum_{i=1}^m x_i^2 - \sum_{i=1}^m (y_i-b)x_i \Bigr)$$
$$\frac{\partial E_{(w,b)} } {\partial {b}}=2 \sum_{i=1}^m(y_i-wx_i-b) \cdot (-1)\ =2 \sum_{i=1}^m(-y_i+wx_i+b) \ =2 \Bigl( mb - \sum_{i=1}^m (y_i-wx_i) \Bigr)$$
令上述两个求偏导的式子为0，可得到$\bm w$和$b$最优解的闭式解。
$$\begin{cases} \frac{\partial E_{(w,b)} } {\partial {w}}=2 \Bigl( w \sum_{i=1}^m x_i^2 - \sum_{i=1}^m (y_i-b)x_i \Bigr) =0 \\frac{\partial E_{(w,b)} } {\partial {b}}=2 \Bigl( mb - \sum_{i=1}^m (y_i-wx_i) \Bigr)=0 \end{cases}$$
$$\Downarrow$$
$$\begin{cases} w=\frac{\sum_{i=1}^m y_i(x_i-\bar x)} {\sum_{i=1}^m x_i^2-\frac1 m \Bigl( \sum_{i=1}^m x_i \Bigr)^2} \ b=\frac1 m \sum_{i=1}^m(y_i-wx_i) \end{cases}$$
以下是公式解的详细推导过程：
为什么可以通过求偏导为0的点得到$\bm w$和$b$最优解的闭式解？
均方误差对应了欧几里得距离，预测值和实际值相比可以无限偏差，最大值不存在，只存在最小值（极小值），因此求导为0的点一定是极小值点，可以达到均方误差最小化。
三、多元线性回归
更一般的情况是，数据集$D$中的样本由$d$个属性组成描述，试图得到模型$f(\bm x_i)=\bm w^T\bm x_i+b$，使得$f(\bm x_i)\approx y_i$
为了便于讨论，把$\bm w$和$b$吸收入向量形式$\hat{\bm w}=(\bm w;b)$，把数据集$D$表示为一个$m \times (d+1)$大小的矩阵$\bm X$，其中每行对应于一个示例，该行前$d$个元素对应于示例的$d$个属性值，最后一个元素恒置为1，即
$$\bm X=\begin{pmatrix} x_{11}& x_{12}& \cdots &x_{1d} & 1 \x_{21}& x_{22}& \cdots&x_{2d} & 1 \ \vdots & \vdots & \ddots & \vdots & \vdots \ x_{m1}& x_{m2}& \cdots &x_{md} & 1 \end{pmatrix} =\begin{pmatrix} \bm x_1^T & 1 \ \bm x_2^T & 1 \ \vdots & \vdots \ \bm x_m^T & 1 \end{pmatrix}$$
上述模型表达式可以理解为：$f(\bm x_i)=\bm w^T\bm x_i+b \times 1$，$\bm w$是$\bm x_m^T$的系数，$b$是1的系数。
把标记写成向量形式，$\bm y=(y_1;y_2;\cdots;y_m)$，$E_{\hat{w}}=(\bm y-\bm X \bm{ \hat{w}})^T(\bm y-\bm X \bm{ \hat{w}})$，求$\bm w$应该满足$\hat{\bm w}^*=\arg \min \limits_{\hat{\bm w}}(\bm y-\bm X \bm{ \hat{w}})^T(\bm y-\bm X \bm{ \hat{w}})$，对$\hat{\bm w}$求导得到
$$\frac{\partial E_{\hat {\bm w}} } {\partial {\hat {\bm w}}}=2 \bm X^T (\bm X \hat{\bm w}-\bm y)$$
当$\bm X^T \bm X$为满秩矩阵，导数为0的点为$\hat{\bm w}^* =(\bm X^T \bm X)^{-1}\bm X^T\bm y$，令$\hat{\bm x}_i=(\bm x_i;1)$，则最终学到的多元线性回归模型为$f(\hat{\bm x}_i)={\hat{\bm x}_i}^T (\bm X^T \bm X)^{-1}\bm X^T\bm y$
多数情况下$\bm X^T \bm X$不是满秩矩阵，存在多个解，输出解将由学习算法的归纳偏好决定，常见的做法是引入正则化项
四、对数线性回归（广义线性模型）
对数线性回归$\ln y={\bm w}^T \bm x+b$，实际上是用$e^{{\bm w}^T \bm x+b}$逼近$y$，对数线性回归在形式上仍是线性回归，但是是原来一般线性模型到输出空间的非线性函数映射。这里的对数函数的作用是，将线性回归模型的预测值与真实标记联系起来。
考虑单调可微函数$g(\cdot)$，令$y=g^{-1}({\bm w}^T \bm x+b)$，这样得到的模型称为“广义线性模型”。$g(\cdot)$称为“联系函数”，对数线性回归是广义线性模型在$g(\cdot)=\ln(\cdot)$时的特例。
五、对数几率回归（分类任务学习算法）
考虑二分类任务，其输出标记$y \in{{ 0,1}}$，而线性模型输出的预测值$z={\bm w}^T \bm x+b$为实数值，需要将实数值进行0/1变换，最理想的函数是“单位阶跃函数”
$$y=\begin{cases}0,&\text {z<0};\ 0.5,&\text {z=0};\1,&\text {z>0} \end{cases}$$
若预测值$z$大于0就判断为正例，小于0则判断为反例，预测值为临界值0则可任意判别。但是单位阶跃函数不连续，不能直接用于广义线性模型中的联系函数，可以采用单调可微的“对数几率函数”进行替代。
$$y=\frac 1 {1+e^{-z}}$$
对数几率函数与对数函数是不一样的
将对数几率函数作为联系函数带入，得到
$$y=\frac 1 {1+e^{-({\bm w}^T \bm x+b)}} \Longrightarrow \ln{\frac y {1-y}}={\bm w}^T \bm x+b$$
即现在用线性模型${\bm w}^T \bm x+b$去逼近$\ln \frac y {1-y}$
六、线性判别分析（监督降维）
线性判别分析（LDA）是一种经典的线性学习方法，在二分类问题上因为最早由Fisher提出，亦称“Fisher判别分析”。
LDA思想：给定训练样例集，设法将样例投影到一条直线上，使得同类样例的投影点尽可能接近、异类样例的投影点尽可能远离；在对新样本进行分类时，将其投影到同样的这条线上，再根据投影点的位置来确定新样本的类别。
给定数据集$D={ (x_i,y_i)}_{i=1}^m,y_i\in{0,1}$，令$X_i,\bm\mu_i,\sum_i$分别表示第$i \in {0,1}$类示例的集合，均值向量，协方差矩阵。若将数据投影到直线$\bm w$上，则两类样本的中心在直线上的投影分别为$\bm w^T\bm\mu_0$和$\bm w^T\bm\mu_1$，若将所有样本点都投影到直线上，则两类样本的协方差分别为$\bm w^T\bm\sum_0\bm w$和$\bm w^T\bm\sum_1\bm w$。由于直线是一维空间，因此上述参数均为实数。
如果要满足LDA思想，使得同类样例的投影点尽可能接近、异类样例的投影点尽可能远离，可以让同类样例投影点的协方差尽可能小，即$\bm w^T\bm\sum_0\bm w+\bm w^T\bm\sum_1\bm w$尽可能小；异类样例类中心之间的距离尽可能大，即$||\bm w^T\bm\mu_0-\bm w^T\bm\mu_1 ||_2^2$（2范数，欧氏距离）尽可能大。同时考虑二者，目的是得到最大化目标
$$J=\frac {||\bm w^T\bm\mu_0-\bm w^T\bm\mu_1 ||_2^2} {\bm w^T\bm\sum_0\bm w+\bm w^T\bm\sum_1\bm w} \ =\frac {\bm w^T(\bm \mu_0-\bm \mu_1)(\bm \mu_0-\bm \mu_1)^T\bm w} {\bm w^T(\bm \sum_0+\bm \sum_1)\bm w}$$
定义类内散度矩阵（代表两个类内的聚合度）
$$\bm S_w=\bm \sum_0+\bm \sum_1= \sum \limits_{\bm x \in X_0}(\bm x-\bm \mu_0)(\bm x-\bm \mu_0)^T+ \sum \limits_{\bm x \in X_1}(\bm x-\bm \mu_1)(\bm x-\bm \mu_1)^T$$
定义类间散度矩阵（代表两个类均值的距离）
$$\bm S_b=(\bm \mu_0-\bm \mu_1)(\bm \mu_0-\bm \mu_1)^T$$
因此可以转化表示为求$J=\frac {\bm w^T\bm S_b \bm w} {\bm w^T\bm S_w \bm w}$的最大化，即$\bm S_b$与$\bm S_w$的“广义瑞利商”。将二分类任务推广到多分类任务时，定义了“全局散度矩阵”。
若将$\bm W$视为一个投影矩阵，则多分类LDA将样本投影到$d’$维空间，$d’$通常远小于数据原有的属性数目$d$，可通过这个投影来减小样本数的维度，且投影过程中使用了类别信息，因此LDA也常被视为一种经典的监督降维技术
七、多分类学习
多分类学习的基本思路是“拆解法”，即将多分类任务拆为若干个二分类任务求解，先对问题进行拆分，然后根据拆出的每个二分类任务训练一个分类器，在测试时，对这些分类器的预测结果进行集成已获得最终的多分类结果。
常见的拆分策略有：一对一（OvO）、一对其余（OvR）、多对多（MvM）
OvR只需训练N个分类器，而OvO需要训练N(N-1)/2个分类器。OvO的存储和测试时间代价通常比OvR更大，但是在训练时间上，OvR的每个分类器均使用全部训练样例，而OvO的每个分类器仅用到两个类的样例。因此，在类别很多时，OvO的训练时间代价通常比OvR更小，在测试性能上，则取决于具体的数据分布，在多数情况下两者差不多。
八、类别不平衡问题
不同类别的样本比例相差很大，而且小类往往更重要。
类别不平衡问题解决策略是“再缩放”的思想。现在大致有三种做法，假设反类样例比正类样例多很多，方法一：对训练集的反例进行“欠采样”，去除一些反例，使得正反例的样本数目接近，然后再进行学习。方法二：对训练集的正例进行“过采样”，增加一些正例，使得正反例的样本数目接近，然后再进行学习。方法三：直接基于原始训练接进行学习，但是在用训练好的分类器进行预测时，在决策过程中做“阈值移动”。
欠采样法的时间开销通常远小于过采样法，因为前者丢弃了很多反例，使得分类器训练集远小于初始训练集，而过采样法增加了很多正例，其训练集大于初始训练集。
过采样法不能简单地对初始正例样本进行重复采样，否则会招致严重的过拟合。
代表性算法 ：
过采样法：SMOTE算法是通过对训练集里的正例进行插值来产生额外的正例。
欠采样法：EasyEnsemble算法是利用集成学习机制，将反例划分为若干个集合供不同学习器使用这样对每个学习器来看都进行了欠采样，但在全局来看却不会丢失重要信息。