Golf Machine Learning: mnożenie

68

Chciałbym zaproponować innej społeczności golfistów wyzwanie:

(Sztuczne) sieci neuronowe są bardzo popularnymi modelami uczenia maszynowego, które można projektować i szkolić w celu przybliżenia dowolnej (zwykle nieznanej) funkcji. Często stosuje się je do rozwiązywania bardzo skomplikowanych problemów, których nie wiemy jak rozwiązać algorytmicznie, takich jak rozpoznawanie mowy, niektóre rodzaje klasyfikacji obrazów, różne zadania w autonomicznych systemach sterowania, ... Jeśli szukasz podkładu w sieciach neuronowych, rozważ to doskonałe Artykuł w Wikipedii .

Ponieważ jest to pierwszy z serii, która, mam nadzieję, będzie serią wyzwań związanych z golfem w uczeniu maszynowym, chciałbym, aby sprawy były jak najprostsze:

W wybranym przez siebie języku i ramach projektuj i trenuj sieć neuronową, która biorąc pod uwagę oblicza swój produkt dla wszystkich liczb całkowitych x_1, x_2 między (i włącznie) -10 i 10 .(x1,x2)x1x2 - 10 10x1,x21010

Cel wydajnościowy

Aby się zakwalifikować, Twój model nie może różnić się o więcej niż 0.5 od poprawnego wyniku dla któregokolwiek z tych wpisów.

Zasady

Twój model

  • musi być „tradycyjną” siecią neuronową (wartość węzła jest obliczana jako ważona liniowa kombinacja niektórych węzłów w poprzedniej warstwie, po której następuje funkcja aktywacji),
  • może korzystać tylko z następujących standardowych funkcji aktywacyjnych:
    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
  • musi przyjmować albo jako tupel / vector / list / ... liczb całkowitych albo unosi się jako jedyne wejście,(x1,x2)
  • zwraca odpowiedź jako liczbę całkowitą, liczbę zmiennoprzecinkową (lub odpowiedni kontener, np. wektor lub listę, która zawiera tę odpowiedź).

Twoja odpowiedź musi zawierać (lub link do) cały kod niezbędny do sprawdzenia wyników - w tym przeszkolone masy modelu.

Punktacja

Sieć neuronowa o najmniejszej liczbie wag (w tym wag obciążenia) wygrywa.

Cieszyć się!

Stefan Mesken
źródło
9
Witamy na stronie! Myślę, że to wyzwanie może przynieść wiele korzyści dzięki bardziej solidnej definicji sieci neuronowej. Jest tu kilka rzeczy 1) Byłoby miło, gdybyś napisał to w języku, który nie oznacza jeszcze znajomości NN 2) Naprawdę powinieneś wymienić funkcje aktywacyjne w swoim poście, a nie link do zewnętrznego źródła ( linki zewnętrzne mogą się zmienić lub zniknąć).
Wheat Wizard
4
Czy możemy ponownie użyć wag / warstw splotowych? (Polecam usunięcie bonusu, ponieważ nie dodaje niczego do wyzwania i po prostu odwraca uwagę od głównego celu.) Czy ciężary powinny być rzeczywiste, czy mogą być złożone?
flawr
4
Twoje sformułowanie sugeruje, że węzły z warstwy 3 nie mogą używać danych wejściowych z warstwy 1. Czy kosztowanie węzła warstwy 2 po prostu f(x) = xprzesyła dane wejściowe?
Grimy
4
W prawej kolumnie powinien znajdować się link do piaskownicy, która została utworzona specjalnie w celu rozwiązania tego rodzaju problemów, zanim pytanie zostanie nawet opublikowane na głównej stronie. A filozofią sieci jest to, że lepiej jest zamknąć pytanie, naprawić je i otworzyć ponownie niż uzyskać garść odpowiedzi, które albo nie będą miały sensu po ustaleniu pytania, albo ściśle ograniczą zmiany, które można wprowadzić w pytaniu .
Peter Taylor
7
Ani trochę. Tego rodzaju problemy są wykrywane przez wieloletnie doświadczenie, gdy inni ludzie popełniają ten sam rodzaj błędów. Pewne niejasności przemykają obok piaskownicy, ale wiele innych zostaje tam złapanych. I na pewno zostałoby to złapane, ponieważ, jak wskazano w moim pierwszym komentarzu, mieliśmy dokładnie takie same problemy z pytaniem o sieć neuronową dwa miesiące temu.
Peter Taylor

Odpowiedzi:

37

21 13 11 9 ciężarów

