View source for Feature hashing

{{short description|Vectorizing features using a hash function}}
In [[Machine learning|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 [[Feature (machine learning)|features]], i.e. turning arbitrary features into indices in a vector or matrix.<ref name="Moody">{{cite journal |last1=Moody |first1=John |title=Fast learning in multi-resolution hierarchies |journal=Advances in Neural Information Processing Systems |date=1989 |url=http://papers.nips.cc/paper/175-fast-learning-in-multi-resolution-hierarchies.pdf}}</ref><ref name="Weinberger"/> It works by applying a [[Hash function|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|associative array]]. In addition to its use for encoding non-numeric values, feature hashing can also be used for [[Dimensionality reduction|dimensionality reduction]].<ref name="Weinberger" /> 

This trick is often attributed to Weinberger et al. (2009),<ref name="Weinberger" /> but there exists a much earlier description of this method published by John Moody in 1989.<ref name="Moody" />

==Motivation==

=== Motivating example ===
In a typical [[Document classification|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 [[Philosophy:Type–token distinction|tokens]] are extracted and counted, and each distinct token in the training set defines a [[Feature (machine learning)|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 {{math|''i'', ''j''}} in such a matrix captures the frequency (or weight) of the {{mvar|j}}'th term of the ''vocabulary'' in document {{mvar|i}}. (An alternative convention swaps the rows and columns of the matrix, but this difference is immaterial.)
Typically, these vectors are extremely [[Sparse matrix|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 table]]s and [[Trie|trie]]s 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

{| class="wikitable"
|-
! Term !! Index
|-
| John || 1
|-
| likes || 2
|-
| to || 3
|-
| watch || 4
|-
| movies || 5
|-
| Mary || 6
|-
| too || 7
|-
| also || 8
|-
| football || 9
|}

to the term-document matrix

:<math>
\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}
</math>

(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.<ref name="mobilenlp">{{cite conference |author1=K. Ganchev |author2=M. Dredze |year=2008 |url=http://www.cs.jhu.edu/~mdredze/publications/mobile_nlp_feature_mixing.pdf |title=Small statistical models by random feature mixing |conference=Proc. ACL08 HLT Workshop on Mobile Language Processing}}</ref>  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, [[Organization:Yahoo! Research|Yahoo! Research]] attempted to use feature hashing for their spam filters.<ref>{{cite journal |author1=Josh Attenberg |author2=Kilian Weinberger |author3=Alex Smola |author4=Anirban Dasgupta |author5=Martin Zinkevich |title=Collaborative spam filtering with the hashing trick |journal=Virus Bulletin |year=2009|url=https://www.virusbulletin.com/virusbulletin/2009/11/collaborative-spam-filtering-hashing-trick}}</ref>

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

Most neural networks can only operate on real vector inputs, so we must construct a "dictionary" function <math>\phi: T\to \R^n</math>.

When <math>T </math> is finite, of size <math>|T| = m \leq n</math>, then we can use one-hot encoding to map it into <math>\R^n</math>. First, ''arbitrarily'' enumerate <math>T = \{t_1, t_2, .., t_m\} </math>, then define <math>\phi(t_i) = e_i </math>. In other words, we assign a unique index <math>i </math> to each token, then map the token with index <math>i </math> to the unit basis vector <math>e_i </math>. 

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

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

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

At this point, we have just specified that <math>h </math> should be a hashing function. Thus, ineluctably, 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)<ref name="Weinberger" /> is defined as follows.

First, one specifies two hash functions: the '''kernel hash''' <math>h: T\to \{1, 2, ..., n\}</math>, and the '''sign hash''' <math>\zeta: T\to \{-1, +1\} </math>. Next, one defines the feature hashing function:<math display="block">\phi: T\to \R^n, \quad \phi(t) = \zeta(t) e_{h(t)} </math>Finally, extend this feature hashing function to strings of tokens by<math display="block">\phi: T^* \to \R^n, \quad \phi(t_1, ..., t_k) =\sum_{j=1}^k \phi(t_j) </math>where <math>T^* </math> is the set of [[Kleene star|all finite strings consisting of tokens]] in <math>T </math>.

Equivalently,<math display="block">\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  </math> 

==== Geometric properties ====
We want to say something about the geometric property of <math>\phi</math>, but <math>T</math>, 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|discrete metric]]. To make it nicer, we lift it to <math>T\to \R^T</math>, and lift <math>\phi</math> from <math>\phi: T \to \R^n</math> to <math>\phi: \R^T \to \R^n</math> by linear extension: <math display="block">\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 </math>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 [[Complete metric space|completion]], to allow well-behaved infinite sums, or one may demand that nothing is [[Philosophy:Actual infinity|actually infinite, only potentially so]]. Here, we go for the potential-infinity way, by restricting <math>\R^T</math> to contain only vectors with finite support: <math>\forall (x_t)_{t\in T} \in \R^T</math>, only finitely many entries of <math>(x_t)_{t\in T}</math> are nonzero.

Define an [[Inner product space|inner product]] on <math>\R^T</math> in the obvious way: <math display="block">\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</math>As a side note, if <math>T</math> is infinite, then the inner product space <math>\R^T</math> is not [[Complete metric space|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 <math>\phi: \R^T \to \R^n</math>.

First, we can see why <math> h</math> is called a "'''kernel hash'''": it allows us to define a [[Kernel method|kernel]] <math> K: T\times T \to \R</math> by<math display="block"> K(t, t') = \langle e_{h(t)}, e_{h(t')}\rangle</math>In the language of the "kernel trick", <math> K</math> is the kernel generated by the "feature map" <math display="block"> \varphi : T \to \R^n, \quad \varphi(t) = e_{h(t)}</math>Note that this is not the feature map we were using, which is <math>\phi(t) = \zeta(t) e_{h(t)} </math>. In fact, we have been using  ''another kernel'' <math> K_{\zeta}: T\times T \to \R</math>, defined by <math display="block"> K_\zeta (t, t') = \langle \zeta(t)e_{h(t)}, \zeta(t')e_{h(t')}\rangle</math>The benefit of augmenting the kernel hash <math> h</math> with the binary hash <math> \zeta</math> is the following theorem, which states that <math> \phi</math> is an isometry "on average".

{{Math theorem
| name = Theorem (intuitively stated)
| math_statement = If the binary hash <math> \zeta</math> is unbiased (meaning that it takes value <math> -1, +1</math> with equal probability), then <math>\phi: \R^T \to \R^n</math> is an isometry in expectation:<math display="block"> \mathbb{E}[\langle \phi(x), \phi(x') \rangle] = \langle x, x' \rangle.</math>
}}{{Proof| proof=

By linearity of expectation, <math display="block"> \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</math>Now, <math> \mathbb{E}[\zeta(t)\zeta(t')] =\begin{cases}
1 \quad \text{ if }t=t'\\
0 \quad \text{ if }t \neq t'\\
\end{cases}</math>, since we assumed <math> \zeta</math> is unbiased. So we continue<math display="block"> \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</math>

|title=Proof}}



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

This is a good intuitive picture, though not rigorous. For a rigorous statement and proof, see <ref name="Weinberger" />

==== 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 {{mvar|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. 
<source lang="pascal">
 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
</source>
Thus, if our feature vector is ["cat","dog","cat"] and hash function is <math> h(x_f)=1</math> if <math>x_f</math> is "cat" and <math>2</math> if <math>x_f</math> is "dog". Let us take the output feature vector dimension ({{mono|N}}) to be 4. Then output {{mono|x}} will be [0,2,1,0].
It has been suggested that a second, single-bit output hash function {{mvar|ξ}} be used to determine the sign of the update value, to counter the effect of [[Hash table#Collision resolution|hash collision]]s.<ref name="Weinberger">{{cite conference |author1=Kilian Weinberger |author2=Anirban Dasgupta |author3=John Langford |author4=Alex Smola |author5=Josh Attenberg |year=2009 |url=http://alex.smola.org/papers/2009/Weinbergeretal09.pdf |title=Feature Hashing for Large Scale Multitask Learning |conference=Proc. ICML}}</ref> If such a hash function is used, the algorithm becomes
<source lang="pascal">
 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
</source>

The above pseudocode actually converts each sample into a vector. An optimized version would instead only generate a stream of <math>(h, \zeta)  </math> pairs and let the learning and prediction algorithms consume such streams; a [[Linear model|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: <math> t\neq t', \phi(t) = \phi(t') = v</math>. A machine learning model trained on feature-hashed words would then have difficulty distinguishing <math> t</math> and <math> t'</math>, essentially because <math> v</math> is [[Philosophy:Polysemy|polysemic]]. 

If <math> t'</math> is rare, then performance degradation is small, as the model could always just ignore the rare case, and pretend all <math> v</math> means <math> t</math>. 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.<ref>{{cite conference|last=Bai|first=B.|author2=Weston J. |author3=Grangier D. |author4=Collobert R. |author5=Sadamasa K. |author6=Qi Y. |author7=Chapelle O. |author8=Weinberger K. |title=Supervised semantic indexing|conference=CIKM|year=2009|pages=187–196|url=http://www.cs.cornell.edu/~kilian/papers/ssi-cikm.pdf}}</ref>

== 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.<ref name="mobilenlp"/>

Weinberger et al. (2009) applied their version of feature hashing to [[Multi-task learning|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.<ref name="Weinberger" />

Chen et al. (2015) combined the idea of feature hashing and [[Sparse matrix|sparse matrix]] to construct "virtual matrices": large matrices with small storage requirements. The idea is to treat a matrix <math>M\in \R^{n\times n}</math> as a dictionary, with keys in <math>n\times n</math>, and values in <math>\R</math>. Then, as usual in hashed dictionaries, one can use a hash function <math>h: \N\times \N\to m</math>, and thus represent a matrix as a vector in <math>\R^m</math>, no matter how big <math>n</math> is. With virtual matrices, they constructed ''HashedNets'', which are large neural networks taking only small amounts of storage.<ref>{{Cite journal |last=Chen |first=Wenlin |last2=Wilson |first2=James |last3=Tyree |first3=Stephen |last4=Weinberger |first4=Kilian |last5=Chen |first5=Yixin |date=2015-06-01 |title=Compressing Neural Networks with the Hashing Trick |url=https://proceedings.mlr.press/v37/chenc15.html |journal=International Conference on Machine Learning |language=en |publisher=PMLR |pages=2285–2294}}</ref>

==Implementations==
Implementations of the hashing trick are present in:

* [[Software:Apache Mahout|Apache Mahout]]<ref name="mahout">{{cite book |last1=Owen |first1=Sean |title=Mahout in Action |last2=Anil |first2=Robin |last3=Dunning |first3=Ted |last4=Friedman |first4=Ellen |publisher=Manning |year=2012 |pages=261–265}}</ref>
* [[Software:Gensim|Gensim]]<ref>{{cite web|url=http://radimrehurek.com/gensim/corpora/hashdictionary.html |title=gensim: corpora.hashdictionary – Construct word<->id mappings |publisher=Radimrehurek.com |accessdate=2014-02-13}}</ref>
* [[Software:Scikit-learn|scikit-learn]]<ref>{{cite web|url=http://scikit-learn.org/stable/modules/feature_extraction.html#feature-hashing |title=4.1. Feature extraction — scikit-learn 0.14 documentation |publisher=Scikit-learn.org |accessdate=2014-02-13}}</ref>
* sofia-ml<ref>{{cite web|url=https://code.google.com/p/sofia-ml/ |title=sofia-ml - Suite of Fast Incremental Algorithms for Machine Learning. Includes methods for learning classification and ranking models, using Pegasos SVM, SGD-SVM, ROMMA, Passive-Aggressive Perceptron, Perceptron with Margins, and Logistic Regression |accessdate=2014-02-13}}</ref>
* [[Software:Vowpal Wabbit|Vowpal Wabbit]]
* [[Software:Apache Spark|Apache Spark]]<ref>{{cite web|url=https://spark.apache.org/docs/latest/api/scala/index.html#org.apache.spark.mllib.feature.HashingTF|title=Hashing TF|quote=Maps a sequence of terms to their term frequencies using the hashing trick.|accessdate=4 September 2015}}</ref>
* [[R (programming language)|R]]<ref>{{cite web|url=https://cran.r-project.org/web/packages/FeatureHashing/index.html |title=FeatureHashing: Creates a Model Matrix via Feature Hashing With a Formula Interface}}</ref>
* [[Software:TensorFlow|TensorFlow]]<ref>{{cite web|url=https://www.tensorflow.org/api_docs/python/tf/keras/preprocessing/text/hashing_trick |title=tf.keras.preprocessing.text.hashing_trick — TensorFlow Core v2.0.1 |quote=Converts a text to a sequence of indexes in a fixed-size hashing space. |accessdate=2020-04-29}}</ref>
*[https://ml.dask.org/modules/generated/dask_ml.feature_extraction.text.HashingVectorizer.html#dask_ml.feature_extraction.text.HashingVectorizer Dask-ML]<ref>{{Cite web|title=dask_ml.feature_extraction.text.HashingVectorizer — dask-ml 2021.11.17 documentation|url=https://ml.dask.org/modules/generated/dask_ml.feature_extraction.text.HashingVectorizer.html#dask_ml.feature_extraction.text.HashingVectorizer|access-date=2021-11-22|website=ml.dask.org}}</ref>

==See also==

* {{Annotated link |Bloom filter}}
* {{Annotated link |Count–min sketch}}
* {{Annotated link |Heaps' law}}
* {{Annotated link |Locality-sensitive hashing}}
* {{Annotated link |MinHash}}

==References==
{{Reflist|30em}}

==External links==
* [http://hunch.net/~jl/projects/hash_reps/index.html Hashing Representations for Machine Learning] on John Langford's website
* [https://web.archive.org/web/20120609232923/http://metaoptimize.com/qa/questions/6943/what-is-the-hashing-trick What is the "hashing trick"? - MetaOptimize Q+A]

[[Category:Hashing]]
[[Category:Machine learning]]

{{Sourceattribution|Feature hashing}}