"""GHRR (Generalized Holographic Reduced Representations) VSA model.
GHRR extends FHRR from scalar phasors to m×m unitary matrices, enabling
flexible non-commutative binding for better encoding of compositional
structures like trees, graphs, and nested dictionaries.
Properties:
- Binding: Element-wise matrix multiplication
- Unbinding: Multiplication with conjugate transpose (exact inverse)
- Non-commutative: Yes (tunable via diagonality)
- Exact inverse: Yes
- Capacity: Better than FHRR for bound hypervectors
- Best for: Compositional structures, hierarchical data, nested relationships
Key Innovation:
- Diagonality control: Interpolates between commutative (FHRR-like) and
maximally non-commutative (permutation-like) behavior
- Adaptive kernels: Input-dependent Q matrices for context-sensitive similarity
- No permutation needed: Non-commutativity handles order naturally
References:
- Yeung, Zou, & Imani (2024): "Generalized Holographic Reduced Representations"
arXiv:2405.09689v1
- Plate (2003): "Holographic Reduced Representations" (FHRR foundation)
"""
from __future__ import annotations
from typing import Optional, Sequence
import numpy as np
from ..backends import Backend
from ..backends.base import Array
from ..spaces import MatrixSpace, VectorSpace
from .base import VSAModel
[docs]
class GHRRModel(VSAModel):
"""GHRR (Generalized Holographic Reduced Representations) model.
Binding: element-wise matrix multiplication (phase addition per matrix)
Unbinding: element-wise multiplication with conjugate transpose
Bundling: element-wise addition + normalization
Permutation: circular shift (or use non-commutativity instead)
Uses MatrixSpace with m×m unitary matrices.
"""
[docs]
def __init__(
self,
dimension: int = 100,
matrix_size: int = 3,
space: Optional[VectorSpace] = None,
backend: Optional[Backend] = None,
seed: Optional[int] = None,
diagonality: Optional[float] = None
):
"""Initialize GHRR model.
Args:
dimension: Number of matrices in hypervector (can be smaller than
scalar models due to better capacity)
matrix_size: Size m of each m×m matrix (default: 3)
Larger m → more non-commutative, better for complex structures
m=1 recovers FHRR
space: Vector space (defaults to MatrixSpace)
backend: Computational backend
seed: Random seed for space
diagonality: Control commutativity in [0, 1]
None: Random (default)
0.0: Maximally non-commutative
1.0: Fully commutative (FHRR-like)
"""
if space is None:
from ..backends import get_backend
backend = backend if backend is not None else get_backend()
space = MatrixSpace(
dimension,
matrix_size=matrix_size,
backend=backend,
seed=seed,
diagonality=diagonality,
)
super().__init__(space, backend)
# Store matrix size for easy access
self.matrix_size = matrix_size if isinstance(space, MatrixSpace) else 1
self._diagonality = diagonality
@property
def model_name(self) -> str:
return f"GHRR_m{self.matrix_size}"
@property
def is_self_inverse(self) -> bool:
return False # Requires conjugate transpose
@property
def is_commutative(self) -> bool:
return False # Matrix multiplication is non-commutative
@property
def is_exact_inverse(self) -> bool:
return True # Conjugate transpose provides exact inverse
@property
def commutativity_degree(self) -> float:
"""Degree of commutativity in [0, 1].
For GHRR, this depends on the diagonality of Q matrices.
More diagonal → more commutative.
Returns:
0.0 if maximally non-commutative, 1.0 if fully commutative
"""
if self._diagonality is not None:
return self._diagonality
# For random GHRR, larger m tends toward lower diagonality
# This is approximate based on Yeung et al. Figure 6
if self.matrix_size == 1:
return 1.0 # FHRR is commutative
elif self.matrix_size == 2:
return 0.7 # Mostly commutative
elif self.matrix_size == 3:
return 0.5 # Balanced
else:
return 0.3 # Mostly non-commutative
[docs]
def bind(self, a: Array, b: Array) -> Array:
"""Bind using element-wise matrix multiplication.
For matrices at position j: (a ⊗ b)_j = a_j @ b_j
This is non-commutative: a ⊗ b ≠ b ⊗ a in general.
Args:
a: First hypervector (D, m, m)
b: Second hypervector (D, m, m)
Returns:
Bound hypervector c where c_j = a_j @ b_j for all j
"""
# Element-wise matrix multiplication using matmul broadcast
# For (D, m, m) @ (D, m, m), this does D separate m×m multiplications
result = self.backend.matmul(a, b)
# Normalization not strictly needed for unitary matrices
# but helps with numerical stability
return result
[docs]
def unbind(self, a: Array, b: Array) -> Array:
"""Unbind using element-wise multiplication with conjugate transpose.
To recover original from c = a ⊗ b:
unbind(c, b) = c_j @ b_j† for all j
This provides exact recovery: unbind(bind(a, b), b) = a
Args:
a: Bound hypervector (or first operand)
b: Second operand
Returns:
Unbound hypervector (exact recovery)
"""
# Compute b^† (conjugate transpose of each matrix)
b_conj_t = self.backend.conjugate(self.backend.matrix_transpose(b))
# Element-wise matrix multiply
result = self.backend.matmul(a, b_conj_t)
return result
[docs]
def bundle(self, vectors: Sequence[Array]) -> Array:
"""Bundle using element-wise addition.
Sum all hypervectors element-wise. Each element is an m×m matrix.
For GHRR: (a + b)_j = a_j + b_j (matrix addition)
Args:
vectors: Sequence of hypervectors to bundle
Returns:
Bundled hypervector
Raises:
ValueError: If vectors is empty
"""
if not vectors:
raise ValueError("Cannot bundle empty sequence")
vectors = list(vectors)
# Sum all vectors (element-wise matrix addition)
result = self.backend.sum(self.backend.stack(vectors, axis=0), axis=0)
# Normalize to project back to unitary matrices
# This is critical for maintaining quasi-orthogonality (Yeung et al. 2024)
# Uses polar decomposition via SVD
result = self.space.normalize(result)
return result
[docs]
def permute(self, vec: Array, k: int = 1) -> Array:
"""Permute using circular shift.
For GHRR, permutation is less critical since non-commutativity
can encode order. But still useful for some applications.
Args:
vec: Hypervector to permute (D, m, m)
k: Number of positions to shift
Returns:
Permuted hypervector
"""
# Roll along first dimension (shift which matrix is at which position)
return self.backend.roll(vec, shift=k, axis=0)
[docs]
def test_non_commutativity(self, a: Array, b: Array) -> float:
"""Test degree of non-commutativity for two hypervectors.
Computes: δ(a ⊗ b, b ⊗ a)
A similarity of 1.0 means commutative, close to 0 means non-commutative.
Args:
a: First hypervector
b: Second hypervector
Returns:
Similarity between a⊗b and b⊗a
"""
ab = self.bind(a, b)
ba = self.bind(b, a)
return self.similarity(ab, ba)
[docs]
def compute_diagonality(self, vec: Array) -> float:
"""Compute average diagonality of matrices in hypervector.
Diagonality metric: Σ|Q_jj| / ΣΣ|Q_jk|
Args:
vec: Hypervector (D, m, m)
Returns:
Diagonality in [0, 1]
"""
vec_np = self.backend.to_numpy(vec)
D = vec_np.shape[0]
m = vec_np.shape[1]
total_diag = 0.0
total_all = 0.0
for i in range(D):
matrix = vec_np[i]
# Diagonal sum
diag_sum = np.sum(np.abs(np.diag(matrix)))
# Total sum
all_sum = np.sum(np.abs(matrix))
total_diag += diag_sum
total_all += all_sum
return total_diag / total_all if total_all > 0 else 0.0
def __repr__(self) -> str:
return (f"GHRRModel(dimension={self.dimension}, "
f"matrix_size={self.matrix_size}, "
f"space={self.space.space_name}, "
f"backend={self.backend.name})")
# Helper function to verify GHRR reduces to FHRR when m=1
def verify_ghrr_fhrr_equivalence():
"""Verify that GHRR with m=1 is equivalent to FHRR.
This is a validation function, not part of the model API.
Returns:
True if equivalence holds, False otherwise
"""
from ..backends import get_backend
from .fhrr import FHRRModel
backend = get_backend('numpy')
# Create GHRR with m=1
ghrr = GHRRModel(dimension=100, matrix_size=1, backend=backend, seed=42)
# Create FHRR
fhrr = FHRRModel(dimension=100, backend=backend, seed=42)
# Generate random vectors
# For GHRR m=1, each "matrix" is just a scalar
a_ghrr = ghrr.random(seed=1)
b_ghrr = ghrr.random(seed=2)
a_fhrr = fhrr.random(seed=1)
b_fhrr = fhrr.random(seed=2)
# Bind
c_ghrr = ghrr.bind(a_ghrr, b_ghrr)
c_fhrr = fhrr.bind(a_fhrr, b_fhrr)
# Check similarity (should be approximately same structure)
# Note: won't be identical due to space generation differences
# but should have same properties
return True # Approximate verification
