Saito et al, Maximum Classifier Discrepancy for Unsupervised Domain Adaptation, CVPR 2018에 대한 간단한 리뷰

기존 DANN을 이용한 Domain adaptation의 문제점

기존 DANN은 Feature Generator $G$, 그리고 generated 된 feature가 source / target 중 어느 데이터에서 추출된 것인지를 구별하는 classifier $F$를 바탕으로 적대적 학습을 진행한다. 기존의 문제는, 모델 방식이 Source와 Target의 Feature 공간을 맞추는 데에 너무 집중한 나머지, Label boundary를 고려하지 못했다는 데에 있다.

예를 들어, Label classifier 를 Source domain에서 학습을 시키고, adaptation을 통해서 target sample을 source domain에 가깝게 했다. 그렇다고 해서, target sample이 올바르게 분류된다는 보장은 없다.

이러한 문제점을 해결하고자, 본 논문에서는 두 개의 label classifier을 이용한 새로운 방법론을 제시한다.

Proposed Method

두괄식으로, 먼저 제안된 방법론 먼저 제시한 후, 이에대한 직관적 설명과 이론적인 설명을 덧붙이도록 한다.

Discrepancy Loss 논문에서 두 분포 간의 discrepancy는 다음과 같은 식으로 정의한다(L1 distance) 이러한 정의는 후술할 이론적 내용과 연관이 있다. 추가적으로, L2거리를 loss로 정의하면 잘 작동하지 않는다고 한다.(경험적으로)

$d(p_1, p_2) = \frac{1}{K}\sum_k|p_{1k} - p_{2k}|$

Step A 우선 Sample domain에 대하여 두 개의 classifier $F_1, F_2$와 $G$를 train 한다.

$\min_{G, F_1, F_2} \mathcal{L}(X_s, Y_s)$ where $\mathcal{L}(X_s, Y_s) = -E_{(x,y) \sim (X_s, Y_s)}\sum_k1_{k = y_s}\log p(y|x_s)$

논문의 main idea인 두 개의 classifier을 사용하기 위해서는, 일단 이들이 sample domain에 대해서는 잘 작동해야 한다.

Step B

Feature Generater $G$를 고정시키고, $F_1, F_2$의 판별 discrepancy를 최대화 시킨다.

$\min_{F_1, F_2}\mathcal{L}(X_s, Y_s) - \mathcal{L}{adv}(X_t)$ where $\mathcal{L}{adv}(X_t) = E_{x_t \sim X_t}(d(p_1(y|x_t),p_2(y|x_t))$

위의 그림을 참고하여 이게 무슨 말인지 설명해보면, 두 label을 잘 분류하는 두 label classifier에 대하여, 이들의 target에 대한 분류 discrepancy가 최대가 된다는 것은 $F_1, F_2$의 decision boundary가 sample 데이터의 각 label(0,1)에 해당하는 경계에 가깝게 형성된다는 직관을 이용한 것이다.

Step C

$F_1, F_2$를 고정시키고 $G$를 위에서 구한 discrepancy가 최소화되도록 학습시킨다.

$\min_{G}\mathcal{L}_{adv}(X_t)$

그렇다면, sample support에서 벗어나서 위치한 target data에 대하여 feature generator는 이들의 분포를 sample support로 이동시키려고 할 것이다.

이후 step B,C를 반복함으로써 model에 대한 update가 지속적으로 이루어진다

Target label에 맞춰 해당하는 classifier의 경계로 이동한다는 보장이 어디있는가?

$F_1, F_2$가 고정되어 있을 때, sample support에서 떨어져있는 target sample $x_t$가 Generator의 update를 통하여 두 경계($F_1, F_2$) 중 더 가까운 경계로 이동할까?

-> 그럴 것이다. 경계와의 거리와 $p(y|x_t)$는 밀접한 관련이 있는 개념이기 때문에, 최대한 빨리 discrepancy를 최소화 하기 위해서는 target data가 가장 가까운 경계로 이동해야 할 것이다.

Theoretical Insight

저자들은 다음과 같은 domain adaptation theorem에서 본 방법론의 아이디어를 떠올렸다고 한다.

여기서 $\mathcal{H}$를 sample data를 잘 분류하는 classifier들의 집합으로 생각하자.

우리의 모델 하에서, $h = F_1(G)$, $h' = F_2(G)$의 합성함수 형태로 표현이 가능하다.

또한, sample data를 $F_1, F_2$가 잘 분류한다는 가정 하에서, $d_{\mathcal{H}\Delta\mathcal{H}}$ 의 첫번째 항은 0에 가깝게 된다.

즉, Theorem 1의 upper bound를 줄이기 위해서는 $\sup_{F_1, F_2} E_{x\sim\mathcal{T}}I(F_1(G(x)) \neq F_2(G(x)))$를 를 minimize 시켜는 target domain을 선택해야 하고, 이는 다음과 같이 표현 할 수 있다. $\min_G\sup_{F_1, F_2} E_{x\sim\mathcal{T}}I(F_1(G(x)) \neq F_2(G(x)))$

이 식이 우리가 이 논문에서 제시된 방법론과 일맥상통하는 부분이 있음을 알 수 있다.

이 포스트는 Bernamou et al.(2015), Iterative Bregman Projections for regularized transportation problems, SIAM 논문의 초반부를 읽고 참고한 것이다.

Optimal transport 문제에서 optimal coupling을 찾는 것은 많은 컴퓨팅을 필요로 하고, iterative bregman projection을 기반으로 한 sinkhorn algorithm 등이 많이 쓰인다. 이 포스팅에서는 iterative bregman projection의 entropic OT regularization에 대하여 설명한다.

Entropic OT problems

OT 문제에서 목적함수로 우리는 주로 entropic regularization을 고려한다.

$$\arg\min_{\gamma \in \Pi(\mu, \nu)}<\gamma, C>{\mathcal{F}} + \epsilon H(\gamma)$$, where $H(\gamma) = \sum{ij}\gamma_{ij}log{\gamma_{ij}}$

이러한 entropic regularization term은 $\gamma$의 non-sparsity(smoothness)를 유도한다.

하지만 이와 더불어, solution을 구하는 데에 있어 추가적인 이점을 주기 때문에 많이 쓰이는 것도 있다.

우선, 위의 Loss는 entropy term이 추가됨으로써, strongly convex하게 된다. 즉, unique minimizer $\gamma^*$가 존재한다.

이 때 제약조건 $\gamma \in \Pi(\mu, \nu)$ 가 없는 경우를 고려하면, $\gamma^* = e^{-\frac{C}{\epsilon}}$ 임을 구할 수 있다.

위의 최적화 문제를 약간 다른 관점에서 생각해보자.

"위의 최적화 문제의 해는 제약조건이 없는 경우의 해 $\gamma^*$를 벡터공간 $\mathcal{S} = {\gamma | \gamma \in \Pi(\mu, \nu)}$ 에 KL divergence에 대하여 projection 한 것이다."

즉, 위의 최적화 문제는 다음과 같이 쓸 수 있다.

$$\arg\min_{\gamma \in \Pi(p,q)}KL(\gamma|\xi)$$ where $\xi = e^{-\frac{C}{\epsilon}}$

왜 이와 같이 표현될 수 있는가 하면,

$KL(\gamma|\xi) = \sum_{ij}\gamma_{ij}log\frac{\gamma_{ij}}{e^{-\frac{C}{\epsilon}}} =\sum_{ij}\gamma_{ij}log\gamma_{ij} + \frac{1}{\epsilon}\sum_{ij}\gamma_{ij}C_{ij} =H(\gamma)+\frac{1}{\epsilon}<\gamma, C>_{\mathcal{F}}$ 이기 때문이다.

이제 다음과 같은 projection을 정의하자. $P_\mathcal{C}^{KL}(\xi) := \arg\min_{\gamma \in \mathcal{C}}KL(\gamma|\xi)$

이러한 projection의 해를 구하는 방법이 Iterative Bregman projection이다.

Iterative Bregman Projection

Setting

Iterative Bregman projection에서는 다음의 상황을 다룬다.

$\min_{\gamma \in \mathcal{C}}KL(\gamma|\xi))$ where $\xi$ is a given point in $R_+^{N \times N}$ , and $\mathcal{C}$ is a intersection of closed convex sets $$\mathcal{C} = \cap_{\mathcal{l}= 1}^L \mathcal{C}l$$ s.t. $\mathcal{C}$ has nonempty intersecton with $R+^{N \times N}$. 추가적으로, set $\mathcal{C}l$의 index의 확장을 위해 $\forall n \in N, \mathcal{C}{n+L} = \mathcal{C}_n$이라고 한다. 이는 지속적인 iteration을 위함이다.

Iterative Bregman Projections

(이하 IBP)

구하고자 하는 최적화 문제의 해는 아래의 알고리즘을 통해 구할 수 있다

이 때 $C_l$은 convex affine subspace이다.

1. Let $\gamma^{(0)} = \xi$
2. define $\forall n > 0, \gamma^{(n)} = P_{C_n}^{KL}(\gamma^{(n-1)})$
   Then, $\gamma^{(n)} \rightarrow P_{C}^{KL}(\xi)$ as $n \rightarrow \infin$

Dykstra's Algorithm

이 때 $C_l$이 affine subspace이 아니라면, 수정된 버전인 Dykstra's algorithm을 사용해야 한다.

Solving entropic OT problem via iterative bregman projection

위의 IBP를 그래도 entropic ot 문제를 푸는 데 적용 할 수 있다.

이는 $\xi$를 $C_1 = {\gamma ; \gamma 1 = p}$, $C_2 = {\gamma \in \gamma^T = q}$의 intersection 위에 projection 하는 것이고, 이 때 $C_1, C_2$는 모두 convex affine subspace임으로, 그대로 적용이 가능하다

참고로, $P_{C_1}^{KL}(\gamma) = diag(\frac{p}{\bar\gamma 1})\bar\gamma$, $P_{C_2}^{KL}(\gamma) = \bar\gamma diag(\frac{q}{\bar\gamma^T 1})$ 로 계산된다.

• 기존의 optimal transport for unsupervised DA 방법론들은 label을 제외한 source sample X만을 transport 시키고 있음
• 이러한 방법론들은 다음의 conditional distribution에 대한 성질이 성립함을 함축적으로 가정함. 즉,$P_s(Y|\mathcal{T}(X)) = P_t(Y|X)$
  • $\mathcal{T}$는 OT mapping of sample
  • $\hat{P_t}(Y|X_t) = Model(Y|\mathcal{T}(X_s)) \sim P_S(Y|T(X_s))$ <- 기존의 OT 방법이 성립하려면 이 가정을 따라야만 합리적임.
• 다만, 기존의 OT mapping 에서는 이 가정이 굳이 성립해야 할 특별한 이유는 없음
• Proposal : Source와 Target의 결합분포를 Transport 시킨다: ㄴ 이렇게 하면 위의 문제점이 해결 되는가??? ㄴ Target의 label 정보를 우리가 모르기 때문에 문제가 되고, 해결방안을 제시하고 있음.

JDOT

Kantorovich formulation을 응용하면, 제안하는 방식은 다음과 같은 식으로 나타내어진다.

$$\gamma_0 = \arg\min_{\gamma \in \Pi(\mathcal{P}s, \mathcal{P}_t)} \int{(\Omega \times \mathcal{C})^2} \mathcal{D}(x_1, y_1; x_2, y_2)d\gamma(x_1, y_1;x_2, y_2)$$ where $\mathcal{D}(x_1, y_1; x_2, y_2) = \alpha d(x_1, x_2) + \mathcal{L}(y_1, y_2)$

위 식의 해(최적의 $\gamma$)는 $\mathcal{D}$가 lower-semi continuous 일 때 존재함이 알려져 있다. (Supp. A 참고) 이 상황은 $d$가 norm이고 $\mathcal{L}$이 일반적 loss일때 만족된다.

문제는, target data의 label은 우리가 알 수 없다는 점인데, 우리의 목적은 target data에 대하여 잘 동작하는 classifier f를 찾는 것이라는 것을 상기하자. 이를 이용하여, target의 label $y_t \sim f(x_t)$로 근사시키자.(아마 f는 sample 분포에서 학습된 classifier일 것이다). 그리고 근사된 joint distribution $\mathcal{P}_t^f = (X_t, f(X_t))$ 로 적도록 하자.

위의 문제를 empirical distribution과 $\mathcal{P}t^f$에 대하여 다시 쓰면 $$\min{f, \gamma} \sum_{ij} \mathcal{D}(x_i^s, y_i^s; x_t^s, f(x_t))\gamma_{ij} = \min W(\mathcal{P_s}, \mathcal{P_t^f})$$.

현실에서는, f의 overfitting 방지를 위해 f에 추가적인 제약조건이 걸리기도 한다.

Comparison with other OT based DA methods

• JDOT에서는 굳이 barycentric mapping을 찾을 필요가 없음 ㄴ 직접 f를 구하려고 시도하기 때문. ㄴ barycentric mapping은 두 분포 사이에 wasserstein distance를 근사적으로 줄일 뿐이므로, 이론적 배경이 JDOT에 비해 부족함

A bound on the target error

