Znajdź największy pierwiastek wielomianu z siecią neuronową

11

Wyzwanie

Znajdź najmniejszą sieć neuronową ze sprzężeniem zwrotnym, taką, że biorąc pod uwagę dowolny trójwymiarowy wektor wejściowy (a,b,c) z wpisami liczb całkowitych w [10,10] , sieć wyprowadza największy (tzn. „Najbardziej pozytywny”) pierwiastek z wielomian x3+ax2+bx+c z błędem ściśle mniejszym niż 0.1 .

Dopuszczalność

Pojęcie dopuszczalności w moim poprzednim wyzwaniu polegającym na grze w sieci neuronowe wydawało się nieco restrykcyjne, dlatego w przypadku tego wyzwania wykorzystujemy bardziej liberalną definicję sprzężonej sieci neuronowej:

Neuron jest funkcją ν:RnR , który jest określony przez wektor wRn o ciężarach , A Odchylenie bR , i aktywacja funkcji f:RR w następujący sposób:

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

Sprzężona do przodu sieć neuronowa z węzłami wejściowymi {1,,n} jest funkcją (x1,,xn)Rn którą można zbudować z sekwencji (νk)k=n+1N neuronów, gdzie każdy νk:Rk1R pobiera dane wejściowe z (x1,,xk1)i generuje skalarxk . Biorąc pod uwagę określony zestawS{1,,N} zwęzłów wyjściowych, to wyjście sieci neuronowych jest wektorem(xk)kS .

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ść. f(t)=t

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

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

  • Sigmoid. f(t)=etet+1

  • Sinusoid. f(t)=sint

Ogólnie, dopuszczalna sieć neuronowa jest określona przez węzły wejściowe, sekwencję neuronów i węzły wyjściowe, podczas gdy każdy neuron jest określony przez wektor wag, obciążenie i funkcję aktywacji z powyższej listy. Na przykład dopuszczalna jest następująca sieć neuronowa, choć nie spełnia ona celu wydajności tego wyzwania:

  • Węzły wejściowe: {1,2}

  • Neurony: νk(x1,,xk1):=xk2+xk1 dla k{3,,10}

  • Węzły wyjściowe: {5,9,10}

Ta sieć składa się z 8 neuronów, z których każdy ma zerową stronniczość i aktywację tożsamości. Innymi słowy, sieć ta oblicza uogólnioną sekwencję Fibonacciego wygenerowaną przez x1 i x2 a następnie wyprowadza z tej sekwencji 5., 9. i 10. liczbę w tej kolejności.

Punktacja

Biorąc pod uwagę liczbę rzeczywistą x z końcowym rozszerzeniem dziesiętnym, niech p(x) będzie najmniejszą nieujemną liczbą całkowitą p dla której 10p|x|<1 i niech q(x) będzie najmniejszą nieujemną liczbą całkowitą q dla której 10qx jest liczbą całkowitą. Wtedy mówimy, p(x)+q(x) jest precyzja z x .

Na przykład x=1.001 ma dokładność 4 , podczas gdy x=0 ma dokładność 0 .

Twój wynik to suma dokładności wag i stronniczości w sieci neuronowej.

(Np. Powyższy przykład ma 16 punktów).

Weryfikacja

Chociaż korzenie można wyrazić za pomocą wzoru sześciennego , największy dostęp do korzenia można najłatwiej uzyskać za pomocą metod numerycznych. Zgodnie z sugestią @ xnora obliczyłem największy pierwiastek dla każdego wyboru liczb całkowitych a,b,c[10,10] , a wyniki można znaleźć tutaj . Każda linia tego pliku tekstowego ma formę a,b,c,root. Na przykład w pierwszym wierszu podano, że największy pierwiastek z x310x210x10 wynosi około 10.99247140445449 .

Edycja: oryginalny plik, który opublikowałem, zawierał błędy w przypadkach, gdy wielomian zawierał wiele elementów głównych. Obecna wersja powinna być wolna od takich błędów.

