Pitanje:
Značenje (i dokaz) "RNN može približiti bilo koji algoritam"
user3726947
2016-06-28 00:34:47 UTC
view on stackexchange narkive permalink

Nedavno sam pročitao da se ponavljajuća neuronska mreža može približiti bilo kojem algoritmu.

Dakle, moje je pitanje: što to točno znači i možete li mi uputiti gdje je to dokazano?

Provjerite djela Halberta Whitea.Mislim da je upravo on dokazao da je neuronska mreža univerzalni aproksimator.(Ipak, nisam siguran u ponavljajuće neuronske mreže.)
Referenca koju tražite odnosi se na Hornik, a također se ti rezultati tiču ANN-a, a ne RNN-a koji žive u različitim prostorima (prvi se odnosi na funkcije, a drugi slijed) ...
Dva odgovori:
user20160
2016-06-29 05:54:20 UTC
view on stackexchange narkive permalink

Prvo moramo proći kroz neke koncepte iz teorije izračunavanja. Algoritam postupak je za izračunavanje funkcije. S obzirom na ulaz, algoritam mora stvoriti ispravan izlaz u konačnom broju koraka, a zatim završiti. Reći da je funkcija izračunljiva znači da postoji algoritam za njezino izračunavanje. Među beskonačnim skupom svih funkcija, većina se ne može izračunati. Turingovi strojevi matematički su model koji formalizira pojam računanja. Postoje i drugi ekvivalentni modeli, ali Turingovi su strojevi standardni 'referentni model'. Prema Church-Turingovoj tezi, svaki algoritam može implementirati Turingov stroj, a sve izračunate funkcije mogu se izračunati na taj način. Bilo koja određena instanca Turingova stroja izračunava samo određenu funkciju. Ali, postoji posebna klasa Turingovih strojeva nazvana univerzalni Turingovi strojevi koja može simulirati bilo koji drugi Turingov stroj za bilo koji ulaz. To čine uzimajući opis stroja koji treba simulirati (i njegov ulaz) kao dio vlastitog ulaza. Bilo koji određeni primjerak univerzalnog Turingova stroja stoga može izračunati bilo koju izračunavu funkciju (tj. Može implementirati bilo koji algoritam). Bilo koji sustav koji dijeli ovu sposobnost naziva se Turingov cjelovit. Jedan od načina da se dokaže da je Turingov sustav cjelovit jest pokazati da može simulirati univerzalni Turingov stroj. Pokazalo se da su mnogi sustavi Turingovi cjeloviti (npr. Većina programskih jezika, određeni stanični automati i kvantna mehanika).

Ponavljajući neuralni mreže

Sljedeći rad pokazuje da za bilo koju izračunatu funkciju postoji konačna rekurentna neuronska mreža (RNN) koja je može izračunati. Nadalje, postoje konačni RNN-ovi koji su Turingov kompletni, te stoga mogu implementirati bilo koji algoritam.

Siegelmann i Sontag (1992). O računskoj snazi ​​neuronskih mreža

Koriste mreže koje sadrže konačan broj rekurentno povezanih jedinica, koje primaju vanjske ulaze u svakoj vremenskoj točki. Stanje svake jedinice dato je ponderiranim zbrojem njezinih ulaza (plus pristranost), provedenih kroz nelinearnu funkciju aktiviranja. Aktivacijska funkcija je zasićena linearna funkcija, koja je komadno linearna aproksimacija sigmoida. Ponderi i pristranosti su fiksni, pa se ne događa učenje.

Mreža izvodi preslikavanje iz binarnog ulaznog niza u binarni izlazni slijed. Postoje dva vanjska ulaza u mrežu koji se napajaju u sve jedinice: 'podatkovna linija' i 'linija provjere valjanosti'. Linija podataka sadrži ulazni slijed nula i jedinica, a zatim nula nakon završetka ulaznog niza. Linija za provjeru daje mreži do znanja kada se događa sekvenca unosa. Sadrži jedan za vrijeme trajanja ulaznog niza, a zatim nula nakon završetka. Jedna jedinica se smatra „izlaznom jedinicom“. Izbacuje nule za neko proizvoljno kašnjenje, zatim izlazni slijed nula i jedinica, pa nulu nakon završetka izlaznog niza. Sljedećom jedinicom smatra se 'jedinica za provjeru valjanosti', što nas zna kada se događa izlazni slijed. Izlazi jedan dok se događa izlazni niz, a u suprotnom nula.

