"EigenGame: PCA as a Nash Equilibrium" の紹介

導入

EdTechLab で機械学習エンジニアをしています山城です。私の所属する EdTechLab では、 AI ビジネス英語スピーキングテスト「PROGOS(R)」のモデル開発と運用を中心に、その他データ分析やR&Dも行っています。

さて、機械学習では特徴量の次元削減に使われる手法として PCA (principal component analysis, 主成分分析) があります。EdTechLab でもモデル開発で使ったりしており、馴染みのある手法であります。そんな折、この PCA がゲーム理論におけるゲームとみなせるという、 ICLR2021 に採択された論文 EigenGame: PCA as a Nash Equilibrium openreview.net を見つけました。PCA も Nash 均衡もよく聞く概念ではありますが、この二つを並べて論じているのは初めて見ました。普段使っている手法がどのようにゲーム理論の観点から捉え直せるか、興味を引いたので論文を読み進めてみました。この記事では PCA をゲームとして定式化できることを示した論文の定理2.1 の紹介をします。

まずゲーム理論と PCA についておさらいし、その後定理の主張を説明していきます（ゲーム理論も PCA もご存知の方は最初の2節は飛ばしていただいても問題ないです）。

ゲーム理論の用語の紹介

論文の主張を理解するためにゲームを定式化し、Nash 均衡の概念を導入していきますが、その前によくある例を紹介します。

例. 囚人のジレンマ

[wiki]参照

二人の囚人 A, B がいて、次の前提と条件で司法取引を持ちかけられている。

（前提1）互いに相談はできないとする
（前提2）囚人はどちらも自分ができるだけ短い刑期で済ませたいと考えている
（条件1）片方が自白すれば、自白した方は釈放、黙秘した方は懲役10年
（条件2）2人とも黙秘すれば、2人とも懲役2年
（条件3）2人とも自白すれば、2人とも懲役5年

各囚人は自白と黙秘のどちらを選択をするべきか、というのが問題です。どちらの囚人も自分の利益の最大化（刑期の最小化）を目的としている場合、どちらの囚人も上記の前提のため、意思決定のプロセスは

相手が自白した場合、自分が黙秘すれば懲役10年となるため、それよりも短い懲役5年で済む自白を選択しよう
相手が黙秘した場合、自分が自白すれば釈放されるので、自白を選択しよう

となるため、結果的にどちらも自白し、どちらも懲役5年となります*1。。さて、上記の問題は相手のとる戦略（自白or黙秘）を考慮しつつ、自分の利益を最大化（懲役の最小化）するように自身の戦略を選択する意思決定問題と捉えることができます。これをゲームとして定式化していきます。

ゲームの定式化

さっそくゲームを定式化します（[lec2] を参照）。

(定義) ゲームとは３つ組み $\displaystyle{ (I, S _ {i (i \in I)}, U _ {i (i \in I)}) }$ のことを指す。ここで各記号はそれぞれ

プレイヤーの集合 $\displaystyle{ I={1, 2, ..., k } }$
各プレイヤーのとれるアクションの有限集合 $\displaystyle{ S _ i（i \in I） }$
各プレイヤーの効用関数 $\displaystyle{ u _ i: S \to \mathbb{R} }$ ここで $\displaystyle{ S := \prod _ {i \in I} S _ i }$

と定めれらます。これは各プレイヤーがおのおの自分のアクションを指定したときに $\displaystyle{ S }$ の元 $\displaystyle{ s }$ が一つ定まり、それに応じて、各プレイヤーの効用関数の値 $\displaystyle{ u _ i(s) }$ （i.e. 自分の利益）が定まるということを表します。

続いて Nash 均衡の概念を導入します。

(定義) 　 $\displaystyle{S}$ の元をストラテジープロファイルと呼ぶ。

ここで便宜上の記号を導入しておきます。 $\displaystyle{S _ i}$ の元を $\displaystyle{s _ i}$ と表すことにして $\displaystyle{s _ {-i}}$ で $\displaystyle{\prod _ {i \neq j} S _ j}$ の元を表すことにする。

Nash 均衡とは言ってしまえば、全てのプレイヤーに対して、自分だけアクションを変えると必ず自身が損をする状態が成立していることを指します。

(定義) 　Nash 均衡とは、任意のプレイヤー $\displaystyle{i}$ に対して

$\displaystyle{ u_i (s^*_{i} , s^*_{-i}) ≥ u_i(s_i, s^*_{-i}), \quad s_i \in {}^{\forall}\!S_i }$

となるストラテジープロファイル $\displaystyle{ s^ * = (s^ * _ {i}, s^ * _ {-i}) \in S }$ のことを指す。