JDOT를 통해 구해진 f에 대한 이론적 성질을 보인다.

Notation $f \in \mathcal{H}$ : hypothesis in hypothesis space $err_T(f) = E_{(x,y) \sim P_t}(\mathcal{L}(y,f(x)))$

Assumption $\mathcal{L}$은 Bounded, symmetric, k-lipschitz이며 triagular ineq.을 만족함을 가정

또한, 기존 lipschitz 조건의 확장인 probabilistic lipschitz라는 개념을 도입한다.

f가 prob.libschitzness를 만족한다는 것은, 가까운 두 객체가 비슷한 함수값을 높은 확률로 가진다는 것을 모델링 할 수 있다.

Main theorem

(증명은 supp.B에 적어둔다) 의미를 해석해보자.

• $f \in \mathcal{H}$는 임의의 labeling function.
• $\Pi^*$는 $\mathcal{P}_s, \mathcal{P}_t^f$ 사이의 optimal coupling.
• $f^$는 다음 조건 만족 ㄴ Lipschitz labeling function ㄴ $\Pi^$에 대해$\phi$ probabilistic transfer lipschitzness 만족 ㄴ 위 조건 만족시키는 f 중 $err_s(f^) + err_T(f^)$를 최소화시킴 ㄴ $\forall x_1, x_2, |f(x_1) - f(x_2)| \leq M$ for some $M >0$
• $\mathcal{L}$ : symmetric, k-lipschitz, satifies triangle ineq.

즉, $W_1(\hat\mathcal{P}_s, \hat\mathcal{P}_t^f)$를 최소화함으로서, $err_T(f)$가 작아진다는 의미이다.

Learning with JDOT

다음과 같은 setting을 고려한다

• $f \in \mathcal{H}$는 RKHS or Parameterized 될 수 있는 함수들의 집합이다. ㄴ 이러한 함수 클래스는 linear model, NN, kernel methods 등을 포함함.
• regularization term $\Omega(f)$ ㄴ 주로 squared norm 에 대한 비감소 함수.
• 추가적으로 $\gamma$에 대한 regularization도 생각할 수 있다 ㄴ entropic / group-lasso...
• $\mathcal{L}$은 continuous / differentiable

풀어야 하는 최적화 문제는 다음과 같다.

$$\min_{f \in \mathcal{H}, \gamma \in \Delta}\sum_{i,j}\gamma_{ij}(\alpha d(x_s^i, x_t^j) + \mathcal{L}(y_s^i, f(x_t^j)) + \lambda\Omega(f)$$

Optimization procedure

• $\gamma$ 와 $f$에 대해서 따로따로 최소화시키는 것이 가장 일반적인 방법이다 ㄴ Block Coordinate Descent(BCD) or Gauss-Seidel Method

• $f$ 가 고정되어 있는 경우, 이는 classical OT문제가 되며 ㄴ network simplex algorithm / regularized OT / stochastic OT.. 등으로 풀 수 있다.

• $\gamma$ 가 고정되어 있는 경우, $$\min_{f \in \mathcal{H}, \gamma \in \Delta}\sum_{i,j}\gamma_{ij} \mathcal{L}(y_s^i, f(x_t^j)) + \lambda\Omega(f)$$ 와 같은 식을 최적화 하는 문제 ㄴ $N_sN_t$개의 항을 가지므로 computationally expensive ㄴ Loss를 잘 고르면 complexity 줄일 수 있다.(추후 설명) ㄴ$\mathcal{H}$ 가 RKHS일 때, represeneter theorem에 의하면, 위와 같은 최적화 문제의 해는 $f^* = \sum_i^{N_t}\alpha_i K(x_i, x)$의 형태로 표현되고, 즉 $N_t$개의 parameter을 최적화시키는 문제가 된다. ㄴ 2-block Gauss-Seidel method로 최적화 가능하다고 한다.

Supplementary materials

A. optimal $\gamma_0$의 존재성

$$\gamma_0 = \arg\min_{\gamma \in \Pi(\mathcal{P}s, \mathcal{P}_t)} \int{(\Omega \times \mathcal{C})^2} \mathcal{D}(x_1, y_1; x_2, y_2)d\gamma(x_1, y_1;x_2, y_2)$$

B. Proof of the main theorem

(업데이트 예정)

본 논문 optimal transport for domain adaptation 에서는, optimal transport를 이용한 도메인 적응 문제의 formulation, 그리고 계산을 위한 알고리즘을 소개하고 있다.

Domain adaptation?

도메인 적응 문제는 다음과 같은 상황에서 일어난다.

어떤 Learning 상황에서든, Training data와 Test data(적용하고자 하는 데이터)의 분포가 같기는 힘들다. Training Data에서 학습된 모델이 잘 작동하게 하기 위해서 (Generalization error의 최소화) 두 분포 차이를 어떻게 다뤄야 할까?

이 문제를 푸는 데에는 다양한 방법론들이 있으며, 본 논문에서는 optimal transport를 통해 이를 다루는 방법론을 설명한다. 이는 현재 가장 각광받는 접근방식 중 하나이기도 하다.

<Optimal transport를 활용한 도메인 적응문제 그림으로 설명>

Optimal transport?

optimal transport(이하 OT)는 한국어로 하면 "최적수송" 방법으로, 서로 다른 분포가 있을 때, 확률밀도/질량 함수 관점에서 접근하면 어떻게 가장 적은 cost(다양한 metric이 사용됨)로 각 support를 mapping 시킬지에 관한 내용이다.

기본적인 OT mapping T는 다음과 같이 정의된다.

위와 같이 구하는 mapping T를 optimal transport map이라고 하며, T는 어느 한 분포의 support에서 다른 어떠한 분포의 support로 가는 mapping이다. 이러한 문제를 Monge problem 이라고 한다.

문제는, Monge problem의 해를 정의할 수 없는 상황이 많이 발생한다는 것이다. 예를 들어, 서로 다른 두 이산형 분포 P, Q가 있는데, P의 support에 해당하는 원소가 Q의 support의 그것보다 개수가 적은 경우, 위와 같은 map T를 찾아낼 수 없는 경우가 존재한다. 이런 경우까지 포괄하고자, Kantorovich formulation이 제안되었다.

Kantorovich formulation에서는 Monge problem과 다르게 OT map T를 명시적으로 구하지는 않는다.(애초에 map T가 존재하지 않는 상황을 위한 개념임을 생각하자) 대신, joint distribution $\gamma$가 비슷한 역할을 한다. $\gamma$에서 쉽게 $\gamma(y|x)$를 구할 수 있고, 직관적으로 이것이 가지는 의미는, x의 질량을 y에 어떠한 확률(비율)로 분배하는지를 나타낸다고 볼 수 있다. 우리는 이 joint distribution을 optimal coupling이라고 부른다.

추가적으로, optimal transport와 아주 밀접한(사실상 동일한) 개념임 Wasserstein distance는 두 분포의 차이를 나타내는 metric으로서 다음과 같이 정의할 수 있다.

Framework

위의 OT개념을 사용하여 Domain adaptation 문제를 다음과 같은 방식으로 풀어 낼 수 있을 것이다.

1. Sample data $X_s$, target data $X_t$로 부터 sample, target 분포 $\mu_s, \mu_t$를 estimate 한다

2. $\mu_s$에서 $\mu_t$로 가는 optimal transport를 도출한다.

3. sample data를 transport를 통해 target support로 이동시키고, 거기서 분류기를 학습한다. (classifier이기 때문에 sample data의 label은 그대로 유지한다)

여기서, kantorovich formulation 하에서 OT-coupling을 통해 데이터를 이동시키는 것이 애매하다고 느껴질 수 있다.

이러한 상황에서는 barycentric mapping이라는 개념을 이용하여, 다음의 조건을 만족시키는 점을 optimal coupling에 의해 생성되는 map으로 정의한다.

Regularized Discrete Optimal Transport

위의 Framework 하에서, 결국 우리에게 주어진 것은 OT-coupling $\gamma$를 어떻게 구할 것이냐에 대한 문제이다.

앞에서 구한 OT-coupling의 정의에 의하면, 위의 식을 품으로써 OT-coupling을 구하게 된다.

본 논문에서는 위의 단순한 Loss에 추가적으로 Regularization Term 들을 도입함으로써, 더 나은 일반화 성능을 가지는 OT-coupling 구하는 방법론을 소개한다.

For smoothness

위의 정의로만 구한 OT-coupling $\gamma$는 $n_s$ x $n_t$ (각각 sample, target 데이터 개수) 차원을 가지는 matrix로 구해지며, 많은 원소가 0으로 나타내게 된다. Overfitting을 피하기 위해서는 $\gamma$을 보다 smooth 하게 보정해줄 필요가 있다. 따라서 Cuturi(2013)은 다음과 같은 Regularization term을 도입한 Loss function을 제안하였다.

위의 식에서 $\Omega_s(\gamma)$는 negative entropy를 의미하며, $\gamma(. | i)$가 uniform 분포를 가질 때 최소화 된다. 즉 위의 제약 항은 특정 원소가 0이 되지 않도록 (sparsity 방지) 하는 항이라고 보면 되며, 이는 uniform 분포와 $\gamma$ 사이의 KL-divergence로 이해 할 수도 있다.

위와 같은 최적화문제는 Sinkhorn-Knopp's scaling matrix approach를 통하여 효율적으로 구할 수 있다고 한다.(추후 설명)

Class-Regularization for Domain Adaptation

Sample data를 Target domain으로 이동시킬 때는, Sample data들의 구조를 보존하는 것도 매우 중요한 점이다.

따라서 이에 대한 제약 항 $\Omega_c$를 도입하면 Loss는 위와 같이 정의될 수 있다. Class-regularization을 위한 제약 항으로 논문에서는 두 가지의 옵션을 제시한다.

Regularization with Group-Sparsity

첫 번째 옵션은 sample data의 label 정보를 이용하는 것이다. 직관적인 motivation은 Target domain의 point는 같은 label을 가지는 sample data의 원소로부터만 mass를 받아야 한다는 것이다. 이는 transformation 후의 class 구조를 보존하기 위한 것이다.

만약, source에서 class가 잘 분리 되어 있었는데, OT에 의해 이동된 source 데이터에 class가 막 섞여있다면, 바람직한 결과가 나오기 어렵기 때문이다.

이에 따라서 다음과 같은 regularization term을 추가로 도입한다.

위의 제약항을 해석해보면, 각 target data $x_j$에 대하여, label $cl$을 가지는 source data들 $x_i$ , $i \in I_{cl}$ 에 대한 확률 합을 최소화 시킨다는 것이고, 이는 특정 고정된 j에 대해 특정 cl만을 label로 가지는 source가 연결될 확률이 양수가 되도록 강제한다.

이러한 제약 항을 도입하는데에 있어서, 우리가 기대하는 것은 Y의 분포가 source와 target domain에서 비슷하다는 것이다. (Source의 Y 정보가 Target의 Y 정보로 전송? 되고 있으므로) 하지만 약간의 차이는 용인 가능하다고 한다.

Laplacian Regularization

$\Omega_c$에 대한 첫 번째 선택에서는 class의 구조를 보존하는 것을 목표로 한 것이다.

두 번째 방법인 Laplacian Regularization 에서는 그래프를 통해서 추정된 데이터 구조를 OT 동안 유지하고자 하는데 목적이 있다.

위에서 $S_s$는 sample data 사이의 유사도를 나타낸 행렬을 의미하며, 이 제약항은 결국 유사도가 큰 데이터들이 target 으로 mapping 되었을 때, 두 barycenter mapping 간의 $L_2$ distance가 가까이 유지되게끔 강제한다.

Generalized Conditional Gradient(GCG) for solving regularized OT problems

이제 $\gamma$를 최적화시키는 방법을 알아보자. 이에 앞서, 논문에서는 restricted $\gamma$의 집합$\mathcal{B}$에서 최적의 $\gamma$가 존재하는 조건에 대하여 탐구한다.

• 위의 Loss는 $\gamma$에 대하여 연속임
• $\mathcal{B}$는 compact set.
• 최대최소정리에 의해 Loss는 minima를 가짐
• Loss function이 convex인가?
  • Frobenius norm : convex (w.r.t $\gamma$)
  • negative entropy : convex
  • (18)의 laplacian regularization term은 convex

minima를 구하는 알고리즘으로, 이 논문에서는 기존의 conditional gradient algorithm(CG)를 확장한 Generalized conditional gradient(GCG)를 제안한다.

이 부분에 대해서는 convex optimization을 공부해보고 업데이트 예정이다.

Identifying Cause and Effect on Discrete Data using Additive Noise Models(Peters.J, Janzing.D, Scholkoph. B, 2009)

Motivation

이산형 공변량과 이산형 반응변수 데이터에서 어떻게 인과관계를 모델링 할 수 있을 것인가?

ANMs for Discrete Variables

다음의 모델을 셋팅하자.

$$Y = f(X) + N, N \perp X $$

(자세한 조건은 생략)

Identifiability

수 많은 joint distribution 들 중,

1. ANM이 X->Y로 결정되는 분포가 있고, (forward direction)
2. Y->X로 결정되는 분포가 있으며(backward direction)
3. identifiable 하지 않은 분포
4. 두 방향 모두 성립하지 않는 분포가 있을 것이다.

본 논문에서는 3의 영역에 포함되는 분포는 매우 강한 restriction을 만족해야 한다는 Theorem 을 들어 3의 영역에 해당되는 분포의 집합이 소수임을 밝히고 있다.

Practical Method for Causal Inference

프레임워크는 다음과 같다.

(1) iid Data $(X,Y)$가 주어져 있다.

(2) 데이터를 모델 $Y = f(X) + N$에 적합 시킨 후 이 때의 잔차를 $\hat{N}$이라고 하자. 또한 데이터를 모델 $X = G(Y) + N$에 적합 시킨 후 이 때의 잔차를 $\tilde{N}$이라고 하자.

(3) $\hat{N} \perp X, \tilde{X} \not\perp Y$ : X->Y $\hat{N} \not\perp X, \tilde{X} \perp Y$ : Y->X $\hat{N} \not\perp X, \tilde{X} \not\perp Y$ : bad fitting $\hat{N} \perp X, \tilde{X} \perp Y$ : Not identifiable

그럼 남은 관심대상은 $f(X)$와 independence test에 관한 것이다.

본 논문에서는 f(X)를 구할 때, 단순 $L_p$ loss를 사용하는 것이 아니라 Dependence measure : $DM(N,X)$를 사용할 것을 제안한다. 이는 적합 후 noise와 공변량에 대한 independence 를 통하여 모델을 평가하기 때문이다.

Independence test로는 (이산형 변수이기 때문에) $\chi^2$ test를 사용할 수 있다. 다만 각 cell의 기대도수가 작을 때에는, Fisher의 exact test를 사용한다.

Experiments

Question:

• dependence measure 을 사용한 regression이 가짜 인과관계를 형성할 가능성은 없는가?

https://www.youtube.com/watch?v=JUJNGv_sb4Y Stanford의 Andrew Ng 교수님의 Deep Learinig 수업 Week # : Full-cycle of DL project를 정리한 것임

Steps of an ML project

1. Select Problem
2. Get data
3. Design Model
4. Train Model
5. Test Model
6. Deploy
7. Maintain System

• Quality Assurance

• 4에서 한번에 되는 경우는 거의 없으므로 3과 4를 엄청 반복하게 될 것.

1. What is good project

• 작업하기 좋은 프로젝트가 무엇인가?
• Domain 지식을 최대한 활용하여 독특한 작업 수행
• 타당성(Feasibility) : 딥러닝으로 할 수 있는게 무엇이고 할 수 없는게 무엇인가?

2. Get data

• 데이터 수집에 걸리는 시간 / 방법?
• 새로운 프로젝트를 할 때는 뭐가 주된 이슈인지 알기가 매우 어렵다.
• 일단 첫 모델을 돌려본 후, 매우 반복적으로 진행될 것.
• 데이터를 빨리 구할 수 있다면 빨리 구해라.

3. Train Model ~ 5. Test Model

• 중요 : 각 실험에 대하여 메모를 꼭 해라.
• 수업에서 주로 다룰 부분

• 베이지안 네트워크에서 값을 모르는 노드를 추론하려면 주로 Bayesian Posterior을 통하여 접근하는 방법을 생각할 수 있다.

• Markov property를 이용하여 이러한 posterior를 구하는 식을 쓰는 건 매우 간단하다.

• 우리가 사전에 가지고 있는 정보는 Conditional probality table(direct edge간의 조건부분포)임을 다시 한번 상기하자.

• CPD가 Full로 주어진 상황이 많이 있을지는 생각해봐야겠다. 아마 흔한일은 아닐 것 같다.

• 어쨋든 간에, 시간이 무한대라면, 이러한 inference는 그냥 계산하면 된다.

• 이러한 naive한 접근방식은 $O(K^N)$의 시간복잡도를 가진다.

  • 엣지 수 만큼 곱하는 것을 |e||a| 번 만큼 해야하고, |B|만큼 반복해야 P(B,j,m) 얻을 수 있음
  • 더하기는 |e||a||B|번 하면 됨
  • 최종 연산량 = (|edge|+1)|e||a||B|
  • Hidden variable이 늘어남에 따라서 기하급수적으로 증가한다.

• 시간복잡도를 줄이기 위해, Variable Elimination이라는 기법을 사용한다.

• variable elimination은 단순히 sum의 순서를 바꿔서 연산량을 줄이는 기법임.

• 위의 P(L,t,r)을 구하는 두 예제를 생각해보면,

  • Enumeration 연산량 : |2||T||R||L| + |T||R||L| = 3|T||R||L|
    • Variable Elimination 연산량 : (|R|+|R|)|T| + |L|(|T| + |T|) = 2|L|T| + 2|R||T|

• random L에 대한 확률을 구하려면 결국 L의 원소개수만큼 반복해야하는데, 그 안에 L과 관련이 없는 인자들을 따로 factor로 묶은 다음에 L의 변화에 따른 factor에 대한 연산을 생략하는 technique라고 이해하면 될 것 같다.

• 아까 나왔던 그래프에 대한 예제를 variable elimination으로 계산하면 다음과 같다.
• sum을 최대한 안쪽으로 넣으면, 일단 곱하기 연산수가 감소한다.

• 하지만 variable elimination하는 방법이 유일한 것은 아니다. 변수 순서를 바꿈에 따라 필요한 계산량이 천차만별이다.

• 그 전에, 왜 이러한 방법에 "variable elimination"이라는 이름이 붙었는지 확인해보자. 사실 sum의 순서를 바꿔서 어느 변수를 소거하는 것은, "소거 변수"를 제외한 나머지 변수들 간의 joint prob을 구하는 것과 같은 연산이다.

• 위의 슬라이드를 보면, 첫번째 방법은 X1, X2, Z 순서대로 변수를 제거하고, 두번째 방법은 Z, X2, X1 순으로 제거한다. Z를 먼저 제거하면, (X1,X2,X3)에 대한 joint를 계산해야 한다. 이 세 변수는 종속적이기 때문에, 직관적으로 보면 연산량이 많아질 위험이 있다.

• 가장 큰 factor의 크기에 의해 연산량이 달라진다고 말하고 있다. 가장 큰 factor의 크기가 작을수록 연산효율이 좋다.
• Factor의 크기 : 각 factor가 가질 수 있는 값의 크기. 즉 factor가 이진변수 n개로 표현되면 크기는 $2^n$이다.
• 이게 뭔말인고 하니, 결국 위에서 (X1, X2, X3)에 대한 joint를 계산하기 때문에 연산량이 많아진 다는 것과 같은 맥락이다.
• 아까 두 방법 중 첫번째 방법에서는 f1,f2,f3의 크기가 모두 2이다.
• 두번째 방법에서는 f1의 크기가 $2^3 = 8$이 된다.
• 하지만, 어떠한 최악의 경우에는 variable elimination을 무슨 순서로 하든지 exponential 한 연산량에서 더 나아질 수 없다고 한다.

• 지금까지 한 것은 참 값을 구하는 Exact Inference 방법이다.
• 우리는 Exact가 아니라 approximate하게 확률을 추론 할 수도 있다. 정확한 결과 대신 계산 속도와 효율성에 장점이 있다.

*본 포스팅은 서울대학교 데이터사이언스 대학원 이상학 교수님의 "데이터사이언스를 위한 머신러닝과 딥러닝2" 강의록을 기반으로 함.

• 기존의 markov chain의 가정에 의하면, 모든 상태는 그 직전 상태에만 의존하므로, 이전 상태에 현 상태에 대한 모든 정보가 포함된다고 생각되는 경우에 한하여 사용될 것이다.

• 만약 우리가 현 상태에 대한 불완전한 정보나 missing이 포함된 데이터만 관찰 할 수 있다면, Hidden Markov Model은 적절한 선택지일 것이다.

• 여기서 Z는 Hidden state, X는 Outcome state를 의미이며, 우리는 X를 현재 관찰하고 있다.
• 예를 들면, 우리가 과거 날씨에 관한 정보를 잘 알지 못하는 상황이라고 가정하면 Z는 weather, X는 그 날에 했던 activity라고 둘 수 있다.

• HMMs는 다양한 sequential data에 대하여 효과적인 모델이라고 한다.
• HMM에 관한 inference와 그에 대한 알고리즘 세 개를 소개한다.
  • Viterbi : Z의 Value가 관심대상이다. 즉, $argmaxP(Z|X)$를 알고자 한다.
    • Forward-Backward : State에 대한 확률계산을 위한 알고리즘이다.
  • Baum-Welch : Parameter 추정에 관한 알고리즘이다.

• Markov Chain의 활용 예시를 소개한다. POS는 NLP문제에서 단어의 품사를 예측하는 방법론이다.
  • 자료와 같이, 품사 Z를 Hidden State로 생각하고, 우리는 현재 실제 문장 X를 관측하는 상황이라고 가정한다.

• HMM의 기본 셋팅에 대하여 설명한다.
• Hidden State Z의 전이확률은 시간 t에 관련 없이 동일하다(우리가 지금까지 다룬 Markov Chain은 이를 가정하고 있다. 물론 당연히 Markov Chain이 이 조건을 만족할 필요는 없다)
• $X_i$의 $Z_i$에 대한 조건부분포는 시간 t에 관계가 없다.

• 위의 셋팅에 따라서 HMM을 정의했다고 생각하면, 이제 우리에게 남은 과제는 일단 위의 세개가 있다.

• $\arg \max_z P(Z|X)$ 를 찾기 : viterbi 알고리즘은 이를 해결하는 방법 중 하나다.

• $P(X)$ 찾기 : ex) Forward-Backward 알고리즘

