[TIL Day28] Machine Learning 기초 - Matrix Calculus

이전 게시글과 이어서 작성하였다.

3. 중요 연산과 성질들 (Operations and Properties)

전치 (Transpose)

행렬을 전치하는 것은 그 행렬을 뒤집는 것으로 생각할 수 있다.
행렬 $A\in \mathbb{R}^{m\times n}$이 주어졌을 때 그것의 전치행렬은 $A^T \in \mathbb{R}^{n\times m}$으로 표시하고 각 원소는 다음과 같이 주어진다.

$\left( A^T \right)_{ij} = A_{ji}$

• 행렬의 전치 시 성립하는 성질들
  - $(A^T)^T = A$
  - $\left(AB\right)^T = B^TA^T$
  - $(A + B)^T = A^T + B^T$

• numpy의 T 속성을 사용해서 전치행렬 구하기

A = np.array([
    [1,2,3],
    [4,5,6]
])

A.T
## output
# array([[1, 4],
#       [2, 5],
#       [3, 6]])

대칭행렬 (Symmetic Matrices)

정방행렬 $A$가 $A^T$와 동일할 때 대칭행렬이라고 부른다. $A = -A^T$일 때는 반대칭(anti-symmetric)행렬이라고 부른다.

• $AA^T$는 항상 대칭행렬이다.
  $(AA^T)^T = (A^T)^TA^T=AA^T$

• $A + A^T$는 대칭, $A - A^T$는 반대칭이다.

$A = \frac{1}{2}(A+A^T)+\frac{1}{2}(A-A^T)$

대각합 (Trace)

정방행렬 $A\in \mathbb{R}^{n\times n}$의 대각합은 $\mathrm{tr}(A)$로 표시(또는 $\mathrm{tr}A$)하고 그 값은 $\sum_{i=1}^n A_{ii}$이다. 대각합은 다음과 같은 성질을 가진다.

• 대각합의 성질
  - For $A\in \mathbb{R}^{n\times n}$, $\mathrm{tr}A = \mathrm{tr}A^T$
  - For $A,B\in \mathbb{R}^{n\times n}$, $\mathrm{tr}(A+B) = \mathrm{tr}A + \mathrm{tr}B$
  - For $A\in \mathbb{R}^{n\times n}, t\in\mathbb{R}$, $\mathrm{tr}(tA) = t\,\mathrm{tr}A$
  - For $A, B$ such that $AB$ is square, $\mathrm{tr}AB = \mathrm{tr}BA$
  - For $A, B, C$ such that $ABC$ is square, $\mathrm{tr}ABC = \mathrm{tr}BCA = \mathrm{tr}CAB$, and so on for the product of more matrices (여러 행렬의 곱이 정방행렬일 때, cycle을 따라서 순서를 바꾸어 곱해도 그 대각합은 같다.)

• numpy의 trace 속성으로 대각합 구하기

A = np.array([
        [100, 200, 300],
        [ 10,  20,  30],
        [  1,   2,   3],
    ])
np.trace(A)
## output
# 123

Norms

벡터의 norm은 벡터의 길이로 이해할 수 있다.
$l_2$ norm (Euclidean norm)은 다음과 같이 정의된다.

$\left \Vert x \right \|_2 = \sqrt{\sum_{i=1}^n{x_i}^2}$

• numpy.linalg로 norm 구하기

import numpy.linalg as LA
LA.norm(np.array([3, 4]))
## output
# 5.0

• $\left \Vert x \right \|_2^2 = x^Tx$(자기자신과의 내적값)임을 기억하라.

• $l_p$ norm
  $\left \Vert x \right \|_p = \left(\sum_{i=1}^n|{x_i}|^p\right)^{1/p}$

• Frobenius norm (행렬에 대해서 정의)
  $\left \Vert A \right \|_F = \sqrt{\sum_{i=1}^m\sum_{j=1}^n A_{ij}^2} = \sqrt{\mathrm{tr}(A^TA)}$
  - 증명
  
  

