[ML] 0. Base Knowledge

Intro

Machine Learning은 data들로 부터 특정 pattern을 나타내는 function을 만드는 것이라고 할 수 있다. 즉, pattern은 data에 대한 간단한 요약본이라고 볼 수 있다. 확률/통계 이론 및 선형대수, 미적분, 정보 이론 관련 기본 내용을 해당 포스팅에 정리한다. 여기서 다루는 내용은 대게 많이 추상적인 내용이며, 키워드 중심의 내용이다. 만약, 추가적인 설명이 필요하다면 키워드를 기반으로 더 검색을 하는 것이 좋을 것이다.

Probability/Statisics

확률과 통계는 대게 거의 동의어처럼 사용되지만, Statistics는 대게 과거를 의미할 때 사용하는 반면 Probability는 미래를 의미하는 용도로 많이 사용되어진다.

Probability Space

확률 공간을 정의하는 것은 확률을 이해하는 토대가 된다. 확률을 적용하기 위한 공간을 먼저 살펴보자.

Sample Space( $\Omega$ )
가능한 모든 결과값의 집합이다.
ex. 동전을 두 번을 던져서 나올 수 있는 모든 결과값은 $\Omega =$ $\{ hh, ht, th, tt \}$
Event( $E$ )
Sample Space의 Subset이다. Sample Space에서 발생할 수 있는 event라는 의미로 볼 수 있다.
ex. 동전을 두 번을 던져서 모두 같은 면이 나오는 Event는 $E =$ $\{ hh, tt \}$
Field( $\mathcal{F}$ )
Sample Space에서 발생 가능한 모든 Event들의 집합이다.
ex 동전을 두 번 던져서 나오는 결과값의 Field는 $\mathcal{F} =$ $\{$ $\emptyset$ , $\{hh\}$ , $\{ht\}$ , $\{th\}$ , $\{tt\}$ , $\{hh, ht\}$ , $\{hh, th\}$ , $\{hh, tt\}$ , $\{ht, th\}$ , $\{ht, tt\}$ , $\{th, tt\}$ , $\{hh, ht, th\}$ , $\{hh, ht, tt\}$ , $\{hh, th, tt\}$ , $\{ht, th, tt\}$ , $\{hh, ht, th, tt\}$ $\}$
$\sigma$ -field
자신 내부의 원소를 포함하는 합집합을 모두 포함하는 셀 수 있는 field를 sigma field라고 한다.
이 $\sigma$ -field는 일반적인 확률과 특정 domain에서의 확률을 정의하는데 필요하다.
우리가 sample space( $\Omega$ )와 $\sigma$ -field $\mathcal{F} \subset 2^{\Omega}$ 가 주어질 때, 확률P가 다음과 같이 mapping한다고 하자. $P: \mathcal{F} \mapsto [0, 1]$ 이때 P는 다음과 같은 특징을 가진다.
- $A \in \mathcal{F}$ 인 모든 A에 대해서 $P(A) \leq 0$ 이다.
  $P(\emptyset) = 0, P(\Omega) = 1$
- $\{A_i\}_{i \in I}$ 이고, 서로 다른 모든 i, j에 대해 $A_{i}\cup A_{j} = \emptyset$ 이라면, 아래 식을 만족한다.
  $P(\cup_{i \in I}A_i) = \sum_{i \in I}P(A_i)$

Important properties of Probability

