Machine Learning Golf: Multiplicación

68

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 .(x1,x2)x1x2x1,x21010

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. linear(x)=x ,
    2. softmax(x)i=exijexj ,
    3. seluα,β(x)={βx, if x>0αβ(ex1), otherwise ,
    4. softplus(x)=ln(ex+1) ,
    5. leaky-reluα(x)={x, if x<0αx, otherwise ,
    6. tanh(x) ,
    7. sigmoid(x)=exex+1 ,
    8. hard-sigmoid(x)={0, if x<2.51, if x>2.50.2x+0.5, otherwise ,
    9. ex
  • debe tomar como tupel / vector / list / ... de enteros o flotantes como su única entrada,(x1,x2)
  • 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!

Stefan Mesken
fuente
9
Bienvenido al sitio! Creo que este desafío podría beneficiar mucho de una definición más sólida de una red neuronal. Aquí hay un par de cosas 1) Sería muy bueno para usted decirlo en un lenguaje que no implique conocimiento de NNs 2) Realmente debería enumerar las funciones de activación en su publicación en lugar de vincular a una fuente externa ( los enlaces externos pueden cambiar o desaparecer).
Wheat Wizard
44
¿Podemos reutilizar pesos / usar capas convolucionales? (Recomiendo eliminar el bono, ya que no agrega nada al desafío y solo distrae del objetivo principal). ¿Se supone que los pesos son reales o pueden ser complejos?
flawr
44
Su redacción implica que los nodos de la capa 3 no pueden usar entradas de la capa 1. ¿Cuesta un peso tener un nodo de la capa 2 simplemente haciendo f(x) = xreenviar su entrada?
Grimmy
44
Debe haber un enlace en la columna derecha al Sandbox, que fue creado expresamente para solucionar este tipo de problemas antes de que la pregunta se publique en el sitio principal. Y la filosofía de la red es que es mejor cerrar una pregunta, arreglarla y volver a abrirla que obtener un montón de respuestas que no tendrán sentido una vez que la pregunta se haya solucionado o que limiten estrictamente los cambios que se pueden hacer a la pregunta. .
Peter Taylor
77
De ningún modo. Este tipo de problemas son detectados por la experiencia de muchos años de ver a otras personas cometer el mismo tipo de errores. Algunas ambigüedades pasan desapercibidas, pero hay muchas más atrapadas allí. Y esto definitivamente se habría captado, porque como se indicó en mi primer comentario, tuvimos exactamente los mismos problemas con una pregunta sobre la red neuronal hace dos meses.
Peter Taylor

Respuestas:

37

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:

xy=(x+y)2(xy)24

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 formas{0,1,2,,20}0.5

approx_square(x)=i=02wiexp(0.0001ix)

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 .=(wi)i0.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!

falla
fuente
Creo que su código de verificación en el pie de página del enlace TIO pierde una aplicación de abs. Pero todo está bien de todos modos.
Christian Sievers
@ChristianSievers ¡Gracias, actualicé el enlace TIO!
falla
No soy un experto en NN, por curiosidad, ¿cómo se hace el conteo de peso? y0necesita 4, y1necesita 2, y3necesita 2, y4necesita 1, y5necesita 1 y y6necesita 2. ¿Eso es 12?
Margaret Bloom
3
@MargaretBloom Sí, esto es realmente un poco inusual, pero el OP dijo en los comentarios que podemos reutilizar pesas y solo tenemos que contarlas una vez, incluso si usamos el mismo peso varias veces. Entonces, todos los pesos que estoy usando se definen en la primera parte de la función.
falla
31

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 :ϵex1+x+x22

ABeϵA+ϵBeϵAϵB2ϵ2Bϵ

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.ϵepsc

xnor
fuente
1
No estoy seguro de que esto cuente como una 'red neuronal tradicional' (regla n. ° 1), pero es obvio que puede reformatearse en una, así que no veo ningún problema con eso. Buena solución!
Stefan Mesken
1
Puede definir C = -B(1 peso) y luego tener [e_s, e_d] = conv([A,B,C], [eps, eps])(2 pesos) para ahorrar un peso :) (Por cierto: ¡Un enfoque muy inteligente!)
error
(Se me olvidó añadir el exp)
flawr
44
Incluso puede bajar mucho reutilizando los pesos : no tiene que contar el mismo peso varias veces.
falla
2
@flawr Ese es un buen truco, pero creo que las posibilidades de convolución y reutilización de pesos en los comentarios hacen que este sea un desafío tan diferente que voy a mantener esta respuesta tal como está.
xnor
22

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

Mugriento
fuente
1
Esperaba que a alguien se le ocurriera un algoritmo de multiplicación codificado en ANN. Pero no pensé que sería la primera respuesta. ¡Bien hecho! (También estoy ansioso por ver si podrá lograr algo como esto con el conjunto de datos MNIST o algún otro problema de ML más relajado: D.)
Stefan Mesken
14

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)6=18 entre la entrada y la primera capa oculta,
  • (6+1)3=21 entre las capas ocultas y
  • (3+1)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.1010

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.44350433910=90.443504

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

Stefan Mesken
fuente
6

2 pesas

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

xyeϵx+ϵy+eϵxϵyeϵxϵyeϵx+ϵy4ϵ2.

Es suficiente tomar para este desafío.ϵ=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:{±ϵ,±(4ϵ2)1}{±ϵ,(4ϵ3)1}±(4ϵ2)1=±ϵ(4ϵ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 .{±0.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{±0.1}0.10.1

0.1x=wwx,

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.w100.110.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.{±10k}10k

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

Dustin G. Mixon
fuente