CAIS (Continual AI Study)

이번 포스팅에서는 행렬의 $A=LU$ 분해 (LU decomposition or factorization)에 대해 살펴보자.

이러한 행렬의 분해들은 컴퓨터에서의 계산이 편리하고 주어진 행렬이 무엇인지 분석하기 쉽게 만들어 준다.

1. 곱셈의 역 (Inverse)

LU 분해의 이해를 돕기 위해 지난시간에 다루었던 행렬 곱셈의 inverse에 대해 짧게 살펴보자.

Invertible하고 son-singular인 두 행렬 $A$와 $B$가 있을때, 행렬 곱 $AB$의 뒤에 그것들의 역행렬들을 어떤 순서로 곱해야 단위 행렬이 나올까?

(즉, $AB??=I$)

이를 위해서는 아래와 같이 "Reverse order"로 곱해줘야 한다.

$$\begin{equation} A\underbrace{BB^{-1}}_{I}A^{-1} = AA^{-1} = I \end{equation} \tag{1}$$

행렬의 전치 (Transpose)

행렬의 전치는 row축과 column축을 뒤바꾸는 것을 말하며 다음과 같이 대각선을 중심으로 뒤집힌 모양을 말한다.

$$ \underbrace{\begin{bmatrix} a_{11} & a_{12}\\ a_{21} & a_{22} \end{bmatrix}}_{A} \xrightarrow{\text{transpose}} \underbrace{\begin{bmatrix} a_{11} & a_{21}\\ a_{12} & a_{22} \end{bmatrix}^T}_{A^T} \tag{2}$$

이를 행렬 곱셈에 적용하면 아래와 같이 된다.

$$\begin{equation} AA^{-1}=I \xrightarrow{\text{transpose}} (AA^{-1})^T = I^T \xrightarrow{\text{reverse order}} \underbrace{(A^{-1})^T}_{(A^T)^{-1}}(A)^T=I \end{equation} \tag{3}$$

여기서 전치가 row축과 column축을 뒤바꾸는 것이기 때문에 행렬 곱셈의 순서가 바뀐다.

또한 $A$의 역행렬의 전치 부분은 $A$의 전치행렬의 역행렬이 된다. (항등행렬이 나오려면)

2. LU 분해

$A=LU$ 분해는 행렬의 분해방법 중 가장 간단한 형태로 어떤 행렬 $A$가 있을 때, 이를 하삼각 행렬(Lower triangular matrix)와 상삼각 행렬(Upper triangular matrix)의 곱으로 분해하여 나타내는 것을 말한다.

(우선 분해과정에서 행교환이 필요하지 않은 행렬만 고려한다)

2.1. 2x2 case

어떤 non-singular 행렬 $A$가 있을때, 지난 포스팅 [2. 행렬의 소거법 참고]에서 배웠던 소거 행렬을 사용하여 상삼각 행렬을 다음과 같이 만들 수 있다.

$$\underbrace{\begin{bmatrix} 1 & 0 \\ -4 & 1 \end{bmatrix}}_{E_{21}} \underbrace{\begin{bmatrix} 2 & 1 \\ 8 & 7 \end{bmatrix}}_{A} = \underbrace{\begin{bmatrix} 2 & 1 \\ 0 & 3 \end{bmatrix}}_{U} \tag{4}$$

$A=LU$와 같은 형태를 얻기 위해서는 다음과 같이 양변에 $E_{21}$의 역행렬을 곱해주면 된다.

$$(E_{21})^{-1} E_{21} A  = (E_{21})^{-1}U \tag{5}$$

여기서 $(E_{21})^{-1}$는 $E_{21}$과 곱했을때 항등행렬이 나오게끔 만들면 되므로 -4만 4로 바꿔주면 되며 (하삼각 행렬이 만들어짐), 결국 $A$는 다음과 같이 $LU$의 형태로 분해될 수 있다.