Iako ovi RNN-ovi mapiraju binarne ulazne sekvence u binarne izlazne nizove, možda bi nas mogle zanimati funkcije definirane na raznim drugim matematičkim objektima (druge vrste brojeva , vektori, slike, grafikoni itd.). Ali, za bilo koju izračunavu funkciju, ove druge vrste objekata mogu se kodirati kao binarne sekvence (npr. Pogledajte ovdje za opis kodiranja drugih objekata pomoću prirodnih brojeva, koji zauzvrat mogu biti predstavljeni u binarnom obliku).

Oni pokazuju da za svaku izračunatu funkciju postoji konačni RNN (gore opisanog oblika) koji ga može izračunati. To čine pokazujući da je moguće koristiti RNN za izričitu simulaciju automatskog potiskivanja s dva snopa. Ovo je još jedan model koji je računski ekvivalentan Turingovom stroju. Bilo koju izračunatu funkciju može izračunati Turingov stroj. Bilo koji Turingov stroj može se simulirati automatom s dva pritiska. Bilo koji automat s dvostrukim slaganjem može se simulirati pomoću RNN-a. Stoga se svaka izračunava funkcija može izračunati pomoću RNN-a. Nadalje, budući da su neki Turingovi strojevi univerzalni, RNN-ovi koji ih simuliraju Turingov su komplet, te stoga mogu implementirati bilo koji algoritam. Oni posebno pokazuju da postoje Turingovi cjeloviti RNN-ovi s 1058 ili manje jedinica.

Ostale posljedice

Zanimljiva posljedica rezultata simulacije jest da su određene pitanja o ponašanju RNN-a su neodlučna. To znači da ne postoji algoritam koji im može odgovoriti za proizvoljne RNN-ove (iako mogu odgovarati u slučaju određenih RNN-ova). Primjerice, neodlučno je pitanje uzima li određena jedinica ikad vrijednost 0; ako bi se moglo odgovoriti na ovo pitanje općenito, bilo bi moguće riješiti problem zaustavljanja za Turingove strojeve, koji je neodrediv.

Računarska snaga

U gornjem radu svi su mrežni parametri i stanja racionalni brojevi. To je važno jer ograničava snagu RNN-a i rezultirajuće mreže čini realnijima. Razlog je taj što su obrazloženja izračunati brojevi, što znači da postoji algoritam za njihovo izračunavanje s proizvoljnom preciznošću. Većina stvarnih brojeva je neispravna, a samim tim i nepristupačna - čak ih ni najmoćniji Turingov stroj ne može predstavljati, a mnogi ljudi sumnjaju da bi mogli biti predstavljeni u fizičkom svijetu. Kada imamo posla s 'stvarnim brojevima' na digitalnim računalima, pristupamo još manjoj podskupini (npr. 64-bitnim brojevima s pomičnim zarezom). Predstavljanje proizvoljnih stvarnih brojeva zahtijevalo bi beskonačne informacije.

Članak kaže da bi davanje pristupa mreži stvarnim brojevima povećalo računsku snagu još više, izvan Turingovih strojeva. Siegelmann je napisao niz drugih članaka istražujući tu sposobnost "super-Turinga". Međutim, važno je napomenuti da su to matematički modeli i rezultati ne znače da bi takav stroj mogao stvarno postojati u fizičkom svijetu. Postoje dobri razlozi da mislite da ne bi moglo, iako je to otvoreno pitanje.

hej, ovo mi je super zanimljivo, pitao sam se imate li referencu kako biste saznali više o ovoj teoriji računanja i njezinoj vezi s algoritmima strojnog učenja ili kvantnim računanjem.Hvala!
Znači li to da je povratna mreža automatski inferiorna?Na primjer, želim proizvesti ASIC ploču koja bi trenirala mrežu različite dubine, pa bih radije odabrala LSTM neurone i zaboravila na bilo koji tradicionalni perceptron model, jer bi oni stvorili mreže slabije kvalitete.Pravo?
horaceT
2016-06-29 03:05:57 UTC
view on stackexchange narkive permalink

Mislim da je to ono što tražite. Taj je tip dokazao da višeslojna ili čak jednoslojna mreža za prosljeđivanje može aproksimirati bilo koju funkciju, pod uvjetom da mreža ima dovoljno skrivenih jedinica.

Hornik, K. (1991). Približne mogućnosti višeslojnih mreža za prosljeđivanje. Neuronske mreže, 4 (2), 251-257.

nisam to mislio.Već sam pročitao dokaz za to.Uredio sam svoje pitanje.


Ova pitanja su automatski prevedena s engleskog jezika.Izvorni sadržaj dostupan je na stackexchange-u, što zahvaljujemo na cc by-sa 3.0 licenci pod kojom se distribuira.
Loading...