論文の概要: Differentially Private One Permutation Hashing and Bin-wise Consistent Weighted Sampling

• arxiv url: http://arxiv.org/abs/2306.07674v1
• Date: Tue, 13 Jun 2023 10:38:12 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-14 14:11:57.550119
• Title: Differentially Private One Permutation Hashing and Bin-wise Consistent Weighted Sampling
• Title（参考訳）: 微分プライベートな1置換ハッシュとbin-wise consistent weighted sampling
• Authors: Xiaoyun Li and Ping Li
• Abstract要約: Minwise hashing (MinHash) は、大規模な検索および学習アプリケーションで広く使われている標準アルゴリズムである。 1つの置換ハッシュ(OPH)は、データベクトルを$K$ binに分割し、各bin内でハッシュ値を生成するMinHashの効率的な代替手段である。 我々は, DP-OPH-fix, DP-OPH-re, DP-OPH-randの3つの変種を用いたDP-OPHフレームワークを提案する。
• 参考スコア（独自算出の注目度）: 37.6593006747285
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Minwise hashing (MinHash) is a standard algorithm widely used in the industry, for large-scale search and learning applications with the binary (0/1) Jaccard similarity. One common use of MinHash is for processing massive n-gram text representations so that practitioners do not have to materialize the original data (which would be prohibitive). Another popular use of MinHash is for building hash tables to enable sub-linear time approximate near neighbor (ANN) search. MinHash has also been used as a tool for building large-scale machine learning systems. The standard implementation of MinHash requires applying $K$ random permutations. In comparison, the method of one permutation hashing (OPH), is an efficient alternative of MinHash which splits the data vectors into $K$ bins and generates hash values within each bin. OPH is substantially more efficient and also more convenient to use. In this paper, we combine the differential privacy (DP) with OPH (as well as MinHash), to propose the DP-OPH framework with three variants: DP-OPH-fix, DP-OPH-re and DP-OPH-rand, depending on which densification strategy is adopted to deal with empty bins in OPH. A detailed roadmap to the algorithm design is presented along with the privacy analysis. An analytical comparison of our proposed DP-OPH methods with the DP minwise hashing (DP-MH) is provided to justify the advantage of DP-OPH. Experiments on similarity search confirm the merits of DP-OPH, and guide the choice of the proper variant in different practical scenarios. Our technique is also extended to bin-wise consistent weighted sampling (BCWS) to develop a new DP algorithm called DP-BCWS for non-binary data. Experiments on classification tasks demonstrate that DP-BCWS is able to achieve excellent utility at around $\epsilon = 5\sim 10$, where $\epsilon$ is the standard parameter in the language of $(\epsilon, \delta)$-DP.
• Abstract（参考訳）: Minwise hashing (MinHash) は業界で広く使われている標準アルゴリズムであり、バイナリ (0/1) の Jaccard 類似性を持つ大規模検索および学習アプリケーションに使用される。 MinHashの一般的な用途の1つは、大規模なn-gramテキスト表現を処理することで、実践者が元のデータ(禁じられる)を作らなくてもよいようにすることである。 MinHashのもう1つの一般的な用途は、隣接する(ANN)サーチに近いサブ線形時間を可能にするハッシュテーブルの構築である。 MinHashは大規模な機械学習システムを構築するツールとしても利用されている。 MinHashの標準実装には、$K$ランダムな置換を適用する必要がある。 比較として、one permutation hashing (oph)は、データベクトルを$k$binに分割し、各bin内でハッシュ値を生成するminhashの効率的な代替品である。 OPHはより効率的で、より便利である。 本稿では,ディファレンシャルプライバシ (dp) と oph (minhash) を組み合わせることで,dp-oph-fix, dp-oph-re, dp-oph-rand の3つの変種とdp-ophフレームワークを提案する。 アルゴリズム設計に関する詳細なロードマップとプライバシ分析について述べる。 提案手法のDP-OPH法とDP-MH法との比較を行い,DP-OPHの利点を正当化した。 類似性探索実験はdp-ophの利点を検証し、異なる実用シナリオにおける適切な変種の選択を導く。 提案手法は,非バイナリデータに対するDP-BCWSと呼ばれる新しいDPアルゴリズムを開発するために,bin-wise consistent weighted sample (BCWS) にも拡張される。 分類タスクの実験では、DP-BCWS が $\epsilon = 5\sim 10$ で優れたユーティリティを達成できることが示されており、$\epsilon$ は $(\epsilon, \delta)$-DP の言語の標準パラメータである。

