Udacity深度学习课程-MiniFlow理解

Posted by vaultli on October 8, 2017

目前,深度学习领域里有许多深度学习辅助工具,例如TensorFlow、Caffe、MXNet、PyTorch等等,这些深度学习框架均有着广泛的应用,同时又各有优缺点。其中,TensorFlow是由Google公司发明的深度学习框架,可用于灵活搭建多种神经网络架构,并支持CPU、GPU运算,是一款非常好的深度学习辅助工具。TensorFlow安装简单,社区强大,缺点是运行效率稍逊于Caffe等工具,但是这并不影响TensorFlow的优秀。要想用好TensorFlow就要理解其中的运行原理,因此学习MiniFlow可以帮助我们理解TensorFlow的运行机制。

1. 拓扑排序(Topological sorting)

为了可以更好地理解MiniFlow,首先要学习一下拓扑排序的相关知识。

拓扑排序(Topological sorting):将有向图中的顶点以线性方式进行排序,即对于任何连接自顶点v的有向边uv,在最后的排序结果中,顶点u总是在顶点v的前面。

一个有向图能被拓扑排序的充要条件是它是一个有向无环图(Directed Acyclic Graph,DAG)。

实现拓扑排序的算法主要有Kahn算法和基于深度优先遍历(Depth-First Search,DFS)的拓扑排序。下面主要讲解一下Kanh算法。

Kanh算法主要思想是先找入度为0的节点,排序后移除这些点及输出的边,再找此时入度为0的节点重复前面的操作,以此类推,得到拓扑排序的结果。Kanh算法的伪代码如下:

L <- Empty list that will contain the sorted elements
S <- Set of all nodes with no incoming edges
while S is non-empty do
    remove a node n from S
    insert n into L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (graph has at least one cycle)
else
    return L (a topologically sorted order)

以图1的DAG为例,利用Kanh算法进行拓扑排序后的结果如图2所示。

图1

图1

图2

图2

2. MiniFlow

有了拓扑排序的基础,MiniFlow的原理便更容易被理解。利用MiniFlow创建神经网络需要两个步骤:

  • 定义节点和边图表。
  • 通过该图表传播值。

以图3的神经网络为例,简要说明MiniFlow的原理。

图3

图3

将图3的神经网络转化为图4所示的拓扑结构。图4中的箭头表示信号的流动,每个节点拥有自己的含义,在Python中用相应的类定义。$X$、$W_1$、$b_1$、$W_2$、$b_2$、$y$ 是Input()节点;$l_1$、$l_2$ 是Linear()节点,可实现线性组合运算;$S$ 是Sigmoid()节点,可实现sigmoid激活;$C$ 是MSE()节点,可实现cost的计算。每种节点都有主要属性self.inbound_nodes、self.outbound_nodes、self.value、self.gradients,主要方法self.forward()、self.backward()。

图4

图4

图4经过拓扑排序后可以得到图5的结果,图5中的箭头仅表示节点的一种先后顺序,并不表示信号的流动。

图5

图5

在程序实现时,利用节点类定义图3,利用字典存储图4,利用列表存储图5。实现拓扑排序的函数先把图存储为字典,然后利用Kanh算法实现拓扑排序,得到用列表表征的排序结果。

下面展示的照片为Python实现的程序源码,而且写有注释,帮助理解。miniflow.py的程序源码如下:

miniflow.py

miniflow.py

miniflow.py

miniflow.py

miniflow.py

miniflow.py

miniflow.py

miniflow.py

nn.py程序为主程序,调用了miniflow.py模块,其程序源码如下:

nn.py

nn.py

3. 小结

TensorFlow的基本原理和MiniFlow是一致的,也是由定义节点和边图表以及通过该图表传播值两大主要部分组成。TensorFlow里定义的是张量Tensor,通过会话Session传播值。关于TensorFlow的具体用法和示例,之后还会继续撰写博客解析。

参考链接

拓扑排序的原理及其实现:http://blog.csdn.net/dm_vincent/article/details/7714519