Normalización por lotes

En una red neuronal, la normalización por lotes se logra mediante un paso de normalización que fija las medias y varianzas de las entradas de cada capa. Idealmente, la normalización se realizaría sobre todo el conjunto de entrenamiento, pero para utilizar este paso junto con métodos de optimización estocástica , resulta poco práctico usar la información global. Por lo tanto, la normalización se limita a cada minilote en el proceso de entrenamiento.

Usemos B para denotar un mini-lote de tamaño m del conjunto de entrenamiento completo. La media y la varianza empíricas de B podrían denotarse como

${\displaystyle \mu _{B}={\frac {1}{m}}\sum _{i=1}^{m}x_{i}}$y${\displaystyle \sigma _{B}^{2}={\frac {1}{m}}\sum _{i=1}^{m}(x_{i}-\mu _{B})^{2}}$.

Para una capa de la red con entrada d- dimensional,${\displaystyle x=(x^{(1)},...,x^{(d)})}$, cada dimensión de su entrada se normaliza (es decir, se recentra y se reescala) por separado,

${\displaystyle {\hat {x}}_{i}^{(k)}={\frac {x_{i}^{(k)}-\mu _{B}^{(k)}}{\sqrt {\left(\sigma _{B}^{(k)}\right)^{2}+\epsilon }}}}$, dónde${\displaystyle k\in [1,d]}$y ${\displaystyle i\in [1,m]}$;${\displaystyle \mu _{B}^{(k)}}$y${\displaystyle \sigma _{B}^{(k)}}$son la media y la desviación estándar por dimensión, respectivamente.

${\displaystyle \epsilon }$se agrega en el denominador para la estabilidad numérica y es una constante positiva arbitrariamente pequeña. La activación normalizada resultante${\displaystyle {\sombrero {x}}^{(k)}}$tienen media cero y varianza unitaria, si${\displaystyle \epsilon }$no se tiene en cuenta. Para restaurar el poder de representación de la red, sigue un paso de transformación como

${\displaystyle y_{i}^{(k)}=\gamma ^{(k)}{\hat {x}}_{i}^{(k)}+\beta ^{(k)}}$,

donde los parámetros${\displaystyle \gamma ^{(k)}}$y${\displaystyle \beta ^{(k)}}$Posteriormente se aprenden en el proceso de optimización.

Formalmente, la operación que implementa la normalización por lotes es una transformación${\displaystyle BN_{\gamma ^{(k)},\beta ^{(k)}}:x_{1...m}^{(k)}\rightarrow y_{1...m}^{(k)}}$llamada transformación de normalización por lotes. La salida de la transformación BN${\displaystyle y^{(k)}=BN_{\gamma ^{(k)},\beta ^{(k)}}(x^{(k)})}$Luego se pasa a otras capas de la red, mientras que la salida normalizada ${\displaystyle {\hat {x}}_{i}^{(k)}}$permanece dentro de la capa actual.

La transformada BN descrita es una operación diferenciable , y el gradiente de la pérdida${\displaystyle l}$ con respecto a los diferentes parámetros se pueden calcular directamente con la regla de la cadena .

Específicamente,${\displaystyle {\frac {\partial l}{\partial y_{i}^{(k)}}}}$depende de la elección de la función de activación , y el gradiente frente a otros parámetros podría expresarse como una función de${\displaystyle {\frac {\partial l}{\partial y_{i}^{(k)}}}}$:

${\displaystyle {\frac {\partial l}{\partial {\hat {x}}_{i}^{(k)}}}={\frac {\partial l}{\partial y_{i}^{(k)}}}\gamma ^{(k)}}$,

