斯坦福机器学习教程之——线性回归

目录

UFLDL Tutorial讲解
引言
 线性回归概述
1. LMS 算法
2. 正则方程组
2.1 矩阵求导
 2.2 回顾最小二乘法
 2.3 线性代数方法推导正则方程组
 3. 概率化解释
3.1. 极大似然估计法详解
 4. 局部加权线性回归
4.1 机器学习非参数化方法
 后续还需学习的知识
写该博客中用到的Markdown技巧
Reference

UFLDL Tutorial讲解

这是教程中提供的Lecture Note。里面详细介绍了Linear Regression的内容。由于该pdf的内容很丰富，讲解也很经典，在看完以后就大概翻译了一下有关线性回归的内容，里面也有一些可以后续继续学习的内容。

引言

首先，文中假设我们有一个数据集，给出了来自Portland的47个房子的居住面积和价格。

然后绘制出了房子的居住面积和价格之间的散点图。

通过这些数据，如何通过居住面积去去预测这个地区的其他房子的价格呢？

我们把$x^{(i)}$用来代表输入变量，或者叫做输入特征（input feature），用$y^{(i)}$来代表输出，或者用来做预测的目标变量(target variable)。把一对$(x^{(i)},y^{(i)})$叫做训练样例（training example）,把用来做学习的样例的列表叫做训练集（training set）。注意到上标$(i)$只是简单地表示训练集的索引，和指数运算并没有半毛钱关系。用$X$来表示输入数值的空间，$Y$表示输出值的空间，在这个例子中$X=Y=\Bbb R$。

为了描述更加正规化地描述监督式学习的问题，我们的目标是给定一个训练集，去学习一个函数$h:X \mapsto Y$使得h(x)是一个对相应的y值的一个好的预测。由于一些历史的原因，我们把这个函数h称为一个hypothesis(假设)。通过图像展示整个学习的过程如下：

当我们需要预测的目标变量是连续的，比如我们上面的关于房子的例子，我们把这样的问题叫做一个回归(regression)问题。当y只能取少数量的离散的值时（比如如果给出了居住面积，我们想去预测一个住所是一个房子还是公寓），我们把这样的问题成为分类(classification)问题。

线性回归概述

为了让我们的住房问题更加有趣，让我们考虑一个稍微更丰富一些的我们知道每个房子有多少卧室的数据集。
在在个问题里，x是一个二维向量在$\Bbb R^2$空间中。比如，$X_{1}^{(i)}$是训练集中第i个房子的居住面积，$X_{2}^{(i)}$是卧室的数量。（通常，当设计一个learning学习的问题时，它将会依赖你决定去选择什么特征，所以如果你不在Portland去收集住房数据，你可能也会决定包含其他特征比如每个房子是否有一个壁炉，浴室的数量等等）我们将在后面更多地讨论特征选择，但是现在让我们认为这些特征都是给定的。）

为了进行监督式学习，我们必须确定我们如何在电脑中表示hypothese h。作为初始的选择，让我们用一个关于x的线性函数去近似表示目标函数y。

$h_{\theta}(x) = \theta_{0} + \theta_{1}x_{1} + \theta_{2}x_{2}$

在这里，$\theta_{i}$表示用来参数化从$X$映射到$Y$的线性函数空间的参数（也称为权重）。当没有混淆的风险时，我们把$\theta$作为下标，变成$h_{\theta}(x)$，并且把这个式子直接简写成h(x)。为了简化记号，我们引入一个惯例，让$x_{0}=1$，这里$x_{0}$表示截距，所以式子变成下面的样子：

$h(x) = \sum_{i=0}^{n} \theta_{i}x_{i} = \theta^{T}x$

在上面式子的最右边我们看到的$\theta$和x都是向量。这里的n表示输入变量的个数（不包括截距$x_{0}$）。（个人理解：这里的x相当于是一个n维向量，具有n个特征，每一维表示一个特征，这个n不是训练资料的数量）。

现在，给定一个训练集，我们如何选择或者说去学习参数$\theta$呢？一个合理的方法看起来好像是让h（x）这个假设更加接近于目标函数y(个人理解：这样表示h(x)预测得更加接近真实值，表示预测更准确)，至少对于我们训练的资料是这样的。为了让这种想法更加正规一点，我们定义了下面的函数用来度量对于每一个$\theta$，每个样例$x^{(i)}$对应的$h(x^{(i)})$与相应的实际（目标）结果$y^{(i)}$之间离得有多近（即准确程度有多高）。我们定义估值函数(cost function)（也可以叫价值函数，成本函数，损失函数等等）

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

如果你之前已经看过线性回归，你可能把这个式子当成引出普通最小二乘法（Ordinary Least Square:OLS）的最小二乘估值函数。不管你之前是否看过它，让我们继续，我们最终将会展示它只是更广阔的算法家族中的一个特例。

下面插入一些查到的资料：

最小二乘法的资料

从这个博客中摘录了一段话：

对于一元线性回归模型, 假设从总体中获取了n组观察值（X1，Y1），（X2，Y2）， …，（Xn，Yn）。对于平面中的这n个点，可以使用无数条曲线来拟合。要求样本回归函数尽可能好地拟合这组值。综合起来看，这条直线处于样本数据的中心位置最合理。选择最佳拟合曲线的标准可以确定为：使总的拟合误差（即总残差）达到最小。有以下三个标准可以选择：

