Mašina pati sugalvojo Rubiko kubą

Dar vienas žmogaus įgūdžių ir sumanumo bastionas pateko į mašinų puolimą. Naujo tipo giluminio mokymosi mašina išmoko išspręsti Rubiko kubą be jokios žmogaus pagalbos.

Šis etapas yra svarbus, nes naujasis požiūris sprendžia svarbią kompiuterių mokslo problemą – kaip išspręsti sudėtingas problemas, kai pagalba yra minimali.

Pirmiausia šiek tiek fono. Rubiko kubas yra trimatis galvosūkis, kurį 1974 m. sukūrė vengrų išradėjas Erno Rubikas, kurio tikslas yra sulygiuoti visus tos pačios spalvos kvadratus tame pačiame kubo paviršiuje. Jis tapo tarptautiniu geriausiai parduodamu žaislu ir parduotas daugiau nei 350 mln.

Dėlionė taip pat sulaukė didelio kompiuterių mokslininkų ir matematikų susidomėjimo. Vienas juos sudominęs klausimas yra mažiausias judesių skaičius, reikalingas jai išspręsti iš bet kurios padėties . 2014 m. įrodytas atsakymas yra 26.

Kitas dažnas iššūkis yra sukurti algoritmus, kurie gali išspręsti kubą iš bet kurios padėties. Pats Rubikas per mėnesį nuo žaislo išradimo sugalvojo algoritmą, kuris galėtų tai padaryti.

Tačiau visi bandymai automatizuoti procesą buvo pagrįsti algoritmais, kuriuos sukūrė žmonės.

Visai neseniai kompiuterių mokslininkai bandė ieškoti būdų, kaip mašinos galėtų pačios išspręsti problemą. Viena idėja yra naudoti tą patį metodą, kuris buvo toks sėkmingas žaidimuose, tokiuose kaip šachmatai ir „Go“.

Šiuose scenarijuose gilaus mokymosi mašinai pateikiamos žaidimo taisyklės ir tada jis žaidžia prieš save. Svarbiausia, kad kiekviename žingsnyje jis apdovanojamas pagal tai, kaip jis veikia. Šis apdovanojimo procesas yra labai svarbus, nes jis padeda mašinai atskirti gerą žaidimą nuo blogo žaidimo. Kitaip tariant, tai padeda mašinai mokytis.

Tačiau tai neveikia daugelyje realaus pasaulio situacijų, nes atlygis dažnai būna retas arba sunku nustatyti.

Pavyzdžiui, atsitiktiniai Rubiko kubo posūkiai negali būti lengvai apdovanoti, nes sunku nuspręsti, ar nauja konfigūracija yra arčiau sprendimo. Atsitiktinių posūkių seka gali tęstis ilgą laiką nepasiekus sprendimo, todėl galutinės būsenos atlygis gali būti pasiūlytas tik retai.

Priešingai, šachmatuose yra gana didelė paieškos erdvė, tačiau kiekvienas ėjimas gali būti įvertintas ir atitinkamai apdovanotas. Tai tiesiog netinka Rubiko kubui.

Įveskite Stepheną McAleerį ir kolegas iš Kalifornijos universiteto Irvine. Šie vaikinai sukūrė naujos rūšies giluminio mokymosi techniką, vadinamą autodidaktine iteracija, kuri gali išmokti išspręsti Rubiko kubą be žmogaus pagalbos. Triukas, kurį įvaldė McAleer ir kiti, yra rasti būdą, kaip mašina galėtų sukurti savo atlygio sistemą.

Štai kaip tai veikia. Atsižvelgdama į neišspręstą kubą, mašina turi nuspręsti, ar konkretus veiksmas yra esamos konfigūracijos patobulinimas. Kad tai padarytų, ji turi turėti galimybę įvertinti judesį.

Autodidaktinė iteracija tai atlieka pradedant nuo baigto kubo ir grįžtant atgal, kad surastų konfigūraciją, panašią į siūlomą judėjimą. Šis procesas nėra tobulas, tačiau gilus mokymasis padeda sistemai išsiaiškinti, kurie judesiai paprastai yra geresni už kitus.

Apmokytas tinklas naudoja standartinį paieškos medį, kad gautų siūlomus veiksmus kiekvienai konfigūracijai.

Rezultatas yra nepaprastai gerai veikiantis algoritmas. Mūsų algoritmas gali išspręsti 100% atsitiktinai sumaišytų kubelių, o vidutinis sprendimo ilgis yra 30 judesių – mažiau arba lygus sprendėjams, kurie naudoja žmogaus srities žinias, sako McAleer ir kt.

Tai įdomu, nes tai turi įtakos įvairioms kitoms užduotims, su kuriomis susidūrė gilusis mokymasis, įskaitant galvosūkius, pvz., Sokobaną, žaidimus, tokius kaip Montezuma's Revenge, ir tokias problemas kaip pirminių skaičių faktorinavimas.

Iš tiesų, McAleer ir bendradarbiai turi kitų tikslų: mes stengiamės išplėsti šį metodą, kad surastume apytikslius kitų kombinacinio optimizavimo problemų sprendimus, pavyzdžiui, baltymų tretinės struktūros numatymą.

Neaišku, ar šios problemos bus tokios pat išspręstos taikant šį metodą. Paprastai jiems nėra naudinga įrodyti, kad juos galima išspręsti keliais judesiais, kaip tai daro Rubiko kubo problema. Tai neabejotinai čia išėjo į naudą komandai.

McAleer ir bendradarbiai teigia, kad jų požiūris yra tam tikra samprotavimų apie problemas forma. Jie nurodo, kad vienas samprotavimo apibrėžimas yra: algebrinis manipuliavimas anksčiau įgytomis žiniomis, siekiant atsakyti į naują klausimą.

Jie sako, kad būtent tai daro jų algoritmas, vadinamas DeepCube. Priešingai, įprastos giluminio mokymosi mašinos tiesiog atpažįsta tam tikrus modelius. Jie sako, kad „DeepCube“ gali išmokyti mąstyti, kad išspręstų sudėtingą aplinką su tik viena atlygio būsena, naudojant gryną sustiprinimo mokymąsi.

Galbūt. Žinoma, tikras išbandymas bus tai, kaip šis metodas susidoros su sudėtingesnėmis problemomis, tokiomis kaip baltymų lankstymas. Stebėsime, kaip tai veikia.

Nuoroda: arxiv.org/abs/1805.07470 : Rubiko kubo sprendimas be žmogaus žinių

paslėpti