Czy sieci neuronowe można wykorzystać do opracowania algorytmów?

Po coraz większych sukcesach sieci neuronowych w grach planszowych wydaje się, że następnym celem, który wyznaczyliśmy, może być coś bardziej przydatnego niż pokonanie ludzi w Starcraft. Dokładniej, zastanawiałem się, czy

Czy sieci neuronowe można przeszkolić do rozwiązywania klasycznych problemów algorytmicznych?

Mam na myśli, że na przykład sieć otrzyma wykres wejściowy $G$ z ważonymi krawędziami i dwoma wierzchołkami $s$ i $t$ określono i poprosiliśmy o znalezienie najkrótszego $st$ścieżka tak szybko, jak to możliwe. Potem wydaje mi się, że sieć neuronowa odkryłaby i wytrenowała się, by używać Dijkstry lub czegoś podobnego.

Z jednej strony wiemy, że moc obliczeniowa sieci neuronowych jest$TC^0$. Z drugiej strony nie wiem, czy jest to związane z moim pytaniem. Mimo to w przypadku większości problemów nie wiemy, czy można je rozwiązać$TC^0$albo nie. Sprawdzanie, czy sieć neuronowa może się trenować, może być dobrym wskaźnikiem, czy istnieje szybki algorytm, czy nie. Na przykład, jeśli sieci neuronowe nie są w stanie samodzielnie nauczyć się szybkiego rozwiązywania SAT, oznacza to, że jest to (jeszcze bardziej) prawdopodobne$NP\not\subset TC^0$. Zastanawiam się, co sieć neuronowa zrobiłaby z GRAPHISOMORPHISM lub FACTORIZATION.

Oczywiście wyodrębnienie algorytmu to zupełnie inne pytanie. Podejrzewam, że eksperci wiedzą, jak to zrobić, ale omawianie tego nie jest tematem tego pytania.

Dodano dwa dni później: po obejrzeniu odpowiedzi pozwól mi określić, że jeśli odpowiesz przecząco, to chciałbym wiedzieć

Dlaczego gra w szachy jest łatwiejsza niż Dijkstra lub Graphisomorphism?

Według tego bloga Reza Zadeh szkolenie sieci neuronowej w celu uzyskania prawidłowego wyniku nawet dla zaledwie dwóch trzecich przykładów treningu jest trudne obliczeniowo:

Rzeczywiście, w 1988 r. J. Stephen Judd pokazuje następujący problem jako trudny do NP:

Biorąc pod uwagę ogólną sieć neuronową i zestaw przykładów szkoleniowych, czy istnieje zestaw wag krawędzi dla sieci, aby sieć generowała poprawny wynik dla wszystkich przykładów szkoleniowych?

Judd pokazuje również, że problem pozostaje trudny do rozwiązania, nawet jeśli wymaga tylko sieci, aby wygenerować prawidłową moc wyjściową tylko dla dwóch trzecich przykładów treningowych, co oznacza, że ​​nawet w przybliżeniu szkolenie sieci neuronowej jest z natury trudne w najgorszym przypadku. W 1993 roku Blum i Rivest pogarszają wieści: nawet prosta sieć z zaledwie dwiema warstwami i trzema węzłami jest trudna do wyuczenia!

To nie jest pełna odpowiedź i nie jestem zbyt doświadczony w sieciach neuronowych, ale być może pomocny.

NN zasadniczo otrzymują dane wejściowe i dają odpowiedź. Następnie są szkoleni poprzez praktykę, aby uzyskać podobne odpowiedzi na „podobne” dane wejściowe w dziedzinie, na przykład, tę samą etykietę do zdjęć tego samego zwierzęcia lub wysokie oceny do „dobrych” pozycji w szachach, gdzie dobra oznacza wysokie szanse na wygraną.

Tak jak skomentowałem, sieci neuronowe są niejednorodnym modelem obliczeniowym, który działa w zupełnie inny sposób niż algorytmy krok po kroku uruchamiane na maszynach Turinga. Zamiast tego pomyśl o nich jako o „miękkich” obwodach, które wykorzystują ciągłą matematykę, a nie logikę, i mogą być modyfikowane lub trenowane i mogą się mylić.

Dlaczego gra w szachy jest łatwiejsza niż Dijkstra lub Graphisomorphism?

Częściowo jest to różnica między proszeniem kogoś, aby odpowiedział na pytanie najlepiej jak potrafił, a proszeniem go o jedną poprawną odpowiedź wraz z dowodem, że jest poprawna. Częściowo jest to różnica między rozwiązaniem problemu o stałym rozmiarze, a jednoczesnym rozwiązaniem problemu dla wszystkich możliwych rozmiarów wejściowych.

