Abstract
Standard machine learning models often represent data as high-dimensional "flat" real-valued vectors, which lack explicit structural organization and demand significant storage. This paper introduces Hierarchical K-way D-dimensional (HKD) discrete embeddings, a method to compress these vectors into compact, hierarchical codes. By utilizing a regularized autoencoder with an exponentially decaying weight function, HKD forces the model to capture broad categories in the initial dimensions and fine-grained details in subsequent ones. Evaluations on synthetic and real-world datasets demonstrate that HKD achieves massive search space reductions (up to 93.6%) and superior neighborhood preservation compared to existing discrete encoding techniques.
Introduction
While real-valued embeddings are powerful for capturing semantic relationships, they are computationally expensive to search and store. Furthermore, they do not inherently reflect the hierarchical nature of real-world data, such as biological taxonomies or product categories. Existing discrete hashing methods improve search speed but often treat all bits as equally important, failing to recover nested structures. HKD addresses these challenges by learning a structured discrete representation that naturally organizes data into a searchable hierarchy.
The HKD Framework
The core of the proposed method is a Regularized Autoencoder designed to map continuous embeddings into $D$ slots, each containing a $K$-way discrete value.
Hierarchical Encoding via Weight Decay
To induce a hierarchical structure, the authors introduce an exponentially decaying weight function, $w_d = w_0 \exp(-\lambda d)$, into the neighborhood preservation loss. By penalizing differences in the "front" slots of the code more heavily than the "back" slots, the model is incentivized to use the first few dimensions for high-level clustering.
Differentiable Discrete Codes
Since the "argmax" operation required for discrete selection is non-differentiable, the framework employs a "Softmax temperature" trick during training. This allows gradients to flow through the discrete code layer, enabling end-to-end optimization of the autoencoder.
Neighborhood Preservation (pt-SEE)
To maintain the local structure of the original space without the quadratic cost of all-pairs comparisons, the model uses parametric t-distributed stochastic exemplar-centered embedding (pt-SEE). This technique compares data points to a fixed set of representative "exemplars," significantly reducing computational overhead.
Experimental Results
The authors evaluated HKD against the state-of-the-art KD-encoding (Shu et al., 2018) across synthetic and real-world datasets, including WordNet and CIFAR-100.
Retrieval Efficiency and Accuracy
On a synthetic hierarchical dataset, HKD demonstrated a remarkable ability to prune search spaces. As shown in the table below, the method achieves a search complexity reduction of up to 93.6% while maintaining near-perfect neighborhood preservation (KNN accuracy) compared to the baseline.
Semantic Hierarchy Recovery
In experiments with the WordNet mammal subtree, HKD successfully recovered biological taxonomies. For instance, closely related species shared identical codes for the first several dimensions, only diverging at the final bits. In contrast, distantly related animals were separated at the very first dimension. Similar results were observed in CIFAR-100, where the model successfully partitioned "superclasses" (e.g., vehicles) into specific sub-classes (e.g., bicycles vs. motorcycles) as more code dimensions were considered.
Conclusion
HKD provides a robust framework for transforming flat embeddings into structured, searchable hierarchies. By combining discrete encoding with hierarchical regularization, the method offers a scalable solution for large-scale data retrieval and visualization. Future work may explore end-to-end training directly from raw data, potentially removing the dependency on pre-trained continuous embeddings.
Summary updated