Contar boceto

Method of a dimension reduction

Count sketch es un tipo de reducción de dimensionalidad que es particularmente eficiente en estadística , aprendizaje automático y algoritmos . ^{[1] [2]} Fue inventado por Moses Charikar, Kevin Chen y Martin Farach-Colton ^[3] en un esfuerzo por acelerar el AMS Sketch de Alon, Matias y Szegedy para aproximar los momentos de frecuencia de las corrientes ^[4] (estos los cálculos requieren contar el número de apariciones de los distintos elementos de la corriente).

El boceto es casi idéntico ^{[ cita necesaria ]} al algoritmo hash de características de John Moody, ^[5] pero difiere en el uso de funciones hash con baja dependencia, lo que lo hace más práctico. Para seguir teniendo una alta probabilidad de éxito, se utiliza el truco de la mediana para agregar múltiples bocetos de conteo, en lugar de la media.

Estas propiedades permiten el uso de métodos de kernel explícitos , agrupación bilineal en redes neuronales y son la piedra angular de muchos algoritmos de álgebra lineal numérica. ^[6]

Explicación intuitiva

Los inventores de esta estructura de datos ofrecen la siguiente explicación iterativa de su funcionamiento: ^[3]

• en el nivel más simple, la salida de una única función hash que asigna elementos de flujo q a {+1, -1} alimenta un único contador ascendente/descendente C . Después de una sola pasada sobre los datos, la frecuencia de un elemento de corriente q puede aproximarse, aunque muy pobremente, al valor esperado ; ${\displaystyle n(q)}$ ${\displaystyle {\mathbf {E}}[C\cdot s(q)]}$
• Una forma sencilla de mejorar la varianza de la estimación anterior es utilizar una serie de funciones hash diferentes , cada una conectada a su propio contador . Para cada elemento q , todavía se mantiene, por lo que promediar en todo el rango i ajustará la aproximación; ${\displaystyle s_{i}}$ ${\displaystyle C_{i}}$ ${\displaystyle {\mathbf {E}}[C_{i}\cdot s_{i}(q)]=n(q)}$
• la construcción anterior todavía tiene una deficiencia importante: si un elemento de salida a de frecuencia más baja pero aún importante presenta una colisión hash con un elemento de alta frecuencia, la estimación puede verse afectada significativamente. Para evitar esto, es necesario reducir la frecuencia de las actualizaciones del contador de colisiones entre dos elementos distintos. Esto se logra reemplazando cada uno en la construcción anterior con una matriz de m contadores (haciendo que el contador se establezca en una matriz bidimensional ), con el índice j de un contador particular que se incrementará/disminuirá seleccionado a través de otro conjunto de funciones hash que asignan elemento q en el rango {1.. m }. Dado que , el promedio de todos los valores de i funcionará. ${\displaystyle n(a)}$ ${\displaystyle C_{i}}$ ${\displaystyle C_{i,j}}$ ${\displaystyle h_{i}}$ ${\displaystyle {\mathbf {E}}[C_{i,h_{i}(q)}\cdot s_{i}(q)]=n(q)}$

Definición matemática

1. Para las constantes y (que se definirán más adelante), elija de forma independiente funciones hash aleatorias y tales que y . Es necesario que las familias de hash de las que se eligen y sean independientes por pares. ${\displaystyle w}$ ${\displaystyle t}$ ${\displaystyle d=2t+1}$ ${\displaystyle h_{1},\dots ,h_{d}}$ ${\displaystyle s_{1},\dots ,s_{d}}$ ${\displaystyle h_{i}:[n]\to [w]}$ ${\displaystyle s_{i}:[n]\to \{\pm 1\}}$ ${\displaystyle h_{i}}$ ${\displaystyle s_{i}}$

2. Para cada elemento de la secuencia, agréguelo al enésimo depósito del enésimo hash. ${\displaystyle q_{i}}$ ${\displaystyle s_{j}(q_{i})}$ ${\displaystyle h_{j}(q_{i})}$ ${\displaystyle j}$

Al final de este proceso, se tienen sumas donde ${\displaystyle wd}$ ${\displaystyle (C_{ij})}$

${\displaystyle C_{i,j}=\sum _{h_{i}(k)=j}s_{i}(k).}$

Para estimar el recuento de s se calcula el siguiente valor: ${\displaystyle q}$

${\displaystyle r_{q}={\text{median}}_{i=1}^{d}\,s_{i}(q)\cdot C_{i,h_{i}(q)}.}$

Los valores son estimaciones imparciales de cuántas veces ha aparecido en la transmisión. ${\displaystyle s_{i}(q)\cdot C_{i,h_{i}(q)}}$ ${\displaystyle q}$

La estimación tiene varianza , donde es la longitud del arroyo y es . ^[7] ${\displaystyle r_{q}}$ ${\displaystyle O(\mathrm {min} \{m_{1}^{2}/w^{2},m_{2}^{2}/w\})}$ ${\displaystyle m_{1}}$ ${\displaystyle m_{2}^{2}}$ ${\displaystyle \sum _{q}(\sum _{i}[q_{i}=q])^{2}}$

Además, se garantiza que nunca estará más que alejado del valor real, con una probabilidad de . ${\displaystyle r_{q}}$ ${\displaystyle 2m_{2}/{\sqrt {w}}}$ ${\displaystyle 1-e^{-O(t)}}$

