論文の概要: Provable guarantees for decision tree induction: the agnostic setting
- arxiv url: http://arxiv.org/abs/2006.00743v1
- Date: Mon, 1 Jun 2020 06:44:07 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-26 07:51:13.860155
- Title: Provable guarantees for decision tree induction: the agnostic setting
- Title（参考訳）: 決定木誘導の証明可能保証:不可知の設定
- Authors: Guy Blanc and Jane Lange and Li-Yang Tan
- Abstract要約: 我々は、広く採用され、実証的に成功したトップダウン決定木学習の性能に関する証明可能な保証を与える。
すべてのモノトン関数に対して$f$とパラメータ$sin MathN$は、stildeO((log s)/varepsilon2)$でエラーを発生させる決定木を構成する。
アルゴリズムの保証は、ほぼ一致する$stildeOmega(log s)$ lower boundで補います。
- 参考スコア（独自算出の注目度）: 16.784355746717562
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We give strengthened provable guarantees on the performance of widely
employed and empirically successful {\sl top-down decision tree learning
heuristics}. While prior works have focused on the realizable setting, we
consider the more realistic and challenging {\sl agnostic} setting. We show
that for all monotone functions~$f$ and parameters $s\in \mathbb{N}$, these
heuristics construct a decision tree of size $s^{\tilde{O}((\log
s)/\varepsilon^2)}$ that achieves error $\le \mathsf{opt}_s + \varepsilon$,
where $\mathsf{opt}_s$ denotes the error of the optimal size-$s$ decision tree
for $f$. Previously, such a guarantee was not known to be achievable by any
algorithm, even one that is not based on top-down heuristics. We complement our
algorithmic guarantee with a near-matching $s^{\tilde{\Omega}(\log s)}$ lower
bound.
- Abstract（参考訳）: 我々は、広く採用され、実証的に成功した「トップダウン決定木学習ヒューリスティックス」の性能に関する証明可能な保証を与える。
それまでの研究は実現可能な設定に焦点を合わせてきたが、より現実的で挑戦的な設定を考える。
すべての単調関数~$f$ とパラメータ$s\in \mathbb{n}$ に対して、これらのヒューリスティックは、$s^{\tilde{o}((\log s)/\varepsilon^2)} の大きさの決定木を構築し、エラー$\le \mathsf{opt}_s + \varepsilon$ を達成する。
従来、このような保証はいかなるアルゴリズムでも実現可能ではなく、トップダウンヒューリスティックスに基づくものではないことが分かっていた。
我々は、ほぼ一致する$s^{\tilde{\omega}(\log s)}$の下限でアルゴリズム保証を補完する。
関連論文リスト
- 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) - Fully-Dynamic Decision Trees [3.0058005235097114]
ラベル付き例の挿入と削除の任意のシーケンス上で決定木を維持するための,最初の完全動的アルゴリズムを開発した。
実数値機能の場合、このアルゴリズムは挿入/削除毎に$Obig(fracd log3 nepsilon2big)$.amortized run timeを持つ。
同様の保証を持つアルゴリズムは、amortized run time $Omega(d)$と space $tildeOmega (n d)$を使用する。
論文 参考訳（メタデータ） (2022-12-01T18:58:19Z) - Superpolynomial Lower Bounds for Decision Tree Learning and Testing [5.117810469621253]
ランダム化されたETHの下では、2つの基本的な問題に対して超ポリノミカルな下界が証明される。
その結果, 分散自由なPAC学習と決定木の試験において, 新たな下位境界が示唆された。
学習決定木の境界の低さを$nOmega(log s)$に改善できることを示します。
論文 参考訳（メタデータ） (2022-10-12T16:25:48Z) - Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
現在の実用的なBOアルゴリズムは、$mathcalO(fraclogNsqrtN)$から$mathcalO(e-sqrtN)$まで、$N$は評価の数である。
本稿では,boと木に基づく楽観的楽観化の概念を絡み合うことにより,無音環境における後悔を改善できる可能性について検討する。
次数$mathcal O(N-sqrt)で指数的再帰を達成できる最初の実践的手法であるBOOアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-10T13:07:44Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z) - On Avoiding the Union Bound When Answering Multiple Differentially
Private Queries [49.453751858361265]
このタスクのアルゴリズムは、$o(frac1epsilonsqrtk log frac1delta)$の期待値$ell_infty$エラーバウンドを達成する。
一方、DaganとKurkのアルゴリズムは、$O(frac1epsilonsqrtk log frac1delta)$の$ell_infty$エラー境界が期待だけでなく常に保持するという驚くべき利点を持っています。
論文 参考訳（メタデータ） (2020-12-16T17:58:45Z) - Testing and reconstruction via decision trees [19.304587350775385]
決定木に対する部分線形および局所計算アルゴリズムを,テストと再構成に焦点をあてて検討した。
mathrmpoly(log s, 1/varepsilon)cdot nlog n$ time で実行するテスターは、未知の関数への$mathrmpoly(log s, 1/varepsilon)cdot n$ queryを作る。
論文 参考訳（メタデータ） (2020-12-16T04:18:00Z) - 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 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。