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

• John likes to watch movies.
• Mary likes movies too.
• John also likes football.

can be converted, using the dictionary

to the term-document matrix

${\displaystyle {\begin{pmatrix}{\textrm {John}}&{\textrm {likes}}&{\textrm {to}}&{\textrm {watch}}&{\textrm {movies}}&{\textrm {Mary}}&{\textrm {too}}&{\textrm {also}}&{\textrm {football}}\\1&1&1&1&1&0&0&0&0\\0&1&0&0&1&1&1&0&0\\1&1&0&0&0&0&0&1&1\end{pmatrix}}}$

(Punctuation was removed, as is usual in document classification and clustering.)

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.^[3] 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.^[4]

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 ${\displaystyle t}$ in a finite (or countably infinite) set ${\displaystyle T}$. Suppose we only need to process a finite corpus, then we can put all tokens appearing in the corpus into ${\displaystyle T}$, meaning that ${\displaystyle T}$ is finite. However, suppose we want to process all possible words made of the English letters, then ${\displaystyle T}$ is countably infinite.

Most neural networks can only operate on real vector inputs, so we must construct a "dictionary" function ${\displaystyle \phi :T\to \mathbb {R} ^{n}}$.

When ${\displaystyle T}$ is finite, of size ${\displaystyle |T|=m\leq n}$, then we can use one-hot encoding to map it into ${\displaystyle \mathbb {R} ^{n}}$. First, arbitrarily enumerate ${\displaystyle T=\{t_{1},t_{2},..,t_{m}\}}$, then define ${\displaystyle \phi (t_{i})=e_{i}}$. In other words, we assign a unique index ${\displaystyle i}$ to each token, then map the token with index ${\displaystyle i}$ to the unit basis vector ${\displaystyle e_{i}}$.

One-hot encoding is easy to interpret, but it requires one to maintain the arbitrary enumeration of ${\displaystyle T}$. Given a token ${\displaystyle t\in T}$, to compute ${\displaystyle \phi (t)}$, we must find out the index ${\displaystyle i}$ of the token ${\displaystyle t}$. Thus, to implement ${\displaystyle \phi }$ efficiently, we need a fast-to-compute bijection ${\displaystyle h:T\to \{1,...,m\}}$, then we have ${\displaystyle \phi (t)=e_{h(t)}}$.

In fact, we can relax the requirement slightly: It suffices to have a fast-to-compute injection ${\displaystyle h:T\to \{1,...,n\}}$, then use ${\displaystyle \phi (t)=e_{h(t)}}$.