${\displaystyle {\frac {\partial l}{\partial \gamma ^{(k)}}}=\sum _{i=1}^{m}{\frac {\partial l}{\partial y_{i}^{(k)}}}{\hat {x}}_{i}^{(k)}}$,${\displaystyle {\frac {\partial l}{\partial \beta ^{(k)}}}=\sum _{i=1}^{m}{\frac {\partial l}{\partial y_{i}^{(k)}}}}$,${\displaystyle {\frac {\partial l}{\partial \sigma _{B}^{(k)^{2}}}}=\sum _{i=1}^{m}{\frac {\partial l}{\partial y_{i}^{(k)}}}(x_{i}^{(k)}-\mu _{B}^{(k)})\left(-{\frac {\gamma ^{(k)}}{2}}(\sigma _{B}^{(k)^{2}}+\epsilon )^{-3/2}\right)}$,${\displaystyle {\frac {\partial l}{\partial \mu _{B}^{(k)}}}=\sum _{i=1}^{m}{\frac {\partial l}{\partial y_{i}^{(k)}}}{\frac {-\gamma ^{(k)}}{\sqrt {\sigma _{B}^{(k)^{2}}+\epsilon }}}+{\frac {\partial l}{\partial \sigma _{B}^{(k)^{2}}}}{\frac {1}{m}}\sum _{i=1}^{m}(-2)\cdot (x_{i}^{(k)}-\mu _{B}^{(k)})}$,

y${\displaystyle {\frac {\partial l}{\partial x_{i}^{(k)}}}={\frac {\partial l}{\partial {\hat {x}}_{i}^{(k)}}}{\frac {1}{\sqrt {\sigma _{B}^{(k)^{2}}+\epsilon }}}+{\frac {\partial l}{\partial \sigma _{B}^{(k)^{2}}}}{\frac {2(x_{i}^{(k)}-\mu _{B}^{(k)})}{m}}+{\frac {\partial l}{\partial \mu _{B}^{(k)}}}{\frac {1}{m}}}$.

Durante la etapa de entrenamiento, los pasos de normalización dependen de los minilotes para garantizar un entrenamiento eficiente y confiable. Sin embargo, en la etapa de inferencia, esta dependencia ya no es útil. En cambio, el paso de normalización en esta etapa se calcula con las estadísticas de la población de tal manera que la salida podría depender de la entrada de manera determinista. La media de la población,${\displaystyle E[x^{(k)}]}$y varianza,${\displaystyle \operatorname {Var} [x^{(k)}]}$, se calculan como:

${\displaystyle E[x^{(k)}]=E_{B}[\mu _{B}^{(k)}]}$, y${\displaystyle \operatorname {Var} [x^{(k)}]={\frac {m}{m-1}}E_{B}[\left(\sigma _{B}^{(k)}\right)^{2}]}$.

Por lo tanto, las estadísticas de población constituyen una representación completa de los minilotes.

La transformación BN en el paso de inferencia se convierte así en:

${\displaystyle y^{(k)}=BN_{\gamma ^{(k)},\beta ^{(k)}}^{\text{inf}}(x^{(k)})=\gamma ^{(k)}{\frac {x^{(k)}-E[x^{(k)}]}{\sqrt {\operatorname {Var} [x^{(k)}]+\epsilon }}}+\beta ^{(k)}}$,

dónde${\displaystyle y^{(k)}}$se pasa a las siguientes capas en lugar de${\displaystyle x^{(k)}}$Dado que los parámetros son fijos en esta transformación, el procedimiento de normalización por lotes consiste esencialmente en aplicar una transformación lineal a la función de activación.

Una explicación alternativa ^{[ 5 ]} es que la mejora con la normalización por lotes se debe en cambio a la producción de un espacio de parámetros más suave y gradientes más suaves, como se formaliza mediante una constante de Lipschitz más pequeña .

Consideremos dos redes idénticas, una contiene capas de normalización por lotes y la otra no; luego se comparan los comportamientos de estas dos redes. Denotemos las funciones de pérdida como${\displaystyle {\hat {L}}}$y${\displaystyle L}$, respectivamente. Sea la entrada a ambas redes${\displaystyle x}$y la salida sea${\displaystyle y}$, para el cual${\displaystyle y=Wx}$, dónde${\displaystyle W}$son los pesos de la capa. Para la segunda red,${\displaystyle y}$Además, pasa por una capa de normalización por lotes. Denotemos la activación normalizada como${\displaystyle {\hat {y}}}$, que tiene media cero y varianza unitaria. Sea la activación transformada${\displaystyle z=\gamma {\hat {y}}+\beta }$y supongamos que${\displaystyle \gamma }$y${\displaystyle \beta }$son constantes. Finalmente, denotemos la desviación estándar sobre un minilote.${\displaystyle {\hat {y_{j}}}\in \mathbb {R} ^{m}}$como${\displaystyle \sigma _{j}}$.

