Dimensionality Reduction, PCA, Manifold Learning

Unsupervised Learning

세 가지 일반 과업

• 군집화(clustering): 유사한 sample을 모아 같은 group으로 묶는 일
• 밀도 추정(Density Est.): Data로부터 확률분포를 추정하는 일
• 공간 변환(Transform.): 원래 특징 공간을 저차원 또는 고차원 공간으로 변환하는 일

공간 변환 예시

공간 변환을 통해 쉽게 군집을 나누는 경우

• 실제 데이터는 매우 고차원이기 때문에, 차원의 저주문제(차원이 증가할수록, 데이터가 듬성듬성 존재하게 되는 문제)를 해결하기 위해 공간 변환이 필요하다.

Dimensionality Reduction

The Curse of Dimensionality

차원의 저주

• 많은 ML 문제는 data의 차원의 수가 높을 때, 엄청나게 어려워진다. 이를 curse of dimensionality라고 한다.

  

  점점 사용하지 않는 공간이 늘어나게 된다. (데이터가 듬성듬성)

차원의 저주 해결방법

• 한 가지 방법은 training set의 size를 증가시켜 training instances가 충분한 밀집도에 도달하도록 하는 것이다.
  • 하지만 무작정 dataset을 늘리는 것은 어렵다.
• 또 다른 방법은 차원을 축소시키는 것이다.

Dim.Reduction의 Main Approaches

1) Projection

• 가정: training instances는 모든 차원에 균일하게 분산되지 않는다. (특정 영역에 몰려 있음)
• 모든 training instances는 고차원 공간의 훨씬 낮은 차원의 하위 공간 내에(혹은 가까이) 존재한다.
• 낮은 차원으로 data를 투영 $\rarr$ 특징을 쉽게 확인할 수 있다.

Projection의 한계

어떤 저차원에 어떻게 projection?

• Unrolling의 경우 projection하기 어렵다.
• 이러한 복잡한 dataset의 경우, projection의 수행이 오히려 좋지 않을 수 있다.

2) Manifold Learning

• d차원 manifold는 지역적으로 d차원 hyperplane과 닮은 n차원 공간의 일부이다.($d < n$, d차원에서 n차원으로 차원 축소를 하려는데, 거기에는 어떤 manifold라는 것이 있을 것이고, 이는 d차원의 hyperplane과 닮아있어서 경향을 추출할 수 있을 것이다.)
• Manifold assumption을 기반으로 하는데, 이는 현실의 매우 고차원의 datasets이 굉장이 낮은 차원의 manifold와 닮아 있을 수 있다는 가정이다. (쉽게 말해, 고차원에 뿌려진 데이터들을 잘 아우르는 sub space가 있을 것이라는 가정)

Unrolling을 수행하고 Projection하면 다음과 같이 저차원에서 Decision boundary를 쉽게 구할 수 있다.

Unrolling을 수행하고 Projection을 한다고 해서 항상 간단해지지 않을 수도 있다.
"어떤" manifold인지 가정이 중요하다.

Another Approach: PCA

Principal Component Analysis

1) data와 가장 근접한 hyperplane(projection이 가장 잘 맞는 저차원)을 식별한다.
2) 식별한 hyperplane에 data를 Project

올바른 hyperplane이란?
차원 축소를 잘하는 기준은 각 data의 특성을 잘 살릴 수 있는가이다.
즉, data들이 가장 많이 퍼질 수 있도록 하는 hyperplane이 적합(분산을 유지)

C1의 경우, data의 분산이 잘 이루어졌다.
따라서 data의 구분이 쉬워진다.
하지만 C2의 경우, data의 분산이 잘 이루어지지 않고 몰려있다.
따라서 여러 data간의 차별성이 감소하여 구분이 오히려 더 어려워진다.

PCA: Preserving the Variance

Variance(분산)값이 가장 큰(혹은 가장 잘 보존하는) hyperplane을 선택

• 가장 큰 variance 값을 가지는 axis을 식별: "C1"
• 위에서 식별한 axis와 직교하면서, 그 중 가장 큰 variance 값을 가지는 axis을 식별: "C2"
• 위 과정을 반복

PC

: $i^{th}$ axis는 data의 $i^{th}$ principal component(PC)라고 한다.
Example

