Eigenvalue & Eigenvector

고유벡터(Eigenvector)란 특정 정방행렬 $A$를 통해서 선형 변환했을 때 방향이 변화하지 않는 벡터입니다. 그리고 그 벡터가 변하는 길이는 고윳값(Eigenvalue)입니다. 수식으로 나타냈을 때 아래 수식을 만족하는 $\lambda, e$ 를 각각 $A$의 고윳값과 고유벡터라고 합니다. \(Ae = \lambda e\)

$A$는 정방행렬이므로 다음과 같이 나타낼 수 있습니다.

[(A - \lambda I)e = 0]

$v \neq \vec{0}$ 이면 $\text{det}(A-\lambda I) = 0$ 이어야 합니다. $A - \lambda I$ 의 요소를 나타내면 아래와 같습니다.

[A - \lambda I = \left[\begin{array}{cccc} a_{11} - \lambda & a_{12} & \cdots & a_{1n} \ a_{21} & a_{22} - \lambda & \cdots & a_{2n} \ \vdots & \vdots & \ddots \ a_{n1} & a_{n2} & & a_{nn} - \lambda \end{array} \right]]

따라서, 이 행렬의 행렬식을 구하면

[\det (A - \lambda I) = \lambda^n + c_1\lambda^{n-1} + c_2\lambda^{n-2} + \cdots]

와 같은 $\lambda$ 에 관한 $n$차식이 도출됩니다. 우변의 식인 $\lambda^n + c_1\lambda^{n-1} + c_2\lambda^{n-2} + \cdots + c_n = 0$ 을 만족하는 $\lambda$를 구하여 행렬 $A$의 고윳값을 찾을 수 있습니다. $n \geq 5$ 일 때에는 해를 구하는 공식이 없습니다. 그렇기 때문에 일반적으로 고윳값을 구할 때에는 시행착오법(Trial-error)을 사용하여 구합니다.

$2 \times 2$ 크기의 행렬 $A$를 예로 들어 해당 행렬의 고윳값과 고유벡터를 구해보도록 하겠습니다.

[A = \left[\begin{array}{cc} 4 & -5 \ 2 & -3 \end{array} \right]
A - \lambda I = \left[\begin{array}{cc} 4-\lambda & -5 \ 2 & -3-\lambda \end{array}\right]]

$\det (A-\lambda I) = 0$ 인 $\lambda$를 구하면 아래와 같이 나오게 됩니다.

[\begin{aligned} \det (A - \lambda I) &= (4-\lambda)(-3-\lambda)+10
&= \lambda^2-\lambda-12 = (\lambda - 4)(\lambda+3) = 0 \end{aligned}
\therefore \lambda = 4, -3]

각 $\lambda$를 $A-\lambda I$ 행렬에 대입하여 나오게 되는 Null space가 각각의 고유벡터가 됩니다. 각 고윳값마다 하나의 고유벡터가 존재합니다.

[e = \mathbb{N}(A-\lambda I)]

그렇다면 삼각행렬의 고윳값은 어떻게 구할 수 있을까요? 아래와 같은 상삼각행렬 $U$의 고윳값을 구해보겠습니다.

[U = \left[\begin{array}{ccc} 1 & 4 & 5 \ 0 & 5 & 6 \ 0 & 0 & 3 \end{array} \right]]

$U - \lambda I$ 역시 상삼각행렬이고 상삼각 행렬의 행렬식은 피봇의 곱과 같으므로 $\det (U - \lambda I) = 0$ 이 되는 식을 구하면 아래와 같습니다.

[\det (U - \lambda I) = (1-\lambda)(5-\lambda)(3-\lambda) = 0
\therefore \lambda = 1,3,5]

이렇게 삼각행렬의 고윳값은 해당 행렬의 대각 성분(Diagonal term) 자체가 고윳값이 됩니다.

다음으로 임의의 정방행렬 $A$에 대하여 이 행렬의 대각 성분을 모두 더한 값에 대해 알아보겠습니다. 이 값은 $A$의 Trace(트레이스)라고도 부릅니다. 결과부터 말하면 이 값은 모든 고윳값을 더한 것과 같게 됩니다. 수식으로는 아래와 같이 나타낼 수 있습니다.

[\text{Trace of } A = \sum^n_{i=1} a_{ii} = a_{11} + a_{22} + \cdots + a_{nn} = \sum^n_{i=1} \lambda_{ii}]

어떻게 이렇게 될 수 있을까요? 임의의 정방행렬 $A$의 고윳값을 구하는 과정을 요소를 사용하여 다시 살펴보겠습니다. $A - \lambda I$ 의 값은 다음과 같이 나타낼 수 있습니다.

[A - \lambda I = \left[\begin{array}{ccccc} a_{11} - \lambda & a_{12} & a_{13} & \cdots & a_{1n} \ a_{21} & a_{22} - \lambda & a_{23} & \cdots & a_{2n} \ & & a_{33} - \lambda & & \ & & & \ddots & \ a_{n1} & a_{n2} & a_{n3} & & a_{nn} - \lambda \end{array} \right]]

위 행렬의 행렬식을 Co-factor를 사용하여 구한다고 해봅시다. 첫째 행을 기준으로 한다면 수식은 아래와 같을 것입니다.

[\det (A - \lambda I) = (a_{11} - \lambda)C_{11} + a_{12}C_{12} + a_{13}C_{13} + \cdots + a_{1n}C_{1n}]

Co-factor를 재귀적으로 구하는 과정을 생각해본다면 $C_{11}$ 에는 $\lambda$ 가 $n-1$ 번 등장하지만 다른 Co-factor에는 $\lambda$ 가 $n-2$ 번 등장하는 것을 알 수 있습니다. $1$번째 행에서 한 개의 $\lambda$가 사라지게 되고, $n$번째 열에서 한 개의 $\lambda$가 사라지게 되기 때문입니다. 이를 기억하고 위 수식을 임의의 상수인 계수 $c_1, c_2, \cdots$ 를 사용하여 나타내 보겠습니다.

[\det (A - \lambda I) = (-\lambda)^n + c_1(-\lambda)^{n-1} + c_2(-\lambda)^{n-2} + \cdots + c_n]

우리의 목표는 위 식이 $0$이 되는 $\lambda$의 값을 구하는 것입니다. 이 때 근과 계수와의 관계를 활용하여 모든 고윳값의 합을 구해볼 수 있습니다. 근과 계수와의 관계에 의하여 $k_1x^n + k_2x^{n-1} + \cdots = 0$ 과 같은 고차방정식에서 모든 근의 합은 $-(k_2/k_1)$ 입니다. 따라서 $\det (A - \lambda I) = 0$ 을 만족하는 모든 고윳값의 합은 $(-\lambda)^{n-1}$의 계수인 $c_1$이 나오게 될 것입니다.

다시 Co-factor로 돌아가 보겠습니다. $C_{11}$에만 $\lambda^{n-1}$ 이 있었고, 나머지 Co-factor에는 최대 차수를 $\lambda^{n-2}$ 으로 갖는 항들을 가지고 있었습니다. 그리하여 최종식에 도출되는 $\lambda^n, \lambda^{n-1}$ 은 오로지 $\det (A - \lambda I)$을 Co-factor로 나타낸 식에서 첫번째 항에 의해서 결정됩니다. 특히 $\lambda^n, \lambda^{n-1}$ 은 아래와 같은 항에 의해 도출되는 것을 알 수 있습니다.

[\det (A - \lambda I) = (a_{11} - \lambda)(a_{22} - \lambda) \cdots (a_{nn} - \lambda) + \cdots]

