Text Embedding と LSH を用いた高速商品バリアント判定

こんにちは、カウシェで機械学習エンジニアをしている白川です。
先日、下記の記事でレコメンドの実装の裏側についてご紹介しました。

この記事の内容を人に説明する機会があって読み直していたら商品バリアント判定部分のアルゴリズムの説明が抜けている事に気づいたので、その部分を切り出してちょっとした Tips としてご紹介したいと思います。

商品バリアントって？

同一商品の色違い・サイズ違い・柄違い・味違い…などを商品バリアントと呼びます。カウシェの扱う商品にも商品バリアントが無数にあります。

商品レコメンドをする場合など、この商品バリアントを適切にコントロールしないと、同一商品のバリアントばかりレコメンドされるようなことになってしまったりします。

そのためカウシェの現状の商品レコメンド機能では、同一商品のバリアントからランダムにひとつ選び、ほかは除外することにより、同一商品のバリアントがレコメンドを占領しないようにしています。

商品バリアントの特定タスク

本来的は DB 上でバリアントが特定できる状況が好ましいのですが、現状ではそれが難しいのが実情でした。そのため、レコメンド機能を作るに当たっては、何らかのロジックを通じてバリアントの特定を行う必要がありました。

商品点数はかなり多いため、なるべくスケーラブルで高速・軽量なロジックにしたく、下記のようなアルゴリズムで商品バリアントを特定することにしました。

バリアント特定アルゴリズム

• 下記のバリアント生成アルゴリズムで生成されたバリアント ID と事業者 ID（同一販売者であることを表す ID）、価格などが同一の商品をバリアントとする。

バリアント ID 生成アルゴリズム

1. 商品のタイトル情報にたいして Text Embedding モデル（レコメンドで使用したのと同じ BERT ベースのモデル）を適用し、商品の Embeddings を作る

2. 1 の商品 Embeddings を L2 ノルムが 1 になるように正規化

3. LSH により、2 の Embeddings を 8 次元の 0/1 配列に量子化

4. 3 の 8 次元 0/1 配列を 2 進数で読み取り整数化

バリアント ID の生成アルゴリズムがコアは LSH（Locality Sensitive Hashing）なのですが、下記の論文の方法を使いました。

Charikar, Moses 2002. Similarity Estimation Techniques from Rounding Algorithms In Proceedings of the 34th Annual ACM Symposium on Theory of Computing.
[pdf]

実装はとてもシンプルで、下記はそのコードです。

import numpy as np


class LSH:
    def __init__(self, embed_dim, code_length):
        """LSH for angular distance"""
        self.planes = np.random.normal(0, 1, (code_length, embed_dim))

    def __call__(self, embs):
        """compute LSH codes"""
        return (embs.dot(self.planes.T) > 0).astype(int)

    def to_int(self, codes):
        """convert each code to a integer"""
        return codes.dot(np.asarray([2**i for i in range(codes.shape[1])]))

今回は 8 次元の 0/1 配列に変換したのですが、これは空間を原点を通るランダムな平面で 8 回切ったときに同じセグメントに存在する商品はタイトルが十分近いとみなしていることになります。いくつか実験し、事業者 ID と価格などが一致しているという前提のもとでは 8 次元で十分そうでした。

終わりに

実用性と高速化を兼ね備えたアルゴリズムを考えるのは楽しいですね！有用でシンプルな Tips はこれからも公開していけたらと思っています。