# 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.

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.