回归
通过房地产市场的数据，预测一个给定面积的房屋的价格就是一个回归问题。这里我们可以把价格看成是面积的函数，它是一个连续的输出值。但是，当把上面的问题改为“预测一个给定面积的房屋的价格是否比一个特定的价格高或者低”的时候，这就变成了一个分类问题, 因为此时的输出是‘高’或者‘低’两个离散的值。
机器学习初级算法梳理一
分类
给定医学数据，通过肿瘤的大小来预测该肿瘤是恶性瘤还是良性瘤(课程中给的是乳腺癌的例子)，这就是一个分类问题，它的输出是0或者1两个离散的值。(0代表良性，1代表恶性)。

分类问题的输出可以多于两个，比如在该例子中可以有{0,1,2,3}四种输出，分别对应{良性, 第一类肿瘤, 第二类肿瘤, 第三类肿瘤}。
机器学习初级算法梳理一
在这个例子中特征只有一个，那就是瘤的大小。有时候也有两个或者多个特征, 例如下图，有“年龄”和“肿瘤大小”两个特征。(还可以有其他许多特征，如下图右侧所示)

下图中上下两个图只是两种画法。第一个是有两个轴，Y轴表示是否是恶性瘤，X轴表示瘤的大小; 第二个是只用一个轴，但是用了不同的标记，用O表示良性瘤，X表示恶性瘤。

2. 无监督学习（Unsupervised Learning）

在无监督学习中，我们基本上不知道结果会是什么样子，但我们可以通过聚类的方式从数据中提取一个特殊的结构。在无监督学习中给定的数据时和监督学习中给定的数据不一样的。在无监督学习中给定的数据没有任何标签，或者说只有同一种标签。如下图所示：
机器学习初级算法梳理一
如下图所示，在无监督学习中，我们只是给定了一组数据，我们的目标是发现这组数据中的特殊结构。例如我们使用无监督学习算法会将这组数据分成两个不同的簇,，这样的算法就叫聚类算法。

2.1 无监督学习举例

新闻分类
第一个例子举的是Google News的例子。Google News搜集网上的新闻，并且根据新闻的主题将新闻分成许多簇, 然后将在同一个簇的新闻放在一起。如图中红圈部分都是关于BP Oil Well各种新闻的链接，当打开各个新闻链接的时候，展现的都是关于BP Oil Well的新闻。
根据给定基因将人群分类
如图是DNA数据，对于一组不同的人我们测量他们DNA中对于一个特定基因的表达程度。然后根据测量结果可以用聚类算法将他们分成不同的类型。这就是一种无监督学习, 因为我们只是给定了一些数据，而并不知道哪些是第一种类型的人，哪些是第二种类型的人等等。
机器学习初级算法梳理一
其他

用于管理计算机集群，在一个计算机管理中心，找出哪些计算机在进行着协同工作，就可以让数据中心更高效的工作。
用于社交网络的分析，若知道某人的各种账号的好友，例如QQ、微信、FaceBook等，就能知道哪些好友是一个好友组，哪些仅仅是互相认识的好友。
很多公司有大型的客户信息数据库，给出一个客户数据集，自动找出不同的市场分割，并自动将客户分到细分市场中，从而在不同的细分市场中进行更有效的销售。在这里事先并不知道有哪些细分市场。

3. 半监督学习（Semi-supervised Learning）

有监督学习和无监督学习的中间带就是半监督学习（semi-supervised learning）。对于半监督学习，其训练数据的一部分是有标签的，另一部分没有标签，而没标签数据的数量常常远远大于有标签数据数量（这也是符合现实情况的）。
隐藏在半监督学习下的基本规律在于：数据的分布必然不是完全随机的，通过一些有标签数据的局部特征，以及更多没标签数据的整体分布，就可以得到可以接受甚至是非常好的分类结果。

举例：给学生很多未分类的书本与少量的清单，清单上说明哪些书属于同一类别。

从不同的学习场景看，SSL可分为四大类：

