1
$\begingroup$

I am looking for binary encoding of a set of integers that satisfy the following two properties:

  1. The number of 1s in the larger numbers is larger.

  2. The hamming distance between the encoding of two consecutive numbers is minimized.

Is there any number coding scheme to do this?

The objective is to find a better encoding for ordinal values as a binary vectors. The common idea for encoding of ordinal values in machine learning is to consider them categorical and encode them as one-hot binary vector. But a one-hot vector is quite wasteful.

Suppose you encode two ordinal values $o_1 < o_2$ as $d$-dimensional binary vectors $\mathbf{v}_1, \mathbf{v}_2 \in \{0, 1\}^{d}$. For this encoding to be efficient, there should exist an embedding vector $\mathbf{w} \in \mathbb{R}^{d}$ such that $\mathbf{w}^{\top}\mathbf{v}_1 < \mathbf{w}^{\top}\mathbf{v}_2$.

$\endgroup$
8
  • 3
    $\begingroup$ Could you be more specific about the first property, please? Taken literally, you want the encoding of "two" to have more 1s than that of "one", that of "three" more still et cetera, forcing you to adopt the silly $1\mapsto 1, 2\mapsto 11, 3\mapsto 111, 4\mapsto 1111$ etc. I rather suspect that your reason for including item 1 is to avoid the use of Gray codes and the like. Why is that? You need to also be more specific about ties. $\endgroup$
    – Jyrki Lahtonen
    Commented Oct 6, 2018 at 9:45
  • $\begingroup$ @JyrkiLahtonen: I added the context and clarification for the problem definition. Please make changes if my presentation is confusing. $\endgroup$
    – Taha
    Commented Oct 6, 2018 at 19:07
  • $\begingroup$ Hmm. Won't the usual base two presentation of integers work if we use $w=(1,2,4,8,\ldots,2^{d-1})$? $\endgroup$
    – Jyrki Lahtonen
    Commented Oct 6, 2018 at 19:12
  • $\begingroup$ The problem happens with $3 = [0, 1, 1]$ and $4 = [1, 0, 0]$. When we learn $\mathbf{w}$, the algorithm needs to understand the relationship between coordinates (the leftmost position should have twice the value of the position to its right). Your previous solution is a better one though. $\endgroup$
    – Taha
    Commented Oct 6, 2018 at 19:18
  • $\begingroup$ Also, $\mathbf{w}$ should be learned from the data. We do not know the true numerical value of the ordinal numbers in the dataset and the prediction task. $\endgroup$
    – Taha
    Commented Oct 6, 2018 at 21:00

0

Reset to default

You must log in to answer this question.