cs229笔记1:线性回归

俗话说好记性不如烂笔头,看过的东西很快就会忘了,记录下来一方面会增强记忆,另一方面也方便查阅。这里根据css229视频和讲义简单做下笔记。

监督学习

本节定义了一些符号。$x^{(i)}$ 表示输入变量,也可以叫做特征。$y^{(i)}$ 表示输出变量,也可以叫做目标变量。$(x^{(i)}, y^{(i)})$ 表示一个训练样本,上标中的 (**i) **表示这是第 i 个样本。因此,对于一个包含 m 个训练样本的训练集,可以表示为如下形式

$${(x^{(i)}, y^{(i)}); i = 1,…,m}$$

所谓监督学习,可以简单描述为:给定一个训练集,通过训练学习到函数 $h(x)$,使得它能够对新的输入 $x$ 得到 “好的” 预测结果 $y$。这里的 $h(x)$ 叫做 hypothesis

2018-07-07-8.57.03

若预测结果是连续的,把这种学习问题称为 回归问题。若预测结果只有少数几个值,则称为 分类问题

线性回归

对于监督学习,首先要考虑的是 hypothesis 的形式,线性回归自然用到的是线性函数。例如预测房价问题,$x$ 是二维向量,其中$x_1^{(i)}$ 表示第 i 个样本的房间面积,$x_2^{(i)}$ 表示第 i 个样本的卧室数量,则 $h(x)$ 可表示为如下形式

$$h_\theta(x) = \theta_0 + \theta_1x_1 + \theta_2x_2$$

其中 $\theta$ 是参数,又叫做权重,它通过线性函数将输入空间 $X$ 映射到输出空间 $Y$。为方便表示,可引入常量 $x_0 = 1$

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

这里 $\theta$ 和 $x$ 均为向量,准确来说是列向量,$\theta^T$ 则是对应的行向量,根据向量乘法将上述公式展开可得到第一个公式

如何求 $\theta$ 的值呢?我们的目标是使得预测值尽可能接近实际值,也就是让预测值和实际值之间的距离 $|h_\theta(x) - y|$ 尽可能小,为了方便计算可对其取平方从而去掉绝对值符号,得到 $(h_\theta(x^{(i)}) - y^{(i)})^2$。考虑训练集中所有样本,对结果求和。通常为方便计算将上述值除以2,最终得到如下 损失函数

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

LMS算法

为了最小化 $J(\theta)$,考虑 **梯度下降 **算法。所谓梯度,其实质是向量,表示函数在该点处的方向导数沿此方向取最大值。梯度下降可以理解为沿梯度的相反方向移动,使得函数值逐渐减小,这样最终可以找到一组参数值,使得函数值取最小值或接近最小值。对于每一个参数 $\theta_j$,可通过求偏导数 $\frac{\partial}{\partial \theta_j}J(\theta)$ 得到其梯度,进而可得到如下更新规则

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

其中 $\alpha$ 称为 学习速率,它决定了函数值减小的速度。速率设置较大下降的速度会比较快,但也可能错过最小值;速率设置较小可能会需要比较多的迭代次数下降到最小值

\begin{align}
\frac{\partial}{\partial \theta_j}J(\theta)
&= \frac{\partial}{\partial \theta_j} \frac{1}{2} (h_\theta(x) - y)^2 \\
&= 2 \frac{1}{2} (h_\theta(x) - y) \frac{\partial}{\partial \theta_j} (h_\theta(x) - y) \\
&= (h_\theta(x) - y) \frac{\partial}{\partial \theta_j} (\sum_{i=0}^{n} \theta_i x_i - y) \\
&= (h_\theta(x) - y)x_j
\end{align}

只考虑一个样本,更新规则如下

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

此更新规则叫做 **LMS **(least mean squares)更新规则,或 Widrow-Hoff learning rule。其中 $(y^{(i)} - h_\theta(x^{(i)}))$ 称为误差项。该规则可以理解为:如果预测值 $h_\theta(x^{(i)})$ 接近实际值 $y^{(i)}$,则仅需要对参数做较小的更新,否则需要较大的更新

稍作修改可应用于整个训练集。对于每一个参数 $\theta_j$,均需要使用 m 个样本数据进行计算。此方法称为 **批梯度下降 **法(batch gradient descent)

