CS229 笔记 02

公式推导

$ {\text {For simplicity, Let}} A, B, C \in {\Bbb {R}}^{n \times n}. $ ​

$ {\bf {\text {Fact.1:}}} \text{If } a \in {\Bbb R}, {\rm tr}a=a $

$ {\bf {\text {Fact.2:}}} {\rm{tr}}A={\rm{tr}}A^{\rm T} $

$$ \begin{eqnarray*} {\rm{tr}}\,A&=&\sum_{i=1}^n{a_{ii}} \\[1em] &=&{\rm{tr}}\,A^{\rm T} \end{eqnarray*} $$

$ {\bf {\text {Fact.3:}}} {\rm{tr}}AB={\rm{tr}}BA $

$$ \begin{eqnarray*} {\rm tr}\,AB&=&\sum_{i=1}^n{[AB]_{ii}} \\[1em] &=&\sum_{i=1}^n{\sum_{k=1}^{n}{a_{ik}\,b_{ki}}} \\[1em] &=&\sum_{i=1}^n{\sum_{k=1}^{n}{b_{ki}\,a_{ik}}} \\[1em] &=&\sum_{i=1}^n{\sum_{k=1}^{n}{b_{ik}\,a_{ki}}} \\[1em] &=&\sum_{i=1}^n{[BA]_{ii}} \\[1em] &=&{\rm tr}\,BA \\ \end{eqnarray*} $$

$ {\bf {\text {Fact.4:}}} {\rm{tr}}ABC={\rm{tr}}CAB={\rm{tr}}BCA $

$$ \begin{eqnarray*} {\rm tr}\,ABC&=&{\rm tr}\,(AB)C \\[1em] &=&{\rm tr}\,C(AB) \tag{Fact.3} \\[1em] &=&{\rm tr}\,A(BC) \\[1em] &=&{\rm tr}\,(BC)A \tag{Fact.3} \\[1em] \end{eqnarray*} $$

$ {\bf {\text {Fact.5:}}} \nabla_A\rm{tr}AB=B^{\rm T} $

$$ \begin{eqnarray*} {\rm{tr}\, AB}&=&\sum_{i=1}^n{[AB]_{ii}}=\sum_{i=1}^n{\sum_{k=1}^n{a_{ik}\,b_{ki}}} \\[1em] \nabla_A{\rm{tr}}AB&=&\frac{\partial{\rm{tr}}AB}{\partial A} \\[1em] &=&\begin{bmatrix}\frac{\partial{\rm{tr}}AB}{\partial a_{11}} & \frac{\partial{\rm{tr}}AB}{\partial a_{12}} & \cdots & \frac{\partial{\rm{tr}}AB}{\partial a_{1n}} \\[1em] \frac{\partial{\rm{tr}}AB}{\partial a_{21}} & \frac{\partial{\rm{tr}}AB}{\partial a_{22}} & \cdots & \frac{\partial{\rm{tr}}AB}{\partial a_{2n}} \\[1em] \vdots & \vdots & \ddots & \vdots \\[1em] \frac{\partial{\rm{tr}}AB}{\partial a_{n1}} & \frac{\partial{\rm{tr}}AB}{\partial a_{n2}} & \cdots & \frac{\partial{\rm{tr}}AB}{\partial a_{nn}}\end{bmatrix} \\[1em] &=&\begin{bmatrix}\frac{\partial}{\partial a_{11}}{\sum_{i=1}^n{\sum_{k=1}^n{a_{ik}\,b_{ki}}}} & \frac{\partial}{\partial a_{12}}{\sum_{i=1}^n{\sum_{k=1}^n{a_{ik}\,b_{ki}}}} & \cdots & \frac{\partial}{\partial a_{1n}}{\sum_{i=1}^n{\sum_{k=1}^n{a_{ik}\,b_{ki}}}} \\[1em] \frac{\partial}{\partial a_{21}}{\sum_{i=1}^n{\sum_{k=1}^n{a_{ik}\,b_{ki}}}} & \frac{\partial}{\partial a_{22}}{\sum_{i=1}^n{\sum_{k=1}^n{a_{ik}\,b_{ki}}}} & \cdots & \frac{\partial}{\partial a_{2n}}{\sum_{i=1}^n{\sum_{k=1}^n{a_{ik}\,b_{ki}}}} \\[1em] \vdots & \vdots & \ddots & \vdots \\[1em] \frac{\partial}{\partial a_{n1}}{\sum_{i=1}^n{\sum_{k=1}^n{a_{ik}\,b_{ki}}}} & \frac{\partial}{\partial a_{n2}}{\sum_{i=1}^n{\sum_{k=1}^n{a_{ik}\,b_{ki}}}} & \cdots & \frac{\partial}{\partial a_{nn}}{\sum_{i=1}^n{\sum_{k=1}^n{a_{ik}\,b_{ki}}}}\end{bmatrix} \\[1em] &=&\begin{bmatrix} b_{11} & b_{21} & \cdots & b_{n1} \\ b_{12} & b_{22} & \cdots & b_{n2} \\ \vdots & \vdots & \ddots & \vdots \\ b_{1n} & b_{2n} & \cdots & b_{nn} \end{bmatrix} \\[1em] &=&B^{\rm T} \end{eqnarray*} $$

