2019-05-14

Raspberry Pi対応ロボットAlphabot2をC++から動かす

Robotics

Raspberry Piから制御できるロボットであるAlphabot2を手に入れたので，組み立ててC++から動かしてみる．

f:id:noconocolib:20190514020108j:plain — 組み立ててみるとこんな感じ

f:id:noconocolib:20190514020402j:plain — 電源を入れるとLEDが光る

f:id:noconocolib:20190514020456p:plain — 電池で動く

最初ニッケル水素電池を挿して動かそうとしたが稼働しなかった（電圧不足）．リチウム電池に変えたらちゃんと動いた．

また，このAlphabot2はmicro USBポートから充電できるので，充電池を挿してあげると何回も使えて良さそう．

C++からwiringPiを使ってラズパイのGPIOに信号を送ってみる． WiringPiのPWM出力用の関数を使って，サーボ制御のためのPWM信号を出力する．

wiringpi.com

#include <wiringPi.h>
#include <stdio.h>

int RIGHT_FORWARD = 29;
int LEFT_FORWARD = 23;
int main(){
    wiringPiSetup();
    pinMode(LED,OUTPUT);

    while (1){
        digitalWrite(RIGHT_FORWARD,HIGH);
    digitalWrite(LEFT_FORWARD,HIGH);    

    delay(1000);

    digitalWrite(RIGHT_FORWARD, LOW);
    digitalWrite(LEFT_FORWARD, LOW);

    delay(1000);
    }
}

コンパイル

$ g++ test.cc -lwiringPi -lcrypto -I<path to wiringPi> -lpthread -lcrypt -lrt

上記のようなコードをラズパイ上で実行することで，きちんとホイールが回転するか確認できる．

これにEdge TPUを積んだりすると面白そう．

2019-05-01

ベイズ推論の概要（パラメータの事後分布と予測分布）

Bayes' theorem

ベイズ学習の基本であるパラメータの事後分布および未観測データの予測分布の計算についての概要．

一般的に，機械学習モデルのもつパラメータをデータから決定することを学習と呼ぶ．ベイズ推論の枠組みでは，パラメータも何らかの不確実性を持っているような確率変数として扱う．この不確実性を持つパラメータの事後分布をデータの観測によって求めることが学習にあたる．

また，このようにして得られたモデルのパラメータに基づいて，未観測データに対する推論を行う際も，予測分布を確率推論を用いて求める．

パラメータの事後分布

訓練データ集合を $D$ とする．ベイズ学習では同時分布 $D, \theta$ について考えることで，データを表現するようなモデルを構築する．

$p(D, \theta) = p(D|\theta)p(\theta)$

$\theta$ はモデルに含まれる未知のパラメータであり，観測されていないものとする．パラメータ $\theta$ に関する事前の不確実性は事前分布 $p(\theta)$ を与えることでモデルに反映させることができる．

また， $p(D|\theta)$ はあるパラメータ $\theta$ からどのようにしてデータ $D$ が発生するのかを記述している．この $p(D|\theta)$ をパラメータ $\theta$ についての尤度関数と呼ぶ．

データ $D$ を観測したあとでは，パラメータの不確実性はベイズの定理を用いて以下のように更新される：

$p(\theta|D) = p(D|\theta)p(\theta) / p(D)$

この条件付き分布 $p(\theta|D)$ の計算がベイズ学習における学習にあたる．

予測分布

学習された分布を用いて，未観測のデータ $x^{*}$ に対する予測分布 $p(x^{*}|D)$ を計算したい．データ $D$ ，未知データ $x^{*}$ ，パラメータ $\theta$ に関する同時分布は，

$p(D, x^{*}, \theta) = p(D|\theta)p(x^{*}|\theta)p(\theta)$

となる．現在，データ $D$ のみが手元にあるとすると，残りの変数の事後分布は，

$p(x^{*}, \theta|D) = \frac{p(D, x^{*}, \theta)}{p(D)}$

$= \frac{p(D|\theta)p(x^{*}|\theta)p(\theta)}{p(D)}$

$= p(x^{*}|\theta)p(\theta|D)$

上記の式においてパラメータ $\theta$ を積分除去すると，

$p(x^{*}|D) = \int p(x^{*}|\theta)p(\theta|D)d\theta$

となり，求めたい予測分布が得られる．

2019-03-17

Edge TPU USB Acceleratorでモデルの再学習を試してみた

Edge TPU

Edge TPUを用いて，自作データセットによるClassifierの再学習（転移学習）を試してみた．

