A Global Ranking Method Based on the Interaction Between Commodities

⏵ 1. 序論

従来の検索・ランキング手法では、表示される商品間の相互影響を考慮できていませんでした。同様に、個々の商品のクリック率（CTR）やコンバージョン率（CVR）を推定する従来の手法は、その商品の CTR や CVR が同時に表示される他の商品（表示コンテキストと呼びます）の影響を受けないという仮定に基づいています。実際には、商品の表示コンテキストはユーザーのクリックや購買の意思決定に影響を与えます。ある商品の周辺に類似した商品があり、かつそれらの価格がより安ければ、ユーザーがその商品を購入する確率は低くなります。逆に、周辺の商品がより高ければ、購入確率は大幅に上昇します。

従来のランキングモデルが前提としてきた「コンテキストは影響を与えない」という仮定を崩した場合、どのように順位付けを行うべきでしょうか。そこで、商品間の相互作用を考慮したグローバルランキング手法を初めて提案します。E コマースの順位付けをグローバル最適化問題として定式化し、目標として商品の取引量でユーザー満足度を反映する GMV（Gross Merchandise Volume、商品総取引額）を最大化することを掲げます。正確には、グローバルランキングの最適化目標は GMV の期待値を最大化することです。GMV の期待値を計算するには、相互に影響し合う各商品の取引確率を知る必要があるため、商品間の相互作用を考慮した取引確率推定モデルを提案します。

まず、グローバル特徴拡張アプローチを提案します。これは、ある商品の取引確率を推定する際に、他の商品の影響をグローバル特徴としてモデルに組み込むことで、推定時に他の商品の影響を考慮する手法です。さらに、RNN モデルを用いて商品の順位が取引確率に与える影響を正確に考慮します。RNN モデルにより、E コマースランキングを系列生成問題として定式化し、ビームサーチアルゴリズムを用いてより良い順位を探索します。タオバオワイヤレスメイン検索プラットフォームで大規模な実験を行い、既存のタオバオワイヤレスメイン検索アルゴリズムと比較して GMV が 5% 向上しました。

⏵ 2. グローバルランキング手法

グローバルランキング段階の入力はランキング対象の N 個の商品で、出力はこの N 個の順位列です。

S = (1, ..., N) を基本ランキング出力の上位 N 商品系列とします。

O は S の全順列集合を表します。

o は S のある順列を表します。

また、順位 o における商品 i の位置を表します。

順位 o における商品 i の表示コンテキストを表します。具体的な定義は後述します。

商品の価値を示します。

目標を今回の検索で発生する GMV として定義すると、順位 o が与えられたとき、以下が成り立ちます。

グローバルランキングの最終目標は、期待収益が最大の順位を見つけることです。

この最適な順位を見つけるには、2 つの問題を解決する必要があります。

問題 1：取引確率をどのように正確に推定するか。

問題 2：順位探索は組み合わせ最適化問題であり、全探索の時間計算量は N。 です。合理的で効率的な近似アルゴリズムを見つける必要があります。

問題 1 は効果向上の鍵です。推定が正確であればあるほど、後続の組み合わせ最適化の効果は顕著になり、逆に不正確であれば第 2 ステップの組み合わせ最適化が無意味になります。

理論的には、i に対する完全な表示コンテキストが存在します。しかし、表示コンテキストを完全に考慮すると、問題 2 の組み合わせ最適化の複雑さを軽減することが困難です。問題 2 をより効率的に解くには、表示コンテキストを適切に簡略化する必要があります。表示コンテキストの簡略化の程度に応じて、グローバルランキングモデルを 2 つのカテゴリーに分類します。

2.1 グローバル特徴拡張

第 1 のモデルでは、表示コンテキストの商品集合情報のみを利用し、実際の表示順序は考慮しません。直感的には、第 1 のモデルは、ユーザーが商品 i を購入するかどうかを決定する際、見たすべての商品集合 S のみを記憶しており、S 内の商品の表示順序は考慮しないと仮定します。

この状況は、ユーザーが自分の選択セットを把握しており、その中から最も購入したい商品を比較して選ぶことに相当します。商品 i 自体の特徴をローカル特徴と呼びます。商品 i のローカル特徴を他の候補商品の特徴と比較することで、この商品を候補セット内の他の商品と比較した結果を得られ、これらの比較結果をグローバル情報を含む特徴として予測に追加できます。

価格特徴を例に取ると、ランキング S を価格順に並べ替え、商品 i の価格順位を 0 から 1 の間に一様に正規化します（最も高い価格が 1、最も安い価格が 0 となります）。これが商品 i のグローバル価格特徴です。