Dustin G. Mixon
źródło
3
Co dzieje się na wejściu wielomianu nie ma rzeczywistych pierwiastków, na przykład kiedy a=0i kwadrat ma dwa złożone pierwiastki?
xnor
Myślę, że najczystszym rozwiązaniem byłoby powiedzenie, że dane wejściowe będą aniezerowe, a nawet tylko 1. Zalecam też umieszczenie niektórych przypadków testowych, dając pierwiastek wysokiej precyzji, abyśmy mogli sprawdzić, czy nasze wartości mieszczą się w granicach 0,1. Dobrze byłoby mieć dane wyjściowe dla wszystkich możliwych danych wejściowych, prawdopodobnie w łączu, ponieważ to dużo dla postu.
xnor
1
Lubię nowe zasady dopuszczalności. Wygląda jednak na to, że nowa funkcja sinusoidy jest niezwykle użyteczna. Mam szkicowy dowód, że funkcja formularza x -> a * sin(b * softplus(x) + c)może zastąpić dowolną skończoną liczbę punktów danych z liczbą całkowitą xna dowolną precyzję przy użyciu bardzo dużej i precyzyjnej częstotliwości.
xnor
1
Nie jestem pewien, jak przydatny byłby (dla przyszłych wyzwań): W teorii liczb używamy funkcji wysokości do pomiaru złożoności liczby. Na przykład wysokość naiwna ułamka (zredukowanego) jest określona przez h = log max { | p | , | q | } (i jest wiele uogólnień). Być może można to wykorzystać jako alternatywny środek. p/qh=logmax{|p|,|q|}
flawr
1
@ DustinG.Mixon Nie jestem pewien, czy wiesz, ale mamy piaskownicę do publikowania szkiców i omawiania szczegółów wyzwania oraz czatu .
flawr

Odpowiedzi:

6

14 674,000,667 5 436 050 5 403 448 10 385 5 994 4447
3806 Całkowity precyzja

Dla linii bazowej zbadałem następujące podejście: Wybierz M,δ,ϵ>0 tak, że jeśli próbkujemy wielomian p(x)=x3+ax2+bx+c przy

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

wtedy największy punkt próbkowania sS spełniający p(s)<ϵ koniecznie istnieje i musi znajdować się w granicach 0.1 największego pierwiastka z p . Można pokazać, że dla naszej kolekcji wielomianów można przyjąć M=11 , δ=0.1 i ϵ=104 .

Projektowania sieci neuronowej, który realizuje to logiczne, że początek warstwie neuronów próbki wielomian na S . W odniesieniu do każdego sS bierzemy

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

Następnie możemy określić, które z nich są mniej niż ϵ=104 . Okazuje się, że dla sS utrzymuje, że p(s)<104 tylko wtedy, gdy p(s)0 . Jako takie, możemy użyć aktywacji relu, aby dokładnie zidentyfikować nasze próbki:

relu(104t)relu(t)104={1if t00if t104.

Realizujemy to za pomocą kilku warstw neuronów:

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

At this point, we have x4,s=1 when p(s)<104, and otherwise x4,s=0. Recall that we seek the largest s for which x4,s=1. To this end, we label x4,M as x5,M (for notational convenience), and for each k1, we iteratively define

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

x5,ss is the unique s for which x5,s=1. We may now identify s by another application of relu activations:

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

Explicitly, we define neurons by

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

Then x8,s=1 if s=s and otherwise x8,s=0. We linearly combine these to produce our output node:

x9=sSsx8,s=s.

For the score, each layer has neurons with different levels of precision: (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|. Furthermore, all but two of the layers have |S|=221 neurons; layer 5 has |S|1 neurons and layer 9 has 1 neuron.

Edit: Improvements: (1) We can sample the polynomial much more efficiently using finite differences. (2) We can bypass layers 2 through 4 by instead using a sigmoid activation. (3) The overflow issues in layer 5 can be averted (and subsequent layers can be combined) by more carefully applying relu activations. (4) The final sum is cheaper with summation by parts.

What follows is the MATLAB code. To be clear, prec is a function (found here) that computes the precision of a vector of weights or biases.

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
źródło
2

53,268 29,596 29,306 total precision

Private communication with @A.Rex led to this solution, in which we construct a neural net that memorizes the answers. The core idea is that every function f:SR over a finite set S enjoys the decomposition

f(x)=sSf(s){1if x=s0else}.

As such, one may construct a neural net implementation of f by first transforming the input into an indicator function of the input, and then linearly combining using the desired outputs as weights. Furthermore, relu activations make this transformation possible:

relu(t1)2relu(t)+relu(t+1)={1if t=00if tZ{0}.

What follows is a MATLAB implementation of this approach. To be clear, roots.txt is the roots file posted above (found here), and prec is a function (found here) that computes the total precision of a vector of weights or biases.

Edit 1: Two improvements over the original: (1) I factored some neurons out of the for loops. (2) I implemented "Lebesgue integration" in the final sum by first combining terms from the same level set. This way, I pay for the higher-precision value of an output only once every level set. Also, it is safe to round outputs to the nearest fifth by the rational root theorem.

Edit 2: Additional minor improvements: (1) I factored more neurons out of a for loop. (2) I don't bother computing the term in the final sum for which the output is already zero.

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
źródło