Bekerja pada waktu siang dan melakukan penyelidikan pada waktu malam, saintis penyelidikan Google Brain menyelesaikan satu tekaan yang membingungkan komuniti matematik selama beberapa dekad.

Pada pertengahan Oktober 2022, Justin Gilmer terbang dari California ke New York untuk melawat bekas mentornya Michael Saks, seorang ahli matematik di Universiti Rutgers, di Pantai Timur.

Semasa mengenang, mereka tidak bercakap tentang matematik. Malah, Gilmer tidak memikirkan secara serius tentang matematik sejak memperoleh PhD di Universiti Rutgers pada 2015. Pada masa itu, dia memutuskan untuk tidak meneruskan kerjaya dalam bidang akademik dan mula mengajar dirinya pengaturcaraan. Semasa makan malam bersama Saks, Gilmer memberitahu mentornya tentang kerjanya di Google: pembelajaran mesin dan kecerdasan buatan.

Semasa berjalan di laluan kampus, Gilmer teringat bahawa pada tahun 2013, dia menghabiskan lebih daripada setahun berjalan di laluan ini, memikirkan masalah yang dipanggil "tekaan set tertutup kesatuan (juga ( dipanggil Frankl konjektur)" masalah. Ini selalu menjadi masalah yang tidak membuahkan hasil. Untuk semua usahanya, Gilmer hanya berjaya mengajar dirinya sendiri mengapa masalah yang kelihatan mudah tentang koleksi nombor ini sangat sukar untuk diselesaikan.

Tetapi selepas lawatan ini tujuh tahun kemudian, Gilmer tiba-tiba mendapat inspirasi baharu. Dia mula memikirkan bagaimana mengaplikasikan teori maklumat untuk menyelesaikan dan menutup sangkaan yang ditetapkan. Selepas sebulan penyelidikan, laluan kepada pembuktian terus dibuka. Pada bulan November, beliau menerbitkan keputusan di arXiv, mengumumkan kemajuan ketara dalam membuktikan keseluruhan sangkaan.

Pautan kertas: https://arxiv.org/pdf/2211.09055.pdf

Kertas kerja ini mencetuskan gelombang penyelidikan seterusnya. Ahli matematik di Universiti Oxford, MIT, dan Institut Kajian Lanjutan, antara lain, dengan cepat mula mengusahakan kaedah baharu Gilmer.

Apakah sangkaan set tertutup kesatuan?

Konjektur set tertutup berkaitan dengan set nombor, seperti {1, 2} dan {2, 3, 4}. Anda boleh melakukan operasi pada set, termasuk mengambil kesatuan mereka, yang menggabungkan mereka. Contohnya, gabungan {1, 2} dan {2, 3, 4} ialah {1, 2, 3, 4}.

Sebuah set atau keluarga dikatakan "tertutup kesatuan" jika penyatuan mana-mana dua set dalam keluarga adalah sama dengan set sedia ada dalam keluarga. Sebagai contoh, pertimbangkan keluarga empat set ini: {1}, {1, 2}, {2, 3, 4}, {1, 2, 3, 4}.

Menggabungkan mana-mana pasangan, anda akan mendapat set yang sudah ada dalam keluarga, jadi keluarga ini dikatakan set tertutup.

Ahli matematik telah membincangkan tekaan set tertutup seawal tahun 1960-an, tetapi tidak sampai tahun 1979 ia menerima kenyataan rasmi pertamanya, dalam artikel oleh Péter Frankl Dalam kertas itu, beliau ialah seorang ahli matematik Hungary yang berhijrah ke Jepun pada tahun 1980-an Selain matematik, dia juga suka persembahan jalanan.

Frankl menjangkakan bahawa jika keluarga set adalah penutup kesatuan, maka ia mesti mempunyai sekurang-kurangnya satu elemen (atau nombor) yang muncul dalam sekurang-kurangnya separuh daripada set. Ini adalah ambang yang berlaku secara semula jadi kerana dua sebab.

​

Justin Gilmer

Pertama semua, Dalam contoh set keluarga sedia dan tertutup, semua elemen muncul tepat 50% daripada set. Sebagai contoh, anda boleh menggunakan nombor 1 hingga 10 untuk membentuk semua set yang berbeza, menghasilkan sejumlah 1024 set tersebut. Mereka membentuk keluarga tertutup sebanyak 512 set di mana setiap satu daripada 10 elemen muncul.

Apabila Frankl mencadangkan sangkaan ini, belum ada sesiapa yang mencadangkan contoh keluarga himpunan tertutup di mana sangkaan itu tidak benar. Jadi 50% nampaknya ramalan yang betul.

