論文の概要: Learning Mixtures of Permutations: Groups of Pairwise Comparisons and
Combinatorial Method of Moments
- arxiv url: http://arxiv.org/abs/2009.06784v2
- Date: Fri, 4 Mar 2022 18:56:19 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-18 12:17:29.777949
- Title: Learning Mixtures of Permutations: Groups of Pairwise Comparisons and
Combinatorial Method of Moments
- Title（参考訳）: 置換の混合を学習する:ペアワイズ比較群とモーメントの組合せ法
- Authors: Cheng Mao and Yihong Wu
- Abstract要約: Mallows混合モデルについて検討した。
高次元設定では、$n$要素上の置換のMallows混合を学習する最適時間アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 8.691957530860675
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In applications such as rank aggregation, mixture models for permutations are
frequently used when the population exhibits heterogeneity. In this work, we
study the widely used Mallows mixture model. In the high-dimensional setting,
we propose a polynomial-time algorithm that learns a Mallows mixture of
permutations on $n$ elements with the optimal sample complexity that is
proportional to $\log n$, improving upon previous results that scale
polynomially with $n$. In the high-noise regime, we characterize the optimal
dependency of the sample complexity on the noise parameter. Both objectives are
accomplished by first studying demixing permutations under a noiseless query
model using groups of pairwise comparisons, which can be viewed as moments of
the mixing distribution, and then extending these results to the noisy Mallows
model by simulating the noiseless oracle.
- Abstract（参考訳）: ランクアグリゲーションのような応用では、置換のための混合モデルは、集団が異質性を示すときに頻繁に用いられる。
本研究では,広く用いられているマロ混合モデルについて検討する。
高次元設定では、$n$要素上のマロース混合と$\log n$に比例する最適なサンプル複雑性を学習し、$n$で多項式的にスケールする以前の結果を改善する多項式時間アルゴリズムを提案する。
高雑音環境下では,雑音パラメータに対するサンプル複雑性の最適依存性を特徴付ける。
両方の目的は、まず、ペアワイズ比較の群を用いてノイズレスクエリモデルの下で置換をデミックスし、混合分布のモーメントとみなし、ノイズレスオラクルをシミュレートしてノイズの多いマロズモデルに拡張することで達成される。
関連論文リスト
- Mixup Augmentation with Multiple Interpolations [26.46413903248954]
サンプルペアから複数の勾配を生成するマルチミックス(multi-mix)という単純な拡張を提案する。
生成されたサンプルの順序を順序付けすることで、マルチミックスは、標準的なミックスアップよりもトレーニングプロセスのガイドに役立てることができる。
論文 参考訳（メタデータ） (2024-06-03T15:16:09Z) - Universal Lower Bounds and Optimal Rates: Achieving Minimax Clustering Error in Sub-Exponential Mixture Models [8.097200145973389]
まず、混合モデルのクラスタリングにおける誤差率の普遍的な下限を確立する。
次に、この下界をサブ指数尾を持つ混合モデルで再現的アルゴリズムが達成できることを実証する。
ポアソンまたは負二項混合によりモデル化されたデータセットについて,指数族に属する混合モデルについて検討した。
このような混合では、ブロッグマンの発散を利用したロイドのアルゴリズムの変種であるブロッグマンのハードクラスタリングが最適であることを示す。
論文 参考訳（メタデータ） (2024-02-23T16:51:17Z) - A Generalized Multiscale Bundle-Based Hyperspectral Sparse Unmixing
Algorithm [8.616208042031877]
ハイパースペクトルスパースアンミックスでは、空間領域における終端員の変動に対処するためにスペクトル束を用いることに成功した。
我々は,群間隔誘導混合ノルムを組み込むことにより,非混合問題を解くために,マルチスケール空間正規化手法を一般化する。
論文 参考訳（メタデータ） (2024-01-24T00:37:14Z) - Fast Semisupervised Unmixing Using Nonconvex Optimization [80.11512905623417]
半/ライブラリベースのアンミックスのための新しい凸凸モデルを提案する。
スパース・アンミキシングの代替手法の有効性を実証する。
論文 参考訳（メタデータ） (2024-01-23T10:07:41Z) - Improving Gradient-guided Nested Sampling for Posterior Inference [47.08481529384556]
本稿では,パフォーマンス,汎用的勾配誘導型ネストサンプリングアルゴリズム,$tt GGNS$を提案する。
後部分布から大量の高品質なサンプルを得るために,ネストサンプリングと生成フローネットワークを組み合わせる可能性を示す。
論文 参考訳（メタデータ） (2023-12-06T21:09:18Z) - Fitting large mixture models using stochastic component selection [0.0]
本稿では,少数のコンポーネントのみを評価するために,計算とメトロポリス・ハスティングスアルゴリズムの期待値の組み合わせを提案する。
コンポーネント割り当てのマルコフ連鎖は、アルゴリズムのイテレーション間で順次生成される。
提案手法の一般性を重視し,浅い混合モデルと深い混合モデルの両方を訓練する能力を備える。
論文 参考訳（メタデータ） (2021-10-10T12:39:53Z) - Maximum Entropy Reinforcement Learning with Mixture Policies [54.291331971813364]
MaxEntアルゴリズムを用いて混合エントロピーのトラクタブル近似を構築する。
我々は、それが限界エントロピーの合計と密接に関連していることを示しています。
我々は, 混合ポリシーケースに対するsoft actor-critic (sac) のアルゴリズム的変種を導出し, 一連の連続制御タスクで評価する。
論文 参考訳（メタデータ） (2021-03-18T11:23:39Z) - Estimating the Number of Components in Finite Mixture Models via the
Group-Sort-Fuse Procedure [0.974672460306765]
GSF(Group-Sort-Fuse)は、有限混合モデルにおける秩序と混合度を同時推定するための新しいペナル化可能性手法である。
GSFは, パラメータ推定における真の混合次数と$n-1/2$収束率を多対数因子まで推定する上で一貫したものであることを示す。
論文 参考訳（メタデータ） (2020-05-24T02:38:12Z) - Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
乗算重み更新法に基づいて,Klivans と Meka のアルゴリズムを適用した。
アルゴリズムは、文献の他のものと質的に類似したサンプル複雑性境界を楽しみます。
ランタイムが低い$O(mp2)$で、$m$サンプルと$p$ノードの場合には、簡単にオンライン形式で実装できる。
論文 参考訳（メタデータ） (2020-02-20T10:50:58Z) - Algebraic and Analytic Approaches for Parameter Learning in Mixture
Models [66.96778152993858]
1次元の混合モデルにおけるパラメータ学習のための2つの異なるアプローチを提案する。
これらの分布のいくつかについては、パラメータ推定の最初の保証を示す。
論文 参考訳（メタデータ） (2020-01-19T05:10:56Z) - Clustering Binary Data by Application of Combinatorial Optimization
Heuristics [52.77024349608834]
本稿では,2値データのクラスタリング手法について検討し,まず,クラスタのコンパクトさを計測するアグリゲーション基準を定義した。
近隣地域と人口動態最適化メタヒューリスティックスを用いた5つの新しいオリジナル手法が導入された。
準モンテカルロ実験によって生成された16のデータテーブルから、L1の相似性と階層的クラスタリング、k-means(メドイドやPAM)の1つのアグリゲーションの比較を行う。
論文 参考訳（メタデータ） (2020-01-06T23:33:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。