Linear Codes for Hyperdimensional Computing

超維度計(jì)算中的線性碼

https://arxiv.org/pdf/2403.03278

解讀總結(jié)：

本文的核心觀點(diǎn)是將線性碼引入高維計(jì)算（HDC）領(lǐng)域，以提升性能、效率和可擴(kuò)展性。以下是本文的重點(diǎn)及主要觀點(diǎn)解讀：

1. 線性碼的優(yōu)勢(shì)：

- 線性碼通過(guò)布爾線性代數(shù)定義，隨機(jī)選擇時(shí)具有良好的非相干性特性，與非線性碼相比無(wú)性能損失。

- 其代數(shù)結(jié)構(gòu)為 ⊕-恢復(fù)問題提供了快速解決方案，并顯著加速了 Σ-恢復(fù)中的窮舉搜索方法。

2. 高效性與存儲(chǔ)優(yōu)化：

- 線性碼的生成矩陣支持高效編碼（僅需異或操作），且存儲(chǔ)需求大幅降低（只需存儲(chǔ)生成矩陣而非整個(gè)碼）。

- 驗(yàn)證線性碼的非相干性特性比非線性碼更高效，運(yùn)行時(shí)間從二次關(guān)系降至線性關(guān)系。

3. 應(yīng)用廣泛：

- 線性碼在實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)（如鍵值存儲(chǔ)、集合、視覺場(chǎng)景分析等）中表現(xiàn)優(yōu)異，支持組合結(jié)構(gòu)的表示和分解。

- 提供了幾乎瞬時(shí)的恢復(fù)能力，在實(shí)驗(yàn)中顯著優(yōu)于現(xiàn)有的諧振網(wǎng)絡(luò)和窮舉搜索方法。

4. 未來(lái)研究方向：

- 探索線性碼在近似計(jì)算中的應(yīng)用，進(jìn)一步優(yōu)化恢復(fù)算法。

- 將線性碼擴(kuò)展到學(xué)習(xí)任務(wù)（如分類、聚類、回歸）以及實(shí)值或復(fù)值高維計(jì)算領(lǐng)域。

觀點(diǎn)總結(jié)：

本文提出了一種基于線性碼的高維計(jì)算框架，解決了傳統(tǒng)方法在效率和存儲(chǔ)上的瓶頸，同時(shí)保持甚至提升了性能。這一方法不僅在理論上有堅(jiān)實(shí)的基礎(chǔ)，還為實(shí)際應(yīng)用提供了強(qiáng)大的工具，展示了線性碼在高維計(jì)算中的巨大潛力。

后續(xù)改進(jìn)：《All You Need is Unary: End-to-End Bit-Stream Processing in Hyperdimensional Computing》

摘要

高維計(jì)算（HDC）是一種新興的計(jì)算范式，用于將組合信息表示為高維向量，并在從機(jī)器學(xué)習(xí)到神經(jīng)形態(tài)計(jì)算的廣泛應(yīng)用中展現(xiàn)出巨大的潛力。HDC 長(zhǎng)期以來(lái)的一個(gè)挑戰(zhàn)是如何將組合表示分解為其組成因子，這一問題被稱為恢復(fù)問題。在本文中，我們提出了一種解決恢復(fù)問題的新方法，并建議使用隨機(jī)線性碼。這些碼是布爾域上的子空間，是信息論中一個(gè)被廣泛研究的主題，在數(shù)字通信中有多種應(yīng)用。我們首先證明，使用隨機(jī)線性碼進(jìn)行高維編碼保留了當(dāng)前主流（普通）隨機(jī)碼的良好特性，因此這兩種方法生成的高維表示具有相當(dāng)?shù)男畔⒋鎯?chǔ)能力。接著，我們展示了隨機(jī)線性碼具有一種豐富的子碼結(jié)構(gòu)，可以用來(lái)構(gòu)建鍵值存儲(chǔ)，這涵蓋了 HDC 的大多數(shù)用例。最重要的是，我們證明，在我們開發(fā)的框架下，隨機(jī)線性碼允許簡(jiǎn)單的恢復(fù)算法來(lái)分解（無(wú)論是捆綁還是綁定的）組合表示。前者依賴于構(gòu)建布爾域上的某些線性方程系統(tǒng)，其解可顯著縮小搜索空間，并在許多情況下嚴(yán)格優(yōu)于窮舉搜索。后者利用這些碼的子空間結(jié)構(gòu)實(shí)現(xiàn)可證明正確的因式分解。兩種方法都比現(xiàn)有的最先進(jìn)的諧振網(wǎng)絡(luò)快得多，通常快一個(gè)數(shù)量級(jí)。我們?cè)?Python 中使用基準(zhǔn)軟件庫(kù)實(shí)現(xiàn)了我們的技術(shù)，并展示了有前景的實(shí)驗(yàn)結(jié)果。

