論文の概要: Foundational theory for optimal decision tree problems. I. Algorithmic and geometric foundations
- arxiv url: http://arxiv.org/abs/2509.11226v1
- Date: Sun, 14 Sep 2025 12:01:02 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-09-16 17:26:22.985367
- Title: Foundational theory for optimal decision tree problems. I. Algorithmic and geometric foundations
- Title（参考訳）: 最適決定木問題の基本理論 I. アルゴリズムと幾何学の基礎
- Authors: Xi He,
- Abstract要約: 第1部では, ODT問題に関する4つの新しい定義を紹介する。
第2部では,第1次最適超曲面決定木アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 1.972521190983547
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: In the first paper (part I) of this series of two, we introduce four novel definitions of the ODT problems: three for size-constrained trees and one for depth-constrained trees. These definitions are stated unambiguously through executable recursive programs, satisfying all criteria we propose for a formal specification. In this sense, they resemble the "standard form" used in the study of general-purpose solvers. Grounded in algebraic programming theory-a relational formalism for deriving correct-by-construction algorithms from specifications-we can not only establish the existence or nonexistence of dynamic programming solutions but also derive them constructively whenever they exist. Consequently, the four generic problem definitions yield four novel optimal algorithms for ODT problems with arbitrary splitting rules that satisfy the axioms and objective functions of a given form. These algorithms encompass the known depth-constrained, axis-parallel ODT algorithm as the special case, while providing a unified, efficient, and elegant solution for the general ODT problem. In Part II, we present the first optimal hypersurface decision tree algorithm and provide comprehensive experiments against axis-parallel decision tree algorithms, including heuristic CART and state-of-the-art optimal methods. The results demonstrate the significant potential of decision trees with flexible splitting rules. Moreover, our framework is readily extendable to support algorithms for constructing even more flexible decision trees, including those with mixed splitting rules.
- Abstract（参考訳）: 本シリーズの第1部(第1部)では, ODT問題の新たな定義として, サイズ制約木を3つ, 深さ制約木を1つ導入する。
これらの定義は実行可能再帰プログラムを通して曖昧に記述され、形式仕様の提案する全ての基準を満たす。
この意味では、汎用解法の研究で使われる「標準形式」に類似している。
代数的プログラミング理論に根ざした、正しい構成アルゴリズムを仕様から導出するための関係形式論は、動的プログラミング解の存在や非存在を確立できるだけでなく、その存在がいつでも構成的に導出できる。
その結果、4つの一般的な問題定義は、与えられた形式の公理と目的関数を満たす任意の分割規則を持つ ODT 問題に対して4つの新しい最適アルゴリズムをもたらす。
これらのアルゴリズムは、一般的な ODT 問題に対して統一的で効率的でエレガントな解を提供しながら、既知の深さ制約付き軸並列 ODT アルゴリズムを特別なケースとして含む。
パートIIでは,第1の最適超曲面決定木アルゴリズムを提示し,ヒューリスティックCARTや最先端最適手法を含む軸並列決定木アルゴリズムに対する包括的実験を行う。
その結果、フレキシブルな分割ルールを持つ決定木の有意なポテンシャルが示された。
さらに, このフレームワークは, 分割ルールの混在など, より柔軟な決定木を構築するアルゴリズムをサポートするために, 容易に拡張可能である。
関連論文リスト
- Foundational theory for optimal decision tree problems. II. Optimal hypersurface decision tree algorithm [1.972521190983547]
このシリーズのパート1では、4つの公理を通して適切な決定木モデルを厳格に定義した。
第2部では,第1次超曲面決定木(HODT)アルゴリズムを導入する。
論文 参考訳（メタデータ） (2025-09-15T15:38:44Z) - Provably optimal decision trees with arbitrary splitting rules in polynomial time [1.9405875431318445]
決定木の最初の公理的定義を提供する。
公理を満たす決定木を適切な決定木と呼ぶ。
最適決定木問題の解法として,初めて証明可能な正解時間アルゴリズムを開発した。
論文 参考訳（メタデータ） (2025-03-03T12:14:53Z) - Theoretical Analysis of Quality Diversity Algorithms for a Classical Path Planning Problem [12.1622929638257]
本稿では,古典的計画問題に対する品質多様性(QD)アルゴリズムの挙動について検討する。
この結果から,Map-Elites QDアルゴリズムは各ノードの最短経路を並列に計算できることがわかった。
論文 参考訳（メタデータ） (2024-12-16T04:58:32Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。
微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文 参考訳（メタデータ） (2023-02-24T18:41:48Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - 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) - Evolutionary algorithms for constructing an ensemble of decision trees [0.0]
本稿では,進化的アルゴリズムに基づく決定木とそのアンサンブルの誘導法を提案する。
我々のアプローチの主な違いは、決定木の実値ベクトル表現を使うことである。
いくつかの公開UCIデータセットを用いて,本手法の予測性能を検証した。
論文 参考訳（メタデータ） (2020-02-03T13:38:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。