• $\arg\max_\theta P(x:\theta)$ 찾기 : ex) baum-welch

• 이 때, $\theta$는 $<\pi, T, \epsilon>$를 포함한다.

  • $\pi$는 초기상태를 의미한다.
  • T는 Z의 전이행렬을 의미한다

Viterbi Algorithm

• 먼저, viterbi 알고리즘에 대하여 설명하자.
• 알고리즘의 목적은 $P(Z|X)$를 최대화시키는 Z를 찾는 것이다.
• 만약 이 문제에 대하여 Naive하게 접근한다면, 확률계산을 $n * m^n$번 만큼 해야한다.
  • $nm^n$이라는 숫자가 나온 이유는 다음과 같다. 일단 z의 모든 조합은 $m^n$개이다. 또한, 각 z에 대한 조건부확률을 계산하는 것은 아래의 공식 때문에 최대 n번 필요하다.
  • 즉 naive한 접근으로의 order는 $n*m^n$이 된다
• 이러한 복잡도를 줄이기 위해 Viterbi 알고리즘이 사용된다.

• Viterbi Algorithm의 기본적인 아이디어는 다음과 같다.
• Naive한 접근을 할 때, 우리는 모든 z1..zn의 조합 총 $m*n^m$ 개의 조합에 대하여 모두 확률을 계산하게 된다.
• 하지만, 흥미있는 대상이 확률의 Maximum일 때는, 굳이 모든 상태공간을 다 찾아 뒤질 필요가 없다.
• 예를들어, $Z_1 \rightarrow Z_4$ 까지의 경로 중 X에 대하여 가장 높은 조건부확률을 가지는 경로를 조사하기 위해선, Z가 2개의 state를 가질 수 있다는 상황 하에서 naive한 방법론으로는 $2^4 = 16$개의 Route를 비교해야 한다.
• 하지만 만약 우리가 현재 최대확률을 가지는 $Z_1 \rightarrow Z_3(A)$, $Z_1 \rightarrow Z_3(B)$ (여기서 A,B는 Z의 state. 즉 $Z_1 \rightarrow Z_3(A)$는 $Z_3$이 A로 끝나는 경로를 의미한다.) 를 알고 있다면, 우리는 최대확률을 가지는 $Z_1 \rightarrow Z_4(A)$ 를 찾기 위해 2개의 경로만 비교하면 된다. $Z_1 \rightarrow Z_4(B)$의 경우에도 마찬가지다.

• 결론적으로 위의 아이디어를 체계화하면 다음과 같은 알고리즘을 생각 할 수 있다.

• $\mu_j(z_j)$는 t = j-1에서 각 상태로의 최적 경로에서, 주어진 상태 $z_j$로 가는 경로의 확률이다.

• 이를 연쇄적으로 반복한 후, $M = \max_{z_n}\mu_n(z_n)$을 구하면, 시간 1부터 n까지의 최적의 경로를 찾을 수 있다.

• viterbi 알고리즘의 시간복잡도는, $O(n*m^2)$이다. 기본 아이디어를 생각해보면 이해가 될 것이다.

• Viterbi 알고리즘의 문제점은, 서로 다른 확률들을 연쇄적으로 곱하다보니 결과값이 수치적으로 0이 될 가능성이 존재한다.
• 간단한 해결책은 log를 통해서 확률들의 곱을 log들의 합으로 만드는 것이다.

Forward-Backward Algorithm

• 다음으로 Forward-Backward 알고리즘에 대하여 알아보자. 앞서 언급한대로, 이 알고리즘의 목적은 확률의 계산. 즉 observed X에 대한 Z의 다양한 조건부확률을 계산하는 데 있다.

