論文の概要: On Computing Probabilistic Explanations for Decision Trees
- arxiv url: http://arxiv.org/abs/2207.12213v1
- Date: Thu, 30 Jun 2022 21:58:31 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-31 14:48:08.970353
- Title: On Computing Probabilistic Explanations for Decision Trees
- Title（参考訳）: 決定木に対する確率的説明の計算について
- Authors: Marcelo Arenas, Pablo Barcel\'o, Miguel Romero, Bernardo Subercaseaux
- Abstract要約: 十分な理由は、決定木を$T$とインスタンスを$x$とすると、決定を$T(x)$とします。
本稿では,決定木に対する$delta$sufficient-reasonsの計算複雑性について検討する。
決定木の構造的制約を識別し,SATソルバがこれらの問題に実際にどのように対処できるかを示す。
- 参考スコア（独自算出の注目度）: 4.406418914680962
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Formal XAI (explainable AI) is a growing area that focuses on computing
explanations with mathematical guarantees for the decisions made by ML models.
Inside formal XAI, one of the most studied cases is that of explaining the
choices taken by decision trees, as they are traditionally deemed as one of the
most interpretable classes of models. Recent work has focused on studying the
computation of "sufficient reasons", a kind of explanation in which given a
decision tree $T$ and an instance $x$, one explains the decision $T(x)$ by
providing a subset $y$ of the features of $x$ such that for any other instance
$z$ compatible with $y$, it holds that $T(z) = T(x)$, intuitively meaning that
the features in $y$ are already enough to fully justify the classification of
$x$ by $T$. It has been argued, however, that sufficient reasons constitute a
restrictive notion of explanation, and thus the community has started to study
their probabilistic counterpart, in which one requires that the probability of
$T(z) = T(x)$ must be at least some value $\delta \in (0, 1]$, where $z$ is a
random instance that is compatible with $y$. Our paper settles the
computational complexity of $\delta$-sufficient-reasons over decision trees,
showing that both (1) finding $\delta$-sufficient-reasons that are minimal in
size, and (2) finding $\delta$-sufficient-reasons that are minimal
inclusion-wise, do not admit polynomial-time algorithms (unless P=NP). This is
in stark contrast with the deterministic case ($\delta = 1$) where
inclusion-wise minimal sufficient-reasons are easy to compute. By doing this,
we answer two open problems originally raised by Izza et al. On the positive
side, we identify structural restrictions of decision trees that make the
problem tractable, and show how SAT solvers might be able to tackle these
problems in practical settings.
- Abstract（参考訳）: フォーマルXAI(説明可能なAI)は、MLモデルによる決定に対する数学的保証を備えたコンピューティングの説明に焦点を当てる成長分野である。
形式xaiの内部において、最も研究されている事例の1つは、伝統的にモデルの最も解釈可能なクラスの一つと見なされる決定木によって取られる選択を説明することである。
最近の研究は「十分な理由」の計算の研究に重点を置いており、決定木$T$とインスタンス$x$が与えられた場合、決定木$T(x)$が$x$の機能のサブセットである$y$を提供することで、$y$と互換性のある他のインスタンス$z$が$y$と互換性がある場合、$T(z) = T(x)$は直感的には、$y$の機能は$x$の分類を完全に正当化するのに十分であることを意味する。
しかし、十分な理由が説明の制限的な概念であり、したがってコミュニティはそれらの確率的対応について研究を始めており、そこでは$t(z) = t(x)$の確率は少なくとも$\delta \in (0, 1]$の値でなければならない。
本稿では,決定木に対する$\delta$-sufficient-reasonsの計算複雑性を考察し,(1)最小サイズの$\delta$-sufficient-reasonsを見つけること,(2)最小の包摂性を持つ$\delta$-sufficient-reasonsは多項式時間アルゴリズム(P=NPを除く)を許容しないことを示す。
これは、包含的に最小限の十分推論が容易に計算できる決定論的ケース(\delta = 1$)とは対照的である。
これにより、元々Izzaらによって提起された2つのオープンな問題に答える。
肯定的な面では、問題を抽出可能な決定木の構造的制約を特定し、SATソルバがこれらの問題に実際にどのように対処できるかを示す。
関連論文リスト
- Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。
我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
論文 参考訳（メタデータ） (2024-06-18T08:54:04Z) - A Theory of Interpretable Approximations [61.90216959710842]
我々は、ある基底クラス $mathcalH$ の概念の小さな集合によってターゲット概念 $c$ を近似するという考え方を研究する。
任意の$mathcalH$と$c$のペアに対して、これらのケースのちょうど1つが成り立つ: (i) $c$を任意の精度で$mathcalH$で近似することはできない。
解釈可能な近似の場合、近似の複雑さに関するわずかに非自明なa-priori保証でさえ、定数(分布自由かつ精度)の近似を意味することを示す。
論文 参考訳（メタデータ） (2024-06-15T06:43:45Z) - On the Trade-off between the Number of Nodes and the Number of Trees in
a Random Forest [8.340919965932443]
我々は、$n$変数の多数関数は、$n-T$が定数であれば、それぞれ大きさで$T$$$(n$)決定ツリーのバッグで表現できることを示した。
k$-out-of-n$関数に関する関連する結果も提示される。
論文 参考訳（メタデータ） (2023-12-16T02:09:34Z) - Superpolynomial Lower Bounds for Decision Tree Learning and Testing [5.117810469621253]
ランダム化されたETHの下では、2つの基本的な問題に対して超ポリノミカルな下界が証明される。
その結果, 分散自由なPAC学習と決定木の試験において, 新たな下位境界が示唆された。
学習決定木の境界の低さを$nOmega(log s)$に改善できることを示します。
論文 参考訳（メタデータ） (2022-10-12T16:25:48Z) - Agnostic learning with unknown utilities [70.14742836006042]
現実世界の多くの問題において、決定の効用は基礎となる文脈である$x$ と decision $y$ に依存する。
我々はこれを未知のユーティリティによる不可知学習として研究する。
サンプルされた点のみのユーティリティを推定することで、よく一般化した決定関数を学習できることを示す。
論文 参考訳（メタデータ） (2021-04-17T08:22:04Z) - Universal guarantees for decision tree induction via a higher-order
splitting criterion [16.832966312395126]
本アルゴリズムは,全対象関数に対して,一様分布に対して, -1,1n から -1,1$ の証明可能な保証を実現する。
我々の拡張の要点は、その属性の$f$と小さなサブセットの相関を考慮に入れた、新しい分割基準である。
我々のアルゴリズムは以下の保証を満たす: すべての対象関数 $f : -1,1n to -1,1$, sizes $sin mathbbN$, error parameters $epsilon$ に対して、決定を構成する。
論文 参考訳（メタデータ） (2020-10-16T21:20:45Z) - An Algorithm for Learning Smaller Representations of Models With Scarce
Data [0.0]
データセットが小さすぎるか、完全に代表的でない状況下で、二項分類問題を解くための欲求的アルゴリズムを提案する。
それは、ゆるやかな精度の制約、反復的なハイパーパラメータプルーニング手順、新しいデータを生成するために使われる関数といった訓練されたモデルに依存している。
論文 参考訳（メタデータ） (2020-10-15T19:17:51Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-06-06T13:34:41Z) - Agnostic Q-learning with Function Approximation in Deterministic
Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。
もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文 参考訳（メタデータ） (2020-02-17T18:41:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。