[Dimensionality Reduction] Unsupervised Method (Nonlinear embedding) 2: t-SNE

본 포스트는 고려대학교 산업경영공학부 강필성 교수님의 Business Analytics 강의를 정리한 내용입니다.

 

SNE (Stochastic Neighbor Embedding)

SNE에서는 local distance를 보존하는 것이 local이 아닌 객체에 대한 distance보다 중요하는 것이 핵심이다.

LLE에서는 정해진 개수의 이웃들 간의 weight를 찾고, 이를 저 차원으로 축소하였다. LLE에서는 이웃의 변화가 없었다. SNE에서는 객체 두 쌍의 거리가 local인 것을 확률적으로 결정한다. 이 말은 가깝게 있는 객체뿐만이 아니라, 조금 더 멀리 있는 객체들도 확률적으로는 낮을 뿐이지 뽑힐 수도 있다는 것이다.

1개의 data point가 다른 data point를 이웃으로 뽑는 것을 확률로 표현할 수 있다. $i$를 기준으로 해서 $j$번째 이웃을 뽑을 확률을 표현할 수 있고, 이를 고차원에서 저차원의 $j$를 뽑는 확률, 저차원에서 고차원의 $j$를 뽑는 확률로 표현할 수 있다.

$$ p_{j \mid i}=\frac{e^{-\frac{\parallel \mathbf{x}{i}-\mathbf{x}{j} \parallel^{2}}{2 \sigma^{2}{i}}}}{\sum{k\neq i}e^{-\frac{\parallel \mathbf{x}{i}-\mathbf{x}{k} \parallel^{2}}{2 \sigma^{2}_{i}}}} $$

$$ q_{j \mid i}=\frac{e^{-\parallel \mathbf{y}{i}-\mathbf{y}{j} \parallel^{2}}}{\sum_{k\neq i}e^{-\parallel \mathbf{y}{i}-\mathbf{y}{k} \parallel^{2}} } $$

$p_{j \mid i}$는 원래 차원에서 객체 $i$가 다른 객체 $j$를 이웃으로 선택할 확률이고, $q_{j\mid i}$는 축소된 차원에서 객체 $i$가 원래 차원 $j$를 이웃으로 선택할 확률이다.

이 2가지 확률에 대해서 정의하였는데, 식을 살펴보면 분포는 nomalization을 진행한다. 핵심은 분자에 있는데, 이는 서로 가까울 수록 확률 값이 커지고, 멀어질수록 확률은 낮아진다.

기존 LLE에서는 구체적인 개수 안에 들어오는 이웃에 대해서는 1, 아닌 객체들에 대해서는 0을 사용했다.

모든 데이터는 같은 공간에 있지 않기 때문에 우리는 서로 다른 공간에 대해서 다른 radii를 사용해야 한다. radii를 통해 충분히 많은 이웃이 반경에 들어가야 되기 때문이다. radii가 크면 이웃의 distribution entropy는 커질 것이고, 반대로 작으면 낮아질 것이다.

따라서 우리가 적절한 entropy를 사용하기 위해 radii를 잘 조절해야 한다.

어떠한 문제를 해결하기 위해서는 우리에게 주어진 것이 무엇이고, 찾아야 하는 미지수를 명확하게 정해야 한다.

우리는 현재 $p_{j \mid i}=f(x), \ q_{j \mid i}=q(y)$라는 식을 정의하였고, 현재는 $x$를 알고 있다.

수식을 통해 $p_{j \mid i}$는 계산이 가능하다. 하지만 우리가 실절적으로 알아야 하는 것은 $u$이고, 이는 저차원 coordinate system이다.

우리의 목표는 $p_{j \mid i}$와 $q_{j \mid i}$를 최대한 동일하게 만들고 싶은 것이 목적이다. 이를 위해 2개의 분포를 비교하는 데 있어 KL divergence를 사용할 수 있다. 이는 두 분포의 유사성을 파악할 수 있지만 distance matrix는 아니다. 이를 아래 수식과 같이 표현할 수 있다.

$$ cost = \sum_{i}KL(P_{i}||Q_{i})=\sum_{i}\sum_{j}p_{j\mid i}\log\frac{p_{j \mid i}}{q_{j \mid i}} $$

KL divergence를 통해 나온 summation이 cost function이 된다.

우리는 cost function을 $y$에 대해 편미분을 진행함으로써 우리가 구해야 하는 최종적인 수식을 정의할 수 있다. 결과는 다음과 같다.