さらに強い条件として上の等式を満たす $\displaystyle{ s^ * }$ が唯一である場合は $\displaystyle{ s^ * }$ を strict Nash 均衡と呼ぶ。

先程の囚人のジレンマを上の定式化に当てはめてみると、

プレイヤー $\displaystyle{ I = \{A, B\} }$
アクション $\displaystyle{ S _ A = S _ B = \{ \text{自白}、\text{黙秘} \} }$
各プレイヤーの効用関数は次のようになる ( $\displaystyle{ x _ A, x _ B }$ は各囚人の取る選択を表す):

$\displaystyle{ \begin{align*} (x_A, x_B) = (\text{自白}, \text{自白})\text{ のとき}& \quad u_A(x_A, x_B) = u_B(x_A, x_B) = 5　\\ (x_A, x_B) = (\text{自白}, \text{黙秘})\text{ のとき}& \quad u_A(x_A, x_B)=0, u_B(x_A, x_B) = 10 \\ (x_A, x_B) = (\text{黙秘}, \text{自白})\text{ のとき}& \quad u_A(x_A, x_B)=10, u_B(x_A, x_B) = 0 \\ (x_A, x_B) = (\text{黙秘}, \text{黙秘})\text{ のとき}& \quad u_A(x_A, x_B)=u_B(x_A, x_B) = 2\end{align*} }$

となります。

このときストラテジープロファイル $\displaystyle{ (\text{自白}, \text{自白}) }$ が Nash 均衡となっており、さらにこれが strict Nash 均衡でもあることがわかります。

　以上の定式化により、各プレイヤーは他のプレイヤーの選択の結果の影響を受けつつ、自身の利益が最大となるように自身の行動を選択するという意思決定問題がゲームとして定式化され、Nash 均衡という概念が導入されました。

少し話はそれますが、Nash 均衡に関しては次の定理が知られています。

(Nash 均衡の存在定理 [lec5])

（上記のような）有限型のゲームにおいて、mixed strategy *2 については必ず Nash 均衡が存在する.

今回の論文で扱うアクションの数は有限ではない無限型のゲームだが、無限型のゲームについてはある条件を満たせば、（上で定義した pure な意味での） Nash 均衡が必ず存在することが示せます（こちらも[lec5]を参照）。

PCA のおさらい

[小西] を参照

PCA とはデータが $\displaystyle{ d }$ 個の変数からなる $\displaystyle{ n }$ 個のサンプルが与えられたときに、標本分散を最大化させる座標軸を逐次的に決めていくプロセスのことです。

　もう少し詳しくプロセスを説明します。 $\displaystyle{d}$ 個の変数 $\displaystyle{ (X _ 1, X _ 2, ..., X _ d) }$ からなる $\displaystyle{ n }$ 個のサンプルデータが与えられているとします:

$\displaystyle{ \begin{align*}x_1 &= (x_{11}, ..., x_{d1}),\\ x_2 &= (x_{12}, ..., x_{d2}), \\ ... \\ x_n &= (x_{1n}, ..., x_{n1}).\end{align*} }$

このとき各変数 $\displaystyle{ X _ i }$ の標本分散は $\displaystyle{ \frac{1}{n} \sum _ j^ n (x _ {ij} - \bar{x} _ i)^ 2 }$ で与えられる（ $\displaystyle{ \bar{x} _ i }$ は $\displaystyle{ X _ i }$ の標本平均）。いま各変数の一次結合による変換

$\displaystyle{ Y := v_1X_1 + \cdots + v_dX_d }$

によって得られる新たな変数 $\displaystyle{ Y }$ に対する標本分散を最大化させる $\displaystyle{ \boldsymbol{v} = (v _ 1, ..., v _ d)^ {\top} }$ を求めることを考えます。このとき $\displaystyle{ Y }$ に関する標本分散は標本平均を $\displaystyle{ \bar{y} }$ とすると

$\displaystyle{ \begin{align*} \frac{1}{n}\sum_i^n (y_i - \bar{y})^2 &= \frac{1}{n}\sum_i^n \{\sum_j^d v_j(x_{ij} - \bar{x}_j)\}^2 \\ &= \frac{1}{n}\sum_i^n (\check{\boldsymbol{x}}_i \boldsymbol{v})(\check{\boldsymbol{x}}_i \boldsymbol{v})\ \quad \bigl (\check{\boldsymbol{x}}_i := (x_{i1} - \bar{x}_1, ..., x_{id} - \bar{x}_d)\bigr) \\ &=\frac{1}{n}\sum_i^n \boldsymbol{v}^{\top}\check{\boldsymbol{x}}_i^{\top}\check{\boldsymbol{x}}_i \boldsymbol{v} \\ &= \boldsymbol{v}^{\top}M \boldsymbol{v} \quad \bigl (M := \frac{1}{n}\sum_i^n \check{\boldsymbol{x}}_i^{\top}\check{\boldsymbol{x}}_i \bigr) \end{align*} }$

