6.867 Machine Learning, Lecture 11 Notes

1 Lecture topics: model selection criteria • Minimum description length (MDL) • Feature (subset) selection Model selection criteria: Minimum description length (MDL) The minimum description length criterion (MDL) turns the model selection problem into a communication problem. The basic idea is that the best model should lead to the best way of compressing the available data. This view equates learning with the ability to compress data. This is indeed a sensible view since learning has to do with the ability to make predictions and effective compression is precisely based on such ability. So, the more we have learned, the better we can compress the observed data. In a classification context the communication problem is defined as follows. We have a sender and a receiver. The sender has access to the training data, both examples x1 , . . . , xn and labels y1 , . . . , yn , and needs to communicate the labels to the receiver. The receiver already has the examples but not the labels. Any classifier that perfectly classifies the training examples would permit the receiver to reproduce the labels for the training examples. But the sender (say we) would have to communicate the classifier to the receiver before they can run it on the training examples. It is this part that pertains to the complexity of the set of classifiers we are fitting to the data. The more choices we have, the more bits it takes to communicate the specific choice that perfectly classified the training examples. We can also consider classifiers that are not perfectly accurate on the training examples by communicating the errors that they make. As a result, the communication cost, the number of bits we have to send to the receiver, depends on two things: the cost of errors on the training examples (description length of the data given the model), and the cost of describing the selected classifier (description length of the model), both measured in bits. Simple two-part MDL. Let’s start by defining the basic concepts in a simpler context where we just have a sequence of labels. You could view the examples xi in this case just specifying the indexes of the corresponding labels. Consider the following sequence of mostly 1’s: n labels � �� � 1 1 1 −1 1 1 1 1 1 −1 1 . . . (1) 2 If we assume that each label in the sequence is an independent sample from the same distribution, then each yt ∈ {−1, 1} is a sample from P (yt |θ) = θδ(yt ,1) (1 − θ)δ(yt ,−1) (2) for some θ. Here δ(y1 , 1) is an indicator such that δ(yt , 1) = 1 if yt = 1 and zero otherwise. In our model P (yt = 1|θ) = θ. We don’t necessarily know that this is the correct model for the data. But whatever model (here a set of distributions) we choose, we can evaluate the resulting communication cost. Now, the question is: given this model for the data, how many bits do we need to send the observed sequence of n labels to the receiver? This can be answered generally. Any distribution over the data can be used as a basis for a coding sceme. Moreover, the op­ timal coding scheme, assuming the data really did follow our distribution, would require − log2 P (y1 , . . . , yn |θ) bits (base two logarithm) or − log P (y1 , . . . , yn |θ) nats (natural log­ arithm). We will use the natural logarithm for consistency with other material. You can always convert the answer to bits by multiplying nats by log(2). Since our model assumes that the labels are independent of each other, we get − log P (y1 , . . . , yn |θ) = n � − log P (yt |θ) (3) t=1 It is now tempting to minimize this encoding cost with respect to θ (maximizing the loglikelihood): � n � n � � min − log P (yt |θ) = − log P (yt |θ̂) (4) θ t=1 t=1 = −l(y1 , . . . , yn ; θ̂) (5) where l(D; θ) is again the log-likelihood of data D and θ̂ is the maximum likelihood setting of the parameters. This corresponds to finding the distribution in our model (one corre­ sponding to θ̂) that minimizes the encoding length of the data. The problem is that the receiver needs to be able to decode what we send. This is only possible if they have access to the same distribution (be able to recreate the code we use). So the receiver would have to know θ̂ (in addition to the model we are considering but we will omit this part, assuming that the receiver already knows the type of distributions we are have). The solution is to encode the choice of θ̂ as well. This way the receiver can recreate our steps to decode the bits we have sent. So how do we encode θ̂? It is a continuous parameter 3 and it might seem that we need an infinite number of bits to encode a real number. But not all θ can arise as ML estimates of the parameters. In our case, the ML estimates of the parameters θ have the following form θ̂ = n̂(1) n (6) where n̂(1) is the number of 1’s in the observed sequence. There are thus only n+1 possible values of θ̂ corresponding to n̂(1) ∈ {0, . . . , n}. Since the receiver already knows that we are encoding a sequence of length n, then we can just send θ by defining a distribution over its 1 possible discrete values, say Q(θ = k/n) = n+1 for simplicity (i.e., a uniform distribution over possible discrete values). As before the cost in bits (nats) is − log Q(θ̂) = log(n + 1). The total cost we have to send to the receiver is therefore DL of data given model DL of model � �� � � �� � DL = −l(y1 , . . . , yn ; θ̂) + log(n + 1) (7) This is known as the description length of the sequence. The minimum description length criterion simple finds the model that leads to the shortest description length. Asymptoti­ cally, the simple two-part MDL principle is essentially the same as BIC. Universal coding, normalized maximum likelihood. The problem with the simple two part coding is that the description length we associate with the second part, the model, may seem a bit arbitrary. We can correct this by finding a distribution that is in some sense universally closest to just encoding the data with the best fitting distribution in our model: − log PN M L (y1 , . . . , yn ) ≈ min −l(y1 , . . . , yn ; θ) = − max l(y1 , . . . , yn ; θ) θ θ (8) In other words, we don’t wish to define a prior over the parameters in our model so as to encode the parameter values. While it won’t be possible to achieve the above approximate equality with equality since the right hand side, if exponentiated, wouldn’t define a valid distribution (because of the ML fitting). The distribution that minimizes the maximum deviation in Eq.(8) is given by exp (maxθ l(y1 , . . . , yn ; θ)) � � � exp (maxθ l(y1 , . . . , yn ; θ)) y � ,...,yn PN M L (y1 , . . . , yn ) = � (9) 1 and is known as the normalized maximum likelihood distribution. Using this distribution 4 to encode the sequence leads to a minimax optimal coding length Parametric complexity of model � � � �� �� � � − log PN M L (y1 , . . . , yn ) = − max l(y1 , . . . , yn ; θ) + log exp max l(y1 , . . . , yn ; θ) (10) θ � y1� ,...,yn θ Note that the result is again in the same form, the negative log-likelihood with a ML param­ eter setting and a complexity penalty. The new parametric complexity penalty depends on the length of the sequence as well as the model we use. While the criterion is theoretically nice, it is hard to evaluate the parametric complexity penalty in practice. Feature subset selection Feature selection is a problem where we wish to identify components of feature vectors most useful for classification. For example, some components may be very noisy and therefore unreliable. Depending on how such features1 would be treated in the classification method, it may be best not to include them. Here we assume that we have no prior knowledge of which features might be useful for solving the classification task and instead have to provide an automated solution. This is a type of model selection problem, where the models are identified with subsets of the features we choose to include (or the number of features we wish to include). Note that kernels do not solve nor avoid this problem. By taking an inner product between feature vectors that may contain many noisy or irrelevant features results in an unnecessarily varying kernel value. Instead of selecting a subset of the features we could also try to weight them according to how useful they are. This is a related feature weighting problem and we will get to this later on. This is also the method typically used with kernels (cf. kernel optimization). Let’s address the feature selection problem a bit more concretely. Suppose our input features are d−dimensional binary vectors x = [x1 , ..., xd ]d where xi ∈ {−1, 1} and labels are binary y ∈ {−1, 1} as before. We will begin by using a particular type of probability model known as Naive Bayes model to solve the classification problem. This will help tie our MDL discussion to the feature selection problem. In the Naive Bayes model, we assume that the features are conditionally independent given the label so that � d � � P (x, y) = P (xi |y) P (y) (11) i=1 1 We will refer to the components of the feature/input vectors as “features”. 5 Put another way, in this model, the features are correlated only through the labels. We will contrast this model with a “null model” that assumes that none of the features are relevant for the label: � d � � P0 (x, y) = P (xi ) P (y) (12) i=1 In other words, in this model we assume that the features and the label are all independent of each other. The Naive Bayes model (as well as the null model) are generative models in the sense that they can generate all the data, not just the labels. These models are typically trained using the log-likelihood of all the data as the estimation criterion. Let us follow this here as well. We will discuss later on how this affects the results. So, we aim to maximize � d � n n � � � log P (xt , yt ) = log P (xti |yt ) + log P (yt ) (13) t=1 t=1 = = i=1 d n �� log P (xti |yt ) + i=1 t=1 � d � � i=1 n � log P (yt ) (14) t=1 � n̂iy (xi , y) log P (xi |y) xi ,y + � n̂y (y) log P (yt ) (15) y where we have used counts n̂iy (xi , y) and n̂y (y) to summarize the available data for the purpose of estimating the model parameters. n̂iy (xi , y) indicates the number of training instances that have value xi for the ith feature and y for the label. These are called sufficient statistics as they are the only things from the data that the model cares about (the only numbers computed from the data that are required to estimate the model parameters). The ML parameter estimates, values that maximize the above expression, are simply fractions of these counts: n̂y (y) n n̂iy (xi , y) P̂ (xi |y) = n̂y (y) P̂ (y) = (16) (17) As a result, we also have P̂ (xi , y) = P̂ (xi |y)P̂ (y) = n̂iy (xi , y)/n. If we plug these back into 6 the expression for the log-likelihood, we get ˆl(Sn ) = n � log P̂ (xt , yt ) (18) t=1 � � � � d � � n̂iy (xi , y) � n̂y (y) = n log P̂ (xi |y) + log P̂ (yt ) n n y xi ,y i=1 ⎡ ⎤ ˆ ) −Ĥ(Xi |Y ) −H(Y �� � �� �� �⎥ d � � ⎢� ⎢ = n⎣ P̂ (xi , y) log P̂ (xi |y) + P̂ (y) log P̂ (yt )⎥ ⎦ i=1 xi ,y � = n − d � (19) (20) y � Ĥ(Xi |Y ) − Ĥ(Y ) (21) i=1 where Ĥ(Y ) is the Shannon entropy (uncertainty) of y relative to distribution P̂ (y) and Ĥ(Xi |Y ) is the conditional entropy of Xi given Y . Entropy H(Y ) measures how many bits (here nats) we would need on average to encode a value y chosen at random from P̂ (y). It is zero when y is deterministic and takes the largest value (one bit) when P̂ (y) = 1/2 in case of binary labels. Similarly, the conditional entropy Ĥ(Xi |Y ) measures how uncertain we would be about Xi if we already knew the value for y and the values for these variables were sampled from P̂ (xi , y). If xi is perfectly predictable from y according to P̂ (xi , y), then Ĥ(Xi |Y ) = 0. We can perform a similar calculation for the null model and obtain � d � n � � ˆl0 (Sn ) = log P̂0 (xt , yt ) = n − Ĥ(Xi ) − Ĥ(Y ) t=1 (22) i=1 Note that the conditioning on y is gone since the features were assumed to be independent of the label. By taking a difference of these two, we can gauge how much we gain in terms of the resulting log-likelihood if we assume the features to depend on the label: ˆl(Sn ) − ˆl0 (Sn ) = n d � � � Ĥ(Xi ) − Ĥ(Xi |Y ) (23) i=1 The expression Iˆ(Xi ; Y ) = Ĥ(Xi ) − Ĥ(Xi |Y ) (24) 7 is known as the mutual information between xi and y, relative to distribution P̂ (xi , y). Mutual information is non-negative and symmetric. In other words, Iˆ(Xi ; Y ) = Ĥ(Xi ) − Ĥ(Xi |Y ) = Ĥ(Y ) − Ĥ(Y |Xi ) (25) To understand mutual information in more detail, please consult, e.g., Cover and Tomas listed on the course website. So, as far as feature selection is concerned, our calculation so far suggests that we should select the features to include in the decreasing order of Iˆ(Xi ; Y ) (the higher the mutual information, the more we gain in terms of log-likelihood). It may seem a bit odd, however, that we can select the features individually, i.e., not consider them in specific combinations. This is due to the simple Naive Bayes assumption, and our use of the log-likelihood of all the data to derive the selection criterion. The mutual information criterion is nevertheless very common and it is useful to understand how it comes about. We will now turn to improving this a bit with MDL.