# For discrete optimization problems, shouldn't there be a similarity metric over the label space?

Let's say we want to map images of animals to categorical language label of what the animal is.

Let's say we have multiple sub-classes within the class of "dogs" e.g. poodles, terriers, bulldogs. Let's say we have a class "cat" e.g. Persian, Siamese, Maine Coone. The labels are always specific sub-classes.

The language label is a 1-hot vector from 1 ... N where N is the max number of sub-classes.

There are two ways we can setup this 1-hot vector:

(a) [poodles, terriers, bulldogs, Persian, Siamese, Maine Coone]

or

(b) [poodles, Persian, terriors, bulldogs, Siamese, Maine Coone]

Shouldn't (a) give better generalization than (b)? But most classification algorithms these days treat these two types the same. Basically, there is often a notion of "similarity" in the label space that I don't think is exploited.

## 1 Answer

Your remark is perfectly valid, but there are a couple of problems with your proposed solution.

There are in fact models where the classes are not assumed to be completely independent. For example in Zero-Shot Learning classes from training and evaluation might be different, but there is assumption that for each one of them a feature vector is provided. See Zero-Shot Learning - The Good, the Bad and the Ugly for details. An example method that tackles this problem is Embarrassingly simple zero-shot learning.

The problem with using similarity is that you actually need to specify it, because there are many different types of similarity - (note that ZSL does that implicitly, because you have cosine/Euclidean distance etc for vectors).

For example is a whale more similar to a salmon or a horse? (you care about being a member of common taxon or visual similarity, or where do they live?).

Another problem is that if you actually have a similarity in mind, how do you encode it? There will be problems with scalability, as for $$n$$ classes you will need to specify $$n^2$$ distances. Also adding a new class will require specifying similarities to all other classes, and not just adding a few new examples.