优酷多目标保量模型

Reading time ~2 minutes

youku在《Multi-objective Optimization for Guaranteed Delivery in Video Service Platform》提出了一种方法:

1.介绍

2.相关工作

3.内容的曝光分配模型

在本节中,首先给出内容的保量分发策略的一些概念:

3.1 前提

我们只考虑需要GD策略的抽屉或者模块(drawers),它被表示为:

\[S = \lbrace s_j, j \in Z_n \rbrace\]

其中:

  • \(Z_n\)表示从1到n的整数集合

在drawer \(s_j\)的位置集合被表示为:

\[D_{s_j}=\lbrace d_{jk}, j \in Z_n, k \in Z_{\Theta(s_j)}\rbrace\]

其中:

  • \(\Theta_{s_j}\)表示在drawer \(s_j\)的位置数目

假设需要考虑在这些drawer的内容集合被表示为:

\[Q=\lbrace q_i, i \in Z_m \rbrace\]

其中:m是内容数目

在每个位置\(d_{jk}\)的整体天级PV限制被表示为\(C(d_{jk})\)。不失一般性,后面章节,我们将PV value表示为x,将CLICK value表示为y

考虑到每个drawer和position的资源容量(resource capacity),以及每个内容的CTR趋势,我们的目标是:为每个内容发现合适的天级PV,它可以最大化整个频道的VV,同时尽可能避免”过曝光(over-exposure)”和“欠曝光(under-exposure)”。因此,GD策略的主要问题是:给定一个内容的PV value x,我们估计它的click value值y。正式的,点击预估模型是一个”mapping”函数,它可以根据历史天级PV和CLICK数据来学到相应的patterns,并能预测一天的click value。

3.2 pv-click-ctr预估模型

每个内容的CTR趋势(trend)涉及到许多因素,很难对这些因素枚举并基于它的历史数据进行模型构建。因而,我们从其它视角对该问题进行研究。

总的来说,点击来自于曝光。在大多数case下,越多的曝光会带来越多点击数。然而,每个内容的目标消费者的总数目是有限的。当曝光量过大时,对同一消费者进行重复曝光在统计上不能带来更多的点击。这种“饱和”现象可以在我们的产品中通过历史数据观察到,这与经济学系统中的人口模型相似。受[13]的启发,我们引入一个参数化模型(parametric model)来捕获以上的观点。

特别的,假设:

  • y(x)表示点击值,它与在一天内某一内容的一个PV value x一一对应
  • \(\Delta x\)是PV增量
  • \(\Delta y\)是对应于\(\Delta x\)的点击增量
  • r是相对增长率系数。不同内容的相对增长率是不同的,因为它主要依赖于内容质量

如果PV值x很小,我们可以将CLICK增长率看成是与PV成比例关系,因为越多的曝光通常会带来越多的点击:

\[\frac{y(x+\Delta x) - y(x)}{\Delta x} \approx r * y(x)\]

…(1)

然而,当PV value x很大时,点击会具有“饱和”效应,增长率会递减。正式的,它可以写成:

\[\frac{y(x+\Delta x) - y(x)}{\Delta x} < 0\]

…(2)

与paper[13]相类比,我们使用一个关于y(x)的线性递减函数,来描述“饱和”效应,例如:

\[\frac{y(x+\Delta x) - y(x)}{\Delta x} = r(1 - \frac{y(x)}{y_m}) y(x)\]

…(3)

其中,\(y_m\)被称为中心点击值(pivot CLICK value)。当PV超过对应于\(y_m\)的PV量时,相对增长率会为负,例如:如果\(y(x) > y_m, 1-\frac{y(x)}{y_m} < 0\)。其中,r和pivot CLICK \(y_m\)是核心content-based参数,表示内容的属性。

假设:\(\Delta x \rightarrow 0\),那么等式(3)将是一个在CLICK和PV值间的ODE常微分方程模型:

\[\frac{dy}{dx} = r ( 1 - \frac{y}{y_m}) y\]

…(4)

等式(4)的解为:

\[y = \frac{y_m y_0}{y_0 - (y_0 - y_m) e^{-r(x - x_0)}}\]

…(5)

其中:

  • \(x_0\)和\(y_0\)表示初始PV和初始CLICK。

如果\(y_0 < y_m\),CLICK value会增长,随着\(x \rightarrow \infty\)时会渐近逼近\(y_m\);如果\(y_0 > y_m\),CLICK value会递减;随着\(x \rightarrow \infty\)会远离\(y_m\),事实上\(y = y_m\)是等式(4)的等价。因而,\(y = y_m\)的均衡点(equilibrium)。因而,等式(4)的正均衡点\(y=y_m\)是全局稳定的,也就是说,对等式(4)的y(x)求解\(\lim_{n \rightarrow \infty} y(x) = y(m)\),其中任意初始值\(x_0\)。

