차원의 저주가 무엇이고 어떻게 해결할 수 있는가?는 인터뷰에서 종종 묻는 질문이다. 난이도가 높지 않음에도 만족스러운 답변을 들은 적은 없다. 책은 용어/개념만 소개하고 서베이 논문은 여러 알고리즘을 분류하기만 할 뿐 개념과 함의를 종합적으로 정리하지 않은 듯하다. 그래서 이 글은 다양한 관점에서 개념적으로 이해하는 데 도움을 주고자 한다. 참고자료를 찾아보지 않고 그냥 기억에 의존해서 쭉 적어나가기 때문에 일부 방법론의 구체적인 내용은 사실과 다를 수 있으니 자세한 것은 직접 찾아보기 바란다.
차원의 저주?
예외적인 경우룰 제외하면 데이터의 피쳐(와 양)가 많을수록 더 정확한 모델을 구축할 수 있다. 기존 모델이 불만족스러울 때 가장 먼저 새로운 피쳐를 발굴해서 추가하는 작업을 하는 것도 가장 쉽고 효과도 즉각적이기 때문이다. 하지만 무턱대고 피쳐를 무한히 추가할 수는 없는 노릇이다. 어느 수준을 넘어서면 새로운 피쳐가 모델의 강건성뿐만 아니라 시스템 전체의 안정성에 부정적인 영향을 준다. 흔히 차원의 저주 Curse of Dimensionality라 부르는 현상이 발생한다. 차원의 저주의 가장 직접적인 영향은 피쳐의 개수/차원이 늘어날수록 필요한 계산량과 메모리 사용량은 그보다 더 빠르게 증가한다. 즉, 계산 불가 상태에 빠진다. 그리고 불필요한 (Colinear, redundant, noisy) 데이터가 추가되거나 Sparsity가 증가해서 모델의 정확도가 오히려 떨어지기도 한다. 많은 강력한 알고리즘이 있지만 데이터 과학은 여전히 데이터를 직접 눈으로 검수하면서 얻은 직관, 인사이트에 기반하는데 차원이 크면 그런 EDA 작업이 사실상 불가능하다. 고차원과 저차원의 데이터 간의 메커니즘 (또는 인사이트) 자체가 다른 경우도 흔하다. (** 요즘 데이터 차원이 증가하는 현상은 너무 자명해서 따로 설명하지 않았음)
차원 축소
차원의 저주가 데이터의 차원 증가에 따른 결과이므로 당연히 차원을 제한하거나 줄이면 바로 해결된다. 이를 차원 축소 Dimension(ality) Reduction이라 부른다. 구체적인 방법론을 나열/설명하기 전에 데이터 차원이 높아질수록 모델의 정확도가 증가하는데 차원의 축소하면 모델 정확도를 포기해야하지 않느냐? 고 물을 수 있다. 옳은 지적이다. 그래서 모델의 정확도를 적정선에서 유지하면서 데이터 차원 (또는 그에 따른 계산량)을 확 줄여서 차원 축소는 기술이 아니라 예술인 거다. 차원을 축소하면 당연히 계산량과 메모리 사용량이 준다. 차원 축소로 모델의 정확도가 다소 하락하는 것이 일반적이나 오히려 정확도와 강건성이 개선되기도 한다. 중복되거나 노이즈, 또는 아웃라이어 등이 제거돼서 모데의 안정성이 증가하고 저 차원의 모델이 일반화에 유리한 면도 있다. 그리고 무엇보다도 낮은 차원의 데이터는 테이블로 쭉 나열해보거나 그래프 등으로 시각화 (visualization)해서 눈으로 직접 확인해볼 수 있다. 실제 모델은 수백 개의 피쳐로 구성된 매우 복잡하더라도, 소수의 중요한 피쳐는 직접 눈으로 확인해서 검증하고 또 그걸 시각화해서 비전문가들과 공유/설명하는 것도 필요하다. 비슷한 측면에서 소수의 요소 (피쳐)로 만들어진 모델이 더 이해하고 해석하기에 용이하다. (차원 축소 자체가 이해의 범위를 벗어날 수도 있지만ㅠㅠ) 우려되는 점은 계속 언급했듯이 정보 손실로 인한 모델 정확도가 하락될 수 있고, 중요 피쳐로만 설명되지 않는 특수한 케이스를 놓칠 수 있다.
그래서 어떻게?
차원 축소에 특별한 알고리즘이 특정되는 걸로 생각할 수 있는데, 현존하는 모든 (대부분의?) 기계학습 알고리즘들을 차원축소에 활용할 수 있다. 인터뷰에서 차원 축소 방법론을 제시하라고 물어보면 겨우 PCA정도만 겨우 대답하는 경우가 많다. 이는 차원 축소에 관해서 평소에 깊고 넓게 생각해보지 않고 책이나 논문에 소개된 개념을 피상적으로만 배워서 기억하고 있기 때문이다. PCA가 가장 잘 알려진 방법은 맞미나 PCA가 차원 축소를 모두 커버할 수는 없다. 당장 머리에 떠오르는 클러스터링, 분류, 회귀 등의 모든 알고리즘/모델을 차원 축소에 사용할 수 있다. 아래의 관점으로 생각해보면 차원 축소 알고리즘을 어떻게 해석하고 설계할 수 있는지 그리고 기존 기계학습 알고리즘이 어떻게 차원 축소에 활용될 수 있는지 감을 잡을 수 있다.
1. N차원의 데이터를 M차원의 데이터로 변환하는 함수 (M << N)
2. N개의 축으로 설명되는 데이터를 M개의 축으로 프로젝션
3. M개의 영역으로의 파티션/할당 또는 M개의 중심점 (centroid)과의 거리
차원축소 알고리즘은 어떤 특성을 가져야 하는가? 개인적으로 ‘일관성’ 또는 ‘연속성’이 가장 중요하다고 본다. 차원 축소는 그것만으로 목적 (최종 결과물)이 아니라 과정 (중간 결과물)이다. 즉, 축소된 차원의 데이터를 가지고 시스템을 분석한다거나 예측모델을 만들어야 한다. 그래서 지금 A 데이터를 축소해서 a를 만들었다면 다른 시점에 다시 A를 축소하면 a가 그대로 또는 a와 매우 유사한 a’로 재현돼야 한다. 모델을 만들 때의 표현과 추론할 때의 표현이 달라지면 아무리 좋은 모델도 의미가 없다. 아래에 소개할 임의성에 기반한 알고리즘들 (예, Random Projection, Min-hash)은 언뜻 보기에는 작동하지 않을 것 같지만 일관성이 유지된다는 점에서 수긍이 간다. 데이터 표현이 일관된다면 다음으로 효과성이 중요하다. 데이터의 차원은 축소되지만 원래 데이터의 성질이 바뀌면 차원 축소를 한 의미가 없어진다. 오리지널 모델의 결과와 축소된 모델의 결과가 거의 같도록 데이터가 축소돼야 한다. 다음으론 효율성이 중요하다. 트레이드-오프가 있지만 최소의 데이터로 최대의 효과를 얻어야 한다. 100만 차원의 데이터를 겨우 1만 차원 줄여서 99만 차원으로 표현한다면 굳이 차원 축소를 할 필요가 없다. 원래 데이터의 10% (또는 1%) 미만으로 오리지널 모델의 8~90% 성능을 내야 한다.
대표적인 알고리즘을 간단히 소개/나열만 한다.
- Feature Selection: 데이터를 완전히 다른 형태로 변환 (Transformation)하는 것보다 중요하고 의미있는 소수의 피쳐 subset으로 줄이는 것이 가장 직관적이다. 피쳐 셀렉션은 차후에 더 긴 설명이 필요하겠지만 모델 적합도에 기반한 방식과 결과 (Y) 기여도에 기반한 방식이 있다.
- Random Projection: 다소 반직관적이지만 가장 심플한 방식이다. 원래 데이터가 KxN 행렬이라면 여기에 임의의 NxM 행렬을 곱해서 KxM 행렬로 바꾼다. N차원이 마법처럼 M차원이 되다. 여기서 중요한 점은 NxM 행렬이 특별한 규칙에 의해서 만들어진 것이 아니라 말 그대로 랜덤으로 만들어도 된다는 점이다. NxM 행렬을 한번 고정하면 어떠한 N차원의 데이터가 들어오더라도 ‘일관되게’ M차원의 데이터로 변환된다. 물론 '효과성’은 다소 희생될 수 있지만 의외로 잘 작동한다. ‘임의’라고 표현했지만 실제 애플리케이션에서는 특정한 확률로 -1, 0, 1으로 된 NxM 행렬을 만든다. (대용량/고차원 데이터에서) Very Sparse Random Projection에서는 1과 -1의 비율이 매우 낮아도 최종 결과에는 큰 차이가 없다고 한다.
- PCA (Principal Component Analysis): PCA는 워낙 유명해서 굳이 긴 설명은 필요없을 듯하다. 어떤 데이터의 특성을 가장 잘 표현하는 방법은 가장 많이 흩어진 (분산이 가장 큰) 축으로 설명된다.
- Categorization & Classification: 어떤 데이터를 M개의 카테고리나 class로 분류할 수 있다면 이는 자연스레 M차원의 one-hot 인코딩이 된다. 즉, 분류된 클래스(들)만 1이고 나머지는 0으로 된 M차원의 바이너리 벡터가 된다.
- Clustering: 비슷하게 M개의 클러스터 중에서 어느 클러스터에 속하는가 (바이너리) 또는 M개의 클러스터와의 유사도/거리 (실수)를 벡터로 표현하면 바로 M차원의 축소된 벡터가 만들어진다. 예를 들어, k-means 클러스터링을 통해서 몇 번째 클러스터에 속하는가로 바이너리 벡터를 만들거나 각 클러스터의 centroid와의 거리를 계산해서 실수형 벡터를 만들 수 있다.
- (랜덤) 파티션: Min-hash처럼 랜덤 파티션으로도 효과적인 방법이다. 랜덤 프로젝션과 거의 같다고 볼 수도 있는데, M개의 (랜덤) 하이퍼-플레인을 기준으로 데이터가 위/아래에 있는지를 표시하면 자연스레 M차원의 바이너리 벡터가 만들어진다. 다른 해싱 트릭이나 블럼필터도 같은 선에서 볼 수 있다.
- SVD를 비롯한 각종 Matrix Factorization의 latent vector가 축소된 차원 벡터가 되고, LDA (Latent Dirichlet Allocation)을 비롯한 토픽모델링에서도 토픽 벡터가 축소된 차원 벡터가 된다. 딥러닝 (또는 ANN)에서 중간의 모든 히든 레이어는 축소된 (또는 확장된) 벡터가 된다.
** 차원 축소와 함께 데이터의 사이즈 (샘플 수)를 줄이는 방법도 있다. (이정도만ㅎㅎ)
** 많이 나이브하지만 차원 축소의 이론적 배경은 Johnson-Lindenstrauss Lemma를 참조하기 바람.
