机器学习

ML

---

梯度下降

对于$f:\mathbb{R}^{n\times m}\mapsto \mathbb{R}$，定义

$$\nabla_A f(A)= \begin{bmatrix} \frac{\partial f}{\partial A_{1,1}} & \cdots & \frac{\partial f}{\partial A_{1,m}} \\ \vdots & \ddots & \vdots \\ \frac{\partial f}{\partial A_{n,1}} & \cdots & \frac{\partial f}{\partial A_{n,m}} \end{bmatrix}$$

显然有$\nabla_{A^{\rm T}}f(A)=(\nabla_Af(A))^{\rm T}$。

对$n\times n$的方阵$A$定义$\mathrm{tr}\ A=\sum_{i=1}^n A_{i,i}$。

$\mathrm{tr}\ A^{\rm T}=\mathrm{tr}\ A$和$\mathrm{tr}\ A+\mathrm{tr}\ B=\mathrm{tr}\ (A+B)$以及$\mathrm{tr}\ (k\cdot A)=k\cdot \mathrm{tr}\ A$都是显然的。

之后

$$\mathrm{tr}\ AB=\sum_{i=1}^n\sum_{j=1}^n A_{i,j}B_{j,i}=\mathrm{tr}\ BA$$
也不难得到。

$\nabla_A \mathrm{tr}\ AB=B^{\rm T}$是显然的。

以下先讨论$x\neq y$的情形。

$$\begin{align*} (\nabla_A \mathrm{tr}\ CABA^{\rm T})_{x,y} &= \partial(\sum_{i=1}^n\sum_{j=1}^n (CA)_{i,j}(BA^{\rm T})_{j,i})\frac{1}{\partial A_{x,y}} \\ &= \partial(\sum_{i\neq x} (CA)_{i,y}(BA^{\rm T})_{y,i}+\sum_{j\neq y}(CA)_{x,j}(BA^{\rm T})_{j,x}+(CA)_{x,y}(BA^{\rm T})_{y,x})\frac{1}{\partial A_{x,y}} \end{align*}$$

分别展开

$$\partial\left(\sum_{i\neq x} (CA)_{i,y}(BA^{\rm T})_{y,i}\right)\frac{1}{\partial A_{x,y}} = \sum_{i\neq x}C_{i,x}(BA^{\rm T})_{y,i}=\sum_{i\neq x}(C^{\rm T})_{x,i}(AB^{\rm T})_{i,y}$$

$$\partial\left(\sum_{j\neq y} (CA)_{x,j}(BA^{\rm T})_{j,x}\right)\frac{1}{\partial A_{x,y}} = \sum_{j\neq y}(CA)_{x,j}B_{j,y}$$

$$\begin{align*} \partial((CA)_{x,y}(BA^{\rm T})_{y,x})\frac{1}{\partial A_{x,y}}&= \partial\left(\sum_{k=1}^nC_{x,k}A_{k,y}\sum_{p=1}^n B_{y,p}A_{x,p}\right)\frac{1}{\partial A_{x,y}} \\ &= C_{x,x}\sum_{p\neq y}B_{y,p}A_{x,p}+B_{y,y}\sum_{k\neq x}C_{x,k}A_{k,y}+\frac{\partial C_{x,x}B_{y,y}A_{x,y}^2}{\partial A_{x,y}} \\ &= C_{x,x}\sum_{p=1}^nB_{y,p}A_{x,p}+B_{y,y}\sum_{k=1}^nC_{x,k}A_{k,y} \end{align*}$$

综上

$$(\nabla_A \mathrm{tr}\ CABA^{\rm T})_{x,y}=(CAB+C^{\rm T}AB^{\rm T})_{x,y}$$

令$X=\begin{bmatrix}x^{(1)} \\ x^{(2)} \\ \vdots \\ x^{(n)} \end{bmatrix}$。

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

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

$$\begin{align*} \nabla_{\theta}J(\theta)&=\frac{1}{2}(X\theta-\vec{y})^T(X\theta-\vec{y}) \\ &= \frac{1}{2} \nabla_{\theta} (\theta^{\rm T}X^{\rm T}X\theta-\theta^{\rm T}X^{\rm T}\vec{y}-\vec{y}^{\rm T}X\theta+\vec{y}^{\rm T}\vec{y}) \\ &= \frac{1}{2} \nabla_{\theta} \mathrm{tr}\ (\theta^{\rm T}X^{\rm T}X\theta-\theta^{\rm T}X^{\rm T}\vec{y}-\vec{y}^{\rm T}X\theta) \end{align*}$$