Fondo

Reconocer la primalidad parece ser un mal ajuste para las redes neuronales (artificiales). Sin embargo, el teorema de aproximación universal establece que las redes neuronales pueden aproximarse a cualquier función continua, por lo que en particular debería ser posible representar cualquier función con soporte finito que uno desee. Así que tratemos de reconocer todos los números primos entre el primer millón de números.

Más precisamente, porque este es un sitio web de programación, pasemos a 2 ^ 20 = 1,048,576. El número de primos por debajo de este umbral es 82,025 o aproximadamente 8%.

Reto

¿Qué tan pequeña de una red neuronal puede encontrar que clasifique correctamente todos los enteros de 20 bits como primos o no primos?

Para los propósitos de este desafío, el tamaño de una red neuronal es el número total de pesos y sesgos necesarios para representarlo.

Detalles

El objetivo es minimizar el tamaño de una única red neuronal explícita.

La entrada a su red será un vector de longitud 20 que contiene los bits individuales de un número entero, representado con 0s y 1s o alternativamente con -1s y + 1s. El orden de estos puede ser el bit más significativo primero o el bit menos significativo primero.

La salida de su red debe ser un solo número, de modo que por encima de algún límite, la entrada se reconozca como primo y por debajo del mismo límite, la entrada se reconozca como no primo. Por ejemplo, positivo podría significar primo (y negativo no primo), o alternativamente mayor que 0.5 podría significar primo (y menor que 0.5 no primo).

La red debe ser 100% precisa en todas las 2 ^ 20 = 1,048,576 posibles entradas. Como se mencionó anteriormente, tenga en cuenta que hay 82,025 primos en este rango. (Resulta que siempre generar "no primo" sería 92% de precisión).

En términos de terminología de red neuronal estándar, esto probablemente se denominaría sobreajuste . En otras palabras, su objetivo es sobreajustar perfectamente los números primos. Otras palabras que uno podría usar es que el "conjunto de entrenamiento" y el "conjunto de prueba" son los mismos.

Este desafío no considera el número de parámetros "entrenables" o "aprendibles". De hecho, es probable que su red contenga pesos codificados, y el siguiente ejemplo está totalmente codificado. En cambio, todos los pesos y sesgos se consideran parámetros y se cuentan.

La longitud del código necesario para entrenar o generar su red neuronal no es relevante para su puntaje, pero ciertamente se agradece publicar el código relevante.

Base

Como línea de base, es posible "memorizar" todos los 82,025 números primos con 1,804,551 pesos totales y sesgos.

Tenga en cuenta que el siguiente código incluye muchas cosas: un ejemplo funcional, un código de prueba funcional, una definición funcional de red neuronal utilizando una biblioteca de red neuronal conocida, una red neuronal "codificada" (o al menos no "capacitada") y una medida de trabajo de puntaje.

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é es una red neuronal?

Para los propósitos de este desafío, podemos escribir una definición estrecha pero precisa de una red neuronal (artificial). Para algunas lecturas externas, sugiero Wikipedia sobre redes neuronales artificiales , redes neuronales de avance , perceptrón multicapa y función de activación .

Una red neuronal de avance es una colección de capas de neuronas. El número de neuronas por capa varía, con 20 neuronas en la capa de entrada, cierto número de neuronas en una o más capas ocultas y 1 neurona en la capa de salida. (Debe haber al menos una capa oculta porque los primos y los no primos no son linealmente separables de acuerdo con sus patrones de bits). En el ejemplo de línea de base anterior, los tamaños de las capas son [20, 82025, 1].

Los valores de las neuronas de entrada están determinados por la entrada. Como se describió anteriormente, esto será 0s y 1s correspondientes a los bits de un número entre 0 y 2 ^ 20, o -1s y + 1s de manera similar.

Los valores de las neuronas de cada capa siguiente, incluida la capa de salida, se determinan a partir de la capa de antemano. Primero se aplica una función lineal, de manera totalmente conectada o densa . Un método para representar dicha función es usar una matriz de pesos . Por ejemplo, las transiciones entre las dos primeras capas de la línea de base se pueden representar con una matriz de 82025 x 20. El número de pesos es el número de entradas en esta matriz, por ejemplo, 1640500. Luego, cada entrada tiene un término de sesgo (separado) agregado. Esto puede ser representado por un vector, por ejemplo, una matriz de 82025 x 1 en nuestro caso. El número de sesgos es el número de entradas, por ejemplo, 82025. (Tenga en cuenta que los pesos y los sesgos juntos describen una función lineal afín ).

