线性回归算法梳理（打卡task-1）

1.从不同的角度看线性回归（传统的统计学的角度+机器学习角度）

线性回归算法梳理（打卡task-1）

2.机器学习概述：

机器学习(Machine Learning, ML)，顾名思义，让机器去学习。这里，机器指的是计算机，是算法运行的物理载体，你也可以把各种算法本身当做一个有输入和输出的机器。那么到底让计算机去学习什么呢？对于一个任务及其表现的度量方法，设计一种算法，让算法能够提取中数据所蕴含的规律，这就叫机器学习。如果输入机器的数据是带有标签的，就称作有监督学习。如果数据是无标签的，就是无监督学习。

监督学习：

监督学习是使用已知正确答案的示例来训练网络。已知数据和其一一对应的标签，训练一个预测模型，将输入数据映射到标签的过程。
监督式学习的常见应用场景如分类问题和回归问题。
常见的有监督机器学习算法包括支持向量机(Support Vector Machine, SVM)，朴素贝叶斯(Naive Bayes)，逻辑回归(Logistic Regression)，K近邻(K-Nearest Neighborhood, KNN)，决策树(Decision Tree)，随机森林(Random Forest)，AdaBoost以及线性判别分析(Linear Discriminant Analysis, LDA)等。深度学习(Deep Learning)也是大多数以监督学习的方式呈现。

非监督式学习：

在非监督式学习中，数据并不被特别标识，适用于你具有数据集但无标签的情况。学习模型是为了推断出数据的一些内在结构。
常见的应用场景包括关联规则的学习以及聚类等。
常见算法包括Apriori算法以及k-Means算法。

半监督式学习：

在此学习方式下，输入数据部分被标记，部分没有被标记，这种学习模型可以用来进行预测。
应用场景包括分类和回归，算法包括一些对常用监督式学习算法的延伸，通过对已标记数据建模，在此基础上，对未标记数据进行预测。
常见算法如图论推理算法（Graph Inference）或者拉普拉斯支持向量机（Laplacian SVM）等。

弱监督学习：

弱监督学习可以看做是有多个标记的数据集合，次集合可以是空集，单个元素，或包含多种情况（没有标记，有一个标记，和有多个标记）的多个元素。
数据集的标签是不可靠的，这里的不可靠可以是标记不正确，多种标记，标记不充分，局部标记等。
已知数据和其一一对应的弱标签，训练一个智能算法，将输入数据映射到一组更强的标签的过程。标签的强弱指的是标签蕴含的信息量的多少，比如相对于分割的标签来说，分类的标签就是弱标签。
举例，给出一张包含气球的图片，需要得出气球在图片中的位置及气球和背景的分割线，这就是已知弱标签学习强标签的问题。

在企业数据应用的场景下，人们最常用的可能就是监督式学习和非监督式学习的模型。在图像识别等领域，由于存在大量的非标识的数据和少量的可标识数据，目前半监督式学习是一个很热的话题。

线性回归代价函数作用原理

在回归问题中，通过代价函数来求解最优解，常用的是平方误差代价函数。有如下假设函数：

h ( x ) = A + B x h(x) = A + Bx h(x)=A+Bx

假设函数中有 A A A和 B B B两个参数，当参数发生变化时，假设函数状态也会随着变化。

想要拟合图中的离散点，我们需要尽可能找到最优的 A A A和 B B B来使这条直线更能代表所有数据。如何找到最优解呢，这就需要使用代价函数来求解，以平方误差代价函数为例，假设函数为 h ( x ) = θ 0 x h(x)=\theta_0x h(x)=θ0x。

平方误差代价函数的主要思想就是将实际数据给出的值与拟合出的线的对应值做差，求出拟合出的直线与实际的差距。在实际应用中，为了避免因个别极端数据产生的影响，采用类似方差再取二分之一的方式来减小个别数据的影响。因此，引出代价函数：

