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
[を] 転置インデックスによる検索システムを作ってみよう！
転置インデックスによる検索システムを作ってみよう！ 2007-11-26-5 [Algorithm][Programming] 転置インデックス[2007-06-17-6]による検索システムの実装は パフォーマンスを無視すれば意外と簡単です。 それを示すために Perl で簡単な検索システムを作ってみました。 検索方式は転置インデックス(Inverted Index)、 ランキングには TF-IDF[2005-10-12-1] を用いました。 検索対象ファイルは一行一記事で以下のフォーマットとします。 [記事ID][SPC][記事内容]\n 記事IDは数字、記事内容は UTF-8 の文字で構成されるものとします。 以下のようなサンプル test.txt を用意しました。 1 これはペンです 2 最近はどうですか？ 3 ペンギン大好き 4 こんにちは。いかがおすごしですか？ 5 ここ最近疲れ
![[を] 転置インデックスによる検索システムを作ってみよう！](https://cdn-ak-scissors.b.st-hatena.com/image/square/af37977ee866988286b95e74fff98500a190545c/height=288;version=1;width=512/https%3A%2F%2Fchalow.net%2Fimages%2Ftcl-logo-25.png){kind=logo}
講義資料 - PukiWiki
講義資料 † 注: 直したつもりではありますが去年からの更新のし忘れで，python.logos.ic.i.u-tokyo.ac.jp というサーバ名が，ときどき marten.logos.ic.i.u-tokyo.ac.jp となっていることが有るかもしれません(もうないつもり)．marten はすべからく pythonと読み替えてください ここには、講義のスライドや配布資料がアップされます。 ↑ テストデータ, reference情報など † 10/30 mini-Python文法 grammar.txt 10/30 字句解析器テストデータ tokenizer_test.tar.gz 11/14 構文木ヘッダsyntree.h.txt 11/14 構文木Cソースの一部syntree.c.txt 11/14 構文解析木ヘッダparser.h.txt 11/14 構文解析木Cソース一部al
livedoor Developers Blog:String::Trigram でテキストの類似度を測る - livedoor Blog（ブログ）
こんにちは。検索グループ解析チームの nabokov7 です。 今回は、livedoor キーワードでの事例より、テキストの類似度を測るのに便利な手法を紹介します。 livedoor キーワードは、livedoor ブログでその日その日で話題になった語をランキング表示するサービスです。 当初、はてなキーワードやWikipediaを足して2で割ったようなサービスを作れといった開き直った指示のもとで開発が開始されたともいう、分社化前の芸風の名残で、キーワードの検索結果にはユーザが自由に解説を書き込める Wikipedia 的スペースもついています。 で、この解説部分に、さまざまなサイトから文章をまる写ししちゃう人がとても多いのですね。 特に多いウィキペディア日本語版からの剽窃を防止するために、livedoor キーワードでは以下のような対策を講じることにしました。 ウィキペディア日本語版の解説
Web関連語抽出を試作
Web関連語抽出を試作 2007-09-04-3 [WebTool][NLP] Web関連語抽出 http://yapi.ta2o.net/kanrenp/ Yahoo!ウェブ検索APIで検索結果100件を取ってきて、形態素解析をかけて、 複合名詞的なものだけ抽出し、出現頻度をカウントして表示します。 ちょっと前に作ったやつで、まだ試作段階なんだけど、 とりあえず動くので公開しておきます。 例： - 銀行 http://yapi.ta2o.net/kanrenp/s/%E9%8A%80%E8%A1%8C.html - skype http://yapi.ta2o.net/kanrenp/s/skype.html - カメラ http://yapi.ta2o.net/kanrenp/s/%E3%82%AB%E3%83%A1%E3%83%A9.html 出てくる関連語はいろいろ使いまわしができ
カイ二乗値で単語間の関連の強さを調べる
カイ二乗値で単語間の関連の強さを調べる 2007-09-19-1 [Algorithm][Programming] カイ２乗値を使って単語間の関連度を調べる方法。 つまり、関連語を探すときに、χ二乗値を関連度として使う。 perl によるサンプルコード (chiword.pl)。昔、勉強がてら作ったコード。 #!/usr/bin/perl use strict; use warnings; my %cnt; my $pair_num; while (<>) { chomp; next if /^\s*$/; my @list = sort split(/,/, $_); for (my $i = 0; $i < @list; $i++) { for (my $j = $i + 1; $j < @list; $j++) { next if $list[$i] eq $list[$j]; $c
きまぐれ日記: 情報抽出アルゴリズム Espresso 最終章
Espresso を飲みながらさらに Espresso を考えていました。 r_instance = A^n * r_instance_0 となるのは間違いないと思います。A は P * P^{T}、さらに P = 1/|I||P| * pmi(i, p)/ maxpmi です。 A は、インスタンスどうしの類似度を表現した正方対称行列です。A_{i,j} はインスタンス i, j の類似度です。 類似度は、パターン個数次元からなるベクトルの内積で、各次元は pmi となります。 この形だと、r_instanc は r_instance_0 できまるので、初期値に依存してるように思えますが、A^n がいったい どういう意味を持つのかずっと考えていました。 A_{i,j} が 0, 1 の場合、A は無向グラフの接続行列となります。i,j がつながっている場合は A_{i,j} = 1となり
Pythonでのキーワード抽出実装
初出: 2007/6/27 更新: 2007/7/1 文章からキーワードを抽出するスクリプトをPythonモジュールとして実装しました。 分かち書きした上に、適切に複合語をつくり、さらに重要そうなものかどうかのスコアをつけます。 アルゴリズムは、以下のサイトを参考にしました。 http://gensen.dl.itc.u-tokyo.ac.jp/ ここで紹介されている論文 * 中川裕志、森辰則、湯本紘彰: "出現頻度と連接頻度に基づく専門用語抽出",自然言語処理、Vol.10 No.1, pp. 27 - 45, 2003年1月 http://www.r.dl.itc.u-tokyo.ac.jp/~nakagawa/academic-res/jnlp10-1.pdf に掲載されているFLR法のみを実装しています。 実行結果サンプル たとえば、こんなページの本文をテキストフ
Wikipediaのキーワードリンクを使って関連語データを作ってみた
Wikipediaのキーワードリンクを使って関連語データを作ってみた 2007-06-09-3 [NLP][Programming][Algorithm] Wikipedia のキーワードリンクを使って関連語データ（関連キーワード集） を作ってみた。 Wikipedia のデータはダウンロードページからbz2形式のを取ってきた。 日本のウィキペディアのXMLデータね。 (see Wikipedia:データベースダウンロード) で、Perlスクリプトで以下の関連語データ作成処理を行った。 （スクリプトはこの記事の末尾に載せておく） (1) 各キーワードページに含まれているキーワード（リンク）を取り出す。 例えばキーワードAのページにB,C,Dが含まれていたら、A => B,C,D というデータを蓄積。 またキーワードAが他のキーワードのページ（例えばX）に含まれていたら、それも蓄積。その場合
きまぐれ日記: ルー語変換を MeCab だけで実現
巷で話題のルー語変換．周りにこういうしゃべり方をする人がいるからかもしれませんが， 爆笑しました 中身は，MeCab -> EDICT -> Bilingual Emacspeak だそうです． 単純な単語置換なので，MeCab を汎用テキスト変換ツールとして利用すればまったく同じことが MeCab だけで実現できます． やってることは単純で, MeCab の辞書の品詞フィールドをルー語にした辞書を作るだけです．対象のルー語がない場合は単語そのものを品詞に設定します． 通常は 「入力文字列 -> 品詞列」 の変換が行われます．上記のような辞書を作ると，品詞の部分がすべてルー語に置き換わって 「入力文字列 -> ルー語文字列」の変換が実現されます． しかも単語のつながりやすさや，出現しやすさは上記のような辞書を作っても CSV カラムの 2,3,4 カラム目に残っているので， 原理的には M
きまぐれ日記: キーワード抽出: tf-idf の意味づけ
単語の重み付けの古典的な方法に tf-idf があります。文書中の各単語の tf-idf 値計算し、値でソートすると、その文書に特徴的な単語リストを得ることができます。 http://nais.to/~yto/clog/2005-10-12-1.html tf-idf は、単なるヒューリスティックスだと考えられていましたが、最近言語モデルに基づく情報検索手法がさかんに研究されるようになり、tf*idf の解釈が明らかになってきました。言語モデルに基づく手法は、ヒューリスティックスばりばりの手法と同性能にもかかわらず、文書のランキングに理論的で合理的な説明を与えることができます。 情報検索は、クエリ q に対し、もっとも適合する文書 d_opt を求めるタスクです。つまり、q が与えられたとき、文書 d が出現する確率 p(d|q) の最大化問題と解釈できます。 d_opt = argmax
言語情報・悪魔の辞典 - Hiroshi Nakagawa
Hiroshi Nakagawa 言語情報・悪魔の辞典 「悪魔の辞典」という有名な本がありますが、その書名があまりに魅力的なの で、これをパロッたたくさんの本や記事があります。この小文もその末席に座 ることを目指しているわけです。 見出し語一覧 一神教 Nグラム 学者 逆説 クイック 言語学者 作文 再現率 終助詞 ジップの法則 情報検索 人工知能 ソシュール 成長 単語 辞書 チョムスキー 適合率 日本語の乱れ(終助詞) 日本語の乱れ(やる) メタデータ 一神教（バカの壁） 養老猛司著「バカの壁」によると、都会人は精神的に弱く、 何かにすがりたい気持ちがあるので、絶対的な権威を持つ一神教に引きずりこ まれる傾向があるのだと言います。一方、塩野七生は「ローマ人の物語」の中 で、ローマの人々は、3世紀以降、それまでのやり方がうまくいかなくなって、 それまでの多神教から一神教であるキリスト教に
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://it.jeita.or.jp/eltech/committee/knowledge/2004.html
長岡技科大 自然言語処理研究室さんの公開Bookまーく