Fugu-MT 論文翻訳(概要): Reachability Is NP-Complete Even for the Simplest Neural Networks

論文の概要: Reachability Is NP-Complete Even for the Simplest Neural Networks

arxiv url: http://arxiv.org/abs/2108.13179v1
Date: Mon, 30 Aug 2021 12:38:57 GMT
ステータス: 処理完了
システム内更新日: 2021-08-31 18:02:42.999772
Title: Reachability Is NP-Complete Even for the Simplest Neural Networks
Title（参考訳）: 最も単純なニューラルネットワークでもNP完全である到達可能性
Authors: Marco S\"alzer and Martin Lange
Abstract要約: この問題は、一般的なニューラルネットワークと共役入力/出力仕様に対してNP完全である、と最近主張された。 NP-hardnessは1層のみの単純な仕様とニューラルネットワークの制限されたクラスをすでに保持していることを示す。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We investigate the complexity of the reachability problem for (deep) neural networks: does it compute valid output given some valid input? It was recently claimed that the problem is NP-complete for general neural networks and conjunctive input/output specifications. We repair some flaws in the original upper and lower bound proofs. We then show that NP-hardness already holds for restricted classes of simple specifications and neural networks with just one layer, as well as neural networks with minimal requirements on the occurring parameters.
Abstract（参考訳）: 我々は、(深度)ニューラルネットワークの到達可能性問題の複雑さを調査し、有効な入力が与えられたとき、有効な出力を計算するか? この問題は一般のニューラルネットワークと接続型入出力仕様に対してNP完全であると主張した。元の上界証明と下界証明のいくつかの欠陥を修復する。さらに,np-hardnessは1層のみの単純な仕様とニューラルネットワークの制限クラスと,発生パラメータの最小要件を持つニューラルネットワークに対してすでに保持されていることを示す。

関連論文リスト

LinSATNet: The Positive Linear Satisfiability Neural Networks [116.65291739666303]
本稿では,ニューラルネットワークに人気の高い正の線形満足度を導入する方法について検討する。本稿では,古典的なシンクホーンアルゴリズムを拡張し,複数の辺分布の集合を共同で符号化する,最初の微分可能満足層を提案する。
論文参考訳（メタデータ） (2024-07-18T22:05:21Z)
Verified Neural Compressed Sensing [58.98637799432153]
精度の高い計算タスクのために、初めて(私たちの知識を最大限に活用するために)証明可能なニューラルネットワークを開発します。極小問題次元(最大50)では、線形および双項線形測定からスパースベクトルを確実に回復するニューラルネットワークを訓練できることを示す。ネットワークの複雑さは問題の難易度に適応できることを示し、従来の圧縮センシング手法が証明不可能な問題を解く。
論文参考訳（メタデータ） (2024-05-07T12:20:12Z)
Robustness Verifcation in Neural Networks [0.0]
ニューラルネットワーク計算における形式的検証問題について検討する。 1つの疑問は、ネットワークが有効な出力を計算するような有効な入力が存在するかどうかである。半線形環境では,この問題が克服可能であることを示す。
論文参考訳（メタデータ） (2024-03-20T09:34:38Z)
Extrapolation and Spectral Bias of Neural Nets with Hadamard Product: a Polynomial Net Study [55.12108376616355]
NTKの研究は典型的なニューラルネットワークアーキテクチャに特化しているが、アダマール製品(NNs-Hp)を用いたニューラルネットワークには不完全である。本研究では,ニューラルネットワークの特別なクラスであるNNs-Hpに対する有限幅Kの定式化を導出する。我々は,カーネル回帰予測器と関連するNTKとの等価性を証明し,NTKの適用範囲を拡大する。
論文参考訳（メタデータ） (2022-09-16T06:36:06Z)
Consistency of Neural Networks with Regularization [0.0]
本稿では,ニューラルネットワークの規則化による一般的な枠組みを提案し,その一貫性を実証する。双曲関数(Tanh)と整形線形単位(ReLU)の2種類の活性化関数が検討されている。
論文参考訳（メタデータ） (2022-06-22T23:33:39Z)
On the Neural Tangent Kernel Analysis of Randomly Pruned Neural Networks [91.3755431537592]
ニューラルネットワークのニューラルカーネル(NTK)に重みのランダムプルーニングが及ぼす影響について検討する。特に、この研究は、完全に接続されたニューラルネットワークとそのランダムに切断されたバージョン間のNTKの等価性を確立する。
論文参考訳（メタデータ） (2022-03-27T15:22:19Z)
Reachability In Simple Neural Networks [2.7195102129095003]
NP-hardnessは、単純な仕様とニューラルネットワークの制限されたクラスをすでに保持していることを示す。我々は、ニューラルネットワーク検証研究のこの方向の展開の可能性について、徹底的な議論と展望を行う。
論文参考訳（メタデータ） (2022-03-15T14:25:44Z)
The mathematics of adversarial attacks in AI -- Why deep learning is unstable despite the existence of stable neural networks [69.33657875725747]
固定アーキテクチャを用いた分類問題に対するニューラルネットワークのトレーニングに基づくトレーニング手順が,不正確あるいは不安定なニューラルネットワーク(正確であれば)を生み出すことを証明している。鍵となるのは、安定かつ正確なニューラルネットワークは入力に依存する可変次元を持つ必要があり、特に、可変次元は安定性に必要な条件である。我々の結果は、正確で安定したニューラルネットワークが存在するというパラドックスを示しているが、現代のアルゴリズムはそれらを計算していない。
論文参考訳（メタデータ） (2021-09-13T16:19:25Z)
Training Neural Networks is ER-complete [0.7251305766151019]
ニューラルネットワーク、トレーニングデータ、およびしきい値を考えると、総誤差がしきい値以下であるようにニューラルネットワークにとってNPハードであることが知られていました。 ER完全であることを示すことにより、この根本的な問題を的確に決定する。これは、ER方程式の系と整数係数と実未知のの不等式が解を持つかどうかを決定することと同値であることを意味する。
論文参考訳（メタデータ） (2021-02-19T08:28:37Z)
Towards Understanding Hierarchical Learning: Benefits of Neural Representations [160.33479656108926]
この研究で、中間的神経表現がニューラルネットワークにさらなる柔軟性をもたらすことを実証する。提案手法は, 生の入力と比較して, サンプルの複雑度を向上できることを示す。この結果から, 深度が深層学習においてなぜ重要かという新たな視点が得られた。
論文参考訳（メタデータ） (2020-06-24T02:44:54Z)

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