Sort with a neural network

Question

The previous neural net golfing challenges (this and that) inspired me to pose a new challenge:

The challenge

Find the smallest feedforward neural network such that, given any 4-dimensional input vector \$(a,b,c,d)\$ with integer entries in \$[-10,10]\$, the network outputs \$\textrm{sort}(a,b,c,d)\$ with a coordinate-wise error strictly smaller than \$0.5\$.

Admissibility

For this challenge, a feedforward neural network is defined as a composition of layers. A layer is a function \$L\colon\mathbf{R}^n\to\mathbf{R}^m\$ that is specified by a matrix \$A\in\mathbf{R}^{m\times n}\$ of weights, a vector \$b\in\mathbf{R}^m\$ of biases, and an activation function \$f\colon\mathbf{R}\to\mathbf{R}\$ that is applied coordinate-wise:

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

Since activation functions can be tuned for any given task, we need to restrict the class of activation functions to keep this challenge interesting. The following activation functions are permitted:

• Identity. \$f(t)=t\$

• ReLU. \$f(t)=\operatorname{max}(t,0)\$

• Softplus. \$f(t)=\ln(e^t+1)\$

• Hyperbolic tangent. \$f(t)=\tanh(t)\$

• Sigmoid. \$f(t)=\frac{e^t}{e^t+1}\$

Overall, an admissible neural net takes the form \$L_k\circ L_{k-1}\circ\cdots \circ L_2\circ L_1\$ for some \$k\$, where each layer \$L_i\$ is specified by weights \$A_i\$, biases \$b_i\$, and an activation function \$f_i\$ from the above list. For example, the following neural net is admissible (while it doesn't satisfy the performance goal of this challenge, it may be a useful gadget):

$$\left[\begin{array}{c}\min(a,b)\\\max(a,b)\end{array}\right]=\left[\begin{array}{rrrr}1&-1&-\frac{1}{2}&-\frac{1}{2}\\1&-1&\frac{1}{2}&\frac{1}{2}\end{array}\right]\mathrm{ReLU}\left[\begin{array}{rr}\frac{1}{2}&\frac{1}{2}\\-\frac{1}{2}&-\frac{1}{2}\\1&-1\\-1&1\end{array}\right]\left[\begin{array}{c}a\\b\end{array}\right]$$

This example exhibits two layers. Both layers have zero bias. The first layer uses ReLU activation, while the second uses identity activation.

Scoring

Your score is the total number of nonzero weights and biases.

(E.g., the above example has a score of 16 since the bias vectors are zero.)

Answer 1

Octave, 96 88 87 84 76 54 50 weights & biases

This 6-layer neural net is essentially a 3-step sorting network built from a very simple min/max network as a component. It is basically the example network from wikipedia as shown below, with a small modification: The first two comparisons are done in parallel. To bypass negative numbers though the ReLU, we just add 100 first, and then subtract 100 again at the end.

So this should just be considered as a baseline as it is a naive implementation. It does however sort all possible numbers that do not have a too large magnitude perfectly. (We can adjust the range by replacing 100 with another number.)

Try it online!

max/min-component

There is a (considerably less elegant way more elegant now, thanks @xnor!) way to find the minimum and maximum of two numbers using less parameters:

$$\begin{align} \min &= a - ReLU(a-b) \\ \max &= b + ReLU(a-b) \end{align}$$

This means we have to use a lot less weights and biases.

Thanks @Joel for pointing out that it is sufficient to make all numbers positive in the first step and reversing it in the last one, which makes -8 weights. Thanks @xnor for pointing out an even shorter max/min method which makes -22 weights! Thanks @DustinG.Mixon for the tip of combining certain matrices which result in another -4 weights!

function z = net(u)
a1 = [100;100;0;100;100;0];
A1 = [1 0 0 0;0 0 1 0;1 0 -1 0;0 1 0 0;0 0 0 1;0 1 0 -1];
B1 = [1 0 -1 0 0 0;0 0 0 1 0 -1;0 1 1 0 0 0;0 0 0 0 1 1];
A2 = [1 0 0 0;0 1 0 0;1 -1 0 0;0 0 1 0;0 0 0 1;0 0 1 -1];
A3 = [1 0 -1 0 0 0;0 1 1 0 0 0;0 0 0 1 0 -1;0 1 1 -1 0 1;0 0 0 0 1 1];
B3 = [1 0 0 0 0;0 1 0 -1 0;0 0 1 1 0;0 0 0 0 1];
b3 = -[100;100;100;100];
relu = @(x)x .* (x>0);
id = @(x)x;
v = relu(A1 * u + a1);
w = id(B1 * v) ;
x = relu(A2 * w);
y = relu(A3 * x);
z = id(B3 * y + b3);
% disp(nnz(a1)+nnz(A1)+nnz(B1)+nnz(A2)+nnz(A3)+nnz(B3)+nnz(b3)); %uncomment to count the total number of weights
end

Try it online!