tło
Uznanie pierwszorzędności wydaje się słabym dopasowaniem do (sztucznych) sieci neuronowych. Jednak uniwersalne twierdzenie o aproksymacji stwierdza, że sieci neuronowe mogą aproksymować dowolną funkcję ciągłą, a zatem w szczególności powinna istnieć możliwość przedstawienia dowolnej finalnie obsługiwanej funkcji, której pragnie. Spróbujmy więc rozpoznać wszystkie liczby pierwsze wśród pierwszych milionów liczb.
Dokładniej, ponieważ jest to strona programistyczna, przejdźmy do 2 ^ 20 = 1 048 576. Liczba liczb pierwszych poniżej tego progu wynosi 82 025 lub około 8%.
Wyzwanie
Jak mała jest sieć neuronowa, która poprawnie klasyfikuje wszystkie 20-bitowe liczby całkowite jako pierwsze, czy nie pierwsze?
Do celów tego wyzwania rozmiar sieci neuronowej to całkowita liczba wag i odchyleń wymaganych do jej przedstawienia.
Detale
Celem jest zminimalizowanie rozmiaru pojedynczej, wyraźnej sieci neuronowej.
Wejście do twojej sieci będzie wektorem o długości 20 zawierającym poszczególne bity liczby całkowitej, reprezentowane albo przez 0s i 1s, albo alternatywnie przez -1s i + 1s. Ich kolejność może być najbardziej znacząca jako pierwsza lub najmniej znacząca jako pierwsza.
Dane wyjściowe Twojej sieci powinny być pojedynczą liczbą, tak aby powyżej pewnego odcięcia wejście było rozpoznawane jako liczba pierwsza, a poniżej tego samego odcięcia wejście było rozpoznawane jako nie pierwsze. Na przykład dodatnia może oznaczać liczbę pierwszą (a ujemna nie pierwsza), lub alternatywnie większa niż 0,5 może oznaczać pierwszą (a mniejsza niż 0,5 nie pierwsza).
Sieć musi być w 100% dokładna na wszystkich 2 ^ 20 = 1 048 576 możliwych danych wejściowych. Jak wspomniano powyżej, należy zauważyć, że w tym zakresie znajduje się 82 025 liczb pierwszych. (Wynika z tego, że zawsze wyrażenie „non prime” byłoby 92% dokładne.)
W kategoriach standardowej terminologii sieci neuronowej można to nazwać nadmiernym dopasowaniem . Innymi słowy, Twoim celem jest idealne dopasowanie liczb pierwszych. Inne słowa, których można użyć, to to, że „zestaw treningowy” i „zestaw testowy” są takie same.
To wyzwanie nie uwzględnia liczby parametrów „możliwych do wyuczenia” lub „możliwych do nauczenia”. Rzeczywiście, Twoja sieć może zawierać ciężary zakodowane na stałe, a poniższy przykład jest całkowicie zakodowany na stałe. Zamiast tego wszystkie wagi i odchylenia są uważane za parametry i są zliczane.
Długość kodu niezbędnego do wyszkolenia lub wygenerowania sieci neuronowej nie ma znaczenia dla twojego wyniku, ale opublikowanie odpowiedniego kodu jest z pewnością mile widziane.
Linia bazowa
Jako punkt wyjściowy można „zapamiętać” wszystkie 82 025 liczb pierwszych za pomocą 1 804 551 całkowitych wag i odchyleń.
Zauważ, że poniższy kod zawiera wiele rzeczy: działający przykład, działający kod testowy, robocza definicja sieci neuronowej wykorzystującej znaną bibliotekę sieci neuronowej, „zakodowaną” (lub przynajmniej „nie przeszkoloną”) sieć neuronową, oraz roboczy pomiar wyniku.
import numpy as np
bits = 20
from keras.models import Sequential
from keras.layers import Dense
from sympy import isprime
# Hardcode some weights
weights = []
biases = []
for n in xrange(1<<bits):
if not isprime(n):
continue
bit_list = [(n / (1 << i))%2 for i in xrange(bits)]
weight = [2*bit - 1 for bit in bit_list]
bias = - (sum(bit_list) - 1)
weights.append(weight)
biases .append(bias)
nprimes = len(biases)
weights1 = np.transpose(np.array(weights))
biases1 = np.array(biases )
weights2 = np.full( (nprimes,1), 1 )
biases2 = np.array( [0] )
model = Sequential()
model.add(Dense(units=nprimes, activation='relu', input_dim=bits, weights=[weights1, biases1]))
model.add(Dense(units=1, activation='relu', weights=[weights2, biases2]))
print "Total weights and biases: {}".format( np.size(weights1) + np.size(weights2) + np.size(biases1) + np.size(biases2) )
# Evaluate performance
x = []
y = []
for n in xrange(1<<bits):
row = [(n / (1 << i))%2 for i in xrange(bits)]
x.append( row )
col = 0
if isprime(n):
col = 1
y.append( col )
x = np.array(x)
y = np.array(y)
model.compile(loss='binary_crossentropy', optimizer='sgd', metrics=['accuracy'])
loss, accuracy = model.evaluate(x, y, batch_size=256)
if accuracy == 1.0:
print "Perfect fit."
else:
print "Made at least one mistake."
Co to jest sieć neuronowa?
Na potrzeby tego wyzwania możemy zapisać wąską, ale precyzyjną definicję (sztucznej) sieci neuronowej. Z jakiegoś zewnętrznego czytania, proponuję Wikipedię na sztucznej sieci neuronowej , wyprzedzającym sieci neuronowe , perceptron wielowarstwowy i funkcji aktywacji .
Wyprzedzające sieć neuronowa jest zbiorem warstw neuronów. Liczba neuronów na warstwę jest różna, z 20 neuronami w warstwie wejściowej, pewną liczbą neuronów w jednej lub więcej ukrytych warstwach i 1 neuronem w warstwie wyjściowej. (Musi istnieć co najmniej jedna ukryta warstwa, ponieważ liczb pierwszych i nie-liczb pierwszych nie można rozdzielić liniowo zgodnie z ich wzorami bitowymi.) W powyższym przykładzie linii podstawowej rozmiary warstw wynoszą [20, 82025, 1].
Wartości neuronów wejściowych są określane przez dane wejściowe. Jak opisano powyżej, będą to albo 0 i 1 s odpowiadające bitom liczby od 0 do 2 ^ 20, lub -1s i + 1 podobnie.
Wartości neuronów każdej kolejnej warstwy, w tym warstwy wyjściowej, określa się wcześniej na podstawie warstwy. Najpierw stosowana jest funkcja liniowa w sposób całkowicie połączony lub gęsty . Jedną z metod reprezentowania takiej funkcji jest użycie macierzy wag . Na przykład przejścia między dwiema pierwszymi warstwami linii podstawowej można przedstawić za pomocą macierzy 82025 x 20. Liczba wag jest liczbą wpisów w tej macierzy, np. 1640500. Następnie do każdego wpisu dodawany jest (osobny) termin odchylenia. Może to być reprezentowane przez wektor, np. W naszym przypadku matrycę 82025 x 1. Liczba odchyleń to liczba wpisów, np. 82025. (Należy zauważyć, że wagi i odchylenia razem opisują afiniczną funkcję liniową ).
Waga lub obciążenie jest liczone, nawet jeśli wynosi zero. Do celów tej wąskiej definicji odchylenia liczone są jako wagi, nawet jeśli wszystkie są zerowe. Należy zauważyć, że w przykładzie podstawowym używane są tylko dwie różne wagi (+1 i -1) (i tylko nieco bardziej wyraźne odchylenia); niemniej jednak rozmiar jest większy niż milion, ponieważ powtórzenie w żaden sposób nie pomaga w zapisie wyniku.
Na koniec funkcja nieliniowa zwana funkcją aktywacji jest stosowana wejściowo do wyniku tej afinicznej funkcji liniowej. Do celów tej wąskiej definicji dozwolone funkcje aktywacji to ReLU , tanh i sigmoid . Cała warstwa musi korzystać z tej samej funkcji aktywacji.
W przykładzie podstawowym liczba wag wynosi 20 * 82025 + 82025 * 1 = 1722525, a liczba błędów wynosi 82025 + 1 = 82026, co daje łączny wynik 1722525 + 82026 = 1804551. Jako symboliczny przykład, gdyby istniały jeszcze jedna warstwa, a rozmiary warstw były w zamian [20, a, b, 1], wówczas liczba wag wynosiłaby 20 * a + a * b + b * 1, a liczba odchyleń wynosiłaby a + b + 1.
Ta definicja sieci neuronowej jest dobrze obsługiwana przez wiele platform, w tym Keras , scikit-learn i Tensorflow . Keras jest używany w powyższym przykładzie podstawowym, z kodem zasadniczo następującym:
from keras.models import Sequential
model = Sequential()
from keras.layers import Dense
model.add(Dense(units=82025, activation='relu', input_dim=20, weights=[weights1, biases1]))
model.add(Dense(units=1, activation='relu', weights=[weights2, biases2]))
score = numpy.size(weights1) + numpy.size(biases1) + numpy.size(weights2) + numpy.size(biases2)
Jeśli macierze wag i stronniczości są tablicami numpy , to numpy.size bezpośrednio powie ci liczbę wpisów.
Czy istnieją inne rodzaje sieci neuronowych?
Jeśli potrzebujesz pojedynczej, precyzyjnej definicji sieci neuronowej i wyniku na potrzeby tego wyzwania, skorzystaj z definicji z poprzedniej sekcji. Jeśli uważasz, że „jakakolwiek funkcja”, patrząc we właściwy sposób, jest siecią neuronową bez parametrów , skorzystaj z definicji z poprzedniej sekcji.
Jeśli jesteś bardziej wolnym duchem, zachęcam do dalszej eksploracji. Być może twoja odpowiedź nie będzie się liczyć do wąskiego wyzwania, ale może będziesz mieć więcej zabawy. Inne pomysły, które możesz wypróbować, obejmują bardziej egzotyczne funkcje aktywacyjne, rekurencyjne sieci neuronowe (odczytując po jednym na raz), splotowe sieci neuronowe, bardziej egzotyczne architektury, softmax i LSTM (!). Możesz użyć dowolnej standardowej funkcji aktywacyjnej i dowolnej standardowej architektury. Liberalna definicja „standardowych” funkcji sieci neuronowej może obejmować wszystko, co zamieszczono w arxivie przed opublikowaniem tego pytania.
Odpowiedzi:
Podział próbny: wynik 59407, 6243 warstw, ogółem 16478 neuronów
Podany jako program w języku Python, który generuje i sprawdza poprawność sieci. Zobacz komentarze w
trial_division
celu wyjaśnienia, jak to działa. Walidacja jest dość powolna (jak w, czas działania mierzony w godzinach): Zalecam użycie PyPy lub Cython.Próg wynosi 1: wszystko powyżej, co jest liczbą pierwszą, wszystko poniżej jest złożone lub zerowe, a jedyne wejście, które daje wynik 1, to samo 1.
Na marginesie, re
źródło
Ocena 984314, 82027 warstw, łącznie 246076 neuronów
Możemy zachować wszystko w liczbach całkowitych, jeśli użyjemy funkcji aktywacyjnej ReLU, która upraszcza analizę.
...
Wynik to (82026 - 3) * 12 + 21 + 4 + 9 + 4.
źródło