从启发式学习到机器学习：Citymobil中的搜索建议

你好！我叫Mikhail Dyachkov，在Citymobil从事机器学习。今天，我将向您介绍有关生成最终目的地搜索建议的新算法。您将学到看似简单的任务如何变成一个有趣的场景，我们希望借助它可以使用户的生活更加轻松。我们将继续密切监视新算法的工作，随后将对其进行调整，以保持较高的排名质量。对于所有用户，我们将在接下来的几周内推出该算法，但是我们已经准备好谈论从启发式方法到机器学习算法并将其推广到运营的漫长旅程。



我认为从用户界面的角度描述出租车订单方案的理想世界视图是值得的。我希望我们的应用程序了解用户要离开哪辆车的位置/位置/时间/时间。在本文中，我们将研究我们的解决方案来回答“ where”问题。



搜索建议是第一个屏幕上的中心元素之一（用户登录后看到的一个元素）。在地理搜索小组中，我们称它们为“ sajest”（根据英语建议）。它们基于销的当前位置（即落点）和一天中的时间为用户提供其旅行历史记录的最终路线地址（“ B”点），而无需输入搜索查询。我们尝试借助sagests帮助用户“一键式”形成订单。在当前版本的客户端iOS应用程序中，最复杂的情​​况是：







地理搜索由于生成搜索结果的算法而可能会影响客户端应用程序最重要的产品指标之一，例如订购出租车的时间（订购时间或T2O）以及客户形成订单的动作数（订单动作或A2O））。因此，我们决定开发一种算法，该算法将针对一天中的给定位置和时间预测路线最可能的终点（点“ B”）。

启发式

地理搜索团队的后端开发人员之一（瓦西列斯克，您好！）想出了一种相当简单的启发式方法来生成对起点“ A”和终点“ B”均有效的最有趣的东西。应当立即指出，启发式方法不适用于用户的旅行历史记录，而不适用于用户点击搜索结果的历史记录，这会带来一些问题。这些对象我们称之为“峰”（来自英文。拾）。启发式看起来像这样：

1. 对于当前用户，我们将利用他的所有历史峰值。
2. 我们对它们进行过滤，使那些目标相同（从/到那里）。
3. , , 300 ( «» — 300 «», «» — 300 «»). , GPS- .
4. , , , , , .
5. , , 3:00 14:00, , .
6. - (), , - .
7. .

该算法工作了一段时间，并且通常对MVP很有用（我们稍后会讨论指标），但是它有很多缺点。除了相当原始的工作逻辑外，它还不是基于行程，而是基于用户的选择。因此，有时用户获得的搜索结果不明显。而且，由于存储峰历史的“特定”方式，进行快速分析非常困难。基于此，我们决定尝试应用机器学习。接下来，我们将考虑排名问题的表述，并将我们的问题简化为二进制分类。

排名问题陈述

在讨论功能，指标和模型之前，我们需要弄清楚我们要解决的问题是什么。让我们进行迭代，首先尝试为排名问题制定一个一般的表述。看起来像这样：



$$$X$ -很多物体。



$$$X^l = \{x_1, \dots, x_l \}$ -训练样本。 



$$$i \prec j$ -成对正确顺序 $$$(i, j)$



目标：建立排名功能 $$$a: X \rightarrow ℝ$，与 

$$

$$i \prec j ⇒  a(x_i) < a(x_j)$$

现在，让我们制定通过查询对搜索结果进行排名的任务。它与一般排名问题的不同之处在于，出现了两组而不是我们需要排序的一般对象集$$$D$ 和 $$$Q$ -许多文件和查询。



$$$D$ -收集文件（答案）。



$$$Q$ -很多要求。



$$$D_q \subseteq D$ -查询q找到的文档集。



$$$X = Q \times D$ -对象是成对的“请求，文档”： $$$x \equiv (q, d), q \in Q, d \in D_q$



$$$Y$ -一组有序的评分（评级）。



$$$y(q, d): X \rightarrow Y$-相关度分数。



分数越高$$$y(q, d)$，文件越相关 $$$d$ 请求 $$$q$...



仅在相同查询找到的那些文档之间定义正确的顺序$$$q$： 

$$

$$(q, d) \prec (q, d') \Leftrightarrow y(q, d) < y(q, d')$$

在我们推荐路线终点的任务中，等级组是二进制的。对于用户，建议的地址可能是相关的，也可能是不相关的（不包括具有多个端点的复杂路由的情况）。如果我们在用户的上下文中考虑任务，那么$$$q$-对服务的请求，其中包含客户的ID，地理位置，日期和时间；$$$D_q$-用户旅行的许多历史终点“ B”（我们仅根据过去旅行的地址提出建议）。每个有效答案$$$d \in D_q$ 根据要求 $$$q$ 可能与用户相关（从当前时间点到当前时间，用户需要准确到达此处）或无关。



