机器学习（西瓜书）第 3 章线性模型-编程新知

3.1 基本形式

线性模型要做的有两类任务：分类任务、回归任务

分类的核心就是求出一条直线w的参数，使得直线上方和直线下方分别属于两类不同的样本

回归就是用来拟合尽可能多的点的分布的方法，我们可以通过拟合的直线知道一个新样本的相关数值
在这里插入图片描述
例如若在西瓜问题中学得“/好瓜⑺- 0.2 • n色泽+ 0.5 •/根蒂+ 0.3 •力敲声+ 1”，则意味着可通过综合考虑色泽、根蒂和敲声来判断瓜好不好，其中根蒂最要紧，而敲声比色泽更重要.

本章介绍几种经典的线性模型.我们先从回归任务开始，然后讨论二分类和多分类任务.

3.2 线性回归

一元线性回归

我们先考虑一种最简单的情形：输入属性的数目只有一个
在这里插入图片描述
（大致有两大类方法，有一类特别擅长处理离散的东西，有一大类特别擅长处理连续的东西，如果用离散的东西去处理这种连续信号，那要先把连续信号做离散化；反之，要先把离散值连续化。而这两个过程，到现在也没有一个完美的解决方案）
（以下使用逗号表示行向量(x1, x2)，用分号表示列向量(x1;x2)）
线性模型擅长的是处理数值属性，而
对离散属性,若属性值间存在“序”（order）关系，可通过连续化将其转化为连续值，例如三值属性“高度” 的取值“高” “中” “低”可转化为｛1.0,0.5,0.0｝; 若属性值间不存在序关系，假定有k 个属性值，则通常转化为k 维向量,例如属性“瓜类”的取值“西瓜” “南瓜” “黄瓜”可转化为(0,0,1), (0,1,0),(1,0,0).若将无序属性连续化,则会不恰当地引入序关系,对后续处理如距离计算等造成误导

如何确定w和b 呢？显然，关键在于如何衡量于f(x)与y 之间的差别（垂直的差别，而不是点到直线的距离）.2.3节介绍过,均方误差 / 平方损失是回归任务中最常用的性能度量，因此我们可试图让均方误差最小化，即
在这里插入图片描述
均方误差有非常好的几何意义，它对应了常用的欧几里得距离或简称“欧氏距离"(Euclidean distance).基于均方误差最小化来进行模型求解的方法称为“最小二乘法”(least square m e t h o d ) .在线性回归中，最小二乘法就是试图 找到一条直线，使所有样本到直线上的欧氏距离之和最小.

求解w和b 使E(w,b)最小化的过程，称为线性回归模型的最小二乘“参数估计”
在这里插入图片描述
这里E(w ,b)是关于w和 b的凸函数，当它关于w和 b 的导数均为零时，得到w 和b 的最优解.
对实数集上的函数，可通过求二阶导数来判别: 若二阶导数在区间上非负, 则称为凸函数；若二阶导数在区间上恒大于0 ,则称为严格凸函数.
然后令式(3.5)和(3.6)为零可得到w 和b最优解的闭式(closed-form)解
在这里插入图片描述

a.极大似然估计

正态分布（Normal distribution）又名高斯分布（Gaussian distribution）
若随机变量X服从一个数学期望为μ、标准方差为σ^2的高斯分布，记为： $X∼N(μ,σ^2)$ ,则其概率密度函数为
在这里插入图片描述
正态分布的期望值μ决定了其位置，其标准差σ决定了分布的幅度。因其曲线呈钟形，因此人们又经常称之为钟形曲线。我们通常所说的标准正态分布是μ = 0,σ = 1的正态分布（见右图中绿色曲线）。

因为概率密度函数给出了相应值的概率，我们就可以按照分布对数据进行采样，每一个数据点的采样互不影响，而且都是从同一个分布中采样而来的，这样的采样结果我们称之为 独立同分布 的数据，而独立同分布是大部分算法模型的重要假设

