1. LU 분해(LU decomposition)
LU분해는 지금까지 배운 가우스 소거법을 알고리즘의 형태가 아닌 행렬의 결과물로 표현하는 방식
가우스 소거법을 프로그래밍적으로 지원하는 알고리즘이 존재
numpy는 LU분해라는 방식으로 제공
1) 행렬분해(matrix decomposition)의 의미
어떤 숫자를 인수분해 한 상태로 가지고 있으면 계산이 편한 경우 많음 ex> 분수의 약분, 최대공약수, 최소공배수...
행렬도 행렬분해한 상태로 가지고 있으면 계산이 편한 경우가 많음
행렬분해의 종류
- LU 분해(LU decomposition)
- QR 분해(QR decomposition)
- 특이값 분해(SVD, Singular Value decomposition)
LU분해는 가우스 소거법을 행렬의 형태로 나타낸 것
2) LU 분해 LU decomposition 란?
- L : lower triangular matrix(하삼각행렬)
- U : upper triangular matrix(상삼각행렬)
LU 분해는 주어진 행렬을 아래의 형태를 가지는 두 행렬의 곱으로 나누는 행렬분해
주어진 행렬 A를 LU 분해했을 때의 장점
Ax=b문제를 아래와 같이 나타내면
Ax = b ->
->
(단, )
선형시스템을 다음과 같이 두 단계로 간단히 해결할 수 있게 됨
- y를 구하는 단계 -> Forward-substitution(전방대치법): y구하기
- x를 구하는 단계 -> Back-substitution(후방대치법): 1번을 통해 구한 y를 이용해 x구하기
3) LU decomposition(LU 분해)의 의미
LU 분해는 가우스 소거법의 forward elimination(전방소거법)을 행렬로 코드화 한 것
- L : 행렬 A를 전방소거하는데 쓰인 replacement와 scaling에 대한 EROs를 기록해 둔 행렬
- U : 행렬 A를 전방소거한 후 남은 upper triangular matrix(상삼각행렬)
- P : 행렬 A를 전방소거하는데 쓰인 interchange에 대한 EROs를 기록해 둔 행렬(옵션)
(그래서 사실 LU분해라고 하면, A = PLU 가 리턴이 된다.)
4) LU decomposition(LU 분해)의 활용
LU 분해는 다음의 이유로 활용된다.
- 수치적 안정성 : 선형시스템 Ax = b의 해를 역행렬 A-1를 이용해 직접 구하는 것 보다 PLU 분해를 이용하는 것이 좀 더 수치적으로 안정적
- b가 자주 업데이트 되는 경우 : 선형시스템 Ax = b 에서 행렬 A는 고정되어 있고 b가 자주 변하는 문제가 종종 있다. 이런 경우, 행렬 A를 미리 PLU로 분해해 둔다면, b가 업데이트될 때마다 선형시스템의 해 x를 실시간으로 구할 수 있습니다. (공학적으로 LU분해를 이용하는 이유)
5) 프로그래밍 실습
파이썬의 numpy, scipy 라이브러리 활용
import numpy as np
import scipy
import scipy.linalg
# 행렬 A 코딩
A = np.array([[3, 1, 1], [1, -2, -1], [1, 1, 1]])
# LU 분해
P, L, U = scipy.linalg.lu(A)
# 검증
AA = P @ L @ U
if np.linalg.norm(A - AA) < 1e-3:
print("Ok")
else:
print("something wrong")
>> Ok
#LU 분해를 활용해 Ax = b 풀기
b = np.array([4, 1, 2])
# LU 분해
lu, piv = scipy.linalg.lu_factor(A)
x = scipy.linalg.lu_solve((lu, piv), b)
#검증
bb = A@x
if np.linalg.norm(b - bb) < 1e-3:
print("Ok")
else:
print("something wrong")
>>Ok
* piv : 최종 permutation matrix
행간 교환 연산을 행렬의 곱으로 만들어주는 역할
2. 행렬연산과 선형조합
1. 행렬 표기법과 관련 용어
1) 행렬이란
행렬(matrix)은 직사각형 구조에 숫자들을 담아 놓은 구조
행렬 안 각 숫자들은 행렬의 요소(entry)
- 행렬 벡터 :하나의 행이나 열을 가지는 특수한 행렬을 각각 행 벡터row vector, 열 벡터column vector라고 한다.
- 스칼라(Scalar) : 1 x 1 행렬
- : m∗n개의 숫자가 직사각형 구조에 채워진 형태
주요 표기법
- 행렬 A의 각 (i, j)요소는 aij로 나타낸다.
- 행렬 A를 간략히 표기할 때 A = [aij]로 나타낸다.
- 행렬 A의 크기가 중요할 경우는A = [aij]m x n로 나타낸다.
2) Transpose Matrix(전치행렬)
m x n 행렬 A에 대한 transpose matrix(전치행렬) AT는 A의 행을 열로, A의 열을 행으로 가지는 n x m행렬이다. 즉, (AT)ij = (A)ij를 만족한다.
3) 벡터 표기법
벡터는 볼드체 소문자 x로 표기한다. 선형대수에서는 벡터라고 하면 보통 열벡터를 가리킴
주요 표기법
- 벡터라고 하면 일반적으로 열벡터(column vector)를 말한다.
- n-벡터는 n개의 스칼라(scalar)로 구성된 열벡터를 말한다.
4) Zero Matrices(영행렬)
행렬의 모든 요소가 0이면, 해당 행렬을 영행렬(zero matrix)라 하고 O로 표기한다.
A + O = O + A = A
- 숫자 세계에서의 0과 같은 존재
- 교환법칙 등 또한 성립
- 행렬합에 대한 항등원 역할
5) Square Matrix(정방행렬) - n x n 행렬
행과 열의 개수가 모두 n인 정사각형(square)모양의 행렬을 n차 square matrix(정방행렬)이라 한다.
특히, aii (i = 1,2,..., n)를 행렬 An의 main diagonal(주대각선)이라 한다.
6) AT(항등행렬)
주대각선(main diagonal)이 1이고 나머지 요소는 모두 0인 n차 정방행렬(square matrix)을 항등행렬(identify matrix)이라 한다.
숫자의 1과 같은 존재
행렬곱에 대한 항등원 역할
7) 행렬의 곱 (중요)
m x r행렬 A = [aij] 와 행렬 B = [bij] 가 있을 때, 두 행렬의 곱 AB는 m x n 행렬 C = [cij] 를 정의한다.
여기서 두 행렬의 곱 AB로 정의된 행렬 C의 각 (i, j)-요소는 다음과 같이 정의된다.
cij = ai1b1j + ai2b2j + ... + airbrj
(A의 행 * B의 열) 즉 내적의 값을 나열한 것이다
행렬의 곱에서 반드시 숙지해야할 사항
- 행렬 C의 각 요소 cij는 ‘곱의 왼쪽 행렬 A의 i번째 행벡터’와 ‘곱의 오른쪽 행렬 B의 j번째 열벡터’의 내적(inner product)이다.
- 따라서, 두 행렬의 곱 AB에 대해 A의 열 개수와 B의 행 개수는 일치해야 한다.
- 일반적으로 AB != BA이다. 왜냐하면 행과 열을 뽑아오는 방법이 다르기 때문이다. 교환법칙이 성립하지 않는다.
- 행렬의 곱은 병렬처리(parallel processing)로 가속할 수 있다. 즉 독립적으로 계산될 수 있다. (중요)
2. 스칼라, 벡터, 행렬, 그리고 텐서: 계층적 구조 이해하기
1) 스칼라 -> 벡터 -> 행렬
- 스칼라는 숫자 하나 : 7
- 이 스칼라를 벡터로 표현하면 1개의 구성요소로 이루어진 1-벡터 : [7]
- 이 스칼라를 행렬로 표현하면 1개의 구성요소로 이루어진 1*1 행렬 : [7]1 x 1
2) 벡터 -> 행렬
벡터는 여러 숫자가 일열로 늘어선 구조이다.
이 벡터를 행렬로 표현하면 여러 모양의 행렬로 표현할 수 있다.
- 4x1 행렬
- 2x2 행렬
- 2x2 행렬의 전치행렬
- 1x4 행렬
표현하고자 하는 행렬의 모양은 응용문제에 따라 결정!
3) 행렬 -> 벡터
행렬은 사각형 구조에 여러 숫자가 행과 열로 늘어선 구조이다.
이 행렬은 다음과 같이 6-벡터로 표현할 수 있다.
행렬을 벡터로 변환할 때, 행부터 혹은 열부터 읽을 것인지는 응용문제에 따라 결정!
4) 텐서
텐서(tensor)는 스칼라, 벡터, 행렬을 아우르는 개념이다. 숫자가 늘어설 수 있는 방향이 k개면 k-텐서로 부른다.
- 0-텐서 : 스칼라 (숫자가 늘어설 수 있는 방향이 없다)
- 1-텐서 : 벡터 (숫자가 늘어설 수 있는 방향이 한 방향이다)
- 2-텐서 : 행렬 (숫자가 늘어설 수 있는 방향이 두 방향이다)
- 3-텐서 : 만일 아래의 T의 각 요소 Pij가 벡터라면, T는 3-텐서로 볼 수 있다.
3-텐서의 대표적인 예는 컬러영상이다. Pij가 3-벡터이면 RGB영상을, 4-벡터이면 RGBA영상을 나타낸다.
3. 분할행렬(Partitioned Matrix)
1) 분항행렬이란?
- 선형대수를 이해하기 위해 가장 중요한 개념
- 행렬을 조각(partition) 단위로 분할하여 생각해도 무방하다.
- --> 행렬은 부분행렬(submatrix)로 이루어진 직사각형 구조로 확장해서 생각할 수 있다.
- 행렬을 구조적으로 보는 방법
- 행렬을 조각조각 분할(행벡터 단위로, 열벡터 단위로, …)해서 계산해도 됨
- 행렬은 행벡터의 모임(->열벡터처럼 보임) / 열벡터의 모임(->행벡터처럼 보임)으로 나타낼 수 있다
- 보통 열벡터의 모임으로 많이 씀
2) 분할행렬로 행렬의 곱 이해하기
두 행렬의 곱 AB = C를 아래와 같이 matrix-column vector products로 볼 수 있다.
AB = A * [b1 b2 ... bn](열벡터의 모임) = [Ab1 Ab2 ... Abn] = C
예를 들면, A2 x 3 B 3 x 2 = C 2x2을 다음과 같이 구조적으로 해석할 수 있다.
A∗[b1b2] = [Ab1Ab2]
두 행렬의 곱 AB = C를 아래와 같이 row vector-matrix products로도 볼 수 있다.
AB = [a1 a2 ... am](행벡터의 모임)*B = [a1B a2B ... amB] = C
예를 들면,A2 x 3 B 3 x 2 = C 2x2 을 다음과 같이 구조적으로 해석할 수 있다.
[a1a2]∗B=[a1Ba2B]
4. 선형조합(Linear Combination): Ax는 A의 열벡터에 대한 선형조합
1) 행렬을 구조적으로 보기
행렬을 숫자들의 모임이 아닌 행렬은 열벡터의 리스트로 보기
ai는 행렬 A의 i-번째 열벡터이다. 특히 각 열벡터는 m-벡터이기 때문에, m x n 행렬은 m-벡터가 n개 있다고 해석한다.
2) 행렬@벡터 연산을 구조적으로 보기
Ax는 행렬 A가 가지고 있는 열벡터의 선형조합이다.
행렬A: m-벡터 n개
x : n- 벡터
--> 스칼라 x 벡터의 곱을 합한 것이 됨
선형대수에서는 이처럼 벡터들에 대한 가중치 합을 선형조합(linear combination)이라 부른다.
Ax의 결과는 행렬 A가 가지고 있는 열벡터의 선형조합으로만 한계가 지어진다.
(좌항을 아무리 복잡하게 만들어도 A의 벡터들의 가중치 합을 벗어날 수 없다)
3) [중요] 선형시스템 Ax = b를 선형조합 관점에서 바라보기
(정리) 선형시스템 Ax=b를 선형조합 관점에서 바라보기
행렬 A의 열벡터를 가중치합으로 선형조합할 때 벡터 b를 만들 수 있는 가중치 조합이 존재한다면, 선형시스템 Ax=b의 해는 존재한다.
그 해는 가중치 xi들로 구성된 x이다.
4) Column Space(열공간)
행렬 A의 열벡터들에 대한 가능한 모든 선형조합의 결과를 모아 집합으로 구성할 수 있을 것이다.
이 집합을 column space(열공간)이라 하고 다음과 같이 표기한다.
col(A)
Consistent Linear System
선형시스템 Ax=b가 해를 가지면 다음을 만족한다.
Consistent Linear System
선형시스템 Ax=b가 r가 없으면 다음을 만족한다.
예제)
위의 행렬의 col(A)은 xy 평면이다.
따라서 xy 평면 상의 3-벡터 b를 이용해 Ax = b를 구성하면, 해당 선형시스템의 해는 존재하지만
xy평면을 벗어난 3-벡터 b를 이용해 선형시스템 Ax = b 를 구성하면, 해당 선형시스템의 해는 존재하지 않는다.
3. 좌표계 변환(Change of Basis): 좌표계::좌표값 = 행렬::벡터
Ax = Ib
A : 좌표계
: 좌표값
: 표준좌표계
b: 좌표값
1) 벡터의 표현
벡터는 크기와 방향을 가진 물리량
1. 벡터의 물리적 표현(좌표계 없는 표현)
벡터 v를 화살표로 표현한다.
- v의 크기 : 화살표의 길이
- v의 방향 : 화살표의 방향
2. 벡터의 수학적 표현(좌표계 있는 표현)
벡터 v를 화살표로 표현한다.
좌표계를 도입한 후, 벡터의 시작점을 원점에 맞추고 끝점의 위치(x,y) 를 벡터 v의 수학적 표현으로 정의한다. (숫자로 계산 가능)
- v의 크기 : 화살표의 길이를 계산
- v의 방향 : 화살표의 방향을 벡터로 표현
2) 좌표계(Coordinate System)
좌표를 쓴다는건 좌표계가 있다는 것
다음과 같이 2-벡터 v가 주어졌다고 하자. 이 벡터는 xy-평면 상에서는 원점 (0, 0)에서 시작하여 (a, b)에서 끝나는 벡터를 의미한다.
v는 다음과 같이 해석될 수 있다.
결과적으로 항등행렬 자체가 직교좌표계를 표현한다고 정리할 수 있다. 그리고 각각의 좌표값은 일종의 각 축에 내린 수선의 발과 의미를 같이한다.
항등행렬을 좌표계로 볼 수 있다면, 다른 행렬 또한 좌표계로 볼 수 있다.
만일 두 벡터 v1과 v2를 이용해 새롭게 좌표계를 만든다면 v의 좌표값은 무엇일까?
새로운 좌표계를 만든다는 말은 어떤 벡터 v에 도착하기 까지의 과정을 오롯이 v1과 v2를 몇번 사용하여 도착했는지로 표현한다는 의미이다.
[v]의 앞에는 사실 항등행렬이 숨겨져 있다.
즉, 좌표계(표준좌표계)가 숨겨져 있다.
위 식의 (좌항)과 (우항)이 표현하는 바는 다음과 같다.
- (좌항) : 과 를 기저(basis)로 가지는 좌표계(coordinate system)에서는 동일한 벡터 의 좌표값은 (4, 3)이다.
- (우항) : 과 를 기저(basis)로 가지는 표준좌표계(standard coordinate system)에서 벡터 v의 좌표값은 (a, b)이다.
3) 좌표계 변환(Change of Basis)
선형시스템(linear system)문제를 좌표계 변환으로 바라보면 다음과 같다.
Ax = b
A는 좌표계이다.
x는 좌표계에 대한 좌표값이다.
b는 좌표값인데
그 앞에 표준좌표계(I, 항등행렬)이 숨겨져 있다.
- (좌항) : A의 열벡터들을 기저(basis)로 가지는 좌표계에서는 동일 벡터의 좌표값은 x이다.
- (우항) : 표준좌표계(standard cordinate system)에서 어떤 벡터의 좌표값은 b이다.
역행렬을 이용해 선형시스템의 해를 구하는 문제 역시 좌표계 변환으로 바라볼 수 있다.
x = A-1b
- (좌항) : 표준좌표계(standard cordinate system)에서 어떤 벡터의 좌표값은 x이다.
- (우항) : A-1의 열벡터들을 기저(basis)로 가지는 좌표계에서는 동일 벡터의 좌표값은 b이다.
--> Ax = b를 기준으로 하면 b 앞에 표준좌표계(항등행렬)이 붙음
역행렬을 하면 x를 기준으로 x 앞에 표준좌표계(항등행렬)이 붙음
--> 동일한 문제이지만 바라보는 관점에 따라 다르게 표현될 수 있다. 선형시스템은 좌표계 변환이라고 해석할 수 있다.
정리
행렬은 좌표계이고, 벡터는 좌표값이다.
임의의 v는 다양한 좌표계에서 표현될 수 있다.
v = A [v]A
v = B [v]B
v: 표준좌표계에 표현된 v
A : 좌표계 A
[v]A: 좌표계 A에서 표현된 v
B : 좌표계 B
[v]B: 좌표계 B에서 표현된 v
[v]A를 구했다는 것은 A라는 행렬이 정의하는 좌표계의 각각의 basis들을 몇번 써서 v라는 지점에 도착할 수 있는지를 구한 것이다.
결론적으로, 좌표계를 행렬로 구성하고, 그 옆에 곱해져있는 벡터를 해당 좌표계에서의 좌표값이라고 할 수 있다.
이와 같은 수식을 통해 A 또는 B 좌표계 기준으로 표준좌표계를 쓸 수 있다.
예제: 좌표계 변환(Change of Basis)
1. 2-벡터 벡터 v가 표준좌표계에서 (2,3)으로 표현된다고 하자. 벡터(3,1)과 (1,-2)를 기저벡터로 가지는 새로운 좌표계를 도입했을 때, 해당 벡터 v는 어떤 좌표값을 가질까?
2. 3-벡터 벡터 v가 표준좌표계에서 (2,1,3)으로 표현된다고 하자. 벡터(1,3,1)과 (1,-2,2)를 기저벡터로 가지는 새로운 좌표계를 도입했을 때, 해당 벡터 v는 어떤 좌표값을 가질까?
(표준좌표계는 3x3인 3차원 좌표계였지만 --> 2차원 좌표계로 변환한 경우)
4. 선형변환(Linear Transformation) : 행렬은 선형함수다. (입력: 벡터 출력: 벡터)
1) 함수 복습
함수의 개념 : 함수는 상자(함)에 입력(input)이 들어가면 어떤 기능을 수행한 다음 출력을 뱉어내는 블랙박스
domain(정의역): 입력이 정의되는 집합 D
codomain(공역): 출력이 정의되는 집합 C
range(치역): codomain 중 실제 함수의 출력이 나오는 부분집합
함수 f는 D의 각 원소 x가 C의 한 원소 y(=f(x))에 대응되는 매핑룰(mapping rule)
f: D -> C
는 domain, codomain이 실수이니까
f: R -> R
로 표시 가능
C-스타일 프로그래밍으로 위의 함수 f를 구현한다면?
입출력으로 실수 집합 R(real number)을 다루는 함수라는 것을 명시하기 위해 입출력 타입을 float으로 한다.
float f ( float x ) { return x*x + 2*x + 3; }
2) 선형함수(Linear Function)와 선형 변환
1. 선형함수
만일 함수 f가 아래 두가지 조건을 만족하면 함수 f를 선형함수(linear function)이라 한다.
(선형함수란? 그려봤을때 직선 형태, 평면 형태)
(단, c는 임의의 스칼라)
- 임의의 두 입력에 대해,
- ‘+연산을 먼저 수행한 결과를 함수 입력으로 넣고 함수를 수행한 결과’와
- ‘각 입력에 대해 함수를 수행한 후 나온 결과에 대해 +연산을 수행한 결과’는 같다.
- 임의의 입력에 대해, ‘
- 스칼라 곱셈 연산을 먼저 수행한 다음 함수를 수행한 결과’와
- ‘입력에 대해 함수를 수행한 후 나온 결과에 대해 스칼라 곱셈 연산을 수행한 결과’는 같다.
2. 선형 변환 변환(Transformation)
함수의 입력이 n-벡터이고 출력이 m-벡터인 함수 T를 생각해 보자.
이와 같이 함수의 입출력이 벡터인 함수를 변환(transformation)라 한다.
T : Rn -> Rm
특별히 n=m인 경우, 해당 변환을 연산자(operator)라고 한다.
변환의 예 : MNIST 손글씨 인식 문제
예를 들어, 28x28 해상도의 손글씨 숫자영상을 그레이스케일로 받아, 0부터 9까지의 어떤 숫자가 적혀있는지 알아내는 MNIST 손글씨 인식 문제는 다음과 같은 (비선형)변환이다. 함수가 아니라 변환이라고 한다.
T: R2 x 28 -> R10
인공지능의 변환은 대부분 선형변환이 아니라 비선형 변환이다.
4) 행렬변환(Matrix Transformation)
m x n행렬 A에 대해 Ax는 n-벡터를 입력으로 받아 m-벡터를 출력으로 내는 변환 TA(x) = Ax 으로 볼 수 있다.
이 변환은 행렬이 정의하기 때문에 행렬변환(matrix transformation)이라고 한다.
TA: Rn -> Rm
그런데 행렬변환은 다음의 선형함수 성질을 모두 만족하기 때문에 선형변환(linear transformation)이다.
TA(x + y) = TA(x) + TA(y)
TA(cx) = cTA(x)
(단, x,y∈Rn이고, c는 임의의 스칼라
TA를 행렬 A라고 생각하고 보면 쉽다. 행렬은 입출력이 벡터이기 때문에 함수 중에서도 특별한 변환(transformation)이 된다. 즉 행렬은 선형변환이다.
정리
mxn 행렬은 n-벡터를 입력으로 받아 m-벡터를 출력으로 내는 선형변환이며, 임의의 선형변환은 행렬로 표현가능하다.
즉, 행렬은 선형변환의 구현체이다.
3) 표준행렬(standard matrix): 선형변환 코딩하기
1. 행렬변환 코딩하기
- 구현하고자 하는 기능(function)의 입력과 출력이 벡터로 정의되는지 확인한다. 벡터가 아니면 변환이 아니기 때문에 행렬로 구현할 수 없다.
- 구현하고자 하는 기능이 선형인지 확인한다.
- 입력이 n-벡터이고, 출력이 m-벡터이면 m x n표준행렬(standard matrix) 을 구성한다.
2. 표준행렬(Standard Matrices)을 이용한 선형변환 코딩
다음의 m x n표준행렬(standard matrix) 을 구성하여 우리가 원하는 방식대로 동작하는 행렬변환 TA: Rn -> Rm을 코딩할 수 있다.
정리 : 표준행렬 구하기
- n-차원 표준기저벡터 생각한다.
- 각 n-차원 표준기저벡터 에 대해, 우리가 원하는 기능을 동작시켜 얻은 결과인 m-차원 벡터 표준행렬의 각 열에 적는다.
예제: 표준행렬(Standard Matrices)을 이용한 선형변환 코딩
1. 2차원 벡터를 입력으로 받아, 해당 벡터를 x-축에 프로젝션(투영)하는 기능을 구현
2. 2차원 벡터를 입력으로 받아, 해당 벡터를 반시계 방향으로 만큼 회전하는 기능을 구현
-> 벡터로 입력받아 벡터로 출력되는지 확인, 선형인지 확인
'Math' 카테고리의 다른 글
책 <인공지능을 위한 수학> 정리 (0) | 2021.05.07 |
---|---|
[AI class day10] 인공지능 수학- 추정, 검정, 엔트로피 TIL (0) | 2021.05.03 |
[AI class day 9] 인공지능 수학- 확률과 확률분포 TIL (0) | 2021.04.29 |
[AI class day 8] 인공지능 수학- 자료의 정리 TIL (0) | 2021.04.28 |
[AI class day 6] 인공지능 수학- 선형대수Linear Algebra TIL (0) | 2021.04.26 |