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 $x^3+ax^2+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ą $\nu\colon\mathbf{R}^n\to\mathbf{R}$ , który jest określony przez wektor $w\in\mathbf{R}^{n}$ o ciężarach , A Odchylenie $b\in\mathbf{R}$ , i aktywacja funkcji $f\colon\mathbf{R}\to\mathbf{R}$ w następujący sposób:

$$\nu(x) := f(w^\top x+b), \qquad x\in\mathbf{R}^n.$$

Sprzężona do przodu sieć neuronowa z węzłami wejściowymi $\{1,\ldots,n\}$ jest funkcją $(x_1,\ldots,x_n)\in\mathbf{R}^n$ którą można zbudować z sekwencji $(\nu_k)_{k=n+1}^N$ neuronów, gdzie każdy $\nu_k\colon\mathbf{R}^{k-1}\to\mathbf{R}$ pobiera dane wejściowe z $(x_1,\ldots,x_{k-1})$i generuje skalar$x_k$ . Biorąc pod uwagę określony zestaw$S\subseteq\{1,\ldots,N\}$ zwęzłów wyjściowych, to wyjście sieci neuronowych jest wektorem$(x_k)_{k\in S}$ .

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)=\operatorname{max}(t,0)$

• SoftPlus. $f(t)=\ln(e^t+1)$

• Sigmoid. $f(t)=\frac{e^t}{e^t+1}$

• Sinusoid. $f(t)=\sin t$

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: $\nu_k(x_1,\ldots,x_{k-1}):=x_{k-2}+x_{k-1}$ dla $k\in\{3,\ldots,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 $x_1$ i $x_2$ 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 $10^{-p}\cdot |x|<1$ i niech $q(x)$ będzie najmniejszą nieujemną liczbą całkowitą $q$ dla której $10^q \cdot x$ 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\in[-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 $x^3-10x^2-10x-10$ 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.

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,\delta,\epsilon>0$ tak, że jeśli próbkujemy wielomian $p(x)=x^3+ax^2+bx+c$ przy

$$S:=\{-M,-M+\delta,-M+2\delta,\ldots,M\},$$

wtedy największy punkt próbkowania $s^\star\in S$ spełniający $p(s^\star)<\epsilon$ 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$ , $\delta=0.1$ i $\epsilon=10^{-4}$ .

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

$$x_{1,s} = s^2\cdot a + s\cdot b + 1\cdot c + s^3.$$

Następnie możemy określić, które z nich są mniej niż $\epsilon=10^{-4}$ . Okazuje się, że dla $s\in S$ utrzymuje, że $p(s)<10^{-4}$ tylko wtedy, gdy $p(s)\leq 0$ . Jako takie, możemy użyć aktywacji relu, aby dokładnie zidentyfikować nasze próbki:

$$\frac{\mathrm{relu}(10^{-4}-t) - \mathrm{relu}(-t)}{10^{-4}} = \left\{\begin{array}{cl}1&\text{if }t\leq 0\\0&\text{if }t\geq 10^{-4}.\end{array}\right.$$

Realizujemy to za pomocą kilku warstw neuronów:

$$\begin{aligned} x_{2,s} &= \mathrm{relu}(-1\cdot x_{1,s}+10^{-4}), \\ x_{3,s} & = \mathrm{relu}(-1\cdot x_{1,s}), \\ x_{4,s} &= 10^{4}\cdot x_{2,s}-10^{4}\cdot x_{3,s}. \end{aligned}$$

At this point, we have $x_{4,s}=1$ when $p(s)<10^{-4}$, and otherwise $x_{4,s}=0$. Recall that we seek the largest $s^\star$ for which $x_{4,s^\star}=1$. To this end, we label $x_{4,M}$ as $x_{5,M}$ (for notational convenience), and for each $k\geq 1$, we iteratively define

$$x_{5,M-k\delta} = 1\cdot x_{4,M-k\delta}+2\cdot x_{5,M-(k-1)\delta} = \sum_{j=0}^k 2^{k-j}x_{4,M-j\delta}.$$

$x_{5,s}$$s^\star$ is the unique $s$ for which $x_{5,s}=1$. We may now identify $s^\star$ by another application of relu activations:

$$\mathrm{relu}(t-2)-2\cdot\mathrm{relu}(t-1)+t = \left\{\begin{array}{cl}1&\text{if }t=1\\0&\text{if }t\in\mathbf{Z}_{\geq 0}\setminus\{1\}.\end{array}\right.$$

Explicitly, we define neurons by

$$\begin{aligned} x_{6,s} &= \mathrm{relu}(1\cdot x_{5,s} - 2), \\ x_{7,s} &= \mathrm{relu}(1\cdot x_{5,s} - 1), \\ x_{8,s} &= 1\cdot x_{6,s} - 2\cdot x_{7,s} + 1\cdot x_{5s}. \end{aligned}$$

Then $x_{8,s}=1$ if $s=s^\star$ and otherwise $x_{8,s}=0$. We linearly combine these to produce our output node:

$$x_9 = \sum_{s\in S} s\cdot x_{8,s} = s^\star.$$

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

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\colon S\to\mathbf{R}$ over a finite set $S$ enjoys the decomposition

$$f(x) = \sum_{s\in S}f(s)\cdot \left\{\begin{array}{cl}1&\text{if }x=s\\0&\text{else}\end{array}\right\}.$$

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:

$$\mathrm{relu}(t-1)-2\cdot\mathrm{relu}(t)+\mathrm{relu}(t+1) = \left\{\begin{array}{cl}1&\text{if } t=0\\0&\text{if }t\in\mathbf{Z}\setminus\{0\}.\end{array}\right.$$

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