Машинное обучение гольфу: умножение

68

Я хотел бы предложить другой вид игры в гольф для этого сообщества:

(Искусственные) нейронные сети являются очень популярными моделями машинного обучения, которые могут быть разработаны и обучены для приближения к любой заданной (обычно неизвестной) функции. Они часто используются для решения очень сложных задач, которые мы не знаем, как решать алгоритмически, такие как распознавание речи, определенные виды классификации изображений, различные задачи в автономных системах вождения, ... Для начинающих в нейронных сетях посчитайте это превосходным Статья в Википедии .

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

На языке и структуре по вашему выбору спроектируйте и обучите нейронную сеть, которая с учетом вычисляет их произведение для всех целых чисел между (и включая) и .(x1,x2)x1x2x1,x21010

Цель производительности

Чтобы соответствовать требованиям, ваша модель не может отклоняться более чем на от правильного результата по любой из этих записей.0.5

правила

Ваша модель

  • должна быть «традиционной» нейронной сетью (значение узла рассчитывается как взвешенная линейная комбинация некоторых узлов в предыдущем слое с последующей функцией активации),
  • разрешается использовать только следующие стандартные функции активации:
    1. linear(x)=x ,
    2. softmax(x)i=exijexj ,
    3. seluα,β(x)={βx, if x>0αβ(ex1), otherwise ,
    4. softplus(x)=ln(ex+1) ,
    5. leaky-reluα(x)={x, if x<0αx, otherwise ,
    6. tanh(x) ,
    7. sigmoid(x)=exex+1 ,
    8. hard-sigmoid(x)={0, if x<2.51, if x>2.50.2x+0.5, otherwise ,
    9. ex
  • должен принимать либо целое число / вектор / список / ... целых чисел, либо число с плавающей запятой как единственный вход,(x1,x2)
  • вернуть ответ в виде целого числа, числа с плавающей запятой (или подходящего контейнера, например, вектора или списка, который содержит этот ответ).

Ваш ответ должен включать (или ссылку на) весь код, необходимый для проверки ваших результатов, в том числе обученные веса вашей модели.

счет

Нейронная сеть с наименьшим количеством весов (включая веса смещения) выигрывает.

Наслаждайтесь!

Стефан Мескен
источник
9
Добро пожаловать на сайт! Я думаю, что эта проблема могла бы выиграть от более надежного определения нейронной сети. Здесь есть пара вещей: 1) Было бы очень хорошо, чтобы вы изложили это на языке, который еще не подразумевает знание NN. 2) Вы действительно должны перечислить функции активации в своем посте, а не ссылаться на внешний источник ( внешние ссылки могут измениться или исчезнуть).
Пшеничный волшебник
4
Можем ли мы повторно использовать веса / использовать сверточные слои? (Я рекомендую убрать бонус, поскольку он ничего не добавляет к вызову и просто отвлекает от основной цели.) Предполагается, что веса являются реальными или сложными?
flawr
4
Ваша формулировка подразумевает, что узлы из уровня 3 не могут использовать входные данные из уровня 1. Стоит ли иметь вес, когда узел 2-го уровня просто выполняет f(x) = xпересылку своих входных данных?
Grimmy
4
В правой колонке должна быть ссылка на «Песочницу», которая была создана специально для устранения подобных проблем еще до того, как вопрос будет опубликован на основном сайте. Философия сети заключается в том, что лучше закрыть вопрос, исправить его и снова открыть, чем получить кучу ответов, которые либо не будут иметь смысла после того, как вопрос будет решен, либо будут жестко ограничивать изменения, которые могут быть внесены в вопрос. ,
Питер Тейлор
7
Не за что. Подобные проблемы обнаруживаются многолетним опытом, когда другие люди совершают такие же ошибки. Некоторая неясность проскальзывает мимо песочницы, но многие другие попадают туда. И это определенно было бы замечено, потому что, как указано в моем первом комментарии, у нас были точно такие же проблемы с вопросом нейронной сети два месяца назад.
Питер Тейлор

Ответы:

37

21 13 11 9 весов

Это основано на поляризационной идентичности билинейных форм, которая в одномерном реальном случае сводится к полиномиальной идентичности:

xy=(x+y)2(xy)24

Так y1что просто вычисляет [x+y, x-y]с использованием линейного преобразования, и y3это просто абсолютное значение y1в качестве шага предварительной обработки для следующего: затем «трудная» часть вычисляет квадраты, которые я объясню ниже, а после этого просто вычисляя разницу и масштабирование, которое снова линейная операция.

Для вычисления квадратов я использую экспоненциальный ряд который должен быть точным для всех целых чисел пределах примерно . Эта серия имеет видs{0,1,2,,20}0.5

approx_square(x)=i=02wiexp(0.0001ix)

где я только что оптимизировал для весов W2( ). Вся эта аппроксимация снова включает в себя только два линейных преобразования с экспоненциальной активацией, расположенной между ними. Такой подход приводит к максимальному отклонению около .=(wi)i0.02

function p = net(x)
% 9 weights
one = 1; 
mone =-1;
zero = 0;
fourth = 0.25;
W1 = [1e-4, 2e-4];
W2  = [-199400468.100687;99700353.6313757];
b2 = 99700114.4299316;
leaky_relu = @(a,x)max(a*x,x); 


% Linear
y0 = [one, one; one, mone] * x;

% Linear + ReLU
y1 = mone * y0;
y2 = [leaky_relu(zero, y0), leaky_relu(zero, y1)];

% Linear
y3 = y2 * [one; one];

% Linear + exp
y4 = exp(y3 * W1); 

% Linear + Bias
y5 =  y4 * W2 + b2;

% Linear
y6 = [one, mone]*y5;
p = y6 * fourth;

end

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

flawr
источник
Я думаю, что ваш проверочный код в нижнем колонтитуле ссылки TIO не соответствует приложению abs. Но все хорошо в любом случае.
Кристиан Сиверс
@ChristianSievers Спасибо, я обновил ссылку TIO!
flawr
Я не специалист по NN, из любопытства, как происходит подсчет веса? y0нужно 4, y1нужно 2, y3нужно 2, y4нужно 1, y5нужно 1 и y6нужно 2. Это 12?
Маргарет Блум
3
@MargaretBloom Да, это действительно немного необычно, но ФП сказал в комментариях, что мы можем повторно использовать весы, и когда-либо придется их подсчитывать только один раз, даже если мы используем один и тот же вес несколько раз. Таким образом, все веса, которые я использую, определены в первой части функции.
flawr
31

7 весов

eps = 1e-6
c = 1 / (2 * eps * eps)

def f(A, B):
	e_s = exp(eps * A + eps * B)  # 2 weights, exp activation
	e_d = exp(eps * A - eps * B)  # 2 weights, exp activation
	return c * e_s + (-c) * e_d + (-1 / eps) * B  # 3 weights, linear activation

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

Использует следующее приближенное равенство для малых основанное на разложении Тейлора :ϵex1+x+x22

ABeϵA+ϵBeϵAϵB2ϵ2Bϵ

Достаточно маленький выбор позволяет нам выйти за границы допустимых ошибок. Обратите внимание, что и являются постоянными весами в коде.ϵepsc

XNOR
источник
1
Не уверен, что это считается «традиционной нейронной сетью» (правило № 1), но очевидно, что ее можно переформатировать в одну, поэтому я не вижу в этом проблемы. Отличное решение!
Стефан Мескен
1
Вы можете определить C = -B(1 вес) и затем иметь [e_s, e_d] = conv([A,B,C], [eps, eps])(2 веса), чтобы сэкономить один вес :) (Кстати: очень умный подход!)
недостаток
(Я забыл добавить exp)
flawr
4
Вы можете даже стать намного ниже, повторно используя веса - вам не нужно считать один и тот же вес несколько раз.
flawr
2
@ Flawr Это хороший трюк, но я думаю, что допуски для свертки и повторного использования весов в комментариях делают это настолько сложной задачей, что я собираюсь оставить этот ответ таким, какой он есть.
xнор
22