Primero, se puede demostrar que la magnitud del gradiente de una red normalizada por lotes,${\displaystyle ||\triangledown _{y_{i}}{\hat {L}}||}$, está acotado, con el límite expresado como

${\displaystyle ||\triangledown _{y_{i}}{\hat {L}}||^{2}\leq {\frac {\gamma ^{2}}{\sigma _{j}^{2}}}{\Bigg (}||\triangledown _{y_{i}}L||^{2}-{\frac {1}{m}}\langle 1,\triangledown _{y_{i}}L\rangle ^{2}-{\frac {1}{m}}\langle \triangledown _{y_{i}}L,{\hat {y}}_{j}\rangle ^{2}{\bigg )}}$.

Dado que la magnitud del gradiente representa la Lipschitzidad de la pérdida, esta relación indica que una red normalizada por lotes podría lograr una Lipschitzidad comparativamente mayor. Nótese que el límite se vuelve más ajustado cuando el gradiente${\displaystyle \triangledown _{y_{i}}{\hat {L}}}$se correlaciona con la activación${\displaystyle {\hat {y_{i}}}}$, que es un fenómeno común. La escala de${\displaystyle {\frac {\gamma ^{2}}{\sigma _{j}^{2}}}}$Esto también es significativo, ya que la varianza suele ser grande.

En segundo lugar, la forma cuadrática del hessiano de pérdida con respecto a la activación en la dirección del gradiente puede acotarse como

${\displaystyle (\triangledown _{y_{j}}{\hat {L}})^{T}{\frac {\partial {\hat {L}}}{\partial y_{j}\partial y_{j}}}(\triangledown _{y_{j}}{\hat {L}})\leq {\frac {\gamma ^{2}}{\sigma ^{2}}}{\bigg (}{\frac {\partial {\hat {L}}}{\partial y_{j}}}{\bigg )}^{T}{\bigg (}{\frac {\partial L}{\partial y_{j}\partial y_{j}}}{\bigg )}{\bigg (}{\frac {\partial {\hat {L}}}{\partial y_{j}}}{\bigg )}-{\frac {\gamma }{m\sigma ^{2}}}\langle \triangledown _{y_{j}}L,{\hat {y_{j}}}\rangle {\bigg |}{\bigg |}{\frac {\partial {\hat {L}}}{\partial y_{j}}}{\bigg |}{\bigg |}^{2}}$.

La escala de${\displaystyle {\frac {\gamma ^{2}}{\sigma _{j}^{2}}}}$indica que el hessiano de la pérdida es resistente a la varianza del mini-lote, mientras que el segundo término del lado derecho sugiere que se vuelve más suave cuando el hessiano y el producto interno no son negativos. Si la pérdida es localmente convexa , entonces el hessiano es semidefinido positivo , mientras que el producto interno es positivo si${\displaystyle {\hat {g_{j}}}}$se dirige hacia el mínimo de la pérdida. Por lo tanto, de esta desigualdad se podría concluir que el gradiente generalmente se vuelve más predictivo con la capa de normalización por lotes.

A continuación, se procede a traducir los límites relacionados con la pérdida respecto a la activación normalizada a un límite para la pérdida respecto a los pesos de la red:

${\displaystyle {\hat {g_{j}}}\leq {\frac {\gamma ^{2}}{\sigma _{j}^{2}}}(g_{j}^{2}-m\mu _{g_{j}}^{2}-\lambda ^{2}\langle \triangledown _{y_{j}}L,{\hat {y}}_{j}\rangle ^{2})}$, dónde${\displaystyle g_{j}=max_{||X||\leq \lambda }||\triangledown _{W}L||^{2}}$y${\displaystyle {\hat {g}}_{j}=max_{||X||\leq \lambda }||\triangledown _{W}{\hat {L}}||^{2}}$.

