MinHashによる高速な類似検索 - Preferred Networks Research & Development
年が明けてもう一ヶ月経ちましたね．岡野原です． 今日はMinHashと呼ばれる手法を紹介します．これは特徴ベクトルの高速な類似検索に利用することができます(クローラーの文脈だとShingleとして知られている）． 今や世の中のあらゆる種類のデータが，高次元のバイナリベクトルからなる特徴ベクトルで表されて処理されるようになってきました．例えば文書データであれば文書中に出現する単語やキーワードの出現情報を並べた単語空間ベクトル（Bag of Words）で表し，画像データも，SIFTをはじめとした局所特徴量を並べた特徴ベクトル（とそれをSkecth化したもの）として表せます．行動情報や時系列データも特徴量をうまく抽出する．グラフデータもFast subtree kernels[1]と呼ばれる方法で非常に効率的に特徴ベクトルに変換することができ，グラフの特徴をよく捉えることができるのが最近わかっ
「第3回自然言語処理勉強会＠東京」でCSAについて発表します - EchizenBlog-Zwei
@nokunoさんの好意で「第3回自然言語処理勉強会＠東京」でCompressed Suffix Arrayについて発表させていただくことになりました。 つきましては参考のため発表資料を以下に置いておきます。参加される方はもちろん、興味のある方はご覧になっていただけるとうれしいです。 第3回自然言語処理勉強会＠東京 : ATND 第3回自然言語処理勉強会＠東京を開催します - nokunoの日記 なお本資料は以下の皆様のアドバイスを頂きました。ありがとうございました(とくに@overlastさんには4-5時間もお付き合い頂きました。おかげさまでスライドの質が大幅アップしました。感謝)。 @overlastさん @tamago_donburiさん @tsubosakaさん @machyさん
リンク解析とか: 重要度尺度と von Neumann カーネル - smly’s notepad
NAIST の入学手続を終えた. 残りの期間はサーベイするぞーということで shimbo 先生の講義資料「リンク解析とその周辺の話題」を読んでいます. 一日目, 二日目の資料は PageRank, HITS, SALSA などの重要度尺度の紹介と, von Neumann Kernels と HITS の関係についてのお話が中心. これらを実装してみた. 後半に進むほど力尽きて記述が適当になってます:)PageRankポイントはランダム遷移行列による random walk では定常分布に収束しない (エルゴード性 (ergodic) を満たさない) という点. どうして満たさないかというと. sink (出次数のない節点) が存在するとき, 明らかに既約 (irreducible) でないのでエルゴード性を満たさない. 複数の強連結成分を持つケース => 周期性を持つと考えてよい? 周期
トライ（ダブル配列，簡潔データ構造）と STL コンテナ - ny23の日記
以前実装した構築速度重視の動的ダブル配列 (表中 dda) の構築速度を Darts, darts-clone (0.32g beta5, 0.32e5), DASTrie (1.0), doar (0.0.10)，簡潔データ構造を利用したトライ (tx 0.16) ，STL コンテナ (std::map, std::tr1::unordered_map) 辺りと比べてみた．キー集合としては，中規模で疎な集合（Wikipedia 英語版記事タイトル）と小規模で密な集合（郵便番号辞書）を用いた． ====================================================================== Wikipedia-en 記事タイトル | Build | Search | Search* | Size [bytes] =================
超高速テキスト処理のためのアルゴリズムとデータ構造 (PDF)
超高速テキスト処理のための ゕルゴリズムとデータ構造 東京大学情報理工学系研究科* 岡野原 大輔 hillbig@is.s.u-tokyo.ac.jp NLP2010 チュートリゕル 2010 3/8@東京大学本郷キャンパス * 2010年4月から所属が （株）プリフゔードンフラストラクチャーになります。 内容 • 背景 – 自然言語処理と機械学習 • オンラン学習 – 教師有/無, 正則化 • 疎ベクトル々文字列データ構造 – 特徴情報の格納、全部分文字列情報 • 乱択化ゕルゴリズム – Hash Kernel, Randomized SVD 背景 大規模自然言語処理と機械学習 背景 • 利用可能な言語資源の急激な拡大 – ブログ, 掲示板, 商品情報, レビュー – Wikipedia, Google N-gram Corpus ～1010 語 – c.f. Penn TreeB
Topic-Sensitive PageRank - 日々の勉強の航跡
Taher H. Haveliwala. Topic-Sensitive PageRank Proceedings of the Eleventh International World Wide Web Conference, 2002. PDFへのリンク 概要 Topic-Sensitive PageRankという、PageRankというアルゴリズムを改善したものの提唱 アルゴリズムの特徴 検索の結果にqueryやquery context(文脈、前後関係）を反映させる。 query contextを反映させる場合、この論文の実験ではuserがqueryを含む文章を指定しているが、文章ではなくcontextを反映させる方が良い結果を得られる。何をcontextにするかにはいろいろなアイディアがある（後述）。 PageRankはもともとウェブページにofflineでランク付けして(ran
Compressed Suffix Arrayの解説(4) -unary記法- - EchizenBlog-Zwei
< Compressed Suffix Arrayの解説(3) -圧縮の方針- < | > Compressed Suffix Arrayの解説(5) -Succinct Bit Vector- > ================================================ まずは下準備。数値列をunary記法でbit列に変換する方法を説明。 unary(ユナリィ)記法というのは数値の数だけの0を並べて、最後に1を置くというもの。具体例を挙げると 数値 unary 0 1 1 01 2 001 3 0001 4 00001 5 000001となる。 unary記法では1が数値間の境界を表すために各数値毎のbitサイズを固定長にする必要がない。例えば数値列 1 1 2 2 1 2は各数値をそれぞれ1byteで表したとすると全体で48bit(6byte)必要になる。一方で
第8回 転置索引における検索処理 | gihyo.jp
代表的な関連度指標には、コサイン類似度（cosine similarity）やOkapi BM25などがあります。具体的な計算式や詳細はここでは省略しますが、上記の値を組み合わせて、関連度を計算します[3]。 コサイン類似度は、文書とクエリをタームを次元としたベクトル空間にマップし、文書ベクトルとクエリベクトルの成す角度により、文書とクエリの関連度（類似度）を求めます（成す角度が小さければ関連度が高い）。またOkapi BM25は、文書がクエリに対して適合かどうかは確率的に決定されるという統計的な原理に基づき、文書とクエリの関連度を求めます。 検索時にこれらを計算するには、索引の構築時に上記の統計値を計算し保持しておく必要があります。実装にはさまざまな方法が考えられますが、たとえばfd,tはポスティングリストの中に埋め込んでおき[4]、ftやFtは辞書と一緒に保存しておくといった方
[IR] Google WSDM'09講演で述べられている符号化方式を実装してみた - tsubosakaの日記
MG勉強会の後にid:sleepy_yoshiさんに教えてもらったWSDM 2009における講演"Challenges in Building Large-Scale Information Retrieval Systems"で述べられている符号化方式のGroup Varint Encodingを実装してみた。 資料 講演スライド スライドの日本語による解説記事 整数の符号化方式 転置インデックスなどで文章番号のリストを前の値との差分で表すなどの方法を用いると出現する、ほとんどの値は小さな値となるためこれを4バイト使って表現するのは記憶容量の無駄である。 このためVarint Encoding、ガンマ符号、デルタ符号、Rice Coding、Simple 9、pForDeltaなど様々な符号化方式が提案されている。このうちVarint Encodingは実装が手軽なことからよく用いられて
![[IR] Google WSDM'09講演で述べられている符号化方式を実装してみた - tsubosakaの日記](https://cdn-ak-scissors.b.st-hatena.com/image/square/d5a026a6225c4524c834d0237efa271b5b0d54f0/height=288;version=1;width=512/https%3A%2F%2Fogimage.blog.st-hatena.com%2F17680117127124028144%2F17680117127124030436%2F1557332443)
DO++: AND検索の最尤推定
検索技術においてAND検索、つまり二つの単語を指定して、それが両方出現している文書数の推定を高速に行うのは難しい問題です。 問題を正しく書くと単語w_xが出ている文書番号(x1,x2,x3,..,xn)とw_yが出ている文書番号(y1,y2,y3,...,ym)が与えられたら | {(i,j)|x_i = y_j} | の数を求める問題です。 これは前もって全通り求めて保存しておくにも単語種類数の二乗のオーダー分必要なのでできません。 これは機械学習でも特徴関数が0/1の値しかとらないとき、二つの要素の特徴ベクトルの内積を求める問題と同じで、またデータベースでもJOINの順番を決めるときにでてくる問題です。 普通は全体の文書からサンプルをとって、その中で数えてみて、それを元のサイズにスケールさせることをします。例えば全体文書1億件の中から文書1000件だけとってきて、その中でw_xとw_y
Polynomial Semantic Indexing -- 大規模データからのスケーラブルな距離学習 - 武蔵野日記
午後はNIPS 2009 読み会。 Bing Bai, Jason Weston, David Grangier, Ronan Collobert, Kunihiko Sadamasa, Yanjun Qi and Corinna Cortes, Mehryar Mohri, "Polynomial Semantic Indexing" という論文について紹介してみた。 これはtsubosaka さんの日記にすばらしくまとまっているので、内容をあえて繰り返さず(クリアに書かれているので読む価値はあると思う)、感想を述べると、文書と文書の類似度を測る尺度としてこの polynomial semantic indexing はけっこう有用なのではないかな、と思った。@unnonounoさんと@tsubosakaさんも Twitter でつぶやいていたが、これは大規模なデータから低ランク近似して
Polynomial Semantic Indexing - tsubosakaの日記
NIPS 2009で発表された論文"Polynomial Semantic Indexing" [1]を読んだ。これは低ランク近似を用いた教師ありの情報検索に関する手法である。 情報検索について 与えられたクエリに関して適当な重みづけをおこなって順位づけして、適切な文章を返却するという問題は古くから研究されている。 オーソドックスな方法としては文章をbag-of-wordsで表して各単語の重みをtf-idfで正規化し、クエリに関しても同様な処理を行いコサイン類似度などの距離尺度を使って最も近い何件かを返すというものがある。この方法の欠点としてはクエリの単語を含まない文章はヒットしないという問題がある。これは各単語が独立であるという仮定を行っているためであり、明らかに誤っている仮定である。 もう一つの方法としては文章-単語行列が低次元の特徴量によって近似する方法である。代表的な方法としてLS
構築した辞書を元にAho Corasick法を使ってキーワードを探す - yasuhisa's blog
どのようなときにAho Corasick法が必要か辞書構築した後の応用先(?)の一つとして、辞書を元にした転置インデックスを作ることがあげられる。「どのキーワードがどの文章に登場したか」が一番簡単な転置インデックスだと思うんだけど、今回は登場した文章のどの位置にあったかまで記録したい(例えばリンクを張る時に使いたいから)。転置インデックス作るときは、通常 形態素解析ベース N-gramベース の2種類が主な手法だと思うんだけど、今回はせっかく構築した辞書をもとに転置インデックスを作りたいので、上の2つではうまくできない。かといって、文章とキーワード総当たりとかやっていたら死ぬので、効率のよい方法が必要。そこでAho Corasick法ですよ、奥さん。はてなキーワードへのリンク処理とかに使われたりします。 入力と出力入力と出力を先に紹介しよう。入力は辞書とこんな感じの文章。 <総説誌名>蛋白
ギレンも登場！BM25なPerlモジュール書いたよ - download_takeshi’s diary
久しぶりに何か書きます。 情報検索のアルゴリズムで「BM25」というものがあります。 何年か前に某研究所に遊びに行ったときに「TF/IDFより精度のいいやつ」みたいな感じでかなりアバウトに教えてもらいました。 その時は「名前だけでも覚えて帰ろう」と思っていたのですが、帰りに安い居酒屋で大酒をのみ、電車のなかで騒いでしまうほど酔っ払ってすっかりその名前を忘れてしまってました。（なにやってんだか・・・） で、最近Web+DB pressをパラパラ見ていたらBM25の名前を発見！ああ、これだこれだ、思い出したよ！ というわけで、重い腰を上げてモジュール化してみました。 githubに上げてあります。 Lingua::JA::OkapiBM25 http://github.com/miki/Lingua-JA-OkapiBM25 そのうちCPANからも落とせるようになります。 正式名称は「Okap
min_heapを用いた上位r個の要素の抽出 - tsubosakaの日記
MG勉強会の発表があるため4.6ランキング検索の部分を読むついでに、最後のサブセクションの上位r個の要素を取り出す部分について実装してみた。 情報検索において、N個の候補集合から上位r個の要素を取り出すことが多い。 値が配列に格納されているとするとこれを実現するためのコードはもっとも単純に行うと以下のようになる //長さlenの配列arrayの中でトップr個の値をresultに挿入する void sort_method(int * array , int len, int r , vector<int> & result){ sort(array , array + len); copy(array + len - r , array + len , back_inserter(result)); } しかし、Nが大きいとき、MGの例だとN=100万のときにsortの処理にはおおよそ100
『Blogopolisの裏側』発表資料 - kaisehのブログ
昨日のSeasar Conference 2009 Autumnで発表させていただいた『Blogopolisの裏側』の資料を公開します。 Blogopolisの裏側View more documents from kaiseh. 資料の28枚目に、重み付きボロノイ図の重心ベースレイアウトの説明用動画がありました。その動画は以下にアップしました。 講演者の皆さん、運営の皆様、本当にお疲れ様でした！ 追記 id:mi-changさん p14ででてる「頂点数」、「多角形数」って何を意味してるんだろう?頂点数が多いということはより多くのタグと結びついているってこと? これは、1つ1つのエントリーやブログ、地区（カテゴリ）に対応する土地の幾何データのことです。例えば、5角形の土地の場合は5個の頂点座標が必要になります。土地の頂点数はレイアウト上の理由で決まるもので、タグとは直接関係はありません。
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
特異値分解とLSIの意味 - あらびき日記
Compressed Suffix Arrays - おなかすいたWiki！
加藤 和彦 Kazuhiko KATO, Dr. Prof.
Amazon.co.jp: Google PageRankの数理 ―最強検索エンジンのランキング手法を求めて―: Amy N.Langville (著), Carl D.Meyer (著), 岩野和生 (翻訳), 黒川利明 (翻訳), 黒川洋 (翻訳): 本
