Ch2. Linear Algebra

TIMESTAMP

@200918 : PDF 정리 시작 (~가역행렬까지)
@200919 : PDF 정리 완료 (노름~)
@200919 : 본문 정리 시작 (~2.1)

들어가기전에

About this chapter

• 선형대수학은 과학과 공학 분야에 폭 넓게 사용되어 왔지만, 이산 수학(discrete)보다는 연속적인 형태(continuous)로 인해 상대적으로 컴퓨터 과학 분야에서는 잘 다뤄지지 않았다. 선형대수를 잘 이해하는 것은 많은 머신러닝 알고리즘이나 특히 딥러닝을 이해하고 수행하는데 필수적이다.
• 따라서 본 챕터를 통해서 필수적으로 알아야할 필수 선형대수 개념들을 다루고 본격적으로 딥러닝을 소개하고자 한다. 이번 챕터에서는 선형대수학 전체가 아닌 딥러닝에 관련된 부분만을 다룬다.

Scalars, Vectors, Matrices and Tensors

Scalars

• 스칼라는 정수, 실수, 유리수 등 하나의 숫자로 여기서는 이탤릭체로 표기한다
  $a,n,x$

예시

• 실수 스칼라 $s\in\R$
• 정수 스칼라 $n\in\N$

Vectors

• 벡터는 1차원 배열(1D array)로 실수, 이진수, 정수 등이 될 수 있다. 종류와 크기에 따라서 다음과 같이 쓰며, 소문자 볼드체로 표기한다.
  $\bm{x} = \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix} \in \R^n$
• 순서에 따라 정렬되며, 인덱스(index)를 통해 각 숫자를 파악할 수 있다.
• 벡터는 공간에서의 점들로 생각할 수 있으며, 각 요소는 축에서의 좌표값을 제공한다.

예시 : 인덱스를 통해 벡터의 일부를 표현할 수 있다.

• if $S=\{1,3,6\}$, then $\bm{x}_S=\begin{bmatrix}x_1\\x_3\\ x_6\end{bmatrix}$
• 그 외에도, $\bm{x}_{-1}, \bm{x}_{-S}$ 등으로 표기할 수 있다.

Matrices

• 행렬은 2차원 배열(2D array)로 종류와 크기에 따라서 다음과 같이 쓴다. 행렬은 대문자 볼드체로 표기하고, 행렬의 원소는 이탤릭체를 쓰지만 볼드를 쓰지 않는다.
  $\bm{A}= \begin{bmatrix} A_{1,1} & A_{1,2} \\ A_{2,1} & A_{2,2} \end{bmatrix} \in\R^{m\times n}$

예시 : $f(\bm{A})_{i,j}$는 함수 $f$를 취한 행렬 $\bm{A}$의 각 요소 $(i,j)$를 의미한다

Tensors

• 텐서는 다차원의 숫자의 배열로 0부터 고차원이 될 수 있다.
  • 스칼라(0차원), 벡터(1차원), 행렬(2차원) 등

예시 : $\mathbf{A}$와 같은 형태로 표현하며, 각 좌표 $(i,j,k)$에 대한 $\mathbf{A}$의 요소는 $A_{i,j,k}$로 나타낼 수 있다.

Matrix Transpose

• 행렬의 전치(transpose)는 중심 대각선(main diagonal)을 기준으로 하는 거울상으로 생각할 수 있다.
  

• 전치행렬은 $\bm{A}^\top$로 표기한다.

  $(\bm{A}^\intercal)_{i,j}=A_{j,i} \\ \quad \\ (\bm{AB})^\top=\bm{B}^\top\bm{A}^\top$

[예제1] 벡터와 스칼라

• $\bm{x}=[x_1,x_2,x_3]^T$
  벡터는 열이 하나인 행렬로, 벡터의 전치는 행이 하나인 행렬이 된다.
• $a=a^\top$
  스칼라는 값 하나를 가지는 행렬로, 스칼라는 자기 자신을 전치행렬로 가진다.

