Feature hashing

Uses your system voice; voice and rate in settings.

Snapshot

≈ 8 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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

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

When T is finite, of size |T| = m \leq n , then we can use one-hot encoding to map it into \R^n . First, arbitrarily enumerate T = \{t_1, t_2, .., t_m\} , then define \phi(t_i) = e_i . In other words, we assign a unique index i to each token, then map the token with index i to the unit basis vector e_i . One-hot encoding is easy to interpret, but it requires one to maintain the arbitrary enumeration of T . Given a token t\in T , to compute \phi(t) , we must find out the index i of the token t . Thus, to implement \phi efficiently, we need a fast-to-compute bijection h: T\to \{1, ..., m\} , then we have \phi(t) = e_{h(t)} . In fact, we can relax the requirement slightly: It suffices to have a fast-to-compute injection h: T\to \{1, ..., n\} , then use \phi(t) = e_{h(t)} . In practice, there is no simple way to construct an efficient injection h: T\to \{1, ..., n\} . However, we do not need a strict injection, but only an approximate injection. That is, when t\neq t' , we should probably have h(t) \neq h(t') , so that probably \phi(t) \neq \phi(t') . At this point, we have just specified that h should be a hashing function. Thus we reach the idea of feature hashing.

Algorithms

First, one specifies two hash functions: the kernel hash h: T\to \{1, 2, ..., n\} , and the sign hash \zeta: T\to \{-1, +1\} . Next, one defines the feature hashing function: \phi: T\to \R^n, \quad \phi(t) = \zeta(t) e_{h(t)} Finally, extend this feature hashing function to strings of tokens by \phi: T^* \to \R^n, \quad \phi(t_1, ..., t_k) =\sum_{j=1}^k \phi(t_j) where T^* is the set of all finite strings consisting of tokens in T . Equivalently, \phi(t_1, ..., t_k) = \sum_{j=1}^k \zeta(t_j) e_{h(t_j)} = \sum_{i=1}^n \left(\sum_{j: h(t_j)=i} \zeta(t_j)\right) e_i We want to say something about the geometric property of \phi , but T , 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 T\to \R^T , and lift \phi from \phi: T \to \R^n to \phi: \R^T \to \R^n by linear extension: \phi((x_t)_{t\in T}) = \sum_{t\in T} x_t \zeta(t) e_{h(t)} = \sum_{i=1}^n \left(\sum_{t: h(t)=i} x_t \zeta(t)\right) e_i There 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 \R^T to contain only vectors with finite support: \forall (x_t)_{t\in T} \in \R^T , only finitely many entries of (x_t)_{t\in T} are nonzero. Define an inner product on \R^T in the obvious way: \langle e_t, e_{t'} \rangle = \begin{cases} 1, \text{ if }t=t', \\ 0, \text{ else.} \end{cases} \quad \langle x, x'\rangle = \sum_{t, t'\in T} x_t x_{t'} \langle e_t, e_{t'} \rangle As a side note, if T is infinite, then the inner product space \R^T 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 \phi: \R^T \to \R^n . First, we can see why h is called a "kernel hash": it allows us to define a kernel K: T\times T \to \R by K(t, t') = \langle e_{h(t)}, e_{h(t')}\rangle In the language of the "kernel trick", K is the kernel generated by the "feature map" \varphi : T \to \R^n, \quad \varphi(t) = e_{h(t)} Note that this is not the feature map we were using, which is \phi(t) = \zeta(t) e_{h(t)} . In fact, we have been using another kernel K_{\zeta}: T\times T \to \R , defined by K_\zeta (t, t') = \langle \zeta(t)e_{h(t)}, \zeta(t')e_{h(t')}\rangle The benefit of augmenting the kernel hash h with the binary hash \zeta is the following theorem, which states that \phi is an isometry "on average". The above statement and proof interprets the binary hash function \zeta not as a deterministic function of type T\to \{-1, +1\} , but as a random binary vector \{-1, +1\}^T with unbiased entries, meaning that Pr(\zeta(t) = +1) = Pr(\zeta(t) = -1) = \frac 1 2 for any t\in T . This is a good intuitive picture, though not rigorous. For a rigorous statement and proof, see 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 h(x_f)=1 if x_f is "cat" and 2 if x_f is "dog". Let us take the output feature vector dimension ( ) to be 4. Then output 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 (h, \zeta) 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

Feature hashing generally suffers from hash collision, which means that there exist pairs of different tokens with the same hash: t\neq t', \phi(t) = \phi(t') = v . A machine learning model trained on feature-hashed words would then have difficulty distinguishing t and t' , essentially because v is polysemic. If t' is rare, then performance degradation is small, as the model could always just ignore the rare case, and pretend all v means t . 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.

Implementations

Implementations of the hashing trick are present in: Apache Mahout Gensim scikit-learn sofia-ml Vowpal Wabbit Apache Spark R TensorFlow Dask-ML

See also

References

External links

Hashing Representations for Machine Learning on John Langford's website What is the "hashing trick"? - MetaOptimize Q+A

Text derived from https://en.wikipedia.org/w/index.php?oldid=1314772715 under CC BY-SA 4.0; modifications have been made.

References

  1. ↩Wikipedia publication date (×1) · confidence 0.95 https://en.wikipedia.org/w/index.php?oldid=1314772715