Joint Probability
두 Event의 Joint Probability는 두 Event의 합집합의 확률을 의미한다. $P(A, B) = P(A \cap B)$
Marginal Probability
대게 두 개 이상의 Event가 있을 때, 각 각의 Event의 확률을 특정할 때 사용한다. $P(A), P(B)$
Independence
두 Event가 독립이라는 의미는 서로의 Event가 서로 영향을 받지 않는다는 의미이다. 주의할 것은 이것이 의미하는 것이 두 Event의 교집합이 없다는 의미가 아니다.
예를 들어보면 다음과 같다. 우리가 위에서 예시로 사용한 두 개의 동전을 던진 결과를 보자. 두 개의 동전이 모두 앞면이 나오는 경우와 모두 뒷면이 나오는 경우는 서로 독립일까? 이는 독립이 아니다. 왜냐하면, 동전이 모두 앞면이 나오는 사건은 필연적으로 모두 뒷면이 나오는 사건은 반드시 일어나지 않을 것이라는 증거가 되기 때문이다. 반대로, 모두 앞면이 나오는 사건과 한 번만 앞면이 나오는 사건을 생각해보자. 하나의 사건이 일어났다고, 반드시 그 사건이 일어났거나 안일어났다는 관계를 밝혀낼 수 없다. 따라서, 이러한 경우 두 사건이 독립적이라고 한다.
이를 수학적으로 표현하면, 다음과 같이 표현할 수 있다.
$P(A, B)=P(A)P(B)$
즉 위 공식이 성립하면 독립이며, 독립이라면 위의 식이 성립한다.
Conditional Probability
두 Event가 있을 때, 하나의 Event가 발생했을 때 다른 하나의 Event가 발생할 확률을 의미한다. 따라서, 이는 다음과 같이 수식으로 표현할 수 있다.
$P(A|B) = {{P(A, B)}\over{P(B)}}, (P(B) \neq 0)$
여기서 independence 특성을 더 명확하게 확인할 수 있는데, 만약 A와 B가 독립이라면, $P(A|B) = P(A)$ 이다.
즉, B가 발생했는지 여부는 A의 결과에 영향을 안준다는 것이다.
Partition
Sample Space( $\Omega$ )를 겹치지 않고, 모두 포함하는 Event의 집합을 의미한다. 따라서, 이를 식으로 다음과 같이 표현할 수 있다.
$\cup_{i=1}^{n}{P_i} = \Omega$ 이고, $\cap_{i=1}^{n}{P_i} = \emptyset$
Marginalization
전체 Sample space( $\Omega$ )에 대하여 B가 이에 대한 partition일 때, 아래 공식이 성립한다.
$P(A) = \sum_{i=1}^{n}{P(A,B_i)} = \sum_{i=1}^{n}{P(A|B_i)P(B_i)}$
Bayes' Theorem
만약 $P(B) \neq 0$ 라면, 아래 공식이 성립한다. 간단히 conditional probability를 풀어주면 아래 식을 얻을 수 있다.
$P(A|B) = {P(B|A)P(A)\over{P(B)}}$
해당 식은 단순히 Joint Probability로 변환하고, 다시 반대 확률로 변경했을 뿐이다. 이 공식이 중요하다기 보다는 이 공식이 가지는 의미를 이해하는 것이 중요하다. 확률을 사건의 발생의 빈도로 이해하는 Frequentist Approach에서는 관측을 통해서 특정 데이터가 발생할 확률을 얻는다. 만약 우리가 원하는 확률이 관측을 통해서는 얻을 수 없는 데이터라고 하자. 이 경우에 우리는 확률의 역연산이 필요하다. 위의 공식을 보면 특이한 것이 보이는데, 바로 $P(A|B)$ 와 $P(A)$ 이다. 이는 전체 확률을 통해서 Conditional Probability를 찾는 것이다. 그렇기에 우리는 이를 역연산이라고 부르며, 우리가 가지고 있는 기존 사전 확률(Priority, 이전까지 맞을 거라고 생각한 확률)을 통해서 데이터가 주어졌을 때의 사건의 확률을 다시 계산해보는 것이다. 이 과정을 Bayesian Update라고 하는데 이 과정을 통해서 얻은 $P(A|B)$ 를 다시 다음 데이터에 대해서는 $P(A)$ 로써 활용하는 것이다. 이렇게 해서 우리는 점진적으로 $P(A)$ 를 찾아나갈 수 있다.

Random Variable

Random Variable이라는 것은 특정 사건을 수학적으로 표현하기 위해서 변형하는 과정을 의미한다. 우리는 이전 예시에서 두 개의 동전을 동시에 던져서 나온 결과를 Sample Space로 두었고, 이를 $\Omega =$ $\{ hh, ht, th, tt \}$ 라고 표현했다. 하지만, 이와 같은 표기 방식은 수학적인 연산을 적용하기 어렵다. 따라서, 우리는 앞면이 나온 경우를 $X=1$ , 뒷면이 나온 경우를 $X=-1$ 라고 하는 형태로 치환하는 것이다. 여기서 만들어진 X를 우리는 Random Variable이라고 부른다. 이런 치환을 통해서 우리는 확률을 Random Variable에 대한 함수로 표현할 수 있다.

