5つの産業用類似アルゴリズム

1. はじめに

広告主は通常、ユーザータグに基づいて広告のターゲットユーザーを定義します。たとえば、広告主がアウディの広告を掲載したい場合、北部の 25 歳から 44 歳の男性を選択する場合があります。また、メルセデスベンツの広告を掲載したい場合、江蘇省と浙江省の 25 歳から 55 歳の男性を選択する場合があります。

しかし、広告主の事前知識には限界があるため、選択するターゲット層は通常非常に小さく、配信要件を満たすことができません。たとえば、広告主が 100 万人をターゲットにしたいが、ユーザータグを通じて 10 万人のユーザーしか選択していないとします。残りの 90 万人のユーザーはどのように選択すればよいでしょうか。

広告主によって囲まれた 100,000 人のユーザーをシードユーザー (「シードユーザー」) と呼ぶと、提供する必要のある類似ユーザーの追加グループを「類似ユーザー」と呼ぶことができます。シードユーザーに基づいて類似グループを拡張するこのプロセスを、「類似モデリング」と呼びます。したがって、類似モデルは特定のアルゴリズムではなく、モデリング手法の一種を表す一般的な用語です。

2. 似ている

類似には、類似度計算に基づく「類似度ベース」、回帰モデル予測に基づく「回帰ベース」、ラベル類似度に基づく「近似ベース」、ユーザー類似度ネットワークに基づく「グラフベース」、注目度最適化に基づく「注目ベース」など、多くの種類があります。

しかし、この区分は少々無理があるので、ここでは古典的な類似モデルをいくつか紹介するつもりです。

2.1 似たようなもの

重み付け基準ベースのアルゴリズムは、広告テクノロジー企業 Turn によって構築され、ACM 2015 で公開された近似ベースのアルゴリズムです。このアルゴリズムは、主に関連ラベルを計算することで群衆を拡散します。類似性、新規性、品質の 3 つの観点からラベルペアを総合的に評価します。

類似度の計算式は次のとおりです。

はインジケータ関数で、ラベルがある場合は 1、ない場合は 0 になります。はユーザー数です。

ただし、この類似度計算式には、次の 2 つの問題がある可能性があります。1. データがまばらであるため、ほとんどのユーザーはタグを数個しか持っていないため、ほとんどのタグ間の相関は比較的高くなります。2. 関連タグはシードユーザーのタグと比較して非常に大きいか非常に小さいため、計算結果は冗長であるように見えます。

そこで著者は、2 番目の類似度計算式を採用しました。

この時点で、新規性の計算式も存在します。

さらに、品質スコア q を定義する必要があります。品質スコア q には主に CTR、CVR、ROI が含まれ、特定のシナリオに応じて自分で定義できます。

上記の 3 つの指標の加重乗算を実行します。

ログを取り、重量を追加して最終的な評価結果を取得します。

次に、タグ間のスコアを計算し、類似のタグを群衆の拡張に使用できるようになりました。

2.2 Yahoo 類似サイト

Yahoo 類似モデルはグラフベースで、類似性ベースと回帰ベースの方法を組み合わせたものです。システムアーキテクチャは次のとおりです。

主に次の 4 つの部分で構成されます。

ユーザー間の類似性に基づいてユーザー類似性ネットワークを構築し、LSH を使用してユーザーをバケット化します。

大まかな例: シードユーザーと同じバケット内のユーザーは候補ユーザーと見なされます。

特徴スクリーニング: 特徴 IV に基づいて特徴スクリーニングを実行し、シードユーザーを表すことができる肯定的な特徴を選択します。

細かい並べ替え: ユーザースコアを計算して並べ替え、スコアが最も高いユーザーのセットを返します。

ユーザーの類似性は次のように定義されます。

このうち、はユーザーの特徴ベクトルを表し、重み行列は単一の特徴または特徴の組み合わせの線形相関の重要度を表します。これは、ユーザーの特徴の重要度に基づいて構築できます。その時間計算量は、検索の時間計算量はです。 Yahoo は、ユーザーの最適化とバケット化に MinHash と LSH を使用します。

次に、システムはシードユーザーに基づいて、同じバケット内のユーザーを候補セットとして呼び出します。

広告主によって重視するユーザー特性が異なるため、たとえば、K12 教育は年齢を重視し、化粧品は性別に重点を置くため、事前に機能のスクリーニングが必要です。 Yahoo は、パフォーマンスと説明可能性を考慮して、情報価値を特徴スクリーニング方法として使用し、重みマトリックスを構築します。

このうち、S は広告主が提供するシードユーザーです。U は候補ユーザーセットであり、サンプルまたはユーザーセット全体から取得できます。これは肯定的な特徴であり、この機能がシードユーザーにとって他のユーザーよりも重要であることを示しています。

この時点でのユーザー評価方法は次のとおりです。

そのうち、特徴の重要度は、特徴の 2 次的な尺度です。

Yahoo システムは主に IV の重みを持つ最初の順序を使用するため、特定の広告配置のユーザースコアは次のようになります。

このスコアは実数であることに注意してください。確率を計算したい場合は、ソグモイド関数を使用して圧縮することができます。

2.3 LinkedIn の類似品

Linkedin は KDD 16 で類似システムを公開しました。そのアーキテクチャを下の図に示します。

これは、オンラインとオフラインの 2 つの部分に大別され、それぞれ「キャンペーンに依存しない拡張」と「キャンペーンを意識した拡張」と呼ばれます。

「キャンペーンに依存しない拡張」フレームワークは主に拡張にエンティティを使用します。たとえば、データマイニングはビッグデータや機械学習に拡張できます。このフレームワークのアルゴリズムは、LR モデルを使用して、過去のインタラクションデータからエンティティ間の類似性を取得します。この拡張メソッドは、システム内で直接使用できます (追加の計算は不要)。

「キャンペーン対応拡張」フレームワークは、近隣検索を使用して、ユーザー属性に基づいて類似ユーザーを拡張します。

類似度の計算はオンラインでもオフラインでも必要なので、ここで簡単に紹介しておきます。

Linkedin は、各エンティティを構造化された複数フィールドのドキュメントとしてモデル化し、n-gram/辞書、標準化された名前付きデータ型 (標準化、会社名、業界名など)、派生データ型 (派生、インターネット企業はネットワーク開発、ソフトウェア開発などを派生できます)、および近接性 (ユーザーと会社の相互作用のネットワークに基づいて他の関連会社を識別する) の 4 種類のフィールドを抽出します。例えば：

エンティティの構造化されたドキュメントは、転置インデックスライブラリに組み込まれます。ドキュメントの各フィールドの属性には、特徴ベクトルがあります。ドキュメントの同じフィールド間の類似度は、cos 類似度を使用して計算されます。

ドキュメント間の類似性は、ドメインの類似性を使用して線形に重み付けされます。

このうち、s は異なるフィールドの類似度、w は異なるフィールドの重みです。

Linkedin では、ユーザーと企業それぞれに対して上記のエンティティモデリングを実行し、ユーザーがフォローしている企業をポジティブサンプル、フォローしていない企業をネガティブサンプルとして、LR モデルを使用してトレーニングします。

PS: リコールが不十分になるような極端な状況はあるでしょうか?

2.4 Tecent 類似品

リアルタイム Attention ベースの類似モデル (RALM) は、WeChat Kanyikan チームによって提案され、KDD19 で公開されました。類似モデルに Attention を統合し、リアルタイムの情報推奨に使用されます。そのシステムアーキテクチャを下図に示します。

大まかに分けると、「オフライントレーニング」、「オンラインリアルタイム予測」、「オンライン非同期処理」の3つで、それぞれ上図の下、中、上の位置に対応します。

2.4.1 オフライン学習

「オフライントレーニング」部分には、ユーザー表現学習と類似学習が含まれます。前者はユーザーの特徴ベクトルを学習するために使用され、後者はユーザーの特徴ベクトルに基づいて類似度スコアを計算するために使用されます。

ユーザー表現学習モジュールは、Youtube DNN モデルをベースに改良したものです。左側はユーザーの特徴で、concat の代わりに Attention を使用します。左側はアイテムの特徴で、次に SCE Loss またはマルチ分類を全体的に実行して、ユーザーの次のクリックを予測します。トレーニングが完了すると、左側の最後の隠し層がユーザーの特徴ベクトルとして取得されます。モデル構造を下図に示します。

類似学習モジュールはデュアルタワー構造を採用しています。左側にすべてのシードユーザーの特徴ベクトルが入力され、右側にターゲットユーザーの特徴ベクトルが入力されます。その構造は次の図のようになります。

これは、RALM がリアルタイム計算を実現できる主な理由でもあります。アイテムの特徴をシードユーザーの特徴に置き換え、ユーザー - アイテムモデルをユーザー - ユーザーモデルに変換します。

したがって、類似ユーザー学習モジュールの鍵となるのは、シードユーザーグループを表現することです。

ユーザーが自身の個人情報とグループ共通情報を持っていると仮定すると、シードグループは「個人情報 + 共通情報」として表現できます。著者は、それぞれ Local Attention と Global Attention をモデル化し、2 つの埋め込みを学習します。

ローカルアテンションは、シードに対して乗法的なアテンションを使用して、シードユーザーグループ内のターゲットユーザーに関連する情報を抽出し、ユーザーのローカル情報を取得します。

グローバルアテンションはシードユーザーグループにのみ関連します。すべてのセルフアテンションメソッドは、シードユーザーをマトリックス変換で乗算し、次にシードユーザー自身で乗算して、ユーザーグループ自体内の関心分布をキャプチャするために使用されます。

