論文の概要: The Phase Transition Phenomenon of Shuffled Regression
- arxiv url: http://arxiv.org/abs/2310.20438v1
- Date: Tue, 31 Oct 2023 13:21:14 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-01 15:09:19.023392
- Title: The Phase Transition Phenomenon of Shuffled Regression
- Title（参考訳）: シャッフル回帰の相転移現象
- Authors: Hang Zhang and Ping Li
- Abstract要約: 本研究では, シャッフル(置換)回帰問題に固有の相転移現象について検討する。
本研究では,メッセージパッシング(MP)技術を活用し,位相遷移点の位置を正確に同定することを目的とする。
- 参考スコア（独自算出の注目度）: 17.99906229036223
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the phase transition phenomenon inherent in the shuffled (permuted)
regression problem, which has found numerous applications in databases,
privacy, data analysis, etc. In this study, we aim to precisely identify the
locations of the phase transition points by leveraging techniques from message
passing (MP). In our analysis, we first transform the permutation recovery
problem into a probabilistic graphical model. We then leverage the analytical
tools rooted in the message passing (MP) algorithm and derive an equation to
track the convergence of the MP algorithm. By linking this equation to the
branching random walk process, we are able to characterize the impact of the
signal-to-noise-ratio ($\snr$) on the permutation recovery. Depending on
whether the signal is given or not, we separately investigate the oracle case
and the non-oracle case. The bottleneck in identifying the phase transition
regimes lies in deriving closed-form formulas for the corresponding critical
points, but only in rare scenarios can one obtain such precise expressions. To
tackle this technical challenge, this study proposes the Gaussian approximation
method, which allows us to obtain the closed-form formulas in almost all
scenarios. In the oracle case, our method can fairly accurately predict the
phase transition $\snr$. In the non-oracle case, our algorithm can predict the
maximum allowed number of permuted rows and uncover its dependency on the
sample number.
- Abstract（参考訳）: 我々は,データベースやプライバシ,データ解析などにおいて多くの応用が見られたシャッフル(置換)回帰問題に内在する相転移現象について検討する。
本研究では,メッセージパッシング(MP)技術を活用し,位相遷移点の位置を正確に同定することを目的とする。
本分析では,まず置換回復問題を確率的グラフィカルモデルに変換する。
次に、メッセージパッシング(MP)アルゴリズムに根ざした解析ツールを活用し、MPアルゴリズムの収束を追跡する方程式を導出する。
この方程式を分岐ランダムウォーク過程にリンクすることにより、置換回復における信号対雑音比($\snr$)の影響を特徴づけることができる。
信号が与えられるか否かによっては、オラクルケースと非オラクルケースを別々に調査する。
相転移状態を特定する際のボトルネックは、対応する臨界点の閉形式公式を導出することにあるが、稀な場合のみそのような正確な式を得ることができる。
この技術的課題に対処するために,ほぼすべてのシナリオにおいて閉形式式を得ることができるガウス近似法を提案する。
oracleの場合、このメソッドは$\snr$というフェーズ遷移をかなり正確に予測できる。
非オラクルの場合、アルゴリズムは置換列の最大許容個数を予測し、サンプル数への依存性を明らかにする。
関連論文リスト
- Harmonic Path Integral Diffusion [0.4527270266697462]
本稿では,連続多変量確率分布から抽出する新しい手法を提案する。
本手法では,状態空間の起点を中心とするデルタ関数を$t=0$とし,ターゲット分布に$t=1$で変換する。
これらのアルゴリズムは他のサンプリング手法、特にシミュレートおよびパス積分サンプリングと対比し、解析制御、精度、計算効率の点でそれらの利点を強調した。
論文 参考訳（メタデータ） (2024-09-23T16:20:21Z) - A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
不均一な問題に対する近似メッセージパッシングアルゴリズム(AMP)を導出する。
特に,情報理論の閾値よりも大きい信号と雑音の比を必要とする既知のアルゴリズムが,ランダムよりも優れた処理を行うための統計的・計算的ギャップの存在を同定する。
論文 参考訳（メタデータ） (2023-02-13T19:57:17Z) - Conditioning Normalizing Flows for Rare Event Sampling [61.005334495264194]
本稿では,ニューラルネットワーク生成構成に基づく遷移経路サンプリング手法を提案する。
本手法は遷移領域の熱力学と運動学の両方の解法を可能にすることを示す。
論文 参考訳（メタデータ） (2022-07-29T07:56:10Z) - An application of the splitting-up method for the computation of a
neural network representation for the solution for the filtering equations [68.8204255655161]
フィルタ方程式は、数値天気予報、金融、工学など、多くの現実の応用において中心的な役割を果たす。
フィルタリング方程式の解を近似する古典的なアプローチの1つは、分割法と呼ばれるPDEにインスパイアされた方法を使うことである。
我々はこの手法をニューラルネットワーク表現と組み合わせて、信号プロセスの非正規化条件分布の近似を生成する。
論文 参考訳（メタデータ） (2022-01-10T11:01:36Z) - Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
マルコフ決定過程における純粋探索問題について検討する。
エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
論文 参考訳（メタデータ） (2021-06-05T09:16:28Z) - Statistical Approach to Quantum Phase Estimation [62.92678804023415]
位相推定アルゴリズム(PEA)に新しい統計的・変動的アプローチを導入する。
固有位相推定のみを返す従来的かつ反復的なPEAとは異なり、提案手法は未知の固有状態-固有位相対を決定できる。
本稿では,IBM Qプラットフォームおよびローカルコンピュータ上で,Qiskitパッケージを用いた手法のシミュレーション結果を示す。
論文 参考訳（メタデータ） (2021-04-21T00:02:00Z) - A spectral algorithm for robust regression with subgaussian rates [0.0]
本研究では, 試料の分布に強い仮定がない場合の線形回帰に対する2次時間に対する新しい線形アルゴリズムについて検討する。
目的は、データが有限モーメントしか持たなくても最適な準ガウス誤差を達成できる手順を設計することである。
論文 参考訳（メタデータ） (2020-07-12T19:33:50Z) - Mean field analysis of reverse annealing for code-division
multiple-access multiuser detection [0.966840768820136]
レプリカ法を用いて,CDMAマルチユーザ検出の典型的なARA性能を統計力学を用いて評価した。
本研究では, 1次位相遷移を回避するために, 実用アルゴリズムがしきい値を超えうることを示す。
論文 参考訳（メタデータ） (2020-04-23T10:57:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。