Esquema tensorial

El esquema tensorial de Pham y Pagh ^{[ 4 ]} calcula ${\displaystyle C^{(1)}x\ast C^{(2)}y}$, dónde${\displaystyle C^{(1)}}$y${\displaystyle C^{(2)}}$son matrices de bocetos de conteo independientes y${\displaystyle \ast }$es convolución vectorial . Demuestran que, sorprendentemente, esto es igual a${\displaystyle C(x\otimes y)}$– ¡un esbozo del producto tensorial!

Resulta que esta relación puede verse en términos del producto de división de caras como

${\displaystyle C^{(1)}x\ast C^{(2)}y={\mathcal {F}}^{-1}({\mathcal {F}}C^{(1)}x\circ {\mathcal {F}}C^{(2)}y)}$, dónde${\displaystyle {\mathcal {F}}}$es la matriz de la transformada de Fourier .

Desde${\displaystyle {\mathcal {F}}}$es una matriz ortonormal ,${\displaystyle {\mathcal {F}}^{-1}}$no afecta la norma de${\displaystyle Cx}$y puede ser ignorado. Lo que queda es que${\displaystyle C\sim {\mathcal {C}}^{(1)}\bullet {\mathcal {C}}^{(2)}}$.

Por otro lado,

${\displaystyle {\mathcal {F}}(C^{(1)}x\ast C^{(2)}y)={\mathcal {F}}C^{(1)}x\circ {\mathcal {F}}C^{(2)}y=({\mathcal {F}}C^{(1)}\bullet {\mathcal {F}}C^{(2)})(x\otimes y)}$.

El problema con el algoritmo original de bocetos tensoriales era que utilizaba matrices de bocetos de conteo , que no siempre son reducciones de dimensionalidad muy buenas.

En 2020 ^{[ 15 ]} se demostró que cualquier matriz con filas independientes suficientemente aleatorias es suficiente para crear un esquema tensorial. Esto permite utilizar matrices con garantías más sólidas, como las matrices reales de Johnson-Lindenstrauss gaussianas .

En particular, obtenemos el siguiente teorema:

Consideremos una matriz${\displaystyle T}$con filas iid${\displaystyle T_{1},\dots ,T_{m}\in \mathbb {R} ^{d}}$, de tal manera que${\displaystyle E[(T_{1}x)^{2}]=\|x\|_{2}^{2}}$y${\displaystyle E[(T_{1}x)^{p}]^{1/p}\leq {\sqrt {ap}}\|x\|_{2}}$. Dejar${\displaystyle T^{(1)},\dots ,T^{(c)}}$ser independiente consta de${\displaystyle T}$y${\displaystyle M=T^{(1)}\bullet \dots \bullet T^{(c)}}$.

Entonces${\displaystyle |\|Mx\|_{2}-\|x\|_{2}|<\varepsilon \|x\|_{2}}$con probabilidad${\displaystyle 1-\delta }$para cualquier vector${\displaystyle x}$si

${\displaystyle m=(4a)^{2c}\varepsilon ^{-2}\log 1/\delta +(2ae)\varepsilon ^{-1}(\log 1/\delta )^{c}}$.

En particular, si las entradas de${\displaystyle T}$son${\displaystyle \pm 1}$ obtenemos${\displaystyle m=O(\varepsilon ^{-2}\log 1/\delta +\varepsilon ^{-1}({\tfrac {1}{c}}\log 1/\delta )^{c})}$lo cual coincide con el teorema normal de Johnson-Lindenstrauss .${\displaystyle m=O(\varepsilon ^{-2}\log 1/\delta )}$cuando${\displaystyle \varepsilon }$es pequeño.

El artículo ^{[ 15 ]} también muestra que la dependencia de${\displaystyle \varepsilon ^{-1}({\tfrac {1}{c}}\log 1/\delta )^{c}}$es necesario para construcciones que utilizan proyecciones aleatorias tensoriales con entradas gaussianas .

Debido a la dependencia exponencial de${\displaystyle c}$En los bocetos tensoriales basados ​​en el producto de división de caras , se desarrolló un enfoque diferente en 2020 ^{[ 15 ]} que aplica

