microsoft在《Position-Normalized Click Prediction in Search Advertising》对coec做了介绍。

1.介绍

竞价排名搜索广告的ctr预估系统的目标是:根据其它上下文知识(比如:用户信息),对一个query-ad pair估计CTR。ctr预估对于ad排序、位置分配(allcation),定价(pricing),以及回报(payoff)很关键。通过估计得到的CTR作为query-ad相关度的一种衡量,并且与其它非相关因子相互独立。然而实际上,有许多外围因子影响着基于相关度的ctr系统,通常会在观察到的点击数据(click-through data)上扮演着重要角色。一个经典的示例是:广告展现位置(ad presentation position)。这些外在因子必须小心处理,否则会导致一个次优的ctr预估,许多真实世界的系统都会存在这种缺陷。

我们提出了一个概率因子模型(probabilistic factor model)作为一个总的原则性方法来研究这些效应。该模型很简单并且是线性的,在广告领域会做出经验性的调整。对于纠正在搜索算法上的位置偏差(positional bias)有大量研究,许多研究都是:检测模型(examination model)[12],cascade model[5], 动态贝叶斯网络模型(DBN)[3],而对于搜索广告领域却很少。我们的方法采用了与examination model相似的因子分解假设,也就是说:在item上的点击概率,是一个关于位置先验概率和一个基于相关度的与位置无关的概率的乘积。再者,我们会专门研究广告领域的位置概念,通过合并其它广告特有的重要信号,例如:query-ad keyword match type和广告总数。

来自搜索算法的其它模型(比如:cascade和DBN模型),通常会假设:一个item的估计得到的ctr(estimated CTR)是与展示在搜索结果页的items的相关度(relevance)相互独立的。这些更复杂的假设对于搜索算法结果更合适,其中用户对于结果链接之一上的点击行为具有一个高概率。然而对于广告,在广告上的点击概率总是相当低,通常是一个百分比。因此,效果越高(非点击)的广告是相互接近的因子的乘积。

2.因子模型

假设:

  • i表示一个query-ad pair
  • j表示ad的位置
  • c表示点击次数
  • v表示曝光次数

观察到的CTR是一个条件概率 。对于在竞价搜索广告中的经验假设,我们做出如下简化:

  • 1.一个ad的点击是与它的位置相互独立的 (假设:位置可以物理上进行检查examining)。
  • 2.给定一个ad的位置,检查(examining)一个广告是与它的内容或相关度是相互独立的

正式的,位置依赖的CTR(position-dependent CTR)可以表示为:

…(1)

其中:

  • 第一个因子 :可以简单表示为,它是一个位置归一化的CTR(position-normalized CTR),可以表示ad的相关度
  • 第二个因子 ,可以简单表示为,体现了位置偏差( positional bias)。

有了该CTR因子分解(factorization),我们可以处理关于点击行为的两种自然随机模型,接着在部署模型上通过一个先验进行平滑。【1,9】

3. Binomial模型

很自然的,假设点击数遵循一个二项分布:

。。。

4.POISSON模型

如果尝试次数n足够大,成功概率p (success probability)足够小,那么。由于广告(ad)就是这样一个领域,我们可以导出Poisson模型,它会生成一个相似的且足够有效的更新。该生成模型是:

…(9)

5.GAMMA-POISSON模型

对于empirical和regularization的目的,我们在Poisson模型中在位置因子(positional factor)上引入了一个gamma先验:

…(16)

经验上,观察CTR(observed CTR)几何上会随位置的降低而递减【11】,展示出与gamma信号有一个很好的拟合。实例上,次一点的位置(inferior positions,比如:side bar的底部位置)可能会遭受严峻的数据稀疏性问题,尤其是点击;因此,正则化(regularizing)或平滑(smoothing)这些噪声估计会产生更好的泛化。gamma分布是一个常见的选择,因为它是Poisson的一个共轭先验。

。。。

6.点击模型

一个点击模型或CTR预测模型的目标是:为给定的一个query-ad pair,估计一个位置无偏CTR(positional-unbiased CTR),例如:相关度CTR(relevance CTR) 。上述描述的位置归一化点击模型(positional normalized click model)会做这样的处理,同时也会发生位置先验概率 。factor模型的另一个观点是:在ad位置上做过平滑的kNN模型;当特征空间只包含了query-ad pairs,k=1。对于有足够历史点击数据的query-ad pairs这是可信的,因子模型可以合理执行。而对于一个冷启动问题原则性处理方法是,将queries和ads的一元特征(unigram features)添加到特征空间中,当在预测时遇到新的pairs时对CTR预估做backing-off。

位置归一化点击模型也可以被独立应用,并联合其它点击模型来估计relevance-only CTR。更严厉的,我们会所设位置因子与其它相关度因子相互独立。在模型训练时,需要通过它的位置先验来归一化每个ad曝光。在预测时,CTR预测器会从位置归一化的训练数据中进行学习,并生成完全的relevance-only CTR。

7.实验

7.1 使用人造数据仿真

我们首先在一个通过概率模型(例如:给定一个sound模型)生成的人造数据集上仿造了Gamma-Poisson模型。通过仔细设计模型参数,人造数据可以十分模仿真实的搜索广告数据。尽管模仿数据不能完全反映真实系统,但它至少有两个优点:

  • 1.当从真实噪声中进行抽象时,允许快速研究大量参数
  • 2.通过该数据曝露的真实分布来验证学到的模型,对于真实数据很重要

数据生成如下:

    1. 位置 ,生成一个,以降序对q排序,通过对q进行缩放
  • 2.

参考

lightFM源自于paper: 《Metadata Embeddings for User and Item Cold-start》:

一、介绍

构建推荐系统能在冷启动场景中(新用户、新item)运行良好是个挑战。标准的MF模型在该setting中效果很差:很难有效估计user和item的隐因子,因为协同交互数据很稀疏。

基于内容的(CB)方法,可以通过使用item的metadata来解决该问题。因为这些信息是事先预知的,对于新item(没有协同数据可收集)的推荐依然可以计算。不幸的是,在CB模型中没有迁移学习出来:对于每个用户的建模是以孤立的方式估计得到的,并没有利用其它用户数据。因此,CB模型的执行会比MF模型要差。

最后,解决该问题很关键。我们是一家时尚公司,目标是为我们的用户提供便利的方法进行在线时尚品浏览、购买。为了这个目的,我们维护了一个非常大的商品目标:在写入时,我们会跨网络聚合超过800w的时尚items,并会每天添加上万新的商品。

为我们做出推荐有三个因子。首先,我们的系统包含了一个非常大的items数目。这使得我们的数据很稀疏。第二,我们如下进行处理:通常,最相关的items是那些新释放出的collections,允许我们只有一个短时间窗口来收集数据,并提供有效推荐。最后,我们的用户大比例是首次访问的用户(first-time visitors):我们希望为他们推荐引人注目的推荐,即使只有少量数据。用户和item的冷启动组合,使得纯粹的协同和CB方法不适用。

为了解决该问题,我们使用一个混合content-collaborative模型,称为LightFM,归因于它会对FM进行resemblance。在LightFM中,就像在一个协同过滤模型中一样,users和items被表示成隐向量(embeddings)。然而,正如在一个CB模型一样,这些都通过描述每个商品或用户的内容特征(content features)的函数进行定义。例如,如果该电影“绿野仙踪(Wizard of Oz)”通过以下的features描述:”音乐幻想剧(musical fantasy)”、“朱迪·加兰(Judy Garland)”、以及“Wizard of Oz”,那么它的隐表示可以通过对这些features的隐表示进行求和得到。

通过这么做,LightFM可以将CB和CF的推荐的优点进行联合。在该paper中,我们会对该模型公式化,并在两个数据集上进行实验,展示:

  • 1.在冷启动和低密度场景,LightFM至少与纯CB模型一样好,实质上,当满足以下二者之一(1)在训练集中提供了协同信息 (2) 在模型中包含了用户特征 时,效果要更好。
  • 2.当协同数据很丰富时(warm-start, dense user-item matrix),LightFM至少与MF模型效果一样好。
  • 3.通过LightFM生成的Embeddings,可以编码关于features的重要语义信息,可以被用于相关推荐任务:比如:标签推荐。