[예제2] 행렬의 연산

• $\bm{C=A+B}$ where $C_{i,j}=A_{i,j}+B_{i,j}$
• $\bm{D}=a \cdot \bm{B}+c$ where $D_{i,j}=a\cdot B_{i,j}+c$

[예제3] 딥러닝에서의 브로드캐스팅

• $\bm{C=A+b}$ where $C_{i,j}=A_{i,j}+b_j$
  벡터 $\bm{b}$가 행렬의 각 행에 더해질 수 있고, 이처럼 많은 곳에 해당 벡터를 복사하는 것을 broadcasting이라고 한다.

Multiplying Matrices and Vectors

Matrix (Dot) Product

Identity Matrix

Systems of Equations

Solving Systems of Equations

• 선형 연립방정식은
  (1) 해가 없거나
  (2) 여러 해를 가지거나
  (3) 단 하나의 해를 가진다

Matrix Inversion

• 이를 이용하여 연립방정식을 풀 수 있다.
  $\bm{A}\bm{x}=\bm{b} \\ \bm{A}^{-1}\bm{A}\bm{x}=\bm{A}^{-1}\bm{b} \\ \bm{I}_n\bm{x}=\bm{A}^{-1}\bm{b}$

Invertibility

• 다음과 같은 경우에는 역행렬을 만들 수 없다.
  • 행이 열보다 많을 때
  • 열이 행보다 많을 때
  • "linearly dependent", "low rank"

Norms

• 노름은 벡터의 크기를 나타내는 것으로, 0부터 해당 벡터의 지점까지의 거리와 유사하다.

• $L^p$ norm

  $||\bm{x}||_p = (\sum_i|x_i|^p)^\frac{1}{p}$
  • L2 norm ($p$=2)
  • L1 norm ($p$=1) : $||x||_1=\sum_{i}|x_i|$
  • Max norm (infinite $p$) : $||x||_\infty=\max_{i}|x_i|$

Special Matrices and Vectors

• Unit vector

• Symmetric matrix

• Orthogonal matrix
  $\bm{A}^\top\bm{A}=\bm{A}\bm{A}^\top=\bm{I} \\\quad\\ \bm{A}^{-1}=\bm{A}^\top$

Eigendecomposition

• 고유벡터와 고유값
  (eigenvector, eigenvalue)
  $\bm{Av} = \lambda \bm{v}$
• 대각화 가능 행렬의 고유값 분해
  (eigendecomposition of a diagonalizable matrix)
  $\bm{A} = \bm{V}diag(\bm{\lambda})\bm{V}^{-1}$
• 모든 실수 대칭행렬은 직교하는 교유값 분해가 있다.
  (orthogonal eigendecomposition)

Effects of Eigenvalues

Singular Value Decomposition

• 특이값 분해는 고유값 분해와 유사하지만 좀 더 일반화된 형태로, 꼭 사각행렬일 필요가 없다.
  $\bm{A=UDV^\top}$

Moore-Penrose Pseudoinverse

1. 오직 하나의 해를 가질 경우 : 역행렬과 동일하다
2. 해가 없을 경우 : $||\bm{Ax-y}||_2$ 오차가 최소는 지점
3. 많은 해를 가질 경우 : $\bm{x}$의 노름이 최소가 되는 지점

Computing the Pseudoinverse

• SVD를 통해 의사역행렬의 계산이 가능하다
  $\bm{A^+=VD^+U^\top}$
  Take reciprocal of non-zero entries

Trace

• 대각합
  $\operatorname{Tr}(\bm{A})=\sum_{i}\bm{A}_{i,i} \\\quad\\ \operatorname{Tr}(\bm{ABC})=\operatorname{Tr}(\bm{CAB})=\operatorname{Tr}(\bm{BCA})$

Learning linear algebra

• Do a lot of practice problems
• Start out with lots of summation signs and indexing into individual entries
• Eventually you will be able to mostly use matrix and vector product notation quickly and easily