${\displaystyle M(x\otimes y\otimes \cdots )=M^{(1)}(x\otimes (M^{(2)}y\otimes \cdots ))}$

Podemos lograr tal cosa${\displaystyle M}$al dejar

${\displaystyle M=M^{(c)}(M^{(c-1)}\otimes I_{d})(M^{(c-2)}\otimes I_{d^{2}})\cdots (M^{(1)}\otimes I_{d^{c-1}})}$.

Con este método, solo aplicamos el método general de boceto tensorial a tensores de orden 2, lo que evita la dependencia exponencial en el número de filas.

Se puede demostrar ^{[ 15 ]} que la combinación${\displaystyle c}$reducciones de dimensionalidad como esta solo aumentan${\displaystyle \varepsilon }$por un factor${\displaystyle {\sqrt {c}}}$.

La transformada rápida de Johnson-Lindenstrauss es una matriz de reducción de dimensionalidad.

Dada una matriz${\displaystyle M\in \mathbb {R} ^{k\times d}}$, calculando el producto matriz-vector${\displaystyle Mx}$acepta${\displaystyle kd}$tiempo. La Transformada Rápida de Johnson-Lindenstrauss (FJLT), ^{[ 16 ]} fue introducida por Ailon y Chazelle en 2006.

Una versión de este método toma ${\displaystyle M=\operatorname {SHD} }$ dónde

1. ${\displaystyle D}$es una matriz diagonal donde cada entrada diagonal${\displaystyle D_{i,i}}$es${\displaystyle \pm 1}$independientemente.

La multiplicación matriz-vector${\displaystyle Dx}$se puede calcular en${\displaystyle O(d)}$tiempo.

1. ${\displaystyle H}$es una matriz de Hadamard , que permite la multiplicación matriz-vector en tiempo${\displaystyle O(d\log d)}$
2. ${\displaystyle S}$es un${\displaystyle k\times d}$matriz de muestreo que es todo ceros, excepto un solo 1 en cada fila.

Si la matriz diagonal se reemplaza por una que tiene un producto tensorial de${\displaystyle \pm 1}$Los valores en la diagonal, en lugar de ser totalmente independientes, es posible calcular${\displaystyle \operatorname {SHD} (x\otimes y)}$rápido.

Para un ejemplo de esto, veamos:${\displaystyle \rho ,\sigma \in \{-1,1\}^{2}}$ser dos independientes${\displaystyle \pm 1}$vectores y deje${\displaystyle D}$sea ​​una matriz diagonal con${\displaystyle \rho \otimes \sigma }$en diagonal. Entonces podemos dividir${\displaystyle \operatorname {SHD} (x\otimes y)}$como sigue:

${\displaystyle {\begin{aligned}&\operatorname {SHD} (x\otimes y)\\&\quad ={\begin{bmatrix}1&0&0&0\\0&0&1&0\\0&1&0&0\end{bmatrix}}{\begin{bmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{bmatrix}}{\begin{bmatrix}\sigma _{1}\rho _{1}&0&0&0\\0&\sigma _{1}\rho _{2}&0&0\\0&0&\sigma _{2}\rho _{1}&0\\0&0&0&\sigma _{2}\rho _{2}\\\end{bmatrix}}{\begin{bmatrix}x_{1}y_{1}\\x_{2}y_{1}\\x_{1}y_{2}\\x_{2}y_{2}\end{bmatrix}}\\[5pt]&\quad =\left({\begin{bmatrix}1&0\\0&1\\1&0\end{bmatrix}}\bullet {\begin{bmatrix}1&0\\1&0\\0&1\end{bmatrix}}\right)\left({\begin{bmatrix}1&1\\1&-1\end{bmatrix}}\otimes {\begin{bmatrix}1&1\\1&-1\end{bmatrix}}\right)\left({\begin{bmatrix}\sigma _{1}&0\\0&\sigma _{2}\\\end{bmatrix}}\otimes {\begin{bmatrix}\rho _{1}&0\\0&\rho _{2}\\\end{bmatrix}}\right)\left({\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\otimes {\begin{bmatrix}y_{1}\\y_{2}\end{bmatrix}}\right)\\[5pt]&\quad =\left({\begin{bmatrix}1&0\\0&1\\1&0\end{bmatrix}}\bullet {\begin{bmatrix}1&0\\1&0\\0&1\end{bmatrix}}\right)\left({\begin{bmatrix}1&1\\1&-1\end{bmatrix}}{\begin{bmatrix}\sigma _{1}&0\\0&\sigma _{2}\\\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\,\otimes \,{\begin{bmatrix}1&1\\1&-1\end{bmatrix}}{\begin{bmatrix}\rho _{1}&0\\0&\rho _{2}\\\end{bmatrix}}{\begin{bmatrix}y_{1}\\y_{2}\end{bmatrix}}\right)\\[5pt]&\quad ={\begin{bmatrix}1&0\\0&1\\1&0\end{bmatrix}}{\begin{bmatrix}1&1\\1&-1\end{bmatrix}}{\begin{bmatrix}\sigma _{1}&0\\0&\sigma _{2}\\\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\,\circ \,{\begin{bmatrix}1&0\\1&0\\0&1\end{bmatrix}}{\begin{bmatrix}1&1\\1&-1\end{bmatrix}}{\begin{bmatrix}\rho _{1}&0\\0&\rho _{2}\\\end{bmatrix}}{\begin{bmatrix}y_{1}\\y_{2}\end{bmatrix}}.\end{aligned}}}$

En otras palabras,${\displaystyle \operatorname {SHD} =S^{(1)}HD^{(1)}\bullet S^{(2)}HD^{(2)}}$, se divide en dos transformaciones rápidas de Johnson-Lindenstrauss, y la reducción total lleva tiempo${\displaystyle O(d_{1}\log d_{1}+d_{2}\log d_{2})}$en vez de${\displaystyle d_{1}d_{2}\log(d_{1}d_{2})}$igual que con el enfoque directo.

El mismo enfoque se puede extender para calcular productos de grado superior, como por ejemplo:${\displaystyle \operatorname {SHD} (x\otimes y\otimes z)}$

Ahle et al. ^{[ 15 ]} muestra que si${\displaystyle \operatorname {SHD} }$tiene${\displaystyle \varepsilon ^{-2}(\log 1/\delta )^{c+1}}$filas, luego${\displaystyle |\|\operatorname {SHD} x\|_{2}-\|x\||\leq \varepsilon \|x\|_{2}}$para cualquier vector${\displaystyle x\in \mathbb {R} ^{d^{c}}}$con probabilidad${\displaystyle 1-\delta }$, al tiempo que permite una multiplicación rápida con grado${\displaystyle c}$tensores.

Jin et al., ^{[ 17 ]} el mismo año, mostraron un resultado similar para la clase más general de matrices llamada RIP , que incluye las matrices de Hadamard submuestreadas. Demostraron que estas matrices permiten dividirse en tensores siempre que el número de filas sea${\displaystyle \varepsilon ^{-2}(\log 1/\delta )^{2c-1}\log d}$En el caso${\displaystyle c=2}$Esto coincide con el resultado anterior.

Estas construcciones rápidas se pueden combinar nuevamente con el enfoque recursivo mencionado anteriormente, lo que da como resultado el esquema tensorial general más rápido.

Los métodos de kernel son populares en el aprendizaje automático , ya que le dan al algoritmo diseñado la libertad de crear un "espacio de características" en el que medir la similitud de sus puntos de datos. Un clasificador binario simple basado en kernel se basa en el siguiente cálculo:

${\displaystyle {\hat {y}}(\mathbf {x'} )=\operatorname {sgn} \sum _{i=1}^{n}y_{i}k(\mathbf {x} _{i},\mathbf {x'} ),}$

dónde${\displaystyle \mathbf {x} _{i}\in \mathbb {R} ^{d}}$son los puntos de datos,${\displaystyle y_{i}}$es la etiqueta de la${\displaystyle i}$el punto (ya sea −1 o +1), y${\displaystyle {\hat {y}}(\mathbf {x'} )}$es la predicción de la clase de${\displaystyle \mathbf {x'} }$. La función${\displaystyle k:\mathbb {R} ^{d}\times \mathbb {R} ^{d}\to \mathbb {R} }$es el núcleo. Ejemplos típicos son el núcleo de la función de base radial ,${\displaystyle k(x,x')=\exp(-\|x-x'\|_{2}^{2})}$y núcleos polinomiales como${\displaystyle k(x,x')=(1+\langle x,x'\rangle )^{2}}$.

Cuando se utiliza de esta manera, el método del kernel se denomina "implícito". A veces es más rápido realizar un método de kernel "explícito", en el que un par de funciones${\displaystyle f,g:\mathbb {R} ^{d}\to \mathbb {R} ^{D}}$se encuentran, de tal manera que${\displaystyle k(x,x')=\langle f(x),g(x')\rangle }$Esto permite expresar el cálculo anterior como

${\displaystyle {\hat {y}}(\mathbf {x'} )=\operatorname {sgn} \sum _{i=1}^{n}y_{i}\langle f(\mathbf {x} _{i}),g(\mathbf {x'} )\rangle =\operatorname {sgn} \left\langle \left(\sum _{i=1}^{n}y_{i}f(\mathbf {x} _{i})\right),g(\mathbf {x'} )\right\rangle ,}$

donde el valor${\displaystyle \sum _{i=1}^{n}y_{i}f(\mathbf {x} _{i})}$se puede calcular con antelación.

El problema con este método es que el espacio de características puede ser muy grande. Es decir,${\displaystyle D>>d}$Por ejemplo, para el núcleo polinomial${\displaystyle k(x,x')=\langle x,x'\rangle ^{3}}$obtenemos${\displaystyle f(x)=x\otimes x\otimes x}$y${\displaystyle g(x')=x'\otimes x'\otimes x'}$, dónde${\displaystyle \otimes }$es el producto tensorial y${\displaystyle f(x),g(x')\in \mathbb {R} ^{D}}$dónde${\displaystyle D=d^{3}}$. Si${\displaystyle d}$ya es grande,${\displaystyle D}$puede ser mucho mayor que el número de puntos de datos (${\displaystyle n}$) y por lo tanto, el método explícito es ineficiente.

La idea del boceto tensorial es que podemos calcular funciones aproximadas.${\displaystyle f',g':\mathbb {R} ^{d}\to \mathbb {R} ^{t}}$dónde${\displaystyle t}$incluso puede ser más pequeño que${\displaystyle d}$y que aún tienen la propiedad de que${\displaystyle \langle f'(x),g'(x')\rangle \approx k(x,x')}$.

Se demostró en 2020 ^{[ 15 ]} que este método funciona incluso para polinomios de alto grado y núcleos de funciones de base radial.

Supongamos que tenemos dos grandes conjuntos de datos, representados como matrices.${\displaystyle X,Y\in \mathbb {R} ^{n\times d}}$y queremos encontrar las filas${\displaystyle i,j}$con los productos internos más grandes${\displaystyle \langle X_{i},Y_{j}\rangle }$Podríamos calcularlo.${\displaystyle Z=XY^{T}\in \mathbb {R} ^{n\times n}}$y simplemente mira todo${\displaystyle n^{2}}$posibilidades. Sin embargo, esto tomaría al menos${\displaystyle n^{2}}$tiempo, y probablemente más cerca de${\displaystyle n^{2}d}$utilizando técnicas estándar de multiplicación de matrices.

La idea de la multiplicación de matrices comprimidas es la identidad general.

${\displaystyle XY^{T}=\sum _{i=1}^{d}X_{i}\otimes Y_{i}}$

dónde${\displaystyle \otimes }$es el producto tensorial . Dado que podemos calcular una aproximación ( lineal ) a${\displaystyle X_{i}\otimes Y_{i}}$De manera eficiente, podemos sumar esos valores para obtener una aproximación del producto completo.

El agrupamiento bilineal es la técnica de tomar dos vectores de entrada,${\displaystyle x,y}$de diferentes fuentes y utilizando el producto tensorial${\displaystyle x\otimes y}$como capa de entrada a una red neuronal.

En ^{[ 19 ]} los autores consideraron utilizar el boceto tensorial para reducir el número de variables necesarias.

En 2017, otro artículo ^{[ 20 ]} toma la FFT de las características de entrada, antes de que se combinen usando el producto elemento a elemento. Esto nuevamente corresponde al esquema tensorial original.