論文の概要: Decision Tree Learning on Product Spaces

• arxiv url: http://arxiv.org/abs/2605.12983v1
• Date: Wed, 13 May 2026 04:26:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-14 23:30:27.808936
• Title: Decision Tree Learning on Product Spaces
• Title（参考訳）: 製品空間における決定木学習
• Authors: Arshia Soltani Moakahr, Faraz Ghahremani, Kiarash Banihashem, MohammadTaghi Hajiaghayi,
• Abstract要約: 任意の関数 $fimat$ に対して、$s$, max depth $D_textopt$, average depth $_textopt$ が最適な決定木で計算可能であることを示す。 また、最適化木の大きさや深さに関する事前知識を必要とせず、完全にパラメータフリーであるトップダウンの欲求に基づくアルゴリズムも提示する。
• 参考スコア（独自算出の注目度）: 19.61677355524952
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Decision tree learning has long been a central topic in theoretical computer science, driven by its practical importance. A fundamental and widely used method for decision tree construction is the top-down greedy heuristic, which recursively splits on the most influential variable. Despite its empirical success, theoretical analysis of this heuristic has been limited. A recent breakthrough by Blanc et al. (ITCS, 2020) provided the first rigorous theoretical guarantees for the greedy approach, but only under the uniform distribution. We extend this analysis to the more general and practically relevant setting of arbitrary product distributions. Our main result shows that for any function $f$ computable by an optimal decision tree of size $s$, maximum depth $D_{\text{opt}}$, and average depth $Δ_{\text{opt}}$, the greedy heuristic constructs an $ε$-approximating tree whose size grows at most with $\exp\bigl(Δ_{\text{opt}} D_{\text{opt}} \log(e/ε)\bigr)$. In the special case where the optimal tree is a full binary tree, this bound improves upon the bound of Blanc et al. and holds under a strictly broader class of distributions. Moreover, we present an algorithm based on the top-down greedy heuristic that is entirely parameter-free -- it requires no prior knowledge of the optimal tree's size or depth -- offering a practical advantage over Blanc et al.'s method.
• Abstract（参考訳）: 決定木学習は、その実践的重要性によって引き起こされた理論計算機科学において、長い間中心的な話題であった。 決定木構築の根本的で広く用いられる方法は、最も影響力のある変数について再帰的に分割するトップダウンの欲求的ヒューリスティック(英語版)である。 経験的な成功にもかかわらず、このヒューリスティックの理論的な分析は限られている。 Blanc et al (ITCS, 2020) による最近のブレークスルーは、強欲なアプローチに対する厳密な理論的保証を提供したが、一様分布に留まった。 この分析は、任意の積分布のより一般的で実用的な設定にまで拡張する。 我々の主な結果は、任意の関数$f$計算可能で、$s$, maximum depth$D_{\text{opt}}$, average depth$Δ_{\text{opt}}$, the greedy heuristic constructs a $ε$-approximating tree with size at least grows at $\exp\bigl(Δ_{\text{opt}} D_{\text{opt}} \log(e/ε)\bigr)$であることを示している。 最適木が完全二分木である特別な場合、この境界はブランとアルの境界によって改善され、厳密な分布のクラスの下に保持される。 さらに、最適化木の大きさや深さに関する事前の知識を必要とせず、完全にパラメータフリーな、トップダウンの欲求ヒューリスティックに基づくアルゴリズムを提案する。

関連論文リスト

• TreeGrad-Ranker: Feature Ranking via $O(L)$-Time Gradients for Decision Trees [73.0940890296463]
  確率値は、決定木の局所的な予測値を説明する特徴のランク付けに使用される。 TreeGradは、共同目的の多重線型拡張の勾配を$O(L)$時間で計算する。 TreeGrad-Rankerは、機能ランキングを生成するために共同目標を最適化しながら、勾配を集約する。 TreeGrad-Shapは、積分パラメータを持つベータシェープ値を計算するための数値的に安定なアルゴリズムである。
  論文  参考訳（メタデータ） (2026-02-12T06:17:12Z)
• Optimal Decision Tree Pruning Revisited: Algorithms and Complexity [22.57063332430197]
  我々は,サブツリーの更新と育成の基本的な作業に焦点をあてる。 サブツリー置換に間に合うように最適プルーニングを行うことができるが、サブツリーの更新にはNP完全である。 例えば、サブツリーの上昇は小さなドメインサイズでは難しいが、$D2d cdot |I|O(1)$timeでは、$|I|$が入力サイズである。
  論文  参考訳（メタデータ） (2025-03-05T15:02:46Z)
• Learning a Decision Tree Algorithm with Transformers [75.96920867382859]
  メタ学習によってトレーニングされたトランスフォーマーベースのモデルであるMetaTreeを導入し、強力な決定木を直接生成する。 我々は、多くのデータセットに欲求決定木とグローバルに最適化された決定木の両方を適合させ、MetaTreeを訓練して、強力な一般化性能を実現する木のみを生成する。
  論文  参考訳（メタデータ） (2024-02-06T07:40:53Z)
• Harnessing the Power of Choices in Decision Tree Learning [20.08390529995706]
  本稿では,ID3,C4.5,CARTなどの決定木学習アルゴリズムを簡易に一般化し,実証的に成功した決定木学習アルゴリズムを提案する。 私たちのアルゴリズムであるTop-$k$は、$k$のベスト属性を単一のベスト属性ではなく、可能な分割として考慮しています。 広範な実験を通して、Top-k$は、決定木学習の2つの主要なアプローチより優れていることを示す。
  論文  参考訳（メタデータ） (2023-10-02T18:45:46Z)
• Properly learning decision trees in almost polynomial time [25.763690981846125]
  我々は,決定木を適切に,不可知的に学習するための$nO(loglog n)$-timeメンバシップクエリアルゴリズムを提案する。 我々のアルゴリズムは、決定木を学習するための実践と類似点を共有している。 すべての決定木がどのようにして「刈り取られる」かを示し、結果のツリーのすべての変数が影響を受けます。
  論文  参考訳（メタデータ） (2021-09-01T22:12:47Z)
• On Finding the $K$-best Non-projective Dependency Trees [39.5549669100436]
  我々はCamerini et al. (1980) の$K$-bestスパンニングツリーアルゴリズムを単純化する。 ルート制約を受けるグラフの$K$-best依存木を復号するアルゴリズムを新たに拡張する。
  論文  参考訳（メタデータ） (2021-06-01T20:23:41Z)
• Convex Polytope Trees [57.56078843831244]
  コンベックスポリトープ木(CPT)は、決定境界の解釈可能な一般化によって決定木の系統を拡張するために提案される。 木構造が与えられたとき,木パラメータに対するCPTおよび拡張性のあるエンドツーエンドトレーニングアルゴリズムを効率的に構築する。
  論文  参考訳（メタデータ） (2020-10-21T19:38:57Z)
• 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)

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

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