想由一组数据得到是哪个高斯分布？高斯分布的定义域是从负无穷到正无穷，因此任何一个都可能采样出这组数据，因此真正想知道的是哪个高斯分布能让这组数据出现的概率最大
每一个数据被采样的概率都可以写成一个条件概率的形式N(1.88|μ,σ^2)，表示从mu和sigma的高斯分布中被采样的可能性大小。由于它们是同分布的，因此每一个条件概率中的参数mu和sigma都是一样的
同时又由于它们是相互独立的，所以同时出现的概率（也就是联合概率）体现为概率的连乘
由于我们的任务是找到一个高斯分布让这组数据出现的概率最大，所以要将联合概率取最大值，对应最大值的参数mu和sigma就是我们要找的这个高斯分布，这就是 极大似然估计 的基本思想（似然即参数估计的可能性）
在极大似然估计的函数中，联合概率的计算需要连乘来实现，但可以看到x*x的结果总是在y=x下方，所以大量的小于1的概率连乘结果会是一个非常小的数字，在实际使用中数字太小很可能直接下溢到0无法计算，所以要想办法把连乘消灭掉，通常的做法是将联合概率取对数，将内部的乘法转变为外部的加法，而加法不会让概率越来越小，对数操作也不会影响到求取最大值，因为它是单调递增的函数，所以极大似然估计往往是求取对数似然的最大值
在这里插入图片描述
将目标值y看作从一个高斯分布中采样而来的数据
将目标值y看作从一个高斯分布中采样而来的数据，在给定x的情况下，y是不确定的，现在的数据只不过是其中的一种采样结果，这相当于增加了一个均值为0的噪声项，目标值y对于x的分布就是一个均值为0，方差为sigma的高斯分布
假设所有数据都遵循同一个条件分布，且数据点相互独立，就可以进行极大似然估计。我们将高斯分布概率密度函数代入，最终得到一大坨，其中sigma是噪声的参数，与模型无关，可以从求最大值的过程中剔除，最后的结果就是我们重新得到了最小二乘估计
看似不需要证明的最小二乘估计，其实只是极大似然估计在高斯分布下的一种特殊形式
在这里插入图片描述

在这里插入图片描述
极大似然估计的用途就是估计概率分布的参数值，通常我们对一个随机变量进行建模的话，我们通常只会1.确定一下它属于哪个分布，例如正态分布，但是正态分布中有两个关键参数，由这两个参数可以2.确定唯一的一个正态分布
在这里插入图片描述

为什么只要是误差就会服从均值为0的正态分布？首先从直觉上讲，误差一般都是0左右浮动；从中心极限定理来说，如果一个随机变量是由很多个独立的随机变量之和，那么这个随机变量就服从正态分布
在这里插入图片描述

b.求解w和b

在这里插入图片描述

在这里插入图片描述

上述知识铺垫结束，以下回归正题：

对于凸函数来说，全局解就是最小值点，因此充分必要条件就是一阶导为0
在这里插入图片描述

如果要想用Python 来实现上式的话，上式中的求和运算只能用循环来实现。但是如果能将上式向量化，也就是转换成矩阵（即向量）运算的话，我们就可以利用诸如NumPy这种专门加速矩阵运算的类库来进行编写。下面我们就尝试将上式进行向量化。
在这里插入图片描述

多元线性回归

更一般的情形是如本节开头的数据集。，样本由d 个属性描述.此时我们
试图学得在这里插入图片描述
这称为“多元线性回归“(multivariate linear regression).

a.由最小二乘法导出损失函数Ew-hat

在这里插入图片描述

然后它就能写成这样一个很简洁的两个向量内积的形式
写成这样的形式后，就可以套最小二乘法了

把求和运算进行进一步的向量化，便于用numpy那种矩阵加速

在这里插入图片描述
因为两个向量相乘是一个数，所以它整体的转置相当于是对一个数做一个转置，是不变的（这样转化是为了敲代码方便，一般数据集用的data frame都是反过来摆的）

