# Neural Network accuracy and loss guarantees?

This question is part of a sample exam that I'm working on to prepare for the real one. I've been stuck on this one for quite a while and can't really motivate my answers since it keeps referring to guarantees, can someone explain what guarantees we can have in a neural network such as the one described?

Network description:

Assume a deep neural network (DNN) that takes as input images images of handwritten digits (e.g., MNIST). The input network consists of 28x28 = 784 input units, a hidden layer of logistic units, and a softmax group of 10 units as the output layer. The loss function is the cross-entropy. We have many training cases and we always compute our weight update based on the entire training set, using the error backpropagation algorithm. We use a learning rate thats small enough for all practical purposes, but not so small that the network doesnt learn. We stop when the weight update becomes zero. For each of the following questions, answer yes or no, and explain very briefly.

Questions:

1. Will this DNN configuration enable the the weights to minimize the loss value (there may be multiple global optima)?

2. Does this DNN configuration guarantee that the loss reduces on every step? We use our network to classify images by simply seeing which of the 10 output units gets the largest probability when the network is presented with the image, and declaring the number of that output unit to be the networks guessed label.

3. Does this DNN configuration guarantee that the number of mistakes that the network makes on training data (by following this classification strategy) never increases?

1. No. Assume you initialize all weights with the same value. Then all gradients (in the same layer) will be the same. Always. Hence the network effectively only learns one parameter per layer. It is possible (and likely) that this is neither a gloabl nor a local minimum of the network (which has more parameters).
2. Yes, as the learning rate is "small enough for all practical purposes". (No, if you use SGD or mini-batch gradient descent)
3. Usure. I think the correct answer is "No, the network can make more mistakes in between with cross entropy.". It is certainly sure to improve CE loss while at the same time getting worse at accuracy (see proof below). However, I'm not sure if the gradient would ever lead to such a result.

## Example for 3

#!/usr/bin/env python

from math import log

def ce(vec):
"""index 0 is the true class."""
return -(log(vec[0]) + sum([log(1-el) for el in vec[1:]]))

a = [0.1001, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.0999]
print(ce(a))
b = [0.49, 0.51, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
print(ce(b))


gives:

ce(a) = 3.24971912864
ce(b) = 1.42669977575


Hence the cross entropy loss dropped (as expected), the probability for the correct class increased (as expecte) but it makes a mistake (if you simply take the argmax).

• While it's true that you can find a way to reduce the cross-entropy and decrease the accuracy, I don't think that is possible with gradient descent. If you are following the gradient, you are by definition going in the direction that reduces the cross-entropy the most. In your example I don't think that training via GD could lead index 1 to go from .1 to .51. While that reduces the cross-entropy, the cross-entropy could be reduced further if the output of index 1 was decreased instead of increased. – J. O'Brien Antognini Jan 13 '17 at 21:43
• @J.O'BrienAntognini I'm not too sure if this can happen. However, it is important to see that a better cross-entropy does not necessarily mean the accuracy gets better. (Another problem might be the type of gradient descent: If it is stochastic / mini-batch gradient descent, even the loss might go up at some point) – Martin Thoma Jan 13 '17 at 21:47
• Absolutely, if SGD is used, then all bets are off. But I think that if it is strictly gradient descent on the entire training set, the accuracy can get no worse if you follow the gradient. While there are some directions you can move in parameter space that decrease both the cross-entropy and accuracy, the direction of steepest descent shouldn't decrease the accuracy. – J. O'Brien Antognini Jan 13 '17 at 21:54
• @J.O'BrienAntognini: I think there must be something wrong with your theory. In my experience (training many neural networks), it is entirely possible for loss to improve and accuracy to get worse during a single training run. I think what is missing from your argument is dealing with multiple samples (i.e. your argument possibly holds when there is one training example) – Neil Slater Jan 14 '17 at 12:27
• @MartinThoma: Yes that is most normal situation. Maybe I'll try to construct something in Numpy to show this really is a thing in practice during training on full batches. – Neil Slater Jan 14 '17 at 13:39

A guarantee is a proof that some algorithm will always have a certain performance (or the performance will never be worse than the guarantee). In general there are not a whole lot of theoretical guarantees for NNs. But this question is sufficiently limited in scope that some guarantees hold.

1. This question is maybe a little ambiguous, but I would lean towards answering "no". The question is asking whether the training will lead to a minimum, but they don't specify whether the minimum needs to be a global or a local minimum. If you simply descend down the gradient of the loss function (as we are doing here), you are extremely likely to end up at a local minimum, though unlikely to end up at a global minimum. However, in practice local minima are not much worse than global minima. I say that this is extremely likely to happen because there is a very small chance that you could accidentally land right on a saddle point. This would be a point with a vanishing gradient that is not a local minimum, and training would stop when you land there. (Or, even more unlikely, you could be very unlucky and start on a local maximum!) If they're looking for guarantees, you can't guarantee that that won't happen. But if the DNN is fairly large and the weight initialization is random, you can guarantee that it almost surely won't happen, so there is an argument to be made in favor of "yes".

2. Yes. Since we are descending the gradient of the loss function, the loss function can never increase on any step. (This is assuming the loss function is reasonably smooth.)

EDIT: After some discussion in another answer I have decided that my original answer was incorrect. My updated answer is below:

1. No. Although training will decrease the overall cross-entropy of the entire training set, it is possible that the cross-entropy on a single case will increase. It is therefore possible to construct a training set such that the classifications remain the same from one step to the next for all cases except this one particular example, which moves from a correct classification to an incorrect classification. The overall cross-entropy on the training set will decrease, but the accuracy will increase.