基多面体のオンライン予測

基多面体上のオンライン予測
畑埜晃平
九州大学大学院システム情報科学研究院
2012.11.29-30
文科省数学・数理科学と諸科学・産業との連携研究WS
「離散構造と最適化：展開と連携」
共同研究者
•
•
•
•
末廣大貴（九大）
来嶋秀治（九大）
瀧本英二（九大）
永野清仁（東大）
本発表
“Online Prediction over Submodular Constraints,” ALT’12, 2012.
目次
1. 離散構造のオンライン予測問題
2. 本研究の概要：基多面体上のオンライン予測
3. まとめ・未解決問題など
離散構造を用いた
“オンライン”意思決定問題
プレイヤー
離散構造
環境
累積損失を
小さくしたい
損失
オンライン意思決定問題の例
オンライン最短経路
離散構造
s-t パス
オンラインスケジューリング
オンラインネットワーク最適化
順列
全域木
例：オンラインスケジューリング問題
• 教授と n人の学生
• T日間，毎日教授は各学生とディスカッションをする
• 学生のフロー時間（待ち+処理時間）の総和の累積を小さく
したい
• 各学生に要する時間は不明
Let’s discuss
A
B
in the order of
A, C, D, B !
C
D
time
オンラインスケジューリング問題 (2/3)
e.g.
フロー時間 = 待ち時間+ 処理時間
待ち時間
A
処理時間
0
C
D
B
１日の総フロー時間
順列を表現するベクトル
損失ベクトル
6
オンラインスケジューリング問題(3/3)
Let’s discuss
in the order of
A, C, D, B !
(1,2,3,4), (1,2,4,3)...
順列の集合C  

...(4,3,2,1)

c1  C
t=1
Let’s discuss
in the order of
C, A, D, B !
損失
c1   1
損失
t=2
c2  C
c2   2
7
…
オンライン離散構造予測問題
仮定:
C: 離散構造のクラス
各離散構造を n 次元ベクトルで表現(C∈ 𝑅 𝑛 )
プロトコル：各時刻 t=1,…T において
１離散構造　ct  C
プレイヤー
（敵対的）環境
３
プレイヤーの損失　ct   t
 t [0,1]n
２損失ベクトル　オンライン離散構造予測問題(2)
プレイヤーのゴール：
T
T
リグレット
　 ct   t  min  c   tの最小化
t 1
プレイヤーの
累積損失
cC
t 1
（後から見て）
最良の離散構造の
累積損失
補足：リグレットｖｓ競合比
• オンラインアルゴリズムの解析には
T
c
が用いられる
t
t
競合比  t 1 T
min  c   t
cC
t 1
• 一方，オンライン予測の分野では多くの場合
競合比→ 1（T→∞）となるためリグレットを採用
• 問題によっては競合比＋リグレットで測る場合もある
（例：オフライン問題がNP困難な場合など）
既存研究
• Follow the Peturbed Learder(FPL) [Kalai & Vempala 03]
– オフライン離散最適化手法をサブルーチンとして用いる
– リグレットは若干他手法に劣る
• Kakadeらの手法 [Kakade+ 09]
• オフライン近似離散最適化手法をサブルーチンとして用いる
• 各ステップ毎の実行時間は多項式時間だが T に依存
• 個々の離散構造に対する手法
– 全域木[Cesa-Bianch&Lugosi 09]
– 順列[Helmbold&Warmuth 09][Yasutake+ 11][Yasutake+ 12]
– パス・・・[Koolen+ 10]
汎用的＆効率的かつリグレットの小さい手法が求められる
どうやってリグレットを最小化するか？
～多くの手法に共通する戦略～
連続緩和＋ラウンディング
離散構造を表現する
ベクトル
ct
プレイヤー
ラウンディング
連続ベクトル
wt
連続ベクトルの
オンライン予測アルゴリズム
（既存手法，リグレット保証付き）
損失ベクトル
t
連続ベクトルのオンライン予測
Follow the Regularized Leader（FTRL）
予測方法：
 t

wt 1  arg min   w   j Dw , w0 
wW
 j 1

累積損失
基準となるベクトルからの
ダイバージェンス
多くの場合，解析的な更新が可能
具体例：Hedge [Freund&Schapire 97], OGD [Zinkevich 03]
リグレット：
 
