斯坦福大学《机器学习与数据挖掘公开课》：梯度下降算法与正则方程研究

算法中用到了大量线性代数的知识。所以我觉得有必要先回顾和梳理一下线性代数的基础知识。

1 基本概念和符号

线性代数可以为线性方程提供一种简单的表达和运算方法，例如以下方程：

4x1-5x2=13-2-2 9

可以简单地表示为：

X 也是一个矩阵，即 (x1, x2)T。当然你可以把它想象成一个列向量。

1.1 基本表示法

用A ε 表示一个m行n列的矩阵A，矩阵的每个元素都是实数。

要表示 N 维向量，请使用 x ∈ 。这通常是一个列向量。如果要表示行向量，通常通过转置列向量（后面跟T）来表示。

1.2 向量的内乘和外乘

根据类中的定义，如果形式为 xT y 或 yT x，则表示为内积，结果为实数，这意味着： 如果如果形式为 xyT，则表示该外积：。

1.3 矩阵向量乘法

考虑矩阵 A ∈ Rm×n 和向量 x ∈ Rn，它们的乘积是向量 y = Ax ∈ Rm。这意味着以下表达式：

如果 A 是由行表示的矩阵（即表示为 ），则 y 表示为：

相对地，如果 A 是由列表示的矩阵，则y 的表达式为：

这意味着：y 被认为是 A 的列的线性组合。每列乘以一个系数并相加。系数由 x 获得。

类似地，

yT=xT*A 表示如下：

yT 是 A 行的线性组合。每行乘以一个系数并相加。系数由x获得。

1.4 矩阵 - 矩阵相乘

也有两种表示方式：

第一种方式：A 表示为行，B 表示为列

第二种方式，A 表示为列，而B表示为一条线：

本质上是一样的，只是表达方式不同。

1.5 矩阵梯度运算（由教师改编）

定义一个函数 f，它是 m x n 矩阵到实数的映射。那么f在A上的梯度定义如下：

我这里理解为A的元素的表达式f(A)=是一个实数，那么所谓的A的梯度就是一个矩阵如A。矩阵的每个元素都是关系中f(A)的原始元素。

1.6 其他术语

由于篇幅限制，这里不再赘述。其他所需术语包括单位矩阵、对角矩阵、矩阵转置、对称矩阵 (AT=A)、反对称矩阵 (A =-AT)、矩阵迹、向量模、线性独立性、矩阵秩、满秩矩阵、矩阵的逆（当且仅当矩阵满秩时可逆）、正交矩阵、矩阵列空间（取值范围）、行列式、特征向量和特征值...

2 使用的公式

课程中用到了很多公式，我们将一一列举。好吧，有些公式的证明很简单，有些困难的我不知道如何证明，也懒得去详细思考。毕竟，感觉数学对我来说更像是一种工具。

与换位相关：

• (AT)T = A
• (AB)T = BT AT
• (A + B)T = AT + BT♹♹❀ • A
对于 Rn×n trA = trAT .
• 对于 A，B ∈ Rn×n tr(A + B) = trA + trB。
• 对于 A ∈ Rn×n t ∈ R ， tr(tA) = t trA.
• 对于A、B，使得AB 是正方形，trAB = trBA。
• 对于A、B、C，使得ABC 是正方形，traABC = trBCA = trCAB。当乘法次数较多时也是如此，即每次从尾部取出一个矩阵放在前面，这样一个矩阵相乘得到的矩阵的迹是一致的。

排名相关

• 对于A ∈ Rm×n，rank(A) ≤ min(m, n)。如果rank(A) = min(m, n)，则A称为满秩 ，B ∈ Rn×p，rank(AB) ≤ min(rank(A)，rank(B ))。
• 对于A B ∈ Rm×n, 等级(A + B) ≤ 等级(A) + 等级(B)。

逆相关：

• (A−1)−1 = A
• 如果 Ax = b ，左乘和右乘以 A−1 得到 x = A−1b。
• (AB)−1 = B−1A−1
• (A−1)T = (AT)−1。 F 通常表示为 A−T。

与行列式相关：

• A ∈ Rn×n for |A| = |AT |.
• 对于 A，B ∈ Rn×n，|AB| = |A||B|.
• 对于 A ∈ Rn×n |A| = 0，说明矩阵 A 是奇异矩阵，不可逆矩阵
• 对于 A ∈ Rn× n 且 A 可逆，|A|−1 = 1/|A|。

梯度相关： ♺ • ∇x(f(x) + g(x)) = ∇xf(x) + ∇xg(x)。 • 对于 T ∈ R ∇x(t f(x)) = t∇xf(x).

• ∇xbT x = b
• ∇xxT Ax = 2Ax（如果 A 对称） ∇2xxT Ax = 2A（如果 A 对称）

• ∇A|A| =(adj(A))T = |A|A−T 。 adj=adjoint

3 梯度下降算法和正规方程组示例应用

