Resumen Técnico: Características aleatorias para la aproximación de núcleos grassmannianos con proyecciones de rango uno acotadas

Planteamiento del problema

En muchas tareas de aprendizaje supervisado y no supervisado, las clases de datos o grupos se representan naturalmente mediante subespacios de baja dimensión en espacios de alta dimensión, en lugar de puntos euclídeos individuales. Esto requiere operar en la variedad grassmanniana $\mathcal{G}(k, n)$, el conjunto de todos los subespacios de dimensión $k$ en $\mathbb{R}^n$. Si bien los métodos de núcleo (por ejemplo, SVM) pueden aprender eficazmente sobre tales datos utilizando núcleos positivos definidos (como el núcleo de proyección o el de Binet–Cauchy), estos sufren de una escalabilidad deficiente. Los métodos de núcleo estándar requieren la construcción y el almacenamiento de una matriz de Gram de $N \times N$, lo que conlleva costos de memoria y computación de $O(N^2)$, lo cual es prohibitivo para conjuntos de datos grandes.

Los intentos existentes para aproximar los núcleos grassmannianos mediante características aleatorias enfrentan dos limitaciones principales:

1. Proyecciones Aleatorias Densas: La incrustación de subespacios proyectando sus proyectores ortogonales sobre matrices gaussianas densas requiere $O(n^2)$ de almacenamiento y computación por característica, lo que resulta impráctico para dimensiones altas.
2. Proyecciones de Rango Uno (ROP) No Acotadas: Aunque las ROP basadas en mediciones cuadráticas $a^\top P b$ son computacionalmente más baratas ($O(kn)$ por característica), exhiben distribuciones de cola pesada (sub-Weibull). Esto resulta en tasas de concentración lentas, lo que impide garantías de aproximación uniforme sobre toda la variedad grassmanniana con un número de características que escala linealmente con la dimensión intrínseca.

Metodología

Los autores proponen una familia de mapas de características aleatorias que combinan proyecciones de rango uno (ROP) con transformaciones no lineales acotadas para lograr una aproximación de núcleo uniforme y escalable.

1. Proyecciones de Rango Uno (ROP)

Para un subespacio $P \in \mathcal{G}(k, n)$ representado por una base ortonormal $U$ (donde $P = UU^\top$), el método sondea el subespacio utilizando $m$ mediciones cuadráticas de rango uno independientes:
$$\psi_{\text{rop}}(U) = \left( a_i^\top P b_i \right)_{i=1}^m$$
donde $a_i, b_i \sim \text{i.i.d. } \mathcal{N}(0, I_n)$. Esto reduce el costo computacional por característica a $O(kn)$ y el almacenamiento a $O(kn)$ (tras factorizar $U^\top a_i$ y $U^\top b_i$).

2. Transformaciones No Lineales Acotadas

Para domar la distribución de cola pesada de las ROP no acotadas y asegurar la convergencia uniforme, los autores componen $\psi_{\text{rop}}$ con funciones no lineales acotadas $g(\cdot)$:
$$\psi_g(U) = g(\psi_{\text{rop}}(U))$$
Se analizan dos transformaciones específicas:

• Características Binarias: Utilizando la función signo, $g(\lambda) = \text{sign}(\lambda)$. Esto genera características aleatorias binarias $\psi_\pm \in \{\pm 1\}^m$, permitiendo un almacenamiento de 1 bit compacto y operaciones de bits rápidas.
• Características Periódicas: Utilizando la exponencial compleja, $g(\lambda) = \exp(i\omega \lambda)$. Esto genera características aleatorias periódicas $\psi_\circ$, análogas a las Características de Fourier Aleatorias (Random Fourier Features).

3. Proyecciones Estructuradas

Para reducir aún más la complejidad computacional, los autores reemplazan los vectores de sondeo gaussianos densos por matrices aleatorias estructuradas basadas en composiciones de transformadas rápidas de Walsh-Hadamard y matrices de signo diagonales aleatorias (inspiradas en Choromanski et al., 2016). Esto reduce la complejidad computacional de $O(kmn)$a$O(km \log n)$ manteniendo las propiedades estadísticas.

Contribuciones Clave

Garantías Teóricas

El artículo establece que los productos internos empíricos de estas características aleatorias acotadas son estimadores insesgados de núcleos grassmannianos específicos y bien definidos, que son invariantes ante rotaciones. Crucialmente, los autores demuestran límites de aproximación uniforme sobre todos los subespacios de dimensión fija $k$ en $\mathbb{R}^n$.