또, Random Variable을 정의하여 다음과 같은 값을 연속적으로 정의할 수 있다.

Mean
Random Variable의 평균 또는 기댓값이라고 부른다.
$\mu_{X} = E[X] = \sum_{x}{xP(X=x)}$
Variance
평균에서 데이터가 떨어진 정도를 표현하는 값으로 분산이라고 부른다.
$\sigma_{X}^{2} = E[(X-\mu_{X})^2] = E[X^2] -\mu_{X}^{2}$
Covariance
Random Variable X와 Y의 상관관계(Correlation)을 확인하는 척도로 사용한다.
$cov(X, Y) = E[(X-\mu_{X})(Y-\mu_{Y})] = E[XY] -\mu_{X}\mu_{Y}$
만약, 두 X와 Y가 서로 전혀 상관이 없다(Independent)면, $cov(X, Y) = 0$ 이다. 그 반대는 성립하지 않지만, 그럴 가능성이 굉장히 높아진다.
Correlation Coefficient
Covariance보다 더 엄격한 상관관계를 확인하는 척도로 사용되는데, 단순히 Covariance를 각 표준편차( $\sigma$ )로 나눈 것이다. 이로 인해 결과 값은 [-1, 1] 사이 값이 된다.
$corr(X, Y) = {cov(X,Y)\over{\sigma_{X}\sigma_{Y}}}$
따라서, 1일 수록 두 Random Variable의 상관성이 높으며 비례하는 관계라는 것을 의미하며, -1일 경우에는 상관이 높지만 반비례하는 관계라는 것을 의미한다. 반대로, 0인 경우는 상관 관계가 아주 낮음으로 독립일 가능성이 높다. 그렇다고 100%는 아니지만, 단지 그럴 확률이 굉장히 높다는 것이다. 주의할 점은 Correlation Coefficient가 1이라고 X가 Y의 원인이 되는 것은 아니라는 것을 유의해야 한다. 단순히 X가 일어났을 때, Y가 일어날 확률이 높다는 것이다.

Law of Large Numbers

경험적 확률과 수학적 확률 사이의 관계를 나타내는 법칙으로, 전체 경우의 수와 이에 따른 확률(모집단)이 있을 때, 관측한 경우의 수와 이에 따른 확률(표본 집단)은 관측 데이터의 크기가 커질 수록 표본 평균이 모평균에 가까워짐을 의미한다.

자주 사용되는 Probability Distribution Function

특정 task의 경우 이미 정의된 확률 분포를 통해서 표현할 수 있는 경우가 있다. 따라서, 아래와 같은 대표적인 확률 분포는 알아두는 것은 중요하다.

Bernoulli distribution
하나의 사건이 일어날 확률을 의미한다. 발생하는 경우를 X=1, 그렇지 않은 경우를 X=0으로 random variable로 치환하여 나타낸 확률 분포(probability distribution)이다. 대표적인 사건은 동전 던지기와 같은 두 개의 결과만 갖는 binary event을 표현할 때이다.
따라서, 사건이 일어날 확률을 p라고 할 때, 다음과 같이 Random Variable에 대한 확률을 정의할 수 있다.
$P(X=x) = p^{x}(1-p)^{1-x}$ 복잡해보이지만, 실상은 X가 0 또는 1이므로, $P(X=0)=1-p$ 이고, $P(X=1)=p$ 이다.
- 평균 $E[X] = p$
- 분산
  $Var[X] = E[X^2] - \mu_{X}^2 = p - p^2 = p(1-p)$
Binomial Distribution
확률이 p인 사건을 n번 수행했을 때, x번 발생할 확률을 의미한다. 따라서, Random Variable X의 범위는 {0, 1, …, n}이 된다. 대표적인 사건은 동전 던지기를 여러 번 던졌을 때, 앞 면이 x번 나올 경우의 수이다.
이에 따라 Random Variable에 대한 확률을 정의하면 다음과 같다.
$P(X=x) = {n \choose x}p^x(1-p)^{n-x}$
이 또한 복잡해 보이지만, 사실은 독립적인 Bernoulli의 연속 수행으로 볼 수 있다.
- 평균
  $E[X] = np$
