本節(jié)是自動求導框架技術的第三節(jié)，本系列其余文章包括
1. 控制流簡介
????前面兩節(jié)我們已經(jīng)知道了如何實現(xiàn)普通計算圖，然后基于計算圖的拓撲排序和逆向拓撲排序完成前向傳播與反向求導。但是僅有這些是不夠的，在 tensorflow 中還引入了一種叫做控制流的機制來提高框架的靈活性。引入控制流之后，框架的使用者可以向計算圖中引入分支選擇以及循環(huán)，進而構造出更加復雜的神經(jīng)網(wǎng)絡結構。
2. 控制流的實現(xiàn)難點
? ? 引入控制流將會使得計算圖的構建以及前向傳播帶來很大的不同。首先，計算圖將變得動態(tài)。分支選擇以及循環(huán)控制流只有在真實運行的時候依據(jù)其依賴的數(shù)據(jù)的輸入來判斷走哪個分支、是否結束循環(huán)。就好比建筑師得到了一張動態(tài)的圖紙，在建高樓之前完全不知道大樓會蓋到多少層，長什么樣子；只有真正建到某些層之后考慮了一下現(xiàn)在建筑的狀況，然后決定接下來的部分怎么建造。
控制流引入的另一個難點在于循環(huán)控制流的實現(xiàn)。引入循環(huán)之后，原本的計算圖在邏輯上出現(xiàn)了環(huán)，從而無法進行拓撲排序。所以對于有控制流的計算圖，前向計算和反向傳播的實現(xiàn)要么拋棄拓撲排序這一思路，要么就要通過某些方式將循環(huán)進行拆解。
3. 控制流的實現(xiàn)思路
3.1 虛擬圖的結構
? ? 為了解決計算圖動態(tài)的問題，我引入了“虛擬圖”這一概念?？蚣艿氖褂谜卟⒉恢苯訕嬙煊嬎銏D，而是構造一個包含了控制流的虛擬圖，然后框架對虛擬圖進行前向傳播的同時動態(tài)生成一個計算圖，之后基于生成的計算圖進行反向傳播。虛擬圖的引入解決了動態(tài)計算圖難以進行反向傳播的問題。
????虛擬圖的組成包含三種節(jié)點：分支結點 branch_node，循環(huán)節(jié)點 loop_node，普通節(jié)點 virtual_node。branch_node 可以決定向其子節(jié)點提供哪個計算節(jié)點的依賴（包括空依賴）從而實現(xiàn)分支控制，接下來主要談一下 loop_node 的問題。對于虛擬圖我依然希望其是有向無環(huán)圖，所以我需要將邏輯上的循環(huán)和有向無環(huán)圖這兩個矛盾進行調和，實現(xiàn)方法的思路來自于圖的強連通分量。參考算法導論中文版第22章的引理22.13。
對于一個圖而言，每個強連通分量可以看做是一個廣義的節(jié)點，這些廣義節(jié)點構成的圖是一個有向無環(huán)圖。
? ? 所以解決虛擬圖包含循環(huán)的方式就是把 loop_node 看做一個廣義節(jié)點，其中包含了一個“子虛擬圖”，這個子虛擬圖在 loop_node 的中的 inner_loop () 函數(shù)的控制下可以循環(huán)遍歷多次，直到滿足 loop_node 的循環(huán)跳出條件。由于 loop_node 中包含的子虛擬圖也是一個虛擬圖，所以整個虛擬圖是一個遞歸層層嵌套的結構，可以實現(xiàn)大部分的循環(huán)級聯(lián)、循環(huán)嵌套。但是虛擬圖在其各個層面上依然是有向無環(huán)圖，所以可以進行拓撲排序。
3.2 虛擬圖如何生成計算圖
????虛擬圖中的 build_compute_graph (cg, idx) 函數(shù)用于構造計算圖，cg是待生成計算圖的引用，表示 compute_graph；idx 是循環(huán)的下標。
????在虛擬圖中，每個節(jié)點用一個二元組唯一標識：<type, id>，其中 type 標識這個虛擬節(jié)點的類別，根據(jù)type 虛擬節(jié)點能夠知曉自己應該生成什么樣的計算節(jié)點；id 是用于區(qū)分同一個類別的不同虛擬節(jié)點。由于虛擬圖中存在循環(huán)，一個虛擬節(jié)點可能在某個循環(huán)中生成多個計算節(jié)點，所以計算節(jié)點使用一個三元組唯一標識：<type, id, idx>，idx 就是上面提到的循環(huán)下標。
? ? 虛擬圖中的 build_compute_graph (cg, idx) 流程介紹如下：
1. 對虛擬圖拓撲排序；
2. 對于拓撲排序后的每個節(jié)點：
? ? if (是loop_node) : 執(zhí)行 這個 loop_node 的 inner_loop (cg) 函數(shù)
????if (是普通virtual_node)：首先查找當前待生成的計算節(jié)點的依賴節(jié)點是否齊全（由于分支結點的原因當前虛擬節(jié)點的路徑可能并不會被經(jīng)過），如果依賴節(jié)點齊全，則根據(jù)虛擬節(jié)點的 type 值生成相應的計算節(jié)點，加入計算圖 cg，并調用計算節(jié)點中的 op () 方法完成這個計算節(jié)點輸出的計算。
3. 返回該計算圖的末尾節(jié)點。
對于loop_node 的 inner_loop (cg) 函數(shù)，其主要流程如下：
1. 調用 loop_node 中用戶自定義的 init (cg) 函數(shù)完成循環(huán)的初始化；
2. while (用戶自定義condition (cg) 函數(shù)返回0) {
? ? 循環(huán)下標 idx 自增
? ? 遍歷 loop_node 中的子虛擬圖，即調用子虛擬圖的?build_compute_graph (cg, idx) 函數(shù)
}
3. 記錄下循環(huán)的結果——最后生成的計算節(jié)點
通過對虛擬圖前向傳播的同時構建出計算圖，這個計算圖是一個有向無環(huán)圖。然后反向傳播的就可以依據(jù)該計算圖執(zhí)行。
