독립(independence)이란 무엇인가 (5): 정보이론에서의 독립

우리는 이전 글에서 '독립'이란 개념이 단순히 떨어져 있다는 의미를 넘어서
어떤 대상이 다른 것으로부터 생성될 수 없고, 다른 정보로부터 예측될 수 없는 상태임을 확인하였다.
엄밀한 수학 용어는 아니지만 편의상 매트로이드 이론에서는 구조적 독립, 정보이론에서는 정보적 독립이라는 이름으로 구체화된다.

이번 글에서는 정보이론에서의 독립이 어떤 수학적 구조로 정의되며 이 개념이 어떻게 정보량, 예측력, 알고리즘 최적성과 연결되는지를 다룬다.

 

확률에서의 독립의 정의

● 두 확률 변수 X, Y가 있을 때, X의 값을 알아도 Y의 확률 분포가 바뀌지 않는다면 두 변수는 정보적으로 독립이라 한다.
● 즉, X에 대한 정보는 Y에 대해 아무런 예측력을 제공하지 않는다.
● 이는 조건부 확률로 표현하면 다음과 같다:

P(Y | X) = P(Y)

 

● 이 등식이 모든 X에 대해 성립하면, 우리는 다음과 같이 정리한다:

두 확률 변수 X, Y가 독립이다 ⇔ 조건부 확률 P(Y|X) = P(Y)

 

 

한편, 확률에서의 독립을 정보이론에서의 독립으로 논의를 확장시키기 위해 먼저 엔트로피라는 개념에 대해서 알아야 한다.

정보량의 기준 – 엔트로피란 무엇인가

● 엔트로피 H(X)는 변수 X의 불확실성 정도를 수치화한 개념이다.

H(X) = - ∑ P(x) log P(x)

● X가 완전히 예측 가능하다면 → H(X) = 0
● X가 완전히 랜덤하다면 → H(X)는 최대

즉, 엔트로피는 'X를 설명하기 위해 얼마나 많은 정보가 필요한가'를 수치로 표현한 것이다.

 

 

 

정보적 관계의 측정 – 상호정보량(Mutual Information)

상호정보량(mutual information)은 두 확률 변수 X와 Y가 얼마나 많은 정보를 공유하고 있는지를 수치로 나타낸 개념이다.

정보이론은 정보적 독립을 상호정보량(mutual information)을 통해 수치화한다.
두 변수 X와 Y에 대해 X를 알게 되었을 때 Y에 대한 불확실성이 얼마나 줄어드는지를 상호정보량 I(X; Y)로 정의한다. 이는 다음과 같다 :

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

여기서 H(Y)는 Y의 엔트로피, H(Y|X)는 X를 알고 있을 때 Y의 조건부 엔트로피이다.

● X를 알면 Y의 불확실성이 줄어든다 → I(X;Y) > 0
● X를 알아도 Y의 불확실성이 줄어들지 않는다 → I(X;Y) = 0

정리: I(X; Y) = 0 ⇔ X와 Y는 정보적으로 독립이다.

 

 

 한편, 상호정보량은 세 가지 방식으로 정의할 수 있으며 각각은 같은 본질을 다른 구조로 표현한 것이다.

1) I(X; Y) = H(Y) − H(Y | X)
2) I(X; Y) = H(X) − H(X | Y)
3) I(X; Y) = H(X) + H(Y) − H(X, Y)

이 정의들을 이해하기 위해서는 각 항이 나타내는 개념을 정확히 파악해야 한다.

▶ H(X)는 확률 변수 X의 엔트로피이다. 이는 X가 얼마나 불확실한지를 수치화한 값이며, X를 완전히 예측하거나 설명하기 위해 필요한 정보량이다
▶  H(Y | X)는 X를 알고 있을 때 Y에 남아 있는 조건부 불확실성이다
▶  H(X, Y)는 X와 Y를 하나의 쌍으로 묶어 함께 고려할 때 필요한 총 정보량이며 이를 결합 엔트로피라고 한다
▶  H(X) + H(Y)는 X와 Y가 서로 완전히 독립일 때 두 엔트로피를 단순히 합한 값이다

이제 각 정의가 의미하는 바를 살펴보자.

 

1)번 수식에 대한 해설 :

I(X; Y) = H(Y) − H(Y | X)는 X를 알게 되었을 때 Y의 불확실성이 얼마나 줄어드는지를 나타낸다.

즉 X가 Y의 예측에 얼마나 기여하는지를 수치로 표현한 것이다.

 

1) + 2) 수식에 대한 해설 :

또한,  I(X; Y) = H(Y) − H(Y | X) = H(X) − H(X | Y) 의 관계가 성립함을 알 수 있다.

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

