2.1.3 候補検索の詳解 | Building Recommender Systems Using Large Language Models

位置づけ

候補検索とは、推薦対象の全カタログから、ランキングモデルに渡す候補アイテム集合を高速に取り出す工程である。英語では candidate retrieval、candidate generation、matching、recall stage などと呼ばれることが多い。

推薦システム全体を大きく分けると、次のような流れになる。

コンテンツ理解で作品を特徴量化する
ユーザーモデリングでプロフィールの嗜好を表現する
候補検索で全作品から数百件から数千件程度を取り出す
ランキングで候補を精密に並べ替える
再ランキングやビジネスルールで多様性、安全性、配信制約を調整する
画面上の棚や枠に表示する

候補検索の役割は「最終順位を完璧に決めること」ではない。役割は、後段のランキングが評価すべき有望な作品をできるだけ漏らさず集めることである。

Hulu のような動画配信サービスで考えると、推薦可能な作品は item_information_table にある。ここには series_id、service_type、genre、sub_genre、casts、film_directors、description、avg_mood_tag、avg_fingerprint、publish_start_at、publish_end_at、is_blacklist などがある。一方、プロフィールの視聴履歴は unique_viewed_series にあり、profile_id、series_id、last_viewing_date がある。

候補検索では、これらを使って「この profile_id に対して、まずランキング候補に入れるべき series_id はどれか」を高速に決める。

なぜ候補検索が必要なのか

推薦で最も素朴な発想は、全作品を 1 つずつスコアリングして、スコアの高い順に並べることである。しかし、これは大規模サービスでは現実的ではない。

例えば、推薦可能な作品が 100 万件あり、1 人のユーザーに対してランキングモデルで全件を評価するとする。ランキングモデルが 1 件あたり 1 ミリ秒しかかからないとしても、単純計算では 1000 秒かかる。もちろん並列化はできるが、全ユーザー、全リクエストでこれを行うのは高コストである。

実際には、ランキングモデルは多くの特徴量を使う。

ユーザーの長期嗜好
ユーザーの短期嗜好
候補作品のジャンル、タグ、mood
ユーザーと候補作品の類似度
視聴済み作品との共起スコア
配信終了までの日数
SVOD/TVOD の適合性
キッズ適合性
デバイスや時間帯
同一シリーズや同一ジャンルの出しすぎ

このような複雑なモデルを全作品に対してリアルタイムで実行するのは重い。そこで、まず候補検索で「可能性が高い作品だけ」に絞る。

候補検索は、計算量を次のように変える工程である。

\text{全作品数 } N \quad \rightarrow \quad \text{候補数 } K

ここで通常、 $K \ll N$ である。例えば、100 万作品から 1000 件に絞れば、ランキング対象は 1000 分の 1 になる。

候補検索は再現率を重視する

候補検索で最も重要なのは、精度よりも再現率である。

ランキングに渡されなかった作品は、どれほど良い作品でも最終推薦に出られない。つまり、候補検索で漏れた時点で、その作品は負けである。

この性質を式で書くと、最終推薦集合 $\mathcal{R}_u$ は候補集合 $\mathcal{C}_u$ の部分集合である。

\mathcal{R}_u \subseteq \mathcal{C}_u

したがって、理想的には、将来ユーザーが視聴しそうな作品集合 $\mathcal{Y}_u$ を候補集合がなるべく多く含んでいてほしい。

\text{Recall@K} = \frac{|\mathcal{C}_u^{(K)} \cap \mathcal{Y}_u|} {|\mathcal{Y}_u|}

ワークド例: Recall@K を実際に計算する

プロフィール P001 が、評価期間中に実際に次の 4 作品を 25% 以上視聴したとする。ここでは、これを将来視聴集合 $\mathcal{Y}_u$ とする。

「名探偵コナン」
「SPY x FAMILY」
「インターステラー」
「TENET」

候補検索モデルが上位 10 件として次を返したとする。

「名探偵コナン」
「葬送のフリーレン」
「SPY x FAMILY」
「鬼滅の刃」
「インターステラー」
「ダークナイト」
「進撃の巨人」
「呪術廻戦」
「世界の果てまでイッテQ」
「韓国恋愛ドラマ A」

この候補集合 $\mathcal{C}_u^{(10)}$ と将来視聴集合 $\mathcal{Y}_u$ の共通部分は次である。

\mathcal{C}_u^{(10)} \cap \mathcal{Y}_u = \{\text{名探偵コナン}, \text{SPY x FAMILY}, \text{インターステラー}\}

したがって、Recall@10 は次のようになる。

\text{Recall@10} = \frac{3}{4} = 0.75

ここで重要なのは、「候補 10 件のうち 7 件が将来視聴されなかった」ことを、この段階では過度に責めないことである。候補検索の役割は、ランキング前に有望な作品を漏らさず集めることである。ノイズ候補はランキングで落とせる。一方、「TENET」が候補に入っていないことは、ランキングでは救えない。したがって候補検索では、まず Recall を高くすることが重要である。

候補検索の段階では、多少ノイズのある候補が混ざってもよい。後段のランキングで落とせるからである。一方、良い候補を取り逃がすと、後段では救えない。

このため、候補検索では「高再現率」「広いカバレッジ」「高速性」「多様な検索パス」が重要になる。

Hulu での候補検索の入力と出力

Hulu のドメイン情報に即して考えると、候補検索の入力は次のようになる。

profile_id
プロフィールの視聴済み series_id 集合
last_viewing_date による最近性
視聴済み作品のジャンル、タグ、人物、mood、fingerprint
推薦可能な作品カタログ
配信期間、ブラックリスト、キッズ適合性などの制約

出力は、ランキングモデルに渡す候補作品集合である。

\mathcal{C}_u = \{ i_1, i_2, \ldots, i_K \}

ここで $\mathcal{C}_u$ はプロフィール $u$ に対する候補 series_id の集合である。

