Kullback-Leibler

Size: px

Start display at page:

Download "Kullback-Leibler"

ときなたつざわ
5 years ago
Views:

1 Kullback-Leibler Kullback-Leibler 3. q i Kullback-Leibler Kullback-Leibler max-plus Laplace Boltzmann Boltzmann Sanov 3. Sanov Sanov Sanov KL URL Ver Ver Sanov 3. Stirling. 6 8 Ver

2 2 0 : Stirling Stirling. Kullback-Leibler Boltzmann exp ν β νf ν k... [] Csiszar, Imre. A simple proof of Sanov s theorem. Bull Braz Math Soc, New Series 374, , [2] Dembo, Amir and Zeitouni, Ofer. Large Deviations Techniques and Applications. Stochastic Modelling and Applied Probability formerly: Applications of Mathematics, 38, Second Edition, Springer, 998, 396 pages. Google [3] Ellis, Richard, S. The theory of large deviations and applications to statistical mechanics. Lecture notes for École de Physique Les Houches, August 5 8, 2008, 23 pages. [4] Sanov, I. N. On the probability of large deviations of random variables. English translation of Matematicheskii Sbornik, 4284:, pp. 44. Institute of Statistics Mimeograph Series No. 92, March, pdf [5]. I., 2008/2, [6] Ramon van Handel. Lecture 3: Sanov s theorem. Stochas Analytic Seminar Princeton University, Blog Article, 0 October [7] Vasicek, Oldrich Alfonso. A conditional law of large numbers. Ann. Probab., Volume 8, Number 980, Sanov 3.

3 3 Kullback-Leibler Stirling Kullback-Leibler.. q i q i 0, r i= q i =. i q i. q,..., q r. n, i k i k i. i k i /n n., n i n. n k i /n q i,. 2 Boltzmann. q,..., q n, k /n,..., k r /n, n. n i k i, r i= k i = n k! k r! qk qr kr, 0. p i 0, r i= p i =. n i k i /n p i, p i..2 n p i. n, k i log n k i = np i + Olog n = np i + O n,. logk i /n = log p i + Olog n/n 2. Stirling r i= k i = n log = n log n n + Olog n = k i log n i= k i + Olog n, log k i! = k i log k i k i + Olog k i = k i log k i k i + Olog n, log q k i i = k i log q i. 2 Taylor log + x = x x 2 /2 + x 3 /3 x 4 /4 +. i=

4 4. Kullback-Leibler k i. : log k! k r! qk q k r r = n = n = n k i log k i n n log q i + Olog n p i log p i log q i + Olog n i= i= i= p i log p i q i + Olog n Kullback-Leibler D[p q] = i= p i log p i q i : log k! k r! qk q k r r = nd[p q] + Olog n. p i. D[p q] Kullback-Leibler Kullback-Leibler divergence. Kullback-Leibler S[p q] = D[p q] = i= p i log p i q i. n q i p i n. : n p i = exp nd[p q] + Olog n. D[p q] > 0, n Olog n nd[p q], exp nd[p q]..4 Kullback-Leibler Kullback-Leibler D[p q] p = p,..., p r fx = x logx/q = xlog x log q x > 0. f x = log x log q +, f x = /x > 0 fx. fx x = q

5 .5. 5 x. fx fq + f qx = x q x = q. D[p q] = i= p i log p i q i p i q i = 0, i= p i = q i i =,..., r. Kullback-Leibler 0, 0 p i q i., p i q i, D[p q] > 0, p i n n 0., n k i /n q i.. Kullback-Leibler q i p i. n Kullback- Leibler n. Kullback-Leibler, Kullback-Leibler., p i, Kullback-Leibler. Kullback-Leibler. n, Kullback-Leibler. Kullback-Leibler, p i.. n.. B A., A B, B A.., n,...5 r = 2, q = q, q 2 = q.., p = p, p 2 = p, Kullback-Leibler : D[p q] = p log p q + p log p q. p = q 0, p q. Kullback- Leibler q p. p n exp nd[p q] + Olog n., p, D[p q] p

