가우스-조르당 소거법과 여러 가지 행렬

가우스-조르당 소거법: 체계적으로 정답을 찾아내는 알고리즘 #

가감법을 컴퓨터의 언어로 #

중학교 수학 시간에 연립방정식을 풀던 때를 떠올려보면 두 수식을 더하거나 빼서 변수 하나를 소거하고 남은 변수값을 구한뒤 다시 대입하는 방식인 가감법을 사용했다.

예를들어 다음과 같은 연립방정식이 있다.

우리는 1식에서 2를 곱한뒤 ($2x + 4y = 16$), 2식에서 빼주어서 $x$를 없앴고

$y = 3$을 1식에 대입하면 $x = 2$라는 정답을 얻는다.

이 방식은 식 2~3개일때는 손쉽게 풀 수 있지만, 미지수가 1,000개, 식이 1,000개 라면 어떻게 해야할까?

사람이 일일이 어떤식에 무엇을 곱해서 뺄지 판단하는것은 불가능하다. 컴퓨터가 미지수의 개수와 상관없이 기계적(알고리즘으로)으로 순서대로 처리할 수 있는 표준화된 절차가 필요하다.

이 절차가 바로 가우스-조르당의 소거법 (Gauss0Jordan Elimination) 이다.

버튼 3개만 써서 복잡한 숫자판을 깔끔하게 정돈하는 퍼즐 게임 같은거라고 보면된다

친구랑 보드게임을 하고 있다고 생각해보자 게임의 목표는 아래처럼 엉켜있는 숫자판을 대각선만 1이고 나머지는 0인 깔끔한 모양으로 만드는 것이다.

[ 1  2 |  8 ]   ───(퍼즐 조작)───►   [ 1  0 |  2 ]  ->  x = 2
[ 2  5 | 19 ]                         [ 0  1 |  3 ]  ->  y = 3

1. 줄 바꾸기 버튼: 1번 줄과 2번 줄의 위치를 서로 바꾼다.
2. 배수 곱하기 버튼: 한 줄 전체 숫자에 2나 3을 곱한다.
3. 줄끼리 빼기 버튼: 1번 줄에 2를 곱한 결과를 2번 줄에서 빼버린다.

이 3가지 버튼만 순서대로 잘 눌러서 왼쪽을 [1 0 / 0 1] 모양으로 만들어내면, 맨 오른쪽에 남는 숫자 2와 3이 바로 우리가 찾던 답($x=2, y=3$)이 된다. 이 정해진 규칙대로 퍼즐을 푸는 과정이 가우스 조르당 소거법이다.

덧붙인 행렬과 기본행 연산 (위의 비유 전문적인 설명) #

가우스-조르당 소거법을 시작하기 위해, 우선 계수 행렬 $A$와 결과 벡터 $\mathbf{b}$를 하나로 덧붙인 행렬 Augmented Matrix를 만든다.

이 행렬이 변형시킬때, 우리가 사용할 수 있는 규칙은 3가지 뿐이다. 방정식의 해를 변하지 않게 유지하면서 행을 바꾸는 이 연산들을 기본 행 연산 ELementary Row Operation, ERO라고 부른다.

1. 행 교환: 두 행의 위치를 서로 바꾼다. 식의 순서를 바꿔도 해는같다.
2. 행 스칼라 곱: 한 행 전체에 0이 아닌 숫자를 곱한다. (양변에 같은 수를 곱해도 해는 같다.)
3. 행 가감(더하기/빼기): 한 행에 특정 숫자를 곱한 결과를 다른 행에 더하거나 뺀다 (두 식을 더하거나 빼도 해는 같다.)

수학적 원리 #

위에서 말한 3가지 퍼즐 버튼을 수학에서는 기본 행 연산 Elementary Row Operation 이라고 부른다.

계수와 결과값을 합쳐놓은 표를 덧붙인 행렬 Augmented Matrix라고 한다.

• 1단계 (2행 1열을 0으로 만들기):(2행) $-$ $2 \times$ (1행) 을 계산.
  \left[\begin{array}{cc\|c} 1 & 2 & 8 \\ 0 & 1 & 3 \end{array}\right]
• 2단계 (1행 2열을 0으로 만들기):(1행) $-$ $2 \times$ (2행) 을 계산.
  \left[\begin{array}{cc\|c} 1 & 0 & 2 \\ 0 & 1 & 3 \end{array}\right]

왼쪽이 대각선만 1인 단위행렬이 되었으므로 x = 2, y = 3 이라는 최종 해를 얻게 된다.

AI에서 가우스 소거법의 의미 #

