[Manifold Learning] IsoMap, LLE, t-SNE 설명

Manifold Learning

여기서 매니폴드 학습은 데이터 분포의 비선형(non-linear) 구조를 직접적으로 고려합니다.

즉, Nonlinear Dimensionality Reduction 문제를 봅니다.

1. Manifold?

위상수학에서 개발된 매니폴드와 이론과 달리, 기계학습에서는 개념적으로 다룹니다.

주로 고차원 공간에 내재한 저차원 공간을 매니폴드라고 합니다.

매니폴드는 보통 비선형 구조를 가지며, 특정 점을 중심으로 인근만 살피면 선형 구조에 가깝습니다.

기계학습에서 trainset에 있는 샘플은 매니폴드 위 또는 매니폴드에 가까이 있습니다.

훈련집합 샘플 $x = (x_1, x_2, \cdots, x_d)^T$ 는 $d$차원 공간의 한 점입니다. 데이터는 보통 매우 높은 차원 공간에 분포합니다. 그런데 샘플은 d차원에 무작위로 분포하는 것이 아니라, d보다 훨씬 낮은 차원 공간에 분포합니다.

물론 이 분포에 조금 떨어진 샘플도 존재할 것입니다. 그래서 매니폴드 인근에 집중되어 있다고 하며, 이를 매니폴드 가정(manifold hypothesis)라고 합니다.

위 그림에서 (a)는 3차원 상의 데이터를 2차원 평면에서 충분히 구별 가능한 상황으로 만들었고,

(b)는 한 차원은 직선이고, 한 차원은 곡선인 2차원 swiss roll 구조를 한 매니폴드 공간을 보여줍니다.

2. IsoMap

최근접 이웃 그래프(Nearest neighbor graph) (Tenenbaum, 2000)

1) 각 점에 대한 k-nearest neighbor을 찾고, 유클리디언 거리를 계산하여 거리 행렬(distance matrix) M에 기록합니다. 이 단계를 마치면, 각 행은 k개의 요소만 0이 아닌 값, 나머지는 0이 됩니다.

2) 두 점 사이 최단경로(shortest path)를 Floyd 알고리즘을 이용하여 M의 0인 값들을 계산합니다. 위 그림에서 빨간색이 최단 경로입니다. 이렇게 구한 M은 n x n 행렬로 데이터 분포의 비선형 구조를 잘 반영합니다.

IsoMap

M의 고유벡터(eigen vector)를 구하고, 고윳값(eigen value)이 큰 순서대로 $d_{low}$ 개의 고유 벡터를 선택합니다. 이 고유벡터는 새로운 저차원 공간을 생성합니다. 이 때 고유벡터가 d차원이 아닌 n차원이므로 투영을 이용하여 저차원 변환하지 않습니다.

일반적으로 2차원 공간으로 변환한다면, 훈련집합 $\mathbb{X} = {x_1, x_2, \cdots, x_n}$은
$$
{(\sqrt\lambda_1 v_1^1, \sqrt\lambda_2 v_2^1)^T, (\sqrt\lambda_1 v_1^1, \sqrt\lambda_2 v_2^2)^T, \cdots, (\sqrt\lambda_1 v_1^1, \sqrt\lambda_2 v_2^n)^T}
$$
이 됩니다.

여기서 $\lambda_1$은 가장 큰 고윳값이고, $v_1^i$는 이 고윳값에 해당하는 고유 벡터의 i번째 요소입니다.

마찬가지로 $\lambda_2$ 는 두번째로 큰 고윳값이고, $v_2^i$는 이 고윳값에 해당하는 고유 벡터의 i번째 요소입니다.

IsoMap은 distance matrix M을 구할 대 k를 적절하게 설정해야 합니다. 너무 크면 최단 경로를 사용해야 하는데, 유클리디언 거리를 사용하는 문제가 생기고, 너무 작게 설정하면 멀리 있는 샘플 쌍 사이 경로가 없어 불연속 공간이 되는 문제가 발생합니다.

또한 훈련집합 크기가 커지면 M의 크기가 너무 커져 메모리 문제가 발생하기도하고, 고유벡터를 구하는 수치적 문제가 생기기도 합니다. 이를 처리하기 위한 알고리즘은 (Talwalkar, 2013)에 나와 있습니다.

문제를 정리하면)

1) Floyd 알고리즘은 $O(N^3)$ 시간이 걸려 매우 오래걸립니다.

2) IsoMap이 사용하는 distance matrix M은 밀집행렬이어서 고유벡터를 구하는데 어려움이 있습니다.

3. LLE(Locally Linear Embedding)

LLE는 IsoMap과 비슷한점 많지만, 이를 개선한 방법입니다. (Roweis, 2000)

거리 행렬 M 대신, 함수 $\epsilon$ 을 최소로 하는 가중치 행렬 $W$ 를 사용합니다.
$$
\epsilon(W) = \sum_{i=1}^{n} \Vert x_i - \sum_{x_j \in {x_i의 이웃}} w_{ij}x_j \Vert^2_2
$$

위 그림은 k = 5 인 상황입니다. $x_i$ 와 이웃한 점 5개를 골라 weighted sum이 $x_i$와 가장 근접해지는 가중치 $W$ 를 찾습니다.

이렇게 구한 가중치 행렬 $W$ 은 $d$차원의 원래 공간에 분포한 데이터의 비선형 구조 정보를 잘 담고 있다고 할 수 있습니다. LLE는 $W$를 이용하여 $d_{row}$ 차원의 새로운 공간에서의 점 $y$를 구합니다.

