Daguan Data: 推奨システムアルゴリズムの再ランキングの実践

インターネットの出現と普及は、大量の情報をユーザーにもたらし、情報化時代の情報需要を満たしました。しかし、インターネットの急速な発展に伴い、オンライン情報の量が大幅に増加し、ユーザーは大量の情報に直面しても、自分にとって本当に役立つ情報を得ることができなくなりました。むしろ、情報の利用効率が低下し、情報過多の問題が生じています。

[[190823]]

Daguan Data には、情報過多を解決するためのいくつかの方法があります。1 つは検索です。ユーザーが明確な情報ニーズを持っている場合、その意図はいくつかの短いキーワードに変換され、そのキーワードが対応する検索エンジンに送信されます。検索エンジンは、膨大な情報データベースから関連情報を検索し、顧客に返します。もう 1 つは推奨です。ユーザーの意図が不明瞭または表現が難しい場合、特に近年のモバイル インターネットの台頭により、ユーザーは必ずしも明確な意図を持って閲覧するわけではありません。多くの場合、ユーザーは「閲覧」または時間をつぶすという考え方で Web ページまたはアプリを閲覧します。このような状況では、情報過多を解決し、ユーザーの意図を理解し、ユーザーの好みに応じてパーソナライズされた結果をプッシュするには、推奨システムがより良い選択です。この記事では、まずレコメンデーションシステムのプロセスフレームワークを簡単に紹介し、次に主に再ランキングについて紹介します。

1. 推奨システムプロセスフレームワーク

フレームワークの観点から見ると、推奨システムのプロセスは、データのクリーニング、データの保存、候補セットの生成、候補セットの融合ルールのフィルタリング、および再ランク付けに分けられます。まず、顧客から報告されたデータがクリーンアップされ、データの一貫性がチェックされ、無効な値と欠損値が処理され、ダーティデータが削除され、データがフォーマットされてさまざまな種類のストレージ システムに保存されます。ユーザー行動ログや推奨ログは時間の経過とともに蓄積され、サイズが大きくなり、通常は分散ファイルシステム (HDFS)、つまり Hive テーブルに保存されます。必要に応じて、ローカルにダウンロードしてオフライン分析を行うことができます。商品情報は通常、MySQL に保存されます。しかし、Daguan Data では、顧客数の増加により商品情報テーブル (item_info) のサイズが増大したため、Hive と HBase にも保存されています。Hive はオフライン分析操作を容易にしますが、リアルタイム プログラムで読み取る場合の Hive テーブルのリアルタイム パフォーマンスは低いため、リアルタイム プログラムが読み取れるように HBase にもコピーが書き込まれます。各プログラム モジュールによって生成された結果については、プロセス同期関係を持つプログラムでは通常、Redis をバッファー ストレージとして使用し、プロデューサーはコンシューマーが使用できるように Redis に情報を書き込みます。候補セット生成とは、ユーザーの過去の行動、リアルタイムの行動、さまざまな戦略やアルゴリズムに基づいて推奨候補セットを生成することです。同時に、クリック フィードバックは、ユーザーのリアルタイム操作に基づいて候補セットをリアルタイムで調整します。一部の新しいユーザーや履歴の動作が少ないユーザーの場合、候補セットが小さすぎるため、それを補うための代替戦略が必要になります。候補セット融合ルールフィルタリングには、主に2つの機能があります。1つは、生成された候補セットを融合して、推奨戦略のカバレッジと精度を向上させることです。さらに、条件を満たさない項目を除外するために、製品と操作の観点からいくつかの人工ルールを決定する必要があります。並べ替えでは、主に機械学習モデルを使用して、融合された候補セットを並べ替えます。

