Sortir dengan jaringan saraf

15

Tantangan golf neural net sebelumnya ( ini dan itu ) menginspirasi saya untuk mengajukan tantangan baru:

Tantangan

Temukan jaringan neural feedforward terkecil sehingga, diberikan setiap vektor input 4-dimensi (a,b,c,d) dengan entri integer di [10,10] , output jaringan sort(a,b,c,d) dengan kesalahan koordinat-bijaksana benar-benar lebih kecil dari 0.5 .

Tidak dapat diterima

Untuk tantangan ini, jaringan saraf umpan maju didefinisikan sebagai komposisi lapisan . Lapisan adalah fungsi L:RnRm yang ditentukan oleh matriks ARm×n dari bobot , vektor bRm dari bias , dan fungsi aktivasi f:RR yang diterapkan coordinate- bijaksana:

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

Since activation functions can be tuned for any given task, we need to restrict the class of activation functions to keep this challenge interesting. The following activation functions are permitted:

  • Identity. f(t)=t

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

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

  • Hyperbolic tangent. f(t)=tanh(t)

  • Sigmoid. f(t)=etet+1

Secara keseluruhan, sebuah jaring saraf yang dapat diterima mengambil bentuk LkLk1L2L1 untuk beberapa k , di mana setiap lapisan Li ditentukan oleh bobot Ai , bias bi , dan fungsi aktivasi fi dari daftar di atas. Misalnya, jaring saraf berikut ini dapat diterima (meskipun tidak memenuhi tujuan kinerja dari tantangan ini, itu mungkin merupakan gadget yang berguna):

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

Contoh ini menunjukkan dua lapisan. Kedua lapisan memiliki bias nol. Lapisan pertama menggunakan aktivasi ReLU, sedangkan yang kedua menggunakan aktivasi identitas.

Mencetak gol

Your score is the total number of nonzero weights and biases.

(E.g., the above example has a score of 16 since the bias vectors are zero.)

Dustin G. Mixon
sumber
2
@ Tutup pemilih: Apa yang sebenarnya tidak jelas? Saya tidak berpikir salah satu dari tantangan NN sebelumnya ditentukan dengan sangat baik.
flawr
1
Tidak - lewati koneksi tidak diperbolehkan.
Dustin G. Mixon
1
@ DustinG.Mixon Saya sebenarnya baru saja menemukan pendekatan untuk max / min yang hanya menggunakan 15 bobot, bukan 16, tapi itu jauh kurang elegan :)
flawr
3
Ini adalah tantangan khusus yang saya pikir bisa berfungsi sebagai model untuk tantangan jaringan saraf di masa depan.
xnor
1
Saya pribadi merasa sulit untuk mengoptimalkan tanpa melewatkan koneksi. Ini karena NN pengurutan diperlukan untuk menghasilkan angka yang cukup dekat dengan input. Jadi sepertinya perlu untuk 'mengingat' / 'merekonstruksi' input di seluruh lapisan. Saya tidak melihat bagaimana itu bisa dilakukan dengan mudah sekalietterlibat karena tidak ada invers fungsi yang diizinkan sebagai aktivasi. Jadi kita hanya dibiarkan dengan ReLU yang baseline (dengan perbaikan kecil seperti yang ditunjukkan dalam jawaban flawr) sudah mendekati optimal.
Joel

Jawaban:

13

Oktaf , 96 88 87 84 76 54 50 bobot & bias

Jaringan saraf 6 lapis ini pada dasarnya adalah jaringan sortir 3 langkah yang dibangun dari jaringan min/ maxkomponen yang sangat sederhana . Ini pada dasarnya adalah contoh jaringan dari wikipedia seperti yang ditunjukkan di bawah ini, dengan sedikit modifikasi: Dua perbandingan pertama dilakukan secara paralel. Untuk melewati angka negatif melalui ReLU, kita tambahkan saja 100 dulu, lalu kurangi 100 lagi di akhir.

Jadi ini harus dianggap sebagai baseline karena merupakan implementasi yang naif. Namun itu mengurutkan semua angka yang mungkin yang tidak memiliki besaran terlalu besar dengan sempurna. (Kami dapat menyesuaikan rentang dengan mengganti 100 dengan nomor lain.)

Cobalah online!

maks / komponen min

Ada cara (yang jauh kurang elegan lebih elegan sekarang, terima kasih @xnor!) Cara untuk menemukan minimum dan maksimum dua angka menggunakan lebih sedikit parameter:

min=Sebuah-ReL.U(Sebuah-b)maks=b+ReL.U(Sebuah-b)

Ini berarti kita harus menggunakan bobot dan bias yang jauh lebih sedikit.

Terima kasih @ Joel untuk menunjukkan bahwa cukup untuk membuat semua angka positif pada langkah pertama dan membalikkannya pada yang terakhir, yang menghasilkan bobot -8. Terima kasih @xnor karena telah menunjukkan metode max / min yang lebih pendek yang menghasilkan bobot -22! Terima kasih @ DustinG.Mixon untuk tip menggabungkan matriks tertentu yang menghasilkan bobot -4 lagi!

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

Cobalah online!

cacat
sumber
1
Offset konstan pada dasarnya digunakan untuk membuat input menjadi tidak negatif. Setelah dilakukan pada lapisan pertama, semua output antara dari blok pembanding adalah non-negatif dan cukup untuk mengubahnya kembali hanya di lapisan terakhir.
Joel
1
Mungkinkah Anda mendapatkan gadget min-max yang lebih pendek (a - relu(a-b), b + relu(a-b))?
xnor
@ joel Oh sekarang saya mengerti, itu masuk akal :)
flawr
@ xnor Terima kasih banyak yang membuat perbedaan besar !!!!
flawr
1
Nitpick tidak penting: Skor untuk bias pertama adalah nnz (A1 * a0), bukan nnz (a0). (Atau kita harus membayar harga matriks identitas.) Angka-angka ini sama dalam hal ini.
Dustin G. Mixon