myTarget中的动态再营销（dynrem）是一种有针对性的广告技术，它使用有关网站在网站上以及广告商的移动应用程序中的用户操作的信息。 例如，在一个在线商店中，用户查看了商品页面或将商品页面添加到购物篮中，myTarget使用这些事件来准确显示某人已经表现出兴趣的商品和服务的广告。 今天，我将更详细地讨论生成非个人的机制，即item2item-recommendations，它使我们能够多样化和补充广告输出。

dynrem myTarget的客户主要是在线商店，可以拥有一个或多个产品列表。 在制定建议时，应将“商店-货物清单”对视为一个单独的单元。 但为简单起见，我们接下来将仅使用“存储”。 如果我们讨论输入任务的规模，那么应该为大约一千家商店建立建议，并且商品数量可以从数千到数百万不等。

dynrem的推荐系统必须满足以下要求：

1. 标语包含最大化其点击率的产品。
2. 建议在给定时间内离线构建。
3. 系统架构必须灵活，可扩展，稳定并且可以在冷启动环境中工作。

请注意，从建立固定时间的建议的需求和所描述的初始条件（我们乐观地假设商店的数量在增加）中，自然而然地产生了对经济地使用机器资源的需求。

第2节包含构建推荐系统的理论基础，第3节和第4节讨论了该问题的实际方面，第5节总结了总体结果。

基本概念

考虑为一家商店建立推荐系统的任务，并列出基本的数学方法。

奇异值分解（SVD）

建立推荐系统的一种流行方法是奇异分解（SVD）方法。 评分表 $$$R =（r_ {ui}）$ 表示为两个矩阵的乘积 $$$P$ 和 $$$Q$ 这样 $$$R \约P Q ^ T$ 然后给用户评分 $$$u$ 用于商品 $$$我$ 表示为 $$$\ hat {r} _ {ui} = <p_u，q_i>$ [1]，其中标量积的元素是维向量 $$$k$ （模型的主要参数）。 该公式是其他SVD模型的基础。 寻找任务 $$$P$ 和 $$$Q$ 归结为功能的优化：

（2.1）

$$

$$J（P，Q）= \ sum _ {（u，i）} \ mathcal {L}（r_ {ui}，\ hat {r} _ {ui}）+ \ Lambda（P，Q）\ rightarrow \ min_ {P，Q}，$$

在哪里 $$$L$ -错误功能（例如， Netflix竞赛中的RMSE）， $$$Λ$ -正则化，并且总和是已知评级的对。 我们以显式形式重写表达式（2.1）：

（2.2）

$$

$$J（P，Q）= \ sum _ {（u，i）}（r_ {ui}-<p_u，q_i>）^ 2 + \ lambda_1 || p_u || ^ 2 + \ lambda_2 || q_i || ^ 2 \ rightarrow \ min_ {P，Q}，$$

在这里 $$$λ1$ ， $$$λ2$ -用户表示的L2正则化系数 $$$p_ {u}$ 和货物 $$$q_ {i}$ 相应地。 Netflix竞赛的基本模型是：

（2.3）

$$

$$\ hat {r} _ {ui} = \ mu + b_u + b_i + <p_u，q_i>，$$

（2.4）

$$

$$J（P，Q）= \ sum _ {（u，i）}（r_ {ui}-\ mu-b_u-b_i-<p_u，q_i>）^ 2 + \ lambda_1 || p_u || ^ 2 + \ lambda_2 || q_i || ^ 2 + \ lambda_3 b_u ^ 2 + \ lambda_4 b_i ^ 2 \ rightarrow \ min_ {P，Q}，$$

在哪里 $$$µ$ ， $$$b_ {u}$ 和 $$$b_ {i}$ -分别针对评分，用户和产品的偏见。 可以通过向模型（2.3）-（2.4）添加隐式用户首选项来对其进行改进。 在Netflix竞赛示例中，显式响应是用户“根据我们的要求”对电影设置的分数，以及有关“用户与产品互动”的其他信息（查看电影，其描述，对其进行评论；即，隐式响应不会给出隐式响应）有关电影评级的直接信息，但同时表示兴趣）。 隐式响应记帐是在SVD ++模型中实现的：

（2.5）

$$

$$\ hat {r} _ {ui} = \ mu + b_u + b_i + <p_u + \ frac {1} {\ sqrt {\ sigma_u}} \ sum_ {j \ in S（u）} y_j，\，\ ，q_i>，$$

在哪里 $$$S（u）$ -用户与之隐式交互的一组对象， $$$σ_{u} = | S（u）|，y_ {j}$ -尺寸表示 $$$k$ 对于来自的对象 $$$S（u）$ 。

