Linear Algebra for ML

---

2. Linear Algebra

---

2.1 Scalars, Vectors, Matrices and Tensors

• Scalars : 스칼라는 선형수학에서 보는 형태와 달리 하나의 단어로 표현되며 주로 이탈릭체를 사용한다. 실수인지 자연수인지 등의 어떤 형태의 수인지 주로 함께 서술하여 준다. 예) a
• Vectors : 수의 열로 되어있는 형태를 가진다. 각 수(element)는 인덱스로 그 순서를 표현하며 벡터는 주로 소문자에 굵은체를 사용한다.

$$\mathbf{x} = \begin{bmatrix} x_{1} \\ x_{2} \\ \vdots \\ x_{n} \end{bmatrix}$$

• Matrices : 매트릭스는 벡터를 옆으로 붙인 형태로 2차원의 배열을 가진다. 각 수(element)는 두개의 인덱스로 구분될수 있다. A = 3 > 매트릭스 A의 첫 번째 행과 두 번째 열의 수는 3이라는 것을 의미한다.

  $$\mathbf{A} = \begin{bmatrix} A_{1,1}\ A_{1,2} \\ A_{2,1}\ A_{2,2} \\ \vdots \\ A_{n,1}\ A_{n,2} \end{bmatrix}$$

• Tensors : 어떤 경우에는 우리는 2차원 이상으로 이루어진 수의 형태가 필요하다. 텐서를 쉽게 생각하기 위해서는 각 매트릭스가 element로 이루어진 vector를 생각하면 상상하기 쉽다. 선형대수학에서 스칼라는 rank 0의 텐서, 벡터는 rank 1의 텐서, 매트릭스는 rank 2의 텐서이다. Arial 폰트의 굵은 굵기로 텐서를 표현한다.

• main diagonal : 매트릭스에서 가장 왼쪽, 가장 위쪽부터 하나씩 내려오며 하나씩 오른쪽으로 이동하며 만나는 element들의 집합을 main diagonal이라고 한다.

• transpose : 매트릭스에서 가장 중요한 operation중 하나이며 main diagonal를 기준으로 반사된 형태를 만드는 작업이다.

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

• 벡터는 하나의 열로만 이루어진 매트릭스로 볼 수 있으며 벡터에 Transpose를 가하면 하나의 행을 가지는 매트릭스가 된다.

• 행으로 이루어진 매트릭스를 가끔씩 식에서 볼 수 있으며 그럴땐 다시 transpose를 적용해 column vector로 변형할 수 있다

$$\mathbf{x} = [x_1,x_2, ... x_n]^T$$

2.2 Multiplying Matrices and Vectors

• matrix product : 매트릭스 곱의 결과물 A가 $m \times n$, B가 $n \times p$ 매트릭스의 경우 처럼 A의 열 차수와 B의 행 차수가 같아야 $AB = C$의 경우처럼 $C (m \times p)$ 매트릭스를 가질 수 있다.

• AB = C가 성립된다고 BA 의 곱이 성립되는 것이 아니다.

  $$C_{i,j} = \sum_kA_{i,k}B_{k,j}$$

• 매트릭스의 각 element끼리 곱하여 매트릭스를 생성하는 것은 element-wise product 혹은 Hadamard product라고 한다.

• 벡터 계산에서 쓰이는 dot product는 같은 차수의 벡터 x와 y를 x를 transpose하여 매트릭스 곱을 하는 것과 같다.
  매트릭스의 곱은 다음과 같은 특징을 가진다.

• Distributive
  $A(B+C) = AB + AC$

• Associative
  $A(BC) = (AB)C$

• 단 commutative하지 않다.
  $AB != BA$

• 하지만 vector의 dot product는 commutative하다.

  $$x^Ty = y^Tx$$

• Transpose of a matrix product has a simple form

  $$(AB)^T = B^TA^T$$

• on vector

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

• a system of linear equation

$$Ax=b$$

$\text{where A is m x n matrix, b is m x 1 vector, and x is n x 1 vector}$

2.3 Identity and Inverse Matrices

• matrix inversion 으로 matrix equation 을 풀 수 있다.
• matrix inversino을 이해하기 위해서는 Identity matrix에 대한 이해가 필요하다.
• Identity matrix : square marix이며 main diagonal의 모든 element에는 1이 값으로 존재하며 나머지 element는 0인 매트릭스다.

Matrix Inverse

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

solving matrix equation with inverse

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

• 강력한 tool이지만 software engineering에서는 사용하는 것이 제한적인 것이 현실이다.

2.4 Linear Dependence and Span

• Inverse가 존재하기위해선 Ax=b의 식에서 반드시 단 하나의 solution이 존재해야 한다.
• Linear combination : set에 존재하는 vector의 조합 혹은 scalar를 곱하여 조합하여 만들어낸 vector
• Span : Linear combination의 모든 point들의 집합이다.
• Column space / Range of A : matrix equation에서 column들의 span을 의미한다.
• Linear dependence : vector들이 각각 서로서로 Linear combination이 아닌 상태를 의미한다.

종합적으로 매트릭스가 inverse가 되려면…

• solution이 하나만 존재
• A 매트릭스가 최대 m column이 존재
• 종합하면 매트릭스가 square의 형태여야 한다 ⇒ m = n
• Singular matrix : square matrix with linear independence
• singular가 아니더라도 solution을 구할 수 는 있지만 matrix inversion을 쓸 수 없다.

2.5 Norms

• Norm : one of measuring size of vector.

$$L_pnorm = ||x||_p = \left( \sum_i|x_i|^p \right)^{1/p}$$

$\text{for p in }\mathbb{R},\ p \geq 1$

