Implicit Regularization in Tensor Factorization

읽으면서 쓰는 글. 중간에 드랍할 수 있음.

이해한 바를 토대로 작성했으며 직역/뇌내 해석이다.

 

최근 arxiv sanity에 top recent라서 가져왔다. 이름부터 심상치 않은 개념을 담고 있을 것 같은 느낌이 드는 논문이다.

arxiv.org/pdf/2102.09972.pdf          

신기하게도 코드까지 있다. github.com/noamrazin/imp_reg_in_tf

 

 

우선 이 논문은 implicit regularization(-> generalization)에 대한 논문이다.

 

참고로 아래부터 계속 언급할 텐서는 Domain X를 의미한다.

tensor factorization이라는 방법을 사용하는 것 같은데, 어떻게 텐서를 분해하겠다는건지 아직은 모르겠으나, 어떤 텐서가 담고 있는 정보의 내재적인 요소 때문에 generalization과 연관지을 수 있는 부분이 분명히 존재할 것이라는 개념 하에서 출발한다. 어떤 방법으로든 tensor의 complexity를 측정할 수 있다면, 같은 모델과 같은 regularizer, optimizer를 사용한다고 해도 generalization이 잘 되는 데이터와 안 되는 데이터를 구분할 수 있을 것이다.

 

Implicit regularization이라는 단어는 전에 rethinking generalization 논문에서 봤는데 사실 잘 기억이 안난다.

 

 

---

Abstract.

"generalization이 잘 되는 데이터는 분명 존재한다."

그런데 어떤 데이터가 잘 generalization이 되는지를 수식화, 정량화 하는 방법에 대해서는 많은 사람들이 원하지만 아직 연구가 부족하다.

이에 따라 이 논문에서는 tensor factorization을 통해 implicit regularization을 분석하는데, 이게 어떤 non-linear neural network와 동치이다. 그러면 어떻게 하느냐.

 

gradient decent 과정이 어떻게 tensor들을 분해하는지를 특징지었다. 그리고 low tensor rank로 가는데에 어떤 bias가 있는지에 대해서 실험적인 증거를 통해 설명한다.

(원문) "We characterize the dynamics that gradient descent induces on the factorization, and establish a bias towards low tensor rank, in compliance with empirical evidence."

 

그리고 non linear neural network의 implicit regularization을 포착하는 tensor rank에서 영감을 받아, 이 논문에서는 이를 complexity에 대한 measure로써 보려고 한다. 실제로 실험한 것에 따르면, standard dataset에 모델이 fitting할때는 굉장히 tensor rank(=complexity)가 낮음을 확인했다고 한다. 따라서, tensor rank가 어쩌면 neural network의 implicit regularization을 설명해줌과 동시에 real world data에 대한 특성을 generalization 관점에서 설명해볼 수 있지 않을까 한다.

 

 

Introduction.

우리는 딥 뉴럴 네트워크를 사용하는데 이 모델의 learnable parameter가 training data보다 많은 경우에서, 심지어 explicit regularization이 없는 경우에서도 learnable parameter가 많다는 것은 굉장히 묘...한 일이다.

 

그래서 대부분 이 generalization의 이유를 implicit regularization 때문이라고 한다. Predictor가 low complexity를 가지는 쪽으로 학습이 되는 것. 예를 들면 natural scene data의 경우 generalization이 잘 되지만, random data같은 경우에는 그렇지 않은데, 이 이유로 전자의 경우에는 Predictor의 complexity가 낮기 때문이라는 것이다.

그런데 이 predictor에 대한 formalizing이 굉장히 어려운데, 이유는 Predictor의 complexity에 대한 정의가 아직 부족하기 때문이다.

그래서 아직까지의 분석은 거의 간단한 셋팅에서 이루어지는데, complexity에 대한 개념이 명백한 것들이 해당된다. 예를 들면 matrix completion처럼. 물론 실제로는 matrix보다 훨씬 고차원의 tensor가 practical한 셋팅일 것이다.

 

이 논문에서는 Tensor Factorization을 통해 complexity를 분석했으며, tensor rank가 complexity를 나타낼 수 있으며 더 나아가 implicit regularization을 시사하고 있다. 대체 tensor factorization이 뭘까?

이를 알기 위해서는 먼저 matrix completion이 무엇인지 알아야하며, 이에 대한 해법 중 하나인 matrix factorization은 무엇이고, 이를 tensor로 확장한 tensor completion/factorization이 무엇인지에 대해 알아가며 사고를 확장해야할 것이다. 바로 아래에 이어서 이에 대한 설명을 간략하게 적어보았다.

 