为了描述每个视频内容的CTR趋势,在等式(5)中的参数r和\(y_m\)需要通过历史PV和CLICK数据进行填充。我们将所有内容相关的因子归属为这些参数,期望它们来表示内容自己的CTR趋势。我们使用least square fitting方法来估计这些参数。

3.3 曝光分配公式

基于3.2节提出的pv-click-ctr预估模型,该子部分目标是,开发一个最优化程序模型来解决PV分配问题。假设:

  • \(x_{ijk}\)表示内容\(q_i\)从位置\(d_{jk}\)获得的PV value
  • \(f(x_{ijk})\)是对应于\(x_{ijk}\)对应的CLICK value,它可以使用等式(5)进行计算

我们的目标是:最大化总视频观看数(video views: VV),并通过最优化\(x_{ijk}\)来最小化CTR variance。通过分析最优化目标和约束,分配问题可以被定义如下:

\[max \sum\limits_{i=1}^m \sum\limits_{j=1}^n r_{ij} f(x_{ijk}), k \in Z_{\Theta(s_j)} \\ min \frac{\sum\limits_{i=1}^m (p_i - P)^2}{m - 1} \\ p_i = \frac{\sum_{j=1}^n f(x_{ijk})}{\sum_{j=1}^n x_{ijk}}, \forall i \in \lbrace 1, 2, \cdots, m \rbrace, \forall k \in Z_{\Theta(s_j)} \\ P = \frac{\sum\limits_{i=1}^m \sum\limits_{j=1}^n f(x_{ijk})}{\sum\limits_{i=1}^m \sum_{j=1}^n x_{ijk}}, \forall k \in Z_{\Theta(s_j)}\]

….(6)(7)(8)(9)

约束条件为:

s.t.

\[\sum\limits_{i=1}^m x_{ijk} < C(s_j), \forall j \in \lbrace 1, 2, \cdots, n \rbrace, \forall k \in Z_{\Theta(s_j)}\]

…(10)

\[\sum\limits_{i=1}^m \sum_{j=1}^n x_{ijk} < R, \forall k \in Z_{\Theta(s_j)}\]

…(11)

\[x_{ijk} < max \lbrace C(d_{jl}), l \in Z_{\Theta(s_j)} \rbrace, \\ \forall i \in \lbrace 1,2, \cdots, m\rbrace, \forall j \in \lbrace 1,2, \cdots, n\rbrace, \forall k \in Z_{\Theta(s_j)}\]

…(12)

\[|C_{jk}| \leq k, C_{jk} = \lbrace x_{ijk} | x_{ijk} \geq C(d_{jk}), 1 \leq i \leq m \rbrace, \\ \forall j \in \lbrace 1, 2, \cdots, n \rbrace, \forall k \in Z_{\Theta(s_j)}\]

…(13)

其中:

  • \(r_{ij}\):是对于内容\(q_i\)在drawer \(s_j\)中CLICK和VV间的正相关系数
  • \(C(s_j)\):是drawer \(s_j\)的总PV资源数
  • R:是drawer set S的总可供资源数

等式(6)的最优化目标是在所有drawers上最大化总VVs。其它最优化目标是,在最小化等式(7)-(9)描述的的不同内容间的CTR variance。

  • 等式(10)描述的约束意味着:内容集合Q在drawer \(s_j\)中的资源分配不能超过它的资源容量(capacity)
  • 等式(11)表示drawer set S的资源约束
  • 等式(12)是位置资源约束,它表示资源分配给在任意drawer中的一个内容,不能超过它的最大位置资源容量
  • 等式(13)可以确保它们必须是一个drawer的一且只有一个位置分配给一个内容,也就是说:我们不能在相同时间展示相同内容给用户。

4.GA-based内容分配算法

为了获得在第3节中建模的分配问题的最优或次优解,提出了一个遗传算法(Genetic Algorithm)GA分配算法,它是一个迭代算法,其中会嵌入pv-click-ctr预测模型。

注意,等式(6)-(13)中表示的PV分配问题,对应于一个多目标约束优化问题(MCOP: Multi-objective Constrained Optimization Problem),它的最优解是很难找出的。通常,一个MCOP可以通过加权法( weighting)被转化成一个单目标最优化问题,接着PV分配问题定义如下:

\[max \ g(X | \lambda) = \sum\limits_{i=1}^m \sum\limits_{j=1}^n r_{ij} f(x_{ij}) + \lambda \frac{1} {\frac{\sum\limits_{i=1}^m (p_i - P)^2}{m-1}} \\ p_i = \frac{\sum\limits_{j=1}^n f(x_{ij})}{\sum\limits_{j=1}^n x_{ij}}, \forall i \in \lbrace 1,2, \cdots, m \rbrace \\ P = \frac{\sum\limits_{i=1}^m \sum\limits_{j=1}^n f(x_{ij})}{\sum\limits_{i=1}^m \sum\limits_{j=1}^n x_{ij}}\]

…(14)(15)(16)

\[s.t. X \in \Omega\]

…(17)

