論文の概要: Certification from Examples is Hard for Circuits and Transformers under Minimal Overparametrization

• arxiv url: http://arxiv.org/abs/2605.22964v1
• Date: Thu, 21 May 2026 18:49:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-25 17:29:20.060986
• Title: Certification from Examples is Hard for Circuits and Transformers under Minimal Overparametrization
• Title（参考訳）: 極小過度化による回路・変圧器の実証は困難である
• Authors: Artur Back de Luca, Kimon Fountoulakis,
• Abstract要約: 平均ケースの精度は、いまだに一貫性のない振る舞いを隠蔽することができる。 これは正確な証明を動機付け、学習された仮説が目標に等しいことを示すのに必要なラベル付きサンプルの最小セットを求める。 いくつかの仮説は容易に証明できるが、最小限のオーバーパラメトリゼーションでさえ、いくつかの仮説クラスにおいて証明を指数関数的に困難にすることができる。
• 参考スコア（独自算出の注目度）: 15.005368732088511
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: As state-of-the-art neural networks are deployed on reasoning and algorithmic tasks, exactness guarantees become increasingly important. However, high average-case accuracy can still mask inconsistent behaviors. This motivates exact certification, which asks for the smallest set of labeled examples needed to certify that a learned hypothesis equals the target. We show that while some hypotheses are easy to certify, even minimal overparametrization can make certification exponentially hard across several hypothesis classes. For threshold circuits of depth $\ge 2$, adding a single extra gate can force certificate sizes exponential in the input dimension. We show an analogous hardness result for log-precision Transformers with only constant architectural overhead. We also characterize approximate certification, showing that allowing only polynomially many mistakes still requires exponentially large certificates, whereas constant relative-error guarantees can hide exponentially many mistakes. Empirically, we study certification for constructed circuits and trained Transformers for recognizing binary addition. While the constructed circuits instantiate the exponential barrier for certification, the trained Transformer analysis shows that imperfect models can evade detection by large uniformly sampled certificate candidates.
• Abstract（参考訳）: 最先端のニューラルネットワークが推論やアルゴリズムタスクにデプロイされるにつれて、正確性を保証することがますます重要になる。 しかし、平均ケースの精度は相反する振る舞いを隠蔽することができる。 これは正確な証明を動機付け、学習された仮説が目標に等しいことを示すのに必要なラベル付きサンプルの最小セットを求める。 いくつかの仮説は容易に証明できるが、最小限のオーバーパラメトリゼーションでさえ、いくつかの仮説クラスにおいて証明を指数関数的に困難にすることができる。 深さ$\ge 2$のしきい値回路では、1つの余分なゲートを追加することで、入力次元で証明書のサイズを指数関数的に強制することができる。 連続的なアーキテクチャ上のオーバーヘッドしか持たない対数精度変換器に対して、類似した硬度結果を示す。 多項式的に多くの誤りを許すには、指数関数的に大きな証明書が必要である一方で、一定の相対エラー保証は指数関数的に多くの誤りを隠蔽できることを示す。 実験により,構成回路の認証と2値加算の認識のためのトレーニング用トランスフォーマーについて検討した。 構築された回路は、認証の指数的障壁をインスタンス化するが、トレーニングされたTransformer分析により、不完全なモデルが、大規模な一様サンプリング証明候補による検出を回避できることが示されている。

関連論文リスト

• Towards Verifiable AI with Lightweight Cryptographic Proofs of Inference [3.3323431541048385]
  完全証明を軽量なサンプリングベースアプローチで置き換える検証フレームワークとプロトコルを提案する。 我々は,機能的に異なるモデル間のトレース分離を活用可能な条件を定式化し,検証可能な推論プロトコルの安全性について議論する。 我々の手法は、最先端の暗号証明システムと比較して、証明時間を桁違いに削減する。
  論文  参考訳（メタデータ） (2026-03-19T15:24:27Z)