컴퓨터는 사람처럼 이 식에서 x를 넘겨볼까? 하고 고민할 수 없다.

대신 가우스 소거법처럼 1열부터 차례대로 0으로 만들어라라는 정해진 알고리즘을 수행한다.

수백만개의 미지수를 가진 AI 선형 시스템을 풀 때, 컴퓨터 내부에서는 이퍼즐 연산을 수십억번 반복하여 최적의 정답을 찾아낸다.

역행렬: 원상복구 Ctrl + Z 시키는 행렬 #

실수로 지운 글자를 돌려놓는 Ctrl + Z 버튼같은건데

일반 숫자 세계에서는 곱했던것을 원상복구시키려면 나눗셈을 한다.

• 5에서 2를 곱하면 10이 된다 5 x 2 = 10
• 다시 원래대로 돌리려면 2의 역수인 $\frac{1}{2}$을 곱해준다. ($10 \times \frac{1}{2} = 5$)

행렬의 세계에는 나눗셈이 없다. 대신 어떤 행렬 A가 데이터를 변형시켜놓았을때 그것을 완벽하게 원래 상태로 돌려놓는 되돌리기 패스워드 같은 행렬이 존재하는데 이를 역행렬 ($A^{-1}$)이라고 부른다.

[원본 데이터] ─── (행렬 A 곱하기) ───► [암호화된 데이터] ─── (역행렬 A⁻¹ 곱하기) ───► [원본 데이터 복원]

그렇다면 모든 행렬은 되돌리기 (역행렬)이 가능할까? #

종이 상자 하나고 있다고 해보자

상자를 살짝 접었다면 다시 펼쳐서 원상복구가 가능하다.

하지만, 상자를 발로 쾅 밟아서 납짝하게 만들면 상자 안에 무엇이 들어있는지 절대 되돌릴 수 없다.

수학에서도 데이터를 차원 아래로 납작하게 눌러버리는 행렬은 역행렬이 존재하지 않으며 이를 특이 행렬 Singular Matrix라고 부른다.

수학적 원리 #

어떤 행렬 A와 그 역행렬 $A^{-1}$ 을 곱하면 아무것도 변하지 않는 단위행렬 I가 된다.

$2 \times 2$ 행렬 $A = \begin{bmatrix} a & b \\ c & d \end{bmatrix}$ 가 있을 때, 역행렬이 존재하는지 판별하는 기준값을 행렬식(Determinant)이라고 한다.

$$\text{행렬식 } \det(A) = ad - bc$$

• $\det(A) \neq 0$ 일 때: 역행렬이 존재합니다.
  $$A^{-1} = \frac{1}{ad - bc} \begin{bmatrix} d & -b \\ -c & a \end{bmatrix}$$
• $\det(A) = 0$ 일 때: 상자가 납작해진 상태이므로 역행렬이 존재하지 않는다.

이론적으로 A\mathbf{x} = \mathbf{b}$의 답은$\mathbf{x} = A^{-1}\mathbf{b}$로 구하지만

Python/PyTorch 코드에서 inv(A) 함수로 역행렬을 직접 구하는 일은 거의 없다.

컴퓨터가 역행렬을 직접 계산하는 것은 연산량이 너무 많고 미세한 소수점 오차가 쉽게 쌓이기 때문이다.

대신 앞으로 배운 소거법 방식으로는 내부적으로 사용하는 p.linalg.solve(A, b) 함수를 사용하는 것이 훨씬 빠르고 정확하다.

여러 가지 행렬 #

1. 전치행렬 ($A^T$) #

스마트폰을 가로로 들고 보다가 세로로 돌리는 것처럼, 행렬의 행과 열을 서로 바꾸는 연산

.

2. 대각행렬 ($D$) #

대각선 위치에만 숫자가 있고 나머지 칸은 전부 0인 행렬.

• 왜 좋을까?: 일반 행렬은 곱셈할 때 계산이 복잡하지만, 대각행렬끼리는 대각선 숫자에 있는 값끼리만 곱하면 끝. 컴퓨터가 연산할 때 메모리와 시간을 엄청나게 아낄 수 있습니다.

3. 직교행렬 ($Q$): #

직교행렬은 전치행렬($Q^T$)을 취하기만 하면 바로 역행렬($Q^{-1}$)이 되는 아주 신기하고 유용한 행렬이다.

3D 캐릭터를 모델링할때 캐릭터 팔이나 다리모양을 찌그러트리지 않고도 각도만 360도 회전시킬때 사용하는 회전도구같은거라 보면 된다.