論文の概要: Optimal Classification Trees for Continuous Feature Data Using Dynamic Programming with Branch-and-Bound

• arxiv url: http://arxiv.org/abs/2501.07903v1
• Date: Tue, 14 Jan 2025 07:46:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-15 13:26:03.858507
• Title: Optimal Classification Trees for Continuous Feature Data Using Dynamic Programming with Branch-and-Bound
• Title（参考訳）: 分岐境界を用いた動的プログラミングを用いた連続特徴データのための最適分類木
• Authors: Catalin E. Brita, Jacobus G. M. van der Linden, Emir Demirović,
• Abstract要約: 与えられたサイズ制限内でのトレーニング性能を最大化する最適な分類木はNPハードであり、実際にはほとんどの最先端手法は、深さ3の最適木を計算できない。 本稿では,分岐とバウンドを持つ動的プログラミングを用いて,連続的な特徴データに基づいて木を直接最適化する新しいアルゴリズムを提案する。 実験により、これらの手法は、最先端の最適手法よりも1桁以上の実行時間を改善するとともに、グレディよりもテスト精度を5%向上することを示した。
• 参考スコア（独自算出の注目度）: 1.3654846342364308
• License:
• Abstract: Computing an optimal classification tree that provably maximizes training performance within a given size limit, is NP-hard, and in practice, most state-of-the-art methods do not scale beyond computing optimal trees of depth three. Therefore, most methods rely on a coarse binarization of continuous features to maintain scalability. We propose a novel algorithm that optimizes trees directly on the continuous feature data using dynamic programming with branch-and-bound. We develop new pruning techniques that eliminate many sub-optimal splits in the search when similar to previously computed splits and we provide an efficient subroutine for computing optimal depth-two trees. Our experiments demonstrate that these techniques improve runtime by one or more orders of magnitude over state-of-the-art optimal methods and improve test accuracy by 5% over greedy heuristics.
• Abstract（参考訳）: 与えられたサイズ制限内でトレーニング性能を確実に最大化する最適な分類木を計算することはNPハードであり、実際にはほとんどの最先端の手法は、深さ3の最適木を計算しない。 したがって、ほとんどの手法はスケーラビリティを維持するために連続した機能の粗い双項化に依存している。 本稿では,分岐とバウンドを持つ動的プログラミングを用いて,連続的な特徴データに基づいて木を直接最適化する新しいアルゴリズムを提案する。 我々は,従来計算されていた分割と同様の探索において,多くの部分最適分割を排除し,最適深度2木を計算するための効率的なサブルーチンを提供する新しいプルーニング手法を開発した。 実験により,これらの手法は,最先端の最適手法よりも1桁以上のランタイム向上と,強欲なヒューリスティックスよりも5%の精度向上を実現していることが示された。

関連論文リスト

• Learning Deep Tree-based Retriever for Efficient Recommendation: Theory and Method [76.31185707649227]
  効率的なレコメンデーションのために,Deep Tree-based Retriever (DTR)を提案する。 DTRは、トレーニングタスクを、同じレベルでツリーノード上のソフトマックスベースのマルチクラス分類としてフレーム化している。 非リーフノードのラベル付けによって引き起こされる準最適性を緩和するため、損失関数の補正法を提案する。
  論文  参考訳（メタデータ） (2024-08-21T05:09:53Z)
• Branches: A Fast Dynamic Programming and Branch & Bound Algorithm for Optimal Decision Trees [12.403737756721467]
  決定木(DT)学習は、解釈可能な機械学習の基本的な問題である。 両アプローチの長所を組み合わせた新しいアルゴリズムであるブランチを導入する。 DPとB&Bは効率的な刈り出しのための新しい解析的境界を持つため、ブランチは速度とスパーシティの最適化の両方を提供する。
  論文  参考訳（メタデータ） (2024-06-04T10:11:46Z)
• Improved Algorithms for Neural Active Learning [74.89097665112621]
  非パラメトリックストリーミング設定のためのニューラルネットワーク(NN)ベースの能動学習アルゴリズムの理論的および経験的性能を改善する。 本研究では,SOTA(State-of-the-art (State-the-art)) 関連研究で使用されるものよりも,アクティブラーニングに適する人口減少を最小化することにより,2つの後悔の指標を導入する。
  論文  参考訳（メタデータ） (2022-10-02T05:03:38Z)
• Efficient Non-Parametric Optimizer Search for Diverse Tasks [93.64739408827604]
  興味のあるタスクを直接検索できる,スケーラブルで汎用的なフレームワークを初めて提示する。 基礎となる数学表現の自然木構造に着想を得て、空間を超木に再配置する。 我々は,モンテカルロ法を木探索に適用し,レジェクションサンプリングと等価形状検出を備える。
  論文  参考訳（メタデータ） (2022-09-27T17:51:31Z)
• 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)
• 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)
• Learning Optimal Classification Trees: Strong Max-Flow Formulations [8.10995244893652]
  線形プログラミングの緩和を強くした最適二分分類木に対するフローベースMIP定式化を提案する。 我々はこの構造と最大フロー/最小カットの双対性を利用してベンダーズ分解法を導出する。
  論文  参考訳（メタデータ） (2020-02-21T05:58:17Z)

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

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