$$
\phi(\mathbb{X'}) = \sum_{i=1}^{n} \Vert y_i - \sum_{y_j \in {y_i의 이웃}} w_{ij}y_j \Vert^2_2
$$
이 때 위 식을 이용해서 목적함수 $\phi$를 최소화하는 점의 집합 $\mathbb{X'}$를 구합니다.

LLE가 사용하는 가중치 행렬 $W$ 는 각 행이 k개의 요소만 0이 아니고, 나머지는 0인 희소행렬이므로 최적해를 구하기가 쉽습니다.

4. t-SNE (t-Distributed Stochastic Neighbor Embedding)

다양한 데이터 실험에서 월등한 성능을 보이는 알고리즘입니다.(Maaten, 2008)

다음은 MNIST 숫자 샘플 60,000개중 6,000를 뽑아 784차원을 2차원으로 변환한 결과입니다.

t-SNE는 $x_i$와 $x_j$의 유사도를 조건부 확률로 측정합니다. 이 식은 가우시안 분포를 닮았는데, $x_i$와 가까운 샘플은 높은 확률을, 먼 샘플에는 0에 가까운 확률을 부여합니다.
$$
p_{j|i} = \frac{exp(-\frac{\Vert x_i - x_j \Vert^2_2}{2\sigma_i^2})}{\sum_{k \neq i}exp(-\frac{\Vert x_i - x_k \Vert^2_2}{2\sigma_i^2})}
$$

$\sigma_i$는 $x_i$ 주변 데이터 분포에 따라 결정되는데, 데이터가 밀집될수록 작은 값을 가집니다.

이 식을 바탕으로, $p_{j|i} = p_{i|j}$ 를 만족하도록 (대칭이 되도록) 식을 재정의 합니다.
$$
p_{ij} = p_{ji} = \frac{p_{j|i} + p_{i|j}}{2n}
$$

변환된 공간에서 유사도는 가우시안 분포대신 t분포(Student's t)를 사용합니다. 스튜던트 t분포는 원점에서 멀어질수록 가우시안보다 0에 덜 가까운 두꺼운 꼬리(heavy-tail)성질을 가진 분포입니다.

변환 공간에서의 점을 y라고 표기하면, $y_i$와 $y_j$의 유사도는 다음과 같이 정의할 수 있습니다.
$$
q_{ij}= \frac{(1 + \Vert y_i - y_j \Vert^2_2)^{-1}}{\sum_{k \neq l }(1 + \Vert y_k - y_l \Vert^2_2)^{-1}}
$$
$q_{ii} = 0$ 입니다.

원래 공간에서 데이터 구조가 변환 공간에서 유지되어야 하므로,

원래공간의 P확률분포와 변환 공간 Q확률 분포 가깝게 되어야 합니다.

따라서 두 확률분포의 KL-divergence를 목적함수로 사용합니다.

변환된 샘플 집합을 $\mathbb{X'} = {y_1, y_2, \cdots, y_n}$ 라고 합시다.
$$
J(\mathbb{X'}) = KL(P \Vert Q)= \sum_{i=1}^n \sum_{j=1}^n p_{ij} log(\frac{p_{ij}}{q_{ij}})
$$
이를 최소로하는 $\mathbb{X'}$를 찾기 위해, 경사하강법을 이용합니다.

다음은 $J$ 목적함수를 $y_i$로 미분하여 얻은 그레디언트 입니다.
$$
\frac{\partial J}{\partial y_i} = 4 \sum_{j=1}^n (p_{ij} - q_{ij})(y_i - y_j) (1 + \Vert y_i - y_j \Vert^2_2)^{-1}
$$
이를 이용하여 최종 알고리즘은 다음과 같습니다.

5. 귀납적(inductive) 학습 모델과 transductive 학습 모델

IsoMap, LLE, t-SNE 출력을 생각해보면, '변환된 데이터' 임을 알 수 있습니다.

PCA나 autoencoder가 최적화된 매개변수를 출력하는 것과는 다르다는 것을 알 수 있습니다.

따라서 t-SNE 등과 같은 알고리즘은 새로운 샘플이 입력되면 처리할 수 없습니다.

기계학습에서는 이처럼 새로운 샘플을 처리할 능력이 없는 모델을 트랜스덕티브(transductive) 학습 모델이라고 합니다. (Vapnik, 1998) (IsoMap, LLe, t-SNE, semi-supervised 그래프 최소분할)

반면, 새로운 샘플을 처리할 수 있는 모델 학습은 귀납적(inductive) 모델 학습이라고 합니다.

주어진 과업이 데이터 가시화(data visulization)라면 트랜스덕티브한 모델의 결과가 더 우월합니다.

PCA는 선형 모델이므로 비선형 구조의 데이터를 제대로 처리할 수 없으며, 오토인코더는 비선형 처리가 가능하지만 데이터의 지역적 구조를 제대로 표현하지 못하기 때문입니다.

한편, t-SNE는 귀납적 모델로 확장이 가능합니다.(Maaten, 2009) 이러한 parametric t-SNE 기법은 RBM을 적층한 전방 신경망 구조를 채택하였고, 학습은 stacked autoencoer와 마찬가지로 층별 예비학습과 fine-tune 단계를 거칩니다. 또한 t-SNE가 사용한 목적함수를 개조해서 매니폴드의 비선형 구조를 제대로 표현합니다.

---

Reference
기계학습, 매니폴드 학습 - 오일석