Count sketch

Count sketch is a type of dimensionality reduction that is particularly efficient in statistics, machine learning and algorithms.^[1][2] It was invented by Moses Charikar, Kevin Chen and Martin Farach-Colton^[3] in an effort to speed up the AMS Sketch by Alon, Matias and Szegedy for approximating the frequency moments of streams^[4] (these calculations require counting of the number of occurrences for the distinct elements of the stream).

The sketch is nearly identical^{[citation needed]} to the Feature hashing algorithm by John Moody,^[5] but differs in its use of hash functions with low dependence, which makes it more practical. In order to still have a high probability of success, the median trick is used to aggregate multiple count sketches, rather than the mean.

These properties allow use for explicit kernel methods, bilinear pooling in neural networks and is a cornerstone in many numerical linear algebra algorithms.^[6]

Intuitive explanation

The inventors of this data structure offer the following iterative explanation of its operation:^[3]

• at the simplest level, the output of a single hash function s mapping stream elements q into {+1, -1} is feeding a single up/down counter C. After a single pass over the data, the frequency ${\displaystyle n(q)}$  of a stream element q can be approximated, although extremely poorly, by the expected value ${\displaystyle {\mathbf {E}}[C\cdot s(q)]}$ ;
• a straightforward way to improve the variance of the previous estimate is to use an array of different hash functions ${\displaystyle s_{i}}$ , each connected to its own counter ${\displaystyle C_{i}}$ . For each element q, the ${\displaystyle {\mathbf {E}}[C_{i}\cdot s_{i}(q)]=n(q)}$  still holds, so averaging across the i range will tighten the approximation;
• the previous construct still has a major deficiency: if a lower-frequency-but-still-important output element a exhibits a hash collision with a high-frequency element, ${\displaystyle n(a)}$  estimate can be significantly affected. Avoiding this requires reducing the frequency of collision counter updates between any two distinct elements. This is achieved by replacing each ${\displaystyle C_{i}}$  in the previous construct with an array of m counters (making the counter set into a two-dimensional matrix ${\displaystyle C_{i,j}}$ ), with index j of a particular counter to be incremented/decremented selected via another set of hash functions ${\displaystyle h_{i}}$  that map element q into the range {1..m}. Since ${\displaystyle {\mathbf {E}}[C_{i,h_{i}(q)}\cdot s_{i}(q)]=n(q)}$ , averaging across all values of i will work.

Mathematical definition

1. For constants ${\displaystyle w}$  and ${\displaystyle t}$  (to be defined later) independently choose ${\displaystyle d=2t+1}$  random hash functions ${\displaystyle h_{1},\dots ,h_{d}}$  and ${\displaystyle s_{1},\dots ,s_{d}}$  such that ${\displaystyle h_{i}:[n]\to [w]}$  and ${\displaystyle s_{i}:[n]\to \{\pm 1\}}$ . It is necessary that the hash families from which ${\displaystyle h_{i}}$  and ${\displaystyle s_{i}}$  are chosen be pairwise independent.

2. For each item ${\displaystyle q_{i}}$  in the stream, add ${\displaystyle s_{j}(q_{i})}$  to the ${\displaystyle h_{j}(q_{i})}$ th bucket of the ${\displaystyle j}$ th hash.

At the end of this process, one has ${\displaystyle wd}$  sums ${\displaystyle (C_{ij})}$  where

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

To estimate the count of ${\displaystyle q}$ s one computes the following value:

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

The values ${\displaystyle s_{i}(q)\cdot C_{i,h_{i}(q)}}$  are unbiased estimates of how many times ${\displaystyle q}$  has appeared in the stream.

The estimate ${\displaystyle r_{q}}$  has variance ${\displaystyle O(\mathrm {min} \{m_{1}^{2}/w^{2},m_{2}^{2}/w\})}$ , where ${\displaystyle m_{1}}$  is the length of the stream and ${\displaystyle m_{2}^{2}}$  is ${\displaystyle \sum _{q}(\sum _{i}[q_{i}=q])^{2}}$ .^[7]

Furthermore, ${\displaystyle r_{q}}$  is guaranteed to never be more than ${\displaystyle 2m_{2}/{\sqrt {w}}}$  off from the true value, with probability ${\displaystyle 1-e^{-O(t)}}$ .

Vector formulation