1 半监督分类
半监督分类(Semi-Supervised Classification)：是在无类标签的样例的帮助下训练有类标签的样本，获得比只用有类标签的样本训练得到的分类器性能更优的分类器，弥补有类标签的样本不足的缺陷，其中类标签取有限离散值。

2 半监督回归
半监督回归(Semi-Supervised Regression)：在无输出的输入的帮助下训练有输出的输入，获得比只用有输出的输入训练得到的回归器性能更好的回归器，其中输出取连续值。

3 半监督聚类
半监督聚类(Semi-Supervised Clustering)：在有类标签的样本的信息帮助下获得比只用无类标签的样例得到的结果更好的簇，提高聚类方法的精度。

4 半监督降维
半监督降维(Semi-Supervised Dimensionality Reduction)：在有类标签的样本的信息帮助下找到高维输入数据的低维结构，同时保持原始高维数据和成对约束(Pair-Wise Constraints)的结构不变，即在高维空间中满足正约束(Must-Link Constraints)的样例在低维空间中相距很近，在高维空间中满足负约束(Cannot-Link Constraints)的样例在低维空间中距离很远。

4. 泛化能力

泛化能力用来表征学习模型对于未知数据的预测能力。

很显然，我们没有办法对所有的数据进行预测然后判断来计算一个模型的泛化能力，所以在实际应用当中，我们一般还是用的测试集中的数据来近似泛化能力。

但是，统计学习也在理论上试图对学习方法的泛化能力进行了分析，首先给出泛化误差的定义：

泛化误差越小，学习模型的泛化能力越好。

简单来说，如果说一个模型在测试集上表现的与训练集一样好，我们就说这个模型的泛化能力很好；如果模型在训练集上表现良好，但在测试集上表现一般，就说明这个模型的泛化能力不好。

从误差的角度来说，泛化能力差就是指的是测试误差比训练误差要大的情况，所以我们常常采用训练误差，测试误差来判断模型的拟合能力，这也是测试误差也常常被称为泛化误差的原因。

5.过拟合与欠拟合

我们在训练模型的时候有两个目标：

降低训练误差，寻找针对训练集最佳的拟合曲线
缩小训练误差和测试误差的差距，增强模型的泛化能力

这两大目标就对应机器学习中的两大问题：欠拟合与过拟合。具体来讲：

欠拟合是指模型在训练集和测试集表现都不好的情况，此时训练误差、测试误差都大

过拟合是指模型在训练集上表现良好，但在测试集上表现不好的情况，此时训练误差小，测试误差大，模型泛化能力不足。
过拟合通常可以理解为，模型的复杂度要高于实际的问题，所以就会导致模型死记硬背的记住，而没有理解背后的规律。就比如说人脑要比唐诗复杂得多，即使不理解内容，我们也能背下来，但是理解了内容和写法对于我们理解记忆其他唐诗有好处，如果死记硬背那么就仅仅记住了而已。

欠拟合(under-fitting) 是和过拟合相对的现象，可以说是模型的复杂度较低，没法很好的学习到数据背后的规律。就好像开普勒在总结天体运行规律之前，他的老师第谷记录了很多的运行数据，但是都没法用数据去解释天体运行的规律并预测，这就是在天体运行数据上,人们一直处于欠拟合的状态，只知道记录过的过去是这样运行的，但是不知道道理是什么。

机器学习初级算法梳理一
如上图所示，左边这幅表示欠拟合，其不能很好的拟合所有的点；最右边这幅为过拟合，其太认真的拟合所有的点，导致模型的泛化能力很差。

6. 偏差(Bias)与方差(Variance)

6.1 什么是偏差和方差

过拟合与欠拟合是从泛化的角度来谈误差，而从数学的角度分析，预测误差可以分解成三个部分：偏差(bias), 方差(variance) 和噪声(noise). 在估计学习算法性能的过程中, 我们主要关注偏差与方差. 因为噪声属于不可约减的误差 (irreducible error)。

