論文の概要: Interval Certifications for Multilayered Perceptrons via Lattice Traversal
- arxiv url: http://arxiv.org/abs/2607.08773v1
- Date: Thu, 09 Apr 2026 11:25:43 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-27 00:46:12.98629
- Title: Interval Certifications for Multilayered Perceptrons via Lattice Traversal
- Title（参考訳）: 格子トラバースによる多層パーセプトロンのインターバル認証
- Abstract要約: 本研究では, 対向ロバスト性問題を格子問題に還元できることを示す。
我々は形式的検証器を開発し、音の最大性と完全最小性が保証される。
新たなParallelepipedoNNシステムを用いて,実験的検討を行った。
- 参考スコア（独自算出の注目度）: 10.268619734362547
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: In this work we present a rigorous theoretical framework to a foundational problem of AI safety, namely adversarial robustness. In particular, we show that the adversarial robustness problem can be reduced to a lattice traversal problem. Each element of this lattice corresponds to an interval, i.e., an axis-aligned hyper-rectangle, containing an input point $\mathbf{x}$. Consider a multilayered perceptron classifier (MLP). An interval $I$ constitutes a sound certification if $\mathbf{x} \in I$ and $\mathbf{x}$ can be freely perturbed in $I$ without changing the MLP's prediction. Complementarily, an interval $I$ constitutes a complete certification if $\mathbf{x} \in I$ and when $\mathbf{x}$ moves outside of $I$ the MLP's prediction is guaranteed to change. While the sound certification problem corresponds to the well-studied adversarial robustness, complete certifications have not been examined in the literature. We develop lattice traversal operators, which we apply in a refine & verify iterative scheme. Using formal MLP verifiers, sound maximality and complete minimality are guaranteed. Moreover, we examine objective optimization problems. There we discover some interesting asymmetries. For complete certifications, the minimum solution is obtained in polynomial oracle calls. This does not hold for sound certifications, where we prove strong intractability results. Additionally, we examine optimization problems in symmetric intervals (i.e., $\ell_\infty$-spheres), where we provide logarithmic algorithms. Finally, we present an empirical evaluation, using the novel ParallelepipedoNN system.
- Abstract（参考訳）: 本研究では,AIの安全性,すなわち対向的堅牢性に関する基礎的な問題に対して,厳密な理論的枠組みを提案する。
特に, 対向ロバスト性問題は格子トラバース問題に還元可能であることを示す。
この格子の各要素は間隔、すなわち入力点 $\mathbf{x}$ を含む軸方向の超矩形に対応する。
多層パーセプトロン分類器(MLP)を考える。
もし$\mathbf{x} \in I$ と $\mathbf{x}$ が MLP の予測を変更することなく$I$ で自由に摂動できるなら、その区間 $I$ は音響認証を構成する。
補足的に、区間$I$は$\mathbf{x} \in I$と$\mathbf{x}$が$I$の外に移動するときの完全証明を構成する。
健全な認証問題は、よく研究された敵の堅牢性に対応するが、文献では完全な認証は検討されていない。
我々は格子トラバーサル演算子を開発し、これを洗練・検証反復スキームに適用する。
正式なMLP検証器を用いることで、音の最大性と完全最小性が保証される。
さらに,目的最適化問題についても検討する。
そこで興味深い対称性がいくつか見つかる。
完全証明の場合、最小解は多項式オラクル呼び出しで得られる。
これは、強い難易度の結果が証明される健全な認定には当てはまらない。
さらに、対数アルゴリズムを提供する対称区間(例えば$\ell_\infty$-spheres)の最適化問題についても検討する。
最後に,ParallelepipedoNNシステムを用いた実験的検討を行った。
関連論文リスト
- PureSuperQMA(exp) = BellPureSymQMA(poly) = QMA via Dimension-Free Bosonic Argmax [36.23068106699028]
純粋状態整合性問題は自然に量子証明システムにつながり、1人の証人が多くの受理制約を満たす必要がある。
$mathsfBellPureSymQMA(textpoly)$は、証明者が純粋状態の多くのコピーを検証しなければならない関連するモデルである。
k$-local pure-state consistency is $mathsfQMA$-complete for every fixed $kge2$, so is the exact bosonic and fermionic pure $N$-representability problem。
論文 参考訳（メタデータ） (2026-09-10T17:37:22Z) - Multi-Prover Interactive Proof Systems with Leakage [1.0960289997471082]
本稿では,プロデューサ間の通信が許されるが境界づけられた設定にアプローチする2つの手法を提案する。
任意の$p$に対して、$mathsfNEXP$と$mathsfRE$に対して$mathsfMIPast$と$mathsfMIPast$プロトコルを構築することができる。
論文 参考訳（メタデータ） (2026-05-11T01:58:44Z) - SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More [37.208622097149714]
我々は、最大$|M u|$で境界を証明できる新しいアップタイムアルゴリズムの族を与える。
我々の認証アルゴリズムは, Sum-of-Squares階層を必須に活用する。
論文 参考訳（メタデータ） (2024-12-30T18:59:46Z) - Learning Networks from Wide-Sense Stationary Stochastic Processes [7.59499154221528]
ここでの重要な推論問題は、ノード出力(ポテンシャル)からエッジ接続を学習することである。
我々はWhittleの最大可能性推定器(MLE)を用いて時間相関サンプルから$Last$のサポートを学習する。
MLE問題は厳密な凸であり、ユニークな解であることを示す。
論文 参考訳（メタデータ） (2024-12-04T23:14:00Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳（メタデータ） (2022-12-01T15:57:58Z) - Multimeasurement Generative Models [7.502947376736449]
我々は、密度$p_X$ in $mathbbRd$を未知分布からサンプリングする問題を学習とサンプリングの問題を$p_mathbfY$ in $mathbbRMd$とする。
論文 参考訳（メタデータ） (2021-12-18T02:11:36Z) - Under-bagging Nearest Neighbors for Imbalanced Classification [63.026765294759876]
我々は,不均衡な分類問題に対して,textitunder-bagging $k$-NN (textitunder-bagging $k$-NN) というアンサンブル学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-01T14:10:38Z) - Provable Robustness of Adversarial Training for Learning Halfspaces with
Noise [95.84614821570283]
ラベル雑音の存在下での敵対的ロバストなハーフスペースの特性を分析する。
我々の知る限りでは、これは敵の訓練がノイズの分類子を与えることを示す最初の研究である。
論文 参考訳（メタデータ） (2021-04-19T16:35:38Z) - Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。
情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
論文 参考訳（メタデータ） (2020-12-17T16:43:11Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-11T14:25:02Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳（メタデータ） (2020-05-13T16:44:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。