未学習のニューラルネットに隠された「当たりくじ」

# はじめに
従来式のニューラルネットでは, 未学習のニューラルネットに対し, 各辺の重みを徐々に変化させることで学習を行います.

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/584592/d5de5c1a-24af-66ad-4d20-2eda61baf222.png" width=75%>

これに対し本記事では, **未学習のニューラルネットに対し, 重み更新なしで学習が可能**な画期的な一風変わった手法"edge-popup algorithm"[1]を紹介します.

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/584592/e02decbf-d712-6055-ca48-aa1a0388b917.png" width=75%>

元論文: <a href="https://arxiv.org/abs/1911.13299"> What's Hidden in a Randomly Weighted Neural Network?</a>
公式実装: <a href="https://github.com/allenai/hidden-networks/blob/master/simple_mnist_example.py">https://github.com/allenai/hidden-networks/blob/master/simple_mnist_example.py</a>

本記事ではedge-popup algorithmがどういった着想で編み出されていて, 何を行うアルゴリズムか, どの程度高い性能が出るか, どういった後続研究があるかを順を追って見ていきます.

# 宝くじ仮説とは
宝くじ仮説(The Lottery Ticket Hypothesis)[2]は, 本記事を読むにあたって押さえておいた方が良い前知識です. これについて簡単に説明します.

一般的に, 大きなニューラルネットほど比較的精度が出やすい一方で, 不要そうなedgeを取り除いてコンパクトにした方が精度が出る場合もあることが知られています. このことからニューラルネットの学習を宝くじになぞらえ「大規模なニューラルネットは部分構造をたくさん含むため, 当たりくじに相当するような良い部分ネットワークを引き当てやすく, 高精度を達成しやすいのではないか?」と言う仮説が立てられています.

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/584592/49569b85-a480-b903-4caf-dc114df1596e.png" width=95%>

つまり**学習済みのニューラルネットワークには, それ単独で同じ程度学習させても, 元のネットワークの性能に匹敵する部分ネットワーク(当たりくじ)が存在する**という仮説が宝くじ仮説と呼ばれているものであり, ニューラルネットの軽量化に関する分野では有名な仮説です.

# Edge-popup algorithm
当たりくじを見つけるべく着想された手法が本記事の主題"edge-popup algorithm"[1]です.

この手法では, 順伝搬時に各edgeに対し, 重みとは別にpopup scoreという値を付与します. これによって各辺の重要度をランク付けし, 上位k%を選出します.
例えば, 重要度が上位k=50%に入るedgeを選出する場合は以下のようになります.

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/584592/6312d35d-8f72-a484-5063-828d584511b8.png" width=85%>

選ばれなかった重みは0と等価として扱います. 後述する手順を通し各scoreは学習を通して更新されていくため, 一度上位k%に入選できなかったedgeが後になって入選し直すこともあります.

また, scoreは毎回更新される一方で, 重みは学習全体を通して初期値のまま一切変更しません. **未学習のネットワークを一切の重み更新なしで学習できる**点が本手法の画期的と言える点です.

# 逆伝搬時
逆伝搬時は勾配を各scoreに伝搬, scoreの値を更新する必要があります.

結論から述べると, $s_{ab}$をノード$a$からノード$b$へ向かうedgeのscoreとした時, 以下のように更新されます.

```math
\begin{align}

s_{ab} \leftarrow s_{ab} - \alpha \frac{\partial \mathcal{L}}{\partial I_{b}}w_{ab}Z_{a}

\end{align}
```

ただし$\mathcal{L}$は損失関数, $\alpha$は学習率であり, その他の変数は以下の図のようにおきます.

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/584592/fbc619d3-2c73-c955-50e6-0d179fcafcc2.png" width=100%>

## 勾配の導出
勾配は以下のようにして導出できます.

