🤼 👸🏾 😄 Okko的建议：如何通过乘以两个矩阵来赚取数亿美元 📕 ㊗️ 🎠

Rekko-Okko在线电影院的个性化推荐

您是否熟悉这样一种情况，您花费大量时间选择与观看时间相当的电影？对于在线电影院的用户来说，这是一个普遍的问题，对于电影院本身来说，这就是利润的损失。

幸运的是，我们拥有Rekko-一种个人推荐系统，该系统已成功地帮助Okko用户一年来从一万多个内容中选择电影和系列。在本文中，我将从算法和技术的角度告诉您如何安排它，我们如何进行它的开发以及如何评估结果。好吧，我还会告诉您年度A / B测试的结果。

首先，有一点历史。 Okko于2011年作为Iota的一部分开始成立，以Yota Play的名字开始。

旧的Yota Play界面

用户早在2011年就接受了在互联网上合法观看电影的想法

用户评论在线电影院中内容的成本

Yota Play当时是一项独特的服务：它与社交网络紧密集成，并在服务的许多部分中使用了朋友观看和评级的电影信息，包括推荐信息。

Yota Play的社交推荐

2012年，决定用算法性建议补充社会性建议。这就是“甲骨文”的出现-在线电影院Okko的第一个推荐系统。以下是他的设计文档的摘录：

已实施的个人推荐系统使用了类似的方法。级别的等级从“无”（空虚，缺席）到“所有”（完全，最大）。在[127 .. + 127]范围内，0-是中间值或“范数”。在此规模上，还评估了产品主角的同情度和产品的主观价格以及“红色”度。例如，宇宙的大小估计为+127（以维度为单位），而黑暗的估计数目为127（以光强度为单位）。

在提出建议时，不仅背景而且特定用户的性质也很重要。个人资料还包含4种字符类型比例（根据K. Leonhard的指示，学究、,脚，容易受刺激）。

大脑的生理极限并不取决于一个人的性格，也不取决于他的友善和友善。这位教授说，新皮层存在限制，新皮层负责清醒的思想和言语。在已实施的系统中也要考虑到这种限制，尤其是在为学究类型的角色制定建议时，以及在社交关系中形成此类用户的样本时。

拍摄自电影《拉斯维加斯的恐惧与厌恶》

正如您已经了解的那样，时代是疯狂的，大脑的生理极限并不局限于任何事物，超频的新皮层本身可以以光速生成个人推荐。因此，该模型决定立即投入生产。

据人们从尚存的古代文明的作品中可以判断，“ Oracle”是协作过滤算法的狂野组合，充分地运用了业务规则。

体系结构“ Oracle”

到2013年中，每个人都松了一口气，最终决定检查推荐机器的质量。为此，在应用程序的主要部分中填充了受过专门训练的编辑器，并启动了A / B测试：一半的用户看到了算法的输出，一半的用户看到了编辑器的选择。

现在，我们正在阅读有关人工智能的下一个胜利的文章，并恐怖地想象他将失去我们工作的那一天。然后，在2013年，情况有所不同：一个人英勇地击败了汽车，在内容部门创造了更多工作。 Oracle已关闭，以后再也不会打开。不久，所有社交筹码都消失了，Yota Play变成了Okko。

重命名后立即在线电影院Okko的界面

2013年至2016年是人工智能的“冬天”和内容部门的极权统治的标志：该服务中没有个人推荐。

到2017年年中，很明显，您不能再这样生活了。 Netflix的成功举世闻名，整个行业正朝着个性化快速发展。用户不再对“哑”静态服务感兴趣，他们已经开始习惯于“智能”界面，完全理解它们并预测所有需求。

作为第一次迭代，我们决定与两家大型俄罗斯建议供应商整合。每天，这两种服务都会从Okko那里获取必要的数据，并在远程服务器上用黑匣子沙沙作响，然后上传结果。

根据六个月A / B测试的结果，对照组和测试组之间没有发现统计学上的显着差异。

在A / B测试结束时，我来到Okko，与分析主管Mikhail Alekseev（ malekseev ）一起使该服务真正变得个人化。不到一年，Danil Kazakov（ xaph ）加入了我们，最终组成了现役团队。

一般注意事项

当一个国际社会长期研究的业务问题浮出水面并且需要迅速解决时，很容易采用您拥有的第一个流行的深度神经网络解决方案，用铁锹将数据推入其中，将其推入并扔入产品中。

来自xkcd.com的有关机器学习的漫画书

