論文の概要: Discovering the Interpretability-Performance Pareto Front of Decision Trees with Dynamic Programming

• arxiv url: http://arxiv.org/abs/2309.12701v1
• Date: Fri, 22 Sep 2023 08:18:08 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-25 15:19:48.182598
• Title: Discovering the Interpretability-Performance Pareto Front of Decision Trees with Dynamic Programming
• Title（参考訳）: 動的プログラミングによる決定木の解釈可能性-性能パレットフロントの発見
• Authors: Hector Kohler, Riad Akrour, Philippe Preux
• Abstract要約: 最適決定木を見つけるための新しいマルコフ決定問題(MDP)を提案する。 提案手法は,精度と実行時間の観点から,最先端のアルゴリズムと競合することを示す。
• 参考スコア（独自算出の注目度）: 9.587070290189507
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Decision trees are known to be intrinsically interpretable as they can be inspected and interpreted by humans. Furthermore, recent hardware advances have rekindled an interest for optimal decision tree algorithms, that produce more accurate trees than the usual greedy approaches. However, these optimal algorithms return a single tree optimizing a hand defined interpretability-performance trade-off, obtained by specifying a maximum number of decision nodes, giving no further insights about the quality of this trade-off. In this paper, we propose a new Markov Decision Problem (MDP) formulation for finding optimal decision trees. The main interest of this formulation is that we can compute the optimal decision trees for several interpretability-performance trade-offs by solving a single dynamic program, letting the user choose a posteriori the tree that best suits their needs. Empirically, we show that our method is competitive with state-of-the-art algorithms in terms of accuracy and runtime while returning a whole set of trees on the interpretability-performance Pareto front.
• Abstract（参考訳）: 決定木は人間によって検査され解釈されるため、本質的に解釈可能であることが知られている。 さらに、最近のハードウェアの進歩は、通常よりも正確な木を生成する最適な決定木アルゴリズムへの関心を再燃させた。 しかし、これらの最適アルゴリズムは、決定ノードの最大数を指定することで得られる、手の定義した解釈可能性性能トレードオフを最適化する単一のツリーを返す。 本稿では,最適決定木を求めるための新しいマルコフ決定問題(mdp)を提案する。 この定式化の主な関心は、単一の動的プログラムを解くことで、複数の解釈可能性-性能トレードオフに対する最適決定木を計算し、ユーザがニーズに最も適した木を後部木に選択できるようにすることである。 実験により,本手法は精度と実行時間の観点から最先端のアルゴリズムと競合し,解釈可能性向上のPareto面に木全体の集合を返却することを示す。

関連論文リスト

• An Unsupervised Learning Framework Combined with Heuristics for the Maximum Minimal Cut Problem [5.092968949752308]
  本研究は,MMCPの最大値と非教師なし学習フレームワークを提案する。 重要な観察は、それぞれの溶液が少なくとも1本の枝木に対応することである。 フレームワークを評価し、特定のアプリケーションを提供するために、広範な実験を行います。
  論文  参考訳（メタデータ） (2024-08-16T02:07:34Z)
• TreeDQN: Learning to minimize Branch-and-Bound tree [78.52895577861327]
  Branch-and-Boundは、Mixed Linear Programsという形で最適化タスクを解決するための便利なアプローチである。 解法の効率は、分割する変数を選択するのに使用される分岐に依存する。 分岐を効率的に学習できる強化学習法を提案する。
  論文  参考訳（メタデータ） (2023-06-09T14:01:26Z)
• 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)
• Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories [72.15369769265398]
  機械学習は分岐のための有望なパラダイムとして登場した。 分岐のための単純かつ効果的なRLアプローチであるレトロ分岐を提案する。 我々は現在最先端のRL分岐アルゴリズムを3～5倍に上回り、500の制約と1000の変数を持つMILP上での最高のILメソッドの性能の20%以内である。
  論文  参考訳（メタデータ） (2022-05-28T06:08:07Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。 本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
  論文  参考訳（メタデータ） (2022-01-28T05:53:28Z)
• What's Wrong with Deep Learning in Tree Search for Combinatorial Optimization [8.879790406465556]
  本稿では、NP-hard Maximum Independent Set問題に対するオープンソースのベンチマークスイートについて、その重み付けと非重み付けの両変種について述べる。 また,Li らによる木探索アルゴリズム (NeurIPS 2018) の詳細な解析を行い,小型および大規模合成および実世界のグラフ上で様々な構成を検証した。 木探索で用いられるグラフ畳み込みネットワークは,解構造の有意な表現を学ばず,実際にランダムな値に置き換えることができることを示す。
  論文  参考訳（メタデータ） (2022-01-25T17:37:34Z)
• Modularity in Reinforcement Learning via Algorithmic Independence in Credit Assignment [79.5678820246642]
  提案手法は, 事前決定の順序に対して, スパース変化のみを必要とする伝達問題に対して, 政策段階の手法よりも, より標本効率が高いことを示す。 我々は最近提案された社会的意思決定の枠組みをマルコフ決定プロセスよりもよりきめ細かい形式主義として一般化する。
  論文  参考訳（メタデータ） (2021-06-28T21:29:13Z)
• Learning to Schedule Heuristics in Branch-and-Bound [25.79025327341732]
  現実世界のアプリケーションは通常、迅速な意思決定を可能にするために、検索の早い段階で優れたソリューションを見つける必要があります。 正確なMIPソルバにおけるスケジューリングのための最初のデータ駆動フレームワークを提案する。 最先端の学術MIPソルバーのデフォルト設定と比較して、挑戦的なインスタンスのクラスで平均プライマリ積分を最大49%削減することができます。
  論文  参考訳（メタデータ） (2021-03-18T14:49:52Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。 また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
  論文  参考訳（メタデータ） (2020-11-19T10:00:54Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)

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

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