分解机（FM）

从具有不同SVD模型的示例中可以看出，一个模型在评估公式中包含的一组术语上与另一个模型不同。 而且，每次扩展模型都代表着一项新任务。 我们希望可以轻松实现这样的更改（例如，添加新的隐式响应，同时考虑时间参数），而无需更改模型实现代码。 可以使用以下参数化以方便的通用形式表示模型（2.1）-（2.5）。 我们将用户和产品表示为一组功能：

（2.6）

$$

$$\ overline {x} ^ U =（x_1 ^ U，x_2 ^ U，\点，x_l ^ U）\ in \ mathbb {R} ^ l，$$

（2.7）

$$

$$\ overline {x} ^ I =（x_1 ^ I，x_2 ^ I，\点，x_m ^ I）\ in \ mathbb {R} ^ m$$

图 1：CF情况下的特征矩阵示例。

例如，在协作过滤（CF）的情况下，当仅使用有关用户和产品交互的数据时，特征向量看起来像是一个热码（图1）。 介绍矢量 $$$\ overline {x} =（\ overline {x} ^ U，\ overline {x} ^ I）$ ，然后将推荐任务简化为目标变量的回归问题 $$$r_ {ui}$ ：

1. 线性模型：
   （2.8）
   

   $$

   $$h_ {lin}（\ overline {x}）= w_0 + \ sum_ {j = 1} ^ {l + m} w_jx_j$$
2. Poly2：
   （2.9）
   

   $$

   $$h_ {poly2}（\ overline {x}）= w_0 + \ sum_ {j = 1} ^ {l + m} w_jx_j + \ sum_ {i = 1} ^ {l + m} \ sum_ {j = i + 1 } ^ {l + m} w_ {ij} x_i x_j$$
3. 调频：
   （2.10）
   

   $$

   $$h_ {FM}（\上划线{x}）= w_0 + \ sum_ {j = 1} ^ {l + m} w_jx_j + \ sum_ {i = 1} ^ {l + m} \ sum_ {j = i + 1 } ^ {l + m} x_i x_j <\上线{v} _i，\上线{v} _j>$$

在哪里 $$$w_ {j}$ -模型参数， $$$v_ {i}$ 是尺寸向量 $$$k$ 代表标志 $$$我$ 在潜在的空间 $$$l$ 和 $$$m$ -用户和产品的标牌数量。 除了一次性代码之外，基于内容的功能（基于内容的CB）还可以用作标志（图2），例如，产品和用户配置文件的矢量化描述。


图 2：扩展特征矩阵的示例。

[2]中介绍的FM模型是（2.1）-（2.5），（2.8），（2.10）的概括。 FM的本质在于，它考虑了使用标量积的要素的成对相互作用 $$$<\上线{v} _i，\上线{v} _j>$ ，不使用参数 $$$w_ {ij}$ 。 FM优于Poly2的优点是参数数量大大减少：对于矢量 $$$v_ {i}$ 我们将需要 $$$（l + m）·k$ 参数，以及 $$$w_ {ij}$ 将是必需的 $$$lm m$ 参数。 在 $$$l$ 和 $$$m$ 对于大订单，第一种方法使用的参数要少得多。

请注意：如果训练集中没有特定的配对 $$$（i，j）$ ，然后用 $$$w_ {ij}$ 在Poly2中，它不影响模型的训练，并且评分分数仅在线性部分上形成。 但是，方法（2.10）允许我们通过其他功能建立关系。 换句话说，有关一次交互的数据有助于评估此示例中未包括的属性的参数。

基于FM，实现了所谓的混合模型，其中将CB属性添加到CF属性。 它使您能够解决冷启动问题，并考虑到用户的偏好并允许您提出个性化的建议。

Lightfm

在FM的流行实现中，重点在于用户特征与产品特征之间的分离。 矩阵充当模型参数 $$$E ^ U$ 和 $$$E ^ I$ 提交自定义和产品功能：

（2.11）

$$

$$E ^ U = \开始{pmatrix} \上线{e} _1 ^ U \\ \ vdots \\ \上线{e} _l ^ U \结束{pmatrix}，\，\，E ^ I = \开始{pmatrix } \ overline {e} _1 ^ I \\ \ vdots \\ \ overline {e} _m ^ I \ end {pmatrix}，\ overline {e} _i ^ U \ in \ mathbb {R} ^ k，\ overline { e} _i ^ I \ in \ mathbb {R} ^ k$$

以及抵消 $$$\ overline {b} ^ U，\ overline {b} ^ I \ in \ mathbb {R} ^ k$ 。 使用用户和产品视图：