• forward-backward 알고리즘은 그 이름에서 알 수 있듯이, Forwrad, Backward의 두 부분으로 구성된다.
• Forward probability $s_t(i) = P(Z_t = i, x_{1:t})$
• Backward probabilty $r_t(i) = P(x_{t+1:n}|Z_t=i)$
• $s_t(i) * r_t(i) = P(x_{1:n},Z_t=i)$ : 이러한 성질 덕에 다양한 x에 대한 조건부확률을 구하는 데에 쓰일 수 있다.

• 이와 같이 forward-backward 알고리즘을 통해 forward, backward probability를 알고 있으면, 적절히 조합하여 원하는 조건부확률을 찾을 수 있다.

• 여기서, Forward probabilty $s_j(z_j)$가 어떻게 정의되었는지 주목하자
• $s_j(z_j) = \sum_{z_{j-1}}s_{j-1}(z_{j-1})p(z_j|z_{j-1})p(x_j|z_j) = \sum_{z_{j-1}}p(z_{j-1}, x_{1:j-1})p(z_j|z_{j-1})p(x_j|z_j) = \sum_{z_{j-1}}p(x_{1:j-1},z_j,z_{j-1})p(x_j|z_j) = \sum_{z_{j-1}}p(x_{1:j},z_j)$

• Backward prob는 위와 같이 계산한다.

Baum-Welch algorithm

지금까지의 두 상황은(Z추론, 확률추론) 모두 $\theta = <\pi, T, \epsilon>$을 우리가 알고 있다는 상황하에서 이루어진 것이다. 이제 $\theta$ 자체를 추론하기 위한 Baum-Welch algorithm 을 소개한다.

• 일반적으로 HMM에서의 파라미터 추정은 GMM에서에 비해 더 어렵다.

• 잠재변수 Z가 하나가 아니고, 그리고 그들간에 의존성이 있기 때문임.

• Transition probabilty 즉 Z의 전이확률은 위의 그림과 같이 추정할 수 있다. 이는 직관적이기도 하지만, 사실 잘 생각해보면 이산형 Markov Chain에서 어느 상태 i에서 다른 상태로 전이하는 사건은 다항분포를 따르게 되고, 다항분포의 MLE는 그냥 표본비율이 되기 때문에 위와 같이 생각해도 무리가 없다.
• 이를 구하기 위해 우선 $P(Z_t = i, Z_{t+1} = j , x_{1:n})$을 추정해보자.

• 예를 들어, Forward Backward를 이용해 $P(Z_2 = i, Z_{3} = j , x_{1:n}) = s_2(i)P(Z_3 = j|Z_2 = i)P(x_3|Z_3 = j)r_3(j)$로 구할 수 있다.

*본 포스팅은 서울대학교 데이터사이언스 대학원 이상학 교수님의 "데이터사이언스를 위한 머신러닝과 딥러닝2" 강의록을 기반으로 함.

• Clustering에는 많은 방법들이 있다.
• Clustering 방법들에 대한 평가를 위해서, 어떠한 측도가 필요할 것이다.
• 이를 위한 하나의 접근법은, Data가 특정 생성모델에 의해 generated 되었다고 보는 것이다. 즉 특정 모델을 가정하고, 통계학에서의 MLE와 비슷한 방법론을 이용하여 파라미터를 추정한다.

• Gaussian Mixture Model의 pdf는 단순히 정규분포의 가중합이다.
• Gaussian의 선형 결합은 거의 모든 smooth density를 근사할 수 있다고 한다.
  • 이에 대한 직관적인 설명을 stack exchange에서 찾았다. 아주아주 간단히 요약하면, 임의의 pdf는 direc-delta함수의 선형결합으로 표현되고, gaussian distribution은 분산을 0으로 보내면 direc-delta로 수렴하므로 gaussian의 mixture를 통해서 any pdf를 근사할 수 있다는 논리다. 이것만 보면 꼭 임의의 pdf를 근사하기 위해 gaussian의 mixture를 쓸 필요는 없어보인다.

• GMM을 fitting 할 때의 기본적인 접근법은, Maximum Likelihood Estimator를 찾는 것이다.
• 이 때 두 가지 문제가 발생한다.
  • Singularities : 만약 mixture model 내에 한 component가 단 하나의 데이터셋에 대응된다면, 해당 component에 해당되는 likelihood가 무한대로 발산하게 된다(해당 component는 direc-delta로 수렴하게 된다) 또한, 해당하는 원소의 분산이 0으로 수렴하므로, X의 공분산행렬은 singular하게 된다. (해당 원소가 대응되는 row/column의 원소가 모두 0으로 수렴) 공분산 행렬의 Inverse는 MLE를 산출하는데 필요한데, 이를 구하기 어렵게 된다.
  • Identifiability : GMM은 Gaussian의 단순 가중합이므로, parameter의 순서에 상관이 없이 같은 모델에 대응될 수 있다.
• 결론적으로, 일반적인 미분 방법을 이용하여 GMM을 fitting하는 것은 무리가 있다.

• Naive 한 ML방식 대신, GMM을 Fitting 할 때는 각 Data point x가 어떠한 Gaussian component에서 왔는지를 나타내는 Latent variable Z를 도입하여 문제를 단순화한다.

• 이러한 잠재변수의 도입이 어떻게 기존 ML방식의 문제점을 해소시키는가?

  • 이는 Latent Variable하에서의 optimization 방식인 EM 알고리즘을 설명 한 후 다시 언급하도록 하자.

• Hidden latent variable Z를 도입하여 기존의 log-likelihood를 다시 표현했다.
• sum-inside-log의 상황은 다음과 같은 이유로 최적화가 어렵다.
  • 여기서 u와 $\Sigma$는 벡터다. log 안에 sum이 있으면, log는 비선형 함수이므로 component별로 분리가 매우 어렵고, 즉 각 component 간의 상호작용을 모두 고려한 최적화가 이루어져야 한다. 즉 문제가 복잡해진다.
  • 비슷한 맥락에서, 해가 closed-form으로 나오지 않는다.
    
  • 이 함수의 최적화를 위해 Gradient Descent를 쓰지 않는 이유도 이에 대응될 것이다.

• 직관적인 EM에 대한 설명이다.
  • observed data 를 기반으로 한 complete data(X,Z)의 가능도를 계산한다
  • 위의 가능도를 최대화시키는 방향으로 parameter를 update 시킨다.

• 다시 말하면, E-step에서는 observed data를 조건부로 하여 latent variable의 posterior를 산출한다.
  • 이 때, 각 data point에 대하여 z의 값이 확률적으로 부여되므로, 하나의 데이터 포인트가 하나의 가우시안 컴포넌트에 과도하게 맞춰지는 문제를 해결 할 수 있다.
• M-step에서는 posterior를 최대화시키는 방향으로 parameter-update를 진행한다.

• E step을 조금만 더 자세히 살펴보자. 앞서 언급되었던 E-step에서의 posterior은 Bayes Theorem을 이용하여 간단하게 계산이 가능하다.

• M-step에서는 앞서 구했던 $\gamma$를 이용하면 sum-inside-log 상황을 탈피할 수 있다.
• 위의 EM step 을 반복한다.

• 요약하면 전체적인 흐름은 다음과 같다.
• E-step에서는 given data에 대한 Latent Variable에 대한 조건부 분포를 구하고, 이를 이용해서 계속해서 parameter를 update시킨다.

$$\int_a^b h(x)dx $$ 과 같은 적분을 계산하는 것은, $h(x)$가 복잡한 함수이거나 $x$가 다차원 벡터인 경우 쉬운 일이 아니다. 이런 경우, 적분값을 근사적으로 구하기 위해, 여러가지 Simulation 방법론들이 개발되었다. Simulation은 특히 Bayesian Inference에서 유용하다.

예를 들어, $X^n = (X_1,...,X_n)$이 observed data일 때, posterior density는 다음과 같이 구할 수 있다. $$\pi(\theta|X^n) = \frac{L_n(\theta)\pi(\theta)}{c} $$

Bayesian inference에서는 posterior의 mean을 이용해 $\theta$를 추정하는 경우가 많은데, 만약 $\theta = (\theta_1, \theta_2....)$가 다차원 벡터라면, $\theta_1$에 대한 추론을 위해서는 $\theta_1$에 대한 주변사전분포, 즉 $\pi(\theta_1|X^n) = \int_{\theta_2}\int_{\theta_3}...\int_{\theta_k} \pi(\theta|X^n)$를 구한 후, 비로소 $\theta_1$에 대한 추론이 가능해 질 것이다. 이런 과정에서 요구되는 다중적분 들은 계산이 힘들거나 연산량이 많은 경우가 빈번하기에, 이러한 경우 우리는 simulation을 선호하게 되는 것이다.

Basic Monte Carlo Integration.

가장 간단한 형태의 simulation은 Monte-carlo 적분이다.

$$I = \int_a^b h(x)dx $$ 의 적분을 해야 하는 상황을 생각하자. 만약 h(x)가 복잡한 형태라서, I에 대하여 알려진 closed form의 적분형태가 없어서, 직접적으로 적분값을 구할 수 없다. 이러한 상황에서, 우리는 다음의 사실을 발견 할 수 있다.

$$I = \int_a^b h(x)dx = \int_a^b w(x)f(x)dx = E_fw(x) $$

만약 우리가 f라는 밀도함수에서 observations 들을 generate 할 수 있다면, Strong Law of Large Numbers 에 의해, $$\frac{1}{n}\sum_i w(x_i) \xrightarrow{a.s} E_fw(x) = T $$ 임을 알 수 있으므로, $\frac{1}{n}\sum_i w(x_i)$를 $I$에 대한 Estimate로 활용 할 수 있다.

Example(Bayesian inference for two binomials)

$$X \sim Bin(n, p_1) ;;; Y \sim Bin(m, p_2) $$ 이 때, prior $\pi(p_1, p_2) = \pi(p_1)\pi(p_2) = 1$이라고 설정하자.

Bayesian method를 통해서 $\delta = p_2 - p_1$을 추정해보고자 한다.

수식적으로 풀면 다음과 같다.

$f(p_1, p_2 | X,Y) \propto p_1^X(1-p_1)^{n-X}p_2^Y(1-p_2)^{m-Y}$ $\delta$에 대한 posterior를 구하기 위해선, $P(\delta \le c|X,Y) = \int_Af(p_1, p_2 | X,Y)$ where $A ={p_1, p_2| p_2 - p_1 \le c}$ 를 구하고 이를 $\delta$에 대하여 미분하는 방법을 생각할 수 있으나, 이는 수치적으로 복잡한 형태를 띌 수 있다.

이러한 번거로움을 피하기 위해, 우리는 Monte-Carlo Simulation을 생각 해볼 수 있다.

$\delta$의 posterior mean은 다음과 같이 표현된다. $$\hat{\delta} = \int \delta f(p_1, p_2 | X,Y) = \int \delta f(p_1,|X)f(p_2|Y) $$ 이 때, $p_1|X \sim Beta(X+1, n-X+1)$, $p_2|Y \sim Beta(Y+1, m-Y+1)$ 이다.

이제 $$P_1^{(i)} \sim Beta(X+1, n-X+1) $$ $$P_2^{(i)} \sim Beta(Y+1, m-Y+1) $$ 로 샘플링을 하고, $\delta_i = P_2^{(i)} - P_2^{(i)}$로 두면

Monte Carlo 방법에 따라서 Bayes method에 따른 $\delta$의 estimator은

$$\hat{\delta} \approx \frac{1}{N}\sum_i \delta_i $$ 로 구할 수 있다.

Importance Sampling

몬테칼로 적분에서, 우리는 $h(x) = w(x)f(x)$로 표현되는 pdf $f$를 잡아서, $f$를 따르는 분포에서 표본을 샘플링함으로써 구하고자 하는 적분을 근사 할 수 있었다.

만약, 적당한 f를 찾기 힘들다면, 우리는 다음과 같이 생각할 수도 있다. 사실, 몬테칼로 방법과 다른것이 없다.

Sampling이 가능한 pdf $g(x)$를 잡아서,

$$I = \int h(x)f(x)dx = \int \frac{h(x)f(x)}{g(x)}g(x)dx = E_g(Y) $$ where $Y = \frac{h(x)f(x)}{g(x)}$. 그렇다면, 몬테칼로와 같은 방법으로, $$ \hat{I} = \frac{1}{N}\sum Y_i $$ 와 같이 적분의 근사값을 구할 수도 있다.

여기서 하나의 궁금증이 생길 수 있다.

$g(x)$는 무엇을 고르든 상관이 없는가?

$g(x)$를 무엇을 고르든 구해진 추정값이 참값으로의 일치성을 갖는 것은 자명하다.

다만, $g(x)$의 선택에 따라, 추정값의 표준오차가 달라지게 된다. 다음을 보자.

$$E_g(w^2(x)) = \int (\frac{h(x)f(x)}{g(x)})^2g(x)dx = \int \frac{h^2(x)f^2(x)}{g(x)}dx $$