这对于真实推荐系统来说有许多好处。因为LightFM在dense和sparse数据上均表现良好,它不需要为每种setting构建和维护多个特定机器学习模型。另外,它可以同时使用user和item的metadata,它可以应用于user和item的冷启动场景。

LightFM python版的Github地址为:https://github.com/lyst/lightfm.

2.LightFM

2.1 动机

LightFM模型的结构受以下两种考虑的启发:

  • 1.该模型必须能从交互数据中学习user和item表示:如果描述为“舞会袍(ball gown)”和”铅笔裙(pencil skirt)”的items均被用户所喜欢,该模型必须能学到ball gowns与pencil skirts相似。
  • 2.该模型必须能为新items和users计算推荐

第1点通过使用隐表示方法来解决。如果ball gowns和pencil skirts均被相同的用户所喜欢,它们的embeddings会更接近;如果ball gowns和机车夹克(biker jackets)不会被相同的用户所喜欢,它们的embeddings会更远。

这样的表示允许迁移学习出现。如果对于ball gowns和pencil skirts的表示很相近,我们可以自信地推荐ball gowns给一个刚与pencil skirts交互过的新用户。

在纯CB模型之上使用降维技术(比如:LSI)也可以达到该目换,因为它们只会编码由feature co-occurrence给定的信息,而非用户动作。例如,假设所有浏览过由“飞行员(aviators)”描述的items的用户,同时也浏览了由“旅行者(wayfarer)”描述的items,但这两个features从未在相同的item中同时描述过。这种情况下,对于wayfarers的LSI vector不会与aviators的相似,即使协同信息建议应该这样做。

第2点通过将items和users表示成它们的content features的线性组合。由于content features被认为是:当一个user或一个item进入该系统时,它允许直接做出推荐。这种结构很容易理解。“牛仔夹克(denim jacket)”的表示看成是denim的表示和jacket的表示的求和(sum);一个来自美国的女性用户(a female user from the US)的表示是US的表示和female users的表示的求和。

2.2 模型

为了公式化描述该模型,假设U是用户集,I是items集合,是user features的集合,是item features的集合。每个用户与多个items交互,正向或者负向。所有user-item交叉pair 是正交互和负交互的联合。

Users和items通过它们的features进行完全描述。每个user u通过一个特征集合描述 。为每个item i它们的特征为。features是提前知道的,可以表示user和item的metadata。

该模型通过d维的user和item的feature embeddings 为每个feature f进行参数化。每个feature也可以通过一个标量bias项(对于user features是,对于item features则是)描述。

user u的隐表示,通过对它的features的隐向量进行求和来表示:

item i的隐表示类似,如下:

user u的bias项,通过对features的biases进行求和得到:

item i的bias项如下:

该模型对于user u 和 item i的预测,接着通过user向量和item向量的点乘,加上对应的偏置给出:

…(1)

有许多函数适合。一个identity函数也能对预测评分很好地运行;在本paper中,我们只对二分类数据预测感兴趣,因而选择sigmoid:

模型的最优化目标是,最大化在该参数上的条件似然。该似然如下:

…(2)

使用ASGD进行训练。4线程。learning rate使用ADAGRAD。

2.3 与其它模型关系

LightFM与协同MF模型间的关系,由user和item的feature sets的结构决定。如果feature sets只包含了每个user和item的指示变量,LightFM相当于MF模型。如果feature sets也包含了metadata features,它们被至少一个item或user所共享,那么LightFM就扩展了MF模型:通过让feature的隐因子来解释用户交互的部分结构。

这在三方面很重要。

  • 1.在大多数应用中,metadata features要比users或items还要少,因为使用一个确定类型/类目的结构,或者因为维护一个固定size的关于最常用项的字典,当使用原始文本特征时。这意味着,从受限的训练数据中,需要估计更少的参数,减小overfitting机率并提升泛化效果。
  • 2.指示变量的隐向量不能为新的、冷启动users和items进行估计。将它们表示成metadata features的组合,可以从训练集中被估计,并做出冷启动预测。
  • 3.如果只有指定变量,LightFM与标准MF模型相当。

当只有metadata特征、没有指示变量时,模型通常不会缩减到一个纯CB模型。LightFM通过对协同交叉矩阵进行因子分解来估计feature embeddings;这不同于CB模型:它会对纯内容共现矩阵进行因子分解。

一个特别的case是,当每个用户通过一个指示变量描述时,并且只与一个item交互时,此时LightFM会变为CB。在该setting中,user vector等价于在LSI公式中的一个document vector,只有在product descriptions中共同出现过的features具有相似的embeddings。

事实上,LightFM一方面包含了在sparse data的纯CB模型,另一方面包含了在dense data上的MF模型。事实上,经验表明,至少与每种场景的单一模型一样好。

参考

Label Partitioning For Sublinear Ranking

1.介绍

我们有一个multi-class或者multi-label问题,其中每个训练样本包含了一个上下文,以及一个关于target classes 的小集合(该集合在一个关于可能classes的大型空间L的范围之外)。例如,我们的问题可能是:给定前面的词汇,预测在句子中的下一个词。

1.1 F(x,y)

我们希望学习到一个兼容函数(compatibility function) ,它会说明关于某个class y以及一个context x间的兼容性。例如——给定该上下文,该class的概率

“穷举(Exhaustive)”训练法,比如:softmax和logistic regression需要我们为每个训练样本,对于每个类去计算F(x,y)。当很大时,计算开销会很大。

1.2

  • target classes(正样本):
  • candidate classes(候选样本):
  • randomly chosen sample of classes(负样本):

“候选采样(Candidate Sampling)”训练法,涉及到构建这样一个训练任务:对于每个训练样本,我们只需要为候选类(candidate classes)评估F(x,y)。通常,候选集合是target classes和随机选中抽样的classes(非正例) 的合集(union)。

随机样本可以依赖(或者不依赖)和/或

训练算法会采用神经网络的形式训练,其中:用于表示F(x,y)的layer会通过BP算法从一个loss function中进行训练。

图1

  • : 被定义为:给定context x,根据抽样算法在sampled classes的集合中得到class y的概率(或:expected count)。
  • :是一个任意函数(arbitrary function),不依赖于候选类(candidate class)。由于softmax涉及到一个归一化(normalization),加上这种函数不会影响到计算概率。
  • logistic training loss为:
  • softmax training loss为:
  • NCE 和Negatvie Sampling可以泛化到是一个multiset的情况。在这种情况中,表示在中y的期望数(expected count)。相似的,NCE,Negative Sampling和Sampled Logistic可以泛化到是一个multiset的情况。在这种情况下,表示在中y的期望数(expected count)。

Sampled Softmax

参考:http://arxiv.org/abs/1412.2007

假设我们有一个单标签问题(single-label)。每个训练样本包含了一个context以及一个target class。我们将作为:给定context x下,一个target class y的概率

我们可以训练一个函数F(x,y)来生成softmax logits——也就是说,该class在给定context上的相对log概率(relative log probabilities):

其中,K(x)是一个不依赖于y的任意函数(arbitrary function)。

在full softmax训练中,对于每个训练样本,我们会为在中的所有类计算logits 如果类L总数很大,计算很会昂贵

抽样函数:

在”Sampled Softmax”中,对于每个训练样本我们会根据一个选择抽样函数:来选择一个关于“sampled” classese的小集合。每个被包含在中的类,它与概率完全独立。

我们创建一个候选集合,它包含了关于target class和sampled classes的union:

我们的训练任务是为了指出:在给定集合上,在中哪个类是target class

对于每个类,给定我们的先验,我们希望计算target class y的后验概率。

使用Bayes’ rule:bayes

…(b)

得到:

接着,为了计算,我们注意到为了让它发生,可以包含y或也可以不包含y,但必须包含所有其它元素,并且必须不包含在任意classes。因此:

其中:是一个与y无关的函数。因而:

这些是relative logits,应feed给一个softmax classifier,来预测在中的哪个candidates是正样本(true)。

因此,我们尝试训练函数F(x,y)来逼近,它会采用在我们的网络中的layer来表示F(x,y),减去,然后将结果传给一个softmax classifier来预测哪个candidate是true样本。

从该classifer对梯度进行BP,可以训练任何我们想到的F。

#

以tensorflow中的tf.random.log_uniform_candidate_sampler为例。

它会使用一个log-uniform(Zipfian)base分布。

该操作会随样从抽样分类(sampled_candidates)中抽取一个tensor,范围为[0, range_max)。

sampled_candidates的元素会使用base分布被无放回投样(如果:unique=True),否则会使用有放回抽样。

对于该操作,基础分布是log-uniform或Zipf分布的一个近似:

当target classes近似遵循这样的一个分布时,该sampler很有用——例如,如果该classes以一个字母序表示的词语,并以频率降序排列。如果你的classes没有通过词频降序排列,就不需要使用该op。

另外,该操作会返回tensors: true_expected_count,

sampled_softmax_loss

def _compute_sampled_logits(weights,
                            biases,
                            labels,
                            inputs,
                            num_sampled,
                            num_classes,
                            num_true=1,
                            sampled_values=None,
                            subtract_log_q=True,
                            remove_accidental_hits=False,
                            partition_strategy="mod",
                            name=None,
                            seed=None):
    # 核心代码实现:
    if isinstance(weights, variables.PartitionedVariable):
        weights = list(weights)
    if not isinstance(weights, list):
        weights = [weights]

    # labels_flat:  batch_size.
    with ops.name_scope(name, "compute_sampled_logits",
                        weights + [biases, inputs, labels]):
        if labels.dtype != dtypes.int64:
            labels = math_ops.cast(labels, dtypes.int64)

        labels_flat = array_ops.reshape(labels, [-1])

    # 抽取num_sampled个样本.
    if sampled_values is None:
        sampled_values = candidate_sampling_ops.log_uniform_candidate_sampler(
            true_classes=labels,
            num_true=num_true,
            num_sampled=num_sampled,
            unique=True,
            range_max=num_classes,
            seed=seed)

    # 这三个值不会进行反向传播
    sampled, true_expected_count, sampled_expected_count = (array_ops.stop_gradient(s) for s in sampled_values)

    # 转成int64
    sampled = math_ops.cast(sampled, dtypes.int64)

    # label + sampled (labels基础上拼接上抽样出的labels)
    all_ids = array_ops.concat([labels_flat, sampled], 0)

    # 合并在一起,使用all_ids一起进行查询
    all_w = embedding_ops.embedding_lookup(
        weights, all_ids, partition_strategy=partition_strategy)

    # 分割出label的weight.
    true_w = array_ops.slice(all_w, [0, 0],
                             array_ops.stack(
                                 [array_ops.shape(labels_flat)[0], -1]))

    # 分割出sampled weight.
    sampled_w = array_ops.slice(
        all_w, array_ops.stack([array_ops.shape(labels_flat)[0], 0]), [-1, -1])

    # user_vec * item_vec
    sampled_logits = math_ops.matmul(inputs, sampled_w, transpose_b=True)

    # bias一起查询.
    all_b = embedding_ops.embedding_lookup(
        biases, all_ids, partition_strategy=partition_strategy)

    # true_b is a [batch_size * num_true] tensor
    # sampled_b is a [num_sampled] float tensor
    true_b = array_ops.slice(all_b, [0], array_ops.shape(labels_flat))
    sampled_b = array_ops.slice(all_b, array_ops.shape(labels_flat), [-1])

    # element-wise product.
    dim = array_ops.shape(true_w)[1:2]
    new_true_w_shape = array_ops.concat([[-1, num_true], dim], 0)
    row_wise_dots = math_ops.multiply(
        array_ops.expand_dims(inputs, 1),
        array_ops.reshape(true_w, new_true_w_shape))

    # true label对应的logits, bias.
    dots_as_matrix = array_ops.reshape(row_wise_dots,
                                       array_ops.concat([[-1], dim], 0))
    true_logits = array_ops.reshape(_sum_rows(dots_as_matrix), [-1, num_true])
    true_b = array_ops.reshape(true_b, [-1, num_true])


    true_logits += true_b
    sampled_logits += sampled_b

    # 减去先验概率.
    if subtract_log_q:
      # Subtract log of Q(l), prior probability that l appears in sampled.
      true_logits -= math_ops.log(true_expected_count)
      sampled_logits -= math_ops.log(sampled_expected_count)

    # 输出logits,拼接在一起.
    out_logits = array_ops.concat([true_logits, sampled_logits], 1)

    # 输出的labels.
    out_labels = array_ops.concat([
        array_ops.ones_like(true_logits) / num_true,
        array_ops.zeros_like(sampled_logits)
    ], 1)

    return out_logits, out_labels

得到logits和labels后,就可以计算softmax_cross_entropy_with_logits_v2了。

log_uniform_candidate_sampler

1
2
3
4
5
6
7
8
9
tf.random.log_uniform_candidate_sampler(
true_classes,
num_true,
num_sampled,
unique,
range_max,
seed=None,
name=None
)

使用一个log-uniform(Zipfian)的基础分布来采样classes集合。

该操作会对一个sampled classes(sampled_candidates) tensor从范围[0, range_max)进行随机抽样。

sampled_candidates的elements会从基础分布进行无放回抽样(如果unique=True)或者有放回抽样(unique=False)。

对于该操作的base distribution是一个近似的log-uniform or Zipfian分布:

当target classes近似遵循这样的一个分布时,该sampler很有用——例如,如果该classes表示字典中的词以词频降序排列时。如果你的classes不以词频降序排列,无需使用该op

另外,该操作会返回true_expected_count和sampled_expected_count的tensors,它们分别对应于表示每个target classes(true_classes)以及sampled classes(sampled_candidates)在sampled classes的一个平均tensor中期望出现的次数。这些值对应于在上面的。如果unique=True,那么它是一个post-rejection概率,我们会近似计算它。

paper2

另外在paper 2《On Using Very Large Target Vocabulary for Neural Machine Translation》的第3节部分,也做了相应的讲解。

paper2 第3节

在该paper中,提出了一种model-specific的方法来训练具有一个非常大的目标词汇表(target vocabulary)的一个神经网络机器翻译(NMT)模型。使用这种方法,训练的计算复杂度会是target vocabulary的size的常数倍。另外,该方法允许我们高效地使用一个具有有限内存的快速计算设备(比如:一个GPU),来训练一个具有更大词汇表的NMT模型。

训练一个NMT的计算低效性,是由等式(6)的归一化常数引起的。为了避免计算该归一化常数的成长复杂度(growing complexity),我们这里提出:在每次更新时使用target vocab的一个小子集。提出的方法基于早前Bengio 2008的工作。

等式(6), next target word的概率:

…(6)

其中Z是归一化常数(normalization constant):

…(7)

假设我们考虑在等式(6)中output的log-probability。梯度的计算由一个正部分(positive part)和负部分(negative part)组成:

…(8)

其中,我们将energy 定义为:

梯度的第二项(negative)本质上是energy的期望梯度:

…(9)

其中P表示

提出的方法主要思想是,通过使用少量samples进行importance sampling来逼近该期望,或者该梯度的负项。给定一个预定义的分布Q和从Q中抽取的一个样本集合,我们使用下式来逼近等式(9)中的期望:

…(10)

其中:

…(11)

该方法允许我们在训练期间,使用target vocabulary的一个小子集来计算归一化常数,每次参数更新时复杂度更低。直觉上,在每次参数更新时,我们只会更新与correct word 以及在中的sampled words相关的vectors。一旦训练完成,我们可以使用full target vocabulary来计算每个target word的output probability。

尽管提出的方法可以天然地解决计算复杂度,使用该方法本质上不能在每个句子对(sentance pair:它们包含了多个target words)更新时保证参数数目。

