Vectorizing features using a hash function
In machine learning, feature hashing, also known as the hashing trick (by analogy to the kernel trick), is a fast and space-efficient way of vectorizing features, i.e. turning arbitrary features into indices in a vector or matrix. It works by applying a hash function to the features and using their hash values as indices directly (after a modulo operation), rather than looking the indices up in an associative array. In addition to its use for encoding non-numeric values, feature hashing can also be used for dimensionality reduction. 
This trick is often attributed to Weinberger et al. (2009), but there exists a much earlier description of this method published by John Moody in 1989.
Motivation.
Motivating example.
In a typical document classification task, the input to the machine learning algorithm (both during learning and classification) is free text. From this, a bag of words (BOW) representation is constructed: the individual tokens are extracted and counted, and each distinct token in the training set defines a feature (independent variable) of each of the documents in both the training and test sets.
Machine learning algorithms, however, are typically defined in terms of numerical vectors. Therefore, the bags of words for a set of documents is regarded as a term-document matrix where each row is a single document, and each column is a single feature/word; the entry "i", "j" in such a matrix captures the frequency (or weight) of the j'th term of the "vocabulary" in document i. (An alternative convention swaps the rows and columns of the matrix, but this difference is immaterial.)
Typically, these vectors are extremely sparse—according to Zipf's law.
The common approach is to construct, at learning time or prior to that, a "dictionary" representation of the vocabulary of the training set, and use that to map words to indices. Hash tables and tries are common candidates for dictionary implementation. E.g., the three documents
can be converted, using the dictionary
to the term-document matrix
formula_1
The problem with this process is that such dictionaries take up a large amount of storage space and grow in size as the training set grows. On the contrary, if the vocabulary is kept fixed and not increased with a growing training set, an adversary may try to invent new words or misspellings that are not in the stored vocabulary so as to circumvent a machine learned filter. To address this challenge, Yahoo! Research attempted to use feature hashing for their spam filters.
Note that the hashing trick isn't limited to text classification and similar tasks at the document level, but can be applied to any problem that involves large (perhaps unbounded) numbers of features.
Mathematical motivation.
Mathematically, a token is an element formula_2 in a finite (or countably infinite) set formula_3. Suppose we only need to process a finite corpus, then we can put all tokens appearing in the corpus into formula_3, meaning that formula_3 is finite. However, suppose we want to process all possible words made of the English letters, then formula_3 is countably infinite.
Most neural networks can only operate on real vector inputs, so we must construct a "dictionary" function formula_7.
When formula_3 is finite, of size formula_9, then we can use one-hot encoding to map it into formula_10. First, "arbitrarily" enumerate formula_11, then define formula_12. In other words, we assign a unique index formula_13 to each token, then map the token with index formula_13 to the unit basis vector formula_15. 
One-hot encoding is easy to interpret, but it requires one to maintain the arbitrary enumeration of formula_3. Given a token formula_17, to compute formula_18, we must find out the index formula_13 of the token formula_2. Thus, to implement formula_21 efficiently, we need a fast-to-compute bijection formula_22, then we have formula_23.
In fact, we can relax the requirement slightly: It suffices to have a fast-to-compute "injection" formula_24, then use formula_23.
In practice, there is no simple way to construct an efficient injection formula_24. However, we do not need a strict injection, but only an "approximate" injection. That is, when formula_27, we should "probably" have formula_28, so that "probably" formula_29. 
At this point, we have just specified that formula_30 should be a hashing function. Thus we reach the idea of feature hashing.
Algorithms.
Feature hashing (Weinberger et al. 2009).
The basic feature hashing algorithm presented in (Weinberger et al. 2009) is defined as follows.
First, one specifies two hash functions: the kernel hash formula_31, and the sign hash formula_32. Next, one defines the feature hashing function:formula_33Finally, extend this feature hashing function to strings of tokens byformula_34where formula_35 is the set of all finite strings consisting of tokens in formula_3.
Equivalently,formula_37 
Geometric properties.
We want to say something about the geometric property of formula_38, but formula_39, by itself, is just a set of tokens, we cannot impose a geometric structure on it except the discrete topology, which is generated by the discrete metric. To make it nicer, we lift it to formula_40, and lift formula_38 from formula_42 to formula_43 by linear extension: formula_44There is an infinite sum there, which must be handled at once. There are essentially only two ways to handle infinities. One may impose a metric, then take its completion, to allow well-behaved infinite sums, or one may demand that nothing is actually infinite, only potentially so. Here, we go for the potential-infinity way, by restricting formula_45 to contain only vectors with finite support: formula_46, only finitely many entries of formula_47 are nonzero.
Define an inner product on formula_45 in the obvious way: formula_49As a side note, if formula_39 is infinite, then the inner product space formula_45 is not complete. Taking its completion would get us to a Hilbert space, which allows well-behaved infinite sums.
Now we have an inner product space, with enough structure to describe the geometry of the feature hashing function formula_43.
First, we can see why formula_53 is called a "kernel hash": it allows us to define a kernel formula_54 byformula_55In the language of the "kernel trick", formula_56 is the kernel generated by the "feature map" formula_57Note that this is not the feature map we were using, which is formula_58. In fact, we have been using "another kernel" formula_59, defined by formula_60The benefit of augmenting the kernel hash formula_53 with the binary hash formula_62 is the following theorem, which states that formula_63 is an isometry "on average".
 ;templatestyles src="Math_theorem/styles.css" / ;
