6
$\begingroup$

Let's say we have a set of labels of the same length, and we need to find the distance between them.

In the case of binary labels, one can use the Hamming distance. For example, if $l_1 = 01101$ and $l_2 = 00111$, then $d(l_1, l_2) = 2$.

In my case, labels are formed from the alphabet $A=\{a, b, c, d, e\}$, so the length of the alphabet is $|A|=5$, and the length of each label is $n=4$.

In my case, an ordinal scale is applicable for letters from alphabet $A$:

$$a < b < c < d < e.$$

Examples of labels: deed, aaaa, aaad, aaae, dada, cccd.

Edit. The Hemming distance for three labels aaaa, aaad, aaae gives $$d(aaaa, aaad) = d(aaaa, aaae)$$ but I am looking for a metric which will distinguish $d$ and $e$ and return $$d(aaaa, aaad)<d(aaaa, aaae)$$ because $d<e$.

Edit 2.

For creating a label we use a threshold $T \in \mathbf{R}$ and apply the next function for the $i$-th element of $X=(x_1, x_2, \ldots, x_n)$: \begin{equation} f(x_i) = \begin{cases} a, & x_i \leq -T, \\ b, & -T < x_i \leq 0, \\ c, & x_i = 0, \\ d, & 0 < x_i \leq T, \\ e, & x_i >T. \ \end{cases} \end{equation} Finally, we use the concatination operator $\&$, for example, $a \& a \& a \& a= aaaa$.

Question. What a metric can I use to calculate the distance between labels?

| cite | improve this question | | | | |
$\endgroup$
  • 3
    $\begingroup$ I am not sure it is useful in this context to be referring to your sequences as "words" as the meaningful properties for creating distances in language do not seem to apply to your problem. I think you will get better answers if you just describe your problem without the added baggage of the "word" label. $\endgroup$ – Barker Dec 30 '19 at 21:04
  • $\begingroup$ @Barker, I have updated the question and change the 'word' to 'label'. $\endgroup$ – Nick Dec 31 '19 at 1:19
  • 1
    $\begingroup$ But is position important or not? You haven't given enough examples to see whether $d(aaaa, aada) = d(aaaa, aaad)$? Is the distance simply the piecewise sum of the individual distances between components? (Is your input vectors or not? I don't see it helpful to call them 'labels' or 'words'. They seem to be quantized vectors) $\endgroup$ – smci Dec 31 '19 at 10:14
  • 1
    $\begingroup$ @Nick actually the usage of word "word" is not wrong, it just happen that within this community the common understanding for the word "word" is in the context of nlp rather than as an abstract mathematical object. $\endgroup$ – Yohanes Alfredo Dec 31 '19 at 10:32
  • $\begingroup$ Is there a reason you can't just compute the distance based on your x_i values rather than the labels? It seems then you might also have some more nuance where a d that is slightly below T would be closer to e than a d that is nearly 0. $\endgroup$ – Barker Dec 31 '19 at 20:40
7
$\begingroup$

It really depends on what kind of words you are referring to. There are two distance that I wish to talk about :

  1. Edit Distance

    If you wish to capture difference in terms of how different two sequence are, you can use levenshtein distance or Damerau-Levenshtein distance. Mathematically for a word $A$ or $B$, the levenshtein distance is the least number of moves/operations to transform word $A$ to word $B$. This is what you might be looking for when your definition of word as a sequence of alphabet.

  2. Context Similarity

    For words we can also talk about contextual meaning of each word. If the two words are related or have similar meaning then we expect this measure to be small. This can be implemented with word2vec. Basically we train our model in unsupervised manner and will have it's vectorized representation and we measure the distance by comparing the two vectors. The most popular way for measuring the distance is using cosine similarity.

The two distances does not correlate with each other. For example, deed and deer, the edit distance is small (in fact it is equals to 1), but the similarity distance will be big since those words are not related.

Edit : Since the asker explained his specific case.

You can consider using Earth Mover's/Wasserstein distance.

This is my idea how you might approach this. Suppose you wish to imply ordering for each letter such that $a < b < c < d < e$ and you have 3 words on your letter. Suppose you have a word $abc$, for 3 letters let $t_1=0,t_2=1,t_3=2$, and $w_1=a,w_2=b,w_3=c$. Also let $T$ be a key value mapping between letter and some arbitrary value and should reflect your ordering.

\begin{equation} f(x) = \begin{cases} T(w_i), & t_i \leq x < t_{i+1}, \\ 0, & otherwise\\ \end{cases} \end{equation} Forgive my poor use of notations though, but the idea is (if we let $T(a)=0.8$ and $T(b)=1.5$) for example you have a function that have value $f(x)=0.8$ for $x\in[0,1]$ and then value of $f(x)=1.5$ for $x\in[1,2]$. Now you can see this as an unnormalized distribution and you could calculate earthmovers/wasserstein distance. This is just some random idea, might not necessarily make sense though.

Here is a useful link.

