机器学习算法复习之线性回归
由ypyu创建，最终由ypyu 被浏览 9 用户
很简单的算法，却蕴含着机器学习中的一些基本思想，包括梯度下降法、最大似然估计的原理等。很多其他机器学习算法，都是在线性回归算法的基本思路之上修改得来。
和KNN的区别：KNN实例即模型，不需训练；而线性模型等很多算法，则是通过训练计算参数获得一个函数，再通过函数进行预测。
通俗理解
就是以各特征值为自变量，待预测的标签值为因变量，通过机器学习的训练过程获得各自变量的最佳参数，这样就构成一个线性组合的函数，用这个函数就可以预测某一个样本的标签值。（输入其特征值，输出其标签值）这也是很多机器学习算法的训练基本思路。
举例：用距中心区距离、户型、周边设施数量、面积等自变量，去预测房价这个因变量。
数学原理
1、符号说明（看各种参考资料前先看其符号如何定义，否则陷入混乱）
d个特征（属性），m个样本（数据点、实例）,
$x_{j}^{i}$
指第i个样本的第j个特征的特征值。
样本的真实标签值：
$y^{(i)}$
，i取从1到m
样本的特征值：
$x^{(i)}$
，i取从1到m
自变量参数（权重）：w，也有地方用θ
回归函数（假设函数）：f(x)，也有地方用h(x)
我们需要获得的函数：
$f(x)=w_{0}+w_{1}x_{1}+w_{2}x_{2}+...+w_{d}x_{d}$
可以用向量形式表示：
$f(x)=w^{T}x$
（正规表达应为
f(x)=w^{T}x+w_{0}
，整个预测函数对应用于分隔的超平面，w是法向量，w0或b是截距。为书写简便忽略w0或b）
（这里w和x均为列向量，而现实中的表格数据，样本点一般为一行）
2、获得最佳参数的过程-机器学习的训练过程-误差函数最优化问题的求解过程
我们要获得这个用于预测的函数，其实就是要获得自变量对应的最佳参数：
首先我们看什么才是最佳参数？
机器学习里定义，如果用这个假设函数预测的值，它与真实值的差距最小，那么这个函数就是最佳函数，其参数也就是最佳参数。
在线性回归中，所有样本的总误差这样表示（原因：见3）：
$\sum_{i=1}^{m}{(f(x^{(i)})-y^{(i)})^{2}}=\sum_{i=1}^{m}{(w^{T}x^{(i)}-y^{(i)})^{2}}$
在上面的式子中，x和y分别对应训练集中的特征值和标签值，都是已知的，只有w是未知的，j将w作为自变量，构建一个误差函数：
$J(w^{T})=\sum_{i=1}^{m}{(w^{T}x^{(i)}-y^{(i)})^{2}}$
也就是说，只要找到一系列w值，使得函数J的值最小，这些w就是最优的参数。所以说，机器学习的训练过程，等同于一个目标函数是J、自变量是w的最优化问题。
误差有很多不同的表示方法，在线性回归中我们用的这种形式，叫做均方误差（mean-square error, MSE）（均方误差等于上式再除以样本数量m），它对应欧几里得距离，而基于均方误差最小化进行模型求解的方法称为最小二乘法（least square method），或者最小二乘准则。
对应到特征空间上，可理解为寻找一条直线（超平面），使得所有训练样本到这条直线的欧氏距离之和最短。
然后我们看如何具体操作来获得最佳参数
对于最小二乘准则下的最优化问题，有两种解法：
（1）正规方程法（Normal Equation）/矩阵解法
高中、初中就学过了，就是令导数（偏导数）为零求函数的极值。这种方法求得的是闭式解/解析解/精确解。以前我们经常解的是一元的，但在机器学习问题中，我们要解多元的（特征有很多），所以可借助矩阵形式求解。
将各个样本的各个特征的取值组成一个m×（d+1）矩阵X，将各个样本的真实标签值组成一个m维的向量y，则用矩阵计算来表示目标函数：
$J(w)=(Xw-y)^{T}(Xw-y)$
令上式导数为零，得：
$w^{*}=(X^{T}X)^{-1}X^{T}y$
代入参数向量即可获得最终的假设函数f(x).
上式要求X为满秩矩阵或正定矩阵，而在机器学习中这个条件常不满足；而且在维度特别大的时候，其时间复杂度为
$O(n^{3})$
，运行时间会非常慢，所以机器学习中常用另一种方法。
（2）梯度下降法（Gradient Descent）/一种迭代优化法
简单逻辑：比如要求最佳的参数θ，先设定一个θ的初始值，然后朝着一个方向，不停的一点点的改变θ的值，通过θ的改变使得代价函数J(θ)的值变小，直到J(θ)不再变化（收敛），也就是最小了。
我们从误差之山上爬下来，不是随便爬的，每爬一段我们都要环顾四周，找到能让我们下降最快的方向。怎么找？就是求偏导，各个偏导各自进行迭代更新，最终获得一系列最佳参数。
梯度指出了一个让损失函数提升最快的方向，所以我们要在前面加一个负号。
确定了方向，我们还要决定每步走多远，这就是学习率α，学习率的确定涉及调参技巧（一般0.001到0.01，或进行学习率衰减）。
什么时候结束，有时我们不是非得到收敛时才停止，有很多其他停止策略：比如梯度值变化很小时，比如达到指定迭代次数时，比如代价函数变动很小时。
具体到线性回归问题中，首先我们先稍稍修改目标函数：
$J(w^{T})=\frac{1}{2m}\sum_{i=1}^{m}{(w^{T}x^{(i)}-y^{(i)})^{2}}$
加1/2是为消去求导时平方项产生的2，加1/m是为了抵消样本规模对目标函数的影响（否则样本数越少目标函数越小，样本数不同无法比较了）
更新公式（注意是对w求偏导）：wj=wj-步长*偏导
$w_{j}=w_{j}-\alpha\frac{\partial J(w_{j})}{\partial w_{j}}=w_{j}-\alpha\frac{1}{m}\sum_{i=1}^{m}({f(x^{(i)})-y^{(i)}})x_{j}^{(i)}$
（参数更新公式的符号容易弄混：一，看结果是f(x)-y还是y-f(x)；二，有的更新公式后面跟的是偏导数形式
$\frac{\partial J(w_{j})}{\partial w_{j}}$
，所以加负号，有的跟具体的表达式，可能负负消去）
梯度下降可能导致局部极值不等于最值的问题，但对于线性回归而言，代价函数总是一种碗形（bow-shaped），这种碗形的函数就是凸函数（convex function）。所以这种问题又叫凸优化问题。
扩展：批量梯度下降、随机梯度下降（SGD）、小批量梯度下降（MBGD）
批量梯度下降，就是每次迭代过程用所有样本点加总的代价函数来计算梯度。
随机梯度下降，就是每次迭代过程只用随机选择的一个样本点组成的损失函数来计算。
小批量梯度下降介于两者之间，每次迭代用一小部分数据组成代价函数。（需要设定参数b，将数据分几份，非深度学习：32、64、128，深度学习：64-512）
也就是说，在随机梯度下降和小批量梯度下降中，数据的遍历和梯度下降式迭代这两个过程同时进行：比如第一次下降迭代，我们用第一份子训练集，第二次我们用第二份，这样我们遍历完所有数据的同时，也已经迭代了很多次。
我们将遍历所有数据一次叫做一次epoch，意思就是一次epoch过程中已经梯度迭代了很多次。（而经典梯度下降是一次epoch迭代一次）
3、扩展：从概率论的角度看机器学习的训练过程：用最大似然估计法进行参数估计
从概率论的角度看获得最佳参数的问题，就是参数估计的过程。也可以说，这是我们之所以能够用训练集来基于最小二乘准则获得最佳的参数这种思路，其背后的概率论工作原理。
当然，最大似然估计比最小二乘法更具有一般性，就是说当按高斯分布写似然函数求最大似然估计的时候，就是用最小二乘法（最小二乘准则），但按另外的分布写似然函数，就不是在用最小二乘了。
（1）假设
我们的数据集需要满足：
独立假设。数据的特征值之间互不影响，比如甲和乙去贷款，银行不会因为给甲贷多了也给乙贷更多，甲和乙不是亲戚不互相担保，没有任何关系。
同分布假设。比如用中国的数据构建了一个预测房价的模型，拿去预测美国的房价，可能就会有问题。
我们还假设其一般服从高斯分布，所以数据集不满足高斯分布时，需要进行标准化。
（2）从最大似然估计到最小二乘准则
如果第i个样本的误差为：
$\epsilon^{(i)}=y^{(i)}-w^{T}x^{(i)}$
假设我们的数据集服从高斯分布（正态分布），也就是误差服从高斯分布：
$p(\epsilon^{(i)})=\frac{1}{\sqrt{2\pi}\sigma}e^{(-\frac{(\epsilon^{(i)})^{2}}{2\sigma^{2}})}=\frac{1}{\sqrt{2\pi}\sigma}e^{(-\frac{(y^{(i)}-w^{T}x^{(i)})^{2}}{2\sigma^{2}})}$
也就是说，第i个样本（特征值和真实标签值分别为
$x^{i}$
和
$y^{i}$
），它之所以能被我们观察到，是因为他们在样本中出现了，而它出现的概率就是上式，而且：
$p(\epsilon^{(i)})=p(y^{(i)}|x^{(i)})$
那么所有样本都出现的概率是多少呢？因为互相独立假设，相乘即可：
$\prod_{i=1}^{m}\frac{1}{\sqrt{2\pi}\sigma}e^{(-\frac{(y^{(i)}-w^{T}x^{(i)})^{2}}{2\sigma^{2}})}$
我们用数学式表达出了我们拿到的这个训练样本的样本分布结果。
上面这个概率函数中，x和y都是已知的，只有w未知，他们共同组成了一个分布（用上述概率函数表示），这个分布决定了现在你拿到的这些训练样本它们谁的标签值等于多少。
因为w未知，所以可以看作自变量为w的一个函数，这就是似然函数：
$L(w)=\prod_{i=1}^{m}\frac{1}{\sqrt{2\pi}\sigma}e^{(-\frac{(y^{(i)}-w^{T}x^{(i)})^{2}}{2\sigma^{2}})}$
既然我们已经拿到了这样分布的一个数据集，那我们就假设这一分布是最可能的分布，所以我们令这个似然函数的取值最大，获得的一系列w值，也就是最佳参数了。
最大似然估计，说的通俗一点，就是利用这些已知的样本分布结果，反推最有可能（最大概率）导致这样结果的参数值。（十一个人躺在那里，检查了十个人都死了，于是我推出这是个都死了的分布，第十一个人直接预测：死了）
原始的似然函数是个乘积的形式，比较复杂，我们将其转换成比较好计算的形式：
首先对似然函数进行log变换（乘法运算变成加法运算）：
$logL(w)=log\prod_{i=1}^{m}\frac{1}{\sqrt{2\pi}\sigma}e^{(-\frac{(y^{(i)}-w^{T}x^{(i)})^{2}}{2\sigma^{2}})}=mlog\frac{1}{\sqrt{2\pi}\sigma}-\frac{1}{\sigma^{2}}\cdot\frac{1}{2}\sum_{i=1}^{m}\Delta$
去掉各个无关最优化问题的常数，最后我们得到
$\frac{1}{2}\sum_{i=1}^{m}\Delta$
，我们令似然函数最大，考虑前面的负号，就是令这个部分最小。
展开Δ：
$J(w)=\frac{1}{2}\sum_{i=1}^{m}(y^{(i)}-w^{T}x^{(i)})$
得到最小二乘准则。
参考：
优达学城：机器学习课程
网易云课堂：Python数据分析与机器学习实战
吴恩达机器学习课程
周志华《机器学习》
李航《统计学习方法》