Probabilistic Hash Embeddings for Online Learning of Categorical Features

AI summary

Overview

Research area: Machine learning for streaming/online data with categorical features; specifically, hashing-based embedding methods, Bayesian online learning, and continual learning.

Technical level: Advanced. The paper assumes familiarity with embedding tables, feature hashing, variational inference, ELBOs, and Bayesian posterior updates.

Scope: The paper proposes a probabilistic hash embedding (PHE) module and a scalable variational inference algorithm for online learning over categorical vocabularies that change and can grow unboundedly, evaluated on classification, sequence modeling, and recommendation tasks.

Note: the supplied paper content is truncated partway through Section 4.4 (the recommendation application), so final recommendation results, Section 4.5, and the conclusion are not available and are marked below as not reported.

What This Paper Is About

Standard feature hashing maps categorical values into a fixed-size embedding table, but it was designed and evaluated for offline or batch settings where the vocabulary is fixed. In streaming settings, new categories appear over time while old ones recur, and the authors show that deterministic hash embeddings suffer from catastrophic forgetting driven by collisions and by the order in which items arrive. PHE instead treats the hash embedding table as a random variable and applies Bayesian online learning so the model can adapt to new items without forgetting old ones, using memory that does not grow with the number of distinct observed categories.

Key Contributions

1. A probabilistic hash embedding (PHE) module. A fixed hash function combined with a hash embedding table E whose entries each have an independent Gaussian prior. Multiple hash functions (universal hashing) reduce collisions from O(1/B) to O(1/B^K), while the table is shared across all hash functions so memory stays O(Bd), independent of the number of hash functions.

2. A scalable online variational inference algorithm. The paper derives ELBO objectives for a static setting and for an online update in which the previous approximate posterior replaces the prior, plus a variational EM variant that jointly learns model parameters θ and posterior parameters λ. Updates are sparse (each item activates at most K embeddings) and other network parameters are frozen during online learning.

3. Theory characterizing online learning. Proposition 3.1 states that for every permutation of the data arrival order, the Bayesian online posterior equals the Bayesian batch posterior almost everywhere, so PHE is order-invariant in the exact-inference limit.

4. Demonstration as a plug-in module. PHE is paired with different backbones — including a Deep Kalman Filter for sequence modeling and Neural Collaborative Filtering for recommendation — and evaluated in three streaming setups.

Main Findings

• Deterministic hash embeddings forget and are order-sensitive. On online classification streams, the Ada-family baselines show a downward accuracy trend even when no new items need to be learned; the authors attribute this to parameter interference, where items sharing a hash embedding table row adversely affect each other when one is updated.

• PHE is competitive with upper-bound collision-free embeddings. In Table 1, PHE reaches Adult 84.1 ± 0.2 accuracy, Bank 89.6 ± 0.0, Mushroom 98.8 ± 0.0, and CoverType 64.3 ± 0.2, against collision-free EE at 84.2 ± 0.0, 90.0 ± 0.0, 98.8 ± 0.0, and 64.3 ± 0.1 respectively, and probabilistic P-EE at 84.8 ± 0.0, 90.1 ± 0.0, 98.8 ± 0.0, and 64.0 ± 0.4.

• Large memory savings. Table 1 reports PHE compression ratios relative to P-EE of 0.09 (Adult), 0.2 (Bank), 0.62 (Mushroom), 0.2 (CoverType), 0.02 (Retail), and 0.04 (MovieLens). The text states PHE takes as low as 2% memory of P-EE, and the abstract states memory as low as 2 to 4% of a one-hot embedding table.

• Retail and MovieLens mean absolute error (lower is better). SlowAda 49.1 ± 82.9, MediumAda 22.7 ± 20.3, FastAda not reported, PHE 3.0 ± 0.2, EE 3.7 ± 0.1, P-EE 3.2 ± 0.4 on Retail. On MovieLens: SlowAda 15.3 ± 0.1, MediumAda 15.1 ± 0.1, FastAda 15.1 ± 0.1, PHE 14.7 ± 0.0, EE 15.1 ± 0.0, P-EE 14.7 ± 0.0.

• Baseline hyperparameter sensitivity. FastAda trains 15 epochs per step, MedAda 5, and SlowAda 1, and the Ada-family results vary substantially across these settings, while PHE uses a single hyperparameter configuration and outperforms all Ada baselines across all datasets. On Retail, FastAda errors "explode after 50 days."

• Stability. The paper reports that PHE is more stable and has smaller variance than the hash embedding baselines, and that it is the only method listing no training-epoch hyperparameter search among the hash-based methods.

• Simplified demonstration of order invariance. A small experiment with two categorical items arriving alternately, each repeated ten times before the other arrives, shows deterministic hash embeddings incurring large prediction errors on recurrent items while PHE predicts much more accurately, consistent with Proposition 3.1.

• No new items still causes degradation for baselines. The paper notes that accuracy curves trend downward for Ada methods even though all items seen online were learned during initialization, supporting the parameter-interference explanation.

• Retail vs P-EE discrepancy. On Retail, PHE outperforms the collision-free P-EE baseline on average despite using only 2% of its memory; the authors suggest P-EE initializes new embeddings from scratch and is slow to warm up, whereas PHE reuses shared parameters from initial training.

Methodology in Plain English

