エンジニアを目指す浪人のブログ

情報系に役立ちそうな応用数理をゆるめにメモします

二値分類におけるノーフリーランチ定理を証明する

情報学 機械学習

勉強を進めていて，機械学習あるいは組み合わせ最適化における基本的な原理であるノーフリーランチ定理(no free lunch theorem)を知りました．文献[2]によるとそれぞれ別のものとして考えるようです．機械学習におけるそれがどのようなものかについて，文献[4]から引用します．

ノーフリーランチ定理：全ての分類問題を考えたとき，どのようなアルゴリズムも平均的には，その汎化誤差に関して事前の差はない

この記述のいいかえとして，以下の記述があります．

あるアルゴリズム A がある予測問題で，アルゴリズム B より汎化誤差に関して性能が良かったとしても，アルゴリズム B が A より良くなるような別の予測問題が存在する

上記二つの記述は直感的にはわかりやすいですが，具体的に数式で理解したいところです．本記事では二値分類におけるノーフリーランチ定理に着目し，文献[1]をベースにして定理と証明をまとめます．なお文献[3]にも類似した別バージョンの記述があります．

=================================================================================
{\displaystyle \mathbb{I}[ \ p \ ] } は {\displaystyle p } が真のとき {\displaystyle 1}，そうでないとき {\displaystyle 0} となる関数とします．
任意の集合 {\displaystyle \mathcal{S} } の {\displaystyle m } 個の直積集合を以下のように書くことにします．
{\displaystyle \;\;\; \mathcal{S}^m = \mathcal{S} \times \mathcal{S} \times \cdots \times\mathcal{S} }


可算集合 {\displaystyle \mathcal{X} } を変数 {\displaystyle X } の空間，{\displaystyle \mathcal{Y} \in \{ -1,1 \} } をラベル空間とします( {\displaystyle \{ 0,1 \} } の方が一般的かもしれませんが，便宜上こちらを採用します)．確率変数の組 {\displaystyle (X \times Y) \in \mathcal{X} \times \mathcal{Y} } の(同時)確率分布 {\displaystyle \mathcal{D} } の確率を {\displaystyle P_{(X,Y) \sim \mathcal{D} } [ \cdot ] }，その期待値を {\displaystyle E_{(\cdot) \sim \mathcal{D} } [ \cdot ] }，{\displaystyle \mathcal{D} } の試行を独立に {\displaystyle m } 回行うときの確率分布を {\displaystyle \mathcal{D}^m } ，その確率を {\displaystyle P_{(X,Y)^m \sim \mathcal{D}^m } [ \cdot ] }，その期待値を {\displaystyle E_{(\cdot) \sim \mathcal{D}^m } [ \cdot ] } とします．{\displaystyle \mathcal{D} } に従うサンプルを {\displaystyle S_i, \ i \in \{ 1,2,\ldots \} }，{\displaystyle \mathcal{D}^m } に従うサンプルを {\displaystyle S = \cup_i S_i } とします．

サンプル {\displaystyle S \sim \mathcal{D}^m } から(二値)分類器 {\displaystyle \mathcal{A} } を決定する手続きを数式で表すと {\displaystyle \mathcal{A} [ \cdot ] : \cup_{i=1}^{\infty} S_i \to \mathcal{Y}^\mathcal{X} } であり( {\displaystyle \mathcal{Y}^\mathcal{X} } は集合 {\displaystyle \mathcal{X} } から集合 {\displaystyle \mathcal{Y} } への写像の集合です)，決定した分類器は関数 {\displaystyle \mathcal{A} [ S ](\cdot) : \mathcal{X} \to \mathcal{Y} } です．

二値分類の目的は以下の誤差 {\displaystyle \mathrm{err}(\cdot,\cdot) } を小さくする関数 {\displaystyle f : \mathcal{X} \to \mathcal{Y} } を見つけることです．

(1){\displaystyle \;\;\; \mathrm{err}(f,\mathcal{D})= P_{(X,Y) \sim \mathcal{D}} [ f(X) \neq Y ] }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \sum_{x \in \mathcal{X}} P [ X = x \ \cap \ Y \neq f(x) ] }


以下の二値分類におけるノーフリーランチ定理は，固定した {\displaystyle m } 個のサンプル(確率変数) {\displaystyle S } についての誤差(1)の期待値(汎化誤差)をあらゆる(離散)確率分布について( {\displaystyle 1/4 } よりも)小さくする分類器を得ることが不可能である，ということを主張する定理です．{\displaystyle | \cdot | } は集合の要素数です．

定理 3.1 (No free lunch)
{\displaystyle m \le | \mathcal{X} |/2 } とする．任意の分類器 {\displaystyle \mathcal{A}} について，以下の1.2.をみたすような確率分布 {\displaystyle \mathcal{D} } が存在する．

