論文の概要: Learning Mixtures of Markov Chains with Quality Guarantees
- arxiv url: http://arxiv.org/abs/2302.04680v1
- Date: Thu, 9 Feb 2023 14:55:17 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-10 15:36:01.778475
- Title: Learning Mixtures of Markov Chains with Quality Guarantees
- Title（参考訳）: マルコフ連鎖と品質保証の混合学習
- Authors: Fabian Spaeh, Charalampos E. Tsourakakis
- Abstract要約: 現代のアプリケーションの多くは、多くのユーザ・トレイルを生成しています。
この問題を数学的にモデル化する1つのアプローチはマルコフ連鎖の混合である。
最近、Gupta, Kumar and Vassilvitski [GKV16] は、n状態のL鎖の混合物を完全に回収できるアルゴリズムを導入した。
- 参考スコア（独自算出の注目度）: 8.528384027684192
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A large number of modern applications ranging from listening songs online and
browsing the Web to using a navigation app on a smartphone generate a plethora
of user trails. Clustering such trails into groups with a common sequence
pattern can reveal significant structure in human behavior that can lead to
improving user experience through better recommendations, and even prevent
suicides [LMCR14]. One approach to modeling this problem mathematically is as a
mixture of Markov chains. Recently, Gupta, Kumar and Vassilvitski [GKV16]
introduced an algorithm (GKV-SVD) based on the singular value decomposition
(SVD) that under certain conditions can perfectly recover a mixture of L chains
on n states, given only the distribution of trails of length 3 (3-trail).
In this work we contribute to the problem of unmixing Markov chains by
highlighting and addressing two important constraints of the GKV-SVD algorithm
[GKV16]: some chains in the mixture may not even be weakly connected, and
secondly in practice one does not know beforehand the true number of chains. We
resolve these issues in the Gupta et al. paper [GKV16]. Specifically, we
propose an algebraic criterion that enables us to choose a value of L
efficiently that avoids overfitting. Furthermore, we design a reconstruction
algorithm that outputs the true mixture in the presence of disconnected chains
and is robust to noise. We complement our theoretical results with experiments
on both synthetic and real data, where we observe that our method outperforms
the GKV-SVD algorithm. Finally, we empirically observe that combining an
EM-algorithm with our method performs best in practice, both in terms of
reconstruction error with respect to the distribution of 3-trails and the
mixture of Markov Chains.
- Abstract（参考訳）: オンラインで音楽を聴いたり、ウェブを閲覧したり、スマートフォンでナビゲーションアプリを使うなど、多くのモダンなアプリケーションが、多くのユーザー・トレイルを生み出している。
このようなパスを共通のシーケンスパターンでグループにクラスタリングすることで、より優れたレコメンデーションによるユーザエクスペリエンスの改善、さらには自殺の防止 [lmcr14] につながる人間の行動の重要な構造を明らかにすることができる。
この問題を数学的にモデル化する一つのアプローチはマルコフ連鎖の混合である。
近年, Gupta, Kumar, Vassilvitski [GKV16] は, 特異値分解(SVD)に基づくアルゴリズム(GKV-SVD)を導入した。
本研究は, GKV-SVDアルゴリズムの2つの重要な制約を強調し, 対処することにより, マルコフ連鎖を解き放つ問題に寄与する。
我々はこれらの問題をGupta et al. paper[GKV16]で解決する。
具体的には、過剰適合を避けるためにLの値を効率的に選択できる代数的基準を提案する。
さらに,分離鎖の存在下で真の混合を出力し,雑音に対して頑健な再構成アルゴリズムを設計する。
提案手法がGKV-SVDアルゴリズムより優れていることを示すため,合成データと実データの両方で理論的結果を補完する。
最後に,3トラルの分布とマルコフ連鎖の混合に関する再構成誤差の両面において,EMアルゴリズムと我々の手法を併用した手法が有効であることを示す。
関連論文リスト
- Fast Semisupervised Unmixing Using Nonconvex Optimization [80.11512905623417]
半/ライブラリベースのアンミックスのための新しい凸凸モデルを提案する。
スパース・アンミキシングの代替手法の有効性を実証する。
論文 参考訳（メタデータ） (2024-01-23T10:07:41Z) - Chain of Log-Concave Markov Chains [2.9465623430708905]
非正規化密度からのサンプリングのための理論的枠組みを導入する。
対数凹凸条件密度のサンプリング列に密度からサンプリングを分解できることを証明した。
我々は,分布のモード間で「絡み合う」アルゴリズムの顕著な能力について報告する。
論文 参考訳（メタデータ） (2023-05-31T01:00:35Z) - Linear Convergence of Reshuffling Kaczmarz Methods With Sparse
Constraints [7.936519714074615]
カッツマルツ行列(英語版)(KZ)とその変種は、部分線型方程式系を解く際の単純さと効率性のために広く研究されている。
KHT に対する最初の理論的収束保証は、空間的制約のある系の解に線形に収束することを示すことである。
論文 参考訳（メタデータ） (2023-04-20T07:14:24Z) - Stochastic Gradient Descent under Markovian Sampling Schemes [3.04585143845864]
マルコフ型サンプリングスキームにのみアクセス可能なバニラ勾配勾配の変動について検討する。
我々は、基礎となるマルコフ連鎖で可能な最小限の制限的な仮定の下で収束率を得ることに焦点をあてる。
論文 参考訳（メタデータ） (2023-02-28T09:18:00Z) - Orthogonal SVD Covariance Conditioning and Latent Disentanglement [65.67315418971688]
SVDメタ層をニューラルネットワークに挿入すると、共分散が不調和になる。
我々は最寄り直交勾配(NOG)と最適学習率(OLR)を提案する。
視覚認識実験は,共分散条件と一般化を同時に改善できることを実証した。
論文 参考訳（メタデータ） (2022-12-11T20:31:31Z) - Rethinking skip connection model as a learnable Markov chain [12.135167279383815]
我々は、学習可能なマルコフ連鎖として定式化できるスキップ接続でモデルの振舞いを深く掘り下げる。
効率的なマルコフ連鎖は、入力データを常により良い方法でターゲットドメインにマップするので好まれる。
残差のようなモデルを学習可能なマルコフ連鎖にするために、簡単なペナル接続のルーチンを提案する。
論文 参考訳（メタデータ） (2022-09-30T07:31:49Z) - Plug-And-Play Learned Gaussian-mixture Approximate Message Passing [71.74028918819046]
そこで本研究では,従来のi.i.d.ソースに適した圧縮圧縮センシング(CS)リカバリアルゴリズムを提案する。
我々のアルゴリズムは、Borgerdingの学習AMP(LAMP)に基づいて構築されるが、アルゴリズムに普遍的な復調関数を採用することにより、それを大幅に改善する。
数値評価により,L-GM-AMPアルゴリズムは事前の知識を必要とせず,最先端の性能を実現する。
論文 参考訳（メタデータ） (2020-11-18T16:40:45Z) - Learning Mixtures of Low-Rank Models [89.39877968115833]
低ランクモデルの計算混合を学習する問題について検討する。
ほぼ最適サンプルを用いて未知の行列を復元することが保証されるアルゴリズムを開発する。
さらに,提案アルゴリズムはランダムノイズに対して確実に安定である。
論文 参考訳（メタデータ） (2020-09-23T17:53:48Z) - Least Squares Regression with Markovian Data: Fundamental Limits and
Algorithms [69.45237691598774]
マルコフ連鎖からデータポイントが依存しサンプリングされる最小二乗線形回帰問題について検討する。
この問題を$tau_mathsfmix$という観点から、鋭い情報理論のミニマックス下限を確立する。
本稿では,経験的リプレイに基づくアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-16T04:26:50Z) - Learning to Hash with Graph Neural Networks for Recommender Systems [103.82479899868191]
グラフ表現学習は、大規模に高品質な候補探索をサポートすることに多くの注目を集めている。
ユーザ・イテム相互作用ネットワークにおけるオブジェクトの埋め込みベクトルの学習の有効性にもかかわらず、連続的な埋め込み空間におけるユーザの好みを推測する計算コストは膨大である。
連続的かつ離散的なコードとを協調的に学習するための,単純かつ効果的な離散表現学習フレームワークを提案する。
論文 参考訳（メタデータ） (2020-03-04T06:59:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。