  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.
