10
$\begingroup$

I'm reading the cornerstone paper Sequence to Sequence Learning with Neural Networks by Ilya Sutskever and Quoc Le. On the first page, it briefly mentions that:

A surprising example of the power of DNNs is their ability to sort
N N-bit numbers using only 2 hidden layers of quadratic size 

Can anyone briefly outline how to sort numbers using only 2 hidden layers?

$\endgroup$
3
$\begingroup$

Doing some research, I found a paper which proves that sorting can be done with at most 3 layers, and that their solution is optimal if you restrict the size of the network to be polynomial w.r.t. to the number of input numbers:

Depth Efficient Neural Networks for Division and Related Problems, see Theorem 7 on page 955 (page 10 in the PDF).

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Thanks for finding the relevant paper! Actually, this paper does the sorting with "depth" 3, which appears to mean just two hidden layers. See also their reference 14 which they rely on for the lower bound, "Threshold Circuits of Bounded Depth" igi-web.tugraz.at/people/maass/psfiles/34o.pdf (also on ResearchGate) esp pages 131-132 (3-4 in pdf). $\endgroup$ – Ben Reiniger Jul 13 '19 at 12:41
1
$\begingroup$

I'd imagine one could come up with weights manually to do the job exactly, but maybe the point is to be able to train one? A couple of examples:

How to sort numbers using Convolutional Neural Network?

https://github.com/primaryobjects/nnsorting

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.