Trouver la plus grande racine d'un polynôme avec un réseau neuronal

Le défi

Trouver le plus petit réseau neuronal à action directe de telle sorte que, étant donné tout vecteur d'entrée en trois dimensions $(a,b,c)$ avec des entrées entières dans $[-10,10]$ , le réseau génère la racine la plus grande (c'est-à-dire "la plus positive") de polynôme $x^3+ax^2+bx+c$ avec une erreur strictement inférieure à $0.1$ .

Admissibilité

La notion d'admissibilité dans mon précédent défi de golf de réseau neuronal semblait un peu restrictive, donc pour ce défi, nous utilisons une définition plus libérale du réseau neuronal à action directe:

Un neurone est une fonction $\nu\colon\mathbf{R}^n\to\mathbf{R}$ qui est spécifiée par un vecteur $w\in\mathbf{R}^{n}$ de poids , un biais $b\in\mathbf{R}$ et une fonction d'activation $f\colon\mathbf{R}\to\mathbf{R}$ de la manière suivante:

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

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

Un réseau neuronal à action directe avec des nœuds d'entrée $\{1,\ldots,n\}$ est fonction de $(x_1,\ldots,x_n)\in\mathbf{R}^n$ qui peut être construit à partir d'une séquence $(\nu_k)_{k=n+1}^N$ de neurones, où chaque $\nu_k\colon\mathbf{R}^{k-1}\to\mathbf{R}$ prend les entrées de $(x_1,\ldots,x_{k-1})$ et produit un scalaire $x_k$ . Compte tenucertains ensemble spécifié $S\subseteq\{1,\ldots,N\}$ denoeuds de sortie, la sortie du réseauneurones est le vecteur $(x_k)_{k\in S}$ .

Étant donné que les fonctions d'activation peuvent être réglées pour une tâche donnée, nous devons restreindre la classe des fonctions d'activation pour garder ce défi intéressant. Les fonctions d'activation suivantes sont autorisées:

Identité. $f(t)=t$
ReLU. $f(t)=\operatorname{max}(t,0)$
SoftPlus. $f(t)=\ln(e^t+1)$
Sigmoïde. $f(t)=\frac{e^t}{e^t+1}$
Sinusoïde. $f(t)=\sin t$

Dans l'ensemble, un réseau neuronal admissible est spécifié par des nœuds d'entrée, une séquence de neurones et des nœuds de sortie, tandis que chaque neurone est spécifié par un vecteur de poids, un biais et une fonction d'activation de la liste ci-dessus. Par exemple, le réseau neuronal suivant est admissible, bien qu'il n'atteigne pas l'objectif de performance de ce défi:

Noeuds d'entrée: $\{1,2\}$
Neurones: $\nu_k(x_1,\ldots,x_{k-1}):=x_{k-2}+x_{k-1}$ pour $k\in\{3,\ldots,10\}$
Noeuds de sortie: $\{5,9,10\}$

Ce réseau se compose de 8 neurones, chacun avec un biais nul et une activation d'identité. En termes, ce réseau calcule la séquence de Fibonacci généralisée générée par $x_1$ et $x_2$ , puis émet les 5e, 9e et 10e nombres de cette séquence, dans cet ordre.

Notation

Étant donné un nombre réel $x$ avec une expansion décimale terminale, soit $p(x)$ le plus petit entier non négatif $p$ pour lequel $10^{-p}\cdot |x|<1$ , et que $q(x)$ soit le plus petit entier non négatif $q$ pour lequel $10^q \cdot x$ est entier. Ensuite, nous disons que $p(x)+q(x)$ est la précision de $x$ .

Par exemple, $x=1.001$ a une précision de $4$ , tandis que $x=0$ a une précision de $0$ .

Votre score est la somme des précisions des poids et des biais dans votre réseau neuronal.