（1）用“残差和最小”确定直线位置是一个途径。但很快发现计算“残差和”存在相互抵消的问题。

（2）用“残差绝对值和最小”确定直线位置也是一个途径。但绝对值的计算比较麻烦。

（3）最小二乘法的原则是以“残差平方和最小”确定直线位置。用最小二乘法除了计算比较方便外，得到的估计量还具有优良特性。这种方法对异常值非常敏感。

1. LMS 算法

我们想选择$\theta$去最小化$J(\theta)$。为了这么做，让我们一个搜索的算法来开始对$\theta$的某个“初始的猜测”，并且不断地（迭代）改变$\theta$使得$J(\theta)$的值更小，直到像希望的一样，我们聚集$\theta$到一个值使得$J(\theta)$最小。特殊地，让我们考虑梯度下降(gradient descent)算法，它开始于某个初始的$\theta$，然后不断执行迭代更新：

$\theta_{j} := \theta_{j} - \alpha \frac{\partial}{\partial x} J(\theta)$

(这个更新对于所有的值$j = 0,…,n$是同时执行的)
这里，$\alpha$被叫做学习速率。这是一个非常自然的算法，它不断地在J函数下降最快的方向选择走一步。
为了实现这个算法，我们不得不算出上面这个式子右边这部分的偏导数。让我们先算出当我们只有一个训练样本（x,y）时的情形，所以我们可以忽略函数J的定义中的那个求和部分。这样我们就有：

$\frac{\partial}{\partial \theta_{j}} J(\theta) = \frac{\partial}{\partial \theta_{j}} \frac{1}{2} (h_{\theta}(x)-y)^{2}$ $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = 2 \cdot \frac{1}{2}(h_{\theta}(x)-y) \cdot \frac{\partial}{\partial \theta_{j}}(h_{\theta}(x)-y)$ $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = (h_{\theta}(x)-y) \cdot \frac{\partial}{\partial \theta_{j}}\left (\sum_{i=0}^{n} \theta_{i}x_{i} -y \right)$ $\ \ \ \ = (h_{\theta}(x)-y) x_{j}$

对于单个的训练样例，它给了一个更新的规则：

$\theta_{j} := \theta_{j} + \alpha (y^{(i)} - h_{\theta}(x^{(i)}))x_{j}^{(i)}$

这个规则叫做LMS更新规则(LMS代表”least mean squares”,即最小均方差)，它也被叫做Widrow-Hoff学习规则。

个人理解如下：

注意这个规则写成下面的形式其实更容易理解一些：

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

相当于是沿着梯度的反方向走，即沿着梯度下降方向进行更新。

这个规则有一些属性看起来自然和直观。举个例子，更新的梯度是与错误/偏差（error） $y^{(i)} - h_{\theta}(x^{(i)})$。因此，例如，如果我们遇到一个我们的预测几乎和真实的值$y^{(i)}$差不多的训练样本，那么我们就会发现没有必要去修改参数。相反，如果我们的预测$h_{\theta}(x^{(i)})$有很大的误差（它离$y^{(i)}$很远，即差值很大），那么对参数的改变就很大。

我们已经导出了只有一个训练样本的LMS规则。对于一个多于一个样本的训练集，有两种方式修改这个方法。第一种是通过下面的算法替换它：

　Repeat until convergence(循环直到收敛) {
$\ \ \ \ \ \ \ \ \ \theta_{j} := \theta_{j} + \alpha \sum_{i=1}^{m}(y^{(i)} - h_{\theta}(x^{(i)}))x_{j}^{(i)} $ (对于每个j)
　}

读者可以很容易地证明在上面更新规则中求和式子中的值正是$\partial J(\theta) / \partial \theta_{j}$(对于最初始的J的定义)。所以，这是在原始的估值函数J上简单地做梯度下降(gradient descent)。这个方法在每一步都要扫描整个训练集中的每一个样例，被叫做批量梯度下降（Batch gradient descent）。我们注意到，通常梯度下降会被局部极小值所影响，我们在这里提出的线性回归的最优化问题只有一个全局最优解，没有其他局部最优解。因此，梯度下降法总是会聚集到全局的最小值处。

(假设学习速率$\alpha$不是很大，太大就发散了，不会收敛到最小值。用小球从山坡上向谷底滚的例子来说，如果$\alpha$很大，相当于单位时间内滚下的步长很长，这样当步长太长时，就会一下子滚到对面山坡上，继续迭代就会在对面山坡上向上滚，这样永远也无法达到谷底，即无法达到最优解处。因而$\alpha$不能太大)

实际上，J是一个凸的二次函数（国外喜欢把开口向上的二次函数叫做凸函数，国内教学正好相反，把这种开口向上的成为凹函数）。这里有一个最小化二次函数的梯度下降法的例子。

上面的椭圆展示了一个二次函数的等高线，也展示了梯度下降法采用的轨迹，初始点是(48，30)。图中的x（用线段连起来的）标记了梯度下降法逐次通过的$\theta$值。

当我们运行批量梯度下降算法去在我们预测的训练集上拟合$\theta$时，通过学习一个居住面积的函数去预测房价，我们得到$\theta_{0} = 71.27, \theta_{1} = 0.1345$。如果我们把$h_{\theta}(x)$作为x(住房面积)的函数，使用训练资料来画图，我们就可以得到以下图像：如果卧室的数量也被当做一个输入特征算在内的话，我们得到$\theta_{0} = 89.60, \theta_{1} = 0.1392,\theta_{2} = -8.738$。

