論文の概要: 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段階として,等価性検証のための拡張アルゴリズムを実装し,その実用化に必要な最適化を評価する。
最後に、同値検証と反例探索の両方において、我々のアプローチが過去の最先端技術よりも優れたユースケースを示す比較評価を行う。
関連論文リスト
- 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) - Information Bottleneck Analysis of Deep Neural Networks via Lossy
Compression [55.41644538483948]
Information Bottleneck(IB)原則は、ディープニューラルネットワーク(DNN)のトレーニングプロセスを分析するための情報理論フレームワークを提供する。
本稿では,一般NNのICB解析のための包括的フレームワークを提案する。
論文 参考訳(メタデータ) (2023-05-13T21:44:32Z) - AskewSGD : An Annealed interval-constrained Optimisation method to train
Quantized Neural Networks [12.229154524476405]
我々は、深層ニューラルネットワーク(DNN)を量子化重みでトレーニングするための新しいアルゴリズム、Annealed Skewed SGD - AskewSGDを開発した。
アクティブなセットと実行可能な方向を持つアルゴリズムとは異なり、AskewSGDは実行可能な全セットの下でのプロジェクションや最適化を避けている。
実験結果から,AskewSGDアルゴリズムは古典的ベンチマークの手法と同等以上の性能を示した。
論文 参考訳(メタデータ) (2022-11-07T18:13:44Z) - Towards Better Out-of-Distribution Generalization of Neural Algorithmic
Reasoning Tasks [51.8723187709964]
ニューラルネットワーク推論タスクのOOD一般化について検討する。
目標は、ディープニューラルネットワークを使用して入出力ペアからアルゴリズムを学ぶことである。
論文 参考訳(メタデータ) (2022-11-01T18:33:20Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。