---
title: 【DL輪読会】Pruning as a Game: Equilibrium-Driven Sparsification of Neural Networks
tags: 
author: [Deep Learning JP](https://convert.docswell.com/user/DeepLearning2023)
site: [Docswell](https://www.docswell.com/)
thumbnail: https://bcdn.docswell.com/page/GEWZ58LWE2.jpg?width=480
description: 【DL輪読会】Pruning as a Game: Equilibrium-Driven Sparsification of Neural Networks by Deep Learning JP
published: January 08, 26
canonical: https://convert.docswell.com/s/DeepLearning2023/5N9Y4P-2026-01-09-130647
---
# Page. 1

![Page Image](https://bcdn.docswell.com/page/GEWZ58LWE2.jpg)

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/


# Page. 2

![Page Image](https://bcdn.docswell.com/page/47Z1N8M2J3.jpg)

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


# Page. 3

![Page Image](https://bcdn.docswell.com/page/YJ6L8P56EV.jpg)

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


# Page. 4

![Page Image](https://bcdn.docswell.com/page/GJ519KY574.jpg)

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


# Page. 5

![Page Image](https://bcdn.docswell.com/page/9E212WGGJR.jpg)

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


# Page. 6

![Page Image](https://bcdn.docswell.com/page/D7YZYLVGJM.jpg)

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


# Page. 7

![Page Image](https://bcdn.docswell.com/page/VEN3P4M8E8.jpg)

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


# Page. 8

![Page Image](https://bcdn.docswell.com/page/Y7993QNX73.jpg)

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


# Page. 9

![Page Image](https://bcdn.docswell.com/page/G789MGK9JD.jpg)

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


# Page. 10

![Page Image](https://bcdn.docswell.com/page/L7LW3GZMER.jpg)

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


# Page. 11

![Page Image](https://bcdn.docswell.com/page/4EM9DQV67W.jpg)

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


# Page. 12

![Page Image](https://bcdn.docswell.com/page/PERG482N79.jpg)

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


# Page. 13

![Page Image](https://bcdn.docswell.com/page/P7XX28D87X.jpg)

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


# Page. 14

![Page Image](https://bcdn.docswell.com/page/37KWMKXL7D.jpg)

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


# Page. 15

![Page Image](https://bcdn.docswell.com/page/LJ31YZ56E5.jpg)

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


# Page. 16

![Page Image](https://bcdn.docswell.com/page/8JDX5RDM7G.jpg)

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


# Page. 17

![Page Image](https://bcdn.docswell.com/page/VEPPGWXQE8.jpg)

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


# Page. 18

![Page Image](https://bcdn.docswell.com/page/27V268LP7Q.jpg)

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


# Page. 19

![Page Image](https://bcdn.docswell.com/page/5JGRN5XQ7L.jpg)

参考文献
[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