候補セット生成と再ランク付けの 2 つのレベルでは、効果の反復のために両方のレイヤーを頻繁に変更する必要があるため、ABTest をサポートする必要があります。効率的な反復をサポートするために、候補セットのトリガー層と並べ替え層を分離します。これら 2 つの層の結果は直交しているため、比較実験は互いに影響を与えることなく個別に実行できます。同時に、各レイヤー内では、ユーザーに応じてトラフィックを複数の部分に分割し、複数の戦略の同時オンライン比較をサポートして、推奨効果を向上させます。

2. 機械学習による再ランキング

さまざまなアルゴリズムによってトリガーされた候補セットの場合、アルゴリズムの過去の効果のみに基づいて、アルゴリズムによって生成されたアイテムの位置を決定するのは、少し単純で粗雑に思えます。同時に、各アルゴリズム内では、さまざまなアイテムの順序は、1つまたは複数の要素によって単純に決定されます。これらの並べ替え方法は、最初のステップの予備選択プロセスにのみ使用できます。最終的な並べ替え結果は、関連する並べ替えモデルと包括的な要素を使用して、機械学習方法の助けを借りて決定する必要があります。

ソートモデルは、非線形モデルと線形モデルに分けられます。非線形モデルは、特徴における非線形関係をより適切に捉えることができますが、トレーニングと予測のコストは線形モデルよりも高く、非線形モデルの更新サイクルも比較的長くなります。比較すると、線形モデルでは特徴処理の要件が高く、ドメインの知識と経験に基づいた特徴の手動前処理が必要です。ただし、線形モデルは単純なので、トレーニングと予測の効率は高くなります。そのため、更新サイクルを短縮することができ、業務と組み合わせたオンライン学習の試みも可能となります。

2.1 線形モデル

線形モデルでは、主にロジスティック回帰が導入されます。ロジスティック回帰は一般化線形モデルです。名前に回帰が含まれていますが、実際には分類アルゴリズムであり、主にバイナリ分類アルゴリズムまたはマルチ分類アルゴリズムで使用されます。マルチ分類には、1 対 1 残り (OvR) と多対多 (MvM) という 2 つの異なる分類の考え方があります。ここでは、主に予測と分類の問題 (特定のユーザー ID が特定のアイテム ID をクリックするかどうか) について説明します。

まず、各ユーザー ID と各アイテム ID が特徴として取得され、モデル関数は次のようになります。

 gz=i=1mαi*Ui+j=1kβj*Ij  
 Hz = 11 + eg(Z)

m、kはそれぞれユーザーIDとアイテムIDの数、αi、βjはそれぞれ独立変数Ui、Ijのパラメータです。

ロジスティック回帰モデルは、最大尤度法を使用してモデルのパラメータを推定し、コスト関数は次のようになります: Jθ=i=1nyi*hθ(Zi):

n はサンプル数、yi はサンプルのラベル、すべてのパラメータは θ ベクトルに置き換えられます。次に、コスト関数の最適化を計算するためのパラメータが計算されます。最適化理論では、勾配降下法、ランダム勾配降下法、ニュートン法、準ニュートン法、共役勾配法など、最適化パラメータを解決するための多くの方法があります。ここではニュートン法を使用します。

ニュートン法の考え方は非常に単純で、テイラー展開を2次形式に展開することです。

この式は次の場合にのみ有効です:

解決：

反復式は次のようになります。

根を求めるニュートン法:

比較すると、ニュートン法は勾配降下法よりも収束しやすい（反復回数が少ない）のですが、高次元の場合、ニュートンの反復式は次のようになります。

ここで、H はヘッセ行列です。

ヘッセ行列は計算の複雑さを増しますが、一般的に候補セットの数はそれほど多くないため、許容範囲内です。

クリックスルー率の推定では、肯定的なサンプルと否定的なサンプルのバランスが著しく悪いため、否定的なサンプルのサンプリングが必要になります。同時に、トレーニングの前に、TFIDF を使用してトレーニング データを列ベクトルに変換する必要があります。これにより、各行は長さ m+k の列ベクトルになり、その結果がトレーニングのモデル入力として使用されます。