と変形できます。ここで $\displaystyle{ M }$ は $\displaystyle{ X }$ の標本分散共分散行列となっています。さらに求める $\displaystyle{ \boldsymbol{v} }$ には制限条件としてノルムが1 *3であることを課す。これにより標本分散を最大化させる $\displaystyle{ \boldsymbol{v} }$ を求める問題は最適化問題

$\displaystyle{ \begin{align*} &max \quad v^T M v \\ &subject \, to \quad v^T v = 1 \end{align*} }$

の解として定式化される。この最適化問題はラグランジュの未定乗数法を使うことで、固有値問題

$\displaystyle{ Mv = \lambda v }$

に帰着される。この固有値問題を解き、得られる固有値の中で最大のものを選ぶ（実はそれが標本分散となっている）、その固有ベクトルを第1主成分と呼ぶ（それを $\displaystyle{ \boldsymbol{v _ 1} }$ とおく）。第1主成分を求めた後、今度は2番目に大きい標本分散が得られる $\displaystyle{ \boldsymbol{v} }$ を求めていく。2番目に求める $\displaystyle{ \boldsymbol{v} }$ には標本分散を最大にする条件に加えて第1主成分 $\displaystyle{ \boldsymbol{v _ 1} }$ に対する直交条件*4が追加される。再度上のプロセスを繰り返せば2番目に大きい標本分散を求める問題は結局

$\displaystyle{ \begin{align*} &max \quad v^T M v \\ &subject \, to \quad v^T v = 1, v^Tv_1 = 0 \end{align*} }$

として定式化されます。こちらも同様にラグランジュの未定乗数法で固有値問題に落とし込めます。同様にそこで得られた固有ベクトルを第2主成分と呼びます。以降の第 $\displaystyle{ i }$ 主成分 ( $\displaystyle{ i=3, 4, ..., d }$ ) も同様にして求められます。以上が PCA のプロセスの概要になります*5。

PCA では求めた主成分のうち、第 $\displaystyle{ k }$ 主成分( $\displaystyle{ k \lt d }$ )までを用いて、元のデータを線形変換

$\displaystyle{ XV_k \quad \bigr(V_k := (\boldsymbol{v_1}, \boldsymbol{v_2}, ...,\boldsymbol{v_k})\bigl) }$

を行うことで（ $\displaystyle{ d }$ 次元から $\displaystyle{ k }$ 次元への）次元削減を実現できます。

論文の定理2.1 の主張

　ここまででようやく定理の主張を理解する準備が整ったので早速説明していきます。まず論文の定理2.1 の主張を述べておきます。 $\displaystyle{ X }$ を $\displaystyle{ n \times d }$ 行列として、 $\displaystyle{ 0 \lt k \le d }$ とする。

定理2.1

$\displaystyle{ M:= X^ TX }$ *6の top- $\displaystyle{ k }$ の固有ベクトルは正かつ異なるとする*7。このとき、これらベクトルは各 $\displaystyle{ i \in {1, 2, ..., k} }$ に対して、

$\displaystyle{ \max _{\hat{v}_i^{\top} \hat{v}_{i}=1} \left\{ u_{i}\left(\hat{v}_{i} \mid \hat{v}_{j \lt i}\right) := \hat{v}_i^{\top} M \hat{v}_{i} - \sum_{ j \lt i } \frac{\left(\hat{v}_i^{\top} M \hat{v}_{j}\right)^{2}}{\hat{v}_j^{\top} M \hat{v}_{j}} = \left\|X \hat{v}_{i}\right\|^{2}-\sum_{ j \lt i } \frac{\left\langle X \hat{v}_{i}, X \hat{v}_{j}\right\rangle^{2}}{\left\langle X \hat{v}_{j}, X \hat{v}_{j}\right\rangle} \right\} }$

が定めるゲームの strict な Nash均衡となる。（主張ここまで）

ここで $\displaystyle{ M }$ の top- $\displaystyle{ k }$ の固有ベクトルとは $\displaystyle{ M }$ の固有値を大きい順に並べたとき、上位 $\displaystyle{ k }$ 個の固有値の固有ベクトルを指す。上で見たように、これは $\displaystyle{ X }$ の第1主成分から第 $\displaystyle{ k }$ 主成分のことを指しています。

　定理の主張はPCAを直交条件を制約条件とする $\displaystyle{ v^ TMv }$ を最大化する $\displaystyle{ v }$ を見つける最適化問題としてではなく、その直交条件という依存関係を目的関数の中に組み込むことで、関数 $\displaystyle{ u _ {i}\left(v _ {i} \mid v _ {j \lt i}\right) }$ をプレイヤー $\displaystyle{ i }$ の効用関数として捉えることができ、PCA をゲームとして再定式化することができることを述べている。