以上的结果是通过批量梯度下降法得到的。有一种替代批量梯度下降的方法，它运行效果很好。（个人理解：批量梯度下降算法在m的值很大的时候，每次都需要计算求和的式子，会导致算法效率急剧下降）考虑下面的算法：

　Loop(循环)　{
$\ \ \ \ \ \ \ for(i = 1 \ to \ m)${
$\ \ \ \ \ \ \ \ \ \ \ \theta_{j} := \theta_{j} + \alpha (y^{(i)} - h_{\theta}(x^{(i)}))x_{j}^{(i)}$ (对于每个j)
　$\ \ \ \ $}
　}

在这个算法中，我们反复地在训练集上运行，而且每次我们遇到一个训练样本时，我们就根据关于单个训练样本的错误的梯度值来更新参数。这个算法被称为随机梯度下降(也称作增量梯度下降)。

鉴于批量梯度下降法在每走一步的之前都要扫描一遍整个训练集——如果m很大的时候这将是一个非常耗时的操作——随机梯度下降法可以立即开始进步，并且学习每一个它看过的样例后持续地进步。

大多数时候，随机梯度下降法可以比批量梯度下降法更快地得到趋近最小值的$\theta$值。(注意虽然如此，它也可能永远无法汇聚到最小值处，并且参数$\theta$会不断在$J(\theta)$的最小值附近波动。但实际上大部分处在最小值附近的值都可以认为它是真实最小值的合理的近似)。由于这些原因，尤其当训练集很大时，随机梯度下降法经常比批量梯度下降法表现更好。

总结一下：

批量梯度下降算法运算量较大，依次迭代一般不会到达最优解，因此随着迭代次数增加，当数据量很大时，算法效率会很低。但它受到噪声等因素影响较小。

随机梯度下降算法运算量较小，当数据集很大时，一般不需要扫描完整个数据集就能达到最优解。但是它容易受到噪声影响，因为每一次迭代都是对一组数据求相应的梯度，然后更新$\theta$值。这样，每次迭代的方向不一定是全局最优化方向，会有一些偏差。（但是偏差不会对最终的结果造成太大影响，最后的结果往往是在全局最优解附近）

下面是自己用matlab实现的梯度下降的动图：

Matlab实现梯度下降及Matlab绘制动态图详见我的这篇博客。

2. 正则方程组

(这个标题是Normal Equations，查了半天资料，貌似是当年高斯命名的)

梯度下降法给出了一种最小化J的方法。让我们讨论用第二种方法来做，这一次我们明确地执行最小化的（动作），也不再采用迭代的算法。在这个方法中，我们将要最小化J，直接对每个$\theta_{j}$求导,并把它们都设为0（个人理解：这就是求梯度，让梯度向量变成零向量，即到达谷底，没有办法继续向下，因此为最小值处）。为了确保我们做这些（运算）不用写大量的代数和满篇的矩阵求导式子，让我们先介绍一些做矩阵运算的记号。

2.1 矩阵求导

对于一个函数$\Bbb R^{m \times n} \mapsto \Bbb R$，它从$m \times n$维矩阵空间映射到实数空间，我们定义f对A的导数为：

$\nabla_{A}f(A) = \left\lbrack\matrix{\frac{\partial f}{\partial A_{11}} & \ldots & \frac{\partial f}{\partial A_{1n}} \cr \vdots & \ddots & \vdots \cr \frac{\partial f}{\partial A_{m1}} & \ldots & \frac{\partial f}{\partial A_{mn}} \cr }\right\rbrack$

因此，梯度$\nabla_{A}f(A)$本身就是一个$m \times n$矩阵，它的(i,j)元素表示$ \partial f / \partial A_{ij} $。例如，我们假设$A = \left\lbrack\matrix{A_{11} & A_{12} \cr A_{21} & A_{22} \cr }\right\rbrack$是一个$2 \times 2$矩阵，而且函数$f: \Bbb R^{2 \times 2} \mapsto \Bbb R$可以给出：

$f(A) = \frac{2}{3}A_{11} + 5A_{12}^{2} + A_{21}A_{22}$

这里，$A_{ij}$表示矩阵A的第$(i,j)$位置的元素。于是我们就有

$\nabla_{A}f(A) = \left\lbrack\matrix{\frac{2}{3} & 10A_{12} \cr A_{22} & A_{21} \cr }\right\rbrack$

我们介绍矩阵的“迹”操作，写作$tr$。对于一个$n \times n$方阵A,它的迹表示主对角线的元素之和。

$trA = \sum_{i=1}^{n}A_{ii}$

如果a是一个实数(即$1 \times 1$矩阵)，那么$tr a = a$。（如果你之前没有看过这个操作的记号，你应该把A的迹当成$trA$或者一个应用在矩阵A上的”迹”函数，他通常在写的时候不带参数）

对于两个矩阵A和B来说，矩阵迹的操作有一些性质。比如当AB为方阵时，我们就有$trAB = trBA$。(自己验证一下！)把它当做推论，我们就可以得到如下式子：

$trABC = trCAB = trBCA$ $trABCD = trDABC = tr CDAB = tr BCDA$

下面的迹操作的性质非常好证明。这里，A和B都是方阵，a为实数。

$trA = trA^{T}$ $tr(A+B) = trA + trB$ $traA = atrA$