이 식으로부터 $(-\lambda)^{n-1}$의 계수인 $c_1$이 어떻게 도출되는 지 구할 수 있습니다.

[c_1 = a_{11} + a_{22} + \cdots + a_{nn}]

이 값이 행렬 $A$가 가진 모든 고윳값의 합과 같았으므로 $A$의 대각성분을 모두 합한 값, 즉 $A$의 Trace가 모든 고윳값의 합과 같음을 알 수 있습니다.

Eigenvalue Decomposition

다음은 행렬을 분해하는 또 다른 방법인 고윳값 분해(Eigenvalue decomposition)에 대해서 알아보겠습니다. 결과부터 알아보자면 임의의 정방행렬 $A$를 고윳값 분해하여 나타낸 결과는 아래와 같습니다.

[A = S \Lambda S^{-1}]

위 식에서 행렬 $S$는 각 고유벡터를 열벡터로 갖는 행렬이며, 행렬 $\Lambda$는 고윳값을 대각성분으로 갖는 대각 행렬(Diagonal matrix)입니다. 이렇게 나타낼 수 있는 이유에 대해 알아보겠습니다. 먼저 두 행렬의 곱 $AS$를 아래와 같이 나타낼 수 있습니다.

[AS = A \left[\begin{array}{cc} e_1 & e_2 & \cdots & e_n \end{array} \right] = \left[\begin{array}{cc} Ae_1 & Ae_2 & \cdots & Ae_n \end{array} \right]]

가장 오른쪽 항의 각 요소를 고윳값과 고유벡터의 정의를 사용하여 아래와 같이 나타낼 수 있습니다.

[\left[\begin{array}{cc} Ae_1 & Ae_2 & \cdots & Ae_n \end{array} \right] = \left[\begin{array}{cc} \lambda_1e_1 & \lambda_2e_2 & \cdots & \lambda_ne_n \end{array} \right]]

마지막 식은 아래와 같이 나타낼 수 있습니다. 이 과정을 통해 $AS = S \Lambda$임을 알 수 있습니다.

[\left[\begin{array}{cc} \lambda_1e_1 & \lambda_2e_2 & \cdots & \lambda_ne_n \end{array} \right] = \left[\begin{array}{cc} e_1 & e_2 & \cdots & e_n \end{array} \right]\left[\begin{array}{cc} \lambda_1 & 0 & \cdots & 0 \ 0 & \lambda_2 & \cdots & 0 \ \vdots & \vdots & \ddots & \ 0 & 0 & & \lambda_n \end{array} \right] = S \Lambda
\therefore AS = S \Lambda]

마지막으로 양 변에 $S^{-1}$을 곱해주어 $A$에 대한 식으로 나타내어 줄 수 있습니다.

[A = S \Lambda S^{-1}]

Properties

고윳값과 고유벡터의 정의와 고윳값 분해를 사용하면 고윳값과 고유벡터가 가진 여러가지 성질을 알 수 있습니다. 첫 번째 성질은 각각 다른 값을 갖는 고윳값 $\lambda_1, \lambda_2, \cdots, \lambda_n$ 에 대하여 고유벡터 $e_1, e_2, \cdots, e_n$ 가 선형 독립(Linearly independent)이라는 점입니다. 이는 귀류법을 통해서 증명할 수 있습니다.

먼저 $e_2$ 가 $e_1$ 에 종속이라고 가정해보겠습니다. 그렇다면 $e_2 = c \cdot e_1$ 처럼 한 벡터를 다른 벡터의 스칼라 곱으로 나타낼 수 있을 것입니다. 이 식의 양변에 행렬 $A$를 곱하면 아래와 같이 나타낼 수 있습니다.

[Ae_2 = c \cdot Ae_1]

고윳값과 고유벡터의 정의에 의하여 위 식의 좌변과 우변은 각각 아래 식처럼 변형해 줄 수 있습니다.

[\lambda_2e_2 = c \cdot \lambda_1 e_1]

그리고 원래 $e_2 = c \cdot e_1$ 식의 양변에 스칼라 값인 $\lambda_2$를 곱하여 식을 나타내면 $\lambda_2e_2 = c \cdot \lambda_2e_1$ 로 나타낼 수 있습니다. 두 식의 좌변은 $\lambda_2e_2$ 로 동일하므로 한 식의 우변을 대입한 뒤에 모든 항을 좌변으로 넘긴 뒤 공통 부분으로 묶어내면 아래와 같이 나타낼 수 있습니다.

[c (\lambda_2 - \lambda_1)e_1 = 0]

고유벡터인 $e_1$은 영벡터가 아니고, 두 고윳값이 같지 않으므로 $c = 0$이 됩니다. 즉, $e_2$ 와 $e_1$이 종속 관계에 있다는 가정은 틀리게 되는 것이며 두 벡터가 선형 독립 관계에 있음을 알 수 있습니다. 이를 일반화하여 다음과 같이 나타낼 수 있습니다. 특정한 고유벡터 $e_n$가 다른 고유벡터와 선형 종속 관계에 있다고 하면 아래와 같이 나타낼 수 있습니다.

[e_n = c_1e_1 + c_2e_2 + \cdots +c_{n-1}e_{n-1}]

양변에 $A$를 곱한 식은 각각 아래와 같이 나오게 됩니다.

[Ae_n = c_1Ae_1 + c_2Ae_2 + \cdots +c_{n-1}Ae_{n-1}
\lambda_ne_n = c_1\lambda_1e_1 + c_2\lambda_2e_2 + \cdots + c_{n-1}\lambda_{n-1}e_{n-1}]

그리고 양변에 $\lambda_n$을 곱한 식은 아래와 같습니다.

[\lambda_ne_n = c_1\lambda_ne_1 + c_2\lambda_ne_2 + \cdots + c_{n-1}\lambda_ne_{n-1}]

두 수식을 빼주면 식이 다음과 같이 변하게 됩니다.

[c_1 (\lambda_n - \lambda_1)e_1 + c_2 (\lambda_n - \lambda_2)e_2 + \cdots + c_{n-1} (\lambda_n - \lambda_{n-1})e_{n-1} = 0]

이를 만족하려면 $c_1, c_2, \cdots, c_{n-1} = 0$이어야 하므로 다른 고윳값을 갖는 고유벡터는 나머지 고유벡터와 선형 독립 관계에 있는 것을 알 수 있습니다.

두 번째 성질은 고윳값 분해에 사용되는 $S$가 Unique하지 않다는 점입니다. 특정한 고유벡터 $e$를 스칼라배 해준 $ke$ 역시 고유벡터이기 때문에 만약 특정 행렬의 $S$가 아래 식의 $S_1$과 같다면 $S_2$ 역시 해당 행렬의 $S$가 됩니다.

[S_1 = \left[\begin{array}{cc} 1 & 1 \ 1 & -1 \end{array} \right] \qquad S_2 = \left[\begin{array}{cc} 1 & -1 \ 1 & 1 \end{array} \right]]

다음 성질은 행렬 $A$의 거듭제곱과 고윳값의 관계를 나타낸 것입니다. 특정 행렬 $A$ 의 거듭제곱인 $A^k$ 에 대하여 아래와 같은 식이 성립합니다.

[A^ke = \lambda^ke]

위 식은 위에서 알아보았던 고윳값 분해를 사용하여 증명할 수 있습니다. 고윳값 분해를 사용하여 행렬의 거듭제곱 $A^k$ 를 다음과 같이 나타낼 수 있습니다.