b.求解w-hat

在这里插入图片描述

未知数w-hat是d+1维的向量

三项都是标量对向量求导，属于矩阵微分的内容，就是上节课的梯度，标量对向量求导
在这里插入图片描述

矩阵
在这里插入图片描述

若X^TX满秩或正定，则以上解
若X^TX不满秩，则可解出多个w-hat，此时不能硬去解它，而是加入额外的限制。此时需求助于归纳偏好，或引入 正则化 regularization

然而,现实任务中X T X 往往不是满秩矩阵.例如在许多任务中我们会遇到大量的变量，其数目甚至超过样例数，导致X 的列数多于行数，X T X 显然不满秩.此时可解出多个w-hat它们都能使均方误差最小化.选择哪一个解作为输出, 将由学习算法的归纳偏好决定，常见的做法是引入正则化(regularization)项.
例如，生物信息学的基因芯片数据中常有成千上万个属性，但往往只有几十、上百个样例.回忆一下：解线性方程组时，若因变量过多，则会解出多组解.

线性模型的变化：
现在可以用求解线性的方式来得到一个非线性的方案

可否令模型预测值逼近g 的衍生物呢？譬如说，假设我们认为示例所对应的输出标记是在指数尺度上变化，那就可将输出标记的对数作为线性模型逼近的目标，即
在这里插入图片描述
式(3.14)在形式上仍是线性回归，但实质上已是在求取输入空间到输出空间的非线性函数映射

广义线性模型：
更一般地，考虑单调可微函数g (・)，令
在这里插入图片描述
显然，对数线性回归是广义线性模型在 g(-) = In(-)时的特例.

3.3 对数几率回归（二分类）

算法原理

对数几率回归，也被称为逻辑回归
机器学习中只有两大类算法，回归和分类。
虽然名字中带有回归，但其本质上是一个分类算法
令模型预测值逼近y的衍生物，也就是线性模型的基础上套一个映射函数来实现分类功能

在这里插入图片描述

单位阶跃函数不连续，因此不能直接用作式(3.15)中的g—( • ) .于是我们希望找到能在一定程度上近似单位阶跃函数的“替代函数”(surrogate function), 并希望它单调可微.对数几率函数(logistic function)正是这样一个常用的替代函数：
在这里插入图片描述

从图3.2可看出，对数几率函数是一种"Sigmoid函数"它将z 值转化为一个接近0 或1 的y值,并且其输出值在z = 0 附近变化很陡.将对数几率函数作为 g-(•)代入式(3.15),得到
在这里插入图片描述

损失函数的极大似然估计推导

在这里插入图片描述
注意由于是离散型变量，所以是概率质量函数

损失函数的信息论推导

在这里插入图片描述

由于均方损失非凸，对数几率回归不能通过令偏导为0求解，即对数几率回归是没有闭式解的，即无法像线性回归那样求解出w=，而是一般用这些近似求解的方式，梯度下降，牛顿法

3.4 线性判别分析（二分类）

用线性模型做“分类“有2种基本思路，刚才的是先用线性模型做线性回归，然后找一个联系函数，把我们要做的分类结果和回归结果联系起来，比如刚才的对率回归
那我们可以直接做分类吗？

线性判别分析（Linear Discriminant Analysis,简称LDA）是一种经典的线性学习方法，在二分类问题上因为最早由［Fisher, 1936］提出，亦称“Fisher判别分析”.

算法原理（模型）

在这里插入图片描述
LDA的思想非常朴素：给定训练样例集，设法将样例投影到一条直线上,
使得同类样例的投影点尽可能接近、异类样例的投影点尽可能远离；在对新样本进行分类时，将其投影到同样的这条直线上，再根据投影点的位置来确定新样本的类别
在这里插入图片描述

本质上可以认为是一种降维的做法，而这个降维是要考虑类别标记的，因此是一种监督降维
在这里插入图片描述

反正我们看的是在w上的投影，因此w的大小不重要，只需要关注w的方向

