[AI정보이론] Log Sum Inequality, Data-Processing Inequality

 

 

Log Sum Inequality

로그 합 부등식(Log Sum Inequality)은 확률 분포 사이의 관계를 나타내는 데 사용된다

 

이 부등식은 두 확률 분포의 엔트로피 혹은 두 확률 분포 사이의 상대 엔트로피(Kullback-Leibler divergence)와 관련하여 자주 등장한다

 

 

 

Concavity of Entropy

함수 H(p) = log|χ| - D(p||u)는 p에 대한 엔트로피 함수이다

 

여기서, χ 는 가능한 모든 상태의 개수를 나타내며, u는 균등 분포(uniform distribution)를 나타낸다

 

D(p||u)는 p와 u 사이의 Kullback-Leibler divergence(상대 엔트로피)를 나타내며,
이는 확률 분포 p가 균등 분포 u와 얼마나 다른지를 측정하는 척도이다

 

log|χ|는 상수이므로 - D(p||u) 에 의해서 H(P)는 Concave Function이 된다

< D는 convex이기 때문 >

 

 

 

Data-Processing Inequality

마르코프 체인은 특정 상태의 순서가 주어졌을 때, 미래의 상태가 과거의 상태에 직접적으로 의존하지 않고,
오직 현재 상태에만 의존하는 확률 과정을 말한다

 

세 확률변수 X, Y, Z가 순서대로 마르코프 체인을 형성한다고 할 때 (X → Y → Z),
이는 Z의 조건부 분포가 오직 Y에만 의존하고 X와는 조건부 독립이라는 것을 의미한다

 

여기서 조건부 독립이란 Y의 값이 주어졌을 때, X와 Z 사이의 상관관계가 없다는 것을 의미한다

 

1. p(x)는 (X)의 마르지날 확률(marginal probability)이다
2. p(y|x)는 X가 주어졌을 때 Y의 조건부 확률(conditional probability)이다
3. p(z|y)는 Y가 주어졌을 때 Z의 조건부 확률이다

 

이 공식은 X에서 Y로, 그리고 Y에서 Z로의 확률적 전이가 어떻게 이루어지는지를 보여준다

 

마르코프 체인의 핵심적인 아이디어는 X의 특정 상태에서 출발하여 Y를 거쳐 Z로 이동하는 과정에서
Z의 확률이 오직 Y에 의해서만 결정된다는 것이다

 

 

Markov Chain

p(x, z|y)

이 식은 Y가 주어졌을 때 X와 Z의 결합 확률을 나타낸다

이는 전체 확률 p(x, y, z)를 Y의 마르지날 확률 p(y)로 나눈 것이다

 

 

p(x, y)p(z|y)/p(y)

이 식은 p(x, y, z)를 p(x, y)와 p(z|y)의 곱으로 표현한 다음, p(y)로 나누어 조건부 확률 p(x, z|y)를 구하는 방식을 보여준다

여기서 p(x|y)p(z|y)로 변형할 수 있다

 

 

p(x|y)p(z|y) 

이는 (Y)가 주어졌을 때 (X)와 (Z)가 서로 독립임을 나타낸다

즉, (Y)를 알고 있으면, (Z)에 대한 (X)의 정보는 (Y)를 통해서만 영향을 받고, (X)와 (Z) 사이에 직접적인 정보 교환이 없음을 의미한다

 

 

마르코프 체인의 방향성은 X에서 Z로의 정보 흐름을 의미하지만,
이는 Z에서 X로의 정보 흐름도 동일하게 적용됨을 의미한다

 

즉, Y를 기준으로 할 때 X와 Z 사이의 정보 흐름은 대칭적이다

 

 

만약 Z가 Y의 함수로 표현될 수 있다면, 이는 Y가 Z를 완전히 결정한다는 것을 의미한다

 

Y는 중간 매개 변수로서 작용하며, X로부터의 정보는 Y를 거쳐 Z로 전달된다

이 과정에서, Z는 Y의 함수 f(Y)로 정의되기 때문에, Y의 값이 주어지면 Z의 값은 이미 결정된다고 볼 수 있다

 

이렇게 Y가 주어졌을 때 X와 Z가 조건부 독립이라면, X로부터 Z로의 정보 전달은 오직 Y를 통해서만 이루어진다

 

 

여기서 I(X;Y)는 두 확률 변수 X와 Y 사이의 상호 정보량을 나타내며, I(X;Z)는 X와 Z 사이의 상호 정보량을 나타낸다

 

X → Y → Z 이므로 X에서 Y로 가는 정보량이 X에서 Z로 가는 정보량 보다 더 많을 수 밖에 없다

만약 X 에서 Z를 거쳐 Y로 갔다면 부등호의 방향은 반대가 되어야 한다

 

 

 

증명

I(X;Y,Z) = I(X;Z) + I(X;Y|Z)

 

I(X;Y,Z)의 정의에 따라  :  I(X;Y,Z) = H(X) - H(X|Y,Z)

 

여기서 H(X)는 X의 엔트로피, H(X|Y,Z)는 Y와 Z가 주어졌을 때 X의 조건부 엔트로피이다

 

I(X;Y|Z)의 정의에 따라  :  I(X;Y|Z) = H(X|Z) - H(X|Y,Z)

I(X;Z)의 정의에 따라  :  I(X;Z) = H(X) - H(X|Z)

 

따라서, I(X;Z) + I(X;Y|Z)를 계산하면  :  ( H(X) - H(X|Z) ) + ( H(X|Z) - H(X|Y,Z) ) = H(X) - H(X|Y,Z) = I(X;Y,Z)

 

 

I(X;Y,Z) = I(X;Y) + I(X;Z|Y)

 

이는 위와 유사한 방식으로 증명할 수 있으며, 시작점은 I(X;Y)와 I(X;Z|Y)의 정의이다

 

I(X;Y) = H(X) - H(X|Y)

I(X;Z|Y) = H(X|Y) - H(X|Y,Z)

 

두 식을 합하면:

I(X;Y) + I(X;Z|Y) = ( H(X) - H(X|Y) ) + ( H(X|Y) - H(X|Y,Z) ) = H(X) - H(X|Y,Z) = I(X;Y,Z)