Implementing IALS in Go

Welcome to the next lesson of this course, where we delve into Implementing Implicit Alternating Least Squares (IALS). Throughout this course, we've progressively constructed a foundation for understanding recommendation systems, moving from explicit rating matrices to utilizing implicit feedback. IALS, our focus for this lesson, is a sophisticated method that leverages implicit data, such as user clicks or views, rather than explicit ratings, to refine recommendations. Let’s explore how this powerful algorithm can elevate your recommendation capabilities by incorporating implicit user preferences.

Before we dive into IALS, let’s quickly revisit how to create the preference (interaction) and confidence matrices in Go. These matrices are the foundation of the IALS algorithm.

Here’s a Go code snippet that demonstrates how to set up these matrices:

package main

import (
    "fmt"
)

func main() {
    // Example watch times for 2 users and 4 items
    watchTimes := [][]int{
        {30, 28, 0, 0}, // User 1
        {0, 0, 15, 22}, // User 2
    }
    numUsers := len(watchTimes)
    numItems := len(watchTimes[0])
    alpha := 40

    // Initialize preference and confidence matrices
    preferenceMatrix := make([][]float64, numUsers)
    confidenceMatrix := make([][]float64, numUsers)
    for u := 0; u < numUsers; u++ {
        preferenceMatrix[u] = make([]float64, numItems)
        confidenceMatrix[u] = make([]float64, numItems)
        for i := 0; i < numItems; i++ {
            if watchTimes[u][i] > 0 {
                preferenceMatrix[u][i] = 1.0
            } else {
                preferenceMatrix[u][i] = 0.0
            }
            confidenceMatrix[u][i] = 1.0 + float64(alpha*watchTimes[u][i])
        }
    }
}

In this code:

• The preferenceMatrix is filled with 1.0 if there is an interaction (watch time > 0), and 0.0 otherwise.
• The confidenceMatrix is calculated as 1 + alpha * watchTime, reflecting our certainty about each interaction.

The IALS algorithm modifies the classic ALS approach to handle implicit feedback by focusing on binary interactions rather than explicit ratings. The goal is to factorize the user-preference matrix into user and item feature matrices, while incorporating confidence levels, to refine prediction accuracy.

In IALS, we aim to approximate the user-item interaction matrix using two lower-dimensional matrices: user factors (U) and item factors (V). The optimization problem involves minimizing the following objective function for implicit feedback:

$\min_{U,V} \sum_{u,i} c_{ui} (p_{ui} - U_u \cdot V_i^T)^2 + \lambda (\| U_u \|^2 + \| V_i \|^2)$

Where:

• $p_{ui}$ represents the preference of user $u$ for item $i$, which is 1 for observed interactions and 0 otherwise.
• $c_{ui}$ is the confidence level associated with each interaction.
• $\lambda$ is the regularization parameter to prevent overfitting.

The predicted interaction $\hat{p}_{ui}$ for user $u$ and item $i$ is calculated by:

$\hat{p}_{ui} = U_u \cdot V_i^T$

IALS alternates between updating user and item factors using confidence-weighted least squares, updating one set of factors while keeping the other fixed:

1. Fix Item Factors and Optimize User Factors:

   • For each user $u$, solve the following equation to get updated user factors:

   $U_u = (V^T C_u V + \lambda I)^{-1} V^T C_u P_u$

   Here, $C_u$ is the diagonal matrix of confidence levels for user $u$, $P_u$ is the preference vector, and $I$ is the identity matrix.

2. Fix User Factors and Optimize Item Factors:

   • For each item $i$, update item factors using:

   $V_i = (U^T C_i U + \lambda I)^{-1} U^T C_i P_i$

   In this case, $C_i$ is the diagonal matrix of confidence levels for item $i$, and $P_i$ is the preference vector.

These updates efficiently capture user behavior and item attractiveness, enhancing the prediction accuracy through iterations.

In these equations, $C_u$ and $C_i$ are diagonal confidence matrices: the values $c_{ui}$ appear only on the diagonal, and every off-diagonal entry is zero. Conceptually, this means each user-item pair contributes its own weight without directly mixing different items or users inside the confidence matrix itself. In optimized implementations, we usually exploit this diagonal structure instead of materializing large dense $N \times N$ matrices for every update.

By solving these optimization problems iteratively, IALS leverages implicit feedback to produce robust recommendations, dynamically adjusting based on user interactions and confidence levels.

Let’s implement the function to update user features in Go. Since Go does not have built-in matrix operations, we will use slices and loops. For solving linear systems, we can use the gonum library, which provides matrix operations and solvers.

We use *mat.Dense when the goal is to lean on Gonum's matrix operations directly. Some practice tasks later switch to [][]float64 to make the data layout and update logic easier to inspect line by line. The underlying math is the same: the choice is mainly about readability versus relying more heavily on library matrix types.

