Advanced Machine Learning 1 - Preliminaries

Before starting

“Class” 카테고리에 있는 포스팅들은 실제로 수업에서 배운 내용을 정리하려는 목적으로 작성되었다. 이 글은 그 중 Advanced Machine Learning 과목의 수업을 다룬다…만, 오늘 작성할 내용들은 후술할 MLE를 제외하고는 수업 자료만 제공되었다. 해당 자료만 보고 정리한 내용이니 참고할 것.

Probabilities and Distributions

Probability Density Function & Probability Mass Function

함수 $f: \mathbb{R}^D \rightarrow \mathbb{R}$가 다음의 두 조건을 만족하면 이 함수를 확률밀도함수(Probability Density Function, PDF)라고 한다.

1. $\forall x \in \mathbb{R}^D, f(x) \geq 0$
2. $\int_{\mathbb{R}^D} f(x)\, dx = 1$

확률이라는 말이 들어가서 헷갈릴 수 있지만 $f(x) \leq 1$일 필요는 없다. 적분값이 1이기만 하면 된다. 그리고 특정 점 $x$에서의 확률인 $P(X = x) = 0$이다. 오로지 구간 $[a, b]$에서의 확률로만 의미를 가진다. 그리고 이 구간에서의 확률이 다음과 같이 적분으로 정의된다.

\[P(a \leq X \leq b) = \int_a^b f(x)\, dx\]

또한 이산확률변수에서는 적분 대신 sum을 사용하며, 이를 확률질량함수(Probability Mass Function, PMF)라고 한다.

Cumulative Distribution Function

다변량 실수값 확률변수 $X$에서 누적분포함수(Cumulative Distribution Function, CDF) $F_X$는 다음과 같이 정의된다.

\[F_X(x) = P(X_1 \leq x_1, \, \ldots, \, X_D \leq x_D)\]

당연히 단변량이라면 $F_X(x) = P(X \leq x)$로 표현될 것이다.

또한 CDF는 다음과 같이 PDF의 적분으로 표현할 수 있다.

\[F_X(x) = \int_{-\infty}^{x_1} \cdots \int_{-\infty}^{x_D} f(z_1, \ldots, z_D)\, dz_1 \cdots dz_D\]

여기서 “Distribution”이라는 말은 두 가지 다른 의미로 쓰인다.

1. PDF 함수($f(x)$) 자체
2. 확률변수 $X$와 PDF를 연결하는 관계, 즉 $X$의 분포

Sum Rule & Product Rule

우선, 두 확률변수 $x$, $y$에 대해 다음 4가지 분포를 구분해야 한다.

• $p(x, y)$: 결합분포 (joint distribution)
• $p(x), p(y)$: 주변분포 (marginal distribution)
• $p(x \mid y)$: $x$가 주어졌을 때 $y$의 조건부분포 (conditional distribution)
• $p(y \mid x)$: $y$가 주어졌을 때 $x$의 조건부분포

Sum Rule은 결합분포에서 특정 변수를 적분(or 합산)하면 나머지 변수의 주변분포를 얻는다는 법칙이다. Sum Rule은 주변화 법칙(Marginalization Property)라고도 부른다.

\[p(x) = \begin{cases} \sum_{y \in \mathcal{Y}} p(x, y) & \text{if } y \text{ is discrete} \\ \int_{\mathcal{Y}} p(x, y)\, dy & \text{if } y \text{ is continuous} \end{cases}\]

다변량의 경우, $\mathbf{x} = (x_1, \ldots, x_D)^T$에서 $x_i$의 주변분포는 나머지 변수들을 전부 적분하여 얻는다.

\[p(x_i) = \int p(x_1, \ldots, x_D)\, dx_{\setminus i}\]

Product Rule은 결합분포는 조건부분포와 주변분포의 곱으로 분해된다는 법칙이다.

\[p(x, y) = p(y \mid x)\, p(x)\]

변수 순서는 임의적이기 때문에 순서를 바꾼 다음의 공식도 물론 성립한다.

\[p(x, y) = p(x \mid y)\, p(y)\]

그리고 이 둘을 결합해서 생각하면 다음의 전확률 법칙(Law of Total Probability)을 얻을 수 있다.

