Feature Hashing for Scalable Machine Learning with Nick Pentreath

Feature hashing is a powerful technique for handling high-dimensional features in machine learning. It is fast, simple, memory-efficient, and well suited to online learning scenarios. While an approximation, it has surprisingly low accuracy tradeoffs in many machine learning problems. Feature hashing has been made somewhat popular by libraries such as Vowpal Wabbit and scikit-learn. In Spark MLlib, it is mostly used for text features; however, its use cases extend more broadly. Many Spark users are not familiar with the ways in which feature hashing might be applied to their problems. In this talk, I will cover the basics of feature hashing, and how to use it for all feature types in machine learning. I will also introduce a more flexible and powerful feature hashing transformer for use within Spark ML pipelines. Finally, I will explore the performance and scalability tradeoffs of feature hashing on various datasets.

1. Nick Pentreath, IBM
Feature Hashing for
Scalable Machine
Learning
#EUds15

2. About
•About me
–@MLnick
–Principal Engineer at IBM working on machine
learning & Apache Spark
–Apache Spark committer & PMC
–Author of Machine Learning with Spark
#EUds15 2

3. Agenda
•Intro to feature hashing
•HashingTFin Spark ML
•FeatureHasherin Spark ML
•Experiments
•Future Work
#EUds15 3

4. Feature Hashing
4#EUds15

5. Encoding Features
5#EUds15
2.13.2−0.20.7
!!
•Most ML algorithms
operate on numeric
feature vectors
•Features are often
categorical –even
numerical features (e.g.
binning continuous
features)

6. Encoding Features
•“one-hot” encoding is
popular for categorical
features
•“bag of words” is
popular for text (or token
countsmore generally)
00100
! 02011
#EUds15 6

7. High Dimensional Features
•Many domains have very high densefeature dimension
(e.g. images, video)
•Here we’re concerned with sparsefeature domains, e.g.
online ads, ecommerce, social networks, video sharing,
text & NLP
•Model sizes can be very large even for simple models
#EUds15 7

8. !
The “Hashing Trick”
•Use a hash function to map feature values to
indices in the feature vector
Dublin
Hash “city=dublin” 00100
Modulo hash value
to vector size to get
index of feature
Stock Price
Hash “stock_price” 02.60…00
Modulo hash value
to vector size to get
index of feature
#EUds15 8

9. Feature Hashing: Pros
•Fast & Simple
•Preserves sparsity
•Memory efficient
–Limits feature vector size
–No need to store mapping feature name -> index
•Online learning
•Easy handling of missing data
•Feature engineering
#EUds15 9

10. Feature Hashing: Cons
•No inverse mapping => cannot go from feature
indices back to feature names
–Interpretability & feature importances
–But similar issues with other dim reduction techniques
(e.g. random projections, PCA, SVD)
•Hashcollisions …
–Impact on accuracy of feature collisions
–Can use signed hash functions to alleviate part of it
#EUds15 10

11. HashingTFin Spark ML
#EUds15 11

12. HashingTFTransformer
•Transforms text (sentences) -> term frequency
vectors (aka “bag of words”)
•Uses the “hashing trick” to compute the feature
indices
•Feature value is term frequency (token count)
•Optional parameter to only return binary token
occurrencevector
#EUds15 12

13. HashingTFTransformer
#EUds15 13

14. Hacking HashingTF
•HashingTFcan be used for
categorical features…
•…but doesn’t fit neatly into
Pipelines
#EUds15 14

15. FeatureHasherin Spark ML
#EUds15 15

16. FeatureHasher
•Flexible, scalable feature encoding using
hashing trick
•Support multiple input columns (numeric or
string / boolean, i.e. categorical)
•One-shotfeature encoder
•Core logic similar to HashingTF
#EUds15 16

17. FeatureHasher
•Operates on entire Row
•…UDF with structinput
#EUds15 17

18. FeatureHasher
#EUds15 18
•Determining feature
index
–Numeric: feature
name
–String / boolean:
“feature=value”
•String encoding =>
effectively “one hot”
with indicator value
of 1.0

19. FeatureHasher
•Modulo raw index to feature vector size
•Hash collisions are additive(currently)
#EUds15 19

20. FeatureHasher
#EUds15 20

21. Experiments
#EUds15 21

22. Text Classification
•KaggleEmail Spam Dataset
0.955
0.96
0.965
0.97
0.975
0.98
0.985
0.99
10 12 14 16 18
Hash bits
AUC by hash bits
HashingTF
CountVectorizer
#EUds15 22

23. Text Classification
•Adding regularization (regParam=0.01)
0.97
0.975
0.98
0.985
0.99
0.995
10 12 14 16 18
Hash bits
AUC by hash bits
HashingTF
CountVectorizer
#EUds15 23

24. Ad Click Prediction
•CriteoDisplay Advertising Challenge
–45m examples, 34m features, 0.000003% sparsity
•OutbrainClick Prediction
–80m examples, 15m features, 0.000007% sparsity
•CriteoTerabyte Log Data
–7 day subset
–1.5b examples, 300m feature, 0.0000003% sparsity
#EUds15 24

25. Data
•Illustrative characteristics -CriteoDAC
0
2
4
6
8
10
12
Millions
Unique Values per Feature
0%
10%
20%
30%
40%
50%
60%
70%
80%
90%
100%
Feature Occurence (%)
#EUds15 25

26. Challenges
Raw Data StringIndexer OneHotEncoder VectorAssembler
OOM!
•Typical one-hot encoding pipeline fails consistently with
large feature dimension
#EUds15 26

27. Results
•Compare AUC for different # hash bits
0.695
0.7
0.705
0.71
0.715
0.72
18 20 22 24
Hash bits
Outbrain
AUC
0.74
0.742
0.744
0.746
0.748
0.75
0.752
18 20 22 24
Hash bits
CriteoDAC
AUC
#EUds15 27

28. Results
•Criteo1T logs –7 day subset
•Can train model on 1.5b examples
•300m original features for this subset
•2
24
hashed features (16m)
•Impossible with current Spark ML (OOM, 2Gb
broadcast limit)
#EUds15 28

29. Summary & Future Work
#EUds15 29

30. Summary
•Feature hashing is a fast, efficient, flexible tool for
feature encoding
•Can scale to high-dimensional sparse data, without
giving up much accuracy
•Supports multi-column “one-shot” encoding
•Avoids common issues with Spark ML Pipelines
using StringIndexer& OneHotEncoderat scale
#EUds15 30

31. Future Directions
•Will be part of Spark ML in 2.3.0 release (Q4 2017)
–Refer toSPARK-13969for details
•Allow users to specify set of numeric columns to be
treated as categorical
•Signed hash functions
•Internal feature crossing & namespaces (ala Vowpal
Wabbit)
•DictVectorizer-like transformer => one-pass feature
encoder for multiple numeric & categorical columns (with
inverse mapping) –see SPARK-19962
#EUds15 31

32. References
•Hash Kernels
•Feature Hashing for Large Scale Multitask
Learning
•VowpalWabbit
•Scikit-learn
#EUds15 32

33. Thank You.
@MLnick
spark.tc