正规方程组 投影法

机器学习 CS229

---

概述

       正规方程组（Normal Equation）在机器学习中是一种比较常见的求权重向量 $\theta$ 较为常见的方法，相对于梯度下降不需要迭代过程，也不需要进行特征缩放。

关于矩阵的小知识

       正规方程组与梯度下降不同，需要较多的数学知识作为支撑，关于矩阵方面的知识很多都忘记了，也算是顺便复习下。

       首先，我们定义一个函数 $f:R^{m*n} \rightarrow R$ 表示从 $m*n$ 矩阵到实数的映射，我们再定义一个 $\nabla f(A)$ 如下：

$$\nabla f(A) =\begin{bmatrix} \frac{\partial f}{\partial A_{11}} & \cdots\ & \frac{\partial f}{\partial A_{1n}} \\ \vdots & \ddots & \vdots \\ \frac{\partial f}{\partial A_{n1}} & \cdots\ & \frac{\partial f}{\partial A_{nn}} \\ \end{bmatrix}$$
       再引入矩阵的迹这个概念，还是以矩阵 $A$ 为例：
$$trA = \sum_{i=1}^nA_{ii}$$
       这个概念很容易理解，我们再来介绍一些简单的性质（公式4中的a为实数）：
$$trAB = trBA \\ trA = trA^T \\ tr(A+B) = trA+trB \\ traA = atrA$$
       关于上面这些公式的证明在此就不在赘述了，维基上都有相关的解释，结合前面的所有内容，我们再引入一些公式（我们假设A为非奇异矩阵）：
$$\nabla trAB = B^T \\ \nabla_{A^T} f(A) = (\nabla f(A))^T \\ \nabla_A trABA^TC = CAB + C^TAB^T \\ \nabla_A |A| = |A|(A^{-1})^T \\ $$

       公式1和公式2不要太好证明，这里我们就简单说明下公式3和公式4。

$$\nabla_A trABA^TC = \nabla_Atrf(A)g(A^T) = \nabla_{A:f(A)} trf(A)g(A^T) + (\nabla_{A^T:g(A^T)}f(A)g(A^T))^T\\ =(g(A^T))^T\nabla_Atrf(A) + ((f(A))^T\nabla_{A^T:g(A^T)}g(A^T))^T = C^TAB^T + CAB$$

       上面主要运用了乘法求导法则（虽然我感觉好像有点问题，在第二个等式我不是很理解，如果您理解，希望您能跟我联系）和迹的性质。对于公式4，我们需要借助一点伴随矩阵的知识，我们将伴随矩阵记为 $A^*$ ，则对于任意非奇异矩阵我们有， $A^{-1}|A| = A^*$ 。对于行列式，我们有这样的性质$|A^T| = |A|$，所以很显然公式4右侧就是 $(A^T)^*$ ，将公式4左侧展开我们很容易能够发现，公式左侧也是 $(A^T)^*$ ，所以公式4也是正确的。
       到此为止，我们的知识储备已经足够了，接下来就是核心部分了。

最小二乘法

       对于一组训练数据，我们很明显可以将输入矩阵和输出向量用下列形式表示：

$$X =\begin{bmatrix} (x^{(1)})^T \\ (x^{(2)})^T \\ \vdots \\ (x^{(m)})^T \\ \end{bmatrix}$$
$$y =\begin{bmatrix} y^{(1)} \\ y^{(2)} \\ \vdots \\ y^{(m)} \\ \end{bmatrix}$$
       在这里我们认为我们的直线方程为 $h_\theta(x^{(i)}) = (x^{(i)})^T\theta$ ，那么：
$$X\theta-y =\begin{bmatrix} h_\theta(x^{(1)}) - y^{(1)} \\ h_\theta(x^{(2)}) - y^{(2)} \\ \vdots \\ h_\theta(x^{(m)}) - y^{(m)} \\ \end{bmatrix}$$
       我们希望推导出 $J(\theta)$最小是 $\theta$ 的值（关于 $J(\theta)$ 的意义，将会在接下来的系列文章中简单介绍下）。
$$J(\theta) = \frac{1}{2} \sum_{i = 1}^{m}(h_\theta(x^{(i)}) - y^{(i)})^2 = \frac{1}{2} (X\theta-y)^T(X\theta-y)$$
       我们希望求得 $\nabla J(\theta) = 0$ 时，对应的 $\theta$ 的值，那么：
