Fugu-MT 論文翻訳(概要): C-MinHash: Rigorously Reducing $K$ Permutations to Two

論文の概要: C-MinHash: Rigorously Reducing $K$ Permutations to Two

arxiv url: http://arxiv.org/abs/2109.03337v1
Date: Tue, 7 Sep 2021 21:06:33 GMT
ステータス: 翻訳完了
システム内更新日: 2021-09-10 07:42:27.810214
Title: C-MinHash: Rigorously Reducing $K$ Permutations to Two
Title（参考訳）: C-MinHash:$K$の置換を2つに厳格に削減
Authors: Xiaoyun Li and Ping Li
Abstract要約: MinHash (Minwise hashing) は、大量のバイナリ (0/1) データにおける Jaccard (resemblance) の類似性を近似するために、ランダムハッシュを生成するための重要かつ実用的なアルゴリズムである。我々は、bf Circulant MinHash (C-MinHash)を提案する。
参考スコア（独自算出の注目度）: 25.356048456005023
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Minwise hashing (MinHash) is an important and practical algorithm for generating random hashes to approximate the Jaccard (resemblance) similarity in massive binary (0/1) data. The basic theory of MinHash requires applying hundreds or even thousands of independent random permutations to each data vector in the dataset, in order to obtain reliable results for (e.g.,) building large-scale learning models or approximate near neighbor search in massive data. In this paper, we propose {\bf Circulant MinHash (C-MinHash)} and provide the surprising theoretical results that we just need \textbf{two} independent random permutations. For C-MinHash, we first conduct an initial permutation on the data vector, then we use a second permutation to generate hash values. Basically, the second permutation is re-used $K$ times via circulant shifting to produce $K$ hashes. Unlike classical MinHash, these $K$ hashes are obviously correlated, but we are able to provide rigorous proofs that we still obtain an unbiased estimate of the Jaccard similarity and the theoretical variance is uniformly smaller than that of the classical MinHash with $K$ independent permutations. The theoretical proofs of C-MinHash require some non-trivial efforts. Numerical experiments are conducted to justify the theory and demonstrate the effectiveness of C-MinHash.
Abstract（参考訳）: minhash (minwise hashing) は、大規模バイナリ (0/1) データの jaccard (resemance) 類似性を近似するためにランダムハッシュを生成するための重要かつ実用的なアルゴリズムである。 MinHashの基本理論は、大規模な学習モデルの構築や、大規模データの近傍の探索の信頼性を得るために、データセットの各データベクトルに数百から数千の独立したランダムな置換を適用することを必要とする。本稿では, {\bf circulant minhash (c-minhash)} を提案し,その理論的な結果について述べる。 C-MinHashの場合、まずデータベクトルに初期置換を行い、次に第2の置換を使ってハッシュ値を生成する。基本的に、第2の置換は循環シフトによって$K$倍に再使用される。古典的なMinHashとは異なり、これらの$K$ハッシュは明らかに相関性があるが、それでもジャカード類似性の偏りのない推定値が得られるという厳密な証明を与えることができ、理論的な分散は古典的なMinHashのものと独立な置換の$K$よりも均一に小さい。 C-MinHashの理論的な証明は、いくつかの非自明な努力を必要とする。理論を正当化し,C-MinHashの有効性を示す数値実験を行った。

関連論文リスト

