読者です 読者をやめる 読者になる 読者になる

バンディットアルゴリズムの復習5:Combinatorial bandits

バンディット 機械学習 論文・資料・スライド集

書きかけ、後ほど各アルゴリズムの説明や実験など追加予定。→ 終わり

日本語で検索してもCombinatorial banditsは出てこなかったのでメモ。 UCBまではたくさん実装出てくるけど、Combinatorial bandits以降はほとんど実装も検索に出てこない感じだった。

前回

matroid bandit

やりたいこと

マトロイド上の確率的なモジュラー関数を最大化したい。 モジュラー関数はこの問題ではある集合EからとってきたKこのアイテムに付いている重みの総和(Eは後ほど定義します)。各アイテムの重みはL次元のベクトル (0, 1, 0, 0, 1...)のようにかけてこれが確率的に決まる、というもの。この重みが1になるかどうかの確率分布Pの形はもちろん初めは不明。このPをバンディットの枠組みで求める。

Matroid

Matroid -- from Wolfram MathWorld

Augmentation property

日本語Wiki: マトロイド - Wikipediaの(A3)のこと

f:id:misos:20161207032400p:plain

Wikipediaより抜粋

ここの E を一般的に ground set と言う。問題設定のある集合Eはこれのことを指しています。

Modular Function

Modular Function -- from Wolfram MathWorld

Maximum-weight basis of the matroid

https://en.wikipedia.org/wiki/Matroid#Greedy_algorithm

もしもすべてのアイテムの重みがわかっていれば、貪欲法を使って簡単に解ける問題に。 最小全域木問題はマトロイドのMaximum-weight basisの例になっていて、もしも枝の重みが全て初めからわかっていたらクラスカル法のように貪欲な手法で解くことができる。

クラスカル

  1. 木の集合を作成する(初めは頂点1こ1こが木)
  2. 枝の集合を軽い順にソート( e1 < e2 < e3 ... < el)
  3. while 枝の集合が空でない
    3.1. eiを集合から取り除く
    3.2 eiの両端が別々の木ならそれらを連結する

アルゴリズム:Optimistic Matroid Maximization

問題設定

マトロイドバンディットは マトロイドMとL次元の重みwの分布Pの対(M, P)。 それぞれの重みwは確率的で、i.i.dでPから生成されるとする、wの重みは非負の値を持つ。

バンディットと結びつけるために、集合Eに含まれるアイテムeはそれぞれ一本のアームに対応づけられている。 そしてアームは同時に複数弾けると仮定、同時に引くアームの集合をAと呼んで「アームAを引いた」=「Aの中のアーム全てを引いた」ということにして、このアームAを引いた時にはAに含まれるアイテムの重みの総和が報酬として得られる。

入力はマトロイドM=(E, F), アイテムの集合EとEの部分集合の族F。 最小全域木の文脈でいいうとEが木の枝の集合、Fがエッジの部分集合を適当な形で集めた族(空集合も含まれる)。 出力は枝の平均重みがもっとも軽くなるようなEの部分集合をFから選んで出力する。

アルゴリズム詳細

以下、最小全域木の文脈の場合。

  • すべての枝の重みを観測する(アームを引く)
  • アームごとにUCBを計算する
  • アームをUCBの順番に並べる(大きい、もしくは小さい順。問題設定による)
  • 'At' を空集合にする
  • UCBによってソート済みのアームを順番に選択していき...
    • A^t2^E個の枝の部分集合(部分集合の作り方の全パターン)-F の場合にならない限り
    • A^tに枝を追加していく
  • UCBを更新するための計算
  • A^tに含まれるアームの報酬の平均値を計算 -> 出力

これを一周(one episode)として何度も繰り返す。

元論文

Kveton, Branislav, et al. "Matroid bandits: Practical large-scale combinatorial bandits." Proceedings of AAAI Workshop on Sequential Decision-Making with Big Data. 2014.

その他関連論文

Chen, Wei, et al. "Combinatorial multi-armed bandit and its extension to probabilistically triggered arms." Journal of Machine Learning Research 17.50 (2016): 1-33.

Wen, Zheng, et al. "Efficient learning in large-scale combinatorial semi-bandits." Proceedings of the 32nd International Conference on Machine Learning. 2015.

Combes, Richard, Mohammad Sadegh Talebi Mazraeh Shahi, and Alexandre Proutiere. "Combinatorial bandits revisited." Advances in Neural Information Processing Systems. 2015.