선형 연립방정식과 역행렬

선형 연립방정식(Systems of linear equations)

* 복수의 미지수를 포함하는 복수의 선형 방정식을 선형 연립방정식 혹은 연립일차방정식이라고 한다.

* M개의 미지수를 가지는 N개의 선형 연립방정식은 다음과 같다.

* 이를 행렬과 벡터의 곱셈으로 표현하면 다음과 같이 표현 가능하다.

* A는 계수행렬(coefficient matrix), x는 미지수 벡터(unknown vector), b를 상수 벡터(constant vector)라고 부른다.

역행렬(inverse matrix)

* 원래의 행렬 A와 위와 같은 관계를 만족시키는 행렬을 역행렬이라고 한다.

* 역행렬이 존재하는 행렬 : 가역행렬(invertible matrix), 정칙행렬(regular matrix), 비특이행렬(non-singular matrix) 라고한다.

* 역행렬이 존재하지 않는 행렬을 : 비가역행렬(non-invertible matrix), 특이행렬(singular matrix), 퇴화행렬(degenerate matrix)

* 대각행렬의 역행렬은 각 대각성분의 역수로 이뤄진 대각행렬과 같음.

역행렬의 성질

* 행렬 A,B,C가 모두 각각 역행렬이 존재할 때

1) 전치 행렬의 역행렬은 역행렬의 전치행렬과 같다. 따라서 전치행렬의 역행렬도 대칭이다.

2) 두 개 이상의 정방 행렬의 곱은 같은 크기의 정방 행렬이 되는데 이러한 행렬의 곱의 역행렬은 다음 성질이 성립한다.

역행렬의 계산

* C는 여인수행렬(cofactor matrix)이다.

* 여인수행렬의 전치행렬 $C^T$를 수반행렬(adjoint matrix)라고 하고 adj(A)라고 한다.

* det(A)=0이면 역행렬이 존재하지 않는다.

역행렬에 대한 정리

1) 셔먼-모리슨(sherman-morrison)공식

* 정방행렬 A와 벡터 u,v에 대해 다음 공식이 성립함

2) 우드베리(Woodbury)공식

* 정방행렬 A와 이에 대응하는 적절한 크기의 행렬 U, V, C에 대해 다음 공식이 성립함.

분할행렬의 역행렬

* 4개 블록으로 분할된 행렬의 역행렬은 각 분할행렬을 이용하여 계산할 수 있다.

* 이 식에서 F는 다음과 같이 주어진다.

넘파이를 사용한 역행렬 계산

import numpy as np

A = np.array([[1,1,0],[0,1,1],[1,1,1]])
Ainv=np.linalg.inv(A)
Ainv

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

역행렬과 선형 연립방정식의 해

* 선형 연립방정식에서 미지수의 개수와 방정식의 수가 같다면 계수행렬은 정방행렬이 된다.

* 만약 계수행렬이 역행렬이 존재한다면 선형 연립방정식의 해는 아래와 같이 구할 수 있다.

선형 연립방정식과 선형 예측모형

* 위와 같은 N차원 벡터를 N개 입력받아 목푯값 벡터를 출력하는 선형 예측모형은 다음과 같이 표현 가능하다.

* X는 계수행렬이고, w는 가중치 벡터, y는 목푯값을 뜻하는 상수 벡터이다.

* 만약 계수행렬 X의 역행렬이 존재한다면 가중치 벡터 w는 다음과 같이 구할 수 있다.

from sklearn.datasets import load_boston
import warnings
warnings.filterwarnings('ignore')

boston=load_boston()
X=boston.data
y=boston.target
A=X[:4, [0,4,5,6]] #column중 CRIM, NOX, RM, AGE 만 사용
b=y[:4]

w=np.dot(np.linalg.inv(A), b)
w
#array([-3.12710043e+02, -1.15193942e+02,  1.44996465e+01, -1.13259317e-01])

* 위 코드는 역행렬의 성질을 이용하여 가중치 벡터 w를 구하는 code이다.

미지수의 수와 방정식의 수가 다를 경우

* 미지수의 수와 방정식의 수가 다를 경우 선형 연립방정식의 계수 벡터를 구하는 방법을 살펴본다.

* 미지수의 수와 방정식의 수를 고려할 때 연립방정식은 다음 세 가지 종류가 있다. 방정식의 수가 N이고 미지수의 수가 M일 때,

1) N=M

* 앞에서 다룬 내용과 같이 역행렬이 존재한다면 역행렬을 통해 계수 벡터를 구한다.

2) N<M

* 위와 같이 방정식의 수 보다 미지수의 수가 적은 경우 무수히 많은 해가 존재하게 된다.

3) N>M

