whole page优化介绍

Reading time ~1 minute

摘要

MAB framework(Multi-Armed Bandit)已经被成功应用到许多web应用中。然而,许多会涉及到内容推荐的复杂real-world应用不能满足传统的MAB setting。为了解决该问题,我们考虑一个ordered combinatorial semi-bandit问题,其中,learner会从一个包含K actions的base set中推荐S个actions,并在S(超过M)个不同的位置展示这些结果。目标是:在事后根据最可能子集和位置来最大化累积回报(cumulative reward)。通过采用minimum-cost maximum-flow network(最小费用最大流网络),基于thompson sampling的算法常用于(contextual)组合问题中,以解决这个组合难题。它可以潜在与whole-page推荐以及任意概率模型一起工作,来说明我们方法的高效性,我们主要关注Gaussian process optimization以及一个contextual setting,其中ctr使用lr进行预测。我们演示了该算法在synthetic Gaussian process问题上的效果,以及在Yahoo!首页的Today Module的大规模新闻推荐数据集进行了验证。

1.介绍

我们使用新闻推荐作为示例。图1是一个portal website的snapshot。在该view中,存在6个slots来展示新闻推荐。这些slots在positions、container sizes以及visual appearance上都不同。一些研究表明:用户不会顺序扫描webpages[Liu 2015, Lagun 2014]。如何作出whole-page推荐,也就是说,从一个更大池子中选择6篇文章,并将它们放置在webpage上,这是一个在ranking之外的组合问题(combinatorial problem)。我们的目标是,寻找一个最优的布局配置(layout configuration)来最大化期望的总CTR。这个主题也有相关工作(Wang 2016),然而搜索引擎以real-time方式工作,它们的模型在batch data上训练(而非online learning的方式),因而忽略了exploration/exploitation tradeoff。

一些已经存在的工作使用multi-plays来解决bandits,例如:

  • subset regret problem(Kale 2010..)
  • batch mode bandit optimization with delayed feedbackes(Desautels 2014)
  • ranked bandits(Radlinski 2008)

这类learning问题也被看成是一个combinatorial bandit/semi-bandit (Gai 2013)。然而,我们示例中的复杂combinatorial setting难度超出了这些方法。

为了建模这种场景,我们考虑如下的rodered combinatorial bandit问题。给定最优的context信息,而非选择一个arm,learner会选择一个关于S个actions的subset,并从M个可能位置上在S个不同位置对它们进行展示。我们的新颖性有:

  • 1.我们的方法不会求助于其它方法来提供近似解。相反,我们会将该问题通过mcmf network进行公式化,并有效提供精确解(exact solutions)
  • 2.据我们所知,我们的模型会处理通用的layout信息,其中positions的数目可以大于选中arms的subset数,例如:S < M.
  • 3.我们会使用Thompson sampling作为bandit实例。Thompson sampling的一个优点是,不管随机reward function有多复杂,它在计算上很容易从先验分布进行抽样,并在所抽样参数下选择具有最高reward的action。因此,它可以潜在与任意probabilisitic user click模型一起工作,例如:Cascade Model和Examination Hypothesis。

图1

2.问题设定

由于position和layout bias,很合理假设:对于每篇文章和每个position,存在与(content, position) pair相关联的一个ctr,它指定了用户对于在一个特定position上展示的内容的点击概率。在一个序列rounds(\(t=1,2,\cdots, T\))上,learner需要从关于K个actions的一个base set A中选中S actions来在S(小于M)个不同positions上展示,并接受到一个reward:它是在选中subset中关于(action,position) pair的rewards的总和。对于每个展示的(content, position) pair,所有回报(payoff)会被展示。该feedback model被称为“semi-bandits”(Audiber, 2013)。我们可以根据该方法来展示建模关于selected arms中subset的positions,我们称该setting为“ordered combinatorial semi-bandits”。

Ordered(Contextual) Combinatorial Bandits

在每个round t,learner会使用一个(optional)context vector \(x_t\)展示。为了考虑layout信息,会为每个(action, position) pair (k, m)构建一个feature vector \(a_{k,m}\)。该learner会从A中选择S个actions来在S(小于M)个不同positions进行展示。因此,一个合法的combinatorial subset是一个从S个不同actions到S个不同positions的映射;或者更简单地,它是一个one-to-one映射 \(\pi_t : \lbrace 1,2,\cdots, S\rbrace \rightarrow (A, \lbrace 1,2,\cdots, M \rbrace)\)。我们接着将每个\(\pi_t\)看成是一个super arm。该learner接着为每个选中的(action, position) pair接收 reward \(r_{\pi_t(s)} (t)\)。round t的总reward是每个position \(\sum\limits_{s=1}^{S} r_{\pi_t(s)}(t)\)的rewards总和。目标是:随时间最大化expected cumulative rewards \(E[\sum_{t=1}^T \sum_{s=1}^S r_{\pi_t(s)}(t)]\)。

contextual conbinatorial bandits的一个重要特例是,context-free setting:它对于所有t来说,context \(x_t\)是个常量。通过将S, K设置成特殊值,许多已经存在的方法可以被看成是我们的combinatorial bandits setting的特例。例如:S=1等价成传统的contextual K-armed bandits。如果我们将K=1设置成dummy variable,并将N个positions看成是actions,我们的combinatorial bandit问题会退化成为unordered subset regrets问题(Kale 2010)。bandit ordered slate问题以及ranked bandits可以看成是S=M的特例。我们的setting不局限于l2r,足够通用可以对whole-page presentation进行optimize。

