自己学習するAIと推薦システムへの応用 〜 Open Ended Learningの紹介

機械学習 ディープラーニング 推薦

opg

こんにちは、データシステム部のAnirudh Gururaj Jamkhandiです。私はECにおけるユーザーの購買率向上を目指して、推薦アルゴリズムの研究開発に携わっています。

高機能な計算機の登場により、現在では様々な業界で機械学習が飛躍的に利用されています。特に、深層学習は特定のタスクにおいては、人間の能力をはるかに超える結果を出しています。しかし、人間にとっては初歩的な能力である、自ら問題を生成したり他のタスクに一般化する能力はまだありません。近年、そういった課題を解決するための学習アルゴリズムの開発が盛んに行われています。本記事では、そのようなアルゴリズムの1つである「Open Ended Learning」を紹介します。

目次

はじめに

この10年間、機械学習の技術はこれまでになく発展し、実社会への導入が行われてきました。Artificial Intelligence Index Report 2019によると、グローバル企業の50％以上が、少なくとも1つの機能にAIを採用していると言われています。AIは楽観的な予測と大規模な投資が行われてきた一方で、特に自動運転・家事代行・音声アシスタント技術の開発においては、失望・信頼の喪失や投資減（「AIウィンター」）の時期も見られます。このような落ち込みの理由として考えられるのは、学習アルゴリズムが汎化されない、あるいは不測の事態にうまく適応できないことです。この問題は、アルゴリズムに収益を依存している企業、特にECにも大きく影響します。従って、不測の事態でもうまく機能する学習アルゴリズムの開発は実サービスにおいて重要な課題となっています。

ZOZOでは、機械学習アルゴリズムが様々な場面で利用されています。例えば、ユーザーへのアイテムのレコメンド、画像検索などがあります。これらのタスクでは、各領域の専門家が根本的な問題を特定し、指標やインプットを最適化することで問題解決する必要があります。特に推薦システムでは、データの少ない新規ユーザー、新規アイテム、多様性などに対応するモデル開発をすることになります。このような複雑な課題を認識し、かつ解決できるアルゴリズムはあるのでしょうか。本記事では、このような多様で複雑な問題を生成・特定し、同時に未知の状況にもうまく一般化して解決できる「Open Ended Learning（以下、OEL）」という手法を紹介します。

Open Ended Learningの紹介

state-of-the-artとされる既存手法からさらに改善する方法は、問題を選んだり時には作ったりして、それを解決しようとするアプローチでした。そうすることでアルゴリズムが改善され、それが課題解決に役立ちます。一方、人工生命の研究者が提唱する自然進化に基づくアプローチは、問題を解決するだけでなく、問題を自動生成するアルゴリズムを作ることです。OELとは、学習モデルが好奇心を絶やさず、自ら挑戦的な学習機会を生み出すような学習のことです。設定した問題のみを解決する機械学習アルゴリズムとは異なり、OELは私たちの想像を超える驚きを生み出してくれる可能性も秘めています。

Open Ended Learningの研究の現状

人工生命の研究者たちは、以前からOELの研究・調査をしてきました。しかし、取り組むべき課題の複雑さが増すにつれ、進化のために利用できるデータが足りないことに気付き、この研究が活発化し始めました。主要な例としては、Uber AIのWangらが「二足歩行ロボット」に適用したPOET（Paired Open Ended Trailbrazer）やDeepMindが「かくれんぼ」や「旗取りゲーム」などに応用した研究があります。いずれの研究も、ある環境で学んだ経験を別の環境に応用させるOELによって汎化性能を改善しています。最近よく見られるGenerative Adversarial Networks（GAN）もOELの一種です。

ZOZOでも様々な状況でのレコメンデーションをシミュレートすることで、既存性能を超えるアルゴリズム開発を試みています。強化学習に基づき、逐次的なユーザー行動のモデル化を行い、長期的なエンゲージメントを最大化する手法です。

次に、このようなシステムとユーザー行動の相互作用を使って動的に変化させる、つまりインタラクティブな推薦システムの設計を紹介します

インタラクティブな推薦システムの問題設定

この推薦システムでは、セッションにおける報酬の最大化を目標とします。