实际上,我们会对training corpus进行分区(partition),并在训练之前为每个分区(partition)定义一个target vocabulary子集。在训练开始之前,我们会顺序检查训练语料中的每个target sentence,并累积唯一的target word,直到唯一的target words达到了预定义的阀值。然后在训练期间将累积的vocabulary用于corpus的partition。我们会重复该过程,直到达到训练集的结尾。假设对于第i个partition的target words的子集用表示。

这可以理解成,对于训练语料的每个partition具有一个单独的分布。该分布会为在子集中包含的所有target words分配相等的概率质量(probability mass),其它words则具有为0的概率质量,例如:

提议分布(proposal distribution)的选择会抵消掉correction term——来自等式(10)-(11)中importance weight的,使得该方法等价于,使用下式来逼近等式(6)中的准确output probability:

需要注意的是,Q的这种选择会使得estimator有偏。

对比常用的importance sampling,提出的该方法可以用来加速,它会利用上现代计算机的优势来完成matrix-matrix vs. matrix-vector乘法。

参考

Microsoft在《Trustworthy Online Controlled Experiments: Five Puzzling Outcomes Explained 》中对A/B testing中存在的5个谜题做了解释。

3.1 搜索引擎的OEC

3.1.1 背景

选择一个好的OEC对于整个商业经营很重要。这些指标驱动着go/no-go的决策。在之前工作中,我们强调了长期关注的必要,并建议将lifetime value作为一个指导原则。像日活用户(DAU)这样的指标被一些公司所使用。在《7 pitfalls to Avoid when Running controlled Experiements on the web》中,首个陷阱是:

从商业角度上看,应选择这样一个OEC:它可以通过做一些很明显“错误(wrong)“的事情就很轻易地击败control组实验

当我们尝试为Bing获得一个OEC时,我们会首先关注商业目标。当前有两个顶级的长期目标:查询分享(query share)以及每次搜索的回报(revenue per search)。确实,许多项目被激励来提升它们,但有一个很好的示例:短期目标和长期目标完全背离。

3.1.2 Puzzling Outcome

当Bing在实验中有个bug,导致了展示给用户非常差的结果,但两个关键的公司级指标提升显著:每个用户的不同查询数(distinct queries per user)涨了10%,每用户回报(revenue per user)提升了30%! Bing应该如何评估该实验?什么是OEC?

很明显,实验中的长期目标与短期指标是不能对齐的。如果它们可以对齐,我们可以降低质量来提升query share和revenue!

3.1.3 解释

从搜索引擎的角度,退化的算法结果(展示给用户的主搜索引擎结果,有时也被称为10个蓝链接(10 blue links))会强制用户发起更多的查询(这会增加每个用户的queries)以及点击更多的广告(增加回报)。然而,这很明显是短期提升,这与零售商店里提升价格相似:你可以增加短期回报,但客户更偏向于与时间竞赛,因此平均顾客的生命周期价值(lifetime value)将会缩短。

为了理解该问题,我们分解了query share。我们将月查询分享数(monthly query share)定义为:Bing上不同查询数 / 一整个月所有搜索引擎的不同查询数,正如comScore所测量的(distinct意味着:同一用户在半小时内在相同的垂直搜索引擎(比如:网页or图片)上连续重复的queries,被统计成1)。由于在Bing上,我们可以很轻易地测量分子(我们的distinct queries,而非整个makret),该目标是为了增加该component。每个月的distinct queries可以被分解成三个项相乘:

…(1)

其中,在乘积中的第2项和第3项会在月周期上计算,session被定义为:用户开始发起一个query、30分钟后在搜索引擎上没有活动就结束。

如果一个搜索引擎的目标是,允许用户快速发现它们的答案、或者完成它们的任务,那么减小每个任务的distinct queries是一个明确的目标,它会与关于增加收入的商业目标相冲突。因为该指标与每个sesion不同查询数(distinct queries per session)高度相关(),我们推荐:distinct queries不能单独用来作为搜索实验的OEC。

给定如等式(1)所示的不同查询的分解,我们来看下这三个项:

  • 1.User per month。在一个controlled experiment中,独立用户数由设计决定。例如,在一个相等的A/B test中,用户数会以近似相同的数目分到两个variants中。(如果在variants中用户的比例很不同,这很可能是个bug)。出于该原因,该项不能成为该实验OEC的一部分。
  • 2.每任务查询数(distinct queries per task)应该最小化,但它很难测量。每session不同查询数(distinct queries per session)是一个可用的代理指标(surrogate metric)。这是一个精细指标(subtle metric),然而,由于增加它可能意味着用户需要发起理多查询来完成该任务,但减少它可能表示放弃查询。该指标需要最小化,意味着该任务会被成功完成
  • 3.Sessions/user 是在实验中要优化(增加)的关键指标,因为满意的用户会来得更多。这是一个在Bing中OEC的关键成分(key component)。如果我们有好的方式来标识tasks,等式(1)中的分解可以通过task来进行,我们可以优化tasks/user。

在搜索引擎结果页上展示的退化算法结果,会给用户一个明显更差的搜索体验,但会造成用户点击更多广告(它的相对相关度会增加),从而增加短期回报。在没有其它约束下,每用户回报(Pevenue per user)同样不能被用来当成搜索和广告实验的一个OEC。当关注回报指标时,我们希望:在不会对用户满意度指标(比如:sessions/user)造成负面影响的情况下增加它们。

3.1.4 学到的

query量的分解,搜索的长期目标,展示了冲突的组成(components):一些会增加短期指标(sessions/user),另一些会减小短期指标(queries/session)表示任务成功完成。我们的假设是,更好的用户体验会增加users/month,最后一项不能在一个control实验中进行测量。

该分析不仅影响搜索实验,也会影响SEM等(search engine marketing)。当决定广告的bid量时,很自然的会尝试和优化在session中的queries数,它会伴随广告点击。然而,长的sessions表示用户找不到满意的东西(例如:驱动用户下拉更多结果页)

顾客生命周期值(Lifetime customer value)通常应是决定OEC的指导准则。对于controlled experiments,特定的短期指标的选择需要很好地理解商业,同时理解以下这点很重要:长期目标不能总是与短期指标相对齐。

3.2 点击跟踪

3.2.1 背景

跟踪用户的在线点击和表单提交(比如:搜索(searches))对于web分析、controlled experiments、以及商业智能很重要。大多数网站使用web beacons(1x1 pixel图片请求)来跟踪用户动作,但等待beacon在点击和提交上的返回会减慢下一动作(例如:展示搜索结果、或者目标页)。一种可能性是,使用一个较短超时(short timeout),共识是:跟踪机制(停留在用户动作)的用时越多,数据损失越低。从Amazon、Google、Microsoft的研究表明,数百毫秒的小延迟,对于回报和用户体验会有剧烈的副作用,我们发现许多网站允许较长延时以便更可靠的收集点击数据。例如,到2010年3月,多个microsoft网站等待click beacons返回一个2s的timeout,这会在用户点击上引入一个大约400ms的平均延迟。关于该主题的一个白皮书最新已经发布[23]。据我们所知,该issue并没有被大多数网站owners所理解,它们的实现具有很大的click losses。对于广告,点击与支付相绑定,重定向通常被用于避免click loss。然而,对于用户这会引入一个额外的delay,对于tracking clicks来说并不常用。

3.2.2 Puzzling Outcome

仅仅添加一小段代码,比如:当用户点击一个搜索结果时,执行额外的JavaScript。需要在那个点被执行该段Javascript代码的原因是,在浏览器被允许处理和打开目标站点之前,目标站点的session-cookie被更新。

这会轻微地减慢用户体验,但实验表明用户会点击更多!为什么呢?

3.2.3 解释

用户点击更多的“成功”并不是真实的,准确来说是一个仪表误差(instrumentation difference)。chrome、firfox、safari对于结束从当前页导航走的请求更激进些,关于click beacons的一个不可忽视的比例并不会向server做出[23]。。。

3.初始效应(Initial Effect)

3.3.1 背景

