論文の概要: Necessary and Sufficient Conditions for Optimal Decision Trees using Dynamic Programming

• arxiv url: http://arxiv.org/abs/2305.19706v3
• Date: Mon, 15 Jan 2024 13:06:10 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-18 02:46:49.998758
• Title: Necessary and Sufficient Conditions for Optimal Decision Trees using Dynamic Programming
• Title（参考訳）: 動的プログラミングを用いた最適決定木の必要十分条件
• Authors: Jacobus G. M. van der Linden, Mathijs M. de Weerdt, Emir Demirovi\'c
• Abstract要約: サブツリーを独立なサブプロブレムとして解き、木構造を利用する方法を示す。 我々は、従来の動的プログラミングアプローチを、分離可能な目的と制約の組み合わせを最適化できるフレームワークに一般化する。
• 参考スコア（独自算出の注目度）: 8.815461200424776
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Global optimization of decision trees has shown to be promising in terms of accuracy, size, and consequently human comprehensibility. However, many of the methods used rely on general-purpose solvers for which scalability remains an issue. Dynamic programming methods have been shown to scale much better because they exploit the tree structure by solving subtrees as independent subproblems. However, this only works when an objective can be optimized separately for subtrees. We explore this relationship in detail and show the necessary and sufficient conditions for such separability and generalize previous dynamic programming approaches into a framework that can optimize any combination of separable objectives and constraints. Experiments on five application domains show the general applicability of this framework, while outperforming the scalability of general-purpose solvers by a large margin.
• Abstract（参考訳）: 決定木のグローバル最適化は、正確性、大きさ、その結果、人間の理解性の観点から有望であることが示されている。 しかし、使用するメソッドの多くは、スケーラビリティが問題である汎用解法に依存している。 動的プログラミング手法は、サブツリーを独立したサブプロブレムとして解くことによってツリー構造を利用するため、はるかに拡張されている。 しかし、これは目的が別々にサブツリーに最適化できる場合にのみ機能する。 この関係を詳細に検討し、そのような分離性に必要な条件を示し、従来の動的プログラミングアプローチを、分離可能な目的と制約の組み合わせを最適化できるフレームワークに一般化する。 5つのアプリケーションドメインにおける実験により、このフレームワークの一般的な適用性が示され、汎用解法のスケーラビリティを大きく上回っている。

関連論文リスト

• Feature-Based Interpretable Surrogates for Optimization [0.8437187555622164]
  本研究では、より一般的な最適化ルールを用いて解釈可能性を高める方法について検討する。 提案したルールは、具体的な解ではなく、共通の特徴を特徴とする解の集合にマップされる。 特に,提案手法が提案するソリューションの品質向上を,既存の解釈可能な最適化サロゲートと比較して実証する。
  論文  参考訳（メタデータ） (2024-09-03T13:12:49Z)
• Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spaces [54.58348769621782]
  木アンサンブルはアルゴリズムチューニングやニューラルアーキテクチャ検索といったブラックボックス最適化タスクに適している。 ブラックボックス最適化にツリーアンサンブルを使うことの2つのよく知られた課題は、探索のためのモデル不確実性を効果的に定量化し、また、 (ii) ピースワイドな定値取得関数を最適化することである。 我々のフレームワークは、連続/離散的機能に対する非拘束ブラックボックス最適化のための最先端の手法と同様に、混合変数の特徴空間と既知の入力制約を組み合わせた問題の競合する手法よりも優れている。
  論文  参考訳（メタデータ） (2022-07-02T16:59:37Z)
• Quant-BnB: A Scalable Branch-and-Bound Method for Optimal Decision Trees with Continuous Features [5.663538370244174]
  本稿では,分岐とバウンド(BnB)に基づく新たな離散最適化手法を提案する。 提案アルゴリズムのQuant-BnBは,様々な実データセット上での浅い最適木に対する既存手法と比較して,大幅な高速化を示す。
  論文  参考訳（メタデータ） (2022-06-23T17:19:29Z)
• Multi-Objective Constrained Optimization for Energy Applications via Tree Ensembles [55.23285485923913]
  エネルギーシステムの最適化問題は、強い非線形系の挙動と複数の競合する目的のために複雑である。 場合によっては、提案された最適解は、物理的性質や安全クリティカルな操作条件に関連する明示的な入力制約に従う必要がある。 本稿では,ブラックボックス問題に対する制約付き多目的最適化のためのツリーアンサンブルを用いた新しいデータ駆動戦略を提案する。
  論文  参考訳（メタデータ） (2021-11-04T20:18:55Z)
• 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)
• Polynomial-Time Exact MAP Inference on Discrete Models with Global Dependencies [83.05591911173332]
  ジャンクションツリーアルゴリズムは、実行時の保証と正確なMAP推論のための最も一般的な解である。 本稿では,ノードのクローン化による新たなグラフ変換手法を提案する。
  論文  参考訳（メタデータ） (2019-12-27T13:30:29Z)

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

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