[\begin{aligned} A^k &= (S \Lambda S^{-1})^k
&= S \Lambda S^{-1}S \Lambda S^{-1}S \Lambda S^{-1} \cdots S \Lambda S^{-1}
&= S \Lambda^k S^{-1}
\therefore A^kS &= \Lambda^kS \end{aligned}]

Determinant

이번에는 행렬식(Determinant)에 대해서 알아보겠습니다. 행렬식이란 무엇일까요? 오늘도 역시 위키피디아로 알아보도록 하겠습니다.

선형대수학에서, 행렬식은 정사각 행렬에 스칼라를 대응시키는 함수의 하나이다. 실수 정사각 행렬의 행렬식의 절댓값은 그 행렬이 나타내는 선형 변환이 초부피를 확대시키는 배수를 나타내며, 행렬식의 부호는 방향 보존 여부를 나타낸다.

즉, 행렬식이란 특정한 정방 행렬마다 주어지는 하나의 스칼라값입니다. 특정 정방행렬 $A$의 행렬식은 일반적으로 $\det A$ 로 나타냅니다.

Formula

그렇다면 행렬식은 어떻게 구할 수 있을까요? 행렬식을 구하는 데에도 가우스 소거법(Gaussian elimination)이 사용됩니다. $\det A$ 가 행렬 $A$에서 가우스 소거법을 진행하며 생성되는 피봇의 곱으로 정의되기 때문입니다. 수식으로 나타내면 아래와 같습니다.

[\det A = \pm \prod^n_{i=1} \text{pivots}]

이 됩니다. $\pm$ 이 붙는 이유는 가우스 소거를 진행하는 과정에서 피봇팅을 하면 행을 교차(Row exchange)하게 되는데 이 때문에 부호 교체가 발생하는 것입니다. 행을 교차하는 것과 행렬식 부호의 관계는 아래에 있는 행렬식의 성질에서 다시 알아보겠습니다.

해당 공식을 통하여 $2 \times 2$행렬의 행렬식이 어떻게 나오게 되는 지를 알아보겠습니다.

[\det \left[\begin{array}{cc} a & b \ c & d \end{array} \right] = \det \left[\begin{array}{cc} a & b \ 0 & d - b(c/a) \end{array} \right] = a(d - b(c/a)) = ad - bc]

아래에서 Cofactor를 통한 공식을 하나 더 알아볼 것입니다. 하지만 가우스 소거법을 이용한 방식보다 계산량이 많아 실제로는 가우스 소거를 이용한 방법이 더 자주 사용됩니다.

Basic Properties

행렬식은 세 가지 기본적인 성질을 가지고 있습니다. 첫 번째 성질은 단위 행렬(Identify matrix)의 행렬식이 $1$이라는 점입니다.

Row Exchange

두 번째 특성은 정방행렬 $A$의 두 행이나 두 열을 바꿀 때마다(Row exchange) 부호가 바뀐다는 점입니다. $2 \times 2$ 사이즈의 행렬을 사용하여 성질이 진짜로 그러한 지를 알아보겠습니다. 아래 식에서 행을 한 번 바꾸니 부호가 반대가 되는 것을 알 수 있습니다.

[\begin{aligned} \det \left[\begin{array}{cc} a & b \ c & d \end{array} \right] &= ad - bc
\det \left[\begin{array}{cc} c & d \ a & b \end{array} \right] &= bc - ad = -(ad - bc) \ &= - \det A \end{aligned}]

Linearly Dependent on 1st row

세 번째 성질은 행렬식이 첫 번째 행에 대해서 선형 종속(Linearly dependent)이라는 점입니다. 이 성질 때문에 아래와 같은 수식이 성립하게 됩니다.

[\det \left[\begin{array}{cc} a + a^\prime & b + b^\prime \ c & d \end{array} \right] = \det \left[\begin{array}{cc} a & b \ c & d \end{array} \right] + \det \left[\begin{array}{cc} a^\prime & b^\prime \ c & d \end{array} \right]]

등호 왼쪽에 있는 행렬식을 공식을 활용하여 풀어 쓰면 아래와 같습니다.

[\begin{aligned} \det \left[\begin{array}{cc} a + a^\prime & b + b^\prime \ c & d \end{array} \right] &= (a+a^\prime)d - (b+b^\prime)c \ &= (ad - bc) + (a^\prime d - b^\prime c)
&= \det \left[\begin{array}{cc} a & b \ c & d \end{array} \right] + \det \left[\begin{array}{cc} a^\prime & b^\prime \ c & d \end{array} \right] \end{aligned}]

위 식을 통해 행렬식이 첫 번째 행에 대해서 선형 종속 관계에 있음을 알 수 있습니다. 세 번째 성질을 이용하면 다음과 같은 수식들도 모두 만족함을 보일 수 있습니다.

[\begin{aligned} 1) &\det \left[\begin{array}{cc} a & b \ c & d \end{array} \right] = \det \left[\begin{array}{cc} a & 0 \ c & d \end{array} \right] + \det \left[\begin{array}{cc} 0 & b \ c & d \end{array} \right]
2) &\det \left[\begin{array}{cc} t\cdot a & t\cdot b \ c & d \end{array} \right] = t\cdot \det \left[\begin{array}{cc} a & b \ c & d \end{array} \right]
3) &\det \left[\begin{array}{cc} t\cdot a & t\cdot b \ t\cdot c & t\cdot d \end{array} \right] = t^2 \cdot \det \left[\begin{array}{cc} a & b \ c & d \end{array} \right] \end{aligned}]

위 수식들 중 세 번째 식을 일반화하면 특정 정방행렬 $A$의 모든 요소를 스칼라배 해준 행렬 $t \cdot A$의 행렬식을 다음과 같이 나타낼 수 있습니다.

[\det (t\cdot A_{n \times n}) = t^n \cdot \det A]

Additional Properties

2개(이상)의 동일한 행을 갖는 행렬 A의 행렬식

위에 등장했던 세 가지 성질을 이용하면 행렬식의 추가적인 몇 가지 성질도 알아낼 수 있습니다. 첫 번째는 행렬 $A$에서 두 개(이상)의 행이 같다면 $\det A = 0$ 이라는 점입니다. 특정 행렬 $A$를 전치한 행렬 $A^T$의 열벡터를 각각 $a_1, a_2, \cdots, a_n$ 이라고 하면 행렬 $A$는 다음과 같이 나타낼 수 있을 것입니다.

[A = \left[\begin{array}{c} a_1^T \ a_2^T \ \vdots \ a_n^T \end{array} \right]]

이 중에서 $i,j$ 번째 행, 즉 $a_i^T, a_j^T ((i \neq j) \leq n)$가 서로 같다고 해보겠습니다. 그렇다면 원래의 행렬 $A$와 $i,j$ 번째 행을 서로 바꾼 행렬을 $A^\prime$ 이라고 하면 각각을 다음과 같이 나타낼 수 있습니다.

[A = \left[\begin{array}{c} a_1^T \ \vdots \ a_i^T \ \vdots \ a_j^T \ \vdots \ a_n^T \end{array} \right] \qquad A^\prime = \left[\begin{array}{c} a_1^T \ \vdots \ a_j^T \ \vdots \ a_i^T \ \vdots \ a_n^T \end{array} \right]]

위에서 두 행을 한 번 교차(Row exchange)하면 행렬식의 부호가 바뀌는 성질이 있었습니다. 그렇기 때문에 두 행렬의 행렬식의 절댓값은 동일하지만 부호는 다르게 됩니다. 이를 수식으로 나타내면 아래와 같습니다.

