論文の概要: Many processors, little time: MCMC for partitions via optimal transport
couplings
- arxiv url: http://arxiv.org/abs/2202.11258v1
- Date: Wed, 23 Feb 2022 01:20:13 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-25 04:18:09.502482
- Title: Many processors, little time: MCMC for partitions via optimal transport
couplings
- Title(参考訳): 多くのプロセッサ、わずかな時間:最適輸送結合による分割のためのMCMC
- Authors: Tin D. Nguyen and Brian L. Trippe and Tamara Broderick
- Abstract要約: 既存の結合概念の離散クラスタリング変数への直接的な応用は、すぐには満たされないことを示す。
この失敗は「ラベルスイッチング問題(label-switching problem)」から生じ、意味論的に等価なクラスタレバリングは結合鎖の高速な一致を妨げる。
分割空間上の計量を用いて、最適な輸送結合を用いて実用的なアルゴリズムを定式化する。
- 参考スコア(独自算出の注目度): 17.248439315751227
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Markov chain Monte Carlo (MCMC) methods are often used in clustering since
they guarantee asymptotically exact expectations in the infinite-time limit. In
finite time, though, slow mixing often leads to poor performance. Modern
computing environments offer massive parallelism, but naive implementations of
parallel MCMC can exhibit substantial bias. In MCMC samplers of continuous
random variables, Markov chain couplings can overcome bias. But these
approaches depend crucially on paired chains meetings after a small number of
transitions. We show that straightforward applications of existing coupling
ideas to discrete clustering variables fail to meet quickly. This failure
arises from the "label-switching problem": semantically equivalent cluster
relabelings impede fast meeting of coupled chains. We instead consider chains
as exploring the space of partitions rather than partitions' (arbitrary)
labelings. Using a metric on the partition space, we formulate a practical
algorithm using optimal transport couplings. Our theory confirms our method is
accurate and efficient. In experiments ranging from clustering of genes or
seeds to graph colorings, we show the benefits of our coupling in the highly
parallel, time-limited regime.
- Abstract(参考訳): マルコフ連鎖モンテカルロ法(MCMC)は、無限時間極限における漸近的に正確な期待を保証するため、クラスタリングにおいてしばしば用いられる。
しかし、有限時間では、遅い混合はしばしば性能を低下させる。
現代の計算環境は膨大な並列性を提供するが、並列MCMCの実装には重大なバイアスが生じる。
連続確率変数のMCMCサンプリングでは、マルコフ連鎖結合はバイアスを克服することができる。
しかしこれらのアプローチは、少数の移行の後、ペアのチェーンミーティングに大きく依存します。
分散クラスタリング変数に対する既存の結合アイデアの直接的な応用は、すぐには満たせないことを示す。
この失敗は「ラベルスイッチング問題(label-switching problem)」から生じ、意味論的に等価なクラスタレバリングは結合鎖の高速な一致を妨げる。
チェーンは、パーティションの(任意な)ラベル付けではなく、パーティションの空間を探索するものだと考えています。
分割空間上の計量を用いて最適な輸送結合を用いた実用的なアルゴリズムを定式化する。
我々の理論は、この方法が正確で効率的であることを確認する。
遺伝子や種子のクラスタリングからグラフの着色まで幅広い実験において,高度に並列な時間制限された構造における結合の利点を示す。
関連論文リスト
- Distributed MCMC inference for Bayesian Non-Parametric Latent Block
Model [0.24578723416255754]
ベイジアン非パラメトリック潜在ブロックモデル(DisNPLBM)のための分散マルコフ連鎖モンテカルロ(MCMC)推論手法を提案する。
我々の非パラメトリックコクラスタリングアルゴリズムは、潜在多変量ガウスブロック分布を用いて観測と特徴を分割する。
DisNPLBMは、実験結果を通じてクラスタラベリングの精度と実行時間に与える影響を実証する。
論文 参考訳(メタデータ) (2024-02-01T22:43:55Z) - SpreadNUTS -- Moderate Dynamic Extension of Paths for No-U-Turn Sampling
& Partitioning Visited Regions [0.0]
本稿では,no-U-turn sampler (NUTS) として知られる特定のハミルトンモンテカルロ (HMC) アルゴリズムの変更を紹介する。
NUTS は NUTS よりも早くサンプル空間を探索することを目的としており、真分布への収束が NUTS より高速なサンプリング器を提供する。
論文 参考訳(メタデータ) (2023-07-09T05:00:25Z) - Improved Bound for Mixing Time of Parallel Tempering [4.68299658663016]
パラレルテンパリングのための新しい下限を、$log L$を除く全てのパラメータにマルチモーダル依存を持つスペクトルギャップ上で提示する。
これにより、モードの数に指数関数的に依存する最良の既存の境界が改善される。
スペクトルギャップ上の仮定上界は$log L$に指数関数依存しており、ある意味では我々の境界は密であることを示す。
論文 参考訳(メタデータ) (2023-04-03T19:03:22Z) - Beyond Exponentially Fast Mixing in Average-Reward Reinforcement
Learning via Multi-Level Monte Carlo Actor-Critic [61.968469104271676]
本稿では,アクター・アクターとアクター・アクター・アクター・アルゴリズムに埋め込まれた平均報酬に対して,マルチレベルモンテカルロ推定器を用いて混合時間に適応したRL手法を提案する。
不安定な報酬を伴うRL問題において,安定性に要求される技術的条件の緩和効果が,実用上優れた性能に変換されることを実験的に示す。
論文 参考訳(メタデータ) (2023-01-28T04:12:56Z) - Parallel Approaches to Accelerate Bayesian Decision Trees [1.9728521995447947]
本稿では,MCMCにおける並列性を利用した2つの手法を提案する。
第一に、MCMCを別の数値ベイズ的アプローチで置き換える。
第2に、データのパーティショニングについて検討する。
論文 参考訳(メタデータ) (2023-01-22T09:56:26Z) - Optimization on manifolds: A symplectic approach [127.54402681305629]
本稿では、最適化問題を解くための一般的な枠組みとして、ディラックの制約付きハミルトン系理論の散逸拡張を提案する。
我々の(加速された)アルゴリズムのクラスは単純で効率的なだけでなく、幅広い文脈にも適用できる。
論文 参考訳(メタデータ) (2021-07-23T13:43:34Z) - What Are Bayesian Neural Network Posteriors Really Like? [63.950151520585024]
ハミルトニアンモンテカルロは、標準およびディープアンサンブルよりも大きな性能向上を達成できることを示す。
また,深部分布は標準SGLDとHMCに類似しており,標準変動推論に近いことが示された。
論文 参考訳(メタデータ) (2021-04-29T15:38:46Z) - Contrastive learning of strong-mixing continuous-time stochastic
processes [53.82893653745542]
コントラスト学習(Contrastive Learning)は、ラベルのないデータから構築された分類タスクを解決するためにモデルを訓練する自己指導型の手法のファミリーである。
拡散の場合,小~中距離間隔の遷移カーネルを適切に構築したコントラスト学習タスクを用いて推定できることが示される。
論文 参考訳(メタデータ) (2021-03-03T23:06:47Z) - The Connection between Discrete- and Continuous-Time Descriptions of
Gaussian Continuous Processes [60.35125735474386]
我々は、一貫した推定子をもたらす離散化が粗粒化下での不変性を持つことを示す。
この結果は、導関数再構成のための微分スキームと局所時間推論アプローチの組み合わせが、2次または高次微分方程式の時系列解析に役立たない理由を説明する。
論文 参考訳(メタデータ) (2021-01-16T17:11:02Z) - Kernel learning approaches for summarising and combining posterior
similarity matrices [68.8204255655161]
我々は,ベイズクラスタリングモデルに対するMCMCアルゴリズムの出力を要約するための新しいアプローチを提案するために,後部類似性行列(PSM)の概念を構築した。
我々の研究の重要な貢献は、PSMが正の半定値であり、したがって確率的に動機付けられたカーネル行列を定義するのに使用できることである。
論文 参考訳(メタデータ) (2020-09-27T14:16:14Z) - AMAGOLD: Amortized Metropolis Adjustment for Efficient Stochastic
Gradient MCMC [37.768023232677244]
ハミルトニアン・モンテカルロ(英語版)(SGHMC)は、連続分布からサンプリングする効率的な方法である。
本稿では、しばしばメトロポリス・ハスティング(M-H)補正を用いてバイアスを除去する2次SG-MCMCアルゴリズム--AMAGOLDを提案する。
我々は, AMAGOLD が減少するステップサイズではなく, 目標分布に収束し, 収束速度が全バッチベースラインよりも遅くなることを証明した。
論文 参考訳(メタデータ) (2020-02-29T06:57:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。