バンディット系のメモです。かなり適当です、すいません。

元論文

Learning Hidden Features for Contextual Bandits

Wang, Huazheng, Qingyun Wu, and Hongning Wang. “Learning Hidden Features for Contextual Bandits.” Proceedings of the 25th ACM International on Conference on Information and Knowledge Management. ACM, 2016.

実装の(一部は)以下にあります。

github.com

まとめると

普通のContextual Banditでは利用可能なデータを全て特徴量として扱う
実際にはデータ全てを用いることは計算量的にも望ましくないし、必要なデータを特徴ベクトルとして全て観測できる設定は現実に即していない
そのため、潜在的な特徴をユーザとアイテムに追加して観測できなかった特徴をモデル化
regretの上限を証明して、また coodinate descent は一部のパラメータだけを参照してデータを更新するので計算速度も比較的はやい
性質上、スパースなデータでは精度向上の幅は小さい

背景

Contextual Bandit

Contextual Banditとはバンディット問題における探索と活用のトレードオフを補助的な情報（つまり、ユーザーやアームに関する特徴量）を用いて最適にしてゆく問題設定。通常はアクセスできる特徴全てを利用して報酬( もしくは損失 )をモデル化する。

推薦システムのところで既出。

paper.hatenadiary.jp

既存手法の問題点

このようなContextual Banditで利用可能な情報全てを用いて計算を行うのは現実的ではない。ニュースのレコメンド例を用いて考えてみると、全ての情報を使いたくないので例えば「ニュースのカテゴリ」、「ニュースの発生場所」を特徴としてContextual Banditを行う。このような時、例えば「ニュースの発信源」でニュースをみるか決めている人についてはいつまでたっても正しいレコメンドはできない。つまり、一部の人にだけ特化した推薦システムができてしまう。しかし、利用可能な情報全てを初めから用いた推薦システムの構築は難しく、プライバシーの問題などから当初は利用できない特徴もある時がある。なので、そのような利用できない特徴もモデル化できるContextual Banditのアルゴリズムが欲しい。

Latent Factor Model

おそらく理解に必要なので。

Latent factor models for Collaborative Filtering from sscdotopen

www.slideshare.net

座標降下(Coordinate Descent)法

いつか張った気がしますが、再掲。

coordinate descent 法について from 京都大学大学院情報学研究科数理工学専攻

www.slideshare.net

問題設定

入力は、 - アームの集合A - アームを引く回数T - 各アームの特徴ベクトルX - ユーザーの集合U

出力は、 - 時刻tにアームaとユーザーuを選択した時の regret の時系列

最終的な目的関数は - オラクル(ベストな選択肢)を常に選択する場合と比較して regret を最小にすること

注意として、入力には含めてないけれどもモデル化する潜在的な特徴量の次元数をあらかじめ定めておく必要あり。

アルゴリズム

f:id:misos:20170602024752p:plain

時刻tにおけるユーザーuに対してアームaを選択した時のregretは、アームの特徴（context）とユーザーの嗜好（θ_u）とガウスノイズを使って上のように記述できる。

けれども応用先によっては、アームの特徴に関する情報全てに常にアクセスできるとは限らない。つまり、上の式でのxに手元にあるデータ全てを与えるのは現実的ではない。なので観測できない特徴ベクトルとそれに対応するバンディットのパラメータを導入すると regret は

f:id:misos:20170602030753p:plain

とかける。今、アームに新しく潜在特徴ベクトルをつけたのでユーザーの特徴ベクトルにもそれに対応する潜在ベクトルを追加する。あとはこの追加した潜在ベクトルに対応するパラメータを coordinate descent にて求める。

f:id:misos:20170602174451p:plain

この時、回帰にて最適化する式は (報酬の推定値と実際に観測した値の二乗誤差)と(ユーザーの特徴ベクトルに対する正則化項)と(アイテムの潜在ベクトルに対する正則化項)を追加したもの。この式に対して、regretのバウンドが証明されている。新たに考量する潜在的な特徴ベクトル v 関係する項をなくせば、確かに普通の contextual bandit の式の形になる。