I. 引言

高維計(jì)算（HDC，也稱為向量符號(hào)架構(gòu)）是一種新興的計(jì)算范式，旨在模糊信息的基于位置的普遍表示方式，其中比特的意義與其相對(duì)位置相關(guān)聯(lián) [1]。與傳統(tǒng)計(jì)算不同，傳統(tǒng)計(jì)算通過(guò)對(duì)象的上下文定位構(gòu)建數(shù)據(jù)結(jié)構(gòu)（例如列表、樹、向量等），而 HDC 范式將原子項(xiàng)識(shí)別為無(wú)上下文比特的高維向量，然后通過(guò)各種代數(shù)操作將其用作構(gòu)建更復(fù)雜數(shù)據(jù)結(jié)構(gòu)的構(gòu)建塊——這些數(shù)據(jù)結(jié)構(gòu)同樣是高維（HD）向量。HDC 框架受到廣泛的科學(xué)挑戰(zhàn)和工程應(yīng)用的推動(dòng)，涵蓋從認(rèn)知模型 [2, 3, 4] 到機(jī)器學(xué)習(xí)的基礎(chǔ)任務(wù) [5, 6, 7, 8]，再到 DNA 測(cè)序 [9]、語(yǔ)音識(shí)別 [10]、機(jī)器學(xué)習(xí)硬件 [11]、機(jī)器人 [12] 等各種應(yīng)用。HDC 近年來(lái)吸引了大量研究，包括幾項(xiàng)理論研究 [13, 14] 和綜述 [15, 16, 17]。

HDC 范式進(jìn)一步劃分為不同的架構(gòu)，每種架構(gòu)都指定了字母表、捆綁運(yùn)算符和綁定運(yùn)算符。字母表的選擇決定了原子 HD 向量的條目；常見選擇是“密集”（即 {±1}）、“稀疏”（即 {0, 1}），或在某些情況下復(fù)數(shù) [5, 18]（另見 [19]）。捆綁運(yùn)算符接收兩個(gè) HD 向量作為輸入，并輸出與兩者相似的 HD 向量；常見選擇是實(shí)值加法 [13, 14]、布爾 OR [5] 或多數(shù)運(yùn)算符 [11]。綁定運(yùn)算符接收兩個(gè) HD 向量作為輸入，并輸出與兩者均不相似的 HD 向量。總的來(lái)說(shuō)，幾乎所有 HDC 工作都將綁定定義為逐點(diǎn)（或 Hadamard）乘積，這在密集（即 {±1}）表示的情況下等同于異或（XOR）。

顯然，特定架構(gòu)的選擇在很大程度上取決于 HDC 實(shí)現(xiàn)的系統(tǒng)規(guī)范。在本文中，我們專注于最常見的架構(gòu)，通常稱為 Multiply-Add-Permute（MAP，盡管我們的方法消除了對(duì)置換操作的需求），在這種架構(gòu)中，HD 向量是密集的，捆綁運(yùn)算是實(shí)值加法“+”，綁定運(yùn)算是異或“⊕”。

在 HDC 應(yīng)用的系統(tǒng)規(guī)范背景下出現(xiàn)了各種計(jì)算挑戰(zhàn)，其中包括回憶（即識(shí)別給定對(duì)象是否存儲(chǔ)在內(nèi)存中）、比較（即兩個(gè)給定表示有多“相似”）或?qū)?HD 表示進(jìn)行訓(xùn)練 [7]。回憶和比較已被 [13] 理論分析，并顯示出與一種稱為非相干性的屬性密切相關(guān)，該屬性概括了不同 HD 表示之間的不相似程度，并源自準(zhǔn)正交性 [20]。HDC 中最重要的開放問題之一，也是 [15] 綜述中提到的第一個(gè)開放問題，是恢復(fù)問題。在各種應(yīng)用中，人們會(huì)收到一個(gè)復(fù)雜數(shù)據(jù)結(jié)構(gòu)的表示作為輸入，并需要將其分解為其組成元素；輸入可能是多個(gè) HD 向量捆綁的結(jié)果（即捆綁恢復(fù)）和/或綁定這些向量的結(jié)果（即綁定恢復(fù)）。恢復(fù)是一些重要 HDC 系統(tǒng)（如通用鍵值存儲(chǔ)，它將大多數(shù)其他數(shù)據(jù)結(jié)構(gòu)實(shí)例化為特殊情況）或更具體領(lǐng)域應(yīng)用（如視覺場(chǎng)景分析或搜索樹查詢 [21]）的關(guān)鍵組成部分。已經(jīng)提出了幾種啟發(fā)式方法來(lái)處理恢復(fù)問題 [21, 22]，但迄今為止尚無(wú)嚴(yán)格的解決方案。

