[Dimensionality Reduction] - Locally Linear Embedding (LLE)

• nonlinear dimensionality reduction울 위해 eigen vector를 사용
  • 구현이 쉽다
  • 최적화가 local minia를 포함하지 않는다.
  • 높은 수준의 nonlinear embedding이 가능
  • 높은 차원의 데이터를 낮은 차원의 좌표 시스템으로 mapping 가능
• LLE 과정
  • 1) 각 데이터 포인트에 대해 이웃을 계산한다.
  • 2) 각 데이터 포인트의 이웃을 으로 부터 reconstruction cost function이 최소화되는 Weight matrix를 구한다.
    
    • $ E(W) = \Sigma_{i} | x_{i} - \Sigma_{j}W_{ij}x_{j}|^{2} $ 
    • $s.t. W_{ij} = 0 if x_{j} does not belong to the neighbors of x_{i} $
    • $\Sigma_{j} W_{ij} = 1 $ for all i 
  • 3) 2)에서 구한 Weight Matrix를 사용하여 하위의 non-zero eigen vector를 구한다. 
    • $ \phi(W) = \Sigma_{i} | y_{i} - \Sigma_{j} W_{ij}y_{j} |^{2} $
  • 주변의 객체 $x_{j}$로 부터 $x_{i}$를 reconstruction 할 수 있다면 $E(W)  = 0$ 이다
  • 주변의 객체 $x_{j}$로 부터 $x_{i}$를 reconstruction 할 수 없다면 $E(W)  > 0$ 이다
  • $ y_{i} $의 차원은 $ x_{i} $ 차원보다 낮다.

 

• LLE 과정(con't)
  • 만약 $x_{i}$ 가 이웃의 convet set 안에 위치한다면 $ \epsilon(W) = 0 $ 이다.
  • Step3의 $ Y_{i} $를 찾는 방법은?
    • $ min_{y} \phi(W) = \Sigma_{i} | y_{i} - \Sigma_{j} W_{ij}y_{j} |^{2}$ => $ \phi(W) = \Sigma_{i,j} M_{ij} (y_{i}y_{j}) $
    • where $ M_{ij} = \delta_{ij} - W_{ij} - W_{ji} + \Sigma_{k} W_{ki}W_{kj}, \delta_{ij} = 1 if i = j, 0  $ otherwise
    • $ s.t. \Sigma_{i} y_{i} = 0, {1 \over {n} } \Sigma_{i} yy^{T} = I $
    • $ s.t. \Sigma_{i} y_{i} = 0 $ 는 embedding된 $ y_{i}  $ 각 변수 의 평균이 0 이다.
    • $ {1 \over {n} } \Sigma_{i} yy^{T} = I $, 각 변수들은 직교한다.
    • eigen value가 작은 eigen vector를 찾는다.
    • N X (d+1) 차원의 값을 찾고 bottom 값을 제거하면 N X d 차원의 embedding vector인 y를 얻을 수 있다.