O T
（多くの場合に最適）
射影とラウンディング
conv(C): クラスC の要素の凸包
射影
入力：　zR
z
n
出力：
x *  min D( x , z )
x conv(C)
conv(C)
x
*
D : Bregmanダイバージェンス
(２ノルム距離，
KLダイバージェンス等
)
ラウンディング
入力：
x  conv(C )
出力：
c  C s.t.E (c )  x
conv(C)
x
射影とラウンディング(2)
FTRLによる更新
conv (C )
wt
wt 1
射影の利点
リグレットを保存
ラウンディングの利点
損失を保存
射影
wt  1
2
 最良のconv(C )の内点  最良の連続ベクトル




 に対するリグレット   に対するリグレット

 

E(ct   t )  wt   t
離散構造の期待損失
conv(C)の内点の損失
要点
小さいリグレットを得るには離散構造のクラスCに
対する射影とラウンディングがあればOK
問題点
• 多くの離散構造のクラスに対して射影・ラウンディングは
計算困難（一般に離散構造の候補は指数個）
• 個々の離散構造ごとに設計が必要
目次
1. 離散構造のオンライン予測問題
2. 本研究の概要：基多面体上のオンライン予測
3. まとめ・未解決問題など
本研究の概要
• 基多面体の端点で表現される離散構造に対する
射影・ラウンディングの設計
• 基多面体の端点で表現される離散構造の例
–
–
–
–
–
–
エキスパート [Littlestone&Warmuth 94][Vovk 90]
k-set [Warmuth&Kuzmin 08]
順列 [Yasutake+ 11][Helmbold&Warmuth 09]
全域木 [Lugosi&Cesa-Bianch 06][Koolen+ 10]
k-forest
オンライン予測分野において
truncated permutation
知られていない例
準備
• 劣モジュラ関数と基多面体
劣モジュラ関数
定義
関数 𝑓: 2{1,…,𝑛} → R が劣モジュラ関数⇔
A, B  {1,..., n}, k  {1,..., n} s.t. A  B　かつk  B,
f ( A  {k})  f ( A)  f ( B  {k})  f ( B)
例
g
f ( S )  g (| S |)
g : 上に凸な関数
|A|
|B|
|S|
基多面体
定義
劣モジュラ関数f : {1,..., n}  R　に対する基多面体B( f )


n
B( f )   x  R | S  {1,2,..., n},  xi  f ( S ),  xi  f ({1,2,..., n}) 
i S
i{1, 2 ,..., n}


x1+ x2=f({1,2})
例（n=2）
x1  f ({1})
x2  f ({2})
x1  x2  f ({1,2})
x2
f({2})
B(f)
f({1})
x1
基多面体（n=3）
x1  f ({1})
x2  f ({2})
x3  f ({3})
x1  x2  f ({1,2})
B(f)
x2  x3  f ({2,3})
x1  x3  f ({1,3})
x1  x2  x3  f ({1,2,3})
一般には2n-1個の線形制約，高々n!個の端点を持つ
conv(C)=B(f)となる離散構造の例(1)
離散構造のクラスC
ベクトル表現
劣モジュラ関数
(0,0,0,1,0,0)
1, | S | 1
f (S )  
0, | S | 0
エキスパート
“n 人のエキスパートから
１人を選択”
1が１つ
|S|
k-set
“n 人のエキスパートから
k人の組み合わせを選択”
(0,1,0,1,0,1)
k , | S | k
f (S )  
| S |, | S | k
1がk 個
|S|
conv(C)=B(f)となる離散構造の例(2)
離散構造のクラスC
ベクトル表現
劣モジュラ関数
|S |
順列（Permutahedron）
(3,4,2,1,6,5)
損失はn人の
待ち時間の総和
f ( S )   (n  1  i )
i 1
|S|
truncated permutation
(3,4,3,1,4,4)
損失は上位k人を
除いたn-k人の
待ち時間の総和
(n  k ) | S |, | S | k

|S |
f (S )  
(n  k )k   (n  1  i ), | S | k
i  k 1