J ( θ 0 , θ 1 ) = 1 m ∑ i = 1 m ( h ( x ( i ) ) − y ( i ) ) 2 J(\theta_0, \theta_1) = \frac{1}{m}\sum_{i=1}^m(h(x^{(i)})-y^{(i)})^2 J(θ0,θ1)=m1i=1∑m(h(x(i))−y(i))2

最优解即为代价函数的最小值 min ⁡ J ( θ 0 , θ 1 ) \min J(\theta_0, \theta_1) minJ(θ0,θ1)。如果是1个参数，代价函数一般通过二维曲线便可直观看出。如果是2个参数，代价函数通过三维图像可看出效果，参数越多，越复杂。

当参数为2个时，代价函数是三维图像。

线性回归的损失函数

损失函数（Loss Function）又叫做误差函数，用来衡量算法的运行情况，估量模型的预测值与真实值的不一致程度，是一个非负实值函数，通常使用$

L(Y, f(x))$来表示。损失函数越小，模型的鲁棒性就越好。损失函数是经验风险函数的核心部分，也是结构风险函数重要组成部分。

优化方法（梯度下降）

梯度下降

机器学习中为什么需要梯度下降？

梯度下降是迭代法的一种，可以用于求解最小二乘问题。
在求解机器学习算法的模型参数，即无约束优化问题时，主要有梯度下降法（Gradient Descent）和最小二乘法。
在求解损失函数的最小值时，可以通过梯度下降法来一步步的迭代求解，得到最小化的损失函数和模型参数值。
如果我们需要求解损失函数的最大值，可通过梯度上升法来迭代。梯度下降法和梯度上升法可相互转换。
在机器学习中，梯度下降法主要有随机梯度下降法和批量梯度下降法。

梯度下降法缺点？

靠近极小值时收敛速度减慢。
直线搜索时可能会产生一些问题。
可能会“之字形”地下降。

梯度概念需注意：

梯度是一个向量，即有方向有大小。
梯度的方向是最大方向导数的方向。
梯度的值是最大方向导数的值。

核心思想归纳：

初始化参数，随机选取取值范围内的任意数；
迭代操作：

a）计算当前梯度；

b）修改新的变量；

c）计算朝最陡的下坡方向走一步；

d）判断是否需要终止，如否，返回a）；
得到全局最优解或者接近全局最优解。

梯度下降法算法描述

确定优化模型的假设函数及损失函数。

举例，对于线性回归，假设函数为：

h θ ( x 1 , x 2 , . . . , x n ) = θ 0 + θ 1 x 1 + . . . + θ n x n h_\theta(x_1,x_2,...,x_n)=\theta_0+\theta_1x_1+...+\theta_nx_n hθ(x1,x2,...,xn)=θ0+θ1x1+...+θnxn

其中， θ i , x i ( i = 0 , 1 , 2 , . . . , n ) \theta_i,x_i(i=0,1,2,...,n) θi,xi(i=0,1,2,...,n)分别为模型参数、每个样本的特征值。

对于假设函数，损失函数为：

J ( θ 0 , θ 1 , . . . , θ n ) = 1 2 m ∑ j = 0 m ( h θ ( x 0 ( j ) , x 1 ( j ) , . . . , x n ( j ) ) − y j ) 2 J(\theta_0,\theta_1,...,\theta_n)=\frac{1}{2m}\sum^{m}_{j=0}(h_\theta (x^{(j)}_0 ,x^{(j)}_1,...,x^{(j)}_n)-y_j)^2 J(θ0,θ1,...,θn)=2m1j=0∑m(hθ(x0(j),x1(j),...,xn(j))−yj)2

相关参数初始化。

