OpenAI mudel lükkas ümber diskreetse geomeetria keskse hüpoteesi

Peaaegu 80 aastat on matemaatikud uurinud petlikult lihtsat küsimust: kui paigutada tasandile $n$ punkti, siis mitu punktipaari saab olla täpselt kaugusel $1$?

See on tasandiliste ühikkauguste probleem, mille esitas esimesena Paul Erdős 1946. aastal. See on kombinatoorse geomeetria üks tuntumaid küsimusi – lihtne sõnastada, kuid märkimisväärselt keeruline lahendada. Brassi, Moseri ja Pachi 2005. aasta raamat „Research Problems in Discrete Geometry” nimetab seda „tõenäoliselt kõige tuntumaks (ja kõige lihtsamini selgitatavaks) probleemiks kombinatoorses geomeetrias”. Princetoni ülikooli juhtiv kombinatoorikateadlane Noga Alon kirjeldab seda kui „ühte Erdősi lemmikprobleemi”. Erdős pani selle probleemi lahendamise eest välja isegi rahalise auhinna.

Täna jagame läbimurret ühiku kauguse probleemis. Alates Erdősi algsest tööst on valitsenud uskumus, et allpool kujutatud „ruutvõrgu” konstruktsioonid olid ühikukaugusega paaride arvu maksimeerimiseks sisuliselt optimaalsed. OpenAI sisemine mudel lükkas selle pikaajalise hüpoteesi ümber, pakkudes lõputut hulka näiteid, mis annavad polünoomilise paranduse. Tõestust on kontrollinud rühm sõltumatuid matemaatikuid. Nad on kirjutanud ka kaasartikli, milles selgitavad oma argumente ja annavad tulemuse tähtsuse kohta täiendavat taustteavet ja konteksti.

Tähelepanuväärne on ka see, kuidas tulemuseni jõuti. Tõestus tuli uuest üldotstarbelisest arutlusmudelist, mitte süsteemist, mis oleks treenitud spetsiaalselt matemaatika jaoks, üles ehitatud tõestusstrateegiate läbiotsimiseks või suunatud konkreetselt ühiku kauguse probleemile. Osana laiemast püüdest testida, kas arenenud mudelid suudavad panustada tipptasemel teadustöösse, hindasime seda Erdősi probleemide kogumikul. Sel juhul esitati tõestus, mis lahendas selle lahendamata probleemi.

See tõestus on oluline verstapost matemaatika- ja tehisintellekti valdkonnas. See on esimene kord, kui matemaatika ühe alavaldkonna keskne silmapaistev lahendamata probleem on tehisintellekti poolt autonoomselt lahendatud. See näitab ka nende süsteemide arutluse sügavust. Matemaatika pakub arutluse jaoks eriti selget katsekeskkonda: probleemid on täpsed, võimalikke tõestusi saab kontrollida ja pikk argument töötab ainult siis, kui mõttekäik on algusest lõpuni järjepidev. Tähelepanuväärne on ka meetod, millega probleem lahendati. Tõestus rakendab elementaarsele geomeetrilisele küsimusele ootamatuid ja keerukaid ideid algebralisest arvuteooriast.

Fieldsi medali laureaat Tim Gowers nimetab kaasartiklis seda tulemust „tehisintellekti matemaatika verstapostiks“. Tuntud arvuteoreetiku Arul Shankari sõnul „näitab see artikkel minu arvates, et tänapäevased tehisintellekti mudelid on midagi enamat kui lihtsalt abivahendid inimmatemaatikute jaoks – nad suudavad tulla välja originaalsete ja geniaalsete ideedega ning need ka ellu viia“.

Tõestus on saadaval siin⁠(avaneb uues aknas). Juhtivate väliste matemaatikute kaasnev artikkel on saadaval siin⁠(avaneb uues aknas). Mudeli mõttekäigu lühendatud versiooni leiate siit⁠(avaneb uues aknas).

