iALSの有名な論文
Collaborative Filtering for Implicit Feedback Datasets
交互最小二乗法を利用しているので、user embedding / item embeddingの最適化計算を異なるuser/itemに対して独立して計算することができ、スケーラビリティがある。
user/itemのペアに依存しないため、計算量はとなる。
オリジナルのiALSのデメリットは、埋め込み次元数dに対して3次関数的に増大する点。
Fast als-based matrix factorization for explicit and implicit feedback datasets(https://dl.acm.org/doi/10.1145/1864708.1864726)
上記の論文では、埋め込みベクトルの1要素ずつ計算することで、計算量がとなることを紹介している。ただ、最近のハードウェアはベクトル計算に特化しており、スカラー計算では不利。
ベクトル計算をしているオリジナルiALSと後続のスカラー計算の間を取った、埋め込みのサブベクトル(block)をまとめて計算する手法を既に提案している。
iALS++: Speeding up Matrix Factorization with Subspace Optimization(https://arxiv.org/abs/2110.14044)
今回は、iALS++のブロックサイズ128を利用した。
一般的なiALSのLosは以下の通りで、3項に分解できる。
SGDで最適化する場合に、user/itemの出現頻度に対して正則化させるために
を導入している。
またiALS++では、に
対して指数: [0, 1]を導入した項で置き換えて、Loss最適化する。
の場合は、オリジナル版と同じ。の場合は,と一致する
また、これだけではuser-itemの組み合わせ()に対する正則化が含まれていないため、以下のように変形する。
メトリクス(recall, NDCG)で測定することは有用ではあるが、特定のパラメータの選択がなぜ上手くいかないのかが見えなくなるため、の成分別でプロットする
一部ユーザーをテストデータとしてとっておき、各ユーザーのinteraction80%だけで学習を行う。
残りの20%のinteractionを予測し、ランキング指標を比較。
最終interactionをtestととして取り除き、ランダムに追加した100個を含め101個のitemに対してランキング指標を比較
iALSは以下のメリットがある
デメリット
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)
これらを読んだ前提の論文なので必読
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
簡略化したコード: 中身は結構シンプル
の算出についてはを解くようにコレスキー分解を利用しているのがポイント
アルゴリズム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;
};
}