안녕하세요, 박천성 연구원입니다. 이번 포스트에서는 ICLR 2018 oral 로 발표되는 논문 “Breaking the Softmax Bottleneck: A High-Rank RNN Language Model, ICLR 2018, Yang “을 소개하려고 합니다. 주변에서도 ‘좋은 논문이다’라는 이야기를 많이 들었는데, 읽어보니 정말 좋은 논문이라 이렇게 소개해보려고 합니다.

먼저 이 논문의 main contribution 두가지를 말씀드리고 싶습니다.

  1. 이론적 측면 : 이 논문에서는 일반적으로 language modeling에 아무런 의심없이 사용하는 사용하는 RNN + softmax function이 의도치 않은 한계점을 갖게 된다는 점을 maxtrix fatorization측면에서 분석하여 아주 쉽게 증명해냈습니다. 그리고 그것을 해결해줄 아주 간단하지만 효과적인 방법론 MoS(Mixture of Softmaxes)도 제시했습니다.
  2. 실험적 측면 : 이 논문에서 제시한 방법(MoS)을  State of the art model에 적용해 새로운 State of the art를 달성했고,  단어 단위의 language modeling이 필요한 Penn Treebank and WikiText-2 datasets 두개 모두에서 상당한 차이로 좋은 결과를 얻었습니다. 또한 음성으로부터 text를 생성해내야하는 Switchboard dataset에서도 기존에 사용하는 softmax에 비해 더 좋은 성능을 낸다는 것을 보여주었습니다.

 

Language Modeling

rnn
그림 1. Basic RNN model [3]
위 그림에서 처럼, 일반적인 RNN 모델은 hidden state(그림 1에서 s_t 에 해당)가 output projection matrix(그림 1에서 V 에 해당)와 곱해진 뒤 softmax가 씌워져 최종 probability 를 만들어 냅니다.

 

Softmax bottleneck

softmax.png
수식 1. softmax

그림 1에서 s_t h_c V W  라고 생각하시면 이해하기 쉬우실텐데요,  다들 아시겠지만 수식 1은 대부분의 RNN이 language modeling을 할때 사용하는 softmax 수식입니다. 이 softmax 수식을 자세히 파헤쳐 보겠습니다.

 

스크린샷 2018-03-16 오후 5.14.28.png
수식 2. softmax 의 goal

결국에는 softmax를 통해 modeling 하려는 target은 수식 2 에서의 실제 단어의 등장확률 P^{*} 입니다. 모델로부터 실제 probability를 아주 똑같이 예측하는것이 Goal이겠죠.

 

스크린샷 2018-03-16 오후 5.26.35.png
수식 3. A^* , H_\theta W_\theta 정의

수식 3. 과 같이 A^{*} , H_\theta W_\theta 를 정의해봅시다.

 

스크린샷 2018-03-16 오후 5.40.28.png
수식 4. A   정의

수식 4처럼 A 라는 matrix를 정의해봅시다. A 는 P^{*}   P 로만 바뀐 matrix 입니다. 수식 2에서 P = P^{*} 가 goal이었기 때문에 수식 4처럼 A = A^{*} 가 goal이 됩니다.

 

Aprime.png
수식 5. A'   정의

증명을 위해 A'  을 수식 5와 같이 정의해봅시다.

스크린샷 2018-03-16 오후 5.54.29.png
수식 6.  softmax 의 log 전개

수식 6 처럼 softmax에 씌워진 log를 전개해서 풀어낼 수 있습니다. 위에 A 를 같이 써놓은 데에는 이유가 있습니다. 눈치가 빠르시거나 수학을 잘하시는 분들은 벌써 감을 잡으셨겠지만, A 를 풀어쓰기 위해 비슷한 형태로 만들고 있는 중입니다.

스크린샷 2018-03-16 오후 6.09.34.png
수식 7. A 전개

수식 7 처럼 A 를 풀어쓸 수 있습니다. 수식 6을 사용해서 전개하면 수식 7의 오른쪽에 해당하는 matrix 와 같이 전개됨을 알 수 있습니다.

스크린샷 2018-03-16 오후 6.13.49.png
수식 8. F(A) 정의

수식 8 처럼 집합  F(A) 를 정의해봅시다.  J_{N,M} 은 모든 element가 1로 이루어진 matrix입니다.

스크린샷 2018-03-16 오후 6.22.26.png
수식 9. \Lambda{} J_{N,M}  예시

수식 9는 A 에 더해지는\Lambda{} J_{N,M}  이 어떻게 생긴 matrix인지 이해를 돕기 위해 예시를 써보았습니다. 이 term은 row 가 똑같은 숫자로 이뤄진 어떠한 matrix 도 될 수 있습니다.

스크린샷 2018-03-16 오후 6.28.27.png
수식 10.   \Lambda{} J_{N,M}  과  F(A)

