Sortieren mit einem neuronalen Netzwerk

15

Die vorherigen Herausforderungen im Bereich des Golfsports mit neuronalen Netzen ( dies und das ) haben mich zu einer neuen Herausforderung inspiriert:

Die Herausforderung

Finden Sie das kleinste neuronale Feedforward-Netzwerk, sodass bei einem beliebigen 4-dimensionalen Eingabevektor mit ganzzahligen Einträgen in das Netzwerk ausgibt mit einem Koordinatenfehler von weniger als .(a,b,c,d)[10,10]sort(a,b,c,d)0.5

Zulässigkeit

Für diese Herausforderung wird ein vorwärts gerichtetes neuronales Netzwerk als eine Zusammensetzung von Schichten definiert . Eine Schicht ist eine Funktion , die durch eine Matrix von Gewichten , einem Vektor , spezifiziert ist von Verzerrungen und eine Aktivierungsfunktion , die koordinativ angewendet wird:L:RnRmARm×n b R m f : RRbRm f:RR

L(x):=f(Ax+b),xRn.

Da Aktivierungsfunktionen für eine bestimmte Aufgabe optimiert werden können, müssen wir die Klasse der Aktivierungsfunktionen einschränken, um diese Herausforderung interessant zu halten. Folgende Aktivierungsfunktionen sind zulässig:

  • Identität. f(t)=t

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

  • Softplus. f(t)=ln(et+1)

  • Hyperbolischer Tangens. f(t)=tanh(t)

  • Sigmoid. f(t)=etet+1

Insgesamt hat ein zulässiges neuronales Netz für einige die Form , wobei jede Schicht durch Gewichte , Vorspannungen und eine Aktivierungsfunktion spezifiziert ist aus der obigen Liste. Das folgende neuronale Netz ist beispielsweise zulässig (obwohl es das Leistungsziel dieser Herausforderung nicht erfüllt, kann es ein nützliches Gadget sein):LkLk1L2L1kLiAibifi

[min(a,b)max(a,b)]=[111212111212]ReLU[121212121111][ab]

Dieses Beispiel zeigt zwei Schichten. Beide Schichten haben keine Vorspannung. Die erste Schicht verwendet die ReLU-Aktivierung, während die zweite die Identitätsaktivierung verwendet.

Wertung

Ihre Punktzahl ist die Gesamtzahl der Gewichte und Verzerrungen ungleich Null .

(ZB hat das obige Beispiel eine Punktzahl von 16, da die Vorspannungsvektoren Null sind.)

Dustin G. Mixon
quelle
2
@Nahwähler: Was genau ist unklar? Ich denke nicht, dass eine der vorherigen NN-Herausforderungen so gut spezifiziert war.
27.
1
No-Skip-Verbindungen sind nicht zulässig.
Dustin G. Mixon
1
@ DustinG.Mixon Ich habe gerade einen Ansatz für die max / min gefunden, der nur 15 Gewichte anstelle von 16 verwendet, aber es ist wesentlich weniger elegant :)
Fehler
3
Dies ist eine genau festgelegte Herausforderung, die meines Erachtens als Modell für zukünftige neuronale Netzwerkherausforderungen dienen könnte.
27.
1
Ich persönlich finde es schwierig, zu optimieren, ohne Verbindungen zu überspringen. Dies liegt daran, dass eine Sortiernummer erforderlich ist, um Zahlen auszugeben, die nahe genug an den Eingängen liegen. Es scheint also notwendig zu sein, die Eingaben über Ebenen hinweg zu "merken" / "rekonstruieren". Ich sehe nicht ein, wie das einfach gemacht werden kann, wenn es sich um eine handelt, da es keine Umkehrungen dieser Funktionen gibt, die als Aktivierungen erlaubt sind. Wir bleiben also nur bei den ReLUs, für die die Basislinie (mit geringfügigen Verbesserungen, wie in der Antwort von flawr gezeigt) bereits nahezu optimal ist. et
Joel

Antworten:

13

Octave , 96 88 87 84 76 54 50 Gewichte & Vorspannungen

Dieses 6-lagige neuronale Netz ist im Wesentlichen ein 3-stufiges Sortiernetz, das aus einem sehr einfachen min/ max Netzwerk als Komponente aufgebaut ist. Es handelt sich im Grunde genommen um das Beispielnetzwerk aus Wikipedia (siehe unten) mit einer kleinen Änderung: Die ersten beiden Vergleiche werden parallel durchgeführt. Um negative Zahlen durch die ReLU zu umgehen, addieren wir zuerst 100 und subtrahieren am Ende erneut 100.

Dies sollte nur als Basis betrachtet werden, da es sich um eine naive Implementierung handelt. Es werden jedoch alle möglichen Zahlen, die keine zu große Größe haben, perfekt sortiert. (Wir können den Bereich anpassen, indem wir 100 durch eine andere Zahl ersetzen.)

Probieren Sie es online!

max / min-Komponente

Es gibt eine Möglichkeit ( wesentlich weniger elegant , dank @xnor!), Das Minimum und Maximum von zwei Zahlen mit weniger Parametern zu ermitteln:

min=aReLU(ab)max=b+ReLU(ab)

Dies bedeutet, dass wir viel weniger Gewichte und Vorspannungen verwenden müssen.

Vielen Dank an @Joel für den Hinweis, dass es ausreicht, alle Zahlen im ersten Schritt positiv zu machen und im letzten Schritt umzukehren, was -8 Gewichte ergibt. Vielen Dank an @xnor für den Hinweis auf eine noch kürzere Max / Min-Methode, die -22 Gewichte ergibt! Vielen Dank an @ DustinG.Mixon für den Tipp, bestimmte Matrizen zu kombinieren, die zu weiteren -4 Gewichten führen!

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

Probieren Sie es online!

fehlerhaft
quelle
1
Die konstanten Offsets werden grundsätzlich verwendet, um die Eingänge nicht negativ zu machen. Sobald dies in der ersten Schicht geschehen ist, sind alle Zwischenausgaben der Vergleichsblöcke nicht negativ und es genügt, sie nur in der letzten Schicht zurück zu ändern.
Joel
1
Könnten Sie ein kürzeres Min-Max-Gadget mit bekommen (a - relu(a-b), b + relu(a-b))?
28.
@ joel Oh, jetzt verstehe ich, das macht sehr viel Sinn :)
Fehler
@xnor Vielen Dank, der einen großen Unterschied macht !!!!
28.
1
Inkonsequenter Nitpick: Der Score für den ersten Bias ist nnz (A1 * a0), nicht nnz (a0). (Andernfalls müssen wir den Preis für eine Identitätsmatrix bezahlen.) Diese Zahlen sind in diesem Fall dieselben.
Dustin G. Mixon