设 $X$ 是训练数据组成的矩阵，每一行代表一条训练数据，每一列代表一种特征。设 $Y$ 是训练数据的“正确答案”组成的向量，再设 $ heta$ 是每种特征的权值组成的向量，linear regression 的目的就是通过让代价函数 $J( heta) = frac{1}{2}(X heta-Y)^T(X heta-Y)$ 最小化，获得一个最优的 $ heta$，从而对新的数据做出正确的推断。
我们当然可以使用梯度下降法慢慢调整 $ heta$，使得代价函数下降，但我们还可以推导一个 normal equation，通过等式直接求出最优的 $ heta$。
Normal equation 的推导思想，就是让 $ abla_ heta J( heta) = 0$，从而解出最优的 $ heta$。这就要求代价函数是一个凸函数（因为凸函数的局部最优值就是全局最优值）。我们首先来看代价函数在什么情况下是凸函数。
代价函数为凸函数的条件
根据凸函数的定义，只有满足 $f(tx+(1-t)y) le tf(x) + (1-t)f(y)quad (0 < t < 1)$ 时 $f$ 才是凸函数。所以我们需要证明： $$J(t heta_1 + (1-t) heta_2) le tJ( heta_1) + (1-t)J( heta_2)$$ 经过一番展开和化简之后，我们可以将证明的目标简化为： $$ heta_1T(XTX) heta_1 + heta_2T(XTX) heta_2 ge heta_1T(XTX) heta_2 + heta_2T(XTX) heta_1$$ 移项与合并后，我们发现，只需要满足：$$( heta_1- heta_2)T(XTX)( heta_1- heta_2)ge0$$ 代价函数就是凸函数。根据半正定矩阵的定义，只有 $(X^TX)$ 是半正定矩阵时，该不等式成立。而 $(X^TX)$ 很显然是半正定的，因为对于任意向量 $a$，我们都有 $$aT(XTX)a = (Xa)^T(Xa) ge 0$$
梯度的推导
我们接下来计算 $ abla_ heta J( heta) = 0$ 成立时 $ heta$ 的值。首先推导三个等式。
等式 1：$ abla_A ext{tr}(AB) = B^T$
直接把矩阵的迹展开成矩阵元素的形式即可证明：$$ ext{tr}(AB) = sum_isum_ja_{i,j}b_{j,i}$$ $$frac{partial}{partial a_{i,j}} ext{tr}(AB) = b_{j,i}$$ $$ abla_A ext{tr}(AB) = B^T$$ 同理还能证明 $ abla_A ext{tr}(A^TB) = B$
等式 2：$ ext{tr}(A_1A_2dots A_n) = ext{tr}(A_nA_1A_2dots A_{n-1})$
我们先证明 $ ext{tr}(AB) = ext{tr}(BA)$：$$ ext{tr}(AB) = sum_isum_ja_{i,j}b_{j,i} = sum_jsum_ib_{j,i}a_{i,j} = ext{tr}(BA)$$ 再证明原等式： $$ ext{tr}(A_1A_2dots A_n) = ext{tr}((A_1A_2dots A_{n-1})A_n) = ext{tr}(A_nA_1A_2dots A_{n-1})$$
等式 3：$ abla_A ext{tr}(ABA^TC) = CAB+CTABT$
网络上貌似有很多精巧的证明方法，不过我都不怎么懂- -，还是暴力展开比较实在：$$ ext{tr}(ABA^TC) = sum_isum_jsum_ksum_la_{i,j}b_{j,k}a_{l,k}c_{l,i}$$ $$frac{partial}{partial a_{i,j}} ext{tr}(ABATC)=sum_ksum_lb_{j,k}a_{l,k}c_{l,i}=(BATC)_{j,i}$$ $$frac{partial}{partial a_{l,k}} ext{tr}(ABA^TC)=sum_ksum_la_{i,j}b_{j,k}c_{l,i}=(CAB)_{l,k}$$ 要注意矩阵 $A$ 中元素的偏导会出现两次，例如与 $a_{1,2}$ 有关的偏导会在 $i=1,j=2$ 时出现一次，还会在 $l=1,k=2$ 时出现一次，所以我们要把两个偏导结果加起来，得到：$$ abla_A ext{tr}(ABA^TC) = (BATC)T + CAB = CAB+CTABT$$
有了以上三个等式，我们就可以推导梯度了。
首先把代价函数全部展开，获得：$$J( heta) = hetaTXTX heta - hetaTXTY - Y^TX heta + Y^TY$$ 由于数值的迹等于自身，我们有：$$J( heta) = ext{tr}( hetaTXTX heta - hetaTXTY - Y^TX heta + Y^TY)$$ $$= ext{tr}( hetaTXTX heta) - ext{tr}( hetaTXTY) - ext{tr}(Y^TX heta) + ext{tr}(Y^TY)$$ 我们把梯度加进去，由于最后一项和 $ heta$ 无关，可以直接略去。有：$$ abla_ heta J( heta) = abla_ heta ext{tr}( hetaTXTX heta) - abla_ heta ext{tr}( hetaTXTY) - abla_ heta ext{tr}(Y^TX heta)$$ 对第一项和第三项使用公式 2：$$ abla_ heta J( heta) = abla_ heta ext{tr}( heta hetaTXTX) - abla_ heta ext{tr}( hetaTXTY) - abla_ heta ext{tr}( heta Y^TX)$$ 对第一项使用公式 3（令 $A = heta, B = I,C = X^TX$，其中 $I$ 是单位矩阵）：$$ abla_ heta ext{tr}( heta hetaTXTX) = X^TX heta + X^TX heta = 2X^TX heta$$ 对第二项和第三项使用公式 1：$$ abla_ heta ext{tr}( hetaTXTY) = X^TY$$ $$ abla_ heta ext{tr}( heta Y^TX) = X^TY$$ 所以 $$ abla_ heta J( heta) = 2X^TX heta - 2X^TY = 0$$ $$X^TX heta = X^TY$$ 这就是 normal equation。
若 $(X^TX)$ 为正定矩阵，则由正定矩阵的行列式大于 0 可知正定矩阵一定有逆矩阵，我们有 $$ heta = (XTX){-1}X^TY$$ 若 $(X^TX)$ 不可逆，似乎也可以用伪逆矩阵带入算出 $ heta$，不过我并不知道为什么这样是正确的...