論文の概要: A Theory of Interpretable Approximations

• arxiv url: http://arxiv.org/abs/2406.10529v1
• Date: Sat, 15 Jun 2024 06:43:45 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-19 00:02:58.957572
• Title: A Theory of Interpretable Approximations
• Title（参考訳）: 解釈可能な近似の理論
• Authors: Marco Bressan, Nicolò Cesa-Bianchi, Emmanuel Esposito, Yishay Mansour, Shay Moran, Maximilian Thiessen,
• Abstract要約: 我々は、ある基底クラス $mathcalH$ の概念の小さな集合によってターゲット概念 $c$ を近似するという考え方を研究する。 任意の$mathcalH$と$c$のペアに対して、これらのケースのちょうど1つが成り立つ: (i) $c$を任意の精度で$mathcalH$で近似することはできない。 解釈可能な近似の場合、近似の複雑さに関するわずかに非自明なa-priori保証でさえ、定数(分布自由かつ精度)の近似を意味することを示す。
• 参考スコア（独自算出の注目度）: 61.90216959710842
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Can a deep neural network be approximated by a small decision tree based on simple features? This question and its variants are behind the growing demand for machine learning models that are *interpretable* by humans. In this work we study such questions by introducing *interpretable approximations*, a notion that captures the idea of approximating a target concept $c$ by a small aggregation of concepts from some base class $\mathcal{H}$. In particular, we consider the approximation of a binary concept $c$ by decision trees based on a simple class $\mathcal{H}$ (e.g., of bounded VC dimension), and use the tree depth as a measure of complexity. Our primary contribution is the following remarkable trichotomy. For any given pair of $\mathcal{H}$ and $c$, exactly one of these cases holds: (i) $c$ cannot be approximated by $\mathcal{H}$ with arbitrary accuracy; (ii) $c$ can be approximated by $\mathcal{H}$ with arbitrary accuracy, but there exists no universal rate that bounds the complexity of the approximations as a function of the accuracy; or (iii) there exists a constant $\kappa$ that depends only on $\mathcal{H}$ and $c$ such that, for *any* data distribution and *any* desired accuracy level, $c$ can be approximated by $\mathcal{H}$ with a complexity not exceeding $\kappa$. This taxonomy stands in stark contrast to the landscape of supervised classification, which offers a complex array of distribution-free and universally learnable scenarios. We show that, in the case of interpretable approximations, even a slightly nontrivial a-priori guarantee on the complexity of approximations implies approximations with constant (distribution-free and accuracy-free) complexity. We extend our trichotomy to classes $\mathcal{H}$ of unbounded VC dimension and give characterizations of interpretability based on the algebra generated by $\mathcal{H}$.
• Abstract（参考訳）: ディープニューラルネットワークは、単純な特徴に基づいて、小さな決定木によって近似できるだろうか? この質問とその変種は、人間によって*解釈可能な*機械学習モデルの需要が高まっている背景にある。 In this work, we study such question by introduced *interpretable approximations*, a concept that captures the idea of Approximating a target concept $c$ by a small aggregate of concept from some base class $\mathcal{H}$。 特に、単純なクラス $\mathcal{H}$ (e g , of bounded VC dimension) に基づいて、決定木による二進概念 $c$ の近似を考え、その木深さを複雑性の尺度として使う。 私たちの主な貢献は、以下の顕著な三分割である。 $\mathcal{H}$ と $c$ の任意のペアに対して、これらのケースのちょうど1つが成り立つ。 (i)$c$を任意の精度で$\mathcal{H}$で近似することはできない。 (ii)$c$は任意の精度で$\mathcal{H}$で近似できるが、精度の関数として近似の複雑さを束縛する普遍レートは存在しない。 (iii)$\mathcal{H}$と$c$のみに依存する定数$\kappa$が存在し、*any*データ分布と *any* 所望の精度レベルに対して$c$は$\mathcal{H}$で近似できる。 この分類学は、教師付き分類の風景とは対照的に、分布自由で普遍的に学習可能なシナリオの複雑な配列を提供する。 解釈可能な近似の場合、近似の複雑さに関するわずかに非自明なa-priori保証でさえ、一定の(分布自由かつ精度自由な)複雑さを伴う近似を意味することを示す。 我々は、非有界VC次元のクラス $\mathcal{H}$ に三分法を拡張し、$\mathcal{H}$ によって生成される代数に基づく解釈可能性の特性を与える。

関連論文リスト

• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Local approximation of operators [0.0]
  距離空間 $mathfrakX$ と $mathfrakY$ の間の非線形作用素の近似の度合いを決定する問題について検討する。 例えば、$mathbbSd$ の近似に関係する定数は $mathcalO(d1/6)$ である。
  論文  参考訳（メタデータ） (2022-02-13T19:28:34Z)
• Empirical complexity of comparator-based nearest neighbor descent [0.0]
  K$-nearest 隣り合うアルゴリズムの Java 並列ストリームの実装を示す。 Kullback-Leiblerの発散比較器による実験は、$K$-nearest近くの更新ラウンドの数が直径の2倍を超えないという予測を支持している。
  論文  参考訳（メタデータ） (2022-01-30T21:37:53Z)
• Statistically Near-Optimal Hypothesis Selection [33.83129262033921]
  仮説選択問題に対する最適2ドルの近似学習戦略を導出する。 これは、最適な近似係数とサンプルの複雑さを同時に達成する最初のアルゴリズムである。
  論文  参考訳（メタデータ） (2021-08-17T21:11:20Z)
• Universal Regular Conditional Distributions via Probability Measure-Valued Deep Neural Models [3.8073142980733]
  提案したフレームワークを用いて構築されたモデルはすべて、$C(mathcalX,mathcalP_1(mathcalY))$で密集している。 提案モデルはまた、ほとんどのランダム化された機械学習モデルに存在するアレラトリック不確かさを汎用的に表現できることも示している。
  論文  参考訳（メタデータ） (2021-05-17T11:34:09Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• A deep network construction that adapts to intrinsic dimensionality beyond the domain [79.23797234241471]
  本稿では,ReLUを活性化したディープネットワークを用いて,2層合成の近似を$f(x) = g(phi(x))$で検討する。 例えば、低次元埋め込み部分多様体への射影と、低次元集合の集合への距離である。
  論文  参考訳（メタデータ） (2020-08-06T09:50:29Z)
• Average-case Complexity of Teaching Convex Polytopes via Halfspace Queries [55.28642461328172]
  平均的なケースの教えの複雑さは$Theta(d)$であり、最悪のケースの教えの複雑さは$Theta(n)$とは対照的である。 我々の洞察は、$phi$-separable dichotomiesの平均ケースの複雑さに厳密な拘束力を確立することを可能にする。
  論文  参考訳（メタデータ） (2020-06-25T19:59:24Z)
• A Journey into Ontology Approximation: From Non-Horn to Horn [17.210841426842816]
  非Horn記述論理(DL)で定式化されたオントロジーの完全近似について検討する。 我々は必然的に無限となる具体的な近似スキームを提供し、$mathcalELU$-to-$mathcalEL$ において、実際には有限近似が存在する傾向があることを観察する。 対照的に、これらはいずれも$mathcalELU_bot$-to-$mathcalEL_bot$と$mathcalALC$-to-$mathcalEL_bot$の場合ではない。
  論文  参考訳（メタデータ） (2020-01-21T19:47:21Z)

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

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