[\det A^\prime = - \det A]

하지만 $a_i = a_j$ 이므로 실제로 두 행렬의 요소는 모두 같습니다. 그렇기 때문에 아래의 식도 성립해야 합니다.

[\det A^\prime = \det A]

두 식을 연결하면 $\det A = - \det A$ 가 되므로 이를 만족하는 $\det A = 0$ 밖에 없게 됩니다.

Zero Row or Column

특정 행렬 $A$ 내에 모든 성분이 $0$인 행이나 열이 존재하면 $A$의 행렬식 $\det A = 0$ 이 됩니다.

Raw Operation

또 하나의 추가적인 성질은 Row operation을 해도 행렬식 값이 바뀌지 않는다는 점입니다. 이 성질 덕분에 가우스 소거법을 이용하여 행렬식을 구할 수 있게 됩니다. 이 성질을 일반화하여 수식으로 나타내면 아래와 같습니다.

[\begin{aligned} \det \left[\begin{array}{cc} a - lc & b - ld \ c & d \end{array} \right] &= \det \left[\begin{array}{cc} a & b \ c & d \end{array} \right] + \det \left[\begin{array}{cc} -lc & -ld \ c & d \end{array} \right]
&=\det \left[\begin{array}{cc} a & b \ c & d \end{array} \right]-l \cdot \det \left[\begin{array}{cc} c & d \ c & d \end{array} \right]
&= \det \left[\begin{array}{cc} a & b \ c & d \end{array} \right] \end{aligned}]

Determinant of AB & Transpose A

다음 성질은 $\det{AB}$ 와 $\det A^T$에 관련된 것입니다. 첫 번째로 두 행렬 $A,B$를 곱한 행렬 $AB$의 행렬식에 대해 알아보겠습니다. 이 경우에 대해서는 일반적으로 아래의 식이 성립하게 됩니다. 아래 식의 증명은 생략하도록 하겠습니다.

[\det{AB} = \det{A} \cdot \det{B}]

다음으로 전치 행렬 $A^T$ 의 행렬식 $\det A^T$ 에 대해서 알아보겠습니다. 일반적으로 $\det A^T = \det A$가 성립합니다. $LDU$ 분해법을 사용하면 쉽게 증명할 수 있습니다. 아래는 이 성질을 $A$를 각각 $LDU$ 분해한 뒤에 위에서 알아본 것입니다. 행렬곱의 행렬식을 구하는 방법을 통해서 최종적으로 두 행렬 모두 $\det D$ 임을 알아낼 수 있습니다.

[\begin{aligned} \det A = \det (LDU) &= \det L \cdot \det D \cdot \det U = \det D
\det A^T = \det (LDU)^T &= \det U^TD^TL^T =\det U^T \cdot \det D^T \cdot \det L^T = \det D
&\therefore \det A = \det A^T
\because D^T = D, &\quad (LDU)^T = U^TD^TL^T, \quad \det U = \det L = 1 \end{aligned}]

Another Formula

위에서 알아본 성질을 사용하면 행렬식을 구하기 위한 새로운 공식을 유도할 수 있습니다. 이 공식을 유도하는 데에는 $\det A$ 가 첫 번째 행에 선형 종속이라는 성질, 두 행을 교환할 경우 행렬식의 부호가 바뀌는 성질, 모든 성분이 $0$인 행 또는 열이 있을 때 $\det A = 0$ 인 성질이 사용됩니다.

이 세 가지 성질을 이용하여 $2 \times 2$ 행렬의 행렬식을 구해보겠습니다.

[\begin{aligned} \det \left[\begin{array}{cc} a & b \ c & d \end{array} \right] =& \det \left[\begin{array}{cc} a & 0 \ c & d \end{array} \right] + \det \left[\begin{array}{cc} 0 & b \ c & d \end{array} \right]
=& -\det \left[\begin{array}{cc} c & 0 \ a & 0 \end{array} \right] -\det \left[\begin{array}{cc} 0 & d \ a & 0 \end{array} \right] -\det \left[\begin{array}{cc} c & 0 \ 0 & b \end{array} \right] -\det \left[\begin{array}{cc} 0 & d \ 0 & b \end{array} \right]
=& 0 + \det \left[\begin{array}{cc} a & 0 \ 0 & d \end{array} \right] - \det \left[\begin{array}{cc} c & 0 \ 0 & b \end{array} \right] + 0 = ad-bc \end{aligned}]

이를 $3 \times 3$ 행렬에도 적용해 보겠습니다. 첫 번째 행에 선형 종속 관계이므로 첫 번째 행의 각 요소에 대해 식을 나누면 아래와 같이 쓸 수 있습니다.

[\det \left[\begin{array}{ccc} a_{11} & a_{12} & a_{13} \ a_{21} & a_{22} & a_{23} \ a_{31} & a_{32} & a_{33} \end{array} \right] = \det \left[\begin{array}{ccc} a_{11} & 0 & 0 \ a_{21} & a_{22} & a_{23} \ a_{31} & a_{32} & a_{33} \end{array} \right] + \det \left[\begin{array}{ccc} 0 & a_{12} & 0 \ a_{21} & a_{22} & a_{23} \ a_{31} & a_{32} & a_{33} \end{array} \right] + \det \left[\begin{array}{ccc} 0 & 0 & a_{13} \ a_{21} & a_{22} & a_{23} \ a_{31} & a_{32} & a_{33} \end{array} \right]]

위 식의 우변의 세 항 중에서 첫 번째에 해당하는 항을 다시 두 번째 행 요소를 기준으로 풀어쓸 수 있습니다. 풀어쓴 식은 아래와 같습니다.

[\det \left[\begin{array}{ccc} a_{11} & 0 & 0 \ a_{21} & a_{22} & a_{23} \ a_{31} & a_{32} & a_{33} \end{array} \right] = \det \left[\begin{array}{ccc} a_{11} & 0 & 0 \ a_{21} & 0 & 0 \ a_{31} & a_{32} & a_{33} \end{array} \right] + \det \left[\begin{array}{ccc} a_{11} & 0 & 0 \ 0 & a_{22} & 0 \ a_{31} & a_{32} & a_{33} \end{array} \right] + \det \left[\begin{array}{ccc} a_{11} & 0 & 0 \ 0 & 0 & a_{23} \ a_{31} & a_{32} & a_{33} \end{array} \right]]

동일하게 위 식의 우변의 세 항 중에서 첫 번째에 해당하는 항을 다시 세 번째 행 요소를 기준으로 풀어쓸 수 있습니다. 풀어쓴 식은 아래와 같습니다.

[\det \left[\begin{array}{ccc} a_{11} & 0 & 0 \ a_{21} & 0 & 0 \ a_{31} & a_{32} & a_{33} \end{array} \right] = \det \left[\begin{array}{ccc} a_{11} & 0 & 0 \ a_{21} & 0 & 0 \ a_{31} & 0 & 0 \end{array} \right] + \det \left[\begin{array}{ccc} a_{11} & 0 & 0 \ a_{21} & 0 & 0 \ 0 & a_{32} & 0 \end{array} \right] + \det \left[\begin{array}{ccc} a_{11} & 0 & 0 \ a_{21} & 0 & 0 \ 0 & 0 & a_{33} \end{array} \right]]

이렇게 모든 항을 풀어쓰게 되면 총 27개의 항이 나오게 될 것입니다. 이 중 모든 열의 요소가 $0$이 아닌 항들만 모아보면 아래와 같이 나오게 될 것입니다.

