Golf Pembelajaran Mesin: Perkalian

68

Saya ingin mengusulkan berbagai tantangan golf untuk komunitas ini:

(Buatan) Jaringan Saraf Tiruan adalah model pembelajaran mesin yang sangat populer yang dapat dirancang dan dilatih untuk memperkirakan fungsi apa pun (biasanya tidak diketahui). Mereka sering digunakan untuk memecahkan masalah yang sangat kompleks yang kita tidak tahu bagaimana menyelesaikan secara algoritmik seperti pengenalan suara, beberapa jenis klasifikasi gambar, berbagai tugas dalam sistem mengemudi otonom, ... Untuk primer pada jaringan saraf, pertimbangkan ini sangat baik Artikel Wikipedia .

Karena ini adalah yang pertama dalam apa yang saya harapkan menjadi serangkaian tantangan golf pembelajaran mesin, saya ingin menjaga semuanya sesederhana mungkin:

Dalam bahasa dan kerangka kerja pilihan Anda, rancang dan latih jaringan saraf yang, diberikan menghitung produk mereka untuk semua bilangan bulat x_1, x_2 antara (dan termasuk) -10 dan 10 .(x1,x2)x1x2x1,x21010

Tujuan Kinerja

Agar memenuhi syarat, model Anda tidak boleh menyimpang lebih dari 0.5 dari hasil yang benar pada salah satu entri tersebut.

Aturan