$$\underbrace{\begin{bmatrix} 2 & 1 \\ 8 & 7 \end{bmatrix}}_{A} =\underbrace{\begin{bmatrix} 1 & 0 \\ 4 & 1 \end{bmatrix}}_{L} \underbrace{\begin{bmatrix} 2 & 1 \\ 0 & 3 \end{bmatrix}}_{U} \tag{6}$$

2.2. 3x3 case

이번에는 왜 $EA=U$의 형태에서 굳이 역행렬을 구하여 $A=LU$의 형태로 만드는 것일까에 대해 생각해보자

이를 위해 다음과 같은 3x3 행렬 $A$를 고려해보자.

$$ A= \begin{bmatrix} 2 & 1 & 7 \\ 4 & -1 & 16 \\ 0 & -15 & 19 \end{bmatrix} \tag{7}$$

이러한 3x3 행렬을 상삼각 행렬로 만들기 위해서는 $a_{21}, a_{31}, a_{32}$를 순차적으로 제거해야 하므로 $E_{32}E_{31}E_{21}A=U$와 같은 형태가 만들어지며 $E$만 따로 계산해서 나타내면 다음과 같다.

$$ \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -5 & 1 \end{bmatrix}}_{E_{32}} \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}}_{E_{31}=I} \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}}_{E_{21}} = \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ \color{red}{10} & -5 & 1 \end{bmatrix}}_{E} \text{ in } \color{blue}{E}A=U   \tag{8}$$

여기서 $L$을 구하려면 $E$행렬들의 역행렬을 reverse order에서 곱해주면 된다.

$$ \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}}_{(E_{21})^{-1}} \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}}_{(E_{31})^{-1}=I} \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 5 & 1 \end{bmatrix}}_{(E_{32})^{-1}} = \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ \color{red}{2} & 1 & 0 \\ 0 & \color{red}{5} & 1 \end{bmatrix}}_{L} \text{ in } A=\color{blue}{L}U   \tag{9}$$

여기서 $\pm 2$와 $\pm 5$는 소거 과정에서 pivot row에 곱해지는 multiplier이다. 

Eq. (8-9)을 보면 $E$에 10이라는 숫자가 생겼고, $L$에는 multiplier들만 그대로 들어간다.

이러한 추가적인 숫자는 골칫거리가 되는경우가 많다.

예를 들어, 아주 큰 행렬 $A$에 대해 $U$를 만들어낼 수 있는 $E$를 딥러닝에서 사용되는 gradient descent를 통해 최적화문제로 푼다고 해보면, 위의 10과 같이 뭔가 학습해야할 파라미터 수가 증가하고 (search space 증가) 문제를 더 어렵게 만들 수 있다.

따라서 $A=LU$의 형태가 더 좋은 표현이다.

2.3. 치환 행렬 (Permutation matrix)

지금까지 행 교환을 요구하지 않는 행렬 $A$에 대하여 살펴보았다.

Eq. (9)와 같이 빨간색으로 표시된 multipliers가 $L$에 그대로 들어가는 특성을 유지하기 위해 행교환은 치환행렬 $P$를 사용하여 따로 처리해보자

$P_{23}$를 2번째 row와 3번째 row를 바꿔주는 행렬이라고 하자.

$n$개의 rows가 있을때, 행교환의 가능한 조합의 수는 $n!$가 된다.

$n=3$일 때 다음과 같이 $n!=6$개의 치환행렬이 존재한다.

$$ \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}}_{I} \underbrace{\begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}}_{P_{12}} \underbrace{\begin{bmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{bmatrix}}_{P_{13}} \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}}_{P_{23}} \underbrace{\begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix}}_{P_{13}P_{23}} \underbrace{\begin{bmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix}}_{P_{12}P_{23}}  \tag{10}$$

이를 통해 행교환이 필요할 경우 $P$를 사용하여 아래와 같이 LU 분해를 표현할 수 있다.

$$ PA=LU \tag{11}$$