Itu tidak bermakna ia mudah untuk dibuktikan. Sebelum kerja Gilmer, banyak kertas kerja hanya berjaya menetapkan ambang yang berbeza dengan bilangan set dalam keluarga (bukannya ambang 50% yang sama untuk semua saiz keluarga set).

Will Sawin dari Columbia University berkata: "Rasanya ia sepatutnya mudah, dan ia serupa dengan banyak masalah mudah, tetapi ia tidak pernah ditakluki."

Kekurangan kemajuan mencerminkan kedua-dua sifat sukar diatasi masalah dan hakikat bahawa ramai ahli matematik lebih suka tidak memikirkannya. Mereka bimbang bahawa mereka akan membuang tahun kerjaya mereka mengejar masalah yang mustahil. Gilmer masih ingat pada satu hari pada tahun 2013, apabila dia pergi ke pejabat Saks dan menyebut perkara ini dan sangkaan tertutup, dan pengajar, yang juga bergelut dengan masalah itu, menendangnya keluar dari bilik.

Cerapan tentang Ketidakpastian

Selepas melawat Rutgers, Gilmer melancarkan soalan itu ke dalam fikirannya, cuba memahami mengapa ia begitu sukar. Dia mengingatkan dirinya tentang fakta asas: Jika anda mempunyai keluarga 100 kombinasi set, terdapat 4950 cara berbeza untuk memilih dua dan menggabungkannya. Kemudian dia berfikir: Bagaimanakah 4950 kombinasi berbeza boleh memetakan kepada 100 set jika tiada unsur muncul dalam gabungan ini sekurang-kurangnya dengan kekerapan tertentu?

Pada ketika ini, dia sudah pun menuju ke arah penyelesaian, walaupun dia belum mengetahuinya.

Teori maklumat telah dibangunkan pada separuh pertama abad ke-20, terutamanya dalam karya Claude Shannon 1948 "A Mathematical Theory of Communication." Kertas ini menyediakan cara yang tepat untuk mengira jumlah maklumat yang diperlukan untuk menghantar mesej, berdasarkan jumlah ketidakpastian yang mengelilingi apa yang dinyatakan oleh mesej itu. Hubungan antara maklumat dan ketidakpastian ini adalah pandangan Shannon yang luar biasa.

Teori maklumat sering muncul dalam kombinatorik, bidang matematik yang berkaitan dengan mengira objek yang Gilmer pelajari sebagai pelajar siswazah. Tetapi semasa dia terbang pulang ke California, dia bimbang bahawa cara dia mengaitkan teori maklumat dengan tekaan set tertutup kesatuan adalah kenaifan seorang amatur.

"Sejujurnya, saya agak terkejut tiada siapa yang memikirkan perkara ini sebelum ini," kata Gilmer. "Tetapi mungkin saya tidak perlu terkejut, kerana saya sendiri telah memikirkannya selama setahun, dan saya tahu teori maklumat datang dari kecintaan saya terhadap matematik." Dia terutamanya sibuk dengan kerja hariannya di Google pada hari bekerja, dan menumpukan dirinya untuk mengkaji masalah matematik pada masa lapangnya. Dia juga membawa buku teks matematik bersamanya untuk bekerja supaya dia boleh mencari formula yang terlupa pada bila-bila masa. Gilmer mengekalkan kakinya di atas tanah tetapi juga melihat ke bintang-bintang—dia suka membaca blog ahli matematik terkenal Tim Gowers, yang membuatkannya terus terinspirasi.

Gilmer berkata dengan sederhana: "Mungkin anda fikir orang yang menyelesaikan masalah matematik yang sukar tidak sepatutnya merujuk Bab 2 Teori Elemen Maklumat, tetapi saya melakukannya."

Pendekatan yang dicadangkan oleh Gilmer adalah untuk membayangkan keluarga set tertutup di mana kebarangkalian sebarang elemen muncul dalam semua set adalah kurang daripada 1%. Ini adalah contoh balas yang, jika benar, akan memalsukan sangkaan Frankl.

Andaikan dua set A dan B dipilih secara rawak daripada keluarga ini, tanya: Apakah kebarangkalian set A mengandungi nombor 1? Bagaimana dengan set B? Oleh kerana kebarangkalian setiap elemen muncul dalam mana-mana set adalah kurang sedikit daripada 1%, anda tidak seharusnya mengharapkan A atau B mengandungi 1. Ini bermakna kita tidak akan terkejut jika kedua-duanya tidak mengandungi 1, dan pastinya tidak akan mendapat banyak maklumat.

