論文の概要: 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層のみの単純な仕様とニューラルネットワークの制限クラスと,発生パラメータの最小要件を持つニューラルネットワークに対してすでに保持されていることを示す。
関連論文リスト
- 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) - Fixed-Point Code Synthesis For Neural Networks [0.0]
固定点算術を用いて、すでに訓練済みのニューラルネットワークのフォーマット(精度)を調整するための新しい手法が導入された。
新たな最適化されたニューラルネットワークは、ユーザによって固定されたしきい値まで精度を変更することなく、その出力を固定点数で計算する。
論文 参考訳(メタデータ) (2022-02-04T12:02:54Z) - 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) - How Neural Networks Extrapolate: From Feedforward to Graph Neural
Networks [80.55378250013496]
勾配勾配降下法によりトレーニングされたニューラルネットワークが、トレーニング分布の支持の外で学んだことを外挿する方法について検討する。
グラフニューラルネットワーク(GNN)は、より複雑なタスクでいくつかの成功を収めている。
論文 参考訳(メタデータ) (2020-09-24T17:48:59Z) - Extending Answer Set Programs with Neural Networks [2.512827436728378]
ニューラルネットワークを導入することで、応答セットプログラムをシンプルに拡張するNeurASPを提案する。
我々は、NeurASPがトレーニング済みニューラルネットワークの知覚精度を向上できるだけでなく、論理ルールによる制約を与えることで、ニューラルネットワークをより良くトレーニングできることを示した。
論文 参考訳(メタデータ) (2020-09-22T00:52:30Z) - Towards Understanding Hierarchical Learning: Benefits of Neural
Representations [160.33479656108926]
この研究で、中間的神経表現がニューラルネットワークにさらなる柔軟性をもたらすことを実証する。
提案手法は, 生の入力と比較して, サンプルの複雑度を向上できることを示す。
この結果から, 深度が深層学習においてなぜ重要かという新たな視点が得られた。
論文 参考訳(メタデータ) (2020-06-24T02:44:54Z) - Efficient Integer-Arithmetic-Only Convolutional Neural Networks [87.01739569518513]
我々は従来のReLUを境界ReLUに置き換え、その減少は活性化量子化によるものであることを示す。
我々の整数ネットワークは、対応するFPNネットワークと同等の性能を発揮するが、メモリコストは1/4に過ぎず、最新のGPUでは2倍高速である。
論文 参考訳(メタデータ) (2020-06-21T08:23:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。