Hintergrund

Das Erkennen der Primalität scheint für (künstliche) neuronale Netze schlecht geeignet zu sein. Der universelle Approximationssatz besagt jedoch, dass neuronale Netze jede kontinuierliche Funktion approximieren können, so dass es insbesondere möglich sein sollte, jede beliebige endlich unterstützte Funktion darzustellen. Versuchen wir also, alle Primzahlen unter den ersten Millionen Zahlen zu erkennen.

Genauer gesagt, da dies eine Programmierwebsite ist, steigen wir auf 2 ^ 20 = 1.048.576. Die Anzahl der Primzahlen unterhalb dieser Schwelle beträgt 82.025 oder ungefähr 8%.

Herausforderung

Wie klein von einem neuronalen Netzwerk können Sie feststellen, dass alle 20-Bit-Ganzzahlen korrekt als Primzahl oder Nicht-Primzahl klassifiziert werden?

Für die Zwecke dieser Herausforderung ist die Größe eines neuronalen Netzwerks die Gesamtzahl der Gewichte und Vorspannungen, die erforderlich sind, um es darzustellen.

Einzelheiten

Ziel ist es , die Größe eines einzelnen, expliziten neuronalen Netzwerks zu minimieren .

Die Eingabe in Ihr Netzwerk ist ein Vektor der Länge 20, der die einzelnen Bits einer Ganzzahl enthält, die entweder mit 0 und 1 oder alternativ mit -1 und + 1 dargestellt werden. Die Reihenfolge dieser kann das höchstwertige Bit zuerst oder das niedrigstwertige Bit zuerst sein.

Die Ausgabe Ihres Netzwerks sollte eine einzelne Zahl sein, sodass die Eingabe oberhalb eines bestimmten Grenzwerts als Primzahl und unterhalb desselben Grenzwerts als Nichtprimzahl erkannt wird. Zum Beispiel könnte Positiv Primzahl bedeuten (und Negativ nicht Primzahl), oder alternativ könnte Größer als 0,5 Primzahl bedeuten (und weniger als 0,5 nicht Primzahl).

Das Netzwerk muss für alle 2 ^ 20 = 1.048.576 möglichen Eingaben 100% genau sein. Wie oben erwähnt, gibt es in diesem Bereich 82.025 Primzahlen. (Daraus folgt, dass die Ausgabe von "nicht prim" immer 92% genau wäre.)

In Bezug auf die Standardterminologie für neuronale Netze würde dies wahrscheinlich als Überanpassung bezeichnet . Mit anderen Worten, Ihr Ziel ist es, die Primzahlen perfekt zu überziehen. Andere Wörter, die man verwenden könnte, sind, dass der "Trainingssatz" und der "Testsatz" gleich sind.

Diese Herausforderung berücksichtigt nicht die Anzahl der "trainierbaren" oder "lernbaren" Parameter. In der Tat enthält Ihr Netzwerk wahrscheinlich fest codierte Wertigkeiten, und das folgende Beispiel ist vollständig fest codiert. Stattdessen werden alle Gewichte und Verzerrungen als Parameter betrachtet und gezählt.

Die Länge des Codes, die zum Trainieren oder Generieren Ihres neuronalen Netzwerks erforderlich ist, ist für Ihre Punktzahl nicht relevant, aber das Posten des entsprechenden Codes ist sicherlich erwünscht.

Grundlinie

Grundsätzlich ist es möglich, sich alle 82.025 Primzahlen mit 1.804.551 Gesamtgewichten und Vorspannungen zu "merken" .

Beachten Sie, dass dieser folgende Code viele Dinge beinhaltet: ein funktionierendes Beispiel, einen funktionierenden Testcode, eine funktionierende Definition eines neuronalen Netzwerks unter Verwendung einer bekannten Bibliothek für neuronale Netzwerke, ein "hartcodiertes" (oder zumindest nicht "trainiertes") neuronales Netzwerk, und eine funktionierende Messung der Punktzahl.

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

