greedy decoding(greedy search)은 왜 최적이 아닐까?

1. greedy decoding

 

일반적으로 행하던 decoding 방법이다.

 

매 time step마다 계산된 확률분포중 가장 확률이 높은 단어를 하나씩 선택한다.

 

sequence 전체적으로 보는것보다 당장 현재 step에서 가장 확률이 높은 최적 단어를 뽑고자 하는 것이다.

 

순간순간에는 최적이지만 전체로 볼때는 최적이 아니라는 greedy algorithm에서 따온거겠지?

 

 

정답은 he hit me with a pie인데 he, he hit 생성하고 다음 단어 생성하는데 최적인 단어는 a라고 생각한거지..

 

그러면 이제 이 순간 다음부터는 뭐가 나오든 최종 결과는 무조건 잘못된거임

 

 

2. 이상적인 번역이란

 

이상적으로 input sequence x가 주어질 때 그것에 대한 번역인 translation y를 찾는다는 것은

 

y의 T개의 token $y_{1},y_{2},...,y_{T}$에 대하여 다음의 조건부확률을 최대화시키는 것이다.

 

 

분해할때 input은 y1부터 넣으니까 P(y1|x)로 분해를 먼저 시작한다는 점… 이게 자연스럽다

 

-------------------------------------------------------------------------------------------------------

이 확률식을 해석을 해보면 번역이라는 것은 input x를 넣으면 번역문 y를 뽑아낼 확률을 계산하는 것이다.

 

그런데 seq2seq 딥러닝이 번역을 할 때 번역문 y를 바로 뽑아내는 것이 아니고 token 하나씩 뽑아낸다는 점을 배웠다

 

input x를 먼저 다 읽어보고 첫번째 단어 y1을 뽑는다

 

그 다음 input x의 정보와 첫번째 단어 y1을 보고 나서 두번째 단어 y2를 뽑는다

 

그 다음 input x의 정보와 첫번째 단어 y1, 두번째 단어 y2를 뽑고나서 세번째 단어 y3를 뽑는다

 

그래서 딥러닝 과정에 맞는 자연스러운 확률 분해라는 점을 기억해야한다--------------------------------------------------------------------------------------------------------------------------

 

왜냐면 처음에 너가 분해할때 아무생각없이 이런식으로 해서 지적해본 것이다

 

 

물론 이렇게 분해할 수도 있지만 설명한대로 seq2seq 과정에 안맞아서 의미적으로 조금 아쉽다

 

왜냐하면 번역이라는 것이 input x를 먼저 넣으면 y1이 먼저 나오니까

 

x를 받고 y1을 넣는 P(y1|x)가 자연스럽지… 아무튼 중요한건 아님 생각이란 걸 하자는게 중요한거

 

 

 

3. greedy decoding은 왜 최적이 되는 것이 아닐까?

 

P(y|x)를 최대화한다는 것은 분해된 각 확률 P(y1|x) , P(y2|y1,x),.. 를 최대화하면 된다는 생각에 기반했다.

 

그런데 P(y1|x)가 최대가되는 y1을 뽑았다고 하자.

 

그 나온 y1을 이용해서 P(y2|y1,x)를 최대화시킨 y2를 뽑았다고 생각해본다면 사실 이런 경우도 있지 않을까?

 

P(y1|x)가 최대가 아닌 y1에서 P(y2|y1,x)의 최댓값이 되는 경우 A와

 

P(y1|x)가 최대일때 y1에서 P(y2|y1,x)가 최댓값이 되는 경우 B를 생각해보면 B보다 A가 큰 경우가 있을수있지 않을까?

 

그러면서  P(y1|x)가 최대가 아닌 y1에서 결국에 전체 확률인 P(y|x)가 최대가되는 경우가 존재할 수 있다는 점이다.

 

이러한 문제점을 해결하기 위해 여러가지 decoding 방법이 제안되었다

 

 

4. greedy search 구현

 

def sample(self, features, states = None):

    # 학습이 완료된 상태에서 이미지만 넣었을때 문장이 나오도록 해봅시다
    # 주어진 image feature들을 greedy search방법으로 caption들을 생성합니다.
    # Greedy search란? - https://ko.wikipedia.org/wiki/%ED%83%90%EC%9A%95_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

    sampled_ids = []
    inputs = features.unsqueeze(1)  # (1,256) -> (1,1,256)

    for i in range(self.max_seq_length):

        # [Do it yourself] 이미지에서 추출한 feature를 input으로 우선 넣은 후 연관성이 높은 단어를 예측합니다.(이때의 lstm의 입력 states = None입니다.)
        # 이때의 출력 states에는 tuple 형태로 2가지를 담고 있습니다. states = (hidden state의 상태, cell state의 상태)이것과 출력으로 나온 단어를 
        # 통해 다음에 나올 적절한 단어를 예측하게 됩니다.
        # 하단의 ?에 들어가면 좋을 변수들을 선정하여 채워주세요 (힌트 : LSTM은 출력을 다시 입력으로 받으며, 기존의 상태는 states에 저장합니다.)

        # hiddens: (batch_size, 1, hidden_size) == (1, 1, 512)
        # states: ([1,1,512], [1,1,512])
        hiddens, states = self.lstm(inputs, states)

        # Hidden layer의 결과를 Fully connected layer를 통해 가장 큰 값을 가지는 단어를 추정합니다.
        # outputs:  (batch_size, vocab_size) == (1, 9956)
        outputs = self.linear(hiddens.squeeze(1))

        # [Do it yourself] 수천개의 단어들 중에서 가장 큰 값을 가지는 단어의 argmax 위치만 필요합니다. 출력에서 max값을 가지는 위치를 뽑아주세요.
        # 자세한 사항은 다음을 참고하세요 https://wikidocs.net/52460 (힌트 : max를 이용하고 적당한 axis를 찾아주세요)
        _, predicted = outputs.max(1)

        # [Do it yourself] argmax위치의 단어(predicted)를 기존에 선택된 단어집(sampled_ids)에 추가(append 함수 이용)
        sampled_ids.append(predicted)

        #현재 만들어진 단어를 기반으로 다음 단어 예측을 위해 워드임베딩을 하여 다음 input으로 넣어줄 준비를 합니다.

        inputs = self.embed(predicted) # inputs: (batch_size, embed_size) == (1, 256)
        inputs = inputs.unsqueeze(1) # inputs: (batch_size, 1, embed_size)

    # sampled_ids: (batch_size, max_seq_length)
    sampled_ids = torch.stack(sampled_ids,1)

    return sampled_ids