候補検索の段階では、各候補に「どの検索パスから出たか」も付けておくとよい。

item_cf
content_embedding
topic
two_tower
popular
new_release
continue_watching
editorial
tvod_promotion

この情報はランキング特徴量として使える。例えば、同じ作品が item_cf と content_embedding の両方から出てきたなら、複数の根拠がある候補として扱える。

検索パスを複数持つ理由

教科書では、アイテムベース検索、トピックベース検索、ユーザーベース協調フィルタリング、ハイブリッドアプローチが挙げられている。実務では、候補検索を 1 つの方法だけに依存しないことが多い。

理由は、検索パスごとに得意不得意が違うからである。

例えば、アイテムベース CF は「過去に見た作品と一緒に見られやすい作品」を拾うのが得意である。一方で、新作やロングテール作品には弱い。

コンテンツベース検索は、説明文、タグ、mood、fingerprint から意味的に近い作品を拾える。新作にも使いやすい。一方で、実際のユーザー行動に基づく意外な関連は拾いにくい。

人気作品検索は、新規ユーザーや履歴が薄いユーザーに強い。一方で、人気作品ばかりになると発見性が落ちる。

継続視聴検索は、シリーズ視聴体験には非常に重要である。一方で、探索的な新規発見には向かない。

したがって、候補検索では複数の候補ソースを作り、後段でマージする。

\mathcal{C}_u = \mathcal{C}_u^{\text{item-cf}} \cup \mathcal{C}_u^{\text{content}} \cup \mathcal{C}_u^{\text{topic}} \cup \mathcal{C}_u^{\text{two-tower}} \cup \mathcal{C}_u^{\text{popular}} \cup \mathcal{C}_u^{\text{continue}}

このようにすることで、候補集合の再現率と多様性を高められる。

図 1: 候補検索では複数の検索パスを並列に使い、重複排除した候補集合をランキングに渡す。

ワークド例: 複数検索パスのマージ

プロフィール P001 が最近「SPY x FAMILY」と「名探偵コナン」を見ているとする。各検索パスが次の候補を返したとする。

アイテム CF: 「劇場版名探偵コナン」「金田一少年の事件簿」「ルパン三世」
コンテンツ類似: 「葬送のフリーレン」「鬼滅の刃」「SPY x FAMILY Season 2」
TTSN: 「SPY x FAMILY Season 2」「劇場版名探偵コナン」「呪術廻戦」
人気と新着: 「推しの子」「薬屋のひとりごと」「劇場版名探偵コナン」

単純に結合すると 12 件に見える。しかし重複を除くと、候補は次の 9 件になる。

「劇場版名探偵コナン」
「金田一少年の事件簿」
「ルパン三世」
「葬送のフリーレン」
「鬼滅の刃」
「SPY x FAMILY Season 2」
「呪術廻戦」
「推しの子」
「薬屋のひとりごと」

ここで「劇場版名探偵コナン」は、アイテム CF、TTSN、人気と新着の 3 経路から出ている。この情報はランキングで有用である。例えば、次のような特徴量を候補に付けられる。

候補作品	出現検索パス数	アイテム CF	コンテンツ類似	TTSN	人気と新着
劇場版名探偵コナン	3	1	0	1	1
SPY x FAMILY Season 2	2	0	1	1	0
金田一少年の事件簿	1	1	0	0	0

候補検索の出力は series_id のリストだけではなく、「なぜ候補に入ったか」を表す検索パス特徴も持たせると、後段のランキングが判断しやすくなる。

アイテムベース検索

アイテムベース検索は、ユーザーが過去に視聴した作品と類似した作品を取り出す方法である。

Hulu の例では、プロフィール $u$ が視聴した作品集合を $I_u$ とする。

I_u = \{ i \mid \text{profile } u \text{ watched series } i \}

各視聴済み作品 $i$ に対して、類似作品集合 $N(i)$ を取得し、それらを候補にする。

\mathcal{C}_u^{\text{item}} = \bigcup_{i \in I_u} N(i)

類似作品の作り方には大きく 2 種類ある。

行動共起に基づく類似
コンテンツ特徴に基づく類似

行動共起に基づく場合、作品 $i$ と $j$ が同じプロフィールに一緒に見られやすければ近いと考える。

\text{sim}_{\text{cf}}(i,j) = \frac{\mathbf{r}_i^{\mathsf{T}}\mathbf{r}_j} {\|\mathbf{r}_i\|\|\mathbf{r}_j\|}

ここで $\mathbf{r}_i$ は作品 $i$ を視聴したプロフィールを表すベクトルである。

コンテンツ特徴に基づく場合、作品 $i$ と $j$ の embedding を使う。

\text{sim}_{\text{content}}(i,j) = \frac{\mathbf{c}_i^{\mathsf{T}}\mathbf{c}_j} {\|\mathbf{c}_i\|\|\mathbf{c}_j\|}

ここで $\mathbf{c}_i$ は作品 $i$ のコンテンツ embedding である。Hulu の avg_fingerprint は、この用途に使える可能性がある。説明文やタグから作ったテキスト embedding と組み合わせることもできる。

図 2: アイテムベース CF では、作品を「どのプロフィールに見られたか」のベクトルとして表し、共起の強さから類似作品を作る。

ワークド例: アイテムベース CF の cosine 類似度

4 つのプロフィール P1、P2、P3、P4 がいるとする。作品ごとに「25% 以上視聴したか」を 1、していないかを 0 で表す。

作品	P1	P2	P3	P4
名探偵コナン	1	1	1	0
金田一少年の事件簿	1	1	0	0
インターステラー	0	0	1	1

このとき、各作品の視聴ベクトルは次のようになる。

\mathbf{r}_{\text{コナン}} = \begin{bmatrix} 1 & 1 & 1 & 0 \end{bmatrix}

