이글은 towardsdatascience.com의 내용임. (링크)
An intuitive explanation of Beam Search
이 글에서 목표 언어에 대해 문장에서 가장 관련있는 단어를 찾기 위해 seq2seq 알고리짐을 사용는 neural machine translation 어떻게 개발되는지에 대해 알아본다.
Beam search란
빔써치(beam search)를 이해하기 위해 seq2seq의 신경 기계 번역(neural machine translation) 사용 케이스를 살펴본다.
Seq2Seq 모델은 기본 블록으로 LSTM(Long Short Term Memory) 또는 GRU(Gated Recurrent Unit)을 사용하는 인코더와 디코더 프레임워크를 사용한다.
인코더는 소스 정보를 인코딩하는 소스 시퀀스를 매핑하고 디코더로 전달한다. 디코더는 출력 시퀀스를 생성하기 위해 초기 입력으로 start-of-string <START>을 덧붙여 입력으로써 디코더로 부터 인코딩된 데어터를 가지고 온다.
여기서 소스 시퀀스는 힌디어 문장이다. 그리고 목표 시퀀스는 영어로 생성된다.
어떻게 목표 시퀀스를 위한 최고이면서 가장 가능성있는 단어를 선택할까?
간단한 접근은 목표 언어로된 단어집을 갖는 것이다. 소스 문장 기준으로 10,000단어를 말하고 10,000개의 목표 단어 각각에 대한 확률을 얻는다.
목표 언어에서 소스 문장에 대해 여러개의 번역이 있을 수 있다.
무작위로 번역을 선택해야 하는가?
목표는 최고로 그리고 가장 그럴듯한 번역된 단어를 선택하는 것이다. 따라서 소스 문장 기분으로 최고 확률을 갖는 목표 단어를 선택한다.
단지 최고의 번역 하나만을 선택해야 하는가?
탐욕적 검색(Greedy Search) 알고리즘은 각 단계에서 입력으로 최고 대표 샘플 하나만을 선택한다. 단지 최고의 하나만을 선택하는 것은 현재 단계에서는 적합할 수 있지만, 전체 문장을 구성할때 차선책(sub-optimal choice)일 수 있다.
빔써치(beam search) 알고리즘은 조건부 확률에 따라 각 단계에서 입력 시퀀스에 대한 여러개의 대안을 고른다. 대안의 수는 빔의 넓이 B(Beam Width B)로 불리는 파라미터에 따른다. 각 단계에서 빔써치는 해당 단계에서 가장 선택될 가능성이 높은 선택으로 가장 높은 확률을 갖는 최고 대안의 수 B를 선택한다.
이를 이하하기 위한 예제를 살펴보자
여기서 빔 넓이는 3, 영단어집은 10,000개로 한다.
Step 1: 입력 문장이 주어지면 가장 높은 확률을 가진 상위 3개의 단어를 찾는다. 가장 그럴듯한 단어의 수는 빔 넓이에 따른다.
- 인코딩된 입력 문장을 디코더에 입력한다. 디코더는 그러면 단어집의 모든 10,000개의 단어에 softmax를 적용한다.
- 10,000개의 확률로부터 가장 높은 가넝성을 가진 상위 3개의 단어만을 선택한다.
- 빔 넓이가 3으로 설정되었기 때문에 번역된 단어를 위한 최고이면서 가장 그럴듯한 대안은 3개로 한다.
- 만약 빔 넓이를 10으로 하면 가장 가능성이 높은 상위 10개 단어를 선택한다. 지금은 상위 3개 단어를 저장한다 : 메모리에 I, My 그리고 We
Step 1: 입력 문장에 기초하여 가장 높은 가능성을 가진 3개 단어를 찾는다.
탐욕적 검색은 항상 단지 하나의 최고 대안만을 고려한다.
Step 2: 조건부 확률을 기반으로 첫번째와 두번째 단어에 대한 3개의 최고 쌍을 찾는다.
Step 2: 번역된 문장의 첫번째와 두번째 단어에 대해 상위 3쌍의 단어를 찾는다.
- 입력으로써 Step 1으로부터 첫음 선택된 3 단어(I, My, We)를 두번째 단계로 보낸다.
- 두번째 단어를 위한 최고의 3가지 대안을 찾기 위해 단어집 내 10,000개의 단어 모두에 softmax를 적용한다. 이를 진행하는 동안, 조건부 확률을 사용하여 가장 그럴듯한 쌍을 구성하는 첫번째와 두번째 단어의 조합을 알게된다.
- 첫번째와 두번째 단어에 대한 최고의 3개 쌍을 찾기 위해 첫번째 단어 "I"를 가져와 단어집내 10,000개의 모든 단어에 softmax를 적용한다.
- 다른 두 단어가 선택한 "My", "We"에 대해 확률을 평가한다.
- 첫번째와 두번째 단어의 상위 3가지 쌍을 선택하기 위해 30,000가지 다른 조합을 실행한다.
- 상위 첫번째와 두번째 단어 쌍의 조합은 "I am", "My parents"와 "I will"이다.
- 높은 조건부 확률을 갖는 첫번째와 두번째 단어로써 "We"와 쌍을 이루는 어떤 단어도 찾을 수 없기 때문에 이제 첫번째 단어 "We"를 뺀다(drop).
- 매 단계에서 이들 부분적인 문장 조각과 출력을 평가하기 위해 인코더-디코더 네트워크의 3개 복사본을 인스턴스화 한다. 테느워크 복사본의 수는 빔 넓이의 크기와 동일하다.
Step 3: 입력 문장과 선택된 첫번째와 두번째 단어에 기초하여 첫번째, 두번째 그리고 세번째 단어에 대한 3가지 최고의 쌍을 찾는다.
Step 3: 번역된 문장에서 그럴듯한 첫 3개 단어를 찾는다.
- 입력 문장과 상위 첫번째와 두번째 단어 쌍의 조합인 "I am", "My Parents" 그리고 "I will"과 함께 가장 높은 조건부 확률을 갖는 세번째 단어를 찾는다.
- 다시 최고면서 첫번째, 두번째 그리고 세번째 단어의 가장 그럴듯한 조합을 선택하기 위해 30,000번의 조합을 수행하고 seq2seq 인코더-디코더 메델의 3개 복사본을 인스턴스화 한다.
- 상위 3개의 첫번째, 두번째 그리고 세번째 단어 조합은 "I am visiting", "I will visit" 그리고 "I am going"이다.
- 상위 3개 조합내에서 "My Parents"로 첫번째, 두번째 그리고 세번째 단어조합을 찾을 수 없기 때문에 "My parents" 조합을 뺀다.
이 절차를 계속 하면 가장 높은 확률을 가진 3 문장이 선택된다. 상위 3개 문장은 다양한 길이이거나 같은 길이 일 수 있다.
가장 폰은 조건부 확률과 다른 길이를 가진 3개의 출력 문장
마지막으로 가장 높은 확률을 가진 문장을 디코더을 출력으로 선택한다.
더 큰 빔 넓이값이 더 좋은 번역을 할까?
더 큰 빔 넓이는 더 나은 번역을 하지만 많은 메모리와 컴퓨팅 파워를 사용한다.
빔 넓이 3과 단어집 10,000개 일때, 매 단계에서 30,000개의 조합이 평가되고 3개의 인코더 디코더의 인스컨스가 생성되고 최고 문장길이는 9였다. 다수의 인코더-디코더 복사본을 생성하고 각 단계에서 30,000개의 조건부 확률을 계산하는 것은 많은 메모리와 컴퓨팅 파워가 필요하다.
더 작은 빔 넓이는 더 낮은 품질의 번역으로 이어지지만 따르고 메모리 사용과 컴퓨팅 파워 측면에서 빠르고 효과적일 것이다.
결론
빔 써치는 NLT(Neural Machine Translation), 이미지 캡셔닝, 챗봇 등과 같은 seq2seq Depp NLP 알고리즘에 대해 가장 유명한 검색 전략이다.
빔 써치는 조건부 확률을 사용하여 빔 넓이에 따라 다수의 최고 옵션을 고려한다. 이는 차선책인 Greedy search보다 좋다.