クロス検証の結果によると、精度、再現率、F1 スコアはすべて約 0.83 であり、非常に印象的です。

候補セットをモデルに入力すると、対応する予測確率が得られます。この確率は、入力値をベクトルに変換し、ロジット関数を使用して (0, 1) の間の値に正規化し、その値に基づいて対応する順序を取得することによって得られます。 （大観データ孟立斌）

2.2 非線形モデル

非線形モデルでは、主に GBDT (Gradient Boost Decision Tree) とそのアプリケーションについて説明します。 GBDT はよく使われる非線形モデルであり、Boost アルゴリズムの一種です。まずは AdaBoost と呼ばれる新しいメタアルゴリズムを紹介しましょう。

Adaboost アルゴリズムは、最初に各サンプルに重み値を割り当てます。最初は、各サンプルの重みは同じです。各反復では、単層決定木分類器が確立されます (ランダムな推測よりもわずかに優れている限り、任意の分類器を弱分類器として使用できますが、弱分類器は単純であるほど優れています)。分類器は、計算された予測サンプルの最小エラー率に基づいて最適な単層決定木を選択し、同時に、誤って分類されたポイントの重みを増やし、正しく分類されたポイントの重みを減らします。このように、一部のポイントが常に誤分類されている場合は、「深刻な懸念」となり、非常に高い重みが与えられます。その後、N 回の反復 (ユーザーが指定) を実行すると、N 個の単純な分類器 (基本学習器) が得られ、それらを組み合わせて (たとえば、重み付けしたり、投票させたりすることができます)、最終モデルが得られます。

オリジナルの Boost アルゴリズムでは、アルゴリズムの開始時に各サンプルに重み値を割り当てます。最初は、すべてのサンプルは同等に重要です。トレーニングの各ステップで得られたモデルは、データ ポイントの推定を正しいか正しくないかを決定します。各ステップの後に、誤って分類されたポイントの重みを増やし、正しく分類されたポイントの重みを減らします。このように、一部のポイントが常に誤って分類されている場合、それらのポイントには「深刻な懸念」があり、非常に高い重みが割り当てられます。その後、N 回の反復 (ユーザーが指定) を実行すると、N 個の単純な分類器 (基本学習器) が得られ、それらを組み合わせて (たとえば、重み付けしたり、投票させたりすることができます)、最終モデルが得られます。

勾配ブーストと従来のブーストの違いは、各計算が前の計算の残差を削減することです。残差を排除するために、残差削減の勾配方向に新しいモデルを構築できます。したがって、Gradient Boost では、新しい各モデルの目的は、勾配の方向で以前のモデルの残差を減らすことであり、これは正しいサンプルと誤ったサンプルに重み付けする従来の Boost 方式とは大きく異なります。

具体的なアルゴリズムは次のとおりです。

私たちの目標は、サンプル空間内で最良の予測関数 f*(X) を見つけることです。これにより、X を y にマッピングする損失関数 L(y,F(X)) が最小化されます。つまり、

損失関数の二乗誤差は次のとおりです。

予測関数F(X)はP={P1,P2,…}をパラメータとして取り、いくつかの弱分類器の合計として記述できると仮定します。ここで、P={βm,αm}0Mであり、m番目の弱分類器の式はβmh(X;αm)です。ここで、βmh(X;αm)

はm番目の回帰木を表し、ベクトルαmはm番目の回帰木のパラメータを表し、βmは予測関数におけるm番目の回帰木の重みを表します。

次に、N 個のサンプル ポイント {xi,yi}N について、最適化問題は、次の式を満たすパラメータ {βm,αm}、m=0,1,2,…,M を見つけることと同等です。

解決策は次の反復プロセスに簡略化されます。

1. まず、初期化分類器を定数ρとして定義します。ここで、F0(X)は弱分類器の初期化と定数ρを表し、初期予測損失関数が最小値に達するようにします。