\mathbf{r}_{\text{金田一}} = \begin{bmatrix} 1 & 1 & 0 & 0 \end{bmatrix}

\mathbf{r}_{\text{インターステラー}} = \begin{bmatrix} 0 & 0 & 1 & 1 \end{bmatrix}

まず、「名探偵コナン」と「金田一少年の事件簿」の類似度を計算する。

内積は次の通りである。

\mathbf{r}_{\text{コナン}}^{\mathsf{T}} \mathbf{r}_{\text{金田一}} = 1 \cdot 1 + 1 \cdot 1 + 1 \cdot 0 + 0 \cdot 0 = 2

ノルムは次の通りである。

\|\mathbf{r}_{\text{コナン}}\| = \sqrt{1^2 + 1^2 + 1^2 + 0^2} = \sqrt{3}

\|\mathbf{r}_{\text{金田一}}\| = \sqrt{1^2 + 1^2 + 0^2 + 0^2} = \sqrt{2}

したがって cosine 類似度は次のようになる。

\text{sim}(\text{コナン}, \text{金田一}) = \frac{2}{\sqrt{3}\sqrt{2}} \approx 0.816

次に、「名探偵コナン」と「インターステラー」の類似度を計算する。

\mathbf{r}_{\text{コナン}}^{\mathsf{T}} \mathbf{r}_{\text{インターステラー}} = 1 \cdot 0 + 1 \cdot 0 + 1 \cdot 1 + 0 \cdot 1 = 1

\|\mathbf{r}_{\text{インターステラー}}\| = \sqrt{0^2 + 0^2 + 1^2 + 1^2} = \sqrt{2}

\text{sim}(\text{コナン}, \text{インターステラー}) = \frac{1}{\sqrt{3}\sqrt{2}} \approx 0.408

この小さな例では、「名探偵コナン」は「金田一少年の事件簿」により近い。したがって、プロフィールが「名探偵コナン」を見ているなら、アイテムベース CF は「金田一少年の事件簿」を強めの候補として出す、という判断になる。

例えば、あるプロフィールが「インターステラー」を見た場合、アイテムベース検索は次のような候補を拾う可能性がある。

同じ監督の作品
宇宙 SF 作品
重厚で思索的な洋画
他のユーザーが一緒に見ている作品
avg_fingerprint が近い映像雰囲気の作品

アイテムベース検索は、候補検索の基本である。実装しやすく、説明もしやすい。

トピックベース検索

トピックベース検索は、ユーザーが関心を示しているトピックに関連する作品を取り出す方法である。

動画配信では、トピックはジャンルより細かい概念として考えるとよい。

宇宙探索
タイムリープ
医療ドラマ
犯罪捜査
学園青春
家族愛
料理対決
韓国恋愛ドラマ
キッズ向け冒険
ノンフィクション犯罪

プロフィール $u$ のトピック嗜好を $\mathbf{t}_u$ 、作品 $i$ のトピック特徴を $\mathbf{t}_i$ とする。トピックベースのスコアは例えば次のように計算できる。

s_{\text{topic}}(u,i) = \mathbf{t}_u^{\mathsf{T}}\mathbf{t}_i

トピック嗜好 $\mathbf{t}_u$ は、視聴済み作品のトピックを集約して作れる。

\mathbf{t}_u = \frac{\sum_{i \in I_u} w_{u,i}\mathbf{t}_i} {\sum_{i \in I_u} w_{u,i}}

ここで $w_{u,i}$ は最近性や視聴強度に基づく重みである。

トピックベース検索の良い点は、解釈しやすいことである。「最近、医療ドラマを見ているから医療ドラマを候補にする」「宇宙 SF をよく見ているから宇宙探索トピックを候補にする」と説明できる。

一方で、トピック設計が粗いと推薦も粗くなる。単に「SF」とだけ分類すると、ユーザーが好きな SF のタイプを見分けられない。宇宙探索、ディストピア、ロボット、タイムリープ、怪獣、近未来サスペンスなどに分けた方が、候補検索の質は上がる。

ユーザーベース協調フィルタリング検索

ユーザーベース協調フィルタリングは、似たプロフィールを探し、そのプロフィールが見ている作品を候補にする方法である。

プロフィール $u$ と $v$ の視聴ベクトルを $\mathbf{r}_u$ 、 $\mathbf{r}_v$ とすると、類似度は次のように計算できる。

\text{sim}(u,v) = \frac{\mathbf{r}_u^{\mathsf{T}}\mathbf{r}_v} {\|\mathbf{r}_u\|\|\mathbf{r}_v\|}

プロフィール $u$ に対する候補集合は、近傍プロフィール $N(u)$ が視聴した作品から作る。

\mathcal{C}_u^{\text{user-cf}} = \bigcup_{v \in N(u)} I_v

この方法の直感は分かりやすい。「あなたと似た視聴履歴のプロフィールが見ている作品」を推薦するというものである。

ただし、Hulu のように unique_viewed_series が約 15 億行ある規模では、全プロフィール間の類似度を直接計算するのは難しい。ユーザー数はアイテム数より大きくなりやすく、プロフィールの嗜好も時間で変化するためである。

そのため、ユーザーベース CF は説明や分析には便利だが、大規模オンライン候補検索では、アイテムベース CF、行列分解、Two-Tower、ANN などの方が使いやすいことが多い。

コンテンツベース検索

コンテンツベース検索は、作品自体の属性や説明文、embedding を使う検索である。教科書では、キーワードマッチング、TF-IDF、コサイン類似度が紹介されている。

キーワードマッチングは、完全一致に近い検索である。例えば、「ノーラン」「SF」「宇宙」「韓国ドラマ」などの語が一致する作品を拾う。

利点は高速で実装しやすいことである。一方で、表現揺れに弱い。

例えば、次の語は意味的に近いが、完全一致では別物である。

