摘要：近日它們交鋒的戰場就是動態計算圖，誰能在這場戰爭中取得優勢，誰就把握住了未來用戶的流向。所以動態框架對虛擬計算圖的構建速度有較高的要求。動態計算圖問題之一的多結構輸入問題的高效計

隨著深度學習的發展，深度學習框架之間競爭也日益激烈，新老框架紛紛各顯神通，想要在廣大DeepLearner的服務器上占據一席之地。近日它們交鋒的戰場就是動態計算圖，誰能在這場戰爭中取得優勢，誰就把握住了未來用戶的流向。作為一名DeepLearner，如果能選中最適合的框架，就能在學習、研究和生產中提高自己的效率，步步領先。但要是上錯了船，文檔、性能、靈活性四處漏水，跳船之后還得游一段時間，這段時間可能都夠別人開到新大陸了。所以說了解框架發展，掌握形式，可謂是每個不甘人后的DeepLearner的必修課。

近期各大框架發展的趨勢主要有兩個，一個是增加對動態圖計算的支持，另一個是在主編程語言上適應廣大用戶的需求。最近比較火熱的動態計算圖相關的框架主要有DyNet、PyTorch和TensorFlow Fold，就是圍繞著這其中一個點或兩個點進行的。

目前在這場競爭中，TensorFlow Fold以其先進的Dynamic Batching算法走在了其他框架的前面。為了方便大家了解TensorFlow Fold的特性，本文將會為大家厘清有關動態圖計算的一些概念，對比介紹DyNet、PyTorch和TensorFlow等框架的特性，重點講解TensorFlow Fold的核心算法和接口。

本文分為五個部分：

一、當我們說動態計算圖的時候，我們指的是什么？

二、框架競爭的焦點：編程語言與動態計算圖

三、以靜制動：巧妙的Dynamic Batching算法

四、TensorFlow Fold：封裝在靜態框架上的動態接口

五、總結

當我們說動態計算圖的時候，我們指的是什么？

首先，我們要搞清楚深度學習框架所謂的“動態”和“靜態”究竟是按照什么標準劃分的。為了大家的直觀理解，我這里要引入一個系列比喻，房地產商（框架使用者）通過電子郵件（編程語言代碼）請建筑公司（深度學習框架）幫忙建造房子（計算圖） 。

在靜態框架使用的是靜態聲明 （static declaration）策略，計算圖的聲明和執行是分開的，換成比喻的說法就是：建筑設計師畫建筑設計圖（聲明）和施工隊建造房子（執行）是分開進行的。畫設計圖的時候施工隊的建筑工人、材料和機器都還沒動，這也就是我們說的靜態。這個整個聲明和執行的過程中涉及到兩個圖，這里我們分別給它們一個名字，聲明階段構建的圖叫虛擬計算圖，在這個過程中框架需要將用戶的代碼轉化為可以一份詳細的計算圖，這份計算圖一般會包含計算執行順序和內存空間分配的策略，這些策略的制定一般是這個過程最消耗時間的部分；執行階段構建的圖叫實體計算圖，這個過程包括為參數和中間結果實際分配內存空間，并按照當前需求進行計算等，數據就在這張實體計算圖中計算和傳遞。不過這里要注意一點的是，虛擬計算圖中的部件并不需要在每一次執行中都轉化為實體計算圖。像建筑設計圖上畫了三層別墅的規劃，但建筑隊可以在按客戶的要求只建下面的兩層。另外一張設計圖可以用多少次也沒有規定死，所以說靜態只是相對于下面的動態框架而言，并不是說靜態框架就只能按部就班。常見的靜態框架有TensorFlow、MXNet、Theano等。

而動態框架則不同，使用的是動態聲明（dynamic declaration）策略，聲明和執行一起進行的。比喻一下就是設計師和施工隊是一起工作的，設計師看郵件的第一句如“要有一個二十平方米的臥室”，馬上畫出這個臥室的設計圖交給施工隊建造，然后再去看第二句。這樣虛擬計算圖和實體計算圖的構建就是同步進行的了。因為可以實時的計劃，動態框架可以根據實時需求構建對應的計算圖，在靈活性上，動態框架會更勝一籌。Torch、DyNet、Chainer等就是動態框架。