이러한 $P$의 전치 행렬은 행교환했던것을 다시 원래대로 되돌려놓게 된다. (헷갈리면 계산해보면 알 수 있다)

즉 $P^T$는 $P$의 역행렬이다.

$$ P^T=P^{-1} \tag{12}$$

Reference

1. MIT Lecture by Gilbert Strang [Link]

이번 포스팅에서는 행렬 곱셈의 다양한 해석에 대해 살펴보고, 역행렬 및 Gauss-Jordan 소거법을 다룬다.

1. 행렬 곱(Matrix Multiplication)

고교과정에서 배웠던 행렬 곱셈을 간단하게 상기해보자.

두개의 행렬 $A \in \mathbb{R}^{m \times n}$, $B \in \mathbb{R}^{n \times p}$가 있을 때, 그것들의 곱 $C=AB \in \mathbb{R}^{m \times k}$의 각 요소는 다음과 같이 계산된다.

$$\begin{align} c_{34} &= (\text{row 3 of }A) \cdot (\text{column 4 of }B) \\ &= a_{31}b_{14} + a_{32}b_{24} + \cdots = \sum^n_{k=1}a_{3k}b_{k4}  \end{align} \tag{1}$$

이를 column의 관점에서 살펴보면,

$$\underbrace{\begin{bmatrix} \, & \, & \, \\ \, & \, & \,  \\ \, & \, & \,  \end{bmatrix}}_{A \in \mathbb{R}^{m \times n}} \underbrace{\begin{bmatrix} \, & \, & \, \\ col_1 & \cdots & col_p \\ \, & \, & \,  \end{bmatrix}}_{B \in \mathbb{R}^{n \times p}} = \underbrace{\begin{bmatrix} \, & \, & \,  \\ A\cdot(col_1) & \cdots & A\cdot(col_p) \\ \, & \, & \, \end{bmatrix}}_{C \in \mathbb{R}^{m \times p}} \tag{2}$$

여기서 흥미있는 특징은 다음과 같다.

• $C$의 column들은 $A$의 column들의 combinations이다.
• 마찬가지로, $C$의 row들은 $B$의 row들의 combinations이다.

※ 이러한 특징은 column들에 matrix를 곱함으로써 column vector들을 다른 공간에서 볼 수 있다는 것을 의미하며 이러한 개념은 deep learning, contrastive learning, distance metric learning 등 다양하게 사용될 수 있다.

이번에는 column vector와 row vector의 곱셈 형태를 살펴보자.

$$\underbrace{\begin{bmatrix} 2 \\ 3  \\ 4  \end{bmatrix}}_{m \times 1} \underbrace{\begin{bmatrix} 1 & 6 \end{bmatrix}}_{1 \times p} = \underbrace{\begin{bmatrix} 2 & 12  \\ 3 & 18 \\ 4 & 24 \end{bmatrix}}_{m \times p} \tag{3}$$

여기서 col2는 col1에 6을 곱한 것과 같다 → 두 컬럼은 같은 벡터이다 → 즉, column space에서 두 벡터는 intersection은 line이다.

또한 rows에 대해서도 동일한 특징을 가진다.

Eq. (3)을 토대로 $AB$는 (cols of $A$) $\times$ (rows of $B$)의 합으로 나타낼 수 있다.

$$\begin{bmatrix} 2 & 7 \\ 3 & 8  \\ 4 & 9 \end{bmatrix} \begin{bmatrix} 1 & 6 \\ 0 & 0 \end{bmatrix} = \begin{bmatrix} 2 \\ 3 \\ 4  \end{bmatrix} \begin{bmatrix} 1 & 6 \end{bmatrix} + \begin{bmatrix} 7 \\ 8 \\ 9  \end{bmatrix} \begin{bmatrix} 0 & 0 \end{bmatrix} \tag{4}$$

또한 행렬 곱은 블록 단위로 쪼개서 다음과 같이 계산하는 것도 가능하다.

