Ewolucja sztucznych sieci neuronowych do rozwiązywania problemów NP


10

Niedawno przeczytałem naprawdę ciekawy wpis na blogu Google Research Blog o sieci neuronowej. Zasadniczo wykorzystują te sieci neuronowe do rozwiązywania różnych problemów, takich jak rozpoznawanie obrazów. Używają algorytmów genetycznych do „ewolucji” ciężarów aksonów.

Więc w zasadzie mój pomysł jest następujący. Gdybym miał napisać program, który rozpoznaje liczby, nie wiedziałbym, jak zacząć (mógłbym mieć jakiś niejasny pomysł, ale mam na myśli to, że nie jest to trywialne ani łatwe.) Ale używając sieci neuronowej nie muszę. Tworząc odpowiedni kontekst, aby sieć neuronowa mogła się rozwijać, moja sieć neuronowa „znajdzie właściwy algorytm”. Na dole cytowałem naprawdę interesującą część artykułu, w której wyjaśniają, w jaki sposób każda warstwa ma inną rolę w procesie rozpoznawania obrazu.

Jednym z wyzwań sieci neuronowych jest zrozumienie, co dokładnie dzieje się na każdej warstwie. Wiemy, że po treningu każda warstwa stopniowo wyodrębnia funkcje obrazu na wyższym i wyższym poziomie, aż ostatnia warstwa zasadniczo podejmie decyzję o tym, co pokazuje obraz. Na przykład pierwsza warstwa może szukać krawędzi lub narożników. Warstwy pośrednie interpretują podstawowe funkcje w poszukiwaniu ogólnych kształtów lub komponentów, takich jak drzwi lub skrzydło. Kilka ostatnich warstw składa je w kompletne interpretacje - neurony te aktywują się w odpowiedzi na bardzo złożone rzeczy, takie jak całe budynki lub drzewa.

Zasadniczo moje pytanie brzmi: czy nie moglibyśmy użyć algorytmów genetycznych + sieci neuronowych w celu rozwiązania każdego problemu NP? Po prostu tworzymy właściwy kontekst ewolucyjny i pozostawiamy „naturze” znalezienie rozwiązania.

Incepcjonizm: coraz głębiej w sieci neuronowe

EDYCJA: Wiem, że możemy użyć Brute-Force lub znaleźć nieefektywne rozwiązanie w wielu przypadkach. Dlatego staram się podkreślić rozwijające się sztuczne sieci neuronowe. Jak powiedziałem w komentarzu: Mając wystarczającą ilość czasu i odpowiedni wskaźnik mutacji, możemy znaleźć optymalne rozwiązanie (a przynajmniej tak myślę).

Pojęcie


1
Nie musimy. Możemy po prostu użyć brutalnej siły. Jaki jest dokładnie twój cel?
Pål GD,

2
Nie jestem ekspertem od sieci neuronowych, więc nie wiem, czy można je przeszkolić w zakresie prawidłowego rozwiązywania problemów NP. Ale nie sądzę, że zadajesz właściwe pytanie. Wymyślenie algorytmu, który rozwiązuje problem zawarty w NP, zwykle nie jest trudne, wystarczy sprawdzić każde możliwe rozwiązanie. Jednak znalezienie algorytmu, który rozwiązuje trudny NP problem w czasie wielomianowym, to inna historia i jego istnienie jest bardzo mało prawdopodobne. Ponieważ sieci neuronowe mogą być symulowane przez maszynę truującą, nadal potrzebują super wielomianowego czasu, chyba że P = NP i nie będą zbyt pomocne.
Dennis Kraft,

tak, sieci neuronowe zostały użyte przeciwko NP całkowitym problemom, np. Podróżującemu Sprzedawcy i wielu innym, a na ten temat znajdują się badania / literatura. mogą mieć pewne użyteczne właściwości, ale nie uciekają od ograniczeń czasowych teorii złożoności, jak wskazuje DK.
vzn

Chodzi mi o to: stosując odpowiednią częstotliwość mutacji i wystarczający czas, możemy (przynajmniej teoretycznie) znaleźć optymalne rozwiązanie. (Lub przynajmniej lokalne maksimum) Zdjęcie: Koncepcja
NMO

2
Algorytmy genetyczne (i cała reszta technik „AI”) są w zasadzie randomizowane „wypróbuj próbkę przestrzeni rozwiązania” z pewnymi inteligentami (heurystyką), aby nie była ona całkowicie losowa. Nie, nie jest to lepsze niż „wypróbowanie wszystkich możliwych rozwiązań”, w większości przypadków znacznie gorsze (ponieważ nie ma gwarancji, że nie sprawdzisz ponownie tego samego odrzuconego przypadku). Jasne, znajdują „przyzwoite” rozwiązania. Ale chcemy znaleźć to, co najlepsze .
vonbrand,