宇宙、惑星探索、スペース、銀河
刑事、捜査官、探偵
恋愛、ラブストーリー、ロマンス
Bluetooth イヤホン、ワイヤレスヘッドフォン

TF-IDF は、説明文中の語の重要度を使って作品をベクトル化する手法である。

\text{tfidf}(t,i) = \text{tf}(t,i) \log \frac{N}{\text{df}(t)}

ここで $t$ は語、 $i$ は作品、 $N$ は作品数、 $\text{df}(t)$ は語 $t$ を含む作品数である。

TF-IDF は説明文やタグがしっかりある作品には有効である。ただし、同義語や文脈理解には弱い。

埋め込み検索では、説明文、タグ、映像 fingerprint、mood tag などから dense vector を作り、コサイン類似度や内積で近い作品を探す。

\text{sim}(u,i) = \frac{\mathbf{p}_u^{\mathsf{T}}\mathbf{c}_i} {\|\mathbf{p}_u\|\|\mathbf{c}_i\|}

ここで $\mathbf{p}_u$ はプロフィールの嗜好ベクトル、 $\mathbf{c}_i$ は作品のコンテンツベクトルである。

コンテンツベース検索は、次の場面で強い。

新作で視聴ログが少ない
ロングテール作品を拾いたい
説明文やタグが豊富である
mood や映像 fingerprint が使える
協調フィルタリングだけでは人気作品に偏る

一方で、コンテンツだけでは「実際にユーザーが反応した関連」を拾いきれない。作品内容は似ていても、ユーザー行動上は一緒に見られないこともある。

協調フィルタリング検索

協調フィルタリング検索は、ユーザーと作品の相互作用パターンを使って候補を取り出す方法である。

Hulu では、unique_viewed_series からプロフィール、作品の二値行列を作れる。

\mathbf{R} \in \{0,1\}^{m \times n}

$\mathbf{R}_{u,i}=1$ は、プロフィール $u$ がシリーズ $i$ を 25% 以上視聴したことを表す。

協調フィルタリング検索には、主に次の形がある。

ユーザーベース CF
アイテムベース CF
行列分解による embedding 検索

行列分解では、 $\mathbf{R}$ をユーザー行列とアイテム行列に分解する。

\mathbf{R} \approx \mathbf{P}\mathbf{Q}^{\mathsf{T}}

ユーザー $u$ の潜在ベクトルを $\mathbf{p}_u$ 、作品 $i$ の潜在ベクトルを $\mathbf{q}_i$ とすると、候補検索では内積が大きい作品を取り出す。

s(u,i) = \mathbf{p}_u^{\mathsf{T}}\mathbf{q}_i

この方法では、作品メタデータを使わなくても、視聴パターンから潜在的な嗜好空間を学習できる。

ただし、協調フィルタリング検索にはコールドスタート問題がある。新作は視聴ログが少ないため、 $\mathbf{q}_i$ をうまく学習できない。新規プロフィールは視聴履歴がないため、 $\mathbf{p}_u$ をうまく作れない。

そのため、協調フィルタリング検索だけでなく、コンテンツベース検索や人気作品検索を組み合わせる必要がある。

ニューラル検索

ニューラル検索は、ユーザーとアイテムをニューラルネットワークで dense embedding に変換し、近いものを検索する方法である。

古典的なキーワード検索や TF-IDF は、語の一致や浅い特徴に依存する。一方、ニューラル検索では、ユーザーの視聴履歴、作品説明文、タグ、人物、mood、映像 fingerprint などを使って、意味的に近いものを同じ空間に写像できる。

候補検索で重要なのは、アイテム embedding をあらかじめ作ってインデックス化できることである。

オンラインリクエスト時には、次の処理を行う。

プロフィール $u$ の特徴からユーザー embedding $\mathbf{z}_u$ を作る
ANN インデックスから $\mathbf{z}_u$ に近い作品 embedding $\mathbf{z}_i$ を検索する
上位 $K$ 件を候補集合としてランキングへ渡す

スコアは例えば内積である。

s(u,i) = \mathbf{z}_u^{\mathsf{T}}\mathbf{z}_i

またはコサイン類似度を使う。

s(u,i) = \frac{\mathbf{z}_u^{\mathsf{T}}\mathbf{z}_i} {\|\mathbf{z}_u\|\|\mathbf{z}_i\|}

このニューラル検索の代表例が、添付図の左側にある Two-Tower Neural Network、つまり TTSN である。

Two-Tower Neural Network

Two-Tower Neural Network、TTSN は、ユーザー側とアイテム側を別々のニューラルネットワークで埋め込みに変換するモデルである。添付図の左側では、User Features が User Tower に入り、User Embedding になる。一方、Item Features は Item Tower に入り、Item Embedding になる。最後に両者の dot product または similarity score を計算する。

数式で書くと、ユーザー特徴を $\mathbf{x}_u$ 、アイテム特徴を $\mathbf{x}_i$ とし、それぞれのタワーを $f_{\theta}$ 、 $g_{\phi}$ とする。

\mathbf{z}_u = f_{\theta}(\mathbf{x}_u)

\mathbf{z}_i = g_{\phi}(\mathbf{x}_i)

スコアは次のように計算する。

s(u,i) = \mathbf{z}_u^{\mathsf{T}}\mathbf{z}_i

この構造の最大の利点は、アイテム embedding をオフラインで事前計算できることである。アイテムタワーはユーザーに依存しないため、全作品に対して $\mathbf{z}_i$ を作り、ANN インデックスに入れておける。

オンラインでは、プロフィールの特徴から $\mathbf{z}_u$ だけを計算し、近い $\mathbf{z}_i$ を検索する。

Hulu での入力特徴を考えると、ユーザー特徴には次のようなものが入る。

profile_id embedding
視聴済み series_id の embedding 集約
最近視聴したジャンル分布
最近視聴した mood 分布
長期嗜好 embedding
短期嗜好 embedding
SVOD/TVOD 反応傾向
視聴曜日や時間帯