A = np.array([
        [100, 200, 300],
        [ 10,  20,  30],
        [  1,   2,   3],
    ])

LA.norm(A)
## output
# 376.0505285197722

np.trace(A.T.dot(A))**0.5
## output
# 376.0505285197722

선형독립과 Rank (Linear Independence and Rank)

벡터들의 집합 $\{x_1,x_2,\ldots,x_n\}\subset \mathbb{R}^m$에 속해 있는 어떤 벡터도 나머지 벡터들의 선형조합으로 나타낼 수 없을 때 이 집합을 선형독립(linear independent)이라고 부른다.
역으로 어떠한 벡터가 나머지 벡터들의 선형조합으로 나타내질 수 있을 때 이 집합을 (선형)종속(dependent)이라고 부른다.

• Column Rank
  - 행렬 $A\in \mathbb{R}^{m\times n}$의 열들의 부분집합 중에서 가장 큰 선형독립인 집합의 크기

• Row Rank
  - 행렬 $A\in \mathbb{R}^{m\times n}$의 행들의 부분집합 중에서 가장 큰 선형독립인 집합의 크기

• rank의 성질
  - 모든 행렬의 column rank와 row rank는 동일, $rank(A)$로 표시
  - For $A\in \mathbb{R}^{m\times n}$, $\mathrm{rank}(A) \leq \min(m, n)$. If $\mathrm{rank}(A) = \min(m, n)$, then $A$ is said to be full rank.
  - For $A\in \mathbb{R}^{m\times n}$, $\mathrm{rank}(A) = \mathrm{rank}(A^T)$.
  - For $A\in \mathbb{R}^{m\times n}, B\in \mathbb{R}^{n\times p}$, $\mathrm{rank}(A+B) \leq \min(\mathrm{rank}(A), \mathrm{rank}(B))$.
  - For $A, B\in \mathbb{R}^{m\times n}$, $\mathrm{rank}(A+B) \leq \mathrm{rank}(A) + \mathrm{rank}(B)$.

• numpy.linalg의 matrix_rank를 사용해서 쉽게 구할 수 있다.

역행렬 (The Inverse)

정방행렬 $A\in \mathbb{R}^{n\times n}$의 역행렬 $A^{-1}$은 $A^{-1}A = I = AA^{-1}$을 만족하는 정방행렬($\in \mathbb{R}^{n\times n}$)이다.
$A$의 역행렬이 존재할 때, $A$를 invertible 또는 non-singular하다고 말한다.

• 역행렬의 성질들
  - $A$의 역행렬이 존재하기 위해선 $A$는 full rank여야 한다.
  - $(A^{-1})^{-1} = A$
  - $(AB)^{-1} = B^{-1}A^{-1}$
  - $(A^{-1})^T = (A^T)^{-1}$

• numpy.linalg의inv로 역행렬을 구할 수 있다.

직교 행렬 (Orthogonal Matrices)

$x^Ty=0$가 성립하는 두 벡터 $x, y \in \mathbb{R}^n$를 직교(orthogonal)라고 부른다.
$\|x\|_2 = 1$인 벡터 $x\in \mathbb{R}^n$를 정규화(normalized)된 벡터라고 부른다.
모든 열들이 서로 직교이고 정규화된 정방행렬 $U\in \mathbb{R}^{n\times n}$를 직교행렬이라고 부른다.

• 직교행렬의 성질들
  - $U^TU = I$
  
  - $UU^T = I$ (이건 밑에서 증명)
  - $U^{-1} = U^T$ ($U^TU = I = UU^T$이 성립하며 이것은 역행렬의 정의와 동일)
  - $\|Ux\|_2 = \|x\|_2$ for any $x\in \mathbb{R}^{n}$
  

치역(Range), 영공간(Nullspace)

벡터의 집합($\{x_1,x_2,\ldots,x_n\}$)에 대한 생성(span)

벡터 $x_i$들의 (모든 실수 $a_i$에 대한)선형조합으로, 벡터들의 집합이므로 공간을 이룬다.

