什麼是《失控》中說的「稀疏分散式網路」？

12-01

卡內爾瓦的演算法是一種將有限數量的數據點儲存進非常巨大的潛在的內存空間的絕妙方法。
換句話說，卡內爾瓦指出了一種能夠將思維所擁有的任何感知存入有限記憶機制的方法。
由於宇宙中可能存在的思想要比原子或粒子更多，人類思維所能接觸到的只是其中非常稀疏的一部分，
因此，卡內爾瓦稱他的演算法為「稀疏分布記憶」演算法。
http://book.ifeng.com/lianzai/detail_2010_11/30/3280672_14.shtml

懷疑翻譯之後術語差別，搜索結果沒有明顯解釋。

《失控》中的描述是：

Pentti Kanerva在1974年提出了Sparse Distributed Memory(SDM)
此演算法簡單明了，熟手一下午就能實現
在80年代中期，Kanerva使用微調後的SDM進行20x20像素的阿拉伯數字識別

之前看《失控》的時候對這東西很好奇，最近找了些資料研究了一下。個人感覺是，KK誇大了SDM的神奇之處。這是一個很有意思的模型，但遠未達到「破解人類記憶奧秘」的程度。

我對SDM的理解如下：
計算機常規的存儲方式是：一個地址(key)存一個值(value)，根據精確地址取精確的值。所以，1. 有多少數據就需要多少空間、2. 不知道精確地址(key)就什麼也拿不到。
而SDM能達到以下效果：1. 開固定大小的空間，不管來多少數據，不需要額外的空間、2. 對於任何地址(key)都能取到值，當然，也不保證取到的值一定靠譜。

SDM的核心思路解決了以下兩個問題：
1. 怎麼在一個地址保存多個值？
答：把他們加起來
2. 怎麼從不精確的地址取到值？
答：存時候多存幾個地方，取時候多取幾個地方

以下是我構造的一個簡單的例子，比論文中的又簡化了一些。

先解釋第一個問題：
怎麼在一個地址保存「－－＋」和「－＋＋」兩條數據？（假定每個值都是3bit，為了表明key和value不需要有什麼關係，value的二進位使用＋/－而不是1/0來表示。）

答：每個地址初始為(0, 0, 0)，將－視為-1，＋視為1，把每個位的數值加和即可。所以存完這兩條數據後，這個地址的值會變成(-2, 0, 2)。所以你看到了，確實是使用固定大小的空間來存的。如果每個位用一個byte來保存，那就需要限制數值的範圍是-127~+127。假如我們使用的value是m bit，那不管有多少數據，一個地址需要的空間大小就是m * 8bit。

然後是第二個問題：
假設我們有兩條數據：{001:－－＋, 011:－＋＋}，那應該怎麼存，怎麼取？（假設要存的key和value都是3bit的）

存：每條數據要存到多個地方，我們先假設每條數據要存到「差別&<=1bit」的地址中（專業術語叫Hamming distance），那麼001這條需要保存到{001, 101, 011, 000}這4個地址中，011這條需要保存到{011, 111, 001, 010}這4個地址中。存完之後，按照我們剛才說的演算法，那麼001位置保存的就是(-2, 0, 2)；101位置只有第一條數據，所以是(-1, -1, 1)；而110位置沒有修改，還是(0, 0, 0)。

取：取的時候需要取所有「差別&<=1bit」的地址。所以，如果以001來取數據，我們需要取{001, 101, 011, 000}這4個地址，然後將結果加起來（結果是(-6, -2, 6)），正/負理解為＋/－，我們就得到了結果：－－＋。你看，我們成功地查出來了001:－－＋這條數據。
當然，這麼折騰一圈肯定需要有更多的好處，我們再試試用100來取數據。我們需要取{100, 000, 110, 101}這4個地址，加和最後為(-2, -2, 2)。也就是，我們用100也查出來－－＋這條數據了。
如果用101作為條件，結果是(-4, 0, 4)，0隨機轉為＋和－，也就是說，有可能隨機出－－＋，也有可能隨機出－＋＋。這就是多條數據混雜的情況了。更極端一點，可以想像如果每個地址下都是(0, 0, 0)，那等價於隨機。
總之，通過一個不精確的key，我們也是能查到點結果的。結果是否靠譜，取決於查詢條件有多接近真實的key，以及有多少干擾。

真實的SDM與上面的模型還有一點區別：
1. 為了能解決具體問題key和value只用3bit肯定是不夠的，怎麼也得256bit，甚至上千bit。這時候，Hamming距離&<=1肯定是不成的，怎麼也得幾十吧
2. 按上面這種參數算下來，存取一次就得讀寫海量的地址。所以，為了提高效率，並不是所有可能的key都有一個對應的地址，而是選取很少的一部分地址，只從這些地址中存取。
3. 具體的玩法包括：

用來存key-value，可以進行模糊的查找。與大腦「提示一下就能想起來」有類似之處。
用來存一堆key，key=value。雖然每次查詢的結果不一定靠譜，但一定比起查詢的key更接近一個真實的key。所以多次查詢就可以達到逐漸逼近的效果。這與大腦「一點一點回憶起來」有相似之處。
用來存一個鏈。key=P(n)，value=P(n+1)。那麼，對P(n)的查詢就可以起到"預測"的效果了。這與大腦的「預測」有相似之處。

我的看法：
SDM想解決的是，超大數據量下，通用的模糊查詢的問題。而目前，同類問題通常使用建模後學習參數的思路來解決。至於與大腦的「學習」相提並論，還缺少很多關鍵條件，比如：模式/概念的識別，結果的反饋等。
SDM作為一種通用的演算法，不利用數據的規律，而是依賴Hamming距離決定數據相似度，在目前來看是比較失敗的。這導致了：一方面，針對具體用途不會有什麼效果優勢；另一方面，在效果持平下，不會有效率優勢。
用Google學術搜索的結果讓我感覺這玩意貌似一直沒有進入主流視野。在看到剛才那些例子（數字識別、鏈的預測）的時候，主流的反應通常是神經網路、馬爾科夫鏈。（p.s. 神經網路比SDM提出的要晚，這是後話了）

附，主要參考資料：
1. http://en.wikipedia.org/wiki/Sparse_distributed_memory
2. ftp://reports.stanford.edu/pub/cstr/reports/csl/tr/89/400/CSL-TR-89-400.pdf

參見維基百科對 DHT 的解釋： http://zh.wikipedia.org/wiki/%E5%88%86%E6%95%A3%E5%BC%8F%E9%9B%9C%E6%B9%8A%E8%A1%A8

「稀疏」主要是指存儲的稀疏，類似於「稀疏」矩陣。