偏差指的是模型在训练集上的错误率，如5%。其实是与训练误差成线性关系的。
方差指的是模型在开发集（或测试集）上的表现与训练集上的差距。如开发集的错误率比训练集差1%。其实是与 测试误差 - 训练误差 成线性关系的。

从偏差与方差的角度来分析模型常常会有四种情况：

偏差很低，方差很高：意味着训练误差很低，测试误差很高，此时发生了过拟合现象。
偏差很高，方差很低：意味着训练误差，测试误差都很高，此时发生了欠拟合现在。
偏差，方差都很高：意味着此时同时发生了欠拟合和过拟合现象。
偏差很低，方差很低：意味着训练误差很低，测试误差也很低，表示我们的模型训练的结果很好。

6.2 偏差与方差的权衡

从上面的分析我们可以看出，在实际中，从偏差与方差的角度能够比欠拟合，过拟合的角度更好的对当前的模型状态进行很好的评估。在实际中构建模型的过程中，其实就是对于偏差与方差之间的权衡，因为很多改进算法在减少偏差的同时往往会增大方差，反之亦然。

通过学习曲线来判断偏差与方差
在代码中添加一些曲线能够帮助你更好的分析模型状态，本节仅探讨对于分析偏差，方差有帮助的学习曲线，更多的学习曲线需要根据自己的需要来给定。

训练集样本数量与训练误差，测试误差。对于模型来说，当训练集的数据量达到一定程度之后，数据量的提升对于模型的提升已经微乎其微了，此时你需要权衡是否需要花费精力去获取更多的数据来提升模型性能。假设你的训练集有1000个样本，那么通过规模为100,200， 300，…，1000的样本集分别运行算法，我们就能得到训练误差，测试误差随训练集数据变化的曲线：

机器学习初级算法梳理一
从上图中，我们根据 Training error 与 Dev error的收敛情况完全可以很轻松的判断出此时偏差与方差的状况。

6.3 如何降低偏差

当你发现你的模型的偏差很高时，这也意味着你的训练误差很高，建议从以下几个角度试试：

加大模型规模（更换其余机器学习算法，神经网络可以增加每层神经元/神经网络层数）：偏差很高很有可能是因为模型的拟合能力差，对于传统机器学习算法，各个方法的拟合能力不同，选择一个拟合能力更好的算法往往能够得出很好的结果。对于神经网络（拟合能力最强）而言，通过增加网络层数或增加每层单元数就能够很好的提高模型的拟合能力。
根据误差分析结果来修改特征：我们需要将错误样本分类，判断可能是由于什么原因导致样本失败，在针对分析结果，增加或减少一些特征。
减少或去除正则化：这可以避免偏差，但会增大方差。
修改模型结构，以适应你的问题：对于不同的问题，不同的模型结构会产生更好的结果，比如在CV中常用CNN，而在NLP领域常用LSTM。

6.4 如何降低方差

当你发现你的模型的方差很高时，说明你的模型泛化能力弱，可以从以下几个角度分析：

重新分析，清洗数据。有时候，造成方差很大的原因往往是由于数据不良造成的，对于深度学习来说，有一个大规模，高质量的数据集是极为重要的。
添加更多的训练数据。增大训练数据能够往往能够提高模型的泛化能力。
加入正则化。正则化是机器学习中很重要的一个技巧，你必须掌握它。
加入提前终止。意思就是在训练误差变化很慢甚至不变的时候可以停止训练，这项技术可以降低方差，但有可能增大了偏差。提前终止有助于我们能够在到达最佳拟合附近，避免进入过拟合状态。
通过特征选择减少输入特征的数量和种类。显著减少特征数量能够提高模型的泛化能力，但模型的拟合能力会降低，这意味着，该技术可以减小方差，但可能会增大偏差。不过在深度学习中，我们往往直接将所有特征放入神经网络中，交给算法来选择取舍。
减少模型规模，降低模型复杂度（每层神经元个数/神经网络层数）：谨慎使用。一般情况下，对于复杂问题如CV或NLP等问题不会降低模型复杂度，而对于简单问题，采用简单模型往往训练速度更快，效果很好。
根据误差分析结果修改输入特征。
修改模型架构，使之更适合你的问题。一般可以选择简单模型的情况下，不选择复杂模型。

