アヒルと “TANSTAAFL”

技術研究所の (あ) です。

弊研究所では機械学習を用いた画像分類などをやってます。
機械学習にもやり方がいろいろありますが、どれも基本的には、「判定したいもの」や「状況」を入力したときに出てくる「答え」が、なるべく正解 (教師データ) と同じに (もしくは近いものに) なるようにするか、あるいは何らかの「ポイント」がなるべく高くなるように学習する、ということをやってます。

すなわち、何らかの評価関数 (コスト関数) の最大値・最小値を探すという、最適化問題を扱っていることになります。この最適化問題に関して、おもしろい名前の定理があります。

その名も「ノーフリーランチ定理 (No-Free-Lunch Theorem)」。”Free Lunch” とは「無料の昼食」のこと。”No Free Lunch” とは「無料の昼食なんてものはない」ということ。

「『無料の昼食なんてものはない』定理」? いったいどういうことでしょう?

ノーフリーランチ定理

この定理の内容は

「コスト関数の極値を探索するあらゆるアルゴリズムは、
全ての可能なコスト関数に適用した結果を平均すると同じ性能となる」
(David H. Wolpert and William G. Macready, 1995)

というものです。
もう少し詳しく説明します。最適値を探すアルゴリズムを頑張って工夫したとします。ある一連のコスト関数に対してはとても効率よく最適値を探すことができたとしましょう。しかし、「考えうる全ての、ありとあらゆるコスト関数」を持ってきて、それらの最適値を探させると、「平均的には」工夫してないアルゴリズムと性能の差がでない、というのです。

な、何を言っているのか(ry

「考えうる全てのコスト関数」というのがミソなのですが、それでも、それらを相手にしては、凄いアルゴリズムとそうでもないアルゴリズムは変わらない、と言われてしまうと困ってしまいます。最適値を探索するアルゴリズムを工夫することは無意味なのでしょうか? もちろん、そんなことはありません。

一般的に、ある領域の問題に対するコスト関数には、「ありとあらゆる」ものは出てきません。何らかの特徴というか癖というか、そんなようなものがあります。ノーフリーランチ定理が主張するのは、「ある領域の問題」に対する最適化アルゴリズムは、その特徴や癖を事前知識としたりして、その領域に特化したものにせねばならない (それをぜんぜん違う領域に適用すると性能がでないかもしれない)、ということなのです。

機械学習にもやり方がいろいろありますが、「どれか一つのやり方で万事 ok」とはいかない、ということでもあります。問題の領域に合わせて、やり方を選んだり工夫したりする必要があるのです。

名前の由来

ところで、なぜこの定理は「ノーフリーランチ定理」なんていう名前なのでしょう?「無料の昼食」とは「うまい話」のことで、「どれか一つのやり方で万事 ok」などという「うまい話」はない、ということを表しています。

かつてアメリカのどこかの酒場で「飲みに来た客には、昼食を無料で振る舞う」という宣伝が出されることがあったそうです。昼食無料、宣伝としては魅力的ですね。まさに、うまい話に見えますね。しかしもちろん、実際には昼食の代金は酒代に上乗せされているだけです。そんなうまい話などありません。

ここから、「無料の昼食などない (There Ain’t No Such Thing As A Free Lunch)」という格言が生まれました。頭文字を取って、 “TANSTAAFL” (タンスターフル) という略語でも使われます。

そしてこの格言は、1966年に R.A.ハインラインの代表的な SF 小説の一つ「月は無慈悲な夜の女王」の中で取り上げられ、広く知られるようになりました。それが、この定理の名前の直接の由来です。
ちなみに「月は無慈悲な夜の女王」には、マイク (マイクロフト) という名のとても印象深い AI が登場しますので興味のある方はぜひ:-)。

みにくいアヒルの子定理

もう一つ、似たような感じでおもしろい名前の不思議な定理があります。「みにくいアヒルの子定理 (Ugly Ducking Theorem)」、です。これは日本の物理学者の渡辺慧が提唱・証明した定理で、

「みにくいアヒルの子と普通のアヒルの子は、二匹の普通のアヒルの子と同じくらい類似している」

というものです。これはまた、何を言ってるんだか、な感じです。

もう少し詳しく説明します。みにくいアヒルの子を A、二匹の普通のアヒルの子を B と C とします。A と B には共通点があります (鳥である、とか)。A と C にも、B と C にも共通点があります。A と B だけに共通で、C に当てはまらないような点も、まあ見つかるでしょう。同様に、A と C だけ、B と C だけ、の共通点も見つかるはずです。このように、全ての組み合わせに対応する共通点があるので、すなわち、どれも同じだけ似ているのです。

…ちょっと詭弁っぽいですね。実は、ノーフリーランチ定理が「考えうる全てのコスト関数に対して」というのがミソだったのと同じように、これも「あらゆる種類の共通点 (や差異) を同じ重みで考える」というところがミソになっています。実際には、人間が何かの類似性や差異を判断するときには、重要視するものとあまりしないものと、意識的・無意識的に重み付けしているのです。逆に、そうした適度な重み付けがないと、何かを類似度に基づいてグループ分けすることはできなくなってしまう、というのが、この定理なのです。

機械学習を使って画像を分類する場合も、要は「どの類似性・差異を重要視するか」ということを教師データを使って学習させています。理屈から言うと、データセットに対してどんな分類の仕方でもできてしまいます (ノーフリーランチ定理からすると、学習しやすい分類の仕方となかなか学習が進まない分類の仕方はあるでしょう) が、そこに何らかの価値観を入れ込むのです。

さいごに

以上、二つのおもしろい名前の定理のご紹介でした。人間と同じような判断のできる仕組みを作ろうとするところに関わる定理に、こんななんとも人間的なネーミングがなされているのがまたおもしろいですね。内容も不思議で、この世の真理の奥深さが垣間見える感じです。

まだまだおもしろく不思議なものはたくさんあるでしょうから、一つでも多く見つけ、活用していきたいものです。


SNSでもご購読できます。