Finden Sie die größte Wurzel eines Polynoms mit einem neuronalen Netzwerk

Die Herausforderung

Finden Sie das kleinste neuronale Feedforward-Netzwerk so, dass das Netzwerk bei einem beliebigen dreidimensionalen Eingabevektor mit ganzzahligen Einträgen in die größte (dh "positivste") Wurzel der ausgibt Polynom mit einem Fehler, der streng kleiner als . $(a,b,c)$ $[-10,10]$ $x^3+ax^2+bx+c$ $0.1$

Zulässigkeit

Der Begriff der Zulässigkeit in meiner vorherigen Herausforderung zum Golfspielen mit neuronalen Netzen schien etwas restriktiv zu sein. Daher verwenden wir für diese Herausforderung eine liberalere Definition des neuronalen Feedforward-Netzwerks:

Ein Neuron ist eine Funktion , die durch einen Vektor von Gewichten , eine Vorspannung und eine Aktivierungsfunktion auf folgende Weise: $\nu\colon\mathbf{R}^n\to\mathbf{R}$ $w\in\mathbf{R}^{n}$ $b\in\mathbf{R}$ $f\colon\mathbf{R}\to\mathbf{R}$

ν (x) := f (w^{⊤} x + b), x \in R^{n} .

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

Ein vorwärts gerichtetes neuronales Netzwerk mit Eingangsknoten ist eine Funktion von , die aus einer Sequenz von Neuronen, wobei jedes Eingaben von und gibt einen Skalar . Bei einer bestimmten Menge von Ausgabeknoten ist die Ausgabe des neuronalen Netzwerks der Vektor . $\{1,\ldots,n\}$ $(x_1,\ldots,x_n)\in\mathbf{R}^n$ $(\nu_k)_{k=n+1}^N$ $\nu_k\colon\mathbf{R}^{k-1}\to\mathbf{R}$ $(x_1,\ldots,x_{k-1})$ $x_k$ $S\subseteq\{1,\ldots,N\}$ $(x_k)_{k\in S}$

Da Aktivierungsfunktionen für eine bestimmte Aufgabe optimiert werden können, müssen wir die Klasse der Aktivierungsfunktionen einschränken, um diese Herausforderung interessant zu halten. Folgende Aktivierungsfunktionen sind zulässig:

Identität. $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}$
Sinus. $f(t)=\sin t$

Insgesamt wird ein zulässiges neuronales Netz durch Eingangsknoten, eine Folge von Neuronen und Ausgangsknoten spezifiziert, während jedes Neuron durch einen Vektor von Gewichten, eine Vorspannung und eine Aktivierungsfunktion aus der obigen Liste spezifiziert wird. Beispielsweise ist das folgende neuronale Netz zulässig, obwohl es das Leistungsziel dieser Herausforderung nicht erfüllt:

Eingabeknoten: $\{1,2\}$
Neuronen: für $\nu_k(x_1,\ldots,x_{k-1}):=x_{k-2}+x_{k-1}$ $k\in\{3,\ldots,10\}$
: $\{5,9,10\}$

Dieses Netzwerk besteht aus 8 Neuronen mit jeweils null Bias und Identitätsaktivierung. Mit anderen Worten, dieses Netzwerk berechnet die von und erzeugte verallgemeinerte Fibonacci-Sequenz und gibt dann die 5., 9. und 10. Zahl aus dieser Sequenz in dieser Reihenfolge aus. $x_1$ $x_2$

Wertung

Bei einer reellen Zahl mit endender Dezimalerweiterung sei die kleinste nichtnegative ganze Zahl für die , und sei die kleinste nichtnegative ganze Zahl für welche ist eine ganze Zahl. Dann sagen wir, dass die Genauigkeit von . $x$ $p(x)$ $p$ $10^{-p}\cdot |x|<1$ $q(x)$ $q$ $10^q \cdot x$ $p(x)+q(x)$ $x$

Zum Beispiel hat eine Genauigkeit von , während eine Genauigkeit von . $x=1.001$ $4$ $x=0$ $0$

Ihre Punktzahl ist die Summe der Präzisionen der Gewichte und Verzerrungen in Ihrem neuronalen Netzwerk.

(ZB hat das obige Beispiel eine Punktzahl von 16.)

Nachprüfung

Während die Wurzeln in Form der kubischen Formel ausgedrückt werden können , ist die größte Wurzel möglicherweise am einfachsten mit numerischen Mitteln zugänglich. Nach @ Vorschlag des xnor, berechnet ich die größte Wurzel für jede Wahl der ganzen Zahlen , und die Ergebnisse können hier gefunden werden . Jede Zeile dieser Textdatei hat die Form . In der ersten Zeile wird beispielsweise angegeben, dass die größte Wurzel von ungefähr . $a,b,c\in[-10,10]$ a,b,c,root $x^3-10x^2-10x-10$ $10.99247140445449$

