Locally Linear Embedding (LLE)

-
01_6 : Dimensionality Reduction : ISOMAP & LLE 

Locally Linear Embedding(LLE)

LLE는 eigenvector를 사용한 nonlinear dimensionality reduction 방법으로써, 아래와 같은 특징이 있다.
  • 구현하기가 쉽다.
  • Local minima에 빠지지 않는다. (즉, 반드시 Global minima를 찾는다)
  • highly nonlinear embedding또한 찾아낼 수 있다.
  • 고차원의 data를 원하는 차원의 저차원으로 바꿀 수 있다.


LLE Procesure

  • Step1 : 각 Data point $x_i$에 대하여 K개의 이웃(neighbor)을 구한다. (K는 Hyperparameter)
  • Step2 : 각 Data point를 neighbor $x_j$에 대하여 reconstruct하는데 가장 적합한 $W_ij$를 찾는다. (Cost function을 최소화 하는 $W_ij$)
아래의 그림을 예시로 생각해보자.
각 Data point $x_i$에 대하여 neighbor $x_j$들을 통해 reconstruct 하고자 한다. 이러한 과정은 아래 수식으로 표현된다.
$$ E(W)=\sum_i\left| x_i - \sum_j W_{ij}x_j \right|^2 $$
$$s.t.\; W_{ij} = 0\;if\;x_j\;does\;not\;belong\;to\;the\;neighbor\;of\;x_i$$
$$\sum_j W_{ij} = 1\;for\;all\;i$$
위의 예시에서 $x_i$는 주변의 neighbor로 구성되는 Convex Hull에 포함되고, neighbor로 부터 완벽하게 reconstruct 될 수 있다. 따라서 이 경우 $E(W) = 0$일 것이다.

반면 아래의 예시에서 $x_i$는 주변의 neighbor로 구성되는 Convex Hull에 포함되지 않고, neighbor로 부터 완벽하게 reconstruct 될 수 없다. neighbor로 부터 reconstruct되는 $x_i$의 정보는 $\sum_j W_{ij}x_j$인데, 이는 $x_i$와 오차가 있다. 따라서 이 경우 계산되는 $E(W) > 0$일 것이다. 이때 이 $E(W)$를 최소화 하는 $W$ matrix를 구해야 한다.
다시말해 우리가 Step 2에서 하려는 동작은 $X$를 알고있을 때, $W$를 최적화 하려는 것이다.

+Step 2의 최적화 문제는 단순 계산을 통해 최적의 $W$값을 구할 수 있다. Convex안의 $x_i$가 neighbor의 Convex set 안에 있다면, 적당한 $W_{ij}$에 대하여 $E(W)=0$일 것임으로 적당한 $W_{ij}$으로 손실 없이 $x_i$를 Reconstruct 가능하다. 
Convex set 밖에 있다면, 위의 그림처럼 Convex Hull에서 수직이 되도록 $\sum_j W_{ij}x_j$를 구성하는 $W_{ij}$를 찾는경우가 $x_i$에 가장 가깝게 위치할 것이고, 이 경우 $E(W)$가 최소가 될 것이다.

이제 Step 3를 살펴보자.
  • Step 3 : 위의 Step 2에서 최적화한 $W$를 기반으로 아래의 $\Phi(W)$를 최소화 하는 $Y$를 구한다.
$$ \Phi(W)=\sum_i\left| y_i - \sum_j W_{ij}y_j \right|^2 $$
이제 Step 2에서 구한 $W$를 기반으로 $Y$를 최적화 한다. 기존의 Data $x_i$가 $x_i\in \mathbb{R}^d$이었다면, 새롭게 구한 $y_i$는 $x_i$의 정보를 embedding 하면서 저차원으로 표현된다. $y_i\in \mathbb{R}^{d^\prime}\;\;(d^\prime<d)$

이 과정을 예시를 보면서 다시한번 살펴보자.
$X$는 5차원의 Data이다. Step 1에서 각 $X_i$의 neighbor들을 구하고, Step 2에서 각 $X_i$들을 최소한의 $E(W)$로 $X_i$의 재구축이 가능한 $W$를 찾는다. 이제 마지막으로 $W$를 기반으로 2차원인  data $Y$로 embedding 한다.

LLE의 목적은 data $X$에서 data $Y$로 차원 축소 할 때, 각 원소들 사이의 유사성관계, 재구축에 기여하는 정도에 대한 정보를 최대한 유지하는 것이다. 
Step 2에서 구한 $E(W)$를 최소화 하는 $W$가 바로 각 원소들간의 유사성관계를 표현하고, Step 3에서 구한 $\Phi(W)$를 최소화 하는 $Y$가 바로 유사성관계를 최대한으로 유지하면서 차원 축소된 data이다.


LLE Procesure (Cont.)

