Computing with Residue Numbers in High-Dimensional Representation

高維表示中的殘差計算 https://arxiv.org/abs/2311.04872

https://direct.mit.edu/neco/article/37/1/1/125267 2025

應用：

基礎：

計算神經科學中的先前工作[11]，[30]強調殘數數系統賦予網格細胞有用的計算屬性，包括高空間分辨率、模塊化更新和錯誤校正。我們展示了殘數超維計算如何在工作神經實現中成功實現這些編碼屬性（第2.2節和2.3節）。反過來，我們的代數框架對計算神經科學有兩個貢獻。首先，我們展示了如何將殘數數系統擴展到一個自洽的非負六邊形坐標系統。其次，我們提供了一種新的算法，通過諧振器網絡集體耦合空間位置到網格細胞模塊。我們框架對系統神經科學的核心預測是，每個網格細胞模塊對應于諧振器網絡中的一個因子估計。更具體地說，每個模塊實現了一個環面吸引子網絡，與海馬體和其他網格細胞模塊的乘法耦合使錯誤校正成為可能。這一預測既與支持單個網格細胞模塊中連續吸引子網絡存在的最新實驗分析一致[41]，也與海馬體和內側內嗅皮層聯合吸引子動力學的最新理論一致[42]。

從運動中推斷結構或者將由于3D形狀和照明產生的陰影與光譜反射屬性分離。大腦如何通常分離這些變化因素是未知的，并且由于因素組合創建任何給定場景的方式在計算上是具有挑戰性的，因為存在組合爆炸[32]。我們分兩個階段解決這個問題：

摘要??

我們介紹了一種名為殘數超維計算（Residue Hyperdimensional Computing，簡稱RHC）的計算框架，它將殘數數系統與在隨機高維向量上定義的代數統一起來。我們展示了如何將殘數表示為高維向量，使得可以通過向量元素上的組件級、可并行化的操作執行代數運算。結合一種高效的高維向量分解方法，該框架能夠在大幅減少資源使用的情況下表示和操作具有大動態范圍的數值，并且展現出對噪聲的顯著魯棒性。我們展示了這一框架在視覺感知和組合優化等計算難題上的潛力，顯示了其相較于基線方法的改進。更廣泛地說，該框架為大腦中網格細胞的計算操作提供了可能的解釋，并為表示和操作數值數據提出了新的機器學習架構。

1 引言

表示和計算數值的高維表示形式——例如位置、速度和顏色——是機器學習和計算神經科學中的一個核心問題。在機器學習中，數值的向量表示對于在神經網絡中定義位置或功能編碼非常有用[1]–[3]，提高對對抗性示例的魯棒性[4]，以及生成高效的分類器[5]。在神經科學中，實驗者尋求理解大腦中神經元群體如何表示和轉換感知或認知變量，因此許多理論家構建了模型，來展示這些變量如何被編碼在高維向量編碼中，以及如何從這些編碼中解碼（例如，[6]–[8]）。

神經科學中高維表示的一個特別突出的例子是海馬體背側內嗅皮層中‘網格細胞’的空間位置編碼[9]。網格細胞在其放電率中具有多個峰值，這些峰值與六邊形格子排列的空間位置相關聯。雖然這種編碼方案乍一看有些令人困惑，但其有用性從其作為群體編碼的功能中變得明顯。與具有傳統單峰編碼功能的神經元群體相比，其編碼分辨率隨著神經元數量的增加而線性增長，網格細胞群體擁有隨著神經元數量增加而呈指數增長的編碼分辨率[10]。特別是，Fiete及其同事強調了網格細胞編碼利用了殘數數的特性（見下文2.2節）[11]。

受這一觀察結果的啟發，我們提出了一個基于殘數數系統的分布式神經計算的全面代數框架。我們的新框架建立在現有的用于計算高維隨機向量的代數框架之上。這個想法最初被稱為全息減少表示計算[12]，現在也被稱為向量符號架構（Vector Symbolic Architectures，簡稱VSA）[13]和超維計算[14]。我們稱我們的新框架為殘數超維計算（RHC），并證明它繼承了標準殘數數系統和超維計算的計算優勢。這使得即使在內存需求大大減少的情況下，也能高效地表示數字并搜索大動態范圍內的數值。此外，正如我們將看到的，新框架為理解網格細胞中的計算提供了有用的形式主義。