[\begin{aligned} \det \left[\begin{array}{ccc} a_{11} & a_{12} & a_{13} \ a_{21} & a_{22} & a_{23} \ a_{31} & a_{32} & a_{33} \end{array} \right] = \det \left[\begin{array}{ccc} a_{11} & 0 & 0 \ 0 & a_{22} & 0 \ 0 & 0 & a_{33} \end{array} \right] + \det \left[\begin{array}{ccc} a_{11} & 0 & 0 \ 0 & 0 & a_{23} \ 0 & a_{32} & 0 \end{array} \right] + \det \left[\begin{array}{ccc} 0 & a_{12} & 0 \ a_{21} & 0 & 0 \ 0 & 0 & a_{33} \end{array} \right]\ + \det \left[\begin{array}{ccc} 0 & a_{12} & 0 \ 0 & 0 & a_{23} \ a_{31} & 0 & 0 \end{array} \right] + \det \left[\begin{array}{ccc} 0 & 0 & a_{13} \ a_{21} & 0 & 0 \ 0 & a_{32} & 0 \end{array} \right] + \det \left[\begin{array}{ccc} 0 & 0 & a_{12} \ 0 & a_{22} & 0 \ a_{31} & 0 & 0 \end{array} \right] \end{aligned}]

각각의 값을 구하여 나타내면 아래와 같이 나타나게 될 것입니다.

[\det A = a_{11}a_{22}a_{33} + (-1)a_{11}a_{23}a_{32} + \cdots = \sum^3{\alpha, \beta, \gamma} a{1\alpha}a_{2\beta}a_{3\gamma}(\det P_{\alpha \beta\gamma})]

위 식을 $3 \times 3$이 아닌 $n \times n$ 크기의 행렬로 일반화하면 아래와 같이 나타낼 수 있습니다. 이렇게 유도되는 공식을 Big formula라고 합니다.

[\det A_{n \times n} = \sum_{\alpha, \beta, \gamma, \cdots, \mu} a_{1\alpha}a_{2\beta}a_{3\gamma} \cdots a_{n\mu}(\det P_{\alpha \beta\gamma\cdots \mu})]

다시 $3 \times 3$ 행렬로 돌아가서 $a_{11}$과 관련된 아이들만 모아보겠습니다.

[a_{11}(a_{22}a_{33}\det P_{1} + a_{23}a_{32}\det P_{2}) = a_{11}C_{11}]

이 때 등장하는 두 항을 공통된 부분으로 묶어낸 뒤에 나머지 부분을 Co-factor, $C$ 라고 나타내겠습니다. 이 때 등장하는 Cofactor는 해당 행과 열의 요소를 제외한 나머지 부분 행렬(Sub matrix)의 행렬식과 같게 됩니다. 위 식과 같에 등장하는 $C_{11}$ 은 아래와 같이 나타나게 되는 것이지요.

[C_{11} = \det \left[\begin{array}{cc} a_{22} & a_{23} \ a_{32} & a_{33} \end{array} \right]]

일반적으로 나타내면 아래와 같이 나타낼 수있습니다.

[C_{ij} = (-1)^{i+j}\det M_{ij} \qquad M = \text{minor matrix}]

Co-factor를 사용하면 Big formula의 식을 아래와 같이 조금 더 간단하게 나타낼 수 있습니다. 첫 번째 행을 기준으로 할 경우에는 식이 아래와 같이 됩니다.

[\det A = a_{11}C_{11} + a_{12}C_{12} + \cdots + a_{1n}C_{1n} = \sum^n_{j=1} a_{1j}C_{1j}]

무조건 첫 번째 행을 기준으로 해야하는 것은 아닙니다. 임의의 행인 $i$번째 행을 기준으로 사용하여도 같은 결과를 도출할 수 있습니다.

[\det A = a_{i1}C_{i1} + a_{i2}C_{i2} + \cdots + a_{in}C_{in} = \sum^n_{j=1} a_{ij}C_{ij}]

하지만 실제로는 Co-factor를 사용하더라도 재귀적으로 계속 부분 행렬(Sub-matrix)의 행렬식을 구해야 합니다. 그렇기 때문에 일반적으로 행렬식을 구할 때에는 가우스 소거법을 통한 방법을 더 많이 사용하고 있습니다.

Projection

이번 시간에는 사영(Projection)에 대하여 알아보도록 하겠습니다. 위키백과에서는 사영의 뜻을 다음과 같이 서술하고 있습니다.

사영 또는 투영은 어떤 집합을 부분집합으로 특정한 조건을 만족시키면서 옮기는 작용이다.

즉, 벡터의 사영이란 특정 벡터를 다른 벡터 공간으로 옮기는 행위를 말합니다. 벡터의 사영에서 부분공간의 점들 중 거리가 가장 작은 곳으로 옮긴다는 특정 조건이 있습니다. 예를 들어, $\vec{a}$ 를 다른 벡터 $\vec{b}$ 위로 사영하고자 한다면 $\vec{a}$ 가 사영되는 지점인 $\vec{a^\prime}$ 과 원래 벡터 사이의 거리 $\vert\vec{a} - \vec{a^\prime}\vert$ 최소가 됩니다. 아래 그림은 벡터의 사영을 이미지로 나타낸 것입니다.

이미지 출처 : wikibooks.org

위 이미지에서 $\vec{v}$ 를 사영한 벡터는 둘 사이의 거리인 $\vert \vec{v} - \text{proj}_{[\vec{s}]}(\vec{p})\vert$를 최소화 하는 지점으로 결정됩니다.

Solve Equation

사영을 이용하면 또 다른 형태의 연립방정식의 해를 구할 수 있습니다. 식의 개수가 미지수의 개수보다 더 많은 경우입니다. 미지수의 개수가 2개이고 식이 3개인 경우를 평면상에 나타내면 아래와 같습니다. 물론, 운좋게 세 직선이 한 점에서 만날 수도 있으나 그런 경우는 제외하겠습니다.

이런 경우에는 정해진 하나의 해가 없습니다. 이 연립방정식을 행렬로 나타냈을 때의 $A$는 열의 개수보다 행의 개수가 많은 행렬이 됩니다. 이럴 때에는 해를 나타내는 벡터 $\vec{b}$ 가 $A$의 Column space 내부에 없기 때문에, $A$의 Column 스페이스와 거리가 최소가 되는 곳, 즉 $\vec{b}$ 를 $A$ 의 Column space로 사영한 곳을 해로 정하게 됩니다. 사영 벡터 $\vec{p} = \hat{c}\cdot A$ 라고 하면 $\vec{b} - \hat{c}\cdot A \perp \vec{a_i}$ 이므로 다음과 같은 식을 만족하게 됩니다.

[\begin{aligned} \vec{a_1}^T (\vec{b} - &\hat{c}\cdot A) = 0
\vec{a_2}^T (\vec{b} - &\hat{c}\cdot A) = 0
&\vdots
\vec{a_n}^T (\vec{b} - &\hat{c}\cdot A) = 0
\therefore A^T(\vec{b} - &\hat{c}\cdot A) = 0
\end{aligned}]

식을 전개하여 $\hat{c}$에 대하여 정리하면

[\hat{c}\cdot A^TA = A^T \cdot\vec{b}
\hat{c} = (A^TA)^{-1}A^T \cdot\vec{b}]

최종적으로 이 해를 구하기 위한 변환 행렬, 즉 사영 행렬(Projection matrix, $P$ )은 다음과 같이 나타낼 수 있습니다.