\[p(x) = \sum_{y \in \mathcal{Y}} p(x, y) = \sum_{y in \mathcal{Y}} p(x \mid y)\, p(y)\]

Bayes’ Rule

머신러닝은 알고리즘으로는 설명하기 어려운 데이터 간의 상관관계를 이어주는 학문이기 때문에 관측되지 않은 잠재변수(latent variable)에 대해 추론하는 것이 중요하다.

다음과 같은 상황을 생각해보자.

$X$를 메일에 특정 단어가 포함되었는지의 여부로, $Y$를 메일의 스팸 여부라고 정의하자. 우리는 이미 $P(X)$(전체 메일 중 특정 단어가 등장하는 비중), $P(Y)$(전체 메일 중 스팸의 비중), 그리고 $P(X|Y)$(스팸 메일 중 특정 단어가 등장하는 비중)을 알고 있다. 이 상황에서 특정 단어 $x$가 등장한 메일이 스팸인지를 알고 싶다. 이 값은 $P(Y = 1 \mid X = x)$로 표기할 수 있으며, 이를 Bayes’ Rule을 사용해 계산할 수 있다.

Bayes’ Rule은 다음과 같이 쓸 수 있다.

\[p(y \mid x) = \frac{p(x \mid y)\, p(y)}{p(x)}\]

여기서 각 항의 의미는 다음과 같다.

• $p(y)$ (Prior): 관측 전 $y$에 대해 갖고 있던 지식
• $p(x \mid y)$ (Likelihood): $y$를 안다고 가정했을 때 $x$가 나올 확률
• $p(y \mid x)$ (Posterior): $x$를 관측한 후 $y$에 대해 알 수 있는 것
• $p(x)$ (Evidence): 정규화 상수. $p(x) = \int p(x \mid y)\, p(y)\, dy$

이제 원래의 스팸 메일 문제로 돌아가서, “Rolex”라는 단어가 스팸 메일 2000통 중 250통, 정상 메일 1000통 중 5통에 등장하며 스팸/정상 확률이 동일하다고 할 때, “Rolex”라는 단어가 들어가는 메일을 스팸일 확률을 계산해보자.

메일이 스팸일 확률과 아닐 확률은 동일하댔으므로 $P(Y = 0) = P(Y = 1) = 0.5$다. 또한 $p = P(X = 1 \mid Y = 1) = 250/2000$, $q = P(X = 1 \mid Y = 0) = 5/1000$이다. 이 때 우리가 알고자 하는 확률은 $P(Y = 1 \mid X = 1)$이며, 이는 다음과 같이 구할 수 있다.

\[P(Y = 1 \mid X = 1) = \frac{p \cdot \frac{1}{2}}{p \cdot \frac{1}{2} + q \cdot \frac{1}{2}} = \frac{0.125}{0.125 + 0.005} \approx 0.962\]

즉, 96.2%의 확률로 스팸메일일 것이다.

Maximum Likelihood Estimator

동전을 던져서 $D = {H, T, T, H, H, H, T, T, T, T}$를 얻었을 때, 앞면이 나올 확률 $P(H)$를 어떻게 추정할까? 직관적으로 보면 $P(H) = n_H / (n_H + n_T) = 0.4$지만, 이것이 수학적으로도 옳은지를 확인해보자.

최대 우도 추정(Maximum Likelihood Estimator, MLE)은 주어진 데이터 $D$에 대해, 데이터가 나올 확률 $P(D;\theta)$를 최대화하는 $\theta$를 추정값으로 삼는 방법이다.

\[\hat{\theta} = \arg\max_{\theta} P(D;\theta)\]

아까의 동전 문제로 돌아가보자. 동전 던지기는 이항분포로 모델링할 수 있기 때문에 $P(H) = \theta$, $P(T) = 1-\theta$가 된다. 따라서, 우리가 원하는 상황이 나올 확률은 다음과 같다.

\[P(D;\theta) = \binom{n_H + n_T}{n_H} \theta^{n_H} (1-\theta)^{n_T}\]

로그는 단조증가함수이므로 여기서 로그를 취해도 최댓값의 위치는 변하지 않는다.

\[\begin{aligned} \hat{\theta} &= \arg\max_{\theta}\log\binom{n_H+n_T}{n_H} \theta^{n_H} (1-\theta)^{n_T} \\ &= \arg\max_{\theta} \left[ \log\binom{n_H+n_T}{n_H} + n_H \log\theta + n_T \log(1 - \theta) \right] \end{aligned}\]

