Implementing Factorization Machines

Introduction to Factorization Machines

Welcome to this lesson on factorization machines, an important model in the realm of recommendation systems. Factorization machines, or FM, excel in capturing interactions between variables, making them a powerful tool for both regression and classification tasks. For instance, they can predict a rating (regression) or calculate the likelihood of a recommendation (classification).

Review of Dataset Preparation

Before we delve into the implementation of a factorization machine, let's briefly revisit the dataset preparation process from the previous lesson. Even though we won't repeat the entire code here, it's crucial to remember the structure we've established. In the prior lesson, you learned how to load JSON files and create a user-item interaction matrix using dummy variables. Additionally, you enriched the dataset with auxiliary features like user preferences and genre similarity. These steps laid the groundwork for accurately predicting ratings in a recommendation system. Recall the importance of these preparatory steps as we move forward.

Theory Behind

\hat{y}(\mathbf{x}) = w_0 + \sum_{i=1}^{n} w_i x_i + \sum_{i=1}^{n} \sum_{j=i+1}^{n} \langle \mathbf{v}_i, \mathbf{v}_j \rangle x_i x_j

Latent Vectors

[v_{u1,1}, v_{u1,2}]

Feature	Latent Vector
user1	$[v_{u1,1}, v_{u1,2}]$
user2	$[v_{u2,1}, v_{u2,2}]$
user3	$[v_{u3,1}, v_{u3,2}]$
item1	$[v_{i1,1}, v_{i1,2}]$
item2	$[v_{i2,1}, v_{i2,2}]$
item3	$[v_{i3,1}, v_{i3,2}]$
uf1	$[v_{uf1,1}, v_{uf1,2}]$
uf2	$[v_{uf2,1}, v_{uf2,2}]$
if1	$[v_{if1,1}, v_{if1,2}]$
if2	$[v_{if2,1}, v_{if2,2}]$

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Implementing the Factorization Machine Model: Part 1

Let's move on to the implementation of the factorization machine model. We'll break this into parts to ensure clarity.

First, let's define the __init__ method to initialize the required data.

Python

import numpy as np

class SimpleFactorizationMachine:
    def __init__(self, n_factors, n_features, learning_rate=0.01, epochs=100, reg=0.01):
        self.n_factors = n_factors
        self.learning_rate = learning_rate
        self.epochs = epochs
        self.reg = reg
        
        self.w0 = 0  # Global bias term
        self.W = np.zeros(n_features)  # Linear coefficients
        self.V = np.random.normal(0, 0.1, (n_features, n_factors))  # Interaction factors

import numpy as np

class SimpleFactorizationMachine:
    def __init__(self, n_factors, n_features, learning_rate=0.01, epochs=100, reg=0.01):
        self.n_factors = n_factors
        self.learning_rate = learning_rate
        self.epochs = epochs
        self.reg = reg
        
        self.w0 = 0  # Global bias term
        self.W = np.zeros(n_features)  # Linear coefficients
        self.V = np.random.normal(0, 0.1, (n_features, n_factors))  # Interaction factors

In the __init__ method, we initialize several key parameters of the factorization machine.

n_factors: This defines the number of components in each latent vector. It represents the dimensionality of the latent space for each feature, capturing the complexity of interactions.
n_features: This is the total number of features in the dataset.

Together, n_factors and n_features define the dimensions of the interaction matrix V, which is of size (n_features, n_factors). Each row in this matrix corresponds to a feature, and each column corresponds to a component of the latent vector for that feature.

The learning_rate, epochs, and reg are hyperparameters governing the learning process. The w0 is the global bias, W stores linear coefficients for features, and V contains the interaction factors, initialized with small random values.

Implementing the Factorization Machine Model: Part 2

Next, we define the fit method that uses gradient descent to train the algorithm.

Python