[P = A(A^TA)^{-1}A^T
\because P\cdot \vec{b} = A \cdot \hat{c} = A(A^TA)^{-1}A^T \cdot\vec{b}]

$\vec{b}$ 벡터를 어떤 행렬 $A$의 Column space에 사영시키는 간단한 예시를 보겠습니다. 각 행렬과 벡터의 요소는 다음과 같습니다.

[A = \left[\begin{array}{cc} 1 & 2 \ 1 & 3 \ 0 & 0 \end{array} \right] \ \vec{b} = (4,5,6)^T]

$A$ 의 Column space는 $xy$ 평면이며, 이 공간으로의 사영시키는 행렬 $P$는 위 식을 사용하여 구할 수 있습니다.

[A^TA = \left[\begin{array}{ccc} 1 & 1 & 0 \ 2 & 3 & 0 \end{array} \right]\left[\begin{array}{cc} 1 & 2 \ 1 & 3 \ 0 & 0 \end{array} \right] = \left[\begin{array}{cc} 2 & 5 \ 5 & 13 \end{array} \right]
\therefore (A^TA)^{-1} = \left[\begin{array}{cc} 13 & -5 \ -5 & 2 \end{array} \right]]

사영 행렬 $P$ 를 구하는 식을 사용하면

[P = A(A^TA)^{-1}A^T = \left[\begin{array}{cc} 1 & 2 \ 1 & 3 \ 0 & 0 \end{array} \right]\left[\begin{array}{cc} 13 & -5 \ -5 & 2 \end{array} \right]\left[\begin{array}{ccc} 1 & 1 & 0 \ 2 & 3 & 0 \end{array} \right] = \left[\begin{array}{ccc} 1 & 0 & 0 \ 0 & 1 & 0 \ 0 & 0 & 0\end{array} \right]]

이 됩니다. 벡터 $\vec{b}$를 사영한 벡터는 $P \cdot \vec{b}$ 이므로 다음과 같습니다.

[P \cdot \vec{b} = \left[\begin{array}{ccc} 1 & 0 & 0 \ 0 & 1 & 0 \ 0 & 0 & 0\end{array} \right]\left[\begin{array}{c} 4 \ 5 \ 6\end{array} \right] = \left[\begin{array}{c} 4 \ 5 \ 0\end{array} \right]]

Normal Equation

사영 기법은 임의의 점들을 근사하는 함수를 찾는 데에 사용할 수 있습니다. 가장 간단하게 직선을 찾는 선형 회귀(Linear regression)의 예시부터 알아보겠습니다.

이미지 출처 : wikipedia - Linear_regression

위 그래프의 점을 각각 $(x_1, y_1), (x_2, y_2), (x_3, y_3), (x_4, y_4)$ 라고 하고 이를 근사하는 파란 직선을 $y = w_0 + w_1 x$ 라고 하겠습니다. 이 4개의 점을 모두 지나는 직선은 없으며 파란 직선은 직선과 점 사이의 거리를 최소화하는 조건을 만족하는 직선입니다.

각 점을 지나는 직선은 각각 $y_1 = w_0 + w_1 x_1, \quad y_2 = w_0 + w_1 x_2, \quad y_3 = w_0 + w_1 x_3, \quad y_4 = w_0 + w_1 x_4$ 조건을 만족하므로 식이 4개고 미지수가 2개인 연립방정식의 해를 구하는 것과 같습니다. 이를 행렬을 사용한 식으로 나타내면 아래와 같습니다.

[\left[\begin{array}{cc} 1 & x_1 \ 1 & x_2 \ 1 & x_3 \ 1 & x_4 \end{array} \right]\left[\begin{array}{c} w_0 \ w_1 \end{array} \right] = \left[\begin{array}{c} y_0 \ y_1 \ y_2 \ y_3 \end{array} \right]]

위 식에서 $w_0, w_1$을 구하는 과정은 위에서 풀었던 $A\mathbf{x} = b$ 를 사영으로 푸는 방법과 동일합니다. 이렇게 사영 기법을 통해 회귀식의 미지수를 구하는 방법을 정규 방정식(Normal Equation) 또는 최소 제곱법(Least squares)이라고 합니다.

Orthogonality

이번 게시물에서는 벡터의 직교성(Orthogonality)에 대해 알아보겠습니다. 벡터의 직교성은 왜 중요할까요? 첫 번째는 직교하는(Orthogonal) 벡터는 서로 선형 독립(Linearly Independence) 관계에 있기 때문입니다. 선형 독립인 벡터 $\vec{v_1}, \vec{v_2}, \cdots, \vec{v_n}$ 는 다음의 조건을 만족합니다.

[\begin{aligned} &c_1\vec{v_1} + c_2\vec{v_2} + \cdots + c_n\vec{v_n} = 0
\text{only,} \quad &c_1 = c_2 = \cdots = c_n = 0 \end{aligned}]

두 번째는 직교하는 벡터를 서로 내적하면 결과값이 $0$이 되기 때문입니다. 이런 특성 덕분에 특정 벡터를 직교 벡터의 합으로 나타내면 연산이 매우 쉬워지게 됩니다. 특정 벡터의 크기를 구하는 경우가 이에 속합니다. $\vec{x} = (1,2,3)$의 크기 $\Vert \vec{x} \Vert$ 를 아래와 같이 구할 수 있습니다. 먼저 직교하는 벡터 $\vec{a},\vec{b},\vec{c}$로 나눕니다.

[\text{if} \quad \vec{a} = (1,0,0), \vec{b} = (0,2,0),\vec{c} = (0,0,3)
\vec{x} = \vec{a}+\vec{b}+\vec{c}]

이를 사용하면 아래와 같은 방법을 사용하여 $\Vert \vec{x} \Vert$를 구할 수 있습니다.

[\begin{aligned} \Vert \vec{x} \Vert^2 = \vec{x}\cdot \vec{x} &= (\vec{a}+\vec{b}+\vec{c})\cdot (\vec{a}+\vec{b}+\vec{c}) \ &=\vec{a}\cdot \vec{a}+\vec{b}\cdot \vec{b}+\vec{c} \cdot \vec{c}
&= \Vert \vec{a} \Vert^2 + \Vert \vec{b} \Vert^2 + \Vert \vec{c} \Vert^2
&= 1 + 4 + 9 = 13
\therefore \Vert \vec{x} \Vert &= \sqrt{13}
\because \vec{a} \cdot \vec{b} &= 0, \vec{b} \cdot \vec{c}=0, \vec{c} \cdot \vec{a} = 0 \quad \text{(Orthogonal)} \end{aligned}]

Orthogonal Subspace

직교하는 부분 공간(Orthogonal subspace)이란 한 부분 공간 내의 모든 벡터가 다른 한 부분 공간 내의 모든 벡터에 대해 직교 관계에 있을 때의 부분 공간 사이의 관계를 말합니다.

대표적인 직교 부분 공간의 예시는 주요 부분 공간(Fundamental subspace)에서 찾을 수 있습니다. 간단한 예시를 통해서 다음 행렬 $A$ 의 주요 부분 공간이 어떻게 그려지는지 알아보겠습니다.

[A = \left[\begin{array}{cc} 1 & 2 \ 3 & 6 \end{array} \right] \xrightarrow{\text{G.E.}} \left[\begin{array}{cc} 1 & 2 \ 0 & 0 \end{array} \right]]

위 식을 사용하여 $A$의 Column space와 Null space를 구할 수 있습니다.

[\mathbf{C}(A) = c\left[\begin{array}{c} 1 \ 3 \end{array} \right] \qquad \mathbf{N}(A) = x_2\left[\begin{array}{c} -2 \ 1 \end{array} \right]]