Matrix Completion이 무엇인가?
"Unknown matrix가 있는데, 여기서 랜덤하게 subset을 뽑는다. 그리고 우리는 이 unseen entries가 무엇인지 맞추는 것이다. 이런 관점에서 본다면 seen entries가 training dataset에 해당되는 것이다."

이 논문 설명만 보면 이해가 어려울 것 같아 다른 자료를 참고하고 있다. sanghyukchun.github.io/73/     여기에 잘 설명 되어있다.
대략 요약하면 다음과 같다.

넷플릭스를 떠올려보자. 우리는 특정 유저가 특정 영화를 얼마나 좋아할지에 대한 score값(Y label)을 알고싶다.
유저들은 영화에 평점을 매겼기 때문에 어느정도의 정보를 모을 수 있으며, 이를 유저*영화 사이즈의 행렬로 나타낼 수 있다.
하지만 모든 유저가 모든 영화를 본건 아니기 때문에 중간에 뚫려있는 칸이 있을 것이다. 나머지 빈칸을 맞추는 문제이다.
GT Matrix가 존재한다면, 우리는 빈칸이 있는 Matrix를 채워 최대한 GT를 맞추고 싶을 것이다.
어쨌거나 저 matrix를 구할거고, 이 X->Y로 가는 함수를 논문에서 predictor라고 부르고 있다. 연산의 complexity는 matrix의 rank에 해당할 것이다.

실제로 푸는 방법은 여러가지가 있을 것인데, matrix factorization의 성능이 좋아서인지 많이 사용하는 것으로 보인다.

Matrix Factorization이 무엇인가?
위의 GT matrix는 원래는 엄청 큰 M*N matrix일 것이다. 그런데 이걸 더 낮은 dimension K를 사용하면?
R = M*N matrix
P = M*K matrix
Q = N*K matrix
이렇게 R = P(Q)T로 나타낼 수 있다.
이를 의미적으로 설명한다면, 유저와 그 유저들이 매긴 각 영화에 대한 커다란 raw data R 대신에 유저의 흥미 정도라든가 영화의 특성 등의 정보를 나타내는 latent variable P, Q로 대신 표현하겠다는 것이다.

그러면 최대한 저차원의 variable들로 나타낼 수 있을거고, 이걸로 R을 구한다. 물론 latent variable들이 의미를 잘 담기 위해서는 optimize 해야할 것이다. 두가지 방법이 있다고 저 글에서 설명하고 있다.

첫번째로, convex relaxation. R-R^hat = 0을 푼다.
둘째로, non-convex problem을 바로 푸는 법.
나는 후자가 더 익숙해보이는데, ||R-P*Q||_2를 loss로 설정해서 minimize 하면 되는거 아냐?
어쨌거나 이런 방법으로 matrix factorization을 구할 수 있다는 것이다.



이 논문에서도 Introduction에서 언급하길 (다른 17, 19년도 연구 인용), 그 matrix factorization을 간단한 linear neural network로 만들 수 있고 gradient descent로 학습하며 initial parameter는 거의 0에 가깝도록 하여 lr을 매우 낮춰 천천히 학습하게했다고 한다.
게다가 실험적으로 밝혀진 바로는 이러한 matrix factorization을 통해서 implicit하게 comlexity가 minimize될 수 있다고 말한다.


Tensor로의 확장?
이렇듯 matrix factorization에서 implicit regularization에 대해 분석하는 것이 최근 활발하게 연구되고 있다고 한다.
하지만 문제점은 practical하지 않다는 점. latent variable을 만들어주는(=matrix factorization) 모델이 그냥 linear인데다가, 2d matrix형태의 데이터이기 때문이다.

따라서 NIPS 2020년도 논문 "Implicit regularization in deep learning may not be explainable by norms."에서는 N차원의 tensor completion 문제를 푸는 것으로 정의하고, tensor factorization을 (위의 matrix factorization처럼) gradient descent로 학습했다고 한다.
유사하게 다른 연구에서도 어느정도의 non-linearity를 가지는 모델을 사용해서 위와 같은 것을 했다고 한다.

 

그러면 이 논문의 contribution은 무엇인가.

tensor factorization의 implicit regularization에 대하여 더 이론적인 분석을 제공한다.

 

