Factorization Machines in JavaScript

Introduction to Factorization Machines

Welcome to this lesson on factorization machines, an important model in the realm of recommendation systems. Factorization machines (FM) excel at 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 dive into implementing a factorization machine, let's briefly revisit the dataset preparation process from the previous lesson. Previously, you learned how to load data from JSON files and represent it as arrays of objects in JavaScript. You also created a user-item interaction matrix using dummy variables (one-hot encoding) and enriched the dataset with auxiliary features such as user preferences and genre similarity. These steps are crucial for building a dataset that can be used for accurate predictions in a recommendation system. For this lesson, assume your data is structured as an array of objects, where each object represents a user-item interaction with features like: JavaScript {user1: 0, user2: 1, user3: 0, // one-hot user item1: 0, item2: 0, item3: 1, // one-hot item uf1: 0.7, uf2: 0.2, // user features if1: 0.5, if2: 0.1, // item features rating: 4.0 // target value} To train the model, you will need to convert this array of objects into two arrays: X : an array of arrays, where each sub-array contains the feature values for one interaction (excluding the target). y : an array of target values (e.g., ratings).

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

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 2

Now, let's implement the fit method in JavaScript using ml-matrix and mathjs for correct and efficient vector/matrix operations.

JavaScript

SimpleFactorizationMachine.prototype.fit = function(X, y) {
    const m = X.rows;
    const n = X.columns;
    for (let epoch = 0; epoch < this.epochs; epoch++) {
        for (let i = 0; i < m; i++) {
            let x = X.getRow(i);
            let linearTerms = this.w0 + math.dot(x, this.W);

            let interactionTerm = 0;
            for (let f = 0; f < this.nFactors; f++) {
                let v_f = this.V.map(row => row[f]);
                let dot_x_vf = math.dot(x, v_f);
                let dot_x2_vf2 = math.dot(x.map(xi => xi ** 2), v_f.map(vfi => vfi ** 2));
                interactionTerm += (dot_x_vf ** 2 - dot_x2_vf2) / 2;
            }

            let prediction = linearTerms + interactionTerm;
            let err = prediction - y[i];

            this.w0 -= this.learningRate * err;

            for (let j = 0; j < n; j++) {
                this.W[j] -= this.learningRate * (err * X.get(i, j) + this.reg * this.W[j]);
            }

            for (let f = 0; f < this.nFactors; f++) {
                let v_f = this.V.map(row => row[f]);
                for (let j = 0; j < n; j++) {
                    let grad = err * (x[j] * (math.dot(x, v_f) - v_f[j] * x[j])) + this.reg * this.V[j][f];
                    this.V[j][f] -= this.learningRate * grad;
                }
            }
        }
    }
};

SimpleFactorizationMachine.prototype.fit = function(X, y) {
    const m = X.rows;
    const n = X.columns;
    for (let epoch = 0; epoch < this.epochs; epoch++) {
        for (let i = 0; i < m; i++) {
            let x = X.getRow(i);
            let linearTerms = this.w0 + math.dot(x, this.W);

            let interactionTerm = 0;
            for (let f = 0; f < this.nFactors; f++) {
                let v_f = this.V.map(row => row[f]);
                let dot_x_vf = math.dot(x, v_f);
                let dot_x2_vf2 = math.dot(x.map(xi => xi ** 2), v_f.map(vfi => vfi ** 2));
                interactionTerm += (dot_x_vf ** 2 - dot_x2_vf2) / 2;
            }

            let prediction = linearTerms + interactionTerm;
            let err = prediction - y[i];

            this.w0 -= this.learningRate * err;

            for (let j = 0; j < n; j++) {
                this.W[j] -= this.learningRate * (err * X.get(i, j) + this.reg * this.W[j]);
            }

            for (let f = 0; f < this.nFactors; f++) {
                let v_f = this.V.map(row => row[f]);
                for (let j = 0; j < n; j++) {
                    let grad = err * (x[j] * (math.dot(x, v_f) - v_f[j] * x[j])) + this.reg * this.V[j][f];
                    this.V[j][f] -= this.learningRate * grad;
                }
            }
        }
    }
};

Linear Terms: Calculated as the sum of the global bias and the dot product of the feature vector and linear coefficients.
Interaction Terms: For each latent factor, sum the dot products and squared terms to capture feature interactions.
Parameter Updates: Update the global bias, linear coefficients, and interaction factors using gradient descent and regularization.

Making Predictions and Evaluating Model Performance

Let's see how to use the factorization machine in practice. We'll split the data into training and testing sets, train the model, make predictions, and evaluate performance using Mean Absolute Error (MAE).

// Example: Assume data is loaded as an array of objects
const data = [
  // ... your data objects here ...
];

// Extract feature names (excluding the target)
const featureNames = Object.keys(data[0]).filter(k => k !== 'rating');