2. 各反復では、回帰木に基づく弱分類器が構築され、m 回目の反復後に得られる予測関数が Fm(X) と仮定され、対応する予測関数は L(y, Fm(X)) です。予測損失関数をできるだけ早く削減するには、最初の m-1 回の反復で生成された予測損失関数の勾配方向に m 番目の弱分類器 βmh(X;αm) を確立する必要があります。ここで、-gm(xi) は m 回目の反復の弱分類器の確立方向を表し、L(yi, F(xi)) は最初の m-1 回の反復で生成された予測損失関数を表します。式は L(yi, F(xi))=((yi-F(xi))2 です。

得られた勾配降下方向に基づいて、パラメータ αm は、回帰木 h(X;αm) をこの方向に沿って近づけるパラメータ値です。つまり、

βmはこの方向への探索の最大ステップ長であり、次の式で表される。

3. 各反復後に得られた予測関数を更新します。つまり、Fm(X) = Fm-1(X) + βmh(X;αm)です。対応する予測損失関数が誤差収束条件を満たすか、生成された回帰ツリーが設定値Mに達すると、反復は終了します。

4. 過剰適合を避けるために、各弱分類器には通常、0 から 1 の範囲の「学習率」ν が掛けられます。ν 値が小さいほど、学習はより保守的になり、同じ精度を達成するために必要な反復回数が多くなります。逆に、学習が速いほど、過剰適合する可能性が高くなります。

GBDT の本来の利点は、さまざまな識別機能と機能の組み合わせを発見できることです。 GBDT と LR は次のように組み合わせることができます。

まず、既存の特徴を使用して GBDT モデルをトレーニングし、次に GBDT モデルによって学習されたツリーを使用して新しい特徴を構築し、最後にこれらの新しい特徴を元の特徴に追加してモデルを一緒にトレーニングします。構築された新しい特徴ベクトルの値は 0/1 であり、ベクトルの各要素は GBDT モデルのツリーのリーフ ノードに対応します。サンプル ポイントがツリーを通過して最終的にこのツリーのリーフ ノードに落ちると、新しい特徴ベクトル内のこのリーフ ノードに対応する要素値は 1 になり、このツリーの他のリーフ ノードに対応する要素値は 0 になります。新しい特徴ベクトルの長さは、GBDT モデル内のすべてのツリーに含まれるリーフ ノードの数の合計に等しくなります。

例を挙げてください。下の図の 2 つのツリーは GBDT によって学習されます。最初のツリーには 3 つのリーフ ノードがあり、2 番目のツリーには 2 つのリーフ ノードがあります。入力サンプル ポイント x が最初のツリーの 2 番目のリーフ ノードに該当する場合、2 番目のツリーの最初のリーフ ノードに該当します。 GBDT によって取得される新しい特徴ベクトルは [0, 1, 0, 1, 0] となり、ベクトルの最初の 3 桁は最初のツリーの 3 つのリーフ ノードに対応し、最後の 2 桁は 2 番目のツリーの 2 つのリーフ ノードに対応します。

LR はシンプルで、トレーニングと予測の効率が高いですが、特徴エンジニアリングが非常に重要です。既存の特徴エンジニアリング実験は、主に識別的な特徴と特徴の組み合わせを見つけることに焦点を当てていますが、このような面倒な作業を行っても、必ずしも結果が改善されるとは限りません。 GBDT アルゴリズムの特性を利用すると、識別的な特徴と特徴の組み合わせを発見できるため、特徴エンジニアリングの労働コストを削減できます。 2014 年の Kaggle CTR コンペティションの優勝者はこの組み合わせ方法を使用しており、私も彼らから学びました。

[この記事は51CTOコラムニスト「Daguan Data」によるオリジナル記事です。転載については51CTOコラムまでご連絡ください]

この著者の他の記事を読むにはここをクリックしてください