Neural Network: What if there are multiple right answers for a given set of inputs?

Question

For a given input into the input nodes, there are multiple correct values for the output nodes. In the training set, there are times when the inputs result in a certain output, and other times when the inputs result in a completely different (but equally valid) output.

Will a neural network still be able to "figure out" a pattern? From what I know about backpropagation, it seems like the different right answers would prevent it from functioning properly. If that's so, are there any solutions?

I don't need the neural network to predict all possible correct solutions, but I do need it to output a correct solution.

Answer 1

A neural network can in principle deal with this. Actually, I believe they are among the best models for this task. The question is whether it is modeled correctly.

Say you are looking at a regression problem and minimize the sum of squares, i.e.

$$L(\theta) = \sum_i (\hat{y}_i - y_i)^2.$$

Here, $L$ is the loss function we minimize with respect to the parameters $\theta$ of our neural net $f$, which we use to find an approximation $\hat{y}_i = f(x_i; \theta)$ of $y_i$.

What will this loss function result in for ambiguous data like $(x_1, y_1), (x_1, y_2)$ with $y_1 \neq y_2$? It will make the function predict $f$ predict the mean of both.

This is a property which not only holds for neural nets, but also for linear regression, random forests, gradient boosting machines etc--basically every model that is trained with a squared error.

It makes now sense to investigate where the squared error comes from, so that we can adapt it. I have explained elsewhere that the squared error stems from the log-likelihood of a Gaussian assumption: $p(y|x) = \mathcal{N}(f(x; \theta), \sqrt{1 \over 2})$. Gaussians are uni modal, which means that this assumption is the core error in the model. If you have ambiguous outputs, you need an output model with many modes.

The most commonly used one is mixture density networks, which assume that the output $p(y|x)$ is actually a mixture of Gaussians, e.g.

$$p(y|x) = \sum_j \pi_j(x) \mathcal{N}(y|\mu_j(x), \Sigma_j(x)).$$

Here, $\mu_j(x), \Sigma_j(x)$ and $\pi_j(x)$ are all distinct output units of the neural nets. Training is done via differentiating the log-likelihood and back-propagation.

There are many other ways, though:

• This idea is applicable also to GBMs and RFs.
• A completely different strategy would be to estimate a complicated joint likelihood $p(x, y)$ which allows conditioning on $x$, yielding a complex $p(y|x)$. Efficient inference/estimation will be an issue here.
• A quite different example is certain Bayesian approaches which give rise to multimodal output distributions as well. Efficient inference/estimation is a problem here as well.

---

Answer 2

Perhaps an RNN can solve this "order doesn't matter" problem.

Consider the task of image captioning which has been successfully implemented by Stanford and Google. Now consider that an image might have multiple equally correct solutions, "dog playing with cat" or "cat playing with dog". I believe using an RNN (recurrent neural network) to spit out the text is the key to getting around this, because the RNN knows that if it already said "dog playing with" the next word should be "cat", and vice versa for "cat playing with" -> dog. http://cs.stanford.edu/people/karpathy/cvpr2015.pdf

Answer 3

Firstly there is no reason for back propagation to 'fail' in the case of ambiguous data. Here is why. Neural nets work by producing a truly highly non-linear function by composing linear functions with a non-linear activation function. The model class of neural nets are functions of this class. Roughly speaking a neural net produces a function as follows: At each stage a decision is made as to how many variables (features) to create. Each new variable is created by composing the non-linear activation function with an arbitrary linear combination of the previous variables. That means that there are (n+1)*(m) constants that are created . Each new variable is some unknown linear combination of the n variables of the previous stage plus a constant.

One wishes to minimize the difference between actual observations and predictions according to some loss function $L(\Theta ,x_i)$ where $\Theta$ is all the parameters created by the model, that is the unknown sets of coefficients of all the linear functions. Thus the loss function is a function of the parameter set ${\Theta}$ and one wishes to minimize L with respect to the "theta's"

In the case discussed by bayerj, that loss function is $L_{\Theta} = \sum_i (y_i - F_{\Theta} (x_i) )^2 $ . Where i runs over all the observations. The model is (in theory only !!!!) fitted by finding the parameters $\Theta$ which minimize this highly non-linear and non-convex function.

In general that is impossible to do. What one can do is find local minima of the function $L_{\Theta}$ as a function of ${\Theta} = (\theta_1, \ldots, \theta_M) $. Local minima can be calculated by various methods including gradient descent, which in the context of neural nets is called 'back propagation'. So there is nothing ambiguous about the y's being multivalued. That is because one is interested in solving the system of equations $ \frac{\partial L}{\partial w_i}=0 $ for $ i = 1 \ldots (n+1)m $ . There is no inconsistency because it treats each variable set and it's outcome as constants.

I will end with a little though experiment and a bigger thought experiment. An ordinary least squares model is a trivial case of a neural net in which the activation is linear and there is only one layer and one output. Imagine a data set consisting of $x_i = i, y_i = 3x_i + 'noise'$ and i running from 0 to 10,000. If I add a new observation $(x,y) = (0, 10) $ we have the ambiguous data points (0,noise) and (0,10) . However the other 9,999 observations favor the data point (0,noise) and the model will reflect a value much closer to zero than to 5 = (0+10)/2 .
Bigger thought experiment. Imagine one is trying to discover probability of loan default using a neural net with income data and loan to income ratio (LTI). Suppose one trains on 1000 people who don't default and 150 who do. Now add example 1151 a person with characteristics of the top 1% of the no-default crowd, but assign him to the default outcome. For example Mr. #1151 could have just discovered that his true love in life is gambling and not going to work every day. The model will still have no choice but to characterize him as default = 0. In essence, if one looks at the loss function for the first 150 people $L(x_i) = \mbox{nnet.train}(x_i) '=' 0 $ will be almost identical. To add $L(x_{151}$ to the mix will still have a loss function majorized by the behaviour on the first 150 examples. It cannot average.

Answer 4

If you have more than one output $o_1, o_2,..,o_n$ for the $n$ possible correct answers. I have found the following error function works for about up to 4 expected answers:

$$E(o) = \tanh|e-o_1| \tanh|e-o_2|...\tanh|e-o_n|$$

Where $e$ is the expected result which is a random one of the correct answers.

Notice that the error is $E(o_n)=0$ for all $n$ and that nowhere $E''(x)=0$