論文の概要: Single MCMC Chain Parallelisation on Decision Trees
- arxiv url: http://arxiv.org/abs/2207.12688v1
- Date: Tue, 26 Jul 2022 07:07:51 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-27 13:10:28.927973
- Title: Single MCMC Chain Parallelisation on Decision Trees
- Title(参考訳): 決定木上の単一MCMC鎖並列化
- Authors: Efthyvoulos Drousiotis, Paul G. Spirakis
- Abstract要約: 本稿では,平均的なラップトップやパソコン上でMCMC決定ツリーチェーンを並列化する手法を提案する。
実験の結果,シリアルと並列実装が統計的に同一である場合,実行時間を18倍に向上できることがわかった。
- 参考スコア(独自算出の注目度): 0.9137554315375919
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Decision trees are highly famous in machine learning and usually acquire
state-of-the-art performance. Despite that, well-known variants like CART, ID3,
random forest, and boosted trees miss a probabilistic version that encodes
prior assumptions about tree structures and shares statistical strength between
node parameters. Existing work on Bayesian decision trees depend on Markov
Chain Monte Carlo (MCMC), which can be computationally slow, especially on high
dimensional data and expensive proposals. In this study, we propose a method to
parallelise a single MCMC decision tree chain on an average laptop or personal
computer that enables us to reduce its run-time through multi-core processing
while the results are statistically identical to conventional sequential
implementation. We also calculate the theoretical and practical reduction in
run time, which can be obtained utilising our method on multi-processor
architectures. Experiments showed that we could achieve 18 times faster running
time provided that the serial and the parallel implementation are statistically
identical.
- Abstract(参考訳): 決定木は機械学習で非常に有名であり、通常最先端のパフォーマンスを取得する。
それにもかかわらず、cart、id3、random forest、boosted treeなどの有名な変種は、ツリー構造に関する以前の仮定をエンコードし、ノードパラメータ間で統計的強度を共有する確率的バージョンを欠いている。
既存のベイズ決定木の研究はマルコフ・チェイン・モンテカルロ (MCMC) に依存しており、特に高次元のデータと高価な提案を計算的に遅くすることができる。
本研究では,従来の逐次実装と統計的に同一でありながら,マルチコア処理による実行時間を短縮できる,平均的なラップトップやパーソナルコンピュータ上でMCMC決定ツリーチェーンを並列化する手法を提案する。
また,本手法をマルチプロセッサアーキテクチャに応用した,実行時間の理論的,実用的な削減を計算した。
実験の結果,シリアルと並列実装が統計的に同一である場合,実行時間を18倍に向上できることがわかった。
関連論文リスト
- Terminating Differentiable Tree Experts [77.2443883991608]
本稿では,変圧器と表現生成器の組み合わせを用いて木操作を学習するニューラルシンボリック微分木機械を提案する。
まず、専門家の混在を導入することで、各ステップで使用される一連の異なるトランスフォーマーレイヤを取り除きます。
また,モデルが自動生成するステップ数を選択するための新しい終端アルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-07-02T08:45:38Z) - TREE: Tree Regularization for Efficient Execution [4.205565040528205]
本稿では,決定木の訓練中に不均一な確率分布を報知することにより,経路長を削減する手法を提案する。
具体的には,CARTアルゴリズムの不純物を規則化し,低不純物だけでなく,分割基準の評価にも高い非対称分布を求める。
論文 参考訳(メタデータ) (2024-06-18T12:01:06Z) - Des-q: a quantum algorithm to provably speedup retraining of decision trees [2.7262923206583136]
Des-qは、回帰および二分分類タスクのための決定木を構築し、再訓練するための新しい量子アルゴリズムである。
我々は,複数のデータセット上での最先端の古典的手法に対して,Des-qのシミュレーションバージョンをベンチマークする。
提案アルゴリズムは,最新の決定木に類似した性能を示しながら,周期木再学習を著しく高速化する。
論文 参考訳(メタデータ) (2023-09-18T17:56:08Z) - Bayesian Decision Trees Inspired from Evolutionary Algorithms [64.80360020499555]
我々は、マルコフ連鎖モンテカルロ(MCMC)を本質的に並列なアルゴリズムであるシーケンシャルモンテカルロ(SMC)に置き換えることを提案する。
実験により、SMCと進化的アルゴリズム(EA)を組み合わせることで、MCMCの100倍のイテレーションでより正確な結果が得られることが示された。
論文 参考訳(メタデータ) (2023-05-30T06:17:35Z) - Parallel Tree Kernel Computation [0.0]
2つの有限木からなる木核の計算のための逐次アルゴリズムの並列実装を考案する。
その結果,提案した並列アルゴリズムは遅延の点で逐次アルゴリズムよりも優れていることがわかった。
論文 参考訳(メタデータ) (2023-05-12T18:16:45Z) - Parallel Approaches to Accelerate Bayesian Decision Trees [1.9728521995447947]
本稿では,MCMCにおける並列性を利用した2つの手法を提案する。
第一に、MCMCを別の数値ベイズ的アプローチで置き換える。
第2に、データのパーティショニングについて検討する。
論文 参考訳(メタデータ) (2023-01-22T09:56:26Z) - Efficient semidefinite-programming-based inference for binary and
multi-class MRFs [83.09715052229782]
分割関数やMAP推定をペアワイズMRFで効率的に計算する手法を提案する。
一般のバイナリMRFから完全多クラス設定への半定緩和を拡張し、解法を用いて再び効率的に解けるようなコンパクトな半定緩和を開発する。
論文 参考訳(メタデータ) (2020-12-04T15:36:29Z) - MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
動的プログラミングと探索に基づいて最適な分類木を学習するための新しいアルゴリズムを提案する。
当社のアプローチでは,最先端技術が必要とする時間のごく一部しか使用せず,数万のインスタンスでデータセットを処理することが可能です。
論文 参考訳(メタデータ) (2020-07-24T17:06:55Z) - On Effective Parallelization of Monte Carlo Tree Search [51.15940034629022]
モンテカルロ木探索(MCTS)は、探索木を構築するためにかなりの数のロールアウトを必要とするため、計算コストがかかる。
効果的な並列MCTSアルゴリズムを設計する方法は、体系的に研究されておらず、まだよく分かっていない。
我々は,より効率的な並列MCTSアルゴリズムの設計に,提案する必要条件をどのように適用できるかを実証する。
論文 参考訳(メタデータ) (2020-06-15T21:36:00Z) - Einsum Networks: Fast and Scalable Learning of Tractable Probabilistic
Circuits [99.59941892183454]
我々は,PC用の新しい実装設計であるEinsum Networks (EiNets)を提案する。
中心となるのは、E EiNets は単一のモノリシックな einsum-operation に多数の算術演算を組み合わせている。
本稿では,PCにおける予測最大化(EM)の実装を,自動微分を利用した簡易化が可能であることを示す。
論文 参考訳(メタデータ) (2020-04-13T23:09:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。