이 값이 최대가 되는 $\theta$를 구하기 위해선, 위의 식을 미분하여 0이 되는 값을 찾으면 된다.

\[\frac{\partial}{\partial\theta} \log P(D;\theta) = \frac{n_H}{\theta} - \frac{n_T}{1-\theta} = 0\] \[\therefore \hat{\theta} = \frac{n_H}{n_H + n_T}\]

이로써 위의 직관적인 추정값과 일치함을 알 수 있다.

Expected Value

연속 확률변수 $X ~ p(x)$에 대한 함수 $g: \mathbb{R} \rightarrow \mathbb{R}$의 기댓값(Expected Value)은 다음과 같다.

\[\mathbb{E}_X[g(x)] = \int_{x \in \mathcal{X}} g(x)\, p(x)\, dx\]

만일 이산 확률변수라면 다음과 같이, 적분 대신 sum으로 표현된다.

\[\mathbb{E}_X[g(x)] = \sum_{x \in \mathcal{X}} g(x)\, p(x)\]

만일 $X = (X_1, \ldots, X_D)^T$인 다변량 확률변수라면, 기댓값은 다음과 같이 각 원소별로 정의된다.

\[\mathbb{E}_X[g(x)] = \begin{pmatrix} \mathbb{E}_{X_1}[g(x_1)] \\ \vdots \\ \mathbb{E}_{X_D}[g(x_D)] \end{pmatrix} \in \mathbb{R}^D\]

참고로, 기댓값은 선형 연산이다. 만일 $f(x) = ag(x) + bh(x)$라면 다음과 같이 계산할 수 있다.

\[\begin{aligned} \mathbb{E}_X[f(x)] &= \int f(x)\, p(x)\, dx \\ &= \int (ag(x) + bh(x))\, p(x)\, dx \\ &= a\int g(x)\, p(x)\, dx + b\int h(x)\, p(x)\, dx \\ &= a\, \mathbb{E}_X[g(x)] + b\, \mathbb{E}_X[h(x)] \end{aligned}\]

평균(Mean)은 위의 기댓값에서 $g$를 항등함수로 선택한 특별한 케이스이다.

\[\mathbb{E}_X[x] = \begin{pmatrix} \mathbb{E}_{X_1}[x_1] \\ \vdots \\ \mathbb{E}_{X_D}[x_D] \end{pmatrix} \in \mathbb{R}^D\]

Covariance

두 단변량 확률변수 $X, Y \in \mathbb{R}$의 공분산(Covariance)은 각각의 평균으로부터의 편차의 곱에 대한 기댓값으로 정의된다.

\[\text{Cov}_{X, Y}[x, y] = \mathbb{E}_{X, Y}\left[(x - \mathbb{E}_{X}[x])(y - \mathbb{E}_{Y}[y])\right]\]

기댓값의 선형성을 이용하면 이는 다음과 같이 정리할 수 있다.

\[\text{Cov}_{X, Y}[x, y] = \mathbb{E}_{X, Y}[xy] - \mathbb{E}_X[x]\, \mathbb{E}_Y[y]\]

그리고 이 때, 변수 자신과의 공분산을 의미하는 $\text{Cov}_{X, X}[x, x]$를 분산(Variance)이라고 하며, $\mathbb{V}_X[x]$로 표기한다. 분산의 제곱근은 표준편차이며, $\sigma(x)$로 표기한다.

$x \in \mathbb{R}^D$, $y \in \mathbb{R}^E$인 다변량일 경우, 공분산은 다음과 같이 행렬로 정의된다.

\[\text{Cov}[x,y] = \mathbb{E}\left[(x - \mathbb{E}[x])(y - \mathbb{E}[y])^T\right] = \mathbb{E}[xy^T] - \mathbb{E}[x]\mathbb{E}[y]^T = \text{Cov}[y,x]^T\]

이 때, 당연히 $\text{Cov}[x,y] \in \mathbb{R}^{D \times E}$이다.

마지막으로 $x \in \mathbb{R}^D$, 평균벡터 $\mu \in \mathbb{R}^D$에 대해, 다변량 공분산 행렬 $\mathbb{V}_X[x]$는 다음과 같이 정의된다.

