5
$\begingroup$

If one has a dataset large enough to learn a highly complex function, say learning chess game-play, and the processing time to run mini batch gradient descent on this entire dataset is too high, can I instead do the following?

  1. Run the algorithm on a chunk of the data for a large number of iterations and then do the same with another chunk and so on? (Such will not produce the same result as mini batch gradient descent as I am not including all data in one iteration, but rather learning from some data and then proceeding to learn on more data, beginning with the updated weights may still converge to a reasonably trained network.)

  2. Run the same algorithm (the same model also with only data varying) on different PC's (each PC using a chunk of the data) and then see the performance on a test set and take the final decision as a weighted average of all the different models outputs with the weight being high for the model which did the best on test sets?

$\endgroup$
1
$\begingroup$

Good question. It brings up the important consideration of practical computibility, what digital processes that exhibit intelligence can run fast enough on available hardware to be of use.

Rules Based Systems

In rules based (expert) systems, the search is based on predicate calculus, a mathematical model of human reasoning. The rules are an attempt to encapsulate the domain knowledge needed to solve expected problems.

In the case of chess, the rules are

a. the rules of the game and
b. the rules of excellence in winning game-play.

The search through the rules for each move presents an astronomical number of combinations 1, placing a burden on computing resources and the stake holders waiting for results. Strategies have emerged to achieve practical computibility, including these.

  • Limiting the permutations by dismissing nonsensical permutations
  • Following the more probable search paths first based on heuristics
  • Distributing the rule set (in a compiled and optimized state) to multiple computing nodes in a cluster
  • Finding commonly successful strategies and the conditions of when they are favorable and then executing them when appropriate

Artificial Networks

Artificial networks are circuits that attain acceptable behavior by progressively encoding knowledge in an N-dimensional array of parameters. The knowledge begins with an initial state, which is a guess, and then successive guesses2 converge on what is sufficiently encoded knowledge to produce acceptable circuit behavior in use.

MLPs, CNNs, RNNs, and other static topology machine learning components have their own characteristics that, taken together, place a heavy burden on computing resources and the stake holders. Each of these characteristics either produce a nested loop or a need for parallelism to replace the loop.

  • Iterations required for convergence
  • Iteration through each sample used in training
  • Iteration through layers for both forward propagation of the signals and the backward propagation and distribution of corrective feedback
  • Iteration through the channels specified by the width of each layer
  • The heart of approximating complex behavior are the functions that are not first degree equations, which are often called activations even though their action has little in common with the activation of neurons in vertebrates.

If, in your scenario, the game contains pseudo-random moves and is played by a robot that must bluff and detect bluffs, there may be additional dimensions added to both training and game-play.

  • Video adds pixel layer, horizontal and vertical positions, frame, and possibly camera angle
  • Audio adds FFT Hann windows, frequency with phase, and channel

Convergence and Practical Computibility

What is termed stochastic gradient descent does parameter updates after each example, which can be too slow. Strategies have emerged to achieve practical computibility, including these.

  • Shortening convergence time using back-propagation variants such as Momentum and Adaptive Moment Estimation
  • Batch gradient descent performs model updates at the end of each training epoch, where each epoch iterates through all training examples
  • Mini-batch gradient descent segments the training examples to find a balance between the robustness of stochastic gradient descent and the efficiency of batch gradient descent — This stragegy is in common use and the batches can be distributed to nodes in a super-computing cluster 3

The comment in the question that these methods do not produce the same result as stochastic gradient descent is correct. Mini-batch results (in terms of accuracy of convergence and reliability at finding the global minimum at all) is dependent on order of the batches if done serially with parameter adjustment at the end of each mini-batch. In other words if there are four mini-batches, Q, R, S, and T, the result of the training sequence Q-R-S-T will not be the same as Q-S-R-T or any other ordering of the four 3.

What is often abbreviated dataset is, from the perspective of statistics, a sample from a population. In chess, the population is every possible combination of moves and opponent moves to a game ending, including wins, loses, and stalemates.

When segmenting for mini-batch in a single computer process, the goal in selecting the sub-samples from the sample is to obtain a distribution of distributions of sub-sample characteristics that minimizes the difference between Q-R-S-T results and T-S-R-Q results.

The previous sentence is difficult to parse, but important. In simpler terms, the goal is to make the mini-batch produce results independent of mini-batch order. This equality in feature distribution between mini-batches is also important when the mini-batches are parallelized across a cluster because relative entropy4 impacts convergence rate.

Distributed Computing and Mini-batch

