Найти самый большой корень многочлена с нейронной сетью

Соревнование

Найдите наименьшую нейронную сеть с прямой связью, чтобы при любом трехмерном входном векторе $(a,b,c)$ с целочисленными значениями в $[-10,10]$ сеть выводила самый большой (т. Е. «Наиболее положительный») корень полином $x^3+ax^2+bx+c$ с ошибкой, строго меньшей $0.1$ .

допустимость

Понятие допустимости в моей предыдущей игре в нейронную сеть выглядело немного ограничительным, поэтому для этой задачи мы используем более либеральное определение нейронной сети с прямой связью:

Нейрон является функцией $\nu\colon\mathbf{R}^n\to\mathbf{R}$ , который задается вектором $w\in\mathbf{R}^{n}$ из весов , A смещения $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.$

Нейронная сеть с прямой связью с входными узлами $\{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}$ .

Поскольку функции активации могут быть настроены для любой конкретной задачи, нам нужно ограничить класс функций активации, чтобы эта задача была интересной. Разрешены следующие функции активации:

Идентичность. $f(t)=t$
РЕЛУ. $f(t)=\operatorname{max}(t,0)$
Softplus. $f(t)=\ln(e^t+1)$
Сигмовидной. $f(t)=\frac{e^t}{e^t+1}$
Синусоида. $f(t)=\sin t$

В целом, допустимая нейронная сеть определяется входными узлами, последовательностью нейронов и выходными узлами, в то время как каждый нейрон задается вектором весов, смещением и функцией активации из приведенного выше списка. Например, допустима следующая нейронная сеть, хотя она не соответствует цели производительности этой задачи:

Входные узлы: $\{1,2\}$
Нейроны: $\nu_k(x_1,\ldots,x_{k-1}):=x_{k-2}+x_{k-1}$ для $k\in\{3,\ldots,10\}$
Выходные узлы: $\{5,9,10\}$

Эта сеть состоит из 8 нейронов, каждый с нулевым смещением и активацией идентичности. Словом, эта сеть вычисляет обобщенную последовательность Фибоначчи, сгенерированную $x_1$ и $x_2$ а затем выводит 5-е, 9-е и 10-е числа из этой последовательности в указанном порядке.

счет

Дано вещественное число $x$ с завершающим десятичным разложением, пусть $p(x)$ наименьшее неотрицательное целое число $p$ для которого $10^{-p}\cdot |x|<1$ , и пусть $q(x)$ наименьшее неотрицательное целое число $q$ для которого $10^q \cdot x$ является целым числом. Тогда мы говорим , $p(x)+q(x)$ является точностью от $x$ .

Например, $x=1.001$ имеет точность $4$ , тогда как $x=0$ имеет точность $0$ .

Ваша оценка - это сумма точности весов и смещений в вашей нейронной сети.

(Например, приведенный выше пример имеет оценку 16.)

верификация

В то время как корни могут быть выражены через кубическую формулу , самый большой корень, возможно, легче всего получить с помощью числовых средств. Следуя предложению @ xnor, я вычислил самый большой корень для каждого выбора целых чисел $a,b,c\in[-10,10]$ , и результаты можно найти здесь . Каждая строка этого текстового файла имеет форму a,b,c,root. Например, первая строка сообщает, что самый большой корень из $x^3-10x^2-10x-10$ составляет примерно $10.99247140445449$ .

Редактировать: исходный файл, который я разместил, имел ошибки в тех случаях, когда полином имел многократный корень. Текущая версия не должна содержать таких ошибок.

code-challenge optimization polynomials neural-networks Дастин Г. Миксон
источник

То, что происходит во входном полиноме, не имеет реальных корней, например, когда a=0квадратик имеет два сложных корня?

xnor

Я думаю, что самым чистым решением было бы сказать, что входные данные будут aотличны от нуля или даже равны 1. Кроме того, я бы порекомендовал ввести несколько тестовых случаев, чтобы получить корни с высокой точностью, чтобы мы могли проверить, что наши значения находятся в пределах 0,1. Также было бы хорошо иметь выходные данные для всех возможных входов, вероятно, в виде ссылки, поскольку это много для поста.

xnor

