論文の概要: Locality-sensitive hashing in function spaces
- arxiv url: http://arxiv.org/abs/2002.03909v1
- Date: Mon, 10 Feb 2020 16:16:26 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-02 08:27:49.670427
- Title: Locality-sensitive hashing in function spaces
- Title(参考訳): 関数空間における局所性に敏感なハッシュ
- Authors: Will Shand and Stephen Becker
- Abstract要約: 我々は、$mathbbRN$上のLSH関数を$Lp$空間に拡張できる2つの方法を提案する。
提示されたハッシュスキームを用いて、1次元連続確率分布上のワッサーシュタイン距離のLSH族を構成する。
- 参考スコア(独自算出の注目度): 6.316693022958221
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We discuss the problem of performing similarity search over function spaces.
To perform search over such spaces in a reasonable amount of time, we use {\it
locality-sensitive hashing} (LSH). We present two methods that allow LSH
functions on $\mathbb{R}^N$ to be extended to $L^p$ spaces: one using function
approximation in an orthonormal basis, and another using (quasi-)Monte
Carlo-style techniques. We use the presented hashing schemes to construct an
LSH family for Wasserstein distance over one-dimensional, continuous
probability distributions.
- Abstract(参考訳): 本稿では,関数空間上で類似性探索を行う問題について論じる。
このような空間を妥当な時間で探索するために、我々は {\displaystyle {\it locality-sensitive hashing} (lsh) を用いる。
本論文では,$\mathbb{r}^n$ 上の lsh 関数を $l^p$ 空間に拡張する2つの方法を提案する。
1次元連続確率分布上のwasserstein距離のためのlshファミリを構成するために,提案ハッシュスキームを用いる。
関連論文リスト
- Improving LSH via Tensorized Random Projection [0.07252027234425332]
テンソルデータに対するユークリッド距離とコサイン類似性に対する高速かつ空間効率な局所性感度ハッシュ関数を提案する。
我々のアプローチは空間効率が高く、低ランクの$CP$または$TT$テンソルに効率的に適用することができる。
論文 参考訳(メタデータ) (2024-02-11T12:54:07Z) - Fast Locality Sensitive Hashing with Theoretical Guarantee [5.635783105833339]
局所性に敏感なハッシュ(LSH)は、多くの機械学習タスクで広く使われている効果的なランダム化手法である。
本稿では,l2 ノルムの下で,FastLSH という名前の簡易かつ効率的な LSH スキームを設計する。
ランダムサンプリングとランダムプロジェクションを組み合わせることで、FastLSHは時間複雑性を O(n) から O(m) (mn) に還元する。
実験結果から,FastLSHは回答の品質,空間占有,クエリ効率の面で,最先端技術と同等であることがわかった。
論文 参考訳(メタデータ) (2023-09-27T08:21:38Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳(メタデータ) (2023-07-24T14:37:22Z) - An Approximation Theory for Metric Space-Valued Functions With A View
Towards Deep Learning [25.25903127886586]
任意のポーランド計量空間 $mathcalX$ と $mathcalY$ の間の連続写像の普遍函数近似器を構築する。
特に、必要なディラック測度数は $mathcalX$ と $mathcalY$ の構造によって決定されることを示す。
論文 参考訳(メタデータ) (2023-04-24T16:18:22Z) - Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。
本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
論文 参考訳(メタデータ) (2023-02-22T20:21:25Z) - Unsupervised Hashing with Similarity Distribution Calibration [127.34239817201549]
教師なしハッシュ法は、特徴空間内のデータポイント間の類似性をバイナリハッシュコードにマッピングすることで保存することを目的としている。
これらの方法は、連続的な特徴空間におけるデータポイント間の類似性が離散的なハッシュコード空間に保存されないという事実をしばしば見落としている。
類似性範囲はコードの長さによって制限され、類似性崩壊と呼ばれる問題を引き起こす可能性がある。
本稿では,この問題を緩和する新しい類似度分布法を提案する。
論文 参考訳(メタデータ) (2023-02-15T14:06:39Z) - Binary Representation via Jointly Personalized Sparse Hashing [22.296464665032588]
二元表現学習のための効果的な教師なし手法、すなわち、共同パーソナライズされたスパースハッシュ(JPSH)を提案する。
異なるパーソナライズされたサブスペースは、異なるクラスタのカテゴリ固有の属性を反映するように構成される。
JPSHにおける意味とペアの類似性を同時に保存するために,PSHと多様体に基づくハッシュ学習をシームレスな定式化に組み込む。
論文 参考訳(メタデータ) (2022-08-31T14:18:37Z) - Scalable Differentially Private Clustering via Hierarchically Separated
Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。
最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文 参考訳(メタデータ) (2022-06-17T09:24:41Z) - Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations [79.66404989555566]
我々は、リッチな観測空間を持つより現実的な非依存的RLの設定と、近似的ポリシーを含まないような固定されたポリシーのクラス$Pi$を考える。
我々は,MDPの階数$d$の誤差が有界な設定のためのアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-06-22T03:20:40Z) - Smooth Bandit Optimization: Generalization to H\"older Space [37.15553727896912]
我々は、目標が累積後悔である滑らかな報酬関数のバンディット最適化を考える。
私たちの主な結果は、指数 $alpha>1$ を持つ H"older space への報酬関数の一般化です。
私たちは、$alphaleq 1$サブセット内で、既存の下限に適合する後悔率を達成することを示します。
論文 参考訳(メタデータ) (2020-12-11T01:43:25Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳(メタデータ) (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。