Fractional Binding in Vector SymbolicRepresentations for Efficient Mutual Information Exploration

向量符號表示中的分數綁定用于高效的互信息探索

https://www.compneuro.uwaterloo.ca/files/publications/furlong.2021.pdf

摘要

互信息（MI）是驅動探索的標準目標函數。使用高斯過程計算信息增益受到時間和內存復雜度的限制，這些復雜度隨著觀察數據數量的增加而增長。我們通過將矢量符號架構與貝葉斯線性回歸相結合，提出了一種高效的MI驅動探索實現方法。我們展示了與基于高斯過程的方法相當的性能，但內存和時間復雜度在樣本數量上保持恒定，而非分別隨樣本數量的平方和立方增長，從而實現了長期探索。

關鍵詞——互信息采樣，貝葉斯優化，矢量符號架構，分數綁定

I. 引言

互信息（MI）是量化探索過程中好奇心的標準目標函數 [1], [2]。本文以貝葉斯優化為框架來實現好奇心，并提出了一種MI驅動的探索算法，其時間和內存需求在觀察數量上保持恒定，優于高斯過程方法計算MI時所需的時間復雜度 t3 和內存復雜度 t2。

一種常見的信息采樣方法是使用高斯過程（GPs）計算信息增益，例如 [3]-[6]。然而，計算MI所需的方差需要對一個與采樣數據點數量 t 的平方成比例增長的矩陣進行求逆。內存的無限制增長以及評估采樣位置所需時間的相應增加，與使用有限內存系統的長期運行不兼容。

為了克服高斯過程的局限性，研究人員通過高效的算法改進了占據網格方法 [7]，用于計算信息增益 [8], [9]。這些方法的復雜度通常與網格單元數量呈線性增長。然而，占據網格存在高斯過程所沒有的限制——分辨率固定，且僅對網格中的點建模。這些缺點可以通過使用非規則和自適應表示（例如三角化網格或KD樹）來緩解，但它們需要額外的機制來表示函數域，并需要更多內存來表示更大的區域。

我們提出了一種結合兩種方法優點的算法。該算法在觀察數量上的內存和時間需求是恒定的，并且與候選采樣位置的數量呈線性關系，但仍能對函數域中的所有點進行定義。我們通過將矢量符號架構（VSA）中的分數綁定概念與貝葉斯線性回歸（BLR）相結合實現了這一點，以建模函數域上的不確定性。

VSAs 用于建模認知過程 [10]-[14]。符號被表示為向量，而認知則通過對這些向量的操作來實現。綁定是一個關鍵操作，通過綁定兩個現有符號 A 和 B 創建一個新符號 C，記作 C = A ~ B，通常表示 A 和 B 之間的槽填充關系。認知語義指針（Cognitive Semantic Pointers）是一種神經實現的 VSA，其綁定操作符為循環卷積。整數量、原子符號（如單詞）和結構化表示（如句子）可以通過綁定在語義指針中表示。為了表示整數量，綁定會迭代整數次，記作 S? = S ~ ... ~ S，其中 k ∈ N，S ∈ R? 是一個固定維度 d 的語義指針，我們稱其為“軸指針”或“軸向量”。

空間語義指針（SSPs）通過分數綁定擴展了語義指針，以表示實數 [13], [15]。分數綁定通過傅里葉變換實現，公式為 S? = F?1{F{S}?}，其中 x ∈ R 是通過軸指針 S 的傅里葉變換逐元素指數編碼的實數值。使用 SSPs 可以讓我們在生物學表征與信息論模型的好奇心之間建立聯系。SSPs 通過建模網格細胞和位置細胞連接到生物學 [16], [17]，這些表征與生物體的位置相關 [18]。此外，空間關系的組織可能在其他腦區中也被使用 [19]。

SSPs 通過 SSP 向量點積誘導的核函數與信息論探索建立了聯系。SSPs 誘導了一個 sinc 核函數 [20]，并且 sinc 核函數已被證明是核密度估計器的高效核函數 [21], [22]。誘導核函數的向量表示可以用于構建內存和時間高效的核密度估計器，如 EXPoSE 算法 [23]。但 Schneider 等人 [23] 構建的是核密度估計器（KDE），而我們將 SSPs 與貝葉斯線性回歸結合，以近似高斯過程回歸。

其他方法也結合了向量表示與 BLR 來提高計算效率。ALPaCA 利用向量空間上的不確定性進行元學習 [24], [25]。Perrone 等人 [26] 將數據投影到向量空間中，以實現更高效的貝葉斯優化。然而，這些技術需要學習從輸入數據到向量空間的投影。SSPs 的優勢在于其表示不需要學習，而是可以設計，從而進一步提高了效率。

