16 Sat

TIL

[인공지능을 위한 선형대수] CHAPTER 2. 선형시스템 및 선형변환

선형방정식과 선형시스템

선형방정식

• $a_1x_1 + a_2x_2 + ... + a_nx_n = b$

• 이 때 a를 계수, b를 상수라고 하며 x는 우리가 풀어야 할 미지수 또는 변수

이를 다음과 같이 표현 가능하다

• $a^Tx = b$

• 기본적으로 스케일러는 소문자로 표시하고 벡터일 경우에는 볼드체로 표시한다.

• 매트릭스는 대문자로 표시한다.

선형시스템

• 선형방정식의 집합 (연립방정식이라고도 한다)

선형시스템의 예

$60 x_1 + 5.5 x_2 + 1x_3 = 66 \\ 65 x_1 + 5.0 x_2 + 0x_3 = 74 \\ 55 x_1 + 6.0 x_2 + 1x_3 = 78 \\$

이 때, 3개의 연릭방정식은 다음과 같이 쓸 수 있다. 이를 Matrix Equation 이라고 한다.

$\left[\begin{array}{rrr} 60&5.5&1\\ 65&5.0&0\\ 55&6.0&1 \end{array}\right]$$\left[\begin{array}{rrr} x_1\\x_2\\x_3\end{array}\right] = \left[\begin{array}{rrr} 66\\74\\78\end{array}\right]$

또는 다음과 같이 표현할 수 있다

$a^T_1x = 66 \\ a^T_2x = 74 \\ a^T_3x = 78$

항등 행렬 (Identity Matrix)

AB = BA = A 가 되도록 하는 행렬 B를 항등 행렬이라고 표현하며 I 로 표현한다. 정사각행렬에 대해서만 정의할 수 있다.

역행렬 (Inverse Matrix)

$A^{-1}A = AA^{-1} = I_n$

2차 역행렬 같은 경우는 다음과 같은 방법으로 역행렬을 구할 수 있다.

$A^{-1} = \frac {1} {ad-bc} \left[\begin{array}{rrr} d&-b\\ -c&a \end{array}\right]$

3차 이상의 행렬에 대한 역행렬도 2차 행렬의 역행렬 같은 공식은 없지만 알고리즘적으로 풀어낼 수 있는 과정이 존재한다.

역행렬 식을 만족하는 행렬 A는 정사각행렬에 대해서는 항상 만족하지만 직사각행렬에 대해서는 한쪽만 만족한다.

역행렬을 통한 선형 시스템 풀이

$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ A\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x \ \ \ \ \ =\ \ \ \\ \ \ b$

$\left[\begin{array}{rrr} 60&5.5&1\\ 65&5.0&0\\ 55&6.0&1 \end{array}\right]$$\left[\begin{array}{rrr} x_1\\x_2\\x_3\end{array}\right] = \left[\begin{array}{rrr} 66\\74\\78\end{array}\right]$

$A^{-1} = \left[\begin{array}{rrr} 0.0870&0.0870&-0.0870\\ -1.1304&0.0870&1.1314\\ 2.0000&-1.0000&-1.0000 \end{array}\right]$

$x = A^{-1}b = \left[\begin{array}{rrr} 0.0870&0.0870&-0.0870\\ -1.1304&0.0870&1.1314\\ 2.0000&-1.0000&-1.0000 \end{array}\right] \left[\begin{array}{rrr} 66\\74\\78\end{array}\right] = \left[\begin{array}{rrr} -0.4\\20\\-20\end{array}\right]$

이 솔루션의 의미는 주어진 데이터를 만족할 수 있는 x를 찾은 것

(life-span) = -0.4(weight) + 20(height) -20(is_smoking)

역행렬이 존재하지 않은 행렬 A for Ax = b

• 역행렬이 존재할 때의 근은 하나로 특정된다.

• 역행렬이 존재하지 않을 때의 근은 무수히 많거나 존재하지 않는다.

• ad-bc가 0이 될 때 역행렬이 존재하지 않으며 이를 A의 판별자 또는 det A 라고 한다.

• a : b = c : d 의 관계가 만족하면 역행렬이 존재하지 않는다.

직사각행렬 A in Ax = b

방정식의 개수가 m개, 변수가 n개 일 때

• m < n (변수가 더 많을 때) : 무한히 많은 해답이 존재한다. (under-determined system)

• m > n (변수가 더 적을 때) : 완벽히 만족하는 해답은 존재하지 않는다 (over-determined system)

• 그러나 머신러닝에서는 m > n 의 경우더라도 최대한 모든 점을 지나가는 것처럼 보이게 하는 방정식을 구할 수 있다.

실습

from numpy.linalg import solve
x = solve(A, b)
x