總結來說，我們列出了通過殘數超維計算實現的四個關鍵編碼屬性：(1) 代數結構：向量上的簡單操作執行編碼值的加法和乘法；(2) 表達性：可行的編碼范圍與維度的增長速度比線性更好；(3) 高效解碼：解碼所需的資源與編碼范圍的增長速度相比，增長得更慢；(4) 對噪聲的魯棒性。盡管以前提出的一些模型實現了這些屬性中的一些（見表S.1，補充材料A），但據我們所知，殘數超維計算是第一個實現所有這四個理想的框架，正如我們現在將要展示的。

2 結果

我們首先定義了殘數超維計算框架所基于的關鍵概念（第2.1節），然后在第2.2節中完整描述了該框架。然后，我們展示了它在編碼、解碼以及魯棒性方面的有利特性（第2.3節），以及如何將其擴展到多維（第2.4節）和小數編碼（第2.5節）。特別值得注意的是，我們構建了一個類似于網格細胞坐標的六邊形殘數編碼系統，它比正方形格子提供了更高的空間分辨率。最后，我們描述了如何將該框架應用于視覺場景分析和組合優化問題（第2.6節）。

2.1 預備定義

2.2 殘數超維計算

現在，我們介紹分數冪編碼（Fractional Power Encoding，簡稱FPE）如何實現殘數數系統。作為第一步，我們解釋FPE如何實現同余（表示一個余數，模m）現在，我們介紹分數冪編碼（Fractional Power Encoding，簡稱FPE）如何實現殘數數系統。作為第一步，我們解釋FPE如何實現同余（表示一個余數，模m）。

新版：

2.3 諧振器網絡實現殘數的高效解碼

給定殘數的向量表示，我們如何解碼它以恢復其值 x？在超維計算中常用的一種解碼方法是碼本解碼[23]，它涉及將與一組已知值 x 的 M 個碼本向量進行內積。然而，這個過程需要 的存儲空間和 M 次內積評估。

幸運的是，我們可以利用余數將一個數字的動態范圍分解為一組較小的數字，每個數字的整體動態范圍較小，從而改善這種情況。例如，一個動態范圍為105的數字，當表示為模數 [3, 5, 7] 的形式時，總動態范圍變為3+5+7 = 15。這反過來又使解碼所需的內存和計算資源減少了105/15 = 7倍。然而，要使這一方法有效，我們需要反轉方程4——也就是說，我們必須將 z(x) 因式分解為一組由 x 模 mk 表示的組成向量 {zm1(x), zm2(x), ... , zmK(x)}，從中可以輕松恢復 x。為此，我們可以使用諧振器網絡[24],[25]，這是一種最近發現的高效因式分解超維計算向量的方法。圖2a顯示，對于不同的M值范圍，諧振器網絡可以比標準碼書解碼快一個數量級地恢復向量。兩個對這一點有貢獻的參數是向量維度 (D) 和模數數量 (K)。

為了評估諧振器解碼對向量維度的依賴性，我們固定模數數量 (K = 2) 并計算諧振器在有效范圍 M 上的經驗準確性（圖2b）。我們發現，對于固定的 D，準確性在某個M范圍內幾乎保持完美，之后準確性迅速下降。為了評估 D 的擴展性，我們定義維度容量 C 為經驗準確性至少為95%的最大M值。我們發現 C(D) 的擴展性可以用二次多項式很好地擬合（圖2c），這與之前研究的具有兩態組件的諧振器網絡的擴展規律一致[25]。進一步測試更高維度將有助于確認二次擴展性，但即使是線性擴展，其斜率也很大（注意 C(4096) >。

為了評估對模數數量的依賴性，我們固定 D = 1024 并變化 K。我們發現隨著 K 的增加，諧振器容量減少（圖2d），這也與之前的工作一致[25]。盡管如此，我們強調具有較高 K 的諧振器有兩個優勢：每次解碼的計算量減少（圖2a），以及內存需求減少。諧振器只需要 Pk mk = b 個碼書向量，而不是 Qk mk = M。這意味著，在給定的碼書預算下，增加 K 可以增加幾個數量級的有效范圍（圖2e）。值得注意的是，對于給定的 b，最大M由蘭道函數 g(b) 給出，g(b) 隨 b 的增加按規模增長[26]。這意味著在提供足夠的 K 的情況下，存儲需求和有效范圍之間存在指數級的擴展關系。

最后，我們評估了諧振器網絡解碼對噪聲的魯棒性。我們從 von Mises 分布中抽取均值為0、集中度為 κ 的相位噪聲；較高的 κ 表示噪聲較小。在圖2f中，我們觀察到性能隨噪聲的增加逐漸下降，但即使在高噪聲水平下，容量仍然保持相當高。