6 6. Kullback-Leibler n 0.. n. n a.?, n q. 0 a < q, a n., 0 a < q, a, n q. q < a., n, a 0. a p. Kullback-Leibler. p a D[p q] p = a., n p = a. q < a, a, n a. : { D[q q] = 0 0 a q, n n log k/n a n q k q n k = inf D[p q] = k p a, n k k/n a q k q n k = exp D[a q] q < a. n inf D[p q] + Olog n. p a a. n D[p q]..6 max-plus Laplace a, b a, b max{a, b}, a, b a + b semiring, semifiled max-plus. max-plus tropical mathematics.,.., max 0, +,. log., : n n logena + e nb = max{a, b}, n n logena e nb = a + b.

7 7.. a b, b a 0, e nb a, n logean + e nb = n log e na + e nb a = a + n log + e nb a a n.. : n n log expna i + Olog n = max{a,..., a r }. i= expna i + Olog n /n n a i., expna i + Olog n = expn max{a,..., a r } + Olog n i= n. Laplace. : β exp nfx + Olog n dx = exp n inf fx + Olog n α x β α fx x = x 0, f x 0 > 0, β e nfx gx dx = e nfx0 2π gx 0 + o nf x 0 α Laplace. n. n. 2 Boltzmann Kullback-Leibler, Boltzmann. 2. q = q,..., q r. n i i k i /n p i, p = p,..., p r. n p = exp nd[p q] + Olog n n. : p = p,..., p r f ν,i p i = c ν ν =, 2,..., s i=

8 8 2. Boltzmann., R r,,...,, f ν,,..., f ν,r ν =,..., s. p, n?, i E i E i p i = U i=, U, n., i, E i, E i p i = U i=, U, n. 2 s =. s >. 2.2 Boltzmann n, r i= p i = Kullback-Leibler K[p q] = r i= p i logp i /q i p = p,..., p r. Lagrange. Kullback- Leibler p. L = p i log p s i + λ p i + β ν f ν,i p i c ν q i= i i= ν= i=. λ, β ν. p i L 0 0 = L λ = 0 = L β ν = p i, i= f ν,i p i c ν ν =,..., s, 2 i= 0 = L p i = log p i q i + λ + s β ν f ν,i i =,..., r 3 ν=. 3, s p i = exp λ β ν f ν,i q i ν=

9 2.3. 9, Z := e λ = i= e s ν= β νf ν,i q i, p i = Z e s ν= β νf ν,i q i 4. Z. p i Z = e λ β ν. β ν 4 2. exp s ν= β νf ν,i Boltsmann. Boltzmann q i p i. p i Gibbs., n p = p,..., p r. n p i Gibbs. s =, f,i = E i, c = U, β = β, p i = Z e βe i q i, Z = e βe i q i, i= log Z β = Z E i e βe i q i = U. i= q i Boltzmann. Gibbs S[p q] = K[p q] = r i= p i logp i /q i : logp i /q i = s ν= β νf ν,i log Z, r i= p i =, r i= f ν,ip i = c ν S[p q] = s β ν c ν + log Z. ν= s =, f,i = E i, c = U, β = β S[p q] = βu + log Z., Boltzmann,. 2.3 qx. n px /n n S[p q] = K[p q] = px log px qx dx. px : f ν xpx dx = c ν ν =,..., s.

10 0 2. Boltzmann, K[p q] px : px = s Z e ν= β νf ν x qx, Z = e s ν= β νf ν x qx dx, log Z = f ν xe s ν= β νf ν x qx dx = c ν. β ν Z... k + + k r = n, β i = log q i p k,...,k r = q k,...,k r = k! k r! qk q k r r k! k r! r n, Z = r = e i= β ik i q k,...,k r, Z r n px = Z e x µ2 /2σ 2, Z = 2πσ 2. Gamma x > 0 px = e x/τ x α τ α Γα = e x/τ+α log x Z, Z = τ α Γα. Beta px = x > 0 x α Bα, β + x = eα log x α+β log+x, Z = Bα, β. α+β Z t Cauchy px = π + x Z 2 = e log+x2, Z = π. Beta 0 < x < px = xα x β Bα, β = eα log x+β log x Z, Z = Bα, β. Poisson p k = e λ λ k k! = e log λk q k, q k = e Z k!, Z = eλ+.

11 s =, f x = x 2, c =, qx = 3., n x 2 x x 2 n/n x x 2 n = n, n x. px = Z e βx2, Z = R e βx2 dx = πβ /2, log Z β = 2β =. β = /2, Z = 2π, px = e x2 /2 / 2π. n. R n 2 n n n. : n n S n fx µ n dx = R fx e x2 /2 2π dx. n S n n n, µ n, fx x x x,..., x n. 4.,. 3 Sanov Sanov. Stirling. [6].. 3. Sanov {, 2,..., r} P : P = { p = p,..., p r R r p,..., p r 0, p + + p r = }. P r. q = q,..., q r P. X, X 2,... {, 2,..., r}, q = q,..., q r. q = q,..., q r. 3 qx = qx.,. 4 Maxwell-Boltzmann.

12 2 3. Sanov A #A, A P A. i =,..., r X,..., X n i k i P #{ k =, 2,..., n X k = i } = k i for each i =,..., r = k! k r! qk qr kr. k,..., k r k i = 0,,..., n, k + + k r = n. k,..., k r k /n,..., k r /n P n P : { k P n = n,..., k } r k i = 0,,..., n, k + + k r = n. n P n n + r. #P n n + r. X,..., X n P n P n, P n. P n P n. p, q P 2 D[p q] : D[p q] = i= p i log p i q i. p i q i 0 0 log 0 = 0, log 0 =. D[p q] Kullback-Leibler. 3. Sanov. : A P inf n 2 A P 5 sup n n log P P n A inf p A D[p q]. n log P P n A inf p A D[p q]. 3 P A A n n log P P n A = inf D[p q]. p A n Kullback-Leibler D[p q] inf r = 2, q = q, q 2 = q, p = p, p 2 = p, D[p q] = p log p q + p log p q. 5 P A., A.

13 3.2. Sanov 3 p = q 0, p q. 0 a < b, A = a, b. P P n A = n q k q n k k n n log α<k/n<β a<k/n<b n q k q n k = inf k D[p q] = a<p<b. Sanov. D[b q] b < q, D[q q] = 0 a q b, D[a q] q < a 3.2 Sanov Stirling k, l. l k l k. l! k! kl k. l! k! = k + k + 2 l kl k. l! k! = l + l + 2 k = k l k. k k l Sanov. Stirling p P n n + r e nd[p q] P P n = p e nd[p q].. p = p,..., p r = k /n,..., k r /n P n, nd[p q] = e nd[p q] = P P n = p = k i log p i + i= p k p kr r k i log q i, i= q k q k r r, k! k r! qk q kr r.

14 4 3. Sanov, : n + r k!... k r! pk p k r r... l i = 0,,..., n, l + + l r = n., p i = k i /n l!... l r! pl p lr r., 3.3, k!... k r! pk p kr r = l! k! lr! k r! kk l k k r l r r k l k k l r k r r k k l k k r l r r =., = l + +l r=n n + r. l!... l r! pl p lr r n + r k!... k r! pk p kr r 3.3 Sanov 3... A {, 2,..., r} P. n= P n = P Q r {, 2,..., r} P. A P p n P n A. P P n A = p P n A D[p n q] = inf D[p q] n p A P P n = p P P n = p n n log P P n A D[p n q] r logn + n inf n n log P P n A inf p A D[p q]. n + r e nd[p n q].. 2. A {, 2,..., r} P. P P n A = P P n = p e nd[p q] n + r e n inf p A D[p q]. p P n A p P n A

15 3.3. Sanov n log P P n A inf D[p q] + r logn + p A n sup n n log P P n A inf p A D[p q] A B, B C, A C. B A C inf p B D[p q] inf p A D[p q] inf p C D[p q]. C B D[p q] p, inf p C D[p q] = inf p B D[p q]. inf p B D[p q] = inf p A D[p q] = inf p C D[p q]., Sirling.. : q i 0, q + + q r = k! k r! qk q k r r k i Z 0, k + + k r = n.., k i,. 2 : k i Z 0, k + + k r = n, k i /n = q i, l! l r! ql q l r r k! q r! qk q k r r l i Z 0, l + + l r = n. : l! k! kl k k, l Z 0. k, l. 2. Sanov.

16 KL n,. q i 0, r i= q i =, a, b i r i= b i = a, p i = b i a = Nb i Na. N Na log Na! Nb! Nb r! qnb qr Nbr = i= p i log p i q i. Kullback-Leibler. /Na Na! N Nb! Nb r! qnb q Nb r r = p /q p pr /q r pr... N Na log Na! Nb! Nb r! qnb q Nb r r = Na Nb i log k log k + Nb i log q i Na k= i= k= i= = Na log k Nb i Na Na log k Na + Nb i log q i k= = Na Na k= 0 log k Na log x dx = [x log x x] 0 = i= p i log p i q i. i= i= i= pi i= 0 k= Na Nb i k= log x dx + i= log k Na + p i log q i i= p i log q i i= [x log x x] p i 0 + p i log q i 2 Na logna r i= Nb i logna = 0.. : N Na p i = b i /a /Na i= p /q p pr /q r p r.

Kullback-Leibler

Kullback-Leibler Kullback-Leible Sanov 206 6 6 http://www.math.tohoku.ac.jp/~kuoki/latex/206066kullbackleible.pdf 0 2 Kullback-Leible 3........................... 3.2........... 4.3 Kullback-Leible.............. 4.4 Kullback-Leible......................