이 논문에서 주장하는 바는 tensor rank가 (non linear neural network의) implicit regularization의 정도를 나타낼 수도 있다는 것이다.

이를 MNIST, Fashion-MNIST에서 실험한 결과를 제시하고 있다.

이 데이터셋들이 정말 tensor rank가 낮게 나왔는데, random data (무작위로 0,1을 채워넣음)에 대해서는 rank가 높게 나왔다는 것이다.

 

 

 

Tensor Factorization.

아래 그림을 먼저 보자. discrete variables 3개(A, B, C)를 가지는 data (tensor)에 대한 prediction task이다.

각 변수는 5개의 값 중 하나를 가질 수 있다. 그러면 총 125개의 경우의 수가 나올거고, 이에 대한 tensor는 5*5*5 3차원 큐브형태로 있을 것이다.

 

그러면 이 데이터셋 내에서 모든 데이터는 저 5*5*5 space에 하나의 점으로 맵핑된다. 그리고 각각이 label을 가지고 있을 것이다. 우리는 여기서 데이터셋으로 가지고있지 않은 점에 대해서도 레이블을 잘 맞추는 것이 Prediction task인 것이며, 이런 unseen data에 대해서도 잘 해결한다는 것이 바로 'generalization이 잘된다' 라고 말할 수 있는 것이다.

 

 

notation은 논문을 보도록 하자.

어쨌거나 이 문제를 R-component tensor factorization으로 풀것인데, 이 말은 즉 R개의 component를 곱하면 최종적인 tensor가 나온다는 것이다.

그러면 우리는 원래 텐서 W를 복원하기 위한 컴포넌트 R의 개수가 최대한 적었으면 좋겠다는 것이다. 이 component R 최소 개수를 W의 'tensor rank'라고 지칭하는 것이다.

이말대로라면 앞에서의 똑같은 5*5*5라고 해도 데이터가 추론하기에 좋다면 적은 컴포넌트를 필요로 할것이며, 이것이 low rank로 나타나고, 결과적으로 generalization이 잘 되는 것이다.

 

논문에서 말하길, 여기서 직접적으로 R값을 제한하는 식으로 tensor factorization output의 rank를 제한할 수 있다고 한다. 하지만, 우리의 목적은 gradient descent를 통해서 추론된 implicit regularization를 보는 것이다. 위 수식 (2)의 objective function을 통해 수식 (3)의 형태처럼 추론될 것이기 때문에, 명시적인 constraints를 주지 않으면서 R을 임의의 큰 값을 사용해서 본다고 한다.

(뭐 0이 많다든가 entropy가 엄청 낮은 component가 많이 나온다거나 그러면 low rank라고 볼수 있는 그런건가? 일단 다음으로.)

 

gradient.

 

2.1 Interpretation as Neural Network

뭔가 멋진 얘기들을 본 것 같은데 이걸 NN으로 어떻게 하는가.

일단 tensor completion은 prediction problem으로 볼 수 있다. 아까 말한 그 unknown tensor W*가 있다고 가정했을 때, input에 대해서 빈칸 부분도 잘 맞추는 것이 곧 generalization이 잘 됨을 의미하니까.

 

training set의 경우 W*의 칸이 채워진 관측 데이터일 것이고, unseen data에 대한 에러는 test error일 것이다.

 

 

(예시) Input: 100*100 binary image, Output: Continuous label

10000 tensor completion problem이고, dimension=2가 된다.

이에 대해 continuous label을 matrix가 가지고 있는 그런 형태.

 

하지만 observation은 uniformly 분포되어있지 않을 가능성이 있다. 따라서 matrix completion 문제를 정의하면서 reconstruction error를 측정할때도 균일하게 측정되진 않을 것이다.

 

 

어쨌거나 위에서 정의한 수식대로라면, tensor factorization는 'a two layer neural network with multiplicative non-linearity'로 볼 수 있다고 한다.

input으로 tensor의 location이 주어지면 (이미지라는 것도 수많은 조합 중 하나인 것. 이전 이미지 참고) output은 원래 그 위치에 있어야할 값을 맞추는 것이다. 핵심은 그러면 tensor factorization이라는게 일반 딥러닝처럼 좀 더 practical해지려면 no linearity도 커버할 수 있어야한다는 것.

 

아직까진 그냥 conv, pooling 연산처럼 곱셈하는 게 왜 w의 factorization 수식과 동치인지는 모르겠다.

