Entropy, Exponential Family, and Information Geometry

by allenlu2007

本文主要參考 Dasgupta 的 presentations.  

Dasgupta 用一個具體的例子,很好的把 Entropy, Exponential family, 和 information geometry 連結在一起。

 

Entropy

前文提到 Entropy 的定義,也稱為 Shannon Information.

Entropy 稱為 (Shannon) Information 有點 confusing.  例如和 Fisher information 的觀念恰好相反。

其實 Entropy 定義為 randomness 的程度 (亂度) 更精確的反應其物理意義。至於亂度高代表 information 多或少。

則和應用有關。

 

Dasgupta 的 presentation 說明直觀上 make sense to define 

entropy “measurement of randomness” = H(p) = – ∑ p(x) log p(x)   (note: log is 2-base)

另外如果從以下 6 個 assumptions 出發。可以証明只上述定義唯一滿足。 

NewImage 

Subadditivity.  H(X, Y) ≦ H(X) + H(Y) 

NewImage

另一個有趣的觀點是 Entropy 定義滿足 AEP (asymptotic equipartition property).

這個性質在統計力學以及 Quantum field theory 很重要。

基本上就是在 thermal equilibrium 時。所有的 states 都有同樣的 energy.

NewImage

 

NewImage

 

另一個說法是 (Wiki AEP):

NewImage

不論 X1, X2, .., Xn 是什麼,  p(X1, X2, …, Xn) ~ 2^(-n H(X))

 

舉例而言,如果是一個 fair coin (p=0.5).  H = 1.   p(X1, X2, …, Xn) = 1/2^n.  當然每一個 sequence 機率都是 1/2^n.

如果是一個完全 biased coin (p=1).  H = 0   p(X1, X2, …, Xn) = 1.   只會有一個 sequence (all head) 機率為 1.

如果是 75% head (25% tail) 的 biased coin (p=0.75).  H = 0.811  p(X1, X2, .., Xn) = 1/2^(0.811n) = 0.57^n

p(X1, X2, .., Xn) = (n,x) 0.75^x 0.25^(n-x)  

從 Large number theory 我們知道當 n 很大時,大多數的 x 都會聚集在 x = 0.75n 附近。

p(X1, X2, …, Xn) = (n, 0.75n) 0.75^(0.75n) 0.25^(0.25n) = (n, 0.75n) (0.75^0.75)^n (0.25^0.25)^n = (n, 0.75n) 0.57^n

定性而言 AEP 成立。証明可以參考 wiki

 

KL Divergence (Relative Entropy)

KL(p || q) = ∑ p log(p/q)   (注意沒有 “-” sign!)

可以視為兩個 distribution 之間的 “distance metric”

因為:

(1) KL(p || q) ≧ 0

(2) KL(p || q) = 0  iff  p = q

假設 u 是 uniform distribution over domain S where p ≠ 0

KL(p || u) = ∑ p(x) log S  – H(p) = log S – H(p)

log S 可視為最大亂度 (所有值的機率相等,最 fair case)

KL(p || u) 也就是任意 distribution p 和 uniform distribution 的 “distance metric”. 

 

但是和一般的 “distance metric” 不同 (e.g. L2 norm or L1 norm), 

(1) KL(p || q) ≠ KL(q || p)

(2) KL(p || q) could be ∞, 在某一些點 p≠0 and q=0.

 

A Real Problem Example (Maximum Entropy Method => Exponential Family)

Dasgupta 最精采的地方是用一個簡單的例子把一些觀念串起來。

假設要 model 一本書 (e.g. 字典)中所有 English word 的 distribution

Define Domain S = {English words}   大約有 5 萬常用 words.

如果沒有任何 prior information, 最合理的 distribution 就是 uniform distribution, U.  也就是最大 Entropy (亂度)。

這在統計物理符合實驗結果。在滿足 temperature constraint 下,稱為 Maxwell-Boltzmann distribution.

 

Maximum Entropy Method Without Prior Information

可以証明等價於 maximum entropy method 如下:

max H(p) = – ∑ p(x) log p(x)

subject to   pi ≧ 0;  ∑ pi = 1

利用 Lagrangian multiplier 可以得到 p1 = p2 …   = 1/n

 

假設加上一些 measured statistic constraints:

Pr(length > 5) = 0.3

Pr(end in ‘e’) = 0.45

Pr(start with ‘s’) = 0.08

etc.

 

