Probabilistic Hash Embeddings for Temporal Tabular Data Streams

Does the applicability of PHE depend on the base machine learning method?

No, it doesn't depend on the base machine learning methods. As demonstrated in our experiments, PHE is applicable to a wide range of applications with various base models. We will emphasize this more clearly in the revised version of our draft.

How can one compute the Bayesian update of the hash embedding, what assumptions are necessary on the distributions?

The details of the Bayesian updates are provided in Section 3.3, where we apply variational inference to approximate the true posteriors. We assume that the approximate posterior distributions of the embedding entries and latent variables are independently Gaussian, as shown in Eq. 2 and the following paragraph. Such assumptions are common in deep latent variable models and approximate inferences. And we don’t make assumptions on data distributions. By optimizing the objective function in Eq. 5, we learn these approximate posteriors.

The main idea of the paper is to replace a deterministic hash table by a probabilistic one (PHE), in which each cell is a probability distribution and is updated by calculating the posterior distribution. Properties of PHE follow from the theory of online Bayesian learning, notably in each step, the posterior distribution is the same whether learned online or at once, based on all samples so far. In my opinion, this is the key idea, however it is hidden in Appendix D starting at line 1030. Furthermore, no reference is given to the theorem (or hidden and I did not spot).

We appreciate the reviewer's constructive suggestions. We mentioned this idea in our introduction section and in the small-scale analytical experiments. We will make this part clearer in our next revision.

In practice, I am a bit uncertain about the importance of the hash table size, especially in light of the large language models. More motivation, including data and vocabulary sizes, would be necessary. Data in the experiments are definitely small in this sense

A larger vocabulary and embedding table is a strong mark in categorical feature intensive applications like retail, E-commerce, recommendation, healthcare, and medical diagnosis. Although continually expanding the embedding table with rows for new items typically improves accuracy, it comes at a cost. A larger embedding table requires more resources to deploy, reduces memory efficiency, and slows down execution. This is a well documented issue and an active research area [Ko et al., 2022; Shi et al., 2020b; Kang et al., 2021; Coleman et al., 2024].

Hash embeddings provide a condensed embedding representation for sparse features that are either novel or unbounded. The size of the hash embedding is fixed irrespective of the size of the feature vocabulary. The fixed-size nature of hash embeddings facilitates efficient memory allocation and accelerates model execution. This observation is not new and is leveraged by many practical systems [Weinberger et al., 2009; Coleman et al., 2024]. By mapping an extensive and dynamically evolving feature sets into a unified predetermined finite-dimensional embedding space, hash embeddings address the challenges of high-dimensional and sparse feature in machine learning applications. However, previous work only focuses on offline settings.

Therefore, our experimental design focuses on online learning and demonstrates the efficacy of our proposed PHE (Probabilisitic Hash Embeddings) across various real-world applications that have a temporally dynamic vocabulary. Investigations on four science datasets or domains, one retail datasets of a whole-year sales data, and one movie recommendation dataset spanning 30 years aim to demonstrate the plug-in and applicability nature of our method in a dynamic environment of changing categorical features. By examining the performance in such environments, we confirm PHE’s robustness and adaptability in data streams and continual learning tasks.

Unfortunately, the paper is not well written, very hard to follow the presentation jumping back and forth between main paper and Appendix. While the very simple hand picked two-value example is worked out in much detail showing forgetting can occur with partial hash collision (which is not a surprise in my opinion), several important details are not worked out at all. For example, a detailed Bayesian update for the same example would be more enlightening than the deterministic analysis. Specific suggestions are [...]

We thank you for your suggestions. We will reorganize the content of the appendix and the main paper in our next revision.

While the goal of the paper is to close to the upper bound of the collision-free hash and the experimentations show good results in this sense, I am not convinced whether competitive models are used for the tasks. For example, is Deep Kalman filter recommendation competitive to state-of-art recommenders? Why was it selected? Is it because the update is feasible to compute? This is not explained in the paper. Please justify your choice of Deep Kalman filters and other baseline models.