- 분산
  $Var[X] = Var[\sum_{i}X_i]=\sum_iVar[X_i]=np(1-p)$
Beta Distribution
$\alpha, \beta > 0$ 를 만족하는 두 parameter를 이용한 probability distribution이다.
이는 [0, 1]에서 continuous한 random variable를 이용할 수 있다. 이에 따른 확률은 다음과 같다.
$P(X=x) \propto x^{\alpha-1}(1-x)^{\beta-1}$
이에 대한 의미를 이해하자면, 확률에 대한 확률 분포이다. 각 $\alpha - 1$ 와 $\beta - 1$ 를 성공 횟수, 실패 횟수라고 하자. 이는 이미 알고 있는 모집단(전체 집합)의 계산 결과이다. 그리고 random variable을 특정 event의 확률이라고 하자. 예를들면, 동전 던지기를 할 때, 앞면이 나올 확률이 $1\over2$ 이라는 것을 이미 알고 있다. 따라서, 우리는 $\alpha - 1$ = $\beta - 1$ 라는 것을 알고 있는 것이다. 하지만, 실제로 동전 던지기를 5번 수행했을 때, 4번 앞면이 나왔다고 하자. 그렇다면, 우리가 추측한 해당 event의 확률은 $4\over5$ 이 된다. 그렇다면, 실제로 해당 확률이 $4\over5$ 일 확률을 얼마나 될까?
이를 측정하기 위한 것이 Beta distribution인 것이다. 이에 따라, Beta distribution을 PDF로 표현하면 ${\alpha\over\alpha+\beta}$ 에서 높은 확률값을 가지는 것을 볼 수 있다.
- 평균
  $E[X] = {\alpha\over{\alpha+\beta}}$
- 분산
  $Var[X] = {\alpha\beta\over{(\alpha+\beta)^2(\alpha+\beta+1)}}$
위의 평균과 분산을 보면 알 수 있듯이, 만약 이전 모집단에서의 평균값에 대한 믿음이 크다면, 각각 $\alpha, \beta$ 의 비율은 유지하면서 상수배를 수행하여 평균은 동일하지만 분산 값을 더 적게 만들어 뾰족한 형태의 분포를 완성할 수도 있다. 이 경우에는 평균과 맞지 않는 표본집합에서의 평균을 굉장히 확률이 낮은 확률로 식별하는 것이다.
Gaussian Distribution
$\mu, \sigma^2$ 를 parameter로 갖는 probability distribution이다.

이는 $[-\infin, \infin]$ 를 구간으로 continuous한 random varible을 이용한다. 이에 따른 확률은 다음과 같다. (단일 random variable인 경우)

$P(X) = {1\over{\sqrt{2\pi\sigma^2}}}\exp(-{1\over{2\sigma^2}}(X-\mu)^2)$

이 분포는 굉장히 많은 곳에 사용되는데 우리가 생각할 수 있는 대게의 자연 발생에 의한 현상들(ex. 사람 키의 분포)이 이 분포를 따르기 때문이다. 그렇기에 다양한 환경에서 많이 사용되는 분포이다. 뿐만 아니라 (Lindeberg-Levy) Central Limit Theoriem에 따르면, 표본에서 얻은 표본 평균을 구하면 구할 수록 점점 Gaussian Distribution을 따라간다. 즉, $n \rarr \infin$ 이면, 표본 평균이 이루는 분포가 Gaussian이라는 것이다.

추가적으로 알아볼 것은 바로 여러 개의 Random Variable로 Gaussian Distribution을 더 높은 차원으로 구성할 수 있다는 것이다. 이를 수행하면, Gaussian 분포가 평균과 분산을 포함하기 때문에 두 데이터의 경향성(Covariance)를 어느정도 파악할 수 있다.

Calculus

일명 미적분학으로, 대게의 미적분 법칙은 모두 알고 있을 것이라고 생각하고 넘어간다.

Optimization

정말 모두가 알고 있을 거 같지만, 그럼에도 중요하기 때문에 정리하고 넘어가자. 일반적으로 Optimization이란 최적값을 찾는 과정이다. 이 과정에서 대게 사용되는 것이 최솟값 또는 최댓값이다. 우리는 최솟값/최댓값을 미분을 통해서 구할 수 있다.

