《AOGNets：Deep AND-OR Grammar Networks for Visual Recognition》論文筆記與Pytorch實現

01-31

個人感覺，這篇論文涉及的內容很多，但是重點就是提出了AOGNet模型，並基於該模型進行了一些討論。讀過論文，我認為論文的主要出發點是將Grammer Model（語法模型）和 Deep Learning Model（深度學習模型）組合到一起，創造了一種Deep Grammer Model。這樣設計的模型可以同時兼顧特徵的探索和利用（exploration & exploitation）。基於論文中涉及的規則，使得模型的設計有了更多的理論基礎。

1、Grammer Model（語法模型）

Grammer Model這個概念於我來說是一個比較新的概念。語法模型首先需要設計 n 條規則，然後根據該規則構建一個圖（graph，這裡強烈建議忘記圖的定義和遍歷方式的同學，複習一下數據結構的對應部分），該graph就是一種特徵表達範式（或者理解為一種特徵模型）。由於是與深度學習結合，所以這裡並沒有指定特徵表達的含義，只給出了文章中使用的 3 種規則,三種規則的表達式如下：

$S_{i,j} rightarrow t_{i,j}$ （1）

$S_{i,j}(m) rightarrow L_{i,i+m} cdot R_{i+m+1,j}, 0 le m < k$ （2）

$S_{i,j} rightarrow S_{i,j}(0) | S_{i,j}(1) | cdotcdotcdot |S_{i,j}(j-i)$ （3）

上面給出的三個表達式，真的其實真的只能算是一種數學表達式，對於解釋模型有所用，但是對於理解模型的細節與實現，個人認為沒啥作用。由於採用語法模型作為解釋，就會有句子（sentence）和單詞（words）的概念。在這裡可以將所有的channel理解為一個sentence。假設某層有1024個channel作為一個sentence，句子中有4個word，那麼1024個channel平分成4份每256channel就組成一個work。有了句子和單詞的概念之後，我們再引入sub-sentence（分句）的概念，也就是有連續的幾個word組成的句子就是sub-sentence。sub-sentence也可以由另外兩個sub-sentence組成。在上述的三個表達式中，S、L、R都表示sub-sentence，下標分別分句由第i個word到第j個word，括弧中的字母m表示，組成該sub-sentence的另外兩個sub-sentence的斷點。

如果上面關於sentence、sub-sentence、word的解釋不是很清楚，可以從圖（graph）的角度出發，sentence對應graph的頂端節點，sub-sentence對應graph的中間節點，word對應graph的葉子節點。對word、sub-sentence和sentence有個基本概念之後，分別對上述的三個規則進行更加詳細的介紹：

①termination rule（終端規則）：

所謂termination rule就是基礎的規則，其實就是輸入特徵 f 到輸出特徵 F 的一種變換，可以是線性變換，也可以是非線性的。在最終的結構圖中用Terminal-node表示。因此對應公式（1）， $S_{i,j}$ 直接由從i 到 j的word通過變換 $tau$ 得到。至於 $tau$ 的具體表達式在後面介紹deep learning model的時候給出。

②and rule（and語法規則）

and rule作者稱之為binary decomposition（or composition）rule，我覺得直接就稱為 and規則就好了，因為該規則通過and節點實現。根據公式（2）可知，該節點表示對組成sub-sentence的左右兩個sub-sentence執行 and 操作。具體實現過程中，就是將sub-sentence L 和 R 的特徵並聯（concatenation）然後經過變換 $tau$ 得到。這裡的 $tau$ 可以和termination rule中的 $tau$ 設計相同也可以不同。

③or rule（or 語法規則）

or rule也是我給起的名字，原因同樣是因為該規則通過or節點實現。基於or規則，需要將所有之前與i-j單詞相關的sub-sentence執行or操作。具體的實現過程就是將與單詞i-j相關的sub-sentence的特徵依次相加然後經過變換 $tau$ 得到。這裡面有一處我認為論文中表述的不是特別合適，就是直接由i-j單詞經過 $tau$ 得到的特徵，也參與了or操作。所以，我將三個規則的公式改寫成下面的形式（非常小的變化，就是將第一個公式中的S變為T，並在第三個公式中加入了T）：

