[40] 경량화(4) - 행렬 분해

1️⃣ Kernel

1) Linear transformation

Linear transformation은 변환 후에 덧셈과 scalar를 보존하는 변환입니다.

 

https://mathinsight.org/image/linear_transformation_2d_m1_m1_1_3

 

 

2) Kernel

Kernel은 알맹이, 핵심이란 의미입니다.

남기고 싶은 부분 또는 핵심을 저장할 때 사용합니다.

 

https://en.wikipedia.org/wiki/Kernel_(linear_algebra)

 

 

3) Kernel Method

Kernel Method는 Kernel 하고 약간 다릅니다.

 

예를 들어, 아래 그림에서 빨간 점과 초록 점을 classification하고 싶을 때 저차원 -> 고차원으로 보내면 확실히 구분되는 경우가 있습니다. 따라서 $< f(x), f(y) >$ 부분에서 $z_{x}$부분에 $x^{2}_{1} + x^{2}_{2}$, $z_{y}$부분에 $y^{2}_{1} + y^{2}_{2}$로 만들어서 사용하면 차원을 높여서 사용할 수 있습니다.

 

https://www.quora.com/What-are-kernels-in-machine-learning-and-SVM-and-why-do-we-need-them/answer/Lili-Jiang?srid=oOgT

 

하지만 고차원으로 보내게 되면 cost(계산량)가 비싸집니다. 100차원 x 100차원을 dot product 했을 때 어마어마한 cost가 발생하게 됩니다.

 

그렇기 때문에 차원을 높이는 $< f(x), f(y) >$ 방법보다 kernel인 $x \cdot y + ||x||^{2}||y||^{2}$을 사용합니다.

 

https://www.quora.com/What-are-kernels-in-machine-learning-and-SVM-and-why-do-we-need-them/answer/Lili-Jiang?srid=oOgT

 

이렇게 계산하면 차원이 늘어나기 전에 $x,y$를 계산하기 때문에 저 차원의 상태에서 계산을 해서 결과를 낼 수 있습니다.

 

 

 

 

2️⃣ Low-rank approximation in model compression

 

Kernel method처럼 딥러닝에서 Filter를 decompostion 하는 방법입니다.

Depth-wise Seperable Convolution을 사용하면 훨씬 연산량이 적게 결과를 도출할 수 있습니다.

 

다만, 여기서는 Kernel method와는 다르게 결과가 기존 값과 정확하게 같지 않고 approximation (근사)합니다.

 

 

https://www.edwith.org/bcaitech1

 

원래 Initial state와 Terminal state를 만들어내는 network을 계산할 때 cost가 커지는 문제점이 있기 때문에

⇒ 원래 계산과 근사하게

⇒ cost는 더 적게

만들기 위해 weight들을 저차원(Low-rank)로 분해(이때, essential하지 않은 것은 버리기도 함) 한 후, low rank의 tensor들로 조립을 해서 사용합니다.

 

 

 

 

 

3️⃣ Matrix decomposition

 

Matrix decomposition road-map은 다음과 같습니다.

 

[Kossaifi et al., IEEE 2020]

 

Matrix decomposition은 행렬을 특정한 구조를 가진 다른 행렬의 곱으로 나타내는 것을 의미합니다.

이때, 나눠진 행렬의 곱은 원본 행렬에 근사하게 됩니다.

 

https://en.wikipedia.org/wiki/Matrix_decomposition#Singular_value_decomposition

 

 

1) Singular Value Decomposition (SVD)

Singular Value Decomposition은 eigenvalue(고윳값)을 decomposition 할 때 행과 열 크기가 같은 정방행렬(m x m 행렬)만 가능했지만 행과 열 크기가 다른 직각행렬에서의 분해가 가능합니다.

 

방법은 U matrix (mxm 정방행렬)과 V matrix (nxn 정방 행렬)을 사용하며, 가운데를 대각 행렬로 만들어서 사용합니다. (여기서 *은 Transpose)

 

https://bkshin.tistory.com/entry/%EB%A8%B8%EC%8B%A0%EB%9F%AC%EB%8B%9D-20-%ED%8A%B9%EC%9D%B4%EA%B0%92-%EB%B6%84%ED%95%B4Singular-Value-Decomposition

 

2) Singular Value Decomposition ⇒ Principal Component Analysis

Singular Value Decomposition을 Principal Component Analysis로 변환하기 위해서는 가운데 있는 대각 행렬의 일부분을 제거해서 정방행렬로 만들어 사용합니다. 대각행렬을 제거하면서 $V^{T}$ matrix도 일부가 잘라나가게 됩니다.

 

 

https://towardsdatascience.com/singular-value-decomposition-and-its-applications-in-principal-component-analysis-5b7a5f08d0bd#:~:text=Singular%20Value%20Decomposition%20in%20PCA&text=The%20relationship%20between%20the%20Singular,order%20of%20the%20Singular%20Values.

 

 

 

4️⃣ Tensor decomposition

1) CP (Canonical Polyadic) decomposition

 

• SVD → CPD → Tucker D → Network decoupling
  
  
• CP decomposition은 SVD의 tensor 버전
  
  다만, tensor이기 때문에 eigen value에 대응할 수 있는 것이 $\lambda$입니다.
  
  따라서 I x J x K tensor를 Rank 1짜리 선형 합으로 나타낼 수 있습니다.

 

[Kolda et al., SIAM 2009]

 

 

• a x b x c의 rank 1 tensor를 구하는 방법은 Optimization (iterative search)을 통해 덜 principal한 component를 잘라내고 나서 원래 tensor에 근사합니다.

 

 

 

2) Network decoupling

Network decoupling은 regular convolution와 depth-wise separable convolution의 수학적 연관도가 있다고 분석했습니다.

 

즉, depth-wise separable convolution은 regular convolution의 principal components이다라고 말하고 있습니다.

depth-wise separable convolution 여러 개를 sum 해서 original convolution을 approximate 하는 것을 뜻합니다.

 

 

[Guo et al., arXiv 2018]

 

Theorem 1.을 보면 computational complexity를 올리지 않고 depth-wise separable convolution 여러 개를 sum으로 원래 network의 regular convolution을 approximate 할 수 있다는 것을 말합니다. ($k_{h}$와 $k_{w}$를 곱한 것 보다는 K가 작게)

 

[Guo et al., arXiv 2018]

 

따라서 Full rank를 쓰는 것이 아닌 partial rank를 사용해서 중요한 component들만 뽑아서 approximation을 할 수 있습니다. 여기서 top T개만 뽑아서 사용하기 때문에 W와 똑같다고 볼 수는 없고 W에 근사한다고 말할 수 있습니다. 

 

[Guo et al., arXiv 2018]