2.4 多維度的推廣

2.4.1 Zn 的笛卡爾表示

（新版修改了從六邊形到三角）

2.5 擴展到小數解碼分辨率

在前面的部分中，我們專門使用整數狀態和實現它們的殘數數系統。然而，有趣的是，我們可以將 FPE（分數冪編碼）的定義擴展到有理數（方法 4.4.1），并且諧振器網絡會收斂到非整數的 FPE 編碼，即使碼本僅包含整數的編碼（圖 4a 和 b）。嚴格來說，超越整數的這種擴展不再是殘數數系統，乘法綁定也不再有明確的定義。然而，對于網格細胞的理論分析中已經考慮了向小數分辨率的擴展，例如在 [11]，[30] 中，我們展示了諧振器動態實現了這個小數分辨率。

圖 4b 建議了一個有效的小數精度解碼程序。碼本狀態和最終諧振器網絡狀態之間的內積可以通過將狄拉克梳與 sinc 函數卷積來很好地描述（補充材料 B）。對于整數編碼，這個函數將在所有不在峰值附近的特征上評估為 0，但對于非整數，情況不再如此。盡管如此，我們還是能找到最匹配諧振器網絡狀態的小數偏移量，以便解碼小數值（方法 4.4.2）。

相位噪聲是解碼小數狀態的限制因素。為了更嚴格地量化這一點，我們在不同的噪聲環境下（κ 分別為 16 和 1）評估了具有不同有效范圍 M 的諧振器網絡。然后，我們將每個單位間隔分割成 r 個分區，這樣就有 M · r 個不同的數字被表示。圖 4c 和 4e 分別顯示了在 κ = 16 和 κ = 1 下，不同分區數量的解碼精度。為了考慮精度和區分的不同狀態數量，我們還報告了“每個向量的比特數”指標 [31]，在圖 4d 和 4f 中。這個指標驗證了在較低噪聲下，我們可以更可靠地解碼更多的狀態

2.6 應用

2.6.1 從圖像中高效分離物體形狀和姿態

在這里，我們研究視覺中的分離問題——即在僅知道圖像像素值的情況下，恢復場景的底層組成部分的任務。這類問題在視覺感知中比比皆是；示例包括從運動中推斷結構或者將由于3D形狀和照明產生的陰影與光譜反射屬性分離。大腦如何通常分離這些變化因素是未知的，并且由于因素組合創建任何給定場景的方式在計算上是具有挑戰性的，因為存在組合爆炸[32]。

我們通過兩個階段解決這個問題。首先，我們通過卷積稀疏編碼（方法 4.5）形成圖像的潛在特征表示。這一步反映了初級視覺皮層中的神經表示，據推測這種表示是用少量圖像特征來描述圖像內容的[33]。我們觀察到這一步是有用的，因為它有助于去相關化圖像模式，從而實現更高的精度和加速諧振器網絡的收斂。

其次，我們將潛在的特征表示編碼成高維向量，然后可以通過諧振器網絡將其分解為其組成部分（Oa、Hb、Vc）。這是通過將每個圖像特征的位置的殘數編碼疊加成一個單一的場景向量 s（方法 4.5，方程 10）來完成的。得到的向量 s 可以等價地表示為代表物體形狀和位置的向量的乘積，因此，分離這些因素的問題本質上就變成了一個向量分解問題。

標準的方法來分解場景向量（例如，在[34]中）將是使用三個碼本，分別對應形狀、水平位置和垂直位置，總共有 10 + 105 * 2 = 220 個碼本向量。相比之下，具有模數 {3, 5, 7} 的殘數數系統使用 7 個因子，但只需要 10 + (3 + 5 + 7) * 2 = 40 個向量。圖 5b 展示了兩種問題設置的示例運行。

圖 5c 展示了殘數諧振器與標準諧振器基線相比的兩個主要優勢：內存需求的減少（正如所描述的）和所需的迭代次數。雖然在模擬中，標準諧振器平均需要超過 2,000 次碼本評估，但殘數諧振器平均只需要 ≈ 800 次碼本評估。（與蠻力搜索相比，兩者都有顯著改進，蠻力搜索需要 110,250 次碼本評估）。關鍵的教訓是，對諧振器網絡的這一簡單改變導致了所需計算數量的乘法減少。

2.6.2 產生子集和問題的確切解

