【DL輪読会】Pruning as a Game: Equilibrium-Driven Sparsification of Neural Networks

DEEP LEARNING JP Pruning as a Game: Equilibrium-Driven Sparsification of Neural Networks [DL Papers] Presenter: Manato Yaguchi, Matsuo-Iwasawa lab, M2 http://deeplearning.jp/

• http://deeplearning.jp/

書誌情報 紹介論文  タイトル: Pruning as a Game: Equilibrium-Driven Sparsification of Neural Networks 出典: Arxiv , 2025/12  著者: Zubair Shah, Noaman Khan 概要  ニューラルネットワークの Pruning を、パラメータ群毎の参加度を戦略とした、連続な非協力ゲー ムとして定式化した  この定式化において、ナッシュ均衡で、余分なネットワークは削減され、スパース性が自然に現れる ことを示した ※画像は出典記載のないものは、本論文から引用 2

• https://www.arxiv.org/abs/2512.22106

Background：Pruning 画像：出典[1]  Neural NetworkのPruning とは、一旦学習により得たモデルに対して、再学習することなく モデルサイズや計算コストを削減する手法  削減手法としては、ノード毎に重要度の重みを割り振ったり[2]、正則化項を加えたりして[3]、 意図的にスパースにしている Question  そもそもスパース性はどこからくるのか？もっと自然にスパース性が現れないのか？ => ゲーム理論的に解釈可能 (本論文の主張) 3

問題設定  𝑙 はサンプル毎のLoss  𝜃 をpruning を行う単位 𝜃𝑖 (ex, ニューロン/フィルタ/重みブロック)に分割  s𝑖 を各単位の参加度 とし、初期は全参加(𝑠𝑖 = 1) とする. 6

ゲーム理論としての定式化  各 𝜃𝑖 の 参加度 𝑠𝑖 についての最適化をゲーム理論の枠組みで考える.  各 player の 効用 を 以下で定める.  𝑠−𝑖 は, 𝑠𝑖 を除くすべてのplayer の戦略を表す.  Bは, Benefit Term で, Cは Cost Term とする.  Benefit Term と Cost Term は以下のように自然に与えることができる. 𝜕𝐿  Bは、𝜕𝑠 の1次近似と、 を使えば導出できる. 7

ナッシュ均衡  𝑠 が以下の式を満たすとき, ナッシュ均衡であると定義する  自分以外のすべての戦略が固定され、自分だけ戦略を変えるとき、現在の戦略より得られる効用が良くなる ことはない  上の定式化において、(ゲーム理論的な意味で) Pruning が起こるのは、以下の式を満たす とき  つまり、s_i を 0にするのが、一番効用が得られる という状況 => これはどういう状況か？ 次ページで簡単な理論解析 8

スパースになる条件に関する理論解析  効用関数 U, Benefit Term B, Cost Term C の定義より, U の1次の平衡条件は、以 下のようになる.  𝑠𝑖 > 0 において、解は以下の式を満たす  分子が0 or 負なら, 最適な 𝑠𝑖 は 0になる. すなわち、𝜃𝑖 の寄与はない状態が最善になる. 解釈1：𝜃𝑖 がLossに与える影響の大きさ (どれくらい必要かの指標) 解釈2：𝜃𝑖 が他の重み𝜃j とどれくらい競合するか (どれくらい不要かの指標) 9

新たなPruning アルゴリズムの提案  ネットワークのパラメータ 𝜃 と, 参加度 s を交互に更新するアルゴリズムを提案 => Purning をシンプルな形で表現可能  パラメータ更新:  参加度の更新:  Utility 関数は、前ページで述べた通り 10

実験  2層の隠れ層を持つネットワーク上で、MNISTを使ったPruningの実験  Hidden layer1: 512 neurons, Hidden layer2: 256 neurons  ニューロンの数の分(つまり、768個)のグループを用意し、各グループの参加度の学習をパラ メータの学習と交互に行う 11

実験結果  Beta をあげるとスパース性が 上がる. (青->オレンジ)  Penalty 項をあげるほど、グ ループの参加度の平均が0に 近づく(左下図). 12

まとめ まとめ  ニューラルネットワークの Pruning について、ゲーム理論的な定式化を与えた.  特に、パラメータ群が参加度を戦略として選ぶ非協力ゲームのナッシュ均衡として、スパース性 が自然に現れることを表した. 感想  パラメータ群の分け方に関しては、特に言及していない 余談  Pruning の話としては、非協力ゲームのナッシュ均衡という枠組みでスパース性を議論したの はこの論文の貢献である  一方で、(論文中では触れられていないものの) 似たような話として、PCA を ナッシュ均衡とし て捉える論文があるので、一部を抜粋して紹介する. 13

