連続体仮説と結びつく証明不可能な学習モデルが発見される

数学基礎論は、機械学習の発展において重要な役割を果たし、私たちの理解を向上させ、新しい学習をデザインするためのツールを提供します。しかし、時にはコストが付いてきます。例えばゲーデルとコーエンは、1931年にすべてが数学で証明できるわけではないことを発表しました。今回の論文では、機械学習アルゴリズムと数学の結びつきによって、特定の事柄における機械学習が活用可能かどうかを判断できなくなってしまうと指摘されています。

論文Learnability can be undecidable(学習可能性は決定不能でありうる)

目次
1、機械学習は数学的な制限を共有している連続体仮説とは?
2、連続体仮説とは?
3、連続体仮説と機械学習がつながる
4、証明不可能な学習モデルとは
5、まとめ

機械学習は数学的な制限を共有している

現在、PCやスマートフォンに搭載されたAIから電子メールのスパムフィルターまで、機械学習を用いたアルゴリズムは日常生活のあらゆる場所に浸透しています。機械学習においてはデータを分析し、パフォーマンスを向上させるアルゴリズムのデザインが肝心です。コンピューターに対して「このような画像を『人の顔』だと判断するように」と明示的にプログラムするのは困難ですが、機械学習で大量の画像を学習させることによって、AIが人の顔が映った画像とそうでない画像を区別が可能になります。

このように基本的にはデータベースを分析することによって、結果を予測するための予測子(予測を行うための数学関数そのもの、またはそれに近いもの)を得ることが最終的な目標となります。与えられたモデルと関数族について、合理的な制約のもとでこの目標が達成できる(望ましい予測子が得られる)場合、そのモデルは学習可能であるとされます。

これらの現代のアプリケーションは、その起源を辿るとさまざまな数学的分析に関係する機械学習のサブフィールドにたどり着きます。

連続体仮説とは?

数学の大きな醍醐味の一つに「証明」があります。例えば「解の存在証明」のように、「解がないことを証明する」ようなものがたくさんあります。そんな証明の命題の一つに、不完全性定理で知られるような「証明も反証もできない命題であることが証明されている命題」があります。

『連続体仮説』

『連続体仮説』も、「証明も反証もできない命題」のひとつです。

19世紀にドイツの数学者であるゲオルク・カントールによって「自然数の濃度と実数の濃度との間には他の濃度は存在しない。」という「連続体仮説」提唱されました。

カントールは連続体仮説が真であると信じていましたが、ゲーデルの不完全性定理によって、自然数を含むある公理系が独立命題をもつことを証明されました。関連 ZFCから独立な命題の一覧

さらに、1960年代には数学者ポール・コーエンが、連続体仮説が公理系ZFC(いわゆる「通常」の公理系)から独立していることを証明しました。

※公理(こうり、英: axiom)とは、その他の命題を導きだすための前提として導入される最も基本的な仮定のことである。一つの形式体系における議論の前提として置かれる一連の公理の集まりを公理系という

カントールは,連続体仮説は真であると信じ,証明しようと試みた.しかし,連続体仮説の真偽は ZFC のもとでは決定できないことが,次の形で示されました。.
定理 1.1. (ゲーデル,1938)ZFC に CH を加えた体系は無矛盾である.
定理 1.2. (コーエン,1963)ZFC に CH の否定を加えた体系は無矛盾である.

参照 連続体仮説の独立性

ZFC公理系 は伝統的な数学諸分野をすべて包摂する公理系なので,「ZFC公理系 で真偽を決定できない」とは,すなわち「伝統的な数学の証明能力を超越した問題である」ことを意味します。

つまり、連続体仮説は「仮説」というけれども、今までもこれからも「連続体仮説が正しい」とか「間違っている」とか証明されることはない。なぜなら、通常の数学の公理系では連続体仮説は「証明」も「反証」もできないこと――公理系から「独立」しているという――が証明されているから、ということになります。

Ben-David氏らの研究チームは、一見関係無いように見える、機械学習においても、この「連続体仮説」を共有していて、同じように「すべての事象が証明可能というわけではない」という「殻」に閉じ込められている運命にあると言います。

連続体仮説と機械学習がつながる

今まで数学基礎論における連続体仮説(自然数と実数の中間の濃度をもつ無限集合は存在しない)は工学上の有用性はないと考えられていましたが、今回の論文では、機械学習に関する決定可能性問題に重要な関係があることが示されました。

連続体仮説を偽と仮定した公理系において決定可能な機械学習に関する問題が存在することが明らかになったのです。

つまり連続体仮説を真とする標準的な公理系においては決定不可能な機械学習の問題が存在することになる。逆に連続体仮説を偽とする標準的な公理系においては決定可能な機械学習の問題が存在するということです。

いかにも工学的応用がなさそうな集合論の結果が、機械学習という最先端の工学分野に結びついたという点で大変興味深いです。

証明不可能な学習モデルとは

論文内では、機械学習における学習可能性を考える際に、連続体仮説に結びついているために、学習可能かどうかを判別できない機械学習モデルがあることを指摘します。

例えば具体的に示されているのが、データの最大値を推定する「estimatingthemaximum(EMX)」というモデルです。このモデルは標準数学の枠組みでは学習可能性が証明できないとのことです。

Ben-David氏はEMXモデルを使用する例として、具体的には Web サイトに最適な広告を置く戦略になぞらえました。例えば、「どのユーザーが広告を見て特定のウェブサイトを訪れるのかが判明していない状態で、最も多くのユーザーを引き寄せる広告を見つけ出す」といった問題の場合「いくつかの関数の中から最も目標達成の期待値が大きな関数を見つけ出す能力をAIに教え込むものである」と言い換えることができます。

論文ではこのEMX問題を形式的に定義します。サイトの訪問者は実数の区間 [0, 1] にある実数である。広告のターゲットは区間 [0, 1] にある実数の有限集合である。サイトの訪問者は確率分布Pに従って独立に訪問してくる‥など。

そして結論としては、EMXの学習可能性が ZFC 公理系と独立である、という定理を証明しました。

もう少し詳しくいうと、連続体仮説が真であるようなモデルでは、EMX は学習可能であるが、連続体仮説が偽であるようなモデルでは、EMX は学習可能でないということになります。

EXMモデルは機械学習においてよく使われている「確率的で近似的に正しいモデル(PACモデル)」とよく似ていますが、わずかに学習基準の違いがあります。EXMモデルは「証明も反証もできないことが証明されている」連続体仮説と結びついており、その結果EXMモデル自体についても、「証明も反証もできない」という結果が導き出されてしまうとのことです。

まとめ

簡単にまとめると、機械学習アルゴリズムが有限個の学習データから無限にある判定対象を弁別できるか否かは、自然数全体と実数全体との間の“濃度”をもつ無限集合が存在するか否かという連続体仮説の問題に帰着することが数学的に示されたということになります。

EMXは機械学習の新しいモデルであるため、実際のアルゴリズムを開発する上でのその有用性はまだわかりません。Ben-David氏の発見がすぐさま既存の機械学習分野に大打撃を与えることはないでしょう。

しかし、新しい学習モデルを導入する際は注意が必要であることがわかりました。さらに、確立された既存の学習モデルにおいても、もう一度見直す必要があるかもしれません。最先端のコンピュータ科学の分野でさえ、数学の奥深い本質を逃れることは不可能だということを、私たちに思い出させてくれます。