論文の概要: Bounding the Complexity of Formally Verifying Neural Networks: A Geometric Approach

• arxiv url: http://arxiv.org/abs/2012.11761v2
• Date: Thu, 25 Mar 2021 13:17:14 GMT
• ステータス: 処理完了
• システム内更新日: 2021-04-26 07:26:58.415492
• Title: Bounding the Complexity of Formally Verifying Neural Networks: A Geometric Approach
• Title（参考訳）: 形式的検証ニューラルネットワークの複雑さの境界:幾何学的アプローチ
• Authors: James Ferlez and Yasser Shoukry
• Abstract要約: ReLUニューラルネットワーク(NN)の複雑さを正式に検証することを検討する。 本稿では,2つの異なるNNに対して,検証問題は2種類の制約を満たすことを示す。 両方のアルゴリズムは、NNパラメータをハイパープレーンを用いてNNアーキテクチャの効果に効率的に変換する。
• 参考スコア（独自算出の注目度）: 1.9493449206135296
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we consider the computational complexity of formally verifying the behavior of Rectified Linear Unit (ReLU) Neural Networks (NNs), where verification entails determining whether the NN satisfies convex polytopic specifications. Specifically, we show that for two different NN architectures -- shallow NNs and Two-Level Lattice (TLL) NNs -- the verification problem with (convex) polytopic constraints is polynomial in the number of neurons in the NN to be verified, when all other aspects of the verification problem held fixed. We achieve these complexity results by exhibiting explicit (but similar) verification algorithms for each type of architecture. Both algorithms efficiently translate the NN parameters into a partitioning of the NN's input space by means of hyperplanes; this has the effect of partitioning the original verification problem into polynomially many sub-verification problems derived from the geometry of the neurons. We show that these sub-problems may be chosen so that the NN is purely affine within each, and hence each sub-problem is solvable in polynomial time by means of a Linear Program (LP). Thus, a polynomial-time algorithm for the original verification problem can be obtained using known algorithms for enumerating the regions in a hyperplane arrangement. Finally, we adapt our proposed algorithms to the verification of dynamical systems, specifically when these NN architectures are used as state-feedback controllers for LTI systems. We further evaluate the viability of this approach numerically.
• Abstract（参考訳）: 本稿では,Rectified Linear Unit (ReLU) Neural Networks (NN) の動作を正式に検証する計算複雑性について考察する。 具体的には、浅いNNとTLL(Two-Level Lattice)という2つの異なるNNアーキテクチャに対して、(凸)ポリトピック制約の検証問題は、その検証問題の他の全ての側面が固定されている場合、NN内のニューロン数の多項式であることを示す。 各タイプのアーキテクチャに対して明示的な(しかし類似した)検証アルゴリズムを提示することで、これらの複雑さの成果を達成します。 どちらのアルゴリズムもnnパラメータをハイパープレーンによってnnの入力空間の分割に効率的に変換し、元の検証問題をニューロンの幾何から得られる多項式的に多くのサブ検証問題に分割する効果を持つ。 これらのサブプロブレムはNNが純粋にアフィンであるように選択でき、したがって各サブプロブレムは線形プログラム(LP)を用いて多項式時間で解けることを示す。 これにより、超平面配置領域を列挙する既知のアルゴリズムを用いて、元の検証問題に対する多項式時間アルゴリズムを得ることができる。 最後に、提案アルゴリズムを動的システムの検証に適用し、特にこれらのNNアーキテクチャがLTIシステムの状態フィードバックコントローラとして使用される場合について述べる。 さらに,本手法の有効性を数値的に評価する。

関連論文リスト

• Neural Networks Asymptotic Behaviours for the Resolution of Inverse Problems [0.0]
  本稿では,畳み込み逆問題に対するニューラルネットワーク(NN)手法の有効性について検討する。 NNのパラメータの非線形性を無視できるGaussian Processs(GP)に対応するNNの制限について検討する。 格子上のモンテカルロ法でシミュレートされた量子調和振動子の場合、デコンボリューション逆問題に対処する。
  論文  参考訳（メタデータ） (2024-02-14T17:42:24Z)
• Correctness Verification of Neural Networks Approximating Differential Equations [0.0]
  ニューラルネットワーク(NN)は部分微分方程式(PDE)の解を近似する NNはシミュレーションソフトウェアツールの不可欠な部分となり、複雑な動的システムのシミュレーションを100回以上加速することができる。 この研究は、NN微分を有限差分近似として定義することにより、これらの関数の検証に対処する。 初めて、出力領域の事前知識のないNN関数のバウンダリング問題に取り組む。
  論文  参考訳（メタデータ） (2024-02-12T12:55:35Z)