Además de un paisaje más uniforme, se demuestra que la normalización por lotes podría resultar en una mejor inicialización con la siguiente desigualdad:

${\displaystyle ||W_{0}-{\hat {W}}^{*}||^{2}\leq ||W_{0}-W^{*}||^{2}-{\frac {1}{||W^{*}||^{2}}}(||W^{*}||^{2}-\langle W^{*},W_{0}\rangle )^{2}}$, dónde${\displaystyle W^{*}}$y${\displaystyle {\hat {W}}^{*}}$son los pesos óptimos locales para las dos redes, respectivamente.

Algunos investigadores argumentan que el análisis anterior no puede capturar completamente el rendimiento de la normalización por lotes, ya que la demostración solo considera el autovalor más grande, o equivalentemente, una dirección en el paisaje en todos los puntos. Se sugiere que es necesario tener en cuenta el espectro de autovalores completo para realizar un análisis concluyente. ^{[ 8 ] [ 5 ]}

Dado que se hipotetiza que las capas de normalización por lotes podrían reducir el desplazamiento interno de covariables, se diseñó un experimento para medir cuantitativamente dicha reducción. En primer lugar, es necesario definir matemáticamente el concepto de desplazamiento interno de covariables. Específicamente, para cuantificar el ajuste que realizan los parámetros de una capa en respuesta a las actualizaciones de las capas anteriores, se mide la correlación entre los gradientes de la función de pérdida antes y después de que se actualicen todas las capas anteriores, ya que los gradientes podrían capturar los cambios derivados del método de entrenamiento de primer orden. Si el desplazamiento introducido por las modificaciones en las capas anteriores es pequeño, la correlación entre los gradientes sería cercana a 1.

Se calcula la correlación entre los gradientes para cuatro modelos: una red VGG estándar , ^{[ 6 ]} una red VGG con capas de normalización por lotes, una red lineal profunda (DLN) de 25 capas entrenada con descenso de gradiente por lotes completos y una red DLN con capas de normalización por lotes. Curiosamente, se muestra que los modelos VGG estándar y DLN tienen correlaciones de gradientes más altas en comparación con sus contrapartes, lo que indica que las capas adicionales de normalización por lotes no reducen el desplazamiento de covariables internas.

Aunque la normalización por lotes se introdujo originalmente para aliviar los problemas de desaparición o explosión del gradiente , una red de normalización por lotes profunda sufre de hecho una explosión del gradiente en el momento de la inicialización, independientemente de lo que utilice para la no linealidad. Por lo tanto, el panorama de optimización está muy lejos de ser suave para una red de normalización por lotes profunda inicializada aleatoriamente. Más precisamente, si la red tiene${\displaystyle L}$capas, entonces el gradiente de los pesos de la primera capa tiene norma${\displaystyle >c\lambda ^{L}}$para algunos${\displaystyle \lambda >1,c>0}$dependiendo únicamente de la no linealidad. Para cualquier no linealidad fija,${\displaystyle \lambda }$disminuye a medida que aumenta el tamaño del lote. Por ejemplo, para ReLU,${\displaystyle \lambda }$disminuye a${\displaystyle \pi /(\pi -1)\approx 1.467}$a medida que el tamaño del lote tiende a infinito. En la práctica, esto significa que las redes de normalización de lotes profundas son imposibles de entrenar. Esto solo se soluciona mediante conexiones de salto al estilo de las redes residuales . ^{[ 9 ]}

Esta explosión de gradiente en la superficie contradice la propiedad de suavidad explicada en la sección anterior, pero en realidad son consistentes. La sección anterior estudia el efecto de insertar una única norma de lote en una red, mientras que la explosión de gradiente depende del apilamiento de normas de lote típicas de las redes neuronales profundas modernas.

