論文の概要: 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の定理では、すべての決定木は影響のある変数を持つが、すべての決定木がどのようにして「突破」され、結果のツリーのすべての変数が影響を持つかを示す。

関連論文リスト

• Fast decision tree learning solves hard coding-theoretic problems [7.420043502440765]
  我々は、Ehrenfeucht と Haussler のアルゴリズムの改善により、$k$-NCP に対して$O(log n)$-approximation アルゴリズムが得られることを示す。 これは、$k$-NCPのアルゴリズムを設計するための新しい道、あるいはEhrenfeucht と Haussler のアルゴリズムの最適性を確立するための道と解釈できる。
  論文  参考訳（メタデータ） (2024-09-19T21:40:57Z)
• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  本研究では,動的ノード選択とノードレベルの探索予算を備えた新しいガイド付き木探索アルゴリズムを提案する。 GSM8KおよびTabMWPデータセットを用いて行った実験により,本手法はベースライン法に比べて計算コストが大幅に低いことを示した。
  論文  参考訳（メタデータ） (2024-06-29T05:14:04Z)
• Learning a Decision Tree Algorithm with Transformers [75.96920867382859]
  メタ学習によってトレーニングされたトランスフォーマーベースのモデルであるMetaTreeを導入し、強力な決定木を直接生成する。 我々は、多くのデータセットに欲求決定木とグローバルに最適化された決定木の両方を適合させ、MetaTreeを訓練して、強力な一般化性能を実現する木のみを生成する。
  論文  参考訳（メタデータ） (2024-02-06T07:40:53Z)
• 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)
• 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)

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

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