Opiera się to na identyczności polaryzacji form dwuliniowych, która w rzeczywistym przypadku jednowymiarowym sprowadza się do tożsamości wielomianowej:

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

Więc y1po prostu oblicza [x+y, x-y]za pomocą transformacji liniowej i y3jest po prostu wartością bezwzględną y1jako krok wstępnego przetwarzania dla następnego: Następnie „twarda” część oblicza kwadraty, które wyjaśnię poniżej, a następnie po prostu oblicza różnicę i skalowanie, które jest znowu operacją liniową.

W celu obliczenia pola I użyć wykładniczy serii , która powinna być odpowiednia dla wszystkich liczb w ciągu około . Ta seria ma formęs{0,1,2,,20}0.5

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

gdzie właśnie zoptymalizowałem dla wag W2( ). Całe to przybliżenie obejmuje ponownie tylko dwie transformacje liniowe z aktywacją wykładniczą umieszczoną pomiędzy nimi. Takie podejście powoduje maksymalne odchylenie około .=(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

Wypróbuj online!

wada
źródło
Myślę, że twój kod sprawdzający w stopce linku TIO pomija aplikację abs. Ale i tak wszystko jest w porządku.
Christian Sievers
@ChristianSievers Dzięki, zaktualizowałem link TIO!
flawr
Nie jestem ekspertem od NN, z ciekawości, w jaki sposób oblicza się wagę? y0potrzebuje 4, y1potrzebuje 2, y3potrzebuje 2, y4potrzebuje 1, y5potrzebuje 1 i y6potrzebuje 2. To jest 12?
Margaret Bloom
3
@MargaretBloom Tak, to rzeczywiście jest trochę niezwykłe, ale OP stwierdził w komentarzach, że możemy ponownie użyć ciężarków i zawsze musimy je policzyć tylko raz, nawet jeśli wielokrotnie użyjemy tej samej wagi. Wszystkie wagi, których używam, są zdefiniowane w pierwszej części funkcji.
flawr
31

7 ciężarków

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

Wypróbuj online!

Używa następującej przybliżonej równości dla małego na podstawie rozszerzenia Taylora :ϵex1+x+x22

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

Wybranie tyle małe, że mieści się w wymaganych granicach błędu. Zauważ, że i są stałymi wagami w kodzie.ϵepsc

xnor
źródło
1
Nie jestem pewien, czy liczy się to jako „tradycyjna sieć neuronowa” (reguła nr 1), ale oczywiste jest, że można ją przeformatować w jedną, więc nie widzę w tym żadnego problemu. Fajne rozwiązanie!
Stefan Mesken
1
Możesz zdefiniować C = -B(1 wagę), a następnie mieć [e_s, e_d] = conv([A,B,C], [eps, eps])(2 ciężary), aby zaoszczędzić jedną wagę :) (BTW: Bardzo sprytne podejście!)
flawr
(Zapomniałem dodać exp)
wada
4
Możesz nawet obniżyć znacznie, ponownie wykorzystując odważniki - nie musisz wielokrotnie liczyć tej samej masy.
flawr
2
@flawr To niezła sztuczka, ale myślę, że tolerancja na splot i ponowne użycie wag w komentarzach sprawia, że ​​jest to tak różne wyzwanie, że zamierzam zachować tę odpowiedź w obecnej postaci.
xnor
22

33 31 ciężarów

# 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";

Wypróbuj online!

Powoduje to długie mnożenie w (sorta) binariach, a tym samym zwraca dokładny wynik. Powinno być możliwe skorzystanie z okna błędu 0,5, aby zagrać w golfa, ale nie jestem pewien, jak to zrobić.

Warstwy od 1 do 6 rozkładają pierwsze wejście w 5 „bitach”. Z powodów golfowych nie używamy rzeczywistych plików binarnych. Najbardziej znaczący „bit” ma wagę -15 zamiast 16, a gdy wejście ma wartość 0, wszystkie „bity” mają wartość 0,5 (co nadal działa dobrze, ponieważ zachowuje tożsamość inputA = -15*a15 + 8*a8 + 4*a4 + 2*a2 + 1*a1).

Umorusany
źródło
1
Spodziewałem się, że ktoś wymyśli na stałe zakodowany algorytm multiplikacji ANN. Ale nie sądziłem, że to będzie pierwsza odpowiedź. Dobra robota! (Zależy mi również na tym, czy będziesz w stanie wyciągnąć coś takiego za pomocą zestawu danych MNIST lub innego, bardziej relastycznego problemu ML: D.)
Stefan Mesken
14

43 ciężary

