論文メモ

TencentRec: Real-time Stream Recommendation in Practice

概要

  • 一定の時間間隔でモデルを更新する従来のレコメンダーシステムでは、最新のウェブアプリケーションの要件を満たすことができない
  • 本稿では、リアルタイムレコメンデーションにおける「ビッグ」「リアルタイム」「アキュレート」の3つの課題に取り組む
  • 「システム」「アルゴリズム」「データ」という3つの側面から、Stormをベースとした一般的なリアルタイム・ストリーム・レコメンデーション・システム「TencentRec」を提案
  • はアイテムベースの協調フィルタリング、コンテンツベース、デモグラフィックベースのアルゴリズムを含む、いくつかの古典的な実用的な推薦アルゴリズムをTencentRecに実装
  • アイテムベースCFアルゴリズムを詳細に紹介
  • リアルタイムのデータ収集と処理を強化することで、レコメンデーションの変化をリアルタイム
  • TencentRecを一連のプロダクション・アプリケーションに展開し、毎日100億のユーザー・リクエストに対して正確なリアルタイム・レコメンデーションを提供
  • 大量のデータストリームを分析するために、様々なデータ・アクセスと大量のステータス・データ・ストレージを処理するために、Tencent Data Access（TDAccess）とTencent Data Store（TDStore）という2つのコンポーネントをそれぞれ開発
  • 以下の三つのアルゴリズムを実装
    • アイテムベースの協調フィルタリング[16]
    • デモグラフィックベースのアルゴリズム[19]
    • コンテンツベースのアルゴリズム[18]
  • TencentRecはすでに本番運用されている
  • 1日に100億件のユーザーリクエストと1PB以上のデータを扱い、ユーザーに正確なリアルタイム推薦を提供する上で優れた性能を達成

システムアーキテクチャ

  • 1日に処理しなければならないユーザーアクションは約40億回、生成されるデータは1PB以上
  • TencentRecは1日に100億件のユーザーリクエストを処理する必要があり、約1兆回の計算が発生
  • 膨大な計算をサポートするためには、数千台のマシンで構成されるクラスターが必要
  • ストリーム処理フレームワークとして、Yahoo S4 2, Spark Streaming 3, and S- torm 4を比較検討
  • リアルタイム推薦計算をサポートするためにStormを選択
  • Stormは、データのストリームを処理する分散型リアルタイム計算システム
    • Stormを選んだ理由
        1. Stormはリアルタイムのデータストリーム計算をサポート
        1. Stormは、クラスタ内のノードを動的に追加または削除できる優れたスケーラビリティ
        1. Stormは、高速な障害回復が可能なステートレスシステムであるため、耐障害性をもつ
        1. Stormは、シンプルなプログラミングモデル、幅広いプログラミング言語のサポート、Stormの使用に優れたサポートを提供できる活発なオープンソースコミュニティなどの利点
  • Stormクラスタの構造を示しており、「Nimbus」と「Supervisor」という2種類のノード
  • Tencent Data Access (TDAccess)
  • 通信モデルには、Publish/Subscribeモデルを採用
  • 従来のキューのように、データを保存しないというわけではない。データをディスクにキャッシュ。
  • Tencent Data Store (TDStore)と呼ばれる分散メモリベースのキーバリューストレージを利用して、推薦計算に使用されるステータスデータを保存

推薦アルゴリズム

  • 暗黙のフィードバック問題を解決
  • リアルタイムアイテムベースCFのためのスケーラブルな増分更新メカニズムを提案
  • 計算コストを削減するためのリアルタイム・プルーニング技術を提案
  • アイテムペアにリンクタイムを設定し、ある期間内にユーザーが一緒に評価した場合のみ、2つのアイテムが関連しているとみなす
  • TencentRecでは、毎日40億以上のユーザーアクションが発生
  • ニュースを例にとると、各ユーザーは毎日平均して10個以上のニュースを評価
  • Hoeffding bound理論
  • Hoeffding boundは、[10]において、データストリーム分析のための非常に高速な決定木を構築するために使用
  • ほとんどの推薦システムでは、ユーザーとアイテムのペアの数に比べて、すでに得られた評価の数は通常非常に少ない => data sparsity

計算資源

  • 最大のクラスターには約200台のコンピュータが搭載されており、クラスター全体では約1500台のコンピュータが搭載
  • 全体のクラスターは、1日に40億のユーザーアクションタプルを扱い、データサイズは1PB以上
  • 1日に100億回のユーザーリクエストがあり、1秒間に最大50万回のリクエストがある
  • 各リクエストには平均で50回の計算が必要で、TencentRecは1兆回近い計算
  • それでも、安定してリアルタイムのレコメンドを提供することが可能

まとめ

  • TencentRecと呼ばれる包括的なレコメンデーション・システムを紹介
  • Stormを採用
  • 様々なデータアクセスと大量のステータスデータの保存を処理するために、TDAcessとTDStoreをそれぞれ開発
  • 協調フィルタリング、コンテンツベース、デモグラフィックベースなど、業界でよく使われているレコメンデーションアルゴリズムを実装
  • 実用的なアイテムベースのCFアルゴリズムを提案し、暗黙のフィードバック問題に対するロバスト性、スケーラブルなインクリメンタル・アップデート、リアルタイム・プルーニングなどの優れた特性を備えている
  • TencentRecは、細分化されたキャッシュ、コンバイナー関数、マルチハッシュ技術などの最適化を利用
  • TencentRecは、1日あたり約40億件のリアルタイム・ユーザー・アクション・データ・タプルと100億件のレコメンド・リクエストを長期にわたって処理