Me gustaría proponer un tipo diferente de desafío de golf para esta comunidad:

Las redes neuronales (artificiales) son modelos de aprendizaje automático muy populares que se pueden diseñar y entrenar para aproximar cualquier función (generalmente desconocida). A menudo se usan para resolver problemas muy complejos que no sabemos cómo resolver algorítmicamente, como el reconocimiento de voz, ciertos tipos de clasificaciones de imágenes, diversas tareas en sistemas de conducción autónomos, ... Para una introducción a las redes neuronales, considere esto excelente Artículo de Wikipedia .

Como este es el primero en lo que espero ser una serie de desafíos de golf de aprendizaje automático, me gustaría mantener las cosas lo más simples posible:

En el lenguaje y marco de su elección, diseñe y entrene una red neuronal que, dado calcula su producto para todos los enteros entre (e incluyendo) y .$(x_1, x_2)$$x_1 \cdot x_2$$x_1, x_2$$-10$$10$

Objetivo de rendimiento

Para calificar, su modelo no puede desviarse en más de del resultado correcto en cualquiera de esas entradas.$0.5$

Reglas

Su modelo

• debe ser una red neuronal 'tradicional' (el valor de un nodo se calcula como una combinación lineal ponderada de algunos de los nodos en una capa anterior seguida de una función de activación),
• solo puede usar las siguientes funciones de activación estándar:
  1. $\textrm{linear}(x) = x$ ,
  2. $\textrm{softmax}(\vec{x})_i = \frac{e^{x_i}}{\sum_j e^{x_j}}$ ,
  3. $\textrm{selu}_{\alpha, \beta}(x) = \begin{cases} \beta \cdot x & \text{, if } x > 0 \\ \alpha \cdot \beta (e^x -1 ) & \text{, otherwise} \end{cases}$ ,
  4. $\textrm{softplus}(x) = \ln(e^x+1)$ ,
  5. $\textrm{leaky-relu}_\alpha(x) = \begin{cases} x & \text{, if } x < 0 \\ \alpha \cdot x & \text{, otherwise} \end{cases}$ ,
  6. $\tanh(x)$ ,
  7. $\textrm{sigmoid}(x) = \frac{e^x}{e^x+1}$ ,
  8. $\textrm{hard-sigmoid}(x) = \begin{cases} 0 & \text{, if } x < -2.5 \\ 1 & \text{, if } x > 2.5 \\ 0.2 \cdot x + 0.5 & \text{, otherwise} \end{cases}$ ,
  9. $e^x$
• debe tomar como tupel / vector / list / ... de enteros o flotantes como su única entrada,$(x_1, x_2)$
• devuelve la respuesta como un entero, flotante (o un contenedor adecuado, por ejemplo, un vector o una lista, que contiene esta respuesta).

Su respuesta debe incluir (o vincular) todo el código necesario para verificar sus resultados, incluidos los pesos entrenados de su modelo.

Puntuación

La red neuronal con el menor número de pesos (incluidos los pesos de sesgo) gana.

¡Disfrutar!

21 13 11 9 pesas

Esto se basa en la identidad de polarización de las formas bilineales que en el caso real unidimensional se reduce a la identidad polinómica:

Entonces, y1solo calcula [x+y, x-y]usando una transformación lineal, y y3es solo el valor absoluto de y1como un paso de preprocesamiento para el siguiente: Luego, la parte "difícil" es calcular los cuadrados que explicaré a continuación, y después de eso simplemente calcular una diferencia y escalar qué Es de nuevo una operación lineal.

Para calcular los cuadrados utilizo una serie exponencial que debería ser precisa para todos los enteros dentro de alrededor de . Esta serie es de la forma$s$$\{0,1,2,\ldots,20\}$$0.5$

donde acabo de optimizar para los pesos W2( ). Toda esta aproximación comprende nuevamente solo dos transformaciones lineales con una activación exponencial intercalada en el medio. Este enfoque da como resultado una desviación máxima de aproximadamente .$=(w_i)_i$0.02

function p = net(x)
% 9 weights
one = 1; 
mone =-1;
zero = 0;
fourth = 0.25;
W1 = [1e-4, 2e-4];
W2  = [-199400468.100687;99700353.6313757];
b2 = 99700114.4299316;
leaky_relu = @(a,x)max(a*x,x); 


% Linear
y0 = [one, one; one, mone] * x;

% Linear + ReLU
y1 = mone * y0;
y2 = [leaky_relu(zero, y0), leaky_relu(zero, y1)];

% Linear
y3 = y2 * [one; one];

% Linear + exp
y4 = exp(y3 * W1); 

% Linear + Bias
y5 =  y4 * W2 + b2;

% Linear
y6 = [one, mone]*y5;
p = y6 * fourth;

end

