auto-grad

• 1. Base Principle
• 2. Useful Rules
  • 2.1. Differential
  • 2.2. Trace
• 3. Common differential calculations
  • 3.1. MSE
  • 3.2. Eigenvalue and Eigenvector
    • 3.2.1. Eigenvalue
    • 3.2.2. Eigenvector

1. Base Principle

$l=f(A),f:{\mathbb{R}}^{m\times n}\to \mathbb{R},f\in {\mathcal{C}}^1$

$$\begin{array}{r}\frac{\partial f}{\partial A}=\left[\begin{array}{cccc}\frac{\partial f}{\partial A_{1,1}}& \frac{\partial f}{\partial A_{1,2}}& \cdots & \frac{\partial f}{\partial A_{1,n}}\\ \frac{\partial f}{\partial A_{2,1}}& \frac{\partial f}{\partial A_{2,2}}& \cdots & \frac{\partial f}{\partial A_{2,n}}\\ ⋮& ⋮& \ddots & ⋮\\ \frac{\partial f}{\partial A_{m,1}}& \frac{\partial f}{\partial A_{m,2}}& \cdots & \frac{\partial f}{\partial A_{m,n}}\end{array}\right]\end{array}$$ $$\begin{array}{rl}dl& =tr(dl)\\ & =tr(df(A))\\ & =tr(\sum _{i,j}\frac{\partial f}{\partial A_{i,j}}d{A}_{i,j})\\ & =tr((\frac{\partial f}{\partial A}{)}^{T}dA)\end{array}$$

$\forall dA,dl=tr(B^{T}dA)⟹\frac{\partial f}{\partial A}=B$

So all we need to do is to find a $B$ that satisfies $\forall dA,dl=tr(B^{T}dA)$.

2. Useful Rules

2.1. Differential

