CS 229 notes Supervised Learning

监督学习 线性代数

Forword

the proof of Normal equation and, before that, some linear algebra equations, which will be used in the proof.

The normal equation

Linear algebra preparation

For two matrices $A$ and $B$ such that $AB$ is square, $trAB\ = \ trBA$.

Proof: $trAB \ = \ \displaystyle{\sum_{i=1}^n(AB)_{ii} = \sum_{i=1}^n(\sum_{j=1}^nA_{ij}B_{ji}) = \sum_{i=1}^n\sum_{j=1}^n A_{ij}B_{ji} = \sum_{i=1}^n\sum_{j=1}^n B_{ij}A_{ji}} = trBA.$

Corollary: $trABC = trCAB = trBCA\space,$
$trABCD=trDABC=trCDAB=trBCDA.$

Some properties:
$1.\quad trA=trA^T\\ 2. \quad tr(A+B) = trA+trB\\ 3. \quad tr\space aA = a\space trA$

some facts of matrix derivative:
$\nabla_AtrAB=B^T...................................................................(1)$

Proof: since $trAB = \displaystyle{\sum_{i=1}^n\sum_{j=1}^nA_{ij}B_{ji}}$

$\nabla_{A^T}f(A) = (\nabla_Af(A))^T...........................................................(2)$
$\nabla_AtrABA^TC = CAB+C^TAB^T..................................................(3)$