$\mathrm{span}(\{x_1,x_2,\ldots,x_n\}) = \left\{ v : v = \sum_{i=1}^n\alpha_i x_i, \alpha_i \in \mathbb{R} \right\}$

행렬의 치역 (range)

행렬 $A\in \mathbb{R}^{m\times n}$의 치역 $\mathcal{R}(A)$는 A의 모든 열들에 대한 생성(span)이다.

$\mathcal{R}(A) = \{ v\in \mathbb{R}^m : v = Ax, x\in \mathbb{R}^n\}$

영공간 (nullspace)

행렬 $A\in \mathbb{R}^{m\times n}$의 영공간(nullspace) $\mathcal{N}(A)$는 $A$와 곱해졌을 때 0이 되는 모든 벡터들의 집합이다.

$\mathcal{N}(A) = \{x\in \mathbb{R}^n : Ax = 0\}$

• 중요한 성질
  - n차원 내 임의의 한 점 $w$는 $u\in \mathcal{R}(A^T)$와 $v \in \mathcal{N}(A)$의 합으로 표현 가능하다.
  $\{w : w = u + v, u\in \mathcal{R}(A^T), v \in \mathcal{N}(A)\} = \mathbb{R}^n ~\mathrm{and}~ \mathcal{R}(A^T) \cap \mathcal{N}(A) = \{0\}$

$\mathcal{R}(A^T)$(n차원)와 $\mathcal{N}(A)$(n차원)를 직교여공간(orthogonal complements)라고 부르고 $\mathcal{R}(A^T) = \mathcal{N}(A)^\perp$라고 표시한다.

투영 (projection)

$\mathcal{R}(A)$위로 벡터 $y\in \mathbb{R}^m$의 투영(projection)은

$\mathrm{Proj}(y;A) = \mathop{\mathrm{argmin}}_{v\in \mathcal{R}(A)} \| v - y \|_2 = A(A^TA)^{-1}A^Ty$

• $U^TU = I$인 정방행렬 $U$는 $UU^T = I$임을 보이기
  - $U$의 치역은 전체공간($\mathcal{R}(A) = \mathbb{R}^n$)이므로 임의의 $y$에 대해 $\mathrm{Proj}(y;U) = y$이어야 한다.
  - 모든 $y$에 대해 $U(U^TU)^{-1}Uy = y$이어야 하므로 $U(U^TU)^{-1}U^T= I$이다.
  - 따라서 $UU^T = I$이다.

행렬식 (Determinant)

정방행렬 $A\in \mathbb{R}^{n\times n}$의 행렬식(determinant) $|A|$ (또는 $\det A$)는 다음과 같이 계산할 수 있다.

$|A| = A_{1,1}\times|A^{(1,1)}| - A_{1,2}\times|A^{(1,2)}| + A_{1,3}\times|A^{(1,3)}| - A_{1,4}\times|A^{(1,4)}| + \cdots ± A_{1,n}\times|A^{(1,n)}|$

where $A^{(i,j)}$ is the matrix $A$ without row $i$ and column $j$.

• 3 x 3 행렬의 행렬식 계산
  $A = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 0 \end{bmatrix}$

$|A| = 1 \times \left | \begin{bmatrix} 5 & 6 \\ 8 & 0 \end{bmatrix} \right | - 2 \times \left | \begin{bmatrix} 4 & 6 \\ 7 & 0 \end{bmatrix} \right | + 3 \times \left | \begin{bmatrix} 4 & 5 \\ 7 & 8 \end{bmatrix} \right |$

• numpy.linalg 모듈의 det 함수를 사용하여 행렬식을 구할 수 있다.

행렬식의 성질들