7.交叉验证(Cross Validation)

7.1 交叉验证原理

交叉验证是在机器学习建立模型和验证模型参数时常用的办法。交叉验证，顾名思义，就是重复的使用数据，把得到的样本数据进行切分，组合为不同的训练集和测试集，用训练集来训练模型，用测试集来评估模型预测的好坏。在此基础上可以得到多组不同的训练集和测试集，某次训练集中的某样本在下次可能成为测试集中的样本，即所谓“交叉”。

那么什么时候才需要交叉验证呢？交叉验证用在数据不是很充足的时候。比如在我日常项目里面，对于普通适中问题，如果数据样本量小于一万条，我们就会采用交叉验证来训练优化选择模型。如果样本大于一万条的话，我们一般随机的把数据分成三份，一份为训练集（Training Set），一份为验证集（Validation Set），最后一份为测试集（Test Set）。用训练集来训练模型，用验证集来评估模型预测的好坏和选择模型及其对应的参数。把最终得到的模型再用于测试集，最终决定使用哪个模型以及对应参数。

7.2 交叉验证方法

根据切分的方法不同，交叉验证分为下面三种：

1. 留出法（holdout cross validation）
在机器学习任务中，拿到数据后，我们首先会将原始数据集分为三部分：训练集、验证集和测试集。
训练集用于训练模型，验证集用于模型的参数选择配置，测试集对于模型来说是未知数据，用于评估模型的泛化能力。
机器学习初级算法梳理一
这个方法操作简单，只需随机把原始数据分为三组即可。

2. k 折交叉验证（k-fold cross validation）
不过如果只做一次分割，它对训练集、验证集和测试集的样本数比例，还有分割后数据的分布是否和原始数据集的分布相同等因素比较敏感，不同的划分会得到不同的最优模型，而且分成三个集合后，用于训练的数据更少了。

于是有了 k 折交叉验证（k-fold cross validation） 加以改进：
机器学习初级算法梳理一
k 折交叉验证通过对 k 个不同分组训练的结果进行平均来减少方差，因此模型的性能对数据的划分就不那么敏感。

第一步，不重复抽样将原始数据随机分为 k 份。
第二步，每一次挑选其中 1 份作为测试集，剩余 k-1 份作为训练集用于模型训练。
第三步，重复第二步 k 次，这样每个子集都有一次机会作为测试集，其余机会作为训练集。在每个训练集上训练后得到一个模型，用这个模型在相应的测试集上测试，计算并保存模型的评估指标，
第四步，计算 k 组测试结果的平均值作为模型精度的估计，并作为当前 k 折交叉验证下模型的性能指标。

k 一般取 10,
数据量小的时候，k 可以设大一点，这样训练集占整体比例就比较大，不过同时训练的模型个数也增多。
数据量大的时候，k 可以设小一点。

3. 留一法（Leave one out cross validation）
当 k＝m 即样本总数时，叫做留一法（Leave one out cross validation），每次的测试集都只有一个样本，要进行 m 次训练和预测。
这个方法用于训练的数据只比整体数据集少了一个样本，因此最接近原始样本的分布。但是训练复杂度增加了，因为模型的数量与原始数据样本数量相同。一般在数据缺乏时使用。

此外：

多次 k 折交叉验证再求均值，例如：10 次 10 折交叉验证，以求更精确一点。
划分时有多种方法，例如对非平衡数据可以用分层采样，就是在每一份子集中都保持和原始数据集相同的类别比例。
模型训练过程的所有步骤，包括模型选择，特征选择等都是在单个折叠 fold 中独立执行的。

还有一种比较特殊的交叉验证方式，Bootstrapping：通过自助采样法，即在含有 m 个样本的数据集中，每次随机挑选一个样本，再放回到数据集中，再随机挑选一个样本，这样有放回地进行抽样 m 次，组成了新的数据集作为训练集。