Odpowiedzi:


21

Nie. Jest mało prawdopodobne, aby ten kierunek był przydatny z dwóch powodów:

  1. Sieci neuronowe nie są „magiczne”. Są sposobem na znalezienie wzorów. W przypadku niektórych problemów, w których można znaleźć wystarczająco silne wzorce, a wzorców można się nauczyć z rozsądnej liczby przykładów, mogą one być skuteczne. Ale to nie jest magiczny czarodziejski pył. To, że możesz skonfigurować sieć neuronową, nie oznacza, że ​​propagacja wsteczna z pewnością znajdzie dobry sposób na rozwiązanie twojego problemu. Możliwe, że nie ma żadnych wzorców, że wzorce można odkryć tylko na niewykonalnej liczbie przykładów lub że wzorce istnieją, ale procedura szkolenia sieci neuronowej nie jest w stanie ich znaleźć.

Sieci neuronowe są po prostu kolejną formą uczenia maszynowego. Możemy zrobić te same uwagi na temat maszyn wirtualnych lub losowych lasów lub regresji liniowej w każdej innej formie uczenia maszynowego. Sieci neuronowe nie są magiczną srebrną kulą, która rozwiązuje wszystkie problemy z uczeniem maszynowym. Są tak samo skuteczne jak inne metody uczenia maszynowego lub w przypadku niektórych problemów, może trochę bardziej skuteczne, ale nie są magiczne.

Czasami spotykam ludzi, którzy słyszeli tylko trochę o sieciach neuronowych, i odchodzą myśląc, że sieci neuronowe są odpowiedzią na wszystko - może dlatego, że słyszeli, że „twój mózg też używa sieci neuronowych”, lub widzieli fajna aplikacja (rozpoznawanie głosu lub coś takiego). Ale nie daj się zwieść. Nie wierz w szum. Sieci neuronowe są przydatną techniką, ale nie pozwolą komputerom rozwiązać problemów związanych z NP-zakończeniem, ani przejść testu Turinga, zabrać wszystkich naszych zadań i zastąpić ludzi komputerami. W każdym razie nie w najbliższym czasie. To tylko science fiction.


1
Naprawdę dobra odpowiedź. Algorytmy genetyczne + sieci neuronowe wydają się bardzo potężne, ale może nie wystarczy rozwiązać każdego problemu np. Wyobrażam sobie pozostawienie tych sieci neuronowych + algorytmów genetycznych na wolności w poszukiwaniu tego rozwiązania p. Jak małe harcerze haha.
NMO,

1
Warto również zauważyć, że sieci neuronowe zwykle zapewniają pewne prawdopodobieństwo znalezienia poprawnej odpowiedzi, a nie gwarancji. Kiedy rozluźniasz swoje wymagania dotyczące problemów, aby umożliwić nieoptymalne rozwiązania, bardzo często pojawiają się praktyczne rozwiązania problemów NP-zupełnych, pomimo ich trudności w najgorszym przypadku.
Dan Bryant

9

Wydaje się, że inne odpowiedzi, choć pouczające / pomocne, nie rozumieją dokładnie twojego pytania i czytają w nim trochę za dużo. Nie pytałeś, czy sieci neuronowe przewyższają inne metody, pytałeś tylko, czy można je zastosować do kompletnych problemów NP. Odpowiedź brzmi: tak, z pewnym sukcesem, i jest to znane od dziesięcioleci i istnieje wiele różnych badań na ten temat i nadal trwa. Ma to związek z elastycznością uczenia maszynowego. Zauważ, że nawet jeśli nie znajdą dokładnych lub optymalnych rozwiązań, rozwiązania, które mają, mogą mieć inne pożądane właściwości. kilka przykładowych dokumentów:


4

Sieci neuronowe w rzeczywistości nie rozwiązują problemów z NP-zupełnymi. To, co robią, polega na rozwiązywaniu problemów, które są niezwykle zbliżone do problemów NP-zupełnych.

Jedną wielką cechą sieci neuronowych jest to, że nie są one zobowiązane do znalezienia „właściwej” odpowiedzi za każdym razem. Mogą się „mylić”. Na przykład możesz rozwiązać problem z pakowaniem pojemników i znaleźć rozwiązanie o 1% taniej od idealnego rozwiązania i być całkowicie zadowolonym z tej odpowiedzi.