• C1: the first PC
• C2: the second PC
  • C1과 orthogonal하고 V가 최대

PCA: 어떻게 PC를 찾는가

• Sample X와 관련된 공분산 행렬의 고유벡터 형태에 대해 분산을 최대화할 가중치 벡터 $w$를 찾는다.
  • Singular Value Decomposition으로도 해결 가능

PCA: 얼마나 많은 axis을 PCA로 할 것인가

PCA를 임의의 숫자로 한정하고 구하기보단,
원본 data의 variance를 충분히 크게 유지할 때(e.g., 원본의 95%정도)까지 PCA를 구한다.

original 차원이 400일 때, PCA를 구하면서 점점 차원을 축소시킨다.
이때, 150차원부터 variance가 급격하게 줄기 시작한다.
따라서, 150차원을 적당한 threshold로 잡는다.
(해당 그래프는 data마다 다르게 그려질 수 있다.)

• 차원 축소 시, 원본 data의 손실은 발생할 수 있다. (이로 인해 다시 원 차원으로 복구 시, 복구가 제대로 이뤄지지 않을 수 있다.)
• 차원 축소를 하게 되면, 마치 압축한 것처럼 보이기도 한다.(일부 noise 포함)
• 굉장히 큰 사진 파일에 대해서도 PCA를 사용해 차원을 축소시킬 수도 있다.

Nonlinear Dimensionality Reduction Techniques

Locally Linear Embedding(LLE)

nonlinear dimensionality reduction 기법 중 하나

• manifold learning(projection에만 의존하는 것 X)에 기반
• 서로 가까운, 이웃한 data들이 있다(group)는 가정 하에, 이러한 group끼리 모일 수 있도록 차원 축소를 시행

원리

(1)번 단계에서는 고차원의 data에서 특정 지점을 기준으로 이웃한 data group을 식별
(2)번 단계에서 선형 가중치를 기준으로 이러한 이웃들을 재구성
(3)번 단계에서는 이러한 선형 가중치를 최대한 보존하는 저차원으로의 projection을 수행

Example

지역적으로 비슷한 data끼리 모여있고, 일반적인 projection으로는 구분이 어려움굉장히 unrolling이 잘 수행된 것은 아니지만, 이웃한 data들은 잘 보존되어져 있다.

Others for NLDR

• Kernel PCA
  • PCA도 nolinear하게 사용, kernel trick을 사용
  • kernel SVM과 유사(nonlinear data에 대한 SVM 지원)
• t-Distributed Stochastic Neighbor Embedding (t-SNE)
  • visualization에 많이 사용

PCA in math form

선형 인자 model

• 선형 연산을 이용한 공간 변환 기법
• 선형 연산을 사용하므로 행렬 곱으로 인코딩(enc)과 디코딩(dec) 과정을 표현
  $f: z=W_{enc}x+\alpha_{enc}\\ g: x=W_{dec}z+\alpha_{dec}$
• $\alpha$는 데이터를 원점으로 이동하거나 잡음을 추가하는 등의 역할
• 인자 $z$와 추가 항 $\alpha$에 따라 여러 가지 model이 존재
  • $z$에 확률 개념이 없고 $\alpha$를 생략하면 PCA-관찰 벡터 $x$와 인자 $z$는 결정론적인 1:1 매핑 관계
  • $z$와 $\alpha$가 가우시안 분포를 따른다고 가정하면 확률 PCA$^{probabilistic PCA}$

PCA: 전처리

• 데이터를 원점 중심으로 옮기는 전처리를 먼저 수행

  

PCA: 변환식

• 주성분 분석이 사용하는 변환식
  • 일반적인 선형 변환식인 인코딩 식에서 $z$에 확률 개념이 없고 $\alpha$를 생략하면 주성분 분석
  • 변환 행렬 $W$는 $d*q$로서 주성분 분석은 $d$차원의 $x$를 $q$차원의 $z$로 변환($q<d$)
    • $w$의 j번째 열 벡터와의 내적 ${u_j}^Tx$는 $x$를 $u_j$가 가리키는 axis로 projection

$z=W^Tx\\ 이때\,w=(u_1\,u_2\,\cdots\,u_q)이고, u_j=(u_{1j},u_{2j},\cdots,u_{dj})^T$

