Alternating Least Squares Recommendations

Welcome back! In the 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.

Compared with neighborhood-based methods, ALS scales better to large sparse matrices because it works with compact user and item factor representations instead of comparing every user or item directly. It also handles missing values naturally by optimizing only over observed ratings, and its alternating updates are a good fit for efficient linear algebra implementations. In this unit, we still work with explicit ratings; the implicit-feedback version of ALS will come later.

Let's quickly recap and continue from the code you wrote in the previous lesson. You already have code that:

• Reads a user-item rating matrix from a file (explicit_ratings.txt)
• Copies the original matrix for later evaluation
• Randomly marks a proportion of entries as missing (-1) and records their indices

Here is the relevant setup code (with print statements and unnecessary parts omitted):

package main

import (
    "bufio"
    "math/rand"
    "os"
    "strconv"
    "strings"
    "time"
)

func readRatings(filename string) ([][]int, error) {
    var R [][]int
    file, err := os.Open(filename)
    if err != nil {
        return nil, err
    }
    defer file.Close()
    scanner := bufio.NewScanner(file)
    for scanner.Scan() {
        line := scanner.Text()
        ratingStrings := strings.Fields(line)
        var ratings []int
        for _, ratingStr := range ratingStrings {
            rating, err := strconv.Atoi(ratingStr)
            if err != nil {
                return nil, err
            }
            ratings = append(ratings, rating)
        }
        R = append(R, ratings)
    }
    return R, nil
}

func maskRatings(R [][]int, missingRatio float64, rnd *rand.Rand) ([][]int, [][2]int) {
    masked := make([][]int, len(R))
    for i := range R {
        masked[i] = make([]int, len(R[i]))
        copy(masked[i], R[i])
    }
    var missingIndices [][2]int
    for u := range masked {
        for i := range masked[u] {
            if masked[u][i] != -1 && rnd.Float64() < missingRatio {
                masked[u][i] = -1
                missingIndices = append(missingIndices, [2]int{u, i})
            }
        }
    }
    return masked, missingIndices
}

func main() {
    rnd := rand.New(rand.NewSource(time.Now().UnixNano()))
    R, err := readRatings("explicit_ratings.txt")
    if err != nil {
        panic(err)
    }
    originalR := make([][]int, len(R))
    for i := range R {
        originalR[i] = make([]int, len(R[i]))
        copy(originalR[i], R[i])
    }
    missingRatio := 0.1
    R, missingIndices := maskRatings(R, missingRatio, rnd)
    // ALS implementation will go here...
}

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

If you want fully reproducible runs while debugging, you can temporarily replace the time-based seed with a fixed seed such as rand.NewSource(42). The time-based version is fine for exploration, but fixed seeds make it much easier to compare outputs across runs.

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.

Add this function and initialization to your code:

import (
    "gonum.org/v1/gonum/mat"
    "math/rand"
)

func randomMatrix(rows, cols int, rnd *rand.Rand) *mat.Dense {
    data := make([]float64, rows*cols)
    for i := range data {
        data[i] = rnd.Float64() * 0.01
    }
    return mat.NewDense(rows, cols, data)
}

// In main(), after marking missing entries:
numUsers := len(R)
numItems := len(R[0])
numFactors := 3

U := randomMatrix(numUsers, numFactors, rnd)
V := randomMatrix(numItems, numFactors, rnd)

Here, U represents user factors, and V represents item factors, with numFactors indicating the dimensionality of these latent features. We multiply the random initialization by 0.01 so that factor values start small; this helps keep early predictions stable and usually makes optimization behave more smoothly than starting with large random values.

The ALS algorithm is the heart of our lesson. Before diving into the steps involved in ALS, it's essential to understand the optimization problem we're tackling and how ratings are predicted.

The ALS algorithm addresses the problem of predicting missing ratings in a user-item interaction matrix by factorizing it into two matrices: user factors (U) and item factors (V). We aim to approximate the matrix $R$ (user-item ratings) by minimizing the difference between the actual and predicted ratings through the following optimization problem:

Here,

• $R_{ui}$ is the actual rating given by user $u$ to item $i$.
• $U_u$ and $V_i$ are the user and item factor vectors, respectively.
• $\lambda$ is the regularization parameter that penalizes large values of the factors to prevent overfitting.

Importantly, during training, we only work with user-item pairs where the ratings are known. Unknown (missing) ratings are excluded from the optimization process.

Once we have the factorized matrices, the predicted rating $\hat{R}_{ui}$ for user $u$ and item $i$ is calculated as:

Think of the original ratings matrix as a big table where most of the entries are missing. ALS tries to "fill in the blanks" by figuring out what kind of users and what kind of items there are, using only the ratings that are actually present. Each user and each item gets a set of hidden features (the factors), and the predicted rating is just a combination of these features. The algorithm keeps tweaking these features so that, for the ratings we do know, the predictions are as close as possible to the real values—while also making sure the features themselves don't get too large (which helps prevent overfitting). In the end, ALS gives us a way to guess what a user might think of an item they've never rated, based on patterns learned from everyone else's ratings.

The ALS algorithm solves this optimization problem iteratively by alternating between updating user factors and item factors. Here's how ALS specifically tackles this:

1. Fix Item Factors and Optimize User Factors:

   • For each user $u$, it minimizes the error for the observed ratings by updating $U_u$, while keeping V fixed.
   • The update rule for user factors is derived from setting the derivative of the loss function with respect to $U_u$ to zero, resulting in:

   $U_u = (V_u^T V_u + \lambda I)^{-1} V_u^T R_u$

   Here, $V_u$ consists of item factors for items rated by user $u$, and $R_u$ are the actual ratings by user $u$.

2. Fix User Factors and Optimize Item Factors:

   • For each item $i$, it minimizes the error for the observed ratings by updating $V_i$, while keeping U fixed.
   • The update rule for item factors is similarly derived and is given by:

   $V_i = (U_i^T U_i + \lambda I)^{-1} U_i^T R_i$

   Here, $U_i$ consists of user factors for users who rated item $i$, and $R_i$ are the actual ratings for item $i$.

Below is the ALS structure in smaller pieces. Gonum provides the matrix operations and solvers, but the high-level loop is simple: initialize factor matrices, repeatedly update users while holding items fixed, then update items while holding users fixed.

func als(R [][]int, numFactors int, lambda float64, numIterations int, rnd *rand.Rand) (*mat.Dense, *mat.Dense) {
    numUsers := len(R)
    numItems := len(R[0])
    U := randomMatrix(numUsers, numFactors, rnd) // User factors
    V := randomMatrix(numItems, numFactors, rnd) // Item factors

    for iter := 0; iter < numIterations; iter++ {
        // update all users
        // update all items
    }
    return U, V
}

The two update phases follow the same pattern, so it is easier to look at them separately.

First, when updating a user, we collect the items that user actually rated, build a small matrix from those item-factor rows, and solve one regularized least-squares problem:

for u := 0; u < numUsers; u++ {
    var itemIdx []int
    var ratings []float64
    for i := 0; i < numItems; i++ {
        if R[u][i] != -1 {
            itemIdx = append(itemIdx, i)
            ratings = append(ratings, float64(R[u][i]))
        }
    }
    if len(itemIdx) == 0 {
        continue
    }

    V_u := mat.NewDense(len(itemIdx), numFactors, nil)
    for idx, i := range itemIdx {
        V_u.SetRow(idx, V.RawRowView(i))
    }

    var A mat.Dense
    A.Mul(V_u.T(), V_u)
    for f := 0; f < numFactors; f++ {
        A.Set(f, f, A.At(f, f)+lambda)
    }

    b := make([]float64, numFactors)
    for idx, r := range ratings {
        for f := 0; f < numFactors; f++ {
            b[f] += V.At(itemIdx[idx], f) * r
        }
    }

    var x mat.VecDense
    err := x.SolveVec(
        mat.NewSymDense(numFactors, A.RawMatrix().Data),
        mat.NewVecDense(numFactors, b),
    )
    if err != nil {
        continue
    }
    U.SetRow(u, x.RawVector().Data)
}

In this block, mat.NewDense(len(itemIdx), numFactors, nil) creates a temporary matrix to hold just the item-factor rows relevant to user u. V.RawRowView(i) returns row i from the factor matrix as a []float64, so SetRow(...) can copy those values directly into V_u. Then A.Mul(V_u.T(), V_u) forms the Gram matrix for this user's observed items, and adding lambda on the diagonal applies regularization.

The item update is symmetric: instead of gathering rated items for one user, we gather rating users for one item and build the temporary matrix from user-factor rows:

for i := 0; i < numItems; i++ {
    var userIdx []int
    var ratings []float64
    for u := 0; u < numUsers; u++ {
        if R[u][i] != -1 {
            userIdx = append(userIdx, u)
            ratings = append(ratings, float64(R[u][i]))
        }
    }
    if len(userIdx) == 0 {
        continue
    }

    U_i := mat.NewDense(len(userIdx), numFactors, nil)
    for idx, u := range userIdx {
        U_i.SetRow(idx, U.RawRowView(u))
    }

    var A mat.Dense
    A.Mul(U_i.T(), U_i)
    for f := 0; f < numFactors; f++ {
        A.Set(f, f, A.At(f, f)+lambda)
    }

    b := make([]float64, numFactors)
    for idx, r := range ratings {
        for f := 0; f < numFactors; f++ {
            b[f] += U.At(userIdx[idx], f) * r
        }
    }

    var x mat.VecDense
    err := x.SolveVec(
        mat.NewSymDense(numFactors, A.RawMatrix().Data),
        mat.NewVecDense(numFactors, b),
    )
    if err != nil {
        continue
    }
    V.SetRow(i, x.RawVector().Data)
}

