概要
XNUMX月中旬、 ジャスティン・ギルマー 友人の結婚式に出席するためにカリフォルニアからニューヨークに飛んだ。 東海岸にいる間、彼は元顧問を訪ねた。 マイケル・サックス、ギルマーがXNUMX年前に博士号を取得したラトガース大学の数学者。
Saks と Gilmer は昼食を取り合ったが、数学については話さなかった。 実際、ギルマーは 2015 年にラトガース大学を卒業して以来、数学について真剣に考えていませんでした。そのとき、彼は学界でのキャリアを望んでいないと判断し、代わりに独学でプログラミングを学び始めました。 サックスと一緒に食事をしながら、ギルマーはかつての恩師に、機械学習と人工知能に取り組んでいる Google での仕事について話しました。
ギルマーがラトガースを訪れた日は晴れていた。 彼は歩き回りながら、2013 年に XNUMX 年の大半を同じキャンパスの小道を歩き回り、組合閉鎖予想と呼ばれる問題について考えていたことを思い出しました。 それは実りのないものでしたが、固執していました.ギルマーは、彼のすべての努力にもかかわらず、数のセットに関する単純に見える問題が解決するのが非常に難しい理由を自分自身に教えることに成功しただけでした.
「なぜそれが難しいのかを理解したという満足が得られるまで、多くの人がその問題について考えていると思います。 おそらくほとんどの人よりも多くの時間を費やしました」とギルマーは言いました。
16 月の訪問の後、予想外のことが起こりました。彼は新しいアイデアを思いつきました。 ギルマーは、情報理論の手法を適用して、ユニオンの閉じた予想を解決する方法について考え始めました。 彼はそのアイデアを XNUMX か月間追求し、毎回失敗することを期待していました。 しかし、代わりに、証明への道が開かれ続けました。 最後に、XNUMX 月 XNUMX 日に彼は 史上初の結果を発表 これにより、数学者は完全な予想を証明することができます。
この論文は、一連のフォローアップ作業を引き起こした。 オックスフォード大学、マサチューセッツ工科大学、高等研究所などの数学者は、ギルマーの斬新な方法をすぐに構築しました。 しかし、そうする前に、彼らは自分自身の質問をしました:この男は誰ですか?
半分いっぱい
和閉予想は、{1, 2} や {2, 3, 4} などの集合と呼ばれる数の集まりに関するものです。 セットに対して操作を実行できます。これには、それらを結合することを意味するユニオンを取ることも含まれます。 たとえば、{1, 2} と {2, 3, 4} の結合は {1, 2, 3, 4} です。
セットのコレクションまたはファミリーは、ファミリー内の任意の XNUMX つのセットの和集合がファミリー内の既存のセットと等しい場合、「ユニオン クローズド」と見なされます。 たとえば、次の XNUMX セットのファミリーを考えてみましょう。
{1}、{1、2}、{2、3、4}、{1、2、3、4}。
任意のペアを組み合わせると、すでにファミリに含まれているセットが得られ、ファミリのユニオン クローズが作成されます。
数学者は 1960 年代にまでさかのぼるユニオン クローズド予想のバージョンについて雑談しましたが、1979 年の論文で最初の正式な声明を受け取りました。 ピーター・フランクル1980 年代に日本に移住したハンガリーの数学者で、ストリート パフォーマンスも彼の追求の XNUMX つです。
フランクルは、集合の族が和集合で閉じている場合、集合の少なくとも半分に現れる少なくとも XNUMX つの要素 (または数) を持たなければならないと推測しました。 XNUMX つの理由から、これは自然なしきい値でした。
第 50 に、すべての要素が正確に 1% のセットに含まれるユニオン クローズド ファミリの例がすぐに利用できます。 たとえば、10 から 1,024 までの数字からさまざまなセットを作成できます。 そのような集合は 10 あり、組合に閉じた家族を形成し、512 の要素のそれぞれが XNUMX の集合に現れます。 そして第二に、フランクルがこの推測を行った時点では、この推測が成り立たなかった組合閉鎖家族の例を誰も示していなかった.
したがって、50% は正しい予測のように思えました。
簡単に証明できるというわけではありませんでした。 フランクルの論文以来、何年にもわたって結果はほとんどありませんでした. ギルマーの仕事の前は、これらの論文は、ファミリーのセット数によって変化するしきい値を確立することしかできませんでした (すべてのサイズのセット ファミリーに対して同じ 50% のしきい値であるのとは対照的です)。
「簡単であるべきだと感じています。多くの簡単な問題に似ていますが、攻撃に抵抗しています」と彼は言いました。 ウィル・サウィン コロンビア大学の。
進歩の欠如は、問題のトリッキーな性質と、多くの数学者がそれについて考えたくないという事実の両方を反映しています。 彼らは、解決不可能な魅力的な問題を追いかけて何年ものキャリアを失うのではないかと心配していました. ギルマーは、2013 年のある日、サックスのオフィスに行き、労働組合が閉鎖した推測を持ち出したことを覚えています。 彼の顧問は、過去に自分で問題に取り組んだことがあり、彼を部屋から追い出しそうになりました。
「マイクは、『ジャスティン、あなたは私にこの問題についてもう一度考えさせようとするだろうし、私はそれをしたくない』と言った」とギルマーは言った.
不確実性の洞察
ラトガースを訪れた後、ギルマーは頭の中で問題を転がし、なぜそれが難しいのかを理解しようとしました。 彼は基本的な事実を自分自身に促しました: 100 セットの家族を持っている場合、4,950 つを選択して結合する方法は 4,950 通りあります。 それから彼は自問しました: 100 の異なる共用体が、少なくともある程度の頻度でそれらの共用体に出現しない場合、わずか XNUMX のセットにマップされる可能性はありますか?
その時点でさえ、彼は証明への道を進んでいたが、彼はまだそれを知らなかった. オブジェクトのペアをランダムに引っ張ったときに何が期待できるかについて厳密な考え方を提供する情報理論の手法が、彼をそこに導きます。
情報理論は 20 世紀の前半に発展しましたが、最も有名なのはクロード シャノンの 1948 年の論文です。コミュニケーションの数学的理論」 この論文は、メッセージが正確に何を言うかについての不確実性の量に基づいて、メッセージを送信するために必要な情報量を計算する正確な方法を提供しました. このリンク - 情報と不確実性の間 —シャノンの驚くべき、基本的な洞察でした。
おもちゃの例として、私がコインを 99 回投げ、その結果のシーケンスをあなたに送信したとします。 通常のコインの場合、送信には 1 ビットの情報が必要です。 しかし、それが装填されたコイン (たとえば、表が出る可能性が XNUMX% の場合) である場合、所要時間は大幅に短縮されます。 たとえば、ロードされたコインが XNUMX 回すべて表になる場合、XNUMX (XNUMX ビットの情報) を送信することに事前に同意することができます。 公平なコイントスの結果は、偏ったコイントスよりも驚くべき結果が得られるため、より多くの情報が得られます。
同じ考え方が、数値の集合に含まれる情報にも当てはまります。 たとえば、1,024 から 1 までの数字から作成された 10 個のセットなど、ユニオンで閉じたセットのファミリがある場合、ランダムに 50 つのセットを選択できます。 それから、各セットの要素をあなたに伝えることができます. そのメッセージを送信するために必要な情報量は、それらの要素が何であるかについての不確実性の量を反映しています。たとえば、最初のセットの最初の要素が 1 である可能性は 1% です (50 は、 XNUMX% の確率で、公正なコイン投げの最初の結果が表になります。
情報理論は、ギルマーが大学院生として学んだオブジェクトのカウントに関係する数学の分野である組み合わせ論によく登場します。 しかし、彼がカリフォルニアに帰国したとき、彼は、情報理論を閉鎖連合予想に結びつけようと考えた方法が、アマチュアのナイーブな洞察ではないかと心配しました。 .
「正直に言うと、これまで誰も考えなかったことに少し驚いています」と Gilmer 氏は言います。 「でも、私自身が XNUMX 年間それについて考えていて、情報理論を知っていたので、驚くべきではないかもしれません。」
可能性が高い
ギルマーは、Google での仕事を終えた夜と、XNUMX 月後半から XNUMX 月初旬にかけての週末に、この問題に取り組みました。 彼は、数学者のグループが何年も前に研究したアイデアに勇気づけられました。 オープンなコラボレーション Tim Gowers という名の著名な数学者のブログで。 彼はまた、忘れていた公式を調べることができるように、教科書をそばに置いて作業しました。
「素晴らしい結果を思いついた人は、本書の第 2 章を参照する必要はないと思うでしょう。 情報理論の要素、しかし私はそうしました」とギルマーは言いました。
ギルマーの戦略は、すべてのセットの 1% にさえ要素が現れない組合閉鎖家族を想像することでした。これは、もしそれが実際に存在するなら、フランクルの予想を反証する反例です。
このファミリから A と B の 1 つのセットを無作為に選択し、それらのセットに含まれる要素を 1 つずつ検討するとします。 ここで次の質問をします。セット A に数字 1 が含まれる確率はどれくらいですか? そしてセットB？ すべての要素が特定のセットに出現する可能性は XNUMX% 弱なので、A または B のいずれかに XNUMX が含まれているとは思わないでしょう。します。
次に、A と B の和集合に 1 が含まれる可能性について考えてみます。まだ可能性は低いですが、個々のセットのいずれかに現れる可能性よりも可能性が高いです。 これは、A に現れる可能性と B に現れる可能性の合計から、両方に現れる可能性を引いたものです。 だから、たぶん2％弱。
これはまだ低いですが、50 対 50 の命題に近づいています。 つまり、結果を共有するにはより多くの情報が必要です。 言い換えれば、すべてのセットの少なくとも 1% に要素が表示されないユニオン クローズド ファミリがある場合、セット自体のいずれかよりも XNUMX つのセットのユニオンに多くの情報があります。
「物事を要素ごとに明らかにし、学習した情報の量を見るというアイデアは非常に賢いです。 それが証明の主な考え方です」と彼は言いました。 ライアン・アルワイス プリンストン大学の。
この時点で、ギルマーはフランクルの予想に近づき始めていた. これは、結合が閉じたファミリでは、XNUMX つのセットの結合に含まれる情報がセット自体よりも少なく、多くないことを示すのは簡単だからです。
その理由を理解するために、1,024 から 1 までの数字から作成できる 10 の異なるセットを含む、和集合で閉じられたファミリについて考えてみてください。これらのセットからランダムに 1,024 つを選択すると、平均して 252 つの要素を含むセットになります。 (これらの 120 個のセットのうち、XNUMX 個には XNUMX つの要素が含まれており、これが最も一般的なセット サイズです。) また、約 XNUMX つの要素を含む和集合になる可能性もあります。 しかし、XNUMX つの要素を含むセットを作成する方法は XNUMX 通りしかありません。
要点は、ランダムに選択された XNUMX つのセットの内容については、結合についてよりも不確実性が高いということです。 和集合は、より多くの要素を持つより大きなセットに偏り、その可能性はより少なくなります。 結合が閉じられたファミリで XNUMX つのセットの結合を取ると、偏ったコインを投げるときのように、何が得られるかがわかります。つまり、結合には、それを構成するセットよりも少ない情報が含まれることを意味します。
それでギルマーは証拠を掴んだ。 彼は、セットの 1% にさえ要素が表示されない場合、ユニオンにさらに多くの情報を含めることを余儀なくされることを知っていました。 ただし、共用体に含まれる情報は少なくて済みます。 したがって、セットの少なくとも 1% に現れる要素が少なくとも XNUMX つ必要です。
50へのプッシュ
ギルマーが 16 月 38 日に証明を投稿したとき、彼は、彼の方法を使用して完全な予想の証明にさらに近づくことが可能であり、しきい値を XNUMX% に引き上げる可能性があると考えているというメモを含めました。
五日後、 三 異なります グループヘッド 数学者の数は、まさにそれを行うためにギルマーの仕事に基づいて構築された論文を互いに数時間以内に投稿しました. NEW 論文 続いて、しかし、最初のバーストは、ギルマーの方法を可能な限り採用したようです。 50% に到達するには、追加の新しいアイデアが必要になる可能性があります。
それでも、フォローアップ論文の著者の何人かにとっては、38% に到達することは比較的簡単であり、ギルマーが自分でそれをしなかった理由を疑問に思っていました. 最も単純な説明は正しいものであることが判明しました.XNUMX年以上数学から離れた後、ギルマーはそれをやってのけるために必要な技術的分析作業のいくつかを行う方法を知りませんでした.
「私は少し錆びていて、正直言って行き詰まりました」とギルマーは言いました。 「しかし、私はコミュニティがそれをどこに持っていくのかを見たいと思っていました。」
それでもギルマーは、彼を実践から遠ざけたのと同じ状況が、おそらくそもそも彼の証明を可能にしたと考えています。
「大学院で XNUMX 年間この問題について考えたのに進歩しなかった理由を説明できる唯一の方法です。数学を XNUMX 年間やめてから問題に戻って、この突破口を見つけたのです」と彼は言いました。 「機械学習をしていることが私の思考に偏りを与えたということ以外に、それを説明する方法がわかりません。」
訂正： 2023 年 1 月 3 日
元の見出しは、ギルマーを「Google エンジニア」と呼んでいました。 実は研究者です。
