[LG Aimers] 2. Mathematics for ML

해당 게시글은 LG Aimers Phase1의 수업 내용을 정리한 글로, 모든 내용의 출처는 https://www.lgaimers.ai/ 입니다.

1. Matrix Decomposition

   • determinant
     • 역행렬의 존재 여부를 구하기 위해 determinant 개념을 정의
     • Laplace Expansion : 33 행렬의 determinant는 22행렬의 determinant의 recursive한 formular로 정의됨을 발견
     • determinant는 행렬곱에 대한 분리 가능 : det(AB) = det(A)det(B)
       • cf) trace는 행렬합에 대한 분리 가능
   • Eigenvalue
     • Ax = $\lambda$x (A는 square matrix)
       • det(A-$\lambda$I) = 0
     • Eigenvalues are NOT unique
       • = Eigenvetors are NOT unique
     • det(A) = eigenvalue들의 곱
     • trace(A) = eigenvalue들의 합
   • Cholesky Decomposition
     • $A = LL^{\top}$
       • A가 symmetric, positive definite이면 L은 lower-triangular matrix with positive diagonals
       • $det(A)=det(L)det(L^{\top})=det(L)^2$
         • 이때 L이 triangular matrix이므로 det(L) = eigenvalue들의 곱
       • determinant 계산이 매우 쉬워짐
   • Eigenvalue Decomposition (대칭행렬에만 적용가능)
     • $A=PDP^{-1}$
       • $A$는 항상 대칭행렬, $D$는 대각행렬
     • Diagonal matrix
       • det(D) = d1d2…*dn
       • determinant, 역행렬, n제곱 구하기 매우 쉬움 → 일반 행렬을 대각행렬로 분해하고자 하는 시도 다양 → 그 중 하나가 eigendecomposition
         
       • $D = P^{-1}AP$ → $D^2=P^{-1}APP^{-1}AP = P^{-1}A^2P$
         • A가 diagonalizable하다면
       • $D=P^{-1}AP=P^{\top}AP$
         • A가 orthogonally diagonalizable하다면 = A가 symmetric하다면
     • A is orthogonally diagonalizable == A is symmetric
       • A가 대칭행렬일 경우 eigenvetor가 서로 직교(orthogonal)한다.
   • Singular Value Decomposition (일반적인 모든 행렬에 적용가능)
     • 대칭이지 않으며 정방행렬인 경우, 대칭이지 않으며 정방행렬도 아닌 경우
     • $A=U\sum V^{\top}$
       • $U,V$ 항상 orthogonal matrix
         • $UU^{\top}=I, VV^{\top}=I$
       • $\sum$ 항상 diagonal matrix
         • singular value라고 부름
     • $A^{\top}A$의 Eigenvalue Decomposition과 동치이다.
       • $A$가 symmetric하다면 EVD=SVD
     • 모든 경우에 존재하기 때문에 데이터 분석 시 매우 유용하게 사용됨

