Maszyna sama odkryła kostkę Rubika

Kolejny bastion ludzkich umiejętności i inteligencji padł pod naporem maszyn. Nowy rodzaj maszyny do głębokiego uczenia się nauczył się rozwiązywać kostkę Rubika bez pomocy człowieka.

Kamień milowy jest ważny, ponieważ nowe podejście dotyczy ważnego problemu w informatyce — jak rozwiązywać złożone problemy, gdy pomoc jest minimalna.

Najpierw trochę tła. Kostka Rubika to trójwymiarowa łamigłówka opracowana w 1974 roku przez węgierskiego wynalazcę Erno Rubika, której celem jest wyrównanie wszystkich kwadratów tego samego koloru na tej samej powierzchni sześcianu. Stała się najlepiej sprzedającą się na świecie zabawką i sprzedała się w ponad 350 milionach sztuk.

Zagadka wzbudziła również duże zainteresowanie informatyków i matematyków. Jedno pytanie, które ich zaintrygowało, to: najmniejsza liczba ruchów potrzebna do rozwiązania go z dowolnej pozycji . Odpowiedź, sprawdzona w 2014 roku, okazuje się być 26.

Innym powszechnym wyzwaniem jest zaprojektowanie algorytmów, które mogą rozwiązać kostkę z dowolnej pozycji. Sam Rubik w ciągu miesiąca od wynalezienia zabawki wymyślił algorytm, który mógł to zrobić.

Jednak wszystkie próby zautomatyzowania tego procesu opierały się na algorytmach, które zostały stworzone ręcznie przez ludzi.

Niedawno informatycy próbowali znaleźć sposoby na samodzielne rozwiązanie problemu przez maszyny. Jednym z pomysłów jest zastosowanie tego samego rodzaju podejścia, które było tak skuteczne w grach takich jak szachy i Go.

W takich scenariuszach maszyna do głębokiego uczenia się otrzymuje reguły gry, a następnie gra przeciwko sobie. Co najważniejsze, jest nagradzany na każdym kroku w zależności od tego, jak działa. Ten proces nagradzania jest niezwykle ważny, ponieważ pomaga maszynie odróżnić dobrą grę od złej gry. Innymi słowy, pomaga maszynie się uczyć.

Ale to nie działa w wielu rzeczywistych sytuacjach, ponieważ nagrody są często rzadkie lub trudne do ustalenia.

Na przykład losowe obroty kostki Rubika nie mogą być łatwo nagrodzone, ponieważ trudno ocenić, czy nowa konfiguracja jest bliższa rozwiązaniu. A sekwencja losowych tur może trwać przez długi czas bez osiągnięcia rozwiązania, więc nagroda w stanie końcowym może być oferowana rzadko.

W szachach natomiast istnieje stosunkowo duża przestrzeń poszukiwań, ale każdy ruch można odpowiednio ocenić i nagrodzić. Tak nie jest w przypadku kostki Rubika.

Wchodzi Stephen McAleer i koledzy z Uniwersytetu Kalifornijskiego w Irvine. Ci goście są pionierami nowego rodzaju techniki głębokiego uczenia się, zwanej iteracją autodydaktyczną, która może nauczyć się rozwiązywać kostkę Rubika bez pomocy człowieka. Sztuczka, którą opanowali McAleer i spółka, polega na znalezieniu sposobu na stworzenie przez maszynę własnego systemu nagród.

Oto jak to działa. Mając nierozwiązaną kostkę, maszyna musi zdecydować, czy konkretny ruch jest ulepszeniem istniejącej konfiguracji. Aby to zrobić, musi być w stanie ocenić ruch.

Iteracja autodydaktyczna robi to, zaczynając od gotowej kostki i pracując wstecz, aby znaleźć konfigurację podobną do proponowanego ruchu. Ten proces nie jest doskonały, ale głębokie uczenie pomaga systemowi określić, które ruchy są generalnie lepsze od innych.

Po przeszkoleniu sieć używa standardowego drzewa wyszukiwania do wyszukiwania sugerowanych ruchów dla każdej konfiguracji.

Rezultatem jest algorytm, który działa wyjątkowo dobrze. Nasz algorytm jest w stanie rozwiązać 100% losowo zaszyfrowanych kostek, osiągając średnią długość rozwiązania wynoszącą 30 ruchów — mniejszą lub równą rozwiązaniom wykorzystującym wiedzę z dziedziny ludzkiej, powiedzmy McAleer i spółka.

Jest to interesujące, ponieważ ma wpływ na wiele innych zadań, z którymi zmagało się głębokie uczenie, w tym łamigłówki, takie jak Sokoban, gry takie jak Zemsta Montezumy i problemy, takie jak faktoryzacja liczb pierwszych.

Rzeczywiście, McAleer i spółka mają na celu inne cele: pracujemy nad rozszerzeniem tej metody, aby znaleźć przybliżone rozwiązania innych problemów optymalizacji kombinatorycznej, takich jak przewidywanie struktury trzeciorzędowej białka.

Nie jest jasne, czy te problemy będą równie podatne na takie podejście. Na ogół nie korzystają z dowodu, że można je rozwiązać w niewielkiej liczbie ruchów, jak ma to miejsce w przypadku kostki Rubika. To niewątpliwie działało na korzyść zespołu.

McAleer i spółka twierdzą, że ich podejście jest formą rozumowania o problemach. Wskazują, że jedną z definicji rozumowania jest: algebraiczne manipulowanie wcześniej nabytą wiedzą w celu odpowiedzi na nowe pytanie.

Mówią, że dokładnie to robi ich algorytm – zwany DeepCube. Natomiast konwencjonalne maszyny do głębokiego uczenia się po prostu rozpoznają pewne wzorce. Mówią, że DeepCube jest w stanie nauczyć się rozumowania, aby rozwiązać złożone środowisko z tylko jednym stanem nagrody przy użyciu czystego uczenia się przez wzmacnianie.

Być może. Prawdziwym testem będzie oczywiście, jak to podejście radzi sobie z bardziej złożonymi problemami, takimi jak fałdowanie białek. Będziemy obserwowali, jak to działa.

Nr ref.: arxiv.org/abs/1805.07470 : Rozwiązywanie kostki Rubika bez wiedzy ludzkiej

ukryć