StanFord 机器学习公开课笔记(1):LMS and LS

作者: v1gor | 来源:发表于2019-11-02 13:56 被阅读0次

StanFord 机器学习公开课笔记(1):LMS and LS
Andrew Ng Stanford机器学习公开课总结(5)
Stanford-CS-229-CN.Video1&2
逻辑回归
多元线性回归
资料
内容整理（持续更新）
StanFord 机器学习公开课笔记(4):生成学习算法
StanFord 机器学习公开课笔记(2):(Over/Unde
机器学习笔记1

本讲视频及讲义链接

前言

LMS(Least Mean Square)算法是StanFord的Widrow和Hopf在研究自适应理论时提出的算法，也就是课程中介绍的各种梯度下降法的关键:参数更新使用的算法。

LSM(Least Square Method)是最小二乘法，课程中给出了使用最小二乘法直接通过给出的训练样本经矩阵计算得出所需的参数的（不需要像梯度下降法那样迭代）

之所以用LMS和LMS作为标题，是因为我学习的时候没分清最小二乘法和梯度下降法的区别，因为它们的计算过程似乎是一样的，于是查了一些资料，多少明白了一些它们的区别。

这是知乎上看到的回答，感觉比较容易理解，引用一下：

markdown-img-paste-2017122623405394.png

监督学习-线性回归-梯度下降法

课程主要讲述4方面的内容：

监督学习
- 回归问题
- 分类问题
机器学习理论
无监督学习
- 聚类问题
强化学习
- 回报函数

有监督学习：从给定的训练样本中计算假设函数h(hypothesis),使这个函数能够在限定的误差范围内对新的输入x计算出输出y。示意图如下：

markdown-img-paste-20171226231347589.png

无监督学习：发觉隐藏在数据之下的结构。

梯度下降法

要把数学符号和它们的含义流畅地在脑中转换，这样才能快速参悟每个数学表达式的精妙之处，就像英语中的同声传译一样。----某知乎dalao

一些常用的数学符号：

$x:$ 输入变量（特征）

$y:$ 输出变量（目标变量）

$(x,y):$ 训练样本

$m:$ 训练样本个数

$n:$ 样本特征个数（x的维数）

$(x^{(i)},y^{(i)}):$ 第i组训练样本

$x_i:$ 第i维输入变量，也就是第i个特征。

$\theta:$ 最终要求出的h(x)的参数

线性回归问题的一般思路

我们的目标是通过训练样本找到一个参数向量 $\theta$ 使得函数 $h_\theta (x)$ 成为一个能够根据新的输入变量计算出一个相对合理的目标变量。我们高中学过如何用一个回归函数拟合一组离散的数据：

markdown-img-paste-20171226235250192.png

假设上图中直线方程是 $y = kx + b$ ，那么这里的参数向量 $\theta = (b,k)$ 训练样本的输入变量就是图中所有点的x的值，每个输入变量对应的输出变量就是每个点对应的y值。

以前使用最小二乘法直接根据所有的x的值计算出k和b，计算方法如下：

markdown-img-paste-20171227000426388.png

(上图来自高一的课件2333，看完就想起来啥是最小二乘法了）

在机器学习中，由于计算机可以快速多次计算，以及最小二乘法在计算上的一些困难（需要求逆矩阵），因此采用一种称为梯度下降法的方式来求出合适的参数k和b。

在回归问题中，假设 $h(x)=h_\theta(x)=\theta_0 + \theta_1 x_1 + \theta_2 x_2$

（在其他问题中有其他形式的假设，具体采用哪种应该具体问题具体分析）

为了方便用向量表达 $h(x)$ ，我们定义 $x_0 = 1$

因此 $h(x)=\sum^{n}_{i=0} \theta_i x_i = \theta ^T x$

我们接下来介绍的所有方法的目标都是计算使得式子 $\frac{1}{2}\sum_{i=1}^{m}(h_\theta (x^{(i)} )- y^{(i)})^2$ 取最小值的参数向量 $\theta$ 。

定义损失函数 $J(\theta) = \frac{1}{2}\sum_{i=1}^{m}(h_\theta (x^{(i)} )- y^{(i)})^2$ 因此目的就变成了：计算参数 $\theta$ 使得损失函数 $J(\theta)$ 达到最小值。

梯度下降法过程及原理

当存在两个参数时， $J(\theta)$ 的图像是可能是这样的：

markdown-img-paste-2017122712323549.png

像一个山脉图，现在我们要找到 $J(\theta)$ 的最小值，其实就是要找到这座山的最低点。

想象你正站在一座山的山坡上(比如上图初始点的位置)，你的目标是到达这座山的山脚，那么最直观的方法就是先环顾四周，找到向下最陡峭的方向，往那个方向走一步，之后再环顾四周，找到最陡峭的方向....最终你会到达这座山的山脚或者是一个局部最低点(因为可能会到达一个类似盆地的地方但却不是山脚)

为了决定每次向下走的方向，使用代数中的"梯度"的概念：梯度的几何意义是一个函数在某个点增加最快的方向。但是我们的目的不是让 $J(\theta)$ 上升，而是下降，因此需要找到下降最快的方向，也就是梯度方向的反方向，代数表达式就是梯度的反方向

函数 $J(\theta)$ 在点 $\theta_i$ 的梯度的计算方法是 : $\frac{\partial J(\theta_i) }{\partial \theta_i}$ 。因此梯度的反方向的代数表示就是 $-\frac{\partial J(\theta_i) }{\partial \theta_i}$

有了方向之后，需要确定每次走多远，这就是所谓的"学习速度"(步长)，也就是一个手动定义的常量 $\alpha$ . 学习速度过快( $\alpha$ 过大) 容易越过最小值；步子过小则下降的太慢。

将步长乘以梯度表示的方向就得到一个向量 $-\alpha \frac{\partial J(\theta_i) }{\partial \theta_i}$ ,这个向量加上初始点 $(\theta_1,\theta_2)$ 表示的向量 $\theta_i$ ，就得到一个新的向量 $\theta_i := \theta_i - \alpha \frac{\partial J(\theta_i) }{\partial \theta_i}$ 。这时的向量 $\theta_i$ 的终点就是下降一步后的 $J(\theta_i)$ 在图像 $J(\theta)$ 中的位置。示意图如下：

markdown-img-paste-20171227130703388.png

重复上面的过程直到某一步计算中梯度为0，则到达了局部最低点。

参考链接：梯度下降法原理

梯度下降法计算实例

只有一组训练样本

$\begin{aligned} \frac{\partial J(\theta)}{\partial \theta} &= \frac{1}2\frac{\partial}{\partial \theta} (h_\theta(x) - y)^2 \\ &=\frac{1}22(h_\theta(x) - y)\frac{\partial}{\partial \theta}(h_\theta(x)-y) \\ &=(h_\theta(x)-y)\frac{\partial h_\theta(x)}{\partial \theta} \\ &=(h_\theta(x)-y)\frac{\partial}{\partial \theta}(\theta_0 x_0 + \theta_1 x1 + .... + \theta_n x_n)\\ &=(h_\theta(x)-y)x \end{aligned}$

上面的推导的最后一步用到了标量对一维向量求导的方法：

markdown-img-paste-20171227134511417.png

更多求导的知识可以看这里：矩阵、向量的导数计算

因此 $\theta_i := \theta_i - \alpha (h_\theta(x)-y)x$

有m组训练样本

$\begin{aligned} \frac{\partial J(\theta)}{\partial \theta} &=\frac{1}2 \sum_{i=1}^{m} \frac{\partial}{\partial \theta} (h_\theta(x) - y)^2 \\ &=\frac{1}22\sum_{i=1}^{m}(h_\theta(x^{(i)})-y)\frac{\partial}{\partial \theta}\sum_{i=1}^{m}(h_\theta(x^{(i)})-y^{(i)})\\ &=\sum_{i=1}^{m}(h_\theta(x^{(i)})-y)\sum_{i=1}^{m}x^{(i)}\\ &=\sum_{i=1}^{m}(h_\theta(x^{(i)})-y)x^{(i)} \end{aligned}$

因此，m组训练样本的情况下， $\theta_i := \theta_i - \alpha \sum_{i=1}^{m}(h_\theta(x^{(i)})-y)x^{(i)}$

批量梯度下降法的特点

上述梯度下降法称为批量梯度下降法(Batch Gradient Desent),之所以称为“批量”，是因为每次更新 $\theta$ 的值，都需要使用所有的训练样本来计算一次(因为 $J(\theta)$ 函数中的求和符号)，这样的话如果有百亿量级的训练样本，则每一次下降都是十分艰难的。因此有其他梯度下降的方法。

增量(随机)梯度下降法

随机梯度下降方法每一次只是用一组训练样本进行下降，即

for j = 1 to m:

$\theta_i := \theta_i - \alpha(h_\theta(x^{(j)}) - y^{(j)})$

用这样的方法，在训练样本很大的时候也能够迅速下降，但是这种方法不会精确收敛到全局最小值，下降的路径也不能保证 $J(\theta)$ 的值一定是递减的，但是最终 $J(\theta)$ 的值会在最小值附近徘徊，对于大量的训练样本来说，精度是足够的。

下图粗略表示了随机梯度下降法的下降过程：

markdown-img-paste-20171227140812134.png

图中每个圈代表一条等高线，最外围的最高。可以对比上面批量梯度下降的图示来观察二者的区别。

最小二乘法的矩阵表示

最小二乘法不需要“一步一步地往下走”，直接通过训练样本和计算公式计算出表达式 $h_\theta(x)$ 。

为了使用矩阵表示，需要将之前的符号重写为矩阵形式：
$X=\begin{pmatrix}x^{(1)}\\ x^{(2)}\\ x^{(3)}\\ ... \end{pmatrix}$

因此
$X\theta = \begin{pmatrix}x^{(1)}\theta \\ x^{(1)T}\theta \\ x^{(2)T}\theta\\ ...\\ x^{(m)T}\theta\\ \end{pmatrix} =\begin{pmatrix}h_\theta(x^{(1)})\\ h_\theta({x^{(2)}})\\ ....\\ h_\theta(x^{(m)})\\ \end{pmatrix}$

又因为
$y= \begin{pmatrix} y^{(1)}\\ y^{(2)}\\ ...\\ y^{(m)}\\ \end{pmatrix}$
所以
$X\theta -y = \begin{pmatrix}h_\theta(x^{(1)}) - y^{(1)}\\ h_\theta(x^{(2)}) - y^{(2)}\\ ...\\ h_\theta(x^{(m)})-y^{(m)}\\ \end{pmatrix}\\ \nabla_\theta J(\theta) = \vec 0$
为了计算和化简上面的式子，引入几个线性代数中的符号和推论：

梯度
$\nabla_\theta J(\theta) = \begin{pmatrix} \frac{\partial J(\theta)}{\partial \theta_0}\ \frac{\partial J(\theta)}{\partial \theta_1}\ ...\ \frac{\partial J(\theta)}{\partial \theta_m}\ \end{pmatrix} \in \Re^{m+1}$
矩阵的迹
$trA = tr(A) = \sum{i=1}^{m}A_{ii}$
推论
1. trAB = trBA
2. trABC = trCAB = trBCA
3. $\nabla_\theta trAB = B^T$
4. $trA = trA^T$
5. $tr[a] = [a]$
6. $\nabla_A trABA^TC=CAB+C^TAB^T$

开始计算：
$\begin{align} \nabla\theta J(\theta) & = \nabla\theta \frac{1}{2}(X\theta - y)^T(X\theta - y)\\ & = \frac{1}{2}\nabla\theta(\theta^TX^TX\theta - \theta^TX^Ty-y^TX\theta + y^Ty)\\ & = \frac{1}{2}\nabla\theta tr(\theta^TX^TX\theta - \theta^TX^Ty-y^TX\theta + y^Ty)\\ & = \frac{1}{2}(\nabla\theta tr\theta\theta^TX^TX - \nabla\theta try^TX\theta - \nabla_\theta tr y^TX\theta) \end{align}$

第二步到第三步使用了推论5，因为 J(\theta) 是一个标量。

第三步到第四步使用了推论4，且 $yy^T$ 对 $\theta$ 的偏导为0.

根据推论6： \nabla_\theta tr\theta I \theta^TXTX \longrightarrow X^TX\theta I + XX^T\theta I^T.(\theta = A,I = B,C = X^TX)

根据推论3： $\nabla_\theta tr y^TX\theta = X^Ty$

因此 $J(\theta) = \frac{1}2 (X^TX\theta + XX^T\theta - X^Ty-X^Ty) = X^TX\theta - X^Ty = \vec 0$

即 $X^TX\theta = X^Ty \rightarrow \theta = (X^TX)^{-1}X^Ty$

因此只需要计算式子 $\theta = (X^TX)^{-1}X^Ty$ 就可一步得到使得 $J(\theta)$ 最小的 $\theta$ .

StanFord 机器学习公开课笔记(1):LMS and LS
本讲视频及讲义链接前言 LMS(Least Mean Square)算法是StanFord的Widrow和Hop...
Andrew Ng Stanford机器学习公开课总结(5)
--- layout: post title: Andrew Ng Stanford机器学习公开课总结（...
Stanford-CS-229-CN.Video1&2
参考内容：斯坦福大学公开课：机器学习课程Stanford-CS-229-CN Video 1 机器学习的动机与应...
逻辑回归
点击链接：逻辑回归 NG机器学习公开课笔记：机器学习笔记
多元线性回归
链接：多元线性回归 NG机器学习公开课笔记：机器学习笔记
资料
机器学习视频在此 Stanford machine learning 笔记在此 tensorflow中文api手册...
内容整理（持续更新）
机器学习基础视频教程：吴恩达机器学习-网易云公开课笔记地址：机器学习笔记作业练习：https://github....
StanFord 机器学习公开课笔记(4):生成学习算法
本讲视频及讲义链接生成学习算法生成学习算法和判别学习算法的区别判别学习算法(Discriminative) ...
StanFord 机器学习公开课笔记(2):(Over/Unde
本讲视频及讲义链接前言涉及的知识点：使用最小二乘法来拟合参数的本质原因拟合和过拟合的概念局部线性回归算法...
机器学习笔记1
机器学习笔记1

StanFord 机器学习公开课笔记(1):LMS and LS

前言

监督学习-线性回归-梯度下降法

梯度下降法

一些常用的数学符号：

线性回归问题的一般思路

梯度下降法过程及原理

梯度下降法计算实例

只有一组训练样本

有m组训练样本

批量梯度下降法的特点

增量(随机)梯度下降法

最小二乘法的矩阵表示

相关文章

StanFord 机器学习公开课笔记(1):LMS and LS

Andrew Ng Stanford机器学习公开课总结(5)

Stanford-CS-229-CN.Video1&2

逻辑回归

多元线性回归

资料

内容整理（持续更新）

StanFord 机器学习公开课笔记(4):生成学习算法

StanFord 机器学习公开课笔记(2):(Over/Unde

机器学习笔记1

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读