論文の概要: Node Similarities under Random Projections: Limits and Pathological Cases
- arxiv url: http://arxiv.org/abs/2404.10148v2
- Date: Mon, 29 Jul 2024 16:51:26 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-30 23:27:56.042999
- Title: Node Similarities under Random Projections: Limits and Pathological Cases
- Title(参考訳): ランダム射影におけるノードの類似性:限界と病理例
- Authors: Tvrtko Tadić, Cassiano Becker, Jennifer Neville,
- Abstract要約: ランダム投影法により, ドット積とコサインの類似性がいかによく保存されているかを検討する。
埋め込みによって誘導されるノード順序を反転させるランダムなプロジェクションの確率を計算することにより、基本的な結果をランキングアプリケーションに特殊化する。
ランダムな投射によって生じる統計的ノイズに関して、コサイン類似性は驚くほど正確な近似をもたらすことを示す。
- 参考スコア(独自算出の注目度): 9.452274776651494
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Random Projections have been widely used to generate embeddings for various graph learning tasks due to their computational efficiency. The majority of applications have been justified through the Johnson-Lindenstrauss Lemma. In this paper, we take a step further and investigate how well dot product and cosine similarity are preserved by random projections when these are applied over the rows of the graph matrix. Our analysis provides new asymptotic and finite-sample results, identifies pathological cases, and tests them with numerical experiments. We specialize our fundamental results to a ranking application by computing the probability of random projections flipping the node ordering induced by their embeddings. We find that, depending on the degree distribution, the method produces especially unreliable embeddings for the dot product, regardless of whether the adjacency or the normalized transition matrix is used. With respect to the statistical noise introduced by random projections, we show that cosine similarity produces remarkably more precise approximations.
- Abstract(参考訳): ランダム射影は、計算効率のために様々なグラフ学習タスクの埋め込みを生成するために広く用いられている。
アプリケーションの大部分はJohnson-Lindenstrauss Lemmaを通じて正当化されている。
本稿では,グラフ行列の行に印加した場合に,ランダムなプロジェクションによってドット積とコサインの類似性がいかによく保存されるかを検討する。
我々の分析は、新しい漸近的および有限サンプルの結果を提供し、病理症例を特定し、数値実験でそれらを検証する。
埋め込みによって誘導されるノード順序を反転させるランダムなプロジェクションの確率を計算することにより、基本的な結果をランキングアプリケーションに特殊化する。
次数分布によっては, 隣接性, 正規化遷移行列の有無にかかわらず, ドット積に対して特に信頼性の低い埋め込みを生成する。
ランダムな投射によって生じる統計的ノイズに関して、コサイン類似性は驚くほど正確な近似をもたらすことを示す。
関連論文リスト
- On diffusion-based generative models and their error bounds: The log-concave case with full convergence estimates [5.13323375365494]
我々は,強い対数空間データ分布を仮定して,拡散に基づく生成モデルの収束挙動を理論的に保証する。
我々は、モチベーションの例を通して、未知の平均を持つガウス分布からサンプリングし、我々のアプローチの強力さを実証する。
この手法はサンプリングアルゴリズムにおいて最もよく知られた収束率をもたらす。
論文 参考訳(メタデータ) (2023-11-22T18:40:45Z) - Posterior Contraction Rates for Mat\'ern Gaussian Processes on
Riemannian Manifolds [51.68005047958965]
我々は,本質的なガウス過程が実際により優れた性能を発揮することを示す。
我々の研究は、データ効率の異なるレベルを区別するために、よりきめ細かい分析が必要であることを示している。
論文 参考訳(メタデータ) (2023-09-19T20:30:58Z) - Statistically Optimal Generative Modeling with Maximum Deviation from the Empirical Distribution [2.1146241717926664]
本稿では, 左非可逆なプッシュフォワード写像に制約されたワッサーシュタインGANが, 複製を回避し, 経験的分布から著しく逸脱する分布を生成することを示す。
我々の最も重要な寄与は、生成分布と経験的分布の間のワッサーシュタイン-1距離の有限サンプル下界を与える。
また、生成分布と真のデータ生成との距離に有限サンプル上限を確立する。
論文 参考訳(メタデータ) (2023-07-31T06:11:57Z) - Conditionally Strongly Log-Concave Generative Models [33.79337785731899]
本稿では, 強い対数対数分布を持つ条件付き確率分布の積にデータ分布を分解する条件付き強対数対数モデルを提案する。
これは効率的なパラメータ推定とサンプリングアルゴリズムにつながり、理論的な保証があるが、データ分布はグローバルなログコンケーブではない。
数値的な結果は、$varphi4$モデルや弱レンズ収束写像のような物理場に対して、以前の研究よりも高分解能で示される。
論文 参考訳(メタデータ) (2023-05-31T20:59:47Z) - Exact Non-Oblivious Performance of Rademacher Random Embeddings [79.28094304325116]
本稿では,Rademacherランダムプロジェクションの性能を再検討する。
入力データに関して数値的に鋭く、曖昧でない新しい統計的保証を確立する。
論文 参考訳(メタデータ) (2023-03-21T11:45:27Z) - Importance sampling for stochastic quantum simulations [68.8204255655161]
我々は、係数に応じてハミルトン式からサンプリングしてランダムな積公式を構築するqDriftプロトコルを導入する。
サンプリング段階における個別のシミュレーションコストを考慮し、同じ精度でシミュレーションコストを削減可能であることを示す。
格子核効果場理論を用いて数値シミュレーションを行った結果, 実験結果が得られた。
論文 参考訳(メタデータ) (2022-12-12T15:06:32Z) - Shortcomings of Top-Down Randomization-Based Sanity Checks for
Evaluations of Deep Neural Network Explanations [67.40641255908443]
モデルランダム化に基づく正当性チェックの限界を,説明書の評価のために同定する。
トップダウンモデルランダム化は、フォワードパスアクティベーションのスケールを高い確率で保存する。
論文 参考訳(メタデータ) (2022-11-22T18:52:38Z) - Convergence for score-based generative modeling with polynomial
complexity [9.953088581242845]
我々は、Scoreベースの生成モデルの背後にあるコアメカニックに対する最初の収束保証を証明した。
以前の作品と比較すると、時間的に指数関数的に増加するエラーや、次元の呪いに苦しむエラーは発生しない。
予測器・相関器はどちらの部分のみを使用するよりも収束性が高いことを示す。
論文 参考訳(メタデータ) (2022-06-13T14:57:35Z) - Efficiently Sampling Functions from Gaussian Process Posteriors [76.94808614373609]
高速後部サンプリングのための簡易かつ汎用的なアプローチを提案する。
分離されたサンプルパスがガウス過程の後部を通常のコストのごく一部で正確に表現する方法を実証する。
論文 参考訳(メタデータ) (2020-02-21T14:03:16Z) - A comparison of different types of Niching Genetic Algorithms for
variable selection in solar radiation estimation [0.0]
本研究は,アルゼンチンのトゥクマン州に分布する4つの気象観測所の気候データベースに適用した8種類のニーチ手法の挙動を比較した。
目標は、推定方法によって入力変数として使われた異なる入力変数の集合を見つけることである。
論文 参考訳(メタデータ) (2020-02-14T13:52:04Z) - Fast approximations in the homogeneous Ising model for use in scene
analysis [61.0951285821105]
我々は、推論に必要な量を数値計算できる正確な近似を提供する。
近似式はスケーラブルでマルコフランダム場の大きさに満足できないことを示す。
機能的磁気共鳴イメージングアクティベーション検出実験においてベイズ推論を行い, ピスタチオ樹収量の年次増加の空間パターンにおける異方性に対する確率比試験を行った。
論文 参考訳(メタデータ) (2017-12-06T14:24:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。