$$ \frac{\partial C}{\partial y_{i}}=2\sum_{j}(y_{j}-y_{i})(p_{j\mid i}-q_{j \mid i}+p_{i\mid j}-q_{i \mid j}) $$

위 수식이 어떻게 나오는지 계산을 통해 살펴보자.

$$ C = \sum_{i}KL(P_{i}||Q_{i})=\sum_{i}\sum_{j}p_{j\mid i}\log\frac{p_{j \mid i}}{q_{j \mid i}} $$

cost function의 log를 분해하면 다음과 같게 된다.

$$ C = \sum_{i}\sum_{j}p_{j\mid i}\log p_{j \mid i} - \sum_{i}\sum_{j} p_{j \mid i} \log q_{j\mid i} $$

여기서 첫번째 term은 고차원에 대한 수식이기 때문에 상수로 취급한다. ($y$이랑 연관이 없다.)

상수를 없앤 식을 $C'$라고 하자.

$$ C' = -\sum_{i}\sum_{j}p_{j \mid i}\log q_{j \mid i} \ \ (\frac{\partial C}{\partial y_{t}} =\frac{\partial C'}{\partial y_{t}}) $$

이 식을 $t$가 앞쪽에 있는지, 뒤에 있는지, 아예 없는 case에 따라 값이 달라진다. 이러한 이유로 위 식을 3개의 term으로 나눈다.

$$ C'=-\sum_{i}p_{t\mid i}\log q_{t\mid i}-\sum_{j}p_{j \mid t} \log q_{j\mid t} - \sum_{i \neq t}\sum_{j \neq t}p_{i \mid j}\log q_{i \mid j} $$

위 식을 통해 cost function의 gradient를 구한다.

계산의 편의를 위해 $d_{ti}$를 다음과 같이 정의한다.

$$ d_{ti}=exp(-\parallel y_{t}-y_{i}\parallel^{2})= d_{it} $$

$d_{ti}$는 $d_{it}$와 같고, 위 식을 $y_{t}$에 대해 편미분을 진행한다.

$$ \frac{\partial d_{ti}}{\partial y_{t}}=d'{ti} = -2(y{t}-y_{i})exp(-\parallel y_{t}-y_{i} \parallel^{2})=-2(y_{t}-y_{i})d_{ti} $$

또한 $d_{ti}$를 사용하여 3가지 case에 대한 $q$를 표현할 수 있다.

$$ \begin{align} q_{t\mid i} &=\frac{exp(-\parallel y_{i}-y_{t} \parallel^{2})}{\sum_{k \neq i} exp(-\parallel y_{i}-y_{k} \parallel^{2})} = \frac{d_{it}}{\sum_{k \neq i}d_{ik}} \\ q_{j\mid t}&=\frac{exp(-\parallel y_{t}-y_{j} \parallel^{2})}{\sum_{k \neq t} exp(-\parallel y_{t}-y_{k} \parallel^{2})} = \frac{d_{tj}}{\sum_{k \neq t}d_{tk}} \\ q_{i\mid j}&=\frac{exp(-\parallel y_{j}-y_{i} \parallel^{2})}{\sum_{k \neq j} exp(-\parallel y_{j}-y_{k} \parallel^{2})} = \frac{d_{ji}}{\sum_{k \neq j}d_{jk}} \end{align} $$

위 수식들을 이용하여 $C'$에 대한 편미분을 진행하자.

 

Term 1

$$ \frac{\partial}{\partial y_{t}}(-\sum_{i}p_{t\mid i}\log q_{t\mid i})= -\sum_{i}p_{t \mid i}\cdot \frac{1}{q_{t\mid i}} \cdot \frac{\partial q_{t \mid i}}{ \partial y_{t}} $$

로그를 미분하면 위 수식과 같이 전개된다.

$$ = -\sum_{i}p_{t \mid i} \cdot \frac{1}{q_{t\mid i}}\cdot \frac{d_{it}' \cdot (\sum_{k \neq i}d_{ik})-d_{it} \cdot d_{it}'}{(\sum_{k \neq i}d_{ik})^{2}} $$

$d$에 대한 summation에서 $t$가 존재하기 때문에 위와 같이 식이 전개된다.

$$ = -\sum_{i}p_{t \mid i} \cdot \frac{1}{q_{t\mid i}} \cdot \frac{-2(y_{t} - y_{i}) \cdot d_{it} \cdot (\sum_{k \neq i} d_{ik})+2(y_{t} -y_{i}) \cdot d_{it}^{2}}{(\sum_{k \neq i}d_{ik})^{2}} $$