Otra posible razón del éxito de la normalización por lotes es que desacopla la longitud y la dirección de los vectores de peso y, por lo tanto, facilita un mejor entrenamiento.

Al interpretar la normalización por lotes como una reparametrización del espacio de pesos, se puede demostrar que la longitud y la dirección de los pesos están separadas y, por lo tanto, se pueden entrenar por separado. Para una unidad de red neuronal particular con entrada${\displaystyle x}$y vector de peso${\displaystyle w}$, denotamos su salida como${\displaystyle f(w)=E_{x}[\phi (x^{T}w)]}$, dónde${\displaystyle \phi }$es la función de activación, y denotamos${\displaystyle S=E[xx^{T}]}$. Supongamos que${\displaystyle E[x]=0}$y que el espectro de la matriz${\displaystyle S}$está limitado como${\displaystyle 0<\mu =\lambda _{min}(S)}$,${\displaystyle L=\lambda _{max}(S)<\infty }$, de tal manera que${\displaystyle S}$es simétrica definida positiva. Agregar normalización por lotes a esta unidad da como resultado:

${\displaystyle f_{BN}(w,\gamma ,\beta )=E_{x}[\phi (BN(x^{T}w))]=E_{x}{\bigg [}\phi {\bigg (}\gamma ({\frac {x^{T}w-E_{x}[x^{T}w]}{var_{x}[x^{T}w]^{1/2}}})+\beta {\bigg )}{\bigg ]}}$, por definición.

El término de varianza se puede simplificar de tal manera que${\displaystyle var_{x}[x^{T}w]=w^{T}Sw}$. Supongamos que${\displaystyle x}$tiene media cero y${\displaystyle \beta }$puede omitirse, entonces se deduce que

${\displaystyle f_{BN}(w,\gamma )=E_{x}{\bigg [}\phi {\bigg (}\gamma {\frac {x^{T}w}{(w^{T}Sw)^{1/2}}}{\bigg )}{\bigg ]}}$, dónde${\displaystyle (w^{T}Sw)^{\frac {1}{2}}}$es la norma inducida de${\displaystyle S}$,${\displaystyle ||w||_{s}}$.

Por lo tanto, se podría concluir que${\displaystyle f_{BN}(w,\gamma )=E_{x}[\phi (x^{T}{\tilde {w}})]}$, dónde${\displaystyle {\tilde {w}}=\gamma {\frac {w}{||w||_{s}}}}$, y${\displaystyle \gamma }$y${\displaystyle w}$Consideremos su longitud y dirección por separado. Esta propiedad podría utilizarse para demostrar la convergencia más rápida de problemas con normalización por lotes.

Con la interpretación de la reparametrización, se podría demostrar que aplicar la normalización por lotes al problema de mínimos cuadrados ordinarios logra una tasa de convergencia lineal en el descenso de gradiente, que es más rápida que el descenso de gradiente regular con una convergencia sublineal.

Denotemos el objetivo de minimizar un problema de mínimos cuadrados ordinarios como

${\displaystyle \min _{{\tilde {w}}\in R^{d}}f_{OLS}({\tilde {w}})=\min _{{\tilde {w}}\in R^{d}}(E_{x,y}[(y-x^{T}{\tilde {w}})^{2}])=\min _{{\tilde {w}}\in R^{d}}(2u^{T}{\tilde {w}}+{\tilde {w}}^{T}S{\tilde {w}})}$, dónde${\displaystyle u=E[-yx]}$y${\displaystyle S=E[xx^{T}]}$.

Desde${\displaystyle {\tilde {w}}=\gamma {\frac {w}{||w||_{s}}}}$, el objetivo se convierte así en

${\displaystyle \min _{w\in R^{d}\backslash \{0\},\gamma \in R}f_{OLS}(w,\gamma )=\min _{w\in R^{d}\backslash \{0\},\gamma \in R}{\bigg (}2\gamma {\frac {u^{T}w}{||w||_{S}+\gamma ^{2}}}{\bigg )}}$donde se excluye el 0 para evitar que haya 0 en el denominador.

