論文の概要: An Exact Junction-Tree Extended Formulation for Optimal Classification Trees

• arxiv url: http://arxiv.org/abs/2609.24741v1
• Date: Mon, 21 Sep 2026 15:10:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-23 03:38:27.406914
• Title: An Exact Junction-Tree Extended Formulation for Optimal Classification Trees
• Title（参考訳）: 最適分類木のための厳密なジャンクショントレー拡張定式化
• Abstract要約: 本稿では,2値特徴を持つ有界深度分類木に対して,正確な線形計画法(LP)を考案する。 その結果, 正確な縮小は, ジャンクションツリーの定式化を著しく減少させることがわかった。
• 参考スコア（独自算出の注目度）: 16.87091101554527
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We develop an exact linear programming (LP) formulation for bounded-depth classification trees with binary features, using a junction-tree representation. The formulation is integral and supports recursive subtree optimization. Exact reductions make the model smaller while preserving the optimal value and recovery of an optimal tree. The reduced model supports two solution methods: column generation and message passing. Column generation solves integral restricted LPs and uses bounds over the full feasible domain to certify optimality. Message passing recursively combines optimal subtree costs. Both methods solve common subtree problems that, once the preceding tree decisions are fixed, can be evaluated independently and in parallel. Computational experiments show that the exact reductions substantially reduce the size of the junction-tree formulation. The resulting linear programming formulation certifies instances for which the tested mixed-integer formulation does not establish optimality within the same computational budget, while the column-generation and message-passing methods certify more instances and achieve an order-of-magnitude reduction in geometric-mean runtime relative to an existing state-of-the-art exact method for optimal classification trees.
• Abstract（参考訳）: 分岐木表現を用いた境界深度分類木に対する厳密な線形プログラミング(LP)の定式化を開発する。 定式化は完全であり、再帰的なサブツリー最適化をサポートする。 厳密な削減により、最適な値と最適な木の回復を保ちながらモデルを小さくすることができる。 縮小モデルはカラム生成とメッセージパッシングという2つのソリューションメソッドをサポートする。 カラム生成は、完全に制限されたLPを解決し、最適性を証明するために完全な実現可能な領域上のバウンダリを使用する。 メッセージパッシングは最適なサブツリーコストと再帰的に結合する。 どちらの手法も、前の木の決定が修正されると、独立に並列に評価できる共通のサブツリー問題を解く。 計算実験により、正確な還元はジャンクションツリーの定式化を著しく減少させることが示された。 得られた線形プログラミング定式化は、試験された混合整数の定式化が同じ計算予算内で最適性を確立しないインスタンスを認証し、列生成およびメッセージパス法は、より多くのインスタンスを認証し、既存の最適な分類木に対する最先端の正確な方法と比較して、幾何平均実行時のオーダー・オブ・マグニチュード還元を達成する。

関連論文リスト

• 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)
• Hinge Regression Tree: A Newton Method for Oblique Regression Tree Splitting [18.562483381753804]
  2つの線形予測器上での非線形最小二乗問題として分割するHynge Regression Tree(HRT)を提案する。 このノードレベルの最適化を解析し、バックトラックライン探索の変種について、局所的な目的が単調に減少し収束することを証明する。 合成および実世界のベンチマークで、HRTはよりコンパクトな構造を持つ単木ベースラインにマッチするか、より優れることを示す。
  論文  参考訳（メタデータ） (2026-02-05T06:49:01Z)
• Birch SGD: A Tree Graph Framework for Local and Asynchronous SGD Methods [51.54704494242525]
  本稿では,分散SGD手法を解析・設計するための新しい統一フレームワークであるBirch SGDを提案する。 本研究では,Birch SGDを用いて8つの新しい手法を設計し,これまでに知られていた手法とともに解析する。 i) すべてのメソッドが$Oleft(frac(R + 1) L Deltavarepsilon + fracsigma2 L Deltavarepsilon2right)$と同じ"イテレーションレート"を共有している。
  論文  参考訳（メタデータ） (2025-05-14T08:37:45Z)
• Soft regression trees: a model variant and a decomposition training algorithm [0.24578723416255752]
  そこで本研究では,各入力ベクトルに対して,単一の葉ノードに関連付けられた線形回帰として定義する,ソフト多変量回帰木(SRT)の新たな変種を提案する。 SRTは条件付き計算特性、すなわち各予測は少数のノードに依存する。 15のよく知られたデータセットの実験により、従来のソフトレグレッションツリーと比較して、我々のSRTと分解アルゴリズムは高い精度とロバスト性が得られることが示された。
  論文  参考訳（メタデータ） (2025-01-10T13:06:36Z)
• Hierarchical clustering with dot products recovers hidden tree structure [53.68551192799585]
  本稿では,階層構造の回復に着目した凝集クラスタリングアルゴリズムの新しい視点を提案する。 クラスタを最大平均点積でマージし、例えば最小距離やクラスタ内分散でマージしないような、標準的なアルゴリズムの単純な変種を推奨する。 このアルゴリズムにより得られた木は、汎用確率的グラフィカルモデルの下で、データ中の生成的階層構造をボナフェイド推定することを示した。
  論文  参考訳（メタデータ） (2023-05-24T11:05:12Z)
• Tight Mixed-Integer Optimization Formulations for Prescriptive Trees [3.0923557923374196]
  本稿では,入力特徴ベクトルと学習した決定木の予測結果との関係をモデル化することに注力する。 従来よりも厳密な混合整数最適化法を提案する。
  論文  参考訳（メタデータ） (2023-02-28T16:44:10Z)
• bsnsing: A decision tree induction method based on recursive optimal boolean rule composition [2.28438857884398]
  本稿では,決定木帰納過程における分割規則選択を最適化するMIP(Mixed-integer Programming)の定式化を提案する。 商用の解法よりも高速に実例を解くことができる効率的な探索解法を開発した。
  論文  参考訳（メタデータ） (2022-05-30T17:13:57Z)
• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
  アルゴリズムの展開は、モデルベースのアルゴリズムの各イテレーションをニューラルネットワーク層として実装することにより、解釈可能で類似のニューラルネットワークアーキテクチャを生成する。 本稿では、Gershgorin disc perfect alignment (GDPA)と呼ばれる最近の線形代数定理を利用して、二進グラフの半定値プログラミング緩和(SDR)のためのプロジェクションフリーアルゴリズムをアンロールする。 実験結果から,我々の未学習ネットワークは純粋モデルベースグラフ分類器よりも優れ,純粋データ駆動ネットワークに匹敵する性能を示したが,パラメータははるかに少なかった。
  論文  参考訳（メタデータ） (2021-09-10T07:01:15Z)
• Convex Polytope Trees [57.56078843831244]
  コンベックスポリトープ木(CPT)は、決定境界の解釈可能な一般化によって決定木の系統を拡張するために提案される。 木構造が与えられたとき,木パラメータに対するCPTおよび拡張性のあるエンドツーエンドトレーニングアルゴリズムを効率的に構築する。
  論文  参考訳（メタデータ） (2020-10-21T19:38:57Z)

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

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