Revisiting the Performance of iALS on Item Recommendation Benchmarks

iALSの有名な論文

Collaborative Filtering for Implicit Feedback Datasets

iALS

交互最小二乗法を利用しているので、user embedding / item embeddingの最適化計算を異なるuser/itemに対して独立して計算することができ、スケーラビリティがある。

user/itemのペアに依存しないため、計算量はO(d2S+d3(U+I))O(d^2|S|+d^3(|U|+|I|))となる。

オリジナルのiALSのデメリットは、埋め込み次元数dに対して3次関数的に増大する点。

Fast als-based matrix factorization for explicit and implicit feedback datasets(https://dl.acm.org/doi/10.1145/1864708.1864726)

上記の論文では、埋め込みベクトルの1要素ずつ計算することで、計算量がO(ds+d2(U+I))O(d|s|+d^2(|U|+|I|))となることを紹介している。ただ、最近のハードウェアはベクトル計算に特化しており、スカラー計算では不利。

ベクトル計算をしているオリジナルiALSと後続のスカラー計算の間を取った、埋め込みのサブベクトル(block)をまとめて計算する手法を既に提案している。

iALS++: Speeding up Matrix Factorization with Subspace Optimization(https://arxiv.org/abs/2110.14044)

今回は、iALS++のブロックサイズ128を利用した。

iALS++の解説など

Loss

一般的なiALSのLosは以下の通りで、3項に分解できる。

my image

SGDで最適化する場合に、user/itemの出現頻度に対して正則化させるために

my image

を導入している。

またiALS++では、R(W,H)R(W,H)

対して指数vv: [0, 1]を導入した項で置き換えて、Loss最適化する。

my image

v=0v=0の場合は、オリジナル版と同じ。v=1v=1の場合は,RfreqR^{freq}と一致する

また、これだけではuser-itemの組み合わせ(LIL_I)に対する正則化が含まれていないため、以下のように変形する。

my image
HPO

メトリクス(recall, NDCG)で測定することは有用ではあるが、特定のパラメータの選択がなぜ上手くいかないのかが見えなくなるため、LS,LI,RL_S,L_I,Rの成分別でプロットする

  • iteration
    • 初期パラメータとしては16を設定し、収束状況に応じで値を増減させる。
  • embeddingの初期値の標準偏差(σ\sigma)
    • σ\sigma^*は0.1などの定数。リスケールすることで埋め込み次元数dによる影響を受けにくくさせる。
    • σ=1dσ\sigma=\frac{1}{\sqrt{d}}\sigma^*
  • 埋め込み次元数
    • iALSの成績が悪い大部分はこの値が小さすぎることに起因する。例えばMovieLens20Mでは、2000次元が最も良い結果をもたらす。オーバーフィッティングを引き起こすかもしれないが、経験的にそれでも次元数が大きいほうがよく、L2でオーバーフィッティングは軽減されている。
  • Unobserved Weight(α0{\alpha}_0) and Regularization(λ\lambda)
    • これらは、一緒に探索するのが望ましい。
    • LIL_Iは観測値(y=1y=1) ,LSL_Sは非観測のweight(y=0y=0)を管理している。また次元数が大きくなるほど、正則化の効果も必要となる。そのため、それぞれが同程度の大きさになる必要がある。

結果

検証1

一部ユーザーをテストデータとしてとっておき、各ユーザーのinteraction80%だけで学習を行う。

残りの20%のinteractionを予測し、ランキング指標を比較。

my image
my image
検証2

最終interactionをtestととして取り除き、ランダムに追加した100個を含め101個のitemに対してランキング指標を比較

my image
結論

iALSは以下のメリットがある

  • (iALS++)埋め込み次元数に対して計算量が2次的に増える(iALSのように3次的ではない)
  • グラム行列(Gramian trick)を利用してnegative pairの計算量を軽減している
    • Item Recommendation from Implicit Feedback参照
    • item-contextおけるすべての組み合わせに対する予測値を計算しなくてはいけない部分をitem,contextごとで独立して計算して(それぞれのグラム行列の内積で置き換える)、簡略化するテクニック
  • I個の独立した計算をするので並列化が可能
  • モデルサイズはitemサイズに対して線形に増加するだけで済む
  • 内積でrating予測ができるため、効率的にレコメンドができる。

デメリット

  • ランキングメトリクスに適合していない。(今回の検証ではlambdarankでloss最適化しているモデルに匹敵する結果になったが)
  • context-awareなモデルに対応していない
    • ただし、拡張したモデルは既にいくつか存在する
      • A generic coordinate descent framework for learning from implicit feedback
      • Fast ALS-based tensor factorization for context-aware recommendation from implicit feedback
      • Item recommendation from implicit feedback
  • 行列分解モデルは、新しいフィードバックを受け取るたびに再学習する必要がある
    • SLIM、EASE、オートエンコーダなどのbag of itemモデルは再学習は不要
補足

iALS++: Speeding up Matrix Factorization with Subspace Optimization(https://arxiv.org/abs/2110.14044)

A Generic Coordinate Descent Framework for Learning from Implicit Feedback(https://arxiv.org/abs/1611.04666)

これらを読んだ前提の論文なので必読

my image
実装

https://github.com/google-research/google-research/tree/master/ials/vae_benchmarks

https://github.com/google-research/google-research/blob/master/ials/vae_benchmarks/ialspp_main.cc

簡略化したコード: 中身は結構シンプル

δ\deltaの算出についてはAx=bAx=bを解くようにコレスキー分解を利用しているのがポイント

アルゴリズム10行目にあるunobserved_weightをlocal_item_embeddingを乗せてない気がする

const Recommender::VectorXf ProjectBlock(
    const SpVector &user_history,
    const Recommender::VectorXf &user_embedding,
    const Recommender::VectorXf &local_user_embedding,
    const Recommender::MatrixXf &local_item_embedding,
    const Recommender::VectorXf &prediction,
    const Recommender::MatrixXf &local_gramian,
    const Recommender::MatrixXf &local_global_gramian,
    const float reg, const float unobserved_weight)
{
    int local_embedding_dim = local_item_embedding.cols();

    Recommender::VectorXf new_value(local_embedding_dim);
    // 7-1. $\alpha_0G^{I,\pi}_\pi
    Eigen::MatrixXf matrix = unobserved_weight * local_gramian;
    // 7-2.
    for (int i = 0; i < local_embedding_dim; ++i)
    {
        matrix(i, i) += reg;
    }

    const int kMaxBatchSize = 128;
    auto matrix_symm = matrix.selfadjointView<Eigen::Lower>();
    Eigen::VectorXf rhs = Eigen::VectorXf::Zero(local_embedding_dim);
    const int batch_size = std::min(static_cast<int>(user_history.size()),
                                    kMaxBatchSize);
    int num_batched = 0;
    Eigen::MatrixXf factor_batch(local_embedding_dim, batch_size);
    // 8.
    for (const auto &item_and_rating_index : user_history)
    {
        const int cp = item_and_rating_index.first;
        const int rating_index = item_and_rating_index.second;
        const Recommender::VectorXf cp_v = local_item_embedding.row(cp);
        // 9.1 \hat{y}(u^*,i) - y
        const float residual = (prediction.coeff(rating_index) - 1.0);
        // h_{i,\pi}
        factor_batch.col(num_batched) = cp_v;
        // 9.
        rhs += cp_v * residual;

        ++num_batched;
        if (num_batched == batch_size)
        {
            // 10. outer product
            matrix_symm.rankUpdate(factor_batch);
            num_batched = 0;
        }
    }
    if (num_batched != 0)
    {
        auto factor_block = factor_batch.block(
            0, 0, local_embedding_dim, num_batched);
        // 10.
        matrix_symm.rankUpdate(factor_block);
    }

    // add "prediction" for the unobserved items
    // 6-1. \alpha_0w_{u^*}G^{I,\pi}
    rhs += unobserved_weight * local_global_gramian * user_embedding;
    // add the regularization.
    // 6-2.
    rhs += reg * local_user_embedding;
    // 12.
    Eigen::LLT<Eigen::MatrixXf, Eigen::Lower> cholesky(matrix);
    new_value = local_user_embedding - cholesky.solve(rhs);

    return new_value;
}

void Step(const SpMatrix &data_by_user,
          const int block_start,
          const int block_end,
          VectorXf *prediction,
          F get_user_embedding_ref,
          const MatrixXf &item_embedding,
          const int index_of_item_bias)
{
    // w_{u^*,\pi}
    MatrixXf local_item_emb = item_embedding.block(
        0, block_start, item_embedding.rows(), block_end - block_start);

    // G^{I,\pi} outer product
    MatrixXf local_gramian = local_item_emb.transpose() * local_item_emb;
    // 4. G^{I,\pi}_{\pi} outer product
    MatrixXf local_global_gramian = local_item_emb.transpose() * item_embedding;

    // Used for per user regularization.
    int num_items = item_embedding.rows();

    auto data_by_user_iter = data_by_user.begin(); // protected by m
    {
        while (true)
        {
            int u = data_by_user_iter->first;
            SpVector train_history = data_by_user_iter->second;
            ++data_by_user_iter;

            // \{lambda}
            float reg = RegularizationValue(train_history.size(), num_items);
            VectorXf old_user_emb = get_user_embedding_ref(u);
            VectorXf old_local_user_emb = old_user_emb.segment(
                block_start, block_end - block_start);
            VectorXf new_local_user_emb = ProjectBlock(
                train_history,
                old_user_emb,
                old_local_user_emb,
                local_item_emb,
                *prediction,
                local_gramian,
                local_global_gramian,
                reg, this->unobserved_weight_);
            // Update the ratings
            // 13. w_{u^*,\pi}\leftarrow w_{u^*,\pi}-\delta
            VectorXf delta_local_user_emb =
                new_local_user_emb - old_local_user_emb;
            // 14.
            for (const auto &item_and_rating_index : train_history)
            {
                // 15. \hat{y}(u^*,i)\leftarrow\hat{y}(u^*,i)-\langle\delta,h_{i,\pi}\rangle
                prediction->coeffRef(item_and_rating_index.second) +=
                    delta_local_user_emb.dot(
                        local_item_emb.row(item_and_rating_index.first));
            }
            // Update the user embedding.
            get_user_embedding_ref(u).segment(
                block_start, block_end - block_start) = new_local_user_emb;
        };
    }