5 ms·

Recommending items to more than a billion people

116 points by antoinec 11y ago

istvan__ 11y ago
This is pretty cool, the scale is one reason almost any time Facebook publishes something in "big data" subject it is worth to read.
- amelius 11y ago
  I guess it is the only reason, because most of these problems are relatively easy to solve for small data.
  - istvan__ 11y ago
    You would be surprised. Several companies have a big data-problem even with small amount of it. :)
skbohra123 11y ago
Please don't do it, however great technical feat it is, the truth is, it sucks. I hate those the most in facebook.
- sjtrny 11y ago
  You would rather ads that are not tailored to your interests?
  - mildbow 11y ago
    Well of course. Tailored ads just make sense to companies because it increases click/conversion rates. I would rather not be convinced to buy things I don't have a need for. Thus, I don't see how more effective ads are any better for me.
acconsta 11y ago
To solve the matrix equation A × X = B we need to find the inverse A^-1 Huh? Isn't Gaussian elimination more straightforward?
- Rainymood 11y ago
  Maybe there are some optimized ways to calculate inv(A)? I could see Gaussian elimination taking a very long time if your A and B matrix are HUGE.
  - yaakov34 11y ago
    Enhanced versions of Gaussian elimination are used for quite large matrices (with many millions of non-zero coefficients), but for even larger matrices, approximate algorithms can be used. These converge to the desired solution, as opposed to computing it directly, as with Gaussian elimination.
- kanyethegreat 11y ago
  Since they're using collaborative filtering, the matrix they're solving for is very sparse (ie it's an undetermined system). So they're fitting a nonlinear regression model by minimizing the regularized squared error. Since the vectors they're trying to model (x and y) are both unknown, the optimization problem is not convex, or in other words, can't be solved for exactly. http://www2.research.att.com/~volinsky/papers/ieeecomputer.pdf http://www2.research.att.com/~volinsky/papers/ieeecomputer.p... Edit: everything, then added AT&T research paper link
  - yaakov34 11y ago
    Come again? A nonlinear matrix equation of the form AX=B?
    - kanyethegreat 11y ago
      Yeah, I have no idea why I said that. Answer's been fixed
sjtrny 11y ago
The technical name for this is "collaborative filtering". I think they are basing their work on this paper - http://www.jmlr.org/papers/volume10/takacs09a/takacs09a.pdf http://www.jmlr.org/papers/volume10/takacs09a/takacs09a.pdf EDIT: Actually looks like Eq (15) from - http://public.research.att.com/~volinsky/netflix/BellKorICDM07.pdf http://public.research.att.com/~volinsky/netflix/BellKorICDM... Anyway there are lots of papers around on the topic.
- Rifu 11y ago
  They do mention that in the 2nd paragraph and repeatedly throughout the article as CF. I found the article to be a nice primer on the topic as it listed common approaches to the problem.
- thebigjc 11y ago
  Lots of research here, but the most interesting part is their distributed graph approach. Scaling up CF is a challenging problem, and the current open source implementations have problems at really large scales. I hope they open source their Giraph implementation, or at least part of it.
FiReaNG3L 11y ago
I hoped for a minute that they shared their complete implementation; anyone aware of a recommendation system that can scale to millions of items, be updated as soon as new items come in (no full graph recalculation) and take multiple inputs (ratings, saved in library, etc)?
- paulasmuth 11y ago
  Have a look at Google's MinHash algorithm. While it's a probabilistic solution, You can run it as a mapreduce and will at no point need to have the full data set in memory/on a single machine. So it does scale pretty well. http://www2007.org/papers/paper570.pdf http://www2007.org/papers/paper570.pdf EDIT: I see you changed your comment to include "no full graph recalcuation". Incremental recos are possible to do with minhash but I think you can't solve decay of old data easily.
known 11y ago
http://en.m.wikipedia.org/wiki/SAS_Institute http://en.m.wikipedia.org/wiki/SAS_Institute
a1k0n 11y ago
FWIW, I gave a talk about the Alternating Least Squares algorithm mentioned here (and linked in several comments) and how we implemented it at Spotify: Slides: http://www.a1k0n.net/spotify/ml-madison/ http://www.a1k0n.net/spotify/ml-madison/ Video (for the extremely patient): https://www.youtube.com/watch?v=MX_ARH-KoDg https://www.youtube.com/watch?v=MX_ARH-KoDg

116 points by antoinec 11y ago

This is pretty cool, the scale is one reason almost any time Facebook publishes something in "big data" subject it is worth to read.

amelius 11y ago
I guess it is the only reason, because most of these problems are relatively easy to solve for small data.
- istvan__ 11y ago
  You would be surprised. Several companies have a big data-problem even with small amount of it. :)

