Contexte

Reconnaître la primauté semble être un mauvais choix pour les réseaux de neurones (artificiels). Cependant, le théorème d'approximation universel stipule que les réseaux de neurones peuvent approximer n'importe quelle fonction continue, donc en particulier il devrait être possible de représenter toute fonction à support fini que l'on souhaite. Essayons donc de reconnaître tous les nombres premiers parmi le premier million de nombres.

Plus précisément, puisqu'il s'agit d'un site de programmation, montons à 2 ^ 20 = 1 048 576. Le nombre de nombres premiers inférieurs à ce seuil est de 82 025, soit environ 8%.

Défi

Quelle taille de réseau neuronal pouvez-vous trouver qui classe correctement tous les entiers de 20 bits comme premiers ou non premiers?

Aux fins de ce défi, la taille d'un réseau de neurones est le nombre total de poids et de biais nécessaires pour le représenter.

Détails

L'objectif est de minimiser la taille d'un réseau neuronal unique et explicite.

L'entrée de votre réseau sera un vecteur de longueur 20 contenant les bits individuels d'un entier, représenté soit avec 0s et 1s soit alternativement avec -1s et + 1s. L'ordre de ceux-ci peut être le bit le plus significatif en premier ou le bit le moins significatif en premier.

La sortie de votre réseau doit être un numéro unique, de sorte qu'au-dessus d'une certaine coupure, l'entrée soit reconnue comme principale et en dessous de la même coupure, l'entrée soit reconnue comme non principale. Par exemple, positif peut signifier premier (et négatif pas premier), ou alternativement supérieur à 0,5 peut signifier premier (et moins de 0,5 pas premier).

Le réseau doit être précis à 100% sur toutes les 2 ^ 20 = 1 048 576 entrées possibles. Comme mentionné ci-dessus, notez qu'il y a 82 025 nombres premiers dans cette plage. (Il s'ensuit que la sortie toujours "pas premier" serait précise à 92%.)

En termes de terminologie de réseau neuronal standard, cela s'appellerait probablement un sur- ajustement . En d'autres termes, votre objectif est de parfaitement équiper les nombres premiers. D'autres mots que l'on pourrait utiliser sont que le "kit de formation" et le "kit de test" sont identiques.

Ce défi ne prend pas en compte le nombre de paramètres «entraînables» ou «apprenants». En effet, votre réseau est susceptible de contenir des poids codés en dur, et l'exemple ci-dessous est entièrement codé en dur. Au lieu de cela, tous les poids et biais sont considérés comme des paramètres et sont comptés.

La longueur du code nécessaire pour former ou générer votre réseau neuronal n'est pas pertinente pour votre score, mais la publication du code pertinent est certainement appréciée.

Référence

Comme référence, il est possible de «mémoriser» tous les 82 025 nombres premiers avec 1 804 551 poids et biais totaux.

Notez que ce code qui suit comprend de nombreux éléments: un exemple de travail, un code de test de travail, une définition de travail d'un réseau de neurones utilisant une bibliothèque de réseaux de neurones connue, un réseau de neurones "codé en dur" (ou du moins non "formé"), et une mesure de travail du score.

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

Qu'est-ce qu'un réseau neuronal?

Aux fins de ce défi, nous pouvons écrire une définition étroite mais précise d'un réseau neuronal (artificiel). Pour une lecture externe, je suggère Wikipedia sur le réseau de neurones artificiels , le réseau de neurones à action directe , le perceptron multicouche et la fonction d'activation .

Un réseau de neurones à action directe est une collection de couches de neurones. Le nombre de neurones par couche varie, avec 20 neurones dans la couche d'entrée, un certain nombre de neurones dans une ou plusieurs couches cachées et 1 neurone dans la couche de sortie. (Il doit y avoir au moins une couche masquée car les nombres premiers et les nombres non premiers ne sont pas séparables linéairement en fonction de leurs motifs binaires.) Dans l'exemple de ligne de base ci-dessus, les tailles des couches sont [20, 82025, 1].

Les valeurs des neurones d'entrée sont déterminées par l'entrée. Comme décrit ci-dessus, ce sera soit 0s et 1s correspondant aux bits d'un nombre compris entre 0 et 2 ^ 20, soit -1s et + 1s de manière similaire.

Les valeurs des neurones de chaque couche suivante, y compris la couche de sortie, sont préalablement déterminées à partir de la couche. Tout d'abord, une fonction linéaire est appliquée, de manière entièrement connectée ou dense . Une méthode pour représenter une telle fonction consiste à utiliser une matrice de poids . Par exemple, les transitions entre les deux premières couches de la ligne de base peuvent être représentées avec une matrice 82025 x 20. Le nombre de poids est le nombre d'entrées dans cette matrice, par exemple 1640500. Ensuite, chaque entrée a un terme de biais (séparé) ajouté. Cela peut être représenté par un vecteur, par exemple une matrice 82025 x 1 dans notre cas. Le nombre de biais est le nombre d'entrées, par exemple 82025. (Notez que les poids et les biais décrivent ensemble une fonction linéaire affine .)

Un poids ou un biais est compté même s'il est nul. Aux fins de cette définition étroite, les biais comptent comme des poids même s'ils sont tous nuls. Notez que dans l'exemple de référence, seuls deux poids distincts (+1 et -1) sont utilisés (et seulement des biais légèrement plus distincts); néanmoins, la taille dépasse le million, car la répétition n'aide en rien le score.