$$AB=C = \begin{bmatrix} A_1 & A_2 \\ A_3 & A_4  \end{bmatrix} \begin{bmatrix} B_1 & B_2 \\ B_3 & B_4 \end{bmatrix} = \begin{bmatrix} A_1B_1+A_2B_3 & A_1B_2+A_2B_4  \\ A_3B_1+A_4B_3 & A_3B_2 + A_4B_4  \end{bmatrix}  \tag{5}$$

여기서 블록들을 균등하게 쪼갤필요는 없으며 블록들끼리 계산이 가능하기만 하면 된다.

2. 역행렬 (Inverses)

어떤 정방 행렬 (square matrix) $A \in \mathbb{R}^{n \times n}$이 주어지면 그것의 역행렬 $A^{-1} \in \mathbb{R}^{n \times n}$은 다음과 같이 정의된다.

$$A^{-1}A = I = AA^{-1} \tag{6}$$

• $A$에 대한 역행렬이 존재한다면, $A$는 "invertible" 혹은 "non-singular"라고 부른다.
• $A$가 어떤 다른 공간으로의 projection을 수행한다고 하면, $A^{-1}$는 원래의 공간으로 재매핑한다.

그렇다면, 역행렬이 존재하지 않는 경우에 대해 살펴보자 (Singular case)

$$Ax= \begin{bmatrix} 1 & 3 \\ 2 & 6  \end{bmatrix} \begin{bmatrix} 3 \\ -1 \end{bmatrix} = \begin{bmatrix} 0  \\ 0  \end{bmatrix}  \tag{7}$$

이와 같이 $Ax=0$를 만족하는 0이 아닌 벡터 $x$가 존재한다면 $A$의 역행렬은 존재하지 않는다.

※ 선형 시스템에서 입력 $x$가 주어졌을때, $A$를 통해 그것을 0으로 만들어 버리면 다시 원래의 공간으로 재매핑할 수 있는 어떤 행렬이 존재한다는 것은 unfeasible하다.

※ 또한 column vector들의 linear combination이 0이 될 수 있다는 것을 의미하며 그것들이 같은 선상에 존재한다는 것을 나타낸다. (즉 역행렬이 존재하려면 column들이 independent해야 하는데 이는 추후 column space를 다룰 때 자세히 살펴보자)

Gauss-Jordan Elimination

마지막으로 Gauss-Jordan 소거법을 이용하여 역행렬을 구해보자.

$$\underbrace{\begin{bmatrix} 1 & 3 \\ 2 & 7  \end{bmatrix}}_{A} \underbrace{\begin{bmatrix} a & b \\ c & d \end{bmatrix}}_{A^{-1}} = \underbrace{\begin{bmatrix} 1 & 0  \\ 0 & 1  \end{bmatrix}}_{I}  \tag{8}$$

이것은 다음과 같이 두개의 연립 선형 방정식들로 표현할 수 있다.

$$\begin{align} \begin{bmatrix} 1 & 3 \\ 2 & 7  \end{bmatrix} \begin{bmatrix} a \\ c \end{bmatrix} &= \begin{bmatrix} 1 \\ 0 \end{bmatrix} \\ \begin{bmatrix} 1 & 3 \\ 2 & 7  \end{bmatrix} \begin{bmatrix} b \\ d \end{bmatrix} &= \begin{bmatrix} 0 \\ 1 \end{bmatrix}  \end{align} \tag{9}$$

Gauss-Jordan 소거법은 동시에 여러개의 연립 선형 방정식을 풀 수 있게끔 하는 것이다.

즉,

$$\left[ \begin{array}{cc|cc} 1 & 3 & 1 & 0 \\ 2 & 7& 0 & 1 \end{array} \right] \Rightarrow \left[ \begin{array}{cc|cc} 1 & 3 & 1 & 0 \\ 0 & 1& -2 & 1 \end{array} \right] \Rightarrow \left[ \begin{array}{cc|cc} 1 & 0 & 7 & -3 \\ 0 & 1 & -2 & 1  \end{array} \right] \tag{10}$$