In practice, there is no simple way to construct an efficient injection ${\displaystyle h:T\to \{1,...,n\}}$. However, we do not need a strict injection, but only an approximate injection. That is, when ${\displaystyle t\neq t'}$, we should probably have ${\displaystyle h(t)\neq h(t')}$, so that probably ${\displaystyle \phi (t)\neq \phi (t')}$.

At this point, we have just specified that ${\displaystyle h}$ should be a hashing function. Thus, ineluctably, we reach the idea of feature hashing.

Feature hashing (Weinberger et al. 2009)

The basic feature hashing algorithm presented in (Weinberger et al. 2009)^[2] is defined as follows.

First, one specifies two hash functions: the kernel hash ${\displaystyle h:T\to \{1,2,...,n\}}$, and the sign hash ${\displaystyle \zeta :T\to \{-1,+1\}}$. Next, one defines the feature hashing function:

$${\displaystyle \phi :T\to \mathbb {R} ^{n},\quad \phi (t)=\zeta (t)e_{h(t)}}$$

Finally, extend this feature hashing function to strings of tokens by

$${\displaystyle \phi :T^{*}\to \mathbb {R} ^{n},\quad \phi (t_{1},...,t_{k})=\sum _{j=1}^{k}\phi (t_{j})}$$

where ${\displaystyle T^{*}}$ is the set of all finite strings consisting of tokens in ${\displaystyle T}$. Equivalently,

$${\displaystyle \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}}$$

Geometric properties

We want to say something about the geometric property of ${\displaystyle \phi }$, but ${\displaystyle 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 ${\displaystyle T\to \mathbb {R} ^{T}}$, and lift ${\displaystyle \phi }$ from ${\displaystyle \phi :T\to \mathbb {R} ^{n}}$ to ${\displaystyle \phi$ :\mathbb {R} ^{T}\to \mathbb {R} ^{n}} by linear extension:

$${\displaystyle \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 ${\displaystyle \mathbb {R} ^{T}}$ to contain only vectors with finite support: ${\displaystyle \forall (x_{t})_{t\in T}\in \mathbb {R} ^{T}}$, only finitely many entries of ${\displaystyle (x_{t})_{t\in T}}$ are nonzero. Define an inner product on ${\displaystyle \mathbb {R} ^{T}}$ in the obvious way:

$${\displaystyle \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 ${\displaystyle T}$ is infinite, then the inner product space ${\displaystyle \mathbb {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 ${\displaystyle \phi$ :\mathbb {R} ^{T}\to \mathbb {R} ^{n}} .

First, we can see why ${\displaystyle h}$ is called a "kernel hash": it allows us to define a kernel ${\displaystyle K:T\times T\to \mathbb {R} }$ by

$${\displaystyle K(t,t')=\langle e_{h(t)},e_{h(t')}\rangle }$$

In the language of the "kernel trick", ${\displaystyle K}$ is the kernel generated by the "feature map"

$${\displaystyle \varphi :T\to \mathbb {R} ^{n},\quad \varphi (t)=e_{h(t)}}$$

Note that this is not the feature map we were using, which is ${\displaystyle \phi (t)=\zeta (t)e_{h(t)}}$. In fact, we have been using another kernel ${\displaystyle K_{\zeta }:T\times T\to \mathbb {R} }$, defined by

$${\displaystyle K_{\zeta }(t,t')=\langle \zeta (t)e_{h(t)},\zeta (t')e_{h(t')}\rangle }$$

The benefit of augmenting the kernel hash ${\displaystyle h}$ with the binary hash ${\displaystyle \zeta }$ is the following theorem, which states that ${\displaystyle \phi }$ is an isometry "on average".

Theorem (intuitively stated) — If the binary hash ${\displaystyle \zeta }$ is unbiased (meaning that it takes value ${\displaystyle -1,+1}$ with equal probability), then ${\displaystyle \phi$ :\mathbb {R} ^{T}\to \mathbb {R} ^{n}} is an isometry in expectation:

$${\displaystyle \mathbb {E} [\langle \phi (x),\phi (x')\rangle ]=\langle x,x'\rangle .}$$

Proof By linearity of expectation,

$${\displaystyle \mathbb {E} [\langle \phi (x),\phi (x')\rangle ]=\sum _{t,t'\in T}(x_{t}x'_{t'})\cdot \mathbb {E} [\zeta (t)\zeta (t')]\cdot \langle e_{h(t)},e_{h(t')}\rangle }$$

Now, ${\displaystyle \mathbb {E} [\zeta (t)\zeta (t')]={\begin{cases}1\quad {\text{ if }}t=t'\\0\quad {\text{ if }}t\neq t'\\\end{cases}}}$, since we assumed ${\displaystyle \zeta }$ is unbiased. So we continue

$${\displaystyle \mathbb {E} [\langle \phi (x),\phi (x')\rangle ]=\sum _{t\in T}(x_{t}x'_{t})\langle e_{h(t)},e_{h(t)}\rangle =\langle x,x'\rangle }$$

The above statement and proof interprets the binary hash function ${\displaystyle \zeta }$ not as a deterministic function of type ${\displaystyle T\to \{-1,+1\}}$, but as a random binary vector ${\displaystyle \{-1,+1\}^{T}}$ with unbiased entries, meaning that ${\displaystyle Pr(\zeta (t)=+1)=Pr(\zeta (t)=-1)={\frac {1}{2}}}$ for any ${\displaystyle t\in T}$.

This is a good intuitive picture, though not rigorous. For a rigorous statement and proof, see ^[2]

 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

 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

Extensions and variations