在本文中，我們的主要?jiǎng)訖C(jī)是高效的恢復(fù)算法，因此我們建議在 HDC 中使用隨機(jī)線性碼。“線性碼”是指布爾域上的子空間，具有較大的兩兩漢明距離。這些對(duì)象在信息和編碼理論中得到了廣泛研究，主要用于通信系統(tǒng)中的糾錯(cuò) [23]。隨機(jī)選擇線性碼很有吸引力，因?yàn)楂@得具有良好特性的碼的概率很高，例如較大的漢明距離。

我們首先證明，通過(guò)將 HDC 編碼過(guò)程指定為隨機(jī)線性碼，基本上不會(huì)丟失任何東西。也就是說(shuō)，如前所述，[13] 使用非相干性屬性衡量的 HDC 系統(tǒng)的信息容量不會(huì)因在線性結(jié)構(gòu)上施加編碼過(guò)程而受到不利影響。事實(shí)上，隨機(jī)線性碼比非線性碼在選擇合適碼的概率上提供了更好的界限。此外，使用任何線性碼進(jìn)行編碼都可以通過(guò)簡(jiǎn)單的邏輯運(yùn)算完成（特別是異或和與運(yùn)算），可以在軟件/硬件中輕松實(shí)現(xiàn)，并且需要指數(shù)級(jí)更少的空間來(lái)存儲(chǔ)。此外，線性碼還可以支持按需隨機(jī)選擇碼字，這是 HDC 范式的核心，只需付出少量額外努力即可實(shí)現(xiàn)。

接著，我們繼續(xù)展示在 HDC 中使用線性碼所帶來(lái)的顯著收益，具體體現(xiàn)在三個(gè)方面：

1) 鍵值存儲(chǔ)的簡(jiǎn)單實(shí)現(xiàn)，為研究和實(shí)現(xiàn)多種 HD 數(shù)據(jù)結(jié)構(gòu)提供了一種統(tǒng)一的方法。

2) 在捆綁恢復(fù)問題中顯著縮小搜索空間的大小。

3) 高效且可證明正確的綁定恢復(fù)問題解決方案。

我們的捆綁恢復(fù)算法依賴于對(duì)某些碼字子集的窮舉搜索，盡管其規(guī)模比整個(gè)碼本小得多（呈指數(shù)級(jí)縮小）。然而，我們的綁定恢復(fù)算法既不依賴窮舉搜索，也不依賴任何啟發(fā)式方法，事實(shí)上適用于所有線性碼，無(wú)論其非相干性特性如何。它基于一個(gè)簡(jiǎn)單的線性代數(shù)事實(shí)，即子空間中的向量在該子空間的一組基上具有唯一的表示，并且可以通過(guò)求解線性方程組在線性時(shí)間內(nèi)找到這種表示。我們使用現(xiàn)成的 Python 庫(kù)實(shí)現(xiàn)了這兩種算法，并展示了令人鼓舞的結(jié)果。

具體而言，與窮舉搜索相比，我們的捆綁恢復(fù)算法在運(yùn)行時(shí)間上表現(xiàn)出顯著減少，并且令人驚訝的是，在窮舉搜索失敗的情況下（例如由于非相干性不足），我們的算法仍然能夠一致成功。此外，我們的綁定恢復(fù)算法為所有線性碼提供了幾乎即時(shí)且正確的解決方案，遠(yuǎn)遠(yuǎn)優(yōu)于最近一種稱為諧振網(wǎng)絡(luò)技術(shù) [21, 25] 的基準(zhǔn)實(shí)現(xiàn) [24]。例如，我們的算法通常在不到一秒內(nèi)完成，而諧振網(wǎng)絡(luò)往往需要數(shù)分鐘僅用于生成所有碼字的列表。我們還評(píng)論道，由于我們使用線性碼的特定方式，捆綁和綁定向量的組合也可以被恢復(fù)。例如，要恢復(fù)一組綁定向量中的所有碼字，可以首先應(yīng)用我們的捆綁恢復(fù)算法，然后對(duì)每個(gè)結(jié)果綁定向量應(yīng)用綁定恢復(fù)算法。