어쨌거나 그렇다면 저걸 풀면 되는거고, dynamical characterization 파트를 보면 dynamic characterization을 각각의 tensor factorization의 component의 Norm으로써 정의한다는 것을 알 수 있다.

읽진 않았는데 대충 보면 low rank results를 향한 bias가 있다고 한다.

 

 

 

음 논문 보면 뭔소린줄은 대략 알겠는데 저 많은 증명을 설명할 자신이 없어서 드랍.....

 

 

---

위에 읽기 귀찮아서 다시 정리. 대략 설명할때 이 순서로 얘기해야겠다.

 

 

1. Tensor Completion의 이해

처음부터 얘기하면 이해하기 어려울 것 같아서, matrix completion 문제를 언급한 후에 tensor completion/factorization 논문 수식들을 설명해야겠다.

 

2. Neural Network로의 해석

텐서를 채우는데 이걸 factorization했다는것까진 알겠는데, 이게 그래서 우리가 어떻게 써먹냐.

neural network로 볼 수 있기 때문이다. Figure 2를 띄우고 설명해야겠다. 식을 보면 W_e를 factorization했던 그 식과 우리가 아는 conv-pooling이 동치라는 것을 알 수 있다.

 

왜 동치인가? (사실 이거 몰라도 논문 읽는데 상관 없을 것 같은데, 궁금해서 찾아봤다.)

 

우리가 일반적으로 알고있는 tensor multiplication이 Kronecker product이라는 것부터 설명해야한다. 아마 그림이나 식만 봐도 바로 다들 이해할 것 같다. 이게 사실 (흔히 알고있는 vector에서의) outer product의 generalization된 형태이다. 행렬 버전.

 

참고자료

• en.wikipedia.org/wiki/Kronecker_product 여기 식을 보면 아마 딥러닝 하는 사람이라면 바로 알거다.
• en.wikipedia.org/wiki/Outer_product outer product. 이걸 보면 새삼 왜 inner product / outer product이라 이름을 지었는지 알 수 있다.
• arxiv.org/pdf/1905.01289v1.pdf convolution is outer product

 

응? 그 고등학교땐지 중학교땐지 배운 AB sin theta인지 뭔지 그 outer product? 맞다.

Kronecker product이 우리가 잘 아는 딥러닝의 행렬연산임은 눈으로 확인 했는데, 예전에 벡터가지고 했던 그거라는게 잘 이해가 안되어서 이것도 한번 찾아봤다.

 

학교에서 배운 것으로는 a=(a1 a2 a3) b=(b1 b2 b3)의 외적은,

|  i    j   k  |

|a1  a2 a3 |

|b1 b2 b3 |

이걸 가지고 계산했던걸 기억할거다. 그 행렬의 determinant 구할 때 처럼!

아마 선형대수학을 기억하면 이해가 더 쉬울 것이다. 행렬을 곱하는 것은 어떤 선형변환을 하는 것과 같은데, 3차원이라면 eigen vector가 3개 있을거다. (3*3으로 쓰긴 하지만 결국 eigen vector의 linear combination으로 다른 eigen vector를 나타낼 수 있는 경우는 머릿속에서 제외하도록 하자) 아무튼 쉽게 생각해서 2차원이라고 하면, determinant(행렬식)는 주어진 변환행렬의 eigen vector 둘이 이루고 있는 평행사변형의 넓이이다. 그게 벡터 외적이지 뭐야.

 

참고자료들

angeloyeo.github.io/2019/08/06/determinant.html determinant에 대하여 (2*2)

 

아무튼 조금만 계산 해보면 우리가 원래 알던 외적이 저 Kronecker product이며 어떻게 확장된건지 감각적으로 알 수 있다.

 

 

3. 그래서 어떻게 Data의 generalization capability를 정량화하나?

아까 rank로 표현한다 뭐다 했는데 원래 아는 rank는 정수값이니까 논문에 나온 0.XX값은 전혀 아니고.

저 최소한의 R을 쓴다는게 그러면 convolution 파라미터가 0에 가까운 게 많으면 된다는건가? 값을 일단 크게 고정해놓고 gradient descent를 통해서 implicit regularization이 어떻게 되는지 분석을 하기 위함이었으니까.

 

일단 Fig2를 보면 R은 width, factorization의 각 컴포넌트인 w들은 conv의 learnable parameter임을 알 수 있다.

 

 

Dynamical Characterization.