最主要的是不要屈服于这种诱惑。科学界的任务-在腐烂和合成的数据集上达到最大速度-通常与业务任务不符-赚更多的钱，而花更少的资源。

不，这并不意味着您不需要循环网络，并且可以使用k最近邻方法来赚取数十亿美元。可能会发现，根据您的数据，经典矩阵分解将使您每年可以有条件地赚取额外的1亿，而经常性网络可以赚取额外的收入-每年为1.05亿。同时，为这些相同的网络维护一机架带有视频卡的服务器每年将花费1000万，并且需要额外几个月的开发和实施，而将现成的矩阵分解简单地集成到服务和邮件列表的另一部分中将需要一个月的改进，并将再提供100个有条件的百万每年。

因此，重要的是要从基础知识-成熟的基础方法开始-走向越来越现代的方法，一定要衡量和预测每种新方法将对业务产生什么影响，将花费多少成本以及将使您获得多少收入。

Okko可以很好地测量。从字面上看，我们在A / B测试中对每一项新功能，每一项创新都进行了A / B测试，并检查了效果是否具有统计学意义，并且只有在做出是否接受新功能的决定之后才进行检查。

例如，当前的Rekko仪表板将控件组和测试组的50多个指标进行了比较，包括收入，服务花费的时间，选择电影的时间，按订阅观看的次数，转换为购买和自动续订等。是的，我们仍然保留一小部分从未收到个性化推荐的用户（对不起）。

关于推荐系统

首先，简要介绍推荐系统。

推荐系统的目标是针对每个用户 $u \ in$ 关于他与元素互动的故事 $我\在$ 在所有元素的集合上建立顺序关系。这意味着：无论我们采用两个任意元素，我们总是可以说哪个更适合用户，哪个更不适合。

许多电影中等级关系的插图

这个相当普通的任务可以简化为一个简单的任务：将元素映射到已经定义了顺序关系的集合。例如，在一组实数上。在这种情况下，每个用户和每个元素都必须能够预测某个值-该用户偏爱该元素的程度。

许多电影到许多实数的映射的插图

通过在元素上建立顺序关系，我们可以解决许多业务问题，例如，从所有元素N中选择与用户最相关的元素，或者根据用户的偏好对搜索结果进行排序。

理想情况下，我们需要一整套上下文相关的订单关系。如果用户进入了“动作”系列，则他很可能更喜欢电影“驱逐舰”而不是电影“奥斯卡”，但是在“电影与西尔维斯特·史泰龙”电影中，偏好可能恰好相反。可以针对星期几，一天中的时间或用户从中输入服务的设备给出类似的示例。

考虑到局部，将多部影片映射到多个实数的插图

传统上，所有用于构建个人推荐的方法都分为三大类：协作过滤（CF），内容模型（内容模型，CM）和结合了前两种方法的混合模型。

协作过滤方法使用有关所有用户和所有元素交互的信息。通常，此类信息以稀疏矩阵的形式表示，其中行对应于用户，列对应于元素，并且用户和元素包含表征它们之间交互的值，如果没有交互则包含空格。在这里构造顺序关系的任务减少到填写丢失的矩阵元素的任务。

协作过滤方法的交互矩阵图

通常，这些方法易于理解和实施，速度很快，但效果并不理想。

内容模型-用于解决分类或回归问题的任意机器学习方法，由一组特定的参数进行参数化 $\ theta$ 。在入口处，它们接受用户的属性和元素的属性，并且输出是给定元素与此用户的相关程度。此类模型不是在所有用户和所有元素的交互（例如协作过滤方法）上讲授的，而只是在个别先例上讲授的。

内容模型图

通常，此类模型比协作过滤方法要准确得多，但是它们的速度要慢得多。想象一下，如果我们具有某种通用形式的功能，可以接受用户和元素的符号作为输入，那么必须为每对调用它 $（u，i），u \ in U，i \ in I$ 。对于一千个用户和一万个元素的情况，这是一百万个呼叫。

混合模型结合了这两种方法的优势，可以在合理的时间内提供质量建议。

当今最流行的混合方法是两层体系结构，其中协作过滤模型从所有可能的元素中选择少量（100-1000）的候选者，然后通过功能更强大的内容模型对其进行排名。有时可能会有几个这样的阶段来选择候选人，并且在每个新级别都使用越来越复杂的模型。

两层体系结构图

这种架构具有许多优点：

协作部分和内容部分没有互连，可以分别使用不同的频率进行培训；
质量总是比单独的协作模型更好；
速度远高于内容模型的速度。
“免费”是从协作模型中获取向量，然后可以将其用于解决相关问题。