def fit(self, X, y):
    m, n = X.shape
    for epoch in range(self.epochs):
        for i in range(m):
            # Calculate linear terms by combining global bias and feature coefficients
            linear_terms = self.w0 + np.dot(X[i], self.W)
            
            # Calculate interaction terms using dot product of feature interactions
            interaction_term = sum(
                (np.dot(X[i], self.V[:, f]) ** 2 - np.dot(X[i] ** 2, self.V[:, f] ** 2)) / 2
                for f in range(self.n_factors))
            
            # Combine linear terms and interaction terms to get predictions
            predictions = linear_terms + interaction_term
            # Calculate prediction error
            err = predictions - y[i]
            
            # Update global bias using gradient descent
            self.w0 -= self.learning_rate * err
            # Update linear coefficients with regularization
            self.W -= self.learning_rate * (err * X[i] + self.reg * self.W)
            
            # Update interaction factors for each latent feature
            for f in range(self.n_factors):
                V_f = self.V[:, f]
                self.V[:, f] -= self.learning_rate * (
                    err * (X[i] @ V_f - X[i] ** 2 * V_f) / 2 + self.reg * V_f)

def fit(self, X, y):
    m, n = X.shape
    for epoch in range(self.epochs):
        for i in range(m):
            # Calculate linear terms by combining global bias and feature coefficients
            linear_terms = self.w0 + np.dot(X[i], self.W)
            
            # Calculate interaction terms using dot product of feature interactions
            interaction_term = sum(
                (np.dot(X[i], self.V[:, f]) ** 2 - np.dot(X[i] ** 2, self.V[:, f] ** 2)) / 2
                for f in range(self.n_factors))
            
            # Combine linear terms and interaction terms to get predictions
            predictions = linear_terms + interaction_term
            # Calculate prediction error
            err = predictions - y[i]
            
            # Update global bias using gradient descent
            self.w0 -= self.learning_rate * err
            # Update linear coefficients with regularization
            self.W -= self.learning_rate * (err * X[i] + self.reg * self.W)
            
            # Update interaction factors for each latent feature
            for f in range(self.n_factors):
                V_f = self.V[:, f]
                self.V[:, f] -= self.learning_rate * (
                    err * (X[i] @ V_f - X[i] ** 2 * V_f) / 2 + self.reg * V_f)

Initialize Parameters and Loop: We begin by determining the shape of the data (m, n) and iterating over each epoch to train the model.
Calculate Linear Terms: The linear terms are computed by summing the global bias w0 and the dot product of the feature coefficients W with the data instance X[i].
Calculate Interaction Terms: For each latent factor f, interaction terms are computed by taking the difference between the square of dot products and the dot product of squared terms, capturing feature interactions.
Compute Predictions and Error: Combine linear and interaction terms for predictions, then compute the error by subtracting actual ratings from predicted values.
Update Global Bias: The global bias is updated with the gradient of the error.
Update Linear Coefficients: Linear coefficients are adjusted using gradient descent, with regularization to prevent overfitting.
Update Interaction Factors: Each interaction factor is updated using the error and incorporates regularization to fine-tune learning of feature interactions. The gradient for interaction factors includes two parts:
- The term (X[i] @ V_f) computes the dot product between the feature vector and the current latent vector, highlighting the current influence of all features on the interaction term.
- The term (X[i] ** 2 * V_f) is the element-wise multiplication between the squared feature vector and the current latent vector, used to adjust for non-linearity and overfitting in interactions.

This dual consideration ensures that interactions are learned without inflating the error, especially with regularization.

from data_extraction import extract_dataset from sklearn.model_selection import train_test_split # Extract dataset df = extract_dataset() # Split dataset into train and test X = df.drop(columns=['rating']).values y = df['rating'].values X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42) # Define and train factorization machine model fm_model = SimpleFactorizationMachine(n_factors=3, n_features=X_train.shape[1], learning_rate=0.001, epochs=1000) fm_model.fit(X_train, y_train) # Test the model y_pred = fm_model.predict(X_test) # Evaluate model using Mean Absolute Error mae = np.mean(abs((y_test - y_pred))) print(f'Mean Absolute Error: {mae:.4f}') # Mean Absolute Error: 0.9364

Introduction to Factorization Machines

Review of Dataset Preparation

Theory Behind

Latent Vectors

Join the 1M+ learners on CodeSignal

Implementing the Factorization Machine Model: Part 1

Gradient Descent

Implementing the Factorization Machine Model: Part 2

Implementing the Factorization Machine Model: Part 3

Making Predictions and Evaluating Model Performance

Conclusion and Summary