Optimizing Item-CF for Product Recommendations

Buzzvil serves 30 e-commerce advertisers. To improve our retargeting solution, we introduced the Item-CF product recommendation algorithm. Here is how we optimized and deployed it.

Buzzvil’s Retargeting Solution

Retargeting products account for more than 20% of Buzzvil’s revenue. Traditionally, retargeting shows users the same products they expressed interest in on an e-commerce platform, encouraging them to click the ad and complete a purchase.

A retargeting example: after adding a product to their cart on SSG, a user sees that same product in an ad on a Buzzvil placement.

Buzzvil provides tailored retargeting solutions to around 30 e-commerce businesses, from home-shopping services to large marketplaces such as Coupang. To personalize these ads, we receive third-party data about user–product interactions from each merchant. We wondered whether, instead of simply showing the products users had already viewed, we could use that data to find other products that would encourage additional purchases. We have therefore been treating retargeting as a recommendation problem and steadily researching and developing machine-learning solutions. This post introduces our Python implementation of Item-CF and the optimizations that let it scale to large merchants.

What Is Item-CF?

Item-CF is the item-based form of collaborative filtering, a recommendation algorithm. To understand CF and Item-CF, imagine a user–item interaction matrix. Let’s use a fictional e-commerce store as an example.

An interaction matrix for a fictional store with three users and five products. The vectors for products 2 and 5 are highlighted in green.

Each cell is 1 if the user purchased the product and 0 otherwise. Rows represent users; columns represent items. CF’s intuition is that similar users have similar purchasing patterns. To recommend products to someone, find the most similar users and show what they bought.

Item-CF instead finds similar items. It builds an Item Similarities table recording the closest matches for every item. At recommendation time, it looks up the user’s previous purchases and recommends their most similar items.

Item-CF is well known as an algorithm popularized by Amazon twenty years ago. For more detail on CF and Item-CF, I recommend Amazon’s original paper. Next, we will cover our implementation and optimization of the paper’s algorithm for building the Item Similarities table.

Reimplementing It in Python

similar_items_table = defaultdict(list)
for product in product_catalog:
    products_bought_together = set()
    for user in users_who_purchased_product[product]:
        for product_bought_together in products_purchased_by_user[user]:
            products_bought_together.add(product_bought_together)

    for product_bought_together in products_bought_together:
        score = cosine_similarity(product, product_bought_together)
        similar_items_table[product].append((product_bought_together, score))

We translated the paper’s pseudocode into Python. It ran without problems on the example store above and our smallest merchants. The same could not be said for a medium-sized merchant with 600,000 users and 400,000 products: the estimated runtime was an astonishing 300 days.

Optimization #1: Sparse Vectors

With fewer than ten lines of Python, there were no obvious optimization opportunities. Apart from the loops, the main candidate was line 9, which calculates similarity between two item vectors. Let’s look at the formula.

The numerator accesses each dimension i of vectors A and B. But if either value is zero, their product contributes zero to the result. There is no need to calculate an addition of zero: we need only operate on dimensions where both vectors have nonzero values. The more zeros the vectors contain—the sparser they are—the lower the time complexity of the cosine-similarity calculation becomes.

Fortunately, real e-commerce user–item interaction matrices are extremely sparse. Most users buy only a tiny fraction of all products, and most products are bought by only a small fraction of users. Some products, such as bottled water, are bought by many people and produce dense vectors, but these accounted for less than 1% of all vectors.

We therefore stored item vectors in sparse form and changed the cosine-similarity calculation to operate efficiently on sparse vectors.

from scipy.sparse import csr_matrix
from sklearn.metrics.pairwise import cosine_similarity

# Use sparse vector format
a = csr_matrix(...)  # instead of np.array([0,0,...,0])
b = csr_matrix(...)

similarity_score = cosine_similarity(a, b)  # 6x faster!

Fortunately, we did not need to implement either the sparse representation or the similarity calculation ourselves. Simply using the sparse formats provided by SciPy and scikit-learn let their internal cosine-similarity implementations handle the optimization.

On average, this made the algorithm about six times faster. It would now take “only” 50 days instead of 300. Still far too slow for an actual advertising service.

Optimization #2: An Embarrassingly Parallel Workload

We examined whether the first loop really needed to run sequentially. Calculating the most similar items for item 2 did not need to wait for the work on item 1. Similarities for every item could be computed independently. Item-CF was an embarrassingly parallel workload.

We therefore optimized it with a distributed implementation. Looking for a distributed-computing framework that would be easy to adopt within Python, we chose Ray.

import ray

ray.init()

# Put variables into shared memory using `put`
users_who_purchased_product_ref = ray.put(users_who_purchased_product)
products_purchased_by_user_ref = ray.put(products_purchased_by_user)

@ray.remote  # Decorator turns regular function into asynchronous function
def compute_partial(partial_product_catalog, users_who_purchased_product, products_purchased_by_user):
    partial_table = defaultdict(list)
    for product in partial_product_catalog:
        products_bought_together = set()
        for user in users_who_purchased_product[product]:
            for product_bought_together in products_purchased_by_user[user]:
                products_bought_together.add(product_bought_together)

        for product_bought_together in products_bought_together:
            score = cosine_similarity(product, product_bought_together)
            partial_table[product].append((product_bought_together, score))
            
    return partial_table

# Split products e.g. If you had 10 products, you can call compute_partial() twice - first for 1~5, second for 6~10
futures = [compute_partial(partial_product_catalog_part_1, users_who_purchased_product_ref, products_purchased_by_user_ref),
           compute_partial(partial_product_catalog_part_2, users_who_purchased_product_ref, products_purchased_by_user_ref),
           ...]

ray.get(futures)  # After this line, `futures` has all partially computed similarities.

We also considered Spark and Dask. Spark required deploying and operating a JVM cluster outside Python, creating too much setup work. Dask’s requirement to use its own data types, such as Dask DataFrame and Dask Array, was another constraint we wanted to avoid. As the code above shows, Ray let us convert the existing algorithm into a distributed version with minimal changes.

The algorithm could now distribute its work across the available CPU cores. On a large EC2 r5.12xlarge instance, runtime fell from 50 days to four hours!

All 48 cores of an r5.12xlarge hard at work :running:

Single-Core vs. Multi-Core Optimization

We have introduced Item-CF, reimplemented it in Python, and explored two optimizations that made it practical for Buzzvil’s retargeting system. Sparse vectors reduced the space and time complexity of the relevant operations. Ray then made it relatively easy to turn a custom Python algorithm into a distributed version.

Looking back at the full process of optimizing and deploying Item-CF, I was reminded how difficult distributed algorithms are to develop and debug. Even with a comparatively approachable framework like Ray, distributed optimization took several times as much development effort as single-core optimization. My recommendation is to optimize at the single-core level first, then move to multiple cores.

Recommendation Is a Complex Problem

Finally, let me explain why Item-CF offered advantages over other recommendation models in Buzzvil’s particular position. We recommend products, but we are an advertising company, not an e-commerce company. Our ML team is solving recommendations for 30 catalogs, not one. Robustness is therefore one of the most important properties of any model or solution we adopt. Our recommendation system must serve every advertiser, not just one. In a startup where resources are perpetually limited, we particularly need models that transfer to new domains without additional implementation cost.

Item-CF met that need. User–item interactions alone produced high-quality recommendations across all our merchants. We do not use metadata such as user gender or age, product price, or category as features. Companies such as Netflix and Spotify show that combining metadata with interactions can improve recommendations. What differs for Buzzvil is that metadata quality is not guaranteed. Compared with interaction data, metadata quality varies substantially between merchants. For our model, that metadata is closer to a source of bottlenecks than a helpful addition.

Recommendation problems must be solved in the context of each company’s business and data quality. Unlike research ML, applied ML needs to measure practical qualities such as robustness alongside pure predictive performance. Do not be dazzled by papers reporting state-of-the-art results: there is no universal model that solves every recommendation problem. Item-CF certainly is not one either! Think of it as a model that delivers high-quality recommendations for a relatively modest set of required features.

If Buzzvil’s advertising and product-recommendation challenges interest you:

Apply for an engineering role at Buzzvil

Have a coffee chat with a Buzzvil technical recruiter