FactorHD: A Hyperdimensional Computing Model for Multi-Object Multi-Class Representation and Factorization

Technical Summary: FactorHD

Problem Statement
Neuro-symbolic artificial intelligence (neuro-symbolic AI) relies on Hyperdimensional Computing (HDC) to perform logical analysis and reasoning. While existing HDC models effectively represent simple class-instance or class-class relations using binding-bundling structures, they struggle with the more complex class-subclass relation, where multiple objects associate with different levels of classes and subclasses (e.g., animals $\to$ dogs $\to$ spaniels $\to$ Fido).

Current models face three primary challenges in this domain:

1. Superposition Catastrophe: When representing multiple objects, subclass items become mixed and indistinguishable.
2. The Problem of 2: Representing several identical objects simultaneously leads to information loss.
3. Inefficiency in Factorization: As the hierarchy size (number of classes and subclasses) scales, existing models require exhaustive iterative unbinding operations and similarity measurements. This results in high computational costs and time complexity (often exceeding $O(N^2M)$), making them unsuitable for large-scale scenarios. Furthermore, current models often require complete factorization of an object even when only a subset of subclasses is of interest.

Methodology: FactorHD
The authors propose FactorHD, a novel HDC model designed to represent and factorize complex class-subclass hierarchies efficiently. The methodology consists of two core components:

1. Symbolic Encoding (Bundling-Binding-Bundling):

   • FactorHD introduces a symbolic encoding method that embeds an extra memorization clause (a redundant class label, denoted as LABEL) to connect items.
   • The structure follows a bundling-binding-bundling form:
     • Subclass levels belonging to the same class are combined via bundling (addition).
     • Different classes are linked via binding (multiplication).
     • Different objects are connected via bundling.
   • Crucially, even if a specific class item is not associated with an object, the model reserves its class label and bundles it with a global NULL HV. This eliminates the need for foreknowledge of which classes are present in an object, a requirement for previous models.

2. Efficient Factorization Algorithm:

   • The algorithm avoids exhaustive search by selectively eliminating redundant classes. It unbinds unselected class labels and computes similarity between the resulting vector and the subclass items of the target class.
   • Single Object: The item with the highest similarity is selected, and the process repeats for subsequent subclass levels.
   • Multiple Objects: The algorithm identifies all subclass items at a specific level that exceed a predefined threshold similarity (TH). It then selectively binds these candidates to form combinations. If a combination's similarity to the target HV exceeds TH, the object is confirmed.
   • Threshold Selection: The optimal TH value ($TH^*$) is determined based on HV dimension ($D$), the number of objects ($N$), and the number of factors ($F$). The paper provides a fitting formula: $TH^* = 0.001(10^4 + 2N - 15F - 0.001D - \log(M))$.

Key Contributions

• Novel Representation: FactorHD supports the representation of multiple objects with multi-level subclass hierarchies without suffering from superposition catastrophe or the problem of 2, utilizing a redundant class label to preserve information.
• Efficient Algorithm: The proposed factorization algorithm significantly reduces computational complexity to approximately $O(NM)$ (where $N$ is the number of objects and $M$ is the number of subclass items per class), compared to the exponential or quadratic complexity of prior methods. It enables partial factorization, allowing the system to extract specific subclasses of interest without processing the entire hierarchy.
• Scalability and Accuracy: The model maintains high factorization accuracy even as problem sizes scale, overcoming the limitations of existing C-C (Class-Class) and C-I (Class-Instance) models.

Experimental Results
Evaluations were conducted on synthetic representations (Rep 1, 2, and 3) and practical datasets (RAVEN, Cifar-10, Cifar-100) integrated with a ResNet-18 neural network for feature extraction.

• Speedup: FactorHD achieves a 5667$\times$ speedup at a representation size of $10^9$ compared to existing HDC models (such as the resonator network and IMC factorizer). At a size of $10^6$, the speedup is approximately 18.5$\times$.
• Accuracy on Synthetic Data: FactorHD maintains factorization accuracy above 99% even at lower HV dimensions, whereas baseline models (e.g., resonator network) fail as problem sizes increase.
• Real-World Datasets:
  • On the Cifar-10 dataset, FactorHD integrated with ResNet-18 achieved 92.48% factorization accuracy.
  • On Cifar-100, the model demonstrated high accuracy with minimal loss compared to standard neural classification tasks (accuracy loss < 3% for Cifar-10).
  • On the RAVEN dataset, the model achieved over 90% accuracy for most patterns with $D=1000$.

Significance
The paper claims that FactorHD overcomes the fundamental limitations of "superposition catastrophe" and "the problem of 2" in neuro-symbolic AI. By enabling efficient partial factorization and handling complex hierarchical structures, FactorHD extends the applicability of HDC to broader scenarios involving multi-object reasoning. The model demonstrates that neuro-symbolic systems can achieve high computational efficiency and accuracy without relying on the exhaustive, iterative processes that hinder previous HDC designs.