Pruébalo en línea!

7 pesas

eps = 1e-6
c = 1 / (2 * eps * eps)

def f(A, B):
	e_s = exp(eps * A + eps * B)  # 2 weights, exp activation
	e_d = exp(eps * A - eps * B)  # 2 weights, exp activation
	return c * e_s + (-c) * e_d + (-1 / eps) * B  # 3 weights, linear activation

Pruébalo en línea!

Utiliza la siguiente igualdad aproximada para pequeño basado en la expansión de Taylor :$\epsilon$$e^x \approx 1 + x + \frac{x^2}{2}$

Elegir suficientemente pequeño nos lleva dentro de los límites de error requeridos. Tenga en cuenta que y son pesos constantes en el código.$\epsilon$epsc

33 31 pesos

# Activation functions
sub hard { $_[0] < -2.5 ? 0 : $_[0] > 2.5 ? 1 : 0.2 * $_[0] + 0.5 }
sub linear { $_[0] }

# Layer 0
sub inputA() { $a }
sub inputB() { $b }

# Layer 1
sub a15() { hard(5*inputA) }

# Layer 2
sub a8()  { hard(-5*inputA + 75*a15 - 37.5) }

# Layer 3
sub aa()  { linear(-5*inputA + 75*a15 - 40*a8) }

# Layer 4
sub a4()  { hard(aa - 17.5) }

# Layer 5
sub a2()  { hard(aa - 20*a4 - 7.5) }

# Layer 6
sub a1()  { linear(0.2*aa - 4*a4 - 2*a2) }

# Layer 7
sub b15() { hard(0.25*inputB - 5*a15) }
sub b8()  { hard(0.25*inputB - 5*a8) }
sub b4()  { hard(0.25*inputB - 5*a4) }
sub b2()  { hard(0.25*inputB - 5*a2) }
sub b1()  { hard(0.25*inputB - 5*a1) }

# Layer 8
sub output() { linear(-300*b15 + 160*b8 + 80*b4 + 40*b2 + 20*b1 - 10*inputA) }

# Test
for $a (-10..10) {
        for $b (-10..10) {
                die if abs($a * $b - output) >= 0.5;
        }
}

print "All OK";

Pruébalo en línea!

Esto hace una multiplicación larga en (más o menos) binario, y por lo tanto devuelve el resultado exacto. Debería ser posible aprovechar la ventana de error 0.5 para jugar golf un poco más, pero no estoy seguro de cómo.

Las capas 1 a 6 descomponen la primera entrada en 5 "bits". Por razones de golf, no utilizamos binarios reales. El "bit" más significativo tiene un peso de -15 en lugar de 16, y cuando la entrada es 0, todos los "bits" son 0.5 (que aún funciona bien, ya que conserva la identidad inputA = -15*a15 + 8*a8 + 4*a4 + 2*a2 + 1*a1).

43 pesas

Las dos soluciones publicadas hasta ahora han sido muy inteligentes, pero es probable que sus enfoques no funcionen para tareas más tradicionales en el aprendizaje automático (como OCR). Por lo tanto, me gustaría presentar una solución 'genérica' (sin trucos ingeniosos) para esta tarea que, con suerte, inspire a otras personas a mejorarla y dejarse atrapar por el mundo del aprendizaje automático:

Mi modelo es una red neuronal muy simple con 2 capas ocultas integradas en TensorFlow 2.0 (pero cualquier otro marco también funcionaría):

model = tf.keras.models.Sequential([
tf.keras.layers.Dense(6, activation='tanh', input_shape=(2,)),
tf.keras.layers.Dense(3, activation='tanh'),
tf.keras.layers.Dense(1, activation='linear')
])

Como puede ver, todas las capas son densas (lo que ciertamente no es óptimo), la función de activación es tanh (que en realidad podría estar bien para esta tarea), excepto la capa de salida que, debido a la naturaleza de esta tarea, Tiene una función de activación lineal.

Hay 43 pesos:

• $(2+1) \cdot 6 = 18$ entre la entrada y la primera capa oculta,
• $(6+1) \cdot 3 = 21$ entre las capas ocultas y
• $(3+1) \cdot 1 = 4$ conectando la última capa oculta y la capa de salida.

Los pesos se han entrenado (con un optimizador Adam) mediante un enfoque de ajuste por capas: primero se han ajustado para minimizar el error cuadrático medio no solo en la multiplicación de enteros entre y sino en las entradas en un vecindario determinado alrededor de estos valores . Esto da como resultado una convergencia mucho mejor debido a la naturaleza del descenso del gradiente. Y representó 400 épocas de entrenamiento en 57.600 muestras de entrenamiento cada una, utilizando un tamaño de lote de 32.$-10$$10$