Dado que el objetivo es convexo con respecto a${\displaystyle \gamma }$, su valor óptimo podría calcularse estableciendo la derivada parcial de la función objetivo frente a${\displaystyle \gamma }$a 0. El objetivo podría simplificarse aún más a ser

${\displaystyle \min _{w\in R^{d}\backslash \{0\}}\rho (w)=\min _{w\in R^{d}\backslash \{0\}}{\bigg (}-{\frac {w^{T}uu^{T}w}{w^{T}Sw}}{\bigg )}}$.

Nótese que esta función objetivo es una forma del cociente de Rayleigh generalizado.

${\displaystyle {\tilde {\rho }}(w)={\frac {w^{T}Bw}{w^{T}Aw}}}$, dónde${\displaystyle B\in R^{d\times d}}$es una matriz simétrica y${\displaystyle A\in R^{d\times d}}$es una matriz simétrica definida positiva .

Se demuestra que la tasa de convergencia del descenso de gradiente del cociente de Rayleigh generalizado es

${\displaystyle {\frac {\lambda _{1}-\rho (w_{t+1})}{\rho (w_{t+1}-\lambda _{2})}}\leq {\bigg (}1-{\frac {\lambda _{1}-\lambda _{2}}{\lambda _{1}-\lambda _{min}}}{\bigg )}^{2t}{\frac {\lambda _{1}-\rho (w_{t})}{\rho (w_{t})-\lambda _{2}}}}$, dónde${\displaystyle \lambda _{1}}$es el mayor valor propio de${\displaystyle B}$,${\displaystyle \lambda _{2}}$es el segundo valor propio más grande de${\displaystyle B}$, y${\displaystyle \lambda _{min}}$es el valor propio más pequeño de${\displaystyle B}$. ^{[ 10 ]}

En nuestro caso,${\displaystyle B=uu^{T}}$es una matriz de rango uno, y el resultado de convergencia se puede simplificar en consecuencia. Específicamente, consideremos pasos de descenso de gradiente de la forma${\displaystyle w_{t+1}=w_{t}-\eta _{t}\triangledown \rho (w_{t})}$con tamaño de paso${\displaystyle \eta _{t}={\frac {w_{t}^{T}Sw_{t}}{2L|\rho (w_{t})|}}}$y comenzando desde${\displaystyle \rho (w_{0})\neq 0}$, entonces

${\displaystyle \rho (w_{t})-\rho (w^{*})\leq {\bigg (}1-{\frac {\mu }{L}}{\bigg )}^{2t}(\rho (w_{0})-\rho (w^{*}))}$.

El problema del aprendizaje de semiplanos se refiere al entrenamiento del perceptrón , que es la forma más simple de red neuronal. El problema de optimización en este caso es

${\displaystyle \min _{{\tilde {w}}\in R^{d}}f_{LH}({\tilde {w}})=E_{y,x}[\phi (z^{T}{\tilde {w}})]}$, dónde${\displaystyle z=-yx}$y${\displaystyle \phi }$es una función de pérdida arbitraria.

Supongamos que${\displaystyle \phi }$es infinitamente diferenciable y tiene una derivada acotada. Supongamos que la función objetivo${\displaystyle f_{LH}}$es${\displaystyle \zeta }$- suave , y esa es una solución${\displaystyle \alpha ^{*}=argmin_{\alpha }||\triangledown f(\alpha w)||^{2}}$existe y está acotado de tal manera que${\displaystyle -\infty <\alpha ^{*}<\infty }$También supongamos${\displaystyle z}$es una variable aleatoria normal multivariada . Con la suposición gaussiana, se puede demostrar que todos los puntos críticos se encuentran en la misma línea, para cualquier elección de función de pérdida.${\displaystyle \phi }$. Específicamente, el gradiente de${\displaystyle f_{LH}}$podría representarse como