主要初始化 θ i {\theta}_i θi、算法迭代步长${\alpha} 、终止距离、终止距离、终止距离{\zeta} 。初始化时可以根据经验初始化，即。初始化时可以根据经验初始化，即。初始化时可以根据经验初始化，即{\theta} 初始化为 0 ，步长初始化为0，步长初始化为0，步长{\alpha} 初始化为 1 。当前步长记为初始化为1。当前步长记为初始化为1。当前步长记为{\varphi}_i $。当然，也可随机初始化。
迭代计算。

1）计算当前位置时损失函数的梯度，对${\theta}_i $，其梯度表示为：

∂ ∂ θ i J ( θ 0 , θ 1 , . . . , θ n ) = 1 2 m ∑ j = 0 m ( h θ ( x 0 ( j ) , x 1 ( j ) , . . . , x n ( j ) ) − y j ) 2 \frac{\partial}{\partial \theta_i}J({\theta}_0,{\theta}_1,...,{\theta}_n)=\frac{1}{2m}\sum^{m}_{j=0}(h_\theta (x^{(j)}_0 ,x^{(j)}_1,...,x^{(j)}_n)-y_j)^2 ∂θi∂J(θ0,θ1,...,θn)=2m1j=0∑m(hθ(x0(j),x1(j),...,xn(j))−yj)2

2）计算当前位置下降的距离。

φ i = α ∂ ∂ θ i J ( θ 0 , θ 1 , . . . , θ n ) {\varphi}_i={\alpha} \frac{\partial}{\partial \theta_i}J({\theta}_0,{\theta}_1,...,{\theta}_n) φi=α∂θi∂J(θ0,θ1,...,θn)

3）判断是否终止。

确定是否所有 θ i {\theta}_i θi梯度下降的距离 φ i {\varphi}_i φi都小于终止距离 ζ {\zeta} ζ，如果都小于 ζ {\zeta} ζ，则算法终止，当然的值即为最终结果，否则进入下一步。

4）更新所有的 θ i {\theta}_i θi，更新后的表达式为：

θ i = θ i − α ∂ ∂ θ i J ( θ 0 , θ 1 , . . . , θ n ) {\theta}_i={\theta}_i-\alpha \frac{\partial}{\partial \theta_i}J({\theta}_0,{\theta}_1,...,{\theta}_n) θi=θi−α∂θi∂J(θ0,θ1,...,θn)

θ i = θ i − α 1 m ∑ j = 0 m ( h θ ( x 0 ( j ) , x 1 ( j ) , . . . , x n ( j ) ) − y j ) x i ( j ) \theta_i=\theta_i - \alpha \frac{1}{m} \sum^{m}_{j=0}(h_\theta (x^{(j)}_0 ,x^{(j)}_1,...,x^{(j)}_n)-y_j)x^{(j)}_i θi=θi−αm1j=0∑m(hθ(x0(j),x1(j),...,xn(j))−yj)xi(j)

5）令上式 x 0 ( j ) = 1 x^{(j)}_0=1 x0(j)=1，更新完毕后转入1)。

由此，可看出，当前位置的梯度方向由所有样本决定，上式中 1 m \frac{1}{m} m1、 α 1 m \alpha \frac{1}{m} αm1 的目的是为了便于理解。

如何对梯度下降法进行调优？

实际使用梯度下降法时，各项参数指标不能一步就达到理想状态，对梯度下降法调优主要体现在以下几个方面：

算法迭代步长 α \alpha α选择。

在算法参数初始化时，有时根据经验将步长初始化为1。实际取值取决于数据样本。可以从大到小，多取一些值，分别运行算法看迭代效果，如果损失函数在变小，则取值有效。如果取值无效，说明要增大步长。但步长太大，有时会导致迭代速度过快，错过最优解。步长太小，迭代速度慢，算法运行时间长。
参数的初始值选择。

初始值不同，获得的最小值也有可能不同，梯度下降有可能得到的是局部最小值。如果损失函数是凸函数，则一定是最优解。由于有局部最优解的风险，需要多次用不同初始值运行算法，关键损失函数的最小值，选择损失函数最小化的初值。
标准化处理。