다음과 같이 쉽게 구할 수 있는데, 이 때는 역행렬을 이용하여 구하지는 않는다. 왜냐하면

3x = 6 이라는 식에서, x는 당연히 2지만 역행렬을 구하는 과정으로 풀이한다고 할 때,

x = $3^{-1}6$ 이 되며 이 때 3의 역수는 0.33333.. 의 형태를 가지게된다. 결국 이러한 풀이는 컴퓨터의 실수 표현의 한계때문에 아주 적은 오차를 발생하게 되는데, 이것이 행렬간의 역행렬에서도 발생하므로 역행렬을 이용하여 구하지는 않는다.

실습 I

간단한 numpy array

import numpy as np

# column vector
c = np.array([1,2,3])
print(c.shape)

# obtaining a particular entry
print (c[0])

(3,)
1

2차원 numpy array : vector

# row vector
r = np.array([ [1,2,3] ])
print (r.shape)

(1, 3)

색인

# obtaining a particular entry
print (r[0,1])

2

np.zeros, np.ones, np.full, np.random.random

# creating a matrix with all zeros
a = np.zeros((2,2))
print (a)
# creating a matrix with all ones
b = np.ones((2,2))
print (b)
             
# creating a matrix filled with the same constant
c = np.full((2,2), 7)
print (c)
             
# creating a matrix with random values
d = np.random.random((2,2))
print (d)

[[ 0.  0.]
 [ 0.  0.]]
[[ 1.  1.]
 [ 1.  1.]]
[[7 7]
 [7 7]]
[[ 0.93589863  0.19331487]
 [ 0.14309097  0.43003853]]

2차원 numpy array : matrix

# creating a matrix
A=np.array([[1,2],[3,4],[5,6]])
print (A)

[[1 2]
 [3 4]
 [5 6]]

# creating another matrix
B=np.array([[11,12,13,14],[15,16,17,18]])
B

array([[11, 12, 13, 14],
       [15, 16, 17, 18]])

전치행렬

# transpose a matrix
A.T

array([[1, 3, 5],
       [2, 4, 6]])

행렬 곱

# matrix-matrix multiplication
np.dot(A,B)

array([[ 41,  44,  47,  50],
       [ 93, 100, 107, 114],
       [145, 156, 167, 178]])

행렬 곱의 잘못된 예시

# matrix-matrix multiplication 
# size should match!
np.dot(B,A)

---------------------------------------------------------------
ValueError                    Traceback (most recent call last)
<ipython-input-30-1c2410a4aca9> in <module>()
      1 # matrix-matrix multiplication
      2 # size should match!
----> 3 np.dot(B,A)

ValueError: shapes (2,4) and (3,2) not aligned: 4 (dim 1) != 3 (dim 0)

# coefficient matrix A and a vector b
A=np.array([[60, 5.5, 1],[65, 5.0, 0],[55, 6.0, 1]])
b=np.array([66, 70, 78])

항등행렬 eye

# identity matrix 
eye3 = np.eye(3)
eye3

array([[ 1.,  0.,  0.],
       [ 0.,  1.,  0.],
       [ 0.,  0.,  1.]])

역행렬 구하기 numpy.linalg.inv

# computing an inverse
from numpy.linalg import inv
A_inv = inv(A)
A_inv

array([[ 0.08695652,  0.00869565, -0.08695652],
       [-1.13043478,  0.08695652,  1.13043478],
       [ 2.        , -1.        , -1.        ]])

잘못된 행렬 곱 연산. DOT을 사용하지 않고 *을 사용해서 element-wise 방식으로 곱해진다.

# wrong matrix multiplication
A*A_inv

array([[  5.21739130e+00,   4.78260870e-02,  -8.69565217e-02],
       [ -7.34782609e+01,   4.34782609e-01,   0.00000000e+00],
       [  1.10000000e+02,  -6.00000000e+00,  -1.00000000e+00]])

올바른 행렬 곱

# correct matrix multiplication
A.dot(A_inv)

array([[ 1.,  0.,  0.],
       [ 0.,  1.,  0.],
       [ 0.,  0.,  1.]])

행렬과 벡터의 곱

# solution of a linear system
x=A_inv.dot(b)
x

array([ -0.43478261,  19.65217391, -16.        ])

numpy.linalg.solve

# a better way to solve the same linear system
from numpy.linalg import solve
x = solve(A,b)
x

array([ -0.43478261,  19.65217391, -16.        ])

이 때 solve의 계산은 역행렬을 구하는 계산으로 하지 않는다. 역행렬을 구하는 방법은 조그마한 오차를 발생시키기 때문이다.

선형결합

선형 결합에는 벡터 v와 스칼라 c가 주어지며 이 때 스칼라 c를 가중치라고 한다. 이 가중치는 실수 범위 내에 있는 수이며, 0도 당연히 포함된다.

