論文の概要: Tightness of prescriptive tree-based mixed-integer optimization
formulations
- arxiv url: http://arxiv.org/abs/2302.14744v1
- Date: Tue, 28 Feb 2023 16:44:10 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-01 15:20:45.294432
- Title: Tightness of prescriptive tree-based mixed-integer optimization
formulations
- Title（参考訳）: 説明的木に基づく混合整数最適化の厳密性
- Authors: Max Biggs and Georgia Perakis
- Abstract要約: 本稿では,入力特徴ベクトルと学習した決定木の予測結果との関係をモデル化することに注力する。
従来よりも厳密な混合整数最適化法を提案する。
- 参考スコア（独自算出の注目度）: 2.538209532048867
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We focus on modeling the relationship between an input feature vector and the
predicted outcome of a trained decision tree using mixed-integer optimization.
This can be used in many practical applications where a decision tree or tree
ensemble is incorporated into an optimization problem to model the predicted
outcomes of a decision. We propose tighter mixed-integer optimization
formulations than those previously introduced. Existing formulations can be
shown to have linear relaxations that have fractional extreme points, even for
the simple case of modeling a single decision tree. A formulation we propose,
based on a projected union of polyhedra approach, is ideal for a single
decision tree. While the formulation is generally not ideal for tree ensembles
or if additional constraints are added, it generally has fewer extreme points,
leading to a faster time to solve, particularly if the formulation has
relatively few trees. However, previous work has shown that formulations based
on a binary representation of the feature vector perform well computationally
and hence are attractive for use in practical applications. We present multiple
approaches to tighten existing formulations with binary vectors, and show that
fractional extreme points are removed when there are multiple splits on the
same feature. At an extreme, we prove that this results in ideal formulations
for tree ensembles modeling a one-dimensional feature vector. Building on this
result, we also show via numerical simulations that these additional
constraints result in significantly tighter linear relaxations when the feature
vector is low dimensional. We also present instances where the time to solve to
optimality is significantly improved using these formulations.
- Abstract（参考訳）: 本研究では,入力特徴ベクトルと学習決定木の予測結果との関係を混合整数最適化を用いてモデル化する。
これは、決定木またはツリーアンサンブルが最適化問題に組み込まれ、決定の予測結果がモデル化される多くの実用的なアプリケーションで使用できる。
従来よりも厳密な混合整数最適化法を提案する。
既存の定式化は、単一の決定木をモデリングする単純な場合であっても、最小の極点を持つ線形緩和を持つことが示される。
私たちが提案する定式化は、射影されたポリヘドラアプローチに基づいて、単一の決定木に最適である。
定式化は一般に木のアンサンブルには適さないが、追加の制約を加えると、極端な点がより少なくなり、特に比較的少数の木がある場合、解ける時間が短縮される。
しかし、以前の研究では、特徴ベクトルのバイナリ表現に基づく定式化がよく計算され、実用的な応用には魅力的なことが示されている。
既存の定式化をバイナリベクトルで引き締める複数のアプローチを示し、同じ特徴に複数の分割がある場合、分数極点が取り除かれることを示す。
極端に、これは1次元特徴ベクトルをモデル化したツリーアンサンブルの理想的な定式化をもたらすことを証明している。
この結果に基づいて,これらの制約が,特徴ベクトルが低次元である場合の線形緩和を著しく厳密にすることを示す数値シミュレーションも行った。
また,これらの定式化を用いて最適解法時間を大幅に改善する事例も提示する。
関連論文リスト
- Free Lunch in the Forest: Functionally-Identical Pruning of Boosted Tree Ensembles [45.962492329047215]
木アンサンブルを原モデルと「機能的に同一」な縮小版にプルークする方法を提案する。
我々は,アンサンブル上での機能的同一プルーニングの問題を形式化し,正確な最適化モデルを導入し,大規模なアンサンブルをプルーする高速かつ高効率な方法を提供する。
論文 参考訳（メタデータ） (2024-08-28T23:15:46Z) - Unboxing Tree Ensembles for interpretability: a hierarchical
visualization tool and a multivariate optimal re-built tree [0.34530027457862006]
我々は,木組モデルの解釈可能な表現を開発し,その振る舞いに関する貴重な洞察を提供する。
提案モデルは,木組決定関数を近似した浅い解釈可能な木を得るのに有効である。
論文 参考訳（メタデータ） (2023-02-15T10:43:31Z) - Optimal Sparse Regression Trees [24.03491277969824]
本研究は,確率的最適スパース回帰木の構築に対する動的プログラミングとバウンドのアプローチを提案する。
ラベル集合上の1次元におけるk平均クラスタリングアルゴリズムの最適解に基づいて、新しい下界を利用する。
論文 参考訳（メタデータ） (2022-11-28T00:43:21Z) - bsnsing: A decision tree induction method based on recursive optimal
boolean rule composition [2.28438857884398]
本稿では,決定木帰納過程における分割規則選択を最適化するMIP(Mixed-integer Programming)の定式化を提案する。
商用の解法よりも高速に実例を解くことができる効率的な探索解法を開発した。
論文 参考訳（メタデータ） (2022-05-30T17:13:57Z) - Robust Optimal Classification Trees Against Adversarial Examples [5.254093731341154]
本稿では,ユーザが特定した攻撃モデルに対して最適に堅牢な決定木を訓練する手法の集合を提案する。
逆学習において生じるmin-max最適化問題は、単一最小化定式化を用いて解くことができることを示す。
また,両部マッチングを用いた任意のモデルに対して,上界の対角精度を決定する手法を提案する。
論文 参考訳（メタデータ） (2021-09-08T18:10:49Z) - Partition-based formulations for mixed-integer optimization of trained
ReLU neural networks [66.88252321870085]
本稿では,訓練されたReLUニューラルネットワークのための混合整数式について紹介する。
1つの極端な場合、入力毎に1つのパーティションがノードの凸殻、すなわち各ノードの最も厳密な可能な定式化を回復する。
論文 参考訳（メタデータ） (2021-02-08T17:27:34Z) - Convex Polytope Trees [57.56078843831244]
コンベックスポリトープ木(CPT)は、決定境界の解釈可能な一般化によって決定木の系統を拡張するために提案される。
木構造が与えられたとき,木パラメータに対するCPTおよび拡張性のあるエンドツーエンドトレーニングアルゴリズムを効率的に構築する。
論文 参考訳（メタデータ） (2020-10-21T19:38:57Z) - 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) - MINA: Convex Mixed-Integer Programming for Non-Rigid Shape Alignment [77.38594866794429]
非剛体形状マッチングのための凸混合整数プログラミングの定式化。
効率的な低次元離散モデルに基づく新しい形状変形モデルを提案する。
論文 参考訳（メタデータ） (2020-02-28T09:54:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。