${\displaystyle \triangledown _{\tilde {w}}f_{LH}({\tilde {w}})=c_{1}({\tilde {w}})u+c_{2}({\tilde {w}})S{\tilde {w}}}$, dónde ${\displaystyle c_{1}({\tilde {w}})=E_{z}[\phi ^{(1)}(z^{T}{\tilde {w}})]-E_{z}[\phi ^{(2)}(z^{T}{\tilde {w}})](u^{T}{\tilde {w}})}$,${\displaystyle c_{2}({\tilde {w}})=E_{z}[\phi ^{(2)}(z^{T}{\tilde {w}})]}$, y${\displaystyle \phi ^{(i)}}$es el${\displaystyle i}$-ésima derivada de${\displaystyle \phi }$.

Al establecer el gradiente en 0, se deduce que los puntos críticos acotados${\displaystyle {\tilde {w}}_{*}}$puede expresarse como${\displaystyle {\tilde {w}}_{*}=g_{*}S^{-1}u}$, dónde${\displaystyle g_{*}}$depende de${\displaystyle {\tilde {w}}_{*}}$y${\displaystyle \phi }$Al combinar esta propiedad global con el desacoplamiento de la dirección de la longitud, se podría demostrar que este problema de optimización converge linealmente.

En primer lugar, se diseña una variación del descenso de gradiente con normalización por lotes, el Descenso de Gradiente en Parametrización Normalizada (GDNP), para la función objetivo.${\displaystyle \min _{w\in R^{d}\backslash \{0\},\gamma \in R}f_{LH}(w,\gamma )}$, de modo que la dirección y la longitud de los pesos se actualizan por separado. Denotemos el criterio de parada de GDNP como

