10. 레일리 몫과 일반화된 고유값

 

행렬 $A$ 의 특이값을 구하기위해 $\frac{||Ax||^2}{||x||} = \frac{x^TSx}{x}$ 를 최대화 했었다.

$R(x) = \frac{x^TSx}{x}$ 를 레일리 몫 Rayleigh quotient 라고한다.

 

$R(x)$ 의 최대값은 행렬 $S$ 의 가장 큰 고유값 $\lambda_1$ 과 같다.

$R(x)$ 의 최소값은 행렬 $S$ 의 가장 작은 고유값 $\lambda_n$ 과 같다.

두 고유값 사이에 있는 고유값에 해당하는 고유벡터들은 모두 $R(x)$ 의 안장점 이다.

 

안장점들은 1계도함수의 값이 0 이지만, 최대나 최소가 되지 않는 점이다.

안장점은 $x = q_k$ 에 모든 $i$ 에 대해서 $\frac{\partial R}{\partial x_i} = 0$ 을 만족할때, $R(q_k) = \frac{q_k^T\lambda_k q_k}{q_k^T q_k} = \lambda_k$ 이다.

 

이 점들은 행렬 $A$ 의 특이값 분해와도 연결된다. 앞서 봐왔듯이, $S = A^TA$ 이고, 양의 정부호(혹은 준정부호) 행렬인 $S$ 의 레일리 몫은 행렬 $A$ 의 Norm 을 이 끌어내고, $S$ 의 가장큰 고유값이 $A$ 의 가장 큰 특이값의 제곱이 된다.

$||A||^2 = \max \frac{||Ax||^2}{||x||} = \max \frac{x^TA^TAx}{x^Tx} = \max \frac{x^TSx}{x^Tx} = \lambda_1(S) = \sigma_1^2 (A)$

 

이렇게 대칭 행렬의 고유값 문제는 $R(x)$ 를 최대화하는 문제가 된다.

 

---

일반화된 고유값과 고유벡터

 

통계 데이터분야에 응용하려면 이차 대칭행렬 $M$ 을 $R(x)$ 를 분모에 넣는다.

 

일반화된 레일리 몫 : $R(x) = \frac{x^TSx}{x^TMx}$

 

역학에서 행렬 $M$ 은 질량행렬 mass matrix  이고, 통계학에서는 공분산 행렬 이다.

일반화된 레일리 몫 $R(x) = \frac{x^TSx}{x^TMx}$ 일때, 고유값 $Sx = \lambda x$ 는 $Sx = \lambda Mx$ 로 바뀐다.

행렬 $M$ 이 양의 정부호 행렬일때, $R(x)$ 의 최대값은 $M^{-1}S$ 의 고유값중 가장 큰 값이다.

일반화된 레일리 몫 문제 $Sx = \lambda Mx$, $H=M^{-1}S$ 인 $Hy = \lambda y$ 라는 $H$ 의 고유값문제로 바꿀수 있을텐데, 문제는 $H$ 가 대칭행렬이 아닐수도 있다는 점이다.

그래서 $H$ 를 $M$ 의 제곱근 행렬을 이용해서 $H = M^{-\frac{1}{2}}SM^{-\frac{1}{2}}$ 로 제시한다.

 

• 두 행렬 $M^{-1}S$, $M^{-\frac{1}{2}}SM^{-\frac{1}{2}}$ 은 같은 고유값을 가진다.
• $M^{-\frac{1}{2}}SM^{-\frac{1}{2}}$ 는 대칭성을 가진다.
• 양의 정부호 $M$ 은 양의 정부호인 제곱근 행렬을 가진다.

대각행렬의 제곱근행렬은 같은 고유값을 갖는다?

$ M = Q\Lambda Q^T $ 에 $\Lambda \geq 0 $ 이면, $M^{\frac{1}{2}}  = Q\Lambda^{\frac{1}{2}} Q^T$ 는 $\Lambda^{\frac{1}{2}} \geq 0 $ 를 만족한다.

 

일반화된 레일리 몫을 $x = M^{-\frac{1}{2}}y$ 으로 표현해 $ \frac{x^TSx}{x^TMx} = \frac{y^T(M^{-\frac{1}{2}})^TSM^{-\frac{1}{2}}y}{y^Ty} = \frac{y^THy}{y^Ty} $ 으로 변환된다.

 

일반화된 문제 $Sx = \lambda M x$ 를 $Hy = \lambda y $ 로 바꾼다. $S$, $M$ 이 양의 정부호이면 $H = M^{-\frac{1}{2}}SM^{\frac{1}{2}}$ 이다. 가장 큰 고유값은 $\lambda_1 $ 이고, $H$ 의 가장 큰 고유벡터 $y_1$ 과 $M^{-1}S$ 의 가장 큰 고유벡터 $x_1$ 를 알 수 있다.

 