这里会有重复多次的样本，也会有一次都没有出现的样本，原数据集中大概有 36.8% 的样本不会出现在新组数据集中。

优点是训练集的样本总数和原数据集一样都是 m，并且仍有约 1/3 的数据不被训练而可以作为测试集。
缺点是这样产生的训练集的数据分布和原数据集的不一样了，会引入估计偏差。此种方法不是很常用，除非数据量真的很少。

二、线性回归的原理

1. 线性模型

给定d个属性描述的实例x = (x1,x2,…,xd),其中xi是x在第i个属性上的取值，线性模型想要学得一个通过属性的线性组合来进行预测的函数，即：

一般写成向量模型：

2. 线性回归

给定数据集D={(x1,y1),(x2,y2),(x3,y3)…(xm,ym)} ,其中xi = (xi1,xi2,xi3,…xid) 是d维属性向量，yi∈R，线性回归试图学到一个线性模型以尽可能准确的预测实值输出标记.即：

接下来要做的就是确定w和b，关键在于衡量f(x)与y的区别，这里我们常用均方误差作为回归任务中最常用的性能度量，通过最小化均方误差得到最优的w和b.即优化：

对于这种形式，我们采用最小二乘法进行估计，为了方便计算与编程，这里把w和b归入到同一个向量w^=(w,b),相应的，数据集d表示为一个m x (d+1)大小的矩阵X，其中每行对应一个实例，由于截距项的系数固定为1不需改变，所以矩阵X最后一列均为1，前d个元素对应实例的d个属性值，即：

再将均方误差转化为向量形式:

令：

对w求导，(向量可以看做是正常的二次项求导)：

并令导数为0并左乘：

三、线性回归损失函数、代价函数和目标函数

损失函数和代价函数是同一个东西，其中损失函数一般针对单个样本，而代价函数是针对总体，即为求完全部损失函数后的均值；目标函数是一个与他们相关但更广的概念，举例说明：

我们给定x，这三个函数都会输出一个f(X)，这个输出的f(X)与真实值Y可能是相同的，也可能是不同的，为了表示我们拟合的好坏，我们就用一个函数来度量拟合的程度。这个函数就称为损失函数(loss function)，或者叫代价函数(cost function)。
损失函数：

代价函数：

损失函数越小，就代表模型拟合的越好。那是不是我们的目标就只是让loss function越小越好呢？还不是。这个时候还有一个概念叫风险函数(risk function)。风险函数是损失函数的期望，这是由于我们输入输出的(X,Y)遵循一个联合分布，但是这个联合分布是未知的，所以无法计算。但是我们是有历史数据的，就是我们的训练集，f(X)关于训练集的平均损失称作经验风险(empirical risk)，所以我们的目标就是最小化经验风险。

当模型过拟合，即在训练集上表现很好而在测试集上预测效果不好时，这就引出了下面的概念，我们不仅要让经验风险最小化，还要让结构风险最小化。

这个时候就定义了一个函数J(f)，这个函数专门用来度量模型的复杂度，在机器学习中也叫正则化(regularization)。常用的有L1， L2范数。到这一步我们就可以说我们最终的优化函数是：

即最优化经验风险和结构风险，而这个函数就被称为目标函数

四、优化方法（梯度下降法、牛顿法、拟牛顿法）

1. 梯度下降法（Gradient Descent）

1.1 梯度下降法概念

梯度下降法是最早最简单，也是最为常用的最优化方法。梯度下降法实现简单，当目标函数是凸函数是，梯度，梯度下降法的解是全局解，一般情况下，其解不保证是全局最优解，梯度下降法的速度也未必是最快的。梯度下降法的优化思想是用当前位置负梯度方向作为搜索方向，因为该方向为当前位置的最快下降方向，所以也被称为是”最速下降法“。最速下降法越接近目标值，步长越小，前进越慢。梯度下降法的搜索迭代示意图如下图所示：

梯度下降法的缺点：

（1）靠近极小值时收敛速度减慢，如下图所示；

（2）直线搜索时可能会产生一些问题；