まず$s_{ab}$の更新式は, 損失$\mathcal{L}$を小さくしたいため以下のように表せます.
```math
\begin{align}

s_{ab} \leftarrow s_{ab} - \alpha \frac{\partial \mathcal{L}}{\partial s_{ab}} \tag{1}

\end{align}
```
このうち$\frac{\partial \mathcal{L}}{\partial s_{ab}}$が求めたい箇所です. この箇所は, ノードbへの入力の和$I_{b}$を用いて次のように変形できます.
```math
\begin{align}

\frac{\partial \mathcal{L}}{\partial s_{ab}} = \frac{\partial \mathcal{L}}{\partial I_{b}}\frac{\partial I_{b}}{\partial s_{ab}}

\end{align}
```
このうち右辺の左側$\frac{\partial \mathcal{L}}{\partial I_{b}}$は通常の誤差逆伝播で求まります. $\frac{\partial I_{b}}{\partial s_{ab}}$を後述の式変形で求めます.

ここで, scoreの仕組みを導入していない場合のニューラルネット, すなわち従来のニューラルネットを考えます. 
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/584592/8c1b9621-9318-16ef-ac2f-d3f389f1d0ba.png" width=100%>
ネットワークを上図のようにおくと$I_b$は以下のように表現できます.

```math
\begin{align}

I_b = \sum_{a^{\prime} \in \left\{ a_1, ..., a_n\right\}}w_{a^{\prime} b}Z_{a^{\prime}}

\end{align}
```

その上で, このネットワークにscoreの仕組みを導入することを考えます.
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/584592/04b633af-dd19-ac5b-04ce-7cf1ccdaaa8a.png" width=100%>
ここで, $s_{ab}$が上位k%に入選しているならば1を, そうでなければ0を出力する関数を$h(s_{ab})$とおきます. $h(s_{ab})$によって各edgeを格付けしているようなイメージです. この$h(s_{ab})$を用いると, scoreの仕組みを導入したネットワークにおいて, $I_b$は以下のように表現できます.

```math
\begin{align}

I_b = \sum_{a^{\prime} \in \left\{ a_1, ..., a_n\right\}}w_{a^{\prime}b}Z_{a^{\prime}}h(s_{a^{\prime}b})

\end{align}
```

以上から, 目的であった$\frac{\partial I_{b}}{\partial s_{ab}}$は以下のようになります.

```math
\begin{align}

\frac{\partial I_{b}}{\partial s_{ab}} &= \frac{\partial ( \sum_{a^{\prime} \in \left\{ a_1, ..., a_n\right\}}w_{a^{\prime} b}Z_{a^{\prime}}h(s_{a^{\prime} b}) ) }{\partial s_{ab}}

\end{align}
```

ここで, 関数$h(s_{ab})$は0もしくは1を返すだけの関数であるため, 傾きがほとんどの場合で0であり, そのままでは勾配を伝搬できません.

そこで, straight-through gradient estimator[7]を使って, 後ろから伝搬してきた誤差をそのまま流すだけにします. 具体的には$h$の傾きを$1$だと決めてしまいます.
これを用いると, 目的の箇所は以下のようにできます.

```math
\begin{align}

\frac{\partial I_{b}}{\partial s_{ab}} &= \frac{\partial ( \sum_{a^{\prime} \in \left\{ a_1, ..., a_n\right\}}w_{a^{\prime} b}Z_{a^{\prime} }h(s_{a^{\prime} b}) ) }{\partial s_{ab}} \\
&= w_{ab}Z_{a}\\

\end{align}
```

以上より
```math
\begin{align}

\frac{\partial \mathcal{L}}{\partial s_{ab}} &= \frac{\partial \mathcal{L}}{\partial I_{b}}\frac{\partial I_{b}}{\partial s_{ab}} \\
&= \frac{\partial \mathcal{L}}{\partial I_{b}}w_{ab}Z_{a} \\

\end{align}
```
と求めることができ, $s_{ab}$の更新式であった$(1)$に代入することで
```math
\begin{align}

s_{ab} \leftarrow s_{ab} - \alpha \frac{\partial \mathcal{L}}{\partial I_{b}}w_{ab}Z_{a}

\end{align}
```
が導出できます.

# 実験
edge-popup algorithmの元論文では以下の2点を調べるべく, データセットとしてCifer10やImageNetを用いて実験を行なっています.
1. 元のネットワークのうち何%を残すと良いか.
2. 元のネットワークはどの程度の大きさを持っていると良いか.  

また, ネットワークの初期値について, 以下のどちらの方が高い精度が出るかも検証しています.
* Kaiming Normal $N_k$
平均0, 分散$\sqrt{2/𝑛}$($n$は全層のノードの数)のガウス分布による初期化.
* Signed Kaiming Constant $U_k$
$-\sqrt{2/𝑛}, \sqrt{2/𝑛}$の2値からランダムに選出, 初期化.

