Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Convolutionの数理とアルゴリズム

 Convolutionの数理とアルゴリズム

Deep Learning Acceleration 勉強会資料

Koichi Nakamura

September 03, 2017
Tweet

More Decks by Koichi Nakamura

Other Decks in Technology

Transcript

  1. Convolutional Neural Network • Convolutional Neural Network (CNN)はDeep Neural Networkの主要なアーキテク

    チャの一つ 画像: http://www.wildml.com/2015/11/understanding-convolutional-neural-networks-for-nlp/
  2. 代表的なアルゴリズム 1. Direct: 定義通り 2. im2col, col2im: 行列乗算(GEMM)に帰着 3. 高速畳み込みアルゴリズム

    • FFT • Winograd • など • テンソルのレイアウトや 具体的な実装方法も考えると 多数の選択肢がある • DIRECT • IMPLICIT_GEMM • IMPLICIT_PRECOMP_GEM M • GEMM • FFT • FFT_TILING • WINOGRAD • WINOGRAD_NONFUSED 例: cuDNN v7で実装されているForward propagation http://docs.nvidia.com/deeplearning/sdk/pdf/cuDNN-Library- User-Guide.pdf, P18
  3. トレードオフ • 場面によっても最適なアルゴリズムが変わる • 学習時: • バッチサイズ大きめ • Input Dataは固定

    • Weightは頻繁に更新 • 推論時: • バッチサイズ小さめ(1とか) • Input Dataは毎回変わる • Weightは固定 入口側 • inputサイズ大きめ • チャンネル少なめ 出口側 • inputサイズ小さい • チャンネル多め 同じConvolutionでも層によって特徴が異なる(resnetの場合) https://wiseodd.github.io/techblog/2016/10/13/residual-net/
  4. 本日の内容 • 下記4種のアルゴリズムについて数学的な所の解説をします 1. Direct 2. Im2col 3. FFT 4.

    Winograd • Forward Propagationについてのみ解説します • Convolution層のbackpropagationもconvolution計算が主になるので大体同じ
  5. Direct Algorithm: 定義通りの計算 O[:, :, :, :] = 0 for

    n = 0..N-1 for y = 0..H-1 for x = 0..W-1 for cout = 0..Cout-1 for fy = 0..FH-1 for fx = 0..FW-1 for cin = 0..Cin-1 O[n, y, x, cout] += I[n, y+fy, x+fx, cin] * W[cout, cin, fy, fx] O[n, y, x, cout] += b[cout] , , , = ෍ =0 −1 ෍ =0 −1 ෍ =0 −1 , + , + , [ , , , ] + [ ]
  6. 計算量 • 入力サイズ(padding前): • 出力サイズ: • Weightサイズ: • 乗算回数: •

    加算回数: F + O[:, :, :, :] = 0 for n = 0..N-1 for y = 0..H-1 for x = 0..W-1 for cout = 0..Cout-1 for fy = 0..FH-1 for fx = 0..FW-1 for cin = 0..Cin-1 O[n, y, x, cout] += I[n, y+fy, x+fx, cin] * W[cout, cin, fy, fx] O[n, y, x, cout] += b[cout]
  7. 計算例 N H W FH FW Cin Cout InSize OutSize

    Weight MAC Ops 1 56 56 3 3 64 64 201K 201K 37K 231M 1 28 28 3 3 128 128 100K 100K 147K 231M 1 14 14 3 3 256 256 50K 50K 590K 231M 1 7 7 3 3 512 512 25K 25K 2M 231M 256 56 56 3 3 64 64 51M 51M 37K 59,190M 256 28 28 3 3 128 128 26M 26M 147K 59,190M 256 14 14 3 3 256 256 13M 13M 590K 59,190M 256 7 7 3 3 512 512 6M 6M 2M 59,190M N Input Output InSize OutSize Weight MAC Ops 1 2048 1000 2K 1K 2M 4M 256 2048 1000 524K 256K 2M 1,049M Convolution層 (ResNetから持ってきた例) FC層 (ResNetから持ってきた例)
  8. 畳み込みと多項式乗算 • = 0 + 1 + 2 2 +

    3 3と = 0 + 1 + 2 2を掛けると = 0 0 + 0 1 + 1 0 + 0 2 + 1 1 + 2 0 2 + 1 2 + 2 1 + 3 0 3 + 2 2 + 3 1 4 + 3 2 5
  9. 畳み込みと多項式乗算 • = 0 + 1 + 2 2 +

    3 3と = 0 + 1 + 2 2を掛けると = 0 0 + 0 1 + 1 0 + 0 2 + 1 1 + 2 0 2 + 1 2 + 2 1 + 3 0 3 + 2 2 + 3 1 4 + 3 2 5 • これとinput: (0,0, 0 , 1 , 2 , 3 , 0,0)、weight: (2 , 1 , 0 )の畳み込みは等価 × × × Σ input weight output 0 0 0 1 2 3 0 0 2 1 0
  10. 畳み込みと多項式乗算 • = 0 + 1 + 2 2 +

    3 3と = 0 + 1 + 2 2を掛けると = 0 0 + 0 1 + 1 0 + 0 2 + 1 1 + 2 0 2 + 1 2 + 2 1 + 3 0 3 + 2 2 + 3 1 4 + 3 2 5 • これとinput: (0,0, 0 , 1 , 2 , 3 , 0,0)、weight: (2 , 1 , 0 )の畳み込みは等価 input weight output 0 0 0 1 2 3 0 0 × × × Σ 2 1 0
  11. 畳み込みと多項式乗算 • = 0 + 1 + 2 2 +

    3 3と = 0 + 1 + 2 2を掛けると = 0 0 + 0 1 + 1 0 + 0 2 + 1 1 + 2 0 2 + 1 2 + 2 1 + 3 0 3 + 2 2 + 3 1 4 + 3 2 5 • これとinput: (0,0, 0 , 1 , 2 , 3 , 0,0)、weight: (2 , 1 , 0 )の畳み込みは等価 input weight output 0 0 0 1 2 3 0 0 × × × Σ 2 1 0
  12. Discrete Convolution 有限列に対する1D discrete linear convolution 複素数列 = 0 ,

    1 , … , , = (0 , 1 , … , )のDiscrete Convolution ∗ を以下によって定める ∗ = ෍ += ( = 0, … , + ) 例: = 1,2,3 , = (1, −1)の時 ∗ = 1 ⋅ 1,1 ⋅ −1 + 2 ⋅ 1, 2 ⋅ −1 + 3 ⋅ 1, 3 ⋅ −1 = (1, 1, 1, −3)
  13. Coefficient Representation • 多項式を係数列で表現する 例 = 1 − − 22

    + 3 + 24のCoefficient Representationは (1, −1, −2, 1, 2)
  14. Point-Value Representation • 点と値の組で表現する • 点の取り方によって無数の表現がある 例 = 1 −

    − 22 + 3 + 24の = 0, 1, −1, 1 2 , − 1 2 に関する Point-Value Representationは (1, 1, 1,1/4, 1) Unisolvence定理 相異なる0 , 1 , … , に対して標本点 0 , 0 , … , ( , )が与 えられた時、 = 0, … , に対して = を満たす次以下の多項式は常に存在し、一意である
  15. Coefficient Representationでの積は大変 • Coefficient Representation (0, 1 , 2 ,

    3 ) と(0 , 1 , 2 ) の積は (0 0 , 0 1 + 1 0 , 0 2 + 1 1 + 2 0 , 1 2 + 2 1 + 3 0 , 2 2 + 3 1 , 3 2 ) • 次式と次式に対して( + 1)( + 1)回の掛け算 = 0 + 1 + 2 2 + 3 3, = 0 + 1 + 2 2 = 0 0 + 0 1 + 1 0 + 0 2 + 1 1 + 2 0 2 + 1 2 + 2 1 + 3 0 3 + 2 2 + 3 1 4 + 3 2 5
  16. Point-Value Representationでの積は簡単 • = 0 , 1 , 2 ,

    3 , 4 , 5 でのPoint-Value Representation (0 , 1 , 2 , 3 , 4 , 5 )と(0 , 1 , 2 , 3 , 4 , 5 ) • の積は (0 0 , 1 1 , 2 2 , 3 3 , 4 4 , 5 5 ) • 次式と次式に対して + + 1回の掛け算
  17. Point-Value Representationを用いた高速乗算法 Coefficient Representation Coefficient Representation Point-Value Representation Point-Value Representation

    Evaluation Interpolation Element-Wise Multiplication Convolution 表現間の変換を高速にできるならば、Direct Convolutionよりも高速になる (ここでの”高速”は演算回数という意味で)
  18. Coefficient Rep. → Point-Value Rep. • = 0 + 1

    + 2 2→ 0 , 1 , 2 , 3 = ( 0 , 1 , 2 , 3 ) Point-Value Representation Coefficient Representation Vandermonde Matrix
  19. Coefficient Rep. → Point-Value Rep. • = 0 + 1

    + 2 2→ 0 , 1 , 2 , 3 = ( 0 , 1 , 2 , 3 ) 表現長に対して(2)なので速くない
  20. CNN ConvolutionをFFTで行う流れ • Input, WeightをFFT • それぞれ • + −

    1 + − 1 • + − 1 + − 1 • 以上に増加 • (Real-Valued FFTを使うとこの半分) • Input, Weightのどちらかは Precomputeしておくことができる • 計算量 • FFT, IFFTは(? log ) のオーダー • Element-Wise Multiplicationは 4 + − 1 + − 1 Inverse FFT + 不要部分の除去 Padding + FFT
  21. Tiling • , は小さな値(3など)の事が多いので、メモリ使用量の増大が著しい • 例えば = = 56, =

    = 3の場合3 × 3が64 × 64 (2べきに切り上げる為)になるので455倍 • 入力側を適当にタイリングして、結合するもしくは重なる部分を足す(Overlap-Add 法) 例えば2x2のタイルずつに区切ってFFTで計算
  22. 別にPoint-Value Representationでなくても良い Coefficient Representation Coefficient Representation 何らかのRepresentation 何らかの Representation 何らかの速く計算できる

    線形変換 Element-Wise Multiplication Convolution • 最終的に辻褄が合えば何でも良い • 良い変換を頑張って探す 何らかの速く計算できる 線形変換
  23. winograd algorithm: F(2x2, 3x3) • 4x4のタイルから、3x3のカーネルで畳み込んで、2x2のタイルを作る操作を単位とす るアルゴリズム • 6x6タイル、3x3カーネルから4x4タイルを作るF(4x4, 3x3)や

    8x8タイル、3x3カーネルから6x6タイルを作るF(6x6, 3x3)など色々ある • 詳しくは→ https://arxiv.org/abs/1509.09308 及び https://github.com/andravin/wincnn
  24. • 定義通りにやると、出力1 pixel, 1 channel,の計算に • 3x3xCin = 9Cin回の乗算 •

    3x3xCin = 9Cin回の加算 • が必要。 • これが4 pixel, Cout channel分なので • 36CinxCout回の乗算 • 36CinxCout回の加算 • が必要
  25. F(2x2, 3x3)のアルゴリズム 1. 事前に、4x3変換行列を使ってをCoutxCinx4x4 テンソル′に変換しておく 2. 入力を4x4変換行列で4x4xCinテンソル′に変換する 3. ′と′の要素毎の積を取り、チャンネルに関して足し込む(4x4のタイルがCout個出来 る)

    4. 出来た4x4タイルを4x2変換行列で2x2タイルにする 計算量 ステップ2. 加減算32Cin回で可能 ステップ3. 4x4xCinxCout=16CinxCout回の乗算、 同じ回数の加算 ステップ4. 加減算36Cout回で可能
  26. 例: • = 1234, 1 = 7, 2 = 13,

    2 = 16とすると 1 = mod 1234, 7 = 2 2 = mod 1234, 13 = 12 3 = mod(1234, 16)=2 1 = 13 ⋅ 16 −1 = 5−1 = 3 (mod 7) 2 = 7 ⋅ 16 −1 = 8−1 = 5 (mod 13) 3 = 7 ⋅ 13 −1 = 11 = 3 (mod 16) なので 1 1 13 ⋅ 16 + 2 2 7 ⋅ 16 + 3 3 7 ⋅ 13 = 8514 となり8514 = 1234 (mod 7 ⋅ 13 ⋅ 16)だから確かに成立。 modular inverseの計算はmaximaなどの 数式処理系を使えば楽
  27. (2,3)の導出 • 今の定理は多項式環でも成立する。 • 例として先程やったconvolution , , , ∗ ,

    , = [ + + , + + ] に対応するwinograd algorithmを導いてみる。 • これは3 pixelのフィルタで2 pixel作り出すので(2,3)と呼ばれる 紹介した論文にあるこれ→ を導出してみる
  28. • = + + 2 + 3, = + +

    2と置く • ()の2, 3の項を見れば良いのだけど、これは5次で次数が高くて面倒だが = + + + 3と変形して ℎ() = + の部分のみを中国剰余定理で計算すれば良い • 1 = , 2 = − 1, 3 = + 1とおくと ℎ1 = mod(ℎ , ) = ℎ2 = mod(ℎ , − 1) = ( + )(1) ℎ3 = mod(ℎ , + 1) = − (−1) 1 = − 1 + 1 −1 = −1 (mod ) 2 = + 1 −1 = 1/2 (mod − 1) 3 = − 1 −1 = 1/2 (mod + 1) • 従って中国剰余定理より ℎ = ℎ1 1 − 1 + 1 + ℎ2 2 + 1 + ℎ3 3 − 1 = − − 1 + 1 + 1 2 + 1 + 1 + 1 2 − −1 − 1 (mod − 1 ( + 1)) • ℎ()は3次式だから両辺の3の係数を比べると ℎ = − − 1 + 1 + 1 2 + 1 + 1 + 1 2 − −1 − 1 + ( − 1)( + 1) という等式を得る
  29. • さて = + ℎ + 3()なので • 2の係数 (出力1つ目)は

    + 1 2 + 1 − 1 2 − −1 − = − + 1 2 + 1 − 1 2 − (−1) • 3の係数(出力の2つ目)は − + 1 2 + 1 + 1 2 − −1 + = 1 2 + 1 + 1 2 − −1 − − • 1 , (−1)に関する積は2式で共通だからこの右辺は4回の乗算で計算出来る • という事でhttps://arxiv.org/pdf/1509.09308.pdfの式(5)が導出出来た。(終わり) • 先程の“ = + + + 3と変形”の意味だけど、直感的に説明すると 右図の2回の畳み込みにおいて共通して参照されるのが, だから、 この部分とフィルタの積をどう工夫するかを考えれば良いという話。 • だから(3,3) (入力5 pixel,フィルタ3pixel)の場合には = + + + 2 + 4 みたいにして4 = − 2なんかを追加すると(2)に関する項が出てきて 同じような計算が出来る。 • この辺はVandermonde matrixを使うと楽に書けるとか、Cook-Toom Filterで 同じ物が出てくるとかそういう話はあるみたい
  30. まとめ • いくつかのConvolutionの計算法を紹介しました • Direct • Im2col • FFT •

    Winograd • それぞれトレードオフがあり、状況に応じて使い分けていく事が重要 • Deep Learningの文脈でFast convolution algorithmの研究は まだそんなに行われていないと思います • 計算代数や関数解析などの人達に是非Deep Learning分野に参入していただきたい