Fugu-MT 論文翻訳(概要): Complexity of Injectivity and Verification of ReLU Neural Networks

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

arxiv url: http://arxiv.org/abs/2405.19805v2
Date: Mon, 16 Jun 2025 06:32:52 GMT
ステータス: 翻訳完了
システム内更新日: 2025-06-17 19:42:49.039219
Title: Complexity of Injectivity and Verification of ReLU Neural Networks
Title（参考訳）: インジェクティビティの複雑さとReLUニューラルネットワークの検証
Authors: Vincent Froese, Moritz Grillo, Martin Skutella,
Abstract要約: ReLUネットワークによって計算される関数のインジェクティビティは、関数の可逆性が要求されるたびに重要な役割を果たす。インジェクティビティを決定する正確な計算複雑性のcoNP完全性を証明する。また,特定の入力が特定の出力しか得られないことを検証するネットワーク検証問題についても検討する。
参考スコア（独自算出の注目度）: 5.482420806459269
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Neural networks with ReLU activation play a key role in modern machine learning. Understanding the functions represented by ReLU networks is a major topic in current research as this enables a better interpretability of learning processes. Injectivity of a function computed by a ReLU network, that is, the question if different inputs to the network always lead to different outputs, plays a crucial role whenever invertibility of the function is required, such as, e.g., for inverse problems or generative models. The exact computational complexity of deciding injectivity was recently posed as an open problem (Puthawala et al. [JMLR 2022]). We answer this question by proving coNP-completeness. On the positive side, we show that the problem for a single ReLU-layer is still tractable for small input dimension; more precisely, we present a parameterized algorithm which yields fixed-parameter tractability with respect to the input dimension. In addition, we study the network verification problem which is to verify that certain inputs only yield specific outputs. This is of great importance since neural networks are increasingly used in safety-critical systems. We prove that network verification is coNP-hard for a general class of input domains. Our results also exclude constant-factor polynomial-time approximations for the maximum of a function computed by a ReLU network. In this context, we also characterize surjectivity of functions computed by ReLU networks with one-dimensional output which turns out to be the complement of a basic network verification task. We reveal interesting connections to computational convexity by formulating the surjectivity problem as a zonotope containment problem
Abstract（参考訳）: ReLUアクティベーションを持つニューラルネットワークは、現代の機械学習において重要な役割を果たす。 ReLUネットワークで表現される関数を理解することは、学習プロセスのより良い解釈可能性を実現するため、現在の研究において主要なトピックである。 ReLUネットワークによって計算される関数のインジェクティビティ、すなわち、ネットワークへの異なる入力が常に異なる出力に導かれるかどうかという問題は、逆問題や生成モデルのために関数の可逆性が必要なときは常に重要な役割を果たす。射影率を決定する正確な計算複雑性は、最近開問題として提起された(Puthawala et al [JMLR 2022])。我々は、coNP完全性を証明することで、この問題に答える。正の面では、単一ReLU層が小さい入力次元に対してまだトラクタブルであることを示し、より正確には、入力次元に対して固定パラメータのトラクタビリティをもたらすパラメータ化アルゴリズムを提案する。さらに,特定の入力が特定の出力しか得られないことを検証するネットワーク検証問題について検討する。これは、ニューラルネットワークが安全クリティカルなシステムでますます使われているため、非常に重要である。入力領域の一般クラスに対してネットワーク検証がcoNPハードであることを証明する。また,ReLUネットワークによって計算される関数の最大値に対する定数係数多項式時間近似も除外した。この文脈では、ReLUネットワークによって計算された関数の1次元の出力により、基本的ネットワーク検証タスクの補完となる関数のサージェクティビティも特徴付ける。代入性問題をゾノトープ包含問題として定式化することにより,計算凸性への興味深い関係を明らかにする。

関連論文リスト

PEEL the Layers and Find Yourself: Revisiting Inference-time Data Leakage for Residual Neural Networks [64.90981115460937]
本稿では、ディープニューラルネットワーク(NN)の推論時データ漏洩リスクについて検討する。残差NNの中間出力からブロックワイズ入力特徴を効果的に回収できる新しい後方特徴逆変換法である textbfPEEL を提案する。その結果,平均二乗誤差 (MSE) で評価した場合,PEEL は最先端の回収方法よりも桁違いに優れていることがわかった。
論文参考訳（メタデータ） (2025-04-08T20:11:05Z)
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)

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

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