あざらしなので

備忘録と日常のこと

Winograd勉強メモ

忘れるからメモ

Winogradとは

畳み込み演算を高速に計算できる(かもしれない)アルゴリズム

論文↓
Fast Algorithms for Convolutional Neural Networks

Winograd F(2x2,3x3)

入力画像を4x4,出力画像を2x2,カーネルサイズを3x3のwinogradアルゴリズム
計算式は以下の通り

$Y=A^ T[[ GgG^ T ]⊙[B^ TdB]]A$

ここで
$A^ T = \begin{bmatrix} 1 & 1 & 1 & 0 \\\ 0 & 1 &-1 &-1 \end{bmatrix}$

$B^ T = \begin{bmatrix} 1 & 0 & -1 & 0 \\\ 0 & 1 & 1 &0 \\\ 0 & -1 & 1 & 0 \\\ 0 & 1 & 0 & -1 \end{bmatrix}$

$G = \begin{bmatrix} 1 & 0 & 0 \\\ 0.5 & 0.5 & 0.5 \\\ 0.5 & -0.5 & 0.5 \\\ 0 & 0 & 1 \end{bmatrix}$

$d$ は入力4x4, $g$ はweight，⦿は各要素の乗算．

入力チャンネルと出力チャンネルを加味すると以下のようになる．

ci:入力チャンネル
co:出力チャンネル

$Y_{co}= A^ T \Biggl\{\sum_{ci} \biggl[ [ Gg_{ci,co}G^ T ]⊙[B^ Td_{ci}B]\biggr] \Biggr\}A$

実装法

推論のconvにおいてどのように計算するのが良いか
基本として，
1. $[ GgG^ T ]$ はweightの計算なので事前に行う
2. $G$ を除いた変換行列との行列積はベクトルの加算減算で計算する

また，各要素の乗算である $[ Gg_{ci,co}G^ T ]⊙[B^ Td_{ci}B]$ は16個の行列ベクトル積に変換することができる．

$[ Gg_{ci,co}G^ T ]⊙[B^ Td_{ci}B]$ を $C_{i,j,co}$
$[ Gg_{ci,co}G^ T ]$ を $W_{i,j,ci,co}$
$[B^ Td_{ci}B]$ を $I_{i,j,ci}$

とし，さらに

$C_{i,j,co}$ を長さ $co$ のベクトル $C'_{i,j}$ に変換
$W_{i,j,ci,co}$ を $co \times ci$ の行列 $W'_{i,j}$ に変換
$I_{i,j,ci}$ を長さ $ci$ のベクトル $I'_{i,j}$ に変換

すると
$C'_{i,j}=W'_{i,j}I'_{i,j}$
と計算することができる

感想

SIMDで行列積変換するのめんどくさそう
数式の表現合ってるかな...