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]

1. Introduction

[Problem]: Online Class-Incremental Continual Learning

[Dataset]: Non-i.i.d streaming data (각 샘플은 한번만 보여짐)

[Approach]: Replay method

[Main Issue]:

• 제한된 replay buffer로 인한 오래된 클래스들과 최근 클래스들 사이의 imbalance
• 특히, softmax 분류기와 FC layer는 class imbalance에 심각하게 영향을 받음
  - Recency Bias : 모델이 최근 클래스들에 편향되게 학습되는 경향이 있음

[Contribution]:

• Softmax classifier의 결점들을 해결하기 위해 NCM을 사용
• NCM의 정확도 향상을 위해 supervised contrastive learning을 experience replay-based training과 결합

2. Method

2.1. Softmax Classifier vs. NCM Classifier

Softmax classifier

Neural networks에서 cross-entropy loss와 함께 흔히 사용되는 Softmax classifier는 다음과 같은 결점들을 가진다.

• Architecture modification for new classes: 새로운 클래스가 들어오면 training을 멈추고 FC layer에 출력 노드 및 해당하는 connections을 추가해야한다.
• Decoupled representation and classification: 위와 같은 이유로 encoder와 분류 layer를 따로 학습시켜야 함
• Task-recency bias: 모델이 최근 클래스들에 편향되게 학습되는 경향이 있음

Nearest Class Mean (NCM) Classifier

Embeding network $f$가 training된 후, NCM은 1) 각 클래스의 평균 벡터 or prototype을 계산하고, 2) 새로운 샘플 $x$에 대해 그것의 임베딩을 모든 prototype들과 비교한뒤 가장 비슷한 것의 클래스로 할당한다:

$$\begin{equation} \mu_c = \frac{1}{n_c} \sum_i f(x_i) \cdot 1\{y_i=c\} \end{equation} \tag{1}$$

$$\begin{equation} y^\ast = \arg\min_{c=1,...,t} \| f(x) - \mu_c \| \end{equation} \tag{2}$$

여기서 $1\{y_i=c\}$는 $y_i = c$에 대한 indicator이다.

NCM의 이점

• 새로운 클래스가 더해질 때 FC layer의 추가 혹은 수정을 요구하지 않음
• Eq. (1)에서, 인코더의 변화에 따라 prototype도 알아서 변하므로 거리 계산만 하면 됨
• NCM 분류기는 FC layer를 포함하지 않으므로 task-recency bias가 덜함

2.2. Supervised Contrastive Replay

Supervised Contrastive Learning (SCL)

NCM의 정확도 향상을 위해, SCL을 적용 (같은 클래스는 가깝게, 다른 클래스는 멀게 보일 수 있도록 학습)

SCL은 세가지 메인 컴포넌트들로 구성된다.

1. $Aug(\cdot)$은 데이터 샘플 $x$의 augmented view $\tilde{x}$를 생성, i.e., $\tilde{x}=Aug(x)$.
2. Encoder network $Enc(\cdot)$은 $x$를 embedding $r$로 매핑, i.e., $r=Enc(x) \in \mathbb{R}^{D_E}$.
3. Projection network $Proj(\cdot)$은 $r$을 projected vector $z$로 매핑, i.e., $z=Proj(r) \in \mathbb{R}^{D_P} $

b개의 샘플들을 가진 batch $B = \{x_k,y_k\}_{k=1,...,b}$가 주어지면, 2b개의 샘플을 가진 multiviewed batch $B_I=B\cup \tilde{B}$가 생성, 여기서 $\tilde{B} = \{ \tilde{x}_k=Aug(x_k), y_k \}_{k=1,...,b}$.

SCL loss는 다음과 같이 계산된다.

$$\begin{equation} \mathcal{L}_{\text{SCL}}(Z_I) = \sum_{i\in I} \frac{-1}{\vert P(i) \vert} \sum_{p\in P(i)} \log \frac{\text{exp}(z_i \cdot z_p / \tau)}{\sum_{j\in A(i)} \text{exp}(z_i \cdot z_j / \tau) } \end{equation} \tag{3}$$

여기서 $I$는 $B_I$의 indices set이고, $A(i)=I\setminus\{i\}$는 $B_I$에서 샘플 i를 제외한 모든 샘플의 indices set이다.

