論文の概要: Proper decision trees: An axiomatic framework for solving optimal decision tree problems with arbitrary splitting rules
- arxiv url: http://arxiv.org/abs/2503.01455v2
- Date: Thu, 23 Oct 2025 08:48:37 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-25 03:08:04.325773
- Title: Proper decision trees: An axiomatic framework for solving optimal decision tree problems with arbitrary splitting rules
- Title（参考訳）: 適切な決定木:任意の分割規則で最適な決定木問題を解決するための公理的枠組み
- Authors: Xi He, Max A. Little,
- Abstract要約: 本稿では,決定木のアルゴリズム特性を解析するための公理的枠組みを提案する。
本論文の中心となるのは決定木問題であり,その汎用性と有効性から,適切な決定木と呼ぶ。
メモリ化は一般に、データセットとサブツリーの両方を格納しなければならないため、空間複雑性の観点からは非現実的であることを示す。
- 参考スコア（独自算出の注目度）: 2.5505924504226223
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: We present an axiomatic framework for analyzing the algorithmic properties of decision trees. This framework supports the classification of decision tree problems through structural and ancestral constraints within a rigorous mathematical foundation. The central focus of this paper is a special class of decision tree problems-which we term proper decision trees-due to their versatility and effectiveness. In terms of versatility, this class subsumes several well-known data structures, including binary space partitioning trees, K-D trees, and machine learning decision tree models. Regarding effectiveness, we prove that only proper decision trees can be uniquely characterized as K-permutations, whereas typical non-proper decision trees correspond to binary-labeled decision trees with substantially greater complexity. Using this formal characterization, we develop a generic algorithmic approach for solving optimal decision tree problems over arbitrary splitting rules and objective functions for proper decision trees. We constructively derive a generic dynamic programming recursion for solving these problems exactly. However, we show that memoization is generally impractical in terms of space complexity, as both datasets and subtrees must be stored. This result contradicts claims in the literature that suggest a trade-off between memoizing datasets and subtrees. Our framework further accommodates constraints such as tree depth and leaf size, and can be accelerated using techniques such as thinning. Finally, we extend our analysis to several non-proper decision trees, including the commonly studied decision tree over binary feature data, the binary search tree, and the tree structure arising in the matrix chain multiplication problem. We demonstrate how these problems can be solved by appropriately modifying or discarding certain axioms.
- Abstract（参考訳）: 本稿では,決定木のアルゴリズム特性を解析するための公理的枠組みを提案する。
この枠組みは厳密な数学的基礎の中での構造的制約と祖先的制約を通じて決定木問題の分類を支援する。
本論文の中心となるのは決定木問題であり,その汎用性と有効性から,適切な決定木と呼ぶ。
汎用性の観点から言えば、このクラスはバイナリ空間分割木、K-D木、機械学習決定木モデルなど、よく知られたデータ構造を仮定する。
有効性については、K-置換として固有な決定木のみを特徴付けることができるのに対し、典型的な非適切な決定木は、かなり複雑なバイナリラベル決定木に対応する。
この形式的特徴付けを用いて、任意の分割規則と適切な決定木に対する目的関数に対して最適な決定木問題を解くための汎用的なアルゴリズム的アプローチを開発する。
我々はこれらの問題を正確に解くための汎用動的プログラム再帰を構成的に導出する。
しかし,メモリ化は一般に,データセットとサブツリーの両方を格納しなければならないため,空間複雑性の観点からは非現実的であることを示す。
この結果は、メモリ化データセットとサブツリーの間のトレードオフを示唆する文献の主張に矛盾する。
さらに,木深や葉の大きさなどの制約を緩和し,薄型化などの手法で高速化する。
最後に,2次特徴データよりもよく研究される決定木,2次探索木,行列連鎖乗算問題に起因する木構造など,いくつかの不適切な決定木に解析を拡張した。
特定の公理を適切に修正あるいは破棄することで、これらの問題をいかに解決できるかを実証する。
関連論文リスト
- Optimal Decision Tree Pruning Revisited: Algorithms and Complexity [22.57063332430197]
我々は,サブツリーの更新と育成の基本的な作業に焦点をあてる。
サブツリー置換に間に合うように最適プルーニングを行うことができるが、サブツリーの更新にはNP完全である。
例えば、サブツリーの上昇は小さなドメインサイズでは難しいが、$D2d cdot |I|O(1)$timeでは、$|I|$が入力サイズである。
論文 参考訳（メタデータ） (2025-03-05T15:02:46Z) - Learning accurate and interpretable tree-based models [27.203303726977616]
我々は、同じドメインからデータに繰り返しアクセスする木に基づく学習アルゴリズムを設計するためのアプローチを開発する。
本稿では,よく使われるエントロピーとジニ不純物に基づく基準を補間するトップダウンアルゴリズムにおいて,ノード分割基準の新しいパラメータ化クラスを提案する。
我々は、ランダムな森林や傾斜した木など、一般的な木に基づくアンサンブルのチューニングに結果を拡張した。
論文 参考訳（メタデータ） (2024-05-24T20:10:10Z) - An Algorithmic Framework for Constructing Multiple Decision Trees by
Evaluating Their Combination Performance Throughout the Construction Process [1.8749305679160366]
決定木の組み合わせによる予測は機械学習に有効であることが知られている。
本稿では,決定木を同時に構築し,それらの組み合わせ性能を評価するアルゴリズムフレームワークを提案する。
論文 参考訳（メタデータ） (2024-02-09T14:58:07Z) - Learning a Decision Tree Algorithm with Transformers [75.96920867382859]
メタ学習によってトレーニングされたトランスフォーマーベースのモデルであるMetaTreeを導入し、強力な決定木を直接生成する。
我々は、多くのデータセットに欲求決定木とグローバルに最適化された決定木の両方を適合させ、MetaTreeを訓練して、強力な一般化性能を実現する木のみを生成する。
論文 参考訳（メタデータ） (2024-02-06T07:40:53Z) - TreeDQN: Learning to minimize Branch-and-Bound tree [78.52895577861327]
Branch-and-Boundは、Mixed Linear Programsという形で最適化タスクを解決するための便利なアプローチである。
解法の効率は、分割する変数を選択するのに使用される分岐に依存する。
分岐を効率的に学習できる強化学習法を提案する。
論文 参考訳（メタデータ） (2023-06-09T14:01:26Z) - Construction of Decision Trees and Acyclic Decision Graphs from Decision
Rule Systems [0.0]
本稿では,決定木を構成する複雑さと決定木を表す非周期決定グラフについて考察する。
決定木全体を構築しない可能性について論じるが、与えられた入力に対して、この木で計算経路を記述する。
論文 参考訳（メタデータ） (2023-05-02T18:40:48Z) - Improved Quantum Query Upper Bounds Based on Classical Decision Trees [0.7812210699650152]
古典的なクエリアルゴリズムが決定木として与えられると、古典的なクエリアルゴリズムよりも高速な量子クエリアルゴリズムはいつ存在するのか?
我々は、下層の決定木の構造に基づく一般的な構成を提供し、これが上から四進的な量子スピードアップをもたらすことを証明している。
論文 参考訳（メタデータ） (2022-03-06T14:04:06Z) - Decision Machines: Congruent Decision Trees [0.0]
本稿では,ブール試験を二進ベクトル空間に埋め込み,木構造を行列として表現する決定機械を提案する。
我々は,決定木と注意機構の一致を探求し,決定木を最適化し,予測力を増強するための新たな道を開く。
論文 参考訳（メタデータ） (2021-01-27T12:23:24Z) - 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) - Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies [76.83991682238666]
Branch and Bound (B&B) は、Mixed-Integer Linear Programming Problem (MILP) の解法として一般的に用いられる木探索法である。
本稿では,新しい模倣学習フレームワークを提案し,分岐を表現するための新しい入力機能とアーキテクチャを提案する。
論文 参考訳（メタデータ） (2020-02-12T17:43:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。