[AI] 존슨-린덴스트라우스 정리를 통한 랜덤 투영, 지역 선형 임베딩(LLE)

들어가며

저번 글에서는 PCA에 대해 알아보았는데

매우 고차원의 데이터셋의 경우 PCA는 시간적으로 너무 느려져 효율이 떨어진다

대신 이 경우 사용 가능한 방법으로는 랜덤 투영이 있다

오늘은 랜덤 투영에 대해 알아볼 것이다

추가로 PCA와 랜덤 투영과 달리 투영 방식에 의존하지 않는 매니폴드 학습 방식을 사용하는

지역 선형 임베딩(LLE)에 대해서도 알아볼 것이다

 

랜덤 투영

이름만 들었을 때는 랜덤한 차원으로 투영하는건지 데이터를 랜덤으로 선택해서

특정 차원으로 투영시키는건지 쉽게 이해가 가지 않을 수 있다

랜덤 투영은 데이터에 랜덤한 행렬을 곱해서 낮은 차원으로 투영시킨다

이 방식의 핵심 아이디어는 고차원에서는 대부분의 데이터가 차원을 줄여도 거리 구조가 망가지지 않으며

특정한 최적의 방향으로 투영하지 않고 랜덤한 방향으로 투영하더라도

높은 확률로 거리 구조가 잘 보존된다는 것이 것이다

 

물론 당연히 매우 낮은 차원으로 랜덤하게 투영하면

많은 정보가 손실되고 거리가 왜곡되게 된다

 

그렇다면 적절한 차원을 어떻게 정할 수 있을까?

이 질문에 대한 대답은 존슨과 린덴스트라우스의 정리에서 시작된다

 

존슨과 린덴스트라우스는 거리가 주어진 허용 오차 이상으로 변하지 않도록 보장하기 위해

보존할 최소 차원 수를 결정하는 방정식을 생각해내었다

예를 들어 20000개의 특성과 5000개의 샘플로 구성된 데이터셋이 있고

두 샘플 간의 제곱 거리가

10%를 초과하여 변경되지 않도록 하려면 d >= 4log(m) / (1/2 ε ^2 - 1/3 ε ^3)인 d값으로 최소 7300차원으로 투영하면 된다20000 -> 7300 이면 엄청난 차원 감소라고 볼 수 있다

 

사이킷런의 johnson_lindenstrauss_min_dim() 함수를 통해 방정식을 사용해 최적의 차원 수를 구할 수 있다

from sklearn.random_projection import johnson_lindenstrauss_min_dim

m, ε = 5_000, 0.1
d = johnson_lindenstrauss_min_dim(m, eps=ε)

n = 20_000
np.random.seed(42)
P = np.random.randn(d, n) / np.sqrt(d)
X_reduced = X @ P.T

이런식으로 원본 데이터에 랜덤 행렬을 곱해주기만 하면

축소된 차원의 데이터로 변환된다

 

여기서 랜덤 행렬을 생성하는 방식은 가우시안 분포를 이용한 것으로

평균 0, 분산 1이 되도록 값이 되도록 행렬을 구성하고 루트d를 나누어 스케일링을 해주어

데이터가 거리 구조적으로 원본에서 크게 왜곡되지 않도록 한다

 

GaussianRandomProjection 클래스에서 위의 과정의 작업을 함수로 구현한 걸 사용할 수 있다

from sklearn.random_projection import GaussianRandomProjection

gaussian_rnd_proj = GaussianRandomProjection(eps=ε, random_state=42)
X_reduced = gaussian_rnd_proj.fit_transform(X)

 fit()을 통해 johnson_lindenstrauss_min_dim()으로 출력할 차원을 결정하고

랜덤 행렬을 생성하여 components_ 속성에 저장한다

이후 transform()을 통해 이 랜덤행렬을 사용하여 투영을 진행시켜 최종 결과값을 도출해낸다

 

지금까지는 가우시안 분포를 통한 랜덤 투영이였고

랜덤 투영을 희소 행렬로 생성하여 투영시키는 방식도 있다