通常我们在讲优化时，都最小化，因为我们是基于凸函数来讨论的

损失函数推导（策略）

给定数据集D={(x_i,y_i)}m,i=1，y_i属于 {0,1},令X_i,mu_i,sigma_i分别表示第i属于{0,1}类示例的集合、均值向量、协方差矩阵（严格来讲既非方差也非协方差）.
在这里插入图片描述
二范数就是求向量的模长：

这里补上w的模长的好处：这样就可以直接转换成内积的这样一种很简便的形式，一个整体就可以换成一个向量内积的形式，两个都额外乘上w的模长不影响度量它们两中心之间的距离

w转置乘mu0就是mu0在w这个方向上的投影长度，不严谨的说法

严格来说这不是方差，因为方差的话前面少了系数1/m0
w转置乘mu0就是它们的中心在w上的投影长度

w转置乘x，就是x这个样本在w转置这个方向上的投影长度（放大的系数即w的模长先不管），再乘上样本中心在w转置这个方向上的投影长度，其实就是一个数，拿x样本减去中心，后面的其实是一样的，就相当于(x-x拔) ^ 2，也就是sigma(x-x拔)^2，相当于不是严格意义上的方差公式，

在这里插入图片描述

两个竖杠右下角加一个2，就是 二范数，二范数就是求向量的模长在这里插入图片描述

右上角再加一个2，就是二范数的平方，其实就是相当于求一个向量的内积

w是向量，向量没有除法不能乱约掉
在这里插入图片描述

拉格朗日乘子法

在这里插入图片描述

求解w（算法）

在这里插入图片描述

由于Sb是对称矩阵，所以Sb转置等于Sb；Sw也是如此
在这里插入图片描述

广义特征值和广义瑞利商

在这里插入图片描述

线性判别分析的多类推广

可以将L D A推广到多分类任务中…假定存在N 个类，且第i 类示例数为 m_i。我们先定义“全局散度矩阵”：
在这里插入图片描述

其中全局散度矩阵中u是所有数据的均值向量

3.5 多分类学习

若不用LDA，比如回归，就两类分类，包括知识向量机也只有两类分类
也就是说怎么把基于两类的模型来做多类的分类呢？

现实中常遇到多分类学习任务.有些二分类学习方法可直接推广到多分类,但在更多情形下，我们是基于一些基本策略，利用二分类学习器来解决多分类问题

不失一般性，考虑N 个类别C 1 & , … ,CN , 多分类学习的基本思路是 “拆解法”，即将多分类任务拆为若干个二分类任务求解.具体来说，先对问题进行拆分，然后为拆出的每个二分类任务训练一个分类器;在测试时，对这些分类器的预测结果进行集成以获得最终的多分类结果.这里的关键是如何对多分类任务进行拆分，以及如何对多个分类器进行集成.本节主要介绍拆分策略.

最经典的拆分策略有三种：“一对一”(One vs. One,简称O v O )、“一对其余“(One vs. Rest,简称 O vR)和"多对多" (Many vs. M a n y ,简称 MvM).

在这里插入图片描述

通常我们的训练开销是和样本多少关系非常大，不是线性，通常是平方甚至三次方，所以反而OvO训练时间比OvR小，因为每个模型中用到的样本比它少，而且它可以更好的做变形化

考虑N个类别多分类学习的基本思路是“拆解法”，即将多分类任务拆为若干个二分类任务求解。

拆分策略：

一对一 One vs. One OvO

将N个类别两两配对，产生N*(N-1)/2个二分类任务，新样本同时输入所有分类器，得到N*(N-1)/2个分类结果，最终结果可通过投票法产生。

一对其余 One vs. Rest OvR

每次将一个类的样例作为正例，其他所有类的样例作为反例训练分类器，产生N个二分类任务。新样本输入所有分类器，若仅有一个分类器预测为正类，则对应类别标记为最终分类结果；若多个分类器预测为正类，通常考虑各个分类器的预测置信度，选置信度最大的类别标记作为分类结果。
在这里插入图片描述

