Abstract
密連想メモリ（DAM）は、より高次の相互作用によってホップフィールドネットワークを一般化し、適切なパターン分離条件の下で記憶容量が O(N^{n-1}) とスケールすることを実現します。既存の動力学的解析は主として、ランダムにサンプリングされたパターンを用いた熱力学極限 N\to\infty を調べているため、有限サイズでの保証や明示的な収束率は提供しません。
本論文では、DAM想起ダイナミクスに対するアルゴリズム的解析を開発し、明示的で検証可能なパターン条件の下で有限-N の保証を導きます。分離仮定および高い負荷の下での有界干渉条件のもとで、非同期想起ダイナミクスが幾何学的に収束することを証明します。これにより、軌道が引き込み領域に入った後は O(\log N) の収束時間が成り立つことが示されます。さらに、1スイープあたりに許容できる破損ビット数を定量化する明示的なマージン条件によって表される、敵対的ロバスト性の境界を確立します。また、最悪の場合において記憶容量が多項対数因子までの形で
\Theta(N^{n-1}) にスケールする容量保証を導出し、さらにランダムなパターン集合に対して古典的な
\Theta(N^{n-1}) のスケーリングを回復することを示します。最後に、DAM想起ダイナミクスはポテンシャルゲームとして解釈でき、非同期更新のもとで純粋ナッシュ均衡への収束が保証されることを示します。
完全な証明は付録に掲載され、また予備的な実験として、予測される収束、ロバスト性、容量スケーリングの挙動を示します。
