論文の概要: Complexity of Deciding Injectivity and Surjectivity of ReLU Neural Networks

• arxiv url: http://arxiv.org/abs/2405.19805v1
• Date: Thu, 30 May 2024 08:14:34 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-31 15:28:56.574819
• Title: Complexity of Deciding Injectivity and Surjectivity of ReLU Neural Networks
• Title（参考訳）: ReLUニューラルネットワークのインジェクティビティとサージェクティビティの決定の複雑さ
• Authors: Vincent Froese, Moritz Grillo, Martin Skutella,
• Abstract要約: ReLU層の単射率を決定するためのcoNP完全性を証明する。 1次元出力を持つ2層ReLUネットワークのサージェクティビティも特徴付ける。
• 参考スコア（独自算出の注目度）: 5.482420806459269
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Neural networks with ReLU activation play a key role in modern machine learning. In view of safety-critical applications, the verification of trained networks is of great importance and necessitates a thorough understanding of essential properties of the function computed by a ReLU network, including characteristics like injectivity and surjectivity. Recently, Puthawala et al. [JMLR 2022] came up with a characterization for injectivity of a ReLU layer, which implies an exponential time algorithm. However, the exact computational complexity of deciding injectivity remained open. We answer this question by proving coNP-completeness of deciding injectivity of a ReLU layer. On the positive side, as our main result, we present a parameterized algorithm which yields fixed-parameter tractability of the problem with respect to the input dimension. In addition, we also characterize surjectivity for two-layer ReLU networks with one-dimensional output. Remarkably, the decision problem turns out to be the complement of a basic network verification task. We prove NP-hardness for surjectivity, implying a stronger hardness result than previously known for the network verification problem. Finally, we reveal interesting connections to computational convexity by formulating the surjectivity problem as a zonotope containment problem
• Abstract（参考訳）: ReLUアクティベーションを持つニューラルネットワークは、現代の機械学習において重要な役割を果たす。 安全クリティカルな応用の観点からは、トレーニングされたネットワークの検証は非常に重要であり、インジェクティビティやサージェクティビティといった特徴を含むReLUネットワークによって計算される関数の本質的性質を徹底的に理解する必要がある。 最近、Puthawala et al [JMLR 2022] は、指数時間アルゴリズムを意味するReLU層のインジェクティビティのキャラクタリゼーションを考案した。 しかし、射影率を決定するための正確な計算複雑性は未解決のままであった。 我々は、ReLU層の単射率を決定するcoNP完全性を証明することで、この問題に答える。 正の面では、本研究の主な結果として、入力次元に関する問題の固定パラメータのトラクタビリティを導出するパラメータ化アルゴリズムを提案する。 また、1次元出力を持つ2層ReLUネットワークのサージェクティビティも特徴付ける。 興味深いことに、決定問題は、基本的なネットワーク検証タスクを補完するものであることが判明した。 本研究はNP硬度を推定し,従来ネットワーク検証問題で知られていたよりも硬度が強いことを示す。 最後に、双対包摂問題として全射性問題を定式化することにより、計算凸性への興味深い接続を明らかにする。

関連論文リスト

• Physics-Informed Neural Networks: Minimizing Residual Loss with Wide Networks and Effective Activations [5.731640425517324]
  特定の条件下では、広いニューラルネットワークによってPINNの残留損失を世界規模で最小化できることを示す。 良好な高次導関数を持つ活性化関数は、残留損失を最小限に抑える上で重要な役割を果たす。 確立された理論は、PINNの効果的な活性化関数の設計と選択の道を開く。
  論文  参考訳（メタデータ） (2024-05-02T19:08:59Z)
• Robustness Verifcation in Neural Networks [0.0]
  ニューラルネットワーク計算における形式的検証問題について検討する。 1つの疑問は、ネットワークが有効な出力を計算するような有効な入力が存在するかどうかである。 半線形環境では,この問題が克服可能であることを示す。
  論文  参考訳（メタデータ） (2024-03-20T09:34:38Z)