則可以 model 成

T1(x) = 1(length > 5)  [1(•) 是 indictor function.  =1 if length > 5; 0 otherwise]

T2(x) = 1(end in ‘e’)

etc.

如果用 random variable 可以寫如下。其實不用引入 random variable!!

E(T1) = 0.3

E(T2) = 0.45

E(T3) = 0.08

etc.

 

此時 maximum entropy method 如下: (http://www2.isye.gatech.edu/~yxie77/ece587/Lecture11.pdf)

 

max H(p) = – ∑ p(x) log p(x)

subject to   pi ≧ 0;  ∑ pi = 1

and  ∑ p(x) 1_T1(x) = 0.3  ;  ∑ p(x) 1_T2(x) = 0.45  ;   ∑ p(x) 1_T1(x) = 0.08 ; etc.

可以寫為   ∑ pi rij = E(Rj) = αj   for 1 ≦ j ≦ m    ( T1, T2, .. Tm 是 m 個 statistics constraints)

 

利用 Lagrangian multiplier 可以解出新的 maximum entropy distribution 同時滿足 contraints.

或是用 convex optimization with linear equality constraints. 

詳細解可以參考 reference.   Summarize 如下:

 

NewImage

 

n 是 pi distribution space dimension;   m 是 Ti constraint space dimension.

在我們的例子 rij = 1 or 0 depending on the indictor function conditions?

 

重點是上述 equation 代表 exponential family!!

 

Maximum Entropy Method With Prior Information

如果再加上 prior distribution, π(x).  Maximum entropy method 變成

min KL(p, π) = + ∑ p(x) log p(x)/π(x) = H(p, Π) – H(p)

subject to   pi ≧ 0;  ∑ pi = 1

and  ∑ p(x) 1_T1(x) = 0.3  ;  ∑ p(x) 1_T2(x) = 0.45  ;   ∑ p(x) 1_T1(x) = 0.08 ; etc.

可以寫為   ∑ pi rij = αj   for 1 ≦ j ≦ m    ( T1, T2, .. Tm 是 m 個 statistics constraints)

 

注意此時變成 minimum KL distance 而非 maximum entropy.  如果 Π(x) 是 unifrom distribution.

min KL(p, Π) = min [log S – H(p)] = max H(p) 其實就是 no prior 的 maximum entropy.  

NewImage

和 no prior 結果和之前非常類似。只是 log p 變成 log p/π.  λo → ν.  rij → Ti(x).

Z 稱為 partition constant, 是 λi 的函數。

所以 p(x) 只是多了 prior information π(x).  以及 normalization constant Z 變得更複雜。

 

何時可以忽略 prior information? 答案是不行。因為 π(x) 是 product 的一部份。但下一次的 prior 會是這次的 posterior. 

因此透過迭代的方式仍可以處理掉 prior.  Think the case of uniform prior as no prior. 

 

Maximum Entropy Method for Continuous Distribution

H(f) = – ∫ f(x) log f(x) dx

NewImage

NewImage

NewImage

結論和 discrete distribution 完全一樣!!   注意 inequality constraints 並沒有改變 f(x) 的形式。只是多了一些 terms, 對應的 λi ≧ 0.

 

 

Exponential Family

Maximum entropy method 所解出的結果,不論是否有 prior information.  神奇的剛好是 exponential family distribution.

前文在討論 sufficient statistics 時提到 exponential family 以及相關特性如下。

 Exponential Family 包含大多常見的 PDF/PMF 如下:

the normalexponential,gammachi-squaredbetaDirichletBernoullicategoricalPoissonWishartInverse Wishart and many others. A number of common distributions are exponential families only when certain parameters are considered fixed and known, e.gbinomial (with fixed number of trials), multinomial (with fixed number of trials), and negative binomial (with fixed number of failures). Examples of common distributions that are not exponential families are Student’s t, most mixture distributions, and even the family of uniform distributionswith unknown bounds. 

Scalar parameter exponential family 可以表示如下:

f_{X}(x\mid \theta )=h(x)\exp \left(\eta (\theta )\cdot T(x)-A(\theta )\right)

where T(x), h(x), η(θ), and A(θ) are known functions.

* h(x) 稱為 base measure

* T(x) 就是 sufficient statistic.  

* η 稱為 natural parameter.  

* A(η) 稱為 log-partition function.  

 

Exponential families 有一些重要的特性:

* Exponential families 的 sufficient statistics T(x) 可以 summarize arbitrary amount of IID data.

* Exponential families 都有 conjugate priors, 這對 Bayesian statistics 很有用。

* Exponential families 的 posterior pdf (prior * conditional pdf) 雖然有 close-form.  但大多非 exponential families. E.g. Student t-distribution.

比較之後:

*  h(x) ≈ π(x) 對應 prior information

* η(θ) ≈ λi  對應 Lagrange dual coefficient, 也稱為 natural parameter.  如果 η(θ)=θ (canonical form) 就更像。

  後面有例子說明 natural parameter space 和 expectation parameter space 之間的轉換。

* T(x) ≈ Ti(x) 對應 sufficient statistics?  如果 η(θ) and T(x) 是 vector forms, 則 η(θ)•T(x) = ∑λi Ti(x) 相對應。 

* exp(A(θ)) ≈ Z 對應 partition constant. 

乍看之下 A(θ) 只是一個 normalization constant.  其實所有的 information 都被濃縮在 A(θ) 中!!!

後文會看到 Fisher Information or manifold curvature 只和 A(θ) 有關!!!  是個狠角色。

 

Examples 1: Bernoulli Distribution

Normal form:  p(x) = θ^x (1-θ)^(1-x)  where x = 0 or 1   i.e. p(1) = θ and p(0) = (1-θ)

 

Maximum entropy exponential family form:

Input space: S = {0, 1}

Base measurement or prior information: h(x) = 1

Features: T(x) = x

Nature parameter: η    -∞ < η < ∞   (η = ln θ/(1-θ) )

Log partition function: G(η)

 

f(x) = h(x) exp( η(θ) T(x) – A(θ) ) = exp( ηx – G(η) ) 

 

First sum to 1:  exp(-G) + exp(η-G) = 1  =>  exp(-G) (1+exp(η)) = 1  =>

Log partition function: G(η) = ln(1+exp(η))

f(x; η) = exp(ηx – ln(1+exp(η))) = exp(η)^x *  1/[1+exp(η)]  ###  (natural parameter form)

f(0) = 1/(1+exp(η)) ;  f(1) = exp(η)/[1+exp(η)) ; f(0) + f(1) = 1 as expected

Let expectation parameter: θ = exp(η)/(1+exp(η))   0 ≦ θ ≦ 1

exp(η) = θ/(1-θ)   or  η = ln θ/(1-θ)

f(x; θ) = [θ/(1-θ)]^x (1-θ) = θ^x (1-θ)^(1-x) ### (expectation parameter form)

 

Examples 2: Normal Distribution with Known Variance

Normal form: f(x; θ) =  (1/√2π σ) exp(-(x-θ)^2/2σ^2)

 

Maximum entropy form:

Input space: S = {-∞, +∞}

Base measurement or prior information: h(x) = (1/√2π σ) exp(-x^2/2σ^2)  (zero mean normal distribution)

Features: T(x) = x/𝜎

Nature parameter: η    -∞ < η < ∞   ( η = θ/𝜎 )

Log partition function: G(η) = η^2/2 = θ^2/2σ^2


f(x) = h(x) exp( η(θ) T(x) – A(θ) ) =  (1/√2π σ) exp(-x^2/2σ^2)  exp( ηx – G(η) ) 

 ∫ f(x) = 1  =>  exp(-G)  ∫ (1/√2π σ) exp(-x^2/2𝜎^2) exp(ηx/σ) dx = 1

exp(-G) exp(η^2/2) = 1  =>  G = η^2 / 2  and θ = ση 

 

可以參考 wiki exponential family 得到更多的 distribution 以及對應的參數。

 

Exponential Families Fisher Information

Exponential family 很容易計算 Fisher information.  後文提到 Fisher information 就是 Riemann manifold 的曲率。

f_{X}(x\mid \theta )=h(x)\exp \left(\eta (\theta )\cdot T(x)-A(\theta )\right)


前文已証明 E[ ∇ log f(x; θ) ] = 0

Iθ = E[∇log f(x; θ) ∇log f(x; θ)’] 

From https://web.stanford.edu/class/stats311/Lectures/lec-09.pdf

NewImage

NewImage

NewImage

NewImage 

 

我們尚未用到 exponential family 特性。代入 exponential family distribution

s(x; θ) = ∇ log f(x; θ) = ∇η(θ)•T(x) – ∇A(θ)   =>  ∇η(θ) • E[T(x)] = ∇A(θ)

I(θ) = -E[∇s(x;θ)]  = – E[ ∇(∇η(θ)•T(x)) ] + ∇^2A(θ) = -∇^2 η(θ) • E[T(x)] + ∇^2 A(θ)

由上兩 equations 可以解出 I(θ).

如果是 canonical form :  η(θ) = θ, 可以簡化為:

E[T(x)] = ∇A(θ)

I(θ) = ∇^2 A(θ)

 

實務上當然很少有這麼幸運的 case.  但我們可以用 coordinate mapping (transformation)

用 η space 來簡化計算。同時也提供物理直覺。

首先 η(θ) 必須是 one-to-one mapping, 也就是 θ(η) 存在且唯一。

f(x; θ) 也會有對應的 f(x; η).  注意兩者對應的是不同的 Riemann manifolds.  兩者的 curvatures

或是 Fisher information 並不相等,但有固定的關係見下文。

NewImage

Equation (2) 的 Hessian and vector dimension 需要再檢查。但 k=1 正確。 

可以把 θ manifold maps to η manifold 簡化計算。

NewImage

可以看到 I(η), 也就是 η manifold 的 curvature 很容易計算。就是 Hessian of G(η).

但我們最終是要計算 I(θ), θ manifold 的 curvature.  其實也非常簡單。左右各乘 J’ and J.

J 是 Jacobian.  上述 Jacobian 和 Hessian 的 dimension 都是正確的 k x k. 

Equations (1A), (2A), and (3A) 可以用來計算  E(T(x)), I(θ), Var(T(x)).  不要用 equations (1) and (2).

 

var T(x) = ∇^2 G(η)!!  By Desgupta’s presentation, 也可以參考本文

and I(θ) = J’ [var T(x) ] J !!      Proof to be added.  但可用下例驗証:

 

k=1 的特例。Equations (3) and (4) 是 equations (1A) and (2B) 的特例。

NewImage

 

Legendre Transform

一個有趣的問題是如何選取 θ?  之前的例子如 Bernoulli distribution, Normal distribution, 或是後面的 Poission distribuion

都有共同的特性,就是 θ 對應的是 E(T(x)) or E(x), 也就是 expectation parameter!

我們可以利用這個特性定義 θ.  對於多數的 exponential family distribution 差不多是正確的。

i.e.   θ = E(T(x)) =  ∇G(η)   or θ = dG(η)/dη if k=1

因為 G(η) 是 concave function (to be proved), 上式提醒我們 Legendre transform

Λ*(θ) = sup ( <θ, η> – G(η) )   where θ = ∇G(η)  and η = ∇Λ*(θ)

Legendre transform 特性是  L(L(G(η))) = G(η)  or L(L(Λ*(θ))) = Λ*(θ)

 

注意 Λ*(θ) ≠ A(θ) !!!    A(θ) = G(η(θ)) = G(∇Λ*(θ)) 

可以証明: ∇Λ*(θ) = [∇G(η)]^-1  or  ∇Λ*(θ) * ∇G(η) = 1

所以   A(θ) = G(η(θ)) = G(∇Λ*(θ)) = G( ∇G(η)^-1 ) 

 

實務上是否有用 is still questionable.  看以下的例子:

For Poisson distribution: G(η) = exp(η)  and ∇G(η) = exp(η) = θ

Legendre transform:  Λ*(θ) = θ (lnθ – 1)  =>  ∇Λ*(θ) = lnθ

A(θ) = exp(lnθ) = θ

 

目前看來 Legendre transform 只是有趣但沒有很實際的用途?

Not exactly?  可能和 Bregman divergence 有關?

 

 

另一個觀察就是 Riemann geometry 特性:  參考本文

NewImage 

NewImage

 

重點是 I(θ) ≠ I(η).  但是 ds^2(θ) = ds^2(η).  I(θ) or I(η) 可視為 curvature of the Riemann manifold.

 

對 exponential family, Kullback-Leibler divergence 是 Bregman divergence on the natural parameters.

KL(θ || θ+dθ) = 1/2 dθ’ I(θ) dθ   (true for all distribution),  對於 exponential family =>

KL(θ || θ+dθ) = 1/2 dθ’ I(θ) dθ = 1/2 dη’ ∇^2 G(η) dη 

(infinitesimal) Rao distrance D(θ, θ+dθ) = √ 2 KL(θ||θ+dθ)

其他的部份參考下文 Bregman divergence. 

 

 

Exponential Families Fisher Information Examples

Example 1: Bernoulli distribution 用 (3) and (4)

NewImage

var(T(x)) = var(x) = θ(1-θ)!!

 

Bernoulli distribution 用 (1) and (2), 不建議使用。

NewImage

 

Example 2: Normal distribution with known variance. 

Maximum entropy form: 

Input space: S = {-∞, +∞} 

Base measurement or prior information: h(x) = (1/√2π σ) exp(-x^2/2σ^2)  (zero mean normal distribution)

Features: T(x) = x/𝜎

Nature parameter: η    -∞ < η < ∞   ( η = θ/𝜎 )

Log partition function: G(η) = η^2/2 = θ^2/2σ^2

 

f(x) = h(x) exp( η(θ) T(x) – A(θ) ) =  (1/√2π σ) exp(-x^2/2σ^2)  exp( ηx – G(η) ) 

 

∇G(η) = η = θ/𝜎

∇^2 G(η) = 1

dη/dθ = 1/𝜎

E(T(x)) = E(x/𝜎) = θ/𝜎  =>   E(x) = θ  as expected.

E(T(x)) = E(x/𝜎) = ∇A(θ) * σ = θ/σ  => A(θ) = 1/2 * (θ/σ)^2

var(T(x)) = var(x/𝜎) = 1 => var(x) =  𝜎^2 as expected. 

I(θ) = 1* (1/𝜎)^2 = 1/𝜎^2    

 

Example 3: Normal distribution with unknown mean and variance

??  To be added ??

 

 

Example 4: Poisson Distribution 

f(x; θ) = θ^x / x!  exp(-θ)

 

Maximum entropy form: 

Input space: S = Z+ and 0 (all positive integer space and 0) 

Base measurement or prior information: h(x) = 1/x!

Features: T(x) = x

Nature parameter: η    -∞ < η < ∞   ( θ=exp(η) or η=lnθ )

Log partition function: G(η) = exp(η) = θ


f(x) = h(x) exp( η(θ) T(x) – A(θ) ) =  (1/x!) exp( ηx – G(η) ) 

∑ f(x)  = exp(-G(η)) exp(exp(η)) = 1 => G(η) = exp(η)
f(x; η) = 1/(x!) exp(ηx – exp(η)) 

∇G(η) = exp(η) = θ

∇^2 G(η) = exp(η) = θ

dη/dθ = 1/θ

所以:

E(T(x)) = E(x) = ∇G(η) = θ

E(T(x)) = ∇A(θ) * dθ/dη = ∇A(θ) θ = θ

A(θ) = θ

Var(T(x)) = Var(x) = ∇^2 G(η) = θ

I(θ) = ∇^2 G(η) * (dη/dθ)^2 = 1/θ

 

 

Information Geometry

Information geometry 的物理意義,可以先從上述的 optimization 看出。

 

Maximum Entropy Method With Prior Information

如果再加上 prior distribution, π(x).  Maximum entropy method 變成

min KL(p, π) = + ∑ p(x) log p(x)/π(x) = H(p, Π) – H(p)

subject to   pi ≧ 0;  ∑ pi = 1

and  ∑ pi rij = αj   for 1 ≦ j ≦ m    ( T1, T2, .. Tm 是 m 個 statistics constraints)

 

整個問題可以視為  prior π 投影在 L (affine space given by the constraints.  

即便沒有任何其他 constraints, 至少也有 ∑pi=1 的 constraint) 的 minimum distance.

在一般的幾何條件下的解法就是用畢式定理。就是找垂直於 L 的 projection point. 

NewImage

 

 

KL(p || π) = KL(p || p*) + KL(p* || π) 就是 probability distribution 的畢式定理。?? 

What does it mean? and how to prove?

p 是任意滿足 constraints 的點, i.e. affine subspace. 

 

NewImage

 

重點是在如何定義 inner product <x, y>.  在 information geometry 中,in general 是非歐幾何。

所以 projection <x,y>_G = x’ G y

G 是 Fisher information matrix   gij = E[d/da  d/db] = – E[second derivative] 

Exponential family 的 Fisher Information? 

KL(p, p*) 對應的是 manifold 上的 geodesic curve.

如何找到 p*, 就是找 prior π project 在 p*?   

 

Advertisements