${\displaystyle h(w_{t},\gamma _{t})=E_{z}[\phi '(z^{T}{\tilde {w}}_{t})](u^{T}w_{t})-E_{z}[\phi ''(z^{T}{\tilde {w}}_{t})](u^{T}w_{t})^{2}}$.

Sea el tamaño del paso

${\displaystyle s_{t}=s(w_{t},\gamma _{t})=-{\frac {||w_{t}||_{S}^{3}}{Lg_{t}h(w_{t},\gamma _{t})}}}$.

Para cada paso, si${\displaystyle h(w_{t},\gamma _{t})\neq 0}$, luego actualice la dirección como

${\displaystyle w_{t+1}=w_{t}-s_{t}\triangledown _{w}f(w_{t},\gamma _{t})}$.

Luego actualice la longitud según

${\displaystyle \gamma _{t}={\text{Bisection}}(T_{s},f,w_{t})}$, dónde${\displaystyle {\text{Bisection()}}}$es el algoritmo de bisección clásico y${\displaystyle T_{s}}$es el número total de iteraciones ejecutadas en el paso de bisección.

Denotemos el número total de iteraciones como${\displaystyle T_{d}}$, entonces el resultado final de GDNP es

${\displaystyle {\tilde {w}}_{T_{d}}=\gamma _{T_{d}}{\frac {w_{T_{d}}}{||w_{T_{d}}||_{S}}}}$.

El algoritmo GDNP modifica ligeramente el paso de normalización por lotes para facilitar el análisis matemático.

Se puede demostrar que en GDNP, la derivada parcial de${\displaystyle f_{LH}}$frente al componente de longitud converge a cero a una tasa lineal, de tal manera que

${\displaystyle (\partial _{\gamma }f_{LH}(w_{t},a_{t}^{(T_{s})})^{2}\leq {\frac {2^{-T_{s}}\zeta |b_{t}^{(0)}-a_{t}^{(0)}|}{\mu ^{2}}}}$, dónde${\displaystyle a_{t}^{(0)}}$y${\displaystyle b_{t}^{0}}$son los dos puntos de partida del algoritmo de bisección a la izquierda y a la derecha, respectivamente.

Además, para cada iteración, la norma del gradiente de${\displaystyle f_{LH}}$con respecto a${\displaystyle w}$converge linealmente, de tal manera que

${\displaystyle ||w_{t}||_{S}^{2}||\triangledown f_{LH}(w_{t},g_{t})||_{S^{-1}}^{2}\leq {\bigg (}1-{\frac {\mu }{L}}{\bigg )}^{2t}\Phi ^{2}\gamma _{t}^{2}(\rho (w_{0})-\rho ^{*})}$.

Combinando estas dos desigualdades, se podría obtener una cota para el gradiente con respecto a${\displaystyle {\tilde {w}}_{T_{d}}}$:

${\displaystyle ||\triangledown _{\tilde {w}}f({\tilde {w}}_{T_{d}})||^{2}\leq {\bigg (}1-{\frac {\mu }{L}}{\bigg )}^{2T_{d}}\Phi ^{2}(\rho (w_{0})-\rho ^{*})+{\frac {2^{-T_{s}}\zeta |b_{t}^{(0)}-a_{t}^{(0)}|}{\mu ^{2}}}}$, de tal manera que se garantice que el algoritmo converge linealmente.

Aunque la demostración se basa en el supuesto de una entrada gaussiana, también se ha demostrado experimentalmente que GDNP podría acelerar la optimización sin esta restricción.

Consideremos un perceptrón multicapa (MLP) con una capa oculta y${\displaystyle m}$unidades ocultas con mapeo desde la entrada${\displaystyle x\in R^{d}}$a una salida escalar descrita como

${\displaystyle F_{x}({\tilde {W}},\Theta )=\sum _{i=1}^{m}\theta _{i}\phi (x^{T}{\tilde {w}}^{(i)})}$, dónde${\displaystyle {\tilde {w}}^{(i)}}$y${\displaystyle \theta _{i}}$son los pesos de entrada y salida de la unidad${\displaystyle i}$En consecuencia, y${\displaystyle \phi }$es la función de activación y se supone que es una función tanh .

Los pesos de entrada y salida podrían entonces optimizarse con

${\displaystyle \min _{{\tilde {W}},\Theta }(f_{NN}({\tilde {W}},\Theta )=E_{y,x}[l(-yF_{x}({\tilde {W}},\Theta ))])}$, dónde${\displaystyle l}$es una función de pérdida,${\displaystyle {\tilde {W}}=\{{\tilde {w}}^{(1)},...,{\tilde {w}}^{(m)}\}}$, y${\displaystyle \Theta =\{\theta ^{(1)},...,\theta ^{(m)}\}}$.

Considere fijo${\displaystyle \Theta }$y optimizando únicamente${\displaystyle {\tilde {W}}}$, se puede demostrar que los puntos críticos de${\displaystyle f_{NN}({\tilde {W}})}$de una unidad oculta en particular${\displaystyle i}$,${\displaystyle {\hat {w}}^{(i)}}$, todos se alinean a lo largo de una línea dependiendo de la información entrante en la capa oculta, de tal manera que

${\displaystyle {\hat {w}}^{(i)}={\hat {c}}^{(i)}S^{-1}u}$, dónde${\displaystyle {\hat {c}}^{(i)}\in R}$es un escalar,${\displaystyle i=1,...,m}$.

Este resultado podría probarse estableciendo el gradiente de${\displaystyle f_{NN}}$a cero y resolviendo el sistema de ecuaciones.

Aplique el algoritmo GDNP a este problema de optimización alternando la optimización sobre las diferentes unidades ocultas. Específicamente, para cada unidad oculta, ejecute GDNP para encontrar el óptimo.${\displaystyle W}$y${\displaystyle \gamma }$. Con la misma elección de criterio de parada y tamaño de paso, se deduce que

${\displaystyle ||\triangledown _{{\tilde {w}}^{(i)}}f({\tilde {w}}_{t}^{(i)})||_{S^{-1}}^{2}\leq {\bigg (}1-{\frac {\mu }{L}}{\bigg )}^{2t}C(\rho (w_{0})-\rho ^{*})+{\frac {2^{-T_{s}^{(i)}}\zeta |b_{t}^{(0)}-a_{t}^{(0)}|}{\mu ^{2}}}}$.

Dado que los parámetros de cada unidad oculta convergen linealmente, todo el problema de optimización tiene una tasa de convergencia lineal. ^{[ 8 ]}