SNE (Stochastic Neighbor Embedding)

우리 인간은 3차원까지 밖에 보고 느낄 수 없기 때문에, 고차원의 데이터를 차원축소(Dimension Reduction)하여 저차원(1~3)으로 나타내는 것이 중요하다.

현실 세계에서 고차원의 데이터가 많이 있나라고 반문하는 사람이 있을 것이다. 예를 들어 보면, 어떤 것을 생산하는 설비에서 센싱되는 데이터와 생산품의 품질 등을 분석할 때, 특정 시점의 센싱 값(M개)과 품질 지수(N개)를 하나로 묶으면 그 데이터는 M+N 차원이다.

또 여러장의 이미지(그림)를 분석하는 경우를 생각해 보면, 각 그림은 해상도만큼의 차원을 갖은 데이터이다. 흑백 20x30 사이즈의 그림은 600 차원의 데이터이다. 이러한 그림 수천장을 분석해서 분류하는 일을 하는 사람은 고차원의 데이터를 다루고 있는 것이다.

#차원 축소(Dimension Reduction)

앞서도 언급했지만, 차원 축소는 2가지 측면에서 매우 중요하다.

• 데이터 분석의 전처리 (Preprocessing)


• 고차원 데이터의 시각화 (Visualization)

차원 축소하는 방법으로 가장 많이 알려진 것이 PCA (Principal Component Analsys, 주성분 분석)이다. 분산이 큰 성분을 분석해서 나타내는 것이다. 유사한 아이디어인 특이값 분해 (SVD)를 참고하는 것도 좋다. 하지만 PCA는 주성분이 아닌 부분은 완전히 무시가 되는 단점이 있다.

차원 축소할 때, 원래 차원에서의 주변 데이터와의 거리(Distance 또는 Identity)를 최대한 보전하는 방법이 있다. 그 방법중에 가장 성공한 알고리즘이 Stochastic Neighbor Embedding 이다.

#SNE (Stochastic Neighbor Embedding) 알고리즘

우리의 목표는 고차원(N)의 데이터(x) n개를 동일한 개수의 저차원(M)의 데이터(y)로 만들고자 한다. 그리고 차원을 줄이더라도 데이터간의 거리는 원래와 유사하게 하고자 한다.

데이터 간의 거리 및 선택 확률 분포

데이터간의 거리를 어떻게 정의할 것인가? 특정 차원에서 거리를 정의하는 방법은 다양하게 있을 수 있으나, 가장 일반적인 것은 유클리드 거리이다.

데이터의 분산 정도에 따라 그 거리의 의미(크기)가 달라지므로, 분산(또는 표준편차)으로 위 값을 나누어 정규화할 필요가 있다.

아래에 붙은 2는 나중에 활용할 표준 정규 확률 분포의 정의와 같게 하기 위함이다. 한가지 더 생각해 볼 것이 있다. 위의 수식에서 분산은 모든 x들에 대해 구한 값이다. 많은 데이터 중에서 xi 데이터 주변만 관심이 있다면, xi 주변의 특정 개수의 데이터만 가지고 분산을 구하는 것이 타당하지 않을까?

위의 수식을 Dissimilarities(우리말로는 다름도?)라고 부른다. 분산을 xi 주변의 이웃들(Local Neighbor)인 k개 만 가지고 구한 것이다. 이 k를 Perplexity(우리말로는?)라고 부른다. 위의 정의에 따르면 i와 j가 바뀌면 위의 값이 달라진다. 즉, i와 j에 대해서 비대칭이다.

정규분포를 활용하면 xi와 xj의 거리를 확률로 나타낼 수 있고, xi의 이웃 중에서 xj를 선택할 확률은 다음과 같이 정의할 수 있다.

참고로, 정규분포와 비교해 보시라. 평균으로부터 떨어진 거리에 따라 그 확률을 구할 수 있다.

고차원의 확률분포와 저차원 확률 분포 차이

고차원의 데이터 xi들 사이의 선택 확률(pij)은 위의 수식으로 정의가 되었고, 저차원의 데이터 yi들 사이의 선택 확률(qij)도 동일하게 정의할 수 있다. 편의상 분산을 1/2로 가정한다. (고차원 데이터에서 저차원 데이터를 구하려고 하는 것이기 때문)

위에서 정의한 확률분포들이(pij, qij) 가장 유사하게 하는 yi를 찾는 것이 목표이다. 확률분포들 사이의 차이를 나타내는 쿨백-라이블러 발산 (KL Divergence) 이라는 방법이 있다. 임의의 xi에 대한 비용 함수(Cost Function)를 아래와 같이 정의하자

우리는 모든 데이터 xi들에 대한 비용 함수(C)는 다음과 같다.

이제 문제는 위의 비용함수를 최소로 하는 yi들을 찾는 것이다. 즉 비용함수의 미분값이 영이 되는 yi를 찾는 것이다. (미분하는 것은 복잡해서 생략함. 최종 수식은 매우 단순함)

이론은 이게 전부이다. 이것을 구하는 알고리즘은 비용함수 최소화하는 일반적인 방법론으로 풀 수 있다. 그 알고리즘은 다음 기회에 다루고자 한다.

정규분포 대신에 t분포를 활용하는 알고리즘은 t-SNE이다.