여기서는 Convex라는 성질에 대해서 자세히 다루지 않는다. 시간이 있다면, 이에대한 개념도 반드시 숙지하기를 바란다.

최대/최소 구하기

모두가 알다시피 함수의 미분은 기울기를 의미한다. 만약 함수의 미분에 특정 값을 대입할 경우 이는 그 지점에서의 기울기를 의미한다.

먼저, 함수의 미분에 대입한 값이 0인 경우에 해당 값(극값)이 가지는 성질을 기억해야 한다. 만약, 값이 0으로 하는 값을 기준으로 좌우 부호가 바뀐다면, 이는 정말 극대, 극소라는 의미를 가진다. 즉, 해당 구간에서 최소와 최대라는 의미를 가지는 것이다.

이를 이해하기 위해서는 함수의 기울기의 부호가 바뀌었다는 의미를 살펴보아야 한다. 이는 함수의 값이 구간 내에서 가장 작은 값(극소) 또는 구간 내에서 가장 큰 값(극대)라는 것을 의미한다. 왜냐하면, 직관적으로 기울기가 0이 되기 전까지는 계속해서 증가/감소해왔다는 것을 알기 때문이다. 따라서, 우리는 기울기가 0인 지점을 모두 찾아 비교하면, 그 안에서 최대/최소를 찾을 수 있을 것이다.

그런데 어떻게 하면, 기울기가 0인 지점이 극대인지 극소인지를 구분할 수 있을까? 이것은 바로 직전의 값을 미분 함수에 대입해보면 쉽게 알 수 있다. 하지만, 이것이 매번 그렇게 쉽게 판별되는 것은 아니다. 따라서, 우리는 이중 미분을 사용한다. 이중 미분 함수에 극값을 대입했을 때 양수라면 이는 극소를 의미하고, 음수인 경우는 극대를 의미한다. 이 또한, 직관적으로 기울기의 변화량이라는 이중 미분의 정의를 알면, 직관적으로 와닿을 수 있다.

이렇게 해서 극대와 극소를 골라내고, 이중에서 가장 큰 값과 가장 작은 값을 찾아내면, 우리는 이것을 함수의 최적화를 수행했다고 한다.

Constraint Optimization

여기서는 특별한 case를 위한 예시이다. 특정 조건이 주어졌을 때, 이를 만족하면서 특정 함수의 optimization을 수행하는 것이다.

그러면 우리가 최적화하고자 하는 목적함수( $\mathcal{J}(\bold{x})$ )와 등식 제약 조건( $h_{j}(\bold{x})$ ), 부등식 제약 조건( $g_{i}(\bold{x})$ )을 살펴보자.

우리는 모든 최적화 문제를 다음과 같은 형태로 묘사할 수 있다.

\begin{align*} \text{minimize} \quad & \mathcal{J}(\bold{x}) &\\ \text{subject to} \quad & g_{i}(\bold{x}) \leq 0, & i = 1, ..., M \\ & h_{j}(\bold{x}) = 0, & j = 1, ..., L \end{align*}

maximization인 경우는 음수를 취해서 결과를 구한 후 변환 시에 다시 음수를 취해주면 된다. 그리고 부등호가 반대인 제약 조건인 경우에도 양변에 음수를 취해서 간단하게 뒤집는 것이 가능하다.

이러한 문제를 풀기 위해서는 우리는 식을 Lagrangian 형태로 변환해야 한다.

Lagrangian

이는 조건부식에 있는 조건에 변수( $\nu$ , $\lambda$ )를 곱한 값의 합과 원래 목적 함수( $\mathcal{J}(\bold{x})$ )의 합이다.

\mathcal{L}(\bold{x}, \boldsymbol{\nu}, \boldsymbol{\lambda}) = \mathcal{J}(\bold{x}) + \sum_{i=1}^{M}{\nu_{i}g_{i}(\bold{x})} + \sum_{j=1}^{K}{\lambda_{j}h_{j}(\bold{x})}