• a norm is any function f that staisfies the following properties
  • f(x) = 0 ⇒ x = 0
  • f(x+y) ≤ f(x) + f(y) (the Triangle Inequality)
  • for all alpha, f(alpha x) = |x|f(x)

L2 norm (Euclidean norm)

$$L_2norm = ||x||_2 = \left(\sum_i |x_i|^2\right)^{1/2}$$

자주 쓰이기 때문에 ||x||로 많이 표기됨

• squared L2 norm이 수학적으로 컴퓨터로 처리하기 수월하다.
• the derivatives of the squared L2 norm with respect to each element of x each depend only on the corresponding element of x, while all of the derivatives of the L2 norm depend on the entire vector.

L1 norm

$$L_1norm = ||x||_1 = \sum_i|x_i|$$

• L1 norm 은 zero와 nonzero의 차이가 중요할때 ML에서 자주 쓰인다.

Max norm

$$||x||_\infty = \max_i|x_i|$$

||x||∞ = maxi|xi|

Frobenius norm - size of matrix

$$||A||_F = \sqrt{\sum_{i,j}A^{2}_{i,j}}$$

• 벡터의 L2 norm과 비슷한 형태를 가진다.

두 벡터의 dot product를 norm의 형태로 다시 쓴 형태

$$x^Ty = ||x||_2||y||_2cos\theta$$

• θ 는 x와 y 사이의 각도이다.

2.6 Sepcial Kinds of Matrices and Vectors

• unit vector : unit norm을 가지는 벡터

$$||x||_2 = 1$$

• orthogonal : 벡터 x와 벡터y가 x^Ty = 0의 값을 가지면 orthogonal 하다고 한다. 직관적으로 벡터 차원에서 직각을 이루는 것을 의미한다. orthogonal을 이루고 unit norm을 가지면 orthonormal이라고 한다.
• orthogonal matrix: 매트릭스의 행들이 orthonormal하고 열들이 orthonormal한 square 매트릭스를 의미한다.

$$A^TA = AA^T = I$$

this implies that

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

2.7 Eigendecomposition(고유값 분해)

• 수를 인수분해하는 것 처럼 매트릭스를 분해하여 매트릭스의 특징을 한번에 나타내는 형태로 분해한다.
• eigendecomposition : 매트릭스를 eigenvector와 eigenvalue로 분해 하는 것

• eigenvector: non-zero벡터인 v가 다음을 만족하는 것을 의미한다.

  $$\mathbf{A}v = \lambda v$$

  여기서 lambda는 eigenvalue이며 eigenvector v와 매칭한다.

  Eigendecomposition

  $$\mathbf{A} = \mathbf{V}diag(\lambda)\mathbf{V}^{-1}$$

  V는 Linearly independent한 eigenvector을 옆으로 붙여 구성한 매트릭스이며 diag(lambda)는 각 eigenvector에 매칭하는 eigenvalue를 main diagonal로 가지는 매트릭스이다.

  • 모든 매트리스가 eigendecomposition이 가능 한 것은 아니다.

하지만 이 책에서는 간단한 분해가 가능한 매트릭스만 다룬다. 실수 + symmetric 한 매트릭스는 실수로만 구성된 eigenvector와 eigenvalue로 분해할 수 있다.

$$A = QΛQ^T$$

여기서 Q는 eigenvector로 이루어진 orthogonal matrix이며 Lambda는 eigenvalue의 diagonal matrix이다.

• 여기서 symmetric한 매트릭스 A는 eigendecomposition이 보장되어있지만 분해가 고유하지는 않을 수 있다.

2.8 Singular Value Decomposition (SVD)

• Eigendecomposition과 같은 성격을 가지며 Singular Value Decomposition은 매트릭스를 singular vector와 singular value로 분해한다.
• eigendecomposition보다 좀 더 일반적으로 적용이 가능하다.
• 모든 실수의 매트릭스는 SVD가 가능하다.

$$A=UDV^T$$

• U와 V는 orthogonal matrix이다.
• D는 diagonal 매트릭스이며 반드시 square 매트릭스는 아니다.
• U의 벡터들은 left-singular vector V의 colmn 벡터들은 right-sigular vector라고 불린다.
• SVD의 가장 유용한 기능은 부분적으로 non-square matrix로의 매트릭스 inversion을 generalize 하는 것이다.

2.9 The Moore-Penrose Pseudoinverse

• Ax = y를 풀기 위해 A의 inverse인 B를 구한다고 가정하자.
• x = By의 형태를 가져야하는데 이것이 불가능한 경우 적용하는 것이 Moore-Penrose Pseudoinverse이다.

$$A^+ = VD^+U^T$$

• 여기서 U,D,B는 A의 SVD를 이용하여 구한다.
• D+는 D의 non-zero element를 reciprocal을 취한후 transpose하여 구한다.

2.10 The Trace Operator

• trace opearator는 diagonal entry들의 합을 쉽게 표현해 준다.

$$Tr(A) = \sum_iA_{i,i}$$

• Frobenius norm

$$||A||_F = \sqrt{Tr(AA^T)}$$

• 특징

$$Tr(A) = Tr(A^T) \\ Tr(ABC) = Tr(CAB) = Tr(BCA)$$

2.11 The Determinant

• square matrix가 가지며 det(A)라고 표현된다. 혹은 |A|라고 표현한다.
• det(A)는 product of all eigenvalues와 같다.

$$| \mathbf{A}| = \left| \begin{bmatrix} a\ \ b \\ c\ \ d \end{bmatrix} \right| = ad - bc$$

2.12 Example: Principal Component Analysis

Continue…