low rank approximation 개요 간단하게

1. terminology

 

kernel, filter, matrix, tensor 전부 비슷하면서 약간 달라?

 

kernel을 channel로 쌓으면 filter라고 부른다는데 딱히 찾아봐도 뭐가 없네

 

matrix가 2차원으로 원소를 모아놓은거면 tensor는 3차원 이상으로 원소를 모아놓은거

 

decomposition과 factorization은 사실상 동일해서 혼용해서 사용

 

그래서 tensor decomposition을 tensor factorization이라고 부르기도함

 

low rank approximation은 decomposition들을 전부 통틀어서 이르는 느낌이랄까

 

decomposition과 factorization 비슷한 용어들

 

 

convolution layer를 decomposition하는 경우 convolution filter를 decomposition하는거라 filter decomposition이라고 부름

 

데이터를 모델링할 때는 각 차원의 축이 의미를 가지도록 모델링하는 경우가 많음

 

2차원으로 모델링한 데이터를 decomposition할 때 matrix factorization이라고 부름

 

예를 들어 text는 x축을 속해있는 document, y축을 term이라고 모델링할 수 있고

 

medical record는 x축을 환자이름, y축을 진단받은 약이라고 모델링할 수 있어서

 

이런 데이터를 decomposition한다는 것은 matrix decomposition한다는 것

 

3차원 이상으로 더 높은 차원으로 표현된 데이터를 decomposition하는 것은 tensor factorization이라고 부름

 

예를 들어 text를 2차원에서는 document, term으로 모델링했지만 3차원으로 author , term, 출판된 time으로 모델링할 수도 있음

 

이렇게 표현된 3차원의 text를 decomposition하면 tensor decomposition한다고 부름

 

filter decomposition, matrix decomposition, tensor decomposition의 명확한 정의

 

 

2. low rank matrix approximation motivation

 

low rank matrix approximation은 대규모의 machine learning 문제를 풀 때 쓰는 kernel method를 위한 essential tool이다.

 

kernel method란 data point를 고차원의 feature space로 projection하는 방법이다

 

예를 들어 support vector machine, gaussian process

 

kernel method에서 데이터는 kernel matrix로 표현된다. (예를 들면 gram matrix)

 

많은 머신러닝 알고리즘이 kernel matrix를 이용해서 문제를 해결한다

 

그러나 많은 경우 kernel method는 kernel matrix와 관련된 계산 비용이 매우 크다는 것이 문제다

 

계산 비용은 2차원의 경우는 matrix연산이므로 최소한 training 데이터 수의 제곱 $O(N^{2})$

 

그러나 대부분의 kernel method가 역행렬을 계산하거나 eigenvalue decomposition을 계산해야해서

 

train데이터 수의 세제곱 $O(N^{3})$이 기본이고 그 이상의 고차원인경우 상상할 수 없을 정도로 커짐

 

그래서 large training set은 모델 성능에 좋겠지만 저장비용부터 계산비용까지 어마어마하다

 

cholesky decomposition같은 low rank decomposition이 이러한 계산비용을 줄임에도 불구하고

 

여전히 그들은 kernel matrix를 계산하기위한 계산비용이 필요하다

 

이런 문제를 해결하기 위한 하나의 접근법이 바로 low rank approximation이다.