1. {\displaystyle \mathrm{err}(f,\mathcal{D})=0 } となる {\displaystyle f \in \mathcal{Y}^\mathcal{X} } が存在する．
2. {\displaystyle E_{S \sim \mathcal{D}^m} [ \mathrm{err}(\mathcal{A} [ S ] ,\mathcal{D}) ] \ge 1/4 } が成り立つ．

証明.
{\displaystyle \mathcal{C} \subseteq \mathcal{X} } を {\displaystyle |\mathcal{C}|= 2m } となる集合とする．関数 {\displaystyle f_i \in \mathcal{Y}^\mathcal{C}, \ i = \{ 1,2,\ldots,2^{2m} \} } を考える．{\displaystyle |\mathcal{Y}^\mathcal{C} |=2^{2m} } である．{\displaystyle \mathcal{C} \times \mathcal{Y} } 上の確率分布 {\displaystyle \mathcal{D}_i,\ i \in \{ 1,2,\ldots,2^{2m} \} } を以下で定義する．

{\displaystyle \;\;\;\;\;\; P_{(X,Y) \sim \mathcal{D}_i} [ X=x \cap Y=y ] = \begin{cases} 1/2m & x \in \mathcal{C}, \ y=f_i(x) \\ 0 & x \in \mathcal{C}, \ y \neq f_i(x) \end{cases} }

すると以下が成り立つので {\displaystyle \mathcal{D}_i,\ i \in \{ 1,2,\ldots,2^{2m} \} } は分類器 {\displaystyle f_i } について1.を満たす確率分布である．

{\displaystyle \;\;\;\;\;\; \mathrm{err}(f_i,\mathcal{D}_i)= P_{(X,Y) \sim \mathcal{D}_i} [ f_i (X) \neq Y ] }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \sum_{x \in \mathcal{X}} P [ X = x \ \cap \ Y \neq f_i (x) ] }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = 0 }

{\displaystyle \mathcal{X} } 上の確率分布 {\displaystyle \mathcal{D}_X } を以下で定義する．

{\displaystyle \;\;\;\;\;\; P_{X \sim \mathcal{D}_X} [ X=x ] = \begin{cases} 1/2m & x \in \mathcal{C} \\ 0 & x \in \mathcal{X} \setminus \mathcal{C} \end{cases} }

{\displaystyle \mathcal{D}_i } からサンプル {\displaystyle (x,y) } をドローすることは {\displaystyle \mathcal{D}_X } からサンプル {\displaystyle x } をドローし {\displaystyle y=f_i (x) } とすることと等価である．{\displaystyle \mathcal{C} } の半数の要素を {\displaystyle \mathcal{D}_X^m } からドローした集合を以下のように定義する．

{\displaystyle \;\;\;\;\;\; S_X = (x_1,\ldots,x_m) \sim \mathcal{D}_X^m }

{\displaystyle \;\;\;\;\;\; S_X^i = \left( (x_1,f_i(x)),\ldots,(x_m,f_i(x)) \right), \;\;\; i \in \{ 1,2,\ldots,2^{2m} \} }

{\displaystyle \mathcal{D}_i^m } からサンプル {\displaystyle S } をドローすることは {\displaystyle \mathcal{D}_X^m } からサンプル {\displaystyle S_X } をドローし {\displaystyle y=f_i (x) } として {\displaystyle S_X^i } を得ることと等価であるので，以下が成り立つ．{\displaystyle \mathcal{A} } をある分類器とする．

{\displaystyle \;\;\;\;\;\; E_{S \sim \mathcal{D}_i^m} [ \mathrm{err}(\mathcal{A} [ S ] ,\mathcal{D}_i) ] = E_{S_X \sim \mathcal{D}_X^m} [ \mathrm{err}(\mathcal{A} [ S_X^i ] ,\mathcal{D}_i) ] }

これを用いて以下を得る．

(※){\displaystyle \;\;\; \max_{i \in \{ 1,2,\ldots,2^{2m} \}} E_{S \sim \mathcal{D}_i^m} [ \mathrm{err}(\mathcal{A} [ S ] ,\mathcal{D}_i) ] \ge \frac{1}{2^{2m}} \sum_{i=1}^{2^{2m}} E_{S \sim \mathcal{D}_i^m} [ \mathrm{err}(\mathcal{A} [ S ] ,\mathcal{D}_i) ] }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \frac{1}{2^{2m}} \sum_{i=1}^{2^{2m}} E_{S_X \sim \mathcal{D}_X^m} [ \mathrm{err}(\mathcal{A} [ S_X^i ] ,\mathcal{D}_i) ] }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = E_{S_X \sim \mathcal{D}_X^m} \left[ \frac{1}{2^{2m}} \sum_{i=1}^{2^{2m}} \mathrm{err}(\mathcal{A} [ S_X^i ] ,\mathcal{D}_i) \right] }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \ge \min_{S_X \in \mathcal{C}^m } \frac{1}{2^{2m}} \sum_{i=1}^{2^{2m}} \mathrm{err}(\mathcal{A} [ S_X^i ] ,\mathcal{D}_i) }