$T_{i,j}rightarrow t_{i,j}$

$S_{i,j}(m)rightarrow L_{i,i+m} cdot R_{i+m+1,j}, 0 leq m < k$

$S_{i,j} rightarrow S_{i,j}(0) | S_{i,j}(1) | cdotcdotcdot | S_{i,j}(j-i) | T_{i,j}$

④圖的構造：

基於上述三個規則構造圖（graph），作者提出了breadth-first search（BFS）演算法來實現。對於這個演算法論文中給出了如上表所示的演算法說明。廣度優先搜索演算法相信大家都不陌生，這裡利用下面的圖為例進行一個簡單的說明，大家一定就能完全理解了。圖中，作者假設每個sentence有4個word組成。從頂端節點出發，我們需要從舊句子（input feature）得到新句子（output feature）。新句子 $S_{0,3}$ 由 $S_{0,3}(0),S_{0,3}(1),S_{0,3}(2),T_{0,3}$ 四個分句經過Or節點得到。其中 $T_{0,3}$ 直接由input feature層經過輸入 $tau$ 變換即可得到，而 $S_{0,3}(0),S_{0,3}(1),S_{0,3}(2)$ 則分別由不同的And節點得到。比如說 $S_{0,3}(0)$ 由 $T_{0,0}$ 和 $S_{1,3}$ 的輸出經過And節點得到。因為 $T_{0,0}$ 只包含一個word,所以不再需要Or節點, $S_{1,3}$ 則表示新的Or節點,按照上述方式繼續進行擴展。需要注意的是在圖的構造過程中，有的節點可能之前已經構造過，此時要注意節點的連接而不是構造一個新的節點。比如圖中第五行的幾個節點都會出現這種情況。

此外，雖然構造方式採用BFS演算法，但是在圖的執行過程中採用的是DFS演算法。這樣做的好處是，構造的時候遵循三條規則可以快速有效構造graph不至於遺失節點，執行的時候可以保證每個節點所需的數據都已獲得不需要等待。

2、Deep Learning Model（深度學習模型）

前面說過，這篇論文的主要出發點是將 Grammer Model 和 Deep Learning Model 進行整合。整合的方式就是將 $tau$ 變換用Deep Learning的多層表示，同時將上述一個graph稱之為一個AOG Building Block。一個或數個AOG Building Block組成一個Stage，數個Stage 就組成了AOGNet。由於處理的是圖像數據，數據經過一個AOG Building Block，數據就會從 $Ctimes H times W$ 變化為 $C times H times W$ , 一般每個stage間會進行H、W的降維和channel的增加。一個Building Block則不一定。是否進行降維和增加channel由卷積層的c和stride決定。

文章中作者給出了兩種 $tau$ 的構造方式，較為複雜的一種稱之為BN Block（BottleNeck Block）如上圖所示。從圖中也可以看出，參考了Residual Network的構造方式，連名稱都是一樣的。棕色表示卷積層，藍色表示BatchNorm層，綠色表示ReLU層，Block由兩個分支組成，上面的分支較短可以更有效地傳遞梯度，下層的分支較長可以更有效的探索特徵。圖中的 $alpha$ 稱為bottleneck ratio，是一個控制channel的超參，文章採用的是0.25. 此外，文章中還提到了另外一種構造方案我稱之為Normal Block，由一層Conv+BN+ReLU構成，非常簡潔。這裡我們首先給出兩種 $tau$ 構造方式的實現代碼:

import torch.nn as nnnnclass T_Normal_Block(nn.Module):n n def __init__(self, in_channels, out_channels, stride=1):n super(T_Normal_Block, self).__init__()n self.conv = nn.Conv2d(in_channels, out_channels, 3,n stride=stride, padding=1, bias=True)n self.bn = nn.BatchNorm2d(out_channels)n self.relu = nn.ReLU(inplace=True)n self.dp = nn.Dropout(p=0.1, inplace=True)n n def forward(self, x):n x = self.conv(x)n x = self.bn(x)n x = self.relu(x)n x = self.dp(x)n return xnnclass T_BottleNeck_Block(nn.Module):n n def __init__(self, in_channels, out_channels, alpha=0.25, stride=1):n super(T_BottleNeck_Block, self).__init__()n n self.left = nn.Sequential(n nn.Conv2d(in_channels, out_channels, 1,n stride=stride, padding=0, bias=True),n nn.BatchNorm2d(out_channels))n n self.right = nn.Sequential(n nn.Conv2d(in_channels, alpha*out_channels, 1,n stride=1, padding=0, bias=True),n nn.BatchNorm2d(out_channels),n nn.ReLU(inplace=True),n n nn.Conv2d(alpha*out_channels, alpha*out_channels, 3,n stride=stride, padding=1, bias=True),n nn.BatchNorm2d(out_channels),n nn.ReLU(inplace=True),n n nn.Conv2d(alpha*out_channels, out_channels, 1,n stride=1, padding=0, bias=True),n nn.BatchNorm2d(out_channels))n n self.relu = nn.ReLU(inplace=True)n n def forward(self, x):n left = self.left(x)n right = self.right(x)n o = left+rightn o = self.relu(o)n return on

從代碼中可以看出兩種 $tau$ 的實現都非常的簡潔易於理解。我們給出AOG Building Block的代碼。代碼分為三個部分：construct 部分、re-construct 部分和 forward 部分。其中， construct 部分即遵循 BFS 演算法構建graph，re-construct部分則遵循 DFS 演算法對graph的存放狀態進行重構，按執行順序保存節點，並正式創建其中的網路結構， forward部分只是依照規則前向執行網路，得到結果。詳細內容參加代碼及注釋：

