論文の概要: Mixed integer linear optimization formulations for learning optimal
binary classification trees
- arxiv url: http://arxiv.org/abs/2206.04857v1
- Date: Fri, 10 Jun 2022 03:10:14 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-14 01:37:18.298196
- Title: Mixed integer linear optimization formulations for learning optimal
binary classification trees
- Title（参考訳）: 最適二分分類木学習のための混合整数線形最適化公式
- Authors: Brandon Alston, Hamidreza Validi, Illya V. Hicks
- Abstract要約: 最適二分分類木を設計するための4つの混合整数線形最適化(MILO)法を提案する。
モデルをスケールする能力を示すために、13の公開データセットで実験を行います。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Decision trees are powerful tools for classification and regression that
attract many researchers working in the burgeoning area of machine learning.
One advantage of decision trees over other methods is their interpretability,
which is often preferred over other higher accuracy methods that are relatively
uninterpretable. A binary classification 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 discrete prediction. An optimal binary classification
tree 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. In this paper, we propose four mixed integer
linear optimization (MILO) formulations for designing optimal binary
classification trees: two flow-based formulations and two-cut based
formulations. We provide theoretical comparisons between our proposed
formulations and the strongest flow-based MILO formulation of Aghaei et al.
(2021). We conduct experiments on 13 publicly available datasets to show the
models' ability to scale and the strength of a biobjective approach using
Pareto frontiers. Our code and data are available on GitHub.
- Abstract（参考訳）: 決定木は分類と回帰のための強力なツールであり、機械学習の急成長する分野で働く多くの研究者を惹きつける。
他の方法よりも決定木の方が優れているのは解釈可能性であり、比較的解釈不能な他の高精度な方法よりも好まれる。
二分分類木には2種類の頂点がある。
(i)ちょうど2人の子供がいて、データポイントが一組の離散的特徴に基づいて評価される分岐頂点
(ii)データポイントが個別に予測される葉の頂点。
最適な二分分類木は、目的とする生体的最適化問題を解くことで得られる。
i) 正しく分類されたデータポイントの数を最大化し、
(ii)分岐頂点の数を最小化する。
本稿では, 最適二分分類木を設計するための4つの混合整数線形最適化 (milo) 式を提案する。
本稿では,提案した定式化とAghaei et al. (2021) の最強フローベースMILO定式化とを理論的に比較する。
我々は,パレートフロンティアを用いて,モデルがスケールする能力と2目的アプローチの強みを示すために,13の公開データセットについて実験を行う。
コードとデータはGitHubで公開されている。
関連論文リスト
- Learning Deep Tree-based Retriever for Efficient Recommendation: Theory and Method [76.31185707649227]
効率的なレコメンデーションのために,Deep Tree-based Retriever (DTR)を提案する。
DTRは、トレーニングタスクを、同じレベルでツリーノード上のソフトマックスベースのマルチクラス分類としてフレーム化している。
非リーフノードのラベル付けによって引き起こされる準最適性を緩和するため、損失関数の補正法を提案する。
論文 参考訳（メタデータ） (2024-08-21T05:09:53Z) - Optimal Mixed Integer Linear Optimization Trained Multivariate Classification Trees [0.0]
最適二分分類木を設計するための2つのカットベース混合整数線形最適化(MILO)法を提案する。
我々のモデルは、最小限の実用不可能なサブシステム(MIS)をオンザフライで識別し、パッケージング制約の形をとる切断平面を導出する。
論文 参考訳（メタデータ） (2024-08-02T14:37:28Z) - Margin Optimal Classification Trees [0.0]
最適分類木(OCT)問題に対する新しい混合整数定式化法を提案する。
我々のモデルは、Margin Optimal Classification Tree (MARGOT)と呼ばれ、バイナリ分類のためのSupport Vector Machinesの一般化機能を利用する。
提案手法の解釈可能性を高めるため,超平面の局所的疎結合を誘導する特徴選択制約を含む2種類のMARGOTを解析した。
論文 参考訳（メタデータ） (2022-10-19T14:08:56Z) - 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) - Optimal Propagation for Graph Neural Networks [51.08426265813481]
最適グラフ構造を学習するための二段階最適化手法を提案する。
また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
論文 参考訳（メタデータ） (2022-05-06T03:37:00Z) - Riemannian classification of EEG signals with missing values [67.90148548467762]
本稿では脳波の分類に欠落したデータを扱うための2つの方法を提案する。
第1のアプローチでは、インプットされたデータと$k$-nearestの隣人アルゴリズムとの共分散を推定し、第2のアプローチでは、期待最大化アルゴリズム内で観測データの可能性を活用することにより、観測データに依存する。
その結果, 提案手法は観測データに基づく分類よりも優れており, 欠落したデータ比が増大しても高い精度を維持することができることがわかった。
論文 参考訳（メタデータ） (2021-10-19T14:24:50Z) - Auto-weighted Multi-view Feature Selection with Graph Optimization [90.26124046530319]
グラフ学習に基づく新しい教師なしマルチビュー特徴選択モデルを提案する。
1) 特徴選択過程において, 異なる視点で共有されたコンセンサス類似度グラフが学習される。
各種データセットを用いた実験により,提案手法が最先端手法よりも優れていることを示す。
論文 参考訳（メタデータ） (2021-04-11T03:25:25Z) - Strong Optimal Classification Trees [8.10995244893652]
最適二分分類木を学習するための直感的なフローベースMIO定式化を提案する。
我々の定式化は、解釈可能かつ公平な決定木の設計を可能にするために、サイド制約を満たすことができる。
提案手法は最先端MIO技術よりも29倍高速であることを示す。
論文 参考訳（メタデータ） (2021-03-29T21:40:58Z) - Optimal Decision Trees for Nonlinear Metrics [42.18286681448184]
本稿では,非線形メトリクスに対して最適な木を生成するための新しいアルゴリズムを提案する。
我々の知る限りでは、これは非線形メトリクスに対して証明可能な最適決定木を計算するための最初の方法である。
当社のアプローチは、線形メトリクスの最適化と比較した場合、トレードオフにつながります。
論文 参考訳（メタデータ） (2020-09-15T08:30:56Z) - MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
動的プログラミングと探索に基づいて最適な分類木を学習するための新しいアルゴリズムを提案する。
当社のアプローチでは,最先端技術が必要とする時間のごく一部しか使用せず,数万のインスタンスでデータセットを処理することが可能です。
論文 参考訳（メタデータ） (2020-07-24T17:06:55Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。
品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文 参考訳（メタデータ） (2020-02-26T16:19:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。