Manifold Learning(多様体学習)과 알고리즘

 Manifold의 학습은 곧 다른 의미로 kernel 테크닉의 예시라고 할 수 있다. Kernel이 given data를 High-dimensional Reproducing Kernel Hilbert Space에서 갖고 논다면, Manifold를 배우는 것은 그 반대로 dimension을 효과적으로 줄이는 과정이다.

 고차원의 데이터(이미지 등)은 그 자체로는 다루기 까다롭다. 가령 일반적으로 사용되는 euclidean distance도 차원에 값 영향을 많이 받는다. 하지만 대부분의 고차원 데이터는 그 안에 manifold를 가지기 마련인데, 가령 object의 성격이 제한될 때(e.g., 특정 강아지 사진) 데이터 내부적으로 dependent한 correlation이 생기기 때문이다. (e.g., 강아지의 눈, 코, 귀 위치는 어느 정도 예측 가능한 범위에 있다) 즉 이러한 데이터의 고유한 구조를 impact하게 학습하고, 이를 visualize할 수 있다면 데이터의 이해에 도움이 된다.

 

1. Manifold Learning의 필요성

1) 클러스터링의 관점에서

 데이터 xi∈R의D승이 D차원 공간에 플롯되어있을 때, 데이터에 의미가 있으면 유사한 데이터는 가까운 위치에 나타날 것이라고 기대된다. 이러한 생각을 토대로 K평균 등으로 데이터를 클러스터링하는 것이 가능하다.

 그러나, 실제로 유사한 데이터는 반드시 D차원 공간 상에 가까운 위치에 존재하지 않을 수 있다. 예를 들면 아래와 같은 데이터가 있다고 가정해보자 (비슷한 색상의 점들은 비슷한 데이터를 의미). 3차원 공간에서의 데이터가 배열되어 있다. 빨간색은 중심에 모여있지만, 파란색이나 초록색은 넓게 분포되어 있다. 이런 데이터에 대해 K-평균법 등을 사용하여 클러스터링을 실시해도 의미있는 결과를 얻지 못한다.

 그럼에도 어떠한 법칙에 의해 데이터가 공간 상에 배치되어있다고 생각할 수 있다. 우리는 그러한 법칙을 찾을 필요가 있다.

2) 차원감소의 관점에서

 기계학습이나 데이터분석에서 차원 감소라는 방법이 필요해졌다. 차원감소는 고차원의 데이터를 가시화하기 위해 3차원 미만으로 떨어뜨리거나, 데이터를 기계학습에 이용할 때 불필요한 성분을 떨어뜨리는 것을 의미한다.

 특히 가장 유명한 PCA(;Principal Component Analysis)에서 구현도 단순하므로 많은 방면에서 활용되고 있다. ICA(;Independent Component Analysis)도 유명하다. 이러한 것들은 기본적인 아이디어는 고차원 데이터 xi=(x1,⋯,xD)∈R의D승의 각 성분을

 위와 같이이 선형 결합하는 것으로, 더 뛰어난 성분 x′을 얻을 수 있는가에 대한 것이다. 뛰어난 성분은 복수여도 좋고, 위에서 언급하였듯 선형 결합을 몇 개 생각할 수 있다면

