版权声明：本系列文章为博主原创文章，转载请注明出处！谢谢！
正式内容开始前，我们首先约定本系列文章中所使用的各种符号：
$m$: 训练集合中，训练样本的总数目。
$x$: 输入变量，也称为特征(feature)。
$y$: 输出变量，也称为目标变量(target)。
$n$: 模型中，特征的数量。
$(x, y)$: 即为一个训练样本。
$x^{(i)}$: 训练集合中第$i$个样本对应的输入变量，注意，这里$i$是上标，不是指数。
$y^{(i)}$: 训练集合中第$i$个样本对应的输出变量，同样，这里的$i$是上标，不是指数。
这些符号将贯穿整系列博文，如有遗忘务必随时回来翻看。
本章索引：
本章将讨论监督学习中的第一个问题 - 回归问题。首先，用一个例子引出监督学习中的回归问题；然后，从最简单的线性回归开始，介绍解决这类问题所用的两种方法：基于迭代的梯度下降和基于闭式推导的标准方程；再次，介绍一类不需要确定参数模型的非参数学习方法；最后，从概率学角度讨论在梯度下降方法中的一些假设，例如线性模型和最小二乘的假设为什么是合理的。
1. 监督学习模型
2. 回归问题定义和线性回归
3. 梯度下降算法解决线性回归问题
4. 用正规方程推导线性回归问题
5. 局部加权线性回归
6. 讨论：一些假设的概率学解释
以一个根据房屋面积预测房屋价格的例子开始，假设我们知道了如下一组房屋面积和房屋价格的关系（数据直接从吴老师公开课中借用过来的），那么我们是不是可以做点什么呢？
| 面积(平方英尺) | 价格(美元) |
| 2104 | 400 |
| 1416 | 232 |
| 1534 | 315 |
| 852 | 178 |
| 1940 | 240 |
| ... | ... |
1. 监督学习模型：
在有了这些数据后，我们肯定希望能透过这些已知数据找到其中的规律，从而用来预测其他房屋的价格（根据房屋面积）。为了达到这个目的，我们应该如何做呢？直觉上一个合理的方法是：
(1). 将这组训练集合提供给学习算法，用机器学习算法对它们进行训练。
(2). 算法生成一个映射，用$h$来表示，该映射将变量从输入空间映射到输出空间。历史原因，可以称之为假设(hypothesis)。我们常提到的模型(model)就和$h$有很大的关系。
(3). 当我们有新的数据需要处理的时候，就把这组数据输入之前得到的模型$h$，得到预测输出。
上面便是利用监督学习解决实际问题的思路。所谓监督学习，强调的是训练集合提供给学习算法的数据中，既包含了输入变量，又包含了对应于每个输入变量的“正确答案”，也叫输出变量。用图来表示如下：
在监督学习问题中，根据要预测的目标变量的类型，又可以分为两类问题。如果我们要预测的目标变量$y$是连续值，如上例中的价格，那么称这类问题为回归问题(regression problem)；如果我们要预测的目标变量$y$是离散值，如根据房屋面积判断该房屋是普通公寓还是别墅，那么这类问题称为分类问题(classification problem)。
2. 回归问题定义和线性回归
为了讲解算法，我们再添加一个变量，就是房间中卧室的数量。
| 面积(平方英尺) | 卧室数量 | 价格(美元) |
| 2104 | 3 | 400 |
| 1600 | 3 | 330 |
| 2400 | 3 | 369 |
| 1416 | 2 | 232 |
| 3000 | 4 | 540 |
| ... | ... | ... |
用$x_1$表示第一个输入变量-房屋面积，用$x_2$表示第二个输入变量-卧室数量，用$y$表示输出变量-价格。
为了用监督学习算法来预测，一个方法是我们首先应确定如何表示$h$？最简单的表示形式，就是把输出变量$y$表示成输入变量$x_1$和$x_2$的线性函数，即模型$h$是线性模型，那么此时就是线性回归问题。
egin{equation*}h_{ heta}(x)= heta_0+ heta_1x_1+ heta_2x_2end{equation*}
我们将这里的$ heta$称为参数(parameters)或权重(weights)。在不会引起混淆的情况下，可以省略掉下标$ heta$，
假设$x_0$=1，可以将线性回归的模型写成如下所示的向量乘积形式。
egin{equation*} h(x)= heta_0x_0+ heta_1x_1+ heta_2x_2 = sum_{i=0}^n heta_ix_i = heta^Txend{equation*}
其中，
egin{equation*} heta = egin{bmatrix} heta_0 \ heta_1 \ heta_2 end{bmatrix}, x = egin{bmatrix} x_0 \ x_1 \ x_2 end{bmatrix} end{equation*}
定义好了模型$h$的表示形式，随后我们需要做的就是根据已知的训练集合，通过寻找、搜索和学习，来找出合理的模型参数- $ heta$，使得训练集合提供的“正确答案”($y$)与模型预测值($h_ heta(x) = heta_0+ heta_1x_1+ heta_2x_2$)达到最佳匹配，即模型预测值和观测到的训练集合尽可能的接近。直观上，使得二者之间累计误差最小的参数模型就是最优的参数模型，因此定义一个损失函数$J( heta)$来衡量$h$与样本值之间的累计误差。
egin{equation*}J( heta) = frac{1}{2}sum_{i=1}^m(h_ heta(x^{(i)}) - y^{(i)})^2end{equation*}
根据训练集合，找到一组$ heta$以使得上述损失函数取到最小值，则$h(x)$就确定了，线性回归问题也就得到了解决，所以现在问题转化成了如何最小化损失函数。
3. 梯度下降
求解损失函数的最小值的第一个方法，就是采用搜索算法-梯度下降，它其实是一种迭代算法。对于每个$ heta$，从某个随机的初始值$ heta_j$开始，不断搜索新的$ heta_j$使$J( heta)$变小，直至收敛在一点。用公式描述如下：
egin{equation*} heta_j := heta_j - alphafrac{partial}{partial heta_j}J( heta)end{equation*}
$:=$的含义是赋值，不是逻辑上相等的意思。
上述公式的意义简单解释一下：
$alpha$是一个步长因子，只是一个常数来决定每次迭代的步长幅度，不用过多关心。微分项$frac{partial}{partial heta_j}J( heta)$是损失函数$J( heta)$的梯度。以二次函数以求最小值为例，如下图所示。我们知道极值点处的导数值为0（B点），是我们要到达的目标。如果迭代的初始值随机选在了C点，很明显选取的$ heta$值比目标值大，且此时梯度是正数（单变量实值函数中梯度就是导数，导数在C点的斜率为整），那么下一次的$ heta$应该在当前$ heta$值的基础上减小，即通过减去一个为正数的梯度就可以得到；反之，如果迭代的初始值随机选在了B点，那么选取的$ heta$值比目标值小，且此时梯度为负数，下一次的$ heta$就应该在当前$ heta$值的基础上增大，通即过减去一个负数的梯度就可以得到。如此，梯度下降算法通过不断的迭代使得参数不断趋向并收敛于极值点。
为了实现这个算法，我们需要知道$frac{partial}{partial heta_j}J( heta)$是什么。简单起见，我们从只有一个样本的训练集合(即$m=1$)开始，从而在推导过程中省略掉求和号。
egin{eqnarray*}
frac{partial}{partial heta_j}J( heta) & = & frac{partial}{partial heta_j}frac{1}{2}(h_ heta(x)-y)^2 \
& = & 2cdotfrac{1}{2}(h_ heta(x)-y)cdotfrac{partial}{partial heta_j}(h_ heta(x)-y) \ & = & (h_ heta(x)-y)cdotfrac{partial}{partial heta_j}(sum_{i=0}^n heta_ix_i-y) \ & = & (h_ heta(x)-y)x_j end{eqnarray*}
如此，我们得到了只有一个样本的训练集合的更新规则：
egin{equation*} heta_j:= heta_j+alpha(y^{(i)}-h_ heta(x^{(i)}))x_j^{(i)}end{equation*}
接下来需要从从单一样本的训练集合推广到普通的多样本训练集合，有几种不同的推广方法：
(1) 批梯度下降
在每一次迭代中，这种方法都会遍历训练集合中的所有的样本，即
egin{equation*} heta_j := heta_j+alphasum_{i=1}^m(y^{(i)}-h_ heta(x^{(i)}))x_j^{(i)} qquad (for quad everyquad j).end{equation*}
这种方法称为批梯度下降(batch gradient descent)。它可以确保$ heta$收敛到最小值上。因为$J$实际上就是一个凸二次函数。
(2) 随机梯度下降
Loop {
for i=1 to m, {
$ heta_j:= heta_j+alpha(y^{(i)}-h_ heta(x^{(i)}))x_j^{(i)} qquad (for quad every quad j).$
}
}
在这个算法中，从头到尾，我们总共只遍历一遍训练集合。在每一步迭代中，我们只考虑用一个样本来更新参数$ heta$。对比批梯度下降算法，每一次循环都要遍历整个训练集合。当训练集合中样本的数目非常大时，这是很耗时间的操作。随机梯度下降算法通常比批梯度下降算法收敛更快，但它最终可能不是收敛到最小值，而是在最小值附近波动，且大部分情况下足够逼近最小值。这种算法在训练集合的规模很大时，可以高效执行，并获得不错的效果。
梯度下降法是一个最优化算法，通常也称为最速下降法。最速下降法是求解无约束优化问题最简单和最古老的方法之一，虽然现在已经不具有实用性，但是许多有效算法都是以它为基础进行改进和修正而得到的。最速下降法是用负梯度方向为搜索方向的，最速下降法越接近目标值，步长越小，前进越慢。（摘自百度百科：梯度下降）
4 标准方程推导
上面的梯度下降算法可以通过迭代的方式最小化损失函数$J$。除此以外，还有另一种思路-- 强行推导$J$相对于$ heta$的偏导数，并让它为零（可导函数在其极值点处，一阶导数值为0）。
开始推导之前，先给出两个定义，帮助我们用矩阵表示法来简化推导过程。
定义1：函数对于矩阵的偏导数
有一个函数$f: mathbb{R}^{m imes n} o mathbb{R}$，它把一个$m imes n$的矩阵映射成一个实数，则我们定义这个函数$f$对于矩阵A的偏导数:
egin{eqnarray*} abla_Af(A)= egin{bmatrix} frac{partial f}{partial A_{11}} & cdots & frac{partial f}{partial A_{1n}} \ vdots & ddots & vdots \ frac{partial f}{partial A_{m1}} & cdots & frac{partial f}{partial A_{mn}} end{bmatrix} end{eqnarray*}
所以，梯度$ abla_Af(A)$本身是一个$m imes n$的矩阵，它的第$(i,j)$个坐标是$partial f / partial A_{ij}$。
例如，$A=egin{bmatrix} A_{11} & A_{12} \ A_{21} & A_{22}end{bmatrix} $是一个2*2的矩阵; $f: mathbb{R} ^ {2 imes 2} o mathbb{R} $ 有如下形式：
egin{equation*} f(A)=frac{3}{2}A_{11}+5A_{12}^2+A_{21}A_{22} end{equation*}
套用上面的公式，可以得到：
egin{equation*} abla_Af(A)= egin{bmatrix} frac{3}{2} & 10A_{12} \ A_{22} & A_{21} end{bmatrix} end{equation*}
定义2：矩阵的迹
矩阵的迹：
egin{equation*} trA=sum_{i=1}^nA_{ii} end{equation*}
有了以上两个定义，则矩阵的迹，我们有以下性质：
egin{equation*} trAB = trBA end{equation*}
egin{equation*} trABC = trCAB = trBCAend{equation*}
egin{equation*} trABCD = trDABC = trCDAB = trBCDA end{equation*}
egin{equation*} trA = trA^Tend{equation*}
egin{equation*} tr(A+B) = trA + trB end{equation*}
egin{equation*} traA = atrAend{equation*}
对于矩阵的偏导数，我们有以下性质：
egin{equation*} abla_Atr(AB)=B^T end{equation*}
egin{equation*} abla_{A^T} = ( abla_Af(A))^T end{equation*}
egin{equation*} abla_AtrABA^TC = CAB + C^TAB^T end{equation*}
egin{equation*} abla_A|A| = |A| (A^-1)^T end{equation*}
接下来，我们来求解使得$J( heta)$最小的$ heta$值的封闭形式。
为了将矩阵的形式重写$J$，定义一个$m imes n$的设计矩阵$X$，它包含了所有的m组训练样本的输入，每组样本的输入写成列向量$x^{(i)}$的形式:
egin{equation*} X = egin{bmatrix} (x^{(1)})^T \ (x^{(2)})^T \ vdots \ (x^{(m)})^T \ end{bmatrix} end{equation*}
定义$vec y$是$m$维的列向量，包含了每组训练样本的目标:
egin{equation*} vec y = egin{bmatrix} y^{(1)} \ y^{(2)} \ vdots \ y^{(m)} end{bmatrix} end{equation*}
由于$h_ heta(x^{(i)}) = (x^{(i)})^T heta$，我们可以得出：
egin{equation*} X heta-vec y = egin{bmatrix} (x^{(1)})^T heta \ (x^{(2)})^T heta \ vdots \ (x^{(m)})^T heta end{bmatrix} - egin{bmatrix} y^{(1)} \ y^{(2)} \ vdots \ y^{(m)}end{bmatrix} = egin{bmatrix} h_ heta(x^{(1)})^T heta-y^{(1)} \ h_ heta(x^{(2)})^T heta-y^{(2)} \ vdots \ h_ heta(x^{(m)})^T heta-y^{(m)} end{bmatrix} end{equation*}
对于一个向量$vec z$，我们有知道$z^Tz= sum_iz_i^2$，那么
egin{equation*}frac{1}{2}(X heta-vec y)^T(X heta-vec y) = frac{1}{2}sum_{i=1}^m(h_ heta(x^{(i)})-y^{(i)})^2=J( heta) end{equation*}
根据之前的结论，$ abla_{A^T}trABA^TC=B^TA^TC^T+BA^TC$，因此我们有：
egin{eqnarray*} abla_ heta J( heta) & = & abla_ heta frac{1}{2} (X heta-vec y)^T(X heta-vec y) \ & = & frac{1}{2} abla_ heta ( heta^TX^TX heta- heta^TX^Tvec y - vec y ^TX heta+vec y^Tvec y) \ & = & frac{1}{2} abla_ heta tr ( heta^TX^TX heta- heta^TX^Tvec y - vec y ^TX heta+vec y^Tvec y) \ & = & frac{1}{2} abla_ heta (tr heta^TX^TX heta-2trvec y^TX heta) \ & = & frac{1}{2}(X^TX heta+X^TX heta-2X^Tvec y) \ & = & X^TX heta-X^Tvec y end{eqnarray*}
为了求$J( heta)$的最小值，我们使这个等式为0，最终得到：
egin{equation*} X^TX heta = X^Tvec yend{equation*}
egin{equation*} heta = (X^TX)^{-1}X^Tvec y end{equation*}
推导没啥难点，有线性代数基础的兄弟们应该都能看明白。
5. 局部加权线性回归
上面我们的讨论都是基于线性模型，也就是输入变量$y$和输出变量$x$之间的关系都是线性的：$y= heta_0+ heta_1x$。实际上，这样的线性模型不一定能很好的拟合给定的数据集，例如下图中的左图。
如果我们在以上线性模型的基础上再添加一个特征$x^2$，用$y= heta_0+ heta_1x+ heta_2x^2$来拟合，拟合的结果就比线性模型好很多，如上图的中间图所示。因此，直觉上，我们用越多的特征拟合，效果应该越好。然而，特征过多的话也会带来麻烦，例如上图中的右图，我们用5阶多项式拟合: $y=sum_{j=0}^5 heta_jx^j$. 尽管曲线拟合了所有的样本点，但它很难用作预测房价的方式。
在没有明确的定义情况下，我们可以说图1是欠拟合(underfitting)的一个例子：模型没有很好的捕捉到数据结构。而图3是过拟合(overfitting)的一个例子。
讲这个例子的目的是为了引出非参数学习。线性回归是参数化学习算法的一个例子。所谓参数化学习，是指实际训练前都需要对数据遵从的模型进行一个假定，这个假定可以是一个已知的概率分布或混合分布。上面的例子告诉我们，对于一个参数化的学习算法，为了达到良好的性能，特征的选取是很重要的。参数方法的优点是把估计概率密度、判别式或回归函数问题归结为估计少量参数值，缺点则是模型假定并非总成立，当不成立时就会出现很大的误差。
这时我们就需要使用非参数方法，其中我们只需要假定一个事实：即相似的输入具有相似的输出。因为我们一般都认为世界的变化时平稳、量变到质变的，因此无论是密度、判别式还是回归函数都应当缓慢地变化。在这样的非参数估计（nonparamitric estimation）中，局部实例对于密度的影响就显得颇为重要，而较远的实例影响则较小。这里，我们将讨论局部加权线性回归-当训练数据足够大的时候，特征的选取就不那么重要了。
首先对比一下原始的线性回归和局部加权线性回归的区别。为了预测在一个特定点$x$的目标值$y$，
这里的$w^{(i)}$是非负的权值。直觉上，如果
一个相当标准但不唯一的权值选择方式是：
egin{equation*} w^{(i)}=exp(-frac{(x^{(i)}-x)^2}{2 au^2}) end{equation*}
线性回归是先建模型，建好以后用模型来预测，且模型建好以后，训练集合的数据不再有用。局部加权线性回归的在预测点附近选取局部数据，之后对子集执行线性回归。
局部加权线性回归是我们接触的第一个非参数学习算法。之前的线性回归是参数学习算法，因为它包含了有限且个数固定的参数(即$ heta_i$)参与数据拟合。这种方法在得到$ heta$以后不再需要训练数据了，而局部加权算法是需要的。术语“非参数”指的是，参数数目随着训练集的增大而现行增加的，你算法需要用到的东西会随着训练集合线性增长。
6. 讨论：一些假设的概率学解释
继续之前，容某吐槽一下：其实我也不知道吴老师为啥会讲这一部分内容。如果上面是教我们如何做的话，这部分讨论就是在叫我们为何能这样做？虽然内容连贯一致，但总担心会有童鞋反被迷糊和绕晕:(
友情提示，上面空了一行...好奇心比较重的童鞋可以用鼠标选中一下。只不过是选中一下，保证让你买不了吃亏买不了上当
当面对参数化学习，例如最初的线性回归时，为什么线性模型$h_{ heta}(x)= heta_0+ heta_1x_1+ heta_2x_2$和最小均方误差定义的损失函数$J( heta)$是合理的选择呢？这里我们给出一系列的概率学假设，在这些假设条件下，最小均方与线性回归确实是非常合理的。
首先，我们假设目标变量与输入变量之间有如下关系：
egin{equation*} y^{(i)}= heta^Tx^{(i)}+epsilon^{(i)},end{equation*}
其中，$epsilon^{(i)}$是误差项，例如随机噪声。进一步假设$epsilon^{(i)}$是独立同分布的(Independently and Identically Distributed, IID)，它们都服从均值为0，方差为$sigma^2$的高斯分布，即$epsilon^{(i)} sim N(0, sigma^2)$，它的密度函数为：
egin{equation*}p(epsilon^{(i)})=frac{1}{sqrt{2pi}sigma}exp(-frac{(epsilon^{(i)})^2}{2sigma^2}) end{equation*}
由此我们可以推出：
egin{equation*} p(y^{(i)}|x^{(i)}; heta) =frac{1}{sqrt{2pi}sigma}exp(-frac{(y^{(i)}- heta^Tx^{(i)})^2}{2sigma^2}) end{equation*}
因此变量$y^{(i)}|x^{(i)}; heta$服从均值为$ heta^Tx^{(i)}$，方差为$sigma^2$的高斯分布，即$y^{(i)}|x^{(i)}; heta sim mathcal{N}( heta^Tx^{(i)}, sigma^2)$
注意，表达式$p(y^{(i)}|x^{(i)}; heta)$的含义是：给定$x^{(i)}$, 且以$ heta$为参数下的$y^{(i)}$的分布。由于$ heta$本身不是随机变量，因此我们不能把$ heta$当做条件写成$p(y^{(i)}|x^{(i)}, heta)$的形式。
给定$X$和$ heta$，$y^{(i)}$的分布$p(y^{(i)}|x^{(i)}; heta)$是什么呢？它已经由上面的公式给出，通常我们会把这个函数当做$X$或者$y$的函数。然而，在训练集中，$x$和$y$都是已知的，目的是估计$ heta$。那么，此时可以将这个函数当做参数$ heta$的函数。当把它作为参数$ heta$的函数时，我们称之为似然函数。
egin{equation*} L( heta)=L( heta;X,vec y)=p(vec y|X; heta)end{equation*}
注意到$epsilon^{(i)}$之间独立同分布的性质，上式可以写成3：
egin{eqnarray*} L( heta) & =& prod_{(i=1)}^m p(y^{(i)}| x^{(i)}; heta) \ & = & prod_{i=1}^mfrac{1}{sqrt{2pi}sigma}exp(-frac{(y^{(i)}- heta^Tx^{(i)})^2}{2sigma^2}) end{eqnarray*}
现在这个概率模型给定了$y^{(i)}$和$x^{(i)}$之间的关系，我们应该怎么选择最佳的$ heta$呢？按照最大似然估计的原则，应当选择使得似然函数最大的$ heta$。
在实际计算的时候，我们可以计算任何似然函数的严格增函数。因此，我们我们选择最大化对数似然函数：
egin{eqnarray*} ell( heta) & = & logL( heta) \ & = & logprod_{i=1}^m frac{1}{sqrt{2pi}sigma}exp(-frac{(y^{(i)}- heta^Tx^{(i)})^2}{2sigma^2}) \ & = & sum_{i=1}^mlogfrac{1}{sqrt{2pi}sigma}exp(-frac{(y^{(i)}- heta^Tx^{(i)})^2}{2sigma^2}) \ & = & mlogfrac{1}{sqrt{2pi}sigma}-frac{1}{sigma^2}cdotfrac{1}{2}sum_{i=1}^m(y^{(i)}- heta^Tx^{(i)})^2 end{eqnarray*}
最大化似然函数等价于最小化：
egin{equation*} frac{1}{2}sum_{i=1}^m(y^{(i)}- heta^Tx^{(i)})^2 end{equation*}
上面就是$J( heta)$
egin{equation*} frac{1}{2}sum_{i=1}^m(y^{(i)}- heta^Tx^{(i)})^2 end{equation*}
也就是说，我们假定了误差服从高斯分布，然后把最大似然估计应用于线性回归的线性模型，最终得到了和直接使用最小均方误差形式相同的结果。
总结：对于回归问题，应当根据具体的应用场景选择合适的算法。例如，
1. 参数or非参数学习：根据训练集合，好的模型是否容易确定。如果模型容易确定，那么可以用参数学习比如线性回归等，如果模型不容易确定，那么就可以用非参数模型比如局部加权回归，以减小回归对于模型的依赖。
2. 线性or非线性回归：根据训练集合是否适合使用线性模型建模。
3. 批梯度下降or随机梯度下降：根据训练集合的大小，如果训练集合规模庞大，随机梯度下降是很合适的。