2007-12-13

局所的重み（TF）と大域的重み（IDF）

ﾔﾊﾞｽ

けっこう日数が経っちゃったので復習しますね（；＿；）

局所的重み

局所的重み $\normalsize l_{ij}$ は、文書 $\normalsize D_{j}$ に対する索引語 $\normalsize w_{i}$ の出現頻度 $\normalsize f_{ij}$ から計算されるのでした。

局所的重みだけでも4種類あるみたいデスね。

2進重み（binary weight）: 索引語が文書に出現するときに1。出現しなければ0になるというもの。
あんまり使われてないらしいです。
索引語頻度（term ferquency; TF）: 出現頻度 $\normalsize f_{ij}$ のこと。索引語が該当文書にいくつ出現するかという値です。
TF-IDFのTFですよ！
対数化索引語頻度（logarithmic term ferquency）: 出現頻度の高い索引語が極端に大きい重みを持たないようにするために対数を使います。

　 $\Large l_{ij}=log(1+f_{ij})$
拡大正規化索引語頻度（augmented normalized term ferquency）: 該当文書中でいちばん出現頻度の高い索引語の頻度を使って索引語頻度 $\normalsize f_{ij}$ を正規化する方法。

　索引語が文書に出現するとき、

　　 $\Large l_{ij}=0.5+0.5\frac{f_{ij}}{\text{max}f_{kj}}$

　索引語が文書に出現しないとき、

　　 $\Large l_{ij}=0$

むー（￣〜￣；）？？
下のほうに行くほど精度が高いのかなあ。。
あとで計算してみます＞＜

大域的重み

大域的重み $\normalsize g_{i}$ は、文書集合全体にわたる索引語 $\normalsize w_{i}$ の出現頻度の偏りを使って計算される重みで、多くの文書で出現する索引語は低い重みを、特定の文書のみに偏って出現する索引語に高い重みを与えるというものでした。

文書による索引語の偏りを表すのに、文書頻度（document frequency）っていうのを使うみたいです。
これは、索引語 $\normalsize w_{i}$ を含む文書数のことで、 $\normalsize n_{i}$ という記号で表現するみたい。

大域的重みは3種類あるみたいデスね。

文書頻度の逆数（inverse document ferquency; IDF）: 逆数にすることで、（頻度が）多い→（重みが）低い/（頻度が）少ない→（重みが）高いを再現するのですね！

　　 $\Large g_{i}=log\frac{n}{n_{i}}$

ちなみに $\normalsize n$ は、すべての文書数のことで、対数化しているのは、IDFの値の変化を少なくするためだそうです。。数式を見ただけでは理解できないお＞＜
確率的IDF（probabilistic IDF）: これは、文書集合の半数以上の文書に含まれる索引語に対しては不の値をとるようにしたIDFってことみたいだけど。。

　　 $\Large g_{i}=log\frac{n-n_{i}}{n_{i}}$

数式を見ただけでは理解できないお＞＜
大域的頻度IDF（grobal ferquency IDF）: 文書集合を通しての索引語の頻度（大域的頻度）と文書頻度とを組み合わせた方法。索引語 $\normalsize w_{i}$ の大域的頻度を $\normalsize F_{i}$ とするとき、大域的頻度IDFの定義はこうなるらしいです。

　　 $\Large g_{i}=log\frac{F_{i}}{n_{i}}$

索引語の文書頻度 $\normalsize n$ 小さく、大域的頻度 $\normalsize F_{i}$ が大きいほど大きな重みになります。。(￣~￣；) ウーン

普段使わない用語が連発して、イメージするのが難しくなってきました。。（Ｔ＿Ｔ）

次回、実際になにかのデータを使って計算してみようと思います！

2007-12-10

索引語の抽出と重み付け

これから本質に入っていく予感がしてドキドキです

今日は先に感想を書いちゃいます。
索引語の抽出方法として、形態素解析とNグラムインデクシングがあって、重み付けの方法として、TF-IDFがあるということはなんとなく知っていたんですが、そのなんとなくがはっきりして、たいへんすっきりです！

