Consistency between two outputs of a neural network I'm trying to fit a dense neural network based on tabular data input, where the outputs are two separate classification vectors, with one cross-entropy loss function for each.
Example: given a few input features, for a customer that visits a travel website with the intention of buying a train ticket, the model would predict both the destination of travel and the traveling class (1st class or 2nd class) that the customer is likely to buy.
Problem: it seems as if internally, the network was divided in two at some point in the hidden layers, and each sub-network got specialised in predicting one output vector, ignoring the other. This leads to an overall acceptable accuracy for each output, but the consistency between the two outputs leaves to be desired.

For example, for a given entry, the network would predict "London" and "1st Class", because independently, each output makes sense according to the input features, but there isn't a single training point where London and 1st class can be found together, simply because there isn't a 1st class option when travelling to London. The network seems to be completely devoid of any concern for the consistency between the two.
Example, if the passenger is an accountant, 35yo and departs from Brussels, the training set gives a clear winner for destination: London and, separately, also for class: 1st, and so this is what the network will tend to predict, despite this combination being totally absent.

Would there be any way to amend the network and/or the organisation of the loss functions so that the consistency between the two outputs would be taken into account, and the network would avoid combination of outputs that can't be found in the training set, and favor those that are?
More generally, what would be some good approaches to tackle this issue? Note that I would like to avoid resorting to manual rules down the line, if that is possible.
 A: Another method would be to build two neural networks. The first NN is trained to predict the destination. For the second NN, include the destination predicted by the first NN as an input feature and train the network to predict the class. The second network should then learn to only predict classes that are options for the predicted destination.
Edited in response to @Jivan's comment.
There are more complex methods of multi-label classification, but I'd keep it simple if possible, and try either @Dikran's or my approach first. They are both standard ways of implementing multi-label classification (see this Medium post). Dikran's method is a Label Powerset and mine is a Classifier Chain. As you've pointed out, there are pros and cons to both these methods. If neither of these produce a good enough result, you could try a variation of the classifier chain, where you build one network to predict one label from the union of destinations and classes. Then train two further networks, one that predicts the destination given a predicted class and the other that predicts the class given a predicted destination. At inference time, you would use the first network to predict either a class or destination, then the appropriate second network predict the other label.
A: Cost function
In what way would your neural network be able to know that the 1st class with destination London is not feasible? How do you teach that to the network? In what way did you 'punish' the network during training for wrong predictions?
It is important that the training phase allows the network to train the desired features. In your question, you did not tell which cost function you used to train the model.
It is also not clear what type of output is created by your model and what you would desire from it. Do I guess correctly that the output is just a single class prediction? In that case, what class prediction would you favor in the example from the question.
Is 'London 2nd class' a better prediction than 'London 1st class'?
When this cost function only cares about a single error then it is gonna care less about combined errors. That might lead to your problem (I am assuming that this is how your cost function is created, but it is not clear).
Predicting London + 1st class will be wrong in the 89302 cases when the true value is Londen + 2nd class. But the choice to predict the 1st class instead of 2nd class might be rewarded in the 48516 + 41411 + 38186 + 35247 + 28512 cases when the true value is Paris/Rome/Berlin/Madrid/Rotterdam + 1st class (I am not sure, but I guess that your cost function is doing this).
You can punish the system for making predictions about 1st class when it is in London, but at the same time you reward 1st class predictions when the occur in other cities. So you are getting Londen 1st class as result.
Type of output
I mentioned earlier that I am guessing that your model is just giving a single class prediction. I am guessing this based on your situation as well as on the phrase

For example, for a given entry, the network would predict "London" and "1st Class"

If that is the case then you might consider to use a different type of output. Instead of predicting a single class you could have as output a vector of probabilities for all desired combinations of destinations and classes (as well as other aspects that you might have in your model). Then you could value the predictions and perform the training based on a likelihood function of a categorical distribution.
When you apply this model (some online shopping tool or some help for an airline company?) then it will not give a single class as output, but instead it could give a ranking of the top destinations.
Network structure
What kind of dense neural network do you have and how did your train it? It might be imaginable that there should be a node in some of those layers that gets trained to deal with the London + 2nd class case specifically. But, how many layers do you have, how many nodes per layer do you have, how did you do cross-valdiation?
It is imaginable that this error/false-prediction might occur. But it is difficult to say why and how exactly it occurs without details.
A: If consistency is a problem I would make it a single classification task where "London first class", "London second class", ..., "Rome first class" and "Rome second class" were distinct classes, rather than make it two distinct classification tasks.  You current network architecture is giving the a-priori hint that they are completely distinct classification tasks, but if e.g. some destinations don't have both classes, then there is a dependence between the two sub-classes.  Combining the two classification tasks into one would be the easiest way of putting the dependence back into the model.
At the moment, I think your model is predicting that the customer would opt for a first class ticket if it were available, which is not an unreasonable answer - it is just generalising the idea that people in relatively well paid occupations (e.g. accountant) tend to travel first-class.  You could always just ignore the class output where it is not an option.
Does the network really need so many layers?  It could be that a single hidden layer may be sufficient for this problem and the layer above that is not actually doing much useful processing, in which case the division of the network may not be that meaningful.
