Delayed Feedback Model

Modeling Delayed Feedback in Display Advertising 논문을 읽고 내용을 정리한다.

논문에서 풀고자 하는 문제

Click 이후에 발생하는 Conversion Rate의 추정

• cost-per-conversion(CPA) payment model에서 ad-exchange나 DSP는 impression의 가치를 추정해야한다.
• impression의 가치인 eCPM(expected Cost Per Mile)은 다음과 같이 계산된다.
  @@
  \begin{align}
  eCPM & = CPA \times Pr(conversion, click) \\
  & = CPA \times Pr(click) \times Pr(Conversion | click)
  \end{align}
  @@
• 문제는 Click 이후에 실제 Conversion은 오랜 시간이 지난 후 발생할 수 있다는 점이다. (사실, 모든 케이스를 끝까지 다 관찰하는 것은 근본적으로 불가능하기도 하다) 이 때문에 Conversion을 판정하는 matching window가 너무 짧을 경우에는 negative sample로 잘못 레이블링되는 샘플들이 다수 발생하게 된다.
  이러한, ‘delayed feedback’ 문제를 해결하는 방법을 이 논문에서 제안한다.

접근법

positive data와 unlabeled data로 부터 모형을 학습

• 이 논문에서는 matching window를 사용하여 positive/negative data로 나누는 방법을 사용하지 않는다. matching window를 사용하면 너무 짧을 경우 방법은 잘못 레이블링된 negative data를 발생하며, 너무 길 경우에는 최신 데이터를 반영하지 못하는 딜레마가 있다.
• 대신에 positive와 unlabeled data(미래에 conversion이 될 수 있는 데이터)로 구분하는 접근법을 취한다.

positive data와 unlabeled data로 부터 모형을 학습하는 기존 연구와의 비교

• 궁극적으로 예측하고자 하는 변수를 @C@라고 하자. 그런데 이 @C@는 전기간에 걸쳐서 발생하는 Conversion을 말하므로 근본적으로 관측 자체가 어려운 변수이다.
• 대신에 우리는 Click 발생 시점으로 부터 현시점까지의 소요 시간 내에 Conversion 발생 여부 @Y@는 알 수 있다.
• 이 @Y@ 변수는 위에서 언급한 positive data와 unlabeled data가 된다.
• positive data와 unlabeled data로 부터 학습하는 것에 관한 기존 연구들은 missing at random(레이블링이 되거나/안되는 것이 랜덤하다)을 가정하는 접근법을 취한다. 이렇게 하면 이 가정으로 부터 @p(y=1|x)@와 @p(s=1|x)@가 상수배만큼 차이가 난다는 것을 보일 수 있으며, 이 사실로 인해 관측된 변수로부터 잠재변수의 클래스의 확률 모델링이 가능하게 된다.
• 그런데, Conversion을 예측하는 문제에서는 missing at random이 아니라는 점이 문제이다. click 이후 소요시간이 짧을 수록 충분히 관측하지 않았기 때문에 궁극적으로는 positive 샘플로 전환 될 수 있는 케이스라도 레이블이 안붙게 되는 비율이 많아지기 때문이다. 따라서 기존 연구들의 방법론을 그대로 적용하기 어렵고 새로운 방안을 고려해야한다.

Click과 Conversion간의 expected dealy를 설명하는 delayed feedback 모델 도입

• 앞서 언급했듯 우리가 알 수 있는 것은 @Y@이며, @Y@의 확률분포를 기반으로한 likelihood로부터 @C@의 확률모델의 parameter를 추정해야 한다.
• likelihood를 construct하기 위해서는 unlabeled data(@Y=0@인 케이스)의 경우의 수를 나누어 접근해야 한다.
• unlabeled data인 경우 정말로 전환이 안되거나 delay time이 elapsed time보다 큰 경우일 수 있으며, 이 경우의 수의 확률을 모델링 하기 위해서 delay time에 대한 확률 모델이 필요하다.
• 논문에서는 Survival Analysis의 개념을 응용하여 delay time을 모델링하였다.
• Survival analysis는 censored data를 가지고 환자의 수명의 분포를 추정하는 기법이다. Conversion data 또한 censored data이며, conversion까지 걸리는 시간이 delay라는 점에서 유사한 문제로 볼 수있다.
• 그러나, 한가지 차이점은 survival analysis에서는 환자의 사망은 언젠가는 발생하지만 Conversion은 끝끝내 발생하지 않을 수 있다는 점이다.
• 따라서, conversion의 확률 모델과 delay의 확률 모델을 동시에 학습해야 한다.

MODEL

문제를 formalize하기 위해 아래 확률변수의 정의를 짚어본다.

• @X@ : a set of features
• @Y \in {0,1}@ : 클릭 이후 현 시점까지 conversion의 발생 여부
• @C \in {0,1}@ : 전기간에 걸친 Conversion 여부
• @D@ : click과 conversion 사이의 delay (@C = 0@이면 @D@는 정의되지 않음)
• @E@ : click 이후 소요 시간

main relation between theses variables : 이 relation으로 인해서 likelihood를 구할때 @Y=0@인 경우 @C@의 값에 따라 decompose되며 @C=1@인경우 @E@의 확률분포를 사용하게 된다.
@@
Y=0 \Leftrightarrow C=0 \ or \ E<D , \\\
Y=1 \Rightarrow C=1
@@

독립성 가정 (conditional independence)
@@
Pr(C,D|X,E) = Pr(C,D|X)
@@

Two parametric model (두 모델 모두 GLM)

