다운로드
작성자: admin 작성일시: 2016-05-16 23:14:40 조회수: 5734 다운로드: 291
카테고리: 기초 수학 태그목록:

연립 방정식과 역행렬

선형 예측 모형은 입력 데이터 벡터와 가중치 벡터의 내적으로 계산된 예측값이 실제 출력 데이터와 가장 비슷해지는 모형이다. 그럼 이 때 가중치 벡터는 어떻게 구할 수 있을까? 여기에서는 연립 방정식과 (의사) 역행렬을 이용하여 선형 예측 모형의 가중치 벡터를 구하는 방법을 알아본다.

선형 연립 방정식

$x_1, x_2, \cdots, x_M$ 이라는 $M$ 개의 미지수를 가지는 $N$개의 선형 방정식을 선형 연립 방정식(system of linear equations)이라고 한다.

$$ \begin{matrix} a_{11} x_1 & + \;& a_{12} x_2 &\; + \cdots + \;& a_{1M} x_M &\; = \;& b_1 \\ a_{21} x_1 & + \;& a_{22} x_2 &\; + \cdots + \;& a_{2M} x_M &\; = \;& b_2 \\ \vdots\;\;\; & & \vdots\;\;\; & & \vdots\;\;\; & & \;\vdots \\ a_{N1} x_1 & + \;& a_{N2} x_2 &\; + \cdots + \;& a_{NM} x_M &\; = \;& b_N \\ \end{matrix} $$

행렬의 곱셈을 이용하면 이 선형 연립 방정식은 다음처럼 간단하게 쓸 수 있다. $$ Ax = b $$

이 식에서 $A, x, b$ 는 각각 계수 행렬, 미지수 벡터, 상수 벡터라고 부른다.

$$ A = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1M} \\ a_{21} & a_{22} & \cdots & a_{2M} \\ \vdots & \vdots & \ddots & \vdots \\ a_{N1} & a_{N2} & \cdots & a_{NM} \\ \end{bmatrix} , \;\; x = \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_M \end{bmatrix} , \;\; b= \begin{bmatrix} b_1 \\ b_2 \\ \vdots \\ b_N \end{bmatrix} $$$$ Ax = b \;\;\;\;\; \rightarrow \;\;\;\;\; \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1M} \\ a_{21} & a_{22} & \cdots & a_{2M} \\ \vdots & \vdots & \ddots & \vdots \\ a_{N1} & a_{N2} & \cdots & a_{NM} \\ \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_M \end{bmatrix} = \begin{bmatrix} b_1 \\ b_2 \\ \vdots \\ b_N \end{bmatrix} $$

예를 들어 선형 연립 방정식

$$ \begin{alignat}{7} 3x_1 &&\; + \;&& 2x_2 &&\; - \;&& x_3 &&\; = \;&& 1 & \\ 2x_1 &&\; - \;&& 2x_2 &&\; + \;&& 4x_3 &&\; = \;&& -2 & \\ -x_1 &&\; + \;&& \tfrac{1}{2} x_2 &&\; - \;&& x_3 &&\; = \;&& 0 & \end{alignat} $$

은 다음처럼 쓸 수 있다.

$$ Ax = b $$$$ A = \begin{bmatrix} 3 & 2 & -1 \\ 2 & -2 & 4 \\ -1 & \tfrac{1}{2} & 1 \\ \end{bmatrix}, \;\;\; x = \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix}, \;\;\; b = \begin{bmatrix} 1 \\ -2 \\ 0 \end{bmatrix} $$

만약 $A, x, b$가 행렬이 아닌 실수라면 이 방정식은 나눗셈을 사용하여 쉽게 풀 수 있을 것이다.

$$ x = \dfrac{b}{A} $$

그러나 행렬은 나눗셈이 정의되지 않으므로 이 방법은 사용할 수 없다. 행렬에서는 나눗셈 대신 역행렬(inverse)이라는 것을 사용한다.

역행렬

정방 행렬 $A$에 대한 역행렬 $A^{-1}$은 원래의 행렬 $A$와 다음 관계를 만족하는 정방 행렬을 말한다. $I$는 단위 행렬(identity matrix)이다.

$$ A^{-1} A = A A^{-1} = I $$

