값싼 비용으로 최대 효율을 낼 수 있을까 - lottery ticket hypothesis

1. introduction

 

research의 트렌드를 바꿔버린 혁명적인 가설로 한번 제기된 이후 후속논문이 지금까지도 나오고 있음

 

첫 network인 A를 parameter initialization을 하고 적당히 training을 하여 91%의 정확도를 얻었다고 하자.

 

이후 training된 network를 pruning하여 B를 얻었다고 한다.

 

이 때 B의 현재 parameter에서 mask로 가려지지 않은 부분을 A의 첫 initialization된 parameter로 reset한 다음에

 

정확히 A와 동일한 training방법을 사용하여 reset한 B를 training하면 91%에 가까운 정확도를 얻을 수 있는 그런 network B가 존재할 수 있다는 뜻이다.

 

이런 network B를 lottery ticket이라고 부른다. 이것이 무슨 의미를 가지느냐?

 

애초에 더 복잡한 A를 training하는 것보다 간단한 B를 training한다면 pruning 비용을 절약할 수 있다는 것임.. 간단한 비용으로 동일한 성능을 얻을 수 있다는 의미

 

물론 그런 network를 어떻게 찾느냐가 문제

 

그리고 hypothesis임

 

증명은 못하겠지만 경험적으로 맞는것 같아서 제기해보는 것

 

lottery ticket 예를 들어 설명한 그림

 

 

2. formalization

 

2-1)

 

random하게 initialize된 dense neural network는 아마 어떠한 initialize된 subnetwork를 가질 것이다.

 

그런 subnetwork는 original network와 거의 동일한 iteration으로

 

이 subnetwork 혼자서 동일한 training했을 때 얻을 수 있는 accuracy가

 

original network를 training했을 때 accuracy와 동일하다.

 

 

2-2)

 

수학적으로 $f(x, \theta)$라는 dense neural network가 있고 intialize된 parameter $\theta_{0}$를 생각하자.

 

training set x를 이용하여 SGD로 optimization을 할 때 f는 minimum validation loss L, test accuracy a를 j iteration만에 가진다.

 

이제 0아니면 1을 원소로 가지는 mask 행렬 m을 생각하자.

 

$f(x,m\bullet\theta)$는 original network인  $f(x, \theta)$에서 적절한 방법으로 pruning 된 subnetwork이다.

 

이 subnetwork는 original network와 동일한 initialization parameter인 $\theta_{0}$로 initialization되어 $f(x,m\bullet\theta_{0})$부터 training을 시작함

 

마스크 m은 고정시키고 SGD로 optimization을 시키면 j ' iteration만에 validation loss L' 과 test accuracy a ' 을 가진다.

 

이 때 lottery ticket hypothesis는  $j' <= j$를 만족하고 $a' >= a$를 만족하며 $\left| m \right|_{0} \ll \left| \theta \right|$ (이거는 무슨 뜻인지는 알겠는데 수식적으로 뭐라 해석해야하는지 모르겠다...)인 마스크 m이 존재한다라고 예측한다.

 

무슨 말이냐면 training iteration을 덜 해도 original network보다 같거나 높은 accuracy를 가지는 parameter가 더 적은 subnetwork가 존재할 수 있다는 것임

 

처음 lottery ticket을 제안한 논문의 설명

 

 

근데 이제 어떻게 찾는지는 모르겠고 항상 존재하는지도 모르겠다는게 문제임

 

참고로 여기서 dense하다의 의미가 갑자기 궁금해서 찾아보니까 network의 각 node가 거의 모든 다른 node와 연결된 network를 의미한다고 함

 

 

3. 더 재미있는 부분?

 

논문에서 더 재미있는 부분을 언급했는데 original network의 초기 initialization parameter인 $\theta_{0}$를 사용하지 않고

 

새롭게 initialization된 parameter인 $\theta_{0}^{'}$을 사용하여 subnetwork를 training하면 original network와 동일한 성능을 더 이상 내지 않더라

 

 

여기서 말하는 winning ticket=lottery ticket는 original보다 덜 training해도 성능이 그에 상응하는 parameter가 적은 subnetwork

 

이러한 사실이 의미하는 바는 small인 subnetwork 반드시 적절하게 initialization된 상태에서 효과적으로 training될 수 있다는 뜻이다.

 

 

4. 한계점

 

증명이 안된 가설임

 

높은확률로 있을 것 같기는 한데 언제나 존재하는지도 사실 모름

 

그래서 어떻게 구하는지도 몰라

 

pruning된 것을 먼저 training시켜봤자 사실 이것이 lottery ticket인 것을 알려면

 

original network를 training시켜봐야만 알 수 있다

 

그래서 lottery ticket의 의미가 사실 상실되어버리는 거지

 

이후 original network를 최대한 덜 사용하면서 적은 cost로 lottery ticket를 찾아내려고 논문들이 여럿 등장함

 

찾아보니까 증명? 심지어 더욱 강력한 버전도 증명을 한것 같은데 어떻게 찾는지에 대해서는 잘 모르는듯