Distributed Multiplicative Weights
Methods for DCOP

(分散制約最適化問題に対する分散乗算型重み更新法)
ERATO感謝祭 Season II吉田 悠一
Joint with 波多野 大督

COP: 制約最適化問題
最小s-tカット
入力：グラフG = (V = {1, 2, …, n}, E), 頂点s, t ∈ V
目的：s, t間の最小カットを求める

s

2

4

1t
6

35

制約最適化問題
制約最適化問題 (Constraint Optimization Problem, COP)
入力：グラフG = (V, E),定義域Di (i ∈ V),
コスト関数fij: Di × Dj → ℝ+ (ij ∈ E)
目的：コストの低い割当を求める
割当φのコストf(φ) := Σij∈Efij(φi, φj)
最小s-tカット24t1f45

sf24

1f23

Ds = {0}, Dt = {1}Di = {0, 1} (i ∈ V ¥ {s, t})fij(a, b) = [a ≠ b]

060

3

5101

分散制約最適化問題
分散制約最適化問題 (Distributed COP, DCOP)
入力：COPの入力(G, {Di}, {fij})– 各変数を管理するエージェントが存在– 隣接するエージェントとのみ通信可能
目的：エージェントが協力してコストの低い割当を求める• 通信量を抑える• 計算時間を抑える

f23

1

34
f45

2

f24

56

分散制約最適化問題の重要性• 様々なマルチエージェントシステムをモデル化可能– エージェントが協調して動作– 会議日程調整問題• 分散最適化が必要な状況– 入力が巨大で一台の計算機に載らない– 計算機等が物理的に分散している– 共有したくない情報がある（プライバシー）

本研究の貢献
分散最適化の課題
解の質

通信量・計算時間

乗算型重み更新法に基づいたアルゴリズムを二つ提案• 局所的な通信のみ利用• 実データ・人工データで、既存手法に対して– 最大2.75倍良い解が– より高速に得られた

提案アルゴリズムの概要

緩和線形計画問題（LP）

DCOP

緩和
コスト最小化ゲーム

乗算型重み更新法
LP解に収束

粗相関均衡点に収束

ラウンディング DCOPの ラウンディング
解
DMW-Game
DWM-LP後悔最小化後悔（リグレット）最小化問題
例：天気予測• 複数の天気予報士が毎日天気予報する• 次の日の天気から、各予報士の当たり外れが分かる• 最良の予報士と同程度天気を当てたい
乗算型重み更新法：後悔最小化を達成する手法• 予報士に信頼度（重み）を付与• 信頼度に応じた確率で予報士を選んで予報を真似る• 得られた結果から信頼度を更新する

乗算型重み更新法
乗算型重み更新法 (Multiplicative weight update method, MW)
入力：d個の戦略(＝予報士), 整数T(＝予報日数), 実数η
出力：{1, …., d}上の確率分布p1, …, pT（pt = t日目の予報士を選ぶ戦略）
w1 = (1, …, 1)
For t = 1 to T do
確率pta := wta / 𝄁𝄁wt𝄁𝄁1で戦略aを選択
コストct = (ct1, …, ctd)を観測
wt+1a := wta(1 - ηcta) (a ∈ {1,…,d})

乗算型重み更新法の理論保証[定理] T = 1/ε2, η = 1/√Tの時、任意の戦略aについて以下が成り立つ。

MWに従って予報士を選んだ時のコスト

予報士aを選択し続けた時のコスト
Diのサイズは定数と仮定[系] Tを十分大きく取れば、最良の戦略aに対するコストの差を任意に小さく出来る。

提案アルゴリズムのアイデア• エージェントiはfi := Σij∈Efijを最小化したい• エージェントiは戦略の分布μiを保持– 各隣接エージェントjから戦略分布μjを受け取る– 自分が戦略a ∈ Diを選択した時のコストを計算– MWによって、自分の戦略分布μiを更新• コストの定義により解の収束先が変わる提案アルゴリズムの概要

緩和線形計画問題（LP）

DCOP

緩和コスト最小化ゲーム

乗算型重み更新法
LP解に収束

粗相関均衡点に収束

ラウンディング DCOPの ラウンディング
解DMW-Game
DWM-LPDMW-LP: LP緩和
COPを線形計画問題 (LP) に緩和
mins.t. (i) μiはDi上の確率分布(ii) μij は Di × Dj上の確率分布(iii) μijのDiにおける周辺分布はμiに一致

241

635

DMW-LP: コスト計算
エージェントiの各ステップでの動作
各隣接エージェントjから分布μjを受け取る{μj}を固定し、fiをμiの関数とみた時の(劣)勾配を計算
勾配をコストとしてMWによりμiを更新する

241635DMW-LP: 理論保証
[定理]{μi}: DMW-LPがT = 1/ε2ステップ後に出力する分布{μ*i}: LP解以下が成り立つ。

DMW-LPから得られる解LP解Diのサイズは定数と仮定[系] Tが十分大きいと、LP解との差が任意に小さくなる

提案アルゴリズムの概要

緩和線形計画問題（LP）

DCOP

緩和
コスト最小化ゲーム

乗算型重み更新法
LP解に収束

粗相関均衡点に収束

ラウンディング DCOPの ラウンディング
解DMW-Game
DWM-LPDMW-Game: コスト最小化ゲーム••••

エージェントiはfi := Σij∈Efijを最小化したい
各エージェントは周りを見て自分の戦略を変化させる
均衡点は良い解に違いない ⇒ どの均衡点に注目する？
粗相関均衡！
粗相関均衡

より計算が簡単

相関均衡

多項式時間で計算可能

混合ナッシュ均衡

存在するが計算困難

純粋ナッシュ均衡

存在するとは限らない

DMW-Game: コスト計算
エージェントiの各ステップでの動作
各隣接エージェントjから分布μjを受け取る{μj}を固定した時の、戦略a ∈ Diのコストcaを計算{ca}をコストとしてMWによりμiを更新
出力μ = (1/T)Σt μt1×…×μtn (μti: tステップ目の分布μi)f23v1v3

f24v4
f45v2v5v6

DMW-Game: 理論保証
μ: DMW-GameがT = 1/ε2ステップ後に出力する分布
任意のi ∈ Vとc ∈ Diについて以下が成り立つ。

DMW-Gameから得られる解

粗相関均衡
Diのサイズは定数と仮定

Tが十分大きいと、粗相関均衡との差が任意に小さくなるラウンディング
確率分布μを割当φに丸める
DMW-LP• 多数決: 一番確率の大きい要素を使う• Distributed Stochastic Algorithm (DSA) 風– 変数の値を少しずつ決める– 既に値の決まっている隣接変数で条件付けした分布からサンプル
DMW-Game• 多数決• 多数決＋リスタート– 早く収束した変数を固定し、それ以外の変数の重みを初期化して再度実行実験設定
計算環境: Ubuntu, Intel Core-i7 3770@3.4GHz, メモリ4GB比較対象••••

Maxsum (Messeage-Passing)
DeQEDm, DeQEDa (Lagrange Duality)
DSA
MGM (Graphical-Game)

評価項目• 解の質 = 得られた解のコスト / LPにより得られた下界• 模擬実行時間

実験結果

数msで計算可能！

まとめ
乗算型重み更新法に基づく解法を二つ提案• DMW-LP: 線形計画問題の最適解に収束• DMW-Game: コスト最小化ゲームの粗相関均衡点に収束
提案手法の利点• 局所的な通信のみで動作• DMW-Game: 効率的に良質な解が得られる• DMW-LP: 下界が得られる課題• “堅い”制約，大域的な制約に対応