Dwa opublikowane dotychczas rozwiązania były bardzo sprytne, ale ich podejścia prawdopodobnie nie będą działać w przypadku bardziej tradycyjnych zadań w uczeniu maszynowym (takich jak OCR). Dlatego chciałbym przedstawić „ogólne” (bez sprytnych sztuczek) rozwiązanie tego zadania, które, mam nadzieję, zainspiruje innych ludzi do ulepszenia go i wciągnięcia w świat uczenia maszynowego:

Mój model jest bardzo prostą siecią neuronową z 2 ukrytymi warstwami wbudowanymi w TensorFlow 2.0 (ale każda inna struktura również by działała):

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')
])

Jak widać, wszystkie warstwy są gęste (co z pewnością nie jest optymalne), funkcja aktywacji jest tanh (co może być w porządku dla tego zadania), z wyjątkiem warstwy wyjściowej, która ze względu na charakter tego zadania, ma liniową funkcję aktywacji.

Istnieją 43 wagi:

  • (2+1)6=18 między wejściem a pierwszą ukrytą warstwą,
  • (6+1)3=21 między ukrytymi warstwami i
  • (3+1)1=4 łączy ostatnią ukrytą i warstwę wyjściową.

Wagi zostały wytrenowane (przy użyciu optymalizatora Adama) poprzez podejście dopasowania warstwowego: Po pierwsze, zostały one dopasowane, aby zminimalizować średni błąd kwadratu nie tylko przy mnożeniu liczb całkowitych między a ale w rzeczywistości na wejściach w pewnym sąsiedztwie wokół tych wartości . Powoduje to znacznie lepszą zbieżność ze względu na charakter opadania gradientu. Obejmowało to 400 epok treningu na 57 600 próbkach treningowych, przy użyciu partii o wielkości 32.1010

Następnie dopracowałem je - optymalizując pod kątem maksymalnego odchylenia w dowolnym zadaniu mnożenia liczb całkowitych. Niestety, moje nuty nie pokazują zbyt dobrego dostrajania, które skończyłem, ale było to bardzo niewielkie. W sąsiedztwie 100 epok na tych 441 próbnych ćwiczeniach, przy wielkości partii 441.

Oto wagi, z którymi skończyłem:

[<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)>]

który ledwie osiągnął określony cel w zakresie wydajności. Maksymalne odchylenie skończyło się na czym świadczy .0.44350433910=90.443504

Mój model można znaleźć tutaj i możesz go wypróbować online! w środowisku Google Colab.

Stefan Mesken
źródło
6

2 ciężary

Zainspirowały mnie inne odpowiedzi, aby przybliżyć tożsamość polaryzacji w inny sposób. Trzyma to dla każdego małegoϵ>0

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

Dla tego wyzwania wystarczy wziąć .ϵ=0.01

Oczywista implementacja tego przybliżenia w sieci neuronowej przyjmuje wagi w . Te cztery ciężary można golfować do trzech przez faktoring . Jak wspomniałem w komentarzu powyżej, każda sieć neuronowa o ciężarach z precyzją maszynową może być golfowana w (ogromną!) Sieć neuronową z tylko dwoma wyraźnymi wagami. Zastosowałem tę procedurę, aby napisać następujący kod MATLAB:{±ϵ,±(4ϵ2)1}{±ϵ,(4ϵ3)1}±(4ϵ2)1=±ϵ(4ϵ3)1

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 ] );

Podsumowując, ta sieć neuronowa składa się z 1250 010 ciężarów, z których wszystkie mieszczą się w .{±0.1}

Jak uciec z zaledwie 1 wagą (!)

Okazuje się, że można symulować dowolną sieć neuronową o masie w z większą siecią neuronową, która ma tylko jedną wagę, a mianowicie . Rzeczywiście, mnożenie przez można zaimplementować jako{±0.1}0.10.1

0.1x=wwx,

gdzie to wektor kolumny pozycji, wszystkie równe . W przypadku sieci neuronowych, w których połowa wag jest dodatnia, ta transformacja wytwarza sieć neuronową, która jest razy większa.w100.110.5

Oczywiste uogólnienie tej procedury przekształci każdą sieć neuronową o ciężarze w w większą sieć neuronową o pojedynczej wadze . W połączeniu z procedurą opisaną w moim komentarzu powyżej utrzymuje zatem, że każda sieć neuronowa o ciężarach precyzyjnych maszynowo może zostać przekształcona w sieć neuronową o pojedynczej wadze.{±10k}10k

(Być może powinniśmy zmodyfikować sposób, w jaki ponownie wykorzystywane wagi są oceniane w przyszłych wyzwaniach golfowych sieci neuronowych).

Dustin G. Mixon
źródło