esittely
Lokakuun puolivälissä, Justin Gilmer lensi Kaliforniasta New Yorkiin osallistuakseen ystävän häihin. Itärannikolla hän vieraili entisen neuvonantajansa luona, Michael Saks, matemaatikko Rutgersin yliopistossa, jossa Gilmer oli suorittanut tohtorin tutkinnon seitsemän vuotta aiemmin.
Saks ja Gilmer tapasivat lounaalla, mutta he eivät puhuneet matematiikasta. Itse asiassa Gilmer ei ollut ajatellut vakavasti matematiikkaa sen jälkeen, kun hän valmistui Rutgersista vuonna 2015. Silloin hän päätti, ettei hän halunnut uraa akateemisessa maailmassa, ja alkoi sen sijaan opettaa itse ohjelmointia. Kun hän ja Saks söivät, Gilmer kertoi vanhalle mentorilleen työstään Googlessa, jossa hän työskentelee koneoppimisen ja tekoälyn parissa.
Oli aurinkoinen päivä Gilmer vieraili Rutgersissa. Kävellessään ympäriinsä hän muisteli, kuinka vuonna 2013 hän oli viettänyt suurimman osan vuodesta kävellen samoilla kampuspoluilla pohtien ongelmaa, jota kutsutaan ammattiliiton sulkeutuneeksi olettamukseksi. Se oli ollut kiinnitys, vaikkakin hedelmätön: Kaikesta ponnisteluistaan huolimatta Gilmer oli vain onnistunut opettamaan itselleen, miksi numerojoukkoja koskeva yksinkertaiselta vaikuttava ongelma oli niin vaikea ratkaista.
”Uskon, että monet ihmiset ajattelevat ongelmaa, kunnes he ovat tyytyväisiä ymmärtävänsä, miksi se on vaikeaa. Vietin siihen todennäköisesti enemmän aikaa kuin useimmat ihmiset, Gilmer sanoi.
Lokakuun vierailunsa jälkeen tapahtui jotain odottamatonta: Hän sai uuden idean. Gilmer alkoi miettiä tapoja soveltaa informaatioteorian tekniikoita liiton suljetun arvelun ratkaisemiseksi. Hän jatkoi ideaa kuukauden ajan odottaen joka käänteessä sen epäonnistuvan. Mutta sen sijaan polku todisteeseen avautui jatkuvasti. Lopulta 16. marraskuuta hän julkaisi lajissaan ensimmäisen tuloksen joka saa matemaatikot suuren osan tiestä todistamaan täydelliset olettamukset.
Lehti käynnisti jatkuvan seurantatyön. Oxfordin yliopiston, Massachusetts Institute of Technologyn ja Institute for Advanced Studyn matemaatikot rakensivat nopeasti Gilmerin uusille menetelmille. Mutta ennen kuin he tekivät, he esittivät oman kysymyksensä: Kuka tämä kaveri on?
Puoliksi täynnä
Suljettu liitto oletus koskee lukukokoelmia, joita kutsutaan joukoiksi, kuten {1, 2} ja {2, 3, 4}. Voit suorittaa sarjoille operaatioita, mukaan lukien niiden yhdistämisen, mikä tarkoittaa niiden yhdistämistä. Esimerkiksi {1, 2} ja {2, 3, 4} liitto on {1, 2, 3, 4}.
Joukkokokoelmaa tai -perhettä pidetään "suljetun liitonna", jos minkä tahansa perheen kahden joukon liitto vastaa mitä tahansa perheessä olevaa joukkoa. Ajatellaanpa esimerkiksi tätä neljän sarjan perhettä:
{1}, {1, 2}, {2, 3, 4}, {1, 2, 3, 4}.
Yhdistä mikä tahansa pari ja saat sarjan, joka on jo perheessä, mikä tekee perheliitosta suljetun.
Matemaatikot keskustelivat liiton suljetun arvelun versioista jo 1960-luvulla, mutta se sai ensimmäisen virallisen lausuntonsa vuonna 1979 kirjoittamassaan paperissa. Péter Frankl, unkarilainen matemaatikko, joka muutti Japaniin 1980-luvulla ja jonka harrastuksiin kuuluu katuesityksiä.
Frankl arveli, että jos joukkojen perhe on liitossuljettu, siinä täytyy olla vähintään yksi alkio (tai luku), joka esiintyy vähintään puolessa joukoista. Se oli luonnollinen kynnys kahdesta syystä.
Ensinnäkin on helposti saatavilla esimerkkejä liiton suljetuista perheistä, joissa kaikki elementit esiintyvät tasan 50 %:ssa joukoista. Kuten kaikki erilaiset sarjat, joita voit tehdä esimerkiksi numeroista 1-10. Tällaisia joukkoja on 1,024 10, jotka muodostavat suljetun perheen, ja jokainen 512 elementistä esiintyy niistä XNUMX:ssa. Ja toiseksi, kun Frankl teki olettamuksen, kukaan ei ollut koskaan tuottanut esimerkkiä ammatillisesta perheestä, jossa olettamus ei pädenyt.
Joten 50 % vaikutti oikealta ennusteelta.
Se ei tarkoittanut, että sen todistaminen oli helppoa. Franklin paperin jälkeisten vuosien aikana tuloksia on vain vähän. Ennen Gilmerin työtä nämä paperit onnistuivat vain määrittämään kynnysarvot, jotka vaihtelivat perheen joukkojen lukumäärän mukaan (toisin kuin sama 50 %:n kynnys kaikenkokoisille sarjaperheille).
"Tuntuu siltä, että sen pitäisi olla helppoa, ja se on samanlainen kuin monet ongelmat, jotka ovat helppoja, mutta se on vastustanut hyökkäyksiä", sanoi Will Sawin Columbian yliopistosta.
Edistyksen puute heijasti sekä ongelman hankalaa luonnetta että sitä tosiasiaa, että monet matemaatikot halusivat olla ajattelematta sitä; he pelkäsivät menettävänsä vuosia urastaan jahtaaessaan houkuttelevaa ongelmaa, jota oli mahdotonta ratkaista. Gilmer muistaa päivän vuonna 2013, kun hän meni Saksin toimistoon ja otti esille ammattiliiton sulkeutuneen arvelun. Hänen neuvonantajansa - joka oli aiemmin paininut ongelman kanssa - melkein heitti hänet ulos huoneesta.
"Mike sanoi: "Justin, saat minut ajattelemaan tätä ongelmaa uudelleen, enkä halua tehdä sitä", Gilmer sanoi.
Näkemys epävarmuudesta
Vierailun jälkeen Rutgersissa Gilmer pyöritti ongelmaa mielessään yrittäen ymmärtää, miksi se oli niin vaikeaa. Hän kehotti itseään perusasialla: Jos sinulla on 100 sarjan perhe, on olemassa 4,950 4,950 eri tapaa valita kaksi ja ottaa niiden liiton. Sitten hän kysyi itseltään: Kuinka on mahdollista, että 100 XNUMX erilaista liittoa kartoittuu vain XNUMX joukkoon, jos mitään elementtiä ei esiinny näissä liitoissa vähintään jollain taajuudella?
Jo tuolloin hän oli matkalla todisteeseen, vaikka hän ei tiennyt sitä vielä. Tietoteorian tekniikat, jotka tarjoavat tiukan ajattelutavan siitä, mitä odottaa, kun vedät esineparia satunnaisesti, vievät hänet sinne.
Tietoteoria kehittyi 20-luvun alkupuolella, tunnetuimmin Claude Shannonin vuoden 1948 artikkelissa "Viestinnän matemaattinen teoria.” Paperi tarjosi tarkan tavan laskea viestin lähettämiseen tarvittavan tiedon määrä, joka perustuu epävarmuuteen siitä, mitä viesti tarkalleen ottaen sanoisi. Tämä linkki - tiedon ja epävarmuuden välillä — oli Shannonin merkittävä, perustavanlaatuinen oivallus.
Esimerkkinä leluista kuvittele, että heitän kolikon viisi kertaa ja lähetän tuloksena olevan sarjan sinulle. Jos se on tavallinen kolikko, sen lähettämiseen tarvitaan viisi bittiä tietoa. Mutta jos se on ladattu kolikko – esimerkiksi 99 %:n todennäköisyys putoaa pään päälle – se vie paljon vähemmän. Voisimme esimerkiksi sopia etukäteen, että lähetän sinulle 1 (yksi bitti tietoa), jos ladattu kolikko laskeutuu kaikki viisi kertaa, mikä on erittäin todennäköistä. Reilun kolikonheiton lopputuloksessa on enemmän yllätystä kuin puolueellisessa, ja siksi enemmän tietoa.
Sama ajattelu pätee lukujoukkojen sisältämään tietoon. Jos minulla on ryhmä suljettuja sarjoja – esimerkiksi 1,024 1 sarjaa, jotka on tehty luvuista 10–50 – voisin valita kaksi sarjaa satunnaisesti. Sitten voisin kertoa sinulle kunkin sarjan elementit. Viestin lähettämiseen tarvittavan tiedon määrä kuvastaa näiden elementtien epävarmuuden määrää: On esimerkiksi 1 % todennäköisyys, että ensimmäisen joukon ensimmäinen elementti on 1 (koska 50 esiintyy puolessa joukosta perhe), aivan kuten on XNUMX %:n todennäköisyys, että reilun kolikonheiton sarjan ensimmäinen tulos on päitä.
Informaatioteoria esiintyy usein kombinatoriikassa, matematiikan alueella, joka liittyy esineiden laskemiseen, mitä Gilmer oli opiskellut jatko-opiskelijana. Mutta kun hän lensi takaisin kotiin Kaliforniaan, hän oli huolissaan siitä, että tapa, jolla hän ajatteli yhdistävänsä informaatioteorian suljetun liiton olettamukseen, oli amatöörin naiivi näkemys: Varmasti työskentelevät matemaatikot olivat törmänneet tähän kiiltävään esineeseen aiemmin ja tunnistaneet sen hölyn kullaksi. .
"Ollakseni rehellinen, olen hieman yllättynyt, ettei kukaan ajatellut tätä aiemmin", Gilmer sanoi. "Mutta ehkä minun ei pitäisi olla yllättynyt, koska olin itse miettinyt asiaa vuoden ja tiesin informaatioteorian."
Todennäköisemmin kuin ei
Gilmer työskenteli ongelman parissa yöllä Googlen työnsä päätyttyä ja viikonloppuisin lokakuun jälkipuoliskolla ja marraskuun alussa. Häntä rohkaisivat ajatukset, joita ryhmä matemaatikoita oli tutkinut vuosia aiemmin vuonna avointa yhteistyötä tunnetun matemaatikon Tim Gowersin blogissa. Hän työskenteli myös oppikirja rinnallaan, jotta hän voisi etsiä kaavoja, jotka hän oli unohtanut.
”Luulisi, että jonkun, joka saa hyvän tuloksen, ei pitäisi joutua tutustumaan luvun 2 Tietoteorian elementit, mutta tein sen", Gilmer sanoi.
Gilmerin strategiana oli kuvitella liittosuljettu perhe, jossa mitään elementtiä ei esiintynyt edes 1 %:ssa kaikista joukoista – vastaesimerkki, joka, jos se todella olisi olemassa, väärentäisi Franklin olettamuksen.
Oletetaan, että valitset tästä perheestä satunnaisesti kaksi joukkoa, A ja B, ja harkitset elementtejä, jotka voisivat olla näissä joukoissa, yksi kerrallaan. Kysy nyt: Mitkä ovat kertoimet, että joukko A sisältää luvun 1? Ja aseta B? Koska jokaisen elementin todennäköisyys esiintyä missä tahansa tietyssä joukossa on hieman alle 1 %, et odottaisi A:n tai B:n sisältävän ykköstä. Tämä tarkoittaa, että ei ole juurikaan yllätyksiä – ja vain vähän tietoa –, jos huomaat, että kumpikaan ei itse asiassa tekee.
Ajattele seuraavaksi mahdollisuutta, että A:n ja B:n liitto sisältää luvun 1. Se on silti epätodennäköistä, mutta todennäköisempää on, että se esiintyy jommassakummassa yksittäisessä joukossa. Se on summa sen todennäköisyydestä, että se esiintyy A:ssa ja todennäköisyydellä, että se esiintyy B:ssä miinus todennäköisyys, että se esiintyy molemmissa. Eli ehkä hieman alle 2 %.
Tämä on edelleen alhainen, mutta se on lähempänä 50-50-ehdotusta. Tämä tarkoittaa, että tuloksen jakaminen vaatii enemmän tietoa. Toisin sanoen, jos on liittosuljettu perhe, jossa mitään elementtiä ei esiinny vähintään 1 %:ssa kaikista joukoista, kahden joukon liitossa on enemmän tietoa kuin kummassakaan joukossa itse.
”Ajatus paljastaa asioita elementti kerrallaan ja tarkastella oppimaasi tiedon määrää on erittäin fiksu. Se on todisteen pääidea”, sanoi Ryan Alweiss Princetonin yliopistosta.
Tässä vaiheessa Gilmer alkoi lähestyä Franklin olettamusta. Tämä johtuu siitä, että on helppo osoittaa, että suljetussa perheessä kahden joukon liitto sisältää välttämättä vähemmän tietoa kuin itse joukot – ei enempää.
Nähdäksesi syyn, ajattele tuota liiton suljettua perhettä, joka sisältää 1,024 1 erilaista sarjaa, jotka voit muodostaa numeroista 10-1,024. Jos valitset satunnaisesti kaksi näistä sarjoista, päädyt keskimäärin viisi elementtiä sisältäviin sarjoihin. (Näistä 252 120 joukosta XNUMX sisältää viisi elementtiä, mikä tekee siitä yleisimmän joukon koon.) Saatat myös todennäköisesti päätyä liittoon, joka sisältää noin seitsemän elementtiä. Mutta seitsemän elementtiä sisältävien sarjojen tekemiseen on vain XNUMX erilaista tapaa.
Asia on siinä, että kahden satunnaisesti valitun joukon sisällöstä on enemmän epävarmuutta kuin niiden liitosta. Liitto kallistuu suurempiin sarjoihin, joissa on enemmän elementtejä, joihin on vähemmän mahdollisuuksia. Kun otat kahden sarjan liiton liiton suljetussa perheessä, tiedät tavallaan, mitä saat – kuten kun käännät puolueellisen kolikon – mikä tarkoittaa, että liitto sisältää vähemmän tietoa kuin sarjat, joista se koostuu.
Siitä Gilmerillä oli todiste. Hän tiesi, että jos mitään elementtiä ei esiinny edes 1 %:ssa sarjoista, liiton on pakko sisältää enemmän tietoa. Mutta liiton pitää sisältää vähemmän tietoa. Siksi vähintään yhden elementin on oltava vähintään 1 %:ssa joukoista.
Push to 50
Kun Gilmer julkaisi todisteensa 16. marraskuuta, hän lisäsi huomautuksen, jonka mukaan hänen mielestään hänen menetelmänsä avulla oli mahdollista päästä vielä lähemmäksi todistetta täydellisestä oletuksesta, mikä saattaa nostaa kynnyksen 38 prosenttiin.
Viisi päivää myöhemmin, kolmella eri ryhmät matemaatikot lähettivät muutaman tunnin sisällä toisistaan papereita, jotka perustuivat Gilmerin työhön tehdäkseen juuri sen. lisä- paperit seurannut, mutta ensimmäinen purske näyttää vieneen Gilmerin menetelmät niin pitkälle kuin mahdollista; 50 prosenttiin pääseminen vaatii todennäköisesti lisää uusia ideoita.
Silti joillekin seurantapaperien tekijöille 38 prosentin saavuttaminen oli suhteellisen yksinkertaista, ja he ihmettelivät, miksi Gilmer ei vain tehnyt sitä itse. Yksinkertaisin selitys osoittautui oikeaksi: Yli puolen vuosikymmenen matematiikan opiskelun jälkeen Gilmer ei vain tiennyt, kuinka tehdä teknistä analyyttistä työtä, joka vaadittiin sen saavuttamiseksi.
"Olin hieman ruosteessa, ja rehellisesti sanottuna olin jumissa", Gilmer sanoi. "Mutta olin innokas näkemään, mihin yhteisö ottaisi sen."
Silti Gilmer ajattelee, että samat olosuhteet, jotka jättivät hänet pois harjoittelusta, tekivät todennäköisesti hänen todisteensa mahdolliseksi.
"Se on ainoa tapa selittää, miksi ajattelin ongelmaa vuoden tutkijakoulussa enkä edistynyt, jätin matematiikan kuudeksi vuodeksi, palasin sitten ongelmaan ja tein tämän läpimurron", hän sanoi. "En osaa selittää sitä muuten kuin koneoppimisessa oleminen puolueellinen ajatteluni."
korjaus: Tammikuu 3, 2023
Alkuperäisessä otsikossa viitattiin Gilmeriin "Google-insinööriksi". Itse asiassa hän on tutkija.