• Complejidad de Muestreo: Demuestran que $m = O(kn)$ características aleatorias (hasta factores logarítmicos) bastan para controlar el error de aproximación uniformemente. Esto escala linealmente con la dimensión ambiente $n$ y la dimensión del subespacio $k$, una mejora significativa respecto a los requisitos de $O((kn)^2)$ para las ROP no acotadas.
• Núcleo Binario ($\kappa_\pm$): Se demuestra que el núcleo esperado para las características binarias es positivo definido y rotacionalmente invariante. Aunque no existe una expresión de forma cerrada para un $k$ general, se caracteriza de forma semi-explícita como:
  $$\kappa_\pm(U, V) = 1 - \frac{2}{\pi} \mathbb{E}[\angle(P g, Q g)]$$
  donde $g \sim \mathcal{N}(0, I_n)$ y $\angle(\cdot, \cdot)$ es el ángulo entre vectores. Para $k=1$, se deriva una forma cerrada $(1 - 2\theta/\pi)^2$.
• Núcleo Periódico ($\kappa_\circ$): El núcleo esperado para las características periódicas admite una expresión de forma cerrada que depende de los ángulos principales $\{\theta_j\}_{j=1}^k$:
  $$\kappa_\circ(U, V) = \prod_{j=1}^k (1 + \omega^2 \sin^2 \theta_j)^{-1}$$
  Los autores analizan el comportamiento de $\kappa_\circ$ con respecto al parámetro de frecuencia $\omega$:
  • $\omega$ Grande: $\kappa_\circ$ se comporta como un núcleo Binet–Cauchy inverso (sensible a ángulos principales pequeños).
  • $\omega$ Pequeño: $\kappa_\circ$ aproxima un núcleo de Función de Base Radial (RBF) de proyección, $\exp(-\frac{1}{2}\omega^2 \|P-Q\|_F^2)$.

Complejidad Computacional

Los métodos propuestos ofrecen ganancias sustanciales de eficiencia:

• Memoria: El almacenamiento para las ROP no estructuradas acotadas es $O(mn)$ para los vectores de sondeo. Al sustituir $m = O(kn)$ para asegurar la aproximación uniforme, la complejidad de memoria global se convierte en $O(kn^2)$ (específicamente derivada como $O(\delta^{-2}(kn^2))$ en el artículo). Esto es distinto de las proyecciones densas que requieren $O(mn^2)$ de almacenamiento (escalando como $O(k^3 n^3)$ para la aproximación uniforme).
• Computación: La complejidad computacional para las ROP no estructuradas acotadas es $O(kmn)$. Con $m = O(kn)$, esto escala como $O(k^2 n^2)$. Esto es significativamente menor que la complejidad $O(k^2 n^3)$ asociada con los métodos de proyección densa (que requieren $O(\delta^{-2} k^3 n^3)$).
• Almacenamiento: Las características binarias requieren solo $O(m)$ bits por subespacio.

Resultados Experimentales

Los autores validan su enfoque utilizando experimentos sintéticos y el conjunto de datos ETH-80 (imágenes de objetos visuales desde diferentes puntos de vista).

1. Aproximación de Núcleo: Los experimentos confirman que las ROP acotadas convergen a sus núcleos objetivo con costos computacionales y de memoria significativamente menores que las proyecciones densas.
2. Incrustaciones Estructuradas: El análisis empírico de los bocetos de Hadamard-diagonal estructurados muestra que usar $S=3$ bloques es suficiente para aproximar una distribución gaussiana, validando el uso de transformadas rápidas.
3. Desempeño de Clasificación:
   • En tareas de clasificación de superclases (8 vías) y clasificación de objetos (80 vías), las características aleatorias propuestas (tanto no estructuradas como estructuradas) logran precisiones de clasificación comparables con los métodos de núcleo exactos, aunque con algunos compromisos dependiendo de la tarea específica y el núcleo.
   • Específicamente, las incrustaciones estructuradas con una relación de sobremuestreo $\rho = m/(nk)$ tan baja como 0.05 (5% del tamaño de la base original) logran una alta precisión reduciendo el tiempo de computación en órdenes de magnitud en comparación con la evaluación de núcleo exacta. Por ejemplo, en la tarea de clasificación de 80 vías, los métodos estructurados redujeron el tiempo de ejecución total de ~52.9 segundos (núcleo de proyección exacta) a ~1.9 segundos. Sin embargo, esta aceleración vino acompañada de una notable caída en la precisión del 98.75% (exacto) al 83.00% (estructurado), resaltando el compromiso entre la eficiencia computacional y el desempeño de la clasificación en este escenario específico.

Significado y Reivindicaciones

El artículo afirma proporcionar una alternativa práctica y escalable a los núcleos grassmannianos clásicos. Al combinar proyecciones de rango uno con no linealidades acotadas, los autores demuestran que es posible:

1. Recuperar la geometría grassmanniana con alta precisión.
2. Lograr garantías de aproximación uniforme sobre la variedad con un número de características que escala linealmente con la dimensión intrínseca.
3. Reducir drásticamente los requisitos de memoria y computación, haciendo que el aprendizaje basado en núcleos para datos de subespacios sea factible para aplicaciones de gran escala y alta dimensión.

El trabajo cierra la brecha entre los métodos de núcleo teóricos y la escalabilidad práctica, ofreciendo un marco donde el compromiso entre el error de aproximación y el costo computacional puede controlarse explícitamente mediante el número de características aleatorias y la elección de la transformación no lineal.