d0evi1 Reading time ~1 minute

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可以被分解成三个项相乘：

\[\frac{Users}{Month} \times \frac{Sessions}{User} \times {Distinct \ queries}{Session}\]

…(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 解释

对于许多指标来说，均值的标准差与\(1/\sqrt{n}\)成正比，其中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并进行重试。

参考：

d0evi1 Reading time ~2 minutes

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, \(\delta\)），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 = (4r\delta / \Delta)^2\]

其中：

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

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

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

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

如果对checkout过程做出一个变化，你只需要分析那些启动checkout过程的用户，因为其它用户不能看到任何差异，只会增加噪声。假设10%的用户从checkout开始，并且其中有50%用户完成了它。该用户分片（user segment）是更同质的，因此OEC具有更低的可变性。正如之前使用相同的数子，平均转化率是0.5, std-dev是0.5, 因而基于\((4 \cdot 2 \cdot \sqrt{0.5 \cdot (1-0.5)} / (0.5 \cdot 0.05))^2\)，你需要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的所有组合：\(2^5=32\)个user groups。部分因子（factional factorial）则是完全因子的一个部分，它具有\(2^K\)个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

略

参考：

d0evi1 Reading time ~4 minutes

google在google+这个产品上提出了《Improving User Topic Interest Profiles by Behavior Factorization》，我们来看下具体实现：

1.介绍

2.相关工作

2.1 构建user profiles

对于许多用户而言，社交媒体上共享的信息是过饱和的。因此，主题兴趣画像(topic interest profiles)的构建是个性化推荐系统中很重要的一部分。我们的工作受关于利用行为信号的个性化研究的启发。

搜索引擎研究者已经利用user profiles来提供个性化搜索结果【9,11,4,30,35】。通常，user profiles会被表示成一个在高维空间中的向量，这些向量表示了在不同items上的用户偏好（比如：网页、电影、社交媒体posts），或者在不同空间上的用户偏好（例如：表示主题的关键词、或来自类目树taxonomy的主题类别）

2.1.1 MF & Embedding模型

推荐方法的一大类是CF，系统通常会使用一个user-by-item矩阵，每个条目表示用户在一个相应item上的评分。因此，在输入矩阵中的某一行表示：一个特征用户对items的偏好。关于一个用户在一个指定item上的未知偏好，可以使用矩阵补全（matrix completion）来进行推断（infer），研究者们已经使用MF方法取得了巨大进展。

在我们的paper中，我们并没有使用通过items（发表：posts）偏好来表示user profile的方法，我们更关注对user的主题兴趣(topical interests)进行推断，其中主题通过Google知识图谱的条目进行表示（比如：”basketball”、’video games’）。研究者已经使用MF来创建embedding模型，或者生成式模型（如：LDA）来构建user profiles[21]。MF以及生成式模型可以学到latent embedding空间，其中偏好可以通过user和item间的latent embedding factors的相似度进行计算。

比起item-based方法，topic-based方法在社交媒体中更加可扩展，其中实际items（posts）数目会很大。做为替代，通过计算在user topic兴趣和item(post)兴趣间的相似度，我们可以预测在一个item上的一个用户的兴趣。

2.2 社交媒体的个性化user profiles

正如在其它推荐问题上一样，社交媒体研究者通常将构建一个user profile看成是构建一个个性化推荐系统的首要任务。研究者在社交媒体上已经应用MF和生成式模型(LDA)来建模user-topic矩阵，并专门构建了user profiles[8,7,34,3,6,15,33,27]。例如，Guy等人基于content和item的偏好来构建user profiles，接着为社交媒体items（比如：书签和社交软件）来提供个性化推荐[8,7]。Chen等人在twitter上构建了user topic profiles并提供了会话的个性化推荐。User profile也被用于提供好友推荐[6]，社群推荐[33]，动作推荐（mentioning推荐[33], commenting[27]）。

对于一个user profile来说，用户偏好可以使用隐式反馈（比如：用户活动）进行infer[8]。作为对比，在传统推荐系统中，CF通常需要显式评分，这会带来用户的额外开销。例如，Hu等人提出了一个MF方法来利用稀疏数据的隐式反馈。在该思想基础上，Noel等人在MF上提出了一个新的目标函数，并考虑上在feature-based相似度、以及user-user信息。

2.3 上下文个性化

社交媒体平台提供了用户丰富的上下文信息，比如：用户在何时（when）对某用户发表（who’s post）的某主题（what topic）进行了web评论。许多最近研究讨论了如何利用这些丰富的上下文来学习更好的user profiles。Singh等人提出的CMF（协同矩阵因子分解），目标是使用上下文信息来在异构网络上提供推荐。与该工作比较接近的有：

  • (a) Liu提出了 a social-aided context-aware recommender systems for books and movies. 会利用丰富的上下文信息来将user-item矩阵划分为多个矩阵[20]
  • (b) Jamali等人提出了: a context-dependent matrix factorization model to create user profiles for recommendation in social network [14]。

除了矩阵分解技术外，研究者提出了context-aware generative models来在Twitter上帮助创建user profiles和隐语义模型[25,32,36]。例如，Zhang等人使用生成模型提出了一个two-step framework来首先发现不同的主题域，接着使用MF方法在每个域上提供推荐[37]。不同用户可能对不同领域感兴趣，与我们工作相关，但在用户行为上有些区别。我们主要关注：每个用户的主题兴趣是如何通过不同类型的行为进行划分的。

研究者们已经使用内存来构建和提升user profiles。Li等人提出了一种 transfer learning方法来对两个领域的两个向量，使用相互间的信息进行因子分解[18]。Hu等人提出了一个三元因子分解（triadic-factorization-based）方法来对user-item-domain的tensor进行因子分解，来提供跨领域的个性化推荐。

2.4 行为因子分解

“如果你将知觉（perception）看成是一种联系（contact）和洽谈(communion)的方式，那么，支配感知就是支配联系，限制和管理感知就是限制和管理联系。”—Erving Goffman, The Presentation of Self in Everyday Lif.

最近工作表明，多种上下文可以提升user profiles的质量。在我们的paper中，展示了社交媒体用户具有不同类型的行为与不同主题进行交互，我们应使用行为类型看成是一种重要的上下文。我们也会为不同行为类型构建多个user profiles，接着在不同行为独立的推荐中，灵活使用这些不同的profiles。例如：推荐阅读(read)的内容，推荐分享(reshare)的内容。等

社会学家表明，人们在他们的每一天生活中，会呈现不同的画面给其它人；他们每天的对话会以不同主题展开，具有不同的听众。社交媒体的出现吸引了社会学家的兴趣，他们在网络社群上研究了该现象。例如，社会学家建立了这样的理论：由于用户对于在公开社交媒体上的准确受众（exact audiences）没有清晰看法，他们的行为具有模糊上下文边界[22]。然而，由于不同类型的行为，比如：发表（posting）和评论（commenting），会影响非常不同的受众，我们以下的分析建议，用户在社交媒体上仍会展示出不同的“身份（’identities’）”，以及对不同的主题展示不同类型的行为。通过定量研究，Zhao等人指出：用户体验社交媒体平台（比如：Facebook），与现实中的多种身份相似。据我们所知，我们的paper是首次提出：用户在一个社交媒体上利用不同的在线表示。

3. google+行为分析

我们分析了在google+上的匿名用户在线行为。我们首先抽取了在发表（posts）上的主题条目作为我们的特征，来为每个post构建特征向量。对于每个用户在posts上的行为动作，我们会聚合post对应的feature vectors来为每个用户-行为组合(user-behavior combination)构建一个entity vector。接着，我们对这些user-behavior entity vectors表示的不同的主题兴趣进行粗粒度的measure。我们展示了在这些向量间存在很大的不同，这启发了我们利用行为因子分解来建模不同的行为类型。

3.1 数据集描述

使用了2014 五月的google+用户公开行为来进行分析。我们在所有公开发现上分析了所有用户行为，每条记录被表示为一个tuple：(u,b,E)，其中一个用户u（具有一个匿名id）使用行为b来参与一个包含了实体集合E的post。有4种类型的行为：发表（post），分享（reshare）、评论（comment）、+1.

我们会使用google知识图谱的实体形式（它包含的概念有：computer algorithms, landmarks, celebrities, cities, or movies.）来抽取更高级的语义概念，而非使用更低级向量（比如：word tokens）。它当前包含了5亿实体，在主题覆盖上提供了广度与深度。

我们基于标准的实体识别方法（利用实体间的共现先验，实体间的相关度似然，实体在文本中位置，接着最终对实体主题进行最终排序），使用一个实体抽取器。

对于给定的一个post，我们使用相应的知识图谱实体作为特征来表示它的主题。因此，在input tuple(u,b,E)中每个E是一个关于知识图谱实体的集合。例如，如果一个用户\(u_1\)创建了一个关于宠物狗图片的post，与该行为对应的是：(\(u_1\), CreatePost, {“Dog”, “Pet”, …})。如果另一个用户\(u_2\)在一个关于Xbox Minecraft的youtube视频post上进行了评论，该行为对应于该tuple：(\(u_2\), Comment, {“Minecraft”, “Xbox”, …})。

3.2 衡量行为间的不同

对于每个user，我们会使用一个特定类型行为来从他交互的posts中聚合实体。最后，对于每个用户，我们对应于4种不同类型的行类会获得4个主题实体集合。

我们接着使用Jaccard相似度来衡量集合间的不同。

t1.png

表1: Average Jaccard similarity between pairs of behavior types