Proof 1:
assume $A$ to be a $m\times n$ matrix, then $B$ will be a $n \times n$ matrix while $C$ is a $m \times m$ matrix.
$trABA^TC = \displaystyle{\sum_{i=1}^m(ABA^TC)_{ii} = \sum_{i=1}^m\sum_{j=1}^n(AB)_{ij}(A^TC)_{ji} = \sum_{i=1}^m\sum_{j=1}^n(\sum_{k=1}^nA_{ik}B_{kj})(\sum_{l=1}^m(A^T_{jl}C_{li})\\ =\sum_{i=1}^m\sum_{j=1}^n\sum_{k=1}^n\sum_{l=1}^mA_{ik}B_{kj}A^T_{jl}C_{li}=\sum_{i=1}^m\sum_{j=1}^n\sum_{k=1}^n\sum_{l=1}^mA_{ik}A_{lj}B_{kj}C_{li}}$
$(\nabla_AABA^TC)_{pq} =\frac{\partial trABA^TC}{\partial A_{pq} }=\frac{\partial}{\partial A_{pq} } \displaystyle{ \sum_{i=1}^m\sum_{j=1}^n\sum_{k=1}^n\sum_{l=1}^mA_{ik}A_{jl}B_{kj}C_{li}\\ = \sum_{j=1}^n\sum_{l=1}^mA_{lj}B^T_{jg}C_{lp} + \sum_{i=1}^m\sum_{j=1}A_{ik}B_{kq}C_{pi}}$
$\displaystyle{= \sum_{j=1}^n\sum_{l=1}^mC^T_{pl}A_{lj}B_{qj} + \sum_{i=1}^m\sum_{j=1}A_{ik}B_{kq}C_{pi}}$
$\displaystyle{= \sum_{j=1}^n\sum_{l=1}^m(C^TA)_{pj}B^T_{jq} + \sum_{i=1}^m\sum_{j=1}C_{pi}(AB)_{iq}}$
$\displaystyle{= \sum_{j=1}^n\sum_{l=1}^m(C^TAB^T)_{pq} + \sum_{i=1}^m\sum_{j=1}(CAB)_{pq}}$
Hence we have $\nabla_AtrABA^TC = CAB+C^TAB^T$.

Proof 2:
View this problem as a question of linear transformations. So $A,B,C$ are three linear transformations.

$tr(A+\Delta A)B(A+\Delta A)^TC - trABA^TC \\= tr(A+\Delta A)B(A^T+\Delta A^T)C-trABA^TC\\ = tr(\Delta A)BA^TC+trAB(\Delta A^T)C$

According to the property $1,2$,
$tr(\Delta A)BA^TC = tr((\Delta A)BA^TC)^T=trC^TAB^T(\Delta A^T)$,

$trAB(\Delta A^T)C = trCAB(\Delta A^T)$.

Thus, $tr(\Delta A)BA^TC+trAB(\Delta A^T)C\\ = trCAB(\Delta A^T)+trC^TAB^T(\Delta A^T)$
This expression can and should be viewed as a linear mapping acting on the vector $\Delta A$, and this view gives us the desired result.

$\nabla_A|A| = |A|(A^{-1})^T.............................................................(4)$

Proof: $(\nabla_A |A|)_{pq} = C_{pq} = A^*_{qp} = (A^*)^T_{pq} = |A|(A^{-1})_{pq}$
($C$ refers to the cofactor)

Least squares revisited

$X = \begin{bmatrix}—(x^{(1)})^T—\\—(x^{(2)})^T—\\.\\.\\.\\—(x^{(m)})^T—\end{bmatrix}$(if we don't include the intercept term)

$\vec y = \begin{bmatrix}y^{(1)}\\y^{(2)}\\.\\.\\.\\y^{(m)}\end{bmatrix}$

since $h_\theta(x^{(i)} = (x^{(i)})^T\theta$,

$X\theta - \vec{y} = \begin{bmatrix}(x^{(1)})^T\theta\\(x^{(2)})^T\theta\\.\\.\\.\\(x^{(m)})^T\theta\end{bmatrix} - \begin{bmatrix}y^{(1)}\\y^{(2)}\\.\\.\\.\\y^{(m)}\end{bmatrix} = \begin{bmatrix}h_\theta(x^{(1)})-y^{(1)}\\h_\theta(x^{(2)})-y^{(2)}\\.\\.\\.\\h_\theta(x^{(m)})-y^{(m)}\end{bmatrix}$

Thus,
$\frac{1}{2}(X\theta-\vec{y})^T(X\theta-\vec{y}) = \frac{1}{2}\displaystyle{\sum_{i=1}^{m}(h_\theta(x^{(i)}) -y^{(i)})^2} = J(\theta)$.

Combine Equations $(2),(3)$：
$\nabla_{A^T}trABA^TC = B^TA^TC^T+BA^TC..............................................(5)$

Hence $\nabla_\theta J(\theta) = \frac{1}{2}\nabla_\theta(X\theta-\vec{y})^T(X\theta-\vec{y})\\ = \frac{1}{2}\nabla_\theta(\theta^TX^TX\theta-\theta^TX^T\vec{y}-\vec{y}X\theta -({\vec{y}})^T\vec{y})$

Notice it is a real number, or you can see it as a $1\times 1$ matrix, so
$\frac{1}{2}\nabla_\theta(\theta^TX^TX\theta-\theta^TX^T\vec{y}-\vec{y}\theta X -({\vec{y}})^T\vec{y}) \\= \frac{1}{2}\nabla_\theta tr(\theta^TX^TX\theta-\theta^TX^T\vec{y}-\vec{y} X\theta -({\vec{y}})^T\vec{y}) \\= \frac{1}{2}\nabla_\theta(tr\theta^TX^TX\theta - 2tr\vec{y} X\theta)$
since $trA = trA^T$ and $\vec y$ involves no $\theta$ elements.
then use equation $(5)$ with $A^T = \theta, B = B^T = X^TX, C = I$，

$J(\theta)= \frac{1}{2}\nabla_\theta(tr\theta^TX^TX\theta - 2tr\vec{y} X\theta) \\= \frac{1}{2}(X^TX\theta+X^TX\theta-2X^T\vec{y}) \\ = X^TX\theta-X^T\vec{y}$
To minmize $J$， we set its derivative to zero, and obtain the normal equation:
$X^TX\theta = X^T\vec{y}$
$\theta = (X^TX)^{-1}X^T\vec{y}$