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

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ę).

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

1. $\ne$$\ne$$\ne$

2. 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.

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:

• Sieci neuronowe i problemy z optymalizacją NP-complete; Badanie wydajności dotyczące problemu bisekcji grafowej / Peterson, Anderson

• Sieci neuronowe dla problemów NP-Complete (1996) / Budinich

• Znalezienie przybliżonych rozwiązań problemów NP-trudnych przez sieci neuronowe jest trudne / Yao

• O mocy sieci neuronowych w rozwiązywaniu trudnych problemów / Bruck, Goodman

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ś.

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.