Un peso o sesgo se cuenta incluso si es cero. Para los propósitos de esta definición limitada, los sesgos cuentan como pesos incluso si todos son cero. Tenga en cuenta que en el ejemplo de línea de base, solo se usan dos pesos distintos (+1 y -1) (y solo sesgos ligeramente más distintos); no obstante, el tamaño es más de un millón, porque la repetición no ayuda con la puntuación de ninguna manera.

Finalmente, una función no lineal llamada función de activación se aplica de entrada al resultado de esta función lineal afín. Para los propósitos de esta definición limitada, las funciones de activación permitidas son ReLU , tanh y sigmoid . Toda la capa debe usar la misma función de activación.

En el ejemplo de referencia, el número de pesos es 20 * 82025 + 82025 * 1 = 1722525 y el número de sesgos es 82025 + 1 = 82026, para un puntaje total de 1722525 + 82026 = 1804551. Como ejemplo simbólico, si hubiera una capa más y los tamaños de capa eran en cambio [20, a, b, 1], entonces el número de pesos sería 20 * a + a * b + b * 1 y el número de sesgos sería a + b + 1.

Esta definición de red neuronal está bien respaldada por muchos marcos, incluidos Keras , scikit-learn y Tensorflow . Keras se usa en el ejemplo de línea de base anterior, con un código esencialmente como sigue:

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 las matrices de pesos y sesgos son matrices numpy , entonces numpy.size le indicará directamente el número de entradas.

¿Hay otros tipos de redes neuronales?

Si desea una definición única y precisa de red neuronal y puntaje para los propósitos de este desafío, utilice la definición en la sección anterior. Si cree que "cualquier función" vista de la manera correcta es una red neuronal sin parámetros , utilice la definición en la sección anterior.

Si eres un espíritu más libre, entonces te animo a explorar más. Quizás su respuesta no contará para el desafío limitado , pero tal vez se divertirá más. Algunas otras ideas que puede probar incluyen funciones de activación más exóticas, redes neuronales recurrentes (lectura de un bit a la vez), redes neuronales convolucionales, arquitecturas más exóticas, softmax y LSTM (!). Puede usar cualquier función de activación estándar y cualquier arquitectura estándar. Una definición liberal de las características de la red neuronal "estándar" podría incluir cualquier cosa publicada en el arxiv antes de la publicación de esta pregunta.

División de prueba: puntaje 59407, 6243 capas, 16478 neuronas en total

Dado como un programa Python que genera y valida la red. Vea los comentarios en trial_divisionpara una explicación de cómo funciona. La validación es bastante lenta (como en tiempo de ejecución medido en horas): recomiendo usar PyPy o Cython.

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

El umbral es 1: cualquier cosa por encima de eso es primo, cualquier cosa por debajo es compuesta o cero, y la única entrada que da una salida de 1 es 1 en sí.

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

Como un aparte, re

El teorema de aproximación universal establece que las redes neuronales pueden aproximarse a cualquier función continua

$\max\left(0, 1 - \sum a_i\right)$$\max\left(0, 1 + \sum(a_i - 1)\right)$pero solo funciona correctamente si se garantiza que sus entradas sean 0 o 1, y puede generar enteros más grandes. Son posibles varias otras puertas en una capa, pero NOR por sí solo es Turing completo, por lo que no hay necesidad de entrar en detalles.

Puntuación 984314, 82027 capas, 246076 neuronas en total

Podemos mantener las cosas enteramente en los enteros si utilizamos la función de activación ReLU, que simplifica el análisis.

$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$ con pesos 1, 2, 4, ... y sesgo 0. Costo: (20 + 1) * 1 = 21.

Capa 2: salidas $\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))^+$ . Costo (2 + 1) * 3 = 9.

$\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))^+$

Capa 5: salidas $\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))^+$

...

Capa 82026: salidas $\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$

El puntaje es (82026-3) * 12 + 21 + 4 + 9 + 4.