Mašīna pati ir izdomājusi Rubika kubu

Vēl viens cilvēka prasmju un inteliģences bastions ir kritis mašīnu uzbrukumā. Jauna veida padziļinātas apmācības mašīna ir iemācījusies atrisināt Rubika kubu bez cilvēka palīdzības.

Pagrieziena punkts ir nozīmīgs, jo jaunā pieeja risina svarīgu datorzinātņu problēmu — kā atrisināt sarežģītas problēmas, kad palīdzība ir minimāla.

Vispirms nedaudz fona. Rubika kubs ir trīsdimensiju puzle, ko 1974. gadā izstrādāja ungāru izgudrotājs Erno Rubiks, un tās mērķis ir izlīdzināt visus vienādas krāsas kvadrātus vienā kuba pusē. Tā kļuva par starptautiski visvairāk pārdoto rotaļlietu un tika pārdota vairāk nekā 350 miljonu vienību.

Puzle ir izraisījusi arī ievērojamu datorzinātnieku un matemātiķu interesi. Viens jautājums, kas viņus ir ieintriģējis, ir mazākais kustību skaits, kas nepieciešams, lai to atrisinātu no jebkuras pozīcijas . Atbilde, kas pierādīta 2014. gadā, ir 26.

Vēl viens izplatīts izaicinājums ir izstrādāt algoritmus, kas var atrisināt kubu no jebkuras pozīcijas. Pats Rubiks mēneša laikā pēc rotaļlietas izgudrošanas nāca klajā ar algoritmu, kas to varētu izdarīt.

Taču mēģinājumi automatizēt procesu ir balstīti uz algoritmiem, ko cilvēki ir izstrādājuši ar rokām.

Pavisam nesen datorzinātnieki ir mēģinājuši atrast veidus, kā mašīnas pašas var atrisināt problēmu. Viena no idejām ir izmantot tādu pašu pieeju, kas ir bijusi tik veiksmīga ar tādām spēlēm kā šahs un Go.

Šajos scenārijos padziļinātas mācīšanās mašīnai tiek doti spēles noteikumi un pēc tam tā spēlē pret sevi. Būtiski, ka tas tiek atalgots katrā solī atkarībā no tā, kā tas darbojas. Šis apbalvošanas process ir ļoti svarīgs, jo tas palīdz iekārtai atšķirt labu spēli no sliktas spēles. Citiem vārdiem sakot, tas palīdz mašīnai mācīties.

Taču tas nedarbojas daudzās reālās pasaules situācijās, jo atlīdzības bieži vien ir reti vai grūti nosakāmas.

Piemēram, nejaušus Rubika kuba pagriezienus nevar viegli atalgot, jo ir grūti spriest, vai jaunā konfigurācija ir tuvāk risinājumam. Un nejaušu pagriezienu secība var turpināties ilgu laiku, nesasniedzot risinājumu, tāpēc gala stāvokļa atlīdzību var piedāvāt tikai reti.

Turpretim šahā ir salīdzinoši liela meklēšanas telpa, taču katru gājienu var novērtēt un attiecīgi apbalvot. Tas vienkārši neattiecas uz Rubika kubu.

Ievadiet Stephen McAleer un kolēģi no Kalifornijas Universitātes, Irvine. Šie puiši ir ieviesuši jauna veida dziļās mācīšanās paņēmienus, ko sauc par autodidaktisko iterāciju, kas var iemācīties atrisināt Rubika kubu bez cilvēka palīdzības. McAleer un viņa apgūtais triks ir atrast veidu, kā iekārtai izveidot savu atlīdzības sistēmu.

Lūk, kā tas darbojas. Ņemot vērā neatrisinātu kubu, iekārtai ir jāizlemj, vai konkrēta kustība ir esošās konfigurācijas uzlabojums. Lai to izdarītu, tai jāspēj novērtēt gājiens.

Autodidaktiskā iterācija to dara, sākot ar gatavo kubu un strādājot atpakaļ, lai atrastu konfigurāciju, kas ir līdzīga ierosinātajai kustībai. Šis process nav ideāls, taču dziļa mācīšanās palīdz sistēmai noskaidrot, kuras kustības parasti ir labākas par citām.

Pēc tam, kad tīkls ir apmācīts, tīkls izmanto standarta meklēšanas koku, lai meklētu ieteiktās kustības katrai konfigurācijai.

Rezultāts ir algoritms, kas darbojas ļoti labi. Mūsu algoritms spēj atrisināt 100% nejauši šifrētu kubu, vienlaikus sasniedzot vidējo atrisināšanas garumu 30 gājienu apmērā, kas ir mazāks par vai vienāds ar risinātājiem, kas izmanto cilvēka domēna zināšanas, saka McAleer un citi.

Tas ir interesanti, jo tas ietekmē dažādus citus uzdevumus, ar kuriem padziļināta mācīšanās ir cīnījusies, tostarp tādas mīklas kā Sokoban, spēles, piemēram, Montezuma’s Revenge, un tādas problēmas kā pirmskaitļu faktorizēšana.

Patiešām, McAleer un co ir citi mērķi: mēs strādājam pie šīs metodes paplašināšanas, lai atrastu aptuvenus risinājumus citām kombinatoriskās optimizācijas problēmām, piemēram, olbaltumvielu terciārās struktūras prognozēšanai.

Nav skaidrs, vai šīs problēmas būs tikpat risināmas ar šo pieeju. Parasti viņiem nav izdevīgi pierādīt, ka tos var atrisināt ar nelielu kustību skaitu, kā to dara Rubika kuba problēma. Šeit tas neapšaubāmi strādāja par labu komandai.

McAleer un co apgalvo, ka viņu pieeja ir argumentācijas veids par problēmām. Viņi norāda, ka viena spriešanas definīcija ir: algebriski manipulēt ar iepriekš iegūtajām zināšanām, lai atbildētu uz jaunu jautājumu.

Viņi saka, ka tieši to dara viņu algoritms, ko sauc par DeepCube. Turpretim parastās dziļās apmācības iekārtas vienkārši atpazīst noteiktus modeļus. Viņi saka, ka DeepCube spēj iemācīties spriest, lai atrisinātu sarežģītu vidi ar tikai vienu atalgojuma stāvokli, izmantojot tīru pastiprināšanas mācīšanos.

Varbūt. Patiesais pārbaudījums, protams, būs tas, kā šī pieeja tiek galā ar sarežģītākām problēmām, piemēram, olbaltumvielu locīšanu. Mēs skatīsimies, lai redzētu, kā tas darbojas.

Atsauce: arxiv.org/abs/1805.07470 : Rubika kuba atrisināšana bez cilvēka zināšanām

paslēpties