The authors take the standard hashing trick — map a string to an index in a small table and look up a row — and turn the table into a random variable. Each entry of the table gets a Gaussian prior. When an item arrives, K hash functions produce K indices, K rows are retrieved, and an assembly function g (sum, average, maximum, minimum, or a weighted sum) combines them into one embedding. Predictions integrate over the uncertainty in the table, using Monte Carlo sampling to estimate the expectation.

Learning proceeds by variational inference: a factorized Gaussian approximate posterior over table entries is fit by maximizing the ELBO, which contains a data log-likelihood term and a KL term against the prior that acts as regularization. The reparameterization trick plus gradient methods handle optimization. When a new batch of data arrives, the previous approximate posterior replaces the prior, producing a new ELBO whose KL term is against the earlier posterior — this is the online update. A variational EM variant additionally learns likelihood parameters θ, which are then frozen along with the old posterior parameters so that only the hash embeddings adapt as new items appear.

Experiments simulate streams: at each step the model predicts, is evaluated, then updates embeddings. Only the hash embedding table is updated during online learning while all other model parameters, learned on an initial dataset, are held fixed. Every experiment is repeated five times with different initialization. Hash hyperparameters are fixed: K = 3 hash functions and a prime bucket size B supporting ten times the expected total vocabulary — B = 7 for the tabular datasets, B = 109 for Retail, and B = 10009 for MovieLens.

Datasets: Adult, Bank, Mushroom, and Covertype (UCI Machine Learning Repository, mixed discrete and continuous columns, continuous columns normalized) for classification; Retail for sequence modeling, containing over 4,000 products and over 540K time-stamped invoice records between 01/12/2010 and 09/12/2011, with the first three months used to initialize the model; MovieLens-32M for recommendation. For sequence modeling the likelihood is a parametric Poisson distribution with a latent time variable modeled by a GRU-based variational posterior and dynamics from a multilayer perceptron. For recommendation, PHE is combined with Neural Collaborative Filtering as a rating prediction model.

Why This Matters

Impact on research. The paper argues it is the first method to handle open vocabularies in online dynamic environments while keeping memory constant. It connects feature hashing to Bayesian online learning and continual learning, and it recasts the hash-collision problem as a source of catastrophic forgetting rather than only an accuracy loss. It also extends models like Deep Kalman Filters and Neural Collaborative Filtering, which normally assume a fixed item vocabulary, to unbounded item sets.

Real-world applications:

• Recommendation and streaming services where new users, items, or movies appear continuously.
• Intrusion detection and cybersecurity, where new usernames and application names appear over time.
• Healthcare, where new patients arrive at hospitals and must be incorporated without discarding learned representations.
• Retail and grocery, where new products are added to stores while existing products recur.
• General tabular ML in finance, fraud detection, and anomaly detection, where categorical features are ubiquitous.

Industry relevance. The motivation comes from deployed systems at large technology firms (Yahoo and Google are cited as having incorporated hashing approaches). PHE's constant memory footprint matters for deployment cost and latency, since larger embedding tables require more resources and slow execution. The authors are affiliated with Amazon Web Services, and the paper frames bounded memory, avoiding architecture expansion, and stability under streaming distribution shift as operational advantages.

Future Directions

• Closing the gap between exact and approximate inference. Proposition 3.1 holds for exact Bayesian inference, while experiments use variational inference; the authors explicitly note mean-field, optimization, and amortization gaps.
• Extending beyond single-valued categorical features. The setup assumes each feature is assigned exactly one category, and the paper notes only that the work is "compatible" with multi-valued features without demonstrating it.
• Applying PHE to additional probabilistic backbones. The paper presents PHE as a plug-in and names Deep Kalman Filters and Neural Collaborative Filtering, leaving other likelihood models and architectures to be explored.
• Characterizing the limits of the method. The abstract's listed contributions and the truncated content do not report final recommendation results, Section 4.5, or the conclusion and limitation discussion, so the authors' own stated limitations and remaining open questions are not available in the supplied content.

Target Audience

Researchers and practitioners working on streaming or continual learning with categorical features, embedding-table compression, and feature hashing; recommender-system and sequence-modeling engineers dealing with growing item vocabularies; and readers with a background in variational inference and probabilistic modeling who want a principled, memory-bounded alternative to deterministic hash embeddings. Readers seeking a beginner-level introduction to hashing or variational inference will need supplementary background.

Authors’ abstract

We study streaming data with categorical features where the vocabulary of categorical feature values is changing and can even grow unboundedly over time. Feature hashing is commonly used as a pre-processing step to map these categorical values into a feature space of fixed size before learning their embeddings. While these methods have been developed and evaluated for offline or batch settings, in this paper we consider online settings. We show that deterministic embeddings are sensitive to the arrival order of categories and suffer from forgetting in online learning, leading to performance deterioration. To mitigate this issue, we propose a probabilistic hash embedding (PHE) model that treats hash embeddings as stochastic and applies Bayesian online learning to learn incrementally from data. Based on the structure of PHE, we derive a scalable inference algorithm to learn model parameters and infer/update the posteriors of hash embeddings and other latent variables. Our algorithm (i) can handle an evolving vocabulary of categorical items, (ii) is adaptive to new items without forgetting old items, (iii) is implementable with a bounded set of parameters that does not grow with the number of distinct observed values on the stream, and (iv) is invariant to the item arrival order. Experiments in classification, sequence modeling, and recommendation systems in online learning setups demonstrate the superior performance of PHE while maintaining high memory efficiency (consumes as low as 2~4 memory of a one-hot embedding table). Supplementary materials are at https://github.com/aodongli/probabilistic-hash-embeddings