論文の概要: Provably optimal decision trees with arbitrary splitting rules in polynomial time
- arxiv url: http://arxiv.org/abs/2503.01455v1
- Date: Mon, 03 Mar 2025 12:14:53 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-05 19:14:15.470793
- Title: Provably optimal decision trees with arbitrary splitting rules in polynomial time
- Title（参考訳）: 多項式時間における任意の分割規則を持つ確率最適決定木
- Authors: Xi He, Max A. Little,
- Abstract要約: 決定木の最初の公理的定義を提供する。
公理を満たす決定木を適切な決定木と呼ぶ。
最適決定木問題の解法として,初めて証明可能な正解時間アルゴリズムを開発した。
- 参考スコア（独自算出の注目度）: 1.9405875431318445
- License:
- Abstract: In this paper, we introduce a generic data structure called decision trees, which integrates several well-known data structures, including binary search trees, K-D trees, binary space partition trees, and decision tree models from machine learning. We provide the first axiomatic definition of decision trees. These axioms establish a firm mathematical foundation for studying decision tree problems. We refer to decision trees that satisfy the axioms as proper decision trees. We prove that only proper decision trees can be uniquely characterized as K-permutations. Since permutations are among the most well-studied combinatorial structures, this characterization provides a fundamental basis for analyzing the combinatorial and algorithmic properties of decision trees. As a result of this advancement, we develop the first provably correct polynomial-time algorithm for solving the optimal decision tree problem. Our algorithm is derived using a formal program derivation framework, which enables step-by-step equational reasoning to construct side-effect-free programs with guaranteed correctness. The derived algorithm is correct by construction and is applicable to decision tree problems defined by any splitting rules that adhere to the axioms and any objective functions that can be specified in a given form. Examples include the decision tree problems where splitting rules are defined by axis-parallel hyperplanes, arbitrary hyperplanes, and hypersurfaces. By extending the axioms, we can potentially address a broader range of problems. Moreover, the derived algorithm can easily accommodate various constraints, such as tree depth and leaf size, and is amenable to acceleration techniques such as thinning method.
- Abstract（参考訳）: 本稿では、二分探索木、K-D木、二分空間分割木、機械学習による決定木モデルなど、よく知られたデータ構造を統合する、決定木と呼ばれる一般的なデータ構造を紹介する。
決定木の最初の公理的定義を提供する。
これらの公理は決定木問題を研究するための確かな数学的基礎を確立する。
公理を満たす決定木を適切な決定木と呼ぶ。
適切な決定木のみが一意に K-置換として特徴づけられることを証明している。
置換は最もよく研究されている組合せ構造であるため、この特徴付けは決定木の組合せ的およびアルゴリズム的特性を分析するための基礎となる。
この進歩の結果、最適決定木問題を解くための証明可能な最初の多項式時間アルゴリズムを開発した。
提案アルゴリズムは, 正規プログラム導出フレームワークを用いて導出され, ステップ・バイ・ステップの方程式推論により, 正確性を保証するサイドエフェクトフリーなプログラムを構築することができる。
導出アルゴリズムは、構成によって正しいものであり、公理に従属する任意の分割規則と与えられた形式で特定できる任意の目的関数によって定義される決定木問題に適用できる。
例えば、分割規則が軸平行超平面、任意の超平面、超曲面によって定義される決定木問題がある。
公理を拡張することで、幅広い問題に対処できる可能性がある。
さらに, 木深や葉の大きさなどの制約に容易に対応でき, 薄型化法などの加速技術にも適用可能である。
関連論文リスト
- 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) - Greedy Algorithm for Inference of Decision Trees from Decision Rule
Systems [0.0]
決定木と決定ルールシステムは属性、知識表現ツール、アルゴリズムとして重要な役割を果たす。
本稿では,逆変換問題について考察する。
本研究は,決定木全体を構築する代わりに,与えられた属性に対する決定木の操作をシミュレートする欲求時間アルゴリズムに焦点を当てる。
論文 参考訳（メタデータ） (2024-01-08T09:28:55Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。