• Example: 2차원을 1차원으로 변환하는 상황($d=2, q=1$)이때 $u$는 방향 벡터로 사용

PCA: 목적

• 손실을 최소화하면서 저차원으로 변환
  • 정보 손실 예
    • (a)는 $x_1,\,x_2$ 쌍이, $x_3,\,x_4$ 쌍이 같은 점으로 변환되는 정보 손실
    • (b)는 $x_1,\,x_3$ 쌍이 같은 점으로 변환되는 정보 손실
    • (c)는 4점이 모두 다른 점으로 변환되어 정보 손실이 가장 적다.
  • 주성분 분석은 변환된 훈련집합 $Z=\{z_1,z_2,\cdots,z_n\}$의 분산이 클수록 정보 손실이 적다고 판단

PCA: 최적화 문제

문제: $Z=\{z_1,z_2,\cdots,z_n\}$의 분산을 최대화하는 $q$개의 축(hyperplane), 즉 $u_ 1,u_2,\cdots,u_q$를 찾아라. 이 단위 벡터는 변환 행렬 $W$를 구성한다.

• $q$=1로 국한하고 분산을 쓰면,

  $\sigma^2=\frac{1}{n}\sum^n_{i=1}(z_i-\bar z)^2=\sum^n_{i=1}{z_i}^2=\sum^n_{i=1}(u^Tx_i)^2=u^T\sum u(\sum u는\,공분산행렬)$

  이러한 식의 결과인 $\sigma^2$를 최대화하는 $u$를 찾는 것이 PCA의 목표

• 주성분 분석의 학습 알고리즘 (선형에 적합)

1. 훈련집합으로 공분산 행렬 $\sum$을 계산한다.
2. $\sum u=\lambda u$ 를 풀어 $d$개의 고윳값과 고유 벡터를 구한다.
3. 고윳값이 큰 순서대로 $u_1,u_2,u_3,\cdots,u_d$를 나열한다.(이들을 주성분이라 부름)
4. $q$개의 주성분 $u_1,u_2,u_3,\cdots,u_d$를 선택하여 식에 있는 행렬 $W$에 채운다.

• 비선형 데이터에서 정보 손실다음과 같이 비선형 데이터에 대한 선형 PCA의 한계가 존재한다.

PCA: 최적화 문제 $\rarr$ Kernel PCA

비선형 데이터에서의 정보 손실을 막기 위한 해결책

• $u_1,u_2,u_3,\cdots,u_d$를 구한 다음, $u_i$를 axis로 간주하여 투영
• kernel trick을 적용한 kernel PCA 개념kernel PCA의 비선형 데이터 처리 능력

Kernel PCA: 메모리 기반

• 새로운 sample $x$가 들어오면,
  • 이미 $a_1,\cdots,a_l$는 계산했다고 가정
  • $x_1,\cdots,x_n$ 역시 주어진 상황
    $a_k=\sum^n_{j=1}a_{kj}K(x_j,x),\,k=1,2,\cdots,l$
    $x$를 미리 알 수 없으므로, 위의 식의 $K()$(커널 함숟)을 구하려면
    기존 훈련집합($x_1,\cdots,x_n$)을 모두 저장하고 있어야 함
  • $\rarr$ Kernel PCA는 메모리 기반 방법, 훈련집합 $X$의 크기가 클 경우, 메모리 부담이 증대

PCA: code

차원 축소된 데이터 분류하기

• 2차원 wine set 분류하기 (By Logistic Regression)

  

PCA로 영상 압축

• MNIST(손글씨) dataset(28*28=784-dimension) to 154-D using PCA

  

  • Load MNIST data
  • Split train/test sets
  • How to use PCA: variance 보존 %, 또는 차원 수 명시
  • PCA to compress image
    • Compressed (reduced) image
    • Decompressed (recovered) image

Tuning Hyperparameters

GridSearchCV

• kPCA(Kernel PCA)를 위한 최적의 kernel과 gamma 값을 찾는 것

  • 최고의 분류 정확도를 얻기 위해 사용

• Example: Two-step pipeline

  

  • kPCA를 이용해서 2-D로 차원을 축소
  • 분류를 위해 Logistic Regression 사용 (LR로 분류의 정확도를 높임)