Information Theory & Optimization

Information Theory

3차 산업혁명은 정보 혁명이다. 여기에서 정보를 어떻게 정의할 수 있을까.

Information

• 정보란 놀람의 정도를 의미한다.
  • Degree of surprise
  • 놀람의 정도는 사건이 일어날 확률에 반비례한다.
    $h(e_i) \propto \frac{1}{P(e_i)}$
  • 해가 동쪽에서 뜬다 ⇒ 놀랍지 않은 일
• 자기 정보(Self Information): 특정 사건, 메시지의 정보량
  • $h(e_i)=\log(\frac{1}{P(e_i)})=-\log(P(e_i))$
  • 밑이 2이면 bit, e이면 nat를 의미한다.
  • ex) 주사위를 던져 1이 나오는 사건의 self information은 $\log6$
  • ex) 해가 동쪽에서 뜨는 사건의 self information은 $-\log1=0$

Entropy

• 엔트로피: 확률변수 $X$의 정보량 기댓값
  • 정보량: 무질서도, 불확실성
    $H(X)=\mathbb{E}[h(e_i)]=\mathbb{E}\big[ \log \big( \frac{1}{P(e_i)} \big) \big]$
  • 이산확률 분포 $H(x)=-\sum P(e_i)\log P(e_i)$
    • ex) 동전 던지기에 대한 확률변수 $X$의 엔트로피
      $H(X)=-0.5\log0.5 -0.5\log0.5=\log2$
      ⇒ 1 bit
  • 연속확률 분포 $H(x)=-\int P(e_i)\log P(e_i)$

Kullback-Leibler Divergence

• 두 확률분포 사이의 차이를 측정하는 척도
  $KL(P\|Q)=\sum_xP(x)\log_2{\frac{P(x)}{Q(x)}}$
• 교차 엔트로피(Cross Entropy): 두 확률분포 $P$와 $Q$ 사이의 무질서도
  $H(P,Q)=-\sum P(x)\log_2{Q(x)}$
  $KL(P\|Q)=H(P,Q)-H(P)$
• 머신러닝, 딥러닝에서 교차 엔트로피의 의미
  • 실제 데이터의 분포: $P$
  • 딥러닝 모델이 예측한 데이터의 분포: $Q$
  • 딥러닝 모델의 학습 목표: $P$와 $Q$의 차이를 줄이는 것
  • Cross Entropy가 목적 함수로 사용된다.
  • $Q$로 $P$를 잘 설명하기 위해 $H(P,Q)$를 최소화하는 방향으로 $Q$를 학습시킨다.

Optimization

수학에서 최적화란 주어진 함수의 최댓값, 최솟값을 찾는 문제이다.

머신러닝/딥러닝에서 최적화

• 문제점
  1. 목적함수의 개형이 매우 복잡하다.
     • 많은 양의 학습 데이터 정보가 담겨 있다.
  2. 최적화해야 할 매개변수 개수가 매우 많다.
• 최적화 문제 해결 전략
  1. Exhaustive search: 가능한 해를 모두 생성하여 저장한다.
     • 문제점: 매개변수 개수, 데이터 개수에 따라 연산량이 기하급수적으로 증가한다.
  2. Random Search
     • 문제점: 근거가 없다. 최적해를 찾을 수 있는 보장이 없다.
  3. 경사하강법
     • 난수를 생성하여 초기해를 설정하고 기울기 반대 방향에서 해를 찾는다.

Gradient Descent

• 편미분: 다변수함수에 대한 1차 도함수
• Gradient: 편미분 결과 벡터
• 연쇄법칙: 합성함수의 미분에 사용된다.
  $f(x)=g(h(x))$
  $f'(x)=g'(h(x))h'(x)$
  • 뉴럴네트워크도 합성함수의 형태로 볼 수 있으므로 파라미터에 대한 gradient를 구하기 위해 chain rule을 활용한다.
• Gradient Descent
  • $-f'(x)$ 방향에 목적함수의 최저점이 존재하지만 얼마만큼 이동해야 최적해에 도달하는지는 알 수 없다.
  • 이 문제를 해결하기 위해 Learning Rate 개념을 도입한다.
    $\theta=\theta-\rho \text{g}$