Natural Language Generation은 단어들의 sequence 를 아웃풋으로 예측하는 task 이다. 일반적으로 generation model은 각각의 decoding time step 에서 전체 단어 사전에 대한 확률 분포를 예측한다. 따라서 실제로 단어를 생성해내기 위해서는 모델의 예측 확률 분포를 이용해 각 time step의 단어로 변환하는 과정이 필요하다.
모델이 예측한 확률 분포에 대해 디코딩하기 위해서는 예측된 확률 분포에 따라 가능한 모든 output sequence의 조합을 Search (탐색) 해야 한다. 그런데 일반적으로 단어 사전은 수만 개의 토큰을 포함하고 있기 때문에 전체 공간을 탐색하는 것은 계산적으로 불가능하다. 따라서 실제로는 휴리스틱한 방법을 사용해 충분히 좋은 output sequence 를 생성해내도록 한다. 휴리스틱 탐색 방법은 근사적이거나 충분히 decoding된 output sequence를 반환한다.
1. Greedy Search Decoder
가장 직관적인 방법은 output sequence 에서 생성된 각각의 확률 분포에서 가장 값이 높은 토큰을 선택하는 탐욕방법이다. 각각의 time step에서 가장 값이 높은 단어들을 최종 sequence 로 사용한다. 이 방법은 직관적이고 구현이 간단하며 속도가 빠르기 때문에 대부분의 경우 잘 작동한다. 하지만 몇몇 경우에는 최적점과는 거리가 있을 수 있다.
2. Beam Search Decoder
Beam Search 는 Greedy Search와 함께 가장 많이 사용되는 휴리스틱 방법이다. 각각의 time step에서 가능도가 가장 높은 하나의 토큰을 선택하는 Greedy와 달리 각 step에서 탐색의 영역을 k개의 가장 가능도가 높은 토큰들로 유지하며 다음 단계를 탐색한다. 이때 k는 사용자가 지정하는 hyper-parameter 이다. k를 크게 하면 더 넓은 영역을 탐색하기 때문에 더 좋은 target sequence를 생성할 수 있지만, 그만큼 속도가 느려지기 때문에 조절이 필요하다. 일반적으로 기계번역에서는 beam size k를 5 또는 10 으로 설정한다.
참고로 Greedy Search의 경우는 beam 이 1인 탐색과 같다.
Beam Search Algorithm
parameter k가 주어질 때 예측된 확률 분포의 sequence에 대해 beam search를 진행하는 과정은 다음과 같다.
(1) 각 step에서 각각의 후보 sequence를 모든 가능한 다음 step으로 확장한다.
(2) 확장된 후보 step 에 대해 점수를 계산하는데, 점수는 모든 확률 값을 곱하여 얻는다.
(3) 가능도가 높은 k개의 sequence만 남기고, 나머지 후보들은 제거한다.
(4) sequence가 끝날 때까지 위 과정을 반복한다. 이때 sequence의 끝을 판별할 때,
- < eos > 토큰이 등장함
- 설정한 최대 길이에 도달
- threshold likelihood 밑으로 probability가 낮아짐
등의 기준을 사용할 수 있다. 이때 각 time step에서의 확률 값은 V 차원 단어 사전에 대한 softmax 값으로 매우 작은 값을 가질 수 있다. 따라서 decoding step이 진행됨에 따라 이 값들을 계속 곱하게 되면 부동소수점 연산에서 underflow가 나타날 수 있기 때문에, 확률 값에 자연로그 log 변환을 사용한다. 또한 최소화를 통해 해를 찾기 위해 부호 변환을 적용하여 확률 값에 대한 negative log를 곱하는 방식을 사용하는 것이 일반적이다.
[Reference]
https://littlefoxdiary.tistory.com/4
http://www2.statmt.org/nmt-book/