마지막에 도출된 행렬은 무엇을 의미하는지 알기 위해 elimination matrix를 사용하여 위의 과정을 표현해보자

$$E[A \quad I] = [I \quad ?]$$ 

여기서 Eq. (5)와 같이 블록 곱에 의해 $EA=I$가 된다.

즉 $E=A^{-1}$이다.

따라서, $?=EI=A^{-1}$가 되므로,

$$A^{-1} = \begin{bmatrix} 7 & -3 \\ -2 & 1  \end{bmatrix}$$

Reference

1. Deisenroth, Marc Peter, A. Aldo Faisal, and Cheng Soon Ong. Mathematics for machine learning. Cambridge University Press, 2020.

2. MIT Lecture by Gilbert Strang [Link]

연립방정식을 푸는 것의 핵심은 solution set은 유지하면서 연립 방정식을 더 간단한 형태로 변형하는 elementary transformations이다.

• a) 행렬에서 두 rows의 exchange
• b) a row에 대한 0이아닌 상수 곱
• c) 두 rows의 덧셈

1. Row-Echelon Form (REF)

다음의 연립방정식을 고려해보자.

$$\begin{align} x_1 + 2x_2 + x_3 &= 2 \\ 3x_1 + 8x_2 + x_3 &=12 \\ 4x_2 + x_3 &=2 \end{align} \tag{1}$$

이를 $\mathbf{Ax}=\mathbf{b}$의 form에서 간략성을 위해 변수 $\mathbf{x}$의 노테이션을 생략한 형태를 augmented matrix라고 하며 다음과 같이 나타낸다.

$$\begin{equation} \left[ \begin{array}{ccc|c} 1 & 2 & 1 & 2 \\ 3 & 8& 1 & 12 \\ 0 & 4 & 1 & 2  \end{array} \right] \end{equation} \tag{2} $$

여기서 elementary transformations에 의해 다음과 같이 간략화 시킬 수 있다.

$$\left[ \begin{array}{ccc|c} \color{red}{1} & 2 & 1 & 2 \\ 3 & 8& 1 & 12 \\ 0 & 4 & 1 & 2  \end{array} \right] \begin{array} \\ -3R_1 \\ \end{array} \Rightarrow \left[ \begin{array}{ccc|c} \color{red}{1} & 2 & 1 & 2 \\ 0 & \color{red}{2}& -2 & 6 \\ 0 & 4 & 1 & 2  \end{array} \right] \begin{array} \, \\ \, \\ -2R_2 \end{array} \Rightarrow \left[ \begin{array}{ccc|c} \color{red}{1} & 2 & 1 & 2 \\ 0 & \color{red}{2}& -2 & 6 \\ 0 & 0 & \color{red}{5} & -10  \end{array} \right] \tag{3}$$

마지막 행렬과 같이 upper triangular matrix의 형태를 REF라고 하며 빨간색으료 표시된 요소는 pivot이라 한다.

이를 다시 연립방정식으로 바꾸면,

$$\begin{align} x_1 + 2x_2 + x_3 &= 2 \\ 2x_2 - 2x_3 &=6 \\ 5x_3 &=-10 \end{align} \tag{4}$$

이는 back substitution에 의해 밑에서부터 $x_3=-2, x_2=1, x_1=2$로 풀 수 있다.

2. Elimination Matrix and Elementary Matrix

이 섹션에서는 Elimination 및 elementary transformations을 컴퓨터가 처리할 수 있도록 행렬곱으로써 어떻게 나타내는지에 대해 살펴본다.

먼저 행렬 연산들은 다음과 같이 동작한다.

1) matrix $\times$ column $\to$ column