\[\begin{aligned} \mathbb{V}_X[x] &= \text{Cov}_X[x,x] \\ &= \mathbb{E}_X[(x-\mu)(x-\mu)^T] = \mathbb{E}_X[xx^T] - \mathbb{E}_X[x]\mathbb{E}_X[x]^T \\ &= \begin{pmatrix} \text{Cov}_{X_1,X_1}[x_1,x_1] & \cdots & \text{Cov}_{X_1,X_D}[x_1,x_D] \\ \vdots & & \vdots \\ \text{Cov}{X_D,X_1}[x_D,x_1] & \cdots & \text{Cov}_{X_D,X_D}[x_D,x_D] \end{pmatrix} \end{aligned}\]

이 행렬은 symmetric이고, positive semidefinite이며, 데이터가 얼마나 퍼져 있는지를 나타낸다.

Empirical Mean & Covariance

이론적인 통계량(population statistics)과는 달리, 머신러닝에서는 유한한 데이터로부터 통계량을 추정해야 한다. 그래서 경험적인 통계량을 계산해야 한다.

경험적 평균 벡터(Empirical Mean Vector)는 각각의 변수들에 대한 관측값의 산술평균으로 정의된다.

\[\bar{x} := \frac{1}{N} \sum_{n=1}^{N} x_n, \quad x_n \in \mathbb{R}^D\]

비슷하게, 경험적 공분산 행렬(Empirical Covariance Matrix)는 다음과 같은 $D \times D$ 행렬로 정의된다.

\[\Sigma := \frac{1}{N} \sum_{n=1}^{N} (x_n - \bar{x})(x_n - \bar{x})^T\]

Gaussian Distribution

평균 $\mu$, 분산 $\sigma^2$인 단변량 가우시안 분포의 밀도함수는 다음과 같다.

\[p(x \mid \mu, \sigma^2) = \frac{1}{\sqrt{2\pi\sigma^2}} \exp\!\left(-\frac{(x-\mu)^2}{2\sigma^2}\right)\]

다변량의 경우, 가우시안 분포는 평균 벡터 $\mu$와 공분산 행렬 $\Sigma$로 정의된다.

\[p(x \mid \mu, \Sigma) = (2\pi)^{-D/2} |\Sigma|^{-1/2} \exp\!\left(-\frac{1}{2}(x-\mu)^T \Sigma^{-1} (x-\mu)\right)\]

그리고 이 $p(x) = \mathcal{N}(x \mid \mu, \Sigma)$ 혹은 $X \sim \mathcal{N}(\mu, \Sigma)$라고 표기한다.

특별한 케이스로, $\mu = 0$, $\Sigma = 1$이면 이를 표준정규분포라고 한다.

Linear Algebra - Projection

고차원의 데이터는 분석하거나 시각화하기가 어렵다. 그러나 이 고차원의 데이터 중에서도 핵심 정보는 소수의 차원에 집중되어 있는 경우가 많다. 그렇기 때문에 핵심 데이터를 보존하면서 분석 및 시각화에 용이한 저차원으로 데이터를 정보 손실을 최소화하며 압축을 시도하며, 이를 투영(Projection)이라고 한다.

1차원 부분공간으로의 투영

원점을 지나는 직선(1D 부분공간 $U$)의 기저벡터를 $b \in \mathbb{R}^n$이라 하자. 이 때, $x \in \mathbb{R}^n$을 $U$에 투영한 벡터 $\pi_U(x) \in U$는 $x$와 가장 가까운 $U$ 위의 점이 된다. 그리고 $\pi_U(x)$는 다음 성질을 만족한다.

• $\pi_U(x)$는 $b$의 스칼라배가 된다. 즉, $\pi_U(x) = \lambda b$
• 오차벡터 $x - \pi_U(x)$는 $b$에 수직이다. 즉, $\langle x - \pi_U(x), b\rangle = 0$

그럼 이제 Projection을 구하는 방법을 알아보자.

① 좌표 $\lambda$ 구하기

직교 조건인 $\langle x - \lambda b, b\rangle = 0$에서부터 다음을 얻을 수 있다.

\[\lambda = \frac{\langle b, x \rangle}{\langle b, b \rangle} = \frac{b^T x}{\|b\|^2}\]

