scikit-learnのモデルに疎行列（csr_matrix）を渡したときの速度
はじめに
sklearnのモデルには疎行列を取れるものもたくさんありますが、この場合速度差があったりするのでしょうか。
いろいろなデータとモデルで検証を行ってみました。
目次
実験1：digitsを分類させてみる
簡単のためにdigitsを使います。digitisは数字が書かれている白い部分などが0になるデータのため、疎行列表現に向いています。
分類器は
- SVC（サポートベクターマシン）
- RandomForestClassifier（ランダムフォレスト）
- MultinomialNB（多項ナイーブベイズ）
- GradientBoostingClassifier（勾配ブースティング）
- MLPClassifier（多層パーセプトロン）
を使うことにします（いずれもscipyの疎行列型（csr_matrix）を引数に取れるものです）。
コード
import time from scipy.sparse import csr_matrix from sklearn.datasets import load_digits from sklearn.model_selection import train_test_split from sklearn.svm import SVC from sklearn.ensemble import RandomForestClassifier,\ GradientBoostingClassifier from sklearn.naive_bayes import MultinomialNB from sklearn.neural_network import MLPClassifier from sklearn.metrics import f1_score def main(): digits = load_digits() X_train_d, X_test_d, y_train, y_test = train_test_split( digits.data, digits.target, stratify=digits.target) svm, rfc, nb, gbdt, mlp\ = SVC(gamma="scale"), \ RandomForestClassifier(n_estimators=100, random_state=0, n_jobs=-1), \ MultinomialNB(), \ GradientBoostingClassifier(),\ MLPClassifier() for clf in [svm, rfc, nb, gbdt, mlp]: print(clf.__class__.__name__) for x_sparse in [False, True]: if x_sparse: X_train, X_test = csr_matrix(X_train_d),\ csr_matrix(X_test_d) else: X_train, X_test = X_train_d, X_test_d t1 = time.time() clf.fit(X_train, y_train) t2 = time.time() fit_time = t2 - t1 t1 = time.time() pred = clf.predict(X_test) t2 = time.time() pred_time = t2 - t1 print("sparse:{0:5} " "fit:{1:.4f}[s] " "pred:{2:.4f}[s] " "f1:{3:.4f}".format(str(x_sparse), fit_time, pred_time, f1_score(y_test, pred, average="macro"))) print() if __name__ == "__main__": main()
結果
SVC sparse:False fit:0.2539[s] pred:0.0378[s] f1:0.9845 sparse:True fit:0.4004[s] pred:0.0642[s] f1:0.9845 RandomForestClassifier sparse:False fit:0.2547[s] pred:0.1023[s] f1:0.9710 sparse:True fit:0.3523[s] pred:0.1036[s] f1:0.9710 MultinomialNB sparse:False fit:0.0068[s] pred:0.0021[s] f1:0.8783 sparse:True fit:0.0038[s] pred:0.0007[s] f1:0.8783 GradientBoostingClassifier sparse:False fit:3.5609[s] pred:0.0081[s] f1:0.9733 sparse:True fit:6.1823[s] pred:0.0155[s] f1:0.9733 MLPClassifier sparse:False fit:1.6450[s] pred:0.0012[s] f1:0.9801 sparse:True fit:2.0896[s] pred:0.0019[s] f1:0.9802
多項ナイーブベイズ以外は遅くなるようです。
実験2：多項ナイーブベイズについてもう少し
多項ナイーブベイズについて詳しく見ていきます。
コード
import timeit from scipy.sparse import csr_matrix from sklearn.datasets import load_digits from sklearn.model_selection import train_test_split from sklearn.naive_bayes import MultinomialNB def main(): digits = load_digits() X_train_d, X_test_d, y_train, y_test = train_test_split( digits.data, digits.target, stratify=digits.target) X_train_s, X_test_s = csr_matrix(X_train_d), \ csr_matrix(X_test_d) nb = MultinomialNB() td = timeit.timeit( lambda : nb.fit(X_train_d, y_train), number=10**3) ts = timeit.timeit( lambda : nb.fit(X_train_s, y_train), number=10**3) tc = timeit.timeit( lambda : nb.fit(csr_matrix(X_train_d), y_train), number=10**3) print("dense:{0:.4f}[s] sparse:{1:.4f}[s] " "convert:{2:.4f}".format(td, ts, tc)) # => dense:1.9102[s] sparse:1.6712[s] convert:3.8140 if __name__ == "__main__": main()
速いのは確かですが、もともとnumpy配列型の場合、変換時間込みでは遅いようです。
実験3：巨大データで試す
キャッシュ効率などにも影響されるはずなので、巨大データで試します。
なお、20newsgroupsを使いましたが、SVM, 勾配ブースティング、多層パーセプトロンは遅すぎにより除外しています。
コード
import time from scipy.sparse import csr_matrix from sklearn.datasets import fetch_20newsgroups from sklearn.feature_extraction.text import CountVectorizer from sklearn.ensemble import RandomForestClassifier from sklearn.naive_bayes import MultinomialNB from sklearn.metrics import f1_score def main(): news20_train = fetch_20newsgroups(subset="train") news20_test = fetch_20newsgroups(subset="test") cv = CountVectorizer(stop_words="english", min_df=0.01) X_train_d = cv.fit_transform(news20_train.data).toarray() y_train = news20_train.target X_test_d = cv.transform(news20_test.data).toarray() y_test = news20_test.target rfc, nb\ = RandomForestClassifier(n_estimators=100, random_state=0, n_jobs=-1), \ MultinomialNB() for clf in [rfc, nb]: print(clf.__class__.__name__) for x_sparse in [False, True]: if x_sparse: X_train, X_test = csr_matrix(X_train_d),\ csr_matrix(X_test_d) else: X_train, X_test = X_train_d, X_test_d t1 = time.time() clf.fit(X_train, y_train) t2 = time.time() fit_time = t2 - t1 t1 = time.time() pred = clf.predict(X_test) t2 = time.time() pred_time = t2 - t1 print("sparse:{0:5} " "fit:{1:.4f}[s] " "pred:{2:.4f}[s] " "f1:{3:.4f}".format(str(x_sparse), fit_time, pred_time, f1_score(y_test, pred, average="macro"))) print() if __name__ == "__main__": main()
結果
RandomForestClassifier sparse:False fit:15.2506[s] pred:0.4377[s] f1:0.6945 sparse:True fit:7.5513[s] pred:0.2058[s] f1:0.6945 MultinomialNB sparse:False fit:0.1795[s] pred:0.1097[s] f1:0.6806 sparse:True fit:0.0230[s] pred:0.0094[s] f1:0.6806
この場合はそこそこ速くなるようです。ご利益がある、と言って良いのではないでしょうか。
実験3：巨大データで相互変換にかかる時間を検証する
巨大データにおける相互変換速度を検証します。
import timeit from scipy.sparse import csr_matrix from sklearn.datasets import fetch_20newsgroups from sklearn.feature_extraction.text import CountVectorizer def main(): news20_train = fetch_20newsgroups(subset="train") cv = CountVectorizer(stop_words="english", min_df=0.01) X_train_s = cv.fit_transform(news20_train.data) X_train_d = X_train_s.toarray() tc1 = timeit.timeit(lambda : csr_matrix(X_train_d), number=100)/100 tc2 = timeit.timeit(lambda : X_train_s.toarray(), number=100)/100 print("dense->sparse:{:.4f}[s]\n" "sparse->dense:{:.4f}[s]".format(tc1, tc2)) if __name__ == "__main__": main()
結果
dense->sparse:0.1530[s] sparse->dense:0.0341[s]
ということは、スパースで持たせておいて必要に応じてdenseに変換する、というのはありな戦略だと思います。逆は少し重いようですが、それでも考慮に値します。
この変換をするモデルは、FunctionTransformerで簡単に書けます。
sklearn.preprocessing.FunctionTransformer — scikit-learn 0.21.3 documentation
def f(X, *args, **kwargs): return X.toarray()
のような関数を書いてモデルに渡すだけですね。
考察
疎行列表現の場合はアクセスのたびにデータ変換を行って取り出すことになるので、オーバーヘッドのことだけ考えれば遅くなることが予想されます。
疎行列表現の方が速くなるケースがあるのは、つまりは以下のような事情によると考えられます。
- CPUのキャッシュ効率に依存する。つまり、でかすぎるデータをそのまま扱うと大部分がCPUキャッシュからあふれるが（数MBしかないのが普通なので）、疎行列表現ならだいぶ改善する可能性がある
- ゼロが多く含まれるデータを密行列（普通のnumpy配列など）で表現した場合、計算処理の時間の大部分はゼロの配列要素との比較に費やされる。アルゴリズムの実装側で配慮してくれていれば、疎行列表現を使った場合は非ゼロの部分だけ取り出して演算できるので、速くなる可能性がある。
要約すると、データが大規模で、かつスパースであれば疎行列表現の方が有利な可能性があるという、当たり前の結論になります。
まとめ
概ね素のnumpy配列の方が速い。モデル（多項NBなど）やデータサイズによっては逆転し得る。
多項NBはともかく、他のモデルでもうまくやれば数倍速くなるようなので、考慮に値すると思います。
追記
もっとよく効く使いみちを見つけました。変数選択で使うときに、疎行列の方が何桁も効率的です。
sklearnの変数選択は疎行列型（csr_matrix）でやると速いっぽいよ - 静かなる名辞
色々気になることがあったので、調査した上で疎行列型で扱う場合の工夫を記事にまとめました。こちらも御覧ください。