A continuación, los he afinado, optimizando la desviación máxima en cualquiera de las tareas de multiplicación de enteros. Desafortunadamente, mis notas no muestran mucho ajuste fino que terminé haciendo, pero fue muy menor. Cerca de 100 épocas en esas 441 muestras de entrenamiento, con un tamaño de lote de 441.

Estos son los pesos con los que terminé:

[<tf.Variable 'dense/kernel:0' shape=(2, 6) dtype=float32, numpy=
 array([[ 0.10697944,  0.05394982,  0.05479664, -0.04538541,  0.05369904,
         -0.0728976 ],
        [ 0.10571832,  0.05576797, -0.04670485, -0.04466859, -0.05855528,
         -0.07390639]], dtype=float32)>,
 <tf.Variable 'dense/bias:0' shape=(6,) dtype=float32, numpy=
 array([-3.4242163, -0.8875816, -1.7694025, -1.9409281,  1.7825342,
         1.1364107], dtype=float32)>,
 <tf.Variable 'dense_1/kernel:0' shape=(6, 3) dtype=float32, numpy=
 array([[-3.0665843 ,  0.64912266,  3.7107112 ],
        [ 0.4914808 ,  2.1569328 ,  0.65417236],
        [ 3.461693  ,  1.2072319 , -4.181983  ],
        [-2.8746269 , -4.9959164 ,  4.505049  ],
        [-2.920127  , -0.0665407 ,  4.1409926 ],
        [ 1.3777553 , -3.3750365 , -0.10507642]], dtype=float32)>,
 <tf.Variable 'dense_1/bias:0' shape=(3,) dtype=float32, numpy=array([-1.376577  ,  2.8885336 ,  0.19852689], dtype=float32)>,
 <tf.Variable 'dense_2/kernel:0' shape=(3, 1) dtype=float32, numpy=
 array([[-78.7569  ],
        [-23.602606],
        [ 84.29587 ]], dtype=float32)>,
 <tf.Variable 'dense_2/bias:0' shape=(1,) dtype=float32, numpy=array([8.521169], dtype=float32)>]

que apenas alcanzó el objetivo de rendimiento establecido. La desviación máxima terminó siendo como lo atestigua .$0.44350433$$9 \cdot 10 = 90.443504$

Mi modelo se puede encontrar aquí y también puede probarlo en línea. en un entorno de Google Colab.

2 pesas

Me inspiraron las otras respuestas para aproximar la identidad de polarización de una manera diferente. Por cada pequeño , sostiene que$\epsilon>0$

Es suficiente tomar para este desafío.$\epsilon=0.01$

La implementación neta neta obvia de esta aproximación toma pesos en . Estos cuatro pesos se pueden reducir a tres factorizando . Como mencioné en un comentario anterior, cada red neuronal con pesos en la precisión de la máquina puede convertirse en una red neuronal (¡enorme!) Con solo dos pesos distintos. Apliqué este procedimiento para escribir el siguiente código MATLAB:$\{\pm\epsilon,\pm(4\epsilon^2)^{-1}\}$$\{\pm\epsilon,(4\epsilon^3)^{-1}\}$$\pm(4\epsilon^2)^{-1}=\pm\epsilon\cdot(4\epsilon^3)^{-1}$

function z=approxmultgolfed(x,y)

w1 = 0.1;   % first weight
w2 = -w1;   % second weight

k  = 250000;
v1 = w1*ones(k,1);
v2 = w2*ones(k,1);

L1 = w1*eye(2);
L2 = [ w1 w1; w2 w2; w1 w2; w2 w1 ];
L3 = [ v1 v1 v2 v2 ];
L4 = v1';

z = L4 * L3 * exp( L2 * L1 * [ x; y ] );

En total, esta red neuronal consta de 1.250.010 pesos, todos los cuales residen en .$\{\pm0.1\}$

Cómo escapar con solo 1 peso (!)

Resulta que puede simular cualquier red neuronal que tenga pesos en con una red neuronal más grande que solo tenga un peso, a saber, . De hecho, la multiplicación por se puede implementar como$\{\pm0.1\}$$-0.1$$0.1$

donde es el vector de columna de entradas, todas iguales a . Para las redes neuronales en las que la mitad de los pesos son positivos, esta transformación produce una red neuronal que es veces más grande.$w$$10$$-0.1$$10.5$

La obvia generalización de este procedimiento transformará cualquier red neuronal con pesos en en una red neuronal más grande con el peso simple . Combinado con el procedimiento en mi comentario anterior, por lo tanto, sostiene que cada red neuronal con pesas de precisión mecánica puede transformarse en una red neuronal de un solo peso.$\{\pm 10^{-k}\}$$-10^{-k}$

(Quizás deberíamos modificar cómo se puntúan los pesos reutilizados en futuros desafíos de golf de redes neuronales).