想定される状況
- 自然言語をBERTなど単語分散表現を用いてベクトル化
- cos 類似度を計算し、文章同士の類似度を数値化
- 類似度の高いコンテンツ同士を似ているコンテンツとみなし、レコメンドするためのデータセットを作成する
以上の状況において、 O(N^2) のデータ量となるが、 「コンテンツデータが100万件あります！」みたいな、 O(N) = 10^6 規模のデータセットとなると、計算コストなどが大きくなり計算が容易ではないという問題が発生します。（実体験）
その解決策をまとめておきます。
計算コストの削減
- ベクトルの L2 正規化
- 行列の内積を演算
- 正規化済みのベクトルなのでこの演算結果で得られるベクトルが類似度ベクトルとなる
計算アルゴリズム
正規化したN個の文章ベクトルをそれぞれ
V_i (i = 1 ... N)
とするとき、文章ベクトルを縦方向に結合し、まとめた行列を
A = \left( \begin{array}{c} V_1 \\ V_2 \\ \vdots \\ V_N \end{array} \right)
と定義し、類似度行列 W を以下のように得る。
W = A \cdot A^{\mathrm{T}}
このとき W は N × N 行列となる。
それぞれの要素は各アイテム間の類似度をそのまま示す。例えば、
W_{12}
は、1個目のアイテムと2個目のアイテムの類似度を示す。
データ量の削減
上記の計算コストの削減では計算量は減らせるものの、データ量は変わらず O(N^2) のままである。
そこで、N の数を減らす工夫が必要となる。
- クラスタリングによるデータセットの分割
- 混交ガウスモデルなど教師なしクラスタリングを使い、データをK個のデータに分割する
- 類似度は Top M 個のみを採用する
- 例えば、類似度の高い順に並べ替え、上位30個のみ保持することにすれば、類似度行列のデータ量は N × 30 となる
- 特徴量ベクトルの集合行列 A の分割
- 詳細は後述する
ベクトルの集合行列の分割方式
特徴量ベクトルの集合行列 A
A = \left( \begin{array}{c} V_1 \\ V_2 \\ \vdots \\ V_N \end{array} \right)
を、縦方向にM個に分割する。例えば、1個の行列に100個ずつのベクトルを含むとすると、
A_1 = \left( \begin{array}{c} V_1 \\ \vdots \\ V_{100} \end{array} \right) \\
A_2 = \left( \begin{array}{c} V_{101} \\ \vdots \\ V_{200} \end{array} \right) \\
A_3 = \left( \begin{array}{c} V_{201} \\ \vdots \\ V_{300} \end{array} \right) \\
\vdots \\
A_M = \left( \begin{array}{c} V_{N-99} \\ \vdots \\ V_{N} \end{array} \right)
このとき、A_1 に対する類似度行列は、
W_1 = A_1 \cdot A^{\mathrm{T}}
であり、W_1 の大きさは 100 × N 行列となる。この方法では計算コストも同様に減らせる。
最終的に、W_1 ... W_M を縦方向に結合したものは W に一致するので計算上の差異はない。
\left( \begin{array}{c} W_1 \\ \vdots \\ W_M \end{array} \right) = W