class AOG_Building_Block(nn.Module):n # AOG_Building_Blockn # params： in_channels是輸入特徵圖的通道數，out_channels輸出特徵圖的通道數n # sub_nums就是上述所說的word個數n # sub_in_channels和sub_out_channels分別表示與一個單詞相關的輸入通道數和輸出通道數n # Ttype指定了T採用何種類型構造方式nn def __init__(self, in_channels, out_channels, n stride=1, Ttype=T_Normal_Block, sub_nums=4):n super(AOG_Building_Block, self).__init__()n self.in_channels = in_channelsn self.out_channels = out_channelsn self.sub_nums = sub_numsn self.sub_in_channels = int(self.in_channels / self.sub_nums)n self.sub_out_channels = int(self.out_channels / self.sub_nums)n n # 調用construct函數（BFS演算法）將構造圖graphn self.structure = self.construct()n # 調用reconstruct函數（DFS演算法）重構圖graphn self.structure = self.reconstruct()n # 根據重構的圖graph構造網路結構，用ModuleList存儲網路結構，依次執行n self.nodes = nn.ModuleList()n for node in self.structure:n in_channels = node[in_channels]n out_channels = node[out_channels]n if node[type] == t:n self.nodes.append(Ttype(in_channels, out_channels, stride=stride))n else:n self.nodes.append(Ttype(in_channels, out_channels, stride=1))n n # BFS演算法，用[]記錄整張圖中各個節點，n # 每個節點用一個{}記錄內容，其中各種節點包含的key如下：n # or_node: type, start（文章中i）, end（文章中j）, children(多個index number的list)n # and_node: type, left_start, left_end, n # right_start, right_end, children（只有連個index number的list）n # t_node: type, start, endn # 每種節點還包括:in_channels(節點的輸入特徵通道數)n # out_channels（節點的輸出特徵通道數）n # history_key(節點的唯一標識，用於防止節點被重複構建)n def construct(self):n history_key = or_0_{}.format(self.sub_nums-1)n structure = [{type:or, start:0, end:self.sub_nums-1,n in_channels:self.out_channels,n out_channels:self.out_channels,n history_key:history_key}]n history = {history_key:0}n n sum_nodes = 1n idx = 0n # 利用循環進行構建，當圖中所有的節點都遍歷過時，說明graph已經構建完成。n # or、and、t節點分別進行處理n while(idx < sum_nodes):n now_node = structure[idx]n if now_node[type] == or:n nnum = now_node[end] - now_node[start] + 1n history_key = t_{}_{}.format(now_node[start], now_node[end])n if history_key in history:n now_node[children] = [history[history_key]]n else:n structure.append({type:t, n start:now_node[start], n end:now_node[end],n in_channels:nnum*self.sub_in_channels,n out_channels:nnum*self.sub_out_channels,n history_key:history_key})n history[history_key] = sum_nodesn now_node[children] = [sum_nodes]n sum_nodes += 1n for m in range(now_node[start], now_node[end]):n mid = m n history_key = and_{}_{}_{}.format(now_node[start], mid, n now_node[end])n if history_key in history:n now_node[children].append(history[history_key])n else:n structure.append({type:and, n left_start:now_node[start],n left_end:mid,n right_start:mid+1, n right_end:now_node[end],n in_channels:nnum*self.sub_out_channels,n out_channels:nnum*self.sub_out_channels,n history_key:history_key})n history[history_key] = sum_nodes n now_node[children].append(sum_nodes)n sum_nodes += 1n elif now_node[type] == and:n left_history_key, left_child = n self.get_andnode_child(now_node[left_start],n now_node[left_end])n right_history_key, right_child = n self.get_andnode_child(now_node[right_start], n now_node[right_end])n if left_history_key in history:n now_node[children] = [history[left_history_key]]n else:n structure.append(left_child)n now_node[children] = [sum_nodes]n history[left_history_key] = sum_nodesn sum_nodes += 1n n if right_history_key in history:n now_node[children].append(history[right_history_key])n else:n structure.append(right_child)n now_node[children].append(sum_nodes)n history[right_history_key] = sum_nodesn sum_nodes += 1 n elif now_node[type] == t:n passn idx += 1n return structuren n # 根據start和end得到and節點不同的子節點n # 如果start == end 將不需要Or節點（sub-sentence），否則需要Or節點並需要繼續搜索n def get_andnode_child(self, start, end):n nnum = end-start+1n if start == end:n key = t_{}.format(start)n temp = {type:t,n start:start,end:end,n in_channels:nnum*self.sub_in_channels,n out_channels:nnum*self.sub_out_channels,n history_key:keyn }n else:n key = or_{}_{}.format(start, end)n temp = {type:or,n start:start,end:end,n in_channels:nnum*self.sub_out_channels,n out_channels:nnum*self.sub_out_channels,n history_key:key}n return key, temp nn # DFSn # 利用深度優先搜索對graph進行重構，節點的key沒有發生變化n # 由於一個Block的網路深度一般不會太深，且只在訓練或測試之前構造一次n # 因此直接用遞歸方式實現n def reconstruct(self):n structure = []n history = {}n old_structure = self.structuren n # 定義遞歸函數n def dfs(node):n if node[type] == t:n history_key = node[history_key]n if history_key in history:n idx = history[history_key]n else:n idx = len(structure)n history[history_key] = idxn structure.append(node)n else:n history_key = node[history_key]n if history_key not in history:n temp = []n for idy in node[children]:n idx = dfs(old_structure[idy])n temp.append(idx)n node[children] = tempn idx = len(structure)n history[history_key] = idxn structure.append(node)n else:n idx = history[history_key] n return idxn dfs(old_structure[0])n return structuren n # 前向函數，pytorch中必須實現的函數n def forward(self, x):n # 首先將input features拆分成不同的word xsn xs = x.split(self.sub_in_channels, dim=1)n # datas 用於記錄每個節點的輸出結果n datas = []n for c_node, m_node in zip(self.structure, self.nodes):n if c_node[type] == and:n left_id = c_node[children][0]n right_id = c_node[children][1]n # and 節點，將左右子節點的輸出數據concatn tmp = torch.cat((datas[left_id], datas[right_id]), dim=1)n tmp = m_node(tmp)n datas.append(tmp)n elif c_node[type] == or:n tmp = Nonen # or 節點，將所有子節點的輸出數據相加求和n for idx in c_node[children]:n if tmp is None:n tmp = datas[idx]n else:n tmp = tmp + datas[idx]n tmp = m_node(tmp)n datas.append(tmp)n else:n # t 節點，直接將輸入xs中對應的部分執行n if c_node[start] == c_node[end]:n tmp = m_node(xs[c_node[start]])n datas.append(tmp)n else:n tmp = torch.cat(xs[c_node[start]:c_node[end]+1], dim=1)n tmp = m_node(tmp)n datas.append(tmp)n #最終返回List中最後一個節點的結果，作為整個graph的輸出結果n return datas[-1]n

