論文の概要: Foundational theory for optimal decision tree problems. II. Optimal hypersurface decision tree algorithm

• arxiv url: http://arxiv.org/abs/2509.12057v1
• Date: Mon, 15 Sep 2025 15:38:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-16 17:26:23.375246
• Title: Foundational theory for optimal decision tree problems. II. Optimal hypersurface decision tree algorithm
• Title（参考訳）: 最適決定木問題の基本理論 II. 最適超曲面決定木アルゴリズム
• Authors: Xi He,
• Abstract要約: このシリーズのパート1では、4つの公理を通して適切な決定木モデルを厳格に定義した。 第2部では,第1次超曲面決定木(HODT)アルゴリズムを導入する。
• 参考スコア（独自算出の注目度）: 1.972521190983547
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Decision trees are a ubiquitous model for classification and regression tasks due to their interpretability and efficiency. However, solving the optimal decision tree (ODT) problem remains a challenging combinatorial optimization task. Even for the simplest splitting rules--axis-parallel hyperplanes--it is NP-hard to optimize. In Part I of this series, we rigorously defined the proper decision tree model through four axioms and, based on these, introduced four formal definitions of the ODT problem. From these definitions, we derived four generic algorithms capable of solving ODT problems for arbitrary decision trees satisfying the axioms. We also analyzed the combinatorial geometric properties of hypersurfaces, showing that decision trees defined by polynomial hypersurface splitting rules satisfy the proper axioms that we proposed. In this second paper (Part II) of this two-part series, building on the algorithmic and geometric foundations established in Part I, we introduce the first hypersurface decision tree (HODT) algorithm. To the best of our knowledge, existing optimal decision tree methods are, to date, limited to hyperplane splitting rules--a special case of hypersurfaces--and rely on general-purpose solvers. In contrast, our HODT algorithm addresses the general hypersurface decision tree model without requiring external solvers. Using synthetic datasets generated from ground-truth hyperplane decision trees, we vary tree size, data size, dimensionality, and label and feature noise. Results showing that our algorithm recovers the ground truth more accurately than axis-parallel trees and exhibits greater robustness to noise. We also analyzed generalization performance across 30 real-world datasets, showing that HODT can achieve up to 30% higher accuracy than the state-of-the-art optimal axis-parallel decision tree algorithm when tree complexity is properly controlled.
• Abstract（参考訳）: 決定木は、その解釈可能性と効率性のために分類および回帰タスクのユビキタスモデルである。 しかし、最適決定木(ODT)問題を解くことは、組合せ最適化の課題である。 最も単純な分割規則(軸平行超平面)であっても、最適化はNPハードである。 本シリーズの第1部では, 4つの公理を用いて適切な決定木モデルを厳密に定義し, これらに基づき, ODT問題の4つの公式定義を導入した。 これらの定義から、公理を満たす任意の決定木に対して、ODT問題を解くことができる4つの汎用アルゴリズムを導出した。 また、超曲面の組合せ幾何学的性質を解析し、多項式超曲面分割規則で定義される決定木が、提案した適切な公理を満たすことを示した。 第1部で確立されたアルゴリズム的および幾何学的基礎に基づいて構築されたこの2部シリーズの第2部(パートII)では,第1次超曲面決定木(HODT)アルゴリズムを紹介する。 我々の知る限り、既存の最適決定木法は、これまでは超平面分割規則に限られており、超曲面の特別な場合であり、汎用的な解法に依存している。 対照的に、HODTアルゴリズムは外部解法を必要とせず、一般的な超曲面決定木モデルに対処する。 地表面の超平面決定木から生成された合成データセットを用いて,木の大きさ,データサイズ,寸法,ラベル,特徴雑音を変化させる。 その結果,本アルゴリズムは軸平行木よりも地上の真理を精度良く復元し,騒音に対する頑健性を示すことがわかった。 また,30の実世界のデータセットを対象とした一般化性能を解析し,木々の複雑さを適切に制御した場合,HODTは最先端の最適軸並列決定木アルゴリズムよりも最大30%高い精度で達成可能であることを示した。

関連論文リスト

• Foundational theory for optimal decision tree problems. I. Algorithmic and geometric foundations [1.972521190983547]
  第1部では, ODT問題に関する4つの新しい定義を紹介する。 第2部では,第1次最適超曲面決定木アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-09-14T12:01:02Z)
• Multi-Armed Bandits-Based Optimization of Decision Trees [0.0]
  本稿では,マルチアーマッドバンド (MAB) に基づくプルーニング手法,強化学習 (RL) に基づく手法を提案する。 そこで我々はMABアルゴリズムを用いて各プルーニング動作からのフィードバックに基づいて最適な分岐ノードを見つける。
  論文  参考訳（メタデータ） (2025-08-08T02:43:45Z)
• Provably optimal decision trees with arbitrary splitting rules in polynomial time [1.9405875431318445]
  決定木の最初の公理的定義を提供する。 公理を満たす決定木を適切な決定木と呼ぶ。 最適決定木問題の解法として,初めて証明可能な正解時間アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2025-03-03T12:14:53Z)
• Learning a Decision Tree Algorithm with Transformers [75.96920867382859]
  メタ学習によってトレーニングされたトランスフォーマーベースのモデルであるMetaTreeを導入し、強力な決定木を直接生成する。 我々は、多くのデータセットに欲求決定木とグローバルに最適化された決定木の両方を適合させ、MetaTreeを訓練して、強力な一般化性能を実現する木のみを生成する。
  論文  参考訳（メタデータ） (2024-02-06T07:40:53Z)
• Breiman meets Bellman: Non-Greedy Decision Trees with MDPs [8.530182510074983]
  我々は、欲求と最適なアプローチのギャップを埋めるフレームワークDPDT(Dynamic Programming Decision Trees)を提案する。 DPDTはマルコフ決定プロセスの定式化と分割生成を組み合わせ、ほぼ最適決定木を構築する。 実験の結果,DPDTは既存の最適解法よりも桁違いに少ない演算でほぼ最適損失を達成できた。
  論文  参考訳（メタデータ） (2023-09-22T08:18:08Z)
• 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)
• ENTMOOT: A Framework for Optimization over Ensemble Tree Models [57.98561336670884]
  ENTMOOTは、ツリーモデルをより大きな最適化問題に統合するためのフレームワークである。 ENTMOOTは、ツリーモデルの意思決定とブラックボックス最適化への単純な統合を可能にしていることを示す。
  論文  参考訳（メタデータ） (2020-03-10T14:34:07Z)

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

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