論文の概要: The Computational Complexity of Counting Linear Regions in ReLU Neural Networks
- arxiv url: http://arxiv.org/abs/2505.16716v1
- Date: Thu, 22 May 2025 14:25:12 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-23 17:12:48.356207
- Title: The Computational Complexity of Counting Linear Regions in ReLU Neural Networks
- Title（参考訳）: ReLUニューラルネットワークにおける数直線領域の計算複雑性
- Authors: Moritz Stargalla, Christoph Hertrich, Daniel Reichman,
- Abstract要約: 線型領域が実際に何であるかについては、多くの異なる定義が存在する。
種々の定義に対して,そのような領域の数を数えることの計算複雑性を解析する。
アルゴリズム面では、いくつかの共通定義に対して少なくとも空間において線形領域を数えることが可能であることを示す。
- 参考スコア（独自算出の注目度）: 6.363158395541767
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: An established measure of the expressive power of a given ReLU neural network is the number of linear regions into which it partitions the input space. There exist many different, non-equivalent definitions of what a linear region actually is. We systematically assess which papers use which definitions and discuss how they relate to each other. We then analyze the computational complexity of counting the number of such regions for the various definitions. Generally, this turns out to be an intractable problem. We prove NP- and #P-hardness results already for networks with one hidden layer and strong hardness of approximation results for two or more hidden layers. Finally, on the algorithmic side, we demonstrate that counting linear regions can at least be achieved in polynomial space for some common definitions.
- Abstract（参考訳）: 与えられたReLUニューラルネットワークの表現力の確立された尺度は、入力空間を分割する線形領域の数である。
線型領域が実際に何であるかについては、多くの異なる、非等価な定義が存在する。
我々は、どの論文がどの定義を使うのかを体系的に評価し、それらの相互関係を議論する。
次に、これらの領域の数を様々な定義に対して数えることの計算複雑性を分析する。
一般的には、これは難解な問題である。
隠れた層が1つあるネットワークに対して既にNPと#Pの硬さが証明されており、2つ以上の隠れた層に対して近似結果の強い硬さが証明されている。
最後に、アルゴリズム側では、いくつかの共通定義に対して少なくとも多項式空間において線形領域を数えることが可能であることを示す。
関連論文リスト
- The Evolution of the Interplay Between Input Distributions and Linear
Regions in Networks [20.97553518108504]
ReLUに基づくディープニューラルネットワークにおける線形凸領域の数をカウントする。
特に、任意の1次元入力に対して、それを表現するのに必要となるニューロンの数に対して最小限の閾値が存在することを証明している。
また、トレーニング中のReLUネットワークにおける決定境界の反復的改善プロセスも明らかにした。
論文 参考訳（メタデータ） (2023-10-28T15:04:53Z) - Zonotope Domains for Lagrangian Neural Network Verification [102.13346781220383]
我々は、ディープニューラルネットワークを多くの2層ニューラルネットワークの検証に分解する。
我々の手法は線形プログラミングとラグランジアンに基づく検証技術の両方により改善された境界を与える。
論文 参考訳（メタデータ） (2022-10-14T19:31:39Z) - Algorithmic Determination of the Combinatorial Structure of the Linear
Regions of ReLU Neural Networks [0.0]
正準多面体のすべての次元の領域と面を決定する。
この全標準構造を計算するアルゴリズムを提案する。
得られたアルゴリズムは、中間ニューロンの数に時間とともに数値的に安定し、すべての次元にわたって正確な情報を得る。
論文 参考訳（メタデータ） (2022-07-15T18:36:12Z) - On the Number of Regions of Piecewise Linear Neural Networks [16.78532039510369]
多くのフィードフォワードニューラルネットワーク(NN)はCPWLマッピングを生成する。
これらのいわゆる線形領域の数は、CPWL NNの表現性を特徴付ける自然な計量を提供する。
本稿では,CPWL NN が生成する線形領域の平均数を推定する補完的フレームワークを提案する。
論文 参考訳（メタデータ） (2022-06-17T08:17:28Z) - Mean-field Analysis of Piecewise Linear Solutions for Wide ReLU Networks [83.58049517083138]
勾配勾配勾配を用いた2層ReLUネットワークについて検討する。
SGDは単純な解に偏りがあることが示される。
また,データポイントと異なる場所で結び目が発生するという経験的証拠も提供する。
論文 参考訳（メタデータ） (2021-11-03T15:14:20Z) - The Separation Capacity of Random Neural Networks [78.25060223808936]
標準ガウス重みと一様分布バイアスを持つ十分に大きな2層ReLUネットワークは、この問題を高い確率で解くことができることを示す。
我々は、相互複雑性という新しい概念の観点から、データの関連構造を定量化する。
論文 参考訳（メタデータ） (2021-07-31T10:25:26Z) - A General Computational Framework to Measure the Expressiveness of
Complex Networks Using a Tighter Upper Bound of Linear Regions [13.030269373463168]
整流器ネットワークによって分割される領域番号の上限は、数値自体の代わりに、DNNの表現力のより実用的な測定である。
我々は,任意のネットワーク構造に対して,新しい,より厳密なアップ・パー・バウンド領域番号を提案する。
私たちの実験では、上界が既存のものよりも密接であることを示し、スキップ接続と残余構造がネットワーク性能を改善する理由を説明します。
論文 参考訳（メタデータ） (2020-12-08T14:01:20Z) - Counting Substructures with Higher-Order Graph Neural Networks:
Possibility and Impossibility Results [58.277290855841976]
グラフニューラルネットワーク(GNN)の計算コストと表現力のトレードオフについて検討する。
新しいモデルでは、$k$のサブグラフをカウントでき、低次GNNの既知の制限を克服できることを示す。
いくつかの場合において、提案アルゴリズムは既存の高階$k$-GNNに比べて計算量を大幅に削減することができる。
論文 参考訳（メタデータ） (2020-12-06T03:42:54Z) - Bounding The Number of Linear Regions in Local Area for Neural Networks
with ReLU Activations [6.4817648240626005]
本稿では,与えられたReLUニューラルネットワークの入力空間内の任意の球面における線形領域数の上界を推定する最初の手法を提案する。
実験の結果、ニューラルネットワークをトレーニングしている間、線形領域の境界はトレーニングデータポイントから離れる傾向にあることがわかった。
論文 参考訳（メタデータ） (2020-07-14T04:06:00Z) - Multipole Graph Neural Operator for Parametric Partial Differential
Equations [57.90284928158383]
物理系をシミュレーションするためのディープラーニングベースの手法を使用する際の大きな課題の1つは、物理ベースのデータの定式化である。
線形複雑度のみを用いて、あらゆる範囲の相互作用をキャプチャする、新しいマルチレベルグラフニューラルネットワークフレームワークを提案する。
実験により, 離散化不変解演算子をPDEに学習し, 線形時間で評価できることを確認した。
論文 参考訳（メタデータ） (2020-06-16T21:56:22Z) - Neural Operator: Graph Kernel Network for Partial Differential Equations [57.90284928158383]
この作業はニューラルネットワークを一般化し、無限次元空間(演算子)間の写像を学習できるようにすることである。
非線形活性化関数と積分作用素のクラスを構成することにより、無限次元写像の近似を定式化する。
実験により,提案したグラフカーネルネットワークには所望の特性があり,最先端技術と比較した場合の競合性能を示すことが確認された。
論文 参考訳（メタデータ） (2020-03-07T01:56:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。