skbohra123 11y ago

Please don't do it, however great technical feat it is, the truth is, it sucks. I hate those the most in facebook.

sjtrny 11y ago
You would rather ads that are not tailored to your interests?
- mildbow 11y ago
  Well of course. Tailored ads just make sense to companies because it increases click/conversion rates. I would rather not be convinced to buy things I don't have a need for. Thus, I don't see how more effective ads are any better for me.

acconsta 11y ago

To solve the matrix equation A × X = B we need to find the inverse A^-1 Huh? Isn't Gaussian elimination more straightforward?

Rainymood 11y ago
Maybe there are some optimized ways to calculate inv(A)? I could see Gaussian elimination taking a very long time if your A and B matrix are HUGE.
- yaakov34 11y ago
  Enhanced versions of Gaussian elimination are used for quite large matrices (with many millions of non-zero coefficients), but for even larger matrices, approximate algorithms can be used. These converge to the desired solution, as opposed to computing it directly, as with Gaussian elimination.
kanyethegreat 11y ago
Since they're using collaborative filtering, the matrix they're solving for is very sparse (ie it's an undetermined system). So they're fitting a nonlinear regression model by minimizing the regularized squared error. Since the vectors they're trying to model (x and y) are both unknown, the optimization problem is not convex, or in other words, can't be solved for exactly. http://www2.research.att.com/~volinsky/papers/ieeecomputer.pdf http://www2.research.att.com/~volinsky/papers/ieeecomputer.p... Edit: everything, then added AT&T research paper link
- yaakov34 11y ago
  Come again? A nonlinear matrix equation of the form AX=B?
  - kanyethegreat 11y ago
    Yeah, I have no idea why I said that. Answer's been fixed

sjtrny 11y ago

The technical name for this is "collaborative filtering". I think they are basing their work on this paper - http://www.jmlr.org/papers/volume10/takacs09a/takacs09a.pdf http://www.jmlr.org/papers/volume10/takacs09a/takacs09a.pdf EDIT: Actually looks like Eq (15) from - http://public.research.att.com/~volinsky/netflix/BellKorICDM07.pdf http://public.research.att.com/~volinsky/netflix/BellKorICDM... Anyway there are lots of papers around on the topic.

Rifu 11y ago
They do mention that in the 2nd paragraph and repeatedly throughout the article as CF. I found the article to be a nice primer on the topic as it listed common approaches to the problem.
thebigjc 11y ago
Lots of research here, but the most interesting part is their distributed graph approach. Scaling up CF is a challenging problem, and the current open source implementations have problems at really large scales. I hope they open source their Giraph implementation, or at least part of it.

FiReaNG3L 11y ago

I hoped for a minute that they shared their complete implementation; anyone aware of a recommendation system that can scale to millions of items, be updated as soon as new items come in (no full graph recalculation) and take multiple inputs (ratings, saved in library, etc)?

paulasmuth 11y ago
Have a look at Google's MinHash algorithm. While it's a probabilistic solution, You can run it as a mapreduce and will at no point need to have the full data set in memory/on a single machine. So it does scale pretty well. http://www2007.org/papers/paper570.pdf http://www2007.org/papers/paper570.pdf EDIT: I see you changed your comment to include "no full graph recalcuation". Incremental recos are possible to do with minhash but I think you can't solve decay of old data easily.

known 11y ago

http://en.m.wikipedia.org/wiki/SAS_Institute http://en.m.wikipedia.org/wiki/SAS_Institute

a1k0n 11y ago

FWIW, I gave a talk about the Alternating Least Squares algorithm mentioned here (and linked in several comments) and how we implemented it at Spotify: Slides: http://www.a1k0n.net/spotify/ml-madison/ http://www.a1k0n.net/spotify/ml-madison/ Video (for the extremely patient): https://www.youtube.com/watch?v=MX_ARH-KoDg https://www.youtube.com/watch?v=MX_ARH-KoDg