Мне нравятся новые правила приемлемости. Похоже, что новая функция синусоиды чрезвычайно полезна. У меня есть отрывочное доказательство того, что функция формы x -> a * sin(b * softplus(x) + c)может переопределить любое конечное число точек данных с целочисленной xили произвольной точностью, используя чрезвычайно большую и точную частоту.

xnor

Не уверен, насколько это будет полезно (для будущих задач): в теории чисел мы используем функции высоты для измерения сложности числа. Например, наивная высота (уменьшенной) дроби

определяется как

(и есть много обобщений). Может быть, это может быть использовано в качестве альтернативной меры.

p / q

$p/q$

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

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

Flawr

@ DustinG.Mixon Я не уверен, что вы в курсе, но у нас есть песочница для публикации черновиков и обсуждения деталей конкурса, а также чата .

Flawr

Ответы:

14 674 000 667 5 436 050 5 403 448 10 385 5 994
4 447 3 806 общей точности

Для базовой линии я исследовал следующий подход: выберите $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\},$

тогда наибольшая выборочная точка $s^\star\in S$ удовлетворяющая условию $p(s^\star)<\epsilon$ обязательно существует и обязательно находится в пределах $0.1$ от наибольшего корня из $p$ . Можно показать, что для нашего набора полиномов можно взять $M=11$ , $\delta=0.1$ и $\epsilon=10^{-4}$ .

Чтобы создать нейронную сеть , которая реализует эту логику, мы начинаем со слоем нейронов, образец многочлена на $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.$

Далее мы определяем, какие из них меньше $\epsilon=10^{-4}$ . Оказывается, что для $s\in S$ верно, что $p(s)<10^{-4}$ только если $p(s)\leq 0$ . Таким образом, мы можем использовать активацию relu для точной идентификации наших образцов:

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

Мы реализуем это с помощью нескольких слоев нейронов:

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

В этот момент мы имеем $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}.$

Благодаря этому преобразованию каждое $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.$

Явно мы определяем нейроны

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

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^{⋆} .

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

Далее следует код MATLAB. Для ясности, precэто функция (найденная здесь ), которая вычисляет точность вектора весов или смещений.

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

Дастин Г. Миксон
источник

53268 29596 29306 Общая точность

Частное общение с @ A.Rex привело к этому решению, в котором мы строим нейронную сеть, которая запоминает ответы. Основная идея заключается в том, что каждая функция $f\colon S\to\mathbf{R}$ над конечным множеством $S$ наслаждается разложением

е (Икс) знак равно \underset{s \in S}{Σ} е (s) \cdot {\begin{array}{cl} 1 & если Икс знак равно s \\ 0 & еще \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$ сначала преобразовав вход в индикаторную функцию входа, а затем линейно скомбинировав, используя нужные выходы в качестве весов. Кроме того, активация relu делает возможным это преобразование:

р е L U (T - 1) - 2 \cdot р е L U (T) + р е L U (T + 1) знак равно {\begin{array}{cl} 1 & если T знак равно 0 \\ 0 & если 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.$

Далее следует реализация этого подхода в MATLAB. Для ясности, roots.txtфайл корней, размещенный выше (найден здесь ), и precявляется функцией (найденной здесь ), которая вычисляет общую точность вектора весов или смещений.

Редактировать 1: Два улучшения по сравнению с оригиналом: (1) Я вычленял несколько нейронов из циклов for. (2) Я реализовал « интеграцию Лебега » в окончательной сумме, сначала объединив термины из того же набора уровней. Таким образом, я плачу за более высокую точность вывода только один раз за каждый установленный уровень. Кроме того, безопасно округлять выходные данные до ближайшей пятой по рациональной корневой теореме .

Редактировать 2: Дополнительные незначительные улучшения: (1) Я выделил больше нейронов из цикла for. (2) Я не пытаюсь вычислить термин в окончательной сумме, для которой результат уже равен нулю.

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

Дастин Г. Миксон
источник

Найти самый большой корень многочлена с нейронной сетью

Соревнование

допустимость

счет

верификация

Ответы:

14 674 000 667 5 436 050 5 403 448 10 385 5 994 4 447 3 806 общей точности

53268 29596 29306 Общая точность

14 674 000 667 5 436 050 5 403 448 10 385 5 994
4 447 3 806 общей точности