Count sketch

Part of a series on
Machine learning and data mining
Problems Classification Clustering Regression Anomaly detection Data Cleaning AutoML Association rules Reinforcement learning Structured prediction Feature engineering Feature learning Online learning Semi-supervised learning Unsupervised learning Learning to rank Grammar induction
Supervised learning (classification • regression) Decision trees Ensembles Bagging Boosting Random forest k-NN Linear regression Naive Bayes Artificial neural networks Logistic regression Perceptron Relevance vector machine (RVM) Support vector machine (SVM)
Clustering BIRCH CURE Hierarchical k-means Expectation–maximization (EM) DBSCAN OPTICS Mean shift
Dimensionality reduction Factor analysis CCA ICA LDA NMF PCA PGD t-SNE
Structured prediction Graphical models Bayes net Conditional random field Hidden Markov
Anomaly detection k-NN Local outlier factor
Artificial neural network Autoencoder Cognitive computing Deep learning DeepDream Multilayer perceptron RNN LSTM GRU ESN Restricted Boltzmann machine GAN SOM Convolutional neural network U-Net Transformer Vision Spiking neural network Memtransistor Electrochemical RAM (ECRAM)
Reinforcement learning Q-learning SARSA Temporal difference (TD)
Theory Kernel machines Bias–variance tradeoff Computational learning theory Empirical risk minimization Occam learning PAC learning Statistical learning VC theory
Machine-learning venues NeurIPS ICML ML JMLR ArXiv:cs.LG
Related articles Glossary of artificial intelligence List of datasets for machine-learning research Outline of machine learning
v t

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 by Alon, Matias and Szegedy for approximating the frequency moments of streams.^[4]

The sketch is nearly identical 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 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]

Mathematical definition[]

1. For constants ${\displaystyle w}$ and ${\displaystyle d}$ (to be defined later) independently choose ${\displaystyle 2d}$ 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_{ij}=\sum _{h_{i}(k)=j}s_{i}(k).}$

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

${\displaystyle {\text{median}}_{i}\,s_{i}(q)\cdot C_{i,h_{i}(q)}.}$

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^[7] 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^[8][9][10] such structures can be computed much faster than normal matrices.

See also[]

• Count–min sketch
• Tensorsketch

References[]

Further reading[]

• 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.