Data Science PT 3: Machine Learning Concepts, Minimum Description Length

We can define features as explanatory variables. For example, the user's zip code, the past browsing history, for some examples. The outcomes are what we actually measure, for example in ad click retention, if the user clicked on the ad. Not all features are useful, so we will use feature selection to select what's good and what's not. 

In supervised learning, we have features and outcomes. As a result, we want to lean a function that approximates or predicts the outcomes for the features. 2 types of supervised learning are classification and regression. In classification, the outcomes are binary (click prediction). In regression the outcomes are more continuous (financial prediction). Unsupervised learning will have less of an emphasis on this course, but we don't know the outcomes here, and in unsupervised learning, we want to learn the data's structure. Examples of this are density estimation and clustering. 

The training data is used to train the model, whereas the test data is used to verify the model and validate the model. This is also called the holdout data. We can also partition into test/training data multiple times too ensure that the result isn't too sensitive to a specific partition. An online algorithm learns from input data as it comes along. The advantage here is that it is responsive. The disadvantage is that it doesn't learn as well. Offline algorithms first waits for the entire data, then runs the algorithm. It has superior learning, but we have to wait a significant amount of time (the end of data processing) to learn. Batch learning is a middle ground between the two, learning from chunks of input data. 

Mathematical models are an abstraction of how to organize/capture the essence of data. The algorithm fits model to data.

Real world data is often far more complex. Complex models explain data well but is difficult to work with. Simple models are nice to work with, but don't quite capture the intricacies of data. Therefore, there is a trade-off. The question is now, What’s the optimal trade-off between data size, computation, and learning? How do we choose the "correct" model? 

Let's define model class C with x as the input data. Our goal  is to choose the “correct” c* ∈C for x. Given c∈C, x has probability Pc(x). A complex model c has more parameters / requires large coding length len(c) vs a simple model.  In information theory, lenc(x)=-log2(Pc(x)). Minimum Description Length (MDL) is a model selection principle where the shortest description of the data is the best model. We can code the equation as follows: 

c*=argminc∈C{lenc(x)+len(c)}

N models have 1 parameter, N^2 models have 2 parameters, and so on. The first term in the c* describes the data, whereas the second term describes c. There can be a parametric class with a fixed number of parameters. We want to first specify c using len(c)=-log2(Pr(c)) bits. We can specify x using lenc(x)=-log2(Pc(x)) bits. 

Minimum Description Length is only one approach and it is related to maximum a posteriori (MAP) estimation. Occam's Razor states that among competing hypotheses, the one with the fewest assumptions should be selected. Statisticians often call the MDL coding length "model selection". 

Again the coding length is defined as len(x)=minc∈C{lenc(x)+len(c)}.

Now let's talk about a mixture of data X and class C. Using all models simultaneously, we will assign probability to X. We also assign greater probability to simpler models. The equation for minimum description length is argmaxc∈C{Pr(c)*Pr(X|c)} = argmaxc∈C{Pr(X,c)}. This gives the 

Pr(x) =  Σc∈CPr(c)*Pr(X|c) = Σc∈CPr(X,c) >= Pr(X,c*). This yields a more precise probabilitistic model for X, but it can also be computationally challenging. This will serve as a leadup to our next article, Model Complexity.