論文の概要: On the Expressive Power of Modern Hopfield Networks
- arxiv url: http://arxiv.org/abs/2412.05562v1
- Date: Sat, 07 Dec 2024 06:52:41 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-10 14:59:04.003167
- Title: On the Expressive Power of Modern Hopfield Networks
- Title(参考訳): 近代ホップフィールドネットワークの表現力について
- Authors: Xiaoyu Li, Yuanpeng Li, Yingyu Liang, Zhenmei Shi, Zhao Song,
- Abstract要約: 現代のホップフィールドネットワーク(MHN)は、ディープラーニングの強力なツールとして登場した。
MHN は $mathsfDLOGTIME$-uniform $mathsfTC0$ であることを示す。
これらの結果は、現代のホップフィールドネットワークの表現力の限界を示している。
- 参考スコア(独自算出の注目度): 25.981970820634427
- License:
- Abstract: Modern Hopfield networks (MHNs) have emerged as powerful tools in deep learning, capable of replacing components such as pooling layers, LSTMs, and attention mechanisms. Recent advancements have enhanced their storage capacity, retrieval speed, and error rates. However, the fundamental limits of their computational expressiveness remain unexplored. Understanding the expressive power of MHNs is crucial for optimizing their integration into deep learning architectures. In this work, we establish rigorous theoretical bounds on the computational capabilities of MHNs using circuit complexity theory. Our key contribution is that we show that MHNs are $\mathsf{DLOGTIME}$-uniform $\mathsf{TC}^0$. Hence, unless $\mathsf{TC}^0 = \mathsf{NC}^1$, a $\mathrm{poly}(n)$-precision modern Hopfield networks with a constant number of layers and $O(n)$ hidden dimension cannot solve $\mathsf{NC}^1$-hard problems such as the undirected graph connectivity problem and the tree isomorphism problem. We also extended our results to Kernelized Hopfield Networks. These results demonstrate the limitation in the expressive power of the modern Hopfield networks. Moreover, Our theoretical analysis provides insights to guide the development of new Hopfield-based architectures.
- Abstract(参考訳): 現代のホップフィールドネットワーク(MHN)はディープラーニングにおいて強力なツールとして登場し、プール層やLSTM、アテンション機構などのコンポーネントを置き換えることができる。
近年の進歩により、ストレージ容量、検索速度、エラー率が向上している。
しかし、その計算表現性の基本的な限界は未解明のままである。
MHNの表現力を理解することは、ディープラーニングアーキテクチャへの統合を最適化するために重要である。
本研究では,回路複雑性理論を用いて,MHNの計算能力に関する厳密な理論的境界を確立する。
我々の重要な貢献は、MHNsが$\mathsf{DLOGTIME}$-uniform $\mathsf{TC}^0$であることを示すことである。
したがって、$\mathsf{TC}^0 = \mathsf{NC}^1$, a $\mathrm{poly}(n)$-precision Modern Hopfield network with a constant number of layer and $O(n)$ hidden dimension cannot solve $\mathsf{NC}^1$-hard problem such as the undirected graph connection problem and the tree isomorphism problem。
結果も Kernelized Hopfield Networks に拡張しました。
これらの結果は、現代のホップフィールドネットワークの表現力の限界を示している。
さらに、我々の理論分析は、新しいホップフィールドアーキテクチャの開発を導くための洞察を提供する。
関連論文リスト
- On the Computational Capability of Graph Neural Networks: A Circuit Complexity Bound Perspective [28.497567290882355]
グラフニューラルネットワーク(GNN)は、リレーショナルデータに対する学習と推論の標準的なアプローチとなっている。
本稿では,回路複雑性のレンズによるGNNの計算限界について検討する。
具体的には、共通GNNアーキテクチャの回路複雑性を分析し、定数層、線形またはサブ線形埋め込みサイズ、精度の制約の下で、GNNはグラフ接続やグラフ同型といった重要な問題を解くことができないことを証明している。
論文 参考訳(メタデータ) (2025-01-11T05:54:10Z) - Theoretical Constraints on the Expressive Power of $\mathsf{RoPE}$-based Tensor Attention Transformers [23.991344681741058]
本研究では, アテンションと$mathsfRoPE$-based Attentionの回路複雑性を分析し, 固定メンバシップ問題や$(A_F,r)*$クロージャ問題を解くことができないことを示す。
これらの結果は,経験的性能と注意の理論的制約と$mathsfRoPE$ベースの注意変換器とのギャップを浮き彫りにした。
論文 参考訳(メタデータ) (2024-12-23T23:26:07Z) - Towards characterizing the value of edge embeddings in Graph Neural Networks [47.01312576529216]
グラフニューラルネットワーク(GNN)は、グラフ上で定義された機械学習問題を解決する主要なアプローチである。
エッジの埋め込みを維持し、更新するアーキテクチャの利点について検討する。
論文 参考訳(メタデータ) (2024-10-13T15:03:24Z) - From Graphs to Qubits: A Critical Review of Quantum Graph Neural Networks [56.51893966016221]
量子グラフニューラルネットワーク(QGNN)は、量子コンピューティングとグラフニューラルネットワーク(GNN)の新たな融合を表す。
本稿では,QGNNの現状を批判的にレビューし,様々なアーキテクチャを探求する。
我々は、高エネルギー物理学、分子化学、ファイナンス、地球科学など多種多様な分野にまたがる応用について論じ、量子的優位性の可能性を強調した。
論文 参考訳(メタデータ) (2024-08-12T22:53:14Z) - Hamiltonian Mechanics of Feature Learning: Bottleneck Structure in Leaky ResNets [58.460298576330835]
我々は、ResNets(tildeLtoinfty$)とFully-Connected nets(tildeLtoinfty$)の間を補間するLeaky ResNetsを研究する。
無限深度極限において、'representation geodesics'の$A_p$:continuous paths in representation space(NeuralODEsに類似)を研究する。
この直感を利用して、以前の研究で見られるように、ボトルネック構造の出現を説明する。
論文 参考訳(メタデータ) (2024-05-27T18:15:05Z) - The Expressibility of Polynomial based Attention Scheme [8.517077915534932]
大規模言語モデル(LLM)は、私たちの日常生活の様々な側面を著しく改善しました。
変換器における注意の二次的複雑さは、長いテキストを処理するためにこれらのモデルをスケールアップする際の課題である。
本稿では,表現的注意力に関する理論的分析を行う。
論文 参考訳(メタデータ) (2023-10-30T22:16:18Z) - Projected Stochastic Gradient Descent with Quantum Annealed Binary Gradients [51.82488018573326]
重み付きニューラルネットワークのトレーニングに適した,新しいレイヤワイドオプティマイザであるQP-SBGDを提案する。
BNNは、深層学習モデルの計算要求とエネルギー消費を最小限の精度で削減する。
提案アルゴリズムは階層的に実装されており,リソース制限量子ハードウェア上での大規模ネットワークのトレーニングに適している。
論文 参考訳(メタデータ) (2023-10-23T17:32:38Z) - Deep Architecture Connectivity Matters for Its Convergence: A
Fine-Grained Analysis [94.64007376939735]
我々は、勾配降下訓練におけるディープニューラルネットワーク(DNN)の収束に対する接続パターンの影響を理論的に特徴づける。
接続パターンの単純なフィルタリングによって、評価対象のモデルの数を削減できることが示される。
論文 参考訳(メタデータ) (2022-05-11T17:43:54Z) - Unified Field Theory for Deep and Recurrent Neural Networks [56.735884560668985]
本稿では,再帰的ネットワークと深層ネットワークの両方に対する平均場理論の統一的,体系的な導出について述べる。
平均場理論への収束は、ディープネットワークよりもリカレントネットワークの方が典型的に遅い。
提案手法はガウス過程が1/n$の体系的展開の最下位次数であることを示す。
論文 参考訳(メタデータ) (2021-12-10T15:06:11Z) - Counting Substructures with Higher-Order Graph Neural Networks:
Possibility and Impossibility Results [58.277290855841976]
グラフニューラルネットワーク(GNN)の計算コストと表現力のトレードオフについて検討する。
新しいモデルでは、$k$のサブグラフをカウントでき、低次GNNの既知の制限を克服できることを示す。
いくつかの場合において、提案アルゴリズムは既存の高階$k$-GNNに比べて計算量を大幅に削減することができる。
論文 参考訳(メタデータ) (2020-12-06T03:42:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。