1. はじめに
万能な機械学習アルゴリズムは存在しない、機械学習アルゴリズムは問題に合わせて選択する必要があると言われています。これを、数学の一定の枠組みの上で証明したのがノーフリーランチ定理（No Free Lunch Theorem）です。（以下ではNFLと略します）
NFLは、機械学習に、ある種の理論的な限界が存在することを示しています。NFLは、機械学習に関する応用や理論、さらには「知性」に関する哲学的議論などでもよく参照される示唆に富んだ定理です。概要を理解するだけではなく、それが意味するところを正確に理解しておくことはきっと有益でしょう。
この記事では、NFLの概要を説明した後、具体例を通してNFLが実際に成り立つことを確認していきます。NFLの証明には立ち入りませんが、正確な理解のために最低限必要となる用語定義は省略せずに説明していきます。このような確認プロセスを通して、NFLが示している機械学習の限界とは具体的にどのようなものなのかを描いていきたいと思います。
2. NFLの名前の由来
本題に入る前に、「No Free Lunch」という定理の名前の由来を確認しておきましょう。この名前は、「無料のランチのようなものは世の中にはない (There Ain’t No Such Thing As A Free Lunch)」という格言から来ています。それは、以下のような内容です。
昔、ある街の、ある酒場に、「ランチ無料！」という看板が出ていた。
しかし、その看板の下の方には「ただし、酒を１杯以上注文した人に限る」とも。
そして、酒代にはランチ代が上乗せされていた。世の中、一見、得に見えるようなものがあっても、
必ずどこか他のところで代償を払わなければならないものだ。
結局、無料の昼食のような万事都合のよい話などない。
※ 本記事末尾の [13], [14] を参照
3. NFLの大まかな意味
前述の格言と同様、NFLも、大まかに言うと以下のような意味を持っています。
- 予測アルゴリズムに対し、全ての問題にわたって予測性能を評価して「平均値」を取ると、どの予測アルゴリズムも同じ値になる。
- どの予測アルゴリズムも、ある問題の予測性能が高ければ、必ず何か他の問題の予測性能が低くなる。
- 結局、全ての問題に対して予測性能が高くなるような万能な予測アルゴリズムは存在しない。
- どの問題も発生する確率が同じならば、どの予測アルゴリズムも、予測性能の「期待値」は同じになる。
ただ、この説明だけでは、かなり意味が曖昧です。
- 「予測アルゴリズム」とは、どのような範囲のアルゴリズムが該当するのでしょうか？
- 「問題」とは、どのような範囲の問題が対象になるのでしょうか？
- 「予測性能」とは、何をどのように評価したものでしょうか？
- 「予測性能の平均値」、「予測性能の期待値」とは、何を指しているのでしょうか？
この後、具体例を通して、これらの疑問に答えていきたいと思います。
4. NFLの種類
NFLには様々な形式のものがありますが、基本的なものはDavid H. Wolpert他により証明された以下の２つでしょう。
- 教師あり学習のNFL:
分類予測問題を教師あり学習により解くアルゴリズムを対象とするNFL。[5][6]参照。 - 探索問題/最適化問題のNFL:
コスト関数の最小値を逐次探索するアルゴリズムを対象とするNFL。[7][8]参照。
以下では、「教師あり学習のNFL」の方に焦点を当てていきます。
※「探索問題/組み合わせ最適化問題のNFL」については、[11]の説明が分かりやすいです。
5. NFLの具体例
ここからが本題です。シンプルな具体例を通してNFLが実際に成り立つことを確認することが目標です。
5.1 問題の枠組みと用語
まず、画像データの分類予測問題を例に、教師あり学習アルゴリズムに関する用語を以下にまとめておきます。これが、NFLの舞台になります。
これらの用語の正確な定義と例を、この後、一つづつ確認していきましょう。
5.2 分類
まず、分類や分類関数について見ていきます。
5.2.1 分類の例
３枚の写真を、「かわいくない」 か、「かわいい」かの２つに分類する例を考えます。
このように、いくつかの分類対象のそれぞれに、$N$個の分類ラベルのいずれかを割り当てる操作を $N$分類 ということにします。上の例は、２分類の例です。
5.2.2 分類関数
分類対象の３枚の写真に、「$0$」、「$1$」、「$2$」という名前をつけ、分類対象の集合を $𝑋=\{0, 1, 2\}$ とします。
分類ラベル「かわいくない」と分類ラベル「かわいい」のそれぞれに、「$0$」、「$1$」という名前をつけ、分類ラベルの集合を $𝑌=\{0, 1\}$ とします。
上の例のように２分類を行うと、写真$0,1,2$のそれぞれに割り当てる分類ラベル$0$または$1$が決まるので、$X$から$Y$への関数$f$が次のように決まります。
$$f(0)=0,~ f(1)=1,~ f(2)=1$$
逆に、$X$から$Y$への関数を一つ選ぶと、各写真に対する２つの分類ラベルの割り当て方が決まるので、２分類を行うことができます。このようにして、２分類と、$𝑋$から$𝑌$への関数を、一対一に対応させることができます。
一般に、分類対象$X$の$N$分類と、分類対象の集合$X$から$N$個の分類ラベルの集合$Y$への関数は一対一に対応しています。
分類という「操作」は厳密な扱いをしにくいので、その代わりに$X$から$Y$への関数を扱っていくことにします。この分類対象の有限集合$X$から、分類ラベルの集合$Y$への関数を、分類関数 と言うことにします。
5.2.3 分類関数集合
２分類という操作も、分類関数も、複数の種類があります。前述の例では、全部で$f_0$～$f_7$の８種類があります。
一般に、 $X$から$Y$への分類関数全体の集合を 分類関数集合$𝑌^𝑋$ と言うことにします。
上の例の場合、$Y^X=\{ f_0, f_1, …,f_7 \} $ です。
5.3 分類予測問題
次に、問題の定義に関わる用語を見ていきます。
5.3.1 正解分類関数と予測分類関数
ある人が行った３枚の写真の２分類を予測する問題を考えます。
上の例の場合、正解の分類に対応する分類関数 $f_3$ を予測することが目標です。$f_2$ と予測したならば、完全な正解ではないですが、３枚中２枚が一致しているので、正解に近い予測と言えるでしょう。
一般に、正解の分類に対応する分類関数を 正解分類関数 $f (∈Y^X)$、予測された分類関数を 予測分類関数 $h (∈Y^X)$ と言うことにします。上の例の場合、$f=f_3,~ h=f_2$ です。
5.3.2 学習データ
３枚の写真の２分類を予測する例で、写真$0$と$1$に対しては、分類ラベル$0$と$1$がそれぞれ対応すると知らされているとします。
$$f(0)=0,~ f(1)=1$$
このような情報は、正解分類関数の予測に役立てられます。この例では、以下のように $f=f_2$ または $f=f_3$ という予測がたてられます。
一般に、正解分類関数$f$に対して、以下を満たす$d(∈X^m×Y^m)$を要素数$m$の 学習データ と言うことにします。
$$ \begin{align*}
d &= (d_X, d_Y), \\
d_X &= (x_1,x_2,, ,x_m)∈X^m, \\
d_Y &= (y_1,y_2,, ,y_m)∈Y^m,~ y_i=f(x_i) \\
\end{align*}
$$
上の例では、以下が要素数2の学習データになります。
$$ d=(d_X, d_Y),~ d_X=(0, 1),~ d_Y=(0, 1) $$
5.3.3 分類予測問題とは
分類予測問題とは、与えられた学習データをもとに正解分類関数を予測する（予測分類関数を提示する）問題のことです。
「3. NFLの大まかな意味」で触れた「問題」とは、分類予測問題の正解の種類の意味であり、「正解分類関数」に対応しています。
5.4 分類予測アルゴリズム
次に、分類予測アルゴリズムの定義と例を見ていきます。
5.4.1 分類予測アルゴリズムとは
分類予測問題を解く何らかのアルゴリズム $a$ があったとすると、$a$ は学習データ $d(∈X^m×Y^m)$ を入力とし、予測分類関数 $h(∈Y^X)$ を出力することができます。そのため、$a$は、 $X^m×Y^m$ から $Y^X$ への関数とみなすことができます。逆に、 $X^m×Y^m$ から $Y^X$ への関数は、分類予測アルゴリズムとみなすことができます。そこで、$X^m×Y^m$ から $Y^X$ への関数$a$を 分類予測アルゴリズム と言うことにします。（したがって、計算量が多すぎて現実には計算可能でないアルゴリズムや、ほとんど予測があたらないような役にたたないアルゴリズムも、分類予測アルゴリズムに該当します。このようなアルゴリズム全てがNFLの対象となります。）
「3. NFLの大まかな意味」で触れた「予測アルゴリズム」とは、この「分類予測アルゴリズム」のことを指しています。
以下では、３枚の写真の２分類を題材にして、分類予測アルゴリズムのシンプルな例を２つ示します。
5.4.2 常に「かわいくない」と予測するアルゴリズム
分類予測アルゴリズム$a_0$は、学習データ以外の写真は常に分類ラベル$0$（かわいくない）と予測するアルゴリズムです。学習データ$d=((x_1,x_2),(y_1,y_2))$に対応する予測分類関数$h=a_0 (d)$を以下のように決めます。
$$ h(x)=
\begin{cases}
y_1 & \text{when } x=x_1 \\
y_2 & \text{when } x=x_2 \\
0 & \text{otherwise}
\end{cases}
$$
5.4.3 常に「かわいい」と予測するアルゴリズム
分類予測アルゴリズム$𝑎_1$は、学習データ以外の写真は常に分類ラベル$1$（かわいい）と予測するアルゴリズムです。学習データ$d=((x_1,x_2),(y_1,y_2))$に対応する予測分類関数$h=a_1 (d)$を以下のように決めます。
$$ h(x)=
\begin{cases}
y_1 & \text{when } x=x_1 \\
y_2 & \text{when } x=x_2 \\
1 & \text{otherwise}
\end{cases}
$$
5.5 誤差関数
次に、誤差の評価に関わる用語を見ていきます。
5.5.1 テストデータ
以下の用語を定義します：
- 学習データ$d=(d_X,d_Y)$に対して、$d_X$に含まれない分類対象データの集合 $q=\{q_1,q_2,, ,q_l\}=X−d_X$ を テスト対象データ と言うことにします。
- 正解分類関数$f$とテスト対象データ$q$に対して、$y_f = ( f(q_1), f(q_2),,,f(q_l) )∈Y^l$ をテスト対象データの 正解ラベル と言うことにします。
- 予測分類関数$h$とテスト対象データ$q$に対して、$y_h = (h(q_1), h(q_2),,,h(q_l))∈Y^l$ をテスト対象データの 予測ラベル と言うことにします。
- テスト対象データと正解ラベルの組 $(q, y_f) ∈X^l×Y^l$ を テストデータ と言います。
３枚の写真の２分類の例では、$d_X=(0, 1)$の場合、以下のようになります。
$$
\begin{align}
q &=X−d_X=\{2\} && \text{・・・テスト対象データ}\\
y_f &=(f(2)) && \text{・・・正解ラベル}\\
y_h &=(h(2)) && \text{・・・予測ラベル}\\
\end{align}
$$
5.5.2 予測の誤差
正解分類関数$f$と予測分類関数$h$に対して、以下はテスト対象データ$𝑞$上での「誤り率」を表しています。これを$f$と$h$の$q$上での 誤差 と言うことにします。
$$ \begin{align}
&Er_q(h, f)=\textstyle\sum_{𝑞_𝑖∈𝑞} \delta(h(𝑞_𝑖)≠ 𝑓(𝑞_𝑖)) / l \\
&ここで、\delta(TRUE)=1,~ \delta(FALSE)=0,~ 𝑙=(𝑞の要素数) \\
\end{align}
$$
３枚の写真の２分類の例では、$𝑞=\{2\}$ の場合、以下のようになります。
$$
Er_q(h, f)=
\begin{cases}
0 & \text{when } h(2)=f(2) \\
& \text{(写真2の予測が正解の場合)} \\
1 & \text{when } h(2)≠f(2) \\
& \text{(写真2の予測が不正解の場合)}
\end{cases}
$$
5.5.3 分類予測アルゴリズムの誤差
学習データが$d$である場合の、正解分類関数$f$に関する分類予測アルゴリズム$a$の 誤差 を、以下のように、$f$と$h=a(d)$のテスト対象データ$q=X−d_X$上での誤差と定義します。
$$ \begin{align}
&Err_{a,d}(f) = Er_q(h,f) = \textstyle\sum_{𝑞_𝑖∈𝑞} \delta(h(𝑞_𝑖)≠ 𝑓(𝑞_𝑖)) / l \\
&ただし、\delta(TRUE)=1,~ \delta(FALSE)=0,~ 𝑙=(𝑞の要素数)
\end{align}
$$
「3. NFLの大まかな意味」で触れた「予測性能」とは、この分類予測アルゴリズムの誤差 $Err_{a,d}(f)$ のことを指しており、この値が小さいほど予測性能は高いと言えます。
３枚の写真の２分類の例では、$𝑑_𝑋=(0, 1)$ の場合、$𝑞=\{2\}$なので、$h=a(d)$と置くと、以下のようになります。
$$
Err_{a,d}(f) =
\begin{cases}
0 & \text{when } h(2)=f(2) \\
& \text{(写真2の予測が正解の場合)} \\
1 & \text{when } h(2)≠f(2) \\
& \text{(写真2の予測が不正解の場合)}
\end{cases}
$$
5.5.4 分類予測アルゴリズムの誤差の計算例
前述の分類予測アルゴリズム$𝑎_0, 𝑎_1$のそれぞれの誤差は以下のようになります。（ただし、$𝑑_𝑋=(0, 1)$ の場合）
5.6 分類の確率分布
前述の分類予測アルゴリズムの誤差 $Err_{a,d}(f)$ は、特定の正解分類関数$f$に対するものでした。現実には、様々な正解分類関数が発生するので、それら全てを評価対象に含めて「総合的に」誤差の低い分類予測アルゴリズムが求められます。つまり、誤差の「期待値」が低いアルゴリズムが求められます（これは、機械学習の文脈で言われる「汎化性能が高い」アルゴリズムに対応していると考えられるでしょう）。そのため、誤差の期待値の計算方法を定義する必要があります。
誤差の期待値の計算方法を定義する前に、正解分類関数の発生確率に関する用語を定義しておく必要があります。それが、このセクションの目標です。
5.6.1 分類の確率分布
最初に定義する必要がある確率は、問題の対象を観測して得られた正解分類関数が$f$になる確率$p(f)$です。この$f$に対する確率の関数$p(f)$を、$f$の 確率分布 と言うことにします。
例えば、３枚の写真の２分類を5人の人に行ってもらい、$f_0$～$f_7$のどの分類関数が選ばれるかを調べます。結果は下の表の人数のようになったとします。さらに、もう一度、今度は5人の中からランダムに1人を選び、３枚の写真の２分類を行ってもらいます。このとき、各$f_0$～$f_7$の確率分布は下表の右の$p(f)$のようになります。
※確率の列の空欄部分は値が0であることを表します。以下も同様です。
5.6.2 分類の条件付き確率分布
次に定義する必要がある確率は、以下の３つです。
- 正解分類関数が $f$ で、学習データが $d=(d_X, d_Y)$ である確率 $p(f, d)$
- 学習データが $d=(d_X, d_Y)$ である確率 $p(d)$
- 学習データが $d=(d_X, d_Y)$ であった場合に、正解分類関数が $f$ である確率 $p(f|d)$
$p(f|d)$ は、以下の式により計算できます。
$$ p(f|d) = \frac {p(f, d)}{p(d)} $$
具体例で、これらの確率を説明しましょう。例えば、３枚の写真の２分類を、前出の5人の人の中からランダムに選んだ一人に行ってもらいます。写真$0$と$1$のそれぞれをどちらに分類したかを教えてもらい、学習データ $d=((0, 1),(y_1,y_2))$ を得ることにします。このとき、$p(f, d)$, $p(d)$, $p(f|d)$は以下のようになります。
このようにして得られる$f$に対する確率の関数 $p(f|d)$ を、学習データ$d$のもとでの分類関数$f$の 条件付き確率分布 と言うことにします（事後確率分布という言い方もあります）。
5.7 分類予測アルゴリズムの期待誤差
NFLの舞台構築の最後のステップは、分類予測アルゴリズムの期待誤差の定義です。
5.7.1 分類予測アルゴリズムの期待誤差とは
学習データ$d$に対する、分類予測アルゴリズム$a$の 期待誤差 $EErr_d(a)$ を以下のように定義します。これは、学習データが $d$ である場合の、分類予測アルゴリズム $a$ の誤差の条件付き期待値を表しています（$E_{f}(・|d)$ が条件付き期待値を表す記号です）。
$$ EErr_d(a) = E_{f∈X^Y}(Err_{a,d}(f)|d) = \textstyle\sum_{f∈X^Y}Err_{a,d}(f)・p(f|d) $$
「3. NFLの大まかな意味」で触れた「予測性能の期待値」とは、この分類予測アルゴリズムの期待誤差 $EErr_d(a)$ のことを指しています。
5.7.2 期待誤差の計算例
分類予測アルゴリズムの期待誤差 $EErr_d(a)$ の計算方法を具体例で確認しておきましょう。
３枚の写真の２分類を、前出の5人の人の中からランダムに選んだ一人に行ってもらう場合、学習データ $d=((x_1, x_2),(y_1,y_2))=((0, 1),(0,1))$ に対する、分類予測アルゴリズム $a_i$ の期待誤差 $EErr_d (a_i)$ は以下のように計算されます。
この場合は、$a_0$ よりも $a_1$ の方が 期待誤差が小さく、予測性能が高くなりました。
5.8 NFL（期待誤差バージョン）
では、具体例でのNFLの確認に入りましょう。
5.8.1 具体例でのNFLの確認 - 宇宙人Xがやってきた
突然ですが、あなたの前に宇宙人Xがやってきたと思ってください。この宇宙人Xに３枚の写真の２分類を行ってもらいます。これまでと同様、写真$0$と$1$のそれぞれをどちらに分類したかを教えてもらい、学習データ $𝑑=((x_1, x_2),(y_1,y_2))=((0,1),(0,1))$ を得たとします。次に、分類予測アルゴリズム $𝑎_𝑖$ で予測分類関数 $h=a_i(d)$ を得て、写真2の分類ラベル $h(2)$ を予測します。
これまでの例と異なるのは、$f$ の確率分布が全く不明という点です。このような場合、それぞれの $f_i$ が発生する確率 $p(f_i)$ は同じと予測するのが最も妥当でしょう。そこで、$p(f_i) = 1/8$ としておきます。
この条件で期待誤差 $EErr_d(a_i)$ を計算してみましょう。結果は以下の通りです。
この場合は、$a_0$ と $a_1$ の期待誤差は等しくなりました。予測性能の期待値が同じになることを確認できました。
一般に、各 $f$ が発生する確率が同じの場合（$f$ の確率分布が一様分布になる場合）、どのような分類予測アルゴリズム $a$ の期待誤差も等しくなります。それを証明しているのがNFLです。
5.8.2 NFLの中身
正確なNFLの内容を以下に示します。
【NFL(期待誤差バージョン)】 分類関数の確率分布 $p(f)$ が一様分布であるならば、任意の分類予測アルゴリズム $a_0$ と $a_1$、および、任意の学習データ $d$ に対して、以下が成り立つ。
$$ EErr_d(a_0) = EErr_d(a_1) $$
さらに、より一般に、以下のような場合もNFLは成り立つことが証明されています。
- 正解分類関数 $f$ は、分類先を確率的に変動させる関数であってもよい。つまり、分類ラベルの確率分布を出力する関数でもよい。
- 学習データ $d=\{(x_i), (y_i)\}$ はノイズを含んでいてもよい。つまり、$f(x_i)=y_i$ を満たさなくてもよい。
- 学習データ $d=\{(x_i), (y_i)\}$ の $x_i$ はランダムに抽出してもよい。
- テスト対象データ $q=\{q_i\}$ は、一定の条件を満たせば、ランダムに抽出してもよい。
- 分類予測アルゴリズム $a$ は、出力する予測分類関数 $h$ を確率的に変動させてもよい。
- 予測関数 $h$ は、分類先を確率的に変動させてもよい。つまり、分類ラベルの確率分布を出力する関数でもよい。
- 誤差関数は、一定の条件を満たせば、他の関数に置き換えてもよい。確率的に変動する関数であってもよい。
5.9 NFL（単純平均バージョン）
NFLにおける「$p(f)$ が一様分布であるならば」という分類関数の確率分布に関する条件は、以下のように少し定義を変更すると取り除くことができます。
学習データ$d$に対する、分類予測アルゴリズム$a$の 誤差の単純平均 $AvrErr_d(a)$ を以下のように定義します。
$$ AvrErr_{d}(a) = average_{f∈X^Y} (Err_{a,d}(f)) = \textstyle\sum_{f∈X^Y}Err_{a,d}(f) / |X^Y| $$
ここで、$|X^Y|$ は分類関数集合 $X^Y$ の要素数です。分類対象の集合 $X$ の要素数を $|X|$、分類ラベルの集合 $Y$ の要素数を $|Y|$ とすると、$|X^Y|=|X|^{|Y|}$ となります。
この定義の元、以下が成り立ちます。
【NFL(単純平均バージョン)】 任意の分類予測アルゴリズム $a_0$ と $a_1$、および、任意の学習データ $d$ に対して、以下が成り立つ。
$$ AvrErr_{d}(a_0) = AvrErr_{d}(a_1) $$
NFL(単純平均バージョン)は、NFL(期待誤差バージョン)の場合と同様に、より一般の場合にも成り立つことが証明されています。
「3. NFLの大まかな意味」で触れた「予測性能の平均値」とは、分類予測アルゴリズムの誤差の単純平均 $AvrErr_d(a)$ のことを指しています。
３つの写真を２分類する例で、NFL(単純平均バージョン)が成り立っていることを確認してみましょう。「5.5.4 分類予測アルゴリズムの誤差の計算例」の表より、以下のように計算できます。
$$
AvrErr_d(a_0) = (0+1+0+1+0+1+0+1) / 8 = 0.5 \\
AvrErr_d(a_1) = (1+0+1+0+1+0+1+0) / 8 = 0.5
$$
6. NFLが実世界で意味するもの
最後に、NFLが実世界でどのような意味を持つかを考えてみたいと思います。
- 万能な分類予測アルゴリズムは存在しません。冒頭の説明の繰り返しになりますが、どの分類予測アルゴリズムも、ある正解分類関数に対する誤差が小さければ、必ず何か他の正解分類関数に対する誤差が大きくなります。
- 逆の言い方をすると、発生する確率や重要性の低い正解分類関数の誤差を犠牲にすることで、発生する確率や重要性の高い正解分類関数の誤差を小さくすることが可能になります。それにより、より期待誤差の小さい、あるいは、より実世界での価値の高い分類予測アルゴリズムを得られる可能性があります。
- つまり、NFLは、実世界での機械学習アルゴリズムの改良や開発の価値を否定するものではないということです。
- 実世界の問題では、分類予測アルゴリズムの期待誤差が同じになることはほとんどないでしょう。正解分類関数の確率分布が一様分布になるケースは、ほとんどないと考えられるからです。あったとしても、以下のようなケースぐらいでしょう。
- 正解分類関数の確率分布が実際に一様分布の場合： 例えば、意図的に、ランダムに正解分類関数を選択するような場合です。
- 正解分類関数の確率分布が全く未知の場合： 宇宙人Xの例のように、正解分類関数の確率分布を、仮説として一様分布と想定するという場合です。
- 正解分類関数の確率分布が全く未知の場合であっても、知見が蓄積されていけば、いずれ一様分布という仮説を見直すことが可能になるでしょう。そして、分類予測アルゴリズムの期待誤差が同じになるという状況も、変わっていくと予想されます。
- 宇宙人Xの例で言うと、当初は、「正解分類関数の確率分布が全く未知」なので、「正解分類関数の確率分布は一様分布である」という仮説を採用して、NFLから「任意の分類予測アルゴリズムの期待誤差は同じになる」という結果を得ることができました。（これはこれで、この時点では、有益な知見でしょう。）
- 後から、宇宙人Xが $f_7$ を選択する可能性が高いということが分かれば（宇宙人Xが、どこかにいるかもしれない $f_0$ を選択する可能性が高い宇宙人Yではないことが分かれば）、正解分類関数の確率分布の仮説を見直し、より予測性能の高い分類予測アルゴリズムを適用することが可能になるでしょう。
- 予測対象の宇宙人Xは何も変わっていないのに、当初の「任意の分類予測アルゴリズムの期待誤差は同じになる」という結論が、後から否定されてしまいました。いったい、どこが間違っていたのでしょうか？ NFLに何か問題があったのでしょうか？ そうではありません。当初の「正解分類関数の確率分布は一様分布である」という仮説が間違っていたというだけです。
- NFL(期待誤差バージョン)は、厳密には、「正解分類関数の確率分布が全く未知」を前提条件にはしていません。「正解分類関数の確率分布が一様分布である」の方を前提条件としています。
- そもそも、「正解分類関数の確率分布が全く未知」という条件は、NFLが厳密に定義している用語を使って表すことができません。NFLが用意している舞台の外側にある概念です。
- したがって、「正解分類関数の確率分布が全く未知」という条件から、「正解分類関数の確率分布が一様分布である」を数学上で証明することはできません。「正解分類関数の確率分布が一様分布である」は、（経験や直感などにもとづいて）仮説として採用することができるだけです。
- この仮説が誤りであれば、この仮説とNFLから導かれる結論「任意の分類予測アルゴリズムの期待誤差は同じになる」も誤りになります。NFLに問題があったのではなく、仮説設定に問題があったということです。
結局、予測対象を観察・研究し、正解分類関数の確率分布をより正確に理解し、それにあった分類予測アルゴリズムを開発・適用することが重要です。それを示唆しているのが、NFLです。
参考文献
- NFLの概説記事
- [1] wikipedita: No Free Lunch Theorem
- [2] wikipedita: ノーフリーランチ定理
- [3] No Free Lunch Theorems
- [4] WHAT DOES DINNER COST?, David H. Wolpert
- David H. WolpertほかによるNFLの論文
- [5] The Lack of A Priori Distinctions Between Learning Algorithms, 1996, David H. Wolpert,
- [6] The Supervised Learning No-Free-Lunch Theorems, 2001, David H. Wolpert
- [7] No Free Lunch Theorems for Search, 1996, David H. Wolpertほか
- [8] No Free Lunch Theorems for Optimization, 1996, David H. Wolpertほか
- 教師あり学習のNFLの関連論文・解説記事
- [9] データマイニング・機械学習分野の概要, 神嶌 敏弘, ノーフリーランチ定理 - 探索問題/最適化問題のNFLの関連論文
- TANSTAAFL: There Ain’t No Such Thing As A Free Lunch の由来
- NFLをシンギュラリティ否定の根拠として参照している例
- [15] 翻訳：知能爆発の不可能性
変更履歴
- 2022/7/8 初版公開
- 2022/7/10 全般的に説明などを追加。
以上