[PML intro] Ch7 Linear Algebra (Sec.7.1 Introduction - 4)

지난 포스팅의 [PML intro] Ch7 Linear Algebra (Sec.7.1 Introduction - 3)에서는 벡터와 행렬의 크기를 측정하는 방법인 노름(Norm)에 대해서 알아보았습니다. 오늘은 행렬을 몇 가지 중요한 성질들에 대해서 알아보도록 하겠습니다. 

 

1. 정사각행렬의 트레이스 (Trace of a square matrix)

정사각행렬 $\mathbf{A} \in \mathbb{R}^{n \times n}$의 트레이스는 행렬의 대각 원소들의 합으로 $\text{tr} (\mathbf{A}) = \sum_{i = 1}^{n} A_{ii}$로 정의됩니다. 트레이스는 단순하지만 몇 가지 중요한 성질들을 가집니다. $c \in \mathbb{R}$ 그리고 $\mathbf{A}, \mathbf{B} \in \mathbb{R}^{n \times n}$라고 할 때 아래의 성질들입니다. 

 

1) 전치(transpose)해도 값은 같다: $\text{tr} (\mathbf{A}) = \text{tr} (\mathbf{A}^{T})$

2) 덧셈에 대해 선형성(linearity)을 갖는다: $\text{tr} (\mathbf{A} + \mathbf{B}) = \text{tr} (\mathbf{A}) + \text{tr} (\mathbf{B})$

3) 스칼라곱에 대해 선형성을 갖는다: $\text{tr} (c\mathbf{A}) = c\text{tr} (\mathbf{A})$

4) 행렬곱의 순서를 바꾸어도 동일하다: $\text{tr} (\mathbf{A}\mathbf{B}) = \text{tr} (\mathbf{B}\mathbf{A})$

5) 고윳값과의 관계가 존재한다: $\text{tr} (\mathbf{A}) = \sum_{i = 1}^{n} \lambda_{i}$

 

마지막으로 순환(cyclic) 성질이 존재합니다. 예를 들어 정사각행렬 $\mathbf{A}, \mathbf{B}, \mathbf{C} \in \mathbb{R}^{n \times n}$이 있다고 가정했을 때 다음이 성립합니다. 

 

$$\text{tr}(\mathbf{A}\mathbf{B}\mathbf{C}) = \text{tr}(\mathbf{B}\mathbf{C}\mathbf{A}) = \text{tr} (\mathbf{C}\mathbf{B}\mathbf{A})$$

 

이를 통해 흔히 사용되는 트레이스 트릭(trace trick)을 얻을 수 있습니다. 즉, 스칼라 내적 $\mathbf{x}^{T}\mathbf{A}\mathbf{x}$를 다음과 같이 바꿀 수 있죠. 

 

$$\mathbf{x}^{T}\mathbf{A}\mathbf{x} = \text{tr}(\mathbf{x}^{T}\mathbf{A}\mathbf{x}) = \text{tr}(\mathbf{x}\mathbf{x}^{T}\mathbf{A})$$

 

이때, $\mathbf{x}^{T}\mathbf{A}\mathbf{x}$ 자체가 스칼라이므로 그 자체로 트레이스 연산을 적용한 결과와 동일하기 때문에 이와 같이 쓸 수 있습니다. 또한, 경우에 따라서 행렬 $\mathbf{A}$ 전체를 직접 계산하는 것은 비용이 크지만 $\mathbf{A}\mathbf{v}$와 같이 행렬-벡터 곱은 싸게 계산할 수 있습니다. 이때, 어떤 랜덤벡터 $\mathbf{v}$가 $\mathbb{E} [\mathbf{v}\mathbf{v}^{T}] = \mathbf{I}$를 만족한다고 가정하겠습니다. 그러면 다음 항등식을 이용해 몬테카를로(Monte-Carlo) 방식으로 $\text{tr} (\mathbf{A})$를 근사할 수 있습니다. 

 

$$\begin{align} \text{tr} (\mathbf{A}) &= \text{tr} (\mathbf{A} \mathbb{E} (\mathbf{v}\mathbf{v}^{T})) \\ &= \mathbb{E} [\text{tr} (\mathbf{A}\mathbf{v}\mathbf{v}^{T})] \\ &= \mathbb{E} [\text{tr} (\mathbf{v}^{T}\mathbf{A}\mathbf{v})] \\ &= \mathbb{E} [\mathbf{v}^{T}\mathbf{A}\mathbf{v}] \end{align}$$

 

이를 지난 포스팅에서 잠깐 언급되었던 Hutchinson trace estimator라고 부릅니다. 

 