セッション最適化では、状態 \mathrm{S}、行動 \mathrm{A}、報酬関数 \mathrm{R}、遷移確率 \mathrm{P}、割引係数 \gamma を持つMarkov Decision Process（MDP）としてモデル化できます。

  • 状態 \mathrm{S}

    • ユーザーの特徴（デモグラ、興味など）と過去の行動に関連した情報（過去の推薦結果、閲覧・クリック・カートに追加したアイテム、満足度など）の両方を表す

  • 行動 \mathrm{A}

    • 選択されたアイテム、Iは推薦アイテム候補
    • 選択し得るアイテムサイズkが固定されていると仮定すると、 \mathrm{A} は \mathrm{A} \subset \mathrm{I} s.t. \mathrm{|A|} = \mathrm{J} であり、 \mathrm{J} はアイテムサイズを表す

  • 遷移確率 \mathrm{P}(\mathrm{S^{'}} | \mathrm{S}, \mathrm{A})

    • 状態 \mathrm{S} で行動 \mathrm{A} をとったときに状態が \mathrm{S^{'}} になる確率を表す

  • 報酬 \mathrm{R}(\mathrm{S}, \mathrm{A})

    • 行動 \mathrm{A} による期待報酬であり、行動 \mathrm{A} のアイテムに対するユーザーエンゲージメントの度合を表す

私たちはこのような推薦システムの様々な部分をモデル化するためにRecSimフレームワークを使用し、ユーザー、アイテム、ユーザー×アイテム間の相互作用のモデル化にOELを利用しました。

インタラクティブな推薦をサポートするRecSimとそのコンポーネント

RecSimは、推薦システムに強化学習を用いるためのシミュレーションプラットフォームです。推薦候補アイテム群（以下、ドキュメント）に対してユーザー行動のシミュレーションを実施する環境を作成できます。このフレームワークは、いくつかのコンポーネントで構成されています。

以下にコンポーネントの特徴を示します。

  • 環境は、ドキュメントモデル、ユーザーモデル、ユーザー選択モデルで構成される
  • エージェントは、推薦結果を作成するためのモデル（以下、ポリシー）を持ち、ドキュメントとユーザーの特徴を利用して推薦する
  • ドキュメントモデルは、ドキュメントの特徴（品質などの潜在的な特徴と、評価や人気などの観測可能な特徴）の事前分布からドキュメントをサンプリングする
  • ユーザーモデルは、ユーザー特徴（満足度、興味などの潜在的特徴、年齢などの観測可能な特徴、セッションの長さなどの行動的特徴）の事前分布から、ユーザーをサンプリングする
  • ユーザー選択モデルは、エージェントのレコメンデーションに対するユーザーの反応をエミュレートする
    • 具体的には、推薦されたドキュメントの特徴とユーザーの特徴を用いて、利用しそうなドキュメントを選択する
  • ユーザー遷移モデルは、ユーザー選択モデルからドキュメントが選択された後に、このモデルを介してユーザー状態を更新する

これらのコンポーネントによって強化学習を行います。エージェントが環境と相互作用し、その相互作用に対するフィードバックを受け取り、期待報酬を最大化することでアクションの選択を最適化します。

次に、どのように推薦システムをシミュレートするのかを説明します。

シミュレーションの各ステップは、4つのプロセスで構成されています。図1は各コンポーネントとステップの関連を示しています。

  1. ユーザーモデルからユーザー状態を、ドキュメントモデルからドキュメントの特徴を要求し、それらをエージェントに送る
  2. エージェント（推薦アルゴリズム）は、現在のポリシーを使用して、ドキュメントセットを返す
  3. ユーザー選択モデルがドキュメントを選択する
  4. ユーザー遷移モデルを用いてユーザーモデルを更新し、報酬によってエージェントポリシーを更新する

このステップ内のプロセスは、あらかじめ設定された終了条件が満たされるまで繰り返されます。そして、最初のステップから最終状態までのすべての状態を集めたものがエピソードです。

recsim_block

図1：RecSimコンポーネントの全体像（引用：https://arxiv.org/pdf/1909.04847.pdf）

RecSimフレームワークを用いたアルゴリズムの設計

課題設定として、長期的なユーザー行動がモデル化された環境を目指します。なぜなら、過去の研究でユーザーの潜在的な状態は、レコメンデーションやサービスの変化に伴ってゆっくりと変化することが確認されているためです。この環境では、CTRは高いが満足度が弱いドキュメントもあれば、CTRは低いが満足度が高いドキュメントもあります。そのため、課題はこの2つのバランスをとり、長期的に最適なトレードオフを実現することです。満足度は潜在的な変数ですが、このシステムダイナミクスは部分的に観測可能です。満足度は、エンゲージメントの増減から推測できます。

このような環境に関するシミュレータは、以下のように設計されています。

ドキュメントモデル

モジュール特徴量の事前分布からモジュールをサンプリングします。モジュールの特徴量としては、CTR、CVR、価格などを使用します。そして、全モジュールのCTR、CVR、価格の平均と分散を求め、それぞれの特徴をガウス分布に当てはめてモジュール特徴量の事前分布とします。

ユーザーモデル

ユーザー特徴量の事前分布からユーザーをサンプリングします。各ユーザーは、net positive exposure ( \mathrm{npe_t}) と呼ばれる特徴量と、satisfaction ( \mathrm{sat_t}) と呼ばれる特徴量を持ちます。満足度は増加の抑制のため、ロジスティック関数を用いて表します。

\mathrm{sat_t} = \sigma \, ( \tau \cdot \mathrm{npe_t})

ここで \tau は ユーザー固有の感度パラメータ、t はエピソード内の時間ステップです。ユーザーがドキュメントを選択すると、 \mathrm{npe_t} は次のように進化します。

\mathrm{npe_{t+1}} = \beta \cdot \mathrm{npe_t} + 2(\mathcal{C} - 0.5) + \mathcal{N}(0,\eta)

ここで、 \beta はユーザー固有の記憶割引（忘却因子）、 \eta はイノベーションの標準偏差です、 \mathcal{C} は CTR です。そして、これが「ユーザー遷移モデル」です。

\mathcal{s_d} は、長期的なエンゲージメントの反応（ \mu_k, \sigma_k）とパルス消費の反応（ \mu_c, \sigma_c）を線形に補うパラメータを持つ対数正規分布で下記の定義とします。 \muと \sigmaはそれぞれの平均CTRと標準偏差です。

\mu_s = (\mathcal{C} \cdot \mu_c + (1-\mathcal{C}) \cdot \mu_k) \cdot \mathrm{sat_t}
\sigma_s = \mathcal{C} \cdot \sigma_c + (1-\mathcal{C}) \cdot \sigma_k
\mathcal{s_d} ~ log \mathcal{N}(\mu_s,\sigma_s)


このように、ユーザーの状態は( \mathrm{sat_t}, \tau, \beta, \eta, \sigma_k, \mu_k, \sigma_c, \mu_c) の組み合わせで定義され、ユーザー状態の唯一のダイナミクスは満足度として表されます。

ユーザー選択モデル

ユーザー反応をシミュレーションするために、CatBoostをモジュールのクリック確率予測に用います。

報酬機能

ここでは目標を累積報酬で表します。また、報酬は目標に向けた中間的なフィードバック（正または負）を提供します。今回は推薦結果によってユーザーの総合的なエンゲージメントを向上させることを目標としています。全体的な報酬機能は、以下の2つの要素で構成されています。

  • ランキングベースの報酬 : エージェントはモジュールの順位を直接予測する代わりに、順位式 \alpha, \phi, \delta の係数を予測するように学習します。そして、予測された係数を用いて、各モジュールのスコアを計算します。モジュールiのスコアは次のように与えられます。

    \mathrm{rankscore(i)} = \mathrm{ctr(i)^{\alpha}} \cdot \mathrm{cvr(i)^{\phi}} \cdot \mathrm{price(i)^{\delta}}
    次に、上位k個のスコアを抽出し、ポジションバイアス \mathrm{W}を割り当てます。そして、最終的なランキング報酬は、モジュール報酬の加重和として計算します。
    \mathrm{R} = \sum\limits_{i=0}^\mathrm{T} \mathrm{rankscore(i)} \cdot \mathrm{W}

  • エンゲージメントベースの報酬：ユーザー選択モデルがエージェントの推薦に対するユーザーの反応を予測すると、ユーザーは選択したモジュールに \mathcal{s_d} 秒（先に定義した）エンゲージメントします。エンゲージメント時間は、エージェントの推薦に対するユーザーの満足度としてフィードバックします。つまり、 \mathcal{s_d}を報酬として使用します。

「ランキングベースの報酬」はモジュールを適切にランキングした場合の報酬で、「エンゲージメントベースの報酬」はモジュールをクリックした場合の報酬です。最終的な報酬は、ランキングベースの報酬とエンゲージメントベースの報酬の合計です。

エージェント

POETの後継となるEnhanced POETというOELアルゴリズムを使用しています。POETの基本的な考え方は以下の通りです。

  1. ノベルティサーチ :

    従来、機械学習・深層学習・進化アルゴリズムを含む学習アルゴリズムは、特定の目的関数を解決するために使用されてきました。生物学的な進化は人間の知能を生み出す重要な要因の1つであり、自然界では全体的な目標がなく、ある機能のために進化した機能が他の機能に使われることもあります。従って、推論のルールをハードコーディングしたり、特定の性能指標で高得点を取るために学習するのではなく、新規性や興味深さを優先します。実際に、ある目的を完全に無視することで、その目的を追求するよりも早く最適化している事例もあります。

  2. ゴールの切り替え :

    1つのエージェントのみを使って新規性のある行動を生み出すのではなく、様々なニッチなタスクと各タスクのそれぞれで良い結果を出すエージェントを保持します。各エージェントは、自分のニッチなタスクで最適化された後、別のニッチな問題でも再度評価されます。もしそのエージェントが他のニッチなタスクで良い結果を出せば、そのエージェントは新しい目的のために最適化されます。従って、興味深い方向にアイデアを追いかけることでアルゴリズムは多様な結果を生み出し、問題を解決できます。

  3. 最小基準共進化（Minimal Criterion Coevolution）と品質の多様性 :

    自然界では、繁殖するために長く生き残るという基本的な原則に従っています。このシンプルな原理により、私たちは多様で複雑な環境を作り出すことができます。MCCでは相互作用する2つの集団を進化させることで、他の母集団に対して閾値（最小基準）を満たすことで生存できるようになり、オープンエンド（制約のなさ）を促進します。

アルゴリズム：POET

algorithm_image

図2：POETアルゴリズムの疑似コード（引用：https://arxiv.org/pdf/1901.01753.pdf）

このアルゴリズムは、図2のようにランダムに初期化された1つの「環境⇔エージェント」のペアから始まります。その後、POETはメインループの中で以下の3つのタスクを実行します。

  1. ペアになったエージェントを各環境に最適化する
    この際の最適化アルゴリズムには、進化戦略を用います。

  2. N(mutate)インターバルごとに対象となる環境パラメータを変異させる
    残したい環境は、ペアとなったエージェントがある閾値を超えている環境です。ある環境が変異元の対象となった場合、まずその環境の子環境を作るために数回の変異（新規性の探索）を行います。その後、新しい環境が簡単すぎず、かつ難しすぎない（品質の多様性を確保する）ことを保証するために、元のペアエージェントとMCCで照合します。これらの操作後に残った環境を異なる環境とペアになったエージェントとテストし、最も良いパフォーマンスを示したものを新しいペアエージェントとして残します。
    mutation_image

    図3：平原の環境に切り株が発生した環境変異の例（引用：https://arxiv.org/pdf/2003.08536.pdf）

  3. N(transfer)インターバルごとに対象となる環境パラメータを変異させる
    このステップではすべてのエージェントが各環境でテストされ、どれかが元のペアのエージェントよりも優れた性能を発揮した場合、より優れたエージェントに置き換えられます。図4の \theta はエージェントのポリシーです。
    goal_switching

    図4：ゴールの切り替えを行いながら変異するステップ（引用：https://icml.cc/media/icml-2019/Slides/4336.pdf）

アルゴリズム：Enhanced POET

POETを汎用的に利用するために、従来では環境の分布パラメータとして表現されていた部分が環境エンコーディング（EE）と環境キャラクタリゼーション（EC）に分離されました。

EEには座標を入力して幾何学的なパターンを生成するニューラルネットワークであるCPPN（Compositional Pattern Production Network）を提案し、ECにはPATA-EC（Performance of All Transferred Agents Environmental Characterization）という指標を提案しています。これは環境の新規性評価には相応の対処が必要であるという考えに基づき、新環境ではすべてのエージェントでその環境との報酬を算出します。そして、相対的なエージェントの順番がどれだけ違うかによって新規性を評価します。

このように新しい環境を生成することで、新たな挑戦を続けるアルゴリズムがPOETです。ペアエージェントは、ニューラルネットワークで表現され、期待報酬を最大化するために状態（ユーザー状態とRecSimでシミュレートされたモジュールの状態）と行動（ランキング生成のための係数）を対応させるポリシーを学習します。

トレーニングプロセス

training_process

図5：トレーニングプロセスの全体像（引用：https://arxiv.org/pdf/1902.00851.pdf）

図5は、エージェントがユーザーと相互作用し、報酬（≒エンゲージメント）を最大化するトレーニングプロセスです。学習は、シミュレータがドキュメントモデルとユーザーモデルからそれぞれの特徴量を要求し、エージェントに送信することから始まります。エージェント（Enhanced POET）は、現在のポリシーを使ってランキング係数を予測し、推薦結果を生成します。ユーザー選択モデルは、その推薦結果に対してモジュール特徴量とユーザー状態を考慮し、ユーザーの選択を予測します。シミュレータは、ユーザー遷移モデルを用いてユーザーモデルを更新し、ユーザーの反応と報酬を用いてエージェントポリシーを更新します。

ZOZOにおけるOpen Ended Learningの推薦システムへの応用

問題設定

現在、ZOZOTOWNのトップページのデザインは「モジュール」構造になっています。「モジュール」とは、図6のようにセール対象商品や新作商品などの特集化されたコンテンツ集合を表しています。

図6：「チェックしたアイテム」モジュールの例

そして、このページではユーザー体験を向上させるために、主に2種類のパーソナライズド・レコメンデーションを提供しています。図7のようなモジュール内での商品推薦とモジュール順序の最適化です。本記事では、後者のモジュール順序の最適化に焦点を当てます。

図7：モジュール・ランキングによるZOZOTOWNのカスタマイズ

また、ZOZOTOWNには、毎日多くの新規ユーザーが訪問し、新着アイテムも多く追加されます。このようなデータの少ないユーザー、アイテムではコールドスタート問題が発生します。

さらに、レコメンデーションに多様性を持たせることで、ユーザー体験の向上が期待できます。

ZOZOTOWNでは、RecSimフレームワークを使用した推薦環境でモジュールランキングのオフライン実験を行いました。

なお、学習プロセス全体は、大規模な実データに対応するためFiber Frameworkを用いて並列化させます。本ケースでは、20の環境とそのペアエージェントをアクティブなものとして実験しています。学習の進捗状況の測定には、研究論文と同様に累積新規環境作成・解決数 ANNECSという指標を使用しています。ANNECSスコアは、新しい環境がMCCをクリアし、かつ設定した報酬の閾値を超えた環境数のカウンターです。そのため、本スコアはニッチであり、有意義な変異を実現した指標となります。

実験結果と考察

結果としては、図8のように学習が進むにつれANNECSスコアは増加し、アルゴリズムがますます有意義な課題を生み出していることを示しました。最終的に10,000イテレーションの学習後、ANNECSスコアは130以上となりました。

annecs_graph

図8：イテレーション数とANNECSスコア

この実験の主な目的は、OELを推薦タスクに応用して複雑な問題を解決すると同時に新しい問題を見つけ出し、またある環境での進化が別の環境でどのように適応するかを確認することでした。そして、シミュレータを使ったオンライントレーニングで20の環境とそのペアエージェントを作成した後、これらをオフライン評価で比較し、最も性能の良いモデルを1つ選定しました。

MODEL PRECISION@10 RECALL@10 NDCG@10
Collaborative Filtering 1.929 13.669 0.0599
NCF 2.522 17.878 0.0868
LamdaMART 2.321 17.683 0.0849
BPRMF 2.483 17.6 0.0837
Direct Curriculum using ES 2.462 17.532 0.0828
Enhanced POET 2.598 17.789 0.0891

このモデルを他のランキングモデルと比較したところ、OELを用いた推薦システムで他の手法よりも優れた結果を得ることができました。この結果とANNECSスコアの増加グラフにより、アルゴリズムが新しい問題を見つけ、それを解決できたことを示しています。

結論と今後の課題

OELが何を発見し、どのような未来をもたらすかはわかりません。そのため、この不確実性に懐疑的な人はPOETのようなシステムを「ランダム性をもたらすアルゴリズム」と解釈するかもしれません。しかし、進化の考え方にヒントを得て不確実性を取り入れたOELは、昨今興味深い研究や多くのコンテストで盛り上がりを見せています。将来的には、レコメンデーションシステムをはじめとする様々なアプリケーションで、このようなおもしろいアルゴリズムが利用されるかもしれません。

ZOZOでは一緒にサービスを作り上げてくれる仲間を募集中です。ご興味のある方は、以下のリンクからぜひご応募ください！

hrmos.co

カテゴリー