在我们计算了每个用户不同行为的jaccard相似得分后，我们接着在所有用户上对分数进行平均。我们过滤掉了：小于10个实体的用户认为是不活跃。表1展示了平均jaccard相似度的结果。我们可以看到，任意两种行为类型间的平均jaccard系统很低。以comment和+1行为为例，在这两种行为间只有9%的主题重合。我们也衡量了用户的发布(publishing)和消费(cosuming)行为上的不同。我们会将用户comment和+1行为的实体组合成一个consuming实体集合，我们将create post和reshare行为的实体组合成一个publishing实体集合。平均jaccard index为0.122. 关于jaccard得分的低重合率表明：用户在不同行为上差异很大。

3.3 讨论

结果分析表明，对于每个用户，他通常在每个行为上具有不同的主题兴趣。也就是说，她通常会在create posts上的主题与comments上的主题会很不同。结果表明，常见的无指定行为（non-behavior-specific）的user profiles可能会在那些强调不同行为类型的应用上执行效果差。

内容推荐者通常会对用户要消费的内容进行定向预测，它可能会受行为（comment和+1）的影响要更好。在其它上下文中，我们会替代预测：用户会创建什么主题的posts。因此，通过为每种行为类型创建主题偏好，特定行为的user profile在不同的推荐上下文上具有更好的效果。

总之，用户在社交媒体上的不同行为包含了重要的上下文信息，它可以帮助我们提升用户个性化profiles上的效果。我们展示了，用户在G+上不同的行为类型会极大影响不同的主题兴趣，使用单独的行为类型构建不同的profiles允许我们为不同的行为上下文定制内容推荐系统。

4.问题定义

4.1 输入行为信号

我们不会为每个用户构建单个profile，相反的，我们提出了为一个用户构建多个profiles来表示它的不同行为类型。特别的，这里我们将社交媒体上的posts行为作为输入，输出一个主题兴趣向量集合来表示每个用户的不同类型的profiles。

给定一个用户集合\(U\)，不同的行为类型\(B\)，以及一个可以表示社交媒体内容\(E\)的特征集合，输入数据可以被表示成：

\[I = \lbrace t_i = (u_i, b_i, E_i), i=1, ..., N \rbrace\]

其中\(u_i \in U, b_i \in B, E_i \subset E\)。

  • 每个\(t_i\)表示一个用户在社交媒体内容的某个特定片段上的动作。例如，一个\(t_i\)可以是：创建一个post，或者对某个post进行comment。
  • \(E_i\)是该post的特征集合。

这里由于我们正构建user topic profiles，我们使用Google知识图谱的实体作为我们的特征集。然而，总体上，\(E\)可以是任意low-level（例如：words）或high-level的特征（例如：其它实体，或地理位置特征）。

4.2 User profiles

我们将user profiles定义成在特征空间E中的向量集合：

\[B = \lbrace P_u = \lbrace V_{u_B} \rbrace \rbrace\]

其中，\(u \in U, B \subset B\)，

  • \(P_u\)是用户u的user profile，
  • \(V_{u_B}\)是用户u在对应于她的行为类型B上的偏好向量。

\(P_u\)可以被认为是一个user tensor。

B即可以是单个行为类型（例如：创建一个post），或是一个不同行为类型的组合（例如：创建一个post和reshare一个post组合）。准确表述为：

\[V_{u_B} = ( p_{u_B}^{e_1}, p_{u_B}^{e_2}, ..., p_{u_B}^{e_k} ), e_j \in E\]

其中，对于j=1,…,k，\(p_{u_B}^{e_j}\)是用户u的行为类型 B在特征\(e_j\)上的偏好。

5.我们的方法

1.png

图1: 生成矩阵和因子分解框架

我们引入了行为因子分解法来为个性化推荐构建user profiles，它包含了三个steps，如图1和2所示。

  • step 1: 给定第4节中定义的input user action tuples \(I\)，我们首先构建不同行为类型的矩阵。这对应于图1中的左部分。
  • step 2: 我们对step 1中生成的矩阵进行因子分解来学到latent embedding space。这对应于图1中的右部分。
  • step 3: 最后，我们使用学到的latent space来对兴趣主题做预测来构建user profiles。这会为每个用户u创建profiles \(P_u = \lbrace V_{u_B} \rbrace\)。这对应于图2.

2.png

图2: 使用latent embedding space构建user profiles

我们会轮流做介绍。

5.1 step 1: 为不同行为类型构建矩阵

在常见的矩阵因子分解技术中，输入的user-item矩阵R被表示成一个\(N \times K\)的矩阵，其中N表示user的数目，K表示items的数目。R被分解成两个矩阵的乘积，矩阵X (\(N \times L\))，矩阵Y（\(K \times L\)）。换句话说，R中的行向量和列向量被映射到一个L维的latent embedding space中。有了这个学到的隐向量，对于在user-item矩阵中任意观察到的行向量，学到的embedding空间可以被用于帮助完成特定的行向量来补全一个用户在items上的估计偏好。

由于我们正构建user-topic-based profiles，我们使用users在主题的兴趣（\(N \times K\) user-topic matrix）作为输入，而非将users在items上的兴趣（\(N \times K\)的user-item matrix）作为输入。

另外，除了使用一个\(N \times K\)矩阵作为输入之外，我们构建和因子分解得到多个矩阵，包括：

  • (a) 传统的\(N \times K\)矩阵，被称为Behavior Non-specific User-topic Matrix(BNUM)
  • (b) Single Behavior-Specific User-topic Matrix(SBSUM)
  • (c) Combined Behavior-Specific User-topic Matrix(CBSUM)

5.1.1 BNUM (Behavior Non-specific User-topic Matrix)

这里，每个条目表示一个用户在特定主题上的隐式兴趣。给定输入用户tuples \(I=\lbrace t_i = (u_i, b_i, E_i), i=1, 2, ... \rbrace\)，我们首先引入涉及用户u的tuples \(I_u\)：

\[I_u = \lbrace t_j = (u_j, b_j, E_j) \rbrace, t_j \in I \wedge u_j = u\]

接着，我们为每个user和topic pair生成观察值：

\[r_{ui} = r(I_u, i)\]

也就是说，我们首先抽取所有涉及用户u的tuples \(I_u\)，在给定用户u涉及主题i的tuples下，使用函数r来计算隐式兴趣。该函数有许多可能的形式，对于不同行为可以训练不同的权重。我们使用以下的等式做为baseline来计算隐式兴趣：

\[r_{ui} = \frac{(\sum\limits_{I_u} \sum\limits_{e \in E_j} \sigma_i(e)) + 1}{(\sum\limits_{I_u} \| E_j \|) + (\|\cup_{I_u} E_j\|)}\]

…(1)

如果i=e，\(\sigma_i(e)\)为1; 否则为0. 也就是说用户u对主题i的隐式兴趣，可以通过i在所有用户u行为上的出现次数，除以所有items的出现总和来计算。我们会使用additive smoothing来对该值进行平滑。

5.1.2 SBSUM (Single Behavior-Specific User-topic Matrix SBSUM)

SBSUM和CBSUM将行为类型单独划分来生成独立的user-topic矩阵。给定一个行为类型的特征集合\(B \subset B\)，我们想构建矩阵\(R_B = \lbrace r_{ui}^B \rbrace\)，其中每个条目表示从B中行为类型得到的隐式兴趣。

我们使用与等式(1)的相同方法，但增加了限制来过滤不在B中的行为类型：

\[r_{ui}^B = \frac{(\sum\limits_{I_u \wedge b_j \in B} \sum\limits_{e \in E_j} \sigma_i(e)) + 1}{ \sum\limits_{I_u \wedge b_j \in B} \| E_j \| ) + (\|\cup_{I_u \wedge b_j \in B} E_j \|)}\]

…(2)

对于每个B，使用该等式，我们可以构建一个矩阵，它使用B中的行为类型来表示用户观察隐式反馈，可以被设置成单个行为类型，或是多个行为类型集合。因此，基于B选择，我们可以构建两个类型的特定行为user-topic矩阵(BSUM)：SBSUM, CBSUM。

首先，我们为每个行为类型构建了一个user-topic矩阵，比如：creating post，resharing，commenting或+1. 每个矩阵的条目是观察值\(r_{ui}^B\)，它通过等式(2)计算，其中B是单个行为。给定\(B = \lbrace b_1, b_2, ..., b_M \rbrace\)为所有行为类型集合，我们生成以下M个SBSUM:

\[\begin{cases} R_{b_1} = \lbrace r_{ui}^B \rbrace, B=\lbrace b_1,b_1 \in \mathscr{B} \rbrace \\ R_{b_2} = \lbrace r_{ui}^B \rbrace, B=\lbrace b_2,b_2 \in \mathscr{B} \rbrace \\ ... \\ R_{b_M} = \lbrace r_{ui}^B \rbrace, B=\lbrace b_M,b_M \in \mathscr{B} \rbrace \end{cases}\]

…(3)

5.1.3 CBSUM（Combined Behavior Specific User-topic Matrix）

在构建SBSUM时，我们创建了M个矩阵，每个表示单个行为类型。然而，我们也希望捕获多种行为类型组合的主题兴趣。例如，在G+中，creating post和resharing posts会生成内容并广播给所有followers，这两种行为类型可以组合在一起来表示用户的发表（publication）。

同时，commenting和+1两者表示用户对post的消费行为。将两者组合在一起可以表示关于用户消费（consumption）的主题兴趣。因此，给定行为类型集合，每个集合是B \(\lbrace B_1, B_2, ..., B_p \rbrace\)的一个子集，我们构建了P个矩阵，每一个均表示用户的组合行为：