由于样本不同，特征取值范围也不同，导致迭代速度慢。为了减少特征取值的影响，可对特征数据标准化，使新期望为0，新方差为1，可节省算法运行时间。

随机梯度和批量梯度区别？

随机梯度下降（SDG）和批量梯度下降（BDG）是两种主要梯度下降法，其目的是增加某些限制来加速运算求解。

下面通过介绍两种梯度下降法的求解思路，对其进行比较。

假设函数为：

h θ ( x 0 , x 1 , . . . , x 3 ) = θ 0 x 0 + θ 1 x 1 + . . . + θ n x n h_\theta (x_0,x_1,...,x_3) = \theta_0 x_0 + \theta_1 x_1 + ... + \theta_n x_n hθ(x0,x1,...,x3)=θ0x0+θ1x1+...+θnxn

损失函数为：

J ( θ 0 , θ 1 , . . . , θ n ) = 1 2 m ∑ j = 0 m ( h θ ( x 0 j , x 1 j , . . . , x n j ) − y j ) 2 J(\theta_0, \theta_1, ... , \theta_n) = \frac{1}{2m} \sum^{m}_{j=0}(h_\theta (x^{j}_0 ,x^{j}_1,...,x^{j}_n)-y^j)^2 J(θ0,θ1,...,θn)=2m1j=0∑m(hθ(x0j,x1j,...,xnj)−yj)2

其中， m m m为样本个数， j j j为参数个数。

1、批量梯度下降的求解思路如下：

a) 得到每个$ \theta $对应的梯度：

∂ ∂ θ i J ( θ 0 , θ 1 , . . . , θ n ) = 1 m ∑ j = 0 m ( h θ ( x 0 j , x 1 j , . . . , x n j ) − y j ) x i j \frac{\partial}{\partial \theta_i}J({\theta}_0,{\theta}_1,...,{\theta}_n)=\frac{1}{m}\sum^{m}_{j=0}(h_\theta (x^{j}_0 ,x^{j}_1,...,x^{j}_n)-y^j)x^{j}_i ∂θi∂J(θ0,θ1,...,θn)=m1j=0∑m(hθ(x0j,x1j,...,xnj)−yj)xij

b) 由于是求最小化风险函数，所以按每个参数 $ \theta $ 的梯度负方向更新 $ \theta_i $ ：

θ i = θ i − 1 m ∑ j = 0 m ( h θ ( x 0 j , x 1 j , . . . , x n j ) − y j ) x i j \theta_i=\theta_i - \frac{1}{m} \sum^{m}_{j=0}(h_\theta (x^{j}_0 ,x^{j}_1,...,x^{j}_n)-y^j)x^{j}_i θi=θi−m1j=0∑m(hθ(x0j,x1j,...,xnj)−yj)xij

c) 从上式可以注意到，它得到的虽然是一个全局最优解，但每迭代一步，都要用到训练集所有的数据，如果样本数据很大，这种方法迭代速度就很慢。

相比而言，随机梯度下降可避免这种问题。

2、随机梯度下降的求解思路如下：

a) 相比批量梯度下降对应所有的训练样本，随机梯度下降法中损失函数对应的是训练集中每个样本的粒度。

损失函数可以写成如下这种形式，

J ( θ 0 , θ 1 , . . . , θ n ) = 1 m ∑ j = 0 m ( y j − h θ ( x 0 j , x 1 j , . . . , x n j ) ) 2 = 1 m ∑ j = 0 m c o s t ( θ , ( x j , y j ) ) J(\theta_0, \theta_1, ... , \theta_n) = \frac{1}{m} \sum^{m}_{j=0}(y^j - h_\theta (x^{j}_0 ,x^{j}_1,...,x^{j}_n))^2 = \frac{1}{m} \sum^{m}_{j=0} cost(\theta,(x^j,y^j)) J(θ0,θ1,...,θn)=m1j=0∑m(yj−hθ(x0j,x1j,...,xnj))2=m1j=0∑mcost(θ,(xj,yj))

