STUDY_SEONMIN
DAY17 - K차원 근사 본문
데이터 분석에서 변수의 개수가 많은 경우 다중공선성 문제가 발생할 가능성이 커지고, 또한 수많은 변수로 만든 예측 모델은 상대적으로 적은 변수로 만든 모델보다 오버피팅될 가능성이 높다.
따라서 고차원 데이터를 저차원으로 근사시킴으로써 그러한 문제를 완화시킬 수 있다.
K차원 근사
- N개의 M차원 벡터 $a_1,\ a_2,\ a_3,\ \dots,\ a_N,\quad (a_i \in R^{M})$
- K개의 정규직교벡터 $w_1,\ w_2,\ w_3,\ \dots,\ w_K,\quad (w_k \in R^{M})$
- K개의 정규직교벡터들을 기저벡터로 갖는 벡터 공간 : $ \mathbf{W} $
N개의 벡터들을 벡터 공간 W로 근사시킬 때는, 최대한 원래의 벡터와 비슷하게 만들어야 한다.
임의의 벡터를 벡터 공간에 투영시키면 원래 벡터와 투영 벡터사이의 거리는 $||a_i^{\perp W}||$ 가 된다.
따라서 K차원 근사 문제는 다음과 같이 나타낼 수 있다.
$$ \arg\underset{W}\min\ \sum_{i=1}^N ||a_i^{\perp W}||^2 $$
또한 $a_i^{\perp W} = a_i - a_i^{||W}$ 이므로
$$ \arg\underset{W}\min\ \sum_{i=1}^N ||a_i^{\perp W}||^2 = \arg\underset{W}\min\ \sum_{i=1}^N (||a_i||^2 - ||a_i^{||W}||^2) $$
위 식에서 Norm을 분리시켜줄 수 있는 이유는 $a_i^{||W}$와 $a_i^{\perp W}$가 서로 직교하기 때문입니다.
$A = \begin{bmatrix} a_1^T \\ a_2^T \\ \vdots \\ a_M^T \end{bmatrix}$라고 할 때 "행렬 놈의 제곱 = 행벡터 놈의 제곱합 = 열벡터 놈의 제곱합" 이므로
$$ \arg\underset{W}\min\ \sum_{i=1}^N (||a_i||^2 - ||a_i^{||W}||^2) = \arg\underset{W}\min\ (||A||^2 - \sum_{i=1}^N ||a_i^{||W}||^2) $$
여기서 행렬$A$는 이미 주어진 벡터로 이루어진 행렬이므로 값이 고정되게 됩니다.
결국 K차원 근사문제는 이렇게 바뀌게 됩니다.
$$ \arg\underset{W}\max\ \sum_{i=1}^N ||a_i^{||W}||^2 $$
벡터 공간 $W$는 K개의 정규직교벡터 $w_1,\ w_2,\ \dots,\ w_K$로 이루어져있습니다.
주어진 $a_i$벡터를 정규직교벡터로 이루어진 공간에 투영할 시 기저벡터들의 선형조합으로 나타내집니다.
$$ a_i^{||W} = (a_i^Tw_1)w_1 + (a_i^Tw_2)w_2 + \dots + (a_i^Tw_k)w_k = \sum_{k=1}^K (a_i^Tw_k)w_k$$
$$ \arg\underset{W}\max\ \sum_{i=1}^N ||a_i^{||W}||^2 = \arg\underset{W}\max\ \sum_{i=1}^N ||\sum_{k=1}^K (a_i^Tw_k)w_k||^2 $$
$a_i^Tw_k$는 $scalar$이므로 $||\sum_{k=1}^K(a_i^Tw_k)w_k||^2$는 직교하는 K개의 벡터 $w_1,\ w_2,\ \dots,\ w_K$들의 길이를 조절하고 더한 후 Norm의 제곱을 계산한 것입니다.
이때 "직교벡터합의 Norm 제곱 = 직교벡터 Norm들의 제곱합"이 되므로
$$ \arg\underset{W}\max\ \sum_{i=1}^N ||\sum_{k=1}^K (a_i^Tw_k)w_k||^2 = \arg\underset{W}\max\ \sum_{i=1}^N \sum_{k=1}^K ||(a_i^Tw_k)w_k||^2 $$
$||cv||^2 = ||c||^2||v||^2$ 이고, $||w_k||^2 = 1,\ (w_k는 정규직교벡터)$이 되므로
$$ \arg\underset{W}\max\ \sum_{i=1}^N \sum_{k=1}^K ||(a_i^Tw_k)w_k||^2 = \arg\underset{W}\max\ \sum_{i=1}^N \sum_{k=1}^K ||a_i^Tw_k||^2 \\ = \arg\underset{W}\max\sum_{i=1}^N \sum_{k=1}^K w_k^Ta_ia_i^Tw_k$$
$A = \begin{bmatrix} a_1^T \\ a_2^T \\ \vdots \\ a_N^T \end{bmatrix} $ 라고 하면
$$ A^TA = a_1a_1^T + a_2a_2^T + \dots + a_Na_N^T = \sum_{i=1}^N a_ia_i^T $$
$$ \arg\underset{W}\max\sum_{i=1}^N \sum_{k=1}^K w_k^Ta_ia_i^Tw_k = \arg\underset{W}\max\sum_{k=1}^K w_k^TA^TAw_k $$
$A^TA$는 분산행렬이고 $M$차원 정방행렬이므로
$$ A^TA = V\Lambda V^T = \sigma_1^2v_1v_1^T + \dots + \sigma_M^2v_Mv_M^T \\ = \sum_{i=1}^M \sigma_i^2v_iv_i^T $$
$$ \arg\underset{W}\max\sum_{k=1}^K w_k^TA^TAw_k = \arg\underset{W}\max\sum_{k=1}^K w_k^T\sum_{i=1}^M (\sigma_i^2v_iv_i^T) w_k \\ = \arg\underset{W}\max\sum_{k=1}^K \sum_{i=1}^M \sigma_i^2(w_k^Tv_iv_i^Tw_k) = \arg\underset{W}\max\sum_{k=1}^K\sum_{i=1}^M\sigma_i^2||v_i^Tw_k||^2$$
분산행렬의 고유벡터들은 모두 직교하므로, 모든 M차원 벡터는 $v_1,\ v_2,\ \dots,\ v_M$들의 선형조합으로 나타낼 수 있다.
$$ w_k = c_{k,1}v_1 + c_{k,2}v_2 + \dots + c_{k,M}v_M $$
$$ ||w_k||^2 = c_{k,1}^2 + c_{k,2}^2 + \dots + c_{k,M}^2 = 1 $$
$$ ||v_i^Tw_k||^2 = || c_{k,1}v_i^Tv_1 + c_{k,2}v_i^Tv_2 + \dots + c_{k,M}v_i^Tv_M ||^2 = c_{k,i}^2 $$
$$ \sum_{k=1}^K\sum_{i=1}^M\sigma_i^2||v_i^Tw_k||^2 = \sum_{k=1}^K\sum_{i=1}^M\sigma_i^2c_{k,i}^2 \\ = (c_{1,1}^2 + c_{2,1}^2 + \dots + c_{K,1}^2)\sigma_1^2 + (c_{1,2}^2 + \dots + c_{K,2}^2)\sigma_2^2 + \dots + (c_{1,M}^2 + \dots + c_{K,M}^2)\sigma_M^2$$
특이값은 주어진 $a_i$ 벡터들로 만들어 낸 행렬에 의해 이미 정해져 있는 값이기 때문에 결국 그 앞에 붙어 있는 계수를 최대로 만들면 전체값이 최대가 될 수 있습니다.
또한 특이값은 정렬된 형태로 있기 때문에 가장 큰 특이값인 $\sigma_1$의 계수를 최대한 크게 만드는 것이 좋습니다.
$$ c_{k,1}^2 + c_{k,2}^2 + \dots + c_{k,M}^2 = 1 $$ 와 같은 조건 하에서 $\sigma_1$의 계수를 최대로 만들기 위해서는 $c_{1,1} = c_{2,1} = \dots = c_{K,1} = 1$이 되어야 합니다.
하지만 그렇게 될 경우 $w_1 = w_2 = w_3 = \dots = w_K = v_1$이 되기 때문에 K개의 정규직교벡터라는 최초의 전제조건에 어긋나게 됩니다.
따라서 $c_{1,1} = 1$이라고 하여 $w_1 = v_1$을 만들었다면 나머지 $w_k$벡터들이 이와 직교하기 위해서는 $ c_{k,1} = 0$이 되어야합니다.
동일한 방식으로 $\sigma_2, \sigma_3, \dots, \sigma_M$까지의 계수들을 계산하게 되면 결국 우리가 구하고자 했던 벡터공간 $\mathbf{W}$는 행렬 $A$의 오른쪽 특이벡터 K개로 이루어진 공간이라는 것을 알 수 있습니다.
$$ w_1 = v_1,\ w_2 = v_2,\ w_3=v_3,\ \dots,\ w_K = v_K $$
'EDUCATION > DSS Online 6기' 카테고리의 다른 글
DAY18 - 다양한 함수 (0) | 2021.02.06 |
---|---|
DAY17 - PCA (0) | 2021.02.06 |
DAY16 - 특이값 분해 (0) | 2021.02.03 |
DAY16 - 분산행렬의 고유분해 (0) | 2021.02.03 |
DAY16 - 대칭행렬의 고유분해 (0) | 2021.02.03 |