如果我们谈论特定技术，那么会有很多可能的组合。

作为协作部分，您可以接收用户订阅，流行内容，用户朋友中的流行内容，可以应用矩阵或张量分解，训练DSSM或具有相当快速预测的任何其他方法。

作为内容模型，通常可以使用任何方法，从线性回归到深层网格。

在Okko，我们目前专注于矩阵分解与WARP损失以及树上梯度增强的结合，我现在将对其进行详细讨论。

第一阶段：候选人甄选

如果我说矩阵分解算法是迄今为止最受欢迎的协作过滤方法，我想我不会说谎。该方法的本质从名称上很清楚：我们正在尝试通过两个较低等级的矩阵的乘积来介绍已经提到的用户与内容交互的矩阵，其中一个是“用户矩阵”，另一个是“元素矩阵”。通过这种分解，我们可以恢复原始矩阵以及所有缺失值。

矩阵分解图

当然，在这种情况下，我们可以自由选择可用矩阵和恢复矩阵的相似性的标准。最简单的标准是标准偏差。

让 $p_u$ -对应于用户的用户矩阵行 $u \ in$ 和 $q_i$ -与元素相对应的元素矩阵的列 $我\在$ 。然后，当矩阵相乘时，它们的乘积 $\ langle p_u，q_i \ rangle$ 表示给定用户与元素之间的预期互动程度。现在计算此数量与相互作用的先验已知值之间的标准差 $r_ {ui}$ 适用于所有互动用户和元素对 $（u，i）\在T $$ ，我们获得了可以最小化的损失函数。

m i n f r a c 1 l v e r t T r v e r t s u m_{（ u ， i ） i n T} （ r_{u i} - l a n g l e p_{u} ， q_{i} r a n g l e ）^{2}

$\ min \ frac {1} {\ lvert T \ rvert} \ sum _ {（u，i）\ in T}（r_ {ui}-\ langle p_u，q_i \ rangle）^ 2$

通常，仍会添加正则化。

m i n f r a c 1 l v e r t T r v e r t s u m_{（ u ， i ） i n T} （ r_{u i} - l a n g l e p_{u} ， q_{i} r a n g l e ）^{2} + l a m b d a （ s u m_{u} l V e r t p_{u} r V e r t^{2} + s u m_{i} l V e r t q_{i} r V e r t^{2} ）

$\ min \ frac {1} {\ lvert T \ rvert} \ sum _ {（u，i）\ in T}（r_ {ui}-\ langle p_u，q_i \ rangle）^ 2 + \ lambda（\ sum_u \ lVert p_u \ rVert ^ 2 + \ sum_i \ lVert q_i \ rVert ^ 2）$

这样的问题不是凸且NP复杂的。但是，很容易注意到，当固定其中一个矩阵时，任务变成相对于第二个矩阵的线性回归，这意味着我们可以迭代地寻找解决方案，交替冻结用户矩阵或元素矩阵。这种方法称为交替最小二乘（ALS）。

ALS的主要优点是速度和易于并行化的能力。为此，Yandex.Zen和Vkontakte非常喜欢他，用户和元素都达到数千万。

但是，如果我们谈论的是在一台计算机上可以容纳的数据量，则ALS不会受到批评。他的主要问题是他优化了错误的损失函数。记住制定推荐系统任务的制定。我们想要获得集合上的顺序关系，而是优化标准偏差。

举一个矩阵的例子来说，标准偏差最小，这很容易，但是元素的顺序被无可救药地破坏了。

让我们看看我们能做些什么。在用户的头部中，与用户交互的所有元素都以某种顺序排列。例如，他确定星际争霸要比《重力》好，《重力》和《外星人》都是同样出色的电影，而且都比《终结者》差一点。同时，他对用户尚未观看的电影也有一定的态度，每个人的态度都一样。他可能认为这样的电影比他所观看的电影先验地糟糕。或者，他可能认为例如普罗米修斯是一部糟糕的电影，而他尚未观看的任何电影都会比他更好。

用户脑中许多电影上的的顺序关系的图示

想象一下，根据服务中用户行为的某些迹象，我们可以通过使用函数将与之交互的元素显示为整数来恢复此顺序。 $\ rho：U \乘以我\到\ mathbb {Z}$ 。用户使用的许多电影 $u$ 互动，表示为 $I_u$ 。我们同意 $\ rho（u，j）= 0$ 如果用户尚未与电影互动 $j$ 那就是 $j \ notin I_u$ 。因此，如果用户认为电影不好，那么 $\ rho（u，i）<0$ ，如果好的话 $\ rho（u，i）> 0$ 。