Was ist ein neuronales Netzwerk?

Für diese Herausforderung können wir eine enge, aber genaue Definition eines (künstlichen) neuronalen Netzwerks aufschreiben. Für eine externe Lektüre empfehle ich Wikipedia zu künstlichem neuronalen Netzwerk , vorwärts gerichtetem neuronalen Netzwerk , mehrschichtigem Perzeptron und Aktivierungsfunktion .

Ein Feedforward-neuronales Netzwerk ist eine Sammlung von Schichten von Neuronen. Die Anzahl der Neuronen pro Schicht variiert, wobei sich 20 Neuronen in der Eingabeschicht, einige Neuronen in einer oder mehreren verborgenen Schichten und 1 Neuron in der Ausgabeschicht befinden. (Es muss mindestens eine ausgeblendete Ebene vorhanden sein, da Primzahlen und Nicht-Primzahlen gemäß ihren Bitmustern nicht linear trennbar sind.) Im obigen Baseline-Beispiel betragen die Größen der Ebenen [20, 82025, 1].

Die Werte der Eingangsneuronen werden durch die Eingabe bestimmt. Wie oben beschrieben, sind dies entweder 0s und 1s, die den Bits einer Zahl zwischen 0 und 2 ^ 20 entsprechen, oder -1s und + 1s in ähnlicher Weise.

Die Werte der Neuronen jeder folgenden Schicht, einschließlich der Ausgangsschicht, werden vorher aus der Schicht bestimmt. Zunächst wird eine lineare Funktion in vollständig verbundener oder dichter Weise angewendet . Eine Methode zur Darstellung einer solchen Funktion ist die Verwendung einer Gewichtungsmatrix . Beispielsweise können die Übergänge zwischen den ersten beiden Ebenen der Grundlinie mit einer 82025 x 20-Matrix dargestellt werden. Die Anzahl der Gewichtungen ist die Anzahl der Einträge in dieser Matrix, z. B. 1640500. Dann wird jedem Eintrag ein (separater) Bias-Term hinzugefügt. Dies kann durch einen Vektor dargestellt werden, z. B. eine 82025 x 1-Matrix in unserem Fall. Die Anzahl der Verzerrungen entspricht der Anzahl der Einträge, z. B. 82025. (Beachten Sie, dass die Gewichte und Verzerrungen zusammen eine affine lineare Funktion beschreiben .)

Eine Gewichtung oder Verzerrung wird gezählt, auch wenn sie Null ist. Für die Zwecke dieser engen Definition gelten Vorspannungen als Gewichte, auch wenn sie alle Null sind. Beachten Sie, dass im Baseline-Beispiel nur zwei unterschiedliche Gewichtungen (+1 und -1) verwendet werden (und nur geringfügig stärker ausgeprägte Verzerrungen). Trotzdem ist die Größe mehr als eine Million, denn die Wiederholung hilft in keiner Weise bei der Partitur.

Schließlich wird eine nichtlineare Funktion, die Aktivierungsfunktion genannt wird, eingangsweise auf das Ergebnis dieser affinen linearen Funktion angewendet. Für die Zwecke dieser engen Definition sind die zulässigen Aktivierungsfunktionen ReLU , tanh und sigmoid . Die gesamte Ebene muss dieselbe Aktivierungsfunktion verwenden.

Im Baseline-Beispiel beträgt die Anzahl der Gewichte 20 * 82025 + 82025 * 1 = 1722525 und die Anzahl der Verzerrungen beträgt 82025 + 1 = 82026, was einer Gesamtpunktzahl von 1722525 + 82026 = 1804551 entspricht eine weitere Schicht und die Schichtgrößen waren stattdessen [20, a, b, 1], dann wäre die Anzahl der Gewichte 20 * a + a * b + b * 1 und die Anzahl der Verzerrungen wäre a + b + 1.

Diese Definition des neuronalen Netzwerks wird von vielen Frameworks gut unterstützt, einschließlich Keras , Scikit-Learn und Tensorflow . Keras wird im obigen Baseline-Beispiel verwendet, wobei der Code im Wesentlichen wie folgt lautet:

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)

