自动求导--Deep Learning框架必备技术二三事

自动求导/梯度/积分好的资料很不好找,学习的过程也颇费功夫,基本学了个大概。
本文不需要太多前置知识,了解TensorFlow的computation graph的那一套最好,不理解也没关系。

前言

传统的Machine Learning框架,如SKlearn等等,广义一点,也可包括XGBoost,libsvm进来,都可以看做“算法的集合”,对新算法,它们编写新的代码,放入repo中。

时间线发展到Deep Learning的时代,人们的需求变化了,每个DL模型,都可能有不同的组成,这样,用户需要框架实现一些基本组件(NN的neuron、loss function、 activation function等等),然后自己来搭积木实现模型。

模型变得灵活了,模型的优化方式基本还是gradient decent based的方法,这就要求框架能够对任意的模型运算能够求梯度/求导,自动求导的需求应运而生。

自动求导常用的方法有三种:

  • Numerical differentiation 数值微分
  • Symbolic differentiation 符号微分
  • Automatic differentiation 自动微分 (让人吐槽无力的大名字)

其中,广泛为DL框架使用的方法为后两种, 符号微分和自动微分。

Numerical differentiation

对于求导,我们第一时间能想到的就是根据导数定义来计算:
$$ f'(x) = \lim_{\Delta x \to 0} \frac{f(x+\Delta x) - f(x)}{\Delta x}$$
数值微分最大的特点就是很直观,好计算,利用了导数定义。

不过这里有一个很大的问题:$\Delta x$的选取怎么选择?
选大了,误差会很大;选小了,不小心就陷进了浮点数的精度极限里,造成舍入误差。

看起来很美好的数值微分,实际应用并不广泛。若一定要用的话,经常使用如下的公式,从两侧逼近:
$$ f'(x) = \lim_{\Delta x \to 0} \frac{f(x+\Delta x) - f(x-\Delta x)}{2\Delta x}$$

Symbolic differentiation

TensorFlow实现了symbolic computing,这里的symbolic和symbolic differentiation是一样的。

与数值相对的,我们希望像我们手动求导一样,我们希望放弃数值相关的运算,而先从表达式出发,将表达式本身看做符号的运算,直接得到求导结果的表达式。

如:
对于 $f(x) = x^2$,我们希望能像自己求导一样得到$f'(x) = 2x$,再带入具体的$x$值进行计算。

比起数值计算,symbolic differentiation最大的好处是精确,其误差为0. 它的缺点也有:

  • 难以计算。比起数值计算,symbolic differentiation要难计算得多。
  • 难以优化,symbolic computing可以非常复杂,然而计算机并不能很好地进行优化这种复杂的运算形式
  • 时间复杂度略高,一方面symbolic differentiation要遍历运算来得到导数的计算公式,然后再从头进行导数的计算

Symbolic differentiation实现

想要实现symbolic differentiation,需要:

  • 统一封装算子和运算
  • 预定义初等函数的导数运算
    • 线性运算
    • 三角函数运算
    • 指数对数
    • ...
  • 预定义导数的四则预算规律:
    • $d(u/v) = (udv - vdu) / v^2 $
    • $d(u*v) = udv + vdu$
    • ...
  • 预定义导数的链式法则:
    • $dy/dx = dy/du * du/dx$

按照导数的符号运算规律一层一层地运算,得到一个导数公式,如果愿意的话,也可以进行一些化简工作。
一个好的例子是Sympy的Symbolic differentiation,Sympy在sympy.core.function.Derivative中实现了Symbolic differentiation.

https://github.com/sympy/sympy/blob/master/sympy/core/function.py

Tensorflow 中的 Symbolic differentiation

Tensorflow实现了通用的符号计算框架,其自动求导也自然而然地使用了Symbolic differentiation的方式。
Tensorflow使用graph的概念来组织数据的流转,一个典型的计算图如图所示:

对于该图g的导数/梯度,TF的做法是从后向前计算,如下图:

  • 从结果C开始,查找C的所有依赖节点I,并计算C的梯度,插入新的计算图中
  • 递归地从I开始,查找I的所有依赖节点I',并计算I的梯度,插入新的计算图中

最终,自顶向下地形成梯度的计算图g'。


在数值计算的时候,梯度会从梯度的计算图g'从前往后进行计算。

