Randomness in Deep Learning Systems: Monte Carlo and Las Vegas Methods

Monte Carlo methods play a super important role in the new generation of deep learning systems. While Monte Carlo based techniques have been around for a while, the explosion of multi-dimensional data sets common in deep learning system have brought its relevance to another level. Monte Carlo techniques fall into the category of randomized algorithms that attempt to provide an answer to a problem that entails certain degree of randomness. In that space, Monte Carlo methods are seeing as an alternative to another “gambling paradise”: Las Vegas.

Las Vegas vs. Monte Carlo

The main difference between Monte Carlo and Las Vegas techniques is related to the accuracy of the output. Las Vegas methods tend to always provide an exact answer while Monte Carlo methods are return answers with a random amount of error. Obviously, the degree of error in Monte Carlo system decreases with the increase in resources such as data or computation models.

A classic example of Las Vegas algorithms is the randomized quick sort algorithm which picks a pivot at random, and then partitions the elements into three sets: all the elements less than the pivot, all elements equal to the pivot, and all elements greater than the pivot.

The randomized quick sort method tends to consume a lot of resources but guarantees an exact answer. Consequently, Las Vegas methods tend to be recommended in scenarios with a small number of potential answers.

Even though Las Vegas models seem great in theory, they result unpractical in many deep learning scenarios that, are so large, that can never expect to produce an exact answer. Monte Carlo techniques addresses some of the limitations of Las Vegas algorithms by improving the efficiency of the computation graph introducing certain level of randomness in the answers. Not surprisingly, Monte Carlo techniques have become incredibly popular in deep learning scenarios that deal with multi-dimensional, large volume datasets.

One of the main applications of Monte Carlo methods in deep learning systems is to draw samples from some probability distribution that represents a dataset. This is typically known as Monte Carlo sampling and has been widely used throughout history to solve highly complex data estimation problems. In one of the most notorious examples, French mathematician Pierre-Simon Laplace once proposed a method to estimate the value of pi using Monte Carlo sampling.

In the context of deep learning systems, Monte Carlo sampling methods have very well-known applications. For instance, it is common to leverage Monte Carlo sampling to select a distribution of the training dataset that approximates the original dataset. Monte Carlo methods also play a role in regularization or optimization techniques estimating the output datasets without having the evaluate the entire computation graph.