여기서 Lagrangian 함수의 optimization이 곧 목적함수의 optimization이다. 증명은 수행하지 않는다. 이에 대한 추가적인 설명이 필요한 경우에는 직접 찾아보아야할 것이다.
여기서 만약 등식만 있는 식인 경우에 우리는 간단히 모든 변수에 대해서 편미분이 0이 되는 등식을 이용해서, 최적 $\bold{x}$ 를 찾을 수 있다. 위에 식에서 부등식 조건( $g_{i}(\bold{x})$ )이 사라진다면, 우리는 미분을 통해서 처리해야하는 값은 총 x의 크기(N)와 L이다. 이는 우리가 편미분해서 구할 수 있는 식의 갯수와 똑같다. 즉, 우리가 모르는 변수는 N+M개 우리가 가진 등식은 N+M개이므로 연립해서 각 값을 구할 수 있는 것이다.

하지만, 부등식인 경우에는 추가적으로 고려해줘야할 것이 있다.

KKT Condition

이는 우리가 최적값( $\bold{x}_{*}$ )를 찾았을 때, 다음과 같은 $\boldsymbol{\nu_{*}}$ , $\boldsymbol{\lambda_{*}}$ 가 존재해야 한다는 정리이다.

Optimality
$\nabla\mathcal{L} = \nabla\mathcal{J}(\bold{x}_{*}) + \sum_{i=1}^{M}{\nu_{*(i)}\nabla g_{i}(\bold{x}_{*})} + \sum_{j=1}^{L}{\lambda_{*(j)}\nabla h_{j}(\bold{x}_{*})} = 0$
위에서 보았던 최적화를 수행하는 식이다.
Feasibility
$g_{i}(\bold{x}_{*}) \leq 0, i = 1, ..., M$
$h_{j}(\bold{x}_{*}) = 0, j = 1, ..., L$
조건이 만족하는지를 확인하는 것이다.
Complementary slackness
$\nu_{*(i)}g_{i}(\bold{x}_{*}) = 0, i = 1, ..., M\quad(\nu_{*(i)} \geq 0)$
위의 식은 다소 헷갈릴 수 있는데 가장 알아듣기 쉬운 형태는 아래이다.
$g_{i}(\bold{x}_{*}) \lt 0\text{, then } \nu_{*(i)} = 0$
$g_{i}(\bold{x}_{*}) = 0\text{, then } \nu_{*(i)} > 0$

위의 식을 만족하는 $\bold{x}_{*}$ , $\boldsymbol{\nu_{*}}$ , $\boldsymbol{\lambda_{*}}$ 를 찾으면, 그것이 최적값에서의 $\bold{x}_{*}$ 이다.

Lagrangian Dual Problem

여기서 한 발 더 나아가면, Lagrangian에 다시 한번 Lagrangian을 취할 수 있다.

우리가 만약 Lagrangian의 하한을 $\mathcal{G}(\boldsymbol{\nu}, \boldsymbol{\lambda})$ 이라 하고,

\mathcal{G}(\boldsymbol{\nu}, \boldsymbol{\lambda}) = \inf_{\bold{x} \in \mathcal{X}}\mathcal{L}(\bold{x}, \boldsymbol{\nu}, \boldsymbol{\lambda})

$\boldsymbol{f}^{*}$ 을 최적값이라고 한다면, 아래 식이 성립한다.

\boldsymbol{f}^{*} \geq \min_{\bold{x}}\mathcal{L}(\bold{x}, \boldsymbol{\nu}, \boldsymbol{\lambda}) := \mathcal{G}(\boldsymbol{\nu}, \boldsymbol{\lambda})

따라서, 우리는 $\mathcal{G}$ 의 최댓값을 찾으면 해당 값이 최적해에 근사한다는 것을 알 수 있다.

이는 우리가 풀고자 하는 문제의 형식을 다시 한 번 바꾸게 된다.

\begin{align*} \text{minimize} \quad & \mathcal{G}(\boldsymbol{\nu}, \boldsymbol{\lambda}) &\\ \text{subject to} \quad & \boldsymbol{\nu}_{i} \geq 0, & i = 1, ..., M \end{align*}

이 식을 KKT condition을 이용하여 푸는 것이 기존 식보다 쉽게 풀 수 있는 경우가 많다. 따라서, 이러한 형태로 문제를 풀이할 수도 있다.

