[03-2] Jensen's Inequality

Convex function

$x_1, x_2$에 대해서 다음의 조건을 만족하면, 함수 $f$는 convex라고 한다.

 

또한 2차 미분이 모든 곳에서 양수면 convex이다.

 

Inequality

Jensen's Inequality

어떤 $f$가 convex이면, 다음의 조건을 만족한다. 어떤 함수의 기댓값은 기댓값을 취한 후, 함수를 적용하는 것보다 크거나 같음을 의미한다.

 

또한 $f$가 strictly convex면, $X=E[X]$고 $X$는 constant임을 알 수 있다. (equality가 성립하는 조건)

 

Information Inequality

정보 불평등이라 불리는 이유는 오직 p(x)=q(x)일 경우에만, equality가 성립하기 때문이다. 이 말은 대부분의 경우 p와 q는 다르기 때문에 Relative entropy가 0보다 커지게 되어 완벽히 q가 p를 대체할 수 없음을 의미한다.

 

증명 과정은 위와 같다. 마지막에 $log1$이 되는 이유는 $log(x)$가 strictly concave이기 때문이다. Jensen's inequality가 $\frac {p(x)} {q(x)} = c$일 때, equality가 성립하게 된다.

 

Non-negativity of Mutual Information

1. $I(X:Y) \geq 0$
   with eq. iff X와 Y가 독립 → $I(X:Y) = D(p(x,y)||p(x)q(x))$
2. $D(p(y|x) || g(y|x)) \geq 0$
   with eq. iff $p(y|x) = q(y|x)$ for all $x,y$ s.t. $p(x)>0$
3. $I(X:Y|Z) \geq 0$
   with eq. iff X와 Y가 Z에 따라 conditionally independent

 

Maximum Entropy

단순하게 생각해봐도 uniform distribution일 때, 제일 크다는 것을 알 수 있다.

$$ H(X) \leq log |X| $$

with eq. iff X가 uniform distribution

 

Conditioning reduces Entropy

$$ H(X|Y) \leq H(X) $$

with eq. iff X와 Y가 independent

 

Independence bound on Entropy

with eq. iff $X_i$가 독립

 

Log Sum Inequality

with eq. iff $\frac {a_i} {b_i} = c $

 

Information inequality 증명에 활용할 수도 있다.

 

Convex and Concave

Convexity and Relative Entropy

다음을 만족하는 $p$, $q$에 대해 $D(p||q)$는 convex이다.

 

Concavity of Entropy

$H(p)$는 다음의 조건을 만족하면 concave다.

 

Concavity of Mutual Information

Fixed $p(y|x)$에 대해서 X와 Y의 mutual information은 $p(x)$에 대해서 concave이다. Fixed $p(y|x)$는 $p(x)$의 linear function을 의미하기 때문이다.

 

반대로 $I(X:Y)$는 $p(x)$가 fixed면, $p(y|x)$에 convex이다.

 

Markov Chain

$X→Y→Z$로 표현한다. 현재의 정보만 미래에 영향을 준다.

 

Data-Preprocessing Inequality

• $X→Y→Z$인 경우에, $I(X:Y) \geq I(X:Z)$
  $z=g(Y)$라 하면, $I(X:Y) \geq I(X:g(Y))$
  이는 information을 처리하면, 정보 손실이 발생함을 의미한다.
• $X→Y→Z$인 경우에, $I(X:Y|Z) \leq I(X:Y)$

 

항상 성립하는 것은 아니다. 가령 $X,Y,Z$가 markov chain이 아니고, X와 Y가 independent이며 Z=X+Y로 fair RV이면,

$$ I(X:Y) = 0, I(X:Y|Z)=0$$

따라서 $I(X:Y|Z) > I(X:Y)$일 수도 있다.

 

Sufficient Statstics

Data-preprocessing inequality에 의해서 정보 손실이 발생하니까, equality를 만족하는 통계적 분석법을 찾는 것이 연구가 되었고 이들을 sufficient statistics이라 한다.

 

가령 다음의 예시를 들 수 있다.

 

당연히 여러개가 있을 수 있고, 이들 중에 가장 크게 information을 압축하는 방법을 Minimal Sufficient Statistic이라 한다. 다음과 같은 예시가 있다.

 

Fano's Inequality

우선 알고가야할 것이 있다.

$$H(X) \leq log |X|$$

*$|X|$는 $X$의 크기

 

Fano's inquality는 $X$와 $\hat{X}$이 random variable일 때, 

$$ H(X|\hat{X}) \leq h_b(P_e) + P_e log(|X|-1) $$

$P_e = Pr\{ X \neq \hat{X}\}$ 이고 $h_b$는 binary entropy function이다.

 

해석은 간단하다. $P_e$가 매우 작을 경우, 우항이 0으로 근접하게 되어서 $H(X|\hat{X})$도 0으로 수렴하게 되어 $\hat{X}$의 추론이 $X$로 가능함을 의미하게 된다.

 

증명은 다음과 같다.

 

그래서 $P_e$의 entropy를 maximize하면, 1이 되서 다음처럼 corollary를 만들 수 있다.

$$ H(X|\hat{X}) < 1 + P_e log|X| $$