• $|I|=1$
• $A$의 하나의 행에 $t\in \mathbb{R}$를 곱하면 행렬식은 $t|A|$
  $\left|~\begin{bmatrix} \rule[.5ex]{1.7ex}{0.5pt} & ta_1^T & \rule[.5ex]{1.7ex}{0.5pt}\\ \rule[.5ex]{1.7ex}{0.5pt} & a_2^T & \rule[.5ex]{1.7ex}{0.5pt}\\ & \vdots &\\ \rule[.5ex]{1.7ex}{0.5pt} & a_n^T & \rule[.5ex]{1.7ex}{0.5pt} \end{bmatrix}~\right| = t|A|$
• $A$의 두 행들을 교환하면 행렬식은 $-|A|$
  $\left|~\begin{bmatrix} \rule[.5ex]{1.7ex}{0.5pt} & a_2^T & \rule[.5ex]{1.7ex}{0.5pt}\\ \rule[.5ex]{1.7ex}{0.5pt} & a_1^T & \rule[.5ex]{1.7ex}{0.5pt}\\ & \vdots &\\ \rule[.5ex]{1.7ex}{0.5pt} & a_n^T & \rule[.5ex]{1.7ex}{0.5pt} \end{bmatrix}~\right| = -|A|$
• For $A\in \mathbb{R}^{n\times n}$, $|A| = |A^T|$.
• For $A, B\in \mathbb{R}^{n\times n}$, $|AB| = |A| |B|$.
• For $A\in \mathbb{R}^{n\times n}$, $|A|=0$, if and only if A is singular (non-invertible).
  $A$가 singular이면 행들이 linearly dependent할 것인데, 이 경우 $S$의 형태는 부피가 0인 납작한 판의 형태가 될 것이다.
• For $A\in \mathbb{R}^{n\times n}$ and $A$ non-singular, $|A^{-1}| = 1/|A|$.

이차형식 (Quadratic Forms)

정방행렬 $A\in \mathbb{R}^{n\times n}$와 벡터 $x\in \mathbb{R}^n$가 주어졌을 때, scalar값 $x^TAx$를 이차형식(quadratic form)이라고 부른다.

$x^TAx = \sum_{i=1}^n x_i(Ax)_i = \sum_{i=1}^n x_i \left(\sum_{j=1}^n A_{ij}x_j\right) = \sum_{i=1}^n\sum_{j=1}^n A_{ij}x_ix_j$

$x^TAx$이 scalar값이므로 다음이 성립함을 알 수 있다.

$x^TAx = (x^TAx)^T = x^TA^Tx = x^T\left(\frac{1}{2}A + \frac{1}{2}A^T\right)x$

따라서 이차형식에 나타나는 행렬을 대칭행렬로 가정하는 경우가 많다.

• 음/양의 준/정부호
  - 대칭행렬 $A\in \mathbb{S}^n$이 0이 아닌 모든 벡터 $x\in \mathbb{R}^n$에 대해서 $x^TAx \gt 0$을 만족할 때, 양의 정부호(positive definite)라고 부르고 $A\succ 0$(또는 단순히 $A \gt 0$)로 표시한다. 모든 양의 정부호 행렬들의 집합을 $\mathbb{S}_{++}^n$으로 표시한다.
  - 대칭행렬 $A\in \mathbb{S}^n$이 0이 아닌 모든 벡터 $x\in \mathbb{R}^n$에 대해서 $x^TAx \ge 0$을 만족할 때, 양의 준정부호(positive sesmi-definite)라고 부르고 $A\succeq 0$(또는 단순히 $A \ge 0$)로 표시한다. 모든 양의 준정부호 행렬들의 집합을 $\mathbb{S}_{+}^n$으로 표시한다.
  - 대칭행렬 $A\in \mathbb{S}^n$이 0이 아닌 모든 벡터 $x\in \mathbb{R}^n$에 대해서 $x^TAx \lt 0$을 만족할 때, 음의 정부호(negative definite)라고 부르고 $A\prec 0$(또는 단순히 $A \lt 0$)로 표시한다.
  - 대칭행렬 $A\in \mathbb{S}^n$이 0이 아닌 모든 벡터 $x\in \mathbb{R}^n$에 대해서 $x^TAx \leq 0$을 만족할 때, 음의 준정부호(negative sesmi-definite)라고 부르고 $A\preceq 0$(또는 단순히 $A \leq 0$)로 표시한다.
  - 대칭행렬 $A\in \mathbb{S}^n$가 양의 준정부호 또는 음의 준정부호도 아닌 경우, 부정부호(indefinite)라고 부른다. 이것은 $x_1^TAx_1 > 0, x_2^TAx_2 < 0$을 만족하는 $x_1, x_2\in \mathbb{R}^n$이 존재한다는 것을 의미한다.
  -Positive definite 그리고 negative definite 행렬은 full rank이며 따라서 invertible이다.
  