• Conversion Model
  @@
  Pr(C=1|X=x) = p(x) \ with \ p(x) = 1 / {1+\exp(-w_c \cdot x)}
  @@
• Delay Model
  @@
  Pr(D=d|X=x,C=1) = \lambda(x)\exp(-\lambda(x) \cdot d)
  @@
  이 때, @\lambda(x)@는 hazard function이며, @\lambda(x) > 0@을 만족하기 위해 @\lambda(x) = \exp(w_d \cdot x)@라고 한다.

OPTIMIZATION

논문에서는 regularized Negative log-likelihood를 최소화하는 parameter를 Gradient Descent 방법으로 optimization하였다.
이를 위해 먼저 Likelihood를 정의한다.

• Likelihood
  @@
  Likelihood = Pr(Y=1, D=d | X=x, E=e) + Pr(Y=0 | X=x, E=e)
  @@
  이 때 우측 항은 아래와 같이 정리된다.
  @@
  \begin{align}
  \require{cancel}
  Pr(Y=1, D=d \ | \ X=x, E=e) & = Pr(C=1, D=d \ | \ X=x, E=e) \\
  & = Pr(C=1, D=d \ | \ X=x) \\
  & = Pr(D=d \ | \ X=x, C=1) \times Pr(C=1 \ | \ X=x) \\
  & = \lambda \exp(-\lambda(x) \cdot d) \cdot p(x)
  \end{align}
  @@
  @@
  \begin{align}
  Pr(Y=0 \ | \ X=x, E=e) & = Pr(Y=0 \ | \ C=0, X=x, E=e) \times Pr(C=0 \ | \ X=x, \cancel{E=e}) \\
  & + Pr(Y=0 \ | \ C=1, X=x, E=e) \times Pr(C=1 \ | \ X=x, \cancel{E=e}) \\
  & = 1 - p(x) + p(x) \cdot \exp(-\lambda(x) \cdot e) \\
  \end{align}
  @@
  @@
  \begin{align}
  Because, \ \ Pr(Y=0 \ | \ C=0, X=x, E=e) & = 1 \\
  Pr(Y=1 \ | \ C=1, X=x, E=e) & = Pr(D>E \ | \ C=1, X=x, E=c) \\
  & = \int_{e_i}^{\infty}\lambda(x)\exp(-\lambda(x)t)dt \\
  & = \exp(-\lambda(x)e_i)
  \end{align}
  @@

위 식으로 부터 negative likelihood는 다음과 같이 도출할 수 있다.

• negative likelihood
  @@
  L(W_C, W_d) \ = \ \sum_{i, y_i = 1} (\log\lambda(x_i) + \lambda(x_i)d_i - \log p(x_i)) \ - \ \sum_{i, y_i = 0} log[1-p(x_i)+p(x_i)\exp(-\lambda(x_i)e_i)]
  @@

여기까지 정의되면 Optimization 문제는 아래와 같이 표현된다.
@@
argmin_{W_c, W_d} L(W_c, W_d) + \frac{\mu}{2}(\Vert W_c \Vert_2 + \Vert W_d \Vert_2) \tag{1}
@@

식 @(1)@은 제약조건이 없고 2차 미분이 가능한 형태로 gradient-based optimization 테크닉으로 풀 수 있다. 논문에서는 L-BFGS를 사용하였다고 한다.

추가적으로 @L(W_c, W_d)@의 gradient를 살펴보면 unlabeled data가 optimization 과정에서 모델에 어떠한 영향을 주는지 직관적으로 이해할 수 있다.

• gradient of Negative Likelihood
  @@
  \begin{align}
  \frac{\partial L(W_c, W_d)}{\partial W_c} & = \sum_{i, yi = 1} \frac{1}{p(x_i)} \cdot \frac{\partial p(x_i)}{\partial W_c} - \ \sum_{i, y=0} \frac{\partial p(x_i)}{\partial W_c} \cdot \frac{1-\exp(-\lambda(x_i)e_i)}{1-p(x_i)+p(x_i)exp(-\lambda(x_i)e_i} \\
  \frac{\partial L(W_c, W_d)}{\partial W_d} & = -\sum_{i, y_i=1} \frac{\partial\lambda(x_i)}{\partial W_d}\cdot \left(\frac{1}{\lambda(x_i)} + d_i\right) +\sum_{i, y_i=0}\left(\frac{p(x_i)exp(-\lambda(x_i)e_i)}{1-p(x_i)+p(x_i)exp(-\lambda(x_i)e_i} \cdot \frac{\partial \lambda(x_i)}{\partial W_d} \right)
  \end{align}
  @@

기타

Experimental result

• 아래 5개 모델과 Negative Likelihood를 비교한 결과 Delayed feedback model이 Negative log-likelihood가 Oracle에 더 가까웠으며, 특히 최근 테스트 셋을 최근 데이터 셋으로 사용하였을 때 더 성능이 좋음을 확인

  • Short Term Conversion model (STC)
  • Naive
  • Oracle
  • Shifted
  • Rescale

• 새로운 캠페인에 대해 Naive 방법론과 비교한 결과 delayed feedback model이 더 빠르게 Conversion rate를 근접하게 맞춰가는 것을 확인

• delay를 Exponential dist로 모델링하는 것이 적합한지 판단하기 위해서 campaign을 condition으로 하여 conditional distribution을 살펴봄

  • 실제 delay의 그래프가 fitted exponential distribution에 가까운 것을 확인하였으며,
  • 짧은 delay는 과소추정하고 긴 딜레이는 과대추정하는 경향성이 있음을 확인함

​