[번역] Foundations of NLP Explained Visually: Beam Search, How It Works

💬 최대한 매끄럽게 해석하고자 노력했지만 어색한 문장이 있을 수 있습니다. 피드백은 언제나 환영입니다 🙂

---

원본 글 주소 : https://towardsdatascience.com/foundations-of-nlp-explained-visually-beam-search-how-it-works-1586b9849a24

Foundations of NLP Explained Visually: Beam Search, How it Works

 

NLP 모델의 Output 생성 방법

 

기계 번역 작업에 자주 사용되는 sequence-to-sequence 모델을 예로 들어보자.

예를 들어, 영어를 스페인어로 번역하는 데 이 모델이 사용된다면 모델은 소스 언어(영어)를 입력으로 받아 타겟 언어에서 소스 언어와 의미가 같은 문장을 출력할 것이다.

 

텍스트는 단어(또는 글자)의 시퀀스이고, NLP 모델은 소스 언어와 타겟 언어에 나타난 모든 단어로 이루어진 vocabulary를 생성한다.

 

모델은 소스 문장을 입력으로 받아 그 문장을 인코더 다음의 임베딩 레이어로 전달한다. 인코더는 입력 문장에서 핵심적인 특징만을 파악하는 압축된 표현을 출력한다.

 

인코더가 출력한 표현은 "<START>" 토큰과 함께 디코더로 넘어가고 디코더는 이를 사용하여 타겟 언어 문장의 압축된 표현을 자체 생성한다.

 

디코더에서 생성한 결과는 softmax와 이어지는 몇 개의 선형 레이어로 구성된 출력 레이어로 넘어간다. 선형 레이어는 출력 시퀀스의 각 위치에서 vocabulary에 있는 각 단어의 발생 가능성에 대한 점수를 출력한다. Softmax는 이 점수들을 확률로 변환한다.

 

물론 우리의 궁극적인 목표는 확률 출력이 아니라 타겟 언어로 된 문장을 만드는 것이다. 이 결과를 얻기 위해 모델은 타겟 문장의 각 위치에서 어떤 단어를 예측해야할지 결정해야 한다.

 

어떻게 해야 할까?

 

 

Greedy Search

 

확실한 방법은 각 위치에서 가장 높은 확률을 갖는 단어를 선택해서 그 단어로 예측하는 것이다. 이 방식은 빠르고 이해하기 쉬우며 종종 정답을 출력하기도 한다.

 

사실 Greedy Search는 이해하기 쉬워서 더 이상 설명할 것이 없다. 하지만 한 걸음 더 나아갈 수 있을까?

 

 

Beam Search

 

Beam Search는 Greedy Search보다 두 가지 향상된 점이 있다.

 

◾ Greedy Search는 각 위치에 가장 적합한 단어를 단 하나만 선택한다. 반대로 Beam Search는 N개의 단어를 선택하는 것으로 확장한다.

◾ Greedy Search는 각 위치들을 독립적인 것으로 본다. 어떤 위치에서 최적의 단어를 확인했을 때, 그 단어의 이전이나 이후에 어떤 단어가 왔는지 확인하지 않는다. Beam Search는 상위 N개의 단어를 고르고 현재 위치의 단어와 이전 위치의 단어들의 결합 확률을 고려한다.

 

하이퍼파라미터 'N'은 Beam width라고 한다.

 

이 방식이 Greedy Search보다 더 나은 결과를 제공한다는 것은 직관적으로 이해 가능하다. 왜냐하면 우리가 관심을 갖는 것은 최고의 완전한 문장인데 각각의 위치에서 가장 좋은 개별적인 단어만 고른다면 완전한 문장을 놓칠 수 있기 때문이다.

 

 

Beam Search 역할

 

Beam width는 2, 문자를 사용한 간단한 예시를 본다.

 

https://towardsdatascience.com/foundations-of-nlp-explained-visually-beam-search-how-it-works-1586b9849a24

 

 

첫 번째 위치