$Hy_1 = \lambda_1 y_1$ 일때, $\max \frac{y^THy}{y^Ty} = \lambda_1$ 이고
$ x_1 = M^{-\frac{1}{2}}y_1 $ 에서 Sx_1 = \lambda_1 M x_1 $ 이다.

---

일반화된 고유벡터는 $M$-직교 이다.

 

대칭행렬 $S$ 는 직교하는 고유벡터를 가질 수 있다. 이를 $Sx = \lambda M x$ 에 적용가능할까?

$S$ 의 직교인 두 고유벡터 $x_1$ $x_2$ 에 대해서, $x_1^TMx_2= 0$ 을 만족할까?

$$ Sx_1 = \lambda_1 M x_1 & Sx_2 = \lambda_2 M x_2 & \lambda_1 \neq \lambda_2 \\ x_1^TMx_2 = 0 $$

양변에 $x_2^T$, $x_1^T$ 를 곱하면,

$$ x_2^TSx_1 = \lambda_1 x_2^TMx_1 & x_1^TSx_2 = \lambda_2 x_1^TMx_2 $$

첫번째 식을 전치하고 빼면,

$$ x_1^TSx_2^T - x_1^TSx_2 = (\lambda_2 - \lambda_1)x_1^TMx_2 = 0 \\

x_1^TMx_2 = 0 \becuase \lambda_1 \neq \lambda_2 $$

 

즉 $x_1^TSx_2 = 0$, $x_1^TMx_2 = 0$ 이다.

---

비가역인 양의 준정부호 $M$ 

 

행렬 $M$ 이 양의 준정부호일 때만 $x^TMx = 0$ 일 수 있다.

$x^TMx = 0$ 이면, 몫 $\frac{x^TSx}{x^TMx}$ 이 무한이 될 수 있고, 행렬 $M^{-\frac{1}{2}}$ 와 $H$ 가 존재조차 안할 수 있다.

 

통계학에서 $M$ 은 공분산행렬인데, 만약 완전히 똑같은 실험을 반복하면 공분산행렬 $M$ 은 특이행렬(역행렬이 존재하지않음)이 된다.

이 경우 행렬식은 0 이고, 비가역이고 레일리 몫은 무한이 된다.

$ \alpha \geq 0$, $\beta \geq 0$ 이고, 고유값 $ \lambda = \frac{\beta}{\alpha}$ 이라고 할때, $\alpha Sx = \beta Mx$ 이다.

1. $\alpha > 0$, $\beta=0$ 이면, $\lambda =0$ 이고 $Sx = 0x$, $S$ 는 고유값 0 을 갖는다.
2. $\alpha =0$, $\beta = 0$ 이면, $\lambda = \infty$ 이고, $Mx=0$ 이다. $M$ 은 비가역이다.
3. $\alpha,\beta = 0$ 이면, $\lambda = \frac{0}{0}$ 은 정의되지 않는다. $Mx=0$ 이고, $Sx=0$ 이다.

군집 내에 샘플수보다 특징 가짓수가 더 많을때, $\alpha = 0$ 이 생길수 있다. ( 정확히는 모르겠음 )

이는 데이터 샘플수가 작을때 실제로 나타는 문제이다.

 

그래서 특이값 분해 접근법으로는 충분하지 않고, 특이값 분해를 일반화해 두번째 행렬 $M$ 에 대한 특이값 분해가 필요하다.

---

일반화된 특이값 분해

 

일반화된 특이값 분해의 전제는 복잡하지만, 여기서는 두개의 행렬 $S$, $M$ 에 대해서만 다루고, 대칭행렬 $S$ 는 양의 정부호인 인경우와, $M$ 이 특이행렬이 가능한 경우를 전제로 한다.

 

이 전제 조건하에 일반화된 특이값 분해 Generalized SVD 의 목적은 두 행렬을 동시에 분해하는 목적을 가진다.

---

두행렬 $A$, $B$ 과 랭크가 $n$ 이고 $m_a$ x $n$, $m_b$ x $n$ 인 행렬이 있다. -> 열이 독립

$S = A^TA$, $M = B^TB$ 의 크기는 모두 $n$ x $n$ 이고 양의 정부호이다.

$A$, $B$ 는 $A = U_A\Sigma_A Z$ 와 $B = U_B\Sigma_B Z$ 로 분해할수 있고, 동일한 $Z$ 를 갖는다.
- $U_A$, $U_B$ 는 직교행렬이고 크기는 $m_A$, $m_B$ 이다.
- $\Sigma_A$, $\Sigma_B$ 는 양의 대각행렬이고, $\Sigma_A^T\Sigma_A + \Sigma_B^T\Sigma_B = I_{n}$ 을 만족한다.
- $Z$ 는 크기가 $n$ 인 가역행렬이다.

