論文の概要: Node Similarities under Random Projections: Limits and Pathological Cases
- arxiv url: http://arxiv.org/abs/2404.10148v1
- Date: Mon, 15 Apr 2024 21:35:25 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-17 18:51:25.386024
- 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 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. Our analysis provides new theoretical results, identifies pathological cases, and tests them with numerical experiments. We find that, for nodes of lower or higher degrees, the method produces especially unreliable embeddings for the dot product, regardless of whether the adjacency or the (normalized version) transition 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を通じて正当化されている。
本稿では、Random Projectionsにより、ドット積とコサイン類似性がいかによく保存されているかについて、さらに詳しく検討する。
我々の分析は、新しい理論的結果を提供し、病理症例を特定し、それらを数値実験で検証する。
その結果, 次数以下のノードに対しては, 隣接性や(正規化バージョン)遷移の有無にかかわらず, ドット積に対して特に信頼性の低い埋め込みを生成することがわかった。
ランダム射影による統計的ノイズに関して、コサイン類似性は驚くほど正確な近似を生成することを示す。
関連論文リスト
- Fundamental Bias in Inverting Random Sampling Matrices with Application to Sub-sampled Newton [43.55440953429919]
逆バイアス(英: inversion bias)とは、ランダムスケッチ自体の非バイアスにもかかわらず、ランダムスケッチの逆は非バイアスにならない現象である。
このバイアスは、さまざまな機械学習パイプラインでランダムスケッチを使用する際の課題を示す。
本研究では,一様および非一様レバレッジに基づくランダムサンプリング法と,構造化されたランダムプロジェクションに対して,逆バイアスを補正する方法を示す。
論文 参考訳(メタデータ) (2025-02-19T09:49:38Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。