Encuentra la raíz más grande de un polinomio con una red neuronal

11

El reto

Encuentre la red neuronal feedforward más pequeña de manera que, dado cualquier vector de entrada tridimensional con entradas enteras en , la red genera la raíz más grande (es decir, "más positiva") de la raíz polinomio con error estrictamente menor que .(a,b,c)[10,10]x3+ax2+bx+c0.1

Admisibilidad

La noción de admisibilidad en mi anterior desafío de golf de red neuronal parecía un poco restrictivo, por lo que para este desafío, estamos utilizando una definición más liberal de red neuronal de alimentación directa:

Una neurona es una función que se especifica mediante un vector de pesos , un sesgo , y una función de activación de la siguiente manera:ν:RnRwRn bR f:RR

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

Una red neuronal de alimentación directa con nodos de entrada es una función de que se puede construir a partir de una secuencia de neuronas, donde cada toma entradas de y genera un escalar . Dado un conjunto específico de nodos de salida , entonces la salida de la red neuronal es el vector .{1,,n}(x1,,xn)Rn(νk)k=n+1Nνk:Rk1R(x1,,xk1)xkS{1,,N}(xk)kS

Dado que las funciones de activación pueden ajustarse para cualquier tarea dada, necesitamos restringir la clase de funciones de activación para mantener este desafío interesante. Se permiten las siguientes funciones de activación:

  • Identidad. f(t)=t

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

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

  • Sigmoideo. f(t)=etet+1

  • Sinusoide. f(t)=sint

En general, una red neuronal admisible se especifica mediante nodos de entrada, una secuencia de neuronas y nodos de salida, mientras que cada neurona se especifica mediante un vector de pesos, un sesgo y una función de activación de la lista anterior. Por ejemplo, la siguiente red neuronal es admisible, aunque no cumple con el objetivo de rendimiento de este desafío:

  • Nodos de entrada: {1,2}

  • Neuronas: paraνk(x1,,xk1):=xk2+xk1k{3,,10}

  • Nodos de salida: {5,9,10}

Esta red consta de 8 neuronas, cada una con sesgo cero y activación de identidad. En palabras, esta red calcula la secuencia generalizada de Fibonacci generada por y y luego genera los números 5, 9 y 10 de esta secuencia, en ese orden.x1x2

Puntuación

Dado un número real con terminación de expansión decimal, sea el número entero no negativo más pequeño para el cual , y sea el número entero no negativo más pequeño para cuál es entero. Entonces decimos que es la precisión de .xp(x)p10p|x|<1q(x)q10qxp(x)+q(x)xx

Por ejemplo, tiene una precisión de , mientras que tiene una precisión de .x=1.0014x=00

Su puntaje es la suma de las precisiones de los pesos y sesgos en su red neuronal.

(Por ejemplo, el ejemplo anterior tiene una puntuación de 16).

Verificación

Si bien las raíces se pueden expresar en términos de la fórmula cúbica , la raíz más grande es quizás más fácilmente accesible por medios numéricos. Siguiendo la sugerencia de @ xnor, calculé la raíz más grande para cada elección de enteros , y los resultados se pueden encontrar aquí . Cada línea de este archivo de texto tiene la forma . Por ejemplo, la primera línea informa que la raíz más grande de es aproximadamente .a,b,c[10,10]x 3 - 10 x 2 - 10 x - 10 10.99247140445449a,b,c,rootx310x210x1010.99247140445449

Editar: el archivo original que publiqué tenía errores en los casos en que el polinomio exhibía una raíz múltiple. La versión actual debe estar libre de tales errores.

Dustin G. Mixon
fuente
3
¿Qué sucede en el polinomio de entrada que no tiene raíces reales, como cuándo a=0y el cuadrático tiene dos raíces complejas?
xnor
Creo que la solución más limpia sería decir que la entrada tendrá aun valor distinto de cero, o incluso solo 1. Además, recomendaría poner algunos casos de prueba, dando raíces a una alta precisión para que podamos verificar que los nuestros estén dentro de 0.1. También sería bueno tener salidas para todas las entradas posibles, probablemente en un enlace, ya que eso es mucho para la publicación.
xnor
1
Me gustan las nuevas reglas de admisibilidad. Sin embargo, parece que la nueva función sinusoide es extremadamente explotable. Tengo una prueba incompleta de que una función del formulario x -> a * sin(b * softplus(x) + c)puede sobreajustar cualquier número finito de puntos de datos con xuna precisión de entero a arbitraria utilizando una frecuencia extremadamente grande y precisa.
xnor
1
No estoy seguro de cuán útil sería (para desafíos futuros): en la teoría de números usamos funciones de altura para medir la complejidad de un número. Por ejemplo, la altura ingenua de una fracción (reducida) viene dada por (y hay muchas generalizaciones). Tal vez esto podría usarse como una medida alternativa. h = log max { | p | , | q | }p/qh=logmax{|p|,|q|}
defecto
1
@ DustinG.Mixon No estoy seguro si está al tanto, pero tenemos una caja de arena para publicar borradores y discutir detalles de un desafío, así como un chat .
defecto