（2.12）

$$

$$\ overline {p} ^ U = \ overline {x} ^ U \ cdot E ^ U = \ sum_ {j = 1} ^ l x_j ^ U \ cdot \ overline {e} _j ^ U，$$

（2.13）

$$

$$\ overline {q} ^ I = \ overline {x} ^ I \ cdot E ^ I = \ sum_ {j = 1} ^ m x_j ^ I \ cdot \ overline {e} _j ^ I，$$

获得对的评分 $$$（u，i）$ ：

（2.14）

$$

$$\ hat {r} _ {ui} = <\上线{p} ^ U，\上线{q} ^ I> + <\上线{x} ^ U，\上线{b} ^ U> + <\上线{x} ^ I，\上划线{b} ^ I>。$$

损失函数

在我们的情况下，有必要为特定用户对产品进行排名，以使相关性更高的产品比不相关性更高的产品具有更高的评分。 LightFM具有多种丢失功能：

1. 后勤是一种需要否定的实现，在大多数任务中都没有明确提出。
2. BPR [3]是为了最大化特定用户在正面和负面例子之间的评分差异。 负值使用引导采样获得。 该算法中使用的质量功能类似于ROC-AUC。
3. WARP [4]与BPR的区别在于对否定示例进行采样的方法和损失函数（也都排名），但同时为用户优化了最佳建议。

实际实施

为了在给定的时间内建立建议，使用了Spark上的并行实现。 为每个商店启动一个独立的任务，其执行由luigi控制。

数据预处理

数据预处理由自动可扩展的Spark SQL工具执行。 最终模型中选择的功能是带有标准转换的商品和目录的文字描述。

与Spark互动时对我们有帮助的是：

1. 按商店对准备好的数据（用户和产品交互的矩阵，它们的标志）进行分区。 这样，您可以在培训阶段节省从HDFS读取数据的时间。 否则，每个任务都必须将数据读入Spark内存并按商店ID对其进行过滤。
2. 将数据保存到Spark或从Spark接收数据是分部分完成的。 这是由于以下事实：在任何这些操作期间，数据均已加载到JVM内存中。 为什么不只是增加JVM的内存？ 首先，可用于训练模型的内存减少，其次，不需要在JVM中存储任何内容，在这种情况下，它充当临时存储。

模型训练

每个商店的模型都在其自己的Spark容器中进行训练，因此您可以同时为商店运行任意数量的任务，仅受群集资源限制。

LightFM缺乏早期停止机制，因此，当目标指标没有增加时，我们会在额外的迭代训练上花费额外的资源。 我们选择AUC作为指标，并通过实验确定了其与CTR的关系。

表示：

$$$S$ -用户和产品（即对）之间的所有已知交互 $$$（u，i）$ ，
$$$我$ -很多商品 $$$我$ ，
$$ -很多用户 $$$u$ 。
对于特定用户 $$$u$ 还介绍 $$$I_ {u} = {i∈I：（u，i）∈S}$ -用户与之互动的许多产品。 AUC可以计算如下[参考]：

（3.1）

$$

$$AUC（u）= \ frac {1} {| \ mathcal {I} _u || \ mathcal {I} \ setminus \ mathcal {I} _u |} \ sum_ {i \ in \ mathcal {I} _u} \ sum_ {j \ in \ mathcal {I} \ setminus \ mathcal {I} _u} \ delta（\ hat {r} _ {ui}> \ hat {r} _ {uj}），$$

（3.2）

$$

$$AUC = \ frac {1} {| \ mathcal {U} |} \ sum_ {u \ in \ mathcal {U}} AUC（u）$$

在公式（3.1）中，我们需要计算所有可能对的等级 $$$（u，i）$ （ $$$u$ 固定），以及比较来自以下项目的评分 $$$\ mathcal {I} _u$ 评分为 $$$\ mathcal {I} \ setminus \ mathcal {I} _u$ 。 假设用户与分类的少量部分进行交互，则计算的复杂度为 $$$O（| \ mathcal {U} || \ mathcal {I} |）$ 。 同时，FM训练的一个时代使我们付出了代价 $$$O（| \ mathcal {U} |）$ 。