Bearbeiten: Die Originaldatei, die ich gepostet habe, hatte Fehler in Fällen, in denen das Polynom eine Mehrfachwurzel aufwies. Die aktuelle Version sollte frei von solchen Fehlern sein.

code-challenge optimization polynomials neural-networks Dustin G. Mixon
quelle

Was passiert, wenn das Eingabepolynom keine reellen Wurzeln hat, wie wenn a=0und das Quadrat zwei komplexe Wurzeln hat?

xnor

Ich denke, die sauberste Lösung wäre zu sagen, dass die Eingabe aungleich Null oder sogar nur 1 sein wird. Außerdem würde ich empfehlen, einige Testfälle einzufügen und die Wurzeln mit hoher Präzision zu versehen, damit wir überprüfen können, ob unsere innerhalb von 0,1 liegen. Es wäre auch gut, Ausgaben für alle möglichen Eingaben zu haben, wahrscheinlich in einem Link, da dies viel für den Beitrag ist.

xnor

Ich mag die neuen Zulässigkeitsregeln. Es sieht jedoch so aus, als ob die neue Sinusfunktion äußerst ausnutzbar ist. Ich habe einen skizzenhaften Beweis dafür, dass eine Funktion des Formulars x -> a * sin(b * softplus(x) + c)eine endliche Anzahl von Datenpunkten mit einer Ganzzahl xmit beliebiger Genauigkeit und einer extrem großen und präzisen Frequenz überanpassen kann .

xnor

Ich bin mir nicht sicher, wie nützlich es wäre (für zukünftige Herausforderungen): In der Zahlentheorie verwenden wir Höhenfunktionen , um die Komplexität einer Zahl zu messen. Zum Beispiel ist die naive Höhe eines (reduzierten) Bruchteils gegeben durch (und es gibt viele Verallgemeinerungen). Vielleicht könnte dies als alternative Maßnahme verwendet werden.

p / q

$p/q$

h = \log max {| p |, | q |}

$h=\log\max\{|p|,|q|\}$

Fehler

@ DustinG.Mixon Ich bin mir nicht sicher, ob Sie es wissen, aber wir haben eine Sandbox , in der Sie Entwürfe veröffentlichen und Details einer Herausforderung sowie einen Chat diskutieren können .

Fehler

Antworten:

14.674.000.667 5.436.050 5.403.448 10.385 5.994 4.447
3.806 Gesamtpräzision

Für eine Basislinie habe ich den folgenden Ansatz untersucht: Wählen Sie so dass, wenn wir das Polynom bei $M,\delta,\epsilon>0$ $p(x)=x^3+ax^2+bx+c$

S := {- M, - M + δ, - M + 2 δ, \dots, M},

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

dann existiert notwendigerweise der größte Abtastpunkt , der erfüllt , und liegt notwendigerweise innerhalb von der größten Wurzel von . Man kann zeigen, dass man für unsere Sammlung von Polynomen , und . $s^\star\in S$ $p(s^\star)<\epsilon$ $0.1$ $p$ $M=11$ $\delta=0.1$ $\epsilon=10^{-4}$

Um ein neuronales Netz zu entwerfen, das diese Logik implementiert, beginnen wir mit einer Schicht von Neuronen, die das Polynom auf . Für jedes nehmen wir $S$ $s\in S$

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

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

Als nächstes identifizieren wir, welche davon kleiner als . Es stellt sich heraus , dass für , ist es das gilt nur dann , wenn . Daher können wir Relu-Aktivierungen verwenden, um unsere Proben genau zu identifizieren: $\epsilon=10^{-4}$ $s\in S$ $p(s)<10^{-4}$ $p(s)\leq 0$

\frac{r e l u (10^{- 4} - t) - r e l u (- t)}{10^{- 4}} = {\begin{array}{cl} 1 & if t \leq 0 \\ 0 & if t \geq 10^{- 4} . \end{array}

$\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.$

Wir implementieren dies mit einigen Schichten von Neuronen:

\begin{aligned} x_{2, s} & = r e l u (- 1 \cdot x_{1, s} + 10^{- 4}), \\ x_{3, s} & = r e l u (- 1 \cdot x_{1, s}), \\ x_{4, s} & = 10^{4} \cdot x_{2, s} - 10^{4} \cdot x_{3, s} . \end{aligned}

$\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}$

Zu diesem Zeitpunkt haben wir wenn , und ansonsten ist . Denken Sie daran, dass wir den größten suchen, für den . Zu diesem Zweck bezeichnen wir als (zur Vereinfachung der Notation) und definieren für jedes iterativ $x_{4,s}=1$ $p(s)<10^{-4}$ $x_{4,s}=0$ $s^\star$ $x_{4,s^\star}=1$ $x_{4,M}$ $x_{5,M}$ $k\geq 1$

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

$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}.$

Dank dieser Transformation ist jedes eine nichtnegative ganze Zahl, und ist das eindeutige für das . Wir können nun durch eine andere Anwendung von Relu-Aktivierungen identifizieren: $x_{5,s}$ $s^\star$ $s$ $x_{5,s}=1$ $s^\star$

