論文の概要: Properly learning decision trees in almost polynomial time
- arxiv url: http://arxiv.org/abs/2109.00637v1
- Date: Wed, 1 Sep 2021 22:12:47 GMT
- ステータス: 処理完了
- システム内更新日: 2021-09-03 13:41:42.513086
- Title: Properly learning decision trees in almost polynomial time
- Title(参考訳): 決定木をほぼ多項式時間で適切に学習する
- Authors: Guy Blanc, Jane Lange, Mingda Qiao, Li-Yang Tan
- Abstract要約: 我々は,決定木を適切に,不可知的に学習するための$nO(loglog n)$-timeメンバシップクエリアルゴリズムを提案する。
我々のアルゴリズムは、決定木を学習するための実践と類似点を共有している。
すべての決定木がどのようにして「刈り取られる」かを示し、結果のツリーのすべての変数が影響を受けます。
- 参考スコア(独自算出の注目度): 25.763690981846125
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We give an $n^{O(\log\log n)}$-time membership query algorithm for properly
and agnostically learning decision trees under the uniform distribution over
$\{\pm 1\}^n$. Even in the realizable setting, the previous fastest runtime was
$n^{O(\log n)}$, a consequence of a classic algorithm of Ehrenfeucht and
Haussler.
Our algorithm shares similarities with practical heuristics for learning
decision trees, which we augment with additional ideas to circumvent known
lower bounds against these heuristics. To analyze our algorithm, we prove a new
structural result for decision trees that strengthens a theorem of O'Donnell,
Saks, Schramm, and Servedio. While the OSSS theorem says that every decision
tree has an influential variable, we show how every decision tree can be
"pruned" so that every variable in the resulting tree is influential.
- Abstract(参考訳): 我々は$n^{O(\log\log n)}$-timeメンバシップクエリアルゴリズムを、$\{\pm 1\}^n$の均一分布の下で、適切にかつ不可知的に決定木を学習する。
実現可能な設定でも、以前の最速のランタイムは$n^{o(\log n)}$であり、これはehrenfeuchtとhausslerの古典的なアルゴリズムの結果である。
我々のアルゴリズムは決定木を学ぶための実用的なヒューリスティックスと類似性を共有しており、これらのヒューリスティックスに対する既知の下限を回避するために追加のアイデアを追加している。
アルゴリズムを分析するために,o'donnell,saks,schramm,および servedio の定理を強化する決定木に対する新しい構造的結果を証明する。
OSSSの定理では、すべての決定木は影響のある変数を持つが、すべての決定木がどのようにして「突破」され、結果のツリーのすべての変数が影響を持つかを示す。
関連論文リスト
- Learning a Decision Tree Algorithm with Transformers [80.49817544396379]
本稿では,従来のアルゴリズムから出力されたフィルタを用いてトランスフォーマーモデルを用いて,分類のための強力な決定木を生成するメタトレーについて紹介する。
次にMetaTreeをトレーニングして、強力な一般化パフォーマンスを実現するツリーを生成します。
論文 参考訳(メタデータ) (2024-02-06T07:40:53Z) - On Computing Optimal Tree Ensembles [8.941441654913644]
ランダム林や、より一般的には(決定ノブレイクダッシュ-)ツリーアンサンブルは、分類と回帰の方法として広く使われている。
最近のアルゴリズムの進歩は、そのサイズや深さなどの様々な測定に最適な決定木を計算することができる。
2つの新しいアルゴリズムと対応する下位境界を提供する。
論文 参考訳(メタデータ) (2023-06-07T13:30:43Z) - How Smart Guessing Strategies Can Yield Massive Scalability Improvements
for Sparse Decision Tree Optimization [18.294573939199438]
現在のアルゴリズムは、いくつかの実世界のデータセットに対して最適な木またはほぼ最適な木を見つけるために、しばしば非現実的な時間とメモリを必要とする。
本稿では,任意の分岐とバウンダリに基づく決定木アルゴリズムに適用可能なスマート推測手法を用いてこの問題に対処する。
提案手法では, 連続的特徴量, 木の大きさ, 最適決定木に対する誤差の下位境界を推定できる。
論文 参考訳(メタデータ) (2021-12-01T19:39:28Z) - On Finding the $K$-best Non-projective Dependency Trees [39.5549669100436]
我々はCamerini et al. (1980) の$K$-bestスパンニングツリーアルゴリズムを単純化する。
ルート制約を受けるグラフの$K$-best依存木を復号するアルゴリズムを新たに拡張する。
論文 参考訳(メタデータ) (2021-06-01T20:23:41Z) - Learning stochastic decision trees [19.304587350775385]
対向雑音に対して最適に耐性のある決定木を学習するための準ポリノミカル時間アルゴリズムを提案する。
私たちのアルゴリズムはさらに適切で、それ自体が決定木である仮説を返します。
論文 参考訳(メタデータ) (2021-05-08T04:54:12Z) - SGA: A Robust Algorithm for Partial Recovery of Tree-Structured
Graphical Models with Noisy Samples [75.32013242448151]
ノードからの観測が独立しているが非識別的に分散ノイズによって破損した場合、Ising Treeモデルの学習を検討する。
Katiyarら。
(2020) は, 正確な木構造は復元できないが, 部分木構造を復元できることを示した。
統計的に堅牢な部分木回復アルゴリズムであるSymmetrized Geometric Averaging(SGA)を提案する。
論文 参考訳(メタデータ) (2021-01-22T01:57:35Z) - 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) - Convex Polytope Trees [57.56078843831244]
コンベックスポリトープ木(CPT)は、決定境界の解釈可能な一般化によって決定木の系統を拡張するために提案される。
木構造が与えられたとき,木パラメータに対するCPTおよび拡張性のあるエンドツーエンドトレーニングアルゴリズムを効率的に構築する。
論文 参考訳(メタデータ) (2020-10-21T19:38:57Z) - On $\ell_p$-norm Robustness of Ensemble Stumps and Trees [83.81523991945018]
我々は,アンサンブルスタンプの音響検証のための効率的なプログラムベースアルゴリズムを開発した。
我々は,アンサンブル・スタンプや木を訓練するための最初の認証された防御法を,$ell_p$ノルム摂動に関して実証した。
論文 参考訳(メタデータ) (2020-08-20T03:42:40Z) - MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
動的プログラミングと探索に基づいて最適な分類木を学習するための新しいアルゴリズムを提案する。
当社のアプローチでは,最先端技術が必要とする時間のごく一部しか使用せず,数万のインスタンスでデータセットを処理することが可能です。
論文 参考訳(メタデータ) (2020-07-24T17:06:55Z) - Generalized and Scalable Optimal Sparse Decision Trees [56.35541305670828]
様々な目的に対して最適な決定木を生成する手法を提案する。
また,連続変数が存在する場合に最適な結果が得られるスケーラブルなアルゴリズムも導入する。
論文 参考訳(メタデータ) (2020-06-15T19:00:11Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。