$ {\bf {\text {Fact.6:}}} \nabla_A{\rm{tr}}ABA^{\rm T}C=C^{\rm T}AB^{\rm T}+ CAB $

$$ \begin{eqnarray*} [\nabla_A{\rm{tr}}\,ABA^{\rm T}C]_{ij}&=&\frac{\partial}{\partial a_{ij}}{\rm{tr}}\,ABA^{\rm T}C \\[1em] &=&\frac{\partial}{\partial a_{ij}}\sum_{pqrs}{a_{pq}\,b_{qr}\,a_{sr}\,c_{sp}} \\[1em] &=&\sum_{pqrs}{b_{qr}\,a_{sr}\,c_{sp}\,[I]_{pi}\,[I]_{qj}} + \sum_{pqrs}a_{pq}\,b_{qr}\,c_{sp}\,[I]_{si}\,[I]_{rj} \\[1em] &=&\sum_{rs}b_{jr}\,a_{sr}\,c_{si} + \sum_{pq}a_{pq}\,b_{qj}\,c_{ip} \\[1em] &=&\sum_{rs}c_{si}\,a_{sr}\,b_{jr} + \sum_{pq}c_{ip}\,a_{pq}\,b_{qj} \\[1em] &=&\sum_{rs}[C^{\rm T}]_{is}\,a_{sr}\,[B^{\rm T}]_{rj} + \sum_{pq}c_{ip}\,a_{pq}\,b_{qj} \\[1em] &=&[C^{\rm T}AB^{\rm T}]_{ij}+ [CAB]_{ij} \\ \end{eqnarray*} \\ $$

$$ \therefore\,\nabla_A\,{\rm {tr}}\,ABA^{\rm T}C=C^{\rm T}AB^{\rm T}+ CAB $$

最小二乘法

假设有 $m$ 个样本 $ x^{(1)},x^{(2)},\cdots,x^{(m)}, x^{(i)} \in {\Bbb R}^{n} $ ，目标集为 $ y^{(1)},y^{(2)},\cdots,y^{(m)}, y^{(i)} \in {\Bbb R} $ .

令：

$$ X=\begin{bmatrix}1 & (x^{(1)})^{\rm T} \\ 1 & (x^{(2)})^{\rm T} \\ \vdots & \vdots \\ 1 & (x^{(m)})^{\rm T} \end{bmatrix}, Y=\begin{bmatrix}y^{(1)} \\ y^{(2)} \\ \vdots \\ y^{(m)} \end{bmatrix}, \Theta=\begin{bmatrix}\theta_{0} \\ \theta_{1} \\ \vdots \\ \theta_{n+1}\end{bmatrix} $$

$$ h(x^{(i)})=\theta_0 + \theta_1x^{(i)}_1 + \theta_2x^{(i)}_2 + \cdots + \theta_{n+1}x^{(i)}_{n+1} $$

