論文の概要: Efficient Neural Network Verification via Order Leading Exploration of Branch-and-Bound Trees
- arxiv url: http://arxiv.org/abs/2507.17453v1
- Date: Wed, 23 Jul 2025 12:20:20 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-24 22:33:14.98447
- Title: Efficient Neural Network Verification via Order Leading Exploration of Branch-and-Bound Trees
- Title（参考訳）: 分岐と境界木を探索する順序付きニューラルネットワークの有効検証
- Authors: Guanqin Zhang, Kota Fukuda, Zhenya Zhang, H. M. N. Dilum Bandara, Shiping Chen, Jianjun Zhao, Yulei Sui,
- Abstract要約: State-of-art, branch and bound (BaB) は、オフ・ザ・シェルフ検証器をサブプロブレムに適用し、より優れた性能を発揮する「分別・対数」戦略である。
本稿では,これらのサブプロブレムを優先順位付けすることで,副プロブレム空間を探索する新しい検証フレームワークであるOlivaを提案する。
Olivaには2つのバリエーションがあり、例えば$OlivaGR$は、逆例を見つけやすいサブプロブレムを常に優先する欲求戦略である。
- 参考スコア（独自算出の注目度）: 8.804277530769532
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The vulnerability of neural networks to adversarial perturbations has necessitated formal verification techniques that can rigorously certify the quality of neural networks. As the state-of-the-art, branch and bound (BaB) is a "divide-and-conquer" strategy that applies off-the-shelf verifiers to sub-problems for which they perform better. While BaB can identify the sub-problems that are necessary to be split, it explores the space of these sub-problems in a naive "first-come-first-serve" manner, thereby suffering from an issue of inefficiency to reach a verification conclusion. To bridge this gap, we introduce an order over different sub-problems produced by BaB, concerning with their different likelihoods of containing counterexamples. Based on this order, we propose a novel verification framework Oliva that explores the sub-problem space by prioritizing those sub-problems that are more likely to find counterexamples, in order to efficiently reach the conclusion of the verification. Even if no counterexample can be found in any sub-problem, it only changes the order of visiting different sub-problem and so will not lead to a performance degradation. Specifically, Oliva has two variants, including $Oliva^{GR}$, a greedy strategy that always prioritizes the sub-problems that are more likely to find counterexamples, and $Oliva^{SA}$, a balanced strategy inspired by simulated annealing that gradually shifts from exploration to exploitation to locate the globally optimal sub-problems. We experimentally evaluate the performance of Oliva on 690 verification problems spanning over 5 models with datasets MNIST and CIFAR10. Compared to the state-of-the-art approaches, we demonstrate the speedup of Oliva for up to 25X in MNIST, and up to 80X in CIFAR10.
- Abstract（参考訳）: 敵の摂動に対するニューラルネットワークの脆弱性は、ニューラルネットワークの品質を厳格に証明する形式的検証技術を必要としている。
最先端のブランチ・アンド・バウンド(BaB)は、オフ・ザ・シェルフ検証器をサブプロブレムに応用し、より優れた性能を発揮する「分割・アンド・コンカー」戦略である。
BaBは分割されるために必要なサブプロブレムを識別できるが、これらのサブプロブレムの空間を単純で「第一の第一のサービス」な方法で探索することで、検証の結論に達するための非効率性の問題に悩まされる。
このギャップを埋めるために、我々はBaBが生成する様々なサブプロブレムに対して、反例を含む可能性の異なるサブプロブレムの順序を導入する。
この順序に基づいて、検証の結論に効率よく到達するために、反例を見つける可能性がより高いサブプロブレムを優先順位付けすることで、サブプロブレム空間を探索する新しい検証フレームワークであるOlivaを提案する。
サブプロブレムに反例が見つからないとしても、異なるサブプロブレムを訪問する順序だけを変えるため、パフォーマンスが低下することはない。
具体的には、Oliva^{GR}$という、反例を見つけやすいサブプロブレムを常に優先する欲求戦略と、シミュレートされたアニーリングにインスパイアされたバランスの取れた戦略である$Oliva^{SA}$という2つの変種がある。
MNISTとCIFAR10の5モデルにまたがる690の検証問題に対するOlivaの性能を実験的に評価した。
最先端のアプローチと比較して,MNISTでは最大25倍,CIFAR10では最大80倍の速度向上を示す。
関連論文リスト
- Adaptive Branch-and-Bound Tree Exploration for Neural Network Verification [8.733719614108102]
ABONNはモンテカルロ木探索(MCTS)方式でBaBのサブプロブレム空間を適応的に探索する。
ABONNは、MNISTで最大$15.2times、CIFAR-10で$24.7timesのスピードアップを実証している。
論文 参考訳（メタデータ） (2025-05-02T02:41:02Z) - Identifying General Mechanism Shifts in Linear Causal Representations [58.6238439611389]
我々は,未知の潜在因子の線形混合を観測する線形因果表現学習環境について考察する。
近年の研究では、潜伏要因の復元や、それに基づく構造因果モデルの構築が可能であることが示されている。
非常に穏やかな標準仮定の下では、シフトしたノードの集合を識別することが可能である。
論文 参考訳（メタデータ） (2024-10-31T15:56:50Z) - Distributed Extra-gradient with Optimal Complexity and Communication
Guarantees [60.571030754252824]
複数のプロセッサ/ワーカー/クライアントがローカルなデュアルベクトルにアクセス可能なマルチGPU設定において、モノトン変分不等式(VI)問題を考察する。
モノトーンVI問題に対するデファクトアルゴリズムであるExtra-gradientは、通信効率が良くないように設計されている。
そこで本稿では,VI の解法に適した非バイアスで適応的な圧縮手法である量子化一般化外部勾配 (Q-GenX) を提案する。
論文 参考訳（メタデータ） (2023-08-17T21:15:04Z) - Towards understanding neural collapse in supervised contrastive learning with the information bottleneck method [26.874007846077884]
ニューラル崩壊(Neural collapse)とは、パフォーマンスプレートを超えてトレーニングされたディープニューラルネットワークの最終層におけるアクティベーションの幾何学である。
分類問題の最適IB解に近づくと、神経崩壊は特に良い一般化をもたらすことを実証する。
論文 参考訳（メタデータ） (2023-05-19T18:41:17Z) - Latent Feature Relation Consistency for Adversarial Robustness [80.24334635105829]
深層ニューラルネットワークは、人間の知覚できない敵のノイズを自然の例に付加する敵の例を予測するときに、誤分類が起こる。
textbfLatent textbfFeature textbfRelation textbfConsistency (textbfLFRC)を提案する。
LFRCは、潜在空間における逆例の関係を、自然例と整合性に制約する。
論文 参考訳（メタデータ） (2023-03-29T13:50:01Z) - Distributionally Robust Bayesian Optimization with $\varphi$-divergences [45.48814080654241]
我々は,$varphi$-divergencesにおけるデータシフトに対するロバスト性について考察する。
この設定におけるDRO-BO問題は有限次元最適化問題と等価であり、連続的な文脈でも証明可能な部分線型後悔境界で容易に実装できることを示す。
論文 参考訳（メタデータ） (2022-03-04T04:34:52Z) - Deep Hierarchy in Bandits [51.22833900944146]
行動の報酬は、しばしば相関する。
統計的効率を最大化するためには,これらの相関を学習に活用することが重要である。
平均作用報酬の相関が階層的ベイズモデルで表されるこの問題のバンディット変法を定式化する。
論文 参考訳（メタデータ） (2022-02-03T08:15:53Z) - Mapping conditional distributions for domain adaptation under
generalized target shift [0.0]
我々は、条件シフトとラベルシフト(GeTarS)の下でのソースとターゲットドメイン間の教師なしドメイン適応(UDA)の問題を考える。
最近のアプローチでは、ドメイン不変表現を学習するが、実際的な制限があり、実際には成り立たない強い仮定に依存している。
本稿では,既存の欠点を回避した,事前訓練された表現の整合化のための,新規で汎用的なアプローチについて検討する。
論文 参考訳（メタデータ） (2021-10-26T14:25:07Z) - Global Optimization of Objective Functions Represented by ReLU Networks [77.55969359556032]
ニューラルネットワークは複雑で非敵対的な関数を学ぶことができ、安全クリティカルな文脈でそれらの正しい振る舞いを保証することは困難である。
ネットワーク内の障害を見つけるための多くのアプローチ(例えば、敵の例)があるが、これらは障害の欠如を保証できない。
本稿では,最適化プロセスを検証手順に統合し,本手法よりも優れた性能を実現する手法を提案する。
論文 参考訳（メタデータ） (2020-10-07T08:19:48Z) - Continuous Profit Maximization: A Study of Unconstrained Dr-submodular
Maximization [4.649999862713523]
我々は、整数格子上の領域である連続利益(CPM-MS)問題を形成する。
格子に基づく二重グリードアルゴリズムを導入し, 定数近似を求める。
本稿では,格子型反復プルーニング手法を提案し,探索空間を効果的に縮小することができる。
論文 参考訳（メタデータ） (2020-04-12T05:35:19Z) - The Simulator: Understanding Adaptive Sampling in the
Moderate-Confidence Regime [52.38455827779212]
エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。
適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。
我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
論文 参考訳（メタデータ） (2017-02-16T23:42:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。