Trang 1
Introduction to Machine Learning 67577 - Fall, 2008 Amnon Shashua School of Computer Science and Engineering The Hebrew University of Jerusalem Jerusalem, Israel arXiv:0904.3664v1 [cs.LG] 23 Apr 2009
Trang 3
Contents 1 Bayesian Decision Theory page 1 1.1 Independence Constraints 5 1.1.1 Example: Coin Toss 7 1.1.2 Example: Gaussian Density Estimation 7 1.2 Incremental Bayes Classifier 9 1.3 Bayes Classifier for 2-class Normal Distributions 10 2 Maximum Likelihood/ Maximum Entropy Duality 12 2.1 ML and Empirical Distribution 12 2.2 Relative Entropy 14 2.3 Maximum Entropy and Duality ML/MaxEnt 15 3 EM Algorithm: ML over Mixture of Distributions 19 3.1 The EM Algorithm: General 21 3.2 EM with i.i.d. Data 24 3.3 Back to the Coins Example 24 3.4 Gaussian Mixture 26 3.5 Application Examples 27 3.5.1 Gaussian Mixture and Clustering 27 3.5.2 Multinomial Mixture and ”bag of words” Application 27 4 Support Vector Machines and Kernel Functions 30 4.1 Large Margin Classifier as a Quadratic Linear Programming 31 4.2 The Support Vector Machine 34 4.3 The Kernel Trick 36 4.3.1 The Homogeneous Polynomial Kernel 37 4.3.2 The non-homogeneous Polynomial Kernel 38 4.3.3 The RBF Kernel 39 4.3.4 Classifying New Instances 39 iii
Trang 4
iv Contents 5 Spectral Analysis I: PCA, LDA, CCA 41 5.1 PCA: Statistical Perspective 42 5.1.1 Maximizing the Variance of Output Coordinates 43 5.1.2 Decorrelation: Diagonalization of the Covariance Matrix 46 5.2 PCA: Optimal Reconstruction 47 5.3 The Case n >> m 49 5.4 Kernel PCA 49 5.5 Fisher’s LDA: Basic Idea 50 5.6 Fisher’s LDA: General Derivation 52 5.7 Fisher’s LDA: 2-class 54 5.8 LDA versus SVM 54 5.9 Canonical Correlation Analysis 55 6 Spectral Analysis II: Clustering 58 6.1 K-means Algorithm for Clustering 59 6.1.1 Matrix Formulation of K-means 60 6.2 Min-Cut 62 6.3 Spectral Clustering: Ratio-Cuts and Normalized-Cuts 63 6.3.1 Ratio-Cuts 64 6.3.2 Normalized-Cuts 65 7 The Formal (PAC) Learning Model 69 7.1 The Formal Model 69 7.2 The Rectangle Learning Problem 73 7.3 Learnability of Finite Concept Classes 75 7.3.1 The Realizable Case 76 7.3.2 The Unrealizable Case 77 8 The VC Dimension 80 8.1 The VC Dimension 81 8.2 The Relation between VC dimension and PAC Learning 85 9 The Double-Sampling Theorem 89 9.1 A Polynomial Bound on the Sample Size m for PAC Learning 89 9.2 Optimality of SVM Revisited 95 10 Appendix 97 Bibliography 105
Trang 5
1 Bayesian Decision Theory During the next few lectures we will be looking at the inference from training data problem as a random process modeled by the joint probability distribu- tion over input (measurements) and output (say class labels) variables. In general, estimating the underlying distribution is a daunting and unwieldy task, but there are a number of constraints or ”tricks of the trade” so to speak that under certain conditions make this task manageable and fairly effective. To make things simple, we will assume a discrete world, i.e., that the values of our random variables take on a finite number of values. Consider for example two random variables X taking on k possible values x1, ..., xk and H taking on two values h1, h2. The values of X could stand for a Body Mass Index (BMI) measurement weight/height2 of a person and H stands for the two possibilities h1 standing for the ”person being over-weight” and h2 as the possibility ”person of normal weight”. Given a BMI measurement we would like to estimate the probability of the person being over-weight. The joint probability P(X, H) is a two dimensional array (2-way array) with 2k entries (cells). Each training example (xi, hj) falls into one of those cells, therefore P(X = xi, H = hj) = P(xi, hj) holds the ratio between the number of hits into cell (i, j) and the total number of training examples∑ (assuming the training data arrive i.i.d.). As a result ij P(xi, hj) = 1. The projections of the array onto its vertical and horizontal axes by sum- ming over columns or over rows is called∑ marginalization and produces P(hj) = i P(xi, hj) the sum over the j’th row is the probability P(H = hj), i.e., the probability of a person being over-weight (or not) before we see any∑ measurement — these are called priors. Likewise, P(xi) = j P(xi, hj) is the probability P(X = xi) which is the probability of receiving such a BMI measurement to begin with — this is often called evidence. Note 1
Trang 6
2 Bayesian Decision Theory h1 2 5 4 2 1 h2 0 0 3 3 2 x1 x2 x3 x4 x5 Fig. 1.1. Joint probability P(X, H) where X ranges over 5 discrete values and H over two values. Each entry contains the number of hits for the cell (xi, hj). The joint probability P(xi, hj) is the number of hits divided by the total number of hits (22). See text for more details. ∑ ∑ that, by definition, j P(hj) = i P(xi) = 1. In Fig. 1.1 we have that P(h1) = 14/22, P(h2) = 8/22 that is there is a higher prior probability of a person being over-weight than being of normal weight. Also P(x3) = 7/22 is the highest meaning that we encounter BMI = x3 with the highest prob- ability. The conditional probability P(hj | xi) = P(xi, hj)/P(xi) is the ratio be- tween the number of hits in cell (i, j) and the number of hits in the i’th column, i.e., the probability that the outcome is H = hj given the measure- ment X = xi. In Fig. 1.1 we have P(h2 | x3) = 3/7. Note that ∑ ∑ P(x , h ) 1 ∑ P(h | x ) = i j = P(x , h ) = P(x )/P(x ) = 1. j i P(x ) P(x ) i j i i j j i i j Likewise, the conditional probability P(xi | hj) = P(xi, hj)/P(hj) is the number of hits in cell (i, j) normalized by the number of hits in the j’th row and represents the probability of receiving BMI = xi given the class label H = hj (over-weight or not) of the person. In Fig. 1.1 we have P(x3 | h2) = 3/8 which is the probability of receiving BMI =∑ x3 given that the person is known to be of normal weight. Note that i P(xi | hj) = 1. The Bayes formula arises from: P(xi | hj)P(hj) = P(xi, hj) = P(hj | xi)P(xi), from which we get: P(xi | hj)P(hj) P(hj | xi) = . P(xi) The left hand side P(hj | xi) is called the posterior probability and P(xi | hj) is called the class conditional likelihood. The Bayes formula provides a way to estimate the posterior probability from the prior, evidence and class likelihood. It is useful in cases where it is natural to compute (or collect data of) the class likelihood, yet it is not quite simple to compute directly
Trang 7
Bayesian Decision Theory 3 the posterior. For example, given a measurement ”12” we would like to estimate the probability that the measurement came from tossing a pair of dice or from spinning a roulette table. If x = 12 is our measurement, and h1 stands for ”pair of dice” and h2 for ”roulette” then it is natural to compute the class conditional: P(”12” | ”pair of dice”) = 1/36 and P(”12” | ”roulette”) = 1/38. Computing the posterior directly is much more difficult. As another example, consider medical diagnosis. Once it is known that a patient suffers from some disease hj, it is natural to evaluate the probabilities P(xi | hj) of the emerging symptoms xi. As a result, in many inference problems it is natural to use the class conditionals as the basic building blocks and use the Bayes formula to invert those to obtain the posteriors. The Bayes rule can often lead to unintuitive results — the one in particu- lar is known as ”base rate fallacy” which shows how an nonuniform prior can influence the mapping from likelihoods to posteriors. On an intuitive basis, people tend to ignore priors and equate likelihoods to posteriors. The follow- ing example is typical: consider the ”Cancer test kit” problem† which has the following features: given that the subject has Cancer ”C”, the probability of the test kit producing a positive decision ”+” is P(+ | C) = 0.98 (which means that P(− | C) = 0.02) and the probability of the kit producing a neg- ative decision ”-” given that the subject is healthy ”H” is P(− | H) = 0.97 (which means also that P(+ | H) = 0.03). The prior probability of Cancer in the population is P(C) = 0.01. These numbers appear at first glance as quite reasonable, i.e, there is a probability of 98% that the test kit will produce the correct indication given that the subject has Cancer. What we are actually interested in is the probability that the subject has Cancer given that the test kit generated a positive decision, i.e., P(C | +). Using Bayes rule: P(+ | C)P(C) P(+ | C)P(C) P(C | +) = = = 0.266 P(+) P(+ | C)P(C) + P(+ | H)P(H) which means that there is a 26.6% chance that the subject has Cancer given that the test kit produced a positive response — by all means a very poor performance. If we draw the posteriors P(h1 |x) and P(h2 | x) using the probability distribution array in Fig. 1.1 we will see that P(h1 |x) > P(h2 | x) for all values of X smaller than a value which is in between x3 and x4. Therefore the decision which will minimize the probability of misclassification would † This example is adopted from Yishai Mansour’s class notes on Machine Learning.
Trang 8
4 Bayesian Decision Theory be to choose the class with the maximal posterior: h∗ = argmax P(h | x), j j which is known as the Maximal A Posteriori (MAP) decision principle. Since P(x) is simply a normalization factor, the MAP principle is equivalent to: h∗ = argmax P(x | h )P(h ). j j j In the case where information about the prior P(h) is not known or it is known that the prior is uniform, the we obtain the Maximum Likelihood (ML) principle: h∗ = argmax P(x | h ). j j The MAP principle is a particular case of a more general principle, known as ”proper Bayes”, where a loss is incorporated into the decision process. Let l(hi, hj) be the loss incurred by deciding on class hi when in fact hj is the correct class. For example, the ”0/1” loss function is: { } 1 i 6= j l(hi, hj) = 0 i = j The least-squares loss function is: l(h , h ) = ‖h −h ‖2 typically used when i j i j the outcomes are vectors in some high dimensional space rather than class labels. We define the expected risk: ∑ R(hi | x) = l(hi, hj)P(hj | x). j The proper Bayes decision policy is to minimize the expected risk: h∗ = argmin R(h | x). j j The MAP policy arises in the case l(hi, hj) is the 0/1 loss function: ∑ R(hi | x) = P(hj | x) = 1 − P(hi | x), j6=i Thus, argmin R(hj | x) = argmax P(hj | x). j j
Trang 9
1.1 Independence Constraints 5 1.1 Independence Constraints At this point we may pause and ask what have we obtained? well, not much. Clearly, the inference problem is captured by the joint probability distribution and we do not need all these formulas to see this. How do we obtain the necessary data to fill in the probability distribution array to begin with? Clearly without additional simplifying constraints the task is not practical as the size of these kind of arrays are exponential in the number of variables. There are three families of simplifying constraints used in the literature: • statistical independence constraints, • parametric form of the class likelihood P(xi | hj) where the inference becomes a density estimation problem, • structural assumptions — latent (hidden) variables, graphical models. Today we will focus on the first of these simplifying constraints — statistical independence properties. Consider two random variables X and Y . The variables are statistically independent X⊥Y if P(X | Y ) = P(X) meaning that information about the value of Y does not add anything about X. The independence condition is equivalent to the constraint: P(X, Y ) = P(X)P(Y ). This can be easily proven: if X⊥Y then P(X, Y ) = P(X | Y )P(Y ) = P(X)P(Y ). On the other hand, if P(X, Y ) = P(X)P(Y ) then P(X, Y ) P(X)P(Y ) P(X | Y ) = = = P(X). P(Y ) P(Y ) Let the values of X range over x1, ..., xk and the values of Y range over y1, ..., yl. The associated k × l 2-way array, P(X = xi, Y = yj) is repre- sented by the outer product P(xi, yj) = P(xi)P(yj) of two vectors P(X) = (P(x1), ..., P(xk)) and P(Y ) = (P(y1), ..., P(yl)). In other words, the 2-way array viewed as a matrix is of rank 1 and is determined by k + l (minus 2 because the sum of each vector is 1) parameters rather than kl (minus 1) parameters. Likewise, if X1⊥X2⊥....⊥Xn are n statistically independent random vari- ables where Xi ranges over ki discrete and distinct values, then the n-way array P(X1, ..., Xn) = P(X1) · ... · P(Xn) is an outer-product of n vectors and is therefore determined by k1 + ... + kn (minus n) parameters instead of k1k2...kn (minus 1) parameters†. Viewed as a tensor, the joint probabil- † I am a bit over simplifying things because we are ignoring here the fact that the entries of the array should be non-negative. This means that there are additional non-linear constraints which effectively reduce the number of parameters — but nevertheless it stays exponential.
Trang 10
6 Bayesian Decision Theory ity is a rank 1 tensor. The main point is that the statistical independence assumption reduced the representation of the multivariate joint distribution from exponential to linear size. Since our variables are typically divided to measurement variables and an output/class variable H (or in general H1, ..., Hl), it is useful to intro- duce another, weaker form, of independence known as conditional indepen- dence. Variables X, Y are conditionally independent given H, denoted by X⊥Y | H, iff P(X | Y, H) = P(X | H) meaning that given H, the value of Y does not add any information about X. This is equivalent to the condition P(X, Y | H) = P(X | H)P(Y | H). The proof goes as follows: • If P(X | Y, H) = P(X | H), then P(X, Y, H) P(X | Y, H)P(Y, H) P(X, Y | H) = = P(H) P(H) P(X | Y, H)P(Y | H)P(H) = = P(X | H)P(Y | H) P(H) • If P(X, Y | H) = P(X | H)P(Y | H), then P(X, Y, H) P(X, Y | H) P(X | Y, H) = = = P(X | H). P(Y, H) P(Y | H) Consider as an example, Joe and Mo live on opposite sides of the city. Joe goes to work by train and Mo by car. Let X be the event ”Joe is late to work” and Y be the event ”Mo is late for work”. Clearly X and Y are not independent because there could be other factors. For example, a train strike will cause Joe to be late, but because of the strike there would be extra traffic (people using their car instead of the train) thus causing Mo to be pate as well. Therefore, a third variable H standing for the event ”train strike” would decouple X and Y . From a computational standpoint, the conditional independence assump- tion has a similar effect to the unconditional independence. Let X range over k distinct value, Y range over r distinct values and H range over s distinct values. Then P(X, Y, H) is a 3-way array of size k × r × s. Given that X⊥Y | H means that P(X, Y | H = hi), a 2-way ”slice” of the 3-way array along the H axis is represented by the outer-product of two vectors P(X | H = hi)P(Y | H = hi). As a result the 3-way array is represented by s(k+r−2) parameters instead of skr−1. Likewise, if X1⊥....⊥Xn | H then the n-way array P(X1, ..., Xn | H = hi) (which is a slice along the H axis of the (n + 1)-array P(X1, ..., Xn, H)) is represented by an outer-product of n vectors, i.e., by k1 + .. + kn − n parameters.
Trang 11
1.1 Independence Constraints 7 1.1.1 Example: Coin Toss We will use the ML principle to estimate the bias of a coin. Let X be a random variable taking the value {0,1} and H would be our hypothesis taking a real value in [0,1] standing for the coin’s bias. If the coin’s bias is q then P(X = 0 | H = q) = q and P(X = 1 | H = q) = 1−q. We receive m i.i.d. examples x1, ..., xm where xi ∈ {0,1}. We wish to determine the value of q. Given that x1⊥...⊥xm | H, the ML problem we must solve is: ∏m ∑ q∗ = argmaxP(x , ..., x | H = q) = P(x | q) = argmax log P(x | q). 1 m i i q i=1 q i Let 0 ≤ λ ≤ m stand for the number of ’0’ instances, i.e., λ = |{xi = 0 | i = 1, ..., m}|. Therefore our ML problem becomes: q∗ = argmax {λlog q + (n − λ) log(1 − q)} q Taking the partial derivative with respect to q and setting it to zero: ∂ λ n − λ [λlog q + (n − λ) log(1 − q)] = − = 0, ∂q q∗ 1 − q∗ produces the result: ∗ λ q = . n 1.1.2 Example: Gaussian Density Estimation So far we considered constraints induced by conditional independent state- ments among the random variables as a means to reduce the space and time complexity of the multivariate distribution array. Another approach would be to assume some form of parametric form governing the entries of the array — the most popular assumption is Gaussian distribution P(X1, ..., Xn) ∼ N(μ, E) with mean vector μ and covariance matrix E. The parameters of the density function are denoted by θ = (μ, E) and for every vector x ∈ Rn we have: 1 −1 (x−μ)>E−1(x−μ) P(x | θ) = exp 2 . (2π)n/2|E|1/2 Assume we are given an i.i.d sample of k points S = {x , ...,x }, x ∈ Rn, 1 k i and we would like to find the Bayes optimal θ: θ∗ = argmax P(S | θ), θ
Trang 12
8 Bayesian Decision Theory by maximizing the likelihood (here we are assuming that the the priors P(θ) are equal, thus the maximum likelihood and the MAP would produce the same result). Because the sample was drawn i.i.d. we can assume that: ∏k P(S | θ) = P(xi | θ). i=1 ∑ Let L(θ) = log P(S | θ) = i log P(xi | θ) and since Log is monotonously increasing we have that θ∗ = argmaxL(θ). The parameter estimation would θ be recovered by taking derivatives with respect to θ, i.e., ∇θL = 0. We have: 1 ∑k n ∑ 1 L(θ) = − log |E| − log(2π) − (x − μ)>E−1(x − μ). (1.1) 2 2 2 i i i=1 i We will start with a simple scenario where E = σ2I, i.e., all the covariances are zero and all the variances are equal to σ2. Thus, E−1 = σ−2I and |E| = σ2n. After substitution (and removal of items which do not depend on θ) we have: 1 ∑ ‖x − μ‖2 L(θ) = −nk log σ − i . 2 σ2 i The partial derivative with respect to μ: ∂L ∑ = σ−2 (μ − x ) = 0 ∂μ i i from which we obtain: 1 ∑k μ = xi. k i=1 The partial derivative with respect to σ is: ∂L nk ∑ = − σ−3 ‖x − μ‖2 = 0, ∂σ σ i i from which we obtain: 1 ∑k σ2 = ‖x − μ‖2. kn i i=1 Note that the reason for dividing by n is due to the fact that σ2 = ... = 1 σ2 = σ2, so that: n 1 ∑k ∑n ‖x − μ‖2 = σ2 = nσ2. k i j i=1 j=1
Trang 13
1.2 Incremental Bayes Classifier 9 In the general case, E is a full rank symmetric matrix, then the derivative of eqn. (1.1) with respect to μ is: ∂L ∑ = E−1 (μ − x ) = 0, ∂μ i i ∑ and since E−1 is full rank we obtain μ = (1/k) x . For the derivative i i with respect to E we note two auxiliary items: ∂|E| −1 ∂ −1 −1 −1 > = |E|E , trace(AE ) = −(E AE ) . ∂E ∂E Using the fact that x>y = trace(xy>) we can transform z>E−1z to trace(zz>E−1) for any vector z. Given that E−1 is symmetric, then: ∂ > −1 −1 > −1 trace(zz E ) = −E zz E . ∂E Substituting z = x − μ we obtain: ( ) ∂L ∑ = −kE−1 + E−1 (x − μ)(x − μ)> E−1 = 0, ∂E i i i from which we obtain: 1 ∑k E = (x − μ)(x − μ)>. k i i i=1 1.2 Incremental Bayes Classifier Consider another application of conditional dependence which is the Bayes incremental rule. Suppose we have processed n examples X(n) = {X , ..., X } 1 n and computed somehow P(H | X(n)). We are given a new measurement X and wish to compute (update) the posterior P(H | X(n), X). We will use the chain rule†: P(X, Y, Z) P(Z | X, Y )P(X | Y )P(Y ) P(Z | X, Y )P(X | Y ) P(X | Y, Z) = ) = = P(Y, Z P(Z | Y )P(Y ) P(Z | Y ) to obtain: P(X | X(n), H)P(H | X(n)) P(H | X(n), X) = P(X | X(n)) from conditional independence, P(X | X(n), H) = P(X | H). The term P(X | X(n)) can expanded as follows: † this is based on the rule P(X1, ..., Xn) = P(X1 | X2, ..., Xn)P(X2 | X3, ..., Xn) · · · P(Xn−1 | Xn)P(Xn)
Trang 14
10 Bayesian Decision Theory ∑ P(X, X(n) | H = h )P(H = h ) P(X | X(n)) = i i P(X(n)) i ∑ P(X | H = h )P(X(n) | H = h )P(H = h ) = i i i P(X(n)) ∑i = P(X | H = h )P(H = h | X(n)) i i i After substitution we obtain: P(X | H = h )P(H = h | X(n)) P(H = h | X(n), X) = ∑ i i . i P(X | H = h )P(H = h | X(n)) j j j The old posterior P(H | X(n)) is now the prior for the updated formula. Consider the following example†: We have a coin which could be either fair or biased towards Head at a probability of 0.6. Let H = h1 be the event that the coin is fair, and H = h2 that the coin is biased. We start with prior probabilities P(h1) = 0.75 and P(h2) = 0.25 (we have a higher initial belief that the coin is fair). Suppose our first coin toss is a Head, i.e., X1 = ”0”. Then, P(x1 | h1)P(h1) 0.5 ∗ 0.75 P(h1 | x1) = = = 0.714 P(x1) 0.5 ∗ 0.75 + 0.6 ∗ 0.25 and P(h2 | x1) = 0.286. Our posterior belief that the coin is fair has gone down after a Head toss. Assume we have another measurement X2 = ”0”, then: P(x2 | h1)P(h1 | x1) 0.5 ∗ 0.714 P(h1 | x1, x2) = = = 0.675, normalization 0.5 ∗ 0.714 + 0.6 ∗ 0.286 and P(h2 | x1, x2) = 0.325, thus our belief that the coin is fair continues to go down after Head tosses. 1.3 Bayes Classifier for 2-class Normal Distributions For the last topic in this lecture consider the 2-class inference problem. We will encountered this problem in this course in the context of SVM and LDA. In the Bayes framework, if H = {h1, h2} denotes the ”class member” variable with two possible outcomes, then the MAP decision policy calls for † adopted from Ron Rivest’s 1994 class notes.
Trang 15
1.3 Bayes Classifier for 2-class Normal Distributions 11 making the decision based on data x: h∗ = argmax {P(h | x), P(h | x)}, 1 2 h1,h2 or in other words the class h1 would be chosen if P(h1 | x) > P(h2 | x). The decision surface (as a function of x) is therefore described by: P(h1 | x) − P(h2 | x) = 0. The questions we ask here is what would the Bayes optimal decision sur- face be like if we assume that the two classes are normally distributed with different means and the same covariance matrix? What we will see is that under the condition of equal priors P(h1) = P(h2) the decision surface is a hyperplane — and not only that, it is the same hyperplane produced by LDA. Claim 1 If P(h1) = P(h2) and P(x | h1) ∼ N(μ1, E) and P(x | h1) ∼ N(μ , E), the the Bayes optimal decision surface is a hyperplane w>(x − 2 μ) = 0 where μ = (μ + μ )/2 and w = E−1(μ − μ ). In other words, the 1 2 1 2 decision surface is described by: > −1 1 −1 x E (μ1 − μ2) − (μ1 + μ2)E (μ1 − μ2) = 0. (1.2) 2 Proof: The decision surface is described by P(h1 | x) − P(h2 | x) = 0 which is equivalent to the statement that the ratio of the posteriors is 1, or equivalently that the log of the ratio is zero, and using Bayes formula we obtain: P(x | h1)P(h1) P(x | h1) 0 = log = log . P(x | h2)P(h2) P(x | h2) In other words, the decision surface is described by 1 > −1 1 > −1 log P(x | h1)−log P(x | h2) = − (x−μ1) E (x−μ1)+ (x−μ2) E (x−μ2) = 0. 2 2 After expanding the two terms we obtain eqn. (1.2).
Trang 16
2 Maximum Likelihood/ Maximum Entropy Duality In the previous lecture we defined the principle of Maximum Likelihood (ML): suppose we have random variables X1, ..., Xn form a random sample from a discrete distribution whose joint probability distribution is P(x | φ) where x = (x1, ..., xn) is a vector in the sample and φ is a parameter from some parameter space (which could be a discrete set of values — say class membership). When P(x | φ) is considered as a function of φ it is called the likelihood function. The ML principle is to select the value of φ that maxi- mizes the likelihood function over the observations (training set) x1, ...,xm. If the observations are sampled i.i.d. (a common, not always valid, assump- tion), then the ML principle is to maximize: ∏m ∏m ∑m φ∗ = argmax P(x | φ) = argmax log P(x | φ) = argmax log P(x | φ) i i i φ i=1 i=1 i=1 which due to the product nature of the problem it becomes more convenient to maximize the log likelihood. We will take a closer look today at the ML principle by introducing a key element known as the relative entropy measure between distributions. 2.1 ML and Empirical Distribution The ML principle states that the empirical distribution of an i.i.d. sequence of examples is the closest possible (in terms of relative entropy which would be defined later) to the true distribution. To make this statement clear let X be a set of symbols {a1, ..., an} and let P(a | θ) be the probability (belonging to a parametric family with parameter θ) of drawing a symbol a ∈ X. Let x1, ..., xm be a sequence of symbols drawn i.i.d. according to P. The occurrence frequency f(a) measures the number of draws of the symbol 12
Trang 17
2.1 ML and Empirical Distribution 13 a: f(a) = |{i : xi = a}|, and let the empirical distribution be defined by ˆ 1 1 P(a) = ∑ f(a) = f(a) = (1/m)f(a). α∈X f(α) ‖f‖1 ∏ The joint probability P(x1, ..., xm | φ) is equal to the product i P(xi | φ) which according to the definitions above is equal to: ∏m ∏ P(x , ..., x | φ) = p(x | θ) = P(a | φ)f(a). 1 m i i=1 a∈X The ML principle is therefore equivalent to the optimization problem: ∏ max P(a | φ)f(a) (2.1) P∈Q a∈X ∑ where Q = {q ∈ Rn : q ≥ 0, q = 1} denote the set of n-dimensional i i probability vectors (”probability simplex”). Let pi stand for P(ai | φ) and fi ∏stand for∑f(ai). Since argmaxxz(x) = argmaxx lnz(x) and given that ln pfi = f lnp the solution to this problem can be found by setting i i i i i the partial derivative of the Lagrangian to zero: ∑n ∑ ∑ L(p, λ, μ) = fi lnpi − λ( pi − 1) − μipi, i=1 i i ∑where λ is the Lagrange multiplier associated with the equality constraint i pi − 1 = 0 and μi ≥ 0 are the Lagrange multipliers associated with the inequality constraints pi ≥ 0. We also have the complementary slackness condition that sets μi = 0 if pi > 0. After setting the partial derivative with respect to pi to zero we get: 1 pi = fi. λ + μi Assume for now that fi > 0 for i = 1, ..., n. Then from complementary slackness we must have μi = 0 (because pi > 0). We are left therefore∑ with the result∑ pi = (1/λ)fi. Following the constraint i p1 = 1 we obtain λ = f . As a result we obtain: P(a | φ) = Pˆ(a). In case f = 0 we could i i i use the convention 0 ln 0 = 0 and from continuity arrive to pi = 0. We have arrived to the following theorem: Theorem 1 The empirical distribution estimate Pˆ is the unique Maximum
Trang 18
14 Maximum Likelihood/ Maximum Entropy Duality Likelihood estimate of the probability model Q on the occurrence frequency f(). This seems like an obvious result but it actually runs deep because the result holds for a very particular (and non-intuitive at first glance) distance mea- sure between non-negative vectors. Let dist(f,p) be some distance measure between the two vectors. The result above states that: ∑ Pˆ = argmin dist(f,p) s.t. p ≥ 0, p = 1, (2.2) p i i for some (family?) of distance measures dist(). It turns out that there is only one† such distance measure, known as the relative-entropy, which satisfies the ML result stated above. 2.2 Relative Entropy The relative-entropy (RE) measure D(x||y) between two non-negative vec- tors x,y ∈ Rn is defined as: ∑n x ∑ ∑ D(x||y) = x ln i − x + y . i y i i i=1 i i i In the definition we use the convention that 0 ln 0 = 0 and based on con- 0 tinuity that 0 ln 0 = 0 and xln x = ∞. When x,y are also probability y 0 ∑ x vectors, i.e., belong to Q, then D(x||y) = i xi ln i is also known as the yi Kullback-Leibler divergence. The RE measure is not a distance metric as it is not symmetric, D(x||y) 6= D(y||x), and does not satisfy the triangle inequality. Nevertheless, it has several interesting properties which make it a fundamental measure in statistical inference. The relative entropy is always non-negative and is zero if and only if x = y. This comes about from the log-sum inequality: ∑ ∑ ∑ xi i xi xi ln ≥ ( xi) ln ∑ yi i yi i i Thus, ∑ ∑ ∑ ∑ i xi x¯ D(x||y) ≥ ( xi) ln ∑ − xi + yi = ¯xln − x¯ + ¯y i yi y¯ i i i † not exactly — the picture is a bit more complex.P Csiszar’s 1972 measures: dist(p,f) = f φ(p /f ) will satisfy eqn. 2.2 provided that φ′−1 is an exponential. However, dist(f,p) i i i i (parameters positions are switched) will not do it, whereas the relative entropy will satisfy eqn. 2.2 regardless of the order of the parameters p,f.
Trang 19
2.3 Maximum Entropy and Duality ML/MaxEnt 15 But aln(a/b) ≥ a − b for a, b ≥ 0 iff ln(a/b) ≥ 1 − (b/a) which follows from the inequality ln(x + 1) > x/(x + 1) (which holds for x > −1 and x 6= 0). We can state the following theorem: Theorem 2 Let f ≥ 0 be the occurrence frequency on a training sample. Pˆ ∈ Q is a ML estimate iff ∑ Pˆ = argmin D(f||p) s.t. p ≥ 0, p = 1. p i i Proof: ∑ ∑ ∑ D(f||p) = − fi lnpi + fi lnfi − fi + 1, i i i and ∑ ∏ argmin D(f||p) = argmax f lnp = argmax ln pfi. p p i i p i i i There are two (related) interesting points to make here. First, from the proof of Thm. 1 we observe that the non-negativity constraint p ≥ 0 need not be enforced - as long as∑f ≥ 0 (which holds by definition) the closest p to f under the constraint i pi = 1 must come out non-negative. Second, the fact that the closest point p to f comes out as a scaling of f (which is by definition the empirical distribution Pˆ) arises because of the relative-entropy measure. For example, if we had used a least-squares distance measure ‖f − p‖2 the result would not be a scaling of f. In other words, we are looking for a projection of the vector f onto the probability simplex, i.e., the intersection of the hyperplane x>1 = 1 and the non-negative orthant x ≥ 0. Under relative-entropy the projection is simply a scaling of f (and this is why we do not need to enforce non-negativity). Under least-sqaures, a projection onto the hyper-plane x>1 = 1 could take us out of the non- negative orthant (see Fig. 2.1 for illustration). So, relative-entropy is special in that regard — it not only provides the ML estimate, but also simplifies the optimization process† (something which would be more noticeable when we handle a latent class model next lecture). 2.3 Maximum Entropy and Duality ML/MaxEnt The relative-entropy measure is not symmetric thus we expect different out- comes of the optimization minx D(x||y) compared to miny D(x||y). The lat- † The fact that non-negativity ”comes for free” does not apply for all class (distribution) models. This point would be refined in the next lecture.
Trang 20
16 Maximum Likelihood/ Maximum Entropy Duality f p 2 p^ ∑ Fig. 2.1. Projection of a non-neagtaive vector f onto the hyperplane xi −1 = 0. i Under relative-entropy the projection Pˆ is a scaling of f (and thus lives in the probability simplex). Under least-squares the projection p2 lives outside of the probability simplex, i.e., could have negative coordinates. ter of the two, i.e., minP∈Q D(P0||P), where P0 is some empirical evidence and Q is some model, provides the ML estimation. For example, in the next lecture we will consider Q the set of low-rank joint distributions (called latent class model) and see how the ML (via relative-entropy minimization) solution can be found.∑ Let H(p) = − i pi lnpi denote the entropy function. With regard to minx D(x||y) we can state the following observation: Claim 2 1 argmin D(p|| 1) = argmax H(p). p∈Q n p∈Q Proof: 1 ∑ ∑ D(p|| 1) = pi lnpi + ( pi) ln(n) = ln(n) − H(p), n i i ∑ which follows from the condition i pi = 1. In other words, the closest distribution to uniform is achieved by maxi- mizing the entropy. To make this interesting we need to add constraints.∑ Consider a linear constraint on p such as i αipi = β. To be concrete, con-
Hiển thị 20 trang đầu. Tải tài liệu để xem đầy đủ.
Bình luận (0)
Chưa có bình luận nào. Hãy là người đầu tiên!