🤵🏽 🙆🏾 👩🏿‍🚀 ヒューリスティックから機械学習まで：Citymobilでの検索候補 🤘🏽 🐰 🚣🏿

こんにちは！私の名前はミハイル・ディアコフです。シティモービルでは機械学習をしています。今日は、最終目的地の検索候補を生成するための新しいアルゴリズムについて説明します。一見単純なタスクがどのように興味深いシナリオに変わったかを学びます。その助けを借りて、ユーザーの生活を少し楽にすることができたと思います。新しいアルゴリズムの動作を引き続き注意深く監視し、その後、ランキングの品質を高いレベルに維持するために調整します。すべてのユーザーに対して、数週間以内にアルゴリズムを起動しますが、ヒューリスティックから機械学習アルゴリズムに至るまでの長い道のりについて話し、それを運用に移す準備ができています。

ユーザーインターフェイスの観点から、タクシー注文シナリオの理想的な世界観を説明することから始める価値があると思います。私たちのアプリケーションに、ユーザーがどこに/どこに/いつ/どの車で出発したいかを理解してもらいたいです。この記事では、「どこで」の質問に答えるためのソリューションを見ていきます。

最初の画面（ログイン後にユーザーに表示される要素）の中心的な要素の1つは、検索候補です。地理検索チームでは、それらを「sajest」と呼んでいます（英語の提案から））。これらは、検索クエリを入力せずに、ピンの現在の場所（つまり、ドロップポイント）と時刻に基づいて、旅行履歴から最終ルートアドレス（「B」ポイント）をユーザーに提供します。私たちは、ユーザーがサジェストの助けを借りて「ワンクリックで」注文を形成できるように努めています。クライアントiOSアプリケーションの現在のバージョンでは、sajestは次のよう

になります。検索結果を生成するためのアルゴリズムにより、ジオ検索は、タクシーの注文に費やされた時間（注文までの時間、またはT2O）や、クライアントアプリケーションの最も重要な製品指標の1つに影響を与える可能性があります。クライアントが注文を形成するために実行したアクションの数（注文するアクション、またはA2O）。したがって、特定の場所と時刻について、ルートの最も可能性の高いエンドポイント（ポイント「B」）を予測するアルゴリズムを開発することにしました。

ヒューリスティック

地理検索チームのバックエンド開発者の1人（vasilesk、こんにちは！）開始点「A」と終了点「B」の両方で機能するsajestを生成するための非常に単純なヒューリスティックを思い付きました。ヒューリスティックはユーザーの旅行履歴ではなく、検索結果のクリック履歴で機能するため、いくつかの問題が発生したことにすぐに注意してください。これらのオブジェクトを「ピーク」と呼びます（英語から。ピック）。ヒューリスティックは次のようになりました。

現在のユーザーについては、彼の歴史的なピークをすべて取り上げます。
それらをフィルタリングし、同じターゲット（from / where）を持つものを残します。
, , 300 ( «» — 300 «», «» — 300 «»). , GPS- .
, , , , , .
, , 3:00 14:00, , .
- (), , - .
.

このアルゴリズムはしばらくの間機能し、一般的にMVPには適していましたが（メトリックについては後で説明します）、いくつかの欠点がありました。かなり原始的な仕事の論理に加えて、それは旅行ではなく、ユーザーの選択に基づいていました。このため、ユーザーが不明瞭な検索結果を取得することがありました。また、ピークの履歴を保存する「特定の」方法のため、迅速な分析を行うことはかなり困難でした。これを踏まえて、機械学習を応用してみることにしました。次に、ランク付け問題の定式化を検討し、問題をバイナリ分類に減らします。

ランキング問題ステートメント

機能、メトリック、およびモデルについて説明する前に、解決しようとしている問題を理解する必要があります。繰り返し行って、最初にランキング問題の一般的な定式化を定式化してみましょう。次のようになります。

X

$X$ -たくさんのオブジェクト。

X^{l} = {x_{1}, \dots, x_{l}}

$X^l = \{x_1, \dots, x_l \}$ -トレーニングサンプル。

i ≺ j

$i \prec j$ -ペアで正しい順序

(i, j)

$(i, j)$

目的：ランキング機能を構築する

a : X \to ℝ