이러한 방정식을 다음과 같이 직관적으로 이해할 수 있을 것 같다.

• X를 알면 Y의 불확실성이 줄어든다 → 그만큼의 정보가 I(X; Y)
• Y를 알면 X의 불확실성이 줄어든다 → 그만큼의 정보가 I(Y; X)

그런데 I(X; Y) = I(Y; X)이므로 둘은 동일한 값이다

이러한 대칭성은 상호정보량이 정보의 방향이 아니라 정보의 상호 작용을 측정하는 값이라는 것을 보여준다.

즉, X가 Y를 설명하는 정도와 Y가 X를 설명하는 정도가 동일한 척도로 나타나는 것이다.

 

3) 수식에 대한 해설 :

I(X; Y) = H(X) + H(Y) − H(X, Y)는 X와 Y의 개별 정보량을 단순히 더한 값과, 두 변수를 함께 설명할 때 필요한 실제 정보량 간의 차이를 의미한다. 이 차이는 곧 X와 Y가 공유하고 있는 중복된 정보의 양을 뜻한다.

→ 항상 H(X, Y) ≤ H(X) + H(Y)가 성립한다.
→ 등호가 성립하는 경우는 X와 Y가 완전히 독립일 때뿐이다.

이제 상호정보량이 정보적 독립성과 어떻게 연결되는지를 보자.

상호정보량 I(X; Y)가 0이라면 이는 H(Y | X) = H(Y)임을 의미한다.

즉 X를 알아도 Y에 대한 불확실성은 전혀 줄어들지 않으며 X는 Y의 예측에 기여하지 못한다.

동시에 이 경우 H(X, Y) = H(X) + H(Y)도 성립하게 되며, 이는 두 변수가 어떤 중복된 정보도 공유하지 않는다는 것을 의미한다.

즉 Y는 X로부터 생성된 정보가 아니며 X로부터 Y를 유도하거나 설명할 수 없다는 뜻이다.

 

I(X; Y) = 0
⇔ H(Y | X) = H(Y)
⇔ H(X, Y) = H(X) + H(Y)

 

따라서 상호정보량이 0이라는 것은 다음 두 조건을 동시에 만족한다는 의미이다.

→  예측 불가능성: X를 알아도 Y를 예측할 수 없다
→  생성 불가능성: Y는 X로부터 만들어질 수 없다

이 두 조건이 모두 만족될 때 X와 Y는 정보적으로 완전히 독립이라 한다.

 

 

 

 

 

정보량 함수는 Submodular하다

정보이론의 또 하나의 중요한 구조는 엔트로피 함수가 submodular하다는 점이다.

 

정보이론에서 엔트로피 함수는 submodular 함수로 간주된다.
이는 다음과 같이 정의된다:

일반적인 submodular 함수 f에 대해,

f(A) + f(B) ≥ f(A ∪ B) + f(A ∩ B)

 

정보량 함수 H는 다음의 차분 형태를 따른다:

어떤 두 집합 A ⊆ B, 원소 x에 대해

H(A ∪ {x}) − H(A) ≥ H(B ∪ {x}) − H(B)

● 이는 정보의 한계효용 감소(diminishing return)를 뜻한다.
● 이미 많이 아는 상태에서는 새 정보 하나가 기여하는 양이 작아진다.
● 반대로 거의 모르는 상태일수록 새 정보는 더 많은 기여를 한다.

 

→  submodular 구조는 정보가 단순히 축적되는 양이 아니라 기존 지식 위에서 상대적으로 측정되는 값임을
수학적으로 드러낸다.
→  정보는 절대량이 아니라 맥락에 따라 달라지는 차이의 크기로 정의된다.

 

 

다음과 같은 실제 문제들은 모두 동일한 정보량 함수 H의 submodular 성질을 공유한다:

 

□ 정보 획득 (센서 배치)

센서 배치 문제는 관측 가능한 영역의 정보량을 최대화하는 문제이다.
센서 집합 A에 대해 정보량을 H(A)로 정의하면, 이는 센서들이 측정하는 확률 변수들의 엔트로피이다.
센서 s를 A에 추가할 때의 정보 기여도는 H(A ∪ {s}) − H(A)로 측정되며, A가 커질수록 이 값은 감소한다.
즉 H는 submodular 함수이며, 이로 인해 탐욕적으로 기여도가 큰 위치를 선택해도 근사 최적해가 보장된다.

 

 

□ 질의 선택 (Query Selection)

어떤 질문을 던질지를 결정할 때도 동일한 구조가 적용된다.
질문 집합 A에 대해 정보량을 H(A)로 정의하면, 이는 질문을 통해 얻는 응답의 엔트로피이다.
질문이 늘어날수록 새 질문 하나의 기여는 감소하므로 H는 submodular 함수가 된다.
따라서 매 순간 가장 많은 정보를 제공하는 질문을 선택하는 탐욕 전략이 이론적으로 정당화된다.

 

