t-SNE(t-Stochastic Neighbor Embedding)
10 Oct 2020 | Machine-Learning
해당 게시물은 고려대학교 강필성 교수님의 강의를 바탕으로 작성한 것입니다.
t-SNE
t-SNE(t-Stochastic Neighbor Embedding, t-확률적 이웃 임베딩)은 ISOMAP, 지역적 선형 임베딩(Locally Linear Embedding, LLE)과 더불어 많이 사용되는 비선형 구조 데이터를 차원 축소하는 알고리즘입니다.
Stochastic Neighbor Embedding
t-SNE의 핵심이 되는 SNE(Stochastic Neighbor Embedding)에 대해 알아보겠습니다. LLE(지역적 선형 임베딩)와 SNE 모두 이웃이 되는 인스턴스를 기준으로 Embedding한다는 공통점을 가지고 있습니다. 하지만 이웃을 선택하는 방법에서 차이점이 있습니다. LLE는 이산적인 접근법으로 이웃을 확정하지만 SNE는 확률적인 방법으로 이웃을 정하게 됩니다. 좀 더 자세히 설명하면 LLE는 가장 가까운 $k$개의 인스턴스(k-Nearest Neighborhood)를 이웃으로 확정한 뒤에는 다른 인스턴스를 고려하지 않습니다. 하지만 SNE는 일정 범위 내의 인스턴스를 모두 고려하되 거리에 따라 확률을 부여하여 고려하게 됩니다. 가까운 인스턴스의 확률은 높고, 멀리 있는 인스턴스의 확률 낮게 반영하는 식으로요. 다시 말해, 확률적으로 지역성을 결정하겠다고 말할 수 있겠습니다.
고차원에서 특정 인스턴스 쌍을 이웃으로 선택할 확률을 $p$로 나타내고, 차원 축소를 하여 저차원에서 특정 인스턴스 쌍을 이웃으로 선택할 확률을 $q$로 나타내면 아래와 같습니다.
\[\color{blue}{p_{i\vert j}} = \frac{\exp(-\frac{\Vert\color{blue}{\mathbf{x}_i - \mathbf{x}_j}\Vert^2}{2\sigma^2_i})}{\sum_{k\neq i}\exp(-\frac{\Vert\color{blue}{\mathbf{x}_i - \mathbf{x}_k}\Vert^2}{2\sigma^2_i})} \qquad
\color{red}{q_{i\vert j}} = \frac{\exp(-{\Vert\color{red}{\mathbf{y}_i - \mathbf{y}_j}\Vert^2})}{\sum_{k\neq i}\exp({\Vert\color{red}{\mathbf{y}_i - \mathbf{y}_j}\Vert^2})}\]
위 수식에서 $p$는 원 데이터의 차원에서 인스턴스 $i$가 인스턴스 $j$를 이웃으로 선택할 확률이며, $q$는 축소된 차원에서 인스턴스 $i$가 인스턴스 $j$를 이웃으로 선택할 확률입니다. $p,q$ 를 나타내는 수식은 비슷하게 생겼습니다. 우선 거리가 멀어질 수록 낮은 확률값을 할당하기 위해서 $y=e^{-x}$를 사용합니다. 이 함수에서는 $x$가 커질수록 함숫값이 작아지기 때문에 서로의 거리가 먼 인스턴스가 이웃으로 정해질 확률이 작아지게 됩니다. $y=e^{-x}$의 그래프는 아래와 같이 생겼습니다.
하지만 몇 가지 차이점도 가지고 있습니다. 먼저 $p$ 는 원래 인스턴스 좌표 $\mathbf{x}$ 에 대한 함수이며, $q$는 축소된 좌표계에서의 인스턴스의 좌표 $\mathbf{y}$에 대한 함수입니다. 그리고 $p$ 를 구하는 식에는 거리에 따른 확률값 차이를 얼마나 줄 것인지를 조정하는 $\sigma$ 가 있습니다. 이 값이 커지면 멀리 있는 인스턴스의 확률이 상대적으로 커지게 되고, 작게 하면 멀리 있는 인스턴스가 이웃으로 선택될 확률이 작아지게 됩니다. 실제로는 $\sigma$ 값이 $[5,50]$ 범위 중 어떤 값을 같더라도 t-SNE 자체가 실제로 강건(Robust)하게 작동하기 때문에 큰 고민없이 기본(Default)값으로 사용하는 것이 일반적입니다.
Cost function
우리의 목적은 두 확률 분포 $p,q$를 동일하게 만드는 것입니다. 따라서 이를 계산하기 위한 쿨백-라이블러 발산(Kullback-Leibler divergence, KLD)을 사용하여 두 값을 비교하게 됩니다. 쿨백-라이블러 발산은 비대칭(non-symmetric)이기 때문에 거리를 나타내는 수치는 아니지만 두 값의 엔트로피를 비교함으로써 목적함수로 사용됩니다. 수식으로 나타내면 아래와 같습니다.
\[C = \sum_i KL(\color{blue}{P_i}\Vert \color{red}{Q_i}) = \sum_i\sum_j \color{blue}{p_{i\vert j}} \log \frac{\color{blue}{p_{i\vert j}}}{\color{red}{q_{i\vert j}}}\]
두 확률 분포가 완전히 동일할 때 목적 함수의 값은 0이 되며 확률 분포가 달라질수록 목적 함수의 값은 커지게 됩니다.
Gradient Descent
이제 목적 함수가 최소인 지점을 찾기 위해서 경사 하강법을 사용하겠습니다. $\mathbf{x}$값은 이미 정해져 있고, 우리가 필요한 것은 위 값을 최소로 만드는 $\mathbf{y}$입니다. 그렇기 때문에 $\mathbf{y}$로 편미분한 그래디언트를 구합니다. 수식으로 나타내면 아래와 같습니다.
\[\begin{aligned}
C &= \sum_i\sum_j \color{blue}{p_{i\vert j}} \log \frac{\color{blue}{p_{i\vert j}}}{\color{red}{q_{i\vert j}}} \\
&= \sum_i\sum_j \color{blue}{p_{i\vert j}} \log \color{blue}{p_{i\vert j}} - \sum_i\sum_j \color{blue}{p_{i\vert j}} \log \color{red}{q_{i\vert j}} \\
C^\prime &= - \sum_i\sum_j \color{blue}{p_{i\vert j}} \log \color{red}{q_{i\vert j}} \\
&= -\sum_i \color{blue}{p_{t\vert i}} \log \color{red}{q_{t\vert i}} - \sum_j \color{blue}{p_{j\vert t}} \log \color{red}{q_{j\vert t}} - \sum_{i \neq t}\sum_{j \neq t} \color{blue}{p_{i\vert j}} \log \color{red}{q_{i\vert j}}
\end{aligned} \\
\because \frac{\partial C}{\partial y_t} = \frac{\partial C^\prime}{\partial y_t}\]
다음은 위 식의 각 항을 $\mathbf{y}$ 로 미분한 식을 구할 차례입니다. 식을 구하기 과정을 좀 더 간단하게 하기 위하여 계산 과정에서 나올 항을 다음과 같이 치환하도록 하겠습니다.
\[d_{ti} = \exp(-\Vert \color{red}{\mathbf{y}_t - \mathbf{y}_i}\Vert^2) = d_{it}\]
이를 활용하면 몇 가지 항을 아래와 같이 나타낼 수 있습니다.
\[\frac{\partial d_{it}}{\partial \mathbf{y}_t} = d^\prime_{ti} = -2(\Vert\mathbf{y}_t-\mathbf{y}_i\Vert) \exp(\Vert\mathbf{y}_t-\mathbf{y}_i\Vert^2) = -2(\mathbf{y}_t-\mathbf{y}_i)d_{ti}\\
q_{t\vert i} = \frac{\exp(\Vert\mathbf{y}_i-\mathbf{y}_t\Vert^2)}{\sum_{k \neq i} \exp(\Vert\mathbf{y}_i-\mathbf{y}_k\Vert^2)} = \frac{d_{it}}{\sum_{k \neq i}d_{ik}}\\
q_{j\vert t} = \frac{\exp(\Vert\mathbf{y}_t-\mathbf{y}_j\Vert^2)}{\sum_{k \neq t} \exp(\Vert\mathbf{y}_t-\mathbf{y}_k\Vert^2)} = \frac{d_{tj}}{\sum_{k \neq i}d_{tk}}\\
q_{i\vert j} = \frac{\exp(\Vert\mathbf{y}_j-\mathbf{y}_i\Vert^2)}{\sum_{k \neq i} \exp(\Vert\mathbf{y}_j-\mathbf{y}_k\Vert^2)} = \frac{d_{ji}}{\sum_{k \neq j}d_{jk}}\]
이제 이를 사용하여 본격적으로 각 항을 미분한 식을 구해보겠습니다. 첫 번째 항을 미분한 값은 아래와 같이 구해집니다.
\[\begin{aligned}
\frac{\partial}{\partial \mathbf{y}_t}\bigg(-\sum_i \color{blue}{p_{t\vert i}} \log \color{red}{q_{t\vert i}}\bigg)
&= -\sum_i \color{blue}{p_{t\vert i}}\cdot \frac{1}{\color{red}{q_{t\vert i}}}\cdot \frac{\partial \color{red}{q_{t\vert i}}}{\partial y_t} \\
&= -\sum_i \color{blue}{p_{t\vert i}}\cdot \frac{1}{\color{red}{q_{t\vert i}}}\cdot \frac{d^\prime_{it}(\sum_{k \neq i}d_{ik}) - d_{it}d^\prime_{it}}{(\sum_{k \neq i}d_{ik})^2} \\
&= -\sum_i \color{blue}{p_{t\vert i}}\cdot \frac{1}{\color{red}{q_{t\vert i}}}\cdot \frac{-2(\mathbf{y}_t-\mathbf{y}_i)d_{ti}(\sum_{k \neq i}d_{ik}) +2(\mathbf{y}_t-\mathbf{y}_i)d_{ti}^2}{(\sum_{k \neq i}d_{ik})^2}\\
&= -\sum_i \color{blue}{p_{t\vert i}}\cdot \frac{1}{\color{red}{q_{t\vert i}}}\cdot \bigg(-2(\mathbf{y}_t - \mathbf{y}_i) \cdot q_{t\vert i} + 2(\mathbf{y}_t - \mathbf{y}_i) \cdot q_{t\vert i}^2\bigg)\\
&= \sum_i \color{blue}{p_{t\vert i}} \cdot 2(\mathbf{y}_t - \mathbf{y}_i)(1 - q_{t\vert i})
\end{aligned}\]
두 번째 항을 미분한 값은 다음의 과정을 거쳐 구할 수 있습니다.
\[\begin{aligned}
\frac{\partial}{\partial \mathbf{y}_t}\bigg(-\sum_j \color{blue}{p_{j\vert t}} \log \color{red}{q_{j\vert t}}\bigg)
&= -\sum_j \color{blue}{p_{j\vert t}}\cdot \frac{1}{\color{red}{q_{j\vert t}}}\cdot \frac{\partial \color{red}{q_{j\vert t}}}{\partial y_t} \\
&= -\sum_j \color{blue}{p_{j\vert t}}\cdot \frac{1}{\color{red}{q_{j\vert t}}}\cdot \frac{d^\prime_{tj}(\sum_{k \neq t}d_{tk}) - d_{tj}(\sum_{k \neq t}d^\prime_{tk})}{(\sum_{k \neq t}d_{tk})^2} \\
&= -\sum_j \color{blue}{p_{j\vert t}}\cdot \frac{1}{\color{red}{q_{j\vert t}}}\cdot \frac{-2(\mathbf{y}_t-\mathbf{y}_j)d_{tj}(\sum_{k \neq t}d_{tk}) - d_{tj}(\sum_{k \neq t}d^\prime_{tk})}{(\sum_{k \neq t}d_{tk})^2}\\
&= 2\sum_j \color{blue}{p_{j\vert t}} \cdot(\mathbf{y}_t-\mathbf{y}_j) + \sum_j \color{blue}{p_{j\vert t}} \cdot \frac{\sum_{k \neq t}d^\prime_{tk}}{\sum_{k \neq t}d_{tk}} \\
&= 2\sum_j \color{blue}{p_{j\vert t}} \cdot(\mathbf{y}_t-\mathbf{y}_j) + \sum_j \frac{d^\prime_{tj}}{\sum_{k \neq t}d_{tk}} \\
&= 2\sum_j \color{blue}{p_{j\vert t}} \cdot(\mathbf{y}_t-\mathbf{y}_j) -2 \sum_j (\mathbf{y}_t-\mathbf{y}_j) \cdot \frac{d_{tj}}{\sum_{k \neq t}d_{tk}}\\
&= 2\sum_j \color{blue}{p_{j\vert t}} \cdot(\mathbf{y}_t-\mathbf{y}_j) -2 \sum_j (\mathbf{y}_t-\mathbf{y}_j) \cdot \color{red}{q_{j\vert t}} \\
&= 2\sum_j (\mathbf{y}_t-\mathbf{y}_j) \cdot (\color{blue}{p_{j\vert t}} - \color{red}{q_{j\vert t}})
\end{aligned}\]
마지막으로 세 번째 항을 미분한 값을 구해보겠습니다.
\[\begin{aligned}
\frac{\partial}{\partial \mathbf{y}_t}\bigg(-\sum_{i \neq t}\sum_{j \neq t} \color{blue}{p_{i\vert j}} \log \color{red}{q_{o\vert j}}\bigg)
&= -\sum_{i \neq t}\sum_{j \neq t} \color{blue}{p_{i\vert j}}\cdot \frac{1}{\color{red}{q_{i\vert j}}}\cdot \frac{\partial \color{red}{q_{i\vert j}}}{\partial y_t} \\
&= -\sum_{i \neq t}\sum_{j \neq t} \color{blue}{p_{i\vert j}}\cdot \frac{1}{\color{red}{q_{i\vert j}}}\cdot \frac{d^\prime_{ji}(\sum_{k \neq j}d_{jk}) - d_{ji}d^\prime_{jt}}{(\sum_{k \neq j}d_{ji})^2} \\
&= -\sum_{i \neq t}\sum_{j \neq t} \color{blue}{p_{i\vert j}}\cdot \frac{1}{\color{red}{q_{i\vert j}}}\cdot \frac{2(\mathbf{y}_t-\mathbf{y}_i)d_{ji}d_{jt}}{(\sum_{k \neq j}d_{jk})^2}\\
&= -\sum_{i \neq t}\sum_{j \neq t} \color{blue}{p_{i\vert j}}\cdot \frac{1}{\color{red}{q_{i\vert j}}}\cdot 2(\mathbf{y}_t - \mathbf{y}_i) \cdot q_{i\vert j}\cdot q_{t\vert j}\\
&= -\sum_{i \neq t}\sum_{j \neq t} \color{blue}{p_{i\vert j}} \cdot 2(\mathbf{y}_t - \mathbf{y}_i) \cdot q_{i\vert j}
\end{aligned}\]
첫 번째 항을 미분하여 나온 식과 세 번째 항을 미분하여 나온 식을 더한 후에 정리해보겠습니다.
\[\begin{aligned}
&\sum_i \color{blue}{p_{t\vert i}} \cdot 2(\mathbf{y}_t - \mathbf{y}_i)(1 - q_{t\vert i}) -\sum_{i \neq t}\sum_{j \neq t} \color{blue}{p_{i\vert j}} \cdot 2(\mathbf{y}_t - \mathbf{y}_i) \cdot q_{i\vert j} \\
=&\sum_j \color{blue}{p_{t\vert j}} \cdot 2(\mathbf{y}_t - \mathbf{y}_j)(1 - q_{t\vert j}) -\sum_{i \neq t}\sum_{j \neq t} \color{blue}{p_{i\vert j}} \cdot 2(\mathbf{y}_t - \mathbf{y}_i) \cdot q_{i\vert j} \\
=& 2\sum_j \color{blue}{p_{t\vert j}} \cdot (\mathbf{y}_t - \mathbf{y}_j) - 2\sum_j \color{blue}{p_{t\vert j}} \cdot (\mathbf{y}_t - \mathbf{y}_j)q_{t\vert j} -2\sum_{i \neq t}\sum_{j \neq t} \color{blue}{p_{i\vert j}} \cdot (\mathbf{y}_t - \mathbf{y}_i) \cdot q_{i\vert j} \\
=& 2\sum_j \color{blue}{p_{t\vert j}} \cdot (\mathbf{y}_t - \mathbf{y}_j) - 2\sum_i\sum_j \color{blue}{p_{t\vert j}} \cdot (\mathbf{y}_t - \mathbf{y}_j)q_{t\vert j}\\
=& 2\sum_j \color{blue}{p_{t\vert j}} \cdot (\mathbf{y}_t - \mathbf{y}_j) - 2\sum_j (\mathbf{y}_t - \mathbf{y}_j)q_{t\vert j} \\
=& 2\sum_j (\mathbf{y}_t - \mathbf{y}_j) \cdot (\color{blue}{p_{t\vert j}} - q_{t\vert j})
\end{aligned}\]
이렇게 나온 식에 두 번째 항을 미분하여 나온 식을 더하여 식을 정리해보겠습니다.
\[\begin{aligned}
&2\sum_j (\mathbf{y}_t - \mathbf{y}_j) \cdot (\color{blue}{p_{t\vert j}} - q_{t\vert j}) + 2\sum_j (\mathbf{y}_t-\mathbf{y}_j) \cdot (\color{blue}{p_{j\vert t}} - \color{red}{q_{j\vert t}}) \\
=& 2\sum_j (\mathbf{y}_t - \mathbf{y}_j) \cdot (\color{blue}{p_{t\vert j}} - q_{t\vert j} + \color{blue}{p_{j\vert t}} - \color{red}{q_{j\vert t}})
\end{aligned}\]
이렇게 구해진 최종 식이 $\partial C/\partial \mathbf{y}_t$ 가 됩니다. 이 식을 사용하여 경사 하강법을 적용하여 최솟값이 되는 지점을 추적해나가는 것이 SNE의 값이 되겠습니다.
Symmetric SNE
조건부 확률을 pairwise한 확률로 바꾸어주기 위해서 다음과 같은 역할을 진행합니다. pairwise 확률은 다음과 같이 변하게 됩니다.
\[p_{ij} = \frac{\exp(-\frac{\Vert\color{blue}{\mathbf{x}_i - \mathbf{x}_j}\Vert^2}{2\sigma^2_i})}{\sum_{k\neq l}\exp(-\frac{\Vert\color{blue}{\mathbf{x}_k - \mathbf{x}_l}\Vert^2}{2\sigma^2_i})} \Rightarrow p_{ij} = \frac{p_{j\vert i} + p_{i\vert j}}{2n} \quad \sum_j p_{ij} > \frac{1}{2n}\]
이 확률을 적용한 SNE를 Symmetric SNE라고 하며, 쿨백-라이블러 발산을 사용한 목적 함수와 그래디언트는 다음과 같이 변하게 됩니다.
\[C = \sum_i KL(\color{blue}{P_i}\Vert \color{red}{Q_i}) = \sum_i\sum_j \color{blue}{p_{ij}} \log \frac{\color{blue}{p_{ij}}}{\color{red}{q_{ij}}} \\
\because \frac{\partial C}{\partial y_i} = 4\sum_j (\mathbf{y}_t - \mathbf{y}_j) \cdot (\color{blue}{p_{ij}} - \color{red}{q_{ij}})\]
t-SNE
위에서 구한 SNE에서는 Crowding problem이라는 문제가 발생합니다. SNE에서는 가우시안 분포(Gaussian distribution, 정규 분포)를 적용하여 인스턴스의 확률을 배정합니다. 가우시안 분포의 그래프를 보겠습니다.
이미지 출처 : wiki.analytica.com
위 그래프에서 빨간색으로 색칠된 부분, 즉 중심에서 가까운 부분보다 파란색으로 색칠된 부분에서 급격히 경사가 감소하는 것을 볼 수 있습니다. 이를 보정하기 위해서 t-SNE에서는 꼬리가 더 두꺼운 스튜던트 t-분포(Student’s t-distribution)를 사용합니다. 이 때 t-분포의 자유도는 1로 정합니다. t-분포의 식을 수식으로 나타내면 아래와 같습니다.
\[f(t) = \frac{\Gamma(\frac{\nu+1}{2})}{\sqrt{\nu\pi}\Gamma(\frac{\nu}{2})}(1+\frac{t^2}{\nu})^{-\frac{\nu+1}{2}}\\
\Gamma(n) = (n-1)!\]
t-분포는 축소된 차원의 확률 분포인 $q$에만 적용되며 이때 $q$ 식은 아래와 같이 변하게 됩니다.
\[\color{red}{q_{i\vert j}} = \frac{(1+{\Vert\color{red}{\mathbf{y}_i - \mathbf{y}_j}\Vert^2})^{-1}}{\sum_{k\neq l}(1+{\Vert\color{red}{\mathbf{y}_k - \mathbf{y}_l}\Vert^2})^{-1}}\]
가우시안 분포에서 중심으로부터 떨어진 시점에서 감소. 그래서 t분포로 꼬리를 두껍게 해줌. 자유도 1인 t분포를 사용. p는 원래와 동일하게 가우시안을 쓰지만. q는 t분포를 사용한다.
해당 게시물은 고려대학교 강필성 교수님의 강의를 바탕으로 작성한 것입니다.
t-SNE
t-SNE(t-Stochastic Neighbor Embedding, t-확률적 이웃 임베딩)은 ISOMAP, 지역적 선형 임베딩(Locally Linear Embedding, LLE)과 더불어 많이 사용되는 비선형 구조 데이터를 차원 축소하는 알고리즘입니다.
Stochastic Neighbor Embedding
t-SNE의 핵심이 되는 SNE(Stochastic Neighbor Embedding)에 대해 알아보겠습니다. LLE(지역적 선형 임베딩)와 SNE 모두 이웃이 되는 인스턴스를 기준으로 Embedding한다는 공통점을 가지고 있습니다. 하지만 이웃을 선택하는 방법에서 차이점이 있습니다. LLE는 이산적인 접근법으로 이웃을 확정하지만 SNE는 확률적인 방법으로 이웃을 정하게 됩니다. 좀 더 자세히 설명하면 LLE는 가장 가까운 $k$개의 인스턴스(k-Nearest Neighborhood)를 이웃으로 확정한 뒤에는 다른 인스턴스를 고려하지 않습니다. 하지만 SNE는 일정 범위 내의 인스턴스를 모두 고려하되 거리에 따라 확률을 부여하여 고려하게 됩니다. 가까운 인스턴스의 확률은 높고, 멀리 있는 인스턴스의 확률 낮게 반영하는 식으로요. 다시 말해, 확률적으로 지역성을 결정하겠다고 말할 수 있겠습니다.
고차원에서 특정 인스턴스 쌍을 이웃으로 선택할 확률을 $p$로 나타내고, 차원 축소를 하여 저차원에서 특정 인스턴스 쌍을 이웃으로 선택할 확률을 $q$로 나타내면 아래와 같습니다.
\[\color{blue}{p_{i\vert j}} = \frac{\exp(-\frac{\Vert\color{blue}{\mathbf{x}_i - \mathbf{x}_j}\Vert^2}{2\sigma^2_i})}{\sum_{k\neq i}\exp(-\frac{\Vert\color{blue}{\mathbf{x}_i - \mathbf{x}_k}\Vert^2}{2\sigma^2_i})} \qquad \color{red}{q_{i\vert j}} = \frac{\exp(-{\Vert\color{red}{\mathbf{y}_i - \mathbf{y}_j}\Vert^2})}{\sum_{k\neq i}\exp({\Vert\color{red}{\mathbf{y}_i - \mathbf{y}_j}\Vert^2})}\]위 수식에서 $p$는 원 데이터의 차원에서 인스턴스 $i$가 인스턴스 $j$를 이웃으로 선택할 확률이며, $q$는 축소된 차원에서 인스턴스 $i$가 인스턴스 $j$를 이웃으로 선택할 확률입니다. $p,q$ 를 나타내는 수식은 비슷하게 생겼습니다. 우선 거리가 멀어질 수록 낮은 확률값을 할당하기 위해서 $y=e^{-x}$를 사용합니다. 이 함수에서는 $x$가 커질수록 함숫값이 작아지기 때문에 서로의 거리가 먼 인스턴스가 이웃으로 정해질 확률이 작아지게 됩니다. $y=e^{-x}$의 그래프는 아래와 같이 생겼습니다.
하지만 몇 가지 차이점도 가지고 있습니다. 먼저 $p$ 는 원래 인스턴스 좌표 $\mathbf{x}$ 에 대한 함수이며, $q$는 축소된 좌표계에서의 인스턴스의 좌표 $\mathbf{y}$에 대한 함수입니다. 그리고 $p$ 를 구하는 식에는 거리에 따른 확률값 차이를 얼마나 줄 것인지를 조정하는 $\sigma$ 가 있습니다. 이 값이 커지면 멀리 있는 인스턴스의 확률이 상대적으로 커지게 되고, 작게 하면 멀리 있는 인스턴스가 이웃으로 선택될 확률이 작아지게 됩니다. 실제로는 $\sigma$ 값이 $[5,50]$ 범위 중 어떤 값을 같더라도 t-SNE 자체가 실제로 강건(Robust)하게 작동하기 때문에 큰 고민없이 기본(Default)값으로 사용하는 것이 일반적입니다.
Cost function
우리의 목적은 두 확률 분포 $p,q$를 동일하게 만드는 것입니다. 따라서 이를 계산하기 위한 쿨백-라이블러 발산(Kullback-Leibler divergence, KLD)을 사용하여 두 값을 비교하게 됩니다. 쿨백-라이블러 발산은 비대칭(non-symmetric)이기 때문에 거리를 나타내는 수치는 아니지만 두 값의 엔트로피를 비교함으로써 목적함수로 사용됩니다. 수식으로 나타내면 아래와 같습니다.
\[C = \sum_i KL(\color{blue}{P_i}\Vert \color{red}{Q_i}) = \sum_i\sum_j \color{blue}{p_{i\vert j}} \log \frac{\color{blue}{p_{i\vert j}}}{\color{red}{q_{i\vert j}}}\]두 확률 분포가 완전히 동일할 때 목적 함수의 값은 0이 되며 확률 분포가 달라질수록 목적 함수의 값은 커지게 됩니다.
Gradient Descent
이제 목적 함수가 최소인 지점을 찾기 위해서 경사 하강법을 사용하겠습니다. $\mathbf{x}$값은 이미 정해져 있고, 우리가 필요한 것은 위 값을 최소로 만드는 $\mathbf{y}$입니다. 그렇기 때문에 $\mathbf{y}$로 편미분한 그래디언트를 구합니다. 수식으로 나타내면 아래와 같습니다.
\[\begin{aligned} C &= \sum_i\sum_j \color{blue}{p_{i\vert j}} \log \frac{\color{blue}{p_{i\vert j}}}{\color{red}{q_{i\vert j}}} \\ &= \sum_i\sum_j \color{blue}{p_{i\vert j}} \log \color{blue}{p_{i\vert j}} - \sum_i\sum_j \color{blue}{p_{i\vert j}} \log \color{red}{q_{i\vert j}} \\ C^\prime &= - \sum_i\sum_j \color{blue}{p_{i\vert j}} \log \color{red}{q_{i\vert j}} \\ &= -\sum_i \color{blue}{p_{t\vert i}} \log \color{red}{q_{t\vert i}} - \sum_j \color{blue}{p_{j\vert t}} \log \color{red}{q_{j\vert t}} - \sum_{i \neq t}\sum_{j \neq t} \color{blue}{p_{i\vert j}} \log \color{red}{q_{i\vert j}} \end{aligned} \\ \because \frac{\partial C}{\partial y_t} = \frac{\partial C^\prime}{\partial y_t}\]다음은 위 식의 각 항을 $\mathbf{y}$ 로 미분한 식을 구할 차례입니다. 식을 구하기 과정을 좀 더 간단하게 하기 위하여 계산 과정에서 나올 항을 다음과 같이 치환하도록 하겠습니다.
\[d_{ti} = \exp(-\Vert \color{red}{\mathbf{y}_t - \mathbf{y}_i}\Vert^2) = d_{it}\]이를 활용하면 몇 가지 항을 아래와 같이 나타낼 수 있습니다.
\[\frac{\partial d_{it}}{\partial \mathbf{y}_t} = d^\prime_{ti} = -2(\Vert\mathbf{y}_t-\mathbf{y}_i\Vert) \exp(\Vert\mathbf{y}_t-\mathbf{y}_i\Vert^2) = -2(\mathbf{y}_t-\mathbf{y}_i)d_{ti}\\ q_{t\vert i} = \frac{\exp(\Vert\mathbf{y}_i-\mathbf{y}_t\Vert^2)}{\sum_{k \neq i} \exp(\Vert\mathbf{y}_i-\mathbf{y}_k\Vert^2)} = \frac{d_{it}}{\sum_{k \neq i}d_{ik}}\\ q_{j\vert t} = \frac{\exp(\Vert\mathbf{y}_t-\mathbf{y}_j\Vert^2)}{\sum_{k \neq t} \exp(\Vert\mathbf{y}_t-\mathbf{y}_k\Vert^2)} = \frac{d_{tj}}{\sum_{k \neq i}d_{tk}}\\ q_{i\vert j} = \frac{\exp(\Vert\mathbf{y}_j-\mathbf{y}_i\Vert^2)}{\sum_{k \neq i} \exp(\Vert\mathbf{y}_j-\mathbf{y}_k\Vert^2)} = \frac{d_{ji}}{\sum_{k \neq j}d_{jk}}\]이제 이를 사용하여 본격적으로 각 항을 미분한 식을 구해보겠습니다. 첫 번째 항을 미분한 값은 아래와 같이 구해집니다.
\[\begin{aligned} \frac{\partial}{\partial \mathbf{y}_t}\bigg(-\sum_i \color{blue}{p_{t\vert i}} \log \color{red}{q_{t\vert i}}\bigg) &= -\sum_i \color{blue}{p_{t\vert i}}\cdot \frac{1}{\color{red}{q_{t\vert i}}}\cdot \frac{\partial \color{red}{q_{t\vert i}}}{\partial y_t} \\ &= -\sum_i \color{blue}{p_{t\vert i}}\cdot \frac{1}{\color{red}{q_{t\vert i}}}\cdot \frac{d^\prime_{it}(\sum_{k \neq i}d_{ik}) - d_{it}d^\prime_{it}}{(\sum_{k \neq i}d_{ik})^2} \\ &= -\sum_i \color{blue}{p_{t\vert i}}\cdot \frac{1}{\color{red}{q_{t\vert i}}}\cdot \frac{-2(\mathbf{y}_t-\mathbf{y}_i)d_{ti}(\sum_{k \neq i}d_{ik}) +2(\mathbf{y}_t-\mathbf{y}_i)d_{ti}^2}{(\sum_{k \neq i}d_{ik})^2}\\ &= -\sum_i \color{blue}{p_{t\vert i}}\cdot \frac{1}{\color{red}{q_{t\vert i}}}\cdot \bigg(-2(\mathbf{y}_t - \mathbf{y}_i) \cdot q_{t\vert i} + 2(\mathbf{y}_t - \mathbf{y}_i) \cdot q_{t\vert i}^2\bigg)\\ &= \sum_i \color{blue}{p_{t\vert i}} \cdot 2(\mathbf{y}_t - \mathbf{y}_i)(1 - q_{t\vert i}) \end{aligned}\]두 번째 항을 미분한 값은 다음의 과정을 거쳐 구할 수 있습니다.
\[\begin{aligned} \frac{\partial}{\partial \mathbf{y}_t}\bigg(-\sum_j \color{blue}{p_{j\vert t}} \log \color{red}{q_{j\vert t}}\bigg) &= -\sum_j \color{blue}{p_{j\vert t}}\cdot \frac{1}{\color{red}{q_{j\vert t}}}\cdot \frac{\partial \color{red}{q_{j\vert t}}}{\partial y_t} \\ &= -\sum_j \color{blue}{p_{j\vert t}}\cdot \frac{1}{\color{red}{q_{j\vert t}}}\cdot \frac{d^\prime_{tj}(\sum_{k \neq t}d_{tk}) - d_{tj}(\sum_{k \neq t}d^\prime_{tk})}{(\sum_{k \neq t}d_{tk})^2} \\ &= -\sum_j \color{blue}{p_{j\vert t}}\cdot \frac{1}{\color{red}{q_{j\vert t}}}\cdot \frac{-2(\mathbf{y}_t-\mathbf{y}_j)d_{tj}(\sum_{k \neq t}d_{tk}) - d_{tj}(\sum_{k \neq t}d^\prime_{tk})}{(\sum_{k \neq t}d_{tk})^2}\\ &= 2\sum_j \color{blue}{p_{j\vert t}} \cdot(\mathbf{y}_t-\mathbf{y}_j) + \sum_j \color{blue}{p_{j\vert t}} \cdot \frac{\sum_{k \neq t}d^\prime_{tk}}{\sum_{k \neq t}d_{tk}} \\ &= 2\sum_j \color{blue}{p_{j\vert t}} \cdot(\mathbf{y}_t-\mathbf{y}_j) + \sum_j \frac{d^\prime_{tj}}{\sum_{k \neq t}d_{tk}} \\ &= 2\sum_j \color{blue}{p_{j\vert t}} \cdot(\mathbf{y}_t-\mathbf{y}_j) -2 \sum_j (\mathbf{y}_t-\mathbf{y}_j) \cdot \frac{d_{tj}}{\sum_{k \neq t}d_{tk}}\\ &= 2\sum_j \color{blue}{p_{j\vert t}} \cdot(\mathbf{y}_t-\mathbf{y}_j) -2 \sum_j (\mathbf{y}_t-\mathbf{y}_j) \cdot \color{red}{q_{j\vert t}} \\ &= 2\sum_j (\mathbf{y}_t-\mathbf{y}_j) \cdot (\color{blue}{p_{j\vert t}} - \color{red}{q_{j\vert t}}) \end{aligned}\]마지막으로 세 번째 항을 미분한 값을 구해보겠습니다.
\[\begin{aligned} \frac{\partial}{\partial \mathbf{y}_t}\bigg(-\sum_{i \neq t}\sum_{j \neq t} \color{blue}{p_{i\vert j}} \log \color{red}{q_{o\vert j}}\bigg) &= -\sum_{i \neq t}\sum_{j \neq t} \color{blue}{p_{i\vert j}}\cdot \frac{1}{\color{red}{q_{i\vert j}}}\cdot \frac{\partial \color{red}{q_{i\vert j}}}{\partial y_t} \\ &= -\sum_{i \neq t}\sum_{j \neq t} \color{blue}{p_{i\vert j}}\cdot \frac{1}{\color{red}{q_{i\vert j}}}\cdot \frac{d^\prime_{ji}(\sum_{k \neq j}d_{jk}) - d_{ji}d^\prime_{jt}}{(\sum_{k \neq j}d_{ji})^2} \\ &= -\sum_{i \neq t}\sum_{j \neq t} \color{blue}{p_{i\vert j}}\cdot \frac{1}{\color{red}{q_{i\vert j}}}\cdot \frac{2(\mathbf{y}_t-\mathbf{y}_i)d_{ji}d_{jt}}{(\sum_{k \neq j}d_{jk})^2}\\ &= -\sum_{i \neq t}\sum_{j \neq t} \color{blue}{p_{i\vert j}}\cdot \frac{1}{\color{red}{q_{i\vert j}}}\cdot 2(\mathbf{y}_t - \mathbf{y}_i) \cdot q_{i\vert j}\cdot q_{t\vert j}\\ &= -\sum_{i \neq t}\sum_{j \neq t} \color{blue}{p_{i\vert j}} \cdot 2(\mathbf{y}_t - \mathbf{y}_i) \cdot q_{i\vert j} \end{aligned}\]첫 번째 항을 미분하여 나온 식과 세 번째 항을 미분하여 나온 식을 더한 후에 정리해보겠습니다.
\[\begin{aligned} &\sum_i \color{blue}{p_{t\vert i}} \cdot 2(\mathbf{y}_t - \mathbf{y}_i)(1 - q_{t\vert i}) -\sum_{i \neq t}\sum_{j \neq t} \color{blue}{p_{i\vert j}} \cdot 2(\mathbf{y}_t - \mathbf{y}_i) \cdot q_{i\vert j} \\ =&\sum_j \color{blue}{p_{t\vert j}} \cdot 2(\mathbf{y}_t - \mathbf{y}_j)(1 - q_{t\vert j}) -\sum_{i \neq t}\sum_{j \neq t} \color{blue}{p_{i\vert j}} \cdot 2(\mathbf{y}_t - \mathbf{y}_i) \cdot q_{i\vert j} \\ =& 2\sum_j \color{blue}{p_{t\vert j}} \cdot (\mathbf{y}_t - \mathbf{y}_j) - 2\sum_j \color{blue}{p_{t\vert j}} \cdot (\mathbf{y}_t - \mathbf{y}_j)q_{t\vert j} -2\sum_{i \neq t}\sum_{j \neq t} \color{blue}{p_{i\vert j}} \cdot (\mathbf{y}_t - \mathbf{y}_i) \cdot q_{i\vert j} \\ =& 2\sum_j \color{blue}{p_{t\vert j}} \cdot (\mathbf{y}_t - \mathbf{y}_j) - 2\sum_i\sum_j \color{blue}{p_{t\vert j}} \cdot (\mathbf{y}_t - \mathbf{y}_j)q_{t\vert j}\\ =& 2\sum_j \color{blue}{p_{t\vert j}} \cdot (\mathbf{y}_t - \mathbf{y}_j) - 2\sum_j (\mathbf{y}_t - \mathbf{y}_j)q_{t\vert j} \\ =& 2\sum_j (\mathbf{y}_t - \mathbf{y}_j) \cdot (\color{blue}{p_{t\vert j}} - q_{t\vert j}) \end{aligned}\]이렇게 나온 식에 두 번째 항을 미분하여 나온 식을 더하여 식을 정리해보겠습니다.
\[\begin{aligned} &2\sum_j (\mathbf{y}_t - \mathbf{y}_j) \cdot (\color{blue}{p_{t\vert j}} - q_{t\vert j}) + 2\sum_j (\mathbf{y}_t-\mathbf{y}_j) \cdot (\color{blue}{p_{j\vert t}} - \color{red}{q_{j\vert t}}) \\ =& 2\sum_j (\mathbf{y}_t - \mathbf{y}_j) \cdot (\color{blue}{p_{t\vert j}} - q_{t\vert j} + \color{blue}{p_{j\vert t}} - \color{red}{q_{j\vert t}}) \end{aligned}\]이렇게 구해진 최종 식이 $\partial C/\partial \mathbf{y}_t$ 가 됩니다. 이 식을 사용하여 경사 하강법을 적용하여 최솟값이 되는 지점을 추적해나가는 것이 SNE의 값이 되겠습니다.
Symmetric SNE
조건부 확률을 pairwise한 확률로 바꾸어주기 위해서 다음과 같은 역할을 진행합니다. pairwise 확률은 다음과 같이 변하게 됩니다.
\[p_{ij} = \frac{\exp(-\frac{\Vert\color{blue}{\mathbf{x}_i - \mathbf{x}_j}\Vert^2}{2\sigma^2_i})}{\sum_{k\neq l}\exp(-\frac{\Vert\color{blue}{\mathbf{x}_k - \mathbf{x}_l}\Vert^2}{2\sigma^2_i})} \Rightarrow p_{ij} = \frac{p_{j\vert i} + p_{i\vert j}}{2n} \quad \sum_j p_{ij} > \frac{1}{2n}\]이 확률을 적용한 SNE를 Symmetric SNE라고 하며, 쿨백-라이블러 발산을 사용한 목적 함수와 그래디언트는 다음과 같이 변하게 됩니다.
\[C = \sum_i KL(\color{blue}{P_i}\Vert \color{red}{Q_i}) = \sum_i\sum_j \color{blue}{p_{ij}} \log \frac{\color{blue}{p_{ij}}}{\color{red}{q_{ij}}} \\ \because \frac{\partial C}{\partial y_i} = 4\sum_j (\mathbf{y}_t - \mathbf{y}_j) \cdot (\color{blue}{p_{ij}} - \color{red}{q_{ij}})\]t-SNE
위에서 구한 SNE에서는 Crowding problem이라는 문제가 발생합니다. SNE에서는 가우시안 분포(Gaussian distribution, 정규 분포)를 적용하여 인스턴스의 확률을 배정합니다. 가우시안 분포의 그래프를 보겠습니다.
이미지 출처 : wiki.analytica.com
위 그래프에서 빨간색으로 색칠된 부분, 즉 중심에서 가까운 부분보다 파란색으로 색칠된 부분에서 급격히 경사가 감소하는 것을 볼 수 있습니다. 이를 보정하기 위해서 t-SNE에서는 꼬리가 더 두꺼운 스튜던트 t-분포(Student’s t-distribution)를 사용합니다. 이 때 t-분포의 자유도는 1로 정합니다. t-분포의 식을 수식으로 나타내면 아래와 같습니다.
\[f(t) = \frac{\Gamma(\frac{\nu+1}{2})}{\sqrt{\nu\pi}\Gamma(\frac{\nu}{2})}(1+\frac{t^2}{\nu})^{-\frac{\nu+1}{2}}\\ \Gamma(n) = (n-1)!\]t-분포는 축소된 차원의 확률 분포인 $q$에만 적용되며 이때 $q$ 식은 아래와 같이 변하게 됩니다.
\[\color{red}{q_{i\vert j}} = \frac{(1+{\Vert\color{red}{\mathbf{y}_i - \mathbf{y}_j}\Vert^2})^{-1}}{\sum_{k\neq l}(1+{\Vert\color{red}{\mathbf{y}_k - \mathbf{y}_l}\Vert^2})^{-1}}\]가우시안 분포에서 중심으로부터 떨어진 시점에서 감소. 그래서 t분포로 꼬리를 두껍게 해줌. 자유도 1인 t분포를 사용. p는 원래와 동일하게 가우시안을 쓰지만. q는 t분포를 사용한다.
Comments