on
Proof of PCA
Why eigenvectors of a covariance matrix become principal component axes
본 포스트에는 수식이 포함되어 있습니다. 분수 등의 수식이 정상적으로 보이지 않는 경우에는 수식을 마우스 오른쪽 버튼으로 클릭한 후 “Math Renderer”를 SVG로 바꿔주세요. (➔How-To)
$n$개의 특성(feature)을 가지는 확률변수 $X$에 대한 $m$개의 표본(sample) $\mathbf{p}_i$가 주어졌다고 가정해보겠습니다.
중심점 이동(centering), 스케일링(scaling) 등의 전처리 과정(pre-processing)을 거친 데이터는 다음과 같은 $m \times n$ 행렬 $\mathbf{D}$로 나타낼 수 있습니다.
여기서 $\mathbf{p}_i$와 $\mathbf{f}_j$는 각각 행렬 $\mathbf{D}$의 $i$번째 행과 $j$번째 열을 의미합니다. 즉, $\mathbf{p}_i$는 $i$번째 표본(sample)이고, $\mathbf{f}_j$는 $j$번째 특성(feature)을 나타냅니다. 따라서 $m$은 표본의 개수이고, $n$은 특성의 개수를 의미합니다.
이때 $a$번째 특성과 $b$번째 특성의 상관관계(correlation)는 어떻게 정량화할 수 있을까요? $a$번째 특성을 나타내는 벡터는 $\mathbf{f}_a$이고, $b$번째 특성을 나타내는 벡터는 $\mathbf{f}_b$이기 때문에 이 두 벡터를 내적하면 두 가지 특성 사이의 상관관계를 정량화하여 나타낼 수 있습니다. 왜냐하면 내적은 두 벡터의 방향이 일치하여 두 벡터가 이루는 각이 0일 때 최대값을 반환하고, 두 벡터가 수직하여 상관관계가 전혀 없을 때는 0을 반환하는 연산이기 때문입니다. 다만 표본의 개수에 따라서 결과의 범위가 너무 많이 달라지는 것을 피하기 위해서 두 벡터의 내적을 $m$으로 나누어서 정규화시킨 값을 두 특성 사이의 상관관계 계측값으로 사용합니다.
$c_{ab} = \frac{1}{m} \left( \mathbf{f}_a^\text{T} \mathbf{f}_b \right)$
이러한 상관관계 계측값 $c_{ab}$를 $(a,b)$ 성분으로 가지는 $m \times n$ 행렬을 확률변수 $\mathbf{X}$의 공분산 행렬(covariance matrix)이라고 합니다.
즉, 공분산 행렬 $\mathbf{C}(\mathbf{X})$의 $(a,b)$ 성분은 특성변수 $\mathbf{f}_a$와 $\mathbf{f}_b$ 사이의 상관관계 정보를 알려줍니다. 그리고 이러한 공분산 행렬은 다음과 같은 성질을 가집니다.
확률변수 $\mathbf{X}$의 공분산 행렬이 $\mathbf{C}$일 때
- 확률변수 $\mathbf{X}$의 $\mathbf{u}$ 방향으로의 분산은 $\mathbf{u}^\text{T} \mathbf{C} \mathbf{u}$ 입니다. (단, $\mathbf{u}^\text{T} \mathbf{u} = 1$)
- 공분산 행렬 $\mathbf{C}$의 $i$번째 고유값인 $\lambda_i$는 $i$번째 고유벡터인 $\mathbf{v}_i$ 방향으로의 분산을 의미합니다.
- 주축(principal axis)이란 어떤 대상이나 시스템의 핵심적인 성질을 나타내는 기하학적인 축을 말합니다. 서로 직교하는 고유벡터들은 확률변수 $\mathbf{X}$의 특징을 잘 표현하는 주축으로 사용할 수 있습니다. 공분산 행렬 $\mathbf{C}$의 고유값들의 크기가 $\lambda_1 > \lambda_2 > \lambda_3 > \cdots$ 이라면 각 축의 중요도는 $\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3, \cdots$ 순서로 설정됩니다.
위의 세 가지 사실을 차례대로 증명해보겠습니다.
위치벡터 $\mathbf{p}_{i}$를 단위벡터 $\mathbf{u}$에 투영한 결과를 $\mathbf{q}_i$라 하고, 원점으로부터 이 벡터의 끝점까지의 부호거리(signed distance)를 $q_i$라 하면 $\mathbf{u}$ 방향으로의 분산은 다음과 같이 계산할 수 있습니다.
$\frac{1}{m} \sum_{i=1}^{m} {q_i}^{2}$
$= \frac{1}{m} \sum_{i=1}^{m} \left( \mathbf{p}_{i}^\text{T} \mathbf{u} \right)^2$
$= \frac{1}{m} \sum_{i=1}^{m} (\mathbf{p}_i^\text{T} \mathbf{u})^\text{T} (\mathbf{p}_i^\text{T} \mathbf{u})$
$= \frac{1}{m} \sum_{i=1}^{m} (\mathbf{u}^\text{T} \mathbf{p}_i) (\mathbf{p}_i^\text{T} \mathbf{u})$
$= \mathbf{u}^\text{T} \left( \frac{1}{m} \sum_{i=1}^{m} \mathbf{p}_i \mathbf{p}_i^\text{T} \right) \mathbf{u}$
$= \mathbf{u}^\text{T} \mathbf{C} \mathbf{u}$
따라서 벡터 $\mathbf{u}$ 방향으로 분산은 $\mathbf{u}^\text{T} \mathbf{C} \mathbf{u}$라는 것을 알 수 있습니다.
이러한 사실은 또 다른 방식으로도 증명이 가능합니다. 확률변수 $\mathbf{X}$를 선형변환한 새로운 확률변수 $\mathbf{AX}$의 공분산 행렬은 다음과 같이 계산할 수 있습니다. (여기서는 이에 대한 증명은 생략하겠습니다.)
$Cov(\mathbf{A} \mathbf{X}) = \mathbf{A} Cov(\mathbf{X}) \mathbf{A}^\text{T}$
여기에 $\mathbf{A} = \mathbf{u}^\text{T}$를 대입하고, 스칼라 확률변수인 경우에 (분산)=(공분산 행렬)인 사실을 이용하면 다음과 같이 벡터 $\mathbf{u}$ 방향으로 분산식을 간단하게 유도할 수 있습니다.
$Var_{\mathbf{u}}(\mathbf{X}) = Var(\mathbf{u}^\text{T} \mathbf{X}) = Cov(\mathbf{u}^\text{T} \mathbf{X}) = \mathbf{u}^\text{T} Cov(\mathbf{X}) \mathbf{u}$
공분산 행렬 $\mathbf{C}$의 $i$번째 고유값과 고유벡터를 각각 $\lambda_i$와 $\mathbf{v}_i$라 하면 다음과 같은 관계식이 성립합니다.
$\mathbf{C} \mathbf{v}_{i} = {\lambda}_{i} \mathbf{v}_{i}$
그리고 $m$차원 공간상에서 임의의 방향을 나타내는 단위벡터 $\mathbf{u}$는 다음과 같이 $m$개 고유벡터들의 선형조합으로 표현할 수 있습니다.
$\mathbf{u} = u_1 \mathbf{v}_1 + u_2 \mathbf{v}_2 + \cdots + u_m \mathbf{v}_m$
이때 $\mathbf{u}$ 방향의 분산 $\mathbf{u}^\text{T} \mathbf{C} \mathbf{u}$는 다음과 같습니다.
$\mathbf{u}^\text{T} \mathbf{C} \mathbf{u}$
$= \mathbf{u}^\text{T} \mathbf{C} (u_1 \mathbf{v}_1 + u_2 \mathbf{v}_2 + \cdots + u_m \mathbf{v}_m)$
$= \mathbf{u}^\text{T} (u_1 \mathbf{C} \mathbf{v}_1 + u_2 \mathbf{C} \mathbf{v}_2 + \cdots + u_m \mathbf{C} \mathbf{v}_m)$
$= \mathbf{u}^\text{T} (u_1 \lambda_1 \mathbf{v}_1 + u_2 \lambda_2 \mathbf{v}_2 + \cdots + u_m \lambda_m \mathbf{v}_m)$
$= (u_1, u_2, \cdots, u_m) \cdot (u_1 \lambda_1, u_2 \lambda_2, \cdots, u_m \lambda_m)$
$= u_1^2 \lambda_1 + u_2^2 \lambda_2 + \cdots + u_m^2 \lambda_m$
만약 $\mathbf{u}$가 $i$번째 고유벡터 방향과 일치한다면 $\mathbf{u}=\mathbf{v}_i$ 이고, 이때 벡터 $\mathbf{u}$는 $i$번째 성분을 제외한 모든 성분들의 값이 0이므로 $\mathbf{u}^\text{T} \mathbf{C} \mathbf{u}$는 다음과 같이 정리할 수 있습니다.
$\mathbf{u}^\text{T} \mathbf{C} \mathbf{u} = \mathbf{v}_i^\text{T} \mathbf{C} \mathbf{v}_i = \lambda_i$
따라서 확률변수 $\mathbf{X}$의 $\mathbf{v}_i$ 방향으로의 분산값은 $\lambda_i$와 같다는 것을 알 수 있습니다.
가장 큰 분산을 가지는 방향을 구하는 문제는 다음과 같이 기술할 수 있습니다.
$\max_{\mathbf{u}} \mathbf{u}^\text{T} \mathbf{C} \mathbf{u}$ s.t. $\mathbf{u}^\text{T} \mathbf{u} = 1$
이러한 최적화 문제는 라그랑주 승수법(Lagrange multiplier)을 이용하면 다음과 같이 기술할 수 있습니다.
$\mathcal{L}=\mathbf{u}^\text{T} \mathbf{C} \mathbf{u} - \lambda (\mathbf{u}^\text{T} \mathbf{u} - 1)$
$\frac{ \partial \mathcal{L} } { \partial \mathbf{u} } = 2 \mathbf{C} \mathbf{u} - 2 \lambda \mathbf{u} = 0$
$\therefore \mathbf{C} \mathbf{u} = \lambda \mathbf{u}$
이것은 공분산 행렬 $\mathbf{C}$의 고유벡터 방향마다 변곡점(inflection point) 또는 안장점(saddle point)이 존재한다는 것을 의미합니다. 즉, 공분산 행렬 $\mathbf{C}$의 고유벡터 방향마다 분산의 국부적인 최대값 또는 최소값이 존재한다는 것을 알 수 있습니다.
그런데 앞에서 증명한 바와 같이 고유벡터 $\mathbf{v}_i$방향으로의 분산값은 $\lambda_i$와 같으므로 가장 큰 고유값을 가지는 고유벡터는 가장 큰 분산의 방향을 나타내는 것을 알 수 있습니다. 즉, 분산의 전역 최대값(global maximum) 방향은 첫 번째 고유벡터의 방향과 일치합니다.
마찬가지 이유로 나머지 고유벡터들 또한 분산의 국부 최대값(local maximum)을 가지고 이들은 서로 수직이기 때문에 공분산 행렬 $\mathbf{C}$의 고유벡터들은 확률변수 $\mathbf{X}$의 특징을 잘 표현하는 주축으로 사용할 수 있습니다.