靈活很好，但也不是沒有代價的。不然的話現在流行的框架中，就不會是靜態框架占比更高了。靜態框架將聲明和執行分開有什么好處呢？較大的好處就是在執行前就知道了所有的需要進行操作，所以可以對圖中各節點計算順序和內存分配進行合理的規劃，這樣就可以就較快的執行所需的計算。就像房地產商郵件里說，“建一個棟大樓，樓頂建個花園，大樓旁邊建一個游泳館”，但這個順序并不是最優的，設計師畫完圖之后，發現大樓的選址旁邊要預留游泳館的空間，游泳館和大樓可以同時開工，并不用等到大樓的樓頂花園建完，就在圖上把這些信息標注了出來，施工隊就可以更高效地施工。這樣一來，靜態框架的執行效率相對來說就更高一些。這一點是動態框架的劣勢，因為它每次規劃、分配內存、執行的時候，都只能看到局部的需求，所以并不能做出全局最優的規劃和內存分配。

另外的好處是對于建筑公司的管理層（框架開發者），因為一張設計圖可以被反復施工，所以設計師畫圖的快慢影響就小地多了，對于一個要建幾年的工程設計師畫圖的時間是三天還是五天影響不大，靜態建筑公司不用花費太多資源去培訓設計師的畫圖速度（縮短構建虛擬計算圖的時間，主要是規劃計算順序和分配內存空間的時間）。而動態建筑公司就不同了，因為每建一套房子或一排房子就要重新畫一遍設計圖，對于一個幾周的子項目來說，花三天畫圖還是五天就影響比較大了。所以動態框架對虛擬計算圖的構建速度有較高的要求。當然因為動態框架每步構建和計算只是虛擬計算圖的一個局部，需要策略不會太復雜，所以制定策略也快得多。

在過去的大部分的深度學習項目中，不管使用的是靜態框架還是動態框架，我們實際上都只用到了構建靜態實際計算圖的能力。為什么這樣說呢？因為在一般在將數據投入模型進行訓練或預測之前，往往會有一個預處理的步奏。在預處理的時候，我們會將圖片縮放裁剪，將句子拼接截斷，使他們變為同樣的形狀大小，然后將集成一個個批次（min-batch），等待批次訓練或預測。這些不同的輸入到模型中其實運行的是同一個計算圖。換成房地產的說法，就是說用戶的需求雖然略有區別，但經過房地產商的努力，他們都同意要同一款房子。不管是房地產商選的是靜態建筑公司還是動態建筑公司，建造的房子都是統一的小區樣式。

這樣作的好處是可以充分利用GPU和多核CPU的并行計算能力。這種能力可以怎么理解呢？建筑施工隊里面有很多的砌墻工人，100個人取砌一堵1米的墻并不會比10個人快上10倍（能實際工作的可能還是只有10個人），而讓他們同時砌十堵1米的墻，可能所花的時間可能和砌一堵墻幾乎一樣快。如果有很多可以通過這樣并行來加速的工作，那整個工程所需要的時間也就可以大大縮短。GPU能夠幾十倍上百倍地提高計算速度是現代深度學習發展的一個關鍵，畢竟現在的深度模型很大程度上還是很依賴調參，需要快速地迭代。能否利用這種加速能力常常就是一次訓練幾個小時還是幾周的區別，也是決定一個項目能不能做的關鍵。

然而，并不是所有項目的數據都可以預處理成相同的形狀和尺寸。例如自然語言處理中的語法解析樹，源代碼中的抽象語法樹，以及網頁中的DOM樹等，形狀的不同本身就是非常重要的特征，不可剝離。這些數據就像充滿個性的藝術家，每個人對房子該是什么樣的都有自己的想法，買房的主要目的就是想彰顯個性，你想讓他們買一樣的房子，對不起，做不到。?

這樣一來，對于每一個樣例，我們都需要一個新的計算圖，這種問題我們需要使用構建動態計算圖的能力才能夠解決。這種問題我們可以叫它多結構輸入問題，因為這個問題中計算圖的動態需求是輸入帶來的。不同框架這個問題的求解能力可以分為三個程度：第一層，無法計算，對于所有樣本都要求同樣的結構，在TensorFlow Fold出來之前所有正常使用的靜態框架處于這個層次。第二層，能計算但不夠高效，不同批次的樣本之間可以有不同的結構，但同一個批次樣本都是同一個結構，因為無法利用GPU和多核CPU的并行計算能力，不能高效計算，目前所有的動態框架屬于這個層次。第三層，能高效計算，能夠在同一個批次里包含不同結構的樣本，這個層次的多結構輸入問題有些論壇上也叫Dynamic Batching問題， TensorFlow Fold的核心算法Dynamic Batching算法剛好同名，TensorFlow Fold和以后實現Dynamic Batching算法的框架處于這個層次。

