こんにちは，株式会社Ridge-iリサーチチームの@machinery81です．今回は有名なオッカムの剃刀の概念と，この原則に基づいた汎化誤差解析の最もシンプルな例を紹介したいと思います．

本記事の内容は以下のスライドに基づいています：

TL;DR
オッカムの剃刀
Occam Bound
- Occam Boundの証明
Occam Boundのベイズ的解釈
さいごに
- 参考文献

TL;DR

オッカムの剃刀の概念について説明；
オッカムの剃刀の形式化と汎化誤差解析への応用について説明．

オッカムの剃刀

必要が無いなら多くのものを定立してはならない．少数の論理でよい場合は多数の論理を定立してはならない [1]．

ja.wikipedia.org

みなさんはオッカムの剃刀を知っていますか？オッカムの剃刀は議論の際に必要以上に多くの仮定をおいてはならないという原則で，その主張のシンプルさとキャッチーさから非常に多くの文脈で引用されることが多い概念です．ある事柄を説明する際に必要十分な仮定のみを考慮すべきというのは確かに様々な場面で重要で，非常に示唆に富んでいると思います．

ところで，統計学及び機械学習の分野でもオッカムの剃刀の考え方は有用であるとされています．つまり，

ある二つの理論が同程度にデータを説明できているとき，より単純な方が好まれる；
統計的機械学習においてモデルの単純さは直感的にだけでなく定量的に測れる；

という2点に基づいて，モデルの良し悪しを評価するフレームワークを考えることができます．これは，例えば2つのモデルAとBがあったとき，もしAとBの手元のデータへの精度が同等であってAの方がBよりも何らかの意味で単純であるならば，Aのモデルを採用した方がいいであろうといった具合です．

ちなみに近年のニューラルネットワークの発展においては，必ずしもこの原則に則らないことも多くなってきたようです．これはover parametrizationやdeep double descentといったキーワードが該当します．

こうした最新の実験的結果との矛盾についての議論も非常に有意義ですが，ひとまず本記事ではオッカムの剃刀の考えに基づく最もシンプルな結果を紹介し，モデルの汎化誤差を議論するイントロダクションとしての立場を取ることにします．特に，学習データへのモデルの損失と未知のデータへのモデルの損失のズレがどのような変数に依存しているのかに注目してみてください．

Occam Bound

定理． 独立かつ同一なサンプルサイズ $m$ のデータセット $\mathcal{S}=\{x, y\}$ とある仮説 $h\in\mathcal{H}$ について少なくとも $1-\delta$ の確率で以下が成り立つ：

$\mathcal{L}(h) \leq \hat{\mathcal{L}}(h) + \sqrt{\frac{(\ln 2)|h| + \ln\frac{1}{\delta}}{2m}}.$

ただし， $|h|$ は仮説 $h$ を記述するのに必要なbit数であり

$\mathcal{L}(h) = \mathbb{E}\Big[1[h(x)\neq y] \Big],$

かつ

$\hat{\mathcal{L}}(h) = \frac{1}{m}\sum^m_{i=1}1[h(x_i) \neq y_i].$

$\mathcal{L}(h)$ はモデル $h$ の未知のデータに対する期待誤差であり， $\hat{\mathcal{L}}(h)$ はモデル $h$ の手元のデータに対する経験誤差に当たります．機械学習の分野でよく引き合いに出される概念として，手元のデータへの損失は小さい一方で未知のデータへの損失が大きくなってしまう過学習（over fitting）があります．これは経験誤差と期待誤差の乖離に起因するため，裏を返すと経験誤差と期待誤差が十分近いことが望ましいとも言えます．

f:id:Ridge-i_Jinguuji:20210831185144p:plain — Photo by https://medium.com/swlh/machine-learning-how-to-prevent-overfitting-fdf759cc00a9

上記の定理は不等式の形で定式化されており，これは，「期待誤差はたかだか経験誤差 + 第二項で抑えられる」ことを意味します．ところで第二項は以下の三つの変数に依存しています：

モデルを記述するのに必要なbit数 $|h|$
学習データのサンプルサイズ $m$
不等式が成り立つ確率を決める正値 $\delta$

ちなみに，Occam Boundは汎化誤差に関する不等式の非常に初歩的なもののうちの一つですが，これよりも優れた不等式であっても似たような形をしていることが多いです [2]．

