线性回归

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

定义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个输入样本。