$$\nabla_\theta J(\theta) = \nabla_\theta \frac{1}{2}(X\theta-y)^T(X\theta-y) \\ = \frac{1}{2}\nabla_\theta (X^T\theta^TX\theta - y^TX\theta - X^T\theta^Ty + y^Ty) \\ = \frac{1}{2}\nabla_\theta tr(X^T\theta^TX\theta - y^TX\theta - X^T\theta^Ty + y^Ty) \\ = \frac{1}{2}\nabla_\theta (trX^T\theta^TX\theta - 2try^TX\theta + try^Ty) \\ = X^TX\theta - X^Ty = \ 0$$
       简单解释下上面的过程，等式(3)是因为一个实数的迹就是它本身，等式(4)则是利用了上面推导的公式，其中 $A^T = \theta, B = B^T = X^TX, C = I$ 。
       到现在为止，我们就得到了权重 $\theta$ 的正规方程组的表达形式(需要注意的这里不能进行化简，一般来说， $A$ 并不会是一个方阵，如果是方阵那可能就要出问题了)：
$$\theta = (X^TX)^{-1}X^Ty$$

投影解释

       知乎上有一个关于正规方程组很好理解，也很容易证明的解释，我认为还是有必要在此简单介绍一下。
       假设 $c$ 、 $b$ 和 $a$ 均为列向量，我们希望用 $b$ 和 $a$ 表示 $c$ ，那么当三者不共面时，一定无解，无法求出相应的 $\theta$ 使 $c = \theta^T( A )$ 成立。

$$A =\begin{bmatrix} a^T \\ b^T \end{bmatrix}$$
       这里我们引入误差向量 $e$ ，可以使 $c = \theta^T A + e$ ，显然当向量 $e\perp A$ 时，误差向量达到最小。
       又因为 $e\perp a$ 时，所以我们有以下两个方程：
$$\left\{ \begin{aligned} a_1^T(c - A\theta) = 0 \\ a_2^T(c - A\theta) = 0 \\ \end{aligned} \right.$$
       整理可以得到 $A^T(b-A\theta) = 0$ ，很显然，我们可以求出 $\theta$ 的值：
$$\theta = (A^TA)^{-1}A^Tc$$
       这与我们前面推导的方程完全一致， $A$ 表示的就是训练集的特征矩阵，而 $c$ 则是相应标记矩阵，我们可以很容易的将上述过程扩展到无线维。
       到此为止，这种解释已经完全结束了，相对于最小二乘法，本方法更容易理解，对数学的要求也比较低，我认为是十分值得阅读的。

需要注意的事

       最后再墨迹墨迹，到此为止我们只是知道了正规方程组的证明推导过程，我们为什么要使用它，它和梯度下降相比有什么优势或者劣势，这些都没去讨论，以下就是对这些内容的一些理解（实际上应该说是整合）。（待研究 只有在解释变量之间没有完美的多重共线性）
       首先，最小二乘法求得的是全局最小值（对于非线性不存在密闭解，需要进行迭代），不需要迭代，避免了梯度下降求得的是局部最优点的问题，同时接近最小点时迭代速度变慢（如果 $\alpha$ 是自适应的，那就更慢了），对于初始点的选择依赖比较严重。最小二乘法同样需要注意的是 $X^TX$ 需要是非奇异矩阵，一般来说只要 $m >> n$ ，同时特征之间的依赖性不是很强的条件下就不会出现矩阵为非奇异矩阵的情况。
       但是，这并不是说梯度下降计算速度慢于最小二乘法，计算一个矩阵的逆是极其耗时的（复杂度大概是 $n^{2.37}$ ），所以如果特征数目$n$的数量比较大的时候（在Andrew Ng的Coursera中给出的临界值为 $10,000$ ），最后还是选择梯度下降比较好。同样，梯度下降也并不是不能够达到全局最优点。批量梯度下降法每次会考虑所有的训练样本，所以得到的就是全局最优点，但是这种方式很慢。（待研究 Gram矩阵优化）
       在投影方法中，我们可以很不负责的认为二次投影不会对整个求解过程造成任何影响，至少从投影的角度上，我们可以这样认为（这里需要注意二次投影，第二次投影的 $c$ 被替换为了 $(A(A^TA)^{-1}A^Tc)$ ）：

$$h(\theta)^2 = A(A^TA)^{-1}A^T(A(A^TA)^{-1}A^Tc) \\ = A((A^TA)^{-1}(A^TA))(A^TA)^{-1}A^Tc \\ = A(A^TA)^{-1}A^Tc \\ = h(\theta)$$

结语

       本来以为这篇文章很快就能够结束了，结果在自己证明时，还是遇到了各种各样的问题，感觉自己的数学基础实在有点差，准备找时间弥补一下。

参考

With(out) A Trace Matrix Derivatives the Easy Way
线性规划、梯度下降、正规方程组——斯坦福ML公开课笔记1-2
掰开揉碎推导Normal Equation