Recommenders: ordering top-k using argpartition()

[WessZumino]

While writing the recommend_k_items() method for the rbm I noticed a small problem related to the argpartition() function. Basically, the returned k-items are not sorted in order, so a smaller number may appear earlier in the list than a bigger one.

This seems to happen with real numbers that are very close, e.g. 4.979 vs 4.981 but it may affect other situations as well. The solution is provided below, more details in

https://docs.scipy.org/doc/numpy/reference/generated/numpy.argpartition.html#numpy.argpartition

What is affected by this bug?

1. recommend_k_items() method

This is used to select the top-k items in SAR

How do we replicate the issue?

consider the following vector
a = np.random.rand(10000)*100

I want the labels of the first 10 elements in decreasing order (biggest --> small), i.e. top_k=10
1) id1 = np.argpartition(-a, top_k)[:top_k]
returns: array([8255, 1269, 1778, 9788, 8726, 5621, 5660, 9619, 8709, 6207], dtype=int64)

Now we can check the actual values
a[id1] = array([99.97332566, 99.9455154 , 99.92515612, 99.94902373, 99.98342226, 99.95773838, 99.93918414, 99.99000961, 99.92482682, 99.92437996])

In the above example, 99.92 is positioned earlier than 99.94 or 99.98. In SAR, the function is used as
id1= np.argpartition(a, -top_k)[-top_k:] , giving:
id1 = array([6207, 8709, 1778, 5660, 8726, 9788, 5621, 1269, 9619, 8255],dtype=int64)
again, we can look at the actual values and find the same problem, just with a different order:

a[id1]= array([99.92437996, 99.92482682, 99.92515612, 99.93918414, 99.98342226, 99.94902373, 99.95773838, 99.9455154 , 99.99000961, 99.97332566])

Expected behavior (i.e. solution)

Solution 1: use full sorting algo like argsort
id2 = np.argsort(-a)[:top_k], giving:
id2 = array([9619, 8726, 8255, 5621, 9788, 1269, 5660, 1778, 8709, 6207], dtype=int64)
with values correctly ordered:
a[id2] = array([99.99000961, 99.98342226, 99.97332566, 99.95773838, 99.94902373, 99.9455154 , 99.93918414, 99.92515612, 99.92482682, 99.92437996])

this solution is slower than np.argpartition().

Solution 2 (preferred): use top_k as a list
id3 = np.argpartition(-a, range(top_k) )[:10], giving the same result of argsort()
id3= array([9619, 8726, 8255, 5621, 9788, 1269, 5660, 1778, 8709, 6207], dtype=int64)

benchmark: For a small array as the one considered in the example above the time difference of the two
algos is negligible. However, for the movielens dataset, the user-affinity matrix is (6040, 3952), in this case
np.argsort() --> 1.2492165565490723
np.argpartition() --> 0.29970526695251465

Therefore, solution 2 seems the preferred one

[yueguoguo]

@maxkazmsft @eisber for visibility.

[anargyri]

Another alternative is to use python's heapq (I think Max uses it in his SAR code).

[miguelgfierro]

this is awesome @WessZumino, could you also please benchmark heapq with the same data you used in solution 1 and 2?

[WessZumino]

@anargyri in the SAR code (the single node at least) we use argpartition. I haven't tried heapq but I can benchmark it following @miguelgfierro suggestion. Also, in this post they suggest to use bottleneck and show few other methods with benchmarks.

[anargyri]

@WessZumino It would be great if you could benchmark these. I thought @maxkazmsft used heapq but maybe I am wrong. I am not aware of bottleneck but you could try it -- maybe also double check you get the same results as the other methods ;-). In theory, heap select should be fast but in practice argsort could be better, as they say in https://docs.python.org/3.5/library/heapq.html.

[anargyri]

Another alternative is to put the numpy array in a Pandas series and use pd.Series.nlargest(top_k). This function gives the correct result and we use it in the evaluation utility https://github.com/Microsoft/Recommenders/blob/98a2ce1dde2cf6637a7982cec80cc700851f54b1/reco_utils/evaluation/python_evaluation.py#L574

[WessZumino]

Hi guys, as discussed with @maxkazmsft on teams, I am closing this issue. Sorting takes place in the evaluation utility, as also confirmed by @anargyri so there seem to be no need to add this function in the top_k method.

[maxkazmsft]

Going to add a flag and heapq code as we discussed - PR coming up today.

[anargyri]

I tried a quick check by calling Spark MLLib's recommendForAllUsers() and it seems that the top-k recommendations returned are sorted:

[Row(itemID=1199, rating=10.561881065368652), Row(itemID=1643, rating=10.118582725524902), Row(itemID=1419, rating=9.433361053466797), Row(itemID=267, rating=9.039209365844727), Row(itemID=1015, rating=8.95529556274414), Row(itemID=1311, rating=8.930313110351562), Row(itemID=364, rating=8.380996704101562), Row(itemID=1184, rating=8.251058578491211), Row(itemID=838, rating=8.172403335571289), Row(itemID=592, rating=8.005163192749023)]

So, how about we follow the same convention for SAR as well?
Also please update the docstring according to any changes you make.

[yueguoguo]

Fixed in #290