매트릭스 방정식에서 벡터 방정식

매트릭스의 열을 분리해서 다음과 같이 표현할 수 있다.

Span

선형 결합에서 재료벡터(주어진 벡터)를 가지고 임의의 가중치를 곱해 만들 수 있는 모든 선형 결합의 결과물을 의미한다.

위 그림에서 재료벡터는 $v_1$과 $v_2$이며 이 두 재료벡터와 가중치를 이용하여 만들어지는 모든 점의 집합이 Span이다. 위와 같다.

만약 재료벡터가 한개라면?

• Span은 Line

재료벡터가 3개라면?

• Span은 평행사변형의 입체버전!

해의 존재 여부

3개의 재료벡터로 만들어지는 Span 안에 결과벡터가 존재하면 이를 만족하는 가중치가 존재한다.

다수의 방정식으로 인식하는 것이 아니라 벡터 방정식으로 기하학적 해석을 할 수 있다.

위와 같이 6번의 계산을 필요로 하는 선형 방정식으로 볼 수 있지만,

아래와 같이 벡터단위로 분리해서 계산할 수도 있다.

$(Ax)^T = x^TA^T$ 와 같으므로 열벡터의 계산을 행벡터의 계산으로도 바꿀 수 있다.

내적 뿐만 아니라 외적도 벡터로 분리해서 계산이 가능하다.

머신러닝 문제를 해결할 때 지금까지의 과정처럼 행렬을 분리해서 계산하는 방법이 중요하다.

예를 들어 100명의 사람과 50명의 피처가 있는 표가 있다고 할 때, 이는 100명의 사람 열벡터와 50개의 특징 행벡터를 이용하여 표현할 수 있다.

선형독립과 선형종속

만약 Span에 x가 포함된다고 할 때, x는 유일한 가? 아니면 매우 많은가? 에 대한 의문을 가질 수 있다.

이를 설명할 수 있는것이 선형독립과 선형종속(선형의존)

해가 여러개라는 것은 어떤 의미일까?

v1과 v2만으로도 만들 수 있는 span에 v3가 존재한다는 의미

선형 독립

새로운 선형 벡터가 추가될 때 기존에 Span에 추가되지 않으면 선형적으로 독립적이라고 한다

3차원 공간에서 있는 4개의 벡터는 항상 선형 의존이다. (비둘기집 원리와 비슷)

다음과 같이 3차원 공간에서 4개의 벡터가 있을 경우는 해가 무수히 많이 존재한다.

만약 3차원 공간에서 2개의 벡터가 있을 경우는 Case by Case => 선형 의존일수도 독립일수도 있다.

선형 독립 : homogeneous equation

• Ax = b 에서 b가 무엇이든 0이라고 두고 푸는 방정식

• b는 영벡터 O로 대치. 이 때, O가 진한 이유는 벡터이기 때문

• 이 방정식은 해의 존재 유무를 판단할 필요가 없는데 이유는 모든 xv를 0으로 세팅하면 최소한 한 개의 해를 가질 수 있기 때문 => 영벡터를 항상 만들 수 있음

• 해가 1개이냐, 더 존재하는 지를 아는 것이 이 방정식의 목표

• 해가 모두 0인 solution을 trivial solution 이라고 하며 하나라도 0이 아닌 해는 nontrivial solution 이라고 한다.

Two definitions are equvalent

• 0이 아닌 해를 가지는 마지막 벡터에 대한 식으로 다른 벡터를 표현한다. 이 벡터가 나머지 벡터의 Span에 포함되는 지 확인한다.

• 포함 된다면 해를 가진다는 의미. $Span\{v_1, v2, ... v_{n-1}\} = Span\{v_n\}$

0이 아닌 b가 존재할 때는?

• 원점에서 출발해서 b로 도착해야 하는 상황

결론

Ax = b는 언제 하나의 해를 가지는가?

• 하나의 평행사변형으로만 그려질 때

• 이 때를 선형 독립이라고 한다.

부분공간의 기저와 차원

Span and Subspace

• Subset : 부분집합

• Subspace : Span과 비슷하다. 선형 결합에 닫혀있는 subset을 subspace라고 한다.

• subspace는 span의 재료벡터로 항상 표현 가능하다

Basis of a Subspace

한 평면이 주어질 때 중복이 허용되지 않는(Lineary independent) 두 벡터의 Span이 평면을 이룬다면 이 벡터들을 기저벡터라고 한다.

Non-Uniqueness of Basis

이 때 기저벡터는 유니크 하지는 않는다. 여러 기저벡터로 Subspace를 표현할 수 있다.

Dimension of Subspace

서브스페이스의 기저벡터의 개수는 동일하다.

