論文の概要: 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を通じて正当化されている。 本稿では,グラフ行列の行に印加した場合に,ランダムなプロジェクションによってドット積とコサインの類似性がいかによく保存されるかを検討する。 我々の分析は、新しい漸近的および有限サンプルの結果を提供し、病理症例を特定し、数値実験でそれらを検証する。 埋め込みによって誘導されるノード順序を反転させるランダムなプロジェクションの確率を計算することにより、基本的な結果をランキングアプリケーションに特殊化する。 次数分布によっては, 隣接性, 正規化遷移行列の有無にかかわらず, ドット積に対して特に信頼性の低い埋め込みを生成する。 ランダムな投射によって生じる統計的ノイズに関して、コサイン類似性は驚くほど正確な近似をもたらすことを示す。

関連論文リスト

• Gaussian Processes Sampling with Sparse Grids under Additive Schwarz Preconditioner [6.408773096179187]
  本稿では,GPモデルの前と後をランダムに実現するためのスケーラブルなアルゴリズムを提案する。 提案アルゴリズムはスパースグリッドを用いた点近似と加法的シュワルツプレコンディショナーを利用する。
  論文  参考訳（メタデータ） (2024-08-01T00:19:36Z)
• On randomized estimators of the Hafnian of a nonnegative matrix [0.0]
  ガウス・ボソンのサンプルは、古典的に難しいと信じられているサンプリングタスクを実行することで量子的優位性を示すことを目的としている。 非負行列に対しては、特定のランダム行列を生成し、その行列式を計算することに基づいて、ハフニアンのランダム化推定子の族が存在する。 ここでは、バルビノクとゴッドシル=ガットマン推定器と呼ばれる2つの推定器の性能について検討する。
  論文  参考訳（メタデータ） (2023-12-15T19:00:07Z)
• A Heavy-Tailed Algebra for Probabilistic Programming [53.32246823168763]
  本稿では,確率変数の尾を解析するための体系的アプローチを提案する。 本稿では,確率型プログラミング言語コンパイラの静的解析(サンプル作成前)において,この手法をどのように利用できるかを示す。 実験結果から,重み付き代数を利用する推論アルゴリズムは,多数の密度モデリングおよび変分推論タスクにおいて優れた性能が得られることを確認した。
  論文  参考訳（メタデータ） (2023-06-15T16:37:36Z)
• Statistical Efficiency of Score Matching: The View from Isoperimetry [96.65637602827942]
  本研究では, スコアマッチングの統計的効率と推定される分布の等尺性との間に, 密接な関係を示す。 これらの結果はサンプル状態と有限状態の両方で定式化する。
  論文  参考訳（メタデータ） (2022-10-03T06:09:01Z)
• Confidence-Optimal Random Embeddings [0.0]
  本稿では、最適でデータに富む統計信頼度境界を持つjohnson-lindenstrauss分布を考案する。 境界は、任意のデータ次元、埋め込み、および歪み耐性に対して、数値的に最良である。 統計的精度の面での先行作業の改善に加え、データ可読アプローチの無意味な体制を正確に決定します。
  論文  参考訳（メタデータ） (2021-04-06T18:00:02Z)
• Pathwise Conditioning of Gaussian Processes [72.61885354624604]
  ガウス過程後部をシミュレーションするための従来のアプローチでは、有限個の入力位置のプロセス値の限界分布からサンプルを抽出する。 この分布中心の特徴づけは、所望のランダムベクトルのサイズで3次スケールする生成戦略をもたらす。 条件付けのこのパスワイズ解釈が、ガウス過程の後部を効率的にサンプリングするのに役立てる近似の一般族をいかに生み出すかを示す。
  論文  参考訳（メタデータ） (2020-11-08T17:09:37Z)
• Asymptotic Analysis of an Ensemble of Randomly Projected Linear Discriminants [94.46276668068327]
  [1]では、ランダムに投影された線形判別式のアンサンブルを用いてデータセットを分類する。 我々は,計算コストのかかるクロスバリデーション推定器の代替として,誤分類確率の一貫した推定器を開発する。 また、実データと合成データの両方で投影次元を調整するための推定器の使用を実証する。
  論文  参考訳（メタデータ） (2020-04-17T12:47:04Z)
• Efficiently Sampling Functions from Gaussian Process Posteriors [76.94808614373609]
  高速後部サンプリングのための簡易かつ汎用的なアプローチを提案する。 分離されたサンプルパスがガウス過程の後部を通常のコストのごく一部で正確に表現する方法を実証する。
  論文  参考訳（メタデータ） (2020-02-21T14:03:16Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  最小二乗問題に対する反復スケッチの性能について検討する。 本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。 これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
  論文  参考訳（メタデータ） (2020-02-03T16:17:50Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。