② 투영점 $\pi_U(x)$ 구하기

\[\pi_U(x) = \lambda b = \frac{b^T x}{\|b\|^2}b\]

만약에 내적으로 dot product를 사용하면, $|\pi_U(x)| = \cos\omega\,|x|$가 된다. 여기서 $\omega$는 $x$와 $b$의 각도이다.

③ 투영 행렬 $P_{\pi}$ 구하기

투영은 선형변환이므로 $\pi_U(x) = P_{\pi}$를 만족하는 투영 행렬 $P_{\pi}$가 존재한다.

\[P_{\pi} = \frac{bb^T}{\|b\|^2}\]

여기서 $bb^T$는 rank가 1인 대칭 행렬이 된다.

일반 부분공간으로의 투영

이제 위의 고찰을 확장해서 생각해보자. $U \in \mathbb{R}^n$의 차원이 $m \geq 1$이고, 순서 기저가 $b_1, b_2, \ldots, b_m$일 때를 가정하자.

투영은 $U$의 원소이므로 각 기저의 선형결합으로 표시할 수 있다.

\[\pi_U(x) = \sum_{i=1}^m \lambda_i b_i = B\lambda\]

여기서 $B = [b_1, \ldots, b_m] \in \mathbb{R}^{n \times m}$, $\lambda = [\lambda_1, \ldots, \lambda_m]^T \in \mathbb{R}^m$

아까의 3단계를 그대로 적용해보자.

① 좌표 $\lambda$ 구하기

오차벡터가 모든 기저벡터에 수직이어야 한다.

\[B^T(x - B\lambda) = 0 \rightarrow B^T B\lambda = B^T x\]

이를 normal equation이라고 한다. 만일 $B$가 full rank라면 $B^T B$는 가역이므로

\[\lambda = (B^T B)^{-1}B^T x\]

여기서 $(B^T B)^{-1}B^T$를 $B$의 pseudo-inverse라고 부른다.

② 투영점 $\pi_U(x)$ 구하기

\[\pi_U(x) = B\lambda = B(B^T B)^{-1}B^T x\]

③ 투영 행렬 $P_{\pi}$ 구하기

\[P_{\pi} = B(B^T B)^{-1}B^T\]

Calculus

Derivative

• Product rule: $(f(x)g(x))’ = f’(x)g(x) + f(x)g’(x)$
• Quotient rule: $\left(\dfrac{f(x)}{g(x)}\right)’ = \dfrac{f’(x)g(x) - f(x)g’(x)}{(g(x))^2}$
• Sum rule: $(f(x)+g(x))’ = f’(x) + g’(x)$
• Chain rule: $(g(f(x)))’ = g’(f(x))f’(x)$

Partial Differentiation and Gradients

함수 $f$가 여러 변수에 의존하는 경우 ($f: \mathbb{R}^n \to \mathbb{R}$), 도함수의 일반화를 Gradient라고 한다. Gradient는 한 번에 하나의 변수만 변화시키고 나머지를 고정하여 각각의 변수에 대한 도함수를 계산한 후, 이들을 모은 형태로 구한다.

$n$개의 변수 $x_1, \ldots, x_n$을 가지는 함수 $f: \mathbb{R}^n \to \mathbb{R}$의 편미분은 다음과 같이 정의된다.

\[\frac{\partial f}{\partial x_i} = \lim_{h \to 0} \frac{f(x_1, \ldots, x_i + h, \ldots, x_n) - f(x)}{h}\]

그리고 이런 편미분들을 모아서 행벡터로 표기한 것을 Gradient라고 정의한다.

\[\nabla_x f = \text{grad}\, f = \frac{df}{dx} = \left[\frac{\partial f(x)}{\partial x_1},\; \frac{\partial f(x)}{\partial x_2},\; \ldots,\; \frac{\partial f(x)}{\partial x_n}\right] \in \mathbb{R}^{1 \times n}\]

편미분에서는 기본적으로 다음의 법칙들이 성립한다.

• Product rule: $\dfrac{\partial}{\partial x}\left(f(x)g(x)\right) = \dfrac{\partial f}{\partial x}g(x) + f(x)\dfrac{\partial g}{\partial x}$
• Sum rule: $\dfrac{\partial}{\partial x}\left(f(x)+g(x)\right) = \dfrac{\partial f}{\partial x} + \dfrac{\partial g}{\partial x}$
• Chain rule: $\dfrac{\partial}{\partial x}\left(g(f(x))\right) = \dfrac{\partial g}{\partial f}\dfrac{\partial f}{\partial x}$