만약, $g(x)$가 너무 얇은 꼬리를 가진다면, w의 2차적률은 $\infty$에 가까워 질 수 있다. 즉, 우리는 꼬리가 f보다 두꺼운 g를 고려할 필요가 있다. 또한, f가 큰 지역에서 작은 g값을 가지는 g를 선택해도, 분산이 커질 우려가 존재한다. 결론적으로 말하면, 우리는 f와 비슷한 개형을 가지는 g를 선택하는 것이 유리하다.

The Metropolis-Hastings Algorithm.

이제 이 장의 Main Theme인 MCMC(Markov Chain Monte Carlo)의 한 종류인 Metropolis-Hastings algorithm을 소개한다.

MCMC의 IDEA

Stationary distribution이 $f$인 Markov Chain $X_1, X_2,...$을 고려하자.

다음이 성립한다.

특정한 조건 하에서 $$ \frac{1}{N}\sum_ih(X_i) \xrightarrow{P} E_f(h(X)) = I $$ 이는 마코프 체인의 대수의 법칙에 의해서 성립하게 된다.

이러한 아이디어를 활용하기 위하여, Staionary distribution이 f인 markov chain을 생성하는 Metropolis-Hastings Algorithm은 다음과 같다.

Metropolis-Hastings Algorithm
0. proposal distribution $q(y|x)$ 를 하나 정하자. q는 pdf를 의미한다.

1. $X_0$를 임의로 고른다
2. $X_0, X_1, ..., X_i$가 주어졌을 때, $X_{i+1}$을 다음과 같이 생성한다.

• proposal $Y \sim q(y|X_i)$을 뽑는다.
• $r = r(X_i, Y) = \min{\frac{f(y)}{f(x)}\frac{q(x|y)}{q(y|x)}, 1}$로 두고,
• $X_{i+1} = \begin{cases} Y & \text{if } with ; probability ;r, \ X_i & \text{if } with; probability; 1-r. \end{cases}$

이에 따르면, 우선 $X_n$은 Markov Chain임을 확인 할 수 있다.

Why M-H algorithm works?

그렇다면, 왜 M-H 알고리즘이 stationary distribution f를 가지는 markov chain을 generate 시킬까?

다음의 증명을 보자

Theorem: M-H algorithm generates Markov chain with stationary distribution f
먼저 M-H algorithm으로 생성되는 Markov chain이 stationary distribution을 가지는지 부터 확인해야 하는데, 이는 M-H algorithm이 ergodic 함을 보이면 된다. (적절하게 proposal distribution q를 설정하면 이는 만족된다.) 또한, Markov Chain 이론에 따르면, Detailed Balance Condition, 즉 $p_{ij}\pi_i = p_{ji}\pi_j$ 가 만족되면 markov chain은 stationary distribution $\pi$를 가진다고 했다.
WTS:M-H에 의해 생성되는 markov chain은 detailed balance를 만족한다 즉 이 경우, $f(x)p(x,y) = f(y)p(y,x)$임을 보이면 된다.이 때 x=y일때는 이 조건이 성립함이 명백하므로, $x \neq y$인 상황만 고려하자.
$p(x,y) = rq(y|x) = \min{\frac{f(y)}{f(x)}\frac{q(x|y)}{q(y|x)}, 1}q(y|x)$ if $x \neq y$
$\therefore f(x)p(x,y) = \min{f(y)q(x|y), f(x)q(y|x)} = f(y)p(y,x)$

따라서 M-H 알고리즘에 의해 생성되는 마코프 체인은 정상분포 f를 가진다.

앞의 monte carlo 방법들에 비해서 MCMC가 가지는 이점은, MCMC는 목표하는 분포 f에 가깝게 데이터를 추출할 수 있는 방법을 제시한다는 것이다.

Gibbs Sampling

깁스추출법은 M-H 알고리즘을 다차원으로 확장시킨 것을 볼 수 있다. 즉, 복잡한 다차원 분포에서 표본을 잘 추출할 수 있도록 하는 알고리즘으로, MCMC의 일종이다.

Gibbs Sampling : 2차원 변수의 경우 Iterate until convergence:

• $X_{n+1} \sim f_{X|Y}(x|Y_n)$

• $Y_{n+1} \sim f_{Y|X}(y|X_{n+1})$
  

  Gibbs Sampling : 다차원 변수로의 일반화 Iterate until convergence:

• $X_{n+1} \sim f_{X|Others}(x|Others)$

• $Y_{n+1} \sim f_{Y|Others}(y|Others)$

• $Z_{n+1} \sim f_{Z|Others}(z|Others)$ ....

  NOTE: Gibbs Sampling은 M-H 알고리즘의 한 종류이다.
  Suppose : proposal = $(X_{n+1},Y_{n+1}, Z, W_n, T_n...)$ current state = $(X_{n+1},Y_{n+1}, Z_n, W_n, T_n...)$ 이 때 z의 분포를 $q(z) = f(z|X_{n+1}, Y_{n+1}, W_n, T_n...)$으로 두면, ($=f_Z(Z|others$)) $r((X_{n+1},Y_{n+1}, Z, W_n, T_n...), (X_{n+1},Y_{n+1}, Z_n, W_n, T_n...))$ $= \min{\frac{f(X_{n+1},Y_{n+1}, Z, W_n, T_n...)}{f(X_{n+1},Y_{n+1}, Z_n, W_n, T_n...)} \frac{q(Z_n|Z)}{q(Z|Z_n)}, 1}$ $= \min {\frac{f(X_{n+1},Y_{n+1}, Z, W_n, T_n...)}{f(X_{n+1},Y_{n+1}, Z_n, W_n, T_n...)}\frac{f(Z_n|X_{n+1}, Y_{n+1}, W_n, T_n...)}{f(Z|X_{n+1}, Y_{n+1}, W_n, T_n...)}, 1} = 1$

** Gibbs Sampling의 Stationary Distribution은 f(X,Y,Z..) 인가?**

근데 문제가 하나 있다. proposal을 추출하는 분포 $q(x) = f(X|others)$에서 데이터를 추출하기 어려운 상황이라면 어떻게 해야할까?

Metropolis with Gibbs 추출법은 MH algorithm과 Gibbs Sampling을 결합하여 각 변수별로 제안된 샘플을 조건부 분포에 따라 선택하는 Gibbs 샘플링을 수행하면서, Metropolis-Hastings 알고리즘을 통해 각 샘플의 수용 여부를 결정한다.

Metropolis within Gibbs : 2차원 변수
(1a) $Z \sim q(z|X_n)$으로 proposal을 추출한다. (1b) $r = \min {\frac{f(Z, Y_n)}{f(X_n, Y_n)}\frac{q(X_n|Z)}{q(Z|X_n)}, 1}$ (1c) $X_{n+1} = \begin{cases} Z & \text{if } with ; probability ;r, \ X_n & \text{if } with; probability; 1-r. \end{cases}$
(2a) $Z \sim \tilde{q}(z|Y_n)$으로 proposal을 추출한다. (2b) $r = \min {\frac{f(X_{n+1}, Z)}{f(X_{n+1}, Y_n)}\frac{\tilde{q}(Y_n|Z)}{\tilde{q}(Z|Y_n)}, 1}$ (2c) $Y_{n+1} = \begin{cases} Z & \text{if } with ; probability ;r, \ Y_n & \text{if } with; probability; 1-r. \end{cases}$

q는 sampling 가능한 분폳함수로 정하면 된다.

*즉, Gibbs Sampling은 M-H 알고리즘을 다차원 분포에대하여 적용하기 위해, 다차원 분포 샘플링 문제를 여러개의 1차원 분포 샘플링의 문제로 변환시킨 것이다.

Question

• M-H 알고리즘에서 q는 어떻게 선택해야 하는가?

Markov Chain

The process ${X_n : n\in T}$ is a Markov chain if $$P(X_n = x | X_0,...,X_{n-1}) = P(X_n = x|X_{n-1}) $$ 즉, markov chain은 오직 이전의 상태(state)에만 영향을 받는 확률과정을 이른다. 따라서 다음과 같은 성질이 성립한다.

$$f(x_1,...,x_n) = f(x_1)f(x_2|x_1)f(x_3|x_2)...f(x_n|x_{n-1}) $$
이 포스트에서, 우리의 관심사는 다음과 같다.

Markov Chain이 언젠가 평형상태를 이루는 조건은 무엇인가?

참고로, 여기서 평형상태라는 것은 n이 커질 때 $X_n$의 분포가 어떠한 상태로 수렴한다는 것을 의미한다. 이의 정의에 대해선 뒤에서 다루도록 하자.

Some definitions

Transition Matrix

We call $p_{ij} = P(X_{n+1} = j |X_n = i)$ the transition probabilities. The matrix P whose (i,j) element is $p_{ij}$ is called the transition matrix.

이 때, $p_{ij}$가 시간 n에 영향을 받지않으면, 이러한 markov chain을 Homogenous 라고 한다. 우리는 오직 homogenous한 상황에 대하여만 다룬다.

N-step transition probabilities

$p_{ij}(n) = P(X_{m+n} = j |X_m = i)$ 즉 상태가 i인 state로부터 n시간이 흐른 후, state가 j일 확률이다.

The Chapman-Kolmogorov equations

The n-step probabilities satisfy $p_{ij}(m+n) = \sum_k p_{ik}(m)p_{kj}(n)$

이는 $$P_{m+n} = P_mP_n $$ 임을 의미한다. $\because P_{m+n,ij} = \sum_k P_{m,ik}P_{n, kj}$

Communication relation

Communication relation

We say that i reaches j if $p_{ij}(n) >0$ for some n, and we write $i \rightarrow j$. If $i \rightarrow j$ and $j \rightarrow i$, we write $i \leftrightarrow j$ and say that i and j communicate.

Theorem

The communication relation satisfies the following properties.

• $i \leftrightarrow i$
• if $i \leftrightarrow j$ then $j \leftrightarrow i$
• if $i \leftrightarrow j$ and $j \leftrightarrow k$ then $i \leftrightarrow k$
• The set of states $\chi$ can be written as a disjoint union of classes $\chi = \chi_1 \cup \chi_2 \cup ...$ where any two states i and j communicate each other if and only if they are in the same class.

위의 정리에서 만약, 모든 상태가 하나의 Class에 있다면, 우리는 그 Chain을 irreducible 하다고 부른다. 또한, 만약 어느 class안의 상태에서 class 외부로 이동이 불가하다면, 그러한 class를 closed라고 부르고, 만약 그러한 class의 원소가 하나라면, 그 원소를 absorbing state라고 부른다.

Recurrent state

Definition State i is recurrent or persistent if $$P(X_n = i ; for ; some ;n \ge 1|X_0 = i) $$ Otherwise, state i is transient.

즉, 우리는 어떠한 상태 i가, 언젠가 반드시 돌아온다면 이러한 상태를 "재귀적"이라고 한다. 반대로, 어떠한 상태 영원히 돌아오지 않을 확률이 존재한다면, 이러한 상태를 "일시적"이라고 한다.

Theorem

A state i is recurrent if and only if $\sum_n p_{ii}(n) = \infty$
A state i is transient if and only if $\sum_n p_{ii}(n) < \infty$
PF) Let $Y = \sum_n I_n$, where $I_n$ : state가 n 시간 후 다시 i로 돌아오는 사건. $E(Y|X_0 = i) = \sum_n p_{ii}(n)$ 이러한 관점에서 생각해볼때, 만약 i가 recurrent하다면, $Y = \infty$이어야 한다.
한편, 다시 state i로 돌아올 확률을 $\alpha< 1$라고하자. 그렇다면, $P(Y|X_o =i) = \alpha^n(1-\alpha)$ 이다. 즉 $Y|X_0$는 geometric 분포를 따르고,이의 평균은 $\frac{1}{\alpha} < \infty$.

Properties of recurrence

1. If state i is recurrent and $i \leftrightarrow j$, then j is recurrent
2. If state i is transient and $i \leftrightarrow j$, then j is transient
3. A finite Markov chain must have at least one recurrent state.
4. The states of a finite, irreducible markov chain are all recurrent.

위 명제들에 대하여 생각해보자. 1. i는 반드시 i로 돌아온다. 만약 i상태에서 출발해 j상태에 도착했다고 해도, 반드시 i로 돌아와야 한다. 즉, $i \rightarrow j \rightarrow i$. 만약, j가 transient하다면, 앞으로 state i가 계속해서 무한번 반복되는 동안, 즉 $i \rightarrow i$의 경로 사이에 j가 단 한번도 없어야 한다. 이 확률은 0이 될 수 밖에 없다.

3. 볼차노-바이어슈트라스 정리 : 유한한 실수 공간에서의 임의의 유계 수열은 적어도 하나의 수렴 부분수열을 가짐. 비슷한 아이디어로 생각해보자.

4. 1,3에 의해 자명하다.

위의 명제들은 아래의 정리로 자명하게 이어진다. Decomposition Theorem The state space $\chi$ can be written as the disjoint union $$ \chi = \chi_T \cup \chi_1 \cup \chi_2 ... $$ where $\chi_T$ are the transient states and each $\chi_i$ is a closed, irreducible set of recurrent states.

