機械学習アルゴリズムの速度比較

機械学習の各アルゴリズムについての説明はたくさん存在しますが、それらの速度を比較している記事はあまりなさそうだったので、やってみました。

はじめに

「Deepでポン！」や「初手LightGBM」という言葉があります。沢山あるMLアルゴリズムのうち、使い慣れているのは一部だけ…という人も意外といるのではないでしょうか。特徴があるデータや変な制約に直面したときに、それに適した比較的マイナーな手法を試してみたら時間がかかって使い物にならない。そんな悲劇を無くすため、本記事では細かいことは置いておいて大雑把に20のモデルの時間を比較しました。

設定

• fit → predictを実行して、それぞれの時間を計測
  • n = 1,000 ~ 1,000万を実験
  • predictは .predict() が実装されてるもののみ実施
  • 10分以上かかったら止める
• パラメータはデフォルトの値を使う
  • ナニモワカラズexampleを参考に実行してみた状況を想定しています
  • ただしごく一部、速度にクリティカルに効くパラメータは設定（後述）
• GPUも使用しない
• pandasではなくpolarsを使用
  • これは単に好みで。別に大きく影響はしないはず
  • catboostだけ受け入れてくれなかったのでpandasに変換してる

※ 特に短い時間で終わるものは、あまり正確に測れてない説もあります。そのケースはそんなに速度気にならないはずなので、許してください。

環境

• windows11
• python 3.8.5
• scikit-learn 1.2.2
• lightgbm 3.3.5
• xgboost 1.7.5
• catboost 1.2

データ

• アイオワ州の酒類の販売データを使用
  • https://data.iowa.gov/Sales-Distribution/2019-Iowa-Liquor-Sales/38x4-vs5h
• 教師ありの場合、売上を予測（特徴量は12個）
• 教師なしの場合、売上を除いた特徴量を使用してクラスタリング・次元圧縮を実施
• 元々238万レコードのデータから、一部取り出して、あるいは増幅させて実験¹

あまり本記事の本題と関係ないので、データの説明は以下に折りたたんでおきます。

https://data.iowa.gov/Sales-Distribution/2019-Iowa-Liquor-Sales/38x4-vs5h
◆ 2019年のデータ（本来は数年分あるデータセット）
◆ ライセンスはCC0

特徴量は以下の12個。ミスって本来カテゴリカル変数として入れるべきものも混ざってしまってます。LabelEncodingしたと思っていただければ汗

• Store Number
• Zip Code
• County Number
• Category
• Vendor Number
• Item Number
• Pack
• Bottle Volume (ml)
• Bottles Sold
• State Bottle Cost
• State Bottle Retail
• Volume Sold (Liters)
• Volume Sold (Gallons)

今回精度はまったく見ていませんが、売数と商品コードがあるのでそこそこ精度良いモデルが作れてる気がします。

比較したアルゴリズム

• sklearn.linear_model
  • LinearRegression
  • Ridge
  • Lasso
  • BayesianRidge
• sklearn.tree
  • DecisionTreeRegressor
  • 無限に深くなってしまうので、n > 10,000のときは max_depth=7 だけ指定してる
• sklearn.ensemble
  • RandomForestRegressor
  • 同じく、n > 10,000のときは max_depth=7 だけ指定
  • GradientBoostingRegressor
• sklearn.neighbors
  • KNeighborsRegressor
  • NearestNeighbors
• sklearn.svm
  • SVR
• sklearn.cluster
  • KMeans
  • DBSCAN
• sklearn.mixture
  • GaussianMixture
• sklearn.decomposition
  • PCA
  • NMF
• sklearn.manifold
  • TSNE
• sklearn.gaussian_process
  • GaussianProcessRegressor
  • カーネルはexampleに従って、kernel = DotProduct() + WhiteKernel() を設定
• lightgbm
  • LGBMRegressor
• xgboost
  • XGBRegressor
• catboost
  • CatBoostRegressor

結果概要

fit にかかった時間をまとめたものが以下になります。両軸とも対数表示にしているのにご注意ください。

大雑把に見てみると

• 線形モデルは速い
• ガウス過程回帰、サポートベクターマシンは遅い
• 木系、GBDT、クラスタリングは真ん中くらい
• 次元圧縮はものによる違いが大きそう

あたりは言えそうです。

なお、画像だと線が多くて見にくいので、plotlyの動かせるグラフをこちらからご覧いただけます。

結果詳細

sample sizeを3000, 100万, 1000万にしたときの結果を載せます。

※ predictが0のものは、（１）そもそも実装されていないもの、（２）ほぼ0秒で終わるのでうまく表示されてないもの、のどちらもあります（見にくくてすいません…）

以上をもとに、もう少し詳細に比較していきます。

線形モデル

• Ridge < BayesianRidge ≤ 線形回帰 << Lasso
• 推論も概ね同じ

1000万レコードでも数秒で終わるのは流石ですね。
線形回帰、Ridgeは解析的に解け、単なる行列計算で済むので分かりやすく速いです。Lassoは逐次的なアルゴリズムで学習しているので、そのあたりの違いが顕著に出てます。

木系

• 決定木 < GradientBoostRegressor < RandomForest
• 推論も概ね同じ

GradientBoostRegressorはアルゴリズム的にはxgboostとそんなに大きく違わないと記憶していたのですが²、xgboostと大きな差がついてるのは実装上の問題ですかね。
RandomForestは結構メモリを食べるという指摘もあります³。また、Rだとパッケージによって結構速さが違ったりもするらしいです⁴。

GBDT

• 学習は lightgbm < xgboost < catboost
• 推論は catboost < xgboost < lightgbm

これは比較されてる記事をよく見かけますが⁵、その通りの結果になりました。
あと今回はカテゴリ変数を使っていないので、そのあたりも入れると結果が違ってくるでしょう⁶⁷。

クラスタリング

• GaussianMixture < KMeans ≒ KNearestNeighbor ≒ KNeighborsRegressor << DBSCAN
• nが小さいときは、DBSCANが高速
• KNearestNeighborの推論がやけに遅い⁸

今回は規模によって振る舞いが違う結果になっています。たぶんググったらそれぞれのtime complexityとか出てくるはず。

次元圧縮

• PCA < NMF << TSNE

高速化のライブラリも色々ありそうです⁹¹⁰。

その他

• GaussianProcess: とても遅い
• SVR (support vector machine): 遅い

おわりに

各アルゴリズムについて高速化の工夫は色々あるので、あまりこの結果を過信しないでください。あくまで参考程度にどうぞ。

一応コードはこちらになります。

他のアルゴリズムや、列が増えた際の挙動なども知りたいところですが、ここで力尽きました。
もし万が一要望があればやるのでコメントください！

1. polarsなので、sample(with_replacement=True) を使用しています ↩

2. かなりあいまいな記憶なので、嘘かも。 ↩

3. https://www.haya-programming.com/entry/2019/06/22/235209 ↩

4. https://kininaru-tetsu.blogspot.com/2015/12/blog-post.html ↩

5. https://www.acceluniverse.com/blog/developers/2019/12/catboost.html ↩

6. https://towardsdatascience.com/catboost-vs-lightgbm-vs-xgboost-c80f40662924#5d39 ↩

7. こういう、本記事のような適当な比較を戒めてる論文もあるので読むといいと思います。https://openreview.net/pdf?id=ryexWdLRtm ↩

8. https://www.kaggle.com/questions-and-answers/123363 ↩

9. https://recruit.cct-inc.co.jp/tecblog/machine-learning/t-sne/ ↩

10. https://jpn.nec.com/hpc/sxauroratsubasa/column/014.html ↩