論文の概要: Hardness of Deceptive Certificate Selection
- arxiv url: http://arxiv.org/abs/2306.04505v1
- Date: Wed, 7 Jun 2023 15:12:16 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-08 13:53:17.348632
- Title: Hardness of Deceptive Certificate Selection
- Title(参考訳): 偽証明書選択の難しさ
- Authors: Stephan W\"aldchen
- Abstract要約: 我々は, AFC を利用した完全性と健全性の向上を目的とした悪意のある証明者検証手法を検討する。
これは、AFCが現実世界のタスクにインタラクティブな分類を使うことを防ぐべきではないという証拠である。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: Recent progress towards theoretical interpretability guarantees for AI has
been made with classifiers that are based on interactive proof systems. A
prover selects a certificate from the datapoint and sends it to a verifier who
decides the class. In the context of machine learning, such a certificate can
be a feature that is informative of the class. For a setup with high soundness
and completeness, the exchanged certificates must have a high mutual
information with the true class of the datapoint. However, this guarantee
relies on a bound on the Asymmetric Feature Correlation of the dataset, a
property that so far is difficult to estimate for high-dimensional data. It was
conjectured in W\"aldchen et al. that it is computationally hard to exploit the
AFC, which is what we prove here.
We consider a malicious prover-verifier duo that aims to exploit the AFC to
achieve high completeness and soundness while using uninformative certificates.
We show that this task is $\mathsf{NP}$-hard and cannot be approximated better
than $\mathcal{O}(m^{1/8 - \epsilon})$, where $m$ is the number of possible
certificates, for $\epsilon>0$ under the Dense-vs-Random conjecture. This is
some evidence that AFC should not prevent the use of interactive classification
for real-world tasks, as it is computationally hard to be exploited.
- Abstract(参考訳): aiの理論的解釈可能性保証への最近の進歩は、インタラクティブな証明システムに基づく分類器によって行われている。
証明者は、データポイントから証明書を選択し、クラスを決定する検証者に送信する。
機械学習の文脈では、このような証明書はクラスに情報を提供する機能になり得る。
健全性と完全性の高いセットアップでは、交換された証明書はデータポイントの真のクラスと高い相互情報を持つ必要がある。
しかし、この保証はデータセットの非対称な特徴相関(高次元データの推定がこれまで難しい性質)に依存する。
W\"aldchen et al. において、AFCを計算的に利用することは困難であると推測された。
非形式的証明を用いて, AFC を利用した精度の高い完全性と健全性を実現することを目的とした悪意のある証明検証手法を提案する。
このタスクは$\mathsf{NP}$-hardであり、$\mathcal{O}(m^{1/8 - \epsilon})$よりも近似できない。
これは、afcが実世界のタスクにインタラクティブな分類を使用することを妨げてはならないという証拠である。
関連論文リスト
- Adaptive Hierarchical Certification for Segmentation using Randomized Smoothing [87.48628403354351]
機械学習の認証は、特定の条件下では、敵対的なサンプルが特定の範囲内でモデルを回避できないことを証明している。
セグメンテーションの一般的な認証方法は、平らな粒度のクラスを使い、モデルの不確実性による高い断続率をもたらす。
本稿では,複数レベルの階層内で画素を認証し,不安定なコンポーネントに対して粗いレベルに適応的に認証を緩和する,新しい,より実用的な設定を提案する。
論文 参考訳(メタデータ) (2024-02-13T11:59:43Z) - Double Bubble, Toil and Trouble: Enhancing Certified Robustness through
Transitivity [27.04033198073254]
ニューラルネットワークモデルの分類を反転させる微妙な敵の例に反応して、最近の研究は、ソリューションとして証明された堅牢性を促進している。
我々は,今日の"最適"証明書が,認証の推移性と入力空間の幾何学の両方を活用することで,どのように改善できるかを示す。
また, 得られた認定半径の4ドルパーセンテージを均一に増加させることにより, さらに有望な結果が得られた。
論文 参考訳(メタデータ) (2022-10-12T10:42:21Z) - Getting a-Round Guarantees: Floating-Point Attacks on Certified Robustness [19.380453459873298]
敵の例は、わずかな入力摂動によって機械学習分類器の決定を変更できるため、セキュリティリスクを引き起こす。
これらの保証は、ラウンドエラーを引き起こす浮動小数点表現の制限により無効化可能であることを示す。
この攻撃は、正確な認証保証を持つ線形分類器や、保守的な認証を持つニューラルネットワークに対して実行可能であることを示す。
論文 参考訳(メタデータ) (2022-05-20T13:07:36Z) - Smooth-Reduce: Leveraging Patches for Improved Certified Robustness [100.28947222215463]
本研究では,Smooth-Reduce の学習自由な修正スムース化手法を提案する。
提案アルゴリズムは,入力画像から抽出した重なり合うパッチを分類し,予測ロジットを集約して,入力周辺の半径が大きいことを証明する。
我々は,このような証明書の理論的保証を提供し,他のランダムな平滑化手法に対する顕著な改善を実証的に示す。
論文 参考訳(メタデータ) (2022-05-12T15:26:20Z) - Almost Tight L0-norm Certified Robustness of Top-k Predictions against
Adversarial Perturbations [78.23408201652984]
トップk予測は、マシンラーニング・アズ・ア・サービス、レコメンダ・システム、Web検索など、多くの現実世界のアプリケーションで使用されている。
我々の研究はランダム化平滑化に基づいており、入力をランダム化することで、証明可能なロバストな分類器を構築する。
例えば、攻撃者がテスト画像の5ピクセルを任意に摂動できる場合に、ImageNet上で69.2%の認定トップ3精度を達成する分類器を構築することができる。
論文 参考訳(メタデータ) (2020-11-15T21:34:44Z) - Higher-Order Certification for Randomized Smoothing [78.00394805536317]
本研究では,スムーズな分類器の安全性向上のための枠組みを提案する。
我々は,0th$-orderと1st$-order情報を用いて,認証された安全領域を計算する方法を提案する。
また,高次情報を用いた認証計算を一般化するフレームワークも提供する。
論文 参考訳(メタデータ) (2020-10-13T19:35:48Z) - Certifying Confidence via Randomized Smoothing [151.67113334248464]
ランダムな平滑化は、高次元の分類問題に対して良好な証明されたロバスト性を保証することが示されている。
ほとんどの平滑化法は、下層の分類器が予測する信頼性に関する情報を与えてくれない。
そこで本研究では,スムーズな分類器の予測信頼度を評価するために,認証ラジイを生成する手法を提案する。
論文 参考訳(メタデータ) (2020-09-17T04:37:26Z) - A Theory of Usable Information Under Computational Constraints [103.5901638681034]
本稿では,複雑なシステムにおける情報推論のための新しいフレームワークを提案する。
我々の基礎はシャノンの情報理論の変分拡張に基づいている。
計算制約を組み込むことで,データから$mathcalV$-informationを確実に推定できることを示す。
論文 参考訳(メタデータ) (2020-02-25T06:09:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。