$$\begin{bmatrix} - & - & -\\ - & - &- \\ -&-&- \end{bmatrix} \begin{bmatrix} 3 \\ 4 \\ 5 \end{bmatrix} = \begin{matrix} 3 \times \text{col1} \\ 4 \times \text{col2} \\ 5 \times \text{col3} \end{matrix} \tag{5}$$

2) row $\times$ matrix $\to$ row

$$\begin{bmatrix} 1 & 2 & 7 \end{bmatrix} \begin{bmatrix} - & - & -\\ - & - &- \\ -&-&- \end{bmatrix} = \begin{matrix} 1 \times \text{row1} \\ 2 \times \text{row2} \\ 7 \times \text{row3} \end{matrix} \tag{6}$$

먼저 row $\times$ matrix $\to$ row의 동작원리를 떠올리면서 Eq. (3)의 첫번째 화살표에 대한 처리를 행렬 곱으로 나타내보자.

$$\begin{bmatrix} 1 & 0 & 0 \\  \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 2 & 1\\ 3 & 8 &1 \\ 0&4&1 \end{bmatrix} = \begin{bmatrix} 1 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 4 & 1 \end{bmatrix} \tag{7}$$

여기서 첫번째 row와 세번째 row는 변하지 않으므로 [1 0 0]과 [0 0 1]이 되며 두번째 row는 $-3 \times$ row1 $+ 1$ row2와 같이 계산되므로 다음과 같이 [-3 1 0]을 곱하는 것에 의해 표현될 수 있다.

$$\underbrace{\begin{bmatrix} 1 & 0 & 0 \\ -3 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}}_{E_{21}} \underbrace{\begin{bmatrix} 1 & 2 & 1\\ 3 & 8 &1 \\ 0&4&1 \end{bmatrix}}_{A} = \begin{bmatrix} 1 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 4 & 1 \end{bmatrix} \tag{8}$$

여기서 $E_{21}$은 A의 2번째 row, 1번째 column의 요소를 제거하기 위한 행렬을 의미한다.

Eq. (3)의 두번째 화살표도 동일하게 나타낼 수 있다.

$$\underbrace{\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -2 & 1 \end{bmatrix}}_{E_{32}} \begin{bmatrix} 1 & 2 & 1\\ 0 & 2 &-2 \\ 0&4&1 \end{bmatrix} = \underbrace{\begin{bmatrix} 1 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 0 & 5 \end{bmatrix}}_{U} \tag{9}$$

이것을 간단한 형태로 나타내면 결합법칙에 의해 다음과 같이 쓸 수 있다.

$$\begin{align} E_{32}(E_{21}A) &= U \\ \Rightarrow (E_{32}E_{21})A &= U \end{align} \tag{10}$$

결과적으로 $A$를 $U$로 만드는 elimination matrix는 $E_{32}$와 $E_{21}$를 곱한 하나의 행렬로 표현 가능하며 컴퓨터에 저장 및 recomputation 관점에서 효율적이다.

위의 elimination matrix를 도출하는 과정에서 elementary transformations중 a row에 대한 상수 곱과 두 rows의 덧셈을 행렬곱으로 나타내는 법을 보았다.

비슷하게 행렬에서 rows의 exchange는 치환행렬을 통해 수행될 수 있다.

Permutation Matrix

- Exchange rows 1 and 2

$$\underbrace{\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}}_{P} \begin{bmatrix} a & b\\ c &d \end{bmatrix} = \begin{bmatrix} c & d \\ a & b \end{bmatrix} \tag{11}$$

- Exchange columns 1 and 2

$$ \begin{bmatrix} a & b\\ c &d \end{bmatrix} \underbrace{\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}}_{P} = \begin{bmatrix} b & a \\ d & c \end{bmatrix} \tag{12}$$

Reference

1. Deisenroth, Marc Peter, A. Aldo Faisal, and Cheng Soon Ong. Mathematics for machine learning. Cambridge University Press, 2020.

2. MIT Lecture by Gilbert Strang [Link]