ある {\displaystyle S_X \in \mathcal{C}^m } について以下が成り立つ．

{\displaystyle \;\;\;\;\;\; \mathrm{err}(\mathcal{A} [ S_X^i ] ,\mathcal{D}_i) = P_{(X,Y) \sim \mathcal{D}_i } [\mathcal{A} [ S_X^i ](X) \neq Y ] }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \frac{1}{|\mathcal{C}|} \sum_{x \in \mathcal{C} } \ \mathbb{I}[ \mathcal{A}[ S_X^i ](x) \neq f_i(x) ] }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \frac{1}{2m} \sum_{x \in \mathcal{C} } \ \mathbb{I}[ \mathcal{A}[ S_X^i ](x) \neq f_i(x) ] }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \ge \frac{1}{2m} \sum_{x \in \mathcal{C} \setminus S_X } \mathbb{I}[ \mathcal{A}[ S_X^i ](x) \neq f_i(x) ] }

以下のような {\displaystyle j(i) } を定義する．

{\displaystyle \;\;\;\;\;\; f_{j(i)}(x) = \begin{cases} f_i(x) & x \in S_X \\ -f_i(x) & x \in \mathcal{C} \setminus S_X \end{cases} }

{\displaystyle x \in S_X } と {\displaystyle i \in \{ 1,2,\ldots,2^{2m} \} } について以下が成り立つ，

{\displaystyle \;\;\;\;\;\; S_X^{j(i)} = \left( (x_1,f_{j(i)}(x)),\ldots,(x_m,f_{j(i)}(x)) \right) }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \left( (x_1,f_i(x)),\ldots,(x_m,f_i(x)) \right) }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = S_X^i }

これらを用いて以下を得る．

{\displaystyle \;\;\;\;\;\; \mathrm{err}(\mathcal{A} [ S_X^i ] ,\mathcal{D}_i) + \mathrm{err}(\mathcal{A} [ S_X^{j(i)} ] ,\mathcal{D}_{j(i)}) }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\; \ge \frac{1}{2m} \sum_{x \in \mathcal{C} \setminus S_X } \left[ \mathbb{I}[ \mathcal{A}[ S_X^i ](x) \neq f_i(x) ] + \mathbb{I}[ \mathcal{A}[ S_X^{j(i)} ](x) \neq f_{j(i)}(x) ] \right] }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\; = \frac{1}{2m} \sum_{x \in \mathcal{C} \setminus S_X } \left[ \mathbb{I}[ \mathcal{A}[ S_X^i ](x) \neq f_i(x) ] + \mathbb{I}[ \mathcal{A}[ S_X^i ](x) \neq - f_i(x) ] \right] }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\; = \frac{1}{2m} \sum_{x \in \mathcal{C} \setminus S_X } 1 }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\; = \frac{1}{2m} | \mathcal{C} \setminus S_X | }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\; = \frac{1}{2} }


これと(※)より以下を得る．
{\displaystyle \;\;\;\;\;\; \max_{i \in \{ 1,2,\ldots,2^{2m} \}} E_{S \sim \mathcal{D}_i^m} [ \mathrm{err}(\mathcal{A} [ S ] ,\mathcal{D}_i) ] }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \ge \min_{S_X \in \mathcal{C}^m } \frac{1}{2^{2m}} \sum_{i=1}^{2^{2m}} \mathrm{err}(\mathcal{A} [ S_X^i ] ,\mathcal{D}_i) }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \min_{S_X \in \mathcal{C}^m } \frac{1}{2^{2m}} \sum_{i=1}^{2^{2m-1}} \left[ \mathrm{err}(\mathcal{A} [ S_X^i ] ,\mathcal{D}_i) + \mathrm{err}(\mathcal{A} [ S_X^{j(i)} ] ,\mathcal{D}_{j(i)} ) \right] }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \ge \frac{1}{2^{2m}} \sum_{i=1}^{2^{2m-1}} \frac{1}{2} }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \frac{1}{4} }

したがって

{\displaystyle \;\;\;\;\;\; \exists \ i, \ E_{S \sim \mathcal{D}_i^m} [ \mathrm{err}(\mathcal{A} [ S ] ,\mathcal{D}_i) ] \ge 1/4 }

成り立つので，これを満たす {\displaystyle \mathcal{D}_i } は 2.を満たす確率分布である．(証明終わり)

=================================================================================

以上，二値分類におけるノーフリーランチ定理を証明しました．


参考文献
[1] Ben-Gurion University of the Negev Sivan Sabato先生のノート https://www.cs.bgu.ac.il/~inl162/wiki.files/interactive2016_1.pdf
[2] No Free Lunch Theoremsのページ http://no-free-lunch.org/
[3] An Interactive Journey into Machine Learning　http://mlweb.loria.fr/book/en/nofreelunch.html
[4] 産業技術総合研究所 神嶌敏弘先生のノート http://www.kamishima.net/archive/mldm-overview.pdf