사이킷런에서 SparseRandomProjection 클래스를 통해 이 방식을 사용할 수 있다

 

이 방식은 가우시안 방식과 동일하게 차원을 결정하고 동일한 방식으로 투영을 진행한다

차이점은 랜덤 행렬이 희소한 행렬이라는 것이다

 

희소한 랜덤 행렬에서 0이 아닌 항목의 비율 r을 밀도라고한다

밀도는 1/루트n으로 계산하며 n은 샘플의 개수를 의미한다

이 값은 원하는 경우 density 매개변수 값을 다른 값으로 설정 가능하다

랜덤 행렬의 각 항목 중 0이 아닌 것의 값은 -v 또는 +v이며

v = 1/루트dr이다 d는 줄일 차원수이고 r은 밀도이다

 

규모가 크거나 데이터셋 자체가 희박한 경우 

가우시안 방식보다 희소행렬 방식이 더 성능이 좋게 나올 것이다

 

지역 선형 임베딩(LLE)

 

PCA, 랜덤 투영은 선형 차원 축소 기술이였다면

지금부터 알아볼 LLE는 비선형 차원 축소 기술이다

 

투영에 의존하지 않는 매니폴드 학습방식을 사용하고

각 훈련 샘플이 최근접 이웃에 얼마나 선형적으로 연관되어 있는지 측정하고

국부적인 관계가 가장 잘 보존되는 저차원 표현을 찾는 방식이다

 

 

왼쪽 데이터에서 LLE 방식을 적용시키니 오른쪽 그림처럼 차원 축소된 모습이다

3차원의 데이터들 각각이 근접한 이웃들과의 거리가 최대한 보존되도록 재배치하여 펼쳐진 것과 같은 모습이다

 

LLE가 동작하는 방식은 우선 한 훈련 샘플 x에 대해 k개의 최근접 이웃을 찾는다

이후 이웃에 대한 선형 함수로 x를 재구성한다

위 식에서 오른쪽 항이 이웃에 의해 재구성된 점이고

샘플 x에서 재구성한 점 사이의 제곱 거리가 최소가되는 w값을 찾아 행렬을 구성한다

 

이후 행렬W는 샘플들 사이의 지역 선형 관계를 담고있는 행렬이 되었고

이제 d차원의 공간으로 만들어주어야한다

 

이때도 위에서와 비슷한 식을 사용한다

여기서는 왼쪽 항은 실제 축소된 차원의 점을 의미하고

오른쪽 항은 이웃으로 재구성한 점이다

 

위의 단계에서도 이웃으로 재구성한 점이지만

위에서는 원래 데이터로 재구성한 점이고

지금 단계에서는 차원 축소를 시킨 데이터로 재구성한 점을 의미한다는 부분이 다르다

 

이번에는 w값 즉 가중치만 알고있고 y값은 미지수로 주어진다

실제 점과 이웃으로 만든 추정값 사이의 오차를 최소화하는 y값을 찾아 행렬을 구성하면

최종적으로 축소된 차원의 데이터를 얻게되는 것이다

 

이 방식은 투영 기법과 비교하면 훨씬 복잡하지만

데이터가 비선형인 경우 훨씬 나은 저차원 표현을 구성할 수 있을 것이다

 

마치며

이번 글에서는 랜덤 투영과 지역 선형 임베딩 방식에 대해 알아보았다

특히 LLE의 작동 방식에 대해 공부할 때 변수 사이의 관계나 수식의 흐름이 되게 복잡하게 다가와서

이해하는 데에 꽤나 시간이 걸렸다

LLE는 비선형 데이터셋에서는 강점을 보이지만 알고리즘이 시간적으로 복잡해서

데이터 규모가 큰 경우에는 적용하기 힘들 것 같다고 생각했다

어떤 예측 모델을 사용할 지의 선택도 중요하지만

그 이전에 데이터의 변환과정에서 고려할 것들을 고려하며 모델을 선택하는 것부터 잘되어야한다고 느꼈다