f:id:noconocolib:20190317161501j:plain f:id:noconocolib:20190317161650j:plain

Edge TPUでは，サーバで分類モデルを再学習する代わりに，ImprintingEngine APIを使用してEdge TPU上で転移学習を実行することができる．

Edge TPUのImprintingEngine APIはCVPR2018で提案されたLow-shot learning with imprinted weights [1]を用いて転移学習を実現する．この手法は，再学習の際にbackwardが必要ないため，Edge TPU上で高速に再学習を実行することが出来る．

Low-shot learning with imprinted weights

Edge TPU APIのインストール

$  wget http://storage.googleapis.com/cloud-iot-edge-pretrained-models/edgetpu_api.tar.gz
$ tar xzf edgetpu_api.tar.gz
$ cd python-tflite-source
$ bash ./install.sh

Feature extractorのダウンロード

特徴抽出を行うためのpretrained modelをダウンロードする．

$ wget http://storage.googleapis.com/cloud-iot-edge-pretrained-models/canned_models/mobilenet_v1_1.0_224_quant_embedding_extractor_edgetpu.tflite

データセットの準備

今回はハムスターとモルモットを分類してみる．

f:id:noconocolib:20190317152609p:plain — 参考画像．左：モルモット，右：ハムスター

以下のようなディレクトリ構造で画像を保存しておく．

サブディレクトリ一つが一つの分類クラスに対応する．

cavy_hamster/
├── cavy
│   ├── 0000006.jpg
│   ├── 000001.jpg
│   ├── 000002.jpg
│   ├── 000003.jpg
│   ├── 000004.jpg
│   ├── 000005.jpg
└── hamster
    ├── 000001.jpg
    ├── 000002.jpg
    ├── 000003.jpg
    ├── 000004.jpg
    ├── 000005.jpg

今回は，各クラスで20枚ずつ画像を用意した．

学習の実行

Edge TPU USB AcceleratorをUSB接続した状態で以下を実行する．

$ python3 demo/classification_transfer_learning.py --extractor mobilenet_v1_1.0_224_quant_embedding_extractor_edgetpu.tflite --data /cavy_hamster --output cavy_model.tflite --test_ratio 0.95

extractor: Edge TPU用にコンパイルした特徴抽出モデル
data: 用意したデータセット
output: Edge TPUで転移学習した結果のモデルの保存先
test_ratio: テストに用いる画像の割合

学習結果

$ python3 demo/classification_transfer_learning.py --extractor mobilenet_v1_1.0_224_quant_embedding_extractor_edgetpu.tflite --data /cavy_hamster --output cavy_model.tflite --test_ratio 0.95

----------------------      Args    ----------------------
Embedding extractor : .//mobilenet_v1_1.0_224_quant_embedding_extractor_edgetpu.tflite
Data set : .//cavy_hamster
Output path : .//cavy_model.tflite
Ratio of test images: 95%
---------------      Parsing data set    -----------------
Dataset path: .//cavy_hamster
Image list successfully parsed! Category Num =  2
W third_party/darwinn/driver/package_registry.cc:65] Minimum runtime version required by package (5) is lower than expected (10).
---------------- Processing training data ----------------
This process may take more than 30 seconds.
Processing category: cavy
Processing category: hamster
----------------      Start training     -----------------
W third_party/darwinn/driver/package_registry.cc:65] Minimum runtime version required by package (5) is lower than expected (10).
----------------     Training finished!  -----------------
Model saved as :  .//cavy_model.tflite
Labels file saved as : .//cavy_model.txt
------------------   Start evaluating   ------------------
W third_party/darwinn/driver/package_registry.cc:65] Minimum runtime version required by package (5) is lower than expected (10).
Evaluating category [ cavy ]
Evaluating category [ hamster ]
----------------     Evaluation result   -----------------
Top 1 : 86%
Top 2 : 100%
Top 3 : 100%
Top 4 : 100%
Top 5 : 100%

再学習後には，以下が出力として得られる．

cavy_model.tflite: 再学習後モデル
cavy_model.txt: ラベルファイル

ラベルファイルは以下のフォーマットで保存されている．

$ cat cavy_model.txt 
0  cavy
1  hamster

再学習したモデルを試す

先程学習したモデルをロードして，新しい入力画像に対して分類を行ってみる．

$ python3 demo/classify_image.py --model ./cavy_model.tflite --label ./cavy_model.txt --image test.jpg 

---------------------------
cavy
Score :  0.71953125
---------------------------
hamster
Score :  0.28046875

