論文の概要: Compressed Computation: Dense Circuits in a Toy Model of the Universal-AND Problem

• arxiv url: http://arxiv.org/abs/2507.09816v1
• Date: Sun, 13 Jul 2025 22:18:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-15 18:48:24.058581
• Title: Compressed Computation: Dense Circuits in a Toy Model of the Universal-AND Problem
• Title（参考訳）: 圧縮計算:Universal-AND問題のトイモデルにおけるデンス回路
• Authors: Adam Newgas,
• Abstract要約: ニューラルネットワークは重ね合わせが可能で、次元よりも多くの特徴を表現できる。 最近の研究は、記憶ではなく計算の類似概念を考察し、理論的構成を提案している。 本研究は,すべての$mchoose 2$対のスパース入力の ANDを演算するUniversal-AND問題に対する玩具モデルについて検討する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Neural networks are capable of superposition -- representing more features than there are dimensions. Recent work considers the analogous concept for computation instead of storage, proposing theoretical constructions. But there has been little investigation into whether these circuits can be learned in practice. In this work, we investigate a toy model for the Universal-AND problem which computes the AND of all $m\choose 2$ pairs of $m$ sparse inputs. The hidden dimension that determines the number of non-linear activations is restricted to pressure the model to find a compute-efficient circuit, called compressed computation. We find that the training process finds a simple solution that does not correspond to theoretical constructions. It is fully dense -- every neuron contributes to every output. The solution circuit naturally scales with dimension, trading off error rates for neuron efficiency. It is similarly robust to changes in sparsity and other key parameters, and extends naturally to other boolean operations and boolean circuits. We explain the found solution in detail and compute why it is more efficient than the theoretical constructions at low sparsity. Our findings shed light on the types of circuits that models like to form and the flexibility of the superposition representation. This contributes to a broader understanding of network circuitry and interpretability.
• Abstract（参考訳）: ニューラルネットワークは重ね合わせが可能で、次元よりも多くの特徴を表現できる。 最近の研究は、記憶ではなく計算の類似概念を考察し、理論的構成を提案している。 しかし、これらの回路が実際に学習できるかどうかについては、ほとんど調査されていない。 本研究では,すべての$m\choose 2$対のスパース入力の AND を計算するUniversal-AND問題に対する玩具モデルについて検討する。 非線形のアクティベーション数を決定する隠された次元は、圧縮計算と呼ばれる計算効率の高い回路を見つけるためにモデルに圧力をかけるために制限される。 学習過程は理論的な構成と一致しない単純な解を見つける。 完全に密度が高く、全てのニューロンが全ての出力に寄与する。 解回路は次元に応じて自然にスケールし、ニューロン効率のためにエラー率をトレードオフする。 同様に、スパーシリティや他のキーパラメータの変化に対して堅牢であり、他のブール演算やブール回路に自然に拡張する。 得られた解を詳細に説明し、低空間での理論的構成よりも効率的である理由を計算する。 我々の発見は、モデルが生成する回路の種類と重ね合わせ表現の柔軟性に光を当てた。 これは、ネットワーク回路と解釈可能性のより広範な理解に寄与する。

関連論文リスト

• Learning to Add, Multiply, and Execute Algorithmic Instructions Exactly with Neural Networks [5.3800094588915375]
  無限幅限界における2層完全連結ネットワークのトレーニング力学について検討する。 このようなモデルの十分な大規模なアンサンブルが、高い確率で正確に実行するためにどのように訓練されるかを示す。 対数的に多くのトレーニングデータだけを用いて効率よく達成できることを示します。
  論文  参考訳（メタデータ） (2025-02-24T00:50:02Z)
• Finding Transformer Circuits with Edge Pruning [71.12127707678961]
  自動回路発見の効率的かつスケーラブルなソリューションとしてエッジプルーニングを提案する。 本手法は,従来の手法に比べてエッジ数の半分未満のGPT-2の回路を探索する。 その効率のおかげで、Edge PruningをCodeLlama-13Bにスケールしました。
  論文  参考訳（メタデータ） (2024-06-24T16:40:54Z)
• Robustness Verifcation in Neural Networks [0.0]
  ニューラルネットワーク計算における形式的検証問題について検討する。 1つの疑問は、ネットワークが有効な出力を計算するような有効な入力が存在するかどうかである。 半線形環境では,この問題が克服可能であることを示す。
  論文  参考訳（メタデータ） (2024-03-20T09:34:38Z)
• A Circuit Complexity Formulation of Algorithmic Information Theory [1.5483078145498086]
  インダクティブ推論のソロモノフ理論に着想を得て,回路複雑性に基づく先行モデルを提案する。 回路複雑性によって測定された単純な説明に対する帰納的バイアスがこの問題に適切であると主張する。
  論文  参考訳（メタデータ） (2023-06-25T01:30:37Z)
• Transformers Learn Shortcuts to Automata [52.015990420075944]
  低深度変換器は任意の有限状態オートマトンを計算できる。 我々は,$O(log T)$レイヤを持つ変換器が,長さ$T$の入力シーケンス上で,オートマトンを正確に再現可能であることを示す。 さらに、これらの解の脆性について検討し、潜在的な緩和を提案する。
  論文  参考訳（メタデータ） (2022-10-19T17:45:48Z)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。 ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
  論文  参考訳（メタデータ） (2022-07-07T08:04:15Z)
• The Separation Capacity of Random Neural Networks [78.25060223808936]
  標準ガウス重みと一様分布バイアスを持つ十分に大きな2層ReLUネットワークは、この問題を高い確率で解くことができることを示す。 我々は、相互複雑性という新しい概念の観点から、データの関連構造を定量化する。
  論文  参考訳（メタデータ） (2021-07-31T10:25:26Z)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  本研究は,統計的学習性を示すために近似ネットワークを必要とする統計有意(SM)近似の形式的定義を提案する。 回路とチューリングマシンの2つの機能クラスに対するSM近似について検討する。
  論文  参考訳（メタデータ） (2021-07-28T04:28:55Z)
• PAC-learning gains of Turing machines over circuits and neural networks [1.4502611532302039]
  私達は最低記述の長さの原則を持って来ることができるサンプル効率の潜在的な利益を研究します。 我々はチューリングマシンを用いて普遍的なモデルと回路を表現する。 回路の複雑さと密接性における古典的オープン問題との密接な関係を浮き彫りにする。
  論文  参考訳（メタデータ） (2021-03-23T17:03:10Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。 ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
  論文  参考訳（メタデータ） (2020-04-25T05:45:59Z)
• Tunable Quantum Neural Networks for Boolean Functions [0.0]
  ブール関数を学習するためにゲートを調整できる汎用量子回路のアイデアを導入する。 学習課題を実行するために,測定の欠如を利用したアルゴリズムを考案した。
  論文  参考訳（メタデータ） (2020-03-31T11:55:01Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。