Za każdym razem, gdy Dijkstra's jest uruchamiany na instancji, która może być dowolnej wielkości, domyślnie udowadnia, że jego wynik jest jedyną prawdziwą odpowiedzią i żadną inną. W szachach i rozpoznawaniu obrazów daje się najlepszą możliwą odpowiedź, a błędy są tolerowane. Ponadto trenuje się tylko sieci, aby rozwiązywać te problemy jednego rozmiaru na raz. Nie sądzę, że wiemy jeszcze, jak uogólnić takie rozwiązanie sieci neuronowej, powiedzmy, na przypadki problemów o zupełnie różnych rozmiarach i kształtach.

Nie sądzę, że powinniśmy zakładać, że sieci neuronowe nie są w stanie rozwiązać najkrótszych ścieżek lub podobnych problemów algorytmicznych, ale rozwiązują problemy w zasadniczo inny sposób niż algorytm krok po kroku, który jest zawsze poprawny.

Wracając do podobieństwa między sieciami neuronowymi a obwodami, zauważ, że obwody były badane od dziesięcioleci, ale sądząc po braku odpowiedzi na (5) z mojego poprzedniego pytania , nie wiemy prawie nic o tym, jak zbudować w pełni poprawne obwody dla danego problem z wyjątkiem transformacji jednolitego algorytmu (maszyny Turinga) w obwód.

W żadnym wypadku nie jestem ekspertem, ale jeszcze nie rozumiem, dlaczego nie.

Sieci neuronowe zasadniczo przeprowadzają optymalizację zgodnie z pewnego rodzaju „modelem kosztów i korzyści”, który często jest już wcześniej znany. Ponadto przestrzeń wyszukiwania jest dobrze zdefiniowana, znane i nieprawidłowe ruchy są znane, a „odmiany” łatwe do zdefiniowania. Nawet w przypadku AlphaZero i AlphaGo funkcje kosztów są prawdopodobnie oparte na współczynniku wygranych i wynikającym z tego rozkładzie współczynników wygranych dla wszystkich możliwych ruchów po wykonaniu ruchu, lub jakiegoś rodzaju heurystyki.

Przy opracowywaniu algorytmów w zasadzie pytasz program, aby nauczył się, jak wyprowadzać poprawny ciąg znaków (z już znanym ukrytym kodowaniem i funkcją kosztów), który odpowiada programowi, który „wykonuje algorytm”. Istnieje jednak prawdopodobnie nieskończenie wiele algorytmów, dla których implementujesz program. Być może będziesz chciał zdefiniować prawidłowe wskaźniki „sprawności”.

Jednak nawet w przypadku niektórych programów wskaźniki „sprawności” mogą być nieco trudne do zdefiniowania. Czas? Wykorzystanie przestrzeni? Ocena ilościowa „skutków ubocznych?” Optymalnie wygenerujesz „najkrótszy program”, który robi tylko to, co chcesz.

Podejrzewam, że jeśli znajdziesz odpowiednie wskaźniki sprawności i algorytmy dopasowania, będziesz w stanie to zrobić.

„sieci neuronowe” przekształcają wektor z jednej przestrzeni wymiarowej na inną przestrzeń wymiarową. są więc niczym więcej niż wysoce, wysoce nieliniowymi aproksymatorami funkcji. nawet sieci neuronowe używają algorytmów aproksymacyjnych do minimalizacji strat. jednak szkolenie sieci neuronowych w celu opracowania nowych algorytmów nie wchodzi w rachubę. Tomasz Mikołow wykonał pewne prace w tym obszarze z rozszerzoną stosową nawracającą siecią neuronową, a także słyszałem o „maszynach neuronowych” dla tej domeny. jednak znalezienie optymalnych strategii było podstawową przyczyną studiowania uczenia się przez wzmocnienie, co jest w pewnym stopniu związane z twoim pytaniem. ale wykorzystanie sieci neuronowych do opracowania nowych algorytmów nie jest możliwe, przynajmniej w najbliższej przyszłości.

Jestem inżynierem QA Automation, więc nie rób wiedzy specjalistycznej w sieciach neuronowych, ale tautologicznie tak, NN może same tworzyć algorytmy. Sami ludzie są na pewnym poziomie NN, a my tworzymy algorytmy, więc oczywiste jest, że tworzone przez nas sztuczne systemy NN mogą same tworzyć algorytmy.