Abstract
Embedding methods such as word embedding have become pillars for many applications containing discrete structures. Conventional embedding methods directly associate each symbol with a continuous embedding vector, which is equivalent to applying linear transformation based on "one-hot" encoding of the discrete symbols. Despite its simplicity, such approach yields number of parameters that grows linearly with the vocabulary size and can lead to overfitting. In this work we propose a much more compact K-way D-dimensional discrete encoding scheme to replace the "one-hot" encoding. In "KD encoding", each symbol is represented by a $D$-dimensional code, and each of its dimension has a cardinality of $K$. The final symbol embedding vector can be generated by composing the code embedding vectors. To learn the semantically meaningful code, we derive a relaxed discrete optimization technique based on stochastic gradient descent. By adopting the new coding system, the efficiency of parameterization can be significantly improved (from linear to logarithmic), and this can also mitigate the over-fitting problem. In our experiments with language modeling, the number of embedding parameters can be reduced by 97% while achieving similar or better performance.
Introduction
In natural language processing (NLP) and other domains handling categorical data, embedding layers are the standard mechanism for mapping discrete symbols to continuous dense vectors. The conventional approach relies on "one-hot" encoding, which effectively creates a lookup table of size $N \times d$, where $N$ is the vocabulary size and $d$ is the embedding dimension.
This linear scaling presents three significant challenges:
- Parameter Explosion: Memory requirements grow linearly with $N$, hindering deployment on resource-constrained devices.
- Overfitting: Rare symbols (following Zipf's law) receive dedicated high-dimensional vectors, leading to poor generalization.
- Inefficiency: One-hot encoding is a sparse and inefficient use of the potential code space.
The KD Encoding Framework
To address these limitations, we propose KD encoding. Instead of a 1-of-$N$ one-hot vector, each symbol is represented by a compact $D$-dimensional code, where each dimension can take one of $K$ discrete values. As long as $K^D \ge N$, every symbol in the vocabulary can be uniquely identified.
To generate a continuous embedding from this discrete code, the model performs two steps:
- Code Lookup: It retrieves a smaller continuous vector for each of the $D$ code components.
- Composition: These component vectors are passed through a differentiable transformation function $f(\cdot)$—such as a simple summation or a recurrent neural network (RNN)—to produce the final symbol embedding.
Learning the Codes
A primary challenge is that discrete codes are non-differentiable, preventing direct optimization via backpropagation. We employ a Straight-Through Estimator (STE) combined with a tempering Softmax. During the forward pass, the model performs a hard argmax to select discrete codes. During the backward pass, it utilizes a "soft" continuous approximation to allow gradient flow.
Crucially, we use temperature annealing. By gradually decreasing the Softmax temperature during training, the model is forced to transition from soft, probabilistic assignments to stable, hard discrete codes. This prevents the codes from shifting indefinitely and aids convergence to a meaningful representation. In this work, codes are learned by mimicking existing pre-trained embeddings (like GloVe) to capture established semantic relationships.
Experimental Evaluation
We evaluated KD encoding on the Penn Treebank (PTB) language modeling task and qualitative semantic grouping using GloVe embeddings.
Key Results:
- Massive Parameter Reduction: On PTB, KD encoding reduced embedding parameters by 82% to 97%. For a large model, the embedding table shrank from 15 million to just 400,000 parameters.
- Maintained Performance: Despite the compression, the model maintained or improved performance. For a small LSTM, perplexity (PPL) improved from 114.53 to 111.13.
- Semantic Capture: The optimization process naturally groups similar concepts. For example, days of the week were found to share identical prefixes in their learned KD codes (e.g.,
3-1-0-4for "tuesday" through "sunday").
Conclusion and Future Work
KD encoding provides a path toward extremely compact and semantically rich embeddings by shifting parameter complexity from $O(N)$ to $O(\log N)$. While the current implementation often relies on pre-trained embeddings as targets, future work will explore learning these discrete codes "on-the-fly" directly from downstream tasks, further streamlining the pipeline for large-scale categorical modeling.
Summary updated