我们现在的陈述中没有证明一些矩阵求导的式子。公式(4)只应用在A为满秩矩阵的时候，其中$|A|$表示A的行列式。我们有如下式子：

$\nabla_{A}trAB = B^{T} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$ $\nabla_{A}f(A) = (\nabla_{A}f(A))^{T}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)$ $\nabla_{A}trABA^{T}C = CAB + C^{T}AB^{T}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (3)$ $\nabla_{A}|A| = |A|(A^{-1})^{T}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (4)$

为了让我们的矩阵记号更加具体，让我们现在仔细地解释一下第一个公式的意思。假设我们有某个固定的矩阵$B \in \Bbb R^{m \times n}$。我们可以根据$f(A) = trAB$定义一个函数$f: \Bbb R^{m \times n} \mapsto \Bbb R$。注意到这个定义很有意思，因为如果$A \in \Bbb R^{m \times n}$,那么$AB$就是一个方阵，我们就可以对它应用”迹”的操作。因此，$f$确实将$\Bbb R^{m \times n}$映射到了$\Bbb R$。然后我们就可以应用我们定义的矩阵求导式子去找到$\nabla_{A}f(A)$，而$A$它自己是一个$m \times n$维矩阵。上面的公式$(1)$说明了$A$矩阵中的$(i,j)$元素会和$B^{T}$中的$(i,j)$元素相乘，即$B_{ji}$这个元素。

公式（3）的证明非常简单。(知乎上有人给出如下几种做法)：

方法一：

$\frac{\partial A_{ij}B_{jk}A_{lk}C_{li}}{\partial A_{mn}}=A_{ij}B_{jn}C_{mi}+B_{nk}A_{lk}C_{lm}=C_{mi}A_{ij}B_{jn}+C_{lm}A_{lk}B_{nk}$

　　其中$A_{lk}$实际上是$A_{kl}^{T}$，因为转置矩阵的性质$A_{ij}^{T}=A_{ji}$,$A_{ji}^{T}=A_{ij}$,所以这里写成了$A_{lk}$。整个式子的核心实际上是求那些式子可以产生$A_{mn}$，然后得到它的系数即为求得的导数的结果。

另一种方法是这样的，这种方法的思想和一阶导数中讲到的拉格朗日中值定理很像：

