こんにちは，株式会社Ridge-iリサーチチームの@machinery81です． 今回はK-fold Cross Validationの理論的側面を紹介したいと思います． なお本記事は@zawatsky_rによってレビューされています．
本記事の内容は以下のスライドに基づいています：
TL;DR
- K-fold Cross Validationは単一のHold-Outに対して汎化バウンドの意味で優越することを紹介
はじめに
みなさん，今日もCross Validationしていますか？ Cross Validationはモデルの性能を評価するための非常に強力なフレームワークの一つで，機械学習の分野に携わる方であれば一度は耳にしたことがあると思います．日本語では交差検証やクロスバリデーションなどと表記されることも多いと思います．
そんなCross Validationは単一のHold-Out Validationと比べて「手元の学習データをフル活用できて良さそう」といった直感的な理解がされる場合が多いと思います．そこで今回は，K-fold Cross Validationが単一のHold-Out Validationに対して理論的にも優位性がある，というお話をしていこうと思います．
Hold-Out ValidationとCross Validation
Hold-Out Validationは，与えられたデータセットを学習用と評価用に分けておき，学習用データで得られたモデルの性能を評価用データで測るというものです． 基本的な仮説としては，未知のテストデータにおけるモデルの性能は，このとき取り分けておいた評価用データでの性能と相関があるだろうというものです． そして実際，データの従う分布がi.i.d.であるときは概ねその通りに振る舞ってくれます．
「きちんとvalidationデータを用意してモデルの性能評価をして，モデルが過学習していないことを確かめよう」と口を酸っぱくして言われた経験がある方も多いのではないでしょうか？
ところで，このようにデータセットを学習用と評価用に分けると，評価用のデータが学習に使えなくてもったいないのではないかと感じるかもしれません． そこで広く活用されているのが，次に紹介するK-fold Cross Validationです． K-fold Cross Validationでは，まずはじめに与えられたデータセットをK分割します．その後，分割したデータのうちの1セットを評価用に，それ以外を学習用に用いてモデルを学習・評価する，という操作をK回繰り返します．
単一のHold-Out Validationと比べて，K回の学習・評価が発生する分計算時間がかかってしまいますが，それが許容できるのであればより良いモデルが獲得できるだろうという仮説に基づいたフレームワークです．
直感的には，K-fold Cross Validationの方がより正確にモデルの性能を見積れそうに思います． このような予想を裏付ける理論的な結果が報告されており，今回はそのうちの一部を紹介します [Blum et al., 1999]．
K-fold Cross Validationの理論的優位性
準備とゴール
まずはじめに，「K-fold Cross Validationの方がHold-Out Validationよりも正確にモデルの性能を見積もれる」とはどういう状態かを確認しておきます．
モデルの手元の評価データにおける経験誤差を，テストデータで達成されるであろう期待誤差
とすると， ある
について
が小さければ，手元の評価データでの性能が未知のテストデータでの性能をよく再現できていると言えそうです． そこで，
- 単一のHold-Out Validationの経験誤差
- 単一のHold-Out Validationの期待誤差
- K-fold Cross Validationの経験誤差
- K-fold Cross Validationの期待誤差
とすると，証明したいのは
となりそうです．
K-fold Cross ValidationはHold-Out Validationと少なくとも同等
まずはじめに，K-fold Cross ValidationがHold-Out Validationと少なくとも同等であることを主張する以下の定理を紹介します．
定理．あるについて，以下が成り立つ．
証明． Jensenの不等式から，すべての凸関数と実数
について
が成り立つ．は
で凸関数なので，
期待値の線形性から，
となり，定理の証明を得る．□
示したかった式と非常に似ていますが，不等式の部分にがついています．
この不等式から，K-fold Cross Validationで見積もられる誤差は，Hold-Out Validationのものと少なくとも同等以上に良いものだということが言えます．
K-fold Cross ValidationはHold-Out Validationに対して厳密に優越
できれば，K-fold Cross Validationが厳密にHold-Out Validationより優れていると言いたいところです． これを主張するのが次の定理です；
定理．入力データの空間が有限，アルゴリズムが学習データの順序に不変，とする．このとき，
とある
について以下が成り立つ：
証明のスケッチ．
Jensenの不等式において等式が成り立つのは，で
が等しいときに限る．
つまり，
となるような
を1組でも見つければ証明は完了する．ここで仮定した順序不変性や
が効いて，定理が証明される．
仮定の一つ目のは，Hold-Out Validationがいつも完璧であるとは限らないということを要請していると捉えることができます．
そこで，K-fold Cross Validationにおいて各foldごとに出てくる誤差が異なれば，それを平均したK-fold Cross Validationの方がよりよい推定量を与えるという解釈ができます．
数値実験
数値実験でも，Hold-Out ValidationとK-fold Cross Validationの差を確かめてみます． RBFカーネルのSVMをdigitsデータセットについて学習／評価した結果を示します．
縦軸は経験誤差と期待誤差の離れ度合い，横軸はKで，Hold-Out／Cross Validationそれぞれで評価セットのサイズはN/Kになります．
図示した結果から，K-fold Cross Validationによってより精密に期待誤差を見積もることができていることが観測できます．
さいごに
Ridge-iでは様々なポジションで積極採用中です． カジュアル面談も可能ですので，ご興味がある方は是非ご連絡ください．
参考文献
- Avrim Blum, Adam Kalai, and John Langford. Beating the hold-out: Bounds for k-foldand progressive cross-validation. InProceedings of the twelfth annual conference on Computational learning theory, pages 203–208, 1999.
- Michael Kearns and Dana Ron. Algorithmic stability and sanity-check bounds forleave-one-out cross-validation.Neural computation, 11(6):1427–1453, 1999
- Anthony, Martin, and Sean B. Holden. "Cross-validation for binary classification by real-valued functions: theoretical analysis." Proceedings of the eleventh annual conference on Computational learning theory. 1998.