2. 정사각행렬의 행렬식 (Determinant of a square matrix)

정사각행렬의 행렬식 $\text{det} (\mathbf{A})$ 또는 $|\mathbf{A}|$는 행렬을 선형변환의 관점에서 보았을 때 단위부피 및 면적을 얼마나 늘리거나 줄이는 지를 나타내는 값을 의미합니다. 정확한 정의는 복잡하기 때문에 여기서는 범위를 넘어서기 때문에 제 이전에 포스팅한 선형대수학을 참고해주세요. 이 행렬식은 몇 가지 중요한 성질들을 가집니다. 

 

1) 전치(transpose)해도 값은 같다: $\text{det} (\mathbf{A}) = \text{det} (\mathbf{A}^{T})$

2) 스칼라곱의 관계성: $\text{det} (c\mathbf{A}) = c^{n}\text{det} (\mathbf{A})$

3) 행렬곱에서의 관계성: $\text{det} (\mathbf{A}\mathbf{B}) = \text{det} (\mathbf{A}) \text{det} (\mathbf{B})$

4) 가역성(invertible) 사이의 관계성: $\text{det} (\mathbf{A}) = 0 \Leftrightarrow \mathbf{A} \text{ is singular }$ 

5) 역행렬과의 관계성: $\text{det} (\mathbf{A}^{-1}) = \frac{1}{\text{det} (\mathbf{A})}$

6) 고윳값과의 관계성: $\text{det} (\mathbf{A}) = \prod_{i = 1}^{n} \lambda_{i}$

 

양의 정부호 (positive definite) 행렬 $\mathbf{A}$에 대해 Cholesky 분해를 $\mathbf{A} = \mathbf{L}\mathbf{L}^{T}$라고 쓸 수 있습니다. 여기서 $\mathbf{L}$는 하삼각 행렬 (lower triangular matrix)입니다. 이때, $\text{det} (\mathbf{A}) = \text{det} (\mathbf{L})\text{det} (\mathbf{L}^{T}) = \text{det} (\mathbf{L})^{2}$입니다. 따라서, 양변에 로그를 취해주면 다음과 같이 쓸 수 있습니다. 

 

$$\begin{align} \log \text{det} (\mathbf{A}) &= 2\log \text{det} (\mathbf{L}) \\ &= 2 \log \prod_{i = 1}^{n} L_{ii} \\ &= 2 \text{tr} (\log \text{diag} (\mathbf{L})) \end{align}$$

 

3. 행렬의 랭크 (Rank of a matrix)

행렬 $\mathbf{A}$의 열랭크 (column rank)는 그 열벡터들이 span하는 공간의 차원이고 행랭크 (row rank)는 그 행벡터들이 span하는 공간의 차원을 의미합니다. 선형 대수의 기본정리 (Fundamental Theory of Lineary Algebra; FTLA)에 따르면 항상 다음이 성립합니다. 

 

$$\text{columnrank} (\mathbf{A}) = \text{rowrank} (\mathbf{A})$$

 

이를 그냥 행렬의 랭크(rank)라고 부르고 $\text{rank} (\mathbf{A})$라고 씁니다. 기본적인 성질들은 다음과 같습니다. 

 

1) 행렬 $\mathbf{A} \in \mathbb{R}^{m \times n}$에 대해 $\text{rank} (\mathbf{A}) \le \text{min} (m, n)$이다. 이때, $\text{rank} (\mathbf{A}) = \text{min} (m, n)$라면 행렬 $\mathbf{A}$를 풀랭크 (full rank)라고 부르고 그렇지 않으면 rank deficient라고 한다. 

2) 행렬 $\mathbf{A} \in \mathbb{R}^{m \times n}$에 대해 

 

$$\text{rank} (\mathbf{A}) = \text{rank} (\mathbf{A}^{T}) = \text{rank} (\mathbf{A}^{T}\mathbf{A}) = \text{rank} (\mathbf{A}\mathbf{A}^{T})$$

 

3) 두 행렬 $\mathbf{A} \in \mathbb{R}^{m \times n}$와 $\mathbf{B} \in \mathbb{R}^{n \times p}$ 에 대해 

 

$$\text{rank} (\mathbf{A}\mathbf{B}) \le \text{min} (\text{rank} (\mathbf{A}), \text{rank} (\mathbf{B}))$$

 

4) 두 행렬 $\mathbf{A}, \mathbf{B} \in \mathbb{R}^{m \times n}$에 대해 

 