関連論文リスト

• Pb-Hash: Partitioned b-bit Hashing [21.607059258448594]
  我々は、$B$ビットを$m$チャンク、例えば$btimes m =B$に分割することでハッシュを再使用することを提案する。 我々の理論的分析により、ハッシュ値を$m$チャンクに分割することで、精度が低下することが明らかとなった。 一部のリージョンでは、Pb-Hashは4.9ドルよりもずっと大きい$m$でもうまく機能している。
  論文  参考訳（メタデータ） (2023-06-28T06:05:47Z)
• 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: Rigorously Reducing $K$ Permutations to Two [25.356048456005023]
  MinHash (Minwise hashing) は、大量のバイナリ (0/1) データにおける Jaccard (resemblance) の類似性を近似するために、ランダムハッシュを生成するための重要かつ実用的なアルゴリズムである。 我々は、bf Circulant MinHash (C-MinHash)を提案する。
  論文  参考訳（メタデータ） (2021-09-07T21:06:33Z)
• Unsupervised Multi-Index Semantic Hashing [23.169142004594434]
  マルチインデックスハッシュに最適化することで,効率的かつ高効率なハッシュコードを学習する教師なしハッシュモデルを提案する。 文書類似度検索のタスクにおいて、MISHと最先端のセマンティックハッシュベースラインを実験的に比較する。 マルチインデックスハッシュは、線形スキャンと比較してベースラインの効率も向上しますが、MISHよりも33%遅くなっています。
  論文  参考訳（メタデータ） (2021-03-26T13:33:48Z)
• CIMON: Towards High-quality Hash Codes [63.37321228830102]
  我々はtextbfComprehensive stextbfImilarity textbfMining と ctextbfOnsistency leartextbfNing (CIMON) という新しい手法を提案する。 まず、グローバルな洗練と類似度統計分布を用いて、信頼性とスムーズなガイダンスを得る。第二に、意味的整合性学習とコントラスト的整合性学習の両方を導入して、乱不変と差別的ハッシュコードの両方を導出する。
  論文  参考訳（メタデータ） (2020-10-15T14:47:14Z)
• Deep Hashing with Hash-Consistent Large Margin Proxy Embeddings [65.36757931982469]
  画像ハッシュコードは、分類または検索のために訓練された畳み込みニューラルネットワーク(CNN)の埋め込みをバイナライズすることによって生成される。 この曖昧さを解消するために、固定されたプロキシ(CNN分類層の重み)の使用が提案されている。 得られたHCLMプロキシはハッシュ単位の飽和を促進することが示され、小さな二項化誤差が保証される。
  論文  参考訳（メタデータ） (2020-07-27T23:47:43Z)
• Reinforcing Short-Length Hashing [61.75883795807109]
  既存の手法は、非常に短いハッシュコードを用いた検索性能が劣っている。 本研究では, 短寿命ハッシュ(RSLH)を改良する新しい手法を提案する。 本稿では,ハッシュ表現とセマンティックラベルの相互再構成を行い,セマンティック情報を保存する。 3つの大規模画像ベンチマークの実験は、様々な短いハッシュシナリオ下でのRSLHの優れた性能を示す。
  論文  参考訳（メタデータ） (2020-04-24T02:23:52Z)
• Bio-Inspired Hashing for Unsupervised Similarity Search [12.78093617645299]
  本稿では,データ駆動方式で疎い高次元ハッシュコードを生成する新しいハッシュアルゴリズムBioHashを提案する。 我々の研究は、LSHが様々な生物学的システムにおけるスパース拡大モチーフの膨大さの計算的理由である可能性を示唆する証拠を提供する。
  論文  参考訳（メタデータ） (2020-01-14T17:04:59Z)

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

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