Wenn die Gewichte und Bias - Matrizen sind numpy Arrays, dann numpy.size gelangen Sie direkt die Anzahl der Einträge erzählen.

Gibt es andere Arten von neuronalen Netzen?

Wenn Sie eine einzige, genaue Definition des neuronalen Netzwerks und der Bewertung für diese Herausforderung wünschen, verwenden Sie bitte die Definition im vorherigen Abschnitt. Wenn Sie der Meinung sind, dass "jede Funktion" ein neuronales Netzwerk ohne Parameter ist , verwenden Sie bitte die Definition im vorherigen Abschnitt.

Wenn Sie ein freier Geist sind, dann ermutige ich Sie, weiter zu erforschen. Vielleicht zählt Ihre Antwort nicht für die knappe Herausforderung, aber vielleicht werden Sie mehr Spaß haben. Einige andere Ideen, die Sie möglicherweise ausprobieren, umfassen exotischere Aktivierungsfunktionen, wiederkehrende neuronale Netze (jeweils ein Bit lesend), faltungsmäßige neuronale Netze, exotischere Architekturen, Softmax und LSTMs (!). Sie können jede Standardaktivierungsfunktion und jede Standardarchitektur verwenden. Eine liberale Definition von "Standard" -Features für neuronale Netze könnte alles beinhalten, was vor dem Versenden dieser Frage auf arxiv veröffentlicht wurde.

Versuchsaufteilung: 59407 Punkte, 6243 Schichten, insgesamt 16478 Neuronen

Gegeben als Python-Programm, das das Netz generiert und validiert. In den Kommentaren finden Sie trial_divisioneine Erklärung zur Funktionsweise. Die Validierung ist ziemlich langsam (wie in, Laufzeit in Stunden): Ich empfehle die Verwendung von PyPy oder Cython.

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

Die Schwelle ist 1: alles, was über der Primzahl liegt, alles, was darunter liegt, ist zusammengesetzt oder Null, und die einzige Eingabe, die eine Ausgabe von 1 ergibt, ist 1 selbst.

#!/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)

Nebenbei, re

Der universelle Approximationssatz besagt, dass neuronale Netze jede kontinuierliche Funktion approximieren können

Es ist leicht zu zeigen, dass ein neuronales Netzwerk, das ReLU verwendet, vollständig ist. Das am einfachsten robust zu implementierende Logikgatter ist NOR: Ein NOR-Gatter mit n Eingängen ist . Ich sage robust, weil dieses Gatter Eingaben größer als 1 akzeptiert, aber (vorausgesetzt, die Eingaben liegen nicht zwischen 0 und 1) immer nur 0 oder 1 ausgibt. Ein einschichtiges UND-Gatter ist funktioniert aber nur dann richtig, wenn die Eingabe garantiert 0 oder 1 ist und möglicherweise größere Ganzzahlen ausgibt. In einer Schicht sind verschiedene andere Gatter möglich, aber NOR ist für sich genommen Turing-vollständig, sodass es nicht erforderlich ist, auf Details einzugehen.$\max\left(0, 1 - \sum a_i\right)$ max ( 0 , 1 + ∑ ( a i - 1 ) )$\max\left(0, 1 + \sum(a_i - 1)\right)$

Kerbe 984314, 82027 Schichten, 246076 Neuronen insgesamt

Wenn wir die Aktivierungsfunktion ReLU verwenden, die die Analyse vereinfacht, können wir die Dinge vollständig in den ganzen Zahlen belassen.

Bei einer Eingabe von die als Ganzzahl bekannt ist, können wir testen, ob mit zwei Schichten und drei Neuronen ist:$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))^+$

Schicht 4: Ausgänge $\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))^+$

Schicht 5: Ausgänge $\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))^+$

...

Schicht 82026: gibt $\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$

Die Bewertung lautet (82026-3) * 12 + 21 + 4 + 9 + 4.