静かなる名辞

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


【python】sklearnのPCAでsvd_solverによる速度差を比較

python sklearn 主成分分析 次元削減 機械学習 20newsgroups CountVectorizer 自然言語処理 Tips 速度計測シリーズ

　sklearnのPCA（主成分分析）がやたら遅くて腹が立ちました。計算コストを下げるために次元削減してるのに、次元削減で計算コスト食ったら意味がありません。

　とにかくこのPCAを高速化したかったので、svd_solverを変えてどうなるか試しました。なお、腹が立つくらい遅かった理由は最終的にちゃんとわかったので、この記事の最後に載せます。

　目次

スポンサーリンク



svd_solverとは

　PCAは内部で特異値分解（SVD）を使っています。この特異値分解がコンピュータにやらせるにはそれなりに計算コストの高い処理で、とりあえずアルゴリズムが何種類かあるようです。

　sklearnのPCAで使える（指定できる）アルゴリズムは次の4つです。

  • auto

　デフォルト値。500*500以下の入力データならfullを、それ以上ならrandomizedを使うそうです*1

  • full

　standard LAPACK solverを使うそうです。とりあえずぜんぶ丸ごと特異値分解してから、n_componentsで指定した次元数だけ取ってくるそうな

  • arpack

　Truncate SVDという手法を使う。一次元ずつ寄与率の大きい主成分から計算していくらしい。n_componentsが小さければ速いことが期待されるんだと思う

  • randomized

　randomized SVDという手法で計算する。乱数使って速くした。乱数なので厳密解ではない

　なお、以上の情報はすべて公式ドキュメントから得ました。
sklearn.decomposition.PCA — scikit-learn 0.20.1 documentation

　とりあえずautoはどうでも良いので、残りの3つを比較することにします。

実験

　PCAをかけたくなるような高次元データといえばBag of Words、ということでこのブログですでに何回も取り上げたことのある、sklearnのfetch_20newsgroupsとCountVectorizerの組み合わせを使います。前者はテキストのデータセット、後者はBoWを生成するクラスです。

　次のような実験用コードを書きました。

# coding: UTF-8

import time
from itertools import product

from sklearn.datasets import fetch_20newsgroups
from sklearn.feature_extraction.text import CountVectorizer
from sklearn.decomposition import PCA

def main():
    news20 = fetch_20newsgroups()

    for min_df in [0.02, 0.01, 0.008, 0.005]:
        cv = CountVectorizer(min_df=min_df, max_df=0.5,
                             stop_words="english")
        X = cv.fit_transform(news20.data).toarray()

        print("min_df:{0} X.shape:{1}".format(min_df, X.shape))
        for n_components, svd_solver in product(
                [100, 500],
                ["full", "arpack", "randomized"]):
            pca = PCA(n_components=n_components, svd_solver=svd_solver)
            t1 = time.time()
            pca.fit_transform(X)
            t2 = time.time()
            print("n_components:{0}  solver:{1:>10}  "\
                  "time:{2:>6.2f}  CP:{3:.4f}".format(
                      n_components, svd_solver, t2-t1, 
                      pca.explained_variance_ratio_.sum()))
        print("")

if __name__ == "__main__":
    main()

　BoWの次元数をmin_dfで変えていき、n_componentsを100と500、svd_solverを上記3つで変化させてPCAをかけたときの速度と累積寄与率（CP：Cumulative Proportion）をそれぞれ測ります。

結果

　次のようになりました。

min_df:0.02 X.shape:(11314, 866)
n_components:100  solver:      full  time:  3.60  CP:0.7455
n_components:100  solver:    arpack  time:  3.90  CP:0.7455
n_components:100  solver:randomized  time:  1.72  CP:0.7443
n_components:500  solver:      full  time:  3.89  CP:0.9528
n_components:500  solver:    arpack  time: 19.42  CP:0.9528
n_components:500  solver:randomized  time:  8.91  CP:0.9516

min_df:0.01 X.shape:(11314, 1916)
n_components:100  solver:      full  time: 22.38  CP:0.8029
n_components:100  solver:    arpack  time:  8.41  CP:0.8029
n_components:100  solver:randomized  time:  4.86  CP:0.8028
n_components:500  solver:      full  time: 22.06  CP:0.9304
n_components:500  solver:    arpack  time: 53.73  CP:0.9304
n_components:500  solver:randomized  time: 13.47  CP:0.9293

min_df:0.008 X.shape:(11314, 2391)
n_components:100  solver:      full  time: 34.24  CP:0.7899
n_components:100  solver:    arpack  time: 10.42  CP:0.7899
n_components:100  solver:randomized  time:  5.75  CP:0.7897
n_components:500  solver:      full  time: 34.88  CP:0.9193
n_components:500  solver:    arpack  time: 63.37  CP:0.9193
n_components:500  solver:randomized  time: 15.18  CP:0.9182

min_df:0.005 X.shape:(11314, 3705)
n_components:100  solver:      full  time:100.52  CP:0.7701
n_components:100  solver:    arpack  time: 16.46  CP:0.7701
n_components:100  solver:randomized  time:  8.70  CP:0.7699
n_components:500  solver:      full  time:100.73  CP:0.9000
n_components:500  solver:    arpack  time: 94.33  CP:0.9000
n_components:500  solver:randomized  time: 20.04  CP:0.8988

　要約すると、

  • fullは基本的に遅い。入力の次元数が増えるとびっくりするくらい遅くなる
  • arpackは100次元に落とすときは威力を発揮している。500次元に落とすケースではかえって遅くなる。ヘタするとfullより遅い
  • randomizedは速い。ただし厳密解ではないことがCPからわかる（full、arpackとは微妙に違う数字になっている）

　こういう状況です。わかりやすいですね。

　それぞれの使い分けは、

  1. 入力次元数の小さい入力ではfullで良い。というかヘタにそれ以外を指定するとかえって遅いケースもある
  2. 入力次元数が大きく、入力次元数>>出力次元数で厳密解がほしければならarpackの使用を検討する
  3. 厳密解じゃなくても良いのでとにかく速いのを！　ってときはrandomized

　ってことになるかと思う・・・。

まとめ

　けっこう変わる。頑張って使い分けよう。

おまけ：腹が立った理由

　sklearnのPCAではn_componentsに小数を指定できます。そうすると累積寄与率がその数字になるように勝手に次元数を決めてくれるので、こりゃ便利だわいと思って私はよく使っていました。

　しかし、実はarpack、randomizedではこの小数での指定は使えません。そのことはドキュメントにもちゃんと書いてあります。無理矢理に指定すると次のようなエラーを吐かれます。

ValueError: n_components=0.95 must be between 1 and n_features=866 with svd_solver='arpack'

　ということは何が起こるか？　勝手にfullにされます。遅い訳です。なんてこった。

　わかってしまえば下らない話で、要するに私が使いこなせていなかっただけなのですが、このことは「ちゃんとドキュメントをよく読んで使おうね」という教訓を私に残したのでした。

*1:300*800だったりしたらどうなるんだろう？　それとも共分散行列のサイズなのだろうか？