情報検索の評価についてメモ(適合率,再現率,F値)

あるモデルによって情報を分類した時に、どのくらいうまく分類しているのか評価するためのメトリクスについてメモ。 テーマを単純にするために、文書から関連する文書を探すような情報検索システムを考える。したがって、関連する・関連しないの二値分類。 適合率(precision) 探した文書に含まれる関連文書の割合。 どれだけ正確に関連文書を探せているかを判定。 再現率(recall) 関連文書をどこまで探し出せているか。 網羅性を判定。 F値(F-score, F-measure, F_1 score) 適合率と再現率はトレードオフの関係にあるため、調和平均してバランスを見るのがF値 例 関連するドキュメントは relevant の頭文字をとって R、関連しないドキュメントは nonrelevant の頭文字をとって N で表すことにする。 3個だけ関連文書があるとする。 R R N R N N N N N N 例1)極端な例として、システムがすべての文書を関連すると判断した場合 正解 R R N R N N N N N N 検索 1 1 1 1 1 1 1 1 1

類似係数(Jaccard/Simpson/Dice)をPythonで求める

語が2つ与えられた時に、どのくらい似ているのか計量評価したいといった目的のために類似指数というのが存在します。 今回は、よく知られていて、かつ、実装の簡単な Jaccard 係数 Simpson 係数 Dice 係数 を Python で実装します。 これら3つの係数は、0から1までの値を取り、1に近づくほど類似し、0に近づくほど類似していないことを表します。 Jaccard 係数 Jaccard index, Jaccard similarity coefficient などとも呼ばれます。 次の式で表されます。 xとYが完全一致 の場合に1となります。 Simpson 係数 overlap coefficient, Szymkiewicz-Simpson coefficient などとも呼ばれます。 次の式で表されます。 XとYが完全一致 XがYの部分集合(またはその逆) の場合に1となります。 Dice 係数 Dice’s coefficient/Sørensen-Dice coefficient などとも呼ばれます。 次の式で表されます。 xとYが完全一致 の場合に1となります。 三角不等式を満たさないため、 計算してみる night nacht nuit の3語に対して、各組み合わせの類似係数を求めてみましょう。 実行してみると、次のような結果となりました。 その他 今回は類似指数を「語」を対象にしましたが、2つのベクトル間の類似性を求めるなど、広い意味での類似性の抽出に利用出来ます。 関連リンク https://en.wikipedia.org/wiki/String_metric https://en.wikipedia.org/wiki/Jaccard_index

MARISA-TrieをコマンドラインとPythonから使う

概要 Matching Algorithm with Recursively Implemented StorAge (MARISA) という Trie に対する高い空間効率とそれなりの時間効率を実現するデータ構造があります。 動的な更新には対応していませんが 辞書引き（Lookup） : 入力文字列が登録されているかどうかを確認 逆引き（Reverse Lookup） : 入力された ID から登録文字列を復元 Common Prefix Search : 入力文字列の前半部分に一致する登録文字列を検索 Predictive Search : 入力文字列で始まる登録文字列を検索 といった操作が可能です。 今回は marisa-trie 0.2.4 をベースに コマンドラインプログラム Python バインディング から MARISA を触ってみます。  Install MARISA 環境は Amazon Linux とします。 まずはC++のプログラムビルドに必要なツール群をインストールします。 次に C++ プログラムのよくある手順でインストールします。 最後に Python バインディングをインストールします。 marisa-trie には SWIG ベースのバインディングもありますが、今回は pip ベースでインストールできるサードパーティーの

「ClubDB2 Watson：クイズ番組に挑戦した質問応答システム」に参加

過去に何度か参加したClub DB2 勉強会で IBM が開発した質疑応答システム”Watson” の開発話を聞けるということで、定時退職(少しフライング)して１９時前になんとか渋谷のIBMイノベーション・センターへ。 好奇心旺盛な参加者が30人程度?集まり、質問が活発に飛び交い、なかなか面白かった。(発表者との距離感が非常によかった) 機械学習・統計・分散処理・NLPのテッキーな解説も聞きたかった気もするが、それはまたどこかで。 次の3つの動画を見れば、参加した気分になれるはず。特にプロジェクトの中心人物による1つ目の解説がおすすめ。 案内の概要 https://www.ibm.com/developerworks/wikis/display/clubdb2/131 2011年2月、米国のクイズ番組において、IBMのコンピューターと人間のチャンピオンとの対戦が実現し、コンピューターが勝利をおさめました。これは、IBMリサーチ（基礎研究部門）の「グランド・チャレンジ」と呼ばれる、成功の保証が無いような技術的に難しい課題への取り組みの一環です。 この講演では対戦の模様の一部をご覧いただき、IBMリサーチが解決した技術的な課題、システムで採用された自然言語処理技術と情報源、そしてグランド・チャレンジの意義と、その成功の秘訣について解説します。 IBM基礎研究所について IBM は技術的に成功するかどうか分からない挑戦(グランド・チャレンジ)に過去に取り組んでおり、Kasparov を負かしたチェスコンピュータのの Deep Blue もこの一つ。 Watson はクイズ番組”Jeopardy!” で人間に勝利すべく開発された質問応答システム プロジェクトは2006年から開始され、5年後の2011年2月に Jeopardy! 最強の人間チャンピオン Ken Jennings と Brad Rutter に勝利を収めた。 世界に9つあるIBM基礎研究所のうちWatson（US)、Haifa(イスラエル）、China、Tokyo(日本）の4つの研究所が Watson の開発に参加。 スピーカーの金山氏は東京からは参加した2名のうちの1名、実質的に手足を動かしている唯一のメンバーであり、自然言語処理が専門。 Watson はIBMの創業者から名前を持ってきているのでかなり気合のはいったプロジェクト。 プロジェクトの参加メンバーは立候補制ではなく、研究員の得意分野によって選抜された。 USの研究所では、20数人の研究者が専属で従事 Jeopardy! について Jeopardy！(ジョパディ!)はアメリカで中断をはさみつつも50年近く続く人気クイズ番組で夕方に放送されている。(アメリカは退社時間が早い) 質問”What is shoe?”の答えが”4-letter word for the iron fitting on the hoof of