It is important to note that our focus is not on improving the SoTA for specific models or tasks, such as sequence modeling or recommendation systems. Rather, our primary objective is to showcase the broad applicability of PHE to a spectrum of models - both deterministic and probabilistic ones. To this end, we have selected the Deep Kalman Filters (DKF) as a representative probabilistic model for sequence modeling. Our empirical study illustrates the versatility of PHE across diverse modeling approaches and data types. We will emphasize this point more clearly in our revision of the draft.

The transitions between paragraphs are quite abrupt, with a lack of logical connections, making some parts difficult to understand. Could the logical structure be further refined?

Thank you for your suggestions. We will make the presentation better in the next revision.

In the “Related Work” section, is the relevance of temporal and recommendation models to the research topic truly that strong? Additionally, could the practical shortcomings of these models be discussed in more detail?

We discuss temporal and recommendation models because they are important motivations and applications of condensed embedding representations [Krishnan et al., 2015; Ko et al., 2022; Shi et al., 2020b; Kang et al., 2021; Coleman et al., 2024]. We will rephrase this section to make them more relevant.

In the “Experiment Overview” section, could you elaborate on the detailed setup of the experiments? Additionally, it is worth noting why the five curves in Figure 5 (Right) exhibit very similar trends.

Thank you for your suggestions. We conducted our experiments in data streaming environments where data points arrive sequentially. Our goal was to simulate practical settings in which new feature items can occur over time and need to be incorporated into the system.

The metric curves for MovieLens-32M in Fig. 5 show similar trends because the experimental environments are consistent across all methods. However, the ranking among the baselines changes over time: AdaFast, despite performing best initially, gradually experiences a decline in performance as more data is revealed.

In Table 2, could there be more comprehensive comparisons regarding memory usage?

We hope Table 2 provides readers with a concrete understanding of PHE's memory efficiency. The formal memory complexity, which is independent of the vocabulary size, is presented in line 202.

The mathematical notation is often imprecise, and it is hard to understand what the paper is trying to accomplish.

We thank the reviewer for the suggestions. We will improve the notations in the revised version. Regarding the key points of our paper, we have summarized them in the general comments.

For the experimental section, there is no comparison with the baseline from previous work. Does this mean that there exists no method in the literature that can be applied in your experimental setting (even if it has low performance?), even ones that do not use unified embeddings? Since this is an important problem, and in the real world, there are indeed applications where categorical data is used without prior knowledge of the vocabulary size (e.g., advertisement), it seems peculiar that no comparison with previous work appears in the paper.

Our work is the first work to handle open vocabulary in online dynamic environments. Appropriate baselines require handling both unbounded feature items and online updates simultaneously. To construct baselines for our setup, we need to combine existing embedding methods designed for offline inference with online updating techniques.

For embedding baselines, we use both Hash or Unified Embeddings (HE) and Expandable Embeddings (EE). While EE is not desirable in practice due to its unbounded memory requirements, we include it as a baseline to understand the performance gap (if any) resulting from our method's memory efficiency. For the online learning baseline, we choose the popular strategy of online fine-tuning by varying the learning rate to give many candidate online learning baselines. The different learning rates correspond to AdaFast/Med/Slow in our paper. All the combinations of the above embedding methods and online learning candidates act as baselines in our experiments.

Our empirical study demonstrates the adaptability of our method in dynamic online learning environments. Specifically, our approach significantly outperforms the hash embedding-based baselines across all applications, while performing on par with the upper-bound baseline.

Usually, hash functions are chosen using a random seed. Why are the methods from prior work that use hashing tricks deterministic, as written in Lines 117-119?

By “deterministic” we mean their hash embeddings are deterministic (vs. probabilistic hash embeddings).

We sincerely thank the reviewer for evaluating and supporting our work. If you have any further questions, please don't hesitate to ask.