이번에는 $A^T$를 사용하여 $A$의 Row space와 Left-Null space를 구할 수 있습니다.

[A^T = \left[\begin{array}{cc} 1 & 3 \ 2 & 6 \end{array} \right] \xrightarrow{\text{G.E.}} \left[\begin{array}{cc} 1 & 3 \ 0 & 0 \end{array} \right]
\mathbf{C}(A^T) = c\left[\begin{array}{c} 1 \ 2 \end{array} \right] \qquad \mathbf{N}(A^T) = y_2\left[\begin{array}{c} -3 \ 1 \end{array} \right]]

아래는 위에서 구한 행렬 $A$의 각 주요 부분 공간을 나타낸 것입니다.

위 그래프로부터 Column space 와 Left-Null space가 직교 관계에 있으며 $\mathbf{C}(A) \perp \mathbf{N}(A^T)$, Row space와 Null space가 각각 직교 관계에 있는 것 $\mathbf{C}(A^T) \perp \mathbf{N}(A)$ 을 알 수 있습니다.

Column space 와 Left-Null space, Row space 와 Null space 처럼, 두 부분 공간 $V,W \in \mathbb{R}^n$ 이 있을 때, $V \perp W$ 조건이 성립하며 $\text{Dim}(V) + \text{Dim}(W) = n$ 이면 Orthogonal complement(직교 여공간) 관계에 있다고 합니다.

해당 게시물은 고려대학교 강필성 교수님의 강의를 바탕으로 작성한 것입니다.

Genetic Algorithm

유전 알고리즘(Genetic algorithm)은 메타 휴리스틱 방법론 중 하나의 방법입니다. 유전 알고리즘에 대해 알아보기 전에 먼저 메타 휴리스틱 방법론이 무엇인지에 대해서 알아보겠습니다.

Meta Heuristics

먼저 휴리스틱에 대해 알아보겠습니다. 휴리스틱(Heuristics)이란 무엇일까요? 위키피디아에서 말하는 휴리스틱의 뜻은 다음과 같습니다.

“휴리스틱(heuristics) 또는 발견법이란 불충분한 시간이나 정보로 인하여 합리적인 판단을 할 수 없거나, 체계적이면서 합리적인 판단이 굳이 필요하지 않은 상황에서 사람들이 빠르게 사용할 수 있게 보다 용이하게 구성된 간편추론의 방법이다.”

위에도 나오는 것처럼 휴리스틱은 간편 추론의 방법입니다. 그렇다면 메타 휴리스틱(Meta heuristics)은 무엇일까요? 위키피디아에서는 메타 휴리스틱을 다음과 같이 설명하고 있습니다.

특정문제가 갖는 정보에 크게 구속되지 않고 다양한 문제에 적용가능한 상위수준의 발견적 기법

복잡한 문제를 풀기 위해서 시행착오(Trial and error) 방법을 사용할 때 효과적으로 문제를 풀기 위해서 사용합니다. 메타 휴리스틱을 적용한 최적화 알고리즘 중에는 자연계의 행동을 모사한 방법이 많습니다. 대표적인 경우가 뇌의 활동을 모사한 인공신경망(Artificial neural networks, ANNs), 개미의 이동을 모사한 개미 식민지 최적화(Ant colony optimization, ACO), 조류나 어류 무리의 행동을 모사한 입자 군집 최적화(Particle swarm optimization, PSO) 등이 있습니다.

Genetic Algorithm

유전 알고리즘은 생물의 번식을 모사한 진화 알고리즘입니다. 번식 과정을 반복하면서 더 나은 솔루션을 찾아가며 기존의 솔루션을 보존합니다. 유전 알고리즘을 전진 선택(Forward selection) 및 후진 제거(Backward Elimination) 또는 Stepwise selection 방식과 비교하여 시간-성능 그래프에 나타내면 다음과 같습니다. Stepwise selection 보다 더 오랜 시간이 걸리게 되지만 더 좋은 성능을 보이는 것을 알 수 있습니다.

유전 알고리즘은 다음과 같은 6단계로 진행됩니다. 아래에서 2-5단계에 해당하는 과정은 선택한 변수가 특정한 조건을 만족할 때까지 반복하는 과정입니다.

1. 크로모좀 초기화 및 파라미터 설정(Initiation)
2. 각 크로모좀 선택 변수별 모델 학습
3. 각 염색체 적합도 평가(Fitness evaluation)
4. 우수 염색체 선택(Selection)
5. 다음 세대 염색체 생성(Crossover & Mutation)
6. (조건을 만족하면) 최종 변수 집합 선택

그림으로 나타내면 아래와 같습니다.

이미지 출처 : subscription.packtpub.com

Initialization

첫 번째 단계인 Initialization(초기화)에 대해서 알아보겠습니다. 유전 알고리즘은 생물의 유전 현상을 모사한 것이므로 사용하는 용어 역시 동일한 단어를 사용합니다. 그렇기 때문에 특성을 선택하는 경우 하나하나를 크로모좀(Chromosome, 염색체)라고 합니다. 데이터셋이 $d$ 차원 이라면 크로모좀 역시 $d$ 차원의 벡터가 됩니다. 각 특성을 선택하는 지의 여부를 $0,1$ 로 나타내는 바이너리 인코딩(Binary Encoding)을 사용합니다. 각각의 특성, 그리고 이와 연결된 인코딩 값은 유전자(Gene)라고 표기합니다.

Initialization 단계에서는 이후 알고리즘에서 사용할 도구를 하이퍼파라미터를 설정하여 정하게 됩니다. 첫 번째 하이퍼파라미터는 몇 개의 크로모좀으로 시작할 지를 결정하는 Population 입니다. 이 값을 100으로 설정하면 한 세대에서 100개의 크로모좀이 생성되므로 100개의 변수 부분집합을 평가할 수 있습니다.

두 번째로는 목적 함수에 해당하는 피트니스 함수(Fitness function)를 설정할 수 있습니다. 세 번째로는 교배 방식(Crossover mechanism)을 설정합니다. 네 번째로는 돌연변이 비율을 설정합니다. 마지막으로 종료 기준을 설정하면 모든 설정이 완료됩니다. 일반적으로 종료 기준은 피트니스 함수값의 유의미한 상승을 결정하는 임계값 또는 GA Operation의 최대 반복 횟수로 설정합니다.

각 크로모좀은 이진 벡터 형태이지만 이를 만드는 과정인 Population initialization은 각 값에 랜덤 값을 부여하는 것에서 시작합니다. $[0,1]$ 범위 내의 임의의 값을 각각의 Gene에 부여한 뒤에 Cut-off 값을 기준으로 이진 벡터로 변환합니다. 이런 과정을 통해 임의성을 부여할 수 있습니다. 아래는 Population이 8이고 특성 차원이 10인 경우에 Population initialization을 수행한 예시입니다.

이미지 출처 : github.com/pilsung-kang/Business-Analytics-IME654

Training

그 다음으로는 이렇게 설정된 크로모좀에 따라 각 모델을 훈련시킵니다. 위 사진의 예시를 따르면 다음과 같은 모델들을 학습하게 됩니다.

