Normal Equations

文章来源：

本文主要是将上一篇中的得出的梯度下降法的算法用矩阵进行化简，得到一个一般化的公式，最后对这两种方法进行了比较。

几个结论

在开始正式推导之前，我将会列出一些推导过程中需要用到的定义和结论，其中有些我会给出证明。

首先是关于矩阵迹的定义:一个n×n的矩阵A的迹，是指A的主对角线上各个元素的总和。迹是定义在矩阵上的一种运算，它是一个实数。

关于矩阵的迹，它有以下几个结论：

1. trAB=trBA 推论:trABC=trCAB=trBCA
2. 令f(A)=trAB1

   1f(A)表示一个函数，这个函数将m×n的矩阵A作为输入，将一个实数trAb作为输出。其实就是从高维到低维的一个映射:Rm×n?R

   ,则?AtrAB=BT
3. trA=trAT
4. 如果a∈R,则tra=a
5. ?AtrABATC=CAB+CTABT

几个结论的简略证明如下：

trAB=trBA

根据矩阵乘法的运算法则，如果C=Am×nBn×m，则Cij=(AB)ij=∑nk=1AikBkj。

所以，tr(AB)=∑mi=1(AB)ii=∑mi=1∑nk=1AikBki=∑nk=1∑mi=1BkiAik=∑nk=1(BA)jj=trBA

现在证明?AtrAB=BT

trAB=∑ni=1∑mk=1AikBki=∑mk=1A1kBk1+∑mk=1A2kBk2?∑mk=1AnkBkn

所以，?trAB?Aij=Bji

即，?AtrAB=BT

结论3、4、5此处就不再给出证明了。2

23、4几乎不用证明，直接利用迹的定义就能够得出。而5的证明，老实说，我也不会，如果有哪位大神会的，请不吝赐教(-.-)。

矩阵推导

有了上述的准备工作，就可以开始我们的推导工作了。我们将训练数据表示成矩阵的形式:

X=???????(x(1))T??(x(2))T???(x(n))T???????(1)

参数θ和输出结果y表示成向量形式:θ=??????θ1θ2?θn??????,y=??????y(1)y(2)?y(m)??????

所以Xθ?y就可以表示成：

Xθ?y=????????(x(1))Tθ?y(1) (x(2))Tθ?y(2) ? (x(m))Tθ?y(m) ????????=????????hθ(x(1))?y(1) hθ(x(2))?y(2) ? hθ(x(m))?y(m) ????????(2)

根据向量的基本性质:zTz=∑ni=1z2i，所以：

12(Xθ?y)T(Xθ?y)=12∑i=1m[hθ(x(i))?y(i)]2=J(θ)(3)

因此，为了使J(θ)达到最小，只需要求出令?θJ(θ)=0时的θ值,这时的θ值就是梯度下降法中最终得到的参数值。

?θ12(Xθ?y)T(Xθ?y)=12?θtr(θTXTXθ?θTXTy→?y→Xθ+y→Ty→)=12?θ(trθTXTXθ?2try→TXθ)=12(XTXθ+XTXθ?2XTy→)=XTXθ?XTy→(4)

最终3

3在上面推导过程中，利用第一节中列出的那5个结论。

，我们得到了最终的Normal Equation:XTXθ=XTy→

所以，梯度下降法就转变为一个矩阵计算：θ=(XTX)?1XTy→

但是，需要注意的是，不要以为式子变简单了，计算量就减少了，事实上，当X的维数很高时，计算量反而更大，因为大矩阵运算会消耗很多资源。

参考文献

• 斯坦福《机器学习》公开课第二集及其配套讲义

字数:1738

- EOF -

声明:本文采用协议进行授权.转载请注明: