確率的勾配降下法（SGD）の並列化について
RecSys 2013 (Hong Kong) - RecSysのbest paperが、なんだか面白そうだったので読む。
A Fast Parallel SGD for Matrix Factorization in Shared Memory Systems
論文の提案手法に関してはこっち
RecSys2013のBestPaperを読む_Fast_Parallel_SGD - 分からんこと多すぎ
本論文自体は、Matrix FactorizationのためのSGDの拡張である点が、他の論文とは違うらしい。
で、この論文の途中に、state-of-the-artが丁寧にまとめられていたので、備忘録にする。
SGDというのは、最適化の方法の1つで、
- 一回の更新にあたって参照するデータ量が少なく（勾配の計算が簡単）
- オンライン化が容易である
ので、大規模データの解析に利用できると言われている。
ただ、SGDはもともと１コア用の処理なので、並列化したい。
そこで、Hog Wildのアルゴリズムと、distributed stochastic gradient descent (DSGD) が、作られた。
今回は、SGDとHog WildとDSGDを、順番に解説（翻訳）していく。
実装は、見たらわかるので割愛する。
1.SGD
これは、単純な勾配法である。
行列Rのu行v列成分を、PuとQvで表現して、誤差を最小化する。
ただし、そのままでは過学習するので、正則化項として、後ろに2つの項を付ける。
SGDでは、(1)の式の勾配を計算するのが困難な場合に、ランダムに(u,v)を選択し、(1)式を以下の式のように簡単化する。
その後、上式を微分し、最急降下法により、(2)式と(3)式で表される更新式を得る。
あとは愚直に(2)と(3)を繰り返せば良い。
2.Hog Wild
この方法では、複数コアで同時に(2)と(3)を繰り返すだけである。
そんなことをすると、更新する時に、あるコアが計算した結果を、別のコアの計算結果が上書きするという事態が発生する。
こういった操作を、Atomic Operation（不可分操作）と言うらしい。
が、そんなことは、疎で巨大な行列なら、滅多に起こらないから気にしない。
特定条件下における収束証明もされていて、実用上問題は発生しないようだ。
3.DSGD
DSGDでは、HogWildとは違い、複数コアで同じ要素を上書きし合うことを避けようとした。
その結果、行列を幾つかに切り分けて、各コア中でそれぞれ独立に更新することにした。
上の図が分かり易いが、行列を分割し、各コアに割り当てると、同じインデックスを選択することが起こりえなくなる。
したがって、コア同士の更新が干渉しなくなる。
ただ、ブロック行列の同じ行や列を選択することができなくなるため、何度も反復してコア間でデータを渡しあわなければならない。
（更新したPやQを参照するために、反復する必要がある）
：以下、個人的疑問
またこの方法では、上手い分割の仕方をしなければ、変なPとQが求まってしまうことが予想される。
例えば、最悪の場合、行列の密部分（いわば1つのクラス）を4つに分割してしまうという事態が発生しうる。
こうなると、その密部分の再構成は、他の密部分が優先された結果、おざなりにされるかもしれない。
（正則化があるので、値の小さな部分は切り捨てられる）
R言語でテンソルを解析する_四則演算編
11/17追記
どうも計算が間違っていることに気がついたので修正中
R言語で疎テンソルを扱うために、slamを導入したが、slamでは要素に対する値の代入ができない。
例えば、dataという三階のテンソルのi,j,k要素のvalue（値）を10に変更するという処理
data[i,j,k]$v <- 10
などができない。
当然、テンソル同士の引き算などもできない。
しかたがないので、関数化する。
calc_simple_sparse_arrayにsimple_sparse_arrayのリストlist(data1,data2,data3)を突っ込むと、METHODで指定した処理がなされて帰ってくる。
例えばcalc_simple_sparse_array(list(data1,data2,data3), METHOD = 2)だと、+data1-data2-data3が帰ってくる。
paste.list <- function(...){ #内部処理高速化のための関数 return(paste(..., sep=":")) } calc_simple_sparse_array <- function(..., METHOD = 1) { #テンソルの和などをする関数 #...:simple_sparse_arrayのlist #METHOD:switch文参照 switch(METHOD, "1" = func <- function(x,y){ x + y }, "2" = func <- function(x,y){ x - y }, "3" = func <- function(x,y){ x * y }, "4" = func <- function(x,y){ x / y }, ) #ユニークなインデックスの組み合わせの探索 idx.mat <- unique(do.call(args = lapply(...,FUN = function(SSA){return(SSA$i)}),what = rbind)) tmp <- do.call(what=paste.list,args=as.data.frame(idx.mat)) idx.list <- lapply(...,FUN = function(SSA){ tmp.idx <- do.call(what=paste.list,args=as.data.frame(SSA$i)) tmp.idx <- match(tmp.idx,tmp) #tmp.idx <- tmp.idx[!is.na(tmp.idx)] return(tmp.idx) }) #数値ベクトルの生成 value.vec <- rep(0,dim(idx.mat)[1]) value.vec[ idx.list[[1]] ] <- ...[[1]]$v if(length(...) > 1){ for(i in 2:length(...)){ value.vec[ idx.list[[i]] ] <- func(value.vec[ idx.list[[i]] ], ...[[i]]$v) } } return(simple_sparse_array(i=idx.mat,v=value.vec)) }
R言語でテンソルを解析する_bind編
R言語で（数万×数万×数万）からなるテンソルを扱うキチ◯イのために、テンソルを処理してbindする方法を書いておく。
R言語ではおそらく、slamパッケージ以外に巨大な疎テンソルを扱う方法が存在しない。
したがって、以下ではslamパッケージを使うことを前提としている。
また、doMCパッケージも用いるが、これは、並列化のためのパッケージである。
便利なことに、.combineという引数で、中のデータを結合することができる。
イメージ的には、do.callとかReduceでcbindする感じ。
これを利用してbindする。
.combineによってabind_simple_sparse_arrayをすると、中で作られたsimple_sparse_arrayを任意の方向に（MARGINで指定した方向に）結合することができる。
サンプルコードは以下。
data1という全要素が１のsimple_sparse_arrayと、data2という全要素が２のsimple_sparse_arrayを、MARGIN=3（奥行方向）に結合している。
library('slam')
library('doMC')
registerDoMC(2)
data <- foreach(i = 1:2, .combine = function(...){ abind_simple_sparse_array(...,MARGIN=3)} ) %dopar% {
as.simple_sparse_array(array(i,c(4,3,2)))
}
> as.array(data)
, , 1
[,1] [,2] [,3]
[1,] 1 1 1
[2,] 1 1 1
[3,] 1 1 1
[4,] 1 1 1
, , 2
[,1] [,2] [,3]
[1,] 1 1 1
[2,] 1 1 1
[3,] 1 1 1
[4,] 1 1 1
, , 3
[,1] [,2] [,3]
[1,] 2 2 2
[2,] 2 2 2
[3,] 2 2 2
[4,] 2 2 2
, , 4
[,1] [,2] [,3]
[1,] 2 2 2
[2,] 2 2 2
[3,] 2 2 2
[4,] 2 2 2
