title: 2. 线性回归 date: 2018-06-03 20:04:00 categories: 课堂笔记 tags: [机器学习,课堂笔记] mathjax: true

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

定义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_AtrABATC=CAB+CTAB^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(\thetaTXTX\theta - \thetaTXTY - YTX\theta + YTY)\
& =\frac{1}{2}[\nabla_\theta tr(\theta\thetaTXTX) - \nabla_\theta tr(YTX\theta) - \nabla tr(YTX\theta)] \end{align} $$ 其中，第一项： $$ \begin{align} \nabla_\theta tr(\theta\thetaTXTX) & = \nabla_\theta tr(\theta I \thetaTXTX) &\text{定理6, set: $\theta ={set} A, I = B, XTX=C$}\
& = XTX\theta I + XTX\theta I & \text{$CAB+CTABT$}\
& = XTX\theta + XTX\theta \end{align} $$ 第二项和第三项： $$ \nabla_\theta tr(YTX\theta) = XTY\
(定理3，set:YTX = B, \theta = A) $$ 所以： $$ \nabla_\theta J(\theta) = XTX\theta - XTY = 0\
\Rightarrow XTX\theta = XTY\
$$ 最后解得： $$ \theta = (XTX){(-1)}XTY $$ 当然，以上的解是有限制的，只有当$XTX$满秩时，才能够求逆。

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