Auf dem Weg zu relationalem hyperdimensionalem Rechnen

Binding ist der saubere Fall. Mit selbstinversem Binding (elementweise Multiplikation bipolarer Vektoren in MAP, XOR in Binary Spatter Codes) bestimmt c = a ⊗ b jedes der drei aus den anderen beiden, und zwar exakt. Also ist (bindo a b c) eine Relation in jedem Modus mit zwei bekannten Argumenten, so wie pluso in CLP(FD). Mit einem oder keinem bekannten wartet sie. In HRR (zirkuläre Faltung) ist die Inverse nur approximativ, und die Relation damit auch.

Permutation ist eine Bijektion, also ist (permo x n y) in allen Modi exakt, wenn n bekannt ist. Ist n unbekannt, zählt sie auf oder wartet.

Bundling ist der interessante Fall. s = a + b + c bestimmt seine Summanden nicht. Rückwärts ausgeführt fragt (bundleo xs s): "Welche Elemente stecken in dieser Superposition?" Das ist eine Suche. Die Antworten sind nach Ähnlichkeit geordnete Kandidaten, keine feste Menge.

Cleanup, (cleanupo codebook noisy x), setzt einen verrauschten Vektor in Relation zu den Codebook-Einträgen, denen er nahe ist. Sie zählt diese nach Ähnlichkeit geordnet auf.

Faktorisierung, s = a ⊗ b ⊗ c mit allen drei unbekannt, aber jeweils aus einem Codebook, ist das, was Resonator-Netzwerke lösen (Frady, Kent, Olshausen und Sommer, 2020). In Logik-Begriffen ist ein Resonator-Netzwerk ein Constraint-Solver für eine Konjunktion von bindo- und cleanupo-Goals: Es iteriert seine Schätzungen, bis sie sich einpendeln, was sie innerhalb seiner Kapazität meistens tun. Das legt nahe, es so einzubinden, wie CLP(FD) in core.logic eingebunden ist: als Constraint-Domäne mit eigenem Propagator.

A. Hypervektoren als Constraint-Domäne. Logikvariablen laufen über Hypervektoren, so wie FD-Variablen über ganze Zahlen laufen. bindo, permo und bundleo sind Constraints. Exakte Operationen propagieren, sobald genug bekannt ist. Approximative (Bundling rückwärts, Cleanup, Faktorisierung) verzweigen über geordnete Kandidaten oder lassen ein Resonator-Netzwerk als Solver der Domäne laufen.

B. Hypervektoren als Orakel für symbolische Suche. Die symbolischen Terme bleiben die Wahrheit: Maps, Vektoren, exakte Unifikation. Jeder Term hat zusätzlich eine Kodierung, (encodeo term hv), und die Suche nutzt Ähnlichkeit, um ihre Zweige zu ordnen: geto mit unbekanntem Key probiert Keys in der Reihenfolge, wie gut sie gegen einen Hypervektor, den man in der Hand hat, unbinden. Antworten werden weiterhin symbolisch geprüft, sie sind also nie falsch, nur früher oder später gefunden. Das ist derselbe Zug wie bei Neural-Guided miniKanren, mit HDC als Führung.

B ist der sicherere erste Schritt. Es hält die Regel dieses Forks, dass Antworten nie stillschweigend falsch sind, weil HDC nur die Reihenfolge bestimmt. A ändert die Semantik: Gleichheit wird zu Ähnlichkeit über einer Schwelle, und die ist nicht transitiv. Aus a ≈ b und b ≈ c folgt nicht a ≈ c, also kann sie nicht die Äquivalenz sein, die eine Substitution braucht. A braucht einen eigenen Begriff von Antwort, etwa Antworten, die ungefähr wahr sind, mit einer Konfidenz dazu.

Eine offene Map (lmap {:a 1} | r) und ein Record-Hypervektor mit unbekanntem Rest haben dieselbe Form: bekannte Bindings plus ein Summand, den man noch nicht identifiziert hat. In HDC zeigt sich der Rest als Rauschen, wenn man einen bekannten Key unbindet. Der Lacks-Constraint ("r hat kein :a") wird zu "r mit :a unbinden ergibt nichts, das einem Codebook-Eintrag nahe ist": eine probabilistische Abwesenheit.

Der Preis ist die Kapazität. Ein Bundle aus n Elementen in D Dimensionen liefert Elemente nur zuverlässig zurück, solange n klein gegenüber D ist. "Der Rest enthält irgendetwas" ist also nicht gratis, so wie es eine ungebundene Variable ist.

Die verschränkte Suche von miniKanren ist fair, aber blind: Sie nimmt Zweige der Reihe nach. HDC gibt jedem Zweig eine Bewertung. Ein relationales HDC-Framework würde Antwort-Streams nach Bewertung geordnet wollen, Best-First statt Breadth-First, mit der Vollständigkeit von miniKanren als Rückfallebene: Schlecht bewertete Zweige werden zurückgestellt, nie verworfen.

• Welche Familie? MAP oder BSC, mit exaktem selbstinversem Binding, machen bindo exakt. HRR und FHRR liefern kontinuierliche Ähnlichkeit; die Inverse von HRR ist approximativ, die von FHRR (die komplexe Konjugation) exakt, aber dessen Binding ist nicht selbstinvers.
• Codebooks als Relationen. Ein Codebook ist eine Faktentabelle: eine pldb-Relation von Symbolen zu Hypervektoren. Geseedet, damit Wiederholungen reproduzierbar sind.
• Lernen. Die Frage, welches Codebook diese Kodierungen passend macht, ist relationales Lernen, rückwärts ausgeführt. Gehört das dazu, oder setzt das Framework feste Codebooks voraus?
• Exakte vs. approximative Antworten. Design B hält Antworten exakt. Design A braucht abgestufte Antworten. Passen beide in einen run?
• Wer ordnet die Suche? Design B kann Zweige innerhalb eines Goals ordnen, zum Beispiel indem es die Alternativen eines conde nach Bewertung sortiert. Eine globale Best-First-Suche über alle offenen Zweige braucht den Suchbaum als Daten. In core.logic besteht der Stream aus Closures, die eine Führung von außen nicht inspizieren kann, und Neural-Guided miniKanren stieß auf dieselbe Einschränkung.
• Wo Resonator-Netzwerke sitzen. Als Constraint-Domäne in core.logic, als eigener Stream oder als externer Solver hinter einem einzigen Goal?

• T. A. Plate, Holographic Reduced Representations, CSLI Publications, 2003.
• P. Kanerva, "Hyperdimensional Computing: An Introduction to Computing in Distributed Representation with High-Dimensional Random Vectors", Cognitive Computation 1, 2009.
• R. W. Gayler, "Vector Symbolic Architectures answer Jackendoff's challenges for cognitive neuroscience", ICCS/ASCS Joint International Conference on Cognitive Science, 2003.
• E. P. Frady, S. J. Kent, B. A. Olshausen, F. T. Sommer, "Resonator Networks, 1: An Efficient Solution for Factoring High-Dimensional, Distributed Representations of Data Structures", Neural Computation 32(12), 2020.
• D. Kleyko, D. A. Rachkovskij, E. Osipov, A. Rahimi, "A Survey on Hyperdimensional Computing aka Vector Symbolic Architectures", ACM Computing Surveys, 2022/2023 (zwei Teile).

Generiert von Claude im Auftrag von Benjamin Schwerdtner.