$a: X \rightarrow ℝ$ 、どれで

i ≺ j \Rightarrow a (x_{i}) < a (x_{j})

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

それでは、検索結果をクエリでランク付けするタスクを作成しましょう。ソートする必要のあるオブジェクトの一般的なセットの代わりに、2つのセットが表示されるという点で、一般的なランキングの問題とは異なります。

D

$D$ そして

Q

$Q$ -多くの文書と要求。

D

$D$ -ドキュメントのコレクション（回答）。

Q

$Q$ -たくさんのリクエスト。

D_{q} \subseteq D

$D_q \subseteq D$ -クエリqで見つかったドキュメントのセット。

X = Q \times D

$X = Q \times D$ -オブジェクトは「リクエスト、ドキュメント」のペアです。

x \equiv (q, d), q \in Q, d \in D_{q}

$x \equiv (q, d), q \in Q, d \in D_q$

Y

$Y$ -順序付けられた一連の評価（評価）。

y (q, d) : X \to Y

$y(q, d): X \rightarrow Y$ -関連性スコア。

スコアが高い

y (q, d)

$y(q, d)$ 、ドキュメントの関連性が高い

d

$d$ リクエスト

q

$q$ ..。

正しい順序は、同じクエリで見つかったドキュメント間でのみ定義されます

q

$q$ ：

(q, d) ≺ (q, d^{'}) \Leftrightarrow y (q, d) < y (q, d^{'})

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

ルートエンドポイントを推奨するタスクでは、評価のセットはバイナリです。ユーザーにとって、提案されたアドレスは、関連性がある場合と関連性がない場合があります（複数のエンドポイントを持つ複雑なルートの場合を除く）。ユーザーのコンテキストでタスクを検討すると、

q

$q$ -クライアントのID、地理的位置、日付と時刻を含むサービスへのリクエスト。

D_{q}

$D_q$ -ユーザーの旅行の多くの履歴エンドポイント「B」（過去の旅行のアドレスに基づいてのみ提案を行います）。そして、すべての有効な答え

d \in D_{q}

$d \in D_q$ 要求に応じて

q

$q$ ユーザーに関連する（現在の時点から、現時点では、ユーザーは正確にここに移動する必要があります）か、関連しないかのいずれかです。

完全を期すために、ターゲットとの要求と応答のペアのサンプルを作成するプロセスを説明するだけです。簡単にするために、5回の旅行をした1人の顧客を考えてみましょう。これらの旅行を最初から最後までランク付けしましょう。最初の旅行では、ユーザーの旅行について何も知らないため、説明されている機械学習アルゴリズムを使用してユーザーにサジェストを提供することはできません（新しいユーザーのヒューリスティックはここで機能します）。 2回目の旅行では、最初の旅行からの最終目的地がわかっており、後処理手順（現在の場所から1 km以上離れている、同じ地域など）に合格した場合、このアドレスをユーザーに提供できます。 3回目の旅行では、すでに1つから2つの可能なサジェットがある可能性があります。2番目のトリップの終了アドレスが最初のトリップの終了アドレスと同じである場合、および終了アドレスが異なる場合。 sajestがエンドポイント「B」と一致した場合（つまり、固定サイズの同じヘクスに落ちた場合）、ターゲットとして1を設定し、それ以外の場合は-0を設定します。このアルゴリズムに従って、「request-（possible）response」という形式のあらゆる種類のペアを形成します。「クライアントごとに。

したがって、ランク付けの問題をバイナリ分類の問題に減らしました。これで、品質メトリックについて説明できます。

指標

問題のランク付けにおいて、ドキュメントからの正解の割合を示すメトリック

D_{q}

$D_q$ 頂点に

n

$n$ リクエストに応じてランキングリスト

q

$q$ Precision @nと呼ばれます。最初の3つのポジションの合計クリックスルー率は約95％であるため、Precision @ 1/2/3に関心があります。同時に、正しい最終アドレスは1つだけです（当然、ユーザーが履歴からアドレスを残したい場合）。したがって、このメトリックは、正しい最終ポイント「B」が上位1/2/3アドレスに該当するケースの割合を示します。私たちのアルゴリズムを提案しました。私たちの問題でそれを思い出してください