因此，我们修改了AUC的计算。 首先，您应该将样本分解为训练 $$$\ mathcal {S} ^ {train} \子集\ mathcal {S}$ 和验证 $$$\ mathcal {S} ^ {val} \子集\ mathcal {S}$ 和 $$$\ mathcal {S} ^ {val} = \ mathcal {S} \ setminus \ mathcal {S} ^ {train}$ 。 接下来，我们使用抽样创建许多用户进行验证 $$$\ mathcal {U} ^ {val} \子集\ {u \ in \ mathcal {U}：（u，i）\ in \ mathcal {S} ^ {val} \}$ 。 对于用户 $$$u$ 来自 $$$\ mathcal {U} ^ {val}$ 积极阶层的要素将被认为是许多 $$$\ mathcal {I} _u ^ {+} = \ {i \ in \ mathcal {I}：（u，i）\ in \ mathcal {S} ^ {val} \}$ 类似的 $$$\ mathcal {I} _u$ 。 作为否定类的元素，我们取一个子样本 $$$\ mathcal {I} _u ^ {-} \子集\ mathcal {I}$ 这样就没有元素 $$$\ mathcal {I} _u$ 。 子样本大小可以与大小成正比。 $$$\ mathcal {I} _u ^ {+}$ 那就是 $$$| \ mathcal {I} _u ^ {-} | = c \ cdot | \ mathcal {I} _u ^ {+} |$ 。 然后用于计算AUC的公式（3.1），（3.2）将会更改：

（3.3）

$$

$$AUC（u）= \ frac {1} {| \ mathcal {I} _u ^ {+} || \ mathcal {I} _u ^ {-} |} \ sum_ {i \ in \ mathcal {I} _u ^ {+}} \ sum_ {j \ in \ mathcal {I} _u ^ {-}} \ delta（\帽子{r} _ {ui}> \帽子{r} _ {uj}），$$

（3.4）

$$

$$AUC = \ frac {1} {| \ mathcal {U} ^ {val} |} \ sum_ {u \ in \ mathcal {U} ^ {val}} AUC（u）$$

结果，由于我们只占用固定的一部分用户，并且集合 $$$\ mathcal {I} _u ^ {+}$ 和 $$$\ mathcal {I} _u ^ {-}$ 体积小。 在AUC（3.4）停止改进之后，商店的学习过程停止。

搜索相似的对象

作为item2item任务的一部分，您必须为每个项目选择 $$$n$ （或尽可能相似的产品），以使横幅的可点击性最大化。 我们的假设：横幅广告的候选人必须从顶部开始考虑- $$$k$ 在空间上最接近的嵌入。 我们测试了以下用于计算“最近邻居”的方法：Scala + Spark，ANNOY，SCANN，HNSW。


对于拥有50万个对象的商店的Scala + Spark，计算诚实的余弦度量需要15分钟，并且需要大量的群集资源，为此我们测试了用于寻找最近邻居的近似方法。 在研究SCANNs方法时，以下参数会有所不同： bucketLimit ， shouldSampleBuckets ， NumHashes和setSignatureLength ，但是与其他方法相比，结果却不尽人意（很多不同的对象掉入了存储桶中）。 ANNOY和HNSW算法显示的结果与诚实余弦相当，但工作速度更快。

	20万种产品		50万商品		2.2m产品
演算法	烦恼	ns	烦恼	ns	烦恼	ns
建立时间 指数（秒）	59.45	8.64	258.02	25.44	1190.81	90.45
总时间（秒）	141.23	01/14	527.76	43.38	2081.57	150.92

由于HNSW的运行速度比所有算法都要快，因此我们决定停止使用它。
我们还将在Spark容器中搜索最近的邻居，并使用适当的分区将结果写入Hive。

结论

回想一下：我们使用WARP训练模型，使用AUC进行早期停车，并使用A / B测试对实时流量进行最终质量评估。

我们相信，在这个地方-组织实验并选择横幅的最佳组成-数据结束，科学开始了。 在这里，我们学习确定为重新定位有效的产品显示推荐是否有意义； 确切显示多少建议； 浏览了多少产品，等等。 我们将在以下文章中讨论这一点。

在本文开头描述的范式框架内对算法进行了进一步的改进-搜索通用嵌入，以将所有商店的产品放置在一个空间中。

感谢您的关注！

文学作品

[1] Ricci F.，Rokach L.，Shapira B.推荐系统手册简介
//推荐系统手册。 -Springer，马萨诸塞州波士顿，2011年。-S. 147160。

[2] Rendle S. Factorization机器// // 2010 IEEE国际数据挖掘会议。 -IEEE，2010年。-S. 995-1000。

[3] Rendle S.等人。 BPR：来自隐式反馈的贝叶斯个性化排名
//人工智能不确定性第二十五次会议论文集。
-AUAI出版社，2009年。-S. 452-461。

[4] Weston J.，Bengio S.，Usunier N. Wsabie：扩大到大词汇量图像注释//第二十二届国际人工智能联合会议。 -2011年。