多結構輸入問題早已存在，可用的模型諸如遞歸神經網絡（Recursive Neural Networks）也提出許久，但因為沒有辦法高效實現，研究和使用者寥寥無幾。因此，當我們說各大框架的動態計算圖的時候，我們關心的不僅僅是他們誰更容易做到，更重要的是能不能高效地做到。動態計算圖問題之一的多結構輸入問題的高效計算問題一旦解決，就會大大促進樹狀網絡甚至更復雜模型和數據集的發展。

但多結構輸入問題并不是的動態圖計算問題，這里給大家舉另外一個例子，即計算圖的結構要依賴于自身的計算結果的情況，類比就是后面房子怎么建要看前面建得怎么樣，這種問題更加復雜，所有的動態框架都可以輕松解決，而靜態框架目前是做不到，不過目前還沒發現有具體問題需要這樣操作，我們這里不作仔細討論。

框架競爭的焦點：編程語言與動態計算圖

在動態計算圖爭鋒下面，還隱含著另外一重較量，編程語言的支持。上文我們將代碼比作電子郵件，那編程語言就是像英語、中文這樣的語言。當前深度學習界更受歡迎的語言莫過于Python了，此外C++也因為其本身的高效在工業界頗得青睞。現在大多主流框架都支持這兩種語言，他們是就像機器學習界的中英文。不過Torch是一個例外，它使用的是比較小眾的Lua，這實際上是它較大一塊短板，因為使用Lua做一些數據處理并不方便，使用者經常要使用Python之類的語言進行數據清洗等操作，然后在轉化為Lua可以讀取的形式。這一點使得無數使用者在不同語言的切換中紛紛投向TensorFlow、MXNet的懷抱。即使去年年中Facebook推出TorchNet這個Torch升級版也沒有挽回太多的人氣，因為TorchNet用的也是Lua。

在DyNet出現前，Python和C++上還沒有一個比較高效的動態計算框架（如Chainer效率并不高）。這個由多所大學和公司的二十多位研究者共同發布新框架，一下子就找準了自己的定位，即在深度學習框架中語言較好（Python/C++）且動態計算最強。他們通過對動態聲明的圖構建流程的優化，大大提高了構建虛擬計算圖的速度，也就是說他們的建筑設計師畫圖和規劃做得飛起。該框架在LSTM和BiLSTM等部分測試中超過了Chainer、Theano和TensorFlow，并且在當時Theano和TensorFlow難以實現的樹狀模型TreeLSTM的測試中也遠遠打敗了Chainer，所以DyNet一出來吸引住了不少使用者。

然而好景不長，Torch不愧是有Facebook支持的公司，很快就推出了據說內部使用已久的PyTorch，將Torch移植到了Python，補足了自己最后一塊短板。這下子就厲害了，不僅挽留住了人氣，借助Python的力量甚至有機會從TensorFlow這位老大手里奪下一塊蛋糕。

但是不管是DyNet還是PyTorch，沒有解決多結構輸入問題的高效計算。它們雖然對不同的批次（mini-batch）可以給出不同的計算圖。但同一個批次內部的樣本的形狀還是要求一致，并沒有一個成熟的解決方案來應對這種情況。就是說他們每建一棟樓或一批樓的可以重新設計，但同時開工的同一批樓的樣式一定是一樣的。

面對新老對手的挑戰，TensorFlow作為深度學習框架界的霸主也不能無動于衷，終于給出了自己關于動態計算圖高效計算的答案——TensorFlow Fold，也就是我們今天要講的主角。這主角出場瞬時就hold住了場面，在Reddit上就有人立馬評論“... pip uninstall pytorch!”。從上一部分我們知道，TensorFlow其實是一個靜態框架，天生在解決動態計算圖問題上處于劣勢。你說它一個靜態的框架，怎么就解決了動態計算圖的問題呢？（其實只是解決了多結構輸入的問題）這中間究竟有什么奧秘，讓筆者為大家娓娓道來。

以靜制動：巧妙的Dynamic Batching算法