アイテム特徴には次のようなものが入る。

series_id embedding
genre
sub_genre
sockets_tag
casts
film_directors
premiere_year
service_type
avg_mood_tag
avg_fingerprint
説明文 embedding

TTSN の学習では、実際に視聴されたユーザー、作品ペアを正例にする。暗黙的フィードバックなので、unique_viewed_series の行が正例に近い。

(u,i^+) \sim \mathcal{D}^{+}

同じユーザーに対して、視聴されていない作品 $i^-$ を負例としてサンプリングする。

(u,i^-) \sim \mathcal{D}^{-}

単純な損失の例は、正例のスコアを負例より高くする pairwise loss である。

L = - \log \sigma \left( s(u,i^+) - s(u,i^-) \right)

または、1 つの正例と複数の負例を同時に比べる softmax loss を使う。

L = - \log \frac{\exp(s(u,i^+))} {\exp(s(u,i^+)) + \sum_{j \in \mathcal{N}_u} \exp(s(u,j))}

ここで $\mathcal{N}_u$ はユーザー $u$ に対してサンプリングされた負例集合である。

図 3: TTSN はユーザー側と作品側を別々に埋め込み化し、作品埋め込みを事前に索引化できるため候補検索に向いている。

ワークド例: TTSN の内積スコアと softmax loss

プロフィール P001 のユーザータワーが、次の 3 次元ユーザー embedding を出したとする。

\mathbf{z}_u = \begin{bmatrix} 0.8 & 0.4 & 0.1 \end{bmatrix}

候補作品のアイテム embedding が次の通りだとする。

\mathbf{z}_{\text{SPY x FAMILY}} = \begin{bmatrix} 0.7 & 0.5 & 0.2 \end{bmatrix}

\mathbf{z}_{\text{インターステラー}} = \begin{bmatrix} 0.2 & 0.9 & 0.7 \end{bmatrix}

\mathbf{z}_{\text{料理バラエティ}} = \begin{bmatrix} 0.1 & 0.2 & 0.9 \end{bmatrix}

内積スコアを計算する。

s(u,\text{SPY x FAMILY}) = 0.8 \cdot 0.7 + 0.4 \cdot 0.5 + 0.1 \cdot 0.2 = 0.78

s(u,\text{インターステラー}) = 0.8 \cdot 0.2 + 0.4 \cdot 0.9 + 0.1 \cdot 0.7 = 0.59

s(u,\text{料理バラエティ}) = 0.8 \cdot 0.1 + 0.4 \cdot 0.2 + 0.1 \cdot 0.9 = 0.25

この場合、TTSN は P001 に対して「SPY x FAMILY」を最も近い候補として返しやすい。

次に、学習時の softmax loss を数値で見る。正例が「SPY x FAMILY」、負例が「インターステラー」と「料理バラエティ」だとする。

L = - \log \frac{\exp(0.78)} {\exp(0.78) + \exp(0.59) + \exp(0.25)}

近似値を入れる。

\exp(0.78) \approx 2.18,\quad \exp(0.59) \approx 1.80,\quad \exp(0.25) \approx 1.28

したがって、正例確率は次のようになる。

\frac{2.18}{2.18 + 1.80 + 1.28} = \frac{2.18}{5.26} \approx 0.414

loss は次の通りである。

L = -\log(0.414) \approx 0.882

学習では、この loss が小さくなるようにユーザータワーとアイテムタワーを更新する。つまり、実際に視聴された「SPY x FAMILY」のスコアを上げ、負例のスコアを相対的に下げる方向に学習する。

TTSN が候補検索に向いている理由

TTSN は候補検索に非常に向いている。理由は、ユーザーとアイテムを同じ embedding 空間に置き、内積やコサイン類似度で検索できるからである。

ランキングモデルのように、ユーザーとアイテムを結合して複雑な MLP に入れるモデルは、全アイテムに対して毎回計算する必要がある。一方、TTSN はアイテム embedding を事前計算できる。

この違いは大きい。

TTSN のオンライン処理は次のようになる。

ユーザー embedding を 1 回計算する
ANN で近いアイテム embedding を検索する
上位候補を返す

つまり、全作品に対して重いモデルを実行しない。

Hulu の規模で考えると、item_information_table の各 series_id に対してアイテム embedding を作っておき、検索インデックスを構築する。リクエスト時には、profile_id の履歴からユーザー embedding を作り、近傍 series_id を取得する。

TTSN は、次のような場面で有効である。

大規模カタログから高速に候補を取りたい
アイテム特徴とユーザー特徴の非線形関係を学習したい
新作にコンテンツ特徴を使って embedding を与えたい
MF より柔軟な表現を使いたい
ANN インデックスと組み合わせたい

一方で、TTSN には限界もある。基本形の TTSN では、ユーザー embedding は候補アイテムに依存しない固定表現である。

例えば、同じプロフィールが次のような多面的な嗜好を持つとする。

平日は短いアニメを見る
週末は長尺の洋画を見る
家族と見るときはキッズ作品を見る
1 人のときは重いサスペンスを見る

1 つの固定ユーザー embedding にこれらを全部押し込むと、嗜好が平均化される。結果として、「どれにも少し近いが、今の意図には鋭く刺さらない」候補が出ることがある。

この問題を補うために、短期履歴を別ベクトルにする、複数 interest vector を持つ、セッション特徴を入れる、後段ランキングで DIN のような target-aware モデルを使う、といった工夫がある。

Deep Interest Network

Deep Interest Network、DIN は、ユーザーの過去行動の中で、現在評価している対象アイテムに関連する行動を強く見るモデルである。添付図の右側では、User Behavior Sequence から Item Embeddings を作り、Target Item に対して Attention Layer を適用し、Weighted Sum of Interests を作っている。その後、Target Embedding と結合し、MLP で予測スコアを出す。

