論文の概要: On $\ell_p$-norm Robustness of Ensemble Stumps and Trees
- arxiv url: http://arxiv.org/abs/2008.08755v2
- Date: Tue, 29 Sep 2020 06:13:02 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-27 02:56:33.983249
- Title: On $\ell_p$-norm Robustness of Ensemble Stumps and Trees
- Title（参考訳）: アンサンブルスタンプとツリーの$\ell_p$-normロバスト性について
- Authors: Yihan Wang, Huan Zhang, Hongge Chen, Duane Boning, Cho-Jui Hsieh
- Abstract要約: 我々は,アンサンブルスタンプの音響検証のための効率的なプログラムベースアルゴリズムを開発した。
我々は,アンサンブル・スタンプや木を訓練するための最初の認証された防御法を,$ell_p$ノルム摂動に関して実証した。
- 参考スコア（独自算出の注目度）: 83.81523991945018
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recent papers have demonstrated that ensemble stumps and trees could be
vulnerable to small input perturbations, so robustness verification and defense
for those models have become an important research problem. However, due to the
structure of decision trees, where each node makes decision purely based on one
feature value, all the previous works only consider the $\ell_\infty$ norm
perturbation. To study robustness with respect to a general $\ell_p$ norm
perturbation, one has to consider the correlation between perturbations on
different features, which has not been handled by previous algorithms. In this
paper, we study the problem of robustness verification and certified defense
with respect to general $\ell_p$ norm perturbations for ensemble decision
stumps and trees. For robustness verification of ensemble stumps, we prove that
complete verification is NP-complete for $p\in(0, \infty)$ while polynomial
time algorithms exist for $p=0$ or $\infty$. For $p\in(0, \infty)$ we develop
an efficient dynamic programming based algorithm for sound verification of
ensemble stumps. For ensemble trees, we generalize the previous multi-level
robustness verification algorithm to $\ell_p$ norm. We demonstrate the first
certified defense method for training ensemble stumps and trees with respect to
$\ell_p$ norm perturbations, and verify its effectiveness empirically on real
datasets.
- Abstract（参考訳）: 近年の研究では、アンサンブルの切り株や木が小さな入力摂動に弱いことが示されており、それらのモデルの堅牢性検証と防御が重要な研究課題となっている。
しかし、各ノードが純粋に1つの特徴値に基づいて決定する決定木の構造のため、以前のすべての作品は$\ell_\infty$ のノルム摂動のみを考える。
一般的な$\ell_p$ノルム摂動についてロバスト性を研究するためには、以前のアルゴリズムでは処理されていない異なる特徴に対する摂動の相関を考慮する必要がある。
本稿では,アンサンブル決定切り株や木々に対する一般的な$\ell_p$標準摂動に対するロバスト性検証と認証防御の問題について検討する。
アンサンブルスタブのロバスト性検証のために、完全検証は$p\in(0, \infty)$に対してnp完全であり、多項式時間アルゴリズムは$p=0$または$\infty$である。
p\in(0, \infty)$の場合、アンサンブルスタンプの音響検証のための効率的な動的プログラミングベースのアルゴリズムを開発する。
アンサンブルツリーの場合、従来のマルチレベルロバスト性検証アルゴリズムを $\ell_p$ norm に一般化する。
我々は,$\ell_p$ノルム摂動に関してアンサンブル・スランプと木を訓練するための最初の認証防衛法を実証し,実データセット上で実効性を検証する。
関連論文リスト
- Identifying General Mechanism Shifts in Linear Causal Representations [58.6238439611389]
我々は,未知の潜在因子の線形混合を観測する線形因果表現学習環境について考察する。
近年の研究では、潜伏要因の復元や、それに基づく構造因果モデルの構築が可能であることが示されている。
非常に穏やかな標準仮定の下では、シフトしたノードの集合を識別することが可能である。
論文 参考訳（メタデータ） (2024-10-31T15:56:50Z) - Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - Verifiable Boosted Tree Ensembles [7.107477567356262]
検証可能な学習支持者は、効率的なセキュリティ検証が可能な機械学習モデルをトレーニングする。
本研究は,基本アンサンブル法による検証学習の先行研究を拡張した。
我々は,$L_in$-normに基づいて,攻撃者に対するロバスト性を検証するための擬似多項式時間アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-02-22T21:56:20Z) - Certified Adversarial Robustness Within Multiple Perturbation Bounds [38.3813286696956]
ランダムスムーシング(Randomized smoothing、RS)は、敵の攻撃に対するよく知られた防御である。
本研究では,複数の摂動境界に対して同時に認証された対向ロバスト性を改善することを目的としている。
論文 参考訳（メタデータ） (2023-04-20T16:42:44Z) - Minimax Rates for Robust Community Detection [19.229475414802213]
逆ノードの破損を伴うブロックモデルにおけるコミュニティ検出の問題点について検討する。
我々の主な結果は、$epsilon$-fraction of corruption and unbounded error $O(epsilon) + e-fracC2 (1 pm o(1))$ where $C = (sqrta - sqrtb)2$ is the signal-to-noise ratio。
アルゴリズムがさらに機能するという意味では、我々のアルゴリズムは2倍に損なわれていることを示す。
論文 参考訳（メタデータ） (2022-07-25T04:45:16Z) - Unbiased and Efficient Sampling of Dependency Trees [0.0]
ほとんどのツリーバンクは、すべての有効な依存ツリーがROOTノードから出てくる単一のエッジを持つ必要がある。
Zmigrodらは最近、単一ルート依存ツリーの分布から置き換えることなくサンプリングするアルゴリズムを提案している。
我々は、Wilson-RCを置換したサンプリングアルゴリズムが実際にバイアスを受けていることを示す。
論文 参考訳（メタデータ） (2022-05-25T09:57:28Z) - Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。
逆汚染レベルに適応する分散認識アルゴリズムをC$で提案する。
論文 参考訳（メタデータ） (2021-10-25T02:53:24Z) - Learning stochastic decision trees [19.304587350775385]
対向雑音に対して最適に耐性のある決定木を学習するための準ポリノミカル時間アルゴリズムを提案する。
私たちのアルゴリズムはさらに適切で、それ自体が決定木である仮説を返します。
論文 参考訳（メタデータ） (2021-05-08T04:54:12Z) - Towards Defending Multiple $\ell_p$-norm Bounded Adversarial
Perturbations via Gated Batch Normalization [120.99395850108422]
既存の敵防衛は、個々の摂動に対するモデル堅牢性を改善するのが一般的である。
最近の手法では、複数の$ell_p$球における敵攻撃に対するモデルロバスト性を改善するが、各摂動型に対するそれらの性能は、まだ十分ではない。
我々は,複数の$ell_pの有界摂動を守るために,摂動不変予測器を逆向きに訓練するGated Batch Normalization (GBN)を提案する。
論文 参考訳（メタデータ） (2020-12-03T02:26:01Z) - An Efficient Adversarial Attack for Tree Ensembles [91.05779257472675]
傾斜促進決定木(DT)や無作為林(RF)などの木に基づくアンサンブルに対する敵対的攻撃
提案手法は,従来のMILP (Mixed-integer linear programming) よりも数千倍高速であることを示す。
私たちのコードはhttps://chong-z/tree-ensemble- attackで利用可能です。
論文 参考訳（メタデータ） (2020-10-22T10:59:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。