論文の概要: Proofs as Explanations: Short Certificates for Reliable Predictions

• arxiv url: http://arxiv.org/abs/2504.08377v1
• Date: Fri, 11 Apr 2025 09:26:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-14 14:20:08.578487
• Title: Proofs as Explanations: Short Certificates for Reliable Predictions
• Title（参考訳）: 説明としての証明:信頼性予測のための短い証明書
• Authors: Avrim Blum, Steve Hanneke, Chirag Pabbaraju, Donya Saless,
• Abstract要約: 我々は、予測$h(x)=y$がトレーニングデータのサブセット$S'$から成り立つ、説明可能なAIのモデルを考える。 集合 $S'$ of size $d+1$ は正の予測の説明として解放され、実現可能性の仮定の下での予測の正しさの短い証明として機能する。
• 参考スコア（独自算出の注目度）: 25.157401709060064
• License:
• Abstract: We consider a model for explainable AI in which an explanation for a prediction $h(x)=y$ consists of a subset $S'$ of the training data (if it exists) such that all classifiers $h' \in H$ that make at most $b$ mistakes on $S'$ predict $h'(x)=y$. Such a set $S'$ serves as a proof that $x$ indeed has label $y$ under the assumption that (1) the target function $h^\star$ belongs to $H$, and (2) the set $S$ contains at most $b$ corrupted points. For example, if $b=0$ and $H$ is the family of linear classifiers in $\mathbb{R}^d$, and if $x$ lies inside the convex hull of the positive data points in $S$ (and hence every consistent linear classifier labels $x$ as positive), then Carath\'eodory's theorem states that $x$ lies inside the convex hull of $d+1$ of those points. So, a set $S'$ of size $d+1$ could be released as an explanation for a positive prediction, and would serve as a short proof of correctness of the prediction under the assumption of realizability. In this work, we consider this problem more generally, for general hypothesis classes $H$ and general values $b\geq 0$. We define the notion of the robust hollow star number of $H$ (which generalizes the standard hollow star number), and show that it precisely characterizes the worst-case size of the smallest certificate achievable, and analyze its size for natural classes. We also consider worst-case distributional bounds on certificate size, as well as distribution-dependent bounds that we show tightly control the sample size needed to get a certificate for any given test example. In particular, we define a notion of the certificate coefficient $\varepsilon_x$ of an example $x$ with respect to a data distribution $D$ and target function $h^\star$, and prove matching upper and lower bounds on sample size as a function of $\varepsilon_x$, $b$, and the VC dimension $d$ of $H$.
• Abstract（参考訳）: 我々は、予測$h(x)=y$がトレーニングデータのサブセット$S'$(存在すれば)から成り、すべての分類器$h' \in H$が$S'$予測$h'(x)=y$に対して少なくとも$b$の誤りを犯すような説明可能なAIのモデルを考える。 そのような集合 $S'$ は、(1) の目的関数 $h^\star$ が$H$ に属し、(2) の集合 $S$ が少なくとも$b$ の破損点を含むという仮定の下で、実際に$x$ がラベル $y$ を持つという証明である。 例えば、$b=0$ と $H$ が$\mathbb{R}^d$ の線型分類器の族であり、$x$ が$S$ の正のデータ点の凸包内にあるならば(従って、すべての一貫した線形分類器が $x$ を正としてラベル付けする)、Carath\'eodory の定理は、$x$ が $d+1$ の凸包内にあることを述べる。 したがって、集合 $S'$ of size $d+1$ は正の予測の説明として解放され、実現可能性の仮定の下での予測の正しさの短い証明として機能する。 本研究では、一般仮説クラス $H$ と一般値 $b\geq 0$ に対して、この問題をより一般的に考える。 我々は、標準的な中空星数を一般化する)$H$というロバストな中空星数の概念を定義し、最小の証明が達成可能な最悪の大きさを正確に特徴付け、そのサイズを自然クラスで解析することを示した。 また、証明書サイズに関する最悪の分散境界や、特定のテスト例の証明書を取得するのに必要なサンプルサイズを厳密に制御する分布依存境界についても検討しています。 特に、データ分布の$D$とターゲット関数の$h^\star$に関する例$x$の証明係数$\varepsilon_x$の概念を定義し、サンプルサイズの上と下の境界を、$\varepsilon_x$, $b$、VC次元$d$の関数として証明する。