ヾ（＞▽＜）ゞ

そもそも索引語って

文書の内容を特徴付ける上で重要な単語のこと。
これを文書の中から抽出する処理をインデクシングという。

うむ。

索引語を抽出するぞ

文書から索引語を抜き出すメジャーな方法は2つ。このへんはさくっと流します。

形態素解析: 文書を品詞分解する。
仕組みはまったくわかりませんが、かなり完成された技術なので、すでにあるものを素直に使うんでいいみたい。
Nグラムインデクシング: N文字単位で索引語を抽出する。
経験的に2グラムと3グラムが定番で、1グラムは意味がない気がします。

形態素解析	庭/に/は/二/羽/ニワトリ/が
2グラム	庭に/には/は二/二羽/羽ニ/ニワ/ワト/トリ/リが
3グラム	庭には/には二/は二羽/二羽ニ/羽ニワ/ニワト/ワトリ/トリが
1グラム	庭/に/は/二/羽/ニ/ワ/ト/リ/が

ちなみに自分は基本的に形態素解析派ですが、部分一致のような意味のない区切りで適合させたいようなときはNグラムというふうに使い分けていたこともありました。

不要語は索引語にしない

形態素解析とNグラムインデクシングで索引語が抽出できたけど、日本語の助詞（「は」とか「が」）とかはたいていどの文書にも頻繁に出てて、これらをいちいち索引語にしちゃうと、こういう単語で検索した場合にほとんどの文書が適合してしまう。
これでは困るので、これらの単語を不要語として索引語にしないようにしたいです。
形態素解析を使うと品詞情報が取れるので、名詞以外は使わないとか、不要語辞書を用意しておいて、そこにある単語を弾くという方法が一般的みたい。

単語の種類でちょっと興味があったのでメモしておきますね。

内容語（content word）: それ自体で意味を持った、ある特定の概念を表している単語のこと。
名詞とか動詞が該当する。
機能語（function word）: 単語と単語の間を関係を表している単語のこと。
助詞とか助動詞、英語だと冠詞、前置詞が該当する。

機能語は不要語になる場合が多い。
内容語でも「する」「ある」みたいな動詞とか、「それ」「これ」みたいな代名詞は不要語候補。

索引語につける重み付けを決める指標は3種類ある

索引語に重みをつけて、検索結果をランキングしたりするわけです。
$\normalsize n$ 個の文書 $\normalsize D_{1}, D_{2}, ..., D_{n}$ があって、これらの文書集合から全部で $\normalsize m$ 個の索引語 $\normalsize w_{1}, w_{2}, ..., w_{n}$ が抽出されたとき、索引語 $\normalsize w_{i}$ の文書 $\normalsize D_{j}$ における重み $\normalsize d_{ij}$ は、以下の3つの指標で決めることができるみたい。

