Beam Search
Exhaustive search
지금까지 배운 모델의 형태는 output을 greedy 하게 내놓기 때문에, output을 하나만 잘 못 출력해도 그 뒤의 output까지 모두 꼬여 버리게 된다. 하지만 뭔가 잘못되었다는 것을 중간에 깨달아도 다시 되돌아갈수는 없다.
y가 출력, x가 입력일 때 우리가 본래 원하는 값은 아래 값을 최대화 하는 것이다.
$P(y|x)=P(y_1|x)P(y_2|y_1,x)P(y_3|y_2,y_1,x)$ ... $P(y_{T}|y_1,...,y_{T-1},x)=\prod_1^TP(y_t|y_1,..y_{t-1},x)$
다만 이렇게 하려면 모든 경우의 수를 따져야 하는데 시간 복잡도는 $O(V^t)$의 연산이 필요하다. 따라서 이전의 greedy한 방법과 위와 같은 bruth-force 느낌의알고리즘의 절충 안으로 제시된 것은 Beam search알고리즘 이다.
Beam search
Beam search는 디코더의 각 time step마다 k개의 가능한 경우를 고려해 최종 K (beam size)개의 output중에서 가장 확률이 높은것을 선택하는 방식이다.(보통 beam size는 5 ~ 10)
K개의 출력은 hypothesis라고 한다. 각 확률을 곱하는 것으로 각 hypothesis의 확률을 구해야 하지만 log를 사용해 곱셈을 덧셉으로 계산할 수 있다.
$score(y_1,...,y_t)=logP_{LM}(y_1,...,t_t|x)=\sum_{i = 1}^t logP_{LM}(y_i|y_1,...,y_{i-1},x)$
Beam search는 무조건 최선의 값을 찾아내지는 못한다. 다만 계산의 효율을 늘리고 기존 greedy한 방법보다는 최선의 결과를 얻을 수 있다.
ex. k = 2 일때 beam search
위 그림에서 첫 단계를 제외한 매 timestep에서 k개의 갈래로 부터 다시 각각 k개의 갈래를 생성해내므로 $k^2$만큼의 연산을 수행하게 된다. 다만 이중에서 다시 최선의 k개를 선택하게 되므로 그 크기가 축소된다. 매 순간 가장 확률 값이 높은 갈래만을 선택하여 알고리즘이 수행된느 것을 확인할 수 있다.
Beam search decoding에서는 각 hypothesis가 서로 다른 time step에서
Beam search는 미리 정해둔 time step $T$에 도달하거나 미리 정해둔 n 개의 완료된 문장이 생성되면 알고리즘이 종료된다.
알고리즘이 종료되면 저장된 completed hypothesis에서 다시 가장 높은 확률 값을 가진 hypothesis가를 선택하여 최종적으로 출력을 내보낸다. 그런데 확률의 로그 값은 항승 음수이므로 sequence의 길이가 길어질수록 반드시 확률 값이 낮아진다는 문제가 존재한다. 따라서 아래와 같이 sequence의 길이로 score 값을 나누어 정규화된 값이 최종 candidate score가 된다.
$score(y_1,...,y_t)=\frac{1}{t}\sum_{i=1}^tlogP_{LM}(y_i|y_1,...,y_{i-1},x)$
문장 번역 평가 방법
자연어 문장 번역을 평가할때 실제결과와 예측 결과를 단순 위치 기반으로 구분하게 되면 정확한 정확도를 계산할수 없다. 예를 들어 I love yo와 oh I love you의 경우 위치 기반으로 정확도를 측정하면 0%의 결과가 나온다. 그래서 위치 기반이 아닌 다른 종류의 성능 평가 방법에 대해 알아 보자.
정밀도/재현율/F-measure
정밀도는 보이는 것으로 판단할 수 있는 수치이다. 검색을 예로 들면, 어떤 키워드로 검색을 했을 때 우리는 그 중 원하는 정보가 몇 개인지 전체 검색 결과에 대하여 percentage를 측정할 수 있다.
즉, 예측된 결과의 크기와 우리가 원하는 정보량의 비를 측정할 수 있다.
재현율은 실제로 잘 된건지 전지적 시점에서 판단할 수 있는 수치이다. 어떤 키워드로 검색했을 때 원래 나와야 할 정보가 100개인데 그 중 5개만 나왔다고 해도 우리는 그 수치를 직접 판단할 수 없다. 이렇게 판단할 수 없는 수치를 재현율로 나타내며, 이는 실제 나와야 할 결과의 크기와 맞게 나온 정보량의 비로 나타낸다.
정밀도와 재현율은 둘다 중요한 수치로, 둘 모두 높은 결과를 낼 수 있는 모델이 좋은 모델일 것이다. 이러한 배경에서 둘 모두를 고려할 수 있도록 계산된 값이 바로 F-measure로, 이는 정밀도와 재현율의 조화평균이다.
하지만 F-measure만을 평가하게 되면 또 다른 문제점이 발생하는데, 순서(order)가 맞지 않는 문장에 패널티를 주는 것이 불가능하다. 단어는 모두 일치하는데 순서가 완전히 뒤바뀐 문장이 생성될 경우 F-measure가 100%로 계산되겠지만, 이는 우리가 원하는 형태가 아니다.
BLEU score
BLEU(Bilingual Evaluation Understudy)는 N-gram overlap를 활용하여 수치를 추가적으로 사용하여 순서 및 F-measure에 준하는수치를 동시에 평가 할 수 있다.
n-gram은 연속된 $n$개의 단어가 reference(target) 문장에 존재하는지를 평가하는 수치로, $n$은 보통 1부터 4까지의 수를 모두 활용한다.
$BLEU=min(1,\frac{length_of_prediction}{length_of_reference})(\prod_{i=1}^4precision_i)^{\frac{1}{4}}$
BLEU score는 보통 한 개의 single sentence가 아닌 전체 말뭉치(corpus)에 대해 계산되며, 여기서는 precision중 작은 값에 지나친 가중치를 주지 않기 위해 기존 조화평균 대신 기하평균을 사용한다.
Reference
이 글은 여기를 참고하여 작성하였습니다.
