時は金なり。 Yandex.Taxiに旅行のコストを正確に計算するように教えたように

製品やサービスを購入する前に、誰もが正確な価格を見つけようとします。 最終コストが計画よりもはるかに高い場合にストーリーが発生することは明らかです。 そして、車やアパートの修理でこれがすでに一般的になっている場合、他の場合では期待と現実の違いはかなり面倒です。



最近まで、タクシー乗車の費用も変動していました。 オンラインサービスでさえ、金額はおよそのみ計算されました-最終費用は、旅行の最後にのみ形成されました。 関税には、原則として、着陸のコスト（キロメートルおよび/または分を含む場合があります）、キロメートルのコスト、および分のコストの3つの要素が含まれます。 もちろん、旅行のおおよその価格をより早く計算することはできましたが、最終的には、たとえば、ドライバーが途中で交通渋滞に巻き込まれたという事実のために変更される可能性があります。 乗客がいつもこれを好まなかったのは明らかです。



Yandex.Navigatorのルーターのデータとトラフィックデータを使用して、Yandex.Taxiが最初から正確な価格を計算し、旅行後に変更されないようにするのは簡単なことではないようです。 しかし実際には、関税だけでなく、膨大な数の要因がコストに影響します。 数えるだけでなく重要です。 一方では、道路上の現在の状況だけでなく、たとえば、まだルート上にないがすぐに発生する交通渋滞も考慮に入れて、コストはユーザーにとって魅力的でなければなりません。 一方、価格は、ポイントAからポイントBへの経路が計画よりも長い場合でも長い場合でも、ドライバーが収益を失うことのないようにする必要があります。 この記事では、問題をどのように解決したか、Yandex.Taxiプラットフォームのすべての参加者に有益なバランスの取れたアルゴリズムを探した方法について説明します。

ルートと時間

旅行のバランスの取れたコストを計算できるようにするために、ルートの長さと期間を正確に予測することを学ぶ必要がありました。 ルーターの一般的な動作を見てみましょう。



これは、より単純な別のシステムである道路グラフに基づいて、ある地点から別の地点へのルートを構築するかなり複雑なシステムです。 グラフはご想像のとおり自然に見えます。各道路は1つまたは複数のエッジに対応しており、道路の交差点と分岐点は最上部にあります。 このグラフは方向性があります（道路も方向性があるため）。

_{^{これは、Yandexモスクワオフィスのエリアでのトラフィックグラフの外観です。}}

グラフエッジの最も重要な特性は、与えられた瞬間にそれらに沿って移動する平均速度です。 これは、現在の交通状況と道路のルール（制限速度など）に依存します。 毎秒、Yandexジオサービスのユーザーから数万の非個人的な信号（GPSトラック）を受信し、それらを集約してから、フィルタリングと補間により、信号のノイズを改善します。 最終段階では、現在のエッジ速度をリアルタイムで計算します（交通渋滞の仕組みの詳細については、 こちらをお読みください ）。



アドレス-仮想グラフの「上部」は、道路グラフのエッジとそれに沿った移動方向で構成されます。

アプリで旅行を予約するとどうなりますか？ 着陸地点（A）から目的地（B）までの最適なルートを見つけるためにルーターにリクエストを送信します。 ルーターは、ポイントAをグラフに投影して、その「アドレス」（エッジと方向の組み合わせ）を見つけます。 ポイントBでも同じことが起こります。そして、ここでシステムの最初の機能がすでに現れています。最短経路を決定するプロセスは、元の「自然な」道路グラフではなく、特定の「仮想」グラフで発生します。 その頂点はもはや交差点ではなく、まさに「アドレス」であり、エッジは道路ではなく「操作」、つまり、ある「アドレス」から別の「アドレス」への移行です。

_{^{道路（左）グラフと仮想（右）グラフの同じ軌跡の表現}}

_{^{直線の動きは、仮想グラフの操作で構成することもできます。便宜上、長い道路はデジタル化するといくつかのエッジに変わります}}