In a distributed computing scenario, once a convergence iteration is complete, the nodes communicate to distribute the results. The nature of the sharing of results between nodes can be as simple as averaging error, weighted by interim convergence accuracy, as the question implies, or as complex as another learning circuit to learn how to distribute results between nodes in parallel mini-batch architectures.

Additional Study

If you wish to understand practical computibility more deeply, study the two incompleteness theorems of Gödel, the limited completeness defined by Turing, the game theory of von Neumann, feedback theory of Wiener, and the application of these in deep learning.

Though seven years old, the concepts of this great primer covers some enduring concepts: Computability, constructivity, and convergence in measure theory, Jeremy Avigad, Department of Mathematical Sciences, Carnegie Mellon University, November, 2011


Notes

[1] The detection of a rule's condition, its antecedents, may lead to the execution of the rule's consequence. If there are several antecedents that apply, which one first is applied first may be a result of the order of the rules in a sequence of them. There may be meta rules to guide selection. If one takes the game of chess and examines the logical permutations of rule execution, even for a single chess move, the possibilities can grow astronomically. That challenge to practical computibility was termed the combinatorial explosion.

[2] Successive guesses in an optimization scheme are generally not random, although the injection of pseudo random perturbations or tries may increase convergence rates and reduce risk of confounding convergence by landing a local minimum when searching the error surface for the global minimum. This search is often accomplished via gradient descent, a scheme that uses the Jacobian of the feed forward functions (and sometimes their Hessian) to intelligently seek the minimum of disparity between current circuit behavior and some specified ideal. That ideal may be a closed form (formula) or a set of correct answers associated with each example, called labels.

[3] Except under the extremely rare coincidence that R is identical to S or by the much rarer coincidence that they are functionally equivalent in the given particular training scenario even though they are not identical.

[4] Kullback–Leibler divergence or relative entropy is a concept built over Claude Shannon's information theory. The term entropy, borrowed from the thermodynamic concept of entropy as a measure of disorder, is an important concept to understand in the quest to achieve practical computibility for a larger set of learn scenarios and the larger networks needed to learn them.

$\endgroup$
  • $\begingroup$ Coming back to this 6 months since I asked, with a lot more clarity on ML, this answer seems very detailed and the resources provided are very useful $\endgroup$ – pranav Dec 10 '18 at 4:21
-1
$\begingroup$

Note: in my answer, I'll assume you're using something like a Neural Network, since I don't believe you actually specified what kind of model you're using. My answer will probably also be correct for most other kinds of approaches, but maybe not for all possible approaches.


1) Run the algorithm on a chunk of the data for a large number of iterations and then do the same with another chunk and so on? It will not be the same as mini batch gradient descent as I am not including all data in one iteration but rather learning from some data and then proceeding to learn on more data ,beginning with the updated weights?

This might work if each of the chunks of data individually is still large enough and sufficiently representative of the distribution of the complete population, but probably not the best way to go. In fact, I don't expect it to perform much better than simply using only the very last chunk, and training only on that one. This is because of the following reason. Suppose you first train for a while on chunk A, then for a long time on chunk B, then for a long time on chunk C, etc. While learning on chunk B, there is a significant risk that your model will "forget" everything it learned from chunk A. When learning on chunk C afterwards, it can also "forget" everything learned from chunk B again.

In pseudocode, the approach you proposed here looks as follows:

for each chunk:
    for large number of iterations:
        learn on chunk()

An easy way to improve on that would be to swap the loops around:

for large number of iterations:
    for each chunk:
        learn on chunk()

What I just described there is actually how I interpret "mini-batch gradient descent" though, the chunks would be minibatches (and the minibatches / chunks would be randomly re-selected from the complete population in every iteration of the outer loop, you wouldn't always use the same chunks). Note that this wouldn't be effective if your dataset is so large that it doesn't fit inside your RAM all at the same time, because then you'll have to deal with excessive I/O.


2) Run the same algorithm(same model also with only data varying) on different PC's(each PC using a chunk of the data) and then see the performance on a test set and take the final decision as a weighted average of all the different models outputs with the weight being high for the model which did the best on test sets?

Yes, this can definitely be effective. This kind of idea (training different models on different subsets of data) is generally referred to as "ensemble" methods. You can even vary the models you use (e.g., have an ensemble with some Random Forests, some SVMs, some Neural Networks, etc.).

$\endgroup$
  • 1
    $\begingroup$ Thanks a lot. Really helpful. And yep,it is a neural network. $\endgroup$ – pranav Jul 28 '18 at 3:19

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.