A Hierarchical Recurrent Encoder Decoder for Generative Context Aware Query Suggestion Review

5 minute read

Abstract

  • 임의의 길이를 갖는 이전 쿼리 sequence를 고려할 수 있는 확률적 suggestion 모델이다. 즉, 맥락을 알아내 generation하는 모델이다. 각각의 encoder와 decoder에 GRU를 이용했고 LTR 알고리즘을 사용했다. HRED를 사용하니 빈번하지 않은 context에 대해서도 잘 예측할 수 있었다.

1. Introduction

  • generative한 통계 모델을 제시했다.
  • 빈도수가 많은 쿼리뿐만 아니라 빈도수가 적은 쿼리 역시 synthetic하게 suggestion을 만들어내는 맥락을 아는 모델이다.
  • 주어진 순차적인 쿼리를 prefix로 가정하고, prefix 다음에 올 가장 확률이 높은 순차적인 단어를 예측한다.
  • 쿼리 suggestions은 주어진 하나 이상의 쿼리에 대해 가능성 있는 연속적인 단어를 샘플링해서 얻어낼 수 있다.
  • 예를 들어, 유저 쿼리 세션이 cleveland gallery -> lake erie art와 같이 두 가지 쿼리로 이루어져 있다면, 모델은 순서대로 cleveland, indian, art, 을 예측한다. (은 end-of-query symbol)
  • suggestion은 첫번째 유저 쿼리로 봤을 때 cleveland의 concept이 적절하기 때문에 contextual하다. 그래서 모델은 단지 최근의 쿼리에만 의존하지 않는다. 그리고 만들어진 쿼리는 training set에 있을 필요가 없기 때문에 synthetic하다.
  • count-based 모델과 달리 하나의 단어들, 쿼리, 순차적인 쿼리를 임베딩에 할당해 data sparsity를 피했다.
  • 우리 모델은 메모리를 많이 차지하지 않고 쿼리 세션에서 end-to-end로 학습될 수 있다.

2. Key Idea

  • suggestion 모델은 쿼리 사이의 근본적인 유사도를 알아내야 한다.
  • 해당 논문에서는 문법적인이고 의미적인 특성을 인코딩하는 임베딩을 이용해서 어떻게 쿼리의 유사도와 쿼리 term의 유사도를 알아내는지에 초점을 맞췄다.
  • 모델로 학습시킨 임베딩의 벡터들은 유사한 주제일 수록 가까이에 있었다.
  • 일반적으로 구절에 대한 벡터 표현은 단어들의 벡터를 평균내서 얻지만, 쿼리에서 단어의 순서는 중요하기 때문에 RNN을 이용했다.
  • RNN을 이용한 인코딩과 디코딩은 이전 쿼리에 대해 다음 쿼리를 예측하는데 쓰일 수 있다.

Imgur

모델은 연속적인 쿼리인 cleveland gallery와 lake erie art 사이의 mapping을 학습한다.

  • 테스트 시 유저의 쿼리는 인코딩 되고 가능성 있는 연속적인 단어로 디코딩 된다.
  • 비록 강력하지만…그런 mapping은 pairwise해서 쿼리의 context를 잃게 된다.
  • 쿼리의 예측을 조건화하기 위해 session-level RNN을 query-level RNN encoder에 추가했다.

The hierarchical recurrent encoder-decoder (HRED) for query suggestion

Imgur

  • query-level RNN은 쿼리를 인코딩하고, session-level RNN은 쿼리 인코딩을 인풋으로 받아 자신의 recurrent state를 업데이트한다.
  • session-level recurrent state는 과거 쿼리를 학습한 요약이다.
  • decoder RNN은 session-level recurrent state를 인풋으로 받아서 다음에 나올 쿼리를 contextual하게 만들어낸다.
  • query-level encoder RNN은 비슷한 쿼리를 임베딩 공간에서 비슷한 벡터로 mapping한다.
  • mapping은 쿼리에서 나오는 단어들이 model의 vocabulary에 나타나는 한, training data에서 보지 못했던 쿼리를 일반화한다. (training에 없던 것도 맞출 수 있게 해준다는 소리인 듯)
  • 이러한 방법은 모델이 드문 쿼리에 대해 단순히 동시에 발생했던 쿼리를 예측했던 걸 넘어서 더 유용하고 일반적인 formulation에 mapping하게 만들어준다.

