論文の概要: MABSplit: Faster Forest Training Using Multi-Armed Bandits
- arxiv url: http://arxiv.org/abs/2212.07473v1
- Date: Wed, 14 Dec 2022 19:43:43 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-16 17:54:57.154880
- Title: MABSplit: Faster Forest Training Using Multi-Armed Bandits
- Title(参考訳): MABSplit:マルチアーマッドバンドを用いた高速森林訓練
- Authors: Mo Tiwari, Ryan Kang, Je-Yong Lee, Sebastian Thrun, Chris Piech, Ilan
Shomorony, Martin Jinye Zhang
- Abstract要約: 本稿では,無作為林などの学習手法の学習を高速化するアルゴリズムを提案する。
アルゴリズムのコアとなるのは、MABSplitと呼ばれるノード分割サブルーチンで、スプリットポイントを効率的に見つけるために使われる。
提案アルゴリズムは,多武器のバンディット文学の手法を利用して,サンプルの割り当て方法の判断を行う。
- 参考スコア(独自算出の注目度): 14.650858573237977
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Random forests are some of the most widely used machine learning models
today, especially in domains that necessitate interpretability. We present an
algorithm that accelerates the training of random forests and other popular
tree-based learning methods. At the core of our algorithm is a novel
node-splitting subroutine, dubbed MABSplit, used to efficiently find split
points when constructing decision trees. Our algorithm borrows techniques from
the multi-armed bandit literature to judiciously determine how to allocate
samples and computational power across candidate split points. We provide
theoretical guarantees that MABSplit improves the sample complexity of each
node split from linear to logarithmic in the number of data points. In some
settings, MABSplit leads to 100x faster training (an 99% reduction in training
time) without any decrease in generalization performance. We demonstrate
similar speedups when MABSplit is used across a variety of forest-based
variants, such as Extremely Random Forests and Random Patches. We also show our
algorithm can be used in both classification and regression tasks. Finally, we
show that MABSplit outperforms existing methods in generalization performance
and feature importance calculations under a fixed computational budget. All of
our experimental results are reproducible via a one-line script at
https://github.com/ThrunGroup/FastForest.
- Abstract(参考訳): ランダムフォレストは現在最も広く使われている機械学習モデルであり、特に解釈可能性を必要とする領域で使われている。
本稿では,ランダムフォレストやその他の木本学習手法の学習を高速化するアルゴリズムを提案する。
我々のアルゴリズムの中核はMABSplitと呼ばれる新しいノード分割サブルーチンであり、決定木を構築する際に効率的に分割点を見つけるために使用される。
提案アルゴリズムは,多武装バンディット文学の手法を利用して,候補分割点間でサンプルと計算能力の割り当て方法を決定する。
我々は、MABSplitが各ノードのサンプリング複雑性を、データポイント数で線形から対数に分割することを理論的に保証する。
いくつかの設定では、mabsplitは一般化性能を低下させることなく、100倍のトレーニング(トレーニング時間の99%削減)につながる。
極端にランダムな森林やランダムなパッチなど、様々な森林ベースの変種でmabsplitを使用する場合も同様のスピードアップを示す。
また,アルゴリズムは分類タスクと回帰タスクの両方で使用できることを示す。
最後に,MABSplitは,計算予算の固定化と特徴量計算において,既存の手法よりも優れていることを示す。
実験結果はすべて、https://github.com/thrungroup/fastforestの1行スクリプトで再現可能です。
関連論文リスト
- Distributed Collapsed Gibbs Sampler for Dirichlet Process Mixture Models
in Federated Learning [0.22499166814992444]
本稿では,DPMM (DisCGS) のための分散マルコフ連鎖モンテカルロ (MCMC) 推論手法を提案する。
我々のアプローチでは、崩壊したGibbsサンプルラーを使用し、独立マシンと異種マシンの分散データを扱うように設計されています。
例えば、100Kのデータポイントのデータセットでは、中央集権的なアルゴリズムは100回のイテレーションを完了するのに約12時間かかります。
論文 参考訳(メタデータ) (2023-12-18T13:16:18Z) - An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration
of Multi-Armed Bandit [65.268245109828]
多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。
既存のR-CPE-MABの手法は、いわゆるトランスダクティブ線形帯域の特殊な場合と見なすことができる。
本稿では,差分探索アルゴリズム (CombGapE) を提案する。
論文 参考訳(メタデータ) (2023-06-15T15:37:31Z) - Parallel Tree Kernel Computation [0.0]
2つの有限木からなる木核の計算のための逐次アルゴリズムの並列実装を考案する。
その結果,提案した並列アルゴリズムは遅延の点で逐次アルゴリズムよりも優れていることがわかった。
論文 参考訳(メタデータ) (2023-05-12T18:16:45Z) - FastHebb: Scaling Hebbian Training of Deep Neural Networks to ImageNet
Level [7.410940271545853]
我々は、Hebbian学習のための効率的でスケーラブルなソリューションであるFastHebbを紹介する。
FastHebbはトレーニングのスピードで、これまでのソリューションを最大50倍のパフォーマンスで上回っている。
私たちは初めて、HebbianアルゴリズムをImageNetスケールに持ち込むことができます。
論文 参考訳(メタデータ) (2022-07-07T09:04:55Z) - Reinforcement Learning for Branch-and-Bound Optimisation using
Retrospective Trajectories [72.15369769265398]
機械学習は分岐のための有望なパラダイムとして登場した。
分岐のための単純かつ効果的なRLアプローチであるレトロ分岐を提案する。
我々は現在最先端のRL分岐アルゴリズムを3~5倍に上回り、500の制約と1000の変数を持つMILP上での最高のILメソッドの性能の20%以内である。
論文 参考訳(メタデータ) (2022-05-28T06:08:07Z) - Parallel Sampling for Efficient High-dimensional Bayesian Network
Structure Learning [6.85316573653194]
本稿では,CPS(Candidate Parent Sets)上で並列サンプリングを行う近似アルゴリズムについて述べる。
修正アルゴリズムはParallel Sampling MINOBS (PS-MINOBS) と呼ばれ、各変数のCPSをサンプリングすることでグラフを構成する。
論文 参考訳(メタデータ) (2022-02-19T22:35:59Z) - WildWood: a new Random Forest algorithm [0.0]
WildWoodはランダムフォレスト(RF)タイプの教師あり学習のための新しいアンサンブルアルゴリズムである。
WWは、アウト・オブ・バグのスコアを計算するために、ブートストラップのアウト・オブ・バグのサンプルを使用する。
WWは、他の確立されたアンサンブル法と比較して高速で競争力がある。
論文 参考訳(メタデータ) (2021-09-16T14:36:56Z) - COPS: Controlled Pruning Before Training Starts [68.8204255655161]
最先端のディープニューラルネットワーク(DNN)プルーニング技術は、トレーニング開始前にワンショットで適用され、プルーニングスコアと呼ばれる単一の基準の助けを借りてスパースアーキテクチャを評価する。
この作業では、単一プルーニング基準に集中するのではなく、任意のGASを組み合わせてより強力なプルーニング戦略を構築するためのフレームワークを提供します。
論文 参考訳(メタデータ) (2021-07-27T08:48:01Z) - Fast and Complete: Enabling Complete Neural Network Verification with
Rapid and Massively Parallel Incomplete Verifiers [112.23981192818721]
BaB プロセス中に線形計画法 (LP) を置き換えるために, 逆モード線形緩和に基づく解析法 (LiRPA) を提案する。
LPとは異なり、LiRPAを適用すると、より弱い境界が得られ、分割時にサブドメインのコンフリクトをチェックすることもできない。
既存のLPベースのアプローチと比較して、桁違いのスピードアップを示す。
論文 参考訳(メタデータ) (2020-11-27T16:42:12Z) - Resource Allocation in Multi-armed Bandit Exploration: Overcoming
Sublinear Scaling with Adaptive Parallelism [107.48538091418412]
腕の引っ張りに様々な量の資源を割り当てることができる分割可能な資源にアクセス可能な場合,マルチアームの帯状地における探索について検討する。
特に、分散コンピューティングリソースの割り当てに重点を置いており、プル毎により多くのリソースを割り当てることで、結果をより早く得ることができます。
論文 参考訳(メタデータ) (2020-10-31T18:19:29Z) - Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。
我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
論文 参考訳(メタデータ) (2020-08-29T14:58:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。