Theorem (intuitively stated) — If the binary hash formula_62 is unbiased (meaning that it takes value formula_65 with equal probability), then formula_43 is an isometry in expectation:formula_67
 ;templatestyles src="Math_proof/styles.css" / ;Proof
By linearity of expectation, formula_68Now, formula_69, since we assumed formula_62 is unbiased. So we continueformula_71
The above statement and proof interprets the binary hash function formula_62 not as a deterministic function of type formula_73, but as a random binary vector formula_74 with unbiased entries, meaning that formula_75 for any formula_76.
This is a good intuitive picture, though not rigorous. For a rigorous statement and proof, see 
Pseudocode implementation.
Instead of maintaining a dictionary, a feature vectorizer that uses the hashing trick can build a vector of a pre-defined length by applying a hash function h to the features (e.g., words), then using the hash values directly as feature indices and updating the resulting vector at those indices. Here, we assume that feature actually means feature vector. 
 function hashing_vectorizer(features : array of string, N : integer):
 x := new vector[N]
 for f in features:
 h := hash(f)
 x[h mod N] += 1
 return x
Thus, if our feature vector is ["cat","dog","cat"] and hash function is formula_77 if formula_78 is "cat" and formula_79 if formula_78 is "dog". Let us take the output feature vector dimension (N) to be 4. Then output x will be [0,2,1,0].
It has been suggested that a second, single-bit output hash function ξ be used to determine the sign of the update value, to counter the effect of hash collisions. If such a hash function is used, the algorithm becomes
 function hashing_vectorizer(features : array of string, N : integer):
 x := new vector[N]
 for f in features:
 h := hash(f)
 idx := h mod N
 if ξ(f) == 1:
 x[idx] += 1
 else:
 x[idx] -= 1
 return x
The above pseudocode actually converts each sample into a vector. An optimized version would instead only generate a stream of formula_81 pairs and let the learning and prediction algorithms consume such streams; a linear model can then be implemented as a single hash table representing the coefficient vector.
Extensions and variations.
Learned feature hashing.
Feature hashing generally suffers from hash collision, which means that there exist pairs of different tokens with the same hash: formula_82. A machine learning model trained on feature-hashed words would then have difficulty distinguishing formula_83 and formula_84, essentially because formula_85 is polysemic. 
If formula_84 is rare, then performance degradation is small, as the model could always just ignore the rare case, and pretend all formula_85 means formula_83. However, if both are common, then the degradation can be serious.
To handle this, one can train supervised hashing functions that avoids mapping common tokens to the same feature vectors.
Applications and practical performance.
Ganchev and Dredze showed that in text classification applications with random hash functions and several tens of thousands of columns in the output vectors, feature hashing need not have an adverse effect on classification performance, even without the signed hash function.
Weinberger et al. (2009) applied their version of feature hashing to multi-task learning, and in particular, spam filtering, where the input features are pairs (user, feature) so that a single parameter vector captured per-user spam filters as well as a global filter for several hundred thousand users, and found that the accuracy of the filter went up.
Chen et al. (2015) combined the idea of feature hashing and sparse matrix to construct "virtual matrices": large matrices with small storage requirements. The idea is to treat a matrix formula_89 as a dictionary, with keys in formula_90, and values in formula_91. Then, as usual in hashed dictionaries, one can use a hash function formula_92, and thus represent a matrix as a vector in formula_93, no matter how big formula_94 is. With virtual matrices, they constructed "HashedNets", which are large neural networks taking only small amounts of storage.
Implementations.
Implementations of the hashing trick are present in:
References.
 ;templatestyles src="Reflist/styles.css" / ;