// Convert data to X (features) and y (target)
const X_arr = data.map(row => featureNames.map(f => row[f]));
const y = data.map(row => row.rating);

// Convert X to Matrix
const X = new Matrix(X_arr);

// Split into train and test sets (e.g., 80% train, 20% test)
function trainTestSplit(X, y, testSize = 0.2, randomSeed = 42) {
    const m = X.rows;
    let indices = Array.from({ length: m }, (_, i) => i);
    function seededRandom(seed) {
        let x = Math.sin(seed++) * 10000;
        return x - Math.floor(x);
    }
    for (let i = indices.length - 1; i > 0; i--) {
        const j = Math.floor(seededRandom(randomSeed + i) * (i + 1));
        [indices[i], indices[j]] = [indices[j], indices[i]];
    }
    const testCount = Math.floor(m * testSize);
    const testIdx = indices.slice(0, testCount);
    const trainIdx = indices.slice(testCount);

    const X_train = new Matrix(trainIdx.map(i => X.getRow(i)));
    const y_train = trainIdx.map(i => y[i]);
    const X_test = new Matrix(testIdx.map(i => X.getRow(i)));
    const y_test = testIdx.map(i => y[i]);
    return { X_train, y_train, X_test, y_test };
}

const { X_train, y_train, X_test, y_test } = trainTestSplit(X, y, 0.2, 42);

// Initialize and train the factorization machine
const nFactors = 3;
const nFeatures = featureNames.length;
const fm = new SimpleFactorizationMachine(nFactors, nFeatures, 0.001, 1000, 0.01);
fm.fit(X_train, y_train);

// Make predictions
const y_pred = fm.predict(X_test);

// Evaluate using Mean Absolute Error (MAE)
function meanAbsoluteError(yTrue, yPred) {
    return math.mean(yTrue.map((yi, i) => Math.abs(yi - yPred[i])));
}

const mae = meanAbsoluteError(y_test, y_pred);
console.log(`Mean Absolute Error: ${mae.toFixed(4)}`);
// Example output: Mean Absolute Error: 0.9364

The Mean Absolute Error (MAE) is defined as:

$\text{MAE} = \frac{1}{n} \sum_{i=1}^{n} |y_i - \hat{y}_i|$

where $n$ is the number of observations, $y_i$ is the actual value, and $\hat{y}_i$ is the predicted value.

Here, we split the dataset into training and testing sets, initialize the factorization machine, train it, make predictions, and evaluate the results using MAE.

// Example: Assume data is loaded as an array of objects const data = [ // ... your data objects here ... ]; // Extract feature names (excluding the target) const featureNames = Object.keys(data[0]).filter(k => k !== 'rating'); // Convert data to X (features) and y (target) const X_arr = data.map(row => featureNames.map(f => row[f])); const y = data.map(row => row.rating); // Convert X to Matrix const X = new Matrix(X_arr); // Split into train and test sets (e.g., 80% train, 20% test) function trainTestSplit(X, y, testSize = 0.2, randomSeed = 42) { const m = X.rows; let indices = Array.from({ length: m }, (_, i) => i); function seededRandom(seed) { let x = Math.sin(seed++) * 10000; return x - Math.floor(x); } for (let i = indices.length - 1; i > 0; i--) { const j = Math.floor(seededRandom(randomSeed + i) * (i + 1)); [indices[i], indices[j]] = [indices[j], indices[i]]; } const testCount = Math.floor(m * testSize); const testIdx = indices.slice(0, testCount); const trainIdx = indices.slice(testCount); const X_train = new Matrix(trainIdx.map(i => X.getRow(i))); const y_train = trainIdx.map(i => y[i]); const X_test = new Matrix(testIdx.map(i => X.getRow(i))); const y_test = testIdx.map(i => y[i]); return { X_train, y_train, X_test, y_test }; } const { X_train, y_train, X_test, y_test } = trainTestSplit(X, y, 0.2, 42); // Initialize and train the factorization machine const nFactors = 3; const nFeatures = featureNames.length; const fm = new SimpleFactorizationMachine(nFactors, nFeatures, 0.001, 1000, 0.01); fm.fit(X_train, y_train); // Make predictions const y_pred = fm.predict(X_test); // Evaluate using Mean Absolute Error (MAE) function meanAbsoluteError(yTrue, yPred) { return math.mean(yTrue.map((yi, i) => Math.abs(yi - yPred[i]))); } const mae = meanAbsoluteError(y_test, y_pred); console.log(`Mean Absolute Error: ${mae.toFixed(4)}`); // Example output: Mean Absolute Error: 0.9364

Introduction to Factorization Machines

Review of Dataset Preparation

Theory Behind

Join the 1M+ learners on CodeSignal

Latent Vectors

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