Pb-Hash: Partitioned b-bit Hashing [21.607059258448594]
我々は、$B$ビットを$m$チャンク、例えば$btimes m =B$に分割することでハッシュを再使用することを提案する。我々の理論的分析により、ハッシュ値を$m$チャンクに分割することで、精度が低下することが明らかとなった。一部のリージョンでは、Pb-Hashは4.9ドルよりもずっと大きい$m$でもうまく機能している。
論文参考訳（メタデータ） (2023-06-28T06:05:47Z)
Differentially Private One Permutation Hashing and Bin-wise Consistent Weighted Sampling [37.6593006747285]
Minwise hashing (MinHash) は、大規模な検索および学習アプリケーションで広く使われている標準アルゴリズムである。 1つの置換ハッシュ(OPH)は、データベクトルを$K$ binに分割し、各bin内でハッシュ値を生成するMinHashの効率的な代替手段である。我々は, DP-OPH-fix, DP-OPH-re, DP-OPH-randの3つの変種を用いたDP-OPHフレームワークを提案する。
論文参考訳（メタデータ） (2023-06-13T10:38:12Z)
Replicable Clustering [57.19013971737493]
我々は,統計学的な$k$-medians,統計学的な$k$-means,統計学的な$k$-centers問題のアルゴリズムをブラックボックス方式で近似ルーチンを用いて提案する。理論的結果を検証するブラックボックスとしてsklearnの$k$-means++実装を用いた2次元合成分布の実験も行っている。
論文参考訳（メタデータ） (2023-02-20T23:29:43Z)
Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文参考訳（メタデータ） (2023-01-11T09:12:28Z)
A Lower Bound of Hash Codes' Performance [122.88252443695492]
本稿では,ハッシュ符号間のクラス間の差分性とクラス内圧縮性が,ハッシュ符号の性能の低い境界を決定することを証明する。次に、ハッシュコードの後部を推定し、それを制御することにより、上記の目的を完全に活用する代理モデルを提案し、低バイアス最適化を実現する。一連のハッシュモデルをテストすることで、平均精度が最大で26.5%、精度が最大で20.5%向上した。
論文参考訳（メタデータ） (2022-10-12T03:30:56Z)
Learning to Hash Naturally Sorts [84.90210592082829]
そこで我々はNaturely-Sorted Hashing (NSH)を導入し,最終結果のソートによる深層ハッシュモデルのトレーニングを行った。 NSHはサンプルのハッシュコードのハミング距離をソートし、それに従って自己教師付きトレーニングのための潜伏した表現を収集する。 Sorted Noise-Contrastive Estimation (SortedNCE) の新たな損失について述べる。
論文参考訳（メタデータ） (2022-01-31T16:19:02Z)
C-OPH: Improving the Accuracy of One Permutation Hashing (OPH) with Circulant Permutations [25.356048456005023]
我々は,C-MinHashの基本的な考え方を取り入れて,一置換ハッシュの精度を向上させることを提案する。ジャカード類似度の推定分散は、既存の(同定された) OPH 法よりも厳密に小さいことを示すことができる。
論文参考訳（メタデータ） (2021-11-18T06:52:15Z)
C-MinHash: Practically Reducing Two Permutations to Just One [25.356048456005023]
従来のミンワイズハッシュ (MinHash) では、大量のバイナリ (0/1) データで Jaccard の類似性を推定するために、$K$ の独立した置換を適用する必要がある。 C-MinHashに関する最近の研究は、2つの置換しか必要ないことを示している。 1つの単一の置換は、データの構造を壊す最初の前処理ステップと、K$ハッシュを生成する循環ハッシュステップの両方に使用される。
論文参考訳（メタデータ） (2021-09-10T00:08:47Z)
List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文参考訳（メタデータ） (2020-11-19T17:21:37Z)
CIMON: Towards High-quality Hash Codes [63.37321228830102]
我々はtextbfComprehensive stextbfImilarity textbfMining と ctextbfOnsistency leartextbfNing (CIMON) という新しい手法を提案する。まず、グローバルな洗練と類似度統計分布を用いて、信頼性とスムーズなガイダンスを得る。第二に、意味的整合性学習とコントラスト的整合性学習の両方を導入して、乱不変と差別的ハッシュコードの両方を導出する。
論文参考訳（メタデータ） (2020-10-15T14:47:14Z)
DartMinHash: Fast Sketching for Weighted Sets [0.5584060970507505]
重み付きハッシュは、類似性探索や大規模カーネルマシンに応用した標準的な次元削減手法である。 mathbbR_geq 0d$の重み付き集合を$xとし、期待時間に$k$独立ミンハッシュを計算する単純なアルゴリズムを導入する。
論文参考訳（メタデータ） (2020-05-23T14:59:25Z)

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

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