\[\begin{cases} R_{B_1} = \lbrace r_{ui}^B \rbrace, B=\lbrace B_1,B_1 \in \mathscr{B} \rbrace \\ R_{B_2} = \lbrace r_{ui}^B \rbrace, B=\lbrace B_2,B_2 \in \mathscr{B} \rbrace \\ ... \\ R_{B_M} = \lbrace r_{ui}^B \rbrace, B=\lbrace b_M,b_M \in \mathscr{B} \rbrace \end{cases}\]

…(4)

5.2 step 2: 学习latent embedding space

这里我们引入了一个矩阵分解（MF）技术来构建用户的主题画像(topic profile)作为baseline方法。另外，我们引入了我们提出的方法，它将baseline算法扩展成行为因子分解。

5.2.1 baseline: MF

在构建BNUM后，我们会学习一个latent embedding space，它可以被用于补全observed user-topic matrix来获得预测的user-topic偏好。在推荐研究中，在学术界和工业界有许多方法尝试改进MF技术。这里我们使用hu[13]提出的因子分解技术。

采用[13]有一个非常特别的原因。在社交媒体平台上，对于大多数用户来说，隐式兴趣信号更容易获取。然而，许多推荐算法并没有考虑显式兴趣 vs. 隐式兴趣信号间的潜在不同。在user-item矩阵上有效的所有其它MF方法，可以被应用到我们的框架中，来使用行为因子分解（behavior factorization）构建user profiles。注意：在后续讨论中，user-topic矩阵中的”topic”与user-item中的item相似。

给定从\(r_{ui}\)的隐式兴趣中观察到的user-item矩阵，Hu[13]将观察集划分成两个变量：偏好\(p_{ui}\)、置信度\(c_{ui}\)。这里\(p_{ui}\)是一个二值变量，它表示用户u是否对item i感兴趣：

\[p_{ui} = \begin{cases} 1 , r_{ui}>0 \\ 0 , r_{ui}=0 \end{cases}\]

置信度\(c_{ui}\)表示对偏好\(p_{ui}\)的置信等级。它表示你对兴趣值有多肯定。它可以通过以下方式进行计算：\(c_{ui} = 1 + \alpha r_{ui}\)。

接着，该算法会学到一个latent embedding space，它会将每个user u和item i映射到该空间上（对应于\(x_u\)和\(y_i\)）。为了学习该空间，算法会尝试解决以下的最优化等式：

\[\min\limits_{x_*,y_*} \sum\limits_{ui} c_{ui} (p_{ui} - x_u^T y_i) ^ 2 + \lambda( \sum\limits_{u} \| x_u \|^2 + \sum\limits_i \| y_i \|^2)\]

…(5)

结果\(x_u\)和\(y_i\)可以被用于补全user-item矩阵，它会估计一个user会喜欢一个item有多喜欢。[13]提出的算法对于隐式feedback/interest datasets工作良好。

在这一点上，我们使用等式(1)来构建user-topic矩阵，采用MF来学习一个latent embedding space。再者，我们可以通过估计用户u在所有主题上的偏好来建模任意用户u的兴趣。对于没有出现在原始user-topic matrix（用于训练该embedding space）中的任意新用户，我们仍能通过使用学到的topic embedding vectors \(y_i\)来将它们映射到该embedding space中。我们将在第5.3节中讨论。

5.2.2 行为因子分解模型（BF）

不同于上述介绍的矩阵因子分解模型，我们希望将用户不同的行为类型进行划分，并为每个用户对于不同的行为生成主题偏好。因此，我们不再使用对单个user-topic matrix进行因子分解，而是会对step 1生成的多个user-topic矩阵（BNUM, SBSUM, CBSUM）进行因子分解。

有一些在context-aware矩阵分解、张量分解等技术（Liu[20]）上进行的早期探索，会创建多个矩阵并同时学习一个latent space。然而，这些技术不能直接用在我们的行为因子分解问题上，因为我们正构建多个user-topic矩阵，它具有相同的列(column)/主题(topic)空间，但具有不同的行(rows)/用户(users)。他们构建的矩阵对于不同的context具有不同的items，相反的我们会使用一个隐式建模方法，也会考虑上行为上下文间的关系，比如：发布行为组合和消费行为组合。

图1展示了行为因子分解（BF）方法与baseline模型对比的区别。在step 1从用户行为构建矩阵时，不再仅构建BNUM，我们也会构建两类矩阵：SBSUM和CBSUM。

在step 2中，我们将所有生成的矩阵因子分解成相同的latent embedding space。我们会学习一个latent embedding space，并将对应每个特定的行为类型的每个用户和每个item映射到该空间中。在每个矩阵中的每个条目是对该用户行为的隐式兴趣值，因此，我们可以以如下方式扩展baseline模型。

这里\(p_{ui}^B\)和\(c_{ui}^B\)表示每个矩阵的偏好的置信度。给定所有特定的行为类型，我们使用等式(3)和(4)的\(\Gamma = \lbrace B_1, B_2, ...\rbrace\)，我们通过优化如下的等式来学习embedding space:

\[min_{x_*,y_*} \sum\limits_{B \in \Gamma} \sum\limits_{u,i} c_{ui}^B (p_{ui}^B - x_u^{B^T} y_i)^2 + \lambda (\sum\limits_{B \in \Gamma} \sum\limits_{u} \| x_u^B \|^2 + \sum\limits_{i} \|y_i\|^2)\]

….(6)

通过写出在\(\Gamma\)上的求和，我们使用一个与原始等式(5)相似解来求解该最优化问题，并为user-behavior和topics学习embedding space。

对比原始的user-topic矩阵，通过我们方法学到的embedding space的可能在对语义相似度的衡量上会更好，因为从之前分析（第3节），我们知道在user-topic矩阵上的观察值是从不同行为上的多种不同兴趣的混合。将这些信号相隔离可以产生一个更清晰的topic model。一个最近的paper：《how to learn generative graphical models such as LDA in social media》【31】。在该paper中，他们探索了如何将文档聚合成语料，并表示一个特定的context。由于生成式图模型和矩阵分解都是尝式从数据中学习latent space，该意图可以在两种方法上均可采用。我们的假设是，在user-behavior级别上构建矩阵，而非在user级别上；这可以帮忙我们清晰地标识跨主题的语义联合，不会增加太多的稀疏性。

5.3 step 3: 构建user profiles

最终，我们介绍了如何使用学到的latent embedding spaces来构建user profiles。如图2所示，我们介绍两种方法：

  • i) 从profile矩阵的input row vectors构建direct profile
  • ii) 通过一个回归模型学到一个权重集合，合并不同的direct profile进行构建weighted profile

对于每个user u，我们会构建\(p_u = \lbrace V_{u_B} \rbrace\)。每个\(V_{u_B}\)是一个关于用户u在特定行为类型B上的主题偏好向量。我们会构建三种类型的user profiles，对应于三种类型的input矩阵：

  • BNUP:
  • SBSUP:
  • CBSUP:

5.3.1 DPB(Direct Profile Building)

我们会使用一个用户的embedding factors(例如：在学到的latent embedding space中对于user u的向量\(x_u\))来生成他的完整的user profiles: \(V_{u_B} \in P_u\)。在DPB中，input是矩阵\(R_B\)中的observed row vectors（对于在\(\Gamma\)中的任意B来说），我们会为每个B构建user profile。

给定一个用户u和B，我们可以获取embedding factor \(x_u^B\)，接着使用该embedding factor和topic embedding factors \(Y = \lbrace y_i \rbrace\)，通过计算点乘：\(x_u^{B^T} Y\)来生成用户u行为B的偏好列表。接着对于每个用户u，她的output user profile可以被表示成:

\[P_u = \lbrace V_{u_B} = x_u^{B^T} Y \brace, B \in \Gamma\]

…(7)

特别的，给定任意B（它是\(B\)的一个子集），我们使用以下的等式来生成用户的SBSUP和CBSUP：

\[V_{u_B} = ( p_{u_B}^{e_1}, p_{u_B}^{e_2}, ..., p_{u_B}^{e_K}), p_{u_B}^{e_i} = x_u^{B^T} y_1\]

…(8)

其中，\(x_u^B\)是用户u在行为类型B上的embedding factor。

总之，在DPB中，不同的profiles通过不同的input row vectors来生成，BNUM的row vector会生成BNUP，SBSUM的row vector会生成SBSUP，CBSUM的row vectors会生成CBSUP。例如，为了为每个用户构建BNUP，我们设置\(B = \mathcal{B}\)，并使用所有他的已观察主题兴趣值（observed topic interest value）来生成他在该embedding space中的embedding factor \(x_u\)。接着为每个topic i计算\(x_uy_i\)，来得到他的BNUP。

\[V_u = (p_u^{e_1}, p_u^{e_2}, ..., p_u^{e_K}), p_u^{e_i} = x_u^T y_i\]

…(9)

对于不在学到的embedding model中的新用户，我们仍可以使用等式(2)来生成他的row input vectors，接着将该向量投影到一个embedding factor上。

5.3.2 WPB (Weighted Profile Building)

DPB会为一个用户生成一个behavior profile（如果该用户在过往有行为）。通过将用户的行为类型相分隔，我们可以使用DPB来为用户u的行为B生成profile，但这需要用户u在行为B上具有非零的观察值。对于那些在B上没有行为的用户，\(V_{u_B}\)会为空，这意味着一个没有该行为类型动作的user，不会有一个user profile。这在某种程度上对应于在推荐系统中的冷启动问题。

然而，我们可以通过使用在其它行为类型的user profiles来解决该问题。我们可以使用加权求和（weighted sum）将他们组合来生成一个在主题上的组合偏好向量。这对应于一个transfer learning问题。

