首先引入一些后面会用到的定理：

定义1：定义函数$f: \Bbb R^{m \times n} \mapsto \Bbb R$，$A \in \Bbb R^{m \times n}$，定义
$$
\nabla_Af(A)=
\begin{bmatrix}
\frac{\partial f}{\partial A_{11}} & \cdots & \frac{\partial f}{\partial A_{1n}}\\
\vdots & \ddots & \vdots \\
\frac{\partial f}{\partial A_{m1}} & \cdots & \frac{\partial f}{\partial A_{mn}}
\end{bmatrix}
$$
定义2：矩阵的迹（Trace）：如果$A \in R^{n\times n}$方阵，那么$A$的迹，是$A$对角线元素之和
$$
tr A = \sum_{i=1}^nA_{ii}
$$
定理1：$tr AB = tr BA$

定理2：$tr ABC = tr CAB = tr BCA$

定理3：$f(A)=tr AB \Rightarrow \nabla_Af(A)=B^T$

定理4：$trA = tr A^T$

定理5：$a \in R \Rightarrow tr a=a$

定理6：$\nabla_AtrABA^TC=CAB+C^TAB^T$

线性回归

一些符号的改写

上一篇博客提到，梯度下降的每一步，对某个参数$\theta_i$，执行：
$$
\displaystyle \theta_i:=\theta_i - \alpha\frac{\partial}{\partial \theta_i}J(\theta)
$$
那么，$h_\theta(x)$的所有参数$\theta$可以表示成一列向量：
$$
\theta = \left[
\begin{array}{c}
\theta_0\\
\theta_1\\
\vdots\\
\theta_n
\end{array}
\right] \in R^{n+1}
$$

我们可以定义：
$$
\nabla_\theta J = \left[
\begin{array}{c}
\frac{\partial}{\partial \theta_0}J\\
\frac{\partial}{\partial \theta_1}J\\
\vdots\\
\frac{\partial}{\partial \theta_n}J
\end{array}
\right] \in R^{n+1}
$$

梯度下降过程可以表示成：
$$
\theta:=\theta - \alpha\nabla_\theta J
$$
其中，$\theta$和$\nabla_\theta J$都说是n+1维向量。

对于训练集中所有的输入${x^{(1)}},x^{(2)},…,x^{(m)}$，其中
$$
x^{(i)} = \left[
\begin{array}{c}
1\\
x_1^{(i)}\\
\vdots\\
x_n^{(i)}\\
\end{array}
\right] \in R^{n+1}
$$

$h(x)=h_{\theta}(x)=\theta_0+\theta_1x_1+\theta_2x_2+…+\theta_nx_n$，可以表示成向量：
$$
\left[
\begin{array}{c}
h_\theta(x^{(1)})\\
h_\theta(x^{(2)})\\
\vdots\\
h_\theta(x^{(m)})\\
\end{array}
\right] = \left[
\begin{array}{c}
(x^{(1)})^T\theta\\
(x^{(2)})^T\theta\\
\vdots\\
(x^{(m)})^T\theta\\
\end{array}
\right] = \left[
\begin{array}{c}
(x^{(1)})^T\\
(x^{(2)})^T\\
\vdots\\
(x^{(m)})^T
\end{array}
\right] \cdot \theta = X \cdot \theta
$$

而
$$
Y = \left[
\begin{array}{c}
y^{(1)}\\
y^{(2)}\\
\vdots\\
y^{(m)}
\end{array}
\right]
$$
于是，
$$
J(\theta) = \frac{1}{2}\sum_{i=1}^{m}(h(x^{(i)} - y^{(i)})^2)=\frac{1}{2}(X \cdot \theta - Y)^T(X \cdot \theta - Y)
$$

推导过程

关于梯度下降法，可以直接简化为求梯度为0的位置，即求$\nabla_\theta J(\theta) = \vec{0}$

首先，简化：
$$
\begin{align}
\nabla_\theta J(\theta) & = \nabla_\theta\frac{1}{2}(X \cdot \theta - Y)^T(X \cdot \theta - Y)\\
& =\frac{1}{2}\nabla_\theta tr(\theta^TX^TX\theta - \theta^TX^TY - Y^TX\theta + Y^TY)\\
& =\frac{1}{2}[\nabla_\theta tr(\theta\theta^TX^TX) - \nabla_\theta tr(Y^TX\theta) - \nabla tr(Y^TX\theta)]
\end{align}
$$
其中，第一项：
$$
\begin{align}
\nabla_\theta tr(\theta\theta^TX^TX) & = \nabla_\theta tr(\theta I \theta^TX^TX) &\text{定理6, set: $\theta =^{set} A, I = B, X^TX=C$}\\
& = X^TX\theta I + X^TX\theta I & \text{$CAB+C^TAB^T$}\\
& = X^TX\theta + X^TX\theta
\end{align}
$$
第二项和第三项：
$$
\nabla_\theta tr(Y^TX\theta) = X^TY\\
(定理3，set:Y^TX = B, \theta = A)
$$
所以：
$$
\nabla_\theta J(\theta) = X^TX\theta - X^TY = 0\\
\Rightarrow X^TX\theta = X^TY\\
$$
最后解得：
$$
\theta = (X^TX)^{(-1)}X^TY
$$
当然，以上的解是有限制的，只有当$X^TX$满秩时，才能够求逆。

如果非满秩，说明方程数量不够，也就是当需要n个参数时，却不够n个输入样本。