整理： ​ $$ \begin{eqnarray*} X\Theta&=&h_\Theta(X) \tag{Eq.1}\\[1em] J_\Theta(X, Y)&=&\frac{1}{2}\begin{Vmatrix}h_\Theta(X) - Y\end{Vmatrix}^2 \\[1em] &=&\frac{1}{2}\begin{Vmatrix}X\Theta - Y\end{Vmatrix}^2 \\[1em] &=&\frac{1}{2}(X\Theta - Y)^{\rm T}(X\Theta - Y) \\[1em] &=&\frac{1}{2}(\Theta^{\rm T}X^{\rm T} - Y^{\rm T})(X\Theta - Y) \\[1em] &=&\frac{1}{2}(\Theta^{\rm T}X^{\rm T}X\Theta - Y^{\rm T}X\Theta - \Theta^{\rm T}X^{\rm T}Y + Y^{\rm T}Y) \tag{Eq.2}\\[1em] \nabla_\Theta{\rm{tr}}(\Theta^{\rm T}X^{\rm T}X\Theta)&=&\nabla_\Theta{\rm{tr}}(\Theta\Theta^{\rm T}X^{\rm T}X) \\[1em] &=&\nabla_\Theta{\rm{tr}}(\Theta I \Theta^{\rm T}X^{\rm T}X) \\[1em] &=&(X^{\rm T}X)^{\rm T}\Theta I^{\rm T} + (X^{\rm T}X)\Theta I \tag{Fact.6} \\[1em] &=&2X^{\rm T}X\Theta \tag{Eq.3} \\[1em] \nabla_\Theta{\rm{tr}}(Y^{\rm T}X\Theta)&=&\nabla_\Theta{\rm{tr}}(\Theta Y^{\rm T}X) \tag{Fact.4} \\[1em] &=&(Y^{\rm T}X)^{\rm T} \tag{Fact.5} \\[1em] &=&X^{\rm T}Y \tag{Eq.4} \\[1em] \nabla_\Theta{\rm{tr}}(\Theta^{\rm T}X^{\rm T}Y)&=&\nabla_\Theta{\rm{tr}}(\Theta^{\rm T}X^{\rm T}Y)^{\rm T} \tag{Fact.2} \\[1em] &=&\nabla_\Theta{\rm{tr}}(Y^{\rm T}X\Theta) \\[1em] &=&X^{\rm T}Y \tag{Eq.5} \\[1em] \end{eqnarray*} $$

令 $ \nabla_\Theta[J_\Theta(X, Y)] = 0 $

$$ \begin{eqnarray*} \nabla_\Theta[J_\Theta(X, Y)] &=& 0 \\[1em] \nabla_\Theta[\frac{1}{2}(\Theta^{\rm T}X^{\rm T}X\Theta - Y^{\rm T}X\Theta - \Theta^{\rm T}X^{\rm T}Y + Y^{\rm T}Y)] &=& 0 \tag{Eq.2} \\[1em] \nabla_\Theta{\rm{tr}}[\frac{1}{2}(\Theta^{\rm T}X^{\rm T}X\Theta - Y^{\rm T}X\Theta - \Theta^{\rm T}X^{\rm T}Y + Y^{\rm T}Y)] &=& 0 \tag{Fact.1}\\[1em] \nabla_\Theta\{\frac{1}{2}[{\rm{tr}}(\Theta^{\rm T}X^{\rm T}X\Theta) - {\rm{tr}}(Y^{\rm T}X\Theta) - {\rm{tr}}(\Theta^{\rm T}X^{\rm T}Y) + {\rm{tr}}(Y^{\rm T}Y)]\} &=& 0 \\[1em] \frac{1}{2}(2X^{\rm T}X\Theta - X^{\rm T}Y - X^{\rm T}Y) &=& 0 \tag{Eq.3.4.5} \\[1em] X^{\rm T}X\Theta - X^{\rm T}Y &=& 0 \\[1em] X^{\rm T}X\Theta &=& X^{\rm T}Y \\[1em] \Theta &=& (X^{\rm T}X)^{-1}X^{\rm T}Y \\[1em] \end{eqnarray*} $$

从线性空间上面理解

$X$ 可以看作是在 ${\Bbb R}^{m}$ 空间中的一个超平面（经过原点 $O$ ）， $Y$ 是空间中的一个点，最小二乘法的可以看作是在平面 $X$ 上面找一个点 $\hat{Y}$ ，使得 $\hat{Y}$ 与 $Y$ 距离最小。

由几何关系可知，当 $\overrightarrow{\hat{Y}Y}$ 与超平面垂直时，距离最短。

超平面为 $X$ 的列空间，即 $X^{\rm T}$ ，$\overrightarrow{\hat{Y}Y}=X\Theta-Y$ 。

由 $X^{\rm T} \bot (X\Theta-Y) $ 得：$X^{\rm T}(X\Theta-Y)={\bf 0}$ 。

解得：$\Theta = (X^{\rm T}X)^{-1}X^{\rm T}Y$