週刊 spaghetti_source

multiplicative weights update method

15:59

今回は乗算型重み更新（multiplicative weights update method）について説明します．いろんな問題に適用できる手法ではありますが，基本的には「連続最適化問題の近似解を得る手法」なので，離散最適化問題・厳密解を重視する競技プログラミング的にはあまり役に立たなそうなネタです．ただし，実装は超容易なので，覚えておくと得することはあるかもしれません．

...

乗算型重み更新は双対勾配法の一種 [Baes-Burgisser 2010] で，様々な分野で何度も再発明されているテクニックです．特に機械学習分野では標準的な技法だったようですが，最適化分野で注目が高まったのは [Arora-Hazan-Kale 2007] による「sparsest cutのSDP緩和を高速に解く」という話からでした．この結果以降，サーベイ論文 [Arora-Hazan-Kale 2012] （2010年にプレプリントとして公開）を参考にした Lecture Note が多くの最適化分野の人によって書かれており，現在では標準的手法の１つになった感があります（see: Google検索： multiplicative weights, lecture note）．

なお，より詳しい歴史的背景は [Arota-Hazan-Kale 2012]を参照してください．今回の解説もこのサーベイ論文を参考にしています．

さて，以下では乗算型重み更新の説明を行いますが，これは「幅広い問題に対するアルゴリズムの設計方針」みたいなものなので，抽象化して説明するのが大変です．自分が思うに，乗算型重み更新を理解するには，いろんな例題に対して適用してみるのが良さそうなので，今回は典型的な２つの問題に対して適用してみます．照明のパターンが重要なので，興味のある方は是非紙とペンを持って計算をフォローしてみてください．

...

問題１．オンライン意思決定問題

次の状況設定を考えましょう．

• n 個の判別機がある．
• 質問が繰り返し与えられる．各質問に対して
  • 判別機は独立に答え（Yes / No）を出力する．
  • 自分も何かしらの答えを出力する．
  • 質問の正答が教えられる．

この設定で，トータルの自分の正答数をできるだけ多くするのが目的となります．どのように各判別機の結果を参考にするかが戦略（意思決定）にあたります．乗算型重み更新では，この問題に対して次のアルゴリズムを設計します．

• 重み p := (1, ..., 1) ∈ R+^n と初期設定する．
• 各質問に対して以下を実行する：
  • 重みに比例する確率で各判別機の回答を採用し，出力する．
  • 間違えた判別機の重みを exp(-h) 倍する（h は小さな正の数）．

イメージとしては「たくさん間違えるとどんどん重みが軽くなり，答えが採用されなくなる」という感じです．重みの変化のさせ方には様々なバリエーションがあると思いますが，上のように exp 倍で重みを変化させるテクニックのことを乗算型重み更新といいます．

※exp(-h) 倍のかわりに (1 - h) 倍するものも乗算型重み更新と呼びますが，exp の展開を考えると本質的に同値なので区別しません．一応 exp(-h) 型更新を「Hedge algorithm」といい，(1 - h) 型更新を「multiplicative weights update」と呼んで区別することもあるようです．

乗算型重み更新で重要なことは，結果の評価にあります．今回の場合次の結果を証明することができます：

定理． 自分が間違える回数は，判別機の中の最多間違い回数 + log n / h + O(h) 倍以下．

証明． k 番目の質問のときの重みを p(k) とし，k 番目の質問に対する各判別機の成果を u(k) とします（正答なら u(k)_j = 0，誤答なら u(k)_j = 1）．判別機 j の k 回目までの間違え回数が Σ[l=1:k] u(l)_j となることに注意してください．

ポテンシャル関数 F(k) := p(k)_1 + ... + p(k)_n とおいて，質問に対してどのように変化するかを評価します．

　F(k+1) = Σp(k)_j exp(-h u(k)_j)

ですが，右辺を h が十分小さいとして展開すると

　F(k+1) = Σp(k)_j ( 1 - h u(k)_j ) = F(k) - h (p(k), u(k))

となります．ここで (p(k), u(k)) / F(k) は k 番目の質問に対して自分が間違える確率に等しいので，それを m(k) という記号であらわすことにすると

　F(k+1) = F(k) - h F(k) m(k) = F(k) ( 1 - h m(k) ) = F(k) exp(-h m(k))

となります．ただし最後の等号では再び exp の近似展開を使っています．この式を繰り返し代入すると