역행렬은 항상 존재하는 것이 아니라 원래의 행렬에 따라서는 존재하지 않을 수도 있다. 역행렬이 존재하는 행렬을 가역행렬(invertible matrix), 정칙행렬regular matrix) 또는 비특이행렬(non-singular matrix)이라고 한다. 반대로 역행렬이 존재하지 않는 행렬을 비가역행렬(non-invertible) 또는 특이행렬(singular matrix), 퇴화행렬(degenerate matrxi)이라고 한다.

역행렬의 성질

역행렬은 다음 성질을 만족한다. 식에서 행렬 $A$, $B$, $C$는 모두 역행렬이 존재한다고 가정한다.

  • 전치 행렬의 역행렬은 역행렬의 전치 행렬과 같다. 따라서 대칭 행렬의 역행렬도 대칭 행렬이다.
$$ (A^{T})^{-1} = (A^{-1})^{T} $$
  • 두 개 이상의 정방 행렬의 곱은 같은 크기의 정방 행렬이 되는데 이러한 행렬의 곱의 역행렬은 다음 성질이 성립한다.
$$ (AB)^{-1} = B^{-1} A^{-1} $$$$ (ABC)^{-1} = C^{-1} B^{-1} A^{-1} $$

역행렬의 계산

역행렬은 행렬식과 다음처럼 계산할 수 있다. 이 식에서 코팩터로 이루어진 행렬 $C$을 코팩터 행렬(matrix of cofactors, 또는 cofactor matrix, comatrix)이라고 한다. 또한 코팩터 행렬의 전치 행렬 $C^T$를 어드조인트 행렬(adjoint matrix, adjugate matrix, 수반 행렬)이라고 하며 $\text{adj}(A)$로 표기하기도 한다.

$$ A^{-1} = \dfrac{1}{\det A} C^T = \dfrac{1}{\det A} \begin{bmatrix} C_{1,1} &\cdots& C_{N, 1}\\ \vdots &\ddots &\vdots\\ C_{1,N} &\cdots &C_{N,N}\\ \end{bmatrix} $$

위 식을 이용하면 임의의 정방행렬의 역행렬을 구할 수 있고 역행렬은 행렬식이 0이 아닌 경우에만 존재한다는 것을 알 수 있다.

연습 문제 1

코팩터 식을 사용하여 다음 역행렬을 계산해 보아라.

  1. $$ \begin{bmatrix} 2 & 0 \\ 0 & 1 \end{bmatrix}^{-1} $$

  2. $$ \begin{bmatrix} \dfrac{1}{\sqrt{2}} & -\dfrac{1}{\sqrt{2}} \\ \dfrac{1}{\sqrt{2}} & \dfrac{1}{\sqrt{2}} \end{bmatrix}^{-1} $$

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

미지수의 수와 방정식의 수가 같다면 행렬 $A$는 정방 행렬이 된다. 만약 행렬 $A$의 역행렬 $A^{-1}$ 이 존재한다면 역행렬의 정의로부터 선형 연립 방정식의 해는 다음처럼 구한다.

$$ Ax = b $$$$ A^{-1}Ax = A^{-1}b $$$$ Ix = A^{-1}b $$$$ x = A^{-1}b $$

NumPy를 사용한 역행렬 계산

NumPy의 linalg 서브패키지에는 역행렬을 구하는 inv 라는 명령어가 존재한다. 그러나 실제로 계산할 때는 수치 해석 상의 여러 가지 문제로 inv 명령어 보다는 lstsq (least square) 명령어를 사용한다.

In:
A = np.array([[2, 3, -2], [3, 5, 6], [2, 4, 3]])
A
Out:
array([[ 2,  3, -2],
       [ 3,  5,  6],
       [ 2,  4,  3]])
In:
b = np.array([[-5], [12], [7]])
b
Out:
array([[-5],
       [12],
       [ 7]])

inv 명령으로 역행렬을 구한다.

In:
Ainv = np.linalg.inv(A)
Ainv
Out:
array([[ 0.69230769,  1.30769231, -2.15384615],
       [-0.23076923, -0.76923077,  1.38461538],
       [-0.15384615,  0.15384615, -0.07692308]])

역행렬을 이용하여 연립방정식의 해를 구한다.

In:
x = np.dot(Ainv, b)
x
Out:
array([[-2.84615385],
       [ 1.61538462],
       [ 2.07692308]])

이렇게 구한 해를 원래 연립방정식에 대입하여 b와 값이 일치하는지 확인한다.