参考

[1] Qi, Hang, Matthew Brown, and David G. Lowe. "Low-shot learning with imprinted weights." Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2018.

2019-03-13

機械学習における正則化

一般的に教師あり学習モデルは，任意の損失関数に対してデータの「当てはまり具合」を最適化するように関数 $f(x)$ を選択する．

しかし，この関数 $f(x)$ が与えられたデータに対してあまりに複雑すぎると，今現在手元にある学習データのみに適合してしまい，未知のデータに弱くなってしまう過学習(over fitting)を引き起こしてしまう．過学習は，モデルが複雑な場合に訓練誤差と汎化誤差の間に大きな差が生じてしまうことに起因する．

正則化

過学習を避ける方法として，より単純なモデルを選ぶといったモデルの選択の他に，正則化(regularization)が存在する．

ここで，モデルの選択も正則化も，データにふさわしい適切な複雑さの関数を選択するという意味では本質的には同じと捉えられる．

正則化は，モデルの訓練誤差を最小化する際，そのモデルの「複雑」さに対する罰則を加えて最小化を行う．この「複雑さ」を定義する関数を正則化関数(regularization function)と呼ぶ．正則化関数を $R(f)$ とすると，一般的な正則化学習法は，

$\min_{f\in{F}} \sum^{n}_{i=1} l(y_{i}, f(x_{i})) + \lambda R(f)$

ここで $\lambda > 0$ は正則化の強さを調整するパラメータ．上式は，データへの当てはまり具合を表す第一項とモデルの複雑さへの罰則を表す第二項から成り立っている．この罰則項の働きによってモデルの過学習を抑えることができる．

線形モデル $f(x) = \beta^{T}x$ について，正則化項 $R(f) = R(\beta)$ としたとき，以下のような正則化関数がよく用いられる．

リッジ正則化 [1]：

$R(\beta) = ||\beta||^{2}_{2} := \sum^{p}_{j=1} \beta^{2}_{j}$

L1正則化 [2]：

$R(\beta) = ||\beta||_{1} := \sum^{p}_{j=1} |\beta_{j}|$

ブリッジ正則化 [3]：ある $\gamma > 0$ を用いて，

$R(\beta) = ||\beta||^{\gamma}_{\gamma} := \sum^{p}_{j=1} |b_{j}|^{\gamma}$

エラスティックネット正則化 [4]：ある $\theta \in [0, 1$ ]を用いて，

$R(\beta) = \theta ||\beta||_{1} + (1 - \theta) ||\beta||^{2}_{2}$

SCAD (smoothly clipped absolute deviation) [5]：ある $\lambda > 0$ と $a > 1$ を用いて，

$R(\beta) =$

$\sum^{p}_{j=1} \lambda |\beta_{j}| \ \ (|\beta_{j}| \leq \lambda)$

$\sum^{p}_{j=1} - \frac{|\beta_{j}|^{2} - 2a \lambda |\beta_{j}| + \lambda^{2}}{2(a - 1)}$

$\sum^{p}_{j=1} \frac{(a+1) \lambda^{2}}{2}$

上記から，ブリッジ正則化はL1正則化とリッジ正則化の一般化であることがわかる（ $\gamma = 1$ のときL1正則化， $\gamma = 2$ のときリッジ正則化）．また，SCAD正則化は非凸関数であるが， $\beta_{j} \to \infty$ で勾配が0になるため推定量にバイアスが乗りにくい．

最も単純なモデルである線形モデルであったとしても，次元が高い場合は自由度が高くなり，過学習を起こす可能性が存在してしまうため，上記のような正則化を用いることで過学習をを回避することができる．

f:id:noconocolib:20190312181943p:plain — 各正則化項のプロット

スパース正則化としてのL1正則化

L1正則化は，学習結果 $\beta$ をスパースにさせやすいという性質を持っている．ここで学習結果 $\beta$ がスパースであるとは， $\beta$ の多くの成分が0であるという意味．

これは，予測に必要のない無駄な特徴量を切り捨てて，特徴選択を行っているとみなせる．

古くから，そうした特徴選択を実現する手法として赤池情報量基準(Akaike information criterion, AIC)が用いられてきた．例えば回帰において，ノイズが分散が $\sigma^{2}$ のガウス分布に従っているとき， $l(y, f) = -\log (\frac{1}{\sqrt{2\pi \sigma^{2}}} \exp (- \frac{(y - f)^{2}}{2\sigma^{2}}))$ であるような設定を考える．このとき，赤池情報量基準に従った特徴選択は，

