Znaczenie (i dowód) „RNN może przybliżyć dowolny algorytm”

Ostatnio czytałem, że nawracająca sieć neuronowa może aproksymować dowolny algorytm.

Więc moje pytanie brzmi: co to dokładnie oznacza i czy możesz podać mi odniesienie, w którym zostało to udowodnione?

tło

Najpierw musimy przyjrzeć się niektórym pojęciom z teorii obliczeń. Algorytm jest procedura obliczania funkcji. Biorąc pod uwagę dane wejściowe, algorytm musi wygenerować poprawne dane wyjściowe w skończonej liczbie kroków, a następnie zakończyć. Powiedzenie, że funkcja jest obliczalna, oznacza, że ​​istnieje algorytm do jej obliczenia. Wśród nieskończonego zestawu wszystkich funkcji większość nie jest obliczalna. Maszyny Turinga to model matematyczny, który formalizuje pojęcie obliczeń. Istnieją inne równoważne modele, ale maszyny Turinga są standardowym „modelem referencyjnym”. Według tezy Kościoła-Turinga, dowolny algorytm może być zaimplementowany przez maszynę Turinga i wszystkie funkcje obliczalne mogą być w ten sposób obliczone. Każdy konkretny przypadek maszyny Turinga oblicza tylko określoną funkcję. Istnieje jednak specjalna klasa maszyn Turinga, zwana uniwersalnymi maszynami Turinga, które mogą symulować każdą inną maszynę Turinga dla dowolnego wkładu. Robią to, przyjmując opis symulowanej maszyny (i jej danych wejściowych) jako część własnych danych wejściowych. Każde konkretne wystąpienie maszyny Universal Turinga może zatem obliczyć dowolną funkcję obliczeniową (tj. Może zaimplementować dowolny algorytm). Każdy system, który dzieli tę umiejętność, nazywa się Turing complete. Jednym ze sposobów udowodnienia, że ​​system jest kompletny, jest wykazanie, że może on symulować uniwersalną maszynę Turinga. Wykazano, że wiele systemów jest kompletnych Turinga (np. Większość języków programowania, niektóre automaty komórkowe i mechanika kwantowa ).

Nawracające sieci neuronowe

Poniższy artykuł pokazuje, że dla dowolnej funkcji obliczeniowej istnieje skończona, rekurencyjna sieć neuronowa (RNN), która może ją obliczyć. Co więcej, istnieją skończone RNN, które są kompletne Turinga i dlatego mogą implementować dowolny algorytm.

Siegelmann i Sontag (1992) . O mocy obliczeniowej sieci neuronowych

Korzystają z sieci zawierających skończoną liczbę powtarzalnie połączonych jednostek, które otrzymują zewnętrzne dane wejściowe w każdym punkcie czasowym. Stan każdej jednostki jest określony przez ważoną sumę jej danych wejściowych (plus błąd systematyczny), przebiegający przez nieliniową funkcję aktywacyjną. Funkcja aktywacji jest nasyconą funkcją liniową, która jest częściowym liniowym przybliżeniem sigmoidu. Wagi i odchylenia są stałe, więc nie ma możliwości uczenia się.

Sieć wykonuje odwzorowanie z binarnej sekwencji wejściowej na binarną sekwencję wyjściową. Istnieją dwa zewnętrzne wejścia do sieci, które są podawane do wszystkich jednostek: „linia danych” i „linia walidacji”. Linia danych zawiera sekwencję wejściową zer i jedynek, a następnie zero po zakończeniu sekwencji wejściowej. Linia sprawdzania poprawności informuje sieć o sekwencji wprowadzania danych. Zawiera jeden na czas trwania sekwencji wejściowej, a następnie zero po jej zakończeniu. Jedna jednostka jest uważana za „jednostkę wyjściową”. Wyprowadza zera przez dowolne opóźnienie, następnie sekwencję wyjściową zer i jedynek, a następnie zero po zakończeniu sekwencji wyjściowej. Inna jednostka jest uważana za „jednostkę sprawdzania poprawności”, która informuje nas o sekwencji wyjściowej.

