numpyでforで計算している部分を高速化したい。

Question

やりたいこと

現在forループで実装している部分を、numpyのメソッドを使うなどして高速化したいと考えております。
(初めにお伝えしますが、本文中に何度かLightGBMに関する話題が登場しますが、実装したいこと自体にはLightGBMは関係なく本ページ下部の「やったこと」章にあるコードのforループを高速化したいだけです。LightGBMに詳しくない方もブラウザバックせずにご一読いただければ嬉しいです。)

具体的には、LightGBMのrambdarankでグループ内での予測順1位かつ正解順1位のaccuracyを求めるカスタムメトリックを作成したいです。
しかし、自分で作成したメトリックはfor文を使っているため学習が非常に遅くなってしまいます。
例えば、以下のようにpredsとlabelとgroupを与えられます。

• groupはpredsとlabelの要素が何個づつグループに所属しているかを示しています。
• predsはLightGBMから渡される予測値です。大きいほうがより高い予測順位となります。
• labelは学習に使用する正解順位のラベルです。0,1,2のいずれかの値を持ち、最大値の2は各グループで必ず1回だけ登場します。大きいほうがより高い正解順位となります。

preds = [-0.112,0.025,0.998,1.112,1.226,0.520,2.112,-0.220,2.174,1.552]
label = [0,0,1,2,0,2,1,0,2,1]
group = [4,3,3]

グループ内で一番大きなpredsを持っている要素のlabelが2であれば正しく予測できている、それ以外だと正しく予測できていないことになります。

文字で説明しても分かりづらいと思いますので表で表現してみます。

• index列はinputとlabelのインデックスです。
• preds列はpredsの値です。
• label列はlabelの値です。
• 「----」となっている行でgroupに基づくグループ分けを行い、predsとlabelの要素を区切ります。

この場合ですと、indexが03、46、7~9の3グループに分けられ、それぞれのグループの中で最大のpredsを持つ行のlabelが2であれば、そのグループは正しく予測できている(TorF = true)、それ以外だと正しく予測できていない(TorF = false)となります。
3グループのうち正しく予測しているのは2グループなので、求めたい値(accuracy)は2/3=0.67となります。

|index|preds|label|T or F|
|:--|:--|||
|0|-0.112|0||
|1|0.025|0||
|2|0.998|1||

3	1.112	2	true
4	1.226	0
5	0.520	2
6	2.112	1	false
----	----	----	----
7	-0.220	0
8	2.174	2	true
9	1.552	1

やったこと

次のようなコードで実装しました。

def accuracy(preds, data):
    BEST_LABEL = 2
    label = data.get_label()
    group = data.get_group()
    
    i = 0
    acc = 0
    for n in group:
        max = preds[i:i+n].argmax()
        acc += (label[i+max] == BEST_LABEL)
        i += n
    acc = acc/len(group)
    return "accuracy", acc, True

しかしこのコードだとforで回しており学習が非常に遅くなってしまうので、numpyのメソッドを使用するなどで高速化を図りたいです。
自分では良い実装が思いつかなかったため、皆様のお力をお借りしたいと考えました。よろしくおねがいします。

環境

Windows10
Python 3.10.0

Comments

[bsdfan]

各groupの値とか、groupの総数(len(group))は、実際はどれぐらいなのでしょうか？

[Luna_rab]

実際は各groupの値は10~20程度、len(group)は学習に使用するデータの量にもよりますが10000～30000程度を想定しています。
また、1回の学習でおよそ500～1000回ほどaccuracy関数が呼ばれます。

Answer 1

データはダミーですが、比較用に測定結果を貼っておきます。solve1が(ほぼ)質問者さんのコード、solve2がppaulさんのコードです。

私の環境では、

• solve1: 0.0002551000000000636秒
• solve2: 0.017054800000000037秒
• solve2(2回目): 0.01655569999999995秒

でした。

import pandas as pd
from time import perf_counter
import numpy as np

preds = [7,8,9,10,8,7,9,7,9,-10] * 100
label = [0,0,1,2,0,2,1,0,2,1] * 100
group = [4,3,3] * 100


def solve1(preds, label, group):
    preds = np.array(preds)
    BEST_LABEL = 2
    i = 0
    acc = 0
    for n in group:
        max = preds[i:i+n].argmax()
        acc += (label[i+max] == BEST_LABEL)
        i += n
    return acc/len(group)


def solve2(preds, label, group):
    group2 = sum([[i]*g for i,g in enumerate(group)], [])
    df = pd.DataFrame({'preds':preds, 'label':label, 'group':group2})
    return df.sort_values('preds').groupby('group').apply(lambda d: d.iloc[-1]['label']==2).mean()


st = perf_counter()
res1 = solve1(preds, label, group)
ed = perf_counter()
print(ed - st, res1)

