【機械学習】ノーフリーランチ定理を徹底解説

この記事では、ノーフリーランチ定理の意味、概要を徹底解説します。

#ノーフリーランチ定理とは
機械学習におけるノーフリーランチ定理とは
**「データから予測モデルを選ぶ（フィッティングする）際、予測モデルの候補が多すぎると、データをどれほどたくさん集めたりモデルの選び方をどのように工夫したりしても、選ばれたモデルの精度が非常に悪くなることがある」**
というものです。
この定理により
**「機械学習モデルを選ぶ際には、その事前知識に基づいて候補となるモデルを限定することが大切である」**
という重要な示唆が得られます。
より正確な記述は専門書に譲るとして、以下ではその肝となる考え方をお伝えします。


# アリスとボブのゲーム
ここではアリスとボブが斬新なゲームをしています。2人のやっているゲームを見ながら、ノーフリーランチ定理について理解していきます。

## ゲーム(1回目)
### ボブのターン（サンプルサイズの指定）
まずボブはアリスに何個のデータが欲しいかを伝えます。
`ボブはアリスに「5個のデータが欲しい」と伝えました。`

### アリスのターン（正解の関数の設定とデータの生成）
アリスはコインの「表・裏」と「赤・白」の対応ルールを決めます。この規則はアリスが自由に決めることができ、ボブには教えません。このルールに従い、コイン投げとその結果の記録をします。

`アリスはボブに見えないようにそっとメモ紙に「表は白。裏は赤」と書き、ポケットにしまいました。
アリスは用意しておいたコインと赤白２枚の紙を取り出しました。
コインを投げて、結果を２枚の紙に書いていきます。
メモ紙に書いたルールに従い、表が出た時には白の紙に「表」と書き、裏が出た時には赤の紙に「裏」と書きます。
アリスは5回コインを投げた結果、コインの目は「表→裏→表→表→裏」と出ました。
アリスは結果をそれぞれの色の紙に書き終えたところで、紙をボブに渡しました。`

### ボブのターン（統計モデルのフィッティング）
ボブは渡された２枚の紙に書かれた数字から、紙の色（赤と白）とコインの表裏の規則性を当てようとします。ボブの推論の正解率が75%以上の場合はボブの勝ちとします。
`白の紙には「表表表」と書かれていて、赤の紙には「裏裏」と書かれていました。
「簡単だよ！表は白の紙、裏は赤の紙に書かれている！」とボブは叫びました。
ボブの推論は100%(=2/2)正しいものでした。
「ボブの推論が75%以上正しい場合はボブの勝ち、それ未満ではアリスの勝ち」というルールにしていたので、今回はボブが勝ちとなりました。`

## ゲーム：2回目
アリスは1回目の結果が悪かったので、コインではなくサイコロを使うことにしました。今度は表と裏の２種類ではなく、1から6の目の６種類になります。

### ボブのターン（サンプルサイズの指定）
`ボブは「今度は10個のデータが欲しい」と伝えました。`

### アリスのターン（正解の関数の設定とデータの生成）
`アリスは「1,2,3,4は白。5,6は赤」とメモ紙に書き、そっとポケットにしまいました。
アリスは10回サイコロを振ったところ、サイコロは「3→2→5→1→2→6→5→2→1→3」という順番ででました。
アリスはメモ紙に書いたルールに基づき、赤と白の紙に出た目を書き、結果をボブに渡しました。`

### ボブのターン（統計モデルのフィッティング）
`ボブが受け取った紙を見ると
白の紙には「3,2,1,2,2,1,3」と書かれていて、赤の紙には「5,6,5」と書かれていました。
ボブは考えたのち、自信がなさそうに「1,2,3は白の紙、4,5,6は赤の紙に書くというルールじゃないかと思う」と言いました。
5つの目(1,2,3,5,6)についてはボブの推論は正しかったのですが、1つの目(4)に関しては間違っています（サイコロを振った際に、偶然4の目は出ませんでした）。
ボブの推論は83%(=5/6)正しかったので、今回もボブが勝ちとなりました。`

# ゲームと現実社会の対比
ゲームの中でアリスが用意したサイコロは、データが生成される自然界や社会現象に相当し、ボブの推論はデータから統計モデルを選ぶ(パラメータのフィッティング)というデータ分析作業に相当します。
ボブが取り組んだ問題はXが{1,2,3,4,5,6}（コイン投げのときは{表,裏}）、yが{赤・白}の値をとる、二値分類問題に相当します。
アリスがメモ紙に記載したルールは仮想的な真のモデルです（一般的にはこのように決定論的なモデルが想定されることはあまりありませんが、議論を単純にするためにここではサイコロの目が決まれば紙の色も必ず一つ決まることにしています）

# ボブがゲームに勝つためには?
アリスがサイコロを捨て、乱数を生成するコンピュータを用意した場合、ボブは勝ち続けることができるでしょうか？
この問いに対する答えがノーフリーランチ定理で、
**乱数の生成できる数(出目)の種類をnとすると、n/2個より少ないサンプルサイズをボブが要求した場合、ボブがどのような推論方法を使っても、アリスはボブの推論の正解率の期待値を75%未満に抑えることができる。（アリスはボブに勝つことができる）**
というものです。
ボブ側の立場になって言い換えると、
**乱数の出目の種類をnとすると、n/2個より少ないサンプルサイズを要求し続ける限り、どのように工夫して推論をしても正解率の期待値が75%以上になることは望めない（アリスに負けてしまう）**
ということになります。
この結果は直感的には当然です。
アリスが一様乱数を使用して1から1000までの出目を生成するとし、ボブが500個未満のデータを要求した場合、用意されたデータの中に出現しなかった出目が少なくとも500種類は存在することになります。データに出現しなかった出目について、ボブは当てずっぽうにならざるを得ず、その部分が偶然正解となる確率は50%。すでに出現した出目については完全に正しく推論できたとしても、全体の正解率の期待値は75%未満になってしまいます。(75%=100%×0.5+50%×0.5)
よって、このゲームでボブが勝てる見込みはとても低いものとなります。

# ノーフリーランチ定理の何がすごいのか？
おそらく今までの説明を読んで、ノーフリーランチ定理に拍子抜けされていると思うので、この定理のどこが興味深いかを補足します。

## データをいくら用意しても性能に限界がある場合がある
出目の種類はサイコロの場合6種類、コインの場合2種類ですが、コンピュータを使用した場合、出目の種類はいくらでも多くできます。現実世界でも、観測されるデータの値が取る値（出目の種類）にはほとんど制限がないと言える場合は多いです（たとえば0と1の間には無限個の有理数が存在しています）
出目の種類が無限大の場合にノーフリーランチ定理が示唆することは、**どんなにサンプルサイズを大きくしても、データの生成する確率分布によっては、精度の高い予測モデルが得られる見込みがない場合がある**ということです。

## 事前知識を活用し予測モデルの候補を絞らなくては、高い予測精度は望めない
実はこのゲームのルールで重要な点は、「アリスがメモ紙に書く規則になんら前提を置いていない」というところです。
ボブはアリスがメモ紙にどのような規則を設定しても対応できるようにしていました。
しかし例えば「アリスは素数が好きだから、『出目がある素数pより小さければ白、p以上ならば赤』という規則を採用するはずだ」などの事前知識があれば、この問題は簡単になります（問題が、素数pを推論する問題に変わります）
このような事前知識を使うことで、出目の種類が無限でも、有限のサンプルサイズで高い正解率を保証することが可能になる場合があります。
（これについての正確な議論は、VC次元の概念を使う必要があります）
まとめますと、**「機械学習においてはデータに関する事前知識を活用することが重要である。データを生成する確率分布になんら仮定を置かなければ、サンプルサイズをどれほど大きくしても望む予測精度が得られない場合がある」**ということがノーフリーランチ定理の重要な帰結です。

# AutoMLについて 
ここから先はAutoMLに関して、ノーフリーランチ定理から示唆されることについて考えたいと思います。
AutoMLとは機械にデータをいれて説明変数と目的変数を定義すれば、自動的に予測モデルを生成してくれるという便利なツールです。
現在、世界的に積極的に開発が進められている領域ですが、こうしたAutoMLツールは、「現在と同じ形で予測精度が追求されている限り、誰もが驚く非常に高い予測精度が達成されることは将来的にもおそらくないだろう」というのが筆者の考えです。その理由は、現在のAutoMLの学習の仕方は、データの生成された現実世界の背景や事前知識などを無視しているためです。
モデルの候補に適切な制限をかけない限り、汎用的で高い予測精度を確保することはできません。
今後、AutoMLが輝かしい発展を遂げるとしたら、「画像認識用AutoML」,「製造業需要予測用AutoML」,「コールセンター対応用AutoML」などのように、AutoML自体が専門分野に特化したものになる必要があると予想します。

機械学習では、ある領域に特化した問題で非常に高い精度をあげることが可能です。将棋や画像認識など、多くの事例が存在します。
しかし「我が社の売り上げを伸ばす革新的なアイディアを出してくれ」という要求に応えられるAIは、将来的にも存在しないだろうと筆者は考えます。