(n-k)がk 個
|S|
本研究の概要
• 基多面体の端点で表現される離散構造に対する
射影・ラウンディングの設計
S
Aアルゴリズム
A関数オラクル
f (S )
– O(n6)時間
– O(n2)時間(特殊ケース)
– 関数オラクルの呼出しは単位時間で出来ると仮定
本結果１：基多面体に対する射影と
ラウンディング
定理
基多面体B(f) に対する射影とラウンディングは多項式時間
で計算可能．
（ここで，ダイバージェンスは２ノルムとKLダイバージェンスに限定）
アイデア
• 基多面体上の分離可能な凸関数の最小化は
劣モジュラ関数最小化（SFM）に帰着可能[Nagano 07]
• SFMは多項式時間で計算可能[e.g., Orlin 07]
• SFM解法の多くは端点の線形結合で解を構成
• 副産物としてラウンディングも構成可能
•
詳しい話は永野先生にお願いします！ :-)
本結果２：特殊な場合
定義
劣モジュラ関数fがcardinarity-based ⇔∃𝑔, 𝑓 𝑆 = 𝑔( 𝑆 )
定理
劣モジュラ関数fが cardinarity-based ならば
基多面体B(f) に対する射影とラウンディングはO(n2)時間
で計算可能．
（ここで，ダイバージェンスは２ノルムとKLダイバージェンス
に限定）
例：エキスパート, k-set,順列，truncated permutation
キーアイデア:“順序保存”補題
定義
劣モジュラ関数 f が交換可能⇔
i

j
i  j  {1,..., n}, x  B( f )  ( x1 ,..., x j ,..., xi ,..., xn )  B( f )
注： f がcardinarity-based ならば交換可能
“順序保存”補題
f を交換可能な劣モジュ
ラ関数とし，
x *  min D( x, z )とする．
xB ( f )
このとき，
zi1  zi2  ...  zin  x*i1  x*i2  ...  x*in
順序保存補題を適用すると・・・
簡単のためz1  z 2    z n ( x1*  x*2    x*n )と仮定
min D( x , z )
sub.to :
x1  f ({1})  g (1)
min D( x , z )
x2  f ({2})  g (1)
sub.to :
x3  f ({3})  g (1)
x1  f ({1})  g (1)
x1  x2  f ({1,2})  g (2)
x1  x3  f ({1,3})  g (2)
x2  x3  f ({2,3})  g (2)
x1  x2  x3  f ({1,2,3})  g (3)
2n-1個の制約
x1  x2  f ({1,2})  g (2)
x1  x2  x3  f ({1,2,3})  g (3)
n個の制約
幾何学的解釈
(2, 1, 3)
(1, 2, 3)
不等式制約は2n-１個
(3, 1, 2)
“有効な”不等式制約はn-１個
(3, 2, 1)
(2, 1, 3)
(3, 1, 2)
(5, 4, 3)
(５，４，３)と同じ
順序をもつ端点
ダイバージェンスが２ノルムの場合
n
min  ( xi  zi ) 2
x
i 1
sub.to :
x1  g (1)
x1  x2  g (2)
x1  x2  x3  g (3)

n個の線形制約を持つ２次計画問題
＝＞多項式時間で解ける
本研究：貪欲手法により O(n2) 時間
で解ける
（KLダイバージェンスの場合も同様）
x1  x2    xn  g (n)
簡単のためz1  z 2    z nと仮定
x*が射影となるための必要十分条件(1)
x *が射影  1 ,...,  n 1  0,  s.t.
x1*  z1  1   2   3    n 1  
x 2  z2
*
  2   3    n 1  

xn*1  z n 1
xn*  z n
  n 1  

n
*
x
 i  g ( n)
i 1
i
 i *

 i   x j  g (i )   0,  i  0,  x*j  g (i )
j 1
 j 1

x*が射影となるための必要十分条件(2)
x *が射影  1 ,...,  n 1  0,  s.t.
z1
左図
n
*
x
 i  g ( n)
z2
i 1
*
x1
z3
x2*
α1
x3
*
z4
α2
α2
α3
α3
α3
x4*
α4
η
α4
η
α4
η
α4
η
i
 i *

 i   x j  g (i )   0,  i  0,  x*j  g (i )
j 1
 j 1

相補性条件
z5
i
x5*
η
 i  0   x*j  g (i )
j 1
i
x
j 1
*
j
 g (i )   i  0
不等式制約を等式で満たすiでαi>0
x*が射影となるための必要十分条件(3)
i
x
j 1
*
j
 g (i )を満たすiで i  0
i
 x*j  g (i)を満たすiで i  0
z1  z 2  z3  z 4
z1  z 2  z3
x1*
x1*
j 1
z1  z 2
z1
g(2)
g(1)
*
x1
α1
α2
α3
α4
η
*
x2
α1
α2
α2
α3
α3
α
α44
η
η
g(3)
x2*
x1*
x2*
x1*
z1  z 2  z3  z 4  z5
x3*
α1
α2
α2
α3
α3
α3
α4
α4
α4
η
η
η
x2*
g(4)
x3*
x4*
α1
α2
α2
α3
α3
α3
α4
α4
α4
α4
η
η
η
η
g(5)
x3*
x4*
x5*
α1
α2
α2
α3
α3
α3
α4
α4
α4
α4
η
η
η
η
η
射影のアイデア
i
z
j 1
i
 g (i )