* 위와 같은 식은 해가 하나도 존재하지 않을 수 있다. 위의 3개의 방정식을 만족하는 해는 $x_1=x_2=x_3=1$인데, 이 값은 4번째 방정식을 만족하지 못한다.

* 보통 우리가 마주하게 되는 문제는 3)의 경우가 많다. 예를 들어 면적, 층수, 한강이 보이는지 여부를 통해 예측하는 부동산 가격 예측 모형의 경우 데이터 sample의 개수가 feature 개수보다 많다. 이 경우 선형 연립방정식의 해가 존재하지 않기 때문에 선형 연립방정식을 푸는 방식으로는 해결 불가능하다.

최소자승문제(Least Square Problem)

* 앞서 살펴본 3)의 경우 선형연립방정식의 해를 구하는 방법으로는 문제를 풀 수 없을 수 있다는 것을 확인하였다.

* 이럴 경우 최소자승법을 사용한다.

* 다시 3)의 경우에 해당하는 선형 연립방정식으로 돌아오자. 이 선형 연립방정식의 해는 존재하지 않는다는 것을 확인한 바 있다.

* 하지만, 양 변이 꼭 똑같지 않아도 된다는 가정을 도입하면 해를 구할 수 있다. $x_1=x_2=x_3=1$ 일 때 해는 아래와 같다.

* 좌변을 예측값, 우변을 목푯값이라고 했을 때 마지막 방정식의 예측값이 4로 4.1에 매우 근사하기 때문에 거의 비슷하게 예측했다고 할 수 있다.

* 이러한 idea를 통해 미지수의 개수보다 방정식의 개수가 많아서 선형 연립방정식을 통해 풀 수 없는 문제를 좌변과 우변의 차이를 최소화 하는 해를 찾는 문제로 바꾸어 풀 수 있다.

* 예측값과 목푯값의 차이를 residual이라고 하고 residual e는 $e=Ax - b$ 와 같이 표현할 수 있다.

* 잔차 벡터 $e$의 norm을 최소화 하는 해를 구한다. 이 때 norm을 최소화 하는 것은 norm의 제곱을 최소화 하는 것과 같기 때문에 norm의 제곱을 최소화하기로 한다.

* $ ||e||^2  = E = (Ax - b)^T (Ax - b) = x^T A^T A x - b^T Ax - x^T A^T b + b^T b $ 라고 할 때 arg min x를 찾기 위하여 다음과 같이 x로 미분했을 때 0이되는 해를 찾는다.

* $\frac{dE}{dx} = -2y^T + 0 = 0$

   $ x^T A^T A = b^T A $

   $ A^T A x = A^T b$

   $ x = (A^T A)^{-1} A^T b$

* 결국 최소자승법을 통해 구한 해 x 는 $(A^T A)^{-1} A^T b$ 가 된다는 것을 알 수 있다.

* numpy를 통해 우리가 계산한 방법을 활용해 해를 구해보겠다.

A=np.array([[1,1,0],
            [0,1,1],
            [1,1,1],
            [1,1,2]])
b=np.array([[2],[2],[3],[4.1]])
x=np.dot(np.dot(np.linalg.inv(np.dot(A.T, A)), A.T), b)

pred_b=np.dot(A, x)
pred_b

# array([[1.98333333],
#        [2.        ],
#        [3.03333333],
#        [4.08333333]])

* 우리가 구한 해 x를 계수행렬 A와 곱해 pred_b를 생성하여 보았더니 실제 b값과 매우 유사한 것을 확인할 수 있다.

* 해를 구하는 더 쉬운 방법으로 np.linalg.lstsq() 메소드를 사용하는 것이 있다.

x, resid, rank, s = np.linalg.lstsq(A, b)
pred_b=np.dot(A, x)
pred_b
# array([[1.98333333],
#        [2.        ],
#        [3.03333333],
#        [4.08333333]])

 

연습 문제 2.4.6

* boston 집값 문제를 선형 예측모형 $Xw = \hat{y}$로 풀었을 때의 가중치벡터 $w$를 최소자승법으로 구하라.

from sklearn.datasets import load_boston
boston=load_boston()
X=boston.data
y=boston.target

data=X
x=np.dot(np.dot(np.linalg.inv(np.dot(data.T, data)), data.T), y)
pred_y=np.dot(data, x)
pred_y[:10], y[:10]

# (array([29.09826353, 24.50227548, 31.22742641, 29.7071035 , 29.56479572,
#         25.29376224, 21.53041161, 19.10333426, 11.09336136, 18.25932202]),
#  array([24. , 21.6, 34.7, 33.4, 36.2, 28.7, 22.9, 27.1, 16.5, 18.9]))