In:
np.dot(A, x) - b
Out:
array([[ -4.44089210e-15],
       [ -3.55271368e-15],
       [ -1.77635684e-15]])

원래 $b$ 값과 해 $x$를 사용하여 계산한 $Ax$는 $10^{-15}$ 수준의 오차내에서 일치한다. 이 오차는 부동소수점의 정밀도 및 계산 과정때문에 발생한 오차이다.

lstsq 명령은 행렬 A와 b를 같이 받아 최소 자승 문제의 해 벡터 x, 잔차 제곱합 resid, 랭크 rank, 특이값 s를 반환한다. 역행렬이 존재하는 경우에는 잔차 제곱합 resid은 빈 배열이다. 랭크와 특이값에 대해서는 추후 설명한다.

In:
x, resid, rank, s = np.linalg.lstsq(A, b)
In:
x
Out:
array([[-2.84615385],
       [ 1.61538462],
       [ 2.07692308]])

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

선형 예측 모형의 계수 벡터를 구하는 문제는 연립 방정식을 푸는 것과 같다. 예를 들어 $N$개의 입력 차원을 가지는 특징 벡터를 입력으로 사용하고 $N$개의 데이터를 이용하여 계수 벡터를 찾으려면 다음 방정식을 만족하는 $w$ 벡터를 찾는 것과 같다.

$$ \begin{matrix} x_{11} w_1 & + \;& x_{12} w_2 &\; + \cdots + \;& x_{1N} w_N &\; = \;& y_1 \\ x_{21} w_1 & + \;& x_{22} w_2 &\; + \cdots + \;& x_{2N} w_N &\; = \;& y_2 \\ \vdots\;\;\; & & \vdots\;\;\; & & \vdots\;\;\; & & \;\vdots \\ x_{N1} w_1 & + \;& x_{N2} w_2 &\; + \cdots + \;& x_{NN} w_N &\; = \;& y_N \\ \end{matrix} $$$$ Xw = y $$

연습 문제 2

보스턴 집값 문제를 선형 예측 모형 $Xw=\hat{y}$로 풀었을 때의 가중치 벡터 $w$를 구하라. 행렬과 벡터 데이터는 다음과 같이 얻을 수 있다. 여기에서는 문제를 간단하게 하기 위해 입력 데이터를 CRIM, NOX, RM, AGE의 4종류로 제한하였고 데이터도 4개만 사용하였다.

from sklearn.datasets import load_boston
boston = load_boston()
X = boston.data
y = boston.target
A = X[:4, [0, 4, 5, 6]]  # 'CRIM', 'NOX', 'RM', 'AGE'
b = y[:4]

이렇게 구한 가중치의 크기나 부호가 우리의 직관이나 경험과 일치하는지 살펴보라.

역행렬의 존재

연립 방적식을 풀 때 추가적으로 고려해야 하는 두가지 문제가 있다.

  • 역행렬이 존재하는가? 존재하는지 어떻게 알 수 있는가?
  • 미지수의 수와 방정식의 수가 다르다면 어떻게 하는가?

행렬식과 역행렬의 관계에서 다음을 알 수 있다.

행렬식의 값이 0이 아니면 역행렬이 존재한다. 반대로 역행렬이 존재하면 행렬식의 값은 0이 아니다.

따라서 행렬식의 값을 계산하여 역행렬의 존재 여부를 알 수 있다. 역행렬이 존재할 때만 선형 연립 방정식의 해를 구할 수 있다.

최소 자승 문제

다음으로 미지수의 수와 방정식의 수를 고려해 볼 때 연립 방정식에는 다음과 같은 세 종류가 있을 수 있다.

  1. 방정식의 수가 미지수의 수와 같다. ($N = M$)
  2. 방정식의 수가 미지수의 수보다 적다. ($N < M$)
  3. 방정식의 수가 미지수의 수보다 많다. ($N > M$)

1번의 경우는 앞에서 다루었다. 2번의 경우에는 무수히 많은 해가 존재할 수 있다. 3번의 경우에는 2번과 반대로 모든 조건을 만족하는 해가 하나도 존재할 수 없을 수 있다.

