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

技術要約：FactorHD

問題提起
ニューロ・シンボリック人工知能（neuro-symbolic AI）は、論理的な分析と推論を行うためにハイパーディメンショナル・コンピューティング（HDC）に依存しています。既存のHDCモデルは、バインディング（結合）・バンブリング（集約）構造を用いて単純なクラス・インスタンス関係やクラス・クラス関係を効果的に表現できますが、複数のオブジェクトが異なるレベルのクラスやサブクラスに関連付けられる、より複雑なクラス・サブクラス関係（例：動物 $\to$ 犬 $\to$ スパニエル $\to$ Fido）の表現には苦慮しています。

現在のモデルは、この領域において主に3つの課題に直面しています：

1. 重ね合わせの破綻（Superposition Catastrophe）： 複数のオブジェクトを表現する際、サブクラスの項目が混ざり合い、区別がつかなくなります。
2. 「2」の問題（The Problem of 2）： 複数の同一オブジェクトを同時に表現すると、情報の損失が発生します。
3. 因数分解の非効率性： 階層（クラスおよびサブクラスの数）の規模が拡大するにつれ、既存のモデルは徹底的な反復的なアンバインディング（解結合）操作と類似度測定を必要とします。これにより、高い計算コストと時間計算量（しばしば $O(N^2M)$ を超える）が発生し、大規模なシナリオへの適用が困難になります。さらに、現在のモデルは、オブジェクトの特定のサブクラス集合のみに関心がある場合であっても、オブジェクトの完全な因数分解を要求することがよくあります。

手法：FactorHD
著者らは、複雑なクラス・サブクラス階層を効率的に表現および因数分解するために設計された新しいHDCモデルであるFactorHDを提案しています。この手法は、2つのコアコンポーネントで構成されています。

1. 記号的エンコーディング（バンブリング・バインディング・バンブリング）：

   • FactorHDは、項目を接続するための追加の記憶節（memorization clause）（冗長なクラスラベル、LABELと表記）を埋め込む記号的エンコーディング手法を導入しています。
   • 構造はバンブリング・バインディング・バンブリングの形式に従います：
     • 同一クラスに属するサブクラスレベルは、バンブリング（加算）によって結合されます。
     • 異なるクラスは、バインディング（乗算）によってリンクされます。
     • 異なるオブジェクトは、バンブリングによって接続されます。
   • 決定的なのは、特定のクラス項目がオブジェクトに関連付けられていない場合でも、モデルはそのクラスラベルを保持し、グローバルなNULL HVとバンブリングすることです。これにより、従来のモデルに必要であった「オブジェクト内にどのクラスが存在するか」という事前知識の必要性が排除されます。

2. 効率的な因数分解アルゴロリズム：

   • このアルゴリズムは、冗長なクラスを選択的に排除することで、徹底的な探索を回避します。選択されていないクラスラベルをアンバインドし、その結果得られたベクトルとターゲットクラスのサブクラス項目の間の類似度を計算します。
   • 単一オブジェクト： 最も類似度が高い項目が選択され、プロセスは後続のサブクラスレベルに対して繰り返されます。
   • 複数オブジェクト： 特定のレベルにおいて、定義された**閾値類似度（TH）**を超えるすべてのサブクラス項目を特定します。その後、これらの候補を選択的にバインドして組み合わせを形成します。組み合わせの類似度がターゲットHVに対してTHを超えている場合、そのオブジェクトは確定されます。
   • 閾値の選択： 最適なTH値（$TH^*$）は、HV次元（$D$）、オブジェクト数（$N$）、およびファクター数（$F$）に基づいて決定されます。論文では以下の適合式を提供しています：$TH^* = 0.001(10^4 + 2N - 15F - 0.001D - \log(M))$。

主な貢献

• 新しい表現形式： FactorHDは、冗長なクラスラベルを利用して情報を保持することにより、重ね合わせの破綻や「2」の問題に陥ることなく、マルチレベルのサブクラス階層を持つ複数のオブジェクトを表現することをサポートします。
• 効率的なアルゴリズム： 提案された因数分解アルゴリズムは、計算量を約 $O(NM)$**（$N$はオブジェクト数、$M$ はクラスあたりのサブクラス項目数）に大幅に削減します（従来のメソッドの指数関数的または二次的な計算量と比較して）。これは、システム全体を処理することなく、関心のある特定のサブクラスを抽出できる部分的な因数分解**を可能にします。
• スケーラビabilityと精度： モデルは、問題の規模が拡大しても高い因数分解精度を維持し、既存のC-C（クラス・クラス）およびC-I（クラス・インスタンス）モデルの限界を克服します。

実験結果
評価は、合成表現（Rep 1, 2, 3）および、特徴抽出のためにResNet-18ニューラルネットワークと統合された実用的なデータセット（RAVEN, Cifar-10, Cifar-100）を用いて行われました。

• 高速化： FactorHDは、表現サイズが$10^9$の場合、既存のHDCモデル（resonator networkやIMC factorizerなど）と比較して5667倍の高速化を達成しました。サイズが$10^6$の場合、高速化は約18.5倍です。
• 合成データにおける精度： FactorHDは、低いHV次元においても99%以上の因数分解精度を維持しますが、ベースラインモデル（例：resonator network）は問題の規模が増大するにつれて失敗します。
• 実世界のデータセット：
  • Cifar-10データセットにおいて、ResNet-18と統合されたFactorHDは**92.48%**の因数分解精度を達成しました。
  • Cifar-100において、本モデルは標準的なニューラル分類タスクと比較して極めて低い損失（Cifar-10で精度低下 < 3%）で高い精度を示しました。
  • RAVENデータセットにおいて、モデルは$D=1000$においてほとんどのパターンで90%以上の精度を達成しました。

意義
本論文は、FactorHDがニューロ・シンボリックAIにおける「重ね合わせの破綻」および「2」の問題という根本的な限界を克服することを主張しています。効率的な部分因数分解を可能にし、複雑な階層構造を扱うことで、FactorHDはマルチオブジェクト推論を含むより幅広いシナリオへのHDCの適用性を拡張します。このモデルは、ニューロ・シンボリックシステムが、従来のHDC設計を妨げてきた徹底的な反復プロセスに依存することなく、高い計算効率と精度を達成できることを示しています。