Temukan akar polinomial terbesar dengan jaringan saraf

11

Tantangan

Temukan jaringan neural feedforward terkecil sehingga, diberikan setiap vektor input 3 dimensi (a,b,c) dengan entri integer di [-10,10] , jaringan menghasilkan akar terbesar (yaitu, "paling positif") dari polinomial dengan kesalahan lebih kecil dari .x3+Sebuahx2+bx+c0,1

Tidak dapat diterima

Gagasan penerimaan dalam tantangan golf saraf saya sebelumnya tampak agak membatasi, jadi untuk tantangan ini, kami menggunakan definisi yang lebih liberal dari jaringan neural feedforward:

Sebuah neuron adalah fungsi ν:RnR yang ditentukan oleh vektor wRn dari bobot , sebuah Bias bR , dan fungsi aktivasi f:RR dengan cara berikut:

ν(x): =f(wx+b),xRn.

Jaringan neural feedforward dengan input node {1,...,n} adalah fungsi dari (x1,...,xn)Rn yang dapat dibangun dari urutan (νk)k=n+1N neuron, di mana setiap νk:Rk-1R mengambil input dari (x1,...,xk-1)dan menghasilkan skalarxk . Mengingat beberapa ditentukan setS{1,...,N}darioutput node, maka output dari jaringan saraf adalah vektor(xk)kS .

Karena fungsi aktivasi dapat disetel untuk setiap tugas yang diberikan, kita perlu membatasi kelas fungsi aktivasi untuk membuat tantangan ini tetap menarik. Fungsi aktivasi berikut diizinkan:

  • Identitas. f(t)=t

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

  • SoftPlus. f(t)=dalam(et+1)

  • Sigmoid. f(t)=etet+1

  • Sinusoid. f(t)=dosat

Secara keseluruhan, jaring saraf yang dapat diterima ditentukan oleh node input, urutan neuron, dan node output, sementara masing-masing neuron ditentukan oleh vektor bobot, bias, dan fungsi aktivasi dari daftar di atas. Misalnya, jaring saraf berikut ini dapat diterima, meskipun tidak memenuhi tujuan kinerja dari tantangan ini:

  • Input node: {1,2}

  • Neuron: νk(x1,...,xk-1): =xk-2+xk-1 untuk k{3,...,10}

  • Node keluaran: {5,9,10}

Jaringan ini terdiri dari 8 neuron, masing-masing dengan nol bias dan aktivasi identitas. Dengan kata lain, jaringan ini menghitung urutan Fibonacci umum yang dihasilkan oleh x1 dan x2 dan kemudian menampilkan angka 5, 9, dan 10 dari urutan ini, dalam urutan itu.

Mencetak gol

Mengingat bilangan real x dengan mengakhiri ekspansi desimal, biarkan hal(x) menjadi yang terkecil non-negatif bilangan bulat hal yang 10p|x|<1 , dan biarkan q(x) menjadi yang terkecil bilangan bulat positif q yang 10qx adalah integer. Kemudian kita katakan p(x)+q(x) adalah presisi dari x .

Misalnya, x=1,001 memiliki ketepatan 4 , sedangkan x=0 memiliki ketepatan 0 .

Skor Anda adalah jumlah dari prasyarat bobot dan bias dalam jaringan saraf Anda.

(Misalnya, contoh di atas memiliki skor 16.)

Verifikasi

Meskipun akar dapat diekspresikan dengan rumus kubik , akar terbesar mungkin paling mudah diakses dengan cara numerik. Mengikuti saran xnor, saya menghitung root terbesar untuk setiap pilihan bilangan bulat Sebuah,b,c[-10,10] , dan hasilnya dapat ditemukan di sini . Setiap baris file teks ini berbentuk a,b,c,root. Sebagai contoh, baris pertama melaporkan bahwa root terbesar x3-10x2-10x-10 adalah sekitar 10.99247140445449 .

Sunting: File asli yang saya poskan memiliki kesalahan dalam kasus-kasus di mana polinomial memperlihatkan multi-root. Versi saat ini harus bebas dari kesalahan tersebut.