$P(i) \equiv \{ p \in A(i) : y_p=y_i \}$는 $A(i)$에서 샘플 i와 같은 labels을 가진 샘플들 (positives)의 집합이다.

$Z(i) = \{z_i\}_{i \in I} = \{ Proj(Enc(x_i)) \}_{i \in I}$이고, $\tau \in \mathbb{R}^+$는 temperature parameter이다.

→ positives과의 내적이 negative와의 것보다 크도록 학습된다.

Supervised Contrastive Replay (SCR)

• Training step: 1) data stream $\mathcal{S}$에서의 minibatch $B_n$과 memory buffer $\mathcal{M}$에서의 minibatch $B_{\mathcal{M}}$은 결합되고, augmented view를 생성한다. 2) input batch와 augmented view는 shared encoder와 projection head에 의해 인코딩되고 SCL에 의해 encoder와 projection은 업데이트된다. 3) $B_n$은 memory buffer $\mathcal{M}$로 업데이트 된다.
• Test step: 1) 모든 buffered 샘플들은 encoder에 의해 임베딩되고 prototypes을 계산하는데 사용된다. 2) 임베딩 공간에서 NCM 분류기가 수행된다.

Training 이후 메모리 버퍼 $\mathcal{M}$에서 데이터 임베딩들의 시각화는 다음과 같다.

Cross-entropy loss를 사용하는 기존 방법들과 달리 contrastive loss를 사용하는 방법이 클래스들을 더 잘 구별할 수 있는 임베딩 공간을 찾는다. → Distance metric learning

Run time이 그렇게 빠르지는 않다. (e.g. encoder network가 업데이트 될때마다 클래스 평균 다시 계산 하는 등)

→ 임베딩 공간의 효율적인 학습 전략이 필요할 듯 하다.

본 논문 링크: [Link]

1. Introduction

[Problem]: NCM 분류기의 정확도를 향상시키기 위해 값비싼 계산 과정 없이 non-linear deep representations을 학습하는 것

[Approach and Contribution]:

1. Distance metric을 학습시키는 것 대신 deep representation을 학습
2. representation을 업데이트 할때마다 클래스 평균을 다시 계산하는 과정을 approximation

논문 링크: [Link]

2. Deep Nearest Mean Classification

NCM은 각 이미지를 가장 가까운 평균을 가진 클래스로 할당한다.

$$\begin{equation} y^\star = {\arg\min}_{y \in \{1,...,Y\}} d(x,\mu_y) \end{equation} \tag{1}$$

이전 포스팅 참고 [Link] - [TPAMI 2013] Distance-Based Image Classification: Generalizing to New Classes at Near-Zero Cost

위 포스팅의 방법과 같이 고정된 표현에 대해 마할라노비스 척도 $W$를 학습하는 것 대신, 이 논문에서는 a deep representation $\phi(\cdot)$의 파라미터들을 학습한다.

이 논문의 아이디어는 비선형 딥 표현을 잘 학습한다면, 선형 척도 $W$를 학습할 필요없이 유클라디안 거리를 사용해도 충분하다는 것이다.

즉,

$$\begin{equation} d^\phi_{xy} = (\phi(x) - \mu^\phi_y)^\top (\phi(x) - \mu^\phi_y), \quad \mu^\phi_y=\frac{1}{N_y} \sum_{i:y_i=y} \phi(x_i) \end{equation} \tag{2}$$

여기서 $\phi(x)$는 convolutional layer 등이 사용될 수 있다.

이 때, 문제는 $\phi(x)$가 업데이트 될때마다 클래스 평균을 다시 계산해야한다는 것이다.

2.1. Mean Updates per Batch

계산 비용을 줄이기 위해, 클래스 평균들의 online estimate를 사용한다.

$$\begin{equation} \mu^\phi_{y_i} \gets \frac{n_{y_i}}{n_{y_i}+1}\mu^\phi_{y_i} + \frac{1}{n_{y_i}+1} \phi (x_i) \end{equation} \tag{3}$$

여기서 $n_{y_i}$는 클래스 $y_i$에 속하는 샘플들의 수이다.

즉, 각 배치에 대한 $\phi(x_i)$만 계산하면 된다.

위의 online mean방법을 더욱 향상시키기 위한 두가지 방법 또한 소개되었다.

