[Dimensionality Reduction] Unsupervised Method (Nonlinear embedding) 1: ISOMAP, LLE
본 포스트는 고려대학교 산업경영공학부 강필성 교수님의 Business Analytics 강의를 정리한 내용입니다.
ISOMAP
ISOMAP은 MDS 절차 중 변환 이전에만 다른 알고리즘이다.
PCA와 MDS는 계산적으로 효율적이고, global optima를 찾을 수 있다. 하지만 선형 방법론의 단점 중 하나는 원래 데이터가 선형이 아니면 데이터를 파악하기가 힘들어진다.
만약 MDS나 PCA를 적용하면 3차원에서 최단 거리를 사용하기 때문에 부정확하다. 이 말은 선형 알고리즘을 사용하면 A에서 점선과 같이 부정확한 distance를 찾는다는 뜻이다. 우리는 청록색 직선과 같은 결과를 원한다.
이를 하려면 A에서 B로 graph 형태로 변환한다. 그리고 나서 가까운 이웃들을 따라가다 보면 목적지에 도달하게 된다. C와 같은 그림을 manifold라고 하는데, 우리는 정확한 직선을 찾지 못해서 약간은 돌아가지만 빨간 선처럼 최대한 최단 거리를 구하는 것이다.
ISOMAP은 MDS와 달리 가까운 노드들을 그래프로 변환 시켜 최단 거리를 구한다.
ISOMAP의 절차는 다음과 같다.
Step 1.
이웃간 그래프를 생성한다. 그래프를 생성하는 방법은 다음과 같다.
- $\epsilon$-Isomap : $\epsilon$ 보다 가까운 2개의 node를 연결한다.
- $k$-Isomap : 만약 $i$가 $j$의 k-nearest neighbor 중 하나라면 $i$와 $j$를 연결한다.
Step 2.
최단 거리를 찾는다. 최단 거리 distance를 구하는 알고리즘을 찾아 최단 거리를 통한다.
Step 3.
위에서 구한 distance matrix를 통해 MDS를 적용한다.
LLE (Locally Linear Embedding)
LLE는 eigenvector를 사용한 비선형 차원 축소법이다.
LLE는 PCA와 비슷하게 eigenvector를 사용한다. local optima에 빠지지 않고, 고차원의 데이터를 우리가 원하는 차원의 개수만큼 lower dimesion으로 변환할 수 있다. ISMAP과 LLE는 local 정보를 이용하는 면에서 공통점이 있다.
LLE의 절차는 다음과 같다.
Step 1.
각 data point의 이웃을 계산한다.
Step 2.
Original data를 가장 최적으로 재구축할 수 있는 이웃들의 가중치를 찾고, 아래 cost function을 통해 최적화한다.
$$ E(\mathbf{W})=\sum_{i}\mid \mathbf{x}{i}-\sum{j}\mathbf{W}{ij}\mathbf{x}{j}\mid^{2} $$
여기서 original data는 $\mathbf{x}{i}$이고, $\mathbf{x}{j}$는 이웃이고, 가중치는 original data를 재구축하기 위해 이웃에 부여되는 가중치이다.
만약 이웃을 가지고 original data를 재구축할 수 있는 경우, 즉 이웃들 간 polygon 안에 original data가 위치한 경우에는 가중치가 0이 된다. 그렇지 않은 경우에는 해당 data에 해당하는 이웃들의 weight의 합은 1이 된다.
Step 3.
original data를 가장 잘 구축하는 vector를 weight $\mathbf{W}$를 통해 eigenvector를 최소화한다.
$$ \Phi(\mathbf{W})=\sum_{i}\mid \mathbf{y}{i}-\sum{j}\mathbf{W}{ij}\mathbf{y}{i}\mid^{2} $$
$\mathbf{W}_{ij}$ 는 이미 step 2에서 구한 값이다. 우리는 이를 통해 $\mathbf{y}$를 최적화할 것이다. $\mathbf{y}$는 낮은 차원으로 임베딩 된 data의 좌표 값이다.
위 절차들을 정리하여 도식화하면 아래와 같다.
우리는 step 3에서 재구축된 $\mathbf{y}$를 원본과 최소화하는 문제로 변형할 수 있다.
$$ \min \Phi(\mathbf{W})=\sum_{i}\mid \mathbf{y}{i}-\sum{j}\mathbf{W}{ij}\mathbf{y}{i}\mid^{2} $$
LLE 논문에서는 최소화 문제를 잘 풀기 위해 다음과 같은 제약식을 가진다.
$$ s.t. \ \sum_{i}\mathbf{y}{i}=0, \ \frac{1}{n}\sum{i}\mathbf{y}\mathbf{y}^{T}= \mathbf{I} $$
첫 번째 제약은 data point의 평균을 0으로 centering 한 것이고, 두 번째 제약은 covariance는 $\mathbf{I}$라는 것이다. (대칭 행렬)
위 제약을 통해 수식을 아래와 같이 정리할 수 있다.
$$ \Phi(\mathbf{W})=\sum_{i}\mid \mathbf{y}{i}-\sum{j}\mathbf{W}{ij}\mathbf{y}{i}\mid^{2} \\ = \sum_{i}[\mathbf{y}^{2}{i}-\mathbf{y}{i}(\sum_{j}\mathbf{W}{ij}\mathbf{y}{j})-(\sum_{j}\mathbf{W}{ij}\mathbf{y}{j})\mathbf{y}{i}+(\sum{j}\mathbf{W}{ij}\mathbf{y}{j})^{2}] \\ =\mathbf{Y}^{T}\mathbf{Y}-\mathbf{Y}^{T}(\mathbf{W}\mathbf{Y})-(\mathbf{W}\mathbf{Y})^{T}\mathbf{Y}+(\mathbf{W}\mathbf{Y})^{T}(\mathbf{W}\mathbf{Y}) \\ = (\mathbf{Y}^{T}-\mathbf{Y}^{T}\mathbf{W}^{T})\mathbf{Y}-(\mathbf{Y}^{T}-\mathbf{Y}^{T}\mathbf{W}^{T})\mathbf{W}\mathbf{Y} \\ = \mathbf{Y}^{T}(\mathbf{I}-\mathbf{W}^{T})\mathbf{Y}-\mathbf{Y}^{T}(\mathbf{I}-\mathbf{W}^{T})\mathbf{W}\mathbf{Y} \\ =\mathbf{Y}^{T}(\mathbf{I}-\mathbf{W}^{T})(\mathbf{Y}-\mathbf{W}\mathbf{Y}) \\ =\mathbf{Y}^{T}(\mathbf{I}-\mathbf{W}^{T})(\mathbf{I}-\mathbf{W})\mathbf{Y} \\ = \mathbf{Y}^{T}(\mathbf{I}-\mathbf{Y}), \ (\mathbf{M}=(\mathbf{I}-\mathbf{W})^{T}(\mathbf{I}-\mathbf{W})) \\ \therefore \ \mathbf{Y}^{T}\mathbf{M}\mathbf{Y} $$
위 수식을 라그랑제 승수 $\alpha$를 이용해 $L$로 나타내면 아래 식과 같이 표현할 수 있다.
$$ \frac{\partial L}{\partial \mathbf{Y}}=(\mathbf{Y}+\mathbf{Y}^{T})\mathbf{M}-\frac{2}{m}\alpha\mathbf{Y} \\ = 2\mathbf{M}\mathbf{Y}-\frac{2}{m}\alpha\mathbf{Y} \\ =0 \\ \therefore \mathbf{M}\mathbf{Y}=\frac{\alpha}{m}\mathbf{Y} $$
위 결과를 통해 $\mathbf{Y}$는 $\mathbf{M}$의 eigenvector 인 것을 알 수 있고, $\frac{\alpha}{m}$은 eigenvalue 인 사실을 알 수 있다.