Fugu-MT 論文翻訳(概要): Harnessing the Power of Choices in Decision Tree Learning

論文の概要: Harnessing the Power of Choices in Decision Tree Learning

arxiv url: http://arxiv.org/abs/2310.01551v2
Date: Wed, 25 Oct 2023 20:40:49 GMT
ステータス: 処理完了
システム内更新日: 2023-10-28 00:45:06.695872
Title: Harnessing the Power of Choices in Decision Tree Learning
Title（参考訳）: 決定木学習における選択力の活用
Authors: Guy Blanc, Jane Lange, Chirag Pabbaraju, Colin Sullivan, Li-Yang Tan, Mo Tiwari
Abstract要約: 本稿では,ID3,C4.5,CARTなどの決定木学習アルゴリズムを簡易に一般化し,実証的に成功した決定木学習アルゴリズムを提案する。私たちのアルゴリズムであるTop-$k$は、$k$のベスト属性を単一のベスト属性ではなく、可能な分割として考慮しています。広範な実験を通して、Top-k$は、決定木学習の2つの主要なアプローチより優れていることを示す。
参考スコア（独自算出の注目度）: 20.08390529995706
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We propose a simple generalization of standard and empirically successful decision tree learning algorithms such as ID3, C4.5, and CART. These algorithms, which have been central to machine learning for decades, are greedy in nature: they grow a decision tree by iteratively splitting on the best attribute. Our algorithm, Top-$k$, considers the $k$ best attributes as possible splits instead of just the single best attribute. We demonstrate, theoretically and empirically, the power of this simple generalization. We first prove a {\sl greediness hierarchy theorem} showing that for every $k \in \mathbb{N}$, Top-$(k+1)$ can be dramatically more powerful than Top-$k$: there are data distributions for which the former achieves accuracy $1-\varepsilon$, whereas the latter only achieves accuracy $\frac1{2}+\varepsilon$. We then show, through extensive experiments, that Top-$k$ outperforms the two main approaches to decision tree learning: classic greedy algorithms and more recent "optimal decision tree" algorithms. On one hand, Top-$k$ consistently enjoys significant accuracy gains over greedy algorithms across a wide range of benchmarks. On the other hand, Top-$k$ is markedly more scalable than optimal decision tree algorithms and is able to handle dataset and feature set sizes that remain far beyond the reach of these algorithms.
Abstract（参考訳）: 本稿では,ID3,C4.5,CARTなどの決定木学習アルゴリズムの簡易な一般化を提案する。これらのアルゴリズムは、機械学習の中心として何十年も使われてきたが、本質的には、最良の属性を反復的に分割することで決定木を成長させる。当社のアルゴリズムであるtop-$k$は、単一のベスト属性ではなく、可能な限りの分割として$k$を考慮します。我々は、理論上、経験的に、この単純な一般化の力を示す。まず、"sl greediness hierarchy theorem} を証明し、すべての$k \in \mathbb{n}$, top-$(k+1)$ がtop-$k$よりも劇的に強力になることを示した。次に、広範囲な実験を通じて、トップ$k$が決定木学習の2つの主要なアプローチ、すなわち古典的な欲望アルゴリズムとより最近の「最適決定木」アルゴリズムを上回ることを示した。一方、Top-k$は、幅広いベンチマークでグレーディアルゴリズムよりも高い精度を常に享受している。一方、top-$k$は最適決定木アルゴリズムよりも著しくスケーラブルであり、これらのアルゴリズムの到達範囲をはるかに超えるデータセットや特徴量を扱うことができる。

関連論文リスト

A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文参考訳（メタデータ） (2024-02-09T19:01:48Z)
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)
On Computing Optimal Tree Ensembles [7.424944196676223]
ランダム林や、より一般的には(決定ノブレイクダッシュ-)ツリーアンサンブルは、分類と回帰の方法として広く使われている。最近のアルゴリズムの進歩は、そのサイズや深さなどの様々な測定に最適な決定木を計算することができる。 2つの新しいアルゴリズムと対応する下位境界を提供する。
論文参考訳（メタデータ） (2023-06-07T13:30:43Z)
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)
Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文参考訳（メタデータ） (2023-01-31T19:14:30Z)
Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文参考訳（メタデータ） (2023-01-11T09:12:28Z)
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)
Optimal Low-Degree Hardness of Maximum Independent Set [93.59919600451487]
スパースな ErdHos-R'enyi ランダムグラフにおいて,大きな独立集合を求めるアルゴリズム的タスクについて検討する。低次アルゴリズムのクラスは、半最適サイズの独立した集合を見つけることができるが、それ以上は見つからないことを示す。
論文参考訳（メタデータ） (2020-10-13T17:26:09Z)
MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
動的プログラミングと探索に基づいて最適な分類木を学習するための新しいアルゴリズムを提案する。当社のアプローチでは,最先端技術が必要とする時間のごく一部しか使用せず,数万のインスタンスでデータセットを処理することが可能です。
論文参考訳（メタデータ） (2020-07-24T17:06:55Z)
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)
Optimal Sparse Decision Trees [25.043477914272046]
この研究は、二変数に対する最適決定木のための最初の実用的なアルゴリズムを導入する。このアルゴリズムは、探索空間と現代のシステム技術を減らす分析的境界の共設計である。我々の実験はスケーラビリティ、スピード、最適性の証明の利点を強調します。
論文参考訳（メタデータ） (2019-04-29T17:56:34Z)

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

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