　F(k+1) = F(1) exp(-h Σm(l)) = exp(log n - h Σm(l))

となりますが，一方で，F の形から，任意の j について

　F(k+1) ≧ p(k+1)_j = exp(-h Σ[l=1:k] u(l)_j )

という評価も成立します．これらをあわせて

　Σm(l) ≦ log n / h + Σ[l=1:k] u(l)_j

となります．誤差のオーダを見積もると + O(h) であることもわかります．//

...

証明のポイントは２点ありました．

• F(k) と F(k+1) の差の評価で「自分の損失（間違え確率）」が出ること．
• p(k)_j の評価で「各判別機の損失」が出ること．

特に各評価が exp の肩に乗っていることから，全体としてO(log n)の評価できることに強みがあります．全体としてO(n)の誤差でいいなら普通の -h 的更新でも可能です．

※上のように確率的にせず，決定的に行なっても類似の評価ができますが，評価の質が劣化します．これは「完全ランダム戦略」で1/2正答率が保証されることと関係があります．

---

問題２．二人ゼロ和ゲームの鞍点

行列 A に対し，min[x] max[p] p A x を満たす確率ベクトル x, p を求める問題を二人ゼロ和ゲームの鞍点問題といいます．ゲーム理論で有名なNash均衡の存在定理は min[x] max[p] = max[p] min[x] が成り立つ，というものでした．

この問題は，普通は線型計画問題に帰着して解きますが，乗算型重み更新でも解くことができます．

• p = (1, ..., 1) と初期化する．
• c := p A について min[x] c x を満たす確率ベクトル x を求める．
• p_j = exp( h (A x)_j ) と更新する．

定理． p(k)/Σp(k)_j := q(k) とおく．このとき Σq(l) A x(l) / T は鞍点の値の log n / h T 近似である．

証明． 先程と同じく F(k) := p(k)_1 + ... + p(k)_m と置いて評価してみます．まず F(k) の漸化式は

　F(k+1) = F(k) + h (p(k) A x(k)) = F(k) (1 + h q(k) A x(k)) = F(k) exp(h q(k) A x(k))

となります．漸化式を繰り返し適用して

　F(k+1) ≦ exp(log n + h Σq(k) A x(k))

となりますが，一方で

　F(k+1) ≧ p(k+1) = exp(h Σ(A x(l))_j)

という評価も得られるので，x(l) の平均を単に x とおいて整理すると

　(A x)_j ≦ log n / h T + 1/T Σq(l) A x(l)

となります．これが任意の j について成り立つので，任意の確率ベクトルと内積して

　q A x - log n / h T + ≦ 1/T Σq(l) A x(l)

と整理しておきます．いま，左辺を q で最大化すると max[q] q A x ≧ min[x] max[q] q A x = OPT であり，右辺は x のとり方から q(k) A x(k) = max[x] q(k) A x ≦ min[q] max[x] q A x = OPT となるので

　OPT - log n / h T + ≦ 1/T Σq(l) A x(l) ≦ OPT

となって，1/T Σq(k) A x(k) が鞍点の log n / h T 近似になっていることが示されました．//

ここからもう少し頑張ると Σx(l)/T と Σp(l)/T が鞍点の近似解になっていることがわかります．

実装例

２つ目の例題：二人ゼロ和ゲームの鞍点，の実装を示します．実装が恐ろしくシンプルなことに注目してください．

def mult_weight():
  epsilon = 0.1;
  x = [1.0 for i in range(n)];
  y = [0.0 for j in range(m)];
  T = int(n / (epsilon*epsilon) );
  for t in range(T):
    c = [sum(x[i] * a[i][j] for i in range(n)) for j in range(m)];
    j = max(zip(c, itertools.count()))[1];
    y[j] += 1.0;
    x = [x[i] * (1 - epsilon * a[i][j]) for i in range(n)];
  return (normalize(x), normalize(y));
def normalize(x):
  return map(lambda t: t / sum(x), x);

参考文献

• S. Arora, E. Hazan, and S. Kale (2007): A combinatorial, primal-dual approach to semidefinite programs, Proceedings of the 39 annual ACM symposium on Theory on computing, pp.227-236.
• M. Baes and M. Burgisser (2010): Hedge algorithm and subgradient methods, Optimization Online.
• S. Arora, E. Hazan, and S. Kale (2012): Multiplicative weights update method: a meta-algorithm and its applications (Reserarch Survey), Theory of Computing Journal, vol.8, no.6, pp.121-164.