論文の概要: Scaling Optimal Classification Trees via Adaptive Feature and Sample Reduction
- arxiv url: http://arxiv.org/abs/2609.05826v1
- Date: Sat, 05 Sep 2026 02:42:53 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-10 19:44:08.143376
- Title: Scaling Optimal Classification Trees via Adaptive Feature and Sample Reduction
- Title（参考訳）: 適応的特徴とサンプル還元による最適分類木のスケーリング
- Abstract要約: 我々はSTreeDに基づく特徴空間とサンプル空間の合同計算フレームワークを開発した。
重み付きSTreeDは、固定された候補に投影後に生成された重複レコードを重み付き代表にマージする。
Adaptive STreeDは、境界付き候補集合を何度も洗練し、既存のツリーで使われる特徴を保持し、重み付き表現を再構築し、結果として生じる問題を解く。
- 参考スコア（独自算出の注目度）: 16.87091101554527
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Dynamic programming for optimal classification trees becomes computationally expensive as the numbers of features and training samples increase. We develop a joint feature- and sample-space reduction framework based on STreeD. Weighted STreeD merges duplicate records created after projection onto a fixed candidate set into weighted representatives. This reduces sample-dependent computation without changing the fixed-candidate optimization problem. Adaptive STreeD repeatedly refines a bounded candidate set, retains features used by the incumbent tree, rebuilds the weighted representation, and solves the resulting reduced problems. Each certified Weighted STreeD solution is optimal for its current candidate set, while the outer feature search remains heuristic over the full feature space. Experiments on five data sets show that Weighted STreeD achieves speedups of up to 121.41 times over standard STreeD. Adaptive STreeD reduces runtime in matched comparisons at depths 2 to 4 and continues to return feasible trees at greater depths where full-feature methods are limited by time or memory. Under the same computational budget, its predictive performance remains comparable to the evaluated optimal classification tree baselines and is higher in some comparisons. These results show how joint feature- and sample-space reduction can scale dynamic-programming-based optimal-tree learning to more demanding instances.
- Abstract（参考訳）: 最適分類木に対する動的プログラミングは,特徴数やトレーニングサンプルの増加に伴って計算コストが増大する。
我々はSTreeDに基づく特徴量削減フレームワークとサンプル空間削減フレームワークを開発した。
重み付きSTreeDは、固定された候補に投影後に生成された重複レコードを重み付き代表にマージする。
これにより、固定候補最適化問題を変更することなく、サンプル依存の計算を削減できる。
Adaptive STreeDは、境界付き候補集合を何度も洗練し、既存のツリーで使われる特徴を保持し、重み付き表現を再構築し、結果として生じる問題を解く。
認定された各STreeDソリューションは、現在の候補セットに対して最適であるが、外的特徴探索は完全な特徴空間に対してヒューリスティックである。
5つのデータセットの実験により、Weighted STreeDは標準STreeDの最大121.41倍のスピードアップを達成することが示された。
Adaptive STreeDは、深さ2から4までの一致した比較のランタイムを削減し、フル機能のメソッドが時間やメモリによって制限されている場合、より深い深さで実行可能なツリーを返す。
同じ計算予算の下では、その予測性能は評価された最適な分類木ベースラインに匹敵し、いくつかの比較では高い。
これらの結果は,動的プログラミングに基づく最適木学習を,より要求の高いインスタンスに拡張できることを示す。
関連論文リスト
- Literati: Towards Anytime Optimal Shape Generalized Trees via AO* [3.469167914196103]
形状一般化木(SGT)は、形状関数を一般化し、表現性を改善し、よりコンパクトな木を可能にする。
既存のSGT誘導アルゴリズムは欲張りであり、最適性を保証するものではない。
最適SGT誘導のための最初のアルゴリズムであるLiteratiを紹介する。
論文 参考訳（メタデータ） (2026-09-08T18:00:21Z) - TreeGrad-Ranker: Feature Ranking via $O(L)$-Time Gradients for Decision Trees [73.0940890296463]
確率値は、決定木の局所的な予測値を説明する特徴のランク付けに使用される。
TreeGradは、共同目的の多重線型拡張の勾配を$O(L)$時間で計算する。
TreeGrad-Rankerは、機能ランキングを生成するために共同目標を最適化しながら、勾配を集約する。
TreeGrad-Shapは、積分パラメータを持つベータシェープ値を計算するための数値的に安定なアルゴリズムである。
論文 参考訳（メタデータ） (2026-02-12T06:17:12Z) - Fast Inference of Visual Autoregressive Model with Adjacency-Adaptive Dynamical Draft Trees [50.230925890958936]
本稿では,隣接するトークン状態と先行受入率を活用することで,ドラフトツリーの深さと幅を調整できる適応型動的ドラフトツリーを提案する。
ADT-Treeは、それぞれ3.13xと3.05xのスピードアップを実現し、LANTERNのような緩やかなサンプリング手法とシームレスに統合する。
論文 参考訳（メタデータ） (2025-12-26T04:45:49Z) - RS-ORT: A Reduced-Space Branch-and-Bound Algorithm for Optimal Regression Trees [2.612627266839037]
MIP(Mixed-integer Programming)は最適な決定木を学習するための強力なフレームワークとして登場した。
連続的な特徴を内在的にバイナライズすることは、グローバルな最適性を犠牲にし、しばしば不必要に深い木を産み出す。
最適回帰木学習を2段階最適化問題として再放送し、RS-ORT(Reduceed-Space Optimal Regression Trees)を提案する。
RS-ORTは木構造変数のみに枝分かれする特殊分岐結合(BB)アルゴリズムである。
論文 参考訳（メタデータ） (2025-10-27T22:17:09Z) - TreePO: Bridging the Gap of Policy Optimization and Efficacy and Inference Efficiency with Heuristic Tree-based Modeling [65.46347858249295]
TreePOは自己誘導型ロールアウトアルゴリズムで、シーケンス生成を木構造検索プロセスとして見る。
TreePOは基本的に、探索の多様性を保存または強化しながら、更新毎の計算負担を削減します。
論文 参考訳（メタデータ） (2025-08-24T16:52:37Z) - Soft regression trees: a model variant and a decomposition training algorithm [0.24578723416255752]
そこで本研究では,各入力ベクトルに対して,単一の葉ノードに関連付けられた線形回帰として定義する,ソフト多変量回帰木(SRT)の新たな変種を提案する。
SRTは条件付き計算特性、すなわち各予測は少数のノードに依存する。
15のよく知られたデータセットの実験により、従来のソフトレグレッションツリーと比較して、我々のSRTと分解アルゴリズムは高い精度とロバスト性が得られることが示された。
論文 参考訳（メタデータ） (2025-01-10T13:06:36Z) - Can a Single Tree Outperform an Entire Forest? [5.448070998907116]
一般的な考え方は、単一の決定木は、テスト精度において古典的なランダムな森林を過小評価する。
本研究では,斜め回帰木の試験精度を大幅に向上させることで,このような考え方に挑戦する。
本手法は,木習熟を非制約最適化タスクとして再編成する。
論文 参考訳（メタデータ） (2024-11-26T00:18:18Z) - bsnsing: A decision tree induction method based on recursive optimal
boolean rule composition [2.28438857884398]
本稿では,決定木帰納過程における分割規則選択を最適化するMIP(Mixed-integer Programming)の定式化を提案する。
商用の解法よりも高速に実例を解くことができる効率的な探索解法を開発した。
論文 参考訳（メタデータ） (2022-05-30T17:13:57Z) - SGA: A Robust Algorithm for Partial Recovery of Tree-Structured
Graphical Models with Noisy Samples [75.32013242448151]
ノードからの観測が独立しているが非識別的に分散ノイズによって破損した場合、Ising Treeモデルの学習を検討する。
Katiyarら。
(2020) は, 正確な木構造は復元できないが, 部分木構造を復元できることを示した。
統計的に堅牢な部分木回復アルゴリズムであるSymmetrized Geometric Averaging(SGA)を提案する。
論文 参考訳（メタデータ） (2021-01-22T01:57:35Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。