El reto
Encuentre la red neuronal feedforward más pequeña de manera que, dado cualquier vector de entrada tridimensional con entradas enteras en , la red genera la raíz más grande (es decir, "más positiva") de la raíz polinomio con error estrictamente menor que .
Admisibilidad
La noción de admisibilidad en mi anterior desafío de golf de red neuronal parecía un poco restrictivo, por lo que para este desafío, estamos utilizando una definición más liberal de red neuronal de alimentación directa:
Una neurona es una función que se especifica mediante un vector de pesos , un sesgo , y una función de activación de la siguiente manera:
Una red neuronal de alimentación directa con nodos de entrada es una función de que se puede construir a partir de una secuencia de neuronas, donde cada toma entradas de y genera un escalar . Dado un conjunto específico de nodos de salida , entonces la salida de la red neuronal es el vector .
Dado que las funciones de activación pueden ajustarse para cualquier tarea dada, necesitamos restringir la clase de funciones de activación para mantener este desafío interesante. Se permiten las siguientes funciones de activación:
Identidad.
ReLU.
SoftPlus.
Sigmoideo.
Sinusoide.
En general, una red neuronal admisible se especifica mediante nodos de entrada, una secuencia de neuronas y nodos de salida, mientras que cada neurona se especifica mediante un vector de pesos, un sesgo y una función de activación de la lista anterior. Por ejemplo, la siguiente red neuronal es admisible, aunque no cumple con el objetivo de rendimiento de este desafío:
Nodos de entrada:
Neuronas: para
Nodos de salida:
Esta red consta de 8 neuronas, cada una con sesgo cero y activación de identidad. En palabras, esta red calcula la secuencia generalizada de Fibonacci generada por y y luego genera los números 5, 9 y 10 de esta secuencia, en ese orden.
Puntuación
Dado un número real con terminación de expansión decimal, sea el número entero no negativo más pequeño para el cual , y sea el número entero no negativo más pequeño para cuál es entero. Entonces decimos que es la precisión de .x
Por ejemplo, tiene una precisión de , mientras que tiene una precisión de .
Su puntaje es la suma de las precisiones de los pesos y sesgos en su red neuronal.
(Por ejemplo, el ejemplo anterior tiene una puntuación de 16).
Verificación
Si bien las raíces se pueden expresar en términos de la fórmula cúbica , la raíz más grande es quizás más fácilmente accesible por medios numéricos. Siguiendo la sugerencia de @ xnor, calculé la raíz más grande para cada elección de enteros , y los resultados se pueden encontrar aquí . Cada línea de este archivo de texto tiene la forma . Por ejemplo, la primera línea informa que la raíz más grande de es aproximadamente .x 3 - 10 x 2 - 10 x - 10 10.99247140445449a,b,c,root
Editar: el archivo original que publiqué tenía errores en los casos en que el polinomio exhibía una raíz múltiple. La versión actual debe estar libre de tales errores.
fuente
a=0
y el cuadrático tiene dos raíces complejas?a
un valor distinto de cero, o incluso solo 1. Además, recomendaría poner algunos casos de prueba, dando raíces a una alta precisión para que podamos verificar que los nuestros estén dentro de 0.1. También sería bueno tener salidas para todas las entradas posibles, probablemente en un enlace, ya que eso es mucho para la publicación.x -> a * sin(b * softplus(x) + c)
puede sobreajustar cualquier número finito de puntos de datos conx
una precisión de entero a arbitraria utilizando una frecuencia extremadamente grande y precisa.Respuestas:
146740006675.436.0505.403.44810.3855.9944.4473.806 total precisión
Para una línea de base, investigué el siguiente enfoque: Seleccione modo que si tomamos muestras del polinomio enM,δ,ϵ>0 p(x)=x3+ax2+bx+c
entonces el punto de muestra más grande satisface necesariamente existe y reside necesariamente dentro de de la raíz más grande de . Se puede demostrar que para nuestra colección de polinomios, se puede tomar , y .s⋆∈S p(s⋆)<ϵ 0.1 p M=11 δ=0.1 ϵ=10−4
Diseñar una red neuronal que implementa esta lógica, que comienzan con una capa de neuronas que muestra el polinomio de . Para cada , tomamosS s∈S
A continuación, identificamos cuáles de estos son menores que . Resulta que para , mantiene que solo si . Como tal, podemos usar activaciones relu para identificar exactamente nuestras muestras:ϵ=10−4 s∈S p(s)<10−4 p(s)≤0
Implementamos esto con unas pocas capas de neuronas:
En este punto, tenemos cuando , y de lo contrario . Recuerde que buscamos la más grande para la cual . Para este fin, etiquetamos como (por conveniencia de notación), y para cada , definimos iterativamentex4,s=1 p(s)<10−4 x4,s=0 s⋆ x4,s⋆=1 x4,M x5,M k≥1
Gracias a esta transformación, cada es un número entero no negativo, y es la única para la cual . Ahora podemos identificar por otra aplicación de activaciones relu:x5,s s⋆ s x5,s=1 s⋆
Explícitamente, definimos las neuronas por
Entonces si y de lo contrario . Los combinamos linealmente para producir nuestro nodo de salida:x8,s=1 s=s⋆ x8,s=0
Para la puntuación, cada capa tiene neuronas con diferentes niveles de precisión: (1) , (2) , (3) , (4) , (5) , (6) , (7) , (8) , (9). Además, todas menos dos de las capas tienen neuronas; la capa 5 tiene neuronas y la capa 9 tiene neurona.6+3+1+9=19 1+4=5 1 5+5=10 1+1=2 1+1=2 1+1=2 1+1+1=3 3|S| |S|=221 |S|−1 1
Editar: Mejoras: (1) Podemos muestrear el polinomio de manera mucho más eficiente usando diferencias finitas. (2) Podemos pasar por alto las capas 2 a 4 usando una activación sigmoidea. (3) Los problemas de desbordamiento en la capa 5 se pueden evitar (y las capas posteriores se pueden combinar) aplicando más cuidadosamente las activaciones de relu. (4) La suma final es más barata con la suma por partes .
Lo que sigue es el código MATLAB. Para ser claros,
prec
es una función (que se encuentra aquí ) que calcula la precisión de un vector de pesos o sesgos.fuente
53.26829.59629.306 total precisiónLa comunicación privada con @ A.Rex condujo a esta solución, en la que construimos una red neuronal que memoriza las respuestas. La idea central es que cada función sobre un conjunto finito disfruta de la descomposiciónf:S→R S
Como tal, se puede construir una implementación de red neural de transformando primero la entrada en una función indicadora de la entrada, y luego combinándola linealmente usando las salidas deseadas como pesos. Además, las activaciones de relu hacen posible esta transformación:f
Lo que sigue es una implementación de MATLAB de este enfoque. Para ser claros,
roots.txt
es el archivo raíz publicado anteriormente (que se encuentra aquí ), yprec
es una función (que se encuentra aquí ) que calcula la precisión total de un vector de pesos o sesgos.Edición 1: Dos mejoras sobre el original: (1) Factoré algunas neuronas fuera de los bucles for. (2) Implementé la " integración de Lebesgue " en la suma final combinando primero los términos del mismo conjunto de niveles. De esta manera, pago el valor de mayor precisión de una salida solo una vez cada nivel establecido. Además, es seguro redondear las salidas al quinto más cercano mediante el teorema de la raíz racional .
Edición 2: Mejoras menores adicionales: (1) Factoré más neuronas a partir de un bucle for. (2) No me molesto en calcular el término en la suma final para la cual el resultado ya es cero.
fuente