Сортировка с нейронной сетью

15

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

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

Найдите наименьшую нейронную сеть с прямой связью, такую, что для любого 4-мерного входного вектора (a,б,с,d) с целочисленными значениями в [-10,10] сеть выводит с координатной ошибкой, строго меньшей, чем .sort(a,b,c,d)0.5

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

Для этой задачи нейронная сеть с прямой связью определяется как композиция слоев . Слой является функцией , что определяется матрицей из веса , вектор из уклонов , а функция активации , который применяется покоординатным:L:рNрмAрм×Nбрм е:рр

L(x):=f(Ax+b),xRn,

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

  • Идентичность. е(T)знак равноT

  • РЕЛУ. е(T)знак равноМаксимум(T,0)

  • Softplus. е(T)знак равнопер(еT+1)

  • Гиперболический тангенс. е(T)знак равноTANH(T)

  • Сигмовидной. е(T)знак равноеTеT+1

В целом, допустимая нейронная сеть принимает форму для некоторого , где каждый слой определяется весами , смещениями и функцией активации из приведенного выше списка. Например, допустима следующая нейронная сеть (хотя она не удовлетворяет цели производительности этой задачи, это может быть полезным гаджетом):LКLК-1L2L1КLяAябяея

[мин(a,б)Максимум(a,б)]знак равно[1-1-12-121-11212]реLU[1212-12-121-1-11][aб]

Этот пример демонстрирует два слоя. Оба слоя имеют нулевое смещение. Первый уровень использует активацию ReLU, а второй использует идентификацию активации.

счет

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

(Например, приведенный выше пример имеет оценку 16, поскольку векторы смещения равны нулю.)

Дастин Г. Миксон
источник
2
@ Close-избиратель: Что именно неясно? Я не думаю, что ни одна из предыдущих проблем NN была так хорошо определена.
Flawr
1
Нет - пропустить соединения не разрешено.
Дастин Г. Миксон
1
@ DustinG.Mixon Я на самом деле только что нашел подход для макс / мин, который использует только 15 весов вместо 16, но это значительно менее элегантно :)
flawr
3
Это хорошо определенная задача, которая, я думаю, может послужить моделью для будущих задач нейронной сети.
xnor
1
Лично мне сложно оптимизировать без пропуска соединений. Это связано с тем, что для вывода чисел, достаточно близких к входам, требуется сортировка NN. Таким образом, представляется необходимым «запомнить» / «восстановить» входные данные по слоям. Я не понимаю, как это можно было бы сделать легко, если задействовано поскольку нет инверсий этих функций, разрешенных в качестве активаций. Таким образом, мы остались только с ReLU, для которых базовый уровень (с незначительными улучшениями, как показано в ответе дефектника) уже близок к оптимальному. еT
Джоэл

Ответы:

13

Октава , 96 88 87 84 76 54 50 весов и уклонов

Этот 6-слой нейронная сеть, по существу , 3-ступенчатые сортировки сеть построена из очень простых min/ max сетей в качестве компонента. В основном это пример сети из Википедии, как показано ниже, с небольшой модификацией: первые два сравнения выполняются параллельно. Чтобы обойти отрицательные числа через ReLU, мы просто сначала добавляем 100, а затем снова вычитаем 100 в конце.

Так что это следует рассматривать как основу, так как это наивная реализация. Однако он сортирует все возможные числа, которые не имеют слишком большой величины идеально. (Мы можем настроить диапазон, заменив 100 другим числом.)

Попробуйте онлайн!

макс / мин-компонентный

Существует ( значительно менее элегантный , более элегантный способ, благодаря @xnor!) Способ найти минимум и максимум двух чисел, используя меньше параметров:

минзнак равноa-реLU(a-б)Максимумзнак равноб+реLU(a-б)

Это означает, что мы должны использовать гораздо меньше весов и уклонов.

Спасибо @Joel за указание на то, что на первом шаге достаточно сделать все числа положительными, а на последнем - на обратном, что составляет -8 весов. Спасибо @xnor за указание на еще более короткий метод max / min, который дает -22 веса! Спасибо @ DustinG.Mixon за совет по объединению определенных матриц, которые приводят к еще -4 весам!

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

Попробуйте онлайн!

flawr
источник
1
Постоянные смещения в основном используются, чтобы сделать входы неотрицательными. После выполнения на первом уровне все промежуточные выходы блоков сравнения неотрицательны, и достаточно изменить его обратно только на последнем уровне.
Джоэл
1
Можете ли вы получить более короткий гаджет min-max с (a - relu(a-b), b + relu(a-b))?
xnor
@joel О, теперь я вижу, это имеет большой смысл :)
flawr
@xnor Спасибо большое, что имеет огромное значение !!!!
Flawr
1
Несущественный нюанс: оценка для первого смещения nnz (A1 * a0), а не nnz (a0). (Или же мы должны заплатить цену за идентификационную матрицу.) Эти цифры одинаковы в этом случае.
Дастин Г. Миксон