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.
 A: 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.