ローカルおよびグローバルの埋め込みを取得した後、それに対して加重合計を実行します。これがシードユーザーグループのすべての情報です。

しかし、ご存知のように、Attention 自体の計算量は非常に大きいため、モデルのオンライン展開に要する時間のかかる要件を満たすことはできません。この目的のために、著者らは、キーの数を減らすために、k-means を通じてシードユーザーをクラスタ化しました。

類似学習が完了すると、ユーザーの FC の特徴ベクトルを右側に保存し、オンラインサービスに提供できるようになります。

2.4.2 オンライン非同期

オンライン非同期処理は、主に次のようなオンライン要求とは関係のない計算を処理します。

ユーザーのクリックログに基づいてアイテムのシードユーザーリストを更新します。

シードユーザーのクラスターセンターを計算し、それを推奨システムに配布します。

グローバル埋め込みを計算します。

これらはすべて定期的に更新され、リアルタイムの計算は必要ありません。

2.4.3 オンラインサービス

オンラインサービスは、主にシードユーザーのクラスターセンター、グローバル埋め込み、およびユーザーの埋め込みを取得し、ローカル埋め込みをオンラインでリアルタイムに計算し、最終的な類似度を計算します。

PS: RALM はクラスタリング機能を備えているため、シードユーザーに異常な点がある場合に問題が発生する可能性があります (もちろん、内部的に最適化されている可能性もあります)。

2.5 Pinterest の類似品

Pinterest Look-Alike は、KDD 19 で類似モデルを公開しました。これは、LR ベースの分類モデルと埋め込みベースの類似性検索モデルの 2 つの部分に大別されます。

2.5.1 分類器ベースのアプローチ

Pinterest のベースラインでは、LR モデルを使用して分類モデルを作成します。シードサンプルを正のサンプルとして、ランダムに選択された非シードサンプルを負のサンプルとして、分類モデルをトレーニングしてすべてのユーザーにスコアを付け、ランク付けします。

2.5.2 埋め込みベースのアプローチ

Pinterest が検討した新しい方法は、大きく分けて 2 つの部分に分けられます。1 つは埋め込みをトレーニングすること、もう 1 つは埋め込みと LSH に基づいて類似ユーザーを見つけることです。

最初のステップは、StarSpace メソッド (ペアワイズ) に基づいてトレーニングされたユーザーの特徴ベクトルを計算することです。

ユーザー: ユーザーを Piar A として使用し、ユーザーの離散特徴 + 正規化された連続特徴を連結し、線形活性化関数を持つ Dense レイヤーの後に、ユーザー特徴ベクトルを出力します。

トピック: アイテムのトピックをペア B として取得し、トピックの特徴ベクトルをルックアップによって取得します。

トレーニングサンプル: ユーザーが操作したアイテムを取得し、そのアイテムのトピックをペア B として使用します。他の k 個のトピックを負のサンプルとしてランダムに選択し、ユーザーとサンプルペアを形成します。

トレーニングセット: ユーザーが操作したアイテムのトピックが正のサンプルとして使用され、ランダムに選択された k 個のトピックが負のサンプルとして使用されます。損失関数は次のとおりです。

トレーニングの終了: このモデルは最終的にシードユーザーの拡散の問題を解決するために使用されるため、著者はシードユーザーと非シードユーザー (シードユーザーの 90% がセット K を形成する) を取得し、残りのシードユーザー 10% から 1 つ、非シードユーザーから 1 つを取得します。類似性を定義すると、トレーニングを停止するための評価基準は次のようになります。

トレーニングテンソルボードを以下に示します。

モデルの再トレーニング: 最新バージョンのモデルを使用して、ユーザーの埋め込みを定期的に (長期間にわたって) 再計算します。主な目的は、すべてのユーザーの興味が変化していることを期待して、ユーザーの行動とユーザーのドリフトを捉えることです。（なぜ？）

ユーザー特徴ベクトルを取得した後、LSH を使用してユーザーをマッピングし、シードユーザーの数に基づいて投票を実行して領域を選択し、その領域内のユーザーが拡張ユーザーとして扱われます。

もちろん、各地域のユーザー数が異なることも考慮する必要があります。そのため、地域内のシードセットの修正スコアは次のようになります。

その中には、エリア内の総人数、平滑化係数、などがあります。

次の表は、各地域の人数を示しています (緑はシードユーザー、赤は非シードユーザーを表します)。

次の表は、投票スコアと確率スコアの差を示しています。地域ランキングが変化したことがわかります。

作成者はマッピングを m 回繰り返し、最終的な確率スコアを取得します: 。各ユーザーのマッピング結果はなので、ユーザーの最終スコアはです。

そして、スコアの高いユーザーが拡張ユーザーとして選択されます。

視覚化の結果は以下の図に示されています。