Summary

display 광고에서 conversion은 click을 하고 오랜 시간 이후 발생하는 경우(delayed feedback)가 종종 있는데, 이는 training 데이터 수집 기간에 실제로 이후에 conversion이 발생했음에도 아직 관측되지 않아서 negative sample로 잘못 레이블링되는 문제가 있다.
기존의 연구들은 데이터를 positie / unlabeled으로 구분했다. unlabeled가 실제로 이후에도 negative인지 확신할 수 없기 때문이다.
그런데 이 연구들은 positive 데이터가 positive class에서 random하게 선택된다고 가정한다. 즉, positive 데이터가 관측되지 않을 확률이 constant하다는 것인데, 실제로는 click이 된지 얼마 지나지 않은 데이터가 positive, 즉 conversion되지 않을 가능성이 훨씬 높다.
이 문제를 해결하기 위해 conversion delay을 모델링하는 추가적인 아키텍쳐를 제안한다.
delayed feedback 상황에서 unlabed 데이터에 대해 conversion인지 아닌지 판단할 때, conversion까지의 시간을 함께 고려한다. 즉, 두개의 parametric model을 가정하게 되는 것이다.
파라미터를 업데이트하기 위해 expectation maximization 방법론과 gradient descent 방법론을 제안한다.

Approach

Analogy to survival analysis

본 연구는 delayed feedback 문제를 해결하기 위해 click과 conversion까지의 시간을 모델링하는 방법을 제안한다. 이 모델은 survival time analysis와 밀접한 관련이 있다. 생존분석은 치료 시작부터 환자의 죽음까지의 시간을 모델링하는데, 종종 이 survival time은 censored 된다. 즉, 환자가 실험 도중에 실험에서 빠지거나 실험이 끝나고도 여전히 생존해있는 경우, 이 survival time을 관측할 수 없고 이를 censored time이라고 하는 것이다. delayed feedback도 이와 비슷한 상황인데, 아직 conversion (death)이 관측되지 않은 경우에 대해서는 delayed time (survival time)이 censored 된다. 적어도, delayed time이 elapsed time보다는 큼을 알 뿐이다.

그러나 생존 분석에서는 환자가 결국 사망하는데, delayed feedback 문제에서는 유저가 결국 conversion 하지 않을 수 있다. 이런 이유로 convert 여부를 예측하는 모델과 conversion할 경우, 그 delayed time을 예측하는 모델이 필요한 것이다. 이런 배경 때문에, 두 모델은 쉽게 떼어낼 수 없는 관계이다. 따라서 이 두 모델은 학습 과정에서 joint하게 훈련하는 것이 필요하다.

Notation

본격적으로 논의를 하기 이전에 노테이션을 정리해보자.

$X$: set of features
$Y \in \{ 0, 1 \}$: conversion이 이미 일어났는지 여부
$C \in \{ 0, 1 \}$: 유저가 마침내 conversion을 했는지 여부
$D$: click과 conversion 사이의 delay time. 만약에 $C=0$이라면 정의되지 않는다.
- $Y=1$인 경우에, $D$가 함께 관측된다.
- $Y=0$인 경우에, 만약 이 유저가 마침내 conversion 했다면, ($C=1$) 함께 관측되지 않는다. (unknown)
$E$: 클릭 이후의 elapsed time.

Relations between variables

위 그림을 살펴보자. display 광고 상황에서 클릭한 유저의 conversion label을 붙이기 위해 observation window만큼 유저를 기다린다. 이 기간 내에 유저가 conversion 했다면 1, 그렇지 않으면 0으로 기록된다. delayed feedback 문제는 0으로 기록된 유저가 observation window 이후에 conversion 하는 경우, training data에 bias가 생긴다는 것이다 (Fake Negative인 경우)

위 그림에서 positive인 경우를 살펴보자. 동그라미에서 노란색 네모까지의 시간을 elapsed time, 빨간색 세모까지의 시간을 delayed time으로 이해해보자. positive인 상황에서는 이미 conversion이 일어났기 때문에 $Y=1$이자, 이는 곧 $C=1$을 의미한다.

fake negative와 real negative을 살펴보자. 두 경우는 observation window 이내에 conversion이 발생하지 않았기 때문에 우선은 $Y=0$이다. 이후에 conversion 여부에 따라서 $C=0$이 될 수도, $C=1$이 될 수도 있다. $C=1$인 경우는, elapsed time (observation window)보다 delayed time이 더 길다. 이를 수식으로 나타내면 $D > E$이다. 정리해보면, $Y=0$인 경우에, $D > E$(conversion 발생)이거나 $C=0$(conversion 발생 x)이다.

여기서 도출할 수 있는 independence 가정은 $(C,D)$가 $X$ given 하에 $E$에 independent이라는 것이다.

잘 생각해보면, $(C,D)$는 유저가 최종적으로 conversion을 했는지에 dependent하다. 즉, $D$는 $C=0$이라면 정의되지 않고 $C=1$일 때만, conversion 시점에 따라서 정의된다. 따라서 elapsed time인 $E$와는 아무 관계가 없는 것이다.

Parametric model

위에서 정의한 확률변수 중에서 실제로 관측 가능한 변수는 $(X,Y,E)$이고, $Y=1$이라면 $D$도 함께 관측된다. 만약, $Y=0$이라면 아직 conversion이 발생하지 않은 상황이므로 $D$는 관측되지 않는다.

