Metrics on Spaces of Probabilites

Lp spaces, metrics on spaces of probabilites, and connections to estimation 2006 1 Lp spaces and Hilbert spaces We first f ormally d efine Lp sp aces. Co nsider a me asure sp ace (X , A, µ) , wh ere µ is a (σ-finite) measure. Let F be the set of all real–valued measurable functions defined on X . T he s pace Lp (µ) comprises that subset of functions of F that have finite p’th moments (here p ≥ 1 ). In other words: Z Lp (µ) = {f ∈ F : | f (x) |p d µ(x) < ∞} . When the measure µ is a probability P , we obtain the class of all random variables on the probability space, (X , A, P ) that have finite p’th moments. This is a normed linear space over R with the norm (length) of the vector f (this is called the Lp norm) being given by µZ kf kp = ¶1/p | f (x) | d µ(x) . p The above norm induces a metric d where d(f, g) = kf − gkp . Note that d(f, g) = 0 if and only if f = g a.e. µ, in which case we identify f with g. The Lp norm, like all worthy norms, satisfies the triangle inequality: kf + gkp ≤ kf kp + kgkp ; this is precisely Minkowski’s inequality. For random variables X, Y defined on the same probability space and having finite p’th moments, Minkowski’s inequality states: E(| X + Y |p )1/p ≤ E(| X |p )1/p + E(| Y |p )1/p . Minkowski’s inequality is a consequence of Hölder’s inequality which states that for measurable real-valued functions f, g defined on X , we have: µZ Z | f (x) g(x) d µ(x) |≤ ¶1/p µZ ¶1/q q | f (x) | dµ(x) | g(x) | dµ(x) . p 1 The space Lp (µ) is a Banach space for p ≥ 1 – this is a normed linear space that is complete – i.e. in which every Cauchy sequence has a limit. The notion of continuity for real valued functions defined on Lp (µ) is a natural extension of the usual one for Euclidean spaces. A sequence of functions gn converges to a function g in Lp (µ) if kgn − gkp → 0. A real-valued function ψ defined on Lp (µ) is said to be continuous if ψ(gn ) converges to ψ(g) as a sequence of real numbers whenever gn converges to g in Lp (µ). Let’s concretize to a specific example. Let X be the space of positive integers N , A be the power set of N and µ be counting measure that assigns the cardinality of a subset of N as its measure. The space Lp (µ) is then the space of all real valued sequences {x1 , x2 , . . .} that are P∞ p p’th power summable – i.e. i=1 | xi | < ∞. Clearly all sequences that have only finitely many non-zero entries satisfy this condition. This space is referred to as the lp space. The lp spaces are infinite-dimensional spaces – i.e. these spaces do not have a finite basis. Another crucial inequality, which in particular, implies that the function f 7→ kf kp is a continuous function from Lp (µ) to the reals is that |kh1 kp − kh2 kp | ≤ kh1 − h2 kp . This is once again a consequence of the triangle inequality. For p = 2, the space Lp (µ) has more geometric structure: it becomes a Hilbert space. We introduce Hilbert spaces in some generality. A Hilbert space H is a normed linear (vector) space (over the field R in the current discussion, though the general treatment requires the field to be the field of complex numbers) that is complete (with respect to the metric topology induced by the norm) and such that the norm arises from an inner product. The inner product hx, yi is a (bilinear) map from H × H to R satisfying the following properties: (a) hα x + β y, zi = αhx, zi + βhy, zi, (b) hx, yi = hy, xi, and (c) hx, xi = kxk2 . Note that properties (a) and (b) jointly imply linearity in the second co-ordinate as well; i.e. hz, αx + βyi = α hz, xi + βhz, yi. Hence bilinearity follows. It is worthwhile here to recall the fundamental properties of a norm (on any normed linear space). These are (a) kxk = 0 if and only if x = 0, (b) kα xk =| α | kxk, for any scalar α, and (c) kx + yk ≤ kxk + kyk, the triangle inequality. The Hilbert spaces that we will be most concerned will be L2 spaces, but this is not the simplest example of this species. The simplest Hilbert spaces P over R are the Euclidean spaces Rk for any integer k. In Rk , the inner product is hx, yi = ki=1 xi yi = xT y(if we write x and y as column vectors). Check that this inner product does induce the usual Euclidean norm. Completeness of Rk with respect to the usual Euclidean metric follows as a direct consequence of the fact that the real line is complete. A fundamental relation in Hilbert spaces is the Cauchy-Schwarz inequality which states 2 that: | hx, yi |≤ kxk kyk . Simple as this relation is, its ramifications are profound. How do we prove this? Assume without loss of generality that neither x nor y is 0 (otherwise, the inequality is trivial). Observe that kx − α yk2 is necessarily non-negative, for every real α. Expanding this in terms of the inner product, we find: kxk2 − 2 α hx, yi + α2 kyk2 ≥ 0 . This function is strictly convex in α and is uniquely minimized at α0 = hx, yi/kyk2 , as can be checked by straightforward differentiation. Plugging in α0 for α must preserve the inequality above; doing so, and simplifying leads to the fact that hx, yi2 ≤ kxk2 kyk2 . This implies the inequality. The line of proof above admits a nice geometric intepretation that will prove useful in thinking about inner products. Draw vectors x, y on the (R2 ) plane (emanating from the origin), and for simplicity let them lie in the first quadrant (so that the angle θ between the two of them is an acute angle). For each α you can draw the vector x − α y; it is then easy to see that the the length of this vector (kx − α yk, with the norm here denoting the usual Euclidean norm) is minimized for that α0 for which the vector x − α0 y is perpendicular to the vector α0 y (and α0 6= 0, unless x = y). Now, by the proof above, α0 should be (x1 x2 + y1 y2 )/(y12 + y22 ). Does this tally with what analytical geometry tells us? We can use the Pythagoras’ theorem to verify. We have: α02 (y12 + y22 ) + (x1 − α0 y1 )2 + (x2 − α0 y2 )2 = x21 + x22 , which on simplification gives: −2 α0 (x1 y1 + x2 y2 ) + 2 α02 (y12 + y22 ) = 0 , and this yields: α0 = x1 y1 + x2 y2 hx, yi = . hy, yi2 y12 + y22 Now, check (from definitions) that the cosine of the angle between x and y is: cos θ = hx, yi α0 kyk = . kxk kxk kyk But since cos θ in absolute magnitude is less than or equal to 1, the Cauchy-Schwarz inequality must hold. The same arguments would work in 3 dimensions, but in any case, the following is clear: Geometrically, the Cauchy-Schwarz inequality is a restatement of the fact that the cosine of the angle between two vectors in a Hilbert space is no greater than 1 in absolute value. Of course, it is 3 difficult to visualize angles in a general Hilbert space. But taking the cue from 2 or 3 dimensions, one can define the angle between two vectors in a Hilbert space to be: α = cos−1 hx, yi . kxk kyk Orthogonality of two vectors then corresponds to α being either π/2 or 3 π/2 whence the numerator in the argument to cos−1 function should vanish: in other words, vectors x and y in a Hilbert space will be said to be orthogonal to each other (written as x ⊥ y), if hx, yi = 0. As a consequence of the Cauchy-Schwarz inequality, it follows that the inner product is a continuous function from H × H → R; in other words, if (xn , yn ) → (x, y) in H × H then hxn , yn i → hx, yi. We develop the concept of orthogonality in some detail as it plays an important role in probabilistic and statistical computations. A vector x is said to be orthogonal to a non-empty subset S of H if x ⊥ y for every vector y ∈ S. The set of all vectors orthogonal to S is denoted by S ⊥ . Check that the following hold: (i) {0}⊥ = H, H⊥ = 0, (ii) S ∩ S ⊥ ⊂ {0}, (iii) S1 ⊂ S2 ⇒ S2⊥ ⊂ S1⊥ and (iv) S ⊥ is a closed linear subspace of H. By a suspace S̃ of H, we mean a subset that is closed under the formation of finite linear combinatons of elements in S̃ (and hence in particular, contains the 0 vector). A subspace of a Hilbert space is not necessarily a Hilbert space, but a closed subspace of a Hilbert space necessarily is. To show that S ⊥ is a closed subspace, it suffices to show that if x and y are in S ⊥ so is α x + β y. But this follows trivially from the definition of S ⊥ . We only need to verify that S ⊥ is closed. So let xn be a sequence of elements in S ⊥ converging to x ∈ H. Then by the continuity of the inner product, we have hxn , yi → hx, yi for any y ∈ H. Now for any y ∈ S, hxn , yi is 0 for all n, showing that hx, yi must also be 0. But ⊥ this shows that x ∈ S ⊥ . Check that S ⊂ S ⊥ ⊥ ≡ S ⊥ . If S is a non-empty subset of H, then S ⊥ ⊥ is the closure of the set of all (finite) linear combinations of vectors in S. Thus S ⊥ ⊥ is the smallest closed linear subspace of H that contains S. In particular, if S is a subspace, then S ⊥ ⊥ is the closure of S (which is also a subspace), and in addition, if S is closed S ⊥ ⊥ = S. Proposition: Let M be a closed linear subspace of S. Then any h ∈ H can be written uniquely as h1 + h2 where h1 ∈ M and h2 ∈ M ⊥ . The map h 7→ h1 is called the orthogonal projection into the subspace M (denoted by πM ) and is a (continuous) linear operator. The map h 7→ h2 is the orthogonal projection onto M ⊥ (written as πM ⊥ ). We will not prove this proposition. For a proof, see for example pages 247–251 of Simmons (Introduction to Topology and Modern Analysis), or a standard textbook in Functional Analysis. Note that πM h = argmin w∈M kh − wk2 . That this is the case follows on noting that: kh − wk2 = kh − πM hk2 + kπM h − wk2 + 2 hh − πM h, πM h − wi ; 4 now the third term vanishes, since h − πM h ∈ M ⊥ and πM h − w ∈ M . The result follows. We now return to L2 (µ) spaces. We have already seen that this is a normed linear (Banach) space. Define an inner product on L2 (µ) by: Z hf, gi = f (x) g(x) d µ(x) . It is not difficult to see that this is well defined, satisfies the criteria for an inner product and induces the L2 (µ) norm. Hence L2 (µ) is a Hilbert space with respect to this inner product. For the moment, specialize to the case where µ is a probability measure P and consider the space L2 (P ) (with underlying sample space (X , A). Let Y and X be random variables in L2 (P ). Regression: Consider the regression problem of regressing Y on X. This is the problem of finding that function φ of X that minimizes E(Y − φ(X))2 . This can be posed in the following manner: Let σ(X) be the sub sigma-field of A generated by X. Let S̃ denote the set of all random variables in L2 (P ) that are measurable with respect to σ(X). This is a closed linear subspace of L2 (P ). The problem now is one of determining that random variable W in the subspace S̃ that minimizes kY − W k2 where k k2 denotes the L2 (P ) norm. By the general theory of Hilbert spaces, this will be the orthogonal projection of Y onto the subspace S̃. Now note that Y = E(Y | X) + (Y − E(Y | X)), where E(Y | X) ≡ E(Y | σ(X)). Clearly E(Y | X) lies in S̃. We will show that Y − E(Y | X) lies in S̃ ⊥ , whence it will follows that E(Y | X) is the orthogonal projection of Y onto S̃ and hence minimizes kY − W k2 over all W in S̃. Thus, for any W ∈ S̃ we need to show that hW, Y − E(Y | X)i = 0. Now, hW, Y − E(Y | X)i = E [W (Y − E(Y | X))] = E [E [W (Y − E(Y | X)) | σ(X)] ] = E [W [E(Y | X) − E(Y | X)] ] = 0. Regression problems in statistics can be viewed as those of computing orthogonal projections on appropriate subspaces of L2 spaces. In linear regression one projects the response variable Y onto the finite dimensional linear subspace of linear combinations of the covariate random variables. This is smaller than the subspace of all random variables that are measurable with respect to the sigma-field generated by the covariate variables. The mean squared error in regression: E(Y − E(Y | X))2 can be viewed as the squared length of the projection of Y onto S̃ ⊥ , the orthogonal complement of S̃. Exercise 1: Let S1 and S2 be two closed linear subspaces of the Hilbert space H and suppose that S1 is strictly contained in S2 . For any vector h consider πS1 h and πS2 h. How does the length (norm) of πS1 h compare to that of πS2 h? What is the relation between πS1 h and πS1 πS2 h? 5 Exercise 2: Consider a probability space (X , A, P ). Let G1 and G2 be sub-sigma fields of A, with G1 ⊂ G2 . Let Y be a random variable defined on (X , A). From the theory of conditional expectations we know that E[[Y | G2 ] | G1 ] = E [Y | G1 ]. Can you derive this from your considerations in Exercise 1? Also, provide a geometric interpretation to the inequality: E [Y − E[Y | G2 ]]2 ≤ E [Y − E[Y | G1 ]]2 . 2 Metrics on spaces of probability measures Consider the space of all probability measures on a probability space (X , A). We discuss how this space can be metrized. Metrization of probability measures (i.e. defining a notion of distance) is important, since in statistics one is often concerned about convergence of estimates based on finite samples to the true parameter (which is often a probability measure) and fundamental to a definition of convergence is the notion of a distance. Two widely used metrics are: (a) Total variation (TV) and (b) Hellinger distance. The TV distance between probability measures P and Q is defined as: dT V (P, Q) = supA∈A | P (A) − Q(A) | . The Hellinger metric is defined as: 1 H (P, Q) = 2 Z √ √ ( p − q)2 d µ , 2 where µ is any measure that dominates both P and Q and p and q are the densities of P and Q with respect to µ. Note that this definition of the Hellinger distance ostensibly depends on the dominating measure µ. However, as we show below, the quantity on the left side of the above display is independent of µ (and the densities p and q). To this end, let µ0 = P0 + Q0 , and define: p0 = d P0 d P0 and q0 = . d µ0 d µ0 Notice that µ0 dominates both P and Q, so the above derivatives exist. Furthermore, note that µ0 is dominated by µ, so d µ0 /d µ exists. Also p = dP/d µ and q = dQ/d µ. Now, s #2 Z Z "s dP dQ √ √ 2 ( p − q) d µ = − dµ dµ dµ s #2 Z "s d P d µ0 d Q d µ0 = − dµ d µ0 d µ d µ0 d µ s #2 Z "s d µ0 dP dQ − dµ = d µ0 d µ0 dµ s #2 Z "s dP dQ = − d µ0 . d µ0 d µ0 6 This shows the invariance of the Hellinger distance to the choice of the dominating measure µ. The TV distance can also be characterized in terms of densities p and q with respect to some dominating measure µ. We have: Z 1 dT V (P, Q) = supA∈A | P (A) − Q(A) |= | p − q | dµ. 2 Thus the T V distance can be thought of as the natural distance between the densities p and q in √ √ L1 (µ), whereas the Hellinger distance is theR natural distance between p and q in L2 (µ). To establish the above display, note that, since (p − q) d µ = 0 we have: Z Z Z Z (p − q) dµ = | p − q | dµ = (q − p) dµ = | q − p | dµ. {p>q} {p>q} {q>p} {q>p} Let A0 = {p > q} and B0 = {q > p}. Then, the above display implies that P (A0 ) − Q(A0 ) =| P (A0 ) − Q(A0 ) |= Q(B0 ) − P (B0 ) =| P (B0 ) − Q(B0 ) | . Now, for any set A, we have: Z P (A) − Q(A) = Z pdµ − qdµ ZA A = Z (p − q) d µ + A∩{p>q} Z ≤ (p − q) d µ A∩{pq} Z ≤ (p − q) d µ {p>q} = P (A0 ) − Q(A0 ) = | P (A0 ) − Q(A0 ) | . Similarly, we deduce that for any set A: Q(A) − P (A) ≤ Q(B0 ) − P (B0 ) =| Q(B0 ) − P (B0 ) | . It follows that: supA∈A | P (A) − Q(A) |≤| P (A0 ) − Q(A0 ) |=| Q(B0 ) − P (B0 ) | . But 1 2 Z | p − q | dµ = 1 2 Z 1 (p − q) dµ + 2 {p>q} Z (q − p) dµ {q>p} | P (A0 ) − Q(A0 ) | + | P (B0 ) − Q(B0 ) | 2 = | P (A0 ) − Q(A0 ) | = = | P (B0 ) − Q(B0 ) | . 7 Exercise R(a): Show that H 2 (P, Q) = 1 − ρ(P, Q) where the affinity ρ is defined as √ ρ(P, Q) = p q d µ. Exercise (b): Show that dT V (P, Q) = 1 − R p ∧ q d µ. Exercise (c): Show that the following inequalities hold: H 2 (P, Q) ≤ dT V (P, Q) ≤ H(P, Q) (1 + ρ(P, Q))1/2 ≤ √ 2 H(P, Q) . We now introduce an important discrepancy measure that crops up frequently in statistics. This is the Kullback-Leibler distance, though the term “distance” in this context needs to be interpreted with a dose of salt, since the Kullback-Leibler divergence does not satisfy the properties of a distance. For probability measures P, Q dominated by a probability measure µ, we define the Kullback-Leibler divergence as: Z p K(P, Q) = log p d µ . q Once again this definition is independent of µ and the densities p and q, since p/q gives the density of the absolutely continuous part of P w.r.t. Q and p d µ is simply d P . In any case, we will focus on the representation in terms of densities since this of more relevance in statistics. We first discuss the connection of the Kullback-Leibler discrepancy to Hellinger distance. We have: K(P, Q) ≥ 2 H 2 (P, Q) . It is easy to check that ¸ ·Z µ r ¶ q pdµ . 2 H (P, Q) = 2 1− p 2 Thus, we need to show that: ¶ r ¶ Z µ Z µ q q − log pdµ ≥ 2 1− pdµ. p p This is equivalent to showing that: r ¶ r ¶ Z µ Z µ q q pdµ ≥ 1− pdµ. − log p p But this follows immediately from the fact that for any positive x, log x ≤ x − 1 whence − log x ≥ 1 − x. We thus have: d2T V (P, Q) ≤ 2 H 2 (P, Q) ≤ K(P, Q) . It follows that if the Kullback-Leibler divergence between a sequence of probabilities {Pn } and a fixed probability P goes to 0, then convergence of Pn to P must happen both in the Hellinger and the TV sense (the latter two modes of convergence being equivalent). 8 3 Connections to Maximum Likelihood Estimation The Kullback-Leibler divergence is intimately connected with maximum likelihood estimation as we demonstrate below. Consider a random variable/vector whose distribution comes from one of a class of densities {p(x, θ) : θ ∈ Θ}. Here Θ is the parameter space (think of this as a subset of a metric space with metric τ ). For the following discussion, we do not require to assume that Θ is finite-dimensional. Let θ0 denote the data generating parameter. The MLE is defined as that value of θ that maximizes the log-likelihood function based on i.i.d. observations X1 , X2 , . . . , Xn from the underlying distribution; i.e. θ̂n = argmaxθ∈Θ n X l(Xi , θ) , i=1 where l(x, θ) = log p(x, θ). Now · K(pθ0 , pθ ) = Eθ0 ¸ p(X, θ0 ) ≥ 0, log p(X, θ) with equality if and only if θ = θ0 (this requires the tacit assumption of identifiability), since: · ¸ · ¸ · ¸ p(X, θ0 ) p(X, θ) p(X, θ) Eθ0 log = Eθ0 − log ≥ − log Eθ0 = 0. p(X, θ) p(X, θ0 ) p(X, θ0 ) Equality happens if and only if the ratio p(x, θ)/p(x, θ0 ) is Pθ0 a.s. constant, in which case equality must hold a.s Pθ0 if Pθ and Pθ0 are mutually absolutely continuous. This would imply that the two distribution functions are identical. Now, define B(θ) = Eθ0 (log p(X, θ)). It is then clear that θ0 is the unique maximizer of of B(θ). Based on the sample however, there is no way to compute the (theoretical) expectation that defines B(θ). A surrogate is the expectation of l(X, θ) ≡ log p(X, θ) based on the empirical measure Pn that assigns mass 1/n to every Xi . In other words, we stipulate θ̂n as an estimate of θ, where: θ̂n = argmaxθ∈Θ Pn (l(X, θ)) ≡ argmaxθ∈Θ n−1 n X l(Xi , θ) = argmaxθ∈Θ i=1 n X l(Xi , θ) . i=1 Since Pn (l(X, θ)) → Eθ0 l(X, θ) a.s., one might expect θ̂n , the empirical maximizer to converge to θ0 , the theoretical maximizer. This is the intuition behind ML estimation. Define gθ (X) = log {p(X, θ0 )/p(X, θ)}. of θ̂n it follows that: 0≥ From the definition n n 1 X 1 X gθ̂n (Xi ) = (gθ̂n (Xi ) − K(pθ0 , pθ̂n )) + K(pθ0 , pθ̂n ) n n i=1 which implies that: Then Eθ0 gθ (X) = K(pθ0 , pθ ). i=1 ¯ n ¯ ¯1 X ¯ ¯ ¯ 0 ≤ K(pθ0 , pθ̂n ) ≤ ¯ gθ̂n (Xi ) − K(pθ0 , pθ̂n )¯ . ¯n ¯ i=1 9 (3.1) By the strong law of large numbers, it is the case that for each fixed θ, n 1X gθ (Xi ) − K(pθ0 , pθ ) →Pθ0 a.s. 0 . n i=1 This however does not imply that: n 1X gθ̂n (Xi ) − K(pθ0 , pθ̂n ) →Pθ0 a.s. 0 n i=1 since θ̂n is a random argument. But suppose that we could ensure: ¯ ¯ n ¯1 X ¯ ¯ ¯ gθ (Xi ) − K(pθ0 , pθ )¯ →Pθ0 a.s. 0 . supθ∈Θ ¯ ¯ ¯n i=1 This is called a Glivenko-Cantelli condition: it ensures that the strong law of large numbers holds uniformly over a class of functions (which in this case is indexed by θ). Then, by (3.1) we can certainly conclude that K(pθ0 , pθ̂n ) converges a.s. to 0. By the inequality relating the Hellinger distance to the Kullback-Leibler divergence, we conclude that H 2 (pθ0 , pθ̂n ) converges a.s. to 0. This is called Hellinger consistency. However, in many applications, we are really concerned with the consistency of θ̂n to θ0 in the natural metric on Θ (which we denoted by τ ). The following proposition, adapted from Van de Geer (Annals of Statistics, 21, Hellinger consistency of certain nonparametric maximum likelihood estimators, pages 14 – 44) shows that consistency in the natural metric can be deduced from Hellinger consistency under some additional hypotheses. Proposition: Say that θ0 is identifiable for the metric τ on Θ, containing Θ if, for all θ ∈ Θ, H(pθ , pθ0 ) = 0 implies that τ (θ, θ0 ) = 0. Suppose that (a) (Θ, τ ) is a compact metric space, (b) θ 7→ p(x, θ) is µ–almost everywhere continuous (here, µ is the underlying dominating measure) in the τ metric, and (c) θ0 is identifiable for τ . The H(pθn , pθ0 ) → 0 implies that τ (θn , θ0 ) → 0. Hence, under the conditions of the above proposition, Hellinger consistency a.s. imply a.s. consistency of θ̂n for θ0 in the τ –metric. would Proof: Suppose that τ (θn , θ0 ) 6= 0. Since {θn } lies in a compact set and does not converge to θ0 , there exists a subsequence {n0 } such that θn0 → θ? 6= θ0 . Note that h(pθn0 , pθ0 ) → 0. Now, by the triangle inequality: h(pθ0 , pθ? ) ≤ h(pθn0 , pθ0 ) + h(pθn0 , pθ? ) . The first term on the right side of the above display converges to 0; as for the second term, this also goes to 0, since by Scheffe’s theorem, the a.s. convergence of p(x, θn0 ) to p(x, θ? ), guarantees that convergence of the densities {pθn0 } to pθ? happens in total variation norm, and consequently in the Hellinger metric. Conclude that h(pθ0 , pθ? ) = 0; by identifiability τ (θ0 , θ? ) = 0. This shows that θn0 converges to θ0 and provides a contradiction. 2. 10 Exercise: Consider the model {Ber(θ) : 0 < a ≤ θ ≤ b < 1}. Consider the M.L.E. of θ based on i.i.d. observations {Xi }ni=1 from the Bernoulli distribution, with the true parameter θ0 lying in (a, b). Use the ideas developed above to show that the M.L.E. converges to the truth, almost surely, in the Euclidean metric. This is admittedly akin to pointing to your nose by wrapping your arm around your head, but nevertheless, illustrates how these techniques work. For “real applications” of these ideas one has to work with high dimensional models, where the niceties of standard parametric inference fail. 11