（3）可能会“之字形”地下降。

从上图可以看出，梯度下降法在接近最优解的区域收敛速度明显变慢，利用梯度下降法求解需要很多次的迭代。

在机器学习中，基于基本的梯度下降法发展了两种梯度下降方法，分别为随机梯度下降法和批量梯度下降法。

比如对一个线性回归（Linear Logistics）模型，假设下面的h(x)是要拟合的函数，J(theta)为损失函数，theta是参数，要迭代求解的值，theta求解出来了那最终要拟合的函数h(theta)就出来了。其中m是训练集的样本个数，n是特征的个数。

1.2 批量梯度下降法（Batch Gradient Descent，BGD）

（1）将J(theta)对theta求偏导，得到每个theta对应的的梯度：

（2）由于是要最小化风险函数，所以按每个参数theta的梯度负方向，来更新每个theta：

（3）从上面公式可以注意到，它得到的是一个全局最优解，但是每迭代一步，都要用到训练集所有的数据，如果m很大，那么可想而知这种方法的迭代速度会相当的慢。所以，这就引入了另外一种方法——随机梯度下降。

对于批量梯度下降法，样本个数m，x为n维向量，一次迭代需要把m个样本全部带入计算，迭代一次计算量为m*n2。

1.3 随机梯度下降（Stochastic Gradient Descent，SGD）

（1）上面的风险函数可以写成如下这种形式，损失函数对应的是训练集中每个样本的粒度，而上面批量梯度下降对应的是所有的训练样本：

（2）每个样本的损失函数，对theta求偏导得到对应梯度，来更新theta：

（3）随机梯度下降是通过每个样本来迭代更新一次，如果样本量很大的情况（例如几十万），那么可能只用其中几万条或者几千条的样本，就已经将theta迭代到最优解了，对比上面的批量梯度下降，迭代一次需要用到十几万训练样本，一次迭代不可能最优，如果迭代10次的话就需要遍历训练样本10次。但是，SGD伴随的一个问题是噪音较BGD要多，使得SGD并不是每次迭代都向着整体最优化方向。

随机梯度下降每次迭代只使用一个样本，迭代一次计算量为n2，当样本个数m很大的时候，随机梯度下降迭代一次的速度要远高于批量梯度下降方法。两者的关系可以这样理解：随机梯度下降方法以损失很小的一部分精确度和增加一定数量的迭代次数为代价，换取了总体的优化效率的提升。增加的迭代次数远远小于样本的数量。

对批量梯度下降法和随机梯度下降法的总结：

批量梯度下降—最小化所有训练样本的损失函数，使得最终求解的是全局的最优解，即求解的参数是使得风险函数最小，但是对于大规模样本问题效率低下。
随机梯度下降—最小化每条样本的损失函数，虽然不是每次迭代得到的损失函数都向着全局最优方向，但是大的整体的方向是向全局最优解的，最终的结果往往是在全局最优解附近，适用于大规模训练样本情况。

2. 牛顿法（Newton’s method）

牛顿法是一种在实数域和复数域上近似求解方程的方法。方法使用函数f (x)的泰勒级数的前面几项来寻找方程f (x) = 0的根。牛顿法最大的特点就在于它的收敛速度很快。

具体步骤：
　　
首先，选择一个接近函数 f (x)零点的 x0，计算相应的 f (x0) 和切线斜率f ’ (x0)（这里f ’ 表示函数 f 的导数）。然后我们计算穿过点(x0, f (x0)) 并且斜率为f '(x0)的直线和 x 轴的交点的x坐标，也就是求如下方程的解：

我们将新求得的点的 x 坐标命名为x1，通常x1会比x0更接近方程f (x) = 0的解。因此我们现在可以利用x1开始下一轮迭代。迭代公式可化简为如下所示：

已经证明，如果f ’ 是连续的，并且待求的零点x是孤立的，那么在零点x周围存在一个区域，只要初始值x0位于这个邻近区域内，那么牛顿法必定收敛。并且，如果f ’ (x)不为0, 那么牛顿法将具有平方收敛的性能. 粗略的说，这意味着每迭代一次，牛顿法结果的有效数字将增加一倍。下图为一个牛顿法执行过程的例子。

