Сортировка номеров, используя только 2 скрытых слоя

10

Я читаю основополагающую статью Илья Суцкевер и Куок Ле, « Последовательность к обучению последовательностей с использованием нейронных сетей ». На первой странице кратко упоминается, что:

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 

Кто-нибудь может вкратце обрисовать, как сортировать числа, используя только 2 скрытых слоя?

Aerin
источник

Ответы:

3

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

Эффективные по глубине нейронные сети для деления и связанных с ними проблем , см. Теорему 7 на стр. 955 (стр. 10 в PDF).

Максимилиан Яниш
источник
1
Спасибо за нахождение соответствующей статьи! На самом деле, эта статья выполняет сортировку с «глубиной» 3, которая, кажется, означает только два скрытых слоя. См. Также их ссылку 14, на которую они опираются для нижней границы, «Пороговые схемы ограниченной глубины» igi-web.tugraz.at/people/maass/psfiles/34o.pdf (также на ResearchGate) esp страницы 131-132 (3 -4 в pdf).
Бен Рейнигер