Dustin G. Mixon
sumber
3
Apa yang terjadi pada input polinomial tidak memiliki akar nyata, seperti kapan a=0dan kuadratik memiliki dua akar kompleks?
xnor
Saya pikir solusi terbersih akan mengatakan bahwa input akan amenjadi nol, atau bahkan hanya 1. Juga, saya akan merekomendasikan memasukkan beberapa kasus uji, memberikan akar ke presisi tinggi sehingga kami dapat memeriksa kami berada dalam 0,1. Akan lebih baik untuk memiliki output untuk semua input yang mungkin, mungkin di tautan karena itu banyak untuk posting.
xnor
1
Saya suka aturan penerimaan yang baru. Sepertinya fungsi sinusoid baru sangat bisa dieksploitasi. Saya punya bukti samar bahwa fungsi formulir x -> a * sin(b * softplus(x) + c)dapat melebihi jumlah poin data hingga dengan xpresisi sembarang dengan menggunakan frekuensi yang sangat besar dan tepat.
xnor
1
Tidak yakin seberapa berguna itu (untuk tantangan di masa depan): Dalam teori bilangan kita menggunakan fungsi ketinggian untuk mengukur kompleksitas bilangan. Misalnya tinggi naif dari fraksi (dikurangi) diberikan oleh h = log max { | p | , | q | } (dan ada banyak generalisasi). Mungkin ini bisa digunakan sebagai langkah alternatif. p/qh=logmax{|p|,|q|}
flawr
1
@ DustinG.Mixon Saya tidak yakin apakah Anda sadar tetapi kami memiliki kotak pasir untuk memposting konsep dan mendiskusikan detail tantangan serta obrolan .
flawr

Jawaban:

6

14674000667 5.436.050 5.403.448 10.385 5994 4447
3806 Total presisi

Untuk baseline, saya menyelidiki pendekatan berikut: Pilih M.,δ,ϵ>0 sehingga jika kita sampel polinomial hal(x)=x3+Sebuahx2+bx+c di

S: ={-M.,-M.+δ,-M.+2δ,...,M.},

maka titik sampel terbesar sS memuaskan hal(s)<ϵ tentu ada dan selalu berada dalam 0,1 dari akar hal . Kita dapat menunjukkan bahwa untuk koleksi polinomial kita, kita dapat mengambil M.=11 , δ=0,1 , dan ϵ=104 .

Untuk merancang jaringan saraf yang mengimplementasikan logika ini, kita mulai dengan lapisan neuron bahwa sampel polinomial pada S . Untuk setiap sS , kami ambil

x1,s=s2a+sb+1c+s3.

Selanjutnya, kami mengidentifikasi yang mana yang kurang dari ϵ=104 . Ternyata untuk sS , ia menyatakan bahwa p(s)<104 hanya jika hal(s)0 . Dengan demikian, kita dapat menggunakan aktivasi relu untuk mengidentifikasi sampel kami dengan tepat:

relkamu(10-4-t)-relkamu(-t)10-4={1jika t00jika t10-4.

Kami menerapkan ini dengan beberapa lapisan neuron:

x2,s=relu(1x1,s+104),x3,s=relu(1x1,s),x4,s=104x2,s104x3,s.

Pada titik ini, kita memiliki x4,s=1 ketika p(s)<104 , dan sebaliknya x4,s=0 . Ingat bahwa kita mencari terbesar s yang x4,s=1 . Untuk tujuan ini, kami memberi label x4,M sebagai x5,M (untuk kenyamanan notasi), dan untuk setiap k1, kami mendefinisikan secara iteratif

x5,Mkδ=1x4,Mkδ+2x5,M(k1)δ=j=0k2kjx4,Mjδ.

Berkat transformasi ini, setiap x5,s adalah bilangan bulat tidak negatif, dan s adalah s unik yang x5,s=1 . Kami sekarang dapat mengidentifikasi s dengan aplikasi lain dari aktivasi relu:

relu(t2)2relu(t1)+t={1if t=10if tZ0{1}.

Secara eksplisit, kami mendefinisikan neuron dengan

x6,s=relu(1x5,s2),x7,s=relu(1x5,s1),x8,s=1x6,s2x7,s+1x5s.

Kemudian x8,s=1 jika s=s dan sebaliknya x8,s=0 . Kami menggabungkan ini secara linear untuk menghasilkan simpul keluaran kami:

x9=sSsx8,s=s.

Untuk skor, setiap lapisan memiliki neuron dengan tingkat presisi berbeda: (1) 6+3+1+9=19 , (2) 1+4=5 , (3) 1 , (4) 5+5=10 , (5) 1+1=2 , (6) 1+1=2 , (7) 1+1=2 , (8) 1+1+1=3 , (9) 3|S|. Selanjutnya, semua kecuali dua lapisan memiliki|S|=221 neuron; layer 5 memiliki|S|-1 neuron dan layer 9 memiliki1 neuron.

Sunting: Perbaikan: (1) Kami dapat mengambil sampel polinomial dengan lebih efisien menggunakan perbedaan hingga. (2) Kita dapat memotong lapisan 2 hingga 4 dengan menggunakan aktivasi sigmoid. (3) Masalah kelebihan pada lapisan 5 dapat dihindari (dan lapisan berikutnya dapat digabungkan) dengan lebih hati-hati menerapkan aktivasi relu. (4) Jumlah akhir lebih murah dengan penjumlahan per bagian .

Berikut ini adalah kode MATLAB. Agar jelas, precadalah fungsi (ditemukan di sini ) yang menghitung ketepatan vektor bobot atau bias.

function sstar = findsstar2(a,b,c)

relu = @(x) x .* (x>0);

totprec = 0;

% x1 samples the polynomial on -11:0.1:11
x1=[];
for s = -11:0.1:11
    if length(x1) < 5
        w1 = [s^2 s 1];
        b1 = s^3;
        x1(end+1,:) = w1 * [a; b; c] + b1;
        totprec = totprec + prec(w1) + prec(b1);
    else
        w1 = [-1 4 -6 4];
        x1(end+1,:) = w1 * x1(end-3:end,:);
        totprec = totprec + prec(w1);
    end
end

% x4 indicates whether the polynomial is nonpositive
w4 = -6e5;
b4 = 60;
x4=[];
for ii=1:length(x1)
    x4(end+1) = sigmf(w4 * x1(ii) + b4, [1,0]);
    totprec = totprec + prec(w4) + prec(b4);
end

% x6 indicates which entries are less than or equal to sstar
x5 = zeros(size(x1));
x6 = zeros(size(x1));
x5(end) = 0;
x6(end) = 0;
for ii = 1:length(x5)-1
    w5 = [-1 -1];
    b5 = 1;
    x5(end-ii) = relu(w5 * [x4(end-ii); x6(end-ii+1)] + b5);
    totprec = totprec + prec(w5) + prec(b5);
    w6 = -1;
    b6 = 1;
    x6(end-ii) = w6 * x5(end-ii) + b6;
    totprec = totprec + prec(w6) + prec(b6);
end

% a linear combination produces sstar
w7 = 0.1*ones(1,length(x1));
w7(1) = -11;
sstar = w7 * x6;

%disp(totprec) % uncomment to display score

end
Dustin G. Mixon
sumber
2

53.268 29.596 29.306 total presisi

Komunikasi pribadi dengan @ A.Rex mengarah ke solusi ini, di mana kami membangun jaringan saraf yang mengingat jawaban. Gagasan intinya adalah bahwa setiap fungsi f:SR pada himpunan terbatas S menikmati dekomposisi

f(x)=sSf(s){1jika x=s0lain}.

f

relkamu(t-1)-2relkamu(t)+relkamu(t+1)={1jika t=00jika tZ{0}.

Berikut ini adalah implementasi MATLAB dari pendekatan ini. Yang jelas, roots.txtadalah file root yang diposting di atas (ditemukan di sini ), dan precmerupakan fungsi (ditemukan di sini ) yang menghitung presisi total dari vektor bobot atau bias.

Sunting 1: Dua peningkatan dibandingkan yang asli: (1) Saya memfaktorkan beberapa neuron untuk loop. (2) Saya menerapkan " integrasi Lebesgue " dalam jumlah akhir dengan terlebih dahulu menggabungkan istilah dari set level yang sama. Dengan cara ini, saya membayar nilai presisi yang lebih tinggi dari suatu output hanya sekali setiap level yang ditetapkan. Juga, aman untuk membulatkan output ke kelima terdekat dengan teorema akar rasional .

Sunting 2: Tambahan kecil tambahan: (1) Saya memfaktorkan lebih banyak neuron dari perulangan for. (2) Saya tidak repot menghitung istilah dalam jumlah akhir yang hasilnya sudah nol.

function r = approxroot(a,b,c)

relu = @(x)x .* (x>0);

totalprec=0;

% x4 indicates which entry of (-10:10) is a
w1 = ones(21,1);   b1 = -(-10:10)'-1;    x1 = relu(w1 * a + b1);
w2 = ones(21,1);   b2 = -(-10:10)';      x2 = relu(w2 * a + b2);
w3 = ones(21,1);   b3 = -(-10:10)'+1;    x3 = relu(w3 * a + b3);
w4p1 = ones(21,1); w4p2 = -2*ones(21,1); w4p3 = ones(21,1);
x4 = w4p1 .* x1 + w4p2 .* x2 + w4p3 .* x3;
totalprec = totalprec + prec(w1) + prec(w2) + prec(w3) + prec(b1) + prec(b2) + prec(b3) + prec(w4p1) + prec(w4p2) + prec(w4p3);

% x8 indicates which entry of (-10:10) is b
w5 = ones(21,1);   b5 = -(-10:10)'-1;    x5 = relu(w5 * b + b5);
w6 = ones(21,1);   b6 = -(-10:10)';      x6 = relu(w6 * b + b6);
w7 = ones(21,1);   b7 = -(-10:10)'+1;    x7 = relu(w7 * b + b7);
w8p1 = ones(21,1); w8p2 = -2*ones(21,1); w8p3 = ones(21,1);
x8 = w8p1 .* x5 + w8p2 .* x6 + w8p3 .* x7;
totalprec = totalprec + prec(w5) + prec(w6) + prec(w7) + prec(b5) + prec(b6) + prec(b7) + prec(w8p1) + prec(w8p2) + prec(w8p3);

% x12 indicates which entry of (-10:10) is c
w9 = ones(21,1);    b9 = -(-10:10)'-1;     x9 = relu(w9 * c + b9);
w10 = ones(21,1);   b10 = -(-10:10)';      x10 = relu(w10 * c + b10);
w11 = ones(21,1);   b11 = -(-10:10)'+1;    x11 = relu(w11 * c + b11);
w12p1 = ones(21,1); w12p2 = -2*ones(21,1); w12p3 = ones(21,1);
x12 = w12p1 .* x9 + w12p2 .* x10 + w12p3 .* x11;
totalprec = totalprec + prec(w9) + prec(w10) + prec(w11) + prec(b9) + prec(b10) + prec(b11) + prec(w12p1) + prec(w12p2) + prec(w12p3);

% x15 indicates which row of the roots file is relevant
x15=[];
for aa=-10:10
    w13 = 1;
    b13 = -2;
    x13 = w13 * x4(aa+11) + b13;
    totalprec = totalprec + prec(w13) + prec(b13);
    for bb=-10:10
        w14p1 = 1;
        w14p2 = 1;
        x14 = w14p1 * x13 + w14p2 * x8(bb+11);
        totalprec = totalprec + prec(w14p1) + prec(w14p2);
        for cc=-10:10
            w15p1 = 1;
            w15p2 = 1;
            x15(end+1,1) = relu(w15p1 * x14 + w15p2 * x12(cc+11));
            totalprec = totalprec + prec(w15p1) + prec(w15p2);
        end
    end
end

% r is the desired root, rounded to the nearest fifth
A = importdata('roots.txt');
outputs = 0.2 * round(5 * A(:,4)');
uniqueoutputs = unique(outputs);
x16 = [];
for rr = uniqueoutputs
    if rr == 0
        x16(end+1,:) = 0;
    else
        lvlset = find(outputs == rr);
        w16 = ones(1,length(lvlset));
        x16(end+1,:) = w16 * x15(lvlset);
        totalprec = totalprec + prec(w16);
    end
end
w17 = uniqueoutputs;
r = w17 * x16;
totalprec = totalprec + prec(w17);

%disp(totalprec) % uncomment to display score

end
Dustin G. Mixon
sumber