这里，为了为用户u的行为类型B生成偏好向量\(V_{u_B}\)，而非直接使用等式(7)的结果，我们可以使用等式(10)为在\(\Gamma\)中的所有行为类型所生成的所有偏好向量进行加权求和（weighted sum）：

\[V_{u_B} = \sum\limits_{B_t \in \Gamma} W_{B_t} x_u^{B_t^T} Y\]

…(10)

\(\Gamma\)中不同行为类型的权重是模型级别的参数，例如：我们会为整个数据集的每个\(B_t \in \Gamma\)学到一个权重。因此，这些权重可以使用一个监督学习方法来从在我们的数据集中具有多种行为类型的所有用户上学到。因此，对于那些在过程历史记录中没有\(B_t\)的用户，我们仍可以为他们构建profiles。

在我们的实现中，我们可以使用线性回归和SGD来学习这些参数。因此，WPB可以生成BNUP、SBSUP、CBSUP，具体取决于应用。在大多数内容推荐应用中，常见的信息消费行为（consumption behaviors）非常重要，我们使用用户已观察到消费行为（observed）来学习权重来构建consumption profile。

6.评估

在之前章节，我们提出了行为因子分解法，它可以学习一个强大的latent space，并为多种行为类型构建user profiles。在该实验中，我们希望验证两个假设：

  • H1: 从我们的行为因子分解方法中学到的latent embedding模型在构建user profiles比baseline MF模型要更好
  • H2: 通过从多种行为类型中组合偏好向量，我们可以提升在特定行为类型上的user profiles的覆盖度(coverage)

在乘余章节，我们首先描述了如何设置实验，例如：我们使用了什么datasets，如何评估输出的user profiles的效果。接着我们比较了行为因子模型与baseline模型。我们也比较了在构建user profiles上的我们提出的两个方法，结果表明：通过组合行为类型，可以提升高质量的用户覆盖度。

6.1 实验设置

为了评估构建user profiles的效果，我们检查了在预测用户主题兴趣的不同方法。我们将dataset划分为两部分：training set和testing set。我们使用trainingset来训练和构建user profiles，然后在testing set上比较不同模型的效果。

6.1.1 Dataset

我们的dataset包含了在2014年 5月和6月的公开的Google+ 用户行为。第3.1节描述了dataset的生成。我们会同时使用5月的数据来训练baseline和我们的MF模型。我们随机从6月的行为数据中进行20%抽样来学习5.3.2节WPB的权重。使用乘余80%行为数据来评估不同方法的效果。

输入矩阵：在我们的dataset上，我们包含了所有公开5月和6月的posts数据。有4种类型关于posts的行为数据。我们构建不同的user-behavior-topic矩阵：

  • SBSUM
  • Publication CBSUM
  • Consumption CBSUM
  • BNUM

6.1.2 评估指标

对于一个给定的行为类型\(B_t\)，我们构建的user profile是一个关于在主题\(V_{u_{B_t}}\)上的偏好向量。在该vector上的值会估计：用户u是否会喜欢在行为\(B_t\)上的每个topic。这可以使用\(R_u^{B_t} = \lbrace r_{ui}^{B_t}, i \in E \rbrace\)在testing set上使用等式(2)计算的隐式兴趣进行评估。

尽管在\(V_{u_{B_t}}\)的实际值，和\(R_u^{B_t}\)不需要是相同的，\(B_t\)的一个好的user profile，\(V_{u_{B_t}}\)主题顺序进排序，必须与我们在testing set中观察的相似。