给定,介绍中提到的评估A/Btesting具有很高的失败率,这非常常见,对于在实验的头几天,可以看到新版本是winner或者可以过早结束。 在该内容中会提到当新特性被引入时的两个效应:始效应(Primacy effects)和Novelty effects。这些都是负面效应,有时会影响实验。 当你在网站上变更了导航(navigation)时会出现Primacy effect,体验的用户可能会变得更低效,直到它们习惯了新导航,因而对于Control组有着天然的优势。相反的,当一个新设计或新特性被引入时,一些用户会研究该新特性,到处进行点击,从而引入一个“Novelty” bias,这会快速消逝,因为该特性并不是真的有用。该bias有时与”霍索恩效应(Hawthorne Effect)”有关,例如:一个短暂的提升。上述提到的实验,其中在MSN主页上的hotmail链接被变更成以独立tab/window方式打开hotmail,会有一个很强的Novelty effect:用户可能很吃惊,并尝试它多次。而Novelty effects会在一个较短时间后消逝,并产生一个更小的效应,长期影响(long-term impact)仍会是正向、无效、或负向的。在这个case中,long-term effect是正向的,该特性会驻留在MSN主页上。Primacy effects和Novelty effects可以通过生成在时间上的delta graph(在Control和Treatment间),以可视化或可分析地方式来进行评价,并评估趋势。如果我们怀疑这样的趋势,我们可以拓展该实验。为了评估正向效果(true effect),可以做一个分析,其中只对在不同variants实验上的新用户计算OEC,因为他们没有受Primacy和Novelty effect的影响。另一个观点是,排除第一周的实验,因为delta通常会在一周之后变得稳定。我们的结果:大多数情况下疑似的Primacy和Novelty effects并不是真实的,只是统计的加工品(statistical artifact)。

3.3.2 Puzzling outcome

在许多实验中,前几天的效果看起来会趋高或者趋低。例如:图3展示了一个真实实验在关键指标上前4天的效果,其中在图中的每个点展示了直到那一天的累积效应(cumulative effect: delta),通过feature owner跟踪得到。

图3

该效果表明:在前4天有一个很强的正趋势。实验者(它希望得到一个正向结果)看到了该intial negtive delta,但使用点虚线来线性推断该趋势,并认为在接下来的几天,该效果将以跨过0%并在第6天开始变成正向。这种思维很常见:我的新特性是明显很棒的,但对用户来说需要花费时间来习惯它,例如:在头几天时我们会看到Primacy effect。用户必须开始越来越喜欢该特性,这对吗?当然是错的!许多情况下,这是可预期的。

3.3.3 解释

对于许多指标来说,均值的标准差与成正比,其中n是用户数。出于简洁性,假设没有重复用户。例如,每个用户在实验期间只访问一次(结果不会变化很多,但使用实际会发生的次线性增长时)。因此,n与天数成正比。如图4所示,当实际效应(actual effect)为0时,对于测量效应(measured effet)的95%置信图。

图4

前几天是高度可变的,因此在初始几天的效应(effect)可能会或高或低于在两或三周后的效应(effect)。例如,头一天具有67%的可能性在95%置信区间之外在实验尾部下降;第二天具有55%的可能性在该区间外。由于该序列(series)是自相关的(auto-correlated),存在两个含义:

  • 1.相对于之前实验发布的最终结果(它们会运行更长的时间),在初始几天的effects通常看起来过度正向或者负向。
  • 2.在前几天期间,累积结果看起来会延伸。例如,假设一个实验在兴趣指标上没有effect。头一天可能是负向的-0.6%,但随着更多数据被累计,该效应(effect)会回归到0均值、95%置信锥的true。feature owners不正确地假设该effect是会延伸的,那将很快会跨过0线。当然,这很少会发生。

图3的graph实际上来自于一个A/A test(control和treatment间没有区别),effect的均值为0. 第一天具有一个负差值(negative delta)(注意:该宽置信区间会与0交叉),随着时间向前,该置信区间会收缩,结果会回归到该均值。确实,如图5所示,该graph会随时间在0附近稳定。

图5

3.3.4 学到的东西

出现”趋势(trends)”是可预期的,因为我们将它看成是一种educational和awareness issue,尽管我们承认后见之明(hindsight)是20/20,我们也会被初始趋势迷惑多次。当你开始涉及实现一个idea、并希望它成功时,确认偏误(confirmation bias)是很强的。当你构建一个假设并希望它趋向正确方向时,初始的负向结果通常进行抑制。

我们运行的实验很少有Primacy effects与intial effects相反的(reverse),例如:某一特性初始是负向的,直到用户学会它并对它习惯,它才会是正向。由于存在这些效应(effects),我们不能发现:单个实验在某一方向上具有统计显著的结果,在另一方向上也会统计显著(例如:一个统计显著的负向,变成统计显著的正向)。

大多数实验具有一个稳定效应(常数均值),但高方差意味着需要收集足够数据来得到更好估计;早期结果通常会有误导。由于存在真实的Novelty effects或Primacy effects,对于一个统计显著负效应,最常见的方式是,随时间变得更负向;而对于一个统计显著的正效应,随时间变得更正向。对于在几周之后扩展(extend)那些统计显著负向的实验,是没有多大价值的。

3.4 实验长度(Experiment Length)和统计强度(Statistical Power)

3.4.1 背景

不同于大多数离线实验,在线实验(online experiments)会持续补充(recruit)用户,而非在实验之前具有一个补充期(recruitment period)。因此,sample size随着实验的运行越长会增加。因此,很自然地期望:运行一个实验越长,会提供关于treatment effect的一个更好的估计,也具有更高的statistical power。注意,对于一些指标,比如:Sessions/User,该均值会随实验运行的越久而增加,也会基于百分比变化计算power。

3.4.2 Puzzling Outcome

图6

图7

3.5 延滞效应(carryover effects)

3.5.1 背景

一些在线实验平台,包括:Bing、Google、Yahoo,依赖于“bucket system”来安排用户进行实验[3]。该bucket system会将用户随机化到不同的buckets中,接着安排buckets进行实验。这是个灵活的系统,允许对后验实验上对用户简单复用。

3.5.2 Puzzling Outcome

一个实验运行后,结果非常惊人。它通常是良好的,因为违反直觉的结果帮助我们理解新的ideas,但指标与在非预期方向的变化移动不相关,该效应(effect)是高度统计显著的。我们以一个更大的sample重新运行该实验来增加statistical power,许多该effect会消失。

3.5.3 解释

“bucket system”的一个大缺陷是,它具有carryover effects的缺点,受前一实验影响的相同用户,被用于接下来的实验中。这是已知的,可以运行A/A tests确认carryover effects,但当他们失败时,我们会失去能力直到我们对bucket assignment进行re-randomize。令人吃惊的是,craayover effect的持续时间(duration)。我们分享以下的两个示例。

图8

在首个示例中,我们在三个阶段(stages)上运行了该实验,其中,我们在47天的A/B实验之前,在user buckets上有一个7-day的A/A实验。在我们完成实验后,我们关掉实验,接着在接下来的三周上继续监控相同的user buckets。图8展示了在treatment和control之间,OEC(Sessions/User)上的日常百分误差(daily percent delta)。灰色bars表示三个stages的划分。

很明显在实验完成之后,在用户上有一个carryover effect。该carryover effect看起来会在实验之后的三周左右消失。

图9

在另一个示例中,如图9所示,用户在实验中曝出的一个bug,会引起较差用户体验。carryover effect会持续更长时间。即使在三个月之后,user buckets仍然没有恢复到之前实验的水平。

3.5.4 缓解技术

尽管carryover effect本身对于实验者很重要,但对于一个实验平台来说保证质量更重要,而非抵制它。在bucket system中,由于user buckets会会从一个实验进行回收利用到另一个实验上,任意carryover impact可以很容易对后续实验造成bias。