さて，第二項が依存している変数のうち特に重要なものが $|h|$ と $m$ です． $m$ は学習データのサンプルサイズに該当するので，たくさんの学習データを収集すればこの値が増えることになります．上記の不等式の右辺第二項において，サンプルサイズ $m$ は分母に位置していることから，サンプルサイズを増やすことでOccam Boundの右辺第二項は小さくなることがわかります．これは，学習データのサンプルサイズを増やすことで経験誤差と期待誤差の乖離が小さくなることを意味しています．たくさん学習データがあれば未知のデータにも正しく予測できそう，ということですね．過学習という現象を説明する際に原因としてあげられることの一つに学習データの不足があることからも，この結果は非常に直感に合うのではないでしょうか．

一方 $|h|$ はモデルを記述するのに必要なbit数を表しているので，この値が大きいほどモデルは複雑であると言えそうです． $|h|$ はOccam Boundの右辺第二項の分子に位置しているので， $|h|$ が小さいほどOccam Boundの右辺第二項も小さくなることがわかります．つまり，シンプルなモデルであるほど経験誤差と期待誤差の乖離が小さくなることを意味します．これはまさにオッカムの剃刀が示唆する，「ある二つの理論が同程度にデータを説明できているとき，より単純な方が好まれる」という主張の形式的な記述になっています．

Occam Boundの証明

Proof.

定理に矛盾する仮説集合を $\mathcal{B}$ とする：

$\mathcal{B}= \Biggl\{\mathcal{L}(h) \geq \hat{\mathcal{L}}(h) + \sqrt{\frac{(\ln 2)|h| + \ln\frac{1}{\delta}}{2m}}\ ;\ h\in\mathcal{H} \Biggr\}$

このとき，

$P\Big[h\in\mathcal{B}\Big] \leq \sum_{h\in\mathcal{H}} \exp\Biggl\{-2m \Biggl(\sqrt{\frac{(\ln 2)|h| + \ln\frac{1}{\delta}}{2m}}\Biggr)^2\Biggr\} \quad (\because \text{Chernoff bound}) \\ \quad\quad\quad\ = \sum_{h\in\mathcal{H}}\delta 2^{-|h|} \\ \quad\quad\quad\ = \delta\sum_{h\in\mathcal{H}}2^{-|h|} \\ \quad\quad\quad\ \leq \delta. \quad (\because \text{Kraft inequality})$

Occam Boundのベイズ的解釈

最後にOccam Boundの簡単な変形を考えてみます． $P$ を $h$ に関する確率分布とし， $|h|_P$ を以下のように定義します：

$|h|_P = \log_2\frac{1}{P(h)}.$

このとき，Occam boundは次のような書き換えができることが証明できます：

$\mathcal{L}(h) \leq \hat{\mathcal{L}}(h) + \sqrt{\frac{(\ln 2)|h|_P + \ln\frac{1}{\delta}}{2m}}.$

これはまさしく仮説集合に関する任意の事前分布を考えた場合のOccam boundに相当しており，モデルの複雑度を確率分布を用いて表現していると言えます． Occam Boundは導出と形のシンプルさから汎化誤差を考える最初のステップとして大事ではありますが，実用的には不等式の緩さなどの問題があります．本記事では紹介しませんが，このような仮説集合の事前分布を考えるというアイディアに基づいて，よりタイトな不等式を考えることもできます（e.g. PAC-Bayes [3]）．汎化誤差に関する不等式の評価に興味を持った方は調べてみてください．

さいごに

Ridge-iでは様々なポジションで積極採用中です．カジュアル面談も可能ですので，ご興味がある方は是非ご連絡ください．

ridge-i.com

参考文献

[1] Nicolas Drouhin. Pluralitas non est ponenda sine neccesitate. Technical report, GRID Working paper, 2006.
[2] Langford, John, and Robert Schapire. "Tutorial on Practical Prediction Theory for Classification." Journal of machine learning research 6.3 (2005).
[3] McAllester, David. "A PAC-Bayesian tutorial with a dropout bound." arXiv preprint arXiv:1307.2118 (2013).

Ridge-institute R&D Blog

オッカムの剃刀と汎化誤差解析