Beam Search

NLP(자연어처리)에서 많이 사용되는 Beam Search에 대해서 알아보고자 한다.

나는 이번 논문 주제인 챗봇에 대한 모델을 만들때 해당 알고리즘을 사용했다. 마침 이번학기 때 (3-2학기) 알고리즘 수업을 들었는데 Greedy search 그리고 DFS 와 비슷한 느낌을 받았다. 

Beam Search 어떻게 생겼고 어떠한 이유때문에 NLP에서 사용되는지 알아보자

	def naive_beam_search_decoder(predictions, k):
	sequences = [[list(), 1.0]]
	for row in predictions:
	all_candidates = list()
	for i in range(len(sequences)):
	seq, score = sequences[i]
	for j in range(len(row)):
	new_seq = seq + [j]
	new_score = score * -log(row[j])
	candidate = [new_seq, new_score]
	all_candidates.append(candidate)
	ordered = sorted(all_candidates, key=lambda tup: tup[1])
	sequences = ordered[:k]
	return sequences

view raw beam_search.py hosted with ❤ by GitHub

	import beam_search
	import random
	seq_len = 4
	V = 10
	predictions = [[random.random() for _ in range(V)] for _ in range(seq_len)]
	def main():
	beam_search.naive_beam_search_decoder(predictions , 5)
	if __name__ == "__main__" :
	main()

view raw main.py hosted with ❤ by GitHub

main.py 로 인하여 prediction은 2차원 리스트가 만들어 진다. 즉, 형태가 [[10개의 랜덤숫자], [10개의 랜덤숫자], [10개의 랜덤숫자], [10개의 랜덤숫자]] 으로 만들어진다. 

여기서 beam_search를 호출한다. beam_size(여기서는 k에 해당한다)는 5로 놓았다.

차근차근히 봐보자. 원래 남의 코드 보는게 진짜 인내의 과정이다. 나도 천천히 설명해 보겠다.

beam_search.py 에서는 방금 만든 prediction과 beam_size인 5를 인풋으로 받는다. 그 후 prediction의 하나인 row 즉, [10개의 랜덤숫자]를 for문에 

하고 있던 도중 수학 재시험을 본다고 한다. 다 하고 돌아오겠다. 그럼 안녕

 

왜 그럼 log를 이용할까?