MinHash - Wikipedia
In computer science and data mining, MinHash (or the min-wise independent permutations locality sensitive hashing scheme) is a technique for quickly estimating how similar two sets are. The scheme was published by Andrei Broder in a 1997 conference,[1] and initially used in the AltaVista search engine to detect duplicate web pages and eliminate them from search results.[2] It has also been applied
Rubyでb-Bit MinHashを実装してみた。 - タチコマ好きなエンジニアのブログ
昨日に引き続き、SmartNews開発者ブログの「b-Bit MinHashによる高速かつ省スペースな類似度判定」を参考に、Rubyでb-Bit MinHashを実装してみた。 ビット数は1、ハッシュ関数の個数は128で計算させている。 ただし、1ビット値は最初から50％の確率で衝突するので、単に一致した回数をkで割っただけでは、真のJaccard係数が0の場合でも0.5くらいの推定値が出てきてしまいます。 とのことなので、一致数をハッシュ関数の個数で割った値から0.5を引いて2倍したものを表示させてみた。（calc_jaccardのコメントを外すと表示される） だいたい0.4に近い値が出るので多分合っているはず。 ベンチマーク的にはMinHashと大差がなかったけれど、popcountの処理をきちんと実装すれば速くなるかもしれない。 ソースコード require 'murmurhash3
b-Bit MinHashによる高速かつ省スペースな類似度判定 - SmartNews Engineering Blog
ゴクロの浜本です。ネットカフェでコードを書くのが好きです。 前回のエントリーでも触れられていますが、SmartNewsはホットな話題をユーザにお届けするために、常時、膨大な数のツイートおよびURLをクロールしています。こうして収集した記事に対し、様々な分析が施されますが、その中でも重要な処理の1つに、記事の類似度判定があります。内容の似通った記事をインデックスから発見し、グループ化する処理です。 毎秒、大量の新着記事が到着することから、この類似度判定は高速に実行する必要があります。また、インデックスを全てメモリに載せているので、類似度判定を実現する際の空間効率も要求されます。 今回は、SmartNewsが高速かつ省スペースな類似度判定のために使用しているb-Bit MinHashと呼ばれる手法を紹介します。2年前に、PFIの岡野原さんが非常に分かりやすい解説記事を書かれており、本エントリー
乱択データ構造の最新事情 －MinHash と HyperLogLog の最近の進歩－
Two sentences are tokenized and encoded by a BERT model. The first sentence describes two kids playing with a green crocodile float in a swimming pool. The second sentence describes two kids pushing an inflatable crocodile around in a pool. The tokenized sentences are passed through the BERT model, which outputs the encoded representations of the token sequences.
局所性鋭敏型ハッシュ - Wikipedia
局所性鋭敏型ハッシュ（きょくしょせいえいびんがたハッシュ、英語: locality sensitive hashing）とは高次元のデータを確率的な処理によって次元圧縮するための手法である。ハッシュの基本的な考え方は類似したデータが高確率で同じバケットに入るようにデータを整理するというものである。多くの場合においてこのバケットの数は入力されるデータサンプルの数よりもずっと小さくなる。 局所性鋭敏型ハッシュを行うためのパラメータの集合をLSH族(Locality Sensitive Hashing Family)と呼ぶ。LSH族は距離空間と閾値、近似因子によって定義される。LSH族[1][2]は2点について次の2つの性質、 ならばとなる確率は以上である。 ならばとなる確率は以下である。 を満たす関数により与えられる族であり，はから一様乱数にしたがって選択される。このときは2点の距離を表す関数
tfidf、LSI、LDAの違いについて調べてみた
tfidf、LSI、LDAの意味、違いを調べるために、それぞれの形式のコーパスの中身を調べてみた。そのメモ。 前回のおさらい 前回の記事では、もっとも基本的なコーパスの中身を確認してみました。その結果、「コーパスとは、文章集合をベクトル空間に変換したもの」いうことが分かりました。 今回は、基本的なコーパス以外の複数のコーパス、特に、tfidf、LSI、LDAで用いるコーパスについて、基本的なコーパスとは何が違うのかを調べます。その結果分かったコーパスの違いから、各モデルの違いを理解することを目標とします。 gensimに実装されたtfidfのコーパスの中身を見てみました 今回は、「Topics and Transformations」を参考に進めていきます。 >>> import logging >>> logging.basicConfig(format='%(asctime)s : %
Integrating BM25 & BM25F into Lucene1
Integrating BM25 & BM25F into Lucene Joaquín Pérez-Iglesias Introduction This document describes the BM25 and BM25F implementation using the Lucene Java Framework. The implementation described here can be downloaded from http://nlp.uned.es/~jperezi/Lucene-BM25/jar/models.jar. Both models have stood out at TREC by their performance and are considered as state-of-the-art in the IR community. BM25 i
TF-IDF - Negative/Positive Thinking
TF-IDFについて いくつかの文書が与えられたとき、文書中の単語の重みを決める手法の一つ。 TF(Term Frequency, 文書中の単語出現頻度) 「よくでてくる単語はその文書の主題を表しやすい」 ある文書dに単語tがでてきた個数をtf(t,d)と定める tfの定義として、個数nをそのまま用いてしまうと文書サイズが大きいほどnも大きくなってしまうことがある。 なので、文書中のすべての単語数で割って正規化したものをtfとして定義するのがいいかも。 IDF(Inverse Document Frequency, 単語が出現する文書数の逆数) 「どんな文書にもよくでてくる単語は、あんまり重要じゃない」 単語tがでてくる文書数をdf(t)とし、全文書数をNとしたとき、以下の式で決まる TF-IDF 上記の2つを組み合わせたもの。 ある文書dに出現する単語tの重みを以下のように定義。 Oka
tf–idf - Wikipedia
情報検索の分野において、tf–idf (または、 TF*IDF、TFIDF、TF–IDF、Tf–idf)は、term frequency–inverse document frequencyの略であり、コーパスや収集された文書群において、ある単語がいかに重要なのかを反映させることを意図した統計量（数値）である[1]。また、tf-idfは情報検索や、テキストマイニング、ユーザーモデリング（英語版）における重み係数（英語版）にもよく用いられる。ある単語のtf-idfの値は文書内におけるその単語の出現回数に比例して増加し、また、その単語を含むコーパス内の文書数によってその増加が相殺される。この性質は、一般にいくつかの単語はより出現しやすいという事実をうまく調整することに役立っている。今日、tf-idfはもっとも有名な語の重みづけ(term-weighting)手法である。2015年に行われた研究
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