2. Convex Optimization

   • 모델의 좋은 파라미터 : 특정 optimization문제의 solution이 되는 경우가 많음
   • Unconstrained Optimization : Gradient Descent
     • Stochastic Gradient Descent
       • Batch gradient : 한 번 업데이트 시 모든 N개의 데이터 활용
       • Mini-Batch gradient : 한 번 업데이트 시 N개의 데이터 중 일부 K개의 subset을 골라 활용
       • Stochastic gradient : 한 번 업데이트 시 subset으로 구한 gradient의 기댓값이 original full batch gradient와 동일하도록 random하게 하나를 골라 활용
         • mini-batch, stochastic gradient는 full-batch gradient의 일종의 noisy approximation
         • data가 매우 많은 상황에서 유용하게 활용하여 업데이트 비용 절감 가능
     • Better Convergence
       • 학습률 조정 필요
       • Momentum
         • 이전에 업데이트한 방향을 고려하여 이번 업데이트 정도 결정
         • 수렴 속도가 빨라짐
   • Constrained Optimization
     • Lagrangian Fucntion
   • Convex sets, functions
     • convex optimization : minimize f(x)
       • f(x)가 convex function, x가 convex set이 될 때, convex oprimization이 됨
     • convex set
       • 어떤 set이 있을 때, 임의의 point 2개를 정하고 이를 연결하는 선분을 구했을 때 해당 선분이 항상 set 내부에 존재할 때 해당 set을 convex하다고 이야기 함
     • convex function (오목)
       • $f(\frac{x+y}{\theta}) \leq \frac{1}{\theta}f(x)+\frac{1}{\theta}f(y)$를 항상 만족하는 함수
         • cf) concave(볼록)함수는 $-f$가 convex할 경우 concave하다고 이야기함
         • 특정 함수가 convex하다는 이야기는 함수의 임의의 점에서 접선을 그렸을 때 해당 함수는 항상 그 접선보다 위에 위치한다는 이야기이다.
           • $f(y)-f(x) \geq \bigtriangledown f(x)^{\top}(y-x)$
         • $\bigtriangledown f(x)=0$이면, $f(y) \geq f(x)$이므로, x는 f함수의 global minimum이 된다.
           • gradient가 0이 되는 local minimum과 global minimum이 일치한다.
       • f가 두번 미분 가능하고 이에 해당하는 eigenvalue가 0보다 크다면 convex하다
     • 예시
       • log함수는 concave함수 == -log함수는 convex 함수
     • convex 함수의 선형 결합 및 이동 = convex
     • lagrange dual 함수도 convex함
   • Convex Optimization
     • stong duality : Dual Problem의 Optimum과 Primal Problem의 Optimum이 동치함
       • $x^* :$ Primal Optimum (f(x)에 대한 최적) / $\lambda^*, v^*:$ Dual Optimum (라그랑지 함수의 최적)
     • KKT Condition
       • Any optimization 문제에 있어 필요조건
       • Convex optimization 문제에 있어 필요충분조건

   → 추가적인 이해를 돕기 위한 링크 : https://velog.io/@wjleekr927/Strong-duality-and-KKT-conditions

3. PCA 주성분 분석

   • 왜 주성분분석을 해야하는가
     • High-dimensional data
       • dimension이 커질수록 분석, 시각화가 매우 어려움
       • 중요하지 않은 차원을 줄일 수 있음
     • Compact data representation
   • PCA 알고리즘 순서
     1. Centering
        • 각 dimension의 평균을 구해 평균으로 빼주기
     2. Standardization
        • 각 dimension의 분산을 구해 분산으로 나눠주기
     3. Eigenvalue/vector
        • 축소하여 만들고자 하는 dimension의 개수 M개의 data covariance matrix의 아이겐벡터, 밸류 구하기
     4. Projection
        • M개의 공간으로 데이터를 사영시킴
     5. undo Standardization, Centering
        • 정규화한 내용을 다시 비정규화하여 원래 위치, 범위로 옮겨주기
   • Data Covariance Matrix
     • $S= \frac{1}{N}XX^{\top}=\frac{1}{N}\sum x_nx_n^{\top}$ (N은 데이터 개수)
       • 항상 positive definite, eigenvalue와 eigenvector 존재, symmetric
   • PCA
     • $z_n=B^{\top}x_n \in \mathbb{R}^{M}, (x_n \in \mathbb{R}^D)$
       • $B \in \mathbb{R}^{D\times M}$ 이며 orthonomal
   • PCA 원리
     • dimensional reduction : 어떤 공간이 reduction하기 좋은 공간인가
     • Data를 가장 잘 나타내는 Subspace를 찾아서 사영시키는 것
       • 데이터 분산이 클 경우 보다 중요한 정보로 파악 (가지고 있는 정보가 많다고 판단)
       • 분산을 가장 크게 만드는 subspace는 data covariance vector의 largest eigenvalue를 갖는 eigenvetor가 된다.
         • 상위 M개의 eigenvector를 찾아서 projection 진행
   • 데이터의 개수보다 데이터의 차원이 높은 경우
     • 보다 효율적으로 PCA를 계산하는 trick이 존재함
       • 데이터 차원 D, 데이터 개수 N 일때 D > N이라고 가정하면
       • 원래는 $XX^{\top} \in \mathbb{R}^{D\times D}$의 eigenstuff를 구해야 함
       • 그러나$\frac{1}{N}X^{\top}X\in \mathbb{R}^{N\times N}$$X^{\top}X\in \mathbb{R}^{N\times N}$의 eigenstuff를 구해서 PCA를 할 수 있음