[심층 학습] Linear Algebra (1)

12월 정도부터 Ian GoodFellow와 Yoshua Bengio의 Deep Learning이라는 책을 가지고 스터디를 하고 있는데, 난이도가 어느 정도 있는 편이라 차근 차근 정리를 해 나가려고 한다. 본인도 챕터가 지나면 지날 수록 이해가 안가거나 어려운 부분이 있으니 만약 내용이 틀렸거나 수정해야 할 부분이 있다면 댓글로 달아주길 바란다. 또한, 모르는 부분에 있어서는 글로 남겨두고 여러 사람들과 이에 대해 토론할 수 있었으면 좋겠다는 생각이 든다..ㅎㅎ

 

---

선형 대수와 확률 통계는 머신러닝과 딥러닝을 이해하는 데 있어서 중요한 도구로 많이 쓰인다. 이러한 학문의 범위는 매우 넓지만 이 책에서는 딥러닝에 필요한 부분만을 추려서 소개한다. 

 

1. Scalars, Vectors, Matrices and Tensors

 

• Scalars: 하나의 수(ex. 100)
• Vectors: 수들의 집합(ex. [1, 2, 3, 4, 5])
• Matrices: 수들의 2차원 배열(ex. [[1, 2],[3,4], [5,6]])
• Tensors: 수들의 고차원 배열

1.1 Transpose

figure 1) Transpose

Transpose는 중요한 operation 중 하나로, diagonal line(dashed line in figure 1)을 중심으로 matrix를 뒤집는 연산이다. 말로만 들으면 어렵지만 결국 행 index와 열 index를 바꾸어주는 것이다.

$$(A^T)_{i,j} = A_{j,i}$$

 

Vector는 한 column만을 가지는 matrix라고 생각할 수 있고, 이의 Transpose는 하나의 row만을 가지는 matrix가 된다. 기본적으로 vector는 열 벡터이기 때문에 다음과 같이 행 벡터와 transpose를 사용하여 표현한다.

$$Column \ Vector: \ \ [x_1, x_2, x_3]^T$$

 

Scalar는 하나의 entry만을 가지는 matrix라고 생각할 수 있고, 이의 transpose는 그냥 그 entry가 된다.

$$ a = a^T$$

 

1.2 Add and Multiply

Matrix는 서로 간 element-wise add가 가능하다. 이를 식으로 나타내면,

$$ C = A + B \ \ \ where \ \ C_{i,j} = A_{i,j} + B_{i,j}$$

**i와 j는 각 행과 열의 index를 나타낸다.

 

Scalar는 Matrix와 element-wise add 및 element-wise multiplication이 가능하다. 이를 식으로 나타내면,

$$ D = a \cdot B + c \ \ \ where \ \ D_{i,j} = a \cdot B_{i,j} + c$$

 

2. Multiplying Matrcies and Vectors

두 matrix간 곱은 가장 많이 쓰이는 연산 중 하나이다. 이는 matrix product라 하고, m x n 행렬 A와 n x p 행렬 B의 matrix product는 m x p 행렬 C가 된다. 이때, A의 열 차원과 B의 행 차원은 무조건 같아야 성립한다.

$$C = AB$$

$$C_{i, j} = \sum_k A_{i,k}B_{k, j}$$

 

**위의 product 연산과 다르게 element-wise multiplication을 사용해야 될 때도 있다. 이럴 때의 행렬 곱을 element-wise product 또는 Hadamard product라고 부르고, 이를 $A \odot B$로 표현한다.

 

matrix product의 자세한 예는 다음 위키를 참조하길 바란다.

https://en.wikipedia.org/wiki/Matrix_multiplication

Matrix multiplication - Wikipedia

 

Matrix Product는 많은 유용한 특성을 가진다. 

1. Distributive: A(B+C) = AB + AC
2. Associative: A(BC) = (AB)C
3. Commutative: matrix는 commutative가 성립되지 않는다($AB \neq BA$), 하지만 vector의 경우는 commutative가 성립한다($x^Ty = y^Tx$)
4. Transpose of matrix product: $(AB)^T = B^TA^T$

추가로 Vector product의 transpose의 경우, column vector와 row vector의 product는 scalar이기 때문에 기존과 같다.

$$x^Ty = (x^Ty)^T = y^Tx$$

 

2.1 Linear Equation

Linear Equation는 matrix A와 vector x의 dot product로 이루어진다.

$$Ax = b$$

**$A \in \mathbb{R}^{m \times n}$, $b \in \mathbb{R}^m$, $x \in \mathbb{R}^n$

 

이를 더 자세히 표현하면,

$$A_{1,1}x_1 + A_{1,2}x_2 + \dots + A_{1, n}x_n = b_1$$

$$A_{2,1}x_1 + A_{2,2}x_2 + \dots + A_{2, n}x_n = b_2$$

$$\dots$$

$$A_{m,1}x_1 + A_{m,2}x_2 + \dots + A_{m, n}x_n = b_m$$

 

3. Identity and Inverse Matrices

Identity matrix

Identity matrix는 어떠한 vector와 곱해지더라도 값이 변하지 않는 matrix를 말한다.

$$\forall x \in \mathbb{R}^n, \ I_nx=x$$

matrix는 diagonal entries는 모두 1이고 그 외 entries는 모두 0의 값을 가진다.

 

Inverse Matrix

inverse matrix는 다음으로 정의할 수 있다.

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

즉, 원래 matrix와 곱해졌을 때 identity matrix가 되는 matrix를 말한다. 이 matrix inversion을 사용해서 이전의 linear equation의 해를 구할 수 있다.