思い出すように、私たちのタスクは最適なルートを見つけることですが、もちろん、「自然な」グラフと「仮想の」グラフのどちらに構築しても、最終的な「物理的な」ルートは気にしません。 ただし、最初に最適性を決定する必要があります。 一方では、都市ではAからBへの最速の道であることは明らかです。他方では、2分を節約しますが、小さな通りに沿って大きな高速道路を迂回する困難なルートが時々ありますが、ターン数が多いため大幅になります運転手にとって「より高価」。 したがって、最初に、操作の「コスト」を定義する関数を定義し、機械学習を使用して最適化することにしました。



このような関数の最も簡単な例は、操作を構成するエッジの長さを、これらのエッジに沿った平均移動速度、いわゆる「幾何学的時間」で割ったものです。 このメトリクスは単純な点では優れていますが、多くの場合、特定の操作の多くの機能を考慮していません。 例として左折してください。 明らかに、規制された交差点の二次道路からそれを作ることは、高速道路に沿って移動するランプに曲がることとまったく同じではありません。 個々の状況の特徴により、操縦全体を完了するのにかかる時間が大幅に増加する可能性があり、それらを考慮するために、各操縦を一連の兆候で説明することにしました：エッジの長さ、幾何学的な移動時間、機能的な道路クラス、専用の公共交通レーンの存在など。 ここでは、「未来の兆候」が自然に発生しました。たとえば、この操作に近づくまでに発生する交通渋滞を考慮するための操作の時間を事前に計算できます。



その結果、ルートの「コスト」に影響する70以上の異なる兆候があり、その数は絶えず増加しています。なぜなら、兆候になり、タスクを支援できる新しい信号を絶えず追加しているからです。



このアプローチのもう1つの特徴は、最初のタスクを2つに分割したことです。ルートを構築し、それに沿った移動時間を明確にします。 これらのモデルをそれぞれ「ルート」と「一時」と呼びましたが、それらが互いにどのように異なるのか、なぜ2つのモデルが必要なのかを詳細に説明する価値があります。



ルートモデルは、ルートの長さとそれに沿った移動時間に基づいて、さまざまなオプションからポイントAからポイントBへの最適なパスを選択するのに役立ちます。 ここでの問題は、ルートモデルが非常に迅速に応答を返さなければならないことです。これは、システムがプロセスのさらなるチェーンでこれらの計算を使用する時間を必要とするためです。 1000回の操作ごとに100ミリ秒が多すぎるとしましょう。1桁少なくする必要があります。 ルートモデルは、計算の観点から可能な限り低くする必要があります。そのため、機能のセットの削減を考慮します。 しかし、すでに最適なルートがある場合-可能な限り正確にそのルートに沿った移動時間を知りたいが、ここではもはや速度で接続されていないので、100ミリ秒の余裕があります。



このために、時間モデルがあります。その唯一のタスクは、既に選択されているパスに沿った移動時間を明確にすることです。 時間モデルでは、各操作の属性の完全なセット、およびアプリケーションからのユーザーのリクエストのパラメーターが考慮されます。現在の現地時間とルートのさまざまなマクロ特性-マイレージ係数（AからBへの実際のルートの長さと直線のこれらのポイント間の距離の比率）などです。 出力では、時間モデルは指定された移動時間を示します。



要約すると、最初のタスク「ルートを最も正確に構築し、ルートに沿って移動する時間を予測する方法」は、いくつかのステップになりました。 最初に、交点の頂点とストリートエッジを持つ「自然な」グラフから、エッジが操作、つまり「アドレス」から「アドレス」への遷移である「仮想」グラフに切り替えました。 これらの各操作について、70を超える属性のセットで説明しました。 第二に、ルーターの動作を最適化するために、2つの予測モデルがあることを決定しました：多数の可能なルートから目的のルートを迅速かつ無作法に選択するルートモデルと、最適なルートの移動時間を指定するタイムモデルです。 次に、これらのモデルの機能について説明します。

モデル

ルートモデルと時間モデルの両方が互いに非常に異なるという事実にもかかわらず、実際には、ルートに沿った移動時間を計算するという同様のタスクがあります。 主な違いは、使用される計算の複雑さ、つまり定性的要因ではなく定量的要因です。 さらに、モデルは同じタスクを持っているため、トレーニングの観点からのアプローチは同じです。 1つのモデル（一時的なモデル）のみを取得し、そのモデルから「余分なものすべて」（たとえば、余分な標識）を削除して、より軽量なルートモデルを取得できます。



