Gradiente de la pendiente de $f(w)=\frac12w^TAw-b^Tw$ ver en el espacio de vectores propios de a $A$

Question

Estoy leyendo ¿por Qué ritmo Realmente Funciona, un post de la nueva destilar diario. Voy a parafrasear a las principales ecuaciones que conducen a la parte que me confunde, el post describe la intuición en más detalle.

El gradiente de la pendiente algoritmo está dada por el siguiente proceso iterativo $$w^{k+1} = w^k-\alpha \nabla f(w^k)$$ donde $w^k$ es el valor de la iteración $k$, la tasa de aprendizaje es $\alpha$ $\nabla f(w)$ es el gradiente de la función de $f$ evaluado en $w$. La función de $f$ desea minimizar.

Gradiente de la pendiente con el impulso dado por la adición de "memoria" en el descenso, este es descrita por el par de ecuaciones:

\begin{align} z^{k+1} &= \beta z^k + \nabla f(w^k) \\ w^{k+1} &= w^k - \alpha z^{k+1} \end{align}

En la siguiente sección "Primeros Pasos: Gradiente de la pendiente", el autor considera que una función cuadrática convexa $$f(w) = \frac12w^TAw-b^Tw, \quad w \in \mathbb{R}^n, A \in \mathbb{R}^{n,n}$$ que ha degradado $$\nabla f(w) = Aw-b$$ Si asumimos $A$ es simétrica y invertable, a continuación, $f$ tiene solución óptima $w^\star = A^{-1}b$.

Si fuéramos a usar gradiente de la pendiente, nos gustaría recorrer hacia esta solución óptima de la siguiente manera \begin{align} w^{k+1} &= w^k - \alpha \nabla f(w) \\ &= w^k - \alpha (Aw^k -b) \end{align}

A continuación, el artículo continúa diciendo que "Hay un espacio natural a la vista de gradiente de la pendiente, donde todas las dimensiones de actuar de forma independiente - los vectores propios de a $A$". Creo que esto tiene sentido, aunque mi intuición es una especie de difusa.

Cada matriz simétrica $A$ tiene un autovalor de descomposición donde $$A = Q\text{diag}(\lambda_1,\ldots,\lambda_n)Q^T.$$

Donde $\lambda_1 > \ldots > \lambda_n$ $Q$ es el vector con los correspondientes vectores propios como columnas (a la derecha?).

Esta parte es donde no entiendo lo que está pasando:

Si queremos realizar un cambio de base, $x^k = Q^T(w^k - w^\star)$, el las iteraciones se rompen, convirtiéndose en:

\begin{align} x_i^{k+1} &= x_i^k - \alpha \lambda_i x_i^k \\ &=(1-\alpha\lambda_i)x_i^k &= (1- \alpha\lambda_i)^{k+1}x_i^0 \end{align}

Regresemos a nuestro espacio original $w$, podemos ver que

$$w^k - w^\star = Qx^k = \sum\limits_{i}^n = x_i^0(1-\alpha\lambda_i)^kq_i$$

¿Qué está pasando aquí? Donde es la motivación de la toma de $w^k - w^\star$ en el eigendomain? ¿Qué es $x^k$? ¿Por qué estamos ahora mirando invidual elementos del vector? He intentado seguir las caculations a través de, pero $x^{k+1}$ depende de $w^{k+1}$ que depende de la $z^k$, lo que yo pensaba que estaban tratando de eliminar. Mi pregunta es ¿alguien puede ampliar en estos pocos pasos con algo de intuición y cálculos? Gracias.

Answer 1

En muchas aplicaciones matemáticas, la motivación se vuelve más claro después de obtener el resultado. Así que vamos a empezar con el álgebra.

Supongamos que se ejecuta GD para $T$ iteraciones. Esto nos dará el conjunto de ${(w_k)}_{k=1}^T$.

Vamos a hacer un cambio de base:

$w^k = Qx^k + w^*$ $\iff$ $x^k = Q^T(w^k-w^*) $

Ahora tenemos ${(x_k)}_{k=1}^T$. ¿Qué podemos decir acerca de ellos? Echemos un vistazo a cada coordenada por separado. Mediante la sustitución de la encima y con el paso de actualización de la GD,