本文的結(jié)構(gòu)如下。在第二節(jié)中，我們簡(jiǎn)要介紹了 HDC，包括 [13] 對(duì)信息容量與非相干性之間關(guān)系的分析。同樣在第二節(jié)中，我們提供了布爾線性代數(shù)和線性碼的基礎(chǔ)知識(shí)，并重申了（已知的）事實(shí)，即隨機(jī)線性碼具有高信息容量（即低相干性），并且其概率界優(yōu)于不一定線性的隨機(jī)碼。在第三節(jié)中，展示了線性碼的子碼結(jié)構(gòu)如何適應(yīng)鍵值存儲(chǔ)的簡(jiǎn)單實(shí)現(xiàn)，這將 HDC 的大多數(shù)用例作為特殊情況實(shí)例化。為了說(shuō)明我們構(gòu)建鍵值存儲(chǔ)的統(tǒng)一方法的優(yōu)勢(shì)，我們提供了幾個(gè)特殊案例的例子，其中我們的方法涵蓋了有限集、向量（序列）、搜索樹和視覺場(chǎng)景分析。在第四節(jié)中，我們提出了捆綁和綁定恢復(fù)算法，并正式證明了它們的保證。第五節(jié)提供了實(shí)驗(yàn)結(jié)果，第六節(jié)得出了結(jié)論。

II. 預(yù)備知識(shí)

我們?cè)诘诙?jié) A 部分開始介紹 HDC，從理論角度展示 HDC 并聚焦于恢復(fù)問題。隨后，我們對(duì)線性碼進(jìn)行簡(jiǎn)要介紹，使讀者熟悉布爾代數(shù)和編碼理論，并展示 HDC 和編碼理論之間的若干相似之處。

A. 高維計(jì)算 (HDC)

更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)（如句子或圖像）通過(guò)原子向量的代數(shù)操作獲得。許多框架被提出以促進(jìn)這些操作，其中我們重點(diǎn)關(guān)注最常見的 Multiply, Add, Permute (MAP) 框架 [3]。總的來(lái)說(shuō)，所有這些框架都包含“綁定”和“捆綁”操作。在 MAP 框架中，用于生成與兩個(gè)輸入向量相似的向量的捆綁操作通過(guò)普通整數(shù)加法實(shí)現(xiàn)，記作“+”。綁定操作通過(guò)逐點(diǎn)乘積（或 Hadamard 積）實(shí)現(xiàn)，記作“⊕”。

B. 線性碼簡(jiǎn)介

a) μ-非相干碼與 ?-平衡碼

如第 II-A 節(jié)所述，成功的高維計(jì)算（HDC）的核心在于使用 μ-非相干碼 （定義 1），更重要的是，隨機(jī)（不一定是線性的）碼以高概率滿足 μ-非相干性。我們現(xiàn)在展示一個(gè)簡(jiǎn)單的事實(shí)，即 μ-非相干碼等價(jià)于 ?-平衡碼 ；?-平衡線性碼 是一個(gè)被廣泛研究的概念 [27, 28, 29, 30]，在計(jì)算機(jī)科學(xué)中有廣泛的應(yīng)用。

III. 基于線性碼的鍵值存儲(chǔ)

我們現(xiàn)在展示如何利用線性碼實(shí)現(xiàn)高維鍵值（KV）存儲(chǔ)。一些提議的技術(shù)需要使用 ⊕-恢復(fù)和 Σ-恢復(fù)算法；目前我們將這些算法視為黑箱，并在后文詳細(xì)闡述。