3. Mathematical Framework

3.2 Architecture

  • hierarchical recurrent encoder-decoder는 위의 그림과 같다.
  • forward에서 query-level encodings, session-level recurrent states, 각각의 쿼리에서 log-likelihood를 계산한다.
  • backward에서는 gradients가 계산되고, parameter들이 업데이트된다.

3.2.1 Query-Level Encoding

  • training session S에 있는 각각의 쿼리 (은 쿼리의 순서, 은 쿼리의 길이)에 대해 query-level RNN은 쿼리의 단어를 순차적으로 읽고 hidden state를 GRU를 이용해 업데이트 한다.
  • 요약하자면, query-level RNN encoder는 쿼리를 고정된 길이의 벡터로 mapping한다.
  • parameter들은 공유되므로 recurrent state는 쿼리에 대해 general하고 contextual한 representation을 갖게 된다.

3.2.2 Session-Level Encoding

  • session-level RNN은 쿼리 representation의 sequence(query-level RNN의 가장 마지막에 있는 recurrent state)를 인풋으로 받아서 session-level recurrent states를 계산한다.
  • 역시 GRU를 사용한다.
  • session-level recurrent state 는 m번째까지의 쿼리에 대해 요약한다.
  • 은 이전 쿼리의 순서에 대해 민감하기 때문에 순서에 의존하는 reformulation을 인코딩한다.
  • 게다가 query vector를 인풋으로 받기 때문에 쿼리 내에 있는 단어의 순서에도 민감하다.

3.2.3 Next-Query Decoding

  • RNN decoder는 이 주어졌을 때 다음 쿼리을 예측한다.

  • 이전 쿼리에 대한 조건화는 RNN decoder의 recurrence를, 의 non-linear transformation을 통해 초기화함으로써 이루어진다.

*은 decoder의 초기 recurrent state

  • recurrence는 다음과 같은 form을 갖는다.
  • 는 decoder GRU, recurrent state 는 다음 단어 의 확률을 계산하는데 사용된다.
  • 다음 단어 에 대한 확률은 다음의 식으로 계산된다.

Imgur

  • 는 v의 embedding, 는 함수이다.
  • 은 parameter, 만약 가 vector 과 가까이 있다면 모델 내에서 은 높은 확률을 갖는다.

3.3 Learning

  • model의 parameter들은 encoder GRU, decoder GRU, session GRU 3개의 GRU의 parameter들로 구성되어있다.
  • output parameter들은 이다.
  • 위의 parameter들은 session S의 log-likelihood를 최대화하도록 학습된다.

Imgur

3.4 Generation and Rescoring

Generation

  • 유저가 쿼리를 순서대로 입력하면, 쿼리 suggestion은 쿼리 이다. 는 가능한 쿼리 공간

Imgur

Example

  • 유저가 cleveland gallery -> lake erie artist라는 쿼리를 입력했다고 해보자.
  • 쿼리 내에 있는 단어들은 GRU를 통해 query-level encoding이 된다. 따라서 쿼리 vector인 를 얻게 된다.
  • 그 다음, 쿼리 벡터에 GRU를 이용해 session-level recurrent state를 계산한다. 이를 통해, 두 개의 session-level recurrent state인 를 얻는다.
  • session-level recurrent state를 초기 decoder input으로 넣는다.(tanh 이용)
  • beam search 크기가 1이라고 가정하자.
  • 첫번째 단어인 이 나올 확률은 softmax를 이용해서 계산되는데, 이때 는 null vector이다. (논문에서 언급은 안했지만 b_0는 1로 초기화해서 를 거의 그대로 유지하는 것 같다.)
  • 가장 높은 확률을 가진 단어인 cleveland는 beam에 추가된다.
  • 그 다음 decoder recurrent state인 를 이용해 decoder GRU에 의해 계산된다.
  • 을 이용해 가장 가능성 있는 두번째 단어로 를 고를 수 있다.
  • 과정은 반복되고 모델은 art를 고르고 를 고를 것이다.
  • 즉, end-of-query symbol이 나오게 되면 user에게 cleveland indian art을 유저에게 보여주게 된다.