Y = {0, 1}, y (q, d)

$Y = \{0, 1\},\; y(q, d)$ -関連性、

a (q, d)

$a(q, d)$ 必要なランキング機能です。その場合、Precision @nは次のように書くことができます。

P_{n} (q) = \frac{1}{n} \sum_{i = 1}^{n} y (q, d_{q}^{(i)})

$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」）：

過去K日間のポイント「B」へのトリップ数。
曜日および時刻ごとのポイント「B」へのトリップ数。
前回のポイント「B」への旅行はいつでしたか。
前回の旅行がポイント「B」に行われたことを示すフラグ。
ポイント「B」は選択された住所/自宅/職場です。

リクエストのみの特性の例 $q$ ( «» + /):

, .
«».
«» K .
«» .
«» //.
/ $q$ .
«».

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

K .
.
過去のトリップ統計（平均、クォンタイル、トリップ距離の中央値など）。

その結果、「request-document」オブジェクトのペアを記述する100を超える機能が得られました。Precision @ 1/2/3を最大化したいので、特定の目的地へのユーザーの旅行の確率を予測し、得られた確率に従って可能な候補をランク付けする必要があるのは論理的です。さまざまなアルゴリズムとさまざまな損失関数を試し、ツリーとログロスの勾配ブーストに落ち着きました。ヒューリスティックを使用したときに得られた結果：

	ヒューリスティック	MLアルゴリズム
精度@ 1	0.657	0.789
精度@ 2	0.719	0.872
精度@ 3	0.761	0.923

製造

当然のことながら、いくつかの複雑なアルゴリズム、機能、トレーニングモデルを考え出す前に、スケーリングを忘れずに、負荷がかかった状態でこれらすべてが戦闘でどのように機能するかを考える必要があります。バックエンド開発チームと集まって、サービスの外観の大まかな概要をスケッチしました。トレーニング済みのマシン学習モデルを非同期待機WebフレームワークSanicでラップすることにしました、検索サービスがリクエストを送信する先。垂直スケーリングに加えて、複数のマシンにデプロイする機能を実装しました。サービスへの要求はロードバランサーのURLに送信され、ラウンドロビンアルゴリズムを使用してこのマシンまたはそのマシンにプロキシされます。サービスの最初のプロトタイプを実装した後、MySQLのクエリの量を大幅に減らすことができることに気付きました。フィードポイントの選択によるピンのシフトは新しい検索リクエストであり、したがって私たちのサービスにとっては、Redisへのリクエストの瞬間からN分間、ユーザーの移動履歴をキャッシュに保存できると考えました。これにより、ベースへの負荷を3分の1に削減しました。その結果、サービススキームは次のように表すことができます。

サービスへのリクエストとその応答をElasticSearchに保存し、NewRelicでの作業の安定性に関与するメトリックを転送および監視します。

私たちのサービスの一般的なワークフロー：

検索サービスは、検索ヒントサービスにリクエストを送信します。
バランサーはマシンの1つを選択し、この要求をそのマシンに送信します。
マシン内で、要求は開いているワーカーの1つに送信されるか、キューに入ります。
労働者の内部：
1. 着信リクエストを検証します。
2. Redisでリクエストを行い、ユーザーの注文履歴がない場合は、MySQLにアクセスして、受信したデータをRedisに書き込みます。
3. 基本的なデータの前処理を行い、モデルの機能を収集します。
4. 我々はそれを行うpredict_proba()すべての生成sajestsと「確率」でソートそれらをに従って。
5. データの追加の後処理を行い、応答を形成します。
6. 回答を検索サービスに返します。

次は何ですか？

現在、スイッチバックテストを使用してモデルを積極的にテストし、その後結論を導き出し、アルゴリズムに追加のアドオンを実装してランキングの品質を向上させています。将来的には、モデルに機能を追加するとともに、製品設計者と協力して、サジェストの「表示」のための新しいソリューションを準備する予定です。もちろん、私たちのアプリケーション自体が、ユーザーがどこに、いつ、どこに、どの車に残したいのかを理解できれば素晴らしいと思います。タクシーの注文がワンクリックでできるように、あらゆる方向に取り組んでいます。

ヒューリスティックから機械学習まで：Citymobilでの検索候補