Introduction to ALS and Collaborative Filtering

Welcome back! In our previous lesson, you explored the foundation of user-item explicit rating matrices used in recommendation systems. Today, we'll expand on that knowledge by diving into one of the powerful techniques for collaborative filtering known as the Alternating Least Squares (ALS) algorithm.

Recommendation systems have become essential in offering personalized experiences, with collaborative filtering being a primary method. Collaborative filtering works by understanding user preferences through their past interactions and leveraging similar users or items to provide recommendations. The ALS algorithm is a matrix factorization approach that enables us to predict missing ratings effectively, making it a valuable tool in recommendation systems.

Recap of the Setup

Before we proceed with implementing the ALS algorithm, let's quickly recap the fundamental steps we covered in the previous lesson for setting up our environment. You may remember how we:

  1. Read data from a file to create a user-item interaction matrix.
  2. Marked some entries with -1 to simulate missing data for testing purposes while saving actual ratings for future evaluation.

Here's a concise code snippet capturing the setup in JavaScript:

const fs = require('fs');

// Read user-item interaction matrix from file
let R = [];
const data = fs.readFileSync('explicit_ratings.txt', 'utf8');
const lines = data.trim().split('\n');
for (let line of lines) {
    const ratings = line.trim().split(' ').map(Number);
    R.push(ratings);
}

// Mark some entries as missing (-1) for testing
const missingRatio = 0.1; // Density of missing entries
const numUsers = R.length;
const numItems = R[0].length;

// Collect all indices of non-missing entries
let allIndices = [];
for (let u = 0; u < numUsers; u++) {
    for (let i = 0; i < numItems; i++) {
        if (R[u][i] !== -1) {
            allIndices.push([u, i]);
        }
    }
}

// Randomly select indices to mark as missing
function shuffle(array) {
    for (let i = array.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [array[i], array[j]] = [array[j], array[i]];
    }
}
shuffle(allIndices);
const numMissing = Math.floor(missingRatio * allIndices.length);
const missingIndices = allIndices.slice(0, numMissing);

// Mark selected entries as missing
for (let [u, i] of missingIndices) {
    R[u][i] = -1;
}

// Save the original matrix for evaluation
const originalR = lines.map(line => line.trim().split(' ').map(Number));

This setup is crucial, as it establishes the data landscape we will work with throughout the ALS implementation.

Initializing User and Item Factors

To predict missing ratings using ALS, we need to decompose the interaction matrix into two matrices — user and item factors. These factors capture latent characteristics that influence user preferences and item popularity. Initially, these factors are filled with random values, which will then be optimized through ALS iterations.

const { Matrix } = require('ml-matrix');

const numFactors = 3;

// Random initialization of user and item factors
let U = Matrix.rand(numUsers, numFactors).mul(0.01); // User factors
let V = Matrix.rand(numItems, numFactors).mul(0.01); // Item factors

Here, U represents user factors and V represents item factors, with numFactors indicating the dimensionality of these latent features.

Optimization Problem
Solving with Alternating Least Squares
Implementing the Algorithm
const { solve, Matrix } = require('ml-matrix');

const lambdaReg = 0.1;
const numIterations = 20;

function trainALS() {
    for (let iteration = 0; iteration < numIterations; iteration++) {
        // Update user factors
        for (let u = 0; u < numUsers; u++) {
            // Find indices of items rated by user u
            let ratedItems = [];
            let ratings = [];
            for (let i = 0; i < numItems; i++) {
                if (R[u][i] !== -1) {
                    ratedItems.push(i);
                    ratings.push(R[u][i]);
                }
            }
            if (ratedItems.length > 0) {
                // V_u: matrix of item factors for items rated by user u
                let V_u = new Matrix(ratedItems.length, numFactors);
                for (let idx = 0; idx < ratedItems.length; idx++) {
                    V_u.setRow(idx, V.getRow(ratedItems[idx]));
                }
                // R_u: vector of ratings by user u
                let R_u = Matrix.columnVector(ratings);

                // Compute (V_u^T V_u + lambda * I)
                let A = V_u.transpose().mmul(V_u);
                for (let f = 0; f < numFactors; f++) {
                    A.set(f, f, A.get(f, f) + lambdaReg);
                }
                // Compute V_u^T R_u
                let b = V_u.transpose().mmul(R_u);

                // Solve for U[u]
                let x = solve(A, b);
                U.setRow(u, x.transpose().to1DArray());
            }
        }

        // Update item factors
        for (let i = 0; i < numItems; i++) {
            // Find indices of users who rated item i
            let ratedUsers = [];
            let ratings = [];
            for (let u = 0; u < numUsers; u++) {
                if (R[u][i] !== -1) {
                    ratedUsers.push(u);
                    ratings.push(R[u][i]);
                }
            }
            if (ratedUsers.length > 0) {
                // U_i: matrix of user factors for users who rated item i
                let U_i = new Matrix(ratedUsers.length, numFactors);
                for (let idx = 0; idx < ratedUsers.length; idx++) {
                    U_i.setRow(idx, U.getRow(ratedUsers[idx]));
                }
                // R_i: vector of ratings for item i
                let R_i = Matrix.columnVector(ratings);

                // Compute (U_i^T U_i + lambda * I)
                let A = U_i.transpose().mmul(U_i);
                for (let f = 0; f < numFactors; f++) {
                    A.set(f, f, A.get(f, f) + lambdaReg);
                }
                // Compute U_i^T R_i
                let b = U_i.transpose().mmul(R_i);

                // Solve for V[i]
                let x = solve(A, b);
                V.setRow(i, x.transpose().to1DArray());
            }
        }
    }
}

trainALS();

The algorithm iterates over these two steps, alternating between updating user and item factors until convergence or a predetermined number of iterations is reached. This alternating optimization procedure ensures that each step solves a least-squares problem, making the factor updates computationally efficient.

Predicting Ratings and Evaluating with RMSE

Once user and item factors are optimized, we can predict the missing ratings by matrix multiplication of the two factors. To evaluate the model's accuracy, we calculate the Root Mean Square Error (RMSE) for excluded items:

// Predict the ratings
const predictedR = U.mmul(V.transpose());

// Calculate RMSE for excluded items
function calculateRMSE(originalR, predictedR, missingIndices) {
    let sumSq = 0;
    for (let [u, i] of missingIndices) {
        const actual = originalR[u][i];
        const predicted = predictedR.get(u, i);
        sumSq += Math.pow(actual - predicted, 2);
    }
    const mse = sumSq / missingIndices.length;
    return Math.sqrt(mse);
}

const rmse = calculateRMSE(originalR, predictedR, missingIndices);
console.log(`RMSE for the excluded items: ${rmse.toFixed(4)}`);

The RMSE offers insight into the prediction error for missing values. A lower RMSE indicates better predictive performance.

Summary and Preparation for Practice Exercises

In this lesson, you've successfully implemented the ALS algorithm to tackle collaborative filtering challenges within recommendation systems. You've learned to construct user-item matrices, initialize factors, and update them to predict missing ratings. This understanding equips you with a robust technique for building recommendation models.

Now, it's time to consolidate this theoretical understanding with hands-on exercises in the CodeSignal IDE. These exercises are designed to reinforce the concepts learned, allowing you to apply ALS in varied scenarios. You've made significant progress, so keep up the great work as you continue to explore the exciting world of recommendation systems!

Previous
Next
Sign up
Join the 1M+ learners on CodeSignal
Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal