[Ads ML / Paper review] An Efficient Deep Distribution Network for Bid Shading in First-Price Auctions

• 논문 링크 (2021년)

Summary

Yahoo, Verizon Media에서 공동으로 연구한 논문이다. 흥미로운 것이, Yahoo는 non-censored에서의 문제를, Verizon Media는 censored에서의 문제를 풀고자 했는데 이 둘이 공동 연구하여, non-censored, censored 모두에서 작동하는 알고리즘을 제안한다는 것이다. 

Main Idea

notation을 정리해보자.

surplus는 아래와 같이 정의된다.

Verizon Media가 좋아하는 방식인 two step으로 surplus을 최대화하는 입찰가를 찾는다. 첫번째는 pdf 또는 cdf 모델링이다. 두번째는 모델링된 분포를 바탕으로 surplus을 최대화하는 입찰가를 찾는다.

이 식은 사실 새로울 것이 없다. Verizon Media에서 이전에 발표한 논문에서도 이미 나왔던 문제 정의이다.

https://steady-programming.tistory.com/109

[Ads ML / Paper review] Bid Shading by Win-Rate Estimation and Surplus Maximization

 

이전 연구에서는 $\hat{b}$에 대한 분포를 직접적으로 가정하지 않고 cdf의 확률을 FM + logistic function으로 추정했다. 이 논문에서는 직접적인 분포를 가정한다.

 

먼저, minimum winning price가 제공되는 경우, 즉 uncensored auction 상황을 생각해보자. 분포를 가정하고, $y$가 주어지므로 MLE을 통해서 분포의 파라미터를 추정할 수 있다.

여기서 $\alpha$가 분포의 파라미터인데, 재미있는 것은 이 파라미터가 bid request 피쳐의 함수라는 것이다. 즉, 일반적인 MLE 처럼 파라미터를 어느것에도 의존하지 않는 형태로 가정하지 않는다. 입력은 bid request 피쳐, output은 파라미터가 된다. 이 관계를 매핑하기 위해 딥러닝을 사용한다. 여기서 논문의 제목, Deep Distribution Network 라는 이름이 유래된다.

minimum winning price가 제공되지 않는 경우, 즉 censored auction인 상황을 생각해보자. 이때는 MLE를 사용하여 파라미터를 추정할 수 없다. 따라서 이전에 Verizon Media에서 발표한 방법을 차용하여 CDF의 확률을 추정한다. 입찰에서 이겼냐, 졌냐로 1/0을 정의하고 cross entropy loss을 최소화하는 방향으로 파라미터를 업데이트 한다. 중요한 점은, 이때도 분포의 파라미터를 추정한다는 점이다.

똑같이 파라미터 $\alpha$는 bid request 피쳐의 함수이다. 이 함수는 Deep Neural Network로 정의된다. 다만, 이 파라미터를 업데이트할 때, log likelihood을 최대화할 수 없으니, binary cross entroy loss을 최소화하는 방향을 선택한다. 따라서 censored auction인 경우에도 분포를 가정하고 그 파라미터를 간접적으로 추정하는 것으로 이해하자.

 

이제 cdf 확률을 계산할 수 있으니 surplus을 최대화하는 문제로 넘어가보자.

censored auction 이든, uncensored auction 이든, 위의 방법을 통해서 가정한 분포의 파라미터를 추정했다면 cdf 확률을 구할 수 있다. 논문에서는 truncated-normal, exponential, gamma, log-normal 분포의 cdf를 위의 식에 넣고 식을 전개하여, 특정 구간에 unique local extrema가 있음을 증명한다. 자세한 증명은 논문을 참고하자. 

따라서 그 unique한 포인트가 바로 surplus을 최대화하는 최적의 입찰 가격인 것이다. 이 최적의 값을 golden section search을 통해서 찾는다.

Some Thoughts

외부 ssp에 의해 일부만 winning price가 주어지는 경우는 어떻게 해야하는가? censored auction loss, uncensored auction loss을 둘다 사용해야할 것 같은데 censored auction loss의 수가 더 많을 것이므로 weight을 적절하게 조절해야할 것 같다.

또한 분포 가정에 의존적이라는 것이 단점이다. 입찰 가격이 실제로 log-normal에 가까운지 살펴봐야한다. 사실 long tail인 경우가 많아서 log-normal로 가정해도 크게 무리가 없을 것 같긴하다. 다만, 봉우리가 여러개일 수도 있고 따라서 non-parametric으로 접근해야할 수도 있다. 분포 가정이 깨지면 golden section search도 사용하지 못하므로 여러가지 생각해야할 포인트가 있다.