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

监督学习

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

$$\begin{array}{}\text{(1)}& (x^{(i)},y^{(i)});i=1,\dots ,m\end{array}$$

所谓监督学习，可以简单描述为：给定一个训练集，通过训练学习到函数 $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)$ 可表示为如下形式

$$\begin{array}{}\text{(2)}& h_{\theta }(x)={\theta }_0+{\theta }_1{x}_1+{\theta }_2{x}_2\end{array}$$

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

$$\begin{array}{}\text{(3)}& h(x)=\sum _{i=0}^n{\theta }_i{x}_i={\theta }^{T}x\end{array}$$

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

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

$$\begin{array}{}\text{(4)}& J(\theta )=\frac{1}{2}\sum _{i=1}^m(h_{\theta }(x^{(i)})-y^{(i)}{)}^2\end{array}$$

LMS 算法

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

$$\begin{array}{}\text{(5)}& {\theta }_j:={\theta }_j-\alpha \frac{\partial }{\partial {\theta }_j}J(\theta )\end{array}$$

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

$$\begin{array}{}\text{(6)}& \frac{\partial }{\partial {\theta }_j}J(\theta )& =\frac{\partial }{\partial {\theta }_j}\frac{1}{2}(h_{\theta }(x)-y{)}^2\text{(7)}& & =2\frac{1}{2}(h_{\theta }(x)-y)\frac{\partial }{\partial {\theta }_j}(h_{\theta }(x)-y)\text{(8)}& & =(h_{\theta }(x)-y)\frac{\partial }{\partial {\theta }_j}(\sum _{i=0}^n{\theta }_i{x}_i-y)\text{(9)}& & =(h_{\theta }(x)-y)x_j\end{array}$$

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

$$\begin{array}{}\text{(10)}& {\theta }_j:={\theta }_j+\alpha (y^{(i)}-h_{\theta }(x^{(i)}))x_j^{(i)}\end{array}$$

此更新规则叫做 **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)

$$\begin{array}{}\text{(11)}& {\theta }_j:={\theta }_j+\alpha \sum _{i=1}^m(y^{(i)}-h_{\theta }(x^{(i)}))x_j^{(i)}\end{array}$$

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

概率解释

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

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

$$\begin{array}{}\text{(12)}& y^{(i)}={\theta }^T{x}^{(i)}+{ϵ}^{(i)}\end{array}$$

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

$$\begin{array}{}\text{(13)}& p({ϵ}^{(i)})=\frac{1}{\sqrt{2\pi }\sigma }exp(-\frac{({ϵ}^{(i)}{)}^2}{2{\sigma }^2})\end{array}$$

可以得到

$$\begin{array}{}\text{(14)}& p(y^{(i)}|x^{(i)};\theta )=\frac{1}{\sqrt{2\pi }\sigma }exp(-\frac{(y^{(i)}-{\theta }^T{x}^{(i)}{)}^2}{2{\sigma }^2})\end{array}$$

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

似然函数 likelihood function

$$\begin{array}{}\text{(15)}& L(\theta )=L(\theta ;X,\overrightarrow{y})=p(\overrightarrow{y}|X;\theta )\end{array}$$

根据独立同分布假设

$$\begin{array}{}\text{(16)}& L(\theta )& =\prod _{i=1}^{m}p(y^{(i)}|x^{(i)};\theta )\text{(17)}& & =\prod _{i=1}^m\frac{1}{\sqrt{2\pi }\sigma }exp(-\frac{(y^{(i)}-{\theta }^T{x}^{(i)}{)}^2}{2{\sigma }^2})\end{array}$$

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

$$\begin{array}{}\text{(18)}& l(\theta )& =logL(\theta )\text{(19)}& & =log\prod _{i=1}^m\frac{1}{\sqrt{2\pi }\sigma }exp(-\frac{(y^{(i)}-{\theta }^T{x}^{(i)}{)}^2}{2{\sigma }^2})\text{(20)}& & =\sum _{i=1}^{m}log\frac{1}{\sqrt{2\pi }\sigma }exp(-\frac{(y^{(i)}-{\theta }^T{x}^{(i)}{)}^2}{2{\sigma }^2})\text{(21)}& & =m\cdot log\frac{1}{\sqrt{2\pi }\sigma }-\frac{1}{{\sigma }^2}\cdot \frac{1}{2}\sum _{i=1}^m(y^{(i)}-{\theta }^T{x}^{(i)}{)}^2\end{array}$$

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

$$\begin{array}{}\text{(22)}& \frac{1}{2}\sum _{i=1}^m(y^{(i)}-{\theta }^T{x}^{(i)}{)}^2\end{array}$$

局部加权线性回归

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

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

$$\begin{array}{}\text{(23)}& \sum w^{(i)}(y^{(i)}-{\theta }^T{x}^{(i)}{)}^2\end{array}$$

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

$$\begin{array}{}\text{(24)}& w^{(i)}=exp(-\frac{(x^{(i)}-x{)}^2}{2{\tau }^2})\end{array}$$

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

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

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