鍵值（KV）存儲(chǔ)是一種基本的數(shù)據(jù)結(jié)構(gòu)，它用索引（鍵）存儲(chǔ)條目（值），并應(yīng)能夠回答“給定鍵對(duì)應(yīng)的值是什么？”這樣的查詢。在本節(jié)中，我們將展示為鍵和值進(jìn)行線性編碼提供了一種使用高維向量維護(hù) KV 存儲(chǔ)的框架。我們首先介紹 KV 存儲(chǔ)必須支持的基本操作，展示如何使用線性碼在實(shí)踐中實(shí)現(xiàn)這些操作，證明其正確性并分析復(fù)雜度。

隨后，我們展示我們的框架可以無(wú)縫擴(kuò)展（再次利用子碼結(jié)構(gòu)）到鍵或值（或兩者）具有組合結(jié)構(gòu)的情況，即某個(gè)給定的鍵（或值）可以進(jìn)一步分解為具有某種上下文意義的原子部分。一個(gè)需要這種組合結(jié)構(gòu)的例子是將搜索樹實(shí)現(xiàn)為高維向量；由于鍵表示該樹中的路徑，它們可以進(jìn)一步分解為表示該路徑的一系列整數(shù)。最后，為了展示我們框架的通用性，我們演示了其在存儲(chǔ)集合和向量（序列）、視覺場(chǎng)景分析以及搜索樹中的應(yīng)用。

形式上，一個(gè) KV 存儲(chǔ) S 是由形如 k, v 的鍵值對(duì)組成的集合，其中鍵 k 來(lái)自某個(gè)集合 K ，值 v 來(lái)自某個(gè)集合 V ，并且存儲(chǔ)的鍵必須彼此不同（允許值相同）。 S 的大小，即其中鍵值對(duì)的數(shù)量，記為 s 。KV 存儲(chǔ)必須支持以下操作：

從定理 1 可以明顯看出，在選項(xiàng) (A) 和選項(xiàng) (B) 之間進(jìn)行選擇的關(guān)鍵因素是密鑰空間 |V| 的大小，相對(duì)于執(zhí)行 Σ-恢復(fù)算法和 s 次奇偶校驗(yàn)的復(fù)雜性之間的權(quán)衡。

A. 組合鍵和組合值

在高維計(jì)算的許多應(yīng)用中，需要一組具有組合結(jié)構(gòu)的鍵或值。例如，在表示搜索樹的鍵值存儲(chǔ)（KV-store）中，一個(gè)鍵 k 表示樹中的一條路徑，而一個(gè)值 v 表示該路徑末端葉子節(jié)點(diǎn)的內(nèi)容（詳見隨后的第 III-B 節(jié)中的詳細(xì)示例）。在這種情況下，路徑是組合性的，因?yàn)樗枋隽嗽?q-叉樹中從根節(jié)點(diǎn)出發(fā)應(yīng)沿著哪些 q 個(gè)兄弟節(jié)點(diǎn)行進(jìn)以到達(dá)指定的葉子節(jié)點(diǎn)。

另一個(gè)例子是視覺場(chǎng)景分析（也將在第 III-B 節(jié)中詳細(xì)討論），即每個(gè)“場(chǎng)景”是一個(gè)“鍵存儲(chǔ)”（即具有單一元素的平凡值集 V 的 KV-store）。每個(gè)場(chǎng)景是由場(chǎng)景中多個(gè)對(duì)象的捆綁組成的，而每個(gè)對(duì)象則是由多個(gè)屬性（如類型、顏色、位置等）綁定而成的。因此，每個(gè)這樣的鍵（或?qū)ο螅┦墙M合性的，因?yàn)樗ㄟ^(guò)綁定多個(gè)高維向量生成。如果要對(duì)場(chǎng)景的高維表示進(jìn)行因式分解，首先會(huì)應(yīng)用 Σ-恢復(fù)來(lái)獲取場(chǎng)景中所有單個(gè)對(duì)象的列表，然后對(duì)每個(gè)對(duì)象進(jìn)一步應(yīng)用 ⊕-恢復(fù)以提取其顏色、位置等屬性。

B. 示例
在本節(jié)中，我們將展示上述鍵值存儲(chǔ)（KV-store）實(shí)現(xiàn)如何通過(guò)適當(dāng)選擇一個(gè)非相干碼 C 及其子碼 K 和 V，涵蓋文獻(xiàn)中最近討論的許多高維數(shù)據(jù)結(jié)構(gòu)用例。

1) 有限集合

可以說(shuō)是最簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，有限集合必須支持添加和刪除元素，以及測(cè)試某個(gè)給定元素是否屬于該集合。為了存儲(chǔ)來(lái)自全集 K 的大小至多為 s 的集合，按照第 III 節(jié)中的構(gòu)造方法進(jìn)行如下操作：

