Wyzwanie
Znajdź najmniejszą sieć neuronową ze sprzężeniem zwrotnym, taką, że biorąc pod uwagę dowolny trójwymiarowy wektor wejściowy z wpisami liczb całkowitych w , sieć wyprowadza największy (tzn. „Najbardziej pozytywny”) pierwiastek z wielomian z błędem ściśle mniejszym niż .
Dopuszczalność
Pojęcie dopuszczalności w moim poprzednim wyzwaniu polegającym na grze w sieci neuronowe wydawało się nieco restrykcyjne, dlatego w przypadku tego wyzwania wykorzystujemy bardziej liberalną definicję sprzężonej sieci neuronowej:
Neuron jest funkcją , który jest określony przez wektor o ciężarach , A Odchylenie , i aktywacja funkcji w następujący sposób:
Sprzężona do przodu sieć neuronowa z węzłami wejściowymi jest funkcją którą można zbudować z sekwencji neuronów, gdzie każdy pobiera dane wejściowe z i generuje skalar . Biorąc pod uwagę określony zestaw zwęzłów wyjściowych, to wyjście sieci neuronowych jest wektorem .
Ponieważ funkcje aktywacyjne można dostosować do dowolnego zadania, musimy ograniczyć klasę funkcji aktywacyjnych, aby wyzwanie było interesujące. Dozwolone są następujące funkcje aktywacji:
Tożsamość.
ReLU.
SoftPlus.
Sigmoid.
Sinusoid.
Ogólnie, dopuszczalna sieć neuronowa jest określona przez węzły wejściowe, sekwencję neuronów i węzły wyjściowe, podczas gdy każdy neuron jest określony przez wektor wag, obciążenie i funkcję aktywacji z powyższej listy. Na przykład dopuszczalna jest następująca sieć neuronowa, choć nie spełnia ona celu wydajności tego wyzwania:
Węzły wejściowe:
Neurony: dla
Węzły wyjściowe:
Ta sieć składa się z 8 neuronów, z których każdy ma zerową stronniczość i aktywację tożsamości. Innymi słowy, sieć ta oblicza uogólnioną sekwencję Fibonacciego wygenerowaną przez i a następnie wyprowadza z tej sekwencji 5., 9. i 10. liczbę w tej kolejności.
Punktacja
Biorąc pod uwagę liczbę rzeczywistą z końcowym rozszerzeniem dziesiętnym, niech będzie najmniejszą nieujemną liczbą całkowitą dla której i niech będzie najmniejszą nieujemną liczbą całkowitą dla której jest liczbą całkowitą. Wtedy mówimy, jest precyzja z .
Na przykład ma dokładność , podczas gdy ma dokładność .
Twój wynik to suma dokładności wag i stronniczości w sieci neuronowej.
(Np. Powyższy przykład ma 16 punktów).
Weryfikacja
Chociaż korzenie można wyrazić za pomocą wzoru sześciennego , największy dostęp do korzenia można najłatwiej uzyskać za pomocą metod numerycznych. Zgodnie z sugestią @ xnora obliczyłem największy pierwiastek dla każdego wyboru liczb całkowitych , a wyniki można znaleźć tutaj . Każda linia tego pliku tekstowego ma formę a,b,c,root
. Na przykład w pierwszym wierszu podano, że największy pierwiastek z wynosi około .
Edycja: oryginalny plik, który opublikowałem, zawierał błędy w przypadkach, gdy wielomian zawierał wiele elementów głównych. Obecna wersja powinna być wolna od takich błędów.
źródło
a=0
i kwadrat ma dwa złożone pierwiastki?a
niezerowe, a nawet tylko 1. Zalecam też umieszczenie niektórych przypadków testowych, dając pierwiastek wysokiej precyzji, abyśmy mogli sprawdzić, czy nasze wartości mieszczą się w granicach 0,1. Dobrze byłoby mieć dane wyjściowe dla wszystkich możliwych danych wejściowych, prawdopodobnie w łączu, ponieważ to dużo dla postu.x -> a * sin(b * softplus(x) + c)
może zastąpić dowolną skończoną liczbę punktów danych z liczbą całkowitąx
na dowolną precyzję przy użyciu bardzo dużej i precyzyjnej częstotliwości.Odpowiedzi:
14674,000,667 54360505403448 10385 599444473806 Całkowity precyzja
Dla linii bazowej zbadałem następujące podejście: WybierzM,δ,ϵ>0 tak, że jeśli próbkujemy wielomian p(x)=x3+ax2+bx+c przy
wtedy największy punkt próbkowanias⋆∈S spełniający p(s⋆)<ϵ koniecznie istnieje i musi znajdować się w granicach 0.1 największego pierwiastka z p . Można pokazać, że dla naszej kolekcji wielomianów można przyjąć M=11 , δ=0.1 i ϵ=10−4 .
Projektowania sieci neuronowej, który realizuje to logiczne, że początek warstwie neuronów próbki wielomian naS . W odniesieniu do każdego s∈S bierzemy
Następnie możemy określić, które z nich są mniej niżϵ=10−4 . Okazuje się, że dla s∈S utrzymuje, że p(s)<10−4 tylko wtedy, gdy p(s)≤0 . Jako takie, możemy użyć aktywacji relu, aby dokładnie zidentyfikować nasze próbki:
Realizujemy to za pomocą kilku warstw neuronów:
At this point, we havex4,s=1 when p(s)<10−4 , and otherwise x4,s=0 . Recall that we seek the largest s⋆ for which x4,s⋆=1 . To this end, we label x4,M as x5,M (for notational convenience), and for each k≥1 , we iteratively define
Explicitly, we define neurons by
Thenx8,s=1 if s=s⋆ and otherwise x8,s=0 . We linearly combine these to produce our output node:
For the score, each layer has neurons with different levels of precision: (1)6+3+1+9=19 , (2) 1+4=5 , (3) 1 , (4) 5+5=10 , (5) 1+1=2 , (6) 1+1=2 , (7) 1+1=2 , (8) 1+1+1=3 , (9) 3|S| . Furthermore, all but two of the layers have |S|=221 neurons; layer 5 has |S|−1 neurons and layer 9 has 1 neuron.
Edit: Improvements: (1) We can sample the polynomial much more efficiently using finite differences. (2) We can bypass layers 2 through 4 by instead using a sigmoid activation. (3) The overflow issues in layer 5 can be averted (and subsequent layers can be combined) by more carefully applying relu activations. (4) The final sum is cheaper with summation by parts.
What follows is the MATLAB code. To be clear,
prec
is a function (found here) that computes the precision of a vector of weights or biases.źródło
53,26829,59629,306 total precisionPrivate communication with @A.Rex led to this solution, in which we construct a neural net that memorizes the answers. The core idea is that every functionf:S→R over a finite set S enjoys the decomposition
As such, one may construct a neural net implementation off by first transforming the input into an indicator function of the input, and then linearly combining using the desired outputs as weights. Furthermore, relu activations make this transformation possible:
What follows is a MATLAB implementation of this approach. To be clear,
roots.txt
is the roots file posted above (found here), andprec
is a function (found here) that computes the total precision of a vector of weights or biases.Edit 1: Two improvements over the original: (1) I factored some neurons out of the for loops. (2) I implemented "Lebesgue integration" in the final sum by first combining terms from the same level set. This way, I pay for the higher-precision value of an output only once every level set. Also, it is safe to round outputs to the nearest fifth by the rational root theorem.
Edit 2: Additional minor improvements: (1) I factored more neurons out of a for loop. (2) I don't bother computing the term in the final sum for which the output is already zero.
źródło