Boceto del conde

Method of a dimension reduction

El boceto de conteo es un tipo de reducción de dimensionalidad que es particularmente eficiente en estadísticas , 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 boceto AMS de Alon, Matias y Szegedy para aproximar los momentos de frecuencia de los flujos ^[4] (estos cálculos requieren el conteo del número de ocurrencias de los distintos elementos del flujo).

El esquema es casi idéntico ^{[ cita requerida ]} al algoritmo de hash Feature 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 esquemas de recuento, en lugar de la media.

Estas propiedades permiten el uso de métodos de kernel explícitos y agrupamiento bilineal en redes neuronales y son una piedra angular en 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 función hash única 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 flujo q se puede aproximar, aunque de manera extremadamente deficiente, por el 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 matriz de diferentes funciones hash , cada una conectada a su propio contador . Para cada elemento q , la sigue siendo válida, por lo que el promedio en el rango i ajustará la aproximación; ${\displaystyle s_{i}}$ ${\displaystyle C_{i}}$ ${\displaystyle {\mathbf {E}}[C_{i}\cdot s_{i}(q)]=n(q)}$
• El constructo anterior todavía tiene una deficiencia importante: si un elemento de salida de menor frecuencia pero aún importante a exhibe una colisión hash con un elemento de alta frecuencia, la estimación puede verse afectada significativamente. Evitar esto requiere reducir la frecuencia de las actualizaciones del contador de colisión entre dos elementos distintos. Esto se logra reemplazando cada uno en el constructo anterior con una matriz de m contadores (haciendo que el conjunto de contadores sea una matriz bidimensional ), con el índice j de un contador particular que se incrementará/decrementará seleccionado a través de otro conjunto de funciones hash que mapean el 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 independientemente funciones hash aleatorias y tales que y . Es necesario que las familias hash de las que se eligen y sean independientes entre sí. ${\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 del flujo, agréguelo al depósito n.º del hash n.º. ${\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 secuencia. ${\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 habrá una desviación mayor del valor real, con probabilidad . ${\displaystyle r_{q}}$ ${\displaystyle 2m_{2}/{\sqrt {w}}}$ ${\displaystyle 1-e^{-O(t)}}$

Formulación vectorial

Alternativamente, Count-Sketch puede verse como una función de 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 reconstruirlo, tomamos . Esto ofrece las mismas garantías que las indicadas 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 bosquejo del tensor

La proyección del boceto de conteo del producto externo de dos vectores es equivalente a la convolución de dos bocetos de conteo de componentes.

El bosquejo de conteo calcula una convolución vectorial

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

Pham y Pagh ^[8] muestran que esto es igual a : un bosquejo de recuento del producto externo 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 los esquemas de recuento. Mediante el uso del producto de división de caras ^{[9] [10] [11],} dichas estructuras se pueden calcular mucho más rápido que las matrices normales.

Véase también

• El esquema 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).
• Bosquejo tensorial

Referencias

1. Faisal M. Algashaam; Kien Nguyen; Mohamed Alkanhal; Vinod Chandran; Wageeh Boles. "Clasificación periocular multiespectral con agrupamiento multilineal compacto multimodal" [1]. IEEE Access , vol. 5. 2017.
2. Ahle, Thomas; Knudsen, Jakob (3 de septiembre de 2019). "Bosquejo tensorial casi óptimo". ResearchGate . Consultado el 11 de julio de 2020 .
3. Charikar, Chen y Farach-Colton 2004.
4. Alon, Noga, Yossi Matias y Mario Szegedy. "La complejidad espacial de la aproximación de los momentos de frecuencia". Journal of Computer and system sciences 58.1 (1999): 137-147.
5. Moody, John. "Aprendizaje rápido en jerarquías de múltiples resoluciones". Avances en sistemas de procesamiento de información neuronal. 1989.
6. Woodruff, David P. "El boceto como herramienta para el álgebra lineal numérica". Theoretical Computer Science 10.1-2 (2014): 1–157.
7. Larsen, Kasper Green, Rasmus Pagh y Jakub Tětek. "CountSketches, Feature Hashing y la mediana de tres". Conferencia 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ícitas . Conferencia internacional SIGKDD sobre descubrimiento de conocimiento y minería de datos. Association for Computing Machinery. 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 de la red de antenas digitales basado en productos matriciales de división de caras" (PDF) . Proc. ICATT-97, Kyiv : 108–109.
11. Slyusar, VI (13 de marzo de 1998). "Una familia de productos faciales de matrices y sus propiedades" (PDF) . Análisis de sistemas y cibernética C/C de Kibernetika I Sistemnyi Analiz.- 1999 . 35 (3): 379–384. doi :10.1007/BF02733426. S2CID  119661450.

Lectura adicional

• Charikar, Moses; Chen, Kevin; Farach-Colton, Martin (2004). "Encontrar elementos frecuentes en flujos de datos" (PDF) . Theoretical Computer Science . 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 agrupamiento multilineal compacto multimodal" [1]. IEEE Access , vol. 5. 2017.
• Ahle, Thomas; Knudsen, Jakob (3 de septiembre de 2019). "Bosquejo tensorial casi óptimo". ResearchGate . Consultado el 11 de julio de 2020 .