Alternatively Count-Sketch can be seen as a linear mapping with a non-linear reconstruction function. Let ${\displaystyle M^{(i\in [d])}\in \{-1,0,1\}^{w\times n}}$ , be a collection of ${\displaystyle d=2t+1}$  matrices, defined by

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

for ${\displaystyle j\in [w]}$  and 0 everywhere else.

Then a vector ${\displaystyle v\in \mathbb {R} ^{n}}$  is sketched by ${\displaystyle C^{(i)}=M^{(i)}v\in \mathbb {R} ^{w}}$ . To reconstruct ${\displaystyle v}$  we take ${\displaystyle v_{j}^{*}={\text{median}}_{i}C_{j}^{(i)}s_{i}(j)}$ . This gives the same guarantees as stated above, if we take ${\displaystyle m_{1}=\|v\|_{1}}$  and ${\displaystyle m_{2}=\|v\|_{2}}$ .

Relation to Tensor sketch

The count sketch projection of the outer product of two vectors is equivalent to the convolution of two component count sketches.

The count sketch computes a vector convolution

${\displaystyle C^{(1)}x\ast C^{(2)}x^{T}}$ , where ${\displaystyle C^{(1)}}$  and ${\displaystyle C^{(2)}}$  are independent count sketch matrices.

Pham and Pagh^[8] show that this equals ${\displaystyle C(x\otimes x^{T})}$  – a count sketch ${\displaystyle C}$  of the outer product of vectors, where ${\displaystyle \otimes }$  denotes Kronecker product.

The fast Fourier transform can be used to do fast convolution of count sketches. By using the face-splitting product^[9][10][11] such structures can be computed much faster than normal matrices.

See also

• Count–min sketch is a version of algorithm with smaller memory requirements (and weaker error guarantees as a tradeoff).
• Tensorsketch

References

1. Faisal M. Algashaam; Kien Nguyen; Mohamed Alkanhal; Vinod Chandran; Wageeh Boles. "Multispectral Periocular Classification WithMultimodal Compact Multi-Linear Pooling" [1]. IEEE Access, Vol. 5. 2017.
2. Ahle, Thomas; Knudsen, Jakob (2019-09-03). "Almost Optimal Tensor Sketch". ResearchGate. Retrieved 2020-07-11.
3. Charikar, Chen & Farach-Colton 2004.
4. Alon, Noga, Yossi Matias, and Mario Szegedy. "The space complexity of approximating the frequency moments." Journal of Computer and system sciences 58.1 (1999): 137-147.
5. Moody, John. "Fast learning in multi-resolution hierarchies." Advances in neural information processing systems. 1989.
6. Woodruff, David P. "Sketching as a Tool for Numerical Linear Algebra." Theoretical Computer Science 10.1-2 (2014): 1–157.
7. Larsen, Kasper Green, Rasmus Pagh, and Jakub Tětek. "CountSketches, Feature Hashing and the Median of Three." International Conference on Machine Learning. PMLR, 2021.
8. Ninh, Pham; Pagh, Rasmus (2013). Fast and scalable polynomial kernels via explicit feature maps. SIGKDD international conference on Knowledge discovery and data mining. Association for Computing Machinery. doi:10.1145/2487575.2487591.
9. Slyusar, V. I. (1998). "End products in matrices in radar applications" (PDF). Radioelectronics and Communications Systems. 41 (3): 50–53.
10. Slyusar, V. I. (1997-05-20). "Analytical model of the digital antenna array on a basis of face-splitting matrix products" (PDF). Proc. ICATT-97, Kyiv: 108–109.
11. Slyusar, V. I. (March 13, 1998). "A Family of Face Products of Matrices and its Properties" (PDF). Cybernetics and Systems Analysis C/C of Kibernetika I Sistemnyi Analiz.- 1999. 35 (3): 379–384. doi:10.1007/BF02733426. S2CID 119661450.

Further reading

• Charikar, Moses; Chen, Kevin; Farach-Colton, Martin (2004). "Finding frequent items in data streams" (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. "Multispectral Periocular Classification WithMultimodal Compact Multi-Linear Pooling" [1]. IEEE Access, Vol. 5. 2017.
• Ahle, Thomas; Knudsen, Jakob (2019-09-03). "Almost Optimal Tensor Sketch". ResearchGate. Retrieved 2020-07-11.