How to handle samples that belong to multiple classes in supervised learning? I'm currently facing a problem in which some of my training examples belong to more than one class at the same time, say, sample $y_i$ pertains to class $A$ and $B$. I was thinking that a solution to it would be to consider that sample as two-fold, i.e., consider it as two samples, one for class $A$ and one for class $B$. However, my problem is that I'm performing a one-vs-all strategy, in which I think this solution may cause numerical errors (the feature matrix would have identical rows)!
Do you know of any reference to this kind of problem (or the technical name for it)?
Thanks in advance!
 A: This looks like a classic Multi Label Classification. There are dozens of possible approaches, in particular sklearn python library implements such methods.
In the most simple scenario, you can train classifiers on the "labels" basis. There won't be any problems with feature matrix, as you can simply divide your $m$ label problem, into $m$ single label problems, and train $m$ independent classifiers. Nice example can be found in sklearn documentation, where there are two binary labels (each sample can have label 1, label 2, both or none), and we simply convert it into two binary classification problems, working on the same input data, but with different labelings.

What is @juampa suggesting is actually something more complex - predicting a structurized labeling makes many assumptions (first of all - that there is any reliable structure in the labels, and that you can model it "by hand"). This can also be a solution, but I would leave it for the later stage, if you find that more common, simplier approaches are not enough. In particular, there are models and methods for predicting structured labels without apriori knowledge of that structure.
A: would a hierarchy of classifiers be a solution for you?
on a first level you find the classifiers corresponding to clusters, and then have classifiers for the subclusters
