Factorization Machines

http://tech.adroll.com/blog/data-science/2015/08/25/factorization-machines.html

by dialtone • 11 years ago

30 14 11 years ago

tech.adroll.com

xtacy2• 11 years ago

Isn't the key insight -- to replace `w_{i,j}` by turning it into a vector with an inner product structure -- also known as the kernel-trick in machine learning? (here, they seem to use a polynomial kernel: https://en.wikipedia.org/wiki/Polynomial_kernel).

EDIT: <strike>It's</strike> Kernel tricks in general are nice because they also generalise well to an infinite dimensional space (the RBF kernel) and compute the dot-products in that space without actually computing the embedding. RBFs: https://en.wikipedia.org/wiki/Radial_basis_function_kernel

99decisionstr4• 11 years ago

Not quite - it's different from the kernel trick, which is impossible at this scale (there's no way you can train an RBF kernel in a decent amount of time when your space has 10^8 features and your training set has 10^9 observations). The idea of factorization machine is to learn the polynomial kernel, and it provides a mechanism to do so which scales "linearly" (with some arbitrary constant that you're in control of).

xtacy2• 11 years ago

Oops, sorry, I didn't mean to say you used a RBF kernel. I edited my comment above. I meant to say your embedding resembles the polynomial kernel (not RBF, which was just meant as a generalisation of such neat tricks :)).

What I meant to say was that you didn't need to compute the embedding explicitly. Since you embed into a space that has a nice structure, you can compute the dot product of the embedded vectors without having to compute the embedding explicitly.

srean4• 11 years ago

Could you elaborate on its differences from the kernel trick. It seems to me @xtacy is exactly right on that modeling point. Training the model using scale appropriate optimization is an orthogonal concern, if that is what you were getting at, i.e. an off the shelf kernelization would not be sufficient to run this at scale.

mattwilson2• 11 years ago

The Factorization Machine term can be computed in O(kn) time where k is a hyper-parameter of the model and n is the number of features in the model. The features are embedded in a k dimensional space so there is nothing infinite dimensional going on with FM.

iaw• 11 years ago

I don't quite understand the benefit of replacing the weighting with a vector. Could anyone offer additional insight?

99decisionstr4• 11 years ago

The idea is that FM is a way to learn the polynomial kernel, by representing each high-order term as a low dimensional dot-product. It improves generalization error by learning a better polynomial kernel, because terms in the kernel are learnt jointly instead of separately, which helps a lot on the sparse combinations of features.

mattwilson2• 11 years ago

Without factorization machines, you would have O(n^2) quadratic weights w_{i,j} to learn. This is bad in a setting like online advertising where you might have millions of features (i.e. n is large) for two reasons. First, this makes training your model very slow. Second, you won't have enough observations to learn all weights w_{i,j} well. So using all quadratic weights in the online advertising setting is not feasible. But we still want to include feature interaction information. Enter FM.

To answer your question, FM is good for two main reasons. First, as a result of some mathematical magic, we can train the model in a time that scales linearly with the time needed to train a model without interaction terms. Second, each of the n features gets embedded in an inner product space with similar features ending up close to one another in some sense. This allows us to make a decent estimate of the interaction between features even if they do not appear frequently in the training data.

fiatmoney• 11 years ago

This is the main paper on factorization machines, which discusses some of the advantages:

http://www.ismll.uni-hildesheim.de/pub/pdfs/Rendle2010FM.pdf

In particular they're nice for recommendation algorithms.

srean4• 11 years ago

If there are any Adroll folks on this thread, really curious to know about Adroll's use of the D programming language, how it has worked out, anecdotes, stories etc. That you use already makes it an attractive place :)

99decisionstr4• 11 years ago

Sure! Here are some insights: https://news.ycombinator.com/item?id=10136197

D is awesome for what we do with it. It unlocks our small team of data scientists to have a huge impact on the company, as we don't have to rely on frameworks such as your typical hadoop/spark cluster which require engineers just to maintain it. We can also use the same code path offline and online where we have very strong latency and QPS requirements.

D makes us ship more often, with less humans. The runtime is not perfect yet, but the language and compiler are awesome. It keeps our codebase small, simple and very efficient.

srean4• 11 years ago

Now that's just bragging with the express purpose of making me envious. So how fast can you come to India :)

Factorization Machines

Related Stories