Gram Matrix

임의의 행렬 $A\in \mathbb{R}^{m\times n}$이 주어졌을 때 행렬 $G = A^TA$를 Gram matrix라고 부르고 항상 positive semi-definite이다.
만약 $m\ge n$이고 $A$가 full rank이면, $G$는 positive definite이다.

고유값 (Eigenvalues), 고유벡터 (Eigenvectors)

정방행렬 $A\in \mathbb{R}^{n\times n}$이 주어졌을 때,
$Ax = \lambda x, x\neq 0$을 만족하는 $\lambda \in \mathbb{C}$를 $A$의 고유값(eigenvalue) 그리고 $x\in \mathbb{C}^n$을 연관된 고유벡터(eigenvector)라고 부른다.

• numpy.linalg 모듈의 eig 함수를 사용하여 고유값과 고유벡터를 구할 수 있다.

A = np. array([[1, 2, 3],
       		   [4, 5, 6],
               [7, 8, 0]])
               
eigenvalues, eigenvectors = LA.eig(A)
eigenvalues, eigenvectors
## output
# (array([12.12289378, -0.38838384, -5.73450994]),
# array([[-0.29982463, -0.74706733, -0.27625411],
#        [-0.70747178,  0.65820192, -0.38842554],
#        [-0.63999131, -0.09306254,  0.87909571]]))

• 고유값, 고유벡터의 성질들
  - $\mathrm{tr}A = \sum_{i=1}^n \lambda_i$
  - $|A| = \prod_{i=1}^n \lambda_i$
  - $\mathrm{rank}(A)$는 0이 아닌 $A$의 고유값의 개수와 같다.
  - $A$가 non-singular일 때, $1/\lambda_i$는 $A^{-1}$의 고유값이다(고유벡터 $x_i$와 연관된). 즉, $A^{-1}x_i = (1/\lambda_i)x_i$이다.
  - 대각행렬 $D = \mathrm{diag}(d_1,\ldots,d_n)$의 고유값들은 $d_1,\ldots,d_n$이다.

• 고유값, 고유벡터와 대칭행렬
  대칭행렬 $A\in \mathbb{S}^n$가 가지는 놀라운 성질들
  - $A$의 모든 고유값들은 실수값(real)이다.
  - $A$의 고유벡터들은 orthonomal(orthogonal, normalized)이다.
  

---

4. 행렬미분 (Matrix Calculus)

The Gradient

행렬 $A\in \mathbb{R}^{m\times n}$를 입력으로 받아서 실수값을 돌려주는 함수 $f : \mathbb{R}^{m\times n} \to \mathbb{R}$이 있다고 하자. $f$의 gradient는 다음과 같이 정의된다.

특별히 $A$가 벡터 $x\in \mathbb{R}^n$인 경우는,

• $x, b\in \mathbb{R}^n$, $A\in \mathbb{S}^n$(대칭행렬)일 때 다음이 성립한다. 꼭 기억하자!
  - $\nabla_x b^Tx = b$
  - $\nabla_x x^TAx = 2Ax$
  - $\nabla_x^2 x^TAx = 2A$
  - $\nabla_A \log |A| = A^{-1}$ ($A\in\mathbb{S}_{++}^n$인 경우)

최소제곱법 (Least Squares)

