WEEK8 : beam search in language model

1. language model

언어 모델에서 사용되는 beam search를 설명하기 전에, 먼저 언어 모델에 대한 설명을 기록한다.

 

언어모델은 단어 시퀀스에 확률을 할당하는 일을 하는 모델이다.

 

단어 시퀀스에 확률을 할당할 때 주로 사용하는 방법은 이전 단어들이 주어졌을 때 다음 단어가 나온 빈도를 이용하는 것이다.

양쪽의 단어로부터 중심단어가 나오는 빈도를 이용하여 단어 시퀀스에 확률을 부여하는 다른 방법도 있긴 하다.

 

확률 할당 시 많이 사용하는 방법은 이전 단어들이 주어졌을 때 다음 단어가 나오는 빈도를 이용하는 것이라고 하였는데,

이 확률을 수식으로 표현하면 다음과 같다.

 

$$ P(W) = P(w_1, w_2, w_3, ..., w_n) = \prod_{i=1}^{n}P(w_i|w_1, w_2, ..., w_{i-1}) $$

$$ = P(w_1)P(w_2|w_1)P(w_3|w_1, w_2)...P(w_n|w_1, w_2, ..., w_{n-1}) $$

 

---

2. greedy search

 

1) greedy search가 무엇인가?

greedy search(=hill climbing search)는 heuristic search에 속하는 방법으로, 최적해를 구하는 데 사용되는 근사적인 방법이다.

여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택하며 진행해나가는 알고리즘이다.

 

greedy search를 이용해 구한 해가 최적이라는 보장은 없다.

반대로, 최적의 해가 하나만 존재하는 uni-modal problem에서는 최적의 탐색 알고리즘이다.

 

https://www.geeksforgeeks.org/search-algorithms-in-ai/

 

2) language model에서 greedy search가 어떻게 사용되는가?

language model에서는 각 step마다 이전 단어들을 기반으로 다음에 나올 단어를 예측한다.

 

이 때 greedy search를 이용해 다음 단어를 예측하는 경우,

P(w_n|w_1, w_2, ..., w_n-1)이 최대가 되는 단어 w_n을 예측값으로 사용하게 된다.

즉 이전 단어가 주어졌을 때 특정 단어가 다음에 나올 확률을 구한 뒤, 그 중 최대 확률값을 산출하는 단어를 다음 단어로 선택하는 것이다.

 

3) language model에서 greedy search를 사용하면 무엇이 문제인가?

 

• 국소적으로는 최적의 단어이나, 전역적으로는 최적의 단어가 아닐 수 있다.
  • 즉, 전체 문장을 보았을 때 그 단어가 최적의 단어가 아닐 수 있다는 말이다.
• 문장 생성 시 input 단어가 동일하면 매번 동일한 문장이 생성된다.

---

3. beam search

 

1) beam search가 무엇인가?

beam search 역시 위에서 다뤘던 hill climbing search와 마찬가지로 heuristic search에 속한다.

beam search는 평가값이 우수한 일정 개수의 확장 가능한 노드만을 메모리에 관리하면서 최상 우선 탐색을 적용하는 기법이다.

즉, best first search에서 기억 노드의 수를 제한하는 방법이다.

 

 

https://d2l.ai/chapter_recurrent-modern/beam-search.html

 

 

2) language model에서 beam search가 어떻게 사용되는가?

language model에서는 각 step마다 이전 단어들을 기반으로 다음에 나올 단어를 예측한다.

 

이 때 beam search를 이용해 다음 단어를 예측하는 경우,

P(w_n|w_1, w_2, ..., w_n-1)을 모든 단어에 대해 구한 후 상위 K개의 단어만 남기고 나머지는 고려대상에서 제외한다.

첫 번째 step에서 이렇게 뽑힌 k개의 단어를 w_21, w_22, ..., w_2k라 하자.

 

그 다음에는 P(w_3|w_1, w_21), P(w_3|w_1, w_22), ... P(w_3|w_1, w_2k)를 모든 단어 w_3에 대해서 구한 뒤 상위 K개의 단어만 후보 단어로 고려하는 것이다. 

 

이러한 과정을 반복하면 최종적으로 K개의 sequence가 나오게 되는데, 이 중 최대 확률값을 가진 sequence를 최종 sequence로 선택한다.

위에 첨부한 사진을 보면 이해에 도움이 될 것이라 생각한다.

 

3) language model에서 beam search를 사용하면 무엇이 해결되는가?

greedy search를 사용하여 다음 단어를 선택하면 국소적으로는 최적의 단어이나, 전역적으로는 최적의 단어가 아닐 수 있다고 했다.

하지만 beam search를 이용하면 이러한 문제가 완화될 수 있다 (완전히 해결되는 것은 아니다)

 

이 때 기억하고자 하는 후보 노드의 개수가 많을수록 최적의 해에 가까워지지만, 속도가 느려진다는 단점이 존재한다.

반대로 후보 노드의 개수가 적을수록 최적의 해에서는 비교적 멀어지지만 속도는 빠르다는 장점이 존재한다.

 

그렇다면 후보 노드의 수가 적절한 지, 부적절한 지 어떻게 판단할 수 있는가?

 

---

4. error analysis on beam search

 

사람이 보기에 최적의 문장이라고 판단한 문장을 y, 알고리즘이 최적이라고 판단한 문장을 y_hat 라고 하자.

 

• 모델에 넣었을 때 P(y) > P(y_hat)인 경우
  • RNN 모델은 잘 학습되었으나, beam search에서 잘못 판단한 경우이다.
  • 따라서 beam search에서 기억하고자 하는 노드의 개수를 늘려야 한다.
• 모델에 넣었을 때 P(y) < P(y_hat)인 경우
  • RNN 모델이 잘못 학습된 것
  • 정규화를 수행하거나 학습데이터를 증가시켜 다시 학습해야 한다.

 

여러가지의 (y, y_hat) 쌍을 구한 뒤 각각의 sequence가 나올 확률을 구한 뒤

RNN model이 잘못된 경우가 많았는지, beam search가 잘못된 경우가 많았는지 판단하여 적절한 조치를 취하는 것이 중요하다.