r e l u (t - 2) - 2 \cdot r e l u (t - 1) + t = {\begin{array}{cl} 1 & if t = 1 \\ 0 & if t \in Z_{\geq 0} ∖ {1} . \end{array}

$\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.$

Explizit definieren wir Neuronen durch

\begin{aligned} x_{6, s} & = r e l u (1 \cdot x_{5, s} - 2), \\ x_{7, s} & = r e l u (1 \cdot x_{5, s} - 1), \\ x_{8, s} & = 1 \cdot x_{6, s} - 2 \cdot x_{7, s} + 1 \cdot x_{5 s} . \end{aligned}

$\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}$

Dann ist wenn und ansonsten . Wir kombinieren diese linear, um unseren Ausgabeknoten zu erzeugen: $x_{8,s}=1$ $s=s^\star$ $x_{8,s}=0$

x_{9} = \sum_{s \in S} s \cdot x_{8, s} = s^{⋆} .

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

Für die Bewertung hat jede Schicht Neuronen mit unterschiedlichen Genauigkeitsstufen: (1) , (2) , (3) , (4) , (5) , (6) , (7) , (8) , (9). Darüber hinaus haben alle bis auf zwei Schichten Neuronen; Schicht 5 hat Neuronen und Schicht 9 hat Neuron. $6+3+1+9=19$ $1+4=5$ $1$ $5+5=10$ $1+1=2$ $1+1=2$ $1+1=2$ $1+1+1=3$ $3|S|$ $|S|=221$ $|S|-1$ $1$

Bearbeiten: Verbesserungen: (1) Wir können das Polynom mit endlichen Differenzen viel effizienter abtasten. (2) Wir können die Schichten 2 bis 4 umgehen, indem wir stattdessen eine Sigmoid-Aktivierung verwenden. (3) Die Überlaufprobleme in Schicht 5 können durch sorgfältigeres Anwenden von Relu-Aktivierungen abgewendet werden (und nachfolgende Schichten können kombiniert werden). (4) die Endsumme ist billiger mit Summierung von Teilen .

Was folgt, ist der MATLAB-Code. Um klar zu sein, precist eine Funktion ( hier zu finden ), die die Genauigkeit eines Vektors von Gewichten oder Verzerrungen berechnet.

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
quelle

53.268 29.596 29.306 Gesamtpräzision

Die private Kommunikation mit @ A.Rex führte zu dieser Lösung, bei der wir ein neuronales Netz aufbauen, das die Antworten speichert. Die Kernidee ist, dass jede Funktion über eine endliche Menge die Zerlegung genießt $f\colon S\to\mathbf{R}$ $S$

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

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

Als solches kann man eine neuronale Netzimplementierung von konstruieren, indem man zuerst die Eingabe in eine Indikatorfunktion der Eingabe umwandelt und dann unter Verwendung der gewünschten Ausgaben als Gewichte linear kombiniert. Darüber hinaus ermöglichen Relu-Aktivierungen diese Transformation: $f$

r e l u (t - 1) - 2 \cdot r e l u (t) + r e l u (t + 1) = {\begin{array}{cl} 1 & if t = 0 \\ 0 & if t \in Z ∖ {0} . \end{array}

$\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.$

Was folgt, ist eine MATLAB-Implementierung dieses Ansatzes. Um es klar auszudrücken, roots.txthandelt es sich um die oben veröffentlichte Root-Datei ( hier zu finden ) und precum eine Funktion ( hier zu finden ), die die Gesamtgenauigkeit eines Vektors von Gewichten oder Verzerrungen berechnet.

Edit 1: Zwei Verbesserungen gegenüber dem Original: (1) Ich habe einige Neuronen aus den for-Schleifen herausgerechnet. (2) Ich habe " Lebesgue-Integration " in der Endsumme implementiert, indem ich zuerst Begriffe aus derselben Ebene kombiniert habe. Auf diese Weise bezahle ich für den höherpräzisen Wert eines Ausgangs nur einmal pro eingestellter Stufe. Es ist auch sicher, Ausgaben durch den rationalen Wurzelsatz auf das nächste Fünftel zu runden .

Edit 2: Zusätzliche kleinere Verbesserungen: (1) Ich habe mehr Neuronen aus einer for-Schleife herausgerechnet. (2) Ich mache mir nicht die Mühe, den Term in der endgültigen Summe zu berechnen, für die die Ausgabe bereits Null ist.

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
quelle

Finden Sie die größte Wurzel eines Polynoms mit einem neuronalen Netzwerk

Die Herausforderung

Zulässigkeit

Wertung

Nachprüfung

Antworten:

14.674.000.667 5.436.050 5.403.448 10.385 5.994 4.447 3.806 Gesamtpräzision

53.268 29.596 29.306 Gesamtpräzision

14.674.000.667 5.436.050 5.403.448 10.385 5.994 4.447
3.806 Gesamtpräzision