論文の概要: Reachability In Simple Neural Networks

• arxiv url: http://arxiv.org/abs/2203.07941v4
• Date: Wed, 11 Oct 2023 09:07:24 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-16 04:42:34.003540
• Title: Reachability In Simple Neural Networks
• Title（参考訳）: 単純なニューラルネットワークにおける到達可能性
• Authors: Marco S\"alzer and Martin Lange
• Abstract要約: NP-hardnessは、単純な仕様とニューラルネットワークの制限されたクラスをすでに保持していることを示す。 我々は、ニューラルネットワーク検証研究のこの方向の展開の可能性について、徹底的な議論と展望を行う。
• 参考スコア（独自算出の注目度）: 2.7195102129095003
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.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 specifications over the input/output dimension given by conjunctions of linear inequalities. We recapitulate the proof and repair some flaws in the original upper and lower bound proofs. Motivated by the general result, we show that NP-hardness already holds for restricted classes of simple specifications and neural networks. Allowing for a single hidden layer and an output dimension of one as well as neural networks with just one negative, zero and one positive weight or bias is sufficient to ensure NP-hardness. Additionally, we give a thorough discussion and outlook of possible extensions for this direction of research on neural network verification.
• Abstract（参考訳）: 我々は、(深度)ニューラルネットワークの到達可能性問題の複雑さを調査し、有効な入力が与えられたとき、有効な出力を計算するか? この問題は一般のニューラルネットワークに対してNP完全であり、線形不等式の接続によって与えられる入力/出力次元に関する仕様である。 我々は、証明を再結合し、元の上界と下界の証明のいくつかの欠陥を修復する。 この結果から,NP-hardnessはすでに,単純な仕様とニューラルネットワークの制限されたクラスに当てはまることを示した。 1つの隠蔽層と1の出力次元と1つの負のゼロと1つの正の重みまたはバイアスを持つニューラルネットワークが与えられると、NPハードネスを確保するのに十分である。 さらに,ニューラルネットワーク検証研究の方向性について,その拡張可能性に関する詳細な議論と展望を行う。

関連論文リスト

• Verified Neural Compressed Sensing [58.98637799432153]
  精度の高い計算タスクのために、初めて(私たちの知識を最大限に活用するために)証明可能なニューラルネットワークを開発します。 極小問題次元(最大50)では、線形および双項線形測定からスパースベクトルを確実に回復するニューラルネットワークを訓練できることを示す。 ネットワークの複雑さは問題の難易度に適応できることを示し、従来の圧縮センシング手法が証明不可能な問題を解く。
  論文  参考訳（メタデータ） (2024-05-07T12:20:12Z)
• Neural Networks with Sparse Activation Induced by Large Bias: Tighter Analysis with Bias-Generalized NTK [86.45209429863858]
  ニューラル・タンジェント・カーネル(NTK)における一層ReLUネットワークのトレーニングについて検討した。 我々は、ニューラルネットワークが、テクティトビア一般化NTKと呼ばれる異なる制限カーネルを持っていることを示した。 ニューラルネットの様々な特性をこの新しいカーネルで研究する。
  論文  参考訳（メタデータ） (2023-01-01T02:11:39Z)
• 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)
• 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)
• Reachability Is NP-Complete Even for the Simplest Neural Networks [0.0]
  この問題は、一般的なニューラルネットワークと共役入力/出力仕様に対してNP完全である、と最近主張された。 NP-hardnessは1層のみの単純な仕様とニューラルネットワークの制限されたクラスをすでに保持していることを示す。
  論文  参考訳（メタデータ） (2021-08-30T12:38:57Z)
• The Separation Capacity of Random Neural Networks [78.25060223808936]
  標準ガウス重みと一様分布バイアスを持つ十分に大きな2層ReLUネットワークは、この問題を高い確率で解くことができることを示す。 我々は、相互複雑性という新しい概念の観点から、データの関連構造を定量化する。
  論文  参考訳（メタデータ） (2021-07-31T10:25:26Z)
• Training Neural Networks is ER-complete [0.7251305766151019]
  ニューラルネットワーク、トレーニングデータ、およびしきい値を考えると、総誤差がしきい値以下であるようにニューラルネットワークにとってNPハードであることが知られていました。 ER完全であることを示すことにより、この根本的な問題を的確に決定する。 これは、ER方程式の系と整数係数と実未知のの不等式が解を持つかどうかを決定することと同値であることを意味する。
  論文  参考訳（メタデータ） (2021-02-19T08:28:37Z)
• Input Hessian Regularization of Neural Networks [31.941188983286207]
  本稿では,Hessian演算子-ノルム正規化を用いたディープニューラルネットワークの学習アルゴリズムを提案する。 我々は、新しい正規化器が実際に実現可能であること、さらに入力勾配正規化よりもニューラルネットワークの堅牢性を高めることを示している。
  論文  参考訳（メタデータ） (2020-09-14T16:58:16Z)

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

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