$\min_{\beta \in \mathbb{R}^{p}} 2 \sum^{n}_{i=1} l(y_{i}, x_{i}^{T} \beta) + 2 ||\beta||_{0}$

ここで，p $||\beta||_{0}$ は $\beta$ の非ゼロ要素の数で， $L_0$ ノルムと呼ばれる． $||\beta||_{0}$ を訓練誤差に足すのは，汎化誤差と訓練誤差の差を補うためであり，特徴量の数を罰則として訓練誤差に足すことで，学習結果をスパースにできる．より多くの特徴量を用いることは，それだけ複雑な関数を用いることに等しくなり，現在手元にある訓練データに当てはまりやすく，訓練誤差と汎化誤差の乖離が大きくなってしまう．AICはこのような乖離を補正するためには $2||\beta||_{0}$ を足せば良いと主張している．

$p$ がサンプル数より十分小さいとき，

$\frac{1}{n} E_{x_{i}, y_{i}} s\sum^{n}_{i+1} l(y_{i}, x_{i}^{T} ||\beta||_{0})$

$= E_{x_{i}, y_{i}} (E_{X, Y} (2l(Y, X^{T} \beta) ))+ O(\frac{1}{n^{2}})$

となる．左辺は目的関数の訓練データの出方に対する期待値，右辺の第一項は汎化誤差の期待値，第二項はサンプルサイズ $n$ が増えるに連れて消えていく項になる．

AICは汎化誤差の不偏推定量であり，AICを最小化する推定量は過学習を避けて正しく汎化誤差を小さくすることができる．しかし，次元 $p$ が大きい場合，AICの最小化は組み合わせ最適化問題となり，NP困難であることが知られている．

そこで， $L_0$ ノルムの代わりに $L1$ ノルムという凸関数を用いるというのが $L1$ 正則化の発想．実際， $L1$ ノルムは $L_0$ ノルムを下から抑える最大の凸関数になっており，最適化の際に非常に都合が良い．

また，L1正則化を用いた線形回帰手法をLassoと呼ぶ．

L1正則化のようにスパースな学習結果を導く正則化をスパース正則化という．

スパース正則化

スパース正則化は，高次元な学習問題において非常に強力な手法である．ここで，スパース性をより広く，ある種の低次元性と捉えると，他にも様々なスパース正則化が考えられる．

グループ正則化

特徴量がいくつかのグループに分かれていると仮定する．グループ正則化は，同じグループに属する特徴量をまとめて一つの特徴量のように扱うスパース正則化である．グループをそれぞれインデックス集合 $g\subseteq \{ 1,\dots,p\} (k=1,\dots,M)$ とする．インデックス集合 $g$ に対する $\beta\in\mathbb{R}^{p}$ の部分ベクトルを $\beta_{g}$ とすると，グループ正則化は以下で表される．

$||\beta||_{G} = \sum^{M}_{k=1} ||\beta_{gk}||_{2}$

一般化連結正則化

一般連結正則化は，あるグラフに関して隣接した変数は同じ値になるようにする正則化である．グラフ $G = (V, E)$ について，一般化連結正則化は，

$||\beta||_{Fused} = \sum_{(i, j)\in{E}} |\beta_{i} - \beta_{j}|$

として与えられる．

トレースノルム正則化

トレースノルム正則化は，低ランク行列を学習したい場合に用いられる． $\beta$ を並び替えた行列 $B$ を考え，その $k$ 番目の特異値を $\sigma_{k} (B) \geq 0$ と表すと，トレースノルム正則化は，

$||B||_{tr} = \sum^{\min \{q, r\}}_{k=1} \sigma_{j} (B)$

となる．これは特異値ベクトルへの $L1$ 正則化とみなせるので，スパースな特異値を持つ行列，すなわち低ランクな行列が学習されることになる．

正則化関数の組み合わせ

以上のように，正則化関数には多くの例が存在する．これらの正則化関数は，単独で用いるだけでなく，複合して適用することもできる．

正則化関数 $h_{1},\dots,h_{K}$ の組み合わせ方には，例えば以下のような方法がある．

和型：

$\hat{h} (\beta) = \sum^{K}_{k=1} h_{k} (\beta)$

畳み込み型

$\underline{h} (\beta) = \inf \sum^{K}_{k=1} h_{k} (\beta_{k}) =: (h_{1} * \cdots * h_{K})$

ちなみに，和型と畳込み型の２つの形式には，以下のような双対関係が成り立っている．