그런데 데이터 분석 문제에서는 계수 행렬 $A$를 특징 행렬 $X$, 미지수 벡터 $x$를 가중치 벡터 $w$ 라고 보았을 때 데이터의 수가 가중치의 수보다 많을 때가 많다. 즉 3번과 같은 경우가 일반적이다. 일반적으로 데이터의 수가 가중치의 수보다 적을 때는 복수의 예측 모형이 있을 수 있으므로 추가적인 조건을 주지 않고서는 예측 모형을 만들기 어렵다.

방정식의 수가 미지수의 수보다 많을 때(3번의 경우)는 정확한 해가 존재하지 않을 수 있으므로 방정식의 우변과 좌변이 정확하게 같기를 바라지 않는다. 대신 좌변과 우변을 비슷하게라도 만들 수 있는 미지수를 찾을 수 있다면 아예 아무런 숫자를 찾지 못하는 것보다는 훨씬 나을 것이다.

$$ Ax \approx b $$

이 경우는 선형 연립 방정식 문제를 좌변과 우변의 차이를 최소화하는 문제로 바꾸어 풀 수 있다.

$$ e = Ax-b $$

좌변과 우변의 차이 즉 잔차를 최소화 한다는 것은 잔차 벡터의 크기 즉, 놈을 최소화 하는 것과 같다.

$$ e^Te = \Vert e \Vert^2 = (Ax-b)^T(Ax-b) $$

이 값을 최소화 하는 $x$ 값을 찾는 식은 다음처럼 표현한다.

$$ x = \text{arg} \min_x e^Te = \text{arg} \min_x \; (Ax-b)^T(Ax-b) $$

위 식에서 $\text{arg} \min_x f(x)$ 는 함수 $f(x)$를 가장 작게 만드는 $x$ 값을 의미한다.

이러한 문제를 최소 자승(Least Square) 문제라고 한다.

$A^TA$가 항상 정방 행렬이 된다는 점을 이용하여 다음과 같이 최소 자승 문제의 답이 어떤 형태가 되는지 살펴보자. 여기에서는 답의 형태만 살펴보고 엄밀한 증명은 하지 않을 것이다.

$$ Ax \approx b $$

이 식의 양변에 $A^T$를 곱하면 각각 $A^TAx$와 $A^Tb$ 가 된다. 이 두 개의 벡터의 값이 같다고 일단 가정하자.

$$ A^TAx = A^Tb $$

만약 정방 행렬 $A^TA$의 역행렬 $(A^TA)^{-1}$이 존재한다면

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

이 식을 정리하면 다음과 같으며 이렇게 구한 값이 최소 자승 문제의 답이 된다.

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

여기에서 행렬 $(A^TA)^{-1}A^T$ 를 행렬 $A$의 의사 역행렬(pseudo inverse)이라고 하며 다음처럼 $ A^{+}$ 로 표기하기도 한다.

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

이 식이 최소 자승 문제의 답이 된다는 것은 나중에 행렬의 미분을 사용하여 증명할 것이다.

NumPy의 lstsq 명령은 사실 이러한 최소 자승 문제를 푸는 명령이다. 다음 문제는 연립방정식의 해의 갯수보다 방정식(조건)의 갯수가 많으므로 일반적으로는 풀리지 않는 문제이다. 이 문제를 최소 자승 문제로 생각하여 풀면 다음과 같다.

In:
A = np.array([[2, 3, -2], [3, 5, 6], [2, 4, 3], [0, 1, 2]])
A
Out:
array([[ 2,  3, -2],
       [ 3,  5,  6],
       [ 2,  4,  3],
       [ 0,  1,  2]])
In:
b = np.array([[-5], [12], [7], [6]])
b
Out:
array([[-5],
       [12],
       [ 7],
       [ 6]])

우선 의사 역행렬을 직접 계산하여 해를 구한다.

In:
Apinv = np.dot(np.linalg.inv(np.dot(A.T, A)), A.T)
Apinv
Out:
array([[ 0.04509804,  0.75294118, -0.6745098 , -1.20196078],
       [ 0.15882353, -0.43529412,  0.49411765,  0.72352941],
       [-0.16862745,  0.14117647, -0.04313725, -0.02745098]])
In:
x = np.dot(Apinv, b)
x
Out:
array([[-3.12352941],
       [ 1.78235294],
       [ 2.07058824]])

이 해를 이용하여 b값을 구하면 다음처럼 소수점 아래 한자리 오차로 일치하는 것을 볼 수 있다.

In:
np.dot(A, x)
Out:
array([[ -5.04117647],
       [ 11.96470588],
       [  7.09411765],
       [  5.92352941]])

