RMSE を Fold ごとに取ると全体の値より小さくなる証明
この記事を書く前に twitter でお話をしている流れで、まますさんに的確な証明を頂くことができました! 証明にはこちら RMSE.pdf - Google ドライブ からアクセスできます。(まますさんありがとうございましたmm)
そもそも
この記事のお題は RMSE を Fold ごとに取ると全体の値より小さくなる証明をやります ということです。
これをやろうと思ったきっかけは #かぐるーど での kaggle本の本読みです。 前回は第5章だったのですが、その5.2.2で次のような記述があります。
クロスバリデーションでモデルの汎化性能を評価する際は、通常は各foldにおけるスコアを平均して行いますが、それぞれのfoldの目的変数と予測値を集めてデータ全体で計算する方法もあります。なお、評価指標によっては各foldのスコアの平均と、データ全体で目的変数と予測値から計算したスコアが一致しません。例えば、MAEやloglossではそれらが一致しますが、RMSEでは各foldのスコアの平均はデータ全体で計 算するより低くなります。
要するに K-Fold それぞれの rmse 平均値と、データセット全体での rmse の値だとデータセット全体のほうが大きい (K Fold のほうが良いように見積もられてしまう) という話です。たしかに Root をとる操作を毎回やるのと、全体で合わせた後やるのだと前者のほうが小さい値になような感じはしますよね。
これ一般的に示せるかなーという議論があり、僕が「関数の凸性とイェンゼンの不等式でいけますよ」と言ったところじゃあやってほしい!と言われたのが当エントリの経緯になります。
せっかくなので簡単にですが凸関数とイェンゼンの不等式にも触れつつ、お話できればと思っています。
NOTE: 若干細かい定義域についてやイェンゼンの不等式の導出についてなどは省略していますので、それらは別途文献など見ていただけば幸いです。
凸関数とは
下準備として、凸関数というのを定義します。凸関数というのは色々な定義がありますが、以下を満たすような関数 $f: \mathbb{R} \to (-\infty,+\infty]$ のことです
$$ f(t x_1 + (1 - t)x_2) \leq t f(x_1) + (1-t) f(x_2) $$
ただし $x_1, x_2$ は任意の実数 $\mathbb{R}$ の点で $t$ には 0以上1以下の制約がついています。
要するに $x_1$ と $x_2$ の内分点での $f$ の値と最初に $f$ で計算してしまってから $f(x_1)$ と $f(x_2)$ の内分を取るのとだと、後者のほうが大きいような関数、って言うことです。
また $f$ が微分可能な場合 $f$ の二階微分 $f'' \geq 0$ であることと上記の等式は同値になります。
イェンゼンの不等式
これをちょっと発展させて内分点の部分を2つ以上の点に拡張したのがイェンゼンの不等式です。
イェンゼンの不等式は上記の式と同じく特定の関数 $f$ が凸関数である必要十分条件を表した式で, $f$が凸ならば任意の自然数 $n$ と$\sum_{i=1}^n p_i = 1, p_i \geq 0$ を満たすような $p_i$ に対して次の式
$$ f(p_1 x_1 + p_2 x_2 \cdots + p_n x_n) \leq p_1 f(x_1) + p_2 f(x_2) \cdots + p_n f(x_n) $$
がなりたつ、という定理です。
たとえば$n=2$の時を考えてもらうと先ほどの凸関数の定義そのままであることはすぐわかると思いますので、凸関数の定義を変数 $n$ 個の場合に拡張したようなイメージです。
RMSE を考える
RMSE とは入力とラベルの誤差の2乗和を $M$ とした時に
$$ {\rm RMSE}(M) = M^{\frac{1}{2}} $$
で計算される値です。これの二階微分を考えると
$$ {\rm RMSE}''(x) = - \frac{1}{4} M^{- \frac{3}{2}} < 0 $$
です。すなわちRMSEの二階微分は常に負の値となります。これは凸関数と全く正反対の性質で一般に凹関数 (concave) と呼ばれ先のイェンゼンの不等式とちょうど不等号が反対の不等式が成立します。
K-Foldしたときの RMSE
今Fold を$ K$ 個に分割して、それぞれが $n_k$ 個のデータを持っているとします。(データセット全体では $N$ 個とします。) この時各 Fold での MSE (Mean Squared Error) を $M_k$ とすると Fold ごとのデータの数で重みづけた ${\rm RMSE}_{\rm fold}$ は
$$ {\rm RMSE}_{\rm fold} = \sum_{k=1}^K \frac{n_k}{N} \sqrt{M_k} $$
となります。一方で通常の RMSE に関しては
$$ {\rm RMSE} = \sqrt{\frac{1}{N} \sum_{k=1}^K n_k M_k} = \sqrt{\sum_{k=1}^K \frac{n_k}{N} M_k} $$
となります。ここで $M_k$ に $n_k$ をかけているのは $M_k$ が既に Mean Squared Error なので要素の数を掛けて和にになおして全体の $N$ で割算をするためです。
ここで $p_k = n_k / N$, $f(x) = \sqrt{x}$ と考えると $f$ は凹関数でかつ $\sum p_k = 1$ ですのでイェンゼンの不等式が用いることが出来て
$$ {\rm RMSE} = \sqrt{\sum_{k=1}^K \frac{n_k}{N} M_k} \geq \sum_{k=1}^K \frac{n_k}{N} \sqrt{M_k} = {\rm RMSE}_{\rm fold} $$
が成立します。即ち fold ごとで RMSE を計算して重み付きの平均を取った値のほうが、データセット全体での RMSE の値より小さくなることがわかりました。
RMSE 以外でも…
上記の証明を追っていただくと分かるようにこの証明はロス関数の値がデータごとに計算できること、及びそれをデータセット全体の平均したあとに凹関数に代入する、という構造が保たれている限り同様の議論をすることが可能です。
ですので Log を取ってから Root を取る RMSLE (Root Mean Squared Log Error) なども同様の議論が可能です。
参考文献
以下は本記事を書くにあたって使用した凸関数に関する話題や凸最適化に関する日本語の参考文献です。
- wikipedia: 凸関数: 凸関数 - Wikipedia
- 非線形計画法: 山下 信雄
- 非線形最適化の基礎: 福島 雅夫
- 工学基礎 最適化とその応用: 矢部 博
この記事は kaggle その2 advent calendar 2019 の記事です。
