Multi-objective Optimization for Guaranteed Delivery in Video Service Platform

By Hang Lei, Yin Zhao, Longjun Cai

This article is based on the paper accepted by KDD 2020 of the same title

Guaranteed-Delivery (GD) is one of the important display strategies for the IP videos in video service platform. Different from the traditional recommendation strategy, GD requires the delivery system to guarantee the exposure amount (also called impressions in some works) for the content, where the amount generally comes from the purchase contract or business consideration of the platform.

In our latest paper, we study the problem of how to maximize certain gains, such as video view (VV) or fairness of different contents (CTR variations between contents) under the GD constraints. We formulate such a problem as a constrained non-linear programming problem, in which the objectives are to maximize the total VVs of contents and the exposure fairness between contents. In order to capture the trends of VV versus the impression number (page views, PV) for each video content, we propose a parameterized ordinary differential equation (ODE) model, and the parameters of the ODE are fitted by the video historical PV and CLICK data.

Challenges Faced by Video Service Platforms

To solve this issue, an effective impression resource allocation system which plans the impression resources in a certain period before every operation period is essential. Generally, the operation period can be one day or every several hours, which depends on the specific requirement. Impression resource is first planned for each content at the be- ginning of the period considering all the requirements, then the dispatching system (typically the recommendation system) will take the impression amount allocated for each content as reference and try to find the most suitable users. Thus the whole system can balance both the business requirements and users’ personal requirement.

However, the impression allocation before each operation period is complicated because of many constraints involved. Currently, the impression system is operated manually, which highly depends on the experience of human, and thus is definitely sub-optimal. On the one hand, the actual impression delivered for a video content in the widget mostly is determined by its click-through rate (CTR) empirically, but manual allocation strategy cannot precisely predict the contents’ CLICK under a given impression. On the other hand, it is even hard for humans to design an allocation strategy that can also achieve high click number, fairness (which is a common object for this scenario) without violating all the constraints for each video.

A typical scenario is that different video contents behave differently in terms of page views (PV) and video views (VV) because of the differences of content properties. Some video contents might achieve high clicks using less impressions while the others might consume more. If we assign too many impressions to these con- tents, the overall CTR might be at a lower level. Although several impression allocating algorithms for ads (also called guaranteed delivery algorithm) have been proposed, to the authors’ knowledge, there is no existing algorithm proposed for contents’ impression allocating problem.

Our Proposed Solution

In this paper, to address the above challenges, we design a two- stage framework. The first stage is forecasting, and the second is allocating. In the forecasting stage, we seek to develop effective predictive model with the goal of forecasting click behavior of users on each content given their daily historical PV and CLICK records. Specifically, to describe CTR trends with respect to PV, a prediction model (called PV-click-CTR model or P2C) based on ordinal differential equation (ODE) is proposed. And then in the allocating stage, we provide a multiple objective nonlinear programming (NLP) model subject to the CTR trends and other constraints. Accordingly, to solve the NLP with ODE involved, a GA allocating algorithm is developed.

Combining CLICK forecasting model and allocating model provides us with a solution to handle content Guaranteed-Delivery (GD) problem. We carried out extensive offline and online experiments, which show the superior of proposed solution, on both model performance and system efficiency. To the best of our knowledge, this is one of the first industrial solutions that are capable of handling content Guaranteed-Delivery (GD) problem. It should be admitted that there are many other related factors, such as the location impact of impression within the widget, the performance of recommendation system for each content, etc. Currently we do not consider those factors since they will make the problem further intractable and leave them as future work.

The main contributions of our work can be summarized as follows:

  • We propose a parameterized PV-click-CTR (P2C) prediction model to describing the CTR trends with PV.
  • We design a framework that can maximizes certain objectives, such as the VV of contents, fairness for each content, under the Guaranteed-Delivery (GD) constraints considering the CTR trends of each video content and impression resource limitation.
  • Comprehensive offline and online experiments are conducted to verify the effectiveness of the proposed PV-click-CTR model as well as Guaranteed-Delivery strategy.

Detailed Analysis of the P2C Model

According to equation (2), the ordinary differential equation model where click increases with PV can be obtained.

By integrating the two ends after separating the variables in equation (3), you can get

Where x0 and y0 are the initial PV and click, respectively.

Based on the P2C model established above, the task of this section is to give an approximate optimal exposure for each content under the circumstances that the exposure resources of each scene and drawer are limited.

First, based on the ordinary differential equation (ODE) model predicted by PV-click-CTR, for each content in the content pool, the least squares are used to fit two parameters in the ODE: click saturation value ym and click with the inherent growth rate of PV r. Thus, the PV-click function relationship of each content is given.

Second, based on the given optimization goals and constraints, a multi-objective nonlinear optimization model of PV distribution can be established.

The optimization goals of the above model include two: maximizing vv in multiple scenes and minimizing the variance of the content CTR in the content pool. It should be noted that the minimum CTR variance here is a formal description of exposure fairness to balance “overexposure” and “underexposure”. The constraints represent the exposure PV constraints of the scene, drawer, pit, and content, respectively. Because we use numerical methods to solve the objective function, the above optimization model cannot be solved using traditional gradient-based algorithms. The evolutionary algorithm provides a solution. Here, the genetic algorithm (GA) is selected to solve. It should be noted that the P2C model is used in the calculation of the fitness value function in GA.

Four Key Experimental Results

In the online experiment part, we established a bucket experiment. The benchmark bucket adopts manual strategy to maintain the quantity; the experiment bucket adopts the strategy proposed in this article. During the experiment, we pay attention to and compare the daily delivery effect of the benchmark bucket and the experimental bucket (CTR variance, overall CTR of the strategy on the scene, etc.). The following is the data of the 30-day and 7-week holding effect. Compared with the results of the manual strategy, it is found that the holding strategy has different degrees of improvement in the CTR variance and the overall CTR of the scene. In particular, in terms of CTR variance, the effect of the hedging strategy is very obvious, with an average relative increase of +50%.

Conclusion

Both the detailed and overall results show that the GD model for contents proposed in this paper can help us to make more informed and effective decisions in practical content GD system, which is superior to the current practical solutions.

References

The views expressed herein are for reference only and don’t necessarily represent the official views of Alibaba Cloud.

Original Source:

Follow me to keep abreast with the latest technology news, industry insights, and developer trends.