Fully Understanding The Hashing Trick

Freksen Casper Benjamin, Kamma Lior, Larsen Kasper Green. Arxiv 2018

[Paper]    
ARXIV Independent

Feature hashing, also known as {\em the hashing trick}, introduced by Weinberger et al. (2009), is one of the key techniques used in scaling-up machine learning algorithms. Loosely speaking, feature hashing uses a random sparse projection matrix $A:{\mathbb{R}}^n\to {\mathbb{R}}^m$ (where $m\ll n$) in order to reduce the dimension of the data from $n$ to $m$ while approximately preserving the Euclidean norm. Every column of $A$ contains exactly one non-zero entry, equals to either $-1$ or $1$. Weinberger et al. showed tail bounds on \(|Ax|2^2\). Specifically they showed that for every $ϵ,\delta$, if \(|x|{\infty} / |x|2\) is sufficiently small, and $m$ is sufficiently large, then $$Pr[||Ax{|}_2^2-|x{|}_2^2|<ϵ|x{|}_2^2]\ge 1-\delta .$$TheseboundswerelaterextendedbyDasgupta\text{etal}(2010)andmostrecentlyrefinedbyDahlgaardetal.(2017),however,thetruenatureoftheperformanceofthiskeytechnique,andspecificallythecorrecttradeoffbetweenthepivotalparameters$|x|{\infty} / |x|_2, m, \epsilon, \delta$remainedanopenquestion.Wesettlethisquestionbygivingtightasymptoticboundsontheexacttradeoffbetweenthecentralparameters,thusprovidingacompleteunderstandingoftheperformanceoffeaturehashing.Wecomplementtheasymptoticboundwithempiricaldata,whichshowsthattheconstants“hiding”intheasymptoticnotationare,infact,verycloseto$1$, thus further illustrating the tightness of the presented bounds in practice.

Similar Work

• Fully Understanding The Hashing Trick
• Understanding Sparse JL For Feature Hashing
• A Framework For Similarity Search With Space-time Tradeoffs Using Locality-sensitive Filtering
• Quicksort Largest Bucket And Min-wise Hashing With Limited Independence