缓解该问题的一种方式是,局部随机化(local randomization)。造成carryover effect的一个根源是:bucket system没有对每个实验进行重新随机化(re-randomize)。整个bucket system会依赖于一个频次不高的bucket re-assignment来对polulation进行随机化,接着该bucket分配在相当长周期内仍不变(constant)。将用户重新随机化到bucket system可以通过变更hashing function来完成,但该bucket system会以一个“bucket line”或者“layer”[3]的方式将所有实验进行成对化(couple),这样,我们必须停止在该bucket line上所有运行的实验,并变更hashing function,这会伤害(capacity)和敏捷性(agility)。另一个可选方案是,使用一个two-level的bucket system,它可以提供局部随机化;也就是说,只在一个buckets子集上进行重新随机化(re-randomizing),但不需要影响其它buckets。

图10

上图展示了,局部重随机化是如何通过一个two-level bucket system来完成的。顶层的bucket system定义了包含在实验中的experiement units的一个集合,tratment assignment则在第二层bucket system中进行。对于每个experiment,第二层hashing会使用一个不同的hash seed。这保证了每一实验随机(per-experiment randomization),从而treatment的分配独立于任何历史事件,包括之前实验的carryover effects。上述方案的一个缺点是,我们不能使用一个共享的Control组:每个实验都需要它自己的Control,以便来自某一实验的任意carryover被“混合”到Control和Treatment(s)中。

局部随机化的一个好处是,我们可以运行一个“回顾式(retrospective)”的A/A 实验,无需实际占据总有效时间(calendar time)。通过对hashing function进行变更,在重启A/B实验之前,我们可以在前几天运行A/A实验进行评估。由于局部重新随机化的独立性,如果我们在实验之前对于任意周期回顾式地比较被分配到control和treatment组上的用户,该比较会是一个A/A。如果该A/A表明对于核心指标有影响,比如:p value < 0.2(由于划分的”unlucky”), 我们需要重新变更hashing key并进行重试。

参考:

Microsoft在KDD2007时的paper《Practical Guide to Controlled Experiments on the Web:Listen to Your Customers not to the HiPPO》中,对A/B testing系统设计有一些practical guide,可以参考一下:

3.controlled experiments

在最简单的受控实验(controlled experiment)中,通常指的是一个A/B test,用户会被随机曝光给两个variants之一:control(A)、treatment(B),如图2所示。

这里的关键点是:“random”。用户不能“随意(any old which way)”分布,没有因子可以影响该决策。基于收集到的observations,会为每个variant生成一个OEC。

例如,在Checkout示例(2.1节)中,OEC可以是转化率、购买单元数、收益、利润、期望生命周期值、或者它们之间的加权组合。

如果experiment的设计和执行是合理的,在两个variants间唯一一直不同的是:Control和Teatment间的变化,因此,任意在OEC上的差异必然会产生该assignment,这存在因果关系。

3.1 术语

  • OEC
  • Factor
  • Variant
  • Experimentation Unit
  • Null Hypothesis
  • Confidence level
  • Power
  • A/A Test
  • Standard Deviation (Std-Dev)
  • Standard Error (Std-Err)

3.2 Hypothesis Testing和Sample Size

为了评估一个treatment组与Control组是否不同,需要做一个统计试验(statistical test)。如果该test拒绝(reject)零假设(OEC是并没有差异),我们认为:一个Treatment是统计显著(statistically significantly)有差异的。

我们不会回顾statistical test的细节,因为他们在许多统计书籍中有描述。

我们要回顾下影响试验(test)的一些重要的因子:

  • 置信等级(confidence level)。通常设置为95%,该level表示:5%的机会是不正确的
  • 统计功效(Power)。通常在80-95%间,尽管不是直接控制的。如果零假设是false的(比如:在OEC上有差异), power表示决定该差异的概率,是统计显著的。(Type II error)
  • (Standard Error)。Std-Err越小,test越强。有三种方法减小std-err:
    • 被估计的OEC通常是大样本的一个平均。如3.1所示,一个均值(mean)的Std-Err会随着sample size的均方根按比例递减,因此,增大sample size(这通常意味着运行实验更久),可以减小Std-Err,从而增大power
    • 使用天然具有更小变动性的OEC components(例如:Std-Dev, ),std-err会越小. 例如,转化率(conversion probability 0-100%)通常比购买单元数目(通常是小整数)具有更低的Std-Dev,换句话说,它比收益(revenue: real-valued)具有一个更低的std-dev。
    • 通过过滤掉那些没有曝光给variants的用户,OEC的可变性会越低. 例如,如果你对checkout page做出一个变更,只分析访问该page的用户,由于每个人都增加了噪声(noise),会增加可变性(variability)
  • 4.the effect:对于variants来说在OECs上的差异。差异越大越容易检测,因此,great ideas不可能错过。相反的,如果Type I或Type II errors发生,当该effects很小时,他们更可能发生。

以下的公式近似期望的sample size,假设期望的置信level为95%,期望的power是90%(31):

其中:

  • n是sample size
  • r是variants数目
  • 是OEC的std-dev
  • 是OECs之间的最小差异
  • 4是因子,表示对于大的n会估计过高25%,但该近似会满足下面示例。

假设有一个电商网站,在实验周期期间,访问该网站的5%用户会以购买行为结束。这样的购买会花费大约75美金。用户的平均花费为3.75美金(95%的人没有消费)。假设:标准差(standard deviation)为30美金。如果你正运行一个A/B test,该test希望检测在收益上有一个5%左右的变化,基于上面的公式:,你将需要超过1600w用户来达到期望的90% power。

然而,如果只只希望在转化率(conversion rate)上检测一个5%的变化,基于3.b会使用一个可变性更低的OEC。购买(一个常见事件)可以被建模成一个p=0.05(购买概率)的伯努利实验(Bernoulli trial)。一个Bernoulli的Std-Err为,因此,基于公式,你需要至少50w用户来达到所期望的power。

由于平方因子的存在,如果目标放宽些,以便你希望在转化上(因子为4)检测一个20%变化,通过乘以一个16的因子来将用户数目下降到30400。

如果对checkout过程做出一个变化,你只需要分析那些启动checkout过程的用户,因为其它用户不能看到任何差异,只会增加噪声。假设10%的用户从checkout开始,并且其中有50%用户完成了它。该用户分片(user segment)是更同质的,因此OEC具有更低的可变性。正如之前使用相同的数子,平均转化率是0.5, std-dev是0.5, 因而基于,你需要25600个用户访问checkout来检测一个5%的变化。由于我们会将没有初始化的90%用户排除,访问该网站的总用户数应该是256000, 这几乎是之前结果的一半,因此实验可以运行一半时间,来生成相同的power。

当运行实验时,提前在OEC上做决定很重要;否则,会增加寻找有机会出现显著结果的风险(与type I error相似)。一些文献中也提出了一些方法,但他们基本上等同于增加95%的置信level,从而减小statistical power。

3.3 online settings的扩展

basic controlled experiments的一些扩展在online setting中是可能的。

3.3.1 Treatment Ramp-up

3.3.2 自动化(Automation)

3.3.3 软件迁移(software migrations)

3.4 限制