$$\text{rank} (\mathbf{A} + \mathbf{B}) \le \text{rank}(\mathbf{A}) + \text{rank} (\mathbf{B})$$

 

5) 정사각행렬은 full rank인 경우에만 가역이다. 따라서, full rank인 것과 $\text{det} (\mathbf{A}) \neq 0$인 것과도 동치이다. 

 

4. 행렬의 조건수 (Condition number of a matrix)

행렬 $\mathbf{A}$의 조건수 (Condition number)는 행렬 $\mathbf{A}$를 포함하는 수치계산이 얼마나 안정적인지 또는 민감한지를 측정하는 값으로 다음과 같이 정의합니다. 

 

$$\kappa (\mathbf{A}) = ||\mathbf{A}|| \cdot ||\mathbf{A}^{-1}||$$

 

여기서 $||\mathbf{A}||$는 행렬 노름으로 보통 2-노름으로 정의합니다. 이때, 항상 $\kappa (\mathbf{A}) \ge 1$이며 $\kappa (\mathbf{A})$가 1에 가까우면 well-conditioned라고 부르고 매우 크면 ill-conditioned라고 부릅니다. 여기서 조건수가 크다는 것인 $\mathbf{A}$가 singular에 가깝다는 것을 의미합니다. 이 값은 단순히 행렬식의 크기를 보는 것이아니라 singular에 얼마나 가까운지를 더 잘 반영합니다. 

 

예를 들어 $\mathbf{A} = 0.1 \mathbf{I}_{100 \times 100}$이라고 가정하겠습니다. 그러면 $\text{det} (\mathbf{A}) = 10^{-100}$이기 때문에 거의 0이기 때문에 가역성이 위험해보인다고 볼 수 있습니다. 하지만 조건수로 보면 $\kappa (\mathbf{A}) = 1$로 안정적인 계산이 가능합니다. 실제로 $\mathbf{A}\mathbf{x}$는 $\mathbf{x}$의 각 원소를 0.1배로 줄이기만 하므로 수치적으로 꽤 안정적입니다. 

 

- 선형방정식에서의 조건수 직관

선형방정식 $\mathbf{A}\mathbf{x} = \mathbf{b}$ 관점에서도 이를 해석해볼 수 있습니다. $\mathbf{A}$가 비특이(non-singular)라면 유일해 $\mathbf{x} = \mathbf{A}^{-1} \mathbf{b}$라고 쓸 수 있습니다. 그렇다면 $\mathbf{b}$를 $\mathbf{b} + \Delta \mathbf{b}$로 살짝 바꾼다면 어떻게 변할까요? 그러면 새로운해는 다음을 만족해야합니다. 

 

$$\mathbf(A) (\mathbf{x} + \Delta \mathbf{x}) = \mathbf{b} + \Delta \mathbf{b}$$

 

따라서, $\Delta \mathbf{x} = \mathbf{A}^{-1} \Delta \mathbf{b}$가 되죠. 만약, $\mathbf{A}$가 well-conditioned이라면 작은 $\Delta \mathbf{b}$가 작은 $\mathbf{x}$로 이어지게 됩니다. 반면 $\mathbf{A}$가 ill-conditioned이면 작은 $\Delta \mathbf{b}$가 엄청 큰 $\mathbf{x}$로 증폭되게 됩니다. 

 

- 조건수와 특이값, 고유값

2-노름 기준으로 조건수는 가장 큰 특이값 vs 가장 작은 특이값의 비와 동일합니다. 즉, $\kappa (\mathbf{A}) = \frac{\sigma_{\text{max}}}{\sigma_{\text{min}}} = \sqrt{\frac{\lambda_{\text{max}}}{\lambda_{\text{min}}}}$이 됩니다. 

 

- 조건수와 최적화 직관

이차형식 $f(\mathbf{x}) = \mathbf{x}^{T}\mathbf{A}\mathbf{x}$의 등고선(level set)을 그려보면 일반적으로 타원의 모양이 됩니다. 이때, 조건수가 커질수록 이 타원은 특정 방향으로 길게 찢어진 모양이 되는데 이는 손실 함수를 매우 좁고 긴 골짜기에 해당하죠. 따라서, $\kappa (\mathbf{A}) = 1$인 경우 등고선이 원 모양으로 모든 방향으로 스케일이 같게 됩니다. 반면 $\kappa (\mathbf{A})$가 매우 크면 어떤 방향은 매우 완만하지만 다른 방향은 매우 가파른꼴이 되어 그래디언트 기반의 최적화 시 지그재그 치면서 느리게 수렴하게 됩니다.