1. argmax 분해와 Greedy

자연어 생성에서 decoding이 정확히 뭘 하는 과정인지, 그리고 왜 문장 전체를 한 번에 구하지 않고 토큰을 하나씩 뽑아 나가는지 정리해봤다.

decoding이 풀려는 문제#

입력 문장 x가 주어졌을 때, 출력 문장 y가 나올 확률을 최대화하는 y를 찾는 것이 decoding의 핵심이다.

$$\underset{y_1,\dots ,y_t}{\mathrm{argmax}}\log P_{LM}(y_1,\dots ,y_t\mid \mathbf{x})$$

여기서 짚어둘 건 이 확률이 문장 전체에 대한 결합확률이라는 점이다. 토큰 하나의 확률이 아니라 y_1부터 y_t까지가 통째로 나올 확률을 본다.

왜 한 번에 못 구하나#

그러면 가능한 모든 문장 조합을 다 따져서 확률이 가장 큰 걸 고르면 되지 않나 싶다. 이걸 exhaustive search라고 하는데, 문제는 계산량이다. 사전 크기가 v이고 출력 길이가 t이면 따져야 할 문장 조합은 $v^t$개가 된다. 길이가 조금만 길어져도 감당이 안 된다.

chain rule로 분해해서 하나씩#

그래서 결합확률을 chain rule로 풀어 쓴다. 이건 근사가 아니라 정확히 같은 식이다.

$$P_{LM}(y_1,\dots ,y_t\mid \mathbf{x})=\prod _{i=1}^t{P}_{LM}(y_i\mid y_1,\dots ,y_{i-1},\mathbf{x})$$

앞 토큰들이 주어졌을 때 다음 토큰의 확률을 구하는 조건부확률의 곱이다. 덕분에 앞에서부터 토큰을 하나씩 예측하고, 그 결과를 조건으로 삼아 다음 분포를 추정하는 식으로 이어갈 수 있다. 다음 단어를 예측하는 auto-regressive language model이 하는 일이 정확히 이거다.

log를 씌우는 이유#

분해한 식은 0과 1 사이 확률값들의 곱이다. 곱이 계속되면 값이 0에 가깝게 작아져 수치적으로 불안정하다. 그래서 log를 취해 곱을 합으로 바꾼다.

$$\log \prod _i{P}_{LM}(y_i\mid \dots )=\sum _i\log P_{LM}(y_i\mid \dots )$$

곱의 누적이 덧셈의 누적이 되니 계산이 편하고 안정적이다. 0~1 값에 log를 취했으니 각 항은 음수가 되고, 합도 음수로 누적된다. 이 음수 누적 구조는 뒤에서 beam search의 길이 정규화 이야기로 다시 이어진다.

Greedy decoding과 그 한계#

가장 단순한 선택법은 greedy decoding이다. 매 타임스텝마다 확률분포에서 가장 확률이 높은 토큰 하나를 뽑아 다음 토큰으로 삼는다. 가장 높은 확률로 생성될 토큰을 그냥 가져가는 것이다.

문제는 매 시점의 최댓값이 문장 전체의 최적해를 보장하지 않는다는 데 있다. 필기를 다시 보니 내가 짚어둔 핵심이 여기 있었다. 어느 시점에서 정답이 아닌 토큰을 한 번 뽑으면, 그 선택이 그대로 뒤 토큰들의 확률분포에 개입한다. 가령 두 번째 선택에서 엉뚱한 토큰을 고르면 그 뒤 단어의 분포 자체가 달라진다. 게다가 greedy는 한 번 뽑은 토큰을 되돌릴 방법이 없다. 결국 greedy는 진짜 argmax를 근사할 뿐, 최적을 보장하지는 못한다.

이 한계를 보완하려고 매 스텝 후보를 여러 개 들고 가는 방법이 beam search다.