最后，我們將我們的子集和算法與蠻力搜索以及解決決策問題的指數時間算法進行了比較。諧振器網絡找到解決方案所需的平均迭代次數大大少于蠻力搜索指數增長的成本（見圖 6e），并且隨著維度的提高而改善。我們發現，在 CPU 上，對于 |S| > 28 的情況，諧振器網絡的時鐘時間比指數時間算法更快（見圖 6f，方法 4.6）；大部分計算時間都花在生成向量表示上，而不是諧振器網絡動態本身。更重要的是，雖然基線算法需要 O(2^|S|) 的內存來保存內存中的候選子集，但諧振器網絡只需要 O(D · |S|) 的內存，因為它永遠不需要明確表示每個子集。我們強調，諧振器網絡的 CPU 實現主要是作為概念驗證，而且如果在新興的計算平臺上實現諧振器網絡，可能會獲得進一步的性能提升，如 [34]，[39] 中所述。

3 討論

我們的研究首次定義了與超維計算相結合的殘數數系統。該框架繼承了兩個系統的益處：來自殘數數系統的無進位算術和中國剩余定理的理論保證，以及超維計算的魯棒性和疊加計算特性[40]。該框架提供了一種有利的方式來編碼、轉換和解碼對噪聲具有魯棒性的變量。綜合這些屬性，使得殘數超維計算成為一個吸引人的框架，用于有效解決困難的計算問題，特別是那些涉及組合優化的問題。它還對模擬大腦中的群體編碼，特別是網格細胞，具有意義。

計算神經科學中的先前工作[11]，[30]強調殘數數系統賦予網格細胞有用的計算屬性，包括高空間分辨率、模塊化更新和錯誤校正。我們展示了殘數超維計算如何在工作神經實現中成功實現這些編碼屬性（第2.2節和2.3節）。反過來，我們的代數框架對計算神經科學有兩個貢獻。首先，我們展示了如何將殘數數系統擴展到一個自洽的非負六邊形坐標系統。其次，我們提供了一種新的算法，通過諧振器網絡集體耦合空間位置到網格細胞模塊。我們框架對系統神經科學的核心預測是，每個網格細胞模塊對應于諧振器網絡中的一個因子估計。更具體地說，每個模塊實現了一個環面吸引子網絡，與海馬體和其他網格細胞模塊的乘法耦合使錯誤校正成為可能。這一預測既與支持單個網格細胞模塊中連續吸引子網絡存在的最新實驗分析一致[41]，也與海馬體和內側內嗅皮層聯合吸引子動力學的最新理論一致[42]。

該框架還對神經群體如何解決困難的優化問題，如視覺場景的分離，具有意義。最近的工作強調了超維計算作為類腦計算抽象的前景[34]，[40]，[43]。殘數超維計算大幅減少了解決解碼問題和組合優化所需的存儲和平均操作數量，提供了一個簡單而強大的改進。此外，我們框架建議的相位表示直接映射到Q態相位網絡[44]，預示著在尖峰神經網絡[45]中的有前景的實現，以及解決組合優化問題的策略[46]。

最后，我們的框架在子集和問題上的性能表明了一條新途徑，用于解決具有分布式表示和非傳統硬件的優化問題。子集和問題特別適合我們的框架，因為它可以通過高維向量的哈達瑪德積操作輕松實現。由于其他難題，如3-SAT，可以有效地映射到子集和問題上，我們的結果可能為有效解決NP難問題指明了一類新的并行算法。

4 方法

4.1 代數運算的定義

4.1.1 加性綁定運算的定義

我們在余數超維計算中通過使用Hadamard積操作（逐元素相乘，⊙）來實現加法：即，。Hadamard積正確地實現了加法，因為它是交換的。可以如下解釋：

4.1.2乘法綁定操作的定義

4.2 解碼方法

4.2.2 諧振器網絡細節

4.2.3 諧振器網絡解碼準確性、容量和噪聲魯棒性的評估

我們評估了諧振器網絡的準確性，作為向量維度 (D)、有效范圍 (M)、模數數量 (K) 和噪聲水平（依賴于 κ）的函數。在圖2f所示的實驗中，我們僅添加了噪聲，除非另有說明，否則 K = 2。圖2d中 D = 1024，圖2f中 D = 512。為了計算與 M 相關的曲線的數據點，我們生成了一個遞增的質數列表，并選擇 K 個連續的質數作為模數。有效范圍 M 是這些模數的乘積。我們繼續在固定的 D 和越來越大的 M 上進行實驗，直到經驗準確性低于給定的閾值（圖2a和2c中為0.95，其他情況下為0.05）。為了報告圖2a所需的比較次數，我們將平均內積迭代次數按準確性進行歸一化，并僅在高準確性范圍內（95%以上）可視化曲線。