lstsq 명령으로 구해도 같은 값이 나온다.

In:
x, resid, rank, s = np.linalg.lstsq(A, b)
x
Out:
array([[-3.12352941],
       [ 1.78235294],
       [ 2.07058824]])

resid은 오차 벡터 $Ax-b$의 크기, 즉 제곱합이다.

In:
resid, np.linalg.norm(np.dot(A, x) - b) ** 2
Out:
(array([ 0.01764706]), 0.017647058823529287)

연습 문제 3

보스턴 집값 문제를 선형 예측 모형 $Xw=\hat{y}$로 풀었을 때의 가중치 벡터 $w$를 최소 자승 방법으로 구하라. 행렬과 벡터 데이터는 다음과 같이 얻을 수 있다.

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

이렇게 구한 가중치의 부호가 우리의 직관이나 경험과 일치하는지 살펴보라. 또 CRIM, NOX, RM, AGE의 가중치가 위에서 구한 값과 어떻게 달라지는지 살펴보라.

질문/덧글

행렬의 곱을 할때마다 np.dot( )을 계속 써주어야 하나요? todh*** 2016년 9월 6일 8:34 오후

np.dot을 계속하려니 다소 번거롭기도한데 np.dot()을 한번만 써서 여러 행렬을 곱할 수 있나요?

답변: 행렬의 곱을 할때마다 np.dot( )을 계속 써주어야 하나요? 관리자 2016년 9월 7일 9:49 오전

현재는 곱을 할때마다 np.dot( )을 계속 써주어야 합니다.
추후 버전에는 numpy.linalg.multi_dot 명령이 추가될 예정이고 ( https://github.com/numpy/numpy/pull/4977 )
지금은 reduce 등을 사용하여 multiple dot 을 구현하실 수 있습니다. ( http://stackoverflow.com/questions/11838352/multiply-several-matrices-in-numpy )

수학 질문 crys*** 2016년 10월 19일 6:53 오후

pseudo inverse를 역행렬의 성질과 결합법칙을 이용하여
이렇게 풀어도 되는 것인지 아니면 어느 부분에서 잘못했는지 궁금합니다.

Apinv = inv(A.T × A) × A.T
= inv(A) × inv(A.T) × A.T ---> 역행렬의 성질
= ( inv(A) × ( inv(A.T) ) × A.T
= inv(A) × ( inv(A.T) × A.T ) ---> 결합법칙
= inv(A) × I ---> 단위행렬

답변: 수학 질문 관리자 2016년 10월 20일 4:01 오후

A가 정방행렬이 아니므로 A의 역행렬은 존재할 수 없습니다.

미지수의 수와 방정식의 수 simf*** 2017년 2월 6일 6:32 오후

안녕하세요 박사님,

최소 자승 문제 부분에서

2. 미지수의 수가 방정식의 수보다 적다. ( N<M ) -> 너무 많은 해가 존재할 수 있다.
3. 미지수의 수가 방정식의 수보다 많다. ( N>M ) -> 모든 조건을 만족하는 해가 하나도 존재할 수 없을 수도 있다.

라고 설명되어 있는데, 반대가 되어야 하는 것 아닌가요?

답변: 미지수의 수와 방정식의 수 관리자 2017년 2월 7일 4:53 오후

잘못되었습니다. 수정하였습니다. 지적 감사드립니다.

최소 자승 문제설명중에 e가 최소인 x를 찾는것? samk*** 2017년 4월 7일 10:23 오후

최소 자승 문제설명중에 e가 최소인 x를 찾는 것은 이해가 갔습니다.
다만, 수식 유도가 이해가 어려운 부분이 있습니다.

1. e=Ax−b
2. eTe=(Ax−b)T(Ax−b)
3. x=argminxeTe=argminx(Ax−b)T(Ax−b)

1 -> 2 -> 3 순서로 유도된 것은
eTe 의 최소값이 e의 최소값과 동일하다는 뜻인지요?

답변: 최소 자승 문제설명중에 e가 최소인 x를 찾는것? 관리자 2017년 4월 11일 9:41 오후

$e^Te$ 의 최소값이 $e$의 최소값과 동일하다는 뜻이 아닙니다. 최소화하는 것은 $e^Te$ 입니다. $e=Ax-b$ l식은 $e$의 정의입니다.