여기서 $Z$ 는 우리가 알던 직교행렬이 아니라 그냥 $\Sigma_A$, $\Sigma_B$ 의 조건을 맞추기 위한 가역행렬이다.

이 $Z$ 가 행렬 $S$,$M$ 를 동시에 대각화 할수있다.

$$ A^TA = Z^T\Sigma_A^TU_A^TU_A\Sigma_A Z^T = Z^T(\Sigma_A^T \Sigma_A)Z \\

B^TB = Z^T \Sigma_B^TU_B^TU_B \Sigma_B Z^T = Z^T(\SIgma_B^T \Sigma_B)Z $$

위 식을 보면 동일한 행렬 $Z$ 로 대칭인 두 양의 정부호 행렬 $S$, $M$ 을 대각화 한다. 대각화하는데 직교성은 필수요소가 아니기 때문에 $Z$ 의 크기를 $\Sigma_A^T \Sigma_A + \Sigma_B^T \Sigma_B = I_n$ 으로 조절할 수 있다.

이 $Z$ 에 열벡터 $x_1$, $\cdots$, $x_n$ 들을 $\Sigma_A$ 에 대해 내림차순으로 정렬하도록 양수 $\sigma_A$ 를 부여한다. ( 특이값의 의미를 가질 수 있도록함. )

 

---

피셔의 선형 판별 분석 LDA Linear Discriminant Analysis

 

통계와 머신러닝에서의 응용을 살펴보자.

두 개의 다른 모집단의 샘플을 얻었다. 각 모집단의 평균은 $m$, 분산이 $\sigma$ 라고할때,

첫번째는 $m_1$, $\sigma_$, 두번째는 $m_2$ , $\sigma_2$ 라고 하자.

 

- 섞여있는 샘플들중 하나를 골랐을때, 어떤 모집단의 샘플인지 어떻게 확인할 수 있을까??

피셔의 선형 판별 분석 LDA 로 그 해답을 얻을 수 있다.

각각 샘플은 각 특성들을 가지는 특성 벡터이다.

 

특성을 나이, 키, 몸무게 라고할때,

첫번째 모집단의 나이 평균은 $m_{a1}, 키 평균은 $m_{h1}, 몸무게 평균은 $m_{w1}

두번째는 $m_{a2}$, $m_{h2}$, $m_{w2}$ 라고 하자.

 

모집단에 대하여 평균에 얼마나 떨어져 있는지에 대한 분산 $\sigma$ 은 3 x 3 행렬 $\Sigma$ 이다.

우리는 $m_1$, $m_2$, $\Sigma_1$, $\Sigma_2$ 에 대한 정보를 통해 샘플이 어떤 모집단에 속하는지 판정하는 규칙을 찾고싶다.

 

피셔의 판정법은 분리벡터 $v$ 를 찾는다.

샘플이 $v^Tf > c$ 를 만족하면 첫번째 모집단, $v^Tf < c $ 이면 두번째 모집단에서 왔다고 추측한다. 여기서 $f$ 는 특성 벡터이다.

여기서 분리벡터 $v$ 는 가능한많이 두 모집단을 구분할 수 있게 한다. 그리고 이는 분리 비율 $R$ 을 최대화한다. ($v^Tf$ 는 분리벡터와 특성 벡터의 내적값이다. )

 

분리비율 $ R = \frac{(x^Tm_1 - x^Tm_2)^2}{x^T\Sigma_1 x + x^T\Sigma_2 x} $ 

비율 $R$ 은 $\frac{x^TSx}{x^TMx}$ 형태를 띈다. 어디보자...

$S = (m_1 - m_2)(m_1 - m_2)^T$ 이고, 행렬 $M$ 은 $\Sigma_1 + \Sigma_2$ 이다.

이제 벡터 $x = v$ 에서 $Sv = \lambda Mv$ 에 대한 분리 비율 $R$ 을 최대화한다고 할 수 있다.

 

$S = (m_1 - m_2)(m_1 - m_2)^T$ 가 랭크 1 인 행렬이기 때문에, 피셔는 고유벡터 $v$ 를 찾을 수 있었다.

고유벡터 $v$ 는 항상 $S$ 의 기저벡터 방향으로 존재한다. 따라서 $Sv$ 는 항상 $m_1 - m_2$ 방향에 있다.

그러면 $Mv$ 도 $Sv = \lambda Mv$ 를 만족하기 위해서 항상 $m_1 - m_2$ 방향에 존재한다.

즉 $v = M^{-1}(m_1 - m_2) 이다.

 

이 결과는 샘플의 특성벡터가 $f$ 이면, $m_1^Tf$, $m_2^Tf$ 를 관찰해야 한다는 의미이다.

나중에 통계적 논의를 통해 $M$ 행렬이 어떻게 $v^Tf$ 테스트에 적용되는지 다룰 예정이다.