が最大となるような
i を選ぶ(i  3)
i
3
1  2 2  3 3  3 4  3   zi  g (3)と設定
i 1
3
2
1  2 2  2 3  2  1  2 2  3 3  3 4  3   2
3
同様に，1   2   3    z1  g (1)
よって，
x1*  g (1), x1*  x2*  g (2)
 zi  g (3)
i 1
α1= α2 =0!!!
3
2
2
z
i 1
i
 g (2)
2
2
  zi  g (2)
i 1
射影のアイデア(2)
3
1  2 2  3 3  3 4  3   zi  g (3)と設定
i 1
z1  z 2  z3  z 4
z1  z 2  z3
1   2  0
z1  z 2  z3  z 4  z5
x1*
x1*
z1  z 2
x1
x2*
x1*
z1
x2*
x1*
g(1)
α1
α2
α3
α4
η
g(2)
α1
α2
α2
α3
α3
α
α44
η
η
x3*
g(3)
x2*
*
α1
α2
α2
α3
α3
α3
α
α44
α4
η
η
η
x2*
g(4)
x3*
x4*
α1
α2
α2
α3
α3
α3
α4
α4
α4
α4
η
η
η
η
g(5)
x3*
x4*
x5*
α1
α2
α2
α3
α3
α3
α4
α4
α4
α4
η
η
η
η
η
射影のアイデア(3)
3
1  2 2  3 3  3 4  3   zi  g (3)と設定
1   2  0
i 1
残りの α3 ,α4 ,ηは後で決まる
残りを同様の手法で処理（高々n回）
ここまでは確定(O(n)時間)
z1'  z 2'  z3'  z 4'  z5'
z1'  z 2'  z3'  z 4'
g(4)
g(1)
x1*
x1*
x1*
x2*
x1*
x1*
g(3)
g(2)
g(5)
x2*
x2*
x2*
x3*
*
x4*
α4
η
x3
計算時間はO(n)×n=O(n2)
x3*
x4*
x5*
α4
η
η
ラウンディングのアイデア
簡単のため，順列の場合のみ議論
(1, 3, 2)
(1, 2, 3)
(3, 1, 2)
(2.75, 2, 1.25)
(3, 2, 1)
(2, 1, 3)
(2, 3, 1)
conv(C)内部の点をO(n)個の端点の凸結合で表現
ラウンディングのアイデア(2)
x1
x  B( f )
x2
x3
x4
x5

 * ((5,4,3,2,1)  (5,1,2,3,4)) / 2

x1 ' x2 '
x3 '
毎ステップ後に段差が１つ以上
消滅⇒O(n)ステップで終了
x4 ' x5 '
詳細は来嶋先生に・・・
目次
1. 離散構造のオンライン予測問題
2. 本研究の概要：基多面体上のオンライン予測
3. まとめ・未解決問題など
まとめ
• オンライン離散構造予測問題
• 既存研究：これまでは個々の離散構造ごとに
アルゴリズムを設計する必要があった
（汎用的なアプローチも存在するが予測精度
や計算効率で劣る）
• 本研究：基多面体で特徴づけられる離散構造
のクラスに対する汎用的な手法
（射影・ラウンディングの設計）
未解決問題（１）
問題：多面体に基づく，より一般的オンライン予測の特徴付け
は可能か？
例：順列
• Permuthahedron と Birkhoff polytope
• いずれも効率的な射影・ラウンディングが可能
[Yasutake+11][Helmbold&Warmuth 09]
(1 3 2)
Permutahedron(基多面体)
1 0 0


0 0 1
0 1 0


Birkhoff polytope（???）
未解決問題（２）
“オフラインーオンライン”変換 [Kakade+ 09]
• オフライン離散近似アルゴリズムを用いて
“近似”射影を実現
• 毎ステップあたりの計算時間・・・Tに依存
問題：より効率的な変換手法は構成できるか？
Cf. Meta Rounding [Carr&Vempala 02]
オフライン離散近似アルゴリズムを用いてラウンディングを
実現（ただし，整数性ギャップの制限されたアルゴリズムを
仮定）
Take Home Message
オンライン予測分野だけでも
離散最適化にまつわる問題はまだまだある

Download Report