위에서 정의한 $d_{ti}' = -2(y_{t}-y_{i})d_{ti}$를 대입한 결과이다.

$$ = -\sum_{i}p_{t \mid i} \cdot \frac{1}{q_{t\mid i}} \cdot (-2(y_{t}-y_{i})\cdot q_{t \mid i}+ 2(y_{t}-y_{i})\cdot q_{t \mid i}^{2}) $$

$d_{it} = q_{t \mid i} \cdot \sum_{k \neq i}d_{ik}$를 사용하여 약분한 결과이다.

$$ = \sum_{i}p_{t \mid i} \cdot 2(y_{t}-y_{i})(1-q_{t \mid i}) $$

$q_{t \mid i}$를 약분해주면 최종적인 식을 얻을 수 있다.

Term 2

$$ \frac{\partial}{\partial y_{t}}(-\sum_{j}p_{j\mid t}\log q_{j\mid t}) = -\sum_{j}p_{j \mid t}\cdot \frac{1}{q_{j\mid t}} \cdot \frac{\partial q_{j \mid t}}{ \partial y_{t}} $$

Term 1과 동일하게 $log$를 분리한다.

$$ = -\sum_{j}p_{j \mid t}\cdot \frac{1}{q_{j\mid t}}\cdot \frac{d_{tj}'\cdot (\sum_{k \neq t}d_{tk}) - d_{tj} \cdot (\sum_{k \neq t} d'{tk})}{(\sum{k \neq t}d_{tk})^{2}} $$

분모 미분과 속 미분을 하면 다음과 같이 된다.

