静かなる名辞

pythonとプログラミングのこと

2019/03/22:TechAcademyがteratailの質問・回答を盗用していた件
2019/03/26:TechAcademy盗用事件 公式発表と深まる疑念


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)でやると速いっぽいよ - 静かなる名辞

 色々気になることがあったので、調査した上で疎行列型で扱う場合の工夫を記事にまとめました。こちらも御覧ください。

【python】scikit-learnで大規模疎行列を扱うときのTips - 静かなる名辞