描述用户-电影交互的的整数值的函数的图标

现在我们可以进入排名 $rank：U \乘以我\到\ mathbb {N}$ 。

r a n k （ u ， i ） = s u m_{j i n I ： r h o （ u ， i ） < r h o （ u ， i ）} t e x t r m I （ l a n g l e p_{u} ， q_{i} r a n g l e < 1 + l a n g l e p_{u} ， q_{j} r a n g l e ）

$rank（u，i）= \ sum_ {j \ in I：\ rho（u，i）<\ rho（u，i）} \ textrm {I}（\ langle p_u，q_i \ rangle <1 + \ langle p_u，q_j \ rangle）$

$\ textrm {I}（x）$ 这里表示指标函数，如果等于则等于1 $x$ 如果为true，则为零。

让我们停一分钟，想一想这样的排名意味着什么。

我们修复用户 $u$ ，这是一些特定的用户-我们对此不感兴趣。因此，其向量 $p_u$ 将被修复。

现在以他看过的任何电影为例，例如《星际穿越》。在公式中， $我$ 。接下来，我们发现用户认为比《星际穿越》更糟糕的电影。我们可以选择“吸引力”，“外星人”，“普罗米修斯”或他尚未看过的任何电影。

障碍的插图

采取“吸引力”。在公式中， $j$ 。 , «» $q_i$ , , «» $q_j$ . . «», «» , .

, , «». $r(u, i)$ , .

L = \sum_{u \in U, i \in I_{u}} ϕ (r a n k (u, i))

$L = \sum_{u \in U, i \in I_u} \phi (rank(u, i))$

$\phi: \mathbb{N} \to \mathbb{R}$ — , . , . , , .

ϕ (x) = \sum_{i = 1}^{x} \frac{1}{i}

$\phi(x) = \sum_{i=1}^x \frac{1}{i}$

. ? , , , , .

: . $j$ , $p(u, j) < p(u, i)$ , $\langle p_u , q_i \rangle < 1 + \langle p_u , q_j \rangle$ 。 $N - 1$ $N$ , $i$

r a n k (u, i) \approx ⌊ \frac{| I | - 1}{N} ⌋

$rank(u, i) \approx \lfloor \frac{\lvert I \rvert - 1}{N} \rfloor$

在哪里 $\lvert I \rvert$ — .

, , , .

WARP WSABIE: Scaling Up To Large Vocabulary Image Annotation . , , . 10%.

$\rho(u, i)$ 。 Okko :

;
;
( );
;
0 10.

, , . 399 , , . , . -, .

— . , explicit : , . , , implicit .

, $\rho(u, i)$ , . . , .

各种消费类型的排名图示例

$\rho(u, i) = -c$ , $\rho(u, i) = c$ , .

, Cython , LightFM .

:

, top-N : . , Approximate nearest neighbor algorithm based on navigable small world graphs .

, , , , . , - , . : , .

内容模型可以避免这些问题。它们功能强大，富有表现力，您可以在其中粘贴任何符号，但它们的运行速度非常慢。解决方案是不对所有元素都运行内容模型，而是对通过矩阵分解获得的候选对象运行内容模型。您可以处理的候选人数量可以多达多少，但最好至少是向用户显示的候选人数量的两倍。在我们的案例中，对于100部推荐电影，最佳解决方案是使用400部候选电影。

我们提交给内容模型的属性可以分为三类：用户属性，元素属性和交互符号。总共获得约50个标志。

作为用户的标志，我们使用他们在服务中行为的汇总统计信息，例如：

订阅观看百分比
用户从中登录应用程序的设备的分布，
服务中的生命，
等

对于电影，我们几乎使用所有可用的元信息：类型，发行年份，国家/地区，演员，导演，年龄限制等。综合的业务指标也非常有帮助：访问卡的百分比，观看次数，收藏夹添加项，通过查看方法，设备等进行分发

互动的迹象包括从选择候选人的阶段开始加快速度，以及所有先前的用户和电影互动的汇总统计数据，以及与所讨论电影相同的演员，导演，编剧的参与。

在使用二级模型对候选人进行排名时，最常见的问题是如何训练该模型。仅就矩阵分解而言，我们需要两组按时间分隔的组-训练和测试。在两阶段系统的情况下，我们将需要其中的三个-两次培训和一次测试。

将数据分为两个模型的训练和测试集的图标