| cite | improve this answer | | | | |
$\endgroup$
  • 1
    $\begingroup$ @Nick, is context similarity relevant to your case? do you have a corpus of "sentences" composed of words from this vocabulary? $\endgroup$ – Itamar Mushkin Dec 30 '19 at 13:31
  • $\begingroup$ @itamarmushkin, no. Context is not similarity relevant. A word is a state's name of Markov chain. $\endgroup$ – Nick Dec 30 '19 at 14:28
  • $\begingroup$ @Nick please checkout my latest edit. Hopefully it gives you idea. Scipy has wasserstein distance calculation implemented $\endgroup$ – Yohanes Alfredo Dec 31 '19 at 10:29
6
$\begingroup$

You can still use the Hamming distance for 5 letters. Another metric than you can use is the Levenshtein distance - the minimum number of single-character edits required to change one word into the other.

If there is some meaning to the order of your letters, such that for example the distance between a and c is larger than the distance between a and b, then you can use a metric such as the euclidean distance.

| cite | improve this answer | | | | |
$\endgroup$
  • 1
    $\begingroup$ I've suggested links to Wikipedia for the terms used, but I think it would be even better if you can recommend a post that explains the terms (like in towardsdatascience or something like that). $\endgroup$ – Itamar Mushkin Dec 30 '19 at 12:18
  • 1
    $\begingroup$ Ok (: I approved the edit and changed the Levenshtein distance link to a blog post.. $\endgroup$ – Daphna Dec 30 '19 at 13:22
3
$\begingroup$

It sounds to me like you may be looking for a simple sum of absolute differences (also called L1 distance).

Assuming that we can extend your ordinal relation $a < b < c < d < e$ into a metric (e.g. $b - a = c - b = 1$, $e - a = 4$, etc.), then you can let the difference between two words of the same length be the sum of absolute differences of symbols in the same position.

For example, $ abcd - edcb = |a-e| + |b-d| + |c-c| + |d-b| = 4 + 2 + 0 + 2 = 8$.

In the case of an alphabet of two symbols, this is identical to the Hamming distance, and like the Hamming distance it doesn't have any idea of context or transposition — $aaea$ and $aeaa$ are separated by a distance of 8, just as much as $aaaa$ and $cccc$.

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ You seem to be imposing additional assumptions onto the original question. It is not the case that $b-a=c-b=1$ for all $a<b<c$, and I don't see anything in Nick's question to suggest that an additional assumption that it does necessarily holds. $\endgroup$ – Alexis Dec 31 '19 at 3:35
  • $\begingroup$ @Alexis I make that assumption clear. $\endgroup$ – hobbs Dec 31 '19 at 3:38
  • $\begingroup$ @Alexis also, that's only an example... you can impose any metric you find suitable. $\endgroup$ – hobbs Dec 31 '19 at 3:39
3
$\begingroup$

Usually when people talk about word similarity, they refer to something like Yohanes Alfredo's answer.

In your case, you want to take into account the sort order of the characters. In that case, it might be that hobbs has the answer you need.

Do you want to find distance according to the overall sort order of the word? In other words, do you want $$d(aaaa, aaad)<d(aaaa, daaa)$$ because words that start with the same letter are closer to each other in the dictionary than words that differ in other letters?

If so, then you're better off calculating a value of each word using the following algorithm that takes into account the position of the letters in the word.

initially set value1 = 0
for i in 1 to length:
    value1 = value1 + (alphabetSize ^ i) * letters1[length - i]
initially set value2 = 0
for i in 1 to length:
    value2 = value2 + (alphabetSize ^ i) * letters2[length - i]
distance = abs(value1 - value2)

What this is doing is treating each word as a number written in base alphabetSize.

I apologize for writing this in pseudocode. Using mathematical notation with capital Sigma would be clearer but I don't know my way around the typography.

| cite | improve this answer | | | | |
$\endgroup$
  • 1
    $\begingroup$ This. Since the OP demands a distance (norm) that respects the total order on the words, the only workable distance function is the difference in location in the total order. That is, compute the number of words between the two given words in the dictionary ordering of all the words over the given alphabet. $\endgroup$ – Eric Towers Dec 30 '19 at 23:33
  • $\begingroup$ @jetpack, the word's (labels) order do not have matter in my case. $\endgroup$ – Nick Dec 31 '19 at 3:05
  • $\begingroup$ By "word's order"', do you mean the order of "characters" in your "word"? $\endgroup$ – Itamar Mushkin Dec 31 '19 at 6:29
  • $\begingroup$ @itamarmushkin, the order of charecters has mean, but the order of labels do not has matter. $\endgroup$ – Nick Dec 31 '19 at 8:03
  • $\begingroup$ @EricTowers Post your comment as an answer (even if it's not the one the OP wants). Note that once you have the words in linear (lexicographic) order you can change the metric with any strictly increasing function of position. $\endgroup$ – Ethan Bolker Dec 31 '19 at 14:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.