• Fixing the NTK: From Neural Network Linearizations to Exact Convex Programs [63.768739279562105]
  学習目標に依存しない特定のマスクウェイトを選択する場合、このカーネルはトレーニングデータ上のゲートReLUネットワークのNTKと等価であることを示す。 この目標への依存の欠如の結果として、NTKはトレーニングセット上の最適MKLカーネルよりもパフォーマンスが良くない。
  論文  参考訳（メタデータ） (2023-09-26T17:42:52Z)
• Benign Overfitting in Deep Neural Networks under Lazy Training [72.28294823115502]
  データ分布が適切に分離された場合、DNNは分類のためのベイズ最適テスト誤差を達成できることを示す。 よりスムーズな関数との補間により、より一般化できることを示す。
  論文  参考訳（メタデータ） (2023-05-30T19:37:44Z)
• On the ISS Property of the Gradient Flow for Single Hidden-Layer Neural Networks with Linear Activations [0.0]
  本研究では,不確かさが勾配推定に及ぼす影響について検討した。 一般の過度にパラメータ化された定式化は、損失関数が最小化される集合の外側に配置されるスプリアス平衡の集合を導入することを示す。
  論文  参考訳（メタデータ） (2023-05-17T02:26:34Z)
• Globally Optimal Training of Neural Networks with Threshold Activation Functions [63.03759813952481]
  しきい値アクティベートを伴うディープニューラルネットワークの重み劣化正規化学習問題について検討した。 ネットワークの特定の層でデータセットを破砕できる場合に、簡易な凸最適化の定式化を導出する。
  論文  参考訳（メタデータ） (2023-03-06T18:59:13Z)
• And/or trade-off in artificial neurons: impact on adversarial robustness [91.3755431537592]
  ネットワークに十分な数のOR様ニューロンが存在すると、分類の脆さと敵の攻撃に対する脆弱性が増加する。 そこで我々は,AND様ニューロンを定義し,ネットワーク内での割合を増大させる対策を提案する。 MNISTデータセットによる実験結果から,本手法はさらなる探索の方向として有望であることが示唆された。
  論文  参考訳（メタデータ） (2021-02-15T08:19:05Z)
• Global Optimization of Objective Functions Represented by ReLU Networks [77.55969359556032]
  ニューラルネットワークは複雑で非敵対的な関数を学ぶことができ、安全クリティカルな文脈でそれらの正しい振る舞いを保証することは困難である。 ネットワーク内の障害を見つけるための多くのアプローチ(例えば、敵の例)があるが、これらは障害の欠如を保証できない。 本稿では,最適化プロセスを検証手順に統合し,本手法よりも優れた性能を実現する手法を提案する。
  論文  参考訳（メタデータ） (2020-10-07T08:19:48Z)
• Measuring Model Complexity of Neural Networks with Curve Activation Functions [100.98319505253797]
  本稿では,線形近似ニューラルネットワーク(LANN)を提案する。 ニューラルネットワークのトレーニングプロセスを実験的に検討し、オーバーフィッティングを検出する。 我々は、$L1$と$L2$正規化がモデルの複雑さの増加を抑制することを発見した。
  論文  参考訳（メタデータ） (2020-06-16T07:38:06Z)
• Globally Injective ReLU Networks [20.106755410331576]
  インジェクティビティは、推論を可能にする生成モデルにおいて重要な役割を果たす。 完全連結型および畳み込み型ReLU層およびネットワークのインジェクティビティを鋭く評価する。
  論文  参考訳（メタデータ） (2020-06-15T15:12:12Z)
• Deep Neural Networks with Trainable Activations and Controlled Lipschitz Constant [26.22495169129119]
  本稿では,深層ニューラルネットワークの活性化関数を学習するための変分フレームワークを提案する。 我々の目的は、リプシッツ定数の上界を制御しながら、ネットワークの容量を増加させることである。 提案手法を標準ReLUネットワークとその変種であるPRELUとLeakyReLUと比較する。
  論文  参考訳（メタデータ） (2020-01-17T12:32:55Z)

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

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