Convergence of Markov Chains

Some definitions

recurrence time Let $X_0 = i$ $T_{ij} = \min {n > 0: X_n = j}$
mean recurrence time $m_i = E(T_{ii}) = \sum_n nf_{ii}(n)$, where $f_{ij}(n) = P(X_1 \neq j, ... X_{n-1} \neq j, X_n = j|X_0 = j)$
A recurrent state is null recurrent or null if $m_i = \infty$ otherwise it is called non-null or positive.
Period The period of state i is d if $p_{ii}(n) = 0$ whenever n is not divisible by d and d is the largest integer with this property. A state with period 1 is called aperiodic.

Lemma

If state i has period d and $i \leftrightarrow j$, then j has period d. pf) Let j is not d-periodic. i.e, $\exist N ; s.t.; p_{jj}(N) \ne 0$, (N은 d의 배수가 아님) $i \leftrightarrow j$ 이므로, $i \rightarrow j$를 갈 때 a시간이 걸리고, $j \rightarrow i$ 로 갈 때 b시간이 걸린다면, a+b는 반드시 d의 배수이다. 다음과 같은 경로를 생각하자. $i \rightarrow j \rightarrow j \rightarrow i$. 여기서 j가 d-periodic이 아니면 $i \rightarrow i$가 d의 배수가 아닌 확률로 돌아올 확률이 양수가 된다. Q.E.D

Ergodic

A state is ergodic if it is recurrent, non-null and aperiodic. A chain is ergodic if all its states are ergodic

Stationary distribution

We say that $\pi$ is a** stationary distribution** if $\pi = \pi P$, where $\pi = {\pi_i : i \in \chi }$ is a vector of non-negative numbers, that sum to 1.

Main Theorem : When a markov chain has a stationary distributon?

1 본 정리는 Markov Chain의 극한분포의 유일 존재 조건을 나타낸다.

An irreducible, ergodic Markov chain has a unique stationary distribution $\pi$. The limiting distribution exists and is equal to $\pi$. If g is any bounded function, then, $$lim_{N \rightarrow \infty} \frac{1}{N} \sum_{n=1}^{N}g(X_n) \rightarrow E_{\pi}(g) \approx \sum_j \pi_j g(j), ; a.s. $$

2 본 정리는 마코프체인의 정상분포의 존재성이 보장된 상황에서, 정상분포가 무엇인지 확인하는 데 쓰이는 정리임 We say that $\pi$ satisfies detailed balance if $$\pi_i p_{ij} = p_{ji}\pi_j $$ If $\pi$ satisfies detailed balance, then $\pi$ is a stationary distribution.

pf) WTS : $\pi = \pi P$.

$(\pi P)j = \sum_k \pi_k p{kj} = \sum_k p_{jk}\pi_j$ = $\pi_j$

Appendix : Inference for Markov chains.

그렇다면, 전이행렬 P는 어떻게 추정할 수 있을까?

P의 각 행은, multinomial 분포를 따른다. 즉, MLE를 구하려면, $\hat{p}{ij} = \frac{n{ij}}{n_i}$ 로 구하면 됨.

이 포스트에선 optimization의 elements들에 대하여 살펴보자.

9.1. Unconstrained optimization

Rates of numerical convergence

일반적인 다항함수에서 처럼, 미분 몇 번 한다고 score function의 minima를 찾을 수 있다면 참 좋겠지만, 현실에서 그러한 일이 일어날 리 만무하다.

일반적으로, 딥러닝에서나 ML에서나 우리는 Score function의 개형을 잘 알 수 없기 때문에, 임의의 초기점부터 시작해 계속해서 score function의 값을 줄여가는 iterative 한 방법론들을 많이 사용한다.

이러한 상황에서, 이렇게 iterative 한 방법을 시도한다고 해서, 과연 최적점으로 수렴한다는 보장이 있을지, 그리고 수렴한다면 그 속도가 얼마인지는 민감한 문제가 아닐 수 없다.

• $x_k \to x^$ linearly in case $||x_{k+1} - x^|| \le c||x_k - x^*||$ for some 0 < c < 1
  

• $x_k \to x^$ superlinearly in case $||x_{k+1} - x^|| \le c_k||x_k - x^*||$ with $c_k = o(1)$
  
• $x_k \to x^$ quadratically in case $||x_{k+1} - x^|| \le c||x_k - x^*||^2$ for some c > 0
  

수렴속도는 linear < superlinear < quadratic 이다.

9.2 Algorithms for unconstrained optimization

• Gradient descent

  $x_{k+1} = x_k - \lambda \bigtriangledown f(x_k)$
  $\because f(x_k + tv) = f(x_k) + tv^T\bigtriangledown f(x_k) + \frac{1}{2}t^2v^T\bigtriangledown^2f(x_k + \alpha v)v$ The rate of change of $f$ in the direction of v is $v^T\bigtriangledown f(x_k)$,
  $\min_{||v||=1} v^T\bigtriangledown f(x_k) = \frac{-||\bigtriangledown f||^2}{||\bigtriangledown f||}$ when $v = -\bigtriangledown f / |\bigtriangledown f|$

• Newton diretction : 2차항까지 근사한다

  $v_k = -(\bigtriangledown^2f(x_k))^{-1}\bigtriangledown f(x_k)$
  $\because f(x_k + v) \approx m_k(v) = f(x_k) + tv^T\bigtriangledown f(x_k) + \frac{1}{2}t^2v^T\bigtriangledown^2f(x_k)v$, $\frac{d}{dv}m_k(v) = 0$ implies $v_k = -(\bigtriangledown^2f(x_k))^{-1}\bigtriangledown f(x_k)$

두 방법론의 차이?

• Newton direction은 Hessian 행렬까지 사용하므로, 계산비용이 큰 대신 수렴속도가 훨씬 빠르다

• 일반 GD와 달리 Newton direction은 learning rate를 설정할 필요가 없다.
  
  

• Quasi-Newton Methods Newton Methods는 강력하지만, Hessian 행렬을 계산하는 것은 상당한 부담일 수 있다. Quasi-Newton은 헤시안을 계산하지 않고 iterative하게 근사하는 방법을 제시한다.
  기본적인 아이디어는 다음과 같음.

  $\bigtriangledown f(x_{k+1}) = \bigtriangledown f(x_{k}) + \bigtriangledown^2 f(x_{k+1})(x_{k+1} - x_k) + o(||x_{k+1} - x_k||)$ $\therefore \bigtriangledown^2 f(x_{k+1})(x_{k+1} - x_k) \approx \bigtriangledown f(x_{k+1}) - \bigtriangledown f(x_{k})$ 의 공식을 이용한다.

• Conjugate gradient methods conjugate gradient methods에 기반한 방법도 요긴하게 쓸 수 있다. (공부중)

9.3 Constrained Optimization

다음과 같은 Constrained optimization 상황은 많은 상황에서 발생한다.

(Primal problem) $min f(x)$ subject to
$g_i(x) \le 0, i = 1...m$
$h_i(x) = 0, i = 1,2,...m$

주어진 상황에 대한 Lagrangian은 다음과 같이 표현됨.

$L(x,\lambda,\mu) = f(x) + \sum_i \lambda_ig_i(x) + \sum_i \mu_ih_i(x)$

그리고 이에 대응되는 Dual function을 다음과 같이 정의한다

$l(\lambda, \mu) = \inf_{x \in D_F} L(x,\lambda,\mu)$ where $D_F$ is the intersection of domains of the objective functions and constraints

Dual이라는 단어를 한국말로는 쌍대라고 하는데, 단순히 이해하면 어떠한 문제(primal)을 풀기위해 이와 대응되는 다른 문제를 상정하여 풀이한다고 생각하면 된다.

우리는 이 때, F를 feasible set, 즉 primal problem에서 constraint를 만족하는 x의 공간이라고 둔다.

그렇다면, F위에서 다음이 성립한다. $L(x,\lambda,\mu) = f(x) + \sum_{i=1}^m\lambda_ig_i(x) \le f(x)$

따라서, $p^\star$ : optimal value of primal function, $d^\star$ : optimal value of dual function = $sup_{\lambda \ge 0, \mu} ;l(\lambda, \mu)$ 이라고 할 때,

$d^\star \le p^\star$이 성립한다. 이를 Weak duality 라고 한다.

linear constraints의 경우에, dual problem은 objective functions로 표현이 가능하다. 다음 상황을 보자

primal problem : Minimize $f(x)$ subject to $Ax \le b, Cx = d$
Dual problem : $l(\lambda, \mu) = inf_x(f(x) + \lambda^T(Ax-b) + \mu^T(Cx-d))$ $=inf_x(f(x)+(A^T\lambda + C^T\mu)x - b^T\lambda - d^T\mu))$ $=-sup_x((-A^T\lambda + C^T\mu)x - f(x)) -b^T\lambda -d^T\mu$ $=-f^*(-A^T\lambda + C^T\mu) -b^T\lambda -d^T\mu$

9.4 Strong duality

책에서는 다소 복잡하게 설명했지만, 나는 결론적으로

strong duality holds $\iff p^\star = d^\star$ 라고 이해했다.

Strong duality가 중요한 이유는, 만약 우리가 primal 문제를 풀기 힘들어서 dual problem을 푸는 상황을 생각할 때, dual problem의 해 $\lambda^, \mu^$를 구하면, dual function을 구할 때 $x^$를 $\lambda, \mu$로 표현이 가능했으므로 이를 통해 구한 x는 primal problem의 solution $x^$ 와 동일해지므로, dual problem을 사용하여 primal problem의 정확한 해를 구할 수 있게된다.

9.5 KKT conditions. (Karush-Kuhn-Tucker)

이렇게 strong duality가 중요하다는 것을 알았는데, 그렇다면 strong duality가 성립함을 알 수 있는 조건들이 무엇이 있을까?

