entropie.pdf

7/25/2019 entropie.pdf

1/23

x log x

xex

r r

n

(r1, . . . , rn) ri

i

r

S(r) r

Cr1,...,rnr := r!

r1! rn!

r (r1, . . . , rn)


2/23

S

(r) :=1

r log Cr1,...,rnr .

r1 (r1, . . . , rn)

r = r1+ +rn r1 (r1, . . . , rn)

(p1, . . . , pn) r

Smoy() := limr+

1

r log Cr1,...,rnr =

ni=1

pilogpi.

H(p1, . . . , pn) :=n

i=1

pilog2pi

(p1, . . . , pn)

n

p1 = = pn=n1 S= log n S= log W

(x, v) R

6

(x, v) R6 ft(x, v)

t

ft x

H

R3ft(v)log ft(v) dv H f

N(u, T Id3) T

n! 2n ennn (x) := R+tx1

et dt

W

loge1/ W


3/23

H(f)

f : Rd R

Rd

H(f) := Rdf(u)log f(u) du.

H

S

H

H

I

H

I

log

x x1

R+ logb b > 0

x bx

R+

b N

x 1

logb(x) x b

n Nlogb(b

n) =n.

0< x


4/23

log2 |1| +log2 |2|

12

A

log2 || log2 |A|

A

pA:=

|

|/

|A

| [0, 1]

log2 || log2 |A|= log2|||A| = log2pA.

pA= 0 A= A

pA = 1 A= A

A1, . . . , An

(p1, . . . , pn) pi := pAi

Ai

n

i=1 pilog2 pi.

log2

pA =

|A|/||

A :={a1, . . . , an} n

r N

r

A Ar

x= xr xr r A ri

ai x r =r1+ +rn

fr,i ai fr,i := r1 ri

A, r , r1, . . . , rn

Cr1,...,rnr := r!

r1! rn! .

r

A

r1, . . . , rn

n log2r Cr1,...,rnr I(r)

log2Cr1,...,rnr I(r) n log2r+ log2C

r1,...,rnr .

r

(fr,1, . . . , f r,n)

(p1, . . . , pn)

I(r) r=+

r

ni=1

pilog2pi

.


5/23

A

pi ai

A :={a1, . . . , an}

(p1, . . . , pn)

log(m!)m log m

(p1, . . . , pn)

I(p1, . . . , pn) :=n

i=1

pilog2pi,

log2

f : Rd R

I(f) :=Rd

f(x)log2f(x) dx,

log2

H

I

X

I(X)

I(L(X))

X

I(f)

flog2f

(, F)

Ent(| )

Ent(| ) :=

d

dlog

d

dd

+

.

Ent(| )

R+ {+} Ent(| ) = 0 = Ent(| )< +

dd

log dd

fL1(, F, ;R)

I(p1, . . . , pn) (p1, . . . , pn)

pi


6/23

n

n

n:={(p1, . . . , pn)(R+)n, p1+ +pn = 1}.

0 l og 0 = 0

n

x R+x log x

I(p1, . . . , pn) =nn

i=1

1

n(pilogpi)

n

ni=1

pin

log

ni=1

pin

= log n= I1

n, . . . ,

1

n.

I

n n

x log x

I : n [0, log n]

0

n R

n

log n

I(p1, . . . , pn)

(p1, . . . , pn)

I(p1, . . . , pn)

I

x log x

R+ R 0

1

x log x I

X

Y

{0, . . . , n}

I((X, Y)) I(X) + I(Y),

X

Y

I


7/23

L(X) =p1x1+ +pnxn X L(Y) =q1y1+ +

qmym Y log(ab) = log a+ log b

1in1jm

piqj log(piqj) = 1jm

qj log(qj) 1in

pi =1

+ 1in

pj log(pj ) 1jm

qj =1

.

I(L(X)L(Y)) = I(X)+I(Y)

ri,j := P(X=xi, Y =yj)

I

pi qj

I((X, Y)) I(L(X) L(Y)) =1in1jm

ri,jpiqj

log ri,jpiqj

piqj .

(i, j) ri,j/piqj x x log x

L(X) L(Y)

1in1jm

ri,jpiqj

log ri,jpiqj

piqj 0.

rij = piqj

i

j

X

Y

Ent(L(X, Y) | L(X) L(Y)) 0

I((X, X)) =

I(X)

n

A :={a1, . . . , an} n a1, . . . , an

x

x1, x2, x2, . . . , xm xi A A

A

|x|

m

x

k

Ak

A

(ai1 , . . . , aik) Ak ai1 aik A.


8/23

A

r

r

s1, . . . , sr

S :={s1, . . . , sr} r

S

A

S

r n

A S

n

r

r

2

2

ai A

ci:=si,1 si,ri S S

si r

A n

c := (c1, . . . , cn) (S)n

(r, n)

ci ai x:= ai1ai1 aim

A

ci1ci2. . . cim S

ai x ci S ci S

ai1ai1 aim

A ci1ci2. . . cim

S.

ai1ai1 aim A

m

ci1ci2. . . cim S m

|ci1 | + |ci2| + + |cim|

ci

logrn


9/23

A

r = 3

(r, n)

(r, n)

A

S

(r, n)

(r, n)

(c1, . . . , cn)

ni=1

rli 1,

li =|ci| r,n,l1, . . . , ln

(r, n)

l1, . . . , ln

(r, n)

(c1, . . . , cn)

ci

cj

j=i