DIN の核心は、ユーザー表現が対象アイテムごとに変わることである。

TTSN では、ユーザー $u$ の embedding $\mathbf{z}_u$ は基本的に候補アイテム $i$ に依存しない。

\mathbf{z}_u = f_{\theta}(\mathbf{x}_u)

一方、DIN では、ユーザー表現が対象アイテム $i$ に依存する。

\mathbf{h}_{u,i} = \sum_{t=1}^{T} \alpha_{t,i} \mathbf{e}_{u,t}

ここで $\mathbf{e}_{u,t}$ はユーザー $u$ の過去行動 $t$ 番目のアイテム embedding、 $\alpha_{t,i}$ は対象アイテム $i$ に対する注意重みである。

注意重みは、過去行動アイテムと対象アイテムの関連度から計算する。

\alpha_{t,i} = \frac{\exp(a(\mathbf{e}_{u,t}, \mathbf{e}_i))} {\sum_{\tau=1}^{T} \exp(a(\mathbf{e}_{u,\tau}, \mathbf{e}_i))}

$a(\mathbf{e}_{u,t}, \mathbf{e}_i)$ は attention score を出す関数である。単純な内積でもよいし、MLP でもよい。

最後に、対象アイテム embedding $\mathbf{e}_i$ と、対象アイテムに応じて集約されたユーザー興味 $\mathbf{h}_{u,i}$ を使って予測する。

\hat{y}_{u,i} = \text{MLP} \left( [\mathbf{h}_{u,i}, \mathbf{e}_i, \mathbf{x}_{u,i}] \right)

ここで $[\cdot]$ はベクトルの結合であり、 $\mathbf{x}_{u,i}$ は追加の文脈特徴である。

図 4: DIN は候補作品ごとに過去視聴への注意重みを変えるため、同じプロフィールでも候補に応じたユーザー表現を作れる。

ワークド例: DIN の attention を数値で計算する

プロフィール P001 が過去に次の 3 作品を見たとする。

「SPY x FAMILY」
「インターステラー」
「料理バラエティ」

ここでは説明のため、各作品の embedding を 2 次元にする。

\mathbf{e}_{\text{SPY x FAMILY}} = \begin{bmatrix} 0.9 & 0.1 \end{bmatrix}

\mathbf{e}_{\text{インターステラー}} = \begin{bmatrix} 0.2 & 0.9 \end{bmatrix}

\mathbf{e}_{\text{料理バラエティ}} = \begin{bmatrix} 0.1 & 0.2 \end{bmatrix}

候補作品が「TENET」だとする。候補 embedding は次のように置く。

\mathbf{e}_{\text{TENET}} = \begin{bmatrix} 0.3 & 0.8 \end{bmatrix}

attention score を単純な内積で計算する。

a(\text{SPY x FAMILY}, \text{TENET}) = 0.9 \cdot 0.3 + 0.1 \cdot 0.8 = 0.35

a(\text{インターステラー}, \text{TENET}) = 0.2 \cdot 0.3 + 0.9 \cdot 0.8 = 0.78

a(\text{料理バラエティ}, \text{TENET}) = 0.1 \cdot 0.3 + 0.2 \cdot 0.8 = 0.19

softmax で注意重みに変換する。指数の近似値は次である。

\exp(0.35) \approx 1.42,\quad \exp(0.78) \approx 2.18,\quad \exp(0.19) \approx 1.21

合計は次の通りである。

1.42 + 2.18 + 1.21 = 4.81

したがって、注意重みは次のようになる。

\alpha_{\text{SPY x FAMILY}, \text{TENET}} = \frac{1.42}{4.81} \approx 0.295

\alpha_{\text{インターステラー}, \text{TENET}} = \frac{2.18}{4.81} \approx 0.453

\alpha_{\text{料理バラエティ}, \text{TENET}} = \frac{1.21}{4.81} \approx 0.252

候補が「TENET」のとき、過去履歴の中では「インターステラー」が最も強く参照される。次に、重み付き興味ベクトル $\mathbf{h}_{u,\text{TENET}}$ を計算する。

\mathbf{h}_{u,\text{TENET}} = 0.295 \begin{bmatrix} 0.9 & 0.1 \end{bmatrix} + 0.453 \begin{bmatrix} 0.2 & 0.9 \end{bmatrix} + 0.252 \begin{bmatrix} 0.1 & 0.2 \end{bmatrix}

1 次元目は次である。

0.295 \cdot 0.9 + 0.453 \cdot 0.2 + 0.252 \cdot 0.1 = 0.3813

2 次元目は次である。

0.295 \cdot 0.1 + 0.453 \cdot 0.9 + 0.252 \cdot 0.2 = 0.4876

したがって、対象作品「TENET」に対するユーザー興味は次になる。

\mathbf{h}_{u,\text{TENET}} \approx \begin{bmatrix} 0.381 & 0.488 \end{bmatrix}

同じプロフィールでも、候補が「SPY x FAMILY Season 2」なら、「SPY x FAMILY」履歴の注意重みが大きくなるはずである。ここが DIN の本質である。固定のユーザー embedding を 1 つ作るのではなく、候補作品ごとに「過去のどの視聴を重視するか」を変えている。

DIN の直感

DIN の直感は、「ユーザーの過去履歴を全部同じ重みで見るのではなく、今評価している候補に関係する履歴を見る」ということである。

例えば、あるプロフィールが次のような履歴を持つとする。

キッズアニメ
宇宙 SF
韓国恋愛ドラマ
ノーラン監督作品
料理バラエティ

候補が「重厚な宇宙 SF 映画」であれば、DIN は宇宙 SF やノーラン監督作品に高い注意重みを置くべきである。

候補が「料理バラエティ」であれば、料理バラエティの履歴に高い注意重みを置くべきである。