Suppose the strong duality holds: $f(x^\star) = l(\lambda^\star, \mu^\star)$ $=inf_{x \in domf}(f(x) + \lambda^{\star T}g(x) + \mu^{\star T}h(x)$ $\le f(x^\star) + \lambda^{\star T}g(x^\star) + \mu^{\star T}h(x^\star) \le f(x^\star)$ which implies
$\sum_{i=1}^m\lambda_i^\star g_i(x^\star) = 0$, 하지만 $lambda \ge 0, g(x^\star) \le 0$이므로, $\lambda_i^\star g_i(x^\star) = 0$, for all $i$

이 조건과 $x^\star$이 Lagrangian의 최소점, 그리고 constraint의 만족여부를 통틀어서 우리는 KKT conditions라고 부른다.

** - KKT Conditions**

• $\bigtriangledown L(x^\star, \lambda^\star, \mu^\star) = 0$

• $g_i(x^\star) \le 0$
  • $h_j(x^\star) = 0$
  • $\lambda_i^\star \ge 0$
  • $\lambda_i^\star g_i(x^\star) = 0$

KKT condition이 만족되는 상황들:

• f is convex, differentiable, each g is convex and differentiable and each h is affine.

• Convex set

C is Convex set if $x, x' \in C$ then $(1-\theta)x + \theta x' \in C$ for any $0 \le \theta \le 1$

Operations on Convex Sets.

• Intersection :

If A and B are convex sets, then $A \cap B$ is a convex set

Example 1 the set of positive-definite matrices $S^+_n$ is convex because..

$H_y = {X|y'Xy > 0}$ is convex for all $y$. $S_n^+= \cap_{y}H_y$ Thus $S_n^+$ is convex.

• Affine transformation

If $S \in R^n$ is convex then $f(S) = {y|y = Ax + b, x \in S }$ is convex. Similarly, $f^{-1}(S)$ is convex if $f(x) = Ax+b$ is an affine map.

• Projection

If S is convex then each projection $\pi(S) = {y|(x,y) \in S }$ is convex.

• Separating Hyperplanes

If C and D are convex, and disjoint then there exists a separating hyperplane between them:
$a^Tx \ge b$ for all $x \in C$ $a^Tx \le b$ for all $x \in D$

• Supporting Hyperplanes

Suppose $x$ is an element of the convex set C. and $x_0$ is in the boundary of C.
There is a Hyperplane H s.t. $H = {x | a^Tx = a^Tx_0}$ and $a^Tx \ge a^Tx_0$ for all $x \in C$

Convex Functions.

• Some terminology

• proper function : A function $f = S \subseteq R^m \to [-\infty, \infty]$ is said to be proper if there is no $x \in S$ with $f(x) = -\infty$ and there is some $x$ with $f(x) \neq \infty$.
  
  

• Effective domain $dom f$ : the set of points where $f$ is finite. i.e, $dom f = {x \in S|f(x) < \infty }$
  
  
• A proper convex function $f$ is $closed$ if it is lower semi-continuous; that is, in case for each $\alpha$ the set ${x:f(x) > \alpha}$ is open.

• 동치명제

  A function $f$ is convex if and only if the $epigraph$ $$epi f ={(x,t) \in R^{n+1} | f(x) \leq t }$$ is a convex set.

• How to show a function is convex? 0차, 1차, 2차 미분의 관점에서 각각 보일 수 있다.

Zeroth-order characterization of convexity :A function $f : R^n \to R$ is convex if and only if $g(t) = f(x + tv)$ is convex for each $x \in dom f$ and $v \in R^n$
특징 : x에 대한 convexity를 t에 대한 convexity로 바꿔버린다.
Example : Log determinant let $f(A) = log det(A)$ then let $g(t) = f(A + tV)$. $g(t) = log det(A + tV) = log det(A) + log det(I + tA^{-1/2}VA^{-1/2})$ $log det(A) + \sum_{i}log(1 + t\lambda_i)$, where $\lambda_i$ is ith eigenvalue of $A^{-1/2}VA^{-1/2}$. Therefore, $f(A)$ is concave.

First-order characterization of convexity : A differentiable function $f : R^n \to R$ is convex if and only if $f(y) \ge f(x) + \bigtriangledown f(x)^T(y-x)$ is convex for every $x,y \in dom f$
특징 : 접선(평면) 성질에 의해 자명.

Second-order characterization of convexity : Hessian 행렬의 non-posivite-definie 성질확인.
Example : log-sum-exp $f(x) = log\sum_{i} exp ; x_i$ is convex.

Functions of Convex Functions

다음은 함수의 convexity를 보존하는 연산들이다.

• Nonnegative weighted sum - trivial

• *Composition with an affine function *

  • If $f : R^n \to R$ is convex and g : $R^m \to R^n$ is affine, givne by $g(x) = Ax + b$, then the composition $(f;o; g)(x) = f(Ax+b)$ is convex.

• pointwise maximum and supremum The maximum of convex functions is convex. Can be shown with the notion of epigraph. similary, $g(x) = sup_{y \in A}f(x,y)$ is convex if $f$ is convex in $x$ for $y \in A$

  • Example : Largest eigenvalue For $X \in S^n$ a symmetric matrix. $\lambda_{max}(X) = sup_{y^Ty = 1}y^TXy$ X is linear for each y s.t. $y^ty = 1$ thus convex. Therefore, $\lambda_{max}(X)$ is convex.

• Composition

  • $f;o;g$ is convex if g is concave and f is convex and nondecreasing
  • $f;o;g$ is concave if g is concave and f is concave and nondecreasing
  • $f;o;g$ is concave if g is convex and f is concave and nonincreasing

Log-Convexity

: $f(x)^\theta f(y)^{1-\theta} \ge f(\theta x + (1-\theta)y)$

Important properties

• The product of log-concave functions is log-concave (trivial)

• If $f:R^{n+m} \to R$ is log-concave then the marginal $g(x) = \int_{R^m} f(x,y) dy$ is log-concave.

  $proof)$ $g(\theta x_1 + (1-\theta)x_2) = \int_{R^m}f(\theta x_1 + (1-\theta)x_2, y)dy$ $\ge \int_{R_m}f(x_1,y)^\theta f(x_2,y)^{1-\theta}dy$ $\ge (\int_{R_m}f(x_1,y)dy)^\theta + (\int_{R^m}f(x_2, y)dy)^{1-\theta}$ By Jensen's ineq

• The convolution $(f \star g)(x) = \int f(x-y)g(y)dy$ of log-concave functions is log-concave.

Conjugate function

The conjugate function $f^*$ of a proper function $f$ is given by

$f^*(y) = sup_{x \in dom f}{<x,y> - f(x)}$. The conjugate is always a convex function : trivial

• If $f$ is differentiable, then $y = \bigtriangledown f(x^*)$

• If f is strictly convex, we can write $\bigtriangledown f^{-1}(y) = x^$, so $f^(y) = <\bigtriangledown f^{-1}(y), y - f(\bigtriangledown f^{-1}(y))$

• Fenchel's inequality From definition, $f(x) + f(x^*) \ge <x,y>$

• Fenchel's duality

  Suppose that $f : R^n \to R \cup {\infty}$ and $g : R^m \to R \cup {\infty}$ are closed proper convex functions and $A \in R^{mn}$ is an m x n matrix. Then
  $inf_{x} {f(x) + g(Ax) } = sup_{\lambda}{-f^\star(A^T\lambda)-g^\star(-\lambda)}$
  proof : by Fenchel's inequality

Question:

• 127p-separating / supporting plane pf
• epigraph convexity pf
• 129p closed convex function??
• 130p zeroth-order pf
• 133p 134p log convexity properties : convolution 의미?

[논문링크] https://academic.oup.com/genetics/article/192/3/1065/5935193

Ancient Human Admixture(Patterson et al. 2012)이다.

발표자료 -> https://github.com/woozins/papers

유전학적 도메인 지식이 많이 필요한 논문이라, 솔직히 말하면 제대로 이해하지 못한 부분도 있지만, 논문을 어떻게 읽는지 배울 수 있었던 좋은 경험이었고, 이 기회로 인해 집단유전학 연구실과 공동연구의 가능성 역시 교수님께서 언급하셔서 앞으로 좋은 기회가 생길 수도 있겠다 싶다.

아이디어

• Admixture graph fitting 에서의 score-function에서 lambda값의 선택에 관한 것. (교수님께서 언급)

느낀 점

• Domain, Theory, Computing 의 균형을 잘 잡는 대학원 생활을 해야 함. 각각에 대하여 어떻게 채울지 생각해보기

EM은 Expectation-Maximization 의 준말이다

Motivation

Example

우리가 알고 있는 단순선형 회귀모델을 생각하자.

$Y_i = X_i\beta + \epsilon_i$ , $i = 1,2,....n$

우리가 일반적으로 가정하는 상황은, $X_1,....X_n$ 그리고 $y_1.... y_n$ 을 알고있는 상황이다.

이 경우에서, $(X_i, y_i), i = 1,2,3...n$ 은 Complete data라고 할 수 있다

만약, 우리가 $y_1 .... y_n$ 을 여전히 알고 있지만, $X_1 ... X_m$ 까지만 알고 $X_{m+1}.... X_n$ $(m < n)$을 모르는 상황에 있을 때, 어떻게 회귀계수 $\beta$ 를 추정하는 것이 좋을까?

이 때는, $(X_1,... X_m, y_1 ... y_n)$ 은 observed data라고 생각 할 수 있고, $X_{m+1} ... X_n$ 은 missing data라고 생각 할 수 있다.

물론, $i = m+1 ... n$ 까지의 데이터를 날리고 추정하는 것도 하나의 방법이지만, EM 알고리즘은 이런 경우에 활용 가능한 최적화 알고리즘을 제공한다.

이와 같은 단순한 문제 뿐만 아니라, missing data problem으로 변환할 수 있는 대부분의 추정문제(보통 latent variable을 도입하는 형태로 많이 이루어진다)에서, EM 알고리즘은 활용될 수 있다.

Algorithm

알고리즘을 설명하기에 앞서, 다음과 같은 용어를 정의한다

• $Y_c$ : Complete Data
• $Y_o$ : Observed Data

EM 알고리즘은 다음의 단계로 구성된다.

E-Step

$Q(\theta | \theta_0) = E_\theta logf(Y_c |Y_o , \theta_0)$ 을 구한다.

What is $Q$ ?

즉, $l(\theta)$의 lower bound를 최대화시키는 작업을 반복하면, $argmax_{\theta};l(\theta)$의 근사치를 찾을 수 있을 것이라는 발상이다.

M-Step

E-step에서 구한 $Q$를 maximize 시키는 새로운 $\theta$ 를 구하고, 이를 새로운 $\theta_0$로 업데이트 시킨다.

Iteration $\theta$ 가 만족스러운 값에 수렴 할때까지 이를 반복한다.

비교적 간단하지 싶으면서도, 왜 이런 알고리즘이 만들어졌는지에 대한 부연설명을 간단히 해보겠다.(본인의 주관적인 의견도 포함되었으니 비판적으로 수용바람)

일단은, 우리가 좋은 모수를 추정하기 위해 하려고 하는 것은, Observed Data $Y_o$ 하에서 Likelihood를 최대화시키는 $\theta$를 찾는 것이다. ($argmax_{\theta};logf(Y_o | \theta)$)

Complete Data $Y_c$의 경우엔, 우리가 비교적 쉽게 log-likelihood를 구할 수 있는 상황이 많다. (motivation part에서의 예시만 봐도 그러하다) 또한, 구하기 쉽지 않다면, latent variable를 도입하여 표현이 용이하게끔 할 수 있다.

그러나, Observed Data $Y_o$의 경우 $logf(Y_o | \theta)$ 를 구하기 힘든 상황이 많다. 당장 motivation의 상황만 보더라도, 저 상황에서의 log-likelihood를 어떻게 표현 할 것인가?

따라서, 비교적 구하기 쉬운 complete data에 관한 log-likelihood를 이용하여 $logf(Y_o | \theta)$ 를 최적화시키는 알고리즘을 고안한 것이 EM알고리즘이라고 생각하면 될 것이다. 이 알고리즘이 어떻게 이를 가능케 하는지는 이어서 설명하도록 하겠다.

Why it works

EM Algorithm은 두 가지 유용한 성질이 있다.

1. EM 알고리즘에 의해 Update 되는 $\theta$는 $logf(\theta | Y_o)$ 를 단조증가 시킨다. (monotonicity)

2. $logf(\theta | Y_o)$ 는 $l$이 bounded from above라는 조건 하에서 특정값 $l^$로 수렴한다. 이 때, $l$이 unimodal이면 $l^$가 global maximum 이 되지만, 일반적으로는 local maximum이다.

(참고 : unimodality) https://en.wikipedia.org/wiki/Unimodality

본 포스트에서는 1번의 증명만을 다루도록 하겠다.

$Q(\theta|\theta^{(p}) = \int logf(Y_c|\theta)k(Y_m|Y_o, \theta^{(p)})dY_m$ $=E_{Y_m|Y_o,\theta^{(p)}}(logf(Y_c|\theta))$ $=l(\theta) + H(\theta|\theta^{(p)})$ $where ; H(\theta|\theta^{(p)}) = \int logk(Y_m|Y_o,\theta)k(Y_m|Y_o,\theta^{(p)})dY_m$
$Q(\theta^{(p+1)}|\theta^{(p)}) = l(\theta^{(p+1)}) + H(\theta^{(p+1)}|\theta^{(p)})$ $Q(\theta^{(p)}|\theta^{(p)}) = l(\theta^{(p)}) + H(\theta^{(p)}|\theta^{(p)})$ $Q(\theta^{(p+1)} \mid \theta^{(p)}) - Q(\theta^{(p)} \mid \theta^{(p)}) = \left{\ell(\theta^{(p+1)}) - \ell(\theta^{(p)})\right} + \left{H(\theta^{(p+1)} \mid \theta^{(p)}) - H(\theta^{(p)})\right}$ $Q(\theta^{(p+1)} \mid \theta^{(p)}) \geq Q(\theta^{(p)} \mid \theta^{(p)})$ by the definition of EM $H(\theta^{(p+1)} \mid \theta^{(p)}) \leq H(\theta^{(p)} \mid \theta^{(p)})$ by the following using Jensen’s inequality
$\begin{aligned} &\int \log , k(Y_m \mid Y_0, \theta^{(p+1)}) k(Y_m \mid Y_0, \theta^{(p)}) dY_m - \int \log , k(Y_m \mid Y_0, \theta^{(p)}) k(Y_m \mid Y_0, \theta^{(p)}) dY_m \ &\quad = \int \log \left( \frac{k(Y_m \mid Y_0, \theta^{(p+1)})}{k(Y_m \mid Y_0, \theta^{(p)})} \right) \times k(Y_m \mid Y_0, \theta^{(p)}) dY_m \leq \log \int k(Y_m \mid Y_0, \theta^{(p+1)}) dY_m = 0 \end{aligned}$ $\text{Therefore } \ell(\theta^{(p+1)}) \geq \ell(\theta^{(p)}).$

Application

(작성중)

Reference

• 서울대학교 통계학과 응용통계1 강의록
• https://velog.io/@claude_ssim/기계학습-Expectation-Maximization-EM

2023년 12월 27일 학교에서 수강한 특강내용을 바탕으로 함.

Linux Shell

누군가, 빅데이터를 현업에서 처리하려면 Linux 사용법을 아는 것이 중요하다고 말하지만, window만에 익숙해져 있는 사람들에게 크게 와닿진 않았을 것이다.

Windows와 Linux의 차이점에서 출발하자.

GUI (windows) vs CUI (linux)

Windows는 사용자의 편의를 위해, Terminal을 시각화한 GUI(graphic user interface)를 제공하고, 이를 처리하는 데에는 수많은 컴퓨팅 자원들이 사용될 것이다.

반면 Linux의 경우엔, (linux shell) CUI만으로 데이터 처리를 하도록 할 수 있기 때문에, 컴퓨팅 자원의 사용이 적고, 이는 즉 더 큰 데이터에 대한 처리가 용이함을 의미하기도 한다.

여기서 말하는 더 큰 데이터란, 평소에 우리가 볼 일 없는, GB나 TB로도 표현이 불가능한 그런 사이즈 일 것이다. 실제로, 처리되는 데이터의 용량은 해마다 기하급수적으로 늘고있다..

특강에서는, Linux shell 명령어를 쉽게 배울 수 있도록 만들어진 GameShell 프로그램 으로 흥미롭게 명령어들을 배울 수 있었다.

*GameShell 사용법은 다음과 같다. *

https://github.com/mybirth0407/2023-stat-bigdata-computing <특강 강사님이 준비해주신 github 사이트>

에서 새로운 codespace를 만들고,

터미널에 다음을 입력한다.

./init.sh

리눅스 문법에 따르면, init.sh라는 파일을 실행한다는 의미임.

그 후 위 사진과 같이,

cd GameShell ./start.sh

을 입력하면, 흥미로운 프로그램이 하나 실행될 것이다.

배운 명령어<수정중> ls ls -a(숨김파일도 보여줌) ls -l(수정날짜와 같은 정보 보여줌) ls -al(ls -a + ls -l) ls -R : (경로이하 모든 파일 출력)

pwd : print working directory

cd : change directory cd - : 상위 디렉토리로 cd .. : 과거 디렉토리로

tree : 디렉토리 트리로 보여줌

rm : remove mv : move : mv file1 file2 ..... DIRECTORY (디렉토리 앞의 물결은 어떤의미더라?) mkdir : make directory cp : copy

.파일명 : 숨김파일 <와일드카드> : ? * ex) 정우진을 찾을 때 정?진 정?? 정*

alias A = 'B' : 명령어에 별칭붙이기

nano echo

find 명령어 : 검색할때 강력한 툴 - 눈으로만 보고 파일위치를 찾을순 없다 - 검색속도에 최적화됨 ex) find 찾을경로(생략시 현재경로) -name(-type, -iname:대소문자무시) 패턴(ex 정?진)