其中:

  • \(\lambda\)表示weight参数
  • \(\Omega\)是等式(10)-(13)描述的决策(变量)空间
  • \(g(X \mid \lambda)\)是目标函数

应该注意的是,通过等式(14)-(17)建模的分配问题是一个组合优化问题,并且它是非线性和非平滑的。组合优化问题是,它的可行解集合是离散的。该问题是NP-hard完全问题,它在多项式时间内全局最优的求解是相当难的。像branch和bound的搜索算法可以退化成完全枚举,并且CPU时间需要求解,可能会在最坏情况下指数级增长。为了实际求解这样的问题,必须合理的满足寻找好的近似最优解。作为搜索一个近似最优解的经典算法,GA提供了一个可选的方法。不同于通用的GA,我们提出的GA框架包含了以下主要两个部分:

  • coding scheme考虑上ODE约束
  • 本地搜索操作(带elitist策略的选择、交叉和突变)

4.1 Coding Scheme和ODE-based Fitness

根据GA的常用框架,对于分配问题的解是一个染色体(chromosome)或个体(individual)。特别的,在我们问题中的chromosome是一个矩阵,其中,elements是从drawers的相应位置分配的PV value。chromosome会以两步生成:

  • 1) 对于任意内容\(q_i\),会生成一个关于PV values的排列\(x_i = [x_{i,1}, x_{i,2}, \cdots, x_{i,n}]\),其中\(x_i\)的长度为n
  • 2) 对于不同内容合并所有的排序,是为了形成关于chromosome的最终形式\(X= [x_1, x_2, \cdots, x_m]\)

在GA中,每个个体(individual)的fitness函数的值,例如(fitness),是与生存者(survival)的概率是高度相关的。高fitness的个体相对于整体人口来说具有一个被选中进行交配(mating)的高概率,而低fitness个体具有一个相应的被选中低概率。特别的,在该问题中的个体X的fitness函数等于在等式(14)中定义的目标函数。需要注意的是,等式(14)的主要部分是\(f(x_{ij})\)。如上所述,\(f(x_{ij})\)是一个对应于PV value \(x_{ij}\)的CLICK value,它可以通过第3.2节提到的pv-click-ctr模型来获得。假设个体X的fitness函数是F(X),假设:\(U=\lbrace u_1, u_2, \cdots, u_l \rbrace\),以及\(V=\lbrace v_1, v_2, \cdots, v_l\rbrace\)分别表示历史天级PV数据和CLICK数据的集合。由于在等式(4)中定义的两个参数通过使用U和V的数据进行fit,假设\(l \geq 4\)。对于一个PV value \(x_{i,j} \in X\),寻找一个element \(u_k \in U\)如下:

\[u_k = argmin || u_{\bar{k}} - x_{i,j} ||, u_{\bar{k}} \in U\]

…(18)

根据等式(3),我们可以获得\(x_{i,j}\)的一个相应CLICK value:

\[f(x_{i,j}) = v_k + r(1 - \frac{v_k}{v_{max}}) v_k(x_{i,j} - u_k)\]

…(19)

其中,r和\(v_{max}\)是通过将来自U和V的数据作为input来fit的参数。接着根据等式(14),fitness function F(X)可以获得:

\[F(X) = g(X|\lambda)\]

…(20)

4.2 Elitist策略的局部搜索操作

局部搜索操作(local selection operation)涉及到一系列操作,比如:选择(selection)、突变(mutation)、交叉(crossover)。主要目标是,继承高质量基因到下一代中,并进一步提升计算效率以及全局收全敛的概率。

在选择阶段,我们会使用elitism策略来保留“好”基因到下一代中。具体的,假设\(X_u^k\)是在第k代的个体,下一代对应\(X_u^k\)如下:

\[X_i^k =\]

…(21)

这意味着,我们只要保留具有高fitness value的个体到下一代即可。

交叉操作会随机将高质量个体的基因片段进行随机交叉。交叉概率的范围推荐0.4-0.99. 我们使用Order Crossover(OX) strategy。

突变(mutation)操作在GA中具有探索效应,这被期望可以达到大概率的全局最优。通过突变操作,一个新的染色体会通过在交叉之后在染色体中变更某些基因的编码来生成。为了确认人口演进的稳定性,突变概率通常会设得更小的值。本paper使用一种自适应突变概率,如下所示:

\[p_m =\]

…(22)

其中\(p_{max}\)和\(p_{min}\)表示最大和最小突变概率,其中在本paper分别采用0.05和0.01. F是fitness function,\(F_{max}\)和\(F_{avg}\)是对于当前人口的fitness function的最大值和平均值。

5.实验

参考

STAR算法介绍

阿里在《One Model to Serve All: Star Topology Adaptive Recommenderfor Multi-Domain CTR Prediction》中提出了一种思路来解决不同模块使用同一模型的思路:# 1.介绍传统CTR模型关注于si...… Continue reading

PLE介绍

Published on March 04, 2021

DTS介绍

Published on January 02, 2021