由于牛顿法是基于当前位置的切线来确定下一次的位置，所以牛顿法又被很形象地称为是"切线法"。牛顿法的搜索路径（二维情况）如下图所示：

牛顿法搜索动态示例图

关于牛顿法和梯度下降法的效率对比：

从本质上去看，牛顿法是二阶收敛，梯度下降是一阶收敛，所以牛顿法就更快。如果更通俗地说的话，比如你想找一条最短的路径走到一个盆地的最底部，梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步，牛顿法在选择方向时，不仅会考虑坡度是否够大，还会考虑你走了一步之后，坡度是否会变得更大。所以，可以说牛顿法比梯度下降法看得更远一点，能更快地走到最底部。（牛顿法目光更加长远，所以少走弯路；相对而言，梯度下降法只考虑了局部的最优，没有全局思想。）

根据wiki上的解释，从几何上说，牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面，而梯度下降法是用一个平面去拟合当前的局部曲面，通常情况下，二次曲面的拟合会比平面更好，所以牛顿法选择的下降路径会更符合真实的最优下降路径。

注：红色的牛顿法的迭代路径，绿色的是梯度下降法的迭代路径。

牛顿法的优缺点总结：

优点：二阶收敛，收敛速度快；

缺点：牛顿法是一种迭代算法，每一步都需要求解目标函数的Hessian矩阵的逆矩阵，计算比较复杂。

3. 拟牛顿法（Quasi-Newton Methods）

拟牛顿法是求解非线性优化问题最有效的方法之一，于20世纪50年代由美国Argonne国家实验室的物理学家W.C.Davidon所提出来。Davidon设计的这种算法在当时看来是非线性优化领域最具创造性的发明之一。不久R. Fletcher和M. J. D. Powell证实了这种新的算法远比其他方法快速和可靠，使得非线性优化这门学科在一夜之间突飞猛进。

拟牛顿法的本质思想是改善牛顿法每次需要求解复杂的Hessian矩阵的逆矩阵的缺陷，它使用正定矩阵来近似Hessian矩阵的逆，从而简化了运算的复杂度。拟牛顿法和最速下降法一样只要求每一步迭代时知道目标函数的梯度。通过测量梯度的变化，构造一个目标函数的模型使之足以产生超线性收敛性。这类方法大大优于最速下降法，尤其对于困难的问题。另外，因为拟牛顿法不需要二阶导数的信息，所以有时比牛顿法更为有效。如今，优化软件中包含了大量的拟牛顿算法用来解决无约束，约束，和大规模的优化问题。

具体步骤：

拟牛顿法的基本思想如下。首先构造目标函数在当前迭代xk的二次模型：

这里Bk是一个对称正定矩阵，于是我们取这个二次模型的最优解作为搜索方向，并且得到新的迭代点：

其中我们要求步长ak 满足Wolfe条件。这样的迭代与牛顿法类似，区别就在于用近似的Hesse矩阵Bk 代替真实的Hesse矩阵。所以拟牛顿法最关键的地方就是每一步迭代中矩阵Bk 的更新。现在假设得到一个新的迭代xk+1，并得到一个新的二次模型：

我们尽可能地利用上一步的信息来选取Bk。具体地，我们要求

从而得到

这个公式被称为割线方程。常用的拟牛顿法有DFP算法和BFGS算法。

五、线性回归的评估指标

1. 衡量线性回归法的指标：MSE, RMSE和MAE

对于简单线性回归，目标是找到a,b 使得：

其实相当于是对训练数据集而言的，即：

理所当然，其衡量标准可以是：

但问题是，这个衡量标准和样本的数量m相关（如当10000个样本累积误差达到了100，而1000个样本累积误差缺达到了80，虽然80<100，但显然不能说第二个模型要优于第一个模型）。

于是通过对式子处以m，使得其与测试样本m无关进行改进，既有了均方误差MSE (Mean Squared Error)

但有用一个问题，之前为了保证式子每项为正且可导（所以没用绝对值的表示方式），我们对市值式子加了一个平方，但会引入量纲的问题，如房子价格为万元，平方后就成了万元的平方。

于是进一步改进，对MSE开方，使量纲相同，得到均方根误差RMSE(Root Mean Squared Error)

MSE与RMSE的区别仅在于对量纲是否敏感

又一标准，通过加绝对值，即平均绝对误差 MAE(Mean Absolute Error)

在推导a,b的式子时（对train数据集），没用求绝对值的方法是因为其不是处处可导，不方便用来求极值。但评价模型时，对test数据集我们完全可以使用求绝对值的方式。

P.S. 评价模型的标准和训练模型时最优化的目标函数是可以完全不一样的。

RMSE vs MAE

RMSE 与 MAE 的量纲相同，但求出结果后我们会发现RMSE比MAE的要大一些。这是因为RMSE是先对误差进行平方的累加后再开方，它其实是放大了较大误差之间的差距。而MAE反应的就是真实误差。因此在衡量中使RMSE的值越小其意义越大，因为它的值能反映其最大误差也是比较小的。

2. 衡量线性回归最好的指标：R平方(R Squared)

对于上述的衡量方法，如RMSE和MAE还是有问题的，还是因为量纲不一样。比如我们预测考试分数误差是10，预测房价误差是1w。但我们却不能评价我们的模型是更适合预测分数还是预测房价。

解决方案：新的指标——R方

（上：y预测-y真，our model，下：y真平均-y真，baseline model）

使用baseline模型肯定会产生很多错误，我们自己的模型产生的错误会少一些。

R方将回归结果归约到了0~1间，允许我们对不同问题的预测结果进行比对了。

我们可发现，上面其实就是MSE，下面就是方差

六、sklearn线性回归参数详解

from sklearn import linear_model

导入linear_model模块，然后创建一个线性模型linear_model.LinearRegression，该线性回归模型创建有几个参数（可以通过help(linear_model.LinearRegression)来查看）：

fit_intercept：bool量，选择是否需要计算截距，默认为True，如果中心化了的数据可以选择false
normalize：bool量，选择是否需要标准化（中心化），默认为false，和参数fit_intercept有关，自行思考
copy_x:bool量，选择是否幅值X数据，默认True,如果否，可能会因为中心化把X数据覆盖
n_job:int量，选择几核用于计算，默认1，-1表示全速运行

from sklearn import linear_model
reg=linear_model.LinearRegression(fit_intercept=True,normalize=True)

然后就是训练数据，为方便可视化，我们可以用单变量单变量关系的线性回归来验证

from sklearn import linear_model
import matplotlib.pyplot as plt#用于作图
import numpy as np#用于创建向量
reg=linear_model.LinearRegression(fit_intercept=True,normalize=False)
x=[[1],[4],[5],[7],[8]]
y=[1.002,4.1,4.96,6.78,8.2]
reg.fit(x,y)
k=reg.coef_   #获取斜率w1,w2,w3,...,wn
b=reg.intercept_  #获取截距w0
x0=np.arange(0,10,0.2)
y0=k*x0+b
plt.scatter(x,y)
plt.plot(x0,y0)

机器学习初级算法梳理一

得到的结果如上图所示。如果想要多变量线性关系，只需要将对应一维的x数据改一下即可，例如：
from sklearn import linear_model
reg=linear_model.LinearRegression(fit_intercept=True,normalize=False)
x=[[1,3],[4,2],[5,1],[7,4],[8,9]]
y=[1.002,4.1,4.96,6.78,8.2]
reg.fit(x,y)
k=reg.coef_  #获取斜率w1,w2,w3,...,wn
b=reg.intercept_  #获取截距w0

此时输入变量为二变量，输出为单变量，得到的系数k和b如下：

k = array([0.97588271, 0.03692946])
b = -0.011345504840941878

机器学习初级算法梳理一