因为OvO要训练更多的分类器，因此其存储开销和测试时间开销通常比OvR更大。但在训练时，OvR的每个分类器均使用全部训练样例，而OvO的每个分类器仅用到两个类的样例，因此，在类别很多时，OvO的训练时间开销通常比OvR更小。模型的预测性能则取决于具体的数据分布，在多数情形下两者差不多。

多对多 Many vs. Many MvM

每次将若干个类作为正类，其他若干类作为反类。常用的策略如：”纠错输出码“(Error Correcting Output Codes,ECOC)。

类别不平衡

前面介绍的分类学习方法都有一个共同的基本假设，即不同类别的训练样例数目相当.如果不同类别的训练样例数目稍有差别，通常影响不大，但若差别很大,则会对学习过程造成困扰.例如有998个反例，但正例只有2 个，那么学习方法只需返回一个永远将新样本预测为反例的学习器，就能达到99.8%的精度;然而这样的学习器往往没有价值，因为它不能预测出任何正例.

类别不平衡(class-imbalance)就是指分类任务中不同类别的训练样例数目差别很大的情况.不失一般性，本节假定正类样例较少，反类样例较多.在现实的分类学习任务中，我们经常会遇到类别不平衡，例如在通过拆分法解决多分类问题时，即使原始问题中不同类别的训练样例数目相当，在使用OvR、MvM策略后产生的二分类任务仍可能出现类别不平衡现象，因此有必要了解类别不平衡性处理的基本方法.

在这里插入图片描述
几率y/(1-y)反映了正例可能性与反例可能性之比值，阔值设置为0.5恰表明分类器认为真实正、反例可能性相同，即分类器决策规则为：若y/(1-y)>1则预测为正例。

然而当训练集中正例数目(m+)、反例数目(m-)不同时，观测几率是m+/m-。由于通常假设训练集是真实样本总体的无偏采样，因此观测几率就代表了真实几率。但事实上这一假设往往不成立，也就是未必能有效地基于训练集观测几率来推断出真实几率，为此有以下三类解决策略：

1、欠采样
把大类变小，和小类一样多
丢掉一些大类的样本，不能随机丢，因为不知道丢的是不是关键的东西，可能会导致分类边界有非常显著的变化
使用easyensemble，比如小类有3个，每次就从大类中找3个，3v3，是模型1；下次再找3个，3v3，是模型2。每一个这样的子模型都是均衡的。最后用投票之类的方法结合起来。这样的方法利用到了集成学习的好处，反而提高了精度
直接对训练集里的反类样例进行"欠采样"(undersampling)，即去除一些反倒使得正、反例数日接近然后再进行学习。

优点
欠采样法的时间开销通常远小于过采样法，因为前者丢弃了很多反例，使得分类器训练集远小子初始训练集。

缺点
欠采样法若随机丢弃反例，可能丢失一些重要信息。其代表性算法EasyEnsemble 利用集成学习机制，将反例划分为若干个集合供不同学习器使用，这样对每个学习器来看都进行了欠采样，但在全局来看却不会丢失重要信息。

2、过采样
让小类增加，增加到和大类一样多
不能完全用拷贝的方法，因为一旦用了拷贝，会带来一个很大的问题——overfitting的可能就会大幅度增加，会让噪声的影响加倍
而是可以在原有的数据上稍微加点变化，smote的基本想法——在两个样本之间插值
对训练集里的正类样例进行"过采样"(oversampling)，即增加一些正例使得正、反例数目接近，然后再进行学习。

缺点
过采样法增加了很多正例，其训练集大于初始训练集。过采样法不能简单地对初始正例样本进行重复来样，否则会招致严重的过拟合，可以通过对训练集的正例进行插值(SMOTE)。

3、阈值移动threshold-moving

直接基于原始训练集进行学习，但在用训练好的分类器进行预测时，将
在这里插入图片描述嵌入到其决策过程中。