4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I believe that most typical algorithms can be adapted to this setting. The problem is that it is not usually done/well known, since the problem is not that relevant. Anyway you are right, generally it is not possible (e.g. I would not know how to do it in the case of an SVM). $\endgroup$ – bayerj May 3 '14 at 18:26
3
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Forgive me if I missed something but isn't predicting the "mean of both" exactly the opposite of what we need? We need it to predict either one or the other, and exclude things like "mean" as wrong answers. $\endgroup$ – pete Aug 12 '15 at 18:50
  • 2
    $\begingroup$ It depends. If that is not what you want, you should a different likelihood function for your model, e.g. a mixture density network. $\endgroup$ – bayerj Aug 17 '15 at 6:31
  • $\begingroup$ Yeah you're right; I misread your answer at first $\endgroup$ – pete Aug 23 '15 at 21:15
  • $\begingroup$ @bayerj . I am skeptical your answer is correct. Imagine a regression trained on millions of data points including say (0,0) and that the model has intercept zero. Now add the point (0,100) to the training set. The mean of the new data set will be approximately zero and the model will still approximately predict that 0 -> 0 . Am I missing something ? $\endgroup$ – aginensky Jun 30 '17 at 15:36
  • $\begingroup$ @bayerj I think the same argument will work for any model that produces outputs that are continuous functions of their inputs- including neural nets. It is certainly true that abstractly the loss function will be minimized by having the model output the mean of the $y_i$'s, but it may be impossible to get that value from a continuous f(x) . So maybe your answer is correct for things like random forests and boosting. $\endgroup$ – aginensky Jun 30 '17 at 15:37
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.