Sortuj za pomocą sieci neuronowej

15

Poprzednie wyzwania gry w golfa w sieci neuronowej ( to i tamto ) zainspirowały mnie do postawienia nowego wyzwania:

Wyzwanie

Znajdź najmniejszą sieć neuronową ze sprzężeniem zwrotnym, taką, że biorąc pod uwagę dowolny 4-wymiarowy wektor wejściowy (za,b,do,re) z wpisami liczb całkowitych w [-10,10] , wyjścia sieciowe sortować(za,b,do,re) pomocą błąd współrzędnych ściśle mniejszy niż 0,5 .

Dopuszczalność

W przypadku tego wyzwania sieć neuronowa typu feed-forward jest definiowana jako kompozycja warstw . Warstwa jest funkcją L.:RnRm , która jest określona przez matrycę R m x n z ciężarkami , wektor b R m z odchyleń , i aktywacja funkcji F : RR , który jest stosowany coordinate- mądry:ZARm×nbRm fa:RR

L.(x): =fa(ZAx+b),xRn.

Ponieważ funkcje aktywacyjne można dostosować do dowolnego zadania, musimy ograniczyć klasę funkcji aktywacyjnych, aby wyzwanie było interesujące. Dozwolone są następujące funkcje aktywacji:

  • Tożsamość. fa(t)=t

  • ReLU. fa(t)=max(t,0)

  • Softplus. fa(t)=ln(mit+1)

  • Styczna hiperboliczna. fa(t)=tanh(t)

  • Sigmoid. fa(t)=mitmit+1

Ogólnie rzecz biorąc, dopuszczalne sieć neuronowa ma postać L.kL.k-1L.2)L.1 z jakiegoś k , gdzie każda warstwa L.ja jest określony przez wag ZAja , odchyleń bja i funkcji aktywacji faja z powyższej listy. Na przykład dopuszczalna jest następująca sieć neuronowa (chociaż nie spełnia celu wydajności tego wyzwania, może być przydatnym gadżetem):

[min(za,b)max(za,b)]=[1-1-12)-12)1-112)12)]RmiL.U[12)12)-12)-12)1-1-11][zab]

Ten przykład pokazuje dwie warstwy. Obie warstwy mają zerowe obciążenie. Pierwsza warstwa wykorzystuje aktywację ReLU, a druga aktywację tożsamości.

Punktacja

Twój wynik to łączna liczba niezerowych wag i odchyleń.

(Np. Powyższy przykład ma wynik 16, ponieważ wektory odchylenia są równe zero.)

Dustin G. Mixon
źródło
2
@ Zamknięty głosujący: Co dokładnie jest niejasne? Nie sądzę, żeby którekolwiek z poprzednich wyzwań NN było tak dobrze określone.
flawr
1
Nie - pomiń połączenia są niedozwolone.
Dustin G. Mixon
1
@ DustinG.Mixon Właściwie właśnie znalazłem podejście dla maks / min, które wykorzystuje tylko 15 obciążników zamiast 16, ale jest znacznie mniej eleganckie :)
flawr
3
Jest to dobrze określone wyzwanie, które moim zdaniem może służyć jako model dla przyszłych wyzwań związanych z siecią neuronową.
xnor
1
et

Odpowiedzi:

13

Oktawy , 96 88 87 84 76 54 50 obciążników i odchyleń

Ta 6-warstwowa sieć neuronowa jest w zasadzie 3, etap sortowania sieci zbudowana z bardzo prosty min/ max sieci jako składnika. Jest to w zasadzie przykładowa sieć z wikipedii, jak pokazano poniżej, z niewielką modyfikacją: Pierwsze dwa porównania są wykonywane równolegle. Aby ominąć liczby ujemne przez ReLU, najpierw dodajemy 100, a następnie odejmujemy 100 na końcu.

Dlatego należy to uznać za punkt odniesienia, ponieważ jest to naiwne wdrożenie. Jednak idealnie sortuje wszystkie możliwe liczby, które nie mają zbyt dużej wielkości. (Możemy dostosować zakres, zastępując 100 innym numerem).

Wypróbuj online!

składnik maks./min

Istnieje ( znacznie mniej elegancki, teraz bardziej elegancki, dzięki @xnor!) Sposób na znalezienie minimum i maksimum dwóch liczb przy użyciu mniejszej liczby parametrów:

min=za-RmiL.U(za-b)max=b+RmiL.U(za-b)

Oznacza to, że musimy używać znacznie mniej obciążeń i stronniczości.

Dzięki @Joel za wskazanie, że wystarczy, aby wszystkie liczby były dodatnie w pierwszym kroku, i odwrócenie go w ostatnim, co daje -8 wag. Dzięki @xnor za wskazanie jeszcze krótszej metody max / min, która daje -22 wagi! Dzięki @ DustinG.Mixon za końcówkę łączenia niektórych matryc, które dają kolejne -4 wagi!

function z = net(u)
a1 = [100;100;0;100;100;0];
A1 = [1 0 0 0;0 0 1 0;1 0 -1 0;0 1 0 0;0 0 0 1;0 1 0 -1];
B1 = [1 0 -1 0 0 0;0 0 0 1 0 -1;0 1 1 0 0 0;0 0 0 0 1 1];
A2 = [1 0 0 0;0 1 0 0;1 -1 0 0;0 0 1 0;0 0 0 1;0 0 1 -1];
A3 = [1 0 -1 0 0 0;0 1 1 0 0 0;0 0 0 1 0 -1;0 1 1 -1 0 1;0 0 0 0 1 1];
B3 = [1 0 0 0 0;0 1 0 -1 0;0 0 1 1 0;0 0 0 0 1];
b3 = -[100;100;100;100];
relu = @(x)x .* (x>0);
id = @(x)x;
v = relu(A1 * u + a1);
w = id(B1 * v) ;
x = relu(A2 * w);
y = relu(A3 * x);
z = id(B3 * y + b3);
% disp(nnz(a1)+nnz(A1)+nnz(B1)+nnz(A2)+nnz(A3)+nnz(B3)+nnz(b3)); %uncomment to count the total number of weights
end

Wypróbuj online!

wada
źródło
1
Stałe przesunięcia są zasadniczo stosowane do tego, aby dane wejściowe były nieujemne. Po wykonaniu w pierwszej warstwie wszystkie wyniki pośrednie bloków porównania są nieujemne i wystarczy zmienić to tylko w ostatniej warstwie.
Joel
1
Czy możesz otrzymać krótszy gadżet min-max (a - relu(a-b), b + relu(a-b))?
xnor
@joel Oh teraz widzę, że to ma sens :)
flawr
@xnor Dziękuję bardzo, co robi ogromną różnicę !!!!
flawr
1
Nieistotny nitpick: Wynik pierwszego błędu jest nnz (A1 * a0), a nie nnz (a0). (W przeciwnym razie musimy zapłacić cenę matrycy tożsamości). Liczby te są w tym przypadku takie same.
Dustin G. Mixon,