上記の方法により、各ディメンションを順位に応じて展開して対応するグローバル特徴を得られます。最後に、ローカル特徴とグローバル特徴を結合して、表示コンテキストを考慮した商品 i の特徴とします。このとき、表示コンテキストは特徴拡張を通じてモデルに追加され、モデルが取引確率を予測する際に役立ちます。

第 1 のモデルの仮定の下では、問題 2 の組み合わせ最適化は非常に単純になります。商品集合は静的であるため、各商品の取引確率は独立に計算できます。ただし、DNN の計算では商品 i のランキング順位が考慮されないため、ポジションバイアスに基づく補正を行う必要があります。問題 2 を解くには、具体的な値を知る必要はなく、バイアスが前から後ろへと順に減少することだけ知っていれば十分です。このとき、商品を高い順から低い順へランキングすることで、最も収益性の高い順位が得られることが保証されます。

2.2 順系列の生成

第 2 のモデルでは、表示コンテキストの商品集合情報だけでなく、商品 i より前に表示される商品の実際の順序も正確に考慮します。第 1 のモデルと同様に、表示コンテキストの商品集合情報はグローバル特徴の拡張により各商品の特徴に追加されます。ただし、第 1 のモデルとは異なり、第 2 のモデルは計算時に商品 i より前の実際の順序も考慮するため、問題 1 は系列確率推定問題となります。最も直感的な方法は RNN を用いた計算です。

第 1 のモデルとは異なり、商品 i より前の商品の順序を考慮するため、前の商品の順序の変化が商品 i の取引確率に影響を与えます。このため、各商品の収益を個別に計算できません。商品 i の収益は前にランクされる商品の影響を受け、最終的な順位が確定するまで商品 i の前にどのような順位があるかは分かりません。目標はこの最適な順位を決定することです。同時に、商品 i より前の商品の順序のみを考慮することで、前から後ろへと段階的に順位付けでき、各ステップで現在位置の商品を選択できます。

理解を容易にするため、まず単純なケースを考えます。貪欲ランキングです。貪欲ランキングとは、まず収益が最大の商品を最初にランクし、次に最初の商品を条件として残りの商品の収益を再計算し、収益が最大の商品を選んで第 2 位とし、以降も同様に行う方法です。貪欲ランキングは貪欲法の一種です。ビームサーチアルゴリズムは貪欲法の拡張と理解できます。検索の各ステップで、最も収益の大きい系列を保持し、最後のステップまで続けて最適な系列を返します。

元の RNN モデルでは長距離依存性の問題に対処できていません。20 番目の位置の商品の取引確率を計算する際、最初の 4 商品はほぼ影響を与えません。前列の商品はユーザーが最初に見る商品であり、一般的に印象が深く、後列の商品への影響は無視できません。モデルに長距離とランキング位置への依存性を考慮させるため、新しいアテンションメカニズムを設計して RNN ネットワークに追加しました。アテンションを導入し位置情報を埋め込むことで、モデルはデータに基づいて異なる位置のアテンションを自動的に学習し、より良い予測結果を得られます。

⏵ 3. 実験結果

3.1 取引確率の推定

DNN はローカル特徴のみを特徴として使用するベースラインです。ReDNN はグローバル特徴を用いた DNN グローバルランキングモデル、miRNN は RNN グローバルランキングモデル、miRNN+attention は私たちのアテンションメカニズムを追加した RNN モデルです。

3.2 タオバオワイヤレスメイン検索オンライン A/B テスト

miRNN と miRNN+attention モデルを使用してランキングを行った場合、アルゴリズムの計算時間はそれぞれ一定であり、ここで N はランキング対象の商品数、k はビームサーチのビームサイズパラメータです。タオバオ検索のような大規模検索プラットフォームでは、この複雑度は明らかに高すぎます。しかし、ベースラインランキングに基づく上位 N 個の商品のみを再ランキングできます。N が著しく大きくない限り、計算コストは許容範囲内です。同時に、上位の商品は効果に最も大きな影響を与えるため、これらの商品を再ランキングするメリットは比較的大きくなります。

本論文で提案した各グローバルランキング手法について、異なる N と k の条件下での GMV 成長率と検索エンジンレイテンシの増加率を比較しました。

最終結果のまとめ：GMV と検索エンジンレイテンシの両方に対する各手法の貢献を評価しました。

⏵ 4. 結論

商品間の相互作用を考慮した E コマース向けグローバルランキング手法を初めて提案し、タオバオメイン検索で顕著な成果を達成しました。現在の最大の課題は、RNN 手法がより効果的である一方、計算負荷が大きすぎることです。計算負荷を削減する方法が今後の重要な研究方向となります。