formulación vectorial

Alternativamente, Count-Sketch puede verse como un mapeo lineal con una función de reconstrucción no lineal. Sea , una colección de matrices, definida por ${\displaystyle M^{(i\in [d])}\in \{-1,0,1\}^{w\times n}}$ ${\displaystyle d=2t+1}$

${\displaystyle M_{h_{i}(j),j}^{(i)}=s_{i}(j)}$

para y 0 en cualquier otro lugar. ${\displaystyle j\in [w]}$

Luego se dibuja un vector mediante . Para reconstruir tomamos . Esto da las mismas garantías que las expuestas anteriormente, si tomamos y . ${\displaystyle v\in \mathbb {R} ^{n}}$ ${\displaystyle C^{(i)}=M^{(i)}v\in \mathbb {R} ^{w}}$ ${\displaystyle v}$ ${\displaystyle v_{j}^{*}={\text{median}}_{i}C_{j}^{(i)}s_{i}(j)}$ ${\displaystyle m_{1}=\|v\|_{1}}$ ${\displaystyle m_{2}=\|v\|_{2}}$

Relación con el boceto tensorial

La proyección del croquis de conteo del producto exterior de dos vectores es equivalente a la convolución de los croquis de conteo de dos componentes.

El boceto de conteo calcula una convolución vectorial

${\displaystyle C^{(1)}x\ast C^{(2)}x^{T}}$, donde y son matrices de croquis de recuento independientes. ${\displaystyle C^{(1)}}$ ${\displaystyle C^{(2)}}$

Pham y Pagh ^[8] muestran que esto es igual a : un esquema de conteo del producto exterior de vectores, donde denota el producto de Kronecker . ${\displaystyle C(x\otimes x^{T})}$ ${\displaystyle C}$ ${\displaystyle \otimes }$

La transformada rápida de Fourier se puede utilizar para realizar una convolución rápida de bocetos de recuento. Al utilizar el producto de división de caras ^{[9] [10] [11],} tales estructuras se pueden calcular mucho más rápido que las matrices normales.

Ver también

• El boceto Count-min es una versión del algoritmo con menores requisitos de memoria (y garantías de error más débiles como compensación).
• tensorboceto

Referencias

1. Faisal M. Algashaam; Kien Nguyen; Mohamed Alkanhal; Vinod Chandran; Wageeh Boles. "Clasificación periocular multiespectral con agrupación multimodal compacta multilineal" [1]. Acceso IEEE , vol. 5. 2017.
2. Ahlé, Thomas; Knudsen, Jakob (3 de septiembre de 2019). "Bosquejo tensorial casi óptimo". Puerta de la investigación . Consultado el 11 de julio de 2020 .
3. Charikar, Chen y Farach-Colton 2004.
4. Alon, Noga, Yossi Matías y Mario Szegedy. "La complejidad espacial de aproximar los momentos de frecuencia". Revista de Ciencias de la Computación y de Sistemas 58.1 (1999): 137-147.
5. De mal humor, John. "Aprendizaje rápido en jerarquías de resolución múltiple". Avances en los sistemas de procesamiento de información neuronal. 1989.
6. Woodruff, David P. "Dibujar como herramienta de álgebra lineal numérica". Informática teórica 10.1-2 (2014): 1–157.
7. Larsen, Kasper Green, Rasmus Pagh y Jakub Tětek. "CountSketches, hash de funciones y la mediana de tres". Congreso Internacional sobre Aprendizaje Automático. PMLR, 2021.
8. Ninh, Pham; Pagh, Rasmus (2013). Núcleos polinómicos rápidos y escalables a través de mapas de características explícitos . Conferencia internacional SIGKDD sobre descubrimiento de conocimiento y minería de datos. Asociación para Maquinaria de Computación. doi :10.1145/2487575.2487591.
9. Slyusar, VI (1998). «Productos finales en matrices en aplicaciones de radar» (PDF) . Radioelectrónica y Sistemas de Comunicaciones . 41 (3): 50–53.
10. Slyusar, VI (20 de mayo de 1997). "Modelo analítico del conjunto de antenas digitales sobre la base de productos matriciales de división de caras" (PDF) . Proc. ICATT-97, Kiev : 108–109.
11. Slyusar, VI (13 de marzo de 1998). "Una familia de productos faciales de matrices y sus propiedades" (PDF) . Cibernética y Análisis de Sistemas C/C de Kibernetika I Sistemnyi Analiz.- 1999 . 35 (3): 379–384. doi :10.1007/BF02733426. S2CID  119661450.

Otras lecturas

• Charikar, Moisés; Chen, Kevin; Farach-Colton, Martín (2004). "Encontrar elementos frecuentes en flujos de datos" (PDF) . Informática Teórica . 312 (1). Elsevier BV: 3-15. doi :10.1016/s0304-3975(03)00400-6. ISSN  0304-3975.
• Faisal M. Algashaam; Kien Nguyen; Mohamed Alkanhal; Vinod Chandran; Wageeh Boles. "Clasificación periocular multiespectral con agrupación multilineal compacta multimodal" [1]. Acceso IEEE , vol. 5. 2017.
• Ahlé, Thomas; Knudsen, Jakob (3 de septiembre de 2019). "Bosquejo tensorial casi óptimo". Puerta de la investigación . Consultado el 11 de julio de 2020 .