이라고 표시하는 것도 가능하다. 간단히 말하자면 배열 A를 잘 정하고 싶은 것이라고 할 수 있다. 이러한 방법들은 어디까지나 선형변환에 의해 뛰어난 성분을 찾고 싶어하는 것이다. 따라서 x는 공간 상에서 확장, 회전을 할 뿐이다 (또는 좌표계를 회전하고 있다고 봐도 좋다).

 그렇게하여 얻어낸 d(≤D)개의 성분은 좋은 성분인지는 경우에 따라 다르다. 예를들어 분류 문제의 특징량으로써 이용하고 싶은 경우에는 분리가 분리가 잘 되는 부분공간만을 얻어내는 것이 중요하다. 이러한 케이스에서 예를 들어 아래와 같이 3차원 공간의 데이터 (사실 아까의 그림과 같은 그림)에 대해 선형 변환 방법은 별로 도움이 되지 않는다. PCA나 ICA로 데이터를 2차원 데이터로 차원하여 2차원 평면을 좋아하는 각도로 놓고 여기서 데이터를 투영하는 것이다.

 게다가 지금은 어디까지나 3차원의 데이터를 취급하고 있기 때문에, 선형에서는 선형으로는 안될 것 같다고 눈으로 보고 판단할 수 있다. 그러나 보통의 데이터는 그럴 수도 없기 때문에 더욱 판단이 어려워졌다.

 

2. 다양체란?

 다양체는 간단히 말하자면, 국소적으로 본다면 선형공간으로 나태날 수 있는 공간이다. 아래의 데이터는 3차원 공간에 보존되어 있지만 실제로는 2차원이다. 그 이유는 직사각형이 둥글게 말아졌을 뿐이며 국소적으로 본단면 단순한 평면에 불과하다.

 따라서 이런 데이터는 3차원공간에 포함된 2차원 다양체라고 할 수 있다.

 

3. Manifold Learning의 의도

 아까전에, K-평균법을 잘 사용할 수 없다고 말했다. 사실, 2차원 다양체가 포함된 아까의 그림에서는 '빨간색과 오렌지의 거리'와 '빨간색과 황녹색의 거리'를 3차원 공간에서 비교한 경우, (색은 본래 전자가 비슷함에도 불구하고) 후자의 쪽이 가깝다.

 그러나 실제로는 빨간색과 오렌의 쪽이 가까운 데이터이다. 만일 아까의 이미지가 컬러가 아니고 전형 정보가 없다고 하자. 그렇다고 해도 보통은 하나로 연결되어 있다는 것이 주목하고 싶어 질 것이다. 멀어도 하나로 연결되어 있는 쪽이 가깝다고 생각하는 방식이어도 좋을 것이며, Manifold Learning이 이러한 방법을 제공한다.

 먼저 기본적으로 '하나로 연결되어 있다'라고 의식하는 것은 데이터에따라 곡선적으로 거리를 측정하기 때문이다. 그렇게 하면 빨간색과 오렌지는 가까운 위치에 있다고 말할 수 있다. 이것은 데이터를 다양체로 파악하는 것과 동일하다. 즉 굽은 좌표를 데이터에 따라 구성하고 있는 것이다.

  아래는 굽은 좌표를 데이터상에 배열해, 그 좌표를 새로운 세로축과 가로축으로 분산도를 표시한 것이다. 

 x∈R의 D승은 어디까지나 사람이 데이터를 모으는 방법이므로 좌표가 정해지고 만다. 데이터가 가진 본질적인 좌표를 다시 잡는 것이 Manifold Learning인 것이다. 그런데 구부러진 좌표를 세운다는 것은 말하자면 PCA나 ICA와 같은 곧은 좌표를 공간상에 좋은 각도로 다시 배치하는 것의 진화판이라고 볼 수도 있다. 구부러진 좌표를 배치하고 그것을 늘려 똑바로 한다는 것은 곧 데이터에 대해 비선형변환을 하고 있는 것과 다름없다.

 

4. 다양한 Manifold Learning 알고리즘의 예 

1) Isometric feature mapping(Isomap)

Isomap은 가장 오래되고 기초적인 manifold learning 알고리즘 중 하나이다. 데이터 간의 linear distance를 기반으로 graph representation을 학습한다. 과정은 다음과 같다.

 Isomap은 각 데이터 별로 충분히 가까운 데이터들에 대한 인접 그래프를 얻어 매니폴드를 표현하는 과정이다. 이때 두 데이터(노드) 간의 최단 경로를 euclidean distance를 기반으로 구하며, 이는 곧 high-dimensional space에서도 충분히 local한 영역에 대해서는 euclidean space를 합당하게 가정할 수 있기 때문이다.