(Par exemple, l'exemple ci-dessus a un score de 16.)

Vérification

Alors que les racines peuvent être exprimées en termes de formule cubique , la plus grande racine est peut-être la plus facilement accessible par des moyens numériques. Suivant la suggestion de @ xnor, j'ai calculé la racine la plus grande pour chaque choix d'entiers $a,b,c\in[-10,10]$ , et les résultats peuvent être trouvés ici . Chaque ligne de ce fichier texte est de la forme a,b,c,root. Par exemple, la première ligne indique que la racine la plus grande de $x^3-10x^2-10x-10$ est environ $10.99247140445449$ .

Edit: le fichier d'origine que j'ai publié comportait des erreurs dans les cas où le polynôme présentait une racine multiple. La version actuelle devrait être exempte de telles erreurs.

code-challenge optimization polynomials neural-networks Dustin G. Mixon
la source

Que se passe-t-il dans le polynôme d'entrée n'a pas de racines réelles, comme quand a=0et le quadratique a deux racines complexes?

xnor

Je pense que la solution la plus propre serait de dire que l'entrée sera anon nulle, ou même juste 1. De plus, je recommanderais de mettre dans certains cas de test, en donnant les racines à une haute précision afin que nous puissions vérifier que les nôtres sont à 0,1. Il serait également bon d'avoir des sorties pour toutes les entrées possibles, probablement dans un lien, car c'est beaucoup pour la publication.

xnor

J'aime les nouvelles règles de recevabilité. Il semble que la nouvelle fonction sinusoïdale soit extrêmement exploitable. J'ai une preuve sommaire qu'une fonction de la forme x -> a * sin(b * softplus(x) + c)peut surcharger n'importe quel nombre fini de points de données avec un entier xà une précision arbitraire en utilisant une fréquence extrêmement grande et précise.

xnor

Je ne sais pas à quel point cela serait utile (pour les défis futurs): dans la théorie des nombres, nous utilisons des fonctions de hauteur pour mesurer la complexité d'un nombre. Par exemple, la hauteur naïve d'une fraction (réduite)

est donnée par

(et il y a beaucoup de généralisations). Peut-être que cela pourrait être utilisé comme mesure alternative.

p / q

$p/q$

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

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

flawr

@ DustinG.Mixon Je ne sais pas si vous êtes au courant, mais nous avons un bac à sable pour publier des brouillons et discuter des détails d'un défi ainsi que d'un chat .

flawr

Réponses:

14674000667 5436050 5403448 10385 5994 4447
3806 précision totale

Pour une ligne de base, j'ai étudié l'approche suivante: Sélectionnez $M,\delta,\epsilon>0$ telle sorte que si nous échantillonnons le polynôme $p(x)=x^3+ax^2+bx+c$ à

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

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

alors le plus grand point d'échantillon $s^\star\in S$ satisfaisant $p(s^\star)<\epsilon$ existe nécessairement et réside nécessairement à $0.1$ de la plus grande racine de $p$ . On peut montrer que pour notre collection de polynômes, on peut prendre $M=11$ , $\delta=0.1$ et $\epsilon=10^{-4}$ .

Pour concevoir un réseau de neurones qui implémente cette logique, nous commençons par une couche de neurones que l' échantillon polynôme sur $S$ . Pour chaque $s\in S$ , on prend

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

Ensuite, nous identifions ceux qui sont inférieurs à $\epsilon=10^{-4}$ . Il s'avère que pour $s\in S$ , il considère que $p(s)<10^{-4}$ uniquement si $p(s)\leq 0$ . À ce titre, nous pouvons utiliser les activations relu pour identifier exactement nos échantillons:

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

Nous l'implémentons avec quelques couches de neurones:

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

À ce stade, nous avons $x_{4,s}=1$ lorsque $p(s)<10^{-4}$ , et sinon $x_{4,s}=0$ . Rappelons que l'on cherche le plus grand $s^\star$ pour lequel $x_{4,s^\star}=1$ . À cette fin, nous étiquetons $x_{4,M}$ comme $x_{5,M}$ (pour la commodité de la notation), et pour chaque $k\geq 1$ , nous définissons itérativement

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

Grâce à cette transformation, chaque $x_{5,s}$ est un entier non négatif, et $s^\star$ est l'unique $s$ pour lequel $x_{5,s}=1$ . On peut maintenant identifier $s^\star$ par une autre application d'activations relu:

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

De manière explicite, nous définissons les neurones par

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

Alors $x_{8,s}=1$ si $s=s^\star$ et sinon $x_{8,s}=0$ . Nous les combinons linéairement pour produire notre nœud de sortie:

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

Pour le score, chaque couche a des neurones avec différents niveaux de précision: (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|$ . De plus, toutes les couches sauf deux ont $|S|=221$ neurones; la couche 5 a $|S|-1$ neurone et la couche 9 a $1$ neurone.

Edit: Améliorations: (1) Nous pouvons échantillonner le polynôme beaucoup plus efficacement en utilisant des différences finies. (2) Nous pouvons contourner les couches 2 à 4 en utilisant plutôt une activation sigmoïde. (3) Les problèmes de débordement dans la couche 5 peuvent être évités (et les couches suivantes peuvent être combinées) en appliquant plus soigneusement les activations de relu. (4) La somme finale est moins chère avec addition par parties .

Ce qui suit est le code MATLAB. Pour être clair, precest une fonction (trouvée ici ) qui calcule la précision d'un vecteur de poids ou de biais.

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
la source

53268 29596 29306 précision totale

Une communication privée avec @ A.Rex a conduit à cette solution, dans laquelle nous construisons un réseau neuronal qui mémorise les réponses. L'idée centrale est que chaque fonction $f\colon S\to\mathbf{R}$ sur un ensemble fini $S$ bénéficie de la décomposition

F (X) = \sum_{s \in S} F (s) \cdot {\begin{array}{cl} 1 & si X = s \\ 0 & autre \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\}.$

$f$

r e l u (t - 1) - 2 \cdot r e l u (t) + r e l u (t + 1) = {\begin{array}{cl} 1 & si t = 0 \\ 0 & si 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.$

Ce qui suit est une implémentation MATLAB de cette approche. Pour être clair, roots.txtest le fichier racine affiché ci-dessus (trouvé ici ), et precest une fonction (trouvée ici ) qui calcule la précision totale d'un vecteur de poids ou de biais.

Edit 1: Deux améliorations par rapport à l'original: (1) J'ai factorisé certains neurones des boucles for. (2) J'ai implémenté «l' intégration de Lebesgue » dans la somme finale en combinant d'abord les termes du même ensemble de niveaux. De cette façon, je ne paie pour la valeur de précision supérieure d'une sortie qu'une seule fois à chaque niveau défini. En outre, il est sûr d'arrondir les sorties au cinquième près par le théorème de la racine rationnelle .

Edit 2: améliorations mineures supplémentaires: (1) J'ai factorisé plus de neurones d'une boucle for. (2) Je ne me donne pas la peine de calculer le terme dans la somme finale pour laquelle la sortie est déjà nulle.

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
la source

Trouver la plus grande racine d'un polynôme avec un réseau neuronal

Le défi

Admissibilité

Notation

Vérification

Réponses:

14674000667 5436050 5403448 10385 5994 4447 3806 précision totale

53268 29596 29306 précision totale

14674000667 5436050 5403448 10385 5994 4447
3806 précision totale