Google Brain の研究者たちは、日中は働き、夜は研究を行い、数十年にわたって数学コミュニティを困惑させてきた予想を解決しました。

2022年10月中旬、ジャスティン・ギルマーは東海岸にあるラトガース大学の数学者でかつての指導者であるマイケル・サックスを訪ねるためにカリフォルニアからニューヨークに飛びました。

回想の時間では数学の話はしませんでした。実際、ギルマーは 2015 年にラトガース大学で博士号を取得して以来、数学について真剣に考えていませんでした。その時、彼は学界でのキャリアを追求しないことを決意し、独学でプログラミングを学び始めました。サックスとの夕食をとりながら、ギルマーはグーグルでの仕事、つまり機械学習と人工知能についてメンターに語った。

ギルマーは、キャンパスの小道を歩きながら、2013 年に 1 年以上かけてこの道を歩き、「和合閉集合予想」と呼ばれる質問について考えていたことを思い出しました (フランクル予想と呼ばれる）」の問題。これは常に不毛な問題でした。ギルマーは、あらゆる努力の甲斐あって、数字の集合に関するこの一見単純な問題を解くのがなぜそれほど難しいのかを独学で理解することに成功しただけでした。

しかし、7年後のこの訪問の後、ギルマーは突然新しいインスピレーションを得ました。彼は、情報理論を適用して設定された推測を解決し、解決する方法を考え始めました。 1 か月にわたる調査の後、証拠への道は開かれ続けました。 11 月に彼は結果を arXiv で公開し、予想全体の証明において大きな進歩があったことを発表しました。

紙のリンク: https://arxiv.org/pdf/2211.09055.pdf

#この論文はその後の研究の波を引き起こしました。オックスフォード大学、マサチューセッツ工科大学、高等研究所などの数学者は、すぐにギルマーの新しい手法に取り組み始めました。

和集合閉集合予想とは何ですか?

閉集合予想は、{1, 2} や {2, 3, 4} などの数値の集合に関連します。セットに対して演算を実行できます。これには、セットの結合 (セットのマージ) の取得も含まれます。たとえば、{1, 2} と {2, 3, 4} の和集合は {1, 2, 3, 4} になります。

ファミリー内の任意の 2 つのセットの和集合がファミリー内の既存のセットと等しい場合、セットまたはファミリーは「和集合が閉じている」と言われます。たとえば、次の 4 つのセットのファミリーを考えてみましょう: {1}、{1, 2}、{2, 3, 4}、{1, 2, 3, 4}。

任意のペアを結合すると、ファミリ内にすでに存在するセットが得られるため、このファミリは閉じたセットであると言われます。

数学者たちは、1960 年代から閉集合予想について議論し続けてきましたが、ペーター フランクルの論文で最初の正式な声明が発表されたのは 1979 年になってからでした。 1980年代に日本に移住したハンガリー人の数学者で、数学に加えて大道芸も大好きです。

フランクルは、集合の族が閉じた集合の和集合である場合、集合の少なくとも半分に現れる要素 (または数値) が少なくとも 1 つ必要であると推測しました。これは 2 つの理由から自然に発生するしきい値です。

ジャスティン・ギルマー

最初のall、既製の閉じたセット ファミリの例では、すべての要素がセットのちょうど 50% に表示されます。たとえば、1 ～ 10 の数字を使用してすべての異なるセットを形成すると、そのようなセットは合計 1024 個になります。それらは、10 の要素のそれぞれが現れる 512 セットの閉じたファミリーを形成します。

フランクルがこの予想を提案したとき、この予想が当てはまらない閉集合族の例を提案する人はまだ誰もいませんでした。したがって、50% は正しい予測であると思われます。

だからといって、証明するのが簡単というわけではありません。ギルマーの研究以前には、多くの論文は、(セット ファミリのすべてのサイズで同じである 50% のしきい値ではなく) ファミリ内のセットの数に応じて変化するしきい値を確立することしかできませんでした。

コロンビア大学のウィル・サウィン氏は次のように述べています。「それは簡単であるべきだと感じており、多くの簡単な問題に似ていますが、まだ克服されていません。」

進歩の欠如は、この問題の扱いが難しい性質と、多くの数学者がそれについて考えたくないという事実の両方を反映しています。彼らは、不可能な問題を追いかけて何年ものキャリアを無駄にするのではないかと心配しています。ギルマー氏は、2013年のある日、サックス氏のオフィスを訪れ、このこととクローズドセット予想について言及したところ、同じくこの問題に取り組んでいた講師たちに彼を部屋から追い出されたことを覚えている。

不確実性の洞察

ラトガース大学を訪問した後、ギルマーは頭の中で質問を巡らせ、なぜそれがそれほど難しいのかを理解しようと努めました。彼は、基本的な事実を自分自身に思い出させました。100 セットの組み合わせのファミリーがある場合、2 つを選択して組み合わせるには 4950 通りの異なる方法があるということです。そこで彼は次のように考えました。これらの組み合わせに少なくともある程度の頻度で要素が出現しない場合、4950 の異なる組み合わせが 100 のセットにどのようにマッピングされるでしょうか?

この時点で、彼はまだ気づいていなかったとしても、すでに解決への道を進んでいたのです。

情報理論は 20 世紀前半に開発され、最も注目に値するのは 1948 年のクロード シャノンの論文「コミュニケーションの数学理論」です。この論文では、メッセージが表現する内容に関する不確実性の量に基づいて、メッセージの送信に必要な情報量を計算する正確な方法を提供します。情報と不確実性の間のこの関係は、シャノンの驚くべき洞察です。

情報理論は、ギルマーが大学院生として研究していた物体を数えることに関係する数学の分野である組み合わせ論に頻繁に登場します。しかし、カリフォルニアに帰る途中、彼は情報理論を和合閉集合予想と結びつけるやり方が素人の素朴さであるのではないかと心配した。

「正直に言うと、これまで誰もこれを考えなかったことに少し驚いています」とギルマー氏は語った。 「しかし、おそらく驚かないでください。私自身、この問題について 1 年間考えてきましたし、情報理論については知っています。」

問題の探索

ギルマーの数学に対する見解 勉強は私の数学への愛から来ています。彼は平日は主に Google での日々の仕事で忙しく、空いた時間は数学の問題の勉強に専念しています。また、忘れた公式をいつでも調べられるよう、数学の教科書を持ち歩いて仕事に取り組んでいます。ギルマーは地に足をつけながらも星にも目を向けています。彼は有名な数学者ティム・ガワーズのブログを読むのが好きで、インスピレーションを与えてくれています。

ギルマー氏は控えめにこう言いました。「難しい数学的問題を解く人は情報理論の要素の第 2 章を参照すべきではないと思われるかもしれませんが、私はそうしました。」

ギルマーによって提案された方法は、すべての集合に出現する要素の確率が 1% 未満である閉集合のファミリーを想像することです。これは反例であり、もし真実であれば、フランクルの予想が反証されることになる。

この族から 2 つのセット A と B がランダムに選択されたとします。セット A に数字 1 が含まれる確率はいくらですか?セットBはどうでしょうか？特定のセットに各要素が出現する確率は 1% よりわずかに低いため、A または B に 1 が含まれることを期待しないでください。これは、実際にはどちらにも 1 が含まれていないとしても驚かず、確かに多くの情報が得られないことを意味します。

次に、A と B の和集合に 1 が含まれる確率を考えます。これはまだ可能性は低いですが、いずれかのセットに 1 が単独で出現する確率よりわずかに高く、A に 1 が出現する確率と B に 1 が出現する確率の合計から両方に 1 が出現する確率を引いた値になります。したがって、A と B の和集合に 1 が含まれる確率は約 2% 未満です。

これはまだ低いですが、推定 50% に近いため、結果を共有するにはさらに多くの情報が必要であることを意味します。言い換えれば、すべてのセットに出現する要素の確率が 1% 未満である和集合を囲む集合ファミリーが存在する場合、2 つのセットの和集合には、いずれかのセットを単独で使用するよりも多くの情報が含まれます。

「推測を要素ごとに証明するというアイデアは非常に賢いです」とプリンストン大学のライアン・アルワイス氏はコメントしました。

ギルマーの研究はフランクルの疑惑に近づき始めました。これは、和集合閉集合の族では、2 つの集合の和集合には 2 つの集合自体よりも少ない情報が含まれるべきであり、それ以上の情報は含まれないことが簡単に示されるためです。

理由は簡単です。1024 個の異なるセットを含む和集合閉集合ファミリーを例にとると、各セットの要素は 1 から 10 までの数値です。これらのセットのうち 2 つがランダムに選択されると、平均して 5 つの要素の和集合が得られます。 (1024 セットのうち、252 には 5 つの要素が含まれており、これが最も一般的なセット サイズです。) 約 7 つの要素の結合を取得する可能性もあります。しかし、7 つの要素の和集合を得る方法の組み合わせは 120 通りしかありません。

重要なのは、ランダムに選ばれた 2 つのセットには、それらの和集合よりも不確実性の高い要素が含まれているということです。結合は、より多くの要素とより少ない可能性を備えたより大きなセットに似ています。和集合が閉じられた集合群内の 2 つの集合に対して和集合演算を実行すると、偏ったコインを投げるのと同じように、和集合の結果がわかる場合があります。コインがどちら側に着地するかを簡単に推測できます。 2 つのセット自体よりも。

これに基づいて、ギルマーは、セット内に少なくとも 1 つの要素が出現する確率は 1% 以上であると考えています。ギルマー氏が 11 月 16 日に証明を発表したとき、ギルマー氏はメモを付けました。ギルマー氏は、彼の手法を使用することで完全な予想の証明に近づく可能性があり、しきい値が 38% に上がる可能性があると考えていました。

5日後、数学者の3つの異なるグループが、ギルマーの研究に基づいた論文を互いに数時間以内に発表しました。感染拡大によりギルマー氏のアプローチは極限まで押し上げられたようだが、50％に到達するにはさらに新しいアイデアが必要になるかもしれない。

それでも、フォローアップ論文の著者の中には、なぜギルマー氏が 38% という比較的単純な研究を自分で行わなかったのか疑問に思った人もいます。実際、その理由は複雑ではありません。ギルマーは 5 年以上数学から離れていたのですが、この目標を達成するための技術分析作業のやり方を知らなかっただけなのです。

「私は少し錆びついていて、正直言って行き詰まっています」とギルマー氏は語った。 「しかし、私は数学コミュニティがそれをどう受け止めるか知りたいと思っています。」 しかし、ギルマー氏はまた、彼が練習する機会を失ったのと同じ理由で、ある程度彼も犠牲になったと信じています。唯一の説明 - なぜ私が大学院で 1 年間この問題を考えたが進歩がなかったのか、そして 6 年間数学から離れた後にこの問題に戻ってきて画期的な進歩を遂げたのか。機械学習以外に私は何も知りません。私の考え方の変化以外の説明。」

以上がGoogle Brain の研究者たちは、日中は働き、夜は研究を行い、数十年にわたって数学コミュニティを困惑させてきた予想を解決しました。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。