TensorFlow Fold解決問題的核心技術叫Dynamic Batching，這個技術能夠構建一個能夠模擬任意形狀和大小的動態計算圖的靜態圖，原本不同樣本的動態計算圖都會被重寫成能夠被這個計算圖高效計算的形式。這樣就巧妙地解決了動態計算圖的高效計算問題。打比喻就是，建筑公司請了一位計算機科學家寫了一個自動化辦公軟件，每當房地產商提出一個個性社區問題的時候，這個軟件就會把一張通用的設計圖告訴設計師去設計；然后對于每一批樓的需求這個軟件都會生成對應的施工指南，只要按照這個指南的指示，施工就可以通過多次建造通用設計圖中的一部分來完成這批樓的建造；在施工指南中軟件已經合并每次建造時重復的工作，這樣施工隊可以并行施工，高效地完成工程。

更妙的是，這個技術并不僅在TensorFlow上能夠使用，對于其他深度學習框架完全能夠適用。可以預見的是，如果短期內沒有更好的解決方案，這個技術很可能會被其他框架的開發者移植到他們自己的框架上，變成MXNet Fold，PyTorch Fold等。

那為什么用靜態計算圖模擬動態計算圖是可能的？因為雖然動態計算圖的形狀和大小千變萬化，但對于一個模型來說它們的基本組件卻可以簡單劃分為兩種：Tensor（張量）和Operation（操作）。

Tensor，可以看做各種各樣的數據塊，主要包括輸入的樣本和計算結果，Tensor的類型可以按照shape（形狀）和data type（數據類型）劃分，具有相同shape和data type的Tensor可以被劃分為一類，就像相同大小和材質的磚頭；這里的shape并不包括batch size，它就像磚頭的個數，一疊不管是十塊還是五塊，只要磚頭的大小材質一樣，我們認為是同一個類。

Operation，并不是是指加減乘除這樣最底層的操作，而是指一塊小的計算子圖，一塊計算子圖接受某種確定類型的Tensor作為輸入，并輸出某種確定類型的Tensor。這塊計算子圖在動態構建圖的過程中并不會被拆開，而是作為一個整體被適用，比如RNN的Cell或其他用戶自己定義的一些固定的操作組合。

對于某一個模型如樹狀RNN來說，但它只會有限種Operation和Tensor類型，當我們將這些Operation和Tensor類型放到一起，我們就有了一個通用子圖，這時候只需要一些控制部件控制這個每次子圖執行的部分（上文有提到每次執行的實體計算圖可以只是虛擬計算圖的一部分）以及組合方式，我們就可以模擬對應模型所有可能的計算圖。達成這種控制只需TensorFlow的三個部件：tf.gather、tf.concat和tf.while_loop。

說完通用子圖的組成，我們再說說Dynamic Batching怎么將不同結構的計算圖重寫成可以用通用子圖計算的形式。Dynamic Batching是一個貪婪（greedy）的算法，它接受一個有向無環計算圖作為輸入:

給圖中的每一個節點（操作）標注一個深度，所有沒有任何依賴的節點標注為深度0，依賴的節點深度較大為d的節點的深度標注為d+1；

在圖中插入pass-through（直通）的操作，使得第d+1層只依賴于第d層；

將同一深度涉及相同操作的節點合并到一起，方便并行計算；

將同一深度的計算結果按Tensor類型（包括Tensor的形狀和數值類型）有序拼接在一起；

將輸入原始計算圖中的每條邊標記上（深度，數據類型，序號），對應它們可以獲取上一層計算結果的位置。

對于一批不同結構的計算圖，我們可以把它們看做不連通的大圖同樣處理。上面算法的第三步會將這批圖中同一深度的相同操作進行合并，方便并行計算。說完圖的構建，我們再說說怎么執行：算法在每次迭代中執行一個深度的計算，使用tf.while_loop從深度0一直執行到較大深度。在每一個深度中，tf.gather根據上面第五步的標記為各個Operation獲取當前深度各條輸入邊的Tensor，如果某個Operation沒有獲取到任何Tensor，說明當前深度這個Operation不需要執行計算。Operation執行完后tf.concat將相同Tensor類型的計算結果拼接在一起，提供給下一個深度的計算。?

