“所有数值计算归根结底是一系列有限的可微算子的组合”
——《An introduction to automatic differentiation

### 符号语言的导数

《Deep Learning》 Chap 6.5.5

### Backpropagation algorithm

1. Input $x$ : Set the corresponding activation $a^1$ for the input layer.
2. Feedforward : For each $l=2,3,…,L$ compute $z^l = w^la^{l-1}+b^l$ and $a^l = \sigma (z^l)$
3. Output error $\delta^L$ : Compute the vector $\delta^L = \nabla_aC \bigodot \sigma^\prime(z^L)$
4. Backpropagate the error : For each $l=L-1,L-2,…,2$ compute $\delta^l = ((w^{l+1})^{\top} \delta^{l+1}) \bigodot \sigma^\prime(z^l)$
5. Output : The gradient of the cost function is given by $\frac{\partial C}{\partial w_{jk}^l} = a_k^{l-1}\delta_j^l$ and $\frac{\partial C}{\partial b_{j}^l} = \delta_j^l$

• We’ll use $w_{jk}^l$ to denote the weight for the connection from the kthkth neuron in the $(l-1)^{th}$ layer to the $j^{th}$ neuron in the $l^{th}$ layer.
• We use $b_j^l$ for the bias of the $j^{th}$ neuron in the $l^{th}$ layer. And we use $a_j^l$ for the activation of the $j^{th}$ neuron in the $l^{th}$ layer.
• We use $s \bigodot t$ to denote the elementwise product of the two vectors. Thus the components of $s \bigodot t$ are just $(s \bigodot t)_j=s_j t_j$

### Automatic Differentiation

CSE599G1: Deep Learning System (陈天奇)

• 手动求解法(Manual Differentiation)
• 求解出梯度公式，然后编写代码，代入实际数值，得出真实的梯度。在这样的方式下，每一次我们修改算法模型，都要修改对应的梯度求解算法，因此没有很好的办法解脱用户手动编写梯度求解的代码。
• 数值微分法(Numerical Differentiation)
• 符号微分法(Symbolic Differentiation)

• “表达式膨胀”（expression swell）问题，如果不加小心就会使得问题符号微分求解的表达式急速“膨胀”，导致最终求解速度变慢，如本小节末的图表Table 1所示。
• Implement differentiation rules:
• Product Rule: $\frac{d(f+g)}{dx}=\frac{df}{dx}+\frac{dg}{dx}$
• Sum Rule: $\frac{d(fg)}{dx}=\frac{df}{dx}g+f\frac{dg}{dx}$
• Chain Rule: $\frac{d(h(x))}{dx}=\frac{df(g(x))}{dx}+\frac{dg(x)}{x}$
• 自动微分法(Automatic Differentiation)

• 自动微分法是一种介于符号微分和数值微分的方法：数值微分强调一开始直接代入数值近似求解；符号微分强调直接对代数进行求解，最后才代入问题数值；自动微分将符号微分法应用于最基本的算子，比如常数，幂函数，指数函数，对数函数，三角函数等，然后代入数值，保留中间结果，最后再应用于整个函数。因此它应用相当灵活，可以做到完全向用户隐藏微分求解过程，由于它只对基本函数或常数运用符号微分法则，所以它可以灵活结合编程语言的循环结构，条件结构等，使用自动微分和不使用自动微分对代码总体改动非常小，并且由于它的计算实际是一种图计算，可以对其做很多优化，这也是为什么该方法在现代深度学习系统中得以广泛应用。

### Backpropagation vs AutoDiff (reverse)

CSE599G1 DeepLearning System Lecture4 —— Slides View

• We can take derivative of derivative nodes in autodiff, while it’s much harder to do so in backprop.
• In autodiff, there’s only a forward pass (vs. forward-backward in backprop). So it’s easier to apply graph and schedule optimization to a single graph.
• In backprop, all intermediate results might be used in the future, so we need to keep these values in the memory. On the other hand, in autodiff, we already know the dependencies of the backward graph, so we can have better memory optimization.

### Jacobi与链式法则

《Deep Learning》 Chap 6.5.2

https://github.com/exacity/deeplearningbook-chinese

### Tensorflow的自动求导实现

“Constructs symbolic derivatives of sum of ys w.r.t. x in xs
[db, dW, dx] = tf.gradients(C, [b,W,x])

《Deep Learning》一书中，表示TheanoTensorflow采用如下图算法的子程序来建立 $grad_table$，而在Tensorflow白皮书的第五节中，介绍了在$grad_table$中，存储了通常会被重复计算多次的 $\partial u^{(n)} / \partial u^{(i)}$，用以减少程序的冗余计算从而增加效率：

If a tensor $C$ in a TensorFlow graph depends, perhaps through a complex subgraph of operations, on some set of tensors $X_k$, then there is a built-in function that will return the tensors ${dC/dX_k}$.

$op.bprop$ 方法应该总是假装它的所有输入彼此不同，即使它们不是。例如，如果 $mul$ 操作传递两个 $x$ 来计算 $x^2$，$op.bprop$ 方法应该仍然返回 $x$ 作为对于两个输入的导数。反向传播算法后面会将这些变量加起来获得 $2x$，这是 $x$ 上总的正确的导数。

## 其它：PyTorch的自动求导

PyTorch提供了包torch.autograd用于自动求导。在前向过程中，PyTorch会构建计算图，每个节点用Variable表示，表示由输入节点到输出节点的函数（torch.autograd.Function对象）。Function对象不仅负责执行前向计算，在反向过程中，每个Function对象会调用.backward()函数计算输出对输入的梯度，然后将梯度传递给下一个Function对象。

### How autograd encodes the history (PyTorch)

An important thing to note is that the graph is recreated from scratch at every iteration, and this is exactly what allows for using arbitrary Python control flow statements, that can change the overall shape and size of the graph at every iteration. You don’t have to encode all possible paths before you launch the training - what you run is what you differentiate.

### PyTorch中定义一个新操作

forward()
forward()可以有任意多个输入、任意多个输出，但是输入和输出必须是Variable。

backward()
backward()的输入和输出的个数就是forward()函数的输出和输入的个数。其中，backward()输入表示关于forward()输出的梯度，backward()的输出表示关于forward()的输入的梯度。在输入不需要梯度时（通过查看needs_input_grad参数）或者不可导时，可以返回None。