候補が「キッズアニメ」であれば、キッズアニメ履歴を重視する。

つまり、DIN はプロフィールの多面的な嗜好を、候補アイテムごとに切り替えて使う。これは家族共有プロフィールや、多ジャンル視聴プロフィールで特に有効である。

DIN は候補検索向きか、ランキング向きか

添付図では TTSN と DIN が並んでいるため、どちらも候補検索モデルに見えるかもしれない。しかし実務的には、基本形の DIN は候補検索よりランキングに向いている。

理由は、DIN のユーザー表現 $\mathbf{h}_{u,i}$ が対象アイテム $i$ ごとに変わるからである。

TTSN では、アイテム embedding を事前計算して ANN インデックスに入れられる。ユーザー embedding も 1 回作ればよい。

DIN では、候補アイテムごとに attention を計算する必要がある。つまり、全作品に対して DIN を実行すると重い。

この違いをまとめると次の通りである。

観点	TTSN	DIN
ユーザー表現	候補に依存しにくい固定 embedding	候補ごとに変わる target-aware 表現
アイテム embedding の事前索引化	しやすい	基本形では難しい
候補検索への適性	高い	低いから中程度
ランキングへの適性	中程度	高い
強み	高速、大規模検索、ANN と相性が良い	多面的な興味、短期意図、候補別の関連履歴
弱み	嗜好が平均化されやすい	推論コストが高い

したがって、典型的な構成は次のようになる。

TTSN や MF や item CF で数百から数千件の候補を取る
DIN のような target-aware モデルで候補を精密にスコアリングする
再ランキングで多様性、配信制約、キッズ安全性を調整する

ただし、DIN 的な attention を候補検索に使う研究や実装もある。その場合は、ユーザーの interest vector を複数作って ANN 検索する、履歴を短く切る、事前にセッション embedding を作るなどの工夫が必要になる。

TTSN と DIN を Hulu で使うなら

Hulu の候補検索で TTSN を使う場合、オフラインとオンラインを分ける。

オフラインでは、全 series_id に対してアイテムタワーを実行し、作品 embedding を作る。

\mathbf{z}_i = g_{\phi}(\mathbf{x}_i)

この $\mathbf{z}_i$ を ANN インデックスに登録する。インデックス作成時には、配信終了作品やブラックリスト作品を除外するか、検索後にフィルタする。

オンラインでは、profile_id の履歴からユーザー特徴を作る。

\mathbf{z}_u = f_{\theta}(\mathbf{x}_u)

その後、ANN で近い作品を取得する。

\mathcal{C}_u^{\text{ttsn}} = \text{ANNTopK}(\mathbf{z}_u, \{\mathbf{z}_i\})

DIN を使う場合は、TTSN などで取ってきた候補に対して、候補ごとの関連履歴を見てスコアリングする。

例えば候補が「宇宙 SF」なら、ユーザー履歴の中で宇宙 SF、ノーラン作品、重厚な洋画に注意が向く。候補が「キッズアニメ」なら、キッズアニメ履歴に注意が向く。このようにして、1 つのプロフィールに複数の嗜好が混ざっていても、候補ごとに見るべき履歴を変えられる。

ANN が必要になる理由

TTSN や行列分解で embedding を作っても、全作品との内積を毎回正確に計算すると重い。そこで近似最近傍探索、ANN を使う。

ANN は、完全に正確な最近傍を探す代わりに、十分近い候補を高速に探すアルゴリズムである。

候補検索では、少し近似誤差があっても許容されることが多い。なぜなら、後段のランキングで再評価するからである。それよりも、低レイテンシで多くのユーザーに候補を返せることが重要である。

教科書で後続章に出てくる LSH、ANNOY、HNSW は、ANN の代表的な方法である。

LSH: 近いベクトルが同じバケットに入りやすいようにハッシュする
ANNOY: ランダム射影木を使って近傍探索する
HNSW: 階層的な近傍グラフを使って高速に探索する

実務では HNSW 系のインデックスがよく使われる。高い検索品質と高速性を両立しやすいからである。

候補検索とランキングの違い

候補検索とランキングは混同しやすいが、目的が違う。

候補検索の目的は、良さそうな作品を漏らさず集めることである。多少ノイズがあってもよい。

ランキングの目的は、候補の中から最終表示順を精密に決めることである。候補数が少ないため、より重い特徴量やモデルを使える。

例えば、候補検索では TTSN の内積だけで上位 1000 件を取る。ランキングでは、その 1000 件に対して、DIN、GBDT、DNN、ルール、配信制約、多様性制御を使って上位 50 件を作る。

この分担は重要である。候補検索に精密さを求めすぎると遅くなる。ランキングに全カタログを渡すと重すぎる。候補検索は広く速く、ランキングは狭く深く、という役割分担である。

候補のマージと重複排除

複数の検索パスを使うと、同じ作品が複数のパスから出てくる。例えば、ある作品が item CF、TTSN、人気作品検索のすべてから出てくることがある。

候補検索では、これらをマージして重複排除する。

\mathcal{C}_u = \text{dedup} \left( \bigcup_{r \in \mathcal{R}} \mathcal{C}_{u}^{(r)} \right)

ここで $\mathcal{R}$ は検索パス集合である。

重複排除した後も、検索パス情報は消さない方がよい。ランキング特徴量として使えるからである。

例えば、次のような特徴量を作れる。

どの検索パスから出たか
何個の検索パスから出たか
各検索パスでの順位
各検索パスでのスコア
視聴済み作品のどれに似て出たか

複数の独立した検索パスから出た候補は、強い候補である可能性が高い。一方、人気検索からだけ出た候補は、個人化の根拠が弱いかもしれない。

候補検索で先にフィルタすべきもの

候補検索では、推薦不可能な作品をできるだけ早めに除外する必要がある。

Hulu の item_information_table では、次の列が関係する。