0. Linear Algebra and Vector

선형 대수 (Linear Algebra)는 벡터에 대해 배우고, 벡터를 다루는 규칙들을 공부하는 학문이다.

벡터란, 고등과정에서 배웠던 기하학적 벡터에서 확장해서 "서로 자유자재로 더하고, Scaling이 가능한 Object"라는 좀 더 일반적인 의미를 가진다.

머신러닝 혹은 딥러닝에서 벡터는 주로 elements of $\mathbb{R}^n$ ($n$개의 실수들의 튜플)의 형태로써 다루어지며 다음과 같이 표현된다.

$$\begin{equation} \mathbf{a} = \begin{bmatrix} 1 \\ 2\\ 3 \end{bmatrix} \in \mathbb{R}^3 \end{equation}$$

1. Systems of Linear Equations

이번 포스트에서는 선형 대수의 중심이 되는 파트인 연립 일차 방정식 (Systems of Linear Equations)을 다룬다.

Example 1

The Geometry of Linear Equations

두개의 변수 $x_1, x_2$를 가진 연립 일차 방정식에서, 각 선형 방정식은 $x_1x_2$-평면위의 하나의 선을 정의한다.

Solution은 모든 방정식들을 동시에 충족해야하므로, solution set은 이러한 선들의 intersection이다.

다음의 연립 일차 방정식을 고려해보자.

$$\begin{align} 4x_1 + 4x_2 &= 5 \\ 2x_1 - 4x_2 &=1 \end{align} \tag{3}$$

여기서 solution은 점 $(1,\frac{1}{4})$이며 아래 그림과 같이 나타낼 수 있다.

비슷하게, 3개의 변수가 있을때, 각 선형 방정식은 3차원 공간에서의 평면을 결정한다.

이러한 연립 일차 방정식을 좀더 체계적으로 풀기 위해, 행렬이라는 개념이 도입되는데, 예를 들어 다음과 같은 연립 선형 방정식을 고려해보자.

$$\begin{align} 2x_1 + -x_2 &= 0 \\ -x_1 + 2x_2 &=3 \end{align} \tag{4}$$

이는 다음과 같이 행렬을 사용하여 표현될 수 있다.

$$\begin{equation} \underbrace{\begin{bmatrix} 2 & -1 \\ -1 & 2 \end{bmatrix}}_{A} \underbrace{\begin{bmatrix} x_1 \\ x_2 \end{bmatrix}}_{\mathbf{x}} = \underbrace{\begin{bmatrix} 0 \\ 3 \end{bmatrix}}_{\mathbf{b}} \tag{5} \end{equation}$$

여기서 $A$는 계수들의 행렬, $\mathbf{x}$는 unknowns의 벡터로 해석가능하다.

Eq. (5)는 또한 다음과 같이 나타낼 수 있다.

$$\begin{equation} x_1 \underbrace{\begin{bmatrix} 2 \\ -1 \end{bmatrix}}_{\text{Column 1}} + x_2  \underbrace{\begin{bmatrix} -1 \\ 2 \end{bmatrix}}_{\text{Column2}} = \begin{bmatrix} 0 \\ 3 \end{bmatrix} \tag{6} \end{equation}$$

이를 그림으로 나타내면 다음과 같다.

즉, $A\mathbf{x}=\mathbf{b}$의 form에서 $\mathbf{b}$는 $A$의 columns의 선형결합이다.

이러한 해석은 머신러닝에서 중요한데, 일반적으로 입력 데이터의 각 feature는 column vector로써 주어진다.

또한 $\mathbf{b}$가 ground-truth label이라하면 $\mathbf{x}$의 solution은 알고리즘 혹은 모델로 해석될 수 있다. 

Reference

1. Deisenroth, Marc Peter, A. Aldo Faisal, and Cheng Soon Ong. Mathematics for machine learning. Cambridge University Press, 2020.

2. MIT Lecture by Gilbert Strang [Link]