Mean Condensation: 학습되는 표현이 지속적으로 변하므로, 최근에 들어오는 예제들에 더 많은 가중치를 할당한다.

이를 위해 각 epoch의 시작에서, $n_y = 1 \forall y \in Y$로 설정한다. 

즉 historical 클래스 평균들은 현재 epoch에서 싱글 데이터 포인트로써 카운트된다.

Decay Mean: epoch마다 평균을 다시 설정하는것 대신, 다음과 같이 decay scheme을 사용한다.

$$\begin{equation} \mu^\phi_{y_i} \gets \alpha \mu^\phi_{y_i} + (1-\alpha) \phi (x_i) \end{equation} \tag{4}$$

실제 구현에서는 single example $\phi(x_i)$대신 batch mean $\mu^\phi_{B_y}$를 사용한다.

3. Experiments

1. Introduction

[Problem]: Tiny device위에서 정확한 실시간 예측이 가능한 kNN

[Target Device]: $\leq$ 32kB RAM, 16MHz processor를 가진 IoT 디바이스

[Approach]: k-Nearest Neighbor (kNN)

• (kNN의 이점): tiny 디바이스에서 쉬운 구현, overfitting에 강함, 해석이 용이
• (kNN의 결점): a) Poor accuracy, b) Model size (예측하기 위해 전체 training data를 요구하므로) c) Prediction time (각 test instance에 대해 모든 training data와의 거리를 계산하므로)

[Contribution]:

• Sparse low-d projection: trainable sparse projection matrix를 사용하여 정확도를 보존하면서 전체 데이터를 저차원으로 projection
• Prototypes: 전체 트레이닝 데이터셋을 표현하기 위한 'prototypes'을 학습
• Joint optimization: 주어진 모델 사이즈 내에서 최적 모델을 얻을 수 있도록 최적화 과정에서 sparcity constraints을 부과

2. Problem Formulation

$n$개의 데이터 점들과 해당하는 label or class들을 각각 $X=[x_1,x_2,...,x_n]^T, x_i \in \mathbb{R}^d$와 $Y=[y_1,y_2,...,y_n]^T, y_i \in \mathcal{Y}$라고 하자.

kNN 예측 함수의 a smooth version으로써 다음을 고려하자.

$$\begin{equation} \hat{y}= \rho(\hat{s}) = \rho \left( \sum^n_{i=1} \sigma (y_i) K(x,x_i) \right) \end{equation} \tag{1}$$

여기서 $\hat{s}$는 score vector이고, $\rho: \mathbb{R}^L \to \mathcal{Y}$는 score vector를 출력 공간으로 mapping한다 (single-label이면 best score를 가진 클래스만 1로).

$\sigma:\mathcal{Y} \to \mathbb{R}^L$은 반대로 ground-truth를 score vector와 같은 차원으로 매핑한다.

$K: \mathbb{R}^d \times \mathbb{R}^d \to \mathbb{R}$는 두 점사이의 similarity function이다. (such as $l_2$ distance)

전체 트레이닝 셋의 효율적인 표현으로써 학습할 prototypes을 $B=[b_1,...,b_m]$라 하고, 해당하는 score vectors $Z=[z_1,...,z_m] \in \mathbb{R}^{L \times m}$라고 하자.

결과적으로 decision function은 $ \hat{y}=\rho \left( \sum^m_{j=1} z_j K(x,b_j) \right) $로 주어진다.

또한 전체 데이터를 저차원으로 projection하기 위해 추가적인 matrix $W \in \mathbb{R}^{\hat{d} \times d}$를 사용한다.  (Distance Metric Learning으로 볼 수 있음)

따라서 Eq. (1)은 다음과 같이 쓰여질 수 있다.

$$\begin{equation} \hat{y}= \rho \left( \sum^n_{j=1} z_j K(Wx,b_j) \right) \end{equation} \tag{2}$$

여기서 $b_j \in \mathbb{R}^{\hat{d} \times m}, z_j \in \mathbb{R}^{L \times m}$이다.

이 논문에서는 similarity function으로써 다음과 같이 가우시안 커널을 사용하였다.

$$\begin{equation} K_\gamma = \text{exp} (-\gamma^2 \| x-y \|^2_2) \end{equation} $$