定理 1 表明，這些過(guò)程能夠以規(guī)定的復(fù)雜度正確實(shí)現(xiàn)集合操作。

備注 3 ：如果不希望預(yù)先選擇整個(gè)碼 C，或者 K 中元素的比特表示不可用，則可以通過(guò)輕量級(jí)的簿記動(dòng)態(tài)隨機(jī)選擇碼字，同時(shí)保持 C 的線性結(jié)構(gòu)。詳細(xì)內(nèi)容見附錄 B。

備注 4 ：使用線性碼構(gòu)建的集合數(shù)據(jù)結(jié)構(gòu)在假設(shè)的非相干性方面與使用不一定線性的碼構(gòu)建的結(jié)構(gòu)相同，因此它們的信息容量（即保證成功執(zhí)行添加、刪除和成員操作的最大集合大小 s）也相同。因此，任何依賴于底層碼相干性證明的性質(zhì)都會(huì)自動(dòng)被我們的線性碼變體繼承。例如，我們使用線性碼表示集合的方法自動(dòng)繼承了 [13, 定理 8、9、10] 中提到的大小估計(jì)、交集計(jì)算和噪聲魯棒性。

4) 視覺場(chǎng)景分析

另一個(gè)展示線性碼組合能力的用例是一種描述場(chǎng)景的數(shù)據(jù)結(jié)構(gòu)，該場(chǎng)景包含疊加的對(duì)象，每個(gè)對(duì)象包含多個(gè)屬性。例如，想象一幅圖片，其中有多個(gè)數(shù)字以不同的位置和顏色疊加在一起 [21, 圖 3]。人們希望構(gòu)建一個(gè)單一的高維向量來(lái)描述這樣的場(chǎng)景，以便能夠高效解碼，即給定的組合高維向量可以被分解為其組成對(duì)象，而每個(gè)對(duì)象可以進(jìn)一步分解為其組成屬性。一個(gè)自然的解決方案是使用四個(gè)碼分別描述對(duì)象的顏色、數(shù)字、緯度和經(jīng)度。然后，場(chǎng)景是對(duì)對(duì)象向量的捆綁，每個(gè)對(duì)象向量是從這些碼中各取一個(gè)碼字的綁定結(jié)果。我們?cè)u(píng)論說(shuō)，這種技術(shù)在為機(jī)器學(xué)習(xí)模型添加推理能力方面非常有用。通過(guò)訓(xùn)練這些模型識(shí)別組合結(jié)構(gòu)，然后將這些結(jié)構(gòu)解碼為其組成元素，可以極大地提高這些模型的解釋能力。

我們還評(píng)論說(shuō)，為了在機(jī)器學(xué)習(xí)中成功應(yīng)用該技術(shù)（見上文），必須能夠處理噪聲。也就是說(shuō)，一個(gè)訓(xùn)練用于輸出組合向量的機(jī)器學(xué)習(xí)模型極有可能犯某些錯(cuò)誤（例如，由于模型最后一層激活函數(shù)的輸入不準(zhǔn)確而導(dǎo)致的比特翻轉(zhuǎn)）。為了糾正這種情況，必須在將其輸入我們的 Σ-恢復(fù)和 ⊕-恢復(fù)算法之前，應(yīng)用額外的解碼算法來(lái)去除噪聲。

IV. 恢復(fù)算法

一般來(lái)說(shuō)，這是一個(gè)困難的問題，盡管作者尚未發(fā)現(xiàn)任何關(guān)于該問題的復(fù)雜性結(jié)果（例如，NP 完全性）。在 [21, 25] 中提出了一種使用諧振網(wǎng)絡(luò)的啟發(fā)式解決方案。然而，正如我們即將展示的，如果 是線性碼，則該問題可以通過(guò)直接的布爾代數(shù)求解。

備注 8：我們的實(shí)驗(yàn)表明，這些界限是過(guò)于悲觀的，我們的算法通常比窮舉搜索快一個(gè)數(shù)量級(jí)。