在本文中，我們將我們的算法——空間語義指針互信息貝葉斯優化（SSP-MI），與 [6] 中開發的高斯過程互信息貝葉斯優化（GP-MI）算法進行了性能比較。我們通過實驗表明，該算法實現的后悔性能至少與 GP 算法相當，但其時間和內存復雜度在樣本數量 t 上保持恒定，而基于 GP 的方法分別為 O(t3) 和 O(t2)。SSP-MI 的恒定時間和內存需求意味著它可以部署在有限硬件上進行長期運行操作。

II. 方法

兩種算法都通過十個觀測值進行初始化，這些觀測值用于優化超參數。初始化點通過隨機打亂候選位置的順序并使用前 10 個點來選擇。對于兩種算法，超參數僅在初始的 10 個樣本上進行優化，并且之后不再修改。

A. 實驗

我們在 Himmelblau、Branin-Hoo 和 Goldstein-Price 函數上測試了這些算法，這些函數在文獻 [6] 中被用作基準。我們對這些函數進行了縮放，以將問題轉化為最大化問題，從而確保高斯過程超參數擬合收斂，并獲得與文獻 [6] 中報告的類似的后悔值。這些函數在受限域上進行評估，評估時沒有添加噪聲，域內的點沿著每個軸均勻分布，形成一個 100 × 100 的網格。智能體被賦予 250 次采樣的預算。域和縮放因子見表 I。

III. 結果

圖1在左側展示了算法遺憾值的演變，在右側展示了評估采樣位置所花費的累積時間。陰影區域表示N=30 次試驗的95%置信區間。

除了最初的幾個樣本外，各算法的平均遺憾值基本無法區分。表II報告了各算法的 的均值和標準差的差異。正值表示SSP-MI算法的遺憾值和標準差更低。在樣本量為125和250時進行的貝葉斯假設檢驗發現，SSP-MI算法的性能要么優于GP-MI算法，要么與GP-MI算法在95%的概率下無法區分。在存在統計差異的地方，效應量（Cohen's d）為中等到大。在測試場景下，從遺憾值性能來看，沒有理由選擇GP-MI而不是SSP-MI。

SSP-MI的優勢在選擇采樣位置的時間上變得明顯。在每次迭代中，算法都會重新計算候選采樣位置的采集函數。對于GP-MI，計算時間隨著收集的樣本數量增加而增長。對于SSP-MI，計算采集函數的時間與收集的樣本數量無關，因此圖1中觀察到的是線性趨勢.

IV. 討論

我們已經證明了，使用生物學上合理的表示方法，基于互信息（MI）驅動的探索可以實現在連續空間中具有固定內存和計算時間限制的探索。將空間語義指針（Spatial Semantic Pointers，SSP）和貝葉斯線性回歸（Bayesian Linear Regression，BLR）相結合，能夠在有限的內存空間內進行操作，并在任意空間中長期運行。

在三個標準優化目標上，我們的經驗遺憾值性能要么與基于高斯過程（GP）的基線方法在統計上無法區分，要么優于基線方法。與基于GP的方法不同，評估候選采樣位置的時間與收集的樣本數量無關，并且其內存需求為 ，其中 d 是SSP的維度，而GP-MI的內存需求為 ，其中 t 是觀測數量。請注意，我們在圖1中對計算時間的估計保守地包括了一次性編碼成本。盡管需要超過100個樣本才能攤銷這一成本，但編碼可以在操作開始之前完成，這將進一步有利于SSP-MI。與占用網格方法類似，評估時間隨著候選位置數量的增加而線性增長，但SSP-MI仍然在連續空間中定義。

我們的算法是使用向量表示進行好奇心引導探索的初步概念驗證。如果SSP是模擬認知的統一工具，如Eliasmith等 [14] 所述，那么我們的方法也可以模擬概念空間中的好奇心。然而，盡管我們使用SSP對數據進行了編碼，但也可以使用其他能夠誘導核函數的向量編碼方法。仍有算法改進的空間。六邊形SSP [17] 可能會提高編碼候選采樣位置的效率，并進一步將工作與空間表示的神經模型整合。對噪聲的性能退化仍有待研究。

由于計算采集函數是高效的，因此在有限集合中選擇采樣點 x 以最大化采集函數應該是可行的，從而避免因任意采樣函數域而產生的遺憾。此外，我們或許能夠評估整個軌跡，而不僅僅是單個采樣位置。單個SSP可以表示軌跡和空間區域，這些特性或許可以被利用來高效地評估軌跡的信息量，并通過計算點積來評估其在配置空間中的可行性。由于我們的好奇心模型是通過采集函數中的 以實現目標驅動的，因此通過調整預期獎勵和信息增益的權重，可以在任務驅動的探索與類似游戲的探索之間進行切換。

我們展示了一種高效實現好奇心的方法，這可能適用于內存和時間受限的場景。盡管這項工作還處于初步階段，但它為高效的自主探索提供了一個起點。

原文鏈接：https://www.compneuro.uwaterloo.ca/files/publications/furlong.2021.pdf