局所的重み（local weight） [tex: \normalsize l_{ij}]:索引語 $\normalsize w_{i}$ の文書 $\normalsize D_{j}$ における再現頻度に基づいて計算される重み。再現率向上を目的としていて、文書中に頻繁に出現する索引語に対して大きな値が与えられる。
自分の言葉で翻訳すると、ひとつの文書の中である索引語がどれくらいの割合で出てくるかどうかを数値化する。。？ヾ(;´▽｀A``
大域的重み（global weight） [tex: \normalsize g_{i}]:文書集合全体にわたる索引語 $\normalsize w_{i}$ の分布を考慮して決定される重み。適合率向上を目的としていて、特定の文書に集中して出現する索引語に対して大きな値が与えられる。
自分の言葉で翻訳すると、文書全体で頻出している索引語が、ひとつの文書どれくらい密集しているのかを数値化する。。？ヾ(;´▽｀A``
文書正規化係数（document normalization factor） [tex: \normalsize n_{j}]:文書が長くなると、含まれる単語の数も増えるので、長い文書から抽出された索引語ほど重みが大きくなる。
これを補正する目的で導入する値のこと。

これら3つの指標から、下記の式によって索引語の重み $\normalsiz d_{j}$ が決定されるみたい。
　 $\Large d_{j}=\frac{l_{ij}g_{i}}{n_{j}}$

ここから、TF-IDFといわれているものが実はこの式で表される重み付けのひとつにすぎないというドラマチックな展開になるんだけど、ここまで書いた時点で眠くなっちゃったので、明日続きを書きます。。

ε=ε=ε=└|∵|┐

2007-12-05

他の評価尺度とかテスト・コレクションとか

$\normalsize R$ 適合率

全文書のうち、検索質問に適合する文書の総数を $\normalsize R$ としたときに、検索結果の上位から $\normalsize R$ 番目を出力した時点での適合率。
→ 上位にランキングされた検索結果の有用性がわかるみたい。

昨日の例だと、 $\normalsize R$ 適合率は4位の時点での適合率になるから、0.75。

$\normalsize F$ 尺度

再現率 $\normalsize R$ と適合率 $\normalsize P$ の調和平均のこと。

調和平均というのは「逆数の平均値の逆数」・・・ってことらしいけど（￣〜￣；）？？
式で書くと、こういうことみたい。

　 $\Large Hm=\frac{n}{\sum_{i=1}^{n}\frac{1}{X_i}}$

話がそれたけど、つまり $\normalsize F$ 尺度とはこういうこと。

　 $\Large F=\frac{2}{\frac{1}{\normalsize R}+\frac{1}{\normalsize P}}$

→ $\normalsize R$ と $\normalsize P$ が大きくなるほど $\normalsize F$ 尺度も大きくなるので、この値が大きいほど精度がいいってことみたい。

昨日の例を使って $\normalsize F$ 尺度を計算してみます。

表示件数	適合性	再現率	適合率	$\normalsize F$ 尺度
1	○	0.25	1.00	0.40
2	○	0.50	1.00	0.67
3	×	0.50	0.67	0.57
4	○	0.75	0.75	0.75
5	○	1.00	0.80	0.89
6	×	1.00	0.67	0.80
7	×	1.00	0.57	0.73
8	×	1.00	0.50	0.67
9	×	1.00	0.44	0.61
10	×	1.00	0.40	0.57

なるほど。
この場合、5位まで表示するのがいちばん精度がいいというわけですね！
これは興味深い（・∀・）

けど、なんで普通に平均じゃだめなのかなぁ？？？

$\normalsize E$ 尺度

$\normalsize F$ 尺度は、再現率と適合率を同じ比重で考えたけど、この比重を調整できる尺度が $\normalsize E$ 尺度。
$\normalsize b$ を再現率と適合率の比重を表すパラメータとしたとき、 $\normalsize E$ 尺度の定義はコレ。

　 $\Large E=1-\frac{1+b^2}{\frac{b^2}{\normalsize R}+\frac{1}{\normalsize P}}$

$b=1$ のとき: 再現率と適合率は同程度に重要。
$b>1$ のとき: 再現率よりも適合率を重視。
$b<1$ のとき: 適合率よりも再現率を重視。

うお。。＼（−"−）／
これで評価の幅は広がったけど、使いこなすのが大変そうだあ（Ｔ＿Ｔ）

テスト・コレクション

検索システムの評価用データのことで、以下の項目が与えられてるらしいです。

集合文書: 検索対象となる文書の集合。
検索質問集合: 検索質問文の集合。検索キーワードとか、クエリとか呼ばれてるやつデスね。
適合情報: 検索質問集合の書く検索質問文に対して、文書集合中のどれが適合していて、どれが適合していないかという情報。

これを元に検索システムを評価したり比較したりするみたいです。
日本語のテスト・コレクションもあって、BMIR-J1とか、BMIR-J2とか、NTCIRっていうのが有名みたい。

これって、一般ぴーぷるでは入手できないのかなぁ（・＿・？）

2007-12-04

再現率と適合率の続き

具体的に計算してみた

たとえば、こんな感じの検索結果を考えます。

検索結果は全部で10件。
そのうち、適合文書は4個。
それぞれの文書にランクがついていて、それで表示順を決めている。
適合文書は、1位, 2位, 4位, 5位に登場する。

ランク	1	2	3	4	5	6	7	8	9	10
適合性	○	○	×	○	○	×	×	×	×	×

適合性っていうのは、その文章が適合文書かどうかっていう判定で、検索された文書の内容が検索質問に対してマッチしてれば○、ちょっと違うなーっていうのが×。
ホントはテスト・コレクションを持ってきて、そこで決められているものを使うんだけど、今回は練習用に勝手に決めますた。

このとき、
再現率 = 検索された文書中の適合文書の数/全文書中の適合文書の数だから、
4/　4 = 1.00

適合率 = 検索された文書中の適合文書の数/検索された文書の数だから、
4/10 = 0.40
になる。

検索結果を何件表示するかによって、再現率、適合率が変わるよ

気をつけないといけないのは、上のはあくまで検索結果を10件全部表示した場合。
検索結果の表示件数を1〜10件でにした場合、再現率、適合率はこんな感じで変わる。

表示件数	適合性	再現率	適合率
1	○	1/ 4 = 0.25	1/ 1 = 1.00
2	○	2/ 4 = 0.50	2/ 2 = 1.00
3	×	2/ 4 = 0.50	2/ 3 = 0.67
4	○	3/ 4 = 0.75	3/ 4 = 0.75
5	○	4/ 4 = 1.00	4/ 5 = 0.80
6	×	4/ 4 = 1.00	4/ 6 = 0.67
7	×	4/ 4 = 1.00	4/ 7 = 0.57
8	×	4/ 4 = 1.00	4/ 8 = 0.50
9	×	4/ 4 = 1.00	4/ 9 = 0.44
10	×	4/ 4 = 1.00	4/10 = 0.40

わーい、できたよ＼(￣▽￣)／

平均適合率

適合文書が検索された時点での適合率の平均値

この値を使って、再現率と適合率を総合的な観点から評価するみたい。

上の例だと、
(1.00 + 1.00 + 0.75 + 0.80) / 4 = 0.89

n点平均適合率

あらかじめ決められたn個の再現率レベルでの適合率の平均値

これも再現率と適合率を総合的な観点から評価ための尺度。

(ｏ･ω･ｏ）？ﾎｴ

再現率を基準にして、それに対応する適合率を計算して、その平均を出す感じ？？？
再現率レベル 0.0, 0.1, 0.2, ..., 1.0 の11点平均適合率ってのがメジャーみたい。

補間適合率を使って再現率に対応する適合率を求める

補間適合率っていうのは、再現率レベル $\normalsize x$ 以上の適合率のうちの最大値のことみたい。

上の結果の場合、こういうことになるみたい。
う、うまく説明できない。・°°・(>_<)・°°・。

再現率	補間適合率
0.0	1.00
0.1	1.00
0.2	1.00
0.3	1.00
0.4	1.00
0.5	1.00
0.6	0.75
0.7	0.75
0.8	0.80
0.9	0.80
1.0	0.80

で、各再現率レベルの補間適合率の平均を出すので、
(1.00 + 1.00 + ... + 0.80) / 11 = 0.9

平均適合率とだいたい同じくなればいい・・・の？？

これを数式で書く。
11点平均適合率 $\normalsize\tilde P$ は、補間適合率 $\normalsize P(i)$ を用いて、次のように表すことができる。。らしい。

$\Large\tilde P=\frac{1}{11}\sum_{i=0}^{10}P(\frac{i}{10})$

(￣~￣；) ウーン

数式がすらすら読めるようになりたいお＞＜

2007-12-03

再現率と適合率

検索結果の評価尺度？

いくつかの文書があって、その中から検索した結果の良し悪しを判断するのに使うみたい。

再現率: 検索対象となる文書集合の中の検索質問に適合する文書のうち、実際に検索された文書の割合
→ 検索質問に適合する文書を漏れなく検索しているかどうか（完全性）がわかる。
適合率: 検索された文書集合の中で、検索質問に適合する文書の割合
→ 検索質問に適合する文書だけを検索しているかどうか（正確性）がわかる。