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.

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_divisioncelu wyjaśnienia, jak to działa. Walidacja jest dość powolna (jak w, czas działania mierzony w godzinach): Zalecam użycie PyPy lub Cython.

$\alpha \to \max(0, \alpha)$

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.

#!/usr/bin/python3

import math


def primes_to(n):
    ps = []
    for i in range(2, n):
        is_composite = False
        for p in ps:
            if i % p == 0:
                is_composite = True
                break
            if p * p > i:
                break
        if not is_composite:
            ps.append(i)
    return ps


def eval_net(net, inputs):
    for layer in net:
        inputs.append(1)
        n = len(inputs)
        inputs = [max(0, sum(inputs[i] * neuron[i] for i in range(n))) for neuron in layer]
    return inputs


def cost(net):
    return sum(len(layer) * len(layer[0]) for layer in net)


def trial_division(num_bits):
    # Overview: we convert the bits to a single number x and perform trial division.
    # x is also our "is prime" flag: whenever we prove that x is composite, we clear it to 0
    # At the end x will be non-zero only if it's a unit or a prime, and greater than 1 only if it's a prime.
    # We calculate x % p as
    #     rem = x - (x >= (p << a) ? 1 : 0) * (p << a)
    #     rem -= (rem >= (p << (a-1)) ? 1) : 0) * (p << (a-1))
    #     ...
    #     rem -= (rem >= p ? 1 : 0) * p
    #
    # If x % p == 0 and x > p then x is a composite multiple of p and we want to set it to 0

    N = 1 << num_bits
    primes = primes_to(1 + int(2.0 ** (num_bits / 2)))

    # As a micro-optimisation we exploit 2 == -1 (mod 3) to skip a number of shifts for p=3.
    # We need to bias by a multiple of 3 which is at least num_bits // 2 so that we don't get a negative intermediate value.
    bias3 = num_bits // 2
    bias3 += (3 - (bias3 % 3)) % 3

    # inputs: [bit0, ..., bit19]
    yield [[1 << i for i in range(num_bits)] + [0],
           [-1] + [0] * (num_bits - 1) + [1],
           [0] * 2 + [-1] * (num_bits - 2) + [1],
           [(-1) ** i for i in range(num_bits)] + [bias3]]

    for p in primes[1:]:
        # As a keyhole optimisation we overlap the cases slightly.
        if p == 3:
            # [x, x_is_even, x_lt_4, x_reduced_mod_3]
            max_shift = int(math.log((bias3 + (num_bits + 1) // 2) // p, 2))
            yield [[1, 0, 0, 0, 0], [0, 1, -1, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, -1, p << max_shift]]
            yield [[1, -N, 0, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, -1, 1]]
            yield [[1, 0, 0, 0], [0, 1, -p << max_shift, 0]]
        else:
            # [x, x % old_p]
            max_shift = int(num_bits - math.log(p, 2))
            yield [[1, 0, 0], [1, -N, -p_old], [-1, 0, p << max_shift]]
            yield [[1, -N, 0, 0], [0, 0, -1, 1]]
            yield [[1, 0, 0], [1, -p << max_shift, 0]]

        for shift in range(max_shift - 1, -1, -1):
            # [x, rem]
            yield [[1, 0, 0], [0, 1, 0], [0, -1, p << shift]]
            yield [[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, -1, 1]]
            yield [[1, 0, 0, 0], [0, 1, -p << shift, 0]]
        # [x, x % p]
        p_old = p

    yield [[1, 0, 0], [1, -N, -p]]
    yield [[1, -N, 0]]


def validate_primality_tester(primality_tester, threshold):
    num_bits = len(primality_tester[0][0]) - 1
    primes = set(primes_to(1 << num_bits))
    errors = 0
    for i in range(1 << num_bits):
        expected = i in primes
        observed = eval_net(primality_tester, [(i >> shift) & 1 for shift in range(num_bits)])[-1] > threshold
        if expected != observed:
            errors += 1
            print("Failed test case", i)
        if (i & 0xff) == 0:
            print("Progress", i)

    if errors > 0:
        raise Exception("Failed " + str(errors) + " test case(s)")


if __name__ == "__main__":
    n = 20

    trial_div = list(trial_division(n))
    print("Cost", cost(trial_div))
    validate_primality_tester(trial_div, 1)

Na marginesie, re

uniwersalne twierdzenie o aproksymacji stwierdza, że ​​sieci neuronowe mogą aproksymować dowolną funkcję ciągłą

$\max\left(0, 1 - \sum a_i\right)$$\max\left(0, 1 + \sum(a_i - 1)\right)$ale działa poprawnie tylko wtedy, gdy gwarantowane są wartości wejściowe równe 0 lub 1 i może generować większe liczby całkowite. Różne inne bramy są możliwe w jednej warstwie, ale sam NOR jest kompletny z Turinga, więc nie trzeba wchodzić w szczegóły.

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ę.

$x$$x = a$

1. $\textrm{ge}_a = (x - a)^+$$\textrm{le}_a = (-x + a)^+$
2. $\textrm{eq}_a = (-\textrm{ge}_a - \textrm{le}_a + 1)^+$$\textrm{eq}_{a}$$1$$x = a$$0$

$x$

$\textrm{ge}_2 = (x - 2)^+$$\textrm{le}_2 = (-x + 2)^+$

$\textrm{accum}_2 = (-\textrm{ge}_2 - \textrm{le}_2 + 1)^+$$\textrm{ge}_3 = (\textrm{ge}_2 - (3-2))^+$$\textrm{le}_3 = (-\textrm{ge}_2 + (3-2))^+$

$\textrm{accum}_3 = (2^{21} \textrm{accum}_2 -\textrm{ge}_3 - \textrm{le}_3 + 1)^+$$\textrm{ge}_5 = (\textrm{ge}_3 - (5-3))^+$$\textrm{le}_5 = (-\textrm{ge}_3 + (5-3))^+$

$\textrm{accum}_5 = (2^{21} \textrm{accum}_3 -\textrm{ge}_5 - \textrm{le}_5 + 1)^+$$\textrm{ge}_7 = (\textrm{ge}_5 - (7-5))^+$$\textrm{le}_7 = (-\textrm{ge}_5 + (7-5))^+$

...

$\textrm{accum}_{1048571} = (2^{21} \textrm{accum}_{1048559} -\textrm{ge}_{1048571} - \textrm{le}_{1048571} + 1)^+$$\textrm{ge}_{1048573} = (\textrm{ge}_{1048571} - ({1048573}-{1048571}))^+$$\textrm{le}_{1048573} = (-\textrm{ge}_{1048571} + ({1048573}-{1048571}))^+$

$\textrm{accum}_{1048573} = (2^{21} \textrm{accum}_{1048571} -\textrm{ge}_{1048573} - \textrm{le}_{1048573} + 1)^+$

$+\infty$

Wynik to (82026 - 3) * 12 + 21 + 4 + 9 + 4.