Respuestas:

6

14674000667 5.436.050 5.403.448 10.385 5.994 4.447
3.806 total precisión

Para una línea de base, investigué el siguiente enfoque: Seleccione modo que si tomamos muestras del polinomio enM,δ,ϵ>0p(x)=x3+ax2+bx+c

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

entonces el punto de muestra más grande satisface necesariamente existe y reside necesariamente dentro de de la raíz más grande de . Se puede demostrar que para nuestra colección de polinomios, se puede tomar , y .sSp(s)<ϵ0.1pM=11δ=0.1ϵ=104

Diseñar una red neuronal que implementa esta lógica, que comienzan con una capa de neuronas que muestra el polinomio de . Para cada , tomamosSsS

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

A continuación, identificamos cuáles de estos son menores que . Resulta que para , mantiene que solo si . Como tal, podemos usar activaciones relu para identificar exactamente nuestras muestras:ϵ=104sSp(s)<104p(s)0

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

Implementamos esto con unas pocas capas de neuronas:

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

En este punto, tenemos cuando , y de lo contrario . Recuerde que buscamos la más grande para la cual . Para este fin, etiquetamos como (por conveniencia de notación), y para cada , definimos iterativamentex4,s=1p(s)<104x4,s=0sx4,s=1x4,Mx5,Mk1

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

Gracias a esta transformación, cada es un número entero no negativo, y es la única para la cual . Ahora podemos identificar por otra aplicación de activaciones relu:x5,sssx5,s=1s

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

Explícitamente, definimos las neuronas por

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

Entonces si y de lo contrario . Los combinamos linealmente para producir nuestro nodo de salida:x8,s=1s=sx8,s=0

x9=sSsx8,s=s.

Para la puntuación, cada capa tiene neuronas con diferentes niveles de precisión: (1) , (2) , (3) , (4) , (5) , (6) , (7) , (8) , (9). Además, todas menos dos de las capas tienen neuronas; la capa 5 tiene neuronas y la capa 9 tiene neurona.6+3+1+9=191+4=515+5=101+1=21+1=21+1=21+1+1=33|S||S|=221|S|11

Editar: Mejoras: (1) Podemos muestrear el polinomio de manera mucho más eficiente usando diferencias finitas. (2) Podemos pasar por alto las capas 2 a 4 usando una activación sigmoidea. (3) Los problemas de desbordamiento en la capa 5 se pueden evitar (y las capas posteriores se pueden combinar) aplicando más cuidadosamente las activaciones de relu. (4) La suma final es más barata con la suma por partes .

Lo que sigue es el código MATLAB. Para ser claros, preces una función (que se encuentra aquí ) que calcula la precisión de un vector de pesos o sesgos.

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
fuente
2

53.268 29.596 29.306 total precisión

La comunicación privada con @ A.Rex condujo a esta solución, en la que construimos una red neuronal que memoriza las respuestas. La idea central es que cada función sobre un conjunto finito disfruta de la descomposiciónf:SRS

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

Como tal, se puede construir una implementación de red neural de transformando primero la entrada en una función indicadora de la entrada, y luego combinándola linealmente usando las salidas deseadas como pesos. Además, las activaciones de relu hacen posible esta transformación:f

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

Lo que sigue es una implementación de MATLAB de este enfoque. Para ser claros, roots.txtes el archivo raíz publicado anteriormente (que se encuentra aquí ), y preces una función (que se encuentra aquí ) que calcula la precisión total de un vector de pesos o sesgos.

Edición 1: Dos mejoras sobre el original: (1) Factoré algunas neuronas fuera de los bucles for. (2) Implementé la " integración de Lebesgue " en la suma final combinando primero los términos del mismo conjunto de niveles. De esta manera, pago el valor de mayor precisión de una salida solo una vez cada nivel establecido. Además, es seguro redondear las salidas al quinto más cercano mediante el teorema de la raíz racional .

Edición 2: Mejoras menores adicionales: (1) Factoré más neuronas a partir de un bucle for. (2) No me molesto en calcular el término en la suma final para la cual el resultado ya es cero.

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
fuente