33 31 весов

# Activation functions
sub hard { $_[0] < -2.5 ? 0 : $_[0] > 2.5 ? 1 : 0.2 * $_[0] + 0.5 }
sub linear { $_[0] }

# Layer 0
sub inputA() { $a }
sub inputB() { $b }

# Layer 1
sub a15() { hard(5*inputA) }

# Layer 2
sub a8()  { hard(-5*inputA + 75*a15 - 37.5) }

# Layer 3
sub aa()  { linear(-5*inputA + 75*a15 - 40*a8) }

# Layer 4
sub a4()  { hard(aa - 17.5) }

# Layer 5
sub a2()  { hard(aa - 20*a4 - 7.5) }

# Layer 6
sub a1()  { linear(0.2*aa - 4*a4 - 2*a2) }

# Layer 7
sub b15() { hard(0.25*inputB - 5*a15) }
sub b8()  { hard(0.25*inputB - 5*a8) }
sub b4()  { hard(0.25*inputB - 5*a4) }
sub b2()  { hard(0.25*inputB - 5*a2) }
sub b1()  { hard(0.25*inputB - 5*a1) }

# Layer 8
sub output() { linear(-300*b15 + 160*b8 + 80*b4 + 40*b2 + 20*b1 - 10*inputA) }

# Test
for $a (-10..10) {
        for $b (-10..10) {
                die if abs($a * $b - output) >= 0.5;
        }
}

print "All OK";

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

Это делает длинное умножение в (sorta) двоичном и, таким образом, возвращает точный результат. Должна быть возможность воспользоваться окном ошибок 0,5 для игры в гольф, но я не уверен, как это сделать.