Information Theory

Entropy

수학에서 정보의 불확실성(uncertainty)을 표현하기 위해서 물리의 entropy 라는 개념을 도입한 것이다. 즉 정보가 가지는 "surprise" 정도가 크다면, entropy가 큰 정보를 의미하고, 일반적인 정보라면 이는 entropy가 작은 정보인 것이다.

수학적으로 다시 정의하자면, 다음과 같다.
sample space $\Omega$ 에서 정의된 random variable $X$ 와 확률 $p_{X}(x)$ 이 주어질 때, Entropy를 $H(x)$ 라 하자.

H(X) = -\sum_{x \in \Omega}p(x)\log_{2}p(x)

위 식에서 log의 밑이 2인 것을 알 수 있는데 computer science에서는 정보가 bit단위로 저장되기 때문에 기본적으로는 2를 사용한다. 하지만, 상황에 따라서는 다른 밑을 사용할 수도 있다.

헷갈릴 수 있는데 표기법이 굉장히 다양하니 유의해서 보도록 하자.

H(X) = H_{p}(X) = H(p) = H_{X}(p) = H(p_{X})

최댓값과 최솟값

Entropy는 정보의 불확실성을 나타낸다고 했다. 즉, 정보가 확실할 수록 Entrophy는 0으로 수렴하며, 확실히 아는 정보의 경우 Entropy가 최솟값인 0이 된다.
반대로 Entropy의 최댓값의 경우 $|\Omega| = n$ 이라고 할 때, $\log_{2}{n}$ 이다. 이는 uniform distribution(모든 Random Variable의 확률이 같은 분포)일 경우이다.

0 \leq H(x) \leq log_{2}{|\Omega|}

$\bold{\log_{2}({1 \over p_{X}(x)})}$ 의 평균

Entropy를 random variable x의 확률의 역수의 log를 취한 값으로 해석할 수도 있다.

