編譯 | Mr Bear
編輯 | 陳大鑫
在人們互相交流和信息傳遞的過程中，「隱喻」的作用極其重要。在1970年之前，當人們提起「桌面」這個單詞，聯想到的還都是放滿了鍋碗瓢勺的桌子。但是當天才計算機大師Alan Kay在 Xerox PARC 實驗室設計了現代的 GUI 交互界面之後，桌面這個詞可能更多的指代的就是配備各種圖形化作業系統的電腦桌面了。
近年來，在深度學習領域，人們將一個新的具有廣闊前景的研究領域隱喻為「彩票假說」（LTH）。在本文中，我們會深入探討該假設，並回顧 Frankle 和 Carbin 在 ICLR 2019 上發表的那篇風光無限的最佳論文《THE LOTTERY TICKET HYPOTHESIS: FINDING SPARSE, TRAINABLE NEURAL NETWORKS》。
1
深度學習模型剪枝
對過參數化的神經網絡進行剪枝是深度學習領域中經久不衰的問題。其中，最常見的方法是將某些特定的權值設置為零，並且在隨後的訓練過程中凍結它們（不進行訓練）。這種思想比較樸素，實現也很簡單，只要將權值 W 和一個二元剪枝掩模 M 按對應元素相乘即可。進行這種幹預的動機如下：
通過對過參數化的函數進行正則化處理，使剪枝後的模型具有較強的泛化能力。能夠找出原本龐大網絡中性能優越的小型子網絡（現有存儲條件可滿足），從而減少模型前向推理時的內存需求。減少了模型所需的算力、耗電量、存儲和延遲等需求，從而使其能夠在行動裝置部署。近年來，隨著網絡模型的深度越來越深，以上三個問題逐漸受到了人們越來越大的關注。一般來說，優秀的網絡剪枝算法必須解決以下 4 個基本問題：
問題 1：應該剪掉怎樣的連通結構？
非結構化修剪不考慮剪枝的權值之間的任何關係。另一方面，結構化剪枝則是通過去除整個神經元（權值列）、刪除卷積神經網絡的卷積核或通道等方式對一組權值進行剪枝。儘管非結構化的剪枝方法往往能在保持較高性能的同時剪掉數量更多的權值，但是這種方法並不一定會真正加速在標準硬體上的計算過程。實際上，這裡的關鍵原因在於密集的計算可以很容易被並行化處理；而剪枝後的網絡通常過於「分散」，難以實現並行計算。
除了從結構化角度來對剪枝算法進行分類，我們還能夠從局部和全局剪枝的角度進行另一種分類。其中，局部剪枝方法會強制從網絡的每一層剪掉一定比例的權值參數。而全局剪枝就沒有這個要求了，它只需要將整個網絡中 s% 的權重參數剪掉即可。
圖 2：深度學習網絡剪枝要考慮的因素：剪掉哪些部分、如何剪枝、何時剪枝、剪枝頻率如何？
問題 2：如何對有待剪枝的權值參數進行排序？
已經有一些研究人員或多或少使用了啟發式方法對網絡中的某個權值的重要性進行評估。其中常見並且有效的經驗是，網絡中權重取值較大的連接或者說神經元對網絡的表達能力和函數擬合能力更加重要，剪枝算法應該儘量避免剪掉這些權值。儘管這種經驗非常實用，但是從直覺上說，這好像和 L2 權值正則化方法的思想有些矛盾。在 L2 正則化方法中，損失函數會對取值很大的權重進行較大的懲罰，避免網絡過度依賴於某些權重或者神經元，從而保證模型的泛化能力。這種對於權值處理的矛盾也催生出了相關的技術，這些技術使用基於梯度的方法或者更高階的曲率信息來學習剪枝掩模。
問題 3：我們應該多久進行一次剪枝？
基於權值的幅值對其重要性進行評估會在很大程度上受到噪聲幹擾。我們知道，網絡剪枝方法可以分為單次剪枝（One-Shot）和迭代式（Iterative）剪枝。單次剪枝會極大地受到噪聲的影響，而迭代式剪枝方法則會好很多，因為它在每次迭代之後只會刪除掉少量的權重，然後周而復始地進行其他輪的評估和刪除，這就能夠在一定程度上減少噪聲對於整個剪枝過程的影響。通常，每次迭代的剪枝率大概在 20% 左右，總共需要進行 20~30 輪剪枝迭代（最終僅僅保留 1% 未被剪掉的網絡權重）。當然，我們可以設計網絡來讓修剪後保留的權值參數更多一些（即更保守），但是這會增加算法的訓練時間。
問題 4：何時執行剪枝步驟？
具體來說，我們可以在「訓練前」、「訓練中」和「訓練後」三個不同的階段執行剪枝。其中，在訓練收斂後進行剪枝的方法通常會降低模型的泛化能力，所以很多工作需要重新對模型再次進行微調。除了訓練後的剪枝，訓練中的剪枝方法也很常用，這種方法通常是跟正則化、Dropout、強化分布式表徵等思想相關聯。然而，從頭開始訓練一個稀疏的網絡幾乎是不可能的，所以「訓練前」剪枝的方法很少被使用。
2
彩票假設（LTH）及其擴展方法
Frankle & Carbin (2019) — The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks
論文連結：
https://openreview.net/forum?id=rJl-b3RcF7
代碼連結：
https://github.com/facebookresearch/open_lth
當前有很多研究已經證實，在不顯著降低網絡性能的前提條件下，一個訓練好的稠密的網絡能夠被剪枝成一個參數量很小的網絡。實際上，人們曾在很長的一段時間內認為，從頭開始訓練一個稀疏的網絡幾乎是不可能的。這是為什麼呢？其實，較小的子網絡確實可以近似一個性能良好的函數，但是它與稠密的網絡相比，其學習模式（learning dynamics）有很大的差別。
在 Frankle 和 Carbin 與 2019 年發表的「彩票假設」原始論文中，作者首先解釋了可能造成這種現象的原因。他們認為在網絡剪枝之後，生成的子網絡會被隨機初始化。但是，如果我們能在生成裁剪網絡之後，將子網絡的權重重新初始化為它們的原始權重（在剪枝後已經被掩模屏蔽了），那麼在經歷較少輪的迭代之後，網絡就有可能恢復到它在剪枝之前的性能，甚至可能達到更好的性能。這些性能特別優越的子網絡就好比在權值初始化彩票遊戲中中獎的幸運兒。彩票假設的具體內容如下：
彩票假設：任何隨機初始化的稠密的前饋網絡都包含具有如下性質的子網絡——在獨立進行訓練時，初始化後的子網絡在至多經過與原始網絡相同的迭代次數後，能夠達到跟原始網絡相近的測試準確率。
那麼我們如何才能找到這種「中獎網絡」呢？Frankle 和 Carbin 在 2019 的論文中提出了迭代幅值剪枝（IMP，iterative magnitude pruning）方法：首先，對初始的稠密網絡進行多輪訓練，直到模型收斂。然後，我們確定最小的 s% 個權值，並創建一個二值掩模對這些權值進行剪枝。隨後，我們使用之前的初始化權值重新訓練稀疏化後的網絡。在模型收斂後，我們重複該剪枝過程（屏蔽額外的 s 的權值），並使用新一輪剪枝後發現的掩模設置初始化權值。我們重複這個過程，直到達到期望的稀疏程度，或者測試準確率顯著下降。
圖 3：尋找「中獎網絡」的過程
如果 IMP 算法成功執行，它就能找到「中獎網絡」，即經過迭代式的剪枝過程後留下的子網絡。請注意，我們也可能通過簡單的單次剪枝方法實現這一目的，但是當執行額外的計算時，我們可以獲得更好的結果（詳見原始論文的圖 4）。如果我們回顧一下前面提到的網絡剪枝中普遍存在的問題，那麼 IMP 需要滿足以下條件：
圖 4：IMP 與網絡剪枝的核心問題
下圖總結了第一篇 LTH 論文的一些關鍵的實驗結論：
圖 5：LTH 的關鍵性結果。
B 圖：IMP 能夠在不進行任何超參數調整的前提下，僅使用較少的迭代次數就能找出性能超越未修剪的稠密網絡的稀疏子網絡（圖 B 中不同顏色的曲線代表不同的被剪掉的權值比例）。其中，中獎彩票的初始化和隨機重初始化的最終性能之間的差異被稱為「彩票效應」（Lottery Ticket Effect）。圖 C 和圖 D：為了能夠將原始的實驗結果擴展到更加複雜的任務和網絡架構中（如 CIFAR-10數據集，VGG19 和 Resnet20 等網絡），Frankle 和 Carbin 不得不對學習率進行調整，並且引入「熱身」規劃機制，讓模型在預定義的迭代集合內從 0 退火到最終的學習率上。請注意，根據經驗，適合於 ResNet 的學習率遠遠小於適合於 VGG19 的學習率。上述結論告訴我們什麼呢？首先，IMP 算法能夠找到一個有利於當前任務的子結構，而且子網絡的權值初始化需要通過特殊的學習模式獲得。此外，成功的訓練並不一定需要過參數化——過參數化可能只能通過排列組合提供一些可用的子網絡選項，而這些排列組合是會造成組合爆炸效應的。當前已經有很多後續的工作嘗試嘗試揭示「中獎網絡」與普通網絡定性的區別背後的潛在機制。
Frankle et al. (2019) — Stabilizing the Lottery Ticket Hypothesis
論文連結：https://arxiv.org/abs/1903.01611
代碼連結：https://github.com/facebookresearch/open_lth
原始的「彩票假設」論文存在的局限性之一是：該研究僅僅局限於小規模的任務，比如 MNIST 和 CIFAR-10。那為了能夠將 LTH 擴展到其它更加複雜的任務上，Frankle 和 Carbin 不得不調整學習率的變化策略。
Liu 等人https://arxiv.org/pdf/1810.05270.pdf和Gale 等人（https://arxiv.org/pdf/1902.09574.pdf)）
分別發現，如果我們不調整學習率的話，所訓練出來的小網絡性能會很差，無法達到和原始的網絡相近的性能。既然如此，如果我們將「中獎彩票」的限制放寬鬆，將會如何呢？
在 Frankle 等人的後續工作（https://arxiv.org/abs/1903.01611）中，他們嘗試通過將權值重新設置為經過了較少的 k 輪訓練之後得到的權值，而不是網絡的初始化權值，從而魯棒地獲得剪枝後的子網絡。換而言之，我們在剪枝後不將權值「回放」到第 0 輪迭代時的情況，而是將權值回放到第 k 輪迭代時情況。該工作的形式化定義和圖解如下所示：
圖 6：帶回放機制的彩票假設
由於我們沒有對網絡進行徹底的訓練，只是進行了前 k 步的訓練，所以我們找到的這個初始化策略就不能再被叫做「中獎彩票」，它只能算作是一個「接近中獎的彩票」（Matching Ticket）。
圖 7：帶回放機制的 IMP
這種做法的一些關鍵性結論如下圖所示：執行 IMP 算法時，將剪枝後的網絡權重回放為 k>0 的某次迭代後的值是很有效的。它能在仍舊獲得和原始網絡相近的測試性能的同時，剪掉高達 85% 的權值參數。當算法將 k 設置為500時（如圖 8 A 所示），該結論在 CIFAR-10 數據集和 ResNet-20 模型上也成立；當算法將 k 設置為 6 時，該結論也適用於 ImageNet數據集 和 ResNet-50。此時，我們並不需要使用學習率的「熱身」操作。
圖 8：LTH 關鍵結論的放縮結果
Renda et al. (2020) — Comparing Rewinding and Fine-tuning in Neural Network Pruning
論文連結：https://arxiv.org/abs/2003.0238
代碼連結：https://github.com/lottery-ticket/rewinding-iclr20-public
至此，我們已經討論過 IMP 是否能夠找出一種性能與「中獎網絡」相近的網絡初始化狀態。但是和其它剪枝算法相比，IMP 的剪枝算法流程有何異同呢？在 Renda 等人於 2020 年發表的論文「Comparing Rewinding and Fine-tuning in Neural Network Pruning」（https://arxiv.org/abs/2003.02389）中，他們比較了三種不同的剪枝過程：
1、調優：在剪枝過程結束之後，算法對剩餘的權重使用較小的學習率繼續進行學習，從而得到最終的權重取值。一般來說，這個較小的學習率也是稠密的原始網絡最終的學習率。
2、權值回放：該方法與 Frankle 等人在論文「Stabilizing the Lottery Ticket Hypothesis」中使用的方法對應。在剪枝之後，剩餘的神經元權值被重置為第 k 次隨機梯度下降迭代後的權值。此後，算法以第 k 次迭代時的權值為起點，使用某種學習率調整策略重新訓練權值。此時，權值和學習率的調整策略都會被重置。
3、學習率回放：該方法並未回放權值或將學習率調整策略設置為初始狀態，學習率回放使用的是最終未剪枝的權值，並且只將學習率調成策略調整到第 k 輪迭代的狀態。
Renda 等人在論文「Comparing Rewinding and Fine-tuning in Neural Network Pruning」中對比了上述三種方法在準確率、搜索成本和參數效率三個方面的優劣，並且回答了下面的幾個問題：
假設我們可以用無限的算力進行搜索，上述三種模型約簡方法最終的準確率和參數效率（剪枝前後的壓縮比）的表現和差異將如何？給定固定的用於搜索的算力預算時，上述三種模型約簡方法最終的準確率和參數效率的表現和差異將如何？為了回答上面的問題，作者使用 ResNet 34、ResNet 50、ResNet 56 網絡在 GNMT 自然語言處理對比基準上進行了實驗，並得到如下的結論：
在算力無限和給定固定算力預算的實驗中，使用權值回放並重新訓練的性能都明顯優於簡單的微調並再訓練的方法。在結構化和非結構化剪枝的對比實驗中，該結論也成立。學習率回放方法的性能優於權值回放方法。此外，雖然權值回放法在 k=0 時可能效果不好，但將學習率回放到訓練過程開始的狀態往往是有效的。在準確率、壓縮比和搜索成本效率方面，權值回放 LTH 網絡是目前性能最優的對初始網絡進行剪枝的模型。在經過了大規模的實驗後，研究人員提出了許多有關深度學習的實驗性結論，但問題是：對於我們理解這些高度非線性的系統（深度神經網絡）來說，這些結論究竟有什麼含義？
3
剖析彩票假設：魯棒性與學習模式
Zhou et al. (2019) — Deconstructing lottery tickets: Zeros, signs, and the supermask
論文連結：
https://papers.nips.cc/paper/8618-deconstructing-lottery-tickets-zeros-signs-and-the-supermask.pdf
代碼連結：
https://github.com/lottery-ticket/rewinding-iclr20-public
決定某個初始網絡是否為「中獎網絡」的主要因素是什麼？也許，這些因素包括：掩模屏蔽的標準（權值的大小）、回放未被屏蔽的權值的方法，以及將權值設置為零並凍結它們的掩模。但是，如果我們改變以上三種因素其中的一個，結果將如何呢？較大的權重會有什麼樣的影響？使用其它回放策略是否還能夠找到中獎網絡呢？為什麼要把權值設置為零？Zhou 等人在論文「Deconstructing lottery tickets: Zeros, signs, and the supermask」中從以下三個方面對這些問題展開了研究：
對比不同的選擇被屏蔽權值的打分方式：保留那些最小的訓練後權值；保留初始化時最大或者最小的權值，或者在權值空間中幅值變化最大或最小的權重。分析如果不將權值回放到初始狀態，是否仍然會得到中獎網絡：Zhou 等人對比了隨機重初始化、重新打亂保留的權值，以及恆定初始化等情況。將被掩模屏蔽的值固定為初始化的值，而不是將它們設定為 0。通過大量的實驗，作者得出了以下結論：
那些成比例地保留剩餘權值與初始狀態之間距離的評分標準，會得到與保留「最大權值」的標準相同的性能。只要在執行回放時將權值的符號保持為初始權值的符號，就可以獲得和執行經典的 IMP 方法時獲得的相同的中獎網絡（請注意：該結論在 Frankle 於 2020 年發表的論文「The Early Phase of Neural Network Training 」中無法復現）。將權值屏蔽為 0 是很重要的。基於以上結論，作者猜想，利用一些具有先驗設定的掩模也可以成為一種訓練形式：它只是加速了權值變化的過程，而這些權值其實在優化過程中已經逐漸趨向於 0。有趣的是，使用應用於隨機初始化的網絡的 IMP 方法獲得的掩模（並且沒有進行任何額外的訓練）所能達到的性能，遠遠優於隨機的掩模，或者隨機初始化的網絡。所以，我們可以將其看做是一種「超級掩模」，它能夠編碼一種強歸納偏置。這個發現很讓人激動，也許我們可以根本不訓練網絡權值，只需要找到正確的掩模就能獲得很好的模型性能。Zhou 等人在論文「Deconstructing lottery tickets: Zeros, signs, and the supermask」中說明，我們甚至可以通過使掩模可微或使用類似於強化學習的損失函數學習性能優越的掩模。這種思路令人不禁想起 Gaier 和 Ha 於 2019 年發表的「Weight Agnostic Neural Networks」。其中，一個學習到的掩模可以被看做一種連接模式，它對解的正則性進行了編碼。通過對權值進行多次採樣，從而評價某個掩模，我們實際上使該掩模對於採樣的權值具有很強的魯棒性。
Frankle et al. (2020a) — Linear Mode Connectivity & the Lottery Ticket Hypothesis
Paper | Code
論文連結：https://arxiv.org/abs/1912.05671
代碼連結：https://github.com/facebookresearch/open_lth
當我們訓練一個神經網絡時，往往會對數據的批次進行隨機的排序。每個批次會被用來針對網絡參數估計損失的梯度。在完整地遍歷一次數據集（即一個 epoch）後，這些批次會被打亂重組，然後我們進行下一輪的迭代。我們可以將批次的序列視為噪聲的來源，我們可能會在此時將這些噪聲帶入到訓練過程中。由於這個原因，我們得到的最終權值可能差別很大。但是，理想狀態下，我們網絡的訓練過程應該對於這樣的噪聲十分魯棒。更正式地說，我們可以考慮某種權值初始化方式，此時我們使用兩種不同的批次順序進行訓練，從而得到兩組不同的訓練後的權值。Frankle 等人在論文「Linear Mode Connectivity and the Lottery Ticket Hypothesis」中提出了以下問題：如果我們在這兩種通過不同的數據順序得到的最終的權值設定之間平滑地插值（凸組合），那麼驗證/測試的準確率將會如何？
圖 9：線性模式連通性。
當我們在兩個最終的權值之間進行插值時，如果誤差沒有顯著增加，那麼我們則認為網絡是穩定的。此外，我們可以使用某種共享的數據順序對初始權值進行 k 輪迭代訓練，在之後根據兩種獨立的數據順序再分別進行訓練。那麼 k 設置為多少時會使網絡變得穩定呢？如圖 10 所示，這是 k=T 時的情況，但之前的情況呢？實驗結果證明，這與我們為了與中獎網絡相近的初始化而必須回放的迭代次數有關。
圖 10：不同實驗設定下的線性模式連通性。
圖 A：此時沒有中獎網絡，只需要觀察何時網絡對於使用不同數據順序時的插值變得穩定。對於 LeNet 而言，在初始時就已經達到了這種狀態。對於 ResNet-20 而言，只有在較後期的訓練時才會達到這種穩定性。這令人不禁想起了回放的迭代。
圖 B：根據迭代的幅度進行剪枝可以獲得穩定性。但是，只有同時使用回放到 k=0 時的學習率調整策略才能實現這種效果。
圖 C：圖中顯示了參數化的 3 個階段，我們通過剪掉越來越多的權值參數一步步經歷這 3 個階段（重點關注藍色曲線）：
階段 1：網絡嚴重過參數化，以致於隨機剪枝也能得到很好的效果。階段 2：隨著我們剪掉了越來越多的權值參數，只有 IMP 得到了效果不錯的穩定網絡。階段 3：在剩下的權值十分稀疏時，儘管 IMP 仍然會得到穩定的網絡，但是其它網絡的性能較中獎網絡就有較大差距了。該工作演示了如何利用中獎網絡解釋學習模式的性質。下面一篇論文則從更加細粒度的層面上分析了不同的學習階段。
Frankle et al. (2020b) — The Early Phase of Neural Network Training
論文連結：
https://openreview.net/forum?id=Hkl1iRNFwS
代碼連結：https://github.com/facebookresearch/open_lth
至此，我們已經看到，只有在訓練迭代次數較少時，我們才能同時獲得對於數據順序的魯棒性以及與中獎網絡相當的性能。接下來，一個更為普遍的問題是：這些與中獎網絡相近的網絡的初始化有多魯棒？為了不失去這種優異的模型性能，我們能對初始化進行多少調整和幹擾？它是如何隨 k 變化的？
為了研究產生魯棒性的條件，Frankle等人在 CIFAR-10 上使用 ResNet-20 進行了排列實驗。實驗方案如下：使用帶回放機制的 IMP 產生與中獎網絡性能相近的網絡。然後，對該網絡進行擾動並訓練直到收斂。實驗中用到的排列設定包括：
將權值的符號和/或幅值設為第 0 輪或第 k 輪迭代的狀態（見圖 11A），在網絡高度稀疏的情況下，使用任何的權值符號和幅值的排列（即初始化狀態）都會產生性能下降的情況。然而，在網絡較為稠密的情況下，通過 IMP 得到的網絡似乎對於符號的變化更加魯棒。當我們將權值回放到 k=2000 時的狀況時，也能得到性質相同的網絡。
將第 k 輪的權值與結構化的網絡子成分（見圖 11B）進行排列。此類方法包含交換全局的網絡權值（層與層之間）、局部的權值（層內），以及交換給定的卷積核內的權值。與中獎網絡性能相近的網絡並非對於所有的排列方案都體現出較高的魯棒性，其性能會下降到回放到 k=0 輪時的水平上。另一方面，在如圖 11C 所示的情況下，我們通過僅僅交換符號相同的權值限制排列的影響。此時，在任意的稀疏度下，網絡對於卷積核內的權值交換都是魯棒的。
向與中獎網絡性能相近的網絡中加入高斯噪聲（見圖 11D）：為了保證加入規模適當的噪聲，Frankle 等人計算了一個層級別的由特頂層的初始化分布產生的歸一化標準差。對於擾動後的彩票網絡的最終性能而言，有效的標準差的大小有很大的影響。擾動越大意味著性能越差。
圖 11E 展示了使用不同自監督損失預訓練的稠密/稀疏網絡：從 k=500 到 k=2000 之前的網絡性能並沒有太大的變化。這說明除了簡單的權值分布屬性和符號之外，還存在其它的影響因素。相反，在實際的訓練過程中出現了神奇的現象。因此，Frankle 等人提出了這樣的問題：早期的網絡調整是否依賴於條件標籤分布中的信息，或者無監督表示學習是否足夠？在使用隨機標籤時，進行較少輪次的訓練，與回放到第 0 輪的權值相比，確實會縮小網絡與中獎網絡之間的差距。但是，進行更長時間的預訓練最終會降低網絡的性能。最終，預訓練（非中獎網絡）的稀疏網絡並不足以克服「錯誤的」剪枝掩模帶來的損害。
圖 11：訓練初期的結果
總而言之，以上實驗說明了我們很難不使用回放機制，這是由於出現於中獎網絡相近的初始化情況似乎非常重要。自監督預訓練似乎提供了一種潛在的避免進行回放的方法。在下圖中，Frankle 等人總結了對於在 CIFAR-10 數據集上使用 ResNet-20 進行訓練的早期學習模式的理解：
圖 12：神經網絡訓練初期的情況
4
使用較少的計算量發現中獎網絡
儘管 Jonathan Frankle 最初的工作提供了一種經驗上的存在性證明，但是找出中獎網絡仍然是困難的，且計算開銷很大。IMP 需要對越來越稀疏的網絡重複地進行訓練，然而並不是所有研究人員都有條件開展這種研究。自然而然地，研究人員試圖在使用較少的計算量的情況下，找出中獎網絡。下面，我們將介紹近期提出的兩份試圖實現這一目標的工作：
You et al. (2020) — Drawing Early-Bird Tickets: Towards more efficient training of deep networks
論文連結：https://arxiv.org/abs/1909.11957
代碼連結：https://github.com/RICE-EIC/Early-Bird-Tickets
You 等人通過一種開銷較低的訓練方式找到了訓練早期的中獎網絡（因此該網絡被稱為「早鳥彩票」），這種訓練方式融合了早期停止、低精度與大學習率。他們認為，這是神經網絡優化過程的二階段特性造成的：
魯棒的第一階段：學習較低頻/大奇異值的成分。第二階段：學習較高頻/小奇異值的成分。通過只關注識別連接模式，可以在階段 1 中識別出「早鳥中獎網絡」。與標準 LTH 工作的主要區別在於，You 等人（https://arxiv.org/abs/1909.11957）基於批歸一化的縮放因子對整個卷積通道進行剪枝。此外，在單次訓練運行中迭代地執行剪枝。
通過實驗，作者觀察到，剪枝掩模在第一輪訓練中會發生顯著的改變（即「早出現」），但是似乎隨後會很快收斂（詳見圖 13 左側）。
圖 13：掩模的收斂與「早鳥」算法。
因此，他們斷定「早出現」的假設是正確的，並制定了合適的檢測算法：為了檢測「早出現」，他們提出了一種掩模距離度量，計算兩個連續的剪枝迭代的兩個剪枝掩模之間的 Hamming 距離。如果距離小於某個閾值，他們會停止剪枝。然後，可以直接對得到的「早鳥中獎網絡」重新進行訓練，從而恢復性能。
Tanaka et al. (2020) — Pruning neural networks without any data by iteratively conserving synaptic flow
論文連結：https://arxiv.org/abs/2006.05467
代碼連結：
https://github.com/ganguli-lab/Synaptic-Flow
儘管 You 等人
（https://arxiv.org/abs/1909.11957）
研究了是否有可能減少所需的計算量，但他們仍然需要使用數據訓練模型。然而，Tanaka 等人（https://arxiv.org/abs/2006.05467）研究了一個更激進的問題：在不進行訓練、沒有任何數據的情況下，我們能得到中獎網絡嗎？他們認為，在初始階段進行剪枝的最大挑戰是層坍塌（layer collapse）的問題——過早剪掉整個層會使架構變得不可訓練（因為梯度流被截斷了）。
我們不妨想想將一系列全連接層堆疊起來的多層感知機。通過在每一層中保留一個權值，我們可以避免發生層坍塌，這對應於理論上可以得到的最大壓縮比。通過不發生層坍塌現象的剪枝算法可以達到的不需要摺疊的壓縮水平稱為「臨界壓縮」。理想情況下，我們希望這二者相等。受到流網絡的啟發，Tanaka 等人（https://arxiv.org/abs/2006.05467）定義了種基於梯度的度量方法，並將其稱為「突觸顯著性」。從某種程度上說，這種度量與層級別的相關性傳播有關，它可以度量某種形式的貢獻。接著，論文作者從微觀神經元和宏觀網絡層面上證明了兩個顯著性守恆定律。作者說明，為了充分壓縮，基於梯度的方法將完全刪除大的層（如果對模型評估一次）。那麼，為什麼我們不會在 IMP 的訓練中遇到層坍塌問題呢？Tanaka 等人（https://arxiv.org/abs/2006.05467）表明，這是由於梯度下降導致層級別的守恆，以及小的學習率進行迭代式的剪枝。因此，任何想要獲得最大臨界壓縮的全局剪枝算法都必須保證兩點：（1）賦予層級別的守恆正的得分（2）在剪枝後迭代式地重新評估得分。
圖 14：模型性能與突觸流算法。
基於以上觀測結果，作者定義了一種迭代式的過程，它可以生成一個在初始化的網絡中維持突觸強度流的掩模（如圖 14 所示）。最重要的是，該過程完全與數據無關，僅僅需要隨機初始化。它們可以在 CIFAR-10/100 和 Tiny ImageNet 數據集上獲得比其它「在初始階段剪枝」的對比基線更好的性能。
5
在不同的數據集、優化器和域上，彩票網絡是否能泛化？
Morcos et al. (2019) — One ticket to win them all: Generalizing lottery ticket initializations across datasets and optimizers
論文連結：https://arxiv.org/abs/1906.02773
代碼連結：https://github.com/varungohil/Generalizing-Lottery-Tickets
有一個關鍵的問題是：與中獎網絡性能相近的網絡會不會過擬合呢？對於子網絡初始化問題而言，過擬合意味著什麼呢？通常而言，我們使用特定的數據集（例如，MNIST、CIFAR-10、ImageNet），特定的優化器（SGD、Adam、RMSprop），針對於特定的鄰域（視覺）和任務（物體分類）生成中獎網絡。當我們改變其中任意一項因素時，那麼之前的中獎網絡就不一定會仍然具有最佳的性能了。
因此，Morcos 等人
（https://arxiv.org/abs/1906.02773）
提出了以下問題：我們是否能找到某一個視覺數據集（如 ImageNet）上與中獎網絡性能相當的網絡，並將其遷移到另一個視覺數據集（如 CIFAR-100）上？此時，關鍵的問題在於，當我們在新數據集上對與中獎網絡性能相當的網絡進行訓練後，彩票網絡效應是否仍然成立。該過程如下所示：
在一個源數據集上使用 IMP 找到一個中獎網絡。在一個新的目標數據集上，通過訓練源數據集上獲得的中獎網絡至收斂，對其進行再次的評估。此時，你可能會問：輸入/輸出的不同尺寸有何影響呢？由於我們操作的是圖像，那麼在我們考慮的網絡中，第一層應該是一個卷積層，我們並不需要對第一個隱層做任何的變換。在網絡中。網絡從卷積層向全連接（FC）層過渡時，為了保證無論通道的尺寸（不同的數據集該參數不同）如何，FC 層的維度都可以正常工作，Mocos 等人（https://arxiv.org/abs/1906.02773）
使用了全局平均池化。最後的重點是，我們要在遷移過程中剔除掉中獎網絡的最後一層，轉而使用隨機初始化的層。這是因為，不同的數據集有不同類型的目標分類數。該過程與傳統的遷移學習並不相同，這是因為我們並沒有遷移表徵（訓練好的權值）而是遷移了初始化狀態以在獨立的數據集上找出來的剪枝掩模。Morco 等人在論文「One ticket to win them all: generalizing lottery ticket initializations across datasets and optimizers
」中得出了以下結論：
圖 A 與圖 B：將在一個小的源數據集上得到的 VGG-19 的中獎網絡遷移到 ImageNet 上取得了很好的效果，但是其性能要弱於直接在目標數據集（ImageNet）上得到的中獎網絡。另一方面，利用一個比目標數據集更大的數據集得到的中獎網絡，甚至要比使用目標數據集得到的中獎網絡有更好的性能。圖 C 與圖 D：在 ResNet-50 上的情況與在 VGG-19 上的情況大致相同。但是我們可以看到，在 ResNet-50 上，其性能在剪枝程度更小時就已經開始下降了（性能下降地更快）。
圖 15：在不同的數據集上遷移中獎網絡。最後，Morcos 等人也研究了使用某種優化器得到的中獎網絡是否能遷移到使用另一種優化器的場景下。對於 VGG-19 網絡而言，如果我們仔細對學習率進行調整，是可以實現這一目標的。同樣地，這也說明中獎網絡編碼了對於不同的數據和優化過程具有不變性的歸納偏置。
圖 16：在不同的優化器之間遷移中獎網絡。
以上結果說明，中獎網絡很有可能可以作為一種通用的歸納偏置。我們可以想像在一個非常大的數據集上，通過大量的計算，找到一個魯棒的與中獎網絡性能相當的網絡。此後，這種通用的中獎網絡可以靈活地作為大多數鬆散的領域相關任務的初始化器。因此，與對權值初始化進行元學習的想法相類似，中獎網絡可以在權值初始化空間中執行一種平攤搜索（amortized search）。
Yu et al. (2019) — Playing the lottery with rewards and multiple languages: lottery tickets in RL and NLP
論文連結：https://openreview.net/forum?id=S1xnXRVFwH
至此，我們已經研究了計算機視覺任務中的子網絡初始化問題。那麼，對於其它並不是基於交叉熵損失的領域又將如何呢？Yu 等人
（https://openreview.net/forum?id=S1xnXRVFwH）
將相關研究擴展到了語言模型（基於 LSTM 的模型和 Transformer 模型）以及強化學習（「演員-評論家」方法）的環境中。這與之前視覺領域的工作有以下不同之處：（1）除了卷積核和 FC 層之外，我們還需要剪掉其它類型的層（循環層、嵌入層、注意力模塊）。（2）我們在差異很大的損失平面上進行訓練（例如，非靜態的演員-評論家損失）。（3）強化學習網絡通常比大型視覺網絡具有的參數少得多（特別是對於連續控制而言），這可能使其更難在高度稀疏的情況下進行剪枝。
圖 17：語言模型和強化學習領域的中獎網絡。
簡而言之，對於語言和強化學習任務來說，存在顯著優於隨機子網絡的稀疏初始化方法。最有趣的是，作者發現，這種方法可以在保持良好性能的前提下，剪掉 Transformer 模型 2/3 的權值。後期的回放和迭代式剪枝同樣非常關鍵。此外，嵌入層似乎過參數化了。因此，它們主要使用了 IMP。另一方面，對於強化學習任務來說，對於所有作者考慮的遊戲而言，性能良好的剪枝程度有很大差異。這表明，對於某些任務而言，標準的基於 CNN 的演員-評論家網絡擁有的參數過多。這很可能是由許多遊戲組成的強化學習對比基準測試的特性，這些遊戲都是在相同的架構設置下學習的。
6
開放性的研究問題
對於優化、初始化、表達能力、遷移能力、稀疏化/過參數化的作用等研究課題而言，彩票假說開啟了許多不同的研究視角。目前，令人激動的是，還有很多問題有待解決，例如：
能夠找到中獎網絡的高效初始化方案應該是怎樣的？元學習是否可以在可計算的條件下找到這樣的彩票網絡？是否可以形式化定義能夠利用中獎網絡的優化算法？連通性和權值初始化的影響是否能夠解耦？我們是否可以將找到中獎網絡看做一種歸納偏置？使用一半訓練數據預訓練的權值進行初始化的網絡，與使用完整的數據集訓練的最終網絡有泛化能力的差距（https://arxiv.org/abs/1910.08475）。換句話說，使用數據的子集進行預訓練，比從隨機初始化狀態開始訓練的網絡性能更差。中獎彩票網絡是否能解決這種熱啟動問題？沿著Morcos 等人在論文「One ticket to win them all: generalizing lottery ticket initializations across datasets and optimizers」中的思路，可以對該問題進行很好的擴展。不同領域（視覺、語言、強化學習）和不同任務（分類、回歸等）上的中獎網絡有何不同？這些差異是損失平面的性質嗎？我們能否直接從它們的掩模中提取出相應的規律？總而言之，有待探究的問題還很多，還有很多的中獎彩票網絡有待發掘。
via:https://towardsdatascience.com/the-lottery-ticket-hypothesis-a-survey-d1f0f62f8884