b）对每个参数 $ \theta$ 按梯度方向更新 $ \theta$：

θ i = θ i + ( y j − h θ ( x 0 j , x 1 j , . . . , x n j ) ) \theta_i = \theta_i + (y^j - h_\theta (x^{j}_0, x^{j}_1, ... ,x^{j}_n)) θi=θi+(yj−hθ(x0j,x1j,...,xnj))

c) 随机梯度下降是通过每个样本来迭代更新一次。

随机梯度下降伴随的一个问题是噪音较批量梯度下降要多，使得随机梯度下降并不是每次迭代都向着整体最优化方向。

小结：

随机梯度下降法、批量梯度下降法相对来说都比较极端，简单对比如下：

方法	特点
批量梯度下降	a）采用所有数据来梯度下降。 b）批量梯度下降法在样本量很大的时候，训练速度慢。
随机梯度下降	a）随机梯度下降用一个样本来梯度下降。 b）训练速度很快。 c）随机梯度下降法仅仅用一个样本决定梯度方向，导致解有可能不是全局最优。 d）收敛速度来说，随机梯度下降法一次迭代一个样本，导致迭代方向变化很大，不能很快的收敛到局部最优解。

方法

特点

批量梯度下降

a）采用所有数据来梯度下降。

b）批量梯度下降法在样本量很大的时候，训练速度慢。

随机梯度下降

a）随机梯度下降用一个样本来梯度下降。

b）训练速度很快。

c）随机梯度下降法仅仅用一个样本决定梯度方向，导致解有可能不是全局最优。

d）收敛速度来说，随机梯度下降法一次迭代一个样本，导致迭代方向变化很大，不能很快的收敛到局部最优解。

下面介绍能结合两种方法优点的小批量梯度下降法。

3、小批量（Mini-Batch）梯度下降的求解思路如下

对于总数为 m m m个样本的数据，根据样本的数据，选取其中的 n ( 1 < n < m ) n(1< n< m) n(1<n<m)个子样本来迭代。其参数 θ \theta θ按梯度方向更新 θ i \theta_i θi公式如下：

θ i = θ i − α ∑ j = t t + n − 1 ( h θ ( x 0 j , x 1 j , . . . , x n j ) − y j ) x i j \theta_i = \theta_i - \alpha \sum^{t+n-1}_{j=t} ( h_\theta (x^{j}_{0}, x^{j}_{1}, ... , x^{j}_{n} ) - y^j ) x^{j}_{i} θi=θi−αj=t∑t+n−1(hθ(x0j,x1j,...,xnj)−yj)xij

各种梯度下降法性能比较

下表简单对比随机梯度下降（SGD）、批量梯度下降（BGD）、小批量梯度下降（Mini-batch GD）、和Online GD的区别：

BGD	SGD	Mini-batch GD	Online GD
训练集	固定	固定	固定	实时更新
单次迭代样本数	整个训练集	单个样本	训练集的子集	根据具体算法定
算法复杂度	高	低	一般	低
时效性	低	一般	一般	高
收敛性	稳定	不稳定	较稳定	不稳定

BGD、SGD、Mini-batch GD，前面均已讨论过，这里介绍一下Online GD。

Online GD于Mini-batch GD/SGD的区别在于，所有训练数据只用一次，然后丢弃。这样做的优点在于可预测最终模型的变化趋势。

Online GD在互联网领域用的较多，比如搜索广告的点击率（CTR）预估模型，网民的点击行为会随着时间改变。用普通的BGD算法（每天更新一次）一方面耗时较长（需要对所有历史数据重新训练）；另一方面，无法及时反馈用户的点击行为迁移。而Online GD算法可以实时的依据网民的点击行为进行迁移。

线性回归算法梳理（打卡task-1）