Model Anda

  • harus berupa jaringan saraf 'tradisional' (nilai sebuah simpul dihitung sebagai kombinasi linear tertimbang dari beberapa simpul dalam lapisan sebelumnya diikuti oleh fungsi aktivasi),
  • hanya dapat menggunakan fungsi aktivasi standar berikut:
    1. linear(x)=x ,
    2. softmax(x)i=exijexj ,
    3. seluα,β(x)={βx, if x>0αβ(ex1), otherwise ,
    4. softplus(x)=ln(ex+1) ,
    5. leaky-reluα(x)={x, if x<0αx, otherwise ,
    6. tanh(x) ,
    7. sigmoid(x)=exex+1 ,
    8. hard-sigmoid(x)={0, if x<2.51, if x>2.50.2x+0.5, otherwise ,
    9. ex
  • harus menggunakan sebagai tupel / vektor / daftar / ... bilangan bulat atau mengapung sebagai satu-satunya input,(x1,x2)
  • kembalikan jawaban sebagai bilangan bulat, float (atau wadah yang sesuai, misalnya vektor atau daftar, yang berisi jawaban ini).

Jawaban Anda harus mencakup (atau menautkan ke) semua kode yang diperlukan untuk memeriksa hasil Anda - termasuk bobot yang terlatih dari model Anda.

Mencetak gol

Jaringan saraf dengan jumlah bobot terkecil (termasuk bobot bias) menang.

Nikmati!

Stefan Mesken
sumber
9
Selamat datang di situs ini! Saya pikir tantangan ini dapat menguntungkan banyak dari definisi yang lebih kuat dari jaringan saraf. Ada beberapa hal di sini 1) Akan sangat baik bagi Anda untuk menyatakannya dalam bahasa yang belum menyiratkan pengetahuan tentang NNs 2) Anda benar-benar harus membuat daftar fungsi aktivasi dalam posting Anda daripada menghubungkan ke sumber eksternal ( tautan luar dapat berubah atau menghilang).
Wheat Wizard
4
Bisakah kita menggunakan kembali bobot / menggunakan lapisan konvolusional? (Saya sarankan menghapus bonus, karena tidak menambah apa pun pada tantangan dan hanya mengalihkan dari tujuan utama.) Apakah bobotnya seharusnya nyata atau dapat mereka kompleks?
flawr
4
Kata-kata Anda menyiratkan node dari layer 3 tidak dapat menggunakan input dari layer 1. Apakah perlu biaya untuk memiliki node layer 2 hanya melakukan f(x) = xuntuk meneruskan inputnya?
Grimmy
4
Seharusnya ada tautan di kolom kanan ke Sandbox, yang dibuat secara tegas untuk memperbaiki masalah semacam ini sebelum pertanyaan bahkan diposting ke situs utama. Dan filosofi jaringan adalah bahwa lebih baik untuk menutup pertanyaan, memperbaikinya, dan membukanya kembali daripada untuk mendapatkan banyak jawaban yang tidak masuk akal setelah pertanyaan itu diperbaiki atau akan dengan ketat membatasi perubahan yang dapat dibuat untuk pertanyaan tersebut .
Peter Taylor
7
Tidak semuanya. Masalah-masalah seperti ini terdeteksi oleh pengalaman bertahun-tahun melihat orang lain melakukan kesalahan yang sama. Beberapa ambiguitas menyelinap melewati kotak pasir, tetapi lebih banyak lagi yang terperangkap di sana. Dan ini pasti akan tertangkap, karena seperti yang ditunjukkan dalam komentar pertama saya, kami memiliki masalah yang sama persis dengan pertanyaan jaringan saraf dua bulan lalu.
Peter Taylor

Jawaban:

37

21 13 11 9 bobot

Ini didasarkan pada identitas polarisasi bentuk bilinear yang dalam kasus nyata satu dimensi direduksi menjadi identitas polinomial:

xy=(x+y)2(xy)24

Jadi y1hanya menghitung [x+y, x-y]menggunakan transformasi linier, dan y3hanya nilai absolut y1sebagai langkah preprocessing untuk yang berikutnya: Kemudian bagian "keras" adalah menghitung kotak yang akan saya jelaskan di bawah, dan setelah itu hanya menghitung perbedaan dan penskalaan yang sekali lagi merupakan operasi linier.

Untuk menghitung kuadrat saya menggunakan seri eksponensial yang harus akurat untuk semua bilangan bulat dalam waktu sekitar . Seri ini berbentuks{0,1,2,,20}0.5

approx_square(x)=i=02wiexp(0.0001ix)

di mana saya hanya dioptimalkan untuk bobot W2( ). Keseluruhan perkiraan ini terdiri dari hanya dua transformasi linear dengan aktivasi eksponensial yang berada di antaranya. Pendekatan ini menghasilkan penyimpangan maksimal tentang .=(wi)i0.02

function p = net(x)
% 9 weights
one = 1; 
mone =-1;
zero = 0;
fourth = 0.25;
W1 = [1e-4, 2e-4];
W2  = [-199400468.100687;99700353.6313757];
b2 = 99700114.4299316;
leaky_relu = @(a,x)max(a*x,x); 


% Linear
y0 = [one, one; one, mone] * x;

% Linear + ReLU
y1 = mone * y0;
y2 = [leaky_relu(zero, y0), leaky_relu(zero, y1)];

% Linear
y3 = y2 * [one; one];

% Linear + exp
y4 = exp(y3 * W1); 

% Linear + Bias
y5 =  y4 * W2 + b2;

% Linear
y6 = [one, mone]*y5;
p = y6 * fourth;

end

Cobalah online!

cacat
sumber
Saya pikir kode pemeriksaan Anda di bagian bawah tautan TIO melewatkan aplikasi abs. Tapi bagaimanapun juga semuanya baik-baik saja.
Christian Sievers
@ChristianSievers Terima kasih, saya memperbarui tautan TIO!
flawr
Saya bukan ahli NN, karena penasaran, bagaimana perhitungan berat badan dilakukan? y0kebutuhan 4, y1kebutuhan 2, y3kebutuhan 2, y4kebutuhan 1, y5kebutuhan 1 dan y6kebutuhan 2. Itu 12?
Margaret Bloom
3
@MargaretBloom Ya ini memang sedikit tidak biasa, tetapi OP mengatakan dalam komentar bahwa kita dapat menggunakan kembali bobot dan hanya perlu menghitungnya sekali, bahkan jika kita menggunakan berat yang sama beberapa kali. Jadi semua bobot yang saya gunakan didefinisikan di bagian pertama dari fungsi.
flawr
31

7 bobot

eps = 1e-6
c = 1 / (2 * eps * eps)

def f(A, B):
	e_s = exp(eps * A + eps * B)  # 2 weights, exp activation
	e_d = exp(eps * A - eps * B)  # 2 weights, exp activation
	return c * e_s + (-c) * e_d + (-1 / eps) * B  # 3 weights, linear activation

Cobalah online!

Gunakan perkiraan persamaan berikut untuk kecil berdasarkan ekspansi Taylor :ϵex1+x+x22

ABeϵA+ϵBeϵAϵB2ϵ2Bϵ

Memilih cukup kecil membuat kita dalam batas kesalahan yang diperlukan. Perhatikan itu dan merupakan bobot konstan dalam kode.ϵepsc

Tidak
sumber
1
Tidak yakin bahwa ini dianggap sebagai 'jaringan saraf tradisional' (aturan # 1) tetapi jelas bahwa itu dapat diformat ulang menjadi satu, jadi saya tidak melihat ada masalah dengan itu. Solusi bagus!
Stefan Mesken
1
Anda dapat mendefinisikan C = -B(1 berat) dan kemudian memiliki [e_s, e_d] = conv([A,B,C], [eps, eps])(2 bobot) untuk menghemat satu berat :) (BTW: Pendekatan yang sangat cerdas!)
flawr
(Saya lupa menambahkan exp)
flawr
4
Anda bahkan bisa mendapatkan jauh lebih rendah dengan menggunakan kembali bobot - Anda tidak harus menghitung berat yang sama beberapa kali.
flawr
2
@ flawr Itu trik yang bagus, tapi saya pikir kelonggaran untuk konvolusi dan menggunakan kembali bobot dalam komentar membuat ini menjadi tantangan yang sangat berbeda sehingga saya akan tetap mempertahankan jawaban ini.
xnor
22

33 31 bobot

# Activation functions
sub hard { $_[0] < -2.5 ? 0 : $_[0] > 2.5 ? 1 : 0.2 * $_[0] + 0.5 }
sub linear { $_[0] }

# Layer 0
sub inputA() { $a }
sub inputB() { $b }

# Layer 1
sub a15() { hard(5*inputA) }

# Layer 2
sub a8()  { hard(-5*inputA + 75*a15 - 37.5) }

# Layer 3
sub aa()  { linear(-5*inputA + 75*a15 - 40*a8) }

# Layer 4
sub a4()  { hard(aa - 17.5) }

# Layer 5
sub a2()  { hard(aa - 20*a4 - 7.5) }

# Layer 6
sub a1()  { linear(0.2*aa - 4*a4 - 2*a2) }

# Layer 7
sub b15() { hard(0.25*inputB - 5*a15) }
sub b8()  { hard(0.25*inputB - 5*a8) }
sub b4()  { hard(0.25*inputB - 5*a4) }
sub b2()  { hard(0.25*inputB - 5*a2) }
sub b1()  { hard(0.25*inputB - 5*a1) }

# Layer 8
sub output() { linear(-300*b15 + 160*b8 + 80*b4 + 40*b2 + 20*b1 - 10*inputA) }

# Test
for $a (-10..10) {
        for $b (-10..10) {
                die if abs($a * $b - output) >= 0.5;
        }
}

print "All OK";

Cobalah online!

Ini melakukan multiplikasi panjang dalam (agak) biner, dan dengan demikian mengembalikan hasil yang tepat. Seharusnya dimungkinkan untuk memanfaatkan jendela kesalahan 0,5 untuk golf ini lagi, tapi saya tidak yakin bagaimana.

Lapisan 1 hingga 6 menguraikan input pertama dalam 5 "bit". Untuk alasan bermain golf, kami tidak menggunakan biner yang sebenarnya. "Bit" yang paling signifikan memiliki bobot -15 bukannya 16, dan ketika inputnya 0, semua "bit" adalah 0,5 (yang masih berfungsi dengan baik, karena ia mempertahankan identitas inputA = -15*a15 + 8*a8 + 4*a4 + 2*a2 + 1*a1).

Grimmy
sumber
1
Saya memang mengharapkan seseorang untuk datang dengan algoritma perkalian JN-ified yang dikodekan dengan hard-code. Tetapi saya tidak berpikir itu akan menjadi jawaban pertama. Sudah selesai dilakukan dengan baik! (Saya juga ingin melihat apakah Anda akan dapat melakukan hal seperti ini dengan dataset MNIST atau masalah ML lainnya yang lebih relastik: D.)
Stefan Mesken
14

43 bobot

Dua solusi yang diposting sejauh ini sangat pintar tetapi pendekatan mereka kemungkinan tidak akan bekerja untuk tugas-tugas yang lebih tradisional dalam pembelajaran mesin (seperti OCR). Karenanya saya ingin mengajukan solusi 'generik' (tanpa trik pintar) untuk tugas ini yang semoga menginspirasi orang lain untuk meningkatkannya dan terjebak dalam dunia pembelajaran mesin:

Model saya adalah jaringan saraf yang sangat sederhana dengan 2 lapisan tersembunyi yang dibangun di TensorFlow 2.0 (tetapi kerangka kerja lainnya juga akan berfungsi):

model = tf.keras.models.Sequential([
tf.keras.layers.Dense(6, activation='tanh', input_shape=(2,)),
tf.keras.layers.Dense(3, activation='tanh'),
tf.keras.layers.Dense(1, activation='linear')
])

Seperti yang Anda lihat, semua layer padat (yang pastinya tidak optimal), fungsi aktivasi tanh (yang sebenarnya mungkin oke untuk tugas ini), kecuali untuk layer output itu, karena sifat dari tugas ini, memiliki fungsi aktivasi linier.

Ada 43 bobot:

  • (2+1)6=18 antara input dan lapisan tersembunyi pertama,
  • (6+1)3=21 antara lapisan tersembunyi dan
  • (3+1)1=4 menghubungkan yang terakhir disembunyikan dan lapisan keluaran.

Bobot telah dilatih (dengan adam optimizer) dengan pendekatan pemasangan berlapis: Pertama, mereka telah dipasang untuk meminimalkan kesalahan kuadrat rata-rata tidak hanya pada perkalian bilangan bulat antara dan tetapi sebenarnya pada input di lingkungan tertentu di sekitar nilai-nilai ini . Ini menghasilkan konvergensi yang jauh lebih baik karena sifat gradient descent. Dan itu menyumbang 400 epochs pelatihan senilai 57.600 sampel pelatihan masing-masing, menggunakan ukuran batch 32.1010

Selanjutnya, saya telah menyesuaikan mereka - mengoptimalkan untuk deviasi maksimum pada salah satu tugas perkalian bilangan bulat. Sayangnya, catatan saya tidak menunjukkan banyak penyesuaian yang akhirnya saya lakukan, tetapi itu sangat kecil. Di lingkungan 100 zaman pada 441 sampel pelatihan, dengan ukuran batch 441.

Inilah bobot yang akhirnya saya dapatkan:

[<tf.Variable 'dense/kernel:0' shape=(2, 6) dtype=float32, numpy=
 array([[ 0.10697944,  0.05394982,  0.05479664, -0.04538541,  0.05369904,
         -0.0728976 ],
        [ 0.10571832,  0.05576797, -0.04670485, -0.04466859, -0.05855528,
         -0.07390639]], dtype=float32)>,
 <tf.Variable 'dense/bias:0' shape=(6,) dtype=float32, numpy=
 array([-3.4242163, -0.8875816, -1.7694025, -1.9409281,  1.7825342,
         1.1364107], dtype=float32)>,
 <tf.Variable 'dense_1/kernel:0' shape=(6, 3) dtype=float32, numpy=
 array([[-3.0665843 ,  0.64912266,  3.7107112 ],
        [ 0.4914808 ,  2.1569328 ,  0.65417236],
        [ 3.461693  ,  1.2072319 , -4.181983  ],
        [-2.8746269 , -4.9959164 ,  4.505049  ],
        [-2.920127  , -0.0665407 ,  4.1409926 ],
        [ 1.3777553 , -3.3750365 , -0.10507642]], dtype=float32)>,
 <tf.Variable 'dense_1/bias:0' shape=(3,) dtype=float32, numpy=array([-1.376577  ,  2.8885336 ,  0.19852689], dtype=float32)>,
 <tf.Variable 'dense_2/kernel:0' shape=(3, 1) dtype=float32, numpy=
 array([[-78.7569  ],
        [-23.602606],
        [ 84.29587 ]], dtype=float32)>,
 <tf.Variable 'dense_2/bias:0' shape=(1,) dtype=float32, numpy=array([8.521169], dtype=float32)>]

yang hampir tidak memenuhi sasaran kinerja yang dinyatakan. Penyimpangan maksimal berakhir menjadi sebagai saksi oleh .0.44350433910=90.443504

Model saya dapat ditemukan di sini dan Anda juga dapat mencobanya online! di lingkungan Google Colab.

Stefan Mesken
sumber
6

2 beban

Saya terinspirasi oleh jawaban lain untuk memperkirakan identitas polarisasi dengan cara yang berbeda. Untuk setiap , ia berpendapat demikianϵ>0

xyeϵx+ϵy+eϵxϵyeϵxϵyeϵx+ϵy4ϵ2.

Cukup untuk mengambil untuk tantangan ini.ϵ=0.01

Implementasi neural net yang jelas dari perkiraan ini membutuhkan bobot dalam . Keempat bobot ini dapat diturunkan menjadi tiga dengan memfaktorkan . Seperti yang saya sebutkan di komentar di atas, setiap jaring saraf dengan bobot dalam presisi mesin dapat di-golf ke jaring saraf (besar!) Dengan hanya dua bobot berbeda. Saya menerapkan prosedur ini untuk menulis kode MATLAB berikut:{±ϵ,±(4ϵ2)1}{±ϵ,(4ϵ3)1}±(4ϵ2)1=±ϵ(4ϵ3)1

function z=approxmultgolfed(x,y)

w1 = 0.1;   % first weight
w2 = -w1;   % second weight

k  = 250000;
v1 = w1*ones(k,1);
v2 = w2*ones(k,1);

L1 = w1*eye(2);
L2 = [ w1 w1; w2 w2; w1 w2; w2 w1 ];
L3 = [ v1 v1 v2 v2 ];
L4 = v1';

z = L4 * L3 * exp( L2 * L1 * [ x; y ] );

Semua mengatakan, jaring saraf ini terdiri dari 1.250.010 bobot, yang semuanya berada di .{±0.1}

Cara melepaskan diri hanya dengan 1 berat (!)

Ternyata Anda dapat mensimulasikan jaring saraf mana pun yang memiliki bobot dalam dengan jaring saraf yang lebih besar yang hanya memiliki satu berat, yaitu, . Memang, perkalian dengan dapat diimplementasikan sebagai{±0.1}0.10.1

0.1x=wwx,

di mana adalah vektor kolom dari entri, semua sama dengan . Untuk jaring saraf di mana setengah dari bobotnya positif, transformasi ini menghasilkan jaring saraf yang kali lebih besar.w100.110.5

Generalisasi yang jelas dari prosedur ini akan mengubah jaring saraf dengan bobot dalam menjadi jaring saraf yang lebih besar dengan berat tunggal . Dikombinasikan dengan prosedur dalam komentar saya di atas, oleh karena itu menyatakan bahwa setiap jaring saraf dengan bobot presisi mesin dapat diubah menjadi jaring saraf berat tunggal.{±10k}10k

(Mungkin kita harus memodifikasi bagaimana bobot yang digunakan kembali dinilai dalam tantangan golf saraf masa depan.)

Dustin G. Mixon
sumber