表にすると以下のような対応になる。

	PCA	囚人のジレンマ
プレイヤー	$\displaystyle{I = {1, 2, \dots, k }}$	$\displaystyle{I = {A, B }}$
アクション	$\displaystyle{ v \in S^{d} }$ ( $\displaystyle{ S^{d} }$ は $\displaystyle{ d }$ 次元単位球)	自白、黙秘
効用関数	$\displaystyle{ u _ {i}\left(\hat{v} _ {i} \mid \hat{v} _ {j \lt i}\right), i \in I }$	$\displaystyle{ u_A, u_B }$
Nash 均衡	$\displaystyle{ v_i (i \in I) }$ （ $\displaystyle{ v_i }$ は第 $\displaystyle{ i }$ 主成分）	$\displaystyle{ (x_A, x_B) = \left( \text{自白}、\text{自白} \right) }$

　上記の $\displaystyle{ u _ {i}\left(\hat{v} _ {i} \mid \hat{v} _ {j \lt i}\right) }$ の式はどのように得られたのかについて、論文に沿ってざっくり説明します*8。

上の式をPCA の再定式化として導くために論文では $\displaystyle{ d \times k }$ 行列 $\displaystyle{ \hat{V} }$ に対して $\displaystyle{ R(\hat{V}):= \hat{V}^ {\top} M \hat{V} }$ を導入しています。 $\displaystyle{ R(\hat{V}) }$ の値がもし $\displaystyle{ \hat{V} }$ が $\displaystyle{ X }$ の $\displaystyle{ k }$ 個の主成分（i.e. $\displaystyle{M}$ の固有ベクトル）からなる行列なら $\displaystyle{ R(\hat{V}) }$ は $\displaystyle{ k \times k }$ の対角行列となることに注意します。著者らは次の最適化問題を導入しました。

$\displaystyle{ \max _{\hat{V}^{\top} \hat{V}=I} \sum_{i} R_{i i}-\sum_{i \neq j} R_{i j}^{2}. }$

ここで $\displaystyle{ R _ {i j} }$ は行列 $\displaystyle{ R }$ の $\displaystyle{ (i, j) }$ 成分*9。この式のお気持ちを述べると、第一項

$\displaystyle{ \sum_{i} R_{i i} }$

に対角成分の最大化の役割をもたせ（ここは $\displaystyle{ u_i }$ の第一項に対応）、第二項

$\displaystyle{ - \sum_{i \neq j} R_{i j}^{2} }$

で非対角成分の絶対値の最小化の役割を持たせています。つまりこの最適化問題は $\displaystyle{ R }$ を対角化しつつ、その対角成分を最大化させる $\displaystyle{ V }$ を求める、すなわち $\displaystyle{ M }$ の固有値を最大にする固有ベクトルたちを求める問題と考えられます。一方でこの定式化で求まる固有ベクトルでは、主成分間の関係が満たす依存関係（直交条件）を織り込めておらず、PCA の再定式化にはなっていません。そこで $\displaystyle{ - \sum _ {i \neq j} R _ {i j}^ {2} }$ を上記の関数 $\displaystyle{ u _ {i}\left(\hat{v} _ {i} \mid \hat{v} _ {j \lt i}\right) }$ の第二項に置き直すことで、制約条件からは依存関係を外しつつ、依存関係を導入した上記の定理2.1の式でPCAの定式化をすることができました。

以上で定理2.1 の紹介終わる。

後記

この後、論文では定理2.1 の定式化に基づいて、主成分を求めるアルゴリズム（sequential なものとdecentralized なもの）の提案や、その収束性の証明、パフォーマンスの評価のための実験について解説しています。

著者らは論文の結論部分で、今回の定式化や、そこで提案されたアルゴリズムについて、連合学習やプライバシー保護学習や GAN への応用*10 、またはアルゴリズムの改良*11 などを今後の研究の方向性として挙げ、今回のようにゲームの観点から機械学習を見ることで、機械学習とゲーム理論両分野の双方向の発展につながることへの期待を述べています。

今回この論文を読み進めてみて、ゲーム理論や PCA の詳細を復習ができたことや、機械学習で馴染みの深い PCA がゲーム理論の言葉に置き換えられていくのは面白かったです。今回紹介できなかったアルゴリズム部分や続編の論文、ゲーム理論の実応用周りをもう少し調べてみたいと思いました。

最後に、詳細は確認していませんが ICLR 2021 には他にも Dropout をゲーム理論の観点から捉え直した別の論文も投稿されているので、気になる方は確認してみてください。