論文の概要: Geometric Path Enumeration for Equivalence Verification of Neural
Networks
- arxiv url: http://arxiv.org/abs/2112.06582v1
- Date: Mon, 13 Dec 2021 11:56:08 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-14 16:30:38.436200
- Title: Geometric Path Enumeration for Equivalence Verification of Neural
Networks
- Title(参考訳): ニューラルネットワークの等価性検証のための幾何経路列挙法
- Authors: Samuel Teuber, Marko Kleine B\"uning, Philipp Kern and Carsten Sinz
- Abstract要約: 2つのNNが等価な振る舞いを示すことを示すことを目的としたNN等価性の形式的検証問題に焦点をあてる。
理論的には、epsilon-equivalence問題はcoNP完全であることを示す。
第3のステップでは、等価性検証のための拡張アルゴリズムを実装し、その実用化に必要な最適化を評価する。
- 参考スコア(独自算出の注目度): 2.007262412327553
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: As neural networks (NNs) are increasingly introduced into safety-critical
domains, there is a growing need to formally verify NNs before deployment. In
this work we focus on the formal verification problem of NN equivalence which
aims to prove that two NNs (e.g. an original and a compressed version) show
equivalent behavior. Two approaches have been proposed for this problem: Mixed
integer linear programming and interval propagation. While the first approach
lacks scalability, the latter is only suitable for structurally similar NNs
with small weight changes.
The contribution of our paper has four parts. First, we show a theoretical
result by proving that the epsilon-equivalence problem is coNP-complete.
Secondly, we extend Tran et al.'s single NN geometric path enumeration
algorithm to a setting with multiple NNs. In a third step, we implement the
extended algorithm for equivalence verification and evaluate optimizations
necessary for its practical use. Finally, we perform a comparative evaluation
showing use-cases where our approach outperforms the previous state of the art,
both, for equivalence verification as well as for counter-example finding.
- Abstract(参考訳): ニューラルネットワーク(NN)が安全クリティカルなドメインにますます導入されているため、デプロイメント前にNNを正式に検証する必要がある。
本研究では,2つのNN(例えばオリジナル版と圧縮版)が等価動作を示すことを示すことを目的としたNN等価性の形式的検証問題に焦点を当てる。
この問題に対して,混合整数線形計画法と区間伝播法という2つのアプローチが提案されている。
最初のアプローチはスケーラビリティに欠けるが、後者は構造的に類似したNNにしか適していない。
論文の寄稿には4つの部分がある。
まず、epsilon-equivalence問題がcoNP完全であることを証明して理論的結果を示す。
第二に、Tran et al. の 1 つの NN 幾何経路列挙アルゴリズムを複数の NN を用いた設定に拡張する。
第3段階として,等価性検証のための拡張アルゴリズムを実装し,その実用化に必要な最適化を評価する。
最後に、同値検証と反例探索の両方において、我々のアプローチが過去の最先端技術よりも優れたユースケースを示す比較評価を行う。
関連論文リスト
- A Fresh Look at Generalized Category Discovery through Non-negative Matrix Factorization [83.12938977698988]
Generalized Category Discovery (GCD) は、ラベル付きベースデータを用いて、ベース画像と新規画像の両方を分類することを目的としている。
現在のアプローチでは、コサイン類似性に基づく共起行列 $barA$ の固有の最適化に不適切に対処している。
本稿では,これらの欠陥に対処するNon-Negative Generalized Category Discovery (NN-GCD) フレームワークを提案する。
論文 参考訳(メタデータ) (2024-10-29T07:24:11Z) - Neural Network Verification with Branch-and-Bound for General Nonlinearities [63.39918329535165]
ブランチ・アンド・バウンド(BaB)は、ニューラルネットワーク(NN)検証において最も効果的な手法の一つである。
我々は、一般的な非線形性にBaBを実行し、一般的なアーキテクチャでNNを検証する汎用フレームワークGenBaBを開発した。
我々は、Sigmoid、Tanh、Sine、GeLUなどの活性化機能を持つNNを含む幅広いNNの検証におけるGenBaBの有効性を実証する。
論文 参考訳(メタデータ) (2024-05-31T17:51:07Z) - Correctness Verification of Neural Networks Approximating Differential
Equations [0.0]
ニューラルネットワーク(NN)は部分微分方程式(PDE)の解を近似する
NNはシミュレーションソフトウェアツールの不可欠な部分となり、複雑な動的システムのシミュレーションを100回以上加速することができる。
この研究は、NN微分を有限差分近似として定義することにより、これらの関数の検証に対処する。
初めて、出力領域の事前知識のないNN関数のバウンダリング問題に取り組む。
論文 参考訳(メタデータ) (2024-02-12T12:55:35Z) - Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。
最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
論文 参考訳(メタデータ) (2023-10-20T12:45:12Z) - Deep Learning meets Nonparametric Regression: Are Weight-Decayed DNNs Locally Adaptive? [16.105097124039602]
古典的非パラメトリック回帰問題のレンズからニューラルネットワーク(NN)の理論を研究する。
私たちの研究は、なぜ深さが重要なのか、そしてNNがカーネルメソッドよりも強力であるかについて、新たな光を当てています。
論文 参考訳(メタデータ) (2022-04-20T17:55:16Z) - Neural Network Branch-and-Bound for Neural Network Verification [26.609606492971967]
本稿では,効率的な分岐戦略を設計するための新しい機械学習フレームワークを提案する。
グラフ入力として検証したいネットワークを直接扱う2つのグラフニューラルネットワーク(GNN)を学習する。
我々のGNNモデルは、より大きな未確認ネットワーク上での厳しい特性に対してよく一般化されていることを示す。
論文 参考訳(メタデータ) (2021-07-27T14:42:57Z) - Neural Optimization Kernel: Towards Robust Deep Learning [13.147925376013129]
近年の研究では、ニューラルネットワーク(NN)とカーネルメソッドの関連性が示されている。
本稿では,カーネル(NOK)という新しいカーネルファミリーを提案する。
パラメータ化ディープNN(NOK)は,経験的リスクを低減し,有界一般化を同時に低減できることを示す。
論文 参考訳(メタデータ) (2021-06-11T00:34:55Z) - A Convergence Theory Towards Practical Over-parameterized Deep Neural
Networks [56.084798078072396]
ネットワーク幅と収束時間の両方で既知の理論境界を大幅に改善することにより、理論と実践のギャップを埋める一歩を踏み出します。
本研究では, サンプルサイズが2次幅で, 両者の時間対数で線形なネットワークに対して, 地球最小値への収束が保証されていることを示す。
私たちの分析と収束境界は、いつでも合理的なサイズの同等のRELUネットワークに変換できる固定アクティベーションパターンを備えたサロゲートネットワークの構築によって導出されます。
論文 参考訳(メタデータ) (2021-01-12T00:40:45Z) - Bounding the Complexity of Formally Verifying Neural Networks: A
Geometric Approach [1.9493449206135296]
ReLUニューラルネットワーク(NN)の複雑さを正式に検証することを検討する。
本稿では,2つの異なるNNに対して,検証問題は2種類の制約を満たすことを示す。
両方のアルゴリズムは、NNパラメータをハイパープレーンを用いてNNアーキテクチャの効果に効率的に変換する。
論文 参考訳(メタデータ) (2020-12-22T00:29:54Z) - Fast Learning of Graph Neural Networks with Guaranteed Generalizability:
One-hidden-layer Case [93.37576644429578]
グラフニューラルネットワーク(GNN)は、グラフ構造化データから実際に学習する上で、近年大きな進歩を遂げている。
回帰問題と二項分類問題の両方に隠れ層を持つGNNの理論的に基底的な一般化可能性解析を行う。
論文 参考訳(メタデータ) (2020-06-25T00:45:52Z) - Optimization and Generalization Analysis of Transduction through
Gradient Boosting and Application to Multi-scale Graph Neural Networks [60.22494363676747]
現在のグラフニューラルネットワーク(GNN)は、オーバースムーシング(over-smoothing)と呼ばれる問題のため、自分自身を深くするのは難しいことが知られている。
マルチスケールGNNは、オーバースムーシング問題を緩和するための有望なアプローチである。
マルチスケールGNNを含むトランスダクティブ学習アルゴリズムの最適化と一般化を保証する。
論文 参考訳(メタデータ) (2020-06-15T17:06:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。