LLM 向け MinHash でテキストの重複除去のメモ
LLM 向けデータセットでは, 重複や繰り返し(repeatation)が少ないことが重要となります. Scaling Laws and Interpretability of Learning from Repeated Data Deduplicating Training Data Makes Language Models Better CCNet(LLaMa などで使われた), RefinedWeb(Falcon)でも dedup は重要な役割を果たしています. 情報 基本は Suffix Array で exact match と MinHash(LSH, Locally Sensitive Hash)で fuzzy match でテキストの重複除去を行うのが昨今(2023/07 時点)での主流のようです. (SimHash は遅いので大規模では使わないっぽ?) Shingle
【論文読み】CPUでディープラーニングを高速化するSLIDEの紹介 - Qiita
はじめに ライス大学とインテル社の共同開発によって、GPUのような特別なアクセラレーションハードウェアなしでディープラーニングを高速化できるSLIDEが考案されました。そのSLIDEについて解説します。 Deep Learning Breakthrough Results In A 44-Core Intel Xeon Destroying NVIDIA Tesla V100 GPU TL:DR GPUが得意とする行列演算をやるのではなく、LSHによって直接計算せず活性化したニューロンを取得することができます。 Locality Sensitive Hashing Locality Sensitive Hashing（LSH）は、大量なデータから類似度が高いデータのペアを高速に抽出してくれるアルゴリズムです。以下は参考ページです。SLIDEはこのLSHの考え方に基づいて設計されています。
高速な類似検索 ― ハミング距離と鳩ノ巣原理
見ての通り地獄です。k = 30 で六百五十二京九千九百六十九兆八千九百三億千七百九十三万（ろっぴゃくごじゅうにけいきゅうせんきゅうひゃくろくじゅうきゅうちょうはっせんきゅうひゃくさんおくせんななひゃくきゅうじゅうさんまん）になります。[3] [4] そもそも、線形探索より高速に検索することが目的でしたので、Q のサイズがデータの個数 n を上回っては元も子もないのです。例えば n が10億でも、k = 8 で Q のサイズは n をあっけなく上回ります。 でもまぁ安心してください。「だから皆さん線形探索を使いましょう！」なんてオチではないですし、まだ鳩も出てきてないです。以下では、この転置インデックスを用いた解法を上手く活用し、高速に問題を解くマルチインデックスという手法を紹介します。 マルチインデックス ここからは、転置インデックスによる解法を大きいパラメータに対しても有効に使うために
GDBM で学ぶ Extendible Hashing
最近仕事で GDBM を使う機会があり、GDBM で使われている extendible hashing に興味を持ったのでまとめてみました。 なお、今回対象にしている GDBM のバージョンは 1.12 です。 アジェンダ GDBM とは ハッシュテーブルの基礎 ハッシュ関数 衝突処理 リハッシュ Extendible Hashing GDBM による Extendible Hashing ハッシュ関数 ファイルヘッダのデータ構造 バケットのデータ構造 バケット要素のデータ構造 衝突処理 ディレクトリの拡張とバケットの分割 データベースファイルは要素数が多いと肥大化する おわりに 参考 GDBM とは http://www.gnu.org.ua/software/gdbm/ 曰く GNU dbm (or GDBM, for short) is a library of database f
ハッシュ探索について（個人用メモに近い） - Qiita
1.はじめに 友人と応用情報の勉強会を始めたのでそれ用のまとめです． 各個人が気になったところ，もう少し知りたいなと思ったところを勝手にまとめて共有する方式の勉強会です．（毎回記事にするかは怪しい） 記事としては既出もいいところでしょうが，今回の僕のテーマは探索アルゴリズム（ハッシュ探索）です． （綺麗にまとまっていませんが後日時間があれば追記したり整理します...） アルゴリズムについて まず僕がこれをテーマに選んだのは，今までハッシュは全単射じゃないと意味がない（完全に全単射は無理でしょうが，それに近いもの）と思っていたのですが，このハッシュ探索では，全単射が理想ではあるものの，そうでなくとも探索対象の集合を分割できるだけでも意味があるんだ，というもので賢いなと感動したからです． ハッシュはあくまでも道具であって，目的（解きたい問題）によっては使い方も変わるんだなと． 図にするとこんな
DBMの設計と実装 その1 ハッシュ関数 - 豪鬼メモ
個々のレコードがハッシュテーブル内のどのバケットに属するかはハッシュ関数で決める。入力値の種類によらずハッシュ値がうまいことばらけて衝突が起こりにくい関数が良い。今回は定番のMurmur hashを採用した。Rubyの文字列型のハッシュ関数もこれだ。 Murmur hashの値に対してバケット数で剰余を取れば十分なハッシュ関数として機能する。しかし、以前にそれで実装したソースを公開していたら、Murmur hashの作者から直に連絡があり、下位ビットだけ使うのは最善ではないと指摘された。32ビット以下のハッシュ関数が必要な場合、XORを使って上位ビットの折返しをした上で、剰余を取るべきだと。したがって、バケット数に応じたハッシュ関数の実装は以下のようになる。 uint64_t PrimaryHash(std::string_view data, uint64_t num_buckets)
MD5のハッシュ値オールゼロに挑戦 - わさっきhb
いきなりですが問題です． MD5のハッシュ値（チェックサム，fingerprint，メッセージダイジェスト）がすべて0となるような，入力メッセージを答えなさい． さっそくですが解答…いや，答えは知りません．もし，そんな入力メッセージを得ていたら，弱衝突耐性を破ったってことになります．そんな入力があるかどうかも，分かっていません． そこで，もっと簡単な問題にします． MD5のハッシュ値の先頭32ビット（16進出力では最初の8桁）がすべて0となるような，入力メッセージを答えなさい． これくらいだと，計算機をぶん回せば，答えが出てきそうです．情報セキュリティの試験も終わったことですし，Rubyスクリプトを書いてみました． Find all-zero hash · GitHub 少し気をつかったことが2つ，あります．一つは，入力メッセージをどのように生成するかです．乱数を使うと，周期の問題がありま
高速ハッシュアルゴリズム – YOSBITS
この記事は特に高速なハッシュアルゴリズムをまとめた資料です。 暗号的な強度が重要でない場合に使用できるアルゴリズムと暗号強度が考慮されたアルゴリズムがありハッシュ関数の利用環境あわせて検討すべきである。また、実行速度は実行環境に依存するので実際の実行環境で実測して判断するべきである。 MurmurHash 2008年に”Austin Appleby”が考案した非暗号ハッシュアルゴリムです。このアルゴリズムは暗号化処理などに向いていない。MurmurHash3 は現在のバージョンで、32ビットまたは128ビットのハッシュを生成する。MurmurHash2 は古いバージョンで、32ビットまたは64ビットのハッシュを生成する。64ビットのハッシュ値生成するソースには2つの変種がある。64ビットプロセッサ用に最適化された用の MurmurHash64A と32ビットプロセッサ用に最適化された Mu
C++でブルームフィルタを実装する方法 | POSTD
ブルームフィルタとは、「ある要素が集合のメンバである可能性があるか、それとも確実に集合のメンバではないか」を効果的に確認することのできるデータ構造です。この記事では、C++でブルームフィルタを実装する簡単な方法をご紹介します。 ブルームフィルタとは何なのか 、また、 その背後にある多くの数学的要素 については紹介していませんので、ご了承ください。これらのトピックに関しては、素晴らしいリソースがあるので、そちらを参考にしてください。 インターフェイス まずは、ブルームフィルタを定義していきましょう。ここでは、3つのパブリック関数を定義していきます。 コンストラクタ ブルームフィルタにアイテムを追加する関数 アイテムがブルームフィルタにある可能性を確認するためのクエリを行う関数 また、フィルタの状態を保持するビットの配列を含んだ、メンバ変数についても定義します。 #include <vecto
簡単な画像の類似度計算手法「Average Hash」 » Untitled Blog
画像の類似度を計算する方法を調査していたところ、面白い手法を紹介している方がいたので、この場でシェアしたいと思います。 この手法は「Perceptual Hash」という、「比較可能なハッシュ」を生成するための一手法です。 一般的にMD5やSHA1などのハッシュ値は、1バイトでもデータが違えば、まったく違うハッシュ値を返してきますが、「Perceptual Hash」は似たようなデータには似たようなハッシュ値を返してきます。 元ネタのブログによれば、これから紹介する手法のことを、ブログのオーナーであるDr. Neal Krawetzさんは「Average Hash」と呼んでいるようです。 元ネタのブログ記事は、以下のリンクからたどることができます。 Looks Like It – The Hacker Factor Blog いたってシンプルな手法ではありますが、例えば高速で「それなりの精
ConsistentHashing - コンシステント・ハッシュ法
ConsistentHashing - コンシステント・ハッシュ法 目次 この文書について コンシステント・ハッシュ法 実例 実装 用途 コンシステント・ハッシュ法 この文書について "Tom White's Blog: Consistent Hashing" の日本語訳です. http://weblogs.java.net/blog/tomwhite/archive/2007/11/consistent_hash.html 推敲歓迎: 誤訳, タイポ, 訳語の不統一, そのほか... 原文のライセンス: http://creativecommons.org/licenses/by-nc-sa/2.0/ 私は今までに何度かコンシステント・ハッシュ法にとりくんだことがある。 このアイデアをあらわした論文 ( David Karger らによる Consistent Hashing and R
パスワードハッシュにmd5を使うのは小学生までだよねー - 春木屋
おおよそのUNIX-likeシステムでは、パスワードファイルはMD5でハッシュされるのが一般的だ（った）。 しかし、MD5は1996年に脆弱性が見つかって以来、あまり推奨される方式ではなくなっている。 Wikipediaで調べてみても「パソコンレベルで、数10分程度で、同一ハッシュ値の非ユニークなデータ列を生成できる実装が広まっている」などと恐ろしい事が書かれている。 つまり暗号化されていてもMD5ハッシュだと総あたりで易々と破られてしまうということになる。 こういった情勢のもと、多くのシステムでは、パスワードファイルのハッシュ方法を変えたり、または自由に変えられるようになっているので、もしお前らがUNIX-likeシステムを管理しているなら、いますぐ確認しろ。 じゃあ何に変えたらいいの→SHA-2かBlowfishおすすめ。 代替のハッシュ方法としては、Blowfish, SHA-2など
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Remembrance - Radium Software