個人認為上述代碼中對於AOG Building Block的構造和執行已經非常詳盡了，不需要更多的文字說明。下面給出一段基於cifar-10的AOGNet網路結構定義代碼（網路結構圖參照題圖），相信更加有助於理解：

from AOGNet import AOG_Building_Blocknfrom AOGNet import T_Normal_Blocknfrom AOGNet import T_BottleNeck_Blocknnnclass AOGNET(nn.Module):n n def __init__(self, classes_num， Ttype=T_Normal_Block，sub_nums=4):n super(AOGNET, self).__init__()n self.classes_num = classes_numn # 題圖中的Convolutional部分，對應輸入圖片大小為32*32，隨機Crop到28*28，n # 第一層Convolutional不做降維處理，也可以有其他設置n self.conv = nn.Conv2d(in_channels=3, out_channels=16, n kernel_size=3, stride=1, padding=1)n # aog1對應Stage1,同樣不進行降維n self.aog1 = AOG_Building_Block(in_channels=16, out_channels=16, n stride=1, Ttype=Ttype, sub_nums=sub_nums) n # aog2-aog3對應Stage2， H、W降維一半，channel增加一倍n self.aog2 = AOG_Building_Block(in_channels=16, out_channels=32, n stride=2, Ttype=Ttype, sub_nums=sub_nums)n self.aog3 = AOG_Building_Block(in_channels=32, out_channels=32, n stride=1, Ttype=Ttype, sub_nums=sub_nums)n # aog3-aog4對應Stage3，H、W降維一半n self.aog4 = AOG_Building_Block(in_channels=32, out_channels=64, n stride=2, Ttype=Ttype, sub_nums=sub_nums)n # 最終池化及分類n self.pool = nn.AvgPool2d(kernel_size=7)n self.cls = nn.Linear(64, self.classes_num)n n def forward(self, x):n x = self.conv(x)n x = self.aog1(x)n x = self.aog2(x)n x = self.aog3(x)n x = self.aog4(x)n x = self.pool(x)n x = x.view(x.size(0), -1)n x = self.cls(x)n return xn

下表給出了作者在Cifar數據集上的實驗結果，從表中可以看出AOGNets的表現與DenseNet不相上下，基本可以證明AOGNet的在圖像處理問題中的能力。此外文章還將網路用於目標檢測任務，結果也十分優秀，有興趣的請到論文中查看。

下面給出我復現實驗的結果圖，在該圖中的最終結果與上述結果存在一定的差距。這種差距我認為主要是因為圖像預處理以及實驗室網路結構的設計差異，以及其他超參的選擇造成的。畢竟有時候調參對結果的影響也是比較明顯的。

3、總結

這篇論文將Grammer Model 和 Deep Learning Model結合，充分發揮兩者的特性，可以說想法十分的巧妙。利用Grammer Model的理論來構造網路模型，也給了Deep Learning Model一種比較合理的解釋。但是，從最終網路呈現的形式來看，我認為網路對實驗結果的提升主要來源於不同層次之間或者同一層次之間特徵的組合，這一點在Residual Network、DenseNet 等目前非常優秀的網路結構中都有涉及。特徵組合的層次性複雜性差異，也是AOGNet優於ResNet但是和DenseNet持平的原因吧。對於文章中提及的And-Or語法，我認為在當前設計下真的只是一個概念。當然，作者在文章中也說了這篇文章更多的是一次探索，對於And-Or規則後面可能發展出更多的定義方式，或者設計出新的規則，取得了優秀的效果我們不得而知，但是值得期待。畢竟，Deep Learning Model缺少充分的理論證明，被戲稱為「煉丹術」不是一天兩天了，能有一種非常合理的理論解釋也是非常不錯的。（以上觀點純屬個人意見，歡迎大家探討指正，但請輕噴！）

參考文獻：

Xilai Li, Tianfu Wu, Xi Song, Hamid Krim，AOGNets: Deep AND-OR Grammar Networks for Visual Recognition. arXiv.1711.05847

歡迎大家批評指正！

轉載請註明出處！