【讀論文】Neural Turing Machine vs Differentiable Neural Computer

04-27

從 "新智元" 上讀到「深度學習中的 Memory 和 Attention 的前沿進展」的演講 PPT，覺得什麼都好，只是標題太低調，低調得走了樣。嚴格講，Memory 和 Attention，不僅僅是前沿進展，而是突破性進展。

突破性體現在哪裡呢？Google Brain 的 Chris Olah 在「Attention and Augmented Recurrent Neural Networks" 一文中，把「突破性」詮釋為「把神經網路的直覺，與其它東西相結合」。問題是，如何與外圍東西相結合呢？簡單的 API 調用嗎？

Google DeepMind 團隊寫的「Neural Turing Machines」一文。這題目，霸氣！這篇論文的意義，並非局限於把 LSTM 的記憶細胞，延伸到外設存儲。而是勾畫了以深度學習神經網路為 CPU 的操作系統的架構。換而言之，深度學習不再自閉，而是通過像操作系統那樣的機制，與外圍設備緊密協作，在這個新型的操作系統中，深度學習神經網路，發揮著 CPU 的作用。

沿著這個思路，Google 團隊又寫了「Pointer Networks」和「Neural Random-access Machines」等論文。做個不嚴謹的類比，如果深度學習神經網路是 CPU 的話，這些論文談的問題，是如何管理內存和硬碟。

這些新技術有什麼用處呢？先前深度學習與知識圖譜，是人工智慧界兩大技術體系，但是彼此很少有交集。藉助於這些新技術，深度學習與知識圖譜終於合體了。深知合體有什麼用處呢？現身說法，拋磚引玉。

我們從 1.6 億份三甲醫院的病歷中，通過深度學習的辦法，把每一份病歷都轉化為一組向量。基於這 1.6 億組病歷向量，我們通過數據挖掘的辦法，構建了由 1.5 萬個點和 180 萬條邊組成的醫療知識圖譜。基於這個醫療知識圖譜，我們初步實現了人工智慧醫生（Clinical Decision Support System, CDSS）。

主要的技術障礙，全部清除了。接下去的工作，是發現並清掃各種錯誤。針對常見的 300 種病，我們為每種病準備了 100-200 條測試用例，測試用例總數約 5 萬條。在做測試的時候，我們經常需要花費很多時間，對每個錯誤追溯根源，究竟是因為我們的診斷演算法參數有錯誤，還是因為我們整理的醫療知識圖譜失衡了，還是因為來自醫院的病曆數據有噪音？

藉助於深知合體，是否可以做一個半自動的 debugging 工具。這個工具可以自動聚焦到可能是故障點的診斷模型的參數、知識圖譜的局部、以及病曆數據，從而節省大量 debugging 的時間。

【讀論文】深度學習挑戰馮.諾依曼

2016年10月27日「Nature」期刊第538卷，發表了Google 旗下的 DeepMind 團隊寫的人工智慧的論文，題目是「Hybrid computing using a neural network with dynamic external memory」 [1]，用配置了動態外部存儲的神經網路，實現雜交計算。這篇論文介紹了 Differentiable Neural Computer 的實現細節。

DeepMind 團隊在倫敦工作，2014年被Google 收購。DeepMind 開發的 AlphaGo，2016年年初戰勝了圍棋高手李世乭。

早在 2014年12月，DeepMind 團隊發表了一篇論文，「Neural Turing Machines」 [2]。後來，他們對 Neural Turing Machines （NTM）的存儲管理方式做了改進，命名為 Differentiable Neural Computer（DNC）。Differentiable 是可訓練的意思，尤其是可以用 gradient descent 的演算法來訓練。

當今世界，所有計算機的體系，都源自於馮.諾依曼於 1945 年設計的體系，馮.諾依曼體系有三大要素，

1. 基本操作，例如加減乘除。

2. 邏輯流程式控制制，例如 if-else-then，for，while。

3. 外設存儲器，內存和硬碟的定址。

想挑戰馮.諾依曼，就必須從這三個要素入手。DeepMind 團隊認為，馮.諾依曼體系中的邏輯流程式控制制和外設存儲器使用，都必須在程序中寫死，而不能通過觀察範例，自動生成程序。