publish_start_at
publish_end_at
search_start_at
search_end_at
is_blacklist
rating_name
kids_mature_flg
service_type
is_coming_soon
is_live

例えば、配信終了済み作品やブラックリスト作品は候補から除外する。

\mathcal{I}_{\text{eligible}} = \{ i \in \mathcal{I} \mid \text{published}(i) \land \neg \text{blacklisted}(i) \}

候補検索は、この推薦可能集合 $\mathcal{I}_{\text{eligible}}$ の中で行う。

ただし、すべての制約を候補検索段階で完全に処理するとは限らない。例えば、多様性制御や棚ごとの表示ルールは再ランキングで行うことが多い。候補検索段階では、絶対に出してはいけないもの、出しても意味がないものを主に落とす。

Hulu での具体的な候補検索設計例

Hulu のホーム推薦を考えると、次のような候補検索パスが考えられる。

継続視聴候補
アイテムベース CF 候補
コンテンツ embedding 類似候補
TTSN embedding 候補
トピック嗜好候補
人気作品候補
新着作品候補
配信終了間近候補
TVOD 関連候補
編集部キュレーション候補

それぞれの候補数を固定することもある。例えば、TTSN から 500 件、item CF から 300 件、人気から 100 件、新着から 100 件、継続視聴から 50 件を取る、という形である。

このように quota を持たせると、1 つの検索パスが候補集合を独占するのを防げる。

ただし、固定 quota は柔軟性に欠ける。履歴が豊富なプロフィールには個人化候補を多くし、新規プロフィールには人気や新着を多くするなど、ユーザー状態に応じて候補配分を変える方がよい場合もある。

オフライン評価

候補検索の評価では、ランキング後の最終指標だけでなく、候補集合の再現率を確認する。

典型的には、過去のある時点 $t$ までの履歴で候補検索を行い、その後に実際に視聴された作品が候補に入っているかを見る。

\text{Recall@K} = \frac{1}{|\mathcal{U}|} \sum_{u \in \mathcal{U}} \frac{ |\mathcal{C}_u^{(K)} \cap I_u^{\text{future}}| }{ |I_u^{\text{future}}| }

ここで $I_u^{\text{future}}$ は評価期間中にプロフィール $u$ が視聴した作品集合である。

候補検索では、次の指標も見る。

Recall@K
HitRate@K
候補カバレッジ
ロングテールカバレッジ
新作カバレッジ
ジャンル多様性
候補生成レイテンシ
インデックス更新時間
推薦可能制約違反率

特に、候補検索の Recall@K が低い場合、ランキングモデルをいくら改善しても限界がある。ランキングは候補集合の中でしか戦えないからである。

オンライン評価

オンラインでは、候補検索単体の効果を切り分けるのは難しい。最終的な表示はランキングや再ランキングの影響も受けるからである。

それでも、候補検索の改善は次の指標に現れる。

視聴開始率
25% 以上視聴率
完了率
連続視聴率
ホーム画面のクリック率
長期リテンション
新作露出
ロングテール露出
検索パス別の採用率

注意点として、候補検索の Recall を上げるだけではオンライン指標が上がるとは限らない。候補が増えすぎてランキングが混乱することもある。候補の質、候補の多様性、ランキングとの相性が重要である。

実務上の注意点

第 1 に、候補検索はランキングよりも前にあるため、ここで漏れた作品は救えない。候補検索の評価では必ず Recall@K を見るべきである。

第 2 に、候補検索パスを複数持つべきである。TTSN だけ、CF だけ、人気だけに依存すると、特定のユーザーや作品群に弱くなる。

第 3 に、候補検索では鮮度が重要である。publish_start_at、publish_end_at、is_coming_soon、is_blacklist などは常に更新される。インデックスが古いと、配信終了済み作品や不適切作品が候補に残る。

第 4 に、ANN の近似誤差を理解する必要がある。ANN は高速だが、完全な TopK ではない。インデックスパラメータによって Recall とレイテンシがトレードオフになる。

第 5 に、TTSN のユーザー embedding が平均化されすぎないようにする必要がある。長期嗜好、短期嗜好、セッション嗜好を分けることが有効である。

第 6 に、DIN のような target-aware モデルは強力だが、全カタログ検索には重い。候補検索で絞ってからランキングで使うのが基本である。

第 7 に、候補検索ログを残すべきである。どの候補がどの検索パスから出たか、検索時スコアはいくつか、ランキングで何位になったか、表示されたか、視聴されたかを追えるようにする。これがないと、候補検索の改善が難しい。

まとめ

候補検索は、全カタログからランキング対象となる小さな候補集合を高速に作る工程である。目的は、最終順位を決めることではなく、将来ユーザーが反応しそうな作品をできるだけ漏らさず拾うことである。

Hulu のような動画配信では、unique_viewed_series の暗黙的フィードバックと、item_information_table の作品特徴を使って、複数の検索パスを組み合わせるのが自然である。

代表的な検索パスは次である。

アイテムベース検索
トピックベース検索
ユーザーベース CF
アイテムベース CF
行列分解 embedding 検索
コンテンツ embedding 検索
TTSN によるニューラル検索
人気、新着、継続視聴、編集枠

添付図の TTSN は、ユーザーとアイテムを別々のタワーで embedding 化し、内積や類似度で高速検索するモデルである。アイテム embedding を事前計算して ANN インデックス化できるため、候補検索に向いている。

一方、DIN は対象アイテムに応じて過去行動への注意重みを変えるモデルである。多面的な嗜好や短期意図を捉える力が強いが、候補ごとに attention を計算するため、基本的には候補検索後のランキングに向いている。

実務的には、TTSN、CF、コンテンツ検索、人気、新着などで広く候補を集め、DIN やランキングモデルで精密に並べ替え、最後に配信制約、安全性、多様性を調整する構成が扱いやすい。