Data Science PT 4: Model Complexity

0.5 log2 (N) b 

Let's define a finite class of models C which is well-defined. If C is ∞, even for a finite N, we can have a sequence of increasingly complicated models. We will discuss parametric models soon. MDL evaluates various models beyond data compression. Given model c within class C, data X has a probability defined as Pc(X). With ~N^0.5 models, each has probability ~N^-0.5. MDL identifies c that minimizes len(c)+len(Y|X,c).

A simple model has very complex data, a complex model doesn't. A good trade-off between model complexity and data is a mid-sized model that captures the data rather well while still not being overly complex. The model will have a trade-off between its size and its descriptive ability. The variance will grow linearly with the number of elements in the model. The standard deviation is proportional to (N)^(-0.5).  This, we want the spacing to be closer to the standard deviation. The actual coding length for one of those parameters is 1/2 log(N) + O(1) bits.

Model complexity is the penalty for learning unknown parameters. The penalty is the excess coding length. We want to minimize the excess coding length. 

This is the probability for X within learning framework. We want to minimize len(c)[model class] + len(X|c)  [length of the data X conditioned on C]. In addition to data compression, model selection can perform other statistical inference tasks. This in fact actually motivates some machine learning approaches. 

What’s the ideal Θi that minimizes len(X, Θi)? len(X,Θi) = -N1(X)log2(Θi )-N0(X)log2(1-Θi). Thus we determine optimal Θemp or empirical probability, to be N1/N.

Let's give the example of the parametric model now. For one parameter, Xn is binary (0 or 1), independent, and identically distributed. P(Xn = 1) = Θ. As a result, P(Xn = 0) = 1 - Θ. To estimate the probability, count the numbers where Xn = 1 and then divide this by the number of elements. Empirical probability is N1/N where N = N0 + N1. We map the empirical probability to model class C. How about complicated class, C=[0,1]? A complicated class has infinite dimensions but also infinite coding length, or an unclear complexity.

Before, generating Xn, look at Xn-1. When Xn-1 = 0 then Pr(Xn = 1) = Θ0. When Xn-1 = 1 then Pr(Xn = 1) = Θ1. Here, Xn is no longer identically distributed random variables. In switching, if Θ0 = 0.9 then after 0 we usually have 1. If Θ1 = 0.1 then after 1 we rarely have 1. We want to select the correct "model". Given model c with Class C data has probability Pc(x) with (N)^(0.5)  models, each has probability (1/(N^0.5)). We can use the probability for data compression for model selection. 

In contrast, a finite size model class has a finite number of observations. The cardinality/size of the finite model depends on N.  The expectation or average can be defined as E[Xn]=1⋅Θ+0⋅(1-Θ)=Θ. Whereas the variance of the model can be defined as Var(Xn)=E[(Xn-E[Xn])^2]= Θ(1-Θ). As a result the standard deviation would be (Θ(1-Θ)) ^ (0.5). If we want to have (N^(0.5)) bins to represent the model, then possible model classes are {0, (1/N^(0.5)), (2/N^(0.5)), (3/N^(0.5)), ..., N}. 

Recall c*=argminc∈C{lenc(x)+len(c)}. If the lenght of c is constant, then c*=argminc∈C{lenc(x)}.  For the coin flip experiment, lenc(x) = -log2(Pc(x)) = -log2(Θ^(N0) * (1-Θ)^ (N-N0)). Bottom line is that we want to select the class that helps to maximize this probability. We need something close to (N)^(0.5) quantization bins. 

Taking the example of the coin toss, for heads we have Θ and for tails we have 1 - Θ. For 2 parameters we will have 2 states state 0 and state 1. Θ0 is the probability of going from state 0 to state 1 and Θ1 is the probability of remaining at state 1.

Here, we will utilize Q quantization bins. All models/bins have probability 1/Q, and Q = N ^ (α). Again to find α we can approximate the length equation to be  log2(N^α)-N1(X)log2(Θi +N^(-α)) -N0(X)log2(1-Θi -N^(-α)). For α<0.5, second part has polynomial coding length. For α>0.5, second part is negligible. Use α=0.5, or (N)^(0.5) quantization bins.

We will talk about regularization in this paragraph. Each parameter requires N^(0.5) models. With N elements and K parameters the total size of the space is O(N^(0.5K)) with the coding length to be 0.5Klog2(N) bits. Regularization helps the result to be simpler by penalizing model complexity. We can calculate the empirical probability to be Θemp = N1/(N0 + N1) or in simpler terms N1/N. Now if you run multiple (N) coin tosses you get the variance to be NΘ(1 - Θ). In a nutshell, we want to find the model with the highest data probability. The expectation of N times a value is NΘ. 

Let's go over an example problem. Let's say Xn has a probability mass function, P(Xn|Xn−1, Xn−2). For both Xn−1 and Xn−2, we have C probabilities for the next character. There are C - 1 degrees of freedom since we can infer the Cth parameter. For this C -1  = 1 parameter the complexity is 0.5log2(N) bits. Total complexity is ((C^2)(C−1)/2) * log2(N). Again, the length will be the number of bits added up with the other coding redundancy. 

Let's go over one more example. We want to characterize the model complexity of a simple model class for images. There are N^2 pixels in an image, with C allowable values per pixel, with a distribution relying on the pixel above, below, from the left, and to the right of the pixels. The number of possible contexts in pixels is C^4. Now we can assume that there are C - 1 degrees of freedom again, just like the previous example. Since the total number of pixels is  0.5log2(N^2) bits. So as a result, the model complexity is C^4(C − 1)log2(N). bits.  Again, equation is number of contexts (C^4) * coding length per parameter (C - 1) * number of parameters (log2N).