2) Locally Linear Embedding(LLE)

LLE 역시 geometric intuition에 기반한 linear model를 이용해 manifold를 배운다. High-dimensional data는 Global한 관점에서 non-linear하지만, 이를 우선 무시하고 Isomap과 비슷하게 각 데이터의 이웃들이 locally linear하다고 해보자. 원 데이터 D=[x1,x2,...,xN], x∈R의d승을 [z1,z2,...,zN], z∈R의 k승으로 보내는 것이 목적이다.

과정은 다음과 같다.

3) Stochastic Neighbor Embedding(SNE)

LLE가 neighbor 및 weight assignment를 ‘hard’하게 했다면, SNE는 ‘soft’하다. 즉 “neighborhood” 그 자체를 stochastic하게 정의하는 것이다. High dimensional space에서 어떤 data point와의 거리가 가까울 수록 해당 point와의 관계를 tight하게 유지하며, 이는 딱 잘라 neighbor를 정의했던 LLE와 다른 점이다.

가령 i-th data point 관점에서 j-th point에 대한 neighborhood 혹은 영향력은 조건부 확률 형식을 빌려, pj∣ipj∣i으로 표현한다. 이를 gaussian distribution 형식으로 표현하면 다음과 같다.

• 이때 σiσi는 각 데이터에 대해 개별적인 hyper-parameter이다.
• Softmax의 temperature parameter와 비슷한 역할을 하는데, sigmasigma가 작을 수록 두 데이터 포인트의 차이는 보다 부각되며 local한 영향력이 커진다.
• 반면 sigmasigma가 작다면 보다 넓은 범위의 point들이 영향력을 미치게 된다. SNE에서 가장 중요한 hyper-parameter라고 할 수 있으며 데이터가 너무 작은 경우 sigma를 줄여야 한다.

위와 동일한 논리를 low dimensional space의 vector y에 적용할 수 있다.

이렇게 i-th data point에 대해 high, low-dimensional neighborhood probabilistic distribution Pi,Qi를 얻었다. SNE의 핵심은 서로 다른 두 space에서 구한 distribution이 크게 차이가 나지 않도록 만든다는 것이다.

t-SNE는 SNE와 본질적으로 크게 다르지 않은 알고리즘이다. SNE에서는 conditional probability로 (i, j) 관계를 표현하였으며 이는 진정한 distance metric이라 할 수 없는데, asymmetric하기 때문이다. 따라서 이를 보완하고, SNE의 gaussian 대신 t-distribution을 사용한 것이 t-SNE이다. 즉 ,

으로, conditional probability 형식이 아니다. 또한 student t-distribution을 사용하는데, 이는 t-distribution이 gaussian 대비 heavy tail을 갖기 때문에 high dimension space에서의 large distance를 반영하기 더 유리하기 때문이다.

df=1일 때 t-SNE에서 neighborhood representation qijqij는 다음과 같다.

 이는 t-distribution의 chi-squared 항이 반영된 것으로 보인다. 1이 붙은 이유는 역수를 취하는 과정에서 inf가 나오지 않도록 추가한 것이다. 직관적으로는 (i, j)가 가까울 수록 확률적으로 두 data point는 가까운 state이며, 따라서 yi,yjyi,yj가 크게 변하지 않을 가능성이 높다.
MNIST에 적용한 예시는 다음과 같다.

더욱 다양한 알고리즘을 살펴보고 싶다면 아래의 링크를 참고

https://scikit-learn.org/stable/modules/manifold.html

2.2. Manifold learning — scikit-learn 0.22.2 documentation

---

참고자료

https://www.hellocybernetics.tech/entry/2017/07/06/133450

https://parkgeonyeong.github.io/Manifold-Learning-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-(SNE,-/.)/