論文の概要: Towards Optimal Branching of Linear and Semidefinite Relaxations for Neural Network Robustness Certification
- arxiv url: http://arxiv.org/abs/2101.09306v3
- Date: Tue, 17 Sep 2024 17:15:57 GMT
- ステータス: 処理完了
- システム内更新日: 2024-09-18 23:07:58.012734
- Title: Towards Optimal Branching of Linear and Semidefinite Relaxations for Neural Network Robustness Certification
- Title（参考訳）: ニューラルネットワークロバスト性認証のための線形・半有限緩和の最適分岐に向けて
- Authors: Brendon G. Anderson, Ziye Ma, Jingqi Li, Somayeh Sojoudi,
- Abstract要約: 本研究では,ReLUニューラルネットワークの逆入力摂動に対する堅牢性を検証する。
入力不確実性集合を分割し,各部分の緩和を個別に解くために,分岐とバウンドのアプローチをとる。
提案手法は緩和誤差を低減し,ReLUアクティベーションの性質を活かしたパーティションを用いてLP緩和を行うことによって完全に誤差を除去することを示す。
- 参考スコア（独自算出の注目度）: 10.349616734896522
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we study certifying the robustness of ReLU neural networks against adversarial input perturbations. To diminish the relaxation error suffered by the popular linear programming (LP) and semidefinite programming (SDP) certification methods, we take a branch-and-bound approach to propose partitioning the input uncertainty set and solving the relaxations on each part separately. We show that this approach reduces relaxation error, and that the error is eliminated entirely upon performing an LP relaxation with a partition intelligently designed to exploit the nature of the ReLU activations. To scale this approach to large networks, we consider using a coarser partition whereby the number of parts in the partition is reduced. We prove that computing such a coarse partition that directly minimizes the LP relaxation error is NP-hard. By instead minimizing the worst-case LP relaxation error, we develop a closed-form branching scheme in the single-hidden layer case. We extend the analysis to the SDP, where the feasible set geometry is exploited to design a branching scheme that minimizes the worst-case SDP relaxation error. Experiments on MNIST, CIFAR-10, and Wisconsin breast cancer diagnosis classifiers demonstrate significant increases in the percentages of test samples certified. By independently increasing the input size and the number of layers, we empirically illustrate under which regimes the branched LP and branched SDP are best applied. Finally, we extend our LP branching method into a multi-layer branching heuristic, which attains comparable performance to prior state-of-the-art heuristics on large-scale, deep neural network certification benchmarks.
- Abstract（参考訳）: 本稿では,ReLUニューラルネットワークの逆入力摂動に対する堅牢性を検証する。
一般の線形プログラミング (LP) と半定値プログラミング (SDP) の認証手法が抱える緩和誤差を低減させるため,入力の不確実性集合の分割と各部分の緩和の解法を分割的に提案する分岐とバウンドの手法を採用する。
提案手法は緩和誤差を低減し,ReLUアクティベーションの特性を活用するために設計されたパーティションを用いてLP緩和を行うことによって完全に誤差を除去することを示す。
提案手法を大規模ネットワークに拡張するために,分割する部分の数を削減した粗いパーティションを用いることを検討する。
LP緩和誤差を直接最小化する粗いパーティションの計算がNPハードであることを証明する。
最悪ケースのLP緩和誤差を最小化する代わりに, 単一隠れ層の場合において, 閉形式分岐方式を開発する。
解析をSDPに拡張し、実現可能な集合の幾何を利用して、最悪のSDP緩和誤差を最小限に抑える分岐スキームを設計する。
MNIST, CIFAR-10, ウィスコンシン乳がん診断分類器を用いた実験では, 検体検体の割合が有意に増加した。
入力サイズと層数を独立に増加させることで、分岐LPと分岐SDPがどの状態に最も適しているかを実証的に示す。
最後に、LP分岐法を多層分岐ヒューリスティックに拡張し、大規模なディープニューラルネットワーク認証ベンチマークにおける最先端ヒューリスティックに匹敵する性能を得る。
関連論文リスト
- Robust Stochastically-Descending Unrolled Networks [85.6993263983062]
Deep Unrolling(ディープ・アンローリング)は、トレーニング可能なニューラルネットワークの層に切り捨てられた反復アルゴリズムをアンロールする、新たな学習最適化手法である。
アンロールネットワークの収束保証と一般化性は、いまだにオープンな理論上の問題であることを示す。
提案した制約の下で訓練されたアンロールアーキテクチャを2つの異なるアプリケーションで数値的に評価する。
論文 参考訳（メタデータ） (2023-12-25T18:51:23Z) - A Unified View of SDP-based Neural Network Verification through
Completely Positive Programming [27.742278216854714]
完全正のプログラム(CPP)としての検証の正確で凸な定式化を開発する。
我々の定式化は最小限であり、基本的にニューラルネットワークの計算を誤って表現する制約の除去であることを示す分析を提供する。
論文 参考訳（メタデータ） (2022-03-06T19:23:09Z) - Certifiable Outlier-Robust Geometric Perception: Exact Semidefinite
Relaxations and Scalable Global Optimization [29.738513596063946]
本稿では,外接点の存在下でのロバストな幾何学的知覚のためのアルゴリズム設計のための,最初の汎用フレームワークを提案する。
我々の実験では、SDP緩和はアプリケーション間で最大で外れ率で正確であることを実証した。
論文 参考訳（メタデータ） (2021-09-07T21:42:16Z) - DeepSplit: Scalable Verification of Deep Neural Networks via Operator
Splitting [70.62923754433461]
入力摂動に対するディープニューラルネットワークの最悪の性能を分析することは、大規模な非最適化問題の解決につながる。
解析解を持つ小さなサブプロブレムに分割することで,問題の凸緩和を直接高精度に解ける新しい手法を提案する。
論文 参考訳（メタデータ） (2021-06-16T20:43:49Z) - STRIDE along Spectrahedral Vertices for Solving Large-Scale Rank-One
Semidefinite Relaxations [27.353023427198806]
我々は、制約のない最適化問題(POP)の高次半定値プログラミング緩和を考察する。
POPから独立してSDPを解く既存のアプローチは、そのようなSDPの典型的な非エネルギー性のため、大きな問題にスケールできないか、あるいは緩やかな収束に苦しむことができない。
我々は SpecTrahedral vErtices (STRIDE) と呼ばれる新しいアルゴリズムフレームワークを提案する。
論文 参考訳（メタデータ） (2021-05-28T18:07:16Z) - Fast and Complete: Enabling Complete Neural Network Verification with
Rapid and Massively Parallel Incomplete Verifiers [112.23981192818721]
BaB プロセス中に線形計画法 (LP) を置き換えるために, 逆モード線形緩和に基づく解析法 (LiRPA) を提案する。
LPとは異なり、LiRPAを適用すると、より弱い境界が得られ、分割時にサブドメインのコンフリクトをチェックすることもできない。
既存のLPベースのアプローチと比較して、桁違いのスピードアップを示す。
論文 参考訳（メタデータ） (2020-11-27T16:42:12Z) - Investigating the Scalability and Biological Plausibility of the
Activation Relaxation Algorithm [62.997667081978825]
アクティベーション・リラクシエーション(AR)アルゴリズムは、誤りアルゴリズムのバックプロパゲーションを近似するためのシンプルでロバストなアプローチを提供する。
このアルゴリズムは、学習可能な後方重みセットを導入することにより、さらに単純化され、生物学的に検証可能であることを示す。
また、元のARアルゴリズム(凍結フィードフォワードパス)の別の生物学的に信じられない仮定が、パフォーマンスを損なうことなく緩和できるかどうかについても検討する。
論文 参考訳（メタデータ） (2020-10-13T08:02:38Z) - One Ring to Rule Them All: Certifiably Robust Geometric Perception with
Outliers [32.1176248075545]
本稿では,大量の外れ値が存在する場合の認識のための認証アルゴリズムを設計するための,最初の汎用的かつ実用的な手法を提案する。
我々の双対証明器は任意の問題の解の最適部分最適性を利用する。
論文 参考訳（メタデータ） (2020-06-11T19:46:42Z) - Scaling Equilibrium Propagation to Deep ConvNets by Drastically Reducing
its Gradient Estimator Bias [65.13042449121411]
実際には、EPによって提供される勾配推定によるネットワークのトレーニングは、MNISTよりも難しい視覚タスクにスケールしない。
有限ヌード法に固有のEPの勾配推定のバイアスがこの現象の原因であることを示す。
これらの手法を適用し、非対称な前方および後方接続を持つアーキテクチャをトレーニングし、13.2%のテストエラーを発生させる。
論文 参考訳（メタデータ） (2020-06-06T09:36:07Z) - Tightened Convex Relaxations for Neural Network Robustness Certification [10.68833097448566]
我々は、ReLUネットワークの構造を利用して、新しいパーティションベースの認証手順により緩和誤差を改善する。
提案手法は, 既存の線形プログラミング緩和を厳格化することが証明され, 結果がより微細になるにつれて, 緩和誤差がゼロとなる。
論文 参考訳（メタデータ） (2020-04-01T16:59:21Z) - Log-Likelihood Ratio Minimizing Flows: Towards Robust and Quantifiable
Neural Distribution Alignment [52.02794488304448]
そこで本研究では,対数様比統計量と正規化フローに基づく新しい分布アライメント手法を提案する。
入力領域の局所構造を保存する領域アライメントにおいて,結果の最小化を実験的に検証する。
論文 参考訳（メタデータ） (2020-03-26T22:10:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。