上面這一幅圖來著官方論文，左邊是Dynamic Batching為二叉TreeRNN構建的通用計算圖。右邊是一顆簡單的語法解析樹。通用計算圖中有兩種Tensor，代表單詞的編碼整數、詞向量/hidden向量的128維向量。Operation也只有兩個一個詞向量查表操作（embed lookup）和一個RNN的Cell。圖中gather和concat之間的直連表示直通（pass-through）操作。右邊的語法解析樹可以分為三層計算被執行：第一層，將1、3、5通過詞向量查表操作，輸出3個128維的詞向量；第二層，1和3對應的詞向量通過RNN Cell輸出一個128維的隱含層向量，5對應的詞向量直通輸出；第三層，上一層計算的隱含層向量和5對應的詞向量通過RNN Cell，輸出一個128維的隱含層向量。計算完畢。

那這個算法的效果怎么樣呢？它在TreeLSTM的實驗中，8核英特爾CPU的可以加速20多倍，而英偉達GTX-1080上可以加速100倍左右。這個加速比是采用Dynamic Batching算法批處理中平均每個樣本執行的平均時間和單個樣本不作批處理的執行時間之比。這里不包含構建虛擬圖所需要的時間。

TensorFlow Fold：封裝在靜態框架上的動態接口

上面的Dynamic Batching的算法很繁瑣，但不用當心，這個過程是由框架自動完成的，作為框架的使用者，我們只要知道怎么調用官方給出來的接口就可以了。新推出的TensorFlow Fold就是一個TensorFlow的封裝，設計參考了函數式編程的一些思想，目的就是方便用戶快速地構建動態計算圖。下面我們來簡單地瀏覽一下，要進一步了解可以去看官方的教學文檔。

TensorFlow Fold提供了一些函數專門用來處理序列(, ... )：

：計算將函數f應用到每一個序列的元素，比如將句子中的每一個詞轉化為詞向量；

：計算，比如說展開一個RNN（循環神經網絡）；

：計算，將函數g應用到一顆平衡二叉樹上，比如對序列中的元素作max或sum-pooling。

由于TensorFlow原本的基本單元Tensor不適合用于構建動態圖，所以Fold引入新的基本組件Block。Block有明確的一個輸入類型和一個輸出類型，包括：

：來著編程語言如Python中元素，比如字典等；

：擁有數據類型和形狀的TensorFlow基本模塊；

：括號中的每一個t表示對應位置的類型；

：一個不定長的擁有類型為t的元素的序列；

：單元類型。這些基本類型可以相互嵌套，比如一個Block的輸入類型可以是Input類型的Tuple。?

用來創建Block的基本函數有：

：將Python標量轉化為Tensor；

：將Numpy數組轉化為Tensor；

：創建一個Operation；

：用于預處理Python類型。

用來組合Block的基本函數有：

，流水線（pipeline）：將的輸出作為的輸入；

： 接受一個Python字典為輸入，對字典中key值為的value應用；

：根據輸入條件應用中的一個；

：OneOf的特例，如果輸入不為None，應用b；

：輸入應用中的每一個。

用來組合Block的高級函數有：

：流水線的升級版，流水線只能處理串行的流程，Composition()創建一個Scope對象，在這個Scope的縮進范圍內，采用來讀取多個數據流，可以用于構建多分支結構；

：用來創建遞歸結構，這個函數可以先定義一個預先占位的表達式expr，等這個表達式定義完再用expr.resolve_to(expr_def)，將表達式遞歸地代入，這是用來創建樹結構計算圖必不可少的工具。

總結

在動態圖計算領域TensorFlow Fold目前領先一步，卻也不是高枕無憂，只要MXNet， PyTorch等競爭對手抓緊把Dynamic Batching算法實現出來，或進一步想出更好的解決方案，就能很快趕上。而且TensorFlow Fold目前只支持TensorFlow 1.0版本，但只有盡快支持所有版本，才能讓更多的用戶使用上。另外工具的發展也會帶動學科的進步，隨著動態計算圖的實現難度的下降和計算效率的提高，研究者們會越來越多地進入這個領域，可以預期的是接下來一段時間肯定會有更多復雜結構的模型和數據集涌現出來。未來將會如何，諸君盡請期待。

商業智能與數據分析群

興趣范圍包括各種讓數據產生價值的辦法，實際應用案例分享與討論，分析工具，ETL工具，數據倉庫，數據挖掘工具，報表系統等全方位知識

QQ群：81035754