論文の概要: OPORP: One Permutation + One Random Projection
- arxiv url: http://arxiv.org/abs/2302.03505v2
- Date: Tue, 23 May 2023 15:03:53 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-25 00:25:09.690881
- Title: OPORP: One Permutation + One Random Projection
- Title（参考訳）: OPORP: 1つの置換+1つのランダム投影
- Authors: Ping Li and Xiaoyun Li
- Abstract要約: OPORPは、データ縮小/圧縮を達成するために、count-sketch'型のデータ構造の一種を使用する。
1つの重要なステップは、$k$サンプルを$l$標準に正規化することだ。
OPORPでは、(i)正規化と(ii)固定長ビンニングスキームの2つの重要なステップが、コサイン類似性を推定する精度を大幅に改善した。
- 参考スコア（独自算出の注目度）: 37.6593006747285
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Consider two $D$-dimensional data vectors (e.g., embeddings): $u, v$. In many
embedding-based retrieval (EBR) applications where the vectors are generated
from trained models, $D=256\sim 1024$ are common. In this paper, OPORP (one
permutation + one random projection) uses a variant of the ``count-sketch''
type of data structures for achieving data reduction/compression. With OPORP,
we first apply a permutation on the data vectors. A random vector $r$ is
generated i.i.d. with moments: $E(r_i) = 0, E(r_i^2)=1, E(r_i^3) =0,
E(r_i^4)=s$. We multiply (as dot product) $r$ with all permuted data vectors.
Then we break the $D$ columns into $k$ equal-length bins and aggregate (i.e.,
sum) the values in each bin to obtain $k$ samples from each data vector. One
crucial step is to normalize the $k$ samples to the unit $l_2$ norm. We show
that the estimation variance is essentially: $(s-1)A +
\frac{D-k}{D-1}\frac{1}{k}\left[ (1-\rho^2)^2 -2A\right]$, where $A\geq 0$ is a
function of the data ($u,v$). This formula reveals several key properties: (1)
We need $s=1$. (2) The factor $\frac{D-k}{D-1}$ can be highly beneficial in
reducing variances. (3) The term $\frac{1}{k}(1-\rho^2)^2$ is a substantial
improvement compared with $\frac{1}{k}(1+\rho^2)$, which corresponds to the
un-normalized estimator. We illustrate that by letting the $k$ in OPORP to be
$k=1$ and repeat the procedure $m$ times, we exactly recover the work of ``very
spars random projections'' (VSRP). This immediately leads to a normalized
estimator for VSRP which substantially improves the original estimator of VSRP.
In summary, with OPORP, the two key steps: (i) the normalization and (ii) the
fixed-length binning scheme, have considerably improved the accuracy in
estimating the cosine similarity, which is a routine (and crucial) task in
modern embedding-based retrieval (EBR) applications.
- Abstract（参考訳）: 2つのD$次元のデータベクトル(例えば埋め込み)を考える:$u, v$。
ベクトルが訓練されたモデルから生成される多くの埋め込みベース検索(EBR)アプリケーションでは、$D=256\sim 1024$が一般的である。
本稿では, oporp (one permutation + one random projection) が ``count-sketch''' 型のデータ構造の変種を用いて,データの縮小圧縮を実現する。
OPORPでは、まずデータベクトルに置換を適用する。
乱ベクトル$r$が生成される:$E(r_i) = 0, E(r_i^2)=1, E(r_i^3) =0, E(r_i^4)=s$。
ドット積として)$r$をすべての置換データベクトルに乗算します。
次に$D$列を$k$等長のビンに分割し、各ビンの値(すなわち和)を集約し、各データベクトルから$k$サンプルを取得する。
1つの重要なステップは、$k$サンプルを$l_2$標準に正規化することである。
推定分散は基本的に: $(s-1)A + \frac{D-k}{D-1}\frac{1}{k}\left[ (1-\rho^2)^2 -2A\right]$, ここで$A\geq 0$はデータ(u,v$)の関数である。
この式はいくつかの重要な性質を明らかにしている: (1)$s=1$。
2) 因子 $\frac{D-k}{D-1}$ は分散の減少に非常に有益である。
(3) $\frac{1}{k}(1-\rho^2)^2$ という用語は、非正規化推定器に対応する $\frac{1}{k}(1+\rho^2)$ と比較して大幅に改善される。
我々は、OPORPの$k$を$k=1$にし、プロシージャを$m$回繰り返すことで、 'very spars random projections' (VSRP)の作業を正確に回復する。
これはすぐにVSRPの正規化推定器につながり、VSRPの当初の推定器を大幅に改善した。
まとめると、OPORPでは、2つの重要なステップがあります。
(i)正規化及び
(ii)固定長バイナリ化方式は,現代の埋め込み型検索 (ebr) アプリケーションにおいて日常的(かつ重要な)タスクであるコサイン類似度の推定精度を大幅に向上させた。
関連論文リスト
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Regression for matrix-valued data via Kronecker products factorization [0.5156484100374059]
我々は、パラメータ $beta_1k サブセット Rep times q_1$ および $beta_2k サブセット Rep times q$ を推定するための推定アルゴリズム KRO-PRO-FAC を提案する。
シミュレーションおよび実データに関する数値的研究は,提案手法が既存の手法と比較して,推定誤差と予測精度の両方において競合的であることを示している。
論文 参考訳（メタデータ） (2024-04-30T02:44:41Z) - Structure Learning in Graphical Models from Indirect Observations [17.521712510832558]
本稿では、パラメータ法と非パラメトリック法の両方を用いて、Rp$における$p$次元ランダムベクトル$Xのグラフィカル構造を学習する。
温和な条件下では、グラフ構造推定器が正しい構造を得ることができることを示す。
論文 参考訳（メタデータ） (2022-05-06T19:24:44Z) - Weighted-average quantile regression [1.0742675209112622]
重み付き平均量子化回帰フレームワークである$int_Y|X(u)psi(u)du = X'beta$を導入する。
我々はパラメータのベクトルを$beta$で推定し、$T$は利用可能なサンプルのサイズである。
論文 参考訳（メタデータ） (2022-03-06T19:06:53Z) - Spectral properties of sample covariance matrices arising from random
matrices with independent non identically distributed columns [50.053491972003656]
関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$.
ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
論文 参考訳（メタデータ） (2021-09-06T14:21:43Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - Sparse sketches with small inversion bias [79.77110958547695]
逆バイアスは、逆の共分散に依存する量の推定を平均化するときに生じる。
本研究では、確率行列に対する$(epsilon,delta)$-unbiased estimatorという概念に基づいて、逆バイアスを解析するためのフレームワークを開発する。
スケッチ行列 $S$ が密度が高く、すなわちサブガウスのエントリを持つとき、$(epsilon,delta)$-unbiased for $(Atop A)-1$ は $m=O(d+sqrt d/ のスケッチを持つ。
論文 参考訳（メタデータ） (2020-11-21T01:33:15Z) - Sharp threshold for alignment of graph databases with Gaussian weights [1.6752182911522522]
重み付きグラフ(行列)データベースアライメントにおける再構成の基本的限界について検討する。
我々は、$pi*$の正確なリカバリには鋭いしきい値が存在することを証明している。
論文 参考訳（メタデータ） (2020-10-30T14:42:17Z) - Truncated Linear Regression in High Dimensions [26.41623833920794]
truncated linear regression において、従属変数 $(A_i, y_i)_i$ は $y_i= A_irm T cdot x* + eta_i$ は固定された未知の興味ベクトルである。
目標は、$A_i$とノイズ分布に関するいくつかの好ましい条件の下で$x*$を回復することである。
我々は、$k$-sparse $n$-dimensional vectors $x*$ from $m$ truncated sample。
論文 参考訳（メタデータ） (2020-07-29T00:31:34Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。