実験に用いているモデルは
* 畳み込み2層からなるモデル「Conv2」
* 畳み込み4層からなるモデル「Conv4」
* 畳み込み6層からなるモデル「Conv6」
* 畳み込み8層からなるモデル「Conv8」

の4つで, 全てVGG16を参考にしたアーキテクチャとなっているようです.

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/584592/133b6b7d-46b7-4b57-b54a-9dc4f8a6d655.png" width=75%>

表の引用元: [1]

## ニューラルネットの深さに対する検証
まずは元のニューラルネットの深さがどの程度精度に影響を及ぼすか, 残す割合を10%, 30%, 50%, 70%, 90%とした場合の5パターンについての実験です.

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/584592/fb3b3686-e656-9d64-c762-407ef0e72a27.png" width=85%>

図の引用元: [1]

層が深いネットワークほど部分ネットワークを多く持つためか, 精度の出る構造が見つけやすい傾向が見て取れます. 

また, グラフの水色と赤色の場合において, k=50%に近いほど高精度を達成しやすいことがわかります. $n$本のedgeから$kn$本を選び出す場合を考えると, 選び方は$\_{n} C_{kn}$通りあり, これはk=50%の時最大となります. 選べる部分構造の数がこの時に最大となるため, 高精度が達成できているのではないかと元論文では議論しています.

## ニューラルネットの幅に対する検証
次に, 元のニューラルネットのchannel数が, どの程度精度に影響を及ぼすかを見ていきます.
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/584592/cd0d4a4f-77ba-3767-413f-3479766e2f6d.png" width=85%>

図の引用元: [1]

channel数が大きいネットワークほど, やはり部分構造を多く含むためか, 精度の出る部分ネットワークを見つけやすい傾向があることがわかります. 特にConv6に関しては50%選択した場合が, channel数を増やした際, 普通に学習した時の結果と遜色ないくらいの高精度を達成できています.

## さらなる実験
元論文では, edge-popup algorithmで見つけた部分構造に対して, さらに普通の学習を行った時の精度に関する検証も追加で行っています.

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/584592/22a6a578-c057-9bb9-90ea-5a4f8853f1b6.png" width=85%>

結果, ランダムに適当に探してきた部分構造に対し, 普通の学習をした場合と精度はあまり変わらなかったようです.

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/584592/1c4ead42-ae2c-6c1f-d6c7-f9934e4ea1b1.png" width=85%>

元論文ではこのことから, 本手法では宝くじ仮説「学習済みのニューラルネットワークには, それ単独で同じ程度学習させても, 元のネットワークの性能に匹敵する部分ネットワーク(当たりくじ)が存在する」を完全に説明できるわけではないとしています.

# 応用事例
ニューラルネットは各所で応用が進んでおり, 特に自動運転や工場の生産ラインでの検品などで利用する際はリアルタイムに, 瞬時に実行を行えるかが肝要とされています. しかしニューラルネットは一般に計算リソースを大量に必要とし, そのためにCPUやGPUなどでは実行時間が長すぎる, さらに消費電力や発熱の面で難があるなど, 実応用を妨げる要素が多く課題となっています.

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/584592/d15342f8-e3a4-2af9-67fb-e40d301d5b8f.png" width=85%>

画像引用元: [9]

こうした背景からCPUやGPUなどの汎用な演算装置ではなく, いっそのことニューラルネット専用の集積回路を作ってしまい実行速度を大幅に改善する研究が近年盛んです. その1つがedge-popup algorithmの論文から着想されたとされる, <a href="https://www.titech.ac.jp/news/2022/063171">ヒデナイト（Hiddenite）アーキテクチャ</a>[9]です. 

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/584592/316d32da-5139-6f98-3200-2ddc11cc4e85.png" width=85%>

画像引用元: [9]

未学習のニューラルネットは乱数で初期化されているため, 同じシード値さえあればいつでも再現できます. このため乱数生成器ごと集積回路にしてしまうことで, 重みを回路の外から読み込む必要を完全に0にしているようです. また, k=30%の場合が精度が高かったそうで, マスクがスパースなことを利用し高効率なデータ転送を実現しています. 他にも様々な工夫を施すことで, 演算速度を従来よりも大きく改善しているようです.