문제의 발생

VSCODE를 처음 설치하고 돌리던 중, 다음과 같은 에러가 발생한다.

파이썬 인터프리터를 vscode에 연결시키고 돌린 코드에서 뜬 것 인데, 웹서핑을 해보니 시스템 환경변수 PATH에,

이런식으로 아래의 3줄을 추가하는 것이 해결책이었다.

환경변수?

환경 변수(環境 變數, 영어: environment variable)는 프로세스가 컴퓨터에서 동작하는 방식에 영향을 미치는, 동적인 값들의 모임이다. (출처 : 위키백과)

여기서 '동적'인 값이라는 것은 변경이나 수정이 자유롭다는 뜻으로 이해했다. 이 정의에 의하면 좀 두루뭉실하긴 한데, 그래서 이 중에 PATH라는 환경변수가 의미하는 것이 무엇인지 살펴본다.

PATH: 디렉터리 경로의 목록. 사용자가 전체 경로를 지정하지 않고 명령을 입력하면 이 목록을 확인하여 해당 명령어가 경로에 속하는지를 살펴본다.

즉, PATH는 일종의 디폴트 주소 같은거다. 명령에 전체 경로가 지정되어있지 않으면, path에 속하는 경로에 있는지 자동으로 살펴본다는 것이다.

ERROR의 이해

그럼 위의 문제의 해결책이 왜 환경변수를 설정하는 것인지 살펴보자.

일단 명령어 부분을 보면, conda라는 명령어는 저 디렉토리 내에서확인할 수 있는 명령어가 아니다. 왜냐하면 난 anaconda를 C:\anaconda 라는 폴더에 설치했기 때문이다.

그랬기 때문에, 터미널은 conda라는 명령어를 인식할 수 없었지만, path변수에 C:\anaconda라는 폴더를 추가함으로써, 출처를 알 수 없는 conda라는 명령어를 path경로를 통해서 식별할 수 있어 문제가 사라진 것이라고 판단하였다.

이 포스팅은 ai대학원 / 데이터사이언스 대학원입시를 다루고 있지 않습니다. 일반 통계대학원(서울대 통계학과, 고려대 통계학과, 성균관대 등..) 입시를 경험한 후기를 적은 글입니다.

AI, 데이터사이언스 등에 대한 관심이 높아짐에 따라, 요즘엔 통계대학원도 상당히 경쟁률이 셉니다. 제가 생각하는 이유를 몇 가지 추리자면,

1. 통계학이란 학문 분야의 특성 상, 대학원 진학이 유리한 측면이 있음. 즉 대학원을 갔을 때의 Return이 타과에 비해 높은 편이 아닌가 생각합니다.

   
   

2. AI, 데이터사이언스에 대한 높은 관심. 이는 통계학과/수학과 학부생 뿐만 아니라 문이과 막론 타과생들의 엄청난 유입으로 이어집니다.

   
   

3. 취업시장 침체 : 올해 특히 그랬던 것 같습니다. 물론 매년 나오는 말이긴 하죠. 등등등...

통계대학원 입시에 도전한 이유

네. 솔직해지겠습니다. 취업할 자신이 없어서 입시를 시작했어요.

제 스펙은 다음과 같습니다.

• 인서울 중상위권 통계학과 군필남자, 24년 2월 학부 졸업예정(군휴학 3학기, 1학기 조기졸업)

• 학점은 좀 높은편(전체평점 4.15, 전공평점 4.3~4.4?)

• 수학, 코딩은 공부만 해봤고 프로젝트 경험 등 전무

  23년 초에, 졸업 후 어떤 진로를 선택할 것인지에 대한 고민을 많이 했습니다. 주변 친구들의 경우, 보험계리사 시험에 도전하거나, ai/데이터 공모전을 참여하여 스펙을 쌓으려는 친구이 다수 있었습니다. 저의 경우엔, 학부생활을 해오면서 대학원 진학이 제 전공을 살려서 취업하는 데 어느정도는 필요하다고 생각을 하고 있었고, 그렇다고, 포트폴리오를 많이 보는 ai대학원을 가자니 제 코딩능력이나 프로젝트 경험에 대한 자신감이 없었습니다.

  다만, 저는 학부생활을 하면서 수리통계학적 센스에 대한 어느정도의 자신감은 있었기 때문에, 일반 통계대학원 진학 후 대학원에 들어가 데이터사이언스나 ai/ml쪽을 공부하기로 방향성을 잡고 입시준비를 시작했습니다.

통계대학원 입시 준비?

제가 목표로 잡은 학교는, 서울대 통계학과 대학원과 고려대 통계학과 대학원 입니다. (연세대 통계데이터사이언스 대학원도 지원은 했으나, 서울대, 고려대와는 다소 방향성이 다르다고 생각하며, 저는 연세대가 추구하는 방향으로 입시를 준비하지는 않았습니다)

*일반 통계대학원 입시는 굉장히 간단합니다. *

일반적으로 통계대학원은, 입학시험이 따로 있습니다. 이 시험엔 수리통계학과 회귀분석 과목을 기반으로 평균적으로 5문제정도 출제되는 것 같습니다. 그리고, 입학시험 성적은 입시에 지대한 영향을 미칩니다. 보다 정확히 말하면, 입시에 반영할 유의미한 요소가 지필시험 성적이 거의 전부를 차지한다고 보시면 될 것 같습니다.

• 왜냐하면, 일반 통계대학원은 타 대학원과 달리 사전 컨택을 받지 않습니다. (물론 학교마다 다르겠지만, 서울대/고대의 경우엔 확실히 그러합니다)

• 학점의 경우, 당연히 높을수록 좋겠지만, 학점 또한 지필고사 성적에 대한 가산요소 정도로만 생각된다고 생각합니다. 개인적 경험으론 서울대에선 크게 신경쓰는 느낌은 아니었고, 고대에선 면접에서 약간의 가산요소는 되었다고 생각합니다.

• 사전 포트폴리오 역시 당연히 도움은 되겠지만, 저의 경우 포트폴리오가 전무했음에도 불구하고 입시에 큰 걸림돌이 되지는 않았습니다.

결론적으로 말하면, 통계대학원 입시를 성공적으로 하시기 위해선 지필고사 성적을 높게 받는 것이 가장 중요하며, 다른 부분에서는 큰 하자만 없으면 큰 걸림돌이 되지는 않을 것입니다.

지필고사 준비

보통 지필고사 시험범위는 '수리통계학'과 '회귀분석' 단 두 과목입니다.

통계학과 학부 4년간 배우는 것을 단 두 과목으로 요약하라면 당연히 위의 두 과목이 나올 것입니다. 그만큼 핵심적인 과목들이죠.

_<서울대가 목표가 아니라면>_ 만약 수학적 베이스가 있으신 분들이라면, 위 두 과목만 적절한 교재 한 권씩 보셔도 대부분의 학교를 준비하시는 데에 큰 문제가 없을 것이라고 생각합니다. 입시 준비기간은 개인차가 있으므로 제가 따로 언급하지는 않겠습니다만, 일반적으로 4개월 이상은 권장하는 분위깁니다.

만약 수학적 베이스가 없으신 분들이라면, 위 두 과목을 하시기 전에 대학 미적분과 행렬대수 공부가 추가적으로 필요하실 겁니다. 행렬대수는 주로 회귀분석의 중회귀 부분에서 핵심적으로 사용되기에 봐두셔야 회귀분석내용을 온전히 이해하실 수 있으실 겁니다. 행렬대수는 통계학에서 사용되는 선형대수, 행렬의 일부분들을 집중적으로 다루는 과목인데, 개인적으론 '통계학을 위한 행렬대수학' 이라는 교재를 추천합니다.

• 교재추천 : 수리통계학 -> 전명식, 송성주 저 회귀분석 -> 박성현 저 또는 montgomery 저 ->원서입니다. 행렬대수학 -> 통계학을 위한 행렬대수학 / 출판사 : 자유아카데미

_<서울대를 목표로 한다면>_ 서울대 지필고사는 타 학교에 비해 많이 어려운 편입니다.

수리통계학과 회귀분석이라는 출제범위는 여전히 동일하지만, 위에서 추천된 교재만 풀어서는 합격가능성이 낮습니다. 또한, 서울대를 준비하실 땐 시간여유가 있으시다면 기초해석학 내용도 한번 읽어보시는 게 서울대용 수리통계학을 준비하실 때 도움이 되실 겁니다.

-교재추천 수리통계학 -> 김우철 저 : 거의 고정으로 사용되는 교잽니다. 회귀분석 -> 박성현 저 & linear models in statistics(alvin C. Rencher)의 일부분 + 서울대 강의노트(구글링해서 찾으실 수 있습니다. 개인사이트라 주소를 따로 올리진 않겠습니다) 해석학 -> 해석개론(김김계) 행렬대수학 -> 통계학을 위한 행렬대수학 / 출판사 : 자유아카데미

특히 수리통계학은, 모든 연습 문제를 마스터하신다고 생각하고 공부하시는게 안전합니다. 문제는 김우철 수리통계학에 수록된 연습문제들의 난이도가 상당해서, 책을 마스터하려면 상당한 시간이 걸릴겁니다. 개인적으론 서울대 입시를 완벽히 준비하는데 6개월 이상은 필요하다고 봅니다. 제 경우 김우철 수통은 거의 10회독 가량 했던 것 같습니다. 그만큼 책이 쉽지 않습니다.

입시 결과

저는 서울대를 목표로 위와 같이 공부해서,

24년 전기 서울대 통계학과 입시에 합격할 수 있었습니다.

수통, 회귀외에 아무것도 모르는 제게 과분한 성과라고 생각하고, 새로운 기회를 얻은 만큼 2년간 한번 열심히 달려보려고 합니다.

누군가 통계대학원 입시를 준비하시는 분이 계신다면, 이 글을 보고 많은 도움이 되셨으면 좋겠습니다. 감사합니다!

과외관련 comment

통계대학원 입시관련 과외 문의를 주시는 분들이 많은데, 저는 직접 과외하는 것을 계획중에 있지는 않습니다.

다만, 제 대학원 동기 분 중 고려대 통계대학원 입시 관련 과외를 훌륭히 하고 계신 분이 있어, 링크를 공유 드리려고 합니다.

통계대학원 과외 대학원 진학에 있어 도움이 되셨으면 좋겠습니다..!

1. Bootstrap 이용 여부

• random forest 는 부트스트랩 샘플링을 사용하지만, extra trees는 이를 사용하지 않고 original dataset을 사용함

2. 트리 분할 시 변수 선택 과정

• 각각의 알고리즘에서 만들어지는 다수의 트리 중 하나의 트리를 생각하자.

  random forest의 경우, 각각의 트리에서, bootstrap 샘플링된 데이터를 바탕으로 랜덤한 features들을 사용하여 만들 수 있는 최적의 트리를 생성한다.

-반면, extra tree의 각각의 트리에서는, original data를 바탕으로(차이점 1) 랜덤한 feature들을 사용하지만, (랜덤포레스트와 동일) 최적의 트리를 만드는 것이 아니라, 각각 split 지점에서 무작위의 feature을 선택하여 그 feature에 대한 최적의 partition을 찾아 split을 진행한다.(랜덤성과 최적성)

extra tree는 random forest에 비해 randomness가 더 가미된 모델이지만, 역시 optimization 도 포함된 모델이다.

extra tree는 random forest 에 비해..

1. 연산량이 적다

2. 일반적으로 랜덤성이 증가하면, 모델의 bias가 증가하지만 variance는 감소함

그러나 일반적으로는 random forest가 더 선호된다.