1
$\begingroup$

I am doing reinforcement learning in checkers.

After each game the network beats itself, I calculate the loss of every individual position in the game, call backward(), and step(). I am beginning to believe that this is not how SGD is supposed to be used, and that I should be feeding it batches, say a whole game at a time.

Strictly in terms of code:

  • Do I do this by just wrapping the collective inputs in a one dimensional tensor?
  • If I give SGD a collection of inputs does it sample from the collection, calculate the average loss, and use that gradient?
  • Is SGD actually intended to be used in this way with large 'collections'/batches?
$\endgroup$
  • $\begingroup$ Tell us more about the "network beats itself part", are you start with two randomly initialized networks and attempt to get some form of "next move"? i.e. you feed as one input sample all positions on a checker board and the output is a new (valid?) position of all pieces. Or are you using a recursive network and feeding the list of moves until now as the single sample? $\endgroup$ – grochmal May 23 '19 at 16:53
  • $\begingroup$ Its alphazero. The network takes a representation of the board and returns a scalar value and tensor over all (not necessarily legal) moves with logit probabilities. These are used in a UCT search as a value and policy improvement protocol. This has nothing to do with the spirit of my question, though, which is the SGD algorithm $\endgroup$ – basket May 23 '19 at 20:10
  • $\begingroup$ I' was genuinely worried that you were feeding individual moves without any context . I'll write this up more thoroughly later but the summary is that if you are using SGD over a single sample you are removing the randomness (the S) from the SGD. You kind of are doing DGD (definite gradient descent) since you know the sample you are taking at each step :). P.S. this will sound silly (sorry) but i always ask this: do you remember to zero out the gradients after each step? $\endgroup$ – grochmal May 24 '19 at 10:52
2
$\begingroup$

LT;DR: Executing SGD (Stochastic Gradient Descent) is almost like executing GD (Gradient Descent) but computationally cheaper, and probably the only way to execute GD on big datasets. By evaluating at each sample - each game - you are losing the advantages of SGD and one could say you're "rolling your own" version of a computationally cheap GD.

Gradient Descent Summary

After you evaluate the error/loss function of you model, with whatever criterion you may use, you will then attempt to take the gradient of your loss function at the point where your network is. To simply things let's assume that you are using cross-entropy as the criterion of the loss (which makes some sense if you are evaluating an entire matrix of probability results). Let's say that the loss function is, where $H$ is cross-entropy, $f$ the NN evaluation, $X$ input data and $Y$ the labels:

$$ E = H(f(X), y) $$

This is what nn.CrossEntropyLoss does (or any other criterion). We want to find the minima of $E$, for that we can use $\nabla E$ but we cannot get the general formula for $\nabla E$ because we do not have the actual formula for $f$. Yet, we can find the (vector) value of $\nabla E$ at the location we are in (where location is the value of every parameter/weight in our NN). We can find $\nabla E$ for one specific configuration of $W$ which will be the matrix of all weights in the network.

$$ \nabla E_{W} = \frac{2}{N} X^T(XW - y) $$

This is oversimplified - to actually find the matrix $W$ we need to perform backpropagation. In pytorch we get that by doing a huge chain rule with E.backward(). i.e. this is what backward() does, it gets the matrix $W$.

Now we have a handful of very expensive matrix multiplications to get from $W$ to $\nabla E_W$. Possibly prohibitively expensive if the dataset is big ($X$ is the full dataset). Enters SGD.

Stochastic Gradient Descent

The only difference in SGD from GD is that SGD will not use the entire $X$ in the calculation above. Instead SGD will select just a handful of samples (rows) from $X$ and use that as an estimation of $\nabla E_W$. Often it is said that SGD takes only a single sample from $X$ but implementations vary (e.g. ASGD).

Finally step() will apply $\nabla E_W$ times the learning rate to all weights/parameters in the network.

Your Approach

Since you are going sample by sample and performing backward() and step() on each sample you are not really doing SGD (despite calling that function). In your case the SGD optimizer has only a single sample to select from every time, therefore you are uniformly trying all samples in your dataset (as opposite to Stochastically). (That uniformity will reduce the variance of your model, which may be dangerous in other ways, although not very relevant here)

Therefore yes: To use SGD you do need to feed batches of input, and it will "average" (sum) the gradients across the sampled rows of $X$. It will average/sum/accumulate (sum all components) the gradients thanks to the fact that some samples may result in opposite gradient values in some directions; and hopefully the taken samples will agree on the main direction of the gradient and increase the magnitude in that direction.


P.S. The fact that pytorch accumulates the gradients from each selected sample is also one of the reasons we need to call zero_grad() in the training loop. You want to accumulate gradients within an SGD step but not accumulate across steps (SO question on exactly that).

Code

To actually generate batches you can use torch.randperm() I personally like this answer on SO about randperm but I'll add a summary here:

Having the matrix $X$ above as X (in code), one can create a batch of 256 samples with:

batch_size = 128
n_samples = X.size()[0]
permutation = torch.randperm(n_samples)

for i in range(0, n_samples, batch_size):

    indices = permutation[i:i+batch_size]
    batch_x, batch_y = X[indices], Y[indices]

    # nn(X), criterion(), backward(), step(), zero_grads(), ...

Which you need to perform per epoch (refer to linked answer for that and more - do not want to copy that code in full since I do not deserve the merit).

The tricky bit may be the fact that you need to generate the batch from both $X$ and $Y$, and keep the order between them. Using indices generated with randperm allows for that.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for your answer. In my case, should I use sgd over gd when it is not the case that I have a wealth of data since it is very computationally expensive to generate the games. I believe alpha zero did massive CPU parallelization and then sgd over the millions of positions generated. I think I have to use all the samples in my case? $\endgroup$ – basket May 26 '19 at 0:24
  • 1
    $\begingroup$ @basket - This is a statement full of assumptions which i never found a credible source for but: "Using SGD in on DNNs is preferable in general since it will increase the variance of the model and prevent overfitting to some extent" works in practice. Also alphazero is relatively deep a network, YMMV but in general DNN need a good deal of data to learn anything useful (In the thousands at the least). At first sight Checkers seems like a much simpler game than Go so really YMMV, but one may be surprised by game complexity. $\endgroup$ – grochmal May 27 '19 at 15:10

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.