为了完整起见，仅描述创建带有目标的请求-响应对样本的过程。为简单起见，请考虑一位旅行了5次的客户。让我们从头到尾对这些旅行进行排名。对于第一次旅行，我们对用户的旅行一无所知，因此我们无法使用描述的机器学习算法向他提供摘要（新用户的启发式方法在这里起作用）。对于第二次旅行，我们知道第一次旅行的最终目的地，如果用户成功通过了后处理程序（位于距当前位置1公里以上，位于同一地区等），我们可以将此地址提供给用户。对于第三次旅行，我们可能已经从一到两个可能的烦恼，如果第二次行程的结束地址与第一次行程的结束地址相同，并且结束地址不同。如果最有趣的点与端点“ B”重合（即它落入固定大小的相同十六进制），则将目标设置为1，否则设置为-0。根据此算法，我们形成“请求-（可能）响应”形式的各种对“对于每个客户。



因此，我们已将排名问题简化为二进制分类问题。现在我们可以讨论质量评估指标。

指标

在对问题进行排名时，该度量标准显示文档中正确答案的比例 $$$D_q$ 到顶部 $$$n$ 要求时的排名列表 $$$q$被称为Precision @ n。我们对Precision @ 1/2/3感兴趣，因为前三个排名的总点击率约为95％。同时，只有一个正确的最终地址（自然地，如果用户希望从其历史记录中删除该地址），因此，该指标仅显示正确的最终点“ B”落入该地址的前1/2/3个地址的情况的比例建议我们的算法。



回想一下我们的问题$$$Y = \{0, 1\},\; y(q, d)$ -相关性 $$$a(q, d)$是必需的排名功能。然后Precision @ n可以写成：

$$

$$P_n(q) = \frac{1}{n}\sum_{i=1}^{n} y(q, d_q^{(i)})$$

标志和型号

我们问题中模型的特征可以分为几个部分：

• 仅用于文件 $$$d \in D_q$ （最终地址，点“ B”）。
• 仅用于请求 $$$q$ （起始地址，点“ A”）。
• 共同要求和文件 $$$(q, d)$ （从“ A”到“ B”的路线）。
• 用户通用。

这是每个例子。



仅用于文档的符号示例（“ B”点）：

1. 最近K天到达“ B”点的旅行次数。
2. 指向星期几和一天中的时间点“ B”的旅行次数。
3. 上一次到达“ B”点的时间是什么时候。
4. 标记上一次行程指向“ B”。
5. 是“ B”点选定的地址/住所/工作。

仅用于请求的特征示例 $$$q$ ( «» + /):

1. , .
2. «».
3. «» K .
4. «» .
5. «» //.
6. / $$$q$.
7. «».

, $$$(q, d)$ ( «» “”):

1. , .
2. .
3. .

:

1. K .
2. .
3. 历史行程统计信息（平均值，分位数，行程中间距离等）。

结果，我们获得了100多个描述一对“请求文档”对象的功能。由于我们要在1/2/3处使Precision最大化，因此逻辑上我们需要预测用户前往特定目的地的概率，并根据获得的概率对可能的候选者进行排名。我们尝试了不同的算法和不同的损失函数，并决定对树和logloss进行梯度增强。使用启发式方法时获得的结果：

生产

自然，在提出一些复杂的算法，功能和训练模型之前，您需要考虑所有这些如何在负载下进行战斗，同时不要忘记扩展。与后端开发团队聚会之后，我们勾勒出了服务外观的大致轮廓。我们决定将训练有素的机器学习模型包装在async-await网络框架Sanic中，搜索服务将向其发送请求。除了垂直扩展，我们还实现了部署到多台计算机的功能。对服务的请求将被发送到负载均衡器的URL，然后将使用循环算法代理到该计算机或该计算机。在实现服务的第一个原型之后，我们意识到我们可以大大减少MySQL中的查询量。由于选择进给点时针脚的任何移动都是一个新的搜索请求，因此是对我们的服务的，因此，我们认为我们可以将一个存储有用户行进历史记录的缓存存储到请求到Redis的N分钟之间。因此，我们将基座的负载减少了三倍。结果，服务方案可以表示如下：







我们将对服务的请求及其响应存储在ElasticSearch中，并传输和监视负责NewRelic中工作稳定性的指标。



我们服务的一般工作流程：

1. 搜索服务将请求发送到搜索提示服务。
2. 平衡器选择其中一台机器并将此请求发送给它。
3. 在机器内部，请求被发送到一个开放的工作人员或进入队列。
4. 在工作人员内部：
   1. 我们验证传入的请求。
   2. 我们在Redis中进行请求，如果没有用户的订单历史记录，则转到MySQL并将接收到的数据写入Redis。
   3. 我们进行基本数据预处理并收集模型的特征。
   4. 我们predict_proba()根据所有生成的言语进行处理，并按“概率”对它们进行排序。
   5. 我们对数据进行额外的后处理并形成响应。
   6. 我们将答案返回搜索服务。

下一步是什么？

现在，我们正在使用折返测试积极测试我们的模型，以便随后得出结论并对该算法实施其他附件以提高排名质量。将来，我们将尝试为模型添加其他功能，并与产品设计人员一起为“显示”装袋准备新的解决方案。当然，如果我们的应用程序本身了解用户想要离开的车的位置/时间/地点/位置，那将是很棒的。我们四面八方工作，以便一键即可真正完成出租车订单。