The Elements of Statistical Learning. Data Mining_ Inference_ and Prediction (811377), страница 55
Текст из файла (страница 55)
We need some way of approximating Pr(Z|Mm ).A so-called Laplace approximation to the integral followed by some othersimplifications (Ripley, 1996, page 64) to (7.37) giveslog Pr(Z|Mm ) = log Pr(Z|θ̂m , Mm ) −dm· log N + O(1).2(7.40)Here θ̂m is a maximum likelihood estimate and dm is the number of freeparameters in model Mm . If we define our loss function to be−2 log Pr(Z|θ̂m , Mm ),this is equivalent to the BIC criterion of equation (7.35).Therefore, choosing the model with minimum BIC is equivalent to choosing the model with largest (approximate) posterior probability. But thisframework gives us more.
If we compute the BIC criterion for a set of M ,7.8 Minimum Description Length235models, giving BICm , m = 1, 2, . . . , M , then we can estimate the posteriorprobability of each model Mm as1e− 2 ·BICmPMℓ=11e− 2 ·BICℓ.(7.41)Thus we can estimate not only the best model, but also assess the relativemerits of the models considered.For model selection purposes, there is no clear choice between AIC andBIC. BIC is asymptotically consistent as a selection criterion.
What thismeans is that given a family of models, including the true model, the probability that BIC will select the correct model approaches one as the samplesize N → ∞. This is not the case for AIC, which tends to choose modelswhich are too complex as N → ∞. On the other hand, for finite samples,BIC often chooses models that are too simple, because of its heavy penaltyon complexity.7.8 Minimum Description LengthThe minimum description length (MDL) approach gives a selection criterion formally identical to the BIC approach, but is motivated from anoptimal coding viewpoint. We first review the theory of coding for datacompression, and then apply it to model selection.We think of our datum z as a message that we want to encode andsend to someone else (the “receiver”).
We think of our model as a way ofencoding the datum, and will choose the most parsimonious model, that isthe shortest code, for the transmission.Suppose first that the possible messages we might want to transmit arez1 , z2 , . . . , zm . Our code uses a finite alphabet of length A: for example, wemight use a binary code {0, 1} of length A = 2. Here is an example withfour possible messages and a binary coding:MessageCodez10z210z3110z4111(7.42)This code is known as an instantaneous prefix code: no code is the prefix of any other, and the receiver (who knows all of the possible codes),knows exactly when the message has been completely sent. We restrict ourdiscussion to such instantaneous prefix codes.One could use the coding in (7.42) or we could permute the codes, forexample use codes 110, 10, 111, 0 for z1 , z2 , z3 , z4 .
How do we decide whichto use? It depends on how often we will be sending each of the messages.If, for example, we will be sending z1 most often, it makes sense to use theshortest code 0 for z1 . Using this kind of strategy—shorter codes for morefrequent messages—the average message length will be shorter.2367. Model Assessment and SelectionIn general, if messages are sent with probabilities Pr(zi ), i = 1, 2, . .
. , 4,a famous theorem due to Shannon says we should use code lengths li =− log2 Pr(zi ) and the average message length satisfiesXE(length) ≥ −Pr(zi ) log2 (Pr(zi )).(7.43)The right-hand side above is also called the entropy of the distributionPr(zi ). The inequality is an equality when the probabilities satisfy pi =A−li . In our example, if Pr(zi ) = 1/2, 1/4, 1/8, 1/8, respectively, then thecoding shown in (7.42) is optimal and achieves the entropy lower bound.In general the lower bound cannot be achieved, but procedures like theHuffman coding scheme can get close to the bound.R Note that with aninfinite set of messages, the entropy is replaced by − Pr(z) log2 Pr(z)dz.From this result we glean the following:To transmit a random variable z having probability density function Pr(z), we require about − log2 Pr(z) bits of information.We henceforth change notation from log2 Pr(z) to log Pr(z) = loge Pr(z);this is for convenience, and just introduces an unimportant multiplicativeconstant.Now we apply this result to the problem of model selection.
We havea model M with parameters θ, and data Z = (X, y) consisting of bothinputs and outputs. Let the (conditional) probability of the outputs underthe model be Pr(y|θ, M, X), assume the receiver knows all of the inputs,and we wish to transmit the outputs. Then the message length required totransmit the outputs islength = − log Pr(y|θ, M, X) − log Pr(θ|M ),(7.44)the log-probability of the target values given the inputs.
The second termis the average code length for transmitting the model parameters θ, whilethe first term is the average code length for transmitting the discrepancybetween the model and actual target values. For example suppose we havea single target y with y ∼ N (θ, σ 2 ), parameter θ ∼ N (0, 1) and no input(for simplicity). Then the message length islength = constant + log σ +(y − θ)2θ2+.2σ 22(7.45)Note that the smaller σ is, the shorter on average is the message length,since y is more concentrated around θ.The MDL principle says that we should choose the model that minimizes (7.44). We recognize (7.44) as the (negative) log-posterior distribution, and hence minimizing description length is equivalent to maximizingposterior probability.
Hence the BIC criterion, derived as approximation tolog-posterior probability, can also be viewed as a device for (approximate)model choice by minimum description length.2370.0-1.0sin(50 · x)1.07.9 Vapnik–Chervonenkis Dimension0.00.20.40.60.81.0xFIGURE 7.5.
The solid curve is the function sin(50x) for x ∈ [0, 1]. The green(solid) and blue (hollow) points illustrate how the associated indicator functionI(sin(αx) > 0) can shatter (separate) an arbitrarily large number of points bychoosing an appropriately high frequency α.Note that we have ignored the precision with which a random variablez is coded. With a finite code length we cannot code a continuous variableexactly.
However, if we code z within a tolerance δz, the message lengthneeded is the log of the probability in the interval [z, z+δz] which is well approximated by δzPr(z) if δz is small. Since log δzPr(z) = log δz + log Pr(z),this means we can just ignore the constant log δz and use log Pr(z) as ourmeasure of message length, as we did above.The preceding view of MDL for model selection says that we shouldchoose the model with highest posterior probability.
However, many Bayesians would instead do inference by sampling from the posterior distribution.7.9 Vapnik–Chervonenkis DimensionA difficulty in using estimates of in-sample error is the need to specify thenumber of parameters (or the complexity) d used in the fit. Although theeffective number of parameters introduced in Section 7.6 is useful for somenonlinear models, it is not fully general.
The Vapnik–Chervonenkis (VC)theory provides such a general measure of complexity, and gives associatedbounds on the optimism. Here we give a brief review of this theory.Suppose we have a class of functions {f (x, α)} indexed by a parametervector α, with x ∈ IRp . Assume for now that f is an indicator function,that is, takes the values 0 or 1. If α = (α0 , α1 ) and f is the linear indicator function I(α0 + α1T x > 0), then it seems reasonable to say that thecomplexity of the class f is the number of parameters p + 1. But whatabout f (x, α) = I(sin α · x) where α is any real number and x ∈ IR? Thefunction sin(50 · x) is shown in Figure 7.5.
This is a very wiggly functionthat gets even rougher as the frequency α increases, but it has only oneparameter: despite this, it doesn’t seem reasonable to conclude that it hasless complexity than the linear indicator function I(α0 + α1 x) in p = 1dimension.2387. Model Assessment and SelectionFIGURE 7.6. The first three panels show that the class of lines in the planecan shatter three points.
The last panel shows that this class cannot shatter fourpoints, as no line will put the hollow points on one side and the solid points onthe other. Hence the VC dimension of the class of straight lines in the plane isthree. Note that a class of nonlinear curves could shatter four points, and hencehas VC dimension greater than three.The Vapnik–Chervonenkis dimension is a way of measuring the complexity of a class of functions by assessing how wiggly its members canbe.The VC dimension of the class {f (x, α)} is defined to be thelargest number of points (in some configuration) that can beshattered by members of {f (x, α)}.A set of points is said to be shattered by a class of functions if, no matterhow we assign a binary label to each point, a member of the class canperfectly separate them.Figure 7.6 shows that the VC dimension of linear indicator functionsin the plane is 3 but not 4, since no four points can be shattered by aset of lines.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