이제 $Z, B, W$를 어떻게 학습할 것인지에 대해 살펴보자.

각 샘플에 대한 loss function을 $\mathcal{L}(\hat{s}, y)$라 하면 (실험에서는 squared $l_2$ loss function 사용),

Empirical risk는 다음과 같이 정의된다.

$$\begin{equation} \mathcal{R}_{emp} (Z,B,W) = \frac{1}{n} \mathcal{L} \left( y_i, \sum^m_{j=1} z_j K_\gamma (b_j, Wx_i) \right) \end{equation} \tag{3}$$

결과적으로 목적 함수는 sparsity constraints을 부과하는 것에 의해 다음과 같이 정의된다.

$$\begin{equation} \min_{Z:\|Z\|_0 \leq s_Z, B:\|B\|_0 \leq s_B, W:\|W\|_0 \leq s_W} \mathcal{R}_{emp} (Z,B,W) \end{equation} \tag{4}$$

여기서 $\| Z \|_0$은 $Z$내에 zon-zero entries의 수이며 사용자 파라미터 $s_Z$에 의해 sparsity constraint를 가진다.

3. Algorithm

Eq. (4)는 non-convex이므로 이 논문에서는 $Z,B,W$를 한개씩 번갈아가면서 (다른 두개의 파라미터를 고정시켜놓고) 업데이트 한다.  

각각의 파라미터를 최적화하는 것 또한 non-convex이므로 projected SGD를 사용하여 업데이트 한다.

$B, W$를 고정시키고 $Z$에 관해 목적 함수를 최적화한다고 가정하자.

Mini-batch $S$에 대해 $Z$는 다음과 같이 업데이트 된다.

$$\begin{equation} Z \gets HT_{s_Z} \left( Z- \eta \sum_{i \in S} \bigtriangledown_Z \mathcal{L}_i(Z,B,W) \right) \end{equation} $$

여기서 $HT_{s_Z}(A)$는 $A$에서 가장 큰 $s_Z$개의 entries만 남기고 zero로 설정하는 hard thresholding operator이다.

결과적으로 최적화 과정은 다음과 같다.

제안하는 방법의 수렴 분석 및 자세한 실험들은 본논문 참고 [Link]

1. Introduction

[Dataset]: ImageNet-10K

[Problem]: Class-Incremental Learning at near-zero cost

[Approach]: Distance-based classifiers

• k-Nearest Neighbor (kNN) classifier
• Nearest Class Mean (NCM) classifier

이러한 분류기들의 성능은 distance metric에 상당히 의존적이므로 이 논문에서는 모든 클래스들에서 공유되는 low-rank 마할라노비스 거리를 학습하는 것을 중점적으로 다룬다.

[Contribution]:

• NCM 분류기를 위한 metric learning 알고리즘 제안
• 효율성 향상을 위해 low-rank 마할라노비스 거리 도입

2. The Nearest Class Mean Classifier

$d(x, \mu_c)$를 image $x$와 클래스 평균 $\mu_c$사이의 유클리디안 거리라고 하자.

NCM은 입력 $x$를 가장 가까운 클래스 평균을 가진 대응되는 클래스 $c^{\ast} \in \{1,...,C\}$로 다음과 같이 할당한다.

$$\begin{equation} c^{\ast}=\text{argmin}_c d(x, \mu_c)  \tag{1} \end{equation}$$

$$\begin{equation} \mu_c = \frac{1}{N_c} \sum_{i:y_i=c} x_i \tag{2} \end{equation}$$

여기서 $y_i$는 ground-truth, $N_c$는 각 클래스에 해당하는 instances의 수이다.

2.1. Metric Learning for the NCM Classifier

이 섹션에서는 제안된 Nearest Class Mean Metric Learning (NCMML)을 소개한다.

Eq. (1)에서 유클리디안 거리는 trainable 마할라노비스 거리로 대체된다:

$$ \begin{equation} d_{M}(x, x')= (x - x')^\top M (x - x') \end{equation} \tag{3}$$

여기서 $x$와 $x'$는 D-차원 벡터들이고 $M$은 positive definite matrix이다.

계산 및 메모리 효율성 향상의 목적으로 위의 그림과 같이 입력들을 (클래스들을 잘 분리해낼 수 있는) 저차원 공간에 projection시키기 위해 $M$을 low-lank metrics로 쪼갠다.

즉, $M=W^\top W$, $W \in \mathbb{R}^{d \times D}$, $d \leq D$.

$$ \begin{align} d_{W}(x, x')&= (x - x')^\top W^\top W (x - x') \\ &= \| Wx-Wx' \|^2_2 \\ \end{align} \tag{4}$$

Eq. (4)는 W를 통해 입력공간을 저차원 공간으로 linear projection한 뒤 squared $l_2$ norm을 구하는 것과 동일하다.

이를 토대로 NCM 분류기는 다음의 확률 모델을 사용하여 각 클래스를 분류한다.

$$ \begin{equation} p(c \vert x)= \frac{\text{exp}(-\frac{1}{2}d_W(x, \mu_c))}{\sum^C_{c'=1}\text{exp}(-\frac{1}{2}d_W(x, \mu_{c'}))}  \end{equation} \tag{5}$$

Projection 행렬 $W$를 학습하기 위해 다음과 같이 목적함수를 log-likelihood로 정의하고 이를 최적화하기 위한 grandient를 계산한다.

$$ \begin{equation} \mathcal{L}=\frac{1}{N} \sum^N_{i=1}\text{ln} \; p(y_i \vert x_i)   \end{equation} \tag{6}$$

$$ \begin{equation} \bigtriangledown_W \mathcal{L}=\frac{1}{N} \sum^N_{i=1} \sum^C_{c=1} \alpha_{ic} W z_{ic}z_{ic}^\top \end{equation} \tag{7}$$

여기서 $\alpha_{ic}=p(c \vert x_i)- [y_i=c]$, $z_ic=\mu_c - x_i$이다. ($[\cdot]$은 Iverson bracket)

2.2. Nonlinear NCM with Mulitple Class Centroids

이 섹션에서는 클래스 평균만 사용하는 것 대신 centroids의 집합을 사용하여 각 클래스를 표현하는 것에 의해 NCM을 비선형 분류기로 확장한다.

각 클래스 $c$에 대해 $k$개의 centroid들의 집합 $\{m_{cj}\}^k_{j=1}$이 있다고 하자.

각 클래스의 사후 확률은 다음과 같이 정의된다.

$$ \begin{equation} p(c \vert x)= \sum^k_{j=1} p(m_{cj} \vert x)   \end{equation} \tag{8}$$

$$ \begin{equation} p(m_{cj} \vert x) = \frac{1}{Z} \text{exp} \left( -\frac{1}{2} d_W(x,m_{cj}) \right) \end{equation} \tag{9}$$

여기서 $Z$는 normalizer이며, 각 클래스의 centroids을 얻기 위해 k-means clustering을 사용한다.

2.3. Alternative Objective for Small SGD Batches

Eq (7)에서 gradient를 계산하는 것은 매 업데이트마다 Eq (4)를 $N \times C$번 계산해야하기 때문에 값비싸다.

Eq (5)에서 $-\frac{1}{2}d_W(x, \mu_c)$는 다음과 같이 계산된다.

$$ \begin{equation} -\frac{1}{2}\| Wx \|^2_2 -\frac{1}{2}\| W \mu_c \|^2_2 + x^\top W^\top W \mu_c \end{equation}$$

여기서 첫번째 항은 클래스 $c$를 분류하는 것과 관련이 없으므로 제거될 수 있다.

그러므로 Eq (5)는 다음과 같이 negative dot-product와 class-specific bias의 합으로 나타낼 수 있다.

$$ \begin{align} p(c \vert x_i) &= -\frac{1}{Z} \text{exp} ( x_i^\top W^\top W \mu_c + s_c) \\ s_c&=-\frac{1}{2}\| W \mu_c \|^2_2 \\ \end{align} \tag{10}$$

결과적으로, 새로운 클래스가 들어오면 그것에 대한 평균만 계산하여 간단히 일반화 할 수 있다.

3. K-NN Metric Learning

위의 소개된 MCMML과의 비교를 위해 Large Margin Nearest Neighbor (LMNN) classification 방법을 약간 수정하여 사용하였다.

LMNN은 지난 포스트 [Link]에서 짧게 다루었다.

자세한 실험 결과들은 본 논문 참고 [Link]