□ Active Learning

라벨링할 샘플을 선택하는 문제에서도 정보량 함수 H는 동일하게 정의된다.
라벨링된 데이터 집합 A가 주어졌을 때, H(A)는 모델의 불확실성 감소량을 의미한다.
샘플 x를 추가할 때의 기여도는 H(A ∪ {x}) − H(A)이며, 이미 유사한 샘플이 많을수록 이 값은 작아진다.
따라서 H는 submodular하며 반복적으로 기여도가 큰 샘플을 선택하는 전략이 효율적이다.

 

□ Feature Selection
입력 변수 중 어떤 피처를 선택할지를 결정하는 문제에서도 피처 집합 A에 대한 정보량 함수 H(A)는 예측 성능이나 모델 정보량을 기반으로 정의된다. 새로운 피처 하나의 기여도는 기존 선택된 피처 구성에 따라 줄어들며, 이로 인해 H는 submodular이다. 따라서 탐욕적으로 정보 기여가 큰 피처를 선택해도 최적에 근접한 결과를 얻을 수 있다.

 

---

위의 예시들을 살펴보면, 현재 시점에서 가장 정보 기여도가

큰 항목을 매번 선택하는 탐욕 알고리즘이 최적해에 매우 근접한 해를 준다는 점을 알 수 있다.
이는 단조 증가하는 submodular 함수 위에서, 선택 가능한 항목 수에 제한이 있을 경우 탐욕 선택이 전체 최적값의

(1 − $\frac{1}{e}$) 이상을 보장한다는 Nemhauser, Wolsey, Fisher 정리에 의해 이론적으로 뒷받침된다.

( 참고: https://shoeraegi.tistory.com/94 )

 

그러나 여기서 중요한 점은, 근사 최적이지 전역 최적은 아니라는 것이다.
탐욕 알고리즘이 항상 전역 최적을 보장하려면, 선택할 수 있는 항목들의 조합이 아주 특정한 조건을 만족해야 한다.
그 조건이 바로 매트로이드이다.

매트로이드에서는 어떤 항목을 고른 뒤라도, 이후 단계에서 남은 항목 중 교체 가능한 조건이 보장된다.
즉, 한 번의 탐욕적 선택이 나중에 발목을 잡지 않는다는 성질이 존재한다.
하지만 정보량 함수는 submodular이기 때문에, 기여도가 맥락에 따라 달라지고 순서에 민감해지기 시작한다.
이로 인해, 앞선 선택이 나중 선택의 가능성을 제한하고 탐욕이 전역 최적을 놓칠 수 있다.

 

예를 들어 feature selection 문제를 생각해보자.
처음에 A라는 feature가 단독으로 가장 높은 정보 기여도를 보여 탐욕적으로 선택했다고 하자.
하지만 이후 B와 C를 함께 선택했을 때, 이 조합이 A보다 훨씬 높은 정보량을 제공하는 경우가 있다.
탐욕은 이 조합을 찾지 못한다. 왜냐하면 탐욕 알고리즘은 매 단계에서 단독 기여도만 비교하고

B와 C의 조합적 시너지를 고려하지 않기 때문이다.

이처럼 서로 간에 조합 효과가 중요한 경우, 초기 선택이 이후 선택을 제한하는 경우, 선택 집합은 더 이상 매트로이드가 아니게 된다.
교환성이 성립하지 않고 탐욕적 선택은 전역 최적을 보장할 수 없다.

 

feature selection은 이러한 조건을 모두 갖춘 대표적인 예이다.
1) 기여도는 맥락에 따라 변하고
2) 일부 feature들은 단독으로는 미약하지만 조합 시 시너지 효과를 낸다
3) 한 번 선택한 feature는 이후 선택을 제한한다

결국, 정보량이 절대적인 값이 아니라 이미 알고 있는 것에 따라 상대적으로 정의되는 값이기 때문에 정보량 기반의 선택 문제는 대부분 매트로이드 구조를 벗어난다. 탐욕 전략은 여전히 강력한 근사 해를 제공하지만, 항상 최적이라는 보장은 사라진다.

 

 

독립이란 어떤 선택이 다른 것에 의해 예측되거나 구성되지 않는다는 말이며 매트로이드는 그 조건이 성립하는 선택 공간이다.
이 위에서는 탐욕이 항상 최적 해를 만든다. 하지만 정보량 함수처럼 기여도가 맥락에 따라 바뀌면
선택이 순서에 묶이고 교환이 불가능해져 탐욕은 최적을 보장하지 않는다.