Feature hashing for large scale multitask learning

By Kilian Q. Weinberger, Anirban Dasgupta, Josh Attenberg, J. Langford, Alex Smola. 2009

1,095 citations recorded by the source corpus.

Empirical evidence suggests that hashing is an effective strategy for dimensionality reduction and practical nonparametric estimation. In this paper we provide exponential tail bounds for feature hashing and show that the interaction between random subspaces is negligible with high probability. We demonstrate the feasibility of this approach with experimental results for a new use case --- multitask learning with hundreds of thousands of tasks.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Statistical Learning Theory

Citations in the corpus

Reading Wikipedia to Answer Open-Domain Questions (2017, methodology): “Our best performing system uses bigram counts while preserving speed and memory efficiency by using the hashing of (Weinberger et al., 2009) to map the bigrams to 224 bins with an unsigned murmur3 hash.”
Bag of Tricks for Efficient Text Classification (2016, methodology): “We maintain a fast and memory efﬁcient mapping of the n-grams by using the hashing trick (Weinberger et al., 2009) with the same hashing function as in Mikolov et al. (2011) and 10M bins if we only used bigrams, and 100M otherwise.”
Learning both Weights and Connections for Efficient Neural Network (2015, background): “[22], sparsity will minimize hash collision making feature hashing even more effective.”
Advances in Pre-Training Distributed Word Representations (2017, methodology): “We use the hashing trick to circumvent this issue (Weinberger et al., 2009).”
Compressing Neural Networks with the Hashing Trick (2015, methodology): “With the help of feature hashing (Weinberger et al., 2009), Vowpal Wabbit, a large-scale learning system, is able to scale to terafeature datasets (Agarwal et al.”
Marginalized Denoising Autoencoders for Domain Adaptation (2012, background): “Domain adaptation (Ben-David et al., 2009; Huang et al., 2007; Weinberger et al., 2009; Xue et al., 2008) aims to generalize a classiﬁer that is trained on a source domain, for which typically plenty of training data is available, to a target domain, for which data is scarce.”
A Survey on Multi-Task Learning (2017, background): “[162], multiple hashing functions are proposed to accelerate the joint learning of multiple tasks.”
Recent advances in convolutional neural networks (2015, methodology): “work shrinks the storage costs of neural networks signicantly while mostly preserves the generalization performance in image classication. As pointed out in Shi et al . [188] and Weinberger et al . [189], sparsity will minimize hash collision making feature hashing even more eective. HashNets may be”
Compressing Convolutional Neural Networks in the Frequency Domain (2015, methodology): “[6], who show that weights of fully connected networks can be effectively compressed with the hashing trick [60].”
Slow Learners are Fast (2009, methodology): “To deal with high-dimensional feature spaces we used hashing [20].”
A reliable effective terascale linear learning system (2011, background): “These features are hashed (Weinberger et al., 2009) and each training sample ends up being represented as sparse binary vector of dimension 2 24 with around 100 non-zero elements.”
Unsupervised Learning of Sentence Embeddings Using Compositional n-Gram Features (2017, methodology): “(Weinberger et al., 2009), with the same hashing function as used in FastText (Joulin et al.”
Practical and Optimal LSH for Angular Distance (2015, methodology): “Note that one can apply Lemma 2 from the arXiv version of [18] to claim that—after such a dimension reduction—the distance between any two points remains sufficiently concentrated for the bounds from Theorem 1 to still hold (with d replaced by d′).”
Ad click prediction: a view from the trenches (2013, background): “Notably, [31] report excellent results using the hashing trick to project a feature space capable of learning personalized spam filtering model down to a space of only 2(24) features, resulting in a model small enough to fit easily in RAM on one machine.”
Deep neural network based malware detection using two dimensional binary program features (2015, methodology): “Potentially the feature space can become large, in those cases methods like locality-sensitive hashing [21, 6], feature hashing (aka hashing “trick”) [34, 22], or random projections [23, 21, 15, 11] have been used in malware detection.”