Chociaż te RNN odwzorowują binarne sekwencje wejściowe na binarne sekwencje wyjściowe, możemy być zainteresowani funkcjami zdefiniowanymi na różnych innych obiektach matematycznych (inne typy liczb, wektorów, obrazów, wykresów itp.). Ale w przypadku dowolnej funkcji obliczeniowej te inne typy obiektów mogą być kodowane jako sekwencje binarne (np. Zobacz tutaj opis kodowania innych obiektów za pomocą liczb naturalnych, które z kolei mogą być reprezentowane w postaci binarnej).

Wynik

Pokazują, że dla każdej funkcji obliczeniowej istnieje skończony RNN (o postaci opisanej powyżej), który może go obliczyć. Robią to, pokazując, że można użyć RNN do jawnej symulacji automatu z dwoma stosami. Jest to kolejny model, który jest obliczeniowo równoważny z maszyną Turinga. Każda funkcja obliczeniowa może być obliczona przez maszynę Turinga. Dowolną maszynę Turinga można symulować za pomocą automatu z dwoma stosami. Każdy automat z dwoma stosami może być symulowany przez RNN. Dlatego dowolna funkcja obliczalna może być obliczona przez RNN. Ponadto, ponieważ niektóre maszyny Turinga są uniwersalne, RNN, które je symulują, są Turinga kompletne i dlatego mogą implementować dowolny algorytm. W szczególności pokazują, że istnieją kompletne RNN Turinga z 1058 lub mniejszą liczbą jednostek.

Inne konsekwencje

Ciekawą konsekwencją wyników symulacji jest to, że pewne pytania dotyczące zachowania RNN są nierozstrzygalne. Oznacza to, że nie istnieje algorytm, który mógłby odpowiedzieć na nie w przypadku dowolnych RNN (chociaż mogą one być odpowiedzialne w przypadku określonych RNN). Na przykład pytanie, czy dana jednostka kiedykolwiek przyjmuje wartość 0, jest nierozstrzygalne; gdyby można było odpowiedzieć na to pytanie w ogólności, byłoby możliwe rozwiązanie problemu zatrzymania maszyn Turinga, co jest nierozstrzygalne.

Moc obliczeniowa

W powyższym artykule wszystkie parametry i stany sieci są liczbami wymiernymi. Jest to ważne, ponieważ ogranicza moc RNN i sprawia, że ​​powstałe sieci są bardziej realistyczne. Powodem jest to, że racjonalne są liczbami obliczalnymi , co oznacza, że ​​istnieje algorytm obliczania ich z dowolną dokładnością. Większość liczb rzeczywistych jest niepoliczalna, a zatem niedostępna - nawet najpotężniejsza maszyna Turinga nie jest w stanie ich przedstawić, a wiele osób wątpi, że mogłyby być nawet reprezentowane w świecie fizycznym. Kiedy mamy do czynienia z „liczbami rzeczywistymi” na komputerach cyfrowych, uzyskujemy dostęp do jeszcze mniejszego podzbioru (np. 64-bitowe liczby zmiennoprzecinkowe ). Reprezentowanie dowolnych liczb rzeczywistych wymagałoby nieskończonych informacji.

W artykule napisano, że zapewnienie sieci dostępu do liczb rzeczywistych jeszcze bardziej zwiększyłoby moc obliczeniową, wykraczając poza maszyny Turinga. Siegelmann napisał wiele innych artykułów eksplorujących tę funkcję „super-Turinga”. Należy jednak zauważyć, że są to modele matematyczne, a wyniki nie oznaczają, że taka maszyna mogłaby faktycznie istnieć w świecie fizycznym. Istnieją dobre powody, by sądzić, że tak nie jest, choć jest to pytanie otwarte.

Myślę, że tego właśnie szukasz. Ten facet udowodnił, że wielowarstwowa, a nawet jednowarstwowa sieć przesyłowa może przybliżać dowolną funkcję, pod warunkiem, że sieć ma wystarczająco dużo ukrytych jednostek.

Hornik, K. (1991). Możliwości aproksymacyjne wielowarstwowych sieci feedforward. Sieci neuronowe, 4 (2), 251–257.