Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
Convolutionのアルゴリズム
Search
Koichi Nakamura
June 30, 2017
Technology
1
1.7k
Convolutionのアルゴリズム
Koichi Nakamura
June 30, 2017
Tweet
Share
More Decks by Koichi Nakamura
See All by Koichi Nakamura
エッジDLデバイスの選定において考慮すること ML@Loft
nineties
2
1.4k
Deep Learning推論を高速化するソフトウェア技術
nineties
9
8.2k
What is Actcast? / actcast-en
nineties
2
690
Actcast紹介資料 / actcast-ja
nineties
4
2.2k
Ideinの紹介 @ DLLab 推論ナイト
nineties
11
3.8k
Convolutionの数理とアルゴリズム
nineties
10
17k
Creating a language using only assembly language
nineties
54
48k
bootstrap
nineties
47
15k
Other Decks in Technology
See All in Technology
CyberAgent 生成AI Deep Dive with Amazon Web Services / genai-aws
cyberagentdevelopers
PRO
1
480
visionOSでの空間表現実装とImmersive Video表示について / ai-immersive-visionos
cyberagentdevelopers
PRO
1
110
マネジメント視点でのre:Invent参加 ~もしCEOがre:Inventに行ったら~
kojiasai
0
470
LeSSに潜む「隠れWF病」とその処方箋
lycorptech_jp
PRO
2
120
現地でMeet Upをやる場合の注意点〜反省点を添えて〜
shotashiratori
0
530
VPC間の接続方法を整理してみた #自治体クラウド勉強会
non97
1
850
バクラクにおける可観測性向上の取り組み
yuu26
3
420
顧客が本当に必要だったもの - パフォーマンス改善編 / Make what is needed
soudai
24
6.8k
グローバル展開を見据えたサービスにおける機械翻訳プラクティス / dp-ai-translating
cyberagentdevelopers
PRO
1
150
ガバメントクラウド単独利用方式におけるIaC活用
techniczna
3
270
「 SharePoint 難しい」ってよく聞くけど、そんなに言うなら8歳の息子に試してもらった
taichinakamura
1
620
よくわからんサービスについての問い合わせが来たときの強い味方 Amazon Q について
kazzpapa3
0
220
Featured
See All Featured
A Philosophy of Restraint
colly
203
16k
Building Better People: How to give real-time feedback that sticks.
wjessup
363
19k
What's in a price? How to price your products and services
michaelherold
243
12k
Speed Design
sergeychernyshev
24
570
Build your cross-platform service in a week with App Engine
jlugia
229
18k
Into the Great Unknown - MozCon
thekraken
31
1.5k
Fight the Zombie Pattern Library - RWD Summit 2016
marcelosomers
231
17k
Building Applications with DynamoDB
mza
90
6.1k
5 minutes of I Can Smell Your CMS
philhawksworth
202
19k
ReactJS: Keep Simple. Everything can be a component!
pedronauck
664
120k
Designing for Performance
lara
604
68k
Learning to Love Humans: Emotional Interface Design
aarron
272
40k
Transcript
Convolutionのアルゴリズム 中村晃一 (@9_ties) Idein Inc. 本資料はIdein Inc.で開催中の社内コンペ”3x3 Convolution Challenge”用に作成したものです。折角なので一部公開します。
目次 • 背景 • 2D Convolution • direct convolution algorithm
• im2col convolution algorithm • fast convolution algorithm • winograd convolution algorithm • FFTconvolution algorithm (まだ書いてない) • iterative convolution algorithm
背景 • Deep Neural NetworkにおいてConvolutionは利用頻度が非常に高いので 速くしたい • Convolution自体は画像処理分野や数式処理分野等で昔から研究されているが、Deep Learning分野ではフィルタサイズが小さく、チャンネルが非常に多いという特徴が あるのでこれまであまり使われていなかったアルゴリズムが実は強かったりする
• 例えばResNetだと1x1や3x3で チャンネル数が最大2048 引用: https://arxiv.org/abs/1512.03385のTable 1
2D Convolution
以下、簡単の為 stride=1, InputのHxW=OutputのHxWの場合で説明 • パラメータ • N: inputの枚数 • H,
W: input, outputの高さ、幅 • Cin: inputのチャンネル数 • Cout: outputのチャンネル数 • FH, FW: フィルター (カーネル)の高さ・幅 • データのサイズ • input (I): NxHxWxCin • output (O): NxHxWxCout • weight (W): CoutxCinxFHxFW (CinxFHxFWが Cout個) • bias (b): Cout
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] Direct Convolution Algorithm
im2col algorithm
im2col • Convolutionを1回の行列乗算で行うアルゴリズム。 Loweringとも呼ばれる。 • BLASのGEMM等、性能の良いライブラリを使う事が出来る • 多くの実装で使われている。ChainerのCPU版forwardもこれ。
• convolution 2Dを数式で書くと以下のようになる。但し、は CoutxFHxFWxCinの形でメモリに置いてあるとする。 • ここでNxHxWxFHxFWxCinのテンソル′を用意して、以下のようにコピー する • すると′との( ,
, )軸に関する内積(つまり行列乗算の形)になるので GEMM一回で計算出来る , , , = =0 −1 =0 −1 =0 −1 , + , + , [, , , ] + ′ , , , , , = [, + , + , ] , , , = =0 −1 =0 −1 =0 −1 ′ , , , , , [, , , ] + [] 内積の形
• 実装例 ′ , , , , , = [,
+ , + , ] , , , = =0 −1 =0 −1 =0 −1 ′ , , , , , [, , , ] + [] (np.tensordotは複数軸での内積計算を行う)
使用上の注意 • 再配置により要素数が + − 1 + − 1 →
となり、一時的な利用メモリが増加する • 3x3 convolutionだと9倍弱 • コピーのコストも掛かる
fast convolution algorithm
fast convolution algorithm • 乗算の回数が減る手法を”fast” convolution algorithmという • 定数倍の分があるので、実際に速くなるかは別の話 •
Winograd minimal filtering algorithmは乗算回数が最小である事が証 明されている • 雑に雰囲気を説明をすると • 例えば , , , の4数から + + + を計算するには、ナイーブにやると4回乗算が要る が( + )( + )とすれば1回の乗算で済む • このように上手く事前にやを変形しておくと演算回数を減らす事が出来る • ちゃんとした解説は後半に書いておく
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
• 定義通りにやると、出力1 pixel, 1 channel,の計算に • 3x3xCin = 9Cin回の乗算 •
3x3xCin = 9Cin回の加算 • が必要。 • これが4 pixel, Cout channel分なので • 36CinxCout回の乗算 • 36CinxCout回の加算 • が必要
F(2x2, 3x3)のアルゴリズム 1. 事前に、4x3変換行列を使ってをCoutxCinx4x4 テンソル′に変換しておく 2. 入力を4x4変換行列で4x4xCinテンソル′に変換する 3. ′と′の要素毎の積を取り、チャンネルに関して足し込む(4x4のタイルがCout個出来 る)
4. 出来た4x4タイルを4x2変換行列で2x2タイルにする 計算量 ステップ2. 加減算32Cin回で可能 ステップ3. 4x4xCinxCout=16CinxCout回の乗算、 同じ回数の加算 ステップ4. 加減算36Cout回で可能
比較 • Direct • 加算: 36CinxCout • 乗算: 36CinxCout •
Winograd • 加算: 16CinxCout + 32Cin+36Cout回 • 乗算: 16CinxCout • Cin, Coutが十分に大きければ、演算回数が半分以下に減少 • Deep Learningでは中間層でのチャンネル数が大きいのでこれを満た す
( × , × ) アルゴリズム • × タイルを計算するのに •
Direct Algorithmだと • 22 回の乗算・加算 • Winogradだと • + − 1 2 回の乗算・加算 • に比例する前処理コスト, Cout に比例する後処理コスト • Weightサイズは + − 1 2/2倍に増加 • 正方形じゃないタイルで考える事も出来るが、正方形の場合が演算回数は最小になる • レイアウトが変わるので他の要因で勝つ可能性も無くはない 演算回数 weightサイズ F(2x2, 3x3) x0.44 x1.78 F(3x3, 3x3) x0.31 x2.78 F(4x4, 3x3) x0.25 x4.00 F(5x5, 3x3) x0.21 x5.44 F(6x6, 3x3) x0.20 x7.11 3x3 convolutionの場合 タイルが大きいと、weightが巨大になりつらそう 前処理・後処理も単純な加減算ではなくなる
fast convolution algorithmの理論
Linear Convolutionと多項式乗算 • 4 pixelに3 pixelのフィルターを掛けて2 pixelつくる1D convolutionを考える • ∗
をconvolution演算とすると , , , ∗ , , = [ + + , + + ]
Linear Convolutionと多項式乗算 • 4 pixelに3 pixelのフィルターを掛けて2 pixelつくる1D convolutionを考える • ∗
をconvolution演算とすると , , , ∗ , , = [ + + , + + ] • ここで = + + 2 + 3, = + + 2とおくと = + + + + + 2 + + + 3 + + 4 + 5
Linear Convolutionと多項式乗算 • 4 pixelに3 pixelのフィルターを掛けて2 pixelつくる1D convolutionを考える • ∗
をconvolution演算とすると , , , ∗ , , = [ + + , + + ] • ここで = + + 2 + 3, = + + 2とおくと = + + + + + 2 + + + 3 + + 4 + 5 • となり、多項式の積の係数にConvolution演算が現れる
fast convolution algorithmの考え方 • 多項式の高速乗算アルゴリズムは昔から研究されている • 興味がある人は本棚のコンピュータ代数ハンドブックなどを読むと良い • winogradは中国剰余定理を使っている •
Cook-Toomは多項式補間法を使うらしい
中国剰余定理 • 一般的な定理とは別の形の物を使います を整数、1 , … , を互いに素な整数とした時、 = 1
⋯ と おくと = (/ ) (mod M) 但し = mod(, ), = −1 (mod )
例: • = 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などの 数式処理系を使えば楽
(2,3)の導出 • 今の定理は多項式環でも成立する。 • 例として先程やったconvolution , , , ∗ ,
, = [ + + , + + ] に対応するwinograd algorithmを導いてみる。 • これは3 pixelのフィルタで2 pixel作り出すので(2,3)と呼ばれる 紹介した論文にあるこれ→ を導出してみる
• = + + 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) という等式を得る
• さて = + ℎ + 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で 同じ物が出てくるとかそういう話はあるみたい
FFT は後で書いて追加するかも ただし、フィルタサイズの大きいConvolutionに強く3x3くらいでは役に立たない可能性が高い
Iterative convolution • 長いフィルタを分割して反復(もしくは最適的)にfast convolutionを行う方法 • 乗算回数は最小ではなくなるけど、空間計算量が減るとか、加算回数は減るとかの 効果がある • 多項式乗算におけるKaratsuba法とかこの類ですね
• フィルタサイズが3とかだと使いようが無いかな
Algorithmまとめ (3x3,stride=1,pad=1の場合) • Direct Algorithm • 加算: 約9 回 •
乗算: 9 回 • im2col Algorithm • 加算: 約9 回 • 乗算: 9 回 • GEMM一発でやるなら一時的に入力サイズの約9倍の領域が必要(複数回のGEMMに分割するという手もある) • Winograd Algorithm F(2x2, 3x3)の場合 • 加算: 約4 + 8 + 9 回 • 乗算: 4 回 • weightのサイズは16/9倍に増加 • FFT • 後で追加するかもしれないけど、フィルタサイズが小さいので役に立たない可能性が高い • Iterative Convolution • フィルタサイズが小さいので役に立たない可能性が高い