• BlockCert: Certified Blockwise Extraction of Transformer Mechanisms [0.0]
  本稿では,トランス機構のブロックワイズ抽出のためのフレームワークであるBlockCertを紹介する。 我々は、これらの局所的な保証をグローバルな偏差境界まで引き上げる単純なリプシッツに基づく合成定理をLean 4で定式化します。 以上の結果から,明示的な証明を用いたブロックワイズ抽出は,実際のトランスフォーマー言語モデルで実現可能であることが示唆された。
  論文  参考訳（メタデータ） (2025-11-20T06:04:34Z)
• Exact Certification of (Graph) Neural Networks Against Label Poisoning [50.87615167799367]
  グラフニューラルネットワーク(GNN)におけるラベルフリップの正確な認証手法を提案する。 本稿では,ノード分類タスクにおける広範囲なGNNアーキテクチャの認証に本手法を適用した。 私たちの研究は、ニューラルネットワークによって引き起こされた毒殺攻撃に対する最初の正確な認証を提示します。
  論文  参考訳（メタデータ） (2024-11-30T17:05:12Z)
• Adaptive Hierarchical Certification for Segmentation using Randomized Smoothing [87.48628403354351]
  機械学習の認証は、特定の条件下では、敵対的なサンプルが特定の範囲内でモデルを回避できないことを証明している。 セグメンテーションの一般的な認証方法は、平らな粒度のクラスを使い、モデルの不確実性による高い断続率をもたらす。 本稿では,複数レベルの階層内で画素を認証し,不安定なコンポーネントに対して粗いレベルに適応的に認証を緩和する,新しい,より実用的な設定を提案する。
  論文  参考訳（メタデータ） (2024-02-13T11:59:43Z)
• Structure-Aware Robustness Certificates for Graph Classification [13.643197515573029]
  グラフベースの機械学習モデルの堅牢性を証明することは、安全性にとって重要な課題である。 入力グラフ構造に異方性雑音分布を付加したランダムな平滑化法を開発した。 我々のプロセスは、分類器のための構造認識証明書を生成し、これにより、グラフの様々な事前定義された構造に対して、ロバスト性証明書の規模が変化することを示す。
  論文  参考訳（メタデータ） (2023-06-20T22:01:37Z)
• Certified Interpretability Robustness for Class Activation Mapping [77.58769591550225]
  本稿では,解釈可能性マップのためのCORGI(Certifiable prOvable Robustness Guarantees)を提案する。 CORGIは入力画像を取り込み、そのCAM解釈可能性マップのロバスト性に対する証明可能な下限を与えるアルゴリズムである。 交通標識データを用いたケーススタディによるCORGIの有効性を示す。
  論文  参考訳（メタデータ） (2023-01-26T18:58:11Z)
• Double Bubble, Toil and Trouble: Enhancing Certified Robustness through Transitivity [27.04033198073254]
  ニューラルネットワークモデルの分類を反転させる微妙な敵の例に反応して、最近の研究は、ソリューションとして証明された堅牢性を促進している。 我々は,今日の"最適"証明書が,認証の推移性と入力空間の幾何学の両方を活用することで,どのように改善できるかを示す。 また, 得られた認定半径の4ドルパーセンテージを均一に増加させることにより, さらに有望な結果が得られた。
  論文  参考訳（メタデータ） (2022-10-12T10:42:21Z)
• Towards Evading the Limits of Randomized Smoothing: A Theoretical Analysis [74.85187027051879]
  決定境界を複数の雑音分布で探索することにより,任意の精度で最適な証明を近似できることを示す。 この結果は、分類器固有の認証に関するさらなる研究を後押しし、ランダム化された平滑化が依然として調査に値することを示す。
  論文  参考訳（メタデータ） (2022-06-03T17:48:54Z)
• Robustness Verification for Transformers [165.25112192811764]
  我々はトランスフォーマーのための最初のロバスト性検証アルゴリズムを開発した。 提案手法で計算したロバスト性境界は, 素粒子間境界伝播法で計算したロバスト性境界よりもかなり厳密である。 これらの境界はまた、感情分析における異なる単語の重要性を常に反映しているトランスフォーマーの解釈にも光を当てている。
  論文  参考訳（メタデータ） (2020-02-16T17:16:31Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。