論文の概要: On Algebraic Constructions of Neural Networks with Small Weights
- arxiv url: http://arxiv.org/abs/2205.08032v1
- Date: Tue, 17 May 2022 00:09:23 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-18 14:53:56.985758
- Title: On Algebraic Constructions of Neural Networks with Small Weights
- Title（参考訳）: 小重量ニューラルネットワークの代数的構成について
- Authors: Kordag Mehmet Kilic, Jin Sima and Jehoshua Bruck
- Abstract要約: 神経ゲートの重みサイズ,回路サイズ,深さのトレードオフについて検討した。
具体的には、任意の係数を持つ1つの線型方程式が与えられたとき、より小さい(一定の)係数を持つ線形方程式系を用いてそれを表現したい。
EQUALITY関数を計算するために,定数重み付き最適サイズ行列を明示的に構築する。
我々はComparISON関数を計算するために最もよく知られたウェイトサイズ(線形)行列の存在を証明した。
- 参考スコア（独自算出の注目度）: 21.915057426589748
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Neural gates compute functions based on weighted sums of the input variables.
The expressive power of neural gates (number of distinct functions it can
compute) depends on the weight sizes and, in general, large weights
(exponential in the number of inputs) are required. Studying the trade-offs
among the weight sizes, circuit size and depth is a well-studied topic both in
circuit complexity theory and the practice of neural computation. We propose a
new approach for studying these complexity trade-offs by considering a related
algebraic framework. Specifically, given a single linear equation with
arbitrary coefficients, we would like to express it using a system of linear
equations with smaller (even constant) coefficients. The techniques we
developed are based on Siegel's Lemma for the bounds, anti-concentration
inequalities for the existential results and extensions of Sylvester-type
Hadamard matrices for the constructions.
We explicitly construct a constant weight, optimal size matrix to compute the
EQUALITY function (checking if two integers expressed in binary are equal).
Computing EQUALITY with a single linear equation requires exponentially large
weights. In addition, we prove the existence of the best-known weight size
(linear) matrices to compute the COMPARISON function (comparing between two
integers expressed in binary). In the context of the circuit complexity theory,
our results improve the upper bounds on the weight sizes for the best-known
circuit sizes for EQUALITY and COMPARISON.
- Abstract（参考訳）: ニューラルゲートは入力変数の重み付け和に基づいて関数を計算する。
ニューラルゲートの表現力(計算可能な異なる関数の数)は、重みの大きさに依存し、一般に大きな重み(入力数の指数)が必要となる。
重みサイズ、回路サイズ、深さのトレードオフの研究は、回路複雑性理論と神経計算の実践の両方においてよく研究されているトピックである。
本稿では,これらの複雑性のトレードオフを研究するための新しい手法を提案する。
具体的には、任意の係数を持つ1つの線型方程式が与えられたとき、より小さい(一定の)係数を持つ線形方程式系を用いてそれを表現したい。
私たちが開発した手法は、ジーゲルの『Lemma for the bounds, anti-concentration inequality for the existential results and extension of Sylvester-type Hadamard matrices for the constructions』に基づいている。
EQUALITY関数を計算するために、定数ウェイトで最適なサイズ行列を明示的に構築する(二進数で表される2つの整数が等しいかどうかを確認する)。
単一の線形方程式で等式を計算するには指数関数的に大きな重みを必要とする。
さらに、ComparISON関数(バイナリで表される2つの整数間の比較)を計算するために、最もよく知られたウェイトサイズ(線形)行列の存在を証明する。
回路複雑性理論の文脈において,本論文は等式と比較のために最もよく知られた回路サイズの重み付け上の上限を改善した。
関連論文リスト
- Efficient Variational Quantum Linear Solver for Structured Sparse Matrices [0.6138671548064355]
代替基底を用いることで、行列のスパーシリティと基盤構造をよりうまく活用できることが示される。
我々は、グローバル/ローカルなVQLSコスト関数を計算するために効率的な量子回路を設計するために、ユニタリ補完の概念を用いる。
論文 参考訳（メタデータ） (2024-04-25T19:22:05Z) - Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。
我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文 参考訳（メタデータ） (2024-03-08T18:50:19Z) - CoLA: Exploiting Compositional Structure for Automatic and Efficient
Numerical Linear Algebra [62.37017125812101]
機械学習における大規模線形代数問題に対して, CoLA という, 単純だが汎用的なフレームワークを提案する。
線形演算子抽象と合成ディスパッチルールを組み合わせることで、CoLAはメモリと実行時の効率的な数値アルゴリズムを自動的に構築する。
偏微分方程式,ガウス過程,同変モデル構築,教師なし学習など,幅広い応用で有効性を示す。
論文 参考訳（メタデータ） (2023-09-06T14:59:38Z) - Fast quantum algorithm for differential equations [0.5895819801677125]
我々は、数値複雑性を持つ量子アルゴリズムを、$N$で多対数であるが、大規模なPDEに対して$kappa$とは独立に提示する。
提案アルゴリズムは,解の特徴を抽出する量子状態を生成する。
論文 参考訳（メタデータ） (2023-06-20T18:01:07Z) - A Recursively Recurrent Neural Network (R2N2) Architecture for Learning
Iterative Algorithms [64.3064050603721]
本研究では,リカレントニューラルネットワーク (R2N2) にランゲ・クッタニューラルネットワークを一般化し,リカレントニューラルネットワークを最適化した反復アルゴリズムの設計を行う。
本稿では, 線形方程式系に対するクリロフ解法, 非線形方程式系に対するニュートン・クリロフ解法, 常微分方程式に対するルンゲ・クッタ解法と類似の繰り返しを計算問題クラスの入力・出力データに対して提案した超構造内における重みパラメータの正規化について述べる。
論文 参考訳（メタデータ） (2022-11-22T16:30:33Z) - 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) - ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation [5.35599092568615]
本稿では,線形整流ユニットを用いたニューラルネットワークのパワーについて検討する。
我々は,2つの基本最適化問題を$mathcalO(m2n2)$のニューラルネットワークで解くことができることを示した。
論文 参考訳（メタデータ） (2021-02-12T17:23:34Z) - On Function Approximation in Reinforcement Learning: Optimism in the
Face of Large State Spaces [208.67848059021915]
強化学習のコアにおける探索・探索トレードオフについて検討する。
特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。
私たちの後悔の限界はエピソードの数とは無関係です。
論文 参考訳（メタデータ） (2020-11-09T18:32:22Z) - Berrut Approximated Coded Computing: Straggler Resistance Beyond
Polynomial Computing [34.69732430310801]
本稿では,ストラグラー効果に対処する代替手法として,Berrut Approximated Coded Computing (BACC)を提案する。
BACCは計算複雑性が低い数値的に安定であることが証明されている。
特に、BACCは、サーバのクラスタ上でディープニューラルネットワークをトレーニングするために使用される。
論文 参考訳（メタデータ） (2020-09-17T14:23:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。