机器学习小组知识点2:最小均方算法(LMS)

感谢:向原文作者Nanshu Wang致以崇高的敬意!(http://nanshu.wang/post/2015-02-10/)
声明: 博主只是推了一遍然后细节更多的阐释了下,再次向原文作者致谢!

  1. 有监督学习(Supervised Learning)
  2. 线性回归(Linear Regression)
  3.  LMS算法
  4. 正规方程(The Normal Equations)
  5. 正规方程与梯度下降的比较

 

  1. 有监督学习
    先理清几个概念:
    1. x^i: x^i表示”输入”变量(“input” variables),也称为特征(features)。
    2. y^i: y^i表示”输出”变量(“output” variables),也称为目标值(target)。
    3. 一对(x^i,y^i)称为一个训练样本(training example),用作训练的数据集就是就是一组m个训练样本(x^i,y^i);i=1,…,m;被称为训练集(training set)。
    4. X表示输入变量的取值空间,Y表示输出变量的取值空间。那么h:X→Y是训练得到的映射函数,对于每个取值空间X的取值,都能给出取值空间Y上的一个预测值。函数hh的含义为假设(hypothesis)。
    5. 当预测值y为连续值时,则有监督学习问题是回归(regression)问题;预测值y为离散值时,则为分类(classification)问题。 图形化表示整个过程:20161015104654923
  2. 线性回归
    先简单将y表示为x的线性函数:

        \[h(x)=\sum^n_{i=0}\theta_ix_i=\theta^Tx\]

    1. \theta称为参数(parameters),也叫做权重(weights),参数决定了XY的射映空间。
    2. 用x_0=1来表示截距项(intercept term)。 有了训练集,如果通过学习得到参数\theta? 一种方法是,让预测值h(x)h(x)尽量接近真实值y,定义成本函数(cost function):

        \[J(\theta)=\frac{1}{2}\sum^m_{i=1}(h_\theta(x_i)-y_i)^2\]

  3. LMS算法 为了找到使成本函数J(\theta)最小的参数\theta,采用搜索算法:给定一个\theta 的初值,然后不断改进,每次改进都使J(\theta)更小,直到最小化J(\theta)\theta的值收敛。 考虑梯度下降(gradient descent)算法:从初始\theta开始,不断更新:

        \[\theta_j:=\theta_j-\alpha\frac{\partial}{\partial\theta_j}J(\theta)\]

    注意,更新是同时对所有j=0,…,n\theta_j值进行。\alpha被称作学习率(learning rate),也是梯度下降的长度,若\alpha取值较小,则收敛的时间较长;相反,若\alpha取值较大,则可能错过最优值。 算法具体的细节请见下面图片:(因为我实在不想敲公式了。。。。)

20161015111329598

BTW,是的,我手动加滤镜了。向我女票致敬!

图片内容补充:
1. 第一种“整体上”的梯度下降算法就是“批量梯度下降算法”(batch gradient descent)。
2. 第二种“局部上”的梯度下降算法就是“随机梯度下降算法”(stochastic gradient descent),这是因为选择下降的样本只是一部分,**更多的参考资料显示仅仅一个,并且就是对应的样本**。
3. 随机梯度下降和批量梯度下降不同点在于,批量梯度下降每一步更新\theta值,都需要遍历全部的训练样本,而随机梯度下降在遇到每个训练样本时,更新\theta之后继续处理下一个样本,每个样本只遍历一次,算法的学习时间比批量梯度下降快很多。但是,随机梯度下降可能永远不会收敛到全局最优值,而是在成本(惩罚)函数J(\theta)最优值周围附近摇摆。但是在实际问题中,接近最优值的参数值可能已经是足够好的结果了,特别是对于数据量非常大的训练集来说,随机梯度下降是比批量梯度下降更好的选择。
4. 在实际使用梯度下降算法时,将输入变量归一到同一取值范围,能够减少算法的迭代次数。这是因为\theta在小的取值范围内会下降很快,但在大的取值范围内会下降较慢。并且当输入变量取值范围不够均衡时,\theta更容易在最优值周围波动。采用特征缩放(feature scaling)和均值归一化(mean normalization)可以避免这些问题。选择学习率\alpha的值,要观察J(\theta)值在每次迭代后的变化。已经证明了如果\alpha的取值足够小,则J(\theta)每次迭代后的值都会减少。如果J(\theta)在某次迭代后反而增加了,说明学习率\alpha的值应该减小,因为错过了最优值。Andrew Ng推荐的一个经验是每次将\alpha减少3倍。
5. 这里想看一个样本的推导,可见(http://nanshu.wang/post/2015-02-10/)。

D.正规方程
梯度下降是最小化J(\theta)的一种方式,正规方程是另一种求解参数\theta的方法,这种方法可以直接求出最优值参数结果,不需要迭代更新,也不需要事先对数据进行归一化预处理。这种方法实际上是直接求出J(\theta)的导数,并令其为0。 **注明:明白最小二乘的同学,一看就知道什么东西了。** ! 20161015113629410

正规方程求解\theta的时间复杂度为O(n^3)n是特征数量。当特征数量很大时,正规方程求解会很慢。Andrew Ng给出的一个经验参考是:当n>10,000时,采用梯度下降比正规方程更好。

5.正规方程与梯度下降的比较

正规方程 梯度下降法
不需要调整参数 不需要调整参数α
不需要迭代 需要迭代更新权重θ
n n

注意,正规方程还会遇到X^TX不可逆的情况,通常这是因为输入变量中存在线性相关的变量或者是因为特征太多(nm)。解决方法是去掉线性相关的冗余变量,或者删掉一些特征。这里就是数据分析里面的回归系数的假设性检验了。感兴趣的同学,可以参考《线性统计模型》这本书。
更多的细节,会在小组讨论中提出来。

发表评论

电子邮件地址不会被公开。 必填项已用*标注