Neural Networkにおける宝くじ仮説について

Deep Learning論文紹介 Advent Calendar 2019の19日目の記事です。

## はじめに

年末といえば、宝くじ！、という方もおられるのではないでしょうか？
ちなみに今年の年末ジャンボ宝くじが1等7億円だそうで、AWS EC2のp3.8xlargeがおよそ3万円/日なので、宝くじ1等を当てれば、約63年、すなわち一生 p3.8xlarge 1台を立てて暮らす事ができます。

と、叶わないであろう夢はさておき、機械学習の分野で、"SotA"を達成する事はまだ見込みのある"夢"かもしれません。しかしこのSotA達成もまた、もしかしたら「宝くじ」のようかもしれない、というお話（研究）を今回は紹介したいと思います。

本稿のベースとなる論文は3本あります。
1本目は、MITコンピュータ科学・人工知能研究所のFrankleさんとCarbinさんの論文で、一時期話題になった論文です。[^0-0]さらには今年のICLRのbest paperを勝ち取っているので、解説に溢れているか、と思いきや、案外少なかったので、今回改めて取り上げてみました。

[^0-0]: [岡野原さんのツイート](https://twitter.com/hillbig/status/973850440528936961)で最初目にした気がします。その後もtwitterでごくたまに単語を見かけた程度で、後は[この記事](https://towardsdatascience.com/state-of-the-lottery-e705984e4df)を最近見かけた位でした。日本語でも、ざっくり調べた感じ[NHNのブログ](https://techblog.nhn-techorus.com/archives/15178)など幾つか記事が存在するようです。

とは言え、2番煎じ感が強かったことと、その後幾らか発展がありましたので、NeurIPS 2019に採択された2本も併せて解説します。2本目はUberの研究者、3本目はFacebookの研究チームの論文となりますが、いずれの論文もとても丁寧に実験が行われていています。

ちなみにGoogle & Deep Mindも、このテーマで論文を最近書いているのですが[^0-1]、少し方向性が異なるような気がしたのと、まとめる時間がなかったので、今回は割愛させていただきました。

[^0-1]: https://arxiv.org/abs/1911.11134

本当は再現実験も試みていたのですが、限られた時間の中、思いの外苦労してしまっているので、こちらはまた別の機会にご紹介できれば、と思います。

#### 参考文献

* [1]: [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://openreview.net/pdf?id=rJl-b3RcF7)
  + Jonathan Frankle, Michael Carbin
  + cs.LG : 1803.03635
  + ICLR 2019


* [2]: [One ticket to win them all: generalizing lottery ticket initializations across datasets and optimizers](https://papers.nips.cc/paper/8739-one-ticket-to-win-them-all-generalizing-lottery-ticket-initializations-across-datasets-and-optimizers.pdf)
  + Ari S. Morcos, Haonan Yu, Michela Paganini, Yuandong Tian
  + cs.LG : 1905.01067
  + NeurIPS 2019
  + https://ai.facebook.com/blog/understanding-the-generalization-of-lottery-tickets-in-neural-networks/

* [3]: [Deconstructing Lottery Tickets: Zeros, Signs, and the Supermask](https://papers.nips.cc/paper/8618-deconstructing-lottery-tickets-zeros-signs-and-the-supermask.pdf)
  + Hattie Zhou, Janice Lan, Rosanne Liu, Jason Yosinski
  + stat.ML:1906.02773
  + NeurIPS 2019
  + https://eng.uber.com/deconstructing-lottery-tickets/

### 注意点いろいろ

本稿では、上記参考文献にかなり基づきつつも、用語や構成に関しては、執筆者の個性が強く出ている事を予めご了承ください。[^1-1]

[^1-1]: ついでに言うと、以下、導入部で時事ネタや風刺をこっそり入れていますが、特に他意はないので、大人な対応で流して頂けると助かります。

まずこの記事を書いている人間は、データ分析業界の人間で、一応普段から論文を読んだり、「深層学習」も使ってたりしていますが、研究のプロではないため、背景の研究等を汲み取れていない不正確な部分もあると思われます。なので何かありましたら、そこは適宜ご指摘いただけると幸いです。

また数学的に厳密な議論はしないものの、なるべく明確なステートメントで述べるために、本稿のみの用語を幾らか導入しているのに加え、論文内で導入された各用語の和訳も、執筆者が文脈に合わせて意訳したものとなっていたりします。もちろん広く使われている用語については、慣習に併せて使用しているつもりですが、不明点などありましたら、コメント等で問い合わせいただけると幸いです。

さらには、ところどころ私の理解や感想も紛れ込んでいますが（〜と思います、となっている箇所など）、まあ適当に流してください。その他、全般的に建設的な議論ができるコメントは大歓迎です。（あまり哲学的過ぎる議論に関しては、控えさせていただきます。）

図表に関しては、基本的に上記参考文献からの引用となっています。引用元はつけるつもりですが、抜け漏れがあるかもしれません。
また一般的な事実として周知されているものについては、適切なソースを示すのが逆に大変なので、特に引用しません。その他、引用等の抜け漏れ等ありましたら、ご指摘ください。

## 背景

まず深層学習界隈の大きな謎として、古典的な統計学習理論の期待に反して、過剰なパラメータを持つモデル（以後、本稿では過剰モデル、と呼びます）[^2-1]が、うまく学習できてしまう、というものがあります。それどころか、過剰モデルの方が、最終的な汎化性能が上、といったケースも散見されているようです。

[^2-1]: 本当は金持ちモデルと呼びたい...

実際に、（少なくとも推論に関して）パラメータが過剰である事は、学習したモデルに対し、精度をほとんど落とす事なくそのパラメータ数を削減できる場合が存在する事実から明らかです。以後、そのようにして得られたモデルを圧縮モデル、と呼ぶ事にします。最近だと（事前学習中に蒸留してはいますが）Distil BERTがその一例ですね。[^2-2]

[^2-2]: 例えば[このプレプリ](https://arxiv.org/abs/1910.01108)参照。

しかし、ここで次の疑問が出てくると思います：
学習したモデルのパラメータ数を、精度を担保したまま削減できるのであれば、最初から削減したパラメータ数を持つモデル（以後、推論最適モデル[^2-3]、と呼びます）で学習してしまった方が、計算コストも少なくて、二酸化炭素排出量も減り、おそらく飛行機を使わずヨットを使うくらいには環境にやさしいでしょう。そうでなくともストレージコストも減らせますし、GPUを1週間も回せない貧乏データサイエンティストにとっては、切実な問題です。[^2-4]

[^2-3]: 本当は、身の丈モデル、と呼びたい所ですが、忖度できる人間なのでやめておきます。
[^2-4]: 推論コストが低い事と、学習コストが低い事にどの程度相関があるか、はここでは議論しません。また過剰モデルで、何故学習がうまく行くのか、という問いもここでは対象外です。

原理的に必要なパラメータ数の推定が難しいのでは？、という反論は置いておいても、これは至極自然な疑問です。しかしながら、最適モデルを直接学習させても、圧縮モデルほどの性能は出ない事が経験的に、知られているようです。

本稿では、この事実に関連した『宝くじ仮説』と呼ばれている研究について、幾つか紹介したいと思います。

元論文を読む感じ、おそらく元々の動機は、より良い枝刈り(pruning)の模索からも来ていると思われるのですが、執筆者がそちら方面に疎いため、このような背景で切り込みたいと思います。

## 宝くじ仮説とは

以下、良い性能を持つモデル、とはテストデータに対する"適切な"評価指標が高い事を意味します。特にクラス均衡の取れた分類問題しか考えないため、評価指標としては正解率のみ想定していただければ十分です。また通常の学習スキーム（SGDやAdamによるミニバッチ学習）で、最良の性能を出すモデルを、学習最適モデル、と呼ぶ事にしましょう。[^3-1]
このモデルは、先に導入した推論最適モデルに比べて、遥かに多いパラメータ数（1,2桁上）を持つ事が経験的に知られています。また（明確な根拠はありませんが）、学習最適モデルから、蒸留などによって得られる圧縮モデルは、推論最適モデルと同程度のパラメータ数や性能を持つ事が期待されていますが、圧縮モデルが推論最適モデルである、すなわち蒸留結果を直接学習によって得られるかどうか、は非自明である、という事に注意しましょう。

[^3-1]: 正確には学習最適アーキテクチャと呼ぶべきですが、ここでは学習最適モデルと呼ぶ事にします。また前節で述べたように、一般に、学習最適モデルは過剰モデル、すなわち古典的な統計理論から期待されるパラメータ数よりはるかに大きな数のパラメータを持つ事に注意してください。さらに、全てのアーキテクチャを試し尽くす事は当然不可能であり、真の意味で最良なモデル事はできませんので、ここで言う「最良」は、実験可能な範囲で、という但し書き付きです。

以上を踏まえた上で、宝くじ仮説の主張は、大まかに言って次のようなものです：

> 学習最適モデルには、それ単独で同程度学習させても学習最適モデル並の性能が出るような、部分ネットワークモデルが含まれる

ここで『部分ネットワークモデル』とは、ネットワークの持つ幾つかのパラメータを、$0$に置いた時に得られるモデルです。この部分ネットワークモデルは学習最適モデルに対する圧縮モデル、と見なせますし、実際に後で見るように反復枝刈りという手法で獲得します。さらには、それ単独で学習最適モデルと同等の時間で同等の性能へ達成可能である（すなわち学習最適モデル）、という点も重要です。

一応、部分ネットワークモデルを"数学的に"表現しておきましょう。
パラメトリックモデル（仮説）を$f(w)$、さらにパラメータ$w$の取る空間を$\Theta := \mathbb{R}^k$（足し算とかは考えておらず、ベクトル空間ではないですが、すぐ後に見るように掛け算は定義します）とおきます。特に$i$番目の成分を、$w_i \in \mathbb{R}$と表します。
この時、マスク$m$を、$m \in \\{0,1\\}^k$あるいは$m_i \in \\{0,1\\}$で定義しましょう。

ここで定義したようなマスクをモデルに施す（適用する）とは、パラメータ$w$を$w_m := m \odot w$で置き換える事に他なりません。ここで$\odot$は要素毎の掛け算を表す記号です。[^3-2]

[^3-2]: [3]で議論されているような一般のマスクでは、要素毎の掛け算ではなく、ある特定の値に設定したり、あるいはスケーリング操作等を含む操作のフラグとして解釈されるべきですが（[3]では陽に述べておらず、かなり混乱を招きうる、と思われます）、この節では簡単のために、要素積とします。

そして、あるマスク$m$が与えられた時、新しいモデル$f(w_m)$の事を、元のモデル$f(w)$の部分ネットワークモデルである、と言います。[^3-3]

[^3-3]: BatchNormalizationなど、パラメータの統計量が順伝播時に入ってくるようなケースでは、この定義だといろいろ問題があると思うのですが、ここではそんな難しい事は考えずに、これで定義します。また。あるパラメータに0に値を取るマスクをかける事は、そのパラメータの値が変化しても出力が変わらず、ゼロ勾配により、訓練中も値が更新されない事を意味しているので、実質固定している(freezing)、のと同等です。

よって宝くじ仮説を少しだけ数学的な表現に近づけると、

> （ランダム初期化で与えられた）ほぼ全ての$w$に対し、あるマスク$m$が存在して、元モデル$f(w)$とマスクモデル$f(w_m)$を学習させた際に、元モデルと同程度の時間で同等以上の性能を出せる

というものです。

宝くじ仮説を提唱した著者らは、このような部分ネットワークモデルの事を当選券(winning ticket)と呼び、そうでないランダムな部分ネットワークモデルの事を一般券(random ticket)[^3-4]
と呼んでいます。

[^3-4]: 直訳では、ランダム券で、実際の処理に沿った分かりやすい訳なのですが、ここでは当選券と対比させるため、敢えて一般券と訳しています。一般券はだいたい「はずれ」です。

この主張は、推論最適モデルと同一のアーキテクチャを持つモデルでも、初期値によって最終的な性能が変わる事を意味しています。
すなわち、運良く"当選券"を実現する初期値から学習を始めた場合にのみ、学習最適モデルあるいは圧縮モデルと同等の性能を得る事ができ、それ以外の"一般券"で学習を実施した場合は、そこまでの性能に到達し得ません。これが「宝くじ仮説」と呼ばれる所以です。

この仮説の検証については後々見ていくとして、もしこの主張が正しい場合、一体何が期待できるのでしょうか？
推論最適モデルが得られる鍵は、良い初期値(当選券)を得る事です。
ただし「宝くじ」というルールにおいては、どれが当選券か、を事前に知る事は勿論あり得ないわけで[^3-5]、たくさんの一般券を買う必要があります。これは初期値の乱数シードをたくさん試す事に相当します。

[^3-5]: 後で、当選券の「汎用性」について議論しますが、学習を何回も行うにあたっては、「宝くじ」でなくなる可能性があるわけです。

しかしながら、現実の宝くじで、お財布に優しい枚数の購入を通して、当選券を引き当てるのが困難なように、無限とも言える初期値の組み合わせの中から、推論最適モデルに相当する当選券を選び出すのは極めて難しい可能性が高いです。
一方で、宝くじ仮説は、学習最適モデルからそういった当選券を何とか見つけ出せる、という事を言っています。これを今の喩えに当てはめると、この学習最適モデルは、当選券を含む一般券をたくさん買っている、という事を示唆しているわけです。つまりパラメータを過剰に用意する事で、一般券（＝ランダム初期値）をたくさん予め購入しておき、学習プロセスを通して、当選券を炙り出せる、という説明ができます。

仮に当選券の確率が1/100000だったとしましょう。
すると当選券を得るには、大雑把に言って、100000回程度くじを引く必要があります。つまり、推論最適モデルのアーキテクチャを持つモデルで、異なる初期値を持つモデルをオーダー100000個用意して、全て学習すれば、推論最適モデルが得られます事が期待できます。しかしながら、これは現実的とは言えないでしょう。

一方で、例えば、仮に推論最適モデルのパラメータ数が$10^5$程度で、その$10$倍程度のモデルを用意したとします。この時、組み合わせ論的には、部分ネットワークモデルの選び方は、少なく見積もっても$10000$桁以上の候補が存在します。つまり、$10^{10000}$の一般券を購入しているようなもので、それだけ買えば当選券は$10^{9995}$枚以上含まれている、と期待できるわけです。

もちろん実際の学習プロセスはかなり複雑だと思われますので、この正当化や計算等にどの程度意味があるかは分かりません。ただ、dropoutはニューラルネットワークのアンサンブルを行っているのでは、と言われるように、$10^{10000}$ものモデルを同時に学習させるのと同等の効果があるのだとすれば、学習最適モデルが、推論最適モデルよりも過剰なパラメータを持つ事がある程度納得できるかと思います。

## 検証方法：宝くじの当て方

ここでは[3]に従って、宝くじ仮説検証をある程度一般化した手順として紹介します。
大雑把な手順としては、

1. モデルパラメータをランダムに初期化し、マスクの値を全て1に初期化

1. モデルの初期値を保存し、訓練を実施して性能評価

1. 訓練終了後、モデルの初期パラメータと、学習済みパラメータから、マスクを生成する

1. マスクの値に応じて、モデルのパラメータの再初期化と固定を行い、2.に戻る

以上を、マスクの値が$0$である割合（枝刈り率）がある閾値を超えるか、テスト性能が閾値を下回るまで、繰り返していきます。[^4-1]

[^4-1]: ここでのテストデータセットは複数の枝刈り率の値で評価されており、何度も使い回されていますが、特に今回のセットアップでは、この値を基に特定の枝刈り率のモデルを使用したり、枝刈りを実施する事は想定しないため、特に問題ありません。もちろん、これは当選券がoverfitしていない事を意味するものでは無く、この点については、後で当選券の汎用性を議論する際に再度触れます。

#### 枝刈りマスク

一般的に述べるために、ステップ3.とステップ4.の詳細はぼかしましたが、もう少し詳しく見ていきましょう。

まず、ステップ3.で、モデルの初期パラメータと学習済みパラメータから、枝刈り率に応じたマスクを生成する（より正確には、パラメータ毎にマスクスコアをつける）手順の事を、「マスク基準」(mask criteria)、ステップ4.で、マスクからモデルのパラメータ再初期化を行う手順の事を、「マスク処理」(mask action)と呼びます。

元論文では上の２つは、次のような操作です：

* マスク基準：学習済みの重み$w_f$の絶対値$|w_f|$を取り、これをマスクスコアとする。このスコアに対し、上位$(100-p)$%にはマスク値$1$を割り当て、それ以外は$0$を割り当てる。ここで$p$は1回あたりの枝刈り率で、$m$の平均値を$\bar{m}$(sparsity)とおくと、$p=1-\bar{m}$の関係にあります。要するに、マスク値が$0$のパラメータの割合の事で、これが大きいほど、刈られるパラメータ数が増え、採集的に得られるモデルは、小さくなります。

* マスク処理：
  + マスク値が$0$の時：重み$w$を$0$にセットして訓練時にも固定
  + マスク値が$1$の時：重み$w$をその初期値$w_i$に再設定
  + これらの処理は、重み$w$をその初期値に巻き戻して、マスク$m$と重み$w$の要素積として掛け算を実施する事に他ならない。

#### 枝刈り方法の種類

枝刈りをちょっとずつ繰り返す（上のステップ2.から4.を繰り返す）「反復枝刈り」(iterative pruning)と、一気に枝刈りを実施する（上のステップ3.で終了）「単発枝刈り」(one-shot pruning)の2種類があります。

前者の反復枝刈りでは、一般に1回あたりの枝刈り率$p$を固定し、それを$N$回繰り返すと、マスクの平均値は$(1-p)^N$、総枝刈り率は$1-(1-p)^N$となります。すなわち、こちらは、後者の1回限りの枝刈りに比べて、（最終的な総枝刈り率が同じでも）1回の枝刈り率が小さくなります。これは枝刈りをする際に、マスクスコアの低い重みをより多く残す事に他ならず、将来的に重要な重みになる可能性も考慮して、念の為刈らず取っておく、慎重な方法と言えるでしょう。結果として、反復枝刈りを用いた場合の性能は、単発枝刈りの場合よりも一般的に高くなります。

一方で、欠点も当然存在します。それは反復回数$N$回分だけ訓練を実施しなければならない、という点です。すなわち、計算コストは単発枝刈りに比べておよそ$N$倍かかるため、ここは計算コストと精度のトレードオフにあると言えるでしょう。

また、レイヤー毎にマスクスコア評価を行って、枝刈り率を固定する局所枝刈り(local pruning)と、モデル全体でマスクスコア評価を行う大域枝刈り(global pruning)の２通りがありますが、基本的には後者が使われます。
実際、モデルのレイヤー毎のパラメータ数にはばらつきがあり、CNNだと、入力に一番近い畳み込み層のパラメータ数が最も少なく、識別層の初期層のパラメータ数が最も多い傾向にありますが、レイヤー毎に枝刈り率を固定してしまうと、ただでさえパラメータ数の少ない層にパラメータが残らなくなります。

例えばVGG系だと、特徴抽出層第1層は$1792$個（カーネル$3 \times 3$、入力チャンネル$3$、出力チャンネル$64$で$3 \times 3 \times 3 \times 64 + 64 = 1972$）であるのに対し、識別層第1層は$102,764,544$個(入力ユニット数$7 \times 7 \times 512$、出力ユニット数$4096$で$7 \times 7 \times 512 \times 4096 + 4096 = 1972$)と、6万倍近く差があります。
枝刈り率$99$%の時は、前者は$18$個しかパラメータが残らず、これは流石に少ないと考えられます。[^4-2]

[^4-2]: 正確には、[1]では、識別層の枝刈りは実施せず、畳み込み層全体でのみ大域的枝刈りを行っているようです。

なお実際の実験結果については、次節を参照してください。

## 実験結果：当選券は大当たり

元論文[1]では、データセットとしてMNISTとCIFAR-10が、モデルとしてLeNet、2,4,6層のCNN、VGG-19、ResNet-18が用いられています。また1回辺りの枝刈り率は、畳み込み層20%、識別層0%となっているようです。

さて、そこでは次のような観察事実があります：

・当選券を利用した場合、枝刈り率を上げていく（＝パラメータ数を減らしていく）につれ、初期はテスト正解率が幾らか上昇していき、ある時点で最高性能に達した後、徐々に落ちていく傾向にある（ただし、必ずしも上昇するとは限らない）

・一般券を利用した場合、枝刈り率を上げてもテスト性能はせいぜい誤差範囲内でしか向上せず、右肩下がりになっていく

特にLeNetや小さなCNNではかなり上手くいっていますが、グラフ等の引用は割愛します。代わりに、より大きなモデルであるVGG-19やResNet-18の結果の方を見てみましょう。

以下の2枚の図、合計6個のグラフにおいて、上下はモデルの違い、3つのグラフは学習量（更新回数）、線種は再初期化の方法、色は学習方法の違いに対応しています。具体的には

* 上：VGG-19、下：ResNet-18
* 各図とも、左から右にいくにつれ、学習量が増えていく（数値は図参照）
* 実線：当選券、点線：一般券
* 青色：学習率0.1、橙色：学習率0.01、緑色：初期は線形warm up（数値は図参照）

![From [1]:Fig7](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/211360/48c41323-53d0-2c61-0d20-a62d3a381248.png)

[1]のFigure 7 : VGG-19の当選券成績

![From [1]:Fig8](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/211360/cc3a962b-0f11-7af2-5d69-dad826f7d810.png)

[1]のFigure 8 : resNet-18の当選券成績

グラフを眺めてみると分かるように、殆どのケースで実線は点線より上にきている事から、当選券は一般券よりも性能が勝る事が分かります。この結果から、このセットアップについては、宝くじ仮説はかなり信用できる、と言えるでしょう。

ちなみに(学習初期の)学習率が大きいほど、当選券と一般券のギャップは小さくなるのは、ナイーブにはパラメータ更新が激しくなり、初期値依存性が薄まるからだと思われます。ただ一方で、warm upを用いると、当選券と一般券の性能差が、より顕著に出てくるのは個人的にとても興味深い結果だと思いますが、これについては今の所よく理解できていません。
さらに言えば、高い枝刈り率で、warm upより学習率0.01の結果が高い傾向も見られるような気がしますが、これも気になる点ではあります。

## 当選券の再利用

前節で、宝くじ仮説の妥当性を見てきました。ただしそこで用いたデータセットはMNISTだったり、CIFAR-10といったかなり小さい非現実的なものです。よって、より巨大なデータセットでも検証すべきでしょう。

本節では、[2]に従い、巨大なデータセットでの評価に加えて、あるデータセットで得られた当選券が、他のデータセットでも有益か、という"転移"の議論も見ていきましょう。ここでは当選券を他のデータセットで使い回すことを、せっかくなので"転売"と表現する事にします。[^6-1]

[^6-1]: 転移学習と区別する意味でも、ここでは敢えて違う名前をつけています。

ちなみにここで出てくるデータセットには、ソースデータセットとターゲットデータセットという2種類があります。
ソースデータセットで反復枝刈り＆訓練を行って当選券を生成し、それをターゲットデータセットで評価するわけです。

##### セットアップ

* データセット：SVHN、Fashion-MNIST、CIFAR-10、CIFAR-100、ImageNet、Places365
* モデル：VGG-19とResNet-50
* 1回辺りの枝刈り率：全体で20%

## 実験結果：当選券の転売

[2]の著者らの結果は次の２つの図に集約されます。

![From [2]:Fig3](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/211360/9da3986c-f07f-9204-2178-6468de5de987.png)

[2]のFigure 3 : VGG-19の転売実績

![From [2]:Fig4](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/211360/fb617787-ccea-7346-115b-006f2829f75b.png)

[2]のFigure 4 ： ResNet-50の転売実績

* 上：VGG-19、下：ResNet-50
* 各グラフ（タイトル）：評価対象のデータセット
* グラフ内の各曲線（色）：当選券を生み出したデータソース
* 横軸：当選券生成時の枝刈り率
* 縦軸：正解率
* 曲線の幅：6回の乱数シード(初期値を変えて6回試行)に基づく標準偏差

ここから読み取れる事として、

* 90%程度(ケースによっては、95%程度でも)の枝刈り率でも精度はほとんど落ちていない
* 巨大なデータセットでも、当選券は一般券より優れており、特に高い枝刈り率で顕著な差異が見られる
  + 例えば、ImageNet(グラフe)の赤い曲線(random)とそれ以外を比較
* データセットが巨大であるほど、転売時の性能も良い
  + 一般に緑(ImageNet)や茶(Places365)の曲線は、他の青(CIFAR-10)や黄(CIFAR-100)の曲線よりも上に来ている（性能が上）
  + Fashion MNISTでの評価でも、過学習の懸念もなんのその、問題なく転売できており、なんならFashon MNISTで生成した当選券より低い枝刈り率では高性能
* クラス数が多いほど、転売時の性能も良い（少なくとも小さい画像サイズに関しては）
  + 黃(CIFAR-100)の曲線は、青(CIFAR-10)よりも上にきているため

などが挙げられます。ここから、データセットが"複雑"（サンプル数が多い、クラス数が多い、画像サイズが大きい）であればある程、得られる当選券の転移性能も向上し、その意味で汎用的である事が示唆されています。

この事実は応用上も重要です。というのも、もし転売が有用でないとすると、当選券を得るためにデータセット毎に1度学習する必要があります。しかしこの結果から、1度巨大なモデルで当選券を頑張って生成しておけば、他のデータセットでも使える可能性が高い事が分かりました。

ちなみに、枝刈り率を増やすにつれ、性能が向上するケース(CIFAR-100など)が、当選券・一般券に関わらず幾らか見受けられますが、これは枝刈りする前の元のモデル(VGG-19やResNet-50)が、学習最適モデルよりも過剰なパラメータを持つからだとおそらく思われます。

## 最適化手法間での転売

[2]では、データセット間の転売だけでなく、最適化手法(optimizer)間の転売も議論しています。
ここでは、CIFAR-10をソースデータセットとし、ソース最適化手法としてSGD、Adamで得られた当選券と、一般券の３つが、同じCIFAR-10上のターゲット最適化手法としてSGDとAdamにした際の性能を同様に評価しています。

結果の方は次の２つのグラフに集約されていますが、ここでもやはり、異なる最適化手法間（少なくともIFAR-10上のSGDとAdam間）では転売に成功している事が読み取れます。

![From [3]:Fig5](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/211360/6ac92938-abdb-158d-13db-49d9b0e7ab70.png)

[3]のFigure 5 : 最適化手法間の転売

## マスク規準

これまでは、宝くじ検証手順は（詳細を除けば）ほぼ固定でした。本節からは、宝くじ検証手順をいろいろ変えて実験を行った[3]の仕事を紹介します。この研究では、宝くじ検証でさも当然かのように導入された、"直感的な"手順を疑う所を出発点にしています。

さて元の宝くじ検証手順におけるマスク規準として、モデルの重みの絶対値をマスクスコアとして、その上位$(1-p)$%をマスク値1として次の訓練時も更新し、残りをマスク値0として取り除く（あるいは同じことだが、値を0に設定して訓練時は固定する）、という操作が行われていた事を思い出しましょう。[3]では、まずこの部分に疑問を投げかけ、いろいろ変えてみる、という実験が行われています。

そのために、改めてマスク規準を記述しなおしてみます。各重みについて、重みの初期値$w_i$と学習終了時の最終値$w_f$とする時、このペアに対し、実数値のスコアを割り当てます。本稿ではこれをマスクスコアと呼び、このマスクスコアの閾値$M^\ast$を決める事で、マスク値の0,1を決定します。

このマスクスコアを与える関数を$M$と表しましょう。この時、マスクスコアは$M(w_i, w_f)$と表せます。後は、$M(w_i, w_f) > M^\ast$となる重みについては、マスク値$1$が、$M(w_i, w_f) < M^\ast$となる重みについては、マスク値$0$が、それぞれ割り当てられるわけです。
そして、これまでの実験では、$M(w_i, w_f) = |w_f|$と表現できるわけです。この関数を与えることが、マスク規準を決める事に他なりません。

[3]では、以下の9つのマスク規準が比較のため考案されました：

* large_final :$|w_f|$
  + 学習終了時、重みの絶対値が大きいものを保持
* small_final : $−|w_f|$
  + 学習終了時、重みの絶対値が小さいものを保持
* large_init :  $|w_i|$
  + 初期化時、重みの絶対値が大きいものを保持
* small_init : $-|w_i|$
  + 初期化時、重みの絶対値が大きいものを保持
* large_init_large_final : $\min(α|w_f|, |w_i|)$
  + 初期化時・学習終了時、両方共、重みの絶対値がある閾値以上のものを保持
* small_init_small_final : $−\max(α|w_f|, |w_i|)$
  + 初期化時・学習終了時、両方共、重みの絶対値がある閾値以下のものを保持
* magnitude_increase : $|w_f| - |w_i|$
  + 学習終了時の重みの大きさが、初期化時に比べて閾値以上変化したものを保持
* movement : $|w_f-w_i|$
  + 学習終了時の重みが、初期化時に比べて閾値以上変化したものを保持
* random : $r \sim U([0,1)$
  + ランダム初期化

これらを2次元的に表現した図も分かりやすかったので、以下に引用しておきます。

![From [3]:Fig2](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/211360/1591bda2-74cb-7410-5966-80244498551c.png)

[3]のFigure 2 : 様々なマスク規準

### 結果

セットアップは、[1]と同じで、LeNet on MNISTと2,4,6層のCNN on CIFAR-10です。そして比較結果は以下の図のグラフです。

* バンドはlarge_final, magnitude_increaseとrandomだけ図に示しており、これは5回の思考実験の最大・最小を表している
* ★点は、large_finalとmagnitude_increaseが、互いよりもp値0.05で有意に上回った枝刈り率の点を表す

![From [3]:Fig3](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/211360/5fd3b3f8-453b-b77c-0c3e-05cf4eead6dd.png)

[3]のFigure 3 : マスク規準比較

randam(一般券)を上回ったのは、性能順にmagnitude_increase、large_final、large_init_large_final、movement、large_initですが、基本的には（想像通りではありますが）学習終了時の重みの大きさが大きい程重要であることを物語っています。
ただmagnitude_increaseがケースによってはトップクラス、という事実は、応用上重要な可能性は大いにあります。

## マスク処理

前節では、最終的にその絶対値が大きくなる重みが重要である事を再認識しました。そして、当選券と一般券を切り分けているものは何か、という問いへさらに切り込みます。その目的のため、著者らは、初期化方法の変更を提案しています。

以下、マスク値が$1$の場合の処理(Mask-1 actions)と、$0$の場合の処理(Mask-0 actions)それぞれについて、簡単に提案手法とその結果について眺めていきます。なお、いずれもデータセットやモデル、訓練セットアップは、前節のマスク規準比較と同一です。

### マスク値$1$（保持対象）に対する処理

保持対象の重み、すなわち訓練時に実際に更新される重みの初期化ついては、3つの新たな比較実験が提案されています。

* Reinit : 元の初期値分布から経験サンプリング
* Reshuffle : マスク値$1$の重み間で、値をシャッフルし、個々の重みの値ではなく、全体の分布のみが初期と同じになるよう再初期化
* Constant : $0$, $\alpha$, $-\alpha$の三定数値に設定
  + ここで$\alpha$は層毎の初期分布の標準偏差に設定する

より詳細には、各手法とも次の２種類のパターンを試しています：

* init_sign : 元の初期値と同一符号になるよう制御
* rand_sign : 符号に関して特に制御していない

その結果は以下の通りです。

* 線種：
  + 実線：init_sign、点線：rand_sign
* ★点は、rewind (large_final)(従来手法)とconstant (init_sign)が、互いよりもp値0.05で有意に上回った枝刈り率の点を表す

![From [3]:Fig4](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/211360/925f27ae-61d7-c13c-f51e-206cd2da404b.png)

[3]のFigure 4 : 保持対象重みに関する初期化比較

この結果から、著者らは、符号の維持こそが、当選券の重要な鍵になることを主張しています。

ちなみに前節の結論は、重みの絶対値が大きくなるようなものを保持する傾向の規準が、当選券を得る上で重要である、というものでしたが、一見すると整合的でないように最初私には見えました。おそらくですが、重みの絶対値が大きい事は以前重要であり、というのも、小さい重みは用意に符号が反転してしまって、符号が安定しないから、という意味で、整合的なのかな、と理解しています。

またこれも論文では触れられていないですが、気になっている点として、一般券には勝っているものの、reinit (init sign)だけ他の当選券に比べてやたら性能が低い事があります。特にreinitとreshuffleは、低い枝刈り率では同じような操作にも見えますが、ここまで性能間に違いが出るのは、なかなか興味深い結果ではないでしょうか？

### マスク値$0$（除去対象）に対する処理

最後のターゲットは、除去対象の重みです。ここでは、新たな3つの手法を提案しています：

* 初期値に巻き戻し、訓練中は固定
* 初期化時の重みの絶対値が、学習終了時のものよりも大きい場合に0へ設定し、そうでない場合は初期値に巻き戻す
* 上の手法を、マスク値1のものにも適用

著者らが後者２つの実験を提案した背景としては、

> 訓練を通じて、その値が0に近づいていくような重みは、当選券にとって重要でない

という仮説を新たに提唱しているためです。更に言えば、これまで当選券を生み出してきたマスク規準、特にmagnitude_increaseは、最終的に0から遠ざかっていく重みを優遇するものでした。もしこの仮説が正しいとすると、マスク規準は、当選券にとって重要でない重みを除去対象として選び出しているため、マスク規準の比較結果を十分説明できます。


そして肝心の比較結果は以下になります：

![From [3]:Fig5](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/211360/cc26e4d6-0690-ed54-9ca6-bc0693b55c0e.png)

[3]のFigure 5 : 除去対象重みに関する処理比較

結果は最後の手法が最も効果的であり、先の仮説の正しさを示唆していると言えます。

## 超マスク

最後に、少し毛色が変わるのですが、[3]で試みられている面白い実験もついでに紹介したいと思います。

先の仮説の本質を一言で表すと、
> 当選券は学習時に0に近づく重みを切り捨てたもの

となるわけですが、これをさらに推し進めて、当選券を得るマスク規準に基づくマスク操作とは、
> 重みを、学習時に動くであろう方向へ動かす操作

すなわち、訓練と同等の操作であるのでは、という ~~妄想~~ 推察を行っています。なので、勾配法に基づいて重みを更新する通常の訓練をしなくても、うまいマスクを選んできて、未訓練ネットワークに施してやれば、ある程度性能が出るのでは、という結論にたどり着いています。ちなみに著者らは、このマスクを特注マスク(supermasks)と呼んでいます。

そろそろ説明に疲れてきたので、詳細は割愛して結果だけ述べますが、著者らは、マスク規準の変種をさらに利用して、パラメータ更新することなく、未訓練のニューラルネットワークモデルに対し、MNISTで最大86%、CIFAR-10で最大41%を叩き出すような特注マスクを作り出しています。

なお、この特注マスクは、１回最後まで訓練した結果を基に、マスク規準を通して作られたものです。なので、通常の意味で訓練は確かに行ってはいませんが、間接的に重みを評価しており、あくまで通常の訓練が不要になる、といった事を主張しているわけではない事に注意する必要があります、

## おまけ：感想

唐突ですが、私は普段、実験中心の論文を丁寧に読む事は少なく、読む際は、主に次のどちらかが動機としてあります：

・理論的に面白いか？（アカデミア志向）
・応用上有益そうか？（ビジネス志向）

今回の論文達は、これらの中間的立ち位置にあると同時に、ある意味どちらにも当てはまらないと思っています。実際、「深層学習」という劇薬の中で、何が起きているのか、についてたくさんの示唆に富んだ面白さを提示しながらも、一方では、応用やさらなる研究の発展の可能性も随所に垣間見えた気がします。

今回、追試実験も含めかなり丁寧に行われている事から、宝くじ仮説は一定の信頼を得ている一方で、無視できない何か、を我々に突きつけています。特に、当選券のうち何が本質的に重要なのか、という根本的な疑問の解決にはまだ何か足りていない印象を受けました。
ちなみに個人的には、当選券が、学習のより動的な側面から何か特徴づけられるのか、またdropoutによる汎化性能獲得といった現象と関連があるのか、といった問題などの方向性が読んでいる際に気になっていたので、そういった方面への発展も期待したい所です。