論文の概要: Optimal Mixed Integer Linear Optimization Trained Multivariate Classification Trees
- arxiv url: http://arxiv.org/abs/2408.01297v1
- Date: Fri, 2 Aug 2024 14:37:28 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-05 13:17:55.938724
- Title: Optimal Mixed Integer Linear Optimization Trained Multivariate Classification Trees
- Title（参考訳）: 多変量分類木を用いた最適混合整数線形最適化
- Authors: Brandon Alston, Illya V. Hicks,
- Abstract要約: 最適二分分類木を設計するための2つのカットベース混合整数線形最適化(MILO)法を提案する。
我々のモデルは、最小限の実用不可能なサブシステム(MIS)をオンザフライで識別し、パッケージング制約の形をとる切断平面を導出する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Multivariate decision trees are powerful machine learning tools for classification and regression that attract many researchers and industry professionals. An optimal binary tree has two types of vertices, (i) branching vertices which have exactly two children and where datapoints are assessed on a set of discrete features and (ii) leaf vertices at which datapoints are given a prediction, and can be obtained by solving a biobjective optimization problem that seeks to (i) maximize the number of correctly classified datapoints and (ii) minimize the number of branching vertices. Branching vertices are linear combinations of training features and therefore can be thought of as hyperplanes. In this paper, we propose two cut-based mixed integer linear optimization (MILO) formulations for designing optimal binary classification trees (leaf vertices assign discrete classes). Our models leverage on-the-fly identification of minimal infeasible subsystems (MISs) from which we derive cutting planes that hold the form of packing constraints. We show theoretical improvements on the strongest flow-based MILO formulation currently in the literature and conduct experiments on publicly available datasets to show our models' ability to scale, strength against traditional branch and bound approaches, and robustness in out-of-sample test performance. Our code and data are available on GitHub.
- Abstract（参考訳）: 多変量決定木は、多くの研究者や業界の専門家を惹きつける、分類と回帰のための強力な機械学習ツールである。
最適な二分木は2種類の頂点を持つ。
一 正確に二人の子供がおり、個別の特徴の集合に基づいてデータポイントが評価されている分枝頂点
二 データポイントが予測される葉の頂点であって、目的とする生物客観的最適化問題を解くことにより得ることができること。
i) 正しく分類されたデータポイントの数を最大化し、
(ii)分岐頂点の数を最小化する。
分岐頂点は訓練特徴の線形結合であり、したがって超平面とみなすことができる。
本稿では、最適二分分類木を設計するための2つのカットベース混合整数線形最適化(MILO)法を提案する。
我々のモデルは、最小限の実用不可能なサブシステム(MIS)をオンザフライで識別し、パッケージング制約の形をとる切断平面を導出する。
本稿では,現在論文の中で最強のフローベースMILO定式化に関する理論的改善と,我々のモデルがスケールする能力,従来のブランチとバウンドアプローチに対する強み,サンプル外テスト性能の堅牢性を示すために利用可能なデータセットの実験を行う。
コードとデータはGitHubで入手可能です。
関連論文リスト
- Minimally Supervised Learning using Topological Projections in
Self-Organizing Maps [55.31182147885694]
自己組織化マップ(SOM)におけるトポロジカルプロジェクションに基づく半教師付き学習手法を提案する。
提案手法は,まずラベル付きデータ上でSOMを訓練し,最小限のラベル付きデータポイントをキーベストマッチングユニット(BMU)に割り当てる。
提案した最小教師付きモデルが従来の回帰手法を大幅に上回ることを示す。
論文 参考訳（メタデータ） (2024-01-12T22:51:48Z) - The Convex Landscape of Neural Networks: Characterizing Global Optima
and Stationary Points via Lasso Models [75.33431791218302]
ディープニューラルネットワーク(DNN)モデルは、プログラミング目的に使用される。
本稿では,凸型神経回復モデルについて検討する。
定常的非次元目的物はすべて,グローバルサブサンプリング型凸解法プログラムとして特徴付けられることを示す。
また, 静止非次元目的物はすべて, グローバルサブサンプリング型凸解法プログラムとして特徴付けられることを示す。
論文 参考訳（メタデータ） (2023-12-19T23:04:56Z) - Solving a Class of Cut-Generating Linear Programs via Machine Learning [0.0]
カット生成線形プログラム(CGLP)は分離オラクルとして重要な役割を担い、混合整数プログラムの可能な領域に対して有効な不等式を生成する。
分岐木と分岐木のノードでデュアルPを実行するのは、ノード候補の数と、ノードが有用な切断平面を許容する事前知識がないため、計算的に煩雑である。
本稿では,分岐木ノードで切断面を生成できるかどうかを判定する,マシンPクラスの最適値を近似する学習に基づく新しいフレームワークを提案する。
論文 参考訳（メタデータ） (2023-10-30T18:31:52Z) - An improved column-generation-based matheuristic for learning
classification trees [9.07661731728456]
決定木は機械学習(ML)における分類問題の解法として高度に解釈可能なモデルである
決定木を訓練するための標準的なMLアルゴリズムは高速だが、精度の点で最適木を生成する。
citefirat 2020column氏は、意思決定木を学習するためのカラムジェネレーションベースのアプローチを提案した。
論文 参考訳（メタデータ） (2023-08-22T14:43:36Z) - Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。
第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
論文 参考訳（メタデータ） (2023-02-02T08:33:36Z) - Margin Optimal Classification Trees [0.0]
最適分類木(OCT)問題に対する新しい混合整数定式化法を提案する。
我々のモデルは、Margin Optimal Classification Tree (MARGOT)と呼ばれ、バイナリ分類のためのSupport Vector Machinesの一般化機能を利用する。
提案手法の解釈可能性を高めるため,超平面の局所的疎結合を誘導する特徴選択制約を含む2種類のMARGOTを解析した。
論文 参考訳（メタデータ） (2022-10-19T14:08:56Z) - Mixed integer linear optimization formulations for learning optimal
binary classification trees [0.0]
最適二分分類木を設計するための4つの混合整数線形最適化(MILO)法を提案する。
モデルをスケールする能力を示すために、13の公開データセットで実験を行います。
論文 参考訳（メタデータ） (2022-06-10T03:10:14Z) - 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) - Auto-weighted Multi-view Feature Selection with Graph Optimization [90.26124046530319]
グラフ学習に基づく新しい教師なしマルチビュー特徴選択モデルを提案する。
1) 特徴選択過程において, 異なる視点で共有されたコンセンサス類似度グラフが学習される。
各種データセットを用いた実験により,提案手法が最先端手法よりも優れていることを示す。
論文 参考訳（メタデータ） (2021-04-11T03:25:25Z) - Optimal Decision Trees for Nonlinear Metrics [42.18286681448184]
本稿では,非線形メトリクスに対して最適な木を生成するための新しいアルゴリズムを提案する。
我々の知る限りでは、これは非線形メトリクスに対して証明可能な最適決定木を計算するための最初の方法である。
当社のアプローチは、線形メトリクスの最適化と比較した場合、トレードオフにつながります。
論文 参考訳（メタデータ） (2020-09-15T08:30:56Z) - Learning to Cluster Faces via Confidence and Connectivity Estimation [136.5291151775236]
重複する部分グラフを多数必要とせず,完全に学習可能なクラスタリングフレームワークを提案する。
提案手法はクラスタリングの精度を大幅に向上させ,その上で訓練した認識モデルの性能を向上させるが,既存の教師付き手法に比べて桁違いに効率的である。
論文 参考訳（メタデータ） (2020-04-01T13:39:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。