このアプローチは、機械学習の方法を統一しただけでなく、「教科書から」言うように時間モデルを教えることが古典的なタスクであるなど、他の理由でも有利であることが判明しました。 トラベルストーリーの膨大なデータベース、つまり、いくつかの機械学習方法のサンプルとして使用できる多くのルートと時間のペアがあります。 ルートモデルをトレーニングすることはより困難です。これは、より高速なルートを比較するために、すべてのドライバーにポイントAからポイントBまでのすべてのルートオプションに乗らせることはできないためです。 その結果、最初の段階では、時間モデルを教えることに集中しました。



最初のアイデアは、単にルートに沿った操縦の兆候の合計に対して線形モデルを使用し、トレーニングの目標として実際の移動時間を取ることでした。 このアプローチには、問題の特徴的な特性があります。実際、線形性です。 実際、この方法で計算された、たとえば2つの操作からなるルートの時間は、各操作で別々に計算された時間の合計に等しくなります。 さまざまな記号の解釈に困難はありませんでしたが、これは常に素晴らしいことです。記号の重みが大きい場合、記号は重要です。



それにもかかわらず、多くの利点にもかかわらず、このモデルを訓練する最初の試みは期待はずれでした。結果は「幾何学的時間」よりもわずかに優れていました。 、rib骨の形状、地上の道路の高さなどは「船外」のままでした。



予約時の旅行価格の計算方法は次のとおりです。





私たちが知っているように、カテゴリー変数を考慮することは常に困難な仕事であり、CatBoost全体を思いついたのは理由がないわけではありません。 それでも、決定木で使用されるN-way-splitに似た手法を使用して、この問題を解決しようとしました。



People's Mapsの分類に従って、道路は9つの機能クラスに分割され、2つの車道、ロータリー、出口、アンダースタディ、Uターンという5種類のデザインフィーチャもあります。 さらに、道路上には信号機があるかどうかがあります。これらはもう2つの意味です。 合計9x5x2 = 90の組み合わせがあります。 次に、このようなカテゴリの特徴の組み合わせごとに、残りの特徴を個別に考慮します。つまり、最初にサンプルを90個の独立したフラグメントに分割します。 この断片化により、合計で数千の機能を受け取りました。実際には、個々の組み合わせごとに、それぞれの機能を90回検査したためです。 大規模なトレーニングサンプルを考慮しても、この「アニメーション」は、モデルがすぐに再トレーニングを開始するという事実につながりました。 この問題は、L1の正則化（L2とは異なり、符号の影響を平準化でき、その下の重みをゼロにできる）によって部分的に解決されましたが、その結果、アプローチは一連の問題の観点から行き止まりとして認識されなければなりませんでした。 確かに、良いニュースがありました。このような一時的なモデルは、個々の操作で直線性があり、正しい方向に進んでいることを意味するため、すでにルートモデルとして使用できます。



それでも、問題は残っていました。非常に多くの兆候に対処する方法は？ Yandexには、 Matrixnetがあります。これは、決定ツリーの勾配ブースティングに基づく機械学習アルゴリズムで、数百または数千もの属性にうまく対処します。 まず、「額」アプローチを試み、Matrixnetをペアで「ルート-実際の移動時間」でトレーニングしました。 この方法はすぐに良い結果をもたらし、特徴の数を増やし、アルゴリズムのハイパーパラメータを微調整するさらなる作業が予測の質の明白な向上を得るのに役立ちました。 しかし、ただの「排気」にもかかわらず、単にMatrixnetの力のために、欠点もありました：

• 結果を解釈することは困難になりました。なぜなら、木の上の勾配ブーストの場合、実際にはブラックボックスで作業しているからです。 重みに応じてさまざまな記号を単純に解釈することはもはやできません。
• モデルから線形性が消失しました。ルートを2つの部分に分割し、モデルを適用して、ルート全体と同じ数を追加して取得することはできません。
• このようなモデルをルートモデルとして使用することは不可能でした。なぜなら、個別の操縦ではなく、ルート全体でトレーニングしたからです。