为了比较这两个vectors的顺序，我们会将\(V_{u_{B_t}}\)和\(R_{u}^{B_t}\)转换成两个关于在E中主题的排序列表：\(L_{method} = (e_{r_1}, e_{r_2}, ..., e_{r_N})\)是由profile building方法生成的关于top N主题的排序列表，\(L_{observed} = (e_{o_1}, e_{o_2}, ..., e_{o_N'})\)是所有观察到主题的排序列表。我们会使用如下指标进行评估：

  • Recall@N: \(L_{method}\)的top N的主题有多少出现在\(L_{observed}\)
  • NDCG@N:
  • AP@N:

7.讨论

7.1 潜在的应用

有许多应用可以使用我们方法构建的user profiles。由于我们将用户行为（还有不同的items集合：比如：posts, communities, users）映射到相同的embedding模型上，用户行为和items间的相似度可以用于为推荐生成排序列表。对比常用的user profiles（它不会分隔用户行为），我们的方法不仅会考虑users和items间的内容相似性，也会考虑不同推荐任务的上下文。例如，consumption profile可以用于为一个正在阅读post的用户推荐相关的posts，publication profile可以用于在一个用户创建一个post后为他推荐新朋友。

7.2 局限性和未来改进

提出的行为因子分解框架确实可以提升用户兴趣画像的效果，然而仍有局限性。其中之一是，我们的框架依赖于：用户不同的行为类型天然能反映用户的不同兴趣。在构建社交媒体的用户兴趣画像（比如G+）能运行良好，但不能泛化到其它领域上（比如：不同行为类型不能反映不同的用户兴趣）。

另外，结果表明我们的方法不能在用户非常稀疏、或者目标行为类型(尝试预测)没有数据的情况下。一个原因是，这些用户可能比其它用户具有更低的活跃度。另一个原因是，我们的方法会最优化多个矩阵，它们可能会对相同的用户丢失跨不同行为类型的相关性。为了解决这个问题，我们对使用tensor factorization技术（比如：PARAFAC）在行为矩阵上很感兴趣。我们的方法可以认为是一个tensor factorization上unfolding-based方法的扩展。

另外，我们想直接部署该框架到现实的推荐系统上，并通过在线实验来评估。

参考

https://static.googleusercontent.com/media/research.google.com/zh-CN//pubs/archive/43807.pdf

d0evi1 Reading time ~1 minute

Fayyad等在paper[1]提到过一种连续值离散化的方法：MDPLP。下面简单来看下：

1.介绍

分类学习算法通常要使用启发法（heuristics）来在多个属性值和类的组合间的可能关系空间上进行搜索。其中有一种这样的启发法（heuristic），它被使用在数据集中的分类上的选择局部最小化信息熵（比如ID3算法、C4､CART等）

机器学习中的属性可以是类别型的，也可以是连续型（数值型）。上述提到的属性选择过程假设所有的属性都是类别型的。连续型的属性在选择之前需要进行离散化（discretized），通过通过将属性的range范围进行划分成subrange范围。总体上，离散化是一个简单的逻辑条件，将数据划分成至少两个子集。

本文主要关注连续型属性的离散化。首先来看下二元离散化（binary discretization）。接着来看多区间离散化（multi-interval discretization）。

2.二元离散化

连续值属性通常在决策树生成时通过将它的值范围离散化成两个区间。对于连续型属性A，阈值为T， $ A \leq T $被分配到左分枝，$ A \gt T $被分配到右分枝。我们将该阈值T称为分割点（cut point）。该方法被用于ID3算法以及它的变种CART算法中的GID3。它可以被用于任何分类树算法，或者用来处理将连续型属性划分成二个区间的规则。尽管这里我们将它应用于离散化，在决策树生成的topdown的特定上下文也有使用。

假设在一个节点（样本集S具有N个样本）上对一个属性进行分枝。对于每个连续型属性A，我们在值的范围上选择最好的（“best”）分割点$ T_A $。样本首先通过属性A的值升序排列，在排完序序列中每个后继样本对（example pair）间的中点会作为一个潜在的分割点进行评估。这样，对于每个连续值属性，会发生N-1次评估（假设样本没有相同的属性值）。对于候选分割点T的每次评估，数据都会划分成两个集合，结果分区的分类熵（class entropy）会被计算。回忆一下，该离散化过程也会在决策树中的每个节点被执行。

样本集S通过T划分成两个子集：S1和S2 。假设存在K个类：$ C_1, …, C_k $，让$ P(C_i, S) $是S中含有类别$C_i$的样本比例。那么子集S的分类熵（class entropy）被定义成：

\[Ent(S) = - \sum_{i=1}^{k} P(C_i,S) log(P(C_i,S))\]

其中的log基数取2 。 Ent(S)用来衡量在S中的指定的分类信息量，单位为：bits。在集合S被划分成S1和S2后，为了评估生成的分类熵，我们采用它们生成的分类熵的加权平均：

定义1：对于一个样本集S，一个属性A，一个分割值T：假设$ S_1 \in S $是在样本S中的子集，它的A属性值$\leq T$，并且满足$ S_2 = S - S_1 $。分区的分类信息熵通过T索引，E(A,T;S)被定义成：

\[E(A,T;S) = \frac{|S_1|}{|S|} Ent(S_1) + \frac{|S_2|}{|S|} Ent(S_2)\]

…(2)

A的二分离散化通过选择分割点$T_A$来决定，其中$E(A, T_A; S)$是所有候选分割点中的最小值。

2.1 分割点选择的讨论

选择标准（selection criterion）的主要问题之一是：它的开销相当昂贵。尽管它是多项式复杂度，它为每个属性必须评估N-1次（假设有N个不同值的样本）。因为机器学习问题通常被设计成很大的训练量，N通常很大。当对一个类别型（离散化）属性进行时，该标准（criterion）只需要对r个分区进行单次评估即可，其中r为类别的数目。通常$ r « N$。确实，像ID3这样的算法在运行连续型属性时确实会慢许多。

其它缺点是：该算法具有一个天生的缺陷，当超过两个分类时，会生成”坏（bad）”的分割点。该缺点基于一个事实：该算法尝试最小化侯选二元划分集合的加权平均熵（如方程1所示）。分割点可能因此将一个分类的样本以最小化平均熵的方式进行分割。图1展示了这种情况。分割点并不会落在边界B1或B2上的其中之一，则是会落在两边的平均熵最小的点上。

这不是我们所期望的，因为它没必要将相同分类的样本分隔开，产生更大（但质量更低）的树。

然而，这些缺点不会被证明是对的。下面的理论1会展示，不管有多少分类，不管如何离散化，分割点将总是发生在两个类的边界上（见定义2, 它会对边界点有一个精准的说明）。这确实是该启发法（heuristic）的一个期待的特性，因为它展示了该启发法（heuristic）是“表现良好的（well-behaved）”。它告诉我们该启发法（heuristic）将从不选择一个在结果上（目的论：teleological）被认为是“坏”的分割（cut）。另外，该结果将帮助我们在不改变该功能的情况下提升算法的效果。

2.2 分割点总是在边界上

我们展示了属性A的值$ T_A $会最小化平均分类熵$E(A,T_A;S)$: 对于一个训练集S，必须总是在排序后样本序列不同分类的两个样本间的值。假设A(e)表示样本$ e \in S$的A值。

定义2：范围A中的值T是一个边界点，因此存在两个样本：$ e_1, e_2 \in S$具有不同的分类。比如：$A(e_1) < T < A(e_2) $，不存在着这样的样本$e’ \in S$，使得：$A(e_1) < A(e’) < A(e_2) $。

理论1：如果T能最小化E(A,T;S)，那边T就是一个边界点

证明：相当长，忽略。见paper[5]

推论1 用于ID3的该算法，可用于为连续型属性发现一个二分划分，将总是在排好序的属性样本对一个边界点划分数据。

证明：跟据理论1和定义。

推论1的第一个含义是，它可用于支持在离散化时最小化熵。我们使用信息熵的启发法（heuristic），因为我们知道，它控制一些衡量离散化需要的属性。然而，本身并不能排除不希望的情况，比如，图1中的情况。推论声明，“明显坏（obviously bad）”的分割从不会被该启发法（heuristic）所喜欢。该结果可进一步支持在离散化中使用该启发法（heuristic），因为它告诉我们，该启发法（heuristic）从目的论（teleological）的角度是表现良好的。

另外，推论1可以被用于在完全不需要更改效果的情况下增加算法的效果。通过对属性A的值进行排序之后，该算法只需要检查边界点b，而非所有的N-1个侯选。注意：$ k-1 \leq b \leq N-1 $。因为常通k « N，我们会期望节省很大的计算开销。我们演示了对ID3算法的所要评估的潜在分割点的数目上有极大的加速。ID3将连续值属性划分成两个区间。算法会检查多个区间，使用该过程的一个泛化版本（比如：下一节中要讲的一个）来达到更高的加速。算法会搜索规则，而非决策树，在离散化时会花费更多的开销。评估过程的计算加速只是推论1的一个附带效果。它的语义重要性是本文关注的，因为它证明了我们的泛化相同的算法，来生成多个区间，而非两个。

3.泛化该算法

推论1也提供了对扩展该算法的支持，在单个离散化过程中来抽取多个区间，而非两个。该动机是获取更好（“better”）的树。

训练集会做一次排序，接着算法会使用递归，总是选择最好的分割点。所使用的一个原则是：避免对一个给定区间做更进一步的二元划分。事实上，只会考虑这样的边界点：让自顶向下（top-down）的区间的得到更可行（因为该算法从不会在top上提交一个”bad”分割点），并且能减小计算开销。

为了合理地定义这样的一个算法，我们需要用公式来表示这个原则（criterion），以决定对一个给定样本做限制划分。该criterion需要理论支持。期望的测试将在后续被用于验证该理由是否合理。

从树生成的角度上看，为什么多区间（multiple range）的派生版本比二元区间（binary range）有更大的优点呢？通常，“感兴趣（interesting）”的范围可以是在属性值范围内的一个内部区间。为了得到这样的一个区间，单次做二元区间划分（”binary-interval-at-a-time”）的方法将导致不必要的、并会对样本做出超出感兴趣区间范围的过多划分。例如，假设，对于在[0,40]的属性值A，子区间 $ 12 < A \leq 20$是我们感兴趣的。假设A的范围离散化成：$ (-\infty,12), [12,20), [20,25), [25,\infty) $。给定一个算法，比如GID3,它能过滤出不相关的属性值，原则上可以获得如图2(a)所示的决策树。属性选择算法决定着只有2/4的区间是相关的。在区间外的样本会被分组到图中label=S的子集。

为了选择如图2(b)中生成的决策树两个区间范围，可以只使用一个二分区间离散化算法。注意，集S没必要划分成两个子集S1和S2 。对于第一棵树，该算法有机会使用一些其它的属性对S进行划分。该选项在第二种情况下不再使用，进一步的属性选择基于更小的子集：S1和S2. 必要的，这会导至相同的排序问题，会造成不相关值问题（irrelevant valus problem）。关于GID3如何处理该问题，以及如何只有一个子集的值被分支超出了本文的范围。

3.1 分割还是不分割？

给定集合S和一个潜在的二元划分$ \pi_{T}$，它表示在集合S上对属性A的分割值T，我们需要决定是否接受这次划分。该问题天然可以公式化成一个二分决策问题：接受或者拒绝$\pi_T$。假设HT为假设函数，其中$\pi_T$决定着是否接受。也就是说，HT是分类器，它会测试A的值，而非T，接着会对样本进行分类：根据在E中的样本小于T的值，A值<T。相似的，让NT来表示表示零假设（null hypothesis）：该假设会导致$\pi_T$被拒绝。NT会根据E中的类别来对所有样本进行分类，不需要检查A值。因为接受或拒绝都只是可能的动作，其中之一必然是正确的；另一个不正确。当然，没有其它办法来直接决定哪个是正确的。

假设$d_A$表示决定着接受划分$ \pi_T$，$d_R$表示拒绝。该情况中可能的决策集合是$ D= \lbrace d_A, d_R \rbrace $，我们具有待解决的一个二分决策问题。如果我们分配了一个cost给错误的决策，那么与一个决策规则（在$ {d_A, d_R} $间进行选择）相关的期望cost如下：

\[B = c_{11} Prob(d_A \wedge HT) + c_{22} Prob (d_R \wedge NT) + c_{12} Prob(d_A \wedge NT) + c_{21} Prob (d_R \wedge HT)\]

其中$c_{11}$和$c_{12}$表示做出正确选择的costs，而$c_{12}$和$c_{21}$表示做出错误决策的costs。这是期望贝叶斯风险（expected Bayes risk），决策规则被用于选择 $ \lbrace d_A, d_R \rbrace $的其中之一。贝叶斯决策原则（Bayes decision criterion），会调用选择决策规则来最小化期望的cost。

由于我们知道，分配给$c_{12}$和$ c_{21} $是什么值，我们会对均匀error cost分配做重排序。如果$ c_{11} = c_{22} = 0$和 $ c_{12} = c_{21} = 1$，那么最小化Bayes risk会减小一个决策规则PEC（Probalility-of-Error Criterion），它会最小化做出错误决策的概率。接着，它会通过一个简单的派生来展示Bayes决策原则来减小采用的决策规则，给定数据集S，选择假设HT，$ Prob(HT | S)$是计算假设的最大量。我们将该决策原则适用成”贝叶斯决策策略（Bayesian Decision Strategy）”。该策略有时也被称为MAP原则（maximum a posteriori），等价于PEC。

对于我们的决策问题，Bayesian decision strategy会选择$d \in D$的决策，它对应于在数据集S上具有最大概率的hypothesis：这样，如果$ Prob(HT | S) > Prob (NT |S)$，那么我们选$ d_A$。如果我们有一个方法来决策着上述两个要解决问题的概率：简单地选择hypothesis，它具有更高的概率，Bayesian决策策略会保障这是最好的策略。不幸的是，没有简单的方法来直接计算这样的概率。然而，我们应采用这样的方法：它将允许我们直接估计哪个概率更大。

3.2 MDLP(最小描述长度原则)

一个对象的最小描述长度（minimum description）被定义成所需的最小的位数，来唯一指定对象脱离于通用的所有对象。

我们会展示该决策问题，给定一个固定的样本集合，我们使用MDLP来猜测带有更高概率的hypothesis。MDLP是一个通用的原则，它的目的是，对自然界中天然的偏差进行编码，朝着更简单的理论来解释数据的相同部分。MDLP被Rissanen引入，之后被其它人使用。定义如下：

定义3：给定一个假设集合，以及一个数据集S，MDLP会调用假设HT来：$ MLength(HT) + MLength(S |HT) $是在假设集上的最小值。MLength(HT)表示对HT编码的最小可能长度，而 $ MLength(S |HT) $是对给定hypothesis编码的最小编码长度。

为了方便，我们假设长度的单位是：bits。数据的编码可以被认为是对数据点进行编码，它们是对于hypothesis HT来说“异常点（exceptions）”。如果HT能完全拟合数据，那么后一项将为0.

MDLP原则不必要要求与之前讨论的决策原则不同。它可以轻易地展示MDLP和Bayesian risk minimization strategy在理论上是相互相关的。由于篇幅原因，我们忽略了派生版本，它包含着可以包含对数据集S的hypothesis H所需要指定的bits数：$ -log_2 (Prob(H|S)) $，使用Bayes’ rule。最终获得的表达式等价于MDLP。这可以看成是采用MDLP的动机。

基于最早的争论，如果我们具有一种方法来发现真实的hypotheses的最小编码长度，那么采用MDLP来选择一个完整hypotheses的集合会导致使用最大MAP的hypothesis。接着，它等价于PEC决策原则。这意味着，选中的hypothesis将会最小化做出错误选择决策的概率。然而，在物理世界中，我们不会访问概率分布。因而，MDLP被用于对cost的估计，来在hypotheses间做比较。

3.3 应用MDLP：编码问题

现在，一个问题是编码问题（coding problem）。在我们的情况下，决策问题相当简单。完整的hypotheses包含了两个元素：{HT, NT}。我们应采用Quinlan和Rivest的公式，他们在属性选择上使用MDLP来尝试生成紧凑的决策树。在我们的情况下，该问题相当简单。

使用该公式，该问题需要解决的问题是通信问题。目标是通信一个方法（分类器），它可以允许接收器（receiver）来决定在数据集中的样本分类label。假设一个发送器（sender）具有整个训练数据样本集。而接收器具有没有该分类label的样本。sender只需要将合理的分类labeling传送给receiver。sender必须选择最短描述来指定该分类。

对Null Theory NT进行编码：在NT的情况下，sender必须简单地传递在S中的样本的类别。sender发送了N条消息，每个都是一个被编码过的类别label（其中N=$ | S | $）。为了编码在S中的样本的类别，我们必须使用一个最优化算法（比如：Huffman coding）来生成编码来优化平均编码长度。因为我们必须传递在集合S中每个样本的类别，将平均编码长度l乘以N给出了总的cost。另外，需要传递“code book”来用于解码类别。传递的code book的包含了每个类别对应的code word。因而，如果存在着K个分类，code book的长度可以通过(k * l)进行预估。注意，K是一个常数，不能随着N增长，因此，code book的cost是一个小的常数开销。

对划分HT进行编码：选中的分割点会对样本分区，必须由sender根据每两个子集中的分类编码来指定。指定分割点的开销为$log_2(N-1)$ bits，因为我们需要指定序列（分割点在之间落的地方）中N-1个样本的其中之一。

分类器HT对应于二分划分，$ \pi_T $，将集合S划分成子集：S1和S2。其中Sender必须传递分割点的一个说明书，根据S1中的类别序列，根据S2中的类别。再者，我们感兴趣的是，对S1和S2中的类别编码使最小化平均长度，如同在S中的类别编码所做的。其中$ l_1 $和$ l_2 $是对应于S1和S2各自的最小化平均编码长度（单位：bits）。传递HT的cost随着HT的数据一起：

\(log_2(N-1) + | S_1 | \cdot l_1 + | S_2 | \cdot l_2\) (bits)

我们也需要为S1和S2的类别编码各自传递code books。不同于传递S的情况(k个类别)，该情况我们必须通知receiver，哪个类别的子集会在两个子集S1和S2的其一中被表示，接着传递各自的code books。因为我们知道我们的划分是非平凡解（non-trivial）的，例如：$ S_1 \neq S_2 \neq \emptyset $，我们知道S1可能具有$2^k-1$个可能的k个类别的子集。使用一个长度派生版本，它可以被表示成：

\[G_k = [ \sum_{k_1=1}^{k-1} (C_{k_1}^{k}) 2^{k_1}] + 2^k - 1 = 3^k - 2\]

是可能的划分数目，超出我们需要指定的。由于我们需要$ log_2(G_k) $ bits。注意：$ log_2(G_k) < 2 log_2(2^k-1) < 2k$.

##

d0evi1 Reading time ~4 minutes

介绍

《BPR: Bayesian Personalized Ranking from Implicit Feedback》讨论了个性化排序学习模型的一个通用方法：Bayesian Personalized Ranking。主要贡献有：

  • 1.描述了通用的优化方法：BPR-OPT，它来自于对最优个性化排序的最大后验估计。我们展示了BPR-OPT在AUC上的分析。
  • 2.对于最大化BPR-OPT，我们提出了通用学习算法LearnBPR，它基于SGD，在训练过程使用bootstrap sampling。我们展示了该算法会优于最优化BPR-OPT时的SGD。
  • 3.我们展示了如何应用learnBPR到两个state-of-art推荐模型中
  • 4.我们的实验经验上展示了个性化排序任务，使用BPR的模型效果要好于其它学习算法

2.相关工作

推荐系统中最流行的模型是kNN CF。传统上，kNN的相似矩阵通过启发法（heuristics）进行计算（例如：Pearson相关度），但在最近的工作中，相似矩阵可以看成是模型参数，可以学到。最近，矩阵分解（MF）在推荐系统中非常流行，可以使用隐式和显式反馈。在最近工作中，SVD也被证明是可以学习特征矩阵。通过SVD学习得到的MF模型，被证明是很容易overfitting。因而提出了正则化学习方法。对于item的预测，Hu等人提出了一个带case weights的正则的最小二乘优化(WR-MF)。case weights可以被用于减小负样本的影响。Hofmann提出了一个概率隐语义模型来进行item推荐。Schmidt-Thieme将该问题转成一个multi-class问题，并使用一个二分类集合来求解它。即使在item预测上的上述所有工作。。。

本文中，我们主要关注模型参数的离线学习。将学习方法扩展到在线学习情况——例如：添加一个新用户，它的历史增加从0到1，2，… feedback事件——对于MF的排序预测已经被学到。相同的fold-in策略可以被用于BPR。

。。。

3.个性化排序（Personalized Ranking）

个性化排序的任务，会为一个用户提供一个items排序列表。这也被称为item推荐。一个示例是，在线电商希望推荐一个个性化的items排序列表，用户会从中购买。在本paper中，我们会研究以下情形：ranking必须从用户的隐式行为（例如：过去的购买）进行infer得到。隐式反馈系统只提供正例数据（正样本）。未被观察到(non-observed)的user-item pairs（例如：一个用户没有购买一个item）会是一个真实负反馈（用户对购买该item不敢兴趣）以及缺失值（用户可能会在将来购买该item）的混合。

3.1 公式化

图1: 在左侧，为已观察到的数据S。直接从S中学习是不可行的，因为只有正反馈被观察到。通常负例数据通过使用0值填充矩阵来生成

假设U是所有users的集合，I是所有items的集合。在我们的场景下，隐式反馈\(S \subseteq U \times I\)（见图1左侧）。类似这种反馈方式有：电商中的购买行为，视频观看 或者 网页上的点击。推荐系统的任务是提供给用户一个个性化总排序(personlaized total ranking): \(>_u \subset I^2\)，其中\(>_u\)必须满足一个总顺序属性：

\[\begin{aligned} & \forall i,j \in I: i \neq j \Rightarrow i >_u j \vee j >_u i \ \ (totality) \\ & \forall i,j \in I: i >_u j \wedge j >_u i \Rightarrow i = j \ \ (antisymmetry) \\ & \forall i,j \in I: i >_u j \wedge j >_u k \Rightarrow i >_u k \ \ (transitivity) \end{aligned}\]
  • totallity: 总体性
  • antisymmetry: 反对称性
  • transitivity: 传递性

出于便利，我们也定义了：

\[I_u^+ := {i \in I: (u,i) \in S} \\ U_i^+ := {u \in U: (u,i) \in S}\]

3.2 问题分析

前面提到，在隐式反馈系统中只有正例(positive classes)被观察到。剩余数据其实是实际负例(negative)与缺失值（missing value）的一个混合。对于应付缺失值问题，最常见的方法是：忽略所有缺失值。通常典型的机器学习模型不能学习任何东西，因为他们两者间不能进行区分这两者(负例和缺失值)。

对于item推荐，常用的方法是，对一个item预测一个个性化分\(\hat{x}_{ui}\)，它可以影响用户对该item的偏好。接着，该items会根据该分值进行排序。对于item推荐的机器学习方法，通常会从S中创建训练数据：给定：

  • 正例：\((u, i) \in S\) pairs
  • 负例：所有在\((U \times I) \backslash S\)中的其它组合

如图1所示。接着，模型会拟合该数据。这意味着模型的最优化是为在S中的元素预测value是1, 其余为0。该方法的问题是，在模型中将来进行排序的所有元素（\(U \times I \backslash S\)）在训练期间都会作为负反馈被表示给机器学习算法。这意味着：如果一个模型具有足够表现力（它可以精准拟合训练数据），它根本不能进行排序，因为它的预测值基本为全0(很稀疏，大部分为0, 全预测对）。为什么这样的机器学习方法可以预测rankings？唯一原因是，有策略阻止overfitting，比如：正则化。

我们使用一种不同的方法：通过使用item pairs作为训练数据，然后为正确(correctly)的ranking item进行最优化（而非对单个items进行打分），因为这比使用负例来替代缺失值要更好。从S中，我们可以尝试为每个user parts（\(>_u\)）进行重构。如果一个item i被user u观看过，（例如：\((u,i) \in S\)）——那么，我们假设该user喜欢该item要胜过其它未观察到的items。

图2: 在左侧，已观察到的数据S。我们的方法会在一个items pair间创建特定用户的pairwise偏好\(i >_u j\)。在右侧，加号(+)表示一个用户偏爱item i胜过item j；减号(-)表示他偏爱j胜过i。

例如，在图2中，user \(u_1\)已经观看过item \(i_2\)，但没看过item \(i_1\)，因此我们假设，该用户喜欢\(i_2\)要胜过\(i_1\)：\(i_2 >_u i_1\)。对于被一个用户同时观看过的两个items，我们不能推断更偏好哪个。对于用户未观看过的两个items来说（比如：对于user \(u_1\), item \(i_1\)和\(i_4\)），相类似，也不能推断哪个更好。为了将这种现象公式化，我们创建训练数据 \(D_S : U \times I \times I\)：

\[D_S := \lbrace (u, i, j) | i \in I_u^+ \wedge j \in I \backslash I_u^+ \rbrace\]

\((u,i,j) \in D_S\)的语义是，user \(u\)被假设成：喜欢i，胜过j。由于\(>_u\)是非对称的，负例会被隐式对待。

我们的方法有两个优点：

  • 1.我们的训练数据同时包含了正负例pairs以及缺失值。介于两个未观察到的items间的缺失值是将来必须排序的item pairs。这意味着，从pairwise的角度看，训练数据\(D_S\)和测试数据是不相交的。
  • 2.为排序的实际目标函数创建训练数据，例如：观察到\(>_u\)的子集\(D_S\)被用成训练数据。

4.BPR

在这部分，我们为解决个性化排序任务生成了一种通用方法。对于个性化排序，它包含了通用优化准则：BPR-OPT，它源自对该问题的Bayesian分析，会使用似然函数来为\(p(i >_u j \mid \Theta)\)以及模型参数\(p(\Theta)\)的先验概率。我们展示了排序统计AUC的分析。对于遵循BPR-OPT的学习模型，我们提出了算法learnBPR。最后，我们会展示BPR-OPT和LearnBPR是如何应用到两个state-of-art的推荐算法（MF和adaptive kNN）上。比起常用的训练方法，使用BPR来优化这些模型可以生成更好的rankings。

4.1 BPR优化原则

为所有items \(i \in I\)寻找正确的个性化排序的Bayesian公式，是为了最大化以下后验概率，其中\(\Theta\)表示一个指定模型类别(比如：MF)的参数向量。贝叶斯公式为：

\[P(\Theta | >_u) \propto p(>_u | \Theta) p(\Theta)\]

这里，\(>_u\)是对于user u希望但隐含的偏好结构。所有用户都假设行为间相互独立。我们也假设：对于一个指定用户，每个items \((i,j)\) pair的顺序，与每一个其它pair相互独立。因而，对于所有用户\(u \in U\)，以上的特定用户的似然函数\(p(>_u \mid \Theta)\)可以首先被重写成：单个密度(densities)和第二个的乘积的组合。

\[\prod\limits_{u \in U} p(>_u | \Theta) = \prod\limits_{(u,i,j) \in U \times I \times I} p(i >_u j | \Theta)^{\delta((u,i,j) \in D_S)} \cdot(1-p(i >_u j | \Theta))^{\delta((u,j,i) \notin D_S}\]

其中\(\delta\)是指示函数：

\[\delta(b) := \begin{cases} 1 & \text{if b is true,} \\ 0 & \text{else} \end{cases}\]

归因于合理的pairwise ordering scheme的总体(totality)和非对称性(antisymmetry)，上述公式可以简化为：

\[\prod\limits_{u \in U} p(>_u | \Theta) = \prod\limits_{(u,i,j) \in D_S} p(i >_u j | \Theta)\]

到目前为止，通常不会保证获得一个个性化的总顺序。为了得到它，必须满足之前提到过的合理性质（totality、antisymmetry、transitivity）。为了这样做，我们定义了一个用户喜欢item i胜过item j的独立概率：

\[p(i >_u j | \Theta) = \sigma( \hat{x}_{uij} (\Theta))\]

其中：

  • \(\sigma\)是logistic sigmoid：\(\sigma(x) := \frac{1}{1+e^{-x}}\)
  • \(\hat{x}_{uij}(\Theta)\)是一个特定的关于模型参数向量\(\Theta\)的real-valued函数，它会捕获user u、item i、item j间的特殊关系。

换句话说，我们的通用框架会将建模在u、i、j间的关系的任务表示到一个底层模型类（比如：MF或adaptive kNN）上，它们负责估计\(\hat{x}_{uij}(\Theta)\)。因而，统计方式建模一个个性化总顺序\(>_u\)变得可行。出于便利，后续章节我们会跳过介绍来自\(\hat{x}_{xij}\)的参数\(\Theta\)。

至今，我们已经讨论了似然函数。为了补全个性化排序任务的Bayesian建模方法，我们引入了一个通用的先验密度\(p(\Theta)\)，它是一个零均值、协方差矩阵\(\sum_{\Theta}\)的正态分布。

\[p(\Theta) \sim N(0, \sum_{\Theta})\]

下面，为了减小未知超参数的数目，我们设置\(\sum_{\Theta} = \lambda_{\Theta} I\)。现在，我们可以将最大后验估计进行公式化，来生成我们为个性化排序BPR-OPT的通用最优化准则：

\[\begin{aligned} BPR-OPT &:= ln \ p(\Theta | >_u) \\ & = ln \ p(>_u | \Theta) p(\Theta) \\ & = ln \ \prod\limits_{(u,i,j) \in D_S} \sigma(\hat{x}_{uij}) p(\Theta) \\ & = \sum\limits_{(u,i,j) \in D_S} ln \ \sigma(\hat{x}_{uij}) + ln \ p(\Theta) \\ & = \sum\limits_{(u,i,j) \in D_S} ln \ \sigma(\hat{x}_{uij}) - \lambda_{\Theta} \|\Theta \|^2 \end{aligned}\]

其中\(\lambda_{\Theta}\)是模型特定的正则化参数。

4.1.1 AUC最优化分析

有了Bayesian Personalized Ranking(BPR) scheme的公式，很容易理解BPR和AUC间的分析。每个用户的AUC通常被定义为：

\[AUC(u) := \frac{1}{ | I_u^+ | |I \backslash I_u^+ |} \sum\limits_{i \in I_u^+} \sum\limits_{j \in | I \backslash I_u^+|} \sigma(\hat{x}_{uij} > 0)\]

这里，平均AUC是：

\[AUC := \frac{1}{|U|} \sum\limits_{u \in U} AUC(u)\]

…(1)

其中, \(z_u\)是归一化常数：

\[z_u = \frac{1} { | U | | I_u^+ | | I \backslash I_u^+|}\]

在(1)和BPR-OPT间的分析是很明显的。除了归一化常数\(z_u\)外，他们只在loss function上有区别。AUC会使用不可微(non-differentiable)的loss \(\sigma(x>0)\)，它等同于Heaviside function:

\[\sigma(x > 0) = H(x) := begin{cases} 1, & \text{ x > 0 } \\ 0, & \text{ else } end{cases}\]

作为替代，我们会使用可微loss \(ln \sigma(x)\)。惯例上，当为AUC进行最优化时【3】，替代不可微的Heaviside函数。通常，替代选择是启发式的（heuristic），并且有一个与\(\sigma\)相类似的相似形状函数（similarly shaped function）（见图3）。在本paper中，受MLE的启发，我们已经已经生成了替代法 \(ln \sigma(x)\)。

图3: 用于最优化AUC的loss function。不可微的Heaviside H(x)通常使用sigmoid \(\sigma(x)\)来近似。我们的MLE导数建议使用\(ln \sigma(x)\)来替代

4.2 BPR learning算法

在最后一节，我们已经为个性化排序生成了一个最优化原则（optimization criterion）。由于criterion函数是可微的，基于梯度下降(gradient descent)的算法是一个用于最大化的很明智的选择。但正如我们所见，对于我们的问题，标准梯度下降并不适合。为了解决该问题，我们提出了LearnBPR，一个基于SGD的、在训练的三元组上进行bootstrap sampling的算法（见图4）。

图4:基于SGD的boostrapping BRP最优化模型。学习率\(\alpha\)，正则参数\(\lambda_{\Theta}\)

首先，BPR-OPT的梯度会各自按模型参数求导：

\[\begin{aligned} \frac{\partial {BPR-OPT}}{\partial \Theta} & = \sum_{(u,i,j) \in D_S} \frac{\partial}{\partial \Theta} ln \sigma(\hat{x}_{uij}) - \lambda_{\Theta} \frac{\partial}{\partial \Theta} \| \Theta \|^2 \\ & \propto \sum\limits_{(u,i,j) \in D_S} \frac{-e^{-\hat{x}_{uij}}}{1+e^{-\hat{x}_{uij}}} \cdot \frac{\partial}{\partial \Theta} \hat{x}_{uij} - \lambda_{\Theta} \Theta \end{aligned}\]

对于梯度下降，两种常用算法是full GD或SGD。在第一种方法中，每一step，会在所有训练数据上进行计算，接着模型参数会使用learning rate \(\alpha\)进行更新：

\[\theta \leftarrow \Theta - \alpha \frac{\partial BPR-OPT} {\partial \Theta}\]

总之，该方法会在“正确”方向上产生一个下降，但收敛很慢。因此，我们在\(D_S\)上有\(O(\mid S \mid \mid I \mid)\)条训练三元组(triples)，在每个update step上计算full gradient是不可行的。再者，对于使用full DG进行BPR-OPT的最优化、以及在训练pairs上的数据倾斜，会导致很差的收敛。想象下，一个item i，通常是positive的。接着我们在loss中的\(\hat{x}_{uij}\)上有许多项(terms)，因为对于许多用户u、item i，会与所有负例items j进行对比（占主导的分类）。因而，模型参数的梯度依赖于i是否在梯度上占据主导地位。这意味着必须选择非常小的learning rates。第二，由于梯度的不同，正则化很难。

另一个流行的方法是SGD。在这种情况下，对于每个triple \((u,i,j) \in D_S\)，只会执行一个更新。

\[\Theta \leftarrow \Theta + \alpha ( \frac{e^{-\hat{x}_{uij}}}{1+e^{\hat{x}_{uij}}} \cdot \frac{\partial}{\partial \Theta} \hat{x}_{uij} + \lambda_{\Theta} \Theta)\]

总之，对于我们的倾斜问题，这是一个好方法。但training pairs遍历的顺序是很严格的。一个常用的方法是，以item-wise或user-wise的方式遍历数据，会产生很差的收敛，因为在相同的user-item pair上有许多连续的更新——例如：对于一个user-item pair (u,i)，有许多j 满足\((u,i,j) \in D_S\)。

为了解决这个问题，我们建议使用一个SGD算法来随机选择triples（非均匀分布）。该方法在连续更新steps很小时，会选择相同的user-item组合。我们建议使用一个有放回的bootstrap sampling方法，因为在任意step上都可能执行stopping。放弃通过该数据进行full cycles的思想，在我们的case中特别有用，因为样本数目会非常大，为了收敛通常一个full cycle的一部分就足够了。在我们的评估中，我们选择了单个steps的数目，它线性依赖于观察到的正反馈S的数目。

图5展示了一个常用的user-wise SGD、与我们的带bootstrapping的LearnBPR的比较。该模型是16维的BPR-MF。正如你看到的，LearnBPR比user-wise GD收敛更快。

图5: 常见的user-wise SGD与我们的基于bootstrapp sampling的learnBPR算法收敛率的经验比较

4.3 使用BPR来学习模型

对于item推荐，下面我们描述了两个state-of-the-art的模型，以及如何使用我们提出的BPR方法来学习它们。我们已经选择两个不同的模型：MF[5,12]和learned kNN[8]。这两个模型都尝试建模一个用户在一个item上的隐式偏好。它们的预测是对于每个user-item-pair (u,l)的一个实数 \(\hat{x}_{ul}\)。

由于在我们的optimization中，我们有triples \((u,i,j) \in D_S\)，我们首先对estimator \(\hat{x}_{uij}\)进行解耦，并将它定义为：

\[\hat{x}_{uij} := \hat{x}_{ui} - \hat{x}_{uj}\]

现在，我们可以应用任意标准的CF模型来预测\(\hat{x}_{ul}\)。

需要重点注意的是，尽管在其它工作中我们使用相同的模型，我们会使用不同的准则(criterion)对它们进行最优化。这会产生一个更好的排序，因为我们的准则对于排序任务是最优的。我们的准则不会尝试将单个predictor \(\hat{x}_{ul}\)看成是单个数字，但作为替换，尝试对两个预测的差\(\hat{x}_{ui} - \hat{x}_{uj}\)进行分类。

4.3.1 MF

预测\(\hat{x}_{ui}\)的问题可以看成是估计一个矩阵：\(X: U \times I\)。对目标矩阵X使用MF，可以通过两个低秩矩阵\(W: \mid U \mid \times k\)和\(H: \mid I \mid \times k\):

\[\hat{X} := W H^t\]

其中k是维度/秩 (dimensionality/rank)的近似。在W中的每行 \(w_u\)可以被看成是描述一个user u的一个feature vector，相似的，H中的每行\(h_i\)描述了一个item i。因而，预测公式可以被写为：

\[\hat{x}_{ui} = \langle w_u, h_i \rangle = \sum\limits_{f=1}^{k} w_{uf} \cdot h_{if}\]

除了点乘\(\langle \cdot, \cdot \rangle\)外，总之类似于[11]的任意kernel都可以被使用。对于MF的模型参数是\(\Theta = (W, H)\)。该模型参数可以被看成是隐变量（latent variables），会建模一个用户的未观察到的品味(taste)、以及一个item未观察到的属性(properties)。

通常，通过SVD根据最小二乘获得的X的的最佳近似\(\hat{X}\)。对于机器学习任务，SVD会overfits，因此提出了许多其它的MF方法，包含正则化最小二乘最优化，非负因子分解，最大间隔因子分解，等。

对于排序任务，例如：估计一个用户是否偏爱一个item胜过其它item，一个更好的方法是根据BPR-OPT准则来最优化。这可以通过使用提出的LearnBPR来达到。正如之前所述，对于使用LearnBPR的最优化，每个模型参数\(\theta\)的梯度\(\hat{x}_{uij}\)是已知的。对于MF模型，导数为：

\[\frac{\partial}{\partial \theta} \hat{x}_{uij} = \begin{cases} (h_{if} - h_{jf}) & \text{if $\theta = w_{uf}$ } \\ w_{uf} & \text{if $\theta = h_{if}$} \\ -w_{uf} & \text{if $\theta = h_{jf}$} \\ 0 & \text{else} \end{cases}\]

另外，我们使用三个正则化常数：

  • \(\lambda_W\)对应用户特征W;

item features H有两个正则常数：

  • \(\lambda_{H^+}\)被用于只在\(h_{if}\)上用于positive更新；
  • \(\lambda_{H^-}\)用于在\(h_{jf}\)上的negative更新

4.3.2 Adaptive KNN

最近邻方法在CF中很流行。它依赖items间（item-based）或users间（user-based）的相似度衡量。以下我们描述了item-based方法，通常他们会提供更好的结果，但user-based方法也类似。该思想是：为一个user u预测一个item i，它依赖于item i与该用户过往看过的其它所有items(例如：\(I_u^+\))间的相似度。通常，\(I_u^+\)中只有k个最相似的items会被看成是K个最近邻。如果items间的相似度被选中，你可以比较在\(I_u^+\)上的所有items。对于item-based KNN的item预测：

\[\hat{x}_{ui} = \sum\limits_{l \in I_u^+ \wedge l \neq i} c_{il}\]

其中：\(C: I \times I\)是对称的（item-correlation / item-similarity）矩阵。这里，kNN的模型参数为\(\Theta = C\)。

最常用的选择C的方法是，通过应用一个启发式相似度来衡量，比如：cosine向量相似度：

\[c_{i,j}^{cosine} := \frac{|U_i^+ \cap U_j^+|} {\sqrt{ |U_i^+ | \cdot |U_j^+|}}\]

一个更好的策略是，通过学习来将相似度 C适配该问题。这可以通过直接使用C作为参数，或者如果items数很大，你可以学习一个C的因子分解\(H H^t\)，其中：\(H: I \times k\)。下面，在我们的评估中，我们会使用第一种方法来直接学习C，无需因子分解。

为了对kNN模型最优化来进行ranking，我们使用BPR-OPT准则，并使用LearnBPR算法。为了应用该算法，\(\hat{x_{uij}}\)对应模型参数C的梯度为：

\[\frac{\partial}{\partial \Theta} \hat{x}_{uij} = \begin{cases} +1 & \text{if $\theta \in \lbrace c_{il}, c_{li} \rbrace \wedge l \in I_u^+ \wedge l \neq i,$} \\ -1 & \text{if $\theta \in \lbrace c_{jl}, c_{lj} \rbrace \wedge l \in I_u^+ \wedge l \neq j,$} \\ 0 & \text{else} \end{cases}\]

我们有两个正则常数，\(\lambda_+\)用于在\(c_{il}\)上更新，\(\lambda_{-}\)用于在\(c_{jl}\)上更新。

5.与其它方法的关系

  • WR-MF: Weighted Regularized Matrix Factorization
  • MMMF: Maximum Margin Matrix Factorization

略

6.评估

在我们的评估中，我们比较了BPR学习与其它学习方法。我们选择两个流行的模型：MF和kNN。MF模型的效果要好于其它模型（比如：Bayesian模型URP、PLSA等 ）。在我们的评估中，MF模型使用三种不同方法学到：SVD-MF, WR-MF, BPR-MF。对于kNN，我们比较了Cosine-kNN，以及一个使用BPR方法优化的模型(BPR-kNN)。另外，我们也上报了baseline（most-polular）的结果，它会按用户独立的方式来加权每个item：比如：\(\hat{x}_{ui}^{most-pop} := \mid U_i^+ \mid\)。另外，我们给出了对于任意非个性化排序方法在AUC (\(np_{max}\))的理论上界。

6.1 datasets

我们使用两个来自不同应用的数据集。

  • Rossmann dataset：来自在线电商。它包含了1w用户在4k items上的购买历史。总共有426612个购买记录。该任务是预测用户希望在下次购买的一个个性化items列表.
  • Netflix DVD rental dataset: 该数据集包含了用户行为的打分，其中一个用户对电影提供了1-5星的显式评分。如果我们希望以隐式反馈的方式求解，我们可以移除rating。该任务是预测用户是否可能对一个电影进行评分。我们会为用户提供一个最可能打分的个性化排序列表。对于Netflix我们创建了一个subsample: 1w用户，5000 items，包含了565738个rating动作。我们会做子抽样：每个用户至少包含10个items，每个item至少有10个用户。

6.2 评估方法

我们使用留一法（leave-one-out）来进行评估，训练集\(S_{train}\)，测试集\(S_{test}\)。该模型会在\(S_{train}\)上学习，并在\(S_{test}\)上通过平均AUC统计进行评估：

\[AUC = \frac{1}{|U|} \sum\limits_{u} \frac{1}{|E(u)|} \sum\limits_{(i,j) \in E(u)} \sigma(\hat{x}_{ui} > \hat{x}_{uj}\]

…(2)

其中，每个用户u评估的pairs为：

\[E(u) := \lbrace (i,j) | (u,i) \in S_{test} \wedge (u,j) \notin (S_{test} \cup S_{train})rbrace\]

…(2)

AUC越高表示效果越好。随机猜测法的AUC是0.5,最好为1。

我们会重复10次实验，每次抽取新的train/test splits。超参数通过grid search进行最优化。

6.3 结果

图6

参考

https://arxiv.org/pdf/1205.2618.pdf