機械学習と連続体仮説。純粋数学が何に応用されるか誰にも予測できない
機械学習の分野にも「解決できるかどうか証明も反証もできない問題」が存在することが発見され、その論文が話題になっている。
- 機械学習によって解決できるかどうかが証明不可能な学習モデルが発見される - GIGAZINE
- Learnability can be undecidable | Nature Machine Intelligence
論文『Learnability can be undecidable（学習可能性は決定不能でありうる）』は、連続体仮説に言及していて、連続体仮説を使ってある抽象的な機械学習に関する問題が通常の数学の公理系では「証明」も「反証」もできないということを証明している。
連続体仮説には思い入れがあって、一時期 『集合論―独立性証明への案内』 を頑張って読んでいた（読めたとは言っていない）。今も実家にはその勉強ノートが何冊か眠っている。
興味津々で GIGAZINE の記事を読んだが、正直何を言っているのかわからなかった。そこで元の論文を読んでみた（読めたとは言っていない）。わかった範囲で、論文のさわりの部分をちょっとなぞってみたい。間違っている部分もあるかもしれないので、ご指摘いただけるとありがたいです。
連続体仮説
連続体仮説は「仮説」というけれども、今までもこれからも「連続体仮説が正しい」とか「間違っている」とか証明されることはない。なぜなら、通常の数学の公理系では連続体仮説は「証明」も「反証」もできないこと――公理系から「独立」しているという――が証明されているからだ。
「濃度」という概念は、「個数」の概念を無限集合に拡張したものだ。自然数も実数も無限個あるが、厳密に考えると実数は自然数よりも「たくさん」ある。無限と無限が比較できるのだ。そして、連続体仮説の主張によると、自然数の「個数」と実数の「個数」の間には「中間の無限個」を持つような集合は存在しないということになる。別の言い方をすると、自然数の「個数」よりも大きな要素の「個数」を持つ集合のうち最小の集合は、実数の「個数」と一致する。
実数の濃度が自然数の濃度と比べて真に大きい、という話をより正確に理解するためには「対角線論法」でググるとよい。一般的には無限にはさまざまな大きさがあって、任意の無限集合に対してそれよりも濃度の大きい集合が必ず存在する。そのため、無限集合の濃度自体も無数にある。
連続体仮説は19世紀にゲオルグ・カントールが提唱した。カントールは連続体仮説が真であると信じていたようだけど、1960年代に数学者ポール・コーエンが、連続体仮説が公理系ZFC（いわゆる「通常」の公理系）から独立していることを証明した。
数学の公理系から独立している命題は、それまでも知られていた。たとえばゲーデルは不完全性定理によって、自然数を含むある公理系が独立命題をもつことを証明した。連続体仮説は、独立な命題の中でも具体的な例を提供したという歴史的意義がある、と思う（要出典）。
連続体仮説と機械学習がつながった
元論文は、ZFCと独立な命題集に、機械学習の分野からまた一つの命題を加えた。それも、連続体仮説の独立性に基づいてそのことを証明したという。
これの面白さはどこにあるのかというと、いかにも工学的応用がなさそうな集合論の結果が、機械学習という最先端の工学分野に結びついたという点だ。だって、無限のサイズ同士を比較するなんて、まったくもって現実からかけ離れているような、雲の上の話に聞こえるではないか。
現実世界の生活で、「自然数よりも大きく実数よりも小さい濃度の無限集合が存在するかどうか」を気にしなきゃいけない場面なんてあるだろうか。そもそも世の中では、三角関数でさえ日常生活で使わない役立たずと思われているのだ。自然数も実数も無限個あることがわかればいい。それ以上の探求は日常生活と無関係な、純粋な知的好奇心の対象でしかない。そういう世界に我々は生きているのではないか。
ところが、今流行りのAIだとか機械学習だとか言われている分野に、連続体仮説がつながった。まあ実際の機械学習で学習モデルが決定不能かどうかを気にすべき場面が出てくるかは今はまだわからないけど、少なくとも理論上は連続体仮説により決定不能な学習モデルが存在することがわかった。
これからAIを勉強したいという人たちは、微分積分や線形代数や統計といった数学の分野の他に、もう一つ集合論を勉強しなければいけない時代が来るかもしれない。機械学習の勉強をしているはずが、いつの間にか連続体仮説とか到達不能基数とか構成可能宇宙とかそういうワードが飛び交う未来になったら、集合論ファンとしては楽しい未来だと思う。
決定不能な学習モデル
ずいぶん脱線したけれど、話を戻す。
元論文ではEMX（estimating the maximum）という機械学習の問題を考える。具体的には Web サイトに最適な広告を置く戦略になぞらえることができる。
ここに（EMXの）動機づけとなる例をあげましょう。さまざまなユーザーが訪問する Web サイトを想像してみてください。X をその Web サイトに訪問する潜在的なユーザーすべての集合とします。Web サイトのオーナーは広告を設置したいと考えています。広告は与えられた広告のプールから選ばれるものとします。プールにある広告 A はそれぞれ、あるユーザーのグループ F_A ⊆ X をターゲットにしています。たとえば、もし A がスポーツの広告なら、F_A がスポーツファンの集合といった具合です。目標は、ターゲットとなるグループが最も頻繁にサイトを訪問するような広告を設置することです。難しいのは、どういう訪問者がサイトに訪れるのか事前に知ることができないということです。
論文ではEMX問題を形式的に定義している。サイトの訪問者は実数の区間 [0, 1] にある実数である。（つまり、潜在的なサイトの訪問者の集合は連続体濃度のサイズをもつ。）広告のターゲットは区間 [0, 1] にある実数の有限集合である。サイトの訪問者は確率分布Pに従って独立に訪問してくる。などなど。学習可能性とかも形式的に定義している（けど読んでもあまりわからなかった）。
そして結論としては、EMXの学習可能性が ZFC 公理系と独立である、という定理を証明している。もう少し詳しくいうと、
ということになる。（たぶん。自信ない。）
純粋数学が何に応用されるか誰にも予測できない
連続体仮説の独立性証明がなされたときには、それが工学分野で応用されるなんて想像もつかなかったろう。応用されなかったとしても数学は数学の問題意識の中で発展していく。
研究における「選択と集中」がいかに間違っているかという話を随所で聞くけれども、私は学問の専門家ではないが、こういう発見があると確かにそうだと思う。学問の知見がどこでどういうふうに役立つのかは誰にも事前に予測できないのだから、役立つとわかっている分野にだけ集中的に投資するのは、愚かであるという以前に不可能だろう。
まあこれは個人にも当てはまることで、何にせよ勉強しておくにこしたことはない。勉強したことがどこでどう役立つのかわからないのだから、幅広く勉強しておくのがいい。ある日突然、これまで勉強したことが急に必要になったり大きなアドバンテージになるかもしれない。そういう気持ちがある。