표준 기저 벡터는 길이가 1이고 각 벡터가 수직인 벡터이다. 주로 축을 기준으로 벡터를 설정한다.

Column Space of Matrix

매트릭스의 컬럼에 의한 span은 subspace의 조건을 만족하므로 column space라고 한다.

Matrix with Linearly Dependent Columns

물론 3개의 컬럼이 다 기저벡터가 될 수 있지만 선형 독립관계에 있지 않으므로 2개만 스팬의 기저벡터라고 말한다

Rank of Matrix

랭크는 column space의 개수를 말한다. 즉, 서브스페이스의 차원과 같은 값이며 특히 column space의 개수를 특정해서 말한다.

아무리 매트릭스가 커도 각 column간의 패턴이 있다면 랭크는 크지 않다.

선형변환

Transformation

x를 y로 transform 할 때 다음과 같은 기호를 사용한다.

• domain : 정의역을 의미

• co-domain : 공역을 의미

• image : 함숫값을 의미한다. f(1) = 3 일 때 1의 이미지 값은 3이다.

• range : 치역을 의미. 공역 중 정의역과 매칭 되는 값들의 집합이 치역이다.

• 이 때 x의 이미지 값은 딱 하나일 때 함수라고 정의한다.

Linear Transformation

$f(ax+by) = af(x) + bf(y)$를 만족할 때, 해당 transformation을 선형적이라고 한다.

• $f(x) = 3x + 2$ 와 같은 bias가 존재하는 함수 꼴은 만족하지 않는다

  • $3 \cdot 1 + 4 \cdot 2 = 11$

  • $a = 3, x = 1, b = 4, y = 2$

  • $f(ax+by) = f(11) = 35$

  • $af(x) + bf(y) = 3f(1) + 4f(2) = 15 + 32 = 47 \not= 35$

• 근데 이것을 $\left[\begin{array}{rrr} 3&2 \end{array}\right] \left[\begin{array}{rrr} x\\ 1 \end{array}\right]$로 변환하면 선형 변환을 만족한다

  • $3x + 4y = 3\left[\begin{array}{rrr} 1\\ 1 \end{array}\right] + 4\left[\begin{array}{rrr} 2\\ 1 \end{array}\right] = \left[\begin{array}{rrr} 11\\ 7 \end{array}\right]$

  • $\left[\begin{array}{rrr} 3&2 \end{array}\right] \left[\begin{array}{rrr} 11\\7 \end{array}\right] = 47$

  • $\left[\begin{array}{rrr} 3&2 \end{array}\right] 3\left[\begin{array}{rrr} 1\\ 1 \end{array}\right] + \left[\begin{array}{rrr} 3&2 \end{array}\right] 4\left[\begin{array}{rrr} 2\\ 1 \end{array}\right] = 47$

Matrix of Linear Transformation

1) T는 2차원 실수에서 3차원 실수로의 linear transformation 이다.

2)

다음과 같은 두 가지 단서를 통해 T라는 변환을 완벽하게 파헤칠 수 있다.

선형성과 T의 기저벡터를 가지고 T는 다음과 같의 정의되는 변환이다 라고 말할 수 있다.

=> 선형성을 만족하는 변환은 항상 행렬과 입력벡터의 곱으로만 이루어진 관계로 되어있다.

일반적으로, N차원에서 M차원으로의 선형변환 T는 항상 매트릭스와 벡터의 곱으로 표현된다.

$M \times N$차원의 변환 T의 매트릭스 인자는 다음과 같이 표현된다. 이 때 이 A를 선형 변환 T의 기준 행렬이라고 한다.

선형변환 with Neural Networks

정사각형의 모눈 종이를 평행사변형의 모눈 종이로 바꿔주는 것이 선형변환

Affine Layer in Neural Networks

y = 3x + 5 처럼 bias term 이 존재하는 경우 Affine Layer라고 하는데, 이 때도 단지 1로 이루어진 벡터를 추가해줌으로써 Linear 하게 transform 할 수 있게 된다.

전사함수와 일대일함수

ONTO and ONE-TO-ONE

• ONTO : 공역 = 치역

  • 정의역의 개수가 공역보다 많아야 한다. (필요조건)

  • 2차 -> 3차로 선형 변환은 ONTO가 절대 될 수 없다.

  • 인코딩 : 입력벡터가 더 크다

  • 디코딩 : 출력벡터가 더 크다

• ONE TO ONE : 일대일 함수

  • 정의역 = 공역

  • 3차 -> 2차로 선형 변환은 ONE TO ONE이 절대 될 수 없다.

  • 선형 변환 T의 기저 벡터가 선형 독립이면 일대일 함수이다.

Neural Network Example

(단, Non-Linear은 생략)

• T1은 3차원 -> 2차원 이므로 ONE TO ONE은 아니다