수식 10처럼\Lambda{} J_{N,M}  를 정의해놓으면, 수식 6에서 얻은 (수식 10 에서의 제일 윗 수식) 을 통해 어떤 연관성을 짐작하실 수 있을겁니다.

스크린샷 2018-03-16 오후 6.48.37.png
수식 11.  H_\theta W_\theta^{\top} 과 F(A)

수식 11에서 볼 수 있듯이  H_\theta W_\theta^{\top}   F(A) 에 포함 됨을 알 수 있습니다.

스크린샷 2018-03-16 오후 6.54.05.png
수식 12.  A'  과 F(A)

결국엔 수식 5에 의해 A' 은 F(A)  에 속하게 된다는 것을 의미합니다. 이제 본격적으로 F(A)  의 성질을 이용해 softmax bottleneck이 생긴다는 주장을 증명해보도록 하겠습니다.

스크린샷 2018-03-19 오후 1.54.57.png
수식 13. F(A) set의 rank 성질

수식 13은 F(A) 에 속하는 matrix들이 갖는 성질을 서술하고 있습니다. F(A) 에 포함되는 matrix는 rank가 거의 비슷하다라는 내용입니다. 이 성질을 먼저 증명해보도록 하겠습니다.

 

스크린샷 2018-03-19 오후 1.57.48.png
수식 14.  property 2에 대한 증명 1.

A_1  A_2  J_{N,M} 과의 linear combination 으로 표현할 수 있게됩니다. 수식 14에서처럼 이것을 row벡터로 풀어서 보면 더 정확히 둘의 rank가 최대 1까지만 차이가 난다는 것을 알 수 있습니다. A_1  A_2 를 서로 바꾸어서 써보면 대칭적인 수식을 쓸 수 있기 때문에, 아래 수식 15와 같은 수식을 도출 할 수 있게되어, 수식 13의 rank 성질을 증명할 수 있게됩니다.

스크린샷 2018-03-19 오후 2.03.37.png
수식 15.property 2에 대한 증명 2.
스크린샷 2018-03-19 오후 2.06.28.png
수식 16. A' 의 rank bound

수식 16은 기본적인 rank 의 성질입니다. A' 가  H_\theta W_\theta^{\top} 이기 때문에 rank의 bound가 d  가 되게 됩니다. A' 수식 15와 수식 16을 조합해 보면 다음과 같은 사실을 알 수 있게됩니다.

 

스크린샷 2018-03-19 오후 2.17.15.png
수식 17. softmax bottleneck

A 가 A^{*} 보다 훨씬 작은 값인 rank를 갖게 된다는 것입니다. d + 1 이 될 수도 있지만 작은 수이기 때문에 무시하겠습니다. 최종적으로 모델은 A 를 A^{*} 가 되게 만들어야 하는데 A 의 rank가 A^{*} 에 비해 훨씬 작은값을 가질수있다는 것, 그것을 softmax bottleneck이라고 지칭하며 본 논문에서는 한계점이라고 지적하고 있습니다.

해결책 : Mixture of Softmaxes

스크린샷 2018-03-19 오후 3.15.45.png
수식 18. Mixture of Softmaxes (MoS)

논문에서 제안하는 softmax bottleneck의 해법은 Mixture of Softmaxes(MoS)라는 아주 단순하면서도 효과적인 방법인데요. 수식이나 구조는 정말 단순합니다. softmax를 여러개의 모델로부터 조합하여(weighted sum) 최종 probability를 도출해냅니다. 단어 그대로 mixture 인 셈이죠. 수식으로만 보면 이해가 잘 안되니 그림을 살짝 그려보았습니다.

스크린샷 2018-03-19 오후 3.38.41.png
그림 2. Mixture of Softmaxes

그림 2 의 왼쪽 모델은 그림 1과 같이 기본적인 RNN에 softmax로부터 probability를 얻어내는 모델입니다. 반면 오른쪽 모델은 논문이 제안하는 Mixture of Softmaxes 의 예시 모델입니다. 윗 레이어들을 보시면 k개의 서로 다른 weight들을 가지고 mixture를 만들어 최종 probability를 만들어 내는 것입니다.  이렇게 mixture로 probability를 구하게 되면 왜 softmax bottleneck을 해결할 수 있을까요?

 

스크린샷 2018-03-19 오후 3.42.26.png
수식 19. \hat{A}_{MoS}

수식 19에서 \hat{A}_{MoS} 를 풀어서 써보았는데요, 이전 A' 과는 달리 log term이 벗겨지지 않는 구조가 되어버립니다. weighted sum 의 인자인 \pi_{k} 때문인데요, 이 인자 덕분에 \hat{A}_{MoS} 의 rank는 A'  과 달리 rank가 d 에 bound되지 않습니다. 만약 이 \pi_{k} term이 \exp 안에 들어가면 어떻게 달라질까요?

 

