Normal equation

在利用梯度下降(Gradient Descent)算法解决线性回归的课上，Andrew Ng还讲了正则方程式(Normal equation)这个东西，可以不依靠迭代算法求解线性回归问题，而是直接求出解析解。以下是一些相关的内容。

首先还是定义一下符号：

设 $𝑓:{ℝ}^{𝑚\times 𝑛}\to ℝ$ , $𝐴\in {ℝ}^{𝑚\times 𝑛}$, 则定义$𝑓$的梯度如下:

设$𝐴\in {ℝ}^{𝑛\times 𝑛}$, 则定义矩阵A主对角线上的元素之和为矩阵A的迹，记为:

显然: 对于 $𝑎\in ℝ,\text{tr}𝑎=𝑎$

$\text{tr}𝐴=\text{tr}{𝐴}^{𝑇}$

且对于合适的矩阵A,B,C，有以下结论:

$\text{tr}𝐴𝐵=\text{tr}𝐵𝐴$

证明:

设$𝐴\in {ℝ}^{𝑚\times 𝑛},𝐵\in {ℝ}^{𝑛\times 𝑚}$, 则

所以有$\text{tr}𝐴𝐵=\text{tr}𝐵𝐴$

$\text{tr}𝐴𝐵𝐶=\text{tr}𝐶𝐴𝐵=\text{tr}𝐵𝐶𝐴$

证明: 由上面的结论，有:

设$𝑓\left(𝐴\right)=\text{tr}𝐴𝐵$，那么${\nabla }_{𝐴}𝑓\left(𝐴\right)={\nabla }_{𝐴}\text{tr}𝐴𝐵={𝐵}^{𝑇}$

证明:

设$𝐴\in {ℝ}^{𝑚\times 𝑛},𝐵\in {ℝ}^{𝑛\times 𝑚}$, 则

所以$\frac{𝜕𝑓\left(𝐴\right)}{𝜕{𝑎}_{𝑖𝑗}}={𝑏}_{𝑗𝑖}$

所以${\nabla }_{𝐴}𝑓\left(𝐴\right)={\nabla }_{𝐴}\text{tr}𝐴𝐵={𝐵}^{𝑇}$

证明: 并不会, 倒是有在网上找到一个证明，不过并不理解。姑且先记在这里。

故:

回到线性回归，对于输入$𝑋{|}_{𝑛\times 𝑚}$和输出$𝑌{|}_{1\times 𝑚}$，我们的目标是找出一组$𝜃{|}_{𝑛\times 1}$,使得$𝐽\left(𝜃\right)=\frac{1}{2}\parallel {𝜃}^{𝑇}𝑋-𝑌\stackrel{2}{\parallel }$最小，由于:

故我们的目标是，对于给定的X和Y，求出一组$𝜃$，使得${\nabla }_{𝜃}\frac{1}{2}\left({𝜃}^{𝑇}𝑋-𝑌\right){\left({𝜃}^{𝑇}𝑋-𝑌\right)}^{𝑇}=\vec{0}$

故:

故:

这一结果根据X，Y，$𝜃$的定义不同而稍有不同，本质是一样的。当$𝑋{𝑋}^{𝑇}$不可逆时，可以使用伪逆求$𝜃$。