Seterusnya, pertimbangkan kebarangkalian bahawa gabungan A dan B mengandungi 1. Ini masih tidak mungkin, tetapi lebih besar sedikit daripada kebarangkalian 1 muncul dalam mana-mana set sahaja, dan merupakan jumlah kebarangkalian 1 muncul dalam A dan kebarangkalian 1 muncul dalam B tolak kebarangkalian 1 muncul dalam kedua-duanya. Jadi kebarangkalian bahawa gabungan A dan B mengandungi 1 adalah kira-kira kurang daripada 2%.

Ini masih rendah, tetapi lebih hampir kepada 50% tekaan, bermakna lebih banyak maklumat diperlukan sebelum keputusan boleh dikongsi. Dalam erti kata lain, jika terdapat keluarga set yang melampirkan kesatuan di mana kebarangkalian mana-mana elemen muncul dalam semua set adalah kurang daripada 1%, maka gabungan dua set mengandungi lebih banyak maklumat daripada mana-mana set dengan sendirinya.

"Idea untuk membuktikan unsur tekaan demi unsur adalah sangat bijak," komen Ryan Alweiss dari Universiti Princeton.

Karya Gilmer mula mendekati sangkaan Frankl. Ini kerana adalah mudah untuk menunjukkan bahawa dalam keluarga set tertutup kesatuan, gabungan dua set mesti mengandungi kurang maklumat daripada dua set itu sendiri—bukan lebih.

Alasannya mudah, ambil keluarga set tertutup kesatuan yang mengandungi 1024 set berbeza sebagai contoh. Jika dua set ini dipilih secara rawak, secara purata, gabungan lima elemen akan diperolehi. (Daripada 1024 set, 252 mengandungi lima elemen, yang merupakan saiz set yang paling biasa.) Ada kemungkinan juga kita akan mendapat gabungan kira-kira tujuh elemen. Tetapi terdapat hanya 120 kombinasi cara yang berbeza untuk mendapatkan gabungan tujuh elemen.

Maksudnya ialah dua set yang dipilih secara rawak mengandungi unsur-unsur dengan lebih ketidakpastian daripada kesatuan mereka. Kesatuan lebih seperti set yang lebih besar dengan lebih banyak elemen dan kemungkinan yang lebih sedikit. Apabila anda melakukan operasi kesatuan pada dua set dalam keluarga set tertutup kesatuan, anda mungkin mengetahui keputusan kesatuan itu, sama seperti melambung syiling berat sebelah Anda boleh meneka dengan mudah di sebelah mana syiling akan mendarat daripada dua set itu sendiri.

Berdasarkan perkara ini, Gilmer percaya bahawa kebarangkalian sekurang-kurangnya satu elemen muncul dalam set adalah lebih besar daripada atau sama dengan 1%.

Apa yang hilang akan diperoleh

Apabila Gilmer menerbitkan buktinya pada 16 November, dia menyertakan nota - Dia percaya bahawa menggunakan kaedahnya mungkin lebih dekat dengan bukti daripada sangkaan lengkap, berpotensi meningkatkan ambang kepada 38%.

Lima hari kemudian, tiga kumpulan ahli matematik yang berbeza menerbitkan kertas kerja dalam beberapa jam antara satu sama lain yang dibina berdasarkan kerja Gilmer. Wabak itu nampaknya telah mendorong pendekatan Gilmer ke tahap yang melampau, walaupun mencapai 50 peratus mungkin memerlukan lebih banyak idea baharu.

Namun, bagi sesetengah pengarang kertas susulan, mereka tertanya-tanya mengapa Gilmer tidak melakukan kajian 38% yang agak mudah itu sendiri. Sebenarnya, sebabnya tidak rumit: selepas lebih 5 tahun meninggalkan matematik, Gilmer hanya tidak tahu bagaimana untuk melakukan kerja analisis teknikal untuk mencapai matlamat ini.

"Saya agak berkarat, dan sejujurnya, saya tersekat," kata Gilmer. "Tetapi saya ingin tahu ke mana komuniti matematik akan mengambilnya."

Tetapi Gilmer juga percaya bahawa sebab yang sama menyebabkan dia kehilangan peluang berlatih juga, sedikit sebanyak, merugikan dia. Buktinya mula-mula menjadi mungkin: "Ini adalah satu-satunya penjelasan - mengapa saya memikirkan masalah ini selama setahun di sekolah siswazah dan tidak membuat kemajuan, dan kemudian kembali kepada masalah ini selepas enam tahun meninggalkan matematik dan membuat satu kejayaan. Sebagai tambahan kepada pembelajaran mesin, saya tidak tahu penjelasan lain selain perubahan fikiran saya.”

Atas ialah kandungan terperinci Bekerja pada waktu siang dan melakukan penyelidikan pada waktu malam, saintis penyelidikan Google Brain menyelesaikan satu tekaan yang membingungkan komuniti matematik selama beberapa dekad.. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!