这个过程有一些类似deep learning中back propagation的概念。

Automatic differentiation

Automatic differentiation则不对运算进行符号化,比起 Symbolic differentiation返回一个公式(计算图),Automatic differentiation直接返回$f(x)$的导数值$f'(x)$。
狭义地讲,Automatic differentiation可以指使用dual number进行自动导数运算的自动求导方式。

Dual number

我们引入dual number(二元数)的概念。
类比复数的概念:
$$
x = a + bi \quad (i^2 = -1)
$$
我们推广实数,为其引入一个额外的component,
$$
x \mapsto x = x + \dot{x} d \quad (d^2=0)
$$
称之为dual number(二元数)
定义dual number 上如下的运算:
$$
(x + \dot{x}d) + ( y + \dot{y}d) = x + y + (\dot{x} + \dot{y})d
$$
$$
(x + \dot{x}d) ( y + \dot{y}d) = xy + \dot{x}yd + x\dot{y}d + \dot{x}\dot{y}d^2
= xy + (\dot{x}y+ x\dot{y})d
$$
$$
-(x + \dot{x}d) = - x - \dot{x}d
$$
$$
\frac{1}{x + \dot{x}d} = \frac{1}{x} - \frac{\dot{x}}{x^2}d
$$
基于这样的定义,dual number有很多非常不错的性质。

Dual number 与导数

以指数运算为例

以下面的指数运算多项式为例:
$$f(x) = p_0 + p_1x + p_2x^2 + ... + p_nx^n$$
将$x$替换为dual number $x + \dot{x}d$并展开后有:
$$
f(x + \dot{x}d) = p_0 + p1(x + \dot{x}d) + ... + p_n(x + \dot{x}d)^n \\
= p_0 + p_1x + p_2x^2 + ... + p_nx^n + \\
p_1\dot{x}d + 2p_2x\dot{x}d + ... + np_{n-1}x\dot{x}d\\
= f(x) + f'(x)\dot{x}d
$$
由于$\dot{x}$可以随意取,不妨取$\dot{x}$为1,此时,可以见到,dual number的第二部分就是$f(x)$的导数$f'(x)$。

类似地,对于其他运算(三角函数,指数,对数等等),dual number有一样的性质。推广开,有:

对dual number进行运算f的时候,其第二部分即为f的一阶导数f'.

对于多元函数运算,形如:
$$
f(x, y) = xy + x + y \\
f(x + \dot{x}d, y + \dot{y}d) = (x + \dot{x}d)(y + \dot{y}d) + x + \dot{x}d + y + \dot{y}d
$$
求x的偏导数,可以简单地取
$$
\dot{x} = 1, \dot{y} = 0
$$
即可。

Automatic differentiation -- 一个简单的Python实现

实现一个Automatic differentiation,需要以下几点:

  • 实现一个实数的扩展类DualNumber,存储有两个componet的dual number
  • 实现dual number的各种运算
  • 定义各种初等函数的导数运算
此处应有代码,以后再粘贴吧

总结

自动求导的资料甚少,尤其是中文资料非常少。很多资料和工业界的实践都要去读paper以及源码,在symbolic computing大行其道的今天,基本所有的Deep Learning框架都使用了Symbolic differentiation的方式来进行自动求导。虽然这样做的缺点是要backwards一边之后再forward一边,稍微显得时间复杂度稍高,然而DL框架选择把诸如Sigmoid,ReLU,cross entrophy等高级运算封装成了原子运算,也支持对更多更复杂的操作和运算进行封装,让他们的导数在O(1)的时间内可以得到,大大简化了时间。

Reference

[1] Automatic differentiation - Wikipedia
[2] Automatic differentiation (slides)
[3] Introduction to AUTOMATIC DIFFERENTIATION
[4] A comparison of deep learning frameworks
[5] 自动微分法(Automatic differentiation)是如何用C++实现的?
[6] Symbolic computation
[7] SYMBOLIC DIFFERENTIATION
[8] Symbolic Differentiation for Rapid Model Prototyping in Machine Learning and Data Analysis
[9] Sympy : Symbolic Mathematics in Python
[10] Sympy: sympy/sympy/core/function.py
[11] Tensorflow: adding an Op
[12] Tensorflow: RegisterGradient
[13] Tensorflow whitepaper 2015

Comments
Write a Comment