$(h_{1} + \dots +h_{K})^{*} (\beta) = (h^{*}_{1} \cdots h^{*}_{K}) (\beta) (\forall{\beta \in \mathbb{R}^{p}})$

ここで $f^{*}$ は凸関数 $f$ のルシャンドル変換．

参考文献

[1] Hoerl, Arthur E., and Robert W. Kennard. "Ridge regression: Biased estimation for nonorthogonal problems." Technometrics 12.1 (1970): 55-67.
[2] Tibshirani, Robert. "Regression shrinkage and selection via the lasso." Journal of the Royal Statistical Society: Series B (Methodological) 58.1 (1996): 267-288.
[3] Frank, LLdiko E., and Jerome H. Friedman. "A statistical view of some chemometrics regression tools." Technometrics 35.2 (1993): 109-135.
[4] Zou, Hui, and Trevor Hastie. "Regularization and variable selection via the elastic net." Journal of the royal statistical society: series B (statistical methodology) 67.2 (2005): 301-320.
[5] Fan, Jianqing, and Runze Li. "Variable selection via nonconcave penalized likelihood and its oracle properties." Journal of the American statistical Association 96.456 (2001): 1348-1360.

2019-03-01

tqdmでプログレスバーの隣に標準出力する

Python

いい感じのプログレスバーを作ってくれるPythonのライブラリであるtqdmで，プログレスバーの隣に標準出力を更新し続ける方法．

github.com

tqdm means "progress" in Arabic (taqadum, تقدّم) and is an abbreviation for "I love you so much" in Spanish (te quiero demasiado). Instantly make your loops show a smart progress meter - just wrap any iterable with tqdm(iterable), and you're done!

これは，tqdmで用意されているset_postfix関数を使うことで実現できる．

実装例

ループの外側をtqdmで包んで，そのなかでset_postfixを呼ぶ．
引数はOrderedDict

for epoch in range(n_epochs):
    with tqdm(self.train_loader, ncols=100) as pbar:
        for idx, (inputs, targets) in enumerate(pbar):
            optimizer.zero_grad()

            outputs = network(inputs)

            loss = self.criterion(outputs, targets)
            loss.backward()
            self.optimizer.step()

            pbar.set_postfix(OrderedDict(
                epoch="{:>10}".format(epoch),
                loss="{:.4f}".format(loss.item())))

出力例

f:id:noconocolib:20190301021249g:plain

いい感じに出力できてる．

2019-02-28

ニューラルネットワークの蒸留

Knowledge Distillation DeepLearning Model Compression

大規模で複雑な教師ネットワークの出力をもとに，より小さなネットワークを学習する蒸留について．

機械学習モデルの性能評価で重要なのは，学習データに対する正解率ではなく，学習データに含まれていないようなデータに対する汎化性能の方．パラメータの多いモデルは学習データにはよくフィットする一方で，未知のデータに対しては汎化性能が落ちてしまうというケースが多々ある．

よって，学習時は豊富なデータセットから複雑でパラメータ数の多いネットワークを学習し，推論用途により軽量なネットワークを学習し直すというアプローチが考えられる．また，軽量なネットワークは複雑なネットワークと比べてより高速に推論できるため，時間的計算量の観点からも良いと言える．

ニューラルネットワークの蒸留は以下の論文で提案．

Distilling the Knowledge in a Neural Network

Transfer LearningとKnowledge Distillationの違い

Transfer learningとknowledge distillationは，学習の形式はよく似ているが目的が異なる．

Transfer learningは，転移元のネットワークと転移先のネットワークは同程度に複雑で，転移元のネットワークの重みを活用して学習を効果的に進めようという狙いがある．

一方でknowledge distillationは，教師データよりも軽量な生徒モデルを学習することが目的．

Teacher-Student model

教師ネットワークは大規模なデータセットで学習された複雑なニューラルネット
生徒ネットワークは教師ネットワークの出力を利用して学習される軽量なニューラルネット

f:id:noconocolib:20190227224420j:plain

Temperature in Softmax Activation

ソフトマックス関数は，出力を確率の範囲に収めることができる．つまり，出力は全て0と1の間を取り，その合計は1になる．

$\frac{\exp z_i}{\sum_{j} \exp z_j}$

それに対して，温度付きソフトマックス関数は以下で与えられる．

$\frac{\exp z_i / T}{\sum_{j} \exp z_j / T}$

上式は，入力 $z$ を温度 $T$ で割っている形になる．

温度付きソフトマックスの出力例を以下に示す．

f:id:noconocolib:20190227225121p:plain

