論文の概要: Pb-Hash: Partitioned b-bit Hashing
- arxiv url: http://arxiv.org/abs/2306.15944v1
- Date: Wed, 28 Jun 2023 06:05:47 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-29 15:37:26.797061
- Title: Pb-Hash: Partitioned b-bit Hashing
- Title（参考訳）: Pb-Hash: 分割bビットハッシュ
- Authors: Ping Li, Weijie Zhao
- Abstract要約: 我々は、$B$ビットを$m$チャンク、例えば$btimes m =B$に分割することでハッシュを再使用することを提案する。
我々の理論的分析により、ハッシュ値を$m$チャンクに分割することで、精度が低下することが明らかとなった。
一部のリージョンでは、Pb-Hashは4.9ドルよりもずっと大きい$m$でもうまく機能している。
- 参考スコア（独自算出の注目度）: 21.607059258448594
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Many hashing algorithms including minwise hashing (MinHash), one permutation
hashing (OPH), and consistent weighted sampling (CWS) generate integers of $B$
bits. With $k$ hashes for each data vector, the storage would be $B\times k$
bits; and when used for large-scale learning, the model size would be
$2^B\times k$, which can be expensive. A standard strategy is to use only the
lowest $b$ bits out of the $B$ bits and somewhat increase $k$, the number of
hashes. In this study, we propose to re-use the hashes by partitioning the $B$
bits into $m$ chunks, e.g., $b\times m =B$. Correspondingly, the model size
becomes $m\times 2^b \times k$, which can be substantially smaller than the
original $2^B\times k$.
Our theoretical analysis reveals that by partitioning the hash values into
$m$ chunks, the accuracy would drop. In other words, using $m$ chunks of $B/m$
bits would not be as accurate as directly using $B$ bits. This is due to the
correlation from re-using the same hash. On the other hand, our analysis also
shows that the accuracy would not drop much for (e.g.,) $m=2\sim 4$. In some
regions, Pb-Hash still works well even for $m$ much larger than 4. We expect
Pb-Hash would be a good addition to the family of hashing methods/applications
and benefit industrial practitioners.
We verify the effectiveness of Pb-Hash in machine learning tasks, for linear
SVM models as well as deep learning models. Since the hashed data are
essentially categorical (ID) features, we follow the standard practice of using
embedding tables for each hash. With Pb-Hash, we need to design an effective
strategy to combine $m$ embeddings. Our study provides an empirical evaluation
on four pooling schemes: concatenation, max pooling, mean pooling, and product
pooling. There is no definite answer which pooling would be always better and
we leave that for future study.
- Abstract（参考訳）: minwise hashing (minhash), one permutation hashing (oph), consistent weighted sampling (cws) を含む多くのハッシュアルゴリズムは、$b$bitの整数を生成する。
データベクトル毎に$k$ハッシュを使用すると、ストレージは$B\times k$ bitsとなり、大規模学習に使用する場合、モデルサイズは$2^B\times k$となる。
標準的な戦略は、$b$ビットのうち最低の$b$ビットのみを使用し、ハッシュ数である$k$を多少増やすことである。
本研究では,$B$ビットを$m$チャンク,例えば$b\times m =B$に分割することでハッシュを再使用することを提案する。
対応するモデルサイズは$m\times 2^b \times k$となり、これは元の$^b\times k$よりもかなり小さい。
理論分析の結果、ハッシュ値を$m$チャンクに分割すると精度が低下することが明らかとなった。
言い換えれば、$B/m$ビットの$m$チャンクを使うことは、$B$ビットを直接使用するほど正確ではない。
これは同じハッシュの再使用による相関のためである。
一方、我々の分析では(例えば)$m=2\sim 4$に対して精度があまり低下しないことも示している。
一部の地域では、pb-hashは4.99ドルよりはるかに大きい価格でも機能する。
Pb-Hashは、ハッシュメソッド/アプリケーションのファミリーに良い追加であり、産業従事者に利益をもたらすと期待しています。
線形SVMモデルおよびディープラーニングモデルに対する機械学習タスクにおけるPb-Hashの有効性を検証する。
ハッシュデータは本質的に分類(ID)機能であるため、各ハッシュに埋め込みテーブルを使用する標準的なプラクティスに従う。
Pb-Hashでは、$m$の埋め込みを組み合わせる効果的な戦略を設計する必要があります。
本研究は, 連結, 最大プール, 平均プール, 製品プールの4つの手法を実証的に評価した。
どのプールが良いかという明確な答えはなく、私たちは将来の研究のためにそれを残します。
関連論文リスト
- Minwise-Independent Permutations with Insertion and Deletion of Features [0.07252027234425332]
Broder textitet. al.citepBroderCFM98は、バイナリデータの低次元スケッチを計算する$mathrmminHash$アルゴリズムを導入している。
アルゴリズムの厳密な理論的解析を行い、実世界の複数のデータセットに関する広範な実験を補完する。
論文 参考訳（メタデータ） (2023-08-22T07:27:45Z) - 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) - A Lower Bound of Hash Codes' Performance [122.88252443695492]
本稿では,ハッシュ符号間のクラス間の差分性とクラス内圧縮性が,ハッシュ符号の性能の低い境界を決定することを証明する。
次に、ハッシュコードの後部を推定し、それを制御することにより、上記の目的を完全に活用する代理モデルを提案し、低バイアス最適化を実現する。
一連のハッシュモデルをテストすることで、平均精度が最大で26.5%、精度が最大で20.5%向上した。
論文 参考訳（メタデータ） (2022-10-12T03:30:56Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - One Loss for All: Deep Hashing with a Single Cosine Similarity based
Learning Objective [86.48094395282546]
ディープハッシュモデルは通常、学習されたバイナリハッシュコードの識別と量子化エラーの最小化という2つの学習目標を持つ。
本稿では,1つの学習目的しか持たない新しい深層ハッシュモデルを提案する。
我々のモデルは,3つの大規模インスタンス検索ベンチマークにおいて,最先端のマルチロスハッシュモデルより優れている。
論文 参考訳（メタデータ） (2021-09-29T14:27:51Z) - 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) - 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) - Under-bagging Nearest Neighbors for Imbalanced Classification [63.026765294759876]
我々は,不均衡な分類問題に対して,textitunder-bagging $k$-NN (textitunder-bagging $k$-NN) というアンサンブル学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-01T14:10:38Z) - 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) - A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。
我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。
次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
論文 参考訳（メタデータ） (2020-06-02T16:38:36Z) - DartMinHash: Fast Sketching for Weighted Sets [0.5584060970507505]
重み付きハッシュは、類似性探索や大規模カーネルマシンに応用した標準的な次元削減手法である。
mathbbR_geq 0d$の重み付き集合を$xとし、期待時間に$k$独立ミンハッシュを計算する単純なアルゴリズムを導入する。
論文 参考訳（メタデータ） (2020-05-23T14:59:25Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。