こんにちは。nadareです。
普段は業務でレコメンドエンジンをスクラッチで実装しています。
今回はレコメンドでよく使う、履歴との重複を高速に判定する方法を紹介します。
どんな時に使うか
今回紹介するテクニックは主に以下のようなケースで利用します。
- 学習時に負例からユーザーが別の機会でインタラクションするものを除くケース
- 予測時に予測結果からユーザーの履歴に既に含まれているものを除くケース
このテクニックは例えばデジタルコンテンツの購入のように、一度購入した商品をもう一度購入することはないようなケースで良く用います。
例えば1ではNNのモデルでインタラクションのあるアイテムを正例を1、それ以外のバッチ内の他の正例を負例として0で予測するケースを考えます。バッチ内の他の正例が全て0として扱えればいいのですが、中には過去に購入済みであったり正例と同じアイテムであって、本当に無関係な負例と同様0として予測するのには不適切で、マスクをかけたいことがあります。
2のケースは、予測時に既にユーザーが購入している、閲覧済みであるといった理由でレコメンドに適さないアイテムをレコメンドの候補から外すケースです。もちろん予測結果をDBに入れて後からSQL等で重複を判定してもよいのですが、後の方で除外するほどレコメンドの件数を確保しにくく、かつ予測結果の並び替えなどを上手く働かせられなくなります。
具体的なアルゴリズム
1のケースで想定してみましょう。バッチサイズがN=4096で、判定する負例の数も4096、ユーザーはH=100の履歴を持つとします。
愚直に判定するケース
N人のユーザーごとに愚直にN個の負例とHの履歴の衝突を計算すると、O(HN^2)≒1.7Gの計算が必要になり重いです。
pythonでループを回すには当然遅く、行列で一括で計算するには空間計算量が厳しいです。
二分探索を用いるケース
負例はバッチ内で共通なので、これをソートして昇順に並べます。ソートはO(Nlog(N))で可能です。
ソートされた数字の配列Lの中にある数字aがあるかは以下のようなコードで判定できます。
ix = np.searchsorted(L, a) % len(L)
hit = L[ix] == a
このhitした部分についてnp.where等を使ってマスクをかけます。
二分探索の計算量は一回当たりlog(L)のため、O(HNlog(N))≒5.0Mの計算で可能になり、大幅に速度が改善します。
実際の運用
アルゴリズムの説明のため簡略化しましたが、実際は様々なロジックと合わせて上記ロジックを運用します。
ユーザーごとに履歴の長さは異なり、大抵のユーザーの履歴は一桁二桁であるのに対して、稀により大きな桁数の履歴を持つユーザーが現れます。このような場合、大きいユーザーに合わせて密な行列を作ると殆どのユーザーで無駄な計算をしてしまうため、tf.RaggedTensorを使います。また、レコメンドの履歴や推薦結果は人気なものにある程度偏るため、ユニークをとってから計算するなどして同じ計算を極力省きます。
まとめ
二分探索を用いて履歴との衝突を判定するニッチなテクニックを紹介しました。
二分探索は基本的なアルゴリズムですが、しっかり押さえておくことで計算量を大幅に減らすことができます。
競プロ等を通じて、アルゴリズムの基礎力を高めていきましょう。