We are often interested in finding users, hashtags and ads that are very similar to one another, so they may be recommended and shown to users and advertisers. To do this, we must consider many pairs of items, and evaluate how “similar” they are to one another. We call this the “all-pairs similarity” problem, sometimes known as a “similarity join.” We have developed a new efficient algorithm to so
Machine Learning Advent Calendar向けの記事です。 はじめに 最近、個人的にGo言語を触ることがちょいちょいあります。 型があって割と高速に動いてくれて、ポータビリティの高いとこが気に入ってるのですが、何十万・何百万人に推薦データを提供することが使命な会社にいるなら、これを推薦に使おうかなと画策しています。 というわけで今回は、周囲が皆サーベイ論文紹介とかなので若干毛色違いますが、Goでb-bit Minwise Hashingを実装したことについて書きます。 b-bit Minwise Hashingとは Minhash、及びb-bit Minhashについては、既にPFIの岡野原さんによる素晴らしいPostがあるため、詳しく知りたい方はそちら+その中で紹介されている論文を読んでいただくのが一番かと思います。 参考: MinHashによる高速な類似検索 ht
以前集合やベクトルの類似度の記事を書いたんですが、確率分布の類似度には触れていなかったのでついでに書きました ツイート時間分布の類似度を求める 今回はツイート時間ごとの頻度を正規化して、確率分布とみなして類似度を計算してみます 私のアカウント(以下mainと表記)に対して、私のもう一つのアカウント(以下subと表記)+私がリプライを送ってる数が多い(以下friendと表記)上位5人と比較します subがfriendよりも似た結果になることを期待しています 以下にツイート時間の分布(main + sub + friend 5人)を載せました ある程度似ていますが、人によってそこそこ形が違っていて、特に午前中の投稿時間の差は特徴的に見えます またfriend1の一人だけは大きく違った傾向を示しています 以下ではこれらが定量的にどれぐらい異なるのか類似度を計算して比較していきます グラフを描くの
Pythonで実装する類似度計算 - Screaming Loud #1283. 共起性の計算法 ↑この辺りの記事を見て、集合とかベクトルの類似度の計算の記事を下書きのまま放置していたことを思い出したので書き上げた。 類似度の計算のコードを書いたのでそれを載せるだけにしようかと思ったのですが、知っている人にしか伝わりそうにないので自然言語処理でよく使う話の概要だけでも書いときます。 導入 自然言語処理の分野では単語の意味を比較するときに、ある単語の周り(文脈)に出てきた単語のベクトル(文脈ベクトル)の類似度を計算することがある。 これは「ある単語の意味はその周囲に出現する単語によって特徴づけられている」という仮説に基づいていて、文脈ベクトルが似ていれば似たような意味、似たような状況で使われる単語が多いということが言えるからである。 Distributional semantics - Wi
はじめに 類似性が高いベクトルのハッシュ値が近い値になるようなハッシュ関数を使って、 類似するものを高速に検索することができるので、それを試してみた。 Locality Sensitive Hash 類似するデータが高確率で近い値になる(Locality-Sensitive)ハッシュ関数のこと 高次元データの次元圧縮を行える (P1,P2,r,cr)-sensitiveなHash族とは、 2つの特徴ベクトルp,qについて(P1>P2) ||p-q||P1 ||p-q||>crならPr[h(p)=h(q)] を満たすハッシュ関数h:R^d->U コサイン類似度に対するLSH 2つのk次元ベクトルu,vについて コサイン類似度: u*v / sqrt(|u|*|v|) d個のk次元のランダムベクトルr_iを考え、ハッシュ関数h_i(u)を h_i(u) = 1 (r*u >=0) h_i(u)
こんにちは．英語が書けなくて悩んでいる今日このごろです． 先月に引き続き，仲間内で行っている小さな勉強会にて論文紹介をしてまいりました． “Information-Theoretic Metric Learning” V. Davis et al, ICML 2007 (Best Paper) ちょっと古めの論文ですが，あまり踏み込んだことのない分野なので，名著っぽいものから確実におさえていくスタンスで． 発表スライドは以下においておきます．最後のスライドにいろいろ文献リンクしておいたので，ご興味をもって頂けましたら是非そちらも当たってみてください． Information-Theoretic Metric Learning from koji_matsuda 距離計量学習(以下単に距離学習)とは何ぞや，というのは小町さんの日記をご参照いただけると良いと思うのですが， ざっくり言うと，「分
Twitter でグラフ理論に関する話題が上がっていたので、最近調べている距離学習(distance metric learning)について少しまとめてみる。カーネルとか距離(類似度)とかを学習するという話(カーネルというのは2点間の近さを測る関数だと思ってもらえれば)。 この分野では Liu Yang によるA comprehensive survey on distance metric learning (2005) が包括的なサーベイ論文として有名なようだが、それのアップデート(かつ簡略)版として同じ著者によるAn overview of distance metric learning (2007) が出ているので、それをさらに簡略化してお届けする(元論文自体本文は3ページしかないし、引用文献のあとに表が2ページあって、それぞれ相違点と共通点がまとまっているので、これを見ると非
２つのデータが似ている度合いを，類似度の大きさや距離の近さといった数値にしてあらわすことで，クラスタ分析や，k-近傍法，多次元尺度構成法(MDS)をはじめとするいろいろな分析を行うことが可能となる． ここでは，よく知られている類似度や距離について述べる． 類似度という概念は，２つの集合の要素がまさにどれだけ似ているかを数量化したものであり，距離とは，要素同士の離れ具合，従って非類似度とちかい概念と考えてもよい． 参考までに数学における距離の概念の定義を示すと， 距離空間の定義 Sを１つの空でない集合とし，dをSで定義された2変数の実数値関数 d(SxS) → R が，以下の４条件（距離の公理） D1 ： （非負性） 任意のx,y∈Sに対して d(x,y)≧0． D2 ： （非退化性） x,y∈Sに対し d(x,y)=0 ⇔ x=y． D3 ： （対称性） 任意のx,y∈Sに対して d(x
海野です。ちょっと時間があいてしまいましたが、昨年の12月に開催されたNTCIR-9という会議のRecognizing Inference in TExt (RITE)というタスクに、前職の方々と共著で出場しました。 Syntactic Difference Based Approach for NTCIR-9 RITE Task. Yuta Tsuboi, Hiroshi Kanayama, Masaki Ohno and Yuya Unno. NTCIR-9, 2011. [pdf] 含意関係認識といわれるこのタスクは、大雑把に言うと与えられた2つの文が同じ意味のことを言っているかどうか判定しなさいというタスクです（厳密には一方からもう一方が帰結できるかの判定です）。今日は、その中で使ったTree Edit Distance (TED) について解説します。 TEDは2つの順序付き木が
大学院で自然言語処理の研究をしつつ、ブログタイトルのようなものを趣味的にチマチマと作っていまいた。個人的になかなか面白い解析結果が出たと思ったのでご紹介します。 目標： １．twitter上で、ある入力ユーザ（自分でなくてもよい）と興味の対象が似ているユーザを発見する ２．興味あるトピックには、どういう単語が含まれているか発見する 手法： １．１ユーザのツイート全体を１つの文書としてモデリングし、ＬＤＡで解析 ２．全てのユーザについて、トピック-ユーザの特徴ベクトルの距離を使って類似度を計算 特徴： １．巷にあるソーシャルネットワーク系の解析でありがちな、ユーザ同士のリンク情報を全く使っていない ２．トピックの次元は語彙の次元と比べてかなり小さい（1/(10^3)くらい）ので、単に単語の頻度を数えるのと比べて柔軟 解析結果ですが、とりあえずpythonの処理系が動作する環境で確認できるよう
OpenCVを使ってヒストグラムの比較を行ってみる。 どうやるかというと、二つの画像のヒストグラムを計算してから、cvCompareHistを用いてそれらを比較すればいい。 今回は以下の二つの画像を使ってみた。自分の手の画像です。 myhand1.jpg myhand2.jpg cvCompareHistには四つのメソッド(Correlation、Chi-square、Intersection、Bhattacharyya distance)がサポートされている。 Correlationを用いると 結果が高いほうがよりマッチしている 完璧なマッチだった場合は1 完璧なミスマッチの場合は-1 Chi-squareを用いると 結果が低いほうがよりマッチしている 完璧なマッチだった場合は0 完璧なミスマッチだった場合は際限のない値が得られる(ヒストグラムのサイズに依存する) Intersectio
Earth Mover's Distance (EMD) について調べたことを整理しておきます。EMDは、ユークリッド距離のような距離尺度の一つで、二つの分布の間の距離を測ることができます。言語処理ではあまり聞いたことなかったのですが、画像処理や音声処理では比較的有名な距離尺度のようです。 EMDが使える問題設定は下図のようになります。 EMDは特徴量と重みの集合（シグネチャと呼ぶ）で与えられる分布Pと分布Qの間の距離です。ここで、特徴量間では距離 が定義されているのが前提です。特徴量がベクトルのときはユークリッド距離、特徴量が確率分布のときはカルバック・ライブラー距離（情報量）などです。EMDは、特徴量の集合が2つ与えられたときに、1個1個の特徴量間の距離をもとに、特徴量集合間の距離を求められるんですね。これはすごい。 重みは具体的な応用によって使い方が変わりますが、その特徴量の重要度を
C++版のOpenCVを使ってカラーヒストグラムを用いた類似画像検索を実験してみました。バッチ処理などのスクリプトはPythonを使ってますが、PerlでもRubyでも似たような感じでできます。 指定した画像と類似した画像を検索するシステムは類似画像検索システムと言います。GoogleやYahoo!のイメージ検索は、クエリにキーワードを入れてキーワードに関連した画像を検索しますが、類似画像検索ではクエリに画像を与えるのが特徴的です。この分野は、Content-Based Image Retrieval (CBIR)と呼ばれており、最新のサーベイ論文（Datta,2008）を読むと1990年代前半とけっこう昔から研究されてます。 最新の手法では、色、形状、テクスチャ、特徴点などさまざまな特徴量を用いて類似度を判定するそうですが、今回は、もっとも簡単な「色」を用いた類似画像検索を実験してみます
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
