LibFM in python

LibFM is library for factorization machines using an approach proposed by Steffen Rendle. However it seems that there is no python wrapper for this famous library.

However, if you're looking for python version of it, take a look at these projects:

Update: I've tested some LibFM implementations on several datasets. I included libFM and options proposed in this post.

• https://github.com/coreylynch/pyFM
  Lovely minimalistic implementation of Factorization Machines using cython (previous version used numpy).
  This library has an interface similar to scikit-learn.
• http://ibayer.github.io/fastFM/index.html
  fastFM is another option. Library supports both classification and regression.
  Contains three different solvers (SGD, ALS, MCMC). ALS = alternative least squares.
  In the paper written by author of algorithm, he argues that other algorithms are comparable to SGD.
  
  This library is completely following scikit-learn interface (even deriving from BaseEstimator and appropriate mixin classes).
• I was also looking for code in theano, but the only code I found was very dirty and minimalistic (so I'm not hoping it is usable)
  https://github.com/instagibbs/FactorizationMachine

Numpy tricks (again)

A small post about different tricks I use in numpy. Since frequently I work with statistical data and different statistical criterions, frequently I have to compute the order statistics (alternatively, one can ask about which position will get every number in array after array was sorted)
There is rankdata function inside scipy which solves the named problem:

result = rankdata(array)

However, one can easily implement this is numpy (isn't beautiful?):

result = numpy.argsort(numpy.argsort(array))

which is (almost) equivalent code.
See also my previous post on numpy tricks
PS. Once upon a time I will understand why all blogging platforms suggest heavy and ugly layout templates. Even adding background image turns into non-trivial task.

Vector representations of categories

After thinking a while over the last point in my list of topics in machine learning I was going to think over...

I finally came to the thought that I'd better use some graphical model, since there is a great majority of possible algorithms without any warranty of their workability.

So, first thing - probably one can use LDA (Latent Dirichlet allocation, wiki) to find good representation for categories. In this case we should use bag-of-words model, and `categories` will stand for words.
Yes, the model of LDA doesn't seem to be appropriate, though I'm sure it will give reasonable representations.

Another graphical model I came with, is much simpler (and probably was developed a long time ago, but I don't know).
It's generative model looks looks this:

1. First, a `topic` of event is generated. That's an n-dimensional vector $t_{event} \in \mathbb{R}^n$ drawn from gaussian distribution.
2. For each category, say, `site_id`, each value of site_id has it's own topic $t_{cat.value}$ of same dimension $n$. The greater dot product $(t_{cat.value}, t_{event})$, the higher probability that this value of category will be chosen. I shall stress here, that I'm not thinking over the arbitrary number of categories, I'm currently interested in the case, where the number and types of categories are fixed.
3. To be more precise, the probability of each value within category to be drawn for the event with $t_{event}$ vector is propostional to $$ p(\text{cat_value} | \text{event}) \sim p(\text{cat.value}) \times e^{(t_{cat.value}, t_{event})} $$ so, to compute final probability one shall use softmax function.

That said, currently the problem I expect to meet is extremely low speed of training when the number of values for some category is very large (say, there are cases when number of categories one shall proceed is greater then 10000)

PS. After writing this I understood that usage of decision trees to generate ids of leaves - new 'categories' + usage of LibFM over these new features was a very interesting and good idea.

Code and the importance of vectorization

That awkward moment, when the code written in matlab is easier to read and understand then tons os explanations:
Salakhudinov's code of RBM

This code IMHO is a good argument when you need to explain someone that he really needs to learn at least one language with vectorization, no matter whether it is R, matlab, or numpy or theano in python.

Numpy exercises

When one starts writing in python, the typical reaction is disappointment about how slow it is compared to any compilable language. After a while, you learn numpy and find out it's actually not so bad.

Having spent a month with numpy, I found out that many things can be written in it.
Having spent a year with it, I found out that almost any algorithm may be vectorized, though it's sometimes non-trivial.

I'm still quite disappointed about the most answers at stackoverflow, where people prefer plain python for any nontrivial thing.

For instance, you need to compute statistics of values in array. Well, you can sort array and keep track of initial position. Alternatively, you can do it in numpy-one-liner:

order_statistics = numpy.argsort(numpy.argsort(initial_array))

Don't believe? Check this!
Want to compute mean value over the group of events? Another one-liner:

means = numpy.bincount(group_indices, weights=values) / numpy.bincount(group_indices)

Writing oblivious decision tree in numpy is very simple and can be done really fast.

As a non-trivial problem: will you be able to write application of usual decision tree in pure numpy? For simplicity, you can first consider only trees with equal depth of all leaves.

Simplification vs usability

When one designs library/API/whatever, there are two things that one always cares of: flexibility and minimalism. Good solutions incorporate both these points, but sometimes one has to sacrifice some 'very useful feature' for the sake of simplicity of system.

Ok, this was just to say: I'm disappointed by PEP-3113
https://www.python.org/dev/peps/pep-3113/

It's already implemented in python3 and it removes tuple unpacking in arguments.
Yes, this cool feature is inavalibale in python3:

map( lambda id, (key, group): (len(group), key), data)

Problems with annotations are understandable, but there is category of applications when automatic untupling is very handy and annotations are not needed.

Pairwise layer in neural network

In one of previous posts I said that pairwise layer doesn't seem to work...

Well, I was wrong: after checking on higgs-boson dataset from kaggle I found out that this kind of neural network works much better than traditional ones! Hurrah!

Though, much worse then GBDT, but after building AdaBoost over neural network I was able to get comparable (or just the same) quality. The only problem is GBDT trained in minutes, while it took ~24 hours for boosting over NN to train.

Benchmarks of speed (Numpy vs all)

Personally I am a big fan of numpy package, since it makes the code clean and still quite fast.
However I am much worried about the speed, so decided to collect different benchmarks

I decided to write my own benchmarks with several non-trivial operation to check things claimed at different sources. Please find it here here. In my tests numpy is not much slower than other libraries or C++.

numpy vs cython vs weave (numpy is about 2 times slower than others)
(posted in 2011)
http://technicaldiscovery.blogspot.ru/2011/06/speeding-up-python-numpy-cython-and.html

Primarily the post is about numba, the pairwise distances are computed with cython, numpy, numba.
Numba is claimed to be the fastest, around 10 times faster than numpy.
(posted in 2013)
https://jakevdp.github.io/blog/2013/06/15/numba-vs-cython-take-2/

Julia is claimed by its developers to be very fast language.
Well, if that is true, there would be no need in writing easily-vectorizable operation in pure python (yep, I mean they are simply cheating), currently these 'benchmarks' are at the main page
http://julialang.org/

The following post was written in 2011, the problem observed is solution of Laplace equation as usual.
Numpy is ~10 times slower than pure C++ solution (and equal to matlab), weave shows the speed comparable with pure C++ (I don't know anyone using weave now)
http://wiki.scipy.org/PerformancePython

Fresh (2014) benchmark of different python tools, simple vectorized expression A*B-4.1*A > 2.5*B is evaluated with numpy, cython, numba, numexpr, and parakeet (and two latest are the fastest - about 10 times less time than numpy, achieved by using multithreading with two cores)
http://nbviewer.ipython.org/github/rasbt/One-Python-benchmark-per-day/blob/master/ipython_nbs/day7_2_jit_numpy.ipynb

Haven't found any general-purpose theano vs numpy benchmarks, but in the article there is comparison of neural networks and theano is expected to give much better speed than numpy/torch(c++)/matlab, specially it is fast on GPU
http://conference.scipy.org/proceedings/scipy2010/pdfs/bergstra.pdf


One more detailed review of numpy vs cython vs c (held in 2014)
http://notes-on-cython.readthedocs.org/en/latest/std_dev.html
Let me copy-paste the example results (computation of std).

Method	Time (ms)	Compared to Python	Compared to Numpy
Pure Python	183	x1	x0.03
Numpy	5.97	x31	x1
Naive Cython	7.76	x24	x0.8
Optimised Cython	2.18	x84	x2.7
Cython calling C	2.22	x82	x2.7

Simple, but comprehensive comparison of python accelerators was prepared by Jake Vanderplaas and Olivier Grisel:
http://nbviewer.ipython.org/github/ogrisel/notebooks/blob/master/Numba%20Parakeet%20Cython.ipynb
Problem is computation of pairwise distances. The results this time seem to be unbiased:

Python	9.51s
Naive numpy	64.7 ms
Numba	6.72ms
Cython	6.57ms
Parakeet	12.3 ms
Cython	6.57 ms

By the way, I was recently looking for a slow place in my code, and it totally dropped of my mind that computation of residual is long operation:
http://embeddedgurus.com/stack-overflow/2011/02/efficient-c-tip-13-use-the-modulus-operator-with-caution/
Integer division / remainder computation time significaly depends on the bit depth (16 bit operation are ~2 times faster than 32 bit ones, division takes roughly 10 times more time than multiplication).

Surprising: multiplication/addition/binary operations take the same time (compared on numpy 1.9)

Optimization of vector operations

Recently worked over optimization of some (secret) classifier. The problem was mostly not in training, but in applying of trained classifier — this code was originally written in C++ and then translated to cython (which decreased the speed by factor of 2).

This was quite easy rewrite the code using numpy and vectorized approach (initally predictions were built event-by event, after rewriting the classifier was applied tree-by-tree). However this gave only speed comparable with original C++ code (so, twixe faster cython).

What really fastened the code is switching from int8 operations to int64 (the latest are natively supported in all modern processors). So 8 operations in int8 were grouped into one 64-bit. This is done pretty simple by creating views:

In[1]: import numpy
In[2]: x = numpy.random.randint(0, 100, size=64000).astype(’int8′)
In[3]: y = numpy.random.randint(0, 100, size=64000).astype(’int8′)
In[4]: %timeit x & y 
10000 loops, best of 3: 60.6 µs per loop
In[5]: %timeit x.view(’int64′) & y.view(’int64′) 
100000 loops, best of 3: 12 µs per loop
# Checked that output is correct
In[6]: numpy.all( (x & y) == (x.view(’int64′) & y.view(’int64’)).view(’int8′) )
Out[6]: True

 

In this simple example we see 5x speed up. Views of course do not copy the data, which is very essential for the speed. This trick can be applied with: summation / subtration / binary or / binary and, but you need that the size of original array was divisible by 8.

By the way, there is awesome collection of twiddling bits, which was my starting point in bit optimizations.

Theano (python library)

If you want to experiment with neural networks,  and you know python, then my best recommendation is: use theano.

Theano is not about neural networks, really - it is ... hm ... mathematical engine. Something between Matlab and Mathematica.
It is close to Matlab because uses vectorization (the final function will operate vectors).

It is close to Mathematica,  because first you define some expression (function as analytical expression). You can compute (analytical) derivatives, and this is crucial for neural networks, because the main thing you need is derivatives, and nobody wants to spend his time on computing derivatives, specially when some library can do this for you.

After you defined needed function-expressions (activation function and gradient of loss function for neural network), you can compile it with theano (get really a function that can be evaluated for some arguments). The compiled function is vectorized and very fast (though compilation usually takes some time). Your functions can be evaluated on GPU as well.

This gives an ability to define your new neural networks in few lines of code (just by defining activation function). Impressive?

Documentation on theano
Github
Examples (mostly about neural networks, probably the easiest way to start and understand how good theano is)

Even more examples (with less explanation) can be found here.