書誌情報 紹介論文  タイトル: EIGENGAME: PCA AS A NASH EQUILIBRIUM  出典: ICLR2021  著者: Ian Gemp, Brian McWilliams, Claire Vernade & Thore Graepel 概要  主成分分析(PCA)を非協力ゲームとして定式化  特に、PCAを、データの分散が最大になる(複数の)方向(ベクトル)を探すものだと考えたとき、各player を固有 ベクトルとした非協力ゲームとみなせることを示した ※画像は出典記載のないものは、本論文から引用 14

PCA とは  PCAは、直感的には、分散が大きい方向 のベクトルを順に見つけていく手法 もう少し数学的に説明すると…  𝑋 ∈ ℝ𝑛×𝑑 を d次元のデータセットとしたと き、対称行列 M = 𝑋 𝑇 𝑋 の固有ベクトル を求める操作 を考える. Practical には、  データの解釈(disentangle), 圧縮 など に使える手法 1次元目を決める際に、2次元目には依存しないというのは重要 画像出典：https://medium.com/@raghavan99o/principal-componentanalysis-pca-explained-and-implemented-eeab7cb73b72 15

• https://medium.com/@raghavan99o/principal-component-

PCAをゲーム理論的に捉える  対称行列 M = 𝑋 𝑇 𝑋 の固有ベクトルを求める問題は、以下のM を対角化する問題と捉えら れる.  Mは対称行列なので、Vは正規直交行列として表すことにする.  さらに、上の問題は、𝑉෠ を真の固有ベクトルの推定量, スの巡回性から、以下の問題を解くことに帰着される. としたとき、トレー Q. これは、PCAで射影する空間がデータの次元と同じ場合の話。では, k < d の場合は？ 16

PCAをゲーム理論的に捉える  素朴には、k<dの時も、k=dの時と同様に、以下の式を使いたいが…  これだと (i,j)の全ペアを対称に罰することになるが、1次元目の固有ベクトルは、m (> 1)次元目の固有ベ クトルの影響を受けたくない  代わりに、以下の形で固有ベクトルを決めていく. (一般化Gram-Schmidt)  V_1 が決まると、v_2が決まり、… というDAGの形をとる 17

PCAをゲーム理論的に捉える  論文の主張の一つは、以下の定理を示したこと. (証明を含めた細かい話は割愛) 𝑋 𝑇 𝑋 の Top-k の固有値がすべて異なる値を持ち、かつすべて正であるとする. この時、top-k の固有ベクトルは、 を効用関数とする非協力ゲームにおける, 一意の 強ナッシュ均衡となる. では, Pruning を ナッシュ均衡として捉えた話と、PCAをナッシュ均衡として捉えた話は、何が 同じで、何が違うのか？ 18

Pruning as a Game / PCA as Nash の比較 Pruning as a Game PCA as Nash Player パラメータ群 (MNIST の例だと 隠れ ニューロン) 第i主成分（近似固有ベクトル 𝑣ෝ𝑖 ) 戦略 参加率 𝑠𝑖 ∈ [0, 1] 相互作用 他グループとの競合コスト (相関項 σ𝑗≠𝑖 𝑠𝑗 < 𝜃𝑖 , 𝜃𝑗 >) など 親（j<i）との“重なり”を罰する項 情報フロー 基本は全体損失や相関を通じた結 合 親→子の DAG でメッセージパッシング 𝑣ෝ𝑖 ∈ 𝑆 𝑑−1  どちらも、Nash 均衡を学習における目標としている  どちらも冗長性を相互作用で表現し、必要なものだけ残す (Pruning は、他のパラメータ群との重なり をコストに入れ、PCAは親方向との重なりをコストに入れる) 19

Pruning as a Game / PCA as Nash の比較 (違い) 違い 1(厳密さ)  PCA as Nash は「PCAという明確な数学解」をそのままNashとして実現する設計で、定理 として 唯一の strict Nash を示す (厳密)  論文中でも触れているが、DAGの構造をとることにより、解の収束性を示しやすくしている  Pruning の論文は、ニューラルネットがスパースになることに対する説明原理を与えているに過 ぎない 違い2 (相互作用構造)  Pruning の方は、パラメータ群の設計に関して、ほとんど何も言っていない。PCAの方は、 DAGの構造をとっている.  Pruning においても、DAG構造を入れたりして、どの部分に競争関係を仮定するかで結果が変わることを言 えたら良さそう 違い3 (冗長性の測り方が異なる)  Pruning の方は、パラメータ群に対して測り、PCAは、データの射影(𝑋𝑣𝑖 )に対して測る. 20

参考文献 [1] T. Chen, Y. Sui, and X. Chen, et al. A unified lottery ticket hypothesis for graph neural networks. In ICML, 2021 [2] M. C. Mozer and P. Smolensky. Using relevance to reduce network size automatically. Connection Science, 1(1):3–16, 1989. [3] S. Hanson and L. Pratt. Comparing biases for minimal network construction with backpropagation. In NIPS, vol. 1, 1988. 21