두개의 parametric model이 데이터세트 $(x_i, y_i, e_i)$을 피팅하기 위해 사용된다. conversion 확률을 모델링하기 위해서 $Pr(C | X)$가 사용되고 delayed time을 모델링하기 위해서 $Pr(D | X, C=1)$이 사용된다. 이 두 모델의 파라미터를 구하면, $Pr(C | X)$만 사용된다.

$Pr(C | X)$은 logistic regression model을 가정한다.

$Pr(D | X, C=1)$은 exponential distribution을 가정한다.

$\lambda(x)$는 생존분석에서 hazard function이라고 불리며 $\lambda(x) > 0$을 보장하기 위해 $\lambda(x) = exp(w_d \cdot x)$을 사용한다. 따라서 weight vectors은 $w_c,w_d$이다.

Objective function

파라미터를 추정하기 위해 likelihood을 세운다.

\[ L( w_c, w_d ) = \log \prod_i P(Y=1, D=d_i | X=x_i, E=e_i)^{y_i} P(Y=0 | X=x_i, E=e_i)^{1-y_i} \]

잘 생각해보면, 관측되는 데이터는 $(y_i, x_i, e_i)$이고 $y_i=1$인 경우에 $d_i$도 함께 관측된다. parametric model은 $C$에 대해서 세웠지만 해당 값은 결측치 (missing value)이므로 관측된 데이터 기준으로 likelihood을 세우는 것이다.

$ \begin{align*} L( w_c, w_d ) &= \sum_{i, y_i=1} \log P(Y=1, D=d_i | X=x_i, E=e_i) + \sum_{i, y_i=0} \log P(Y=0 | X=x_i, E=e_i) \end{align*} $

각 확률 term을 parameter에 대한 식으로 전개해보자.

Probability of observing conversion

짚고 넘어갈 점은 conversion에 대한 확률이 아니라 conversion을 관측할 확률이다. conversion 확률은 delayed conversion까지 포함하고 conversion을 관측할 확률은 delayed conversion이 아닌, $Y=1$인 확률이다. 이를 전개해보자.

중간에 $Y=1 \rightarrow C=1$인 관계와 conditional independence 관계가 쓰였다.

Probability of not observing conversion

마찬가지로, 최종적으로 conversion을 하지 않을 확률이 아니라 conversion을 관측하지 않을 확률이다. 즉, $Y=0$인 확률인데, 이는 곧 $Y=0$인데 최종적으로 $C=1$인 delayed feedback 확률과 평생 conversion하지 않는 경우인 $D>E$으로 나뉜다. 이를 전개해보자.

최종 likelihood는 아래와 같이 정리할 수 있다.

likelihood가 나왔고 파라미터를 정의하였으니, 이제 gradient descent을 통해 파라미터를 업데이트하면 된다. 파라미터는 $w_c, w_d$이므로 이에대한 gradient을 구하면 아래와 같다.

Effect of unlabled sample

데이터를 관측할 때, unlabled sample인 $y_i=0$의 영향력은 $w_c$의 gradient에 얼마만큼의 contribution을 하는지 살펴보면 쉽게 알 수 있다.

$\lambda(x_i) e_i << 1$인 경우를 생각해보자. delayed time은 exponential distribution으로 가정했고 평균은 $1/\lambda(x)$이다. $\lambda(x_i) e_i << 1 \Longleftrightarrow e_i << 1/\lambda(x_i) $ 이므로 elapsed time이 평균 delayed time보다 훨씬 작다는 것이다. 즉, 데이터를 관측할 때 click 이후의 elapsed time이 너무 작기 때문에 이 유저가 최정적으로 conversion하는지 판단하기에는 애매할 수 있다. 따라서 이 경우에는 $w_c$에 대한 gradient에 contribution이 적다. $\exp ( - \lambda(x_i) e_i)$이 1에 가까워지고 분자가 0에 가까워지기 때문에 $\lambda(x_i) e_i << 1$인 경우 gradient contribution이 적어지는 것이다.

$\lambda(x_i) e_i >> 1$인 경우는 반대로 생각하면 된다. elapsed time이 평균 delayed time보다 훨씬 큰 경우이다. 애초에 이 경우는 최종적으로 conversion이 발생하지 않을 조건과 동일하다. ($D < E$) $\lambda(x_i) e_i >> 1$인 경우, $\exp ( - \lambda(x_i) e_i)$이 0애 가까워지고 gradient contribution은 $1/(1 - p(x_i))$가 된다. 이는 곧, logistic regression의 negative sample의 gradient이므로 의미적으로 negative 가능성을 추가하는 것이다.

Conclusion

delayed feedback modeling의 개념을 거의 처음 제시한 논문을 살펴보았다.
elapsed time, delayed time의 개념이 생존분석에서 유래되었으나 환자가 결국 사망하는 것을 가정하는 생존분석과는 달리 conversion이 발생하지 않을 수도 있는 delayed feedback model의 특징을 살펴보았다.
conversion 여부는 관측되지 않으므로 당장은 관측된 conversion 기준으로 likelihood을 세운다는 점이 하나의 포인트가 될 것 같다.
$Y$ 기준으로 likelihood을 세웠으나 likelihood가 $C, D$ 모델의 파라미터로 표현되어 결국 gradient descent을 하면 conversion model을 구하게 되는 과정이 흥미로웠다.
나중에 시간이 된다면 EM 알고리즘을 더 이해해봐야겠다. (이해하려다가 실패했다..)
시간을 내서 코드로 구현해보자!