ck =si1 sik j < k si1 sij {c1, . . . , cn}

A

ai pi (p1, . . . , pn)

A

c := (c1, . . . , cn)


10/23

(r, n)

S

A

c

L(c) :=n

i=1pi |ci|.

C(r, n)

(r, n)

(r, n)

c

L(c

) infcC(r,n)

L(c).

c

r

(p1, . . . , pn)

A

(p1, . . . , pn)

A

(p1, . . . , pn)

A

I(p1, . . . , pn) infcC(2,n)

L(c) I(p1, . . . , pn) + 1.

r= 2

log2

logr

I

k

A

Ak

kN

I(p1, . . . , pn) infcC(2,nk)

1

kL(c) I(p1, . . . , pn) + 1

k.

1kL(c)

A

c

C(2, nk)

Ak

k

A

I(p1, . . . , pn)

(2, nk

)

k


11/23


12/23


13/23

(p1, . . . , pn)

2I(p1,...,pn).

||

1

2

n

n

n

2I(p1,...,pn)

(p1, . . . , pn) 1

2

{0, . . . , n 1}

n

{0, . . . , n}

I(L(X) L(Y)) = I(X) + I(Y) I((X, Y)).


15/23

nN

pn Fn(p) =Fn1(q, p3, . . . , pn) +q F2(p1/q,p2/q)

q:= p1+p2

I

Fn : n

R

n

N

n N

Fn

Fn(1/ n , . . . , 1/n))< Fn+1(1/(n+ 1), . . . , 1/(n+ 1))

(n1, . . . , nk) Nk n1+ +nk =n

Fn

1

n, . . . ,

1

n

= Fk

n1n

, . . . ,nk

n

+

ki=1

nin

Fni

1

ni, . . . ,

1

ni

;

Fn(p1, . . . , pn) = ni=1

pilogbpi,

b R+

Rn

0 R

min(1, . . . , n)< 0 < max(1, . . . , n) R

max(p1,...,pn)n

1p1++npn=0

I(p1, . . . , pn) = I

(q1 , . . . , q n)

,

(q1 , . . . , q

n)n

qk := (Z)1 e k

Z :=

ni=1e

i

1, . . . , n

(1+ +n)/n 0 0

q := (q1 , . . . , q n) p :=

(p1, . . . , pn) Eq() :=1q1 + + nqn qn


16/23

R

q n Eq() = 0

: R R

() := Eq() := ni=1ie

i

ni=1e i .

C

(0) = (1 + + n)/n

i

{1, . . . , n}

i= min(1, . . . , n)

() :=i+

nj=1je

(ji)

1 +n

j=1e(ji)

,

min(1, . . . , n) +

()

max(1, . . . , n)

R

() =0

() :=Varq() 0,

1, . . . , n

pn Ep() =0 I(p) I(q)

I(q) I(p) =n

i=1

pi

qilog

pi

qi

qi,

Entp | q

p= q

1, . . . , n 0

Ep() = 0

min(1, . . . , n) 0 max(1, . . . , n)

0= (1+ . . . + n)/n

n 0

Rn

1 0] 1, +1[

q

N Z

p= 1/(m+ 1)

N

N

m


17/23

m N

U

Pm

m

K(y|m)

m

y = (y1, . . . , ym) m

K(y | m) := minpPm, s(p)=y

l(p).

(Xi)iN p1a1+

+ pnan a1, . . . , an A :={a1, . . . , an}

c > 0

m N

I(p1, . . . , pn) 1m

yAm

py1 pymK(y | m) I(p1, . . . , pn) + n log mm + cm ,

pz := P(X1=z1, . . . , X m = zm) z Am

1

mE(K((X1, . . . , X m) | m))

m+I(p1, . . . , pn).

S26

1025 = 10

p1, . . . , p26 x1 = , . . . , x26 =


18/23

n

Z/nZ

2

(xn)n 0

1

(an)n

(0+1)/2

(yn)n yn = xn an

(an)n


19/23

I(X)

I(f)

f

Rd

R

X

R

d

R

I( X) = I(X) +d log2 ||,

d2log2(4)

I(X+ ) = I(X)

I((X, Y)) I(X) + I(Y),

X

Y

R

0 log 0 = 0

f

K := [a1, b1] [ad, bd] Rd flog f

K

Rd

K

UK K

K

f

UK

|K|

K

I(UK) I() = log |K| +

K

f(x)log f(x) dx=

K

f(x)log(|K| f) dx= Ent( | UK) ,

Ent( | UK) 0,

=UK

Rd


20/23

: Rd R

exp()

Rd

Rd

(Z)1 exp()

Z

0

Vd

Rd

maxXVd

E((X))=0

I(X) I() := 0+ log2Z,

I() I(X) = Ent(L(X) | ) ,

(x) = x1 R+

E()

0 =

I

() =+d log2(2

1

)

(x) = 1

21 x , x

dd

N(0, )

0 =

d2

X

(Cov(Xi, Xj))1i,jd

I() = d

2 log2

4Det()1/d


21/23

Rd

N(X)

X

N(X) := 14

2 2d I(X).

N(N(m, )) = Det()1/d

X

X

d

||1/d

X

N(X) Det()1/d .

X

K

Rd

K

N(X)

I(UK) UK

K

log |K|

NUK(X) := exp(I(X))

X

Y R

d

N(X+ Y) N(X) + N(Y),


22/23


23/23

Documents

entropie.pdf