推奨事項の選択の品質と速度にどのように取り組むか

私の名前は Pavel Parkhomenko です。ML 開発者です。 この記事では、Yandex.Zen サービスの構造について説明し、その実装によりレコメンデーションの品質を向上できるようになった技術的な改善点を共有したいと思います。 この投稿では、数百万のドキュメントの中からユーザーにとって最も関連性の高いドキュメントをわずか数ミリ秒で見つける方法を学びます。 新しいドキュメントが数十分でベクトルを受信できるように、大きな行列 (数百万の列と数千万の行で構成される) を連続的に分解する方法。 ユーザー記事行列分解を再利用してビデオの適切なベクトル表現を取得する方法。

当社の推奨データベースには、当社のプラットフォームで作成され、外部サイトから取得されたテキスト記事、ビデオ、物語、短い投稿など、さまざまな形式のドキュメントが何百万件も含まれています。 このようなサービスの開発には、多くの技術的な課題が伴います。 その一部を次に示します。

• コンピューティング タスクを分割します。負荷の高い操作はすべてオフラインで実行し、リアルタイムでは 100 ～ 200 ミリ秒を担当するためのモデルの迅速な適用のみを実行します。
• ユーザーのアクションを迅速に考慮します。 これを行うには、すべてのイベントが即座にレコメンダーに配信され、モデルの結果に影響を与える必要があります。
• 新しいユーザーの行動にすぐに適応できるようにフィードを作成します。 システムに参加したばかりの人は、自分のフィードバックが推奨事項に影響を与えると感じるはずです。
• 新しい記事を誰に勧めるべきかをすぐに理解できます。
• 絶えず出現する新しいコンテンツに迅速に対応します。 毎日何万もの記事が公開されますが、その多くは存続期間が限られています (ニュースなど)。 これが、映画や音楽、その他の制作費が長く、息の長いコンテンツとは異なります。
• あるドメイン領域から別のドメイン領域に知識を移転します。 レコメンデーション システムがテキスト記事用にトレーニングしたモデルを備えており、それにビデオを追加すると、既存のモデルを再利用できるため、新しいタイプのコンテンツのランクが向上します。

これらの問題をどのように解決したかについて説明します。

候補者の選定

ランキングの品質を実質的に低下させずに、検討対象のドキュメントの数を数ミリ秒で数千分のXNUMXに減らすにはどうすればよいでしょうか?

多くの ML モデルをトレーニングし、それらに基づいて特徴を生成し、ユーザー向けにドキュメントをランク付けする別のモデルをトレーニングしたとします。 すべて問題ないのですが、ドキュメントが何百万もあり、推奨事項を 100 ～ 200 ミリ秒で作成する必要がある場合、すべてのドキュメントのすべての符号をリアルタイムで取得して計算することはできません。 タスクは、ユーザー向けにランク付けされる数百万の中から特定のサブセットを選択することです。 この段階は通常、候補者の選択と呼ばれます。 それにはいくつかの要件があります。 まず、ランキング自体にできるだけ多くの時間を残すために、選択は非常に迅速に行われなければなりません。 第二に、ランキング対象のドキュメントの数を大幅に減らしたので、ユーザーに関連するドキュメントを可能な限り完全に保存する必要があります。

候補者選択の原則は進化しており、現時点では次のような複数段階のスキームに到達しています。

まず、すべてのドキュメントがグループに分割され、各グループから最も人気のあるドキュメントが抽出されます。 グループには、サイト、トピック、クラスターを含めることができます。 ユーザーごとに、その履歴に基づいて、そのユーザーに最も近いグループが選択され、そこから最適なドキュメントが抽出されます。 また、kNN インデックスを使用して、ユーザーに最も近いドキュメントをリアルタイムで選択します。 kNN インデックスを構築するにはいくつかの方法がありますが、私たちの方法が最も効果的でした。 ニューサウスウェールズ州 (階層型ナビゲーション可能なスモールワールド グラフ)。 これは、数百万のデータベースからユーザーに最も近い N 個のベクトルを数ミリ秒で見つけることができる階層モデルです。 まず、ドキュメント データベース全体をオフラインでインデックス付けします。 インデックス内の検索は非常に高速に行われるため、強力な埋め込みが複数ある場合は、複数のインデックス (埋め込みごとに XNUMX つのインデックス) を作成し、それぞれにリアルタイムでアクセスできます。

各ユーザーにはまだ数万のドキュメントが残っています。 すべての機能を数えるとまだ膨大な量なので、この段階ではライト ランキング (機能が少ない軽量で重いランキング モデル) を使用します。 タスクは、重いモデルがどのドキュメントを上位に持つかを予測することです。 最も高い予測子を持つドキュメントは、重いモデル、つまりランキングの最終段階で使用されます。 このアプローチにより、ユーザーが考慮するドキュメントのデータベースを数十ミリ秒で数百万から数千に削減できます。

ランタイムの ALS ステップ

クリック直後のユーザーのフィードバックを考慮するにはどうすればよいでしょうか?

レコメンデーションにおける重要な要素は、ユーザーのフィードバックに対する応答時間です。 これは、新規ユーザーにとって特に重要です。人がレコメンデーション システムを使い始めたばかりのとき、その人はさまざまなトピックのドキュメントの非パーソナライズされたフィードを受け取ります。 彼が最初のクリックをしたらすぐに、これを考慮して彼の興味に適応する必要があります。 すべての係数をオフラインで計算すると、遅延によりシステムの迅速な応答ができなくなります。 したがって、ユーザーのアクションをリアルタイムで処理する必要があります。 これらの目的のために、実行時に ALS ステップを使用してユーザーのベクトル表現を構築します。

すべてのドキュメントのベクトル表現があると仮定しましょう。 たとえば、ELMo、BERT、またはその他の機械学習モデルを使用して、記事のテキストに基づいてオフラインで埋め込みを構築できます。 システム内でのユーザーのインタラクションに基づいて、同じ空間内のユーザーのベクトル表現を取得するにはどうすればよいでしょうか?

ユーザードキュメントマトリックスの形成と分解の一般原則m 人のユーザーと n 個のドキュメントがあるとします。 一部のユーザーについては、特定のドキュメントとの関係がわかっています。 この情報は mxn 行列として表すことができます。行はユーザーに対応し、列はドキュメントに対応します。 その人はほとんどの文書を見ていないため、マトリックスのほとんどのセルは空のままですが、他のセルは埋められます。 各イベント (いいね、嫌い、クリック) に対して、何らかの値がマトリックスに提供されますが、いいねが 1 に対応し、嫌いが -1 に対応する単純化されたモデルを考えてみましょう。

行列を P (mxd) と Q (dxn) の XNUMX つに分解しましょう。ここで、d はベクトル表現の次元 (通常は小さい数) です。 次に、各オブジェクトは d 次元ベクトル (ユーザーの場合は行列 P の行、ドキュメントの場合は行列 Q の列) に対応します。 これらのベクトルは、対応するオブジェクトの埋め込みになります。 ユーザーがドキュメントを気に入るかどうかを予測するには、エンベディングを単純に乗算するだけです。

行列を分解する可能な方法の XNUMX つは、ALS (交互最小二乗法) です。 次の損失関数を最適化します。

ここで、rui はユーザー u とドキュメント i のインタラクション、qi はドキュメント i のベクトル、pu はユーザー u のベクトルです。

次に、平均二乗誤差 (固定ドキュメント ベクトルの場合) の観点から最適なユーザー ベクトルが、対応する線形回帰を解くことによって分析的に見つかります。

これを「ALSステップ」といいます。 そして、ALS アルゴリズム自体は、マトリックス (ユーザーと記事) の一方を修正し、もう一方を更新することを交互に行い、最適な解を見つけます。

幸いなことに、ユーザーのベクトル表現の検索は、実行時にベクトル命令を使用して実行できるかなり高速な操作です。 このトリックを使用すると、ユーザーのフィードバックをすぐにランキングに反映することができます。 同じ埋め込みを kNN インデックスで使用して、候補の選択を改善できます。

分散協調フィルタリング

インクリメンタル分散行列因数分解を実行し、新しい記事のベクトル表現を素早く見つけるにはどうすればよいでしょうか?

コンテンツだけが推奨シグナルのソースではありません。 もう XNUMX つの重要な情報源は、共同作業に関する情報です。 優れたランキング機能は、伝統的にユーザーとドキュメントのマトリックスの分解から取得できます。 しかし、そのような分解を実行しようとすると、次の問題が発生しました。

1. 私たちは数百万のドキュメントと数千万のユーザーを抱えています。 マトリックスは XNUMX 台のマシンに完全に収まらないため、分解には非常に長い時間がかかります。
2. システム内のほとんどのコンテンツの有効期間は短く、ドキュメントの関連性が維持されるのは数時間だけです。 したがって、それらのベクトル表現をできるだけ早く構築する必要があります。
3. ドキュメントの公開直後に分解を作成すると、十分な数のユーザーがそれを評価する時間がなくなります。 したがって、そのベクトル表現はおそらくあまり良くありません。
4. ユーザーが好きか嫌いかについては、それをすぐに分解で考慮することはできません。

これらの問題を解決するために、頻繁な増分更新によるユーザー ドキュメント マトリックスの分散分解を実装しました。 正確にはどのように機能するのでしょうか?

N 台のマシン (N は数百) のクラスターがあり、XNUMX 台のマシンに収まらない行列の分散分解をそれらのマシン上で実行したいとします。 問題は、一方では各マシンに十分なデータが存在し、他方では計算が独立するように、この分解をどのように実行するかということです。

上で説明した ALS 分解アルゴリズムを使用します。 分散方式で XNUMX ​​つの ALS ステップを実行する方法を見てみましょう。残りのステップも同様です。 ドキュメントの固定マトリックスがあり、ユーザーのマトリックスを構築したいとします。 これを行うには、行ごとに N 個の部分に分割します。各部分にはほぼ同じ数の行が含まれます。 対応する行の空でないセルと、ドキュメント埋め込みの行列 (全体) を各マシンに送信します。 サイズはそれほど大きくなく、ユーザー ドキュメント マトリックスは通常非常にまばらであるため、このデータは通常のマシンに収まります。

このトリックは、モデルが収束するまで、固定行列を XNUMX つずつ交互に繰り返しながら、いくつかのエポックにわたって繰り返すことができます。 ただし、それでも、行列の分解には数時間かかる場合があります。 また、これでは、新しいドキュメントのエンベディングをすぐに受け取り、モデルの構築時に情報がほとんどなかったドキュメントのエンベディングを更新する必要があるという問題は解決されません。

高速増分モデル更新の導入が役に立ちました。 現在トレーニング済みのモデルがあるとします。 彼女のトレーニング以来、ユーザーがインタラクションを行った新しい記事や、トレーニング中にインタラクションがほとんどなかった記事がありました。 このような記事のエンベディングを迅速に取得するために、モデルの最初の大規模トレーニング中に取得したユーザー エンベディングを使用し、ALS ステップを XNUMX つ実行して、固定ユーザー行列を与えられたドキュメント行列を計算します。 これにより、ドキュメントの公開後数分以内に埋め込みを非常に迅速に受信できるようになり、最近のドキュメントの埋め込みを頻繁に更新できます。

人間の行動を考慮した推奨を即座に行うため、実行時にはオフラインで取得したユーザーの埋め込みは使用しません。 代わりに、ALS ステップを実行して、実際のユーザー ベクトルを取得します。

別のドメイン領域への転送

テキスト記事に対するユーザーのフィードバックを使用してビデオのベクトル表現を構築するにはどうすればよいですか?

当初はテキスト記事のみを推奨していたため、アルゴリズムの多くはこのタイプのコンテンツに合わせて調整されています。 しかし、他のタイプのコンテンツを追加する場合は、モデルを適応させる必要性に直面しました。 ビデオの例を使用してこの問題をどのように解決しましたか? XNUMX つのオプションは、すべてのモデルを最初から再トレーニングすることです。 しかし、これには長い時間がかかり、一部のアルゴリズムはトレーニング サンプルのサイズを要求しており、新しいタイプのコンテンツがサービス上で誕生した最初の瞬間には、必要な量がまだ利用できません。

私たちは逆に、テキスト モデルをビデオに再利用しました。 同じ ALS のトリックは、ビデオのベクトル表現を作成するのに役立ちました。 テキスト記事に基づいてユーザーのベクトル表現を取得し、ビデオ視聴情報を使用して ALS ステップを実行しました。 したがって、ビデオのベクトル表現を簡単に取得できました。 そして実行時には、テキスト記事から取得したユーザー ベクトルとビデオ ベクトルの間の近接性を計算するだけです。

まとめ

リアルタイム レコメンデーション システムの中核の開発には多くの課題が伴います。 このデータを効果的に使用するには、データを迅速に処理し、ML メソッドを適用する必要があります。 ユーザー信号とコンテンツの新しいユニットを最小限の時間で処理できる複雑な分散システムを構築します。 その他多くのタスク。

現在のシステムでは、その設計について説明しましたが、ユーザーに対する推奨の質は、ユーザーのアクティビティやサービスの滞在期間に応じて向上します。 しかし、もちろん、ここに最大の困難があります。コンテンツとの対話がほとんどない人の興味をシステムが即座に理解することは困難です。 新規ユーザーに対する推奨事項を改善することが私たちの重要な目標です。 私たちはアルゴリズムの最適化を継続し、ユーザーに関連するコンテンツがより早くフィードに表示され、無関係なコンテンツが表示されないようにしていきます。

出所： habr.com