SparseMatrixについてまとめてみた #Python

この記事は、「Machine Learning Advent Calendar 2015」の15日目の記事になります。
Machine Learningの実装を行う場合によく利用される「Sparse Matrix」について簡単ですがまとめてみました。

SparseMatrix

SparseMatrixとは一般的なDenseMatrixとは異なり、Non-zero Value(0以外の数値)の数がベクトルの長さに対して極めて小さい場合に利用されることが多いです。
SparseMatrixは以下の点でDenseMatrixより優れています。

消費するメモリの量が少なくなる
行列・ベクトル演算のスピードが高速になる

これらのメリットは行列、またはベクトルが十分に大きいサイズであり、なおかつNon-zero Valueの数が小さいときに非常に大きな効果を発揮します。
例えば、複数の質量変数を1-of-Kで表現している場合などが挙げられます。
今回は説明の簡略化のため、行列ではなくベクトルの演算を例に各種ライブラリを見ていきます。

scipy.sparse

おそらくここで説明する中では最も有名なものだと思います。Pythonの機械学習ライブラリでは最も有名であるscikit-learnでも利用することが可能です。
例えば、sklearn.clustering.KMeansの場合、ここに書かれている通り、

X : array-like or sparse matrix

というようにSparseMatrixをXに利用することが可能になっています。
SparseMatrixを定義する方法は様々なものがあります。
詳しくは公式ドキュメントの方を見てください。

Examples

実際に演算する上でDenseとSparseでどれくらい差があるかを見てみましょう。

>>> import scipy.sparse as sp
>>> import numpy as np
>>> # 長さ1,000のベクトル
>>> x1=np.zeros(10**3)
>>> x1[10]=5; x1[100]=10;
>>> y1=sp.lil_matrix(x1).tocsr()
>>> %time x1 * x1 % 要素積
21 μs

>>> %time y1.multiply(y1)
249 μs

>>> # 長さ1,000,000のベクトル
>>> x2=np.zeros(10**6)
>>> x2[10]=5; x2[100]=10;
>>> y2=sp.lil_matrix(x2).tocsr()
>>> %time x2 * x2 % 要素積
4.15 ms

>>> %time y2.multiply(y2)
250 μs

上の例のようにベクトルの長さが大きくなると明らかに計算時間が異なってます。
ちなみに上の例では要素積ですが足し算の場合もDenseVectorに比べて高速になります。

注意点

処理が高速になるのはmultiply()で計算するときのみです
ベクトル積を行う場合は次のようにする方が良いです

# これだとSparseのOperationが行われない
%time y2 * y2.T
3.41 ms

# こちらはSparseのOperatioが行われる
%time y2.multiply(y2).sum()
447 µs

scipy以外の他のライブラリ

Theano

theano.sparseパッケージをロードして使うことができます。
scipy.sparseで言うところのcsr, cscが用意されてます。

>>> from theano import sparse

簡単ですが、上と同じ例をTheanoでもやってみます。

>>> import theano
>>> from theano import sparse
>>> x = sparse.csr_matrix(name='x', dtype='float64')
>>> f = theano.function([x], sparse.basic.mul(x, x))
>>> %time f(y1)
312 µs

もちろん普通のベクトルで演算した場合は、

>>> import theano.tensor as T
>>> x = T.dvector(name='x')
>>> f = theano.function([x], x * x)
>>> %time f(x1)
4.74 ms

のように演算に時間がかかってしまいます。
Theanoのように柔軟に関数が利用でき、微分なども簡単に計算できるライブラリでは覚えておくと便利になると思います。

ただし、注意として

sparse.basicにある演算をfunctionには利用する
theano.sparseはGPUには対応していないようです

TensorFlow

話題のTensorFlowSparseTensorというものを提供しています。

>>> import tensorflow as tf
>>> tf.SparseTensor(values=[1, 2], indices=[[0, 0], [1, 2]], shape=[3, 4])
[[1, 0, 0, 0]
 [0, 0, 2, 0]
 [0, 0, 0, 0]]

こちらは少し調べてみたのですが、利用方法については詳しくわかりませんでした。（後日更新しようと思います）

おわりに

簡単ではありますが、SparseMatrixについてまとめてみました。
自分もまだ勉強中の身で、わからないこともいいので何かご指摘などありましたらコメントいただけると嬉しいです。
機械学習を実装する場合、特にオンライン学習などの場合には有効なので実装する際はDenseMatrixだけでなく、SparseMatrixの実装も考えてみてはいかがでしょうか！？