[\text{Model 1} : \hat{y} = \hat{\beta_0} + \hat{\beta_2}x_2 + \hat{\beta_3}x_3 + \hat{\beta_4}x_4 + \hat{\beta_6}x_6 + \hat{\beta_9}x_9 + \hat{\beta_{10}}x_{10}
\vdots
\text{Model 4} : \hat{y} = \hat{\beta_0} + \hat{\beta_3}x_3 + \hat{\beta_4}x_4 + \hat{\beta_5}x_5 + \hat{\beta_6}x_6 + \hat{\beta_8}x_8 + \hat{\beta_9}x_9
\vdots
\text{Model 8} : \hat{y} = \hat{\beta_0} + \hat{\beta_2}x_2 + \hat{\beta_5}x_5 + \hat{\beta_7}x_7 + \hat{\beta_9}x_9 + \hat{\beta_{10}}x_{10}]

Fitness Evaluation

어떤 크로모좀에 의해 만들어진 모델이 더 나은 것인가를 판단하기 위한 과정입니다. 일반적으로 더 좋은 크로모좀일수록 더 높은 값이 나오도록 함수를 설정합니다. 두 크로모좀이 동일한 변수 개수를 가지고 있을 때에는 더 높은 함숫값을 가진 크로모좀이 선택되어야 하며, 두 크로모좀의 함숫값이 같을 경우에는 더 적은 변수를 가지는 크로모좀을 선택하도록 합니다. 일반적으로 다항 선형 회귀에서는 조정된 결정계수(Adjusted R-square), AIC(Akaike information criterion), BIC(Bayesian information criterion) 등이 있습니다.

각 크로모좀에 대한 수치가 나온 뒤에 처리하는 방법에는 순위(Rank)와 가중치(Weight)의 두 가지 방법이 있습니다. 이 두 방법은 이후 선택(Selection)에서 어떤 방식을 사용할 지에 따라 달라지게 됩니다. 순위 방식에서는 단순하게 더 성능이 좋은, 즉 더 값이 높은 크로모좀의 등수를 매깁니다. 가중치 방식에서는 각각의 크로모좀이 가지는 수치값을 전체 크로모좀의 수치 합으로 나눈 값을 사용합니다.

아래는 조정된 결정계수를 사용하여 각 크로모좀의 평가값을 매긴 뒤에 순위 방식과 가중치 방식을 사용하여 처리해준 것입니다.

이미지 출처 : github.com/pilsung-kang/Business-Analytics-IME654

가중치 값이 어떻게 구해지는지 1, 2번 크로모좀을 통해서 알아보겠습니다. \(\sum_{i=1}^8 (\text{Adj }R^2)_i = 0.75 + 0.78 + \cdots + 0.55 = 4.23 \\ w_1 = 0.75/4.23 = 0.177 \qquad w_2 = 0.78/4.23 = 0.184\)

Selection

선택(Selection)은 어떤 크로모좀을 선택할 것인지를 결정합니다. 위에서 어떤 방식으로 처리해주었는지에 따라서 선택 방식이 갈리게 됩니다. 순위 방식으로 처리하면 결정론적 선택(Deterministic selection)을 사용합니다. 이 방법은 상위 $N\%$ 만 다음 세대로 넘겨주는 방식으로 $N=25$이면 8개의 크로모좀 중 2개의 크로모좀만 선택하게 됩니다. 방법 자체는 매우 간단하지만, 상대적으로 열등한 축에 속하는 크로모좀은 선택되지 못한다는 단점을 가지고 있습니다.

가중치 방식으로 처리하면 확률론적 선택(Probabilistic selection)을 사용합니다. 이 방법은 가중치 비율만큼의 면적을 가진 원판에 다트를 던져 다트가 꽂히는 크로모좀을 선택하는 방식입니다. 아래의 그림을 보며 확률론적 선택법에 대해 알아보겠습니다.

이미지 출처 : github.com/pilsung-kang/Business-Analytics-IME654

먼저 가중치만큼의 범위를 쌓아가면서 $[0,1]$의 누적 가중치 범위를 설정합니다. 그리고 선택하고 싶은 크로모좀 갯수만큼 $[0,1]$범위의 난수를 생성합니다. 위에서는 2개의 크로모좀을 선택하기 위해서 2개의 난수를 생성하였습니다. 그리고 해당 난수가 속하는 범위의 크로모좀을 선택하면 됩니다. 이 방법은 다소 복잡하지만 모든 크로모좀을 선택 후보에 놓을 수 있다는 장점을 가지고 있습니다.

비록 $C_6, C_7$ 등이 선택될 확률 $P(C_6), P(C_7)$은 성능이 좋은 크로모좀인 $C_1, C_2$ 등이 채택될 확률 $P(C_1), P(C_2)$ 보다는 낮지만 일정량의 확률은 보장됩니다.

Crossover & Mutation

다음은 번식이 일어나는 교배(Crossover) 단계입니다. 이 단계에서는 하이퍼파리미터로 교배 지점(Crossover points)의 개수를 지정해주어야 합니다. 교배 지점은 두 크로모좀의 Gene 값을 바꾸는 기준이 되는 점입니다. 이 점을 기준으로 한 쪽은 값을 바꾸게 되며, 다른 한 쪽은 값을 고정하게 됩니다. 특성의 개수가 $N$일 때, 교배 지점의 개수는 $1 \sim N$까지 설정할 수 있습니다.

교배 지점의 개수를 1로 설정했을 때는 다음과 같이 교배가 수행됩니다.

이미지 출처 : github.com/pilsung-kang/Business-Analytics-IME654

교배 지점의 개수를 2로 설정했을 때는 다음과 같이 교배가 수행됩니다.

이미지 출처 : github.com/pilsung-kang/Business-Analytics-IME654

교배 지점의 개수를 N으로 설정했을 때는 다음과 같이 교배가 수행됩니다. 이 때는 모든 Gene이 교배의 대상이 되므로 특성마다 난수를 생성하여 Cut-off 값 이상인 Gene만 교배를 수행합니다. 교배 지점의 개수가 많아질수록 자유도가 높아지는 것이 특징이나 더 높은 자유도가 더 높은 성능을 의미하지는 않습니다.

이미지 출처 : github.com/pilsung-kang/Business-Analytics-IME654

다음은 돌연변이(Mutation)에 대해 알아보겠습니다. 돌연변이를 만들어주는 이유는 알고리즘이 지역 최적점(Local optimum)으로 다가갈 때 빠져나올 기회를 주기 위해서입니다. 하지만 돌연변이의 비율을 높게 설정하면 수렴 시간이 늘어난다는 단점이 있습니다. 그렇기 때문에 일반적으로는 $0.01$ 정도의 값을 사용합니다.

생성되는 각각의 자식 크로모좀의 Gene마다 난수를 부여한 뒤 설정한 값(대개 $0.01$) 이하의 난수가 나온 경우에만 해당 Gene의 값을 바꾸어줍니다. 이 과정을 그림으로 나타내면 다음과 같습니다.

이미지 출처 : github.com/pilsung-kang/Business-Analytics-IME654

Find the Best Solution

마지막으로 최적의 특성을 선택하는 방법입니다. 종료 기준(Stop criteria)을 만족하는 경우에 가장 최적의 크로모좀을 사용하여 특성을 골라냅니다. 반복 과정에서 해 수렴의 안정성을 위해서 한 가지 트릭을 사용합니다. 바로 탑 2를 다음 세대에서 바꾸지 않는 방법입니다. 만약 Population이 100일 때, 이전 세대애서 $C_9, C_{72}$가 가장 높은 성능을 보였다면 다음 세대에서 자식 크로모좀과 바꾸지 않고 그대로 사용합니다. 만약 자식 세대에서 이 둘을 뛰어넘는 성능의 크로모좀이 나오지 않않으면 자신의 자리를 계속 유지하게 됩니다.