論文の概要: Universal guarantees for decision tree induction via a higher-order
splitting criterion
- arxiv url: http://arxiv.org/abs/2010.08633v1
- Date: Fri, 16 Oct 2020 21:20:45 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-06 20:47:17.476921
- Title: Universal guarantees for decision tree induction via a higher-order
splitting criterion
- Title（参考訳）: 高次分割基準による決定木誘導の普遍的保証
- Authors: Guy Blanc, Neha Gupta, Jane Lange, Li-Yang Tan
- Abstract要約: 本アルゴリズムは,全対象関数に対して,一様分布に対して, -1,1n から -1,1$ の証明可能な保証を実現する。
我々の拡張の要点は、その属性の$f$と小さなサブセットの相関を考慮に入れた、新しい分割基準である。
我々のアルゴリズムは以下の保証を満たす: すべての対象関数 $f : -1,1n to -1,1$, sizes $sin mathbbN$, error parameters $epsilon$ に対して、決定を構成する。
- 参考スコア（独自算出の注目度）: 16.832966312395126
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose a simple extension of top-down decision tree learning heuristics
such as ID3, C4.5, and CART. Our algorithm achieves provable guarantees for all
target functions $f: \{-1,1\}^n \to \{-1,1\}$ with respect to the uniform
distribution, circumventing impossibility results showing that existing
heuristics fare poorly even for simple target functions. The crux of our
extension is a new splitting criterion that takes into account the correlations
between $f$ and small subsets of its attributes. The splitting criteria of
existing heuristics (e.g. Gini impurity and information gain), in contrast, are
based solely on the correlations between $f$ and its individual attributes.
Our algorithm satisfies the following guarantee: for all target functions $f
: \{-1,1\}^n \to \{-1,1\}$, sizes $s\in \mathbb{N}$, and error parameters
$\epsilon$, it constructs a decision tree of size $s^{\tilde{O}((\log
s)^2/\epsilon^2)}$ that achieves error $\le O(\mathsf{opt}_s) + \epsilon$,
where $\mathsf{opt}_s$ denotes the error of the optimal size $s$ decision tree.
A key technical notion that drives our analysis is the noise stability of $f$,
a well-studied smoothness measure.
- Abstract（参考訳）: 本稿では,ID3,C4.5,CARTなどのトップダウン決定木学習ヒューリスティックスの簡易拡張を提案する。
本アルゴリズムは,全対象関数に対する証明可能な保証値である$f: \{-1,1\}^n \to \{-1,1\}$を均一分布に対して達成する。
我々の拡張の要点は、その属性の$f$と小さなサブセットの相関を考慮に入れた、新しい分割基準である。
既存のヒューリスティックの分割基準(例えば、giniの不純物と情報ゲイン)は、対照的に、$f$とその個々の属性の相関のみに基づいている。
すべての対象関数$f : \{-1,1\}^n \to \{-1,1\}$, sizes $s\in \mathbb{n}$, and error parameters $\epsilon$に対しては、$s^{\tilde{o}((\log s)^2/\epsilon^2)} というサイズの決定木を構築し、$\le o(\mathsf{opt}_s) + \epsilon$, ここで $\mathsf{opt}_s$ は最適なサイズ$s$ 決定ツリーのエラーを表す。
我々の分析を駆動する重要な技術的概念は、よく研究された滑らか度尺度である$f$のノイズ安定性である。
関連論文リスト
- Monge-Kantorovich Fitting With Sobolev Budgets [6.748324975906262]
近似の性能をMonge-Kantorovich $p$-costで定量化する。
次に、ソボレフ予算の制約の下で、機能的$mathscrJ_p(f)$を最小化するものとして問題を再構築する。
論文 参考訳（メタデータ） (2024-09-25T01:30:16Z) - Differentially Private Kernel Density Estimation [11.526850085349155]
我々は、カーネル密度推定(KDE)のための洗練された微分プライベート(DP)データ構造を導入する。
類似関数 $f$ とプライベートデータセット $X サブセット mathbbRd$ が与えられた場合、我々のゴールは、任意のクエリ $yinmathbbRd$ に対して、X f(x, y)$ の $sum_x を微分プライベートな方法で近似するように$X$ を前処理することである。
論文 参考訳（メタデータ） (2024-09-03T08:01:19Z) - Adaptive approximation of monotone functions [0.0]
GreedyBox が任意の関数 $f$ に対して,対数因子まで,最適なサンプル複雑性を実現することを証明した。
おそらく予想通り、GreedyBoxの$Lp(mu)$エラーは、アルゴリズムによって予測されるよりもはるかに高速な$C2$関数で減少する。
論文 参考訳（メタデータ） (2023-09-14T08:56:31Z) - Fully-Dynamic Approximate Decision Trees With Worst-Case Update Time
Guarantees [3.5509551353363644]
ラベル付き例の挿入と削除の任意の順序に近似的な決定木を保持する最初のアルゴリズムを与える。
我々は$O!left(fracd, f(n)n operatornamenamepolyfrachepsilonright)$ Operations per updateを使って$epsilon$-approximate treeを維持する決定論的アルゴリズムを提供する。
論文 参考訳（メタデータ） (2023-02-08T11:02:58Z) - Submodular + Concave [53.208470310734825]
第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。
本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。
このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
論文 参考訳（メタデータ） (2021-06-09T01:59:55Z) - 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) - Provable guarantees for decision tree induction: the agnostic setting [16.784355746717562]
我々は、広く採用され、実証的に成功したトップダウン決定木学習の性能に関する証明可能な保証を与える。
すべてのモノトン関数に対して$f$とパラメータ$sin MathN$は、stildeO((log s)/varepsilon2)$でエラーを発生させる決定木を構成する。
アルゴリズムの保証は、ほぼ一致する$stildeOmega(log s)$ lower boundで補います。
論文 参考訳（メタデータ） (2020-06-01T06:44:07Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z) - 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) - On the Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。
同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文 参考訳（メタデータ） (2020-02-09T03:39:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。