• Finding Nontrivial Minimum Fixed Points in Discrete Dynamical Systems [29.7237944669855]
  影響を受けるノードの最小数でシステムの非自明な固定点を求めるという新しい最適化問題を定式化する。 この計算難易度に対処するため,この問題を効率的に解決できる特別な事例をいくつか挙げる。 大規模ネットワーク上での問題を解くため,グリーディ選択法とともに汎用的なフレームワークを提案する。
  論文  参考訳（メタデータ） (2023-01-06T14:46:01Z)
• Tunable Complexity Benchmarks for Evaluating Physics-Informed Neural Networks on Coupled Ordinary Differential Equations [64.78260098263489]
  本研究では,より複雑に結合した常微分方程式(ODE)を解く物理インフォームドニューラルネットワーク(PINN)の能力を評価する。 PINNの複雑性が増大するにつれて,これらのベンチマークに対する正しい解が得られないことが示される。 PINN損失のラプラシアンは,ネットワーク容量の不足,ODEの条件の低下,局所曲率の高さなど,いくつかの理由を明らかにした。
  論文  参考訳（メタデータ） (2022-10-14T15:01:32Z)
• Universal approximation property of invertible neural networks [76.95927093274392]
  Invertible Neural Network (INN) は、設計によって可逆性を持つニューラルネットワークアーキテクチャである。 その可逆性とヤコビアンのトラクタビリティのおかげで、IGNは確率的モデリング、生成的モデリング、表現的学習など、さまざまな機械学習応用がある。
  論文  参考訳（メタデータ） (2022-04-15T10:45:26Z)
• Geometric Path Enumeration for Equivalence Verification of Neural Networks [2.007262412327553]
  2つのNNが等価な振る舞いを示すことを示すことを目的としたNN等価性の形式的検証問題に焦点をあてる。 理論的には、epsilon-equivalence問題はcoNP完全であることを示す。 第3のステップでは、等価性検証のための拡張アルゴリズムを実装し、その実用化に必要な最適化を評価する。
  論文  参考訳（メタデータ） (2021-12-13T11:56:08Z)
• Path Regularization: A Convexity and Sparsity Inducing Regularization for Parallel ReLU Networks [75.33431791218302]
  本稿では,ディープニューラルネットワークのトレーニング問題について検討し,最適化環境に隠された凸性を明らかにするための解析的アプローチを提案する。 我々は、標準のディープ・ネットワークとResNetを特別なケースとして含む、ディープ・パラレルなReLUネットワークアーキテクチャについて検討する。
  論文  参考訳（メタデータ） (2021-10-18T18:00:36Z)
• Finite Basis Physics-Informed Neural Networks (FBPINNs): a scalable domain decomposition approach for solving differential equations [20.277873724720987]
  我々はFBPINN(Finite Basis PINNs)と呼ばれる微分方程式に関連する大きな問題を解くための新しいスケーラブルなアプローチを提案する。 FBPINNは古典的有限要素法に着想を得ており、微分方程式の解はコンパクトな支持を持つ基底関数の有限集合の和として表される。 FBPINNでは、ニューラルネットワークを使ってこれらの基底関数を学習する。
  論文  参考訳（メタデータ） (2021-07-16T13:03:47Z)
• LocalDrop: A Hybrid Regularization for Deep Neural Networks [98.30782118441158]
  本稿では,ローカルラデマチャー複雑性を用いたニューラルネットワークの正規化のための新しい手法であるLocalDropを提案する。 フルコネクテッドネットワーク(FCN)と畳み込みニューラルネットワーク(CNN)の両方のための新しい正規化機能は、ローカルラデマチャー複雑さの上限提案に基づいて開発されました。
  論文  参考訳（メタデータ） (2021-03-01T03:10:11Z)
• Provably Efficient Neural Estimation of Structural Equation Model: An Adversarial Approach [144.21892195917758]
  一般化構造方程式モデル(SEM)のクラスにおける推定について検討する。 線形作用素方程式をmin-maxゲームとして定式化し、ニューラルネットワーク(NN)でパラメータ化し、勾配勾配を用いてニューラルネットワークのパラメータを学習する。 提案手法は,サンプル分割を必要とせず,確固とした収束性を持つNNをベースとしたSEMの抽出可能な推定手順を初めて提供する。
  論文  参考訳（メタデータ） (2020-07-02T17:55:47Z)
• Multipole Graph Neural Operator for Parametric Partial Differential Equations [57.90284928158383]
  物理系をシミュレーションするためのディープラーニングベースの手法を使用する際の大きな課題の1つは、物理ベースのデータの定式化である。 線形複雑度のみを用いて、あらゆる範囲の相互作用をキャプチャする、新しいマルチレベルグラフニューラルネットワークフレームワークを提案する。 実験により, 離散化不変解演算子をPDEに学習し, 線形時間で評価できることを確認した。
  論文  参考訳（メタデータ） (2020-06-16T21:56:22Z)

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

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