Encontre a maior raiz de um polinômio com uma rede neural

11

O desafio

Encontre a menor rede neural de avanço de forma que, dado qualquer vetor de entrada tridimensional com entradas inteiras em , a rede produz a maior raiz (ou seja, "mais positiva") da polinômio com erro estritamente menor que .(a,b,c)[10,10]x3+ax2+bx+c0.1

Admissibilidade

A noção de admissibilidade no meu desafio anterior sobre golfe na rede neural parecia um pouco restritiva; portanto, para esse desafio, estamos usando uma definição mais liberal de rede neural feedforward:

Um neurônio é uma função especificada por um vetor de pesos , um viés e uma função de ativação da seguinte maneira:ν:RnRwRn b R f : RR bR f:RR

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

Uma rede neural de feedforward com nós de entrada é uma função de que pode ser criada a partir de uma sequência de neurônios, em que cada recebe entradas de e gera um escalar . Dado um conjunto especificado de nós de saída , a saída da rede neural é o vetor .{1,,n}(x1,,xn)Rn(νk)k=n+1Nνk:Rk1R(x1,,xk1)xkS{1,,N}((xk)kS

Como as funções de ativação podem ser ajustadas para qualquer tarefa, precisamos restringir a classe de funções de ativação para manter esse desafio interessante. As seguintes funções de ativação são permitidas:

  • Identidade. f(t)=t

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

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

  • Sigmoide. f(t)=etet+1

  • Sinusóide. f(t)=sint

No geral, uma rede neural admissível é especificada por nós de entrada, uma sequência de neurônios e nós de saída, enquanto cada neurônio é especificado por um vetor de pesos, um viés e uma função de ativação da lista acima. Por exemplo, a seguinte rede neural é admissível, embora não atenda à meta de desempenho desse desafio:

  • Nós de entrada: {1,2}

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

  • Nós de saída: {5,9,10}

Essa rede consiste em 8 neurônios, cada um com viés zero e ativação de identidade. Em palavras, essa rede calcula a sequência generalizada de Fibonacci gerada por e e, em seguida, gera os números 5, 9 e 10 dessa sequência, nessa ordem.x1x2

Pontuação

Dado um número real com expansão decimal final, seja o menor número inteiro não negativo para o qual e seja o menor número inteiro não negativo para qual é um número inteiro. Então dizemos que é a precisão de .xp(x)p10p|x|<1q(x)q10qxp(x)+q(x)xx

Por exemplo, tem uma precisão de , enquanto tem uma precisão de .x=1.0014x=00

Sua pontuação é a soma das precisões dos pesos e desvios na sua rede neural.

(Por exemplo, o exemplo acima tem uma pontuação de 16.)

Verificação

Embora as raízes possam ser expressas em termos da fórmula cúbica , a maior raiz talvez seja mais facilmente acessada por meios numéricos. Seguindo a sugestão do @ xnor, calculei a maior raiz para todas as opções de números inteiros , e os resultados podem ser encontrados aqui . Cada linha desse arquivo de texto é do formulário . Por exemplo, a primeira linha informa que a maior raiz de é aproximadamente .a,b,c[10,10]x 3 - 10 x 2 - 10 x - 10 10,99247140445449a,b,c,rootx310x210x1010.99247140445449

Editar: o arquivo original que publiquei teve erros nos casos em que o polinômio exibia uma raiz múltipla. A versão atual deve estar livre de tais erros.

Dustin G. Mixon
fonte
3
O que acontece no polinômio de entrada não tem raízes reais, como quando a=0e o quadrático tem duas raízes complexas?
xnor
Eu acho que a solução mais limpa seria dizer que a entrada será adiferente de zero, ou mesmo apenas 1. Além disso, eu recomendo colocar alguns casos de teste, dando as raízes à alta precisão para que possamos verificar se os nossos estão dentro de 0,1. Também seria bom ter saídas para todas as entradas possíveis, provavelmente em um link, já que isso é muito para o post.
xnor
11
Eu gosto das novas regras de admissibilidade. Parece que a nova função sinusóide é extremamente explorável. Eu tenho uma prova superficial de que uma função do formulário x -> a * sin(b * softplus(x) + c)pode super-ajustar qualquer número finito de pontos de dados com xprecisão de número inteiro a arbitrário usando uma frequência extremamente grande e precisa.
Xnor
11
Não tenho certeza de quão útil seria (para desafios futuros): Na teoria dos números, usamos funções de altura para medir a complexidade de um número. Por exemplo, a altura ingênua de uma fração (reduzida) é dada por (e há muitas generalizações). Talvez isso possa ser usado como uma medida alternativa. p/qh=logmax{|p|,|q|}
flawr
11
@ DustinG.Mixon Não tenho certeza se você está ciente, mas temos uma caixa de areia para postar rascunhos e discutir detalhes de um desafio, bem como um bate - papo .
flawr

Respostas:

6

14674000667 5.436.050 5.403.448 10.385 5.994 4.447
3.806 total precisão

Para uma linha de base, investiguei a seguinte abordagem: Selecione , para que, se amostrarmos o polinômio emM,δ,ϵ>0p(x)=x3+ax2+bx+c

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

então o maior ponto de amostra satisfazendo necessariamente existe e reside necessariamente dentro de da maior raiz de . Pode-se mostrar que, para nossa coleção de polinômios, pode-se usar , e .sSp(s)<ϵ0.1pM=11δ=0.1ϵ=104

Para projetar uma rede neural que implementa essa lógica, começamos com uma camada de neurônios que amostra o polinômio em . Para cada , tomamosSsS

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

A seguir, identificamos quais são menores que . Acontece que para , sustenta que somente se . Como tal, podemos usar as ativações relu para identificar exatamente nossas amostras:ϵ=104sSp(s)<104p(s)0

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

Implementamos isso com algumas camadas de neurônios:

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

Neste ponto, temos quando e, caso contrário, . Lembre-se de que procuramos a maior para a qual . Para esse fim, rotulamos como (por conveniência de notação) e, para cada , definimos iterativamentex4,s=1p(s)<104x4,s=0sx4,s=1x4,Mx5,Mk1

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

Graças a essa transformação, todo é um número inteiro não negativo e é o exclusivo para o qual . Agora podemos identificar por outra aplicação de ativações relu:x5,sssx5,s=1s

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

Explicitamente, definimos neurônios por

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

Então se e, caso contrário, . Nós os combinamos linearmente para produzir nosso nó de saída:x8,s=1s=sx8,s=0

x9=sSsx8,s=s.

Para a pontuação, cada camada possui neurônios com diferentes níveis de precisão: (1) , (2) , (3) , (4) , (5) , (6) , (7) , (8) , (9). Além disso, todas as camadas, exceto duas, possuem neurônios; a camada 5 possui neurônios e a camada 9 possui neurônio.6+3+1+9=191+4=515+5=101+1=21+1=21+1=21+1+1=33|S||S|=221|S|11

Edit: Improvements: (1) Podemos amostrar o polinômio com muito mais eficiência usando diferenças finitas. (2) Podemos ignorar as camadas 2 a 4 usando uma ativação sigmóide. (3) Os problemas de transbordamento na camada 5 podem ser evitados (e as camadas subseqüentes podem ser combinadas) aplicando com mais cuidado as ativações relu. (4) A soma final é mais barata com a soma por partes .

O que se segue é o código MATLAB. Para ser claro, precé uma função (encontrada aqui ) que calcula a precisão de um vetor de pesos ou vieses.

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

53.268 29.596 29.306 precisão total

A comunicação privada com @ A.Rex levou a esta solução, na qual construímos uma rede neural que memoriza as respostas. A idéia central é que toda função de em um conjunto finito desfruta da decomposiçãof:SRS

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

Como tal, pode-se construir uma implementação de rede neural de , primeiro transformando a entrada em uma função indicadora da entrada e, em seguida, combinando linearmente usando as saídas desejadas como pesos. Além disso, as ativações relu tornam essa transformação possível:f

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

O que se segue é uma implementação MATLAB dessa abordagem. Para ficar claro, roots.txté o arquivo raiz postado acima (encontrado aqui ) e precé uma função (encontrada aqui ) que calcula a precisão total de um vetor de pesos ou vieses.

Edit 1: Duas melhorias em relação ao original: (1) eu considerei alguns neurônios dos loops for. (2) Eu implementei a " integração de Lebesgue " na soma final, combinando primeiro termos do mesmo nível definido. Dessa forma, pago pelo valor de maior precisão de uma saída apenas uma vez a cada nível definido. Além disso, é seguro arredondar as saídas para o quinto mais próximo pelo teorema da raiz racional .

Edit 2: Melhorias menores adicionais: (1) eu considerei mais neurônios de um loop for. (2) Não me incomodo em calcular o termo na soma final para a qual a saída já é 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
fonte