Step 3에서 $y_i$를 구하는 과정을 살펴보자.
$$ \Phi(W)=\sum_i\left| y_i - \sum_j W_{ij}y_j \right|^2 $$
식을 풀어서 쓰면,
$$ \left| y_i - \sum_j W_{ij}y_j \right|^2=y_i^T (I- \sum_j W_{ij})^T(I- \sum_j W_{ij})y_j$$
식을 정리하면 아래와 같이 나타난다.
$$ \Phi(W)=\sum_iM_{ij}(y_i \cdot y_j)$$
$$where\;\;M_{ij} = \delta_{ij}-W_{ij}-W{ji}+\sum_kW_{ki}W_{kj},\;\;\delta_{ij}=1\;\;if\;\;i=j,\;\;\delta_{ij}=0\;\;otherwise$$
$$s.t\;\;\sum_iy_i = 0,\;\;\frac{1}{n}\sum_iyy^T=I$$
이제 각 제약조건을 생각해보자. 
먼저 $\sum_iy_i = 0$ 조건은 embedding된 공간에서 각 변수들의 평균이 0이라는 조건이다.
그리고 $\frac{1}{n}\sum_iyy^T=I$ 조건은 embedding된 공간에서 각 변수들이 모두 Orthogonal 하다는 조건이다.

위의 식을 다시 행렬식으로 살펴보자.
$$ \Phi(W)=\sum_i\left| y_i - \sum_j W_{ij}y_j \right|^2 $$
$$ \Phi(W)=[(I-W)y]^T[(I-W)y] = y^T(I-W)^T(I-W)y = y^TMy$$
정리하면 우리가 구하고자 하는 최소값 y는 아래의 최적화 문제로 표현된다.
$$min\;\;y^TMy$$
$$s.t\;\;yy^T=1$$
PCA에서 살펴본 것처럼 이제 우리가 구하고자 하는 y는 제약조건이 있는 최적화 문제로 표현된다.
PCA의 최적화 문제는 
$$max\;\;w^TSw$$
$$s.t\;\;w^Tw=1$$
이고 이때 최적해는 $S$의 eigenvalue/eigenvector 이었다. PCA는 maximize 하는것이 목표이기 때문에 eigenvalue를 내림차순으로 정렬하고, 그중 K개의 eigenvector를 선택하여 사용했다.
반면 LLE는 minimize 하는것이 목표이기 때문에 eigenvalue가 작은 eigenvector를 선택해야 할 것이다.


LLE Procesure (Cont.)

위의 최적화 문제를 푸는 방법으로 Rayleitz-Ritz theorm을 사용한다. 이 내용을 깊게 이해하기에는 너무 어려움으로 결론만 알아보도록 하자. Rayleitz-Ritz theorm에 의해서 우리는 아래의 정리를 가져올 수 있다.
  • 우리는 행렬 M의 가장 밑 d+1개의 eigenvector를 사용해서 최적해를 찾을 수 있다. (행렬 M의 eigenvector는 내림차순으로 정렬되어 있다)
  • 가장 밑에 있는 eigenvector는 unit vector 이면서, 모든 원소(component)로 같은 값을 가진다. (가장 eigenvalue가 작은 eigenvector)
  • 가장 밑의 eigenvector를 제거하면, 나머지 d개 embedding의 평균값이 0이 된다. (이 나머지 d개의 vector가 우리가 구하려는 embedding vetor이다)

위의 정리를 바탕으로 LLE는 다음과 같이 전개된다.
  1. Original Data X : 처음의 data는 D개의 variable과 N개의 원소를 가진다. D by N matrix로 표현된다.
  2. Neighborhood matrix W : Step 2를 통해 E(W)를 최소로 만드는 W를 구한다.
  3. M : W의 sparse matrix를 구한다. $M=(I-W)^T(I-W)$
  4. Eigenvectors V : M으로부터 가장 작은 eigenvector 부터 d+1개의 eigenvector를 구한다. 
  5. Embedded mapping Y : d+1개의 eigenvector로 구성된 V에서 가장 작은 eigenvector를 제거한다.
결과적으로 구한 $Y$ 행렬이 우리가 구하고자 하는 Embedding mapping이 완료된 d 차원의 data이다.



※ 이 글은 고려대학교 산업경영공학과 강필성 교수님의 IME654 강의를 참고하여 작성되었습니다.

댓글

댓글 쓰기

이 블로그의 인기 게시물

One-Class SVM & SVDD

