背景#
怎么算微分。。通常有三种方法：
- Symbolic Differentiation
- Numerical Differentiation
- Automatic Differentiation (auto diff)
auto diff 中两种主流的方式分别是 forward-mode 和 reverse-mode。 由于 forward-mode 的方法中，计算的时间复杂度是 O(n)，n 是输入的参数个数；而 reverse-mode 中，计算的时间复杂度是 O(m)，m 是输出节点的个数。在 DNN 中，n 往往很大，远大于 m，因此这里主要介绍 reverse-mode auto diff 方法。
backprop 和 reverse mode auto diff 的区别#
看了 reverse mode auto diff 的过程，感觉和 backprop 是一回事呀。 实际上，backprop 指的是训练神经网络时根据 loss 的 gradient 来更新 weight 的过程，而 auto diff 是 backprop 使用的一种用来计算 gradient 的 technique。
Backpropagation refers to the whole process of training an artificial neural network using multiple backpropagation steps, each of which computes gradients and uses them to perform a Gradient Descent step. In contrast, reverse-mode auto diff is simply a technique used to compute gradients efficiently and it happens to be used by backpropagation.
chain rule#
chain rule..也就是微积分里的链式法则，更准确地说，是多变量的 chain rule。 简单来说，就是同一条路径相乘，不同路径相加。
可以参考 MULTI-VARIABLE CHAIN RULE
实现#
放一个 CSE 599W Systems for ML 课程的 assignment 1，比较简单，只有 add、mul、matmul 这几个算子（因为重点并不在于支持算子的种类）。 需要实现几个算子的 forward 和梯度的计算，这部分比较好写。 然后需要实现 executor 的 run 函数，做个拓扑排序然后计算即可。
1def run(self, feed_dict):
2 """Computes values of nodes in eval_node_list given computation graph.
3 Parameters
4 ----------
5 feed_dict: list of variable nodes whose values are supplied by user.
6
7 Returns
8 -------
9 A list of values for nodes in eval_node_list.
10 """
11 node_to_val_map = dict(feed_dict)
12 print("self.eval_node_list={}".format(self.eval_node_list))
13 # Traverse graph in topological sort order and compute values for all nodes.
14 topo_order = find_topo_sort(self.eval_node_list)
15 # 按照拓扑排序的顺序来计算，保证计算当前节点的值时，其依赖的值都计算出来了。
16 """TODO: Your code here"""
17 for node in topo_order:
18 if isinstance(node.op, PlaceholderOp):
19 continue
20 # 在实际计算的时候，要用具体的值来替代node
21 input_vals = [node_to_val_map[x] for x in node.inputs]
22 res = node.op.compute(node, input_vals)
23 node_to_val_map[node] = res
24
25 # Collect node values.
26 # 因为是按照topo order计算的，最后再变为和输入相同的顺序去输出
27 node_val_results = [node_to_val_map[node] for node in self.eval_node_list]
28 return node_val_results然后是计算梯度这部分。 需要注意 node_to_output_grads_list 是一个 dict，key 是 node，val 其实是一个 list，表示 node 对哪些后续节点的 gradient 有作用。 然后 input_grads 表示的是 node 的 input 节点相对 node 的 gradient。
听起来有些让人费解。。看个具体的例子。
对于下面这个计算图，相关变量的值如下：
详细代码
1def test_multi_var_chain_rule():
2 x1 = ad.Variable(name="x1")
3 x2 = x1+3
4 x3 = x1+5
5 y = x2*x3
6
7 grad_x1, grad_x2, grad_x3 = ad.gradients(y, [x1, x2, x3])
8
9 executor = ad.Executor([y, grad_x1, grad_x2, grad_x3])
10 x1_val = 1 * np.ones(3)
11 y_val, grad_x1_val, grad_x2_val, grad_x3_val = executor.run(feed_dict = {x1 : x1_val})
12
13
14
15nosetests -s -v autodiff_test.py 130 ↵
16autodiff_test.custom_test ... output_node=(x1+((x2*x3)*x1))
17node.name=(x1+((x2*x3)*x1))
18node_to_output_grads_list[node]=[Oneslike((x1+((x2*x3)*x1)))]
19grad=Oneslike((x1+((x2*x3)*x1)))
20input_grads=[Oneslike((x1+((x2*x3)*x1))), Oneslike((x1+((x2*x3)*x1)))]
21
22node.name=((x2*x3)*x1)
23node_to_output_grads_list[node]=[Oneslike((x1+((x2*x3)*x1)))]
24grad=Oneslike((x1+((x2*x3)*x1)))
25input_grads=[(Oneslike((x1+((x2*x3)*x1)))*x1), (Oneslike((x1+((x2*x3)*x1)))*(x2*x3))]
26
27node.name=(x2*x3)
28node_to_output_grads_list[node]=[(Oneslike((x1+((x2*x3)*x1)))*x1)]
29grad=(Oneslike((x1+((x2*x3)*x1)))*x1)
30input_grads=[((Oneslike((x1+((x2*x3)*x1)))*x1)*x3), ((Oneslike((x1+((x2*x3)*x1)))*x1)*x2)]
31
32node.name=x3
33node_to_output_grads_list[node]=[((Oneslike((x1+((x2*x3)*x1)))*x1)*x2)]
34grad=((Oneslike((x1+((x2*x3)*x1)))*x1)*x2)
35input_grads=None
36
37node.name=x2
38node_to_output_grads_list[node]=[((Oneslike((x1+((x2*x3)*x1)))*x1)*x3)]
39grad=((Oneslike((x1+((x2*x3)*x1)))*x1)*x3)
40input_grads=None
41
42node.name=x1
43node_to_output_grads_list[node]=[Oneslike((x1+((x2*x3)*x1))), (Oneslike((x1+((x2*x3)*x1)))*(x2*x3))]
44grad=(Oneslike((x1+((x2*x3)*x1)))+(Oneslike((x1+((x2*x3)*x1)))*(x2*x3)))
45input_grads=None
46
47length of node_to_output_grads_list = {(x1+((x2*x3)*x1)): [Oneslike((x1+((x2*x3)*x1)))], x1: [Oneslike((x1+((x2*x3)*x1))), (Oneslike((x1+((x2*x3)*x1)))*(x2*x3))], ((x2*x3)*x1): [Oneslike((x1+((x2*x3)*x1)))], (x2*x3): [(Oneslike((x1+((x2*x3)*x1)))*x1)], x2: [((Oneslike((x1+((x2*x3)*x1)))*x1)*x3)], x3: [((Oneslike((x1+((x2*x3)*x1)))*x1)*x2)]}
48self.eval_node_list=[(x1+((x2*x3)*x1)), (Oneslike((x1+((x2*x3)*x1)))+(Oneslike((x1+((x2*x3)*x1)))*(x2*x3))), ((Oneslike((x1+((x2*x3)*x1)))*x1)*x3), ((Oneslike((x1+((x2*x3)*x1)))*x1)*x2)]
49
50
51
52
53for node in reverse_topo_order:
54 # print("node.name={} op={}".format(node.name, type(node.op)))
55 grad = sum_node_list(node_to_output_grads_list[node])
56 # print("grad={}".format(grad))
57 input_grads = node.op.gradient(node, grad)
58 # input_grads表示的node的input节点相对node的gradient
59 # print("input_grads={}".format(input_grads))
60 node_to_output_grad[node] = grad
61 for idx, inp in enumerate(node.inputs):
62 node_to_output_grads_list[inp] = node_to_output_grads_list.get(inp, [])
63 node_to_output_grads_list[inp].append(input_grads[idx])