How to deal with item belonging to more than one category

So I'm training a classification task which takes as input some description of the state of a 2x2x2 rubix cube and outputs the optimal move to take. And a potential problem I noticed is that in many states more than one move is optimal. In particular, only about 46% of states have only one optimal move, and 24% have 2, 12% have three, etc. So I have a few choices.

The options I thought of were

1. have each data point choose an optimal move at random
2. Do cross-entropy minimization with the data point containing the same probability for each optimal move. i.e (0.5,0.5,0,0,0,0,0,0,0) if the first two are optimal
3. Discard states with more than one optimal move (this seems really bad)

What is the standard practice? Also, is there a difference between 1 and 2?

If necessary you may assume that I'm using a neural network model

There are multiple ways you can do it. The first two options you propose would be valid but I'm not sure if the log-loss allows you to use probabilities as target as opposed to just binary labels, but if that is the case they will work for what you want. I have another suggestion. Let's say there are at any point n possible moves available (In case of a 2x2x2 there are three dimensions and in every dimension 4 moves I think, so that would be 12 options) you could train 12 classifiers or in the case of a neural networks just twelve sigmoids in the output layer. Then you can represent every move as a probability, represent the training targets as a vector of 1s and 0s with 1 as being an optimal move and then during classification pick the one with the highest probability.

An extension of your first option would be to add all the optimal moves as state. Say move 2 and 4 are optimal you could just add the same state twice with different labels.

EDIT: That said, I think your second option is the best one if the math works out (I'm uncertain about this and don't have time to figure it out right now) but the others will work as well.

EDIT2: According to Neil Slater the second option will work if it's implemented properly and I think that is the cleanest solution so I would go for that if possible, otherwise I would go for either go for the multiple samples for multiple optimal moves or the 12-way binary classification.

• Log loss will work correctly for values other than 0,1 provided the optimiser has been coded to allow for that input. I expect (but don't know) that multiclass logloss on softmax is most usually not coded this way and will not work - that's because with 0,1 you can make some really useful simplifications to the maths, and that has a large impact on the code. I have actually coded this at github.com/neilslater/ru_ne_ne/blob/master/ext/ru_ne_ne/… (the simple case is 4 lines of code, the complex one is longer and calls out to sub-functions not shown). – Neil Slater Sep 2 '16 at 7:24
• I can use the cross entropy loss for this right? Also, the number of outputs is currently equal to the number of moves. I think the two ways can work together. – davik Sep 2 '16 at 8:05
• Cross entropy loss and log loss are the same. Yes the difference between this and the approach I mentioned with 12 outputs with individual binary classification is that with the cross entropy + softmax solution you output a probability distribution over the moves and with the binary solution you have a probability distribution of yes/no optimal per move. – Jan van der Vegt Sep 2 '16 at 8:14
• Oh so you are suggesting no softmax? That sounds like a good idea – davik Sep 2 '16 at 16:30
• But doesn't this lose some information about confidence, so if I were to use this network to solve the cube, it would take longer. – davik Sep 2 '16 at 16:37