尽管根据因果关系提供的controlled experiments的优点显著,它们也有一些必须理解的限制。

  • 1.量化指标,但没有任何解释。我们可能知道哪个“variant”更好,以及好多少,但不知道“为什么(why)”。例如,在用户研究中,行为(behavior)通常会随用户评论(comments)而增加,因此可用性实验室(usability lab)可以用于增加和完善controlled experiments。
  • 2.短期效应(short term) vs. 长期效应(long term effects)。controlled experiments会在实验期间(通常数周)衡量OEC的effect。而一些paper作者则批评说:这样只会注某一指标意味着short-term focus,我们对此不赞同。long-term目标应该是OEC的一部分。假设我们以搜索广告为例。如果你的OEC是收益(revenue),你可能在一个页面上粘帖数个广告,但我们知道:越多广告会伤害用户体验,因此一个好的OEC应包含对于没有点击的房地产广告的一个惩项(penalty term),或/和 对重复访问和放弃的直接measure。同样的,查看一个延迟的转化指标是明智的,其中从一个用户被曝光某样东西到该用户做出动作这段时间内有个迟延(lag)。这有时被称为潜在转化(latent conversions)。找好好的OEC是很难的,但有什么替代方法吗?这里的关键是,认识到该限制。
  • 3.首效应(Primacy effects)和新效应(newness effects)。有一些负面效应需要认识。如果你在一个web网站上更换了导航,体验的用户可能更低效,直到他们完全适应了新导航,因而Control组会天然具有优势。相反的,如果一个新设计或新特性被引入,一些用户可能会研究它,到处进行点击,从而引入一个“newness” bias。该bias有时会与霍索恩效应(Hawthorne effect)相关。Primacy和Newness这两者意味着:一些实验需要运行多周。可以做个分析:为不同variants上的新用户计算OEC,因为他们不会受两个因素影响。
  • 4.必须实现的特性。一个真实的controlled experiment需要曝光一些用户给一个Treatment,不同于当前站点(Control组)。该prototype可能是个prototype,它可以在很小比例上进行测试,或者不会覆盖所有的边缘情况(edge cases)(例如:实验可能故意排除20%的需要显著测试的浏览器类型)。尽管如些,该特性必须被实现,并曝光给用户足够的量。Jacob(34)正确指出:paper prototyping可以被用于在早期定性反馈和快速改进设计。我们赞同并推荐这样的技术来完善controlled experiments。
  • 5.一致性(consistency)。用户可能注意到:比起它们的朋友和家人,他们获得了一个不同的variant。也有可能是一些相同的用户当使用不同电脑(具有不同cookies)看到多个variants。这相对比较罕见:用户会注意到该差异。
  • 6.并行实验(Parallel Experiments)。我们的实验实际上很少发生很强的交叉(33),我们认为这一点是过度关注了。提升对这一点的关注对于实验者来说足够避免交叉(interact)的测试。成对的统计测试(statistical test)也可以完成,来自动标记这样的交叉(interactions)。
  • 7.启动事件和媒体公告。如果对新特性做出一个大的公告,(比如:该特性通过媒体进行公告),所有用户需要看到它。

第4部分来自另一paper。

4.多因子实验(Multi-Variable Testing)

一个包含了超过一个因子(factor)的实验通常被称为:MultiVariable test(MVT)。例如,考虑在MSN主页上在单个实验中测试5个factors。MSN主页截屏如图8所示,为每个factors展示了control。

表二:

在单一测试中,我们可以估计每个factor的效果(main effects),以及多个factors间的交叉效果(interactive effects)。首先,我们会考虑:MVT vs. one-factor-at-a-time (或者A/B tests)的好处和限制。接着我们会讨论对于online MVTs的三种方法,以前每种方法会利用潜在好处并缓和该限制。

对于测试相同factors的single MVT vs. 多个sequential A/B test,MVT主要有两个好处:

  • 1.你可以在一个较短时间内测试许多factors,加速提升。例如,你想测试在网站上的5个变化,你需要每个A/B test运行4周时间来达到你需要的power,它会至少需要5个月来完成A/B tests。然而,你可以使用所有5个factors来运行单个MVT,它只需要1个月就可以达到5个A/B tests相同的power。
  • 2.你可以估计factors间的交叉。两个factors的交叉,如果它们的组合效应与两个单独的effects叠加不同。如果这两个factors一起可以增强结果,那么该交叉(interaction)是协同的(synergistic)。如果相反的,他们相互抵触会抑制该效果,该交叉(interaction)是对抗的(antagonistic)。

三个常见限制是:

  • 1.一些factors的组合可能会给出一个较差的用户体验。例如,对于一个在线零售商来说,正在测试的两个factors可能是:增加一个商品的图片 or 提供额外的商品详情。当单独进行测试时,两者分别均会提升销售,但当两者在同时完成时,“buy box”会被推到折叠(fold)下面,这会减小销售。这就是一个大的对抗交叉(antagonistic interaction)。该交叉在计划阶段(planning phase)可以被捕获,以便这两个factors不会被同时测试。
  • 2.分析和解释是更困难的。对于单个factor的test,你通常具有许多指标来进行Treatment-Control的比较。对于一个MVT,你需要为多个Treatment-Control比较设置相同的matrics(对于每个测试的factor至少要有一个),以及在factors间交叉的分析和解释。确定的是,该信息集越丰富,对于treatments的评估也越复杂。
  • 3.它会花费更长时间开始测试。如果你具有希望测试的5个factors,并计划以一次测一个的方式测试它们,你可以启动任意待测的,接着测试其它的。使用一个MVT,你必须在test开始之前,具备所有5个准备好的testing。如果任何一个延误了,会延误test的启动。

我们不认为:在大多数情况中任意的限制(limitations)是严重的限制,但在进行一个MVT之前应意识到它。通常,我们相信,第一个实验确实会是一个A/B test,主要是因为在相同的test中测试多个factor的复杂性。

有三种哲学来处理在线 MVTs.

4.1 传统MVT

该方法所用的设计被用于制造业(manufacturing)和其它离线应用。这些设计大多数通常是部分因子(fractional factorial)以及Plackett and Burman designs,它们是完全因子设计(所有factor levels上的组合)的一个特定子集。这些设计由Genichi Taguchi普及,有时被称为“田口设计(Taguchi designs)”。用户必须小心选择一个设计,它可能具有足够估计主效应和所关注的交叉效应。

对于我们的MSN示例,我们展示了一个包含了5个factors的test设计,它使用完全因子(full factorial),部分因子(fractional factorial) or Plackeet-Burman design。

表1.

完全因子会具有factors的所有组合:个user groups。部分因子(factional factorial)则是完全因子的一个部分,它具有个user groups,每一列与其它4列是正交的(orthogonal)。很明显,许多这样的factions具有8-16个user groups。K=3的部分因子(fractional factorial)如表1所示,-1表示control,1表示treatment。

如果factors是在2 levels上,Plackett–Burman designs可以被构建,user groups的数目可以是4的倍数,比如:4,8, 12, 16, 20等。对于任意这种designs来说,可以被测试的factors数目是user groups的数目减去一。如果user groups的数目是一个2的power,那么该Plackett–Burman design也是一个部分因子(fractional factorial)。

由于使用了部分因子(fractional factorial),对于一个给定数目的user groups,通常会使用许多Plackett–Burman designs。

在实验设计的统计领域,一个主要研究领域是:寻找这样的设计,它可以最小化用于test所需的user groups数目,同时允许你估计主效应和交叉效应,允许小量或没有混杂(confounding)。表1的fractional factorial 可以估计所有5种main effects,但不能很好估计interactions。对于许多实验来说,运行MVT的主要原因之一,估计要测试的factors间的交叉(interaction)。使用该设计,你不能很好地估计任何交叉,因为所有交叉都是与main effects或two-factor interactions相混淆的。即使在分析或数据挖掘上花再大精力,也不能让你单独估计这些interactions。如果你想估计5个factors中的所有two-factor interactions,你需要一个具有16个treatment combinations的 fractional factorial design。表2的Placket–Burman design具有所有two factor interactions,部分会与main effects和其它two-factor interactions相混杂(confound)。这使得two factor interactions的估计充满挑战。

对于online tests来说,对比传统的MVT方法,我们推荐另外两种更好的可选方法。你喜欢的一种将会依赖于:你对估计interactions的评价有多高。

4.2 并行运行tests的MVT

在offline testing中,可以使用完全因子(full factorial)的部分,因为使用更多treatment组合通常有个开销,即使experimental units的数目没有增加。这不一定是与网站相关的test。如果我们设置了每个factor来运行一个one-factor实验,并同时运行所有的tests,我们可以简化我们的工作,最终获得一个完全因子(full factorial)。在该模式中,我们同时在相同的用户集合上(用户会被独立随机分配给每个实验)开始和停止所有这些one-factor tests。最终结果是在所有要测试因子上你将具有一个完全因子实验。当然,在完全因子上,你可以估计任何你想要的交叉。该方法的一个边缘优点是,你可以在任何时间关闭任何factor(例如:如果对于某一factor的一个treatment是灾难性的)不会影响其它factors。包含剩余factors的实验不会被影响。

