CS229学习笔记（一）——线性回归（Linear Regression）

我们加入房屋的卧室数量作为该例的另一特征量：

这样， $x$ 是一个二维矢量，例如 $x^{(i)}_1$ 代表该训练集中第 $i$ 个房屋的住房面积，而 $x^{(i)}_2$ 代表其卧室数量。

我们使用关于 $x$ 的线性函数去估计 $y$ ：

$h_\theta (x)=\theta _0+\theta _1x_1+\theta _2x_2$

为了简化公式，我们约定 $x_0=1$ （intercept term），因此有：

$h(x)=\sum_{i=0}^n \theta _ix_i=\theta ^Tx$

等式最右部分我们将 $\theta$ 和 $x$ 均视为矢量， $n$ 表示输入变量的数量（不包含 $x_0$ ）。

为了衡量对每一 $\theta$ ， $h(x^{(i)})$ 与相应的 $y^{(i)}$ 的逼近程度，我们定义代价函数（cost function）：

$J(\theta)=\frac{1}{2}\sum_{i=1}^m (h_\theta(x^{(i)})-y^{(i)})^2$

（一）概率解释

当我们面对一个回归问题，为什么线性回归，特别地，最小均方代价函数 $J$ 是合理的选择？

我们假定目标变量与其输入有如下等式关系：

$y^{(i)}=\theta^Tx^{(i)}+\epsilon ^{(i)}$ ,

这里， $\epsilon ^{(i)}$ 是误差项（error term），捕捉未建模效应（例如，有许多特征量与房价相关，但我们未在线性回归中考虑他们），或随机噪声。让我们进一步假设 $\epsilon ^{(i)}$ 是服从均值为0，方差为 $\sigma ^2$ 的高斯分布的独立同分布变量。即 $\epsilon ^{(i)}$ ~ $~N（0，\sigma^2）$ ，则 $\epsilon ^{(i)}$ 的概率分布为：

$p(\epsilon ^2)=\frac{1}{\sqrt{2\pi }\sigma } exp(-\frac{(\epsilon^{(i)})^2}{2\sigma^2} )$ ,

故 $p(y^{(i)}|x^{(i)}; \theta)=\frac{1}{\sqrt{2\pi }\sigma } exp(-\frac{(y^{(i)}-\theta^T x^{(i)})^2}{2\sigma^2} )$ 。

似然函数： $L(\theta)=L(\theta;X,\vec{y} )=p(\vec{y}|x; \theta)$ .

根据之前对 $\epsilon ^{(i)}$ 的独立性假设,

$L(\theta)=\prod_{i=1}^m p(y^{(i)}|x^{(i)}; \theta)=\prod_{i=1}^m \frac{1}{\sqrt{2\pi }\sigma } exp(-\frac{(y^{(i)}-\theta^T x^{(i)})^2}{2\sigma^2} )$

现在，给定这个关于 $y^{(i)}$ 和 $x^{(i)}$ 的概率模型，如何去获得参数 $\theta$ 的值？根据最大似然估计法，通过选择参数 $\theta$ 使得样本数据有最大概率。因此，我们应选择参数 $\theta$ 去最大化 $L(\theta)$ 。

为了简化推导，我们选择最大化对数似然函数（log likelihood function） $l(\theta)$ : $l(\theta) = log L(\theta) = log \prod_{i=1}^m \frac{1}{\sqrt{2\pi }\sigma } exp(-\frac{(y^{(i)}-\theta^T x^{(i)})^2}{2\sigma^2} ) =\sum_{ i=1}^m log \frac{1}{\sqrt{2\pi }\sigma } exp(-\frac{(y^{(i)}-\theta^T x^{(i)})^2}{2\sigma^2} ) =m log \frac{1}{\sqrt{2\pi}} - \frac{1} {\sigma^{2}} \frac{1}{2}\sum_{i=1}^m ( y^{(i) } - \theta^T x^{(i)} ) ^2$

因此，最大化 $l(\theta)$ 即最小化

$\frac{1}{2}\sum_{i=1}^m ( y^{(i) } - \theta^T x^{(i)} ) ^2$ ，

即为我们最初的最小均方代价函数 $J(\theta)$ 。

结论：基于之前的概率假设，线性回归法即是找到 $\theta$ 的最大似然估计值。

（二）最小均方算法（LMS algorithm）