Jeśli usuniesz wymóg posiadania 100% racji za każdym razem, inne metody rozwiązywania problemów działają bardzo dobrze. Na przykład wiele algorytmów planowania trasy (a la Google Maps) musi być NP-kompletnych, ale znalezienie algorytmu, który znajdzie ścieżkę w granicach 1% optymalnego 99,9% czasu, jest dość proste. Stara się ustalić wyniki w tych ostatnich 0,1% przypadków, które sprawiają, że wysiłki związane z NP są tak drogie, że są niesamowicie drogie.

Tak się składa, że ​​kiedy próbujemy zastosować równania NP-zupełne w prawdziwym życiu, często nie potrzebujemy rzeczywistej odpowiedzi. Często czujemy się komfortowo z odpowiedzią „blisko”, chociaż często nie mamy sformułowania, które wyjaśniałoby, z jakiego rodzaju „bliskości” korzystamy. Są to sytuacje, w których sieć neuronowa może odpowiedzieć na rzeczywiste pytanie, które chciałbyś zadać, zamiast konieczności rozwiązania problemu NP-zupełnego, o który prosiłeś.


1

Wiadomo, że sieci neuronowe są zdolne do przybliżania funkcji uniwersalnych , ale wymaga to przeszkolenia ich w zakresie problemu (optymalizacji), który sam w sobie jest problemem NP-zupełnym , dlatego masz szkolenie ewolucyjne i SGD z propagacją wsteczną i tak dalej.

Tak więc, chociaż nie są w stanie rozwiązać problemów związanych z NP-zupełnością, można je wyszkolić w celu przybliżenia z dowolną dokładnością funkcji modelującej problem. Nawet jeśli zdołasz optymalnie rozwiązać problem NP-zupełny za pomocą sieci neuronowej, nadal nie masz sposobu, aby udowodnić, że znalezione rozwiązanie jest w rzeczywistości globalnym optymalnym bez brutalnego wymuszania rozwiązania (nie jest to oczywiście możliwe z praktycznie żadnego praktycznego punktu widzenia przypadek użycia sieci neuronowych).

Twoja wizualizacja jest dokładna w tym sensie, że algorytmy ewolucyjne (zobacz, jak zgrabny algorytm zapobiega przejęciu pojedynczego gatunku przez populację o początkowo wysoce wydajnej strukturze przy użyciu wspólnej sprawności) są mniej odpowiednie niż SGD i inne techniki uczenia maszynowego, które mogą zostać uwięzione optymalne lokalne, ale nie dostarczają dowodów, że znalezione przez nich rozwiązanie jest w rzeczywistości rozwiązaniem optymalnym globalnie.


Czy możesz dodać jakieś odniesienia do swojej odpowiedzi? Spróbuj także poprawić formatowanie (na przykład użyj NP, SGD, propagacji wstecznej i tak dalej, i być może dodaj kilka podziałów linii).
Yuval Filmus

W porządku, wprowadziłem kilka zmian, daj mi znać, jeśli powinienem gdziekolwiek pójść dalej
nick

Myślę, że powinieneś uzasadnić swoje twierdzenie, że „algorytmy ewolucyjne… są mniej skłonne niż SGD i inne techniki uczenia maszynowego do uwięzienia w lokalnych optymach”. Nie sądzę, aby było to właściwe, szczególnie w przypadku konkretnego zadania szkolenia sieci neuronowych.
DW

Ta odpowiedź ma pewne wątpliwości dotyczące definicji kompletności NP. Wbrew temu, co twierdzą, jeśli mamy rozwiązać problem NP-zupełny, to może sprawdzić, czy mamy właściwe rozwiązanie. Istnieje różnica między problemem wyszukiwania NP-complete a problemem optymalizacji NP-hard; w przypadku tego pierwszego możemy rzeczywiście skutecznie sprawdzić, czy rozwiązanie jest poprawne, ale w przypadku tego drugiego możemy nie być w stanie.
DW

Kwalifikowałem się, że nie możemy zweryfikować, że jest to optymalne rozwiązanie bez brutalnego wymuszania naprawdę optymalnego rozwiązania, czy to nie jest poprawne? Podałem uzasadnienie dla mojego rozumowania, że ​​neuroewolucja jest mniej skłonna utknąć w lokalnych optymalnych za pomocą odnośnika do zgrabnego algorytmu i wspólnej sprawności, myślę, że gradient zejścia na utknięcie w lokalnych optymalnych jest raczej oczywisty, a podczas gdy dostrajanie hiperparametrów Framework może pomóc to złagodzić. Nie przypisałbym tego, że sgd ma awersję do utknięcia.
nickw
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.