Слои с 1 по 6 разбивают первый вход на 5 «битов». По причинам, связанным с игрой в гольф, мы не используем настоящий бинарный файл. Наиболее значимый «бит» имеет вес -15 вместо 16, а когда входное значение равно 0, все «биты» равны 0,5 (что все еще отлично работает, поскольку сохраняет идентичность inputA = -15*a15 + 8*a8 + 4*a4 + 2*a2 + 1*a1).

Grimmy
источник
1
Я ожидал, что кто-то придумает жестко запрограммированный алгоритм умножения ANN. Но я не думал, что это будет первый ответ. Отлично сработано! (Я также хочу посмотреть, сможете ли вы выполнить что-то подобное с набором данных MNIST или с какой-нибудь другой, более упругой проблемой ML: D.)
Стефан Мескен
14

43 веса

Два решения, опубликованные до сих пор, были очень умными, но их подходы, вероятно, не будут работать для более традиционных задач в машинном обучении (таких как OCR). Поэтому я хотел бы представить «общее» (без хитрых уловок) решение этой задачи, которое, мы надеемся, вдохновит других людей улучшить ее и погрузиться в мир машинного обучения:

Моя модель представляет собой очень простую нейронную сеть с 2 скрытыми слоями, встроенными в TensorFlow 2.0 (но любой другой фреймворк также подойдет):

model = tf.keras.models.Sequential([
tf.keras.layers.Dense(6, activation='tanh', input_shape=(2,)),
tf.keras.layers.Dense(3, activation='tanh'),
tf.keras.layers.Dense(1, activation='linear')
])

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

Есть 43 веса:

  • (2+1)6=18
  • (6+1)3=21
  • (3+1)1=4

1010

Затем я настроил их - оптимизировал максимальное отклонение для любой задачи целочисленного умножения. К сожалению, мои заметки не показывают особой настройки, которую я закончил, но это было очень незначительно. В окрестностях 100 эпох на тех 441 обучающих выборках, с размером партии 441.

Вот те веса, с которыми я закончил:

[<tf.Variable 'dense/kernel:0' shape=(2, 6) dtype=float32, numpy=
 array([[ 0.10697944,  0.05394982,  0.05479664, -0.04538541,  0.05369904,
         -0.0728976 ],
        [ 0.10571832,  0.05576797, -0.04670485, -0.04466859, -0.05855528,
         -0.07390639]], dtype=float32)>,
 <tf.Variable 'dense/bias:0' shape=(6,) dtype=float32, numpy=
 array([-3.4242163, -0.8875816, -1.7694025, -1.9409281,  1.7825342,
         1.1364107], dtype=float32)>,
 <tf.Variable 'dense_1/kernel:0' shape=(6, 3) dtype=float32, numpy=
 array([[-3.0665843 ,  0.64912266,  3.7107112 ],
        [ 0.4914808 ,  2.1569328 ,  0.65417236],
        [ 3.461693  ,  1.2072319 , -4.181983  ],
        [-2.8746269 , -4.9959164 ,  4.505049  ],
        [-2.920127  , -0.0665407 ,  4.1409926 ],
        [ 1.3777553 , -3.3750365 , -0.10507642]], dtype=float32)>,
 <tf.Variable 'dense_1/bias:0' shape=(3,) dtype=float32, numpy=array([-1.376577  ,  2.8885336 ,  0.19852689], dtype=float32)>,
 <tf.Variable 'dense_2/kernel:0' shape=(3, 1) dtype=float32, numpy=
 array([[-78.7569  ],
        [-23.602606],
        [ 84.29587 ]], dtype=float32)>,
 <tf.Variable 'dense_2/bias:0' shape=(1,) dtype=float32, numpy=array([8.521169], dtype=float32)>]

0.44350433910=90.443504

Мою модель можно найти здесь, а также попробовать онлайн! в среде Google Colab.

Стефан Мескен
источник
6

2 веса

ϵ>0

xyeϵx+ϵy+eϵxϵyeϵxϵyeϵx+ϵy4ϵ2.

ϵ=0.01

{±ϵ,±(4ϵ2)1}{±ϵ,(4ϵ3)1}±(4ϵ2)1=±ϵ(4ϵ3)1, Как я упоминал в комментарии выше, каждая нейронная сеть с весами в точности станка может быть привязана к (огромной!) Нейронной сети только с двумя различными весами. Я применил эту процедуру, чтобы написать следующий код MATLAB:

function z=approxmultgolfed(x,y)

w1 = 0.1;   % first weight
w2 = -w1;   % second weight

k  = 250000;
v1 = w1*ones(k,1);
v2 = w2*ones(k,1);

L1 = w1*eye(2);
L2 = [ w1 w1; w2 w2; w1 w2; w2 w1 ];
L3 = [ v1 v1 v2 v2 ];
L4 = v1';

z = L4 * L3 * exp( L2 * L1 * [ x; y ] );

{±0.1}

Как сойти с рук всего 1 вес (!)

{±0.1}0.10.1

0.1x=wwx,

w100.110.5

{±10k}10k

(Возможно, мы должны изменить то, как повторно используемые веса будут оцениваться в будущих задачах игры в нейронную сеть.)

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