행렬 $A\in \mathbb{R}^{m\times n}$($A$는 full rank로 가정)와 벡터 $b\in \mathbb{R}^n$가 주어졌고 $b\notin \mathcal{R}(A)$인 경우, $Ax = b$를 만족하는 벡터 $x\in \mathbb{R}^n$을 찾을 수 없다.
대신 $Ax$가 $b$와 최대한 가까워지는 $x$, 즉
$\| Ax - b\|_2^2$을 최소화시키는 $x$를 찾는 문제를 고려할 수 있다.

고유값과 최적화문제 (Eigenvalues as Optimization)

다음 형태의 최적화문제를 행렬미분을 사용해 풀면 고유값이 최적해가 되는 것을 보일 수 있다.

$\max_{x\in \mathbb{R}^n} x^TAx \mathrm{~~~~subject~to~} \|x\|_2^2=1$

---

5. Autoencoder와 Principal Components Analysis (PCA)

• Autoencoder
  고차원의 입력데이터를 저차원으로 축소하는 역할로, PCA를 가장 간단한 형태의 autoencoder로 생각할 수 있다.
  

$m$개의 점들 $\{x_1,\ldots,x_m\}$, $x_i\in \mathbb{R}^n$이 주어졌다고 하자. 각각의 점들을 $l$차원의 공간으로 투영시키는 함수 $f(x) = c\in \mathbb{R}^l$와 이것을 다시 $n$차원의 공간으로 회복하는 함수 $g(c)$를 생각해보자. $f$를 인코딩 함수, $g$를 디코딩 함수라고 부르며

$x \approx g(f(x))$
가 되기를 원한다.

• 디코딩 함수
  함수 $g$는 간단한 선형함수로 정의하기로 한다.
  $g(c) = Dc, ~~D\in \mathbb{R}^{n\times l}$
  여기서 $D$는 열들이 정규화되어 있고 서로 직교하는 경우로 한정한다.

• 인코딩 함수
  디코딩 함수가 위와 같이 주어졌을 때, 어떤 함수가 최적의 인코딩 함수일까?
  $f(x)^* = \mathop{\mathrm{argmin}}_{f(x)} \int \| x - g(f(x))\|_2^2 dx$
  

방정식 $\nabla_f \| x - g(f(x))\|_2^2 = 0$을 $f$에 관해 풀면 된다.
$f(x)=c$로 두고 풀면 식 $\nabla_c (x^Tx - 2x^TDc + c^Tc) = 0$를 얻을 수 있고 따라서 최적의 인코더 함수는 $f(x) = D^Tx$

• 최적의 D 찾기
  입력값 $x$와 출력값 $g(f(x))$ 사이의 거리가 최소화되는 $D$를 찾는다.
  에러행렬 $E$를 $E = X - R$, 즉 입력행렬과 출력행렬의 차로 정의하자.
  $X = \begin{bmatrix} \rule[.5ex]{1.7ex}{0.5pt} & x_1^T & \rule[.5ex]{1.7ex}{0.5pt}\\ & \vdots &\\ \rule[.5ex]{1.7ex}{0.5pt} & x_m^T & \rule[.5ex]{1.7ex}{0.5pt} \end{bmatrix},~~ R = \begin{bmatrix} \rule[.5ex]{1.7ex}{0.5pt} & g(f(x_1))^T & \rule[.5ex]{1.7ex}{0.5pt}\\ & \vdots &\\ \rule[.5ex]{1.7ex}{0.5pt} & g(f(x_m))^T & \rule[.5ex]{1.7ex}{0.5pt} \end{bmatrix}$
  우리가 찾는 최적의 $D$는 다음과 같다.
  $D^* = \mathop{\mathrm{argmin}}_{D} \|E\|_F^2~~~\mathrm{subject~to~} D^TD=I_l$
  $R$을 다시 정리하고 식을 풀어보자.
  
  $d_i^Td_i = 1$이므로 벡터들 $d_1,\ldots,d_l$이 $X^TX$의 가장 큰 $l$개의 고유값에 해당하는 고유벡터들일 때 $\sum_{i=1}^l d_i^TX^TXd_i$이 최대화된다.