Enfin, une fonction non linéaire appelée fonction d' activation est appliquée en entrée au résultat de cette fonction linéaire affine. Aux fins de cette définition étroite, les fonctions d'activation autorisées sont ReLU , tanh et sigmoid . La couche entière doit utiliser la même fonction d'activation.

Dans l'exemple de référence, le nombre de poids est de 20 * 82025 + 82025 * 1 = 1722525 et le nombre de biais est de 82025 + 1 = 82026, pour un score total de 1722525 + 82026 = 1804551. À titre d'exemple symbolique, s'il y avait une couche de plus et les tailles de couche étaient à la place [20, a, b, 1], alors le nombre de poids serait 20 * a + a * b + b * 1 et le nombre de biais serait a + b + 1.

Cette définition de réseau neuronal est bien prise en charge par de nombreux cadres, notamment Keras , scikit-learn et Tensorflow . Keras est utilisé dans l'exemple de base ci-dessus, avec du code essentiellement comme suit:

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)

Si les poids et les matrices de biais sont des tableaux numpy , alors numpy.size vous dira directement le nombre d'entrées.

Existe-t-il d'autres types de réseaux de neurones?

Si vous souhaitez une définition unique et précise du réseau neuronal et un score aux fins de ce défi, veuillez utiliser la définition de la section précédente. Si vous pensez que "n'importe quelle fonction" considérée de la bonne façon est un réseau neuronal sans paramètres , veuillez utiliser la définition dans la section précédente.

Si vous êtes un esprit plus libre, je vous encourage à explorer davantage. Peut-être que votre réponse ne comptera pas pour le défi étroit , mais peut-être que vous aurez plus de plaisir. Certaines autres idées que vous pouvez essayer incluent des fonctions d'activation plus exotiques, des réseaux de neurones récurrents (lecture un bit à la fois), des réseaux de neurones convolutifs, des architectures plus exotiques, softmax et LSTM (!). Vous pouvez utiliser n'importe quelle fonction d'activation standard et toute architecture standard. Une définition libérale des caractéristiques du réseau de neurones «standard» pourrait inclure tout ce qui est affiché sur l'arxiv avant la publication de cette question.

Division d'essai: score 59407, 6243 couches, 16478 neurones au total

Donné comme un programme Python qui génère et valide le net. Voir les commentaires dans trial_divisionpour une explication de son fonctionnement. La validation est assez lente (comme dans, le temps d'exécution mesuré en heures): je recommande d'utiliser PyPy ou Cython.

Toutes les couches utilisent ReLU ( ) comme fonction d'activation.$\alpha \to \max(0, \alpha)$

Le seuil est 1: tout ce qui est au-dessus de ce qui est premier, tout ce qui est en dessous est composite ou zéro, et la seule entrée qui donne une sortie de 1 est 1 elle-même.

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

En aparté, re

le théorème d'approximation universel stipule que les réseaux de neurones peuvent approximer n'importe quelle fonction continue

il est facile de montrer qu'un réseau de neurones utilisant ReLU est Turing complet. La porte logique la plus simple à implémenter de manière robuste est NOR: une porte NOR à n entrées est . Je dis vigoureusement parce que cette porte accepte des entrées supérieures à 1 mais (à condition que les entrées ne soient pas comprises entre 0 et 1) ne génère que 0 ou 1. Une porte ET à une seule couche est mais ne fonctionne correctement que si ses entrées sont garanties égales à 0 ou 1 et peuvent produire des entiers plus grands. Diverses autres portes sont possibles sur une seule couche, mais NOR en soi est Turing-complet, il n'est donc pas nécessaire d'entrer dans les détails.$\max\left(0, 1 - \sum a_i\right)$$\max\left(0, 1 + \sum(a_i - 1)\right)$

Score 984314, 82027 couches, 246076 neurones au total

Nous pouvons garder les choses entièrement dans les entiers si nous utilisons la fonction d'activation ReLU, ce qui simplifie l'analyse.

Étant donné une entrée connue pour être un entier, nous pouvons tester si avec deux couches et trois neurones:$x$$x = a$

1. Première couche: sorties et$\textrm{ge}_a = (x - a)^+$$\textrm{le}_a = (-x + a)^+$
2. Deuxième couche: sorties . sera si et sinon.$\textrm{eq}_a = (-\textrm{ge}_a - \textrm{le}_a + 1)^+$$\textrm{eq}_{a}$$1$$x = a$$0$

Couche 1: réduire les 20 entrées à une valeur avec les poids 1, 2, 4, ... et biais 0. Coût: (20 + 1) * 1 = 21.$x$

Couche 2: sorties , . Coût (1 + 1) * 2 = 4.$\textrm{ge}_2 = (x - 2)^+$$\textrm{le}_2 = (-x + 2)^+$

Couche 3: sorties , , . Coût (2 + 1) * 3 = 9.$\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))^+$

Couche 4: sorties , , . Coût (3 + 1) * 3 = 12.$\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))^+$

Couche 5: sorties , , . Coût (3 + 1) * 3 = 12.$\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))^+$

...

Couche 82026: sorties , , . Coût (3 + 1) * 3 = 12.$\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}))^+$

Couche 82027: sorties . Coût (3 + 1) * 1 = 4.$\textrm{accum}_{1048573} = (2^{21} \textrm{accum}_{1048571} -\textrm{ge}_{1048573} - \textrm{le}_{1048573} + 1)^+$

Le seuil est 0. Si vous travaillez avec des doubles, un débordement vers est tout à fait possible, mais cela semble parfaitement conforme aux règles.$+\infty$

Le score est (82026-3) * 12 + 21 + 4 + 9 + 4.