Olgu $u(n)$ tasapinnal asuvate $n$ punkti vaheliste ühikukaugusega paaride suurim võimalik arv. Lineaarse kasvumääraga näiteid on lihtne konstrueerida: $n$ punkti joonele paigutamine annab $n-1$ paari, samas kui ruutvõrk annab umbes $2n$ paari. Senine parim konstruktsioon (põhinedes muudetud skaalaga ruutvõrgul) annab tegelikult veelgi suurema tulemuse: n1+C/loglog(n), kus C on konstant. Kuna $\log \log(n)$ läheneb koos $n$-iga lõpmatusele, läheneb eksponendi lisaliige $0$-le, mis tähendab, et need konstruktsioonid saavutavad kasvu vaid veidi kiiremini kui lineaarselt. Aastakümneid usuti laialdaselt, et see määr on sisuliselt parim võimalik ning ükski konstruktsioon ei saa ruutvõrku märkimisväärselt parandada. Matemaatiliselt väljendades oletas Erdős ülempiiriks n1+o(1), kus sümbol o(1) viitab liikmele, mis koondub n kasvades nulli suunas.

Meie uus tulemus lükkab selle hüpoteesi ümber. Täpsemalt öeldes konstrueeritakse tõestuses lõpmatult paljude n väärtuste jaoks n punkti konfiguratsioonid, millel on vähemalt n1+δ ühikkauguse paari teatud fikseeritud astendaja δ>0 korral. (Algne tehisintellekti tõestus ei anna selget δ väärtust, kuid Princetoni ülikooli matemaatikaprofessori Will Sawini peatselt ilmuv täpsustus on näidanud, et väärtuseks võib võtta δ=0,014.)

Probleemi ajalugu aitab mõista, miks see tulemus on üllatav. Parim teadaolev alumine piir oli püsinud sisuliselt muutumatuna alates Erdősi algsest 1946. aasta konstruktsioonist. Parim ülemine piir, $O(n^{4/3})$, pärineb Spenceri, Szemerédi ja Trotteri 1984. aasta tööst ning hoolimata hilisematest täpsustustest ja seotud struktuursest tööst, mida tegid Székely, Katz ja Silier, Pach, Raz ja Solymosi ning teised, on ülemine piir jäänud sisuliselt muutumatuks. Hüpoteesi toetava tõendusena uurisid Matoušek ja Alon-Bucić-Sauermann probleemi tasandil mitte-eukleidiliste kaugustega ning tõestasid, et „enamik” neist mitte-eukleidilistest kaugustest järgib mingis mõttes hüpoteesi.

Üllataval kombel pärinevad konstruktsiooni võtmekomponendid hoopis väga erinevast matemaatika harust, mida tuntakse algebralise arvuteooriana ja mis uurib selliseid mõisteid nagu tegurdamine täisarvude laiendustes, mida nimetatakse algebralisteks arvukehadeks.

Üldjoontes algab tõestus tuttava geomeetrilise mõttega ja viib selle ootamatusse suunda.

Erdősi algset alumist piiri saab mõista Gaussi täisarvude kaudu: arvud kujul $a+bi$, kus $a$ ja $b$ on täisarvud ning $i$ on $-1$ ruutjuur. Gaussi täisarvud laiendavad tavalisi täisarve ja neil on sarnaselt nendega omadused, nagu algteguriteks lahutamise ühesus. Selliseid tavaliste täisarvude või ratsionaalarvude laiendusi tuntakse algebraliste arvukehadena. Uus argument asendab Gaussi täisarvud algebralise arvuteooria keerukamate üldistustega, millel on rikkalikumad sümmeetriad ja mis võivad luua palju rohkem ühikupikkusega erinevusi.

Täpne argument kasutab selliseid tööriistu nagu lõpmatud klassiväljade tornid ja Golodi–Šafarevitši teooria, et näidata, et argumendi jaoks vajalikud arvukehad on tegelikult olemas. Need ideed olid algebraliste arvuteoreetikute seas hästi tuntud, kuid tuli suure üllatusena, et neil mõistetel on tähendus geomeetriliste küsimuste jaoks Eukleidilisel tasandil.

See tulemus tähistab olulist hetke tehisintellekti ja matemaatika vastastikmõjus: tehisintellektisüsteem on autonoomselt lahendanud pikaajalise lahendamata probleemi aktiivse uurimisvaldkonna keskmes. See annab ka esmase ülevaate uut tüüpi koostööst tehisintellekti ja inimmatemaatikute vahel. Sel juhul loob väliste matemaatikute kaasnev töö märksa rikkalikuma pildi kui algne lahendus üksi.