-
이미지
03_6 : Anomaly Detection : Auto-Encoder, 1-SVM, SVDD MoG와 같은 밀도기반 방법론들은 특정 객체가 정상범주에 속할 확률을 구했다. 반면 Support vector 기반 방법론들은 normal과 abnormal을 구분하는 분류경계면을 찾는다. 이번 글에서는 Support vector 기반의 Anomaly detection 방법 중 one-class SVM과 SVDD를 알아보자. One-class Support Vector Machine (1-SVM, OCSVM) 1-SVM의 목표는 Data를 feature space로 mapping 한 뒤, 분류경계면을 통해 mapping된 Data 중 normal data들이 원점으로부터 최대한 멀어지게 만드는 것이다. 위 그림에서 파란색 분류경계면이 (+1) normal data들을 구분하는 것을 확인할 수 있다. 이 목표를 수식화 한 Optimization problem부터 살펴보자. Optimization Problem $$\min_{\textbf{w}}\;\;\;\frac{1}{2}||\textbf{w}||^2 + \frac{1}{\nu l} \sum_{i=1}^l \xi_i - \rho$$ $$s.t.\;\;\;\textbf{w}\cdot \Phi (x_i) \geq \rho - \xi_i\;\;\;\;(i=1,2,\cdots,l),\;\;\xi_i\geq 0$$ $\frac{1}{2}||\textbf{w}||^2$ term은 SVR과 같이 $x$의 변화에 따른 변동이 크지 않도록 Regularization을 하는 term이다. $\rho$는 위 그림에서 주황 직선을 나타내는데, 원점과 분류경계면 Hyperplane과의 거리를 나타낸다. 이 값을 뺌으로써 최소화 문제를 만족하는 최적해일때 $\rho$가 최대가 되도록 한다. (원점에서 Hyperplane이 최대한 멀어지게 만든다) $\frac{1}{\nu l} \sum_{i=1}^l \xi_i$ term은 제약식에 따라 Hyp...
자세한 내용 보기

Support Vector Regression (SVR)

-
이미지
02_4 : Kernel based learning : Support Vector Regression (SVR) 앞에서 공부했던 SVM은 binary classification을 하기 위한 방법이었다. 이번 글에서 알아볼 SVR은 함수를 추정하여 연속적인 수치변수를 예측하는 회귀 방법이다.  SVR을 알아보기에 앞서 우리가 하려는 함수추정의 목적을 살펴보자. Fitting function 함수를 추정하고 싶을 때 우리의 목적은 크게 2가지로 나뉜다. Minimize an error measure (Loss function) 한마디로 error를 최소화 하여야 한다. (잘 맞춰야 한다) Function to be simple 같은 성능이라면, 함수는 최대한 단순해야 한다. 함수가 단순하다는 뜻은 아래의 조건들을 의미한다. Fewest basis functions Simplest basis functions Flatness is desirable Support Vector Regression (SVR) 위에서 살펴보았던 Loss function과 Flatness를 반영하도록 목적함수를 만들 것이다. SVR에도 여러 종류가 있는데, 우선 $\varepsilon$-SVR에 대하여 알아보자. 현실의 Data들은 어쩔 수 없이 발생하는 noise가 존재한다. 아래 식에서 noise는 $\varepsilon$이다. $$y = f(x)+\varepsilon$$ $\varepsilon$-SVR에서 핵심 아이디어는 $\varepsilon$ 보다 작은 noise에 대해서는 Loss를 주지 말자는 것이다.  왼쪽 그림에서 색이 칠해진 영역을 Epsilon-tube 라고 하는데, 이 영역안에 있는 객체들에게는 Loss를 부여하지 않는다. 이를 위한 Loss function은 오른쪽에 표현된다. 이 Loss function은 hinge를 닮았다고 해서, Hinge Loss 라고 불린다. 차이가 $\varepsilon$ 보다 작은 경우 loss는 0이고, $\vareps...
자세한 내용 보기

Self-Training & Co-Training

-
이미지
 05_2 : Semi-Supervised Learning : Self-Training and Co-Training 우선 가장 기본적인 준지도학습 방법 Self-Training에 대하여 알아보자.  Self-Training 우리에게 주어진 정보는 Labeled data $(\mathbf{X}_l,y_l)$과 Unlabeled data $\mathbf{X}_u$이다. Self-training과정은 다음과 같이 진행된다.  1. 우선 주어진 Labeled data $(\mathbf{X}_l,y_l)$를 사용하여 예측함수 $f$를 학습시킨다. $$y_l = f(x_l)$$ 2. 학습이 완료되면, 예측함수 $f$를 사용해 Unlabeled data $\mathbf{X}_u$의 예측값 $\hat{y}_u$를 구한다. $$\hat{y}_u = f(x_u)$$ $$\Downarrow$$ 3. 이제 기존의 Labeled data와 예측함수에 의해 labeling이 된 Unlabeled data를 합치고, 이 data를 사용해 예측함수 $g$를 학습한다. 이때 어떻게 Unlabeled data를 합치는지에 따라서 많은 variation이 있다. 대표적으로 Add all $(x_u,\hat{y}_u)$ to labeled data Add a few most confident $(x_u,\hat{y}_u)$ to labeled data Add all $(x_u,\hat{y}_u)$ to labeled data, weight each by confidence. 모든 Unlabeled data를 합치는 방법, 몇몇개의 가장 예측 confidence가 높은 data만을 합치는 방법, 모든 data를 합치치만 예측 confidence에 따라서 weight를 지정하는 방법 등이 있다. 4. 위와 같은 과정을 Unlabeled data가 없어지거나, 수렴할 때 까지 반복한다. Propagating 1-Nearest Neighbor 다른 예시로 Propagating ...
자세한 내용 보기