Here’s how you can update user features:

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

// updateUserFeatures updates the user feature matrix in-place.
func updateUserFeatures(
    userFeatures, itemFeatures *mat.Dense,
    confidence, preference [][]float64,
    lambda float64,
) {
    numUsers, numFactors := userFeatures.Dims()
    numItems, _ := itemFeatures.Dims()

    itemFeaturesT := mat.DenseCopyOf(itemFeatures.T())
    lambdaI := mat.NewDiagDense(numFactors, nil)
    for i := 0; i < numFactors; i++ {
        lambdaI.SetDiag(i, lambda)
    }

    // Temporary matrices/vectors to avoid reallocating in each loop
    temp := mat.NewDense(numFactors, numItems, nil)
    A := mat.NewDense(numFactors, numFactors, nil)
    b := mat.NewVecDense(numFactors, nil)
    x := mat.NewVecDense(numFactors, nil)

    for u := 0; u < numUsers; u++ {
        Cu := mat.NewDiagDense(numItems, confidence[u])

        // temp = itemFeaturesT * Cu
        temp.Mul(itemFeaturesT, Cu)
        // A = temp * itemFeatures + lambdaI
        A.Mul(temp, itemFeatures)
        A.Add(A, lambdaI)

        // b = temp * p_u
        pu := mat.NewVecDense(numItems, preference[u])
        b.MulVec(temp, pu)

        // Solve A * x = b
        err := x.SolveVec(A, b)
        if err != nil {
            panic(err)
        }
        for f := 0; f < numFactors; f++ {
            userFeatures.Set(u, f, x.AtVec(f))
        }
    }
}

The updateUserFeatures function iteratively updates each user's feature vector by solving a regularized, confidence-weighted least squares problem. For each user, it constructs a diagonal confidence matrix (Cu) and computes the matrix A and vector b that define the linear system $A x = b$. Here’s a step-by-step breakdown of how this is performed in Go, matching the code:

• Transposing Item Features:
  itemFeaturesT := mat.DenseCopyOf(itemFeatures.T()) creates a transposed copy of the item feature matrix for efficient matrix multiplication.

• Regularization Matrix Creation:
  lambdaI := mat.NewDiagDense(numFactors, nil) initializes a diagonal matrix with lambda on the diagonal, which is added to the weighted matrix to control model complexity and prevent overfitting.

• Iterating Over Users:
  For each user u, the following steps are performed:

  • Confidence Matrix Creation:
    Cu := mat.NewDiagDense(numItems, confidence[u]) creates a diagonal matrix for the confidence values of user u.
  • Weighted Matrix Computation:
    temp.Mul(itemFeaturesT, Cu) computes a confidence-weighted version of the item features. A.Mul(temp, itemFeatures) then forms the regularized Gram matrix for that user. A.Add(A, lambdaI) adds the regularization matrix.
  • Preference Vector Transformation:
    pu := mat.NewVecDense(numItems, preference[u]) creates a vector of preferences for user u. b.MulVec(temp, pu) computes the right-hand side of the equation.
  • Solving for User Features:
    x.SolveVec(A, b) solves the linear system for the user’s feature vector, which is then written back into the user feature matrix with userFeatures.Set(u, f, x.AtVec(f)).

This process ensures that each user's latent factors are adjusted to best explain their implicit feedback, weighted by the confidence in each interaction, and regularized to avoid overfitting.

The process for updating item features is analogous, but the roles of users and items are swapped:

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

// updateItemFeatures updates the item feature matrix in-place.
func updateItemFeatures(
    userFeatures, itemFeatures *mat.Dense,
    confidence, preference [][]float64,
    lambda float64,
) {
    numUsers, numFactors := userFeatures.Dims()
    numItems, _ := itemFeatures.Dims()

    userFeaturesT := mat.DenseCopyOf(userFeatures.T())
    lambdaI := mat.NewDiagDense(numFactors, nil)
    for i := 0; i < numFactors; i++ {
        lambdaI.SetDiag(i, lambda)
    }

    // Temporary matrices/vectors to avoid reallocating in each loop
    temp := mat.NewDense(numFactors, numUsers, nil)
    A := mat.NewDense(numFactors, numFactors, nil)
    b := mat.NewVecDense(numFactors, nil)
    x := mat.NewVecDense(numFactors, nil)

    for i := 0; i < numItems; i++ {
        // Build Ci (diagonal confidence for item i)
        ci := make([]float64, numUsers)
        pi := make([]float64, numUsers)
        for u := 0; u < numUsers; u++ {
            ci[u] = confidence[u][i]
            pi[u] = preference[u][i]
        }
        Ci := mat.NewDiagDense(numUsers, ci)

        // temp = userFeaturesT * Ci
        temp.Mul(userFeaturesT, Ci)
        // A = temp * userFeatures + lambdaI
        A.Mul(temp, userFeatures)
        A.Add(A, lambdaI)

        // b = temp * p_i
        piVec := mat.NewVecDense(numUsers, pi)
        b.MulVec(temp, piVec)

        // Solve A * x = b for x (item feature vector)
        err := x.SolveVec(A, b)
        if err != nil {
            panic(err)
        }
        for f := 0; f < numFactors; f++ {
            itemFeatures.Set(i, f, x.AtVec(f))
        }
    }
}