st = perf_counter()
res2 = solve2(preds, label, group)
ed = perf_counter()
print(ed - st, res2)

st = perf_counter()
res2 = solve2(preds, label, group)  # 2回目
ed = perf_counter()
print(ed - st, res2)

Comments

[Luna_rab]

検証していただきありがとうございます。
やはりpandasの方が遅くなってしまいますか...

[ppaul]

solve2を一回実行した後で2 回目の実行の時間を計るとどうなるかやってみてもらえませんか。
pandasのようなライブラリでは、最初に実行するときに追加のライブラリを読み込むことがあるので、そのための時間も見かけ上の実行時間となることがあります。

[ppaul]

また、pandasの中身(values)はnumpy.ndarrayですので、ライブラリ読み込みを除いてpandasでやって遅いものはnumpyでやっても遅くなる可能性が高いです。
それぞれのグループの長さが４程度だとあまり速くないとは思います。numpyが使っているSIMD長は最近のCPUだと512ビットですのでint32の場合で10を超えるともっと速くなるでしょう。

[退会済みユーザー]

2回目の計測コードを入れてみましたが、0.017 -> 0.0165のように微妙に改善されただけでした。

[Luna_rab]

pandasの中身がndarrayとのことですが、それは列方向に対してだったと記憶しています。ppaulさんのコードではapplyを使用しているのでベクトル処理は行われていないのではないでしょうか？(pandasの処理でapplyを使うと遅くなるのは有名な話だったと思います。)

Answer 2

下記でどうでしょう。

numpy.maximum.reduceat() で、各グループ毎の最大値を求めて、
その最大値に等しいかつ、labelが2の場所を数えています。

def accuracy(preds, data):
    BEST_LABEL = 2
    label = data.get_label()
    group = data.get_group()

    group_max = np.maximum.reduceat(preds, [0, *np.cumsum(group[:-1])])
    acc = np.sum((preds == np.repeat(group_max, group)) & (label == BEST_LABEL))
    acc = acc/len(group)
    return "accuracy", acc, True

手元のテストコードで、元のより1.5倍ちょっと早くなる程度でした。
([0, *np.cumsum(group[:-1])]が固定で、毎回計算する必要がないなら、この部分を外に出すともう少し速くできそうです)

こういうのの高速化はnumbaのほうが良さそうなので、そちらも試してみましたが2倍程度しか速くなりませんでした。
参考までにコードは下記の通りで、元のコードにjitをつけただけで試しています。(引数はndarrayである前提)
もともと、それほど遅くなるようなforの使い方でもないように思います。

from numba import jit

@jit
def _accuracy(preds, label, group):
    BEST_LABEL = 2
    i = 0
    acc = 0
    for n in group:
        max = preds[i:i+n].argmax()
        acc += (label[i+max] == BEST_LABEL)
        i += n
    return acc/len(group)


def accuracy(preds, data):
    label = data.get_label()
    group = data.get_group()

    return "accuracy", _accuracy(preds, label, group), True

Comments

[Luna_rab]

http://numba.pydata.org/numba-doc/latest/user/5minguide.html
Numbaについて上記ガイドでざっくり調べてみましたが、まさにNumbaで速くできそうな感じがしますので一度それで実装してみたいと思います。
numbaでもあまり早くならなかったとのことですが、初回呼び出し時にコンパイルしているようなので繰り返し関数を呼ぶような用途なら、実際はもう少し高速化が狙えるのではないでしょうか。

[bsdfan]

jitコンパイルの時間を除いて、こちらの環境とテストデータで2倍程度でした。
データの大きさによって変わると思いますし、実際の環境で試してみる価値はあります。

[Luna_rab]

既にコンパイル時間を除いて計算していただいていましたか。ありがとうございます。

[Luna_rab]

numbaで計算したところ、bsdfanさんの試算通り計算時間がおおよそ半分になりました。accuracyメトリックなしでの計算時間とaccuracyメトリック込みでの計算時間で差がほとんどなくなったため、当初の目的は達成できました。ありがとうございます。

Answer 3

numpyよりはpandasの方が向いています。

pandasを使うと以下です。

import pandas as pd
preds = [7,8,9,10,8,7,9,7,9,-10]
label = [0,0,1,2,0,2,1,0,2,1]
group = [4,3,3]

group2 = sum([[i]*g for i,g in enumerate(group)], [])
df = pd.DataFrame({'preds':preds, 'label':label, 'group':group2})
accuracy = df.sort_values('preds').groupby('group').apply(lambda d: d.iloc[-1]['label']==2).mean()
print(accuracy)

実行結果

>>> print(accuracy)
0.6666666666666666

Comments

[退会済みユーザー]

この手の処理でpandasを使うと遅くないですか?

[Luna_rab]

実測したわけではないのでわからないですが、それは自分も気になっていました。