クラス7の確立が最も高いと仮定し，異なる温度 $T$ を設定した時の温度付きソフトマックス関数の出力をプロットしている．

図から，温度を高くすれば高くするほど，ソフトマックス関数の出力は滑らかになっていく（ニューラルネットが断定的な判断をしにくくなっている）．数字の例を使うと，0〜9の中だったら7に見えるけど1にも見えるといった反応に近くなる．

つまり，高い温度を用いた温度付きソフトマックス関数は，クラスAとクラスBがどれだけ似ているかといった情報を定量的に扱っているとみなせる．論文では，このような反応をdark knowledgeと呼んでいる．

Knowledge distillationの主なアイディアは，教師ネットワークの持つdark knowledgeを抽出して少ないパラメータの生徒ネットワークを効率的に学習させるという点にある．

Teacher-Student training

生徒ネットワークの学習では，一般的なsoftmax関数によるhard targetに加えて，教師ネットワークの出力を温度付きsoftmax関数に通したsoft targetを用いて学習を行う．

この過程を踏むことで，教師ネットワークのdark knowledgeの抽出を狙う．

最後に，knowledge distillationは，

より軽量なモデルを使える
元々の大規模なネットワークよりも良い汎化性能が見込める
大規模なデータで学習された教師モデルがあれば，生徒モデルの学習時には少ないデータしかなくても学習可能

といった利点を持つとされている．

References

Hinton, Geoffrey, Oriol Vinyals, and Jeff Dean. "Distilling the knowledge in a neural network." arXiv preprint arXiv:1503.02531 (2015).

2019-02-27

SNIP: Single-Shot Network Pruning Based Oo Connection Sensitivity

ICLR Model Compression DeepLearning

ICLR2019採択論文"SNIP: Single-Shot Network Pruning Based Oo Connection Sensitivity"をレビュー．

元論文はこちら:

openreview.net

パラメータ数の多い畳み込みニューラルネットワークを，分類精度をほとんど落とさずに大幅にスパース化するnetwork pruningについての研究．

Abstract

network pruningは，与えられた巨大なニューラルネットワークを，精度を維持したまま小規模化することが目的．

既存のnetwork pruningの手法は，再学習のプロセスや追加のハイパーパラメータが必要など，pruningそのものが高コストになってしまうものが多い．

これを受けて，学習前にデータに基づいてネットワークの接続の重要度を識別するnetwork pruningの手法を提案．

提案手法は以下の特徴を満たす．

Simplicity: ネットワークを学習前に一度だけpruningするだけでよく，事前の学習や面倒なpruningのためのスケジューリングは必要ない．
Versatility: 提案する構造的に重要な接続を発見する指標は，ネットワークアーキテクチャによらず汎用的に適用できる
Interpretability: 提案手法は，データのミニバッチを用いてsingle-shotで重要な接続を発見できる

つまり，提案手法は既存のnetwork pruningの手法とは異なり，学習前からネットワークのスパース化を達成できる．

Neural Network Pruning

Neural network pruningの研究背景には，多くのネットワークはタスクに対してパラメータ過多であり，より小さなネットワークで同様の精度を達成できるはずであるという仮定に基づいている．

与えられたデータセットを $D = {x_{i}, y_{i}}^{n}_{i=1}$ ，求められるsparsity levelを $\kappa$ とする．

neural network pruningは以下の最適化問題を解くことになる．

$\min_{w} L(w; D) = \min_{w} \frac{1}{n} \sum^{n}_{i=1} l(w; (x_{i}, y_{i})),$

$s.t. w\in{\mathbb{R}^m}, |w|_0 \leq \kappa$

$l(\cdot)$ はcross-entropyのような一般的な損失関数， $w$ はネットワークのパラメータ集合， $m$ はパラメータ数， $|\cdot|=0$ は $L_0$ ノルム．

重要度ベースのpruning手法では，冗長なパラメータや接続を重要度に基づいて削除することでネットワークの軽量化を実現する．こうした手法では，パラメータや接続の重要度を測る指標が非常に重要になる．

よく用いられるものとしては，重みパラメータの絶対値が閾値以下のものを重要でないと扱うものや，高いHessianを持つ重みの重要度が高いとする指標がある．

$s_{j} = \begin{cases} |w_{j}|,\ for\ magnitude\ based \ \frac{w\_{j}^{2}H_{jj}}{2}\ or\ \frac{w_{j}^{2}}{2H^{-1}_{jj}},\ for\ Hessian\ based \end{cases}$