toaruharunohi’s diary

機械学習系会議の論文/資料の要約

要約: The Mechanics of n-Player Differentiable Games

http://proceedings.mlr.press/v80/balduzzi18a/balduzzi18a.pdf

ICML2018の準Best Paperの論文

n人のプレイヤーがそれぞれのモデルパラメータをそれぞれについて設定された目的関数について学習していく際のパラメータの挙動について論じている

また、Nash均衡に行き着くための新たな学習アルゴリズムを提案し、それを2-player gameの一種であるGANの学習に応用している

問題設定

Gameは、次の二つによって定義されるとする。

(1)n人のプレイヤー。

(2)n人のプレイヤーそれぞれについて設定された二回微分可能な損失関数。

それぞれのプレイヤーはモデルパラメータ w_iの調整を行なって、それぞれに対して設定された損失関数をなるべく小さくすることを目指す。

  • これになぞらえると、GAN学習問題は「プレイヤーが二人いて、一方が識別器のパラメータを調整して識別器の損失を、もう一方が生成器のパラメータを調整することで識別器の損失に負の定数をかけたものを小さくすることを目指す」ゲームであると説明できる。

なおこの論文ではそれぞれのプレイヤーの損失関数をそれぞれのプレイヤーが制御できるパラメータで微分したものを次の記号で表現する:

f:id:toaruharunohi:20180926224406p:plain

ここで、 l_iはi番目のプレイヤーに対して設定された損失関数、 w_iはi番目のプレイヤーが制御できるモデルパラメータである。

また、以降ではi番目のプレイヤー以外のパラメータはまとめて w_{-i}と表記する。

局所Nash均衡

パラメータ w_iの近傍を U_iと定義する。 局所Nash均衡とはN個のパラメータw_1,..., w_Nが全て次の条件を満たす場合のことである:

[tex: l_i(\hat{w_i}, w{-i}) \geq l_i(w_i, w{-i}) for \hat{w_i} \in U_i ]

Potential GameとHamiltonian Game

GameのHessianを次のように定義する (通常のHessianとは微妙に異なるので注意):

f:id:toaruharunohi:20180926224409p:plain

もしくは

f:id:toaruharunohi:20180926224412p:plain

Hessianは通常の行列と同様に次のように対称行列S (S=ST)と交代行列A (A=-AT)の和に分解できる:

f:id:toaruharunohi:20180926224415p:plain

Aが零行列のときは特にPotential Gameと呼ばれるものであり、過去によく研究されてきた。 一方でSが零行列のときはあまり研究がされてこなかった。この論文ではSが零行列のときをHamiltonian Gameと呼ぶこととしている。

Potential Game

Potential Gameとは任意のtex: w_i, w'i, w''iに対して次の条件を満たすような関数φとN個の正の数 \alpha_1,...\alpha_N (この論文の中では \alpha_i=1と考えて良い)が存在するGameのことである:

f:id:toaruharunohi:20180926224417p:plain

これは次と等価であることが示されている:

f:id:toaruharunohi:20180926224420p:plain

Potential Gameの例としては、N人のプレイヤーが同じモデルのパラメータを同じ目的関数についてそれぞれ独立して最適化する場合などが挙げられる(N人が別々に識別器を学習させる場合など)。

Potential Gameではξを用いた勾配降下法によってφの局所最適解にたどり着けることが容易に示せる。

Hamiltonian Game

Hamiltonian Gameの例としては以下のものが挙げられる。

f:id:toaruharunohi:20180926224424p:plain

Hamiltonian GameはPotential Gameとはかなり性質の異なる概念である。 Potential Gameの場合と同様にプレイヤーにξを用いた勾配降下法によってパラメータを最適化させたいところだが、そうすると以下の図の左ようにくるくる回ってしまう場合もあり、局所Nash均衡に行き着くと限らない。

f:id:toaruharunohi:20180926224430p:plain

次の定理では次に定義するHamiltonian H(w) (HessianのHと紛らわしいが異なるので注意) について勾配降下法を適用することで局所Nash均衡にいきつけるということを示唆している。

f:id:toaruharunohi:20180926224427p:plain

上の図の右側に示されるようにH(w)についての勾配を用いることで局所Nash均衡に向かって正しくパラメータ更新ができるようになる。

一般的な場合において局所Nash均衡を得るためのアルゴリズム

ここまでで、Potential Gameではξを用いた勾配降下法によって、Hamiltonian GameではHamiltonian H(w)について勾配降下法を適用することによってそれぞれ局所Nash均衡に辿りつけることがわかった。

次にPotential GameでもHamiltonian Gameでもない一般的なGameにおいて局所Nash均衡にたどりつけるようなアルゴリズムを検討していく。 具体的には、勾配ξを少し修正して用いることで安定した固定点にパラメータが向かっていくように仕向けることを考える。

  • 勾配ξを修正する手法としてConsensus Optimizationというものがすでに提案されているが、これは安定した固定点に行き着く保証がない。

この論文では、次に示す方法で勾配ξを修正することを提案している:

f:id:toaruharunohi:20180926224440p:plain

これをSymplectic Gradient Adjustment (SGA)と命名している。 Smyplecticという単語はSymplectic geometryという概念に起因している

この更新式は、次の三つの望ましい条件を満たしているところが理想的である: 

f:id:toaruharunohi:20180926224443p:plain 

(ただしD3はλが正であるときに成り立つ)

なお、上記のアルゴリズムはλの選び方に余地がある。仮にλの符号を次の条件が満たされるように選んだとする:

f:id:toaruharunohi:20180926224449p:plain

この時、更に望ましい2つの条件が満たされるような更新式になる:

f:id:toaruharunohi:20180926224446p:plain

最終的なアルゴリズムは以下の通りである: f:id:toaruharunohi:20180926224437p:plain

合成データでのSGAとGradient Descentの比較

以下の損失関数を元にした2プレイヤーゲームを考える。プレイヤー1はxを調整して l_1を、プレイヤー2はyを調整して l_2を下げることを目指す: f:id:toaruharunohi:20180926224456p:plain

この時にGradient Descentを使った場合(ξをそのままパラメータ更新に使った場合)とSGAを使った場合を比較した図が以下の通りである:

f:id:toaruharunohi:20180926224452p:plain

GAN学習の実験

16種のGaussianからなるGMMをGANで近似する実験を行なっている。以下の図がその結果である:

f:id:toaruharunohi:20180926224433p:plain

通常のGradient DescentだとMode Collapseが発生しているが、提案法だと16種のMode全てをある程度捉えることに成功している。