在第一个训练集上，我们将训练第一级模型并建立候选人。从候选对象中排除在该集合中与用户进行交互的那些元素很重要。然后，我们将在第二个训练集中看到用户与哪个候选者进行了交互。我们称其为肯定，其余候选人为否定。这将是我们对内容模型的培训。

两层模型的训练集的形成的说明

为什么行得通？首先，我们精确地在将要使用的数据上训练模型-一级模型的输出。其次，在所有可能的负面示例中，我们采用最复杂的示例-一级模型调用的与用户相关的示例，但并非如此。

接下来是什么？最简单，最明显的解决方案是解决二进制分类问题，然后以概率降序对元素进行排序，这是一个很好的例子。但是，我们可以再次回忆起关于构建推荐系统的问题的陈述，了解二进制分类不是我们要解决的问题，然后再次讨论排名问题。

在XGBoost和LightGBM中，用于排名任务的主要损失函数是LambdaMART。如果您不进行详细介绍，则其背后的直觉非常简单。如果 $f（x_i）$ -例如模型输出 $x_i$ ，则该元素的概率 $我$ 的排名将高于元素 $j$ 将相等

P_ {ij} = P（i \ gt j）= \ frac {1} {1 + \ exp（f（x_j）-f（x_i））}}

$P_ {ij} = P（i \ gt j）= \ frac {1} {1 + \ exp（f（x_j）-f（x_i））}}$

然后可以将损失函数编写如下。

L = - Y_{i j} l o g P_{i j} - （ 1 - Y_{i j} ） l o g （ 1 - P_{i j} ）

$L =-Y_ {ij} \ log {P_ {ij}}-（1-Y_ {ij}）\ log {（1-P_ {ij}）}$

$Y_ {ij}$ 这是排名的真实概率。如果将其定义为1 $我\ gt j$ ，如果为0 $i \ lt g$ 如果是0.5 $i = j$ 。

与单级模型相比，两级模型的指标增加了50％。排名损失函数又增加了10％。

奖励：相关电影

记住，在我们方法的优点中，我提到了矩阵分解带来的“免费”向量，可以用来解决相关问题吗？因此，我们决定其中一项任务-寻找类似电影。

搜索类似电影的插图

解决耻辱的方法很简单：对于每部电影，我们都采用它的向量，并寻找与它的余弦距离最近的向量。看起来很合适。下一阶段是添加元信息并使用图算法。

类似雷科和他的电影

技术实施

除了算法部分之外，我还想谈一谈实现。 Rekko由三个部分组成：私钥，rekko任务和rekko服务。

Lynch在一台功能强大的机器上运行，定期唤醒，为微服务准备数据，并将其放入S3中。

微服务rekko-tasks和rekko-service以及所有其他微服务和数据库都位于Okko产品环境中。他们中的第一个不断监视S3的更改（如果有），将其下载并放入杂货店。第二个微服务使用这些计算结果，以便实时响应用户请求并计算他们的推荐。

服务架构

微服务是使用falcon，gunicorn和gevent用Python编写的，除了业务逻辑之外，它们不代表任何有趣的东西。与Okko产品环境中的所有其他微服务一样，它们由平衡器关闭。

林奇更有趣。

要为用户计算推荐的下一部分，需要做什么？至少：

下载自上次重新计票以来出现的新数据；
处理它们；
训练矩阵分解
建立候选人
重新安排候选人；
应用业务规则
卸载。

听起来似乎并不可怕，您可以将每个部分放到单独的函数中，然后依次调用它们：

data = extract_data() data = transform_data(data) mf_model = train_mf_model(data) candidates = build_candidates(mf_model) predictions = build_predictions(content_model, candidates) upload_predictions(predictions)

好吧，一切都做得很好，我们不同意吗？不完全是但是，如果整张纸落在某个地方怎么办？好吧，例如，由于内存不足。即使我们已经花费了几个小时来训练模型和构建候选者，我们也将不得不重新启动一切。

好吧，接下来让我们将所有中间结果保存到文件中，然后在跌倒之后检查哪些结果已经存在，恢复状态并从正确的时刻开始计算。实际上，这个想法比以前的想法还要糟糕。程序在写入文件的过程中可能会中断，尽管该程序存在，但处于错误状态。在最好的情况下，整个计算将失败；在最坏的情况下，它将以错误的结果结束。

好的，让我们写入原子文件。然后，我们将每个函数都放在一个单独的实体中，并指出它们之间的依赖关系。结果是一连串的计算，每个元素都可以执行或不执行。