Teorema de aproximación universal

El resultado de Cybenko es bastante intuitivo, como espero transmitir a continuación; lo que hace las cosas más difíciles es que apuntaba tanto a la generalidad como a un número mínimo de capas ocultas. El resultado de Kolmogorov (mencionado por vzn) de hecho logra una garantía más fuerte, pero es algo menos relevante para el aprendizaje automático (en particular, no construye una red neuronal estándar, ya que los nodos son heterogéneos); Este resultado a su vez es desalentador ya que en la superficie son solo 3 páginas registrando algunos límites y funciones continuas, pero en realidad está construyendo un conjunto de fractales. Si bien el resultado de Cybenko es inusual y muy interesante debido a las técnicas exactas que utiliza, los resultados de ese sabor son muy utilizados en el aprendizaje automático (y puedo señalarle a otros).

Aquí hay un resumen de alto nivel de por qué el resultado de Cybenko debería ser válido.

Una función continua en un conjunto compacto se puede aproximar mediante una función constante por partes.
Una función constante por partes se puede representar como una red neuronal de la siguiente manera. Para cada región donde la función es constante, use una red neuronal como función indicadora para esa región. Luego construya una capa final con un solo nodo, cuya combinación lineal de entrada es la suma de todos los indicadores, con un peso igual al valor constante de la región correspondiente en la función constante por partes original.

Con respecto al primer punto anterior, esto puede tomarse como la afirmación "una función continua sobre un conjunto compacto es uniformemente continua". Lo que esto significa para nosotros es que puede tomar su función continua sobre , y algún error objetivo , luego puede rejilla en la escala (terminando aproximadamente subcubes) de modo que una función que es constante sobre cada subcubo está dentro de de la función objetivo. $[0,1]^d$ $\epsilon>0$ $[0,1]^d$ $\tau>0$ $(1/\tau)^d$ $\epsilon$

Ahora, una red neuronal no puede representar con precisión un indicador, pero puede acercarse mucho. Supongamos que la "función de transferencia" es un sigmoide. (La función de transferencia es la función continua que aplica a una combinación lineal de entradas para obtener el valor del nodo de la red neuronal). Luego, al hacer que los pesos sean enormes, genera algo cercano a 0 o cercano a 1 para obtener más entradas. Esto es coherente con el desarrollo de Cybenko: observe que necesita que las funciones involucradas sean iguales a 0 o 1 en el límite: por definición de límite, obtiene exactamente lo que estoy diciendo, lo que significa que empuja las cosas arbitrariamente cerca de 0 o 1.

(Ignoré la función de transferencia en la capa final; si está allí, y es continua, entonces podemos ajustar cualquier asignación a reemplazando los pesos constantes con algo en la imagen inversa de esa constante de acuerdo con la transferencia función.) $[0,1]$

Observe que lo anterior puede parecer tomar un par de capas: digamos, 2 para construir los indicadores en cubos, y luego una capa de salida final. Cybenko intentaba dos puntos de generalidad: un número mínimo de capas ocultas y flexibilidad en la elección de la función de transferencia. Ya he descrito cómo trabaja la flexibilidad en la función de transferencia.

Para obtener el número mínimo de capas, evita la construcción anterior y, en su lugar, utiliza el análisis funcional para desarrollar una contradicción. Aquí hay un bosquejo del argumento.

El nodo final calcula una combinación lineal de los elementos de la capa debajo de ella y le aplica una función de transferencia. Esta combinación lineal es una combinación lineal de funciones y, como tal, es en sí misma una función, una función dentro de algún subespacio de funciones, abarcada por los posibles nodos en la capa oculta.
Un subespacio de funciones es como un subespacio ordinario de dimensiones finitas, con la principal diferencia de que potencialmente no es un conjunto cerrado; Es por eso que todos los argumentos de Cybenko toman el cierre de ese subespacio. Estamos tratando de demostrar que este cierre contiene todas las funciones continuas; eso significará que estamos arbitrariamente cerca de todas las funciones continuas.
Si el espacio de funciones fuera simple (un espacio de Hilbert), podríamos argumentar de la siguiente manera. Elija alguna función continua de destino que se supone contradictoriamente que no se encuentra en el subespacio, y proyecte en el complemento ortogonal del subespacio. Este residuo debe ser distinto de cero. Pero dado que nuestro subespacio puede representar cosas como esos pequeños cubos de arriba, podemos encontrar alguna región de este residuo, ajustar un pequeño cubo a él (como arriba) y así acercarnos a nuestra función objetivo. Esto es una contradicción ya que las proyecciones eligen elementos mínimos. (Tenga en cuenta que estoy dejando algo aquí: el argumento de Cybenko no construye ningún cubito, también lo maneja en general; aquí es donde usa una forma del teorema de representación de Riesz y las propiedades de las funciones de transferencia (si recuerdo correctamente, hay un lema separado para este paso,
No estamos en un espacio de Hilbert, pero podemos usar el teorema de Hahn-Banach para reemplazar el paso de proyección anterior (nota, probar que Hahn-Banach usa el axioma de elección).

Ahora me gustaría decir algunas cosas sobre el resultado de Kolmogorov. Si bien este resultado aparentemente no necesita el tipo de antecedentes de Cybenko, personalmente creo que es mucho más intimidante.

Aquí es por qué. El resultado de Cybenko es una garantía de aproximación : no dice que podamos representar exactamente nada. Por otro lado, el resultado de Kolmogorov es proporcionar una igualdad . Más ridículamente, dice el tamaño de la red: solo necesita nodos . Para lograr este fortalecimiento, hay una trampa, por supuesto, la que mencioné anteriormente: la red es heterogénea, por lo que quiero decir que todas las funciones de transferencia no son las mismas. $\mathcal O(d^2)$

Bien, con todo eso, ¿cómo puede funcionar esto?

Volvamos a nuestros cubos de arriba. Tenga en cuenta que tuvimos que hornear con un nivel de precisión: por cada , tenemos que regresar y elegir un más refinado . Como estamos trabajando con combinaciones lineales (finitas) de indicadores, nunca representamos exactamente nada. (las cosas solo empeoran si incluye los efectos aproximados de los sigmoides). $\epsilon>0$ $\tau >0$

$[0,1]$ $[0,1]^d$ $\mathcal O(d^2)$ $\mathbb{R}^d$ $\mathbb R$ $\mathcal O(d^2)$

Tenga en cuenta que el resultado de Cybenko, debido al uso de un solo tipo de función de transferencia, es más relevante para el aprendizaje automático. Los teoremas de este tipo son muy comunes en el aprendizaje automático (vzn sugirió esto en su respuesta, sin embargo, se refirió al resultado de Kolmogorov, que es menos aplicable debido a las funciones de transferencia personalizadas; esto se debilita en algunas versiones más elegantes del resultado de Kolmogorov (producido por otros autores), pero esos todavía involucran fractales, y al menos dos funciones de transferencia).

Tengo algunas diapositivas sobre estos temas, que podría publicar si está interesado (espero que tenga menos divagaciones que las anteriores y tenga algunas fotos; sin embargo, las escribí antes de ser experto en Hahn-Banach). Creo que ambas pruebas son muy, muy buenas. (Además, tengo otra respuesta aquí sobre estos temas, pero la escribí antes de haber asimilado el resultado de Kolmogorov).

matus
fuente

A

$A$

B

$B$

ϕ

$\phi$

\forall f \in A : ϕ (f) \leq 1

$\forall f \in A: \phi(f) \leq 1$

\forall g \in B : ϕ (g) > 1

$\forall g \in B: \phi(g) > 1$

Sasho Nikolov

S

$S$

f \notin S

$f\not\in S$

L

$L$

L (g) = 0

$L(g) = 0$

g \in S

$g \in S$

L (f) = ‖ f ‖

$L(f) = \|f\|$

L (f)

$L(f)$ como parte integral con respecto a alguna medida firmada. Pero esto termina la prueba debido a las condiciones de Cybenko en las funciones de transferencia (continúa en el siguiente comentario).

matus

@SashoNikolov, la condición de Cybenko es que, dada cualquier medida firmada que no sea exactamente cero, existe alguna función afín para que la integración de la función de transferencia compuesta con esa función afín, sobre esa medida, no sea igual a cero. Luego tiene que demostrar el lema de que los sigmoides generalizados (como di anteriormente: límites a 0 y 1 a la izquierda y a la derecha) se ajustan perfectamente. (continúa en el siguiente comentario.)

matus

@SashoNikolov. Arriba dije "dejando caer un cubo a lo largo del residuo". Esto haría nuestro trabajo un poco más fácil, ya que la medida firmada no es exactamente cero, simplemente elegiríamos un pedacito y colocaríamos un indicador allí. En su caso, tiene que trabajar un poco, pero de manera similar, esto se reduce a moverse alrededor del sigmoide con la función afín para que encuentre alguna región fácil, obteniendo así una integral no nula, contradiciendo a Hahn-Banach (que es cero en nuestro subespacio) ; en el sentido de Hilbert, redujimos nuestro residuo, una contradicción.

matus

Wow, esta es una respuesta extremadamente buena. Naturalmente, tengo algunas preguntas si no te importa contestarlas. El resultado de Cybenko (como usted dice) parece más útil para las aplicaciones, pero me pierdo un poco al tratar con el subespacio de funciones. ¿Cómo proyectamos una función continua arbitraria en el complemento ortogonal del subespacio de combinaciones lineales de posibles nodos? Para el caso, ¿cómo conceptualizamos el cumplido ortogonal de ese subespacio? ¿Las funciones más cercanas en el espacio se aproximan más entre sí? (Continuado).

Matt Munson

Hay un resultado avanzado, clave para el aprendizaje automático, conocido como el teorema de Kolmogorov [1]; Nunca he visto un bosquejo intuitivo de por qué funciona. Esto puede tener que ver con las diferentes culturas que lo abordan. La multitud de aprendizaje aplicado considera el teorema de Kolmogorov como un teorema de existencia que simplemente indica que pueden existir NN, por lo que al menos la estructura no es demasiado limitante, pero el teorema no garantiza que se puedan encontrar estos NN. Los matemáticos no están tan interesados en las aplicaciones de bajo nivel del teorema.

El teorema también se usó históricamente para invocar / defender la sofisticación inherente de las NN multicapa para contrarrestar una crítica de Perceptrons (Minsky / Papert) de que había funciones básicas [es decir, no lineales] que no podían aprender.

Los informáticos teóricos prefieren no considerar las NN como "aproximaciones" , ya que ese término tiene un significado especial / diferente. Probablemente exista una analogía aproximada con la interpolación lineal por partes, pero nuevamente, no la he visto expuesta.

[1] Kolmogorov, AN (1957). Sobre la representación de funciones continuas de muchas variables por superposición de funciones continuas de una variable y suma. Doklady Akademii Nauk SSSR, 144, 679-681; American Mathematical Society Translation, 28, 55-59 [1963]

[2] 2.3 Capacidades de aproximación de las redes neuronales de alimentación directa para funciones continuas

[3] Teorema de Kolmogorov y redes neuronales multicapa Kurkova

vzn
fuente

ver también ¿ son las técnicas de aprendizaje automático algoritmos de aproximación? , stats.se

vzn

"Este resultado avanzado [...] no ha visto un bosquejo intuitivo de por qué funciona". ¿Sería un bosquejo de este tipo una tarea considerable para alguien en la avanzada multitud de matemáticas? ¿Las personas de matemáticas avanzadas incluso entienden intuitivamente por qué funciona? Parece que una comprensión intuitiva de este teorema es algo que la multitud de aprendizaje aplicada debería desear fuertemente, si van a idear topologías y algoritmos de aprendizaje superiores para los ANN.

Matt Munson

Editado para gramática, ortografía, puntuación y mayúsculas.

Jeffε

Teorema de aproximación universal - Redes neuronales

Respuestas: