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
ノーコードデータ分析ツールで体験する時系列データ分析超入門
negi111111
0
420
Platform Engineering for Software Developers and Architects
syntasso
1
520
Introduction to Works of ML Engineer in LY Corporation
lycorp_recruit_jp
0
140
誰も全体を知らない ~ ロールの垣根を超えて引き上げる開発生産性 / Boosting Development Productivity Across Roles
kakehashi
1
230
BLADE: An Attempt to Automate Penetration Testing Using Autonomous AI Agents
bbrbbq
0
320
プロダクト活用度で見えた真実 ホリゾンタルSaaSでの顧客解像度の高め方
tadaken3
0
180
CDCL による厳密解法を採用した MILP ソルバー
imai448
3
140
OTelCol_TailSampling_and_SpanMetrics
gumamon
1
200
EventHub Startup CTO of the year 2024 ピッチ資料
eventhub
0
120
OCI Vault 概要
oracle4engineer
PRO
0
9.7k
安心してください、日本語使えますよ―Ubuntu日本語Remix提供休止に寄せて― 2024-11-17
nobutomurata
1
1k
『Firebase Dynamic Links終了に備える』 FlutterアプリでのAdjust導入とDeeplink最適化
techiro
0
130
Featured
See All Featured
Git: the NoSQL Database
bkeepers
PRO
427
64k
Reflections from 52 weeks, 52 projects
jeffersonlam
346
20k
The Success of Rails: Ensuring Growth for the Next 100 Years
eileencodes
44
6.8k
Fontdeck: Realign not Redesign
paulrobertlloyd
82
5.2k
The Cost Of JavaScript in 2023
addyosmani
45
6.8k
Mobile First: as difficult as doing things right
swwweet
222
8.9k
How to Create Impact in a Changing Tech Landscape [PerfNow 2023]
tammyeverts
47
2.1k
The Pragmatic Product Professional
lauravandoore
31
6.3k
Cheating the UX When There Is Nothing More to Optimize - PixelPioneers
stephaniewalter
280
13k
Docker and Python
trallard
40
3.1k
The MySQL Ecosystem @ GitHub 2015
samlambert
250
12k
GraphQLとの向き合い方2022年版
quramy
43
13k
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 • フィルタサイズが小さいので役に立たない可能性が高い