$$ = -\sum_{j}p_{j \mid t}\cdot \frac{1}{q_{j\mid t}}\cdot \frac{-2(y_{t}-y_{j})\cdot d_{tj}\cdot (\sum_{k \neq t}d_{tk})-d_{tj}\cdot (\sum_{k \neq t}d_{tk}')}{(\sum_{k \neq t}d_{tk})^{2}} $$

$d_{tj}'$를 대입한 결과이다.

$$ = 2 \sum_{j}p_{j \mid t} \cdot (y_{t} - y_{j})+\sum_{j} p_{j \mid t}\cdot \frac{\sum_{k \neq t}d_{tk}'}{\sum_{k \neq t}d_{tk}} $$

앞 단과 뒷 단 둘 다 $\sum_{k \neq t}d_{tk}$에 대해 약분하면 나오는 결과이다.

$$ = 2\sum_{j}p_{j \mid t} \cdot (y_{t} - y_{j}) + \sum_{j}\cdot \frac{d'{tj}}{\sum{k \neq t}d_{tk}} $$

앞 단은 그대로 내려오고, 뒷 단의 $\sum_{j}p_{j \mid t} =1$을 만족하기 때문에 없어진다. 분자는 $\sum_{k\neq t}d'{tk}= \sum{k}d_{tk}'$가 성립되고 이로 인해 $d'_{tt} =0$이 되기 때문이다. summation을 $j$로 바꾼 것은 계산의 편의상 변경한 것이다.

$$ = 2\sum_{j}p_{j \mid t} \cdot (y_{t} - y_{j}) -2\sum_{j}(y_{t}-y_{j})\cdot \frac{d_{tj}}{\sum_{k \neq t}d_{tk}} $$

$d_{tj}' = -2(y_{t}-y_{j})d_{tj}$를 대입한 결과이다.

$$ = 2\sum_{j}p_{j \mid t} \cdot (y_{t} - y_{j}) -2\sum_{j}(y_{t}-y_{j})\cdot q_{j \mid t} $$

$q_{j\mid t} =\frac{d_{tj}}{\sum_{k \neq t}d_{tk}}$를 대입한다.

$$ =2\sum_{j}(y_{t} -y_{j})(p_{j \mid t}- q_{j \mid t}) $$

식을 묶어 최종적인 term 2에 대한 수식을 정리하였다.

 

Term 3

$$ \frac{\partial}{\partial y_{t}}(- \sum_{i \neq t}\sum_{j \neq t}p_{i \mid j}\log q_{i \mid j})= -\sum_{i \neq t}\sum_{j \neq t}p_{i\mid j}\cdot \frac{1}{q_{i \mid j}}\cdot \frac{\partial q_{i \mid j}}{\partial y_{t}} $$

동일하게 $log$를 풀어 준다.

$$ = -\sum_{i \neq t}\sum_{j \neq t} p_{i \mid j}\cdot \frac{1}{q_{i \mid j}}\cdot \frac{d'{ji} \cdot \sum{k \neq j}d_{jk} - d_{ji} \cdot d_{jt}'}{(\sum_{k \neq j}d_{jk})^{2}} $$

동일하게 미분을 진행한다.

$$ = -\sum_{i \neq t}\sum_{j \neq t} p_{i \mid j}\cdot \frac{1}{q_{i \mid j}}\cdot \frac{2(y_{t}-y_{t} \cdot d_{ji}\cdot d_{jt})}{(\sum_{k \neq j}d_{jk})^{2}} $$

$d_{ji}'$는 $t$와 상관없는 변수이기 때문에 0이 되고, $d_{jt}'$를 풀어준 결과가 다음과 같다.

$$ = -\sum_{i \neq t}\sum_{j \neq t} p_{i \mid j}\cdot \frac{1}{q_{i \mid j}}\cdot 2(y_{t}-y_{j})\cdot q_{i \mid j}\cdot q_{t \mid j} $$

$q_{j\mid t}=\frac{exp(-\parallel y_{t}-y_{j} \parallel^{2})}{\sum_{k \neq t} exp(-\parallel y_{t}-y_{k} \parallel^{2})} = \frac{d_{tj}}{\sum_{k \neq t}d_{tk}}$, $q_{i\mid j}=\frac{exp(-\parallel y_{j}-y_{i} \parallel^{2})}{\sum_{k \neq j} exp(-\parallel y_{j}-y_{k} \parallel^{2})} = \frac{d_{ji}}{\sum_{k \neq j}d_{jk}}$를 대입한 결과이다.

$$ = -\sum_{i \neq t}\sum_{j \neq t} 2(y_{t}-y_{j})\cdot p_{i \mid j}\cdot q_{t \mid j} $$

$q_{i \mid j}$를 약분하면 최종적인 term 3에 대한 식을 구할 수 있다.

Tern 1 + Term 3

$$ \sum_{i}p_{t \mid i} \cdot 2(y_{t}-y_{i})(1 - q_{t \mid i }) - \sum_{i \neq t}\sum_{j \neq t} 2(y_{t}-y_{j})\cdot p_{i \mid j} \cdot q_{t\mid j} $$

이제 순차적으로 모든 term에 대해 더해주자.

$$ = 2\sum_{j}(y_{t}-y_{j}) \cdot p_{t \mid i} - 2 \sum_{j}(y_{t}-y_{j})\cdot p_{t \mid j} \cdot q_{t\mid j}- 2\sum_{i \neq t}\sum_{j \neq t} (y_{t}-y_{j})\cdot p_{i \mid j} \cdot q_{t\mid j} $$

Term 1에 있는 summation에 대해 $i$를 $j$로 변경해준다. 어차피 문자만 달라지는 거라 상관이 없다. 그러고 나서 term 1 summation에 있는 식들을 전개하면 위와 같은 결과가 나온다.

$$ =2\sum_{j}(y_{t}-y_{j})\cdot p_{t \mid j}-2\sum_{i}\sum_{j}(y_{t}-y_{j})\cdot p_{i\mid j}\cdot q_{t \mid j} $$

그러고 나서 term 3의 summation을 보면 $j \neq t$라는 조건이 있지만, $y_{t}-y_{t}=0$이기 때문에 $j$로 바꿔 쓸 수 있다.

또한 $i \neq t$라는 조건은 2번째 식에 존재하는 $p_{t\mid j}$은 모든 $j$에 대한 summation이고, term 3에 있는 $p_{i\mid j}$는 $i$가 $t$가 아닐 때만 성립하기 때문에, 둘이 합쳐서 위 식과 같이 표현할 수 있다. 따라서 2번째 식을 $j$에서 $i$로 치환하여 다음과 같은 결과가 나온 것이다.

$$ =2\sum_{j}(y_{t}-y_{j})\cdot p_{t \mid j}-2\sum_{j}\sum_{i}p_{i \mid j}\cdot (y_{t}-y_{j})\cdot q_{t\mid j} $$

식을 계산하기 쉽게 순서를 바꿔준다.

$$ =2\sum_{j}(y_{t}-y_{j})\cdot p_{t \mid j}-2\sum_{j}(y_{t}-y_{j})\cdot q_{t\mid j} $$

$\sum_{i}p_{i \mid j}=1$이기 때문에 $i$에 대한 summation을 제거할 수 있다.

$$ =2\sum_{j}(y_{t}-y_{j})( p_{t \mid j}-q_{t\mid j}) $$

식을 정리하면 다음과 같은 결과를 얻을 수 있다.

 

Tern 1 + Term 2 + Term 3

$$ 2\sum_{j}(y_{t}-y_{j})( p_{t \mid j}-q_{t\mid j}) + 2\sum_{j}(y_{t}-y_{j})(p_{t \mid j}-q_{t \mid j}) $$

위에서 구한 식에서 term 2 식을 더해준다.

$$ 2\sum_{j}(y_{t}-y_{j})(p_{t\mid j}-q_{t\mid j}+p_{j \mid t}-q_{j\mid t}) $$

정리를 해줌으로써 cost function에 대한 gradient를 간단한 수식으로 정리할 수 있다.

위 식을 가지고 gradient descent와 같은 gradient update 함수에 넣어 cost를 최소화할 수 있다.

 

Symmetric SNE

지금까지는 SNE의 cost function에 대한 도함수를 계산했다. 기존까지 SNE는 $p_{i \mid j}$와 $p_{j \mid i}$는 다르게 계산을 하였다.

Symmetric SNE는 $p_{i \mid j}$를 $2n$으로 나눔으로써 이를 통합한다.

수식으로 표현하면 다음과 같다.

$$ p_{ij}=\frac{e^{-\frac{\parallel \mathbf{x}{i} -\mathbf{x}{j} \parallel^{2}}{2 \sigma^{2}{i}}}}{\sum{k \neq l}e^{-\frac{\parallel \mathbf{x}{k}-\mathbf{x}{l}\parallel^{2}}{2\sigma^{2}_{i}}}} $$

이는 기존 $p_{ij}$에 대한 확률식이다. 이를 아래 수식과 같이 변형하여 통합한다.

$$ p_{ij}=\frac{p_{j\mid i}+p_{i\mid j}}{2n}, \ \ \sum_{j}p_{ij}>\frac{1}{2n} $$

$2n$으로 나눔으로써 $p_{ij}$를 위와 같이 정의한다.

위 정의를 통해 cost function을 구하면 다음과 같다.

$$ cost = \sum_{i}KL(P_{i}||Q_{i})=\sum_{i}\sum_{j}p_{j\mid i}\log\frac{p_{j \mid i}}{q_{j \mid i}} $$

$$ \frac{\partial C}{\partial y_{i}}=4\sum_{j}(y_{j}-y_{i})(p_{ij}-q_{ij}) $$

Symmetric SNE를 적용하면 위와 같은 plot의 결과가 나온다. 이는 비교적 각 객체의 distance를 잘 보존한 것 같지만, crowding problem이 존재한다. 이는 객체가 멀어질 때 가까이 있는 객체들은 완만하게 감소하는데, 일정 이상 멀어지면 감소하는 폭이 커지는 것을 의미한다.

이는 가우시안 분포를 기준으로 객체를 고려하였기 때문에 생기는 문제이다.

T-SNE

Symmetric SNE의 crowding problem을 해결하기 위해 T-SNE라는 개념이 나왔다.

이는 기존 가우시안 분포를 사용하여 이웃 객체를 선택한 것을 T 분포로 대체하여 먼 객체에 대해 더욱 굳건해진다.

T-SNE의 $p_{ij}$는 기존과 같이 가우시안을 사용하지만, 저 차원에서 원래의 차원에서 뽑는 $q_{ji}$에 대해서는 T 분포를 사용한다. 수식의 정의는 다음과 같다.

$$ q_{ji}=\frac{(1+\parallel y_{i}-y_{j} \parallel^{2})^{-1}}{\sum_{k\neq l}(1+\parallel y_{k}-y_{l} \parallel^{2})^{-1}} $$

위 식들을 통해 cost function의 gradient 수식은 다음과 같이 정의된다.

$$ \frac{\partial C}{\partial y_{i}}=4\sum_{j}(y_{j}-y_{i})(p_{ij}-q_{ij})(1+\parallel y_{i}-y_{j} \parallel^{2})^{-1} $$

t-SNE과 MDS를 비교하면 전자에서는 전체 이웃에 대한 확률을 가지고 이웃을 선택하기 때문에 비슷한 객체들끼리 몰려있는 모습을 볼 수 있다. MDS는 전체 객체의 대한 분산을 보존하려는 경향이 있어 다음과 같은 모습을 보인다.