我们想要通过选取 $\theta$ 去最小化 $J(\theta)$ ，所以，让我们使用一个搜索算法，从 $\theta$ 的“初始猜测值”开始，不断改变 $\theta$ 的值去减少 $J(\theta)$ ，直到得到收敛值 $\theta$ ，使得 $J(\theta)$ 最小。我们考虑梯度下降算法（gradient descent algorithm）：

$\theta_j := \theta_j - \alpha \frac{d}{d\theta_j} J(\theta)$

（更新对所有 $j = 0,...,n$ 同时进行。）这里， $\alpha$ 称为学习率（learning rate）。

为了完成这个算法，我们需要计算出等式右边的偏导数，当只有一个训练例子 $(x,y)$ 时，有：

$\frac{d}{d\theta_j} = \frac{d}{d\theta_j} \frac{1}{2} (h_\theta (x) - y)^2 = 2 *\frac{1}{2}(h_\theta - y)*\frac{d}{d\theta_j}( h_\theta(x) -y)$

$=(h_\theta(x) - y)*\frac{d}{d\theta_j}(\sum_{i=0}^n \theta_i x_i - y) =( h_\theta(x) - y)x_j$ 。

对一个训练例子，我们给定以下更新规律：

$\theta_j := \theta_j - \alpha (y^{(i)}-h_\theta(x^{(i)}))x^{(i)}_j$ ，

该规律被称为LMS更新规则（LMS代表“least mean squares”最小均方根）。

当训练集中不止一个例子时，有两种方法修改LMS更新规则，

（1）批处理梯度下降算法（Batch Gradient Descent）

Repeat until convergence $\{$

$\theta_j := \theta_j - \alpha \sum_{i=1}^m (y^{(i)}-h_\theta(x^{(i)}))x^{(i)}_j$ (for every $j$ )

$\}$

随着迭代次数的增加，每次的迭代变化会很小，可以设定一阈值，当两次迭代小于该阈值时，就停止迭代，得到的结果也近似最优解。

(2)随机梯度下降（stochastic gradient descent also incremental gradient descent）