스크린샷 2018-03-19 오후 3.53.13.png
수식 20. Mixture of Contexts (MoC)

위 수식 20 처럼, 전개가 되고, log를 만나면 아주 쉽게 \exp 과 만나 벗겨지게 됩니다. 따라서 A' 과 같이 rank가 d 에 bound 됩니다.

장점

MoS 말고도, rank가 d 에 bound 되지 않게 만들 수 있는 방법은 많지만, softmax의 성질을 최대한 변형시키지 않으면서 좋은 성능을 내는 MoS 방법론. 본 논문에서는 크게 2가지 장점이 있다고 주장합니다.

  1. Improved expressiveness (compared to Softmax)
    • rank가 d 에 bound 되지 않기때문에 훨씬 더 표현력이 뛰어나다고 할 수 있습니다.
  2. Improved generalization
    • 비슷한 parameter size를 같는 모델이면 softmax에 비해 small dimension을 사용할 수 있고,  이것이 overfiting을 막아줄 수 있기에 더 generalization 이 잘 될 수 있다고 합니다.

결과

결과를 보기에 앞서 비슷한 모델 사이즈일때 성능이 우수한가? 그리고 속도는 심각하게 느리지 않은가? 이 두가지가 궁금했는데 그것들을 모두 논문에 잘 담아놓았습니다.

 

스크린샷 2018-03-19 오후 4.05.36.png
Performance – Penn Treebank[4] dataset
Penn Treebank dataset 에서는 오히려 적은 parameter size인 모델을 가지고, large margin을 내며 우수한 성능을 보여주었습니다.

 

스크린샷 2018-03-19 오후 4.11.38.png
Performance – WikiText-2[5] dataset
WikiText-2 dataset 에서는 좀더 많은 parameter를 쓰긴 했지만 large margin을 내며 우수한 성능을 보여주었습니다.

 

Untitled.png
Performance – Switchboard[6] dataset
앞서 두 dataset와는 조금 다른 성격인 Switchboard dataset (음성을 인식하여 text를 생성) 에서 동일한 모델에 MoS만 적용하여 좋은 성능을 냄을 보여주었습니다.  여러 dataset, 조금 다른 task까지 적용하여 상당히 좋은 성능을 보여주어서 놀라웠습니다.

스크린샷 2018-03-19 오후 4.16.47.png
Table – rank 숫자 비교 및 rank 별 성능 비교

왼쪽 table은 Softmax 와 MoC가 정말로 rank가 bound 되는 것인지, 그리고 MoS의 rank는 정말로 bound 되지 않는 것인지를 보여주는 table입니다. 그리고 오른쪽 table은 rank가 bound되지 않는 것이 정말로 성능향상에 도움이 되는 경향이 있는 것인지를 보여주는 table입니다. rank rk 커진다고 무조건 성능이 좋은것은 아니지만, 성능이 어느 한계점까지는 증가하는 경향이 있다는것을 알 수 있습니다.

스크린샷 2018-03-19 오후 4.19.53.png
Table – Mos training 속도비교

성능이 좋은 MoS의 단점은 너무나 명백합니다. 바로 속도이겠죠? 얼마나 느려지는지를 논문에서 잘 수치화하여 정리해 놓았습니다. MoS 15가 성능이 가장 좋았기 때문에 MoS 15까지 수치화해놓은것 같은데요. WT2/best-1 case에서 6.4배나 느려지는 것만 제외하면 (GPU를 여러대 쓰면 차이가 줄어드네요) 성능에 비해 크게 느려지는 것은 아니라고 생각이 듭니다.

 

결론

아주 직관적이고, 훌륭한 증명과정을 통해 한계점을 정확히 지적햇으며, 간단하지만 효과적인 아이디어로 좋은 성능을 보여주는 훌륭한 논문이라고 생각합니다.

Language model을 다루시는 분이라면 앞으로 결과를 report하는 table에서 “MoS k = 15 ” 가 적혀있는 row를 많이 보게 될지도 모르겠습니다. 마치 beam size = 5 처럼요? ㅎㅎ

 

[1] Breaking the Softmax Bottleneck: A High-Rank RNN Language Model, ICLR 2018, Yang

[2] https://smerity.com/articles/2017/mixture_of_softmaxes.html

[3] http://www.wildml.com/2015/09/recurrent-neural-networks-tutorial-part-2-implementing-a-language-model-rnn-with-python-numpy-and-theano/

[4] Recurrent neural network based language model. In Interspeech, volume 2, pp. 3, 2010, Mikolov

[5] Pointer sentinel mixture models. arXiv 2016. Merity

[6] Switchboard-1 release 2. Linguistic Data Consortium, Philadelphia, 1997. Godfrey and Holliman

Posted by:Cesc Chunseong Park

One thought on “Breaking the Softmax Bottleneck: A High-Rank RNN Language Model (ICLR 2018 Oral)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s