« 読了: Carbone & Gorr (1985) 時系列予測ってフリーハンドでいいんじゃね？→よくなかった | メイン | 読了：Kuhn (2008) R の caret パッケージ »
2015年4月27日 (月)
Kohavi, R. (1995) A study of cross-validation and bootstrap for accuracy estimation and model selection. IJCAI'95 Proceedings of the 14th international joint conference on Artificial intelligence. 1137-1143.
勤務先の仕事で予測モデルの正確性の評価についてお話していて、自分でもちょっぴり混乱するというか、一瞬言葉に詰まる場面があった。ちゃんと勉強しとかなきゃな、と思って目を通した。学会のproceedingsなんだけど、google scholar上の引用回数が4000を超えている。
原文は工学者っぽくきちんと書いてあるんだけど、簡略にメモ。
データから分類器を構築いたしました。その分類器の正確性 accuracy を評価したいです。どうやって評価するか。
えーと、ある事例$v_i$が持つラベルを$y_i$とする。データセット$D$(サイズ$n$)から構築した分類器が事例$v$に与えたラベルを $I(D, v)$と表す。関数$\delta(i,j)$を、値$i$と$j$が一致しているときに1, そうでないときに0である関数とする。話を簡単にするために、コストは正分類で0, 誤分類で1とする。
ひとつめ、ホールドアウト法。test sample estimationともいう。
データを相互排他な2つのサブセットに分ける。ひとつは訓練セットで、サイズは2/3とすることが多い。残りはテストセット(ホールドアウトセットともいう)。で、訓練セット$D_t$から分類器を構築し、ホールドアウトセット$D_h$(サイズ$h$)における正分類率を正確性の推定量とする。ふむふむ。せっかくなので式もメモしておくと
$acc_h = (1/h) \sum_{\langle v_i, y_i \rangle \in D_h} \delta(I(D_t, v_i), y_i)$
分類器構築は事例が多いほうが正確だとみなすなら、これはテストセットが大きいほど悲観的バイアスがかかる推定量である。しかしテストセットを小さくすると信頼区間が広くなる。要するに、ホールドアウト法はあんまし上手いやりかたじゃない。
なお、ホールドアウト法を $k$ 回繰り返して$acc_h$を平均するという手もある(ランダム・サブサンプリング)。しかし、有限なデータセットを相互排反に分割している限り、ある訓練セットでたまたま多かったラベルはそのときのテストセットでは少ないわけで、$acc_h$は過小評価されてしまう[←あっ、そうか...！]。
ふたつめ、cross-validation。[交差検証、交差確認、交差妥当化、いろんな訳語がありそうだ。どれが一番メジャーなのかなあ。以下ではCVと略記する]
まずは k-fold CV。$D$を$k$個のだいたい同じサイズの相互排他なサブセットに分割する。で、1個目, 2個目, ... を取り除きながら、残りのすべてを用いて分類器を構築し、取り除いたサブセットを分類する。で、$k$回を通じた正分類数をデータサイズで割る。ふむふむ。
えーと、事例 $\langle v_i, y_i \rangle$が属しているサブセット以外のすべてからなるデータセットを$D \backslash D_{(i)}$と書くことにして、
$acc_{CV} = (1/n) \sum_{\langle v_i, y_i \rangle \in D} \delta(I(D \backslash D_{(i)}, v_i), y_i)$
CVには他にもいろんなバージョンがある。分割の仕方を変えながら繰り返すとか、分割するときに層別するとか。各事例についてそれだけを取り出すという分割を行うのがご存知 leave-one-outである [原文にはleave-one-oneと書いてあるけど... なに、その犬みたいな名前...]。
データを一部取り除くことでデータは揺れるわけだけど、この揺れの下で分類器が安定しているのであれば、CV推定値は不偏だし、その分散は$acc_{CV} \times (1-acc_{CV})/n$となる。実際には、複雑な分類器生成手法は学習能力の上限に達しておらず、揺れに弱いかもしれない。foldの数が多いほうが安定性は高いと期待できる。さらにいえば、foldの数を動かしても分類器が安定しているならば、推定値の分散も変わらないといえる。
CVには次のような問題点がある。たとえばFisherのアヤメデータは3クラス, 各50ケース。当たるも八卦的な分類器構築メカニズムがあるとして、いま分類器の正確性をleave-one-outで推定すると、leaveされた一事例は常に少数派となり、どの分類器でも常にleaveされた事例以外の2クラスを予測値とする分類器となり、よってleaveされた事例は常に誤分類され、正確性は0, その分散は0となる。しかし分類器が安定しているわけではない。[←なるほどね...]
みっつめ、ブートストラップ。データから同サイズのデータを復元抽出する。
ある個体がある抽出で選ばれない確率は$(1-1/n)^n$, これは約0.368である。つまり選ばれる個体数の期待値は0.632nとなる。抽出された奴らを訓練セット、されなかった奴らをテストセットとする。で、訓練セットでの正確性を$acc_s$, テストセットでの正確性を$\epsilon 0_i$として
$acc_{boot} = (1/b) \sum_{i=1}^b (0.632 \epsilon 0_i + 0.368 acc_s)$
[あれれ？ ここ、誤解しているかも... きちんと勉強しないと...]
ブートストラップにも問題点がある。分類器が完全なmemorizerで(枝刈りなしの決定木みたいなの)、データセットが完全にランダムで、2クラスだとしよう。どのブートストラップ標本でも、$acc_s$は1, $\epsilon 0$は0.5だ。ってことは$acc_{boot}$は0.68になる。ほんとは0.5なのに。このように、memorizer搭載の分類器生成メカニズムでは正確さの推定にバイアスが生じる。
後半は実験。データセットは7つ。決定木(C4.5)とナイーブ・ベイズ分類器を使う。hold-outでの正分類率を正として比較する。
結果。まずバイアスをみると、k-fold CVによる正確性推定値は k が小さいときに悲観的。ブートストラップはデータセットによって楽観的になることがある。
分散もあわせてみると、結局 kを10くらいにした k-hold CVがオススメである由。また分割の際に層別すると成績が良く成る由。へぇー。
実験結果も面白いけど、それより前半の概観が頭の整理になった。そうか、分類器生成メカニズム(この論文でいう Inducer)の性能と分類器の性能をきちんとわけて考えないと混乱するわけだ。勉強になりました。
論文：データ解析(2015-) - 読了：Kohavi(1995) 分類器の正確性の指標を比較する (ホールドアウト, CV, ブートストラップ)