# 余談: 強い宝くじ仮説
Edge-popup algorithmではランダム初期化されたニューラルネットから, 重み更新なしに宝くじを探し当てることができます.

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/584592/49569b85-a480-b903-4caf-dc114df1596e.png" width=95%>

このことからEdge-popup algorithmは, 宝くじ仮説から派生した別の仮説**The strong Lottery Ticket Hypothesis**を実証できている[11]とされており, このことが後続の研究へと着想を与えているようです.

あえて訳すとすれば**強い宝くじ仮説**でしょうか.

これは「十分に大きく, ランダムに初期化されたニューラルネットにおいて, 学習せずとも何らかの目標ニューラルネットを近似できる部分構造が存在する.」[11]という仮説で, まさに上記の実験で実証されたものとなっています. 


# まとめ
本記事では, 当たりくじを探し当てる手法の1つ”edge-popup algorithm”を紹介しました.
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/584592/e02decbf-d712-6055-ca48-aa1a0388b917.png" width=75%>

本手法の重要な点:
* 従来手法と違い, 未学習のニューラルネットから, 重み更新なしで学習ができるのが肝.
* 含まれるくじの総数が多くなるほど精度が出しやすい.
* 注意点として, 宝くじ仮説に完全な説明をつけられている訳ではない.
    * しかし「強い宝くじ仮説」を実証したとされており, 後続研究へと着想が生かされている.

ニューラルネットの軽量化技術はこの他にも量子化, 枝刈りなど様々な手法が研究されており, スマホやマイコン上で動く機械学習モデルへの需要が今後高まることが予想されていることを考えると, これら軽量化技術への注目はますます高まると思われます.

本手法に関しては<a href="https://github.com/allenai/hidden-networks/blob/master/simple_mnist_example.py">論文の公式実装</a>が非常に読みやすいため, より詳細に知りたい方はこちらに目を通してみるのもおすすめします.

本記事の内容に関しては万全を期して作成しておりますが, 間違った点などがありましたらご指摘いただけると非常に助かります.

# 参考
[1]<a href="https://arxiv.org/abs/1911.13299"> What's Hidden in a Randomly Weighted Neural Network?</a>
[2]<a href="https://arxiv.org/abs/1803.03635"> The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks</a>
[3]<a href="https://qiita.com/YusukeKanai/items/9b7f6ba7472f782a5b3b"> [論文読み + α] 宝くじ仮説を試してみる</a>
[4]<a href="https://iblog.ridge-i.com/entry/2021/02/24/115105"> ニューラルネットワークのPruningの最新動向について</a>
[5]<a href="https://laboro.ai/activity/column/engineer/%E5%AE%9D%E3%81%8F%E3%81%98%E4%BB%AE%E8%AA%AC/"> ディープラーニングを軽量化「宝くじ仮説」について</a>
[6]<a href="https://github.com/allenai/hidden-networks/blob/master/simple_mnist_example.py"> hidden-networks 公式実装</a>
[7]<a href="https://arxiv.org/abs/1305.2982"> Estimating or Propagating Gradients Through Stochastic Neurons</a>
[8]<a href="https://bibo6.hatenablog.jp/entry/2022/02/02/063857"> 活性化関数と重みの初期値の関係</a>
[9]<a href="https://www.titech.ac.jp/news/2022/063171"> 隠れニューラルネットワーク理論を具現化したAIチップを世界で初めて開発</a>
[10]<a href="https://laboro.ai/activity/column/engineer/%E3%83%87%E3%82%A3%E3%83%BC%E3%83%97%E3%83%A9%E3%83%BC%E3%83%8B%E3%83%B3%E3%82%B0%E3%82%92%E8%BB%BD%E9%87%8F%E5%8C%96%E3%81%99%E3%82%8B%E3%83%A2%E3%83%87%E3%83%AB%E5%9C%A7%E7%B8%AE/"> ディープラーニングを軽量化する「モデル圧縮」３手法</a>
[11]<a href="https://arxiv.org/abs/2210.16589"> Strong Lottery Ticket Hypothesis with ε--perturbation</a>