Loop $\{$

for $i=1$ to $m$ , $\{$

$\theta_j := \theta_j - \alpha (y^{(i)}-h_\theta(x^{(i)}))x^{(i)}_j$ (for every $j$ ).

$\}$

批处理梯度下降在执行每一次迭代时，都需要遍历整个训练集，当m较大时，算法会非常耗时，而随机梯度下降算法只需对当前传入的例子进行更新。值得注意的是，随机梯度下降算法永远不会在最优值收敛，参数 $\theta$ 的值会在 $J(\theta)$ 的最小值附近持续震荡，但是实际上，在最优值附近的值都是对最优值的合理估计。当训练集较大时，我们一般都会优先选择随机梯度算法。

（三）正规方程组（the normal equations）

定义设计矩阵（design matrix）X是一个m * n的矩阵（如果我们包含截距项，则为m * n+1矩阵），在其行中包含训练例子的输入值：

令 $\vec{y}$ 为包含所有训练集的目标值的n维向量：

因为 $h_\theta(x^{(i)})=(x^{(i)})^T \theta$ ，我们可以很容易的得到：

由于 $z^Tz=\sum\nolimits_{i} z^2_i$ ，则有

$\frac{1}{2} (X\theta - \vec{y} )^T (X\theta - \vec{y} )=\frac{1}{2}\sum_{i=1}^m ( y^{(i) } - \theta^T x^{(i)} ) ^2 = J(\theta)$

因此：

为了最小化 $J$ ，我们要使得其导数为0，所以我们得到正规方程组（normal equations）：

$X^TX\theta =X^T\vec{y}$

因此，使得 $J(\theta)$ 最小的 $\theta$ 值为：

$\theta = (X^TX)^{-1}X^T\vec{y}$ 。

（四）牛顿法（Newton's method）

假设我们有一函数 $f:R\rightarrow R$ ，我们希望找到 $\theta$ 使得 $f(\theta) = 0$ （ $\theta$ 为实数），牛顿法的更新方法如下：

$\theta := \theta - \frac {f(\theta)}{f^{’}(\theta)}$

牛顿法为我们提供了让 $f(\theta) = 0$ 的方法，如何利用这种方法去得到函数 $l$ 的最大值呢？当 $l$ 取得最大值时，有 $l’(\theta) = 0$ ,所以令 $f(\theta) = l’(\theta)$ ，所以：

$\theta := \theta - \frac{l’(\theta)}{l’’(\theta)}$

推广到 $\theta$ 为高维次的情况有：

其中 $H$ 称为Hessian矩阵， $H_{ij}=\frac{d^2l(\theta)}{d\theta_id\theta_j}$ 。

通常而言，牛顿法比批处理梯度下降法需要更少的迭代次数，但由于牛顿法都需要计算n*n阶Hessian矩阵及其逆矩阵，牛顿法的每一次迭代会比梯度下降更加费时。当m不是太大时，一般而言使用牛顿法会更快。

（五）局部加权线性回归（Locally weighted linear regression）

让我们考虑用 $x$ 预测 $y$ ，最左图是使用 $y=\theta_0+\theta_1x$ 去匹配训练集，可以发现匹配效果不是太好。

我们额外再加入一个特征量 $x^2$ ，令 $y=\theta_0+\theta_1x+\theta_2x^2$ ，如中间那幅图所见，似乎参数越多，匹配的效果越好。当使用5个参数， $y=\sum\nolimits_{j=0}^5 \theta_jx^j$ ,进行匹配时，结果如最右图所示，虽然曲线完美的通过了每一个数据点，我们依然不能说它是在不同住房面积（ $x$ ）下，对房屋价格（ $y$ ）的合理预测器。我们称左图的情况为欠拟合（underfitting），右图的情况为过拟合（overfitting）。

上述例子说明，特征量的选择很大程度上决定了学习算法的表现。本部分将讨论局部线性加权回归算法（locally weighted linear regression, LWR），使得特征量的选择不那么重要。

在原始的线性回归算法中，为了得到在查询点 $x$ 预测值，我们会：

1、选取使得 $\sum\nolimits_{i}(y^{(i)}-\theta^T x^{(i)})^2$ 最小的 $\theta$ 值。

2、输出 $\theta^Tx$ 。

而在局部加权线性回归中：

1、选取使得 $\sum\nolimits_{i}\omega ^{(i)}(y^{(i)}-\theta^T x^{(i)})^2$ 最小的 $\theta$ 值。

2、输出 $\theta^Tx$ 。

这里， $\omega ^{(i)}$ 是非负权值（weights）。显然，当 $i$ 对应的 $\omega^{(i)}$ 很大时，在选择 $\theta$ 时会很难使得 $(y^{(i)}-\theta^T x^{(i)})^2$ 很小，如果 $\omega^{(i)}$ 很小， $(y^{(i)}-\theta^T x^{(i)})^2$ 将可以忽略不计。

权值的表达式为：

$\omega^{(i)} = exp(-\frac{(x^{(i)}-x)^2}{2\tau ^2})$

如果 $|x^{(i)}-x|$ 很小，那么 $\omega ^{(i)}$ 会非常接近1，如果 $|x^{(i)}-x|$ 很大，那么 $\omega ^{(i)}$ 会很小。因此，可以这样说，在局部构成了线性回归算法，对于的学习，主要依靠于查询点 $x$ 附近的值。

虽然 $\omega ^{(i)}$ 的形式与高斯分布十分相似，但与高斯分布并无关系，因为 $\omega^{(i)}$ 中并无随机变量。

局部线性加权回归是一种非参数（non-parametric）学习算法，而之前的未加权线性回归算法是一种参数（parametric）学习算法，所谓参数学习算法，它有固定明确的参数去匹配训练集。一旦参数确定，我们就不需要保留训练集中的数据。相反，当使用局部线性加权回归进行·预测时，每进行一次预测，就要重新学习一次，我们需要一直保留整个训练集。“非参数”（non-parametric）大概指的是为了学习 $h$ 所需要的保存的数据随着训练集的大小线性增长。

最后编辑于：2019.01.16 13:37:48

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 216,692评论 6赞 501
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 92,482评论 3赞 392
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 162,995评论 0赞 353
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,223评论 1赞 292
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,245评论 6赞 388
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,208评论 1赞 299
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,091评论 3赞 418
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,929评论 0赞 274
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,346评论 1赞 311
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,570评论 2赞 333
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,739评论 1赞 348
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,437评论 5赞 344
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,037评论 3赞 326
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,677评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,833评论 1赞 269
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,760评论 2赞 369
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,647评论 2赞 354