論文の概要: Spectral partitioning for $k$-block averaging kernels of finite Markov chains
- arxiv url: http://arxiv.org/abs/2608.21466v1
- Date: Fri, 21 Aug 2026 02:53:38 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-25 13:29:43.19186
- Title: Spectral partitioning for $k$-block averaging kernels of finite Markov chains
- Title（参考訳）: 有限マルコフ連鎖の$k$-ブロック平均化核に対するスペクトル分割
- Abstract要約: 我々は,有限でエルゴード的で可逆なマルコフ連鎖に対する平均化カーネルを定義する状態空間分割を選択するアルゴリズムを開発した。
制御スペクトルグラフ,平均場イジングモデル,ベイズ変分選択実験は収束率と統計的推定において顕著に改善された。
- 参考スコア（独自算出の注目度）: 2.9399121155604875
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We develop spectral algorithms for selecting state-space partitions that define averaging kernels for finite, ergodic and reversible Markov chains. For a partition $\mathcal O$, the Gibbs kernel $G_{\mathcal O}$ resamples within the current block from the stationary conditional distribution; when this update is tractable, composing or mixing it with a baseline kernel $P$ can accelerate convergence. We select $\mathcal O$ by rounding the bottom nonconstant eigenfunctions of $P^2$, or the algebraically smallest eigenfunctions of $P$ for additive mixtures, using weighted $k$-means. For $F(\mathcal O)=\|G_{\mathcal O}P-Π\|_{F,π}^2$, we derive exact trace and normalized-cut representations and show that $F$ equals the Pearson $χ^2$-mutual information between the initial block label and the state after one transition, giving this matrix objective a natural probabilistic interpretation. In the two-block case, a threshold sweep exactly solves the associated one-dimensional weighted two-means rounding problem. For general $k \geq 2$, weighted $k$-means rounds the bottom $(k-1)$-dimensional embedding, after which candidates are rescored by $F$; the rounding distortion is a distance between subspaces that yields spectral approximation bounds. We extend the framework to additive mixtures, finite-horizon objectives, and discounted infinite-horizon objectives. In contrast to classical normalized spectral clustering, which uses top nonconstant modes to find low-flow persistent clusters, our method uses bottom modes to favor large normalized cross-block flow and rapid loss of block-label information. Experiments on a controlled-spectrum graph, a mean-field Ising model, and Bayesian variable selection show notable per-iteration improvements in convergence and statistical estimation.
- Abstract（参考訳）: 我々は,有限,エルゴディック,可逆なマルコフ連鎖に対して平均化カーネルを定義する状態空間分割を選択するためのスペクトルアルゴリズムを開発した。
パーティション$\mathcal O$の場合、Gibsカーネル$G_{\mathcal O}$は、定常条件分布から現在のブロック内に再サンプリングされる。
重み付き$k$-平均を用いて、P^2$の底の非定数固有関数や加法混合に対する代数的に最小の$P$の固有関数を丸めることにより、$\mathcal O$を選択する。
F(\mathcal O)=\|G_{\mathcal O}P-\|_{F,π}^2$ に対して、正確なトレースと正規化されたカット表現を導出し、$F$ が最初のブロックラベルと1つの遷移後の状態の間の Pearson $ ^2$-mutual 情報と等しいことを示し、この行列の目的は自然な確率論的解釈を与える。
2ブロックの場合、しきい値スイープは、関連する1次元重み付き2平均ラウンドリング問題を正確に解決する。
一般の$k \geq 2$の場合、重み付き$k$-meansは下階の$(k-1)$-次元埋め込みを囲む。
フレームワークを加法混合、有限水平目的、割引された無限水平目的に拡張する。
低フローの持続的クラスタを見つけるためにトップ非コンスタントモードを使用する古典的正規化スペクトルクラスタリングとは対照的に,本手法はボトムモードを用いて大きな正規化クロスブロックフローとブロックラベル情報の高速な損失を優先する。
制御スペクトルグラフ,平均場イジングモデル,ベイズ変分選択実験は収束率と統計的推定において顕著に改善された。
関連論文リスト
- Learning manifold diffusion semigroups from graph transition matrices [18.784763748323513]
多様体熱半群 $Q_t = et$ がグラフ遷移行列 $P$ を反復することによって直接近似できることを示す。
シミュレーションデータ上で提案した推定器の性能を数値的に示す。
論文 参考訳（メタデータ） (2026-05-25T03:20:11Z) - Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
我々は、長さ$H$の軌跡を、大きさ$S$の有限状態空間上の未知のエルゴードマルコフ鎖の1つによって生成される、$T$ trajectories of length $H$の問題を研究する。
我々は、連鎖の遷移核間の重み付きKL分散によって支配されるクラスタリングエラー率に基づいて、インスタンス依存で高い確率の低い境界を導出する。
次に,新しい2段階クラスタリングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-06-02T05:10:40Z) - Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文 参考訳（メタデータ） (2024-04-29T15:04:07Z) - Debiased Distribution Compression [30.600795754425775]
本稿では, バイアス入力シーケンスによる圧縮に適した新しい圧縮手法を提案する。
バーンイン,近似マルコフ連鎖モンテカルロ,テンパリングによるバイアスを克服しつつ,簡潔かつ正確な後続サマリーを提供する。
論文 参考訳（メタデータ） (2024-04-18T16:11:16Z) - Semidefinite programming relaxations and debiasing for MAXCUT-based clustering [1.9761774213809036]
2つのガウス分布を$mathbbRp$で混合して引き出す小さなデータサンプルを$n$で分割する問題を考察する。
グラフ上の最大カットを求めるように定式化された整数二次プログラムの半定値プログラミング緩和を用いる。
論文 参考訳（メタデータ） (2024-01-16T03:14:24Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Near-optimal fitting of ellipsoids to random points [68.12685213894112]
楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。
我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。
我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
論文 参考訳（メタデータ） (2022-08-19T18:00:34Z) - Bi-stochastically normalized graph Laplacian: convergence to manifold Laplacian and robustness to outlier noise [10.418647759223965]
双確率正規化 (bi-stochastic normalization) はグラフベースのデータ解析においてグラフラプラシアンの代替正規化を提供する。
両階層正規化グラフ Laplacian から (重み付き) Laplacian への収束を速度で証明する。
多様体データが外乱ノイズによって破損した場合、理論的にはラプラシア点の整合性を証明する。
論文 参考訳（メタデータ） (2022-06-22T21:08:24Z) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。
3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。
提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文 参考訳（メタデータ） (2021-10-05T09:33:49Z) - Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
エントロピー正則化で最適な輸送を解くには、ベクトルに繰り返し適用される$ntimes n$ kernel matrixを計算する必要がある。
代わりに、$c(x,y)=-logdotpvarphi(x)varphi(y)$ ここで$varphi$は、地上空間から正のorthant $RRr_+$への写像であり、$rll n$である。
論文 参考訳（メタデータ） (2020-06-12T10:21:40Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。