• Addition rule: $d(X\pm Y)=dX\pm dY$
• Product rule: $d(XY)=(dX)Y+XdY$
• Inverse: $d{X}^{-1}=-X^{-1}dX{X}^{-1}$
• Transpose: $d(X^T)=(dX{)}^T$
• Trace: $d\text{tr}(X)=\text{tr}(dX)$
• Determinant: $d|X|=\text{tr}(X^{\#}dX)$, where $X^{\#}$ is the adjugate matrix
• Hadamard product: $d(X\odot Y)=dX\odot Y+X\odot dY$
• Component-wise(element-wise) function: $d\sigma (X)={\sigma }^{\prime }(X)\odot dX$

2.2. Trace

• Scalar trace: $a=\text{tr}(a)$
• Transpose: $\text{tr}(A^T)=\text{tr}(A)$
• Linearity: $\text{tr}(aA+bB)=a\text{tr}(A)+b\text{tr}(B)$
• Cyclic property: $\text{tr}(AB)=\text{tr}(BA)$, where $A$ and $B^T$ are conformable. Both equal to ${\sum }_{i,j}{A}_{ij}{B}_{ji}$
• Cyclic property with Hadamard product: $\text{tr}(A^T(B\odot C))=\text{tr}((A\odot B{)}^{T}C)$, where $A,B,C$ have the same dimensions. Both equal to ${\sum }_{i,j}{A}_{ij}{B}_{ij}{C}_{ij}$

3. Common differential calculations

• $n$ : dimension of output
• $\hat{\mathbf{y}}$ : predicted value
• $\mathbf{y}$ : target value

3.1. MSE

$\hat{\mathbf{y}}=W\mathbf{x}+\mathbf{b}$

$l={\sum }_{i=1}^n(y_i-{\hat{y}}_i{)}^2=(\hat{\mathbf{y}}-\mathbf{y}{)}^T(\hat{\mathbf{y}}-\mathbf{y})$

let $\mathbf{t}=\hat{\mathbf{y}}-\mathbf{y}$,

$dl=tr(dl)=tr({\mathbf{t}}^{T}d\mathbf{t}+d{\mathbf{t}}^T\mathbf{t})=tr({\mathbf{t}}^{T}d\mathbf{t})+tr(d{\mathbf{t}}^T\mathbf{t})=tr((2\mathbf{t}{)}^{T}d\mathbf{t})$

Thus.
$\frac{\partial l}{\partial \mathbf{t}}=2\mathbf{t}$

$d\mathbf{t}=d(\hat{\mathbf{y}}-\mathbf{y})=d\hat{\mathbf{y}}$

$\frac{\partial l}{\partial \hat{\mathbf{y}}}=2\mathbf{t}$

$d\hat{\mathbf{y}}=d(W\mathbf{x}+\mathbf{b})=dW\mathbf{x}$

$dl=tr((\frac{\partial l}{\partial \hat{\mathbf{y}}}{)}^{T}dW\mathbf{x})=tr(\mathbf{x}(\frac{\partial l}{\partial \hat{\mathbf{y}}}{)}^{T}dW)=tr(((\frac{\partial l}{\partial \hat{\mathbf{y}}}){\mathbf{x}}^T{)}^{T}dW)$

$\frac{\partial l}{\partial W}=(\frac{\partial l}{\partial \hat{\mathbf{y}}}){\mathbf{x}}^T$ = $2\mathbf{t}{\mathbf{x}}^T$

3.2. Eigenvalue and Eigenvector

Suppose $A\in {\text{Sym}}_n(\mathbb{R})$, then $A$ can be decomposed as

$$A=Q\Lambda Q^T$$ $$\begin{gathered} \Lambda =\text{diag}({\lambda }_1,{\lambda }_2,\cdots ,{\lambda }_n),{\lambda }_i\le {\lambda }_{i+1} \\ Q=({\mathbf{q}}_1,{\mathbf{q}}_2,\cdots ,{\mathbf{q}}_n)\in {\mathbf{O}}_n(\mathbb{R}),\text{where }{\mathbf{O}}_n(\mathbb{R})=\{\mathbf{M}\in {\mathbb{R}}^{n\times n}\mid {\mathbf{M}}^T\mathbf{M}=\mathbf{I}\} \end{gathered}$$

where ${\lambda }_i$ are the eigenvalues of $A$ and $Q$ is the eigenvector matrix.

3.2.1. Eigenvalue

$$\begin{array}{rl}\Lambda & =Q^{T}AQ\\ d\Lambda & =Q^{T}dAQ\\ dl& =tr(dl)\\ & =tr((\frac{\partial l}{\partial \Lambda }{)}^{T}d\Lambda )\\ & =tr((\frac{\partial l}{\partial \Lambda }{)}^T{Q}^{T}dAQ)\\ & =tr(Q(\frac{\partial l}{\partial \Lambda }{)}^T{Q}^{T}dA)\\ & =tr((Q\frac{\partial l}{\partial \Lambda }{Q}^T{)}^{T}dA)\end{array}$$

Thus,

$$\frac{\partial l}{\partial A}=Q\frac{\partial l}{\partial \Lambda }{Q}^T$$

3.2.2. Eigenvector

$Q^{T}dQ+d{Q}^{T}Q=0$, because $Q^{T}Q=\mathbf{I}$
Let $H=Q^{T}dQ$

$$\begin{array}{rl}dA& =dQ\Lambda Q^T+Qd\Lambda Q^T+Q\Lambda d{Q}^T\\ Q^{T}dAQ& =(Q^{T}dQ)\Lambda +d\Lambda +\Lambda (d{Q}^{T}Q)\\ & =H\Lambda +d\Lambda +\Lambda H\end{array}$$ $$\begin{array}{rl}(Q^{T}dAQ{)}_{ii}& =d{\Lambda }_{ii}\\ \forall i\ne j,(Q^{T}dAQ{)}_{ij}& =H_{ij}({\lambda }_j-{\lambda }_i)\\ \forall i\ne j,H_{ij}& =\frac{1}{{\lambda }_j-{\lambda }_i}(Q^{T}dAQ{)}_{ij}\\ \forall i,H_{ii}& =0\end{array}$$

Let $F_{ij}=\{\begin{array}{ll}\frac{1}{{\lambda }_j-{\lambda }_i}& \text{if }i\ne j\\ 0& \text{if }i=j\end{array}$

$H=F\odot (Q^{T}dAQ)$

$$\begin{array}{rl}tr(dl)& =tr({\frac{\partial l}{\partial Q}}^{T}dQ)\\ & =tr({\frac{\partial l}{\partial Q}}^{T}QH)\\ & =tr\left((Q^T\frac{\partial l}{\partial Q}{)}^T(F\odot (Q^{T}dAQ))\right)\\ & =tr\left({\left((Q^T\frac{\partial l}{\partial Q})\odot F\right)}^T(Q^{T}dAQ)\right)\\ & =tr\left(Q{\left((Q^T\frac{\partial l}{\partial Q})\odot F\right)}^T{Q}^{T}dA\right)\end{array}$$