$$
\theta_j := \theta_j + \alpha \sum_{i=1}^{m}(y^{(i)} - h_\theta(x^{(i)})) x_j^{(i)}
$$

批梯度下降每次迭代需要对样本集中的所有样本进行计算,当样本集比较大时,计算量也会相应的变得比较大,甚至难以实现。此时可使用 **随机梯度下降 **(stochastic gradient descent),每次迭代随机选取一个样本进行训练。使用随机梯度下降可以快速收敛到接近最小值,通常是在最小值附近波动。当样本集非常大时通常选用随机梯度下降法

概率解释

为什么选用 least-squares 损失函数作为线性回归的损失函数?实际上,在做出几个概率假设的条件下,可以很容易推导出该损失函数

假设输出变量和输入变量之间的关系可以用如下公式表示

$$
y^{(i)} = \theta^T x^{(i)} + \epsilon^{(i)}
$$

其中 $\epsilon^{(i)}$ 表示误差项。假定它符合独立同分布,即 IID(independently and identically distributed),进一步假设其服从高斯分布(正态分布),即 $\epsilon^{(i)} \sim N(0, \sigma^2)$,则它的概率密度可表示为

$$
p(\epsilon^{(i)}) = \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^Tx^{(i)})^2}{2\sigma^2})
$$

其中 $p(y^{(i)}|x^{(i)};\theta)$ 表示在条件 $x^{(i)}$ 下 $y^{(i)}$ 的概率分布,它以 $\theta$ 为参数,注意公式里面是分号

似然函数 likelihood function

$$
L(\theta) = L(\theta; X, \vec{y}) = p(\vec{y}|X; \theta)
$$

根据独立同分布假设

$$
\begin{align}
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^Tx^{(i)})^2}{2\sigma^2})
\end{align}
$$

根据最大似然法,求出使 $L(\theta)$ 最大化时的 $\theta$。为方便计算,可改为使对数似然函数最大化

$$
\begin{align}
l(\theta) &= logL(\theta) \\
&= log\prod_{i=1}^{m} \frac{1}{\sqrt{2\pi}\sigma} exp(- \frac{(y^{(i)} - \theta^Tx^{(i)})^2}{2\sigma^2}) \\
&= \sum_{i=1}^{m}log \frac{1}{\sqrt{2\pi}\sigma} exp(- \frac{(y^{(i)} - \theta^Tx^{(i)})^2}{2\sigma^2}) \\
&= m \cdot log \frac{1}{\sqrt{2\pi}\sigma} - \frac{1}{\sigma^2} \cdot \frac{1}{2} \sum_{i=1}^{m} (y^{(i)} - \theta^Tx^{(i)})^2
\end{align}
$$

若要使其最大化,只需要使第二项最小化,也就是使下式最小化。这就是 $J(\theta)$,即最小二乘损失函数(least-squares cost function)。需要注意的是, $\theta$ 的取值不依赖于 $\sigma^2$,更进一步,即使 $\sigma^2$ 是未知的我们也可以得到相同的结果

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

局部加权线性回归

在原始的线性回归算法中,我们的目标是找到 $\theta$ 的取值,使得 $\sum(y^{(i)} - \theta^Tx^{(i)})^2$ 最小化。

LWR(Locally weighted linear regression)算法中,目标是使如下式子最小化

$$
\sum w^{(i)}(y^{(i)} - \theta^Tx^{(i)})^2
$$

其中 $w^{(i)}$ 是非负的,叫做权重。如果它的取值比较小,则误差项对结果的影响也会比较小,否则会有较大影响。一个比较通用的权重公式是

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

这里权重的大小依赖于 $x$ 的选择,如果 $|x^{(i)} - x|$ 的值非常小,那么权重 $w^{(i)}$ 的取值就接近 $1$,否则权重的值就非常小(接近0)。注意 $w^{(i)}$ 不是随机变量

参数 $\tau$ 叫做 bandwidth 参数,可以理解为有效值的范围,超出一定范围后误差项对结果的影响大小下降的很快

LWR是非参数化学习算法。所谓参数化(parametric)学习算法,即训练出算法的参数后,可以使用算法对新的输入进行结果预测,不需要保留训练集,比如原始的线性回归算法。非参数化(non-parametric)学习算法刚好相反,需始终保留训练集

0%