$\begin{array}{ll} & & \mathrm{tr}{(A + dA)B(A + dA)'C} \\ & = & \mathrm{tr}(ABA'C + dA\times BA'C + AB\times (dA)'\times C) + o(dA) \\ & = & \mathrm{tr}(ABA'C) + \mathrm{tr}((C'AB')'\times dA) + \mathrm{tr}((CAB)'\times dA) + o(dA) \\ & = & \mathrm{tr}(ABA'C) + \langle C'AB', dA\rangle + \langle CAB, dA\rangle + o(dA) \\ & = & \mathrm{tr}(ABA'C) + \langle C'AB' + CAB, dA\rangle + o(dA) \end{array}$

等式(4)可以逆矩阵的伴随矩阵表示。在学习线性代数的逆矩阵时我们知道，

$A^{-1} = \frac{A^{*}}{|A|}$

其中，$A^{*}$表示A矩阵的伴随矩阵，如下所示：

$A^{*} = \left\lbrack\matrix{A_{11} & A_{21} & \ldots & A_{n1} \cr A_{12} & A_{22} & \ldots & A_{n2} \cr \vdots & \vdots & \ddots & \vdots\cr A_{1n} & A_{2n} & \ldots & A_{nn} \cr}\right\rbrack$

$A^{*}$矩阵中的元素$A^{i}(i,j)$表示原A矩阵元素$a(i,j)$的代数余子式。

$A_{ij}=(-1)^{i+j}M_{ij}$

$M_{ij}$表示元素$a_{ij}$的余子式，即去掉第$i$行和第$j$列后形成的$(n-1)$阶行列式。

我们记

$A^{'} = \left\lbrack\matrix{A_{11} & A_{12} & \ldots & A_{1n} \cr A_{21} & A_{22} & \ldots & A_{2n} \cr \vdots & \vdots & \ddots & \vdots\cr A_{n1} & A_{n2} & \ldots & A_{nn} \cr}\right\rbrack$

则有$A^{*} = (A^{'})^{T}$成立。

$M_{ij}$是矩阵$A^{'}$对应的行列式。根据行列式的定义我们得到，$|A| = \sum_{j} a_{ij}A_{ij}^{'}$，即$A$的行列式等于行列式中任意一行或一列每个元素与其代数余子式积的代数和。而它们的代数余子式正好是矩阵$A^{'}$中的元素。所以在求导以后得到的就是导数矩阵就是$A^{'}$矩阵。

所以对于公式$((4)$，我们可以得到：

$A^{-1} = \frac{A^{*}}{|A|} = \frac{(A^{'})^{T}}{|A|}$ $(A^{'})^{T} = |A|A^{-1} \ \ \ \ \ \ \ \ \$ $A^{'} = |A|(A^{-1})^{T} \ \ \ \ \ \ \ \ \$ $\ \ \ \ \ \ \nabla_{A}|A| = A^{'} = |A|(A^{-1})^{T}$

证毕。

2.2 回顾最小二乘法

有了矩阵导数的这些工具后，现在让我们前进去找到最小化$J(\theta)$的$\theta$值的闭式解（close-form solution）。

下面穿插一点关于闭式解的解释：

数值解(numerical solution)是在特定条件下通过近似计算得出来的一个数值，是采用某种计算方法,如有限元的方法, 数值逼近,插值的方法, 得到的解.别人只能利用数值计算的结果。

解析解(analytical solution)就是给出解的具体函数形式，从解的表达式中就可以算出任何对应值，就是一些严格的公式,给出任意的自变量就可以求出其因变量,也就是问题的解, 他人可以利用这些公式计算各自的问题.所谓的解析解是一种包含分式、三角函数、指数、对数甚至无限级数等基本函数的解的形式。解析解为一封闭形式〈closed-form〉的函数，因此对任一独立变量，带入解析函数求得正确的相依变量。因此，解析解也被称为闭式解（closed-form solution）。
eq: x^2=2
solution: x=sqrt(2) – （解析解）
x=1.414 –（数值解）

下面我们开始用向量的形式重写函数J。

给定一个训练集，定义设计矩阵（design matrix） X是一个$m \times n$矩阵(实际上是$m \times (n+1)$,如果加上截距的话)，在它的行中包含了训练样例的输入变量。

（根据维基百科查到的解释：设计矩阵就是一个对象集合中的自变量（自变量（independent variable）也称为解释变量(explanatory varible),因变量（dependent variable）也称为应变量（response variable））的值组成的矩阵）

$X = \left\lbrack\matrix{-- (x^{(1)})^{T} -- \cr -- (x^{(1)})^{T} -- \cr \vdots \cr -- (x^{(m)})^{T} -- \cr}\right\rbrack$

我们让$\overrightarrow y$作为一个m维列向量，包含了来自训练集的所有目标值。

$\overrightarrow y = \left\lbrack\matrix{ y^{(1)} \cr y^{(2)} \cr \vdots \cr y^{(m)}\cr}\right\rbrack$

现在，因为$h_{\theta}(x^{(i)}) = (x^{(i)})^{T}\theta $，我们可以很容易地证明

$X\theta - \overrightarrow y = \left\lbrack\matrix{ h_{\theta}(x^{(1)})-y^{(1)} \cr \vdots \cr h_{\theta}(x^{(m)})-y^{(m)} \cr}\right\rbrack$

因此，根据向量中的一些事实，我们得到等式$z^{T}z=\sum_{i}z_{i}^{2}$

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

最后，为了最小化J，让我们找到它对$\theta$的导数。结合等式(2)和(3)，我们得到

$\nabla_{A^{T}}trABA^{T}C = B^{T}A^{T}C^{T} + BA^{T}C\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (5)$

因此，有下面式子成立（懒得写公式，直接上图了）：

上面这个图里的式子实际上可以类比代数中的二项展开式，然后用之前证明过的推论来做梯度式子的代换。

在第三步，我们用到了实数的迹是一个实数的事实（所以求导后为0了）。第四步用到了$trA = trA^{T}$的事实，第五步我们用到了公式(5)和公式(1)，其中$A^{T} = \theta,B = B^{T} = X^{T}X, C=I$。为了最小化J，我们把它的导数都设置为0，然后得到正则方程组（用向量表示的方程组形式）：

$X^{T}X\theta = X^{T}\overrightarrow y$

因此，最小化$J(\theta)$的$\theta$ 被以闭式解的形式通过以下等式给出：

$\theta = (X^{T}X)^{-1}X^{T}\overrightarrow y$

2.3 线性代数方法推导正则方程组

下面引用一篇用线性代数知识来详细推导正则方程组的文章：

由于文章里的图太丑，我用台大林轩田老师《机器学习基石》课程中对于该部分用向量法证明的图：

个人理解如下：

这里涉及到向量空间的概念，实际上从向量的角度来看，我们假设X矩阵如下：

$X = \left\lbrack\matrix{x_{11} & x_{12} & \ldots & x_{1n} \cr x_{21} & x_{22} & \ldots & x_{2n} \cr \vdots & \vdots & \ddots & \vdots\cr x_{n1} & x_{n2} & \ldots & x_{nn} \cr}\right\rbrack$ $\theta = \left\lbrack\matrix{ \theta_{1} \cr \theta_{2} \cr \vdots \cr \theta_{n} \cr}\right\rbrack$ $\overrightarrow y = \left\lbrack\matrix{ y^{(1)} \cr y^{(2)} \cr \vdots \cr y^{(m)}\cr}\right\rbrack$

因为$X\theta = y$。其中X为$m \times n$矩阵，$\theta$为n维列向量，$\y)为m维列向量。

当等式成立时，有$\sum_{j=1}^{n} \theta_{j}x_{ij} = y_{i} (i=1,2,…,m)$。所以设矩阵$X$的n个列向量分别为$X_{1},X_{2},…,X_{n}$。则$\overrightarrow y$可以表示成X矩阵这个向量空间的n个列向量的线性组合。

$\overrightarrow y = \sum_{i=1} ^{n} \theta_{i}\overrightarrow X_{i}$

由于$\overrightarrow \theta$所有的$\theta_{i}$值不可能全都为0，所以根据上面这个式子我们可以得出，y和X向量空间中的n个列向量线性相关。而且y也由它们线性表出了。根据线性代数中线性方程组的理论，这也说明y向量在X的N个列向量构成的向量空间中，同时也说明矩阵X是满秩矩阵，即可逆矩阵(可逆矩阵首先得保证是n阶方阵)。它这个N维的列向量每一个向量都可以作为向量空间的基，而这个基也就是台大林轩田老师在课程中讲到的X的自由度，所以在上面《机器学习基石》的课件中error所剩下的自由度就只有(N-(d+1))了，它这里的N相当于我们这里面的m，它这里的d相当于是我们的n，(d+1)是加上了截距后的结果。

此外，还要注意用不同眼光看矩阵，它表示不同的含义。

矩阵既是一种线性变换，同时也表示一个向量空间。

3. 概率化解释

当我们面对一个回归问题时，为什么线性回归，尤其是为什么最小二乘估价函数J会是一个合理的选择？在这一节，我们给出了一堆概率的假设，在这些假设下，最小二乘法回归作为一种自然的算法被导出。

让我们假设目标变量和输入通过以下的等式关联：

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

$\epsilon^{(i)}$是一个误差量，它捕获了非模型化的影响（比如如果有一些特征和预测房价非常相关，但是我们在做回归的时候却把它漏掉了）或者随机的噪声。让我们进一步假设$\epsilon^{(i)}$是独立同分布（IID:Independently and identically distributed）的均值为0，方差为$\sigma^{2}$的高斯分布（正态分布）。我们可以写成$\ \epsilon^{(i)} \sim N(0,\sigma^{2})\ $。$\epsilon^{(i)}$的概率密度如下：

//这里是注释：

用$\epsilon^{(i)} = \theta^{T}x^{(i)} - y^{(i)}$代换上式中的$\epsilon^{(i)}$然后才可以得到下面的式子。如果把$\theta$看成一个相对的常量(比如$\theta = \theta_{0}$)，$\epsilon^{(i)}$相当于是一个含有$x^{(i)}$和$y^{(i)}$两个变量的二元函数。上面的式子相当于就是$x^{(i)}$和$y^{(i)}$的联合概率密度。

这表明
这个记号$p(y^{(i)}|x^{(i)};\theta)$表示这是在条件$X=x^{i}$下和参数为$\theta$时$y^{(i)}$的概率分布。注意到我们不应该把$\theta$当成联合分布$p(y^{(i)}|x^{(i)},\theta)$，因为$\theta$不是一个随机变量。我们也可以把$y^{(i)}$的部分写成$y^{(i)}|x^{(i)};\theta \sim N(\theta^{T}x^{(i)},\sigma^{2})$。

给出X和$\theta$，$y^{(i)}$的分布是什么样的？数据的概率可以表示成$p(\overrightarrow y|X;\theta)$。这个量可以被看做对于固定的$\theta$，$\overrightarrow y$的函数（也可以看成是X的函数）。当我们希望明确地把它看成一个$\theta$的函数，我们将把这个函数称作似然函数（likelihood function）。

$L(\theta) = L(\theta;X,\overrightarrow y) = p(\overrightarrow y,X;\theta)$

注意根据$\epsilon^{(i)}$的独立性假设，这个可以被写成：现在，给出关联$y^{(i)}$和$x^{(i)}$的概率模型，什么是一个合理的方法来选择我们对参数$\theta$的最佳估测？最大似然估计（也叫极大似然估计，Maxinum Likelihood）理论告诉我们需要选择$\theta$使得数据发生的可能性更大。我们需要选择$\theta$来最大化$L(\theta)$。

代替最大化$L(\theta)$，我们也可以最大化任何严格递增的对$L(\theta)$进行复合后的函数。尤其地，如果我们对似然函数取对数后再求最大值，这样求导会简单一些。我们把取对数后的函数叫做对数似然函数$l(\theta)$。因此，最大化$l(\theta)$给出了和最小化$\frac{1}{2}\sum_{i=1}^{m}(y^{(\theta)}-\theta^{T}x^{(i)})^{2}$一样的结果。我们把它作为$J(\theta)$，我们最初的最小二乘估值函数。

总结一下：在以前的在数据上的概率假设之下，最小二乘回归对应于找到$\theta$的极大似然估计。因此一系列在最小二乘回归下的假设是很合理的作为一种自然的方法。它仅仅做极大似然估计。（对于最小二乘法而言，成为一个好的、合理的程式，基于概率的假设一点也不是必须的，实际上也有其他自然的假设可以用来证明最终的结果）。

还需要注意，在我们之前的讨论中，我们最终对$\theta$的选择并不依赖于$\sigma^{2}$是多少，实际上，我们已经得出相同的结果即使$\sigma^{2}$是不知道的。当我们讨论指数家族和我们还将会在后面再次用到这些事实。

3.1. 极大似然估计法详解

极大似然估计的依据是：概率最大的事件最可能发生。一次试验就出现的事件(应该)有较大的概率。

极大似然原理：

若一次试验中有n个可能的结果$A_{1},…A_{n}$，现做一次试验，若事件$A_{i}$发生了，则认为事件$A_{i})在这n个可能结果中出现的概率最大。

一次试验就出现的事件(应该)有较大的概率，极大似然估计就是在一次抽样中，若得到观测值$x_{1},…,x_{n}$则选取$\hat \theta(x_{1},…,x_{n})$作为$\theta$的估计值，使得$\theta = \hat \theta(x_{1},…,x_{n})$时，样本出现的概率最大。

4. 局部加权线性回归

考虑这个问题：从$x \in \Bbb R$去预测y。最左边的图展示了用$y=\theta_{0}+\theta_{1}x$对一个数据集进行拟合的结果。我们看到数据点并不是都在直线上，所以它拟合的效果并不好。

相反，如果我们添加一个额外的特征$x^{2}$，并且用$y=\theta_{0}+\theta_{1}x+\theta_{2}x^{2}$。然后我们就有了一个稍微好一点的对数据的拟合（函数）。（看中间的这张图）根据以上的结论，我们有一个天真的猜测，就是当我们添加的特征越多时，好像拟合的效果越好。然而，如果添加太多的特征也会有危险：最右边的图使用一个五次多项式$y=\sum_{j=0}^{5} \theta_{j}x^{j}$来拟合的结果。我们看到即使拟合曲线很好地穿过了所有的数据点，我们也不认为它是对不同住房面积（x）对应的房价（y）的一个好预测。在没有正式定义这些术语的情况下，我们说最左边的这个图展示了一个欠拟合（underfitting）的例子，其中一些数据展示了模型没有捕捉到的结构。而最右边的这张图则是一个过拟合（overfitting）的例子。（在后续的这门课中，当我们讨论学习理论时，我们将规范这些概念，也会更加谨慎地定义一个假设（hypothesis）是好或者坏的意思）。

正如之前讨论的，和上面这个图所展示的，特征的选择对于确保一个学习（learning）算法的性能是很重要的。（当我们讨论模型选择时，我们也会看自动选择一个好的特征集的算法）在这一节中，让我们简明地讨论一下局部加权线性回归（LWR:Local Weighted Regression），它假设有足够的训练数据，使得特征选择显得不那么重要（对结果的影响不大）。这种对待将会比较简明，因为你将有机会在作业中发现一些局部加权线性回归算法的特性。

在原始的线性回归算法中，为了对一个询问的点x做预测(也就是评估$h(x)$)，我们将会：

拟合$\theta$使$\sum_{i}(y^{(i)}-\theta^{T}x^{(i)})^{2}$最小化。
输出$\theta^{T}x$。

相反，局部加权线性回归算法做了以下几步：

拟合$\theta$使$\sum_{i}w^{(i)}(y^{(i)}-\theta^{T}x^{(i)})^{2}$最小化。
输出$\theta^{T}x$。

这里，$w^{(i)}$是非负的权重值。直观上，如果$w^{(i)}$对一个特定的$i$很大，那么在选择$\theta$时，我们将会尽力让$(y^{(i)}-\theta^{T}x^{(i)})^{2}$很小。如果$w^{(i)}$很小，那么$(y^{(i)}-\theta^{T}x^{(i)})^{2}$误差项在拟合时很大程度上会被忽略。

(个人理解：w^{(i)}越大，相当于对整体的影响较大，后面对于预测结果和真实结果之间的误差容忍度就很小，所以预测结果必须尽可能和真实值相同，稍微偏差一点点就会使得整体的值很大。而当w^{(i)}较小时，对预测错误的容忍度就比较大，也就是说明这个特征不是很重要，对结果影响不大，所以预测误差大一些也没关系)

一个对权重非常标准的选择如下：

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

注意到，权重依赖于我们要预测的x。( x是预测点，$x^{i}$表示训练样本中的点)

而且，如果$|x^{(i)}-x|$很小，那么$w^{(i)}$将接近于1。如果$|x^{(i)}-x|$很大，那么$w^{(i)}$将会很小(趋近于0)。因此，在选择$\theta$时只需要考虑离询问的x近的训练样本点，给这些点较大的权值。（个人理解：权值大的样本点表示离x近，权值小表示离x很远，很远的话w为0这一项相当于可以忽略掉了，推到极限情况一种趋近于0，一种趋近于1，这和台大的林轩田老师讲过的0/1误差就很像了，所以这个w的式子很不错，有很丰富的含义）

(注意到，权重的公式和高斯分布的概率密度函数很像，但是$w^{(i)}$和高斯分布没有直接的关系，尤其，$w^{(i)}$也不是随机变量，正太分布或者别的）参数$\tau$控制着权值随距离(即$|x^{(i)}-x|$)的下降速率。$\tau$也被称为带宽参数（bandwidth），也是你将要在作业中实验的内容。

个人理解：

这里用高斯函数来作为权重函数，采用的是非参数估计中的核估计方法。 *为什么选取高斯分布？

便于数学处理
对绝大多数问题，如果使用了线性回归模型，然后测量误差分布，通常会发现误差是高斯分布的。
中心极限定律：若干独立的随机变量之和趋向于服从高斯分布。若误差有多个因素导致，这些因素造成的效应的总和接近服从高斯分布。、

局部加权线性回归是我们遇到的第一个非参数化的算法。我们之前看到的(不加权的)线性回归是一种参数化的学习算法，因为它有有限个用来拟合数据的固定参数(比如$\theta_{i}$)。一旦我们拟合了$\theta$并把它们存起来，我们就不再需要把训练数据留下来做未来的预测了。相反，用局部加权线性回归做预测，我们需要始终保留整个训练集。术语”非参数化”大概指的是我们需要保留下来代表假设（hypothesis）h的参数的数量会随着训练集的大小线型增长。（好不容易翻译过来，，开始没太懂啥意思，查了下资料，维基百科上说非参数化的学习方法它的参数是由训练资料决定的，而不是由模型本身决定的。参数化的学习方法仅仅依赖于少数的参数构成模型，在训练的时候比较好训练，然后可以直接采用模型来做预测。而非参数化的学习方法却不行，它会根据预测的数据来动态调整相应的参数，数据很大时模型复杂度也会比较高。）

（最后这句话和维基百科上说的两种方法的不同点大致一样：非参数化的学习方法的参数数量会随着训练集的变化而变化，而参数化的学习方法有固定数量的参数。非参数化的意思是对于模型本身而言，它没有固定的参数。）

4.1 机器学习非参数化方法

非参数估计的几种方法有：

非参数密度估计
直方图形式的估计
核估计
k-最近邻估计

详见非参数方法讲解的博客。

下面引自这篇关于参数化和非参数化方法的文章：

参数化机器学习方法：通过固定大小的参数集(与训练样本数独立)概况数据的学习模型成为参数模型。不管你给与一个参数模型多少数据，对于其需要的参数量都没有影响。

参数算法包括两部分：
选择目标函数的形式从训练数据中学习目标函数的系数

参数机器学习算法包括：

逻辑回归
线性成分分析
感知机

参数机器学习算法优点：

简洁：理论容易理解和解释
快速：参数模型学习和训练的速度都很快
数据更少：通常不需要大量的数据，在对数据的拟合不是很好时表现也不错

参数机器学习算法的局限性：

约束：以选定函数形式的方式来学习本身就限制了模型
有限的复杂度：通常只能应对简单的问题
拟合度小：实际中通常无法和潜在的目标函数吻合

非参数化机器学习方法：当你拥有许多数据而先验知识很少时，非参数学习通常很有用，此时你不需关注于参数的选取

非参数机器学习算法例子：

决策树，例如CART和C4.5
朴素贝叶斯
支持向量机
神经网络

非参数机器学习算法优势：

可变性：可以拟合许多不同的函数形式
模型强大：对于目标函数不做假设或者做微小假设
表现良好：对于预测表现可以非常好

非参数机器学习算法的局限性：

需要更多数据：对于拟合目标函数需要更多的训练数据
速度慢：因为需要训练更多的参数，训练过程通常比较慢
过拟合：有更高的风险发生过拟合，对于预测也比较难以解释

非参数化的学习算法，每次预测估值函数$J(\theta)$都不确定，无法提前确定参数，所以在每次做预测时就要扫描所有的数据点，然后重新计算$\theta$，计算量会很大。

后续还需要学习的知识

Widrow-Hoff学习规则在BP神经网络中的应用
分析并运行下面Reference中关于线性回归的博客中的python代码
学习机器学习中的其他非参数方法，比如KNN，RBF神经网络之类的算法。
参数回归，半参数回归，非参数回归之类的区别

写该博客中用到的Markdown技巧

第一个是如果想在每一段的段首空两格的话可以用中文全角空格来实现，这样Markdown在解析的时候它就不会像半角空格一样被忽略
第二个是在Markdown中插入公式，我用的MathJax这个js的插件。需要以下几个步骤：
在文档中插入一段js代码：

<script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=default"\> </script\>

行内公式用 $公式$ ，行间公式用$$公式$$。一些特殊符号如何输出可以参考以下几篇博客。

MathJax官网及github地址：

http://www.mathjax.org/
https://github.com/mathjax/MathJax

Markdown输入数学公式教程：

http://oiltang.com/2014/05/04/markdown-and-mathjax/
http://www.ituring.com.cn/article/32403

MathJax相应符号的Markdown写法（非常全）：

http://www.onemathematicalcat.org/MathJaxDocumentation/TeXSyntax.htm

第三个是在MathJax的公式内输出空格需要用\ 这种形式（反斜杠+空格），这样主要是为了让写的等式能够尽量对齐，显得比较美观。

Reference

极大似然估计

http://wenku.baidu.com/link?url=6u1FqP7d2dy2_GUoa-k4ARqAssTpz8upLm2RFzJ7tSKa1LlUJBr94D-uamACjYAFheij9cgJ6o_VDB2M5AZnnZcSNOtVio8deRXehO780Ci
http://www.cnblogs.com/kevinGaoblog/archive/2012/03/29/2424369.html

梯度下降法的比较

http://blog.csdn.net/lilyth_lilyth/article/details/8973972

Markdown插入数学公式

http://blog.csdn.net/xiahouzuoxin/article/details/26478179

局部加权线性回归

http://www.tuicool.com/articles/IFFRRv
http://blog.csdn.net/acdreamers/article/details/44662753
//除了局部加权线性回归外还讲解了其他方法
http://blog.csdn.net/acdreamers/article/details/44662753

线性回归资料(以后还可以看)

http://www.tuicool.com/articles/IFFRRv
//下面博客里的python代码可以试着运行一下
http://blog.csdn.net/moodytong/article/details/10041547
http://www.bubuko.com/infodetail-509872.html

欠拟合与过拟合概念

http://blog.csdn.net/maverick1990/article/details/11721453

参数和非参数机器学习算法

http://shujuren.org/article/106.html

非参数学习(以后还可以看)

http://wenku.baidu.com/link?url=K_Pb6XLKzzNN1LOkd-Btml6G2Cq8d73SJW1VHh82b_wdgsT7N3KnykIy6iUOMhXhiuaTBCOvJDY0ZiR2jGTQr_FioI8dMTwDhJQ2-EQmfw3
//介绍了几种不同类型的机器学习非参数方法
http://blog.csdn.net/app_12062011/article/details/50351144
http://www.zhaokv.com/wiki/ai/machine_learning/prml/probability_distribution/nonparametric