Edited at

GPU(CUDA)で高速に「売れた商品をカテゴライズする」までの試行錯誤。GPUすごいし、Elasticsearchと組み合わせると便利

More than 1 year has passed since last update.


きっかけ

 大量のデータから何が売れ線なのかをみたくて、Kibanaでポチポチと見ていたら商品名称や説明からカテゴライズしたくなった。カテゴライズしたデータのトレンド線が上向いてたらこれは、流行ってるんだな?とか、「寒いと売れると思ってたのに・・売れない品もあるんだな」といったことが分かるかも?と仮設をたててみる。カテゴリ分類は人間が決めているので、やっぱり恣意性がある。機械的に分類したい。経産省の「日本標準商品分類」ってのにできたらいいのか?とりあえず教師無し学習で分類してみる。


結果

・ビジネス的には希望の光が見えるかも・・くらい。

・カテゴライズするにはする!がノイズが多くて変なところで引きあってしまう。

・データのクリーニングにとても時間がかかる。

・とにかくCPUベースでは遅い。GPUにしたら結果的に最適化されてないPHPソース比で1000倍くらい早くなった気がする。

・PythonではGPUのパワーは出しきれない。CUDA-Cのパワーはすごい。

・Elasticsearchに放り込んだら、便利すぎて涙が出た。

ここから下は説明


教師無し学習でやる

そもそもどうやって文章をカテゴライズするの?って状態だったのでイロイロ調べ、論文読んだりしてみました。

「何言ってんのかわかんないっす」って脳みそだったのが、たくさん読んでると理解してくる。

文章クラスタリングというらしい。


文章が似ている、似ていないとは??

文章が似ているか?似ていないか?の判断は二つの文章を比較してスコアをつけてあげればいい

以下の例文を採点する

A:「青りんごが盗まれた」→「青」「リンゴ」「盗む」

B:「赤リンゴが盗られた」→「赤」「リンゴ」「盗む」

C:「リンゴが潰れた」→「リンゴ」「潰す」

D:「おいしいミカンが無くなった」→「おいしい」「ミカン」「無くす」

「→」これは、文を単語に分解して原形に戻す(ほんとに原形になってるか?自信ないです)+カタカ揺れを直す。

この辺はkuromojiとかの形態素解析で頑張る。

シノニムで展開してやるとさらに精度があがるかも。

AとBを比較すると

A+Bのベクトルを作る。(ベクトルって・・・って人はググってください)

「青」「赤」「リンゴ」「盗む」→これが軸

#


リンゴ
盗む

A
1
0
1
1

B
0
1
1
1

できたー

なんとなく、数学的に似ているか判断できそう。

形態素解析を通さない場合は2~3グラムでベクトルを作ってもいいかも。

でも次元数は半端ない。


コサイン類似度

この値をコサイン類似度ってやつに通すと・・・

数学的に0.5似ているって言えることが導き出せます。

コサイン類似度でググるとでてくるよ。

K-MEANSとかクラスタリングは、↑の行が山ほどあるのもをクラスタ化するんですが

文章の場合は次元数が1000とか軽くいってしまうし、軸を足し合わせていったら次元数がとんでもないことになって計算時間が増えてしまう。


集合の計算方法

上記の方法で2つの似ている値(以下スコア)が算出できるので

あとは全ての組み合わせでスコアが一番高い組が一番にていることになる。

A、B、C、D・・・・と品があったとき

A:B、A:C、A:DのなかでAが最も似ている品を算出する

同じように

B:A、B:C、B:DのなかでAが最も似ている品を算出する

全組み合わせ表を算出する

つまり・・・

O(n^2)の計算量になる。


実際にやってみる(すごい時間かかる)

100万超える品(ちょっと名前が変わったら違う商品)をPHPで分類してみたら。。

終わらない。

1万品とかにしてみるけど終わらない。

1000品とかにしてみたら30分くらいで終わった。

これは・・・O(n^2)だから・・・まともにやったら100年とかかかるような気がする。


試行錯誤やってみた

・とにかく遅い

・日本語の突き合わせはすべて転置インデックスにした

・ノイズを可能な限り除去した

・マルチプロセスでCPUコアをちゃんと使えるようにしようとしたけどPHPはだめだ

・PHPは遅いのでPythonでやってみたけど・・やっぱり遅いので・・Cで組んでみたが10倍早くなったくらい。。悲壮感漂う

・スーパーコンピュータ使いたい

・GPU(GTX1050ti)をとりあえず買ってみた。

ここからGPUの試行錯誤

・CUDAコードに起こすのが難しい!Pythonや!→やっぱり遅い!!

・GPUがフルパワー出さない

・PythonからGPU使っても遅いからCUDAコード書く!

・そもそもN万スレッドを立ち上げる感覚がわからない。

・なんとかしてN万スレッドを立ち上げる感覚が身に付く!

・早い!CPU比で20倍くらいはやい!

・CUDA難しいけど楽しい!

・カーネルコードはCPUコードでも動くようにコピーを作っておく

・CPUコードでテストして、GPUコードでテストすると動作確認、デバッグがやりやすい

・マシン語の部分を意識してやればもっと早くなりそう!!

・ifの除法、forの除法やってみる。早い。

・CUDAは無限にリファクタリングできそうだから・・あきらめた

・GTX1050tiでは遅い!!もっといいGPUがほしい!

GPUがうまく動かないとき

・GPU独特の制限を回避しないとWindowsでは長時間カーネル実行ができない「n秒問題」

・計算結果が間違えてるのか、コードが間違えてるのかわからなくなる時がある

・「n秒問題」を設定で回避しても動作が不安定になったら、再起動

・再起動でもだめならコードのバグ


100万品

普通に100万品やってみると、O(n^2)になるからどうやっても終わらない

なのでK-MEANSみたいにすることにした

・5万品を持ってきて2500個に分類する

・一番近いもを足し合わせる

・重心の中心をもとめて

・再度足し合わせる

これで2500の教師データ(と言っていいのだろうか?)ができるので

教師データ:品データを比較して、2500の中で最も近いグループに属するようにした。

100万品だとGPUつかっても14日(途中で落ちたりなんかんだと)かかりました。

もっといい方法があるんだろう。。。


感想

・品のカテゴリ分けはデータのクレンジング次第で成功すると思う

・それよりもGPUの衝撃がすごい

・GPUパワーを使えるようになったので、武器が増えた感じがする

・CPUバウンドならGPUで解決できるかもしれない希望が持てる

・CUDA-Cが難しい。

・ヘテロジニアスが分かってないとGPUパワーの恩恵にあずかれない

・アセンブラが少しでもわかると分岐と繰り返しの除法に手が出せる

・CUDAのIDEがすごい。ヘテロジニアスなのに楽

・Elasticsearch、KIBANA、機械学習の組み合わせがすごい