備注 9：需要提到的是，一個(gè)類似于線性碼的 Σ-恢復(fù)問題的研究此前已經(jīng)存在。所謂的二進(jìn)制加法信道 [36] 是一種多發(fā)送方與單接收方之間的通信模型，接收方接收到發(fā)送方二進(jìn)制消息的和，并需要將該和分解為其組成元素。然而，在二進(jìn)制加法信道中沒有“召回”的概念，因此針對(duì)二進(jìn)制加法信道的傳統(tǒng)碼構(gòu)造不一定是非相干的，這使得它們不適合用于高維計(jì)算（HDC）。此外，針對(duì)二進(jìn)制加法信道的傳統(tǒng)碼構(gòu)造通常不是線性的。一個(gè)例外是 [37]，它研究了帶有兩個(gè)發(fā)送方和線性碼的二進(jìn)制加法信道，并提出了一種解碼算法，這是上述 s = 2 的 Σ-恢復(fù)算法的一個(gè)特例。

V. 實(shí)驗(yàn)

A. 當(dāng)前最先進(jìn)的方法

當(dāng)前最先進(jìn)的 ⊕-恢復(fù)和 Σ-恢復(fù)方法是諧振網(wǎng)絡(luò) [21, 25]，以及其改進(jìn)版本 [26] 和 [38]。盡管諧振網(wǎng)絡(luò)從形式上是為了處理 ⊕-恢復(fù)問題而設(shè)計(jì)的（見 [25, 第 2 節(jié)]），但它們可以通過(guò)“解釋消除”擴(kuò)展到執(zhí)行 Σ-恢復(fù)。也就是說(shuō)，實(shí)驗(yàn)表明（例如 [21, 圖 4]），如果對(duì)捆綁的綁定向量應(yīng)用諧振網(wǎng)絡(luò)，網(wǎng)絡(luò)往往會(huì)收斂到其中一個(gè)綁定向量，然后可以從捆綁中減去或“解釋消除”該向量。

具體來(lái)說(shuō)，在諧振網(wǎng)絡(luò)中，為每個(gè)輸入子碼維護(hù)一個(gè)估計(jì)向量。在收斂后，這些估計(jì)向量被綁定，生成的綁定向量作為輸出，并從輸入向量中減去。減去之后，可以再次應(yīng)用諧振網(wǎng)絡(luò)，直到最終得到零向量（或接近零向量）。

第六章 總結(jié)與討論

本文提出在高維計(jì)算（HDC）中使用線性碼，這些碼通過(guò)布爾線性代數(shù)定義。當(dāng)隨機(jī)選擇時(shí)，這些碼相對(duì)于不一定線性的碼保留了良好的非相干性特性，因此可以在不損失性能的情況下安全地用于 HDC。然而，它們的代數(shù)結(jié)構(gòu)為 ⊕-恢復(fù)問題提供了幾乎即時(shí)的解決方案，并可用于顯著加速 Σ-恢復(fù)中的窮舉搜索方法。

另一個(gè)額外的好處是可以更快地驗(yàn)證線性碼是否具有某些非相干性特性，相較于非線性碼更為高效。在關(guān)鍵應(yīng)用中，人們希望確保隨機(jī)選擇的碼確實(shí)具有所需的非相干性特性。為了驗(yàn)證非線性碼的非相干性，必須計(jì)算任何兩個(gè)碼字之間的內(nèi)積，導(dǎo)致運(yùn)行時(shí)間與碼的大小呈二次關(guān)系。然而，由于非相干性與最小距離（在所有碼中）以及最小距離與最小重量（在線性碼中，見定義 2 及其后續(xù)討論）之間的等價(jià)性，驗(yàn)證線性碼的非相干性只需要驗(yàn)證最小重量。這使得運(yùn)行時(shí)間與碼的大小呈線性關(guān)系。

未來(lái)工作的方向非常廣泛，其中最顯著的方向似乎是研究用于近似計(jì)算的線性碼（計(jì)算應(yīng)以高概率成功），以及尋找更快的 Σ-恢復(fù)算法。此外，我們的重點(diǎn)在于諸如召回、恢復(fù)和各種數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)等簡(jiǎn)單計(jì)算任務(wù)；線性碼在更面向?qū)W習(xí)的任務(wù)（如分類、聚類或回歸 [41]）中的作用仍有待探討。最后，編碼理論方法可能會(huì)在二值域之外找到用途，編碼理論思想在實(shí)值 [13] 或復(fù)值 [5] HDC 中的應(yīng)用仍有待研究。

后續(xù)：《單比特流處理：超維計(jì)算中的端到端比特流處理》

原文鏈接：https://arxiv.org/pdf/2403.03278