◾ 첫 번째 위치에서 모델의 출력 결과를 생각해보자. <START> 토큰으로 시작해서 각 단어에 대한 확률을 얻는다. 확률이 높은 두 개의 문자(Beam width가 2이기 때문)를 선택한다.

 

두 번째 위치

◾ 두 번째 위치에서는 첫번째 위치에 나올 수 있는 문자(확률이 높은 두 개의 문자)를 고정해두고 모델을 두 번 반복한다. 즉 첫 번째 위치에 올 수 있는 문자를 제한하고 가능한 첫 글자에 대해서만 브랜치를 만든다. 

◾  첫 번째 위치의 단어와 두 번째 위치의 단어를 결합했을 때의 확률에 기반하여 전체 중에서 가장 좋은 쌍을 선택한다. 첫 번째 집합에서 하나를 고르고 두 번째 집합에서 하나를 고르는 방식으로 진행되지 않는다.

 

세번째 위치

◾ 세번째 위치에서는 위의 과정을 반복한다. 첫번째 위치, 두번째 위치를 거쳐 고정된 두 글자와 세번째 위치 글자의 결합 확률을 보고 모델을 두 번 반복한다. 

◾ 한 번 더 전체 쌍 중에서 가장 확률이 높은 두 쌍을 고른다.

 

<END> 토큰을 만날 때까지 반복

◾ 이 과정은 특정 위치에서 <END> 토큰의 출현 확률이 가장 높을 때까지 반복된다.

 

최종적으로 만들어진 두 개의 시퀀스 중 확률이 더 높은 시퀀스로 결과를 예측한다.

 

 

Beam Search 작동 방식

 

우리는 이제 개념적인 수준에서 Beam Search를 이해했다. 한 단계 더 들어가 Beam Search가 어떻게 작동하는지 알아본다. 계속해서 같은 예제를 사용할 것이고 Beam width는 2이다.

 

Sequence-to-sequence 모델을 계속해서 보면, 인코더와 디코더는 몇 개의 LSTM 레이어로 구성된 순환 네트워크일 가능성이 높다. 순환 네트워크 대신 트랜스포머로 구현되었을 수도 있다.

https://towardsdatascience.com/foundations-of-nlp-explained-visually-beam-search-how-it-works-1586b9849a24

 

디코더의 구성 요소와 출력층에 집중하기로 한다.

 

첫 번째 위치

첫 번째 단계에서 디코더는 첫 번째 위치의 문자별 확률을 구하기 위해 인코더의 출력과 <START> 토큰을 사용한다.

 

https://towardsdatascience.com/foundations-of-nlp-explained-visually-beam-search-how-it-works-1586b9849a24

 

확률이 높은 A와 C가 선택된다.

 

두 번째 위치

이전과 같이 인코더의 출력을 이용해 디코더를 두 번 실행한다. 첫 번째 위치의 "<START>" 토큰과 함께 첫 번째 디코더 실행 시 두 번째 위치의 입력을 "A"로 미리 설정한다. 두 번째 디코더 실행에서는 두 번째 위치의 입력을 "C"로 설정한다.

 

https://towardsdatascience.com/foundations-of-nlp-explained-visually-beam-search-how-it-works-1586b9849a24

 

문자가 두 번째 위치에 올 확률을 구한다. 하지만 이 확률값은 독립적인 확률값이다. 처음 두 위치에서 결합된 문자 쌍에 대한 확률을 계산해야 한다. 'AB'의 확률은 첫 번째 위치에 'A'가 고정되었기 때문에 첫 번째 위치에서 'A'가 나타날 확률과 두 번째 위치에서 'B'가 나타날 확률을 곱한 것이다.

 

두 개의 디코더 모두 이 과정을 수행한다.

 

세 번째 위치

https://towardsdatascience.com/foundations-of-nlp-explained-visually-beam-search-how-it-works-1586b9849a24

 

처음부터 세 번째 위치까지 문자 세 개의 결합 확률을 계산한다. 

 

<END> 토큰을 만날 때까지 반복

"<END>" 토큰으로 끝나는 두 개의 최상의 시퀀스를 생성할 때까지 이 과정을 반복한다.