Nagu Thomas Bloom kirjutab kaasnevas märkuses:

„Kui hindan tehisintellekti loodud tõestuse tähtsust ja mõju, küsin endalt: kas see on õpetanud meile probleemi kohta midagi uut? Kas me mõistame nüüd diskreetse geomeetriat paremini? Arvan, et vastus on mõõdukas jah: see näitab, et arvuteoreetilistel konstruktsioonidel on sedalaadi küsimuste kohta palju rohkem öelda, kui me kahtlustasime; pealegi võib vajalik arvuteooria olla väga sügav. Pole kahtlust, et paljud algebralised arvuteoreetikud vaatavad lähikuudel tähelepanelikult ka teisi diskreetse geomeetria lahendamata probleeme.”

Selle lahenduse kaudu ilmnenud ootamatu seos algebralise arvuteooria ja diskreetse geomeetria vahel on üks tegur, mis muudab selle tulemuse märkimisväärseks. See ei lahenda lihtsalt konkreetset hüpoteesi, vaid võib anda matemaatikutele silla, mille kaudu hakata uurima edasisi seotud probleeme.

Bloom osutab ka laiemale võimalusele:

„Teadmiste piirid on väga ebaühtlased ning kahtlemata toovad järgmised kuud ja aastad kaasa sarnaseid edusamme paljudes teistes matemaatika valdkondades, kus pikaajalised lahendamata probleemid leiavad lahenduse tänu tehisintellektile, mis paljastab ootamatuid seoseid ja viib olemasolevad tehnilised vahendid oma piirideni. Tehisintellekt aitab meil põhjalikumalt uurida matemaatika katedraali, mille oleme sajandite jooksul üles ehitanud; millised muud varjatud imed ootavad meid veel ees?”

See tulemus pakub paljulubava näite: tehisintellekt annab mitte ainult lahenduse, vaid ka matemaatilise avastuse, mille tähendus muutub järgneva inimliku mõistmise kaudu selgemaks ja rikkalikumaks.

Järeldus on suurem kui see konkreetne tulemus. Parem matemaatiline mõtlemisvõime võib muuta tehisintellekti tugevamaks teaduspartneriks: see suudab siduda keerukaid arutluskäike, ühendada ideid erinevate teadmisvaldkondade vahel, tuua esile paljulubavaid suundi, mida eksperdid poleks ehk esikohale seadnud, ning aidata teadlastel saavutada edu probleemide lahendamisel, mis muidu oleksid liiga keerulised või aeganõudvad.

Need võimed on olulised ka väljaspool matemaatikat. Kui mudel suudab hoida keeruka argumendi sidusana, ühendada ideid teadmiste kaugete valdkondade vahel ja luua tööd, mis peab vastu ekspertide kontrollile, siis on need kasulikud võimed ka bioloogias, füüsikas, materjaliteaduses, inseneriteaduses ja meditsiinis ning need on osa meie pikaajalisest teekonnast automatiseerituma teadustöö suunas: süsteemid, mis aitavad teadlastel ja inseneridel uurida rohkem ideid ja tegeleda keerulisemate tehniliste küsimustega.

Tehisintellekt on kohe alustamas väga tõsise rolli võtmist teadustöö loomingulistes osades ja mis kõige olulisem, tehisintellekti uurimises endas. Kuigi see areng ei ole ootamatu, rõhutab see meie jaoks tungivat vajadust mõista tehisintellekti arengu järgmist etappi, väga intelligentsete süsteemide kooskõlastamisega seotud väljakutseid ning inimeste ja tehisintellekti koostöö tulevikku.

See tulevik sõltub siiski endiselt inimlikust otsustusvõimest. Asjatundlikkus muutub väärtuslikumaks, mitte vähem väärtuslikuks. Tehisintellekt saab aidata otsida, soovitada ja kontrollida. Inimesed valivad olulised probleemid, tõlgendavad tulemusi ja otsustavad, milliseid küsimusi järgmisena uurida.