Now, let’s put everything together into a full IALS implementation in Go. This example uses the gonum library for matrix operations.

package main

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

func randMatrix(rows, cols int) *mat.Dense {
    m := mat.NewDense(rows, cols, nil)
    for i := 0; i < rows; i++ {
        for j := 0; j < cols; j++ {
            m.Set(i, j, rand.NormFloat64()*0.01)
        }
    }
    return m
}

func trainIALS(
    userFeatures, itemFeatures *mat.Dense,
    confidence, preference [][]float64,
    lambda float64, numIters int,
) {
    for iter := 0; iter < numIters; iter++ {
        updateUserFeatures(userFeatures, itemFeatures, confidence, preference, lambda)
        updateItemFeatures(userFeatures, itemFeatures, confidence, preference, lambda)
    }
}

func main() {
    watchTimes := [][]int{{30, 28, 0, 0}, {0, 0, 15, 22}}
    numUsers, numItems, numFactors := len(watchTimes), len(watchTimes[0]), 10
    lambda, alpha, numIters := 40.0, 40.0, 10

    preference, confidence := make([][]float64, numUsers), make([][]float64, numUsers)
    for u := range watchTimes {
        preference[u], confidence[u] = make([]float64, numItems), make([]float64, numItems)
        for i, wt := range watchTimes[u] {
            if wt > 0 {
                preference[u][i] = 1.0
            }
            confidence[u][i] = 1.0 + alpha*float64(wt)
        }
    }

    rand.Seed(time.Now().UnixNano())
    // For reproducible debugging, replace the time-based seed with a fixed one.
    userFeatures := randMatrix(numUsers, numFactors)
    itemFeatures := randMatrix(numItems, numFactors)

    trainIALS(userFeatures, itemFeatures, confidence, preference, lambda, numIters)

    var prediction mat.Dense
    prediction.Mul(userFeatures, itemFeatures.T())
    matPrint(&prediction)
}

func matPrint(X mat.Matrix) {
    fr, fc := X.Dims()
    for i := 0; i < fr; i++ {
        for j := 0; j < fc; j++ {
            fmt.Printf("%8.3f ", X.At(i, j))
        }
        fmt.Println()
    }
}

This code brings together all the components of the IALS algorithm in Go. It starts by preparing the preference and confidence matrices from the raw interaction data (watchTimes). Randomly initialized user and item feature matrices are then iteratively updated using the trainIALS function, which alternates between updating user and item features based on the implicit feedback and confidence levels. After training, the predicted user-item interaction matrix is computed by multiplying the user and item feature matrices, and the results are printed in a readable format. This end-to-end example demonstrates how to implement and train an implicit feedback recommendation model using ALS in Go with the help of the Gonum library for efficient matrix operations.

IALS is designed to work with implicit feedback, such as clicks or views, rather than explicit ratings or watch times. As a result, traditional evaluation metrics like Root Mean Square Error (RMSE), which measure differences between predicted and actual ratings, are not directly applicable to IALS. Instead, evaluation metrics need to focus on binary relevance and ranking quality.

In this unit, our focus is strictly on understanding the implementation of the IALS algorithm itself. In the next unit, we will delve into an appropriate evaluation technique that could be utilized to assess the performance of IALS. It will address the unique nature of implicit feedback and be more aligned with measuring ranking quality and relevance in recommendation tasks.

Here are some tips for optimizing IALS in Go:

• Efficient Loops: Go excels at fast, explicit loops. Use them to avoid unnecessary allocations and keep memory usage low, especially in the inner update loops for users and items.
• Reuse Memory: Reuse matrices and vectors (such as temporary matrices in the update functions) to reduce garbage collection overhead and improve performance.
• Precompute Where Possible: Precompute transposes (e.g., item or user feature transposes) and regularization matrices outside of the inner loops to avoid redundant computation.
• Use Gonum Efficiently: Gonum’s matrix operations are optimized, but avoid creating large temporary matrices inside tight loops if not needed. Prefer in-place operations when possible.

In this lesson, you learned how to implement the IALS algorithm in Go, using implicit feedback to build a recommendation model. You saw how to structure the code to update user and item features and how to use Go’s matrix libraries to solve the necessary linear systems. As you move to practice exercises, focus on understanding the matrix manipulations and the iterative structure of the algorithm — these are key to building effective recommendation systems with implicit data.