関連論文リスト

• Guarantees for Nonlinear Representation Learning: Non-identical Covariates, Dependent Data, Fewer Samples [24.45016514352055]
  我々は、関数クラス$mathcal F times Mathcal G$から、T+1$関数$f_star(t) circ g_star$を学習する際のサンプル複雑度について研究する。 タスク数が$T$になるにつれて、サンプル要件とリスクバウンドの両方が$r$次元回帰に収束することを示す。
  論文  参考訳（メタデータ） (2024-10-15T03:20:19Z)
• Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions [49.69852011882769]
  一般化線形モデル (GLMs) の重畳雑音の存在下での回帰問題に対する最初のアルゴリズムを示す。 本稿では,この問題に最も一般的な分布非依存設定で対処するアルゴリズムを提案する。 これは、サンプルの半分以上を任意に破損させる難聴ノイズを持つGLMレグレッションに対する最初の新しいアルゴリズムによる結果である。
  論文  参考訳（メタデータ） (2023-09-20T21:41:59Z)
• Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
  ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。 我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。 平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
  論文  参考訳（メタデータ） (2023-04-17T10:38:08Z)
• Learning linear dynamical systems under convex constraints [4.4351901934764975]
  線形力学系を単一軌道の$T$サンプルから同定する問題を考察する。 A*$は、制約のない設定に必要な値よりも$T$小さい値を確実に見積もることができる。
  論文  参考訳（メタデータ） (2023-03-27T11:49:40Z)
• Phase Transitions in the Detection of Correlated Databases [12.010807505655238]
  本稿では,2つのガウスデータベースの相関関係を$mathsfXinmathbbRntimes d$と$mathsfYntimes d$で検出する問題について検討する。 この問題は、ソーシャルメディア、計算生物学などの分析に関係している。
  論文  参考訳（メタデータ） (2023-02-07T10:39:44Z)
• Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns [50.053491972003656]
  関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$. ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
  論文  参考訳（メタデータ） (2021-09-06T14:21:43Z)
• Self-training Converts Weak Learners to Strong Learners in Mixture Models [86.7137362125503]
  擬似ラベルの $boldsymbolbeta_mathrmpl$ が,最大$C_mathrmerr$ の分類誤差を達成可能であることを示す。 さらに、ロジスティックな損失に対して勾配降下を実行することで、ラベル付き例のみを使用して、分類誤差が$C_mathrmerr$で擬ラベルの $boldsymbolbeta_mathrmpl$ が得られることを示す。
  論文  参考訳（メタデータ） (2021-06-25T17:59:16Z)
• Optimal Spectral Recovery of a Planted Vector in a Subspace [80.02218763267992]
  我々は、$ell_4$ノルムが同じ$ell$ノルムを持つガウスベクトルと異なるプラントベクトル$v$の効率的な推定と検出について研究する。 規則$n rho gg sqrtN$ では、大クラスのスペクトル法(そしてより一般的には、入力の低次法)は、植込みベクトルの検出に失敗する。
  論文  参考訳（メタデータ） (2021-05-31T16:10:49Z)
• Out-of-sample error estimate for robust M-estimators with convex penalty [5.33024001730262]
  凸ペナルティで正規化された堅牢な$M$-estimatorsに対して、一般的なサンプル外誤差推定を提案する。 一般的な微分可能損失関数 $psi$ は $psi=rho'$ が 1-Lipschitz であるときに許される。
  論文  参考訳（メタデータ） (2020-08-26T21:50:41Z)
• Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals [49.60752558064027]
  ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。 我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
  論文  参考訳（メタデータ） (2020-06-29T17:10:10Z)
• Efficient Statistics for Sparse Graphical Models from Truncated Samples [19.205541380535397]
  i) スパースガウス図形モデルの推論と (ii) スパース線形モデルの回復支援の2つの基本的問題と古典的問題に焦点をあてる。 疎線型回帰については、$(bf x,y)$ が生成されるが、$y = bf xtopOmega* + MathcalN(0,1)$ と $(bf x, y)$ は、truncation set $S subseteq mathbbRd$ に属する場合にのみ見られる。
  論文  参考訳（メタデータ） (2020-06-17T09:21:00Z)

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

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