Cálculo del gradiente de $x^TW^TWW^TWx$

Question

Estoy trabajando en un proyecto de investigación independiente, y necesito el gradiente de una ecuación para el gradiente estocástico. He podido calcular el gradiente $\nabla_W x^TW^TWx$ que resultó ser

$ 2\begin{pmatrix} w_1^\top \cdot x\\ w_2^\top \cdot x\\ \vdots \\ w_n^\top \cdot x \end{pmatrix} x^\top$

donde $x \in \mathbb{R}^n$ y $w_i^\top$ es el $i^{\rm th}$ fila de $W$ , un $n\times n$ matriz. Este es un producto externo y produce un $n\times n$ matriz, según sea necesario. (También me di cuenta de que puedo escribirla como $2Wxx^\top$ .)

Ahora estoy tratando de calcular el siguiente gradiente más desafiante:

$\nabla_W x^TW^TWW^TWx = \nabla_W x^T(W^TW)^2x$

Puedo convertir el gradiente en esa forma matricial a la siguiente forma sumatoria:

$\nabla_W \left[\sum_{i=1}^{n}\sum_{j=1}^{n} x_ix_j \sum_{k=1}^{n} (w_i \cdot w_k) (w_k \cdot w_j) \right]$

donde aquí $w_i \in \mathbb{R}^n$ es un columna de $W$ . Para calcular los gradientes, estoy tratando de hacer $\partial/\partial w_{ij}$ para obtener el patrón de un componente. Sin embargo, incluso para eso, el álgebra se convierte en un completo trabajo. Por ejemplo, con $\partial/\partial w_{ij}$ Estoy recibiendo

$\sum_{i=1}^{n}\sum_{j=1}^n x_ix_j \frac{\partial}{\partial w_{ij}} \left( (w_i\cdot w_j)\|w_j\|_2^2 + \sum_{k=1, k\ne j}^{n} (w_i\cdot w_k)(w_k \cdot w_j) \right)$

¿Conoces una forma mejor de calcular los gradientes que pueda aprovechar el patrón del primer gradiente aquí, o quizás otro concepto del álgebra de gradientes? ¿O es hacer fuerza bruta el camino a seguir? (He repasado el álgebra, pero me resulta difícil ver cómo condensarlo bien). Tal vez sea $2(W^\top W)Wxx^\top$ ? Gracias por la ayuda que puedan prestarme.

Answer 1

Hay varias formas de hacerlo, creo que la más sencilla es simplemente expandir la expresión y escoger las partes lineales.

Dejemos que $\phi(W) = x^T (W^T W)^2 x$ . Entonces $\phi(W+H) = x^T ((W+H)^T (W+H))^2 x$ .

Ampliar y recoger los términos en $H$ tenemos $D \phi(W)(H) = x^T (W^T W H^T W + W^T W W^T H + H^T W W^T W + W^T H W^T W) x$ .

Esto puede simplificarse ligeramente a $D \phi(W)(H) = 2 x^T (W^T W H^T W + W^T W W^T H) x$ .

Mirando $D \phi(W)(e_i e_j^T) $ obtenemos el gradiente $\nabla \phi(W) = 2(W^T W x x^T W^T + W W^T W x x^T)$ .

Aclaraciones :

(i) El $H$ es análogo a $h$ en $f(x+h) = f(x) + Df(x)(h) + o(h)$ .

Se calcula $\phi(W+H)-\phi(W)$ y busca los términos lineales en $H$ (y comprueba que los términos restantes son $o(H)$ ).

(ii) $D \phi(W)$ (o ${ \partial \phi(W) \over \partial W}$ ) es la derivada de $\phi$ las únicas complicaciones son que estamos tratando con matrices.

La derivada evaluada en la dirección $H$ es $D\phi(W)(H)$ . En el habitual $f: \mathbb{R}^n \to \mathbb{R}$ tipo de cosas, podemos representar $Df(x)$ como vector dual (transposición) y $Df(x)(h)$ es sólo la multiplicación por $h$ . Las matrices lo complican ligeramente.

(iii) Para hablar de un gradiente, necesitamos un producto interno. En este caso utilizamos $\langle A, B \rangle = \sum_{ij} [A]_{ij} [B]_{ij}$ . Entonces necesito encontrar algún elemento $G$ tal que $\langle G, H \rangle = D \phi(W)(H)$ y entonces $\nabla \phi(W) = G$ . Vemos que $[G]_{ij} = \langle G, e_i e_j^T \rangle = D \phi(W)(e_i e_j^T)$ .