4. Experiments

4.1 Dataset

  • search log from AOL: 2006년 3월 1일 부터 5월 31일까지의 dataset. 657,426명의 개별 유저들에게서 입력된 16,946,938 개의 쿼리들.
  • background data: 2006년 3월 1일부터 5월 1일 이전까지의 쿼리. 모델과 baseline들을 평가하기 위해 만들었다.
  • training set: background data의 다음 두 주의 쿼리. ranking model을 튜닝하기 위해 만들었다.
  • validation set, test set: 나머지 두 주의 쿼리.

4.2 Model Training

  • background data에서 가장 빈번한 9만 개의 단어를 vocabulary V로 뒀다.
  • parameter 최적화는 mini-batch RMSPROP을 이용했다.
  • gradient의 norm이 1을 넘어가지 않도록 normalizing했다.
  • validation set의 likelihood가 5번이 지나도 오르지 않으면 학습을 그만시켰다.
  • Theano 사용.(2015년이라서 그런 듯)
  • query-level RNN dim: 1000, session-level RNN dim: 1500, output word embedding dim: 300

4.3 Learning to Rank

  • context(anchor) 이 주어졌을 때 target 쿼리 을 예측하는 게 목표이다.
  • 모델의 성능을 시험하기 위해 세 가지 다른 상황에서 다음 쿼리를 예측해봤다.
  • 첫번째는 context 쿼리가 background data에 있을때, 두번째는 context 쿼리가 흔한 쿼리들과 매우 유사할 때, 세번째는 background data에 없을 때이다.
  • 각각의 상황에서 20개의 후보를 골랐고, 후보한테는 true target labeling을 하고 나머지는 모두 관련없는 것으로 labeling을 했다.
  • (2015년 당시)최신 랭킹 알고리즘인 LambdaMART를 supervised 랭커로 선택했다. *LambdaMART는 Learning to Rank 알고리즘 중 하나이다. 아이템 리스트에서 랭킹 문제를 해결하는 알고리즘이다.

Pairwise and Suggestion Features

  • 각각의 후보 suggestion에 대해, 얼마나 많이 context 쿼리 뒤에 왔나를 셌다. 그리고 이 카운트를 feature로 더했다.
  • context 쿼리의 빈도도 사용했다.
  • 또한 context와 suggestion 사이의 Levenshtein 거리도 feature에 더했다.
  • suggestion feature는 suggestion의 길이와 background set에서의 빈도도 포함한다. *Levenshtein 거리는 두 문자열 간의 유사도의 측정 기준이 되는 거리이다. 원래 문자열 s와 타겟 문자열 t와의 거리는 s를 t로 바꾸는 데 필요한 삭제, 삽입, 대치의 횟수이다. ex) s=”test”, t=”tent” => LD(s,t) = 1

Contextual Features

  • suggestion과 context에서 가장 최근의 10개의 쿼리 사이의 character n-gram 유사도에 해당하는 10가지 feature를 더했다.(쿼리 하나당 1개씩 더한 듯)
  • suggestion과 context내에서 각각의 쿼리 사이의 평균 Levenshtein 거리도 더했다.
  • Query Variable Markov Model (QVMM)을 추가적인 feature로 사용해서 추정된 score를 사용했다. *character n-gram similarity는 두 문자열 사이의 유사도를 n-gram을 이용해 알아내는 방법이다.

*bi-gram일때,

*markov model은 stochastic한 모델이다. 미래의 상태는 이전에 발생한 사건이 아니라 오직 현재의 상태에만 의존한다고 가정한다.

HRED Score

  • 주어진 context에 대해서 suggestion의 log-likelihood에 해당하는 추가적인 feature를 추가하는데 사용됐다.

Result

  • HRED는 long-tail queries 즉, background set에서 본 적 없는 쿼리(빈도수가 많지 않은 쿼리)에 대해 많은 성능 향상을 보여줬다.

Reference