論文の概要: Optimal Decision Tree Pruning Revisited: Algorithms and Complexity

• arxiv url: http://arxiv.org/abs/2503.03576v1
• Date: Wed, 05 Mar 2025 15:02:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-06 15:51:32.140023
• Title: Optimal Decision Tree Pruning Revisited: Algorithms and Complexity
• Title（参考訳）: 最適決定木刈り再考:アルゴリズムと複雑度
• Authors: Juha Harviainen, Frank Sommer, Manuel Sorge, Stefan Szeider,
• Abstract要約: 我々は,サブツリーの更新と育成の基本的な作業に焦点をあてる。 サブツリー置換に間に合うように最適プルーニングを行うことができるが、サブツリーの更新にはNP完全である。 例えば、サブツリーの上昇は小さなドメインサイズでは難しいが、$D2d cdot |I|O(1)$timeでは、$|I|$が入力サイズである。
• 参考スコア（独自算出の注目度）: 22.57063332430197
• License:
• Abstract: We present a comprehensive classical and parameterized complexity analysis of decision tree pruning operations, extending recent research on the complexity of learning small decision trees. Thereby, we offer new insights into the computational challenges of decision tree simplification, a crucial aspect of developing interpretable and efficient machine learning models. We focus on fundamental pruning operations of subtree replacement and raising, which are used in heuristics. Surprisingly, while optimal pruning can be performed in polynomial time for subtree replacement, the problem is NP-complete for subtree raising. Therefore, we identify parameters and combinations thereof that lead to fixed-parameter tractability or hardness, establishing a precise borderline between these complexity classes. For example, while subtree raising is hard for small domain size $D$ or number $d$ of features, it can be solved in $D^{2d} \cdot |I|^{O(1)}$ time, where $|I|$ is the input size. We complement our theoretical findings with preliminary experimental results, demonstrating the practical implications of our analysis.
• Abstract（参考訳）: 本稿では、決定木刈り作業の古典的・パラメータ化複雑性解析を包括的に実施し、小決定木学習の複雑さに関する最近の研究を延長する。 そこで、我々は、解釈可能かつ効率的な機械学習モデルを開発する上で重要な側面である、決定木単純化の計算上の課題について、新たな知見を提供する。 ヒューリスティックス(ヒューリスティックス)で使用されるサブツリーの更新と育成の根本的刈り取り作業に焦点をあてる。 驚くべきことに、サブツリー置換のための多項式時間で最適刈り取りを行うことができるが、サブツリーの更新にはNP完全である。 そこで我々は, パラメータと組み合わせを同定し, これらの複雑性クラス間の正確な境界線を確立する。 例えば、サブツリーの上昇は、小さなドメインサイズ$D$、または数$d$のフィーチャーでは難しいが、$D^{2d} \cdot |I|^{O(1)}$timeでは、$|I|$が入力サイズである。 予備的な実験結果と理論的知見を補完し,本研究の実践的意義を実証した。

関連論文リスト

• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  本研究では,動的ノード選択とノードレベルの探索予算を備えた新しいガイド付き木探索アルゴリズムを提案する。 GSM8KおよびTabMWPデータセットを用いて行った実験により,本手法はベースライン法に比べて計算コストが大幅に低いことを示した。
  論文  参考訳（メタデータ） (2024-06-29T05:14:04Z)
• Learning accurate and interpretable decision trees [27.203303726977616]
  我々は、同じドメインから繰り返しデータにアクセスして決定木学習アルゴリズムを設計するためのアプローチを開発する。 本研究では,ベイズ決定木学習における事前パラメータのチューニングの複雑さについて検討し,その結果を決定木回帰に拡張する。 また、学習した決定木の解釈可能性について検討し、決定木を用いた説明可能性と精度のトレードオフを最適化するためのデータ駆動型アプローチを提案する。
  論文  参考訳（メタデータ） (2024-05-24T20:10:10Z)
• TreeDQN: Learning to minimize Branch-and-Bound tree [78.52895577861327]
  Branch-and-Boundは、Mixed Linear Programsという形で最適化タスクを解決するための便利なアプローチである。 解法の効率は、分割する変数を選択するのに使用される分岐に依存する。 分岐を効率的に学習できる強化学習法を提案する。
  論文  参考訳（メタデータ） (2023-06-09T14:01:26Z)
• On Single-Objective Sub-Graph-Based Mutation for Solving the Bi-Objective Minimum Spanning Tree Problem [0.0]
  我々は、進化的計算を取り入れた$mathcalNP$-hard multi-objective least- spanning tree problem (moMST)の効率的な近似に寄与する。 得られた知見に基づいて、高バイアスのサブグラフベースの突然変異演算子を設計する。 その結果,サブグラフベースの演算子が文献のベースラインアルゴリズムに勝っていることを確認した。
  論文  参考訳（メタデータ） (2023-05-31T22:35:17Z)
• Properly learning decision trees in almost polynomial time [25.763690981846125]
  我々は,決定木を適切に,不可知的に学習するための$nO(loglog n)$-timeメンバシップクエリアルゴリズムを提案する。 我々のアルゴリズムは、決定木を学習するための実践と類似点を共有している。 すべての決定木がどのようにして「刈り取られる」かを示し、結果のツリーのすべての変数が影響を受けます。
  論文  参考訳（メタデータ） (2021-09-01T22:12:47Z)
• Robustifying Algorithms of Learning Latent Trees with Vector Variables [92.18777020401484]
  Recursive Grouping (RG) と Chow-Liu Recursive Grouping (CLRG) のサンプル複雑性について述べる。 RG,CLRG,Neighbor Joining (NJ) およびSpectral NJ (SNJ) をトラッピングした内積を用いて強化する。 我々は、潜在木の構造学習において、最初の既知のインスタンス依存の不合理性の結果を導出する。
  論文  参考訳（メタデータ） (2021-06-02T01:37:52Z)
• Growing Deep Forests Efficiently with Soft Routing and Learned Connectivity [79.83903179393164]
  この論文は、いくつかの重要な側面で深い森林のアイデアをさらに拡張します。 我々は、ノードがハードバイナリ決定ではなく、確率的ルーティング決定、すなわちソフトルーティングを行う確率的ツリーを採用する。 MNISTデータセットの実験は、私たちの力のある深部森林が[1]、[3]よりも優れたまたは匹敵するパフォーマンスを達成できることを示しています。
  論文  参考訳（メタデータ） (2020-12-29T18:05:05Z)
• Estimating decision tree learnability with polylogarithmic sample complexity [16.832966312395126]
  トップダウン決定木学習は,高効率な学習可能性推定に有効であることを示す。 決定木仮説のラベル $T(xstar$)$ が多対数的に多くのラベル付き例で計算可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-03T09:26:27Z)
• 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)
• Born-Again Tree Ensembles [9.307453801175177]
  ツリーアンサンブルは、様々な領域で優れた予測品質を提供するが、複数のツリーの同時使用により、アンサンブルの解釈可能性が低下する。 本研究では,その特徴空間全体において,与えられたツリーのアンサンブルと全く同じ振る舞いを再現する,最小サイズの1つの決定木を構築する過程について検討する。 このアルゴリズムは、実践的な関心のある多くのデータセットに対して最適な生長木を生成する。
  論文  参考訳（メタデータ） (2020-03-24T22:17:21Z)

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

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