通常会认为:实验的power会随着treament组合(cells)的数目增加而减少。如果该分析是基于每个单独的cell与Control cell相对比得出,那么这个观点可能是true的。然而,如果分析是基于更传统的方式(为每个effect使用所有数据来计算main effects和interactions),power则不变或减小很少。如果sample size是固定的,它不会影响你正测试单个factor或多个factor。。。有两件事件可以减小你的power。一是对于某一factor增加levels(variants)的数目。这对于你想做出的比较来说,会有效减小sample size,不管test是一个MVT或一个A/B test。另一个是分配少于50%的test polulation到treatment(如果它们是two levels)。在一个MVT中,需要与Control具有相同比例的population,这对于treatment来说这特别重要。

4.3 Overlapping实验

该方法会简单测试一个actro作为一个one-factor实验,当该factor准备与每个独立随机化的test一起被测试时。它与4.2节不同,这里当treatment准备进行每个实验会开启,而非一次性加载所有factors。在一个敏捷软件开发世界中,频繁运行更多的tests有极大好处,因为他们准备进行部署。如果带这些组合的tests上没有明显的用户体验方面问题,这些tests可以同时同步进行,可以展示给任何用户。如果你想最大化你想测试的ideas的速度,并且你不关心交叉(interactions),你可以采用这种方法。factors间的大交叉实际上比大多数人相信的要少很多,除非是已知的,比如:buy box示例。比起之前提到的traditional方法,这是一种更好的替代方法。在传统方法中有这样的限制:必须所有factors都准备好进行测试时你才能进行test。另外,当你完成时,你不能很她地估计交叉。有了overlapping experiments,如果在任何两个factors有足够的overlap,你可以更快速的测试factors,另外你可以估计这些factors间的交叉。如果你特别关心两个特定factors间的交叉,你可以同时计划测试这些factors。

我们相信,这两种方法比传统的MVT方法更适合online实验。如果你想尽可能快地测试你的想法,并且不关心interactions,可以使用overlapping experiments方法。如果同时运行实验时估计交叉很重要,用户可以被独立随机化到每个test中,并给你一个完全因子实验。

5.实验架构

在一个网站上实现一个实验,涉及到两个部分。第一个component是:随机算法(randomization algorithm),它是一个将users映射到variants的函数。第二个component是分配方法(assignment method),它使用随机算法的output来决定每个用户是否能看到该网站的实验。在实验期间,必须收集observations,数据需要被聚合和分析。

5.1 随机算法

寻找一个好的随机算法很重要,因为controlled experiments的统计,会假设:一个实验的每个variant都具有关于users的一个随机抽样。特别的,随机算法必须具有以下4个特性:

  • 1.用户必须等可能地看到一个实验的每个variant(假设:50-50 split)。对于任意指定variant必须是无偏的(no bias)。
  • 2.对于单个user重复分配(repeat assignments)必须是一致的(consistent);在对该网站的每次后续访问上,该user必须被分配到相同的variant上。
  • 3.当多个实验同时并行运行时,实验之间必须没有关联(correlation)。在一个实验中,一个user被分配(assignment)到一个variant,对于被分配给其它任意实验的一个variant,在概率上没有影响
  • 4.该算法必须支持单调递增(monotonic ramp-up),这意味着,如果没有对那些已经被配给Teatment的用户分配进行变更,用户看到一个Treatment的百分比可能会缓慢增加。

5.4.1 使用caching的伪随机

当组合使用caching时,可以使用标准伪数字生成器(standard pseudorandom number generator)作为随机算法。一个好的伪数字生成器会满足关于随机算法的第一和第三个要求。

在第一和第三要求上,我们测试了一些流行的随机数字生成器。我们在100w序列化user IDs上测试了5个仿真实验。运行卡方检验(chi-square)来检索交叉(interactions)。我们发现,只要生成器的seed只在server启动时初始化一次,在许多流行语言(例如:C#)内置的随机数字生成器可以运转良好。在每个请求上对随机数字生成器进行Seeding会造成:相邻的请求会使用相同的seed,这会在实验(experiements)间引入显著相关性(noticeable correlations)。特别的,我们发现,Eric peterson建议使用VB的A/B test代码,会在实验间创建很强的two-way interactions。

为了满足第二个要求,该算法必须引入状态(state):用户的分配必须被缓存,以便他们再次访问该网站。缓存的完成可以是服务端(通过数据库进行存储),也可以是客户端(例如:将user的assignment存到cookie中)。

两种形式都很难扩展到一个具有大量servers的大系统上。server做出随机分配,必须将它的state与其它servers(包括使用了后端算法的那些)进行通信,以便保持分配一致。

使用该方法时,第4个要求(单调递增)特别难实验。不管使用哪种方法来维持状态(state),,会在一个ramp-up之后,该系统需要将Control users(访问该网站的这些用户)重新分配给一个treatment。我们还没有见过一个使用基于伪随机分配(pseduorandom-based assignment)的系统是支持ramp-up的。

5.1.2 Hash和分区

不同于伪随机方法,该方法的完成是无状态的。每个user会被分配一个唯一的id,它可以通过database或cookie来维持。该id会被附加(append)到该experment的name或id上。接着在该组合id上使用hash函数来获得一个integer,它在数值范围内是均匀分布(uniformly distributed)的。该range接着被进行划分,每个variant通过一个partition进行表示。

该方法对于hash函数的选择非常敏感。如果hash函数具有任意的漏斗(funnels)(那些相邻keys的实例会映射到相同的hash code上),那么这会与第一个特性(均匀分布)相冲突。如果hash函数具有characteristics(某个key的变动会产生一个在hash code上可预测的变动),那么实验之间会发生相关。在该技术上,只有很少的hash函数够资格使用。

我们使用许多流行的hash函数、以及一种类似于伪随机数字生成器的方来测试该技术。任意hash函数都会满足第二个要求,但满足第一和第三是很困难的。我们发现,只有加密hash函数MD5生成的数据在实验间没有相关性。SHA256(另一个加密hash)接近,需要一个five-way interaction才会产生一个相关。.NET的string hashing函数则会在一个2-way interaction test上会失败。

5.2 Assignment方法

Assignment方法是软件的一部分,它允许正实验的网站对于不同的用户执行不同的代码路径。有许多方法来实验一个assignment方法,优点和缺点各不同。

流量分割(Traffic splitting)

该方法会涉及到:一个experiement的每个variant在不同的servers的实验,分为物理(physical)和虚拟(virtual)。该网站会将随机算法嵌入到一个负载均衡器(load balancer)或代理服务器(proxy server)中以便对variants间的流量进行分割。流量不能对已存在代码进行变更来实现一个experiment。然而,对于跨所有正运行实验的variants的每个唯一组合来说,该方法需要为它进行一个并行fleet的setup和config,这使得该方法在处理assignment时代价很大。

另一种可选的方法是:服务器端选择(server-side selection),API调用会嵌入到网站的servers中来调用随机算法、并使得分枝逻辑对于每个variant处理一个不同的用户体验。Server-side selection是相当通用的方法,它在一个网站的任一部分可以支持多个实验,从可视化元素到后端算法。然而,从一个开发者实现代码变更到运行实验,这个过程需要额外工作。

最终的可选方法是:客户端选择(client-side selection),JavaScript调用会嵌入到每个web页上,会进行一个远端服务进行分配,并能动态修改页面来产生合适的用户体验。client-side实验通常要比server-side更容易实现,因为开发者只需要将javascript代码嵌入到每个页面上。然而,该方法会严重限制实验的特性;特别的,关于动态内容实验或者后端特性的实验更难实现。

6.学到的课程

理论和实际是不同的。

许多理论技术看起来很适合实际使用,但需要十分小心,以防止污染真实环境。Controlled experiments也不例外。关于运行大量在线实验,我们在三个方面的实际经验分享:

  • (i) 分析
  • (ii) trust & execution
  • (iii) culture & business

参考: