論文の概要: Exact Learning of Permutations for Nonzero Binary Inputs with Logarithmic Training Size and Quadratic Ensemble Complexity

• arxiv url: http://arxiv.org/abs/2502.16763v1
• Date: Mon, 24 Feb 2025 00:50:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-25 15:53:10.990336
• Title: Exact Learning of Permutations for Nonzero Binary Inputs with Logarithmic Training Size and Quadratic Ensemble Complexity
• Title（参考訳）: 対数的訓練サイズと擬似アンサンブル複雑度を有する非ゼロ二項入力の置換の厳密な学習
• Authors: George Giapitzakis, Artur Back de Luca, Kimon Fountoulakis,
• Abstract要約: 本稿では,2層に完全接続されたフィードフォワードニューラルネットワークと,非ゼロ二項入力における順列学習の課題に焦点を当てる。 無限幅のニューラル・タンジェント・カーネル(NTK)では、$k$の標準基底ベクトルのみに勾配降下で訓練されたネットワークのアンサンブルが、任意に高い確率で$k$の固定置換をうまく学習できることが示される。
• 参考スコア（独自算出の注目度）: 5.3800094588915375
• License:
• Abstract: The ability of an architecture to realize permutations is quite fundamental. For example, Large Language Models need to be able to correctly copy (and perhaps rearrange) parts of the input prompt into the output. Classical universal approximation theorems guarantee the existence of parameter configurations that solve this task but offer no insights into whether gradient-based algorithms can find them. In this paper, we address this gap by focusing on two-layer fully connected feed-forward neural networks and the task of learning permutations on nonzero binary inputs. We show that in the infinite width Neural Tangent Kernel (NTK) regime, an ensemble of such networks independently trained with gradient descent on only the $k$ standard basis vectors out of $2^k - 1$ possible inputs successfully learns any fixed permutation of length $k$ with arbitrarily high probability. By analyzing the exact training dynamics, we prove that the network's output converges to a Gaussian process whose mean captures the ground truth permutation via sign-based features. We then demonstrate how averaging these runs (an "ensemble" method) and applying a simple rounding step yields an arbitrarily accurate prediction on any possible input unseen during training. Notably, the number of models needed to achieve exact learning with high probability (which we refer to as ensemble complexity) exhibits a linearithmic dependence on the input size $k$ for a single test input and a quadratic dependence when considering all test inputs simultaneously.
• Abstract（参考訳）: アーキテクチャが置換を実現する能力は、非常に基本的なものです。 例えば、Large Language Modelsは入力プロンプトの部分を正しくコピー(そしておそらく再配列)できる必要がある。 古典的普遍近似定理は、この問題を解くパラメータ構成の存在を保証するが、勾配に基づくアルゴリズムがそれらを見つけることができるかどうかについての洞察を与えない。 本稿では、このギャップを2層完全接続フィードフォワードニューラルネットワークと、非ゼロ二項入力における置換学習の課題に焦点をあてて解決する。 無限幅のニューラル・タンジェント・カーネル(NTK)では、$k$の標準基底ベクトルのみに勾配降下を訓練したネットワークのアンサンブルが、任意に高い確率で$k$の固定置換をうまく学習できることが示される。 正確なトレーニングダイナミクスを解析することにより、ネットワークの出力がガウス過程に収束することを証明する。 次に、これらの実行を平均化して("アンサンブル"法)、単純な丸めのステップを適用すると、トレーニング中に見つからない可能性のある入力について任意に正確な予測が得られます。 特に、高い確率で正確な学習を行うために必要なモデルの数は、単一のテスト入力に対して$k$の入力サイズと、全てのテスト入力を同時に考慮する場合の二次的依存に線形依存を示す。

関連論文リスト

• Automated Sizing and Training of Efficient Deep Autoencoders using Second Order Algorithms [0.46040036610482665]
  一般化線形分類器の多段階学習法を提案する。 検証エラーは不要な入力のプルーニングによって最小化される。 所望の出力は、Ho-Kashyapルールに似た方法で改善される。
  論文  参考訳（メタデータ） (2023-08-11T16:48:31Z)
• Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Tasks [51.8723187709964]
  ニューラルネットワーク推論タスクのOOD一般化について検討する。 目標は、ディープニューラルネットワークを使用して入出力ペアからアルゴリズムを学ぶことである。
  論文  参考訳（メタデータ） (2022-11-01T18:33:20Z)
• Quantum Extremal Learning [0.8937790536664091]
  本稿では,関数出力を極大化する隠れ関数への入力を見つける過程である「極大学習のための量子アルゴリズム」を提案する。 量子エクストリームラーニング(quantum extremal Learning, QEL)と呼ばれるこのアルゴリズムは、データ入力と出力の関係をモデル化するために変分訓練されたパラメトリック量子回路で構成されている。
  論文  参考訳（メタデータ） (2022-05-05T17:37:26Z)
• 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)
• A quantum algorithm for training wide and deep classical neural networks [72.2614468437919]
  勾配勾配勾配による古典的トレーサビリティに寄与する条件は、量子線形系を効率的に解くために必要な条件と一致することを示す。 MNIST画像データセットがそのような条件を満たすことを数値的に示す。 我々は、プールを用いた畳み込みニューラルネットワークのトレーニングに$O(log n)$の実証的証拠を提供する。
  論文  参考訳（メタデータ） (2021-07-19T23:41:03Z)
• Alleviate Exposure Bias in Sequence Prediction \\ with Recurrent Neural Networks [47.52214243454995]
  繰り返しニューラルネットワーク(RNN)を訓練する一般的な戦略は、各ステップで入力として地上の真実を取ることです。 本稿では,RNNの長期的依存関係をよりよく把握するための,完全微分可能なトレーニングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-03-22T06:15:22Z)
• Neural networks behave as hash encoders: An empirical study [79.38436088982283]
  ReLUライクなアクティベーションを持つニューラルネットワークの入力空間は、複数の線形領域に分割される。 このパーティションは、さまざまなディープラーニングモデルで以下のエンコーディング特性を示すことを実証します。 K$-Means、$K$-NN、およびロジスティック回帰などの単純なアルゴリズムは、トレーニングデータとテストデータの両方でかなり優れたパフォーマンスを達成できます。
  論文  参考訳（メタデータ） (2021-01-14T07:50:40Z)
• A case where a spindly two-layer linear network whips any neural network with a fully connected input layer [24.132345589750592]
  勾配降下によるスパース目標を効率的に学習するために,スパース入力層が必要であることを示す。 驚くべきことに、同じタイプの問題は、単純な2層線形ニューラルネットワークによって大幅に効率良く解決できる。
  論文  参考訳（メタデータ） (2020-10-16T20:49:58Z)
• Why Are Convolutional Nets More Sample-Efficient than Fully-Connected Nets? [33.51250867983687]
  標準学習アルゴリズムにおいて、証明可能なサンプル複雑性のギャップを示すことができる自然なタスクを示す。 単一の対象関数を示し、可能なすべての分布について、$O(1)$対$Omega(d2/varepsilon)$ギャップを学習する。 同様の結果が$ell$回帰およびAdamやAdaGradといった適応型トレーニングアルゴリズムに対して達成される。
  論文  参考訳（メタデータ） (2020-10-16T17:15:39Z)

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

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