My name is Pavel Parkhomenko, and I am an ML developer. In this article, I would like to discuss the structure of the Yandex Zen service and share the technical improvements that have significantly enhanced the quality of recommendations. You will learn how to find the most relevant documents for users among millions in just a few milliseconds; how to continuously decompose a large matrix (comprising millions of columns and tens of millions of rows), allowing new documents to obtain their vectors in just a few minutes; and how to reuse the user-article matrix decomposition to achieve a good vector representation for videos.
Our recommendation database contains millions of documents in various formats: text articles created on our platform and sourced from external sites, videos, narratives, and short posts. The development of such a service comes with numerous technical challenges. Here are some of them:
- Distributing computational tasks: perform all heavy operations offline, and only carry out quick model applications in real-time to respond within 100-200 ms.
- Quickly account for user actions. It’s essential that all events are instantly delivered to the recommender and influence the model's output.
- Create a feed that quickly adapts to the behavior of new users. Freshly onboarded individuals should feel that their feedback affects the recommendations.
- Rapidly identify whom to recommend a new article to.
- Promptly respond to the constant emergence of new content. Tens of thousands of articles are published every day, many of which have a short lifespan (for instance, news). This distinguishes them from films, music, and other long-lasting and expensive-to-create content.
- Transfer knowledge from one domain to another. If the recommendation system has trained models for text articles and we introduce videos, we can reuse existing models to better rank the new content type.
I will explain how we tackled these challenges.
Candidate Selection
How to reduce a multitude of documents by thousands in just a few milliseconds without significantly degrading ranking quality?
Let's assume we have trained many ML models, generated features based on them, and trained another model that ranks documents for the user. Everything sounds good, but you can't just calculate all features for all documents in real-time if there are millions of them, and recommendations need to be built within 100-200 ms. The task is to select a subset from millions that will be ranked for the user. This stage is usually called candidate selection. It has several requirements. Firstly, the selection must happen very quickly to leave as much time as possible for the actual ranking. Secondly, while significantly reducing the number of documents for ranking, we need to preserve as many relevant documents for the user as possible.
Our principle of candidate selection has evolved over time, and we have now arrived at a multistage scheme:
First, all documents are divided into groups, and the most popular documents are taken from each group. Groups can be websites, topics, or clusters. For each user, based on their history, we select the groups that are most relevant to them and then take the best documents from those groups. We also use a kNN index to find the most relevant documents for the user in real-time. There are several methods for constructing a kNN index, and the one that works best for us is (Hierarchical Navigable Small World graphs). This is a hierarchical model that allows finding N nearest vectors for the user from a million-document database in just a few milliseconds. We pre-index our entire document database offline. Since searching in the index works quite fast, having several strong embeddings allows us to create multiple indices (one index for each embedding) and access each of them in real-time.
We have tens of thousands of documents for each user. It's still a lot to calculate all the features, so at this stage, we apply light ranking — a simplified model of heavy ranking with fewer features. The task is to predict which documents will be at the top according to the heavy model. Documents with the highest predictions will be used in the heavy model, which is the final stage of ranking. This approach allows us to reduce the pool of documents considered for the user from millions to thousands in just a few milliseconds.
ALS step in runtime
How to incorporate user feedback immediately after a click?
A critical factor in recommendations is the response time to user feedback. This is particularly important for new users: when a person first starts using the recommendation system, they receive a non-personalized feed of diverse documents. Once they make their first click, it is essential to immediately take this into account and adjust to their interests. If all factors are computed offline, the system's quick response will be impossible due to latency. Therefore, it is necessary to process user actions in real time. For this purpose, we use the ALS step in runtime to build a vector representation of the user.
Assuming we have a vector representation for all documents. For example, we can build embeddings based on the text of the article offline using ELMo, BERT, or other machine learning models. How can we obtain a vector representation of users in the same space based on their interactions in the system?
General principle of forming and decomposing the user-document matrixLet’s consider m users and n documents. For some users, their relationship to certain documents is known. This information can be represented as an m x n matrix: rows correspond to users, while columns correspond to documents. Since most documents have not been seen by the user, a majority of the cells in the matrix will remain empty, while others will be filled. For each event (like, dislike, click), the matrix has a specific value — but let's consider a simplified model where a like corresponds to 1, and a dislike corresponds to -1.
We can decompose the matrix into two matrices: P (m x d) and Q (d x n), where d is the dimensionality of the vector representation (usually a small number). Each object will then correspond to a d-dimensional vector (with the user being a row in matrix P and the document being a column in matrix Q). These vectors are the embeddings of the corresponding objects. To predict whether a user will like a document, we can simply multiply their embeddings.
One possible method of matrix decomposition is ALS (Alternating Least Squares). We will optimize the following loss function:
Here, rui denotes the interaction of user u with document i, qi is the vector for document i, and pu is the vector for user u.
Then, the optimal user vector (with fixed document vectors) is found analytically by solving the corresponding linear regression, minimizing the mean squared error.
This is referred to as the 'ALS step.' The ALS algorithm involves alternately fixing one of the matrices (users or documents) and updating the other to find the optimal solution.
Fortunately, finding the user vector representation is a fairly quick operation that can be performed at runtime using vector instructions. This trick allows us to immediately account for user feedback in ranking. The same embedding can be used in a kNN index to improve candidate selection.
Distributed collaborative filtering
How to perform incremental distributed matrix factorization and quickly find the vector representation of new articles?
Content is not the only source of signals for recommendations. Another important source is collaborative information. Traditionally, good features in ranking can be derived from the decomposition of the user-document matrix. However, when trying to perform such decomposition, we encountered several issues:
1. We have millions of documents and tens of millions of users. The matrix cannot fit entirely on a single machine, and the decomposition will take a very long time.
2. Most of the content in the system has a short lifespan: documents remain relevant for only a few hours. Therefore, it is essential to build their vector representation as quickly as possible.
3. If we build the decomposition immediately after the document is published, it won't be evaluated by a sufficient number of users in time. Thus, its vector representation will likely not be very good.
4. If a user has liked or disliked something, we won't be able to account for that in the decomposition immediately.
To address these issues, we implemented a distributed decomposition of the user-document matrix with frequent incremental updates. How does this work?
Suppose we have a cluster of N machines (N is in the hundreds), and we want to perform a distributed decomposition of a matrix that does not fit on a single machine. The question is how to execute this decomposition so that, on one hand, each machine has enough data, and on the other, the computations are independent?
We will use the previously described ALS decomposition algorithm. Let’s consider how to perform one step of the ALS algorithm in a distributed manner—the other steps will be similar. Assume we have a fixed document matrix, and we want to build the user matrix. To achieve this, we will split it into N parts by rows, each part containing roughly the same number of rows. We will send the non-empty cells of the corresponding rows to each machine, along with the full document embeddings matrix. Since its size is not very large, and the user-document matrix is usually very sparse, this data will fit on a standard machine.
This trick can be repeated over several epochs until the model converges, by alternately changing the fixed matrix. However, even then, the matrix decomposition can take several hours. This does not solve the problem of needing to quickly obtain embeddings for new documents and update the embeddings of those that had little information when building the model.
We implemented a fast incremental update to the model. Let's say we have a current trained model. Since its training, new articles have appeared that our users interacted with, as well as articles that had minimal interactions during training. To quickly obtain embeddings for such articles, we use user embeddings obtained during the initial large training of the model and perform one ALS step to compute the documents' matrix while keeping the users' matrix fixed. This allows us to obtain embeddings quite quickly — within a few minutes of document publication — and to frequently update the embeddings of fresh documents.
To immediately consider human actions for recommendations, we do not use user embeddings obtained offline at runtime. Instead, we perform an ALS step and obtain the current user vector.
Transfer to another domain
How to use user feedback on text articles to build a vector representation for videos?
Initially, we only recommended text articles, so many of our algorithms are tailored to this type of content. However, when adding content of a different type, we faced the need to adapt the models. How did we address this task for videos? One option was to retrain all models from scratch. But this is time-consuming, and some algorithms are demanding regarding the amount of training data, which is not yet available in sufficient quantity for new types of content in the early moments of its life on the service.
We took a different approach and repurposed text models for video. In creating vector representations of videos, we utilized the same ALS trick. We took the vector representation of users based on text articles and performed an ALS step using the information about video views. This allowed us to effortlessly obtain a vector representation of the video. At runtime, we simply compute the similarity between the user vector derived from text articles and the vector of the video.
Conclusion
Developing the core of a real-time recommendation system involves numerous challenges. We need to process data quickly and apply ML methods for effective data utilization; build complex distributed systems capable of processing user signals and new pieces of content in minimal time; and tackle many other tasks.
In the current system, the design I described, the quality of recommendations for a user improves with their activity and duration of stay on the service. But of course, this also comes with the main difficulty: the system struggles to understand the interests of a person who has interacted little with the content. Improving recommendations for new users is our key task. We will continue to optimize the algorithms so that relevant content reaches their feed faster while irrelevant content does not appear.
Source: habr.com