4.3 六邊形余數編碼

要將二維向量 x 投影到三維六邊形坐標 y，我們將其乘以矩陣 Ψ：

4.4 子整數精度解碼

4.4.1 編碼方案向有理數的擴展

我們通過與方程4中描述的相同過程來形成余數（模 mk）的表示。如果 q 是一個整數，那么此過程與定義2.2.1一致。但一般情況下，。這很重要，因為雖然我們仍然可以通過內積來評估相似性并執行加法運算，但乘法運算則不再明確定義。

4.4.2 使用諧振器網絡進行子整數解碼

使用諧振器網絡進行子整數解碼包括三個步驟。首先，讓諧振器更新其因子估計，直到收斂到一個固定點。我們強調，即使諧振器的碼書中只包含整數，子整數編碼也是諧振器的固定點（第2.5節）。其次，我們為每個模數找到最接近的整數碼書，并生成在該解碼整數范圍內的分數值的最近碼書（共r個）。第三，我們使用這些編碼分數值的向量進行碼書解碼，返回我們的結果。

4.4.3 噪聲情況下的子整數解碼評估

我們固定 D = 512，并設置 κ = {16.0, 1.0}。我們讓諧振器網絡運行到最大迭代次數或收斂，并評估最接近的整數和最接近的分數狀態是否正確。如果正確，我們認為解是正確的，并報告準確性和每個向量的比特數。

4.4.4 計算每個向量的比特數

為了衡量解碼的總信息量，我們考慮了解碼的準確性和區分的狀態數量。單個數字解碼的信息量（記為 I n u m ）使用相應的準確性（ a ）和總搜索空間的大小（ P ）計算，公式如下：

關于該公式的詳細推導，請參見[31]的第2.2.3節。根據這一指標，當準確性處于隨機水平（1/P）時，解碼的信息量為0。

4.5 視覺場景分解實驗

卷積稀疏編碼通過最小化以下能量函數 E 為每個圖像 I(x, y) 學習一組基礎函數的字典 {?j (x, y)} 并推斷出一組稀疏潛在表示 {Aj (x, y)}:

對于我們的對象示例，我們使用 MNIST 數據集中的 10 張圖像。稀疏編碼字典元素在 MNIST 數據集的一個子集上進行了優化。在為每個圖像推斷出稀疏碼后，我們將其編碼為高維向量（D = 10,000）。我們使用基數為 {3, 5, 7} 的余數數系統來處理水平和垂直維度，然后可以選擇枚舉所有 105 個單因素碼書（標準方法）或使用分別具有 3、5 和 7 個碼書的 3 個因素（余數方法）。在這兩種情況下，我們都運行諧振器網絡直到收斂到一個匹配場景表示的向量（包括重新初始化，如果在固定次數迭代后沒有收斂或陷入局部最小值），并記錄平均迭代次數乘以平均碼書評估次數（對于余數編碼來說，這個值較小）。

4.6 子集和實驗

我們使用具有 3 個模數的余數數系統，{m ? 1, m, m + 1}，其中 m 是一個正整數，確保我們的模數是互質的。為了生成隨機子集和問題，我們首先定義一個最大和范圍為 M/2。對于圖6b 和 6c，m = 200，。

然后，我們從均勻分布中抽取隨機變量（縮放到0和最大集合大小的和的一半之間）。我們接著選擇集合的一個隨機子集（所有子集的可能性相等）并計算其和。這個和作為輸入提供給諧振器網絡，我們認為其解決方案是正確的，如果它收斂到相同的和。如果諧振器網絡返回錯誤的輸出，我們將從不同的隨機初始化重新啟動它，直到達到最大試驗次數。我們改變向量維度 (D) 和集合大小 (|S|)，在多次模擬后報告準確性。對于圖6d，D = 400。

為了比較相對于暴力破解的方法所需的評估次數（圖6e），我們記錄每個集合大小的平均評估次數。我們將暴力破解評估所需的內積比較次數除以每次諧振器網絡迭代所需的比較次數。此外，我們將諧振器迭代次數按準確性進行歸一化，以確保公平比較。在將我們的算法與解算器進行比較時，我們實現了一個精確的子集和算法作為基準 [48]。我們設置 m = 1,000，D = {10,000, 20,000}，并從范圍 [0, 5000] 中均勻抽取整數。