3.Thompson Sampling

在(contextual) K-armed bandit问题中,在每个round会提供一个最优的context信息x。learner接着会选择一个action \(a \ in A\)并观察一个reward r。对于contextual bandit问题,Thompson Sampling在Bayesian setting中是最容易的。每个过往observation包含了一个三元组\((x_i, a_i, r_i)\),以及reward的likelihood function,通过参数形式\(Pr(r \mid a, x, \theta)\)在参数集\(\Theta\)上进行建模。给定一些已知的在\(\Theta\)上的先验分布,这些参数的后验分布基于过往observations通过Bayes rule给出。在每个time step t上,learner会从后验中抽取\(\hat{\theta}^t\),并基于抽取的\(\hat{\theta}^t\)选择具有最大expected reward的action,如算法1所示。

4.Orderd Combinatorial Semi-Bandits算法

由于Thompson sampling对于复杂reward functions的灵活性,我们的主要算法思想使用它来进行ordered semi-bandits。

在每个round t,ordered combinatorial semi-bandit问题涉及到:从一个K actions的集合A中选中S个actions,并在S个不同positions上进行展示,并收到一个reward(所选subset的reward和)

一个naive方法是,将每个复杂的组合看成是一个super arm,并使用一个传统的bandit算法,它会在所有super arms上枚举values。由于super arms的数目会快速膨胀,该方法具有实际和计算限制。

假设每个context x以及(action, position) pair \(a_{k,m}\)的reward的likelihood function以\(Pr(r \mid x,a,\theta)\)的参数形式建模。下面三部分会开发thompson sampling的特殊变种,它们可以有效找到最优mapping \(\pi_t^*: \lbrace 1,2, \cdots, S \rbrace \rightarrow (A, \lbrace 1,2,\cdots, M \rbrace)\),使得:

\[\pi_t^* \in argmax_{\pi_t} \sum_{s=1}^S E[r \mid a_{\pi_t(s), x_t, \hat{\theta}^t]\]

…(1)

将action selection看成是一个约束优化(constrained optimization)

为了找到最佳的super arm \(\pi_t^*\),等式(1)中没有enumeration,我们首先定义:每个(action, position) pair的的expected reward为 \(E[r \mid a_{k,m}, x_t, \hat{\theta}^t]\) 。其中:对于在position \(p_m\)上展示action \(a_k\),给定context \(x_t\)以及采样参数\(\hat{\theta}^t\)。。。。我们也定义了指示变量\(f_{k,m}\)来表示action \(a_k\)是否会在position \(p_m\)上被展示,\(f_{k,m} \in \lbrace 0, 1 \rbrace\)。我们接着将一个合法的super arm转成数学约束。首先,由于每个action会至多被展示一次,它对应于constraint \(\sum_m f_{k,m} \leq 1, \forall k\)。第二,在同一个position上不能放置两个action,因而我们有\(\sum_k f_{k,m} \leq 1, \forall m=1, \cdots, M\)。最终,会选中S个actions,它等价于\(\sum_k \sum_m f_{k,m} = S\)。在等式(1)中对super arms进行最大化,可以被表示成如下的integer programming:

\[\overset{f}{max} \sum\limits_{k=1}^K \sum\limits_{m=1}^M f_{k,m} e_{k,m}\]

服从:

\[...\]

…(2)

总之,integer programming问题不能被高效求解。然而,在下一节所示,给定的公式可以被解释成一个network flow,它遵循多项式时间解。

Network flow

integer optimization问题(2)可以被看成是一个minimum-cost maximum-flow公式,它的edge costs为\(-e_{k,m}\),如图2所述。决策变量\(f_{k,m}\)表示flow的量,沿着一个bipartite graph的edges进行转移,具有expected rewards \(e_{k,m}\)。另外,S表示network flow的total size。另外,与biparite graph相连的edges的flow capacity为1,它表示这些edges可以适应一个flow,至多1个unit。另外,我们可以将constraints的最后集合使用连续等价\(f_{k,m} \in [0,1]\)进行relaxing,将(2)的integer programming公式变更成一个linear programming。

定理1:一个有向网络(directed network)的node-arc incidence matrix是完全unimodular。

这里,我知道问题(2)在linear programming relaxation中constraints的集合可以被表示成标准形式:\(Ax = b, x \geq 0\),它具有一个完全unimodular的constraint matrix A。由于一个graph的incidence matrix具有线性独立行(linearly independent rows),S是一个integer,我们知道linear programming relaation(2)的 super arm selection问题会导致一个integer optimal solution \(f^* \in \lbrace 0,1 \rbrace^{K \times M}\)。另外,linear programming问题可以使用interior-point方法在多项式时间求解,因此我们可以有效求解super arm selection问题。请注意,对于min-cost network flow问题的专有算法可以比linear programming方法具有更好的运行时间。然而,这样的专有方法通常不会允许引入额外的constrainints。对于这些原因,我们在实验中使用一个linear programming solver。

Thompson sampling进行combinatorial semi-bandits

参考

PLE介绍

tx在《Progressive Layered Extraction (PLE): A Novel Multi-TaskLearning (MTL) Model for Personalized Recommendations》提出了PLE模型:# 1.介绍个性化推荐在在线...… Continue reading

DTS介绍

Published on January 02, 2021

taobao Privileged Features Distillation介绍

Published on December 16, 2020