\begin{align*} E[\log_{2}(({1 \over p_{X}(x)})] &= \sum_{x \in X}p_{X}(x)\log_{2}({1 \over p_{X}(x)}) \\ &= -\sum_{x \in X}p_{X}(x)\log_{2}(p_{X}(x)) \\ &= H(p_{X}) \end{align*}

여기서 우리는 $\log_{2}({1 \over p_{X}(x)})$ 을 정보량이라고 정의한다. 식에서도 알 수 있지만, 정보량과 해당 정보량을 얻을 확률은 반비례한다.

Joint, Conditional Entropy

Random Variable이 두 개 이상일 때, 이를 적용할 수 있다. 유도 과정은 $H(X)$ 가 Expectation과 어떤 관계였는지를 떠올려 보면 알 수 있다.

Joint Entropy : $H(X, Y) = -\sum_{x \in \Omega_{X}}\sum_{y \in \Omega_{Y}}p(x, y)\log_{2}p(x, y)$
Conditional Entropy : $H(Y|X) = -\sum_{x \in \Omega_{X}}\sum_{y \in \Omega_{Y}}p(x, y)\log_{2}p(y|x)$

properties

Chain Rule
$H(X, Y) = H(Y|X) + H(X)$
$H(X, Y) = H(X|Y) + H(Y)$
Conditional Entropy's Maximum
$H(Y|X) \leq H(Y)$
독립일 때 같아지며 그 외에는 항상 Conditional의 Entropy가 더 낮다. 의미를 이해하면 쉽다. 한 마디로 X라는 정보가 Y라는 정보가 발생할 확률에 대한 티끌이라도의 힌트를 준다면, 해당 불확실성은 감소하게 되는 것이다.
Joint Entropy's Maximum
$H(X, Y) \leq H(X) + H(Y)$
동일하게 독립일 때 같아지며, 그 외에는 항상 Joint의 Entropy가 더 낮다. 이 또한, 두 사건이 티끌이라도 겹치는 Event가 있다면, 각 Entropy를 더하는 것보다 당연히 작을 수 밖에 없는 것이다.
Concave
Entropy의 그래프는 항상 concave하다.

Coding

정보 이론이 활발하게 사용되는 예시 중에 하나가 바로 데이터의 Encoding/Decoding을 수행하여 bit data로 mapping할 때이다. variable length encoding을 알고 있다면, 이에 대한 이해가 쉬울 것이다. 쉽게 설명하면, 데이터를 bit sequence로 mapping할 때 모든 데이터에게 동일한 bit sequence의 길이만큼을 할당하는 게 아니라 빈도가 높은 데이터부터 짧은 bit sequence 길이를 할당하는 방식이다. 이때 bit sequence의 길이를 Entropy를 이용해서 구할 수 있다. 이 길이는 항상 해당 데이터의 Entropy보다는 커야 한다. 따라서, 해당 Entropy보다 큰 가장 작은 자연수가 해당 데이터의 Bit Sequence 길이의 최적값이다.

KL divergence(Relative Entropy)

Kullback-Leibler Divergence의 약자로, 우리가 구하고자하는 실제 확률(p)과 추측 확률(q) 사이의 오차를 계산할 때 사용하는 지표이다. 따라서, 동일한 Sample Space와 Random Variable에 대한 서로 다른 확률 분포를 비교한다고 생각할 수 있다.

D(p||q) = KL(p||q) = \sum_{x \in \Omega}p(x)\log_{2}(p(x)/q(x)) = E_{p}[\log_{2}({p(x) \over q(x)})]

아쉽게도 KL divergence는 거리와 같은 연산을 적용할 수 없다. 즉, 둘 사이의 역연산은 같지 않을 뿐만 아니라( $D(p||q) \neq D(q||p)$ ), 서로 다른 Random Variable의 KL divergence의 합이 Random Variable의 합의 KL divergence와는 다르다.

Mutual Information

KL divergence를 활용하여 서로 다른 Random Variable X,Y의 연관성을 유추하는 것도 가능하다.

I(X, Y) = D(p(x,y) || p(x)p(y))

$I$ 값이 의미하는 것은 Y를 아는 것이 X의 추측을 얼마나 쉽게하는지에 대한 지표로 작용한다.

증명 과정은 생략하지만, 위의 식을 정리하면 결국은 아래와 같아지기 때문이다.

\begin{align*} I(X, Y) &= H(X) - H(X|Y) \\ &= H(Y) - H(Y|X) \end{align*}

Cross Entropy

우리가 특정 corpus(dataset)를 통해서 확률을 추정했다고 해보자. 그렇다면, 우리는 이 가설을 증명하기 위해서 다른 data에 대해서 해당 추측이 적절한지를 확인하여 정당성을 증명할 수 있다. 그러기 위해서 우리가 만든 확률에서 정보량을 추출하고, 이를 우리가 알고 있는 data의 공간에 넣었을 때의 확률을 추정하기 위해서 Cross Entropy를 사용할 수 있다.

H_{q}(p) = \sum_{x \in \Omega}q(x)\log_{2}{1 \over p(x)}

간단하게 요약하면, 위 식은 틀릴 수 있는 정보를 갖고 구한 최적의 Entropy로, 정보량에 추측 정보량을 넣고, 확률에는 실제 확률을 넣는 방식이다.

또한, 이는 다음과 같이 변형되기도 한다.

H_{q}(p) = H(q) + D(q || p)

또한, 특정 조건이 주어졌을 때의 Conditional Cross Entropy는 다음과 같다.

H_{q}(p) = - \sum_{y \in \Omega_{Y}}\sum_{x \in \Omega_{X}}q(y,x)\log_{2}p(y|x)

하지만, 실제 구현 level에서는 이러한 Cross Entropy를 정석으로 구하는 것은 비용이 크다. 따라서, 이와 근사하는 식을 사용한다.

\begin{align*} H_{q}(p) &= - \sum_{y \in \Omega_{Y}}\sum_{x \in \Omega_{X}}q(y,x)\log_{2}p(y|x) \\ &= {1\over{|T_{Y}|}}\sum_{i=1..|T_{Y}|}{\log_{2}p(y_{i}|x_{i})} \end{align*}

위 식을 이용할 때에는 실제 데이터와 비교에 사용해서는 안된다. 대신 두 개의 서로 다른 p,q가 있을 때, s라는 실제 분포에 어떤 것이 더 적절한지를 판명할 때 사용할 수 있다.

Reference

Tumbnail : Photo by Markus Winkler on Unsplash