情報検索の指標：適合率（精度）、再現率、平均適合率について

情報検索の指標をまとめる。

KDD Cup2012 Track1のEvaluationのページにpdfへのリンクがあった。
http://www.kddcup2012.org/c/kddcup2012-track1/details/Evaluation
これはわかりやすい。
http://sas.uwaterloo.ca/stats_navigation/techreports/04WorkingPapers/2004-09.pdf

(図の出典：Recall, Precision and Average Precision ,Mu Zhu, Working Paper 2004-09, Department of Statistics & Actuarial Science, University of Waterloo, http://sas.uwaterloo.ca/stats_navigation/techreports/04WorkingPapers/2004-09.pdf)

適合率Precision（精度ともいう）は、h(t)/π　のこと。
再現率Recallは、h(t)/t　のこと。

途中まで線形に増加し、その後飽和するのが最良のアルゴリズム。
傾き１の直線はランダムなアルゴリズム。

PrecisionとRecallにはトレードオフがある、とはWikipediaにも書いてあるけど、
数学的な説明は載ってなかった。
この論文にはちゃんと説明してあったので一読をおすすめします。
簡単に言うとrとpが媒介変数tでつながっており、
Bayesの定理を使って式変形すると
rの一階微分r'(t)>0かつpの一階微分p'(t)<0が言えるので
トレードオフがあるという結論になる。

あと解釈が難しいのが平均適合率。
これについてはほとんど物理的な意味はなく、数式上の定義である。
いずれにせよ結果は意図する所をうまく表しているのが面白い。

平均適合率の定義は、
$\frac{1}{1-0} \int_0^1 p(r)dr = \int_0^1 p(r)dr$
これはtで置換積分できる。
$\int_0^1 p(r)dr = \int_0^1 p(r)r'dt = \int_0^1 \frac{\pi r r'}{t} dt$

計算上のアルゴリズムとして、差分型を用いる。
$\int_0^1 p(r)dr = \sum_i p(r)\Delta r$

実際の計算は表を用いて考えると分かる。

ここで�rがずっと固定値なのは、離散なので再現率ｒは
(ヒット数h) / (正解文書の数π)となり、
ヒット数が１増えるときの再現率の増分�ｒは
�ｒ＝（さっきのヒット数＋１: h(t+1)）/（正解文書の数π）ー　（さっきのヒット数: h(t)）
　＝1 / π　
つまり、
$AP = \sum_t p(t) \Delta r = \frac{1}{\pi} \sum_t p(t)$