$$Ax=b$$

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

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

물론 이는 inverse matrix인 $A^{-1}$가 존재한다는 가정이 포함되어있다. 이러한 inversion matrix를 사용해 해를 구하는 방식은, 디지털 컴퓨터가 수치를 표현하는 precision에 제한이 있기 때문에, 대부분의 software application에는 거의 사용되지 않는다.

 

**작은 matrix는 상관없을 수 있지만, matrix가 커지게 되면 $A^{-1}$을 구하는 수식이 복잡해지고 그 값 또한 깔끔하지 않게 나오기 때문에 limited precision에 의해 정확한 해를 구하는 것이 어렵다.

 

4. Linear Dependence and Span

$A^{-1}$이 존재하기 위해서는 모든 b에 대해서 하나의 해만이 존재해야한다. 하지만 경우에 따라 해가 존재하지 않을 수도 있고 또는 해가 무한하게 많이 있을 수도 있다. 또한, 해가 무한히 존재하지 않으면서 하나보다 더 많은 경우는 존재할 수가 없다.

 

그 이유는 만약 x와 y가 모두 방정식의 해라고 할 때, 

$$z=\alpha x + (1-\alpha)y$$

z 또한 모든 실수 $\alpha$에 대해서 해가 되기 때문이다.

 

이는 다음과 같이 증명할 수 있다.

$$Az = \alpha Ax + (1-\alpha)Ay$$

$$Az = \alpha b + (1-\alpha)b$$

$$Az = b$$

 

Linear Combination

얼마나 많은 해가 존재하는지 분석하기 위해서, matrix A를 여러 개의 column vector의 집합으로 생각해볼 수 있다. 이 때 x는 각 vector direction으로 얼마나 이동할지를 나타내는 변수이다.

examples

$$Ax=\sum_i x_iA_{:,i}$$

일반적으로 이러한 operation을 "linear combination" 이라고 부른다.

 

Span of column vectors

여기서 벡터들의 집합($A_{:,i}$)에 대한 "span"은 벡터들의 linear combination으로 얻을 수 있는 모든 points들의 집합을 의미한다. 예를 들어, 벡터 [0,1]과 [1,0]은 linear combination을 통해 2차원 상의 모든 점을 표현할 수 있으므로 span이 2차원 공간이 된다.

 

$Ax=b$가 해를 가지는지를 설명할 때, b가 A의 column vector들의 span에 속하는지를 보는데 이러한 특정한 span을 "column space"라고 부른다.

**b가 colmun space에 속하지 않으면 해가 존재하지 않을 것이다.

 

Requirements of having solution

$Ax=b$가 모든 값 $b \in \mathbb{R}^m$에 대해서 해가 존재하기 위해서는 A의 column space가 $\mathbb{R}^m$이 되어야 한다. 만약 하나의 점이라도 column space에 속하지 않는다면, 그 점에서의 해는 존재하지 않게 된다.

 

기본적으로 column space가 $\mathbb{R}^m$이 되기 위해서는, A가 적어도 m columns를 가져야 한다($n\ge m$). 그렇지 않으면 column space가 m보다 작아지므로 해가 없는 b가 생기게 된다. 예를 들어 3x2 matrix A와 3차원 b를 생각해보자. target b는 3차원인데 $x$는 2차원이 되므로, $x$를 아무리 바꾸어봐도 표현할 수 있는 공간은 $\mathbb{R}^3$ 내의 2차원 평면이 된다. 즉, 해당 2차원 평면에 있는 b에 대해서는 해가 존재하지만, 그 외의 공간에서는 해가 존재하지 않는다.

 

Linear independence

단, $n\ge m$ 조건은 모든 점에서 해를 가지기 위한 필수 조건이지 충분 조건은 아니다. 그 이유는 중복 columns이 있을 수 있기 때문이다.  위 예에서, matrix A가 2x2 이고 $b \in \mathbb{R}^2$라 할 때, $n \ge m$을 만족하지만 두 column vector가 같기 때문에 나타낼 수 있는 span이 1차원 line에 한정된다.

 

이러한 redundancy를 "linear dependence"라고 부른다. 반대로 "linearly independent"라는 것은 어떠한 벡터도 다른 벡터들의 linear combination으로 나타내지 못하는 경우를 말한다. 만약 A가 3차원 columns vector를 3개($a_1, a_2, a_3)$ 가지는 matrix라  할 때, 만약 $a_1$이 $a_2$와 $a_3$의 linear combination으로 만들 수 있는 vector라면, $a_1$은 column space에 어떠한 변화도 주지 못하는 vector가 된다. 왜냐면 이미 $a_2$와 $a_3$로 만들 수 있는 column space에 $a_1$이 속해 있기 때문이다. 따라서 linear equation이 해를 갖기 위해서는 m개의 linearly independent columns를 가지고 있어야 한다.

 

또한 matrix가 inverse를 갖기 위해서는, $Ax=b$식이 모든 $b$에 대해서 최대 하나의 해만 가져야 한다. 그렇기 위해서는 matrix가 최대 m columns만을 가져야 한다. 만약 그 이상의 linearly independent columns가 있다면 해를 parameterizing하는 방법이 하나 이상 존재할 수 있다. 

 

결국에는 matrix가 square(m=n)이어야 한다는 것이다. square matrix인데 linearly dependent columns를 가지면 "singular", 그렇지 않으면 "non-singular"라고 한다. 만약 A가 square가 아니거나 singular라도 방정식의 해를 찾을 수는 있다. 하지만 matrix inversion이 존재하지 않기 때문에 이를 통해 해를 구할 수는 없게 된다.