示例使用上一课的房价示例。有一系列的信息，包括房子的面积和房子的价格。输入格式示例：

老师定义的变量为：

m：训练样本数量

x：输入变量（输入函数，本例中为房屋面积和卧室数量

y：输出变量（目标变量，本例中为房价）

(x,y)：代表样本

：代表第 i 个样本，表示为 。

3.1 监督学习概念

所谓监督学习就是告诉算法每个样本的正确答案。学习算法还可以对新输入输入正确的响应。监督是指训练时对样本答案的监督，h是监督学习的函数。

在此示例中，我们假设目标输出变量是输入变量的线性组合。这意味着我们的假设是存储以下 h(x)：

Theta 表示对象前面的参数（也称为函数权重）。这意味着h(x)之后得到的就是预测结果。

如果我们假设x0=1，那么原始h(x)可以简单地表达为以下形式：

，其中n是特征的数量。为了表达简单，我们将 theta 和 x 都写为向量。下面介绍如何求θ（一个向量），使得h(x)尽可能接近真实结果，至少在训练集中，接近训练集中的正确答案。

我们定义一个成本函数（cost function），并计算每组θ的h(x)与真实值之间的差值。定义如下：

这也是最小二乘法的思想，不过之所以要乘以1/2，是为了简化后续的计算。对于每个训练集的数据集。剩下的问题是在获得 minJ(θ) 时求出 θ 的值。由于J(θ)随着θ的变化而变化，所以我们要求得到minJ(θ)时的θ就是我们想要的θ（这个min也称为最小成本函数），那么我们如何求这个量的theta呢？使用梯度下降算法和普通方程组。我们首先看一下梯度下降算法。

3.2 梯度下降算法

梯度下降算法是一种搜索算法。基本思想可以理解为：我们从山上的某个点开始，找到最陡的坡度并迈出一步（即找到坡度的方向），到达一个点后，找到最陡的坡度并迈出另一步。直到我们继续这样走并到达“最低”点（最小成本函数的收敛点）。

如上图所示，x和y代表theta0和theta1，z方向代表成本函数。显然，起点不同，最终达到的收敛点也可能不同。当然，如果是碗状，则接近点应该是相同的。

算法theta更新表达为：

对于每个theta(j)，首先求J(θ)（梯度方向）对theta(j)的偏导数，然后减小α，然后改变当前的theta(引入j)来获取新的theta(j)并更新它。其中，α是步长，你可以理解为下山时迈出的步子的大小。如果步长太小，接近速度会很慢。如果螺距过大，则可能会在接近点附近来回摆动，而达不到最低点。P.S.这个符号，按照老师的说法，在程序中理解为任务符号（=符号）。如果是 = 符号，则这些值被理解为相等（编程中的 == 符号）。

我们先弄清楚吧。假设现在训练集只有一个数据集求theta(j)的偏导数：

得到可以得到该数据集的表达式theta(j)，也可以，这个数据集是第i个簇，是则表示为：

我们将 theta(j) 更新方法扩展到 m 个训练样本，得到以下公式：

P.S. Xj(i)的最终理解是：第i个数据集中第j个特征的值。

3.2.1 批量梯度下降算法（批量gxxxx dxxxx算法）

重复上述更新步骤直至收敛，得到这组θ值。这是过程：

。

该算法是批量梯度下降算法。为什么这批被称为梯度下降？由于注意到上式中θj的每次更新都需要计算所有样本值，所以如果样本数量非常大（例如几万甚至几十万），这样的更新是非常慢的，而且求θ也很慢，所以还有一种改进的梯度下降算法。

3.2.2 随机梯度下降算法/渐进梯度下降算法

进行一个小的改进并使用样本更新theta。这种方法的优点是肯定比批量梯度下降算法要快，而且样本数据越多，性能应该越明显。缺点是与批量梯度算法相比，得到的收敛点值可能不是最优的。 ？是样本数，n是特征值/影响因素的数量）

2。都具有梯度下降的性质：随着你接近每一个“步”（指的是实际减去的数字，而不是之前定义的α，α是手动设置参数并且参数只有在手动改变时才会改变）变得越来越小。原因是每次将α减去并乘以梯度，但随着逼近的进行，梯度越来越小，减去的值也越来越小。？ 3.3 正规方程组

前面写过：这个方法是另一种方法，与梯度下降算法无关！ ！ ！ ！ ！ ！

首先回顾一下之前定义的矩阵梯度运算：

例如：

然后：

定义一个称为设计矩阵的矩阵，它表示之前所有样本❀的输入 结论： (θT* x( i) 和 x(i) 转置 *θ 结果相同），我们得到 ，它可以写成以下形式：

因为对于任何向量 ，我们得到：

应用以下一系列性质：

(5)由(2)和(3)得到，并进行以下推导

中间添加tr保持不变的原因是它是一个实数（查看作为 1x1 矩阵）并且迹等于其自身。

将上式置0，得到正规方程组

求解