論文の概要: On the Complexity of Neural Computation in Superposition
- arxiv url: http://arxiv.org/abs/2409.15318v1
- Date: Thu, 5 Sep 2024 18:58:59 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-06 20:05:48.747520
- Title: On the Complexity of Neural Computation in Superposition
- Title（参考訳）: 重ね合わせにおけるニューラル計算の複雑さについて
- Authors: Micah Adler, Nir Shavit,
- Abstract要約: ニューラルネットワークの理解の最近の進歩は、重畳が大規模ネットワークの計算効率の根底にある重要なメカニズムであることを示唆している。
ペアワイズのような論理演算は、$O(sqrtm' log m')$ ニューロンと$O(m' log2 m')$パラメータで計算できる。
本研究は,ニューラルネットワークの解釈可能性研究における複雑性理論手法の活用の道を開くものである。
- 参考スコア（独自算出の注目度）: 3.9803704378699103
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Recent advances in the understanding of neural networks suggest that superposition, the ability of a single neuron to represent multiple features simultaneously, is a key mechanism underlying the computational efficiency of large-scale networks. This paper explores the theoretical foundations of computing in superposition, focusing on explicit, provably correct algorithms and their efficiency. We present the first lower bounds showing that for a broad class of problems, including permutations and pairwise logical operations, a neural network computing in superposition requires at least $\Omega(m' \log m')$ parameters and $\Omega(\sqrt{m' \log m'})$ neurons, where $m'$ is the number of output features being computed. This implies that any ``lottery ticket'' sparse sub-network must have at least $\Omega(m' \log m')$ parameters no matter what the initial dense network size. Conversely, we show a nearly tight upper bound: logical operations like pairwise AND can be computed using $O(\sqrt{m'} \log m')$ neurons and $O(m' \log^2 m')$ parameters. There is thus an exponential gap between computing in superposition, the subject of this work, and representing features in superposition, which can require as little as $O(\log m'$) neurons based on the Johnson-Lindenstrauss Lemma. Our hope is that our results open a path for using complexity theoretic techniques in neural network interpretability research.
- Abstract（参考訳）: ニューラルネットワークの理解の最近の進歩は、単一のニューロンが複数の特徴を同時に表現する能力である重ね合わせが、大規模ネットワークの計算効率の根底にある重要なメカニズムであることを示唆している。
本稿では,計算の重ね合わせにおける理論的基礎を考察し,明示的で証明可能なアルゴリズムとその効率性に着目した。
置換やペア論理演算を含む幅広い問題に対して、重ね合わせのニューラルネットワーク計算には少なくとも$\Omega(m' \log m')$パラメータと$\Omega(\sqrt{m' \log m'})$ニューロンが必要である。
つまり、'lottery ticket'' のスパースサブネットワークは、初期密なネットワークサイズが何であれ、少なくとも$\Omega(m' \log m')$パラメータを持つ必要がある。
逆に、ペアワイズのような論理演算と$O(\sqrt{m'} \log m')$ニューロンと$O(m' \log^2 m')$パラメータで計算できる。
したがって、重ね合わせにおける計算、この研究の主題、および重ね合わせにおける特徴を表現するための指数的なギャップがあり、ジョンソン-リンデンシュトラウス・レムマに基づく$O(\log m'$)ニューロンしか必要としない。
私たちの期待は、ニューラルネットワークの解釈可能性研究に複雑性理論技術を使うための道を開くことです。
関連論文リスト
- Approximation of the Proximal Operator of the $\ell_\infty$ Norm Using a Neural Network [1.7265013728931]
ニューラルネットワークを用いて,$textbfprox_alphacdot||infty(mathbfx)$を近似する。
ネットワークの新たな側面は、特徴選択プロセスにより、様々な長さのベクトルを受け入れることができることである。
特徴選択を使用しない「バニラニューラルネットワーク」よりも優れていることを示す。
論文 参考訳（メタデータ） (2024-08-20T22:12:30Z) - Mathematical Models of Computation in Superposition [0.9374652839580183]
重ね合わせは、現在のAIシステムを機械的に解釈する上で深刻な課題となる。
重ね合わせにおけるエンフン計算の数学的モデルを提案し, 重ね合わせはタスクを効率的に遂行するのに有効である。
我々は、重ね合わせで計算を実装するニューラルネットワークを解釈する研究の潜在的な応用について、結論付けている。
論文 参考訳（メタデータ） (2024-08-10T06:11:48Z) - Matching the Statistical Query Lower Bound for k-sparse Parity Problems with Stochastic Gradient Descent [83.85536329832722]
勾配勾配降下(SGD)は,$d$次元ハイパーキューブ上の$k$パリティ問題を効率的に解くことができることを示す。
次に、SGDでトレーニングされたニューラルネットワークがどのようにして、小さな統計的エラーで$k$-parityの問題を解決するかを実証する。
論文 参考訳（メタデータ） (2024-04-18T17:57:53Z) - Memorization Capacity of Neural Networks with Conditional Computation [14.048989759890475]
我々は,$O(sqrtn)$ニューロンを用いたニューラルネットワークを用いて,$n$の入力出力関係の集合を記憶できることを実証した。
条件付きReLUネットワークを用いて,入力あたりのO(log n)$演算のみを用いて同じタスクを実現できることを示す。
論文 参考訳（メタデータ） (2023-03-20T16:33:17Z) - Generalization and Stability of Interpolating Neural Networks with
Minimal Width [37.908159361149835]
補間系における勾配によって訓練された浅層ニューラルネットワークの一般化と最適化について検討する。
トレーニング損失数は$m=Omega(log4 (n))$ニューロンとニューロンを最小化する。
m=Omega(log4 (n))$のニューロンと$Tapprox n$で、テスト損失のトレーニングを$tildeO (1/)$に制限します。
論文 参考訳（メタデータ） (2023-02-18T05:06:15Z) - On the Optimal Memorization Power of ReLU Neural Networks [53.15475693468925]
フィードフォワードReLUニューラルネットワークは、軽度の分離可能性仮定を満たす任意のN$ポイントを記憶することができることを示す。
このような大きなビットの複雑性を持つことは、サブ線形数のパラメータを記憶するのに必要であり、十分であることを示す。
論文 参考訳（メタデータ） (2021-10-07T05:25:23Z) - Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。
次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。
頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
論文 参考訳（メタデータ） (2021-07-22T14:25:16Z) - ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation [5.35599092568615]
本稿では,線形整流ユニットを用いたニューラルネットワークのパワーについて検討する。
我々は,2つの基本最適化問題を$mathcalO(m2n2)$のニューラルネットワークで解くことができることを示した。
論文 参考訳（メタデータ） (2021-02-12T17:23:34Z) - Size and Depth Separation in Approximating Natural Functions with Neural
Networks [52.73592689730044]
本稿では,ReLUネットワークを用いた自然関数の近似におけるサイズと深さの利点を示す。
我々は、そのような結果が$O(d)$を超えることを証明するための複雑性理論上の障壁を示す。
また、サイズ$O(d)$のネットワークで近似できる明示的な自然関数も示している。
論文 参考訳（メタデータ） (2021-01-30T21:30:11Z) - A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。
我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。
次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
論文 参考訳（メタデータ） (2020-06-02T16:38:36Z) - On the Modularity of Hypernetworks [103.1147622394852]
構造化対象関数の場合、ハイパーネットワークにおけるトレーニング可能なパラメータの総数は、標準ニューラルネットワークのトレーニング可能なパラメータの数や埋め込み法よりも桁違いに小さいことを示す。
論文 参考訳（メタデータ） (2020-02-23T22:51:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。