機械学習によって解決できるかどうかが証明不可能な学習モデルが発見される

機械学習の発達にはめざましいものがあり、画像の中から特定のオブジェクトを認識したり人間の声を正しく認識したりと、機械学習を用いた多くのAIが登場しています。しかしそんな機械学習にも「解決できるのかどうかの『証明』ができない問題」が存在すると、コンピューターサイエンスの研究者が指摘しています。

Learnability can be undecidable | Nature Machine Intelligence
https://www.nature.com/articles/s42256-018-0002-3

Unprovability comes to machine learning
https://www.nature.com/articles/d41586-019-00012-4

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

ウォータールー大学でコンピューターサイエンスの教授を務めるShai Ben-David氏は、機械学習のアルゴリズムと数学的論理の結びつきによって、特定の事柄における機械学習が可能かどうかを判断できなくなってしまうと指摘しました。

1931年、オーストリアの数学者・論理学者であったクルト・ゲーデルは、20世紀の数学基礎論・論理学にとって最も重要な発見とされる「不完全性定理」を発表しました。不完全性定理とは、自然数論を含む公理化された理論の中には証明も反証もできず、自身の無矛盾性も証明できない公理が存在するという定理です。

そして、19世紀にドイツの数学者であるゲオルク・カントールが提唱した、「自然数全体の集合の濃度(可算濃度)と実数全体の集合の濃度(連続体濃度)の間には他の濃度が存在しない」という「連続体仮説」についても、「証明も反証もできない命題である」ことが証明されました。Ben-David氏らの研究チームは、これらの数学的理論が機械学習の証明に影響を与えると述べています。

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

しかし、Ben-David氏らの研究チームは機械学習における学習可能性を考える際、不完全性定理および連続体仮説に結びついているために、学習可能かどうかを判別できない機械学習モデルがあることを発見したとのこと。研究チームはデータの最大値を推定する「estimating the maximum(EMX)」というモデルについて、標準数学の枠組みでは学習可能性が証明できないとしています。

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

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

EXMモデルは新しい機械学習モデルだそうで、Ben-David氏の発見がすぐさま既存の機械学習分野に大打撃を与えることはないとのこと。しかし、機械学習モデルには今回のようなケースがあり得ることを理解して、新たな学習モデルを採用する際は慎重を期すべきであり、既存の学習モデルについても再検討する必要があるかもしれません。