Thursday, July 12, 2012

Click Shaping to Optimize Multiple Objectives


Some properties have quite different business requirement other than purely CTR, because e.g. portals may serve as traffic direction to other properties. Therefore we usually have several metrics in mind. In this paper,  there are three objectives in discussion: total clicks, total time spent, average time spent. The first one may be seen as the traditional way, which optimizes the current page while the other two are metrics for downstream pages.

Therefore we have several ways of combining them:
  • linear combination, which may be seen as the linearization of the Pareto optimal
  • goal programming, which maximizes downstream metrics while put a linear constraints on CTR (no worse than a given value, obtained a priori)
  • localized multi-objective program, which maximizes the minimum ratio of downstream property loss (compared to CTR maximization scheme), subject to CTR constraints. This is convex but not differentiable. With some trick, it may be turned into a quasi-convex optimization problem and solved via be-section algorithm
  • a relaxed version of localized multi-objective program, which maximizes the downstream metric, subject to the CTR constraint and downstream constraint (no less than the original)
The experiments can only be carried out on segments of users and some of the down stream properties must be estimated a priori. The result shows a slightly sacrifice of CTR may lead to comparatively higher increase in downstream properties.