Chain Rule

위의 법칙들 중 Chain rule에 대해 좀 더 살펴보자.

만일 $f(x_1, x_2)$에서 $x_1(t)$, $x_2(t)$가 $t$의 함수일 때 $f$의 $t$에 대한 Gradient는 다음과 같이 정리되며, 이는 Chain rule을 사용한 것이다.

\[\nabla_t f = \frac{df}{dt} = \begin{bmatrix}\dfrac{\partial f}{\partial x_1} & \dfrac{\partial f}{\partial x_2}\end{bmatrix}\begin{pmatrix}\dfrac{\partial x_1(t)}{\partial t}\\\dfrac{\partial x_2(t)}{\partial t}\end{pmatrix} = \frac{\partial f}{\partial x_1}\frac{\partial x_1}{\partial t} + \frac{\partial f}{\partial x_2}\frac{\partial x_2}{\partial t}\]

위의 상황을 조금 더 확장하여, 만일 $f(x_1, x_2)$에서 $x_1(s, t)$, $x_2(s, t)$가 각각 두 변수 $s$, $t$의 함수라면 $s$, $t$에 대한 $f$의 Gradient는 다음과 같이 정리된다.

\[\frac{df}{d(s,t)} = \frac{\partial f}{\partial x} \cdot \frac{\partial x}{\partial (s,t)} = \begin{bmatrix}\dfrac{\partial f}{\partial x_1} & \dfrac{\partial f}{\partial x_2}\end{bmatrix} \begin{pmatrix}\dfrac{\partial x_1}{\partial s} & \dfrac{\partial x_1}{\partial t}\\\dfrac{\partial x_2}{\partial s} & \dfrac{\partial x_2}{\partial t}\end{pmatrix}\]

주목할 점은, 이 형태가 행렬의 곱으로 표시된다는 점이다. 이는 역전파의 수학적 기반이 된다.

Useful Identities for Computing Gradients

① $\dfrac{\partial x^T a}{\partial x} = \dfrac{\partial a^T x}{\partial x} = a^T \in \mathbb{R}^{1 \times n}$

Proof:

\[\frac{\partial x^T a}{\partial x} = \left[\frac{\partial (x_1 a_1 + \cdots + x_n a_n)}{\partial x_1}, \ldots, \frac{\partial (x_1 a_1 + \cdots + x_n a_n)}{\partial x_n}\right] = [a_1, \ldots, a_n] = a^T\]

② $\dfrac{\partial x^T Bx}{\partial x} = x^T(B + B^T)$

Proof: ①의 결과를 활용한다.

\[\frac{\partial x^T Bx}{\partial x} = (Bx)^T + x^T\frac{\partial Bx}{\partial x} = (Bx)^T + x^TB = x^T(B + B^T)\]

③ $\dfrac{\partial(x-As)^TW(x-As)}{\partial s} = -2(x - As)^TWA$ for symmetric W

Proof: ①, ①의 결과를 활용한다.

먼저, $(x-As)^TW(x-As)$를 Associative rule을 활용하여 전개한다.

\[(x-As)^TW(x-As) = x^TWx - x^TWAs - s^TA^TWx + s^TA^TWAs\]

그 후, 각 항을 미분한다. 각각의 항별로 미분한 결과는 다음과 같다.

• $\dfrac{\partial x^TWx}{\partial s} = 0$ ($s$에 무관한 항)
• $\dfrac{\partial x^TWAs}{\partial s} = x^TWA$
• $\dfrac{s^TA^TWx}{\partial s} = x^TW^TA$
• $\dfrac{s^TA^TWAs}{\partial s} = s^T(A^TWA + A^TW^TA)$

$W = W^T$이므로 위 항들을 모두 더하면 다음과 같다.

\[(x-As)^TW(x-As) = -2x^TWA + 2s^TA^TWA = -2(x - As)^TWA\]

④ $\dfrac{\partial a^TXb}{\partial x} = ab^T$

미분 대상이 벡터가 아니라 행렬 $X$임에 주의하자.