論文の概要: Improved Bounds on Neural Complexity for Representing Piecewise Linear Functions

• arxiv url: http://arxiv.org/abs/2210.07236v1
• Date: Thu, 13 Oct 2022 17:58:41 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-14 14:11:53.742101
• Title: Improved Bounds on Neural Complexity for Representing Piecewise Linear Functions
• Title（参考訳）: 線形関数表現のためのニューラルネットワークの複雑度改善
• Authors: Kuan-Lin Chen, Harinath Garudadri, Bhaskar D. Rao
• Abstract要約: 修正線形単位を用いたディープニューラルネットワークは、連続的ピースワイド線形関数(CPWL)を表す。 最近の研究では、任意のCPWL関数を正確に表すために必要なニューロンの数は、ピースの数と指数関数的に増加するか、あるいは異なる線形成分の数の因子として指数関数的に増加すると推定されている。 本稿では、より厳密な境界を提案し、任意のCPWL関数に対してこれらの境界を満たすネットワークを見つけるための時間アルゴリズムを確立する。
• 参考スコア（独自算出の注目度）: 23.96475985648844
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A deep neural network using rectified linear units represents a continuous piecewise linear (CPWL) function and vice versa. Recent results in the literature estimated that the number of neurons needed to exactly represent any CPWL function grows exponentially with the number of pieces or exponentially in terms of the factorial of the number of distinct linear components. Moreover, such growth is amplified linearly with the input dimension. These existing results seem to indicate that the cost of representing a CPWL function is expensive. In this paper, we propose much tighter bounds and establish a polynomial time algorithm to find a network satisfying these bounds for any given CPWL function. We prove that the number of hidden neurons required to exactly represent any CPWL function is at most a quadratic function of the number of pieces. In contrast to all previous results, this upper bound is invariant to the input dimension. Besides the number of pieces, we also study the number of distinct linear components in CPWL functions. When such a number is also given, we prove that the quadratic complexity turns into bilinear, which implies a lower neural complexity because the number of distinct linear components is always not greater than the minimum number of pieces in a CPWL function. When the number of pieces is unknown, we prove that, in terms of the number of distinct linear components, the neural complexity of any CPWL function is at most polynomial growth for low-dimensional inputs and a factorial growth for the worst-case scenario, which are significantly better than existing results in the literature.
• Abstract（参考訳）: 修正線形単位を用いたディープニューラルネットワークは、連続的ピースワイド線形関数(CPWL)を表す。 文献の最近の結果は、任意のCPWL関数を正確に表すために必要なニューロンの数は、異なる線形成分の個数の因子で指数関数的に増加するか、指数関数的に増加すると推定している。 さらに、そのような成長は入力次元と線形に増幅される。 これらの結果から,CPWL関数の表現コストは高価であることが示唆された。 本稿では,任意の CPWL 関数に対して,これらの境界を満たすネットワークを見つけるための多項式時間アルゴリズムを提案する。 CPWL関数を正確に表すために必要な隠されたニューロンの数は、少なくとも断片数の2次関数であることを示す。 以前の全ての結果とは対照的に、この上限は入力次元に不変である。 部品数以外にも、CPWL関数の異なる線形成分の数についても検討する。 このような数も与えられると、二次的な複雑性が双線型に変化することが証明され、これは神経の複雑さが小さくなることを意味する。 異なる線形成分の数に関して、CPWL関数の神経的複雑さは、低次元の入力に対して最も多項式的成長であり、最悪の場合の因子的成長であり、文献における既存の結果よりもはるかに優れていることを証明している。

関連論文リスト

• Decomposition Polyhedra of Piecewise Linear Functions [4.594829845106234]
  本稿では,連続ピースワイド線形関数(CPWL)を凸CPWL関数に分解する方法について,よく研究されている問題に寄与する。 すべての CPWL 関数は無限分解を持つが、差分 2 個の凸 CPWL 関数を持つ。 できるだけ少ない線形部分で分解を見つけるために、我々のフレームワークを適用します。
  論文  参考訳（メタデータ） (2024-10-07T10:48:36Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• Polynomial Width is Sufficient for Set Representation with High-dimensional Features [69.65698500919869]
  DeepSetsは集合表現のための最も広く使われているニューラルネットワークアーキテクチャである。 a) 線形 + パワーアクティベーション (LP) と (b) 線形 + 指数的アクティベーション (LE) の2つの集合要素埋め込み層を示す。
  論文  参考訳（メタデータ） (2023-07-08T16:00:59Z)
• Deep neural network approximation of composite functions without the curse of dimensionality [0.0]
  本稿では,ディープニューラルネットワーク(DNN)により近似できる高次元連続関数のクラスを同定する。 クラス内の函数は、積、極大、ある平行化されたリプシッツ連続函数を含む潜在的に非有界な特殊函数として表すことができる。
  論文  参考訳（メタデータ） (2023-04-12T12:08:59Z)
• Expressivity of Shallow and Deep Neural Networks for Polynomial Approximation [0.0]
  一般コンパクト領域上の積関数を近似する浅層ネットワークの複雑さの指数的下界を確立する。 また、この下界は単位立方体上の正規化リプシッツ単項数には適用されないことを示した。
  論文  参考訳（メタデータ） (2023-03-06T23:01:53Z)
• Going Beyond Linear RL: Sample Efficient Neural Function Approximation [76.57464214864756]
  2層ニューラルネットワークによる関数近似について検討する。 この結果は線形(あるいは可溶性次元)法で達成できることを大幅に改善する。
  論文  参考訳（メタデータ） (2021-07-14T03:03:56Z)
• Bilinear Classes: A Structural Framework for Provable Generalization in RL [119.42509700822484]
  Bilinear Classesは強化学習の一般化を可能にする新しい構造フレームワークである。 このフレームワークは、サンプルの複雑さが達成可能な、ほとんどすべての既存のモデルを取り込んでいる。 我々の主な成果は、双線形クラスのためのサンプル複雑性を持つRLアルゴリズムである。
  論文  参考訳（メタデータ） (2021-03-19T16:34:20Z)
• Neural network approaches to point lattice decoding [6.025026882312586]
  voronoi-reduced基底は二元集合への解の空間を制限するために導入された。 CPWL復号関数におけるアフィンの個数を数え、復号問題の複雑さを特徴づける。
  論文  参考訳（メタデータ） (2020-12-13T10:53:34Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  強化学習のコアにおける探索・探索トレードオフについて検討する。 特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。 私たちの後悔の限界はエピソードの数とは無関係です。
  論文  参考訳（メタデータ） (2020-11-09T18:32:22Z)
• Measuring Model Complexity of Neural Networks with Curve Activation Functions [100.98319505253797]
  本稿では,線形近似ニューラルネットワーク(LANN)を提案する。 ニューラルネットワークのトレーニングプロセスを実験的に検討し、オーバーフィッティングを検出する。 我々は、$L1$と$L2$正規化がモデルの複雑さの増加を抑制することを発見した。
  論文  参考訳（メタデータ） (2020-06-16T07:38:06Z)

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

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