CS229 Lecture Note 1(监督学习、线性回归)
CS229 Lecture Note
Ora Yang
译者注：翻译斯坦福CS229对应讲义，如有错误，欢迎留言指正~（持续更新中）
专栏地址：传送门
监督学习
我们首先谈谈几个监督学习问题的例子。假设我们有一个数据集，提供了来自俄勒冈州波特兰市的47个房屋的居住面积和价格信息：
我们可以绘制这些数据：
有了这样的数据，我们如何才能预测波兰特市其他房屋的价格，作为他们居住面积的函数呢？
为了构建符号供将来使用，我们将使用来表示输入变量（本例中的居住面积），也称为输入特征，来表示我们正在常思预测的输出或目标变量（价格）。一对（，）被称为训练示例，以及我们用来学习的数据集—m个训练样例{，；i=1,2,3…m}的列表—被成为训练集。请注意，符号中的标注（i）只是训练集中的索引，与幂无关。我们也将使用X来表示输入值的空间，Y来表示输出值的空间。在本例中，X=Y=R。
我们稍微正式地来描述下监督学习问题，我们的目标是，给定一个训练集，学习一个函数h: X—>Y，使得h能够很好的预测Y的相应值。由于历史原因，函数h被称为假设。如图所示，整个过程就像这样：
当我们想要预测的目标变量是连续的，例如在房价示例中，我们把这个学习问题称为回归问题。当y可以只取少量的离散值(例如，如果给定居住区域，我们想要预测住宅是房子还是公寓)，我们称之为分类问题。
第一部分
线性回归
为了让我们的房屋例子更有趣，让我们考虑一个更丰富的数据集，在该数据集中我们也知道每个房子的卧室数量。
这里，x是中的二维向量。例如，是训练集中第i个房屋的居住面积，是卧室的数量。（一般来说，在设计一个学习问题时，是由你决定来选择什么样的特征，所以如果你在波特兰市收集住房数据,您也可能决定是否包括其他特征,如是否每个房子都有一个壁炉,浴室的数量,等等。稍后我们将详细介绍特征选择，但现在让我们选择给定的特征）
为了实施监督学习，我们必须决定如何在计算机中表示函数/假设h。作为一个初步的选择，我们决定把y近似成x的线性函数：
在这里，是参数（也称权重）参数化从X->Y的线性函数空间，在没有混淆风险的情况下，我们将中的下标去掉，简写成h(x)。为了简化符号，我们还引入了使=1的约定（这是截距项），结果是：
上面等式右边，我们视，x为矢量，n为输入变量的个数（不计入其中）。
现在给定一个训练集，我们该如何去选择或者学习参数呢？一个合理的方法似乎是使h(x)接近y，至少在训练集中。为使之正规化，我们将定义一个函数，对每一个，它来度量h()离对应的多近。我们定义了代价函数：
如果你之前看过线性回归，你可能会发现这是一个熟悉的最小二乘代价函数构成的普通的最小二乘回归模型。不管你之前是否见过，让我们继续，最后我们会展示这是一个更广泛的算法的特例。
1 LMS 算法
我们想选择使得J()最小化的参数。要这样做，我们使用以一些的猜想值开始的搜索算法，反复改变值使J()最小，直到收敛到一个使得J()最小化的值。具体来说，让我们考虑梯度下降算法，它从一些初始开始，并反复更新：
（更新同时作用于所有的j=0,1,2,3,4…n）
此处被称为学习率。这是一个非常自然的算法，它会重复朝J下降最快的方向移动。
为了实现这个算法,我们得算出右边的偏导项是什么。假如只有一个训练样本的情况下（这样就能忽略J定义中求和部分了），让我们先求出它的偏导向。我们有：
对于单个训练样本，该公式提供了一种更新规则：
该规则被称为LMS更新规则(LMS代表"least mean squares")，也被称为Widrow-Hoff学习规则，这个规则有一些看起来很自然和直观的属性。例如，更新的大小与误差项成正比
因此，例如，如果我们遇到了预测值与实际值几乎匹配的训练样本,然后我们发现几乎没有需要去修改参数；相反，如果我们的预测值有一个很大的错误，就需要对参数做一个很大的改变。（例如，它与相差较远）。
我们已经在只有一个训练样本的情况下推导出了LMS规则。有两种途径去修改上述方法来适用于超过一个训练样本的情况。第一方法是直接替换成下面的算法：
读者可以很容易地验证上述求和式子的结果就是∂J(θ)/∂θj（J的原始定义）。因此这就是原始代价函数的简单梯度下降。该方法观察每一个步骤的整个训练集的每个例子，也被称为批量梯度下降。注意，虽然梯度下降一般很容易受到局部极小值的影响，但是我们这里提出的线性回归的优化问题只有一个全局的没有局部优化。因此梯度下降总是收敛（假设学习率α不是很大）到一个全局最小值。事实上J是一个凸二次函数。这儿有一个梯度下降的例子，因此它是用来最小化二次函数的。
上面所示的椭圆是二次函数的轮廓。也显示了梯度下降的轨迹，它在(48,30)处初始化。图中的x由直线相连标记着梯度下降经过的连续值。当我们运行批量梯度下降来拟合之前数据集上的θ时，为了学习预测房价作为住宅面积的函数。我们得到θ0 = 71.27, θ1 = 0.1345。如果我们通过寻来你数据将绘制成x(住宅面积)的函数，我们就得到了下面的图形：
如果卧室数量被作为输入特征之一，我们得到θ0 = 89.60, θ1 = 0.1392,θ2 =-8.738。
上面的结果是通过批量梯度下降获得的。除了批量梯度下降还有一种方法表现不错。考虑下面的算法：
在该算法中我们重复遍历训练集，每遇到一个训练样本，我们根据这个单一训练样本的梯度误差对参数进行更新。该方法被成为随机梯度下降（也被称为递增梯度下降），而批量梯度下降在实行单步运行时要扫描整个训练集—如果m很大运行代价就很高了—随机梯度下降可以立即取得进展并且通过观察的每个样本来持续获得改变。通常随机梯度下降比批量梯度下降快得多。（但是请注意它可能永远不会收敛到最小值并且参数θ将在J(θ)的最小值附近振荡，但是在实际情况中，大多数接近最小值的值可以近似为最小值）。由于这些原因，特别是当训练集很大的时候，随机梯度下降经常比批量梯度下降更受欢迎。
2 正规方程
梯度下降给了一种最小化J的方法。让我们第二种方法，这次显式地执行最小化而不采用迭代算法。在该方法中，我们将显式地执行J关于θj的导数来最小化J，并把他们设置为0。为了使我们能够做到这一点不用写大量的代数和大量的导数矩阵，让我们介绍一些用矩阵来做微积分的符号。
2.1导数矩阵
对于一个函数从m乘n矩阵到实数的映射，我们定义f对A的导数如下：
因此梯度∇Af(A)本身就是个m乘n的矩阵，其（i , j）的元素是∂f/∂Aij。例如，假如
是一个2 x 2的矩阵，并且函数,由下式给出：
在这里Aij表示矩阵A的（i，j）的实体，我们有
我们也引入trace操作符，写作"tr"。对于一个n x n的方阵A，A的trace被定义为其对角线元素的和：
如果a是一个实数（例如，a是1 x 1的矩阵），那么tr a = a。（如果你以前没看见过这样的操作符，你应该把A的trace操作看作tr(A)或者是矩阵A的trace函数的应用。但是它通常不写括号）
trace操作符有一个性质：对于两个矩阵A，B，即AB是方阵，我们有tr AB = tr BA。作为这里性质的推论，我们有，
trace操作符的以下属性也很容易被验证。在这里，A和B是方阵，a是实数。
我们现在不证明的声明举证导数的一些事实。等式（4）仅适用于非奇异方阵A，其中|A|
表示A的行列式。我们有:
为了使我们的矩阵符号更加具体，现在让我们详细地解释第一个方程的意义。假设我们有一个固定的矩阵。然后我们可以根据f(A)
= trAB，定义函数
。
注意这个定义是有意义的，因为如果，那么AB是方阵，我们可以将trace操作符应用上去。因此函数f的确从
映射到
，然后我们可以运用矩阵导数的定义来求∇Af(A)
，它本身就是个M x N的矩阵。上面的等式（1）表示这个矩阵的（i，j）元素有BT的（i，j）元素给出，或者等价于Bji。
等式（1-3）的证明是相当简单的，证明被留作读者的一次练习。等式（4）可以通过矩阵逆的伴随矩阵推导得到。
2.2重新审视最小二乘法
拥有矩阵导数的工具，让我们继续在封闭的形式下寻找最小化J(θ)的参数θ的值。我们通过矩阵矢量表示法重新写J。给定一个训练集，定义设计矩阵X为m x n矩阵（事实上是m x n +1,如果我们包含了截距项）包含训练样本的输入值按行表示：
同样让作为包含训练集所有目标值的m维的向量：
现在，因为，我们可以轻松证明
因此利用这个事实，对于矢量z,我们有
最终为了最小化J，让我们实现它关于θ的导数。结合等式（2）和（3）我们得到
因此，
在第三步中，我们用到了一个事实就是实数的trace就是实数；第四步用到了的事实，第五步使用了公式（5）其中
，C=I和公式（1）。为了最小化J,我们把它的导数设置为0，得到了正规方程：
最小化J（θ）的θ的值由公式闭环给出:
3概率表示
当面对回归问题时，为什么线性回归，特别是为什么最小二乘的代价函数J是合理的选择。在这一节中，我们将给出一组概率假设，其中最小二乘回归是一种非常自然地算法。我们假设目标变量和输入都是通过方程联系起来的
其中是误差项，为了捕捉未建模的影响（例如存在一些与预测房价有关的特征，但是我们并没有添加到回归中）或者是随机噪声。根据均值为0，方差为的高斯分布（也叫正态分布），，我们进一步假设是独立同分布(independently
and identically distributed)。我们可以把这个假设写成也就是说，的密度为
这也意味着：
符号表示这是给定,参数为的的分布。注意我们不应该以
为条件，因为并不是一个随机变量。我们也可以将的分布写成
。
给定X(包含所有的设计矩阵)和，的分布是什么？数据的概率由给定。对于一个固定的值，这个量可以被看作
（或许是X）的函数，当我们想明确地把这看作的函数，我们将称它为似然函数：
注意假设独立（因此给定的也独立）公式也可以被写成：
现在，给定关于和的概率模型，那么选择参数的最佳假设的合理方式是什么？最大似然准则表明我们应该尽可能选择使数据有更高概率的值。也就是我们应该选择能最大化L()的值。
我们也可以最大化L()的任何严格递增的函数，而不用最大化L()。特别地，如果我们最大化log似然函数ℓ(θ),导数的求解会更简单。
因此最大化ℓ(θ)等价于最小化：
我们知道它是J(θ)，即原始的最小二乘代价函数。
总结：根据数据的先验概率假设，最小二乘回归对应于寻找的最大似然估计。这是一组假设，基于最小二乘回归可以被认为仅仅实现最大似然估计的一种非常自然的方法。(注意，概率假设对于最小二乘成为一个非常好的、理性的过程并不是必要的，而且确实存在其他的自然假设也可以用来证明它的合理性。
还要注意的是，在我们之前的讨论中，我们最终的选择并不取决于，事实上，即使是未知的，我们也会得到相同的结果。当我们讨论指数族和广义线性模型时，我们稍后将会用到这个事实。
4局部加权线性回归
考虑到从预测y的问题。下图最左边显示了将
匹配到数据集的结果，我们看到数据并没有真正落在直线上，所以拟合并不是很好。
相反，如果我们提供一个额外的特征并且拟合，我们获得了对数据有着更好拟合的结果。（见中间图）我们天真地认为，添加地特征越多，拟合的效果越好。但是增加太多特征也有风险：最右边的图形是拟合一个5阶多项式的结果：
我们看到即使拟合的曲线完美地通过了数据，我们不认为这是对不同住宅面积(x)的房价(y)的一个很好的预测指标。如果没有正式定义这些术语的含义，我们会说左边的图片显示了一个欠拟合的实例——其中的数据清楚地显示了模型没有捕捉到的结构而右边的图片是一个过拟合的例子。（在这门课的后面，当我们讨论学习理论的时候我们会把这些概念形式化，也会更仔细地定义一个假设是好的还是坏的。）
正如前面所讨论的，上面的例子表明，特征的选择对于确保学习算法的良好性能非常重要。
当我们谈到模型选择时，我们还会看到自动选择一组优秀特性的算法。在这一节中，让我们简要地讨论一下局部加权线性回归(LWR)算法，假设有足够的训练数据，使得选择特性不那么重要。这个处理很简单，因为你将有机会在作业中探索LWR算法的一些特性。
在原始的线性回归算法中，为了在一个查询点x作出预测（例如，评估h(x)），我们会：
-
拟合来最小化
。
-
输出。
与此相反，局部加权线性回归算法如下：
-
拟合来最小化
。
-
输出。
此处是非负的权重值，直观的来说，如果对于某个特定的i值很大，那么在选时，我们会努力使小。如果小，那么
这个错误项在拟合时会被忽略掉。对权重的一个相对标准的选择是
，请注意权重依赖于我们努力去评估的点x。而且，如果|x(i)-x|比较小，就接近于1；并且如果|x(i)-x|比较大，就会比较小。因此，在训练样本靠近查询点x时给一个更高的权重的情况下被选取。还要注意的是，权重公式的形式与高斯分布的密度相似，与高斯没有直接关系，特别是不是一个随机变量，正态分布或者其他。）参数控制训练样本到查询点x之间距离上下降得多块。被称为带宽参数。这也是你们要在作业中要做的实验。
局部加权线性回归是我们看到的非参数算法的第一个例子。我们之前看到的（未加权）的线性回归算法被称为参数学习算法。因为它有固定的有限个数的参数来拟合数据。一旦我们拟合了并存储下来，我们就不再需要保留训练数据来做预测。相反，利用局部加权线性回归来做预测，我们需要保留整个训练集。术语"非参数"（粗略的）指的是为了表示假设h，我们需要保持的东西的数量会随着训练集的大小线性增长。