no free lunch定理

no free lunch定理 (no free lunch theorem)†

直観的には，事例の分布などについて事前知識がなければ，あらゆる目的関数について他を常に上回るような学習アルゴリズムは存在しないという定理．「ただ(=事前の知見なし)の飯(=予測や探索での改善)はない(no free lunch)」といった意味の名称．

形式的には，訓練事例に含まれないデータに対するエラーを \[\mathcal{E}_k(E|F,\mathcal{D})=\sum_{\mathbf{x}\notin\mathcal{D}}P(\mathbf{x})[1-\delta(F(\mathbf{x}),h(\mathbf{x}))]P_k(h(\mathbf{x}|\mathcal{D})\] ただし

\(F(\mathbf{x})\)：学習目標の関数
\(h(\mathbf{x})\)：アルゴリズムが獲得した関数
\(\mathcal{D}\)：訓練事例集合
\(\delta(F,h)\)：目標\(F(\mathbf{x})\)と\(h(\mathbf{x})\)が一致すると1になるKroneckerのδ
\(P_k(h|\mathcal{D})\)：アルゴリズム\(k\)が，訓練事例集合\(h(\mathbf{x})\)を与えられたときに出力する関数\(h\)の分布

no free lunch定理は，任意の二つのアルゴリズム\(P_1(h|\mathcal{D})\)と\(P_2(h|\mathcal{D})\)について，サンプリング分布\(P(\mathbf{x})\)と\(n\)個の訓練事例とは独立に以下のことが成立：

全ての目的関数\(F\)上で均一に平均すると \(\mathcal{E}_1(E|F,n)-\mathcal{E}_2(E|F,n)=0\)．すなわち \[\sum_F \sum_{\mathcal{D}}P(\mathcal{D}|F)[\mathcal{E}_1(E|F,\mathcal{D})-\mathcal{E}_2(E|F,\mathcal{D})]=0\]
ある固定した訓練集合\(\mathcal{D}\)について，\(F\)上で均一に平均すると \(\mathcal{E}_1(E|F,\mathcal{D})-\mathcal{E}_2(E|F,\mathcal{D})=0\)
全ての事前分布\(P(F)\)上で均一に平均すると \(\mathcal{E}_1(E|n)-\mathcal{E}_2(E|n)=0\)
ある固定した訓練集合\(\mathcal{D}\)について，\(P(F)\)上で均一に平均をすると \(\mathcal{E}_1(E|\mathcal{D})-\mathcal{E}_2(E|\mathcal{D})=0\)