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

Question

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.

Answer 1

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.