つまり、私たちのタスクでは、MatrixNetの「額」の使用は適合しませんでした。 その結果、2つの異なるモデルが残されました。それぞれが独自の点で優れていましたが、何か悪い点もありました。 そのようなパラダイム-線形（および再訓練を脅かす）ルートモデルとMatrixnetに基づく時間モデル-では、しばらく開発を試みましたが、魂は普遍的なソリューションを望んでいました。 そしてそれが見つかりました。

線形MatrixNet

よくあることですが、思いついたとき、アイデアは簡単にわかりました：Matrixnetをルート全体ではなく個々の操縦に適用し、エラーの関数として次の違いを取ります：ルート操縦の時間値の合計から目標移動時間を引いたもの。

$$

$$\ sum \ limits_ {r \ in routes}（T_r-\ sum \ limits_ {m \ in maneuvers} F（f_m））^ 2、$$

ここで、Tは目標、fは符号、Fは最適化された関数です。



このような機能は、検索のランキング（検索結果全体の最適化）のタスクに非常に似ていますが、適切な形式の既製のMatrixnetツールがなかったため、自分で実装する必要がありました。



適切な学習ペースとツリーの数を選択する苦労の末、「クリーンな」Matrixnetの品質をほとんど失うことなく、直線性を備えたモデルを手に入れることができました。 これにより、ルートモデルとして使用できるようになりました。また、デジタル化とCatBoostの使用により、カテゴリフィーチャの簡単な使用へのアクセスが開かれました。

結果

このストーリー全体には多くの時間がかかりましたが、最終的には速度に関するすべての要件を同時に満たし、時間の推定に必要な精度を提供するモデルが得られました。 タクシー旅行の費用を事前に正確に計算することを可能にしたのはこの最後の特性であり、旅行の終わりに変更することはできませんでした。



最後の質問-どのような結果が得られましたか、比較できるものはありますか？ もちろん、完全な答えを得るには、多くの要因の議論とかなり深刻な分析が必要です。 ただし、非常に単純な推定値を提供できます。

_{^{「そうだった-それはなった。」 左側には、旅行の費用のおおよその計算を含むアプリケーションの古いバージョンがあります。 右側は現在のバージョンで、旅行の正確な価格がさまざまな料金で表示されています。}}

明らかに、注文時でもYandex.Taxiアプリケーションで旅行の正確な価格を表示すること自体が、サービスをユーザーに透過的にする重要な利点であるため、ここではそれほどリスクはありませんでした。 困難であることが判明した唯一のことは、人が注文時に示した間違った地点Bに到着した場合、そのような場合には計算が無意味であるため、旅行全体がタクシーメーターを使用して再集計されることを説明することでした しかし、それは別の話です。 そのようなケースはほとんどないため、ほとんどのユーザーは旅行前に最終価格を表示するだけでなく、旅行の終わりにタクシーが渋滞しているか、運転手が周りを運転していても変わらないことを高く評価しました。 そしてもちろん、彼らはポイントBをより頻繁に示し始め、この場合のみそのような計算を受け取ることに気づきました。



冒頭で述べたように、アルゴリズムが十分に機能せず、価格がユーザーのみに適している場合、これはドライバーの収益の大幅な損失につながり、その結果、流出につながる可能性があります。 旅行前に価格が表示されるようになった後、注文の数が積極的に増え始めました-正確なコストが重要な多くの人々にとって、Yandex.Taxiを使用することは心理的に簡単になりました。 注文の増加により、タクシー車の利用率が大幅に増加しました。つまり、運転手が乗客を乗せたり注文したりするときのシフトあたりのシェアになり、アイドリング時間を無駄にしません。 これは、成長が他のサービステクノロジー（注文チェーンなど）の作業を改善したという事実によっても起こりました。 これは、ドライバーが前のクライアントを取得する前であっても、次のクライアントの検索を開始するアルゴリズムです。ドライバーがすぐに乗客と一緒に到着するエリアで検索します。

_{^{モスクワとその地域での機械リサイクルの成長。}}

リサイクルの増加により、ドライバーにとって最も重要な指標も増加しました-時間あたりの収入、シフトの時間あたりの平均収益：ロシアの平均では約15-22％増加しました。 一部の都市は本物のチャンピオンであることが判明しましたが、この数字はさらに大きくなりました。



CatBoost接続など、モデルの小規模および大規模な改善の多くを待っています。これについては、後で説明します。