【讀論文】Neural Episodic Control

一周前，2017年3月6日，Google 旗下的 DeepMind 公司，發表了一篇題為《神經情景控制 Neural Episodic Control》的論文。

DeepMind 公司很出名，不僅因為 AlphaGo 是它的產品，而且因為 DeepMind 的員工發表了很多深度學習的論文，數量多，水平高。

《神經情景控制》很搶眼，因為作者中不僅有深度學習的大腕 Oriol Vinyals，而且還有 DeepMind 公司創始人 Demis Hassabis。

這篇論文的主題，是如何大幅度提高深度強化學習的計算效率。

提高計算效率是很重要的課題。譬如迎戰李世乭時，AlphaGo 動用了 1920 顆 CPU、280 顆 GPU。如果能夠大規模提高計算效率，那麼就不需要動用如此暴力的硬體。

如何大規模提高計算效率？《神經情景控制》的思路並不新鮮，以佔用龐大的硬碟空間為代價，來節省 CPU 運算時間。

#1. 以圍棋為例，先定義兩個概念。

1. 棋面 (State)：

圍棋棋盤上，總共有 19 x 19 = 361 個落子位置。譬如目前已經下了 100 手，那麼棋面上黑子和白子各有 50 粒，這些黑子和白子分別佔據的位置，就是一種棋面。

2017-3-14：如何讓 AlphaGo 更快更輕盈？

據專家估計，棋面的數量，大約是 250 的 150 次方，250^150。

2. 贏面 (Action Value)：

贏面是指當前棋局下，黑子（或白子）佔據的優勢。

開局或者中盤的贏面（優勢）不太容易計算，因為只有到了終局以後，才能知道輸贏幾目。

但是終局前一步的贏面很容易計算，因為對手多半會把棋子落在最佳位置上。所謂最佳位置，就是贏的目數最大，或者輸的目數最少的位置。

不過，也許對手一時糊塗，會出臭棋。所以，終局前一步的贏面，應該是終局時的輸贏目數，乘以一個不確定係數。

終局前兩步的贏面也很容易計算，因為自己也一定會把棋子落在最佳位置上，逼迫對方輸的目數最多，或者贏的目數最小。

不過，也不能保證自己永遠保持清醒。是人都會犯糊塗。所以，終局前兩步的贏面，應該是終局時的輸贏目數，先乘以對方的不確定係數，再乘以自己的不確定係數。為了方便計算，假設對方和自己，犯糊塗的概率都一樣，那麼終局前兩步的贏面，等於終局時的輸贏目數，乘以不確定係數的平方。

依次循環，從終局一路回溯到中盤，再一路回溯到開局，就可以估算所有棋面下的贏面了。

#2. 快速查找棋面的索引。

理解了贏面的計算方法以後，就容易理解《神經情景控制》論文中提出的新方法了。

1. 棋面-贏面查詢表：

用一路回溯的辦法，可以計算每一種棋面的贏面。但是一路回溯的計算量很大，不如預先設置 361 個表，每個表對應一個落子位置。

每個表有若干行，每行有兩列，第一列是棋面，第二列是贏面。

預先訓練 AlphaGo 時，對於 361 種落子的位置，分別計算在各個棋面下，對應的贏面。

訓練結束後，就可以找人對弈了。

面對某一個特定棋面時，AlphaGo 該落子在哪一個位置呢？只需要在 361 個表中，分別找到對應的棋面所在的行，取出相應的贏面的值。

這樣總共獲得 361 個落子位置的 361 個贏面的值。取其中贏面最大的那一個落子位置即可。

2. 快速索引：

每一個表有多少行呢？從開局到終局，差不多有 250^150 種棋面，所以每個表差不多有 250^150 行。

如果一行一行地查找當前的棋面，計算量仍然非常大。

提高查找速度，辦法有兩個。

一個是建索引。通過索引，找到相似的棋面，然後再仔細查找確切的棋面。

另一個是近似。沒必要嚴格查找每一種棋面下的確切贏面，不妨把相似棋面的贏面，取個均值。

《神經情景控制》這篇論文，用的是近似的辦法。

不妨把棋面看成一張圖片，用卷積神經網路（CNN）提取層層抽象棋面特徵。CNN 的輸出，是棋面特徵的編碼。

棋面特徵的編碼是一個數字向量，數字本身沒有明確意義，但是相似棋局的數字向量很鄰近。

在這篇論文的實驗中，特徵編碼的數量是 5 * 10^5，遠遠小於 250^150。換而言之，250^150 種棋面，被 CNN 聚類成 5 * 10^5 種相似棋面。

3. 學習：

棋面與圖片不同。輕微改變圖片中的像素，圖片的模樣不會發生太大變化。但是輕微改變棋面中的黑白子的分布，贏面卻大不相同。

所以，CNN 必須非常敏銳地識別棋面中的細微特徵。

如何讓 CNN 變得更敏銳？

在訓練過程中，用一路回溯的辦法，精算每個棋面的贏面。然後對比精算出來的贏面，與查詢表中的近似贏面，兩者之間的誤差。

誤差是錯誤的近似導致的，錯誤的近似是錯誤的 CNN 參數導致的。

逐步調整 CNN 參數，減少精算與近似之間的誤差，從而讓CNN 學會更敏銳地識別棋面中的細微特徵。

# 3. 參考文獻：

[1] Neural Episodic Control

https://arxiv.org/abs/1703.01988