如果把程序理解為把輸入 x 轉換為輸出 y 的函數 f()，y = f(x)，那麼 neural network 就是模擬任何函數的通用模型 f^()。

但是早期的 neural network 有兩個軟肋，

1. 不能實現 variable binding，也就是說，f() 的內部參數，不能隨著輸入 x 的不同而改變。

2. 不能實現 variable-length structure，也就是說，輸入 x 和輸出 y 的維度都是定長的，不能改變。

早期 neural network 的這兩個軟肋，都不難修補。譬如循環神經網路 Recurrent Neural Network（RNN），就解決了這兩個問題。換而言之，RNN 是 Turing-complete 的，可以用來模擬任何函數，當然也可以模擬任何程序的功能。

既然馮.諾依曼體系的三大要素中的兩個，基本操作和邏輯流程式控制制，都能夠被 RNN 模擬，假如 RNN 也能夠解決存儲管理的問題，那麼整個馮.諾依曼體系，就都能夠被 RNN 來實現了。所以 Differentiable Neural Computer （DNC）的工作重點，在於存儲管理。

[3] 深入淺出地解釋了用 RNN 來管理存儲的原理。建議先讀 [3]，再讀 [2]，最後讀 [1]。需要特別注意的，個人體會有幾個方面，1. 存儲的設置，2. 定址機制，3. 需要訓練哪些參數，4. 如何把 DNC 應用到 Graph 操作中。

#1. 存儲的設置：

[3] 把 NTM/DNC 的存儲設置解釋為 the memory is an array of vectors，也就是一個矩陣，每一行就是一個 vector，每行的 vector 的長度一致，所有行集結起來就是 array。在文中的例子中，[3] 把 memory 簡化為 an array of scalar, 也就是 N 行單列的矩陣，每一行只存儲一個數值。

什麼時候需要存儲向量呢？如果存儲里存放的是圖像，那麼每個存儲單元上存儲的是一個像素（r,g,b），像素就是一個向量，三個 bytes 組成的向量。

但是如果需要存儲的是一篇文章，每個存儲單元上需要存儲一個詞，而每個詞的長度不同，怎麼辦？三篇文章都沒有說，但是簡單的辦法有二。

1. 每個存儲單元上，預留足夠長的 vector，遇到很短的詞，空著的 byte 就全部填 0。

2. 把每個詞，無論長短，都轉換為詞向量，詞向量的長度定長。第二個辦法就是其它論文中說的 encoding 的辦法。

另外要注意的是，存儲矩陣的行數可能很多。想像一下，把一部長篇小說存放到存儲矩陣里，每個詞都佔用一行，需要佔用存儲矩陣的多少行。

#2. 定址機制：

DNC 改進了 NTM 的定址機制。NTM 的定址機制是 content-based 和 location-based 的混搭。為什麼需要改進呢？原因有三。

1. NTM 不能保障多個存儲單元之間，不相互重疊，不相互干擾。dynamic memory allocation: allocate a free space

2. NTM 不能釋放存儲單元，如果處理很長的序列時，譬如處理一部超長的長篇小說，搞不好所有存儲都會被佔滿，導致系統崩潰。dynamic memory allocation: free gates

3. 如果連續做幾個讀寫操作，它們所使用的存儲單元的位置，最好是相鄰的。但是在 NTM 中，一旦某個讀寫操作，遠遠跳到其它存儲區域，那麼後續操作也跟著去其它區域，而且失憶，想不起來原先的存儲區域在哪裡。temporal link matrix

DNC 的定址機制，把讀操作和寫操作分開。DNC 用 content-based 和 dynamic memory allocation 的混搭方式，處理寫操作。用 content-based 和 temporal memory linkage 的混搭方式，處理讀操作。

1. content-based 定址：

比較需要處理的目標 vector，與存儲矩陣中每一行的 vector，用餘弦距離來計算兩者相似性。取存儲矩陣中，與目標 vector 距離最短的行。

計算餘弦距離時，需要一個係數向量，beta，這個係數向量是被訓練出來的。

2. dynamic memory allocation 存儲單元分配：

每一個存儲單元，都是等長的 vector。當每一個存儲單元被 free 的時候，整個 vector 中的每一個 element，都可以用來寫入新數據。但是當一個 vector 中有若干 elements 已經被佔用時，剩下的 elements 還可以被寫入新數據。

想像一下，如果每個 vector 的長度是 100，又如果某個 vector 里，已經寫入了一個不長的詞，但是還有剩餘的 elements，這些剩餘的 elements 可以用於給這個詞做詞性標註等等。但是如果剩餘的 elements 不多，那麼詞性標註只好被寫到其它行的 vector 里。

DNC 設計了一個存儲單元佔用向量 u。u(i) = 0 時第 i 行的 vector 中，所有 element 都可以被寫入新數據，而當 u(i) = 1 時第 i 行的 vector 中所有 elements 都已經被佔用了。

但是如果存儲矩陣中有兩行，i 和 j，分別有完全相同的 elements 可以被寫。誰先被寫，取決於權重向量 wt。wt 體現了存儲使用的策略，策略既可以是儘可能寫入最新釋放的存儲單元，也可以儘可能寫入內容相似，而且沒有被完全佔用的存儲單元。這個權重向量 wt，是可以根據被訓練出來的。

3. Temporal memory linkage 讀寫時序的關聯：

Dynamic memory allocation 沒有記錄歷次寫操作時，loc(t) 發生在哪個存儲單元，以及 loc(t+1) 發生在哪個存儲單元。而記錄歷次寫操作的存儲單元的位置順序，是有用的。

DNC 用 N^2 的方陣，來記錄 temporal link，其中 L(i, j) 記錄著 t 時寫操作發生在存儲單元 j，而 t+1 時寫操作發生在存儲單元 i 的概率。L(i, j) 可以是簡單的統計結果，也可以是加權的統計結果，權重體現了控制策略。權重是可以被訓練出來的。

當 N 很大的時，理論上來說 L 方陣會佔用很多空間。但是鑒於 L 方陣很稀疏，很多 L(i, j) 等於 0。根據 DeepMind 團隊的估算，L 實際佔用空間只有 O( N )，計算成本只有 O( N * Log N )

# 3. 需要訓練哪些參數?

除了讀寫操作、以及定址操作中的幾個權重向量以外，還有作為 controller 的 RNN 的參數。RNN 可以選擇結構比較簡單的 neural network，也可以選擇結構更複雜的 LSTM。選用 LSTM 意味著有更多參數，需要被訓練。

訓練數據通常不包含讀寫操作發生在哪個存儲空間上的信息。譬如 NTM 中，Priority Sort 實驗的訓練數據，是一連串（輸入，理想輸出）pairs。每個 pair 中的輸入，是 20 個向量，每個向量伴隨著 priority 打分。每個 pair 中的理想輸出，是從輸入的 20 個向量中，挑選出來的 16 個，並且按 priority 得分排序。

注意，訓練數據中不包含讀寫操作在哪些存儲單元上進行的信息。

# 4. 把 DNC 應用到 Graph 操作中。

文中把 DNC 用於在倫敦地鐵中，尋找兩站之間最佳路線。坐地鐵本身不重要，重要的是如果 RNN 學會使用 Graph 以後，能做什麼？假如 Graph 不是地鐵，而是 social graph 呢？又假如是 knowledge graph 呢？

參考文獻：

[1] 「Hybrid computing using a neural network with dynamic external memory」

http://www.nature.com/articles/nature20101.epdf?author_access_token=ImTXBI8aWbYxYQ51Plys8NRgN0jAjWel9jnR3ZoTv0MggmpDmwljGswxVdeocYSurJ3hxupzWuRNeGvvXnoO8o4jTJcnAyhGuZzXJ1GEaD-Z7E6X_a9R-xqJ9TfJWBqz

[2]「Neural Turing Machines」

https://arxiv.org/abs/1410.5401

[3] Attention and Augmented Recurrent Neural Networks

http://distill.pub/2016/augmented-rnns/