The same idea appears here with roles reversed: U_i contains only the user-factor rows associated with item i, and Gonum again uses A.Mul(...) to build the regularized normal-equation matrix for the item update.

Both phases follow the same solve pattern. Once A and b are ready, Gonum handles the linear solve and gives back the updated factor vector:

b := make([]float64, numFactors)
// fill b from observed ratings

var x mat.VecDense
err := x.SolveVec(
    mat.NewSymDense(numFactors, A.RawMatrix().Data),
    mat.NewVecDense(numFactors, b),
)
if err != nil {
    continue
}

Here, mat.NewVecDense(...) wraps the right-hand side vector b, and mat.NewSymDense(...) wraps A as a symmetric matrix because V_u^T V_u + lambda I and U_i^T U_i + lambda I are symmetric by construction. Finally, x.SolveVec(...) solves A * x = b and stores the result in x.

So the repeated ALS update pattern is:

1. Gather observed ratings.
2. Build a temporary factor matrix from the relevant rows.
3. Form the regularized system A * x = b.
4. Solve it and write the result back into U or V.

If SolveVec fails, it usually means the system is numerically unstable or poorly conditioned. In practice, increasing lambda, reducing factor dimensionality, or checking the data for very sparse rows can help.

Because ALS adds lambda I, the matrix we solve is regularized and is typically much better behaved numerically than an unregularized system. Still, convergence is not automatic: larger numFactors can capture more structure but also increase overfitting risk, while larger lambda increases stability but may underfit.

• Result:
  After the specified number of iterations, the function returns the optimized user and item factor matrices, which can be used to predict missing ratings.

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:

import (
    "math"
)

func predictRatings(U, V *mat.Dense) *mat.Dense {
    var pred mat.Dense
    pred.Mul(U, V.T())
    return &pred
}

func calculateRMSE(originalR [][]int, predictedR *mat.Dense, missingIndices [][2]int) float64 {
    sum := 0.0
    for _, idx := range missingIndices {
        u, i := idx[0], idx[1]
        diff := float64(originalR[u][i]) - predictedR.At(u, i)
        sum += diff * diff
    }
    mse := sum / float64(len(missingIndices))
    return math.Sqrt(mse)
}

After optimizing the user and item factors with ALS, we use matrix multiplication to generate predicted ratings for all user-item pairs. The predictRatings function multiplies the user factor matrix U with the transpose of the item factor matrix V, resulting in a matrix of predicted ratings.

To assess how well the model predicts the ratings that were intentionally masked (i.e., treated as missing during training), we use the calculateRMSE function. This function computes the root mean square error (RMSE) between the predicted ratings and the actual ratings at the masked positions. RMSE is a common metric for evaluating prediction accuracy: a lower RMSE indicates that the predicted ratings are closer to the true values.

One important detail is that ALS predictions are continuous float64 values, even when the original ratings are integers from 1 to 5. For RMSE, it is common to keep these raw floating-point predictions as-is. In a presentation layer, you might later clip or round them, but that is separate from the training and evaluation logic shown here.

Here’s how you use these functions in main:

func main() {
    rnd := rand.New(rand.NewSource(time.Now().UnixNano()))
    R, err := readRatings("explicit_ratings.txt")
    if err != nil {
        panic(err)
    }
    originalR := make([][]int, len(R))
    for i := range R {
        originalR[i] = make([]int, len(R[i]))
        copy(originalR[i], R[i])
    }
    missingRatio := 0.1
    R, missingIndices := maskRatings(R, missingRatio, rnd)

    numFactors := 3
    lambdaReg := 0.1
    numIterations := 20

    U, V := als(R, numFactors, lambdaReg, numIterations, rnd)
    predictedR := predictRatings(U, V)
    rmse := calculateRMSE(originalR, predictedR, missingIndices)
    fmt.Printf("RMSE for the excluded items: %.4f\n", rmse)
}

These hyperparameters are simple teaching defaults, not universal best values. numFactors controls model capacity, lambdaReg controls regularization strength, and numIterations controls how long we alternate the updates. In practice, you would tune them based on validation performance and dataset size.

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. 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!