$x_i^{k+1}= (Q^T(w^{k+1}-w^*))_i = (Q^T(w^k-\alpha (Aw^k-b)-w^*))_i $

Organizar,

$x_i^{k+1}=(Q^T(w^k-w^*))_i-\alpha \cdot (Q^T(Aw^k-b))_i$

El primer término es exactamente $x_i^k$. Para el segundo término, sustituimos $A=Qdiag(\lambda _1 \dots \lambda _n)Q^T$. Esto produce,

$x_i^{k+1}=x_i^k-\alpha \lambda _i x_i^k=(1-\alpha \lambda _i)x_i^k$

Que fue de un solo paso. Repetir hasta que tengamos todo el camino a $x_0$, obtenemos

$x_i^{k+1}=(1-\alpha \lambda _i)^{k+1}x_i^0$

Parece que todo esto no sirve de nada en este punto. Volvamos a nuestra preocupación inicial, el ${w}$s. Desde nuestro original de cambio de base, sabemos que $w^k-w^*=Qx^k$. Otra manera de escribir la multiplicación de la matriz $Q$ por el vector $x^k$$\sum_i x_i^kq_i$. Pero hemos demostrado anteriormente que el $x_i^{k}=(1-\alpha \lambda _i)^{k}x_i^0$. Conectar todo, hemos obtenido la deseada "forma cerrada" fórmula para la GD paso de actualización:

$w^k-w^*=\sum_i x_i^0(1-\alpha \lambda _i)^{k} q_i$

Esto es esencialmente una expresión para el "error" en la iteración $k$ de GD (lo lejos que estamos de la solución óptima, $w^*$). Puesto que estamos interesados en evaluar el desempeño de los GD, esta es la expresión que queremos analizar. Hay dos inmediata observaciones. La primera es que este término va a 0 $k$ va al infinito, que por supuesto es una buena noticia. La segunda es que el error se descompone muy bien en los elementos separados de $x_0$, que es incluso mejor por el bien de nuestro análisis. Cito aquí el post original, ya que creo que ellos lo explican muy bien:

Cada elemento de a $x^0$ es el componente del error en la estimación inicial de la$Q$ -. Hay $n$ tales errores, y cada uno de estos errores sigue su propio solitaria ruta de acceso a la mínima, disminuyendo de forma exponencial con una tasa compuesta de $1-\alpha \lambda_i $. El más cerca de ese número es 1, el más lento converge.

Espero que esto aclare las cosas para usted bastante que usted puede ir para seguir leyendo el post. Es realmente buena!

Answer 2

Voy a dar un par de comentarios en el lenguaje de la máquina de aprendizaje que se espera llevar a un útil conclusión lógica.

En primer lugar, la minimización de que cuadrática objetivo es como resolver un problema de mínimos cuadrados (si esto no es obvio, trate de probar como ejercicio). En segundo lugar, por cualquiera de los mínimos cuadrados problema, si las funciones son ortogonales, entonces la estimación de los coeficientes por separado o de forma secuencial (como haciendo exactamente una ronda de coordinar el descenso) es equivalente a la estimación conjunta. (Si esto no es obvio, entonces supongamos que las funciones son ortogonales. ¿Ves esto significa $A$ debe ser diagonal? Eso significa que cada entrada de la solución no depende de los demás).

Así que ahora la pregunta es: ¿Cómo podemos resolver el mismo problema, pero con una matriz diagonal en lugar de $A$? Tercero, el $\ell_2$ norma es ortogonalmente-invariante, por lo que si a la izquierda o a la derecha multiplicar lo que está dentro de la norma a través de una matriz ortogonal (lo que se interpreta como una rotación), sólo se puede resolver ese problema luego de vuelta que la transformación ortogonal al final. Desde $A$ es simétrica positiva semi-definitiva, podemos obtener los ortogonal de matrices a partir de que el autovalor de la descomposición de $A$ (aka por "diagonalizing" $A$).

De vuelta a la estadística: Este proceso se refiere a veces como el blanqueamiento o pre-whitening aunque creo que hay una falta de concesus como para el uso de este término.

Puesto de manera simple y flexible, en el espacio propio de $A$, las columnas/filas de $A$ puede ser visto como totalmente independientes y no relacionadas piezas de información.