{"id":165,"date":"2021-01-26T17:00:11","date_gmt":"2021-01-26T17:00:11","guid":{"rendered":"https:\/\/fde.cat\/index.php\/2021\/01\/26\/how-machine-learning-powers-facebooks-news-feed-ranking-algorithm\/"},"modified":"2021-02-02T13:42:11","modified_gmt":"2021-02-02T13:42:11","slug":"how-machine-learning-powers-facebooks-news-feed-ranking-algorithm","status":"publish","type":"post","link":"https:\/\/fde.cat\/index.php\/2021\/01\/26\/how-machine-learning-powers-facebooks-news-feed-ranking-algorithm\/","title":{"rendered":"How machine learning powers Facebook\u2019s News Feed ranking algorithm"},"content":{"rendered":"

Designing a personalized ranking system for more than 2 billion people (all with different interests) and a plethora of content to select from presents significant, complex challenges. This is something we tackle every day with News Feed ranking. Without machine learning (ML), people\u2019s News Feeds could be flooded with content they don\u2019t find as relevant or interesting, including overly promotional content or content from acquaintances who post frequently, which can bury the content from the people they\u2019re closest to. Ranking exists to help solve these problems, but how can you build a system that presents so many different types of content in a way that\u2019s personally relevant to billions of people around the world? We use ML to predict which content will matter most to each person to support a more engaging and positive experience. Models for <\/span>meaningful interactions<\/span><\/a> and <\/span>quality content<\/span><\/a> are powered by state-of-the-art ML, such as multitask learning on neural networks, embeddings, and <\/span>offline learning systems<\/span><\/a>. We are sharing new details of how we designed an ML-powered News Feed ranking system.
\n\"How
\n<\/span><\/p>\n

Building a ranking algorithm<\/span><\/h2>\n

To understand how this works, let\u2019s start with a hypothetical person logging in to Facebook: We\u2019ll call him Juan. Since Juan\u2019s login yesterday, his good friend Wei posted a photo of his cocker spaniel. Another friend, Saanvi, posted a video from her morning run. And his favorite Page published an interesting article about the best way to view the Milky Way at night, while his favorite cooking Group posted four new sourdough recipes.\u00a0<\/span><\/p>\n

Because Juan is connected to or has chosen to follow the producers of this content, it\u2019s all likely to be relevant or interesting to him. To rank some of these things higher than others in Juan\u2019s News Feed, we need to learn what matters most to Juan and which content carries the highest value for him. In mathematical terms, we need to define an objective function for Juan and perform a single-objective optimization.
\n<\/span><\/p>\n

Take Saanvi\u2019s running video, for example. On Facebook, one concrete observable signal that an item has value for someone is if they click the like button<\/span>. <\/span><\/i>Given various attributes we know about a post (who is tagged in a photo, when it was posted, etc.)<\/span>,<\/span><\/i> we can use the characteristics of the post <\/span>Xit<\/sub><\/i> toward viewer<\/span> j<\/span><\/i> at time <\/span>t<\/span><\/i>,<\/span> and predict <\/span>Y<\/span><\/i>ijt<\/sub><\/i> (whether Juan might like the post)<\/span>. <\/span><\/i>Mathematically, for each post i<\/i>, we estimate Y<\/span><\/i>ijt<\/sub><\/i> = f(x<\/span><\/i>ijt1;<\/sub><\/i>x<\/span>ijt2;<\/sub><\/i>\u00a0\u2026 xijtC<\/sub><\/i>), where c represents a characteristic <\/span>c <\/span><\/i>(1..<\/span>C<\/i>) such as the type of post or the relationship between the viewer and the author of the post (e.g., whether they marked each other as family members) and the function <\/span>f(.)<\/span><\/i> combines the attributes into a single value.\u00a0<\/span><\/p>\n

For example, if Juan tends to interact with Saanvi a lot or share the content Saanvi posts, and the running video is very recent (e.g., from this morning), we might see a high probability that Juan likes content like this. On the other hand, perhaps Juan has previously engaged more with video content than photos, so the like prediction for Wei\u2019s cocker spaniel photo might be lower. In this case, our ranking algorithm would rank Saanvi\u2019s running video higher than Wei\u2019s cocker spaniel photo because it predicts a higher probability that Juan will like that piece of content.<\/span><\/p>\n

But is liking the only way Juan expresses his preferences? Surely not. He might share articles he finds interesting, watch videos from his favorite game streamers, or leave thoughtful comments on posts from friends. Things get more mathematically complicated when we need to optimize for multiple objectives that all contribute to our overarching objective (creating the most long-term value for people). You can have multiple values (Yijtk<\/sub><\/i>), e.g., likes, comments, and shares, each for a different value of k<\/span><\/i>, that all need to somehow aggregate up to a single <\/span>V<\/span><\/i>ijt<\/sub><\/i> value. To complicate things further, for each person on Facebook there are thousands of signals we need to evaluate to determine what that person might find most relevant, so the algorithm gets very complex in practice.\u00a0\u00a0<\/span><\/p>\n

How do you pick the overarching value for an ecosystem the size of Facebook? We want to provide the people using our services with long-term value. How much does seeing this friend\u2019s running video or reading an interesting article create value for Juan? We think the best way to assess whether something is creating long-term value for someone is to pick metrics that are aligned with what people say is important to them. So we <\/span>survey people<\/span><\/a> about how meaningful they found an interaction with their friends or whether a post is worth their time to make sure our values (<\/span>Y<\/span><\/i>ijtk<\/sub><\/i>)<\/span> reflect <\/span>what people say they find meaningful<\/span><\/a>.<\/span><\/p>\n

Multiple prediction models provide us with multiple predictions for Juan: a probability he\u2019d engage with (e.g., like or leave a comment on) Wei\u2019s cocker spaniel picture, Saanvi\u2019s running video, the article shared on the Page, and the cooking Group posts. Each of these models will try to rank each of these pieces of content for Juan. Sometimes the models disagree (e.g., Juan might like Saanvi\u2019s running video with a higher probability than the Page article, but he might be more likely to share the article than Saanvi\u2019s video), and the way we take each prediction into account for Juan is based on the actions that people tell us (<\/span>via surveys<\/span><\/a>) are more meaningful and worth their time.
\n<\/span><\/p>\n

<\/div>\n

Approximating the ideal ranking function in a scalable ranking system<\/span><\/h2>\n

Now that we know the theory behind ranking (as exemplified through Juan\u2019s News Feed), we need to determine how to build a system for this optimization. We need to score all the posts available for more than 2 billion people (more than 1,000 posts per user, per day, on average), which is challenging. And we need to do this in real time \u2014 so we need to know if an article has received a lot of likes, even if it was just posted minutes ago. We also need to know if Juan liked a lot of other content a minute ago, so we can use this information optimally in ranking.<\/span><\/p>\n

Our system architecture uses a Web\/PHP layer, which queries the feed aggregator. The role of the feed aggregator is to collect all relevant information about a post and analyze all the features (e.g., how many people have liked this post before) in order to predict the post\u2019s value <\/span>Y<\/span><\/i>ijt<\/sub><\/i> to the user, as well as the final ranking score <\/span>V<\/span><\/i>ijt<\/sub><\/i> by aggregating all the predictions.<\/span>
\n<\/span><\/p>\n

\"When
When someone opens up Facebook, regardless of the front-end interface (e.g., iPhone, Android phone, web browser), the interface will send a request to a Web\/PHP (front-end) layer, which then queries the feed aggregator (back-end layer). After accepting a request from the front end, the feed aggregator fetches actions and objects, along with an object summary, from the feed leaf databases so that it can process, aggregate, rank, and return the resulting list of ranked FeedStories to the front end for rendering.<\/figcaption><\/figure>\n

Now let\u2019s review how the aggregator works:<\/span><\/p>\n

    \n
  1. Query inventory.<\/b> We first need to collect all the candidate posts we can possibly rank for Juan (the cocker spaniel picture, the running video, etc.). The first part is fairly straightforward: The eligible inventory includes any non-deleted post shared with Juan by a friend, Group, or Page that he is connected to that was made since his last login. But what about posts created before Juan\u2019s last login that he hasn\u2019t seen yet? Maybe these were higher quality or more relevant than the newer posts, but he simply didn\u2019t have time to look at them. To make sure unseen posts are also reconsidered, we have an unread bumping logic: Fresh posts that Juan has not yet seen but that were ranked for him in his previous sessions are eligible again for him to see. We also have an action-bumping logic: If any posts Juan has already seen have triggered an interesting conversation among his friends, Juan may be eligible to see this post again as a comment-bumped post.<\/span><\/li>\n
  2. Score <\/b>Xit<\/sub><\/i><\/b> for Juan for each prediction (<\/b>Y<\/i><\/b>ijt<\/sub><\/i><\/b>).<\/b> Now that we have Juan\u2019s inventory, we score each post using multitask neural nets. There are many, many features (<\/span>x<\/span><\/i>ijtc<\/sub><\/i>) we can use to predict <\/span>Y<\/span><\/i>ijt<\/sub><\/i>, including the type of post, embeddings (i.e., feature representations generated by deep learning models), and what the viewer tends to interact with. To calculate this for more than 1,000 posts, for each of billions of users \u2014 all\u00a0in real time \u2014\u00a0we run these models for all candidate stories in parallel on multiple machines, called predictors.<\/span><\/li>\n
  3. Calculate a single score out of many predictions: <\/b>V<\/i><\/b>ijt<\/sub><\/i><\/b>.<\/b> Now that we have all the predictions, we can combine them into a single score. To do this, multiple passes are needed to save computational power and to apply rules, such as content type diversity (i.e., content type should be varied so that viewers don\u2019t see redundant content types, such as multiple videos, one after another), that depend on an initial ranking score. First, certain integrity processes are applied to every post. These are designed to determine which integrity detection measures, if any, need to be applied to the stories selected for ranking. Then, in pass 0, a lightweight model is run to select approximately 500 of the most relevant posts for Juan that are eligible for ranking. This helps us rank fewer stories with high recall in later passes so that we can use more powerful neural network models. Pass 1 is the main scoring pass, where each story is scored independently and then all ~500 eligible posts are ordered by score. Finally, we have pass 2, which is the contextual pass. Here, contextual features, such as content-type diversity rules, are added to help diversify Juan\u2019s News Feed.<\/span><\/li>\n<\/ol>\n