論文の概要: Mining Verdict Boundaries for Neural Network Verification
- arxiv url: http://arxiv.org/abs/2607.28954v1
- Date: Fri, 31 Jul 2026 02:16:55 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-03 14:29:40.564725
- Title: Mining Verdict Boundaries for Neural Network Verification
- Title（参考訳）: ニューラルネットワーク検証のためのマイニング検証境界
- Abstract要約: ブランチとバウンドは、問題を適応的に分割し、オフザシェルフ検証器をサブプロブレムに適用することで、ニューラルネットワークの完全な検証を実現することを目的としている。
BaBの重要な問題は、検証されたサブプロブレムと検証されていないサブプロブレムを分割する全てのパスの検証境界を探すことである。
本研究では,各経路の単調性を有効利用し,検証境界を効率よく正確に特定する探索手法を提案する。
- 参考スコア（独自算出の注目度）: 10.091802208162585
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Branch and Bound (BaB) aims to achieve complete verification of neural networks by adaptively partitioning the problem and applying off-the-shelf verifiers to subproblems. Its problem-splitting history can be represented as a tree, where each subproblem corresponds to a child node. A key problem of BaB lies in searching for the verdict boundaries across all the paths that divide the verified and unverified subproblems. We observe that the existing BaB approach tackles this problem by solving each expensive subproblem sequentially along the tree path as its depth increases, requiring costly bounds propagation at every visited BaB tree node (i.e., subproblem), which is inefficient. To address this issue, we propose effective search approaches that leverage the monotonicity of each path to efficiently and precisely locate the verdict boundary by simultaneously splitting multiple activation functions (e.g., ReLU), rather than processing them one at a time as in the classical approach. Our approach performs an effective exponential search along each path, allowing us to skip many boundary-unrelated subproblems when identifying the verdict boundary. The enhanced version further improves this process by estimating the boundary's position using quantitative information obtained from subproblem solving. We perform experimental evaluation on commonly-used benchmarks to assess our proposed techniques, and compare them with recent BaB-based approaches.
- Abstract（参考訳）: ブランチとバウンド(BaB)は、問題を適応的に分割し、オフザシェルフ検証をサブプロブレムに適用することで、ニューラルネットワークの完全な検証を実現することを目的としている。
その問題分割履歴は木として表現することができ、各サブプロブレムは子ノードに対応する。
BaBの重要な問題は、検証されたサブプロブレムと検証されていないサブプロブレムを分割する全てのパスの検証境界を探すことである。
既存のBaBアプローチでは,木道に沿って各高価なサブプロブレムを逐次解決し,その深さが増加するにつれて,訪問するBaBツリーノード(すなわちサブプロブレム)毎にコストのかかるバウンダリを伝搬させることで,この問題に対処する。
そこで本研究では,各経路の単調性を利用した効率的な探索手法を提案し,複数のアクティベーション関数(例えばReLU)を同時に分割することで,従来の手法のように1回に1回処理するのではなく,検証境界を効率的に正確に特定する。
提案手法は各経路に沿って効果的な指数探索を行い,検証境界を特定する際に境界非関係のサブプロブレムの多くをスキップすることができる。
拡張されたバージョンは、サブプロブレム解から得られた定量的情報を用いて境界位置を推定することにより、このプロセスをさらに改善する。
提案手法の評価によく用いられるベンチマークを実験的に評価し,最近のBaBベースの手法と比較した。
関連論文リスト
- How Many Trees in a Random Forest? A Revisited Approach with Plateau Search and Optuna Integration [0.30586855806896046]
ランダムフォレストのためのHPOのための統合三重項ベースプラトー探索アルゴリズムを提案する。
この方法は、バッグ外スコアの相対的な変化を監視して、最小に近い十分なアンサンブルサイズを適応的に追跡する。
実験により、選択された木の数は共通の絶対値と大きく異なることが示されている。
論文 参考訳（メタデータ） (2026-06-02T12:10:43Z) - BaB-prob: Branch and Bound with Preactivation Splitting for Probabilistic Verification of Neural Networks [13.26751081683149]
プレアクティベーション分割を伴う分岐とバウンドは、ニューラルネットワークの決定論的検証に非常に有効であることが示されている。
そこで本稿では,前処理を分割することで,元の問題をサブプロブレムに反復的に分割するBaB-probを提案する。
フィードフォワード・ReLUニューラルネットワークにおけるBaB-probの健全性と完全性を証明する。
論文 参考訳（メタデータ） (2025-09-30T01:39:39Z) - Efficient Neural Network Verification via Order Leading Exploration of Branch-and-Bound Trees [8.804277530769532]
State-of-art, branch and bound (BaB) は、オフ・ザ・シェルフ検証器をサブプロブレムに適用し、より優れた性能を発揮する「分別・対数」戦略である。
本稿では,これらのサブプロブレムを優先順位付けすることで,副プロブレム空間を探索する新しい検証フレームワークであるOlivaを提案する。
Olivaには2つのバリエーションがあり、例えば$OlivaGR$は、逆例を見つけやすいサブプロブレムを常に優先する欲求戦略である。
論文 参考訳（メタデータ） (2025-07-23T12:20:20Z) - 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) - Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。
赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
論文 参考訳（メタデータ） (2024-06-21T05:57:08Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - Decision Diagram-Based Branch-and-Bound with Caching for Dominance and
Suboptimality Detection [9.175779296469194]
本稿では動的プログラミングモデルの構造を利用して探索を高速化する新しい要素を提案する。
鍵となる考え方は、検索中にキャッシュされた拡張しきい値に問い合わせることによって、同じ動的プログラミング状態に対応するノードの繰り返し拡張を防止することである。
このキャッシング機構によって引き起こされるプルーニングは、アルゴリズムによって拡張されたノード数を著しく削減できることを示す実験である。
論文 参考訳（メタデータ） (2022-11-22T10:18:33Z) - Quant-BnB: A Scalable Branch-and-Bound Method for Optimal Decision Trees
with Continuous Features [5.663538370244174]
本稿では,分岐とバウンド(BnB)に基づく新たな離散最適化手法を提案する。
提案アルゴリズムのQuant-BnBは,様々な実データセット上での浅い最適木に対する既存手法と比較して,大幅な高速化を示す。
論文 参考訳（メタデータ） (2022-06-23T17:19:29Z) - Frequent Itemset-driven Search for Finding Minimum Node Separators in
Complex Networks [61.2383572324176]
本稿では,データマイニングにおける頻繁なアイテムセットマイニングの概念をよく知られたメメティック検索フレームワークに統合する,頻繁なアイテムセット駆動探索手法を提案する。
頻繁なアイテムセット組換え演算子を反復的に使用して、高品質なソリューションで頻繁に発生するアイテムセットに基づいた有望な子孫ソリューションを生成する。
特に、29個の新しい上界を発見し、以前の18個の最もよく知られた境界と一致する。
論文 参考訳（メタデータ） (2022-01-18T11:16:40Z) - Improved Branch and Bound for Neural Network Verification via Lagrangian
Decomposition [161.09660864941603]
ニューラルネットワークの入出力特性を公式に証明するためのブランチとバウンド(BaB)アルゴリズムのスケーラビリティを改善します。
活性化に基づく新しい分岐戦略とBaBフレームワークであるブランチとデュアルネットワーク境界(BaDNB)を提案する。
BaDNBは、従来の完全検証システムを大きなマージンで上回り、対数特性で平均検証時間を最大50倍に削減した。
論文 参考訳（メタデータ） (2021-04-14T09:22:42Z) - Batched Neural Bandits [107.5072688105936]
BatchNeuralUCBはニューラルネットワークと楽観性を組み合わせ、探索と探索のトレードオフに対処する。
BatchNeuralUCBは、完全なシーケンシャルバージョンと同じ後悔を達成しつつ、ポリシー更新の数を大幅に減らしています。
論文 参考訳（メタデータ） (2021-02-25T17:36:44Z) - Solving Sparse Linear Inverse Problems in Communication Systems: A Deep
Learning Approach With Adaptive Depth [51.40441097625201]
疎信号回復問題に対するエンドツーエンドの訓練可能なディープラーニングアーキテクチャを提案する。
提案手法は,出力するレイヤ数を学習し,各タスクのネットワーク深さを推論フェーズで動的に調整する。
論文 参考訳（メタデータ） (2020-10-29T06:32:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。